File Recovery FAT32 dominantin SD

Lab 4: File Recovery

Introduction

FAT has been around for nearly 50 years. Because of its simplicity, it is themost widely compatible fi le system. Although recent computers have

adopted newer fi le systems, FAT32 (and its variant, exFAT) is still dominantin SD cards and USB fl ash drives due to its compatibility.Have you ever accidentally deleted a fi le? Do you know that it could berecovered?In this lab, you will build a FAT32 fi le recovery tool called Need You to Undelete my FILE, ornyufilefor short.ObjectivesThrough this lab, you will:Learn the internals of the FAT32 fi le system.Learn how to access and recover fi les from araw disk.

Get a better understanding of key fi le system concepts.Be a better C programmer. Learn how to write code that manipulatesdata at the byte level and understand the alignment issue.OverviewIn this lab, you will work on the data stored in the FAT32 fi le system

directly, without the OS fi le system support. You will implement a tool thatrecovers a deleted file specifi ed by the user.For simplicity, you can assume thatthe deleted fi le is in the root directory.

Therefore, you don’t need to search subdirectories.command performs low-level copying of raw data.Therefore, you can use it to generate an arbitrary-size fi le full of zeros.program is invoked with option-l, it should list all valid

entries in the root directory with the following information:Filename. Similar to/bin/ls -p, if the entry is a directory, you shouldappend a / indicator.File size if the entry is a fi le (not a directory).Starting cluster if the entry is not an empty fi le.You should also print the total number of entries at the end. Your outputshould be in the following format:[root@... cs202]# ./nyufile fat32.disk -lHELLO.TXT (size = 14, starting cluster = 3)

/ (starting cluster = 4)EMPTY (size = 0)Total number of entries = 3Here are a few assumptions:Lab 4: File Recovery7/18You should not list entries marked as deleted.You don’t need to print the details inside subdirectories.For all milestones, there will be no long fi lename (LFN) entries. (If youhave accidentally created LFN entries when you test your program,don’t worry. You can just skip the LFN entries and print only the 8.3

fi lename entries.)Any fi le or directory, including the root directory, may span more than

one cluster.There may be empty fi les.Milestone 4: recover a small fileEMPTY (size = 0)Total number of entries = 3[root@... cs202]# mount fat32.disk /mnt/disk[root@... cs202]# ls -p /mnt/diskDIR/ EMPTY HELLO.TXT[root@... cs202]# cat /mnt/disk/HELLO.TXTHello, world.For all milestones, you only need to recover regular fi les (including emptfi les, but not directory fi les) in the root directory. When the fi le is

Lab 4: File Recovery9/18Here are a few assumptions specifi cally for Milestone 4:should printfilename: file not foundreplacefilenamewith the actual fi le name).Milestone 5: recover a large contiguously-allocated fileNow,代写File Recovery  FAT32   dominantin SD   you will recover a fi le that is larger than one cluster. Nevertheless, forMilestone 5, you can assume that such a fi le is allocated contiguously. Youcan continue toassume that at most one deleted directory entry matchesthe given fi lename. If no such entry exists, your program should printfilename: file not found(replacefilenamewith the actual fi le name).Milestone 6: detect ambiguous file recovery requestsIn Milestones 4 and 5, you assumed that at most one deleted directory

entry matches the given fi lename. However, multiple fi les whose names

differ only in the fi rst character would end up having the same name when

deleted. Therefore, you may encounter more than one deleted directoryentry matching the given fi lename. When that happens, your programshould printfilename: multiple candidates found.If no such fi le matches the given SHA-1 hash, your program should printfilename: file not found(replacefilenamewith the actual fi le name). Forexample:[root@... cs202]# ./nyufile fat32.disk -r TANG.TXT -s 0123456789abcdef01234567TANG.TXT: file not foundThe OpenSSL library provides a functionSHA1(), which computes the SHA-1 hash ofd[0...n-1]and stores the result inmd[0...SHA_DIGEST_LENGTH-1]:#include<openssl/sha.h>#define SHA_DIGEST_LENGTH 20 unsignedchar *SHA1(const unsigned char *d, size_t n, unsigned char *md);

You need to add the linker option-lcryptoto link with the OpenSSL library.Milestone 8: recover a non-contiguously allocated fileFinally, the clusters of a fi le are no longer assumed to be contiguous. Youhave to tryevery permutation of unallocated clusters on the fi le system inorder to fi nd the one that matches the SHA-1 hash.The command-line option isR filename -s sha1. The SHA-1 hash must begiven.Note that it is possible that the fi le is empty or occupies only one cluster. Ifso,-Rbehaves the same as-r, as described in Milestone 7.Lab 4:File Recovery12/18For Milestone 8, you can assume that the entire fi le is within the fi rst 20clusters, and the fi le content occupies no more than 5 clusters, so a bruteorce search is feasible. you cannot fi nd a fi le that matches the given SHA-1 hash, your programEMPTY.TXT– an empty fi le.CONT.TXT– a large contiguously-allocated file.NON_CONT.TXT– a large non-contiguously allocated file.You should make your own test cases and test your program thoroughly.Make sure to test your program with disksformatted with differentparametersThe autograderWe are providing a sample autograder with a few test cases. Please extractthem in your Docker container and follow the instructions intheREADME

fi le. (Refer to Lab 1 for how to extract a .xz  le.) Note that the test cases are not exhaustive. The numbered test cases onGradescope are the same as those in the sample autograder, while thelettered test cases are “hidden” test cases that will not be disclosed. If yourprogram passed the former but failed the latter, please double-check if it handle all corner cases correctly. Do not try to hack or exploit theautograder.Submissionmust submit a.ziparchive containing all fi les needed to compilenyufile$ zip nyufile.zip Makefile *.h *.c that other fi le formats (e.g.,rar will not be accepted.Lab 4: File Recovery

/18You need to upload the .zip  to Gradescope. If you need toacknowledge any infl uences per our academic integrity policy, write themas comments in your source code.RubricThe total of this lab is 100 points, mapped to 15% of your fi nal grade of thiscourse.

Milestone 1: validate usage. (40 points)Milestone 2: print the fi le system information. (5 points)Milestone 3: list the root directory. (10 points)Milestone 4: recover a small fi le. (15 points)Milestone 5: recover a large contiguously-allocated file. (10 points)Milestone 6: detect ambiguous fi le recovery requests. (5 points)Milestone 7a: recover a small fi le with SHA-1 hash. (5 points)Milestone 7b: recover a large contiguously-allocated file with SHA-1

hash. (5 points)Milestone 8: recover a non-contiguously allocated file. (5 points)TipDon’t procrastinateThis lab requires signifi cant programming effort. Therefore, start asearly MAP_SHAREDin order to update the fi le. Once you have mapped your disk image, you can cast anyaddress to the FAT32 data structure type, such as(DirEntry *)(mapped_address + 0x5000). You can also cast the FAT to[]for easy access.The milestones have diminishing returns. Easier milestones are worthmore points. Make sure you get them right before trying to tackle thharder ones.Thislab has borrowed some ideasfrom Dr. T. Y. Wong. Lab 4: File Recovery18/18