亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于多結(jié)構(gòu)信息的FAT文件系統(tǒng)數(shù)據(jù)恢復(fù)算法*

        2010-06-27 02:29:42廖根為
        電信科學(xué) 2010年5期
        關(guān)鍵詞:空閑結(jié)構(gòu)算法

        廖根為

        (華東政法大學(xué)司法鑒定中心 上海 200042)

        當(dāng)計(jì)算機(jī)網(wǎng)絡(luò)中存在入侵行為時(shí),即使入侵痕跡被刪除或破壞,也有可能通過數(shù)據(jù)恢復(fù)手段找到痕跡。在計(jì)算機(jī)司法鑒定中,常需要對被刪除的數(shù)據(jù)文件進(jìn)行數(shù)據(jù)恢復(fù)。

        FAT是一種使用廣泛的文件系統(tǒng),很多操作系統(tǒng)平臺(tái)都支持FAT文件系統(tǒng)。當(dāng)需要對其進(jìn)行數(shù)據(jù)恢復(fù)時(shí)常需要借助數(shù)據(jù)恢復(fù)軟件。筆者在實(shí)踐中發(fā)現(xiàn),目前多數(shù)數(shù)據(jù)恢復(fù)軟件無法成功恢復(fù)非連續(xù)存放的數(shù)據(jù)文件。當(dāng)存在非連續(xù)存放的數(shù)據(jù)文件時(shí),需要進(jìn)行人工分析,既容易出錯(cuò),工作量又大,而且在司法鑒定中,越少人工干預(yù),恢復(fù)出的數(shù)據(jù)越具有客觀性,證據(jù)的可靠性越高,越容易被法院接受。因此,研究與開發(fā)成功率高的數(shù)據(jù)恢復(fù)軟件十分必要。本文充分利用FAT文件系統(tǒng)中FAT表簇分配信息、文件記錄表中起始簇的信息以及文件的創(chuàng)建時(shí)間、修改時(shí)間和最近訪問時(shí)間等信息[1],提出了一種改進(jìn)的數(shù)據(jù)恢復(fù)算法,可以恢復(fù)出大多數(shù)非連續(xù)存放的被刪除的文件,提高了恢復(fù)成功率。

        1 FAT文件系統(tǒng)刪除的原理和數(shù)據(jù)恢復(fù)的思想

        FAT文件系統(tǒng)主要分為 FAT12、FAT16、FAT32幾種文件系統(tǒng),其結(jié)構(gòu)大體相似,均有引導(dǎo)區(qū)、FAT表結(jié)構(gòu)、目錄表結(jié)構(gòu)、數(shù)據(jù)區(qū),但引導(dǎo)區(qū)中BPB表結(jié)構(gòu)、FAT表每一項(xiàng)的大小、根目錄的定位方法有一定差異。另外,在FAT32文件系統(tǒng)中,有一個(gè)FSINFO數(shù)據(jù)結(jié)構(gòu)以及文件的根目錄處在數(shù)據(jù)區(qū)位置[2]。

        FAT文件系統(tǒng)中文件被刪除時(shí) (這里僅指徹底刪除,本文不討論一般刪除情形),內(nèi)容發(fā)生改變的結(jié)構(gòu)為文件目錄表、FAT表、FSINFO結(jié)構(gòu)。其中文件目錄表中對應(yīng)某一文件的短文件名和長文件名項(xiàng)目第一個(gè)字節(jié)被修改成特殊的字符、該文件在FAT表中的簇鏈結(jié)構(gòu)全部清空,備份FAT表中對應(yīng)的簇信息會(huì)相應(yīng)更新。另外,在FAT32文件系統(tǒng)中,當(dāng)刪除一個(gè)文件時(shí),F(xiàn)SINFO結(jié)構(gòu)中下一個(gè)可用的簇的信息會(huì)發(fā)生變化,如果在Windows系統(tǒng)中刪除一個(gè)文件時(shí),文件目錄項(xiàng)的最近訪問時(shí)間也會(huì)進(jìn)行更新,但數(shù)據(jù)區(qū)文件的內(nèi)容沒有發(fā)生任何變化,除非有新的數(shù)據(jù)覆蓋到該文件存儲(chǔ)的區(qū)域。因此,理論上沒有被覆蓋的被刪除的文件是可以被恢復(fù)的[3]。

        目前,比較常見的數(shù)據(jù)恢復(fù)算法有兩類,一類是基于文件系統(tǒng)的數(shù)據(jù)恢復(fù)算法,一種是不依賴文件系統(tǒng),直接依賴文件特征的數(shù)據(jù)恢復(fù)算法。通常后者恢復(fù)的文件較多,但可恢復(fù)文件類型有限,且很多文件恢復(fù)結(jié)果都是錯(cuò)誤的。基于文件系統(tǒng)的數(shù)據(jù)恢復(fù)算法主要依賴目錄結(jié)構(gòu)的信息進(jìn)行數(shù)據(jù)恢復(fù),是目前主流的一種數(shù)據(jù)恢復(fù)算法。采用基于目錄結(jié)構(gòu)信息的數(shù)據(jù)恢復(fù)算法時(shí),由于刪除文件后,目錄結(jié)構(gòu)中對應(yīng)的該文件項(xiàng)目的信息并未被真正地刪除,因此,可以根據(jù)目錄結(jié)構(gòu)中部分文件名信息、文件的起始簇號(hào)、文件的大小等信息,找到數(shù)據(jù)區(qū)對應(yīng)的簇,并從此讀出長度為文件大小的數(shù)據(jù),即為被刪除文件的內(nèi)容。但是此算法成功恢復(fù)文件的前提之一是,待恢復(fù)的被刪除文件必須連續(xù)存放在存儲(chǔ)設(shè)備中[4,5]。

        雖然,F(xiàn)AT文件系統(tǒng)中文件大多數(shù)是連續(xù)存放的,但是,也有一些文件不是連續(xù)存放的。在文件的頭尾之間的連續(xù)簇內(nèi),有一些簇可能已經(jīng)被現(xiàn)有文件占用,有一些是已經(jīng)刪除的其他文件信息,恢復(fù)這些非連續(xù)被刪除的文件對于司法鑒定業(yè)務(wù)來說是十分重要的。如果待恢復(fù)的被刪除文件是完整的,非連續(xù)存放時(shí)現(xiàn)有算法不能成功進(jìn)行數(shù)據(jù)恢復(fù)。為此,需要提出新的算法以改進(jìn)現(xiàn)有算法不能恢復(fù)不連續(xù)存儲(chǔ)文件的缺陷。

        2 FAT文件系統(tǒng)被刪除文件恢復(fù)算法的改進(jìn)

        2.1 被刪除的不連續(xù)文件的形態(tài)

        當(dāng)被刪除文件不連續(xù)時(shí),不連續(xù)部分有可能是已分配空間的現(xiàn)有系統(tǒng)文件存放數(shù)據(jù)的簇,也有可能是曾被刪除文件的簇。而且不連續(xù)空間有可能存在多個(gè),為了研究便利,首先定義某一不連續(xù)文件內(nèi)非本文件的一個(gè)連續(xù)簇段的形態(tài),再推導(dǎo)出各種復(fù)雜的組合。

        2.1.1 實(shí)包

        實(shí)包指的是不連續(xù)文件內(nèi)非屬于本文件數(shù)據(jù)的連續(xù)簇全被現(xiàn)有文件系統(tǒng)中某一個(gè)或多個(gè)文件占用(即該簇段內(nèi)不存在未實(shí)際分配的簇),簡稱R形態(tài),如圖1所示(File1為待恢復(fù)文件,虛線表示文件已被刪除,實(shí)線表示文件未被刪除,以下同)。

        由于R形態(tài)中每一簇都被現(xiàn)有系統(tǒng)文件占有,因此在FAT結(jié)構(gòu)表中均包含非空信息。在數(shù)據(jù)恢復(fù)算法中如果跳開已經(jīng)分配的簇,在進(jìn)行數(shù)據(jù)恢復(fù)時(shí),都可以避開R形態(tài)的干擾。如果待恢復(fù)的被刪除文件中只有R形態(tài)數(shù)據(jù)時(shí),則該文件是完全可以恢復(fù)的。

        2.1.2 虛包

        虛包指的是不連續(xù)文件內(nèi)非屬于本文件數(shù)據(jù)的連續(xù)簇全被已經(jīng)刪除的一個(gè)或多個(gè)文件占有,這些文件是連續(xù)存放的且均為完整的文件或者具備完整的文件信息,簡稱V形態(tài),如圖2所示。

        V形態(tài)存在時(shí),如果V形態(tài)數(shù)據(jù)是待恢復(fù)的被刪除文件之前被刪除的,則V形態(tài)文件不會(huì)出現(xiàn)尾部被待刪除文件覆蓋的情形。如果V形態(tài)數(shù)據(jù)是待恢復(fù)的被刪除文件之后刪除的,則文件不可能被待恢復(fù)的被刪除文件覆蓋。根據(jù)常見的分配算法,也不會(huì)存在待刪除文件被刪除后,V形態(tài)文件跳空覆蓋待刪除文件。因此,當(dāng)V形態(tài)數(shù)據(jù)的起始部分和結(jié)尾部分都處在不連續(xù)文件內(nèi)非屬于本文件數(shù)據(jù)的連續(xù)簇之內(nèi)時(shí),只要在存儲(chǔ)設(shè)備數(shù)據(jù)區(qū)內(nèi)找到確定V形態(tài)文件的信息,則數(shù)據(jù)恢復(fù)可以避開V形態(tài)數(shù)據(jù)的干擾。

        2.1.3 半開

        半開指的是不連續(xù)文件內(nèi)非屬于本文件數(shù)據(jù)的連續(xù)簇全被已經(jīng)刪除的一個(gè)或多個(gè)文件占有,其中存在一個(gè)被刪除的文件其頭部信息不在該連續(xù)區(qū)域內(nèi),或者一個(gè)文件中間或尾部信息不在該連續(xù)區(qū)域內(nèi),簡稱O形態(tài),如圖3所示。

        出現(xiàn)O形態(tài)時(shí),根據(jù)常見的分配算法,O形態(tài)數(shù)據(jù)不可能被待刪除的文件覆蓋,一種常見的情形是,O形態(tài)數(shù)據(jù)與待刪除文件數(shù)據(jù)同時(shí)存在,并相繼被刪除,如果O形態(tài)數(shù)據(jù)半開文件頭能夠在文件目錄表中找到,則文件被恢復(fù)的概率大。如果O形態(tài)數(shù)據(jù)文件尾半開,則表明待恢復(fù)數(shù)據(jù)與被刪除文件過程中有中間文件在該數(shù)據(jù)區(qū)形成,如果中間文件沒有覆蓋待恢復(fù)文件,則文件結(jié)束數(shù)據(jù)區(qū)必然在連續(xù)文件內(nèi),如果新的文件剛好構(gòu)成V形態(tài),則文件可能被恢復(fù),否則較難進(jìn)行恢復(fù)。

        2.1.4 全開

        全開指的是不連續(xù)文件內(nèi)非屬于本文件數(shù)據(jù)的連續(xù)簇全被已經(jīng)刪除的一個(gè)或多個(gè)文件占有,其中存在一個(gè)被刪除的文件其頭部信息不在該連續(xù)區(qū)域內(nèi),同時(shí)一個(gè)文件中間或尾部信息不在該連續(xù)區(qū)域內(nèi),簡稱X形態(tài),如圖4、圖5所示。

        全開X形態(tài)存在時(shí),表明X形態(tài)數(shù)據(jù)所在文件在形成過程中,必然存在中間文件的生成和刪除,且中間文件剛好填充連續(xù)簇內(nèi)剩余的簇,否則不會(huì)形成X形態(tài)。因此恢復(fù)X形態(tài)文件,必須對X形態(tài)內(nèi)數(shù)據(jù)相關(guān)文件進(jìn)行回溯,如果不存在相關(guān)文件的頭部信息或起始簇,則文件難以恢復(fù)。否則,可以通過尋找中間文件信息參照V形態(tài)方法恢復(fù),對一些特殊情況下的文件有可能進(jìn)行恢復(fù)。

        2.1.5 各種形態(tài)的綜合分析

        在一個(gè)不連續(xù)文件所占用的連續(xù)空間內(nèi),存在著若干個(gè)連續(xù)的簇段不屬于本文件。每一個(gè)簇段內(nèi)數(shù)據(jù)形態(tài)可能為上述4種形態(tài)之一,還有可能存在部分簇已經(jīng)分配給現(xiàn)有文件,部分簇處于空閑狀態(tài)。此時(shí),可能存在R+V、R+O、R+X三種組合形式,其中R+V表示在不連續(xù)文件內(nèi)某一連續(xù)簇段內(nèi)存在若干個(gè)已分配的簇被現(xiàn)有文件系統(tǒng)中文件占有,若將這些已經(jīng)分配的簇去除,簇段內(nèi)其他簇構(gòu)成V形態(tài),則稱R+V形態(tài),其他組合類似。因此,對于單獨(dú)的連續(xù)的簇段,可用以下式子表示:

        y={R,V,O,X,R+V,R+O,R+X};

        y表示與被恢復(fù)文件無關(guān)的某一連續(xù)數(shù)據(jù)。所有連續(xù)的簇段可以用下述式子表示:

        Y={R,V,O,X,R+V,R+O,R+X}*;

        其中Y表示待恢復(fù)文件連續(xù)空間中與Y無關(guān)的簇。

        對于某一次數(shù)據(jù)恢復(fù),根據(jù)待恢復(fù)文件存在各種情形分析如下。

        (1)若Y為空集,即被恢復(fù)文件是連續(xù)空間,則可以直接讀出文件。

        (2)若Y中只有R元素,由于R所占用簇段在FAT簇鏈中有完整記錄,因此只要參考FAT表信息,便可成功恢復(fù)文件。

        (3)若Y中只有R、V或R+V,如果V形態(tài)對應(yīng)文件信息在文件記錄表中存在,則V對應(yīng)文件可以恢復(fù),即可以將V占用的簇排除,同理根據(jù)FAT表排除R,則文件也可以成功恢復(fù),但是若V對應(yīng)文件信息在文件目錄表中被覆蓋,則文件不能成功恢復(fù)。

        (4)若Y中存在O,不存在X形態(tài)時(shí),若O頭部半開,表明O文件在待恢復(fù)文件之前形成,且O文件連續(xù)空間中Y部分的文件內(nèi)容在Y形成前剛好是完整的文件。如果不符合,根據(jù)分配算法,不可能存在O半開情形;或者Y文件在其之前形成,形成時(shí),Y文件包含的該連續(xù)簇段是一個(gè)或若干個(gè)完整文件,并且被刪除,刪除后形成O。因此,可以結(jié)合文件目錄表中O形成前刪除文件記錄信息進(jìn)行分析。若存在這樣一個(gè)或幾個(gè)記錄且該記錄成功檢索到,則該文件可以成功恢復(fù),否則無法恢復(fù)。

        (5)若Y中存在 X,則 Y與 X形成先后關(guān)系,且 X、Y不連續(xù)空間文件刪除行為十分復(fù)雜。出現(xiàn)這種情形的可能性十分小。出現(xiàn)的情形類似第4步所述,但X和Y不可能是先后直接形成的,中間伴隨著其他文件的刪除。

        根據(jù)上述5種情況分析可知,如果存儲(chǔ)設(shè)備中某個(gè)未知的待恢復(fù)文件是完整的,則可恢復(fù)的可能性比較大。因?yàn)镕AT中最常見的情形是(1)所述,只有少數(shù)情況下屬于(2)~(5)情形。而少數(shù)情況中最常見的又是(2),其次是(3);(4)與(5)一般只在特殊軟件寫存儲(chǔ)介質(zhì)或者十分特殊的情形時(shí)才會(huì)出現(xiàn),而且也有可能進(jìn)行部分恢復(fù)。因此,可以看出根據(jù)上述思路制定的算法的成功率提高了。

        2.2 改進(jìn)算法核心片段

        根據(jù)上述對不連續(xù)空間文件不同形態(tài)的分析以及恢復(fù)思想,筆者研制了基于多結(jié)構(gòu)信息的數(shù)據(jù)恢復(fù)算法,其核心片段描述如下:

        /*在文件目錄表FDT中,查找被刪除文件fileName起始簇的簇號(hào)k

        */

        k=getFirstCluster(FDT,fileName);

        /*根據(jù)文件目錄表FDT中文件fileName的大小等信息,計(jì)算出其所占用簇的數(shù)目M

        */

        M=getClusters(FDT,fileName);

        /*如果該文件fileName起始簇k非空閑,表明該文件已被覆蓋,無法恢復(fù),返回錯(cuò)誤

        */

        if(!isIdleCluster(k))return ERROR;

        /*M個(gè)元素的數(shù)組C存放文件fileName占用的所有簇號(hào),C[0]存放起始簇號(hào)k

        */

        C[0]=k;

        k=k+1;

        for(i=1;i

        {

        //循環(huán)查找到下一個(gè)空閑簇的簇號(hào)

        while(!isIdleCluster(k)){k=k+1;}

        switch(getCases(FDT,k)){

        /*函數(shù)getCases判定空閑簇k是否為其他刪除文件的起始簇號(hào);

        返回值0,表明該空閑簇k不是其他刪除文件的起始簇號(hào);

        返回值1,表明該空閑簇k曾為其他刪除文件的起始簇號(hào),該刪除文件創(chuàng)建在先,刪除可能在先也可能在后,恢復(fù)時(shí)跳過該刪除文件所占用的所有空閑簇;

        返回值2,表明該空閑簇k曾為其他刪除文件的起始簇號(hào),且該刪除文件創(chuàng)建在后,其覆蓋了文件fileName,而此后其自身亦被刪除。

        */

        //空閑簇k不是其他刪除文件的起始簇號(hào)

        case 0:C[i]=k;

        k=k+1;

        break;

        /*空閑簇k曾為其他非覆蓋刪除文件的起始簇號(hào);跳過其他非覆蓋的刪除文件所占用的簇;定位文件fileName下一個(gè)空閑簇

        */

        case 1:k=getNextFreeCluster(k);

        break;

        /*空閑簇k曾為其他覆蓋刪除文件的起始簇號(hào)文件無法恢復(fù),返回錯(cuò)誤信息

        */

        case 2:return ERROR;

        }

        }

        //讀出被刪除文件所占用簇的數(shù)據(jù)

        return readClusters(C);

        上述改進(jìn)算法的核心片段最終可讀出被刪除文件所占用簇的數(shù)據(jù),再根據(jù)刪除文件的大小,便可恢復(fù)被刪除文件。在進(jìn)行數(shù)據(jù)恢復(fù)時(shí),首先需要定位被刪除的文件目錄。定位被刪除的文件目錄,依據(jù)該文件的短文件名目錄確定;當(dāng)在目錄項(xiàng)中確定了文件大小后,根據(jù)引導(dǎo)扇區(qū)中每簇扇區(qū)數(shù)信息可以確定文件內(nèi)容占用的簇空間。在讀數(shù)據(jù)區(qū)內(nèi)容時(shí),讀取的是空閑簇的數(shù)據(jù)信息,這樣可以完全避免R形態(tài)、R+V形態(tài)、R+O形態(tài)、R+X形態(tài)中R數(shù)據(jù)的干擾。判斷刪除在先時(shí),綜合根據(jù)文件創(chuàng)建時(shí)間、最近訪問時(shí)間(如果在Windows平臺(tái)刪除文件,最近訪問時(shí)間會(huì)更新)等信息進(jìn)行綜合判斷,以確定刪除先后和覆蓋關(guān)系。算法能恢復(fù)大多數(shù)未覆蓋的被刪除文件。

        3 改進(jìn)算法的性能分析

        傳統(tǒng)的恢復(fù)算法能很好地恢復(fù)連續(xù)存儲(chǔ)的被徹底刪除的文件數(shù)據(jù),在此基礎(chǔ)上,改進(jìn)的算法還能較好地恢復(fù)非連續(xù)存儲(chǔ)的被刪除的文件數(shù)據(jù)。如果待恢復(fù)的非連續(xù)存儲(chǔ)的刪除文件所在的簇空間內(nèi),僅包括該被刪除文件和其他未被刪除文件,則該待恢復(fù)文件可以被恢復(fù)。如果待恢復(fù)的非連續(xù)存儲(chǔ)文件所在的簇空間內(nèi),同時(shí)包括有其他連續(xù)存儲(chǔ)的被刪除文件,只要其他文件的創(chuàng)建時(shí)間在先、刪除在后,也就是待恢復(fù)文件數(shù)據(jù)非被覆蓋,待恢復(fù)文件依然可以被完全恢復(fù)。而且該算法適合不同平臺(tái)下刪除的FAT文件系統(tǒng)文件的恢復(fù)??傊撍惴ū容^適合應(yīng)用于司法鑒定業(yè)務(wù),特別當(dāng)需要對特定文件進(jìn)行數(shù)據(jù)恢復(fù)時(shí),性能更佳。

        1 Microsoft MSDN library.File system behavior overview,http://download.microsoft.com/download/4/3/8/43889780-8d45-4b2e-9d3a-c696a890309f/File%20System%20Behavior%20Overview.pdf,2009-10-8

        2 Brian C.File system forensic analysis.Boston:Addison Wesley Professional,2005

        3 戴士劍,涂彥暉.數(shù)據(jù)恢復(fù)技術(shù)(第2版).北京:電子工業(yè)出版社,2007

        4 章華,劉乃琦,郭建東.基于孩子兄弟樹的FAT32文件刪除恢復(fù)算法.計(jì)算機(jī)應(yīng)用研究,2009(3):1116~1118

        5 鐘秀玉.基于FAT32的數(shù)據(jù)恢復(fù)系統(tǒng)的設(shè)計(jì).計(jì)算機(jī)應(yīng)用與軟件,2008(11):56~57

        6 王中杉,劉乃琦等.基于FAT32文件系統(tǒng)的取證研究與實(shí)現(xiàn).計(jì)算機(jī)工程,2009(9):176~178

        猜你喜歡
        空閑結(jié)構(gòu)算法
        恩賜
        詩選刊(2023年7期)2023-07-21 07:03:38
        《形而上學(xué)》△卷的結(jié)構(gòu)和位置
        論結(jié)構(gòu)
        中華詩詞(2019年7期)2019-11-25 01:43:04
        基于MapReduce的改進(jìn)Eclat算法
        “鳥”字謎
        小讀者之友(2019年9期)2019-09-10 07:22:44
        Travellng thg World Full—time for Rree
        進(jìn)位加法的兩種算法
        彪悍的“寵”生,不需要解釋
        論《日出》的結(jié)構(gòu)
        一種改進(jìn)的整周模糊度去相關(guān)算法
        亚洲综合久久成人a片| 国产av一级黄一区二区三区| 国产freesexvideos中国麻豆 | 呻吟国产av久久一区二区| 精品国免费一区二区三区| 日本办公室三级在线观看| 99精品视频69v精品视频| 日本边添边摸边做边爱的网站 | 国产三级自拍视频在线| 中文字幕第一页人妻丝袜| 少妇粉嫩小泬喷水视频www| 亚洲AV无码一区二区三区人| 精品人妻中文字幕一区二区三区| 国产自产二区三区精品| 精品国产一二三产品区别在哪| 国产一区曰韩二区欧美三区| 精品女同一区二区三区在线播放器 | 亚洲av第一区综合激情久久久| 偷拍一区二区三区四区| 国产婷婷色综合av蜜臀av| 巨爆乳中文字幕爆乳区| 青青草久久久亚洲一区| 欧美黑人又粗又大xxxx| 人人妻人人爽人人做夜欢视频九色 | 国产成人一区二区三区影院免费| 国产高潮迭起久久av| 国产精品亚洲lv粉色| 欧美自拍视频在线| 亚洲国产免费一区二区| 国产女人18毛片水真多18精品| 日日碰狠狠躁久久躁9| 欧美zozo另类人禽交| 国产精品成人自拍在线观看| 欧美性受xxxx狂喷水| 天天躁日日操狠狠操欧美老妇| 亚洲激情视频在线观看a五月| 日日摸日日碰人妻无码| 国内精品久久久久久久影视麻豆| 亚洲综合久久一本久道| 痴汉电车中文字幕在线| 国产xxxx99真实实拍|