Identifying a compromised encoded data slice

• US 9,063,968 B2
• Filed: 07/16/2013
• Issued: 06/23/2015
• Est. Priority Date: 08/02/2010
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Resch, Jason K.
• Primary Examiner(s): Perungavoor, Venkat
• Application Number:
  US13/943,520
• Publication Number:
  US 20130304711A1
• Time in Patent Office: 707 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 11/3485 for I/O devices
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 21/335 for accessing specific resources, e.g. using Kerberos tickets
• 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/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: H04L 1/0045 Arrangements at the receiver end
• CPC Class Codes: H04L 1/208 involving signal re-encoding
• CPC Class Codes: H04L 63/04 for providing a confidential data exchange among entities communicating through data packet networks
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/12 Applying verification of the received information cryptographic mechanisms or cryptographic arrangements for data integrity or data verification H04L9/32
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A method begins by processing module in response to a read command, issuing at least a read threshold number of read requests regarding a set of encoded data slices and receiving at least the read threshold number of encoded data slices. The method continues where the processing module selects a unique combination of encoded data slices and decodes the unique combination to produce a recovered data segment. The method continues where the processing module verifies an integrity value for the recovered data segment and indicates whether the unique combination is valid. The method continues where the processing module selects other combinations producing more recovered data segments for further validity verification. The method continues where the processing module utilizes a verified recovered data segment as a response to the read command and identifies a compromised encoded data slice.

Claims

1. A computer-implemented method for execution by one or more processing modules of a computing device, the method comprises:

in response to a read command, issuing at least a read threshold number of read requests regarding a set of encoded data slices, wherein a data segment is dispersed storage error encoded to produce the set of encoded data slices, wherein the data segment has a known integrity value, wherein a decode threshold number of encoded data slices of the set of encoded data slices is needed to recover the data segment, and wherein the read threshold number is greater than the decode threshold number;

receiving the at least the read threshold number of encoded data slices;

entering a loop that includes;

selecting a unique combination of encoded data slices from the set of the at least the read threshold number of encoded data slices, wherein the unique combination includes the decode threshold number of encoded data slices;

disperse storage error decoding the unique combination of encoded data slices to produce a recovered data segment;

generating an integrity value for the recovered data segment;

verifying the integrity value with the known integrity value;

when the integrity value is verified, indicating that the unique combination of encoded data slices is valid;

when the integrity value is not verified, indicating that the unique combination of encoded data slices is not valid;

repeating the loop when less than a desired number of unique combinations of encoded data slices have been processed; and

exiting the loop when the desired number of unique combinations of encoded data slices have been processed;

utilizing one of the recovered data segments corresponding to one of the valid unique combinations of encoded data slice as a response to the read command; and

identifying a compromised encoded data slice based on the unique combinations of encoded data slices that are not valid.

2. The computer-implemented method of claim 1 further comprises:

from an iteration of the loop to a next iteration of the loop;

selecting the unique combination of encoded data slices for the next iteration by changing one encoded data slice from the unique combination of encoded data slices for the iteration; and

when the integrity value is verified for the unique combination of encoded data slices for the iteration and when the integrity value is not verified for the unique combination of encoded data slices for the next iteration, identifying the one changed encoded data slice as being the compromised encoded data slice.

3. The computer-implemented method of claim 1 further comprises:

commencing a rebuilding process to rebuild the compromised encoded data slice.

4. The computer-implemented method of claim 1, wherein the generating the integrity value comprises one of:

performing a deterministic function on the recovered data segment; and

compiling integrity values of the encoded data slices of the unique combination of encoded data slices.

5. The computer-implemented method of claim 1, wherein the utilizing the one of the recovered data segments comprises one of:

utilizing the recovered data segment corresponding to the unique combination of encoded data slices that is a first unique combination to be found valid;

utilizing the recovered data segment corresponding to the unique combination of encoded data slices that is a last unique combination to be found valid; and

arbitrarily selecting the one of the recovered data segments.

6. The computer-implemented method of claim 1, wherein the desired number of unique combinations comprises one of:

all possible unique combinations of the encoded data slices from the set of the at least the read threshold number of encoded data slices;

a number corresponding to changing the unique combinations of one encoded data slice per iteration of the loop; and

a calculated number based on the read threshold number and the decode threshold number.

