정규식 엔진 내부 완전 가이드 2025: NFA, DFA, Thompson, Backtracking Catastrophe — 같은 regex가 1000배 차이나는 이유

A.

근본 원인: 완전히 다른 알고리즘.

두 언어는 정규식 매칭에 다른 접근을 사용한다:

Python (re 모듈): Backtracking 기반.

• NFA의 여러 경로를 순차적으로 시도.
• 실패하면 되돌아가서 다른 경로.
• 최악 시간: 지수적.

Go (regexp 패키지): Thompson NFA 기반 (RE2).

• 모든 가능한 상태를 동시에 유지.
• 실패가 이전 성공을 무효화하지 않음.
• 최악 시간: 다항적 (O(|regex| × |input|)).

극단적 예시:

import re
re.match(r'(a+)+b', 'a' * 30 + 'X')

regexp.MustCompile(`(a+)+b`).MatchString("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaX")

Python의 실행:

• (a+)+b는 이중 중첩 양자화.
• 30개의 a를 그룹으로 나누는 방법이 2^29 가지.
• 각 조합을 시도 → 실패 → 다음 시도.
• 2^29 = 약 5억 번의 매칭 시도.
• 수 분~수 시간 소요.

Go의 실행:

• NFA로 변환.
• 상태 집합을 30개 문자 동안 갱신.
• 각 문자마다 상수 상태 (NFA 크기 기반).
• 약 30 × 상수 = μs 단위.

시간 차이:

• Python: 300,000,000,000 cycles (30초).
• Go: 3,000 cycles (1μs).
• 100,000,000배 차이.

왜 Python은 이런 비효율을?

역사적 이유:

1. Perl의 영향: 1987년 Perl이 정규식을 대중화. Backtracking을 선택했다 (당시 구현이 더 쉬웠음).

2. 기능 요구: Backreferences, lookaround 등은 Thompson NFA로 불가능. 이 기능을 원하면 backtracking 필수.

3. 표준화: PCRE (Perl Compatible)가 사실상 표준이 됨. Python, Ruby, JavaScript 등이 따라감.

4. 관성: 한번 선택하면 바꾸기 어려움.

Go의 다른 선택:

Russ Cox는 Thompson의 제자이며, Google에서 일하면서 대규모 시스템의 regex 성능을 중시했다. 다음을 받아들였다:

• Backreferences 포기: 안전을 위한 대가.
• 완전한 정규 언어만: 수학적 엄격함.
• 예측 가능 성능: 모든 regex가 다항적.

실전 교훈:

1. 사용자 입력에 regex를 쓴다면: Python은 위험. 악의적 입력에 DoS 가능.

2. 동일 언어 내:

   • Python: 간단한 regex만, 의심스러우면 re2 라이브러리.
   • JavaScript: V8의 non-backtracking engine 활용.
   • Go, Rust: 안심하고 사용.

3. Regex 디자인:

   • 중첩 양자화 피하기.
   • 명확한 경계.
   • 측정 필수.

4. 대안 고려:

   • 때로는 문자열 메서드가 더 빠르고 안전.
   • Parser (PEG, hand-written) 고려.

Cloudflare 교훈:

2019년 Cloudflare 장애는 이 차이의 극단적 예시다. PCRE 기반 regex 하나가 30분 동안 전 세계 트래픽을 막았다. 해결책? RE2로 전환. 같은 regex, 같은 입력, 지수적 → 다항적 변화.

결론:

"같은 정규식"이라는 말은 문법만 같을 뿐이다. 엔진에 따라 완전히 다른 알고리즘이 실행된다. 이는 어떤 프로그래밍 언어를 쓰느냐보다 더 근본적인 차이일 수 있다.

프로덕션 시스템에서 정규식을 쓰기 전에:

1. 엔진 확인: Backtracking? Thompson? DFA?
2. 복잡도 확인: 중첩 양자화, 교집합 분기.
3. 입력 검증: 사용자 입력인가?
4. 벤치마크: 큰 입력으로 테스트.
5. 타임아웃: 안전장치.

이 작은 주의가 30분 다운타임 vs 정상 운영의 차이를 만든다.

A.

두 알고리즘의 목적:

Thompson's construction (1968): Regex → NFA. Subset construction (1959): NFA → DFA.

