Avoid backtracing in ceylon interpolation regex #1773

thewoolleyman · 2021-12-10T21:17:53Z

Fix backtracing in ceylon interpolation regex.

Addresses the third remaining Regex Denial Of Service vulnerability reported in https://hackerone.com/reports/1283484. The other two mentioned in that report have already been addressed as part of #1690.

thewoolleyman · 2021-12-10T21:18:17Z

FYI @dblessing

thewoolleyman · 2021-12-10T21:24:17Z

More Details

(The following examples can be reproduced on a gitlab.com wiki page)

A high CPU load can be caused using the following ceylon regex:

```ceylon  
"````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````

This ReDos example in the description of this issue renders in less than a second with the fix in this PR - it was 40+ seconds before.

This fix was based on the suggestions in the "Quantifiers in Sequence" section of this page: https://www.regular-expressions.info/redos.html

I also tested the following valid ceylon markdown, and it still seems to work the same with the fix:

```ceylon
print("Hello, ``person.firstName`` ``person.lastName``, the time is ``Time()``.");
print("1 + 1 = ``1 + 1``");
```

tancnle · 2021-12-13T03:35:41Z

Thank you for your contribution @thewoolleyman ❤️ We would love to see this backtracking issue addressed in rouge ASAP. I have added some suggestions for your consideration. Please let me know what you think 🙏🏼 .

tancnle · 2021-12-13T03:39:23Z

thoughts: With the change in this PR, the interpolated string still seems less ideal. They are all clumped together as Literal::String rather than with interpolation Literal::String::Interpolation. This is, however, another issue that can be dealt with in a separate PR.

tancnle · 2021-12-13T03:29:27Z

lib/rouge/lexers/ceylon.rb

@@ -51,7 +51,7 @@ class Ceylon < RegexLexer

        rule %r("(\\\\|\\"|[^"])*"), Literal::String
        rule %r('\\.'|'[^\\]'|'\\\{#[0-9a-fA-F]{4}\}'), Literal::String::Char
-        rule %r(".*``.*``.*"', String::Interpol
+        rule %r("[^`]*``[^`]*``[^`]*"', String::Interpol


There seems to be a flaw with the initial rule which is caused by this line and the next being mangled into one regex (notice the extraneous single quote ' and missing closing bracket). For better or worse, that bug might not expose the backtracking issue as it is reported 🤔

Given that we addressed the wrapping issue above:

Using the reported string, I have verified on https://regex101.com/debugger

".*``.*``.*" -> Match 1 failed in 106 086 step(s)

"[^`]*``[^`]*``[^`]*"-> Match 1 failed in 95 step(s)

Could we add the string interpolation example in the spec/visual/samples/ceylon for future reference?

diff --git spec/visual/samples/ceylon spec/visual/samples/ceylon index b6d7a122..20cf4608 100644 --- spec/visual/samples/ceylon +++ spec/visual/samples/ceylon @@ -32,3 +32,6 @@ module com.acme.test "1.0.0" { } package com.example; + +print("Hello, ``person.firstName`` ``person.lastName``, the time is ``Time()``."); +print("1 + 1 = ``1 + 1``");

Done, I've added this change in the latest push.

tancnle · 2021-12-13T03:33:17Z

lib/rouge/lexers/ceylon.rb

+        rule %r("[^`]*``[^`]*``[^`]*"', String::Interpol
        rule %r(\.)([a-z_]\w*)) do


suggestion: What do you think about addressing both the wrapping and backtracking issue?

Suggested change

rule %r("[^`]*``[^`]*``[^`]*"', String::Interpol

rule %r(\.)([a-z_]\w*)) do

rule %r("[^`]*``[^`]*``[^`]*"), Literal::String::Interpol

rule %r((\.)([a-z_]\w*)) do

Usually for interpolation it's best to try and push a separate state, so you can highlight the contents of the interpolation as well. It can check for the closing interpolation tokens and then mixin the main expression state.

Thanks @jneen. Great point. In fact, I have a follow-up commit locally to move this string interpolation to state (similar to how the ruby lexer deal with this). Once this merges, I can create another PR to address interpolation more appropriately. WDYT?

@tancnle I've fixed the wrapping as suggested in the latest push.

thewoolleyman · 2021-12-14T01:24:17Z

Thank you for your contribution @thewoolleyman ❤️ We would love to see this backtracking issue addressed in rouge ASAP. I have added some suggestions for your consideration. Please let me know what you think 🙏🏼 .

@tancnle thanks for the prompt response!

I've made the two suggested changes to my commit, and pushed a rebased branch.

Let me know if there's anything else needed on my end.

tancnle · 2021-12-14T06:19:48Z

Thanks @thewoolleyman. The PR looks good to me 🚀

thewoolleyman force-pushed the caw-fix-ceylon-redos branch from 8705cbb to 14d7962 Compare December 10, 2021 21:19

tancnle self-assigned this Dec 13, 2021

tancnle added the author-action The PR has been reviewed but action by the author is needed label Dec 13, 2021

tancnle reviewed Dec 13, 2021

View reviewed changes

thewoolleyman force-pushed the caw-fix-ceylon-redos branch from 14d7962 to 8a54d0b Compare December 14, 2021 01:20

Avoid backtracing in ceylon interpolation regex

2a12a5d

thewoolleyman force-pushed the caw-fix-ceylon-redos branch from 8a54d0b to 2a12a5d Compare December 14, 2021 01:20

tancnle merged commit db5c4ad into rouge-ruby:master Dec 14, 2021

tancnle removed their assignment Dec 14, 2021

tancnle removed the author-action The PR has been reviewed but action by the author is needed label Dec 14, 2021

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Avoid backtracing in ceylon interpolation regex #1773

Avoid backtracing in ceylon interpolation regex #1773

thewoolleyman commented Dec 10, 2021

thewoolleyman commented Dec 10, 2021

thewoolleyman commented Dec 10, 2021

tancnle commented Dec 13, 2021

tancnle commented Dec 13, 2021

tancnle Dec 13, 2021 •

edited

Loading

thewoolleyman Dec 14, 2021

tancnle Dec 13, 2021

jneen Dec 13, 2021

tancnle Dec 13, 2021 •

edited

Loading

thewoolleyman Dec 14, 2021

thewoolleyman commented Dec 14, 2021

tancnle commented Dec 14, 2021

		rule %r("[^`]``[^`]``[^`]*"', String::Interpol
		rule %r(\.)([a-z_]\w*)) do

Avoid backtracing in ceylon interpolation regex #1773

Avoid backtracing in ceylon interpolation regex #1773

Conversation

thewoolleyman commented Dec 10, 2021

thewoolleyman commented Dec 10, 2021

thewoolleyman commented Dec 10, 2021

More Details

tancnle commented Dec 13, 2021

tancnle commented Dec 13, 2021

tancnle Dec 13, 2021 • edited Loading

Choose a reason for hiding this comment

thewoolleyman Dec 14, 2021

Choose a reason for hiding this comment

tancnle Dec 13, 2021

Choose a reason for hiding this comment

jneen Dec 13, 2021

Choose a reason for hiding this comment

tancnle Dec 13, 2021 • edited Loading

Choose a reason for hiding this comment

thewoolleyman Dec 14, 2021

Choose a reason for hiding this comment

thewoolleyman commented Dec 14, 2021

tancnle commented Dec 14, 2021

tancnle Dec 13, 2021 •

edited

Loading

tancnle Dec 13, 2021 •

edited

Loading