Inventors:
Aditya V. Nori - Bangalore, IN
Sriram K. Rajamani - Bangalore, IN
Robert J. Simmons - Pittsburgh PA, US
Nels Beckman - Pittsburgh PA, US
Assignee:
MICROSOFT CORPORATION - Redmond WA
International Classification:
G06F 11/36
Abstract:
A “property checker” uses light-weight symbolic execution to prove that software programs satisfy safety properties by simultaneously performing program testing and program abstraction. A simple example of safety properties includes conditions that must be satisfied for proper program execution, such as whether an application properly interfaces with API methods or functions. Program tests are an “under-approximation” of program behavior, and abstractions are an “over-approximation” of the program. This simultaneous testing either finds a test-case that reaches an error state, or finds an abstraction showing that no path in the state space of the program can reach any error state. If a test-case reaches an error state, the property checker has discovered a violation of the safety property. Conversely, if no path in the state space can reach any error state, the property checker has proved that the program satisfies the desired safety property.