  Decision procedures for SMT problems based on the theory of bit-vectors are a
fundamental component in state-of-the-art software and hardware verifiers.
While very efficient in general, certain SMT instances are still challenging
for state-of-the-art solvers (especially when such instances include
computationally costly functions). In this work, we present an approach for the
quantifier-free bit-vector theory (QF_BV in SMT-LIB) based on incremental SMT
solving and abstraction refinement. We define four concrete approximation steps
for the multiplication, division and remainder operators and combine them into
an incremental abstraction scheme. We implement this scheme in a prototype
extending the SMT solver Boolector and measure both the overall performance and
the performance of the single approximation steps. The evaluation shows that
our abstraction scheme contributes to solving more unsatisfiable benchmark
instances, including seven instances with unknown status in SMT-LIB.
