DeepCode’s Top Findings#5: JavaScript Unsanitized Input is used to build RegEx
Published: 2020-01-14 07:25:57


**Language:** JavaScript
**Defect:** Input Data/Sanitization (Category Security 1)
**Diagnose:** Unsanitized user input flows from the document location and is used to build a regular expression in RegExp. This may result in a Regular expression Denial of Service attack (reDOS).

We find this bug in three.js - you can use the dashboard in [deepcode.ai](https://deepcode.ai) to load *mrdoob/three.js* and follow along. I am using this example as I do not want to expose a real vulnerability but still make my point. As this here is a local script, it should only affect the attacker's machine.

##Background

We will see two interesting things here: (1) How DeepCode uses a data flow analysis to perform what is called a [*taint analysis*](https://en.wikipedia.org/wiki/Taint_checking) and (2) how it reasons about its findings.

Ok, let us start. We have a function that extracts and trims the part of the request URL which includes a question mark to signal a query (line 52 to 64 of the source file).

```
...
function extractQuery() {

			var p = window.location.search.indexOf( '?q=' );

			if ( p !== - 1 ) {

				return window.location.search.substr( 3 );

			}

			return '';

		}
...
```
So, a query like `https://my.web.server/site/page?q=/^(a|aa)+$/` could result in `/^(a|aa)+$/` ([query strings are very forgiving](https://stackoverflow.com/questions/2366260/whats-valid-and-whats-not-in-a-uri-query) ) as the result of calling this function. We see why this is of importance in a bit.

The result of this function will be whatever comes from the user. DeepCode infers that we have incoming data directly from the user in an [unsanitized way](https://wiki.sei.cmu.edu/confluence/display/java/Input+Validation+and+Data+Sanitization). By this we mean the data was not transformed to ensure trustworthiness (e.g., encoding, escaping). Closely related is *validation* where data that does not fit into the desired pattern is rejected. So this data is treated as *tainted*. How does the DeepCode engine infer this is incoming external user data? We use machine learning algorithms applied to thousands of open source projects to identify sources (API functions) of user data. In the same vein, DeepCode learns how such data is typically sanitized before it can be used safely. 


In line 213, it continues...
```
		function updateFilter() {

			var v = filterInput.value;

			...

			var exp = new RegExp( v, 'gi' );

			for ( var key in files ) {

				var section = files[ key ];

				for ( var i = 0; i < section.length; i ++ ) {

					filterExample( section[ i ], exp );

				}

			}
			...
		}

```

As you can see, here the property `value` of the global `filterInput` is assigned to a local variable `v`, which is then used to generate a new regular expression that is then used to provide a selection within an array. So far, so innocent.

In line 318, we find...

```
	...
	filterInput.value = extractQuery();
        ...
        updateFilter();
	...
```

And here it finally all comes together. The tainted data as a result of `extractQuery()` gets assigned to a property of a complex type which is then used inside the function that is called later without prior sanitization. So, finally tainted data gets used to generate a regular expression. An attacker could provide what is called an *evil regex* which can get stuck (aka Denial of Service by overloading the machine). `/^(a|aa)+$/g` (remember our example from above?) is such a regex element for the input *aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!* - try it yourself on [regexr.com](https://regexr.com/). The necessary number of `a`s depends on your machine. Play around and see that the runtime roughly doubles with each additional `a`s until it reaches 250ms where regexr cuts off.

DeepCode argues correctly and provides the argument in a sentence: 

> Unsanitized user input **flows** from **the document location** and is used to build a regular expression in **RegExp**. This may result in a Regular expression Denial of Service attack (reDOS).

![DeepCode Output](https://miro.medium.com/max/626/1*l40aXys9kRrUWJcpERuY_Q.png)

Note: The **bold** parts can be hovered over in the dashboard which will set the focus of the window on the object in question.

Knowing the source (here `window.location`) and the data sink (here `RegEx`), DeepCode formulates the correct argumentation. Finally, DeepCode provides you a *more info* link (here [OWASP - Regular expression Denial of Service](https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS) ) and three examples from other open-source projects to show how those treated the same type of issue. 

Using our machine learning approach, the system classifies sources of tainted data, possible sanitization functions, and data sinks - in this case, generators of regular expressions. DeepCode is able to track tainted data flowing through your application even in cases like this where the literal wanders through several variables.

Secure-coding conventions require to sanitize all user input before using it. There are existing and proven sanitization libraries available ([available npm packages as an example](https://www.npmjs.com/search?q=keywords:sanitization)). 

CU

0xff

PS: A [paper on taint analysis by colleagues from DeepCode](https://files.sri.inf.ethz.ch/website/papers/scalable-taint-specification-inference-pldi2019.pdf)
PPS: An [earlier article on a similar issue by Victor Chibotaru](https://medium.com/crowdbotics/fantastic-vulnerabilities-and-where-to-find-them-part-1-how-to-xss-using-django-form-errors-9b4a1d97a5bb)