Geodesic
Random model sampling: making Craig interpolation work when it should not
Modelirovanie i analiz informacionnyh sistem, Tome 21 (2014) no. 6, pp. 7-17.

Voir la notice de l'article provenant de la source Math-Net.Ru

One of the most serious problems when doing program analyses is dealing with function calls. While function inlining is the traditional approach to this problem, it nonetheless suffers from the increase in analysis complexity due to the state space explosion. Craig interpolation has been successfully used in recent years in the context of bounded model checking to do function summarization which allows one to replace the complete function body with its succinct summary and, therefore, reduce the complexity. Unfortunately this technique can be applied only to a pair of unsatisfiable formulae. In this work-in-progress paper we present an approach to function summarization based on Craig interpolation that overcomes its limitation by using random model sampling. It captures interesting input/output relations, strengthening satisfiable formulae into unsatisfiable ones and thus allowing the use of Craig interpolation. Preliminary experiments show the applicability of this approach; in our future work we plan to do a full evaluation on real-world examples.
Keywords: bounded model checking, static program analysis, function summaries, satisfiability modulo theories.
Mots-clés : Craig interpolation 
@article{MAIS_2014_21_6_a1,
     author = {Marat Akhin and Sam Kolton and Vladimir Itsykson},
     title = {Random model sampling: making {Craig} interpolation work when it should not},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {7--17},
     publisher = {mathdoc},
     volume = {21},
     number = {6},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2014_21_6_a1/}
}
TY  - JOUR
AU  - Marat Akhin
AU  - Sam Kolton
AU  - Vladimir Itsykson
TI  - Random model sampling: making Craig interpolation work when it should not
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2014
SP  - 7
EP  - 17
VL  - 21
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2014_21_6_a1/
LA  - ru
ID  - MAIS_2014_21_6_a1
ER  - 
%0 Journal Article
%A Marat Akhin
%A Sam Kolton
%A Vladimir Itsykson
%T Random model sampling: making Craig interpolation work when it should not
%J Modelirovanie i analiz informacionnyh sistem
%D 2014
%P 7-17
%V 21
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2014_21_6_a1/
%G ru
%F MAIS_2014_21_6_a1
Marat Akhin; Sam Kolton; Vladimir Itsykson. Random model sampling: making Craig interpolation work when it should not. Modelirovanie i analiz informacionnyh sistem, Tome 21 (2014) no. 6, pp. 7-17. http://geodesic.mathdoc.fr/item/MAIS_2014_21_6_a1/

[1] M. Akhin, M. Belyaev, V. Itsykson, “Yet another defect detection: Combining bounded model checking and code contracts”, PSSV'13 (2013), 1–11

[2] A. Biere, A. Cimatti, E. M. Clarke, Y. Zhu, “Symbolic model checking without BDDs”, TACAS'99 (1999), 193–207

[3] J. Christ, J. Hoenicke, A. Nutz, “SMTInterpol: An interpolating SMT solver”, SPIN'12 (2012), 248–254 | Zbl

[4] A. Cimatti, A. Griggio, B.-J. Schaafsma, R. Sebastiani, “The MathSAT5 SMT solver”, TACAS'13 (2013), 93–107 | Zbl

[5] E. Clarke, O. Grumberg, S. Jha, Y. Lu, H. Veith, “Counterexample-guided abstraction refinement for symbolic model checking”, ACM, 50:5, Sep. (2003), 752–794 | DOI | MR

[6] W. Craig, “Three uses of the Herbrand–Gentzen theorem in relating model theory and proof theory”, The Journal of Symbolic Logic, 22:3, Sep. (1957), 269–285 | DOI | MR | Zbl

[7] I. Dillig, T. Dillig, B. Li, K. McMillan, “Inductive invariant generation via abductive inference”, OOPSLA'13, ACM, New York, USA, 2013, 443–456

[8] F. Ivančić, S. Sankaranarayanan, NECLA static analysis benchmarks, http://www.nec-labs.com/research/system/systems_SAV-website/benchmarks.php

[9] B. Li, I. Dillig, T. Dillig, K. McMillan, M. Sagiv, “Synthesis of circular compositional program proofs via abduction”, TACAS'13 (2013), 370–384 | Zbl

[10] K. L. McMillan, “Applications of Craig interpolants in model checking”, TACAS'05 (2005), 1–12

[11] K. L. McMillan, “Lazy abstraction with interpolants”, CAV'06 (2006), 123–136 | MR | Zbl

[12] K. L. McMillan, “Interpolants from Z3 proofs”, FMCAD'11 (2011), 19–27

[13] O. Sery, G. Fedyukovich, N. Sharygina, “Interpolation-based function summaries in bounded model checking”, HVC'11 (2012), 160–175