Selected dynamic issues in software model checking
Software model checking has come of age. After one and a half decade, several successful model checking tools have emerged. One of the most prominent approaches is the virtual machine-based approach, pioneered by Java PathFinder (jpf). And although the virtual machine-based approach has been rather successful, it lags behind classic model checking in terms of speed and memory consumption. Fortunately, with respect to the implementation of virtual-based model checkers, there is still ample room for innovation and optimizations. This paper presents three novel (optimization) techniques that have been implemented into MoonWalker, a software model checker for .Net programs. (a) .Net specifies an exception handling mechanism called structured exception handling (seh). seh is one of the most sophisticated and fine-grained exception handling mechanisms for application platforms. Its implementation within MoonWalker is the most sophisticated in a model checker to date. (b) To decrease memory use within MoonWalker, a collapsing scheme has been developed for collapsing the metadata used by stateful dynamic partial order reduction. The reduction of memory isin some casesmore than a factor of two. (c) Finally, to decrease the verification time, the memoised garbage collection (mgc) algorithm has been developed. It has a lower time-complexity than the often used Mark & Sweep garbage collector. Its main idea is that it only traverses changed parts of the heap instead of the full heap. The average time reduction is up to 25%. We have used the Java Grande Forum benchmark suite to compare MoonWalker against jpf and observed that the average performance of MoonWalker is on par with jpf.
model checking java .net partial order reduction garbage collection