Article

Random testing of interrupt-driven software

Author:

John RegehrAuthors Info & Claims

EMSOFT '05: Proceedings of the 5th ACM international conference on Embedded software

Pages 290 - 298

https://doi.org/10.1145/1086228.1086282

Published: 18 September 2005 Publication History

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 Broekman and Edwin Notenboom. Testing Embedded Software. Addison-Wesley, 2002.

Digital Library

[4]

Dennis Brylow, Niels Damgaard, and Jens Palsberg. Static checking of interrupt-driven software. In Proc. of the 23rd Intl. Conf. on Software Engineering (ICSE), pages 47--56, Toronto, Canada, May 2001.

Digital Library

[5]

Tsong Yueh Chen, Fei-Ching Kuo, and Robert G. Merkel. On the statistical properties of the F-measure. In Proc. of the 4th International Conference on Quality Software (QSIC), pages 146--153, Braunschweig, Germany, September 2004.

Digital Library

[6]

Koen Claessen and John Hughes. Testing monadic code with QuickCheck. In Proc. of the ACM SIGPLAN 2002 Haskell Workshop, Pittsburgh, PA, October 2002.

Digital Library

[7]

Christoph Csallner and Yannis Smaragdakis. JCrasher: An automatic robustness tester for Java. Software---Practice and Experience, 34(11):1025--1050, 2004.

Digital Library

[8]

Lydie du Bousquet, Farid Ouabdesselam, Jean-Luc Richier, and Nicolas Zuanon. Lutess: A specification-driven testing environment for synchronous software. In Proc. of the 1999 Intl. Conf. on Software Engineering (ICSE), pages 267--276, Los Angeles, CA, 1999.

Digital Library

[9]

David Gay, Phil Levis, Robert von Behren, Matt Welsh, Eric Brewer, and David Culler. The nesC language: A holistic approach to networked embedded systems. In Proc. of the Conf. on Programming Language Design and Implementation (PLDI), pages 1--11, San Diego, CA, June 2003.

Digital Library

