×

Resolution proof transformation for compression and interpolation. (English) Zbl 1317.68123

Summary: Verification methods based on SAT, SMT, and theorem proving often rely on proofs of unsatisfiability as a powerful tool to extract information in order to reduce the overall effort. For example a proof may be traversed to identify a minimal reason that led to unsatisfiability, for computing abstractions, or for deriving Craig interpolants. In this paper we focus on two important aspects that concern efficient handling of proofs of unsatisfiability: compression and manipulation. First of all, since the proof size can be very large in general (exponential in the size of the input problem), it is indeed beneficial to adopt techniques to compress it for further processing. Secondly, proofs can be manipulated as a flexible preprocessing step in preparation for interpolant computation. Both these techniques are implemented in a framework that makes use of local rewriting rules to transform the proofs. We show that a careful use of the rules, combined with existing algorithms, can result in an effective simplification of the original proofs. We have evaluated several heuristics on a wide range of unsatisfiable problems deriving from SAT and SMT test cases.

MSC:

68Q60 Specification and verification (program logics, model checking, etc.)
03C40 Interpolation, preservation, definability
03F20 Complexity of proofs
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)

References:

[1] Ackermann W (1954) Solvable cases of the decision problem. Studies in logic and the foundations of mathematics. North-Holland, Amsterdam · Zbl 0056.24505
[2] Amjad H (2007) Compressing propositional refutations. Electron Notes Theor Comput Sci 185:3-15 · Zbl 1335.68222 · doi:10.1016/j.entcs.2007.05.025
[3] Amjad H (2008) Data compression for proof replay. J Autom Reason 41(3-4):193-218 · Zbl 1191.68616 · doi:10.1007/s10817-008-9109-2
[4] Amla N, McMillan K (2003) Automatic abstraction without counterexamples. In: TACAS, pp 2-17 · Zbl 1031.68520
[5] Bar-Ilan O, Fuhrmann O, Hoory S, Shacham O, Strichman O (2008) Linear-time reductions of resolution proofs. In: HVC, pp 114-128
[6] Barrett C, Nieuwenhuis R, Oliveras A, Tinelli C (2006) Splitting on demand in SAT modulo theories. In: LPAR, pp 512-526 · Zbl 1165.68480
[7] Barrett C, Sebastiani R, Seshia S, Tinelli C (2009) Satisfiability modulo theories. In: Biere A, Heule M, van Maaren H, Walsh T (eds) Handbook of satisfiability. IOS Press, Amsterdam, pp 825-885
[8] Bayardo RJ, Schrag R (1997) Using CSP look-back techniques to solve real-world SAT instances. In: AAAI/IAAI, pp 203-208
[9] Biere A, Cimatti A, Clarke E, Strichman O, Zhu Y (2003) Bounded model checking. Adv Comput 58:117-148 · doi:10.1016/S0065-2458(03)58003-2
[10] Bofill M, Nieuwenhuis R, Oliveras A, Rodrguez-Carbonell E, Rubio A (2008) A write-based solver for SAT modulo the theory of arrays. In: FMCAD, pp 101-108
[11] Boudou J, Paleo B (2013) Compression of propositional resolution proofs by lowering subproofs. In: TABLEAUX, pp 237-251 · Zbl 1401.68274
[12] Bozzano M, Bruttomesso R, Cimatti A, Junttila T, Ranise S, van Rossum P, Sebastiani R (2005) Efficient satisfiability modulo theories via delayed theory combination. In: CAV, pp 335-349 · Zbl 1081.68610
[13] Bradley AR (2011) SAT-based model checking without unrolling. In: VMCAI, pp 70-87 · Zbl 1317.68109
[14] Brummayer R, Biere A (2008) Lemmas on demand for the extensional theory of arrays. In: Workshop on SMT · Zbl 1187.68168
[15] Bruni R (2003) Approximating minimal unsatisfiable subformulae by means of adaptive core search. Discret Appl Math 130(2):85-100 · Zbl 1029.68075 · doi:10.1016/S0166-218X(02)00399-2
[16] Bruttomesso R, Pek E, Sharygina N, Tsitovich A (2010) The OpenSMT Solver. In: TACAS, pp 150-153 · JFM 60.0020.02
[17] Bruttomesso R, Rollini S, Sharygina N, Tsitovich A (2010) Flexible interpolation with local proof transformations. In: ICCAD, pp 770-777 · Zbl 1317.68123
[18] Christ J, Hoenicke J, Nutz A (2013) Proof tree preserving interpolation. In: TACAS, pp 124-138 · Zbl 1381.68152
[19] Cimatti A, Griggio A, Sebastiani R (2007) A simple and flexible way of computing small unsatisfiable cores in SAT modulo theories. In: SAT, pp 334-339 · Zbl 1214.68348
[20] Cimatti A, Griggio A, Sebastiani R (2008) Efficient interpolant generation in satisfiability modulo theories. In: TACAS, pp 397-412 · Zbl 1134.68402
[21] Cotton S (2010) Two techniques for minimizing resolution proofs. In: SAT, pp 306-312 · Zbl 1306.68140
[22] CMU Benchmarks. http://www.cs.cmu.edu/ modelcheck/bmc/bmc-benchmarks.html. Accessed 24 April 2014 · Zbl 0079.24502
[23] Craig W (1957) Three uses of the herbrand-gentzen theorem in relating model theory and proof theory. J Symb Log 22(3):269-285 · Zbl 0079.24502 · doi:10.2307/2963594
[24] de Moura L, Bjørner N (2009) Generalized, efficient array decision procedures. In: FMCAD, pp 45-52
[25] de Moura L, Rue H (2002) Lemmas on demand for satisfiability solvers. In: SAT, pp 244-251
[26] Dershowitz N, Hanna Z, Nadel A (2006) A scalable algorithm for minimal unsatisfiable core extraction. In: SAT, pp 36-41 · Zbl 1187.68538
[27] D’Silva V, Kroening D, Purandare M, Weissenbacher G (2008) Restructuring resolution refutations for interpolation. Technical report, ETH · Zbl 1191.68616
[28] D’Silva V, Kroening D, Purandare M, Weissenbacher G (2010) Interpolant strength. In: VMCAI, pp 129-145 · Zbl 1273.68225
[29] Fontaine P, Marion J, Merz S, Nieto L, Tiu A (2006) Expressiveness + automation + soundness: towards combining SMT solvers and interactive proof assistants. In: TACAS, pp 167-181 · Zbl 1180.68240
[30] Fontaine P, Merz S, Paleo B (2011) Compression of propositional resolution proofs via partial regularization. In: CADE, pp 237-251 · Zbl 1341.68188
[31] Gentzen G (1935) Untersuchungen über das logische schließen. i. Math Z 39(1):176-210 · Zbl 0010.14501 · doi:10.1007/BF01201353
[32] Goel A, Krstić S, Fuchs A (2008) Deciding array formulas with frugal axiom Instantiation. In: SMT, pp 12-17
[33] Goel A, Krstić S, Tinelli C (2009) Ground interpolation for combined theories. In: CADE, pp 183-198 · Zbl 1250.68188
[34] Goldberg E, Novikov Y (2003) Verification of proofs of unsatisfiability for CNF formulas. In: DATE, pp 10,886-10,891 · Zbl 1145.68501
[35] Gomes C, Kautz H, Sabharwal A, Selman B (2008) Satisfiability solvers. In: van Harmelen F, Lifschitz V, Porter B (eds) Handbook of knowledge representation. Elsevier, Amsterdam, pp 89-134 · Zbl 1183.68611
[36] Grégoire E, Mazure B, Piette C (2007) Local-search extraction of muses. Constraints 12(3):325-344 · Zbl 1211.90307 · doi:10.1007/s10601-007-9019-7
[37] Grumberg O, Lerda F, Ofer OS, Theobald M (2005) Proof-guided underapproximation-widening for multi-process systems. In: POPL, pp 122-131 · Zbl 1369.68259
[38] Gupta A (2012) Improved single pass algorithms for resolution proof reduction. In: ATVA, pp 107-121 · Zbl 1374.68489
[39] Henzinger T, Jhala R, Majumdar R, McMillan K (2004) Abstractions from proofs. In: POPL, pp 232-244 · Zbl 1325.68147
[40] Heule M, Hunt W, Wetzler N (2013) Trimming while checking clausal proofs. In: FMCAD · Zbl 1423.68475
[41] Huang J (2005) Mup: a minimal unsatisfiability prover. In: ASP-DAC, pp 432-437
[42] Jhala R, McMillan K (2005) Interpolant-based transition relation approximation. In: CAV, pp 39-51 · Zbl 1081.68622
[43] Krajíček J (1997) Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. J Symb Log 62(2):457-486 · Zbl 0891.03029 · doi:10.2307/2275541
[44] Lynce I, Marques-Silva J (2004) On computing minimum unsatisfiable cores. In: SAT, pp 305-310
[45] Marques-Silva J, Sakallah K (1996) GRASP—a new search algorithm for satisfiability. In: ICCAD, pp 220-227
[46] McMillan K (2003) Interpolation and SAT-based model checking. In: CAV, pp 1-13 · Zbl 1278.68184
[47] McMillan K (2004) An interpolating theorem prover. In: TACAS, pp 16-30 · Zbl 1126.68573
[48] McMillan K (2004) Applications of Craig interpolation to model checking. In: CSL, pp 22-23 · Zbl 1095.68610
[49] Mneimneh M, Lynce I, Andraus Z, Marques-Silva J, Sakallah K (2005) A branch-and-bound algorithm for extracting smallest minimal unsatisfiable formulas. In: SAT, pp 467-474 · Zbl 1128.68477
[50] Necula G (1997) Proof-carrying code. In: POPL, pp 106-119
[51] Nelson G, Oppen D (1979) Simplification by cooperating decision procedures. ACM Trans Progr Lang Syst 1(2):245-257 · Zbl 0452.68013 · doi:10.1145/357073.357079
[52] Oh Y, Mneimneh MN, Andraus ZS, Sakallah KA, Markov IL (2004) AMUSE: a minimally-unsatisfiable subformula extractor. In: DAC, pp 518-523
[53] Pudlák P (1997) Lower bounds for resolution and cutting plane proofs and monotone computations. J Symb Log 62(3):981-998 · Zbl 0945.03086 · doi:10.2307/2275583
[54] Ranise S, Tinelli C The satisfiability modulo theories library (SMT-LIB). http://www.smtlib.org. Accessed 24 April 2014
[55] Rollini S Proof transformer and interpolator for propositional logic (PeRIPLO). http://verify.inf.usi.ch/content/periplo. Accessed 24 April 2014
[56] Rollini S, Bruttomesso R, Sharygina N (2010) An efficient and flexible approach to resolution proof reduction. In: HVC, pp 182-196 · Zbl 1325.68215
[57] SAT Challenge (2012) http://baldur.iti.kit.edu/SAT-Challenge-2012/. Accessed 24 April 2014
[58] SATLIB Benchmark Suite http://www.cs.ubc.ca/ hoos/SATLIB/benchm.html . Accessed 24 April 2014
[59] Sebastiani R (2007) Lazy satisfiability modulo theories. JSAT 3:144-224 · Zbl 1145.68501
[60] Shlyakhter I, Seater R, Jackson D, Sridharan M, Taghdir M (2003) Debugging overconstrained declarative models using unsatisfiable cores. In: ASE, pp 94-105
[61] Sinz C (2007) Compressing propositional proofs by common subproof extraction. In: EUROCAST, pp 547-555
[62] Sinz C, Kaiser A, Kuchlin W (2003) Formal methods for the validation of automotive product configuration data. AI EDAM 17(1):75-97
[63] Skeptik Proof Theory Library https://github.com/Paradoxika/Skeptik. Accessed 24 April 2014 · Zbl 0945.03086
[64] Tseitin, GS; Slisenko, AO (ed.), On the complexity of derivation in the propositional calculus, 115-125 (1968), New York
[65] Van Gelder A (2008) Verifying RUP proofs of propositional unsatisfiability. In: ISAIM · Zbl 1145.68501
[66] Weber T, Amjad H (2009) Efficiently checking propositional refutations in hol theorem provers. J Appl Log 7(1):26-40 · Zbl 1171.68041 · doi:10.1016/j.jal.2007.07.003
[67] Yorsh G, Musuvathi M (2005) A combination method for generating interpolants. In: CADE, pp 353-368 · Zbl 1135.03331
[68] Zhang L, Malik S (2003) Extracting small unsatisfiable cores from unsatisfiable Boolean formulas. In: SAT · Zbl 1335.68222
[69] Zhang L, Sharad M (2003) Validating SAT solvers using an independent resolution-based checker: practical implementations and other applications. In: DATE, pp 10,880-10,885
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.