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.
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
| # | 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 |
| 1 | search_strategy_20-02-2020.pdf |