The search for deleted files: FAT file system
In this article I would like to tell you about the algorithms that we used when creating programs for data recovery Hetman Partition Recovery.
But first, let's say that file recovery is even possible, because they are stored in the form of blocks of information recorded on the hard disk sectors. The sectors can be placed sequentially, one after the other and to be scattered randomly across the disk surface. The location of the sectors depends on what blocks were free at the time of saving the file to disk. If the system is not found on disk continuous free block of sectors of sufficient size in order to save the file as a continuous data sequence, the system will fragment the file by writing its parts in loose blocks.
By the way, in case the file is fragmented and the file system is corrupted or destroyed (e.g. after formatting the disk), data recovery tools use algorithms of the search by signature that reads all data from the hard disk's surface in order to detect known file types.
And here lies the main difficulty. Algorithms signature-based search in their work depend on the structures of the headers of the files, analyzing which it is possible to determine the file size. Having information about the location of the title and knowing the exact file size, the program calculates a sector on the disk, which, in their opinion, contain the data file. As you know, work properly, these algorithms will only when entire file is stored in a single continuous fragment. If the file was saved in the form of a set of disparate fragments to restore the missing entry in the file system would be extremely difficult, almost impossible.
But for such cases there are special techniques used by intelligence agencies and forensic work, allowing you to recover the contents of some file types is literally in pieces. Their work is similar to the collection of a puzzle: different pieces of data are being tried in different places in the file, then using heuristic algorithms, the file is reviewed for integrity. Needless to say that such algorithms are extremely resource-intensive, but it is so slow and unreliable that to use them outside of forensic laboratories simply unprofitable.
So, in order to navigate in the recorded information, Windows creates an entry in the file system with an indication of which sectors on the disk a specific file.
At the moment when the user deletes a file, Windows does not erase or overwrite the contents of sectors on the disk. In the case of removal of a file from the SSD memory can be enabled TRIM. The contents of the record on file in the filesystem is also not removed but undergoes modifications, the system marks the record as belonging to a remote file. Now Windows can save that space for some other file. But until that happens, you can try to recover the contents of a remote file. Tools for recovering deleted files scan file system in the search of records marked as deleted. After analyzing these records, it becomes possible to know the exact address of sectors on the disk, which was recorded contents of the original file. After a quick check – do not belong to these sectors with some other file, program reads the sectors and store them in a new file. What happens if the file system had no record that points to a remote file? In this case, the simplest tools do not work.
Next, I will describe an algorithm to find and restore deleted files from a FAT partition which we used when developing our programmes, best of all, this algorithm is described in the book “Forensic analysis of file systems” author Brian Carrie.
Windows system partition contains one or more tables, wherein each table entry describes one partition. In the data record usually indicates the starting sector of the partition, ending sector of the partition (or length) and the partition type.
To search the file system our program is based on the assumption that each topic was file system. Many file systems start with a data structure with constant signature. For example, the FAT file system contains the values 0x55 and 0хАА in bytes 510 and 511 of the first sector. Recovery program looking for a signature and defines them possible beginning of a section. When signatures are detected often performed additional verification with the ranges of values allowed in some fields of the data structure. For example, one of the fields of the FAT file system determines the number of sectors in a cluster; the field value is a power of 2 (for example, 1, 2, 4, 8, 16, 32, 64 or 128). Any other value indicates that the sector is not part of the boot sector the FAT file system, although he ends with a signature 0х55АА.
The basic concept of the FAT file system is that each file and directory is allocated a data structure called a directory entry. This structure contains the file name, its size, the starting address of the file content and other metadata. The contents of files and directories is stored in blocks of data called clusters. If the file or directory is allocated more than one cluster, the remaining clusters can be found by using a data structure called FAT. The structure of FAT is used as to identify the next cluster in the file, and to determine the selection state of the clusters.
The FAT file system is divided into three physical regions. The first area is called reserved, it stores the data of the categories of the file system. In FAT12 and FAT16 placeholder is only 1 sector, but formally its size is defined in the boot sector. The second area of FAT — contains the primary and backup FAT structures. It starts in the sector following the reserved area, and its size is determined by the number and size of the FAT structures. The third area is the data area contains clusters allocated for file storage and directory content.
One of the first tasks when analyzing a FAT file system is the identification of three physical regions. The reserved area starts in sector 0 of the file system, and its size is specified in the boot sector. In FAT 12/16 it usually takes only 1 sector, but FAT32 is reserved for her several sectors.
The FAT area contains one or more FAT structures, and begins in the sector following the reserved area. Its size is calculated by multiplying the number of FAT structures by the size of a structure; both values are stored in the boot sector (the reserved area).
When you delete a file in Windows, its directory entry is marked as unused, and a recording cluster in the FAT are set to zero. The beginning and the file size is known, but information about the other clusters the file is missing.
You can try to recover the contents of a file, reading data from known initial cluster. As for the other clusters, the program of recovery there are two methods: read the volume data corresponding to the size of the file, not paying attention to the status of the selection, or to read data only from free clusters.
The second method often leads to success because it restores some fragmented files. Figure 5 explains what is happening:
In the scenario in Fig. 5 (A) a file occupies four adjacent cluster. In this case, in both cases correctly recover the clusters, 56-59. In Fig. 5 (C) the file was divided into three fragments, and clusters between fragments (57 and 60) were allocated to another file during recovery. In this scenario, the first method recovers clusters 56-59 and erroneously includes the contents of the cluster 57. The second method recovers correctly the sectors 56, 58,59, and 61. In Fig. 5 (C) shows a scenario in which the file is allocated the same piece as in Fig. 5 (B), but clusters between fragments has not been allocated to other files at the time of recovery. In this scenario, both methods incorrectly restore the cluster 56-59, as was done in the previous example. In the file recovery process, there are other scenarios, but they are part of a file is erased, and no one method will not be able to recover the data. Thus, method 2 (state-based clustering) is able to recover deleted files more often than method 1.
In conclusion, I will say that NTFS is much more complicated than FAT, search for deleted files in it, the subject of a separate article.
Article based on information from habrahabr.ru
But first, let's say that file recovery is even possible, because they are stored in the form of blocks of information recorded on the hard disk sectors. The sectors can be placed sequentially, one after the other and to be scattered randomly across the disk surface. The location of the sectors depends on what blocks were free at the time of saving the file to disk. If the system is not found on disk continuous free block of sectors of sufficient size in order to save the file as a continuous data sequence, the system will fragment the file by writing its parts in loose blocks.
By the way, in case the file is fragmented and the file system is corrupted or destroyed (e.g. after formatting the disk), data recovery tools use algorithms of the search by signature that reads all data from the hard disk's surface in order to detect known file types.
And here lies the main difficulty. Algorithms signature-based search in their work depend on the structures of the headers of the files, analyzing which it is possible to determine the file size. Having information about the location of the title and knowing the exact file size, the program calculates a sector on the disk, which, in their opinion, contain the data file. As you know, work properly, these algorithms will only when entire file is stored in a single continuous fragment. If the file was saved in the form of a set of disparate fragments to restore the missing entry in the file system would be extremely difficult, almost impossible.
But for such cases there are special techniques used by intelligence agencies and forensic work, allowing you to recover the contents of some file types is literally in pieces. Their work is similar to the collection of a puzzle: different pieces of data are being tried in different places in the file, then using heuristic algorithms, the file is reviewed for integrity. Needless to say that such algorithms are extremely resource-intensive, but it is so slow and unreliable that to use them outside of forensic laboratories simply unprofitable.
So, in order to navigate in the recorded information, Windows creates an entry in the file system with an indication of which sectors on the disk a specific file.
At the moment when the user deletes a file, Windows does not erase or overwrite the contents of sectors on the disk. In the case of removal of a file from the SSD memory can be enabled TRIM. The contents of the record on file in the filesystem is also not removed but undergoes modifications, the system marks the record as belonging to a remote file. Now Windows can save that space for some other file. But until that happens, you can try to recover the contents of a remote file. Tools for recovering deleted files scan file system in the search of records marked as deleted. After analyzing these records, it becomes possible to know the exact address of sectors on the disk, which was recorded contents of the original file. After a quick check – do not belong to these sectors with some other file, program reads the sectors and store them in a new file. What happens if the file system had no record that points to a remote file? In this case, the simplest tools do not work.
Next, I will describe an algorithm to find and restore deleted files from a FAT partition which we used when developing our programmes, best of all, this algorithm is described in the book “Forensic analysis of file systems” author Brian Carrie.
Windows system partition contains one or more tables, wherein each table entry describes one partition. In the data record usually indicates the starting sector of the partition, ending sector of the partition (or length) and the partition type.
To search the file system our program is based on the assumption that each topic was file system. Many file systems start with a data structure with constant signature. For example, the FAT file system contains the values 0x55 and 0хАА in bytes 510 and 511 of the first sector. Recovery program looking for a signature and defines them possible beginning of a section. When signatures are detected often performed additional verification with the ranges of values allowed in some fields of the data structure. For example, one of the fields of the FAT file system determines the number of sectors in a cluster; the field value is a power of 2 (for example, 1, 2, 4, 8, 16, 32, 64 or 128). Any other value indicates that the sector is not part of the boot sector the FAT file system, although he ends with a signature 0х55АА.
How to find file in FAT table
The basic concept of the FAT file system is that each file and directory is allocated a data structure called a directory entry. This structure contains the file name, its size, the starting address of the file content and other metadata. The contents of files and directories is stored in blocks of data called clusters. If the file or directory is allocated more than one cluster, the remaining clusters can be found by using a data structure called FAT. The structure of FAT is used as to identify the next cluster in the file, and to determine the selection state of the clusters.
The FAT file system is divided into three physical regions. The first area is called reserved, it stores the data of the categories of the file system. In FAT12 and FAT16 placeholder is only 1 sector, but formally its size is defined in the boot sector. The second area of FAT — contains the primary and backup FAT structures. It starts in the sector following the reserved area, and its size is determined by the number and size of the FAT structures. The third area is the data area contains clusters allocated for file storage and directory content.
One of the first tasks when analyzing a FAT file system is the identification of three physical regions. The reserved area starts in sector 0 of the file system, and its size is specified in the boot sector. In FAT 12/16 it usually takes only 1 sector, but FAT32 is reserved for her several sectors.
The FAT area contains one or more FAT structures, and begins in the sector following the reserved area. Its size is calculated by multiplying the number of FAT structures by the size of a structure; both values are stored in the boot sector (the reserved area).
file Recovery
When you delete a file in Windows, its directory entry is marked as unused, and a recording cluster in the FAT are set to zero. The beginning and the file size is known, but information about the other clusters the file is missing.
You can try to recover the contents of a file, reading data from known initial cluster. As for the other clusters, the program of recovery there are two methods: read the volume data corresponding to the size of the file, not paying attention to the status of the selection, or to read data only from free clusters.
The second method often leads to success because it restores some fragmented files. Figure 5 explains what is happening:
In the scenario in Fig. 5 (A) a file occupies four adjacent cluster. In this case, in both cases correctly recover the clusters, 56-59. In Fig. 5 (C) the file was divided into three fragments, and clusters between fragments (57 and 60) were allocated to another file during recovery. In this scenario, the first method recovers clusters 56-59 and erroneously includes the contents of the cluster 57. The second method recovers correctly the sectors 56, 58,59, and 61. In Fig. 5 (C) shows a scenario in which the file is allocated the same piece as in Fig. 5 (B), but clusters between fragments has not been allocated to other files at the time of recovery. In this scenario, both methods incorrectly restore the cluster 56-59, as was done in the previous example. In the file recovery process, there are other scenarios, but they are part of a file is erased, and no one method will not be able to recover the data. Thus, method 2 (state-based clustering) is able to recover deleted files more often than method 1.
In conclusion, I will say that NTFS is much more complicated than FAT, search for deleted files in it, the subject of a separate article.
Комментарии
Отправить комментарий