ReDoS

정규식 서비스 거부(ReDoS)^[1]는 알고리즘 복잡성 공격으로, 평가하는데 매우 오랜 시간이 걸리는 정규식을 제공함으로써 서비스 거부를 발생시킨다.공격은 대부분의 정규 표현식 구현이 입력 크기와 관련하여 걸리는 시간이 기하급수적으로 증가할 수 있다는 최악의 경우 복잡성을 가지고 있다는 사실을 악용한다.따라서 공격자는 속도가 느려지거나 응답하지 않게 됨으로써 프로그램이 이러한 정규식을 제공함으로써 무한의 시간 처리를 하게 할 수 있다.^[2][3]

설명

정규식("regex") 일치는 유한 상태 자동화를 구축하여 수행할 수 있다.Regex는 쉽게 비결정론적 자동자(NFA)로 변환할 수 있으며, 각 상태와 입력 기호에 대해 다음 몇 가지 상태가 있을 수 있다.자동화를 제작한 후 다음과 같은 몇 가지 가능성이 존재한다.

• 엔진은 이를 결정론적 유한 상태 자동화(DFA)로 변환하고 그 결과를 통해 입력을 실행할 수 있다.
• 엔진은 일치 항목이 발견되거나 모든 경로를 시도했다가 실패할 때까지 가능한 모든 경로를 하나씩 시도할 수 있다("역추적").^[4][5]
• 엔진은 비결정적 자동화를 통해 가능한 모든 경로를 병렬로 고려할 수 있다.
• 엔진은 비결정적 자동화를 느리게(즉, 경기 중에 즉시) DFA로 변환할 수 있다.

위의 알고리즘 중 처음 두 알고리즘은 문제가 있다.첫 번째는 결정론적 자동화가 $최대{\displaystyle }$ ${\displaystyle {2m}^{}}$ {\$displaystyle 2^{m}$ 상태일$$ 수 있으며, 여기서 m ${\displaystyle m}$은 비결정론적 자동화의 상태 수입니다. 따라서 NFA에서 DFA로의 변환은 기하급수적인 시간이 걸릴 수 있기 때문이다$.$두 번째는 비결정론적 자동화가 $길이{\displaystyle }$ n ${\displaystyle n}$의 기하급수적인 경로를 가질 수 있기 때문에 문제가 있으며$,$ 따라서 $길이{\displaystyle }$ n ${\displaystyle n}$의 입력을 통과하는 것도 기하급수적인 시간이 걸릴$$ 수 있다.^[6]그러나 마지막 두 알고리즘은 병리학적 동작을 나타내지 않는다.

비병리학적 정규식의 경우 문제가 있는 알고리즘은 대개 빠르며, 실제로는 Regex를 O(m) 시간에 "비교"하고 O(n) 시간에 일치시킬 것으로 기대할 수 있다. 대신 NFA 시뮬레이션과 DFA의 게으른 계산은 O(mn²) 최악의 경우 복잡성을 갖는다.^[7]Regex 서비스 거부는 이러한 기대를 사용자가 제공하는 regex에 적용할 때 발생하며, 사용자가 제공하는 악의적인 정규 표현은 regex 매처 최악의 경우 복잡성을 유발한다.

regex 알고리즘은 효율적인 방법으로 작성할 수 있지만, 현존하는 대부분의 regex 엔진은 항상 효율적으로 해결할 수 없는 추가적인 구성으로 regex 언어를 확장한다.이와 같이 확장된 패턴은 본질적으로 대부분의 프로그래밍 언어에서 역추적을 사용하도록 regex의 구현을 강요한다.

예

지수 역추적

가장 심각한 유형의 문제는 정규식 일치를 역추적할 때 발생한다. 이 경우 일부 패턴은 입력 문자열 길이에 지수적인 런타임을 가진다.^[8]$n{\displaystyle }$ ${\displaystyle n}$자$$ 문자열의 경우 런타임은 $O{\displaystyle }$( ${\displaystyle {2n}^{}}$) ${\displaystyle$ O$(2^{n}})$ 입니다$.$정규식이 세 가지 속성을 가질 때 이러한 현상이 발생한다.

• 정규식은 반복을 적용한다.+,*)를 하위 표현으로,
• 하위 표현은 여러 가지 방법으로 동일한 입력과 일치할 수 있으며, 하위 표현은 더 긴 가능한 일치의 접두사인 입력 문자열과 일치할 수 있다.
• 그리고 반복적인 하위표현 후에 하위표현과 일치하지 않는 무언가와 일치하는 표현이 있다.

두 번째 조건은 다음의 두 가지 예와 함께 가장 잘 설명된다.

• 에(a a)+$, 하위 표현에 반복 적용a a, 어느 정도 일치할 수 있는a교대 양쪽의 두 가지 방법으로
• 에(a+)*$, 반복이 하위표현을 적용한다.a+, 어느 정도 일치할 수 있는a또는aa, 등

