Automated Debugging (CS 560)

2022 Spring
Faculty of Engineering and Natural Sciences
Computer Sci.& Eng.(CS)
3
10
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 OUTCOMES

  • 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.

PROGRAMME OUTCOMES


1. Develop and deepen the current and advanced knowledge in the field with original thought and/or research and come up with innovative definitions based on Master's degree qualifications 4

2. Conceive the interdisciplinary interaction which the field is related with ; come up with original solutions by using knowledge requiring proficiency on analysis, synthesis and assessment of new and complex ideas. 4

3. Evaluate and use new information within the field in a systematic approach. 5

4. Develop an innovative knowledge, method, design and/or practice or adapt an already known knowledge, method, design and/or practice to another field; research, conceive, design, adapt and implement an original subject. 5

5. Critical analysis, synthesis and evaluation of new and complex ideas. 5

6. Gain advanced level skills in the use of research methods in the field of study. 5

7. Contribute the progression in the field by producing an innovative idea, skill, design and/or practice or by adapting an already known idea, skill, design, and/or practice to a different field independently. 4

8. Broaden the borders of the knowledge in the field by producing or interpreting an original work or publishing at least one scientific paper in the field in national and/or international refereed journals. 2

9. Demonstrate leadership in contexts requiring innovative and interdisciplinary problem solving. 1

10. Develop new ideas and methods in the field by using high level mental processes such as creative and critical thinking, problem solving and decision making. 4

11. Investigate and improve social connections and their conducting norms and manage the actions to change them when necessary. 1

12. Defend original views when exchanging ideas in the field with professionals and communicate effectively by showing competence in the field. 4

13. Ability to communicate and discuss orally, in written and visually with peers by using a foreign language at least at a level of European Language Portfolio C1 General Level. 3

14. Contribute to the transition of the community to an information society and its sustainability process by introducing scientific, technological, social or cultural improvements. 1

15. Demonstrate functional interaction by using strategic decision making processes in solving problems encountered in the field. 1

16. Contribute to the solution finding process regarding social, scientific, cultural and ethical problems in the field and support the development of these values. 2


1. Develop the ability to use critical, analytical, and reflective thinking and reasoning 5

2. Reflect on social and ethical responsibilities in his/her professional life. 1

3. Gain experience and confidence in the dissemination of project/research outputs 4

4. Work responsibly and creatively as an individual or as a member or leader of a team and in multidisciplinary environments. 2

5. Communicate effectively by oral, written, graphical and technological means and have competency in English. 2

6. Independently reach and acquire information, and develop appreciation of the need for continuously learning and updating. 4


1. Design and model engineering systems and processes and solve engineering problems with an innovative approach. 5

2. Establish experimental setups, conduct experiments and/or simulations. 5

3. Analytically acquire and interpret data. 1


1. Develop, interpret and use statistical analyses in decision making.


1. Display knowledge of contemporary issues in molecular biology, genetics and bioengineering and apply them to a particular problem.

2. To develop knowledge and theory by using data and scientific methods in molecular biology, genetics and bioengineering.

3. Display a good command of scientific literature in biology, genetics and bioengineering for developing novel projects, improving the quality of research and products


1. Apply knowledge of mathematics, science, and engineering in computer science and engineering related problems. 5

2. Display knowledge of contemporary issues in computer science and engineering and apply to a particular problem. 5

3. Demonstrate the use of results from interpreted data to improve the quality of research or a product in computer science and engineering. 5


1. To have acquired basic theoretical knowledge and technical infrastructure in the field of cyber security,

2. To have developed a deep experience and understanding on the basic methods and human-induced and techinal weaknesses followed by the existing and future cyber attacks, threats and counterfeiting,

3. To be able to analyze an IT infrastructure comprehensively and to determine risk by monitoring the existing weaknesses and to determine a cyber security strategy,

4. To take the necessary measures to prevent possible costs and destruction during the occurrence of cyber attacks,

5. To be able to use current cyber security software tools and related software for professional purposes


1. Understand the conceptual foundations of analytical methods and techniques for data science

2. Understand the theory and practice of applied information systems by developing the necessary computer software skills

3. Transform high-volume data sets into actionable information format and use statistical data analysis tools to support decision making within the corporate structure

4. Understand and apply quantitative modeling and data analysis techniques to extract information from big data and use these findings to analyze business problems, present results using data visualization tools and report findings

