💻 computer science

PUFFERDOS: Efficient and Effective Attack String Generation for Regular Expression Denial of Service Vulnerabilities

이 논문은 세 가지 형식적으로 검증된 취약 패턴을 기반으로 입력을 합성하고, 현실적인 길이 예산 내에서 실제 환경에서의 실행 가능성을 보장하기 위해 구성적 심볼릭 실행(compositional concolic execution)을 통해 이를 정제함으로써 실용적이고 효과적인 ReDoS 공격 문자열을 생성하는 새로운 도구인 PUFFERDOS를 소개한다.

원저자: Shangzhi Xu, Ziqi Ding, Xiao Cheng, Yuekang Li, Nan Sun, Benjamin Turnbull, Shuangxiang Kan, Siqi Ma

게시일 2026-06-19

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Shangzhi Xu, Ziqi Ding, Xiao Cheng, Yuekang Li, Nan Sun, Benjamin Turnbull, Shuangxiang Kan, Siqi Ma

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신에게 아주 똑똑하지만 약간 집요한 보안 요원이 건물 입구에 있다고 상상해 보세요. 이 요원의 업무는 당신의 신분증(입력값)이 특정 패턴(정규 표현식 또는 "regex")과 일치하는지 확인하는 것입니다. 보통은 이 과정이 빠르고 쉽습니다.

하지만 함정이 있습니다. 만약 당신이 매우 특정한, 혼란스러운 신분증을 건네준다면, 요원의 뇌는 루프(loop)에 빠져 갇혀버리게 됩니다. 그들은 당신의 신분증이 패턴과 일치할 수 있는 모든 가능한 방식을 반복해서, 계속해서 확인하기 시작하며, 결국 에너지가 바닥나서 쓰러지게 됩니다. 이것을 ReDoS 공격(정규 표현식 서비스 거부 공격)이라고 부릅니다. 이는 계산기가 무한히 수학 문제를 풀게 만들어 시스템을 멈추게 하는 것과 같습니다.

오랫동안 보안 연구자들은 이러한 함정을 찾아내고, 그 패턴이 깨졌음을 증명할 "테스트용 신분증"을 만들기 위해 노력해 왔습니다. 하지만 기존 방식에는 두 가지 큰 문제가 있었습니다:

신분증이 너무 길었습니다: 실제 웹사이트에서는 절대 받아들이지 않을 정도로 거대한 입력값(예: 책 한 권 분량의 텍젝트)이 필요했습니다.
건물 구조를 고려하지 않았습니다: 그들은 메인 문에 도달하기 전에 다른 경비원(필터)들이 당신의 신분증을 차단할 수도 있다는 사실을 무시한 채, 보안 요원을 고립된 상태에서 테스트했습니다.

여기에 PUFFERDOS가 등장합니다. PUFFERDOS를 단순히 자물쇠를 따는 것이 아니라, 가장 짧고 효율적인 열쇠를 사용하여 건물 전체를 통과하는 방법까지 알아내는 마스터 열쇠공이라고 생각해보세요.

PUFFERDOS가 어떻게 작동하는지 단계별로 쉽게 설명해 드리겠습니다.

1. "정지 지점" 전략 (경비원을 더 힘들게 만들기)

연구진들은 경비원을 멈추게 하려면 단순히 혼란스러운 패턴만 필요한 것이 아니라, 경비원이 아주 작고 비효율적인 단계를 밟도록 만들어야 한다는 것을 깨달았습니다.

비유: 경비원이 복도를 걷고 있다고 상상해 보세요. 만약 당신이 그들이 매 인치마다 멈춰서 바닥을 확인하게 만든다면, 그들은 금방 지칠 것입니다. 만약 10피트마다 멈춘다면, 그들은 더 천천히 지칠 것입니다.
해결책: PUFFERDOS는 경비원이 최대한 많이 되돌아가기(backtrack, 다시 확인하러 돌아가는 것)를 하도록 특정 문자들을 정교하게 선택하고 배치하여 "열쇠"(공격 문자열)를 만듭니다. 이렇게 하면 동일한 "멈춤" 효과를 내면서도 훨씬 짧은 열쇠를 사용할 수 있기 때문에, 이전 방식보다 수천 배 더 빠르게 공격을 수행할 수 있습니다.

2. 세 가지 "함정" 패턴

