파국적 백트래킹

정상 입력에서는 빠른 패턴도 실패 입력에서 폭발할 수 있어

(a+)+b는 끝에 b가 있는 aaaab를 금방 매칭해. 하지만 a만 길게 이어지고 b가 없는 입력에서는 같은 문자들을 묶는 방법을 거듭 다시 시도하며 급격히 느려질 수 있어.

겹친 반복이 같은 입력을 여러 방식으로 나눠

안쪽 a+가 몇 글자를 맡고 바깥 +가 몇 번 반복할지 정하는 경계가 겹쳐 있어. a가 30개라면 29개 경계마다 나눌지 말지를 고르는 조합이 생기고, 마지막 b가 없을 때 엔진은 많은 분할을 실패로 확인하게 돼.

모호한 반복이 겹치는 모양을 찾아

(a+)+와 (a*)*는 같은 문자를 안팎에서 반복하고
(a|a)+는 두 대안이 같은 입력을 받아들이고
(a|aa)+b는 연속된 a를 한 글자와 두 글자로 여러 방식으로 나눌 수 있고
(\w+\s?)+X는 선택적인 공백 때문에 반복 경계가 겹칠 수 있어.

이런 모양에서 뒤쪽 필수 요소가 끝내 실패하면 백트래킹 경로가 폭발할 위험이 커져.

수정은 선택지를 줄이는 방향으로 해

원자 그룹이나 소유적 수량자: 의미가 유지된다고 증명한 구간의 백트래킹을 막아.
부정형 문자 클래스: 종료 표식이 한 글자라면 .*? 대신 [^"]*처럼 경계를 직접 표현해. 뒤 패턴이 실패하면 여전히 문자를 돌려줄 수 있으니 전체 구조를 확인해야 해.
앵커: 시작 위치가 정해져 있다면 ^pattern$으로 엔진이 시도할 출발점을 줄여.
비백트래킹 엔진: 신뢰할 수 없는 입력에는 RE2나 Go regexp처럼 파국적 백트래킹이 없는 엔진을 고려해.

Code

파국적 백트래킹 패턴·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')        # 폭발

Exercise

사용자 입력에 적용되는 정규식 하나를 골라 중첩 수량자, 겹치는 대안, 그룹 안의 탐욕적 .*가 있는지 확인해. 위험한 구조가 있다면 의미를 보존하는 부정형 문자 클래스나 원자 그룹으로 고치고, 고칠 수 없다면 입력 한도와 위험을 문서화해.