Module: Software Analysis
|Software Analysis||Lecture||2||Winter Semester|
|Software Analysis||Recitation Section (small)||2||Winter Semester|
Prof. Sibylle Schupp
Recommended Previous Knowledge:
- Basic knowledge of software-engineering activities
- Discrete algebraic structures
- Object-oriented programming, algorithms, and data structures
- Functional programming or Procedural programming
Students apply the major approaches to data-flow analysis, control-flow analysis, and type-based analysis, along with their classification schemes, and employ abstract interpretation. They explain the standard forms of internal representations and models, including their mathematical structure and properties, and evaluate their suitability for a particular analysis. They explain and categorize the major analysis algorithms. They distinguish precise solutions from approximative approaches, and show termination and soundness properties.
Presented with an analytical task for a software artifact,
students select appropriate approaches from software analysis, and
justify their choice. They design suitable representations by
modifying standard representations. They develop customized
analyses and devise them as safe overapproximations. They formulate
analyses in a formal way and construct arguments for their
correctness, behavior, and precision.
Students discuss relevant topics in class. They defend their solutions orally. They communicate in English.
Using accompanying on-line material for self study, students can assess their level of knowledge continuously and adjust it appropriately. Working on exercise problems, they receive additional feedback. Within limits, they can set their own learning goals. Upon successful completion, students can identify and precisely formulate new problems in academic or applied research in the field of software analysis. Within this field, they can conduct independent studies to acquire the necessary competencies and compile their findings in academic reports. They can devise plans to arrive at new solutions or assess existing ones.
ECTS-Credit Points Module:
Subject theoretical and practical work
Workload in Hours:
Independent Study Time: 124, Study Time in Lecture: 56
Course: Software Analysis
- Modeling: Control-Flow Modeling, Data Dependences, Intermediate Languages)
- Classical Bit-Vector Analyses (Reaching Definition, Very Busy Expressions, Liveness, Available Expressions, May/Must, Forward/Backward)
- Monotone Frameworks (Lattices, Transfer Functions, Ascending Chain Condition, Distributivity, Constant Propagation)
- Theory of Data-Flow Analysis (Tarski's Fixed Point Theorem, Data-Flow Equations, MFP Solution, MOP Solution, Worklist Algorithm)
- Non-Classical Data-Flow Analyses
- Abstract Interpretation (Galois Connections, Approximating Fixed Points, Construction Techniques)
- Type Systems (Type Derivation, Inference Trees, Algorithm W, Unification)
Recent Developments of Analysis Techniques and Applications
- Flemming Nielsen, Hanne Nielsen, and Chris Hankin. Principles of Program Analysis. Springer, 2nd. ed. 2005.
- Uday Khedker, Amitabha Sanyal, and Bageshri Karkara. Data Flow Analysis: Theory and Practice. CRC Press, 2009.
- Benjamin Pierce, Types and Programming Languages, MIT
- Selected research papers