dead-claudia
commented
7 years ago TL;DR: Regular expression matching is slow, hard, and horribly complex behind the scenes. Oh, and you found a potential malicious regular expression resulting from this complexity.
You have discovered a potential malicious regular expression. That file would be a partial match of all of these, with multiple matches for each (note that (ALPHA|BRAVO) was made optional):
(?x: (?# Word AB Word )
( (?: \\s* [A-Za-z_∆⍙]+[\\w∆⍙¯]* )+ )
\\s* (ALPHA|BRAVO)? \\s*
( (?: \\s* [A-Za-z_∆⍙]+[\\w∆⍙¯]* )+ )
)
(?x: (?# Word AB Ints )
( (?: \\s* [A-Za-z_∆⍙]+[\\w∆⍙¯]* )+ )
\\s* (ALPHA|BRAVO)? \\s*
( (?: \\s* \\d+ )+ )
)
(?x: (?# Ints AB Word )
( (?: \\s* \\d+ )+ )
\\s* (ALPHA|BRAVO)? \\s*
( (?: \\s* [A-Za-z_∆⍙]+[\\w∆⍙¯]* )+ )
)
(?x: (?# Ints AB Ints )
( (?: \\s* \\d+ )+ )
\\s* (ALPHA|BRAVO)? \\s*
( (?: \\s* \\d+ )+ )
)With each of these, there's a lot of loops involved that are hard to optimize away. Here's a quick diagram of just the last one as a DFA, the simplest by far, and excluding captures:
NFA flow chart for (\\s*\\d+)+\\s*(ALPHA|BRAVO)?\\s*(\\s*\\d+)+
Note that the character pointer advances on every `yes` unless it's on the last one.
start
|
|----------------------------- advance start pointer,
| move pointer to start
\|/ /|\
whitespace? ------------- yes --------------|
| |
no no
| |
\|/ |
digit? -------------- no --------------> end? --> yes -> no match
| /|\
yes |
| |
|-------------------\ |
\|/ | | |
digit? --- yes | |
| | |
no | |
| | |
|------------\ | |
\|/ | | |
whitespace? --- yes | /|\
| | |
no | |
| | |
\|/ | |
digit? ----- yes -----/ |
| |
\|/ |
A -- no --> B -- yes ---\ |
| | | |
yes \|/ yes |
| | | /|\
\|/ | \|/ |
L --------- no -------- R |
| | | |
yes \|/ yes |
| | | |
\|/ | \|/ |
P --------- no -------- A |
| | | |
yes \|/ yes |
| | | |
\|/ | \|/ /|\
H --------- no -------- V |
| | | |
yes \|/ yes |
| | | |
\|/ | \|/ |
A --------- no -------- O |
| | | |
yes \|/ yes |
| | | |
|-----------------------/ |
| /|\
|------------\ |
\|/ | |
whitespace? --- yes |
| |
no |
| |
\|/ |
digit? --------------- no ----------------/
|
yes
|
|-------------------\
\|/ | |
digit? --- yes |
| |
no |
| |
|------------\ |
\|/ | |
whitespace? --- yes |
| |
no |
| |
\|/ |
digit? ----- yes -----/
|
no
|
\|/
string matched(Captures only make this more complicated, so that's why I omitted them.)
And for your particular source, just trace it with that flow chart. See how long it takes each time. Also, try tracing it by testing your word regex word? == [A-Za-z_∆⍙]+[\\w∆⍙¯]* instead of digit? == \\d+, or even better, create a graph for just word? (it'll only get more complex).
I'll also note that this is far more optimized than what you'd get out of most engines: they usually just perform basic optimizations and use either on the fly code generation or just generate a tree as an NFA (theoretically equivalent to an DFA), since it takes linear time to create the NFA and polynomial time to match worst case, compared to the exponential time and memory best and worst case to go from the NFA to the DFA, just for linear time matching. (My above example is an NFA.)
Or, long story short, regular expression matching is slow, hard, and horribly complex behind the scenes.
Alhadis
Ingramz
This is somewhat difficult to explain, so please bear with me...
Last night while working on a grammar, I added a pattern-block that made Atom hang at 100% CPU usage. After force-quitting the app twice, I scrutinised the last expression for anything that might've triggered infinite recursion. I was drawing blanks until I narrowed it down from this...
... to this:
All of a sudden, Atom wasn't hanging whenever I switched to the tab that had the grammar's language in it. The patterns themselves didn't match anything. What the patterns were was irrelevant. What's important is that, somehow, this particular capturing group causes Atom to freeze.
I know how good First-Mate is at avoiding infinite loops, which is why this bug is concerning. I've isolated it to a separate branch in my repo for closer examination.
Reproduction
tests/life.apl. It should be fine.makein the package's base directory to toggle the problematic capturing group.tests/life.apland restart Atomtests/life.aplI noticed Lightshow also has troubles with this particular ruleset, although its handling is somewhat less predictable than Atom's.