정규표현식 기반 서비스 거부 (ReDoS: Regular Expression Denial-of-Service)

개요

ReDoS(Regular Expression Denial-of-Service)는 정규표현식의 계산 복잡성을 악용하여 서비스의 자원을 고갈시키는 공격 기법입니다. 정규표현식은 입력 데이터 유효성 검증, 보안 필터링, 탐지 룰 등 다양한 영역에서 활용되지만, 비효율적인 패턴 구성 시 입력 길이에 따라 기하급수적으로 연산 시간이 증가하여 서비스 마비로 이어질 수 있습니다. 본 글에서는 ReDoS의 개념, 공격 원리, 피해 사례, 탐지 및 방어 전략을 상세히 살펴봅니다.

---

1. 개념 및 정의

항목	설명
ReDoS	입력값이 특정 정규표현식 패턴을 유발해 과도한 연산이 발생함으로써 서비스 자원을 소모시키는 공격
정규표현식(Regex)	문자열 검색, 매칭, 대체 등을 위해 사용하는 패턴 언어
NFA (Nondeterministic Finite Automaton)	대부분의 프로그래밍 언어가 사용하는 정규식 처리 방식으로, 백트래킹에 의해 성능 저하 발생 가능성 존재

---

2. 공격 원리

ReDoS는 다음과 같은 방식으로 작동합니다.

1. 복잡한 정규표현식 구성: (a+)+, ([a-zA-Z]+)* 등 중첩된 반복 패턴
2. 백트래킹 유도 입력값 구성: aaaaaaaaaaaaaaaaaaaa! → 수많은 경우의 수를 모두 검증해야 함
3. 최악의 경우 지수 시간 복잡도 발생: O(2^n) 수준까지 연산 시간 증가 가능
4. 단일 요청만으로도 CPU 점유율 급증 → 서비스 응답 지연 또는 중단 유도

---

3. 피해 사례

사례	설명
Node.js Express 취약 정규식	사용자 입력 필터링 정규식에서 (.*a){10} 형태 사용으로 인해 30초 이상 지연 발생
Python Re 모듈 기반 웹 서버	로그 파싱 시 비효율적인 정규식으로 인해 DoS 취약점 유발
npm validator.js 라이브러리 CVE	이메일 주소 검증 패턴의 ReDoS 공격 가능성으로 보안 패치

---

4. 탐지 및 분석 방법

방법	설명
정적 분석 도구 사용	r2e, safe-regex, regexlint 등을 통해 위험 정규표현식 자동 탐지
Fuzzing 기반 입력 테스트	악성 입력으로 예상되는 패턴을 자동 생성하여 정규식 반응 시간 측정
백트래킹 경로 분석	정규식의 반복 구조 및 그룹화 패턴을 시각화하여 최악의 경로 확인

---

5. 방어 전략

1) 정규식 설계 시 주의사항

• 중첩된 그룹 사용 최소화: (a+)+ → (a{1,10})+
• 불필요한 Greedy 사용 자제: .* → [^\s]*
• 입력 길이 제한 적용: 사용자 입력값의 최대 길이 제한

2) 런타임 보호 조치

• 입력 검증 전 처리 타임아웃 적용: 일정 시간 이상 소요 시 강제 종료
• 서버 프로세스 격리 및 리소스 제한: 요청별 리소스 제어 (예: Node.js cluster fork)
• WAF 기반 필터링: 반복된 특수 패턴 포함 요청 차단

3) 보안 테스트 및 DevSecOps 적용

• 정규표현식 포함 코드 영역에 대해 정적 분석 자동화 구성
• 코드 리뷰 단계에서 정규식 구조 리뷰 체크리스트 반영

---

6. 관련 도구 및 프레임워크

도구명	설명
safe-regex (Node.js)	정규표현식의 ReDoS 가능성 분석 도구
r2e (Regex to ENFA Visualizer)	정규식의 백트래킹 가능성 시각화 도구
Regexr, Regexper	정규표현식 구조 분석 및 테스트 플랫폼
GitHub CodeQL	코드베이스의 취약한 정규식 탐지를 위한 정적 분석 도구

---

7. 결론

ReDoS는 단순한 입력값 조작으로도 애플리케이션 레벨의 서비스 마비를 유발할 수 있는 고위험 취약점입니다. 특히 웹 필터링, API 요청 검증, 로그 파싱 등에서 사용되는 정규표현식은 반드시 보안 측면에서 검토되어야 하며, 정적 분석, 테스트 자동화, WAF 정책, 입력 길이 제한 등의 조치를 통해 ReDoS 방지 체계를 사전에 구축하는 것이 중요합니다.