人工免疫行為輪廓取證分析方法

楊 珺，曹 陽,2，馬秦生，王 敏

(1. 武漢大學電子信息學院 武漢 430079; 2. 武漢大學軟件工程國家重點實驗室 武漢 430072;3. 通信指揮學院二系 武漢 430010)

人工免疫行為輪廓取證分析方法

楊 珺1，曹 陽1,2，馬秦生1，王 敏3

(1. 武漢大學電子信息學院 武漢 430079; 2. 武漢大學軟件工程國家重點實驗室 武漢 430072;3. 通信指揮學院二系 武漢 430010)

針對當前數據挖掘取證分析方法存在的取證分析效率低的問題，提出了采用免疫克隆算法來構建頻繁長模式行為輪廓的取證分析方法。該方法以行為數據和頻繁項集的候選模式分別作為抗原和抗體，以抗原對抗體的支持度作為親和度函數，以關鍵屬性作為約束條件，以最小支持度作為篩選條件，通過對抗體進行免疫克隆操作來構建基于頻繁長模式的行為輪廓；采用審計數據遍歷行為輪廓匹配對比的分析方法來檢測異常數據。實驗結果表明，與基于Apriori-CGA算法的取證分析方法相比，該方法的行為輪廓建立時間和異常數據檢測時間均大幅降低。該方法有助于提高取證分析的效率以及確立重點調查取證的范圍。

人工免疫; 行為輪廓; 計算機取證; 計算機安全; 數據挖掘; 電子犯罪對策; 信息分析; 模式匹配

目前，針對行為數據的取證分析主要采用的是異常檢測法。該方法通過構造行為輪廓，繼而檢測審計數據和行為輪廓間的偏差獲取證據分布的范圍[1-2]。通常，構造行為輪廓需要分析大量的行為數據[3]，因此關聯規則挖掘技術被應用于取證分析中。當前，在該領域，實現該技術主要基于Apriori及其改進算法，如文獻[4]針對行為數據取證分析提出的Apriori-CGA(criminal behavior profiling generation algorithm)算法，該種算法通過挖掘訓練數據的頻繁模式構造行為輪廓[4-6]，但由于取證分析過程的時間開銷較大，致使取證分析的效率較低，表現為：(1)算法收斂速度慢，導致行為輪廓建立時間較長；(2)算法輸出無趣模式多，導致行為輪廓規模較大，異常數據檢測時間較長。

針對以上問題，本文提出人工免疫行為輪廓的取證分析方法。該方法采用免疫克隆算法挖掘訓練數據的頻繁模式，以加快算法的收斂速度，減少行為輪廓的建立時間；通過設定關鍵屬性來阻止無趣模式的產生，并通過挖掘頻繁長模式進一步壓縮行為輪廓的規模，以加快異常數據檢測的速度。

1 人工免疫行為輪廓取證分析原理

人工免疫行為輪廓取證分析主要分為行為輪廓構造和異常數據檢測兩個階段。行為輪廓構造指在安全隔離的環境下，基于正常的訓練數據構造用戶行為模式的過程，即是以關鍵屬性作為約束條件，以最小支持度作為篩選條件，采用免疫克隆算法從預處理后的訓練數據中挖掘頻繁長模式的過程，其規模取決于其包含模式的數量；異常數據檢測指將行為輪廓和預處理后的審計數據進行比較，查找出兩者間相異的數據集，即可疑數據集，從而確定證據可能分布范圍的過程。圖1給出了人工免疫行為輪廓取證分析的原理框圖。

圖1 人工免疫行為輪廓取證分析原理

1.1 數據預處理

1.2 行為輪廓構造

行為輪廓采用帶關鍵屬性約束的免疫克隆算法來構造。免疫克隆是人工免疫系統理論的重要學說，免疫克隆算法具有收斂速度快、全局和局部搜索能力強的特點[7-9]，因此可以快速地實現頻繁模式的挖掘[10]。

