MURAL - Maynooth University Research Archive Library



    Predicting SMT solver performance for software verification


    Healy, Andrew (2016) Predicting SMT solver performance for software verification. Masters thesis, National University of Ireland Maynooth.

    [thumbnail of AHEALYTHESIS.PDF]
    Preview
    Other
    AHEALYTHESIS.PDF

    Download (909kB) | Preview

    Abstract

    The approach Why3 takes to interfacing with a wide variety of interactive and automatic theorem provers works well: it is designed to overcome limitations on what can be proved by a system which relies on a single tightly-integrated solver. In common with other systems, however, the degree to which proof obligations (or “goals”) are proved depends as much on the SMT solver as the properties of the goal itself. In this work, we present a method to use syntactic analysis to characterise goals and predict the most appropriate solver via machine-learning techniques. Combining solvers in this way - a portfolio-solving approach - maximises the number of goals which can be proved. The driver-based architecture of Why3 presents a unique opportunity to use a portfolio of SMT solvers for software verification. The intelligent scheduling of solvers minimises the time it takes to prove these goals by avoiding solvers which return Timeout and Unknown responses. We assess the suitability of a number of machinelearning algorithms for this scheduling task. The performance of our tool Where4 is evaluated on a dataset of proof obligations. We compare Where4 to a range of SMT solvers and theoretical scheduling strategies. We find that Where4 can out-perform individual solvers by proving a greater number of goals in a shorter average time. Furthermore, Where4 can integrate into a Why3 user’s normal workflow - simplifying and automating the non-expert use of SMT solvers for software verification.
    Item Type: Thesis (Masters)
    Keywords: Predicting; SMT solver performance; software verification;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 8770
    Depositing User: IR eTheses
    Date Deposited: 07 Sep 2017 13:05
    URI: https://mural.maynoothuniversity.ie/id/eprint/8770
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only (login required)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads