How to Solve Regex Issues

TW_Tones · January 5, 2022, 12:15am

@Mohammad I only now got a look at this and its very nice.

On the use of regex it is a big investment in time to learn, but there seems to me possibly no more than 50 basic regex that would provide substantial value to tiddlywiki users with or without regex experience so I wonder if as a result of this plugin and others with regex options we could build a library of regex patterns like we collect filters in Advanced Search > Filters > dropdown. Add a one sentence explanations to each and users will be on the way to learning regex from a tiddlywiki perspective if not a global regex understanding.

Mohammad · January 5, 2022, 1:57am

Yes, that’s a problem
If the pattern can be validated before displaying results it would be great

Mohammad · January 5, 2022, 1:58am

@TW_Tones
Thank you, having a day off predefined patterns is absolutely a must

CodaCoder · January 5, 2022, 3:43am

To put it mildly.

Please, take it seriously and put a guard in place (see my previous) before your good intentions cause someone to lose work:

github.com/Jermolene/TiddlyWiki5

GHSL-2020-362: ReDoS in TiddlyWiki

opened 05:38PM - 22 Dec 20 UTC

closed 10:22AM - 01 Feb 21 UTC

Jermolene

I (@Jermolene) have just received the following notification from the GitHub Sec…urity Lab team and am posting it here for discussion. --- # GitHub Security Lab (GHSL) Vulnerability Report: `GHSL-2020-362` The [GitHub Security Lab](https://securitylab.github.com) team has identified potential security vulnerabilities in [TiddlyWiki](https://github.com/Jermolene/TiddlyWiki5). We are committed to working with you to help resolve these issues. In this report you will find everything you need to effectively coordinate a resolution of these issues with the GHSL team. If at any point you have concerns or questions about this process, please do not hesitate to reach out to us at `securitylab@github.com` (please include `GHSL-2020-362` as a reference). If you are _NOT_ the correct point of contact for this report, please let us know! ## Summary The project contains one or more regular expressions that are vulnerable to [ReDoS](https://en.wikipedia.org/wiki/ReDoS) (Regular Expression Denial of Service) ## Product TiddlyWiki ## Tested Version Latest commit at the time of reporting (December 21, 2020). ## Details ### ReDoS ReDoS, or Regular Expression Denial of Service, is a vulnerability affecting poorly constructed and potentially inefficient regular expressions which can make them perform extremely badly given a creatively constructed input string. For the specific regular expression reported, it is possible to force it to work with an `O(2^n)` runtime performance when there is [exponential backtracking](http://en.wikipedia.org/wiki/ReDoS#Exponential_backtracking). ReDoS can be caused by ambiguity or overlapping between some regex clauses. These badly performing regular expressions can become a security issue if a user can control the input. For example if the project is an input validation library, then the project could be used by a server to validate untrusted user input. There is no one size fits all when it comes to fixing ReDoS. But in general it is about removing ambiguity/overlap inside the regular expression. Before showing the vulnerable regex, it may be helpful to show some examples of regular expressions vulnerable to ReDoS and how to fix them. If you are familiar with this vulnerability and how to fix it, please skip this section. --- ```JavaScript var reg = //g; ``` The above regular expression matches the start of an HTML comment, followed by any characters, followed by the end of a HTML comment. The dot in the regular expression (`.`) matches any char except newlines, and `\s` matches any whitespace. Both `.` and `\s` matches whitespace such as the space character. There are therefore many possible ways for this regular expression to match a sequence of spaces. This becomes a problem if the input is a string that starts with `<!--` followed by a long sequence of spaces, because the regular expression evaluator will try every possible way of matching the spaces (see this debugging session for an example: https://regex101.com/r/XvYgkN/1/debugger). The fix is to remove the ambiguity, which can be done by changing the regular expression to the below, where there is no overlap between the different elements of the regular expression. ```JavaScript var reg = //g; ``` --- ```JavaScript var reg = /(\w+_?)+_(\d+)/; ``` The above matches a snake_case identifier that ends with some digits. However, for a string starting with lots of letters, there many ways for the regular expression to match those letters, due to the regex having a repetition matching letters (`w+`) inside another repetition that can match letters (`(\w+_?)+`). The regular expression evaluator will try every possible grouping of letters into smaller groups of letters (see this debugging session for an example: https://regex101.com/r/fmci1j/1/debugger). The fix is again to remove ambiguity, by changing the inner repetition to match groups of letters that must end with an underscore. ```JavaScript var reg = /(\w+_)+(\d+)/; ``` --- Often the regular expressions are not as simple as the examples above. Like the below regular expression [that used to be part of VS Code](https://github.com/microsoft/vscode/pull/109964/files). (the top regular expression is the vulnerable, the bottom is the fixed) ```JavaScript var linkPattern = /(\[((!\[[^\]]*?\]$\s*)([^\s\($]+?)\s*\)\]|(?:\\\]|[^\]])*\])$\s*)(([^\s\($]|$\S*?$)+)\s*(".*?")?\)/g; var linkPattern = /(\[((!\[[^\]]*?\]$\s*)([^\s\($]+?)\s*\)\]|(?:\\\]|[^\]])*\])$\s*)(([^\s\($]|$[^\s\($]*?\))+)\s*(".*?")?\)/g; ``` But this example is actually very similar to the first example. A section of the regular expression that was too general (`\S`) was changed to something a bit more specific (`[^\s]`) to remove overlap with another part of the regular expression. --- ### Vulnerability TiddlyWiki is A wiki implementation with a filter functionality that is potentially vulnerable to ReDoS. This issue was detected using the [following CodeQL query](https://lgtm.com/query/8014663655552936036/). PoC: - `git@github.com:Jermolene/TiddlyWiki5.git` - Run the below with `node`. ```JavaScript var filters = require("./TiddlyWiki5/core/modules/filters"); filters.parseFilter("[/..........................................................................]") ``` ### Impact This issue may lead to a denial of service. ## GitHub Security Advisories We recommend you create a private [GitHub Security Advisory](https://help.github.com/en/github/managing-security-vulnerabilities/creating-a-security-advisory) for these findings. This also allows you to invite the GHSL team to collaborate and further discuss these findings in private before they are [published](https://help.github.com/en/github/managing-security-vulnerabilities/publishing-a-security-advisory). ## Credit This issue was discovered and reported by GitHub team member [@erik-krogh (Erik Krogh Kristensen)](https://github.com/erik-krogh). ## Contact You can contact the GHSL team at `securitylab@github.com`, please include a reference to `GHSL-2020-362` in any communication regarding this issue. ## Disclosure Policy This report is subject to our [coordinated disclosure policy](https://securitylab.github.com/disclosures#policy).

