Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper presents an innovative model of a program's internal behavior over a set of test inputs, called the probabilistic program dependence graph (PPDG), that facilitates probabilistic analysis and reasoning about uncertain program behavior, particularly that associated with faults. The PPDG is an augmentation of the structural dependences represented by a program dependence graph with estimates of statistical dependences between node states, which are computed from the test set. The PPDG is based on the established framework of probabilistic graphical models, which are widely used in applications such as medical diagnosis. This paper presents algorithms for constructing PPDGs and applying the PPDG to fault diagnosis. This paper also presents preliminary evidence indicating that PPDGs can facilitate fault localization and fault comprehension.

REFERENCES

• 1: Rajeev Alur , Pavol Černý , P. Madhusudan , Wonhong Nam, Synthesis of interface specifications for Java classes, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.98-109, January 12-14, 2005, Long Beach, California, USA
• 2: Rajeev Alur , Pavol Černý , P. Madhusudan , Wonhong Nam, Synthesis of interface specifications for Java classes, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.98-109, January 12-14, 2005, Long Beach, California, USA
• 3: James F. Bowring , James M. Rehg , Mary Jean Harrold, Active learning for automatic classification of software behavior, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA
• 4: Lisa Burnell , Eric Horvitz, Structure and chance: melding logic and probability for software debugging, Communications of the ACM, v.38 n.3, p.31-ff., March 1995 [doi>10.1145/203330.203338]
• 5: 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]
• 6: Hyunsook Do , Sebastian Elbaum , Gregg Rothermel, Supporting Controlled Experimentation with Testing Techniques: An Infrastructure and its Potential Impact, Empirical Software Engineering, v.10 n.4, p.405-435, October 2005 [doi>10.1007/s10664-005-3861-2]
• 7: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 8: Severino F. Galán , Francisco Aguado , Francisco J. Díez , José Mira, NasoNet, Joining Bayesian Networks and Time to Model Nasopharyngeal Cancer Spread, Proceedings of the 8th Conference on AI in Medicine in Europe: Artificial Intelligence Medicine, p.207-216, July 01-04, 2001
• 9: Keith Brian Gallagher, Using program slicing in software maintenance, University of Maryland at Baltimore County, Catonsville, MD, 1990
• 10: Murali Haran , Alan Karr , Alessandro Orso , Adam Porter , Ashish Sanil, Applying classification techniques to remotely-collected program execution data, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 11: Mary Jean Harrold , James A. Jones , Tongyu Li , Donglin Liang , Alessandro Orso , Maikel Pennings , Saurabh Sinha , S. Alexander Spoon , Ashish Gujarathi, Regression test selection for Java software, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.312-326, October 14-18, 2001, Tampa Bay, FL, USA
• 12: David Heckerman , David Maxwell Chickering , Christopher Meek , Robert Rounthwaite , Carl Kadie, Dependency networks for inference, collaborative filtering, and data visualization, The Journal of Machine Learning Research, 1, p.49-75, 9/1/2001 [doi>10.1162/153244301753344614]
• 13: 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
• 14: 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
• 15: 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]
• 16: 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]
• 17: J. W. Laski , B. Korel, A Data Flow Oriented Program Testing Strategy, IEEE Transactions on Software Engineering, v.9 n.3, p.347-354, May 1983 [doi>10.1109/TSE.1983.236871]
• 18: 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
• 19: Chao Liu , Xifeng Yan , Long Fei , Jiawei Han , Samuel P. Midkiff, SOBER: statistical model-based bug localization, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 20: Kevin Patrick Murphy , Stuart Russell, Dynamic bayesian networks: representation, inference and learning, University of California, Berkeley, 2002
• 21: Richard E. Neapolitan, Learning Bayesian Networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 2003
• 22: 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
• 23: A. Podgurski , L. A. Clarke, A Formal Model of Program Dependences and its Implications for Software Testing, Debugging, and Maintenance, IEEE Transactions on Software Engineering, v.16 n.9, p.965-979, September 1990 [doi>10.1109/32.58784]
• 24: Andy Podgurski , David Leon , Patrick Francis , Wes Masri , Melinda Minch , Jiayang Sun , Bin Wang, Automated support for classifying software failure reports, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 25: M. Renieris and S. Reiss. Fault Localization With Nearest Neighbor Queries. In International Conference on Automated Software Engineering, pages 30--39, November 2003.
• 26: Sebastian Thrun, Robotic mapping: a survey, Exploring artificial intelligence in the new millennium, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 27: W. Weimer and G. Necula. Mining Temporal Specifications for Error Detection. In 11th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 461--476, April 2005.
• 28: 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
• 29: 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

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Monitors

General Terms:
Algorithms, Experimentation

Keywords:
fault diagnosis, machine learning, probabilistic graphical models, program analysis