Software and Computational Systems Lab

Publications about CPAchecker

1. Dirk Beyer, Po-Chun Chien, Marek Jankola, and Nian-Ze Lee. A Transferability Study of Interpolation-Based Hardware Model Checking for Software Verification. Proc. ACM Softw. Eng., 1(FSE), 2024. ACM. doi:10.1145/3660797 Keyword(s): CPAchecker, Software Model Checking Funding: DFG-CONVEY Publisher's Version PDF Presentation Supplement
   Artifact(s)

   1. doi:10.5281/zenodo.11070973
   Abstract

   Assuring the correctness of computing systems is fundamental to our society and economy, and formal verification is a class of techniques approaching this issue with mathematical rigor. Researchers have invented numerous algorithms to automatically prove whether a computational model, e.g., a software program or a hardware digital circuit, satisfies its specification. In the past two decades, Craig interpolation has been widely used in both hardware and software verification. Despite the similarities in the theoretical foundation between hardware and software verification, previous works usually evaluate interpolation-based algorithms on only one type of verification tasks (e.g., either circuits or programs), so the conclusions of these studies do not necessarily transfer to different types of verification tasks. To investigate the transferability of research conclusions from hardware to software, we adopt two performant approaches of interpolation-based hardware model checking, (1) Interpolation-Sequence-Based Model Checking (Vizel and Grumberg, 2009) and (2) Intertwined Forward-Backward Reachability Analysis Using Interpolants (Vizel, Grumberg, and Shoham, 2013), for software verification. We implement the algorithms proposed by the two publications in the software verifier CPAchecker because it has a software-verification adoption of the first interpolation-based algorithm for hardware model checking from 2003, which the two publications use as a comparison baseline. To assess whether the claims in the two publications transfer to software verification, we conduct an extensive experiment on the largest publicly available suite of safety-verification tasks for the programming language C. Our experimental results show that the important characteristics of the two approaches for hardware model checking are transferable to software verification, and that the cross-disciplinary algorithm adoption is beneficial, as the approaches adopted from hardware model checking were able to tackle tasks unsolvable by existing methods. This work consolidates the knowledge in hardware and software verification and provides open-source implementations to improve the understanding of the compared interpolation-based algorithms.
   BibTeX Entry

   @article{ItpTransfer-PACMSE, author = {Dirk Beyer and Po-Chun Chien and Marek Jankola and Nian-Ze Lee}, title = {A Transferability Study of Interpolation-Based Hardware Model Checking for Software Verification}, journal = {Proc. ACM Softw. Eng.}, volume = {1}, number = {FSE}, year = {2024}, publisher = {ACM}, doi = {10.1145/3660797}, url = {https://www.sosy-lab.org/research/dar-ismc-transferability/}, presentation = {https://www.sosy-lab.org/research/prs/2024-07-18_FSE_A_Transferability_Study_of_Interpolation-Based_HWMC_for_SV_Marek.pdf}, abstract = {Assuring the correctness of computing systems is fundamental to our society and economy, and <em>formal verification</em> is a class of techniques approaching this issue with mathematical rigor. Researchers have invented numerous algorithms to automatically prove whether a computational model, e.g., a software program or a hardware digital circuit, satisfies its specification. In the past two decades, <em>Craig interpolation</em> has been widely used in both hardware and software verification. Despite the similarities in the theoretical foundation between hardware and software verification, previous works usually evaluate interpolation-based algorithms on only one type of verification tasks (e.g., either circuits or programs), so the conclusions of these studies do not necessarily transfer to different types of verification tasks. To investigate the transferability of research conclusions from hardware to software, we adopt two performant approaches of interpolation-based hardware model checking, (1) <em>Interpolation-Sequence-Based Model Checking</em> (<a href="https://doi.org/10.1109/FMCAD.2009.5351148">Vizel and Grumberg, 2009</a>) and (2) <em>Intertwined Forward-Backward Reachability Analysis Using Interpolants</em> (<a href="https://doi.org/10.1007/978-3-642-36742-7_22">Vizel, Grumberg, and Shoham, 2013</a>), for software verification. We implement the algorithms proposed by the two publications in the software verifier CPAchecker because it has a software-verification adoption of the first interpolation-based algorithm for hardware model checking from 2003, which the two publications use as a comparison baseline. To assess whether the claims in the two publications transfer to software verification, we conduct an extensive experiment on the largest publicly available suite of safety-verification tasks for the programming language C. Our experimental results show that the important characteristics of the two approaches for hardware model checking are transferable to software verification, and that the cross-disciplinary algorithm adoption is beneficial, as the approaches adopted from hardware model checking were able to tackle tasks unsolvable by existing methods. This work consolidates the knowledge in hardware and software verification and provides open-source implementations to improve the understanding of the compared interpolation-based algorithms.}, keyword = {CPAchecker,Software Model Checking}, _pdf = {https://www.sosy-lab.org/research/pub/2024-FSE.A_Transferability_Study_of_Interpolation-Based_Hardware_Model_Checking_for_Software_Verification.pdf}, annote = {This article received the "ACM SIGSOFT Distinguished Paper Award" and its reproduction artifact received the "ACM SIGSOFT Best Artifact Award" at <a href="https://2024.esec-fse.org/info/awards">FSE 2024</a>!}, articleno = {90}, artifact = {10.5281/zenodo.11070973}, funding = {DFG-CONVEY}, issue_date = {July 2024}, numpages = {23}, }
   Additional Infos

   This article received the "ACM SIGSOFT Distinguished Paper Award" and its reproduction artifact received the "ACM SIGSOFT Best Artifact Award" at FSE 2024!
2. Dirk Beyer, Matthias Kettl, and Thomas Lemberger. Decomposing Software Verification using Distributed Summary Synthesis. Proc. ACM Softw. Eng., 1(FSE), 2024. ACM. doi:10.1145/3660766 Keyword(s): CPAchecker, Software Model Checking Funding: DFG-CONVEY, DFG-COOP Publisher's Version PDF Supplement
   Artifact(s)

   1. doi:10.5281/zenodo.11095864
   Abstract

   There are many approaches for automated software verification, but they are either imprecise, do not scale well to large systems, or do not sufficiently leverage parallelization. This hinders the integration of software model checking into the development process (continuous integration). We propose an approach to decompose one large verification task into multiple smaller, connected verification tasks, based on blocks in the program control flow. For each block, summaries are computed — based on independent, distributed, continuous refinement by communication between the blocks. The approach iteratively synthesizes preconditions to assume at the block entry (which program states reach this block) and verification conditions to check at the block exit (which program states lead to a specification violation). This separation of concerns leads to an architecture in which all blocks can be analyzed in parallel, as independent verification problems. Whenever new information (as a precondition or verification condition) is available from other blocks, the verification can decide to restart with this new information. We realize our approach as an extension of the configurable-program-analysis algorithm and implement it for the verification of C programs in the widely used verifier CPAchecker. A large experimental evaluation shows the potential of our new approach: The distribution of the workload to several processing units works well and there is a significant reduction of the response time when using multiple processing units. There are even cases in which the new approach beats the highly-tuned, existing single-threaded predicate abstraction.
   BibTeX Entry

   @article{DSS-PACMSE, author = {Dirk Beyer and Matthias Kettl and Thomas Lemberger}, title = {Decomposing Software Verification using Distributed Summary Synthesis}, journal = {Proc. ACM Softw. Eng.}, volume = {1}, number = {FSE}, year = {2024}, publisher = {ACM}, doi = {10.1145/3660766}, url = {https://www.sosy-lab.org/research/distributed-summary-synthesis/}, presentation = {}, abstract = {There are many approaches for automated software verification, but they are either imprecise, do not scale well to large systems, or do not sufficiently leverage parallelization. This hinders the integration of software model checking into the development process (continuous integration). We propose an approach to decompose one large verification task into multiple smaller, connected verification tasks, based on blocks in the program control flow. For each block, summaries are computed — based on independent, distributed, continuous refinement by communication between the blocks. The approach iteratively synthesizes preconditions to assume at the block entry (which program states reach this block) and verification conditions to check at the block exit (which program states lead to a specification violation). This separation of concerns leads to an architecture in which all blocks can be analyzed in parallel, as independent verification problems. Whenever new information (as a precondition or verification condition) is available from other blocks, the verification can decide to restart with this new information. We realize our approach as an extension of the configurable-program-analysis algorithm and implement it for the verification of C programs in the widely used verifier CPAchecker. A large experimental evaluation shows the potential of our new approach: The distribution of the workload to several processing units works well and there is a significant reduction of the response time when using multiple processing units. There are even cases in which the new approach beats the highly-tuned, existing single-threaded predicate abstraction.}, keyword = {CPAchecker,Software Model Checking}, _pdf = {https://www.sosy-lab.org/research/pub/2024-FSE.Decomposing_Software_Verification_using_Distributed_Summary_Synthesis.pdf}, articleno = {90}, artifact = {10.5281/zenodo.11095864}, funding = {DFG-CONVEY,DFG-COOP}, issue_date = {July 2024}, numpages = {23}, }
3. Dirk Beyer, Nian-Ze Lee, and Philipp Wendler. Interpolation and SAT-Based Model Checking Revisited: Adoption to Software Verification. Journal of Automated Reasoning, 2024. Keyword(s): CPAchecker, Software Model Checking PDF Supplement
   BibTeX Entry

   @article{IMC-JAR, author = {Dirk Beyer and Nian-Ze Lee and Philipp Wendler}, title = {Interpolation and SAT-Based Model Checking Revisited: Adoption to Software Verification}, journal = {Journal of Automated Reasoning}, volume = {}, number = {}, pages = {}, year = {2024}, doi = {}, url = {https://www.sosy-lab.org/research/cpa-imc/}, pdf = {https://www.sosy-lab.org/research/pub/2024-JAR.Interpolation_and_SAT-Based_Model_Checking_Revisited_Adoption_to_Software_Verification.pdf}, keyword = {CPAchecker,Software Model Checking}, _sha256 = {}, }
4. Jan Haltermann, Marie-Christine Jakobs, Cedric Richter, and Heike Wehrheim. Parallel program analysis on path ranges. Science of Computer Programming, 238, 2024. doi:10.1016/j.scico.2024.103154 Keyword(s): Ranged Program Analysis, Cooperative Verification, Software Model Checking, CPAchecker Funding: DFG-COOP Publisher's Version
   Artifact(s)

   1. doi:10.5281/zenodo.8398988
   BibTeX Entry

   @article{RangedPA-journal, author = {Jan Haltermann and Marie{-}Christine Jakobs and Cedric Richter and Heike Wehrheim}, title = {Parallel program analysis on path ranges}, journal = {Science of Computer Programming}, volume = {238}, year = {2024}, doi = {10.1016/j.scico.2024.103154}, url = {}, pdf = {}, keyword = {Ranged Program Analysis, Cooperative Verification, Software Model Checking, CPAchecker}, artifact = {10.5281/zenodo.8398988}, funding = {DFG-COOP}, }
5. Marie-Christine Jakobs and Nian-Ze Lee. Summary of the Eighth International Workshop on CPAchecker (CPAchecker 2023). ACM SIGSOFT Software Engineering Notes, 49(2):25-26, 2024. doi:10.1145/3650142.3650150 Keyword(s): CPAchecker Publisher's Version PDF Supplement
   BibTeX Entry

   @article{CPAcheckerWorkshop, author = {Marie{-}Christine Jakobs and Nian{-}Ze Lee}, title = {Summary of the Eighth International Workshop on CPAchecker (CPAchecker 2023)}, journal = {{ACM} {SIGSOFT} Software Engineering Notes}, volume = {49}, number = {2}, pages = {25--26}, year = {2024}, doi = {10.1145/3650142.3650150}, url = {https://cpa.sosy-lab.org/2023/}, pdf = {}, keyword = {CPAchecker}, annote = {}, artifact = {}, funding = {}, }
6. Dirk Beyer, Matthias Dangl, Daniel Dietsch, Matthias Heizmann, Thomas Lemberger, and Michael Tautschnig. Verification Witnesses. ACM Trans. Softw. Eng. Methodol., 31(4):57:1-57:69, 2022. doi:10.1145/3477579 Keyword(s): CPAchecker, Ultimate, Software Model Checking, Witness-Based Validation, Witness-Based Validation (main) Publisher's Version PDF Supplement
   BibTeX Entry

   @article{Witnesses-TOSEM, author = {Dirk Beyer and Matthias Dangl and Daniel Dietsch and Matthias Heizmann and Thomas Lemberger and Michael Tautschnig}, title = {Verification Witnesses}, journal = {ACM Trans. Softw. Eng. Methodol.}, volume = {31}, number = {4}, pages = {57:1-57:69}, year = {2022}, doi = {10.1145/3477579}, url = {https://www.sosy-lab.org/research/verification-witnesses-tosem/}, keyword = {CPAchecker,Ultimate,Software Model Checking,Witness-Based Validation,Witness-Based Validation (main)}, _pdf = {https://www.sosy-lab.org/research/pub/2022-TOSEM.Verification_Witnesses.pdf}, _sha256 = {48acf3f35251df635e829b29fe8f16fd50498f8f99a082b8b9e0aa094a97a432}, }
7. Dirk Beyer and Marie-Christine Jakobs. Cooperative Verifier-Based Testing with CoVeriTest. International Journal on Software Tools for Technology Transfer (STTT), 23(3):313-333, 2021. doi:10.1007/s10009-020-00587-8 Keyword(s): CPAchecker, Software Model Checking, Software Testing Funding: DFG-COOP Publisher's Version PDF
   Abstract

   Testing is a widely applied technique to evaluate software quality, and coverage criteria are often used to assess the adequacy of a generated test suite. However, manually constructing an adequate test suite is typically too expensive, and numerous techniques for automatic test-suite generation were proposed. All of them come with different strengths. To build stronger test-generation tools, different techniques should be combined. In this paper, we study cooperative combinations of verification approaches for test generation, which exchange high-level information. We present CoVeriTest, a hybrid technique for test-suite generation. CoVeriTest iteratively applies different conditional model checkers and allows users to adjust the level of cooperation and to configure individual time limits for each conditional model checker. In our experiments, we systematically study different CoVeriTest cooperation setups, which either use combinations of explicit-state model checking and predicate abstraction, or bounded model checking and symbolic execution. A comparison with state-of-the-art test-generation tools reveals that CoVeriTest achieves higher coverage for many programs (about 15
   BibTeX Entry

   @article{CoVeriTest-STTT, author = {Dirk Beyer and Marie-Christine Jakobs}, title = {Cooperative Verifier-Based Testing with {CoVeriTest}}, journal = {International Journal on Software Tools for Technology Transfer (STTT)}, volume = {23}, number = {3}, pages = {313-333}, year = {2021}, doi = {10.1007/s10009-020-00587-8}, sha256 = {28a5bf6103296455728076e8c12902a53b3d377a296ea2ba18ac111c93330dbd}, url = {}, pdf = {}, presentation = {}, abstract = {Testing is a widely applied technique to evaluate software quality, and coverage criteria are often used to assess the adequacy of a generated test suite. However, manually constructing an adequate test suite is typically too expensive, and numerous techniques for automatic test-suite generation were proposed. All of them come with different strengths. To build stronger test-generation tools, different techniques should be combined. In this paper, we study cooperative combinations of verification approaches for test generation, which exchange high-level information. We present CoVeriTest, a hybrid technique for test-suite generation. CoVeriTest iteratively applies different conditional model checkers and allows users to adjust the level of cooperation and to configure individual time limits for each conditional model checker. In our experiments, we systematically study different CoVeriTest cooperation setups, which either use combinations of explicit-state model checking and predicate abstraction, or bounded model checking and symbolic execution. A comparison with state-of-the-art test-generation tools reveals that CoVeriTest achieves higher coverage for many programs (about 15%).}, keyword = {CPAchecker,Software Model Checking,Software Testing}, funding = {DFG-COOP}, issn = {1433-2787}, }
8. Dirk Beyer, Matthias Dangl, and Philipp Wendler. A Unifying View on SMT-Based Software Verification. Journal of Automated Reasoning, 60(3):299-335, 2018. doi:10.1007/s10817-017-9432-6 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Presentation Supplement
   Abstract

   After many years of successful development of new approaches for software verification, there is a need to consolidate the knowledge about the different abstract domains and algorithms. The goal of this paper is to provide a compact and accessible presentation of four SMT-based verification approaches in order to study them in theory and in practice. We present and compare the following different "schools of thought" of software verification: bounded model checking, k-induction, predicate abstraction, and lazy abstraction with interpolants. Those approaches are well-known and successful in software verification and have in common that they are based on SMT solving as the back-end technology. We reformulate all four approaches in the unifying theoretical framework of configurable program analysis and implement them in the verification framework CPAchecker. Based on this, we can present an evaluation that thoroughly compares the different approaches, where the core differences are expressed in configuration parameters and all other variables are kept constant (such as parser front end, SMT solver, used theory in SMT formulas). We evaluate the effectiveness and the efficiency of the approaches on a large set of verification tasks and discuss the conclusions.
   BibTeX Entry

   @article{AlgorithmComparison-JAR, author = {Dirk Beyer and Matthias Dangl and Philipp Wendler}, title = {A Unifying View on {SMT}-Based Software Verification}, journal = {Journal of Automated Reasoning}, volume = {60}, number = {3}, pages = {299--335}, year = {2018}, doi = {10.1007/s10817-017-9432-6}, sha256 = {5fab3eafacd7fef9c655afc9cd78bbb419ea47361a81633fb551fbf496875d84}, url = {https://www.sosy-lab.org/research/k-ind-compare/}, presentation = {https://www.sosy-lab.org/research/prs/Latest_UnifyingViewSmtBasedSoftwareVerification.pdf}, abstract = {After many years of successful development of new approaches for software verification, there is a need to consolidate the knowledge about the different abstract domains and algorithms. The goal of this paper is to provide a compact and accessible presentation of four SMT-based verification approaches in order to study them in theory and in practice. We present and compare the following different ``schools of thought'' of software verification: bounded model checking, k-induction, predicate abstraction, and lazy abstraction with interpolants. Those approaches are well-known and successful in software verification and have in common that they are based on SMT solving as the back-end technology. We reformulate all four approaches in the unifying theoretical framework of configurable program analysis and implement them in the verification framework CPAchecker. Based on this, we can present an evaluation that thoroughly compares the different approaches, where the core differences are expressed in configuration parameters and all other variables are kept constant (such as parser front end, SMT solver, used theory in SMT formulas). We evaluate the effectiveness and the efficiency of the approaches on a large set of verification tasks and discuss the conclusions.}, keyword = {CPAchecker,Software Model Checking}, _pdf = {https://www.sosy-lab.org/research/pub/2018-JAR.A_Unifying_View_on_SMT-Based_Software_Verification.pdf}, annote = {Publication appeared first online in December 2017<BR/> CPAchecker is available at: <a href="https://cpachecker.sosy-lab.org/"> https://cpachecker.sosy-lab.org/</a>}, issn = {1573-0670}, }
   Additional Infos

   Publication appeared first online in December 2017
   CPAchecker is available at: https://cpachecker.sosy-lab.org/
9. Marie-Christine Jakobs. Spontane Sicherheitsprüfung mittels individualisierter Programmzertifizierung oder Programmrestrukturierung. In S. Hölldobler, editors, Ausgezeichnete Informatikdissertationen 2017, LNI, pages 91-100, 2018. Gesellschaft für Informatik (GI). Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF
   Abstract

   Korrekt funktionierende Software gewinnt immer mehr an Bedeutung. Im Vergleich zu früher ist es heutzutage schwieriger einzuschätzen, wie gut eine Software funktioniert. Dies liegt unter anderem daran, dass Endnutzer häufiger Software unbekannter Hersteller installieren. Endnutzer sollten sich also aktiv von der Softwarekorrektheit überzeugen, zum Beispiel in Form einer spontanen Sicherheitsprüfung. Übliche Verifikationstechniken zur Korrektheitsprüfung kommen für Endnutzer, in der Regel Laien, nicht in Frage. Die zentrale Frage ist daher, wie man einem Laien eine solche spontane Sicherheitsprüfung ermöglicht. Die Antwort der Dissertation sind einfache, automatische und generelle Verfahren zur Sicherheitsprüfung. In der Dissertation werden verschiedene Verfahren vorgeschlagen und sowohl theoretisch als auch praktisch untersucht. Die vorgeschlagenen Verfahren lassen sich in zwei Forschungsrichtungen einsortieren, nämlich in die Gruppe der Proof-Carrying Code Verfahren bzw. in die Gruppe des alternativen Programs from Proofs Verfahren. Einige Verfahren kombinieren beide Forschungsrichtungen.
   BibTeX Entry

   @incollection{DissZusammenfassungJakobs, author = {Marie-Christine Jakobs}, title = {Spontane Sicherheitspr{\"{u}}fung mittels individualisierter Programmzertifizierung oder Programmrestrukturierung}, booktitle = {Ausgezeichnete Informatikdissertationen 2017}, editor = {S. H{\"{o}}lldobler}, volume = {{D-18}}, pages = {91-100}, year = {2018}, series = {{LNI}}, publisher = {Gesellschaft f{\"{u}}r Informatik ({GI})}, isbn = {978-3885799771}, pdf = {https://dl.gi.de/bitstream/handle/20.500.12116/19486/invited_paper_14.pdf?sequence=1&isAllowed=y}, abstract = {Korrekt funktionierende Software gewinnt immer mehr an Bedeutung. Im Vergleich zu fr&uuml;her ist es heutzutage schwieriger einzusch&auml;tzen, wie gut eine Software funktioniert. Dies liegt unter anderem daran, dass Endnutzer h&auml;ufiger Software unbekannter Hersteller installieren. Endnutzer sollten sich also aktiv von der Softwarekorrektheit &uuml;berzeugen, zum Beispiel in Form einer spontanen Sicherheitspr&uuml;fung. &Uuml;bliche Verifikationstechniken zur Korrektheitspr&uuml;fung kommen f&uuml;r Endnutzer, in der Regel Laien, nicht in Frage. Die zentrale Frage ist daher, wie man einem Laien eine solche spontane Sicherheitspr&uuml;fung erm&ouml;glicht. Die Antwort der Dissertation sind einfache, automatische und generelle Verfahren zur Sicherheitspr&uuml;fung. In der Dissertation werden verschiedene Verfahren vorgeschlagen und sowohl theoretisch als auch praktisch untersucht. Die vorgeschlagenen Verfahren lassen sich in zwei Forschungsrichtungen einsortieren, n&auml;mlich in die Gruppe der Proof-Carrying Code Verfahren bzw. in die Gruppe des alternativen Programs from Proofs Verfahren. Einige Verfahren kombinieren beide Forschungsrichtungen.}, keyword = {CPAchecker,Software Model Checking}, annote = {This is a German summary of the dissertation On-The-Fly Safety Checking - Customizing Program Certification and Program Restructuring.}, doifalse = {20.500.12116/19486}, urlpub = {https://dl.gi.de/handle/20.500.12116/19486}, }
   Additional Infos

   This is a German summary of the dissertation On-The-Fly Safety Checking - Customizing Program Certification and Program Restructuring.
10. Philipp Wendler. Beiträge zu praktikabler Prädikatenanalyse. In S. Hölldobler, editors, Ausgezeichnete Informatikdissertationen 2017, LNI, pages 261-270, 2018. Gesellschaft für Informatik (GI). Keyword(s): Benchmarking, CPAchecker, Software Model Checking Publisher's Version PDF Presentation Supplement
    Abstract

    Der Stand der Forschung im Bereich der automatischen Software-Verifikation ist fragmentiert. Verschiedene Verfahren existieren nebeneinander in unterschiedlichen Darstellungen und mit wenig Bezug zueinander, aussagekräftige Vergleiche sind selten. Die Dissertation adressiert dieses Problem. Ein konfigurierbares und flexibles Rahmenwerk zur Vereinheitlichung solcher Verfahren wird entwickelt und mehrere vorhandene Verfahren werden in diesem Rahmenwerk ausgedrückt. Dies bringt neue Erkenntnisse über die Kernideen dieser Verfahren, ermöglicht experimentelle Studien in einer neuartigen Qualität, und erleichtert die Forschung an Kombinationen und Weiterentwicklungen dieser Verfahren. Die Implementierung dieses Rahmenwerks im erfolgreichen Verifizierer CPAchecker wird in der bisher größten derartigen experimentellen Studie (120 verschiedene Konfigurationen, 671280 Ausführungen) evaluiert. Hierzu wird ein Benchmarking-System präsentiert, das mit Hilfe moderner Technologien signifikante qualitative Messfehler existierender Systeme vermeidet.
    BibTeX Entry

    @incollection{DissZusammenfassungWendler, author = {Philipp Wendler}, title = {Beitr{\"{a}}ge zu praktikabler Pr{\"{a}}dikatenanalyse}, booktitle = {Ausgezeichnete Informatikdissertationen 2017}, editor = {S. H{\"{o}}lldobler}, volume = {{D-18}}, pages = {261-270}, year = {2018}, series = {{LNI}}, publisher = {Gesellschaft f{\"{u}}r Informatik ({GI})}, isbn = {978-3885799771}, url = {https://www.sosy-lab.org/research/phd/wendler/}, pdf = {https://dl.gi.de/bitstream/handle/20.500.12116/19476/invited_paper_4.pdf?sequence=1&isAllowed=y}, presentation = {https://www.sosy-lab.org/research/prs/2018-05-08_GiDiss_BeitraegeZuPraktikablerPraedikatenanalyse.pdf}, abstract = {Der Stand der Forschung im Bereich der automatischen Software-Verifikation ist fragmentiert. Verschiedene Verfahren existieren nebeneinander in unterschiedlichen Darstellungen und mit wenig Bezug zueinander, aussagekr&auml;ftige Vergleiche sind selten. Die Dissertation adressiert dieses Problem. Ein konfigurierbares und flexibles Rahmenwerk zur Vereinheitlichung solcher Verfahren wird entwickelt und mehrere vorhandene Verfahren werden in diesem Rahmenwerk ausgedr&uuml;ckt. Dies bringt neue Erkenntnisse &uuml;ber die Kernideen dieser Verfahren, erm&ouml;glicht experimentelle Studien in einer neuartigen Qualit&auml;t, und erleichtert die Forschung an Kombinationen und Weiterentwicklungen dieser Verfahren. Die Implementierung dieses Rahmenwerks im erfolgreichen Verifizierer CPAchecker wird in der bisher gr&ouml;&szlig;ten derartigen experimentellen Studie (120 verschiedene Konfigurationen, 671280 Ausf&uuml;hrungen) evaluiert. Hierzu wird ein Benchmarking-System pr&auml;sentiert, das mit Hilfe moderner Technologien signifikante qualitative Messfehler existierender Systeme vermeidet.}, keyword = {Benchmarking,CPAchecker,Software Model Checking}, annote = {This is a German summary of the dissertation <a href="https://www.sosy-lab.org/research/bib/Year/2017.complete.html#PhilippPredicateAnalysis">Towards Practical Predicate Analysis</a>.}, doifalse = {20.500.12116/19476}, urlpub = {https://dl.gi.de/handle/20.500.12116/19476}, }
    Additional Infos

    This is a German summary of the dissertation Towards Practical Predicate Analysis.
11. Dirk Beyer and Andreas Stahlbauer. BDD-Based Software Verification: Applications to Event-Condition-Action Systems. International Journal on Software Tools for Technology Transfer (STTT), 16(5):507-518, 2014. doi:10.1007/s10009-014-0334-1 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    BibTeX Entry

    @article{STTT14-BDD, author = {Dirk Beyer and Andreas Stahlbauer}, title = {{BDD}-Based Software Verification: Applications to Event-Condition-Action Systems}, journal = {International Journal on Software Tools for Technology Transfer (STTT)}, volume = {16}, number = {5}, pages = {507--518}, year = {2014}, doi = {10.1007/s10009-014-0334-1}, sha256 = {}, url = {https://doi.org/10.1007/s10009-014-0334-1}, pdf = {https://www.sosy-lab.org/research/pub/2014-STTT.BDD-Based_Software_Verification.pdf}, keyword = {CPAchecker,Software Model Checking}, }

12. Dirk Beyer, Thomas Lemberger, and Henrik Wachowitz. CPA-Daemon: Mitigating Tool Restarts for Java-Based Verifiers. In Proceedings of the 22nd International Symposium on Automated Technology for Verification and Analysis (ATVA 2024, Kyoto, Japan, October 21-24), LNCS , 2024. Springer. Keyword(s): CPAchecker, Software Model Checking, Cooperative Verification Funding: DFG-CONVEY PDF Supplement
    Artifact(s)

    1. doi:10.5281/zenodo.11147333
    BibTeX Entry

    @inproceedings{ATVA24, author = {Dirk Beyer and Thomas Lemberger and Henrik Wachowitz}, title = {{CPA-Daemon}: Mitigating Tool Restarts for Java-Based Verifiers}, booktitle = {Proceedings of the 22nd International Symposium on Automated Technology for Verification and Analysis (ATVA~2024, Kyoto, Japan, October 21-24)}, pages = {}, year = {2024}, series = {LNCS~}, publisher = {Springer}, url = {https://gitlab.com/sosy-lab/software/cpa-daemon}, pdf = {https://www.sosy-lab.org/research/pub/2024-ATVA.CPA-Daemon_Mitigating_Tool_Restart_for_Java-Based_Verifiers.pdf}, abstract = {}, keyword = {CPAchecker, Software Model Checking, Cooperative Verification}, artifact = {10.5281/zenodo.11147333}, doinone = {Unpublished: Last checked: 2024-12-10}, funding = {DFG-CONVEY}, }
13. Daniel Baier, Dirk Beyer, Po-Chun Chien, Marie-Christine Jakobs, Marek Jankola, Matthias Kettl, Nian-Ze Lee, Thomas Lemberger, Marian Lingsch-Rosenfeld, Henrik Wachowitz, and Philipp Wendler. Software Verification with CPAchecker 3.0: Tutorial and User Guide. In Proceedings of the 26th International Symposium on Formal Methods (FM 2024, Milan, Italy, September 9-13), LNCS 14934, pages 543-570, 2024. Springer. doi:10.1007/978-3-031-71177-0_30 Keyword(s): CPAchecker, Software Model Checking, Software Testing Funding: DFG-COOP, DFG-CONVEY, DFG-IDEFIX Publisher's Version PDF Presentation Supplement
    Artifact(s)

    1. doi:10.5281/zenodo.13612338
    Abstract

    This tutorial provides an introduction to CPAchecker for users. CPAchecker is a flexible and configurable framework for software verification and testing. The framework provides many abstract domains, such as BDDs, explicit values, intervals, memory graphs, and predicates, and many program-analysis and model-checking algorithms, such as abstract interpretation, bounded model checking, Impact, interpolation-based model checking, k-induction, PDR, predicate abstraction, and symbolic execution. This tutorial presents basic use cases for CPAchecker in formal software verification, focusing on its main verification techniques with their strengths and weaknesses. An extended version also shows further use cases of CPAchecker for test-case generation and witness-based result validation. The envisioned readers are assumed to possess a background in automatic formal verification and program analysis, but prior knowledge of CPAchecker is not required. This tutorial and user guide is based on CPAchecker in version 3.0. This user guide's latest version and other documentation are available at https://cpachecker.sosy-lab.org/doc.php.
    BibTeX Entry

    @inproceedings{FM24a, author = {Daniel Baier and Dirk Beyer and Po-Chun Chien and Marie-Christine Jakobs and Marek Jankola and Matthias Kettl and Nian-Ze Lee and Thomas Lemberger and Marian Lingsch-Rosenfeld and Henrik Wachowitz and Philipp Wendler}, title = {Software Verification with {CPAchecker} 3.0: {Tutorial} and User Guide}, booktitle = {Proceedings of the 26th International Symposium on Formal Methods (FM~2024, Milan, Italy, September 9-13)}, pages = {543-570}, year = {2024}, series = {LNCS~14934}, publisher = {Springer}, doi = {10.1007/978-3-031-71177-0_30}, url = {https://cpachecker.sosy-lab.org}, pdf = {https://www.sosy-lab.org/research/pub/2024-FM.Software_Verification_with_CPAchecker_3.0_Tutorial_and_User_Guide.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2024-09-10_FM24_CPAchecker_Tutorial.pdf}, abstract = {This tutorial provides an introduction to CPAchecker for users. CPAchecker is a flexible and configurable framework for software verification and testing. The framework provides many abstract domains, such as BDDs, explicit values, intervals, memory graphs, and predicates, and many program-analysis and model-checking algorithms, such as abstract interpretation, bounded model checking, Impact, interpolation-based model checking, <i>k</i>-induction, PDR, predicate abstraction, and symbolic execution. This tutorial presents basic use cases for CPAchecker in formal software verification, focusing on its main verification techniques with their strengths and weaknesses. An extended version also shows further use cases of CPAchecker for test-case generation and witness-based result validation. The envisioned readers are assumed to possess a background in automatic formal verification and program analysis, but prior knowledge of CPAchecker is not required. This tutorial and user guide is based on CPAchecker in version 3.0. This user guide's latest version and other documentation are available at <a href="https://cpachecker.sosy-lab.org/doc.php">https://cpachecker.sosy-lab.org/doc.php</a>.}, keyword = {CPAchecker, Software Model Checking, Software Testing}, annote = {An <a href="https://www.sosy-lab.org/research/bib/All/index.html#TechReport24c">extended version</a> of this article is available on <a href="https://doi.org/10.48550/arXiv.2409.02094">arXiv</a>.}, artifact = {10.5281/zenodo.13612338}, funding = {DFG-COOP, DFG-CONVEY, DFG-IDEFIX}, }
    Additional Infos

    An extended version of this article is available on arXiv.
14. Dirk Beyer, Po-Chun Chien, and Nian-Ze Lee. Augmenting Interpolation-Based Model Checking with Auxiliary Invariants. In Proceedings of the 30th International Symposium on Model Checking Software (SPIN 2024, Luxembourg City, Luxembourg, April 10-11), LNCS 14624, pages 227-247, 2024. Springer. doi:10.1007/978-3-031-66149-5_13 Keyword(s): Software Model Checking, Cooperative Verification, CPAchecker Funding: DFG-CONVEY Publisher's Version PDF Presentation Supplement
    Artifact(s)

    1. doi:10.5281/zenodo.10548594
    Abstract

    Software model checking is a challenging problem, and generating relevant invariants is a key factor in proving the safety properties of a program. Program invariants can be obtained by various approaches, including lightweight procedures based on data-flow analysis and intensive techniques using Craig interpolation. Although data-flow analysis runs efficiently, it often produces invariants that are too weak to prove the properties. By contrast, interpolation-based approaches build strong invariants from interpolants, but they might not scale well due to expensive interpolation procedures. Invariants can also be injected into model-checking algorithms to assist the analysis. Invariant injection has been studied for many well-known approaches, including k-induction, predicate abstraction, and symbolic execution. We propose an augmented interpolation-based verification algorithm that injects external invariants into interpolation-based model checking (McMillan, 2003), a hardware model-checking algorithm recently adopted for software verification. The auxiliary invariants help prune unreachable states in Craig interpolants and confine the analysis to the reachable parts of a program. We implemented the proposed technique in the verification framework CPAchecker and evaluated it against mature SMT-based methods in CPAchecker as well as other state-of-the-art software verifiers. We found that injecting invariants reduces the number of interpolation queries needed to prove safety properties and improves the run-time efficiency. Consequently, the proposed invariant-injection approach verified difficult tasks that none of its plain version (i.e., without invariants), the invariant generator, or any compared tools could solve.
    BibTeX Entry

    @inproceedings{SPIN24c, author = {Dirk Beyer and Po-Chun Chien and Nian-Ze Lee}, title = {Augmenting Interpolation-Based Model Checking with Auxiliary Invariants}, booktitle = {Proceedings of the 30th International Symposium on Model Checking Software (SPIN~2024, Luxembourg City, Luxembourg, April 10-11)}, pages = {227-247}, year = {2024}, series = {LNCS~14624}, publisher = {Springer}, doi = {10.1007/978-3-031-66149-5_13}, url = {https://www.sosy-lab.org/research/imc-df/}, pdf = {https://www.sosy-lab.org/research/pub/2024-SPIN.Augmenting_Interpolation-Based_Model_Checking_with_Auxiliary_Invariants.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2024-04-10_SPIN_Augmenting_IMC_with_Auxiliary_Invariants_Po-Chun.pdf}, abstract = {Software model checking is a challenging problem, and generating relevant invariants is a key factor in proving the safety properties of a program. Program invariants can be obtained by various approaches, including lightweight procedures based on data-flow analysis and intensive techniques using Craig interpolation. Although data-flow analysis runs efficiently, it often produces invariants that are too weak to prove the properties. By contrast, interpolation-based approaches build strong invariants from interpolants, but they might not scale well due to expensive interpolation procedures. Invariants can also be injected into model-checking algorithms to assist the analysis. Invariant injection has been studied for many well-known approaches, including <i>k</i>-induction, predicate abstraction, and symbolic execution. We propose an augmented interpolation-based verification algorithm that injects external invariants into interpolation-based model checking (McMillan, 2003), a hardware model-checking algorithm recently adopted for software verification. The auxiliary invariants help prune unreachable states in Craig interpolants and confine the analysis to the reachable parts of a program. We implemented the proposed technique in the verification framework CPAchecker and evaluated it against mature SMT-based methods in CPAchecker as well as other state-of-the-art software verifiers. We found that injecting invariants reduces the number of interpolation queries needed to prove safety properties and improves the run-time efficiency. Consequently, the proposed invariant-injection approach verified difficult tasks that none of its plain version (i.e., without invariants), the invariant generator, or any compared tools could solve.}, keyword = {Software Model Checking, Cooperative Verification, CPAchecker}, annote = {This article received the "Best Paper Award" at SPIN 2024! An <a href="https://www.sosy-lab.org/research/bib/All/index.html#TechReport24a">extended version</a> of this article is available on <a href="https://doi.org/10.48550/arXiv.2403.07821">arXiv</a>.}, artifact = {10.5281/zenodo.10548594}, funding = {DFG-CONVEY}, }
    Additional Infos

    This article received the "Best Paper Award" at SPIN 2024! An extended version of this article is available on arXiv.
15. Dirk Beyer, Matthias Kettl, and Thomas Lemberger. Fault Localization on Verification Witnesses. In Proceedings of the 30th International Symposium on Model Checking Software (SPIN 2024, Luxembourg City, Luxembourg, April 10-11), LNCS 14624, pages 205-224, 2024. Springer. doi:10.1007/978-3-031-66149-5_12 Keyword(s): Software Model Checking, Witness-Based Validation, CPAchecker Funding: DFG-CONVEY, DFG-IDEFIX, DFG-COOP Publisher's Version PDF
    Artifact(s)

    1. doi:10.5281/zenodo.10794627
    Abstract

    When verifiers report an alarm, they export a violation witness (exchangeable counterexample) that helps validate the reachability of that alarm. Conventional wisdom says that this violation witness should be very precise: the ideal witness describes a single error path for the validator to check. But we claim that verifiers overshoot and produce large witnesses with information that makes validation unnecessarily difficult. To check our hypothesis, we reduce violation witnesses to that information that automated fault-localization approaches deem relevant for triggering the reported alarm in the program. We perform a large experimental evaluation on the witnesses produced in the International Competition on Software Verification (SV-COMP 2023). It shows that our reduction shrinks the witnesses considerably and enables the confirmation of verification results that were not confirmable before.
    BibTeX Entry

    @inproceedings{SPIN24b, author = {Dirk Beyer and Matthias Kettl and Thomas Lemberger}, title = {Fault Localization on Verification Witnesses}, booktitle = {Proceedings of the 30th International Symposium on Model Checking Software (SPIN~2024, Luxembourg City, Luxembourg, April 10-11)}, pages = {205-224}, year = {2024}, series = {LNCS~14624}, publisher = {Springer}, doi = {10.1007/978-3-031-66149-5_12}, pdf = {https://sosy-lab.org/research/pub/2024-SPIN.Fault_Localization_on_Verification_Witnesses.pdf}, abstract = {When verifiers report an alarm, they export a violation witness (exchangeable counterexample) that helps validate the reachability of that alarm. Conventional wisdom says that this violation witness should be very precise: the ideal witness describes a single error path for the validator to check. But we claim that verifiers overshoot and produce large witnesses with information that makes validation unnecessarily difficult. To check our hypothesis, we reduce violation witnesses to that information that automated fault-localization approaches deem relevant for triggering the reported alarm in the program. We perform a large experimental evaluation on the witnesses produced in the International Competition on Software Verification (SV-COMP 2023). It shows that our reduction shrinks the witnesses considerably and enables the confirmation of verification results that were not confirmable before.}, keyword = {Software Model Checking, Witness-Based Validation, CPAchecker}, annote = {Nominated for best paper.<br> This work was also presented with a poster at the 46th International Conference on Software Engineering (ICSE 2024, Lisbon, Portugal, April 14-20): <a href="https://sosy-lab.org/research/pst/2024-03-05_ICSE24_Fault_Localization_on_Verification_Witnesses_Poster.pdf">Extended Abstract</a>.}, artifact = {10.5281/zenodo.10794627}, funding = {DFG-CONVEY,DFG-IDEFIX,DFG-COOP}, }
    Additional Infos

    Nominated for best paper.
    This work was also presented with a poster at the 46th International Conference on Software Engineering (ICSE 2024, Lisbon, Portugal, April 14-20): Extended Abstract.
16. Paulína Ayaziová, Dirk Beyer, Marian Lingsch-Rosenfeld, Martin Spiessl, and Jan Strejček. Software Verification Witnesses 2.0. In Proceedings of the 30th International Symposium on Model Checking Software (SPIN 2024, Luxembourg City, Luxembourg, April 10-11), LNCS 14624, pages 184-203, 2024. Springer. doi:10.1007/978-3-031-66149-5_11 Keyword(s): Software Model Checking, Cooperative Verification, Witness-Based Validation, Witness-Based Validation (main), CPAchecker Funding: DFG-CONVEY, DFG-IDEFIX Publisher's Version PDF Presentation Supplement
    Artifact(s)

    1. doi:10.5281/zenodo.10826204
    BibTeX Entry

    @inproceedings{SPIN24a, author = {Paulína Ayaziová and Dirk Beyer and Marian Lingsch-Rosenfeld and Martin Spiessl and Jan Strejček}, title = {Software Verification Witnesses 2.0}, booktitle = {Proceedings of the 30th International Symposium on Model Checking Software (SPIN~2024, Luxembourg City, Luxembourg, April 10-11)}, pages = {184-203}, year = {2024}, series = {LNCS~14624}, publisher = {Springer}, doi = {10.1007/978-3-031-66149-5_11}, url = {https://gitlab.com/sosy-lab/benchmarking/sv-witnesses/}, pdf = {https://www.sosy-lab.org/research/pub/2024-SPIN.Software_Verification_Witnesses_2.0.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2024-04-11_SPIN24_Software-Verification-Witnesses-2.0.pdf}, abstract = {}, keyword = {Software Model Checking, Cooperative Verification, Witness-Based Validation, Witness-Based Validation (main), CPAchecker}, annote = {}, artifact = {10.5281/zenodo.10826204}, funding = {DFG-CONVEY,DFG-IDEFIX}, }
17. Daniel Baier, Dirk Beyer, Po-Chun Chien, Marek Jankola, Matthias Kettl, Nian-Ze Lee, Thomas Lemberger, Marian Lingsch-Rosenfeld, Martin Spiessl, Henrik Wachowitz, and Philipp Wendler. CPAchecker 2.3 with Strategy Selection (Competition Contribution). In Proceedings of the 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2024, Luxembourg, Luxembourg, April 6-11), part 3, LNCS 14572, pages 359-364, 2024. Springer. doi:10.1007/978-3-031-57256-2_21 Keyword(s): Software Model Checking, Witness-Based Validation, CPAchecker Funding: DFG-CONVEY, DFG-IDEFIX Publisher's Version PDF Supplement
    Artifact(s)

    1. doi:10.5281/zenodo.10203297
    Abstract

    CPAchecker is a versatile framework for software verification, rooted in the established concept of configurable program analysis. Compared to the last published system description at SV-COMP 2015, the CPAchecker submission to SV-COMP 2024 incorporates new analyses for reachability safety, memory safety, termination, overflows, and data races. To combine forces of the available analyses in CPAchecker and cover the full spectrum of the diverse program characteristics and specifications in the competition, we use strategy selection to predict a sequential portfolio of analyses that is suitable for a given verification task. The prediction is guided by a set of carefully picked program features. The sequential portfolios are composed based on expert knowledge and consist of bit-precise analyses using k-induction, data-flow analysis, SMT solving, Craig interpolation, lazy abstraction, and block-abstraction memoization. The synergy of various algorithms in CPAchecker enables support for all properties and categories of C programs in SV-COMP 2024 and contributes to its success in many categories. CPAchecker also generates verification witnesses in the new YAML format.
    BibTeX Entry

    @inproceedings{TACAS24c, author = {Daniel Baier and Dirk Beyer and Po-Chun Chien and Marek Jankola and Matthias Kettl and Nian-Ze Lee and Thomas Lemberger and Marian Lingsch-Rosenfeld and Martin Spiessl and Henrik Wachowitz and Philipp Wendler}, title = {{CPAchecker} 2.3 with Strategy Selection (Competition Contribution)}, booktitle = {Proceedings of the 30th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS~2024, Luxembourg, Luxembourg, April 6-11), part~3}, pages = {359-364}, year = {2024}, series = {LNCS~14572}, publisher = {Springer}, doi = {10.1007/978-3-031-57256-2_21}, url = {https://cpachecker.sosy-lab.org/}, abstract = {CPAchecker is a versatile framework for software verification, rooted in the established concept of configurable program analysis. Compared to the last published system description at SV-COMP 2015, the CPAchecker submission to SV-COMP 2024 incorporates new analyses for reachability safety, memory safety, termination, overflows, and data races. To combine forces of the available analyses in CPAchecker and cover the full spectrum of the diverse program characteristics and specifications in the competition, we use strategy selection to predict a sequential portfolio of analyses that is suitable for a given verification task. The prediction is guided by a set of carefully picked program features. The sequential portfolios are composed based on expert knowledge and consist of bit-precise analyses using <i>k</i>-induction, data-flow analysis, SMT solving, Craig interpolation, lazy abstraction, and block-abstraction memoization. The synergy of various algorithms in CPAchecker enables support for all properties and categories of C programs in SV-COMP 2024 and contributes to its success in many categories. CPAchecker also generates verification witnesses in the new YAML format.}, keyword = {Software Model Checking, Witness-Based Validation, CPAchecker}, _pdf = {https://www.sosy-lab.org/research/pub/2024-TACAS.CPAchecker_2.3_with_Strategy_Selection_Competition_Contribution.pdf}, artifact = {10.5281/zenodo.10203297}, funding = {DFG-CONVEY, DFG-IDEFIX}, }
18. Jan Haltermann, Marie-Christine Jakobs, Cedric Richter, and Heike Wehrheim. Ranged Program Analysis: A Parallel Divide-and-Conquer Approach for Software Verification. In Software Engineering 2024, Fachtagung des GI-Fachbereichs Softwaretechnik, Linz, Austria, February 26 - March 1, 2024, LNI P-343, pages 157-158, 2024. GI. doi:10.18420/SW2024_52 Keyword(s): Ranged Program Analysis, Cooperative Verification, Software Model Checking, CPAchecker Publisher's Version
    BibTeX Entry

    @inproceedings{JakobsSE2024, author = {Jan Haltermann and Marie{-}Christine Jakobs and Cedric Richter and Heike Wehrheim}, title = {Ranged Program Analysis: A Parallel Divide-and-Conquer Approach for Software Verification}, booktitle = {Software Engineering 2024, Fachtagung des GI-Fachbereichs Softwaretechnik, Linz, Austria, February 26 - March 1, 2024}, pages = {157-158}, year = {2024}, series = {{LNI}~{P-343}}, publisher = {GI}, doi = {10.18420/SW2024_52}, pdf = {}, keyword = {Ranged Program Analysis, Cooperative Verification, Software Model Checking, CPAchecker}, annote = {}, artifact = {}, funding = {}, }
19. Dirk Beyer, Po-Chun Chien, and Nian-Ze Lee. CPA-DF: A Tool for Configurable Interval Analysis to Boost Program Verification. In Proc. ASE, pages 2050-2053, 2023. IEEE. doi:10.1109/ASE56229.2023.00213 Keyword(s): Software Model Checking, Cooperative Verification, CPAchecker Funding: DFG-CONVEY Publisher's Version PDF Presentation Video Supplement
    Artifact(s)

    1. doi:10.5281/zenodo.8245821
    Abstract

    Software verification is challenging, and auxiliary program invariants are used to improve the effectiveness of verification approaches. For instance, the k-induction implementation in CPAchecker, an award-winning framework for program analysis, uses invariants produced by a configurable data-flow analysis to strengthen induction hypotheses. This invariant generator, CPA-DF, uses arithmetic expressions over intervals as its abstract domain and is able to prove some safe verification tasks alone. After extensively evaluating CPA-DF on SV-Benchmarks, the largest publicly available suite of C safety-verification tasks, we discover that its potential as a stand-alone analysis or a sub-analysis in a parallel portfolio for combined verification approaches has been significantly underestimated: (1) As a stand-alone analysis, CPA-DF finds almost as many proofs as the plain k-induction implementation without auxiliary invariants. (2) As a sub-analysis running in parallel to the plain k-induction implementation, CPA-DF boosts the portfolio verifier to solve a comparable amount of tasks as the heavily-optimized k-induction implementation with invariant injection. Our detailed analysis reveals that dynamic precision adjustment is crucial to the efficiency and effectiveness of CPA-DF. To generalize our results beyond CPAchecker, we use CoVeriTeam, a platform for cooperative verification, to compose three portfolio verifiers that execute CPA-DF and three other software verifiers in parallel, respectively. Surprisingly, running CPA-DF merely in parallel to these state-of-the-art tools further boosts the number of correct results up to more than 20%.
    Demonstration video: https://youtu.be/l7UG-vhTL_4
    BibTeX Entry

    @inproceedings{ASE23a, author = {Dirk Beyer and Po-Chun Chien and Nian-Ze Lee}, title = {{CPA-DF}: {A} Tool for Configurable Interval Analysis to Boost Program Verification}, booktitle = {Proc.\ ASE}, pages = {2050-2053}, year = {2023}, series = {}, publisher = {IEEE}, doi = {10.1109/ASE56229.2023.00213}, url = {https://www.sosy-lab.org/research/cpa-df/}, pdf = {https://www.sosy-lab.org/research/pub/2023-ASE.CPA-DF_A_Tool_for_Configurable_Interval_Analysis_to_Boost_Program_Verification.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2023-09-13_ASE_CPA-DF_Po-Chun.pdf}, abstract = {Software verification is challenging, and auxiliary program invariants are used to improve the effectiveness of verification approaches. For instance, the <i>k</i>-induction implementation in <a href="https://cpachecker.sosy-lab.org/">CPAchecker</a>, an award-winning framework for program analysis, uses invariants produced by a configurable data-flow analysis to strengthen induction hypotheses. This invariant generator, CPA-DF, uses arithmetic expressions over intervals as its abstract domain and is able to prove some safe verification tasks alone. After extensively evaluating CPA-DF on <a href="https://gitlab.com/sosy-lab/benchmarking/sv-benchmarks">SV-Benchmarks</a>, the largest publicly available suite of C safety-verification tasks, we discover that its potential as a stand-alone analysis or a sub-analysis in a parallel portfolio for combined verification approaches has been significantly underestimated: (1) As a stand-alone analysis, CPA-DF finds almost as many proofs as the plain <i>k</i>-induction implementation without auxiliary invariants. (2) As a sub-analysis running in parallel to the plain <i>k</i>-induction implementation, CPA-DF boosts the portfolio verifier to solve a comparable amount of tasks as the heavily-optimized <i>k</i>-induction implementation with invariant injection. Our detailed analysis reveals that dynamic precision adjustment is crucial to the efficiency and effectiveness of CPA-DF. To generalize our results beyond CPAchecker, we use <a href="https://gitlab.com/sosy-lab/software/coveriteam">CoVeriTeam</a>, a platform for cooperative verification, to compose three portfolio verifiers that execute CPA-DF and three other software verifiers in parallel, respectively. Surprisingly, running CPA-DF merely in parallel to these state-of-the-art tools further boosts the number of correct results up to more than 20&percnt;. <br> Demonstration video: <a href="https://youtu.be/l7UG-vhTL_4">https://youtu.be/l7UG-vhTL_4</a>}, keyword = {Software Model Checking, Cooperative Verification, CPAchecker}, artifact = {10.5281/zenodo.8245821}, funding = {DFG-CONVEY}, video = {https://youtu.be/l7UG-vhTL_4}, }
20. Dirk Beyer, Jan Haltermann, Thomas Lemberger, and Heike Wehrheim. Component-based CEGAR - Building Software Verifiers from Off-the-Shelf Components. In G. Engels, R. Hebig, and M. Tichy, editors, Software Engineering 2023, Fachtagung des GI-Fachbereichs Softwaretechnik, 20.-24. Februar 2023, Paderborn, LNI P-332, pages 37-38, 2023. GI. Keyword(s): CPAchecker, Software Model Checking, Cooperative Verification Publisher's Version PDF
    BibTeX Entry

    @inproceedings{SE23, author = {Dirk Beyer and Jan Haltermann and Thomas Lemberger and Heike Wehrheim}, title = {Component-based {CEGAR} - Building Software Verifiers from Off-the-Shelf Components}, booktitle = {Software Engineering 2023, Fachtagung des GI-Fachbereichs Softwaretechnik, 20.-24. Februar 2023, Paderborn}, editor = {G.~Engels and R.~Hebig and M.~Tichy}, pages = {37--38}, year = {2023}, series = {{LNI}~P-332}, publisher = {{GI}}, sha256 = {}, pdf = {https://sosy-lab.org/research/pub/2023-SE.Component-based_CEGAR_Building_Software_Verifiers_from_Off-the-Shelf_Components.pdf}, abstract = {}, keyword = {CPAchecker,Software Model Checking,Cooperative Verification}, annote = {This is a summary of a <a href="https://www.sosy-lab.org/research/bib/Year/2022.html#ICSE22">full article on this topic</a> that appeared in Proc. ICSE 2022.}, doinone = {DOI not available}, isbnnote = {978-3-88579-726-5}, urlpub = {https://dspace.gi.de/handle/20.500.12116/40128}, }
    Additional Infos

    This is a summary of a full article on this topic that appeared in Proc. ICSE 2022.
21. Marie-Christine Jakobs and Tim Pollandt. diffDP: Using Data Dependencies and Properties in Difference Verification with Conditions. In Proc. iFM, LNCS 14300, pages 40-61, 2023. Springer. doi:10.1007/978-3-031-47705-8_3 Keyword(s): Incremental Verification, Regression Verification, Software Model Checking, CPAchecker Funding: Software-Factory 4.0, DFG-ReVeriX Publisher's Version PDF
    Artifact(s)

    1. doi:10.5281/zenodo.8272913
    BibTeX Entry

    @inproceedings{diffDP, author = {Marie{-}Christine Jakobs and Tim Pollandt}, title = {diffDP: Using Data Dependencies and Properties in Difference Verification with Conditions}, booktitle = {Proc.\ iFM}, pages = {40-61}, year = {2023}, series = {LNCS~14300}, publisher = {Springer}, doi = {10.1007/978-3-031-47705-8_3}, url = {}, pdf = {}, keyword = {Incremental Verification, Regression Verification, Software Model Checking, CPAchecker}, annote = {}, artifact = {10.5281/zenodo.8272913}, funding = {Software-Factory 4.0, DFG-ReVeriX}, }
22. Jan Haltermann, Marie-Christine Jakobs, Cedric Richter, and Heike Wehrheim. Ranged Program Analysis via Instrumentation. In Proc. SEFM, LNCS 14323, pages 145-164, 2023. Springer. doi:10.1007/978-3-031-47115-5_9 Keyword(s): Software Model Checking, CPAchecker, Ranged Program Analysis, Program Instrumentation Publisher's Version PDF
    Artifact(s)

    1. doi:10.5281/zenodo.8065229
    BibTeX Entry

    @inproceedings{RangedPAwithInstrumentation, author = {Jan Haltermann and Marie{-}Christine Jakobs and Cedric Richter and Heike Wehrheim}, title = {Ranged Program Analysis via Instrumentation}, booktitle = {Proc.\ SEFM}, pages = {145-164}, year = {2023}, series = {LNCS~14323}, publisher = {Springer}, doi = {10.1007/978-3-031-47115-5_9}, url = {}, pdf = {}, keyword = {Software Model Checking, CPAchecker, Ranged Program Analysis, Program Instrumentation}, annote = {}, artifact = {10.5281/zenodo.8065229}, funding = {}, }
23. Jan Haltermann, Marie-Christine Jakobs, Cedric Richter, and Heike Wehrheim. Parallel Program Analysis via Range Splitting. In Proc. FASE, LNCS 13991, pages 195-219, 2023. Springer. doi:10.1007/978-3-031-30826-0_11 Keyword(s): Ranged Program Analysis, Cooperative Verification, Software Model Checking, CPAchecker Funding: DFG-COOP Publisher's Version PDF
    BibTeX Entry

    @inproceedings{RangedPA-CPA, author = {Jan Haltermann and Marie{-}Christine Jakobs and Cedric Richter and Heike Wehrheim}, title = {Parallel Program Analysis via Range Splitting}, booktitle = {Proc.\ {FASE}}, pages = {195--219}, year = {2023}, series = {LNCS~13991}, publisher = {Springer}, doi = {10.1007/978-3-031-30826-0_11}, url = {}, pdf = {}, keyword = {Ranged Program Analysis, Cooperative Verification, Software Model Checking, CPAchecker}, annote = {}, artifact = {}, funding = {DFG-COOP}, }
24. Dirk Beyer, Martin Spiessl, and Sven Umbricht. Cooperation between Automatic and Interactive Software Verifiers. In Bernd-Holger Schlingloff and Ming Chai, editors, Proceedings of the 20th International Conference on Software Engineering and Formal Methods, (SEFM 2022, Berlin, Germany, September 26-30, LNCS 13550, pages 111–128, 2022. Springer. doi:10.1007/978-3-031-17108-6_7 Keyword(s): Software Model Checking, CPAchecker Funding: DFG-CONVEY Publisher's Version PDF
    BibTeX Entry

    @inproceedings{SEFM22b, author = {Dirk Beyer and Martin Spiessl and Sven Umbricht}, title = {Cooperation between Automatic and Interactive Software Verifiers}, booktitle = {Proceedings of the 20th International Conference on Software Engineering and Formal Methods, (SEFM~2022, Berlin, Germany, September 26-30}, editor = {Bernd-Holger Schlingloff and Ming Chai}, pages = {111–128}, year = {2022}, series = {LNCS~13550}, publisher = {Springer}, doi = {10.1007/978-3-031-17108-6_7}, sha256 = {a310ff0ac97f37ee817c6f05a4cc9a635cbacd09ad301b483095f133040e8e48}, url = {}, abstract = {}, keyword = {Software Model Checking, CPAchecker}, _pdf = {https://www.sosy-lab.org/research/pub/2022-SEFM.Cooperation_between_Automatic_and_Interactive_Software_Verifiers.pdf}, funding = {DFG-CONVEY}, }
25. Dirk Beyer, Marian Lingsch Rosenfeld, and Martin Spiessl. A Unifying Approach for Control-Flow-Based Loop Abstraction. In Bernd-Holger Schlingloff and Ming Chai, editors, Proceedings of the 20th International Conference on Software Engineering and Formal Methods, (SEFM 2022, Berlin, Germany, September 26-30, LNCS 13550, pages 3-19, 2022. Springer. doi:10.1007/978-3-031-17108-6_1 Keyword(s): Software Model Checking, CPAchecker Funding: DFG-CONVEY Publisher's Version PDF
    BibTeX Entry

    @inproceedings{SEFM22a, author = {Dirk Beyer and Marian Lingsch Rosenfeld and Martin Spiessl}, title = {A Unifying Approach for Control-Flow-Based Loop Abstraction}, booktitle = {Proceedings of the 20th International Conference on Software Engineering and Formal Methods, (SEFM~2022, Berlin, Germany, September 26-30}, editor = {Bernd-Holger Schlingloff and Ming Chai}, pages = {3-19}, year = {2022}, series = {LNCS~13550}, publisher = {Springer}, doi = {10.1007/978-3-031-17108-6_1}, sha256 = {047a8a9062e143741623320cf80ec963ce5f7200a5a75d263fa6615c12f2199e}, url = {}, abstract = {}, keyword = {Software Model Checking, CPAchecker}, _pdf = {https://www.sosy-lab.org/research/pub/2022-SEFM.A_Unifying_Approach_for_Control-Flow-Based_Loop_Abstraction.pdf}, funding = {DFG-CONVEY}, }
26. Dirk Beyer, Jan Haltermann, Thomas Lemberger, and Heike Wehrheim. Decomposing Software Verification into Off-the-Shelf Components: An Application to CEGAR. In Proceedings of the 44th International Conference on Software Engineering (ICSE 2022, Pittsburgh, PA, USA, May 8-20 (Virtual), May 22-27 (In-Person)), pages 536-548, 2022. ACM. doi:10.1145/3510003.3510064 Keyword(s): CPAchecker, Software Model Checking, Interfaces for Component-Based Design Funding: DFG-COOP Publisher's Version PDF Supplement
    Artifact(s)

    1. doi:10.5281/zenodo.5301636
    Abstract

    Techniques for software verification are typically realized as cohesive units of software with tightly coupled components. This makes it difficult to re-use components, and the potential for workload distribution is limited. Innovations in software verification might find their way into practice faster if provided in smaller, more specialized components. In this paper, we propose to strictly decompose software verification: the verification task is split into independent subtasks, implemented by only loosely coupled components communicating via clearly defined interfaces. We apply this decomposition concept to one of the most frequently employed techniques in software verification: counterexample-guided abstraction refinement (CEGAR). CEGAR is a technique to iteratively compute an abstract model of the system. We develop a decomposition of CEGAR into independent components with clearly defined interfaces that are based on existing, standardized exchange formats. Its realization component-based CEGAR (C-CEGAR) concerns the three core tasks of CEGAR: abstract-model exploration, feasibility check, and precision refinement. We experimentally show that - despite the necessity of exchanging complex data via interfaces - the efficiency thereby only reduces by a small constant factor while the precision in solving verification tasks even increases. We furthermore illustrate the advantages of C-CEGAR by experimenting with different implementations of components, thereby further increasing the overall effectiveness and testing that substitution of components works well.
    BibTeX Entry

    @inproceedings{ICSE22, author = {Dirk Beyer and Jan Haltermann and Thomas Lemberger and Heike Wehrheim}, title = {Decomposing Software Verification into Off-the-Shelf Components: An Application to {CEGAR}}, booktitle = {Proceedings of the 44th International Conference on Software Engineering (ICSE~2022, Pittsburgh, PA, USA, May 8-20 (Virtual), May 22-27 (In-Person))}, pages = {536-548}, year = {2022}, publisher = {ACM}, doi = {10.1145/3510003.3510064}, url = {https://www.sosy-lab.org/research/component-based-cegar/}, abstract = {Techniques for software verification are typically realized as cohesive units of software with tightly coupled components. This makes it difficult to re-use components, and the potential for workload distribution is limited. Innovations in software verification might find their way into practice faster if provided in smaller, more specialized components. In this paper, we propose to strictly decompose software verification: the verification task is split into independent subtasks, implemented by only loosely coupled components communicating via clearly defined interfaces. We apply this decomposition concept to one of the most frequently employed techniques in software verification: counterexample-guided abstraction refinement (CEGAR). CEGAR is a technique to iteratively compute an abstract model of the system. We develop a decomposition of CEGAR into independent components with clearly defined interfaces that are based on existing, standardized exchange formats. Its realization component-based CEGAR (C-CEGAR) concerns the three core tasks of CEGAR: abstract-model exploration, feasibility check, and precision refinement. We experimentally show that --- despite the necessity of exchanging complex data via interfaces --- the efficiency thereby only reduces by a small constant factor while the precision in solving verification tasks even increases. We furthermore illustrate the advantages of C-CEGAR by experimenting with different implementations of components, thereby further increasing the overall effectiveness and testing that substitution of components works well.}, keyword = {CPAchecker,Software Model Checking,Interfaces for Component-Based Design}, _pdf = {https://www.sosy-lab.org/research/pub/2022-ICSE.Decomposing_Software_Verification_into_Off-the-Shelf-Components.pdf}, _sha256 = {be1c5d744475af00f5a0cddd51d92353296d1d8e5ba60f5439ba5b98217e0e03}, artifact = {10.5281/zenodo.5301636}, funding = {DFG-COOP}, }
27. Dirk Beyer and Karlheinz Friedberger. Domain-Independent Interprocedural Program Analysis using Block-Abstraction Memoization. In P. Devanbu, M. Cohen, and T. Zimmermann, editors, Proceedings of the 28th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2020, Virtual Event, USA, November 8-13), pages 50-62, 2020. ACM. doi:10.1145/3368089.3409718 Keyword(s): CPAchecker, Software Model Checking Funding: DFG-CONVEY Publisher's Version PDF Supplement
    Artifact(s)

    1. doi:10.5281/zenodo.4024268
    BibTeX Entry

    @inproceedings{FSE20, author = {Dirk Beyer and Karlheinz Friedberger}, title = {Domain-Independent Interprocedural Program Analysis using Block-Abstraction Memoization}, booktitle = {Proceedings of the 28th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE~2020, Virtual Event, USA, November 8-13)}, editor = {P.~Devanbu and M.~Cohen and T.~Zimmermann}, pages = {50-62}, year = {2020}, publisher = {ACM}, doi = {10.1145/3368089.3409718}, url = {https://cpachecker.sosy-lab.org}, keyword = {CPAchecker,Software Model Checking}, _sha256 = {36dc2a423425ee8bec03f0f4073e04f9121d299cc475e27190828e8276e00cb8}, artifact = {10.5281/zenodo.4024268}, funding = {DFG-CONVEY}, fundingid = {378803395}, }
28. Dirk Beyer and Karlheinz Friedberger. Violation Witnesses and Result Validation for Multi-Threaded Programs. In T. Margaria and B. Steffen, editors, Proceedings of the 9th International Symposium on Leveraging Applications of Formal Methods, Verification, and Validation (ISoLA 2020, Rhodos, Greece, October 26-30), part 1, LNCS 12476, pages 449-470, 2020. Springer. doi:10.1007/978-3-030-61362-4_26 Keyword(s): CPAchecker, Software Model Checking, Witness-Based Validation, Witness-Based Validation (main) Funding: DFG-CONVEY Publisher's Version PDF Presentation Supplement
    BibTeX Entry

    @inproceedings{ISoLA20c, author = {Dirk Beyer and Karlheinz Friedberger}, title = {Violation Witnesses and Result Validation for Multi-Threaded Programs}, booktitle = {Proceedings of the 9th International Symposium on Leveraging Applications of Formal Methods, Verification, and Validation (ISoLA~2020, Rhodos, Greece, October 26-30), part~1}, editor = {T.~Margaria and B.~Steffen}, pages = {449-470}, year = {2020}, series = {LNCS~12476}, publisher = {Springer}, doi = {10.1007/978-3-030-61362-4_26}, sha256 = {65fc5325c4e77a80d8e47f9c0e7f0ac02379bfa15dcd9fb54d6587185b8efd77}, url = {https://www.sosy-lab.org/research/witnesses-concurrency/}, presentation = {https://www.sosy-lab.org/research/prs/2021-10-25_ISOLA21_ValidationMultiThreaded_Dirk.pdf}, abstract = {}, keyword = {CPAchecker,Software Model Checking,Witness-Based Validation,Witness-Based Validation (main)}, funding = {DFG-CONVEY}, }
29. Dirk Beyer and Sudeep Kanav. An Interface Theory for Program Verification. In T. Margaria and B. Steffen, editors, Proceedings of the 9th International Symposium on Leveraging Applications of Formal Methods, Verification, and Validation (ISoLA 2020, Rhodos, Greece, October 26-30), part 1, LNCS 12476, pages 168-186, 2020. Springer. doi:10.1007/978-3-030-61362-4_9 Keyword(s): CPAchecker, Software Model Checking, Interfaces for Component-Based Design Funding: DFG-CONVEY Publisher's Version PDF Presentation
    BibTeX Entry

    @inproceedings{ISoLA20b, author = {Dirk Beyer and Sudeep Kanav}, title = {An Interface Theory for Program Verification}, booktitle = {Proceedings of the 9th International Symposium on Leveraging Applications of Formal Methods, Verification, and Validation (ISoLA~2020, Rhodos, Greece, October 26-30), part~1}, editor = {T.~Margaria and B.~Steffen}, pages = {168-186}, year = {2020}, series = {LNCS~12476}, publisher = {Springer}, doi = {10.1007/978-3-030-61362-4_9}, sha256 = {f15159da0e648a25e57c769639c989e68cd3407bfad10db5ee1dc25e1d2fd672}, url = {}, presentation = {https://www.sosy-lab.org/research/prs/2021-10-29_ISOLA21_VerificationInterfaces_Dirk.pdf}, abstract = {}, keyword = {CPAchecker,Software Model Checking,Interfaces for Component-Based Design}, funding = {DFG-CONVEY}, }
30. Dirk Beyer, Marie-Christine Jakobs, and Thomas Lemberger. Difference Verification with Conditions. In F. d. Boer and A. Cerone, editors, Proceedings of the 18th International Conference on Software Engineering and Formal Methods (SEFM 2020, Virtual, Netherlands, September 14-18), LNCS 12310, pages 133-154, 2020. Springer. doi:10.1007/978-3-030-58768-0_8 Keyword(s): CPAchecker, Software Model Checking Funding: DFG-COOP, DFG-CONVEY Publisher's Version PDF Presentation Video Supplement
    Abstract

    Modern software-verification tools need to support development processes that involve frequent changes. Existing approaches for incremental verification hard-code specific verification techniques. Some of the approaches must be tightly intertwined with the development process. To solve this open problem, we present the concept of difference verification with conditions. Difference verification with conditions is independent from any specific verification technique and can be integrated in software projects at any time. It first applies a change analysis that detects which parts of a software were changed between revisions and encodes that information in a condition. Based on this condition, an off-the-shelf verifier is used to verify only those parts of the software that are influenced by the changes. As a proof of concept, we propose a simple, syntax-based change analysis and use difference verification with conditions with three off-the-shelf verifiers. An extensive evaluation shows the competitiveness of difference verification with conditions.
    BibTeX Entry

    @inproceedings{SEFM20b, author = {Dirk Beyer and Marie-Christine Jakobs and Thomas Lemberger}, title = {Difference Verification with Conditions}, booktitle = {Proceedings of the 18th International Conference on Software Engineering and Formal Methods (SEFM~2020, Virtual, Netherlands, September 14-18)}, editor = {F.~d.~Boer and A.~Cerone}, pages = {133--154}, year = {2020}, series = {LNCS~12310}, publisher = {Springer}, doi = {10.1007/978-3-030-58768-0_8}, sha256 = {8e5219da9a998b26f59013c809fbb1db6f92e3f08125fa1bfaacafcfafafef7f}, url = {https://www.sosy-lab.org/research/difference/}, presentation = {https://www.sosy-lab.org/research/prs/2020-09-17_SEFM20_DifferenceVerificationWithConditions_Thomas.pdf}, abstract = {Modern software-verification tools need to support development processes that involve frequent changes. Existing approaches for incremental verification hard-code specific verification techniques. Some of the approaches must be tightly intertwined with the development process. To solve this open problem, we present the concept of difference verification with conditions. Difference verification with conditions is independent from any specific verification technique and can be integrated in software projects at any time. It first applies a change analysis that detects which parts of a software were changed between revisions and encodes that information in a condition. Based on this condition, an off-the-shelf verifier is used to verify only those parts of the software that are influenced by the changes. As a proof of concept, we propose a simple, syntax-based change analysis and use difference verification with conditions with three off-the-shelf verifiers. An extensive evaluation shows the competitiveness of difference verification with conditions.}, keyword = {CPAchecker,Software Model Checking}, funding = {DFG-COOP,DFG-CONVEY}, isbnnote = {}, video = {https://youtu.be/dG02602c9oo}, }
31. Dirk Beyer and Marie-Christine Jakobs. FRed: Conditional Model Checking via Reducers and Folders. In F. d. Boer and A. Cerone, editors, Proceedings of the 18th International Conference on Software Engineering and Formal Methods (SEFM 2020, Virtual, Netherlands, September 14-18), LNCS 12310, pages 113-132, 2020. Springer. doi:10.1007/978-3-030-58768-0_7 Keyword(s): CPAchecker, Software Model Checking Funding: DFG-COOP Publisher's Version PDF Supplement
    BibTeX Entry

    @inproceedings{SEFM20a, author = {Dirk Beyer and Marie-Christine Jakobs}, title = {{{\sc FRed}}: {C}onditional Model Checking via Reducers and Folders}, booktitle = {Proceedings of the 18th International Conference on Software Engineering and Formal Methods (SEFM~2020, Virtual, Netherlands, September 14-18)}, editor = {F.~d.~Boer and A.~Cerone}, pages = {113--132}, year = {2020}, series = {LNCS~12310}, publisher = {Springer}, doi = {10.1007/978-3-030-58768-0_7}, sha256 = {0ce35cbde24d7a9de0513b89f23a81147bf4f8d5880effd57742c7f195e0eeec}, url = {https://www.sosy-lab.org/research/fred/}, abstract = {}, keyword = {CPAchecker,Software Model Checking}, funding = {DFG-COOP}, isbnnote = {}, }
32. Dirk Beyer and Martin Spiessl. MetaVal: Witness Validation via Verification. In S. K. Lahiri and C. Wang, editors, Proceedings of the 32nd International Conference on Computer Aided Verification (CAV 2020, Virtual, USA, July 21-24), part 2, LNCS 12225, pages 165-177, 2020. Springer. doi:10.1007/978-3-030-53291-8_10 Keyword(s): CPAchecker, Software Model Checking, Witness-Based Validation, Witness-Based Validation (main) Funding: DFG-CONVEY Publisher's Version PDF Supplement
    BibTeX Entry

    @inproceedings{CAV20, author = {Dirk Beyer and Martin Spiessl}, title = {MetaVal: {W}itness Validation via Verification}, booktitle = {Proceedings of the 32nd International Conference on Computer Aided Verification (CAV~2020, Virtual, USA, July 21-24), part 2}, editor = {S.~K.~Lahiri and C.~Wang}, pages = {165-177}, year = {2020}, series = {LNCS~12225}, publisher = {Springer}, doi = {10.1007/978-3-030-53291-8_10}, sha256 = {7431085a248c7e2cab70318096622ff19ce1124067158d08866d3f9b250df44e}, url = {https://gitlab.com/sosy-lab/software/metaval}, abstract = {}, keyword = {CPAchecker,Software Model Checking,Witness-Based Validation,Witness-Based Validation (main)}, funding = {DFG-CONVEY}, isbnnote = {978-3-030-53290-1}, }
33. Dirk Beyer and Matthias Dangl. Software Verification with PDR: An Implementation of the State of the Art. In Proceedings of the 26th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2020, Dublin, Ireland, April 25-30), part 1, LNCS 12078, pages 3-21, 2020. Springer. doi:10.1007/978-3-030-45190-5_1 Keyword(s): Software Model Checking, CPAchecker Publisher's Version PDF Presentation Video Supplement
    BibTeX Entry

    @inproceedings{TACAS20a, author = {Dirk Beyer and Matthias Dangl}, title = {Software Verification with {PDR}: An Implementation of the State of the Art}, booktitle = {Proceedings of the 26th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS~2020, Dublin, Ireland, April 25-30), part 1}, pages = {3-21}, year = {2020}, series = {LNCS~12078}, publisher = {Springer}, doi = {10.1007/978-3-030-45190-5_1}, sha256 = {fbd54433b42cb4411ddf6d73eb198507a6d35d8b6581b000be30aed84633e204}, url = {https://www.sosy-lab.org/research/pdr-compare/}, presentation = {https://www.sosy-lab.org/research/prs/2021-03-31_TACAS20_PDR-for-Software_Dirk.pdf}, abstract = {}, keyword = {Software Model Checking,CPAchecker}, video = {https://youtu.be/Wxqd92sdHBE}, }
34. Dirk Beyer and Marie-Christine Jakobs. Cooperative Test-Case Generation with Verifiers. In M. Felderer, W. Hasselbring, R. Rabiser, and R. Jung, editors, Proceedings of the Conference on Software Engineering (SE 2020, Innsbruck, Austria, February 24-28), LNI P-300, pages 107-108, 2020. GI. doi:10.18420/SE2020_31 Keyword(s): CPAchecker, Software Model Checking, Software Testing Publisher's Version
    BibTeX Entry

    @inproceedings{SE20, author = {Dirk Beyer and Marie-Christine Jakobs}, title = {Cooperative Test-Case Generation with Verifiers}, booktitle = {Proceedings of the Conference on Software Engineering (SE~2020, Innsbruck, Austria, February 24-28)}, editor = {M.~Felderer and W.~Hasselbring and R.~Rabiser and R.~Jung}, pages = {107--108}, year = {2020}, series = {{LNI}~P-300}, publisher = {{GI}}, doi = {10.18420/SE2020_31}, sha256 = {}, pdf = {}, presentation = {}, abstract = {}, keyword = {CPAchecker,Software Model Checking,Software Testing}, annote = {This is a summary of a <a href="https://www.sosy-lab.org/research/bib/Year/2019.html#FASE19">full article on this topic</a> that appeared in Proc. FASE 2019.}, isbnnote = {978-3-88579-694-7}, }
    Additional Infos

    This is a summary of a full article on this topic that appeared in Proc. FASE 2019.
35. Dirk Beyer and Marie-Christine Jakobs. CoVeriTest: Cooperative Verifier-Based Testing. In Proceedings of the 22nd International Conference on Fundamental Approaches to Software Engineering (FASE 2019, Prague, Czech Republic, April 6-11), LNCS 11424, pages 389-408, 2019. Springer. doi:10.1007/978-3-030-16722-6_23 Keyword(s): CPAchecker, Software Model Checking, Software Testing Publisher's Version PDF Supplement
    BibTeX Entry

    @inproceedings{FASE19, author = {Dirk Beyer and Marie-Christine Jakobs}, title = {CoVeriTest: Cooperative Verifier-Based Testing}, booktitle = {Proceedings of the 22nd International Conference on Fundamental Approaches to Software Engineering (FASE~2019, Prague, Czech Republic, April 6-11)}, pages = {389-408}, year = {2019}, series = {LNCS~11424}, publisher = {Springer}, doi = {10.1007/978-3-030-16722-6_23}, sha256 = {ee64749fba4796ed79cecfaa500731ef2ac5d5e795770c44b1e7ad358f955398}, url = {https://www.sosy-lab.org/research/coop-testgen/}, keyword = {CPAchecker,Software Model Checking,Software Testing}, }
36. Dirk Beyer, Marie-Christine Jakobs, Thomas Lemberger, and Heike Wehrheim. Combining Verifiers in Conditional Model Checking via Reducers. In S. Becker, I. Bogicevic, G. Herzwurm, and S. Wagner, editors, Proceedings of the Conference on Software Engineering and Software Management (SE/SWM 2019, Stuttgart, Germany, February 18-22), LNI P-292, pages 151-152, 2019. GI. doi:10.18420/se2019-46 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Presentation
    Abstract

    Software verification received lots of attention in the past two decades. Nonetheless, it remains an extremely difficult problem. Some verification tasks cannot be solved automatically by any of today’s verifiers. To still verify such tasks, one can combine the strengths of different verifiers. A promising approach to create combinations is conditional model checking (CMC). In CMC, the first verifier outputs a condition that describes the parts of the program state space that it successfully verified, and the next verifier uses that condition to steer its exploration towards the unverified state space. Despite the benefits of CMC, only few verifiers can handle conditions. To overcome this problem, we propose an automatic plug-and-play extension for verifiers. Instead of modifying verifiers, we suggest to add a preprocessor: the reducer. The reducer takes the condition and the original program and computes a residual program that encodes the unverified state space in program code. We developed one such reducer and use it to integrate existing verifiers and test-case generators into the CMC process. Our experiments show that we can solve many additional verification tasks with this reducer-based construction.
    BibTeX Entry

    @inproceedings{SE19, author = {Dirk Beyer and Marie-Christine Jakobs and Thomas Lemberger and Heike Wehrheim}, title = {Combining Verifiers in Conditional Model Checking via Reducers}, booktitle = {Proceedings of the Conference on Software Engineering and Software Management (SE/SWM~2019, Stuttgart, Germany, February 18-22)}, editor = {S.~Becker and I.~Bogicevic and G.~Herzwurm and S.~Wagner}, pages = {151--152}, year = {2019}, series = {{LNI}~P-292}, publisher = {{GI}}, doi = {10.18420/se2019-46}, sha256 = {}, pdf = {https://www.sosy-lab.org/research/pub/2019-SE.Combining_Verifiers_in_Conditional_Model_Checking_via_Reducers.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2019-02-22_SE19_CombiningVerifiersInConditionalModelChecking_Marie.pdf}, abstract = {Software verification received lots of attention in the past two decades. Nonetheless, it remains an extremely difficult problem. Some verification tasks cannot be solved automatically by any of today’s verifiers. To still verify such tasks, one can combine the strengths of different verifiers. A promising approach to create combinations is conditional model checking (CMC). In CMC, the first verifier outputs a condition that describes the parts of the program state space that it successfully verified, and the next verifier uses that condition to steer its exploration towards the unverified state space. Despite the benefits of CMC, only few verifiers can handle conditions. To overcome this problem, we propose an automatic plug-and-play extension for verifiers. Instead of modifying verifiers, we suggest to add a preprocessor: the reducer. The reducer takes the condition and the original program and computes a residual program that encodes the unverified state space in program code. We developed one such reducer and use it to integrate existing verifiers and test-case generators into the CMC process. Our experiments show that we can solve many additional verification tasks with this reducer-based construction.}, keyword = {CPAchecker,Software Model Checking}, annote = {This is a summary of a <a href="https://www.sosy-lab.org/research/bib/Year/2018.html#ICSE18">full article on this topic</a> that appeared in Proc. ICSE 2018.}, }
    Additional Infos

    This is a summary of a full article on this topic that appeared in Proc. ICSE 2018.
37. Dirk Beyer and Karlheinz Friedberger. In-Place vs. Copy-on-Write CEGAR Refinement for Block Summarization with Caching. In T. Margaria and B. Steffen, editors, Proceedings of the 8th International Symposium on Leveraging Applications of Formal Methods, Verification, and Validation (ISoLA 2018, Part 2, Limassol, Cyprus, November 5-9), LNCS 11245, pages 197-215, 2018. Springer. doi:10.1007/978-3-030-03421-4_14 Keyword(s): CPAchecker, Software Model Checking, BAM Publisher's Version PDF Presentation Supplement
    Abstract

    Block summarization is an efficient technique in software verification to decompose a verification problem into separate tasks and to avoid repeated exploration of reusable parts of a program. In order to benefit from abstraction at the same time, block summarization can be combined with counterexample-guided abstraction refinement (CEGAR). This causes the following problem: whenever CEGAR instructs the model checker to refine the abstraction along a path, several block summaries are affected and need to be updated. There exist two different refinement strategies: a destructive in-place approach that modifies the existing block abstractions and a constructive copy-on-write approach that does not change existing data. While the in-place approach is used in the field for several years, our new approach of copy-on-write refinement has the following important advantage: A complete exportable proof of the program is available after the analysis has finished. Due to the benefit from avoiding recomputations of missing information as necessary for in-place updates, the new approach causes almost no computational overhead overall. We perform a large experimental evaluation to compare the new approach with the previous one to show that full proofs can be achieved without overhead.
    BibTeX Entry

    @inproceedings{ISoLA18b, author = {Dirk Beyer and Karlheinz Friedberger}, title = {In-Place vs. Copy-on-Write CEGAR Refinement for Block Summarization with Caching}, booktitle = {Proceedings of the 8th International Symposium on Leveraging Applications of Formal Methods, Verification, and Validation (ISoLA~2018, Part~2, Limassol, Cyprus, November 5-9)}, editor = {T.~Margaria and B.~Steffen}, pages = {197-215}, year = {2018}, series = {LNCS~11245}, publisher = {Springer}, doi = {10.1007/978-3-030-03421-4_14}, sha256 = {}, url = {https://www.sosy-lab.org/research/bam-cow-refinement/}, pdf = {https://www.sosy-lab.org/research/pub/2018-ISoLA.In-Place_vs_Copy-on-Write_CEGAR_Refinement_for_Block_Summarization_with_Caching.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2018-11-06_ISoLA18_BAM-CoW-Refinement_Dirk.pdf}, abstract = {Block summarization is an efficient technique in software verification to decompose a verification problem into separate tasks and to avoid repeated exploration of reusable parts of a program. In order to benefit from abstraction at the same time, block summarization can be combined with counterexample-guided abstraction refinement (CEGAR). This causes the following problem: whenever CEGAR instructs the model checker to refine the abstraction along a path, several block summaries are affected and need to be updated. There exist two different refinement strategies: a destructive in-place approach that modifies the existing block abstractions and a constructive copy-on-write approach that does not change existing data. While the in-place approach is used in the field for several years, our new approach of copy-on-write refinement has the following important advantage: A complete exportable proof of the program is available after the analysis has finished. Due to the benefit from avoiding recomputations of missing information as necessary for in-place updates, the new approach causes almost no computational overhead overall. We perform a large experimental evaluation to compare the new approach with the previous one to show that full proofs can be achieved without overhead.}, keyword = {CPAchecker,Software Model Checking,BAM}, }
38. Dirk Beyer and Matthias Dangl. Strategy Selection for Software Verification Based on Boolean Features: A Simple but Effective Approach. In T. Margaria and B. Steffen, editors, Proceedings of the 8th International Symposium on Leveraging Applications of Formal Methods, Verification, and Validation (ISoLA 2018, Part 2, Limassol, Cyprus, November 5-9), LNCS 11245, pages 144-159, 2018. Springer. doi:10.1007/978-3-030-03421-4_11 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Presentation
    BibTeX Entry

    @inproceedings{ISoLA18a, author = {Dirk Beyer and Matthias Dangl}, title = {Strategy Selection for Software Verification Based on Boolean Features: A Simple but Effective Approach}, booktitle = {Proceedings of the 8th International Symposium on Leveraging Applications of Formal Methods, Verification, and Validation (ISoLA~2018, Part~2, Limassol, Cyprus, November 5-9)}, editor = {T.~Margaria and B.~Steffen}, pages = {144-159}, year = {2018}, series = {LNCS~11245}, publisher = {Springer}, doi = {10.1007/978-3-030-03421-4_11}, sha256 = {}, pdf = {https://www.sosy-lab.org/research/pub/2018-ISoLA.Strategy_Selection_for_Software_Verification_Based_on_Boolean_Features.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2018-11-05_ISoLA18_StrategySelection_Dirk.pdf}, keyword = {CPAchecker,Software Model Checking}, }
39. Dirk Beyer and Thomas Lemberger. CPA-SymExec: Efficient Symbolic Execution in CPAchecker. In Marianne Huchard, Christian Kästner, and Gordon Fraser, editors, Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering (ASE 2018, Montpellier, France, September 3-7), pages 900-903, 2018. ACM. doi:10.1145/3238147.3240478 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Presentation Video Supplement
    Abstract

    We present CPA-SymExec, a tool for symbolic execution that is implemented in the open-source, configurable verification framework CPAchecker. Our implementation automatically detects which symbolic facts to track, in order to obtain a small set of constraints that are necessary to decide reachability of a program area of interest. CPA-SymExec is based on abstraction and counterexample-guided abstraction refinement (CEGAR), and uses a constraint-interpolation approach to detect symbolic facts. We show that our implementation can better mitigate the path-explosion problem than symbolic execution without abstraction, by comparing the performance to the state-of-the-art Klee-based symbolic-execution engine Symbiotic and to Klee itself. For the experiments we use two kinds of analysis tasks: one for finding an executable path to a specific location of interest (e.g., if a test vector is desired to show that a certain behavior occurs), and one for confirming that no executable path to a specific location exists (e.g., if it is desired to show that a certain behavior never occurs). CPA-SymExec is released under the Apache 2 license and available (inclusive source code) at https://cpachecker.sosy-lab.org. A demonstration video is available at https://youtu.be/qoBHtvPKtnw.
    BibTeX Entry

    @inproceedings{ASE18b, author = {Dirk Beyer and Thomas Lemberger}, title = {{CPA-SymExec}: Efficient Symbolic Execution in {CPAchecker}}, booktitle = {Proceedings of the 33rd {ACM/IEEE} International Conference on Automated Software Engineering ({ASE}~2018, Montpellier, France, September 3-7)}, editor = {Marianne Huchard and Christian K{\"{a}}stner and Gordon Fraser}, pages = {900-903}, year = {2018}, publisher = {ACM}, doi = {10.1145/3238147.3240478}, sha256 = {}, url = {https://www.sosy-lab.org/research/cpa-symexec-tool/}, pdf = {https://www.sosy-lab.org/research/pub/2018-ASE.CPA-SymExec_Efficient_Symbolic_Execution_in_CPAchecker.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2018-09-07_ASE18_CPASymExec_Thomas.pdf}, abstract = {We present CPA-SymExec, a tool for symbolic execution that is implemented in the open-source, configurable verification framework CPAchecker. Our implementation automatically detects which symbolic facts to track, in order to obtain a small set of constraints that are necessary to decide reachability of a program area of interest. CPA-SymExec is based on abstraction and counterexample-guided abstraction refinement (CEGAR), and uses a constraint-interpolation approach to detect symbolic facts. We show that our implementation can better mitigate the path-explosion problem than symbolic execution without abstraction, by comparing the performance to the state-of-the-art Klee-based symbolic-execution engine Symbiotic and to Klee itself. For the experiments we use two kinds of analysis tasks: one for finding an executable path to a specific location of interest (e.g., if a test vector is desired to show that a certain behavior occurs), and one for confirming that no executable path to a specific location exists (e.g., if it is desired to show that a certain behavior never occurs). CPA-SymExec is released under the Apache 2 license and available (inclusive source code) at https://cpachecker.sosy-lab.org. A demonstration video is available at https://youtu.be/qoBHtvPKtnw.}, keyword = {CPAchecker,Software Model Checking}, video = {https://youtu.be/7o7EtpbV8NM}, }
40. Dirk Beyer and Karlheinz Friedberger. Domain-Independent Multi-threaded Software Model Checking. In Marianne Huchard, Christian Kästner, and Gordon Fraser, editors, Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering, ASE 2018, Montpellier, France, September 3-7, 2018, pages 634-644, 2018. ACM. doi:10.1145/3238147.3238195 Keyword(s): CPAchecker, Software Model Checking, BAM Publisher's Version PDF Presentation Supplement
    Abstract

    Recent development of software aims at massively parallel execution, because of the trend to increase the number of processing units per CPU socket. But many approaches for program analysis are not designed to benefit from a multi-threaded execution and lack support to utilize multi-core computers. Rewriting existing algorithms is difficult and error-prone, and the design of new parallel algorithms also has limitations. An orthogonal problem is the granularity: computing each successor state in parallel seems too fine-grained, so the open question is to find the right structural level for parallel execution. We propose an elegant solution to these problems: Block summaries should be computed in parallel. Many successful approaches to software verification are based on summaries of control-flow blocks, large blocks, or function bodies. Block-abstraction memoization is a successful domain-independent approach for summary-based program analysis. We redesigned the verification approach of block-abstraction memoization starting from its original recursive definition, such that it can run in a parallel manner for utilizing the available computation resources without losing its advantages of being independent from a certain abstract domain. We present an implementation of our new approach for multi-core shared-memory machines. The experimental evaluation shows that our summary-based approach has no significant overhead compared to the existing sequential approach and that it has a significant speedup when using multi-threading.
    BibTeX Entry

    @inproceedings{ASE18a, author = {Dirk Beyer and Karlheinz Friedberger}, title = {Domain-Independent Multi-threaded Software Model Checking}, booktitle = {Proceedings of the 33rd {ACM/IEEE} International Conference on Automated Software Engineering, {ASE} 2018, Montpellier, France, September 3-7, 2018}, editor = {Marianne Huchard and Christian K{\"{a}}stner and Gordon Fraser}, pages = {634-644}, year = {2018}, publisher = {ACM}, doi = {10.1145/3238147.3238195}, sha256 = {}, url = {https://www.sosy-lab.org/research/bam-parallel/}, pdf = {https://www.sosy-lab.org/research/pub/2018-ASE.Domain-Independent_Multi-threaded_Software_Model_Checking.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2018-09-07_ASE18_ParallelBAM_Karlheinz.pdf}, abstract = {Recent development of software aims at massively parallel execution, because of the trend to increase the number of processing units per CPU socket. But many approaches for program analysis are not designed to benefit from a multi-threaded execution and lack support to utilize multi-core computers. Rewriting existing algorithms is difficult and error-prone, and the design of new parallel algorithms also has limitations. An orthogonal problem is the granularity: computing each successor state in parallel seems too fine-grained, so the open question is to find the right structural level for parallel execution. We propose an elegant solution to these problems: Block summaries should be computed in parallel. Many successful approaches to software verification are based on summaries of control-flow blocks, large blocks, or function bodies. Block-abstraction memoization is a successful domain-independent approach for summary-based program analysis. We redesigned the verification approach of block-abstraction memoization starting from its original recursive definition, such that it can run in a parallel manner for utilizing the available computation resources without losing its advantages of being independent from a certain abstract domain. We present an implementation of our new approach for multi-core shared-memory machines. The experimental evaluation shows that our summary-based approach has no significant overhead compared to the existing sequential approach and that it has a significant speedup when using multi-threading.}, keyword = {CPAchecker,Software Model Checking,BAM}, }
41. Dirk Beyer, Matthias Dangl, Thomas Lemberger, and Michael Tautschnig. Tests from Witnesses: Execution-Based Validation of Verification Results. In Catherine Dubois and Burkhart Wolff, editors, Proceedings of the 12th International Conference on Tests and Proofs (TAP 2018, Toulouse, France, June 27-29), LNCS 10889, pages 3-23, 2018. Springer. doi:10.1007/978-3-319-92994-1_1 Keyword(s): CPAchecker, Software Model Checking, Witness-Based Validation, Witness-Based Validation (main) Publisher's Version PDF Presentation Supplement
    Abstract

    The research community made enormous progress in the past years in developing algorithms for verifying software, as shown by verification competitions (SV-COMP). However, the ultimate goal is to design certifying algorithms, which produce for a given input not only the output but in addition a witness. This makes it possible to validate that the output is a correct solution for the input problem. The advantage of certifying algorithms is that the validation of the result is —thanks to the witness— easier than the computation of the result. Unfortunately, the transfer to industry is slow, one of the reasons being that some verifiers report a considerable number of false alarms. The verification community works towards this ultimate goal using exchangeable violation witnesses, i.e., an independent validator can be used to check whether the produced witness indeed represents a bug. This reduces the required trust base from the complex verification tool to a validator that may be less complex, and thus, more easily trustable. But existing witness validators are based on model-checking technology — which does not solve the problem of reducing the trust base. To close this gap, we present a simple concept that is based on program execution: We extend witness validation by generating a test vector from an error path that is reconstructed from the witness. Then, we generate a test harness (similar to unit-test code) that can be compiled and linked together with the original program. We then run the executable program in an isolating container. If the execution violates the specification (similar to runtime verification) we confirm that the witness indeed represents a bug. This method reduces the trust base to the execution system, which seems appropriate for avoiding false alarms. To show feasibility and practicality, we implemented execution-based witness validation in two completely independent analysis frameworks, and performed a large experimental study.
    BibTeX Entry

    @inproceedings{TAP18, author = {Dirk Beyer and Matthias Dangl and Thomas Lemberger and Michael Tautschnig}, title = {Tests from Witnesses: Execution-Based Validation of Verification Results}, booktitle = {Proceedings of the 12th International Conference on Tests and Proofs (TAP~2018, Toulouse, France, June 27-29)}, editor = {Catherine Dubois and Burkhart Wolff}, pages = {3-23}, year = {2018}, series = {LNCS~10889}, publisher = {Springer}, doi = {10.1007/978-3-319-92994-1_1}, sha256 = {}, url = {https://www.sosy-lab.org/research/tests-from-witnesses/}, pdf = {https://www.sosy-lab.org/research/pub/2018-TAP.Tests_from_Witnesses_Execution-Based_Validation_of_Verification_Results.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2018-06-27_TAP18-Keynote-CooperativeVerification_Dirk.pdf}, abstract = {The research community made enormous progress in the past years in developing algorithms for verifying software, as shown by verification competitions (SV-COMP). However, the ultimate goal is to design certifying algorithms, which produce for a given input not only the output but in addition a witness. This makes it possible to validate that the output is a correct solution for the input problem. The advantage of certifying algorithms is that the validation of the result is —thanks to the witness— easier than the computation of the result. Unfortunately, the transfer to industry is slow, one of the reasons being that some verifiers report a considerable number of false alarms. The verification community works towards this ultimate goal using exchangeable violation witnesses, i.e., an independent validator can be used to check whether the produced witness indeed represents a bug. This reduces the required trust base from the complex verification tool to a validator that may be less complex, and thus, more easily trustable. But existing witness validators are based on model-checking technology — which does not solve the problem of reducing the trust base. To close this gap, we present a simple concept that is based on program execution: We extend witness validation by generating a test vector from an error path that is reconstructed from the witness. Then, we generate a test harness (similar to unit-test code) that can be compiled and linked together with the original program. We then run the executable program in an isolating container. If the execution violates the specification (similar to runtime verification) we confirm that the witness indeed represents a bug. This method reduces the trust base to the execution system, which seems appropriate for avoiding false alarms. To show feasibility and practicality, we implemented execution-based witness validation in two completely independent analysis frameworks, and performed a large experimental study.}, keyword = {CPAchecker,Software Model Checking,Witness-Based Validation,Witness-Based Validation (main)}, }
42. Dirk Beyer, Marie-Christine Jakobs, Thomas Lemberger, and Heike Wehrheim. Reducer-Based Construction of Conditional Verifiers. In Proceedings of the 40th International Conference on Software Engineering (ICSE 2018, Gothenburg, Sweden, May 27 - June 3), pages 1182-1193, 2018. ACM. doi:10.1145/3180155.3180259 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Presentation Supplement
    Abstract

    Despite recent advances, software verification remains challenging. To solve hard verification tasks, we need to leverage not just one but several different verifiers employing different technologies. To this end, we need to exchange information between verifiers. Conditional model checking was proposed as a solution to exactly this problem: The idea is to let the first verifier output a condition which describes the state space that it successfully verified and to instruct the second verifier to verify the yet unverified state space using this condition. However, most verifiers do not understand conditions as input. In this paper, we propose the usage of an off-the-shelf construction of a conditional verifier from a given traditional verifier and a reducer. The reducer takes as input the program to be verified and the condition, and outputs a residual program whose paths cover the unverified state space described by the condition. As a proof of concept, we designed and implemented one particular reducer and composed three conditional model checkers from the three best verifiers at SV-COMP 2017. We defined a set of claims and experimentally evaluated their validity. All experimental data and results are available for replication.
    BibTeX Entry

    @inproceedings{ICSE18, author = {Dirk Beyer and Marie-Christine Jakobs and Thomas Lemberger and Heike Wehrheim}, title = {Reducer-Based Construction of Conditional Verifiers}, booktitle = {Proceedings of the 40th International Conference on Software Engineering (ICSE~2018, Gothenburg, Sweden, May 27 - June 3)}, pages = {1182-1193}, year = {2018}, publisher = {ACM}, isbn = {978-1-4503-5638-1}, doi = {10.1145/3180155.3180259}, sha256 = {}, url = {https://www.sosy-lab.org/research/reducer/}, pdf = {https://www.sosy-lab.org/research/pub/2018-ICSE.Reducer-Based_Construction_of_Conditional_Verifiers.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2018-06-01_ICSE18_ReducerBasedConstructionOfConditionalVerifiers_Marie.pdf}, abstract = {Despite recent advances, software verification remains challenging. To solve hard verification tasks, we need to leverage not just one but several different verifiers employing different technologies. To this end, we need to exchange information between verifiers. Conditional model checking was proposed as a solution to exactly this problem: The idea is to let the first verifier output a condition which describes the state space that it successfully verified and to instruct the second verifier to verify the yet unverified state space using this condition. However, most verifiers do not understand conditions as input. In this paper, we propose the usage of an off-the-shelf construction of a conditional verifier from a given traditional verifier and a reducer. The reducer takes as input the program to be verified and the condition, and outputs a residual program whose paths cover the unverified state space described by the condition. As a proof of concept, we designed and implemented one particular reducer and composed three conditional model checkers from the three best verifiers at SV-COMP 2017. We defined a set of claims and experimentally evaluated their validity. All experimental data and results are available for replication.}, keyword = {CPAchecker,Software Model Checking}, }
43. Dirk Beyer and Thomas Lemberger. Software Verification: Testing vs. Model Checking. In O. Strichman and R. Tzoref-Brill, editors, Proceedings of the 13th Haifa Verification Conference (HVC 2017, Haifa, Israel, November 13-25), LNCS 10629, pages 99-114, 2017. Springer. doi:10.1007/978-3-319-70389-3_7 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Presentation Supplement
    Abstract

    In practice, software testing has been the established method for finding bugs in programs for a long time. But in the last 15 years, software model checking has received a lot of attention, and many successful tools for software model checking exist today. We believe it is time for a careful comparative evaluation of automatic software testing against automatic software model checking. We chose six existing tools for automatic test-case generation, namely AFL-fuzz, CPATiger, Crest-ppc, FShell, Klee, and PRtest, and four tools for software model checking, namely CBMC, CPA-Seq, ESBMC-incr, and ESBMC-kInd, for the task of finding specification violations in a large benchmark suite consisting of 5693 C programs. In order to perform such an evaluation, we have implemented a framework for test-based falsification (TBF) that executes and validates test cases produced by test-case generation tools in order to find errors in programs. The conclusion of our experiments is that software model checkers can (i) find a substantially larger number of bugs (ii) in less time, and (iii) require less adjustment to the input programs.
    BibTeX Entry

    @inproceedings{HVC17, author = {Dirk Beyer and Thomas Lemberger}, title = {Software Verification: Testing vs. Model Checking}, booktitle = {Proceedings of the 13th Haifa Verification Conference (HVC~2017, Haifa, Israel, November 13-25)}, editor = {O.~Strichman and R.~Tzoref-Brill}, pages = {99-114}, year = {2017}, series = {LNCS~10629}, publisher = {Springer}, isbn = {978-3-319-70389-3}, doi = {10.1007/978-3-319-70389-3_7}, sha256 = {}, url = {https://www.sosy-lab.org/research/test-study/}, pdf = {https://www.sosy-lab.org/research/pub/2017-HVC.Software_Verification_Testing_vs_Model_Checking.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2017-11-15_HVC17_TestStudy_Thomas.pdf}, abstract = {In practice, software testing has been the established method for finding bugs in programs for a long time. But in the last 15 years, software model checking has received a lot of attention, and many successful tools for software model checking exist today. We believe it is time for a careful comparative evaluation of automatic software testing against automatic software model checking. We chose six existing tools for automatic test-case generation, namely AFL-fuzz, CPATiger, Crest-ppc, FShell, Klee, and PRtest, and four tools for software model checking, namely CBMC, CPA-Seq, ESBMC-incr, and ESBMC-kInd, for the task of finding specification violations in a large benchmark suite consisting of 5693 C programs. In order to perform such an evaluation, we have implemented a framework for test-based falsification (TBF) that executes and validates test cases produced by test-case generation tools in order to find errors in programs. The conclusion of our experiments is that software model checkers can (i) find a substantially larger number of bugs (ii) in less time, and (iii) require less adjustment to the input programs.}, keyword = {CPAchecker,Software Model Checking}, annote = {Won the HVC 2017 Best Paper Award.<br> <a href="https://www.sosy-lab.org/research/pub/2017-HVC.Software_Verification_Testing_vs_Model_Checking.Errata.txt"> Errata</a> available.}, }
    Additional Infos

    Won the HVC 2017 Best Paper Award.
    Errata available.
44. Dirk Beyer, Matthias Dangl, Daniel Dietsch, and Matthias Heizmann. Exchanging Verification Witnesses between Verifiers. In J. Jürjens and K. Schneider, editors, Tagungsband Software Engineering 2017, Fachtagung des GI-Fachbereichs Softwaretechnik (21.-24. Februar 2017, Hannover, Deutschland), LNI P-267, pages 93-94, 2017. Gesellschaft für Informatik (GI). Keyword(s): CPAchecker, Software Model Checking, Witness-Based Validation Publisher's Version
    BibTeX Entry

    @inproceedings{SE17-Witnesses, author = {Dirk Beyer and Matthias Dangl and Daniel Dietsch and Matthias Heizmann}, title = {Exchanging Verification Witnesses between Verifiers}, booktitle = {Tagungsband Software Engineering 2017, Fachtagung des GI-Fachbereichs Softwaretechnik (21.-24. Februar 2017, Hannover, Deutschland)}, editor = {J.~J{\"{u}}rjens and K.~Schneider}, pages = {93-94}, year = {2017}, series = {{LNI}~P-267}, publisher = {Gesellschaft f{\"{u}}r Informatik ({GI})}, url = {}, keyword = {CPAchecker,Software Model Checking,Witness-Based Validation}, annote = {This is a summary of a <a href="https://www.sosy-lab.org/research/bib/Year/2016.html#FSE16b">full article on this topic</a> that appeared in Proc. ESEC/FSE 2016.}, doinone = {DOI not available}, urlpub = {https://dl.gi.de/handle/20.500.12116/1288}, }
    Additional Infos

    This is a summary of a full article on this topic that appeared in Proc. ESEC/FSE 2016.
45. Pavel Andrianov, Karlheinz Friedberger, Mikhail U. Mandrykin, Vadim S. Mutilin, and Anton Volkov. CPA-BAM-BnB: Block-Abstraction Memoization and Region-Based Memory Models for Predicate Abstractions (Competition Contribution). In Axel Legay and Tiziana Margaria, editors, Proceedings of the 23rd International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2017, Uppsala, Sweden, April 22-29), LNCS 10206, pages 355-359, 2017. Springer-Verlag, Heidelberg. doi:10.1007/978-3-662-54580-5_22 Keyword(s): CPAchecker, Competition on Software Verification (SV-COMP), Software Model Checking Publisher's Version PDF Supplement
    Abstract

    Our submission to SV-COMP'17 is based on the software verification framework CPAchecker. Combined with value analysis and predicate analysis we use the concept of block-abstraction memoization with optimization and several fixes relative to the version of SV-COMP'16. A novelty of our approach is usage of BnB memory model for predicate analysis, which efficiently divides the accessed memory into memory regions and thus leads to smaller formulas.
    BibTeX Entry

    @inproceedings{CPABAM-COMP17, author = {Pavel Andrianov and Karlheinz Friedberger and Mikhail U. Mandrykin and Vadim S. Mutilin and Anton Volkov}, title = {{CPA-BAM-BnB}: {Block}-Abstraction Memoization and Region-Based Memory Models for Predicate Abstractions (Competition Contribution)}, booktitle = {Proceedings of the 23rd International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS~2017, Uppsala, Sweden, April 22-29)}, editor = {Axel Legay and Tiziana Margaria}, pages = {355--359}, year = {2017}, series = {LNCS~10206}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-662-54579-9}, doi = {10.1007/978-3-662-54580-5_22}, sha256 = {}, url = {https://doi.org/10.1007/978-3-662-54580-5_22}, abstract = {Our submission to SV-COMP'17 is based on the software verification framework CPAchecker. Combined with value analysis and predicate analysis we use the concept of block-abstraction memoization with optimization and several fixes relative to the version of SV-COMP'16. A novelty of our approach is usage of BnB memory model for predicate analysis, which efficiently divides the accessed memory into memory regions and thus leads to smaller formulas.}, keyword = {CPAchecker,Competition on Software Verification (SV-COMP),Software Model Checking}, }
46. Dirk Beyer, Matthias Dangl, Daniel Dietsch, and Matthias Heizmann. Correctness Witnesses: Exchanging Verification Results Between Verifiers. In T. Zimmermann, J. Cleland-Huang, and Z. Su, editors, Proceedings of the 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE 2016, Seattle, WA, USA, November 13-18), pages 326-337, 2016. ACM. doi:10.1145/2950290.2950351 Keyword(s): CPAchecker, Ultimate, Software Model Checking, Witness-Based Validation, Witness-Based Validation (main) Publisher's Version PDF
    BibTeX Entry

    @inproceedings{FSE16b, author = {Dirk Beyer and Matthias Dangl and Daniel Dietsch and Matthias Heizmann}, title = {Correctness Witnesses: {E}xchanging Verification Results Between Verifiers}, booktitle = {Proceedings of the 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE~2016, Seattle, WA, USA, November 13-18)}, editor = {T.~Zimmermann and J.~Cleland-Huang and Z.~Su}, pages = {326-337}, year = {2016}, publisher = {ACM}, doi = {10.1145/2950290.2950351}, sha256 = {}, url = {}, pdf = {https://www.sosy-lab.org/research/pub/2016-FSE.Correctness_Witnesses_Exchanging_Verification_Results_between_Verifiers.pdf}, keyword = {CPAchecker,Ultimate,Software Model Checking,Witness-Based Validation,Witness-Based Validation (main)}, }
47. Dirk Beyer and Thomas Lemberger. Symbolic Execution with CEGAR. In T. Margaria and B. Steffen, editors, 7th International Symposium on Leveraging Applications of Formal Methods, Verification, and Validation (ISoLA 2016, Part 1, Imperial, Corfu, Greece, October 10-14), LNCS 9952, pages 195-211, 2016. Springer. doi:10.1007/978-3-319-47166-2_14 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Presentation Supplement
    Abstract

    Symbolic execution, a standard technique in program analysis, is a particularly successful and popular component in systems for test-case generation. One of the open research problems is that the approach suffers from the path-explosion problem. We apply abstraction to symbolic execution, and refine the abstract model using counterexampleguided abstraction refinement (CEGAR), a standard technique from model checking. We also use refinement selection with existing and new heuristics to influence the behavior and further improve the performance of our refinement procedure. We implemented our new technique in the open-source software-verification framework CPAchecker. Our experimental results show that the implementation is highly competitive.
    BibTeX Entry

    @inproceedings{ISOLA16a, author = {Dirk Beyer and Thomas Lemberger}, title = {Symbolic Execution with {CEGAR}}, booktitle = {7th International Symposium on Leveraging Applications of Formal Methods, Verification, and Validation (ISoLA~2016, Part~1, Imperial, Corfu, Greece, October 10-14)}, editor = {T.~Margaria and B.~Steffen}, pages = {195-211}, year = {2016}, series = {LNCS~9952}, publisher = {Springer}, doi = {10.1007/978-3-319-47166-2_14}, sha256 = {}, url = {https://www.sosy-lab.org/research/cpa-symexec/}, pdf = {https://www.sosy-lab.org/research/pub/2016-ISoLA.Symbolic_Execution_with_CEGAR.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2016-10-10_ISoLA16_SymbolicExecutionWithCegar_Dirk.pdf}, abstract = {Symbolic execution, a standard technique in program analysis, is a particularly successful and popular component in systems for test-case generation. One of the open research problems is that the approach suffers from the path-explosion problem. We apply abstraction to symbolic execution, and refine the abstract model using counterexampleguided abstraction refinement (CEGAR), a standard technique from model checking. We also use refinement selection with existing and new heuristics to influence the behavior and further improve the performance of our refinement procedure. We implemented our new technique in the open-source software-verification framework CPAchecker. Our experimental results show that the implementation is highly competitive.}, keyword = {CPAchecker,Software Model Checking}, annote = {<a href="https://www.sosy-lab.org/research/pub/2016-ISoLA.Symbolic_Execution_with_CEGAR.Errata.txt"> Errata</a> available.}, }
    Additional Infos

    Errata available.
48. Dirk Beyer and Karlheinz Friedberger. A Light-Weight Approach for Verifying Multi-Threaded Programs with CPAchecker. In J. Bouda, L. Holík, J. Kofroň, J. Strejček, and A. Rambousek, editors, Proceedings of the 11th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2016, Telč, Czechia, October 21-23), EPTCS 233, pages 61-71, 2016. ArXiV. doi:10.4204/EPTCS.233.6 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF
    BibTeX Entry

    @inproceedings{MEMICS16-Multi-Threaded, author = {Dirk Beyer and Karlheinz Friedberger}, title = {A Light-Weight Approach for Verifying Multi-Threaded Programs with CPAchecker}, booktitle = {Proceedings of the 11th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS~2016, Tel\v{c}, Czechia, October 21-23)}, editor = {J.~Bouda and L.~Hol\'ik and J.~Kofro\v{n} and J.~Strej\v{c}ek and A.~Rambousek}, pages = {61-71}, year = {2016}, series = {EPTCS~233}, publisher = {ArXiV}, doi = {10.4204/EPTCS.233.6}, sha256 = {}, pdf = {https://www.sosy-lab.org/research/pub/2016-MEMICS.A_Light-Weight_Approach_for_Verifying_Multi-Threaded_Programs_with_CPAchecker.pdf}, keyword = {CPAchecker,Software Model Checking}, }
49. Dirk Beyer and Matthias Dangl. SMT-based Software Model Checking: An Experimental Comparison of Four Algorithms. In Proc. VSTTE, LNCS 9971, pages 181-198, 2016. Springer. doi:10.1007/978-3-319-48869-1_14 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    BibTeX Entry

    @inproceedings{VSTTE16b-AlgorithmComparison, author = {Dirk Beyer and Matthias Dangl}, title = {{SMT}-based Software Model Checking: {A}n Experimental Comparison of Four Algorithms}, booktitle = {Proc.\ VSTTE}, pages = {181--198}, year = {2016}, series = {LNCS~9971}, publisher = {Springer}, doi = {10.1007/978-3-319-48869-1_14}, sha256 = {}, url = {https://www.sosy-lab.org/research/k-ind-compare/index-vstte.html}, pdf = {https://www.sosy-lab.org/research/pub/2016-VSTTE.SMT-based_Software_Model_Checking_An_Experimental_Comparison_of_Four_Algorithms.pdf}, keyword = {CPAchecker,Software Model Checking}, annote = {An <a href="https://www.sosy-lab.org/research/bib/Year/2018.complete.html#AlgorithmComparison-JAR">extended version</a> of this article appeared in JAR.}, }
    Additional Infos

    An extended version of this article appeared in JAR.
50. Dirk Beyer, Matthias Dangl, Daniel Dietsch, Matthias Heizmann, and Andreas Stahlbauer. Verification Witnesses. In J. Knoop and U. Zdun, editors, Tagungsband Software Engineering 2016, Fachtagung des GI-Fachbereichs Softwaretechnik (23.-26. Februar 2016, Wien, Österreich), LNI 252, pages 105-106, 2016. Gesellschaft für Informatik (GI). Keyword(s): CPAchecker, Software Model Checking, Witness-Based Validation Publisher's Version
    BibTeX Entry

    @inproceedings{SE16b-VerificationWitnesses, author = {Dirk Beyer and Matthias Dangl and Daniel Dietsch and Matthias Heizmann and Andreas Stahlbauer}, title = {Verification Witnesses}, booktitle = {Tagungsband Software Engineering 2016, Fachtagung des GI-Fachbereichs Softwaretechnik (23.-26. Februar 2016, Wien, {\"O}sterreich)}, editor = {J.~Knoop and U.~Zdun}, pages = {105-106}, year = {2016}, series = {{LNI}~252}, publisher = {Gesellschaft f{\"{u}}r Informatik ({GI})}, url = {}, keyword = {CPAchecker,Software Model Checking,Witness-Based Validation}, annote = {This is a summary of a <a href="https://www.sosy-lab.org/research/bib/Year/2015.html#FSE15">full article on this topic</a> that appeared in Proc. ESEC/FSE 2015.}, doinone = {DOI not available}, urlpub = {https://dl.gi.de/handle/20.500.12116/746}, }
    Additional Infos

    This is a summary of a full article on this topic that appeared in Proc. ESEC/FSE 2015.
51. Malte Lochau, Johannes Bürdek, Stefan Bauregger, Andreas Holzer, Alexander von Rhein, Sven Apel, and Dirk Beyer. On Facilitating Reuse in Multi-goal Test-Suite Generation for Software Product Lines. In J. Knoop and U. Zdun, editors, Tagungsband Software Engineering 2016, Fachtagung des GI-Fachbereichs Softwaretechnik (23.-26. Februar 2016, Wien, Österreich), LNI 252, pages 81-82, 2016. Gesellschaft für Informatik (GI). Keyword(s): CPAchecker, Software Model Checking Publisher's Version
    BibTeX Entry

    @inproceedings{SE16a-Test-SPL, author = {Malte Lochau and Johannes B{\"u}rdek and Stefan Bauregger and Andreas Holzer and Alexander von Rhein and Sven Apel and Dirk Beyer}, title = {On Facilitating Reuse in Multi-goal Test-Suite Generation for Software Product Lines}, booktitle = {Tagungsband Software Engineering 2016, Fachtagung des GI-Fachbereichs Softwaretechnik (23.-26. Februar 2016, Wien, {\"O}sterreich)}, editor = {J.~Knoop and U.~Zdun}, pages = {81-82}, year = {2016}, series = {{LNI}~252}, publisher = {Gesellschaft f{\"{u}}r Informatik ({GI})}, url = {}, keyword = {CPAchecker,Software Model Checking}, annote = {This is a summary of a <a href="https://www.sosy-lab.org/research/bib/Year/2015.html#FASE15">full article on this topic</a> that appeared in Proc. FASE 2015.}, doinone = {DOI not available}, urlpub = {https://dl.gi.de/handle/20.500.12116/733}, }
    Additional Infos

    This is a summary of a full article on this topic that appeared in Proc. FASE 2015.
52. Egor George Karpenkov, David Monniaux, and Philipp Wendler. Program Analysis with Local Policy Iteration. In Proceedings of the 17th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI 2016, St. Petersburg, FL, USA, January 17-19), LNCS 9583, pages 127-146, 2016. Springer-Verlag, Heidelberg. doi:10.1007/978-3-662-49122-5_6 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    Abstract

    We present local policy iteration (LPI), a new algorithm for deriving numerical invariants that combines the precision of max-policy iteration with the flexibility and scalability of conventional Kleene iterations. It is defined in the Configurable Program Analysis (CPA) framework, thus allowing inter-analysis communication. LPI uses adjustable-block encoding in order to traverse loop-free program sections, possibly containing branching, without introducing extra abstraction. Our technique operates over any template linear constraint domain, including the interval and octagon domains; templates can also be derived from the program source. The implementation is evaluated on a set of benchmarks from the International Competition on Software Verification (SV-COMP). It competes favorably with state-of-the-art analyzers.
    BibTeX Entry

    @inproceedings{LPI, author = {Egor George Karpenkov and David Monniaux and Philipp Wendler}, title = {Program Analysis with Local Policy Iteration}, booktitle = {Proceedings of the 17th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI~2016, St.~Petersburg, FL, USA, January 17-19)}, pages = {127--146}, year = {2016}, series = {LNCS~9583}, publisher = {Springer-Verlag, Heidelberg}, doi = {10.1007/978-3-662-49122-5_6}, sha256 = {}, url = {http://lpi.metaworld.me}, pdf = {https://arxiv.org/pdf/1509.03424}, abstract = {We present local policy iteration (LPI), a new algorithm for deriving numerical invariants that combines the precision of max-policy iteration with the flexibility and scalability of conventional Kleene iterations. It is defined in the Configurable Program Analysis (CPA) framework, thus allowing inter-analysis communication. LPI uses adjustable-block encoding in order to traverse loop-free program sections, possibly containing branching, without introducing extra abstraction. Our technique operates over any template linear constraint domain, including the interval and octagon domains; templates can also be derived from the program source. The implementation is evaluated on a set of benchmarks from the International Competition on Software Verification (SV-COMP). It competes favorably with state-of-the-art analyzers.}, keyword = {CPAchecker,Software Model Checking}, }
53. Karlheinz Friedberger. CPA-BAM: Block-Abstraction Memoization with Value Analysis and Predicate Analysis (Competition Contribution). In Marsha Chechik and Jean-François Raskin, editors, Proceedings of the 22nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2016, Eindhoven, The Netherlands, April 2-8), LNCS 9636, pages 912-915, 2016. Springer-Verlag, Heidelberg. doi:10.1007/978-3-662-49674-9_58 Keyword(s): CPAchecker, Competition on Software Verification (SV-COMP), Software Model Checking Publisher's Version PDF Supplement
    BibTeX Entry

    @inproceedings{CPABAM-COMP16, author = {Karlheinz Friedberger}, title = {{CPA-BAM}: Block-Abstraction Memoization with Value Analysis and Predicate Analysis (Competition Contribution)}, booktitle = {Proceedings of the 22nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS~2016, Eindhoven, The Netherlands, April 2-8)}, editor = {Marsha Chechik and Jean{-}Fran{\c{c}}ois Raskin}, pages = {912--915}, year = {2016}, series = {LNCS~9636}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-662-49673-2}, doi = {10.1007/978-3-662-49674-9_58}, sha256 = {}, url = {https://doi.org/10.1007/978-3-662-49674-9_58}, keyword = {CPAchecker,Competition on Software Verification (SV-COMP),Software Model Checking}, }
54. Stefan Löwe. CPA-RefSel: CPAchecker with Refinement Selection (Competition Contribution). In Marsha Chechik and Jean-François Raskin, editors, Proceedings of the 22nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2016, Eindhoven, The Netherlands, April 2-8), LNCS 9636, pages 916-919, 2016. Springer-Verlag, Heidelberg. doi:10.1007/978-3-662-49674-9_59 Keyword(s): CPAchecker, Competition on Software Verification (SV-COMP), Software Model Checking Publisher's Version PDF Supplement
    BibTeX Entry

    @inproceedings{CPAREFSEL-COMP16, author = {Stefan L{\"{o}}we}, title = {{CPA-RefSel}: {{\sc CPAchecker}} with Refinement Selection (Competition Contribution)}, booktitle = {Proceedings of the 22nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS~2016, Eindhoven, The Netherlands, April 2-8)}, editor = {Marsha Chechik and Jean{-}Fran{\c{c}}ois Raskin}, pages = {916--919}, year = {2016}, series = {LNCS~9636}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-662-49673-2}, doi = {10.1007/978-3-662-49674-9_59}, sha256 = {}, url = {https://doi.org/10.1007/978-3-662-49674-9_59}, keyword = {CPAchecker,Competition on Software Verification (SV-COMP),Software Model Checking}, annote = {Won category DeviceDriversLinux64 in <span style="white-space: nowrap"><a href="https://sv-comp.sosy-lab.org/2016/">SV-COMP'16</a></span>}, }
    Additional Infos

    Won category DeviceDriversLinux64 in SV-COMP'16
55. Dirk Beyer, Matthias Dangl, Daniel Dietsch, Matthias Heizmann, and Andreas Stahlbauer. Witness Validation and Stepwise Testification across Software Verifiers. In E. Di Nitto, M. Harman, and P. Heymans, editors, Proceedings of the 2015 10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on Foundations of Software Engineering (ESEC/FSE 2015, Bergamo, Italy, August 31 - September 4), pages 721-733, 2015. ACM, New York. doi:10.1145/2786805.2786867 Keyword(s): CPAchecker, Ultimate, Software Model Checking, Witness-Based Validation, Witness-Based Validation (main) Publisher's Version PDF
    BibTeX Entry

    @inproceedings{FSE15, author = {Dirk Beyer and Matthias Dangl and Daniel Dietsch and Matthias Heizmann and Andreas Stahlbauer}, title = {Witness Validation and Stepwise Testification across Software Verifiers}, booktitle = {Proceedings of the 2015 10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on Foundations of Software Engineering (ESEC/FSE 2015, Bergamo, Italy, August 31 - September 4)}, editor = {E.~Di~Nitto and M.~Harman and P.~Heymans}, pages = {721-733}, year = {2015}, publisher = {ACM, New York}, isbn = {978-1-4503-3675-8}, doi = {10.1145/2786805.2786867}, url = {}, pdf = {https://www.sosy-lab.org/research/pub/2015-FSE.Witness_Validation_and_Stepwise_Testification_across_Software_Verifiers.pdf}, keyword = {CPAchecker,Ultimate,Software Model Checking,Witness-Based Validation,Witness-Based Validation (main)}, }
56. Dirk Beyer, Stefan Löwe, and Philipp Wendler. Refinement Selection. In B. Fischer and J. Geldenhuys, editors, Proceedings of the 22nd International Symposium on Model Checking of Software (SPIN 2015, Stellenbosch, South Africa, August 24-26), LNCS 9232, pages 20-38, 2015. Springer-Verlag, Heidelberg. doi:10.1007/978-3-319-23404-5_3 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    Abstract

    Counterexample-guided abstraction refinement is a property-directed approach for the automatic construction of an abstract model for a given system. The approach learns information from infeasible error paths in order to refine the abstract model. We address the problem of selecting which information to learn from a given infeasible error path. In previous work, we presented a method that enables refinement selection by extracting a set of sliced prefixes from a given infeasible error path, each of which represents a different reason for infeasibility of the error path and thus, a possible way to refine the abstract model. In this work, we (1) define and investigate several promising heuristics for selecting an appropriate precision for refinement, and (2) propose a new combination of a value analysis and a predicate analysis that does not only find out which information to learn from an infeasible error path, but automatically decides which analysis should be preferred for a refinement. These contributions allow a more systematic refinement strategy for CEGAR-based analyses. We evaluated the idea on software verification. We provide an implementation of the new concepts in the verification framework CPAchecker and make it publicly available. In a thorough experimental study, we show that refinement selection often avoids state-space explosion where existing approaches diverge, and that it can be even more powerful if applied on a higher level, where it decides which analysis of a combination should be favored for a refinement.
    BibTeX Entry

    @inproceedings{SPIN15b, author = {Dirk Beyer and Stefan L{\"o}we and Philipp Wendler}, title = {Refinement Selection}, booktitle = {Proceedings of the 22nd International Symposium on Model Checking of Software (SPIN~2015, Stellenbosch, South Africa, August 24-26)}, editor = {B.~Fischer and J.~Geldenhuys}, pages = {20-38}, year = {2015}, series = {LNCS~9232}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-319-23403-8}, doi = {10.1007/978-3-319-23404-5_3}, url = {https://www.sosy-lab.org/research/cpa-ref-sel/}, pdf = {https://www.sosy-lab.org/research/pub/2015-SPIN.Refinement_Selection.pdf}, abstract = {Counterexample-guided abstraction refinement is a property-directed approach for the automatic construction of an abstract model for a given system. The approach learns information from infeasible error paths in order to refine the abstract model. We address the problem of selecting which information to learn from a given infeasible error path. In previous work, we presented a method that enables refinement selection by extracting a set of sliced prefixes from a given infeasible error path, each of which represents a different reason for infeasibility of the error path and thus, a possible way to refine the abstract model. In this work, we (1) define and investigate several promising heuristics for selecting an appropriate precision for refinement, and (2) propose a new combination of a value analysis and a predicate analysis that does not only find out which information to learn from an infeasible error path, but automatically decides which analysis should be preferred for a refinement. These contributions allow a more systematic refinement strategy for CEGAR-based analyses. We evaluated the idea on software verification. We provide an implementation of the new concepts in the verification framework CPAchecker and make it publicly available. In a thorough experimental study, we show that refinement selection often avoids state-space explosion where existing approaches diverge, and that it can be even more powerful if applied on a higher level, where it decides which analysis of a combination should be favored for a refinement.}, keyword = {CPAchecker,Software Model Checking}, }
57. Dirk Beyer, Matthias Dangl, and Philipp Wendler. Boosting k-Induction with Continuously-Refined Invariants. In D. Kröning and C. S. Pasareanu, editors, Proceedings of the 27th International Conference on Computer Aided Verification (CAV 2015, San Francisco, CA, USA, July 18-24), LNCS 9206, pages 622-640, 2015. Springer-Verlag, Heidelberg. doi:10.1007/978-3-319-21690-4_42 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    Abstract

    k-Induction is a promising technique to extend bounded model checking from falsification to verification. In software verification, k-induction works only if auxiliary invariants are used to strengthen the induction hypothesis. The problem that we address is to generate such invariants (1) automatically without user-interaction, (2) efficiently such that little verification time is spent on the invariant generation, and (3) that are sufficiently strong for a k-induction proof. We boost the k-induction approach to significantly increase effectiveness and efficiency in the following way: We start in parallel to k-induction a data-flow-based invariant generator that supports dynamic precision adjustment and refine the precision of the invariant generator continuously during the analysis, such that the invariants become increasingly stronger. The k-induction engine is extended such that the invariants from the invariant generator are injected in each iteration to strengthen the hypothesis. The new method solves the above-mentioned problem because it (1) automatically chooses an invariant by step-wise refinement, (2) starts always with a lightweight invariant generation that is computationally inexpensive, and (3) refines the invariant precision more and more to inject stronger and stronger invariants into the induction system. We present and evaluate an implementation of our approach, as well as all other existing approaches, in the open-source verification-framework CPAchecker. Our experiments show that combining k-induction with continuously-refined invariants significantly increases effectiveness and efficiency, and outperforms all existing implementations of k-induction-based verification of C programs in terms of successful results.
    BibTeX Entry

    @inproceedings{CAV15, author = {Dirk Beyer and Matthias Dangl and Philipp Wendler}, title = {Boosting k-Induction with Continuously-Refined Invariants}, booktitle = {Proceedings of the 27th International Conference on Computer Aided Verification (CAV~2015, San Francisco, CA, USA, July 18-24)}, editor = {D.~Kr{\"o}ning and C.~S.~Pasareanu}, pages = {622-640}, year = {2015}, series = {LNCS~9206}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-319-21689-8}, doi = {10.1007/978-3-319-21690-4_42}, sha256 = {beb169351523c85e417e028c4e32b47c2c29e5db2e7b29ef8f5a2230e9562216}, url = {https://www.sosy-lab.org/research/cpa-k-induction/}, abstract = {k-Induction is a promising technique to extend bounded model checking from falsification to verification. In software verification, k-induction works only if auxiliary invariants are used to strengthen the induction hypothesis. The problem that we address is to generate such invariants (1) automatically without user-interaction, (2) efficiently such that little verification time is spent on the invariant generation, and (3) that are sufficiently strong for a k-induction proof. We boost the k-induction approach to significantly increase effectiveness and efficiency in the following way: We start in parallel to k-induction a data-flow-based invariant generator that supports dynamic precision adjustment and refine the precision of the invariant generator continuously during the analysis, such that the invariants become increasingly stronger. The k-induction engine is extended such that the invariants from the invariant generator are injected in each iteration to strengthen the hypothesis. The new method solves the above-mentioned problem because it (1) automatically chooses an invariant by step-wise refinement, (2) starts always with a lightweight invariant generation that is computationally inexpensive, and (3) refines the invariant precision more and more to inject stronger and stronger invariants into the induction system. We present and evaluate an implementation of our approach, as well as all other existing approaches, in the open-source verification-framework CPAchecker. Our experiments show that combining k-induction with continuously-refined invariants significantly increases effectiveness and efficiency, and outperforms all existing implementations of k-induction-based verification of C programs in terms of successful results.}, keyword = {CPAchecker,Software Model Checking}, }
58. Dirk Beyer, Stefan Löwe, and Philipp Wendler. Sliced Path Prefixes: An Effective Method to Enable Refinement Selection. In S. Graf and M. Viswanathan, editors, Proceedings of the 35th IFIP WG 6.1 International Conference on Formal Techniques for Distributed Objects, Components, and Systems (FORTE 2015, Grenoble, France, June 2-4), LNCS 9039, pages 228-243, 2015. Springer-Verlag, Heidelberg. doi:10.1007/978-3-319-19195-9_15 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    Abstract

    Automatic software verification relies on constructing, for a given program, an abstract model that is (1) abstract enough to avoid state-space explosion and (2) precise enough to reason about the specification. Counterexample-guided abstraction refinement is a standard technique that suggests to extract information from infeasible error paths, in order to refine the abstract model if it is too imprecise. Existing approaches -including our previous work- do not choose the refinement for a given path systematically. We present a method that generates alternative refinements and allows to systematically choose a suited one. The method takes as input one given infeasible error path and applies a slicing technique to obtain a set of new error paths that are more abstract than the original error path but still infeasible, each for a different reason. The (more abstract) constraints of the new paths can be passed to a standard refinement procedure, in order to obtain a set of possible refinements, one for each new path. Our technique is completely independent from the abstract domain that is used in the program analysis, and does not rely on a certain proof technique, such as SMT solving. We implemented the new algorithm in the verification framework CPAchecker and made our extension publicly available. The experimental evaluation of our technique indicates that there is a wide range of possibilities on how to refine the abstract model for a given error path, and we demonstrate that the choice of which refinement to apply to the abstract model has a significant impact on the verification effectiveness and efficiency.
    BibTeX Entry

    @inproceedings{FORTE15, author = {Dirk Beyer and Stefan L{\"o}we and Philipp Wendler}, title = {Sliced Path Prefixes: An Effective Method to Enable Refinement Selection}, booktitle = {Proceedings of the 35th IFIP WG 6.1 International Conference on Formal Techniques for Distributed Objects, Components, and Systems (FORTE~2015, Grenoble, France, June 2-4)}, editor = {S.~Graf and M.~Viswanathan}, pages = {228-243}, year = {2015}, series = {LNCS~9039}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-319-19194-2}, doi = {10.1007/978-3-319-19195-9_15}, sha256 = {96e16841eb13a602455334a71a516f509ad1b1e2328edade3d5954062b387e7d}, url = {https://www.sosy-lab.org/research/cpa-ref-sel/#FORTE15}, abstract = {Automatic software verification relies on constructing, for a given program, an abstract model that is (1) abstract enough to avoid state-space explosion and (2) precise enough to reason about the specification. Counterexample-guided abstraction refinement is a standard technique that suggests to extract information from infeasible error paths, in order to refine the abstract model if it is too imprecise. Existing approaches ---including our previous work--- do not choose the refinement for a given path systematically. We present a method that generates alternative refinements and allows to systematically choose a suited one. The method takes as input one given infeasible error path and applies a slicing technique to obtain a set of new error paths that are more abstract than the original error path but still infeasible, each for a different reason. The (more abstract) constraints of the new paths can be passed to a standard refinement procedure, in order to obtain a set of possible refinements, one for each new path. Our technique is completely independent from the abstract domain that is used in the program analysis, and does not rely on a certain proof technique, such as SMT solving. We implemented the new algorithm in the verification framework CPAchecker and made our extension publicly available. The experimental evaluation of our technique indicates that there is a wide range of possibilities on how to refine the abstract model for a given error path, and we demonstrate that the choice of which refinement to apply to the abstract model has a significant impact on the verification effectiveness and efficiency.}, keyword = {CPAchecker,Software Model Checking}, }
59. Johannes Bürdek, Malte Lochau, Stefan Bauregger, Andreas Holzer, Alexander von Rhein, Sven Apel, and Dirk Beyer. Facilitating Reuse in Multi-Goal Test-Suite Generation for Software Product Lines. In A. Egyed and I. Schaefer, editors, Proceedings of the 18th International Conference on Fundamental Approaches to Software Engineering (FASE 2015, London, UK, April 13-15), LNCS 9033, pages 84-99, 2015. Springer-Verlag, Heidelberg. doi:10.1007/978-3-662-46675-9_6 Keyword(s): CPAchecker, Software Model Checking, Software Testing Publisher's Version PDF Supplement
    BibTeX Entry

    @inproceedings{FASE15, author = {Johannes B{\"u}rdek and Malte Lochau and Stefan Bauregger and Andreas Holzer and Alexander von Rhein and Sven Apel and Dirk Beyer}, title = {Facilitating Reuse in Multi-Goal Test-Suite Generation for Software Product Lines}, booktitle = {Proceedings of the 18th International Conference on Fundamental Approaches to Software Engineering (FASE~2015, London, UK, April 13-15)}, editor = {A.~Egyed and I.~Schaefer}, pages = {84-99}, year = {2015}, series = {LNCS~9033}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-662-46674-2}, doi = {10.1007/978-3-662-46675-9_6}, sha256 = {fcd4d2f3155e3e061318a444f578c41c5e224a7c76e1bf161fe55cc7ae01ae86}, url = {http://forsyte.at/software/cpatiger/}, keyword = {CPAchecker,Software Model Checking,Software Testing}, }
60. Dirk Beyer and Stefan Löwe. Interpolation for Value Analysis. In U. Aßmann, B. Demuth, T. Spitta, G. Püschel, and R. Kaiser, editors, Tagungsband Software Engineering 2015, Fachtagung des GI-Fachbereichs Softwaretechnik (17. März - 20. März 2015, Dresden, Deutschland), LNI 239, pages 73-74, 2015. Gesellschaft für Informatik (GI). Keyword(s): CPAchecker, Software Model Checking Publisher's Version
    BibTeX Entry

    @inproceedings{SE15-ExplicitCEGAR, author = {Dirk Beyer and Stefan L{\"{o}}we}, title = {Interpolation for Value Analysis}, booktitle = {Tagungsband Software Engineering 2015, Fachtagung des GI-Fachbereichs Softwaretechnik (17. M{\"{a}}rz - 20. M{\"{a}}rz 2015, Dresden, Deutschland)}, editor = {U.~A{\ss}mann and B.~Demuth and T.~Spitta and G.~P{\"{u}}schel and R.~Kaiser}, pages = {73-74}, year = {2015}, series = {{LNI}~239}, publisher = {Gesellschaft f{\"{u}}r Informatik ({GI})}, url = {}, keyword = {CPAchecker,Software Model Checking}, annote = {This is a summary of a <a href="https://www.sosy-lab.org/research/bib/Year/2013.html#FASE13">full article on this topic</a> that appeared in Proc. FASE 2013.}, doinone = {DOI not available}, urlpub = {https://dl.gi.de/handle/20.500.12116/2495}, }
    Additional Infos

    This is a summary of a full article on this topic that appeared in Proc. FASE 2013.
61. Matthias Dangl, Stefan Löwe, and Philipp Wendler. CPAchecker with Support for Recursive Programs and Floating-Point Arithmetic (Competition Contribution). In C. Baier and C. Tinelli, editors, Proceedings of the 21st International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2015, London, UK, April 13-17), LNCS 9035, pages 423-425, 2015. Springer-Verlag, Heidelberg. doi:10.1007/978-3-662-46681-0_34 Keyword(s): CPAchecker, Competition on Software Verification (SV-COMP), Software Model Checking Publisher's Version PDF Supplement
    Abstract

    We submit to SV-COMP'15 the software-verification framework CPAchecker. The submitted configuration is a combination of seven different analyses, based on explicit-value analysis, k-induction, predicate analysis, and concrete memory graphs. These analyses use concepts such as CEGAR, lazy abstraction, interpolation, adjustable-block encoding, bounded model checking, invariant generation, and block-abstraction memoization. Found counterexamples are cross-checked by a bit-precise analysis. The combination of several different analyses copes well with the diversity of the verification tasks in SV-COMP.
    BibTeX Entry

    @inproceedings{CPACHECKER-COMP15, author = {Matthias Dangl and Stefan L{\"{o}}we and Philipp Wendler}, title = {{{\sc CPAchecker}} with Support for Recursive Programs and Floating-Point Arithmetic (Competition Contribution)}, booktitle = {Proceedings of the 21st International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS~2015, London, UK, April 13-17)}, editor = {C.~Baier and C.~Tinelli}, pages = {423--425}, year = {2015}, series = {LNCS~9035}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-662-46680-3}, doi = {10.1007/978-3-662-46681-0_34}, sha256 = {}, url = {https://doi.org/10.1007/978-3-662-46681-0_34}, pdf = {https://www.sosy-lab.org/research/pub/2015-TACAS.CPAchecker_with_Support_for_Recursive_Programs_and_Floating-Point_Arithmetic.pdf}, abstract = {We submit to SV-COMP'15 the software-verification framework CPAchecker. The submitted configuration is a combination of seven different analyses, based on explicit-value analysis, k-induction, predicate analysis, and concrete memory graphs. These analyses use concepts such as CEGAR, lazy abstraction, interpolation, adjustable-block encoding, bounded model checking, invariant generation, and block-abstraction memoization. Found counterexamples are cross-checked by a bit-precise analysis. The combination of several different analyses copes well with the diversity of the verification tasks in SV-COMP.}, keyword = {CPAchecker,Competition on Software Verification (SV-COMP),Software Model Checking}, annote = {Won categories ControlFlow, MemorySafety, and Overall, and received three silver and two bronze medals in <span style="white-space: nowrap"><a href="https://sv-comp.sosy-lab.org/2015/">SV-COMP'15</a></span>}, }
    Additional Infos

    Won categories ControlFlow, MemorySafety, and Overall, and received three silver and two bronze medals in SV-COMP'15
62. Dirk Beyer, Georg Dresler, and Philipp Wendler. Software Verification in the Google App-Engine Cloud. In A. Biere and R. Bloem, editors, Proceedings of the 26th International Conference on Computer-Aided Verification (CAV 2014, Vienna, Austria, July 18-22), LNCS 8559, pages 327-333, 2014. Springer-Verlag, Heidelberg. doi:10.1007/978-3-319-08867-9_21 Keyword(s): CPAchecker, Software Model Checking, Cloud-Based Software Verification Publisher's Version PDF Supplement
    Abstract

    Software verification often requires a large amount of computing resources. In the last years, cloud services emerged as an inexpensive, flexible, and energy-efficient source of computing power. We have investigated if such cloud resources can be used effectively for verification. We chose the platform-as-a-service offer Google App Engine and ported the open-source verification framework CPAchecker to it. We provide our new verification service as a web front-end to users who wish to solve single verification tasks (tutorial usage), and an API for integrating the service into existing verification infrastructures (massively parallel bulk usage). We experimentally evaluate the effectiveness of this service and show that it can be successfully used to offload verification work to the cloud, considerably sparing local verification resources.
    BibTeX Entry

    @inproceedings{CAV14, author = {Dirk Beyer and Georg Dresler and Philipp Wendler}, title = {Software Verification in the {Google} {App-Engine} Cloud}, booktitle = {Proceedings of the 26th International Conference on Computer-Aided Verification (CAV~2014, Vienna, Austria, July 18-22)}, editor = {A.~Biere and R.~Bloem}, pages = {327-333}, year = {2014}, series = {LNCS~8559}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-319-08866-2}, doi = {10.1007/978-3-319-08867-9_21}, sha256 = {f92060721e703c8553d5420c34f07eea24fe25d36ae9c02217688606e1898704}, url = {http://www.sosy-lab.org/~dbeyer/cpa-appengine}, abstract = {Software verification often requires a large amount of computing resources. In the last years, cloud services emerged as an inexpensive, flexible, and energy-efficient source of computing power. We have investigated if such cloud resources can be used effectively for verification. We chose the platform-as-a-service offer Google App Engine and ported the open-source verification framework CPAchecker to it. We provide our new verification service as a web front-end to users who wish to solve single verification tasks (tutorial usage), and an API for integrating the service into existing verification infrastructures (massively parallel bulk usage). We experimentally evaluate the effectiveness of this service and show that it can be successfully used to offload verification work to the cloud, considerably sparing local verification resources.}, keyword = {CPAchecker,Software Model Checking,Cloud-Based Software Verification}, }
63. Dirk Beyer, Andreas Holzer, Michael Tautschnig, and Helmut Veith. Reusing Information in Multi-Goal Reachability Analyses. In W. Hasselbring and N. C. Ehmke, editors, Tagungsband Software Engineering 2014, Fachtagung des GI-Fachbereichs Softwaretechnik (25. Februar - 28. Februar 2014, Kiel, Deutschland), LNI 227, pages 97-98, 2014. Gesellschaft für Informatik (GI). Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF
    BibTeX Entry

    @inproceedings{SE14-MultiGoal, author = {Dirk Beyer and Andreas Holzer and Michael Tautschnig and Helmut Veith}, title = {Reusing Information in Multi-Goal Reachability Analyses}, booktitle = {Tagungsband Software Engineering 2014, Fachtagung des GI-Fachbereichs Softwaretechnik (25. Februar - 28. Februar 2014, Kiel, Deutschland)}, editor = {W.~Hasselbring and N.~C.~Ehmke}, pages = {97--98}, year = {2014}, series = {{LNI}~227}, publisher = {Gesellschaft f{\"{u}}r Informatik ({GI})}, pdf = {https://dl.gi.de/bitstream/handle/20.500.12116/30979/097.pdf?sequence=1&isAllowed=y}, keyword = {CPAchecker,Software Model Checking}, annote = {This is a summary of a <a href="https://www.sosy-lab.org/research/bib/Year/2013.html#ESOP13">full article on this topic</a> that appeared in Proc. ESOP 2013.}, doinone = {DOI not available}, urlpub = {https://dl.gi.de/handle/20.500.12116/30979}, }
    Additional Infos

    This is a summary of a full article on this topic that appeared in Proc. ESOP 2013.
64. Dirk Beyer, Stefan Löwe, Evgeny Novikov, Andreas Stahlbauer, and Philipp Wendler. Precision Reuse in CPAchecker. In W. Hasselbring and N. C. Ehmke, editors, Tagungsband Software Engineering 2014, Fachtagung des GI-Fachbereichs Softwaretechnik (25. Februar - 28. Februar 2014, Kiel, Deutschland), LNI 227, pages 41-42, 2014. Gesellschaft für Informatik (GI). Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF
    Abstract

    Continuous testing during development is a well-established technique for software-quality assurance. Continuous model checking from revision to revision is not yet established as a standard practice, because the enormous resource consumption makes its application impractical. Model checkers compute a large number of verification facts that are necessary for verifying if a given specification holds. We have identified a category of such intermediate results that are easy to store and efficient to reuse: abstraction precisions. The precision of an abstract domain specifies the level of abstraction that the analysis works on. Precisions are thus a precious result of the verification effort and it is a waste of resources to throw them away after each verification run. In particular, precisions are reasonably small and thus easy to store; they are easy to process and have a large impact on resource consumption. We experimentally show the impact of precision reuse on industrial verification problems created from 62 Linux kernel device drivers with 1119 revisions.
    BibTeX Entry

    @inproceedings{SE14-Reuse, author = {Dirk Beyer and Stefan L{\"{o}}we and Evgeny Novikov and Andreas Stahlbauer and Philipp Wendler}, title = {Precision Reuse in CPAchecker}, booktitle = {Tagungsband Software Engineering 2014, Fachtagung des GI-Fachbereichs Softwaretechnik (25. Februar - 28. Februar 2014, Kiel, Deutschland)}, editor = {W.~Hasselbring and N.~C.~Ehmke}, pages = {41--42}, year = {2014}, series = {{LNI}~227}, publisher = {Gesellschaft f{\"{u}}r Informatik ({GI})}, pdf = {https://dl.gi.de/bitstream/handle/20.500.12116/30949/041.pdf?sequence=1&isAllowed=y}, abstract = {Continuous testing during development is a well-established technique for software-quality assurance. Continuous model checking from revision to revision is not yet established as a standard practice, because the enormous resource consumption makes its application impractical. Model checkers compute a large number of verification facts that are necessary for verifying if a given specification holds. We have identified a category of such intermediate results that are easy to store and efficient to reuse: abstraction precisions. The precision of an abstract domain specifies the level of abstraction that the analysis works on. Precisions are thus a precious result of the verification effort and it is a waste of resources to throw them away after each verification run. In particular, precisions are reasonably small and thus easy to store; they are easy to process and have a large impact on resource consumption. We experimentally show the impact of precision reuse on industrial verification problems created from 62 Linux kernel device drivers with 1119 revisions.}, keyword = {CPAchecker,Software Model Checking}, annote = {This is a summary of a <a href="https://www.sosy-lab.org/research/bib/Year/2013.html#FSE13">full article on this topic</a> that appeared in Proc. ESEC/FSE 2013.}, doinone = {DOI not available}, urlpub = {https://dl.gi.de/handle/20.500.12116/30949}, }
    Additional Infos

    This is a summary of a full article on this topic that appeared in Proc. ESEC/FSE 2013.
65. Stefan Löwe, Mikhail U. Mandrykin, and Philipp Wendler. CPAchecker with Sequential Combination of Explicit-Value Analyses and Predicate Analyses (Competition Contribution). In E. Abraham and K. Havelund, editors, Proceedings of the 20th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2014, Grenoble, France, April 5-13), LNCS 8413, pages 392-394, 2014. Springer-Verlag, Heidelberg. doi:10.1007/978-3-642-54862-8_27 Keyword(s): CPAchecker, Competition on Software Verification (SV-COMP), Software Model Checking Publisher's Version PDF Supplement
    Abstract

    CPAchecker is a framework for software verification, built on the foundations of configurable program analysis (CPA). For the SV-COMP'14, we file a CPAchecker configuration that runs up to five analyses in sequence. The first two analyses of our approach utilize the explicit-value domain for modeling the state space, while the remaining analyses are based on predicate abstraction. In addition to that, a bit-precise counterexample checker comes into action whenever an analysis finds a counterexample. The combination of conceptually different analyses is key to the success of our verification approach, as the diversity of verification tasks is taken into account.
    BibTeX Entry

    @inproceedings{CPACHECKER-COMP14, author = {Stefan~L{\"{o}}we and Mikhail~U.~Mandrykin and Philipp~Wendler}, title = {{{\sc CPAchecker}} with Sequential Combination of Explicit-Value Analyses and Predicate Analyses (Competition Contribution)}, booktitle = {Proceedings of the 20th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS~2014, Grenoble, France, April 5-13)}, editor = {E.~Abraham and K. Havelund}, pages = {392-394}, year = {2014}, series = {LNCS~8413}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-642-54861-1}, doi = {10.1007/978-3-642-54862-8_27}, sha256 = {}, url = {https://doi.org/10.1007/978-3-642-54862-8_27}, pdf = {https://www.sosy-lab.org/research/pub/2014-TACAS.CPAchecker_with_Sequential_Combination_of_Explicit-Value_Analyses_and_Predicate_Analyses.pdf}, abstract = {CPAchecker is a framework for software verification, built on the foundations of configurable program analysis (CPA). For the SV-COMP'14, we file a CPAchecker configuration that runs up to five analyses in sequence. The first two analyses of our approach utilize the explicit-value domain for modeling the state space, while the remaining analyses are based on predicate abstraction. In addition to that, a bit-precise counterexample checker comes into action whenever an analysis finds a counterexample. The combination of conceptually different analyses is key to the success of our verification approach, as the diversity of verification tasks is taken into account.}, keyword = {CPAchecker,Competition on Software Verification (SV-COMP),Software Model Checking}, annote = {Won categories ControlFlow, MemorySafety, and Simple, and received one silver and one bronze medal in <span style="white-space: nowrap"><a href="https://sv-comp.sosy-lab.org/2014/">SV-COMP'14</a></span>}, }
    Additional Infos

    Won categories ControlFlow, MemorySafety, and Simple, and received one silver and one bronze medal in SV-COMP'14
66. Sven Apel, Dirk Beyer, Karlheinz Friedberger, Franco Raimondi, and Alexander von Rhein. Domain Types: Abstract-Domain Selection Based on Variable Usage. In V. Bertacco and A. Legay, editors, Proceedings of the 9th Haifa Verification Conference (HVC 2013, Haifa, Israel, November 5-7), LNCS 8244, pages 262-278, 2013. Springer-Verlag, Heidelberg. doi:10.1007/978-3-319-03077-7_18 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    Abstract

    The success of software model checking depends on finding an appropriate abstraction of the program to verify. The choice of the abstract domain and the analysis configuration is currently left to the user, who may not be familiar with the tradeoffs and performance details of the available abstract domains. We introduce the concept of domain types, which classify the program variables into types that are more fine-grained than standard declared types (e.g., 'int' and 'long') to guide the selection of an appropriate abstract domain for a model checker. Our implementation on top of an existing verification framework determines the domain type for each variable in a pre-analysis step, based on the usage of variables in the program, and then assigns each variable to an abstract domain. Based on a series of experiments on a comprehensive set of verification tasks from international verification competitions, we demonstrate that the choice of the abstract domain per variable (we consider one explicit and one symbolic domain) can substantially improve the verification in terms of performance and precision.
    BibTeX Entry

    @inproceedings{HVC13, author = {Sven Apel and Dirk Beyer and Karlheinz Friedberger and Franco Raimondi and Alexander von Rhein}, title = {Domain Types: Abstract-Domain Selection Based on Variable Usage}, booktitle = {Proceedings of the 9th Haifa Verification Conference (HVC 2013, Haifa, Israel, November 5-7)}, editor = {V.~Bertacco and A.~Legay}, pages = {262-278}, year = {2013}, series = {LNCS~8244}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-319-03076-0}, doi = {10.1007/978-3-319-03077-7_18}, url = {https://www.sosy-lab.org/research/domaintypes/}, pdf = {https://www.sosy-lab.org/research/pub/2013-HVC.Domain_Types_Abstract-Domain_Selection_Based_on_Variable_Usage.pdf}, abstract = {The success of software model checking depends on finding an appropriate abstraction of the program to verify. The choice of the abstract domain and the analysis configuration is currently left to the user, who may not be familiar with the tradeoffs and performance details of the available abstract domains. We introduce the concept of domain types, which classify the program variables into types that are more fine-grained than standard declared types (e.g., `int' and `long') to guide the selection of an appropriate abstract domain for a model checker. Our implementation on top of an existing verification framework determines the domain type for each variable in a pre-analysis step, based on the usage of variables in the program, and then assigns each variable to an abstract domain. Based on a series of experiments on a comprehensive set of verification tasks from international verification competitions, we demonstrate that the choice of the abstract domain per variable (we consider one explicit and one symbolic domain) can substantially improve the verification in terms of performance and precision.}, keyword = {CPAchecker,Software Model Checking}, }
67. Dirk Beyer, Stefan Löwe, Evgeny Novikov, Andreas Stahlbauer, and Philipp Wendler. Precision Reuse for Efficient Regression Verification. In B. Meyer, L. Baresi, and M. Mezini, editors, Proceedings of the 9th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on Foundations of Software Engineering (ESEC/FSE 2013, St. Petersburg, Russia, August 18-26), pages 389-399, 2013. ACM. doi:10.1145/2491411.2491429 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    Abstract

    Continuous testing during development is a well-established technique for software-quality assurance. Continuous model checking from revision to revision is not yet established as a standard practice, because the enormous resource consumption makes its application impractical. Model checkers compute a large number of verification facts that are necessary for verifying if a given specification holds. We have identified a category of such intermediate results that are easy to store and efficient to reuse: abstraction precisions. The precision of an abstract domain specifies the level of abstraction that the analysis works on. Precisions are thus a precious result of the verification effort and it is a waste of resources to throw them away after each verification run. In particular, precisions are reasonably small and thus easy to store; they are easy to process and have a large impact on resource consumption. We experimentally show the impact of precision reuse on industrial verification problems created from 62 Linux kernel device drivers with 1119 revisions.
    BibTeX Entry

    @inproceedings{FSE13, author = {Dirk Beyer and Stefan L{\"o}we and Evgeny Novikov and Andreas Stahlbauer and Philipp Wendler}, title = {Precision Reuse for Efficient Regression Verification}, booktitle = {Proceedings of the 9th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on Foundations of Software Engineering (ESEC/FSE 2013, St. Petersburg, Russia, August 18-26)}, editor = {B.~Meyer and L.~Baresi and M.~Mezini}, pages = {389-399}, year = {2013}, publisher = {ACM}, isbn = {}, doi = {10.1145/2491411.2491429}, url = {https://www.sosy-lab.org/research/cpa-reuse/}, pdf = {https://www.sosy-lab.org/research/pub/2013-FSE.Precision_Reuse_for_Efficient_Regression_Verification.pdf}, abstract = {Continuous testing during development is a well-established technique for software-quality assurance. Continuous model checking from revision to revision is not yet established as a standard practice, because the enormous resource consumption makes its application impractical. Model checkers compute a large number of verification facts that are necessary for verifying if a given specification holds. We have identified a category of such intermediate results that are easy to store and efficient to reuse: abstraction precisions. The precision of an abstract domain specifies the level of abstraction that the analysis works on. Precisions are thus a precious result of the verification effort and it is a waste of resources to throw them away after each verification run. In particular, precisions are reasonably small and thus easy to store; they are easy to process and have a large impact on resource consumption. We experimentally show the impact of precision reuse on industrial verification problems created from 62 Linux kernel device drivers with 1119 revisions.}, keyword = {CPAchecker,Software Model Checking}, }
68. Dirk Beyer, Andreas Holzer, Michael Tautschnig, and Helmut Veith. Information Reuse for Multi-goal Reachability Analyses. In M. Felleisen and P. Gardner, editors, Proceedings of the 22nd European Symposium on Programming (ESOP 2013, Rome, Italy, March 19-22), LNCS 7792, pages 472-491, 2013. Springer-Verlag, Heidelberg. doi:10.1007/978-3-642-37036-6_26 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Presentation
    Abstract

    It is known that model checkers can generate test inputs as witnesses for reachability specifications (or, equivalently, as counterexamples for safety properties). While this use of model checkers for testing yields a theoretically sound test-generation procedure, it scales poorly for computing complex test suites for large sets of test goals, because each test goal requires an expensive run of the model checker. We represent test goals as automata and exploit relations between automata in order to reuse existing reachability information for the analysis of subsequent test goals. Exploiting the sharing of sub-automata in a series of reachability queries, we achieve considerable performance improvements over the standard approach. We show the practical use of our multi-goal reachability analysis in a predicate-abstraction-based test-input generator for the test-specification language FQL.
    BibTeX Entry

    @inproceedings{ESOP13, author = {Dirk Beyer and Andreas Holzer and Michael Tautschnig and Helmut Veith}, title = {Information Reuse for Multi-goal Reachability Analyses}, booktitle = {Proceedings of the 22nd European Symposium on Programming (ESOP~2013, Rome, Italy, March 19-22)}, editor = {M.~Felleisen and P.~Gardner}, pages = {472-491}, year = {2013}, series = {LNCS~7792}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-642-37035-9}, doi = {10.1007/978-3-642-37036-6_26}, sha256 = {9112a1c10c81e5aa3948a3a66bfd5ae1ab0d3c08186a67329fcf3efbb7f4d406}, url = {}, presentation = {https://www.sosy-lab.org/research/prs/2013-03-21_ESOP13_InformationReuse_Andreas.pdf}, abstract = {It is known that model checkers can generate test inputs as witnesses for reachability specifications (or, equivalently, as counterexamples for safety properties). While this use of model checkers for testing yields a theoretically sound test-generation procedure, it scales poorly for computing complex test suites for large sets of test goals, because each test goal requires an expensive run of the model checker. We represent test goals as automata and exploit relations between automata in order to reuse existing reachability information for the analysis of subsequent test goals. Exploiting the sharing of sub-automata in a series of reachability queries, we achieve considerable performance improvements over the standard approach. We show the practical use of our multi-goal reachability analysis in a predicate-abstraction-based test-input generator for the test-specification language FQL.}, keyword = {CPAchecker,Software Model Checking}, }
69. Dirk Beyer and Stefan Löwe. Explicit-State Software Model Checking Based on CEGAR and Interpolation. In V. Cortellessa and D. Varro, editors, Proceedings of the 16th International Conference on Fundamental Approaches to Software Engineering (FASE 2013, Rome, Italy, March 20-22), LNCS 7793, pages 146-162, 2013. Springer-Verlag, Heidelberg. doi:10.1007/978-3-642-37057-1_11 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF
    Abstract

    Abstraction, counterexample-guided refinement, and interpolation are techniques that are essential to the success of predicate-based program analysis. These techniques have not yet been applied together to explicit-value program analysis. We present an approach that integrates abstraction and interpolation-based refinement into an explicit-value analysis, i.e., a program analysis that tracks explicit values for a specified set of variables (the precision). The algorithm uses an abstract reachability graph as central data structure and a path-sensitive dynamic approach for precision adjustment. We evaluate our algorithm on the benchmark set of the Competition on Software Verification 2012 (SV-COMP'12) to show that our new approach is highly competitive. We also show that combining our new approach with an auxiliary predicate analysis scores significantly higher than the SV-COMP'12 winner.
    BibTeX Entry

    @inproceedings{FASE13, author = {Dirk Beyer and Stefan L{\"o}we}, title = {Explicit-State Software Model Checking Based on {CEGAR} and Interpolation}, booktitle = {Proceedings of the 16th International Conference on Fundamental Approaches to Software Engineering (FASE~2013, Rome, Italy, March 20-22)}, editor = {V.~Cortellessa and D.~Varro}, pages = {146-162}, year = {2013}, series = {LNCS~7793}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-642-37056-4}, doi = {10.1007/978-3-642-37057-1_11}, sha256 = {3e2ba52da100fd835736b3673fa47a3429522dd3f4c0834b13f29d6a68a8bd45}, url = {}, abstract = {Abstraction, counterexample-guided refinement, and interpolation are techniques that are essential to the success of predicate-based program analysis. These techniques have not yet been applied together to explicit-value program analysis. We present an approach that integrates abstraction and interpolation-based refinement into an explicit-value analysis, i.e., a program analysis that tracks explicit values for a specified set of variables (the precision). The algorithm uses an abstract reachability graph as central data structure and a path-sensitive dynamic approach for precision adjustment. We evaluate our algorithm on the benchmark set of the Competition on Software Verification 2012 (SV-COMP'12) to show that our new approach is highly competitive. We also show that combining our new approach with an auxiliary predicate analysis scores significantly higher than the SV-COMP'12 winner.}, keyword = {CPAchecker,Software Model Checking}, }
70. Dirk Beyer and Andreas Stahlbauer. BDD-Based Software Model Checking with CPAchecker. In A. Kucera et al., editors, Proceedings of the Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2012, Znojmo, Czech Republic, October 26-28), LNCS 7721, pages 1-11, 2013. Springer-Verlag, Heidelberg. doi:10.1007/978-3-642-36046-6_1 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF
    BibTeX Entry

    @inproceedings{MEMICS12, author = {Dirk Beyer and Andreas Stahlbauer}, title = {{BDD}-Based Software Model Checking with {{\sc CPAchecker}}}, booktitle = {Proceedings of the Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS~2012, Znojmo, Czech Republic, October 26-28)}, editor = {A.~Kucera~et~al.}, pages = {1-11}, year = {2013}, series = {LNCS~7721}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-642-36044-2}, doi = {10.1007/978-3-642-36046-6_1}, url = {}, pdf = {https://www.sosy-lab.org/research/pub/2013-MEMICS.BDD-Based_Software_Model_Checking_with_CPAchecker.pdf}, keyword = {CPAchecker,Software Model Checking}, }
71. Philipp Wendler. CPAchecker with Sequential Combination of Explicit-State Analysis and Predicate Analysis (Competition Contribution). In N. Piterman and S. Smolka, editors, Proceedings of the 19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2013, Rome, Italy, March 16-24), LNCS 7795, pages 613-615, 2013. Springer-Verlag, Heidelberg. doi:10.1007/978-3-642-36742-7_45 Keyword(s): CPAchecker, Competition on Software Verification (SV-COMP), Software Model Checking Publisher's Version PDF Supplement
    Abstract

    CPAchecker is an open-source framework for software verification, based on the concepts of configurable program analysis (CPA). We submit a CPAchecker configuration that uses a sequential combination of two approaches. It starts with an explicit-state analysis, and, if no answer can be found within some time, switches to a predicate analysis with adjustable-block encoding and CEGAR.
    BibTeX Entry

    @inproceedings{CPACHECKERSEQCOM-COMP13, author = {Philipp Wendler}, title = {{{\sc CPAchecker}} with Sequential Combination of Explicit-State Analysis and Predicate Analysis (Competition Contribution)}, booktitle = {Proceedings of the 19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS~2013, Rome, Italy, March 16-24)}, editor = {N.~Piterman and S.~Smolka}, pages = {613-615}, year = {2013}, series = {LNCS~7795}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-642-36741-0}, doi = {10.1007/978-3-642-36742-7_45}, sha256 = {}, url = {https://doi.org/10.1007/978-3-642-36742-7_45}, pdf = {https://www.sosy-lab.org/research/pub/2013-TACAS.CPAchecker_with_Sequential_Combination_of_Explicit-State_Analysis_and_Predicate_Analysis.pdf}, abstract = {CPAchecker is an open-source framework for software verification, based on the concepts of configurable program analysis (CPA). We submit a CPAchecker configuration that uses a sequential combination of two approaches. It starts with an explicit-state analysis, and, if no answer can be found within some time, switches to a predicate analysis with adjustable-block encoding and CEGAR.}, keyword = {CPAchecker,Competition on Software Verification (SV-COMP),Software Model Checking}, annote = {Won category Overall and received five bronze medals in <span style="white-space: nowrap"><a href="https://sv-comp.sosy-lab.org/2013/">SV-COMP'13</a></span>}, }
    Additional Infos

    Won category Overall and received five bronze medals in SV-COMP'13
72. Stefan Löwe. CPAchecker with Explicit-Value Analysis Based on CEGAR and Interpolation (Competition Contribution). In N. Piterman and S. Smolka, editors, Proceedings of the 19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2013, Rome, Italy, March 16-24), LNCS 7795, pages 610-612, 2013. Springer. doi:10.1007/978-3-642-36742-7_44 Keyword(s): CPAchecker, Competition on Software Verification (SV-COMP), Software Model Checking Publisher's Version PDF Supplement
    BibTeX Entry

    @inproceedings{CPACHECKEREXPLICIT-COMP13, author = {Stefan L{\"{o}}we}, title = {{{\sc CPAchecker}} with Explicit-Value Analysis Based on {CEGAR} and Interpolation (Competition Contribution)}, booktitle = {Proceedings of the 19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS~2013, Rome, Italy, March 16-24)}, editor = {N.~Piterman and S.~Smolka}, pages = {610-612}, year = {2013}, series = {LNCS~7795}, publisher = {Springer}, isbn = {978-3-642-36741-0}, doi = {10.1007/978-3-642-36742-7_44}, sha256 = {}, url = {https://doi.org/10.1007/978-3-642-36742-7_44}, keyword = {CPAchecker,Competition on Software Verification (SV-COMP),Software Model Checking}, annote = {Received four silver medals in <span style="white-space: nowrap"><a href="https://sv-comp.sosy-lab.org/2013/">SV-COMP'13</a></span>}, }
    Additional Infos

    Received four silver medals in SV-COMP'13
73. Dirk Beyer, Thomas A. Henzinger, M. Erkan Keremoglu, and Philipp Wendler. Conditional Model Checking: A Technique to Pass Information between Verifiers. In Tevfik Bultan and Martin Robillard, editors, Proceedings of the 20th ACM SIGSOFT International Symposium on the Foundations of Software Engineering (FSE 2012, Cary, NC, November 10-17), 2012. ACM. doi:10.1145/2393596.2393664 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    Abstract

    Software model checking, as an undecidable problem, has three possible outcomes: (1) the program satisfies the specification, (2) the program does not satisfy the specification, and (3) the model checker fails. The third outcome usually manifests itself in a space-out, time-out, or one component of the verification tool giving up; in all of these failing cases, significant computation is performed by the verification tool before the failure, but no result is reported. We propose to reformulate the model-checking problem as follows, in order to have the verification tool report a summary of the performed work even in case of failure: given a program and a specification, the model checker returns a condition P -usually a state predicate- such that the program satisfies the specification under the condition P -that is, as long as the program does not leave the states in which P is satisfied. In our experiments, we investigated as one major application of conditional model checking the sequential combination of model checkers with information passing. We give the condition that one model checker produces, as input to a second conditional model checker, such that the verification problem for the second is restricted to the part of the state space that is not covered by the condition, i.e., the second model checker works on the problems that the first model checker could not solve. Our experiments demonstrate that repeated application of conditional model checkers, passing information from one model checker to the next, can significantly improve the verification results and performance, i.e., we can now verify programs that we could not verify before.
    BibTeX Entry

    @inproceedings{FSE12, author = {Dirk Beyer and Thomas A. Henzinger and M. Erkan Keremoglu and Philipp Wendler}, title = {Conditional Model Checking: {A} Technique to Pass Information between Verifiers}, booktitle = {Proceedings of the 20th ACM SIGSOFT International Symposium on the Foundations of Software Engineering (FSE~2012, Cary, NC, November 10-17)}, editor = {Tevfik Bultan and Martin Robillard}, pages = {}, year = {2012}, publisher = {ACM}, isbn = {978-1-4503-1614-9}, doi = {10.1145/2393596.2393664}, url = {https://www.sosy-lab.org/research/cpa-cmc/}, pdf = {https://www.sosy-lab.org/research/pub/2012-FSE.Conditional_Model_Checking.pdf}, abstract = {Software model checking, as an undecidable problem, has three possible outcomes: (1) the program satisfies the specification, (2) the program does not satisfy the specification, and (3) the model checker fails. The third outcome usually manifests itself in a space-out, time-out, or one component of the verification tool giving up; in all of these failing cases, significant computation is performed by the verification tool before the failure, but no result is reported. We propose to reformulate the model-checking problem as follows, in order to have the verification tool report a summary of the performed work even in case of failure: given a program and a specification, the model checker returns a condition P ---usually a state predicate--- such that the program satisfies the specification under the condition P ---that is, as long as the program does not leave the states in which P is satisfied. In our experiments, we investigated as one major application of conditional model checking the sequential combination of model checkers with information passing. We give the condition that one model checker produces, as input to a second conditional model checker, such that the verification problem for the second is restricted to the part of the state space that is not covered by the condition, i.e., the second model checker works on the problems that the first model checker could not solve. Our experiments demonstrate that repeated application of conditional model checkers, passing information from one model checker to the next, can significantly improve the verification results and performance, i.e., we can now verify programs that we could not verify before.}, keyword = {CPAchecker,Software Model Checking}, }
74. Dirk Beyer and Philipp Wendler. Algorithms for Software Model Checking: Predicate Abstraction vs. IMPACT. In Gianpiero Cabodi and Satnam Singh, editors, Proceedings of the 12th International Conference on Formal Methods in Computer-Aided Design (FMCAD 2012, Cambrige, UK, October 22-25), pages 106-113, 2012. FMCAD. Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    Abstract

    CEGAR, SMT solving, and Craig interpolation are successful approaches for software model checking. We compare two of the most important algorithms that are based on these techniques: lazy predicate abstraction (as in BLAST) and lazy abstraction with interpolants (as in IMPACT). We unify the algorithms formally (by expressing both in the CPA framework) as well as in practice (by implementing them in the same tool). This allows us to flexibly experiment with new configurations and gain new insights, both about their most important differences and commonalities, as well as about their performance characteristics. We show that the essential contribution of the IMPACT algorithm is the reduction of the number of refinements, and compare this to another approach for reducing refinement effort: adjustable-block encoding (ABE).
    BibTeX Entry

    @inproceedings{FMCAD12, author = {Dirk Beyer and Philipp Wendler}, title = {Algorithms for Software Model Checking: Predicate Abstraction vs. {IMPACT}}, booktitle = {Proceedings of the 12th International Conference on Formal Methods in Computer-Aided Design (FMCAD~2012, Cambrige, UK, October 22-25)}, editor = {Gianpiero Cabodi and Satnam Singh}, pages = {106-113}, year = {2012}, publisher = {FMCAD}, isbn = {978-1-4673-4831-7}, url = {https://www.sosy-lab.org/research/cpa-uni/}, pdf = {https://www.sosy-lab.org/research/pub/2012-FMCAD.Algorithms_for_Software_Model_Checking.pdf}, abstract = {CEGAR, SMT solving, and Craig interpolation are successful approaches for software model checking. We compare two of the most important algorithms that are based on these techniques: lazy predicate abstraction (as in BLAST) and lazy abstraction with interpolants (as in IMPACT). We unify the algorithms formally (by expressing both in the CPA framework) as well as in practice (by implementing them in the same tool). This allows us to flexibly experiment with new configurations and gain new insights, both about their most important differences and commonalities, as well as about their performance characteristics. We show that the essential contribution of the IMPACT algorithm is the reduction of the number of refinements, and compare this to another approach for reducing refinement effort: adjustable-block encoding (ABE).}, keyword = {CPAchecker,Software Model Checking}, doinone = {DOI not available}, urlpub = {https://ieeexplore.ieee.org/document/6462562/}, }
75. Stefan Löwe and Philipp Wendler. CPAchecker with Adjustable Predicate Analysis (Competition Contribution). In C. Flanagan and B. König, editors, Proceedings of the 18th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2012, Tallinn, Estonia, March 27-30), LNCS 7214, pages 528-530, 2012. Springer-Verlag, Heidelberg. doi:10.1007/978-3-642-28756-5_40 Keyword(s): CPAchecker, Competition on Software Verification (SV-COMP), Software Model Checking Publisher's Version PDF Supplement
    Abstract

    CPAchecker is a freely available software-verification framework, built on the concepts of configurable program analysis (CPA). CPAchecker integrates most of the state-of-the-art technologies for software model checking, such as counterexample-guided abstraction refinement (CEGAR), lazy predicate abstraction, interpolation-based refinement, and large-block encoding. The CPA for predicate analysis with adjustable-block encoding (ABE) is very promising in many categories, and thus, we submit a CPAchecker configuration that uses this analysis approach to the competition.
    BibTeX Entry

    @inproceedings{CPACHECKERABE-COMP12, author = {Stefan L{\"{o}}we and Philipp Wendler}, title = {{{\sc CPAchecker}} with Adjustable Predicate Analysis (Competition Contribution)}, booktitle = {Proceedings of the 18th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS~2012, Tallinn, Estonia, March 27-30)}, editor = {C.~Flanagan and B.~K{\"o}nig}, pages = {528--530}, year = {2012}, series = {LNCS~7214}, publisher = {Springer-Verlag, Heidelberg}, doi = {10.1007/978-3-642-28756-5_40}, sha256 = {}, url = {https://doi.org/10.1007/978-3-642-28756-5_40}, pdf = {https://www.sosy-lab.org/research/pub/2012-TACAS.CPAchecker_with_Adjustable_Predicate_Analysis.pdf}, abstract = {CPAchecker is a freely available software-verification framework, built on the concepts of configurable program analysis (CPA). CPAchecker integrates most of the state-of-the-art technologies for software model checking, such as counterexample-guided abstraction refinement (CEGAR), lazy predicate abstraction, interpolation-based refinement, and large-block encoding. The CPA for predicate analysis with adjustable-block encoding (ABE) is very promising in many categories, and thus, we submit a CPAchecker configuration that uses this analysis approach to the competition.}, keyword = {CPAchecker,Competition on Software Verification (SV-COMP),Software Model Checking}, annote = {Won category ControlFlowInteger and received one silver and two bronze medals in <span style="white-space: nowrap"><a href="https://sv-comp.sosy-lab.org/2012/">SV-COMP'12</a></span>}, }
    Additional Infos

    Won category ControlFlowInteger and received one silver and two bronze medals in SV-COMP'12
76. Dirk Beyer and M. Erkan Keremoglu. CPAchecker: A Tool for Configurable Software Verification. In G. Gopalakrishnan and S. Qadeer, editors, Proceedings of the 23rd International Conference on Computer Aided Verification (CAV 2011, Snowbird, UT, July 14-20), LNCS 6806, pages 184-190, 2011. Springer-Verlag, Heidelberg. doi:10.1007/978-3-642-22110-1_16 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    Abstract

    Configurable software verification is a recent concept for expressing different program analysis and model checking approaches in one single formalism. This paper presents CPAchecker, a tool and framework that aims at easy integration of new verification components. Every abstract domain, together with the corresponding operations, implements the interface of configurable program analysis (CPA). The main algorithm is configurable to perform a reachability analysis on arbitrary combinations of existing CPAs. In software verification, it takes a considerable amount of effort to convert a verification idea into actual experimental results - we aim at accelerating this process. We hope that researchers find it convenient and productive to implement new verification ideas and algorithms using this flexible and easy-to-extend platform, and that it advances the field by making it easier to perform practical experiments. The tool is implemented in Java and runs as command-line tool or as Eclipse plug-in. CPAchecker implements CPAs for several abstract domains. We evaluate the efficiency of the current version of our tool on software-verification benchmarks from the literature, and compare it with other state-of-the-art model checkers. CPAchecker is an open-source toolkit and publicly available.
    BibTeX Entry

    @inproceedings{CAV11, author = {Dirk Beyer and M. Erkan Keremoglu}, title = {{{\sc CPAchecker}}: A Tool for Configurable Software Verification}, booktitle = {Proceedings of the 23rd International Conference on Computer Aided Verification (CAV~2011, Snowbird, UT, July 14-20)}, editor = {G.~Gopalakrishnan and S.~Qadeer}, pages = {184-190}, year = {2011}, series = {LNCS~6806}, publisher = {Springer-Verlag, Heidelberg}, isbn = {978-3-642-22109-5}, doi = {10.1007/978-3-642-22110-1_16}, sha256 = {0b9016de32b714f799da2cf19d3bf8f96cc33069db70beb2e22bbca07c58e2ee}, url = {https://cpachecker.sosy-lab.org}, abstract = {Configurable software verification is a recent concept for expressing different program analysis and model checking approaches in one single formalism. This paper presents CPAchecker, a tool and framework that aims at easy integration of new verification components. Every abstract domain, together with the corresponding operations, implements the interface of configurable program analysis (CPA). The main algorithm is configurable to perform a reachability analysis on arbitrary combinations of existing CPAs. In software verification, it takes a considerable amount of effort to convert a verification idea into actual experimental results --- we aim at accelerating this process. We hope that researchers find it convenient and productive to implement new verification ideas and algorithms using this flexible and easy-to-extend platform, and that it advances the field by making it easier to perform practical experiments. The tool is implemented in Java and runs as command-line tool or as Eclipse plug-in. CPAchecker implements CPAs for several abstract domains. We evaluate the efficiency of the current version of our tool on software-verification benchmarks from the literature, and compare it with other state-of-the-art model checkers. CPAchecker is an open-source toolkit and publicly available.}, keyword = {CPAchecker,Software Model Checking}, }
77. Dirk Beyer, M. Erkan Keremoglu, and Philipp Wendler. Predicate Abstraction with Adjustable-Block Encoding. In Proceedings of the 10th International Conference on Formal Methods in Computer-Aided Design (FMCAD 2010, Lugano, October 20-23), pages 189-197, 2010. FMCAD. Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    Abstract

    Several successful software model checkers are based on a technique called single-block encoding (SBE), which computes costly predicate abstractions after every single program operation. Large-block encoding (LBE) computes abstractions only after a large number of operations, and it was shown that this significantly improves the verification performance. In this work, we present adjustable-block encoding (ABE), a unifying framework that allows to express both previous approaches. In addition, it provides the flexibility to specify any block size between SBE and LBE, and also beyond LBE, through the adjustment of one single parameter. Such a unification of different concepts makes it easier to understand the fundamental properties of the analysis, and makes the differences of the variants more explicit. We evaluate different configurations on example C programs, and identify one that is currently the best.
    BibTeX Entry

    @inproceedings{FMCAD10, author = {Dirk Beyer and M.~Erkan Keremoglu and Philipp Wendler}, title = {Predicate Abstraction with Adjustable-Block Encoding}, booktitle = {Proceedings of the 10th International Conference on Formal Methods in Computer-Aided Design (FMCAD~2010, Lugano, October 20-23)}, pages = {189-197}, year = {2010}, publisher = {FMCAD}, isbn = {}, url = {http://www.sosy-lab.org/~dbeyer/cpa-abe/}, pdf = {https://www.sosy-lab.org/research/pub/2010-FMCAD.Predicate_Abstraction_with_Adjustable-Block_Encoding.pdf}, abstract = {Several successful software model checkers are based on a technique called single-block encoding (SBE), which computes costly predicate abstractions after every single program operation. Large-block encoding (LBE) computes abstractions only after a large number of operations, and it was shown that this significantly improves the verification performance. In this work, we present adjustable-block encoding (ABE), a unifying framework that allows to express both previous approaches. In addition, it provides the flexibility to specify any block size between SBE and LBE, and also beyond LBE, through the adjustment of one single parameter. Such a unification of different concepts makes it easier to understand the fundamental properties of the analysis, and makes the differences of the variants more explicit. We evaluate different configurations on example C programs, and identify one that is currently the best.}, keyword = {CPAchecker,Software Model Checking}, annote = {Won the NRW Young Scientist Award 2010 in Dynamic Intelligent Systems}, doinone = {DOI not available}, urlpub = {https://ieeexplore.ieee.org/document/5770949/}, }
    Additional Infos

    Won the NRW Young Scientist Award 2010 in Dynamic Intelligent Systems
78. Dirk Beyer, Alessandro Cimatti, Alberto Griggio, M. Erkan Keremoglu, and Roberto Sebastiani. Software Model Checking via Large-Block Encoding. In Proceedings of the 9th International Conference on Formal Methods in Computer-Aided Design (FMCAD 2009, Austin, TX, November 15-18), pages 25-32, 2009. IEEE Computer Society Press, Los Alamitos (CA). doi:10.1109/FMCAD.2009.5351147 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF
    Abstract

    Several successful approaches to software verification are based on the construction and analysis of an abstract reachability tree (ART). The ART represents unwindings of the control-flow graph of the program. Traditionally, a transition of the ART represents a single block of the program, and therefore, we call this approach single-block encoding (SBE). SBE may result in a huge number of program paths to be explored, which constitutes a fundamental source of inefficiency. We propose a generalization of the approach, in which transitions of the ART represent larger portions of the program; we call this approach large-block encoding (LBE). LBE may reduce the number of paths to be explored up to exponentially. Within this framework, we also investigate symbolic representations: for representing abstract states, in addition to conjunctions as used in SBE, we investigate the use of arbitrary Boolean formulas; for computing abstract-successor states, in addition to Cartesian predicate abstraction as used in SBE, we investigate the use of Boolean predicate abstraction. The new encoding leverages the efficiency of state-of-the-art SMT solvers, which can symbolically compute abstract large-block successors. Our experiments on benchmark C programs show that the large-block encoding outperforms the single-block encoding.
    BibTeX Entry

    @inproceedings{FMCAD09, author = {Dirk Beyer and Alessandro Cimatti and Alberto Griggio and M.~Erkan Keremoglu and Roberto Sebastiani}, title = {Software Model Checking via Large-Block Encoding}, booktitle = {Proceedings of the 9th International Conference on Formal Methods in Computer-Aided Design (FMCAD~2009, Austin, TX, November 15-18)}, pages = {25-32}, year = {2009}, publisher = {IEEE Computer Society Press, Los Alamitos~(CA)}, isbn = {978-1-4244-4966-8}, doi = {10.1109/FMCAD.2009.5351147}, url = {}, pdf = {https://www.sosy-lab.org/research/pub/2009-FMCAD.Software_Model_Checking_via_Large-Block_Encoding.pdf}, abstract = {Several successful approaches to software verification are based on the construction and analysis of an abstract reachability tree (ART). The ART represents unwindings of the control-flow graph of the program. Traditionally, a transition of the ART represents a single block of the program, and therefore, we call this approach single-block encoding (SBE). SBE may result in a huge number of program paths to be explored, which constitutes a fundamental source of inefficiency. We propose a generalization of the approach, in which transitions of the ART represent larger portions of the program; we call this approach large-block encoding (LBE). LBE may reduce the number of paths to be explored up to exponentially. Within this framework, we also investigate symbolic representations: for representing abstract states, in addition to conjunctions as used in SBE, we investigate the use of arbitrary Boolean formulas; for computing abstract-successor states, in addition to Cartesian predicate abstraction as used in SBE, we investigate the use of Boolean predicate abstraction. The new encoding leverages the efficiency of state-of-the-art SMT solvers, which can symbolically compute abstract large-block successors. Our experiments on benchmark C programs show that the large-block encoding outperforms the single-block encoding.}, keyword = {CPAchecker,Software Model Checking}, }

79. Daniel Baier, Dirk Beyer, Po-Chun Chien, Marie-Christine Jakobs, Marek Jankola, Matthias Kettl, Nian-Ze Lee, Thomas Lemberger, Marian Lingsch-Rosenfeld, Henrik Wachowitz, and Philipp Wendler. Software Verification with CPAchecker 3.0: Tutorial and User Guide (Extended Version). Technical report 2409.02094, arXiv/CoRR, September 2024. doi:10.48550/arXiv.2409.02094 Keyword(s): CPAchecker, Software Model Checking, Software Testing Funding: DFG-COOP, DFG-CONVEY, DFG-IDEFIX Publisher's Version PDF Presentation Supplement
    Artifact(s)

    1. doi:10.5281/zenodo.13612338
    Abstract

    This tutorial provides an introduction to CPAchecker for users. CPAchecker is a flexible and configurable framework for software verification and testing. The framework provides many abstract domains, such as BDDs, explicit values, intervals, memory graphs, and predicates, and many program-analysis and model-checking algorithms, such as abstract interpretation, bounded model checking, Impact, interpolation-based model checking, k-induction, PDR, predicate abstraction, and symbolic execution. This tutorial presents basic use cases for CPAchecker in formal software verification, focusing on its main verification techniques with their strengths and weaknesses. It also shows further use cases of CPAchecker for test-case generation and witness-based result validation. The envisioned readers are assumed to possess a background in automatic formal verification and program analysis, but prior knowledge of CPAchecker is not required. This tutorial and user guide is based on CPAchecker in version 3.0. This user guide's latest version and other documentation are available at https://cpachecker.sosy-lab.org/doc.php.
    BibTeX Entry

    @techreport{TechReport24c, author = {Daniel Baier and Dirk Beyer and Po-Chun Chien and Marie-Christine Jakobs and Marek Jankola and Matthias Kettl and Nian-Ze Lee and Thomas Lemberger and Marian Lingsch-Rosenfeld and Henrik Wachowitz and Philipp Wendler}, title = {Software Verification with {CPAchecker} 3.0: {Tutorial} and User Guide (Extended Version)}, number = {2409.02094}, year = {2024}, doi = {10.48550/arXiv.2409.02094}, url = {https://cpachecker.sosy-lab.org}, presentation = {https://www.sosy-lab.org/research/prs/2024-09-10_FM24_CPAchecker_Tutorial.pdf}, abstract = {This tutorial provides an introduction to CPAchecker for users. CPAchecker is a flexible and configurable framework for software verification and testing. The framework provides many abstract domains, such as BDDs, explicit values, intervals, memory graphs, and predicates, and many program-analysis and model-checking algorithms, such as abstract interpretation, bounded model checking, Impact, interpolation-based model checking, <i>k</i>-induction, PDR, predicate abstraction, and symbolic execution. This tutorial presents basic use cases for CPAchecker in formal software verification, focusing on its main verification techniques with their strengths and weaknesses. It also shows further use cases of CPAchecker for test-case generation and witness-based result validation. The envisioned readers are assumed to possess a background in automatic formal verification and program analysis, but prior knowledge of CPAchecker is not required. This tutorial and user guide is based on CPAchecker in version 3.0. This user guide's latest version and other documentation are available at <a href="https://cpachecker.sosy-lab.org/doc.php">https://cpachecker.sosy-lab.org/doc.php</a>.}, keyword = {CPAchecker, Software Model Checking, Software Testing}, annote = {This technical report is an extended version of our <a href="https://www.sosy-lab.org/research/bib/All/index.html#FM24a">paper</a> at FM 2024.}, artifact = {10.5281/zenodo.13612338}, funding = {DFG-COOP, DFG-CONVEY, DFG-IDEFIX}, institution = {arXiv/CoRR}, month = {September}, }
    Additional Infos

    This technical report is an extended version of our paper at FM 2024.
80. Dirk Beyer, Po-Chun Chien, and Nian-Ze Lee. Augmenting Interpolation-Based Model Checking with Auxiliary Invariants (Extended Version). Technical report 2403.07821, arXiv/CoRR, March 2024. doi:10.48550/arXiv.2403.07821 Keyword(s): Software Model Checking, Cooperative Verification, CPAchecker Funding: DFG-CONVEY Publisher's Version PDF Supplement
    Artifact(s)

    1. doi:10.5281/zenodo.10548594
    Abstract

    Software model checking is a challenging problem, and generating relevant invariants is a key factor in proving the safety properties of a program. Program invariants can be obtained by various approaches, including lightweight procedures based on data-flow analysis and intensive techniques using Craig interpolation. Although data-flow analysis runs efficiently, it often produces invariants that are too weak to prove the properties. By contrast, interpolation-based approaches build strong invariants from interpolants, but they might not scale well due to expensive interpolation procedures. Invariants can also be injected into model-checking algorithms to assist the analysis. Invariant injection has been studied for many well-known approaches, including k-induction, predicate abstraction, and symbolic execution. We propose an augmented interpolation-based verification algorithm that injects external invariants into interpolation-based model checking (McMillan, 2003), a hardware model-checking algorithm recently adopted for software verification. The auxiliary invariants help prune unreachable states in Craig interpolants and confine the analysis to the reachable parts of a program. We implemented the proposed technique in the verification framework CPAchecker and evaluated it against mature SMT-based methods in CPAchecker as well as other state-of-the-art software verifiers. We found that injecting invariants reduces the number of interpolation queries needed to prove safety properties and improves the run-time efficiency. Consequently, the proposed invariant-injection approach verified difficult tasks that none of its plain version (i.e., without invariants), the invariant generator, or any compared tools could solve.
    BibTeX Entry

    @techreport{TechReport24a, author = {Dirk Beyer and Po-Chun Chien and Nian-Ze Lee}, title = {Augmenting Interpolation-Based Model Checking with Auxiliary Invariants (Extended Version)}, number = {2403.07821}, year = {2024}, doi = {10.48550/arXiv.2403.07821}, url = {https://www.sosy-lab.org/research/imc-df/}, pdf = {https://arxiv.org/abs/2403.07821}, abstract = {Software model checking is a challenging problem, and generating relevant invariants is a key factor in proving the safety properties of a program. Program invariants can be obtained by various approaches, including lightweight procedures based on data-flow analysis and intensive techniques using Craig interpolation. Although data-flow analysis runs efficiently, it often produces invariants that are too weak to prove the properties. By contrast, interpolation-based approaches build strong invariants from interpolants, but they might not scale well due to expensive interpolation procedures. Invariants can also be injected into model-checking algorithms to assist the analysis. Invariant injection has been studied for many well-known approaches, including <i>k</i>-induction, predicate abstraction, and symbolic execution. We propose an augmented interpolation-based verification algorithm that injects external invariants into interpolation-based model checking (McMillan, 2003), a hardware model-checking algorithm recently adopted for software verification. The auxiliary invariants help prune unreachable states in Craig interpolants and confine the analysis to the reachable parts of a program. We implemented the proposed technique in the verification framework CPAchecker and evaluated it against mature SMT-based methods in CPAchecker as well as other state-of-the-art software verifiers. We found that injecting invariants reduces the number of interpolation queries needed to prove safety properties and improves the run-time efficiency. Consequently, the proposed invariant-injection approach verified difficult tasks that none of its plain version (i.e., without invariants), the invariant generator, or any compared tools could solve.}, keyword = {Software Model Checking, Cooperative Verification, CPAchecker}, annote = {This technical report is an extended version of our <a href="https://www.sosy-lab.org/research/bib/All/index.html#SPIN24b">paper</a> at SPIN 2024.}, artifact = {10.5281/zenodo.10548594}, funding = {DFG-CONVEY}, institution = {arXiv/CoRR}, month = {March}, }
    Additional Infos

    This technical report is an extended version of our paper at SPIN 2024.
81. Po-Chun Chien. Bridging Hardware and Software Formal Verification (Extended Abstract). Technical report 2024-06, LMU Munich, 2024. Keyword(s): Software Model Checking, Cooperative Verification, Btor2, CPAchecker, Witness-Based Validation Funding: DFG-CONVEY PDF
    Abstract

    Modern technology relies heavily on the integration of hardware and software systems, from embedded devices in consumer electronics to safety-critical controllers. Despite their interdependence, the tools and methods used for verifying the correctness and reliability of these systems are often segregated, meaning that the advancement in one community cannot benefit another directly. Addressing this challenge, my dissertation aims at bridging the gap between hardware and software formal analysis. This involves translating representations of verification tasks, generating certificates for verification results, integrating state-of-the-art formal analysis tools into a cohesive framework, and adapting and combining model-checking algorithms across domains. By translating word-level hardware circuits into C programs, we found out that software analyzers were able to identify property violations that well-established hardware verifiers failed to detect. Moreover, by adopting interpolation-based hardware-verification algorithms for software analysis, we were able to tackle tasks unsolvable by existing methods. Our research consolidates knowledge from both hardware and software domains, paving a pathway for comprehensive system-level verification.
    BibTeX Entry

    @techreport{chien:fm24-doc-symposium, author = {Po-Chun Chien}, title = {Bridging Hardware and Software Formal Verification (Extended Abstract)}, number = {2024-06}, year = {2024}, pdf = {https://www.sosy-lab.org/research/pub/2024-FM_Doctoral_Symposium.Bridging_Hardware_and_Software_Formal_Verification_Extended_Abstract.pdf}, abstract = {Modern technology relies heavily on the integration of hardware and software systems, from embedded devices in consumer electronics to safety-critical controllers. Despite their interdependence, the tools and methods used for verifying the correctness and reliability of these systems are often segregated, meaning that the advancement in one community cannot benefit another directly. Addressing this challenge, my dissertation aims at bridging the gap between hardware and software formal analysis. This involves translating representations of verification tasks, generating certificates for verification results, integrating state-of-the-art formal analysis tools into a cohesive framework, and adapting and combining model-checking algorithms across domains. By translating word-level hardware circuits into C programs, we found out that software analyzers were able to identify property violations that well-established hardware verifiers failed to detect. Moreover, by adopting interpolation-based hardware-verification algorithms for software analysis, we were able to tackle tasks unsolvable by existing methods. Our research consolidates knowledge from both hardware and software domains, paving a pathway for comprehensive system-level verification.}, keyword = {Software Model Checking, Cooperative Verification, Btor2, CPAchecker, Witness-Based Validation}, annote = {An extended abstract of the dissertation project. Submitted to the Doctoral Symposium of FM 2024.}, funding = {DFG-CONVEY}, institution = {LMU Munich}, }
    Additional Infos

    An extended abstract of the dissertation project. Submitted to the Doctoral Symposium of FM 2024.
82. Marie-Christine Jakobs and Tim Pollandt. Incorporating Data Dependencies and Properties in Difference Verification with Conditions (Technical Report). Technical report 2309.01585, arXiv/CoRR, 2023. doi:10.48550/arXiv.2309.01585 Keyword(s): Incremental Verification, Regression Verification, Software Model Checking, CPAchecker Funding: Software-Factory 4.0, DFG-ReVeriX Publisher's Version PDF
    Artifact(s)

    1. doi:10.5281/zenodo.8272913
    BibTeX Entry

    @techreport{diffDP-TechReport, author = {Marie{-}Christine Jakobs and Tim Pollandt}, title = {Incorporating Data Dependencies and Properties in Difference Verification with Conditions (Technical Report)}, number = {2309.01585}, year = {2023}, doi = {10.48550/arXiv.2309.01585}, url = {}, pdf = {}, keyword = {Incremental Verification, Regression Verification, Software Model Checking, CPAchecker}, annote = {This technical report is an extended version of our <a href="https://www.sosy-lab.org/research/bib/All/index.html#diffDP">paper</a> at iFM 2023.}, artifact = {10.5281/zenodo.8272913}, funding = {Software-Factory 4.0, DFG-ReVeriX}, institution = {arXiv/CoRR}, }
    Additional Infos

    This technical report is an extended version of our paper at iFM 2023.
83. Dirk Beyer, Nian-Ze Lee, and Philipp Wendler. Interpolation and SAT-Based Model Checking Revisited: Adoption to Software Verification. Technical report 2208.05046, arXiv/CoRR, August 2022. doi:10.48550/arXiv.2208.05046 Keyword(s): Software Model Checking, CPAchecker Publisher's Version PDF Presentation Supplement
    Abstract

    Interpolation-based model checking (McMillan, 2003) is a formal-verification algorithm, which was originally devised to verify safety properties of finite-state transition systems. The algorithm is state-of-the-art in hardware model checking. It derives interpolants from unsatisfiable BMC queries, and collects them to construct an overapproximation of the set of reachable states. Unlike other formal-verification algorithms, such as k-induction or PDR, which have been extended to handle infinite-state systems and investigated for program analysis, McMillan's interpolation-based model checking algorithm from 2003 has not been used to verify programs so far. This paper closes this significant, 19 years old gap in knowledge by adopting the algorithm to software verification. We implemented it in the verification framework CPAchecker, and evaluated the implementation against other state-of-the-art software-verification techniques over the largest publicly available benchmark suite of C safety-verification tasks. The evaluation demonstrates that interpolation-based model checking is competitive among other algorithms in terms of both the number of solved verification tasks and the run-time efficiency. Our results might have important implications for software verification, because researchers and developers now have a richer set of approaches to choose from.
    BibTeX Entry

    @techreport{TechReport22a, author = {Dirk Beyer and Nian-Ze Lee and Philipp Wendler}, title = {Interpolation and SAT-Based Model Checking Revisited: Adoption to Software Verification}, number = {2208.05046}, year = {2022}, doi = {10.48550/arXiv.2208.05046}, url = {https://www.sosy-lab.org/research/cpa-imc/}, presentation = {https://www.sosy-lab.org/research/prs/2022-08-11_iPRA22_Interpolation_and_SAT-Based_Model_Checking_Revisited.pdf}, abstract = {Interpolation-based model checking <a href="https://doi.org/10.1007/978-3-540-45069-6_1">(McMillan, 2003)</a> is a formal-verification algorithm, which was originally devised to verify safety properties of finite-state transition systems. The algorithm is state-of-the-art in hardware model checking. It derives interpolants from unsatisfiable BMC queries, and collects them to construct an overapproximation of the set of reachable states. Unlike other formal-verification algorithms, such as k-induction or PDR, which have been extended to handle infinite-state systems and investigated for program analysis, McMillan's <em>interpolation-based model checking</em> algorithm from 2003 has not been used to verify programs so far. This paper closes this significant, 19 years old gap in knowledge by adopting the algorithm to software verification. We implemented it in the verification framework CPAchecker, and evaluated the implementation against other state-of-the-art software-verification techniques over the largest publicly available benchmark suite of C safety-verification tasks. The evaluation demonstrates that interpolation-based model checking is competitive among other algorithms in terms of both the number of solved verification tasks and the run-time efficiency. Our results might have important implications for software verification, because researchers and developers now have a richer set of approaches to choose from.}, keyword = {Software Model Checking, CPAchecker}, _pdf = {https://www.sosy-lab.org/research/cpa-imc/Interpolation_and_SAT-Based_Model_Checking_Revisited.pdf}, institution = {arXiv/CoRR}, month = {August}, }
84. Dirk Beyer, Matthias Dangl, and Philipp Wendler. Combining k-Induction with Continuously-Refined Invariants. Technical report MIP-1503, Department of Computer Science and Mathematics (FIM), University of Passau (PA), January 2015. doi:10.48550/arXiv.1502.00096 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    BibTeX Entry

    @techreport{TR1503-PA15, author = {Dirk Beyer and Matthias Dangl and Philipp Wendler}, title = {Combining k-Induction with Continuously-Refined Invariants}, number = {MIP-1503}, year = {2015}, doi = {10.48550/arXiv.1502.00096}, url = {https://www.sosy-lab.org/research/cpa-k-induction/}, keyword = {CPAchecker,Software Model Checking}, annote = {An <a href="https://www.sosy-lab.org/research/bib/Year/2015.complete.html#CAV15">abbreviated version</a> of this article appeared in Proc. CAV 2015.}, institution = {Department of Computer Science and Mathematics (FIM), University of Passau (PA)}, month = {January}, }
    Additional Infos

    An abbreviated version of this article appeared in Proc. CAV 2015.
85. Dirk Beyer, Stefan Löwe, and Philipp Wendler. Domain-Type-Guided Refinement Selection Based on Sliced Path Prefixes. Technical report MIP-1501, Department of Computer Science and Mathematics (FIM), University of Passau (PA), January 2015. doi:10.48550/arXiv.1502.00045 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    BibTeX Entry

    @techreport{TR1501-PA15, author = {Dirk Beyer and Stefan L{\"o}we and Philipp Wendler}, title = {Domain-Type-Guided Refinement Selection Based on Sliced Path Prefixes}, number = {MIP-1501}, year = {2015}, doi = {10.48550/arXiv.1502.00045}, url = {https://www.sosy-lab.org/research/cpa-ref-sel/}, keyword = {CPAchecker,Software Model Checking}, annote = {Extended publications based on this article appeared in <a href="https://www.sosy-lab.org/research/bib/Year/2015.complete.html#FORTE15">Proc. FORTE 2015</a> and <a href="https://www.sosy-lab.org/research/bib/Year/2015.complete.html#SPIN15b">Proc. SPIN 2015</a>.}, institution = {Department of Computer Science and Mathematics (FIM), University of Passau (PA)}, month = {January}, }
    Additional Infos

    Extended publications based on this article appeared in Proc. FORTE 2015 and Proc. SPIN 2015.
86. Dirk Beyer, Stefan Löwe, Evgeny Novikov, Andreas Stahlbauer, and Philipp Wendler. Reusing Precisions for Efficient Regression Verification. Technical report MIP-1302, Department of Computer Science and Mathematics (FIM), University of Passau (PA), May 2013. doi:10.48550/arXiv.1305.6915 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    Abstract

    Continuous testing during development is a well-established technique for software-quality assurance. Continuous model checking from revision to revision is not yet established as a standard practice, because the enormous resource consumption makes its application impractical. Model checkers compute a large number of verification facts that are necessary for verifying if a given specification holds. We have identified a category of such intermediate results that are easy to store and efficient to reuse: abstraction precisions. The precision of an abstract domain specifies the level of abstraction that the analysis works on. Precisions are thus a precious result of the verification effort and it is a waste of resources to throw them away after each verification run. In particular, precisions are small and thus easy to store; they are easy to process and have a large impact on resource consumption. We experimentally show the impact of precision reuse on industrial verification problems, namely, 59 device drivers with 1119 revisions from the Linux kernel.
    BibTeX Entry

    @techreport{TR1302-PA13, author = {Dirk Beyer and Stefan L{\"o}we and Evgeny Novikov and Andreas Stahlbauer and Philipp Wendler}, title = {Reusing Precisions for Efficient Regression Verification}, number = {MIP-1302}, year = {2013}, doi = {10.48550/arXiv.1305.6915}, url = {https://www.sosy-lab.org/research/cpa-reuse/}, abstract = {Continuous testing during development is a well-established technique for software-quality assurance. Continuous model checking from revision to revision is not yet established as a standard practice, because the enormous resource consumption makes its application impractical. Model checkers compute a large number of verification facts that are necessary for verifying if a given specification holds. We have identified a category of such intermediate results that are easy to store and efficient to reuse: abstraction precisions. The precision of an abstract domain specifies the level of abstraction that the analysis works on. Precisions are thus a precious result of the verification effort and it is a waste of resources to throw them away after each verification run. In particular, precisions are small and thus easy to store; they are easy to process and have a large impact on resource consumption. We experimentally show the impact of precision reuse on industrial verification problems, namely, 59 device drivers with 1119 revisions from the Linux kernel.}, keyword = {CPAchecker,Software Model Checking}, annote = {An <a href="https://www.sosy-lab.org/research/bib/Year/2013.complete.html#FSE13">abbreviated version</a> of this article appeared in Proc. ESEC/FSE 2013.}, institution = {Department of Computer Science and Mathematics (FIM), University of Passau (PA)}, month = {May}, }
    Additional Infos

    An abbreviated version of this article appeared in Proc. ESEC/FSE 2013.
87. Sven Apel, Dirk Beyer, Karlheinz Friedberger, Franco Raimondi, and Alexander von Rhein. Domain Types: Selecting Abstractions Based on Variable Usage. Technical report MIP-1303, Department of Computer Science and Mathematics (FIM), University of Passau (PA), May 2013. doi:10.48550/arXiv.1305.6640 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    Abstract

    The success of software model checking depends on finding an appropriate abstraction of the subject program. The choice of the abstract domain and the analysis configuration is currently left to the user, who may not be familiar with the tradeoffs and performance details of the available abstract domains. We introduce the concept of domain types, which classify the program variables into types that are more fine-grained than standard declared types, such as int or long, in order to guide the selection of an appropriate abstract domain for a model checker. Our implementation determines the domain type for each variable in a pre-processing step, based on the variable usage in the program, and then assigns each variable to an abstract domain. The model-checking framework that we use supports to specify a separate analysis precision for each abstract domain, such that we can freely configure the analysis. We experimentally demonstrate a significant impact of the choice of the abstract domain per variable. We consider one explicit (hash tables for integer values) and one symbolic (binary decision diagrams) domain. The experiments are based on standard verification tasks that are taken from recent competitions on software verification. Each abstract domain has unique advantages in representing the state space of variables of a certain domain type. Our experiments show that software model checkers can be improved with a domain-type guided combination of abstract domains.
    BibTeX Entry

    @techreport{TR1303-PA13, author = {Sven Apel and Dirk Beyer and Karlheinz Friedberger and Franco Raimondi and Alexander von Rhein}, title = {Domain Types: Selecting Abstractions Based on Variable Usage}, number = {MIP-1303}, year = {2013}, doi = {10.48550/arXiv.1305.6640}, url = {https://www.sosy-lab.org/research/domaintypes/}, abstract = {The success of software model checking depends on finding an appropriate abstraction of the subject program. The choice of the abstract domain and the analysis configuration is currently left to the user, who may not be familiar with the tradeoffs and performance details of the available abstract domains. We introduce the concept of domain types, which classify the program variables into types that are more fine-grained than standard declared types, such as int or long, in order to guide the selection of an appropriate abstract domain for a model checker. Our implementation determines the domain type for each variable in a pre-processing step, based on the variable usage in the program, and then assigns each variable to an abstract domain. The model-checking framework that we use supports to specify a separate analysis precision for each abstract domain, such that we can freely configure the analysis. We experimentally demonstrate a significant impact of the choice of the abstract domain per variable. We consider one explicit (hash tables for integer values) and one symbolic (binary decision diagrams) domain. The experiments are based on standard verification tasks that are taken from recent competitions on software verification. Each abstract domain has unique advantages in representing the state space of variables of a certain domain type. Our experiments show that software model checkers can be improved with a domain-type guided combination of abstract domains.}, keyword = {CPAchecker,Software Model Checking}, annote = {}, institution = {Department of Computer Science and Mathematics (FIM), University of Passau (PA)}, month = {May}, }
88. Dirk Beyer and Stefan Löwe. Explicit-Value Analysis Based on CEGAR and Interpolation. Technical report MIP-1205, Department of Computer Science and Mathematics (FIM), University of Passau (PA), December 2012. doi:10.48550/arXiv.1212.6542 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF
    BibTeX Entry

    @techreport{TR1205-PA12, author = {Dirk Beyer and Stefan L{\"o}we}, title = {Explicit-Value Analysis Based on {CEGAR} and Interpolation}, number = {MIP-1205}, year = {2012}, doi = {10.48550/arXiv.1212.6542}, url = {}, abstract = {}, keyword = {CPAchecker,Software Model Checking}, annote = {}, institution = {Department of Computer Science and Mathematics (FIM), University of Passau (PA)}, month = {December}, }
89. Dirk Beyer, Thomas A. Henzinger, M. Erkan Keremoglu, and Philipp Wendler. Conditional Model Checking. Technical report MIP-1107, Department of Computer Science and Mathematics (FIM), University of Passau (PA), September 2011. doi:10.48550/arXiv.1109.6926 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    Abstract

    Software model checking, as an undecidable problem, has three possible outcomes: (1) the program satisfies the specification, (2) the program does not satisfy the specification, and (3) the model checker fails. The third outcome usually manifests itself in a space-out, time-out, or one component of the verification tool giving up; in all of these failing cases, significant computation is performed by the verification tool before the failure, but no result is reported. We propose to reformulate the model-checking problem as follows, in order to have the verification tool report a summary of the performed work even in case of failure: given a program and a specification, the model checker returns a condition P -usually a state predicate- such that the program satisfies the specification under the condition P -that is, as long as the program does not leave states in which P is satisfied. We are of course interested in model checkers that return conditions P that are as weak as possible. Instead of outcome (1), the model checker will return P = true; instead of (2), the condition P will return the part of the state space that satisfies the specification; and in case (3), the condition P can summarize the work that has been performed by the model checker before space-out, time-out, or giving up. If complete verification is necessary, then a different verification method or tool may be used to focus on the states that violate the condition. We give such conditions as input to a conditional model checker, such that the verification problem is restricted to the part of the state space that satisfies the condition. Our experiments show that repeated application of conditional model checkers, using different conditions, can significantly improve the verification results, state-space coverage, and performance.
    BibTeX Entry

    @techreport{TR1107-PA11, author = {Dirk Beyer and Thomas A. Henzinger and M. Erkan Keremoglu and Philipp Wendler}, title = {Conditional Model Checking}, number = {MIP-1107}, year = {2011}, doi = {10.48550/arXiv.1109.6926}, url = {https://www.sosy-lab.org/~dbeyer/cpa-cmc/}, abstract = {Software model checking, as an undecidable problem, has three possible outcomes: (1) the program satisfies the specification, (2) the program does not satisfy the specification, and (3) the model checker fails. The third outcome usually manifests itself in a space-out, time-out, or one component of the verification tool giving up; in all of these failing cases, significant computation is performed by the verification tool before the failure, but no result is reported. We propose to reformulate the model-checking problem as follows, in order to have the verification tool report a summary of the performed work even in case of failure: given a program and a specification, the model checker returns a condition P ---usually a state predicate--- such that the program satisfies the specification under the condition P ---that is, as long as the program does not leave states in which P is satisfied. We are of course interested in model checkers that return conditions P that are as weak as possible. Instead of outcome (1), the model checker will return P = true; instead of (2), the condition P will return the part of the state space that satisfies the specification; and in case (3), the condition P can summarize the work that has been performed by the model checker before space-out, time-out, or giving up. If complete verification is necessary, then a different verification method or tool may be used to focus on the states that violate the condition. We give such conditions as input to a conditional model checker, such that the verification problem is restricted to the part of the state space that satisfies the condition. Our experiments show that repeated application of conditional model checkers, using different conditions, can significantly improve the verification results, state-space coverage, and performance.}, keyword = {CPAchecker,Software Model Checking}, annote = {An <a href="https://www.sosy-lab.org/research/bib/Year/2012.complete.html#FSE12">abbreviated version</a> of this article appeared in Proc. FSE 2012.}, institution = {Department of Computer Science and Mathematics (FIM), University of Passau (PA)}, month = {September}, }
    Additional Infos

    An abbreviated version of this article appeared in Proc. FSE 2012.
90. Dirk Beyer, Alessandro Cimatti, Alberto Griggio, M. Erkan Keremoglu, and Roberto Sebastiani. Software Model Checking via Large-Block Encoding. Technical report SFU-CS-2009-09, School of Computing Science (CMPT), Simon Fraser University (SFU), April 2009. doi:10.48550/arXiv.0904.4709 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF
    Abstract

    The construction and analysis of an abstract reachability tree (ART) are the basis for a successful method for software verification. The ART represents unwindings of the control-flow graph of the program. Traditionally, a transition of the ART represents a single block of the program, and therefore, we call this approach single-block encoding (SBE). SBE may result in a huge number of program paths to be explored, which constitutes a fundamental source of inefficiency. We propose a generalization of the approach, in which transitions of the ART represent larger portions of the program; we call this approach large-block encoding (LBE). LBE may reduce the number of paths to be explored up to exponentially. Within this framework, we also investigate symbolic representations: for representing abstract states, in addition to conjunctions as used in SBE, we investigate the use of arbitrary Boolean formulas; for computing abstract-successor states, in addition to Cartesian predicate abstraction as used in SBE, we investigate the use of Boolean predicate abstraction. The new encoding leverages the efficiency of state-of-the-art SMT solvers, which can symbolically compute abstract large-block successors. Our experiments on benchmark C programs show that the large-block encoding outperforms the single-block encoding.
    BibTeX Entry

    @techreport{TR009-SFU09, author = {Dirk Beyer and Alessandro Cimatti and Alberto Griggio and M. Erkan Keremoglu and Roberto Sebastiani}, title = {Software Model Checking via Large-Block Encoding}, number = {SFU-CS-2009-09}, year = {2009}, doi = {10.48550/arXiv.0904.4709}, url = {}, abstract = {The construction and analysis of an abstract reachability tree (ART) are the basis for a successful method for software verification. The ART represents unwindings of the control-flow graph of the program. Traditionally, a transition of the ART represents a single block of the program, and therefore, we call this approach single-block encoding (SBE). SBE may result in a huge number of program paths to be explored, which constitutes a fundamental source of inefficiency. We propose a generalization of the approach, in which transitions of the ART represent larger portions of the program; we call this approach large-block encoding (LBE). LBE may reduce the number of paths to be explored up to exponentially. Within this framework, we also investigate symbolic representations: for representing abstract states, in addition to conjunctions as used in SBE, we investigate the use of arbitrary Boolean formulas; for computing abstract-successor states, in addition to Cartesian predicate abstraction as used in SBE, we investigate the use of Boolean predicate abstraction. The new encoding leverages the efficiency of state-of-the-art SMT solvers, which can symbolically compute abstract large-block successors. Our experiments on benchmark C programs show that the large-block encoding outperforms the single-block encoding.}, keyword = {CPAchecker,Software Model Checking}, annote = {}, institution = {School of Computing Science (CMPT), Simon Fraser University (SFU)}, month = {April}, }
91. Dirk Beyer and M. Erkan Keremoglu. CPAchecker: A Tool for Configurable Software Verification. Technical report SFU-CS-2009-02, School of Computing Science (CMPT), Simon Fraser University (SFU), January 2009. doi:10.48550/arXiv.0902.0019 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
    Abstract

    Configurable software verification is a recent concept for expressing different program analysis and model checking approaches in one single formalism. This paper presents CPAchecker, a tool and framework that aims at easy integration of new verification components. Every abstract domain, together with the corresponding operations, is required to implement the interface of configurable program analysis (CPA). The main algorithm is configurable to perform a reachability analysis on arbitrary combinations of existing CPAs. The major design goal during the development was to provide a framework for developers that is flexible and easy to extend. We hope that researchers find it convenient and productive to implement new verification ideas and algorithms using this platform and that it advances the field by making it easier to perform practical experiments. The tool is implemented in Java and runs as command-line tool or as Eclipse plug-in. We evaluate the efficiency of our tool on benchmarks from the software model checker BLAST. The first released version of CPAchecker implements CPAs for predicate abstraction, octagon, and explicit-value domains. Binaries and the source code of CPAchecker are publicly available as free software.
    BibTeX Entry

    @techreport{TR002-SFU09, author = {Dirk Beyer and M. Erkan Keremoglu}, title = {{CPAchecker}: A Tool for Configurable Software Verification}, number = {SFU-CS-2009-02}, year = {2009}, doi = {10.48550/arXiv.0902.0019}, url = {http://www.sosy-lab.org/~dbeyer/CPAchecker/}, abstract = {Configurable software verification is a recent concept for expressing different program analysis and model checking approaches in one single formalism. This paper presents CPAchecker, a tool and framework that aims at easy integration of new verification components. Every abstract domain, together with the corresponding operations, is required to implement the interface of configurable program analysis (CPA). The main algorithm is configurable to perform a reachability analysis on arbitrary combinations of existing CPAs. The major design goal during the development was to provide a framework for developers that is flexible and easy to extend. We hope that researchers find it convenient and productive to implement new verification ideas and algorithms using this platform and that it advances the field by making it easier to perform practical experiments. The tool is implemented in Java and runs as command-line tool or as Eclipse plug-in. We evaluate the efficiency of our tool on benchmarks from the software model checker BLAST. The first released version of CPAchecker implements CPAs for predicate abstraction, octagon, and explicit-value domains. Binaries and the source code of CPAchecker are publicly available as free software.}, keyword = {CPAchecker,Software Model Checking}, annote = {}, institution = {School of Computing Science (CMPT), Simon Fraser University (SFU)}, month = {January}, }

92. Felix Lindenmeier. Creating an Exchangeable Intermediate Program Representation for the Formal Software Verifier CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2024. Keyword(s): CPAchecker
    BibTeX Entry

    @misc{LindenmeierCfaJsonExport, author = {Felix Lindenmeier}, title = {Creating an Exchangeable Intermediate Program Representation for the Formal Software Verifier CPAchecker}, year = {2024}, keyword = {CPAchecker}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
93. Tobias Maget. Evaluation of JVM Garbage Collectors for CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2024. Keyword(s): CPAchecker, Benchmarking PDF Presentation
    BibTeX Entry

    @misc{MagetEvaluationJVMGarbageCollectorsCPAchecker, author = {Tobias Maget}, title = {Evaluation of JVM Garbage Collectors for CPAchecker}, year = {2024}, pdf = {https://www.sosy-lab.org/research/bsc/2024.Maget.Evaluation_of_JVM_Garbage_Collectors_for_CPAchecker.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2024-10-23-BA_Evaluation_of_JVM_Garbage_Collectors_for_CPAchecker_Maget.pdf}, keyword = {CPAchecker, Benchmarking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
94. Benedikt Damböck. Verification of Java Programs with Exceptions with CPAchecker. Master's Thesis, LMU Munich, Software Systems Lab, 2023. Keyword(s): CPAchecker, Software Model Checking PDF Presentation
    BibTeX Entry

    @misc{DamboeckJavaExceptions, author = {Benedikt Damböck}, title = {Verification of Java Programs with Exceptions with CPAchecker}, year = {2023}, pdf = {https://www.sosy-lab.org/research/msc/2023.Damboeck.Verification_of_Java_Programs_with_Exceptions_with_CPAchecker.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2023-12-06_MA_Verification_of_Java_Programs_with_Exceptions_with_CPAchecker_Damboeck.pdf}, keyword = {CPAchecker,Software Model Checking}, field = {Computer Science}, howpublished = {Master's Thesis, LMU Munich, Software Systems Lab}, }
95. Heinrich Dennis Simon Lindner. Extending the Framework JavaSMT with the SMT Solver Bitwuzla and Evaluation using CPAchecker. at LMU Munich, Bachelor's Thesis, LMU Munich, Software Systems Lab, 2023. Keyword(s): JavaSMT, SMT, Bitwuzla, CPAchecker PDF
    BibTeX Entry

    @misc{LindnerDefense, author = {Heinrich Dennis Simon Lindner}, title = {Extending the Framework JavaSMT with the SMT Solver Bitwuzla and Evaluation using CPAchecker}, year = {2023}, pdf = {2023.Lindner.Extending_the_Framework_JavaSMT_with_the_SMT_Solver_Bitwuzla_and_Evaluation_using_CPAchecker.pdf}, keyword = {JavaSMT, SMT, Bitwuzla, CPAchecker}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, venue = {LMU Munich}, }
96. Daniel Raffler. Adding the SMT solver OpenSMT2 to the JavaSMT Framework and Evaluation using CPAchecker. at LMU Munich, Bachelor's Thesis, LMU Munich, Software Systems Lab, 2023. Keyword(s): SMT, JavaSMT, OpenSMT2, CPAchecker PDF
    BibTeX Entry

    @misc{RafflerBA, author = {Daniel Raffler}, title = {Adding the SMT solver OpenSMT2 to the JavaSMT Framework and Evaluation using CPAchecker}, year = {2023}, pdf = {2023.Raffler.Adding_the_SMT_solver_OpenSMT2_to_the_JavaSMT_Framework_and_Evaluation_using_CPAchecker.pdf}, keyword = {SMT, JavaSMT, OpenSMT2, CPAchecker}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, venue = {LMU Munich}, }
97. Janelle King. Implementing a Solver-Independent SMT-LIB2 Parser-Interpreter and Code-Generator for JavaSMT with Subsequent Evaluation. at LMU Munich, Bachelor's Thesis, LMU Munich, Software Systems Lab, 2023. Keyword(s): JavaSMT, SMT-LIB2, SMT, CPAchecker PDF
    BibTeX Entry

    @misc{KingBA, author = {Janelle King}, title = {Implementing a Solver-Independent SMT-LIB2 Parser-Interpreter and Code-Generator for JavaSMT with Subsequent Evaluation}, year = {2023}, pdf = {2023.King.Implementing_a_Solver-Independent_SMT-LIB2_Parser-Interpreter_and_Code-Generator_for_JavaSMT_with_Subsequent_Evaluation.pdf}, keyword = {JavaSMT, SMT-LIB2, SMT, CPAchecker}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, venue = {LMU Munich}, }
98. Matthias Dangl. Witness-Based Validation of Verification Results with Applications to Software-Model Checking. PhD Thesis, LMU Munich, Software Systems Lab, 2022. doi:10.5282/edoc.31508 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF
    BibTeX Entry

    @misc{DanglWitnesses, author = {Matthias Dangl}, title = {Witness-Based Validation of Verification Results with Applications to Software-Model Checking}, year = {2022}, doi = {10.5282/edoc.31508}, url = {}, pdf = {https://edoc.ub.uni-muenchen.de/31508/3/Dangl_Matthias.pdf}, presentation = {}, keyword = {CPAchecker,Software Model Checking}, annote = {Now at ARS, Munich, Germany}, howpublished = {PhD Thesis, LMU Munich, Software Systems Lab}, urn = {urn:nbn:de:bvb:19-315089}, }
    Additional Infos

    Now at ARS, Munich, Germany
99. Thomas Lemberger. Towards Cooperative Software Verification with Test Generation and Formal Verification. PhD Thesis, LMU Munich, Software Systems Lab, 2022. doi:10.5282/edoc.32852 Keyword(s): CPAchecker, Software Model Checking, Cooperative Verification Publisher's Version PDF Presentation
    BibTeX Entry

    @misc{LembergerCoop, author = {Thomas Lemberger}, title = {Towards Cooperative Software Verification with Test Generation and Formal Verification}, year = {2022}, doi = {10.5282/edoc.32852}, url = {}, pdf = {https://edoc.ub.uni-muenchen.de/32852/1/Lemberger_Thomas.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2022-12-12_PhD_TowardsCooperativeSoftwareVerification_Thomas.pdf}, keyword = {CPAchecker,Software Model Checking,Cooperative Verification}, annote = {Nominated for the <a href="https://se2024.se.jku.at/ernst-denert-se-preis/">Ernst Denert SE-Preis 2024</a>}, howpublished = {PhD Thesis, LMU Munich, Software Systems Lab}, urn = {urn:nbn:de:bvb:19-328522}, }
    Additional Infos

    Nominated for the Ernst Denert SE-Preis 2024
100. Karlheinz Friedberger. Efficient Software Model Checking with Block-Abstraction Memoization. PhD Thesis, LMU Munich, Software Systems Lab, 2022. doi:10.5282/edoc.29976 Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF
     BibTeX Entry

     @misc{FriedbergerBAM, author = {Karlheinz Friedberger}, title = {Efficient Software Model Checking with Block-Abstraction Memoization}, year = {2022}, doi = {10.5282/edoc.29976}, url = {}, pdf = {https://edoc.ub.uni-muenchen.de/29976/1/Friedberger_Karlheinz.pdf}, presentation = {}, keyword = {CPAchecker,Software Model Checking}, annote = {Now at MSG Systems, Munich, Germany}, howpublished = {PhD Thesis, LMU Munich, Software Systems Lab}, urn = {urn:nbn:de:bvb:19-296471}, }
     Additional Infos

     Now at MSG Systems, Munich, Germany
101. Daniel Baier. Implementation of Value Analysis over Symbolic Memory Graphs in CPAchecker. Master's Thesis, LMU Munich, Software Systems Lab, 2022. Keyword(s): CPAchecker, Software Model Checking, Symbolic Memory Graphs PDF Presentation
     BibTeX Entry

     @misc{BaierSymbolicMemoryGraphs, author = {Daniel Baier}, title = {Implementation of Value Analysis over Symbolic Memory Graphs in CPAchecker}, year = {2022}, pdf = {https://www.sosy-lab.org/research/msc/2022.Baier.Implementation_of_Value_Analysis_over_Symbolic_Memory_Graphs_in_CPAchecker.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2022-09-28_MA_Implementation_of_Value_Analysis_over_Symbolic_Memory_Graphs_in_CPAchecker_Baier.pdf}, keyword = {CPAchecker,Software Model Checking,Symbolic Memory Graphs}, howpublished = {Master's Thesis, LMU Munich, Software Systems Lab}, }
102. Martin Pletl. A New Spin on Verification with Symbolic Execution: Symbolic Execution as Formula-Based Predicate Analysis in CPAchecker. Master's Thesis, LMU Munich, Software Systems Lab, 2022. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{PletlSymbolicExecution, author = {Martin Pletl}, title = {A New Spin on Verification with Symbolic Execution: Symbolic Execution as Formula-Based Predicate Analysis in CPAchecker}, year = {2022}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, LMU Munich, Software Systems Lab}, }
103. Maximilian Hailer. New Approaches and Visualization for Verification Coverage. Master's Thesis, LMU Munich, Software Systems Lab, 2022. Keyword(s): CPAchecker, Software Model Checking PDF Presentation
     BibTeX Entry

     @misc{HailerVerificationCoverage, author = {Maximilian Hailer}, title = {New Approaches and Visualization for Verification Coverage}, year = {2022}, pdf = {https://www.sosy-lab.org/research/msc/2022.Hailer.New_Approaches_and_Visualization_for_Verification_Coverage.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2022-06-16_MA_New_Approaches_and_Visualization_for_Verification_Coverage_Hailer.pdf}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, LMU Munich, Software Systems Lab}, }
104. Matthias Kettl. Adjustable Block Analysis: Actor-Based Creation of Block Summaries for Scaling Formal Verification. Master's Thesis, LMU Munich, Software Systems Lab, 2022. Keyword(s): CPAchecker, Software Model Checking PDF Presentation
     BibTeX Entry

     @misc{Kettl, author = {Matthias Kettl}, title = {Adjustable Block Analysis: Actor-Based Creation of Block Summaries for Scaling Formal Verification}, year = {2022}, pdf = {https://www.sosy-lab.org/research/msc/2022.Kettl.Adjustable_Block_Analysis.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2022-02-24_MA_Adjustable_Block_Analysis.pdf}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, LMU Munich, Software Systems Lab}, }
105. Philipp Waldinger. Concurrent Software Verification through Block-based Task Partitioning and Continuous Summary Refinement. Master's Thesis, LMU Munich, Software Systems Lab, 2022. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{WaldingerTaskPartitioning, author = {Philipp Waldinger}, title = {Concurrent Software Verification through Block-based Task Partitioning and Continuous Summary Refinement}, year = {2022}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, LMU Munich, Software Systems Lab}, }
106. Klara Cimbalnik. Program Transformation in CPAchecker: Design and Implementation of a Source-Respecting Translation from Control-Flow Automata to C Code. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2022. Keyword(s): CPAchecker
     BibTeX Entry

     @misc{CimbalnikCfaExport, author = {Klara Cimbalnik}, title = {Program Transformation in \textsc{CPAchecker}: Design and Implementation of a Source-Respecting Translation from Control-Flow Automata to C Code}, year = {2022}, keyword = {CPAchecker}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
107. Ludwig Glückstadt. Genetic Programming in Software Verification. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2021. Keyword(s): Software Model Checking, CPAchecker, Genetic Programming
     BibTeX Entry

     @misc{GlueckstadtGP, author = {Ludwig Glückstadt}, title = {Genetic Programming in Software Verification}, year = {2021}, keyword = {Software Model Checking, CPAchecker, Genetic Programming}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
108. Simon Antonischki. A CPA for String Analysis for Java Programs in CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2021. Keyword(s): Software Model Checking, CPAchecker
     BibTeX Entry

     @misc{AntonischkiStringCPA, author = {Simon Antonischki}, title = {A CPA for String Analysis for Java Programs in \textsc{CPAchecker}}, year = {2021}, keyword = {Software Model Checking, CPAchecker}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
109. Penelope Powers. Mutation based Automatic Program Repair in CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2021. Keyword(s): Automatic Program Repair, CPAchecker
     BibTeX Entry

     @misc{PowersAPR, author = {Penelope Powers}, title = {Mutation based Automatic Program Repair in \textsc{CPAchecker}}, year = {2021}, keyword = {Automatic Program Repair, CPAchecker}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
110. Sebastian Tschoepel. Implementation and Evaluation of a Simple Taint Analysis for CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2021. Keyword(s): CPAchecker, Software Model Checking, Taint
     BibTeX Entry

     @misc{TschoepelTaint, author = {Sebastian Tschoepel}, title = {Implementation and Evaluation of a Simple Taint Analysis for \textsc{CPAchecker}}, year = {2021}, keyword = {CPAchecker, Software Model Checking, Taint}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
111. Moritz Beck. Solver-based Analysis of Memory Safety using Separation Logic. Master's Thesis, LMU Munich, Software Systems Lab, 2020. Keyword(s): CPAchecker, JavaSMT, Separation Logic, Software Model Checking PDF Presentation
     BibTeX Entry

     @misc{BeckSeparationLogic, author = {Moritz Beck}, title = {Solver-based Analysis of Memory Safety using Separation Logic}, year = {2020}, pdf = {https://www.sosy-lab.org/research/msc/2020.Beck.Solver-based_Analysis_of_Memory_Safety_using_Separation_Logic.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2020-09-16_MA_SolverBasedAnalysisOfMemorySafetyUsingSeparationLogic_Beck.pdf}, keyword = {CPAchecker,JavaSMT,Separation Logic,Software Model Checking}, howpublished = {Master's Thesis, LMU Munich, Software Systems Lab}, }
112. Martin Zehendner. Software Verification with Numerical Domains in CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2020. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{ZehendnerNumericalDomains, author = {Martin Zehendner}, title = {Software Verification with Numerical Domains in \textsc{CPAchecker}}, year = {2020}, keyword = {CPAchecker, Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
113. Sven Umbricht. Converting Between ACSL Annotations and Witness Invariants. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2020. Keyword(s): CPAchecker, Software Model Checking, ACSL PDF Presentation
     BibTeX Entry

     @misc{UmbrichtACSL, author = {Sven Umbricht}, title = {Converting Between ACSL Annotations and Witness Invariants}, year = {2020}, pdf = {https://www.sosy-lab.org/research/bsc/2020.Umbricht.Converting.Between.ACSL.Annotations.and.Witness.Invariants.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2021-02-10_BA_Converting.Between.ACSL.Annotations.and.Witness.Invariants_Umbricht.pdf}, keyword = {CPAchecker, Software Model Checking, ACSL}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
114. Benedikt Damböck. Implementierung und Evaluation von einfacher Schleifenabstraktion für das CPAchecker-Framework. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2020. Keyword(s): CPAchecker, Software Model Checking, Loop Acceleration
     BibTeX Entry

     @misc{DamboeckLoopAccel, author = {Benedikt Damböck}, title = {Implementierung und Evaluation von einfacher Schleifenabstraktion für das \textsc{CPAchecker}-Framework}, year = {2020}, keyword = {CPAchecker, Software Model Checking, Loop Acceleration}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
115. Sven Massard. Improve Analysis of Java Programs in CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2020. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{MassardJavaPrograms, author = {Sven Massard}, title = {Improve Analysis of Java Programs in \textsc{CPAchecker}}, year = {2020}, keyword = {CPAchecker, Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
116. Frederic Schönberger. Converting Test Goals to Condition Automata. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2020. Keyword(s): CPAchecker, Software Model Checking PDF Presentation
     BibTeX Entry

     @misc{SchoenbergerTestGoalsToConditions, author = {Frederic Sch{\"o}nberger}, title = {Converting Test Goals to Condition Automata}, year = {2020}, pdf = {https://www.sosy-lab.org/research/bsc/2020.Schoenberger.Converting_Test_Goals_to_Condition_Automata.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2021-01-13_BA_Converting_Test_Goals_to_Condition_Automata_Schoenberger.pdf}, keyword = {CPAchecker, Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
117. Jakob Selberg. Automatic Generation of Test Harnesses for Pointer-Based C Programs: Implementation of a Pointer-Tracking Analysis and Harness-Generation Engine in the Formal Verification Framework CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2020. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{SelbergHarnessesForPointers, author = {Jakob Selberg}, title = {Automatic Generation of Test Harnesses for Pointer-Based C Programs: Implementation of a Pointer-Tracking Analysis and Harness-Generation Engine in the Formal Verification Framework \textsc{CPAchecker}}, year = {2020}, keyword = {CPAchecker, Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
118. Yannick Adams. Domain Types for Predicate Analysis in CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2020. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{AdamsDomainTypesPredicate, author = {Yannick Adams}, title = {Domain Types for Predicate Analysis in \textsc{CPAchecker}}, year = {2020}, keyword = {CPAchecker, Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
119. Vladyslav Kolesnykov. SMT-Based Model Checking of Concurrent Programs. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2020. Keyword(s): CPAchecker, Software Model Checking PDF
     BibTeX Entry

     @misc{KolesnykovConcurrencySMT, author = {Vladyslav Kolesnykov}, title = {{SMT}-Based Model Checking of Concurrent Programs}, year = {2020}, pdf = {https://www.sosy-lab.org/research/bsc/2020.Kolesnykov.SMT-Based_Model_Checking_of_Concurrent_Programs.pdf}, keyword = {CPAchecker, Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
120. Angelos Kafounis. Fault Localization in Model Checking. Implementation and Evaluation of Fault-Localization Techniques with Distance Metrics. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2020. Keyword(s): CPAchecker, Software Model Checking PDF Presentation
     BibTeX Entry

     @misc{KafounisFaultLocalizationWithDistanceMetrics, author = {Angelos Kafounis}, title = {Fault Localization in Model Checking. Implementation and Evaluation of Fault-Localization Techniques with Distance Metrics}, year = {2020}, pdf = {https://www.sosy-lab.org/research/bsc/2020.Kafounis.Fault_Localization_in_Model_Checking_Implementation_and_Evaluation_of_Fault-Localization_Techniques_with_Distance_Metrics.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2020-09-29_BA_FaultLocalizationWithDistanceMetrics_Kafounis.pdf}, keyword = {CPAchecker, Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
121. Schindar Ali. Test-Based Fault Localization in the Context of Formal Verification: Implementation and Evaluation of the Tarantula Algorithm in CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2020. Keyword(s): CPAchecker, Software Model Checking PDF Presentation
     BibTeX Entry

     @misc{AliFaultLocalizationWithTarantula, author = {Schindar Ali}, title = {Test-Based Fault Localization in the Context of Formal Verification: Implementation and Evaluation of the Tarantula Algorithm in CPAchecker}, year = {2020}, pdf = {https://www.sosy-lab.org/research/bsc/2020.Ali.Test-Based_Fault_Localization_in_the_Context_of_Formal_Verification.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2020-09-02_BA_FaultLocalizationWithTestBasedDistanceMetrics_Ali.pdf}, keyword = {CPAchecker, Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
122. Petros Isaakidis. Energy Consumption Prediction of Verification Work. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2020. Keyword(s): CPAchecker, Benchmarking, Energy Measurement
     BibTeX Entry

     @misc{IsaakidisEnergy, author = {Petros Isaakidis}, title = {Energy Consumption Prediction of Verification Work}, year = {2020}, keyword = {CPAchecker, Benchmarking, Energy Measurement}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
123. Matthias Kettl. Fault Localization for Formal Verification: An Implementation and Evaluation of Algorithms based on Error Invariants and UNSAT-cores. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2020. Keyword(s): CPAchecker, Software Model Checking PDF Presentation
     BibTeX Entry

     @misc{KettlFaultLocalization, author = {Matthias Kettl}, title = {Fault Localization for Formal Verification: An Implementation and Evaluation of Algorithms based on Error Invariants and UNSAT-cores}, year = {2020}, pdf = {https://www.sosy-lab.org/research/bsc/2020.Kettl.Fault_Localization_for_Formal_Verification_An_Implementation_and_Evaluation_of_Algorithms_based_on_Error_Invariants_and_UNSAT-cores.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2020-07-22_BA_FaultLocalizationWithUnsatCores_Kettl.pdf}, keyword = {CPAchecker, Software Model Checking}, annote = {Won the LMU research award for excellent students (LMU Forschungspreis f{\"u}r exzellente Studierende) of LMU Munich}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
     Additional Infos

     Won the LMU research award for excellent students (LMU Forschungspreis für exzellente Studierende) of LMU Munich
124. Sonja Münchow. A Web Frontend For Visualization of Computation Steps and their Results in CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2020. Keyword(s): CPAchecker PDF Presentation
     BibTeX Entry

     @misc{MuenchowVisualizeComputationSteps, author = {Sonja M\"unchow}, title = {A Web Frontend For Visualization of Computation Steps and their Results in CPAchecker}, year = {2020}, pdf = {https://www.sosy-lab.org/research/bsc/2020.Muenchow.A_Web_Frontend_for_Visualization_of_Computation_Steps_and_their_Results_in_CPAchecker.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2020-07-15_BA_WebFrontendForVisualizationOfComputationStepsInCpachecker_Muenchow.pdf}, keyword = {CPAchecker}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
125. Adrian Leimeister. A Language Server and IDE Plugin for CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2020. Keyword(s): CPAchecker PDF Presentation
     BibTeX Entry

     @misc{LeimeisterIdeLsp, author = {Adrian Leimeister}, title = {A Language Server and IDE Plugin for \textsc{CPAchecker}}, year = {2020}, pdf = {https://www.sosy-lab.org/research/bsc/2020.Leimeister.A_Language_Server_and_IDE_Plugin_for_CPAchecker.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2020-07-15_BA_IdePluginForCpachecker_Leimeister.pdf}, keyword = {CPAchecker}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
126. Alexander Ried. Design and Implementation of a Cluster-Based Approach for Software Verification. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2020. Keyword(s): CPAchecker, BAM
     BibTeX Entry

     @misc{RiedClusterBAM, author = {Alexander Ried}, title = {Design and Implementation of a Cluster-Based Approach for Software Verification}, year = {2020}, keyword = {CPAchecker, BAM}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
127. Michael Maier. SMT-Based Verification of ECMAScript Programs in CPAchecker. Master's Thesis, LMU Munich, Software Systems Lab, 2019. Keyword(s): CPAchecker, Software Model Checking PDF Presentation
     BibTeX Entry

     @misc{MichaelJavascript, author = {Michael Maier}, title = {{SMT}-Based Verification of {ECMAScript} Programs in {{\sc CPAchecker}}}, year = {2019}, pdf = {https://www.sosy-lab.org/research/msc/2019.Maier.SMT_Based_Verification_of_ECMAScript_Programs_in_CPAchecker.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2019-06-26_MA_SMTBasedVerificationOfECMAScriptProgramsInCPAchecker_Maier.pdf}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, LMU Munich, Software Systems Lab}, }
128. Mirjam Trapp. Heuristics for Effective Predicate Refinement in CPAchecker. Master's Thesis, LMU Munich, Software Systems Lab, 2019. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{MirjamRefinement, author = {Mirjam Trapp}, title = {Heuristics for Effective Predicate Refinement in {{\sc CPAchecker}}}, year = {2019}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, LMU Munich, Software Systems Lab}, }
129. Thomas Bunk. LTL Software Model Checking in CPAchecker. Master's Thesis, LMU Munich, Software Systems Lab, 2019. Keyword(s): CPAchecker, Software Model Checking PDF Presentation
     BibTeX Entry

     @misc{ThomasLTL, author = {Thomas Bunk}, title = {{LTL} Software Model Checking in {{\sc CPAchecker}}}, year = {2019}, pdf = {https://www.sosy-lab.org/research/msc/2019.Bunk.LTL_Software_Model_Checking_in_CPAchecker.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2019-03-27_MA_LtlSoftwareModelChecking_Bunk.pdf}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, LMU Munich, Software Systems Lab}, }
130. Maximilian Wiesholler. Correctness Witness Validation using Predicate Analysis. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2019. Keyword(s): CPAchecker, Software Model Checking, Witness-Based Validation PDF Presentation
     BibTeX Entry

     @misc{WieshollerWitnesses, author = {Maximilian Wiesholler}, title = {Correctness Witness Validation using Predicate Analysis}, year = {2019}, pdf = {https://www.sosy-lab.org/research/bsc/2019.Wiesholler.Correctness_Witness_Validation_using_Predicate_Analysis.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2019-06-05_BA_CorrectnessWitnessValidationUsingPredicateAnalysis_Wiesholler.pdf}, keyword = {CPAchecker, Software Model Checking, Witness-Based Validation}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
131. Krutav Shah. Counterexample-Guided Abstraction Refinement for Interval Domain. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2019. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{ShahIntervalRefinement, author = {Krutav Shah}, title = {Counterexample-Guided Abstraction Refinement for Interval Domain}, year = {2019}, keyword = {CPAchecker,Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
132. Raphael Hagl. Hybrid Testcase Generation with CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2019. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{HaglHybridExecution, author = {Raphael Hagl}, title = {Hybrid Testcase Generation with {{\sc CPAchecker}}}, year = {2019}, keyword = {CPAchecker,Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
133. Andrea Kreppel. Implementation and Evaluation of Backwards Analyses in the Software-Verification Framework CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2019. Keyword(s): CPAchecker, Software Model Checking, Search Strategy PDF
     BibTeX Entry

     @misc{KreppelBackwardsAnalysis, author = {Andrea Kreppel}, title = {Implementation and Evaluation of Backwards Analyses in the Software-Verification Framework {{\sc CPAchecker}}}, year = {2019}, pdf = {https://www.sosy-lab.org/research/bsc/2019.Kreppel.Implementation_and_Evaluation_of_Backwards_Analyses_in_the_Software-Verification_Framework_CPAchecker.pdf}, keyword = {CPAchecker, Software Model Checking, Search Strategy}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
134. Johannes Knaut. Symbolic Heap Abstraction with Automatic Refinement. Master's Thesis, LMU Munich, Software Systems Lab, 2018. Keyword(s): CPAchecker, Software Model Checking PDF
     BibTeX Entry

     @misc{JohannesSymbolicHeapRefinement, author = {Johannes Knaut}, title = {Symbolic Heap Abstraction with Automatic Refinement}, year = {2018}, pdf = {https://www.sosy-lab.org/research/msc/2018.Knaut.Symbolic_Heap_Abstraction_with_Automatic_Refinement.pdf}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, LMU Munich, Software Systems Lab}, }
135. Martin Spiessl. Configurable Software Verification based on Slicing Abstractions. Master's Thesis, LMU Munich, Software Systems Lab, 2018. Keyword(s): CPAchecker, Software Model Checking PDF
     BibTeX Entry

     @misc{MartinSplitting, author = {Martin Spiessl}, title = {Configurable Software Verification based on Slicing Abstractions}, year = {2018}, pdf = {https://www.sosy-lab.org/research/msc/2018.Spiessl.Configurable_Software_Verification_based_on_Slicing_Abstractions.pdf}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, LMU Munich, Software Systems Lab}, }
136. Thomas Lemberger. Abstraction Refinement for Model Checking: Program Slicing + CEGAR. Master's Thesis, LMU Munich, Software Systems Lab, 2018. Keyword(s): CPAchecker, Software Model Checking PDF
     BibTeX Entry

     @misc{ThomasSlicing, author = {Thomas Lemberger}, title = {Abstraction Refinement for Model Checking: Program Slicing + {CEGAR}}, year = {2018}, pdf = {https://www.sosy-lab.org/research/msc/2018.Lemberger.Abstraction_Refinement_for_Model_Checking_Program_Slicing_and_Cegar.pdf}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, LMU Munich, Software Systems Lab}, }
137. Matthias Gerlach. Newton Refinement as Alternative to Craig Interpolation in CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2018. Keyword(s): CPAchecker, Software Model Checking PDF Presentation
     BibTeX Entry

     @misc{GerlachNewtonRefinement, author = {Matthias Gerlach}, title = {Newton Refinement as Alternative to {Craig} Interpolation in {{\sc CPAchecker}}}, year = {2018}, pdf = {https://www.sosy-lab.org/research/bsc/2018.Gerlach.Newton_Refinement_as_Alternative_to_Craig_Interpolation_in_CPAchecker.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2019-01-09_BA_NewtonRefinementAsAlternativeToCraigInterpolationInCPAchecker_Gerlach.pdf}, keyword = {CPAchecker,Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
138. Flutura Estler. Heuristics-Based Selection of Verification Configurations. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2018. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{EstlerHeuristic, author = {Flutura Estler}, title = {Heuristics-Based Selection of Verification Configurations}, year = {2018}, keyword = {CPAchecker,Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
139. Dominik Friedrich. Konzeption, Umsetzung und Visualisierung von statistischen Daten in CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2018. Keyword(s): CPAchecker
     BibTeX Entry

     @misc{FriedrichStatistics, author = {Dominik Friedrich}, title = {{Konzeption, Umsetzung und Visualisierung von statistischen Daten in CPAchecker}}, year = {2018}, keyword = {CPAchecker}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
140. Moritz Buhl. Application of Software Verification to OpenBSD Network Modules. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2018. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{BuhlOpenBSD, author = {Moritz Buhl}, title = {Application of Software Verification to {{\sc OpenBSD}} Network Modules}, year = {2018}, keyword = {CPAchecker,Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
141. Karam Shabita. String Analysis for Java Programs in CPAchecker. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2018. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{SharamStrings, author = {Karam Shabita}, title = {String Analysis for {Java} Programs in {{\sc CPAchecker}}}, year = {2018}, keyword = {CPAchecker,Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
142. Philipp Wendler. Towards Practical Predicate Analysis. PhD Thesis, University of Passau, Software Systems Lab, 2017. Keyword(s): Benchmarking, CPAchecker, Software Model Checking Publisher's Version PDF Presentation Supplement
     BibTeX Entry

     @misc{PhilippPredicateAnalysis, author = {Philipp Wendler}, title = {Towards Practical Predicate Analysis}, year = {2017}, url = {https://www.sosy-lab.org/research/phd/wendler/}, pdf = {https://www.sosy-lab.org/research/phd/2017.Wendler.Towards_Practical_Predicate_Analysis.pdf}, presentation = {https://www.sosy-lab.org/research/prs/2017-11-20_RigorosumWendler_TowardsPracticalPredicateAnalysis.pdf}, keyword = {Benchmarking,CPAchecker,Software Model Checking}, annote = {Nominated for the <a href="https://gi.de/aktuelles/wettbewerbe/dissertationspreis/">Dissertation award 2017</a> of the German <a href="https://gi.de/">Gesellschaft f&uuml;r Informatik (GI)</a>}, howpublished = {PhD Thesis, University of Passau, Software Systems Lab}, urn = {urn:nbn:de:bvb:739-opus4-5098}, }
     Additional Infos

     Nominated for the Dissertation award 2017 of the German Gesellschaft für Informatik (GI)
143. Stefan Löwe. Effective Approaches to Abstraction Refinement for Automatic Software Verification. PhD Thesis, University of Passau, Software Systems Lab, 2017. Keyword(s): CPAchecker, Software Model Checking Publisher's Version PDF Supplement
     BibTeX Entry

     @misc{StefanValueDomain, author = {Stefan L{\"{o}}we}, title = {Effective Approaches to Abstraction Refinement for Automatic Software Verification}, year = {2017}, url = {https://www.sosy-lab.org/research/phd/loewe/}, pdf = {https://www.sosy-lab.org/research/phd/2017.Loewe.Effective_Approaches_to_Abstraction_Refinement_for_Automatic_Software_Verification.pdf}, keyword = {CPAchecker,Software Model Checking}, howpublished = {PhD Thesis, University of Passau, Software Systems Lab}, urn = {urn:nbn:de:bvb:739-opus4-4815}, }
144. Evgeny Dunaev. Entwurf und Implementierung einer Abstraktionsschicht für Zuweisungs-basierte Analysen. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2017. Keyword(s): CPAchecker, Software Model Checking, Refactoring
     BibTeX Entry

     @misc{DunaevUnifyingAnalysis, author = {Evgeny Dunaev}, title = {{Entwurf und Implementierung einer Abstraktionsschicht f{\"u}r Zuweisungs-basierte Analysen}}, year = {2017}, keyword = {CPAchecker,Software Model Checking,Refactoring}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
145. Deyan Ivanov. Interactive Visualization of Verification Results from CPAchecker with D3. Bachelor's Thesis, LMU Munich, Software Systems Lab, 2017. Keyword(s): CPAchecker, Software Model Checking PDF
     BibTeX Entry

     @misc{IvanovVisualization, author = {Deyan Ivanov}, title = {Interactive Visualization of Verification Results from {{\sc CPAchecker}} with {{\sc D3}}}, year = {2017}, pdf = {https://www.sosy-lab.org/research/bsc/2017.Ivanov.Interactive_Visualization_of_Verification_Results_from_CPAchecker_with_D3.pdf}, keyword = {CPAchecker,Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, LMU Munich, Software Systems Lab}, }
146. Gernot Zoerneck. Implementing PDR in CPAchecker. Bachelor's Thesis, University of Passau, Software Systems Lab, 2017. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{ZoerneckPDR, author = {Gernot Zoerneck}, title = {Implementing {PDR} in {{\sc CPAchecker}}}, year = {2017}, keyword = {CPAchecker,Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, University of Passau, Software Systems Lab}, }
147. Thomas Stieglmaier. Augmenting Predicate Analysis with Auxiliary Invariants. Master's Thesis, University of Passau, Software Systems Lab, 2016. Keyword(s): CPAchecker, Software Model Checking PDF Supplement
     BibTeX Entry

     @misc{ThomasInvariants, author = {Thomas Stieglmaier}, title = {Augmenting Predicate Analysis with Auxiliary Invariants}, year = {2016}, url = {https://www.sosy-lab.org/research/msc/stieglmaier}, pdf = {https://www.sosy-lab.org/research/msc/2016.Stieglmaier.Augmenting_Predicate_Analysis_with_Auxiliary_Invariants.pdf}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, University of Passau, Software Systems Lab}, }
148. Sebastian Ott. Implementing a Termination Analysis using Configurable Software Analysis. Master's Thesis, University of Passau, Software Systems Lab, 2016. Keyword(s): CPAchecker, Software Model Checking PDF
     BibTeX Entry

     @misc{SebastianTermination, author = {Sebastian Ott}, title = {Implementing a Termination Analysis using Configurable Software Analysis}, year = {2016}, pdf = {https://www.sosy-lab.org/research/msc/2016.Ott.Implementing_a_Termination_Analysis_using_Configurable_Program_Analysis.pdf}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, University of Passau, Software Systems Lab}, }
149. Stefan Weinzierl. Configurable Pointer-Alias Analysis in CPAchecker. Bachelor's Thesis, University of Passau, Software Systems Lab, 2016. Keyword(s): CPAchecker, Software Model Checking PDF
     BibTeX Entry

     @misc{WeinzierlPointerAliasing, author = {Stefan Weinzierl}, title = {Configurable Pointer-Alias Analysis in {{\sc CPAchecker}}}, year = {2016}, pdf = {https://www.sosy-lab.org/research/bsc/2016.Weinzierl.Configurable_Pointer-Alias_Analysis_for_CPAchecker.pdf}, keyword = {CPAchecker,Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, University of Passau, Software Systems Lab}, }
150. Maximilian Syri. Verification of Concurrent Programs by CFA Sequentialization. Bachelor's Thesis, University of Passau, Software Systems Lab, 2016. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{SyriConcurrency, author = {Maximilian Syri}, title = {Verification of Concurrent Programs by {CFA} Sequentialization}, year = {2016}, keyword = {CPAchecker,Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, University of Passau, Software Systems Lab}, }
151. Stephan Lukasczyk. Unbounded Heap Support for CPAchecker's Predicate Analysis Using SMT Arrays. Bachelor's Thesis, University of Passau, Software Systems Lab, 2016. Keyword(s): CPAchecker, Software Model Checking Supplement
     BibTeX Entry

     @misc{LukasczykPredicateHeap, author = {Stephan Lukasczyk}, title = {Unbounded Heap Support for {{\sc CPAchecker}}'s Predicate Analysis Using {SMT} Arrays}, year = {2016}, url = {https://research.lukasczyk.me/heaparray/}, keyword = {CPAchecker,Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, University of Passau, Software Systems Lab}, }
152. Magdalena Murr. Towards Understandable CPAchecker Counterexamples. Bachelor's Thesis, University of Passau, Software Systems Lab, 2016. Keyword(s): CPAchecker, Software Model Checking PDF
     BibTeX Entry

     @misc{MurrCounterexampleReport, author = {Magdalena Murr}, title = {Towards Understandable {{\sc CPAchecker}} Counterexamples}, year = {2016}, pdf = {https://www.sosy-lab.org/research/bsc/2016.Murr.Towards_Understandable_CPAchecker_Counterexamples.pdf}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Bachelor's Thesis, University of Passau, Software Systems Lab}, subject = {Mobile and Embedded Systems}, }
153. Karlheinz Friedberger. Block-Abstraction Memoization as an Approach to Verify Recursive Procedures. Master's Thesis, University of Passau, Software Systems Lab, 2015. Keyword(s): CPAchecker, Software Model Checking PDF
     BibTeX Entry

     @misc{KarlheinzBAMRecursion, author = {Karlheinz Friedberger}, title = {Block-Abstraction Memoization as an Approach to Verify Recursive Procedures}, year = {2015}, pdf = {https://www.sosy-lab.org/research/msc/2015.Friedberger.Block-Abstraction_Memoization_as_an_Approach_to_Verify_Recursive_Procedures.pdf}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, University of Passau, Software Systems Lab}, }
154. Thomas Lemberger. Efficient Symbolic Execution using CEGAR over Two Abstract Domains. Bachelor's Thesis, University of Passau, Software Systems Lab, 2015. Keyword(s): CPAchecker, Software Model Checking PDF
     BibTeX Entry

     @misc{ThomasSymbolicExecution, author = {Thomas Lemberger}, title = {Efficient Symbolic Execution using {CEGAR} over Two Abstract Domains}, year = {2015}, pdf = {https://www.sosy-lab.org/research/bsc/2015.Lemberger.Efficient_Symbolic_Execution_using_CEGAR_over_Two_Abstract_Domains.pdf}, keyword = {CPAchecker,Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, University of Passau, Software Systems Lab}, }
155. Thomas Stieglmaier. Octagon-Based Software Verification with CPAchecker. Bachelor's Thesis, University of Passau, Software Systems Lab, 2014. Keyword(s): CPAchecker, Software Model Checking PDF
     BibTeX Entry

     @misc{ThomasOctagon, author = {Thomas Stieglmaier}, title = {Octagon-Based Software Verification with {{\sc CPAchecker}}}, year = {2014}, pdf = {https://www.sosy-lab.org/research/bsc/2014.Stieglmaier.Octagon-Based_Software_Verification_with_CPAchecker.pdf}, keyword = {CPAchecker,Software Model Checking}, field = {Internet Computing}, howpublished = {Bachelor's Thesis, University of Passau, Software Systems Lab}, }
156. Georg Dresler. A Google-App-Engine Implementation for CPAchecker. Bachelor's Thesis, University of Passau, Software Systems Lab, 2014. Keyword(s): CPAchecker, Software Model Checking Supplement
     BibTeX Entry

     @misc{DreslerAppEngine, author = {Georg Dresler}, title = {A Google-App-Engine Implementation for {{\sc CPAchecker}}}, year = {2014}, url = {https://www.sosy-lab.org/download/appengine.pdf}, keyword = {CPAchecker,Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, University of Passau, Software Systems Lab}, }
157. Matthias Dangl. Light-Weight Invariant Generation for Software Verification with CPAchecker. Master's Thesis, University of Passau, Software Systems Lab, 2013. Keyword(s): CPAchecker, Software Model Checking PDF
     BibTeX Entry

     @misc{MatthiasInvariantGeneration, author = {Matthias Dangl}, title = {Light-Weight Invariant Generation for Software Verification with {{\sc CPAchecker}}}, year = {2013}, pdf = {https://www.sosy-lab.org/research/msc/2015.Dangl.Light-Weight_Invariant_Generation_for_Software_Verification_with_CPAchecker.pdf}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, University of Passau, Software Systems Lab}, }
158. Matthias Dittrich. Bit-Precise Predicate Analysis with CPAchecker. Bachelor's Thesis, University of Passau, Software Systems Lab, 2013. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{DittrichBitprecisePredicate, author = {Matthias Dittrich}, title = {Bit-Precise Predicate Analysis with {{\sc CPAchecker}}}, year = {2013}, keyword = {CPAchecker,Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, University of Passau, Software Systems Lab}, }
159. Christopher Jahn. Implementation of a CFA and ARG Visualization and Navigation Tool in Java. Master's Thesis, University of Passau, Software Systems Lab, 2012. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{JahnVisualization, author = {Christopher Jahn}, title = {Implementation of a {CFA} and {ARG} Visualization and Navigation Tool in {Java}}, year = {2012}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, University of Passau, Software Systems Lab}, }
160. Andreas Stahlbauer. Block-Encoding Strategies for Predicate Analysis: An Experimental Study. Master's Thesis, University of Passau, Software Systems Lab, 2012. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{StahlbauerStrategies, author = {Andreas Stahlbauer}, title = {Block-Encoding Strategies for Predicate Analysis: An Experimental Study}, year = {2012}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, University of Passau, Software Systems Lab}, permit = {Permission for making available online not granted (Dirk asked on 2020-07-17 and received denial on 2020-07-18)}, }
161. Peter Häring. A Comparative Study of Software Measures as Problem-Predictors. Master's Thesis, University of Passau, Software Systems Lab, 2012. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{HaeringMeasures, author = {Peter H{\"a}ring}, title = {A Comparative Study of Software Measures as Problem-Predictors}, year = {2012}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, University of Passau, Software Systems Lab}, permit = {}, }
162. Alexander Driemeyer. Software-Verifikation von Java-Programmen in CPAchecker. Bachelor's Thesis, University of Passau, Software Systems Lab, 2012. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{DriemeyerJava, author = {Alexander Driemeyer}, title = {Software-Verifikation von Java-Programmen in CPAchecker}, year = {2012}, keyword = {CPAchecker,Software Model Checking}, field = {Computer Science}, howpublished = {Bachelor's Thesis, University of Passau, Software Systems Lab}, }
163. Karlheinz Friedberger. Ein typbasierter Ansatz zur Kombination verschiedener Verifikationstechniken. Bachelor's Thesis, University of Passau, Software Systems Lab, 2012. Keyword(s): CPAchecker, Software Model Checking PDF
     BibTeX Entry

     @misc{KarlheinzDomainTypes, author = {Karlheinz Friedberger}, title = {{Ein typbasierter Ansatz zur Kombination verschiedener Verifikationstechniken}}, year = {2012}, pdf = {https://www.sosy-lab.org/research/bsc/2012.Friedberger.Ein_typbasierter_Ansatz_zur_Kombination_verschiedener_Verifikationstechniken.pdf}, keyword = {CPAchecker,Software Model Checking}, annote = {Won the yearly award of the chamber of industry and commerce of Lower Bavaria (IHK Niederbayern) for an excellent Bachelor's thesis}, field = {Computer Science}, howpublished = {Bachelor's Thesis, University of Passau, Software Systems Lab}, }
     Additional Infos

     Won the yearly award of the chamber of industry and commerce of Lower Bavaria (IHK Niederbayern) for an excellent Bachelor's thesis
164. Mehmet Erkan Keremoglu. Towards Scalable Software Analyisis Using Combinations and Conditions with CPAchecker. PhD Thesis, Simon Fraser University, Software Systems Lab, 2011. Keyword(s): CPAchecker, Software Model Checking PDF Supplement
     BibTeX Entry

     @misc{ErkanCMC, author = {Mehmet Erkan Keremoglu}, title = {Towards Scalable Software Analyisis Using Combinations and Conditions with {{\sc CPAchecker}}}, year = {2011}, url = {https://summit.sfu.ca/item/12363}, pdf = {http://summit.sfu.ca/system/files/iritems1/12363/etd7320_MKeremoglu.pdf}, keyword = {CPAchecker,Software Model Checking}, annote = {Now at Microsoft, Redmond, USA}, howpublished = {PhD Thesis, Simon Fraser University, Software Systems Lab}, }
     Additional Infos

     Now at Microsoft, Redmond, USA
165. Andra-Maria Babau. Modeling and Verification of Airport Security Processes using BPMN and Protocol Interfaces: A Case Study. Master's Thesis, University of Passau, Software Systems Lab, 2011. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{BabauProtocolInterfaces, author = {Andra-Maria Babau}, title = {Modeling and Verification of Airport Security Processes using {BPMN} and Protocol Interfaces: A Case Study}, year = {2011}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, University of Passau, Software Systems Lab}, }
166. Dmitry Balzer. Werkzeugunterstützung für Verstehen und Monitoring von Software-Abhängigkeiten. Master's Thesis, University of Passau, Software Systems Lab, 2010. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{BalzerDependencies, author = {Dmitry Balzer}, title = {{Werkzeugunterst{\"u}tzung f{\"u}r Verstehen und Monitoring von Software-Abh{\"a}ngigkeiten}}, year = {2010}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, University of Passau, Software Systems Lab}, }
167. Alexander von Rhein. Verification Tasks for Software Model Checking. Master's Thesis, University of Passau, Software Systems Lab, 2010. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{AlexQuery, author = {Alexander~von~Rhein}, title = {Verification Tasks for Software Model Checking}, year = {2010}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, University of Passau, Software Systems Lab}, }
168. Ashgan Fararooy. Performing Static Structure Analysis using Software Dependencies. Master's Thesis, Simon Fraser University, Software Systems Lab, 2010. Keyword(s): CPAchecker, Software Model Checking
     BibTeX Entry

     @misc{FararooyStructureAnalysis, author = {Ashgan Fararooy}, title = {Performing Static Structure Analysis using Software Dependencies}, year = {2010}, keyword = {CPAchecker,Software Model Checking}, howpublished = {Master's Thesis, Simon Fraser University, Software Systems Lab}, }
169. Philipp Wendler. Software Verification based on Adjustable Large-Block Encoding. Master's Thesis, University of Passau, Software Systems Lab, 2010. Keyword(s): CPAchecker, Software Model Checking PDF
     BibTeX Entry

     @misc{PhilippABE, author = {Philipp Wendler}, title = {Software Verification based on Adjustable Large-Block Encoding}, year = {2010}, pdf = {https://www.sosy-lab.org/research/msc/2010.Wendler.Software_Verification_based_on_Adjustable_Large-Block_Encoding.pdf}, keyword = {CPAchecker,Software Model Checking}, annote = {Won the NRW Young Scientist Award 2010 in Dynamic Intelligent Systems, received for the Faculty Award 2011 for best Master's thesis, and the yearly award of the Chamber of Industry and Commerce of Lower Bavaria (IHK Niederbayern) for an excellent Master's thesis}, howpublished = {Master's Thesis, University of Passau, Software Systems Lab}, }
     Additional Infos

     Won the NRW Young Scientist Award 2010 in Dynamic Intelligent Systems, received for the Faculty Award 2011 for best Master's thesis, and the yearly award of the Chamber of Industry and Commerce of Lower Bavaria (IHK Niederbayern) for an excellent Master's thesis
170. CPAchecker: Configurable Software Verification. 2007. Keyword(s): Software Development Project, CPAchecker, Software Model Checking Supplement
     BibTeX Entry

     @misc{CPAchecker, title = {{{\sc CPAchecker}}: Configurable Software Verification}, year = {2007}, url = {http://www.sosy-lab.org/~dbeyer/CPAchecker/}, keyword = {Software Development Project,CPAchecker,Software Model Checking}, role = {Principal designer, architect, implementation, and maintenance}, }