다음 regex 가 무서운 이유:
pattern: /^(a+)+$/
input: "aaaaaaaaaaaaaaaaaaaaaaaaa!" (a 25개 + !)
JavaScript / Python / Java — 매치 시도 시간:
20자: 1 초
25자: 30 초
30자: 30 분
35자: 18 시간 (!)평범한 regex 가 사용자 입력 길이에 지수 시간. 서비스 다운 가능 — ReDoS (Regular Expression Denial of Service) 공격. 이 가이드는 backtracking 의 메카니즘, catastrophic 패턴, 그리고 RE2 같은 linear-time engine 의 대안을 정리한다.
왜 regex 가 느려질 수 있나 — backtracking
대부분의 언어 (JavaScript, Python, Perl, Java, .NET, Ruby) 는 backtracking NFA 방식. 단순 한 줄로 풀면:
- 여러 매치 경로가 있으면 모두 시도
- 하나 실패하면 backtrack (되감기) 후 다른 경로
- 모두 실패할 때까지 시도 → 매치 실패 보고
pattern: /a+a+/
input: "aaaab"
엔진의 시도:
1. a+ greedy match "aaaa" → 다음 a+ 찾을 a 없음 → backtrack
2. a+ match "aaa" → 다음 a+ match "a" → 다음 b 매치 X → backtrack
3. a+ match "aa" → 다음 a+ match "a" or "aa" → 다음 b X → backtrack
... 계속간단해 보이지만 nested 시 폭주.
Catastrophic backtracking — (a+)+ 의 비밀
pattern: /^(a+)+$/
input: "aaaa!"
(a+)+ 가 의미:
바깥 + : group 한 번 이상
안쪽 a+: a 한 번 이상
이게 ambiguous — "aaaa" 를 어떻게 group 으로 쪼개나?
[aaaa] 1 group
[aaa][a] 2 groups
[aa][aa] 2 groups
[aa][a][a] 3 groups
[a][aaa] 2 groups
[a][aa][a] 3 groups
[a][a][aa] 3 groups
[a][a][a][a] 4 groups
n 글자 a 에서 그룹화 방법 = 2^(n-1) 가지
! 만나면 매치 실패 → backtrack → 모든 경우 시도 → 지수 시간이게 "catastrophic backtracking". 평범한 정규식이 입력 길이에 지수 시간.
ReDoS — 실제 사고 사례
Cloudflare 2019 사고
WAF (Web Application Firewall) 규칙에 박힌 정규식이 ReDoS 패턴. attacker 가 특정 input 보내면 WAF process CPU 100% → Cloudflare edge server 다수 다운. 27 분 outage. 전 세계 영향.
Stack Exchange 2016 사고
모더레이션 정규식에 ReDoS. 한 사용자의 post 가 site 전체 down.
문제 패턴 — 사용자 input 을 받는 server-side regex 가 catastrophic. attacker 가 의도적으로 polynomial / exponential input 박음.
위험 패턴 — 어떤 게 catastrophic 인가
1. Nested quantifier — (a+)+ 류
(a+)+
(a*)*
(a|aa)+ ← alternation + repeat
(a|a)* ← 같은 alt2. Overlapping alternation — (a|ab)+
(a|ab)+ ← "ab" 가 "a" 와 "b" 두 가지 매치 경로
→ backtrack 폭주3. Overlapping repeat — a+a+
a+a+ ← 첫 a+ 어디까지? 매번 다른 splitting
→ ambiguity → backtrack4. Greedy + lazy 조합 함정
<.+>.*</.+> ← unbalanced 처리에서 폭주
<.+?> ← lazy 가 보통 안전 (greedy 보다)안전한 패턴 — atomic group · possessive
Atomic group (?>...)
# 일반 group + 백트랙 가능
(a+)+ ← catastrophic
# atomic group — 한 번 결정 후 backtrack X
(?>a+)+ ← 안전. group 안의 매치 결정 후 unchangedAtomic group 은 한 번 매치 후 절대 되돌리지 않음. JavaScript 2025+ 지원, Perl/.NET 옛부터, Python 3.11+ 지원.
Possessive quantifier (a++, a*+)
a++ ← greedy + 백트랙 X
a*+
# 일반 vs possessive
a+a ← "aa" 매치 가능 (a+ 가 backtrack 해서 마지막 a 양보)
a++a ← 매치 실패 (a++ 가 모든 a 먹은 후 backtrack X)Java / PCRE / Perl 지원. JavaScript 미지원 (2024 기준).
입력 길이 제한
// 가장 단순한 방어
if (userInput.length > 1000) throw new Error("too long");
const match = pattern.exec(userInput);
// 또는 timeout (Node.js 의 일부 lib 가 지원)
const match = await pattern.execWithTimeout(userInput, 100);Linear engine — RE2 의 대안
Google 의 RE2 (Ken Thompson + Rob Pike) 는 backtracking X. DFA / NFA simulation 으로 입력 길이에 linear 시간 보장. ReDoS 불가능.
Trade-off:
- backreference (
\1) 미지원 - lookbehind 제한
- POSIX 기본 기능만
사용 환경:
- Go 의
regexp표준 라이브러리 — RE2 기반 - Rust 의
regexcrate — RE2 영감 + 일부 확장 - Python 의
re2binding (별도 설치) - JavaScript X (V8 의 V8 IRRegexp 가 backtracking)
실제 검증 — regex-tester 의 함정
브라우저 regex-tester 에서 catastrophic 패턴 + 긴 input 입력 시 탭 freeze. 정규식 테스터 는 useDebouncedValue + main thread 동기 실행 — 매우 큰 입력은 위험. 실무 — server-side regex 는 timeout 필수.
ReDoS 검출 — 도구
- safe-regex (Node) — npm package. catastrophic 패턴 정적 분석
- recheck — Java/JavaScript regex ReDoS 검증
- regexploit — Python 의 regex 패턴 fuzzing
CI 에 통합 권장 — 의존성 + 자체 코드의 regex 검사.
예시 — 안전 vs 위험
# 이메일 — 흔한 ReDoS
^([a-zA-Z0-9]+)*@ ← 위험 ((..+)* 패턴)
^[a-zA-Z0-9]+@ ← 안전
# URL path
^(/[a-z]+)+$ ← 위험 (nested +)
^/(?:[a-z]+/)*[a-z]+$ ← 안전 (non-capturing + atomic-ish)
# JSON 안 따옴표 escape
"(.*?)" ← 보통 안전 (lazy)
"(\\.|[^"])*" ← 잠재 위험 (alternation in *)
# date
^(\d+)+-(\d+)+$ ← 위험 (nested +)
^\d+-\d+$ ← 안전방어 전략 요약
- nested quantifier 피하기 — (a+)+ 류 패턴 X. 작성 시 의도적으로 점검.
- 입력 길이 제한 — 사용자 input 에 regex 적용 전
length검증 - timeout — Node.js 의 일부 라이브러리, server framework 의 timeout middleware
- linear engine — Go / Rust / RE2. JavaScript 은 어려움 (V8 한정)
- CI 정적 분석 — safe-regex / recheck
- 최후 수단 — regex 대신 string method (
indexOf,split)
흔한 함정
1. server-side validation 의 regex
password / username / email 등 사용자 input. 가장 흔한 ReDoS 표면. OWASP regex 모음 참조.
2. log parsing 의 정규식
nginx / Apache log 파싱 — 각 줄에 regex apply. 1 MB log 의 한 줄이 catastrophic 패턴이면 분석 도구 freeze.
3. content security policy 정규식
WAF / IDS 규칙 정규식. attacker 가 의도적 input → security 시스템 자체 down (Cloudflare 사례).
4. markdown / wiki parser
markdown 의 nested syntax 가 정규식으로 처리 시 catastrophic 가능성. Discord / Slack 의 markdown lib 가 가끔 ReDoS fix.
5. JavaScript V8 의 timeout 부재
V8 은 regex timeout API 없음. catastrophic 매치는 main thread block. setTimeout 으로 우회 어려움 — regex 자체가 sync.
Worker thread 에서 regex 실행 → main thread 보호. 또는 server-side 에 regex 위임 (Node + RE2 npm).
참고 자료
- OWASP — Regular Expression Denial of Service — OWASP
- Cloudflare July 2019 outage — postmortem
- Ken Thompson — Regular Expression Search Algorithm (1968) — swtch.com (Russ Cox)
- RE2 syntax — GitHub
요약
- 대부분 언어의 regex = backtracking NFA. 일부 패턴이 입력 길이에 지수 시간.
- catastrophic backtracking — (a+)+ 류 nested quantifier 가 주범. 매치 실패 시 모든 split 경우 시도.
- ReDoS = 의도적 catastrophic input 으로 서비스 down. Cloudflare 2019 사고.
- 위험 패턴 5 가지 — nested quantifier / overlapping alternation / overlapping repeat / greedy 조합 / unbounded repeat.
- 방어 — atomic group / possessive quantifier / 입력 길이 제한 / timeout / RE2.
- RE2 (Go / Rust) 는 linear time 보장. backreference 등 일부 기능 X.
- JavaScript 는 timeout X — Worker thread 또는 server-side 우회.
- 실험 — 정규식 테스터 에서 catastrophic 패턴 + 긴 input 으로 tab freeze 체험 (조심!).