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

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

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 + "!"` (항상 실패)

| N | Python re | Perl | Go regexp | RE2 | Rust regex |

| --- | --- | --- | --- | --- | --- |

| 10 | 1ms | 1ms | 1µs | 1µs | 1µs |

| 20 | 1s | 1s | 1µs | 1µs | 1µs |

| 25 | 40s | 40s | 1µs | 1µs | 1µs |

| 30 | 20min | 20min | 1µs | 1µs | 1µs |

지수 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.