flawopen.com/ReDoS(치명적 백트래킹)란 무엇인가요?/Explained

ReDoS(치명적 백트래킹)란 무엇인가요?

CWE-1333: Inefficient Regular Expression Complexity참고 페이지

간단한 설명

백트래킹 정규식 엔진은 매칭이 실패하면 같은 입력을 여러 방식으로 나누어 다시 시도할 수 있습니다. 일부 모호한 패턴에서는 입력 길이가 늘어날수록 시도 횟수가 지수적으로 증가합니다. 실제 지연은 정규식, 엔진, 입력 크기, 동시성, 리소스 제한에 따라 달라지며, 비용이 큰 요청이 반복되면 서비스 처리 용량을 소진할 수 있습니다.

취약한 패턴

# Nested quantifier
^(a+)+$

# Overlapping alternatives, quantified
^(a|aa)+$

# A long matching prefix plus a final mismatch can
# force extensive retries in vulnerable engines.
# Do not benchmark this with attacker-sized input.

더 안전한 방식

# Bound input before matching, then use a simple
# full-string identifier rule with no nested ambiguity.
import re

IDENTIFIER = re.compile(r"[a-z0-9]{1,64}\Z")

def valid_identifier(value: str) -> bool:
    if not isinstance(value, str) or len(value) > 64:
        return False
    return IDENTIFIER.fullmatch(value) is not None

# A bound reduces worst-case work; still set request
# size, concurrency, and execution-time limits.

백트래킹이 급증하는 이유

백트래킹 엔진에서 ^(a+)+$ 같은 패턴은 모호합니다. aaaa를 중첩된 수량자에 여러 방식으로 나눠 넣을 수 있습니다. 마지막에 일치하지 않는 문자가 있으면 전체 문자열이 실패라고 결론 내리기 전 여러 대안을 탐색할 수 있습니다.

해당 모호성이 있는 패턴은 일치하는 접두부 뒤에 불일치가 있을 때 탐색 경로가 접두부 길이에 따라 지수적으로 늘어날 수 있습니다. 이는 특정 패턴과 엔진 조합에 해당하며 모든 정규식이나 실패에 적용되지는 않습니다. 동시 요청에서는 짧은 입력도 영향을 줄 수 있으므로 입력 크기, 동시성, 시간을 제한하세요.

신뢰할 수 없는 입력이 정규식에 도달하는 경로

입력 검증뿐 아니라 User-Agent 등 헤더 처리, 로그 파이프라인, Markdown과 구문 강조, URL 라우팅, 콘텐츠 필터, WAF 규칙, 전달받은 필드에 정규식을 실행하는 라이브러리에도 위험이 있습니다. 널리 쓰이는 패키지에서도 ReDoS 권고가 있었으므로 의존성도 점검해야 합니다.

자주 묻는 질문

Which languages are affected?

위험은 언어뿐 아니라 엔진과 패턴에 달려 있습니다. 일반적인 백트래킹 엔진도 특정 패턴에서는 지나치게 많은 대안을 탐색할 수 있습니다. Go의 regexp 문서는 입력 길이에 대한 선형 시간을 보장합니다. Rust의 regex crate는 단일 검색에 O(m·n)(m은 패턴 크기, n은 입력 크기)을 명시하므로 패턴이 고정되면 입력에 대해 선형입니다. 반복 검색 iterator의 최악 복잡도는 다릅니다. 이 엔진들은 역참조처럼 보장을 깨뜨리는 기능을 지원하지 않습니다.

Is a length limit enough on its own?

길이 제한은 매칭 작업량을 제한하지만 안전한 값은 패턴, 엔진, 요청률, 서비스 예산에 따라 다릅니다. 모호한 패턴도 수정하고 파싱이나 매칭 전에 제한을 적용하세요.

How do I find vulnerable patterns?

ReDoS를 탐지하는 정적 분석기를 사용하고 실제 엔진에 맞춰 결과를 검토하세요. 반복 안에 반복이 있는 그룹이나 접두부가 겹치는 대안을 확인하고, 격리된 환경에서 입력을 제한하고 엄격한 timeout을 둔 테스트를 수행하세요.

Can I add a timeout instead?

Timeout 지원은 런타임과 API에 따라 다릅니다. .NET에서는 신뢰할 수 없는 입력 매칭에 명시적 timeout을 지정하세요. 다른 환경에서는 엔진 문서의 제어 기능을 확인하고, timeout을 적용할 수 없다면 더 안전한 엔진을 쓰거나 패턴을 다시 설계하세요. Timeout은 입력 및 동시성 제한을 보완하지만 모호한 패턴을 효율적으로 만들지는 않습니다.

ReDoS(치명적 백트래킹)란 무엇인가요?

백트래킹이 급증하는 이유

신뢰할 수 없는 입력이 정규식에 도달하는 경로

자주 묻는 질문

참고 자료