[regex] 사악한 정규식을 어떻게 인식 할 수 있습니까?

Program / 글쓴이

나는 최근에 정규식 서비스 거부 공격에 대해 알게되었고 , 내 코드베이스에서 찾을 수있는 모든 곳에서 또는 적어도 사용자 입력에 사용되는 것이라면 소위 ‘사악한’정규식 패턴을 근절하기로 결정했습니다. 위 의 OWASP 링크 와 wikipedia에 제공된 예제 는 도움이되지만 문제를 간단한 용어로 설명하는 데는 그다지 효과적 이지 않습니다.

wikipedia 의 사악한 정규식에 대한 설명 :

  • 정규 표현식은 복잡한 하위 표현식에 반복 ( “+”, “*”)을 적용합니다.
  • 반복되는 하위 표현식의 경우 다른 유효한 일치의 접미사이기도 한 일치가 있습니다.

예를 들어 wikipedia 에서 다시 :

  • (a+)+
  • ([a-zA-Z]+)*
  • (a|aa)+
  • (a|a?)+
  • (.*a){x} x> 10 인 경우

더 간단한 설명이없는 문제입니까? 정규식을 작성하는 동안이 문제를 피하거나 기존 코드베이스 내에서 쉽게 찾을 수있는 것을 찾고 있습니다.

답변

왜 Evil Regexes가 문제입니까?

컴퓨터는 사용자가 말한대로 정확히 수행하기 때문에 그것이 의미하는 바가 아니거나 완전히 불합리한 경우에도 마찬가지입니다. Regex 엔진에 주어진 입력에 대해 주어진 패턴과 일치하는 것이 있는지 여부를 증명하도록 요청하면 엔진은 얼마나 많은 다른 조합을 테스트해야하는지에 관계없이이를 시도합니다.

다음은 OP 게시물의 첫 번째 예제에서 영감을 얻은 간단한 패턴입니다.

^((ab)*)+$

입력이 주어지면 :

아바 바바 바바 바바 바바 바바 바브

정규식 엔진은 다음과 같은 것을 시도 (abababababababababababab)하고 첫 번째 시도에서 일치하는 항목을 찾습니다.

그러나 우리는 원숭이 렌치를 넣습니다.

abababababababababababab a

엔진이 먼저 시도 (abababababababababababab)하지만 추가로 인해 실패합니다 a. 이것은 우리의 패턴이 (ab)*선의의 표시로 캡처 중 하나를 해제하고 ( “뒤로”) 외부 패턴이 다시 시도하도록 하기 때문에 치명적인 bracktracking을 유발 합니다. 정규식 엔진의 경우 다음과 같습니다.

(abababababababababababab)-아니오
(ababababababababababab)(ab)-아니오
(abababababababababab)(abab)-아니오
(abababababababababab)(ab)(ab)-아니오
(ababababababababab)(ababab)-아니오
(ababababababababab)(abab)(ab)-아니오
(ababababababababab)(ab)(abab)-아니오
(ababababababababab)(ab)(ab)(ab)-아니오
(abababababababab)(abababab)-아니오
(abababababababab)(ababab)(ab)-아니오
(abababababababab)(abab)(abab)-아니오
(abababababababab)(abab)(ab)(ab)-아니오
(abababababababab)(ab)(ababab)-아니오
(abababababababab)(ab)(abab)(ab)-아니오
(abababababababab)(ab)(ab)(abab)-아니오
(abababababababab)(ab)(ab)(ab)(ab)-아니오
(ababababababab)(ababababab)-아니오
(ababababababab)(abababab)(ab)-아니오
(ababababababab)(ababab)(abab)-아니오
(ababababababab)(ababab)(ab)(ab)-아니오
(ababababababab)(abab)(abab)(ab)-아니오
(ababababababab)(abab)(ab)(abab)-아니오
(ababababababab)(abab)(ab)(ab)(ab)-아니오
(ababababababab)(ab)(abababab)-아니오
(ababababababab)(ab)(ababab)(ab)-아니오
(ababababababab)(ab)(abab)(abab)-아니오
(ababababababab)(ab)(abab)(ab)(ab)-아니오
(ababababababab)(ab)(ab)(ababab)-아니오
(ababababababab)(ab)(ab)(abab)(ab)-아니오
(ababababababab)(ab)(ab)(ab)(abab)-아니오
(ababababababab)(ab)(ab)(ab)(ab)(ab)-아니오
                              …-
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abababab) 아니오
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ababab)(ab)-아니오
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(abab)-아니오
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(ab)(ab)-아니오
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ababab)-아니오
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(ab)-아니오
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)-아니오
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)-아니오

가능한 조합의 수는 입력의 길이에 따라 기하 급수적으로 확장되며, 정규식 엔진은 가능한 모든 용어 조합을 다 사용하고 결국 포기할 때까지이 문제를 해결하려는 모든 시스템 리소스를 소모합니다. “일치하는 항목이 없습니다.”라고보고합니다. 한편 서버는 타는 금속 더미로 변했습니다.

