Lund University → Faculty of Engineering → Department of Computer Science

• EDAP15 Program Analysis
• Moodle
• CourseGit
• Schedule
• Skills
• Homework Exercises

Skills

This page lists all technical skills of relevance to this class, as a study guide. If you find that you possess all the skills listed here, you can consider yourself to have mastered the class. The final exam will draw its expectations from this list: each question in the exam can be solved by using and synthesising the skills listed here, basic arithmetic, and general computer science knowledge from the prerequisite undergraduate core classes.

The percentage of synthesis tasks in which you have to combine known skills in ways not directly covered in the class will be no more than 25% of the total points in the final exam.

Note that the list is preliminary and will be updated throughout the course.

• [0] Foundations: Compilers and Programming Languages
  • [0.0] Lexical Analysis and Parsing (Prerequisite)
  • [0.1] Abstract Syntax Trees (Prerequisite)
  • [0.2] Backus-Naur Form (Prerequisite)
  • [0.3] Dynamic Dispatch (Prerequisite)
  • [0.4] Static Program Semantics
  • [0.5] Dynamic Program Semantics
  • [0.6] Intermediate Program Representations
• [1] Foundations: Formal Concepts
  • [1.0] Sets (Prerequisite)
  • [1.1] Tuples (Prerequisite)
  • [1.2] Relations (Prerequisite)
  • [1.3] Graphs (Prerequisite)
  • [1.4] Metalanguages, Object Languages and Metavariables
  • [1.5] Monotonicity
  • [1.6] Worklist Algorithms
  • [1.7] Lattices
• [2] Properties of Program Analyses
  • [2.0] Static vs. Dynamic Program Analysis
  • [2.1] Automatic vs. Manual Program Analysis
  • [2.2] Soundness and Completeness
  • [2.3] True Positive, False Positive, True Negative, and False Negative
  • [2.4] Precision and Recall
  • [2.5] Flow Sensitivity for Flow Sensitive Analysis (as opposed to Flow Insensitive Analysis)
  • [2.6] May Analysis and Must Analysis
  • [2.7] Call-Site Sensitivity
  • [2.8] Control Sensitivity
  • [2.9] Interprocedural Analysis and Intraprocedural Analysis
  • [2.10] Server Analyses and Client Analyses
  • [2.11] Field Sensitivity
• [3] Type Analysis
  • [3.0] Type System
  • [3.1] Typing Rules
  • [3.2] Type Constructor
  • [3.3] Type Variables and Parametric Polymorphism
  • [3.4] Union-Find Data Structure
  • [3.5] Unification (first-order only)
  • [3.6] Using first-order unification to solve a system of equations
  • [3.7] Monomorphic Type Inference
  • [3.8] Using Monomorphic Type Inference to infer the types and type schemes of a program
  • [3.9] Type Schemes
  • [3.10] Dependency Analysis
  • [3.11] Polymorphic Type Inference
• [4] Control Flow Graphs
  • [4.0] Control Flow Graphs
  • [4.1] Basic Blocks
  • [4.2] Given a program and its semantics, compute the Control Flow Graph
• [5] Data Flow Analysis
  • [5.0] Forward Data Flow Analysis and Backward Data Flow Analysis
  • [5.1] Join Functions and Transfer Functions in Data Flow Analysis
  • [5.2] IN-sets and OUT-sets of control-flow nodes in Data Flow Analysis
  • [5.3] Live Variables Analysis
  • [5.4] Product Lattices
  • [5.5] Reaching Definitions Analysis
  • [5.6] The use of Lattices, including their Top Elements and Bottom Elements, in Data Flow Analysis
  • [5.7] Fixpoints / Fixed Points
  • [5.8] Least Fixpoints
  • [5.9] The MFP Algorithm, and using the MFP algorithm to compute a fixpoint
  • [5.10] Monotone Frameworks
  • [5.11] The MOP Algorithm
  • [5.12] Distributive Frameworks
  • [5.13] Given two alternative intraprocedural data flow program analyses that utilise the concepts discussed in class, discuss their relative merits
  • [5.14] For a simple program analysis problem (analogous to the ones discussed in class), sketch a suitable lattice that encodes the analysis and explain your design choices
  • [5.15] For a given program analysis problem and analysis lattice: given an operation whose semantics you are familiar with, describe a suitable transfer function
  • [5.16] Data Flow on the Interval Abstract Domain
  • [5.17] Widening, including widening on the set of program constants
  • [5.18] Interprocedural Data Flow Analysis via Inlining
  • [5.19] Procedure Summaries
  • [5.20] The IFDS Algorithm
• [6] Pointer Analysis
  • [6.0] Points-To Analysis
  • [6.1] The Aliasing Relation
  • [6.2] Concrete Heap Graphs
  • [6.3] Abstract Heap Graphs
  • [6.4] Utilise the results of an Alias Analysis to improve a Data Flow Analysis
  • [6.5] Store-less and Store-based Pointer Analyses
  • [6.6] Access Paths
  • [6.7] Allocation Site Based Summaries
  • [6.8] Summary Heap Nodes
  • [6.9] The Points-To Relation and Points-To Sets
  • [6.10] Null Pointer Representation Strategies: Unique Null, Many Nulls, Nullness Flags
  • [6.11] Steensgaard's Analysis
  • [6.12] Andersen's Analysis with its Inclusion Edges
  • [6.13] Strong and Weak Updates
• [7] Analysis in the Large
  • [7.0] Call Graphs
  • [7.1] Class Hierarchy Analysis
  • [7.2] Rapid Type Analysis
  • [7.3] How programming language features such as dynamic dispatch or dynamic loading may impair static analysis
  • [7.4] Soundiness
• [8] Dynamic Analysis
  • [8.0] Dynamic Analysis via Instrumentation
  • [8.1] Dynamic Events and their Characteristics
  • [8.2] Samples
  • [8.3] Counting vs. Sampling as measurement strategies
  • [8.4] Read and explain Box Plots
  • [8.5] Perturbation in Dynamic Analysis
  • [8.6] Warm-Up Effects
  • [8.7] Statement Test Coverage Analysis
  • [8.8] Given a Dynamic Program Analysis, identify potential causes of Perturbation
  • [8.9] Given a Sample of Performance Characteristics, give Limits to Generality of the Characteristics

Concepts

For each concept in the above (capitalised or marked as acronyms), you should be able to do the following:

• Give matching examples
• Distinguish it from other concepts
• Explain its relationship to any other concepts (is-part-of, is-alternative-to, is-generalisation-of etc.)
• Explain the purpose or utility of the concept