基于有限狀態(tài)機的一種事件重建算法

摘 要：介紹了運用有限狀態(tài)機進行事件重建的理論，利用已搜集到的證據(jù)作為限制條件，提出了一種改進的事件重建算法，最后簡要分析了一個案例。實驗結(jié)果表明該算法是可行和有效的。

關(guān)鍵詞：計算機取證; 事件重建; 有限狀態(tài)機

中圖分類號：TP393.08文獻標志碼：A

文章編號：1001-3695(2007)06-0101-03

0 引言

計算機取證［1－3］是運用計算機及其相關(guān)科學技術(shù)的原理和方法來獲取與計算機相關(guān)的證據(jù)，以證實某個客觀事實存在的過程。計算機取證技術(shù)正在迅速發(fā)展，已經(jīng)在一些領(lǐng)域取得了明顯的進展，如在驗證信息拷貝的工具、專門的信息檢驗和分析工具方面［4－6］，但在支持調(diào)查發(fā)現(xiàn)準確性的理論方面還很少有人研究。

事件重建是一項調(diào)查安全事件中所發(fā)生具體事件的重要任務；它在任何安全事件調(diào)查中都是一項基本活動，因為調(diào)查人員要調(diào)查的是發(fā)生了什么事和事情是怎樣發(fā)生的。Pavel Gladyshev提出了通過有限狀態(tài)機［7，8］來進行事件重建的思想，理論上具有較好的可行性。許多數(shù)字系統(tǒng)，如數(shù)字線路、計算機程序和通信協(xié)議均可以在數(shù)學上用有限狀態(tài)機來描述。首先數(shù)字設備從根本上來說都是有限狀態(tài)機，狀態(tài)是數(shù)字設備的基本數(shù)據(jù)特征，時間上雖然是連續(xù)流動的，但在運行時卻是離散的，因為控制計算機設備的時鐘是數(shù)字的。至于目前的網(wǎng)絡服務，其絕大多數(shù)都是基于TCP/IP協(xié)議之上的，而TCP/IP協(xié)議本身又是使用有限狀態(tài)機來描述其狀態(tài)遷移的［9］。由此可見，利用有限狀態(tài)機分析數(shù)字設備或者協(xié)議都是可行的。 

基于有限狀態(tài)機理論的事件重建方法可以總結(jié)如下：數(shù)字系統(tǒng)首先被描述為一個有限狀態(tài)機，并被看做是一張圖；節(jié)點代表可能的系統(tǒng)狀態(tài)，箭頭代表可能的狀態(tài)轉(zhuǎn)換。如果犯罪事件發(fā)生后發(fā)現(xiàn)系統(tǒng)處于某一特定狀態(tài)，那么所有可能導致系統(tǒng)進入這一特定狀態(tài)的場景或行為均可以通過逆推轉(zhuǎn)換得到。這就為將有限狀態(tài)機理論應用于計算機犯罪事件重建提供了理論依據(jù)。

為便于計算機證據(jù)的自動化分析和事件重建，Pavel Gla￣dyshev對計算機犯罪調(diào)查中所搜集到的計算機證據(jù)作出了形式化的劃分［8］，定義了觀察記錄、觀察記錄序列、證據(jù)陳述等概念，為事件重建的實現(xiàn)奠定了基礎；但也存在一些不足，如事件重建算法相對簡單，還存在著狀態(tài)爆炸問題等，即由于在推理過程中需要求出所有的狀態(tài)轉(zhuǎn)換序列，當在狀態(tài)和事件數(shù)目較多時將會不可避免地因為占用的存儲空間太大而無法處理。

1 基本概念

1.1 有限狀態(tài)機

利用有限狀態(tài)機進行數(shù)字證據(jù)的分析是基于事件的數(shù)學模型。形式上，一個數(shù)字系統(tǒng)的有限狀態(tài)機可以被定義為一個三元組T=（Q，l，Ψ)。這里：

（1）Q是一個關(guān)于系統(tǒng)的所有可能狀態(tài)的有限集合。 

（2）I是一個關(guān)于系統(tǒng)的所有可能發(fā)生事件的有限集合。

（3）（Ψ:I×Q → Q）是一個轉(zhuǎn)換函數(shù)。這個轉(zhuǎn)換函數(shù)將決定任何一個可能的事件到達某一狀態(tài)時將要進入的下一狀態(tài)。

1.2 事件—狀態(tài)變遷表

2 事件重建算法

2.1 Pavel Gladyshev事件重建算法

Pavel Gladyshev提出的事件重建算法(基本事件重建算法)的主要思想是：首先根據(jù)數(shù)字系統(tǒng)的特性建立起有限狀態(tài)機；然后根據(jù)有限狀態(tài)機的特性和狀態(tài)與事件的關(guān)系求出所有的狀態(tài)轉(zhuǎn)換過程集合；最后根據(jù)已搜集到的證據(jù)所處的狀態(tài)，在集合內(nèi)查找包含所有已搜集證據(jù)所處狀態(tài)的轉(zhuǎn)換過程。

