Regular Expression Engineering

What can regular expressions, viewed through a software-engineering microscope, teach us about building software?

A regular expression, described as one line of software, sits at the centre of three radial spokes with no enclosing triangle. The spokes are three perspectives on the same artifact: regex theory asks what it should mean, through semantics, language features and expressiveness; human factors asks how people reason about it, through comprehension, decision-making, reuse and repair; regex engines ask what happens when it runs, through matching algorithms, performance, ReDoS and defenses. The research results sit in the open sectors between the spokes. Between theory and human factors, portability and composition asks whether meaning survives movement and reuse. Between theory and engines, realization asks whether the engine realizes the intended semantics safely. Between human factors and engines, security in practice asks whether developers can recognize and control pathological behavior.

Regular expressions are a niche topic, and that is part of why they are useful to study. A regex may be only one line of code, yet it is an unusually compact meeting point between formal semantics, human programming behavior, and the implementation choices of the engine that executes it. Many of the problems of software engineering become visible here at a scale where we can study them closely.

That perspective is personal as well as methodological. At IBM, I maintained hundreds of regular expressions used to parse the unstable and largely unspecified output of dozens of command-line tools and their many operating modes. Small expressions became critical infrastructure: reused constantly, difficult to reason about, and dependent on assumptions scattered across languages, runtimes, and evolving interfaces.

We study regular expressions as software artifacts. Across this program, we have asked what their formal semantics promise, how developers understand and reuse them, and how matching engines realize them in practice. Bringing those perspectives together exposes gaps that are easy to miss when any one layer is studied alone.

A small artifact can become critical infrastructure

The programme began with a runtime failure: a single expensive input could stall an entire event-driven server, because one regular expression sat on the path every request took. That framing — performance as a security property — set up everything that followed, and measuring the ecosystem rather than the example turned a known theoretical hazard into a demonstrated and widespread one.

• The case of the poisoned event handler: Weaknesses in the Node.js event-driven architecture
  EuroSec · 2017
  The event-handler poisoning weakness in Node.js, which is where the performance-as-a-security-property line of work began.
• A Sense of Time for JavaScript and Node.js: First-Class Timeouts as a Cure for Event Handler Poisoning
  SECURITY · 2018
  First-class timeouts as a defence against event-handler poisoning. The runtime-side answer that preceded the regex-specific work.
• The Impact of Regular Expression Denial of Service (REDOS) in Practice: an Empirical Study at the Ecosystem Scale best paper
  ESEC/FSE · 2018
  Measured ReDoS across an ecosystem and found super-linear regexes widespread in deployed modules. The result that made the problem concrete.

Shared syntax does not guarantee shared meaning

Regular expression syntax looks portable, and developers reuse it as though it were. It is not. Dialects disagree about what an expression matches, behaviour learned in one language does not transfer intact to another, and composing expressions introduces assumptions that neither part carried alone.

• Testing Regex Generalizability And Its Implications: A Large-Scale Many-Language Measurement Study
  ASE · 2019
  Tested whether regex behaviour generalizes across languages at scale. It does not, which turns portability into an engineering problem.
• Why Aren't Regular Expressions a Lingua Franca? An Empirical Study on the Re-use and Portability of Regular Expressions
  ESEC/FSE · 2019
  Asked why regexes are not portable in practice despite a shared surface syntax, examining reuse across languages directly.
• Is Reuse All You Need? A Systematic Comparison of Regular Expression Composition Strategies
  arXiv · 2025
  Compares strategies for composing regexes, asking whether reuse is the right default at the level of the expression itself.

Compact notation does not make reasoning easy

If a one-line artifact is hard to reason about, that is a software-engineering finding rather than a user error. We study what developers actually understand about the expressions they write and reuse, and what an analysis tool has to explain before its findings can be acted on.

• Regexes are Hard: Decision-making, Difficulties, and Risks in Programming Regular Expressions best paper
  ASE · 2019
  Studied what developers understand when they write regexes, and found the difficulties are in comprehension and decision-making, not syntax.
• Improving Developers' Understanding of Regex Denial of Service Tools through Anti-Patterns and Fix Strategies
  S&P · 2023
  ReDoS tools exist but developers misread their output; this studies how to present findings so they can be acted on.

Execution is part of the semantics that matter

What an expression means in practice includes what the engine does to produce that meaning. Backtracking implementations turn ordinary expressions into pathological ones on some inputs, so the questions of which semantics to preserve, and at what cost, belong to engine design — not solely to the programmer writing the expression.

• Rethinking Regex Engines to Address ReDoS
  ACM Joint Meeting on European Software Engineeri · 2019
  Argued the problem is in the engines: worst-case-exponential matching is an implementation choice, not a property of regular expressions.
• Using Selective Memoization to Defeat Regular Expression Denial of Service (ReDoS)
  S&P · 2021
  Selective memoization defeats ReDoS without abandoning the expressive features that made backtracking engines popular.
• Regular Expression Denial of Service Induced by Backreferences
  arXiv · 2026
  Backreferences reintroduce the vulnerability under different conditions, marking the current boundary of the security result.
• Towards the Systematic Testing of Regular Expression Engines
  JAWs · 2026
  Regex engines themselves are largely untested against their own semantics; this proposes testing them systematically.

Security failures cross the layers

ReDoS is not a defect in any single layer. It appears when a formal property, a developer’s expectation, and an implementation’s cost model disagree, so a defense has to hold at whichever layer is reachable. Sanitization intended to make input safe can itself introduce the vulnerability — and the ecosystem study, the anti-pattern work, and the backreference results above each show, from a different direction, that addressing one view alone leaves the others open.

• Exploiting Input Sanitization for Regex Denial of Service
  ICSE · 2022
  Published sanitization logic tells an attacker which inputs reach the matcher, turning a usability feature into an exploitation aid.
• On the Impact and Defeat of Regex DoS
  The Student Research Competition statement of the ReDoS problem and its defences.

What the regex microscope revealed

Across these studies, the recurring lesson is that even very small software artifacts cross boundaries between specification, human understanding, and implementation. Reuse carries assumptions across those boundaries; failures appear when the assumptions do not travel with the artifact.

• SoK: A Literature and Engineering Review of Regular Expression Denial of Service
  AsiaCCS · 2025
  Consolidates a decade of ReDoS literature and engineering practice into one account of what is known and what is still open.

Funding and support

This work has been supported by:

• US National Science Foundation — Collaborative Research: SaTC: CORE: Small: Improving Sanitization and Avoiding Denial of Service Through Correct and Safe Regexes (#2135156)