정규식 탐욕적·게으른 매칭 차이와 ReDoS, 서버를 멈추는 패턴

정규식이 예상보다 훨씬 많이 잡거나, 특정 입력 하나에 CPU를 100% 쓰며 멈춘다면 수량자의 동작 방식을 의심해 봐야 해요. 결론부터 말하면 너무 많이 잡히는 건 기본 수량자가 "탐욕적(greedy)"이라서고 ? 를 붙이거나 부정 문자 클래스를 쓰면 해결돼요. 멈추는 건 중첩 수량자가 만드는 "재앙적 백트래킹"이고, 입력 길이에 따라 시간이 지수적으로 늘어나는 ReDoS 취약점이에요.

이 글에서는 두 현상을 같은 원리(백트래킹)로 설명하고, ^(a+)+$ 패턴이 입력 길이에 따라 얼마나 느려지는지 Node.js와 Python에서 직접 재 본 결과를 보여 드릴게요. 실제로 2019년 클라우드플레어 전 세계 장애, 2016년 스택 오버플로 장애가 모두 정규식 백트래킹 때문이었어요. 코드 리뷰에서 위험한 모양을 알아보는 법과 막는 방법까지 정리했어요.

핵심 요약

수량자(+ *)는 기본적으로 가능한 한 많이 먹는 탐욕적 방식이고, 뒤에 ? 를 붙이면 가능한 한 적게 먹는 게으른 방식이 돼요.

(a+)+ 처럼 수량자가 중첩되면 실패하는 입력에서 경우의 수가 2의 n제곱으로 늘어요. 직접 재 보니 글자 2개 늘 때마다 약 4배씩 느려졌어요.

위험 신호는 중첩 수량자, 겹치는 선택지, 겹치는 연속 수량자 세 가지예요.

입력 길이 제한, 겹치지 않는 패턴, 선형 시간 엔진(RE2), 실행 시간 제한으로 막아요.

탐욕적 매칭이 기본값이다

+, *, {n,} 같은 수량자는 기본적으로 가능한 한 많이 먹어요. HTML 태그를 지우려고 <.+> 를 쓰면 이렇게 돼요.

const s = '<b>bold</b> and <i>it</i>';
s.match(/<.+>/)[0];    // '<b>bold</b> and <i>it</i>'  ← 전체가 하나
s.match(/<.+?>/g);     // ['<b>', '</b>', '<i>', '</i>']
s.match(/<[^>]+>/g);   // ['<b>', '</b>', '<i>', '</i>']

탐욕적 .+ 는 일단 줄 끝까지 다 먹은 다음, 뒤에 > 가 와야 하니까 한 글자씩 뱉으면서(백트래킹) 마지막 > 를 찾아요. 그래서 첫 < 부터 마지막 > 까지 한 덩어리가 돼요.

수량자 뒤에 ? 를 붙이면 게으른(lazy) 수량자가 돼서, 가능한 한 적게 먹고 조건이 맞는 순간 멈춰요. 세 번째처럼 부정 문자 클래스 [^>]+ 를 쓰면 애초에 > 를 먹지 않으니 결과는 같고 백트래킹도 거의 없어요. 저는 구분자가 명확하면 게으른 수량자보다 부정 문자 클래스를 먼저 써요. 의도가 더 분명하고 빠르거든요.

참고로 HTML을 정규식으로 파싱하는 건 이런 간단한 경우가 아니면 권하지 않아요. 속성 안의 >, 주석, 중첩 태그에서 금방 깨져요. 브라우저면 DOMParser, 서버면 HTML 파서 라이브러리를 쓰세요.

백트래킹이 폭발하는 순간: 재앙적 백트래킹

탐욕적이든 게으르든, 대부분의 정규식 엔진(JavaScript V8, Python re, Java, PCRE)은 백트래킹 방식으로 동작해요. 한 갈래로 가 보다가 실패하면 되돌아가서 다른 갈래를 시도하는 거죠. 보통은 문제없는데, 갈래의 수가 폭발하는 패턴이 있어요.

^(a+)+$

이 패턴에 aaaaaaaaaaaaaaaaaaaaaaaa! 처럼 a가 잔뜩 있고 끝에 엉뚱한 문자가 붙은 입력을 넣으면, 엔진은 "a 24개를 그룹 몇 개로 어떻게 나눌지"의 모든 경우를 시도한 뒤에야 실패를 선언해요. a가 n개면 나누는 방법이 2의 (n-1)제곱 가지예요. 글자 하나 늘 때마다 시간이 두 배가 되는 거죠. 직접 재 봤어요.

function time(re, input) {
  const t = process.hrtime.bigint();
  re.test(input);
  return Number(process.hrtime.bigint() - t) / 1e6;   // ms
}
for (const n of [16, 18, 20, 22, 24]) {
  console.log(n, time(/^(a+)+$/, 'a'.repeat(n) + '!').toFixed(1));
}

