FlashBox: a system for logging non-deterministic events in deployed embedded systems

ABSTRACT

The ability to postmortem failures in deployed systems due to non-deterministic events is useful in crash investigations. With this goal in mind, we propose FlashBox - a system that acts as a black box for embedded systems, recording non-deterministic events (interrupts). The FlashBox hardware consists of a microcontroller and flash memory. The FlashBox software is an extension to a compiler, enabling recording capabilities at various granularities. There are no source code modifications required to use FlashBox and no assumptions made on processor capabilities such as hardware counters. The FlashBox log can be used for faithful replay with a goal to isolate faults and reason about failure.

We present a prototype implementation of FlashBox that logs non-deterministic events on an AVR ATMega169 microcontroller. The FlashBox prototype consists of a 8051 microcontroller with flash memory. The avr-gcc compiler has been extended to log non-deterministic events. Based on our experimental results, FlashBox results in 10-23% overhead while providing capability to log non-deterministic events at instruction level granularity. With decreasing cost of flash memories, FlashBox provides a low cost logging mechanism. The use of standard I/O communication protocols enhances portability, enabling ease of integration for different classes of embedded systems.

REFERENCES

• 1: Atmel. AVR RISC processors. http://www.atmel.com/products/avr/, 2007.
• 2: Dennis Brylow , Niels Damgaard , Jens Palsberg, Static checking of interrupt-driven software, Proceedings of the 23rd International Conference on Software Engineering, p.47-56, May 12-19, 2001, Toronto, Ontario, Canada
• 3: T. A. Cargill , B. N. Locanthi, Cheap hardware support for software debugging and profiling, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.82-83, October 1987, Palo Alto, California, United States
• 4: George W. Dunlap , Samuel T. King , Sukru Cinar , Murtaza A. Basrai , Peter M. Chen, ReVirt: enabling intrusion analysis through virtual-machine logging and replay, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844148]
• 5: E. N. (Mootaz) Elnozahy , Lorenzo Alvisi , Yi-Min Wang , David B. Johnson, A survey of rollback-recovery protocols in message-passing systems, ACM Computing Surveys (CSUR), v.34 n.3, p.375-408, September 2002 [doi>10.1145/568522.568525]
• 6: Colin Fidge , Phil Cook, Model Checking Interrupt-Dependent Software, Proceedings of the 12th Asia-Pacific Software Engineering Conference, p.51-58, December 15-17, 2005 [doi>10.1109/APSEC.2005.80]
• 7: S. Garfinkel. History's worst software bugs. Byte Magazine, November 2005.
• 8: Dennis Geels , Gautam Altekar , Scott Shenker , Ion Stoica, Replay debugging for distributed applications, Proceedings of the annual conference on USENIX '06 Annual Technical Conference, p.27-27, May 30-June 03, 2006, Boston, MA
• 9: Samuel T. King , George W. Dunlap , Peter M. Chen, Debugging operating systems with time-traveling virtual machines, Proceedings of the annual conference on USENIX Annual Technical Conference, p.1-1, April 10-15, 2005, Anaheim, CA
• 10: George Lawton, Improved Flash Memory Grows in Popularity, Computer, v.39 n.1, p.16-18, January 2006 [doi>10.1109/MC.2006.22]
• 11: Nancy G. Leveson, Software safety in embedded computer systems, Communications of the ACM, v.34 n.2, p.34-46, Feb. 1991 [doi>10.1145/102792.102799]
• 12: N. G. Leveson , C. S. Turner, An Investigation of the Therac-25 Accidents, Computer, v.26 n.7, p.18-41, July 1993 [doi>10.1109/MC.1993.274940]
• 13: Ben Liblit , Alex Aiken , Alice X. Zheng , Michael I. Jordan, Bug isolation via remote program sampling, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 14: Afzal Malik , Bill Moyer , Dan Cermak, A low power unified cache architecture providing power and performance flexibility (poster session), Proceedings of the 2000 international symposium on Low power electronics and design, p.241-243, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344610]
• 15: Satish Narayanasamy , Gilles Pokam , Brad Calder, BugNet: Recording Application-Level Execution for Deterministic Replay Debugging, IEEE Micro, v.26 n.1, p.100-109, January 2006 [doi>2006-02-17 02:00:03.800]
• 16: Bernhard Plattner, Real-time execution monitoring, Monitoring and debugging of distributed real-time systems, IEEE Computer Society Press, Los Alamitos, CA, 1995
• 17: Feng Qin , Joseph Tucek , Jagadeesan Sundaresan , Yuanyuan Zhou, Rx: treating bugs as allergies---a safe method to survive software failures, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 18: John Regehr, Random testing of interrupt-driven software, Proceedings of the 5th ACM international conference on Embedded software, September 18-22, 2005, Jersey City, NJ, USA [doi>10.1145/1086228.1086282]
• 19: Yasushi Saito, Jockey: a user-space library for record-replay debugging, Proceedings of the sixth international symposium on Automated analysis-driven debugging, p.69-76, September 19-21, 2005, Monterey, California, USA [doi>10.1145/1085130.1085139]
• 20: J. H. Slye , E. N. Elnozahy, Supporting nondeterministic execution in fault-tolerant systems, Proceedings of the The Twenty-Sixth Annual International Symposium on Fault-Tolerant Computing (FTCS '96), p.250, June 25-27, 1996
• 21: J. Hamilton Slye , E. N. Elnozahy, Support for Software Interrupts in Log-Based Rollback-Recovery, IEEE Transactions on Computers, v.47 n.10, p.1113-1123, October 1998 [doi>10.1109/12.729794]
• 22: Sudarshan M. Srinivasan , Srikanth Kandula , Christopher R. Andrews , Yuanyuan Zhou, Flashback: a lightweight extension for rollback and deterministic replay for software debugging, Proceedings of the annual conference on USENIX Annual Technical Conference, p.3-3, June 27-July 02, 2004, Boston, MA
• 23: Rob Strom , Shaula Yemini, Optimistic recovery in distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.3, p.204-226, Aug. 1985 [doi>10.1145/3959.3962]
• 24: H. Thane. Monitoring, Testing and Debugging of Distributed Real-Time Systems. PhD thesis, May 2000.
• 25: H. Thane. Time machines and black box recorders for embedded systems software. ERCIM News, (52):32--33, January 2003.
• 26: H. Thane and D. Sundmark. Debugging using time machines: replay your embedded system's history. In Real-Time and Embedded Computing Conference, page Kap 22, Milan, Italy, November 2001.
• 27: Henrik Thane , Daniel Sundmark , Joel Huselius , Anders Pettersson, Replay Debugging of Real-Time Systems Using Time Machines, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.288.2, April 22-26, 2003
• 28: Ben L. Titzer , Jens Palsberg, Nonintrusive precision instrumentation of microcontroller software, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 29: J. J. P. Tsai , K.-Y. Fang , H.-Y. Chen , Y.-D. Bi, A Noninterference Monitoring and Replay Mechanism for Real-Time Software Testing and Debugging, IEEE Transactions on Software Engineering, v.16 n.8, p.897-916, August 1990 [doi>10.1109/32.57626]
• 30: USDoT. National highway traffic safety administration nhtsa 03v-240. www.autotechdaily.com/pdfs/T02-05-03.pdf, 2003.