연구팀은 대부분의 고장 난 자물쇠가 세 가지 특정 형태를 가진다는 것을 발견했습니다. PUFFERDOS는 각 형태에 대한 특별한 레시피를 가지고 있습니다.

단일 루프 함정 (One-Loop Trap): 하나의 패턴이 여러 가지 혼란스러운 방식으로 읽힐 수 있는 경우입니다. PUFFERDOS는 반복될 가장 짧고 혼란스러운 문자를 선택합니다.
이중 루프 함정 (Two-Loop Trap): 두 개의 패턴이 나란히 있으며, 두 패턴 모두 동일한 문자를 읽을 수 있는 경우입니다. PUFFERDOS는 두 패턴이 서로 그 문자를 처리하려고 다투게끔 만드는, 두 패턴 모두가 읽을 수 있는 문자를 사용합니다.
다중 루프 함정 (Multi-Loop Trap): 긴 체인 형태의 패턴입니다. PUFFERDOS는 경비가 체인의 각 연결 고리를 개별적으로 확인하도록 강제하는 열쇠를 구축합니다.

3. "실제 환경" 시뮬레이션 (Concolic Execution)

이 부분이 가장 중요합니다. 기존 도구들은 진공 상태에서 자물쇠만 테스트했습니다. 하지만 PUFFERDOS는 건물 전체를 시뮬레이션합니다.

비유: 당신에게 문을 여는 열쇠가 있지만, 그 문이 보안 체크포인트, 접수원, 그리고 미로 뒤에 있다고 상상해 보세요. 기존 도구들은 그저 열쇠가 문을 연다는 것만 보여주었습니다. 하지만 PUFFERDOS는 미로를 통과해 걷고, 접수원이 당신을 통과시켜 주는지 확인하며, 실제로 그 문에 도달할 수 있는지 확인합니다.
방법: PUFFERDOS는 "조합적 컨콜릭 실행(compositional concolic execution)"이라는 기술을 사용합니다. 이것을 지도 요약본이라고 생각하세요. 건물의 모든 단계를 매번 다시 걷는 대신, PUFFERDOS는 각 방(함수)에 대한 "치트 시트"를 만듭니다. 그리고 다음과 같이 묻습니다: "만약 내가 이 방에 혼란스러운 열쇠를 준다면, 이 방은 그것을 다음 방으로 전달할 것인가, 아니면 버릴 것인가?"
이러한 치트 시트를 사용함으로써, PUFFERDOS는 짧고 효율적인 열키가 실제 프로그램 내에서 취약한 자물쇠에 실제로 도달할 수 있는지, 아니면 과정 중간의 필터에 의해 차단될지를 빠르게 파악할 수 있습니다.

결과

연구팀은 수천 개의 실제 프로그램과 알려진 보안 취약점(CVE)을 대상으로 PUFFERDOS를 테스트했습니다.

속도: PUFFERDOS는 이전의 최고 도구보다 97배에서 3,800배 더 효율적인 공격 문자열을 생성했습니다. 거대한 문자열 대신 아주 작은 문자열만으로도 시스템을 멈추게 할 수 있었습니다.
성공률: 알려진 보안 취약점의 **96.8%**를 성공적으로 재현했습니다(기존 도구의 77.4%와 비교).
새로운 발견: 12개의 인기 있는 실제 소프트웨어 프로젝트를 테스트했을 때, 기존 도구들이 (공격이 현실적으로 짧고 구현 가능하다고 증명하지 못해) 놓쳤던 59개의 새로운 미공개 보안 취약점을 발견했습니다.

요약하자면: PUFFERDOS는 컴퓨터 시스템이 혼란스러운 패턴에 의해 멈출 수 있음을 찾아내고 증명하는 더 스마트하고 실용적인 방법입니다. 단순히 자물쇠를 찾는 것에 그치지 않고, 그 자물쇠를 막아버릴 가장 짧고 현실적인 열쇠를 찾아내어 그 위험이 실재함을 증명합니다.

기술 요약: PUFFERDOS

문제 정의

정규 표현식 거부 서비스(ReDoS) 공격은 백트래킹 정규 표현식 엔진의 병목 현상이 발생하는 최악의 실행 동작을 악용하여, 매칭 경로를 초선형 또는 지수적으로 탐색하도록 강제합니다. 이는 과도한 CPU 자원을 소비하여 서비스 저하나 불능 상태를 초래합니다. 취약한 정규 표현식을 식별하고 개념 증명(PoC) 공격 문자열을 생성하는 수많은 탐지 도구가 존재하지만, 현재의 접근 방식들은 실제적인 공격을 방해하는 두 가지 결정적인 한계점을 가지고 있습니다:

