ReDoS - 정규식 한 줄이 서버를 세운다

인상착의가 두루뭉술하면 뒤져야 할 골목이 늘어난다. 그 늘어남에 한계가 없다는 게 문제다.

서버가 멈췄는데 요청은 한 건이다

증상부터 보자. 흔한 장애 그림과 생김새가 다르다.

• CPU가 한 코어에서 100%로 붙어 있다. 트래픽은 평소와 같다
• 응답이 끊겼는데 에러 로그가 없다. 예외가 안 났으니 남길 게 없다
• 데이터베이스도 외부 API도 멀쩡하다
• 문제의 요청은 딱 한 건이고, 겉보기에 이상한 데가 없다

이 그림의 이름이 ReDoS(Regular expression Denial of Service)다. 정규식 한 줄이 입력 하나를 받아 사실상 끝나지 않는 계산에 들어간 것이다.

파장은 서버 구조가 정한다. 자바스크립트 런타임처럼 한 스레드가 모든 요청을 처리하는 구조면 그 한 건이 서버 전체를 세운다. 스레드 풀을 쓰는 구조라면 요청 하나가 스레드 하나를 물고 놓지 않으므로, 그런 요청이 스레드 수만큼 들어오면 같은 결과가 된다.

같은 글자를 나누는 방법이 여럿이다

원인은 하나로 모인다. 한 문자열을 패턴이 받아들이는 길이 여러 개일 때 터진다.

(a+)+를 보자. 안쪽 a+는 a를 한 자 이상 먹고, 바깥 +는 그걸 한 번 이상 되풀이한다. 그럼 aaaa는 어떻게 받아들여지나.

(aaaa)          한 번에 넷
(aaa)(a)        셋 + 하나
(aa)(aa)        둘 + 둘
(aa)(a)(a)      …
(a)(aaa)
(a)(aa)(a)
(a)(a)(aa)
(a)(a)(a)(a)    하나씩 넷

여덟 가지다. 넷을 순서 있는 조각으로 나누는 방법이 그만큼이라는 뜻이고, 글자가 하나 늘 때마다 이 수는 두 배가 된다.

정상적인 경우라면 이게 문제가 안 된다. 첫 번째 길에서 매칭이 성공하면 나머지 일곱 가지는 볼 필요가 없다. 앞 글에서 본 그대로다 - 성공은 하나만 찾으면 끝난다. 문제는 실패할 때다.

글자 하나가 늘면 갈래가 두 배

교과서에 늘 나오는 예가 (a+)+$다. 여기에 a를 잔뜩 붙인 뒤 마지막에 ! 하나를 붙여 넣으면, $가 문자열 끝을 요구하는데 !가 걸려 있으니 어떤 나누기로도 성공할 수 없다.

그런데 엔진은 그 사실을 미리 알지 못한다. “안 된다”를 말하려면 여덟 가지든 백만 가지든 전부 해봐야 한다.

입력이 한 글자 늘 때마다 나누는 방법이 두 배가 된다. 그래서 스물몇 글자까지는 아무 일도 없다가, 몇 글자 더 늘어난 순간 서버가 멈춘다.

늘어나는 모양에 붙인 이름으로 말하면 이건 O(2ⁿ)이다. 실무에서 마주치는 성능 문제는 대개 두 배가 네 배가 되는 정도인데, 여기서는 한 글자에 두 배다. 그래서 이 문제는 “느려진다”가 아니라 “어느 순간 안 끝난다”로 나타난다.

실패해야만 터진다

이 성질 때문에 ReDoS는 테스트를 통과한다.

테스트에 넣는 값은 대개 정상 값이다. 정상 값은 매칭에 성공하고, 성공은 첫 길에서 끝나니 순식간이다. 개발할 때도 스테이징에서도 아무 일이 없다.

대가를 치르는 건 매칭에 실패하는 입력뿐이다. 그런데 실패하는 입력이 누구의 손에 있나. 입력 칸을 채우는 쪽이다. 그 사람이 사용자일 수도, 그렇지 않을 수도 있다.

정리하면 이렇다. 위험한 정규식은 평소에 아무 표시도 내지 않다가, 특정한 모양의 입력이 들어온 그 순간에만 모습을 드러낸다.

위험한 생김새는 몇 가지 안 된다

다행히 위험한 패턴의 생김새는 정해져 있다. 코드 리뷰에서 알아볼 수 있을 만큼 적다.

• 수량자 안에 수량자. (a+)+, (\d+)*, (\s*\w+)* 같은 꼴
• 겹치는 선택지. (a|a)*처럼 두 갈래가 같은 글자를 받는 경우. (\w|\d)+도 숫자를 양쪽이 다 받으므로 여기 해당한다
• 넓은 반복이 나란히. .*.*처럼 어디서 끊어도 되는 반복이 이어지는 경우

셋의 공통점은 하나다. 같은 글자를 받아들이는 길이 둘 이상이다. 이 모호함이 곧 갈래이고, 갈래가 겹쳐 쌓이면 두 배씩 늘어난다.

거꾸로 안전한 쪽도 분명하다. \d{2,3}-\d{3,4}-\d{4}처럼 나누는 방법이 하나뿐인 패턴은 아무리 길어도 위험하지 않다. 길이가 문제가 아니라 모호함이 문제다.

순경은 지치지만 엔진은 안 지친다

여기서 전단 비유가 완전히 깨진다. 그리고 이 깨짐이 이 글의 핵심이다.

