Lund University → Faculty of Engineering → Department of Computer Science

• EDAP15 Program Analysis
• Completion & Grades
• 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.

• [0] Foundations: Compilers and Programming Languages
  • [0.0] Programming in Java (Prerequisite)
  • [0.1] Dynamic Dispatch (Prerequisite)
  • [0.2] Side Effects and "pure" functions (functions without externally observable side effects) (Prerequisite)
  • [0.3] Reading Context-Free Grammars in Backus-Naur Form and understanding the difference between Terminal and Nonterminal symbols
  • [0.4] Abstract Syntax Trees
  • [0.5] Static Program Semantics
  • [0.6] Dynamic Program Semantics
  • [0.7] 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] Foundations: Declarative Program Analysis with JastAdd
  • [2.0] Programming with JastAdd
  • [2.1] Reading Abstract Syntax definitions for JastAdd and understanding the structure of the generated Java objects
  • [2.2] Inter-Type Declarations in JastAdd
  • [2.3] Using JastAdd's "Aspect Weaving" process to add methods and fields to AST classes
  • [2.4] Examining JastAdd ASTs, given a JastAdd grammar
  • [2.5] Reference Attribute Grammars (RAGs) and how to use them for program analysis
  • [2.6] Intrinsic Attributes
  • [2.7] Synthesised Attributes
  • [2.8] Inherited Attributes
  • [2.9] Broadcasting Attributes
  • [2.10] Well-Formedness of JastAdd Grammars
  • [2.11] Well-Definedness of JastAdd Grammars
  • [2.12] Debugging Attribute Evaluation in JastAdd
  • [2.13] Reference Attributes
  • [2.14] Parametrised Attributes
  • [2.15] Collection Attributes
  • [2.16] Non-Terminal Attributes (NTAs)
  • [2.17] Circular Attribute Evaluation

• [3] Properties of Program Analyses
  • [3.0] Static vs. Dynamic Program Analysis
  • [3.1] Automatic vs. Manual Program Analysis
  • [3.2] Soundness and Completeness
  • [3.3] True Positive, False Positive, True Negative, and False Negative
  • [3.4] Precision and Recall
  • [3.5] Flow Sensitivity for Flow Sensitive Analysis (as opposed to Flow Insensitive Analysis)
  • [3.6] May Analysis and Must Analysis
  • [3.7] Control Sensitivity
  • [3.8] Server Analyses and Client Analyses
  • [3.9] Field Sensitivity
  • [3.10] Call-Site Sensitivity
  • [3.11] Interprocedural Analysis and Intraprocedural Analysis
• [4] Type Analysis
  • [4.0] Type System
  • [4.1] Typing Rules
  • [4.2] Type Constructor
  • [4.3] Type Variables and Parametric Polymorphism
  • [4.4] Union-Find Data Structure
  • [4.5] Unification (first-order only)
  • [4.6] Using first-order unification to solve a system of equations
  • [4.7] Monomorphic Type Inference
  • [4.8] Using Monomorphic Type Inference to infer the types and type schemes of a program
  • [4.9] Type Schemes
  • [4.10] Polymorphic Type Inference

• [5] Control Flow Graphs
  • [5.0] Control Flow Graphs
  • [5.1] Given a program and its semantics, compute the Control Flow Graph
  • [5.2] Basic Blocks
• [6] Data Flow Analysis
  • [6.0] Forward Data Flow Analysis and Backward Data Flow Analysis
  • [6.1] Join Functions and Transfer Functions in Data Flow Analysis
  • [6.2] IN-sets and OUT-sets of control-flow nodes in Data Flow Analysis
  • [6.3] Live Variables Analysis
  • [6.4] Reaching Definitions Analysis
  • [6.5] Product Lattices
  • [6.6] The use of Lattices, including their Top Elements and Bottom Elements, in Data Flow Analysis
  • [6.7] Fixpoints / Fixed Points
  • [6.8] Least Fixpoints
  • [6.9] The MFP Algorithm, and using the MFP algorithm to compute a fixpoint
  • [6.10] Monotone Frameworks
  • [6.11] The MOP Algorithm
  • [6.12] Distributive Frameworks
  • [6.13] Given two alternative intraprocedural data flow program analyses that utilise the concepts discussed in class, discuss their relative merits
  • [6.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
  • [6.15] For a given program analysis problem and analysis lattice: given an operation whose semantics you are familiar with, describe a suitable transfer function
  • [6.16] Data Flow on the Interval Abstract Domain
  • [6.17] Widening, including widening on the set of program constants
  • [6.18] Interprocedural Data Flow Analysis via Inlining
  • [6.19] Procedure Summaries
  • [6.20] The IFDS Algorithm

• [7] Pointer Analysis
  • [7.0] Points-To Analysis
  • [7.1] The Aliasing Relation
  • [7.2] Concrete Heap Graphs
  • [7.3] Abstract Heap Graphs
  • [7.4] Utilise the results of an Alias Analysis to improve a Data Flow Analysis
  • [7.5] Store-less and Store-based Pointer Analyses
  • [7.6] Access Paths
  • [7.7] Allocation Site Based Summaries
  • [7.8] Summary Heap Nodes
  • [7.9] The Points-To Relation and Points-To Sets
  • [7.10] Null Pointer Representation Strategies: Unique Null, Many Nulls, Nullness Flags
  • [7.11] Steensgaard's Analysis
  • [7.12] Andersen's Analysis with its Inclusion Edges
  • [7.13] Strong and Weak Updates

• [8] Analysis in the Large
  • [8.0] Call Graphs
  • [8.1] Class Hierarchy Analysis
  • [8.2] Rapid Type Analysis
  • [8.3] How programming language features such as dynamic dispatch or dynamic loading may impair static analysis
  • [8.4] Soundiness
• [9] Dynamic Analysis
  • [9.0] Dynamic Analysis via Instrumentation
  • [9.1] Dynamic Events and their Characteristics
  • [9.2] Samples
  • [9.3] Counting vs. Sampling as measurement strategies
  • [9.4] Read and explain Box Plots
  • [9.5] Perturbation in Dynamic Analysis
  • [9.6] Warm-Up Effects
  • [9.7] Statement Test Coverage Analysis
  • [9.8] Given a Dynamic Program Analysis, identify potential causes of Perturbation
  • [9.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
  • Example: What is an example of a True Positive in program analysis?
• Distinguish it from other concepts
  • Example: What is the difference between a May Analysis and a Must Analysis?
• Explain its relationship to any other concepts (is-part-of, is-alternative-to, is-generalisation-of etc.)
  • Example: What is the connection between static program analysis, type inference, and dataflow analysis?
• Explain the purpose or utility of the concept
  • Example: In type inference, why would I want to use a type varaiable?
• Where applicable: apply the concept to a concrete problem that the concept is suitable for
  • Example: Given some specific set of typing rules that you are shown, what is the type of some specific expression?

Advanced questions will go beyond this scope. These questions may:

• Ask you to critically reflect on specific concepts in a specific application scenario (e.g., "To solve this specific analysis challenge, what program analysis approach would you consider?")
• Ask you to examine interactions between concepts beyond the scope of what we discussed in clss (e.g., "Consider some analysis A. We are using A to address some specific analysis challenge. If we give A access to some specific server analysis B, how might this improve the quality of the analysis results from A?")
• This list is not exhaustive.