컴퓨터 프로그램은 종종 "이런 패턴의 문자열을 찾아줘"라고 요청합니다. 예를 들어, "이메일 주소에서 '@' 앞의 이름과 뒤의 도메인이 같은지 확인해 줘" 같은 요청입니다.
기존 방식 (후퇴법, Backtracking): 기존의 검색 프로그램들은 마치 기억력이 좋지만, 실수하면 처음부터 다시 시작하는 사서처럼 행동합니다.
"아, 이 이름이 맞나? 아니야? 그럼 다시 돌아갈게."
"이 도메인이 맞나? 아니야? 다시 돌아갈게."
이렇게 되돌아가서 (Backtrack) 다시 시도하는 과정이 반복되면, 입력된 글자가 조금만 길어져도 사서는 미친 듯이 뛰어다니게 됩니다.
결과: 컴퓨터가 멈추거나 (서비스 거부), 해커가 악의적으로 긴 글자를 보내면 서버가 마비되는 ReDoS(정규식 서비스 거부 공격) 라는 보안 위협이 발생합니다.
2. 새로운 해결책: "집단 기억력"을 가진 사서 (Register Set Automata)
저자들은 이 문제를 해결하기 위해 RSAs (Register Set Automata, 레지스터 세트 오토마타) 라는 새로운 모델을 만들었습니다.
비유: "개별 메모"에서 "집단 메모"로
기존 사서 (Register Automata): 한 번에 하나의 이름만 기억할 수 있는 사서였습니다. "지민이"를 기억하고 있으면 "수진"을 기억하려면 지민이를 잊어야 했습니다.
새로운 사서 (RSAs):여러 사람의 이름을 한 번에 묶어서 (집합으로) 기억할 수 있는 사서입니다.
"지민이, 수진이, 철수이"를 한 번에 한 통장에 적어두고, "지금 들어온 이름이 이 중 하나인가?"라고 한 번에 물어볼 수 있습니다.
만약 "지민이"가 다시 등장하면, "아, 이 통장에 이미 있네!"라고 바로 확인하고 넘어갑니다.
이제 사서는 되돌아가서 다시 시도할 필요가 없습니다. 한 번에 모든 가능성을 통장에 적어두고, 들어오는 글자를 그 통장과 비교하기만 하면 되니까요.
3. 어떻게 작동할까요? (결정론적 자동화)
이 새로운 사서는 결정론적 (Deterministic) 으로 작동합니다.
비유: "만약 A 면 B 로 가고, B 면 C 로 간다"는 식의 명확한 규칙을 따릅니다.
"혹시 A 가 아닐 수도 있나? 그럼 다른 길로 가볼까?"라고 고민하며 헤매는 일이 없습니다.
덕분에 글자 하나를 읽는 데 걸리는 시간이 항상 일정합니다. 글자가 100 개든 100 만 개든, 사서의 작업 속도는 일정하게 유지됩니다.
4. 왜 이것이 중요할까요?
속도: 기존 방식은 글자가 길어질수록 시간이 기하급수적으로 늘어났지만, 이 방식은 글자 수에 비례해서만 선형적으로 증가합니다. (100 배 길어지면 100 배만 느려짐)
보안 (ReDoS 방어): 해커가 서버를 마비시키려고 악의적으로 긴 패턴을 보내도, 이 새로운 사서는 당황하지 않고 일정한 속도로 처리합니다. 서버가 멈추는 것을 막아줍니다.
실용성: 연구자들은 이 이론을 실제로 구현한 프로토타입을 만들었고, 기존 최고의 검색 프로그램들보다 훨씬 안정적으로 작동한다는 것을 증명했습니다.
5. 요약: 한 문장으로 정리
"기존의 텍스트 검색 프로그램이 복잡한 규칙을 만나면 되돌아가며 헤매느라 서버를 멈추게 만들었다면, 이 논문은 '한 번에 모든 가능성을 통장에 적어두고' 깔끔하게 처리하는 새로운 검색 알고리즘을 개발하여, 속도는 빠르고 보안은 튼튼한 검색 시스템을 만들었습니다."
이 기술은 웹 보안, 데이터 검증, 해킹 방지 등 우리가 매일 사용하는 인터넷 서비스의 숨은 영웅이 될 수 있습니다.
1. 문제 정의 (Problem)
배경: 정규식 매칭은 데이터 유효성 검사, 검색, 파싱 등 컴퓨터 과학 전반에서 필수적입니다. 그러나 백레퍼런스 (예: \1, \2 와 같이 이전에 캡처된 그룹을 참조하는 기능) 를 포함한 확장된 정규식은 비정규 언어 (non-regular language) 를 표현할 수 있어 표현력이 강력합니다.
현황: 대부분의 산업용 매커 (PCRE2, Python re, Java regex 등) 는 백레퍼런스를 처리하기 위해 백트래킹 (backtracking) 알고리즘을 사용합니다.
문제점:
성능 저하: 백트래킹은 최악의 경우 입력 길이에 대해 지수 시간 (O(2n)) 이 소요될 수 있습니다.
ReDoS 공격: 악의적인 사용자가 특정 입력을 보내어 서버를 마비시키는 공격이 가능합니다 (예: StackOverflow 2016 년 장애).
현재 솔루션의 한계: RE2 나 HyperScan 과 같은 고속 자동화 기반 매커는 백레퍼런스를 지원하지 않습니다. 이는 백레퍼런스를 지원하는 결정적 자동화 (Deterministic Automata) 모델이 부재하기 때문입니다.
2. 방법론 (Methodology)
저자들은 백레퍼런스를 효율적으로 처리할 수 있는 새로운 이론적 모델인 **레지스터 세트 오토마타 (RSA)**를 도입하고, 이를 기반으로 한 매칭 파이프라인을 설계했습니다.
2.1 레지스터 세트 오토마타 (RSA)
개념: 기존 레지스터 오토마타 (RA) 의 확장입니다.
RA: 각 레지스터가 단일 데이터 값 (symbol) 만 저장.
RSA: 각 레지스터가 **데이터 값의 집합 (Set of symbols)**을 저장할 수 있음.
주요 연산:
입력 값을 레지스터에 추가 (Add).
레지스터 간 병합 (Merge/Union).
레지스터 비우기 (Clear).
레지스터에 특정 값이 존재하는지 테스트 (Membership test).
특징: 무한 알파벳 (infinite alphabet) 을 다루며, 결정적 RSA (DRSA) 는 입력 길이에 대해 선형 (유한 알파벳) 또는 이차 (무한 알파벳) 시간 복잡도로 매칭이 가능합니다.
2.2 변환 알고리즘
정규식 → NRA (비결정적 레지스터 오토마타):
안티미로프 (Antimirov) 의 부분 도함수 (Partial Derivatives) 기법을 사용하여 백레퍼런스가 포함된 정규식을 NRA 로 변환합니다.
이 과정에서 캡처 그룹은 레지스터에, 백레퍼런스는 레지스터 값 테스트로 매핑됩니다.
NRA → DRSA (결정적 레지스터 세트 오토마타):
NRA 결정화 (Determinization) 알고리즘: 비결정적 NRA 를 DRSA 로 변환하는 (반) 알고리즘을 제안합니다.
핵심 기법:
마이크로스테이트 (Macrostate) 추적: 현재 도달 가능한 상태 집합과 레지스터의 크기 클래스 (0, 1, ω) 를 함께 추적하여 부정확성을 관리합니다.
카테시안 오버어프록시메이션 (Cartesian Overapproximation) 방지: 레지스터 간의 의존성 손실을 방지하기 위해 추가적인 검사를 수행합니다.
레지스터 로컬리티 (Register Locality): 상태별 레지스터를 분리하여 충돌을 줄입니다.
카피리스 (Copyless) 조건: 데이터 값이 여러 레지스터에 동시에 복사되지 않도록 정규식을 전처리합니다.
2.3 매칭 복잡도
DRSA 기반 매칭:
유한 알파벳: 입력 길이 O(∣w∣)에 비례하는 선형 시간.
무한 알파벳: 입력 길이 O(∣w∣2)에 비례하는 이차 시간.
이는 백트래킹의 지수 시간 복잡도와 대조적으로 매우 예측 가능하고 안정적입니다.
3. 주요 기여 (Key Contributions)
새로운 모델 제안 (RSA): 레지스터에 집합을 저장하는 자동화 모델을 정의하고, 이론적 성질 (닫힘 성질, 결정성 등) 을 분석했습니다.
결정화 알고리즘: 백레퍼런스가 포함된 정규식의 상당 부분 (단일 문자 캡처 그룹을 가진 경우 등) 을 DRSA 로 변환하는 (반) 알고리즘을 개발했습니다.
이론적 분석:
RSA 의 **공백 문제 (Emptiness Problem)**가 결정 가능하지만, 그 복잡도가 Fω (Ackermannian) 클래스에 속함을 증명했습니다.
RA 와 RSA 의 표현력 비교 및 다른 데이터 오토마타 모델 (History-Register Automata 등) 과의 관계를 규명했습니다.
실용적 구현 및 검증:
Python 기반 프로토타입 매커 (rsamatch) 를 구현했습니다.
실제 세계의 백레퍼런스 정규식 벤치마크 (Lingua Franca, Rengar) 를 사용하여 기존 매커 (grep, pcre2, Python re 등) 와 비교 실험을 수행했습니다.
4. 실험 결과 (Results)
ReDoS 취약성 해결:
기존 백트래킹 매커들은 공격 벡터 입력에서 수 초에서 100 초 이상의 타임아웃을 기록하거나, 수만 단계의 백트래킹을 수행했습니다.
반면, 제안된 rsamatch 는 대부분의 경우 1 초 미만 (대부분 0.1~0.3 초) 에 매칭을 완료했습니다.
표준 편차가 매우 낮아 성능 예측이 매우 안정적입니다.
적용 범위:
수집된 12,046 개의 정규식 중 단일 문자 백레퍼런스를 가진 3,299 개 중 **91%**에서 DRSA 변환에 성공했습니다.
ReDoS 공격에 취약한 1,335 개의 정규식 중 94% (1,246 개) 에서 성공적으로 매칭을 수행했습니다.
성능 비교:rsamatch 는 프로토타입 (Python) 이지만, C/C++ 로 구현된 기존 매커들보다 ReDoS 공격 시나리오에서 훨씬 더 강력하고 예측 가능한 성능을 보였습니다.
5. 의의 및 결론 (Significance)
이론적 기여: 백레퍼런스를 포함하는 정규식 매칭에 대한 결정적 자동화 모델의 부재를 해결하고, 데이터 오토마타 이론에 새로운 모델 (RSA) 을 추가했습니다.
실무적 기여: ReDoS 공격으로부터 시스템을 보호할 수 있는 예측 가능한 성능의 정규식 매커를 제공합니다. 이는 웹 보안, 네트워크 침입 탐지 시스템 (NIDS), 데이터 유효성 검사 등 실시간 성능이 중요한 분야에서 백레퍼런스를 안전하게 사용할 수 있는 길을 엽니다.
향후 과제: 결정화 알고리즘의 성공률을 높이고 (더 복잡한 정규식 처리), 더 효율적인 언어 (C/C++) 로의 구현 및 상용화를 목표로 합니다.
요약하자면, 이 논문은 백트래킹의 비효율성과 보안 위험을 제거하기 위해 레지스터에 집합을 저장하는 새로운 자동화 모델 (RSA) 을 개발하고, 이를 통해 백레퍼런스가 포함된 정규식을 선형/이차 시간 내에 안정적으로 매칭할 수 있음을 증명했습니다.