Service Denied! Understanding How Regex DoS Attacks Work
summary
Specially formatted strings can knock a Rails app offline by triggering exponential work in CRuby’s backtracking regex engine; the talk inspects the CRuby internals, shows 36-character input taking 7 minutes on a pathological pattern, and demonstrates a DFA-based engine that runs the same case in 22 seconds vs 22 milliseconds. Concrete defenses include never allow users to supply regexes, truncating inputs, upgrading Ruby/Rails, and using regex timeouts (Ruby 3.2 adds them) or simpler patterns to avoid nested quantifiers.
AI-written summary · about
chapters (23)
- 0:00Introduction
- 2:21TruffleRuby benchmarks
- 3:24Talk structure
- 4:06ReDoS in 2021
- 5:09Motivation for research
- 6:55Denial of service attack
- 8:59Regex DoS attacks
- 10:02Benchmark limitations
- 11:45Algorithmic complexity
- 13:09Big O notation
- 15:33ReDoS exponential example
- 16:57Regular expressions
- 18:41Regex engines NFAs vs DFAs
- 21:50Backtracking risks
- 23:53DFA linear matching
- 24:35Expressiveness of NFAs and DFAs
- 25:17Rails ReDoS impact
- 25:38Preventing ReDoS attacks
- 27:00Ruby Rails ReDoS response
- 27:42Safer regex patterns
- 29:06Pathological cases
- 29:27Big O for performance
- 30:09Further reading
related talks
31mOh no! My regex is causing a Denial of Service! What can I do about it?
43mTotal ReDoS: the dangers of regex in JavaScript
38mTotal ReDoS: the Dangers of Regex in JavaScript
26mTotal ReDoS: The Dangers of regex in JavaScript
39mRegular Expressions Inside Out
38mParsing Expressions in Ruby
32mSecuring Your Rails App
36ms/regex/DSLs/: What Regex Teaches Us About DSL Design