7. The computer-implemented method of claim 1 further comprises:

performing, by a first processing module of the one or more processing modules, the loop until a first occurrence of the integrity value being verified; and

when the first occurrence of the integrity value being verified;

shifting performance of the loop to a second processing module of the one or more processing modules;

utilizing, by the first processing module, the one of the recovered data segments corresponding to the first occurrence of the integrity value being verified as the response to the read command; and

identifying, by at least one of the first and second processing modules, the compromised encoded data slice based on the unique combinations of encoded data slices that are not valid.

8. A dispersed storage (DS) processing module comprises:

an interface;

a memory;

a recover slices module, operably coupled to the interface and the memory, wherein the recover slices module, when operable within a computing device, causes the computing device to;

in response to a read command, issue at least a read threshold number of read requests regarding a set of encoded data slices, wherein a data segment is dispersed storage error encoded to produce the set of encoded data slices, wherein the data segment has a known integrity value, wherein a decode threshold number of encoded data slices of the set of encoded data slices is needed to recover the data segment, and wherein the read threshold number is greater than the decode threshold number; and

receive the at least the read threshold number of encoded data slices;

a slice validity module, operably coupled to the interface and the memory, wherein the slice validity module, when operable within the computing device, causes the computing device to;

enter a loop causing the computing device to;

select a unique combination of encoded data slices from the set of the at least the read threshold number of encoded data slices, wherein the unique combination includes the decode threshold number of encoded data slices;

disperse storage error decode the unique combination of encoded data slices to produce a recovered data segment;

generate an integrity value for the recovered data segment;

verify the integrity value with the known integrity value;

when the integrity value is verified, indicate that the unique combination of encoded data slices is valid;

when the integrity value is not verified, indicate that the unique combination of encoded data slices is not valid;

repeat the loop when less than a desired number of unique combinations of encoded data slices have been processed; and

exit the loop when the desired number of unique combinations of encoded data slices have been processed; and

a response module, operably coupled to the interface and the memory, wherein the response module, when operable within the computing device, causes the computing device to;

utilize one of the recovered data segments corresponding to one of the valid unique combinations of encoded data slice as a response to the read command; and

identify a compromised encoded data slice based on the unique combinations of encoded data slices that are not valid.

9. The DS processing module of claim 8 further comprises:

from an iteration of the loop to a next iteration of the loop;

the slice validity module further functions to select the unique combination of encoded data slices for the next iteration by changing one encoded data slice from the unique combination of encoded data slices for the iteration; and

when the integrity value is verified for the unique combination of encoded data slices for the iteration and when the integrity value is not verified for the unique combination of encoded data slices for the next iteration, the response module further functions to identify the one changed encoded data slice as being the compromised encoded data slice.

10. The DS processing module of claim 8 further comprises:

the response module further functions to commence a rebuilding process to rebuild the compromised encoded data slice.

11. The DS processing module of claim 8, wherein the slice validity module functions to generate the integrity value by one of:

performing a deterministic function on the recovered data segment; and

compiling integrity values of the encoded data slices of the unique combination of encoded data slices.

12. The DS processing module of claim 8, wherein the response module functions to utilize the one of the recovered data segments by one of:

utilizing the recovered data segment corresponding to the unique combination of encoded data slices that is a first unique combination to be found valid;

utilizing the recovered data segment corresponding to the unique combination of encoded data slices that is a last unique combination to be found valid; and

arbitrarily selecting the one of the recovered data segments.

13. The DS processing module of claim 8, wherein the desired number of unique combinations comprises one of:

all possible unique combinations of the encoded data slices from the set of the at least the read threshold number of encoded data slices;

a number corresponding to changing the unique combinations of one encoded data slice per iteration of the loop; and

a calculated number based on the read threshold number and the decode threshold number.

14. The DS processing module of claim 8 further comprises:

the slice validity module further functions to perform the loop until a first occurrence of the integrity value being verified; and

when the first occurrence of the integrity value being verified;

the slice validity module further functions to shift performance of the loop to a second slice validity module;

the response module further functions to utilize the one of the recovered data segments corresponding to the first occurrence of the integrity value being verified as the response to the read command; and

at least one of the slice validity module and the second slice validity module, when operable within the computing device, causes the computing device to identify the compromised encoded data slice based on the unique combinations of encoded data slices that are not valid.