圖2 證據分布圖

為最大限度地壓縮行為輪廓的規模，行為輪廓采用頻繁長模式構成。在圖2中，設Sp為行為輪廓的行為特征集，Sa為審計數據的行為數據集，Se為證據分布的可疑數據集，則有：

由式(1)可見，當Sa確定時，為縮小Se以降低誤檢率，應盡可能地增大Sp，即增大行為輪廓的規模。但是，過大的輪廓規模會增加審計數據和行為輪廓間的比對次數，導致異常數據檢測時間開銷增大。由于頻繁項集的所有非空子集都是頻繁的[10,12]，因此可以將頻繁模式合并刪減，行為輪廓就可以僅由包含了所有頻繁模式特征信息的頻繁長模式構成，從而達到在縮小行為輪廓規模但不增加誤檢率的情況下，減少異常數據檢測時間的目的。

1.3 異常數據檢測

即在異常數據檢測時，不滿足上述條件的審計數據將被收集到可疑數據集中。

2 行為輪廓構造算法

行為輪廓采用免疫克隆算法構造，該算法以行為數據和頻繁項集的候選模式分別作為抗原和抗體，以抗原對抗體的支持度作為親和度函數，以關鍵屬性作為約束條件，對抗體進行克隆、變異、重組和選擇操作，形成新一代抗體[13]；以最小支持度min_sup作為篩選條件，從抗體中輸出頻繁長模式。

2.1 親和度函數

親和度指抗原和抗體匹配的程度，親和度的大小由親和度函數度量。在免疫克隆算法中，抗體的支持度指抗原中包含抗體的數量與抗原總數之比，說明了抗體在抗原中的代表性，大小反映了抗體成為頻繁模式可能性的大小[10]。因此，在行為輪廓構造中，可選用抗體的支持度作為親和度函數。設sup(Ai)為抗體 Ai的支持度， f (Ai)為抗體 Ai的親和度函數，則 f (Ai)=sup(Ai)。

2.2 克隆操作

2.3 克隆變異

2.4 克隆重組

2.5 克隆選擇

2.6 算法流程

行為輪廓構造的算法流程如圖3所示。初始抗體種群A(0)是從抗原集中隨機生成的，隨機抽取抗原集中的一個抗原，并隨機置0該抗原的若干屬性位便可得到了一個初始抗體。若A(0)中無相同個體，則添加該抗體到A(0)中，重復以上操作，直到種群規模滿足要求。算法終止操作的條件是克隆代數達到初始設定值k或連續若干代操作無新的頻繁長模式輸出。

圖3 行為輪廓構造算法流程圖

3 實驗結果及分析

實驗數據選自文獻[14]的數據文件lbl-conn-7.tar.Z，該組數據共有9個屬性，反映了勞倫斯-伯克利實驗室(Lawrence-Berkeley laboratory)30天的TCP連接情況。選取protocol和remote host作為關鍵屬性項，以使行為輪廓能夠反映用戶在網絡連接中的行為。順序截取用戶1的10 000條正常連接記錄作為訓練數據；隨機截取用戶1剩余記錄中的5 000條記錄作為審計數據。設k=1 000，N=300，Nc=900，=1，pc=0.5，min_sup分別為10%、5%、1%、0.5%和0.1%、0.05%和0.01%。

表1列出了在上述條件下Apriori-CGA算法(方法1)和無約束的免疫克隆算法(方法2)挖掘出的頻繁模式數目，以及帶約束的免疫克隆算法(方法3)挖掘出的頻繁長模式數目；圖4描述了在上述條件下方法1和方法3的運行時間隨最小支持度在常用對數坐標下的變化趨勢。分析表和圖中的信息(10次操作的平均值)可以得到以下結果：

(1)min_sup應合理選取。

min_sup選取過大，會抑止有趣模式的產生，導致行為輪廓模型不完整，證據的分布范圍過寬，取證分析誤檢率增大；而min_sup選取過小，算法提取的模式數量會急劇增加，如min_ s up =0.01%時，相當比例的輸出模式是偶然行為產生的，它們并不具有行為特征性，導致異常數據檢測時間增長，取證分析效率降低。

(2)免疫克隆算法較Apriori-CGA算法提取的頻繁模式數目略少，但其運行效率卻遠高于后者。

Apriori-CGA算法采用逐層搜索迭代的方法尋找頻繁項集，即用遞推的方法由頻繁i?1項集產生i項集[10]，盡管能夠生成所有的頻繁模式，然而其運算量卻較大；而免疫克隆算法采用多點和隨機的群體搜索方法來尋找頻繁項集，能夠快速地收斂于全局最優解[9-10]。由圖4可知，免疫克隆算法的收斂時間遠低于Apriori-CGA算法的收斂時間，即采用免疫克隆算法可以極大地減小行為輪廓的建立時間。

(3)采用帶關鍵屬性約束的頻繁長模式挖掘算法，可以極大地濾除無趣模式和冗余模式，減小行為輪廓的規模，提高異常數據檢測的效率。

表1 各種方法挖掘出的頻繁(長)模式數目

圖4 算法運行時間和最小支持度的關系

假設每個屬性均為布爾型，則由n個屬性決定的所有可能的模式數量為：

表2 異常數據檢測結果

分析表中的信息可以得到以下結果：Apriori-CGA算法理論上能夠完全提取訓練數據的頻繁模式，然而由于訓練數據集規模有限，由訓練數據構造的行為輪廓并非是完備的，因此，審計數據中就可能含有行為輪廓未能覆蓋的正常模式，從而導致誤檢率不為0。從表中可以看出，與基于Apriori-CGA算法的取證分析方法相比，人工免疫行為輪廓取證分析方法的可疑數據規模稍大、誤檢率也稍高，然而檢測時間卻有了大幅度的降低。因此人工免疫行為輪廓取證分析方法能夠在很好體現基于Apriori-CGA算法的取證分析方法主要功能特性的基礎上，大幅度地提高取證分析的效率。

4 結 論

取證分析是從海量的數據中獲取計算機犯罪證據的技術，是計算機取證技術中最重要的環節。本文通過分析取證數據的特點，提出了人工免疫行為輪廓取證分析方法。該方法充分利用了免疫克隆算法收斂速度快、全局及局部搜索能力強、關鍵屬性對取證數據性質約束能力較強，以及頻繁長模式對數據檢測空間壓縮能力較強的特點，實現了行為輪廓的準確、快速、高效構建，以及異常數據的快速檢測。仿真實驗表明，該方法能有效地提高取證分析的效率和確立重點調查取證的范圍。

[1]PEISERT S, BISHOP M, KARIN S, et al. Analysis of computer intrusions using sequences of function calls[J]. IEEE Trans on Dependable and Secure Computing, 2007, 4(2): 137-150.

[2]MA Xin-xin, ZHAO Yang, QIN Zhi-guang. Improving resilience against DDoS attack in unstructured P2P networks[J]. Journal of Electronic Science and Technology of China, 2007, 5(1): 18-22.

[3]HERRERIAS J, GOMEZ R. A log correlation model to support the evidence search process in a forensic investigation[C]// Proceedings of the Second International Workshop on Systematic Approaches to Digital Forensic Engineering. New York: IEEE Computer Society Press,2007: 31-42.

[4]孫 波. 計算機取證方法關鍵問題研究[D]. 北京: 中國科學院軟件研究所, 2004.

SUN Bo. Research on key aspects of computer forensic methods[D]. Beijing: Institute of Software of Chinese Academy of Sciences, 2004.

[5]ABRAHAM T, VEL O. Investigative profiling with computer forensic log data and association rules[C]//Proceedings of the 2002 IEEE International Conference on Data Mining. New York: IEEE Computer Society Press,2002: 11-18.

