정규표현식 테스터

2019년 7월 2일 13:42 UTC, Cloudflare 글로벌 엣지의 모든 서버가 CPU 100%에 도달했습니다. HTTP 트래픽이 멈췄습니다. 공개 포스트모템에 따르면 원인은 몇 분 전 배포된 WAF 룰 하나 — (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*))) 끝의 무경계 +가 붙은 그 문자 클래스가 특정 입력에 적용되자 PCRE의 지수 시간 backtracking이 발동했습니다. 정규식 엔진이 수십억 가지 순열을 시도하는 폭주 상태에 들어갔고, Cloudflare 모든 서버의 모든 CPU가 27분간 이 작업으로 가득 찼습니다. 포스트모템은 실패 모드의 이름을 지었습니다 — catastrophic backtracking, 일명 ReDoS(Regex Denial of Service). 메커니즘은 구조적입니다. 대부분의 프로덕션 정규식 엔진(PCRE, Java java.util.regex, Python re, Ruby Onigmo, JavaScript V8 Irregexp)은 backtracking 매칭으로 구현됩니다. 패턴 후반부에서 매치 시도가 실패하면 엔진이 되돌아가 다른 경로를 시도합니다. 중첩 quantifier — (a+)+, (.*)*, (\w*)*$ 같은 패턴 — 에서 각 글자가 inner / outer 그룹에 분배되는 방법이 지수적으로 많아집니다. 30자 입력이 2^30 ≈ 10억 번의 분배 시도를 만들어내고서야 엔진이 포기합니다. CPU는 한 번의 매치에 초·분, 때로는 수년을 씁니다. 주의해야 할 패턴 — (1) quantifier 안에 quantifier가 들어간 모든 형태 — (a+)+가 교과서 사례. (2) 같은 prefix를 갖는 alternation — (a|aa)+. (3) 매치 안 될 수 있는 literal로 끝나는 무경계 greedy — ^(a+)+\$를 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"에 적용하면 대부분의 엔진이 기어갑니다. 방어 세 가지 — (1) 구조적으로 면역인 엔진 사용. RE2(Google), Hyperscan, Rust regex crate, Go regexp, Lua patterns 모두 선형 시간 NFA 시뮬레이션 — backtrack을 안 합니다. 비용은 일부 형태의 backreference / lookbehind 미지원이지만 실무 패턴 95%엔 문제없음. RE2는 말 그대로 구글에서 ReDoS가 났기 때문에 만들어졌습니다. (2) 모든 regex 평가에 wall-clock timeout. Java Pattern.matcher는 내장 timeout 없음(thread interrupt 활용 필요). .NET은 정확히 이 이유로 Regex(pattern, options, timeout)을 추가. (3) 패턴 린팅. vuln-regex-detector, safe-regex, ESLint no-unsafe-regex 같은 도구가 최악의 구조를 배포 전에 잡아냅니다. 실무 규칙 — 최종 사용자에게서 regex를 받는다면 timeout 없는 언어 기본 엔진은 절대 금지. 패턴을 직접 쓴다면 린터를 돌리세요 — 특히 요청 경로의 WAF나 입력 validator에 배포하기 전. 2019년 Cloudflare는 둘 다 안 했습니다.

// Catastrophic patterns
/^(a+)+$/.test('a'.repeat(30) + 'b');
// V8: ~30 seconds. Engine in tight backtracking loop.

/(.*)*=/.test('=' + 'a'.repeat(50));
// Even worse with inner unbounded greedy.

// Production safety in Node
const RE2 = require('re2');         // linear time
const safe = new RE2('(a+)+');
safe.test('a'.repeat(30) + 'b');    // returns instantly, false

// Native regex with watchdog (workers)
function timedRegex(pattern, input, ms = 50) {
  return new Promise((resolve, reject) => {
    const w = new Worker(`onmessage = e => {
      const re = new RegExp(e.data.p);
      postMessage(re.test(e.data.s));
    }`, { eval: true });
    const timer = setTimeout(() => { w.terminate(); reject(new Error('regex timeout')); }, ms);
    w.onmessage = e => { clearTimeout(timer); resolve(e.data); w.terminate(); };
    w.postMessage({ p: pattern, s: input });
  });
}

// .NET — built-in timeout
var re = new Regex(pattern, RegexOptions.None, TimeSpan.FromMilliseconds(50));