Mohammad · January 5, 2022, 4:03am

@jeremyruston - do you think using regex in advanced search can make Tiddlywiki to crash?

@CodaCoder - I believe the above GitHub isue has resolved and it is not related to advanced search, it is related to the way Tiddlywiki uses regexp! Advanced search just produces titles and they can be limited to 250 or less, so it is far from crashing Tiddlywiki by such searches!

Please note advanced search in fields is a plain wikitext plugin and does not add any JS or bring any new regex tools into Tiddlywiki!

TiddlyTweeter · January 5, 2022, 6:32am

Ciao Mohammad

I looked at it. You know I’m a great fan of regular expressions and where I actually, unlike everything else, have some competence. So it is the regex aspect that I’m most interested in. I think, overall, it is as great idea! But for really useful, safe, implementation, I have a couple of initial comments that I hope will be relevant.

Regarding saving the filters. The existing default system is really only useful if you have a limited number of saved filters. IF you thought that, eventually, there might be, say 50, regex heavy filters then, to be usable, one would need to change the filter dropdown so it had a cascading menu system–i.e. with sub-sections for different groups of filters.

UPDATE: I need to rephrase this as the way the tool works at the moment there is no dropdown. Later.

Regarding the issue of guarding against “catastrophic backtracking”, as well as for half-completed regex, I very much agree with @CodaCoder. Meaning, for regex heavy filters, it is best if there is a Go! button. The end-user would enter the full regex before applying it. The dynamic nature of TW–with an incomplete regex running–would potentially cause more issues than anything else. I do realise this makes the implementation much more complex but I think without it users, especially those not so familiar with regex, could get in a pickle!

TiddlyTweeter · January 5, 2022, 6:50am

Right. But it is still possible to lock the wiki up with a malformed regex. I think the point is to guard against live application before the regex is fully complete?? i.e. a Go! button. Though I’d have to test that to be sure.

Just FYI, as far as I can see, TW is interacting with the JS regex engine and serious error protection is JS based. And I don’t know quite what browsers are doing on that (by the way the JS regex engines do differ slightly between browsers). Personally, to test difficult regex, I use the commercial software RegexBuddy which analyses one’s regex to isolate issues on scope and lookbehind and lookforward.

But, in practice, I think for most use cases in TW it isn’t likely to be much of an issue.

TiddlyTweeter · January 5, 2022, 7:58am

Ciao @Mohammad

This is just a side comment.

I asked an Italian programmer friend to look at TW and give me his first impression of it.

He commented: “It is a very sophisticated self-modifying regex machine with bells and whistles.”

It isn’t quite that, but I thought his comment had quite a lot of truth in it.

Mohammad · January 28, 2022, 4:29pm

10 posts were split to a new topic: Advanced Search in Fields v0.2.0

CodaCoder · January 6, 2022, 6:19pm

