Gastvorträge am Mittwoch 27.11.: "Klimawandel und Extremereignisse – neue Erkenntnisse für die Klimafolgenforschung durch die Nutzung von HPC" im Rahmen der Public Climate School von Students for Future Munich.

Teaching at LMU

Teaching in Winter 2019



Training (Praktikum):

Teaching in Past Semesters

Information on courses tought in past semesters can be found on a separate page.

Regularly Offered Courses


For all seminars these rules apply.

Important Links

Bachelor and Master Theses

We offer several topics for theses on Bachelor and Master level in our research projects (German).

Click on marked topics (▶) to show a more detailed description.
Currently unavailable or finished topics are also shown, and may give inspiration for own ideas.

Please contact us if you are interested in one of these topics or if you want to propose your own topic that is related to our research projects. You can also have a look at our collection of past student reports and theses to get an impression of what a thesis at our chair could look like.

Topics on Formal Verification and Testing

Analysis of a real world software project: What can be specified, analyzed?
Literature survey on benchmark sets for software verification and testing and their usage [1, 2]

very broad description. A possible topic could be:

  1. search benchmarks from tools/frameworks/compilers/conferences
  2. transform benchmarks into SV-benchmark compatible format
  3. evaluate SV-COMP tools on new benchmarks, i.e., perform a case study whether the SV-COMP tools are ready for industry benchmarks

Refinement Selection with Adjustable-Block Encoding [1, 2, 3]
Multi-process architecture for BAM-parallel to provide cluster-based software analysis, maybe with central or shared database for reached states
Experimental evaluation of the effect of pre-processing on analyses (e.g., predicate analysis). Pre-processing (e.g., loop mutations, constant propagation, slicing) can happen in the compiler (gcc, cil, LLVM) or the intermediate representation (CFA). Topic may be related to good, bad, ugly interpolants.
Make PCC approach(es) in CPAchecker understand correctness witnesses [1, 2]
Violation and Correctness Witnesses for Conditional Model Checking [1, 2]
Heuristics for Selecting Predicates for Partial Predicate Abstraction [1]
Finding causes for bugs [1, 2]

There are many different ways to find out whether a program is buggy, for example testing or formal verification. Once we know that a program is buggy, i.e., that it shows some faulty behavior, a developer has to manually debug the program to find the cause of the problem and fix it - this is a difficult and long-taking process. The aim of this thesis is to help programmers with debugging by implementing one or more techniques to (1) automatically find potential causes for faulty behavior and (2) presenting the found causes. Two possible techniques to do this are 'error invariants' and 'unsat cores'.

SMT Solving through Computation of Satisfying Multi-Intervals [1]

Studies show that SMT formulas that are created by model checkers [2] or symbolic execution [3] often have a specific structure: The relation between program variables (e.g., "x == y + z") is dependent on multiple constraints over these variables that each only contain a single variable (e.g., "x > 0", "y > 0", "z > 10", "z < 20"). An example for such a formula would be "x == y + z \land x > 0 \land y > 0 \land z > 10 \land z < 20".
The goal of this work is to implement an (incomplete) SMT solving routine that tries to exploit this specific structure through the following process:
1. For each program variable in the formula, compute the interval(s) of possible values for this variable for which the constraints of this variable are satisfied, and
2. Check whether the relations between program variables can be satisfied with the computed intervals.
Work on this [1] that is implemented in the symbolic execution engine Klee [4] has shown great potential, leading to speedups of up to 55x.


Specification languages for deductive verification
Reasoning and interaction patterns of proof assistants - survey, description, experiments, and improvements.
Dependency analysis on our own projects, i.e., which components depeend on others. This is a meta-topic that is located above our projects, not in our projects. Includes: find or write a tool for visualization and dependency graph generation, find the most complex dependencies and cycles. Additionally, try to convince CPAchecker developers to remove or avoid such cycles. [1]
Real-World Requirements for Software Analysis [1, 2, 3, 4, 5, 6]

The National Institute of Standards and Technology (NIST) has published a specification for capabilities that a "Source Code Security Analysis Tool" needs in order to be useful in software security assurance [1][2]. This is accompanied by test suites (subsets of the NIST SARD test suite, e.g. suite 100 and 101 [3]) with programs that have to be checked for certain weaknesses [4][5]. For classification of the weaknesses, CWE-IDs are used.

This now leads to various interesting research questions. A subset of those can be addressed by a project or thesis, depending on the available time and progress.

