Function Media, L.L.C. v. Google, Inc. et al

Filing 82

CLAIM CONSTRUCTION BRIEF filed by Function Media, L.L.C.. (Attachments: # 1 Exhibit A, # 2 Exhibit B, # 3 Exhibit B (continued), # 4 Exhibit C, # 5 Exhibit C (continued), # 6 Exhibit D, # 7 Exhibit E, # 8 Exhibit E (continued), # 9 Exhibit F, # 10 Exhibit G, # 11 Exhibit G (continued), # 12 Exhibit H, # 13 Exhibit I, # 14 Exhibit J, # 15 Exhibit K, # 16 Exhibit L, # 17 Exhibit M, # 18 Exhibit N)(Tribble, Max)

Download PDF

EXHIBIT IU I L]t illlllll (10) (4s) ilt ilril lllll �llll lllll us00617329181 llll�lllll lllll lllll lllil llll il ill (1r) United States Patent Jenevein Patent Date of No.: US 6,173,291 Bl Patent: Jan. 9,2001 (s4) METHOD AND APPARATUS FOR RECOVERING DATA FROM DAM�GED OR CORRUI'.IED FILE STORAGE MEDIA Morge�st9r!, Sleve, "Mako Your Compuler Fastgt, S�fer, Easier to RuD (Using Disk Utility Sof��'ar�", Home Ofice Comprting, Sep,, 1991, p. 46. (7s) Inventor: Roy M. Jetreveb, A�sti�, TX (US) Ayer, Rict� "W41's the Price Magazi�e, Sep. 14, 1993, p. 108, of � Free Luacb?", PC (73) A.ssigDee: PowerQuest Corporatiotr, Orem, UT (us) (.) Notico: Qr) Appl. No.: (22) (51) Shafz-Aki�, Jim, "The Big Squeeze (Software Review)", Macuser, Jan., 1994, p. 129. "PC C�asch? Call Rescue 911!", Newsbyles News Nelwork, Apr 21, 1997, page N/4. Under 35 U.S.C. 154(b), the te�!� of this pafe�l shall be extended for 0 days. 08/939,085 Filed: Int. C�.' * G06F 17130 707/2�s; 7071206 Sep,26,I997 .,.,.......,,............. 707/210; 707 /202: cited by exami�er (52) U,S. Cl. (s8) (56) Field of Search Referenccs Clted U.S. PATENT DOCUMENIS 707/200,m6, 707DOZ,205 Primary Ex�m�ner-+a�l R. Linlz AssMant Exam�ner-Iean Bolte Fleura�lin (74) Attorney, Age�t, o� Fri�n--Ma�c A. Hubbdd (s7) .4.BSTRACT 4,94L,059 1 l�m AD automafd method and apparatus lor idootifyiDg a�d copying losl �les from a D�ss data sto�age device of a comp�ter whe� �le system infor�ation (as oPposd to the actual data frles) stored oD tbe �ass dat� storage device b�s beeD corrupted or destroyed. fte �ass d�ta slorage device is sc�Ded on a seclor-by-sectol basis in order to �ttempl to 5,Ce3,:264 111992 Pl�tteler et al. ,.,,,,.......... 3951182.03 5,n6,&O + 11t994 Fortier et sl. ....,..,,,.............. 395 /575 + s,42r,�6 s,432,92� + 5,32r,524 6/1994 5/1995 't/1995 5,469,573 1u1995 5,473,753 + 12�9 Burkc cl �1. ......,..,,.............. 111l�2o Jablo� et al. .............,...,. 395/1$ 12 Mccifl, III t al. ...,,.,,.,,,... . 3951712 Welf s et �1. .............,,.....,,.... 3951218 idenlify sectors contaiDing filo system data struct�res and �le attributes. IdetrifcalioD is .oade usilg d�ta sigDature and/or pattem matchiDg frlters. The locatiori of, and any 5,493,649 2 9 5,535,381 ',7t19 5,555,�5 * 5,561,7A6 + �11996 Mo� 9/\9 Slivkr el al,,................... 395/185.01 Kopper ........................--. 3951872 Grieslner et �1. ................... '7A7 205 '711/17O valid i�formation found in, sucb sectors is usd tben to derive inform�tioD l�seful i� tocating frles to be copied to �oother storage device. For exa�ple, in a FAT, NTFS or other cluster-oriettod frle syste�, if iDfor�natioD on thc ��mber of sectors per cluster (SPB) is �ol �vailable from a boot direcfo�f it �nd a cluster base (the stsrting seclor of cluster 0) al calculated usiDg the physic�l location of the begiDDhg secto� of tbg direcfories or folders. when a starti�g cluster is k�own f�oo a dircctory e�try, but �ot additio�al fle allocatjoD iDformatio�, a cl�ster chain may be �eco�structed utiliziDg oDe o� more of several disclosed �elhods. 50 Claimq 10 Drawtug Shets 5,594863 1/1997 5,6O3,0m U�n 5,62i,651 4A9n 5J6t,4O4 5,a32,526 + I 395/�2.13 Stiles Hashimoto et al. ..,..........,... 707nU) Jer�ig�n, IV .,,...,..,............., 7t1 nO6 6A998 Mur�t�r�i et al. ......,...... 3951�2.13 Schuyler .............................. 7a7 1Ut9 nIs OTIIER PUBLICA�TONS Merdelson, Edward, PC Tools Deluxe 5.5 (Soflware Review), PC Mag�zine, Ma�. 27,1990, p, L1.2 carofolo, Dedise A., "Take Cha�go!: A Dive6e Pack�ge of Utillities", Idormatiotr Todat Jul-Aug. 1990, P. 13 U.S. Patent Jan. 9.2001 Sheet 1 of 1.0 us 6,173,291�l Keyboard Main Memory (RAM) Disk Drive Controller Floppy Dlsk Dr�ve BIOS (ROM) Disk Drive Controller Hard Disk Drive Graphics Adapter Eig.1" U.S. Patent Jan. 9,2001 Sheet 2 of 1.0 us 6,173,291 B1 f+l 40b |-_---_---l� DirectoriesandFiles RootDirectory + ((no Root Directory loc) I no longer fixed � | I +---1* -lI I | in loc) | | I Ll_1_s�.:t_l L_ *t l3 . Ll FATl Boot F-_-------ll l &2 Secton �aditionz I I I + Ma 40a Root Diectory | (not (not used) used) I E-tP"ttionSt.L;lJ Ext. Partition Sector Dheclories and Files Root Directory (no longer in fixed loc) 44a 40a 46a 46a 46a arlition 1 FATl Boot Sector (not used) 46a 38a 38a 34a Partition Seclor (MBR) 34a Fig.2� Eig.2b U.S. Patent Jan. 9,2001 Sheet 3 of 10 us 6,173,291 8L I o�reaor�es ano r�us NTFS Meladata Files MFI Copy (Pa�ial) Master File Table artition 2 (volume) (MFr) ,b--l 58 Boot Sector Ext, Partition Sector 5ba 54a- 52a' 50a. 36a. arlition 1 (volume) 34a Fig.3 Read Sectors Where Boot Dhectory is Expected MatchThal 0f a Root MalchThat of a Sub' U.S. Patent Jan.9,2ffi1 Sheet 4 of 10 us 6.173.29181 Store Location and Content of Partition User Selects Destination Drive AnaM�e lnform- atio� and Con- strucl Directory Parlition and Boot Sector lnformalion �f Presenl, and Store (Folder) Tree and Group Extra Files in 'Losl -and- Fig.4 U.S. Patent Jan. 9,2001 Sheet 5 of 10 us 6.173.291 81 a Sector-by-Sector Basis Assuming Minimum Number of Sectors/Cluster Match�hat of SubStore Sector Address of Subdireclorv Sub-directories Found Within Parlition Store Address of and lnformat�on in Partition Sector Calculate Sectors Der Cluster Based on Found Subdirectories Look For All Sutsdirectories on Disk on a Sector-bv-Sector Basis Assumino Celculet�d Value for Sectos oei Cluster bv Data Pattem Match MatchThat of Sub- ifhal of Parlition Store Address of and ln- Store Partition lnformalion and Address U.S. Patent Jan. 9,2{�1 sheet 6 0f 10 us 6,173,291 Bl For Each Dir�tory Found, Starting w�th the F�rst D�rectory, Compute Sectors per Cluster (SPCI an�Cluster Base (CB) Through Other of the Found Directories Directory Available q..rT*9 Choose Nexl Available of the Other Dirsctories for Comparison and Recompule Build Direclory and FileTables BY Match�no Entrials in Direclories with Same sPC and CB and Slore in Working Memory Build Partition Record and Store in Woddng Memory For Each Dheclory and Each File in a D�rectory and File Table Check Chain iri Fat Table Starting w�th the First Directory 1 YES lndicate Directory or File Likely Recoverable lndicate Directory or File May be Recovered U.S. Patent Jan. 9,2001 Sheet 7 of 1.0 tJs 6,L73,29IBL 770 NO 182 NO Gopy to Destination Drive Sectors in File Accordinq lo Fat Table Entries a�d Calculated or Known SPC Calculate Number of Clusters for Length of File ol Consecutive Clusters from File's Starting Cluster Address Fig.8 U.S. Patent Jan. 9,2001 Sheet I of 10 us 6,1.73,291 81 188 Begin With Smallest File 190 CalculateNumber of Clusters Required tor File and get Next Unaccounted for Cluster File of the Same as Unaccounted Get Next Unaccounted for Clusler Fig.9 U.S. Patent Jan.9,2�)1 Sheet 9 of 10 us 6.173.291 81 Place Number of BeCluster in First oWind�w - innino and Display End of First Cluster of Selected File in Second Window Update and Display in Fourth Window List of Clusters by Type for Compadson DisDlay End of Matched Clusierin Second Window Receive User's Selection of Comparison Cluster and Display Beginning of Clusler in Third Window Adiacent to Second Window Fig.10 U.S. Patent Jan. 9,2001 Sheet 10 of 10 us 6,173,291 B1 Cluster Naviga�or D�sp1ay for �i6t� ti;E (-oi FILENAME ' ExT ) ��'��;"�i: I us 6,173,29t B7 desig�ated 30 io the frgure. Howeve�, �ost compu�ers use communicatioo between the CPU,lhe main memory, and the va�ious VO devices. TECHMCAT FIEI� OF II.IVENIIoN The�c is also a sep�rate, Don-volalilo, solid st�te read-o�ly memory 32 for storing wbat is refened to as tbe "BIOS" or Tbe itrveutioD pertains ge�erally to �etbods and �pp�ra"Basic Input/O��l Syslem," which is permanently rsider�t tus for recoverhg data �les from mass data storage devices softB,are, sepa�ate from �D operati�g system. The BIOS wher �le syslem informatioD is corrupted or �issitrg. software routitres, wheD executed by fhe CPU, translate r � certai� "calls" from aD executi�g program w�Dtitg lo accss _BACKGROUND OF THE INVENTION METIIOD AIID APPAR�TUS FOR RECOVERING DATA FROM DAMAGED OR CORRUPTED FILE STORAGE MEDIA more complex types of b�s a�langemenls for e�abliflg s The mai� components of a general p�rpose, prcgra�mable, digilal comp�ler, as illustrated by a represe�tative comp�ler 10 showu of FlG. 1, a�e a ce�tral processing unit (CPU) orprocossor12 for �a�ipulating dat� accordi�g to a progra.E of i�structio�s, and � maiD or worki�g memory 14 for le�porarily storing d�ta, i�cluding progra� inslructioos, (The term "data" will be used generically, uDless the conlext otherwise iDdicales, 10 mean any infor�atioo in digital form stored by � coDp�lter, includiDg, without limilalioo, program iDsln�ctiots, [exl, busiDess dala a�d co��maDds.) Most comp�ters also include one or more �ass or blgh capacily data storage devices for lotg term slorage of data in tho form of files. There are �!�Dy types of �ass data storage devices available, i�cluding, for example, Dag�etic �Dd optical !ape, magnetic, �ag�oto-optical ��d oPtic�l disl.s, aDd solid state (o,g, flash �e�ory). Most, but �ot all, of these devices ard media are non-volatile; i.e. they do �ot require power to �aif�laio loDg-lerm �e�ory' Many can be wrlten to one or more limes. ID �dditioD fo fhe basic, ph�ical p�opelies of thei! �espective storago tDedia, they difier in oanner (sequential versus r�ridom) of access, speed of access, cost pr �nit of data stotagg and sto�age capacitf amo�g oth� cha�acteristics. The type of device slected ofton depends on the rq�ireme�ts fo� tbe partiqrla� co�puter. Unlike lhe main me�ory, which stores data i� directly accessible srnall utrits, i.e. byles, �ass data sto�age dcvics are set up 10 receive aDd make data available 1o the CPU iD cor��paralively large blocks. Mass dala storage devices a�e treate.d as poripberal inpu/o�tp�rt (f/o) devices, meaning that thy aDd/or their co�lrollers are set uP (io hardware, softs�are or both) transfer data in relalively large (e.g. 512 byt� blocks. Most modem computers �tilize at least oDe or more magnetic disk media for high-capacity storage, as s�ch to traDslate betweeD the LBA and a pbysical C,H,S address. media cu�ently ofers a good combination of speed of As previo�sly meDtioned, d�ta is o�ga�izrd for sto�age access, capacity aDd cosl. [n tbo representative co�puter of into frlas. Depending oo the size of th frle and the size of FIG. I the mass d�ta storage devices are a floppy disk drive 16 and its coDtroller lE. a�d bard disk drive 20 a�d its 50 the scto�s i� the storage devic& i� which it is stored, files co�trollr 22. Conve�fiooallf the floppy disk drive receives a removable floxible, magnefic disk 17. The hard disk drive may be slored over o�e or mo�e seclors of lhe storage device an I/O device, whether it be aD operatiog syslem or �n application program, info a sq�etrce of commands that are provided, or stored in registers of, a particular VO device o� its contloller for exec�tion by the coritroller. By segregating ,< haldware-dgpgndent VO device access ro�tines fto�t othor prograEs rufrfri�rg oD the computer, higher level Progra�s, such as operating systems aDd applic�rions prograrls, Deed rot be \r,ritten for specific computer hardware, �llowing at lcast some level of compatibility �mong differor�t h�rdwa�e ,^ syslems. Tbe BIOS also includes soltware for handling certaio tvDes of errors wbjcb occur with the I/O devices, as weu as instructjons for testing vario�s comPonents of the co��p�ter wheo it is powered up and loadiag aD oPraliDg system fro� a disk drive. 25 Disk drives are physically addressed by the BIOS usi�g a cylindo� bead �nd secfo� number. A typical hard disk inchrdgs multiple platters rotatiog on a commoD axis. O� each side of each pl�lte� are arraDged cooc�tric tracl(s. Tracks having the same diameter or radi�s lie \��ithin � 3s "cylinder." Each side of each Platler is read a�d writteD to by a sep�rate a read/ETite head which moves across lhe tr�cks. The head aad cylinder Dumbors udq�ely identify a track, ard the sector �u�bor �niqr�ely idettifres oDe of the sectors within a t�act. Tbe cylindet he�d and secto� ('C,HS") 35 address 0,0,1 is always occupied by a pa�litioD se.tor' Hard disks for may be used by � co�p�ter to store more thaD o�e oper�ting system, which means th�t �o�e thaD one t]!e of file system may be �sod to store �les o� a ha�d disk. A hard disk is thercforo partitionablc i�to mr�ltiple "driveJ'or 40 "volumes." The pa.rtition sector stores a table specifyirig tho start and eDd ofeach p�rtitioD, or a liok 10 the next part�tioD, �s well assome olher basic informatio� abo�l the disk. Most oper�ling systeEs address sctors �si�g a logical block address ratber tb�E the C, H, S address. A logical block as address (LBA) is a sque�lial n�mberi�g of lbe sectors wilhin a partitioD or drive. It is ooe of the BIOS' fuoclions system, keep track of u,hat frles are stored, aDd .�vbere tbey i�cl�des a stack of spatially.sepa��ted, stif, �agnetic are stored, in the storage device. Generally, this �le inforplatters, which are usually fixed, bul may also be made re�ovable. the co�trollers for the respeclive disk d�ives 55 �afior is also stored in the same devico as the frles. Som of the information is typically stored i� desigtated seclors or tra�sla�e basic co��a�ds received ftom fhc CPU iDto the areas set aside for that P�rrPose. approp�iate actions for thal pafic�Iar disk drive, ald co�trol the flow of data to a�d from the disk drives, Comp�ters �ill Each operathg sysle� bas a different fllc system. The Filc often include other types of �ass dal� storage deviccs, sllch AltocatioD T�ble (F,{I) file system is t�e Dative file systeE as CD-ROM drives and lape drives. 60 for lBM-staDdard personal coE�putels r�oDiDg the MS-DOS@, Wi�dowsrH 3.x a�d WindowsrM 95 operating I� additioD 10 �ass d�t� stor�ge devices, tbe comP�ter 10 sysfems of Miqosoft Corporation, aDd it is s�ppoded by also iDcludes v�nous otber pg�ipberal compo�e�fs or I/o Mic�osoft Corpo�at�oD's Windows-Nl The FAT frle system devices ��,ith s�hich the CPU commuDicates, including, for was originally developed for small cap�citt floPpy disks, example, a keyboard 24, � video monitor26 and its g�aphics ad�pler 28. ID tbe si�ptest form of tbe comP�ter 10, the 65 b�t has bee� exteDded to be usd for today's very large capaciry disk drives. Thc FAT file syste� has sever�l verCPU, �ai� �emory, the mass dala stor�ge devicqs a��d the sions. The ones used by earlierversio�s of the Ms-DoS �nd I/O devices com��icate over a single system bus, which is It is the job of an ope�ating syslem, paficula�ly its frle us 6,L73,29t 3 wiDdows 3.x opr�tiDg syster�s are geDer�lly referred to as the FAT-12 aDd F�I-16 frle systems. Microsoft WINDOWS 95 supports FAT-12, FAT-16 and a 32 bit version c�lled FAT-32. Microsoft Corporation's Wirdows NT�M operafi�g systom �tilizes a nalive �le system koow� l',lTFS, or Nw 5 TechDology FiIe Syster�, a�d also s�ppols the HPFS frle system developed by IBM for the OS/2@ operatiDg syste�. These systoEs share, lo varyi�g degree, a similar approach to maDagi�g �ls oD tbe disks. RGS. 2� a�d 2� illustrale, respctively, exa�ples of bow 1� B1 4 the FAT-16 aDd F.AI-32 frle systems oryaoize dala oD a b�rd d�k or otbgr mass data storage device. Each has a partitioD secto� 344 stafing �t C,H,S4,0,1. (A noppy disk is ge�erally �ot partitio�able, aDd tberefore h�s Do Partitio� sctor.) Followi�g each p�fitioD seclor, tbere is a bootsl��p seclor, 1r -- which starts al a Axed localioo (C,H,S=0,1,1) so thal the BIOS always k�ows wbere 10 �Dd it. l� the FAf-1� systeE, there is a si�gle boot seclor 36. In the FAT-32 system, the�e arg two, ideotical boot records, oach labeled 38n, for redundaocy. The bool records slore basic infor�atio! abo�t lbe ,0 -d�sk needed by Lhe file system, as well �s a Program for loadi�g the operatitg sysleE� fro� lhe disk The FAT file systems, like the �le systems �sod by maty operating systems, alloc�te clusters of sectors, ratber thaD individual sectors, for �le storage The tr�mber of sclors per 25 cluster withit a partitiot is fixed duri�g formatti�g of the storagc device and stored iE the boot reco�d The �les a�e grouped into directo�ies. The directors ar organized bierarchically starti�g with a root ditectory 404 The root di�eclory i� th FAT-16 syslem is in a ffxed locatioD i� the 30 slorasg dgvice so tha! it c�n be fouDd. However, the F�432 frle �lstem �eod Dot slore lbe rool directory at a frxod location. The remaining direclo�ies, which are set �p by a usr, are srb-directo� of the root directory, ca� be located timJ stamps for crealioo and modi6calio� d�les, its aDt'rvhere u/ithin the dara arca Ma, along with rhe 35 MS-DoS �tributes and security descnptors There is a �ach �ser diectory iDcl�des at entry poioti�g to ilself' "data" attribute for user flles, which ��ay be used to slore staling cl�sler; an e�l�y for identi�ed by 4 "." and listing its actu�l �le dal� for small user flles. A file may bavo addilional its parent diectory if a�y, identi�ed by a ". "' a�d listing its "�amed atlributes." Fo� a direclory the d�14 are� is used to pa�ent's starti.Dg cluster; aD entry for each fust-orde� sub_ store at�ibutes for a sorted i�dex poi�tiDg to tbe frles that are di�ectory, wbich includes its Da�e a�d st�rting cl�ster cre- 40 srouped in lhe direc�ry. The index for a file incl�des lhe atioD date/time (�nd a provision for loDg ti�e ��mes i� �bs �ame a�d refereDce �umber, which is a Poi�ter lo the that Wi�dows 95); aDd a� e�try for eacb frle slo�d frl's onlry iD fhe MFL directory, wbich iocludes ils !ame, le�gtb aod staniog The MFT � a frxed size. lD the evetrt a frle attrib�rte ca��ot cl�ster, Each directory is allocated at least o�e cl�ster fo� �t withi� the eotry aJea �llocated to the frle, the attribute is storiDg tbis iDformatio�. Basically, each entry in � directory 45 stored oulside the MFf, i� which case it is c�lled a �onacts as a pointer fo the st�ting cluster of � frle, sub_dfuectory reside�t attribute. For � user �lo (as opposed to a di�ectory)' � group of cof�secutive cl�sters whero � DoDresidont attribute or pareDt di�ectory If a �le is allocated m�e tha� oDe cluster, the addition�l cl�sters must be chai�od together by is stored is callod a data ruD a� att�ibute's val�e is the operating system by looking uP a po�ter to the rlext �or-resident, its beader, which always remaios �esidenl, cluster in frle allocatioD table (FA� 464 for lhc pafitio�. s0 indicates that is �o!-�esident, aDd it is followed by a pointer to the LCNS of the cl�sters where tbe att�ibut is actually The FAT 46a is stored be� ee� the bool records atrd the stored. This is acco�plished by recordiEg tbe slartiDg vi�tual rool directory. Bec�use of ils importatce, tbere are lwo cluster number (which is � seque�ti�l n�mberi�g of cluslers copies slored. ft has o�e en�y for gach ch�ster in a Partitioo. within the fil� for each ruD, with the LCN where the run Th; entry will hdic�le tbat the cluster is �vailable, beiDg usd or is b�d. If il is o�e of the cluste� ir� a chain of clusters ss begios, as well as tbe �umber of clusters in the ruD In esseoce, data ru�s are tbo same as the files i� the FAI fi19 �a.ld�g up a �le, it will i�clude lhe clustet �umber for the systems, �nd fbe VCN to LCN mapping is simila� �o the next i� lhe chain or a special, prede�Ded char�cter or value stani�g cl�ster i�form�tion for lhe file i� lhe direclory of � for i�dicati�g that it is the last cl�ster in the chai�. The FAT frle system. Howeyel, u�like the FAI system, the nuEber of for the FAT-32 frle system also stores lbe slarti�g cluster for fhe root di�eclory. I� the FAT-16 table e�ch e�try is � 16 bil 60 clusters or �eDgth i� � run is available in NTFS in lbc same enlry �s the sta�ti�g clusler Dumber, as is �lso the staning cluster address a�d i� FAf-32 each entry is a 32 bit cluster clustors and letgth of othe� rutrs storing the frle Thus, iD address. NTFS, there is no Deed for a sePara�e FAT to sto�e cluster The slorage devices illustrated by FIGS 2a �d 2� have alloc�tioD infomation. A separate bitmap frle, which is one by second partition sectors 34b. The second been partitioned Dartitio�s also iocl�de boot reco�ds, 36� and 38�' 65 of the NTFS metadata frles, itdicates whether a cluster is available for allocatioE ot is atready alloc�ted within the iespectivel� root directories 40b, data a�cas 44� a�d FAT tbe New Te-cboology FiIe ordisk forEalted for tbe NIFS incl�des a m�ster partlion sector 344 a�d a boot seclor 36d at fixed, predetermined addresses However, following the boot secto�, thore is allocated sPaca for, iD order, a master �le table (MFI) 50a, a pa�tial copy 52d of the MFf, ard other NTFS metadata �les 5�l�. Tbe re�ai�iDg uDallocaled alea of seclors 564, up to the exte�ded partition sec�or 58, is �sd for sloring �ser �les and index bufers, which car be thought of as a for� of a diectory. Following lhe extetrded partitioD sctor is a�olher volu�e, o� partitio�, with it owr boot se.lor 36�, MFT 50�, partial MFT copy 520 and NFIS mt�data files54� for that volume, and �n area of us� �les aDd directo�ies 56b. The storage device may have, if desi�ed, additioEal xtolded partitio�s, defltriDg additionat volunes. NTFS can be cotsidered aD exte�sioD of OS,2's HPFS aDd iochdes 6le sec�rity features All data stored o� aD NTFS volume is slored in a file, includir-fllcs, NTSF data slnrclures used 10 locale and e the the bootst�ap data �le (which is sto�e-d it tbe retrieve predefrned boot sctor) and a bitmaP flle wbich records the ;llocetion state of each cl�ster on the volume. NIFS data stn�ctures �re refened to �s metadata frles, and also iDclude a log �le, volume �le, aftribute defrnition t�ble, root directo�y aod bad cluster flle, a�o�g others. Like the FAT �le systems, space in the volume is �llocaled i� cl�ste� ofsectors. The Dumber of sectors in each cluster is frxed within a volume. The cluste� are n�mbered scq�rentially f�o� the begi��itg to lhe etd of the volume ftese numbers are called logical cluster �umbers (LCl$. Each frle, inctuding tho MFI, boot tle aDd othet Eet�d�t� frles. has an entrv in the MFL Each is tre�led as a "frIe," as are �he user di�e�to�ies �nd files. Each "frle" iD the MFf is detnel bv a row ol �tlributes. Thesc atkibutes include rhi�ss lik� tbe names of tbe frle (more lhan o�e is possible). Refeniog now lo FfG. 3d, i� Syslem C'NTFS"), a slorage device frles. i� If t�bles 46�. cl�.�ster. us 6,173,29181 J Fo� a directorf a group of cl��sters storing ooD-reside�t �l iDdex i�for�atioo is called an index bufer The i�dex 6 tioD oD the tass data storage devjce. As eEbodied iIr � Eetbod and appa�aius for recovori�g 6les fror� a damaged o� corfupled Eass data storage device, there �re several altribute iD a directory's e�try in the MFIincludes �D iDdex i.Dvenfive aspecls, a fe$' of which, aDd their adv�Dtages, are root segm�t, �o iDdex allocatio� segmeEt a�d a VCN allocation bitm�p. Tbe root i�dex coDtaiDs the �ext higher s su�omarize-d below. order 6le number for eacb i�dex buffo�. Fo� exa��ple, if frles According to one �spec! a compnfer reads � mass d�ta 1,2 a�d 3 are stored iri a clusto� ru! coDstituti�g a �rst iDdex slorage device on a sector-by-stcto( basis iD order fo allemPt bufer for a directory, file 4 (or the oext bighest orde�ed �le to idc�tify, snd thus locate, through tbe us� ofdala sig�ature o�mber i� the directory) is slored �s the root. For e�ch rool, �Dd/or patlem m�lchi�g "�ltsrs," sclors coDtaining frle there is a VCN-LCN mapping in tbe i�dex �llocalior� 10 system data slruct�es atd frle �ttnbutes, whelber or Dot the such sectors is v�lid. These seclors �ay informalio! segment, wbich includes the startiDg VCN a�d LCN of lhe index bufier and ihe ��mbr of cluslers i� the buffer. The include, for example, partitions, wbicb logically divide the storage devica into separate �le sp�ces or vol�mes a�d �le bitmap segmeDt tr�cks which of tbe VCN'S i� tbe allocated clusler ru�s are free for stori�g additional indgx"s within the system data st�uctures (for exa�ple, the F�[ tables, MFIS or d�ectory enhy. The index buffers �re th�s, in maty resPecls 15 similar cluster allocalion data structures). Tbey also may the FAtr like a directory stored in the data user alea incft�de ile attsibutos, includirg, for example, directories or systc�rs. fo1do6 iD the Fl�I atrd MAC OS �le systems, Don-�side�t NTFS, ot otber frle attributes such as itdex b�ffers Becar�s dat� for lbe fl19 system for a particu�ar slo�agg hicrarchical flle orgadz�tioD data structures (wbich are device is slored on the dovice itself, a comP�tI c�ash, ha�dware �alfu�ctioD or progra�rming glitch c� desfoy 20 someti�es geoerically referrod to herei� �s directories), which may be stored iD user data a�eas. crilical data �ecessary for �olrieving �les Magnetic disk lD accordaoce with a�other a�ect, the locatioE of, aDd drives, io palic�.la�, are suscplible to dala co�rupt�on, any valid information fot�nd it, the sectors, is ustd to de�ive tho�gh it can h�ppen to any medi� to which data is vritten, info�oation �seful in loc�tiDg �les to be coPied to �Dothe� or oD whicb it is stored. For exa�ple, �le system informatio� a FAT, NTFS or other ca� bc conupte-d by d�m�ge to tho disk me-dia caused by 2s storage dovice. For example, cl�ster-oriented �le syste�o, if infor�oafiot on the n��ber of physical shock or, iD conventiooal bard disk drivos, a crash se�to� per cl�ster (sPB) is not �v�ilable from a boot of a read��v�ite head sbould the disks $rddeDly sfop rotatiDg di�ectory, it and a cluster base (tbe starti�g sector of cluster A bardw�e �alfutrclion in tbg device's co�troller, a bad 0) are c�lculated �sing tbc physical locatioD ofthe bogiDDiDg ��emory chip orpoorly written software caD a�so corrupt flle system datt. A power o�lage can strike befo�e caching 30 sectoE of the diroctories or fotders. software has w�itteD all of its cached data !o a file on the According lo a furlher aspcct, iD the eventsector or cluster devic. IEproper po��/eri�g-dow� of a computgr c�n leave alloc�tion itformation is missing for a klown file or di�ec_ crilical �le system iofo��tion stored in memory before it lory for example, wheD lhe slariog cl�sler is k�ow� from a is written 10 lhe device. direclory eDlry, bur ool addirional flle allocalion rr iriformation-a clusler chain may be rgco�strucled uliliziDg The FAT �le system is palicularly at risk Most frle one o� fnore of sever�l Eetbods. The melhods iDclude svstcm corruption occtus Dc�r lhe bcgiooiDg of a disk pirtiLion, wbeie lhe mosl critical FAT flle sys�m i�formarccovering cluslers in sequence from the stafing cluster whicb is larg nough to hold the �le, assumi�g recent disk iion �esides. Tbgre ar comp�ter vir�ses that sPecifrcally target a FAT parlilion lable or bool record, wbich c�n wiPe ,^ defragmetrtation; automatic groupiDg oflost clusters by data type, dete��iDed thro̡gh aDalysis of the flle data, stalti�g oul critical ioform�lioD oecessary to retrieve Ales There is with the smauest files, aDd assuming seque�lial chrsler � "wr�pped aro�nd" efrect which m�y ca�se d�la in the FAT alloc�tio!; or matchitg by � user thro�.�gh us of a visual �le system to be overwrilten when � l�rge caPacity disk is i�torface displaiDg in closo, spatial ptoximity th oDd of a replaced in an older computer that dos ool have ao EIDE disk cootroller, and lbe LBA modc d�k �cccss or lhe largc .. l�st kDown cluster i� file to �n available clustor. capaciry disk soft' are drivor is improperly ioslalle-d. lhese and olber aspecLs aDd adva�tages will be apParenl from tbe following delailed doscriPtion of a Plefetred if inform�tio� o� the Dumbets of secto� per Furthermore, embodiment, iead in conjunctioD with lhe appende-d drawcluster (SPC) is los1, any fl syste� information storing rng�. locatio� of �l's �.td directo�s �sing cl�steIs be@�es usless. If ioformatio� oo wbere exteod p�rlilio�s cxisl is lost, {n BRIEF DESCRIPTION OF THE DRAVr'INGS -all file system informatior� for ao entire Panilion is efec_ FIG. 1 is a sche��tic diagra� of a represeDtative comtively lost, puter. Prior art utility prog��rs for recoveri�g flles stored i� F'lG. 2o � aD sche�atic rep�esntalior� of the use of FAT frle systems, such as Nolon Utilities, usuauy try to secfors i� a m�ss data s�orage device storing �les �sing the "frt''corrupted flle syste� i�formatio� by w�iliDg �ew �le s5 FAT-16 file system. system data to the disk so th�llhe operatiDg system can then FIG. 2b is a schemalic represe�la lion of the �so of sectors the device. However, tbes frxes arg acass tbe files from in a �ass dala storage device sloriog frles usiDg the FAT-32 offc� iDeffective, aDd �ay cs�se valuable data to be overfrle systero. fiitten in the process. FIG. 3 is a schematic lepresDtatio� of tbe sectors of the 60 SUMMARY OF THE use of sctors i� a m�ss data storage dcvice slori�g fles using the NIFS �le system. The iDvDlion pertai�s geDerally lo a�toroated methods FIG. 4 is a flowchart ill�strati�g steps of a comPuter and apparatus for idendryhg aod copyi�g lost �les fro� � process for recoveriDg lost flles from a m�ss data slorage mass data storage device of a comp�ter whe� file system idor�atio� (as opposed to the actual data �les) stored oo the 65 device of a coEputer, FIG. 5 is a flowchart of a comp�rter Process fo� locatitg mass dat� storage device has been comrptcd or destroyed, a rool directory----�s part of the process of FIC. 4 without writing or attempting to rpair file system informa- ir i! it it - I}TT'LNTON us 7 6,173,291 81 I FIG. 6 is a flow charl of a comp�ter process for identifyiDg pa�ti�iols, directories or other frle attibute's in a FAT systom oD as pa�t of the process of FIG. 4. FIG, 7 js a flow chart of a procss fo� calc�lafi�g tbo n�fDbe� secto� pgr cluster ��d cl�ster base for 9�ch d�ectory, a�d building tabls of directories and files for 5 sectors. For exa�ple, i-u the F�T �le syste�s, tbe last two byte� iD the partition sctor ��d the boot �l�,st have the values aa55h. Pattem matchi�g involvos looking at pattems iD the placemeDt and value of tbe bytes iD the sectot or gro�ps of sctors, th�t te�d to �niquely ideDtify that par- selectio� for recovery. FIG. I is a flow chart of a coEputer process for recoverif�g files haviDg valid clusler chaio i�fom�tion, Paliculajly a -^ valid FAT table, or wbeD the dala slor�ge device is receEtly i" defr�gmeDted. FIG. 9 is a flow chaf of an automatcd computer process for recovoug �les with missitrg or iDvalid clusler cbai� i�fo�matio�, particularly, �issiDg or i�valid FAT table tic�lar type of tle atEibute. A dala Pattem match �ray hcl�de checki�g 10 see if the b}'te values in certain locatio�s withi� the sctor or cluslr �ss��e o�e of certai� permitted values, or are within a r�Ege of permitted value's. In NTFS, for exa��plg, the "magic oumbel'' "FILE' can be ssarchel fo� in o�de� to ideDtify the MFI aDd tbo magic nuebor "INDX" can be searched for i� orde� to ideDtify index bufers. gf the process begiDs a secto�-by-secto� read, coDpar.. i�gNtbe, co�tenls of each sctor to a series of data fllte�s to entries, iD fr�gr�e�ted dala slorage device look for other palitio�s aDd fll att.ibutes (for example, FIc. 10 is a flo.�� cha�t of a user-cont�oll�ble computer ol�er root directories �Dd directorias, includiog folders in lhe process for recovering flles wifh missing cluster chain FAT-32 a�d MAC OS flle systems, and, in N�FS, i�dex i�formatior�. b�fiers, cert�iD NTFS �etadat� a�d/or other �ot-resident FIG. 11 is a diagram of � user screen interface for use in z0 frle �tlributes.) The ad<l�ess �Dd infor�n�tion contai�ed iD tbo process of FIG. 10. found �le �tlribufe secto� are stored i� the dala slructure sl up iD lhe workitg merDory of the computer. DETAII-�D DESCRIP�ON In a oreferred embodiment, tbe ioveDtion takes lt�e fofm of a pr�gram of instructio�s stored in me�ory of co�puter, vr'hich a�o being exe�uled by tho CPU of a con�Puler, such as CPU 12 of lhe computer l0 io FIG. l. The prograo is Ioaded ioto the co�puter fro� a floppy disk (such as Boppy 25 disk 17 in FIG, 1) or other romovable slorage media inserted i�to a bootable stor�ge device. The oporating system is Dot 30 loaded. To access o� com�unicate with the disk drives and other I/o devicas, the program relies o� the cotopl�ter's BIoS or other per�aDeDtly-residont, ha�dwa�c specific, I/O device access �oulircs. In lhe follo'��ing descriPtion, like numbers refgr to like 35 c��r��t operating systems �llocate �ac in a storagc device Rferrillg to FIG. 4, a coEP�rter �nder the co�trol of the in a cluster of sectors, the �ltering or ao alysis of a seclor �ay progaam sta�ls by testing each coDtroller for each disk drive also involvj�g analyzing the coo�eo ls of other ie�d seclo�s i� (or other mass dat� storage devic used foa storiDg frles) iD co�j��ctioD therewith, �ssu�iDg � �i�i�um cltlster size, to step 60 to deter�ine whether they are the computer al confi�� th�l the sec�or ispart of a cl�str lhat contains a nlo fuDctio�i�g prope�ly. At decisiot sleP 62, if none of tho +o attribute or panitio�. As indicared by decisioD step E4, the controllers p�ss, the procss ends. Othenvise, fhe devices proces,s of repeals by getling lhe nexl seclor, unlil lhe �re tested �t steP 64. The dlive wilt� workitrg controllers pbysical e�d of the storage device is reached must f�Dct�oo electronically to recovga data. If �o�e pass at By the forgoing process, partitions, directories �nd fragdecision step 66, the process c�ds Otherwis, the user is workir�g storage 45 meDld directo�ies, and other frle attrib�les ca� be located, pro�pted at step 68 to sglect one of the even whc� the maslor partitio� scctor is corrupted, thc root �eviccs as a source, �nd to select �t step 70 another of the direclory is missi�g, FAT tables or MF-IS are corruPted, or worki�g slorago devices as a destinalio�. The source storage sPC infor�atioD is roissiDg fro� the bool sector destinatioo device coDtains the frles to be recovered, and the ODce lh sc�Dning aod �lteri�g process is coEPlte, the storage device is the slo�age device to which recove�ed frles joformalion collecled 50 Drocss moves to slep 86, wherei� the will be �uring the sca� is u�d lo reconslrucl direclory trees of �les step 72, the co�puter bogins a process of a sector-byfor diplay to tbe user Briefly, this may i�clude delerEiDing ^t sector sca� of the source slorage device to ideDtif� aod thus lhe Dumber of sctors per cl�ster (SPC) �nd the cluster bas flle sys{m locate the physical address of, sectors coDtainilg (CB), for each partition or volume, if such iDformation is not inforBation. lfl pa�tiqrlar, at steP 72, the comPuter reads the andPartilion seclors or other master palition sector ��d boot seclols, wbrcb are at pro- 55 avail�ble from the bootsectors, file system data slruc�tres. Furthermore, the dircclories are each sector is determiDed sector addresses. The data iD checked to determi� wbelher tbey are Part of tbe cu�e�t checked to determi�e whether it �atches fhe sjgnat�res a�d directory o! folde� struct��e (i.e tbat they aro tot deleted or paltems �ocessaly for valid sectors using data "flters " data lcft from prior device fo�m�ts). The cha�ces of recovering a data If, the i�formafio� appears valid, it is stored iD on whether cluster allocalio[ structurc set up itr fhe wo�kiDg �e�ory (s�rch as maitr 60 each file is �ssessed based ilformafion is available �rd aPPea�s valid. All flles and 14 in FIG. 1) of the CPU, iD wbicb infolmatiot memory d�e�lorios' hich can't be placed in tbe directory Fee �re collected by the scan will be stor-d for subsequetrf a�alysis [sted separately io a "lost aDd fo�td " A "fl1te/' is a prede�ned sig�atu�e aod/o� alata pattem, At step 8E, the direclory tree �nd "1ost and fou�d" �re which data in the sector is comp��ed. Briefly, sigagainst �ature matching i�volves lookiog for predefned byte val�es 65 disDlaved to the �ser in order to receive a user's selection of th;fl�s to bc rocovered. At $ep 90, the flles ale rccovered iD ccrtaio offsels or locatio�s (eilher absol�te or relative to by identifying a�d copying the clusrers in which the Ab is withiD a seclo�, or wifhiD a cluster of other byte values) pals. At step 74 the comp�ler gels lhe nexf sector' Ii as indicated by dcision step 76, tbo sector is ideDtifred, thro�gh sigEature m�tchi�g, to be an extended Paftitio�, ils coDtenls aDd physical address (logical block address or cyli�der, head, sector address) ��e stored, at steP 7E, it the data strucfures set up iD the worki�g memory. If the sctor is Dot a Da�titioD sector, its coDtenls aro mafched to dala �lters to detofmiDe if it is a frle attrib�te. As iDdicated by decisio� step 80, if the sector is part of a frle �ttributc. the �ddress �Dd conteDt of lhe �lo attribute are storod io the dat� struct�r io the working me�ory of the comp�tef at step 82. lt should be Doted that, since �ost cnpied. us 9 6,773,291.81. 10 sl�ucfure kept in workiog �emory at step 110. The process the! �etums 10 the steps of FIG. 5. Hos/ever, if �sked step 104 the dat� paltem ma�ches that of a sef directory the address of the said directory is stored 5 If, at decisioD to step 114, two sub-directories have f�otbeeD fo�Dd witbin the ssme palitio�, a�d other words, lhis is the �rst sr�b-directory found witbi� the partitio!, the process Ioops b�ck fo step l(N wbile it rcads tbe �ext sctor at step yo� 116. However, if two sub-directories have beo� found 1n -- \r�ithin the same partition at decis�on step up 114, tbo o�mber of seclors per cluster is calc�lated �t step 118 based o� tbe stafting seclors of the two srb di�ectories. Having this info�oatiotr better e�ablgs, and speeds �p, rcognifiot of directo�ie.s. 1< -- stored to l�e destio�troD drive in a ma��er wbich prese�es the directory hierarchy, o� as a co��pressed or �ncoEpressed flat files. To the exlent cluster allocation informafion is tot avalable to cbai� clusters of the selected flles together, the process caD assume tbat tbe clusters iD each flle are sequential if the disk has beeD recenlly def��gmeDted, or, if tbe disk is fraguented, automatically group remaioing cl�slers, which have Dof beet associated \'�ith a frle, directory tlo system data stnrcture or other file att�ibute, by d�t� q?e coEmencing with lhe smallest Ales aDd ass�Ei�g a sequential allocation of clusters. Altemately, or i� additioo therefo, the compute� process caD allow use� i�tervetrtioD by visually comp�ri�g i! adjaceDt wi�dows o! a display the co�teDls of aD e�d of the last k�ou'o cl�ster iD a flle to the co eDts at tbe begi�ni�g of ore of the reEaini�g utassoci�ted cl�sters, been picked by a user from a listiDg of �vailable clusters iD aDotber whdow arra�ged by locatioD a�d clusle� tt?e. Onco all flles �re c�pie4 the process e�ds. However, the scanning, aoalysis and fllc �ccovery sleps ca�, if dosi�ed, be repeated, or the eDlire procoss Tbe follo\��i�g descriptiotr of cerlai� details of the forgoreference FAT frle i�g process ar�d apparatus is oade syste�s $rbstantially as �sed by tbe DOS, lvINDowS 3 x and MNDOWS 95 operatiDg systens, on a disk drivo. Rferri�g 1o FIG. 5, the portioD of fb sc�nDiDg process followillg �eading of the rEaster parlitioo sector �od boot sector of a storagc dovice, which portioo is geDe�ally ideDfified by steps 74 to 82 ol FIG, 4, slarts by lookiDg, �s indicated by step 92, for the root directory of the �rst partition or vohrme on the storage device based on when should be locatd. Further�ore, e�ch slot ol eotry in the rool d�eclory is mafched �g�inst a dalapartem frlter,which looks for per�ittod byte values in certain, predo�ned Positions or frelds wilhin lhe eDtry. For exanple, the root directory will have in the oame field of one of ils ettries a volume label FurthorEo�e, the process cbecks gacb entry for permitted b''tg val�es i� the frle Dame and file extensio� �elds, as well as io date and time stamp frelds for creatio� and l�sl �odi�catioo. If the root d�ectory is fo̡Dd, as i�dicatel by decisio� s�ep 94, its address aDd conto�ts �re stored i� wo�HDg r�emory at step 96. However, if the dat� in the secto� do �ot Eatch that expected for a root directory it is matched agai�st �lters for �ser directories, which �re also referred to horoi� as sub{irectories, at decision steP 9E These filte�s are similar 1o the ones used for the root di�ectory. However, i� lbc FAT frle syste�, the sig�atuo bytes of "." and ".." a�e chocked for it tbg Dames �elds of tho 6rst two ertdes. If tbe sector is Dot pa't of a s�bdirectory, th Dext sector is fetched or read, and the process repeats looking fo! the root di�eclory. If a sr�b-directory is The followiug formulas may be �sed to ca�culate the secto� per cluste� (SPC) �nd the cl�ster base (CB): reslarted i� zo y��-Cd,,) cB-0.84-d+secto�e)-(2xsPc) 9PC>(LBA4�-LBAa (1) (2\ ?5 it "." e�fry iD the directory Doted in the subscriPl lf tbc directo�igs are adjace�t to o�e aDofher aDd small, fh� tbo LBA of each directory could be simply subtracfed 10 frnd the SPC, siDce directo�ics are allocated at besl oDe cluslor in the FAT �le sysfem. In form� a (2), Soctors-, is fhe number of seclors i� the rool directory, aDd LBA-, the logical block 30 the root directotf If the root address of the �rst sector directory is not found, then CB can be calc�rlated using the iD lhe For for�ul� (1), the "LBA' refets lo the logical block address of tbe begi iing sector of the particular dire.tory Doled i� subscript, a�d C is the sta�ing cluster address fo��d i� followi�g for�uta: �s cB-(ca,/LB{�,2-c��axtB^a�l(ca^-ca� (3) At decision step 120, the Procss determines whether the calculated SPC isvalid.I� order for the SPC 1o be valid, the ��.Imber resultirg from the c�lc�lation must be a power of 2. 40 If �e calculated SPC is �o! valid at step 120, the process of loops back to s�p 116, where the �ext sector is read aDd the process is repeated for that seclor beginning with step 104. �t step 122, the procoss continues, if the calculalod SPC is valid, to sea�ch, sector by sector, for othe� sub-directorigs 45 aDd partitions, using the c�lculaled val�re for the SPC for data pattorn m�tchi�g, in a f�a!�er simila� to tbat of steps 106 and 108. At step 124, if lbo data pattem does not rnatch that of � direc�ory if is coEp�red to tbo data pattem �lter for a pafitiotr �t step 126. If a partition is found, the! it is stored 50 at step 128 stored in the process retums to that of FIG. 5 If tbe secto� does lol h�ve a data paltem ��tching that of a found, however, it is assu�ed lhat the root directory is pa�titio� sec�or, the processes reads tbe Dext sector at steP co�upted or missiDg, as sectors iri the "data area" or �se� 130, provided lbat the eDd of the disk has not beeD reached, area are beiog read. T'l�e Procoss then ptoceeds to FlG. 6. the data as iDdicaled by decision step 132. Howover, Rferring to FIG. 6, �s indicatd by decisio! block 1(D, a process of looki�g for additio�al sub-direclories on the 55 pattem malches rhat of a directory at steP 124 lhe �ddress and to i�formatio! in the diroctory is slo�ed itr the data srorage device is perfor�ed on sector-by-seclor basis. The slructure ofthe worki�g memory. If the sector is nol the l�st search assrmes that tbe ��rmber of sectors Per cl�ster arg the on tbe dislq as iDdic�led bydecision step 132, the next scclor minimum allowed by fbc �le system. As by dcision slep is a read �t step 130, aDd lhe process toops back to decision 104 the processed reads lhe data pallero aDd comparos il ag�insl a data pattem expected for a direclory iD a r�a��er 60 step 124. As iodicated by decision step 132, if the end oftbe desk h�s bee� reached, lie process eods. such �s fhat disc�ssed in connection ��'ith FlG. 4. If the data Refeni-og now lo FIG. 7, as indicaled by block 136, a paltem does Dol match that of a dirgclory Process, il is val�e for the nu�ber of sectors per clustor (SPC) aDd the �hecked agairsl that of � pa�lilio� sector al step 104 If the clusler base (CB) a�e calculated, using the form�l� (1) and dala pattem is r�ot a match for that of the Partitl'on sector, process reads tbc oext seclor 108. However, if, at 65 either formula (2) or (3), sel forth above, with the LBA of theD the each directory fou�d iD the sca� as LBA�,.,r. The process decision step 106, the data Pattcrn matches fhat of the begins with the fi�t dire4�ory, �s indicated in step 136. The oalition sector the address of the sector is s�ored in the d�t� if us 11. 6,773,291. Bl t2 LBA of t�e �xt directory is �sed i� a! i�itial calculatioD of SPC aod CB. At decision step 13E, if tho SPC aod CB resulti�g from the calculation are valid as LBAd,.,2 �urobers-{be SPC musl be a power of 2, for exaEple, aod the LBA of the cl�ster bas must be loc�ted sornewhero betwee� tbo g�d of bool direcfor a�d the end of tbe root dLeclory-the res�lt is stored at step 140 aDd, as itdicated directory at slep 144 for coropa�ison at step ��6 so lo�g as thore are olher directories for which calculatioDs are to be made. However, if the SPC a�d CB are Dot valid, tbe process cbecks to see if fhere is �oother directory �v�ilable for comparisoo at step 146. If ole is Dot av�ilable, the iDv�lid result is stored at step 140. If there is one available, it is selected al step 148 and SPC and cB recornp�ted The process the� loops back to step 138, for validatio�. O�ce aD SPC a�d CB is calc�lated for cach directory the process builds diroctory �td AIe tables at step 150 and partitio� sectors at step 152, bolh of ��'hich are sfoted iD the workiog meoory of the computer. To robuild the hierarcbiby decision step 142, the process loops b�ck to get lt� Dext 5 If tbe FAT is valid, as i�dic�ted by decisioD step 170, the process begins with the �rst selected flle, as indica�ed by step 172. If the selected frle's cluster ch�iD in the FAtr table is valid, as indicated by decisioD step 174, the selected file � copied fo a pre^selected desti��tio� drive at step 174. The p�ocss theD returns to decisioD step 174 a�d rgpeals with lhe Dext selecled file, as i�dic�ted by step 178, uotil the lasl selecled frle is copied, as i�dicated by decisio� steP 180. If the FAT table is iDv�lid, as i�dicated by decisioD step 10 170, or if the sele-cfed �le's clusler cbain is invalid, as iDdicated by decision step 174, theD the process P�oceeds safe 10 �ssume lbat all o[ the selected frle's clusters �re sequentially allocated, fhen fhe 15 process, at decision step 184, calc�lales fho number of chains recuired. based o� fhe size of the �le fou�d in the d eclory ��ry for lh frle. Using tho st�rting chster ��Eber from the directo�y e�try the calc�lated rmber of cl�sters are tbeD copied to lho pre,selected desti�lioD drive at stgp 20 186. Afte� copyiDg, the proc-css gels the next frl �t steP 178 if more flles remain, a�d loops back to decjsion steP 174. cal d�ectory slructure, the directories are threaded toggtber Otberwise, the procss ends. usiDg tbe ert�ies iD the directory. Each of tbe diroctories If the disk h�s not be�n receDtly defrag�ented, and the the structure must have the same SPC ar�d CB. However, old FAT table cannol be used 1o chai� toggthe� the clusters of a direclo�ies left after a rforroattitg may have difere�t SPC and CB val�res. Thes SPC a�d CB values are used to 25 frle, a�otber a�tomated process illuslratod it FIG. 9 �ay be used. Refer�ing tow to FIG. 9, ill�strated is �� automated ca.lculate the LBAS of the clusters maki�g up each of the process for gro�pi�g clusters based, it part, oo the type of files in tho di�ectories. Di�ectories which do Eot flt illto the data stored i� tbe clusters aDd aD assumptioD th�t the cluslers structu�e are placed i� � lost aDd found category. These are iD tbe s�allest �les will be seq�e�tial, eveD iD �elatively pl�ced in a "lost aDd fo�nd" list. Begi�ni�g at step 19, a g�ch of is performed for each found director� and e�cb frle 30 fragme�ted d�ives. The process classifres the data in loop the cl�sters ir one of a prede�ned nu�ber of classes, for de�ermiDe listed iD each found directory. Tbis loop checks l�c exa�ple: PCtexl, Unix texl,Don lext, or C/C++ source code, whether lbe clusler chain of lbe directory or �le it th FAT and compressed da!a. These classifrcations c�D be ��de vatid, assuroi�g that the FAI or its copy is fou�d. is based on the distribution of symbols within th clusler, ��d The FAI can be located using sign�hfe and data p�ttern matchi�g. The begi�flingofeach FAT always has tho u�ique 35 the� compari�g the dislributio�s to frgures of merit At step 188, the process co�piles a list of clusters wbich have Dot sigDature bytes of FFF8, if it is for � haJd drive, or FFo, been accounted for �s, for ex�mple, thro�gh a valid FAI it is for a floppy. F�rthemore, lhe FAI alwals begins at a table entry or part of a direclory, The smallest of the �sr's specifrc pbysical address, depeDding on whelher it is a selected �les is chosc! ��ilially, at slop 190, and tho m�mber FAT-16 (C�,s=0,1,2) or FAT-32 (C,H,S=0,2,1) tl's size, however, is not ktow�, because iL depo�ds iD p�l on the 40 of cl�ste� requi�od to hold lbe �le, based oD its size as recorded i� its directory entry, is calcl�lated. Ils sta�tiDg or �uEber of cl�sters on the disk. Howeve�, the root di�eclory, bas clusler data typ is compared sq�entially with each of if its loc�lion is know�, defrnes the upper bour�dary of the the available clusters, slartiDg with the �ext highe� ote to tbe copy of the FAT. The FAI will also bavo nume�ous file's stafi�g cluster, If, �t step 194, there is a data type sequefices of $rccessive Dumbers, si�ce most �les afe stored in sequences of clus{rs. Data pattem matching techniq�es 45 malch, the add�ess ofthe cluster is recorded �t step 196, The process the� gels the next �rnaccou�ted fot cluster at stP 198 car be �sd to assign a 6gure of merit to r"hat is believed to �nd loops back to step 194, �nlil the l�st �vailable cl�ster be the FAT in order to judge whethcr it is valid or c-orrupt. with the cor�ect d�ta type is found, as indicated by decisio! As indicated by decisiot step 156, if a valid SPC aDd CB step 200, or �ntil the end of the pafitioD is reacbed, as are not calculated for a flle's di�ectory, it is indicated l,o the user, �s step 158, as not �kely to be recoverable. If, the 50 iodicated by step 202. O�ce the lasl cl�ster of �le is matched, the �l is copie-d directory has valid SPC ald CB values, tbe� the F�T is at step 204 to the presolected destination drive O�c the file checked at decisiot stcp 160 to see if tbe fl1e's cluster chai� is either copied or the e�d of the partitio� is reached v�ilho� t or "eDtry' is mmplete. Tbis chaiD is stored iD the data finding e�o�gh clusters to make �p the �le, the process looPs struc�re seh.rp itr the worki�g memory. If it is complete, tbe 55 back �o step 192, provided tbere �re additio�al, �ser-selected flle is itrdic�ted at step 162 �o likely be recover�ble. If frles, as idic�ted by decisioD step 206. ID the loop, the lext �ot, the frle is iDdicated at step 164 as possibly bei�g biggesl flle witb missi�g cluster iDfor�alion is selected at recoverable. As i�dic��ed by dcisioD steP 166, lbe Process step 208 for �oatchiDg. Th� process rePeals, e�ch ti��e loops back to step 154 until all of lhe 6les havc beeD getting the text bigger user-selected file, u�til all have gooe cafegoiT�d. tbrough the recovery process FIGS.8, 9 and 10 ill�strate diffo.eDt techniques for The processes described in FIGS. 5-9 are described itr recovering frles. Recovering a �le requires the knowledge of speci�c rcference !o the EA� �lg systems However, thes its sta�tiDg cluster, which can be found f�om dirccfory enlry processes, or their tech�iq�es or methods, ca� be applied to fo� lhe frle, the chain of lhe clusters making up the file, atd NTFS and other frle systems,lbe Primary differences involvthe SPC �nd CB to calculate the LBA of each cl�ster' iog the sigDahrre a�d data patter� �lters that are applied Refenj�g to FlC. 8. ar �ulomatic frle rccovery Procss is during sca�ni�g of the slorage device. For ex�mPle, duri�g illustr�led. Files fo� recovery arc selected by a �ser, at step scanning of a slor�ge device storing N'ITS files, tbe MFT 16E, from list of frles displayed on lhe compute�'s monilor defragmoDfod, such thal decisioD step 182. If the disk il is b�s been rece�tly it if ilis us 13 6,773,291. B1 t4 available, the f.rst fle storage device being divided i�r � plura�ity of itdividually addressabl seclors storitg blocks of data, the method co�prising the steps of re�ding the first flle slorage device on a sector-by-soctor basisi stored by the frle systg� i� data skuct�res by co��paring d�ta lherei� to predeter�i�e.d d�t� pattems; reco�structi�g the directory structure, at least iD P�t, ftoro lhe ide�ti�ed frle attribute iDformstion; a�d copying a �le io fbe recoDsl�ucted direclory structure to a seco�d �le stor�ge devicc. 2. A Eelhod for recoveriDg files lbat are stored on a mass dala stor�ge device of a computing system and that are organized inm a hiorarchic�l file stotage system used by an ca� be found by looki�g for the D�rmbe� correspooditrg to the word "FILE", which is always fo�td iD tho MFT. IDdex b�frers a�e located by lookiog for the word "INDX'. By usi�g LCN a�d actu�lLBA, SPC atd CB can be deter!�i�ed usi�g t�r,o idex buffe� i� the sa�e way as the sctors per 5 cluster is determited usi�g directories or folders i� the FAT frle systeDs. A co�uptd or missing MFI aod Palial MFI is simil�r to baving a missi�g root directory iD tbe FAT �le systems. D�ectories ca� be tbaeaded, to the extett possible, usiDg the conte�ts of the index buffors, and the tbreaded 10 directory struch.rres put i�lo the "lost aDd fou�d" category Na�es of tbe user �les �re part of ڡe i�dexs in the index bufers. ReferriDg Dow to FIG. 10, as an �ltematg to using aulo_ matic methods of chaini�g together cl�sters whgn clusler 15 allocatio� iDformalio� is missing from the FAT, the i��str�ted process of FIG. 10 aids tbe use� i� "r�a�ually" chainiDg togelher cl�stels. Begi�ni�g witb tbe firsl �serseleclod frle, �s iodicated by step 210, the Dumber of the stali�g clusler is displayed io a frrsl window o� the screen 20 of a Dorifor or other usor iDtqrface of th computer, aEd the e�d of its co�torts is displayed in a second wi�dow of the �sr interface. This slep is indicated by block 212. At step 214 lhere is displayed in a fourtb window a list of available cl�sters. ID the third wiDdow, as indicaled by steP 216, there 2s is displayed the begioaing of � available cl�ster selectd by the user for vis�ral co�parison. The second and third wi�_ dows are iD close, spatial proxiroily to facilil�le co�parisoD If the user decides �t de.isio! step 21E that the two clusfer's "match", that is belong together, the user so indicates a�d the 30 comp�ter �ecords the add�ess of the matched cluster and displays il itr the f�sl wiDdow, as indic�ted by step 222. At step 224, the co�p�ter theD displays the e�d of the j�sl�a�ched cluster in the sec�nd window. If user does not thitk that there is a vis�al �atch, the user may select atother of 35 the available cl�sters for cotparisoD at decisio� steP 220 If there a�e no more cluste�s available for comparison, the �ser caD either go back to review the �les (which step is Dot hdicated or the drav�i�gs), or the user �ay Proceed at stgp ideDtifyi�g sctors cotrtai�i�g �le �ttribute inforEation operating syster�, the mass data slorage device beiDg divided into a plurality of iDdividually �ddrssable blocks, called herein sectors, for storing blocks of data, eacb sector baviDg a� address, the metbod comprisi�gl reading from the �ass data stor�ge device on a sectorby-sector bas�s; idenfiryir�g seclors contaiDiDg �le systgm data slruclures by c�ropa�itg dala therei� to predeler�i�ed dafa pattems and/or sign�tures foutd in d�ta slrucfures of the flle slctem; re�diEg tbe i�formatio� from the ide�ti�ed soctors; aDd reco�structi�g at least part of the hierarcbical �1e s�orage system basod on information read f�om the identifled sectors, 3. The method of claim 2 fu�ther coEp�isi�g coPyiEg a filo listed wifbio the at least partly rec-onstructed hiera�cbic�lflIe sl�ucfure lo a second mass data slorage device 4. The �ethod of clai� 2 wherei! storage o� the mass data storage device is allocated for stori�g frlos oD a cl�slorby-cl�sler basis, a cluste� bging co�prised of o�e or a plurality of sectors, 5. The method of claim 4 furlbor comPrising determiDitg a n�rEtrer of sectors pe� cl�ster and a bas cl�sler �ddress 226 lo wile the clusters which have boen malched to a 40 when this information is nof �vailable by reading the fil Dreselected destinalioD drive. If lhere are mo�e selected frles system data structures. �t sep 228, the compuler re�eives the user's nexl selection 6, The method ofclsim 5wbcroin determi�itg the number a! stop 230 and loops back to step 212 to repoat the Process. of seclors pe� cluster i�cludes: Refer�iDg now FIG. 11, a layout of a scree� interf�ce for identifyiog by an address for a frsl soctor of each of the the process of FIG. 10 is ill�strated. A �tst .�/indow 232 a5 two frle s'�tem d�ta structures, each of tbo file syslem displays the cluster Dumber of reatotly selected clusteF in a data slruc!�res iDcludi�g iEformatio� for determioing second '��indow 234. The sccood wiDdow displ�ys tbe conls slarling cluster oumber; te�� ofthe end of a last clusle� that has bee� groupod as parl readirg the iDfor�atioD for deter�iniDg the starting clusof a �le preselected by a user, A fo�rth � indow �8 disPlays ler n�mber fo� each of lhe directo�ies; and a map of available clustels by d�1� type for selectio� by the 50 co�paring the starling cl�ste� �umbers and thg address of user Tbe tbird wi�dow 236 displays tho begiDning of lhe the �rsl sectors of the flle system dat� s[�uchrres to contenls a� available cluster chosen by the �ser for comdetermiDe the sectors per cluster. wiDdows displ�y bolh tbe pa�isoD. The second a�d tb�d 7. The motbod of clairo 5 wherein determining the tu�ber values slored iD the �le oo ooe side, aod the symbols or of secto�s per cl�sfer js calculated fo� each di�ectory located characte� e�coded by those val�res basd o� the data tyPe. 55 ir fle system, aDd recoEstructing the hie�arcbical frle storage to ote o� The inve�tion has be�t dgscribed in refg�ence sysle� incl�des dete��i-�itrg a hiorarchical �le structure more exemplaty erDbodimeDts. Modfic�tioDs, s�bstit�tio�s usi�g �le altdbr�te iDfor�ation froE those �le system data rearrangemeDts of thes embodi�gols caD be r�ade and slructures haviDg t�e sa�e sectors pet cl�ster and �ddress wilhout depafi�g f�om the scope of the i�ve�tiot set fo�th cluster sctor ir lh appe�ded claims, The foregoitg detailed descriPtio� 60 for8�e fi�t@othod of the base 5, whe�eio determiniDg the of claim . The is not idended to liml the scope of the iDverltion �o the D��ber of sectors per cl�ster incl�des: D�tiq�lar mbodimeDls set forlh therei�. identiffiog an address for a �rst sector stori�g � �rst wtat is claiEed is: direc�ory aDd aD �ddress for secood sctor storing a for recovering frles, whe�ein the files a�e 1. A method - orga�ized i� a hierarchical directory sΡucture of a� oPeratiDg syste�'s frle systen, from a frrsl sforagc device of a 65 comp�ter when critical file system infomalion is nol. ecoDd directory; readiog from the frrst dirctory ao � sta�ti�g cl�ster n��ber for tbe first directory and from the second us 15 6,173,291 B1 t6 18. Tbe method of clai� 2 whereiD the �le system d�ta structurs iDclude a boot record. 19. The method of clai� 2 wherei�, the frle systm data structures incftde a Palition sec�or; the melhod includes ide�ifyiDg each pa�dtiot seclor; aDd reconslructiDg the hierarcbic�l frle storage systm i�cludes reconstructi�g a hiorarchical �le st�ucruro for each partitio� identifred by a pa�tilion sector. directory a startiDg cluste� ��mber for the secoDd directory; aDd calculati�g the sectors per clusler by dividi�g lhe differetrce of fhe addresss of lhe frrst aDd secood dirgcto�es by the differeoce of the sta.rling clustgr ��mbers of the 5 deter�i�i�g ttie cl�sler b�se addrcss is calcul�ted usitg lbc followhg fonoula, aDd second directory. 9. The method of claim 5 wherein first ca-GiBAd+sectosd>(2xsPc) wherei� CB is tho cluster base address, LBA-, is a� address of the flrst sec�or of the �oot d�e�torf Sctors* is a n��ber of seclo�s i� the root dircclory ��d 10 10. Tt�e method of clairo 5 whreiE determi�i�g the SPC is the sectors pe� cluster. 15 20. The �othod of claim 2 wbo�oi� ideDti�fi�g se�tors co�tai�irg 6le syster� data st�uctures i�cludes identilying a frle systero data st�ucture co�tai�itg cluster allocatio� infor�afio� for files, aDd wherein the method further iDcl�des selecting a �le to bo rcovered fro� the at le�st parti�lly recoDstructed hierarchical �le structure, determi�hg from lhg cl�s�er allocatio� i�forEation wha( clusters coDt�in dat� for lhe sele.led �le, and copyi�g the selecte-d frle. 21. Th method ofcl�im 20wherein fbe cl�rster allocation fuformatio� is stored in a Filo Allocation Table cluster base add�ess itrcl�des: ide�tifyiDg a �rst a�d a sec�nd direclory; determiniDg a stali�g cluster nu�ber for the flrst �nd the 22. Tbe Eethod ofclai�n 20 $�herei� tbe cl�ster allocatio� 20 second d�reclory; information is stored in a Master File Table. calculatiDg the addross of the bas cluster wilh the fol�, A co�puler readablg Eedi�m stori�g inslructio�s for lowiog formula, c��sing a co�puter to pefform a process, wheD those iDslr�ctions are read by fhe coEp�ter, for rgcoveritrg []s �nd cB-(c��xLB{��a-c��xLa^�.)l(c�nfc�� 25 wberein CB is lbg cluster base address, C�,il is a clustet �le slorage syslem usd by ao operati�g system ar�d tbe mass n�mberof the frrsldirec�ory, C/i,z is the cluster n�mber data siorage dovice is divided iDto a plurality ofindividualy of tbo secoDd directory, LBAai.r is a� address of the add�essable blocks, c�lled herein sectors, for storing blocks frrsl seclor of lhe fr�l dircctory aod LBA/,,a is aD ^^ of data, each sgctor baving a� address; the process co�rprisaddress for lbe �rsl sector of lhe second diroctory' ing: 11. The Eethod of claim 4 furtber comPrisingl reading from the mass data storag dovice oD a se,clorrecivi�g a selection of � �le to be recovergd from the al by-scto� basis; least partially reconstructed hierarchical �le st�uctr�e; identifying sectors cont�ining frle system dat� struclures displayi�g in a �rsl wi�dow on a �ser i�lerface lo.lbe Js by compad�g d�� therein to p�edeter�ioed data paF compuliog syslem an e�d porlioD of data from a las� fems aDd/or sig�atures fouod i� data structures of lhe cluster storitg dat� of the selected frle; a�d flle system; displayiDg iD a second wiDdow o� the user iDterface to tbe readi�g the inforEatiot from the ide�tified secto�s; atd computing system a beginnitg portioD ftom � next recoDstructing at least part of the hier�rchic�l flle storage availablg cluster �ot ye! associate.d witb � 40 system based or� itformalio! read ftom the ideDlifred dis?laying 12. Tbo Eethod of clai� 11 turlher compr�iDg seclo�i. i� a third window a list of clusters whicb have trot bee! 24. The computer �eadable medium of claim 23, wherein associatod with a �le a�d di�layiog in a fourth witdow a list the process furlher comprises copying a file listed s�ithiD the of cluste� whicb have beet �ssociated with the solected frle at le�st parlly rocoDstrucled hiorarchical frlo struct�re to a 13. The Eelbod of clai� 4 fulber 4s seco�d mass data storage device. receiqi�g a plu��lily of sclcclioDs for files to be recovered 25. The computer roadable ͡edi�rm of clair� 23, whereitr fro� the at leasl pafially reconslructed bier�chical frl storage oD the mass data slor�ge devic� is alloc�ted fo� structu�ei a�d stori�g �les oD a cluster-by-clusler basis, a cluster being for each file, stali�g with the s�allest file ��d conlinuing comprised of a pluralily of scto�. in order to the l�rgest flle, sequeotially slri�gi�g 50 26, The comp�ter �e�d�ble �edi�m of claim 25, wherein together clusters sto�ing colteDt of the sarDe t)?e as fhe process furtber comprisos determining a number of a koowo starti�g cl�sler uDlil tbg that stored sectors per cl�sler atd a cluster base adil�ess. sequence of clusters store �n �mouf�f of data equal to 27. The co�puter readable �ediun of claim 26, wherein the knowo size of the file. determioi�g the number of sectors per cl�sler includesl 14. Tbe metbod of claiE 2 wberoin the Ele system dat� 55 identiffing by an address fo� a frrst secfor of each of tbe strucfures incl�de at least olg s�b-directory tho subtwo frle system d�la structures, each of the �le system d�ectory havi�g a �sl entry havi�g a� entry storing a �rst data str�ct�res hcludi�g i�formation fo� determini�g predete�r�i!9d data patter� and a st�fing cluster Dumber for its starting cluster oumber; a seco�d entry storiDg a secood the sub-djrectory, atrd readiDg the i�formation for determiDiDg the startiDg cluspredetermi�ed data palterD �od a stafli�g cluster Dumber for �0 ler nrmber for cacb of lh

Disclaimer: Justia Dockets & Filings provides public litigation records from the federal appellate and district courts. These filings and docket sheets should not be considered findings of fact or liability, nor do they necessarily reflect the view of Justia.

Why Is My Information Online?