# US 2012/0278774 A1 · Model checking in state transition machine verification

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

- Number: US 2012/0278774 A1
- Document ID: US20120278774A1
- Status: Published application
- Kind: A1
- Application number: 13/097,193
- Filed: 2011-04-29
- Published: 2012-11-01
- Earliest claimed: 2011-04-29
- Assignees: International Business Machines Corporation
- Inventors: Viresh Paruthi; Peter Anthony Sandon; Jun Sawada
- Web page: https://patentgrep.com/patent/US20120278774A1

## CPC

- G06F 30/3323: using formal methods, e.g. equivalence checking or property checking
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method, system, and computer program product for improved model checking for verification of a state transition machine (STM) are provided. A hardware design under test and a property to be verified are received. A level (k) of induction proof needed for the verification is determined. A circuit representation of the property using the hardware design under test for k base cases is configured for checking that the circuit representation holds true for the property for each of the k base cases, and for testing an induction without hypothesis by testing whether the property holds true after k clock cycles starting from a randomized state, where induction without hypothesis is performed by omitting a test whether the property holds true for the next cycle after the property holds for k successive cycles. The induction proof of the property using the hardware design under test by induction without hypothesis is produced.

## Claims

### Claim 1

A computer implemented method for improved model checking for verification of a state transition machine (STM), the method comprising:
receiving a hardware design under test and a property to be verified;
determining a level (k) of induction proof needed for the verification;
configuring a circuit representation of the property using the hardware design under test for k base cases, for checking that the circuit representation holds true for the property for each of the k base cases;
further configuring the circuit representation for testing an induction without hypothesis by testing whether the property holds true after k clock cycles starting from a randomized state, wherein the induction without hypothesis is performed, using a processor and a memory, by omitting a test whether the property holds true for the next cycle after the property holds for k successive cycles; and
producing the induction proof of the property using the hardware design under test by induction without hypothesis.

### Claim 2 (depends on 1)

The computer implemented method of claim 1, wherein the receiving, the determining, the configuring, the further configuring, and the producing are performed at a model checker, and wherein the omitting is a result of omitting a logic for induction hypothesis in the circuit representation.

### Claim 3 (depends on 1)

The computer implemented method of claim 1, wherein configuring the circuit representation further comprises:
performing a logic reduction to reduce a circuit corresponding to the property to a combinational logic circuit.

### Claim 4 (depends on 1)

The computer implemented method of claim 1, wherein the property corresponds to a segment of the STM, further comprising:
returning the proof to a theorem prover, wherein the theorem prover combines the result with other results for other properties of the STM and generates a verification of the STM.

### Claim 5 (depends on 1)

The computer implemented method of claim 1, wherein the hardware definition is encoded in a memory.

### Claim 6 (depends on 1)

The computer implemented method of claim 1, further comprising:
testing whether the property holds for the k successive cycles starting from any state in the property.

### Claim 7 (depends on 1)

The computer implemented method of claim 1, wherein the circuit is a logical simulation of a physical circuit.

### Claim 8 (depends on 1)

The computer implemented method of claim 1, further comprising:
producing a counter example for the induction proof when the induction proof fails.

### Claim 9 (depends on 1)

The computer implemented method of claim 1, further comprising:
writing a machine invariant condition; and
proving that the machine invariant condition is constantly held, wherein producing the induction proof uses the machine invariant condition to augment a precondition.

### Claim 10

A computer usable program product comprising a computer usable storage device including computer usable code for verification of a state transition machine (STM), the computer usable code comprising:
computer usable code for receiving a hardware design under test and a property to be verified;
computer usable code for determining a level (k) of induction proof needed for the verification;
computer usable code for configuring a circuit representation of the property using the hardware design under test for k base cases, for checking that the circuit representation holds true for the property for each of the k base cases;
computer usable code for further configuring the circuit representation for testing an induction without hypothesis by testing whether the property holds true after k clock cycles starting from a randomized state, wherein the induction without hypothesis is performed by omitting a test whether the property holds true for the next cycle after the property holds for k successive cycles; and
computer usable code for producing the induction proof of the property using the hardware design under test by induction without hypothesis.

### Claim 11 (depends on 10)

The computer usable program product of claim 10, wherein the receiving, the determining, the configuring, the further configuring, and the producing are performed at a model checker, and wherein the omitting is a result of omitting a logic for induction hypothesis in the circuit representation.

### Claim 12 (depends on 10)

The computer usable program product of claim 10, wherein configuring the circuit representation further comprises:
computer usable code for performing a logic reduction to reduce a circuit corresponding to the property to a combinational logic circuit.

### Claim 13 (depends on 10)

The computer usable program product of claim 10, wherein the property corresponds to a segment of the STM, further comprising:
computer usable code for returning the proof to a theorem prover, wherein the theorem prover combines the result with other results for other properties of the STM and generates a verification of the STM.

### Claim 14 (depends on 10)

The computer usable program product of claim 10, wherein the hardware definition is encoded in a memory.

### Claim 15 (depends on 10)

The computer usable program product of claim 10, further comprising:
computer usable code for testing whether the property holds for the k successive cycles starting from any state in the property.

### Claim 16 (depends on 10)

The computer usable program product of claim 10, wherein the circuit is a logical simulation of a physical circuit.

### Claim 17 (depends on 10)

The computer usable program product of claim 10, further comprising:
Computer usable code for producing a counter example for the induction proof when the induction proof fails instead of producing the induction proof.

### Claim 18 (depends on 10)

The computer usable program product of claim 10, wherein the computer usable code is stored in a computer readable storage medium in a data processing system, and wherein the computer usable code is transferred over a network from a remote data processing system.

### Claim 19 (depends on 10)

The computer usable program product of claim 10, wherein the computer usable code is stored in a computer readable storage medium in a server data processing system, and wherein the computer usable code is downloaded over a network to a remote data processing system for use in a computer readable storage medium associated with the remote data processing system.

### Claim 20

A data processing system for verification of a state transition machine (STM), the data processing system comprising:
a storage device including a storage medium, wherein the storage device stores computer usable program code; and
a processor, wherein the processor executes the computer usable program code, and wherein the computer usable program code comprises:
computer usable code for receiving a hardware design under test and a property to be verified;
computer usable code for determining a level (k) of induction proof needed for the verification;
computer usable code for configuring a circuit representation of the property using the hardware design under test for k base cases, for checking that the circuit representation holds true for the property for each of the k base cases;
computer usable code for further configuring the circuit representation for testing an induction without hypothesis by testing whether the property holds true after k clock cycles starting from a randomized state, wherein the induction without hypothesis is performed by omitting a test whether the property holds true for the next cycle after the property holds for k successive cycles; and
computer usable code for producing the induction proof of the property using the hardware design under test by induction without hypothesis.
