research-article

A data-driven CHC solver

Authors:

Stephen Magill,

Suresh JagannathanAuthors Info & Claims

PLDI 2018: Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 707 - 721

https://doi.org/10.1145/3192366.3192416

Published: 11 June 2018 Publication History

Abstract

We present a data-driven technique to solve Constrained Horn Clauses (CHCs) that encode verification conditions of programs containing unconstrained loops and recursions. Our CHC solver neither constrains the search space from which a predicate's components are inferred (e.g., by constraining the number of variables or the values of coefficients used to specify an invariant), nor fixes the shape of the predicate itself (e.g., by bounding the number and kind of logical connectives). Instead, our approach is based on a novel machine learning-inspired tool chain that synthesizes CHC solutions in terms of arbitrary Boolean combinations of unrestricted atomic predicates. A CEGAR-based verification loop inside the solver progressively samples representative positive and negative data from recursive CHCs, which is fed to the machine learning tool chain. Our solver is implemented as an LLVM pass in the SeaHorn verification framework and has been used to successfully verify a large number of nontrivial and challenging C programs from the literature and well-known benchmark suites (e.g., SV-COMP).

Supplementary Material

WEBM File (p707-zhu.webm)

Download
112.75 MB

References

[1]

Aws Albarghouthi, Arie Gurfinkel, and Marsha Chechik. 2012. Whale: An Interpolation-based Algorithm for Inter-procedural Verification. In Proceedings of the 13th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI'12). Springer-Verlag, Berlin, Heidelberg, 39-55.

Digital Library

[2]

Aaron R. Bradley. 2011. SAT-based Model Checking Without Unrolling. In Proceedings of the 12th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI'11). Springer-Verlag, Berlin, Heidelberg, 70-87.

Digital Library

[3]

Adrien Champion, Tomoya Chiba, Naoki Kobayashi, and Ryosuke Sato. 2018. ICE-based Refinement Type Discovery for Higher-Order Functional Programs. In Proceedings of the Theory and Practice of Software, 24th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'18). Springer-Verlag New York, Inc., New York, NY, USA.

[4]

Chih-Chung Chang and Chih-Jen Lin. 2011. LIBSVM: A Library for Support Vector Machines. ACM Trans. Intell. Syst. Technol. 2, 3, Article 27 (May 2011), 27 pages.

Digital Library

[5]

Edmund Clarke, Armin Biere, Richard Raimi, and Yunshan Zhu. 2001. Bounded Model Checking Using Satisfiability Solving. Form. Methods Syst. Des. 19, 1 (July 2001), 7-34.

Digital Library

[6]

Benjamin Cosman and Ranjit Jhala. 2017. Local Refinement Typing. Proc. ACM Program. Lang. 1, ICFP, Article 26 (Aug. 2017), 27 pages.

Digital Library

[7]

Leonardo De Moura and Nikolaj Bjurner. 2008. Z3: An Efficient SMT Solver. In Proceedings of the Theory and Practice of Software, 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'08). Springer-Verlag, Berlin, Heidelberg, 337-340.

Digital Library

[8]

