SLAM

What’s New?

Yogi (opens in new tab)is now available to plug into the Static Driver Verifier Research Platform. To install SDVRP and Yogi, see this README (opens in new tab).

The Summer (2011) of SLAM saw two awards and a retrospective article in CACM:

• Most Influential PLDI Paper award (opens in new tab) for Automatic Predicate Abstraction of C Programs (opens in new tab), Thomas Ball, Rupak Majumdar, Todd D. Millstein, Sriram K. Rajamani, PLDI 2001 (opens in new tab). The first conference paper from the SLAM project.
• CAV 2011 (opens in new tab) Award. Citation: “The 2011 CAV Award is given to Thomas Ball and Sriram Rajamani, both at Microsoft Research, for their contributions to software model checking,specifically the development of the SLAM/SDV software model checker that successfully demonstrated computer-aided verification techniques on real programs.”
• A Decade of Software Model Checking with SLAM (opens in new tab), T. Ball, V. Levin, S. K. Rajamani, Communications of the ACM, Vol. 54. No. 7, 2011, Pages 68-76

Paper:

• SLAM2: Static Driver Verification with Under 4% False Alarms (opens in new tab), T. Ball, E. Bounimova, R. Kumar, V. Levin, FMCAD 2010 (opens in new tab)

The Static Driver Verifier Research Platform (SDVRP) is a release of SDV/SLAM for academic research. It allows the creation and checking of API-specific rules and programs (for general APIs and programs, not just driver APIs and drivers) and contains a repository of Boolean programs and test results.

• To get started:
  • Read the README in the tab below
  • Download/install the Windows 7 Driver Kit (opens in new tab) (you will want a virtual drive (opens in new tab)to install the download, as it is available only as a DVD ISO image)
  • Download/install SDVRP
• Slide deck. [ppt (opens in new tab), pdf (opens in new tab)]
• Paper. The Static Driver Verifier Research Platform (opens in new tab), Thomas Ball, Ella Bounimova, Vladimir Levin, Rahul Kumar, Jakob Lichtenberg, CAV 2010 (opens in new tab) tools paper
• Questions? E-mail us at sdvrpdis@microsoft.com (opens in new tab)

Pointers in SLAM2. Efficient evaluation of pointer predicates with Z3 SMT Solver in SLAM2 (opens in new tab), Thomas Ball, Ella Bounimova, Vladimir Levin, Leonardo de Moura, March 2010, MSR-TR-2010-24

Congratulations to the Driver Quality Team on winning a 2009 Engineering Excellence Award for “Improving Driver Quality thru Static Verification”. Jon Hagen, Vlad Levin, Adam Shapiro, Donn Terry, Abdullah Ustuner. PREfast for Drivers scans the driver code for issues with concurrency, proper IRQL handling, and a host of other driver challenges. The Static Driver Verifier simulates a hostile environment and systematically tests all code paths, looking for driver model violations. These complementary tools provide both quick and deep driver testing. Both tools have been adopted broadly within Windows and with third-party developers through MSDN and the Windows Driver Kit.

Overview of Static Driver Verifier Research Platform

Static Driver Verifier (SDV) is a compile-time static verification tool, included in the Windows Driver Kit (WDK). The SDV Research Platform (SDVRP) is an extension to SDV that allows you to adapt SDV to:

• Support additional frameworks (or APIs) and write custom SLIC rules for this framework.
• Experiment with the model checking step.

This file provides the following sections:

• Getting Started
• Documentation
• Installation Instructions

Notice: Links in this file are relative and will only work after installation of SDVRP, when this file is opened from the Start -> All Programs -> Microsoft Static Driver Verifier folder.

Getting Started

• Obtain and install WDK and SDVRP (See section Installation Instructions beneath).
• Understand SDV: See staticdv.chm, in particular sections “Static Driver Verifier Concepts” and the “Static Driver Verifier for WDM Drivers: WHDC Lab (opens in new tab)” article on the WHDC SDV web site http://www.microsoft.com/whdc/devtools/tools/sdv.mspx (opens in new tab).
• Try the SDVRP Custom Framework. See SDVRP.docx’s “Walk Through: fail_driver1”.
• Read the rest of SDVRP.docx and SLIC.docx and start experimenting on your own.

Documentation

After installation the following documents are available in the Start -> All Programs -> Microsoft Static Driver Verifier folder:

• README.htm: This file.
• SDVRP.docx: SDVRP Documentation. This is the primary document supporting SDVRP development; however it does not cover the details of the SLIC language, or the basic operation of SDV. These topics are covered by SLIC.docx and staticdv.chm (see beneath).
• SLIC.docx: SLIC Documentation. Syntax and semantics of SLIC, the rule specification language of SDV.
• bebop.docx: Bebop Documentation. Syntax and semantics of Boolean Programs, the internal language used for the model checking step in SDV. Instructions on how to run on the Bebeop Boolean Program Test Suite.
• staticdv.chm: SDV Documentation. This is the documentation provided with the regular version of Static Driver Verifier. It does not cover the SDVRP extensions. This document is also included in the Windows Driver Kit Documentation.
• License.rtf: License Agreement. This license is also presented during download and installation.

Installation Instructions

• Install the WDK.
  • What: The SDVRP requires that the (freely available) Windows Driver Kit Version 7.1.0 (WDK) first be installed. The WDK contains compiler, build environment, and supporting tools that is required to use SDV.
  • See http://www.microsoft.com/whdc/driver/wdk/ (opens in new tab) for information about obtaining the WDK. (As of this writing under: How to Get the WDK -> Microsoft Download Center).
  • Recommend default selection of Features and Location.
  • Notice: The WDK will be installed to “%SystemDrive%\WinDDK\7600.16385.1”.
• Install the SDVRP.
  • What: The SDVRP contains a customized version of SDV that can be used for rule development.
  • Recommend default selection of Features and Installation Path. Installation Path must be a path with no spaces in path name.
  • Notice: The SDVRP will be installed to “%SystemDrive%\WinDDK\SDV”.
• Confirm the WDK use the SDVRP version of SDV:
  • What: The WDK already has SDV available (in the “tools\sdv” folder), but this WDK version of SDV is not useable for SDVRP work. The WDK build environment should automatically detect that SDVRP is installed and use the SDVRP version of SDV.
  • Open a “Windows Win7 x86 Free Build Environment” window (from All Programs -> Windows Driver Kits -> 7600.16385.1 -> Build Environments -> Windows 7 -> x86 Free Build Environment)
  • Validate that this line is printed when you start the build environment: “WARNING: Using external version of Static Driver Verifier.”
  • In case of trouble you should look at the script %SystemDrive%\WinDDK\7600.16385.1\bin\setenv.bat, search for SDV.
• The SDVRP is now ready for use.

Publications

Book Chapter

• Developing Drivers with the Windows® Driver Foundation (opens in new tab), a Microsoft Press book, is now in print, including a chapter about Static Driver Verifier, which has new rules to enable analysis of drivers written against the Kernel-model Driver Framework API.

History

• SLAM and Static Driver Verifier: Technology Transfer of Formal Methods inside Microsoft (opens in new tab), T. Ball, B. Cook, V. Levin and S. K. Rajamani, Integrated Formal Methods 2004

The SLAM Process

• Thorough Static Analysis of Device Drivers (opens in new tab), T. Ball, E. Bounimova, B. Cook, V. Levin, J. Lichtenberg, C. McGarvey, B. Ondrusek, S. K. Rajamani and A. Ustuner, EuroSys 2006 (opens in new tab)
• The SLAM Project: Debugging System Software via Static Analysis (opens in new tab), T. Ball, S. K. Rajamani, POPL 2002, January 2002, pages 1-3.
• Automatically Validating Temporal Safety Properties of Interfaces (opens in new tab), T. Ball, S. K. Rajamani, SPIN 2001 Workshop on Model Checking of Software, LNCS 2057, May 2001, pp. 103-122.
• Checking Temporal Properties of Software with Boolean Programs (opens in new tab), T. Ball, S. K. Rajamani, Workshop on Advances in Verification (with CAV 2000)
• Boolean Programs: A Model and Process for Software Analysis (opens in new tab), T. Ball, S. K. Rajamani, MSR Technical Report 2000-14.

SLAM Specifications

• SLIC: A Specification Language for Interface Checking (opens in new tab), T. Ball, S. K. Rajamani, MSR-TR-2001-21.

Boolean Programs

• Bebop: A Path-sensitive Interprocedural Dataflow Engine (opens in new tab), T. Ball, S. K. Rajamani, PASTE 2001
• Bebop: A Symbolic Model Checker for Boolean Programs (opens in new tab), T. Ball, S. K. Rajamani, SPIN 2000 Workshop on Model Checking of Software, LNCS 1885, August/September 2000, pp. 113-130.

