시니어 엔지니어라면 누구나 한 번쯤 정규표현식(Regex) 때문에 프로덕션 서버 CPU 사용률이 100%를 치고 장애가 발생하는 아찔한 경험을 해본 적이 있을 겁니다. 우리는 이를 ReDoS(Regular Expression Denial of Service)라고 부릅니다. 이런 문제를 겪고 나면 자연스럽게 백트래킹(Backtracking)을 피하기 위해 구글의 RE2, Go의 regexp, 혹은 Rust의 regex 크레이트 같은 선형 시간(Linear time) 보장 엔진으로 갈아타게 됩니다.

하지만 제가 오늘 다룰 주제는 조금 다릅니다. 이른바 ‘안전하다’고 믿었던 선형 시간 보장 엔진들조차, 모든 매치 찾기(Find All) 를 호출하는 순간 그 보장이 깨진다는 사실을 알고 계셨나요?

최근 해커뉴스에서 뜨거운 논쟁을 불러일으킨 iev.ee의 블로그 글을 읽으며, 15년 넘게 백엔드 시스템을 설계해 온 저조차도 무릎을 쳤습니다. 1970년대부터 존재해 온, 하지만 학계와 업계 모두가 암묵적으로 눈감아왔던 정규식 엔진의 O(n²) 문제와 이를 혁신적인 아키텍처로 해결한 RE# 엔진에 대해 깊게 파헤쳐 보겠습니다.

50년 동안 방치된 O(n²)의 덫

대부분의 정규식 엔진이 단일 매치에 대해서는 O(n)을 보장합니다. 하지만 find_iter나 FindAll을 호출하는 순간 이야기가 달라집니다. Rust의 regex 크레이트 공식 문서만이 유일하게 이 사실을 정직하게 명시하고 있습니다.

“반복자(iterators)의 최악의 경우 시간 복잡도는 O(m * n²)입니다. […] 패턴과 검색 대상이 모두 신뢰할 수 없고 모든 매치를 반복 검색하는 경우, 최악의 2차 시간 복잡도에 취약해집니다. 이를 피할 방법은 없습니다.”

이게 정확히 무슨 뜻일까요? 아주 간단한 예를 들어보겠습니다. 패턴 .*a|b를 bbbbbbbbbb라는 문자열에 매칭한다고 가정해 보죠.

1. 첫 번째 위치에서 엔진은 먼저 .*a를 시도합니다. 끝까지 스캔하지만 a가 없으므로 실패합니다.
2. 그런 다음 b 분기를 타서 문자 하나를 매치합니다.
3. 위치를 한 칸 이동하고 다시 1번부터 반복합니다.

전체 문자열의 길이가 n일 때, 엔진은 n + (n-1) + (n-2) + … 번의 스캔을 수행합니다. 전형적인 삼각수 형태의 O(n²) 작업입니다. 단일 매치를 찾는 데 1초가 걸렸다면, 100배 큰 문서에서 모든 매치를 찾는 데 100초가 아니라 3시간이 걸릴 수 있다는 뜻입니다.

저자는 학계 논문들이 정규식을 단순히 ‘매치 여부(Yes/No)‘를 묻는 문제로 축소해버린 것을 원인으로 지적합니다. 이론적으로는 깔끔하지만, 실무에서 우리가 정규식을 쓰는 이유는 매치의 위치 와 길이, 그리고 전체 목록 을 얻기 위해서입니다. 저 역시 이 지적에 100% 공감합니다. 이론과 실무의 괴리가 만들어낸 거대한 사각지대였던 셈이죠.

백트래킹의 망령과 Aho-Corasick의 한계

물론 이 O(n²) 문제는 고전적인 백트래킹 엔진이 유발하는 지수 시간(Exponential time) 폭발에 비하면 양반입니다. npm에서 주당 3억 5천만 번 다운로드되는 minimatch 라이브러리가 5번이나 ReDoS CVE 취약점을 맞은 것을 보면 알 수 있습니다.

고정된 문자열(Fixed strings)에 대해서는 1975년에 나온 Aho-Corasick 알고리즘이 이미 이 문제를 O(n)으로 해결했습니다. Trie 구조와 실패 링크(Failure links)를 통해 단 한 번의 스캔으로 모든 매치를 찾아냅니다. 매치 길이가 고정되어 있어 어디서 끝나는지 모호함이 없기 때문입니다.

하지만 가변 길이를 가진 정규표현식 에서는 이 방식이 통하지 않습니다. Hyperscan 같은 엔진은 ‘가장 빠른 매치(Earliest match)’ 시맨틱을 도입하여 선형 시간을 달성했지만, 이는 우리가 흔히 기대하는 POSIX 표준의 ‘가장 왼쪽의 가장 긴 매치(Leftmost-longest)’ 결과를 왜곡합니다. a+로 aaaa를 검색할 때 4개의 짧은 매치를 반환하는 식이죠. 네트워크 침입 탐지(NIDS)에는 적합할지 몰라도, 일반적인 grep이나 에디터 검색용으로는 낙제점입니다.

RE#의 해결책: 발상의 전환을 이룬 Two-Pass 아키텍처

여기서 RE# 엔진이 등장합니다. RE#은 시맨틱을 타협하지 않고 모든 매치를 선형 시간에 가까운 성능으로 찾아내는 최초의 범용 정규식 엔진입니다. 핵심은 두 번의 스캔(Two passes) 입니다.

단일 패스로 매번 재시작하는 대신, 전체 입력에 대해 다음 두 단계를 거칩니다.

1. 역방향 스캔(Reverse DFA): 문자열의 뒤에서부터 앞으로 스캔하며 매치가 시작될 수 있는 유효한 위치들을 마킹합니다.
2. 순방향 스캔(Forward DFA): 앞에서부터 스캔하며 마킹된 위치에서 가장 긴 매치를 확정합니다.

