HASH-BASED FILE COMPARISON

• US 20130066901A1
• Filed: 09/13/2011
• Published: 03/14/2013
• Est. Priority Date: 09/13/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hilke, James Coryell, Marcelais, Michael Ronn, Sullivan, Shawn Thomas
• Granted Patent: US 8,543,543 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31

Abstract

Concepts and technologies are described herein for hash-based file comparison. In accordance with the concepts and technologies disclosed herein, a comparison tool is configured to compare hash values in a first hash list associated with a first file to hash values in a second hash list corresponding to a second file. The hash values are computed for functional blocks of the respective files and therefore can be compared to indicate if the functional blocks of the two files match one another. If the hash values match, the functional blocks associated with the respective hash values can be determined to match, while hash values that do not match can indicate that the corresponding functional blocks do not match one another.

Claims

1. A computer-implemented method for performing a hash-based comparison of a first file and a second file, the computer-implemented method comprising performing computer-implemented operations for:

obtaining a first hash list having hash values corresponding to functional blocks of the first file;

obtaining a second hash list having hash values corresponding to functional blocks of the second file;

comparing, at a comparison tool, a first hash value in the first hash list to a corresponding hash value in the second hash list; and

determining, based upon the comparing, if a functional block of the first file matches a corresponding functional block of the second file.

2. The method of claim 1, wherein comparing the first hash value to the corresponding hash value comprises determining if the first hash value and the corresponding hash value are identical.

3. The method of claim 2, further comprising determining that the functional block of the first file matches the corresponding functional block of the second file in response to determining that the first hash value is identical to the corresponding hash value.

4. The method of claim 2, further comprising in response to determining that the first hash value is not identical to the corresponding hash value

determining that the functional block of the first file does not match the corresponding functional block of the second file, and

storing data indicating that the functional block of the first file does not match the corresponding functional block of the second file.

5. The method of claim 1, wherein obtaining the first hash list and the second hash list comprises:

generating the first hash list at the comparison tool; and

obtaining the second hash list at the comparison tool by retrieving the second hash list from a source configured to store the second hash list.

6. The method of claim 1, wherein obtaining the first hash list and the second hash list comprises generating the first hash list and the second hash list at the comparison tool by:

determining a file type associated with at least one of the first file or the second file; and

retrieving a rule set corresponding to the determined file type.

7. The method of claim 6, wherein generating the first hash list comprises:

selecting a block of code from the first file;

determining, based upon the rule set, if the block of code corresponds to a functional block of code; and

in response to determining that the block of code corresponds to the functional block of code

hashing the block of code to obtain the first hash value, and

storing the first hash value in the first hash list.

8. The method of claim 7, further comprising:

in response to determining that the block of code does not correspond to the functional block of code, determining if the first file comprises a further block of code; and

in response to determining that the first file comprises the further block of code

selecting the further block of code, and

determining if the further block of code corresponds to a further functional block of code.

9. The method of claim 1, wherein obtaining the first hash list and the second hash list comprises generating the first hash list and the second hash list at the comparison tool by:

determining a file type associated with at least one of the first file or the second file; and

in response to determining that a rule set corresponding to the determined file type is not available, obtaining a default rule set.

10. The method of claim 9, wherein the default rule set comprises a rule that each block of the first file and the second file is functional and is to be hashed.

11. A computer-implemented method for performing a hash-based comparison of a first file and a second file, the computer-implemented method comprising performing computer-implemented operations for:

obtaining the first file and the second file;

generating a first hash list having hash values corresponding to functional blocks of the first file;

generating a second hash list having hash values corresponding to corresponding functional blocks of the second file;

comparing, at a comparison tool, a first hash value in the first hash list to a corresponding hash value in the second hash list; and

determining, based upon the comparing, if one of the functional blocks of the first file matches a corresponding one of the functional blocks of the second file.

12. The method of claim 11, wherein comparing the first hash value to the corresponding hash value comprises determining if the first hash value and the corresponding hash value are identical, and further comprising determining that the functional block of the first file matches the corresponding functional block of the second file in response to determining that the first hash value is identical to the corresponding hash value.

13. The method of claim 11, wherein generating the first hash list comprises:

determining a file type associated with the first file;

determining if a rule set corresponding to the determined file type is available;

retrieving the rule set corresponding to the determined file type, in response to determining that the rule set is available; and

retrieving a default rule set in response to determining that the rule set is not available.

14. The method of claim 13, wherein generating the first hash list comprises:

selecting a block of code from the first file;

determining, based upon the rule set, if the block of code corresponds to a functional block of code; and

in response to determining that the block of code corresponds to the functional block of code

hashing the block of code to obtain the first hash value, and

storing the first hash value in the first hash list.

15. The method of claim 13, further comprising:

in response to determining that the block of code does not correspond to the functional block of code, determining if the first file comprises a further block of code; and

in response to determining that the first file comprises the further block of code

selecting the further block of code, and

determining if the further block of code corresponds to a further functional block of code.

16. The method of claim 13, wherein generating the first hash list comprises selecting a block of code from the first file, and in response to determining that the default rule set is used, hashing the block of code to obtain the first hash value and storing the first hash value in the first hash list.

17. A computer storage medium having computer readable instructions stored thereupon that, when executed by a computer, cause the computer to:

obtain a first file and a second file at a comparison tool;

determine, at the comparison tool, a file type associated with at least one of the first file or the second file;

retrieve a rule set corresponding to the determined file type;

generate, based at least partially upon the rule set, at least one of a first hash list or a second hash list, the first hash list having hash values corresponding to functional blocks of the first file and the second hash list having hash values corresponding to corresponding functional blocks of the second file;

compare, at a comparison tool, a first hash value in the first hash list to a corresponding hash value in the second hash list to determine if the first hash value matches the corresponding hash value;

in response to determining that the first hash value matches the corresponding hash value, determine that one of the functional blocks of the first file matches a corresponding one of the functional blocks of the second file; and

in response to determining that the first hash value does not match the corresponding hash value, determine that the one of the functional blocks of the first file (110) does not match the corresponding one of the functional blocks of the second file (112).

18. The computer storage medium of claim 17, wherein retrieving the rule set comprises

determining if the rule set corresponding to the determined file type is available;

retrieving the rule set corresponding to the determined file type, in response to determining that the rule set is available; and

retrieving a default rule set in response to determining that the rule set is not available.

19. The computer storage medium of claim 17, wherein generating the at least one of the first hash list or the second hash list comprises generating the second hash list, and wherein generating the second hash list further comprises:

selecting a block of code from the second file;

determining, based upon the rule set, if the block of code corresponds to a functional block of code; and

in response to determining that the block of code corresponds to the functional block of code

hashing the block of code to obtain the corresponding hash value, and

storing the corresponding hash value in the second hash list.

20. The computer storage medium of claim 19, further comprising:

in response to determining that the block of code does not correspond to the functional block of code, determining if the second file comprises a further block of code; and

in response to determining that the second file comprises the further block of code

selecting the further block of code, and

determining if the further block of code corresponds to a further functional block of code.