Automated Debugging (CS 560)

2021 Fall
Faculty of Engineering and Natural Sciences
Computer Sci.& Eng.(CS)
3
10.00
Cemal Yılmaz cyilmaz@sabanciuniv.edu,
Click here to view.
English
Doctoral, Master
--
Formal lecture
Interactive,Discussion based learning,Project based learning,Other
Click here to view.

CONTENT

Program debugging is a process of identifying and fixing bugs. Identifying root causes is the hardest, thus the most expensive, component of debugging. Developers often take a slice of the statements involved in a failure, hypothesize a set of potential causes in an ad hoc manner, and iteratively verify and refine their hypotheses until root causes are located. Obviously, this process can be quite tedious and time-consuming. Furthermore, as software systems are getting increasingly complex, the inefficiencies of the manual debugging process are getting magnified. Many automated approaches have been proposed to facilitate program debugging. All these approaches share the same ultimate goal, which is to help developers quickly and accurately pinpoint the root causes of failures. This course will cover state-of-the-art automated debugging approaches from both practical and research perspectives and will consist of two main parts. The goal of the first part is two folds: 1) To turn program debugging from a black art (as many believe) into a systematic and well-organized discipline; and 2) To provide students with enough background information to read and understand the scientific literature. The topics which will be covered in the first part are: How Failures Come To Be, Tracking Problems, Making Programs Fail, Reproducing Problems, Simplifying Problems, Scientific Debugging, Deducing Errors, and Mining and Detecting Anomalies. The second part of the course will survey the related literature by dividing it into four broad categories, namely static- analysis-based, dynamic-analysis-based, model-based, and empirical approaches.

OBJECTIVE

To turn program debugging from a black magic (as many believe) into a systematic and well-organized discipline.
To introduce the principles of systematic program debugging.
To introduce the principles of automating the debugging process.
To introduce the basics of building automated debugging tools.
To introduce the basics of state-of-the-art debugging tools.
To survey the state-of-the-art approaches in the scientific literature.

LEARNING OUTCOME

Describe and apply the principles of systematic program debugging.
Identify, formulate, analyze, and solve basic problems related to automating the debugging process.
Design and implement basic automated debugging tools.
Use, analyze, and evaluate state-of-the-art debugging tools.
Read and understand the related scientific literature.

ASSESSMENT METHODS and CRITERIA

  Percentage (%)
Final 25
Participation 5
Group Project 50
Presentation 20

RECOMENDED or REQUIRED READINGS

Textbook

Andreas Zeller, "Why Programs Fail: A Guide to Systematic Debugging?", Morgan Kaufmann, ISBN: 1558608664 (Recommended)

Readings

Static-Analysis-Based Approaches

D. Engler, B. Chelf, A. Chou et al., ?Checking system rules using system specific, programmer-written compiler extensions,? in Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, Volume 4, San Diego, California, 2000.

D. Hovemeyer, and W. Pugh, ?Finding bugs is easy,? SIGPLAN Not., vol. 39, no. 12, pp. 92-106, 2004.

Y. Xie, and D. Engler, ?Using redundancies to find errors,? IEEE Transactions on Software Engineering, vol. 29, no. 10, pp. 915-928, 2003.

Dynamic-Analysis-Based Approaches

B. Liblit, A. Aiken, A. X. Zheng et al., ?Bug isolation via remote program sampling,? SIGPLAN Not., vol. 38, no. 5, pp. 141-154, 2003.

J. A. Jones, and M. J. Harrold, ?Empirical evaluation of the tarantula automatic fault-localization technique,? in Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, Long Beach, CA, USA, 2005, pp. 273-282.

H. Agrawal, J. R. Horgan, S. London et al., ?Fault Localization using Execution Slices and Dataflow Tests,? in Proceedings of the 6th International Symposium on Software Reliability Engineering, Toulouse, France, 1995, pp. 143-151.

M. Renieris, and S. P. Reiss, ?Fault Localization With Nearest Neighbor Queries,? in Proceedings of the 18th IEEE International Conference on Automated Software Engineering, Montreal, Canada, 2003, pp. 30-39.

M. Stoerzer, B. G. Ryder, X. Ren et al., ?Finding failure-inducing changes in java programs using change classification,? in Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, Portland, Oregon, USA, 2006, pp. 57-68.

V. Dallmeier, C. Lindig, and A. Zeller, "Lightweight defect localization for java."

D. Abramson, I. Foster, J. Michalakes et al., ?Relative debugging and its application to the development of large numerical models,? in Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), San Diego, California, United States, 1995.

B. Liblit, M. Naik, A. X. Zheng et al., ?Scalable statistical bug isolation,? in Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, Chicago, IL, USA, 2005, pp. 15-26.

S. Hangal, and M. S. Lam, ?Tracking down software bugs using automatic anomaly detection,? in Proceedings of the 24th International Conference on Software Engineering, Orlando, Florida, 2002, pp. 291-301.

J. A. Jones, M. J. Harrold, and J. Stasko, ?Visualization of test information to assist fault localization,? in Proceedings of the 24th International Conference on Software Engineering, Orlando, Florida, 2002, pp. 467-477.

C. Yilmaz, A. Paradkar, and C. Williams, ?Time will tell: fault localization using time spectra,? in Proceedings of the 30th international Conference on Software Engineering, Leipzig, Germany, 2008, pp. 81-90.

Model-Based Approaches

C. Yilmaz, and C. Williams, ?An automated model-based debugging approach,? in Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, Atlanta, Georgia, USA, 2007, pp. 174-183.

C. Mateis, M. Stumptner, D. Wieland et al., "Extended Abstract ? Model-Based Debugging of Java Programs," 2000.

C. Mateis, M. Stumptner, D. Wieland et al., ?Model-Based Debugging of Java Programs,? in Proceedings of the International Workshop on Automated Debugging, 2000.

Empirical Approaches

A. Zeller, ?Isolating cause-effect chains from computer programs,? in Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, Charleston, South Carolina, USA, 2002, pp. 1-10.

A. Zeller, and R. Hildebrandt, ?Simplifying and Isolating Failure-Inducing Input,? IEEE Trans. Softw. Eng., vol. 28, no. 2, pp. 183-200, 2002.

C. Yilmaz, M. Cohen, and A. Porter, ?Covering arrays for efficient fault characterization in complex configuration spaces,? IEEE Trans. Softw. Eng., vol. 32, no. 1, pp. 20-34, 2006.

Other Related Papers

A. Zeller, ?Automated Debugging: Are We Close,? Computer, vol. 34, no. 11, pp. 26-31, 2001.

M. D. Ernst, J. Cockrell, W. G. Griswold et al., ?Dynamically discovering likely program invariants to support program evolution,? in Proceedings of the 21st international conference on Software engineering, Los Angeles, California, United States, 1999, pp. 213-224.

R. Reiter, ?A theory of diagnosis from first principles,? Artificial Intelligence, vol. 32, no. 1, pp. 57-95, 1987.

T. Reps, T. Ball, M. Das et al., ?The use of program profiling for software maintenance with applications to the year 2000 problem,? in Proceedings of the 6th European conference held jointly with the 5th ACM SIGSOFT international symposium on Foundations of software engineering, Zurich, Switzerland, 1997, pp. 432-449.