The Tower of Babel

LANGSEC: Language-theoretic Security

"The View from the Tower of Babel"

The Second Language-theoretic Security (LangSec) IEEE S&P Workshop at the IEEE Security & Privacy Symposium 2015 will take place in San Jose on May 21, 2015. For CFP and other workshop info see We are looking for submissions, help with getting the word out, and sponsors!

The First Language-theoretic Security (LangSec) IEEE S&P Workshop at the IEEE Security & Privacy Symposium 2014 took place in San Jose, May 18, 2014. Workshop program and all presented papers are now posted.

The Language-theoretic approach (LANGSEC) regards the Internet insecurity epidemic as a consequence of ad hoc programming of input handling at all layers of network stacks, and in other kinds of software stacks. LANGSEC posits that the only path to trustworthy software that takes untrusted inputs is treating all valid or expected inputs as a formal language, and the respective input-handling routines as a recognizer for that language. The recognition must be feasible, and the recognizer must match the language in required computation power.

When input handling is done in ad hoc way, the de facto recognizer, i.e. the input recognition and validation code ends up scattered throughout the program, does not match the programmers' assumptions about safety and validity of data, and thus provides ample opportunities for exploitation. Moreover, for complex input languages the problem of full recognition of valid or expected inputs may be UNDECIDABLE, in which case no amount of input-checking code or testing will suffice to secure the program. Many popular protocols and formats fell into this trap, the empirical fact with which security practitioners are all too familiar.

LANGSEC helps draw the boundary between protocols and API designs that can and cannot be secured and implemented securely, and charts a way to building truly trustworthy protocols and systems. A longer summary of LangSec in this USENIX Security BoF hand-out, and in the talks, articles, and papers below.

LANGSEC in pictures: Occupy Babel!

How to get on the LANGSEC mailing list: subscribe at

Articles: Talks:
2011 USENIX ;login:
  • "Exploit Programming: from Buffer Overflows to Weird Machines and Theory of Computation", Sergey Bratus, Michael E. Locasto, Meredith L. Patterson, Len Sassaman, Anna Shubina [PDF]

  • "The Halting Problems of Network Stack Insecurity", Len Sassaman, Meredith L. Patterson, Sergey Bratus, Anna Shubina [PDF], [PDF@USENIX]
(The first article explains the "weird machines" view of exploitation, the second one starts with a computation-theoretic view. We recommend reading both, and choosing the reading order based on your background.)

2012 IEEE S&P Journal:

  • "A Patch for Postel's Robustness Principle", Len Sassaman, Meredith L. Patterson, Sergey Bratus, [PDF]
2014 IEEE S&P Journal:
  • Beyond Planted Bugs in "Trusting Trust": The Input-Processing Frontier, Sergey Bratus, Trey Darley, Michael Locasto, Meredith L. Patterson, Rebecca ".bx" Shapiro, Anna Shubina [PDF]

  • Security Applications of Formal Language Theory, Len Sassaman, Meredith L. Patterson, Sergey Bratus, Michael E. Locasto, Anna Shubina [Dartmouth Computer Science Technical Report TR2011-709], published in IEEE Systems Journal, Volume 7, Issue 3, Sept. 2013

  • The View from the Tower of Babel: a Language-theoretic Perspective on Vulnerability Classification, TBA (see Brucon 2012, Shmoocon 2013 talks)


Vulnerabilities & bugs:

Software practice:

  • "LANGSEC 2011-2016", CONFidence 2013 Keynote, Meredith L. Patterson, [slides], [video]
  • "Cats and Dogs Living Together: LangSec is Also About Usability", Meredith L. Patterson, [slides], [video]

Please link to this page as