RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Model. Anal. Inform. Sist.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Model. Anal. Inform. Sist., 2014, Volume 21, Number 6, Pages 7–17 (Mi mais408)  

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

Abstract: 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, Craig interpolation, function summaries, satisfiability modulo theories.

Full text: PDF file (530 kB)
References: PDF file   HTML file
UDC: 004.052.42+004.4'23
Received: 30.06.2014

Citation: 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
\Bibitem{AkhKolIts14}
\by Marat~Akhin, Sam~Kolton, Vladimir~Itsykson
\paper Random model sampling: making Craig interpolation work when it should not
\jour Model. Anal. Inform. Sist.
\yr 2014
\vol 21
\issue 6
\pages 7--17
\mathnet{http://mi.mathnet.ru/mais408}


Linking options:
  • http://mi.mathnet.ru/eng/mais408
  • http://mi.mathnet.ru/eng/mais/v21/i6/p7

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Моделирование и анализ информационных систем
    Number of views:
    This page:179
    Full text:54
    References:21

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020