×

SMT-based verification of program changes through summary repair. (English) Zbl 07757154

Summary: This article provides an innovative approach for verification by model checking of programs that undergo continuous changes. To tackle the problem of repeating the entire model checking for each new version of the program, our approach verifies programs incrementally. It reuses computational history of the previous program version, namely function summaries. In particular, the summaries are over-approximations of the bounded program behaviors. Whenever reusing of summaries is not possible straight away, our algorithm repairs the summaries to maximize the chance of reusability of them for subsequent runs. We base our approach on satisfiability modulo theories (SMT) to take full advantage of lightweight modeling approach and at the same time the ability to provide concise function summarization. Our approach leverages pre-computed function summaries in SMT to localize the checks of changed functions. Furthermore, to exploit the trade-off between precision and performance, our approach relies on the use of an SMT solver, not only for underlying reasoning, but also for program modeling and the adjustment of its precision. On the benchmark suite of primarily Linux device drivers versions, we demonstrate that our algorithm achieves an order of magnitude speedup compared to prior approaches.

MSC:

68-XX Computer science

References:

[1] Clarke EM, Emerson EA (1981) Design and synthesis of synchronization skeletons using branching-time temporal logic. In: Workshop on logics of programs, pp 52-71. Springer, Heidelberg · Zbl 0546.68014
[2] Queille J, Sifakis J (1982) Specification and verification of concurrent systems in CESAR. In: 5th International symposium on programming, pp 337-351 · Zbl 0482.68028
[3] Biere A, Cimatti A, Clarke EM, Zhu Y (1999) Symbolic model checking without BDDs. In: TACAS 1999, vol 1579, pp 193-207. Springer, Heidelberg
[4] Fedyukovich G, Sery O, Sharygina N (2013) eVolCheck: Incremental upgrade checker for C. In: TACAS 2013, vol 7795, pp 292-307. Springer, Heidelberg · Zbl 1381.68159
[5] Barrett C, Sebastiani R, Seshia S, Tinelli C (2009) Satisfiability modulo theories, vol 185, 1st edn., pp 825-885
[6] de Moura LM, Bjørner N (2009) Satisfiability modulo theories: An appetizer. In: SBMF 2009. LNCS, vol 5902, pp 23-36. Springer, Heidelberg · Zbl 1266.03047
[7] Craig, W., Three uses of the herbrand-Gentzen theorem in relating model theory and proof theory, J Symb Log, 22, 3, 269-285 (1957) · Zbl 0079.24502 · doi:10.2307/2963594
[8] Sery O, Fedyukovich G, Sharygina N (2011) Interpolation-based function summaries in bounded model checking. In: HVC 2011, vol 7261, pp 160-175. Springer, Heidelberg
[9] Asadi S, Blicha M, Fedyukovich G, Hyvärinen AEJ, Even-Mendoza K, Sharygina N, Chockler H (2018) Function summarization modulo theories. In: LPAR-22, vol 57, pp 56-75. EasyChair, England & Wales · Zbl 1415.68141
[10] Rollini SF, Alt L, Fedyukovich G, Hyvärinen A, Sharygina N (2013) PeRIPLO: A framework for producing effective interpolants in SAT-based software verification. In: LPAR 2013, vol 8312, pp 683-693. Springer, Heidelberg · Zbl 1407.68303
[11] Alt L, Asadi S, Chockler H, Even-Mendoza K, Fedyukovich G, Hyvärinen A, Sharygina N (2017) HiFrog: SMT-based function summarization for software verification. In: TACAS 2017, vol 10206, pp 207-213. Springer, Heidelberg
[12] Sery O, Fedyukovich G, Sharygina N (2012) Incremental upgrade checking by means of interpolation-based function summaries. In: FMCAD 2012, pp 114-121. IEEE, New York
[13] Fedyukovich, G.; Sery, O.; Sharygina, N., Flexible SAT-based framework for incremental bounded upgrade checking, STTT, 19, 5, 517-534 (2017) · doi:10.1007/s10009-015-0405-y
[14] Asadi S, Blicha M, Hyvärinen A, Fedyukovich G, Sharygina N (2020) Incremental verification by SMT-based summary repair. In: FMCAD 2020. IEEE, New York · Zbl 1474.68321
[15] Silva T, Porto C, da S Alves EH, Cordeiro LC, Rocha H (2021) Verifying security vulnerabilities in large software systems using multi-core k-induction. CoRR arXiv:abs/2102.02368
[16] Kroening D, Tautschnig M (1976) CBMC—C bounded model checker. In: TACAS 2014, vol 42, pp 389-391. Springer, Heidelberg
[17] Clarke E, Kroening D, Lerda F (2004) A tool for checking ANSI-C programs. In: TACAS 2004, vol 2988, pp 168-176. Springer, Berlin, Heidelberg · Zbl 1126.68470
[18] McMillan KL (2003) Interpolation and SAT-based model checking. In: CAV 2003, pp 1-13 · Zbl 1278.68184
[19] Henzinger T, Jhala R, Majumdar R, McMillan KL (2004) Abstractions from Proofs. In: POPL · Zbl 1325.68147
[20] Asadi S, Blicha M, Hyvärinen A, Fedyukovich G, Sharygina N (2020) Farkas-based tree interpolation. In: SAS 2020. Springer, Heidelberg · Zbl 1474.68321
[21] Blanc R, Gupta A, Kovács L, Kragl B (2013) Tree interpolation in Vampire. In: LPAR 2013, vol 8312, pp 173-181. Springer, Berlin · Zbl 1406.68104
[22] Komuravelli A, Gurfinkel A, Chaki S, Clarke EM (2013) Automatic abstraction in SMT-based unbounded software model checking. In: CAV 2013. LNCS, vol 8044, pp 846-862. Springer, Berlin
[23] Fedyukovich G, Bodík R (2018) Accelerating Syntax-Guided Invariant Synthesis. In: TACAS, 2018, vol 10805, pp 251-269. Springer, Heidelberg
[24] Flanagan C, Leino KRM (2001) Houdini, an annotation assistant for esc/java. In: FME 2001, vol 2021, pp 500-517. Springer, Heidelberg · Zbl 0977.68671
[25] Schrijver, A., Theory of linear and integer programming. Wiley-Interscience series in discrete mathematics and optimization. (1999), London: Wiley, Sons, London
[26] McMillan, KL, An interpolating theorem prover, Theor Comput Sci, 345, 1, 101-121 (2005) · Zbl 1079.68092 · doi:10.1016/j.tcs.2005.07.003
[27] Blicha M, Hyvärinen A, Kofron J, Sharygina N (2019) Decomposing Farkas interpolants. In: TACAS 2019, vol 11427, pp 3-20. Springer, Heidelberg · Zbl 1527.68126
[28] Alt L, Hyvärinen A, Asadi S, Sharygina N (2017) Duality-based interpolation for quantifier-free equalities and uninterpreted functions. In: FMCAD 2017, pp 39-46. FMCAD Inc, Austin, Texas
[29] Pudlák, P., Lower bounds for resolution and cutting plane proofs and monotone computations, J Symb Log, 62, 3, 981-998 (1997) · Zbl 0945.03086 · doi:10.2307/2275583
[30] Christ, J.; Hoenicke, J., Proof tree preserving tree interpolation, J Autom Reasoning, 57, 1, 67-95 (2016) · Zbl 1356.68184 · doi:10.1007/s10817-016-9365-5
[31] Gurfinkel A, Rollini SF, Sharygina N (2013) Interpolation properties and SAT-based model checking. In: ATVA 2013, pp 255-271 · Zbl 1410.68229
[32] Hyvärinen A, Marescotti M, Alt L, Sharygina N (2016) OpenSMT2: An SMT solver for multi-core and cloud computing. In: SAT 2016, vol 9710, pp 547-553. Springer, Heidelberg · Zbl 1475.68438
[33] Alt L, Fedyukovich G, Hyvärinen A, Sharygina N (2016) A proof-sensitive approach for small propositional interpolants. In: VSTTE 2015, vol 9593, pp 1-18. Springer, Berlin, Heidelberg
[34] Beyer D, Löwe S, Novikov E, Stahlbauer A, Wendler P (2013) Precision reuse for efficient regression verification. In: ESEC/FSE 2013, pp 389-399. ACM, New York
[35] Conway CL, Namjoshi KS, Dams D, Edwards SA (2005) Incremental algorithms for inter-procedural analysis of safety properties. In: CAV 2005, vol 3576, pp 449-461. Springer, Heidelberg · Zbl 1081.68615
[36] Trostanetski A, Grumberg O, Kroening D (2017) Modular demand-driven analysis of semantic difference for program versions. In: SAS 2017, vol 10422, pp 405-427. Springer, Cham · Zbl 1420.68076
[37] He F, Yu Q, Cai L (2018) When regression verification meets CEGAR. CoRR arXiv:abs/1806.04829
[38] Rothenberg B, Dietsch D, Heizmann M (2018) Incremental verification using trace abstraction. In: Static analysis—25th international symposium, SAS 2018, pp 364-382 · Zbl 1511.68168
[39] Beyer D, Jakobs M, Lemberger T (2020) Difference verification with conditions. In: SEFM 2020, vol 12310, pp 133-154. Springer, Cham
[40] Lauterburg S, Sobeih A, Marinov D, Viswanathan M (2008) Incremental state-space exploration for programs with dynamically allocated data. In: ICSE 2008, pp 291-300. ACM, New York
[41] Visser W, Geldenhuys J, Dwyer MB (2012) Green: reducing, reusing and recycling constraints in program analysis. In: SIGSOFT/FSE 2012, p 58. ACM, New York
[42] Fedyukovich G, Gurfinkel A, Sharygina N (2014) Incremental verification of compiler optimizations. In: NFM 2014, pp 300-306
[43] Fedyukovich G, Gurfinkel A, Sharygina N (2016) Property directed equivalence via abstract simulation. In: Proc. CAV 2016, vol 9780, Part II, pp 433-453. Springer, Cham · Zbl 1411.68065
[44] Hardin RH, Kurshan RP, McMillan KL, Reeds JA, Sloane NJA (1996) Efficient regression verification. In: Proc. WODES’96, pp 147-150. IEEE, Proc
[45] Godlin B, Strichman O (2009) Regression verification. In: The 46th design automation conference, DAC, pp 466-471. ACM, New York
[46] Lahiri SK, McMillan KL, Sharma R, Hawblitzel C (2013) Differential assertion checking. In: ESEC/FSE 2013, pp 345-355. ACM, New York
[47] Pick L, Fedyukovich G, Gupta A (2018) Exploiting synchrony and symmetry in relational verification. In: CAV 2018, Part I, vol 10981, pp 164-182. Springer, Cham · Zbl 1511.68166
[48] Shemer R, Gurfinkel A, Shoham S, Vizel Y (2019) Property directed self composition. In: CAV 2019, vol 11561, pp 161-179. Springer, Heidelberg · Zbl 1533.68176
[49] Mordvinov D, Fedyukovich G (2019) Property directed inference of relational invariants. In: FMCAD 2019, pp 152-160. IEEE, San Jose
[50] Felsing D, Grebing S, Klebanov V, Rümmer P, Ulbrich M (2014) Automating regression verification. In: ASE 2014, pp 349-360. ACM, New York
[51] Yang G, Khurshid S, Person S, Rungta N (2014) Property differencing for incremental checking. In: ICSE 2014, pp 1059-1070. ACM, New York
[52] Lahiri SK, Hawblitzel C, Kawaguchi M, Rebêlo H (2012) SYMDIFF: A language-agnostic semantic diff tool for imperative programs. In: CAV 2012, vol 7358, pp 712-717. Springer, Heidelberg
[53] Godefroid P, Lahiri SK, Rubio-González C (2011) Statically validating must summaries for incremental compositional dynamic test generation. In: SAS 2011, vol 6887, pp 112-128. Springer, Heidelberg
[54] McMillan KL (2010) Lazy annotation for program testing and verification. In: CAV 2010. LNCS, vol 6174, pp 104-118. Springer, Heidelberg (2010)
[55] Albarghouthi A, Gurfinkel A, Chechik M (2012) Whale: An interpolation-based algorithm for inter-procedural verification. In: VMCAI 2012. LNCS, vol 7148, pp 39-55. Springer, Heidelberg (2012) · Zbl 1325.68137
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.