Method and system for data backup

• US 8,041,677 B2
• Filed: 10/12/2006
• Issued: 10/18/2011
• Est. Priority Date: 10/12/2005
• Status: Active Grant

• Current Assignee: Carbonite LLC (Open Text Corporation)
• Original Assignee: Datacastle Corporation (Open Text Corporation)
• Inventors: Sumner, Gary Steven, Ammons, Jaybe Mark, Liddell, Mike
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): Mitiku; Berhanu
• Application Number:
  US11/580,425
• Publication Number:
  US 20070100913A1
• Time in Patent Office: 1,832 Days
• Field of Search: None
• US Class Current: 707/640
• 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/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06F 2201/83 the solution involving signatures
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

Embodiments of the present invention are directed to Web-Services-based data backup and data-archiving applications that provide remote data backup and data archiving to private individuals, small businesses, and other organizations that need reliable, secure, geographically remote, and cost-effective data backup, data archiving, and backed-up and archived-data retrieval. In one embodiment of the present invention, a private or small-business client contracts with a service provider for data-backup and data-archiving services. The service provider, in turn, contracts with a remote data-storage facility to provide secure, reliable data backup and data archiving to the personal or small-business client. A client-side application is downloaded to the client computer and configured to allow the client to store locally encrypted data at the remote, data-storage facilities. Neither the service provider nor the data-storage facility can decrypt or otherwise access the information stored by the client.

Claims

1. A backup and restore system comprising:

a server-side portion that receives backup and restore requests and processes the backup and restore requests by returning encrypted data blocks in response to a restore request, and

storing encrypted data blocks and file signatures in response to a backup request; and

wherein a file signature includes a header that specifies a file-signature version and an ordered sequence of block descriptors, each block descriptor including a block hash and a block length; and

wherein a file signature is generated from a file by partitioning the file into an ordered sequence of natural blocks; and

coalescing the natural blocks, in order, in a an ordered sequence of approximately fixed-size blocks; and

for each approximately fixed-size block,

generating a block descriptor that includes an indication of the length of the block and a cryptographic hash of the block; and

appending the header to the generated block descriptors;

a client-side portion that provides a user-interface that allows files to designated for continuous backup, includes a service process that detects changes to files designated for continuous backup, computes file signatures, computes, by file-signature comparison, blocks needed to be stored for backup and restore operations, and issues requests for backup and restore operations, and

includes a transport service process for exchanging requests and data with the server-side portion.

2. The backup and restore system of claim 1 wherein each cryptographic hash is generated from each approximately fixed-size block by appending a file-encryption key, an encryption-algorithm identifier, and a compression-algorithm identifier to the approximately fixed-size block to generate a fully-specified approximately fixed-size block and applying the cryptographic hash function to the fully-specified approximately fixed-size block.

3. The backup and restore system of claim 1 wherein the service process periodically compares current timestamps of files to previously recorded timestamps to detect those files altered since a previous file-change-detection iteration.

4. The backup and restore system of claim 1 wherein the service process determines blocks needed to be sent to the server portion to backup a file by:

generating a current file signature for the file;

comparing the current file signature to a previously generated file signature to determine data blocks in the file that have changed since the file was last backed up;

determining those data blocks in the file that have changed since the file was last backed up that are not currently stored by the server-side portion as data blocks needed to be stored; and

transmitting the current file signature and determined data blocks needed to be stored to the server portion.

5. The backup and restore system of claim 1 wherein the service process determines blocks needed to be requested from the server portion to restore a file by:

obtaining a file signature for an instance of the file to be restored; and

determining the blocks identified by block hashes in the file signature that are not currently available on the client.

6. The backup and restore system of claim 1 wherein each data block identified by a computed block hash is stored only once by the server-side portion, regardless of the number of times the data block occurs in files designated for continuous backup.

7. The backup and restore system of claim 1 wherein each data block transmitted to the server-side portion is encrypted using a file-encryption key known only to the client that transmitted the data block to the server-side portion, so that the server-side portion cannot access client data stored by the server-side portion.

8. The backup and restore system of claim 1 wherein the server-side portion stores doubly encrypted file-encryption keys on behalf of clients so that clients can restore lost file-encryption keys without providing access to the file-encryption keys to the server-side portion or other clients.