I take the blame for this - I’m somehow failing to get the point across.

Forget all your “static HTML” bits and pieces, they are not the issue. Or, at least, they are not the lion’s share of the problem. Browsers can spit out spans and divs and even tables without even breaking a sweat.

Not so events!

Attaching events to elements takes – relatively speaking – quite a long time. When you have many hundreds, or even thousands to wire up, then you will start to see performance issues.

Now… on to TiddlyWiki.

TW is a dynamic presentation environment. ANY change you make, practically any move you make, will cause the TW internals to reconsider and perhaps even do a rebuild of the dom. Your job, as a seasoned TW dev is to aid TW in that task.

If your code requires 10,000 (ten thousand) divs, pfft – easy.

If your code requires 10,000 divs containing event handlers, oh dear… hmmm… uh, perhaps I’ll go get a coffee…

I don’t understand what the resistance is, but for any seasoned TW dev, this should be your mantra going forward:

Never write another $list of links/buttons and not consider using $eventcatcher

Actuallly, I do understand the resistance -- you've invested in code that mostly works. Changing it is painful. Suck it up... "it's only code"

CodaCoder · January 6, 2022, 6:26pm

It’s not clear what you’re referring to, but I hope you’re not comparing a list of event-handler laden links with a single event handler attached to a parent div ($eventcatcher). If so, your definition of “very fast” is very different to mine.

I’m going to stop now.

Mohammad · January 6, 2022, 6:29pm

There is no resistance at all! I really welcome any improvement! The only resistance I have showed by now if to go with pure wikitext instead of JavaScript! The reason is/was to let more people understand your code! and develop/extend the TW ecosystem!

So, please when you read the Search plugin codes, kindly let me know where we can improve the performance! Note that Shiraz is a separate plugin and it can be improved too!

I have developed simpler dynamic tables in other plugins, I can think to use them instead of Shiraz, if there is room for improvement!

In dynamic table there are many buttons/links and I have read the post by @saqimtiaz on improving the performance by using $eventchatcher!

Thank you for time and comments on Search plugin!

CodaCoder · January 6, 2022, 6:39pm

I’m sorry, but I really don’t have that kind of time right now.

I appreciate that and that’s an admirable stance. I wish I too wrote TW code with an eye on re-use. But that’s my failing. Sorry. the best I can do is “share with myself” through the bundler plugin. Again, I’m time limited so for now, at least, it has to be that way.

Did I read somewhere you have an engineering background? If so, take my input as sharing known facts with you, some of them measured (by others, not me). None of what I gave you above is opinion, just what is known.

Anyway, I MUST get back to “real” work

Mohammad · January 6, 2022, 7:22pm

Thank you anyway!

Good luck!

I leave this here and hope others interested in the search tools find useful points!

Mark_S · January 22, 2022, 3:40pm

That, BTW, is pretty much a definition of the human brain.

tw-FRed · January 22, 2022, 5:05pm

To help prevent that, when regex is selected, I disable live searching and add a Go! button.

I do believe TW users should not be able to crash their wiki/browser when using regexp, I experienced it last week and nearly lost a few hours of work. But in my case, the Go button wouldn’t have helped, for I thought my regexp was legit, and I would have hit the button!

Maybe the solution should be coded in the core, with some kind of “watchdog” monitoring the filters interpreter and “killing” it when a filter processing takes too long ? Just an idea, I don’t even know if this makes sense

Fred

CodaCoder · January 22, 2022, 5:13pm

That’s very true, of course. But you would get chance to take one last look. And also, your regex wouldn’t be executed before it is finished being written, which was my overriding concern.

Mark_S · January 22, 2022, 10:00pm

Rather than a “go” button, which may still not prevent problems, why not have a limit applied? Say 150 tiddlers. Then if a user is sure they want to see all the results, they can select to “See all tiddlers – this may slow your machine down.” . This way users can use the interface normally 90% of the time, be protected from mistakes, verify that a filter works, and still have complete usability when they need it.

CodaCoder · January 22, 2022, 10:23pm

It could be 50,000 operations in just the first tiddler (again, this is your splitter in use, asking it to do something really stupid where it matches “everything”). Then add in just 1,000 tiddlers and you’re going to be there a while… like a week

It’s not ideal, I agree, but something like the Go! button helps slow me down a notch.

And of course, the point in this thread is about stopping regexes running before they’re finished being written.

Anyway… the ship’s already sailing, I think.

TiddlyTweeter · January 26, 2022, 9:09pm

Ciao @Mark_S

Ha! Nice one! Thinking about it, despite @CodaCoder’s caveats, I think that might be a good practical solution in many, if not most, use cases?

I guess, finally, it is an empirical issue. Sad to say I haven’t yet created a regex that locks up mother.

Best, TT