_Written During August 2022_ Published on May 09, 2024 --- ##### Abstract The user of a machine may occasionally delete a file unintentionally. Recovering this data in a quick and easy manner for this user may be essential when that file is required to perform some immediate task. FDRecovery provides a data recovery solution for users who have unintentionally deleted files in the ext2 file system through utilizing existing metadata structures and file system features. When files are deleted in the ext2 file system, the data blocks and inode associated with the file are marked as free. Fortunately though, the block pointers in that inode are still maintained. Using this feature, we can follow the pointers in order to recover the file’s data. ##### Introduction When a file is deleted by some process on a storage device formatted with the ext2 file system, the file’s data are not altered in any way. The data still remain on the device in the same location as they previously were. The pointers to those data blocks are also maintained upon file deletion. Although this makes file recovery relatively simple, the location of these pointers must be known in order to locate them. This information is lost though when the file is deleted. This behavior poses a threat to the implementation of an efficient, time-sensitive, file-level, automated data recovery tool. Many tools [1, 2, 3] have been implemented which attempt to work around this issue by searching through all of the data on the storage device and recognising specific structures associated with specific file formats in order to recover those recognized files. This process is known as data carving [8] and the goal with these tools is typically to recover all files on a storage device. Although these tools are very comprehensive, they have certain limitations which make it desirable to explore other potential file recovery methods. First, these tools are only able to recover a limited number of file formats as they have to be able to recognize the structures associated with those formats. Secondly they are very slow and inefficient as in order to recover files (compared to metadata based solutions), they must search through the entire storage device. Third, recovering and identifying the desired files is not an option as there is no association between the file and its metadata, making it difficult for the tool to present options, and for the user to know which files contain the desired data. Our file recovery tool, FDRecovery, uses a metadata based file recovery solution. This provides a more efficient though less comprehensive file recovery tool which allows easier identification of the desired files, therefore it is also more applicable to the average user who may accidentally delete specific files which need to be recovered in a time-sensitive manner. ##### Background ###### Ext2 Structure Overview The ext2 file system splits the disk into various contiguous sections reserved for different purposes. The smallest of these sections is defined as a block. Blocks are contiguous sections of bytes where each byte within that block is part of the same data structure. Blocks are defined in terms of their size in bytes. This definition is expressed within the super block in ext2, where the block size (in bytes), as well as other file system metadata are contained. The super block resides within a reserved section on disk, specifically taking up the second 1024 bytes of the disk. The second of these sections are called block groups. They contain a certain number of blocks, each of which serves a specified purpose. The purpose, more generally, of block groups is to store data and metadata for files/directories contained within. They also contain redundant copies of more general file system metadata (super block copies and full group descriptor tables). The metadata blocks in these block groups are essential for knowing which data blocks are associated with files. These metadata blocks are known as super blocks, group descriptors, data bitmaps, inode bitmaps, and inodes. Inode and data bitmaps are blocks in which each bit is indicative of whether the associated inode/data block is free or in use. The group descriptors and inodes are stored in table structures, which are essentially contiguous arrays of inodes and group descriptors, with as many as can fit in each block within each block. Although all of these metadata structures are involved in the deletion and the subsequent recovery processes, our tool, FDRecovery, is primarily concerned with inodes, as they contain pointers to the blocks which contain the data for their associated file. [6] ###### Ext2 File Deletion When a file is deleted in the ext2 file system, the data for that file are still maintained on disk. In order to retrieve those data after the file associated with them is deleted, the most intuitive approach would be to simply go back to the metadata associated with that file and find the data they point to on disk. In the case of the ext2 file system, this method is applicable. There are some changes made to the metadata structures which make this more challenging yet possible despite these challenges. These changes, in no particular order, are to change the number of available blocks and inodes in the super block, as well as the same fields in the group descriptor associated with the group containing that file. The data and inode bitmap entries for the data blocks and inode associated with that deleted file are also marked as free. The directory entry for the file, which associates both file name and inode number with the directory containing the file, is also zeroed out. These metadata changes cause two issues in regards to recovering data for a deleted file. The first of these issues is that the file name and knowledge of the directory in which the file was contained are lost. The second and more essential of these issues is that the inode number associated with the deleted file is lost. Notably though, the block pointers for the associated data persists. [5] ##### FDRecovery design ###### Deleted Inode Identification The central problem with recovering a file in ext2 is finding the inode which contains the deleted file’s block pointers. FDRecovery presents all deleted files to the user as recovery options, therefore we must obtain a list of all deleted files. The features we will utilize to achieve this are that when a file is deleted, the entry for its inode in the inode bitmap is marked as free, and the deletion time in that inode is set. We can therefore search through all inodes marked as free in the bitmaps, and check if they have a deletion time field. If they do, then that inode is indeed associated with a deleted file. There are a few changes that can be made, based on the way in which inodes are allocated, that can make this process more efficient. Block groups contain a certain number of inodes. When inodes in a group are allocated to a file, they are allocated from the lowest inode number in that group first. This means that all allocated inodes in the bitmaps will be sequential. This allows for a great efficiency improvement because the point where there are no more allocated inodes in the bitmap, the first one with no deletion time marks the point at which there can be no more deleted files. The result of this is that typically only one free inode which is not associated with a delete will be checked for a deletion time. All inodes which are free and contain a deletion time make up the list of inodes associated with deleted files. ###### Recovery Process Once a list of inodes associated with deleted files is obtained using the above process, the user can select the files they wish to recover based on the inode number and deletion time. With the selected inode numbers, FDRecovery simply follows the block pointers located in the inode to obtain the file data. ##### Limitations There are a few limitations that this recovery method has due to filesystem features and implementation variations. First, the recovered file may be corrupted or the metadata may be lost occasionally. This is because when a file is deleted, it is marked as free and a result of this is that newly created files may overwrite the data associated with the deleted file. Another limitation to FDRecovery in the ext2 filesystem is that we found it to be the case that many modern linux distributions implement behavior which zeroes out the block pointers of deleted files in ext2 [7]. When a file is deleted under such a system, the file becomes unrecoverable using this method.  ##### References [1] CGSecurity. “Testdisk.” CGSecurity, CGSecurity, 27 Oct. 2019, https://www.cgsecurity.org/wiki/TestDisk. [2] CGSecurity. “Photorec.” CGSecurity, CGSecurity, 23 July 2019, https://www.cgsecurity.org/wiki/PhotoRec.  [3] Foremost, http://foremost.sourceforge.net/.  [4] Pal, Anandabrata & Memon, Nasir. (2009). The evolution of file carving. Signal Processing Magazine, IEEE. 26. 59 - 71. 10.1109/MSP.2008.931081 [5] “How Does File Deletion Work in Linux.” Slashroot.in, https://www.slashroot.in/how-does-file-deletion-work-linux.  [6] The Second Extended File System, https://www.nongnu.org/ext2-doc/ext2.html#s-inodes-count.  [7] Ext2 Help - Linux - level1techs Forums. https://forum.level1techs.com/t/ext2-help/114785.  [8] Pal, Anandabrata & Memon, Nasir. (2009). The evolution of file carving. Signal Processing Magazine, IEEE. 26. 59 - 71. 10.1109/MSP.2008.931081.