비효율적인 정규표현식으로 인한 ReDoS

설명

정규표현식에 중첩된 반복(예: (.+)+, (.*)+, (r+){m,})이나 모호한 분기가 있으면 매칭 과정에서 'catastrophic backtracking'이 발생하여 입력 길이에 대해 지수적 시간 복잡도가 나타날 수 있습니다. 공격자는 매우 긴 문자열이나 특정 패턴(예: 'aaaaaaaaaX')을 요청 파라미터로 보내 서버의 CPU를 과점유하게 만들어 응답이 지연되거나 중단되도록 악용합니다. 이벤트 루프 기반 런타임(Node.js 등)에서는 단일 요청만으로도 전체 서비스에 영향을 줄 수 있습니다.

실제 비용은 패턴, 입력과 정규식 엔진에 따라 달라집니다. 중첩 반복이 있다는 사실만으로 모든 매칭이 지수적 비용을 갖는 것은 아닙니다.

잠재적 영향

서비스 거부(DoS): 정규식 매칭이 장시간 걸려 요청 처리가 지연·중단됩니다.
CPU/메모리 자원 고갈: 백트래킹으로 과도한 연산과 스택 사용이 발생합니다.
응답 지연 및 타임아웃: API 응답 속도가 급격히 느려지고 타임아웃이 증가합니다.
가용성/확장성 저하: 소수의 악성 요청만으로도 전체 인스턴스의 처리 능력이 떨어집니다.

해결 방법

중첩 반복 제거: (.+)+, (.*)+, (a+){2,} 같은 패턴을 비모호한 형태로 재작성하세요. 예) /^(__|.)+$/ → /^(__|[^])+_$/.
고정/제한된 반복 사용: 가급적 고정 길이 또는 상한을 둔 {0,64} 등으로 작성하세요.
입력 길이 제한: 정규식 매칭 전에 입력 최대 길이를 제한(예: 256자)하고 초과 시 즉시 차단하세요.
안전한 엔진 사용: 가능한 경우 RE2 기반 라이브러리(re2 등)처럼 선형 시간 매칭을 보장하는 엔진을 사용하세요.
검토: 린터와 정적분석을 보조 수단으로 사용하고, 실제 입력 제한과 엔진의 동작도 확인하세요.
실제 자원 제한 적용: 요청 타임아웃은 동기 정규식 매칭을 중단하지 못합니다. 종료할 수 있는 작업자나 프로세스 또는 제한을 강제할 수 있는 엔진을 사용하세요.

예시

변경 전

javascript

// 비효율적 정규식: 중첩 반복으로 인해 백트래킹 폭발 가능
const express = require('express');
const app = express();

// 영문자 그룹을 다시 반복: ^([a-z]+)+$
const usernameRegex = new RegExp("^([a-z]+)+$", "i");

app.get('/check', (req, res) => {
  const name = (req.query.name || '').toString();
  // 길이 제한 없음 + 위험한 정규식 사용
  if (usernameRegex.test(name)) {
    return res.send('ok');
  }
  res.status(400).send('invalid');
});

app.listen(3000);
// 공격 예: 'a'.repeat(50000) + '!' 로 긴 입력을 보내면 CPU가 장시간 점유될 수 있음

변경 후

javascript

// 안전한 정규식 + 입력 길이 제한 +(선택) RE2 사용 예시
const express = require('express');
// 선택: RE2 사용 시
// const RE2 = require('re2');
const app = express();

// 중첩 반복 제거 및 상한 명시: ^[A-Za-z]{1,64}$
// 네이티브 RegExp 사용
const usernameRegex = new RegExp("^[A-Za-z]{1,64}$");
// RE2 사용 시:
// const usernameRegex = new RE2('^[A-Za-z]{1,64}$');

app.get('/check', (req, res) => {
  const name = String(req.query.name || '');

  // 사전 길이 제한 (이중 방어)
  if (name.length === 0 || name.length > 64) {
    return res.status(400).send('invalid');
  }

  if (!usernameRegex.test(name)) {
    return res.status(400).send('invalid');
  }
  res.send('ok');
});

app.listen(3000);

설명:

변경 전: ^([a-z]+)+$ 는 그룹 내부에 +, 외부에도 +가 있어 모호한 경로가 다수 생성됩니다. 긴 유사 패턴 입력(예: 'aaaa...!')에 대해 백트래킹이 폭발적으로 증가해 CPU를 장시간 점유하고, Node.js 이벤트 루프가 차단되어 서비스 거부(DoS)가 유발됩니다. 또한 입력 길이 제한이 없어 위험이 더 커집니다.
변경 후: 정규식을 비모호하게 재작성(중첩 반복 제거)하고, 명시적 길이 상한을 둬 선형 시간에 가까운 매칭을 보장합니다. 필요 시 RE2 같은 선형 시간 엔진을 사용해 백트래킹 기반 취약점을 구조적으로 제거합니다. 이로써 공격자가 만든 특수 입력으로도 CPU 과점유와 서비스 지연을 유발하기 어렵습니다.

참조

CWE-1333