System and method for verifying the integrity and completeness of records

• US 8,055,635 B2
• Filed: 06/05/2008
• Issued: 11/08/2011
• Est. Priority Date: 02/08/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hsu, Windsor Wee Sun, Ma, Xiaonan
• Primary Examiner(s): Vital; Pierre
• Assistant Examiner(s): OBISESAN, AUGUSTINE KUNLE
• Application Number:
  US12/134,089
• Publication Number:
  US 20080270372A1
• Time in Patent Office: 1,251 Days
• Field of Search: None
• US Class Current: 707/698
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A correctness verification system receives a query, executes the query using a query logic, and produces a query result. The query result comprises data records that satisfy the query, data verification objects associated with the data records, index segments accessed during the execution of the query, index verification objects associated with the index segments, and the query. The system transfers the query result to a verification system. The verification system verifies correctness of the query result by executing the query using the query logic. The verification system uses the data verification objects to verify integrity of the data objects, uses the index verification objects to verify the integrity of the index segments, and uses the index verification objects and the data verification objects to verify the completeness of the query result.

Claims

1. A processor-implemented method for verifying the correctness of query results, comprising:

receiving a query at a data repository;

indexing the data repository;

dividing the index of the data repository into index segments;

updating the index segments after an input of data into the data repository;

executing the received query using a query logic;

producing a query output that includes a query result and verification information associated with the query result;

transferring the query output to a verification system; and

verifying the integrity and completeness of the query result using the verification information included in the query output,

wherein verifying the integrity includes verifying that the query result has not been tampered with, and

wherein verifying the completeness of the query result includes verifying that there are no additions or omissions to the query result, and verifying completeness of the query result includes verifying legitimacy of the updates to the index segments by calculating a root hash of a hash tree from a previous content of a metadata page in the data repository and from nodes along a path from a previous content of the metadata page to a root.

2. The method of claim 1 including computing a secure one-way hash of one of the data records during an insertion of said one of the data records into the data repository,

wherein the query result includes data records that satisfy the received query.

3. The method of claim 1, wherein the query result includes data verification objects associated with the data records in the query result and the received query.

4. The method of claim 3, wherein the query result further includes those of the index segments which are accessed during the executing of the received query.

5. The method of claim 4, wherein the query result further includes index verification objects associated with the accessed index segments and the received query.

6. The method of claim 5, further comprising verifying the correctness of the query result by executing an equivalent query logic on the query specified in the query output.

7. The method of claim 6, further comprising using the data verification objects to verify the integrity of the data records in the query result, by means of the accessed index segments and the associated index verification objects to verify the completeness of the query result.

8. A computer program product having a plurality of executable instruction codes stored on a non-transitory computer storage medium, for verifying the correctness of query results, comprising:

a set of instruction codes for receiving a query at a data repository;

a set of instruction codes for executing the received query using a query logic;

a set of instruction codes for producing a query output that includes a query result and verification information associated with the query result;

a set of instruction codes for transferring the query output to a verification system, wherein the verification system includes verifying indexes migrated to the data repository from a second data repository wherein the indexes were also previously verified in the second data repository; and

a set of instruction codes for verifying the integrity and completeness of the query result using the verification information included in the query output,

wherein verifying the integrity includes verifying that the query result has not been tampered with, and

wherein verifying the completeness of the query result includes verifying that there are no additions or omissions to the query result.

9. The computer program product of claim 8 including repeating the verifying of the query result for step N+1 until an end of query execution,

wherein the query result includes data records that satisfy the received query, and

wherein the verifying the query result includes representing the addresses of metadata pages accessed in a step N as a function of all metadata pages accessed during previous steps.

10. The computer program product of claim 8, wherein the query result includes data verification objects associated with the data records in the query result and the received query.

11. The computer program product of claim 10, wherein the query result further includes index segments accessed during the executing of the received query.

12. The computer program product of claim 11, wherein the query result further includes index verification objects associated with the accessed index segments and the received query.

13. The computer program product of claim 12, further comprising a set of instruction codes for verifying the correctness of the query result by executing an equivalent query logic on the query specified in the query output.

14. The computer program product of claim 13, further comprising a set of instruction codes for using the data verification objects to verify the integrity of the data records in the query result, by means of the accessed index segments and the associated index verification objects to verify the completeness of the query result.

15. A processor-implemented system for verifying the correctness of query results, comprising:

a query system for receiving a query at a data repository;

a data retrieval system for executing the received query using a query logic;

the query system producing a query output that includes a query result and verification information associated with the query result;

the query system transferring the query output to a verification system; and

a data verification system for verifying the integrity and completeness of the query result using the verification information included in the query output,

wherein the verifying the integrity includes verifying that the query result has not been tampered with, and

wherein the verifying the completeness of the query result includes verifying that there are no additions or omissions to the query result

wherein the query result includes data verification objects that include secure one-way hashes of the content of an index segment of the data repository and a timestamp, and

the data verification system changes location of the hashing of data records from inside a trusted domain to outside the trusted domain depending on security requirements.

16. The system of claim 15, wherein the query result includes data records that satisfy the received query.

17. The system of claim 15, wherein the data verification objects are associated with the data records in the query result and the received query, and

wherein the verification objects further include a relative location of a corresponding metadata page in a metadata structure.

18. The system of claim 17, wherein the query result further includes index segments accessed during the executing of the received query.

19. The system of claim 18, wherein the query result further includes index verification objects associated with the accessed index segments and the received query.

20. A computer processor-implemented method for providing a service to verify the correctness of data records, comprising:

identifying a query result that includes a query, a query result comprising a plurality of data records satisfying the query, a plurality of data verification objects, a plurality of index segments accessed in execution of the query, and a plurality of index verification objects;

invoking a correctness verification utility, wherein the query result is made available to the correctness verification utility for consideration; and

receiving a correctness verification of the data records from the correctness verification utility,

wherein verifying the integrity of the query result includes verifying that the query result has not been tampered with,

wherein verifying the completeness of the query result includes verifying that there are no additions or omissions to the query result, and

wherein verifying the correctness of the query result includes verifying both the integrity and completeness of the query result;

wherein the query result includes data verification objects that include secure one-way hashes of the content of an index segment of the data repository and a timestamp, and

changing location of the hashing of data records from inside a trusted domain to outside the trusted domain depending on security requirements.