System and method for backing up data

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 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 hacked 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.

We Claim: 
     
         1 . A method for backing up data comprising:
 selecting a file for backup;   dividing the file into one or more data blocks;   generating a digital fingerprint for at least one of the one or more data blocks 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 of  claim 1 , comprising updating the database to associate the digital fingerprint with the data block location, if the digital fingerprint matches one of the stored, digital fingerprints. 
     
     
         3  The method of  claim 2 , wherein the algorithm comprises a hash function. 
     
     
         4 . The method of  claim 3 , wherein the hash function is MD5 or SHA-1. 
     
     
         5 . A system for backing up data comprising:
 a backup server having access to a digital fingerprint database; and   a source computer connected to the backup server via a communication path, the source computer being configured to:   select a file for backup;   divide the file into one or more data blocks;   generate a digital fingerprint of at least one of the one or more data blocks using a substantially collision-free algorithm;   wherein the backup server is configured to back up the at least one data block if the digital fingerprint does not match any digital fingerprint stored in the database.   
     
     
         6 . The system of  claim 5 , wherein the data block has a location on the source computer and the backup server is configured to add to the database the digital fingerprint and the data block location. 
     
     
         7 . The system of  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 is configured to update the database to associate the digital fingerprint with the data block location. 
     
     
         8 . The system of  claim 5 , further comprising a storage device connected to the backup server for storing the database. 
     
     
         9 . The system of  claim 5 , further comprising a storage device connected to the backup server for storing the backed-op data blocks. 
     
     
         10 . The system of  claim 5 , wherein the communication path comprises a network. 
     
     
         11 . The system of  claim 9 , wherein the network comprises a local area network, or a wide area network, and/or the Internet. 
     
     
         12 . A method for detecting file tampering on a computer, comprising:
 selecting a file;   dividing the selected file into one or more data blocks;   generating a digital fingerprint of at least one of the one or more data blocks;   generating a first digital fingerprint for the at feast one data block on the computer using a substantially collision-free algorithm at a first time;   generating second digital fingerprint for the at least one data block on the computer using the substantially collision-free algorithm at the second time after the first time;   comparing the first digital fingerprint of a data block generated at the first time with second digital fingerprint of a data block generated at the second time; and   determining whether tampering exists on a respective first file if the digital fingerprint of the at least one data block file differs from the second digital fingerprint of the corresponding at least one second data block.   
     
     
         13 . The method of  claim 12 , wherein the file tampering comprises a computer virus. 
     
     
         14 . A method for detecting a computer virus on a computer, comprising:
 generating a digital fingerprint of a computer virus using a substantially collision-free algorithm;   generating a digital fingerprint for a file on the computer using the substantially collision-free algorithm;   comparing the digital fingerprint of the computer file with the digital fingerprint of the computer virus; and   determining whether the computer file is a virus based on the comparison.   
     
     
         15 . The method of  claim 14 , further comprising dividing each file into data blocks and generating a digital fingerprint of at least one data block.