같은 의미의 ^a+$ 는 같은 입력에서 0.001ms도 안 걸려요. 결과는 똑같은데 패턴 모양 하나로 수십만 배 차이가 나는 거예요. 그리고 이 시간 동안 Node.js는 이벤트 루프 전체가 멈춰요. 다른 모든 요청이 그 정규식 하나를 기다리게 되죠. 공격자는 a 30개짜리 문자열 하나로 서버를 세울 수 있어요. 이게 ReDoS(Regular expression Denial of Service)예요.

게으른 버전 ^(a+?)+$ 도 확인해 봤는데, a 22개에서 240ms로 탐욕적 버전과 거의 같았어요. 시도하는 순서만 바뀔 뿐 실패할 때 모든 경우를 다 도는 건 똑같기 때문이에요. 파이썬이 V8보다 약 4배 느렸던 건 엔진 구현 차이일 뿐, 증가 곡선(2개당 4배)은 두 엔진이 똑같았어요. 즉 엔진을 바꾼다고 해결되는 문제가 아니라 패턴 모양의 문제예요.

실제 장애 사례: 클라우드플레어와 스택 오버플로

먼 얘기 같지만 큰 회사들도 당했어요.

• 스택 오버플로 (2016년 7월): 게시물 앞뒤 공백을 지우는 정규식 ^[\s‌]+|[\s‌]+$ 가 공백 2만 개 가까이 들어간 게시물 하나를 만나 백트래킹이 폭발했어요. 그 게시물이 홈페이지에 노출되면서 약 34분간 사이트가 멈췄어요.
• 클라우드플레어 (2019년 7월 2일): WAF 규칙에 들어간 .*(?:.*=.*) 류의 패턴이 전 세계 서버의 CPU를 100%로 만들어, 약 27분간 프록시 트래픽이 크게 실패했어요.

두 사례 모두 악의적인 입력이 아니라 평범한 데이터에서 터졌다는 게 무서운 점이에요. 공식 사후 분석 보고서가 공개돼 있어서, 정규식을 다루는 개발자라면 한 번쯤 읽어 볼 만해요.

위험한 정규식 모양 알아보기

코드 리뷰에서 이런 모양이 보이면 멈춰서 다시 봐요.

(a+)+          중첩 수량자 — 그룹 안에도 밖에도 반복
(\w+\s?)+      중첩 수량자 — 실무에서 가장 흔한 형태
(a|aa)+        겹치는 선택지 — 같은 문자열을 여러 방법으로 매치
(a|a?)+        겹치는 선택지
\d+\d+         겹치는 연속 수량자 — 경계를 어디에 둘지 n가지
.*.*=.*        겹치는 연속 수량자 — 클라우드플레어 사례

공통점은 같은 입력을 여러 가지 방법으로 쪼갤 수 있다는 거예요. 매칭이 성공하면 첫 번째 방법에서 끝나니 문제가 안 드러나요. 실패하는 입력이 와야 모든 방법을 다 시도하면서 폭발해요. 그래서 정상 데이터로 테스트하면 절대 안 잡히고, 운영에서 이상한 입력 하나에 터져요.

실무 예를 하나 들면, 이메일 검증용으로 인터넷에 돌던 이 패턴도 aaaaaaaaaaaaaaaaaaaaaaaaaa@ 같은 입력에서 a가 늘수록 급격히 느려졌어요(26자에서 약 95ms, 측정 환경 동일).

^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$

([a-zA-Z0-9]+)* 가 중첩 수량자예요. 검증용 정규식은 복잡할수록 정상 사용자도 막고(앞 글 정규식 입력 검증 함정 참고) 성능 위험도 커지니, 단순하게 쓰는 게 이중으로 이득이에요.

ReDoS 막는 방법 5가지

1. 겹치지 않게 패턴을 다시 쓴다

대부분 같은 의미를 더 단순하게 쓸 수 있어요.

핵심은 "각 글자가 패턴의 어느 부분에 해당하는지 한 가지로만 정해지게" 만드는 거예요.

2. 입력 길이를 먼저 자른다

지수 폭발은 길이가 짧으면 무해해요. 위 측정에서 16자는 1ms였어요. 이메일 254자, 이름 50자처럼 필드별 상한을 정규식 앞에서 검사하면 위험이 크게 줄어요. 가장 싸고 확실한 방어예요.

3. 선형 시간 엔진을 쓴다

RE2(구글), Go의 regexp, Rust의 regex 크레이트는 백트래킹 없이 입력 길이에 비례하는 시간을 보장해요. 대신 역참조(\1)와 일부 전후방 탐색을 지원하지 않아요. Node.js는 re2 npm 패키지로 쓸 수 있고, V8에도 실험적 선형 엔진이 있어요.

