thenullpage.com
회원가입 폼에서 이름 칸을 검사하는 정규식을 넣어뒀는데, 어떤 사용자가 거기에 긴 글자를 붙여 넣자 서버 응답이 통째로 멈춰버린 일이 있어요. 무한 반복문도 없고 데이터베이스를 부른 것도 아닌데요. 범인은 정규식 한 줄이었어요. 정규식은 답을 못 찾으면 가능한 경우를 전부 뒤져보는데, 그 경우의 수가 글자 하나 늘 때마다 두 배씩 뛰는 패턴이 있거든요. 오늘은 그 함정을 직접 시간을 재보면서 어떻게 알아보고 피하는지 볼게요.
11.1 정규식은 답을 어떻게 찾나요?
엔진은 일단 최대한 많이 먹고, 그러다 뒤가 안 맞으면 한 글자씩 뱉으면서 다시 시도해요. 이 되돌아가기를 백트래킹이라고 불러요.
import re
글 = '말하길 "안녕" 그리고 "잘가"'
re.findall(r'".*"', 글)
결과: ['"안녕" 그리고 "잘가"']
따옴표 한 쌍만 잡고 싶었는데 마지막 따옴표까지 삼켰죠. .*가 끝까지 먹고 나서 닫는 따옴표를 찾느라 뒤로 물러났고, 처음 만난 게 맨 뒤 따옴표였던 거예요.
re.findall(r'"[^"]*"', 글)
결과: ['"안녕"', '"잘가"']
따옴표가 아닌 글자만 먹으라고 하니 되돌아갈 일 자체가 없어졌어요. 여기서는 결과만 달라졌지만, 되돌아가는 횟수가 감당 못 할 만큼 늘어나면 결과가 아니라 시간이 문제가 돼요.
11.2 시간이 폭발한다는 게 무슨 말인가요?
문제가 되는 건 이렇게 생긴 패턴이에요. 단어와 공백이 반복되는 이름을 검사하려고 쓴 거예요.
re.fullmatch(r"(\w+\s?)*", "hong gil dong")
결과: <re.Match object; span=(0, 13), match='hong gil dong'>
멀쩡히 통과해요. 문제는 실패할 때 생겨요. "aaaa!"처럼 끝에 안 되는 글자가 붙으면 엔진은 실패를 선언하기 전에 다른 방법이 없는지 전부 확인해요.
그런데 a 네 개를 (\w+)로 나누는 방법이 한 가지가 아니에요. 통째로 aaaa, 또는 aaa와 a, aa와 aa, 한 글자씩 네 번, 이런 식으로 쪼개는 조합이 다 따로예요. 글자가 하나 늘 때마다 이 조합이 두 배가 돼요.
스무 글자면 백만 가지, 서른 글자면 십억 가지예요. 엔진은 그 전부를 하나씩 밟아본 다음에야 안 된다고 답해요.
짧은 걸로 먼저 보면 이래요.
re.fullmatch(r"(\w+\s?)*", "aaaa!")
결과: None
돌려받은 답은 None 한 줄이죠. 이 한 줄을 내놓기까지 엔진은 a 넷을 쪼개는 조합을 빠짐없이 밟았어요. 넷일 때는 눈 깜짝할 새라 티가 안 나요. 무서운 건 이 조합 수가 자라는 속도예요.
11.3 정말 그렇게 느려지나요?
직접 재보는 게 제일 확실해요.
import re, time
검사 = re.compile(r"^(\w+\s?)*$")
for n in (20, 22, 24, 26, 28):
글 = "a" * n + "!"
시작 = time.time()
검사.match(글)
print(n, round(time.time() - 시작, 2))
결과:
20 0.16
22 0.61
24 2.48
26 9.77
28 38.98
스물여덟 글자짜리 입력 하나에 39초를 썼어요. 글자 두 개 늘 때마다 시간이 네 배씩 뛰는 게 보이시죠. 여기서 몇 글자만 더 붙이면 몇 시간이 돼요.
이게 왜 무서운 사고인지 감이 오실 거예요. 그동안 그 요청을 처리하던 자리는 아무 일도 못 해요. 공격자가 이런 문자열을 몇 개만 동시에 보내면 서버 전체가 멈춰요. 이걸 레도스(ReDoS, 정규식을 이용한 서비스 거부)라고 불러요.
11.4 위험한 패턴은 어떻게 알아보나요?
신호는 딱 하나예요. 수량자 안에 또 수량자가 들어 있는 모양이에요.
(a+)+
(\w+\s?)*
(.*)*
(\d+)*
(a|a)*
겉모습은 달라도 속뜻은 같아요. 같은 글자를 여러 갈래로 나눠 먹을 수 있는가, 이게 기준이에요. 나누는 방법이 두 가지 이상이면 엔진은 그 조합을 전부 시도할 의무가 생겨요.
더 고약한 건 통과하는 입력에서는 멀쩡하다는 점이에요. 성공하면 첫 번째 조합에서 바로 끝나거든요. 그래서 개발할 때 정상 값만 넣어보면 아무 문제가 없고, 운영에 올린 뒤 이상한 값이 들어오는 날 처음 터져요. 테스트할 때 일부러 실패할 값을 넣어봐야 하는 이유예요.
이런 입력이 어디서 들어오나 하면 대부분 우리가 직접 만든 폼이에요. 이름, 검색어, 주소, 파일 이름처럼 길이 제한 없이 받는 칸이 전부 통로가 돼요. 사용자가 올린 글을 훑는 스크립트도 마찬가지고요. 특히 인터넷에서 복사해 온 패턴이라면 한 번 더 보세요. 짧고 그럴듯한 한 줄에 반복이 두 겹 들어 있는 경우가 생각보다 많아요.
11.5 그럼 어떻게 고치나요?
나누는 방법이 하나뿐이 되게 다시 쓰면 돼요.
안전 = re.compile(r"^\w+(\s\w+)*$")
시작 = time.time()
print(안전.match("a" * 40 + "!"))
print(round(time.time() - 시작, 6))
결과:
None
1e-05
마흔 글자인데 0.00001초에 끝났어요. 아까 스물여덟 글자에 39초 걸리던 것과 같은 일을 한 거예요.
차이는 \s에서 물음표를 떼고 공백을 필수로 만든 데 있어요. 단어 다음엔 반드시 공백이 와야 하니 aaaa를 두 덩어리로 쪼갤 방법이 아예 없어요. 갈림길이 사라지면 되돌아갈 일도 없죠.
고칠 때 요령은 이거예요. 반복 안에 있어도 되고 없어도 되는 것(?나 *)이 끼어 있으면 의심하세요. 첫 덩어리를 반복 밖으로 빼내고, 반복 부분은 구분자로 시작하게 만들면 대부분 풀려요.
다 고쳤으면 원래 받던 값이 그대로 통과하는지 반드시 확인하세요. 빨라졌는데 멀쩡한 입력을 거부하면 더 큰 사고니까요.
안전.fullmatch("hong gil dong")
결과: <re.Match object; span=(0, 13), match='hong gil dong'>
11.6 패턴을 못 고치는 상황이면요?
제일 싸고 확실한 방법은 길이를 먼저 자르는 것이에요.
값 = 입력값.strip()
if len(값) > 100:
return "너무 깁니다"
백 글자 이름은 어차피 받을 이유가 없잖아요. 정규식에 닿기 전에 막으면 폭발할 재료 자체가 안 들어와요.
파이썬 3.11부터는 한 번 먹은 걸 도로 뱉지 않는 문법도 쓸 수 있어요. 괄호 앞에 ?>를 붙이는 원자 그룹이에요.
시작 = time.time()
print(re.match(r"^(?>\w+\s?)*$", "a" * 40 + "!"))
print(round(time.time() - 시작, 6))
결과:
None
3.7e-05
수량자 뒤에 더하기를 하나 더 붙이는 \w++ 형태도 같은 뜻이에요. 다만 이건 파이썬 3.10 이하나 자바스크립트에서는 안 되니, 쓰기 전에 쓰는 곳에서 되는지 확인하세요.
참고로 파이썬 표준 정규식에는 시간 제한 옵션이 없어요. 오래 걸리면 그냥 오래 걸려요. 반면 백트래킹을 아예 안 하는 엔진도 있는데, 고 언어의 기본 정규식이 그래요. 항상 입력 길이에 비례하는 시간만 쓰는 대신 룩어라운드와 역참조를 못 써요. 사용자가 넣은 문자열을 대량으로 검사하는 자리라면 이런 선택지도 있다는 걸 알아두면 좋아요.
정리하면 챙길 건 세 가지예요. 반복 안에 반복이 보이면 일단 의심하기, 정상 값 말고 실패할 값으로 시간을 재보기, 그리고 정규식을 만지기 전에 길이부터 자르기. 지금 쓰고 계신 패턴 중에 *나 +가 두 겹으로 겹친 게 있다면, 오늘 그 아래에 time.time 두 줄만 넣고 안 맞는 문자열을 한번 던져보세요. 몇 초씩 멈추는 게 눈으로 보이면 그때부터는 절대 안 잊어버려요.