• Predicate Abstraction of C Programs
  • Polymorphic Predicate Abstraction (opens in new tab), T. Ball, T. Millstein, S. K. Rajamani, ACM TOPLAS Vol. 27, No. 2, March 2005, pages 314-343
  • Automatic Predicate Abstraction of C Programs (opens in new tab), T. Ball, R. Majumdar, T. Millstein, S. K. Rajamani, PLDI 2001, SIGPLAN Notices 36(5), pp. 203-213.
  • Boolean and Cartesian Abstractions for Model Checking C Programs (opens in new tab), T. Ball, A. Podelski, S. K. Rajamani, TACAS 2001, LNCS 2031, April 2001, pp. 268-283.
  • Predicate Abstraction via Symbolic Decision Procedures (opens in new tab), S. Lahiri, T. Ball, B. Cook, CAV 2005.

Abstraction Refinement

• Refining Approximations in Software Predicate Abstraction (opens in new tab), T. Ball, B. Cook, S. Das, S. K. Rajamani. TACAS 2004.
• Generating Abstract Explanations of Spurious Counterexamples in C Programs, T. Ball, S. K. Rajamani, MSR-TR-2002-09.
• Relative Completeness of Abstraction Refinement for Software Model Checking (opens in new tab), T. Ball, A. Podelski, S. K. Rajamani, TACAS 2002, LNCS 2280, April 2002, pp. 158-172.
• Zapato: Automatic theorem proving for predicate abstraction refinement (opens in new tab), T. Ball, B. Cook, S. K. Lahiri and L. Zhang, Tools paper in CAV 2004
• Formalizing Counterexample-driven Refinement with Weakest Preconditions (opens in new tab), T. Ball, Proceedings of the NATO Advanced Study Institute on Engineering Theories of Software Intensive Systems Marktoberdorf, Germany 3–15 August 2004.

Concurrency

• Parameterized Verification of Multithreaded Software Libraries (opens in new tab), T. Ball, S. Chaki, S. K. Rajamani,TACAS 2001, LNCS 2031, April 2001, pp. 158-173.

Miscellaneous

• From Symptom to Cause: Localizing Errors in Counterexample Traces (opens in new tab), T. Ball, M. Naik, S. K. Rajamani, POPL 2003
• Speeding Up Dataflow Analysis Using Flow-Insensitive Pointer Analysis (opens in new tab), S. Adams, T. Ball, M. Das, S. Lerner, S. K. Rajamani, M. Seigle, W. Weimer. SAS 2002, LNCS 2477
• Automatic Creation of Environment Models via Training (opens in new tab), T. Ball, V. Levin, and F. Xie, TACAS 2004
• The SLAM Toolkit (opens in new tab), T. Ball, S. K. Rajamani, CAV 2001

News

• Wired News: Microsoft’s Secret Bug Squasher (opens in new tab)
• Kampf dem Programmierfehlerteufel (opens in new tab)
• SDV and PPRC tools mentioned in The Economist (opens in new tab)
• From reporting of the Microsoft Research Roadshow in Silicon Valley (PC Magazine (opens in new tab))
• SLAM and PPRC tools featured in Bill Gates‘ OOPSLA 2002 (opens in new tab) keynote address (opens in new tab)

Related Projects

• Yogi (opens in new tab) is a new abstraction-refinment engine based on test generation.
• UC Berkeley’s BLAST 1.0 (opens in new tab)
• Sagar Chaki’s MAGIC (opens in new tab)
• Stefan Schwoon (opens in new tab)‘s Moped (opens in new tab)
• Georg Weissenbacher’s BOOP (opens in new tab)

Co-founders

• Thomas Ball (opens in new tab)
• Sriram K. Rajamani (opens in new tab)

MSR colleagues

• Ella Bounimova (opens in new tab)
• Byron Cook

Windows colleagues

• Nar Ganapathy
• Jakob Lichtenberg
• Rahul Kumar
• Vladimir Levin
• Con McGarvey
• Abdullah Ustuner
• Donn Terry

Alumni

• Bohus Ondrusek

Visitors

• Giorgio Delzanno (opens in new tab)
• Andreas Podelski (opens in new tab)
• Stefan Schwoon (opens in new tab)

Interns

2008

• Edgar Pek (opens in new tab)

2007

• Antonios Stampoulis (opens in new tab)

2006

• Rahul Kumar (opens in new tab)

2003

• Shuvendu Lahiri (opens in new tab)
• Jakob Lichtenberg (opens in new tab)
• Georg Weissenbacher (opens in new tab)

2002

• Jakob Lichtenberg (opens in new tab)
• Mayur Naik (opens in new tab)

2001

• Sagar Chaki (opens in new tab)
• Satyaki Das (opens in new tab)
• Robby (opens in new tab)
• Westley Weimer (opens in new tab)

2000

• Sagar Chaki (opens in new tab)
• Rupak Majumdar (opens in new tab)
• Todd Millstein (opens in new tab)