파국적 백트래킹과 그 밖의 정규식 함정

백만 개 입력에서 마이크로초 만에 도는 정규식이, 백만 한 번째 입력에서 요청 스레드를 몇 초간 멈출 수 있습니다. 원인은 거의 항상 같습니다. 겹치는 수량자를 가진 패턴에 거의 매칭되는 입력이 들어온 경우입니다. 엔진은 포기하기 전에 실패하는 방법을 지수적으로 많이 탐색합니다. 이 글은 그 폭발이 어떻게 일어나는지, 그것을 일으키는 패턴을 어떻게 알아보는지, 그리고 대신 무엇을 해야 하는지 설명하겠습니다.

백트래킹 엔진이 패턴을 평가하는 방식

일상적으로 쓰는 정규식 엔진 대부분은 백트래킹 NFA 엔진입니다. PCRE, 자바의 java.util.regex, 자바스크립트의 RegExp, 파이썬의 re, 루비의 Onigmo, .NET입니다. 이들은 한 가지 작동 원리를 공유합니다. +나 * 같은 수량자가 한 구간을 두 가지 이상의 방법으로 매칭할 수 있을 때, 엔진은 하나를 고르고 진행하다가 나머지 패턴이 실패하면 되돌아가 다음 방법을 시도합니다.

구체적으로, a+를 aaa에 매칭하면 이렇습니다.

• a+가 욕심껏 a 세 개를 모두 소비합니다.
• 패턴에서 그 뒤에 오는 것이 그 위치에서 시도됩니다.
• 실패하면 a+가 a 하나를 되돌려주고 다시 시도합니다.
• 이것은 패턴이 매칭되거나 a+가 a 하나로 줄어들 때까지 반복됩니다.

단일 수량자라면 재시도 횟수는 입력 길이에 선형입니다. 문제는 두 수량자가 같은 문자를 차지할 수 있을 때 시작됩니다.

파국적 백트래킹과 ReDoS

이 패턴을 봅시다.

^(a+)+$

"하나 이상의 a, 그룹으로 묶어, 하나 이상 반복, 문자열 끝까지"라는 뜻입니다. aaaa에는 즉시 매칭됩니다. aaaaaaaaaaaaaaaaaaaaaaaaX에는 매칭되지 않고(X가 깨뜨립니다), 그 매칭되지 않는 입력이 최악의 경우입니다.

안쪽 a+와 바깥 (...)+가 완전히 겹칩니다. n개의 a 묶음은 두 수량자 사이에 2^(n-1)가지 서로 다른 방법으로 나눌 수 있습니다. 한 큰 그룹, 두 그룹, n개의 낱개, 그리고 그 사이의 모든 조합입니다. 문자열이 입력 끝이 아니라 X로 끝나므로, 그 모든 분할이 $ 앵커에서 실패합니다. 엔진은 매칭이 없다고 결론짓기 전에 그 전부를 충실히 시도합니다. a를 하나 더 추가하면 작업량이 두 배가 됩니다.

같은 형태가 더 현실적으로 보이는 패턴 안에 숨어 있습니다.

^(\w+\s*)*$          # 공백으로 구분된 단어
^(\d+)*$             # 반복되는 숫자 그룹
(.*,)*               # 쉼표로 구분된 무엇이든
^([a-z]+)*$          # 전형적인 예

각각은 두 수량자가 같은 문자를 매칭할 수 있는 곳에서, 수량화된 하위식이 또 다른 수량자 안에 중첩돼 있습니다. 실패는 거의 매칭되는 긴 입력, 보통 공격자가 제어하는 입력으로 촉발됩니다.

이것이 이를 단순한 성능 함정이 아니라 서비스 거부 벡터로 만드는 점입니다. ReDoS(정규식 서비스 거부)는 입력 검증에 쓰인 정규식, 즉 이메일 필드나 User-Agent 파서, URL 라우트 매처가 공격자 입력에 노출될 때 일어납니다. 공격자는 수십 바이트 길이의 조작된 문자열을 보내고, 서버는 정규식 엔진에서 몇 초에서 몇 분을 쓰며, 소수의 요청이 스레드 풀을 고갈시킵니다. 포럼에서 복사한 검증 정규식이 반복적 원인입니다. 잘 구성된 입력을 받아들이도록 작성됐을 뿐, 악의적인 거의-매칭에 대해 한 번도 테스트되지 않았기 때문입니다.

욕심 vs 게으름은 해결책이 아닙니다

흔한 반사적 대응은 욕심 수량자를 게으른 것으로 바꾸는 것입니다. .*를 .*?로, +를 +?로, "게으르면 일을 덜 한다"는 이론에 기대서요. 게으른 수량자는 엔진이 가능성을 시도하는 순서를 바꿉니다. 욕심은 가장 긴 매칭을 먼저 시도하고 물러나며, 게으름은 가장 짧은 것을 먼저 시도하고 늘립니다. 가능성의 개수는 바꾸지 않습니다. 파국적으로 백트래킹하는 패턴은 게으르게 만들어도 똑같이 파국적으로 백트래킹합니다. 엔진이 탐색 공간의 어느 끝에서 시작하는지만 바꿨을 뿐입니다. 게으른 수량자는 정확성 도구(가장 작은 구간 매칭)이지 성능 도구가 아닙니다.

실제로 통하는 완화책

모호성을 제거하세요. ^(a+)+$의 진짜 해법은 그것이 ^a+$와 동치임을 알아차리는 것입니다. 파국적 패턴 대부분은 평평하고 모호하지 않은 다시 쓰기가 있습니다. 공백으로 구분된 단어가 필요하다면, ^\w+(\s+\w+)*$는 구분자와 단어가 같은 문자를 매칭할 수 없으므로 ^(\w+\s*)*$가 모호한 곳에서 모호하지 않습니다.

