Regex backtracking issues

[joeyparrish]

@davisjam reported some potential regex backtracking vulnerabilities to us via email. In such a vulnerability, extremely long inputs could cause a regex to block for a very long time while parsing.

We believe there is no significant risk to these particular issues. Four of six of them are in the jsdoc template, and therefore do not affect Shaka Player itself. The other two are in the TTML text parser.

Application developers generally have some control or trust in their content catalogs and are not subject to malicious TTML content. Such content, if encountered, would only cause individual browser tabs to lock up. Shaka Player does not run in nodejs or other such environments, and we do not expect this could be used for any kind of DOS attack.

The affected regex should be refactored to avoid this. @davisjam recommends these tools to assess progress:

• https://github.com/substack/safe-regex
• https://github.com/NicolaasWeideman/RegexStaticAnalysis

Here are the details of the reported vulnerabilities:

Vuln 1:

• file: "docs/jsdoc-template/static/scripts/prettify/lang-css.js"
• pattern: "^(-?(?:[_a-z]|\\[\da-f]+ ?)(?:[\w-]|\\\\[\da-f]+ ?))\s:"

Vuln 2:

• file: "docs/jsdoc-template/static/scripts/prettify/lang-css.js"
• pattern: "^"(?:[^\\n\\f\\r\"\\\\]|\\(?:\r\n?|\n|\f)|\\[\S\s])*""

Vuln 3:

• file: "docs/jsdoc-template/static/scripts/prettify/lang-css.js"
• pattern: "^'(?:[^\\n\\f\\r'\\\\]|\\(?:\r\n?|\n|\f)|\\[\S\s])*'"

Vuln 4:

• file: "docs/jsdoc-template/static/scripts/prettify/prettify.js"
• pattern: "^<(?:(?:(?:\.\.\/)|\/?)(?:[\w-]+(?:\/[\w-]+)+)?[\w-]+\.h|[a-z]\w)>"

Vuln 5:

• file: "lib/text/ttml_text_parser.js"
• pattern: "^(\d*\.?\d*)t$",

Vuln 6:

• file: "lib/text/ttml_text_parser.js"
• pattern: "^(?:(\d*\.?\d*)h)?(?:(\d*\.?\d*)m)?(?:(\d*\.?\d*)s)?(?:(\d*\.?\d*)ms)?$",

[TheModMaker]

For those unfamiliar with catastrophic backtracking, here is a short explanation.

Consider the following regex: /a*a*b/

So if you have an input string of aaax, it obviously doesn't match. First it tries to match the first a* with the longest string of a's (since it's greedy). The 'x' doesn't match 'a', so it tries the next regex part; the second a* is optional, so it tries the next regex part; the 'x' doesn't match the expected 'b' so it fails to match.

But the * matches any number of something, so what if we chose less of them? So the regex engine backs up and selects one fewer 'a' from the first a* and moves forward. This time, the remaining string is 'ax', so the second a* can match the 'a'. But the 'x' still doesn't match 'b'.

But what if the second a* didn't use all the a's? See the problem? Here is a list of all the matches the regex engine will try on the above string:

a*	a*	b
aaa		x
aa	a	x
aa		ax
a	aa	x
a	a	ax
a		aax
	aaa	x
	aa	ax
	a	aax
		aaax

You see there are 10 attempts to match the given string, which is really just a series of a's. The regex /a*b/ will only make 4 matches as it tries less values for a*. This can become exponentially worse as there are more characters in the input string.

In the TTML parser we use the regex /\d*\.?\d*/ to match numbers. Since the . is optional, it is similar to the above case.

[joeyparrish]

TTML parser fix cherry-picked for v2.3.3. The remaining issues are in the documentation template, not Shaka Player.

[joeyparrish]

The vulnerable expressions in jsdoc are all from the "prettify" module, which enables syntax highlighting for CSS. https://github.com/jsdoc3/jsdoc/tree/master/templates/default/static/scripts/prettify

That code seems to have been forked in 2012 and never updated. The original code has been updated a few times since then: https://github.com/google/code-prettify/commits/master/src/lang-css.js

I will put together a bug report against jsdoc for this, and a pull request to update, if I can.

[davisjam]

Sounds good. Link to the bug report and I can also take a peek at a fix.

[davisjam]

@joeyparrish I have contacted the code-prettify devs by email. I CCd you in case you want to weigh in or point out the prettify fork.

[ismena]

@joeyparrish Is there something else we should with regards to this issue or are we good to close it?

[joeyparrish]

We have fixed the regex issues that affect our library, but there are others in our jsdoc template. We're leaving it open until we fix those, too.

Our template is forked from the jsdoc default template, and the relevant code in jsdoc was forked from prettify (and never updated). If we do fix these issues in the template ourselves before jsdoc and prettify do, we can upstream the fix.