System and method for backing up data

• US 7,055,008 B2
• Filed: 01/22/2003
• Issued: 05/30/2006
• Est. Priority Date: 01/22/2003
• Status: Active Grant

• Current Assignee: FalconStor, Inc (Hale Capital Management LP)
• Original Assignee: Falconstor Software Incorporated (Hale Capital Management LP)
• Inventors: Niles, Ronald S., Lam, Wai
• Primary Examiner(s): Padmanabhan, Mano
• Assistant Examiner(s): Song, Jasmine
• Application Number:
  US10/348,834
• Publication Number:
  US 20040143713A1
• Time in Patent Office: 1,224 Days
• Field of Search: 713/181, 713/188, 711/161, 711/162, 707/204
• 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 data, the method comprising:

generating a first digital fingerprint representing a first data block stored at a first location in a first memory device;

comparing the first digital fingerprint to one or more values stored in a database;

if the first digital fingerprint does not match any of the values stored in the database;

storing a copy of the first data block in a second memory device separate from the first memory device;

storing the first digital fingerprint in the database;

and storing the first location in the database in association with the first digital fingerprint;

generating a second digital fingerprint representing a second data block stored at a second location in a third memory device;

comparing the second digital fingerprint to the one or more values stored in the database; and

if the second digital fingerprint matches one of the one or more values stored in the database, storing the second location in the database in association with the one value.

2. The method according to claim 1, wherein the first memory device and the third memory device are in the same computer.

3. The method according to claim 1, comprising:

generating the first digital fingerprint using a substantially collision-free algorithm.

4. The method according to claim 3, wherein the algorithm comprises a hash function.

5. The method according to claim 4, wherein the hash function comprises a message digest 5 (MD5) algorithm.

6. The method according to claim 4, wherein the hash function comprises a secure hash algorithm.

7. The method according to claim 3, comprising:

generating the second digital fingerprint using a substantially collision-free algorithm.

8. The method according to claim 1, comprising:

generating the second digital fingerprint using a substantially collision-free algorithm.

9. The method according to claim 8, wherein the algorithm comprises a hash function.

10. The method according to claim 9, wherein the hash function comprises a message digest 5 (MD5) algorithm.

11. The method according to claim 9, wherein the hash function comprises a secure hash algorithm.

12. The method according to claim 1, further comprising:

transmitting the copy of the first data block to the second memory device via a storage area network (SAN).

13. The method according to claim 1, further comprising:

transmitting the copy of the first data block to the second memory device via a large area network (LAN).

14. The method according to claim 1, further comprising:

transmitting the copy of the first data block to the second memory device via an internet.

15. The method according to claim 1, further comprising:

selecting a file stored in the first memory device; and

defining one or more data blocks associated with the stored file.

16. The method according to claim 15, wherein the file is associated with a software package used to verify that an enterprise is in compliance with selected licensing requirements.

17. An apparatus for backing up data, the apparatus comprising:

means for generating a first digital fingerprint representing a first data block stored at a first location in a first memory device;

means for comparing the first digital fingerprint to one or more values stored in a database;

means for storing a copy of the first data block in a second memory device separate from the first memory device, for storing the first digital fingerprint in the database, and for storing the first location in the database in association with the first digital fingerprint, if the first digital fingerprint does not match any of the values stored in the database;

means for generating a second digital fingerprint representing a second data block stored at a second location in a third memory device;

means for comparing the second digital fingerprint to the one or more values stored in the database; and

means for storing the second location in the database in association with the one value, if the second digital fingerprint matches one of the one or more values stored in the database.

18. A system for backing up data, the system comprising:

a first memory device configured to store data;

a second memory device configured to store data;

a third memory device configured to store data;

a database configured to store one or more digital fingerprints; and

a processor configured to;

generate a first digital fingerprint representing a first data block stored at a first location in the first memory device;

compare the first digital fingerprint to one or more values stored in the database;

if the first digital fingerprint does not match any of the values stored in the database;

store a copy of the first data block in the second memory device separate from the first memory device;

store the first digital fingerprint in the database; and

store the first location in the database in association with the first digital fingerprint;

generate a second digital fingerprint representing a second data block stored at a second location in the third memory device;

compare the second digital fingerprint to the one or more values stored in the database; and

store the second location in the database in association with the one value, if the second digital fingerprint matches one of the one or more values stored in the database.

19. The system according to claim 18, wherein the first memory device and the third memory device are the same.

20. The system according to claim 18, wherein the processor is further configured to:

generate the first digital fingerprint using a substantially collision-free algorithm.

21. The system according to claim 20, wherein the algorithm comprises a hash function.

22. The system according to claim 21, wherein the hash function comprises a message digest 5 (MD5) algorithm.

23. The system according to claim 21, wherein the hash function comprises a secure hash algorithm.

24. The system according to claim 20, wherein the processor is further configured to:

generate the second digital fingerprint using a substantially collision-free algorithm.

25. The system according to claim 18, wherein the processor is further configured to:

generate the second digital fingerprint using a substantially collision-free algorithm.

26. The system according to claim 25, wherein the algorithm comprises a hash function.

27. The system according to claim 26, wherein the hash function comprises a message digest 5 (MD5) algorithm.

28. The system according to claim 26, wherein the hash function comprises a secure hash algorithm.

29. The system according to claim 18, wherein the processor is further configured to:

transmit the copy of the first data block to the second memory device via a storage area network (SAN).

30. The system according to claim 18, wherein the processor is further configured to:

transmit the copy of the first data block to the second memory device via a large area network (LAN).

31. The system according to claim 18, wherein the processor is further configured to:

transmit the copy of the first data block to the second memory device via an internet.

32. The system according to claim 18, wherein the processor is further configured to:

select a file stored in the first memory device; and

define one or more data blocks associated with the stored file.

33. The system according to claim 32, wherein the file is associated with a software package used to verify that an enterprise is in compliance with selected licensing requirements.