Module Description

Module: Software Analysis

Courses:

TitleTypeHrs/WeekPeriod
Software AnalysisLecture2Winter Semester
Software AnalysisRecitation Section (small)2Winter Semester

Module Responsibility:

Prof. Sibylle Schupp

Admission Requirements:

None

Recommended Previous Knowledge:

  • Basic knowledge of software-engineering activities
  • Discrete algebraic structures
  • Object-oriented programming, algorithms, and data structures
  • Functional programming or Procedural programming

Educational Objectives:

Professional Competence

Theoretical Knowledge

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. 

Capabilities

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.

Personal Competence

Social Competence

Students discuss relevant topics in class. They defend their solutions orally. They communicate in English. 

Autonomy

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:

6 ECTS

Examination:

Subject theoretical and practical work

Workload in Hours:

Independent Study Time: 124, Study Time in Lecture: 56


Course: Software Analysis

Lecturer:

Sibylle Schupp

Language:

English

Period:

Winter Semester

Content:

  • 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

Literature:

  • 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 Press.
  • Selected research papers