Fast and Precise Sanitizer Analysis with BEK

Pieter Hooimeijer, Benjamin Livshits, David Molnar, Prateek Saxena, Margus VeanesUSENIX Security 2011 · OpenReview

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 &lt;) 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."

Formal grammar of the BEK domain-specific language.

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.

Architecture of the BEK compiler and analysis pipeline.

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 HTMLEncode implementations 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

BibTeX
@inproceedings{hooimeijer2011fast,
  author = {Pieter Hooimeijer and Benjamin Livshits and David Molnar and Prateek Saxena and Margus Veanes},
  title = {{Fast and Precise Sanitizer Analysis with BEK}},
  booktitle = {USENIX Security},
  year = {2011},
  url = {https://openreview.net/forum?id=LpGnLiE6jNU},
}
Figure