Skip to content

Software Quality

Deep static analysis

Deep static analysis decides a property of the program by building a model of it first. The model is usually how values move between procedures; for a regular expression it is the automaton a backtracking engine would run. Either way the finding is high-confidence rather than a proof.

Security is the usual target and not the only one: the same dataflow model finds unsafe API patterns and ordinary correctness defects. Taint analysis is one property expressed over this model — untrusted input reaching a dangerous sink — and it has two ways of being checked, statically over the model or dynamically at runtime.

What it catches

  • Cross-module dataflow bugs. A tainted source reaching a distant sink, or an unsafe API pattern spanning files: findings a per-file linter structurally cannot reach.
  • Catastrophic-backtracking regexes (ReDoS). A pattern an attacker can drive into exponential time, turning a request into a denial of service.

Approaches and tools

Dataflow and query analysis

Query engines treat the codebase as a database and dataflow analyzers follow values across calls.

  • CodeQL (free for OSS) — query-based deep security and quality analysis; supports C/C++, C#, Go, Java/Kotlin, JavaScript/TypeScript, Python, Ruby, and Swift.
  • Semgrep — pattern-based rules across 30+ languages; quick to write a rule per bug class your team keeps hitting.

Regular-expression denial of service (ReDoS)

A backtracking pattern like (a+)+$ runs in exponential time on a crafted input. A backtracking engine builds a non-deterministic finite automaton from the pattern and simulates it (Davis et al. 2018)1, and the blow-up comes from ambiguous states — two paths reaching the same state, so the engine explores what follows twice. Analyzing that automaton finds the ambiguity; the older safe-regex star-height heuristic only approximates it. Other algorithmic-complexity blow-ups are not statically detectable and belong to algorithmic complexity testing.

  • recheck — hybrid automaton-plus-fuzzing analysis that returns the actual attack string, for JavaScript and TypeScript, wired into CI via eslint-plugin-redos. regexploit scans Python and other regexes.
  • CodeQL ships js/redos and js/polynomial-redos queries (with Python and Java equivalents), and Semgrep ships ReDoS rules.
  • By construction: the blow-up is a property of the backtracking algorithm, not of regular expressions. An engine that simulates a finite automaton — RE2, and the Rust regex and Go regexp libraries, which follow RE2's design — matches in time linear in the input, so catastrophic backtracking cannot occur. Such an engine has no backreferences, because (.*)\1 is not a regular expression at all: it describes a language that is not regular, nor even context-free, and matching it is NP-complete (Aho 1990)2. Perl-derived syntax kept the name while describing a strictly larger class of patterns. Where the patterns are genuinely regular, swapping the engine is often a better fix than policing individual ones.
  • Escalate past the regex: a pattern that genuinely needs backreferences is a grammar wearing regex syntax, and the fix is a parser rather than a longer pattern. Parsing expression grammars replace nondeterministic choice with prioritized choice, so a PEG is unambiguous by construction, and a linear-time parser can be built for any PEG by memoizing (Ford 2002, 2004)3 4 — more expressive than regular languages without the exponential. Rosie packages this as a regex replacement with composable, testable named patterns, built on LPeg. The guarantee is not free: memoization costs memory linear in the input, and PEG engines that skip it keep backtracking — Rosie claims linear runtime "for common use cases", not universally.

When to use, when not

The overview carries the shared adoption economics; at the deep end specifically:

Use:

  • CodeQL or Semgrep at diff time for security-sensitive code, where a cross-module dataflow finding is worth the extra runtime.
  • ReDoS analysis on any service that compiles attacker-influenced regexes, or a linear-time engine to remove the risk outright.

Don't:

  • Run the heavy engines on every keystroke; they belong at diff time or in CI, not inline in the editor.

Evidence

Dataflow and query analysis — measured recall is low, and where the finding is shown matters more than how precise it is.

  • Most real bugs go unreported. Against 594 real bugs from 15 Java projects, Error Prone, Infer and SpotBugs together detected 27 — 4.5% — while emitting 5,247 warnings on the files involved (Habib and Pradel 2018)5. The detectors were largely complementary: 18 of the 27 were found by SpotBugs alone, so one tool is not a proxy for the class. The 4.5% is a lower bound: the sample contains only defects that reached version control, which excludes whatever a detector already stopped upstream.
  • Security recall is no better. Six C/C++ analyzers, CodeQL among them, missed between 47% and 80% of the 192 real vulnerabilities in 27 open-source projects (1.15 million lines). Combining every tool's output cut the miss rate to 30–69%, at the cost of flagging 15 percentage points more functions (Lipp et al. 2022)6.
  • Deployment beats precision. Infer at Facebook reported at under 20% false positives and was almost entirely ignored in batch mode — a near-zero fix rate. The same analysis at the same false-positive rate reached a fix rate above 70% once reported on the diff under review (Distefano et al. 2019)7.