5. Understand data quality, data integrity and data veracity, recognize ethical aspects of business related to intellectual property and data privacy


1. Use advanced Math (including probability and/or statistics), advanced sciences, advanced computer and programming, and advanced Electronics engineering knowledge to design and analyze complex electronics circuits, instruments, software and electronic systems with hardware/software. 2

2. Analyze and design advanced communication networks and systems, advanced signal processing algorithms or software using advanced knowledge on diff. equations, linear algebra, complex variables and discrete math. 1


1. Design and model energy systems and processes that will increase efficiency, decrease costs and reduce environmental impact.

2. Develop a basic understanding of the multidisciplinary aspect of energy area and understand the interactions between technical, economic, social and policy aspects.

3. Develop the scientific and technical fundamentals to understand and communicate the working principles of energy systems such as wind turbines, energy storage and conversion devices, electrical power systems, etc.

4. Apply scientific and engineering principles to energy systems for creating innovative solutions to world's energy related problems such as scarce resources, sustainability, energy efficiency and climate change.

5. Interact with researchers from different disciplines to exchange ideas and identify areas of research collaboration to advance the frontiers of present knowledge and technology; determine relevant solution approaches and apply them by preparing a research strategy.

6. Take part in ambitious and highly challenging research to generate value for both the industry and society.


1. Establish a strong theoretical background in several of a broad range of subjects related to the discipline, such as manufacturing processes, service systems design and operation, production planning and control, modeling and optimization, stochastics, statistics. 1

2. Develop novel modeling and / or analytical solution strategies for problems in integrated production and service systems involving human capital, materials, information, equipment, and energy, also using an interdisciplinary approach whenever appropriate. 1

3. Implement solution strategies on a computer platform for decision-support purposes by employing effective computational and experimental tools. 2

4. Acquire skills to independently explore and tackle problems related to the discipline that were not encountered previously. Develop appropriate modeling, solution, implementation strategies, and assess the quality of the outcome. 1


1. Apply a broad knowledge of structure & microstructure of all classes of materials, and the ability to use this knowledge to determine the material properties. 1

2. Apply a broad understanding of the relationships between material properties, performance and processing. 1

3. Apply a broad understanding of thermodynamics, kinetics, transport phenomena, phase transformations and materials aspects of advanced technology. 1

4. Demonstrate hands-on experience using a wide range of materials characterization techniques. 1

5. Demonstrate the use of results from interpreted data to improve the quality of research, a product, or a product in materials science and engineering. 1


1. Develop abstract mathematical thinking and mathematical intuition.

2. Demonstrate a broad understanding of several areas of advanced mathematics and of their interrelations.

3. Have knowledge of the fundamental and advanced concepts, principles and techniques from a range of topics.

4. The ability to tackle complex problems, reveal structures and clarify problems, discover suitable analytical and/or numerical methods and interpret solutions.

5. Analyze problems of the area of specialization, plan strategies for their solution, and apply notions and methods of abstract and/or applied mathematics to solve them.


1. Apply software, modeling, instrumentation, and experimental techniques and their combinations in the design and integration of electrical, electronic, control and mechanical systems. 2

2. Interact with researchers from different disciplines to exchange ideas and identify areas of research collaboration to advance the frontiers of present knowledge and technology; determine relevant solution approaches and apply them by preparing a research strategy. 1

3. Take part in ambitious and highly challenging research to generate value for both the industry and society. 1


1. To have knowledge and experience in the research, design, analysis and development of advanced manufacturing and production systems and the machinery and equipment of these systems

2. Identify product performance and manufacturing processes relationship and optimize process parameters

3. Interpret the resultant data to improve the quality and performance of a product

4. Research and apply manufacturing engineering knowledge on industrial applications


1. Display knowledge of contemporary issues in physics and apply them to specific problems in the field of study.

2. Interpret and criticize newly developed theoretical models and experimental results in a particular field in physics

3. Display a good command of scientific literature in physics for developing novel projects, improving the quality of research and products

4. Apply knowledge of mathematics to analyze experimental results and to solve problems in physics


1. Employ mathematical methods to solve physical problems and understand relevant numerical techniques. 1

2. Conduct basic experiments or simulations. 2

3. Analytically acquire and interpret data. 1

4. Establish thorough understanding of the fundamental principles of physics. 1

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.