2.2 基于路徑搜索的有限狀態(tài)機事件重建算法

基于路徑搜索的有限狀態(tài)機事件重建算法(改進的事件重建算法)的主要思想是：首先根據(jù)被調(diào)查系統(tǒng)的轉(zhuǎn)換關(guān)系建立起有限狀態(tài)機模型，其運轉(zhuǎn)過程即是一個狀態(tài)間不斷互相轉(zhuǎn)換的過程；然后從系統(tǒng)的最終狀態(tài)開始按照有限狀態(tài)機的轉(zhuǎn)換關(guān)系進行逆推；如果所收集到的證據(jù)位于逆推的路徑上，便保存此路徑，直至所有的證據(jù)均得到解釋為止。下面給出了逆推函數(shù)的定義和事件重建過程的詳細描述。

(1)逆推函數(shù)的定義

(2)求滿足觀察記錄序列內(nèi)條件的狀態(tài)轉(zhuǎn)換路徑集 

觀察記錄序列是一個非空序列，它以時間為序?qū)⒂^察記錄列出。非正式地來講，一個觀察記錄序列就代表了一個時間上不間斷的見證者所觀察到的場景。在序列中，下一個觀察記錄緊接前一個觀察記錄的完成而發(fā)生。從狀態(tài)機的角度來看，觀察記錄序列描述的是那些所有可以被劃分成不同場景片段的狀態(tài)轉(zhuǎn)換；而每一個片段又代表著觀測記錄序列中一個相應的觀察記錄。

由此可見，觀察記錄序列是對系統(tǒng)轉(zhuǎn)換過程中所滿足部分條件的描述。因此求滿足其條件的路徑的運算過程可以表述為：以系統(tǒng)所處的最終狀態(tài)為起點，反復調(diào)用逆推函數(shù)ψ-1不斷逆推，僅保存那些具有觀察到證據(jù)的路徑；逆推的結(jié)果繼續(xù)作為下一次求逆運算Ψ-1的輸入；依此類推，直到所有的觀察記錄都在路徑上得到解釋為止。

(3)求滿足證據(jù)陳述內(nèi)所有條件的狀態(tài)轉(zhuǎn)換路徑集

一個證據(jù)陳述是一個包含對犯罪事件作出不同描述的所有觀察記錄序列的列表。證據(jù)陳述將證據(jù)形式化為狀態(tài)機在犯罪事件發(fā)生時所搜集到的觀測記錄，即系統(tǒng)被看成是一個透明的盒子；盒子的狀態(tài)和行為對于一些目擊者來講可以被部分地觀測到；每一個目擊證人所觀測到的事實都被看做是在犯罪事件發(fā)生時系統(tǒng)所處的狀態(tài)，或被觀測特性變換過程中的一個片段。在語法上，證據(jù)陳述由觀測記錄序列構(gòu)成，而觀測記錄序列則由觀測記錄構(gòu)成。

由以上定義可知，證據(jù)陳述包含的是對系統(tǒng)轉(zhuǎn)換過程所滿足全部條件的描述。因此求滿足證據(jù)陳述內(nèi)所有條件的狀態(tài)轉(zhuǎn)換路徑集的過程可描述為：首先計算滿足觀察記錄序列內(nèi)條件的路徑集合；然后把各觀察記錄序列的解釋合并進整個證據(jù)陳述的集合中去。其實現(xiàn)過程是以第一個運算集合為初始集合；然后在其中求滿足相鄰的后一個觀察記錄序列內(nèi)條件的路徑集合；直至求得滿足所有觀察記錄序列內(nèi)的所有條件的路徑集合，即如果有限狀態(tài)機按照路徑集合內(nèi)的轉(zhuǎn)換過程進行運轉(zhuǎn)便可產(chǎn)生證據(jù)陳述內(nèi)的全部證據(jù)。

(4)算法的復雜度分析

由于本算法主要的操作是建立事件—狀態(tài)變遷表和狀態(tài)前驅(qū)表，在狀態(tài)前驅(qū)表建立后其逆推函數(shù)也主要是通過對前驅(qū)表的查找操作來實現(xiàn)逆推的。在運算時僅需保存一張狀態(tài)前驅(qū)表，即在狀態(tài)數(shù)為M、事件數(shù)為N的情況下，算法的空間復雜度為O(M×N)；而基本事件重建算法由于要求出所有的狀態(tài)轉(zhuǎn)換序列集合，必將占用大量的存儲空間，在相同的情況下其空間復雜度為O(ML)。其中L為狀態(tài)轉(zhuǎn)換序列所含中間狀態(tài)的數(shù)目。由此可見，本算法的空間復雜度要明顯低于基本事件重建算法的空間復雜度。

