Conference Proceedings

Inferring congruence equations using SAT

A King, H SONDERGAARD, A Gupta (ed.), S Malik (ed.)

Computer Aided Verification (Lecture Notes in Computer Science) | Springer Berlin Heidelberg | Published : 2008


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.


Awarded by EPSRC

Funding Acknowledgements

This work was funded by EPSRC projects EP/C015517, EP/E033105 and EP/F012896. We thank Paul Docherty for motivating discussions on reverse engineering, Neil Kettle and Axel Simon for their comments on SAT-solving and Gift Nuka for his help with Floyd-style assertions.