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

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

---

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

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

---

I would sum it up as "A repetition of a repetition". The first example you listed is a good one, as it states "the letter a, one or more times in a row. This can again happen one or more times in a row".

What to look for in this case is combination of the quantifiers, such as * and +.

A somewhat more subtle thing to look out for is the third and fourth one. Those examples contain an OR operation, in which both sides can be true. This combined with a quantifier of the expression can result in a LOT of potential matches depending on the input string.

To sum it up, TLDR-style:

Be careful how quantifiers are used in combination with other operators.

---

What you call an "evil" regex is a regex that exhibits catastrophic backtracking. The linked page (which I wrote) explains the concept in detail. Basically, catastrophic backtracking happens when a regex fails to match and different permutations of the same regex can find a partial match. The regex engine then tries all those permutations. If you want to go over your code and inspect your regexes these are the 3 key issues to look at:

1. Alternatives must be mutually exclusive. If multiple alternatives can match the same text then the engine will try both if the remainder of the regex fails. If the alternatives are in a group that is repeated, you have catastrophic backtracking. A classic example is (.|\s)* to match any amount of any text when the regex flavor does not have a "dot matches line breaks" mode. If this is part of a longer regex then a subject string with a sufficiently long run of spaces (matched by both . and \s) will break the regex. The fix is to use (.|\n)* to make the alternatives mutually exclusive or even better to be more specific about which characters are really allowed, such as [\r\n\t\x20-\x7E] for ASCII printables, tabs, and line breaks.

2. Quantified tokens that are in sequence must either be mutually exclusive with each other or be mutually exclusive what comes between them. Otherwise both can match the same text and all combinations of the two quantifiers will be tried when the remainder of the regex fails to match. A classic example is a.*?b.*?c to match 3 things with "anything" between them. When c can't be matched the first .*? will expand character by character until the end of the line or file. For each expansion the second .*? will expand character by character to match the remainder of the line or file. The fix is to realize that you can't have "anything" between them. The first run needs to stop at b and the second run needs to stop at c. With single characters a[^b]*+b[^c]*+c is an easy solution. Since we now stop at the delimiter, we can use possessive quantifiers to further increase performance.

3. A group that contains a token with a quantifier must not have a quantifier of its own unless the quantified token inside the group can only be matched with something else that is mutually exclusive with it. That ensures that there is no way that fewer iterations of the outer quantifier with more iterations of the inner quantifier can match the same text as more iterations of the outer quantifier with fewer iterations of the inner quantifier. This is the problem illustrated in JDB's answer.

While I was writing my answer I decided that this merited a full article on my website. This is now online too.

---

I don't think you can recognize such regexes, at least not all of them or not without restrictively limiting their expressiveness. If you'd really care about ReDoSs, I'd try to sandbox them and kill their processing with a timeout. It also might be possible that there are RegEx implementations that let you limit their max backtracking amount.

---

I have surprisingly come across ReDOS quite a few times performing source code reviews. One thing I would recommend is to use a timeout with whatever Regular Expression engine that you are using.

For example, in C# I can create the regular expression with a TimeSpan attribute.

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");
}

This regex is vulnerable to denial of service and without the timeout will spin and eat resources. With the timeout, it will throw a RegexMatchTimeoutException after the given timeout and will not cause the resource usage leading to a Denial of Service condition.

You will want to experiment with the timeout value to make sure it works for your usage.

---

I would say this is related to the regex engine in use. You may not always be able to avoid these types of regexes, but if your regex engine is built right, then it is less of a problem. See this blog series for a great deal of information on the topic of regex engines.

Note the caveat at the bottom of the article, in that backtracking is an NP-Complete problem. There currently is no way to efficiently process them, and you might want to disallow them in your input.

---

Detecting evil regexes

1. Try Nicolaas Weideman's RegexStaticAnalysis project.
2. Try my ensemble-style vuln-regex-detector which has a CLI for Weideman's tool and others.

Rules of thumb

Evil regexes are always due to ambiguity in the corresponding NFA, which you can visualize with tools like regexper.

Here are some forms of ambiguity. Don't use these in your regexes.

1. Nesting quantifiers like (a+)+ (aka "star height > 1"). This can cause exponential blow-up. See substack's safe-regex tool.
2. Quantified Overlapping Disjunctions like (a|a)+. This can cause exponential blow-up.
3. Avoid Quantified Overlapping Adjacencies like \d+\d+. This can cause polynomial blow-up.

Additional resources

I wrote this paper on super-linear regexes. It includes loads of references to other regex-related research.

---

There are some ways I can think of that you could implement some simplification rules by running them on small test inputs or analyzing the regex's structure.

• (a+)+ can be reduced using some sort of rule for replacing redundant operators to just (a+)
• ([a-zA-Z]+)* could also be simplified with our new redundancy combining rule to ([a-zA-Z]*)

The computer could run tests by running the small subexpressions of the regex against randomly-generated sequences of the relevant characters or sequences of characters, and seeing what groups they all end up in. For the first one, the computer is like, hey the regex wants a's, so lets try it with 6aaaxaaq. It then sees that all the a's, and only the first groupm end up in one group, and concludes that no matter how many a's is puts, it won't matter, since + gets all in the group. The second one, is like, hey, the regex wants a bunch of letters, so lets try it with -fg0uj=, and then it sees that again each bunch is all in one group, so it gets rid of the + at the end.

Now we need a new rule to handle the next ones: The eliminate-irrelevant-options rule.

• With (a|aa)+, the computer takes a look at it and is like, we like that big second one, but we can use that first one to fill in more gaps, lets get ans many aa's as we can, and see if we can get anything else after we're done. It could run it against another test string, like `eaaa@a~aa.' to determine that.

• You can protect yourself from (a|a?)+ by having the computer realize that the strings matched by a? are not the droids we are looking for, because since it can always match anywhere, we decide that we don't like things like (a?)+, and throw it out.

• We protect from (.*a){x} by getting it to realize that the characters matched by a would have already been grabbed by .*. We then throw out that part and use another rule to replace the redundant quantifiers in (.*){x}.

While implementing a system like this would be very complicated, this is a complicated problem, and a complicated solution may be necessary. You should also use techniques other people have brought up, like only allowing the regex some limited amount of execution resources before killing it if it doesn't finish.

참고URL : https://stackoverflow.com/questions/12841970/how-can-i-recognize-an-evil-regex