비현실적인 입력 길이: 기존 도구들은 종종 유의미한 속도 저하를 유발하기 위해 비현실적으로 긴(예: 수십만 자가 필요한) 공격 문자열을 생성합니다. 실제 배포 환경에서는 입력 제약 조건(예: HTTP 헤더 제한)으로 인해 이러한 문자열이 취약한 정규 표현식에 도달하기 전에 잘려버려 공격이 무력화되는 경우가 많습니다.
프로그램 수준의 검증 부족: 많은 생성된 문자열은 정규 표현식 자체에 대해서만 검증됩니다. 이들은 데이터 흐름 제약, 필터링 로직, 또는 호스트 프로그램 내의 입력 절단(truncation)을 고려하지 못합니다. 결과적으로, 이러한 문자열은 실제 프로그램 실행 컨텍처 내에서 취약한 정규 표현식에 도달할 수 없으며, 이로 인해 개발자들이 보고된 취약점을 저위험 또는 공격 불가능한 것으로 치부하게 만듭니다.

방법론

저자들은 효율적(현실적인 길이 예산 내에서 매칭 비용 극대화)이면서 동시에 유효한(실제 프로그램 내에서 취약한 정규 표현식에 도달하도록 검증된) 공격 문자열을 합성하기 위한 하이브리드 프레임워크인 PUFFERDOS를 제안합니다. 이 방법론은 세 가지 핵심 구성 요소로 이루어집니다:

1. 형식적 분석 및 패턴 분류

저자들은 먼저 공격 문자열 구조와 매칭 비용 사이의 관계를 공식화합니다. 형식적 증명(Lemma 3.2–3.4 및 Theorem 3.5)을 통해, 다음의 경우에 매칭 비용이 증가함을 입증합니다:

반복 단위(repetition units)가 가능한 한 짧을 때.
인접한 루프 표현식(Loop Expressions, LEs)의 알파벳 교집합에서 반복 단위가 선택되어, 여러 LE가 동일한 서브스트링을 소비할 수 있을 때.
중지 지점(LE가 종료되는 인덱스)이 서로 얽히지 않고 분리되어 있어, 엔진이 백트래킹 중에 더 긴 입력 세그먼트를 재처리하도록 강제할 때.

이를 바탕으로, 문자열 생성을 가이드하기 위해 세 가지 취약한 패턴을 정의합니다:

지수적 단일 루프 (Exponential One-Loop, EOL): 겹치는 알파벳을 가진 언폴딩(unfolding) 서브 정규 표현식을 포함하는 단일 LE.
루프-교차-루프 (Loop-Intersect-Loop, LIL): 양쪽 LE 모두에 의해 매치될 수 있는 비루프 세그먼트에 의해 구분되는 두 개의 인접한 LE.
다항식 다중 루프 (Polynomial Multi-Loop, PML): 서로 디스조인트(disjoint)한 알파벳이나 구분자를 가진 인접한 LE.

2. 구조 기반 공격 문자열 생성

PUFFERDOS는 취약한 정규 표현식을 추상 구문 트리(rAST)로 파싱하여 특정 취약 패턴(EOL, LIL 또는 PML)을 식별합니다. 그 후 패턴별 규칙을 사용하여 후보 공격 문자열( $s_a = x \cdot y^q \cdot z$ )을 합성합니다:

인픽스(Infix) 생성: 관련 LE들의 알파벳 교집합에서 가장 짧은 반복 단위( $y$ )를 선택합니다. 여러 LE가 있는 패턴의 경우, 중지 지점이 분리되도록 독립적으로 반복되는 단위들을 연결하여 백트래킹 단계를 극대화합니다.
접두사/접미사(Prefix/Suffix) 구성: 접두사( $x$ )는 정규 표현식의 비루프 접두사로부터 유도하고, 접미사( $z$ )는 비루프 접미사로부터 유도하여, 최종 문자열이 정규 표현식에 의해 거부되어 철저한 백트래킹을 유발하도록 보장합니다.

3. ReDoS 특화 조성적 콘콜릭 정제 (Compositional Concolic Refinement)

