Structure and chance: melding logic and probability for software debugging

ABSTRACT

Software errors abound in the world of computing. Sophisticated computer programs rank high on the list of the most complex systems ever created by humankind. The complexity of a program or a set of interacting programs makes it extremely difficult to perform offline verification of run-time behavior. Thus, the creation and maintenance of program code is often linked to a process of incremental refinement and ongoing detection and correction of errors. To be sure, the detection and repair of program errors is an inescapable part of the process of software development. However, run-time software errors may be discovered in fielded applications days, months, or even years after the software was last modified—especially in applications composed of a plethora of separate programs created and updated by different people at different times. In such complex applications, software errors are revealed through the run-time interaction of hundreds of distinct processes competing for limited memory and CPU resources. Software developers and support engineers responsible for correcting software problems face difficult challenges in tracking down the source of run-time errors in complex applications. The information made available to engineers about the nature of a failure often leaves open a wide range of possibilities that must be sifted through carefully in searching for an underlying error.

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: Arbon. R,G. Atkinson, I... Chern..J., and Guida. C,.A. TPF dump analyzer: A system to provide expert assistance to ana- Iysts iu solving runqime program exceptions by deriving program intention from a TPF assembly language program In Proceedings of Application of Artificial Intelligence 4 (San.Jose, Calif.. July 12-I6). AAAL, Menlo Park. Calif, 1992. pp. 71-88.
• 3: Burnell. 1..d,, and Horvitz, lb-.}. A synthesis of logical and probabilistic reasoning fbr prograln understanding and de. bugging. In Proceedings of the 91h Conference on Uncertainty in Artificial Intelligence (Washington, D.C., July 9-11). Morgan Kaufinann, San Mate(), Calif.. 1993, pp, 285-291.
• 4: Lisa J. Burnell , Scott E. Talbot, Incorporating Probabilistic Reasoning in a Reactive Program Debugging System, IEEE Expert: Intelligent Systems and Their Applications, v.9 n.1, p.15-20, February 1994 [doi>10.1109/64.295137]
• 5: Hartman. J, Technical introduction to the First Workshop on Artificial Intelligence and Amomated Program Understanding, In workshop Notes of the AAAI-92 14Srl(shop Program: AI & Automated Program Understanding, L. Van Sickle and J. ttart. man, eds. (San jose, Calif July 12-16). AAAI, Menlo Park, Calif, 1992. pp. 8--30,
• 6: Heckerman, D,, Horvitx, E.. and Nathwani. B. Toward m,lmanve expert svst.ems: Part I. The Pathlinder Pro.iect. Meth. ods Inf.Med. 31. 90-105
• 7: Horvitz. E,J, Reasoning under varying and uncertain resource constraints. In Proceedings of the 7th National Conference on Artificial Intellgence (Minneapolis, Minn,, Aug, 21-26) Morgan Kaufmann. San Mateo, CaliL, 1988. pp. 111-116
• 8: Eric J. Horvitz , John S. Breese , Max Henrion, Decision theory in expert systems and artificial intelligence, International Journal of Approximate Reasoning, v.2 n.3, p.247-302, July 1988 [doi>10.1016/0888-613X(88)90120-X]
• 9: Kozaczvnski. W.. Lelovsky, S., and Ning, J. A knowledgebased approach to software system understanding. In Proceeding of the 6th Anrtual Knoweldge-Based Software Engineering ConJerence (Syracuse, N.Y., Sept, 22-25). 1EEE, Los Mamitos, Calif., 199I. pp. 162-170.
• 10: N. G. Lenz , S. F. L. Saelens, A knowledge-based system for MVS dump analysis, IBM Systems Journal, v.30 n.3, p.336-350, 1991
• 11: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 12: Selffidge, P.G Knowledge representation support for a software information system, in Proceedings of the 7th IEEE Conferecnce on AI Applications (Miami Beach, Fla,, Feb. 24-28), IEEE, Los Mamitos. Calif.. 1991, pp. t34-|40.
• 13: Mark Weiser , Jim Lyle, Experiments on slicing-based debugging aids, Papers presented at the first workshop on empirical studies of programmers on Empirical studies of programmers, p.187-197, June 1986, Washington, D.C., United States

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Design, Theory