Methods and systems for data recovery

• US 8,010,502 B2
• Filed: 04/11/2008
• Issued: 08/30/2011
• Est. Priority Date: 04/13/2007
• Status: Active Grant

• Current Assignee: Peraton, Inc.
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Jessee, Lucas John
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): YOUNG, KEVIN L.
• Application Number:
  US12/101,576
• Publication Number:
  US 20080256139A1
• Time in Patent Office: 1,236 Days
• Field of Search: None
• US Class Current: 707/674
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata

Abstract

To recover deleted files in a data store, candidate blocks of the data store may be identified and, for each of the candidate blocks, a probability that the candidate block contains a directory entry may be determined. Directory entry metadata for candidate blocks that have a determined probability that is greater than a predetermined probability threshold may then be extracted.

Claims

1. A method for recovering deleted files in a data store comprising a FAT file system, comprising:

identifying candidate blocks of a data store, each candidate block comprising a plurality of portions;

determining for each of the candidate blocks a first probability that the candidate block contains a directory entry based upon one of the plurality of portions;

determining for each of the candidate blocks a second probability that the candidate block contains a directory entry based upon another one of the plurality of portions;

combining the first probability and second probability to form a combined probability;

wherein the first and second probabilities are based on the portion being part of a valid directory entry;

extracting directory entry metadata for candidate blocks that have a combined probability that is greater than a predetermined probability threshold; and

recovering the content of a deleted file using the extracted directory entry metadata.

2. The method of claim 1, wherein the candidate blocks comprise at least one of blocks located in unallocated clusters or blocks located in unused portions of allocated clusters.

3. The method of claim 1, one of the plurality of portions comprises a reserved byte and the another one of the plurality of portions comprises an attribute byte;

and wherein determining the first and second probabilities comprises testing the reserved byte in the candidate block and testing the attribute byte in the candidate block.

4. The method of claim 1, wherein one of the plurality of portions comprises temporal data;

and wherein determining one of the first and second probabilities comprises testing the temporal data in the candidate block.

5. The method of claim 1, wherein one of the plurality of portions comprises a file name;

and wherein determining one of the first and second probabilities comprises testing the file name in the candidate block.

6. The method of claim 1, wherein determining one of the first and second probabilities comprises testing for contiguous groups of candidate blocks that have an initial probability that is greater than a predetermined threshold.

7. The method of claim 1, wherein determining one of the first and second probabilities comprises:

assigning initial probabilities for blocks in a cluster by testing the plurality of portions comprising at least a reserved byte, an attribute byte, temporal data, and a file name; and

determining probabilities that are increased from the initial probabilities for contiguous candidate blocks having initial probabilities greater than a predetermined initial probability threshold.

8. The method of claim 1, wherein determining the first and second probabilities comprises:

assigning initial probabilities for blocks in a cluster by testing for each block at least two of the plurality of portions comprising a reserved byte, an attribute byte, temporal data, and a file name; and

determining probabilities that are increased from the initial probabilities for contiguous candidate blocks having initial probabilities greater than a predetermined initial probability threshold.

9. The method of claim 1, wherein determining the first and second probabilities comprises:

assigning initial probabilities for blocks in a cluster by testing for each block at least three of the plurality of portions comprising a reserved byte, an attribute byte, temporal data, and a file name; and

determining probabilities that are increased from the initial probabilities for contiguous candidate blocks having initial probabilities greater than a predetermined initial probability threshold.

10. The method of claim 1, further comprising recovering the content of a deleted file using file information in the extracted metadata.

11. The method of claim 1, further comprising constructing a timeline using temporal information in the extracted metadata.

12. A system for recovering deleted files in a data store comprising a FAT file system, comprising:

a processor;

a candidate block identification module operating on said processor for identifying candidate blocks of a data store, each candidate block comprising a plurality of portions;

a determination module operating on said processor for determining for each of the candidate blocks;

a first probability that the candidate block contains a directory entry based upon one of the plurality of portions,

a second probability that the candidate block contains a directory entry based upon another one of the plurality of portions, and

a combined probability formed by combining the first probability and second probability;

wherein the first and second probabilities are based on the portion being part of a valid directory entry;

an extraction module operating on said processor for extracting directory entry metadata for candidate blocks that have a combined probability that is greater than a predetermined probability threshold; and

recovering the content of a deleted file using the extracted directory entry metadata.

13. The system of claim 12, wherein the candidate blocks comprise at least one of blocks located in unallocated clusters or blocks located in unused portions of allocated clusters.

14. The system of claim 12, wherein one of the plurality of portions comprises a reserved byte and the another one of the plurality of portions comprises an attribute block;

and wherein the determination module is configured to determine the first and second probabilities by testing the reserved byte in the candidate block and testing the attribute byte in the candidate block.

15. The system of claim 12, wherein one of the plurality of portions comprises temporal data;

and wherein the determination module is configured to determine one of the first and second probabilities by the testing temporal data in the candidate block.

16. The system of claim 12, wherein one of the plurality of portions comprises a file name;

and wherein the determination module is configured to determine one of the first and second probabilities by testing the file name in the candidate block.

17. The system of claim 12, wherein the determination module is configured to determine one of the first and second probabilities by testing for contiguous blocks that have an initial probability that is greater than a predetermined threshold.

18. The system of claim 12, wherein the determination module is configured to determine one of the first and second probabilities by:

assigning initial probabilities for blocks in a cluster by testing the plurality of portions comprising a reserved byte, testing an attribute byte, testing temporal data, and a file name; and

determining probabilities that are increased from the initial probabilities for contiguous candidate blocks having initial probabilities greater than a predetermined initial probability threshold.

19. The system of claim 12, wherein the determination module is configured to determine the one of the first and second probabilities by:

