# US 2021/0240594 A1 · Method and system for counter example guided loop abstraction refinement

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

- Number: US 2021/0240594 A1
- Document ID: US20210240594A1
- Status: Published application
- Kind: A1
- Application number: 17/023,594
- Filed: 2020-09-17
- Published: 2021-08-05
- Earliest claimed: 2020-01-31
- Assignees: Tata Consultancy Services Limited
- Applicants: Tata Consultancy Services Limited
- Inventors: Priyanka DARKE; Tanha SHAH; Venkatesh RAMANATHAN
- Web page: https://patentgrep.com/patent/US20210240594A1

## CPC

- G06F 11/3608: {using formal methods, e.g. model checking, abstract interpretation (theorem proving G06N5/013)}
- G06F 11/3624: {by performing operations on the source code, e.g. via a compiler}
- G06F 11/3636: {by tracing the execution of the program}
- G06F 11/3698: Environments for analysis, debugging or testing of software
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Software verification is a vital process to ensure reliability and robustness of software systems. The software verification is associated with verifying one or more properties associated with a piece of code. Conventional methods are unable to verify properties of piece of code with loops, especially in the presence of loops with a large, unknown or infinite bound, or a large number of complex conditions. The present disclosure receives an abstracted piece of code corresponding to an original piece of code to check whether the abstracted piece of code hence the original piece of code is safe or not. The system applies model checking over the abstracted piece of code to check one or more property assertions associated with an abstracted piece of code. If the property assertion fails in model checking, a trace leading to the violation of the one or more property assertions is identified and analyzed.

## Claims

### Claim 1

A processor implemented method, the method comprising:
receiving, by one or more hardware processors, an abstracted piece of code corresponding to an original piece of code, wherein the abstracted piece of code comprises a plurality of base cases and inductive steps, wherein the inductive steps corresponds to a plurality of abstracted loops associated with the abstracted piece of code, and wherein each of the plurality of base cases and inductive steps are associated with a first set of property assertions to be verified;
simultaneously performing, by the one or more hardware processors, a bounded model checking on the abstracted piece of code to verify a property assertion from the first set of property assertions corresponding to a base case from the plurality of base cases and the inductive steps, wherein the abstracted piece of code is safe when the property assertion holds for the base case and inductive steps;
refining, by the one or more hardware processors, the abstracted piece of code when the abstracted piece of code is unsafe corresponding to the inductive steps until all causes leading to violation of a plurality of property assertions are analyzed, comprising:
obtaining an error trace in the abstraction using bounded model checking, wherein the error trace comprises a violation causing path corresponding to the property assertion from the first set of property assertions in the abstraction;
checking validity of the error trace on the original piece of code by utilizing a verification technique to obtain one of a valid error trace and an invalid error trace;
identifying a plurality of trace conditions, corresponding to the body of the plurality of abstracted loops by using the error trace, when the invalid error trace is obtained, wherein the plurality of trace conditions comprises a subset of conditions evaluated to true in the error trace;
negating the plurality of trace conditions to obtain a second set of property assertions;
obtaining the plurality of property assertions by performing a union of the first set of property assertions and one or more property assertions from the second set of property assertions;
further refining of the abstraction based on the plurality of property assertions by annotating the property assertions into the original piece of code and applying loop abstraction using induction technique to obtain a refined abstracted piece of code; and
bounded model checking of the refined abstracted piece of code to check whether the piece of code is safe.

### Claim 2 (depends on 1)

The processor implemented method of claim 1, wherein the induction technique is applied for verification when at least one of property assertion from the first set of property assertion to be verified lies inside the body of each of the plurality of abstracted loops.

### Claim 3 (depends on 1)

The processor implemented method of claim 1, wherein the induction technique unrolls the abstracted loops k+1 times before slicing, wherein k may be increased with every refinement to perform k induction.

### Claim 4 (depends on 1)

The processor implemented method of claim 1, wherein the verification technique comprises one of a testing technique and a plurality of verification techniques.

### Claim 5