0. How can the CWE-IDs from the relevant SARD test suites be mapped to the specification that are used in the Competition on Software Verification(SV-COMP)?
Some of the weaknesses, e.g. memory-safety related ones or undefined behavior like overflows, are already checked for in the SV-COMP. For the CWEs that cannot be translated into the specifications currently used in the SV-COMP, a critical discussion should be added on how easy/hard it would be to add these and on how easy/hard it is to check for those properties. The extend of this discussion can be tuned to the scope of the project/thesis.

1. How many of the tests in the test suite can already be checked by the automatic software verifiers that participated in the Competition on Software Verification(SV-COMP)?
One of the claims of the SV-COMP is that it shall reflect real-world problems in software verification. As such, it is of interest to determine whether this is the case by applying the participating tools to tasks that are used in industry, like the SARD test suite.
Provided that the license allows this, the corresponding test cases can be extracted from the relevant SARD test suites and converted into tasks for the SV-COMP. A task in the SV-COMP consists of a program and a specification, so ideally the right specification is automatically determined by parsing the information in the xml manifest of the SARD test suite. After the conversion is complete, an extensive evaluation with the tools that participated in the SV-COMP (and optionally other tools, like the ones listed in [6]) shall be performed.

2. Can CPAchecker be extended (e.g. by new analyses) to find these weaknesses and become a Source Code Security Analyzer like many other tools[6]?
Currently, CPAchecker is not really designed to return multiple findings, as in verification it is usually enough to show one specification violation. For some CWEs there should be support, e.g. memory safety or overflows. Others however (e.g. "CWE-134: Uncontrolled Format String") would require a new analysis to be implemented. For reducing the scope of the thesis/project, one can also just pick a subset of the CWEs and implement the corresponding analysis or analyses. Another way to adapt the scope is to only look at some of the requirements. These are divided into mandatory features SCSA-RM-{1,2,3,4,5,6} and optional features SCSA-RO-{1,2,3}[1].

BTOR2 frontend for CPAchecker [1, 2]
Assigned/Finished Topics
String analysis in CPAchecker [1, 2]
LTL software model checking
Conversion of counterexamples found by software verifiers into an executable test harness that exposes the bug in the program (prototype exists)
Correctness-witness validation using predicate analysis

Verifiers take a program and a specification as input and output whether the program fulfills the specification.If the answer is yes, the verifier can output additional information in form of a correctness witness.This correctness witness can then be used (e.g. by another verifier) to validate that the answer is correct.Our verifier CPAchecker provides many different analyses for verification, but only one of them (called k-Induction) is currently able to validate witnesses.An analysis based on predicate abstraction already exists in CPAchecker that should be able to validate witnesses with minor to moderate programming effort.Once this is working, predicate abstraction could also give insights into which information is missing in the witness.At the end, an evaluation of the new witness validation can be performed on an already existing set of representative programs using our verification cluster.This topic is suitable for a bachelor's thesis, but could also be extended for a master's thesis on request.

Heuristic selection of verification analyses
A JavaScript frontend for CPAchecker
Support for exceptions in the Java analysis of CPAchecker
Towards understandability of verification result: visualization of graphs produced by verifiers
Predicate analysis based on splitting states for CPAchecker [1, 2]
Improve predicate analysis based on domain-type of variables in CPAchecker [1, 2]
Verification Coverage: what parts of a program are covered by a verifier? [1]
Unify analyses (ValueAnalysis, IntervalAnalysis, SignAnalysis) in CPAchecker by using a common data-wrapper for numerical values (integers, bitvectors, floats, ...), optional: support for symbolic values, BDDs, and Octagons [1]
Define and evaluate different refinement approaches for interval domain or BDD domain (widening, splitting, interpolation, path prefixes) [1, 2, 3]
Separation Logic in CPAchecker
Symbolic Memory Graphs in CPAchecker [1, 2]
Backwards analysis for CPAchecker, initially BDD- and predicate-based (both partially implemented somewhere), later symbolic and explicit analysis.
Good, bad, ugly interpolants. Measure interpolants and build heuristics. Topic might be related to refinement selection. [1]
Automatic test case generation based on Symbolic Execution and other Abstract Domains. [1]
Non-termination analysis in CPAchecker
Exchangeable format for assumption automata in conditional model checking [1]