처음 이 아키텍처를 접했을 때, “전체 문자열을 두 번이나 훑으면 Throughput이 박살 나지 않을까?” 하는 강한 의구심이 들었습니다. 하지만 벤치마크 결과는 제 예상을 완전히 빗나갔습니다.

놀라운 캐시 지역성(Cache Locality)

2663개의 단어 사전을 900KB의 영문 산문과 매칭하는 벤치마크(Aho-Corasick이 가장 유리한 환경)에서 RE#은 놀라운 결과를 보여줍니다.

benchmark	resharp	resharp (hardened)	rust/regex	aho-corasick
dictionary 2663 words (~15 matches)	627 MiB/s	163 MiB/s (3.85x)	535 MiB/s (1.17x)	155 MiB/s (4.05x)

한 번만 스캔하는 Aho-Corasick보다 두 번 스캔하는 RE#이 4배나 더 빠릅니다. 이유는 바로 캐시 지역성 에 있습니다. Aho-Corasick은 거대한 DFA를 미리 구축하기 때문에 상태 전환 시 L1 캐시 미스와 브랜치 예측 실패가 빈번하게 발생합니다. 반면 RE#의 미분(Derivative) 기반 DFA는 지연 평가(Lazy) 방식으로 구축되어 상태 공간이 훨씬 작고 캐시 적중률이 압도적으로 높습니다. 메모리 대역폭과 CPU 캐시 구조를 완벽하게 이해하고 설계한 결과물입니다.

Hardened Mode: 타협 없는 보안

물론 순방향 패스 자체도 악의적인 패턴에서는 여전히 2차 시간 복잡도를 가질 수 있습니다. 이를 원천 차단하기 위해 RE#은 hardened 모드를 제공합니다. 활성화된 DFA 상태 수(S)에 비례하는 O(n * S) 단일 패스 스캔으로 모든 종료 지점을 확정합니다.

let re = Regex::with_options(
    pattern,
    EngineOptions::default().hardened(true)
)?;

이 모드를 켜면 병적인 입력 데이터(50,000자)에서 기존 대비 1,125배 의 속도 향상을 보여줍니다. 하지만 일반적인 텍스트에서는 3~20배의 성능 저하(Overhead)가 발생합니다.

저자가 이 Hardened 모드를 기본값으로 두지 않은 것은 매우 훌륭한 엔지니어링 판단이라고 생각합니다. 대부분의 실무 정규식(예: [A-Z][a-z]+)은 명확한 경계를 가지고 있어 O(n²) 폭발이 일어날 수 없습니다. 발생하지도 않을 엣지 케이스를 위해 모든 정상 트래픽에 20% 이상의 페널티를 부과하는 것은 어리석은 짓입니다. 사용자 입력을 직접 정규식 패턴으로 받아야 하는 특수한 보안 요구사항(Public API 등)이 있을 때만 명시적으로 Opt-in 하도록 만든 설계 철학에 박수를 보냅니다.

해커뉴스 커뮤니티의 반응과 현실적인 한계

해커뉴스 스레드에서는 이 접근법의 실용성에 대해 열띤 토론이 벌어졌습니다. 누군가는 “실무에서 로그를 뒤질 때는 경계가 명확한 정규식을 쓰기 때문에 문제가 안 된다”고 지적했고, 파이썬의 \d+\s+ 검색에서 발생하는 유사한 O(n²) 문제와 Lookbehind를 활용한 우회 기법도 공유되었습니다.

무엇보다 우리가 짚고 넘어가야 할 RE#의 치명적인 한계가 있습니다.

• 캡처 그룹(Capture Groups) 부재: 현재 RE#은 매치의 시작과 끝 경계만 반환합니다. 실무에서 정규식을 쓰는 가장 큰 이유 중 하나가 특정 서브 그룹을 추출하는 것인데, 이 기능이 없다는 것은 꽤 뼈아픕니다. 저자는 잘못된 추상화를 피하기 위해 설계를 고민 중이라고 하지만, 프로덕션 도입을 망설이게 하는 가장 큰 허들입니다.
• 게으른 수량자(Lazy Quantifiers) 미지원: .*? 같은 패턴을 지원하지 않습니다. 엄격한 POSIX 시맨틱을 따르기 때문입니다.

결론: 패러다임의 전환, 하지만 아직은 얼리어답터용

RE# 엔진은 정규표현식을 ‘언제 터질지 모르는 블랙박스’에서 ‘성능 예측이 가능한 안정적인 도구’로 끌어올리려는 야심 찬 프로젝트입니다. 백트래킹을 버리고, Two-Pass 아키텍처를 도입하고, SIMD(AVX2, NEON)를 활용한 스킵 가속까지 곁들여 Rust 생태계의 기존 강자들을 위협하고 있습니다.

하지만 당장 내일 여러분의 프로덕션 코드에 있는 regex 크레이트를 RE#으로 교체해야 할까요? 제 대답은 “아직은 아니다” 입니다. 캡처 그룹의 부재는 실무에서 너무 큰 제약이며, 아직 1.0 정식 릴리스 전입니다.

그럼에도 불구하고 RE#이 제시한 아키텍처는 정규식 엔진의 미래를 보여주는 훌륭한 청사진입니다. 만약 여러분의 시스템이 외부 사용자가 입력한 정규식을 실행해야 하는 멀티테넌트 환경이거나, 테라바이트 단위의 로그에서 복잡한 불리언(Boolean) 연산 검색을 수행해야 한다면 RE#은 그 어떤 엔진보다 훌륭한 무기가 될 것입니다.