Coding scheme for file backup and systems based thereon

• US 6,178,536 B1
• Filed: 08/14/1997
• Issued: 01/23/2001
• Est. Priority Date: 08/14/1997
• Status: Expired due to Term

• Current Assignee: Trend Micro Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Sorkin, Gregory Bret
• Primary Examiner(s): De Cady, Albert
• Assistant Examiner(s): Chase, Shelly A.
• Application Number:
  US08/911,126
• Time in Patent Office: 1,258 Days
• Field of Search: 714/766, 714/6, 714/804, 714/758, 714/805, 714/763
• US Class Current: 714/766
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 21/565 by checking file integrity

Abstract

The present invention concerns a method and system for protection against corruption of data. In order to backup files to be stored in a storage medium, a set of redundant parity symbols is computed by encoding cross-sections across said files using a systematic code. These parity symbols and the files are then stored for later retrieval. If some of these files are erased, corrupted, damaged or infected by a virus, they are reconstructed by decoding the surviving files and the parity symbols.

Claims

1. Method for backing up at least one file of a plurality of files stored in a storage medium, comprising the steps of:

computing a set of redundant parity symbols by encoding cross-sections across said plurality of files using a systematic code, and

storing said parity symbols.

2. The method of claim 1, wherein from time to time a new set of parity symbols is computed.

3. The method of claim 1, wherein a new set of parity symbols is computed upon request by an application program or upon request by a user.

4. The method of claim 1, wherein said systematic code is either an error-correction code or an erasure code.

5. The method of claim 1, wherein said systematic code is a block code.

6. The method of claim 1, wherein said systematic code is a sparse code, and in particular a two-tree code.

7. The method of claim 1, wherein said redundant parity symbols and said plurality of files are stored in different logical or physical storage sections of one and the same storage medium.

8. The method of claim 1, wherein said redundant parity symbols and said plurality of files are stored in separate storage media.

9. Method for reconstructing a lost or damaged file, or a part thereof, stored in a storage medium in conjunction with at least one other file as a plurality of files, said method comprising steps of:

performing a preliminary step of generating and storing a set of redundant parity symbols which are computed by encoding cross-sections across said plurality of files using a systematic code,

decoding said set of redundant parity symbols and said lost or damaged file, or a part thereof, and

applying an exclusive-or operation using said decoded set of redundant parity symbols and said lost or damaged file, or a part thereof, as input, in order to reconstruct said lost or damaged file, or part thereof.

10. The method of claim 9, wherein said systematic code is either an error-correction code or an erasure code.

11. The method of claim 9, wherein said systematic code is a block code.

12. The method of claim 9, wherein said systematic code is a sparse code, and in particular a two-tree code.

13. The method of claim 9, wherein said redundant parity symbols and said plurality of files are stored in different logical or physical storage sections of one and the same storage medium.

14. The method of claim 9, wherein the reconstruction of a lost or damaged file, or a part thereof, is initiated by a verification module.

15. The method of claim 14, wherein said verification module identifies said lost or damaged file, or a part thereof.

16. The method of claim 14, wherein said verification module computes a current checksum and compares it to a saved checksum to identify said lost or damaged file.

17. The method of claim 14, wherein said verification module checks whether a set of files, a file, or a part thereof, has been corrupted by a computer virus.

18. A system for backing up a plurality of files stored in a storage medium, comprising:

an input port for feeding said plurality of files in an encoding unit,

said encoding unit for computing a set of redundant parity symbols by encoding cross-sections across said plurality of files using a systematic code, and

a storage section for storing said parity symbols.

19. The system of claim 18, additionally comprising an update unit which is employed to update said set of redundant parity symbols if one or more files of said plurality of files are changed.

20. The system of claim 19, wherein said update unit is provided with old and new values of said one or more changed files, and which updates those parity symbols of said set of redundant parity symbols which are affected by the file change.

21. The system of claim 19, comprising a timer which triggers from time to time the computation of said updated set of parity symbols.

22. The system of claim 19, wherein said computation of an updated set of parity symbols is triggered manually or automatically.

23. The system of claim 18, wherein said systematic code used by said encoding unit is either an error-correction code, or an erasure code.

24. The system of claim 18, wherein said systematic code used by said encoding unit is a block code.

25. The system of claim 18, wherein said systematic code used by said encoding unit is a sparse code, and in particular a two-tree code.

26. The system of claim 18, wherein said redundant parity symbols and said plurality of files are stored in different logical or physical storage sections of one and the same storage medium.

27. The system of claim 18, wherein said redundant parity symbols and said plurality of files are stored in separate storage media.

28. The system of claim 18, further comprising a verification module which identifies corrupted, damaged or lost files.

29. The system of claim 28, wherein said verification module comprises a virus detection software for identifying files infected by a virus.

30. The system of claim 18, wherein said encoding unit is also employed for updating said set of parity symbols.

31. The system of claim 18, wherein said systematic codes employed by said encoding unit preserve the original bits of said plurality of files such that said plurality of files stored in a storage medium are in the clear.

32. A system according to claim 18, wherein said plurality of files are computer files stored in a storage medium that is at least one of part of a computer or bidirectionally coupled to a computer.

33. A system according to claim 18, wherein said system is part of a file backup system.

34. A system according to claim 18, wherein said system is part of a virus disinfection system.

35. A system according to claim 18, wherein said system is part of an anti-virus protection system.

36. A method for anti-virus protection of files, comprising the steps of:

extracting redundant information pertaining to each file to be protected,

computing and storing parity bits for the extracted redundant information, wherein each said file to be protected is one of a set of files and said steps of extracting and computing comprise steps of computing a set of redundant parity bits by encoding cross-sections across said set of files using a systematic code, and then storing said parity bits,

detecting viral damage to one or more of said files to be protected,

using the stored parity bits and said redundant information for files not affected by viral damage to restore the redundant information for the one or more files affected by viral damage, and

using said redundant information and the one or more files affected by viral damage to restore each such file to its state prior to viral infection.

37. A method as in claim 36, wherein at least one file of the set of files has a length that differs from a length of others of the set of files.