현대 정규식 구현은 세 엔진이 지배합니다. 차이가 중요합니다. PCRE (Perl Compatible Regular Expressions). PHP, nginx, Apache, 과거 Cloudflare WAF 등을 떠받친 C 라이브러리. backtracking 기반, 최대 기능셋 지원 — backreference, lookbehind(PCRE2는 가변 길이), recursion, atomic group, possessive quantifier, 조건 패턴, 모든 문법의 named capture, callout. 비용은 최악 시간 — 적대적 입력에서 지수 시간. PCRE2(현대 fork)는 JIT 컴파일러를 추가해 평균 케이스 매칭 속도를 RE2와 비슷하게 만들었지만 최악 케이스는 그대로입니다. RE2 (Google). Russ Cox의 C++ 구현. Go 표준 라이브러리에도 묶임. Thompson NFA 시뮬레이션 — 엔진이 가능한 파서 상태들의 집합을 유지하며 입력을 lockstep으로 전진. 패턴 복잡도와 무관하게 입력 길이의 선형 시간. 트레이드오프는 미지원 기능 — 임의의 backreference(regex가 임의의 이전 매치 텍스트를 기억해야 하면 안 됨), 일부 바인딩에서 lookbehind는 bounded 길이로 제한. 실코드 정규식 95%엔 drop-in 대체이고 ReDoS를 약간의 비주류 기능을 잃는 대신 제거. Google은 일련의 regex outage 이후 내부 서비스를 모두 RE2로 옮겼습니다. JavaScript V8 (Irregexp). 브라우저 regex 엔진. backtracking 기반이지만 매우 최적화 — 패턴을 JIT 수준에서 네이티브 코드로 컴파일. lookbehind(2018, ES2018부터), named capture (\(?<name>...\)), Unicode property escape (\p{Letter}), s 플래그(dotAll), d 플래그(match indices) 지원. timeout 프리미티브는 없습니다 — 폭주 패턴은 탭을 죽입니다. 최신 V8(2022 이후)은 v8 엔진 플래그로 /l을 켜는 실험적 linear-time 모드를 갖지만 기본 off이고 표준 JS에 노출되지 않습니다. 실무 가이드 — 서버 사이드, 사용자 입력에 닿는 패턴은 RE2 우선(Go 네이티브, Node re2 npm, Rust regex-rs, Python google-re2). 풍부한 기능셋이 필요하고 패턴을 신뢰한다면 PCRE. 브라우저 사이드는 V8에 내장 보호가 없음을 받아들이고 — 패턴 단순 유지, 중첩 quantifier 금지, non-backtracking 구조 선호(JS엔 atomic group이 없지만 (?=(x))\1 lookahead trick으로 흉내). 가능하면 복잡한 정규식을 명시적 문자열 연산으로 대체 — string.includes, string.split, indexOf는 모두 선형 시간이고 무한히 빠릅니다. 기능 미스매치도 중요합니다. Stack Overflow에서 복붙한 PCRE 답이 JavaScript에서 안 도는 경우가 흔함 — PCRE의 가변 폭 lookbehind, possessive quantifier (a++), 재귀 서브루틴 ((?R)), 일부 Unicode 클래스는 PCRE 전용. JavaScript 전용은 d (hasIndices) 플래그와 v (Unicode-Sets) 플래그 (ES2024). 엔진 간 포팅 시 테스트 케이스를 꼭 돌려보세요 — 조용한 의미 차이가 흔합니다.

// PCRE-only that fails in JS:
preg_match('/^(?P>group)$(?<group>foo|bar)/', $s);  // recursion
preg_match('/(?<=\w+)b/', $s);                     // var-width lookbehind

// JavaScript-only:
'abcabc'.matchAll(/(?<x>\w)/dg);  // d flag → result[i].indices
[...'abc'.matchAll(/[\p{Letter}--[a]]/v)]; // v flag set difference

// Cross-engine safe baseline (works everywhere):
const safePattern = /^[a-zA-Z][a-zA-Z0-9_]{0,31}$/;

// Server: use RE2 in Node
const RE2 = require('re2');
const safe = new RE2('^([a-z]+)\\s+(\d+)$');
const m = safe.match('alice 42');
m;  // ['alice 42', 'alice', '42']

// Replace regex with string ops when you can — guaranteed O(n)
const isEmail = (s) => s.includes('@') && s.indexOf('@') === s.lastIndexOf('@');

