Model checking without a model

Publisher Website
Google Scholar
Abstract
VeriSoft is a tool for systematically exploring the state spaces of systems composed of several concurrent processes executing arbitrary code written in full-fledged programming languages such as C or C++. The state space of a concurrent system is a directed graph that represents the combined behavior of all concurrent components in the system. By exploring its state space, VeriSoft can automatically detect coordination problems between the processes of a concurrent system.We report in this paper our analysis with VeriSoft of the "Heart-Beat Monitor" (HBM), a telephone switching application developed at Lucent Technologies. The HBM of a telephone switch determines the status of different elements connected to the switch by measuring propagation delays of messages transmitted via these elements. This information plays an important role in the routing of data in the switch, and can significantly impact switch performance.We discuss the steps of our analysis of the HBM using VeriSoft. Because no modeling of the HBM code is necessary with this tool, the total elapsed time before being able to run the first tests was on the order of a few hours, instead of several days or weeks that would have been needed for the (error-prone) modeling phase required with traditional model checkers or theorem provers.We then present the results of our analysis. Since VeriSoft automatically generates, executes and evaluates thousands of tests per minute and has complete control over nondeterminism, our analysis revealed HBM behavior that is virtually impossible to detect or test in a traditional lab-testing environment. Specifically, we discovered flaws in the existing documentation on this application and unexpected behaviors in the software itself. These results are being used as the basis for the redesign of the HBM software in the next commercial release of the switching software.

This publication has 15 references indexed in Scilit: