Web security - DOS regular expression denial of service attack

Preface

Developers use regular expressions to verify the validity of the data entered by users , When writing regular expressions for verification has defects or is not rigorous , Attackers can construct special strings to consume a lot of system resources of the server , Cause the server's service to be interrupted or stopped .

Regular basis

About the syntax and use of regular expressions , See also Java- Regular expressions and Regular expressions - grammar , This article is just to expand .

1.1 Basic grammar

Regular expressions (Regular Expression, Regex) Is made up of characters ( It can be English letters 、 Numbers 、 Symbols etc. ) And metacharacters ( Special symbols ) A special string with specific rules . In pattern matching , Regular expressions are often used to validate mailboxes 、URL、 Mobile phone number, etc. .

Common metacharacters :

1.2 Regular cases

Regular expressions are a way to match （ In programming language ） String pattern . Here is an example to understand it , The example is “ Use regular expressions to verify email addresses on the server side ”.

It's a paragraph above JavaScript Code （ translator's note ： Can't JS Also just as well , It has little effect on reading this article , Please read on ）. The regular expression we use here is [a-z0–9][email protected][a-z]+\.[a-z]{2,3}. We provided several email addresses , Then we need to check whether they follow the general pattern of e-mail addresses . Let's decompose regular expressions .

• [a-z0–9]+： The string representing here can be any lowercase letter and number . The plus sign at the end (+) Indicates that there must be at least one character （ Whether it's lowercase letters or numbers ）.
• @： It means that there should be AT（@） operator .
• [a-z]+： Indicates that the string here should contain （ One or more ） Lowercase characters
• \.： Indicates that there should be a point here （.）
• [a-z]{2,3}： Indicates that the string here is composed of lowercase letters , But its length can only be 2 or 3.

Let's compare it with the email we choose ID Compare . Let email ID by [email protected]

• [email protected] Corresponding to [a-z0-9][email protected]
• yahooemail Corresponding to [a-z]+
• .com Corresponding to \.[a-z]{2,3}

This is usually how regular expressions work .

1.3 Greedy matching

If I want to match x and y All characters between , I can simply use x.*y To deal with , Be careful ,. Arbitrary character . therefore , The expression will successfully match x)dw2rfy character string .

however , By default , The repetition operator is greedy . They will try to match as many as possible . Let's consider the example above ,x.*y If the expression is for a string axaayaaya To deal with , It will return xaayaay. But users may not expect this result , They may only want strings xaay, such x<anything here>y The pattern of greedy matching is where greedy matching and non greedy matching work . By default , The expression will return the longest possible result , But we can use operators ? Specify it for non greedy matching , In this case, the expression is x.*?y.

1.4 Regular engine

Regular expression engines fall into two categories ： One is called DFA（ Deterministic finite state automata ）, The other is called NFA（ Non deterministic finite state automata ）. Two kinds of engines should work smoothly , There must be a regular form and a text string , Hold one in your hand , Eat one .

DFA Hold the text string to compare the regular form , I see a subregular , Mark all possible matching strings , And then look at the next part of the regular form , Update the annotation according to the new matching result .

and NFA Is holding the regular form to compare the text , Eat a character , Just compare it with the regular form , Make a note of the match ：“ On a certain day, a certain month, a certain year, it was matched ！”, Then go on . Once it doesn't match , Just spit out the character you just ate , One by one , Until I get back to the last match .

engine	difference	Language	How to match
DFA	Fast 、 Few characteristics	mysql etc.	Compare the text to regular
NFA	Slow speed 、 Many characteristics	python、java、php、ruby、.net、perl etc.	Compare text with regular

ReDos attack

2.1 Examples of defects

Please check the browser F12 The console of the developer tool executes the following regular expression matching statement , Feel the changes of the browser ：

/(a+)+z/.test('aaaaab')
/(a+)+z/.test('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab')

