We have been exploring LURCH, an approximate (not necessarily complete) alternative to
traditional model checking based on a randomized search algorithm. Randomized
algorithms like LURCH have been known to outperform their deterministic counterparts for
search problems representing a wide range of applications. The cost of an approximate
strategy is the potential for inaccuracy. If complete algorithms terminate, they find all the
features they are searching for. On the other hand, by its very nature, randomized search …

As software grows increasingly complex, verification becomes more and more challenging.
Automatic verification by model checking has been effective in many domains including
computer hardware design, networking, security and telecommunications protocols,
automated control systems and others [2, 4, 6]. Many realworld software models, however,
are too large for the available tools. The difficulty—how to verify large systems—is
fundamentally a search issue: the global state space representing all possible behaviors of …