둘은 파이프라인의 다른 단계다:

Regex → (Thompson) → NFA → (Subset) → DFA

Thompson's Construction:

목적: 정규식을 NFA로 변환.

방법: 재귀적 합성. 각 regex 연산자에 대응하는 작은 NFA 조각을 정의하고, 이를 결합.

기본 규칙:

문자 a:
  [1] --a--> [2]

연결 ab:
  [A_start] --a--> [A_end] --ε--> [B_start] --b--> [B_end]

선택 a|b:
  [new]--ε--> [A] --a--> [Ae]--ε-->[end]
       \ε-->[B]--b-->[Be]--ε-->/

Kleene star a*:
  [new]--ε-->[A]--a-->[Ae]--ε-->[end]
       ^         |
       |ε        |ε
       +--[middle]<

크기 특성:

• NFA 크기 = O(|regex|).
• 각 연산자마다 상수 개 상태 추가.
• 예: 100자 regex → 200-500개 상태.

장점:

• 선형 크기: 메모리 효율.
• 단순함: 구현 쉬움.
• 모든 regex에 적용 가능.

단점:

• NFA 실행이 복잡 (여러 상태 동시 관리).
• DFA보다 느림 (관리 오버헤드).

Subset Construction:

목적: NFA를 DFA로 변환.

아이디어: DFA의 각 상태는 NFA의 상태 집합에 대응.

핵심 관찰: NFA를 실행할 때, 항상 "현재 가능한 상태 집합"이 있다. 이 집합을 하나의 DFA 상태로 보자.

알고리즘:

1. DFA 시작 상태 = NFA 시작 상태의 ε-closure.
2. Worklist에 넣기.
3. Worklist에서 하나 꺼내기:
   a. 각 입력 문자 c에 대해:
      - 이 집합의 모든 상태에서 c로 전이한 새 집합 계산.
      - 새 집합의 ε-closure.
      - 아직 DFA에 없으면 추가하고 worklist에 넣기.
      - DFA 전이 추가.
4. Worklist 빌 때까지 반복.

예시:

NFA:

[1] --a--> [2] --b--> [3]
    --a--> [4] --b--> [3]

두 개의 a-전이. NFA 비결정론.

DFA:

{1} --a--> {2, 4} --b--> {3}

DFA에선 4가 하나의 상태. 결정론적.

Subset Construction의 함정:

Exponential Blowup: NFA n개 상태 → DFA 최대 2^n 개 상태.

최악 예시:

Regex (a|b)*a(a|b)^n (n개 반복):

• NFA: n+2 상태.
• DFA: 2^(n+1) 상태.
• n=30 → 20억 상태. 메모리 불가.

왜?

이 regex는 "끝에서 n번째가 a"를 체크. DFA는 최근 n+1개 문자를 모두 기억해야 한다. 2^(n+1) 가능한 조합 모두 상태 필요.

NFA는 이를 "동시 상태"로 표현 가능. DFA는 각 조합을 별도 상태로.

RE2의 해결: Lazy DFA:

아이디어: DFA를 미리 만들지 말고, 필요한 상태만 점진적으로 생성.

동작:

1. NFA로 시작.
2. 실행 중 방문하는 상태 집합을 DFA 상태로 캐싱.
3. 같은 집합이 다시 나오면 재사용.
4. 메모리 한계 도달 → 오래된 엔트리 제거, NFA로 폴백.

이점:

• 실전 regex는 DFA가 작음 → 빠름.
• Pathological regex는 NFA로 폴백 → 여전히 선형 시간.
• 최악에도 안전.

Thompson + Subset의 역할 분담:

Regex → NFA (Thompson, O(|regex|))
    → DFA (Subset, O(2^|NFA|) 최악)
       → 실행 O(|input|) 각 문자 상수 시간

vs

Regex → NFA (Thompson)
    → 직접 NFA 실행 O(|input| × |NFA|)

Trade-off:

• DFA 사전 구축: 컴파일 느림 (때론 불가), 실행 빠름.
• NFA 실행: 컴파일 빠름, 실행 약간 느림.

어느 것을 선택?

대부분의 DFA 엔진: Lazy DFA (RE2, Go).

• 실행 시 점진적 DFA 생성.
• 대부분 regex에서 DFA 속도.
• Pathological에서 NFA 폴백.

순수 NFA 엔진: 드물음.

Backtracking 엔진: NFA도 DFA도 아님. 완전히 다른 접근.

역사적 맥락:

1959: Rabin과 Scott이 subset construction 발표. 이론적 결과 (NFA와 DFA의 등가성 증명).

1968: Ken Thompson이 Thompson construction과 NFA 직접 실행 알고리즘 발표. 실용적 구현. grep의 원조.

2007: Russ Cox가 RE2 발표. Thompson의 아이디어를 현대적으로 재구현. Lazy DFA로 최선의 절충.

이것이 50년간의 발전:

• 이론 (Rabin-Scott).
• 실용 (Thompson).
• 최적화 (Russ Cox, RE2).

각 세대가 전 세대의 작업 위에 쌓았다.

교훈:

Thompson construction과 subset construction은 서로를 보완한다:

• Thompson: 간단한 NFA 구성.
• Subset: NFA를 DFA로 변환 (옵션).

현대 엔진(RE2, Go)은 둘 다 활용한다. Thompson으로 NFA를 만들고, 가능하면 lazy하게 DFA로 변환한다. 이것이 예측 가능 성능과 작은 메모리를 동시에 달성하는 방법이다.

이는 이론과 실전의 아름다운 결합이다. 1959년의 수학 결과가 2025년 Google의 서버에서 매 초마다 실행되고 있다. 좋은 이론은 영원하다.

A.

수학적 근원: Ambiguous Matching

Catastrophic backtracking은 같은 문자열이 여러 방식으로 매치되는 regex에서 발생한다. Backtracking 엔진은 이 모든 방식을 시도해야 한다.

전형적 패턴:

1. 중첩 양자화:

(a+)+

a+는 "하나 이상의 a". (a+)+는 "하나 이상의 (하나 이상의 a)".

문자열 "aaaa"에 대해:

• (a)(a)(a)(a): 각각 하나씩.
• (aa)(aa): 2개씩.
• (aaaa): 전체.
• (a)(aaa): 1+3.
• (aaa)(a): 3+1.
• (aa)(a)(a): ...
• ...

n개 a에 대해 2^(n-1) 가지 그룹화 가능. 모두 같은 결과 "aaaa"지만 regex 엔진은 구분 못 함.

2. 교집합 분기:

(a|aa)+

"aaa":

• (a)(a)(a): 각각.
• (aa)(a): 2+1.
• (a)(aa): 1+2.

3. 중복 표현:

(a|ab|abc)+

"abcabc":

• (abc)(abc).
• (ab)(c...) - 불가능하지만 시도.
• (a)(b...) - 여러 가지 시도.

왜 실패 시 많은 시도:

Backtracking 엔진의 작동:

1. Greedy 매치 시도: 가능한 한 길게.
2. 이후 매치 실패 시 backtrack.
3. 약간 덜 greedy하게 재시도.
4. 반복.

실패가 긴 backtrack 유발:

Regex: (a+)+b
Input: "aaaa" (b 없음)

시도:

1. (aaaa): a 모두 먹음. b 매치 시도 → 실패.
2. Backtrack.
3. (aaa)(a): 3+1. b 매치 시도 → 실패.
4. (aa)(aa): 2+2. b 매치 시도 → 실패.
5. (aa)(a)(a): 2+1+1. 실패.
6. (a)(aaa): 1+3. 실패.
7. ... 2^(n-1) 가지 조합 모두 시도.

복잡도 분석:

n개의 a에 대해 (a+)+의 매칭 시도 수:

• 파티션 수: 2^(n-1).
• 각 파티션 검증: O(n).
• 총: O(n × 2^n).

실측:

• n=20: 100만 시도, ~수 초.
• n=30: 수억 시도, ~수 분.
• n=40: 수조 시도, 수 시간.

수학적 증명:

Backtracking의 최악 복잡도는 Packrat parsing 관점에서 분석 가능:

정규 언어 관점:

• Thompson NFA: O(|regex| × |input|) 다항.
• Backtracking: O(2^|input|) 최악 지수.

이유:

