I am trying to understand redos in details and it is more or less clear why (a|a)+x fails on aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab string, but I am curious if there is any example which does not use grouping? I read that the Thompson engine is not vulnerable to this problem, because it does not do backtracking, but as far as I understand this means that it cannot have grouping either. Is it possible to do grouping without backtracking and the vulnerability that comes with it?
Is it possible to write a regex engine that uses grouping but does not do backtracking?
86 Views Asked by inf3rno At
1
There are 1 best solutions below
Related Questions in REGEX
- Python and regex, can't understand why some words are left out of the match
- Special access rule in an .htaccess file for IP addresses, authorized only for one directory structure
- regex working not as expected javascript, displays wrong values
- Clarity on how can `.*` match all strings?
- IIS Rewrite Module exclude bots but allow GoogleBot
- Regex skipping delimiter is there is / before it
- How to ignore case in regexp mapping in a .htaccess rewrite rule?
- Select all lines after last occurrence of a certain character
- Segregate class names using regular expresions
- Regex to match binary literal number in re2c format
- why the perl regular expression is not identifying the value
- Trying to run subprocess commands with carriage returns and newlinees
- `Backward slash + b` does not work as expected on regex
- Extract 15 words before and 8 words after each 9digit number from a text file using regular expressions in python
- How to migrate this regex to JavaScript
Related Questions in DENIAL-OF-SERVICE
- Denial of service: regular expression
- Confirm API is called by known application
- Sonar scan reports issue in Regex
- Denial of service protection: how to reject connections based on content and frequency (golang as example)
- Regex vulnerable to polynomial runtime
- How does this Scapy DHCP DoS/Exhaustion attack work?
- Why is a StackOverflowError worth a CVE?
- Convert pixels to cm using Python
- SonarQube: denial of service for regex pattern due to polynomial runtime backtracking
- How is expanding %(describe) during a git archive a denial-of-service (DOS) risk?
- Checkmarx Resource Exhaustion in Golang url.Parse
- Preconditions for SpEL DoS vulnerability CVE-2022-22950?
- Is it possible to dispatch a successful DOS attack on a firewall with all ports closed?
- Can you limit the size of data that can be deserialized in Ktor?
- Matching user-input text with a user-input regex in Node.js
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular # Hahtags
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
Ok, so the answer is Re2 according to Wiktor Stribiżew. It is possible to support grouping without backtracking. Re2 does not support stuff like backreferences, which is completely understandable, at least I doubt many engines prepare for patterns like this one
/(a)(a|\1)+b/.test("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaax"). They write that lookaround is not fully supported either because of this. So these engines have limits, but they are good enough. Many people try to solve everything with a single pattern, which fuels this problem.