이 두 예에서 모두 사용하였다.$세 번째 조건을 만족시키면서 문자열의 끝과 일치시키지만, 이것을 위해 다른 문자를 사용할 수도 있다.예를 들면(a aa)*c동일한 문제 구조를 가지고 있다.

$위$의 세 가지 정규식은 ${\displaystyle \mathrm{모두}}$ .${\displaystyle }$. . .${\displaystyle }$. . . . . . .$$. . . . . . . . .$.$ . .$$. . . . . . . . . . . . . . 예를 $들어$, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .aaaaaaaaaaaaaaaaaaaaaaaa!역추적 표현식 엔진에서는 완료하는 데 상당히 오랜 시간이 걸릴 것이며, 각 추가 시간에 대해 런타임은 대략 두 배가 될 것이다.a전에!.

또한 지수 대신 다항 시간 $O{\displaystyle ({}^{}}$ ${\displaystyle x^{}}$) ${\displaystyle O(n^{x}})$인 역추적이 가능하다$.$이것은 또한 상당한 효과를 가지려면 악의적인 입력이 훨씬 더 길어야 하기 때문에 이 문제에 덜 주의를 기울였음에도 불구하고 충분한 입력에 대한 문제를 야기할 수 있다.그러한 패턴의 예는 "이다.a*b?a*x", 입력이 임의로 긴 시퀀스인 경우 "a"s.

온라인 리포지토리의 취약한 정규식

온라인 정규 표현 저장소에서 이른바 '악'이나 악성 regex가 발견됐다.전체 정규식을 공격하려면 악의적인 하위 표현식을 찾기에 충분하다는 점에 유의하십시오.

1. RegExLib, id=1757(전자 메일 유효성 검사) - Evil Regex인 빨간색 부분 참조
   ^([a-zA-Z0-9])(([\-.] [_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3}) ([a-z]{2,3}[.]{1}[a-z]{2,3}))$
2. OWASP 유효성 검사 Regex 저장소, Java Classname - Evil Regex인 빨간색 부분을 참조하십시오.
   ^(([a-z])+.)+[A-Z]([a-z])+$

이 두 예는 또한 입력에 취약하다.aaaaaaaaaaaaaaaaaaaaaaaa!.

공격

regex 자체가 사용자 입력에 의해 영향을 받는 경우 공격자는 악의적인 regex를 주입하여 시스템을 취약하게 만들 수 있다.따라서 대부분의 경우 사용자가 서버에서 임의 패턴을 실행할 수 있는 가능성을 제거함으로써 정규식 서비스 거부를 피할 수 있다.이 경우 웹 애플리케이션과 데이터베이스는 주요 취약 애플리케이션이다.또는 악의적인 페이지는 사용자의 웹 브라우저를 걸거나 임의의 양의 메모리를 사용하도록 할 수 있다.

그러나 위 단락의 예시들 중 일부는 다른 예들에 비해 상당히 덜 "인공적"이므로, 프로그래밍 오류의 결과로 얼마나 취약한 regex가 사용될 수 있는지를 보여준다.이 경우 전자우편 스캐너와 침입 탐지 시스템도 취약할 수 있다.다행히 대부분의 경우 문제가 되는 정규식은 '비악' 문양으로 다시 쓸 수 있다.예를 들면(.*a)+에 다시 쓸 수 있다([^a]*a)+.

웹 어플리케이션의 경우 프로그래머는 시스템의 클라이언트와 서버 양쪽 모두에 대한 입력을 검증하기 위해 동일한 정규식을 사용할 수 있다.공격자는 클라이언트 코드를 검사하여 악의적인 정규식을 찾고 웹 서버로 직접 조작된 입력을 전송할 수 있다.

참고 항목

• 서비스 거부 공격
• 사이버워페어
• 저궤도 이온 대포
• 고궤도 이온 대포

참조

외부 링크

• 오픈 소스 애플리케이션의 RedDoS 예:
  • DataVault의 ReDoS
  • EntLib의 ReDoS
  • NASD Core에서 RedDoS.NET 테리릭
• RedDoS에 대한 벤치마크
  • 아킴 호프만(2010년)."ReDoS - JavaScript의 정규식 DoS 벤치마크"2010-04-19.
  • 리처드 M.스미스(2010년)."정규식 서비스 거부(ReDoS) 공격 테스트 결과"2010-04-19.
• ReDoS의 특정 계층에 취약하지 않은 정규 표현 구현에 관한 논문
  • 러스 콕스(2007)"정규 표현식 일치는 간단하고 빠를 수 있다."2011년 4월 20일 발견
• RedDoS 취약성 탐지 도구
  • H. 티에레케, A. 라트나야케(2013)."정규식 서비스 거부(ReDoS) 정적 분석"2013-05-30년 검색됨
  • B. 반 데어 머위, N 웨이드맨(2017년)."Regex 정적 분석".2017-08-12년 회수