• NFA는 같은 상태에 여러 번 오면 병합.
• Backtracking은 각 경로를 독립적으로 시도.

수학적으로 backtracking은 NFA를 "expanded tree"로 본다. 트리 크기가 지수적일 수 있다.

Ambiguous Regex의 식별:

모든 catastrophic regex가 명백하지 않다. 숨겨진 모호성:

명백한:

• (a+)+
• (a*)*
• (.*)*

숨겨진:

• (a|a)*: a|a는 교집합.
• ([a-z]+\s*)+: 두 양자화의 교집합.
• (.*)=(.*): 두 .*가 같은 위치 공유 가능.

Cloudflare의 정확한 문제:

(?:.*=.*)

이 패턴에서:

• .* 와 .*이 등호 주변에서 분할.
• 긴 문자열이면 분할 위치가 많아 catastrophic.

감지 도구:

여러 도구가 catastrophic regex를 자동 감지:

• regex101.com: 시각화, 경고.
• ReScue: Research tool.
• Rexploiter: 공격 패턴 생성.
• safe-regex (npm): JavaScript.
• rxxr2: 정적 분석.

이들은 regex를 분석해서:

• 중첩 양자화 찾기.
• Ambiguous 분기 찾기.
• 공격 문자열 생성.

방어 전략:

1. Regex 재작성:

나쁨:

(a+)+

좋음:

a+                    # 동등한 결과, 간단

나쁨:

([a-z]+\s*)+

좋음:

(?:[a-z]+\s*)+        # non-capturing, 같은 결과
# 또는 더 나은
[a-z\s]+              # 다른 의미지만 맞으면 사용

2. Atomic Groups (PCRE):

(?>a+)+b             # 첫 번째 a+ 매치 후 backtrack 안 함

Backtracking 차단.

3. Possessive Quantifiers:

a++b                 # a를 가능한 한 많이, backtrack 안 함

PCRE, Java, .NET 지원. Python, JavaScript 지원 안 함.

4. 타임아웃:

import signal

def timeout_handler(signum, frame):
    raise TimeoutError()

signal.signal(signal.SIGALRM, timeout_handler)
signal.alarm(5)  # 5초 제한

try:
    re.match(pattern, input)
except TimeoutError:
    print("Regex too slow")

.NET 4.5+: RegexOptions.Compiled + MatchTimeout.

5. 안전한 엔진:

• Go: RE2 기본.
• Rust: regex crate.
• Python: re2 패키지 (별도 설치).

이들은 항상 선형 시간이다. Catastrophic backtracking 불가능.

교훈:

Catastrophic backtracking은 수학적 현상이다:

1. Ambiguous regex가 많은 매칭 가능성.
2. Backtracking engine이 모든 가능성 탐색.
3. 실패 입력이 최악의 경우.
4. 지수 시간 복잡도.

이는 단순한 "버그"가 아니라 알고리즘의 성질이다. Backtracking 방식을 선택한 대가.

실전 조언:

1. Regex를 단순하게: 복잡해지면 parser 사용 고려.
2. 중첩 양자화 피하기: (a+)+ 패턴 금지.
3. 사용자 입력에 조심: 타임아웃 필수.
4. 가능하면 RE2 계열 엔진: Go, Rust는 기본 안전.
5. 측정: 큰 입력, 악의적 입력으로 벤치마크.

정규식은 강력하지만 위험한 도구다. 수학적 이해가 없으면 프로덕션에서 재앙이 된다. Cloudflare의 30분 다운타임이 이를 증명했다. 이 글을 읽은 당신은 이제 그 함정을 피할 수 있다.

A.

수학적 이유: Backreferences는 정규 언어가 아니다.

정규 언어:

Chomsky 계층에서 정규 언어는:

• 유한 오토마타로 인식 가능.
• Pumping Lemma를 만족.
• 기본 연산자: concat, union, Kleene star.

Backreferences의 본질:

(a+)b\1

이 regex는 "앞서 매치한 (a+)와 동일한 a 개수의 a를 다시 매치". 예: aaabaaa.

이 언어는 a^n b a^n | n >= 1.

정규 언어가 아닌 이유 (Pumping Lemma):

만약 이것이 정규 언어라면, Pumping Lemma에 의해:

