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:

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.

Interested? Contact us: Jan Kofroň, Martin Blicha

Recent results and artifacts

P. Parízek, F. Kliber:
Checking Just Pairs of Threads for Efficient and Scalable Incremental Verification of Multithreaded Programs, in Proceedings of JPF Workshop 2022, pp. 27-31, 2023
DOI: 10.1145/3573074.3573082
R. Husák, J. Kofroň, F. Zavoral:
Slicito: Using Computational Notebooks for Program Comprehension, in 2023 IEEE/ACM 31st International Conference on Program Comprehension (ICPC), pp. 64-68, 2023
DOI: 10.1109/ICPC58990.2023.00019
S. Asadi, M. Blicha, A. Hyvärinen, G. Fedyukovich, N. Sharygina:
SMT-based verification of program changes through summary repair, in Formal Methods in System Design, 2023
DOI: 10.1007/s10703-023-00423-0
M. Blicha, K. Britikov, N. Sharygina:
The Golem Horn Solver, in Computer Aided Verification, pp. 209–223, 2023
ISBN: 978-3-031-37703-7, DOI: 10.1007/978-3-031-37703-7_10
P. Parízek, F. Kliber:
Incremental Verification of Multithreaded Programs by Checking Interleavings for Pairs of Threads, Technical report no. D3S-TR-2022-01, Department of Distributed and Dependable Systems, Charles University, pp. 1-15, 2022
L. Alt, M. Blicha, A. Hyvärinen, N. Sharygina:
SolCMC: Solidity Compiler’s Model Checker, in Computer Aided Verification, pp. 325-338, 2022
ISBN: 978-3-031-13185-1, DOI: 10.1007/978-3-031-13185-1_16
M. Blicha, G. Fedyukovich, A. Hyvärinen, N. Sharygina:
Split Transition Power Abstraction for Unbounded Safety, in Proceedings of FMCAD'22, pp. 349-358, 2022
ISBN: 978-3-85448-053-2, DOI: 10.34727/2022/isbn.978-3-85448-053-2_42
M. Blicha, J. Kofroň, W. Tatarko:
Summarization of branching loops, in Proceedings of the 37th ACM/SIGAPP Symposium on Applied Computing, pp. 1808–1816, 2022
ISBN: 978-1-4503-8713-2, DOI: 10.1145/3477314.3507042
M. Blicha, G. Fedyukovich, A. Hyvärinen, N. Sharygina:
Transition Power Abstractions for Deep Counterexample Detection, in Tools and Algorithms for the Construction and Analysis of Systems, pp. 524-542, 2022
ISBN: 978-3-030-99524-9, DOI: 10.1007/978-3-030-99524-9_29
M. Blicha, A. Hyvärinen, J. Kofroň, N. Sharygina:
Using linear algebra in decomposition of Farkas interpolants, in International Journal on Software Tools for Technology Transfer 24(1), pp. 111-125, 2022
DOI: 10.1007/s10009-021-00641-z
R. Otoni, M. Blicha, P. Eugster, A. Hyvärinen, N. Sharygina:
Theory-Specific Proof Steps Witnessing Correctness of SMT Executions, in 58th ACM/IEEE Design Automation Conference (DAC), pp. 541-546, 2021
DOI: 10.1109/DAC18074.2021.9586272

Grants and Projects