Penumbra: automatically identifying failure-relevant inputs using dynamic tainting

ABSTRACT

Most existing automated debugging techniques focus on reducing the amount of code to be inspected and tend to ignore an important component of software failures: the inputs that cause the failure to manifest. In this paper, we present a new technique based on dynamic tainting for automatically identifying subsets of a program's inputs that are relevant to a failure. The technique (1) marks program inputs when they enter the application, (2) tracks them as they propagate during execution, and (3) identifies, for an observed failure, the subset of inputs that are potentially relevant for debugging that failure. To investigate feasibility and usefulness of our technique, we created a prototype tool, PENUMBRA, and used it to evaluate our technique on several failures in real programs. Our results are promising, as they show that PENUMBRA can point developers to inputs that are actually relevant for investigating a failure and can be more practical than existing alternative approaches.

REFERENCES

• 1: H. Agrawal, J. Horgan, S. London, and W. Wong. Fault localization using execution slices and dataflow tests. In ISSRE '95: Proceedings of the 6th International Symposium on Software Reliability Engineering, pages 143--151, 1995.
• 2: Martin Burger , Andreas Zeller, Replaying and isolating failing multi-object interactions, Proceedings of the 2008 international workshop on dynamic analysis: held in conjunction with the ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2008), July 21-21, 2008, Seattle, Washington [doi>10.1145/1401827.1401842]
• 3: Tat W. Chan , Arun Lakhotia, Debugging program failure exhibited by voluminous data, Journal of Software Maintenance: Research and Practice, v.10 n.2, p.111-150, March-Arpil 1998 [doi>10.1002/(SICI)1096-908X(199803/04)10:2<111::AID-SMR167>3.3.CO;2-#]
• 4: Ray-Yaung Chang , Andy Podgurski , Jiong Yang, Finding what's not there: a new approach to revealing neglected conditions in software, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273486]
• 5: James Clause , Ioannis Doudalis , Alessandro Orso , Milos Prvulovic, Effective memory protection using dynamic tainting, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, November 05-09, 2007, Atlanta, Georgia, USA [doi>10.1145/1321631.1321673]
• 6: James Clause , Wanchun Li , Alessandro Orso, Dytan: a generic dynamic taint analysis framework, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273490]
• 7: James Clause , Alessandro Orso, A Technique for Enabling and Supporting Debugging of Field Failures, Proceedings of the 29th international conference on Software Engineering, p.261-270, May 20-26, 2007 [doi>10.1109/ICSE.2007.10]
• 8: Neelam Gupta , Haifeng He , Xiangyu Zhang , Rajiv Gupta, Locating faulty code using failure-inducing chops, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101948]
• 9: Wu Ji , Jia Xiao-xia , Liu Chang , Yang Hai-yan , Liu Chao , Jin Mao-zhong, A Statistical Model to Locate Faults at Input Level, Proceedings of the 19th IEEE international conference on Automated software engineering, p.274-277, September 20-24, 2004 [doi>10.1109/ASE.2004.7]
• 10: James A. Jones , Mary Jean Harrold, Empirical evaluation of the tarantula automatic fault-localization technique, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101949]
• 11: James A. Jones , Mary Jean Harrold , John Stasko, Visualization of test information to assist fault localization, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581397]
• 12: B. Korel , J. Laski, Dynamic program slicing, Information Processing Letters, v.29 n.3, p.155-163, October 26, 1988 [doi>10.1016/0020-0190(88)90054-3]
• 13: Ben Liblit , Mayur Naik , Alice X. Zheng , Alex Aiken , Michael I. Jordan, Scalable statistical bug isolation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 14: S. Lu, Z. Li, F. Qin, L. Tan, P. Zhou, and Y. Zhou. Bugbench: Benchmarks for evaulating bug detection tools. In Bugs 2005: Workshop on the Evaluation of Software Defect Detection Tools, 2005.
• 15: Wes Masri , Andy Podgurski , David Leon, Detecting and Debugging Insecure Information Flows, Proceedings of the 15th International Symposium on Software Reliability Engineering, p.198-209, November 02-05, 2004 [doi>10.1109/ISSRE.2004.17]
• 16: Stephen McCamant , Michael D. Ernst, Quantitative information flow as network flow capacity, Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, June 07-13, 2008, Tucson, AZ, USA
• 17: Ghassan Misherghi , Zhendong Su, HDD: hierarchical delta debugging, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134307]
• 18: Piramanayagam Arumuga Nainar , Ting Chen , Jake Rosin , Ben Liblit, Statistical debugging using compound boolean predicates, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273467]
• 19: M. Renieris and S. Reiss. Fault localization with nearest neighbor queries. In ASE '03: Proceedings of the 18th IEEE International Conference on Automated Software Engineering, pages 30--39, 2003.
• 20: Julian Seward , Nicholas Nethercote, Using Valgrind to detect undefined value errors with bit-precision, Proceedings of the annual conference on USENIX Annual Technical Conference, p.2-2, April 10-15, 2005, Anaheim, CA
• 21: G. Tassey. The economic impacts of inadequate infrastructure for software testing. Technical Report 7007.011, National Institute of Standards and Technology, 2002.
• 22: Joseph Tucek , Shan Lu , Chengdu Huang , Spiros Xanthos , Yuanyuan Zhou, Triage: diagnosing production run failures at the user's site, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 23: I. Vessey. Expertise in debugging computer programs. International Journal of Man-Machine Studies: A Process Analysis, 23(5):459--494, 1985.
• 24: Mark Weiser, Program slicing, Proceedings of the 5th international conference on Software engineering, p.439-449, March 09-12, 1981, San Diego, California, United States
• 25: 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]
• 26: Xiangyu Zhang , Haifeng He , Neelam Gupta , Rajiv Gupta, Experimental evaluation of using dynamic slices for fault location, Proceedings of the sixth international symposium on Automated analysis-driven debugging, p.33-42, September 19-21, 2005, Monterey, California, USA [doi>10.1145/1085130.1085135]
• 27: Xiangyu Zhang , Sriraman Tallam , Rajiv Gupta, Dynamic slicing long running programs through execution fast forwarding, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA [doi>10.1145/1181775.1181786]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

General Terms:
Algorithms, Experimentation, Reliability

Keywords:
automated debugging, dynamic information flow, dynamic tainting, failure-relevant inputs