정규식 그리디 vs 레이지 매칭과 ReDoS(재앙적 백트래킹) 완전정리
정규식에서 +, * 같은 정량자를 쓰다 보면 어느 순간 브라우저 탭이나 서버 프로세스가 그대로 멈춰버리는 경험을 할 수 있습니다. 특히 사용자 입력을 검증하는 정규식에서 이런 일이 벌어지면 단순한 버그를 넘어 서비스 거부(DoS) 공격의 통로가 됩니다. 이 가이드에서는 그 원인이 되는 그리디·레이지 매칭의 동작 방식과, 중첩된 정량자가 왜 지수적으로 느려지는 "재앙적 백트래킹(catastrophic backtracking)"을 일으키는지를 실제 예시로 풀어봅니다.
1. 그리디(탐욕적) 매칭 — 정량자의 기본 동작
+(1회 이상), *(0회 이상), {n,}(n회 이상) 같은 정량자는 정규식 엔진에서 기본적으로 그리디하게 동작합니다. 그리디하다는 것은 일단 매칭 가능한 최대 길이까지 욕심껏 문자를 삼킨다는 뜻입니다. 예를 들어 <.+>를 <b>굵게</b>라는 문자열에 적용하면, .+는 처음엔 문자열 끝까지 다 삼킨 뒤 뒤에 오는 >와 맞는 위치를 찾을 때까지 한 글자씩 되돌려줍니다(이 되돌리는 과정이 백트래킹입니다). 그 결과 첫 <b>가 아니라 마지막 </b>까지 통째로 매칭돼버립니다. 반면 정량자 뒤에 물음표를 붙인 +?, *?는 레이지(게으른) 매칭으로, 최소 길이(0개 또는 1개)부터 시도하다가 뒤쪽 패턴이 실패할 때만 한 글자씩 더 삼킵니다. 같은 문자열에 <.+?>를 적용하면 첫 번째 <b>에서 곧바로 멈춰 그 태그 하나만 매칭됩니다. 즉 그리디와 레이지의 차이는 "얼마나 먼저 많이 먹고 뒤로 물러나는가"와 "얼마나 적게 먹고 앞으로 나아가는가"의 방향 차이일 뿐, 둘 다 백트래킹이라는 같은 메커니즘을 씁니다.
2. 중첩 정량자가 위험한 이유 — 경로의 지수적 폭발
문제는 정량자 하나가 아니라 정량자 안에 또 정량자가 들어간 구조, 즉 (a+)+나 (a|aa)+ 같은 패턴입니다. 이런 패턴은 같은 문자열 구간을 서로 다른 방식으로 여러 번 나눠 담아도 결과가 똑같아지는 경우가 생깁니다. (a+)+로 aaaa를 매칭한다고 하면, 안쪽 그룹이 aaaa 전체를 한 번에 담을 수도 있고, aaa+a로 나눠 두 번 돌 수도 있고, aa+aa, a+a+a+a 등 문자를 그룹으로 쪼개는 모든 조합이 다 유효합니다. n개의 a를 나누는 조합의 수는 대략 2의 (n-1)제곱에 비례해서 늘어납니다. 매칭이 성공하는 입력이라면 엔진이 조합 하나를 찾자마자 멈추므로 큰 문제가 없지만, 문자열 끝에 ! 하나처럼 절대 매칭될 수 없는 문자를 붙여 놓으면 이야기가 달라집니다. 엔진은 성공할 조합이 하나도 없다는 걸 확인하기 위해 가능한 모든 나눔 방식을 백트래킹으로 전부 시도해야 하고, 이게 바로 "재앙적 백트래킹"입니다.
/(a+)+$/에 a를 50개 이어 붙이고 매칭이 절대 불가능하도록 마지막에 느낌표를 하나 붙인 문자열, 즉"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!"를 넣어 테스트해 보면, 짧은 자리수(10~15개)에서는 순식간에 "매칭 없음"이 뜨지만 a의 개수가 30개, 40개, 50개로 늘어날 때마다 처리 시간이 눈에 띄게 배로 늘어나는 것을 체감할 수 있습니다. $는 문자열 끝에서만 매칭되는데 끝에 !가 있어 애초에 성공할 수 없는 패턴이므로, 엔진은 a+를 나누는 모든 조합을 다 시도해 본 뒤에야 실패를 확정합니다. a가 50개면 대략 2의 49제곱에 가까운 경로를 확인해야 해서, 실제 서버라면 이 요청 하나가 CPU 코어 하나를 사실상 영구적으로 붙잡아 둡니다.
3. 실무에서 이걸 피하는 방법
가장 확실한 방법은 애초에 같은 문자 집합을 정량자 두 겹으로 감싸지 않는 것입니다. (a+)+는 결국 a+와 동일한 언어를 매칭하므로 바깥쪽 그룹과 정량자를 걷어내면 그만입니다. (a|aa)+처럼 선택지 사이에 겹치는 부분이 있는 경우도 마찬가지로 의심해야 합니다. 두 번째로, 정규식에 ^, $ 같은 앵커를 적절히 걸어 애초에 백트래킹이 넓게 퍼질 여지를 줄이고, 가능하면 .처럼 범위가 넓은 문자 클래스보다 [0-9]처럼 구체적인 클래스를 씁니다. 세 번째로, JavaScript의 네이티브 RegExp는 원자 그룹(atomic group)이나 possessive quantifier 같은 백트래킹 억제 문법을 지원하지 않기 때문에, 사용자 입력으로 정규식 자체가 결정되는 상황(검색 필터, 커스텀 검증 규칙 등)이라면 실행 시간에 상한을 두는 것이 근본 대책입니다. Node.js 서버라면 정규식 실행을 워커 스레드로 분리해 타임아웃으로 강제 종료하거나, 선형 시간을 보장하는 RE2 계열 엔진으로 대체하는 방법이 실무에서 널리 쓰입니다. 결국 이 문제는 정규식 문법의 사소한 실수가 아니라 백트래킹 기반 NFA 엔진의 알고리즘적 한계에서 비롯되므로, "패턴을 조심해서 짠다"와 "위험한 패턴이 들어와도 죽지 않게 방어한다"를 함께 갖춰야 합니다.
4. 정리 — 정규식 작성 시 체크할 순서
- 정량자 중첩 확인:
(x+)+,(x*)*,(x|xx)+형태가 패턴 안에 있는지 먼저 찾아봅니다. - 겹치는 선택지 제거: 그룹 내부의 선택지들이 같은 문자열을 매칭할 수 있는지 검토해 상호 배타적으로 다듬습니다.
- 신뢰할 수 없는 입력 방어: 사용자 입력을 정규식에 직접 넣거나 사용자가 정규식 자체를 입력하게 한다면 실행 시간 제한을 반드시 둡니다.
자주 묻는 질문
Q. 그리디와 레이지 매칭의 차이는 정확히 무엇인가요?
A. +, *, {n,} 같은 정량자는 기본적으로 그리디(탐욕적)하게 동작해서 매칭 가능한 최대 길이까지 문자를 먼저 삼킨 뒤, 뒤쪽 패턴이 실패하면 한 글자씩 되돌려주며(백트래킹) 전체가 맞아떨어지는 지점을 찾습니다. 반대로 +?, *?처럼 물음표를 붙이면 레이지(게으른)하게 동작해서 최소 길이부터 시도하고, 뒤쪽 패턴이 실패할 때마다 한 글자씩 더 삼키며 확장합니다.
Q. 왜 (a+)+ 같은 패턴이 위험한가요?
A. 바깥쪽 +와 안쪽 +가 같은 문자들을 여러 가지 방식으로 나눠 담을 수 있기 때문입니다. 예를 들어 a를 6개 그룹으로 나눠 담는 방법과 3개 그룹으로 나눠 담는 방법 모두 똑같이 aaaaaa 전체를 매칭하므로, 문자 수가 늘어날수록 그 조합의 수가 2의 n제곱에 가깝게 폭증합니다. 매칭에 최종적으로 실패하는 입력이 들어오면 엔진이 이 모든 조합을 백트래킹으로 다 시도해야 해서 사실상 멈춘 것처럼 보입니다.
Q. ReDoS는 실제로 서비스에 어떤 피해를 주나요?
A. 사용자 입력값(이메일, 비밀번호, URL 등)을 검증하는 서버 코드에 취약한 정규식이 있으면, 공격자가 매칭에 실패하도록 설계된 긴 문자열 하나만 보내도 해당 요청을 처리하는 스레드나 프로세스가 CPU를 100% 점유한 채 멈춥니다. 요청 몇 개만 동시에 보내도 서버 전체가 다른 사용자의 요청을 처리하지 못하는 서비스 거부(DoS) 상태에 빠질 수 있습니다.
Q. 이 사이트의 정규식 테스터로 위험한 패턴을 테스트해도 안전한가요?
A. regex-tester.html은 입력한 패턴을 브라우저의 JavaScript 엔진에서 그대로 실행하며 별도의 실행 시간 제한 로직은 두지 않았습니다. 재앙적 백트래킹을 일으키는 패턴과 긴 입력을 동시에 넣으면 해당 탭이 응답 없음 상태가 될 수 있으니, 위험 패턴을 실습할 때는 문자열 길이를 짧게(10~20자 수준) 시작해서 점점 늘려가며 체감하는 것을 권장합니다.
Q. 중첩 정량자를 안전하게 쓰려면 어떻게 고쳐야 하나요?
A. 같은 문자 집합을 두 겹의 정량자로 감싸지 않는 것이 핵심입니다. (a+)+ 대신 a+, (a|aa)+ 대신 a+ 처럼 바깥쪽 정량자를 걷어내고 안쪽 정량자 하나로 통합할 수 있는지 먼저 검토하세요. 구조상 그룹이 꼭 필요하다면 그룹 내부 선택지들이 서로 겹치는 문자열을 매칭하지 않도록 상호 배타적으로 설계하고, 그래도 불안하면 정규식 엔진 자체에 실행 시간 제한을 거는 라이브러리(re2, safe-regex 등)를 쓰는 것이 안전합니다.