search

rouge-ruby / rouge

A pure Ruby code highlighter that is compatible with Pygments
https://rouge.jneen.net/
Other
3.32k stars 733 forks source link

Avoid backtracing in ceylon interpolation regex #1773

Closed thewoolleyman closed 2 years ago

thewoolleyman commented 2 years ago

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 https://github.com/rouge-ruby/rouge/pull/1690.

thewoolleyman commented 2 years ago

FYI @dblessing

thewoolleyman commented 2 years ago

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 commented 2 years ago

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 commented 2 years ago

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.

Screen Shot 2021-12-13 at 2 31 37 pm
thewoolleyman commented 2 years ago

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 commented 2 years ago

Thanks @thewoolleyman. The PR looks good to me 🚀