♾️ 종료되지 않는 반복문/재귀 시뮬레이터 KISA A-3 · 제어되지 않는 반복문/재귀

공격자가 제어하는 입력이 무한에 가까운 연산을 유발합니다. 백트래킹이 폭발하는 ReDoS 정규식, 혹은 종료 조건이 없는 반복문/재귀로 CPU가 100%에 묶이고 요청 스레드가 멈춥니다(서비스 거부).

① 취약한 입력 처리기 VULNERABLE

실패 유형을 선택하세요. 연산은 시뮬레이션합니다 — 거대한 입력에 실제 악성 정규식을 돌리거나 진짜 무한 루프를 만들지 않습니다(브라우저가 멈춤). 미터는 모델링된 스텝 수를 보여줍니다.

공격자 입력 (길이가 폭발을 유발)

CPU / 백트래킹 스텝 (모델)0%

(실행 전)

② 안전한 처리기: 경계·선형 정규식·깊이 가드 SECURE

같은 입력에 방어 적용: 길이를 제한하고, 정규식을 앵커·선형(중첩 수량자 제거)으로 바꾸며, 반복문에 상한을 두고, 재귀에는 깊이 제한과 시간 제한(타임아웃)을 둡니다. 연산이 선형·유한으로 유지됩니다.

동일 입력 (검증 적용)

CPU / 스텝 (제한됨)0%

(실행 전)

③ 취약 vs 안전 코드

VULNERABLE

// ReDoS: 중첩 수량자 → 지수 백트래킹
Pattern p = Pattern.compile("(a+)+$");
p.matcher(userInput).matches();   // "aaaa...!" 에서 폭발

// 무한 루프: 종료 조건이 입력에 의존
while (true) {                      // 또는 잘못된 조건
    process(queue.poll());         // queue 가 비어도 탈출 못함
}

// 무한 재귀: 종료/깊이 가드 없음
int depth(Node n){ return 1 + depth(n.next); } // 순환 시 StackOverflow

SECURE

// 선형 정규식 + 입력 길이 제한
if (userInput.length() > 256) reject();
Pattern p = Pattern.compile("^a+$");   // 중첩 수량자 제거 (또는 RE2)

// 반복문 상한
for (int i = 0; i < MAX_ITERS && !queue.isEmpty(); i++)
    process(queue.poll());

// 재귀 깊이 가드 + 타임아웃
int depth(Node n, int d){
    if (n == null || d > MAX_DEPTH) return d;   // 가드
    return depth(n.next, d + 1);
}
// 정규식/파싱은 별도 스레드에서 timeout 으로 강제 종료

폭발 원리: (a+)+ 같은 중첩 수량자는 같은 문자열을 지수적으로 많은 방식으로 나눌 수 있어, 끝의 앵커가 실패하면(끝의 !) 그 모든 경우를 백트래킹합니다 — O(2^n). 무한 반복/재귀는 입력과 무관한 종료점이 없습니다. 방어: 입력 길이 제한 · 선형/원자적 정규식 또는 RE2 사용 · 모든 반복문에 상한 · 재귀 깊이 가드 · 위험 연산은 타임아웃으로 감싸 한 요청이 CPU를 점유하지 못하게 합니다.

⚠️ 교육용 시뮬레이션입니다. 스텝 수와 CPU 미터는 상한이 걸린 계산 모델이며, 실제 악성 정규식이나 무한 루프를 실행하지 않습니다.