• 충분히 긴 문자열 w가 정규 언어에 속함.
• w = xyz로 나눌 수 있고, y != ε.
• 모든 k ≥ 0에 대해 xy^k z 도 언어에 속함.

w = a^n b a^n (충분히 큰 n)에 적용:

• y는 어디에 있나?
• y가 첫 번째 a^n 안에 있다면: y^2로 pump하면 첫 부분이 더 길어져서 두 a^n이 달라짐. 언어 위반.
• y가 b를 포함한다면: y^2는 b가 두 개. 언어 위반.
• y가 두 번째 a^n 안에 있다면: 첫 번째보다 길어짐. 위반.

어떤 경우도 Pumping Lemma를 만족 못 함. 모순 → 정규 언어 아님.

Context-Free일까?:

예. a^n b a^n은 context-free (Dyck 언어와 비슷).

Grammar:

S → aSa | b

더 복잡한 예:

(a+)(b+)\1\2

a^n b^m a^n b^m. 이는 context-sensitive (context-free도 아님).

Backreferences는 context-sensitive language를 인식 가능. 즉, 훨씬 강력하지만 복잡.

복잡도 증가:

정규 언어: O(n) 시간 인식. Context-free: O(n³) 시간 인식. Context-sensitive: 일반적으로 NP-hard.

Backreferences with backtracking: NP-complete.

즉, backreferences 있는 regex matching은 NP 문제다. 어떤 알고리즘도 다항 시간으로 일반적으로 풀 수 없다.

구체적 증명:

Aho가 1990년 증명: Backreferences 있는 regex matching은 NP-complete.

Reduction: 3-SAT을 regex matching으로 환원 가능. 3-SAT이 NP-complete이므로 regex도.

실전 함의:

1. Backtracking만 가능:

• DFA로 표현 못 함.
• NFA로도 깔끔하게 표현 못 함.
• 반드시 backtracking이 필요.

2. 지수 시간 최악:

• Backtracking은 NP 문제에 지수 시간.
• 사용자 입력에 위험.

3. Thompson NFA 접근 불가:

• Thompson의 선형 시간 알고리즘이 작동 안 함.
• "현재 상태 집합"이 backreference를 추적 못함.

RE2의 결정:

Russ Cox와 Google 팀의 철학:

"완벽한 정규 언어 엔진 + 항상 다항 시간"

이를 위해 포기한 것:

• Backreferences.
• Non-constant lookbehind.
• 일부 복잡한 기능.

얻은 것:

• 성능 보장: 모든 regex가 O(n).
• 메모리 예측 가능.
• 안전: ReDoS 불가.
• 대규모 운영 가능.

이 trade-off는 의식적이었다. Google은 수백만 개의 regex를 돌린다. 하나라도 catastrophic하면 재앙. 기능 제한이 가격이다.

RE2가 지원하지 않는 다른 기능:

1. Backreferences: (a+)\1.

2. Variable-length lookbehind: (?<=a+) (PCRE는 지원, 점점).

3. Atomic groups: (?>...) (Backtracking 최적화용).

4. Possessive quantifiers: a++, a*+.

5. Conditional matching: (?(1)yes|no).

6. Recursion: (?R) (PCRE의 재귀 regex).

이들 중 일부는 RE2 철학과 맞지 않는다. 정규 언어 아님 또는 예측 가능 성능 해침.

대안: 더 강한 parser:

정말 backreferences가 필요하면:

1. parser generator: yacc, ANTLR, PEG.
2. hand-written parser: 특정 문법용.
3. 다른 엔진: PCRE, Perl.

Regex는 단순한 매칭용. 복잡한 문법엔 진짜 parser가 낫다.

Backreferences가 필요한 경우:

실전에선 드물다. 대부분의 backreference 사용은 다음으로 대체 가능:

1. HTML 태그 매칭:

# Bad
<(\w+).*?</\1>

# Better: HTML parser 사용

HTML은 정규 언어 아님. Regex로 파싱 금지.

2. 중복 단어:

# Backreferences
\b(\w+)\s+\1\b

# Alternative: 코드로 처리
words = text.split()
for i in range(len(words)-1):
    if words[i] == words[i+1]:
        ...

3. Quoted string:

