ReDoS Vulnerable Regular Expressions - unlikely to be triggered

[kevinramharak]

As mentioned in #139 (comment), there are some remaining regular expressions are (technically) vulnerable to a ReDoS attack:

regex	attack string	location
/(\([a-zA-Z0-9]*:[^)]*\))/	'(:'.repeat(38730)	packages/formatters/src/addMissingParentheses.ts#54
/(?:\s)'"(.*?)(?<!\\)"'(?:\s|:|.|$)/g	'\\' + '\t\'"\t'.repeat(27387) + '\n'	packages/formatters/src/errorMessagePrettifier.ts#54
/['“](declare module )['”](.*)['“];['”]/g	';\'declare module ”'.repeat(12910) + ';”\n\'declare module \'“;\''	packages/formatters/src/errorMessagePrettifier.ts#58
/(is missing the following properties from type\s?)'(.*)': ((?:#?\w+, )*(?:(?!and)\w+)?)/g	'is missing the following properties from type\'s'.repeat(6382) + '\n'	packages/formatters/src/errorMessagePrettifier.ts#64
/(types) ['“](.*?)['”] and ['“](.*?)['”][.]?/gi	'TYPES “'.repeat(20702) + '\'\nTYPES “” AND \'\''	packages/formatters/src/errorMessagePrettifier.ts#76
/type annotation must be ['“](.*?)['”] or ['“](.*?)['”][.]?/gi	'TYPE ANNOTATION MUST BE “'.repeat(10955) + '\''	packages/formatters/src/errorMessagePrettifier.ts#86
/(Overload \d of \d), ['“](.*?)['”], /gi	'OVERLOAD 0 OF 0, “'.repeat(12910) + '\nOVERLOAD 0 OF 0, \'\', '	packages/formatters/src/errorMessagePrettifier.ts#103
/(module|file|file name|imported via) ['"“](.*?)['"“](?=[\s(.|,]|$)/gi	' ' + 'FILE "P'.repeat(20702) + '\n'	packages/formatters/src/errorMessagePrettifier.ts#117
/(type|type alias|interface|module|file|file name|class|method's|subtype of constraint) ['“](.*?)['“](?=[\s(.|,)]|$)/gi	'E' + 'MTYPE \'R'.repeat(19365) + '\n'	packages/formatters/src/errorMessagePrettifier.ts#123
/['“]([^>]*)['”] (type|interface|return type|file|module|is (not )?assignable)/gi	' FILE“'.repeat(22361) + ' FILE'	packages/formatters/src/errorMessagePrettifier.ts#128
/['“](import|export|require|in|continue|break|let|false|true|const|new|throw|await|for await|[0-9]+)( ?.*?)['”]/g	'\'0' + '0'.repeat(54773) + '\n“0”'	packages/formatters/src/errorMessagePrettifier.ts#139
/(return|operator) ['“](.*?)['”]/gi	'RETURN “'.repeat(19365) + '\nRETURN \'”'	packages/formatters/src/errorMessagePrettifier.ts#143
/(?<!\w)'((?:(?!["]).)*?)'(?!\w)/g	'\'' + '\'0\'0\x00'.repeat(24503) + '\n'	packages/formatters/src/errorMessagePrettifier.ts#148

The vulnerability can be checked with the recheck playground.

As shown with the attack strings, these are extremely unlikely to ever occur in any code, but they are possible attack vectors nonetheless, thus they are describer here and it would be good to have them fixed.

The cause of these vulnerabilities is the use of (.*) like patterns, which is fine when the input is as expected, but will cause DOS behaviour if matched against a malicious input. This is usually fixable as mentioned in #186:

Replace lazy .*? with [^']* to eliminate quadratic backtracking on strings with many single quotes. The negated class directly matches between the first pair of quotes with no ambiguity.

By using negated class ranges, the regex will behave the same for the expected input, but immediately fail when the input does not match what is expected, without any backtracking.

[SoutikNandy]

It would be interesting to see the solution for it.

[Vinayak9769]

Hi! After reviewing the current codebase, it looks like all three vulnerabilities mentioned here have been addressed.

Can this issue be closed?

[kevinramharak]

@Vinayak9769 Thanks for looking at it, but after checking it again using recheck and my own unfinished extension (https://marketplace.visualstudio.com/items?itemName=regex-radar.regex-radar) which is powered by recheck, I found they are still in the code base, but some of them have may have changed slightly. I also found there are quite a few more of them in other files. Do NOTE that these are extremely unlikely to be triggered, since the attack strings are nonsensical.
I will update the issue with the correct regex's, attack strings and source locations.