Search

We present an algorithm DASH to check if a program P satisfies a safety property φ. The unique feature of this algorithm is that it uses only test generation operations, and it refines and maintains a sound program abstraction as a consequence of failed test generation operations. Thus, each iteration of the algorithm is inexpensive, and can be implemented without any global may-alias information. In particular, we introduce a new refinement operator WPα that uses only the alias information obtained by symbolically executing a test to refine abstractions in a sound manner. We present a full exposition of the DASH algorithm and its theoretical properties. We have implemented DASH in a tool called YOGI that plugs into Microsoft's Static Driver Verifier framework. We have used this framework to run YOGI on 69 Windows Vista drivers with 85 properties and find that YOGI scales much better than SLAM, the current engine driving Microsoft's Static Driver Verifier. [ABSTRACT FROM AUTHOR]

The article discusses technological innovations that will help create automatic software testing programs for computers. It is theoretically impossible to create a program that can automatically test and debug every line of code in a software application, but tools that can test large portions of C programs would be better than any previous technology. Software engineers at Microsoft Corp. have worked on dynamic test generators which offer significant improvements over static test generators. They are using a combination of symbolic execution, dynamic analysis, and systematic state-space exploration tools to test their software.

In this paper, we present new ways of describing and constructing linear tail-biting trellises for block codes. We extend the well-known Bahl-Cocke-Jelinek--Raviv (BCJR) construction for conventional trellises to tail-biting trellises. The BCJR-like labeling scheme yields a simple specification for the tail-biting trellis for the dual code, with the dual trellis having the same state-complexity profile as that of the primal code. Finally, we show that the algebraic specification of Forney for state spaces of conventional trellises has a natural extension to tail-biting trellises. [ABSTRACT FROM AUTHOR]