Regex에서 Catastrophic Backtracking을 피하는 방법은?

API7.ai

December 17, 2020

Technology

정규 표현식의 Catastrophic Backtracking은 정규 표현식이 매칭할 때 너무 많은 역추적(backtracking)을 하여 100% CPU를 점유하고 정상적인 서비스를 차단하는 현상을 말합니다.

배경

저는 정규 역추적이 100% CPU를 유발하는 문제의 발견과 해결 과정을 상세히 설명한 글을 읽었습니다. 원본 글은 상당히 길며, 저는 이전에 OpenResty 개발 중에 비슷한 문제를 두 번 경험한 적이 있습니다.

여기서는 배경을 이해하는 데 시간을 들이지 않도록 간단히 요약하겠습니다.

  1. 대부분의 개발 언어에서 정규 표현식 엔진은 역추적 기반의 NFA(Thompson의 NFA가 아닌)로 구현됩니다.
  2. 역추적이 너무 많으면 100% CPU를 유발하는 치명적인 역추적(catastrophic backtracking)이 발생합니다.
  3. 온라인 환경에서 문제를 찾기 위해 gdb나 systemtap을 사용하여 덤프를 분석해야 합니다.
  4. 이러한 문제는 코드가 라이브되기 전에 발견하기 어렵고, 정규 표현식을 일일이 검토해야 합니다.

개발 관점에서 보면, 문제가 있는 정규 표현식을 수정하는 것이 결론입니다. 최대한 역추적 횟수를 제한하는 안전 메커니즘을 추가할 수 있습니다. 예를 들어 OpenResty에서는 다음과 같이 설정할 수 있습니다.

lua_regex_match_limit 100000;

이렇게 하면 치명적인 역추적이 발생하더라도 제한되어 CPU가 완전히 점유되지 않습니다.

이제 완벽해 보이나요? 개발 수준을 넘어 다른 차원에서 이 문제를 살펴보겠습니다.

공격자

단순히 한 대의 머신을 사용해 요청을 보내면 서버를 마비시킬 수 있습니다. 이는 해커에게 꿈의 핵무기와 같습니다. 이에 비해 DDoS는 약하고, 비용도 많이 듭니다.

이러한 공격은 **ReDoS(RegEx Denial of Service)**라는 이름으로 불립니다.

정규 표현식은 매우 광범위하게 사용되며 백엔드 서비스의 거의 모든 부분에 존재하기 때문에, 취약점을 찾아 이용할 기회가 많습니다.

예를 들어, 해커가 WAF에서 ReDoS 취약점을 발견하고 요청을 보내 WAF를 마비시킨다고 상상해보세요. 짧은 시간 내에 문제를 파악하기 어렵고, 심지어 공격인지도 모를 수 있습니다. 비즈니스를 유지하기 위해 WAF를 재시작하거나 일시적으로 종료할 수 있습니다. WAF가 작동하지 않는 동안 해커는 SQL 인젝션을 통해 데이터베이스를 탈취할 수 있습니다. 반면에 당신은 여전히 전혀 모를 수도 있습니다.

오픈소스 소프트웨어와 클라우드 서비스의 광범위한 사용으로 인해, 자신이 작성한 정규 표현식이 취약점이 없는지 확인하는 것만으로는 충분하지 않습니다. 이는 또 다른 주제이므로, 여기서는 우리가 통제할 수 있는 정규 표현식만 논의하겠습니다.

이러한 정규 표현식을 어떻게 발견할까요?

문제를 해결하는 첫 번째 단계는 문제를 찾는 것이며, 가능한 모든 문제를 찾으려고 노력하는 것입니다. 이를 안전하게 찾는 능력이라고도 합니다.

문제가 있는 정규 표현식을 수동으로 코드 리뷰를 통해 찾는 것은 신뢰할 수 없습니다. 대부분의 개발자는 보안 의식이 부족하며, 복잡한 정규 표현식에서 문제를 찾는 것은 어려울 수 있습니다.

이때 자동화 도구가 유용합니다.

다음 두 가지 자동화 방법을 사용하여 이 문제를 해결할 수 있습니다.

  • 정적 테스트

이러한 도구는 코드를 스캔하여 정규 표현식을 찾고, 특정 알고리즘에 따라 치명적인 역추적이 있는 정규 표현식을 찾아냅니다.

예를 들어, RXXR2는 논문에 기반한 알고리즘으로 구현되었으며, 정규 표현식을 ε-NFA로 변환한 후 검색합니다. 하지만 정규 표현식의 확장 구문을 지원하지 않아 누락이 발생할 수 있습니다.

  • 동적 퍼징

퍼즈 테스트는 일반적인 소프트웨어 테스트 방법으로, 대량의 무작위 데이터를 입력하여 소프트웨어 충돌, 메모리 누수 등을 감지합니다.

