Team for Research in
Ubiquitous Secure Technology

Citation
Cody Hartwig. "Towards Automatic Discovery of Deviations in Binary Implementations". Talk or presentation, 11, October, 2007.

Abstract
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 detection and fingerprint generation. 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 implementation, our 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.

Electronic downloads

• HTML

  Cody Hartwig. <a
  href="http://www.truststc.org/pubs/300.html"
  ><i>Towards Automatic Discovery of Deviations in
  Binary Implementations</i></a>, Talk or
  presentation,  11, October, 2007.

• Plain text

  Cody Hartwig. "Towards Automatic Discovery of
  Deviations in Binary Implementations". Talk or
  presentation,  11, October, 2007.

• BibTeX

  @presentation{Hartwig07_TowardsAutomaticDiscoveryOfDeviationsInBinaryImplementations,
      author = {Cody Hartwig},
      title = {Towards Automatic Discovery of Deviations in
                Binary Implementations},
      day = {11},
      month = {October},
      year = {2007},
      abstract = {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 detection and
                fingerprint generation. 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
                implementation, our 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.},
      URL = {http://www.truststc.org/pubs/300.html}
  }
  

Posted by Larry Rohrbough on 16 Oct 2007.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.