✍️ 필사 모드: 정규표현식 엔진 완전 정복 — NFA, DFA, 백트래킹, ReDoS, Thompson vs PCRE의 깊은 이야기 (2025)

0. 12글자 입력이 10초 걸리는 정규식

다음 Python 코드를 실행해보면 :

import re
re.match(r'(a+)+$', 'a' * 25 + '!')
# 10초+ 걸림

고작 26글자 입력인데 엔진이 멈춘다. 왜? 더 무서운 건:

'aaaaaaaaaaaaaaaaaaaaaaaaaa!'.match(/(a+)+$/)

JavaScript 도 같은 증상. 하지만:

// Go 의 regexp 패키지 (RE2 기반)
regexp.MustCompile(`(a+)+$`).MatchString("aaaaaa...!")
// 즉시 완료

같은 정규식이 언어에 따라 10초 대 1µs. 차이가 1억 배.

이 차이의 뿌리를 이해하려면 1950년대 Kleene 의 정규 언어 이론부터 2019년 Cloudflare 장애까지 되돌아가야 한다. 이 글은 정규식 엔진의 내부와 왜 어떤 엔진이 재앙이고 어떤 엔진이 안전한지를 파헤친다.

1. 정규식의 짧지 않은 역사

1.1 1956 — Kleene 의 "Regular Events"

MIT 의 Stephen Kleene 이 신경망 모델을 연구하다가 "정규 표현식" 을 정의. 세 가지 원시 연산:

• 연결 (concatenation): ab = a 뒤에 b.
• 선택 (alternation): a|b = a 또는 b.
• 반복 (Kleene star): a* = a 를 0번 이상.

이 세 연산으로 만들 수 있는 모든 패턴 = 정규 언어 (regular language).

1.2 1968 — Thompson 의 grep

Bell Labs 의 Ken Thompson 이 이론을 실용화. QED (ed 의 조상) 에 정규식 검색 기능 추가. 1968년 "Regular Expression Search Algorithm" 논문.

• Kleene 의 수학 → NFA (Non-deterministic Finite Automaton).
• 실시간으로 기계어 컴파일 (당시로선 혁명적).
• grep 명령어로 파급.

1.3 1980s — awk, sed, egrep

각자 방언으로 확장. "basic" vs "extended" 정규식 분기 시작.

1.4 1987 — Larry Wall 의 Perl

Perl 이 정규식을 1급 언어 기능 으로 승격. $string =~ /pattern/ 문법. 캡처 그룹, 백레퍼런스, lookahead 도입.

1.5 1997 — PCRE

Philip Hazel 의 "Perl Compatible Regular Expressions" 라이브러리. 거의 모든 언어 (PHP, Python re, Java, JavaScript, Ruby, .NET) 가 PCRE 스타일 채택. 그리고 백트래킹 기반 구현도 함께 전파.

1.6 2009 — Google RE2

Russ Cox 가 "Regular Expression Matching Can Be Simple And Fast" 라는 유명한 글에서 "왜 우리는 Thompson 의 1968 알고리즘을 잊었나?" 를 제기. RE2 오픈 소스 공개. 이후 Go, Rust 의 regex crate 등이 NFA 기반으로 회귀.

2. 두 가지 매칭 패러다임 — NFA 시뮬레이션 vs 백트래킹

2.1 핵심 질문

정규식 a*b 가 aaab 에 매치되는지 확인하려면? 두 가지 전략:

Thompson 식 (NFA 시뮬레이션): "가능한 모든 상태를 동시에 따라간다."

Perl 식 (백트래킹): "한 경로를 끝까지 시도해보고, 실패하면 되돌아가서 다른 경로 시도."

2.2 간단한 예: a*b 매치 aaab

Thompson:

초기 상태 집합: {S0}
'a' 입력 → {S0, S1}      (S0 에서 'a' loop, 또는 S1 이동)
'a' 입력 → {S0, S1}
'a' 입력 → {S0, S1}
'b' 입력 → {S2}           (accept!)

매 글자마다 O(상태 수) 작업 → 전체 O(n × k).

Perl (백트래킹):