# Bad
(['"])(.*?)\1

# Better
"([^"]*)"|'([^']*)'

Russ Cox의 인용:

"Regular expressions should be regular." — Russ Cox (paraphrased)

이는 수학적 엄격함이자 실용적 지혜다. "정규"라는 말에는 이유가 있다.

철학적 차이:

Perl/PCRE 진영: "Regex는 편의를 위한 것. 사용자가 원하는 기능 다 추가".

Thompson/Cox/Google 진영: "Regex는 정규 언어. 그 이상은 다른 도구".

둘 다 타당하지만 프로덕션 시스템에서는 후자가 더 안전하다.

교훈:

1. 알고리즘은 타협을 요구한다. "모든 기능 + 빠른 성능"은 불가능. Backreferences를 원하면 backtracking (느림). 선형 시간을 원하면 backreferences 포기.

2. "Regex"의 의미가 모호해졌다. 오리지널 정규식 = 정규 언어. 현대 "regex" = 정규 언어 + 많은 확장. 이 혼란이 성능 문제의 근원.

3. 도구는 목적에 맞게 선택. 단순 매칭 → RE2/Go. 복잡한 파싱 → parser. 편의 + 작은 데이터 → PCRE/Python. 각자의 영역이 있다.

4. 보안 관점. 사용자 입력에 regex 적용 시 RE2 계열 엔진 강력 권장. ReDoS 공격 불가능.

5. 역사적 맥락 이해. Thompson(1968) → Perl(1987) → PCRE(1997) → RE2(2007). 각 단계가 trade-off를 선택했다. 맹목적으로 "regex가 다 똑같다"고 생각하면 함정에 빠진다.

결론:

RE2가 backreferences를 지원하지 않는 것은 결함이 아니라 기능이다. 수학적 필연이자 의식적 선택이다. 정규 언어의 엄격함을 받아들이는 대가로 예측 가능한 성능과 안전을 얻는다.

프로덕션에서 어떤 엔진을 쓸지 선택할 때, 이 trade-off를 이해하는 것이 중요하다. "더 많은 기능"이 항상 "더 나은 도구"는 아니다. 때로는 제한이 해방이다.

A.

근본 문제: ReDoS 공격

ReDoS (Regular Expression Denial of Service) 는 사용자가 악의적 입력으로 서버의 regex를 catastrophic backtracking에 빠뜨려 CPU를 고갈시키는 공격이다.

공격 시나리오:

# 서버 코드
import re
def validate_email(email):
    pattern = r'^(\w+)@(\w+\.)+(\w+)$'
    return re.match(pattern, email) is not None

# 악의적 요청
validate_email('a' * 1000 + '!')
# 수 초~수 분 CPU 100%

한 요청으로 서버 한 쓰레드를 몇 분간 마비. 수십 요청으로 서버 전체 다운.

실제 사례:

• Cloudflare 2019: WAF regex 하나로 30분 다운타임.
• Stack Overflow 2016: 화이트스페이스 regex로 34분 다운.
• Azure DevOps 2023: 정규식 CPU 고갈.

방어 전략 1: 안전한 엔진 사용

가장 확실한 방법.

Go, Rust:

// Go는 RE2 기본. 항상 안전.
re := regexp.MustCompile(pattern)
re.MatchString(userInput)  // 공격 불가능

Python:

# 기본 re 대신 re2 사용
import re2 as re
re.match(pattern, user_input)

re2 패키지 설치 필요 (pip install re2).

JavaScript:

// V8의 non-backtracking engine (실험적)
const re = new RegExp(pattern, 'u');
// 또는 RE2 WASM
import RE2 from 're2';
const re = new RE2(pattern);
re.test(userInput);

.NET:

// .NET 7+
var regex = new Regex(pattern, RegexOptions.NonBacktracking);
regex.IsMatch(userInput);

.NET 7부터 공식 non-backtracking engine 지원.

방어 전략 2: 타임아웃

안전한 엔진을 못 쓰면 타임아웃으로 제한:

Python:

import signal

class RegexTimeoutError(Exception):
    pass

def _timeout_handler(signum, frame):
    raise RegexTimeoutError()

