Differential analysis of x86-64 instruction decoders

2021. 5 citations.

Abstract

Differential fuzzing replaces traditional fuzzer oracles like crashes, hangs, unsound memory accesses with a difference oracle, where an implementation of a specification is said to be potentially erroneous if its behavior differs from another implementation’s on the same input. Differential fuzzing has been applied successfully to cryptography software and complex application format parsers like PDF and ELF.This paper describes the application of differential fuzzing to x86-64 instruction decoders for bug discovery. It introduces MISHEGOS, a novel differential fuzzer that discovers decoding discrepancies between instruction decoders. We describe MiSHEGos’s architecture and approach to error discovery, as well as the security implications of decoding errors and discrepancies. We also describe a novel fuzzing strategy for instruction decoders on variable-length architectures based on sliding through an overapproximated model of machine instructions.MISHEGOS produces hundreds of millions of decoder tests per hour on modest hardware. We have used MISHEGOS to discover hundreds of errors in popular x86-64 instruction decoders without relying on a hardware decoder for ground truth. MISHEGOS includes an extensible framework for analyzing the results of a fuzzing campaign, allowing users to discover errors in a single decoder or a variety of discrepancies between multiple decoders. We provide access to MISHEGOS’S source code under a permissive license.

Authors

• William H. Woodruff (Trail of Bits, New York, New York): h-index 46; 10,014 citations; corresponding author
• Niki Carroll (George Mason University): h-index 1; 5 citations
• Sebastiaan Peters (Eindhoven University of Technology): h-index 2; 7 citations

Topics

Parallel Computing and Optimization Techniques, Embedded Systems Design Techniques, Security and Verification in Computing, x86, Computer science

References

• W. M. McKeeman. Differential Testing for Software. 1998;10:100-107.
• Richard McNally, Ken Yiu, D. A. Grove, Damien Gerhardy. Fuzzing: The State of the Art. 2012.
• Rakan El-Khalil, Angelos D. Keromytis. Hydan: Hiding Information in Program Binaries. Lecture notes in computer science. 2004;187-199. doi:10.1007/978-3-540-30191-2_15.
• Michalis Athanasakis, Ηλίας Αθανασόπουλος, Michalis Polychronakis, Georgios Portokalidis, Sotiris Ioannidis. The Devil is in the Constants: Bypassing Defenses in Browser JIT Engines. 2015. doi:10.14722/ndss.2015.23209.
• Roberto Paleari, Lorenzo Martignoni, Giampaolo Fresi Roglia, Danilo Bruschi. N-version disassembly. 2010;265-274. doi:10.1145/1831708.1831741.
• Barton P. Miller, Lars Fredriksen, Bryan So. An empirical study of the reliability of UNIX utilities. Communications of the ACM. 1990;33(12):32-44. doi:10.1145/96267.96279.
• Bennet Yee, David Sehr, Gregory Dardyk, J. Bradley Chen, Robert Muth, Tavis Ormandy, et al. Native Client: A Sandbox for Portable, Untrusted x86 Native Code. 2009;79-93. doi:10.1109/sp.2009.25.
• Christopher Jämthagen, Patrik Lantz, Martin Hell. A new instruction overlapping technique for anti-disassembly and obfuscation of x86 binaries. 2013;1-9. doi:10.1109/water.2013.6707878.
• Derek Bruening, Saman Amarasinghe. Efficient, transparent, and comprehensive runtime code manipulation. 2004.
• Cullen Linn, Saumya Debray. Obfuscation of executable code to improve resistance to static disassembly. 2003;290-299. doi:10.1145/948109.948149.
• Nathan Jay, Barton P. Miller. Structured random differential testing of instruction decoders. 2018;84-94. doi:10.1109/saner.2018.8330199.
• Cullen Linn, Saumya Debray. Obfuscation of executable code to improve resistance to static disassembly. 2003. doi:10.1145/948148.948149.