System and Method for Entropy-Based Near-Match Analysis

• US 20100235392A1
• Filed: 03/11/2010
• Published: 09/16/2010
• Est. Priority Date: 03/16/2009
• Status: Active Grant

• Current Assignee: Open Text Holdings, Inc. (Open Text Corporation)
• Original Assignee: Guidance Software Incorporated (Open Text Corporation)
• Inventors: Weber, Dominik, McCreight, Shawn
• Granted Patent: US 8,224,848 B2
• Time in Patent Office: Days
• US Class Current: 707/780
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 21/645 using a third party

Abstract

A system and method for an entropy-based near-match analysis identifies target files that are almost, but not identical, to a reference file. A computing processor computes entropies of the reference and target files, and determines the likeness of the target files to the references file based on the computed entropies. The computing processor determines a near match between the target file and the reference file if the likeness of the two files is within a user-defined tolerance level. According to one embodiment of the invention, the information entropy is a weighted value that takes into account the size of the file.

Claims

1. In a computer forensic investigation system including an examining machine coupled to one or more target machines over a data communications network, a method for identifying one or more files in the one or more target machines that are a near-match to a reference file, the method comprising:

computing or identifying an entropy of the reference file and outputting a first entropy value;

identifying a second entropy value of a target file stored in the one or more target machines;

determining a likeness of content in the target file to content in the reference file based on the first and second entropy values;

identifying a tolerance threshold;

determining a near-match between the target file and the reference file if the likeness of the target file to the reference file is within the tolerance threshold; and

displaying on a display, information on the target file in response to the determining of a near-match.

2. The method of claim 1, wherein the entropy value of the corresponding file is weighted based on a size of the corresponding file.

3. The method of claim 2, wherein the determining of the likeness of content includes:

computing a difference of the weighted entropy values of the target and reference files.

4. The method of claim 2, wherein the determining of the likeness of content includes:

computing a weighted difference of the weighted entropy values of the target and reference files, wherein the weighted difference is based on a size difference of the target and reference files.

5. The method of claim 1, wherein the entropy is calculated for blocks of data contained in the corresponding file.

6. The method of claim 5, wherein the entropy is a 0th order entropy based on a probability that a particular block of data will take a particular value.

7. The method of claim 5, wherein the entropy is a 1st order entropy based on a probability that a pair of adjacent blocks of data will take a particular value pair.

8. The method of claim 1, wherein the entropy is calculated for 1st derivative values of blocks of data contained in the corresponding file.

9. The method of claim 8 further comprising:

calculating 1st derivative values of the blocks of data, wherein the calculating includes;

for each block of data, calculating a difference in a value stored in the block of data and a value stored in an adjacent block of data; and

outputting a differential value in response.

10. The method of claim 8, wherein the entropy is a 0th order entropy based on a probability that a particular block of data will take a particular value.

11. The method of claim 8, wherein the entropy is a 1st order entropy based on a probability that a pair of adjacent data blocks will take a particular pair of values.

12. The method of claim 1 further comprising:

receiving the target file transmitted by the target machine over the data communications network; and

displaying the target file on a display monitor by the examining machine for conducting a forensic investigation of the target machine.

13. An examining machine coupled to one or more target machines over a data communications network, the examining machine comprising:

a display device;

processor coupled to the display device; and

a memory operably coupled to the processor and having program instructions stored therein, the processor being operable to execute the program instructions, the program instructions including;

computing or identifying an entropy of the reference file and outputting a first entropy value;

identifying a second entropy value of a target file stored in the one or more target machines;

determining a likeness of content in the target file to content in the reference file based on the first and second entropy values;

identifying a tolerance threshold;

determining a near-match between the target file and the reference file if the likeness of the target file to the reference file is within the tolerance threshold; and

displaying on the display device information on the target file in response to the determining of a near-match.

14. The examining machine of claim 13, wherein the entropy value of the corresponding file is weighted based on a size of the particular file.

15. The examining machine of claim 14, wherein the program instructions that determine the likeness of content include program instructions that:

compute a difference of the weighted entropy values of the target and reference files.

16. The examining machine of claim 14, wherein the program instructions that determine the likeness of content include program instructions that:

compute a weighted difference of the weighted entropy values of the target and reference files, wherein the weighted difference is based on a size difference of the target and reference files.

17. The examining machine of claim 13, wherein the entropy is calculated for blocks of data contained in the corresponding file.

18. The examining machine of claim 17, wherein the entropy is a 0th order entropy based on a probability that a particular block of data will take a particular value.

19. The examining machine of claim 17, wherein the entropy is a 1st order entropy based on a probability that a pair of adjacent blocks of data will take a particular value pair.

20. The examining machine of claim 13, wherein the entropy is calculated for 1st derivative values of blocks of data contained in the corresponding file.

21. The examining machine of claim 20, wherein the program instructions further include:

calculating 1st derivative values of the blocks of data, wherein the calculating includes;

for each block of data, calculating a difference in a value stored in the block of data and a value stored in an adjacent block of data; and

outputting a differential value in response.

22. The examining machine of claim 20, wherein the entropy is a 0th order entropy based on a probability that a particular block of data will take a particular value.

23. The examining machine of claim 20, wherein the entropy is a 1st order entropy based on a probability that a pair of adjacent data blocks will take a particular pair of values.

24. The examining machine of claim 13, wherein the program instructions further include:

receiving the target file transmitted by the target machine to the examining machine over the data communications network; and

displaying the target file on a display monitor for conducting a forensic investigation of the target machine.

25. A computer forensic investigation system for identifying one or more files in one or more target machines that are a near-match to a reference file, the system comprising:

means for computing or identifying an entropy of the reference file and outputting a first entropy value;

means for identifying a second entropy value of a target file stored in the one or more target machines;

means for determining a likeness of content in the target file to content in the reference file based on the first and second entropy values;

means for identifying a tolerance threshold;

means for determining a near-match between the target file and the reference file if the likeness of the target file to the reference file is within the tolerance threshold; and

means for displaying information on the target file in response to the determining of a near-match.