16th USENIX Security Symposium – Abstract
Pp. 213–228 of the Proceedings
Awarded Best Paper!
Towards Automatic Discovery of Deviations in Binary Implementations with Applications to Error Detection and Fingerprint Generation
David Brumley, Juan Caballero, Zhenkai Liang, James Newsome, and Dawn Song, Carnegie Mellon University
Different implementations of the same protocol specification usually
contain deviations, i.e., differences in how they check and
process some of their inputs. Deviations are commonly introduced as
implementation errors or as different interpretations of the same
specification. Automatic discovery of these deviations is important
for several applications. In this paper, we focus on automatic
discovery of deviations for two particular applications: error
We propose a novel approach for automatically detecting
deviations in the way different implementations of the same
specification check and process their input. Our approach has several
advantages: (1) by automatically building symbolic formulas from the
approach is precisely faithful to the implementation; (2) by solving
formulas created from
two different implementations of the same specification, our approach
significantly reduces the number of inputs needed to find
deviations; (3) our approach works on binaries
directly, without access to the source code.
We have built a prototype implementation of our approach and have
evaluated it using multiple implementations of two different protocols:
HTTP and NTP.
Our results show that our approach successfully finds deviations
between different implementations, including errors in input checking,
and differences in the interpretation of the specification, which can
be used as fingerprints.
- View the full text of this paper in HTML and PDF. Listen to the presentation in MP3 format.
The Proceedings are published as a collective work, © 2007 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.