a 매치, 다음 a 매치, 다음 a 매치, 다음 b 매치 → 성공.

이런 쉬운 경우에는 둘 다 빠르다. 문제는 다음 같은 패턴:

2.3 (a|a)*b 매치 aaaa (실패 케이스)

Thompson 은 여전히 O(n): 상태 수가 제한적.

Perl 백트래킹:

• 첫 'a' 를 왼쪽 a 로? 오른쪽 a 로? 2가지.
• 두 번째 'a' 도 2가지.
• n개 'a' 이면 2^n 경로 탐색.
• 마지막에 'b' 가 없으므로 모든 2^n 경로 시도 후 실패.

a 20개면 100만 경로. 30개면 10억 경로. 지수 시간 폭발.

이게 (a+)+$ 가 26글자에 10초 걸리는 이유.

3. Thompson 의 NFA 구성법

3.1 재귀적 구성

정규식의 각 연산을 NFA 조각으로 매핑:

단일 문자 'a':
  ─[a]→ ○

연결 e1·e2:
  [NFA of e1] → [NFA of e2]

선택 e1|e2:
     ┌→ [e1] ─┐
  ○─┤         ├→ ○
     └→ [e2] ─┘

Kleene star e*:
       ┌───────┐
       ↓       │
  ○ ─→ [e] ─→ ○
       │           
       └────→ (accept)

각 NFA 조각은 단일 시작, 단일 종료 상태. 재귀적으로 조립. 결과 NFA 의 크기는 정규식 길이에 선형.

3.2 ε-전이 (epsilon transition)

입력 없이 상태 이동. 위 다이어그램의 "빈 화살표" 가 ε-전이. 구성을 단순하게 만들지만 시뮬레이션 시 "모든 도달 가능 상태" 계산 필요.

3.3 시뮬레이션 알고리즘

state_set = {start_state}
state_set = ε_closure(state_set)