assigning initial probabilities for blocks in a cluster by testing for each block at least two of the plurality of portions comprising a reserved byte, an attribute byte, temporal data, and a file name; and

determining probabilities that are increased from the initial probabilities for contiguous candidate blocks having initial probabilities greater than a predetermined initial probability threshold.

20. The system of claim 12, wherein the determination module is configured to determine one of the first and second probabilities by:

assigning initial probabilities for blocks in a cluster by testing for each block at least three of the plurality of portions comprising a reserved byte, an attribute byte, temporal data, and a file name; and

determining probabilities that are increased from the initial probabilities for contiguous candidate blocks having initial probabilities greater than a predetermined initial probability threshold.

21. The system of claim 12, further comprising a recovery module for recovering the content of a deleted file using file information in the extracted metadata.

22. The system of claim 12, further comprising a timeline module for constructing a timeline using temporal information in the extracted metadata.

23. A method for determining whether candidate blocks of a data store are likely to contain a directory entry comprising a FAT file system, comprising:

identifying candidate blocks of a data store, each candidate block comprising a plurality of portions;

assigning initial probabilities to candidate blocks by determining first and second probabilities based upon different ones of the plurality of portions to determine whether the different ones of the plurality of portions meets the criteria associated with a directory entry;

assigning a combined probability by combing the first and second probabilities;

assigning a final probability that is higher than the combined probability to each candidate block in a contiguous group of candidate blocks that each have high combined probabilities;

wherein the first and second probabilities are based on the portion being part of a valid directory entry;

reporting candidate blocks with a final probability greater than a predetermined threshold as a list of blocks that are likely to contain a directory entry; and

recovering the content of a deleted file using the reported candidate blocks.

24. The method of claim 23, wherein the identified candidate blocks comprise at least one of blocks located in unallocated clusters or blocks located in unused portions of allocated clusters.

25. The method of claim 23, wherein one of the plurality of portions comprises a reserved byte and an attribute byte;

and wherein assigning the initial probability comprises testing the reserved byte in the candidate block and testing the attribute byte in the candidate block.

26. The method of claim 23, wherein one of the plurality of portions comprises temporal data;

and wherein assigning the initial probability comprises testing the temporal data in the candidate block.

27. The method of claim 23, wherein one of the plurality of portions comprises a file name;

and wherein assigning the initial probability comprises testing the file name in the candidate block.

28. The method of claim 23, wherein assigning the initial probability comprises testing a reserved byte, testing an attribute byte, testing temporal data, and testing a file name.

29. The method of claim 23, further comprising extracting directory entry metadata for candidate blocks on the list.

30. The method of claim 29, further comprising recovering the content of a deleted file using file information in the extracted metadata.

31. The method of claim 29, further comprising constructing a timeline using temporal information in the extracted metadata.

32. A system for recovering deleted files in a data store comprising a FAT file system, comprising:

a candidate block identification hardware module for identifying candidate blocks of a data store, each candidate block comprising a plurality of portions;

a determination hardware module for determining for each of the candidate blocks first and second probabilities that the candidate block contains a directory entry, based upon different ones of the plurality of portions and for determining a combined probability based on the combination of the first and second probabilities;

wherein the first and second probabilities are based on the portion being part of a valid directory entry;

an extraction hardware module for extracting directory entry metadata for candidate blocks that have a combined probability that is greater than a predetermined probability threshold; and

recovering the content of a deleted file using the extracted directory entry metadata.

33. The system of claim 32, wherein the candidate blocks comprise at least one of blocks located in unallocated clusters or blocks located in unused portions of allocated clusters.

34. The system of claim 32, wherein the plurality of portions comprises a reserved byte and an attribute byte;

and wherein the determination hardware module is configured to determine the first and second probabilities by testing the reserved byte in the candidate block and testing the attribute byte in the candidate block.

35. The system of claim 32, wherein one of the plurality of portions comprises temporal data;

and wherein the determination hardware module is configured to determine one of the first and second probabilities by the testing temporal data in the candidate block.

36. The system of claim 32, wherein one of the plurality of portions comprises a file name;

and wherein the determination hardware module is configured to determine one of the first and second probabilities by testing the file name in the candidate block.

37. The system of claim 32, wherein the determination hardware module is configured to determine one of the first and second probabilities by testing for contiguous blocks that have an initial probability that is greater than a predetermined threshold.

38. The system of claim 32, wherein the determination hardware module is configured to determine one of the first and second probabilities by:

assigning initial probabilities for blocks in a cluster by testing the plurality of portions comprising a reserved byte, testing an attribute byte, testing temporal data, and a file name; and

determining probabilities that are increased from the initial probabilities for contiguous candidate blocks having initial probabilities greater than a predetermined initial probability threshold.

39. The system of claim 32, wherein the determination hardware module is configured to determine the first and second probabilities by:

assigning initial probabilities for blocks in a cluster by testing for each block at least two of the plurality of portions comprising a reserved byte, an attribute byte, temporal data, and a file name; and

determining probabilities that are increased from the initial probabilities for contiguous candidate blocks having initial probabilities greater than a predetermined initial probability threshold.

40. The system of claim 32, wherein the determination hardware module is configured to determine the first and second probabilities by:

assigning initial probabilities for blocks in a cluster by testing for each block at least three of the plurality of portions comprising a reserved byte, an attribute byte, temporal data, and a file name; and

determining probabilities that are increased from the initial probabilities for contiguous candidate blocks having initial probabilities greater than a predetermined initial probability threshold.

41. The system of claim 32, further comprising a recovery hardware module for recovering the content of a deleted file using file information in the extracted metadata.

42. The system of claim 32, further comprising a timeline hardware module for constructing a timeline using temporal information in the extracted metadata.