Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Stack overflow due to recursion in src/dfa/dead_rules.cc #394

Closed
Me19m4 opened this issue Jan 20, 2022 · 4 comments
Closed

Stack overflow due to recursion in src/dfa/dead_rules.cc #394

Me19m4 opened this issue Jan 20, 2022 · 4 comments

Comments

@Me19m4
Copy link

Me19m4 commented Jan 20, 2022

Operating System Version：ubuntu 20.04

re2c version：2.2

error function：re2c::backprop

==9992==ERROR: AddressSanitizer: stack-overflow on address 0x7ffdf3f83ff8 (pc 0x00000066f8e0 bp 0x000000135534 sp 0x7ffdf3f84000 T0)
#0 0x66f8e0 in re2c::backprop(re2c::rdfa_t const&, bool*, unsigned long, unsigned long) re2c/src/dfa/dead_rules.cc:149:9
#1 0x66f8e4 in re2c::backprop(re2c::rdfa_t const&, bool*, unsigned long, unsigned long) re2c/src/dfa/dead_rules.cc:149:9
#2 0x66f8e4 in re2c::backprop(re2c::rdfa_t const&, bool*, unsigned long, unsigned long) re2c/src/dfa/dead_rules.cc:149:9
#3 0x66f8e4 in re2c::backprop(re2c::rdfa_t const&, bool*, unsigned long, unsigned long) re2c/src/dfa/dead_rules.cc:149:9
Omit.....
#245 0x66f8e4 in re2c::backprop(re2c::rdfa_t const&, bool*, unsigned long, unsigned long)re2c/src/dfa/dead_rules.cc:149:9
#246 0x66f8e4 in re2c::backprop(re2c::rdfa_t const&, bool*, unsigned long, unsigned long)re2c/src/dfa/dead_rules.cc:149:9
#247 0x66f8e4 in re2c::backprop(re2c::rdfa_t const&, bool*, unsigned long, unsigned long) re2c/src/dfa/dead_rules.cc:149:9
#248 0x66f8e4 in re2c::backprop(re2c::rdfa_t const&, bool*, unsigned long, unsigned long)re2c/src/dfa/dead_rules.cc:149:9
AddressSanitizer: stack-overflow re2c/src/dfa/dead_rules.cc:149:9 in re2c::backprop(re2c::rdfa_t const&, bool*, unsigned long, unsigned long)

Test example link：

https://drive.google.com/file/d/1bLXgifNQhcTQI6937lJhapAa3hgwEugT/view?usp=sharing

Run the following command to repeat the error：

$ ./re2c example
@skvadrik
Copy link
Owner

Thanks for the bug report. Did you find these examples with some kind of fuzzer?

There are two different places where re2c should enforce reasonable size limits:

  • NFA size and depth
  • DFA size and depth

For regular expressions it is not necessary, because counted repetition is only unrolled when NFA is constructed (so RE can't get much larger than their text representation in the source file). For NFA and DFA the limits should be enforced separately, because there may be very large NFA that result in very small DFA (e.g. for something like (((""){0,100}){0,100}){0,100} NFA will have about 100^3 states, but DFA will have just one state). And the other way around (a small NFA triggering pathological exponential DFA size).

In the second test case re2c should check that the lower repetition bound is less or equal to the upper bound.

@skvadrik skvadrik changed the title Stack overflow due to recursion in re2c/ SRC/dFA /dead_rules.cc Stack overflow due to recursion in src/dfa/dead_rules.cc Jan 21, 2022
skvadrik added a commit that referenced this issue Jan 21, 2022
@skvadrik
Limit maximum allowed NFA and DFA size.
a3473fd 
Instead of failing with an out of memory exception or crashing with a
stack overflow, emit an error message and exit. This is a partial fix
for bug #394 "Stack overflow due to recursion in src/dfa/dead_rules.cc",
where re2c hit stack overflow on a counted repetition regexp with high
upper bound.

The patch adds the following limits:
  1. the number of NFA states
  2. NFA depth (maximum length of a non-looping path from start to end)
  3. the number of DFA states
  3. total DFA size (sum total of all NFA substates in all DFA states)

There are tests for the first three limits, but not for the DFA size as
all examples that trigger this behavior take a long time to finish (a
few seconds), which increases test run time almost twice.
skvadrik added a commit that referenced this issue Jan 21, 2022
@skvadrik
Emit an error when repetition lower bound exceeds upper bound.
039c189 
Historically this was allowed and re2c swapped the bounds. However, it
most likely indicates an error in user code and there is only a single
occurrence in the tests (and the test in an artificial one), so although
the change is backwards incompatible there is low chance of breaking
real-world code.

This fixes second test case in the bug #394 "Stack overflow due to
recursion in src/dfa/dead_rules.cc" (the actual fix is to limit DFA size
but the test also has counted repetition with swapped bounds).
@skvadrik
Copy link
Owner

Fixed in commits a3473fd and 039c189.

@samueloph
Copy link

CVE-2022-23901 was assigned to this.

NVD also rated it as a Critical CVE:
https://nvd.nist.gov/vuln/detail/CVE-2022-23901

I didn't have any involvement in this assignment, I'm just posting here for reference.

@skvadrik
Copy link
Owner

skvadrik commented Aug 1, 2023

This bug has been fixed (see above for details). The fix was released in re2c-3.1.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@skvadrik @samueloph @Me19m4