Sign In to Follow Application
View All Documents & Correspondence

Data Structure Abstraction For Model Checking

Abstract: A system and a method for data structure abstraction in a source code for model checking of the source code are provided. The method includes identifying data structure accesses in the source code. Loops are identified in the data structure accesses, and loop-types are identified in the loops. An abstracted code is generated based on the loop types for abstracting the data structure. Abstracting the data structure includes, for each loop, replacing the data structure accesses by one of a corresponding representative element and a non-deterministic value in the loop body of said loop based on the elements accessed, and eliminating loop control statement of said loop operating on elements of the data structure based on loop type of said loop, and adding a plurality of non-array assignments at a start and after the loop body of the source code. The abstracted code is provided for the model checking.

Get Free WhatsApp Updates!
Notices, Deadlines & Correspondence

Patent Information

Application #
Filing Date
09 March 2016
Publication Number
45/2017
Publication Type
INA
Invention Field
COMPUTER SCIENCE
Status
Email
iprdel@lakshmisri.com
Parent Application

Applicants

TATA CONSULTANCY SERVICES LIMITED
Nirmal Building, 9th Floor, Nariman Point, Mumbai-400021, Maharashtra, India

Inventors

1. RAMANATHAN, Venkatesh
Tata Consultancy Services Limited Tata Research Development & Design Centre, 54-B, Hadapsar Industrial Estate, Hadapsar, Pune - 411 013 Maharashtra, India
2. JANA, Anushri
Tata Consultancy Services Limited Tata Research Development & Design Centre, 54-B, Hadapsar Industrial Estate, Hadapsar, Pune - 411 013 Maharashtra, India

Specification

Claims:1. A computer implemented method for data structure abstraction in a source code, for model checking of the source code, the method comprising:
receiving a source code for abstraction;
identifying one or more data structure accesses in the source code, the one or more data structure accesses comprising expressions for referencing elements of a data structure to access the data structure in the source code;
identifying one or more loops in the one or more data structure accesses, a loop of the one or more loops comprising control statement and a loop body, wherein the loop causes the loop body to be repeatedly executed based on the control statement;
identifying one or more loop-types in the one or more loops;
generating an abstracted code based at least on the one or more loop types, the abstracted code capable of abstracting the data structure, wherein abstracting the data structure comprises performing, for each loop of the one or more loops:
replacing the one or more data structure accesses by one of a corresponding representative element and a non-deterministic value in the loop body of said loop based on the elements of the data structure being accessed in a current iteration of said loop,
eliminating loop control statement of said loop operating on the elements of the data structure based on a loop type of said loop, and
adding a plurality of non-array assignments at a start of the loop body and after the loop body of the source code; and
providing the abstracted code for the model checking.

2. The method as claimed in claim 1, wherein a data structure access of the one of more data structure accesses comprises one of an array, an hash table, a graph, a tree, a class, a set, and a map.
3. The method as claimed in claim 1, wherein the one or more loop types comprises a complete loop and a partial loop, wherein the complete loop comprises a loop iterating over all of the elements of the data structure and the partial loop comprises a loop iterating over a subset of the elements of the data structure.
4. The method as claimed in claim 3, wherein eliminating the loop control statement of said loop comprises:
determining the loop type of said loop to be the complete loop; and
replacing the loop control statement with an if (true) statement.

5. The method as claimed in claim 3, wherein eliminating the loop control statement of said loop comprises:
determining the loop type of said loop to be the partial loop; and
replacing the loop control statement with an if(non-deterministic) statement.

6. The method as claimed in claim 1, further comprising determining a location of occurrence of the data structure access, the location being one of a Left Hand Side (LHS) and Right Hand Side (RHS) of a statement of the source code.
7. The method as claimed in claim 6, wherein on determination that the location of occurrence of the data structure access to be the RHS of the statement of the source code, the method further comprises:
determining the accessed element such that the accessed element is associated with an iteration different from a current iteration of said loop; and
replacing the one or more data structure accesses by a corresponding non-deterministic value.

8. The method as claimed in claim 6, wherein on determination that the location of occurrence of the data structure access to be the LHS of the statement of the source code, the method further comprises:
replacing the one or more data structure accesses by a corresponding representative element.

