劉玉峰 李新友 袁鼎榮

廣西師范大學(xué)計信學(xué)院 廣西 541004

0 引言

非法登錄會對系統(tǒng)或其所有組織造成極大的危害，而這些非法行為很可能不會被及時發(fā)現(xiàn)。當發(fā)現(xiàn)了系統(tǒng)的異常癥狀后也不容易找到非法用戶對系統(tǒng)造成的危害。對于這樣的問題，傳統(tǒng)的方法有：就是在軟件系統(tǒng)中增加日志功能，記錄所有用戶的狀態(tài)信息和對系統(tǒng)所做的操作。但是在海量數(shù)據(jù)日志信息中找到可疑的信息，是一件極其繁瑣的事情。對于這些違規(guī)異常操作使用傳統(tǒng)的方法已經(jīng)很不現(xiàn)實，那么如何能及時而且自動的發(fā)現(xiàn)系統(tǒng)中可疑的用戶行為呢？為此，我們提出一個對軟件使用異常用戶的識別技術(shù)。首先我們對以往軟件運行的日志數(shù)據(jù)進行預(yù)處理，得到以用戶使用會話為單位的日志數(shù)據(jù)，然后我們使用統(tǒng)計的方法，統(tǒng)計出可以表現(xiàn)用戶行為特征的屬性值，作為訓(xùn)練決策樹的數(shù)據(jù)集。利用決策樹方法的ID3算法構(gòu)建用戶的分類模型。例如，對于利用獲得的訓(xùn)練數(shù)據(jù)集進行訓(xùn)練決策樹，得到三個類的分類規(guī)則，由歸納得到的規(guī)則庫可以對未來使用軟件的用戶做出預(yù)測。根據(jù)預(yù)測的結(jié)果來決定是否有異常用戶對數(shù)據(jù)庫的入侵行為，根據(jù)其操作路徑便于做出決策，來決定是否對數(shù)據(jù)庫進行重新審核或者進行還原備份處理。

1 相關(guān)研究

我們研究的問題，實質(zhì)上是對軟件系統(tǒng)運行的日志進行挖掘。日志就是程序運行時為了記錄當前狀態(tài)而產(chǎn)生信息，它由軟件工程師根據(jù)具體需求設(shè)置具體內(nèi)容，如可以記錄錯誤，程序當前狀態(tài)等，用戶訪問信息等。以往關(guān)于日志挖掘的研究主要有：軟件數(shù)據(jù)挖掘，Web使用挖掘等。

1.1 軟件挖掘

軟件挖掘就是對軟件生命中期中產(chǎn)生的數(shù)據(jù)使用數(shù)據(jù)挖掘的方法找到有趣的模式從而輔助軟件的各個階段的需求。軟件數(shù)據(jù)挖掘?qū)\行時系統(tǒng)數(shù)據(jù)的研究從其目的上分為：系統(tǒng)完善與重構(gòu)；源代碼潛在錯誤檢測，逆向工程等。其中主要研究有：S.Breu分析程序產(chǎn)生的日志信息，尋找被重復(fù)執(zhí)行的函數(shù)，從而找到程序的切面。在方面挖掘方向中，分析程序日志是一個主要的研究方法。Liu在他的文章中記錄測試程序函數(shù)調(diào)用的日志，然后繪制出函數(shù)調(diào)用的頻繁圖，在圖中抽出主要特性構(gòu)造出基于SVM的分類器，來檢測異常程序。El-Ramly使用遺留系統(tǒng)中嵌入特定日志記錄功能，使用頻繁序列挖掘的方法找到了用戶使用老系統(tǒng)的交互模式，然后根據(jù)找到的模式在新系統(tǒng)開發(fā)中用于自動生成用戶的圖形界面。我們的研究工作也屬于軟件挖掘，其目的就是增強系統(tǒng)在執(zhí)行階段的安全性。是數(shù)據(jù)挖掘技術(shù)在軟件領(lǐng)域的一次應(yīng)用。

1.2 Web使用挖掘

Web使用挖掘就是利用數(shù)據(jù)挖掘技術(shù)對Web日志信息進行分析從而找到瀏覽者的使用模式。但是傳統(tǒng)的Web日志很難還原會話狀態(tài)這一信息，雖然Tanasa提出了一個方法來還原用戶會話，以角色用戶行為模式分析對傳統(tǒng)的Web日志挖掘還是很困難的，主要的研究有：Web服務(wù)器性能改進包括：頁面緩存、預(yù)讀取、交換、定制訪問者個性化服務(wù)、分類瀏覽者等，主要使用數(shù)據(jù)挖掘的方法是：頻繁模式和分類?，F(xiàn)在越來越多的軟件系統(tǒng)是基于Web，即B/S模式，Web日志的功能也被加強，不再是服務(wù)器的一個附加功能，而是軟件系統(tǒng)中一個必需的功能。

系統(tǒng)日志就是系統(tǒng)運行時狀態(tài)的記錄，而日志挖掘就是利用數(shù)據(jù)挖掘方法通過分析系統(tǒng)運行時狀態(tài)尋找系統(tǒng)運行時的有趣模式。

2 基于決策樹的分類方法

在決策樹學(xué)習(xí)方法中有各種各樣的算法。其中最為著名的是ID3算法，它是Quinlan于1986年提出來的。ID3算法體現(xiàn)了決策樹分類的優(yōu)點：算法的理論清晰、方法簡單、學(xué)習(xí)能力較強。缺點是：只對比較小的數(shù)據(jù)集有效，且對噪聲比較敏感。當訓(xùn)練數(shù)據(jù)集加大時，決策樹可能會隨之改變，并且在測試屬性選擇時，他傾向于選擇取值較多的屬性?；镜腎D3算法通過自頂向下構(gòu)造決策樹來進行學(xué)習(xí)，通過定義一個度量標準來衡量每一個實例屬性單獨分類訓(xùn)練樣例的能力。分類能力最好的屬性被選為樹的根節(jié)點的測試屬性，然后為根節(jié)點屬性的每個可能值產(chǎn)生一個分支，并把訓(xùn)練樣例劃分到適當?shù)姆种Вㄒ簿褪牵瑯永脑搶傩灾祵?yīng)的分支）之下。然后重復(fù)整個過程，用每個分支節(jié)點所關(guān)聯(lián)的訓(xùn)練樣例來選取在該節(jié)點被測試的最佳屬性。這形成了對合格決策樹的貪婪搜索（greedy search），也就是算法從不回溯重新考慮以前的選擇。

2.1 ID3算法基礎(chǔ)

ID3算法的核心問題是如何選取在樹的每個節(jié)點要測試的屬性，它的解決方法是利用信息理論，通過定義一個信息增益（information gain）的概念來衡量給定的屬性區(qū)分樣例的能力。它在增長樹的每一步都使用這個信息增益標準來從候選屬性中選擇最佳測試屬性。在信息理論中，對于一個分布P=（p1，p2，…，pn），它的信息量為：

根據(jù)信息理論，假設(shè)一個數(shù)據(jù)樣例集合T被無遺漏的劃分為k個不同的類C1，C2，…，Ck，那么在T中識別一個樣例的類別所需要的信息量為：Info（T）=I（p），其中P為類別的分布，P=（|C1|/|T|，|C1|/|T|，…，|C1|/|T|）。

如果我們用一個屬性A將訓(xùn)練樣例集T劃分為m個子集：T1，T2，…，Tm，那么在劃分后，在T中識別一個樣例的類別所需要的信息量則為在每個子集中識別一個樣例所需要的信息量的加權(quán)平均數(shù)，即：

則屬性A的信息增益為：

Gaub（A，T）=Info（T）-Info（A，T）

2.2 ID3算法的描述

給定一個非類別屬性C1，C2，…，Cn的集合、類別屬性C及記錄的訓(xùn)練集T。

ID3算法的基本框架如下：

Function ID3（R: a set of non-categorical attributes，C: the categorical attribute，S: a training set）

return a decision tree;

Begin

If S is empty，

return a single node with value Failure;

If S consists of records all with the same value for the categorical attribute，

return a single node with that value;

If R is empty，

return a single node with as value the most frequent of the values of the categorical attribute that are found in records of S; [ note that then there will be errors，that is，records that will be improperly classified ];

Let D be the attribute with largest Gain（D，S）among attributes in R;

Let {dj | j=1，2，…，m}be the values of attribute D;

Let {dj | j=1，2，…，m}be the subsets of S consisting respectively of records with value dj for attribute D;

Return a tree with root labeled D and arcs labeled d1，d2，…，dmgoing respectively to the trees ID3（R-{D}，C，S1），ID3（R-{D}，C，S2），…ID3（R-{D}，C，Sm）;

MDL pruning（root）;

End ID3;

屬性的信息增益描述了這樣一個概念：對于一個訓(xùn)練樣例集T，在使用一個屬性A劃分T之后，從T中識別一個樣例的類別所需要的信息量的減少量。通過它，可以度量屬性分類訓(xùn)練樣例集能力的大小。ID3算法正是把信息增益作為增長樹的每一步中選取最佳屬性的度量標準，選擇信息增益作為選擇屬性的標準有下面兩個好處：①通過最少的屬性測試步驟就可以分類一個實例；②生成最短的決策樹，符合“奧坎姆的剃刀”（Occam's razor）的原則。決策樹學(xué)習(xí)算法是最流行的歸納推理算法之一，已經(jīng)被成功的應(yīng)用到從學(xué)習(xí)醫(yī)療診斷到學(xué)習(xí)評估貸款申請的信用風(fēng)險的廣闊領(lǐng)域。

3 軟件日志的挖掘過程

我們針對教務(wù)處的B/S模式成績管理系統(tǒng)的特定使用對象劃分軟件使用用戶為：學(xué)生、教師、異常用戶三個類別。下面對三類用戶的特點進行分析和數(shù)據(jù)獲取、預(yù)處理操作進行介紹。

3.1 三類用戶的特點分析

3.1.1 學(xué)生

學(xué)生的使用記錄是軟件系統(tǒng)的主體對象，學(xué)生登錄系統(tǒng)主要是查看自己各科目的成績，登錄驗證后通過調(diào)用成績顯示模塊（Show（）函數(shù)）查看成績，當發(fā)現(xiàn)自己某一門課程成績不及格的時候，有的學(xué)生可能會產(chǎn)生修改自己成績的想法，找機會獲得非法登錄軟件系統(tǒng)的權(quán)限。這也就是本文要解決的問題，能及時的檢測出這種行為的發(fā)生，維護數(shù)據(jù)庫系統(tǒng)的安全。

3.1.2 異常用戶

在非法竊取登錄權(quán)限后，由于害怕被發(fā)現(xiàn)的心理作用，登錄軟件系統(tǒng)后的目的性很明確，找到相應(yīng)的頁面后，對自己的不及格成績做出快速的修改（調(diào)用了Modify（）函數(shù)或者Add（）函數(shù)），頁面停留時間很短。由于非法修改完成后不會在訪問其它的頁面就會立即退出，所以訪問的深度不會太深。

3.1.3 教師用戶

登錄軟件系統(tǒng)后，要對學(xué)生的成績進行輸入、修改、刪除等操作。教師在頁面操作停留的時間較長，主要訪問頁面是：成績錄入、修改、刪除和統(tǒng)計等頁面。訪問的層次較深，調(diào)用Login（）、Show（）、Add（）、Modify（）、Statistic（）、Delete（）等函數(shù)。非法用戶主要是獲取這個權(quán)限，才能調(diào)用Modify（）模塊函數(shù)進行非法操作。

3.2 數(shù)據(jù)獲取和預(yù)處理

針對教務(wù)處的B/S模式的成績數(shù)據(jù)庫管理系統(tǒng)軟件，本文在構(gòu)造日志函數(shù)時，主要是考慮到不同用戶的會話狀態(tài)、操作時間、該用戶執(zhí)行的程序模塊調(diào)用對數(shù)據(jù)庫的操作，因此我們給運行系統(tǒng)增加專門的日志切面，其關(guān)注點是系統(tǒng)中業(yè)務(wù)邏輯層中的每個函數(shù)的調(diào)用關(guān)系。從而得到如表1形式的日志內(nèi)容。

表1 軟件運行日志的記錄及編號

軟件系統(tǒng)運行日志內(nèi)容的解釋如表2所示。

表2 構(gòu)造分類器的5個屬性及解釋

其中，表中軟件系統(tǒng)用戶操作函數(shù)路徑關(guān)系如表3所示。

表3 操作函數(shù)對應(yīng)的編號

決策樹學(xué)習(xí)方法學(xué)習(xí)到的決策樹很容易轉(zhuǎn)換為if-then的規(guī)則，而且分類規(guī)則易于理解，經(jīng)過以上分析我們采用ID3決策樹學(xué)習(xí)的方法來構(gòu)造分類器，理論上能夠達到較好的分類效果。

注意到在我們所選擇的5個屬性當中，A1和A2的取值是連續(xù)的，A3和A4的取值雖然是離散的，但它們的取值比較多，因此我們有必要對這些屬性進行離散。盡管在決策樹學(xué)習(xí)算法中，能夠處理連續(xù)取值的屬性，但是通過把它們的取值離散可以達到提高學(xué)習(xí)效率和分類精度的目的，每個屬性的值都映射為0、1或2。數(shù)據(jù)集的數(shù)據(jù)離散化處理如表4所示。

表4 屬性的離散化處理

4 實驗

我們從學(xué)校教務(wù)處的基于B/S成績管理系統(tǒng)的歷史軟件運行記錄日志，選取其中的9000條記錄來進行實驗。原始日志經(jīng)過會話識別后得到3600條訪問記錄，我們從3600條訪問記錄中選取了兩類訪問各9條組成小訓(xùn)練樣本集和根據(jù)異常用戶的登錄和操作情況構(gòu)成的7條異常訓(xùn)練樣本集來訓(xùn)練分類器形成規(guī)則庫，便于我們以后異常用戶登錄系統(tǒng)的預(yù)測，如表5所示。讀入屬性和訓(xùn)練集生成決策樹的界面如圖1所示。由訓(xùn)練樣本集生成的決策樹如圖2所示，其中葉節(jié)點中的0、1和2分別代表學(xué)生用戶、教師用戶和異常用戶。

表5 包含25條記錄小訓(xùn)練樣例集

系統(tǒng)輸入屬性和訓(xùn)練集的界面：

生成的決策樹如下：

我們從3600條會話中挑選出300條記錄（包含異常用戶記錄）并標記出它們的類別，用生成的決策樹進行分類測試，測試的結(jié)果。對三類訪問者的分類精度分別為：92.1%、89.6%和83.3%，總體分類精度為90.6%。分類的準確率如表6所示。

圖1 讀入屬性和訓(xùn)練集生成決策樹的界面

圖2 訓(xùn)練樣例生成的決策樹

表6 決策樹的分類精度

我們對診斷出來的異常用戶進行分析，決定是否有異常用戶對數(shù)據(jù)庫系統(tǒng)進行了非法操作，還原出其函數(shù)操作路徑，根據(jù)操作函數(shù)路徑分析異常用戶進行的非法修改數(shù)據(jù)庫管理系統(tǒng)，能夠及時的對數(shù)據(jù)庫管理系統(tǒng)安全管理和維護。從中我們可以體會到對B/S模式數(shù)據(jù)庫管理系統(tǒng)的軟件用戶進行分類是非常重要和必要的。

5 總結(jié)與以后的工作

本文我們先對軟件系統(tǒng)運行日志數(shù)據(jù)進行事務(wù)還原處理，找到代表每次事務(wù)的特征屬性，然后使用ID3決策樹算法找到分類規(guī)則，挖掘出異常用戶，而這個異常事物就代表了對系統(tǒng)進行異常操作的用戶。我們將在以后的研究中，由于獲得用戶類別付出代價較大，對這個方法進行擴展，首先用聚類方法找到不同的用戶類別，標記整個數(shù)據(jù)集的類別后使用決策樹、SVM等方法對這類用戶的使用模式建立一個模型，然后使用這個模型區(qū)分出不同類型的用戶。本文討論的系統(tǒng)異常用戶的檢測只是這方面研究的一個開端，我們會在以后的工作中不斷擴展和細化這個領(lǐng)域的研究。

[1]S.Breu and J.Krinke，"Aspect Mining Using Event Traces，"in Automated Software Engineering，2004.Proceedings.19th International Conference on.2004.

[2]C.Liu，X.Yan，H.Yu，J.Han，and P.S.Yu，Mining Behavior Graphs for“Backtrace”of Noncrashing Bugs.SDM05.2005.

[3]M.El-Ramly，E.Stroulia，and P.Sorenson，F(xiàn)rom run-time behavior to usage scenarios: an interaction-pattern mining approach.Edmonton，Alberta，Canada: ACM.2002.

[4]D.Tanasa and B.Trousse.Advanced data preprocessing for intersites Web usage mining，Intelligent Systems.IEEE.2004.

[5]Han Jiawei，Kamber M.范明，孟小峰譯.數(shù)據(jù)挖掘:概念與技術(shù)[M].北京:機械工業(yè)出版社.2001.

[6]毛國君，段立娟，王實等.數(shù)據(jù)挖掘原理與算法[M].北京:清華大學(xué)出版社.2005.

[7]Tom M.Mitchell.曾華軍，張銀奎譯.機器學(xué)習(xí)[M].北京:機械工業(yè)出版社.1998.

[8]Chang K.C，He B，Li C，Patel M，Zhang Z.Structured dat- a bases on the web: Observations and Implications[J].SIGM- OD Record.

[9]Robert Cooley，Bamshad Mobasher and Jaideep Srivastava.Data Preparation for Mining World Wide Web Browsing Patterns.Knowledge and Information System.1999.