Inter-context control-flow and data-flow test adequacy criteria for nesC applications

ABSTRACT

NesC is a programming language for applications that run on top of networked sensor nodes. Such an application mainly uses an interrupt to trigger a sequence of operations, known as contexts, to perform its actions. However, a high degree of inter-context interleaving in an application can cause it to be error-prone. For instance, a context may mistakenly alter another context's data kept at a shared variable. Existing concurrency testing techniques target testing programs written in general-purpose programming languages, where a small scale of inter-context interleaving between program executions may make these techniques inapplicable. We observe that nesC blocks new context interleaving when handling interrupts, and this feature significantly restricts the scale of inter-context interleaving that may occur in a nesC application. This paper models how operations on different contexts may interleave as inter-context flow graphs. Based on these graphs, it proposes two test adequacy criteria, one on inter-context data-flows and another on inter-context control-flows. It evaluates the proposal by a real-life open-source nesC application. The empirical results show that the new criteria detect significantly more failures than their conventional counterparts.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Glenn Ammons , Thomas Ball , James R. Larus, Exploiting hardware performance counters with flow and context sensitive profiling, ACM SIGPLAN Notices, v.32 n.5, p.85-96, May 1997
• 3: James H. Andrews , Lionel C. Briand , Yvan Labiche , Akbar Siami Namin, Using Mutation Analysis for Assessing and Comparing Testing Coverage Criteria, IEEE Transactions on Software Engineering, v.32 n.8, p.608-624, August 2006 [doi>10.1109/TSE.2006.83]
• 4: Will Archer , Philip Levis , John Regehr, Interface contracts for TinyOS, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236382]
• 5: 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
• 6: Elaine Cheong , Judy Liebman , Jie Liu , Feng Zhao, TinyGALS: a programming model for event-driven embedded systems, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952668]
• 7: Nathan Cooprider , Will Archer , Eric Eide , David Gay , John Regehr, Efficient memory safety for TinyOS, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322283]
• 8: P. G. Frankl , S. N. Weiss, An Experimental Comparison of the Effectiveness of Branch Testing and Data Flow Testing, IEEE Transactions on Software Engineering, v.19 n.8, p.774-787, August 1993 [doi>10.1109/32.238581]
• 9: P. G. Frankl , E. J. Weyuker, An Applicable Family of Data Flow Testing Criteria, IEEE Transactions on Software Engineering, v.14 n.10, p.1483-1498, October 1988 [doi>10.1109/32.6194]
• 10: 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
• 11: Mary Jean Harrold , Mary Lou Soffa, Efficient computation of interprocedural definition-use chains, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.2, p.175-204, March 1994 [doi>10.1145/174662.174663]
• 12: Chih-Chieh Han , Ram Kumar , Roy Shea , Eddie Kohler , Mani Srivastava, A dynamic operating system for sensor nodes, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington [doi>10.1145/1067170.1067188]
• 13: Thomas A. Henzinger , Ranjit Jhala , Rupak Majumdar, Race checking by context inference, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 14: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, ACM SIGOPS Operating Systems Review, v.34 n.5, p.93-104, Dec. 2000
• 15: Hill, T. and Lewicki, P. 2007. STATISTICS Methods and Applications. StatSoft, Tulsa, OK, 2007.
• 16: J. C. Huang, An Approach to Program Testing, ACM Computing Surveys (CSUR), v.7 n.3, p.113-128, Sept. 1975 [doi>10.1145/356651.356652]
• 17: Monica Hutchins , Herb Foster , Tarak Goradia , Thomas Ostrand, Experiments of the effectiveness of dataflow- and controlflow-based test adequacy criteria, Proceedings of the 16th international conference on Software engineering, p.191-200, May 16-21, 1994, Sorrento, Italy
• 18: Tapas Kanungo , David M. Mount , Nathan S. Netanyahu , Christine D. Piatko , Ruth Silverman , Angela Y. Wu, An Efficient k-Means Clustering Algorithm: Analysis and Implementation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.7, p.881-892, July 2002 [doi>10.1109/TPAMI.2002.1017616]
• 19: Sukun Kim , Shamim Pakzad , David Culler , James Demmel , Gregory Fenves , Steven Glaser , Martin Turon, Health monitoring of civil infrastructures using wireless sensor networks, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236395]
• 20: Yu Lei , Richard H. Carver, Reachability Testing of Concurrent Programs, IEEE Transactions on Software Engineering, v.32 n.6, p.382-403, June 2006 [doi>10.1109/TSE.2006.56]
• 21: Philip Levis , Nelson Lee , Matt Welsh , David Culler, TOSSIM: accurate and scalable simulation of entire TinyOS applications, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958506]
• 22: Heng Lu , W. K. Chan , T. H. Tse, Testing context-aware middleware-centric programs: a data flow approach and an RFID-based experimentation, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA [doi>10.1145/1181775.1181805]
• 23: Heng Lu , W.K. Chan , T.H. Tse, Testing pervasive software in the presence of context inconsistency resolution services, Proceedings of the 30th international conference on Software engineering, May 10-18, 2008, Leipzig, Germany [doi>10.1145/1368088.1368098]
• 24: Atif M. Memon , Mary Lou Soffa , Martha E. Pollack, Coverage criteria for GUI testing, Proceedings of the 8th European software engineering conference held jointly with 9th ACM SIGSOFT international symposium on Foundations of software engineering, September 10-14, 2001, Vienna, Austria
• 25: Nguyet T. M. Nguyen , Mary Lou Soffa, Program representations for testing wireless sensor network applications, Workshop on Domain specific approaches to software test automation: in conjunction with the 6th ESEC/FSE joint meeting, p.20-26, September 04-04, 2007, Dubrovnik, Croatia [doi>10.1145/1294921.1294925]
• 26: 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]
• 27: Matthew J. Rutherford , Antonio Carzaniga , Alexander L. Wolf, Simulation-based test adequacy criteria for distributed systems, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA [doi>10.1145/1181775.1181804]
• 28: TinyOS Tutorials. Modules and the TinyOS execution model. http://docs.tinyos.net/index.php/Modules_and_the_TinyOS_Execution_Model.
• 29: Ben L. Titzer , Daniel K. Lee , Jens Palsberg, Avrora: scalable sensor network simulation with precise timing, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 30: T. H. Tse , Stephen S. Yau , W. K. Chan , Heng Lu , T. Y. Chen, Testing Context-Sensitive Middleware-Based Software Applications, Proceedings of the 28th Annual International Computer Software and Applications Conference (COMPSAC'04), p.458-466, September 28-30, 2004
• 31: Zhimin Wang , Sebastian Elbaum , David S. Rosenblum, Automated Generation of Context-Aware Tests, Proceedings of the 29th international conference on Software Engineering, p.406-415, May 20-26, 2007 [doi>10.1109/ICSE.2007.18]
• 32: Qing Xie , Atif M. Memon, Designing and comparing automated test oracles for GUI-based software applications, ACM Transactions on Software Engineering and Methodology (TOSEM), v.16 n.1, p.4-es, February 2007 [doi>10.1145/1189748.1189752]
• 33: Cheer-Sun D. Yang , Amie L. Souter , Lori L. Pollock, All-du-path coverage for parallel programs, Proceedings of the 1998 ACM SIGSOFT international symposium on Software testing and analysis, p.153-162, March 02-04, 1998, Clearwater Beach, Florida, United States
• 34: Yuting Zhang , Richard West, Process-Aware Interrupt Scheduling and Accounting, Proceedings of the 27th IEEE International Real-Time Systems Symposium, p.191-201, December 05-08, 2006 [doi>10.1109/RTSS.2006.37]
• 35: Hong Zhu , Patrick A. V. Hall , John H. R. May, Software unit test coverage and adequacy, ACM Computing Surveys (CSUR), v.29 n.4, p.366-427, Dec. 1997 [doi>10.1145/267580.267590]

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)

General Terms:
Experimentation, Reliability, Verification

Keywords:
networked embedded system, software testing, test adequacy criteria