Microsoft Technology Licensing, LLC

Eleonora O Bounimova

Thomas J Ball

Vladimir A Levin

Rahul Sudhir Kumar

Leonardo Mendonca De Moura

A system is described for processing predicates in the course of analyzing a program, based on a general-purpose theory of pointers. The system converts location expressions in the predicates into logical formulae that are interpretable by a theorem prover module, producing converted predicates. This conversion associates the location expressions with location objects. More specifically, the conversion represents variables as explicitly-specified location objects, and location terms (such as a field-type access terms and dereference-type terms) as constructor-specified location objects. The theory of pointers is also expressed by a set of axioms which constrain the operation of the theorem prover module.

Processing predicates including pointer information

An analysis engine is described for performing static analysis using CEGAR loop functionality, using a combination of forward and backward validation-phase trace analyses. The analysis engine includes a number of features. For example: (1) the analysis engine can operate on blocks of program statements of different adjustable sizes; (2) the analysis engine can identify a subtrace of the trace and perform analysis on that subtrace (rather than the full trace); (3) the analysis engine can form a pyramid of state conditions and extract predicates based on the pyramid and/or from auxiliary source(s); (4) the analysis engine can generate predicates using an increasingly-aggressive series of available discovery techniques; (5) the analysis engine can selectively concretize procedure calls associated with the trace on an as-needed basis and perform other refinements; and (6) the analysis engine can add additional verification targets in the course of its analysis, etc.

Growing community of inventors

Redmond, WA, United States of America

Eleonora O Bounimova