정규식 엔진의 백트래킹이 지수적으로 폭발해 CPU를 태우는 문제.
-
(a+)+$ — 에 "aaaaaaaaaaaaaaaaaaaaaaaaX" 를 넣으면
- a 들을 그룹으로 나누는 경우의 수를 전부 시도한다
- 입력 길이 n 에 대해 2^n 에 가까운 경로
- 25자에서 이미 수 초, 30자면 수 분
무엇이 위험한 패턴인가
중첩 수량자 (a+)+ (a*)* (a|aa)+
인접한 겹치는 대안 (\\d|\\w)+ ← \\d 가 \\w 에 포함된다
선택적 반복 + 앵커 ^(\\s*|\\t)*$
- 공통점: 같은 문자열을 여러 방식으로 매칭할 수 있다
- 실패했을 때 되돌아가 시도할 경로가 폭발한다
Cloudflare 2019년 7월 2일
WAF 규칙에 추가된 정규식 하나
- .(?:.=.*)
이 패턴이 전 세계 엣지 서버의 CPU 를 100% 로 만들었다 27분간 글로벌 트래픽이 502 를 반환했다
- 원인은 '악의적 입력' 이 아니라 평범한 트래픽이었다
- ReDoS 는 공격이 없어도 사고가 된다
방어
- ① 소유 수량자·원자 그룹으로 백트래킹을 끊는다
- (a++)+ (?>a+)+ ← 자바 정규식이 지원한다
- ② 사용자 입력을 정규식으로 받지 않는다
- ③ 입력 길이 상한을 둔다 (지수 폭발은 길이에 민감하다)
- ④ 정규식 대신 파서를 쓴다 (이메일 검증은 특히 정규식이 나쁜 선택)
- ⑤ 별도 스레드에서 타임아웃을 건다 — 자바 표준 API 에는 타임아웃이 없다
왜 언어마다 다른가
-
백트래킹 엔진 — 자바 · 파이썬 · 자바스크립트 · PCRE — 역참조 등 기능이 풍부, 폭발 가능
-
DFA/NFA 엔진 — RE2(Go 기본 · Rust regex) — 선형 시간 보장, 대신 역참조 미지원
-
외부 입력을 정규식으로 다뤄야 한다면 RE2 계열을 고르는 것이 근본 대응이다
왜 백트래킹이 필요한가
정규식을 유한 오토마타로만 처리하면 선형 시간에 끝난다 그런데 역참조 · 전방탐색 같은 기능은 오토마타로 표현할 수 없다
- 이런 기능을 지원하려고 백트래킹 엔진을 쓴다
- 대가로 최악의 경우가 지수가 된다
즉 '기능' 과 '시간 보장' 을 맞바꾼 결과이지 버그가 아니다
자바에서 타임아웃을 거는 실전 방법
// CharSequence 를 감싸 일정 횟수마다 인터럽트를 확인하게 만든다
final class Interruptible implements CharSequence {
private final CharSequence s;
Interruptible(CharSequence s) { this.s = s; }
public char charAt(int i) {
if (Thread.currentThread().isInterrupted())
throw new RuntimeException("regex timeout");
return s.charAt(i);
}
public int length() { return s.length(); }
public CharSequence subSequence(int a, int b) {
return new Interruptible(s.subSequence(a, b));
}
public String toString() { return s.toString(); }
}
matcher = pattern.matcher(new Interruptible(input));
백트래킹 중에도 charAt이 계속 불리므로 여기서 빠져나올 수 있다.
면접 함정
- ❌ "정규식은 빠르다" → 패턴에 따라 지수 시간이 된다.
- ❌ "입력 검증이 있으니 안전" → 검증하는 정규식 자체가 ReDoS인 경우가 흔하다.