Patent ID: 8495035

Claim:
A method for data integrity protection, comprising: arranging data in a plurality of data blocks, the data being so arranged for storage in a storage medium comprising non-volatile memory; computing a respective block signature over each of the data blocks, thereby generating multiple block signatures; storing the data blocks and the block signatures in an integrity hierarchy in the storage medium, the integrity hierarchy comprising multiple levels of signature blocks containing signatures computed over lower levels in the integrity hierarchy, culminating in a top-level block containing a top-level signature computed over all of the integrity hierarchy; making a modification in the data stored in a given data block within the integrity hierarchy; responsively to the modification, recomputing the respective block signature of the given data block; and storing the recomputed block signature in a modified block signature list stored in the top-level block, the modified block signature list comprising a list of block signatures that have been modified since a hierarchy synchronization; upon receiving a request to read a data item from the given data block after making the modification: computing a new block signature of the specified block; and verifying the new block signature against the recomputed block signature in the modified block signature list stored in the top-level block; recomputing the signatures over all of the levels in the integrity hierarchy after storing the recomputed block signature in the modified block signature list; after recomputing the signatures over all of the levels, removing the recomputed block signatures from the modified block signature list stored in the top-level block.