Verification methods
Symbolic techniques and tools (such as SAT and SMT solvers and theorem provers) are used in program verification (establishing interesting properties, such as deadlock absence, race conditions, no assertion violation) to overcome the scaling issues of explicit-state approaches. Some of these methods employ Craig interpolants as an abstract way of representation sets of states. Our research focuses on extending this idea to further improve performance of the verification tools in terms of both verification time and consumed memory.
Project team members wanted!
We seek students willing to participate in our projects focused on (but not restricted to) verification of C programs properties. This involves the following areas:
- Modelling: modelling program semantics (Horn clauses, control-flow graph, logical formulas)
- Model checking: algorithms for model checking (bounded model checking, k-induction, IC3/PDR, Craig interpolation)
- Reasoning engine: SAT solver, SMT solver (extending the algorithms, research on new ones)
Analysis of LLVM passes suitable for software verification
LLVM performs plenty of passes transforming the intermediate representation, usually with the goal to simplify the code for a particular purpose. The goal here is to identify those that contribute to the form being most suitable for software verification. An example of such tools is SeaHorn.
Implementation of new software verification algorithms
This includes development and implementation of new algorithms based on state of the art with the aim to win the software verification competition SV-COMP.
Optimization techniques inside SAT/SMT solver
The goal is to develop algorithms compatible with proof generation and interpolation that improve performance of the solver. This also includes techniques already published in scientific works, but not yet implemented in available tools.
Results and Artifacts
- Jančík P., Alt L., Fedyukovich G., Hyvärinen A. E. J., Kofroň J., Sharygina N.: PVAIR: Partial Variable Assignment InterpolatoR, In proceedings of FASE'16, Eindhoven, Netherlands. The final publication is available at link.springer.com, April 2016 (link)
Grants and Projects
- GAČR 14-11384S: Automatic Formal Analysis and Verification of Programs with Complex Unbounded Data and Control Structures
- GAČR 17-12465S: Verification and Bug-Hunting for Advanced Software