비효율적인 정규식으로 인한 서비스 거부 (ReDoS)

Regular Expression Denial of Service (ReDoS)

설명

ReDoS는 비효율적인 정규식(regex) 패턴이 되돌아가기(backtracking)를 과도하게 유발하여 매칭 시간이 폭증하는 취약점입니다. Java의 java.util.regex 엔진은 backtracking 기반이라, 중첩 반복자((...+)+, (\w+)* 등)나 모호한 대안식 반복((A|.)+ 등)에서 최악의 경우 지수 시간까지 걸릴 수 있습니다. 공격자는 특수하게 만든 긴 입력을 제출해 정규식 매칭 루틴을 오래 묶어두고, 서버 스레드와 CPU를 소모시켜 서비스 거부(DoS)를 유발할 수 있습니다. Java 9+에서 일부 완화책이 있으나, 복잡한 패턴은 여전히 영향을 받을 수 있습니다.

잠재적 영향

• 서비스 거부(DoS): 정규식 매칭이 긴 시간 동안 CPU를 점유해 요청 처리 스레드가 응답하지 않음

• 자원 고갈: CPU 100% 사용, 스레드 풀/요청 큐 고갈로 신규 요청 처리 불가

• 성능 저하 및 지연 증가: 전체 응답 시간이 급증하고 타임아웃이 발생

• 장애 전파: 백엔드 호출 타임아웃, 장애 격리가 실패하면 시스템 전반으로 영향 확산

해결 방법

• 패턴 재작성(모호성 제거): 대안식에서 중복 매칭을 유발하는 분기를 제거하거나 명확한 문자 클래스 사용

• 중첩 반복자 제거: (...+)+, (.)+, (\w+) 등의 패턴을 단일 반복으로 단순화

• 원자적 그룹/포지시브 수량자 사용: (?>...) 또는 *+, ++, ?+로 불필요한 backtracking 차단(호환성 검토 필요)

• 입력 길이 제한: 서버에서 정규식이 처리할 최대 길이를 엄격히 제한하고 검증

• 안전한 엔진 고려: 선형 시간 보장을 제공하는 RE2J 같은 대체 엔진 검토

• 실행 가드: 정규식 평가를 별도 스레드에서 실행해 타임아웃/중단 전략 적용(언어/런타임 제약 고려)

취약한 코드 및 안전한 코드 예시

취약한 코드

import java.util.regex.Pattern;

public class IdCheckerVulnerable {
    // 중첩 반복자: (\d+)+  -> 특정 비일치 지점에서 backtracking 폭증
    private static final Pattern VULN = Pattern.compile("^(\\d+)+$");

    public boolean isNumericId(String input) {
        if (input == null) return false;
        return VULN.matcher(input).matches();
    }
}

안전한 코드

import java.util.regex.Pattern;

public class IdCheckerSafe {
    private static final int MAX_LEN = 256; // 입력 길이 상한
    // 해결책 1: 중첩 제거하여 단일 반복으로 단순화
    private static final Pattern SAFE = Pattern.compile("^\\d+$");
    // 해결책 2(대안): 포지시브 수량자 사용 -> "^(\\d++)$" (불필요한 backtracking 차단)

    public boolean isNumericId(String input) {
        if (input == null || input.length() > MAX_LEN) return false; // 길이 제한으로 비용 상한
        return SAFE.matcher(input).matches();
    }
}

설명:

• 취약한 코드: 패턴 ^(\d+)+$ 는 그룹 내부에 \d+ 반복이 있고, 그룹 자체에도 +가 있어 중첩 반복자가 됩니다. 불일치가 발생하는 긴 입력(예: 많은 숫자 뒤에 문자 1개)을 주면 엔진이 수많은 경로를 되돌아가며 시도하여 매칭 시간이 폭증합니다. 공격자는 이러한 입력을 반복 전송해 CPU와 스레드를 소모시키며 ReDoS를 유발할 수 있습니다.

• 안전한 코드: 중첩 반복을 제거해 ^\d+$ 로 단순화하여 되돌아가기 경로를 급감시켰고, 추가로 입력 길이를 제한해 최악의 비용을 상한 처리했습니다. 필요 시 포지시브 수량자(\d++)나 원자적 그룹(?>...)을 사용해 backtracking 자체를 차단할 수 있어 ReDoS 위험을 크게 줄입니다.

참조

• CWE-1333