LGTM.com - false positive javascript/ql/src/Performance/ReDoS.ql

[yarikoptic]

Description of the false positive

Happened on
https://github.com/sparkletown/sparkle/pull/1443/files#diff-06ebbfcf8e627f41bd6b15a2648431dc8a5dfd21f7d64f9bc798ed55051c0c58R97
with code

.match(/("[^"]*?"|[^"\s]+)+(?=\s*|\s*$)/g) 

stating:

Inefficient regular expression

This part of the regular expression may cause exponential backtracking on strings
containing many repetitions of '!'.

although regular expression does not have any ! and I am not aware of any special handling of ! in the source string which should somehow trigger such behavior.

URL to the alert on the project page on LGTM.com

unfortunately I am just a contributor and do not have access to those. May be @0xdevalias could help.

and here is the webshot

[0xdevalias]

Extra context that @yarikoptic was unable to provide:

URL to the alert on the project page on LGTM.com

This alert was shown in the GitHub UI rather than on LGTM.com, not sure if that changes things at all?

It was shown inline on this file:

• https://github.com/sparkletown/sparkle/pull/1460/files#diff-712ffc191bdeefcad981f5da7c2bb1550371e10c6854ed1b624ec4f415f7686e

And linked through to:

• https://github.com/sparkletown/sparkle/security/code-scanning/10?query=ref%3Arefs%2Fpull%2F1460%2Fmerge

Expand to see screenshot

The latest code snippet that is causing it (the alert has followed it around through some minor refactors) is:

export const breakStringWithQuotesBySpaces = (string: string) =>
  string.match(/("[^"]*?"|[^"\s]+)+(?=\s*|\s*$)/g); // source: https://stackoverflow.com/a/16261693/1265472

The regex explain is:

Expand to see schreenshot

(mostly for my own future reference, this is the specific review thread where we were discussing it further: sparkletown/sparkle#1460 (comment))

[erik-krogh]

Thanks for the report.

Yes, that is a false positive, your regular expression is not vulnerable to ReDoS.

The ReDoS.ql query tries to figure out if there exists a suffix that will cause a string to be rejected.
And it thinks that such a string exists for your positive lookahead (?=\s*|\s*$).
However, as your lookahead matches the empty string, the lookahead will always match, and thus no rejecting suffix exists.

The first part of your regexp would be vulnerable to ReDoS if there existed a rejecting suffix.
Take as example this modified regexp:

/("[^"]*?"|[^"\s]+)+X/.test("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!")

[yarikoptic]

Thank you @erik-krogh ! Besides fixing for false-positive, might be worth adjusting the summary error message to make it obvious that it is not about ! per se and count be another character, e.g. #. May be adding e.g. would be sufficient, i.e.

This part of the regular expression may cause exponential backtracking on strings
containing many repetitions of e.g. '!'.