Model checking is a formal method for verifying whether the system satisfies a user-defined specification. Compared to simulation, model checking is restricted in capacity. On the other hand, simulation is weak in detecting bugs that require long and complex sequences of events to be exposed. This paper combines model checking and simulation in an abstraction-refinement scheme to mitigate the problems of both methods. Abstraction refinement iteratively constructs a simplified model to verify the original model. While a simplified model mitigates the weakness of model checking, the set of simplified error traces model helps guide simulation toward deep bugs. In abstraction refinement, concretization-a process of deriving an error trace in the original model from the abstract ones-is used to invalidate spurious abstract error traces or to refute a property. In this paper, we describe a novel concretization algorithm that combines simulation with satisfiability to efficiently refute properties with very long error traces.

In one-to-many concretization for model checking based on abstraction refinement, constraints on input vectors that are pseudo-randomly generated are often essential to the success of the procedure. These constraints have to do with both primary inputs and invisible state variables. We discuss algorithms that address both types and we show their effectiveness through experiments.

We present an improved algorithm for concretization of abstract error traces in abstraction refinement-based invariant checking. The proposed algorithm maps each transition of the abstract error trace to one or more transitions in the concrete model by using a combination of simulation and satisfiability checking. Prior simulation- based approaches were hindered by limited visibility, which often resulted in excessive backtracking or refinements. The proposed technique addresses this issue in three ways: By identifying variables whose addition to the abstract trace significantly improves its predictive power at a low computational cost; by combining SAT checks with pseudo-random simulation in the construction of the concrete trace; and by a more flexible budgeting of simulation vectors that accounts for the progress made in concretization.

We combine abstraction refinement and simulation to provide a more efficient approach to checking invariant properties whose only counterexamples are very long traces. We allow each transition of an abstract error trace to map to multiple transitions of the concrete error trace and simulate pseudorandom vectors to build segments of the concrete trace. This approach addresses the capacity limitation of the formal verification engine as well as the short-sightedness of the simulator, thus providing a more effective technique for deep, subtle bugs.