[6]ABRAHAM T. Event sequence mining to develop profiles for computer forensic investigation purposes[C]//Proceedings of the 2006 Australasian workshops on Grid computing and e-research. Darlinghurst, Australia: Australian Computer Society, 2006: 145-153.

[7]CASTRO L N, ZUBEN F J. The clonal selection algorithm with engineering applications[C]//Proceedings of GECCO’00,Workshop on Artificial Immune Systems and Their Applications. New York: ACM Press, 2000: 36-37.

[8]TIMMIS J, HONE A, STIBOR T, et al. Theoretical advances in artificial immune systems[J]. Theoretical Computer Science,2008, 403(1): 11-32.

[9]KHILWANI N, PRAKASH A, SHANKAR R, et al. Fast clonal algorithm[J]. Engineering Applications of Artificial Intelligence, 2008, 21(1): 106-128.

[10]焦李成, 劉 芳, 劉 靜, 等. 智能數據挖掘與知識發現[M]. 西安: 西安電子科技大學出版社, 2006.

JIAO Li-cheng, LIU Fang, LIU Jing, et al. Intelligent data mining and knowledge discovery[M]. Xi’an: Xidian University Press, 2006.

[11]金可仲. 基于關鍵屬性約束的關聯規則挖掘在日志分析中的應用[J]. 溫州大學學報, 2008, 29(1): 56-60.

JIN Ke-zhong. Application on log analysis using association rule mining algorithm with key item constraint[J]. Journal of Wenzhou University, 2008, 29(1):56-60.

[12]AGRAWAL R, SRIKANT R. Fast algorithm for mining association rules[C]//Proceedings of the 20th Very Large Data Bases International Conference. San Francisco:Morgan Kaufmann Publishers, 1994: 487-499.

[13]楊 珺, 王 敏, 陳 晨, 等. 帶約束的免疫克隆取證分析方法[J]. 計算機工程, 2010, 36(14): 158-160.

YANG Jun, WANG Min, CHEN Chen, et al. Immune clone forensic analysis method with constraint[J]. Computer Engineering, 2010, 36(14): 158-160.

[14]PAXSON V. Traces available in the internet traffic archive[EB/OL]. (2008-04-09)[2008-07-30]. http://ita.ee.lbl.gov/htm /traces.html.

編 輯 張 俊

Forensic Analysis Method of Behavior Profiling on Artificial Immunity

YANG Jun1, CAO Yang1,2, MA Qin-sheng1, and WANG Min3

(1. School of Electronic Information, Wuhan University Wuhan 430079;2. State Key Laboratory of Software Engineering, Wuhan University Wuhan 430072;3. Second Department, Commanding Communications Academy Wuhan 430010)

To improve the efficiency of the forensic analysis method on data mining, this paper proposes a new method for the forensic analysis of the behavior profiling on the longest frequent pattern which is constructed by immune clonal algorithm. Taking the behavior data and the candidate pattern of the frequent item sets as the antigen and the antibody respectively, the support of the antigen to the antibody as the function of affinity, the key attribute as the constraint condition, and the minimal support as the screening condition, the behavior profiling on the longest frequent pattern is built with the help of the immune clonal operation to antibody. The abnormal data are detected by the matching method that the audit data pass through the list items of the behavior profiling. The proposed method and the method on Apriori-CGA are applied in the same problem. The comparison results indicate that the setting up time of behavior profiling and the test time of abnormal data are dramaticly reduced.Therefore, the proposed method has a good ability in the efficiency of forensic analysis and electronic crime investigation.

artificial immunity; behavior profiling; computer forensics; computer security; data mining;electronic crime countermeasures; information analysis; pattern matching

TP309

A

10.3969/j.issn.1001-0548.2010.06.022

2009- 06- 03;

2009- 10- 14

高等學校博士學科點專項科研基金(20040486049)；國家高技術研究發展計劃(2002AA1Z1490)

楊 珺(1973- )，女，博士生，主要從事信息安全和軟件工程方面的研究.