생성된 문자열이 실제 프로그램 내에서 취약한 정규 표현식에 도달하도록 보장하기 위해, PUFFERDOS는 조성적 콘콜릭 실행 전략을 채택합니다:

경로 추출: 호출 그래프를 구축하여 프로그램 진입점에서 취약한 정규 표현식까지의 실행 가능한 경로를 식별합니다.
함수 요약: 경로 상의 함수들에 대해 콘콜릭 단위 테스트를 수행하여 ReDoS 특화 함수 요약을 생성합니다. 전통적인 요약과 달리, 이 요약은 공격 문자열의 전파와 관련된 동작(예: 항등 변환 또는 상수 반환)만을 유지하고, 경로 폭발을 일으키는 관련 없는 정규 표현식 추론은 제거하도록 프루닝(pruning)됩니다.
시스템 레벨 정제: 요약을 사용하여 시스템 레벨의 콘콜릭 실행을 가이드함으로써, 인터프로시저(interprocedural) 제약 조건을 해결하고 공격 문자열이 필터를 통과하여 현실적인 입력 길이 예산을 초과하지 않으면서 타겟 정규 표현식에 도달하도록 정제합니다.

주요 기여

효율성에 대한 형식적 증명: 본 논문은 특정 문자를 선택하고 이를 인접한 LE의 중지 지점을 분리하도록 배치하는 것이 정규 표현식 매칭 비용을 크게 증폭시킨다는 것을 형식적으로 증명합니다. 이는 세 가지 정규 표현식 취약 패턴의 도출과 증명 가능한 효율적 생성 규칙로 이어집니다.
PUFFERDOS 프레임워크: 형식적 생성 규칙과 ReDoS 특화 조성적 콘콜릭 정제를 통합한 하이브리드 생성기를 개발했습니다. 이 접근 방식은 문자열을 현실적인 제약 조건에 맞게 짧게 만들고 프로그램의 데이터 흐름 내에서 유효하게 만듦으로써, 이론적 탐지와 실제적 공격 사이의 간극을 메웁니다.
포괄적인 평가: 17,962개의 취약한 정규 표현식, 31개의 알려진 CVE, 12개의 인기 오픈 소스 프로젝트로 구성된 대규모 코퍼스에서 도구를 평가했습니다.

결과

평가는 최신 도구인 RENGAR와 비교하여 유의미한 개선을 보여줍니다:

효율성: PUFFERDOS는 동일한 매칭 시간 임계값(0.1초, 1초, 10초)을 달성하면서도 RENGAR가 생성하는 것보다 97.2배에서 3,872.4배 더 짧은 공격 문자열을 생성합니다.
CVE 재현: PUFFERDOS는 RENGAR의 77.4%와 비교하여, 악용된 ReDoS CVE의 **96.8%**를 성공적으로 재현했습니다.
새로운 취약점 발견: 12개의 인기 오픈 소스 프로젝트에 적용했을 때, PUFFEDOS는 RENGAR보다 25개 더 많은 59개의 악용 가능한 ReDoS 인스턴스를 발견했습니다. 이 중 6개 프로젝트의 개발자들이 21개의 결과를 검증했습니다.
실제 영향력: 구문 강조 라이브러리를 다룬 동기 부여 사례에서, PUFFEDOS는 1,000자 길이의 문자열로 4,000초 이상의 시스템 행(hang)을 유발한 반면, 전통적인 방식은 500,000자의 문자가 필요했으며 실제 프로그램의 입력 절단으로 인해 행을 유발하는 데 실패했습니다.

의의

본 논문은 생성된 공격 문자열이 너무 길거나 프로그램 로직을 통과하지 못하기 때문에 ReDoS 탐지의 실질적인 유용성이 제한된다고 주장합니다. 이러한 특정 결함들을 해결함으로써, PUFFEDOS는 실제로 악용 가능한 취약점의 증거를 생성하는 메커니즘을 제공합니다. 이는 매우 중요한데, 개발자들이 ReDoS 보고를 (저위험 또는 공격 불가능한 것으로 인식하여) 무시하게 만드는 직접적인 이유를 해결하기 때문입니다. 짧고 유효한 공격 문자열을 제공함으로써, PUFFEDOS는 더 정확한 위험 평가를 가능하게 하고 실제 소프트웨어 시스템의 ReDoS 취약점 조치를 용이하게 합니다.