School of Computing

Inferring Congruence Equations using SAT

Andy King and Harald Sondergaard

In Aarti Gupta and Sharad Malik, editors, Twentieth International Conference on Computer-Aided Verification, Lecture Notes in Computer Science, pages 182-196. Springer-Verlag, July 2008.

Abstract

This paper proposes a new approach for deriving invariants that are systems of congruence equations where the modulo is a power of 2. The technique is an amalgam of SAT-solving, where a propositional formula is used to encode the semantics of a basic block, and abstraction, where the solutions to the formula are systematically combined and summarised as a system of congruence equations. The resulting technique is more precise than existing congruence analyses since a single optimal transfer function is derived for a basic block as a whole.

Download publication 222 kbytes (PDF)

Bibtex Record

@inproceedings{2691,
author = {Andy King and Harald S{o}ndergaard},
title = {Inferring {C}ongruence {E}quations using {SAT}},
month = {July},
year = {2008},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2008/2691},
    publication_type = {inproceedings},
    submission_id = {841_1206970840},
    booktitle = {Twentieth International Conference on Computer-Aided Verification},
    editor = {Aarti Gupta and Sharad Malik},
    series = {Lecture Notes in Computer Science},
    publisher = {Springer-Verlag},
    refereed = {yes},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014