이메일 형식 검사 한 줄 때문에 서버 전체가 3초씩 멈춘 이유

문제 발생

회원가입 API에 오래전에 검색해서 붙여 둔 이메일 형식 검사가 있었습니다.

const EMAIL = /^([\w.-]+)*@([\w-]+\.)+[\w-]{2,}$/;

if (!EMAIL.test(req.body.email)) {
  return res.status(400).json({ message: '이메일 형식이 올바르지 않습니다.' });
}

테스트도 다 통과했고, 정상적인 이메일은 0.1ms도 안 걸렸습니다. 그런데 어느 날부터 몇 분 간격으로 모든 API 응답이 몇 초씩 통째로 멈췄습니다. 그때마다 CPU 코어 하나가 100%를 찍었고 DB는 한가했습니다. 멈춘 시각의 접근 로그를 맞춰 보니 매번 회원가입 요청이 하나씩 있었고, 이메일 칸에는 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!가 들어 있었습니다. a 31개에 느낌표 하나, 겨우 32글자였습니다. 같은 값을 직접 보내 보니 응답까지 2.9초가 걸렸고, 그사이 보낸 헬스 체크도 2.7초를 기다렸습니다.

원인 분석

보통 정규식은 입력을 한 번 훑으면 끝나지만, 어떤 패턴은 그렇지 않습니다. Node.js의 "Don't Block the Event Loop" 문서가 이 경우를 따로 다룹니다. 대부분은 입력 길이에 비례하는 O(n)이지만 어떤 경우에는 O(2ⁿ)이 될 수 있고, 그러면 입력에 글자 하나만 더해도 엔진이 확인해야 하는 경로가 두 배가 된다고요.

([\w.-]+)*가 바로 그 경우였습니다. 안쪽 +와 바깥 *가 겹쳐 있어서 aaaa를 (aaaa)로도, (a)(aaa)로도, (aa)(aa)로도 나눌 수 있습니다. a가 n개면 나누는 방법이 2ⁿ⁻¹가지입니다. 끝의 ! 때문에 결국 @를 못 찾고 실패하는데, 엔진은 나누는 방법을 전부 바꿔 보기 전까지는 실패라고 단정하지 못합니다. Node.js 문서가 첫 번째로 꼽는 규칙이 (a+)* 같은 중첩 수량자를 피하라는 것이고, OWASP가 위험한 정규식으로 드는 예시에도 우리 패턴과 거의 같은 ([a-zA-Z]+)*$가 있습니다.

직접 재 보니 a가 25개면 51ms, 28개면 0.37초, 30개면 1.5초, 32개면 5.9초였습니다. 정말로 한 글자마다 두 배씩 늘었습니다.

정상 입력으로는 절대 드러나지 않습니다. 같은 문서는 취약한 정규식이라도 매칭에 성공할 때는 보통 문제가 없고, 지수 시간은 실패하는 입력에서 엔진이 여러 경로를 다 시도할 때 생긴다고 설명합니다. 테스트에 넣은 이메일은 전부 올바른 형식이었으니 한 번도 걸릴 일이 없었던 겁니다.

그동안 서버 전체가 멈춥니다. JavaScript는 한 스레드에서 실행되니 정규식이 도는 동안 이벤트 루프가 거기 묶입니다. 문서도 이런 공격 하나 때문에 다른 모든 클라이언트가 차례를 얻지 못한다고 적어 둡니다. 32바이트짜리 요청 하나로 서버를 3초씩 세울 수 있다는 뜻입니다. 규모만 다를 뿐 2019년 7월 Cloudflare 장애도 같은 원인이었습니다. WAF 규칙의 정규식 하나가 과도하게 백트래킹하면서 HTTP 처리용 CPU를 다 써 버렸고, 27분 동안 502 오류가 났습니다.

해결 방안

1. 반복 안에 겹치는 반복을 넣지 않습니다. 앞부분은 ([\w.-]+)*를 [\w.-]+로 바꾸면 의미는 같고, 나누는 방법이 하나뿐이라 실패도 바로 확정됩니다.

const EMAIL = /^[\w.-]+@([\w-]+\.)+[\w-]{2,}$/;

도메인 쪽 ([\w-]+\.)+도 모양은 반복 안의 반복이지만, 그룹마다 반드시 .으로 끝나야 하고 .은 [\w-]에 들어가지 않아서 나누는 방법이 하나로 정해집니다. 모양보다 겹치는지를 봐야 합니다. 바꾼 정규식에 a 10만 개짜리 공격 입력을 넣어도 0.3ms에 끝났습니다.

2. 이메일이라면 브라우저와 같은 기준을 씁니다. MDN의 input type="email" 문서는 브라우저가 아래 정규식과 같은 알고리즘으로 형식을 검사한다고 소개합니다. 수량자에 상한({0,61})이 있고 겹치는 반복이 없어서, 앞에서 쓴 공격 입력들을 10만 자까지 늘려도 3ms를 넘지 않았습니다. 프론트의 type="email"과 서버의 판정이 같아진다는 장점도 있습니다.

const EMAIL = /^[\w.!#$%&'*+/=?^`{|}~-]+@[a-z\d](?:[a-z\d-]{0,61}[a-z\d])?(?:\.[a-z\d](?:[a-z\d-]{0,61}[a-z\d])?)*$/i;

3. 입력 길이를 먼저 자르되, 그것만 믿지 않습니다. Node.js 문서도 복잡한 작업이라면 입력에 상한을 두고 너무 긴 입력은 거부하라고 권합니다. 다만 지수 시간이 나는 패턴 앞에서는 길이 제한이 거의 소용없습니다. 이번 공격은 32글자였습니다. 길이 제한은 1, 2번을 한 다음에 덧대는 장치입니다.

4. 린터로 미리 잡습니다. eslint-plugin-regexp의 regexp/no-super-linear-backtracking 규칙은 지수적, 다항식 백트래킹이 생길 수 있는 정규식을 잡아내고, 추천 설정(recommended)에 들어 있습니다. Node.js 문서가 소개하는 safe-regex 같은 검사 도구도 있지만, 문서 스스로 이런 도구가 취약한 정규식을 전부 잡지는 못한다고 적어 둡니다. 정규식을 새로 넣을 때는 실패하는 긴 입력으로 한 번 재 보는 습관이 제일 확실했습니다.

5. 안전망으로 V8의 선형 엔진을 쓸 수 있습니다. V8 블로그에 따르면 V8 8.8부터 백트래킹을 하지 않는 실험적 엔진이 들어 있고, --enable-experimental-regexp_engine-on-excessive-backtracks 플래그를 켜면 백트래킹이 일정 횟수(기본 5만 번)를 넘었을 때 그 엔진으로 넘어갑니다. Node 22에서 이 플래그를 켜고 같은 공격을 보내니 3.07초가 0.6ms로 줄었습니다. 다만 역참조나 전후방 탐색이 있거나 i, u 플래그가 붙은 정규식에는 적용되지 않고, 이름 그대로 실험적인 기능입니다. 정규식을 아주 많이 다룬다면 Node.js 문서가 소개하는 node-re2(RE2 엔진)도 선택지인데, V8 정규식과 100% 호환되지는 않으니 바꾸기 전에 회귀 테스트가 필요합니다.

공식 문서

• Node.js: Don't Block the Event Loop — REDOS
• OWASP: Regular expression Denial of Service — ReDoS
• MDN: input type="email" — Validation
• eslint-plugin-regexp: no-super-linear-backtracking
• V8: An additional non-backtracking RegExp engine
• Cloudflare: Details of the Cloudflare outage on July 2, 2019