악한 정규식을 찾는 방법

실제로 매우 까다 롭습니다. 나는 그들이 무엇인지 그리고 일반적으로 그들을 피하는 방법을 알고 있지만 몇 가지를 직접 썼습니다. 놀랍도록 오래 걸리는 Regex를 참조하십시오 . 원자 그룹에 가능한 모든 것을 래핑 하면 역 추적 문제를 방지하는 데 도움이 될 수 있습니다. 기본적으로 정규식 엔진에 주어진 표현식을 다시 방문하지 않도록 지시합니다. “첫 번째 시도에서 일치하는 항목을 잠급니다”. 그러나 원자 식은 식 내 에서 역 추적을 방지하지 않으므로 ^(?>((ab)*)+)$여전히 위험하지만 ^(?>(ab)*)+$안전합니다 (일치 (abababababababababababab)한 다음 일치하는 문자를 포기하는 것을 거부하여 치명적인 역 추적을 방지 함).

불행히도 일단 작성되면 실제로 문제 정규식을 즉시 또는 빠르게 찾는 것이 매우 어렵습니다. 결국, 잘못된 정규식을 인식하는 것은 다른 잘못된 코드를 인식하는 것과 같습니다 . 많은 시간과 경험 및 / 또는 단일 재앙적인 이벤트가 필요합니다.

흥미롭게도이 답변이 처음 작성 되었기 때문에 텍사스 ​​대학교 오스틴의 한 팀은 이러한 “악한”패턴을 찾기위한 명시적인 목적으로 정규식의 정적 분석을 수행 할 수있는 도구의 개발을 설명하는 논문을 발표했습니다. 이 도구는 Java 프로그램을 분석하기 위해 개발되었지만 앞으로 몇 년 동안 특히 ReDoS 공격 비율이 계속 증가 함에 따라 JavaScript 및 기타 언어에서 문제 패턴을 분석하고 감지하는 데 더 많은 도구가 개발 될 것으로 예상 됩니다.

정규식
Valentin Wüstholz, Oswaldo Olivo, Marijn JH Heule 및 Isil Dillig 를 사용하는 프로그램에서 DoS 취약성의 정적 감지
The University of Texas at Austin

답변

“사악한”정규식이라고 부르는 것은 치명적인 역 추적 을 보여주는 정규식입니다 . 링크 된 페이지 (내가 작성한)는 개념을 자세히 설명합니다. 기본적으로 치명적인 역 추적은 정규식이 일치하지 않고 동일한 정규식의 다른 순열이 부분 일치를 찾을 수있을 때 발생합니다. 그런 다음 정규식 엔진은 이러한 모든 순열을 시도합니다. 코드를 검토하고 정규식을 검사하려면 다음과 같은 3 가지 주요 문제를 살펴 봐야합니다.

  1. 대안은 상호 배타적이어야합니다. 여러 대안이 동일한 텍스트와 일치 할 수있는 경우 엔진은 나머지 정규식이 실패하면 둘 다 시도합니다. 대안이 반복되는 그룹에 있으면 치명적인 역 추적이 발생합니다. 고전적인 예는 (.|\s)*정규식 플레이버에 “점과 줄 바꿈 일치”모드가 없을 때 모든 텍스트와 일치하는 것입니다. 이것이 더 긴 정규식의 일부인 경우 충분히 긴 공백이있는 제목 문자열 ( .및 모두 일치 \s)은 정규식을 중단합니다. 수정 사항은 (.|\n)*대체 항목을 상호 배타적으로 만들거나 [\r\n\t\x20-\x7E]ASCII 인쇄 가능 항목, 탭 및 줄 바꿈 과 같이 실제로 허용되는 문자에 대해 더 구체적으로 만드는 데 사용 하는 것 입니다.

  2. 순서대로 존재하는 수량화 된 토큰은 상호 배타적이거나 상호 배타적이어야합니다. 그렇지 않으면 둘 다 동일한 텍스트와 일치 할 수 있으며 나머지 정규 표현식이 일치하지 않을 때 두 수량 자의 모든 조합이 시도됩니다. 고전적인 예는 a.*?b.*?c3 개의 사물을 그 사이에 “무엇이든지”일치시키는 것입니다. c일치 할 수없는 경우 첫 번째 .*?는 행 또는 파일의 끝까지 문자별로 확장됩니다. 각 확장에 대해 두 번째 .*?는 줄 또는 파일의 나머지 부분과 일치하도록 문자별로 확장합니다. 해결책은 그들 사이에 “아무것도”를 가질 수 없다는 것을 깨닫는 것입니다. 첫 번째 실행은에서 중지해야 b하고 두 번째 실행은에서 중지해야합니다 c. 단일 문자로a[^b]*+b[^c]*+c쉬운 해결책입니다. 이제 구분자에서 멈췄으므로 소유 한정자를 사용하여 성능을 더 높일 수 있습니다.

  3. 한정자가있는 토큰을 포함하는 그룹은 그룹 내부의 정량화 된 토큰이 상호 배타적 인 다른 항목과 만 일치 할 수없는 경우 자체 한정자가 없어야합니다. 따라서 내부 한정자의 반복 횟수가 더 많은 외부 한정자의 반복 횟수가 더 적 으면 내부 한정자의 반복 횟수가 더 적은 외부 한정자의 반복 횟수와 동일한 텍스트와 일치 할 수있는 방법이 없습니다. 이것은 JDB의 대답에 설명 된 문제입니다.

