Catastrophic Backtracking

지수 함정

일부 innocent 보이는 정규식 패턴이 특정 입력에 지수적으로 느려짐. 패턴 (a+)+b 가 'aaaab' 즉시 매칭. 끝에 'b' 없는 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaa' 에 돌리면 CPU 가 분 단위로 회전 또는 영원 hang.

왜 발생

엔진이 a+ iteration 사이 입력 split 가능한 모든 방법 시도. a 30개면 2^30 (~10억) split. 각 split 이 'b' 없으니 실패. 엔진이 포기 전에 다 시도.

위험 패턴

안과 밖이 둘 다 같은 글자 매칭 가능한 중첩 quantifier 찾기:

(a+)+ — 안과 밖이 둘 다 a 매칭
(a*)* — 동일
(a|a)+ — 대안이 같은 거 매칭
(a|b)*c — 입력에 c 없으면 모든 글자가 a 또는 b 로 시도 가능
(\w+\s)+ — 입력이 공백 없이 끝나면

Quantifier 가진 조각이 여러 방법으로 split 가능 AND 패턴 나머지 실패 자리 어디든 잠재 폭발.

수정

Atomic 그룹 / possessive quantifier — backtracking 비활성화. (?>a+)+b 또는 a++b.
Negated character class — [^X]+ 가 X 찾으려 backtrack X. .*? 대신 [^"]*.
Anchor — ^pattern$ 가 적어도 엔진을 한 위치로 제한.
적대적 입력엔 RE2/Go — RE2 가 backtrack X; ReDoS 불가능.

Code

Catastrophic 패턴·python

import re
import time

# 긴 입력에 실제로 돌리지 마 — hang 함
# (a+)+b   가 'aaaab' 즉시 매칭
# (a+)+b   가 'a' * 30 + 'X' 에서 분 단위
# (a*)*    같은 폭발
# (a|a)+   동일

# Backtracking 이 성능 치는 빠른 demo
def time_match(pattern, text, label):
    start = time.time()
    re.search(pattern, text)
    print(f'{label}: {time.time() - start:.3f}s')

# 안전한 크기로 시연
text = 'a' * 25 + 'X'  # 끝에 'b' 없음
time_match(r'a+b', text, 'simple')
# time_match(r'(a+)+b', text, 'catastrophic')  # 초 단위

# Atomic 그룹 수정 (Python 3.11+)
import sys
if sys.version_info >= (3, 11):
    time_match(r'(?>a+)+b', text, 'atomic')  # 즉시

# Negated class 수정 — 어디서나 동작
text = 'a' * 100 + 'X'
time_match(r'a*X', text, 'simple a*X')        # 빠름
# time_match(r'(a*)*X', text, 'nested')        # 폭발

Catastrophic Backtracking

지수 함정

왜 발생

위험 패턴

수정

Code

External links

Exercise

Progress

댓글 0