def safe_regex_match(pattern, text, timeout=5):
    signal.signal(signal.SIGALRM, _timeout_handler)
    signal.alarm(timeout)
    try:
        return re.match(pattern, text)
    except RegexTimeoutError:
        return None
    finally:
        signal.alarm(0)

주의: SIGALRM은 POSIX만. Windows는 다른 방법 (threading).

Java:

// Java 8+
Pattern pattern = Pattern.compile(regex);
Matcher matcher = pattern.matcher(input);

// Timeout은 명시적 interrupt 필요
Thread t = new Thread(() -> matcher.matches());
t.start();
t.join(5000);  // 5초 대기
if (t.isAlive()) {
    t.interrupt();
    throw new TimeoutException();
}

.NET:

// .NET 4.5+
var regex = new Regex(pattern, RegexOptions.None, TimeSpan.FromSeconds(5));
try {
    regex.Match(input);
} catch (RegexMatchTimeoutException) {
    // 처리
}

JavaScript:

// JavaScript는 native regex timeout 없음
// Web Worker에서 실행 + timeout
const worker = new Worker('regex-worker.js');
worker.postMessage({pattern, input});
setTimeout(() => worker.terminate(), 5000);

방어 전략 3: 입력 검증

Regex 이전에 입력을 검증.

1. 길이 제한:

def validate_email(email):
    if len(email) > 100:  # 이메일 RFC 최대 길이
        return False
    return re.match(pattern, email) is not None

2. 문자 제한:

def validate_input(text):
    if not re.match(r'^[a-zA-Z0-9@._-]+$', text):
        return False  # 이상한 문자 거부
    return re.match(complex_pattern, text) is not None

단순한 사전 검증이 복잡한 regex보다 빠르고 안전.

3. Rate limiting:

# 사용자당 초당 10 요청
from ratelimit import limits

@limits(calls=10, period=1)
def regex_endpoint(request):
    return re.match(pattern, request.input)

악의적 사용자의 반복 공격 방어.

방어 전략 4: Regex 재작성

Catastrophic 패턴 제거.

나쁨:

(a+)+b

좋음:

a+b
# 같은 결과, catastrophic 아님

나쁨:

([a-z]+\s*)+

좋음:

(?:[a-z]+\s*)+
# non-capturing, 여전히 취약. 다음으로 변경:
[a-z\s]+
# 다른 의미지만 catastrophic 아님

나쁨:

.*=.*

좋음:

[^=]*=[^=]*
# 공유 영역 제거

방어 전략 5: Atomic Groups / Possessive Quantifiers

PCRE, Java, .NET 지원:

(?>a+)+b           # atomic group
# 또는
a++b               # possessive quantifier

Backtracking 방지.

Python, JavaScript는 지원 안 함. 이 경우 다른 방어법 사용.

방어 전략 6: 정적 분석

Regex 검사 도구:

# safe-regex (npm)
npm install safe-regex

const safe = require('safe-regex');
console.log(safe('(a+)+'));  // false - catastrophic!
console.log(safe('a+'));      // true - safe

Python:

pip install rstr
# 정적 분석 + 공격 문자열 생성

온라인 도구:

• regex101.com: 시각화, 경고.
• rxxr2: 학술 도구.
• redos-checker: GitHub Action.

CI/CD 통합:

# GitHub Actions
- name: Check regex safety
  run: |
    find src -name "*.py" | xargs -I {} python -c "
      # 각 파일의 regex 추출 및 검증
    "

커밋할 때 자동 검증.

방어 전략 7: 방어적 코딩

원칙: 사용자 입력에 복잡한 regex 적용 전 의심.

Checklist:

1. 정말 regex가 필요한가?

   • 단순 매칭은 문자열 메서드 (in, startswith, endswith).
   • 복잡한 구조는 parser 사용.

2. Regex가 정말 이 복잡해야 하나?

   • 단순화 가능한가?
   • 여러 단계로 나눌 수 있나?

3. 사용자 입력 범위는?

   • 길이 제한.
   • 문자 제한.
   • 빈도 제한.

4. 타임아웃 있나?

   • 항상 설정.
   • 적절한 값 (보통 1-5초).

5. Catastrophic 패턴 있나?

   • 중첩 양자화?
   • 교집합 분기?
   • 정적 분석 도구 사용.

