정규식 하나로 서버가 멈추는 경우

정규식은 대개 성능을 걱정하지 않고 씁니다. 그런데 입력 길이가 조금 늘었을 뿐인데 CPU 하나가 100%에 붙어 내려오지 않는 경우가 있습니다. 패턴의 모양과 엔진의 동작 방식이 겹칠 때 생기는 문제입니다.

엔진은 되돌아가며 시도한다

자바스크립트, 파이썬, 자바, PHP, 루비의 정규식 엔진은 백트래킹 방식입니다. 수량자를 만나면 일단 최대한 길게 먹고, 뒤가 맞지 않으면 한 글자씩 물러나며 다시 시도합니다.

a+b로 aaa를 검사한다고 하면, a+가 aaa를 먹었다가 b가 없어 실패하고, aa로 줄여 다시 시도하고, a까지 줄여 본 뒤 최종 실패합니다. 시도 횟수가 입력 길이에 비례합니다.

문제는 수량자가 중첩될 때입니다.

^(a+)+$

aaaaaaaaaaaaaaaaaaaaaaaaaaaaab 정도의 30자 입력이면 이미 수억 번입니다.

공통점은 같은 입력을 나누는 방법이 여러 가지라는 점입니다. 나누는 방법이 하나뿐이면 폭발하지 않습니다.

실제로 문제가 되는 자리는 정해져 있습니다. 사용자 입력을 검증하는 정규식, 로그나 User-Agent를 파싱하는 정규식, 업로드된 텍스트를 훑는 정규식입니다. 셋 다 길이와 내용을 공격자가 정할 수 있는 입력을 받습니다.

테스트에서 놓치는 이유는 대부분 매칭되는 입력만 넣어 보기 때문입니다. 성공하는 경로는 빨리 끝납니다. 백트래킹이 폭발하는 것은 거의 맞다가 마지막에 틀리는 입력입니다.

확인 방법은 단순합니다. 패턴에 맞는 문자열을 길게 만들고, 끝에 맞지 않는 문자 하나를 붙입니다. 길이를 20, 25, 30으로 늘리며 시간을 재 봅니다. 선형으로 늘면 문제없고, 길이 하나에 두 배씩 늘면 그 패턴은 쓰면 안 됩니다.

패턴을 바꿉니다. 중첩을 푸는 것이 가장 확실합니다. ^(a+)+$는 ^a+$와 결과가 같습니다. (\w+\s?)*처럼 쓴 것은 대개 [\w\s]*로 충분합니다.

원자적 그룹이나 소유 수량자를 씁니다. (?>a+)나 a++는 한 번 먹은 것을 되돌리지 않습니다. 자바, PCRE, 루비, .NET에서 쓸 수 있습니다. 자바스크립트에는 없어서 (?=(a+))\1 형태의 우회를 쓰지만 읽기 어려워집니다.

입력 길이를 먼저 자릅니다. 이메일이 254자를 넘을 수 없다면 정규식에 넣기 전에 길이부터 확인합니다. 지수 증가는 길이 제한 앞에서는 무력합니다.

타임아웃을 겁니다. .NET은 Regex 생성자에 타임아웃을 받고, 자바스크립트는 별도 워커에서 돌리는 방식이 필요합니다.

엔진을 바꿉니다. Go의 regexp와 러스트의 regex 크레이트는 RE2 계열이라 백트래킹을 하지 않습니다. 입력 길이에 선형으로 동작하는 것이 보장됩니다. 대신 역참조와 룩어라운드를 지원하지 않습니다.

이메일 검증이 대표적입니다. RFC를 정확히 따르는 정규식은 수천 자에 이르고, 인터넷에 도는 짧은 버전 상당수가 백트래킹에 취약합니다.

@가 하나 있고 앞뒤가 비어 있지 않은지 정도만 확인한 뒤, 실제 검증은 확인 메일을 보내는 것으로 하는 편이 정확하고 안전합니다. HTML, URL, JSON도 마찬가지로 전용 파서가 있습니다.

tools.onuel.dev의 정규식 테스터에서 패턴과 입력을 바꿔 가며 매칭 결과를 볼 수 있습니다. 길이를 늘린 실패 입력을 넣어 보면 위에서 말한 차이가 그대로 나타납니다.