Title: Refining Trace Abstraction using Abstract Interpretation,
Abstract: The CEGAR loop in software model checking notoriously diverges when the
abstraction refinement procedure does not derive a loop invariant. An
abstraction refinement procedure based on an SMT solver is applied to a trace,
i.e., a restricted form of a program (without loops). In this paper, we present
a new abstraction refinement procedure that aims at circumventing this
restriction whenever possible. We apply abstract interpretation to a program
that we derive from the given trace. If the program contains a loop, we are
guaranteed to obtain a loop invariant. We call an SMT solver only in the case
where the abstract interpretation returns an indefinite answer. That is, the
idea is to use abstract interpretation and an SMT solver in tandem. An
experimental evaluation in the setting of trace abstraction indicates the
practical potential of this idea.