Random testing of interrupt-driven software

ABSTRACT

Interrupt-driven embedded software is hard to thoroughly test since it usually contains a very large number of executable paths. Developers can test more of these paths using random interrupt testing---firing random interrupt handlers at random times. Unfortunately, naïve application of random testing to interrupt-driven software does not work: some randomly generated interrupt schedules violate system semantics, causing spurious failures. The contribution of this paper is the design, implementation, and experimental evaluation of RID, a restricted interrupt discipline that hardens embedded software with respect to unexpected interrupts, making it possible to perform random interrupt testing and also protecting it from spurious interrupts after deployment. We evaluate RID by implementing it in TinyOS and then using random interrupt testing to find bugs and also to drive applications toward their worst-case stack depths.

REFERENCES

• 1: Jarmo T. Alander, Timo Mantere, and Ghodrat Moghadampour. Testing software response times using a genetic algorithm. In Proc. of the 3rd Nordic Workshop on Genetic Algoritms and their Applications (3NWGA), pages 293--298, 1997.
• 2: Atmel, Inc. ATmega128 datasheet, 2002. http://www.atmel.com/atmel/acrobat/doc2467.pdf.
• 3: Bart M. Broekman, Testing Enbredded Software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 4: 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
• 5: Tsong Yueh Chen , Fei-Ching Kuo , Robert Merkel, On the Statistical Properties of the F-measure, Proceedings of the Quality Software, Fourth International Conference on (QSIC'04), p.146-153, September 08-10, 2004 [doi>10.1109/QSIC.2004.27]
• 6: Koen Claessen , John Hughes, Testing monadic code with QuickCheck, Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, p.65-77, October 03, 2002, Pittsburgh, Pennsylvania [doi>10.1145/581690.581696]
• 7: Christoph Csallner , Yannis Smaragdakis, JCrasher: an automatic robustness tester for Java, Software—Practice & Experience, v.34 n.11, p.1025-1050, September 2004 [doi>10.1002/spe.602]
• 8: L. du Bousquet , F. Ouabdesselam , J.-L. Richier , N. Zuanon, Lutess: a specification-driven testing environment for synchronous software, Proceedings of the 21st international conference on Software engineering, p.267-276, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302634]
• 9: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 10: Richard Hamlet. Random testing. In J. Marciniak, editor, Encyclopedia of Software Engineering. Wiley, second edition, 2001.
• 11: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 12: Philip Koopman , John DeVale, Comparing the Robustness of POSIX Operating Systems, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.30, June 15-18, 1999
• 13: N. P. Kropp , P. J. Koopman , D. P. Siewiorek, Automated Robustness Testing of Off-the-Shelf Software Components, Proceedings of the The Twenty-Eighth Annual International Symposium on Fault-Tolerant Computing, p.230, June 23-25, 1998
• 14: Kim G. Larsen, Marius Mikucionis, and Brian Nielsen. Online testing of real-time systems using UPPAAL. In Proc. of the 4th Intl. Workshop on Formal Approaches to Testing of Software, Linz, Austria, September 2004.
• 15: Nancy G. Leveson, Safeware: system safety and computers, ACM Press, New York, NY, 1995
• 16: S. Mankefors , R. Torkar , A. Boklund, New Quality Estimations in Random Testing, Proceedings of the 14th International Symposium on Software Reliability Engineering, p.468, November 17-21, 2003
• 17: 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]
• 18: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 19: A. Pretschner , O. Slotosch , E. Aiglstorfer , S. Kriebel, Model-based testing for real: The inhouse card case study, International Journal on Software Tools for Technology Transfer (STTT), v.5 n.2, p.140-157, March 2004 [doi>10.1007/s10009-003-0128-3]
• 20: John Regehr , Usit Duongsaa, Preventing interrupt overload, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 21: John Regehr, Alastair Reid, and Kirk Webb. Eliminating stack overflow by abstract interpretation. In Proc. of the 3rd Intl. Conf. on Embedded Software (EMSOFT), pages 306--322, Philadelphia, PA, October 2003.
• 22: John Regehr , Alastair Reid , Kirk Webb , Michael Parker , Jay Lepreau, Evolving real-time systems using hierarchical scheduling and concurrency analysis, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.25, December 03-05, 2003
• 23: Antoine Rollet. Testing robustness of real-time embedded systems. In Proc. of the Workshop on Testing Real-Time and Embedded Systems (WTRTES), Pisa, Italy, September 2003.
• 24: Li Tan, Jesung Kim, and Insup Lee. Testing and monitoring model-based generated program. In Proc. of the Runtime Verification Workshop, Boulder, Colorado, July 2003.
• 25: Ben L. Titzer, Daniel Lee, and Jens Palsberg. Avrora: Scalable sensor network simulation with precise timing. In Proc. of the 4th Intl. Conf. on Information Processing in Sensor Networks (IPSN), Los Angeles, CA, April 2005.
• 26: 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
• 27: Aki Watanabe , Ken Sakamura, A specification-based adaptive test case generation strategy for open operating system standards, Proceedings of the 18th international conference on Software engineering, p.81-89, March 25-29, 1996, Berlin, Germany
• 28: Joachim Wegener , Frank Mueller, A Comparison of Static Analysis and Evolutionary Testing for the Verification of Timing Constraints, Real-Time Systems, v.21 n.3, p.241-268, November 2001 [doi>10.1023/A:1011132221066]
• 29: Andreas Zeller , Ralf Hildebrandt, Simplifying and Isolating Failure-Inducing Input, IEEE Transactions on Software Engineering, v.28 n.2, p.183-200, February 2002 [doi>10.1109/32.988498]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Design, Reliability

Keywords:
embedded systems, interrupt-driven software, random testing, sensor networks