3 案例分析

松散空間(Slack Space)是指一個有效文件占用的最后一個簇的末尾的未使用空間。其形成的原因在于文件刪除后系統(tǒng)并不清除被刪除文件所占簇的內(nèi)容（圖1）。通常松散空間的數(shù)據(jù)是待刪除文件在新

文件被寫入磁盤后所產(chǎn)生的數(shù)據(jù)碎片，即是在當前文件之前就已存在的。計算機犯罪事件調(diào)查人員通常也是據(jù)此來進行推理的。現(xiàn)分析這樣一個關(guān)于松散空間的案例［10］：調(diào)查取證人員在A的磁盤松散空間發(fā)現(xiàn)了帶有恐嚇內(nèi)容的數(shù)據(jù)(X文件數(shù)據(jù)部分)，而該簇的正常數(shù)據(jù)(Y文件數(shù)據(jù)部分)是在A外出前形成的。因此調(diào)查人員得出結(jié)論：是A寫下了包含恐嚇和勒索內(nèi)容的文件。而A聲稱在其外出期間公司的C可以使用該計算機，并且在此期間該計算機完全處于C控制之下。因此是C在其機器上惡意制造的恐嚇內(nèi)容文件。

針對此事件的分析過程如下：簇內(nèi)數(shù)據(jù)的更改分三種情況，可表示為LENGTH={0，1，2}。0表示簇未被分配；1表示對簇的左部或右部進行了更改；2代表對簇左右兩部分都進行了更改。簇根據(jù)存儲的內(nèi)容分為左右兩部分，其值域分別定義為LEFT_PART={U，T1，O1}和RIGHT_PART={T2， O2}。U表示恐嚇文件的無關(guān)內(nèi)容部分；T1表示在左半空間內(nèi)被覆蓋了的具有恐嚇的內(nèi)容；T2表示在右半空間內(nèi)具有恐嚇的內(nèi)容；O1表示在左半空間內(nèi)的其他無關(guān)信息；O2表示在右半空間內(nèi)的其他無關(guān)信息。因此事件模型的狀態(tài)集合可表示為Q=LENGTH×LEFT_PART×RIGHT_PART。對簇進行的操作事件有三種：文件系統(tǒng)直接對簇進行寫入WRITE、由低級磁盤操作軟件對簇進行直接寫入DIRECT_WRITE和刪除文件DEL。有限狀態(tài)機的狀態(tài)轉(zhuǎn)換可描述為在對簇的左部和右部進行以上三種操作的情況下其狀態(tài)不斷進行轉(zhuǎn)換的過程。由基于路徑搜索的有限狀態(tài)機事件重建算法可得到若干可能的路徑如圖2所示。

可分別解釋為是由A寫下的恐嚇文件和由A先寫下僅含無關(guān)內(nèi)容的文件再由C在其末尾添加恐嚇內(nèi)容以陷害A的轉(zhuǎn)換過程。比如路徑(0，O1，O2)WRITE(U)(1，U，O2)WRITE(T1，T2)(2，T1，T2)WRITE（U）(1，U，T2)的轉(zhuǎn)換過程即為調(diào)查取證人員所認為的由A的操作所形成的帶恐嚇內(nèi)容的磁盤松散空間形成過程（圖1）；圖2中的轉(zhuǎn)換過程(0，O1，O2)WRITE(U)(1，U，O2)WRITE(U，T2)(2，U，T2)WRITE(U)(1，U，T2)卻可以解釋為是一種A可能受陷害的場景。其解釋如下：

（1）WRITE（U）：A首先寫下那封與此事件無關(guān)的文件；

（2）WRITE（U，T2）：然后C通過磁盤操作軟件在文件的末尾添加恐嚇內(nèi)容；

（3）WRITE（U）：最后C再恢復原文件在簇開始位置最初的內(nèi)容，即可形成被調(diào)查人員所搜集到的松散空間。

這條解釋盡管對于解釋整個事件的發(fā)生過程并不充分，但A的律師卻完全可以用來反駁調(diào)查人員的調(diào)查結(jié)果，即有可能是在A外出期間C在其計算機上偽造的具有恐嚇內(nèi)容的松散空間。同樣，計算機犯罪調(diào)查人員也可以根據(jù)這條解釋所給出的狀態(tài)轉(zhuǎn)換過程有目的地搜集更加充分的證據(jù)，以解決存在的爭議問題。

4 結(jié)束語

由于計算機犯罪調(diào)查針對的主要是計算機系統(tǒng)，用有限狀態(tài)機對計算機證據(jù)進行分析調(diào)查和事件重建變得非常便利。針對Pavel Gladyshev提出的有限狀態(tài)機事件重建算法存在的不足，本文提出了一種改進的狀態(tài)空間搜索算法，并在實驗中取得了較好的實驗效果。

本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。