ReDoS — Regex DoS 공격

공격 벡터

ReDoS (Regular Expression Denial of Service) 가 catastrophic backtracking 의 실전 익스플로잇. 공격자가 취약한 정규식에 입력 공급 가능하면 서버가 분 단위로 CPU 코어 회전 — 또는 본인 프로세스가 out-of-memory 또는 timeout 신호로 죽을 때까지.

실전 예시: Cloudflare 2019

2019년 7월, 중첩 quantifier 가진 단일 정규식이 글로벌 Cloudflare 장애 유발. 패턴이 HTTP 요청 본문에 대해 방화벽 룰 체크. 적대적 본문이 지수 backtracking trigger; CPU saturation 이 네트워크 통해 전파. 장애 ~30분 지속, 수백만 영향.

실전의 흔한 취약 패턴

중첩 quantifier 있는 이메일 검증기 — 많은 옛 이메일 정규식이 (.+)+ 모양.
Greedy lookahead 있는 URL 파서 — .*?(?=&) 가 & 없는 긴 입력에 나쁘게 backtrack 가능.
HTML/XML 추출 — backreference 와 greedy 있는 <(.+)>.*</\1>.
Markdown 재작성 — **(.+?)** 체인이 패턴 이상하게 중첩하면 폭발 가능.

방어

신뢰 안 되는 패턴 돌리지 마. 사용자가 정규식 작성 가능 (검색 필터 등) 면 RE2 사용 또는 엄격 timeout 부과.
Fragile 패턴에 신뢰 안 되는 입력 주지 마. Atomic 그룹, possessive quantifier, negated class 사용.
Timeout 설정. 대부분 언어가 정규식 실행 시간 cap 가능. Python re 가 native 로는 X, but regex 모듈은 함.
사용자 공급 입력엔 RE2 사용 — Go 의 regexp, Python 의 google-re2 바인딩. Linear time 보장.

감지 도구

코드베이스에서 취약 패턴 스캔하는 도구 존재: safe-regex (npm), recheck, GitHub 의 CodeQL 쿼리. 주기적 실행.

Code

ReDoS-safe 대안·python

# 취약: alternation 의 greedy quantifier
# (a|aa|aaa)+b   — 'a'*30+'X' 에 폭발

# 안전한 다시 작성: 대안 deduplicate, atomic 그룹
# (?>a+)b   — 빠르게 실패

# 취약: overlapping quantifier 있는 중첩 그룹
# (.+)+@   — 이메일-like, @ 없는 긴 입력에 폭발

# 안전: anchor + negated class
# ^[^@]+@   — linear time, 이메일에 같은 매칭 파워

# 취약: 경계 없는 lazy quantifier
# .+?(?=END)   — END 절대 안 나오면 폭발

# 안전: negated class
# [^E]*END   — 폭발 X

# 신뢰 안 되는 입력엔 Google RE2 바인딩 사용
# pip install google-re2
# import re2
# re2.compile(r'pattern').search(input)  # linear 보장

ReDoS — Regex DoS 공격

공격 벡터

실전 예시: Cloudflare 2019

실전의 흔한 취약 패턴

방어

감지 도구

Code

External links

Exercise

Progress

댓글 0