ReDoS — 정규식 DoS 공격 · RegEx Quest

ReDoS는 느린 실패 경로를 서비스 거부로 바꿔

ReDoS는 파국적 백트래킹이 가능한 패턴에 공격자가 오래 걸리는 입력을 반복해서 넣는 공격이야. 요청 하나가 CPU를 오랫동안 붙잡으면 적은 입력으로도 처리량이 떨어지고 시간 제한이나 자원 고갈까지 이어질 수 있어.

2019년 Cloudflare 장애가 규모를 보여 줬어

2019년 7월에는 과도한 백트래킹을 일으키는 WAF 정규식 하나가 전역에 배포된 뒤 정상 HTTP 트래픽에서도 CPU를 포화시켰고, 장애가 약 27분 이어졌어. 의도적인 공격은 아니었지만 취약한 패턴 하나가 서비스 전체에 영향을 줄 수 있다는 사실을 선명하게 보여 줬지.

외부 입력을 받는 복잡한 패턴을 먼저 의심해

이메일 검증기 안의 (.+)+ 같은 중첩 수량자
종료 표식이 없는 긴 입력에서 반복 탐색을 하는 URL 패턴
<(.+)>.*</\1>처럼 탐욕적 수량자와 역참조를 결합한 HTML/XML 추출
다른 수량자 안에 잘못 중첩된 \*\*(.+?)\*\* 같은 Markdown 재작성

표면의 문법보다 중요한 건 실패 입력에서 같은 구간을 몇 가지 방식으로 다시 나누는지야.

패턴, 입력, 실행 환경 세 층에서 막아

패턴을 통제해. 사용자가 정규식을 직접 제출하게 해야 한다면 허용 문법을 제한하거나 RE2 계열 엔진을 사용해.
모호한 구조를 줄여. 의미를 확인한 원자 그룹·소유적 수량자와 경계를 직접 나타내는 문자 클래스로 불필요한 분할을 없애.
실행 시간을 제한해. .NET Regex나 Python regex처럼 시간 제한을 제공하는 구현에서는 이를 설정해. Python 내장 re나 JavaScript RegExp처럼 기본 제한이 없다면 작업을 격리하거나 프로세스 수준 제한을 둬.
실패 입력을 시험해. 정상 예시만 보지 말고 종료 표식이 빠진 긴 문자열과 반복 경계가 겹치는 입력을 성능 테스트에 넣어.

자동 탐지는 보조 안전망으로 써

safe-regex, 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   — 폭발적 백트래킹 없음

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

ReDoS — 정규식 DoS 공격

ReDoS는 느린 실패 경로를 서비스 거부로 바꿔

2019년 Cloudflare 장애가 규모를 보여 줬어

외부 입력을 받는 복잡한 패턴을 먼저 의심해

패턴, 입력, 실행 환경 세 층에서 막아

자동 탐지는 보조 안전망으로 써

Code

External links

Exercise

Progress

댓글 0