9. The method as claimed in claim 6, comprising prior to adding the plurality of non-array assignments at the start of the loop body and after the loop body of the source code:
identifying non-data structure variables in the loop body in the LHS of the statement; and
assigning corresponding non-deterministic values to the non-data structure variables.

10. A computer implemented system for reconciliation of records comprising:
at least one memory; and
at least one processor, the at least one memory coupled to the at least one processor wherein the at least one processor is capable of executing programmed instructions stored in the at least one memory to:
receive a source code for abstraction;
identify one or more data structure accesses in the source code, the one or more data structure accesses comprising expressions for referencing elements of the data structures to access the data structure in the source code;
identify one or more loops in the one or more data structure accesses, a loop of the one or more loops comprising control statement and a loop body, wherein the loop causes the loop body to be repeatedly executed based on the control statement;
identify one or more loop-types in the one or more loops;
generate an abstracted code based at least on the one or more loop types, the abstracted code capable of abstracting the data structure, wherein abstracting the data structure comprises performing, for each loop of the one or more loops:
replace the one or more data structure accesses by one of a corresponding representative element and a non-deterministic value in the loop body of said loop based on the elements of the data structure being accessed in a current iteration of said loop,
eliminate loop control statement of said loop operating on the elements of the data structure based on a loop type of said loop, and
add a plurality of non-array assignments at a start of the loop body and after the loop body of the source code; and
provide the abstracted code for the model checking.

11. The system as claimed in claim 10, wherein a data structure access of the one of more data structure accesses comprises one of an array, an hash table, a graph, a tree, a class, a set, and a map.
12. The system as claimed in claim 10, wherein the one or more loop types comprises a complete loops and partial loop, and wherein a complete loop comprises a loop iterating over all of elements of the data structure and a partial loop comprises a loop iterating over a subset of elements of the data structure.
13. The system as claimed in claim 12, wherein to eliminate the loop control statement of said loop, the at least one processor is capable of executing programmed instructions to:
determine the loop type of said loop to be the complete loop; and
replace the loop control statement with an if (true) statement.

14. The system as claimed in claim 13, wherein to eliminate the loop control statement of said loop, the at least one processor is capable of executing programmed instructions to:
determine the loop type of said loop to be the partial loop; and
replace the loop control statement with an if(non-deterministic) statement.

15. The system as claimed in claim 10, wherein the at least one processor is capable of executing programmed instructions to determine a location of occurrence of the data structure access, the location being one of a Left Hand Side (LHS) and Right Hand Side (RHS) of a statement of the source code.
16. The system as claimed in claim 15, wherein on determination that the location of occurrence of the data structure access to be the RHS of the statement of the source code, the at least one processor is capable of executing programmed instructions to:
determine the accessed element such that the accessed element is associated with an iteration different from a current iteration of said loop; and
replace the one or more data structure accesses by a corresponding non-deterministic value.

17. The system as claimed in claim 15, wherein on determination that the location of occurrence of the data structure access to be the LHS of the statement of the source code, the at least one processor is capable of executing programmed instructions to:
replace the one or more data structure accesses by a corresponding representative element.

18. The system as claimed in claim 15, prior to adding the plurality of non-array assignments at the start of the loop body and after the loop body of the source code, the at least one processor is capable of executing programmed instructions to:
identify non-data structure variables in the loop body in the LHS of the statement; and
assign corresponding non-deterministic values to the non-data structure variables
, Description:As Attached

Documents

Application Documents

