Language-Theoretic Security
A security approach that treats every input as a formal language: define its grammar precisely, keep it as simple as possible, and fully recognize input with a real parser before any other code touches it.
Also known as: LangSec, Language-Based Input Security, Shotgun Parsing, Weird Machines
Category: Software Development
Tags: security, cybersecurity, software-engineering, computer-science, formal-methods, validation, principles
Explanation
Language-theoretic security, or LangSec, starts from one observation: most vulnerabilities are input handling bugs. An attacker sends input that the developers didn't expect, and the program, while trying to make sense of it, ends up doing something it was never meant to do. LangSec's answer is to treat input handling as a language recognition problem and to apply formal language theory to it.
The approach comes from the work of Meredith Patterson, Sergey Bratus, Len Sassaman and others.
**Core principles**:
- **All input is a language**: Every protocol and file format has a grammar, whether someone wrote it down or not. Write it down
- **Recognize fully before processing**: Run the whole input through a parser generated from that grammar. Only input that the parser accepts reaches the business logic
- **Keep the input language weak**: Prefer regular or context-free grammars. The more expressive the input language, the harder it is to validate. For the most powerful classes, deciding whether two implementations accept the same inputs is impossible in general
- **Parser equivalence matters**: Two components that parse the same message have to agree on it. When they don't, you get a parser differential, which attackers exploit
**Anti-patterns that it names**:
- **Shotgun parsing**: Validation checks scattered through the processing code. Some input gets acted upon before it's fully checked
- **Weird machines**: Input complex enough to work as a program for the code that parses it. The attacker is then programming your parser
- **Length fields and nested formats**: Features that push a format beyond context-free. They're a classic source of memory corruption bugs
**LangSec and Postel's Law**:
LangSec is the sharpest critique of "be liberal in what you accept". In their paper "A Patch for Postel's Robustness Principle", Sassaman, Patterson and Bratus propose a replacement: be definite about what you accept. Accept exactly the language you specified, reject the rest, and don't try to repair.
**In practice**:
- Use parser generators or parser combinators instead of hand-written ad hoc parsing
- Choose simple, unambiguous formats
- Parse into typed structures at the boundary (see Parse, Don't Validate)
- Reject ambiguous input, such as duplicate keys or conflicting length indications
Related Concepts
← Back to all concepts