순경은 지친다. 골목이 만 개라면 어느 시점에 그만두고 “못 찾았습니다”라고 보고한다. 사람이라 그렇게 된다.

엔진은 안 지친다. 백만 갈래든 조 단위 갈래든 하나씩 다 해본다. 멈추라고 말한 사람이 아무도 없기 때문이다. 정규식 한 줄에는 “여기까지만”이라고 적을 자리가 없고, 대부분의 언어는 기본값으로 상한을 두지 않는다.

그래서 방어의 절반은 알고리즘을 고치는 일이 아니라 멈추라고 말해 주는 일이다.

막는 법 - 입력, 시간, 엔진

방어는 세 층으로 깐다. 셋 다 서로를 대신하지 못한다.

첫째, 입력 길이를 먼저 자른다. 가장 싸고 가장 잘 듣는다. 시간이 길이에 대해 두 배씩 는다는 말은 뒤집으면 길이를 조금만 막아도 상한이 확 내려간다는 뜻이다. 이메일은 320자, 아이디는 32자, 검색어는 100자. 정규식에 넣기 전에 자른다.

둘째, 실행 시간에 상한을 준다. 정규식 실행에 타임아웃을 걸 수 있는 환경이면 그걸 쓴다(.NET의 Regex는 생성자에 타임아웃을 받는다). 언어가 지원하지 않으면 정규식을 도는 자리를 격리한다 - 별도 스레드나 워커에서 돌리고 시간이 넘으면 그 실행을 버리는 식이다. 자바나 자바스크립트 기본 엔진에는 실행 중간에 끊는 장치가 없어서, 이 경우 격리가 유일한 손이다.

셋째, 되돌아가지 않는 엔진을 고를 수 있다. PCRE·자바·자바스크립트 기본 엔진은 전부 백트래킹 방식이라 표현력이 넓은 대신 이 위험을 안고 간다. 반대편에 RE2 계열(구글 RE2, Go의 기본 regexp, 러스트 regex)이 있는데, 이쪽은 되돌아가지 않는 방식으로 만들어져 입력 길이에 비례하는 시간을 보장한다. 대신 역참조나 되돌아보기처럼 백트래킹이 있어야 되는 문법을 포기했다. 공짜가 아니라 표현력과 시간 보장을 맞바꾼 것이고, 어느 쪽이 맞는지는 그 정규식이 누구의 입력을 받느냐가 정한다.

여기에 더해 패턴 자체를 손보는 것이 근본이다. 문자 부류를 좁히고 앵커를 박아 모호함을 없애는 손질은 앞 글에 정리해 두었다.

실무에서: 어디로 새어 들어오나

내가 쓴 정규식만 보면 놓친다. 실제 사고는 대개 다음 넷 중 하나로 들어온다.

• 사용자 입력을 검증하는 정규식. 가장 흔하다. 이메일·URL·전화번호 검증 패턴은 대체로 길고 갈래가 겹친다
• 사용자가 올린 것을 파싱하는 정규식. 업로드한 CSV, 붙여 넣은 로그, 외부에서 받은 웹훅 본문
• 라이브러리에 딸려 온 정규식. 내가 안 썼는데 의존성 안에 있다. 마크다운 렌더러, User-Agent 파서, 검증 라이브러리에서 실제로 ReDoS 취약점이 여러 차례 공표됐다. 의존성 점검 도구가 알려 주는 항목에 이 종류가 섞여 있다
• 사용자가 정규식 자체를 입력하는 기능. 검색 필터나 규칙 편집기가 그렇다. 이건 패턴을 손볼 방법이 없으므로 되돌아가지 않는 엔진으로 돌리거나 기능을 접는 것 외엔 답이 없다

배치는 층으로 생각한다. 경계에서 길이를 자르고, 실행에 시간 상한을 두고, 그 앞에 넘치면 막는 장치를 두어 한 요청이 오래 걸리더라도 서비스 전체가 무너지지 않게 한다.

찾아내는 방법도 알아 두면 좋다. CPU가 붙어 있는데 에러 로그가 조용하면 이 그림을 의심한다. 그 순간 스레드 덤프를 뜨면 정규식 엔진 안쪽 프레임에 멈춰 있는 스레드가 보이고, 그 스택을 거슬러 올라가면 어느 패턴인지가 나온다.

정리

• ReDoS는 요청 한 건이 CPU를 붙들고 놓지 않는 장애다. 에러가 안 나서 로그로는 안 보인다.
• 원인은 하나다. 한 문자열을 받아들이는 길이 여러 개일 때 엔진이 그 길을 전부 확인한다.
• 그 갈래는 입력 한 글자마다 두 배가 된다. 그래서 “느려진다”가 아니라 “어느 순간 안 끝난다”로 나타난다.
• 성공하는 입력은 빠르다. 그래서 정상 값으로만 테스트하면 절대 안 잡힌다.
• 위험한 생김새는 셋뿐이다. 수량자 중첩, 겹치는 선택지, 넓은 반복의 나열. 전부 “같은 글자를 받는 길이 둘 이상”이다.
• 엔진은 지치지 않으므로 멈추라고 말해 줘야 한다. 입력 길이 제한, 실행 시간 상한, 되돌아가지 않는 엔진 순으로 깐다.

다음 글은 한 걸음 물러선다. 이렇게까지 조심해서 써야 한다면, 애초에 정규식을 쓰지 말아야 할 자리는 어디인가.