Analyzing Matching Time Behavior of Backtracking Regular Expression Matchers by Using Ambiguity of NFA

DOI10.1007/978-3-319-40946-7_27zbMath1475.68169OpenAlexW2506796853MaRDI QIDQ2830233

Nicolaas Weideman, Martin Berglund, Brink van der Merwe, Bruce W. Watson

Publication date: 9 November 2016

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-40946-7_27

zbMATH Keywords

ambiguityregular expressionbacktracking matcher

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (8)

How to settle the ReDoS problem: back to the classical automata theory ⋮ On the semantics of atomic subgroups in practical regular expressions ⋮ Re-examining regular expressions with backreferences ⋮ Formalising and implementing Boost POSIX regular expression matching ⋮ Static Detection of DoS Vulnerabilities in Programs that Use Regular Expressions ⋮ Trading Plaintext-Awareness for Simulatability to Achieve Chosen Ciphertext Security ⋮ Memoized regular expressions ⋮ On the semantics of regular expression parsing in the wild

Uses Software

• Snort

Cites Work

• On the Semantics of Regular Expression Parsing in the Wild
• General Algorithms for Testing the Ambiguity of Finite Automata
• Two-way pushdown automata

This page was built for publication: Analyzing Matching Time Behavior of Backtracking Regular Expression Matchers by Using Ambiguity of NFA