# US 2010/0169868 A1 · Unifying Type Checking and Property Checking for Low Level Programs

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0169868 A1
- Document ID: US20100169868A1
- Status: Published application
- Kind: A1
- Application number: 12/347,398
- Filed: 2008-12-31
- Published: 2010-07-01
- Earliest claimed: 2008-12-31
- Assignees: Microsoft Corporation
- Inventors: Jeremy P. Condit; Shaz Qadeer; Shuvendu K. Lahiri
- Web page: https://patentgrep.com/patent/US20100169868A1

## CPC

- G06F 8/437: {Type checking}
- G06F 8/40: Transformation of program code
- G06F 11/3608: {using formal methods, e.g. model checking, abstract interpretation (theorem proving G06N5/013)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

This document describes a unified type checker and property checker for a low level program's heap and its types. The type checker can use the full power of the property checker to express and verify subtle, program specific type and memory safety invariants well beyond what the native low level program system can check. Meanwhile, the property checker can rely on the type checker to provide structure and disambiguation for the program's heap, enabling more concise and more powerful type-based specifications. This approach makes use of a fully automated Satisfiability Modulo Theories (SMT) solver and a decision procedure for checking type safety, which means that the programmer's only duty is to provide high-level type and property annotations as part of the original program's source.

## Claims

### Claim 1

A computer readable medium having stored thereon computer executable instructions causing a computer to execute a process comprising:
translating a program code to an logical representation that includes type-safety assertions;
generating a verification condition from the translated program code;
if the generated verification condition includes one or more universal quantifiers, removing the one or more universal quantifiers from the generated verification condition; and
executing a decision procedure to prove or disprove the generated verification condition.

### Claim 2 (depends on 1)

The computer readable media according to claim 1, wherein the program code has been written in C or C++.

### Claim 3 (depends on 1)

The computer readable media according to claim 1, wherein the logical representation of the program code models values in a heap and models types of the heap locations, the values in the heap modeled using a map from addresses to values and the types of the heap locations modeled using a map from addresses to types.

### Claim 4 (depends on 3)

The computer readable media according to claim 3, wherein the map for the types of the heap locations may use unique types for each field of a structure type.

### Claim 5 (depends on 1)

The computer readable media according to claim 1, wherein translating the program code to a logical representation includes asserting a type safety invariant after every program point by modeling a type safety invariant for a heap and for local variables, if any.

### Claim 6 (depends on 1)

The computer readable media according to claim 1, wherein the program code includes one or more polymorphic types, and wherein the translating of the program code includes translating the one or more polymorphic types of the program code.

### Claim 7 (depends on 1)

The computer readable media according to claim 1, wherein function pointer types are added to the logical representation, the function pointer types comprising argument types, return types, preconditions, and postconditions.

### Claim 8 (depends on 1)

The computer readable media according to claim 1, wherein the annotations include a portion containing user-defined types input directly into the logical representation, and wherein the translating of the program code comprises translating the program code other than the user-defined types into the logical representation.

### Claim 9

A method, comprising:
translating a program code to a logical representation appropriate for input to a theorem prover, wherein the translation encodes type safety assertions into the program code;
generating a verification condition for the type-safety assertions;
if the generated verification condition includes one or more universal quantifiers, removing the one or more quantifiers from the generated verification condition; and
executing a decision procedure to prove or disprove the generated verification condition.

### Claim 10 (depends on 9)

The method of claim 9, wherein the program code includes one or more polymorphic types, and wherein the translating of the program code includes translating the one or more polymorphic types of the program code.

### Claim 11 (depends on 9)

The method of claim 9, further comprising:
annotating a portion of the program code containing user-defined types input directly into the logical representation; and
translating the program code other than the user-defined types into the logical representation.

### Claim 12 (depends on 9)

The method of claim 9, wherein the logical representation of the program code models values in a heap and models types of the heap locations.

### Claim 13 (depends on 9)

The method of claim 9, wherein translating the program code to a logical representation includes asserting a type safety invariant after every program point by modeling a type safety invariant for a heap and for zero or more local variables.

### Claim 14 (depends on 9)

The method of claim 9, wherein the decision procedure comprises obtaining a new formula by instantiating a type safety invariant and definitions for a HasType predicate and a Match predicate at a finite set of locations and types, and further comprising checking the satisfiability of the new formula.

### Claim 15

A computer readable medium having stored thereon computer executable instructions causing a computer to execute a process, the process comprising:
translating the program code to a logical representation appropriate for input to a theorem prover, wherein the translating encodes type safety assertions into the program code; and
executing a solver to prove or disprove the assertions.

### Claim 16 (depends on 15)

The computer readable media according to claim 15, wherein the logical representation of the program code models values in a heap and models types of the heap locations.

### Claim 17 (depends on 15)

The computer readable media according to claim 15, wherein translating the program code to a logical representation includes asserting a type safety invariant after every program point by modeling a type safety invariant for a heap and for local variables, if any.

### Claim 18 (depends on 15)

The computer readable media according to claim 15, wherein the program code includes one or more polymorphic types, and wherein translating the program code to the logical representation also includes translating the one or more polymorphic types.

### Claim 19 (depends on 15)

The computer readable media according to claim 15, wherein a portion of the program code contains user-defined types input directly into the logical representation, and wherein the translating of the program code comprises translating the program code other than the user-defined types into the logical representation.

### Claim 20 (depends on 15)

The computer readable media according to claim 15, wherein the decision procedure comprises obtaining a new formula by instantiating a type safety invariant and definitions for a HasType predicate and a Match predicate at a finite set of locations and types, and further comprising checking the satisfiability of the new formula.