Lookaround는 zero-width assertion입니다 — 현재 위치 앞·뒤에 무엇이 있는지를 글자를 소비하지 않고 검사합니다. 네 종류 — positive lookahead (?=...), negative lookahead (?!...), positive lookbehind (?<=...), negative lookbehind (?<!...). 강력하지만 자주 오남용됩니다. regex 튜토리얼에서 보는 lookaround의 약 80%는 capture group을 가진 평범한 regex로 다시 쓸 수 있고 그 편이 더 빠르고 읽기 쉽습니다. 정당한 용법은 몇 가지로 나뉩니다. (1) delimiter를 소비하지 않고 토큰화. "abc123def"를 letter/digit으로 쪼개는 /(?<=\D)(?=\d)|(?<=\d)(?=\D)/는 글자/숫자 경계에 split을 넣고 어떤 글자도 소비하지 않아 .split이 ["abc","123","def"]를 돌려줍니다. zero-width가 아닌 regex로 같은 효과를 내려면 명시적 재조립 필요. (2) 매치 범위 밖의 제약 검증. "단위가 따라오는 숫자를 찾되 단위는 매치에 포함하지 마": /\d+(?=px|em|rem)/. lookahead 없이는 단위를 매치에 포함(후처리로 제거)하거나 capture group을 써서 group 1을 참조해야 합니다. lookahead가 더 깔끔합니다. (3) 한 패턴에서 여러 독립 제약 검증. 고전 "패스워드는 숫자·문자·특수문자 포함, 12자 이상" 패턴 — /^(?=.*\d)(?=.*[a-zA-Z])(?=.*[!@#$%])\S{12,}$/. 각 (?=...)이 위치 전진 없이 전체 문자열에 대해 한 규칙을 검사. 작동하고 간결하지만, 여러 개의 분리된 검증이 애플리케이션 코드에서 더 명확한 정전형 사례이기도 합니다. (4) Unicode 안에서 단어 경계. JavaScript \b는 기본 ASCII 한정. Unicode 텍스트에 대해 "글자 경계"를 단언하려면 /(?<![\p{Letter}\p{Mark}])foo(?![\p{Letter}\p{Mark}])/u + u 플래그 필요. 쓰지 말아야 할 때 — capture group으로 충분한 모든 경우. /(\d+)px/를 "12px"에 매치하면 match[1] = "12"가 lookbehind 없이 나옵니다. /(?<=\$)\d+/.exec("$42")[0]을 /\$(\d+)/.exec("$42")[1]로 바꾸세요 — 같은 데이터, 더 단순한 regex, lookbehind가 제한된 엔진을 포함해 모든 엔진에서 작동. 미묘한 성능 함정 — backtracking 엔진에서 quantifier가 적용된 그룹 내부의 lookaround는 worst-case 작업량을 곱셈으로 증가시킬 수 있습니다 — 각 backtrack 단계마다 assertion을 다시 평가. RE2는 lookahead 지원, 임의 lookbehind 미지원. Java는 9에서 bounded lookbehind 추가. Python은 고정 길이 lookbehind만. ECMAScript는 2018부터 lookahead와 무경계 lookbehind 모두 지원이지만 Safari가 lookbehind를 2023년에야 출시 — 구버전 Safari 지원이 필요하면 lookbehind는 보류.

// Tokenize on letter/digit boundary (zero-width split)
'abc123def'.split(/(?<=\D)(?=\d)|(?<=\d)(?=\D)/);
// → ['abc', '123', 'def']

// Match number followed by CSS unit, exclude the unit
const px = '20px 1rem 3em'.match(/\d+(?=px|em|rem)/g);
// → ['20', '1', '3']

// Password rule with lookaheads
/^(?=.*\d)(?=.*[a-z])(?=.*[A-Z])(?=.*[!@#$%^&*])\S{12,}$/.test(pw);

// Lookbehind for dollar amount
'price $42 and €50'.match(/(?<=\$)\d+/);  // ['42']

// SAME RESULT without lookbehind (more portable)
'price $42 and €50'.match(/\$(\d+)/)[1];   // '42'

// AVOID: nested-quantifier-with-lookahead — slow on adversarial input
/^(.+(?=.+))+$/.test('a'.repeat(20) + 'X');  // backtracks badly