Isil Dillig, Thomas Dillig, Boyang Li, and Ken McMillan. 2013. Inductive Invariant Generation via Abductive Inference. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications (OOPSLA '13). ACM, New York, NY, USA, 443-456.

Digital Library

[9]

Yoav Freund and Robert E. Schapire. 1999. Large Margin Classification Using the Perceptron Algorithm. Mach. Learn. 37, 3 (Dec. 1999), 277-296.

Digital Library

[10]

Pranav Garg, Christof Loding, P. Madhusudan, and Daniel Neider. 2014. ICE: A Robust Learning Framework for learning Invariants. In Proceedings of the 26th International Conference on Computer Aided Verification - Volume 8559. Springer-Verlag New York, Inc., New York, NY, USA, 69-87.

Digital Library

[11]

Pranav Garg, Daniel Neider, P. Madhusudan, and Dan Roth. 2016. Learning Invariants Using Decision Trees and Implication Counterexamples. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '16). ACM, New York, NY, USA, 499-512.

Digital Library

[12]

Timon Gehr, Dimitar Dimitrov, and Martin T. Vechev. 2015. Learning Commutativity Specifications. In Computer Aided Verification - 27th International Conference, CAV 2015, San Francisco, CA, USA, Proceedings, Part I. Springer-Verlag New York, Inc., New York, NY, USA, 307-323.

[13]

Sergey Grebenshchikov, Nuno P. Lopes, Corneliu Popeea, and Andrey Rybalchenko. 2012. Synthesizing Software Verifiers from Proof Rules. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '12). ACM, New York, NY, USA, 405-416.

Digital Library

[14]

Ashutosh Gupta and Andrey Rybalchenko. 2009. InvGen: An Efficient Invariant Generator. In Proceedings of the 21st International Conference on Computer Aided Verification (CAV '09). Springer-Verlag, Berlin, Heidelberg, 634-640.

Digital Library

[15]

Arie Gurfinkel, Temesghen Kahsai, Anvesh Komuravelli, and Jorge A. Navas. 2015. The SeaHorn Verification Framework. In Computer Aided Verification - 27th International Conference, CAV 2015, San Francisco, CA, USA, Proceedings, Part I. Springer-Verlag New York, Inc., New York, NY, USA, 343-361.

[16]

Matthias Heizmann, Jochen Hoenicke, and Andreas Podelski. 2010. Nested Interpolants. In Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '10). ACM, New York, NY, USA, 471-482.

Digital Library

[17]

Kry?tof Hoder and Nikolaj Bjurner. 2012. Generalized Property Directed Reachability. In Proceedings of the 15th International Conference on Theory and Applications of Satisfiability Testing (SAT'12). Springer-Verlag, Berlin, Heidelberg, 157-171.

Digital Library

[18]

Temesghen Kahsai, Philipp Rummer, Huascar Sanchez, and Martin Schaf. 2016. JayHorn: A Framework for Verifying Java programs. In Computer Aided Verification - 28th International Conference, CAV 2016, Toronto, ON, Canada, Proceedings, Part I. Springer-Verlag New York, Inc., New York, NY, USA, 352-358.

[19]

Anvesh Komuravelli, Arie Gurfinkel, and Sagar Chaki. 2014. SMT-Based Model Checking for Recursive Programs. In Proceedings of the 26th International Conference on Computer Aided Verification - Volume 8559. Springer-Verlag New York, Inc., New York, NY, USA, 17-34.

Digital Library

[20]

Siddharth Krishna, Christian Puhrsch, and Thomas Wies. 2015. Learning Invariants using Decision Trees. http://cs.nyu.edu/~siddharth/invariants_dt.pdf.

[21]

Jiaying Li, Jun Sun, Li Li, Quang Loc Le, and Shang-Wei Lin. 2017. Automatic Loop-invariant Generation and Refinement Through Selective Sampling. In Proceedings of the 32Nd IEEE/ACM International Conference on Automated Software Engineering (ASE 2017). IEEE Press, Piscataway, NJ, USA, 782-792.

Digital Library

[22]

Kenneth L. McMillan. 2003. Interpolation and SAT-Based Model Checking. In Computer Aided Verification, 15th International Conference, CAV 2003, Boulder, CO, USA, Proceedings. Springer-Verlag, Berlin, Heidelberg, 1-13.

[23]

Kenneth L. McMillan. 2006. Lazy Abstraction with Interpolants. In Proceedings of the 18th International Conference on Computer Aided Verification (CAV'06). Springer-Verlag, Berlin, Heidelberg, 123-136.

Digital Library

[24]

Kenneth L. Mcmillan. 2014. Lazy Annotation Revisited. In Proceedings of the 26th International Conference on Computer Aided Verification - Volume 8559. Springer-Verlag New York, Inc., New York, NY, USA, 243-259.

Digital Library

[25]

K. L. McMillan and A. Rybalchenko. 2013. Computing Relational Fixed Points Using Interpolation. https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/MSR-TR-2013-6.pdf.

[26]

LinearArbitrary. 2018. https://github.com/GaloisInc/LinearArbitrary-SeaHorn/.

[27]

ThanhVu Nguyen, Timos Antonopoulos, Andrew Ruef, and Michael Hicks. 2017. Counterexample-guided Approach to Finding Numerical Invariants. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering (ESEC/FSE 2017). ACM, New York, NY, USA, 605-615.

Digital Library

[28]

ThanhVu Nguyen, Deepak Kapur, Westley Weimer, and Stephanie Forrest. 2014. Using Dynamic Analysis to Generate Disjunctive Invariants. In Proceedings of the 36th International Conference on Software Engineering (ICSE 2014). ACM, New York, NY, USA, 608-619.

Digital Library

[29]

Saswat Padhi, Rahul Sharma, and Todd Millstein. 2016. Data-driven Precondition Inference with Learned Features. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '16). ACM, New York, NY, USA, 42-56.

Digital Library

[30]

John C. Platt. 1999. Advances in Kernel Methods. MIT Press, Cambridge, MA, USA, Chapter Fast Training of Support Vector Machines Using Sequential Minimal Optimization, 185-208.

Digital Library

[31]

J. Ross Quinlan. 1993. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.

Digital Library

[32]

Philipp Rummer, Hossein Hojjat, and Viktor Kuncak. 2013. Disjunctive Interpolants for Horn-clause Verification. In Proceedings of the 25th International Conference on Computer Aided Verification (CAV'13). Springer-Verlag, Berlin, Heidelberg, 347-363.

Digital Library

[33]

Sriram Sankaranarayanan, Swarat Chaudhuri, Franjo Ivancic, and Aarti Gupta. 2008. Dynamic Inference of Likely Data Preconditions over Predicates by Tree Learning. In Proceedings of the 2008 International Symposium on Software Testing and Analysis (ISSTA '08). ACM, New York, NY, USA, 295-306.

Digital Library

[34]

C. E. Shannon. 2001. A Mathematical Theory of Communication. SIGMOBILE Mob. Comput. Commun. Rev. 5, 1 (Jan. 2001), 3-55.

Digital Library

[35]

Rahul Sharma and Alex Aiken. 2014. From Invariant Checking to Invariant Inference Using Randomized Search. In Proceedings of the 26th International Conference on Computer Aided Verification - Volume 8559. Springer-Verlag New York, Inc., New York, NY, USA, 88-105.

Digital Library

[36]

Rahul Sharma, Saurabh Gupta, Bharath Hariharan, Alex Aiken, Percy Liang, and Aditya V. Nori. 2013. A Data Driven Approach for Algebraic Loop Invariants. In Proceedings of the 22Nd European Conference on Programming Languages and Systems (ESOP'13). Springer-Verlag, Berlin, Heidelberg, 574-592.

Digital Library

[37]

Rahul Sharma, Saurabh Gupta, Bharath Hariharan, Alex Aiken, and Aditya V. Nori. 2013. Verification as Learning Geometric Concepts. In Static Analysis - 20th International Symposium, SAS 2013, Seattle, WA, USA, Proceedings. Springer-Verlag, Berlin, Heidelberg, 388-411.

[38]

Rahul Sharma, Aditya V. Nori, and Alex Aiken. 2012. Interpolants As Classifiers. In Proceedings of the 24th International Conference on Computer Aided Verification (CAV'12). Springer-Verlag, Berlin, Heidelberg, 71-87.

Digital Library

[39]

SV-COMP. 2017. http://sv-comp.sosy-lab.org/2017/.

[40]

He Zhu, Gustavo Petri, and Suresh Jagannathan. 2016. Automatically Learning Shape Specifications. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '16). ACM, New York, NY, USA, 491-507.

Digital Library

Cited By

Zhou ZYe QDelaware BJagannathan S(2024)A HAT Trick: Automatically Verifying Representation Invariants using Symbolic Finite AutomataProceedings of the ACM on Programming Languages10.1145/36564338:PLDI(1387-1411)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656433
Guo YYao PZhang CChristakis MPradel M(2024)Precise Compositional Buffer Overflow Detection via Heap DisjointnessProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652110(63-75)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3652110
Frohn FGiesl J(2024)Integrating Loop Acceleration Into Bounded Model CheckingFormal Methods10.1007/978-3-031-71162-6_4(73-91)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71162-6_4
Show More Cited By

Index Terms

A data-driven CHC solver
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Formal software verification
  2. Software organization and properties
    1. Software functional properties
      1. Formal methods
        Automated static analysis

Recommendations

A data-driven CHC solver
PLDI '18

We present a data-driven technique to solve Constrained Horn Clauses (CHCs) that encode verification conditions of programs containing unconstrained loops and recursions. Our CHC solver neither constrains the search space from which a predicate's ...
Ivy: safety verification by interactive generalization
PLDI '16: Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation

Despite several decades of research, the problem of formal verification of infinite-state systems has resisted effective automation. We describe a system --- Ivy --- for interactively verifying safety of infinite-state systems. Ivy's key principle is ...
Ivy: safety verification by interactive generalization
PLDI '16

Despite several decades of research, the problem of formal verification of infinite-state systems has resisted effective automation. We describe a system --- Ivy --- for interactively verifying safety of infinite-state systems. Ivy's key principle is ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI 2018: Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2018

825 pages

ISBN:9781450356985

DOI:10.1145/3192366

General Chair:
Jeffrey S. Foster
University of Maryland at College Park, USA
,
Program Chair:
Dan Grossman
University of Washington, USA

ACM SIGPLAN Notices Volume 53, Issue 4
PLDI '18
April 2018
834 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/3296979
Editor:
Matthew Fluet
Rodchester Institude of Technology
Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Conference

PLDI '18

Sponsor:

SIGPLAN

PLDI '18: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 18 - 22, 2018

PA, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
812
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou ZYe QDelaware BJagannathan S(2024)A HAT Trick: Automatically Verifying Representation Invariants using Symbolic Finite AutomataProceedings of the ACM on Programming Languages10.1145/36564338:PLDI(1387-1411)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656433
Guo YYao PZhang CChristakis MPradel M(2024)Precise Compositional Buffer Overflow Detection via Heap DisjointnessProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652110(63-75)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3652110
Frohn FGiesl J(2024)Integrating Loop Acceleration Into Bounded Model CheckingFormal Methods10.1007/978-3-031-71162-6_4(73-91)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71162-6_4
Itzhaky SShoham SVizel Y(2024)Hyperproperty Verification as CHC SatisfiabilityProgramming Languages and Systems10.1007/978-3-031-57267-8_9(212-241)Online publication date: 5-Apr-2024
https://doi.org/10.1007/978-3-031-57267-8_9
Park KD'Antoni LReps T(2023)Synthesizing SpecificationsProceedings of the ACM on Programming Languages10.1145/36228617:OOPSLA2(1787-1816)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622861
Yu SWang TWang JJust RFraser G(2023)Loop Invariant Inference through SMT Solving Enhanced Reinforcement LearningProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598047(175-187)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598047
Krogmeier PMadhusudan P(2023)Languages with Decidable Learning: A Meta-theoremProceedings of the ACM on Programming Languages10.1145/35860327:OOPSLA1(143-171)Online publication date: 6-Apr-2023
https://dl.acm.org/doi/10.1145/3586032
Hu GZhang WZhang H(2023)NeuroPDR: Integrating Neural Networks in the PDR Algorithm for Hardware Model Checking2023 ACM/IEEE 5th Workshop on Machine Learning for CAD (MLCAD)10.1109/MLCAD58807.2023.10299875(1-6)Online publication date: 10-Sep-2023
https://doi.org/10.1109/MLCAD58807.2023.10299875
Vediramana Krishnan HChen YShoham SGurfinkel A(2023)Global guidance for local generalization in model checkingFormal Methods in System Design10.1007/s10703-023-00412-3Online publication date: 28-Mar-2023
https://doi.org/10.1007/s10703-023-00412-3
Ikeda RSato RKobayashi N(2023)Argument Reduction of Constrained Horn Clauses Using Equality ConstraintsProgramming Languages and Systems10.1007/978-981-99-8311-7_12(246-265)Online publication date: 26-Nov-2023
https://dl.acm.org/doi/10.1007/978-981-99-8311-7_12
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents