정규식 한 줄로 CPU 가 100% 가 된다

입력 검증용 정규식을 하나 추가했어요. 이메일 형식을 확인하는 평범한 패턴이었고, 테스트도 다 통과했어요.

배포하고 며칠 뒤 서버 CPU 가 100% 로 붙어서 안 내려와요. 트래픽은 평소와 같아요. 특정 요청 몇 건이 들어온 시점부터 시작됐고요.

프로파일을 떠 보니 정규식 매칭에서 시간을 다 쓰고 있어요. 입력이 조금 긴 문자열 하나인데, 그거 하나를 검사하는 데 몇 분이 걸리고 있었어요.

정규식이 느린 게 아니에요. 특정 패턴과 특정 입력이 만나면 시간이 지수적으로 늘어나는 구조가 있고, 대부분의 언어가 그 구조를 그대로 쓰고 있습니다.

왜 그런가

많은 언어의 정규식 엔진은 역추적 방식으로 동작해요. 여러 갈래가 있으면 하나씩 시도해 보고, 실패하면 되돌아가 다음 갈래를 시도해요.

대부분의 패턴에서는 이게 문제가 안 돼요. 갈래가 몇 개 안 되니까요.

그런데 갈래가 곱해지는 패턴이 있어요. 반복 안에 반복이 들어가고 그 안의 조건이 겹치는 경우예요. 예를 들어 "여러 개가 반복되는 것"이 다시 "여러 번 반복"되는 형태요. 이때 문자열을 나누는 방법의 수가 길이에 따라 지수적으로 늘어나요.

그리고 매칭이 실패할 때 최악이 돼요. 성공하면 첫 번째로 찾은 갈래에서 끝나지만, 실패하려면 모든 갈래를 다 시도해 봐야 확신할 수 있거든요. 그래서 "거의 맞는데 마지막 한 글자가 틀린" 입력이 가장 나빠요.

30자짜리 문자열 하나가 수십억 번의 시도를 유발할 수 있어요. 입력 길이를 조금만 늘려도 시간이 배로 뛰고요.

여기서 중요한 게 있어요. 이건 사용자가 입력으로 유발할 수 있어요. 검색창, 회원 가입, 파일 이름, 심지어 헤더 값 하나로요. 악의가 없어도 우연히 걸릴 수 있고, 알고 하면 요청 한 건으로 서버를 멈출 수 있습니다.

코드로 보면

갈래가 곱해지는 형태를 피한다:

✕ ^(a+)+$          # 반복 안의 반복
✕ ^(\w+\s?)*$      # 겹치는 조건 + 반복
✕ 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!' 하나로 멈춘다

· 겹치지 않게 쓴다
✓ ^\w+(\s\w+)*$

· 애초에 정규식이 필요 없는 경우가 많다
✕ if re.match(r'^[^@]+@[^@]+\.[^@]+$', email)
✓ '@' 로 나눠 길이와 위치만 확인해도 충분하다

· 사용자 입력에는 길이 상한을 먼저 건다
✓ if len(s) > 256: reject
✓ 정규식보다 앞에 둔다

✕ 문제 지점 · ✓ 해법 · 그대로 돌려 보기 전에 자기 환경에 맞게 고쳐 주세요.

실전에서는

대응이 네 갈래예요.

첫째, 패턴을 고치는 것. 갈래가 겹치지 않게 쓰면 역추적이 폭발하지 않아요. 반복 안에 반복을 넣지 않고, 각 갈래가 서로 배타적이 되게 만들어요. 다만 이건 정규식을 잘 아는 사람이 검토해야 하고, 복잡한 패턴에서는 실수하기 쉬워요.

둘째, 입력 길이를 제한하는 것. 지수적 증가는 길이에 달려 있으니, 길이를 막으면 최악의 경우도 제한돼요. 가장 값싸고 확실한 방어예요. 그리고 검증 순서에서 정규식보다 앞에 두어야 의미가 있어요.

셋째, 정규식을 안 쓰는 것. 이메일 검증 같은 건 정규식으로 완벽하게 할 수 없어요. 표준을 정확히 따르는 패턴은 아주 복잡하고, 그 복잡함 자체가 위험이에요. 문자열을 나눠 확인하거나 검증된 라이브러리를 쓰는 편이 낫습니다.

넷째, 안전한 엔진을 쓰는 것. 역추적을 하지 않는 방식의 엔진들이 있어요. 입력 길이에 비례하는 시간을 보장하니 이 문제가 원천적으로 없어요. 대신 역참조 같은 일부 기능을 못 씁니다.

그리고 실행에 상한을 두는 방법도 있어요. 매칭에 시간 제한을 걸 수 있는 환경이면 그걸 쓰세요. 다만 언어와 런타임에 따라 지원 여부가 달라요.

여기서 조심할 게 하나 있어요. 위험한 패턴이 우리 코드에만 있는 게 아니에요. 라이브러리 안에도 있고, 설정 파일에도 있고, 사용자가 입력한 패턴을 그대로 실행하는 기능이 있다면 그건 더 직접적입니다.

처방

1. 사용자 입력에 길이 상한을 거세요. 정규식 검증보다 앞에 두어야 합니다. 가장 값싸고 확실한 방어예요.
2. 반복 안의 반복 패턴을 찾아 고치세요. 갈래가 겹치지 않게 쓰는 게 원칙이에요.
3. 정규식이 정말 필요한지 물어보세요. 문자열 나누기와 길이 확인으로 충분한 경우가 많아요.
4. 이메일 같은 표준 형식은 검증된 라이브러리를 쓰세요. 직접 짠 정규식이 가장 위험합니다.
5. 역추적하지 않는 엔진을 검토하세요. 입력 길이에 비례하는 시간이 보장됩니다.
6. 매칭에 시간 제한을 걸 수 있으면 거세요.
7. 사용자가 패턴을 입력하는 기능이 있다면 특히 주의하세요. 검색 필터 같은 곳이요.
8. 정적 분석 도구로 위험한 패턴을 찾으세요. 사람 눈으로는 잘 안 보입니다.
9. 최악의 입력으로 테스트를 만드세요. 정상 입력만으로는 절대 재현되지 않으니, 일부러 만든 악성 입력을 시간 제한과 함께 돌려야 합니다.
10. 검증 로직을 요청 처리 경로의 가장 앞에 두세요. 무거운 작업 뒤에 두면 이미 자원을 쓴 뒤에 거절하게 됩니다.

지금 확인해 보세요

위험한 패턴이 어디 있나:

· 코드에서 위험한 형태를 찾는다
✕ (x+)+  ·  (x*)*  ·  (x|x)*  ·  반복 안의 반복
✓ 정적 분석 도구를 CI 에 넣는 게 확실하다

· 최악의 입력으로 테스트한다
✓ 'a' * 30 + '!'  같은 입력을 시간 제한과 함께 실행
✓ 정상 입력만으로는 절대 안 나타난다

· CPU 가 튈 때 어디서 쓰는지
✓ 프로파일을 떠서 정규식 매칭이 상위에 있는지 본다

· 사용자 입력에 길이 상한이 실제로 걸려 있나
✕ 정규식보다 앞에 있어야 의미가 있다

· 라이브러리도 확인한다
✓ 로그 파서 · UA 분석기 · 마크다운 렌더러 · 검증 라이브러리

핵심 한 줄정규식은 입력 하나로 서버를 멈출 수 있다. 길이부터 막아라.