Random model sampling: making Craig interpolation work when it should not
Marat Akhin, Sam Kolton, Vladimir Itsykson
Saint-Petersburg Polytechnic University, Polytechnicheskaya street, 29, Saint-Petersburg 195251 Russia
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
bounded model checking, static program analysis, Craig interpolation, function summaries, satisfiability modulo theories.
PDF file (530 kB)
Marat Akhin, Sam Kolton, Vladimir Itsykson, “Random model sampling: making Craig interpolation work when it should not”, Model. Anal. Inform. Sist., 21:6 (2014), 7–17
Citation in format AMSBIB
\by Marat~Akhin, Sam~Kolton, Vladimir~Itsykson
\paper Random model sampling: making Craig interpolation work when it should not
\jour Model. Anal. Inform. Sist.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|