내 답변을 작성하는 동안 나는 이것이 내 웹 사이트 의 전체 기사의 가치가 있다고 결정했습니다 . 이것도 이제 온라인입니다.

답변

나는 그것을 “반복의 반복”이라고 요약 할 것이다. 나열한 첫 번째 예는 “문자 a, 한 행에 한 번 이상입니다. 이것은 다시 한 번에 한 번 이상 발생할 수 있습니다.”라는 좋은 예입니다.

이 경우 찾아야 할 것은 * 및 +와 같은 한정 기호의 조합입니다.

주의해야 할 다소 미묘한 것은 세 번째와 네 번째입니다. 이러한 예에는 양쪽이 모두 참일 수있는 OR 연산이 포함됩니다. 이것은 표현식의 수량 자와 결합되어 입력 문자열에 따라 많은 잠재적 일치를 초래할 수 있습니다.

요약하면, TLDR 스타일 :

다른 연산자와 함께 수량자를 사용하는 방법에주의하십시오.

답변

놀랍게도 소스 코드 검토를 수행하면서 ReDOS를 꽤 많이 접했습니다. 내가 권장하는 한 가지는 사용중인 정규식 엔진에 제한 시간을 사용하는 것입니다.

예를 들어 C #에서는 TimeSpan특성이 있는 정규식을 만들 수 있습니다 .

string pattern = @"^<([a-z]+)([^<]+)*(?:>(.*)<\/\1>|\s+\/>)$";
Regex regexTags = new Regex(pattern, RegexOptions.None, TimeSpan.FromSeconds(1.0));
try
{
    string noTags = regexTags.Replace(description, "");
    System.Console.WriteLine(noTags);
}
catch (RegexMatchTimeoutException ex)
{
    System.Console.WriteLine("RegEx match timeout");
}

이 정규식은 서비스 거부에 취약하며 시간 초과가 없으면 리소스가 회전하고 소모됩니다. 시간 초과를 사용하면 RegexMatchTimeoutException주어진 시간 초과 후에를 발생시키고 리소스 사용으로 인해 서비스 거부 조건이 발생하지 않습니다.

시간 제한 값을 실험하여 사용에 적합한 지 확인해야합니다.

답변

악의적 인 정규식 감지

  1. Nicolaas Weideman의 RegexStaticAnalysis 프로젝트를 사용해보십시오 .
  2. Weideman의 도구 및 기타 도구에 대한 CLI가있는 앙상블 스타일의 vuln-regex-detector 를 사용해보십시오 .

경험의 규칙

악의적 인 정규식은 항상 해당 NFA의 모호성으로 인해 발생하며 regexper 와 같은 도구로 시각화 할 수 있습니다 .

여기에 몇 가지 형태의 모호성이 있습니다. 정규식에서 사용하지 마십시오.

  1. (a+)+(일명 “별 높이> 1”) 과 같은 중첩 수량 자 . 이로 인해 기하 급수적 인 폭발이 발생할 수 있습니다. 서브 스택의 safe-regex도구를 참조하십시오 .
  2. 같은 정량화 중복 분리 (a|a)+. 이로 인해 기하 급수적 인 폭발이 발생할 수 있습니다.
  3. 같은 정량화 된 중복 인접 항목을 피하십시오 \d+\d+. 이로 인해 다항식 폭발이 발생할 수 있습니다.

추가 자료

저는이 논문 을 초 선형 정규식에 대해 썼습니다 . 여기에는 다른 정규식 관련 연구에 대한 많은 참조가 포함됩니다.

답변

나는 이것이 사용중인 정규식 엔진과 관련이 있다고 말하고 싶습니다. 이러한 유형의 정규식을 항상 피할 수있는 것은 아니지만 정규식 엔진이 올바르게 구축 된 경우 문제가되지 않습니다. 정규식 엔진 주제에 대한 많은 정보는 이 블로그 시리즈 를 참조하십시오 .

백 트래킹은 NP-Complete 문제라는 점에서 기사 하단의주의 사항에 유의하십시오. 현재이를 효율적으로 처리 할 수있는 방법이 없으며 입력에서이를 허용하지 않을 수 있습니다.

답변

나는 당신이 그러한 정규식을 인식 할 수 있다고 생각하지 않는다. 적어도 그들 모두는 아니거나 표현력을 제한하지 않고서는 안된다. ReDoS에 대해 정말로 관심이 있다면 샌드 박스로 처리하고 시간 초과로 처리를 종료하려고합니다. 최대 역 추적 양을 제한 할 수있는 RegEx 구현이있을 수도 있습니다.