Something interesting that isn&#x27;t covered in this blog entry but is relevant to many of us is the importance of deterministic parsers for DOS &#x2F; DDOS prevention.  APIs that make use of parsers, be they regular expression parsers, or parsers for more complex grammars such as CFGs, can be abused if the underlying parser is nondeterministic.  Reducing a parser to a DFA (deterministic finite automaton) provides it with measurable performance per character parsed.  If an NFA (non-deterministic finite automaton) is used instead, then an attacker can abuse backtracking to increase parse time, often exponentially.<p>This has been used, quite famously, in standards conforming XML parsers which have some very ugly backtracking issues dealing with entities and entity references.  More commonly, people who decide to add regular expression validation to their APIs are often surprised to discover that an attacker can take up all sorts of server time while the API is trying to validate a carefully crafted degenerate case message.  Many regular expression libraries out there are NFA, including the ones built into some popular high-level language runtimes.