Microsoft's Static Driver Verifier (SDV) pioneered the use of software model checking for ensuring that device drivers correctly use operating system (OS) APIs.However, the verification methodology has been difficult to extend in order to support either (a) new classes of drivers for which SDV does not already have a harness and stubs, or (b) memory-corruption properties.Any attempt to apply SDV out-of-the-box results in either false alarms due to the lack of environment modeling, or scalability issues when finding deeply nested bugs in the presence of a very large number of memory accesses.In this paper, we describe our experience designing and shipping a new class of checks known as angelic checks through SDV with the aid of angelic verification (AV) [1] technology, over a period of 4 years.AV pairs a precise inter-procedural assertion checker with automatic inference of likely specifications for the environment.AV helps compensate for the lack of environment modeling and regains scalability by making it possible to find deeply nested bugs, even for complex memorycorruption properties.These new rules have together found over a hundred confirmed defects during internal deployment at Microsoft, including several previously unknown high-impact potential security vulnerabilities.AV considerably increases the reach of SDV, both in terms of drivers as well as rules that it can support effectively.

Software drivers are usually developed after hardware devices become available. This dependency can induce a long product cycle. Although co-simulation and co-verification techniques have been utilized to facilitate the driver development, Hardware/Software (HW/SW) interface models, as the test harnesses, are often challenging to specify. Such interface models should have formal semantics, be efficient for testing, and cover all HW/SW behaviors described by HW/SW interface protocols. We present an approach to formalizing HW/SW interface specifications, where we propose a semantic model, relative atomicity, to capture the concurrency model in HW/SW interfaces; demonstrate our approach via a realistic example; elaborate on how we have utilized this approach in device/driver development process; and discuss criteria for evaluating our formal specifications. We have detected fifteen issues in four English specifications. Furthermore, our formal specifications are readily useful as the test harnesses for co-verification, which has discovered twelve real bugs in five industrial driver programs.

Bugs in kernel-level device drivers cause 85% of the system crashes in the Windows XP operating system [44]. One of the sources of these errors is the complexity of the Windows driver API itself: programmers must master a complex set of rules about how to use the driver API in order to create drivers that are good clients of the kernel. We have built a static analysis engine that finds API usage errors in C programs. The Static Driver Verifier tool (SDV) uses this engine to find kernel API usage errors in a driver. SDV includes models of the OS and the environment of the device driver, and over sixty API usage rules. SDV is intended to be used by driver developers "out of the box." Thus, it has stringent requirements: (1) complete automation with no input from the user; (2) a low rate of false errors. We discuss the techniques used in SDV to meet these requirements, and empirical results from running SDV on over one hundred Windows device drivers.

Microsoft is improving the quality of system software, in particular, through the intensive application of formal methods. The ultimate goal is to reach a point at which robustness against failures and attacks can be guaranteed. To support this goal, the company has invested in advanced testing and verification tools. Examples include model-based testing supported by AsmL/SpeC#, TLC and Zing model checkers for concurrency verification, a type system augmented with pre-/post- conditions (Fugue), advanced static analysis tools (PreFix, ESP, etc.) and Static Driver Verifier, SDV. SDV is a formal verification tool aimed at checking device drivers developed using the Windows Driver Model (WDM) interface. The WDM interface consists of more than 800 functions - entry points into the kernel functionality. To correctly use the WDM interface is not easy: WDM rules are numerous and complicated.

The paper presents an approach to model checking software system designs specified in xUML (http://www.kc.com/html/xuml.html), an executable subset of UML. This approach is enabled by the execution semantics of xUML and is based on automatic translation from xUML to S/R, the input language of the COSPAN model checker (R.H. Hardin et al., 1996). Model transformations are applied to reduce the state space of the resulting S/R model that is to be verified by COSPAN. An xUML level logic for specifying properties to be checked is defined. Automated support is provided for translating properties specified in the logic to S/R representations and mapping error traces generated by COSPAN to xUML representations.