Using Deterministic Replay for Software Fault Injection
https://doi.org/10.15514/ISPRAS-2014-26(2)-5
Abstract
This paper presents method of improving software fault injection by using deterministic replay. Fault injection and fuzzing are the methods of testing used for checking code coverage quality, improving error handling, and robustness testing. Fuzzing can hardly be applied for stateful communication protocols because of program state could change when restarting an application. The main idea of our method is to inject faults while replaying program deterministically. Deterministic replay requires program execution recording for latter replaying. Recorded log includes user input, incoming network packets, USB input, and hardware timers. During replay we read these events from the log and put them back into the simulator instead of reading inputs or receiving packets from the network. After injecting the fault in replay mode the program execution is different. It means that we should stop the replaying and start normal program execution from that program state. During the execution we simulate all hardware timers to make this mode switching imperceptible to the program. With the help of deterministic replay we can accelerate system initialization, eliminate non-deterministic data sources effect, and simplify environment setup, because the whole program execution before injecting fault is recorded. On the basis of the method the network fuzzer was built. The fuzzer modifies selected network packet saved during session recording and sends it back into the simulator. This phase is repeated from the same program state until the bug in the program was found.
Keywords
deterministic replay,
virtual machine,
debugging,
fault injection,
fuzzing,
simulator,
heisenbug,
QEMU
About the Authors
P. M. Dovgalyuk
ISP RAS, Moscow
Russian Federation
Russian Federation
Y. V. Markin
ISP RAS, Moscow
Russian Federation
Russian Federation
References
1. Bieman J. M., Dreilinger D., Lin L. Using Fault Injection to Test Software Recovery Code. Final report, Colorado advanced software institute, 1995, 48 pages.
2. Becker M., Baldin D., Kuznik C., Joy M. M., Xie T., Mueller W. XEMU: an efficient QEMU based binary mutation testing framework for embedded software. Proceedings of the Tenth ACM International Conference on Embedded Software, ACM New York, NY, USA 2012, pp. 33-42. doi: 10.1145/2380356.2380368
3. Han S., Shin K. G., Rosenberg H. A. DOCTOR: An Integrated Software Fault Injection Environment for Distributed Real-time Systems. In Proc. 2nd Annual IEEE Int. Computer Performance and Dependability Symp. (IPDS’95). Erlangen, Germany, 1995. P. 204-213. doi: 10.1109/IPDS.1995.395831
4. Kanawati J., Abraham J. FERRARI: A Tool for the Validation of System Dependability Properties. In Proc. 22nd IEEE Int. Symp. on Fault Tolerant Computing (FTCS-22). Boston, Massachusetts, USA, 1992. P. 336-344. doi: 10.1109/FTCS.1992.243567
5. Segall Z., Vrsalovic D., Siewiorek D., Yaskin D., Kownacki J., Barton R., Dancey A., Robinson T. FIAT – Fault Injection Based Automated Testing Environment. In Proc. 18th IEEE Int. Symp. on Fault Tolerant Computing (FTCS-18). Tokio, Japan, 1988. P. 102-107. doi: 10.1109/FTCS.1988.5306
6. Li Y., Xu P., Wan H. A Fault Injection System Based on QEMU Simulator and Designed for BIT Software Testing. Applied Mechanics and Materials, vol. 347-350, 2013. pp. 580-587.
7. Dawson S., Jahanian F., Mitton T. ORCHESTRA: a probing and fault injection environment for testing protocol implementations. In proceeding of: Computer Performance and Dependability Symposium, 1996, page 56. doi: 10.1109/IPDS.1996.540200
8. B.P. Miller, L. Fredriksen, and B. So. An Empirical Study of the Reliability of UNIX Utilities. Communications of the ACM 33, 12 (December 1990), pages 32-44. doi: 10.1145/96267.96279
9. Jodeit M., Johns M. USB Device Drivers: A Stepping Stone into Your Kernel. Proceedings of the 2010 European Conference on Computer Network Defense, IEEE Computer Society, Washington, DC, USA, 2010. pp. 46-52. doi: 10.1109/EC2ND.2010.16
10. Cha S. K., Avgerinos T., Rebert A., Brumley D. Unleashing mayhem on binary code. SP '12 Proceedings of the 2012 IEEE Symposium on Security and Privacy. IEEE Computer Society Washington, DC, USA 2012, pp. 380-394. doi: 10.1109/SP.2012.31
11. Patrice Godefroid, Michael Y. Levin, and David Molnar. 2012. SAGE: Whitebox Fuzzing for Security Testing. Queue 10, 1, Pages 20 (January 2012), 8 pages. doi: 10.1145/2090147.2094081
12. The KLEE Symbolic Virtual Machine. http://klee.github.io/klee
13. Vitaly Chipounov, Volodymyr Kuznetsov, and George Candea. 2011. S2E: a platform for in-vivo multi-path analysis of software systems. SIGARCH Comput. Archit. News 39, 1 (March 2011), 265-278. doi: 10.1145/1961295.1950396
14. EPDB – a reversible debugger for Python. https://code.google.com/p/epdb
15. Chow J., Lucchetti D., Garfinkel T., Lefebvre G., Gardner R., Mason J., Small S., Chen P. M. Multi-stage replay with Crosscut. VEE '10 Proceedings of the 6th ACM SIGPLAN/SIGOPS international conference on Virtual execution environments. ¬– New York, NY, USA : ACM, 2010. – pp. 13-24. doi: 10.1145/1735997.1736002
16. Jakob Engblom . Back to Reverse Execution. http://blogs.windriver.com/tools/2013/06/back-to-reverse-execution.html
17. Engblom, J. A review of reverse debugging. System, Software, SoC and Silicon Debug Conference (S4D), 2012, pages 1-6.
18. Bellard F. QEMU, a fast and portable dynamic translator. In USENIX 2005 Annual Technical Conf. pages 41–46, Apr. 2005.
19. Dovgalyuk P. Determinirovannoe vosproizvedenie protsessa vypolneniya programm v virtual'noj mashine [Deterministic replay of software in virtual machine]. Trudy Instituta sistemnogo programmirovaniya RАN [The Proceedings of ISP RAS], T. 21, pod red. V.P. Ivannikova. M.: ISP RАN. 2011. S. 123-132. (in Russian)
20. Bania P. Playing with RDTSC. http://www.piotrbania.com/all/articles/playing_with_rdtsc.txt
Review
For citations:
Dovgalyuk P.M., Markin Y.V. Using Deterministic Replay for Software Fault Injection. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(2):119-136. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(2)-5
Email this article 