For the first statement , The browser will soon give the matching result false, But for the second statement , The browser allows no results for half an hour , And observe cpu In a high occupancy state , At the same time, the browser is currently Tab No response from page （ It can only be forced to close ）：

Such a simple regular match ,JS The engine is stuck “ Dead cycle ” In , The reasons will be explained below .

2.2 Calculation backtracking

Computers can be said to be very stupid when dealing with regular expressions , Although it seems that they have strong computing power . When you need to use a+z Expression to string aaaaaaaaaaaaaaab When you make a match , Anyone can quickly tell you that there is no match , Because this string does not contain characters z. But the regular expression engine of the computer doesn't know ！ It will do the following ：

above JS The regular expression matching process of the engine is called “ to flash back ”. You can see “ to flash back ” The efficiency of what you do is very low ……

If the regular expression is shown in the defect example above (a+)+z, The matching text is still aaaa……aaab Words , Follow the above regular backtracking process , The number of steps it needs to perform increases roughly as shown in the figure below ：

As mentioned to see , The number of calculation steps varies with the input string X The number of is increasing exponentially ……

Here is a website for online observation of regular matching process ：regular-expression-visualizer.

2.3 Defects are regular

The following is the problematic regular ：

//1) English personal name :
Regex: ^[a-zA-Z]+(([',.-][a-zA-Z ])?[a-zA-Z])$
Payload: aaaaaaaaaaaaaaaaaaaaaaaaaaaa!

//2)Email Format validation 
Regex: ^(0-9a-zA-Z@(([0-9a-zA-Z])+([-\w][0-9a-zA-Z])*.)+[a-zA-Z]{
    2,9})$
Payload: a@aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

//3) Complex number verification 
Regex: ^\d[0-9](|.\d[0-9]|)*$
Payload: 1111111111111111111111111!

//4) Pattern matching 
Regex: ^([a-z0-9]+([-a-z0-9][a-z0-9]+)?.){
    0,}([a-z0-9]+([-a-z0-9][a-z0-9]+)?){
    1,63}(.[a-z0-9]{
    2,7})+$
Payload: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

//5)DataVault:
Regex: ^[(,.)]$
Payload: [,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

//6)WinFormsAdvanced:
Regex: \A([A-Z,a-z]\s?[0-9][A-Z,a-z])\Z
Payload: aaaaaaaaaaaaaaaaaa!

//7)EntLib:
Regex: ^([^"]+)(?:\([^"]+))*$
Payload: \\\\\\\\\\\\\\\\“

We found the following rules ：

1. Regular expressions will repeat metacharacters （+、*） Apply to complex subexpressions .;
2. For subexpressions of repeated metacharacters , There is a match , At the same time, this match is also another valid suffix .

Simply put it into the following situations ：

(a+)+
([a-zA-Z]+)*
(a|aa)+
(a|a?)+
(.*a){
    x} for x > 10

2.4 Detection tools

ReDos Attacks often need to be combined with white box auditing to effectively find flawed regular expressions . So when the source code is known , How to quickly determine whether there is a problem with a regular expression ？

Direct up link ： Github regexploit, The installation is simple ：

The method of use is simpler ……

Enter the regular expression you want to detect , To determine whether there is ReDos attack , And give Payload.

summary

ReDos Defense against attacks ：

• Reduce the complexity of regular expressions , Try not to use groups ;
• Strictly limit the length of the string entered by the user ( In certain circumstances );
• Using unit tests 、fuzzing Testing ensures safety ;
• Use static code analysis tools , Such as : sonar;
• Add a server performance monitoring system , Such as : zabbix.

In this paper, the reference ：

1. Github regexploit;
2. A bloodbath caused by a regular expression （ Solution version ）;
3. Caused by regular expressions DoS attack （Redos）;
4. JavaScript Web The server ReDoS Vulnerability analysis ;
5. Regular redos attack , How a simple line of code makes the browser crash completely ！