Using term rewriting to solve Bit-Vector arithmetic problems (Poster Presentation)

• Author(s): Abal, Iago ; Cunha, Alcino ; Hurd, Joe ; Pinto, Jorge Sousa
• Date: 2012
• Persistent ID: http://hdl.handle.net/1822/26358
• Origin: RepositóriUM - Universidade do Minho
• Subject(s): Bit-Vector arithmetic; Decision procedures; Term rewriting; Formal verification
• Document Type: Conference Object
• Language: English

Description

Among many theories supported by SMT solvers, the theory of finite-precision bit-vector arithmetic is one of the most useful, for both hardware and software systems verification. This theory is also particularly useful for some specific domains such as cryptography, in which algorithms are naturally expressed in terms of bit-vectors. Cryptol is an example of a domain-specific language (DSL) and toolset for cryptography developed by Galois, Inc.; providing an SMT backend that relies on bit-vector decision procedures to certify the correctness of cryptographic specifications [3]. Most of these decision procedures use bit-blasting to reduce a bit-vector problem into pure propositional SAT. Unfortunately bit-blasting does not scale very well, especially in the presence of operators like multiplication or division.