ReDoS (Regular Expression Denial of Service) 공격은 자원 고갈 (resource-exhaustion) 취약점의 중요한 범주를 구성합니다. 이러한 공격에서 공격자는 정규 표현식 (regex) 엔진의 병리적인 최악의 실행 동작을 악용하여 매우 비대칭적인 계산 워크로드를 유도하며, 궁극적으로 시스템 자원을 고갈시키고 서비스 가용성을 저하시킵니다. ReDoS 공격으로부터 시스템을 보호하기 위해, 개발 초기 단계에서 ReDoS 취약점을 선제적으로 악용하고 조치를 용이하게 하기 위해 공격 문자열을 생성하여 공격 프로세스를 시뮬레이션하는 수많은 탐지 기술이 제안되었습니다. 기존 기술은 크게 두 가지 범주로 나뉩니다: 병리적인 regex 구조를 검색하는 정적 분석 (static analyses)과 후보 공격 문자열을 합성하는 동적 탐색 (dynamic exploration) 방법입니다. 그러나 생성된 공격 문자열은 대개 비현실적인 입력 길이 예산을 가정하고 프로그램 수준에서 공격의 효과와 효율성을 검증하지 않기 때문에, 실제 환경에서의 악용 (exploitation)에는 비실용적인 경우가 많습니다. 따라서 생성된 많은 문자열이 실제 프로그램에 적용되었을 때 취약한 regex를 트리거하는 데 실패하며, 이는 실질적인 유용성을 더욱 제한합니다. 이러한 단점을 해결하기 위해, 우리는 현실적인 길이 예산 내에서 실행 가능하며 프로그램 수준에서 검증된 공격 입력을 합성하도록 설계되어, 실제 프로그램에서의 ReDoS 취약점을 효과적으로 악용할 수 있게 하는 효율적이고 효과적인 공격 문자열 생성기인 PUFFERDOS를 소개합니다. 구체적으로, 우리는 먼저 관찰과 형식 검증 (formal verification)을 기반으로 세 가지 취약 패턴을 정의합니다. 이 패턴에 따라 PUFFERDOS는 공격 문자열을 생성하기 위한 합성 기술을 수행하며, 그 후 ReDoS 특화 합성적 콘콜릭 실행 (compositional concolic execution)을 통해 문자열을 정제하고 검증하여 실제 환경에서의 악용 가능성을 보장합니다.