for c in input:
    new_set = {}
    for s in state_set:
        for s' in transition(s, c):
            new_set.add(s')
    state_set = ε_closure(new_set)

if accept_state in state_set:
    return MATCH

핵심 보장: 각 상태가 집합에 최대 1번 → 전체 시뮬레이션 O(n × |states|). 상태 수는 정규식 길이에 선형 → O(n × m) (n: 입력 길이, m: 정규식 길이).

3.4 NFA → DFA 변환 (Subset Construction)

NFA 를 DFA 로 변환할 수도 있다:

• DFA: 각 상태에서 각 입력에 단일 다음 상태.
• "NFA 의 상태 집합" → "DFA 의 단일 상태".
• 실행: O(n), 단순 테이블 조회.

단점: DFA 상태 수가 지수 폭발 가능 (NFA 상태 2^k).

3.5 Hybrid 접근

RE2 는 lazy DFA 구성:

• 실행 중 필요한 DFA 상태만 생성.
• 캐시 크기 제한 → 초과하면 NFA 시뮬레이션으로 fallback.
• 실전에서는 대부분 DFA 히트 → O(n) 성능.

4. 백트래킹 엔진의 작동 방식

4.1 Perl/PCRE 스타일 알고리즘

def match(pattern, pos, input, ipos):
    if pattern[pos] == END:
        return ipos
    op = pattern[pos]
    
    if op == CHAR(c):
        if input[ipos] == c:
            return match(pattern, pos+1, input, ipos+1)
        else:
            return FAIL
    
    if op == STAR(sub):
        # Greedy: 가능한 한 많이 매치
        for count in range(max, 0, -1):
            r = try_match_n(sub, count)
            if r != FAIL:
                return match(pattern, pos+1, input, ipos + r)
        return match(pattern, pos+1, input, ipos)  # 0 번 매치
    
    if op == ALT(e1, e2):
        r = match(e1, ipos)
        if r != FAIL:
            return match(pattern, pos+1, input, r)
        return match(e2, ipos)  # 첫 대안 실패 → 두 번째

• 각 선택지/반복 횟수에 대해 재귀 호출.
• 실패 시 되돌아가서 다른 선택 → "backtrack".
• 구현 단순, 기능 풍부.

4.2 왜 매력적인가

백트래킹 엔진이 지원할 수 있는 추가 기능 이 많다:

• 백레퍼런스 \1: "앞에서 캡처한 것과 같은 문자열 다시". NFA 로는 표현 불가.
• Lookahead/Lookbehind (?=...), (?<=...): 소비 없이 조건 확인.
• 원자 그룹 (?>...): 한 번 매치하면 되돌리지 않음.
• 조건부 매치 (?(1)then|else).

이 기능들이 편리해서 수많은 언어가 PCRE 를 채택. 하지만 편리함의 대가가 ReDoS.

5. ReDoS — 정규식 서비스 거부

5.1 취약한 패턴의 분류

세 가지 패턴 카테고리가 지수 시간을 유발:

1. Nested Quantifier: (a+)+, (a*)*, (a|a)*

• 외부 반복 × 내부 반복 → 경로 수 조합 폭발.

2. Overlapping Alternation: (a|ab)*c 에 aaab

• a 와 ab 가 겹침 → 매 위치에서 두 경로.

3. Catastrophic 조합: ^(a+)+$, ^(a|a)*$

5.2 탐지 원리

매 'a' 입력 시 엔진이 선택: "a+ 반복을 계속? 아니면 새 (a+) 시작?" → 둘 다 유효 → 두 경로 탐색 → 다음 글자에서 또 두 경로...

실제 매치 성공 시에는 첫 경로가 바로 먹힘. 매치 실패 시 (끝에 매치 안 되는 글자 있음) 에 모든 조합을 다 시도해야 함 → 지수 폭발.

5.3 Cloudflare 2019년 장애

2019년 7월 2일, Cloudflare 가 27분간 전 세계적으로 다운. 원인: WAF 규칙에 추가된 정규식:

(?:(?:"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

이 패턴이 특정 입력에 대해 지수 폭발. 한 스레드가 100% CPU 사용 → 전체 Cloudflare 네트워크에 연쇄.

교훈:

• 모든 정규식을 운영 환경에 배포하기 전에 복잡도 분석 필요.
• WAF 같은 외부 입력 매칭에는 RE2 같은 안전 엔진.
• Cloudflare 는 이후 자체 안전 엔진 개발.

5.4 StackOverflow 2016년 장애

2016년 7월, StackOverflow 도 34분간 다운. 원인: 게시물 앞뒤 공백 제거 정규식이 특정 긴 공백 시퀀스에서 폭발.

5.5 ReDoS 공격 벡터

사용자 입력을 정규식에 매칭하는 모든 서비스:

• 사용자명 검증.
• 이메일 검증 (유명한 ^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@)([a-zA-Z0-9]+)(([\.\-]?[a-zA-Z0-9]+)*)(\.)([a-zA-Z]{2,})$ 가 취약).
• 로그 필터링.
• 파싱.

공격자가 특수 입력을 보내 CPU 100% 점유 → 서비스 마비.

6. 안전한 엔진들 — RE2, Hyperscan, Rust regex

6.1 RE2 (Google, 2010)

설계 원칙:

• 백레퍼런스 없음, lookaround 없음 → 순수 정규 언어만.
• 컴파일 → NFA 또는 DFA.
• 런타임 메모리 제한.
• 입력 크기에 선형 시간 보장.

용도: 외부 입력, 대량 로그 처리, 웹 크롤링. Google Search 내부에 광범위하게 사용.

6.2 Hyperscan (Intel, 2015)

FPGA 출신 엔지니어들이 만든 SIMD 기반 매칭:

• 한 번에 여러 패턴을 동시 매칭.
• AVX2, AVX-512 활용.
• IDS (침입 탐지) 에 최적화.
• Snort, Suricata 가 채택.

6.3 Rust regex crate

RE2 스타일 + 추가 최적화:

• 백레퍼런스 없음.
• lazy DFA.
• Unicode 완전 지원.
• SIMD 가속.

Rust 커뮤니티의 Burntsushi (Andrew Gallant) 의 작품. ripgrep, fd 같은 CLI 도구의 기반.

6.4 Go regexp

표준 라이브러리. RE2 를 Go 로 포팅. 제한적 기능이지만 항상 안전.

6.5 Java Pattern

PCRE 스타일 백트래킹. Java 11+ 에서 일부 상황 선형 매칭 개선. 하지만 여전히 ReDoS 가능.

6.6 JavaScript 의 상황

V8 은 Irregexp (백트래킹). 2021년 V8 v9.1 에 experimental mode 로 비역추적 엔진 추가. --enable-experimental-regexp-engine 플래그 + /l flag. 점진적 안전화.

7. 엔진별 성능 비교 실험

7.1 벤치마크 설정

패턴: (a+)+$ 입력: "a" * N + "!" (항상 실패)

지수 vs 선형의 차이.

7.2 실전 패턴에서는

실제 프로덕션 정규식은 대부분 취약 패턴 없음 → 차이가 크지 않거나 백트래킹이 더 빠를 수도. 하지만 외부 입력을 처리하는 서비스 는 최악 시나리오 보장이 필수.

8. 안전한 정규식 작성 가이드

8.1 의심스러운 패턴 감지

• 중첩 반복: (a+)+, (a*)*, (.*)* → 즉시 의심.
• 중복 선택: (a|ab)* 에서 첫 글자 겹침.
• 긴 lookahead: (?=.*a)(?=.*b)(?=.*c) 같은 조합.

8.2 구체적 문자 클래스

나쁨: ^(.+)+$       → . 이 너무 많은 매치
좋음: ^([^x]+)+$    → 특정 글자 제외
더좋음: ^([a-z]+)+$ → 명확한 범위

8.3 원자 그룹 / Possessive Quantifier (PCRE)

나쁨: (a+)+         → 백트래킹
좋음: (a++)+        → possessive: 내부 a+ 가 되돌리지 않음
더좋음: (?>a+)+     → 원자 그룹: 같은 효과

JavaScript, Python 은 미지원. PCRE, Java, Ruby 에서만.

8.4 앵커 활용

나쁨: foo.*bar       → foo 발견 후 탐욕적 스캔, 실패 시 역추적
좋음: foo[^b]*bar    → b 아닌 문자만 → 탐욕도 덜하고 역추적도 제한

8.5 타임아웃 설정

.NET, Java 9+ 는 정규식 타임아웃 지원:

Pattern p = Pattern.compile(regex);
// 매칭에 500ms 이상 걸리면 예외
Matcher m = p.matcher(input, 500, TimeUnit.MILLISECONDS);

.NET 의 Regex.MatchTimeout 기본 설정 권장.

8.6 정적 분석 도구

• eslint-plugin-redos: JavaScript.
• safe-regex (npm): 보수적 검출.
• rxxr2: 구체적 공격 입력 생성.
• recheck: 자동 ReDoS 검증.

8.7 대안: 파서 사용

복잡한 패턴 (이메일, URL, JSON 등) 은 전용 파서 사용. 정규식은 "3자 이내 대문자" 같은 단순 매칭용.

나쁨: 이메일 검증 정규식 (수십 줄, 여전히 불완전)
좋음: email-validator 라이브러리 (실제 RFC 5322 파서)

9. 유니코드와 정규식

9.1 . 이 매치하는 것

• 기본: 단일 code unit (UTF-16 에서는 단일 surrogate).
• '👨'.match(/^.$/) → JavaScript 에서 false (이모지가 2 surrogate).
• Python/Go: code point 기반.
• u flag / Unicode mode: code point 단위로.

9.2 Grapheme 클러스터는 어려움

👨‍👩‍👧‍👦 (4인 가족 이모지) = 7 code points + 3 ZWJ. "한 글자" 로 매치하는 정규식 언어는 거의 없음. Intl.Segmenter 같은 라이브러리 별도.

9.3 Case-insensitive 의 함정

Turkish i 문제 (앞선 Unicode 포스트 참조):

• /İ/i.test('i') → locale 따라 결과 다름.
• \p{Lu} (Unicode 속성) 쓰는 게 안전.

9.4 Unicode 속성 매치

\p{Letter}         : 모든 글자
\p{Decimal_Number} : 모든 숫자
\p{Script=Hangul}  : 한글
\p{Emoji_Presentation} : 이모지

ECMAScript 2018+, Python, Java 등 현대 엔진 지원. 매우 유용.

10. 정규식 최적화 트릭

10.1 앵커 우선

나쁨: /abc/.test(str)       → str 어디든 abc 찾음
좋음: /^abc/.test(str)       → 시작만 확인

엔진이 첫 시도 후 바로 실패 가능.

10.2 Literal prefix 추출

엔진들은 보통 "시작이 반드시 특정 문자열" 인 정규식을 감지해 Boyer-Moore 같은 문자열 검색으로 빠르게 스킵. RE2, Rust regex 모두 적용.

10.3 Character class 간결화

나쁨: [abcdefghij...z]
좋음: [a-z]

나쁨: (a|b|c|d|e)
좋음: [abcde]

선택 대신 문자 클래스 → 단일 상태 + 테이블 조회로 더 빠름.

10.4 컴파일된 객체 재사용

// 나쁨 (매번 컴파일):
for (let s of arr) if (/pattern/.test(s)) ...

// 좋음:
const re = /pattern/;
for (let s of arr) if (re.test(s)) ...

Python 은 re.compile 결과를 저장. 내부 캐시가 있지만 명시가 더 안전.

10.5 global vs 단일 매치

JS 에서 /g flag 는 lastIndex 유지 → 같은 객체 재사용 시 혼란. 단일 매치는 flag 없이.

11. 엔진 선택 가이드

PCRE 계열 (백트래킹) 을 선택해야 할 때:

• 백레퍼런스, lookaround 필수.
• 입력이 통제된 상황 (설정 파일, 개발자 작성).
• 최악 시간 보장 불필요.

RE2 계열 (NFA/DFA) 을 선택해야 할 때:

• 외부 입력 을 매칭.
• 최악 시간 보장 필요.
• 대량 데이터 처리.
• 백레퍼런스 불필요.

Hyperscan 을 선택해야 할 때:

• 수천 개 패턴 동시 매칭.
• 네트워크 IDS, 로그 패턴 매칭.
• 최대 처리량 필요.

12. 마치며 — 단순해 보이는 기능의 깊이

/[a-z]+/ 라는 한 줄 뒤에는:

• 1956년 Kleene 의 수학.
• 1968년 Thompson 의 선형 시간 알고리즘.
• 1987년 Perl 의 편리성 확장.
• 2019년 Cloudflare 의 처참한 교훈.
• 2024년 JavaScript 의 experimental safe mode.

50년 넘는 CS 역사와 수많은 장애가 쌓여 있다.

다음에 정규식을 쓸 때:

1. 이 패턴이 외부 입력을 받는가?
2. 중첩 반복이 있는가?
3. 엔진이 ReDoS 에 취약한 백트래킹 기반인가?
4. 타임아웃 또는 안전 엔진으로 보호되는가?

이 네 질문이 다음 장애를 막을 수 있다.

다음 글에서는 해시 테이블의 내부 — 왜 Java HashMap 이 Red-Black Tree 로 떨어지고, 왜 Rust 가 SipHash 를 쓰고, 왜 Abseil 의 Swiss Table 이 SIMD 로 3배 빠른지 — 를 파볼 예정이다. 매일 쓰는 dict, Map, HashMap 뒤의 수십 년간 축적된 트릭들.

참고 자료

• Stephen Kleene — "Representation of Events in Nerve Nets and Finite Automata" (1956).
• Ken Thompson — "Regular Expression Search Algorithm" (CACM, 1968).
• Russ Cox — "Regular Expression Matching Can Be Simple And Fast" (2007), 블로그 시리즈 전체.
• "Flex & Bison" — John Levine (O'Reilly, 2009).
• Cloudflare 2019 장애 포스트모템.
• James Davis et al — "The Impact of Regular Expression Denial of Service (ReDoS) in Practice" (ICSE 2018).
• Intel Hyperscan 논문 + 오픈소스.
• Burntsushi (Andrew Gallant) — Rust regex 내부 문서.
• "Mastering Regular Expressions" — Jeffrey Friedl (O'Reilly, 3rd ed).
• Google RE2 wiki.