정규표현식 엔진은 패턴을 매칭할 때마다 NFA와 DFA 상태기계를 구축하여 실행한다.

Context

정규표현식은 개발자들이 매일 사용하는 텍스트 매칭 도구이지만, 대부분의 엔진이 내부적으로 상태기계를 어떻게 구축하는지 알지 못한다. Thompson이 1968년에 발견한 Thompson's construction은 패턴을 nondeterministic finite automaton (NFA)로 변환한다. NFA는 매 단계마다 여러 경로를 가질 수 있어 powerful하지만 expensive하다.

Technical Solution

• 패턴의 각 문자가 두 개의 상태와 전이로 변환된다
• Concatenation은 상태기계를 순차적으로 연결한다
• Alternation (|)은 epsilon transition으로 분기 경로를 만든다
• Star 연산자는 수락 상태에서 시작 상태로 루프를 추가한다
• subset construction algorithm이 NFA를 DFA로 변환한다

Impact

DFA는 exponentially 더 많은 상태를 가질 수 있지만, 각 단계가 O(1)이다. Backtracking 엔진에서 nested quantifier (a+)+b를 10개 문자열에 매칭하면 약 1,000개 경로를 탐색한다. 20개는 100만 개, 30개는 10억 개 이상으로 폭발한다.

Key Takeaway

정규표현식의 성능 문제는 패턴 설계에서 발생한다. Nested quantifier over overlapping characters는 ReDoS 공격의 원인이 된다.