AI RESEARCH
On the Complexity of the Matching Problem of Regular Expressions with Backreferences
arXiv CS.CL
•
ArXi:2605.07289v1 Announce Type: cross ReDoS is a well-known type of algorithmic complexity attack, where an adversary supplies maliciously crafted strings to a regular expression matching engine, aiming to exhaust computational resources of systems. Even quadratic-time behavior in matching engines has been exploited in successful attacks, as exemplified by major outages at Stack Overflow and Cloudflare.