패턴을 앵커하세요. 앵커는 탐색을 묶습니다. 앵커 없는 패턴은 암묵적으로 모든 시작 위치에서 시도되어 작업량을 늘리고, 종종 느림과 거짓 매칭 둘 다의 원인이 됩니다.

아토믹 그룹이나 소유 수량자를 쓰세요. 엔진이 지원한다면요. 아토믹 그룹 (?>...)는 내용을 매칭한 다음 그 안의 백트래킹 위치를 버립니다. 한번 매칭되면 엔진은 그 문자들을 되돌려주지 않습니다. 소유 수량자 a++는 단일 수량자에 대한 같은 개념의 약식입니다. (a+)+를 (?>a+)+나 a++로 다시 쓰면 지수 탐색이 선형으로 무너집니다. 엔진 지원은 제각각입니다.

엔진	아토믹 그룹 (?>…)	소유 수량자 a++	비고
PCRE / PCRE2	예	예	완전 지원
Java java.util.regex	예	예	Java 4 / 5부터
Ruby (Onigmo)	예	예
.NET	예	아니요	소유 수량자 미지원
Python re	예	예	3.11부터 아토믹 + 소유
JavaScript RegExp	아니요	아니요	TC39 제안 단계, lookahead로 흉내

자바스크립트에서 아토믹 그룹과 소유 수량자는 아직 언어의 일부가 아니라 제안입니다. 표준 우회법은 lookahead와 역참조로 아토믹성을 흉내 내는 것입니다. (?=(a+))\1은 욕심 매칭을 캡처하고 되돌려주기를 거부합니다.

선형 엔진으로 바꾸세요. RE2(구글), 러스트 regex 크레이트, Go의 regexp은 다른 실행 모델을 씁니다. 백트래킹 없이 NFA를 시뮬레이션해, 패턴과 무관하게 입력 길이에 선형인 매칭 시간을 보장합니다. 대가는 기능 손실입니다. 역참조도, lookaround도 없습니다. 이 기능들이 애초에 백트래킹을 강제하는 것이기 때문입니다. 신뢰할 수 없는 패턴이나 신뢰할 수 없는 입력을 정규식에 통과시킨다면, 선형 엔진은 ReDoS 부류 전체를 구조적으로 제거합니다. 정규식이나 그 입력이 온전히 통제되지 않는, 사용자를 마주하는 모든 것에 대해 그것이 올바른 기본값입니다.

앵커, lookaround, 그리고 그 비용

^와 $는 문자열(또는 줄) 경계를 매칭하고, \b는 단어 경계를 매칭합니다. 성능 역할을 넘어, 앵커가 없으면 정확성 버그가 생깁니다. \d{4}는 abc12345 안에서도 매칭되므로, ^...$ 없는 "연도" 검증기는 garbage1999garbage를 받아들입니다. 의도적으로 앵커하고, 플래그에 따라 $가 문자열 끝을 매칭하는지 줄 끝을 매칭하는지 알아두세요(MULTILINE이 이를 바꿉니다).

lookahead (?=...) / (?!...)와 lookbehind (?<=...) / (?<!...)는 문자를 소비하지 않고 무언가가 나타나는지 아닌지를 단언합니다. 비밀번호 규칙, "Y가 뒤따르지 않는 X 매칭" 등에 유용하지만, 각 단언은 그 위치에서 하위 매칭을 돌리고, 특히 lookbehind는 내용이 가변 길이일 때 비쌀 수 있습니다. 이들은 또 백트래킹 엔진을 강제해 RE2 류를 배제합니다. 대안이 정말로 더 나쁠 때 손을 뻗으세요. 기본값으로 쓰지 마세요.

정규식을 아예 쓰지 말아야 할 때

정규식은 정규 언어를 매칭합니다. 중첩되거나 재귀적인 구조는 정규가 아니며, 그것을 매칭하려 하면 깨지기 쉽고, 읽을 수 없고, 조용히 틀린 패턴으로 이어집니다.

• HTML과 XML. 진짜 파서를 쓰세요. 태그 수프 정규식은 항상 한 경우를 놓칩니다.
• JSON, YAML, 소스 코드. 중첩 깊이가 무한합니다. 정규식은 균형 잡힌 구분자를 셀 수 없습니다.
• 산술식, 균형 잡힌 괄호. 같은 문제입니다.
• 따옴표 안에 쉼표가 들어 있는 CSV. 전용 CSV 리더가 더 짧고 정확합니다.

정규식은 토큰화, 평평한 형식 검증, 줄 단위 검색·치환에 알맞은 도구입니다. 중첩되는 것을 매칭하려 한다는 것을 깨닫는 순간, 멈추고 파서로 손을 뻗으세요.

배포 전에 테스트하세요

가장 싼 방어는 모든 검증 패턴을, 프로덕션에 닿기 전에 길고 거의 매칭되는 악의적 입력에 대해 테스트하는 것입니다. 행복 경로만이 아니라요. 우리 정규식 테스터는 패턴을 샘플 문자열에 대해 돌리고 어떻게 동작하는지 볼 수 있게 해, 공격자가 찾기 전에 모호한 수량자를 잡을 수 있습니다. 거기에 모호하지 않은 다시 쓰기, 명시적 앵커, 그리고 통제하지 않는 입력에 대한 선형 엔진을 더하면, 파국적 경우는 결코 발생하지 않습니다.