[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, and Kristofer Pister. System architecture directions for networked sensors. In Proc. of the 9th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 93--104, Cambridge, MA, November 2000.

Digital Library

[12]

Philip Koopman and John DeVale. Comparing the robustness of POSIX operating systems. In Proc. of the 29th Fault Tolerant Computing Symp., Madison, WI, June 1999.

Digital Library

[13]

Nathan P. Kropp, Philip J. Koopman, and Daniel P. Siewiorek. Automated robustness testing of off-the-shelf software components. In Proc. of the Fault Tolerant Computing Symp., Munich, Germany, June 1998.

Digital Library

[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.

Digital Library

[15]

Nancy Leveson. Safeware: System Safety and Computers. Addison-Wesley, 1995.

[16]

S. Mankefors, R. Torkar, and A. Boklund. New quality estimations in random testing. In Proc. of the 14th IEEE Intl. Symp. on Software Reliability Engineering (ISSRE), Denver, CO, November 2003.

Digital Library

[17]

Barton P. Miller, Lars Fredriksen, and Bryan So. An empirical study of the reliability of UNIX utilities. Communications of the ACM, 33(12):32--44, December 1990.

Digital Library

[18]

George C. Necula, Scott McPeak, S. P. Rahul, and Westley Weimer. CIL: Intermediate language and tools for analysis and transformation of C programs. In Proc. of the Intl. Conf. on Compiler Construction (CC), pages 213--228, Grenoble, France, April 2002.

Digital Library

[19]

A. Pretschner, O. Slotosch, E. Aiglstorfer, and S. Kriebel. Model based testing for real. Software Tools for Technology Transfer, 5(2--3):140--157, March 2004.

Digital Library

[20]

John Regehr and Usit Duongsaa. Preventing interrupt overload. In Proc. of the 2005 Conf. on Languages, Compilers, and Tools for Embedded Systems (LCTES), Chicago, IL, June 2005.

Digital Library

[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, and Jay Lepreau. Evolving real-time systems using hierarchical scheduling and concurrency analysis. In Proc. of the 24th IEEE Real-Time Systems Symp. (RTSS), Cancun, Mexico, December 2003.

Digital Library

[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.

Digital Library

[26]

Ben L. Titzer and Jens Palsberg. Nonintrusive precision instrumentation of microcontroller software. In Proc. of the 2005 Conf. on Languages, Compilers, and Tools for Embedded Systems (LCTES), Chicago, IL, June 2005.

Digital Library

[27]

Aki Watanabe and Ken Sakamura. A specification-based adaptive test case generation strategy for open operating system standards. In Proc. of the 18th Intl. Conf. on Software Engineering (ICSE), pages 81--89, Berlin, Germany, March 1996.

Digital Library

[28]

Joachim Wegener and Frank Mueller. A comparison of static analysis and evolutionary testing for the verification of timing constraints. Real-Time Systems, 21(3):241--268, November 2001.

Digital Library

[29]

Andreas Zeller and Ralf Hildebrandt. Simplifying and isolating failure-inducing input. IEEE Transactions on Software Engineering, 28(2):183--200, February 2002.

Digital Library

Cited By

Huang RCui CLian JTowey DSun WChen H(2024)Toward Cost-Effective Adaptive Random Testing: An Approximate Nearest Neighbor ApproachIEEE Transactions on Software Engineering10.1109/TSE.2024.337959250:5(1182-1214)Online publication date: 21-Mar-2024
https://dl.acm.org/doi/10.1109/TSE.2024.3379592
Zhao JWu YDong J(2024)Efficient data race detection for interrupt-driven programs via path feasibility analysisThe Journal of Supercomputing10.1007/s11227-024-06189-480:15(21699-21725)Online publication date: 14-Jun-2024
https://doi.org/10.1007/s11227-024-06189-4
Yu BTian CXing HYang ZSu JLu XYang JZhao LLi XDuan ZChandra SBlincoe KTonella P(2023)Detecting Atomicity Violations in Interrupt-Driven Programs via Interruption Points Selecting and Delayed ISR-TriggeringProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616276(1153-1164)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616276
Show More Cited By

Index Terms

Random testing of interrupt-driven software
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

An effective method to control interrupt handler for data race detection
AST '10: Proceedings of the 5th Workshop on Automation of Software Test

Embedded software frequently uses interrupts for timer or I/O processing. If a memory area is used by both an interrupt handler and other routines at the same time, the embedded system has the potential to fail because of unexpected data in the memory. ...
Acceleration of Random Testing for Software
PRDC '13: Proceedings of the 2013 IEEE 19th Pacific Rim International Symposium on Dependable Computing

Random testing has been widely used in both software and hardware testing areas for years, which is applied as black box testing in software testing. This paper takes advantage of the common features of hardware and software random testing, applying the ...
Comparison of adaptive random testing and random testing under various testing and debugging scenarios

Adaptive random testing is an enhancement of random testing. Previous studies on adaptive random testing assumed that once a failure is detected, testing is terminated and debugging is conducted immediately. It has been shown that adaptive random ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EMSOFT '05: Proceedings of the 5th ACM international conference on Embedded software

September 2005

390 pages

ISBN:1595930914

DOI:10.1145/1086228

Conference Chair:
Wayne Wolf
Princeton University, Princeton, NJ

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 September 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

EMSOFT05

Sponsor:

EMSOFT05: Fifth ACM International Conference on Embedded Software 2005

September 18 - 22, 2005

NJ, Jersey City, USA

Acceptance Rates

Overall Acceptance Rate 60 of 203 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

71
Total Citations
View Citations
1,104
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)2

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang RCui CLian JTowey DSun WChen H(2024)Toward Cost-Effective Adaptive Random Testing: An Approximate Nearest Neighbor ApproachIEEE Transactions on Software Engineering10.1109/TSE.2024.337959250:5(1182-1214)Online publication date: 21-Mar-2024
https://dl.acm.org/doi/10.1109/TSE.2024.3379592
Zhao JWu YDong J(2024)Efficient data race detection for interrupt-driven programs via path feasibility analysisThe Journal of Supercomputing10.1007/s11227-024-06189-480:15(21699-21725)Online publication date: 14-Jun-2024
https://doi.org/10.1007/s11227-024-06189-4
Yu BTian CXing HYang ZSu JLu XYang JZhao LLi XDuan ZChandra SBlincoe KTonella P(2023)Detecting Atomicity Violations in Interrupt-Driven Programs via Interruption Points Selecting and Delayed ISR-TriggeringProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616276(1153-1164)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616276
Li CChen RWang BWang ZYu TJiang YGu BYang MJust RFraser G(2023)An Empirical Study on Concurrency Bugs in Interrupt-Driven Embedded SoftwareProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598140(1345-1356)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598140
Li CChen RWang BYu TGao DYang MRyu SSmaragdakis Y(2022)Precise and efficient atomicity violation detection for interrupt-driven programs via staged path pruningProceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3533767.3534412(506-518)Online publication date: 18-Jul-2022
https://dl.acm.org/doi/10.1145/3533767.3534412
Wang YGao FWang LYu TZhao JLi X(2022)Automatic Detection, Validation, and Repair of Race Conditions in Interrupt-Driven Embedded SoftwareIEEE Transactions on Software Engineering10.1109/TSE.2020.298917148:1(346-363)Online publication date: 1-Jan-2022
https://doi.org/10.1109/TSE.2020.2989171
Shen YPeng YChen JShi LDeng F(2022)Interruption-driven resource competition defect model and testing methodology2022 IEEE 6th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC )10.1109/IAEAC54830.2022.9930087(602-616)Online publication date: 3-Oct-2022
https://doi.org/10.1109/IAEAC54830.2022.9930087
Weiss KRottleuthner MSchmidt TWählisch M(2021)PHiLIP on the HiL: Automated Multi-Platform OS Testing With External Reference DevicesACM Transactions on Embedded Computing Systems10.1145/347704020:5s(1-26)Online publication date: 22-Sep-2021
https://dl.acm.org/doi/10.1145/3477040
Huang RSun WXu YChen HTowey DXia X(2021)A Survey on Adaptive Random TestingIEEE Transactions on Software Engineering10.1109/TSE.2019.294292147:10(2052-2083)Online publication date: 1-Oct-2021
https://doi.org/10.1109/TSE.2019.2942921
Chen JWu YMao CChen TChen H(2021)MMFC-ART: a Fixed-size-Candidate-set Adaptive Random Testing approach based on the modified Metric-Memory tree2021 IEEE 21st International Conference on Software Quality, Reliability and Security (QRS)10.1109/QRS54544.2021.00036(248-259)Online publication date: Dec-2021
https://doi.org/10.1109/QRS54544.2021.00036
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents