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

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

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

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

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

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

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

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

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

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

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

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

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

1.1 數(shù)據(jù)預(yù)處理

1.2 行為輪廓構(gòu)造

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

圖2 證據(jù)分布圖

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

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

1.3 異常數(shù)據(jù)檢測

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

2 行為輪廓構(gòu)造算法

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

2.1 親和度函數(shù)

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

2.2 克隆操作

2.3 克隆變異

2.4 克隆重組

2.5 克隆選擇

2.6 算法流程

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

圖3 行為輪廓構(gòu)造算法流程圖

3 實驗結(jié)果及分析

實驗數(shù)據(jù)選自文獻[14]的數(shù)據(jù)文件lbl-conn-7.tar.Z，該組數(shù)據(jù)共有9個屬性，反映了勞倫斯-伯克利實驗室(Lawrence-Berkeley laboratory)30天的TCP連接情況。選取protocol和remote host作為關(guān)鍵屬性項，以使行為輪廓能夠反映用戶在網(wǎng)絡(luò)連接中的行為。順序截取用戶1的10 000條正常連接記錄作為訓(xùn)練數(shù)據(jù)；隨機截取用戶1剩余記錄中的5 000條記錄作為審計數(shù)據(jù)。設(shè)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)挖掘出的頻繁模式數(shù)目，以及帶約束的免疫克隆算法(方法3)挖掘出的頻繁長模式數(shù)目；圖4描述了在上述條件下方法1和方法3的運行時間隨最小支持度在常用對數(shù)坐標(biāo)下的變化趨勢。分析表和圖中的信息(10次操作的平均值)可以得到以下結(jié)果：

(1)min_sup應(yīng)合理選取。

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

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

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

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

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

圖4 算法運行時間和最小支持度的關(guān)系

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

表2 異常數(shù)據(jù)檢測結(jié)果

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

4 結(jié) 論

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

[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]孫 波. 計算機取證方法關(guān)鍵問題研究[D]. 北京: 中國科學(xué)院軟件研究所, 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]焦李成, 劉 芳, 劉 靜, 等. 智能數(shù)據(jù)挖掘與知識發(fā)現(xiàn)[M]. 西安: 西安電子科技大學(xué)出版社, 2006.

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

[11]金可仲. 基于關(guān)鍵屬性約束的關(guān)聯(lián)規(guī)則挖掘在日志分析中的應(yīng)用[J]. 溫州大學(xué)學(xué)報, 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

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

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