System and method for backing up data

• US 20040143713A1
• Filed: 01/22/2003
• Published: 07/22/2004
• Est. Priority Date: 01/22/2003
• Status: Active Grant

• Current Assignee: FalconStor, Inc (Hale Capital Management LP)
• Original Assignee: FalconStor, Inc (Hale Capital Management LP)
• Inventors: Niles, Ronald S., Lam, Wai
• Granted Patent: US 7,055,008 B2
• Time in Patent Office: Days
• US Class Current: 711/162
• CPC Class Codes: G02B 15/04 by changing a part
• CPC Class Codes: G02B 26/004 based on a displacement or a deformation of a fluid
• CPC Class Codes: G02B 27/646 compensating for small deviations, e.g. due to vibration or shake movement of one or more optical elements for control of motion blur in cameras, projectors or printers G03B2205/0007; image stabilisation in cameras peculiar to the presence or use of an electronic image sensor H04N23/68
• CPC Class Codes: G02B 7/102 controlled by a microcomputer cameras with interchangeable lenses G03B17/14
• CPC Class Codes: G03B 17/17 with reflectors arranged in beam forming the photographic image, e.g. for reducing dimensions of camera
• CPC Class Codes: G03B 2205/0046 Movement of one or more optical elements for zooming for optical zoom lenses in general G02B7/10
• CPC Class Codes: G03B 2205/0069 using electromagnetic actuators, e.g. voice coils
• CPC Class Codes: G03B 3/10 Power-operated focusing
• CPC Class Codes: G03B 5/00 Adjustment of optical system relative to image or object surface other than for focusing
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 16/11 File system administration, e.g. details of archiving or snapshots file system backup G06F11/14
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 21/56 Computer malware detection or handling, e.g. anti-virus arrangements
• CPC Class Codes: G06F 21/564 by virus signature recognition
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders
• CPC Class Codes: G06Q 20/4012 Verifying personal identification numbers [PIN]
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 63/145 : the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms
• CPC Class Codes: H04L 9/0643 : Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: Y10S 707/99953 : Recoverability
• CPC Class Codes: Y10S 707/99955 : Archiving or backup

Abstract

A hash-optimized backup system and method takes data blocks and generates a probabilistically unique digital fingerprint of the content of each data block using a substantially collision-free algorithm. The process compares the generated fingerprint to a database of stored fingerprints and, if the generated fingerprint matches a stored fingerprint, the data block is determined to already have been backed up, and therefore does not need to be backed up again. Only if the generated fingerprint does not match a stored fingerprint is the data block backed up, at which point the generated fingerprint is added to the database of stored fingerprints. Because the algorithm is substantially collision-free, there is no need to compare actual data content if there is a hash-value match. The process can also be used to audit software license compliance, inventory software, and detect computer-file tampering such as viruses and malware.

Claims

1. A method for backing up a data block having a data block location, the method comprising:

generating a digital fingerprint for the data block using a substantially collision-free algorithm;

comparing the digital fingerprint to digital fingerprints stored in a database; and

if the digital fingerprint does not match one of the stored digital fingerprints, backing up the data block and adding to the database the digital fingerprint and the data block location.

2. The method according to claim 1, wherein if the digital fingerprint matches one of the stored digital fingerprints, updating the database to associate the digital fingerprint with the data block location.

3. The method according to claim 2, wherein the algorithm is a hash function.

4. The method according to claim 3, wherein the hash function is MD5 or SHA-1.

5. A system for backing up a data block comprising:

a backup server having access to a digital fingerprint database; and

a source computer connected to the backup server via a communication path,

wherein the source computer generates a digital fingerprint of the data block using a substantially collision-free algorithm, and the backup server backs up the data block if the digital fingerprint does not match any digital fingerprint stored in the database.

6. The system according to claim 5, wherein the data block has a location on the source computer and the backup server adds to the database the digital fingerprint and the data block location.

7. The system according to claim 5, wherein the data block has a location on the source computer and if the digital fingerprint matches a digital fingerprint stored in the database, the backup server updates the database to associate the digital fingerprint with the data block location.

8. The system according to claim 5, further comprising a storage device connected to the backup server for storing the database.

9. The system according to claim 5, further comprising a storage device connected to the backup server for storing the backed-up data blocks.

10. The system according to claim 5, wherein the communication path is a network.

11. The system according to claim 10, wherein the network is a local area network.

12. The system according to claim 10, wherein the network is a wide area network.

13. The system according to claim 10, wherein the network is the Internet.

14. A method for auditing license restrictions of a computer program in an enterprise computing environment, comprising:

generating a digital fingerprint of at least one file in the computer program using a substantially collision-free algorithm;

generating a digital fingerprint for each file on each computer in the enterprise using the substantially collision-free algorithm;

comparing the digital fingerprints from the enterprise files with the digital fingerprint of the computer program file; and

comparing the number of fingerprint matches to the number of licenses allowed for the computer program.

15. The method according to claim 14, further comprising dividing the file into data blocks and generating a digital fingerprint of at least one data block.

16. A method for inventorying a computer program in an enterprise computing environment, comprising:

generating a digital fingerprint of at least one file in the computer program using a substantially collision-free algorithm;

generating a digital fingerprint for each file on each computer in the enterprise using the substantially collision-free algorithm;

comparing the digital fingerprints from the enterprise files with the digital fingerprint of the computer program file; and

counting the number of fingerprint matches.

17. The method according to claim 16, further comprising dividing each file into data blocks and generating a digital fingerprint of at least one data block.

18. A method for detecting file tampering on a computer, comprising:

generating a digital fingerprint for each file on the computer using a substantially collision-free algorithm; and

comparing the digital fingerprints of the computer files with digital fingerprints of the computer files generated when the files were previously saved,

wherein tampering exists on a file if the digital fingerprint of that file differs from the digital fingerprint generated when that file was previously saved.

19. The method according to claim 18, further comprising dividing each file into data blocks and generating a digital fingerprint of at least one data block.

20. The method according to claim 18, wherein the file tampering comprises a computer virus.

21. A method for detecting a computer virus on a computer, comprising:

generating a digital fingerprint of the computer virus using a substantially collision-free algorithm;

generating a digital fingerprint for each file on the computer using the substantially collision-free algorithm; and

comparing the digital fingerprints of the computer files with the digital fingerprint of the computer virus,

wherein the computer virus exists on the computer if any digital fingerprint of the computer files matches the digital fingerprint of the computer virus.

22. The method according to claim 21, further comprising dividing each file into data blocks and generating a digital fingerprint of at least one data block.