ReDoS — the vulnerable patterns are documented; the threat and the fixes are not.

  • Vulnerable patterns are widespread. Thousands of super-linear regexes were found across npm and PyPI, affecting more than 10,000 modules (Davis et al. 2018)1.
  • Automaton analysis over anti-pattern heuristics. The conventional anti-pattern heuristics had few false negatives but many false positives, making them necessary but not sufficient signals of super-linear behavior (Davis et al. 2018)1. That is the empirical case for preferring an automaton-based analyzer to safe-regex.
  • Real-world impact is unestablished. A 2025 systematization found that almost no study evaluates whether ReDoS weaknesses can actually be weaponized against real systems, and that mainstream engines have since added partial or full defenses that render many published threat models obsolete (Bhuiyan et al. 2025)8. Evaluating those defenses, and supporting migration to them, is named as open work. Swapping to a linear-time engine therefore rests on the construction argument, not on measured outcomes.
  • Backreferences fall outside the detectors. The automaton models the current detectors are built on do not cover backreferences. A preprint reports 45 previously unknown quadratic-or-worse vulnerabilities in the Snort ruleset in exactly the regime where existing detectors report nothing (Liu et al. 2026)9.
  • Developers do not reach for the parser. Shown all three repair strategies for a super-linear regex, developers favored revising the regex over truncating the input or writing a custom parser (Davis et al. 2018)1.

Classification

  • Quality dimensions: Security, Functionality, Reliability.
  • Area: Semantic analysis over a model of the program: cross-language query and dataflow engines, and automaton analysis of regular expressions.
  • Guarantee: Empirical.

Referenced by

References

  1. Davis, James C., Christy A. Coghlan, Francisco Servant, and Dongyoon Lee. 2018. "The Impact of Regular Expression Denial of Service (ReDoS) in Practice: An Empirical Study at the Ecosystem Scale." Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2018), 246–56. https://doi.org/10.1145/3236024.3236027. ↩↩↩↩

  2. Aho, Alfred V. 1990. "Algorithms for Finding Patterns in Strings." In Handbook of Theoretical Computer Science, Volume a: Algorithms and Complexity, edited by Jan van Leeuwen. Elsevier. https://doi.org/10.1016/B978-0-444-88071-0.50010-2. ↩

  3. Ford, Bryan. 2002. "Packrat Parsing: Simple, Powerful, Lazy, Linear Time." Proceedings of the Seventh ACM SIGPLAN International Conference on Functional Programming (ICFP '02), 36–47. https://doi.org/10.1145/581478.581483. ↩

  4. Ford, Bryan. 2004. "Parsing Expression Grammars: A Recognition-Based Syntactic Foundation." Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '04), 111–22. https://doi.org/10.1145/964001.964011. ↩

  5. Habib, Andrew, and Michael Pradel. 2018. "How Many of All Bugs Do We Find? A Study of Static Bug Detectors." Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering (ASE '18), 317–28. https://doi.org/10.1145/3238147.3238213. ↩

  6. Lipp, Stephan, Sebastian Banescu, and Alexander Pretschner. 2022. "An Empirical Study on the Effectiveness of Static C Code Analyzers for Vulnerability Detection." Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2022), 544–55. https://doi.org/10.1145/3533767.3534380. ↩

  7. Distefano, Dino, Manuel Fähndrich, Francesco Logozzo, and Peter W. O'Hearn. 2019. "Scaling Static Analyses at Facebook." Communications of the ACM 62 (8): 62–70. https://doi.org/10.1145/3338112. ↩

  8. Bhuiyan, Masudul Hasan Masud, Berk Çakar, Ethan H. Burmane, James C. Davis, and Cristian-Alexandru Staicu. 2025. "SoK: A Literature and Engineering Review of Regular Expression Denial of Service (ReDoS)." Proceedings of the 20th ACM Asia Conference on Computer and Communications Security (ASIA CCS '25), 1659–75. https://doi.org/10.1145/3708821.3733912. ↩

  9. Liu, Yichen, Berk Çakar, Aman Agrawal, Minseok Seo, James C. Davis, and Dongyoon Lee. 2026. Regular Expression Denial of Service Induced by Backreferences. https://doi.org/10.48550/arXiv.2602.21459. ↩