lgtm-com[bot]
commented
1 year ago This pull request introduces 1 alert and fixes 1 when merging eb1dcef3857408335cae903359cdb8b3da1a61c4 into 8e024bc5e63e3d56ab36e1330b1457af369293c1 - view on LGTM.com
new alerts:
- 1 for Unused variable, import, function or class
fixed alerts:
-
1 for Polynomial regular expression used on uncontrolled data
Heads-up: LGTM.com's PR analysis will be disabled on the 5th of December, and LGTM.com will be shut down ⏻ completely on the 16th of December 2022. It looks like GitHub code scanning with CodeQL is already set up for this repo, so no further action is needed :rocket:. For more information, please check out our post on the GitHub blog.
Description
Fix RegEx in code to avoid potential ReDoS attacks. See the CodeQL reference for more information.
Motivation and Context
JavaScript's RegEx engine uses backtracking which means that its worst-case time complexity can be polynomial or even exponential. This can happen when the regex fails to find any matches in the queried string, when the regex is written in such a way that forces the engine to investigate each character in the queried string multiple times.
Polynomial Worst-Case Compexity
The polynomial worst-case complexity happens in cases such as
/\w+\(/. Here, the intention is to find a string of letters terminated with a(. If the queried string does end with a(, all is good. However, if the queried string doesn't end with a(, the engine needs to do a lot of backtracking, which leads to a potential ReDoS vector.The engine needs to do a pattern that looks like this: start with first letter, collect all following letters, reach end of string without finding
(, backtrack, start again with second letter, collect all following letters again, reach end of string without finding(again, backtrack, start again with third letter... If the string is millions of characters long, the engine can freeze and bring down the whole application.There are several ways to prevent this problem:
/\b\w+\(/) before each unbounded repetition, if it makes sense. The generic advice is to add a negative lookbehind before the repetition (e.g./(?<!\w)\w*\(/in our example) which acts as a generic anchor, but this is not available in JavaScript.(a,b,c,d)) in two logically equivalent ways:/\((?:\w+,)*\w+\)//\(\w+(?:,\w+)*\)//(?:scale|translate|rotate|skewx|skewy|matrix)\(/in our example)./[^)]+\(/is better than/.+?\(/is better than/.+\().\btranslate\([^()]+\)where the added(in the square bracket group prevents infinite recursion inside the square bracket group).Note: Repetitions at the very end of a regex (e.g.
/\w+/or/\w+|abc/) are okay because they succeed/fail immediately, without triggering the backtracking which is the problem.Another case with polynomial worst-case complexity is
/^\w+,?\w+\(/in absence of the,and(. In this situation, the second/w+subregex becomes unanchored, forcing the regex engine to traverse all letters for each letter, as above. This problem can be prevented by ensuring that there are no overlaps between the two subregexes - that in every possible situation, each subregex is anchored (e.g./\w+(,\w+)?\(/).Exponential Worst-Case Complexity
Exponential worst-case complexity happens when the polynomial worst-case complexity items happen inside a repetition and without an anchor. Building on from the previous example, if
(\w+,?\w+)*, in absence of the,. The problem is that not only does the regex engine check every possibility for each letter, it also checks every combination of possible arrangements of the two subregexes, which leads to the exponential factor.The surest way to prevent these is to avoid repetitions inside repetitions as much as possible - and, if such a construct is necessary, to make sure that the possibilities (e.g. in an alternation) can never overlap.