  In model checking, when a given model fails to satisfy the desired
specification, a typical model checker provides a counterexample that
illustrates how the violation occurs. In general, there exist many diverse
counterexamples that exhibit distinct violating behaviors, which the user may
wish to examine before deciding how to repair the model. Unfortunately,
obtaining this information is challenging in existing model checkers since (1)
the number of counterexamples may be too large to enumerate one by one, and (2)
many of these counterexamples are redundant, in that they describe the same
type of violating behavior. In this paper, we propose a technique called
counterexample classification. The goal of classification is to partition the
space of all counterexamples into a finite set of counterexample classes, each
of which describes a distinct type of violating behavior for the given
specification. These classes are then presented as a summary of possible
violating behaviors in the system, freeing the user from manually having to
inspect or analyze numerous counterexamples to extract the same information. We
have implemented a prototype of our technique on top of an existing formal
modeling and verification tool, the Alloy Analyzer, and evaluated the
effectiveness of the technique on case studies involving the well-known
Needham-Schroeder protocol with promising results.
