이 논문은 **"정규식 엔진 (Regular Expression Engines) 을 어떻게 더 똑똑하고 안전하게 테스트할 것인가?"**에 대한 새로운 접근법을 소개합니다.
정규식은 우리가 매일 쓰는 프로그램에서 텍스트를 검색하거나 데이터를 추출할 때 사용하는 '복잡한 검색 규칙'입니다. 이 규칙들을 해석해주는 프로그램이 바로 '정규식 엔진'인데, 이 엔진에 버그가 있으면 보안 사고나 시스템 오류가 발생할 수 있습니다.
저자들은 기존의 테스트 방식이 너무 비효율적이고 위험하다고 지적하며, **'ReTest'**라는 새로운 테스트 도구를 개발했다고 말합니다.
이 내용을 쉽게 이해할 수 있도록 세 가지 핵심 비유로 설명해 드릴게요.
1. 문제: 왜 기존 테스트는 실패할까?
비유: "서로 다른 언어를 쓰는 번역기들"
현재의 상황: 정규식 엔진은 여러 종류가 있습니다. (파이썬용, 자바용, C++ 용 등). 마치 서로 다른 나라의 번역기들처럼, 각기 다른 규칙 (방언) 을 따릅니다.
기존 테스트 1 (차이점 비교): 개발자들은 "A 엔진과 B 엔진의 결과가 달라!"라고 하면 버그라고 의심합니다. 하지만 이건 잘못된 의심일 수 있습니다. A 와 B 는 원래 규칙이 조금 다를 수 있으니까요. (예: "빨간색"을 A 는 '진한 빨강'으로, B 는 '연한 빨강'으로 해석할 수 있는데, 둘 다 맞는 해석일 수 있음). 그래서 진짜 버그를 찾아내지 못하고 헛수고를 합니다.
기존 테스트 2 (무작위 입력): 엔진에 무작위 문자를 쑤셔 넣는 '후킹 (Fuzzing)'을 합니다. 하지만 이건 마치 아기에게 복잡한 수학 문제를 풀게 하려고 무작위로 숫자를 던지는 것과 같습니다. 대부분의 입력이 문법적으로 틀려서 (예: "a+b*" 대신 "a+b*!" 같은 이상한 것) 엔진이 아예 읽지도 않고 거절해버립니다. 진짜 복잡한 로직을 테스트할 기회를 주지 못합니다.
2. 해결책: ReTest 의 두 가지 무기
저자들은 이 문제를 해결하기 위해 두 가지 똑똑한 전략을 결합했습니다.
무기 1: 문법을 아는 '스마트 시뮬레이터' (Grammar-aware Fuzzing)
비유: "전문 요리사가 레시피를 보고 재료를 섞는 것"
기존의 무작위 입력은 아기가 장난치는 수준이라면, ReTest 는 전문 요리사입니다.
이 도구는 정규식의 '문법 (규칙)'을 완벽하게 이해하고 있습니다. 그래서 "이런 구조의 레시피라면, 저런 재료를 넣어도 요리가 망가지지 않겠지?"라고 생각하며 문법적으로 완벽한 입력을 만들어냅니다.
덕분에 엔진이 실제로 데이터를 처리하는 '내부 조리 과정 (매칭 로직)'을 깊게 파고들 수 있게 되어, 숨겨진 버그를 찾아낼 확률이 3 배나 높아졌습니다.
무기 2: 외부 기준 없이 스스로를 검증하는 '거울' (Metamorphic Testing)
비유: "다른 사람과 비교하지 않고, 스스로의 논리 일관성을 확인하는 거울"
다른 엔진과 비교하면 (차이점 비교) 언어 차이 때문에 오해가 생깁니다. 대신 ReTest 는 한 엔진 안에서 "이 규칙을 변형해도 결과는 논리적으로 같아야 해"라고 스스로를 검증합니다.
예시: "A 와 B 를 합친 것"과 "B 와 A 를 합친 것"은 결과가 같아야 합니다 (교환법칙). 혹은 "A 를 반복하는 것"과 "A 를 반복한 것을 다시 반복하는 것"도 같아야 합니다.
이 **수학적 법칙 (대수학)**을 이용해, 다른 엔진의 도움 없이도 "이 엔진이 논리적으로 모순이 있나?"를 스스로 찾아냅니다.
3. 성과: 실제로 무엇을 찾았나요?
실험 결과: ReTest 를 유명한 엔진 (PCRE) 에 적용해 보니, 기존 방법보다 3 배 더 많은 코드 경로를 테스트했습니다.
버그 발견: 기존에는 발견되지 않았던 **3 개의 심각한 보안 버그 (메모리 손상 등)**를 찾아냈습니다. 이는 마치 건물의 숨겨진 균열을 찾아내어 붕괴를 막는 것과 같습니다.
요약: 이 논문이 우리에게 주는 메시지
지금까지 정규식 엔진을 테스트하는 것은 "서로 다른 말투를 가진 사람들과 비교하거나, 무작위로 돌을 던져보는" 수준이었습니다.
하지만 저자들은 **"문법을 아는 전문가가 만들어낸 완벽한 테스트 케이스"**와 **"스스로의 논리 일관성을 검증하는 거울"**을 결합하여, 엔진이 얼마나 튼튼한지 시스템적으로 검증하는 방법을 만들었습니다.
이는 소프트웨어의 안전성을 높이고, 우리가 매일 사용하는 프로그램에서 발생할 수 있는 치명적인 오류를 미리 막아주는 중요한 발전입니다.
1. 문제 정의 (Problem)
소프트웨어 공학에서 정규식 (Regex) 은 패턴 매칭, 입력 유효성 검사, 텍스트 처리 등에 필수적으로 사용되며, 이를 구현하는 정규식 엔진 (예: Python 의 re, PCRE, RE2 등) 은 핵심 인프라입니다. 그러나 이러한 엔진들은 버그와 보안 취약점을 포함할 수 있습니다. 현재 정규식 엔진 테스트에는 다음과 같은 근본적인 한계가 존재합니다.
차별적 테스트 (Differential Testing) 의 한계: 서로 다른 엔진 간 출력을 비교하는 방식은 널리 쓰이지만, 정규식 문법과 의미론 (Semantics) 이 엔진마다 (POSIX vs PCRE 등) 상이하여 거짓 양성 (False Positives) 이 빈번하게 발생합니다. 이는 실제 버그가 아닌 의도된 문법 차이를 버그로 오인하게 만듭니다.
기존 페이징 (Fuzzing) 의 비효율성: 기존 페이징은 대부분 바이트 단위의 무작위 변형을 사용합니다. 이는 문법적으로 유효하지 않은 입력을 생성하여 파싱 단계에서 바로 거절당하게 하므로, 엔진의 핵심인 매칭 로직 (Matching Logic) 을 충분히 테스트하지 못합니다.
오라클 문제 (Oracle Problem): 정규식 엔진의 올바른 출력을 판단할 수 있는 보편적인 기준 (Semantic Oracle) 이 부재하여, 버그를 자동으로 식별하기 어렵습니다.
2. 방법론 (Methodology: ReTest Framework)
저자들은 이러한 문제를 해결하기 위해 ReTest라는 체계적인 테스트 프레임워크를 제안합니다. ReTest 는 문법 인식 페이징 (Grammar-aware Fuzzing) 과 변형 테스트 (Metamorphic Testing) 를 결합한 하이브리드 접근법을 사용합니다.
가. 문법 인식 페이징 (Grammar-aware Fuzzing)
입력 생성: 무작위 바이트 변형 대신, 실제 소프트웨어에서 추출된 50 만 개 이상의 정규식 패턴 코퍼스를 시드 (Seed) 로 사용합니다.
구조적 변형: 정규식을 추상 구문 트리 (AST) 로 파싱한 후, 문법적으로 유효한 하위 트리 (Subtree) 를 학습된 풀 (Pool) 에서 선택하여 교체하는 방식으로 변형을 수행합니다.
커버리지 유도: 엔진의 에지 (Edge) 커버리지를 추적하여 새로운 코드 경로를 탐색하는 입력을 유도합니다.
나. 변형 테스트 (Metamorphic Testing)
오라클 해결: 엔진 간 비교 대신, 단일 엔진 내부에서 정의된 대수적 속성 (Kleene Algebra 기반) 을 검증합니다.
변형 관계 (Metamorphic Relations, MRs): 정규식의 대수적 법칙 (예: r∗≡(r∗)∗) 을 기반으로, 입력 패턴을 변형했을 때 매칭 결과가 동일해야 한다는 관계를 정의합니다.
효과: 문법 (Dialect) 에 상관없이 모든 정규식 엔진이 만족해야 하는 수학적 속성을 검증함으로써, 문법 차이에 의한 오차를 제거하고 의미론적 버그를 탐지합니다.
다. 안전성 오라클 (Safety Oracles)
메모리 안전성 위반 (버퍼 오버플로우, Use-after-free 등) 을 탐지하기 위해 AddressSanitizer (ASan), MemorySanitizer (MSan), UndefinedBehaviorSanitizer (UBSan) 를 통합하여 크래시 (Crash) 를 감지합니다.
3. 주요 기여 (Key Contributions)
실무 테스트 관행 조사 (Empirical Study): 22 개의 주요 정규식 엔진을 조사하여 현재 82% 의 버그가 사용자 보고에 의존하며, 문법 인식 페이징을 사용하는 엔진은 2 개 (Irregexp, Rust regex) 에 불과함을 규명했습니다.
버그 및 CVE 분석: 1,007 개의 버그와 156 개의 CVE 를 분석한 결과, 의미론적 버그 (35%) 와 메모리 안전성 취약점 (CVE 의 52%) 이 주된 문제임을 발견했습니다.
ReTest 프레임워크 설계: 문법 인식 페이징과 Kleene Algebra 기반의 16 가지 변형 관계 (Metamorphic Relations) 를 통합한 테스트 프레임워크를 설계하고 프로토타입을 구현했습니다.
변형 관계 카탈로그: 문법 (Dialect) 에 독립적인 16 가지 변형 관계를 정리하여 의미론적 버그 탐지를 위한 오라클을 제공했습니다.
4. 평가 결과 (Results)
PCRE v8.45 엔진을 대상으로 한 예비 평가 결과는 다음과 같습니다.
커버리지 향상: ReTest 는 기존 페이징 방식 (Naive Fuzzing, V8-style Grammar Fuzzing) 대비 3 배 높은 에지 커버리지 (40.12% vs ~12%) 를 달성했습니다.
기존 방식은 초기 커버리지가 낮고 성장이 더딘 반면, ReTest 는 코퍼스를 시드로 사용하여 초기 커버리지가 높고 문맥 인식 변형으로 추가 커버리지를 확보했습니다.
새로운 버그 발견: ReTest 는 PCRE 에서 3 개의 새로운 메모리 안전성 버그 (Heap corruption, Buffer overflow) 를 발견했습니다.
발견된 버그는 UTF-8 모드에서의 이스케이프 시퀀스 처리, 제로 양화자 (Zero-quantified) 재귀 등 특정 조건에서 발생하며, 기존 페이징 방식으로는 발견되지 않았습니다.
효율성: ReTest 는 약 4 만 회 반복으로 3 개의 버그를 발견한 반면, Naive Fuzzing 은 1 억 5 천만 회 이상 반복해도 버그를 찾지 못했습니다.
5. 의의 및 결론 (Significance)
이 연구는 정규식 엔진 테스트 분야에서 다음과 같은 중요한 의의를 가집니다.
표준 부재 문제 해결: 서로 다른 문법 (Dialect) 을 가진 엔진 간 비교 없이도, 수학적 속성 (Kleene Algebra) 을 통해 단일 엔진의 정확성을 검증할 수 있는 문법 독립적 오라클을 제시했습니다.
체계적 테스트 방법론 정립: 무작위 페이징의 한계를 극복하고, 구조적 문법 지식을 활용한 체계적인 테스트 방법론을 제안하여, 엔진 개발자가 수동 테스트에 의존하지 않고도 버그를 식별할 수 있는 기반을 마련했습니다.
보안 및 신뢰성 강화: 메모리 안전성 취약점과 의미론적 오류를 동시에 탐지하여, 정규식 엔진의 신뢰성을 높이고 ReDoS(Regular Expression Denial of Service) 및 기타 보안 위협을 예방하는 데 기여합니다.
저자들은 향후 16 가지 변형 관계를 확장 (E-regex 지원) 하고, 22 개 엔진 전체에 대한 대규모 평가를 수행하여 이 방법론의 보편성을 입증할 계획입니다.