# Name Date
1 201621008284-Response to office action [13-03-2025(online)].pdf 2025-03-13
1 201621008284-US(14)-HearingNotice-(HearingDate-18-02-2025).pdf 2025-01-02
1 Form 5 [09-03-2016(online)].pdf 2016-03-09
2 201621008284-FORM 3 [23-04-2024(online)]-1.pdf 2024-04-23
2 201621008284-Written submissions and relevant documents [13-03-2025(online)].pdf 2025-03-13
2 Form 3 [09-03-2016(online)].pdf 2016-03-09
3 201621008284-Correspondence to notify the Controller [25-02-2025(online)].pdf 2025-02-25
3 201621008284-FORM 3 [23-04-2024(online)].pdf 2024-04-23
3 Form 18 [09-03-2016(online)].pdf 2016-03-09
4 Drawing [09-03-2016(online)].pdf 2016-03-09
4 201621008284-PETITION UNDER RULE 137 [23-04-2024(online)].pdf 2024-04-23
4 201621008284-Correspondence to notify the Controller [24-02-2025(online)].pdf 2025-02-24
5 Description(Complete) [09-03-2016(online)].pdf 2016-03-09
5 201621008284-Written submissions and relevant documents [23-04-2024(online)].pdf 2024-04-23
5 201621008284-US(14)-ExtendedHearingNotice-(HearingDate-27-02-2025)-1130.pdf 2025-02-24
6 201621008284-POWER OF ATTORNEY-(21-04-2016).pdf 2016-04-21
6 201621008284-FORM-26 [04-04-2024(online)].pdf 2024-04-04
6 201621008284-Correspondence to notify the Controller [18-02-2025(online)].pdf 2025-02-18
7 201621008284-CORRESPONDENCE-(21-04-2016).pdf 2016-04-21
7 201621008284-Correspondence to notify the Controller [27-01-2025(online)].pdf 2025-01-27
7 201621008284-Correspondence to notify the Controller [13-03-2024(online)].pdf 2024-03-13
8 201621008284-US(14)-HearingNotice-(HearingDate-08-04-2024).pdf 2024-03-07
8 201621008284-US(14)-HearingNotice-(HearingDate-18-02-2025).pdf 2025-01-02
8 REQUEST FOR CERTIFIED COPY [03-03-2017(online)].pdf 2017-03-03
9 201621008284-CLAIMS [24-08-2020(online)].pdf 2020-08-24
9 201621008284-FORM 3 [23-04-2024(online)]-1.pdf 2024-04-23
9 Form 3 [08-03-2017(online)].pdf 2017-03-08
10 201621008284-COMPLETE SPECIFICATION [24-08-2020(online)].pdf 2020-08-24
10 201621008284-FORM 3 [23-04-2024(online)].pdf 2024-04-23
10 Abstract.jpg 2018-08-11
11 201621008284-FER_SER_REPLY [24-08-2020(online)].pdf 2020-08-24
11 201621008284-Form 1-010416.pdf 2018-08-11
11 201621008284-PETITION UNDER RULE 137 [23-04-2024(online)].pdf 2024-04-23
12 201621008284-Correspondence-010416.pdf 2018-08-11
12 201621008284-OTHERS [24-08-2020(online)].pdf 2020-08-24
12 201621008284-Written submissions and relevant documents [23-04-2024(online)].pdf 2024-04-23
13 201621008284-FORM-26 [04-04-2024(online)].pdf 2024-04-04
13 201621008284-FORM 3 [30-07-2020(online)].pdf 2020-07-30
13 201621008284-CORRESPONDENCE(IPO)-(CERTIFIED)-(8-3-2017).pdf 2018-08-11
14 201621008284-Correspondence to notify the Controller [13-03-2024(online)].pdf 2024-03-13
14 201621008284-FER.pdf 2020-02-24
14 201621008284-Information under section 8(2) [30-07-2020(online)].pdf 2020-07-30
15 201621008284-FER.pdf 2020-02-24
15 201621008284-Information under section 8(2) [30-07-2020(online)].pdf 2020-07-30
15 201621008284-US(14)-HearingNotice-(HearingDate-08-04-2024).pdf 2024-03-07
16 201621008284-CLAIMS [24-08-2020(online)].pdf 2020-08-24
16 201621008284-CORRESPONDENCE(IPO)-(CERTIFIED)-(8-3-2017).pdf 2018-08-11
16 201621008284-FORM 3 [30-07-2020(online)].pdf 2020-07-30
17 201621008284-COMPLETE SPECIFICATION [24-08-2020(online)].pdf 2020-08-24
17 201621008284-Correspondence-010416.pdf 2018-08-11
17 201621008284-OTHERS [24-08-2020(online)].pdf 2020-08-24
18 201621008284-FER_SER_REPLY [24-08-2020(online)].pdf 2020-08-24
18 201621008284-Form 1-010416.pdf 2018-08-11
19 201621008284-COMPLETE SPECIFICATION [24-08-2020(online)].pdf 2020-08-24
19 201621008284-OTHERS [24-08-2020(online)].pdf 2020-08-24
19 Abstract.jpg 2018-08-11
20 201621008284-CLAIMS [24-08-2020(online)].pdf 2020-08-24
20 201621008284-FORM 3 [30-07-2020(online)].pdf 2020-07-30
20 Form 3 [08-03-2017(online)].pdf 2017-03-08
21 REQUEST FOR CERTIFIED COPY [03-03-2017(online)].pdf 2017-03-03
21 201621008284-US(14)-HearingNotice-(HearingDate-08-04-2024).pdf 2024-03-07
21 201621008284-Information under section 8(2) [30-07-2020(online)].pdf 2020-07-30
22 201621008284-Correspondence to notify the Controller [13-03-2024(online)].pdf 2024-03-13
22 201621008284-CORRESPONDENCE-(21-04-2016).pdf 2016-04-21
22 201621008284-FER.pdf 2020-02-24
23 201621008284-CORRESPONDENCE(IPO)-(CERTIFIED)-(8-3-2017).pdf 2018-08-11
23 201621008284-FORM-26 [04-04-2024(online)].pdf 2024-04-04
23 201621008284-POWER OF ATTORNEY-(21-04-2016).pdf 2016-04-21
24 Description(Complete) [09-03-2016(online)].pdf 2016-03-09
24 201621008284-Written submissions and relevant documents [23-04-2024(online)].pdf 2024-04-23
24 201621008284-Correspondence-010416.pdf 2018-08-11
25 201621008284-PETITION UNDER RULE 137 [23-04-2024(online)].pdf 2024-04-23
25 Drawing [09-03-2016(online)].pdf 2016-03-09
25 201621008284-Form 1-010416.pdf 2018-08-11
26 201621008284-FORM 3 [23-04-2024(online)].pdf 2024-04-23
26 Abstract.jpg 2018-08-11
26 Form 18 [09-03-2016(online)].pdf 2016-03-09
27 201621008284-FORM 3 [23-04-2024(online)]-1.pdf 2024-04-23
27 Form 3 [08-03-2017(online)].pdf 2017-03-08
27 Form 3 [09-03-2016(online)].pdf 2016-03-09
28 201621008284-US(14)-HearingNotice-(HearingDate-18-02-2025).pdf 2025-01-02
28 Form 5 [09-03-2016(online)].pdf 2016-03-09
28 REQUEST FOR CERTIFIED COPY [03-03-2017(online)].pdf 2017-03-03
29 201621008284-Correspondence to notify the Controller [27-01-2025(online)].pdf 2025-01-27
29 201621008284-CORRESPONDENCE-(21-04-2016).pdf 2016-04-21
30 201621008284-POWER OF ATTORNEY-(21-04-2016).pdf 2016-04-21
30 201621008284-Correspondence to notify the Controller [18-02-2025(online)].pdf 2025-02-18
31 201621008284-US(14)-ExtendedHearingNotice-(HearingDate-27-02-2025)-1130.pdf 2025-02-24
31 Description(Complete) [09-03-2016(online)].pdf 2016-03-09
32 Drawing [09-03-2016(online)].pdf 2016-03-09
32 201621008284-Correspondence to notify the Controller [24-02-2025(online)].pdf 2025-02-24
33 201621008284-Correspondence to notify the Controller [25-02-2025(online)].pdf 2025-02-25
33 Form 18 [09-03-2016(online)].pdf 2016-03-09
34 Form 3 [09-03-2016(online)].pdf 2016-03-09
34 201621008284-Written submissions and relevant documents [13-03-2025(online)].pdf 2025-03-13
35 Form 5 [09-03-2016(online)].pdf 2016-03-09
35 201621008284-Response to office action [13-03-2025(online)].pdf 2025-03-13
36 201621008284-RELEVANT DOCUMENTS [26-09-2025(online)].pdf 2025-09-26
37 201621008284-FORM-24 [26-09-2025(online)].pdf 2025-09-26

Search Strategy

1 search_strategy_20-02-2020.pdf