마찬가지로, 정규 표현식 테스트에서도 이 방법을 사용할 수 있습니다. 기존 정규 표현식을 기반으로 테스트 데이터를 생성하거나 완전히 무작위로 생성할 수 있습니다.

SlowFuzz는 오픈소스 도구 중 하나로, 논문에 기반한 알고리즘을 구현했습니다. 이 논문은 이 글의 끝에 나열되어 있습니다. 이 도구는 범용 도구이며, 정규 표현식의 구조에 대한 특별한 처리를 하지 않아 누락이 발생할 수 있습니다.

SDLFuzzer는 Microsoft가 몇 년 전에 개발한 ReDoS 탐지 도구이지만, 더 이상 유지보수되지 않습니다.

이 분야에서 선택할 수 있는 도구는 많지 않으며, 관심도 많지 않습니다. 그러나 정보를 검색하던 중, 난징 대학의 몇몇 교수와 박사들이 ReDoS에 관한 논문을 작성하고 도구 ReScue를 오픈소스로 공개한 것을 발견했습니다: https://2bdenny.github.io/ReScue/. 이 도구는 여러 오픈소스 프로젝트에서 ReDoS 취약점을 발견했습니다.

다음은 논문에서의 비교 테스트 결과입니다.

1.jpg

2.jpg

한 번에 해결할 수 있을까요?

이러한 도구를 사용하더라도 오탐과 미탐이 발생할 수 있습니다. 그렇다면 ReDoS를 한 번에 해결할 수 있는 방법이 있을까요?

그렇다면 문제의 근본으로 돌아가 답을 찾아야 합니다: 정규 엔진이 역추적을 사용하여 매칭을 수행한다는 것.

이 방식을 포기하면 되지 않을까요? 네, 이미 여러 다른 구현 방식의 정규 엔진이 존재하며, 이를 한 번에 해결할 수 있습니다. 이들은 모두 역추적을 포기하고 NFA/DFA 오토마톤 방식을 사용하여 구현합니다. 이 방식의 장점은 스트리밍 매칭에 적합하고 더 안전하다는 것이며, 단점은 역참조와 같은 많은 정규 표현식 확장 구문을 지원하지 않는다는 것입니다. 하지만 이러한 구문은 일반적으로 사용되지 않습니다.

  • Google RE2

Google의 RE2는 가장 완성도 높은 오픈소스 프로젝트 중 하나입니다. PCRE의 대부분 구문을 지원하며, Go, Python, Perl, Node.js 등 다양한 개발 언어 라이브러리 구현이 있어 시작 및 교체 비용이 매우 낮습니다.

Perl을 예로 들어 RE2가 치명적인 역추적 문제를 피할 수 있는지 살펴보겠습니다.

다음은 결과 비교 차트입니다.

3.jpg

코드는 다음과 같으며, 관심이 있다면 직접 시도해볼 수 있습니다.

time perl -e 'if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print("hit");}'

40.80s user 0.00s system 99% cpu 40.800 total

이 정규 표현식을 실행하는 데 40.8초가 걸리며, 이 동안 CPU는 99%를 점유합니다.

RE2를 사용하면 대조가 매우 명확합니다.

time perl -e 'use re::engine::RE2; if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print(" hit");}'

perl -e 0.00s user 0.00s system 34% cpu 0.011 total
  • Intel Hyperscan

Intel Hyperscan도 RE2와 유사한 정규 엔진이며, Perl, Python 등 다양한 언어 라이브러리가 있어 시작하기 어렵지 않습니다.

Intel의 관행에 따라, 더 많은 플랫폼에 바인딩되어 x86에서만 실행할 수 있습니다.

만약 독특한 이점이 있다면, Intel의 명령어 세트와 하드웨어와 더 잘 작동하여 성능을 개선할 수 있다는 점입니다. 예를 들어, 자사의 DPDK와 결합할 수 있습니다.

오픈소스 네트워크 침입 탐지 도구인 Snort도 이전 정규 엔진을 Hyperscan으로 교체했으므로, Snort에 익숙한 학생들은 시도해볼 수 있습니다.

확장

다음은 정규 표현식에 관한 몇 가지 논문입니다. 관심이 있다면 확장 자료로 읽어볼 수 있습니다.

  1. SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities: https://arxiv.org/pdf/1708.08437.pdf

  2. Static Analysis for Regular Expression Exponential Runtime via Substructural Logics: https://arxiv.org/abs/1405.7058.pdf

  3. ReScue: Crafting Regular Expression DoS Attacks: https://dl.acm.org/doi/10.1145/3238147.3238159

  4. Regular Expression Matching Can Be Simple And Fast: https://swtch.com/~rsc/regexp/regexp1.html

Tags:
Regex
Codec