Introduction
Web applications are frequently exposed to untrusted user data, necessitating the use of "sanitizers"—functions designed to escape dangerous characters (e.g., converting < to <) to prevent Cross-Site Scripting (XSS) attacks. However, implementing these functions correctly is notoriously difficult. A single oversight in an HTMLEncode function can leave a system vulnerable. Furthermore, when multiple sanitizers are composed, reasoning about properties like commutativity (does the order of application matter?) and idempotence (does applying it twice change the result?) becomes nearly impossible for humans. This complexity often leads to "sanitizer bypass" vulnerabilities in major software products.
The BEK Framework
To address these challenges, the authors introduce BEK, a system for writing and formally verifying string sanitizers. The framework relies on three core components: a domain-specific language (DSL), a symbolic representation of programs, and integration with automated solvers.
The BEK Language
BEK is a restricted, imperative DSL specifically designed for string manipulation. While expressive enough to model real-world sanitizers, it is constrained to ensure that program properties remain mathematically "decidable."
Symbolic Finite State Transducers (SFTs)
The technical core of BEK is the Symbolic Finite State Transducer (SFT). Traditional transducers struggle with large character sets like Unicode due to state explosion—requiring an edge for every possible character. SFTs overcome this by labeling transitions with logical formulas (e.g., "if character is between 'a' and 'z'") rather than literal characters. This allows the system to handle the entire Unicode range efficiently.
Compiler and SMT Integration
The BEK compiler transforms DSL programs into SFTs, which are then converted into constraints for Z3, a high-performance Satisfiability Modulo Theories (SMT) solver. This enables the tool to automatically prove equivalence between sanitizers or identify specific input strings that cause discrepancies.
Once verified, BEK programs can be compiled directly into efficient C# or JavaScript code, ensuring that the analyzed logic is identical to the deployed implementation.
Evaluation and Key Insights
The authors evaluated BEK using production sanitizers from ASP.NET and OWASP, XSS filters from Internet Explorer 8, and various freelance implementations.
- Performance: The analysis is remarkably fast. Checking the commutativity of all IE8 XSS filters took less than two seconds, while verifying an implementation against a comprehensive XSS Cheat Sheet took under 40 seconds.
- Precision: Unlike tools that use over-approximation, BEK is precise. If a bug is found, it generates a concrete counter-example string demonstrating the vulnerability.
- Algebraic Failures: A key finding was that sanitizers rarely satisfy basic algebraic properties. For instance, only 28.6% of tested sanitizers commuted, suggesting that accidental reordering by developers could easily introduce security holes.
- Human Error: Comparison of freelance
HTMLEncodeimplementations revealed frequent disagreements on edge cases (like backticks or single quotes), highlighting the risks of custom security code.
Limitations and Future Work
BEK currently cannot handle sanitizers requiring "unbounded" state or complex lookahead beyond a fixed window. Additionally, while BEK excels at analyzing the sanitizer itself, it does not yet model the complex parsing logic of web browsers (e.g., WebKit). Future work aims to model browser behavior as SFTs to provide end-to-end security guarantees.
Summary updated