Conditional model checking (CMC) [1] is a technique for the combination of different verification approaches, which works as follows. Initially, the first verifier explores a given verification task. In case the first verifier does not finish its exploration, it finally outputs a condition, a description of the explored state space. The output condition is used by the subsequent verifier to restrict its exploration towards the unexplored state space.
The verifier CPAchecker supports the CMC approach. However, the existing CMC implementation uses a tool-dependent condition format, which is only understood by CPAchecker. Furthermore, CPAchecker is currently only able to use its own condition format to restrict the exploration of the state space.
The goal of this thesis is the development of a tool-independent condition exchange format, to integrate this new exchange format into CPAchecker and to practically evaluate it against the existing tool-dependent format. The idea is to use a tool-independent exchange format for the condition, which is similar to the existing exchange formats for correctness and violation witnesses [2,3]. To achieve this goal, one should first identify how the two formats differ theoretically and practically. On this basis, the tool-independent should be developed and integrated in the existing infrastructure for witness exports. To cross-check the realization of the new format, the efficiency and effectivity of CMC when using the existing or the newly developed format should be compared.

[1] Dirk Beyer, Thomas A. Henzinger, M. Erkan Keremoglu, and Philipp Wendler. 2012. Conditional model checking: a technique to pass information between verifiers. In Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering. ACM, New York, NY, USA, , Article 57 , 11 pages.
[2] Dirk Beyer, Matthias Dangl, Daniel Dietsch, Matthias Heizmann, and Andreas Stahlbauer. 2015. Witness validation and stepwise testification across software verifiers. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering. ACM, New York, NY, USA, 721-733.
[3] Dirk Beyer, Matthias Dangl, Daniel Dietsch, and Matthias Heizmann. 2016. Correctness witnesses: exchanging verification results between verifiers. In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering. ACM, New York, NY, USA, 326-337.

Visualization of computation steps and their results in CPAchecker
Parallel BDDs in Java (cf. Sylvan) [1]
Implementation and Evaluation of k-Shrinkability [1, 2, 3, 4]
Visualization of test and verification coverage information in graph-shape visualizations
An IDE plugin for CPAchecker

At the moment, there are two ways to use CPAchecker: Locally through the command-line, and in the cloud through a web interface. Both options require C developers to leave their IDE everytime they want to run CPAchecker, which disrupts their workflow. The goal of this project is to build an IDE plugin that provides a seamless experience of using CPAchecker (e.g., for Eclipse CDT, VisualStudio Code or mbeddr). We would like the plugin to focus on ease of use and immediate feedback that is easy to comprehend. The plugin should:

  1. allow developers to run CPAchecker on their current project,
  2. provide some options for customization (e.g., whether to run CPAchecker locally or in the cloud), and
  3. provide useful feedback (e.g., if a possibly failing assert-Statement was found by CPAchecker)

Topics on Reliable Benchmarking and Measurements

Assigned/Finished Topics
Modern architecture and tests for HTML tables of BenchExec [1]
Measuring and optimizing energy consumption of verification work

Topics on SMT Solvers and Java SMT

JavaSMT: integrate a new solver (with automated tests and build documentation). Possible candidates: CVC4, Boolector, OpenSMT, STP, Yices,...

JavaSMT is a framework that provides a common API for several SMT solvers. Adding support for an additional solver is straightforward. However, JavaSMT is written in Java, while most solvers are written in C or C++. This means one usually has to write bindings using the Java Native Interface. This topic is suited for a bachelor's thesis

Interpolants build from an arbitrary SMT solver (develop a layer into JavaSMT to get (tree) interpolants without explicit support of the solver e.g. from proofs or unsat cores) [1, 2, 3]
Assigned/Finished Topics
SMT query caching, slicing, and simplification module for Java SMT [1]
BDD support in JavaSMT, e.g. add Regions/RegionManager or even something like Q3B to JavaSMT [1, 2, 3]

JavaSMT is a framework that provides a common API for several SMT solvers. For certain problem types, BDDs can be used as a replacement of SMT solvers, as demonstrated by Q3B. The verifier CPAchecker too contains an abstraction layer (Regions/RegionManager) that enables switching between solver and BDDs, while it uses JavaSMT to be able to switch between different solvers. Ideally, the code can be refactored such that the switching between SMT solver and BDD is moved from CPAchecker to JavaSMT. The goal is NOT to add Q3B to the list of solvers supported by JavaSMT, but rather have our own implementation that takes the Regions/RegionManager of CPAchecker as starting point.

Topics on BDDs, ZDDs and ParallelJBDD

Design a ZDD wrapper wich enables the use of ZDDs in CPAchecker [1]
Implement more decision diagrams in ParallelJBDD (chain reduced BDDs/ZDDs, tagged BDDs, ...) [1]
Implementation of optimization techniques in ParallelJBDD (dynamic variable reordering, complementary edges, ...) [1, 2]


When writing a thesis, follow our thesis guidelines and evaluation criteria and use these technical hints for writing (a paper). The software that we use may also be helpful.