Methods and systems for differencing orderly dependent files

• US 9,098,513 B1
• Filed: 08/27/2012
• Issued: 08/04/2015
• Est. Priority Date: 08/27/2012
• Status: Active Grant

• Current Assignee: Trend Micro Inc.
• Original Assignee: Trend Micro Inc.
• Inventors: Ren, Liwei, Xu, Qiuer
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): Abraham, Ahmed
• Application Number:
  US13/595,107
• Time in Patent Office: 1,072 Days
• Field of Search: 707/615, 707/616, 707/623, 707/624
• US Class Current: 1/1
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/325 Hash tables

Abstract

Difference data is generated between a reference file and a target file that are orderly dependent having common blocks that appear in the same order in both the reference and target files. The difference data is generated by comparing hash values of chunks of the reference file against hash values of parts of the target file to identity copy operations between the reference and target files. Chunks of the reference file and parts of the target file are loaded into main memory to create hashes for comparison and unloaded from the main memory after exhaustion. The difference data is included in a difference file, which is provided to one or more endpoint computers. In an endpoint computer, the target file is reconstructed using a copy of the reference file and the difference data from the difference file.

Claims

1. A method comprising:

receiving a reference file and a target file that are orderly dependent of each other, the reference and target files having common blocks that appear in a same order in both the reference and target files;

generating difference data between the reference and target files;

generating a difference file comprising the difference data;

receiving the difference file in a first computer over a computer network; and

in the first computer, reconstructing the target file using the difference data from the difference file and a copy of the reference file stored in the first computer,

wherein generating the difference data between the reference and target files comprises;

dividing the reference file into a plurality of chunks;

loading a first chunk and a second chunk of the reference file into a main memory of a second computer;

loading a part of the target file into the main memory of the second computer;

creating a rolling hash table of the first chunk and a rolling hash table of the second chunk of the reference file, the rolling hash table of the first chunk and the rolling hash table of the second chunk being separate rolling hash tables; and

identifying substrings that are common to both the reference and target files by comparing the rolling hash table of the first chunk of the reference file to a hash of the part of the target file.

2. The method of claim 1 wherein generating the difference data between the reference and target files further comprises:

unloading the first chunk of the reference file and the part of the target file from the main memory of the second computer;

loading a third chunk of the reference file into the main memory of the second computer;

creating a rolling hash table of the third chunk of the reference file; and

identifying substrings that are common to both the reference and target files by comparing the rolling hash table of the third chunk of the reference file to the hash of the part of the target file.

3. The method of claim 2 wherein generating the difference data between the reference and target files further comprises:

creating copy operations for substrings that are common to both the reference and target files.

4. The method of claim 3 wherein generating the difference data between the reference and target files further comprises:

creating a copy list comprising the copy operations.

5. The method of claim 4 wherein generating the difference file comprising the difference data comprises:

adding the copy list to the difference file.

6. The method of claim 1 further comprising:

determining a size of the reference file, wherein the size of the reference file is determined to be greater than a first threshold size.

7. The method of claim 1 wherein the reference file comprises an old version of a pattern file comprising virus signatures for an antivirus and the target file comprises a new version of the pattern file.

8. The method of claim 1 wherein the reference file comprises an old version of a pattern file comprising fingerprints for data loss prevention and the target file comprises a new version of the pattern file.

9. A system comprising:

a computer system that receives a reference file and a target file that are orderly dependent having common blocks that appear in a same order in both the reference and target files, generates a difference data for the reference and target files, formats the difference data into a difference file, and transmits the difference file to a plurality of endpoint computers; and

an endpoint computer in the plurality of endpoint computers that receives the difference file, obtains the difference data from the difference file, and reconstructs the target file in the endpoint computer using a copy of the reference file and the difference data,

wherein the computer system generates the difference data by dividing the reference file into a plurality of chunks, loading a first chunk of the reference file into a main memory of the computer system, loading a second chunk of the reference file into the main memory of the computer system, loading a part of the target file into the main memory of the computer system, creating a rolling hash table of the first chunk of the reference file, creating a rolling hash table of the second chunk of the reference file that is separate from the rolling hash table of the first chunk of the reference file, and comparing the rolling hash table of the first chunk of the reference file to a hash of the part of the target file to identify substrings that are common to both the reference and target files.

10. The system of claim 9 wherein the computer system generates the difference data by unloading the first chunk of the reference file from the main memory of the computer system, loading a third chunk of the reference file into the main memory of the computer system, creating a rolling hash table of the third chunk of the reference file, and comparing the rolling hash table of the third chunk of the reference file to the hash of the part of the target file to identify substrings that are common to both the reference and target files.

11. The system of claim 9 wherein the target file comprises an updated file for an antivirus program in the endpoint computer.

12. The system of claim 9 wherein the target file comprises an updated file for a data loss prevention (DLP) program in the endpoint computer.

13. The system of claim 9 wherein the endpoint computer follows a sequence of copy operations indicated in the difference file to reconstruct the target file.

14. A method comprising:

receiving a reference file and a target file that are determined to be orderly dependent of each other, the reference and target files having common blocks that appear in a same order in both the reference and target files;

dividing the reference file into a plurality of chunks;

loading a first a chunk in the plurality of chunks, a second chunk in the plurality of chunks, and a part of the target file into a main memory of a computer system;

creating a rolling hash table of the first chunk;

creating a rolling hash table of the second chunk that is separate from the rolling hash table of the first chunk;

comparing the rolling hash table of the first chunk and a hash of the first part of the target file to identify a copy operation for reconstructing the target file in an endpoint computer using a copy of the reference file and a listing of copy operations;

including the listing of copy operations in a difference file; and

providing the difference file to the endpoint computer.

15. The method of claim 14 further comprising:

unloading the first chunk from the main memory of the computer system;

loading a third chunk in the plurality of chunks into the main memory of the computer system;

creating a rolling hash table of the third chunk; and

comparing the rolling hash table of the third chunk and a hash of the target file to identify another copy operation for reconstructing the target file in the endpoint computer using the copy of the reference file and the listing of copy operations.

16. The method of claim 14 further comprising:

in the endpoint computer, following the listing of copy operations to copy blocks from the copy of the reference file to the target file being reconstructed.

17. The method of claim 14 further comprising:

determining a size of the reference file to be greater than a threshold size.

18. The method of claim 14 wherein the target file is an updated version of a pattern file of a computer security program.