基于有限狀態機的一種事件重建算法
2007-01-01 00:00:00馬永波陳龍王國胤聶能黎龍
計算機應用研究 2007年6期
摘 要：介紹了運用有限狀態機進行事件重建的理論，利用已搜集到的證據作為限制條件，提出了一種改進的事件重建算法，最后簡要分析了一個案例。實驗結果表明該算法是可行和有效的。
關鍵詞：計算機取證; 事件重建; 有限狀態機
中圖分類號：TP393.08文獻標志碼：A
文章編號：1001-3695(2007)06-0101-03
0 引言
計算機取證［1－3］是運用計算機及其相關科學技術的原理和方法來獲取與計算機相關的證據，以證實某個客觀事實存在的過程。計算機取證技術正在迅速發展，已經在一些領域取得了明顯的進展，如在驗證信息拷貝的工具、專門的信息檢驗和分析工具方面［4－6］，但在支持調查發現準確性的理論方面還很少有人研究。
事件重建是一項調查安全事件中所發生具體事件的重要任務；它在任何安全事件調查中都是一項基本活動，因為調查人員要調查的是發生了什么事和事情是怎樣發生的。Pavel Gladyshev提出了通過有限狀態機［7，8］來進行事件重建的思想，理論上具有較好的可行性。許多數字系統，如數字線路、計算機程序和通信協議均可以在數學上用有限狀態機來描述。首先數字設備從根本上來說都是有限狀態機，狀態是數字設備的基本數據特征，時間上雖然是連續流動的，但在運行時卻是離散的，因為控制計算機設備的時鐘是數字的。至于目前的網絡服務，其絕大多數都是基于TCP/IP協議之上的，而TCP/IP協議本身又是使用有限狀態機來描述其狀態遷移的［9］。由此可見，利用有限狀態機分析數字設備或者協議都是可行的。
基于有限狀態機理論的事件重建方法可以總結如下：數字系統首先被描述為一個有限狀態機，并被看做是一張圖；節點代表可能的系統狀態，箭頭代表可能的狀態轉換。如果犯罪事件發生后發現系統處于某一特定狀態，那么所有可能導致系統進入這一特定狀態的場景或行為均可以通過逆推轉換得到。這就為將有限狀態機理論應用于計算機犯罪事件重建提供了理論依據。
為便于計算機證據的自動化分析和事件重建，Pavel Gla￣dyshev對計算機犯罪調查中所搜集到的計算機證據作出了形式化的劃分［8］，定義了觀察記錄、觀察記錄序列、證據陳述等概念，為事件重建的實現奠定了基礎；但也存在一些不足，如事件重建算法相對簡單，還存在著狀態爆炸問題等，即由于在推理過程中需要求出所有的狀態轉換序列，當在狀態和事件數目較多時將會不可避免地因為占用的存儲空間太大而無法處理。
1 基本概念
1.1 有限狀態機
利用有限狀態機進行數字證據的分析是基于事件的數學模型。形式上，一個數字系統的有限狀態機可以被定義為一個三元組T=（Q，l，Ψ)。這里：
（1）Q是一個關于系統的所有可能狀態的有限集合。
（2）I是一個關于系統的所有可能發生事件的有限集合。
（3）（Ψ:I×Q → Q）是一個轉換函數。這個轉換函數將決定任何一個可能的事件到達某一狀態時將要進入的下一狀態。
1.2 事件—狀態變遷表
2 事件重建算法
2.1 Pavel Gladyshev事件重建算法
Pavel Gladyshev提出的事件重建算法(基本事件重建算法)的主要思想是：首先根據數字系統的特性建立起有限狀態機；然后根據有限狀態機的特性和狀態與事件的關系求出所有的狀態轉換過程集合；最后根據已搜集到的證據所處的狀態，在集合內查找包含所有已搜集證據所處狀態的轉換過程。
2.2 基于路徑搜索的有限狀態機事件重建算法
基于路徑搜索的有限狀態機事件重建算法(改進的事件重建算法)的主要思想是：首先根據被調查系統的轉換關系建立起有限狀態機模型，其運轉過程即是一個狀態間不斷互相轉換的過程；然后從系統的最終狀態開始按照有限狀態機的轉換關系進行逆推；如果所收集到的證據位于逆推的路徑上，便保存此路徑，直至所有的證據均得到解釋為止。下面給出了逆推函數的定義和事件重建過程的詳細描述。
(1)逆推函數的定義
(2)求滿足觀察記錄序列內條件的狀態轉換路徑集
觀察記錄序列是一個非空序列，它以時間為序將觀察記錄列出。非正式地來講，一個觀察記錄序列就代表了一個時間上不間斷的見證者所觀察到的場景。在序列中，下一個觀察記錄緊接前一個觀察記錄的完成而發生。從狀態機的角度來看，觀察記錄序列描述的是那些所有可以被劃分成不同場景片段的狀態轉換；而每一個片段又代表著觀測記錄序列中一個相應的觀察記錄。
由此可見，觀察記錄序列是對系統轉換過程中所滿足部分條件的描述。因此求滿足其條件的路徑的運算過程可以表述為：以系統所處的最終狀態為起點，反復調用逆推函數ψ-1不斷逆推，僅保存那些具有觀察到證據的路徑；逆推的結果繼續作為下一次求逆運算Ψ-1的輸入；依此類推，直到所有的觀察記錄都在路徑上得到解釋為止。
(3)求滿足證據陳述內所有條件的狀態轉換路徑集
一個證據陳述是一個包含對犯罪事件作出不同描述的所有觀察記錄序列的列表。證據陳述將證據形式化為狀態機在犯罪事件發生時所搜集到的觀測記錄，即系統被看成是一個透明的盒子；盒子的狀態和行為對于一些目擊者來講可以被部分地觀測到；每一個目擊證人所觀測到的事實都被看做是在犯罪事件發生時系統所處的狀態，或被觀測特性變換過程中的一個片段。在語法上，證據陳述由觀測記錄序列構成，而觀測記錄序列則由觀測記錄構成。
由以上定義可知，證據陳述包含的是對系統轉換過程所滿足全部條件的描述。因此求滿足證據陳述內所有條件的狀態轉換路徑集的過程可描述為：首先計算滿足觀察記錄序列內條件的路徑集合；然后把各觀察記錄序列的解釋合并進整個證據陳述的集合中去。其實現過程是以第一個運算集合為初始集合；然后在其中求滿足相鄰的后一個觀察記錄序列內條件的路徑集合；直至求得滿足所有觀察記錄序列內的所有條件的路徑集合，即如果有限狀態機按照路徑集合內的轉換過程進行運轉便可產生證據陳述內的全部證據。
(4)算法的復雜度分析
由于本算法主要的操作是建立事件—狀態變遷表和狀態前驅表，在狀態前驅表建立后其逆推函數也主要是通過對前驅表的查找操作來實現逆推的。在運算時僅需保存一張狀態前驅表，即在狀態數為M、事件數為N的情況下，算法的空間復雜度為O(M×N)；而基本事件重建算法由于要求出所有的狀態轉換序列集合，必將占用大量的存儲空間，在相同的情況下其空間復雜度為O(ML)。其中L為狀態轉換序列所含中間狀態的數目。由此可見，本算法的空間復雜度要明顯低于基本事件重建算法的空間復雜度。
3 案例分析
松散空間(Slack Space)是指一個有效文件占用的最后一個簇的末尾的未使用空間。其形成的原因在于文件刪除后系統并不清除被刪除文件所占簇的內容（圖1）。通常松散空間的數據是待刪除文件在新
文件被寫入磁盤后所產生的數據碎片，即是在當前文件之前就已存在的。計算機犯罪事件調查人員通常也是據此來進行推理的。現分析這樣一個關于松散空間的案例［10］：調查取證人員在A的磁盤松散空間發現了帶有恐嚇內容的數據(X文件數據部分)，而該簇的正常數據(Y文件數據部分)是在A外出前形成的。因此調查人員得出結論：是A寫下了包含恐嚇和勒索內容的文件。而A聲稱在其外出期間公司的C可以使用該計算機，并且在此期間該計算機完全處于C控制之下。因此是C在其機器上惡意制造的恐嚇內容文件。
針對此事件的分析過程如下：簇內數據的更改分三種情況，可表示為LENGTH={0，1，2}。0表示簇未被分配；1表示對簇的左部或右部進行了更改；2代表對簇左右兩部分都進行了更改。簇根據存儲的內容分為左右兩部分，其值域分別定義為LEFT_PART={U，T1，O1}和RIGHT_PART={T2， O2}。U表示恐嚇文件的無關內容部分；T1表示在左半空間內被覆蓋了的具有恐嚇的內容；T2表示在右半空間內具有恐嚇的內容；O1表示在左半空間內的其他無關信息；O2表示在右半空間內的其他無關信息。因此事件模型的狀態集合可表示為Q=LENGTH×LEFT_PART×RIGHT_PART。對簇進行的操作事件有三種：文件系統直接對簇進行寫入WRITE、由低級磁盤操作軟件對簇進行直接寫入DIRECT_WRITE和刪除文件DEL。有限狀態機的狀態轉換可描述為在對簇的左部和右部進行以上三種操作的情況下其狀態不斷進行轉換的過程。由基于路徑搜索的有限狀態機事件重建算法可得到若干可能的路徑如圖2所示。
可分別解釋為是由A寫下的恐嚇文件和由A先寫下僅含無關內容的文件再由C在其末尾添加恐嚇內容以陷害A的轉換過程。比如路徑(0，O1，O2)WRITE(U)(1，U，O2)WRITE(T1，T2)(2，T1，T2)WRITE（U）(1，U，T2)的轉換過程即為調查取證人員所認為的由A的操作所形成的帶恐嚇內容的磁盤松散空間形成過程（圖1）；圖2中的轉換過程(0，O1，O2)WRITE(U)(1，U，O2)WRITE(U，T2)(2，U，T2)WRITE(U)(1，U，T2)卻可以解釋為是一種A可能受陷害的場景。其解釋如下：
（1）WRITE（U）：A首先寫下那封與此事件無關的文件；
（2）WRITE（U，T2）：然后C通過磁盤操作軟件在文件的末尾添加恐嚇內容；
（3）WRITE（U）：最后C再恢復原文件在簇開始位置最初的內容，即可形成被調查人員所搜集到的松散空間。
這條解釋盡管對于解釋整個事件的發生過程并不充分，但A的律師卻完全可以用來反駁調查人員的調查結果，即有可能是在A外出期間C在其計算機上偽造的具有恐嚇內容的松散空間。同樣，計算機犯罪調查人員也可以根據這條解釋所給出的狀態轉換過程有目的地搜集更加充分的證據，以解決存在的爭議問題。
4 結束語
由于計算機犯罪調查針對的主要是計算機系統，用有限狀態機對計算機證據進行分析調查和事件重建變得非常便利。針對Pavel Gladyshev提出的有限狀態機事件重建算法存在的不足，本文提出了一種改進的狀態空間搜索算法，并在實驗中取得了較好的實驗效果。
本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。
