50년간 아무도 고치지 않은 정규표현식의 이차 복잡도 문제...새 엔진 RE#이 해결책 제시

[한국정보기술신문] 정규표현식(Regex)은 텍스트 검색, 데이터 추출, 로그 분석 등 소프트웨어 개발 전반에 걸쳐 광범위하게 사용되는 핵심 기술이다. 그런데 RE2, Go의 regexp, Rust의 regex 크레이트, .NET의 NonBacktracking 모드 등 선형 시간(Linear Time)을 보장한다고 홍보하는 모든 정규표현식 엔진이 실은 공통된 결함을 지니고 있다는 사실이 재조명받고 있다. 해당 엔진들의 선형 시간 보장은 단일 매칭 한 건에만 해당하며, 문서 전체에서 모든 매칭을 찾는 순간 이 보장은 사라진다.

이 문제를 정면으로 다룬 것은 개발자 이안 에릭 바라탈루(Ian Erik Varatalu)다. 그는 2026년 3월 16일 공개한 기술 블로그 글에서 문제의 원인과 구조를 상세히 분석하고, 자신이 개발한 정규표현식 엔진 RE#을 통해 해결책을 제시했다.

문제의 메커니즘은 단순하다. 예를 들어 .*a|b라는 패턴을 n개의 'b'로 이루어진 문자열에 적용한다고 가정하자. 엔진은 각 위치에서 먼저 .*a 분기를 시도한다. 이때 나머지 문자열 전체를 훑으며 'a'를 찾지만 결국 실패하고, 그다음 'b' 분기로 문자 하나를 매칭한 뒤 다음 위치로 이동해 이 과정을 반복한다. 결과적으로 n + (n-1) + (n-2) + … 의 삼각급수 형태로 작업량이 쌓여 O(n²)의 복잡도가 발생한다. 입력 크기가 100배 늘어나도 처리 시간이 100배가 아닌 만 배 가까이 늘어날 수 있다는 뜻이다.

Rust regex 크레이트 공식 문서는 이 사실을 솔직하게 명시하고 있다. 문서에는 반복자의 최악 시간 복잡도가 O(m × n²)이며, 패턴과 입력 문자열이 모두 신뢰할 수 없는 출처에서 온 경우 이차 복잡도에 노출될 수 있고 이를 완전히 피할 방법은 없다고 적혀 있다. 이 문제는 1970년대부터 존재해 왔으며, Russ Cox가 2009년에 이미 지적한 바 있고, BurntSushi의 벤치마크 모음 rebar를 통해 RE2, Go, Rust 전반에서 실증적으로 확인된 바 있다.

이차 복잡도 문제에 앞서, 역추적 방식의 정규표현식 엔진이 초래하는 지수적 복잡도 문제도 여전히 현실적인 위협이다. 켄 톰프슨은 이를 방지하는 NFA 구성 방법을 1968년에 이미 발표했지만, 역추적 방식은 대부분의 정규표현식 엔진에서 지금도 기본값으로 사용되고 있다.

대표적인 사례가 npm의 glob 매칭 라이브러리 minimatch다. npm 창시자가 작성한 이 라이브러리는 주당 3억 5천만 회 이상 다운로드되며, 역추적으로 인한 ReDoS(정규표현식 서비스 거부) 취약점으로 다섯 건의 CVE를 기록했다. 현재 minimatch의 공식 문서에는 사용자 입력을 정규표현식 패턴의 출처로 삼으면 보안 사고로 이어질 수 있다는 경고가 굵은 글씨로 명시돼 있으며, 이후 ReDoS 신고는 의도된 동작으로 간주하겠다는 입장도 밝히고 있다.

1975년에 등장한 아호-코라식(Aho-Corasick) 알고리즘은 고정 문자열 집합에 대해 선형 시간 전체 매칭을 보장한다. 트라이와 실패 링크를 활용해 입력을 한 번만 훑으며 모든 매칭을 찾아낸다. 그러나 이 알고리즘은 패턴 길이가 미리 정해진 고정 문자열에만 적용 가능하며, 일반 정규표현식에는 사용할 수 없다.

인텔이 개발한 Hyperscan과 그 파생 프로젝트 Vectorscan은 진정한 선형 시간 전체 매칭을 구현했지만, '가장 이른 매칭(Earliest Match)' 방식을 채택해 결과의 의미가 달라진다. 패턴 a+를 aaaa에 적용하면 일반적으로는 전체를 하나의 매칭으로 보지만, Hyperscan은 각 'a'를 별개의 매칭으로 보고한다. 이는 네트워크 침입 탐지처럼 매칭 여부만 확인하면 되는 용도에는 적합하지만, 텍스트 편집기나 데이터 추출처럼 가장 길고 왼쪽 우선인 매칭이 필요한 일반 용도에는 맞지 않는다.

RE#은 역방향 DFA와 순방향 DFA를 각각 한 번씩만 실행하는 2패스 방식으로 이 문제를 해결한다. 먼저 역방향 DFA가 매칭이 시작될 수 있는 위치를 표시하고, 이후 순방향 DFA가 각 후보 위치에서 가장 긴 매칭을 확정한다. 이 방식은 매칭을 위치마다 재시작하지 않으므로 매칭 수에 관계없이 항상 두 번의 패스만으로 완료된다. 결과는 기존 엔진과 동일한 최좌측-최장(Leftmost-Longest, POSIX) 의미론을 따르기 때문에 사용자가 기대하는 방식으로 동작한다.

바라탈루는 여기서 한 발 더 나아가 '강화 모드(Hardened Mode)'도 제공한다. 강화 모드에서는 순방향 패스 역시 O(n × S) 방식으로 처리해, 악의적인 패턴이 주어지더라도 이차 복잡도가 발생하지 않는다. 벤치마크에 따르면 입력 크기 5만 자 기준으로 일반 모드가 1.8초 걸리는 작업을 강화 모드는 1.6밀리초 만에 처리해 약 1,100배 이상의 속도 차이를 보였다.

다만 강화 모드는 일반 입력에서 패턴에 따라 3~9배 느리기 때문에 기본값으로 설정되지는 않았다. 강화 모드는 인터넷에서 패턴을 입력받는 등 신뢰할 수 없는 환경에서 명시적으로 활성화하는 방식을 채택했다.

RE#은 Rust의 regex 크레이트 및 아호-코라식 알고리즘과의 성능 비교에서도 경쟁력을 입증했다. rebar 벤치마크 기준으로 영문 리터럴 검색에서 34.8 GB/s를 기록해 regex의 33.7 GB/s를 소폭 앞섰으며, 영문 대소문자 무시 리터럴 검색에서는 17.1 GB/s 대 9.7 GB/s로 크게 앞섰다. 2663개 단어를 패턴으로 한 사전 검색에서는 627 MiB/s를 기록해 아호-코라식(155 MiB/s)과 regex(535 MiB/s)를 모두 앞섰다. 두 번의 패스를 수행함에도 더 빠른 이유는, RE#의 파생 기반 DFA가 더 적은 상태를 가져 캐시 효율이 높기 때문이라고 저자는 설명했다.

RE#은 현재 캡처 그룹 미지원, 지연 수량자(Lazy Quantifier) 미지원 등의 제약이 있으며 스트리밍 인터페이스도 아직 개발 중이다. 바라탈루는 RE#을 활용한 grep 도구 re도 함께 공개했으며, 관련 논문이 프로그래밍 언어 분야 최우수 국제 학술대회인 PLDI에 조건부 수락된 상태라고 밝혔다.