Testing CPU emulators

ABSTRACT

A CPU emulator is a software that simulates a hardware CPU. Emulators are widely used by computer scientists for various kind of activities (e.g., debugging, profiling, and malware analysis). Although no theoretical limitation prevents to develop an emulator that faithfully emulates a physical CPU, writing a fully featured emulator is a very challenging and error-prone task. Modern CISC architectures have a very rich instruction set, some instructions lack proper specifications, and others may have undefined effects in corner-cases. This paper presents a testing methodology specific for CPU emulators, based on fuzzing. The emulator is "stressed" with specially crafted test-cases, to verify whether the CPU is properly emulated or not. Improper behaviours of the emulator are detected by running the same test-case concurrently on the emulated and on the physical CPUs and by comparing the state of the two after the execution. Differences in the final state testify defects in the code of the emulator. We implemented this methodology in a prototype (codenamed EmuFuzzer), analysed four state-of-the-art IA-32 emulators (QEMU, Valgrind, Pin and BOCHS), and found several defects in each of them, some of which can prevent the proper execution of programs.

REFERENCES

• 1: U. Bayer, C. Kruegel, and E. Kirda. TTAnalyze: A Tool for Analyzing Malware. In 15th European Institute for Computer Antivirus Research Annual Conference (EICAR 2006), 2006.
• 2: Fabrice Bellard, QEMU, a fast and portable dynamic translator, Proceedings of the annual conference on USENIX Annual Technical Conference, p.41-41, April 10-15, 2005, Anaheim, CA
• 3: Cristian Cadar , Vijay Ganesh , Peter M. Pawlowski , David L. Dill , Dawson R. Engler, EXE: automatically generating inputs of death, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180445]
• 4: Brett Daniel , Danny Dig , Kely Garcia , Darko Marinov, Automated testing of refactoring engines, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia [doi>10.1145/1287624.1287651]
• 5: J. DeMott. The Evolving Art of Fuzzing. http://www.vdalabs.com/tools/The_Evolving_Art_of_Fuzzing.pdf.
• 6: Artem Dinaburg , Paul Royal , Monirul Sharif , Wenke Lee, Ether: malware analysis via hardware virtualization extensions, Proceedings of the 15th ACM conference on Computer and communications security, October 27-31, 2008, Alexandria, Virginia, USA [doi>10.1145/1455770.1455779]
• 7: P. Ferrie. Attacks on Virtual Machine Emulators. Technical report, Symantec Advanced Threat Research, 2006.
• 8: T. Garfinkel and M. Rosenblum. A Virtual Machine Introspection Based Architecture for Intrusion Detection. In Proceedings of Network and Distributed Systems Security Symposium, NDSS, San Diego, California, USA. The Internet Society, Feb. 2003.
• 9: P. Godefroid, M. Y. Levin, and D. Molnar. Automated Whitebox Fuzz Testing. In Proceedings of the Network and Distributed System Security Symposium, 2008.
• 10: Google Inc. Android emulator. http://code.google.com/android/reference/emulator.html.
• 11: Intel. Intel 64 and IA-32 Architectures Software Developer's Manual, Nov. 2008. Instruction Set Reference.
• 12: R. Kaksonen. A Functional Method for Assessing Protocol Implementation Security. Technical report, VTT Electronics, 2001.
• 13: Jack Koziol , David Litchfield , Dave Aitel , Chris Anley , Sinan Eren , Neel Mehta , Riley Hassell, The Shellcoder's Handbook: Discovering and Exploiting Security Holes, John Wiley & Sons, 2004
• 14: Kevin P. Lawton, Bochs: A Portable PC Emulator for Unix/X, Linux Journal, v.1996 n.29es, Sept. 1996
• 15: H. A. Lichstein. When Should You Emulate? Datamation, 1969.
• 16: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 17: Peter S. Magnusson , Magnus Christensson , Jesper Eskilson , Daniel Forsgren , Gustav Hållberg , Johan Högberg , Fredrik Larsson , Andreas Moestedt , Bengt Werner, Simics: A Full System Simulation Platform, Computer, v.35 n.2, p.50-58, February 2002 [doi>10.1109/2.982916]
• 18: Rupak Majumdar , Koushik Sen, Hybrid Concolic Testing, Proceedings of the 29th international conference on Software Engineering, p.416-426, May 20-26, 2007 [doi>10.1109/ICSE.2007.41]
• 19: Lorenzo Martignoni , Elizabeth Stinson , Matt Fredrikson , Somesh Jha , John C. Mitchell, A Layered Architecture for Detecting Malicious Behaviors, Proceedings of the 11th international symposium on Recent Advances in Intrusion Detection, September 15-17, 2008, Cambridge, MA, USA [doi>10.1007/978-3-540-87403-4_5]
• 20: W. M. McKeeman. Differential Testing for Software. Digital Technical Journal, 10(1), 1998.
• 21: Barton P. Miller , Louis Fredriksen , Bryan So, An empirical study of the reliability of UNIX utilities, Communications of the ACM, v.33 n.12, p.32-44, Dec. 1990 [doi>10.1145/96267.96279]
• 22: Glenford J. Myers, Art of Software Testing, John Wiley & Sons, Inc., New York, NY, 1979
• 23: NetBSD/amd64. http://www.netbsd.org/ports/amd64/.
• 24: N. Nethercote. Dynamic Binary Analysis and Instrumentation. PhD thesis, Computer Laboratory, University of Cambridge, United Kingdom, Nov. 2004.
• 25: T. Ormandy. An Empirical Study into the Security Exposure to Host of Hostile Virtualized Environments. In Proceedings of CanSecWest Applied Security Conference, 2007.
• 26: D. Quist and V. Smith. Detecting the Presence of Virtual Machines Using the Local Data Table. http://www.offensivecomputing.net/files/active/0/vm.pdf.
• 27: T. Raffetseder, C. Kruegel, and E. Kirda. Detecting System Emulators. In Proceedings of Information Security Conference (ISC 2007). Springer-Verlag, 2007.
• 28: John Scott Robin , Cynthia E. Irvine, Analysis of the Intel Pentium's ability to support a secure virtual machine monitor, Proceedings of the 9th conference on USENIX Security Symposium, p.10-10, August 14-17, 2000, Denver, Colorado
• 29: J. Rutkowska. Red Pill?or how to detect VMM using (almost) one CPU instruction. http://invisiblethings.org/papers/redpill.html.
• 30: Koushik Sen , Darko Marinov , Gul Agha, CUTE: a concolic unit testing engine for C, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 31: Sun Microsystem. VirtualBox. http://www.virtualbox.org.
• 32: Michael Sutton , Adam Greene , Pedram Amini, Fuzzing: Brute Force Vulnerability Discovery, Addison-Wesley Professional, 2007

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

General Terms:
Reliability, Verification

Keywords:
automatic test generation, emulation, fuzzing, software testing