Anomaly-based bug prediction, isolation, and validation: an automated approach for software debugging

ABSTRACT

Software defects, commonly known as bugs, present a serious challenge for system reliability and dependability. Once a program failure is observed, the debugging activities to locate the defects are typically nontrivial and time consuming. In this paper, we propose a novel automated approach to pin-point the root-causes of software failures.

Our proposed approach consists of three steps. The first step is bug prediction, which leverages the existing work on anomaly-based bug detection as exceptional behavior during program execution has been shown to frequently point to the root cause of a software failure. The second step is bug isolation, which eliminates false-positive bug predictions by checking whether the dynamic forward slices of bug predictions lead to the observed program failure. The last step is bug validation, in which the isolated anomalies are validated by dynamically nullifying their effects and observing if the program still fails. The whole bug prediction, isolation and validation process is fully automated and can be implemented with efficient architectural support. Our experiments with 6 programs and 7 bugs, including a real bug in the gcc 2.95.2 compiler, show that our approach is highly effective at isolating only the relevant anomalies. Compared to state-of-art debugging techniques, our proposed approach pinpoints the defect locations more accurately and presents the user with a much smaller code set to analyze.

REFERENCES

• 1: Hiralal Agrawal , Joseph R. Horgan, Dynamic program slicing, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.246-256, June 1990, White Plains, New York, United States
• 2: A. Barr, "Find the Bug", Addison-Wesley, 2004.
• 3: George Z. Chrysos , Joel S. Emer, Memory dependence prediction using store sets, Proceedings of the 25th annual international symposium on Computer architecture, p.142-153, June 27-July 02, 1998, Barcelona, Spain
• 4: Holger Cleve , Andreas Zeller, Locating causes of program failures, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062522]
• 5: Jedidiah R. Crandall , Frederic T. Chong, Minos: Control Data Attack Prevention Orthogonal to Memory Model, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.221-232, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.26]
• 6: Michael Dalton , Hari Kannan , Christos Kozyrakis, Raksha: a flexible information flow architecture for software security, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 7: Martin Dimitrov , Huiyang Zhou, Unified Architectural Support for Soft-Error Protection or Software Bug Detection, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.73-82, September 15-19, 2007 [doi>10.1109/PACT.2007.76]
• 8: Michael D. Ernst , Jake Cockrell , William G. Griswold , David Notkin, Dynamically Discovering Likely Program Invariants to Support Program Evolution, IEEE Transactions on Software Engineering, v.27 n.2, p.99-123, February 2001 [doi>10.1109/32.908957]
• 9: Michael D. Ernst , Adam Czeisler , William G. Griswold , David Notkin, Quickly detecting relevant program invariants, Proceedings of the 22nd international conference on Software engineering, p.449-458, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337240]
• 10: 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]
• 11: Sudheendra Hangal , Monica S. Lam, Tracking down software bugs using automatic anomaly detection, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581377]
• 12: M.J. Harrold, G. Rothermel, K. Sayre, R. Wu and L. Yi, " An empirical investigation of the relationship between spectra differences and regression faults", Journal of Software Testing and Reliability, Vol. 10, No. 3, 2000
• 13: Derek R. Hower , Mark D. Hill, Rerun: Exploiting Episodes for Lightweight Memory Race Recording, Proceedings of the 35th International Symposium on Computer Architecture, p.265-276, June 21-25, 2008
• 14: D. Jeffrey, N. Gupta and R. Gupta, "Identifying the root causes of memory bugs using corrupted memory location suppression", ICSM 2008
• 15: 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]
• 16: S. Lu, Z. Li, F. Qin, L. Tan, P. Zhou and Y. Zhou, "Bugbench: Benchmarks for evaluating bug detection tools", Work. on Eval. of SW Defect Detection Tools, June 2005.
• 17: Shan Lu , Joseph Tucek , Feng Qin , Yuanyuan Zhou, AVIO: detecting atomicity violations via access interleaving invariants, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 18: Brandon Lucia , Joseph Devietti , Karin Strauss , Luis Ceze, Atom-Aid: Detecting and Surviving Atomicity Violations, Proceedings of the 35th International Symposium on Computer Architecture, p.277-288, June 21-25, 2008
• 19: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 20: 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]
• 21: Pablo Montesinos , Luis Ceze , Josep Torrellas, DeLorean: Recording and Deterministically Replaying Shared-Memory Multiprocessor Execution Ef?ciently, Proceedings of the 35th International Symposium on Computer Architecture, p.289-300, June 21-25, 2008
• 22: Satish Narayanasamy , Gilles Pokam , Brad Calder, BugNet: Continuously Recording Program Execution for Deterministic Replay Debugging, Proceedings of the 32nd annual international symposium on Computer Architecture, p.284-295, June 04-08, 2005
• 23: Milos Prvulovic , Josep Torrellas, ReEnact: using thread-level speculation mechanisms to debug data races in multithreaded codes, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 24: Paul Racunas , Kypros Constantinides , Srilatha Manne , Shubhendu S. Mukherjee, Perturbation-based Fault Screening, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.169-180, February 10-14, 2007 [doi>10.1109/HPCA.2007.346195]
• 25: M. Renieris and S. Reiss, "Fault localization with nearest neighbor queries", ASE, 2003
• 26: Harry J. Saal , Israel Gat, A hardware architecture for controlling information flow, Proceedings of the 5th annual symposium on Computer architecture, p.73-77, April 03-05, 1978 [doi>10.1145/800094.803030]
• 27: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
• 28: S. Sidiroglou, M. Locasto and A. Keromytis, "Hardware support for self-healing software services", Workshop on Arch. Supp. for Security and Anti-Virus, 2004.
• 29: Daniel J. Sorin , Milo M. K. Martin , Mark D. Hill , David A. Wood, SafetyNet: improving the availability of shared memory multiprocessors with global checkpoint/recovery, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 30: G. Edward Suh , Jae W. Lee , David Zhang , Srinivas Devadas, Secure program execution via dynamic information flow tracking, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 31: F. Tip, "A survey of program slicing techniques", Journal of Programming Languages, Vol.3, No. 3, 1995.
• 32: N. Wang and S. Patel, "ReStore: Symptom Based Soft Error Detection in Microprocessors", DSN, 2005.
• 33: M. Weiser, "Program Slicing", IEEE TSE, Vol. SE-10, No. 4, 1982.
• 34: Yichen Xie , Dawson Engler, Using redundancies to find errors, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA [doi>10.1145/587051.587060]
• 35: Min Xu , Mark D. Hill , Rastislav Bodik, A regulated transitive reduction (RTR) for longer memory race recording, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 36: Min Xu , Rastislav Bodik , Mark D. Hill, A "flight data recorder" for enabling full-system multiprocessor deterministic replay, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 37: Andreas Zeller, Isolating cause-effect chains from computer programs, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA [doi>10.1145/587051.587053]
• 38: Andreas Zeller, Yesterday, my program worked. Today, it does not. Why?, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.253-267, September 06-10, 1999, Toulouse, France
• 39: Andreas Zeller, Why Programs Fail: A Guide to Systematic Debugging, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 40: 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]
• 41: Xiangyu Zhang , Neelam Gupta , Rajiv Gupta, Pruning dynamic slices with confidence, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 42: Xiangyu Zhang , Rajiv Gupta, Cost effective dynamic program slicing, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 43: Pin Zhou , Feng Qin , Wei Liu , Yuanyuan Zhou , Josep Torrellas, iWatcher: Efficient Architectural Support for Software Debugging, Proceedings of the 31st annual international symposium on Computer architecture, p.224, June 19-23, 2004, München, Germany
• 44: Pin Zhou , Wei Liu , Long Fei , Shan Lu , Feng Qin , Yuanyuan Zhou , Samuel Midkiff , Josep Torrellas, AccMon: Automatically Detecting Memory-Related Bugs via Program Counter-Based Invariants, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.269-280, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.3]

INDEX TERMS

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

General Terms:
Languages, Performance, Reliability

Keywords:
architectural support, automated debugging