Lund University → Faculty of Engineering → Department of Computer Science

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

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] Static Program Semantics
  • [0.4] Dynamic Program Semantics
  • [0.5] Intermediate Program Representations
  • [0.6] Dynamic Dispatch (Prerequisite)
• [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] Context Sensitivity
  • [2.7] Interprocedural Analysis and Intraprocedural Analysis
  • [2.8] May Analysis and Must Analysis
  • [2.9] Server Analyses and Client Analyses
  • [2.10] 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 (new)
  • [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] Type Schemes
  • [3.9] Polymorphic Type Inference
  • [3.10] Using Monomorphic Type Inference to infer the types and type schemes of a program
• [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] The use of Lattices, including their Top Elements and Bottom Elements, in Data Flow Analysis
  • [5.4] Product Lattices
  • [5.5] Fixpoints
  • [5.6] Least Fixpoints
  • [5.7] The MFP Algorithm
  • [5.8] Use the MFP algorithm to compute a fixpoint
  • [5.9] Monotone Frameworks
  • [5.10] Distributive Frameworks
  • [5.11] Reaching Definitions Analysis
  • [5.12] Live Variables Analysis
  • [5.13] 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.14] For a given program analysis problem and analysis lattice: given an operation whose semantics you are familiar with, describe a suitable transfer function
  • [5.15] Given two alternative intraprocedural data flow program analyses that utilise the concepts discussed in class, discuss their relative merits
  • [5.16] Interprocedural Data Flow Analysis via Inlining
  • [5.17] Procedure Summaries
  • [5.18] 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] Store-less and Store-based Pointer Analyses
  • [6.5] Access Paths
  • [6.6] Allocation Site Based Summaries
  • [6.7] Summary Heap Nodes
  • [6.8] The Points-To Relation and Points-To Sets
  • [6.9] Null Pointer Representation Strategies: Unique Null, Many Nulls, Nullness Flags
  • [6.10] Strong and Weak Updates
  • [6.11] Steensgaard's Analysis
  • [6.12] Andersen's Analysis with its Inclusion Edges
  • [6.13] Utilise the results of an Alias Analysis to improve a Data Flow Analysis
• [7] Object Oriented Analysis
  • [7.0] Call Graphs
• [8] Dynamic Analysis
  • [8.0] Dynamic Analysis via Instrumentation, Performance Counters, and Emulation
  • [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] Given a Dynamic Program Analysis, identify potential causes of Perturbation
  • [8.8] Given a Sample of Performance Characteristics, give Limits to Generality of the Characteristics
  • [8.9] Statement Test Coverage Analysis
  • [8.10] Dynamic Taint Analysis, including Taint Sources, Taint Sinks, and Sanitisers
• [9] Declarative Program Analysis
  • [9.0] Datalog Atoms
  • [9.1] Datalog Rules
  • [9.2] Bottom-Up Program Analysis in Datalog

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