Regular expressions are good, actually

Rob King opens with the history of regular expressions, tracing their origins in 1950s automata theory through early Unix tools and the efficient evaluation method Ken Thompson introduced. He separates formal regular expressions from common extensions such as back references and lookaround, explaining that those extensions need memory beyond the current state and therefore break the formal model.

The middle of the talk turns to security problems in mainstream engines. A live demonstration shows a backtracking Python pattern slowing sharply as the input grows, while a Go version finishes in microseconds, illustrating ReDoS. King also covers memory allocation at match time, weak support for streaming and simultaneous matching, incomplete handling of binary data, and unsafe compilation or serialization of patterns. He compares Python, JavaScript, Go, Rust, RE2 and Hyperscan against design criteria he proposes: linear-time matching, preallocated memory, per-thread state, streaming input, binary and text support, and portability.

The closing section explains how a Thompson-style simulation keeps resource use bounded, and how UTF-8's self-synchronizing design lets an engine match raw bytes. King suggests formally checking compiled patterns before loading them and points to reading material for anyone wanting to build an engine. The takeaway is that regex engine design choices directly affect the security of tools that depend on them.