Lund University → Faculty of Engineering → Department of Computer Science

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 combining the skills listed here, basic arithmetic, and general computer science knowledge from the undergraduate core classes.

Note that the list will be changing during the course.

Concepts

For each concept (maked in bold-face below) be able to do the following:

0. Foundations

  1. Concepts: scanning/tokenisation, parsing, static semantics, dynamic semantics
  2. Concepts: name analysis, type analysis
  3. Concepts: safety, security
  4. Concepts: static program analysis, dynamic program analysis
  5. Concepts: soundness, precision
  6. Discuss and analyse program analyses while factoring in the soundness - precision - termination tradeoff (in the context of Turing-complete languages and nontrivial properties), and utilise this tradeoff when designing analyses
  7. Read and utilise Backus-Naur form (BNF) for expressing syntax
  8. Give examples of memory errors with and without automatic memory management and identify and explain the following errors in short, non-obfuscated code snippets: null pointer dereference, double free, stale pointer error, uninitialised memory error, out-of-bounds error, pointer type error, and memory leak

1. Formal Foundations

  1. Concepts: graphs, sets, tuples
  2. Concept: monotonicity
  3. Concept: descending chain condition (DCC)
  4. Concept: lattices, flat lattices
  5. Concept: distributivity
  6. Concept: fixpoints, maximal fixpoints
  7. Read formal notation involving the concepts in this category

2. Program Representation

  1. Concept: three-address code (= code without nested expressions)
  2. Concept: control-flow graphs (CFGs)
  3. Concepts: static single assignment form (SSA) and Φ (Phi) functions
  4. Concepts: use-def and def-use chains

3. General Static Analysis

  1. Concept: client analysis
  2. Concept: procedure summaries
  3. Concept: worklist algorithm
  4. Concept: whole-program analysis
  5. Concepts: intraprocedural vs. interprocedural analysis
  6. Concepts: context-sensitive vs. context-insensitive analysis
  7. Concept: inlining for context-sensitive program analysis
  8. Concepts: flow-sensitive vs. flow-insensitive analysis
  9. Concepts: object-sensitive vs. object-insensitive analysis
  10. Give examples of limitations of static program analyses and determine whether they apply to given analysis scenarios. Relevant limitations are: decidability, reflection, dynamic loading, eval() and dynamic code generation

4. Dataflow Analysis

  1. Concepts: forward and backward dataflow analysis
  2. Concepts: transfer functions, merge functions
  3. Concepts: top and bottom elements of the analysis lattice
  4. Concepts: monotone frameworks, distributive frameworks
  5. Concepts: maximum fixpoint (MFP) and meet-over-all-paths (MOP) analyses
  6. Concepts: may and must analyses
  7. Design a lattice for a typical dataflow problem while guaranteeing termination
  8. Concepts: IDE analysis, IFDS analysis
  9. Concepts: procedure summaries, representation relations
  10. Apply MFP and IFDS analysis to a dataflow problem

5. Call Graph Analysis

  1. Concept: procedure call graph analysis
  2. Concept: class hierarchy analysis (CHA)

6. Points-to and Alias Analysis

  1. Concepts: points-to, aliases
  2. Concepts: store-based memory models, store-free memory models
  3. Concepts: concrete heap graph, abstract heap graph, summary node
  4. Concept: summarisation based on allocation sites, variables, k-limiting
  5. Concept: aliasing
  6. Concept: access path
  7. Ability to utilise and extend Andersen's points-to analysis, given a description of the algorithm
  8. Concept: k-Call-site sensitivity in points-to analysis
  9. Concepts: Plain and Full object sensitivity

7. Datalog

  1. Concept: Horn clauses
  2. Concepts: EDB and IDB tables in Datalog
  3. Concept: stratification for giving a `sensible' semantics to negation
  4. Read, write, and understand Datalog programs, possibly involving negation

8. Dynamic Analysis

  1. Concepts: Events and Characteristics
  2. Concepts: Measurements and Samples
  3. Concept: Instrumentation
  4. Concept: Perturbation
  5. Concept: Box Plots
  6. Concept: Performance Counters
  7. Concept: Warm-up effect
  8. Concept: Dynamic Taint Analysis
  9. Concept: Dynamic Binary Instrumentation

9. Type Analysis

  1. Concept: Type Environments
  2. Concept: Monomorphic and Polymorphic Types (also known as monotypes / polytypes)
  3. Concept: Hindley-Milner style Type Inference

10. Operational Semantics

  1. Concept: Natural Semantics
  2. Read and understand formal descriptions of operational semantics using Gentzen-style proof rules, and use them for (at least) informal reasoning about the behaviour of language constructs
  3. Modify or write simple natural semantics rules