A system (100) comprising:
at least one memory (104) storing programmed instructions; one or more Input/Output (I/O) interfaces (112); and one or more hardware processors (102) operatively coupled to the at least one memory (104), wherein the one or more hardware processors (102) are configured by the programmed instructions to:
receive an abstracted piece of code corresponding to an original piece of code, wherein the abstracted piece of code comprises a plurality of base cases and inductive steps, wherein the inductive steps corresponds to a plurality of abstracted loops associated with the abstracted piece of code, and wherein each of the plurality of base cases and inductive steps are associated with a first set of property assertions to be verified;
simultaneously perform a bounded model checking on the abstracted piece of code to verify a property assertion from the first set of property assertions corresponding to a base case from the plurality of base cases and inductive steps, wherein the abstracted piece of code is safe when the property assertion holds for the base case and inductive steps; and
refine the abstracted piece of code when the abstracted piece of code is unsafe corresponding to the inductive steps until all causes leading to violation of a plurality of property assertions are analyzed, comprising:
obtaining an error trace in the abstraction using bounded model checking, wherein the error trace comprises a violation causing path corresponding to the property assertion from the first set of property assertions in the abstraction;
checking validity of the error trace on the original piece of code by utilizing a verification technique to obtain one of a valid error trace and an invalid error trace;
identifying a plurality of trace conditions, corresponding to the body of the plurality of abstracted loops by using the error trace, when the invalid error trace is obtained, wherein the plurality of trace conditions comprises a subset of conditions evaluated to true in the error trace;
negating the plurality of trace conditions to obtain a second set of property assertions;
obtaining the plurality of property assertions by performing a union of the first set of property assertions and one or more property assertions from the second set of property assertions;
further refining of the abstraction based on the plurality of property assertions by annotating the property assertions into the original piece of code and applying loop abstraction using induction technique to obtain a refined abstracted piece of code; and
bounded model checking of the refined abstracted piece of code to check whether the piece of code is safe.

### Claim 6 (depends on 5)

The system of claim 5, wherein the induction technique is applied for verification when at least one of property assertion from the first set of property assertion to be verified lies inside the body of each of the plurality of abstracted loops.

### Claim 7 (depends on 5)

The system of claim 5, wherein the induction technique unrolls the abstracted loops k+1 times before slicing, wherein k may be increased with every refinement to perform k induction.

### Claim 8 (depends on 5)

The system of claim 5, wherein the verification technique comprises one of a testing technique and a plurality of verification techniques.

### Claim 9

One or more non-transitory machine readable information storage mediums comprising one or more instructions which when executed by one or more hardware processors causes:
receiving, by one or more hardware processors, an abstracted piece of code corresponding to an original piece of code, wherein the abstracted piece of code comprises a plurality of base cases and inductive steps, wherein the inductive steps corresponds to a plurality of abstracted loops associated with the abstracted piece of code, and wherein each of the plurality of base cases and inductive steps are associated with a first set of property assertions to be verified;
simultaneously performing, by the one or more hardware processors, a bounded model checking on the abstracted piece of code to verify a property assertion from the first set of property assertions corresponding to a base case from the plurality of base cases and the inductive steps, wherein the abstracted piece of code is safe when the property assertion holds for the base case and inductive steps;
refining, by the one or more hardware processors, the abstracted piece of code when the abstracted piece of code is unsafe corresponding to the inductive steps until all causes leading to violation of a plurality of property assertions are analyzed, comprising:
obtaining an error trace in the abstraction using bounded model checking, wherein the error trace comprises a violation causing path corresponding to the property assertion from the first set of property assertions in the abstraction;
checking validity of the error trace on the original piece of code by utilizing a verification technique to obtain one of a valid error trace and an invalid error trace;
identifying a plurality of trace conditions, corresponding to the body of the plurality of abstracted loops by using the error trace, when the invalid error trace is obtained, wherein the plurality of trace conditions comprises a subset of conditions evaluated to true in the error trace;
negating the plurality of trace conditions to obtain a second set of property assertions;
obtaining the plurality of property assertions by performing a union of the first set of property assertions and one or more property assertions from the second set of property assertions;
further refining of the abstraction based on the plurality of property assertions by annotating the property assertions into the original piece of code and applying loop abstraction using induction technique to obtain a refined abstracted piece of code; and
bounded model checking of the refined abstracted piece of code to check whether the piece of code is safe.
