DFA state-space explosion makes DFA-based FTE impractical for many realistic network-monitor regexes: the minimum DFA for `(a|b)*a(a|b){16}` has 131,073 states requiring 266 MB of precomputed tables, while the equivalent NFA has only 36 states requiring 73 KB — a reduction of roughly four orders of magnitude. Some formats in the Snort corpus required up to 383 MB under DFA-based ranking, rendering them prohibitive for deployment.
From 2014-luchaup-libfte — LibFTE: A Toolkit for Constructing Practical, Format-Abiding Encryption Schemes
· §4, Table 6
· 2014
· USENIX Security Symposium
Implications
When selecting target protocol formats for FTE, evaluate the NFA state count rather than the DFA state count — regex patterns with bounded repetition (e.g., `.*a.{N}`) can produce exponentially larger DFAs that make the scheme undeployable.
Audit all regex-based FTE format specifications against DFA explosion before shipping a transport; fall back to NFA-based ranking whenever DFA construction exceeds available memory.