Allocation of Resources Without Limits or Throttling
Detailed paths
Overview
qs is a querystring parser that supports nesting and arrays, with a depth limit.
Affected versions of this package are vulnerable to Allocation of Resources Without Limits or Throttling via improper enforcement of the arrayLimit option in bracket notation parsing. An attacker can exhaust server memory and cause application unavailability by submitting a large number of bracket notation parameters - like a[]=1&a[]=2 - in a single HTTP request.
PoC
const qs = require('qs');
const attack = 'a[]=' + Array(10000).fill('x').join('&a[]=');
const result = qs.parse(attack, { arrayLimit: 100 });
console.log(result.a.length); // Output: 10000 (should be max 100)
Remediation
Upgrade qs to version 6.14.1 or higher.
References
Regular Expression Denial of Service (ReDoS)
Detailed paths
Overview
minimatch is a minimal matching utility.
Affected versions of this package are vulnerable to Regular Expression Denial of Service (ReDoS) in the AST class, caused by catastrophic backtracking when an input string contains many * characters in a row, followed by an unmatched character.
Details
Denial of Service (DoS) describes a family of attacks, all aimed at making a system inaccessible to its original and legitimate users. There are many types of DoS attacks, ranging from trying to clog the network pipes to the system by generating a large volume of traffic from many machines (a Distributed Denial of Service - DDoS - attack) to sending crafted requests that cause a system to crash or take a disproportional amount of time to process.
The Regular expression Denial of Service (ReDoS) is a type of Denial of Service attack. Regular expressions are incredibly powerful, but they aren't very intuitive and can ultimately end up making it easy for attackers to take your site down.
Let’s take the following regular expression as an example:
regex = /A(B|C+)+D/
This regular expression accomplishes the following:
AThe string must start with the letter 'A'(B|C+)+The string must then follow the letter A with either the letter 'B' or some number of occurrences of the letter 'C' (the+matches one or more times). The+at the end of this section states that we can look for one or more matches of this section.DFinally, we ensure this section of the string ends with a 'D'
The expression would match inputs such as ABBD, ABCCCCD, ABCBCCCD and ACCCCCD
It most cases, it doesn't take very long for a regex engine to find a match:
$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCD")'
0.04s user 0.01s system 95% cpu 0.052 total
$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
1.79s user 0.02s system 99% cpu 1.812 total
The entire process of testing it against a 30 characters long string takes around ~52ms. But when given an invalid string, it takes nearly two seconds to complete the test, over ten times as long as it took to test a valid string. The dramatic difference is due to the way regular expressions get evaluated.
Most Regex engines will work very similarly (with minor differences). The engine will match the first possible way to accept the current character and proceed to the next one. If it then fails to match the next one, it will backtrack and see if there was another way to digest the previous character. If it goes too far down the rabbit hole only to find out the string doesn’t match in the end, and if many characters have multiple valid regex paths, the number of backtracking steps can become very large, resulting in what is known as catastrophic backtracking.
Let's look at how our expression runs into this problem, using a shorter string: "ACCCX". While it seems fairly straightforward, there are still four different ways that the engine could match those three C's:
- CCC
- CC+C
- C+CC
- C+C+C.
The engine has to try each of those combinations to see if any of them potentially match against the expression. When you combine that with the other steps the engine must take, we can use RegEx 101 debugger to see the engine has to take a total of 38 steps before it can determine the string doesn't match.
From there, the number of steps the engine must use to validate a string just continues to grow.
| String | Number of C's | Number of steps |
|---|---|---|
| ACCCX | 3 | 38 |
| ACCCCX | 4 | 71 |
| ACCCCCX | 5 | 136 |
| ACCCCCCCCCCCCCCX | 14 | 65,553 |
By the time the string includes 14 C's, the engine has to take over 65,000 steps just to see if the string is valid. These extreme situations can cause them to work very slowly (exponentially related to input size, as shown above), allowing an attacker to exploit this and can cause the service to excessively consume CPU, resulting in a Denial of Service.
Remediation
Upgrade minimatch to version 10.2.1 or higher.
References
Untrusted Search Path
Detailed paths
Overview
Affected versions of this package are vulnerable to Untrusted Search Path in resource detection code which executes ioreg, when the PATH environment variable is modified to include a malicious executable. An attacker can execute arbitrary code within the context of the application by placing a malicious binary earlier in the search path.
Note: This vulnerability is only exploitable on MacOS/Darwin systems.
Remediation
Upgrade go.opentelemetry.io/otel/sdk/resource to version 1.40.0 or higher.
References
Uncaught Exception
Detailed paths
Overview
fast-xml-parser is a Validate XML, Parse XML, Build XML without C/C++ based libraries
Affected versions of this package are vulnerable to Uncaught Exception in the numeric entity processing when parsing XML containing out-of-range entity code points. An attacker can cause the application to crash by submitting specially crafted XML input that triggers an uncaught exception.
Remediation
Upgrade fast-xml-parser to version 5.3.4 or higher.
References
XML Entity Expansion
Detailed paths
Overview
fast-xml-parser is a Validate XML, Parse XML, Build XML without C/C++ based libraries
Affected versions of this package are vulnerable to XML Entity Expansion in replaceEntitiesValue() when handling excessive DOCTYPE input. An attacker can cause excessive resource consumption and make the application unresponsive by submitting malicious XML input with large text entities referenced multiple times. This is a bypass for Billion Laughs protection in DocTypeReader.js, which prevents excessive referencing within and entity, but doesn't prevent repeated expansion of large entities.
Workaround
This vulnerability can be mitigated by disabling DOCTYPE parsing using the processEntities: false option.
PoC
const { XMLParser } = require('fast-xml-parser');
const entity = 'A'.repeat(1000);
const refs = '&big;'.repeat(100);
const xml = `<!DOCTYPE foo [<!ENTITY big "${entity}">]><root>${refs}</root>`;
console.time('parse');
new XMLParser().parse(xml);
console.timeEnd('parse');
Details
Denial of Service (DoS) describes a family of attacks, all aimed at making a system inaccessible to its intended and legitimate users.
Unlike other vulnerabilities, DoS attacks usually do not aim at breaching security. Rather, they are focused on making websites and services unavailable to genuine users resulting in downtime.
One popular Denial of Service vulnerability is DDoS (a Distributed Denial of Service), an attack that attempts to clog network pipes to the system by generating a large volume of traffic from many machines.
When it comes to open source libraries, DoS vulnerabilities allow attackers to trigger such a crash or crippling of the service by using a flaw either in the application code or from the use of open source libraries.
Two common types of DoS vulnerabilities:
High CPU/Memory Consumption- An attacker sending crafted requests that could cause the system to take a disproportionate amount of time to process. For example, commons-fileupload:commons-fileupload.
Crash - An attacker sending crafted requests that could cause the system to crash. For Example, npm
wspackage
Remediation
Upgrade fast-xml-parser to version 5.3.6 or higher.
References
Incorrect Regular Expression
Detailed paths
Overview
fast-xml-parser is a Validate XML, Parse XML, Build XML without C/C++ based libraries
Affected versions of this package are vulnerable to Incorrect Regular Expression in the entity parsing RegEx in DOCTYPE declarations. An attacker can inject arbitrary values that override built-in XML entities by crafting entity names containing ., which is interpreted as a regex wildcard, allowing malicious content to be substituted in place of standard entities when the XML is parsed and subsequently rendered or used in sensitive contexts.
Remediation
Upgrade fast-xml-parser to version 5.3.5 or higher.
References
Allocation of Resources Without Limits or Throttling
Detailed paths
Overview
qs is a querystring parser that supports nesting and arrays, with a depth limit.
Affected versions of this package are vulnerable to Allocation of Resources Without Limits or Throttling via the parseArrayValue function when the comma option is in use. An attacker can exhaust system memory by submitting a parameter containing a large number of comma-separated values, resulting in the allocation of excessively large arrays.
Note:
This is only exploitable if the comma option is explicitly set to true. arrayLimit is properly enforced for index and bracket notation.
PoC
const qs = require('qs');
const payload = 'a=' + ','.repeat(25); // 26 elements after split (bypasses arrayLimit: 5)
const options = { comma: true, arrayLimit: 5, throwOnLimitExceeded: true };
try {
const result = qs.parse(payload, options);
console.log(result.a.length); // Outputs: 26 (bypass successful)
} catch (e) {
console.log('Limit enforced:', e.message); // Not thrown
}
Remediation
Upgrade qs to version 6.14.2 or higher.
References
Prototype Pollution
Detailed paths
Overview
Affected versions of this package are vulnerable to Prototype Pollution via the _.unset and _.omit functions. An attacker can delete methods held in properties of global prototypes but cannot overwrite those properties.
Details
Prototype Pollution is a vulnerability affecting JavaScript. Prototype Pollution refers to the ability to inject properties into existing JavaScript language construct prototypes, such as objects. JavaScript allows all Object attributes to be altered, including their magical attributes such as __proto__, constructor and prototype. An attacker manipulates these attributes to overwrite, or pollute, a JavaScript application object prototype of the base object by injecting other values. Properties on the Object.prototype are then inherited by all the JavaScript objects through the prototype chain. When that happens, this leads to either denial of service by triggering JavaScript exceptions, or it tampers with the application source code to force the code path that the attacker injects, thereby leading to remote code execution.
There are two main ways in which the pollution of prototypes occurs:
Unsafe
Objectrecursive mergeProperty definition by path
Unsafe Object recursive merge
The logic of a vulnerable recursive merge function follows the following high-level model:
merge (target, source)
foreach property of source
if property exists and is an object on both the target and the source
merge(target[property], source[property])
else
target[property] = source[property]
When the source object contains a property named __proto__ defined with Object.defineProperty() , the condition that checks if the property exists and is an object on both the target and the source passes and the merge recurses with the target, being the prototype of Object and the source of Object as defined by the attacker. Properties are then copied on the Object prototype.
Clone operations are a special sub-class of unsafe recursive merges, which occur when a recursive merge is conducted on an empty object: merge({},source).
lodash and Hoek are examples of libraries susceptible to recursive merge attacks.
Property definition by path
There are a few JavaScript libraries that use an API to define property values on an object based on a given path. The function that is generally affected contains this signature: theFunction(object, path, value)
If the attacker can control the value of “path”, they can set this value to __proto__.myValue. myValue is then assigned to the prototype of the class of the object.
Types of attacks
There are a few methods by which Prototype Pollution can be manipulated:
| Type | Origin | Short description |
|---|---|---|
| Denial of service (DoS) | Client | This is the most likely attack. DoS occurs when Object holds generic functions that are implicitly called for various operations (for example, toString and valueOf). The attacker pollutes Object.prototype.someattr and alters its state to an unexpected value such as Int or Object. In this case, the code fails and is likely to cause a denial of service. For example: if an attacker pollutes Object.prototype.toString by defining it as an integer, if the codebase at any point was reliant on someobject.toString() it would fail. |
| Remote Code Execution | Client | Remote code execution is generally only possible in cases where the codebase evaluates a specific attribute of an object, and then executes that evaluation. For example: eval(someobject.someattr). In this case, if the attacker pollutes Object.prototype.someattr they are likely to be able to leverage this in order to execute code. |
| Property Injection | Client | The attacker pollutes properties that the codebase relies on for their informative value, including security properties such as cookies or tokens. For example: if a codebase checks privileges for someuser.isAdmin, then when the attacker pollutes Object.prototype.isAdmin and sets it to equal true, they can then achieve admin privileges. |
Affected environments
The following environments are susceptible to a Prototype Pollution attack:
Application server
Web server
Web browser
How to prevent
Freeze the prototype— use
Object.freeze (Object.prototype).Require schema validation of JSON input.
Avoid using unsafe recursive merge functions.
Consider using objects without prototypes (for example,
Object.create(null)), breaking the prototype chain and preventing pollution.As a best practice use
Mapinstead ofObject.
For more information on this vulnerability type:
Arteau, Olivier. “JavaScript prototype pollution attack in NodeJS application.” GitHub, 26 May 2018
Remediation
Upgrade lodash-es to version 4.17.23 or higher.
References
Prototype Pollution
Detailed paths
Overview
lodash is a modern JavaScript utility library delivering modularity, performance, & extras.
Affected versions of this package are vulnerable to Prototype Pollution via the _.unset and _.omit functions. An attacker can delete methods held in properties of global prototypes but cannot overwrite those properties.
Details
Prototype Pollution is a vulnerability affecting JavaScript. Prototype Pollution refers to the ability to inject properties into existing JavaScript language construct prototypes, such as objects. JavaScript allows all Object attributes to be altered, including their magical attributes such as __proto__, constructor and prototype. An attacker manipulates these attributes to overwrite, or pollute, a JavaScript application object prototype of the base object by injecting other values. Properties on the Object.prototype are then inherited by all the JavaScript objects through the prototype chain. When that happens, this leads to either denial of service by triggering JavaScript exceptions, or it tampers with the application source code to force the code path that the attacker injects, thereby leading to remote code execution.
There are two main ways in which the pollution of prototypes occurs:
Unsafe
Objectrecursive mergeProperty definition by path
Unsafe Object recursive merge
The logic of a vulnerable recursive merge function follows the following high-level model:
merge (target, source)
foreach property of source
if property exists and is an object on both the target and the source
merge(target[property], source[property])
else
target[property] = source[property]
When the source object contains a property named __proto__ defined with Object.defineProperty() , the condition that checks if the property exists and is an object on both the target and the source passes and the merge recurses with the target, being the prototype of Object and the source of Object as defined by the attacker. Properties are then copied on the Object prototype.
Clone operations are a special sub-class of unsafe recursive merges, which occur when a recursive merge is conducted on an empty object: merge({},source).
lodash and Hoek are examples of libraries susceptible to recursive merge attacks.
Property definition by path
There are a few JavaScript libraries that use an API to define property values on an object based on a given path. The function that is generally affected contains this signature: theFunction(object, path, value)
If the attacker can control the value of “path”, they can set this value to __proto__.myValue. myValue is then assigned to the prototype of the class of the object.
Types of attacks
There are a few methods by which Prototype Pollution can be manipulated:
| Type | Origin | Short description |
|---|---|---|
| Denial of service (DoS) | Client | This is the most likely attack. DoS occurs when Object holds generic functions that are implicitly called for various operations (for example, toString and valueOf). The attacker pollutes Object.prototype.someattr and alters its state to an unexpected value such as Int or Object. In this case, the code fails and is likely to cause a denial of service. For example: if an attacker pollutes Object.prototype.toString by defining it as an integer, if the codebase at any point was reliant on someobject.toString() it would fail. |
| Remote Code Execution | Client | Remote code execution is generally only possible in cases where the codebase evaluates a specific attribute of an object, and then executes that evaluation. For example: eval(someobject.someattr). In this case, if the attacker pollutes Object.prototype.someattr they are likely to be able to leverage this in order to execute code. |
| Property Injection | Client | The attacker pollutes properties that the codebase relies on for their informative value, including security properties such as cookies or tokens. For example: if a codebase checks privileges for someuser.isAdmin, then when the attacker pollutes Object.prototype.isAdmin and sets it to equal true, they can then achieve admin privileges. |
Affected environments
The following environments are susceptible to a Prototype Pollution attack:
Application server
Web server
Web browser
How to prevent
Freeze the prototype— use
Object.freeze (Object.prototype).Require schema validation of JSON input.
Avoid using unsafe recursive merge functions.
Consider using objects without prototypes (for example,
Object.create(null)), breaking the prototype chain and preventing pollution.As a best practice use
Mapinstead ofObject.
For more information on this vulnerability type:
Arteau, Olivier. “JavaScript prototype pollution attack in NodeJS application.” GitHub, 26 May 2018
Remediation
Upgrade lodash to version 4.17.23 or higher.
References
Inefficient Algorithmic Complexity
Detailed paths
Overview
golang.org/x/net/html is a package that implements an HTML5-compliant tokenizer and parser.
Affected versions of this package are vulnerable to Inefficient Algorithmic Complexity via the html.Parse function due to quadratic parsing complexity when processing certain inputs, which can lead to denial of service (DoS) if an attacker provides specially crafted HTML content.
Remediation
Upgrade golang.org/x/net/html to version 0.45.0 or higher.
References
Infinite loop
Detailed paths
Overview
golang.org/x/net/html is a package that implements an HTML5-compliant tokenizer and parser.
Affected versions of this package are vulnerable to Infinite loop via the html.Parse function. An attacker can cause resource exhaustion and disrupt service availability by submitting specially crafted HTML input that triggers an infinite parsing loop.
Remediation
Upgrade golang.org/x/net/html to version 0.45.0 or higher.
References
Improper Validation of Integrity Check Value
Detailed paths
Overview
Affected versions of this package are vulnerable to Improper Validation of Integrity Check Value for .idx and .pack files. An attacker can cause the application to consume corrupted files, leading to unexpected errors, due to checksums not being checked in the loadIdxFile() function.
Workaround
This vulnerability can be mitigated by running 'git fsck' from the git CLI to check for data corruption on a given repository.
Remediation
Upgrade github.com/go-git/go-git/v5/storage/filesystem to version 5.16.5 or higher.
References
Regular Expression Denial of Service (ReDoS)
Detailed paths
Overview
foundation-sites is a responsive front-end framework
Affected versions of this package are vulnerable to Regular Expression Denial of Service (ReDoS) due to inefficient backtracking in the regular expressions used in URL forms.
PoC
https://www.''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Details
Denial of Service (DoS) describes a family of attacks, all aimed at making a system inaccessible to its original and legitimate users. There are many types of DoS attacks, ranging from trying to clog the network pipes to the system by generating a large volume of traffic from many machines (a Distributed Denial of Service - DDoS - attack) to sending crafted requests that cause a system to crash or take a disproportional amount of time to process.
The Regular expression Denial of Service (ReDoS) is a type of Denial of Service attack. Regular expressions are incredibly powerful, but they aren't very intuitive and can ultimately end up making it easy for attackers to take your site down.
Let’s take the following regular expression as an example:
regex = /A(B|C+)+D/
This regular expression accomplishes the following:
AThe string must start with the letter 'A'(B|C+)+The string must then follow the letter A with either the letter 'B' or some number of occurrences of the letter 'C' (the+matches one or more times). The+at the end of this section states that we can look for one or more matches of this section.DFinally, we ensure this section of the string ends with a 'D'
The expression would match inputs such as ABBD, ABCCCCD, ABCBCCCD and ACCCCCD
It most cases, it doesn't take very long for a regex engine to find a match:
$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCD")'
0.04s user 0.01s system 95% cpu 0.052 total
$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
1.79s user 0.02s system 99% cpu 1.812 total
The entire process of testing it against a 30 characters long string takes around ~52ms. But when given an invalid string, it takes nearly two seconds to complete the test, over ten times as long as it took to test a valid string. The dramatic difference is due to the way regular expressions get evaluated.
Most Regex engines will work very similarly (with minor differences). The engine will match the first possible way to accept the current character and proceed to the next one. If it then fails to match the next one, it will backtrack and see if there was another way to digest the previous character. If it goes too far down the rabbit hole only to find out the string doesn’t match in the end, and if many characters have multiple valid regex paths, the number of backtracking steps can become very large, resulting in what is known as catastrophic backtracking.
Let's look at how our expression runs into this problem, using a shorter string: "ACCCX". While it seems fairly straightforward, there are still four different ways that the engine could match those three C's:
- CCC
- CC+C
- C+CC
- C+C+C.
The engine has to try each of those combinations to see if any of them potentially match against the expression. When you combine that with the other steps the engine must take, we can use RegEx 101 debugger to see the engine has to take a total of 38 steps before it can determine the string doesn't match.
From there, the number of steps the engine must use to validate a string just continues to grow.
| String | Number of C's | Number of steps |
|---|---|---|
| ACCCX | 3 | 38 |
| ACCCCX | 4 | 71 |
| ACCCCCX | 5 | 136 |
| ACCCCCCCCCCCCCCX | 14 | 65,553 |
By the time the string includes 14 C's, the engine has to take over 65,000 steps just to see if the string is valid. These extreme situations can cause them to work very slowly (exponentially related to input size, as shown above), allowing an attacker to exploit this and can cause the service to excessively consume CPU, resulting in a Denial of Service.
Remediation
There is no fixed version for foundation-sites.
References
Regular Expression Denial of Service (ReDoS)
Detailed paths
Overview
diff is a javascript text differencing implementation.
Affected versions of this package are vulnerable to Regular Expression Denial of Service (ReDoS) via the parsePatch() and applyPatch() functions if the user input passed without sanitisation. An attacker can cause the process to enter an infinite loop and exhaust system memory by providing a patch with filename headers containing \r, \u2028, or \u2029 characters or having control over patch's patch header for application generated patches.
Details
Denial of Service (DoS) describes a family of attacks, all aimed at making a system inaccessible to its original and legitimate users. There are many types of DoS attacks, ranging from trying to clog the network pipes to the system by generating a large volume of traffic from many machines (a Distributed Denial of Service - DDoS - attack) to sending crafted requests that cause a system to crash or take a disproportional amount of time to process.
The Regular expression Denial of Service (ReDoS) is a type of Denial of Service attack. Regular expressions are incredibly powerful, but they aren't very intuitive and can ultimately end up making it easy for attackers to take your site down.
Let’s take the following regular expression as an example:
regex = /A(B|C+)+D/
This regular expression accomplishes the following:
AThe string must start with the letter 'A'(B|C+)+The string must then follow the letter A with either the letter 'B' or some number of occurrences of the letter 'C' (the+matches one or more times). The+at the end of this section states that we can look for one or more matches of this section.DFinally, we ensure this section of the string ends with a 'D'
The expression would match inputs such as ABBD, ABCCCCD, ABCBCCCD and ACCCCCD
It most cases, it doesn't take very long for a regex engine to find a match:
$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCD")'
0.04s user 0.01s system 95% cpu 0.052 total
$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
1.79s user 0.02s system 99% cpu 1.812 total
The entire process of testing it against a 30 characters long string takes around ~52ms. But when given an invalid string, it takes nearly two seconds to complete the test, over ten times as long as it took to test a valid string. The dramatic difference is due to the way regular expressions get evaluated.
Most Regex engines will work very similarly (with minor differences). The engine will match the first possible way to accept the current character and proceed to the next one. If it then fails to match the next one, it will backtrack and see if there was another way to digest the previous character. If it goes too far down the rabbit hole only to find out the string doesn’t match in the end, and if many characters have multiple valid regex paths, the number of backtracking steps can become very large, resulting in what is known as catastrophic backtracking.
Let's look at how our expression runs into this problem, using a shorter string: "ACCCX". While it seems fairly straightforward, there are still four different ways that the engine could match those three C's:
- CCC
- CC+C
- C+CC
- C+C+C.
The engine has to try each of those combinations to see if any of them potentially match against the expression. When you combine that with the other steps the engine must take, we can use RegEx 101 debugger to see the engine has to take a total of 38 steps before it can determine the string doesn't match.
From there, the number of steps the engine must use to validate a string just continues to grow.
| String | Number of C's | Number of steps |
|---|---|---|
| ACCCX | 3 | 38 |
| ACCCCX | 4 | 71 |
| ACCCCCX | 5 | 136 |
| ACCCCCCCCCCCCCCX | 14 | 65,553 |
By the time the string includes 14 C's, the engine has to take over 65,000 steps just to see if the string is valid. These extreme situations can cause them to work very slowly (exponentially related to input size, as shown above), allowing an attacker to exploit this and can cause the service to excessively consume CPU, resulting in a Denial of Service.
Remediation
Upgrade diff to version 3.5.1, 4.0.4, 5.2.2, 8.0.3 or higher.
References
Insecure Randomness
Detailed paths
Overview
Affected versions of this package are vulnerable to Insecure Randomness due to its use of the hexoid() function in the generation of fingerprint IDs.
Remediation
Upgrade formidable to version 2.1.3, 3.5.3 or higher.
References
Regular Expression Denial of Service (ReDoS)
Detailed paths
Overview
brace-expansion is a Brace expansion as known from sh/bash
Affected versions of this package are vulnerable to Regular Expression Denial of Service (ReDoS) in the expand() function, which is prone to catastrophic backtracking on very long malicious inputs.
PoC
import index from "./index.js";
let str = "{a}" + ",".repeat(100000) + "\u0000";
let startTime = performance.now();
const result = index(str);
let endTime = performance.now();
let timeTaken = endTime - startTime;
console.log(`匹配耗时: ${timeTaken.toFixed(3)} 毫秒`);
Details
Denial of Service (DoS) describes a family of attacks, all aimed at making a system inaccessible to its original and legitimate users. There are many types of DoS attacks, ranging from trying to clog the network pipes to the system by generating a large volume of traffic from many machines (a Distributed Denial of Service - DDoS - attack) to sending crafted requests that cause a system to crash or take a disproportional amount of time to process.
The Regular expression Denial of Service (ReDoS) is a type of Denial of Service attack. Regular expressions are incredibly powerful, but they aren't very intuitive and can ultimately end up making it easy for attackers to take your site down.
Let’s take the following regular expression as an example:
regex = /A(B|C+)+D/
This regular expression accomplishes the following:
AThe string must start with the letter 'A'(B|C+)+The string must then follow the letter A with either the letter 'B' or some number of occurrences of the letter 'C' (the+matches one or more times). The+at the end of this section states that we can look for one or more matches of this section.DFinally, we ensure this section of the string ends with a 'D'
The expression would match inputs such as ABBD, ABCCCCD, ABCBCCCD and ACCCCCD
It most cases, it doesn't take very long for a regex engine to find a match:
$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCD")'
0.04s user 0.01s system 95% cpu 0.052 total
$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
1.79s user 0.02s system 99% cpu 1.812 total
The entire process of testing it against a 30 characters long string takes around ~52ms. But when given an invalid string, it takes nearly two seconds to complete the test, over ten times as long as it took to test a valid string. The dramatic difference is due to the way regular expressions get evaluated.
Most Regex engines will work very similarly (with minor differences). The engine will match the first possible way to accept the current character and proceed to the next one. If it then fails to match the next one, it will backtrack and see if there was another way to digest the previous character. If it goes too far down the rabbit hole only to find out the string doesn’t match in the end, and if many characters have multiple valid regex paths, the number of backtracking steps can become very large, resulting in what is known as catastrophic backtracking.
Let's look at how our expression runs into this problem, using a shorter string: "ACCCX". While it seems fairly straightforward, there are still four different ways that the engine could match those three C's:
- CCC
- CC+C
- C+CC
- C+C+C.
The engine has to try each of those combinations to see if any of them potentially match against the expression. When you combine that with the other steps the engine must take, we can use RegEx 101 debugger to see the engine has to take a total of 38 steps before it can determine the string doesn't match.
From there, the number of steps the engine must use to validate a string just continues to grow.
| String | Number of C's | Number of steps |
|---|---|---|
| ACCCX | 3 | 38 |
| ACCCCX | 4 | 71 |
| ACCCCCX | 5 | 136 |
| ACCCCCCCCCCCCCCX | 14 | 65,553 |
By the time the string includes 14 C's, the engine has to take over 65,000 steps just to see if the string is valid. These extreme situations can cause them to work very slowly (exponentially related to input size, as shown above), allowing an attacker to exploit this and can cause the service to excessively consume CPU, resulting in a Denial of Service.
Remediation
Upgrade brace-expansion to version 1.1.12, 2.0.2, 3.0.1, 4.0.1 or higher.