Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1997-08-14
2001-01-23
De Cady, Albert (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S804000
Reexamination Certificate
active
06178536
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a novel scheme which allows to protect against limited damage of stored data. In particular, data backup systems, and anti-virus protection systems (including virus disinfection systems) based on the novel scheme are addressed.
BACKGROUND OF THE INVENTION
Error control coding (ECC) is a ubiquitous technique. Many electronic media suffer occasional losses or corruption of data; ECC is any data representation which is robust against such loss or corruption. Most ECC techniques are designed for protection of transmitted data, but the focus here is on protection of stored data.
Typically, coding is to protect against what is called physical errors. Examples are noise on a telephone line, defects on a disk or tape, or even the failure of an entire hard disk (as is protected by a RAID, a Redundant Array of Independent Disks). Protecting the data in such cases is done, first, by dividing it into blocks. Each block is coded independently. Since a code cannot protect against loss of many bits (or generally, symbols) in any block, the system must be designed so that bits in a block are more or less independent. (For example in the RAID, each bit of a coded block is stored on a separate disk. It is relatively unlikely that two disks will fail at once.)
Backing up computer files is typically done by making a duplicate copy of all the data. This means that the backup copy requires just as much space as the original, and to keep costs reasonable, backups are generally consigned to tape or another capacious but slow medium. Backups are so slow and inconvenient that they are often created and managed by a separate organization, and are often not worth using, except in case of catastrophe. Backups are extremely voluminous and time-consuming to make and unwieldy to organize.
In case of logical faults, it is relatively likely that all symbols in a single logical file will be corrupted or erased at the same time, in contradistinction to the physical fault model, discussed above. Computer viruses are one source of logical faults. The unit corrupted by a computer virus is not a disk track or similar physical unit, but a single computer file (usually an executable file). Another example is a user's own inadvertent erasure, change, or over-writing of a valuable computer file.
It is an object of the present invention to overcome the problems of known backup schemes and systems.
It is another object of the present invention to provide a scheme which allows to quickly and efficiently restore data in case of logical faults.
It is a further object of the present invention to provide a scheme which can be used for anti-virus protection.
SUMMARY OF THE INVENTION
The present invention concerns a method for protecting data against logical faults by means of error correction codes allowing to create vastly smaller backups than conventional systems. Under certain circumstances, it may also be employed against physical faults.
The present invention, in order to protect against corruption of logical units data (‘files’), employs coded blocks consisting of cross-sections across a number of files, rather than bits from within a single file.
For maximal efficiency (best mode), the data blocks should be cross-sections across all files, in which case the code blocks may be of variable length rather than the usual fixed length.
As with most ECC, limited corruption of the coded data results in no loss of original data, while corruption beyond this point may result in substantial loss.
There is a clear distinction between the present invention and most coding applications to transmission or even storage (including RAID in the latter category). Since the present invention provides for a separate integrity component to stand alongside an independent data system, the codes used must be systematic. To explain, in most applications the data are accessed only through the coded channel. For example, any RAID disk read/write must go through the RAID protocol. In this case the code need not be systematic, which is to say that the data bits need not be present ‘in the clear’ within the coded data. The data bits and parity bits may be all intertwined, and only get sorted out by the coding and decoding procedures.
According to the present invention, a systematic code is used which acts as an independent component to protect the data integrity of an ‘original’ system, and the data must be ‘in the clear’ for the original system. The systematic code preserves the original data bits. Please note that, unlike the data bits, there is no constraint on the parity bits, which are used only by the coding component and not the original system. In other words, when using a systematic code, the codeword still includes the original bits and any system processing or reading the original bits does not need to know what kind of coding scheme is used. It can simply take and process the original bits included in the codeword.
One implementation of the present invention uses an erasure code rather than an error-correcting code. An erasure code can restore bits that have been lost, while an error-correcting code can restore bits that have been lost or corrupted. Technically the difference between them is that the erasure code is ‘told’ which bits are bad, while the error correcting code is not given this information; the lesser task demanded of the erasure code allows it to operate more efficiently.
Another implementation may make use of an error-correcting code.
In the present applications, the ‘bad’ symbols are those in ‘bad’ files, which can be identified by a verification system to be described.
The present invention, and modifications thereof, allow realization of systems which efficiently protect against loss of data.
It is an advantage of the inventive scheme that it is fast and reliable. The storage space needed is much smaller than in case of conventional systems.
It is another advantage of the present invention that the size of the backup is linked to the size of the anticipated damage, and is completely independent of the total size of the files being protected.
It is a further advantage of the present invention that it provides protection against limited damage much more economically by employing an error-correcting code.
The invention also allows rapid update of the redundant coding data comprising the backup as new files are added or deleted. The restore operation is reasonably rapid, so recovery of damaged data is done quickly. The speed and compactness of the present invention allows backups to be done locally and constantly if needed so that the backup is always up to date. This allows putting the entire backup and restore mechanism, according to the present invention, under user control.
The present invention is well suited for use in portable computer systems, such as palm tops and notebooks.
REFERENCES:
patent: 4477903 (1984-10-01), Immink et al.
patent: 4495623 (1985-01-01), George et al.
patent: 4654819 (1987-03-01), Stiffler et al.
patent: 4995041 (1991-02-01), Hetherington et al.
patent: 5289540 (1994-02-01), Jones
patent: 5331646 (1994-07-01), Krueger et al.
patent: 5369641 (1994-11-01), Dodt et al.
patent: 5379417 (1995-01-01), Lui et al.
patent: 5428630 (1995-06-01), Weng et al.
patent: 5448668 (1995-09-01), Perelson et al.
patent: 5513192 (1996-04-01), Janku et al.
patent: 5778395 (1998-07-01), Whiting et al.
patent: 03271847 (1991-12-01), None
Cady Albert De
Chase Shelly A.
International Business Machines - Corporation
Ohlandt Greeley Ruggiero & Perle L.L.P.
LandOfFree
Coding scheme for file backup and systems based thereon does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Coding scheme for file backup and systems based thereon, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coding scheme for file backup and systems based thereon will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2531223