6. 엔진 선택 가능한가?

   • RE2 / Go / Rust?
   • .NET의 NonBacktracking?

7. 모니터링:

   • 느린 regex 로깅.
   • 이상 감지.
   • CPU 사용률 알림.

실전 예시: 안전한 이메일 검증:

import re

EMAIL_PATTERN = re.compile(
    r'^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$'
)

def is_valid_email(email: str) -> bool:
    # 1. 길이 검증 (RFC 5321)
    if len(email) > 254:
        return False
    
    # 2. 기본 문자 검증
    if not re.match(r'^[\w@.+\-]+$', email):
        return False
    
    # 3. 복잡 regex (위 검증 통과했으면 안전)
    return EMAIL_PATTERN.match(email) is not None

주의 사항:

이 패턴은 완전한 RFC 5321 준수가 아님. 완전 준수는 복잡하고 위험. "대부분의 실전 이메일" 을 받아들이는 것으로 타협.

이상적 아키텍처:

User Input
    ↓
[Rate Limiter]  ← 초당 X 요청 제한
    ↓
[Length Check]  ← 최대 길이 100
    ↓
[Character Whitelist]  ← 허용 문자만
    ↓
[Fast Regex]  ← 단순 패턴
    ↓
[Slow Regex with Timeout]  ← 복잡 패턴 (5초 timeout)
    ↓
Validated Input

여러 레이어의 방어. 하나가 뚫려도 다음이 있음.

모니터링:

Production metrics:

import time

def timed_regex(pattern, text):
    start = time.perf_counter()
    result = re.match(pattern, text)
    elapsed = time.perf_counter() - start
    
    if elapsed > 0.1:  # 100ms 이상
        logger.warning(f'Slow regex: {elapsed}s, pattern: {pattern[:50]}')
    
    return result

느린 regex 로깅. 이상 패턴 발견.

Alerting:

# Prometheus alert
alert: SlowRegexDetected
expr: regex_duration_seconds > 1
for: 1m
annotations:
  summary: "Regex taking too long"

교훈과 원칙:

1. Assume malicious: 사용자 입력은 적대적이다. 모든 방어 필요.

2. Defense in depth: 하나의 방어만 믿지 마라. 여러 레이어.

3. Prefer safe engines: Go/Rust는 기본 안전. 선택 가능하면 선택.

4. Test with pathological inputs: 악의적 입력으로 벤치마크.

5. Monitor and alert: 이상 감지.

6. Simplify when possible: 단순한 코드가 더 안전.

7. Know your tools: 사용하는 언어/엔진의 특성 이해.

역사의 교훈:

Cloudflare 2019:

• 교훈: 복잡한 WAF regex + backtracking = 재앙.
• 조치: RE2로 전환.
• 결과: 이후 유사 사건 0.

Stack Overflow 2016:

• 공백 정규화 regex.
• 특정 입력에 34분 다운.
• 조치: Regex 재작성, 타임아웃.

이런 사건들은 공개적으로 post-mortem 공유되었다. 업계 전체가 배웠다.

결론:

사용자 입력에 regex를 안전하게 쓰는 것은 복합적 문제다:

• 엔진 선택 (RE2 계열 선호).
• 입력 검증 (길이, 문자, rate).
• 타임아웃 (항상).
• 패턴 검토 (catastrophic 피하기).
• 모니터링 (느린 regex 감지).
• 정적 분석 (CI/CD 통합).

이 모두가 결합되면 강건한 시스템이 된다. 하나만으로는 부족하다.

최종 권장:

프로덕션 시스템에서:

1. 가능하면 Go/Rust 사용: 원천 차단.
2. Python/Node.js: RE2 계열 라이브러리 (re2, node-re2).
3. 그 외: 타임아웃 + 입력 검증 + 정적 분석.
4. 모니터링 필수.
5. 정기 검토: 새 regex 추가 시 보안 검토.

정규식은 강력하지만 위험하다. 이 이중성을 이해하고 조심히 다루는 것이 프로페셔널 엔지니어의 표시다. "그냥 regex 쓰면 되지"라는 태도는 Cloudflare 같은 사건을 만든다.

당신의 regex가 당신의 서비스를 다운시키지 않도록 하라. 그것이 이 글의 핵심 메시지다.