// node --enable-experimental-regexp-engine
const re = new RegExp('^(a+)+$', 'l');     // l = linear 플래그
re.test('a'.repeat(5000) + '!');           // false, 1ms 미만
new RegExp('(a)\\1', 'l');
// SyntaxError: Invalid regular expression: /(a)\1/l: Cannot be executed in linear time

4. 소유 수량자·원자 그룹을 쓴다

Java, PCRE, 그리고 Python 3.11 이상의 re 는 소유 수량자(a++)와 원자 그룹((?>...))을 지원해요. 한 번 먹은 건 되돌려주지 않아서 백트래킹 폭발을 원천 차단해요. JavaScript는 아직 지원하지 않아요.

5. 실행 시간을 제한한다

.NET은 Regex 생성자에 타임아웃을 줄 수 있어요. Node.js는 정규식 자체에 타임아웃이 없어서, 신뢰할 수 없는 패턴이나 입력은 워커 스레드에서 돌리고 시간이 지나면 종료하는 방식으로 격리해요. 사용자가 정규식 자체를 입력하는 기능(검색 필터 등)이 있다면 이 격리는 필수예요.

탐지 도구와 테스트 습관

• 정적 분석: ESLint의 eslint-plugin-regexp(no-super-linear-backtracking 규칙), safe-regex 같은 도구가 위험한 모양을 경고해 줘요. CI에 넣어 두면 리뷰에서 놓친 걸 잡아 줘요.
• 실패 입력으로 테스트: 정상 값만 넣지 말고, "거의 맞다가 마지막에 틀리는" 입력(a 30개 + !)을 꼭 넣어 보세요. 시간이 눈에 띄게 걸리면 위험 신호예요.
• 테스터에서 단계 수 보기: 정규식 테스터에서 입력 길이를 조금씩 늘려 가며 반응 속도가 급격히 변하는지 보면 감이 와요.

자주 묻는 질문

탐욕적 매칭과 게으른 매칭의 차이는 무엇인가요?

탐욕적 수량자(+, *)는 조건을 만족하는 한 가능한 한 많이 먹고, 게으른 수량자(+?, *?)는 가능한 한 적게 먹어요. <.+> 는 첫 < 부터 마지막 > 까지, <.+?> 는 가장 가까운 > 까지 잡아요. 구분자가 명확하면 <[^>]+> 같은 부정 문자 클래스가 더 빠르고 의도도 분명해요.

ReDoS란 무엇인가요?

정규식의 재앙적 백트래킹을 이용한 서비스 거부 공격이에요. 중첩 수량자 같은 패턴에 특정 입력을 넣으면 매칭 시간이 입력 길이에 따라 지수적으로 늘어나 CPU를 독점해요. Node.js처럼 단일 스레드 이벤트 루프 환경에서는 서버 전체가 멈출 수 있어요.

게으른 수량자를 쓰면 ReDoS가 해결되나요?

아니에요. 게으른 수량자는 시도 순서만 바꿀 뿐, 실패하는 입력에서 모든 경우를 시도하는 건 똑같아요. ^(a+?)+$ 도 똑같이 폭발해요. 패턴이 같은 문자열을 여러 방법으로 쪼갤 수 없도록 고치거나, 선형 시간 엔진을 써야 해요.

내 정규식이 ReDoS에 취약한지 어떻게 확인하나요?

중첩 수량자, 겹치는 선택지, 겹치는 연속 수량자 세 가지 모양이 있는지 먼저 보세요. 그다음 "거의 맞다가 마지막에 틀리는" 입력의 길이를 늘려 가며 실행 시간을 재 보면 확실해요. eslint-plugin-regexp 같은 정적 분석 도구를 CI에 넣는 것도 좋아요.

정규식이 느리면 무조건 RE2로 바꿔야 하나요?

사용자 입력이나 사용자 정의 패턴을 다루는 곳이라면 RE2 같은 선형 엔진이 가장 확실해요. 다만 역참조와 일부 전후방 탐색을 못 쓰니 패턴을 바꿔야 할 수 있어요. 내부 데이터만 다루는 곳이라면 패턴을 안전하게 고치고 입력 길이를 제한하는 것으로 충분한 경우가 많아요.

정리

탐욕적 수량자는 "많이 먹고 뱉는" 방식이라 너무 많이 잡히고, 게으른 수량자나 부정 문자 클래스로 고칠 수 있어요. 중첩 수량자처럼 같은 문자열을 여러 방법으로 쪼갤 수 있는 패턴은 실패 입력에서 지수적으로 느려져요. 직접 재 보니 ^(a+)+$ 는 a 24개에서 이미 0.26초(파이썬 1초)가 걸렸어요. 입력 길이 제한, 겹치지 않는 패턴, 선형 엔진 — 이 세 가지만 습관이 돼도 정규식 하나로 서버가 멈추는 일은 거의 없어요.

수량자 문법이 아직 낯설다면 정규식 기초 문법 치트시트부터 보시고, 패턴은 정규식 테스터에서 실패 입력까지 넣어 확인해 보세요.