基于離散馬爾科夫鏈的數據庫用戶異常行為檢測*

畢 猛，王安迪，徐 劍，3，周福才

基于離散馬爾科夫鏈的數據庫用戶異常行為檢測*

畢 猛1，2，王安迪1，徐 劍1，3，周福才1

針對數據庫系統內部攻擊的問題，將基于用戶行為的異常檢測方法引入到數據庫系統內部攻擊檢測中.將離散時間馬爾科夫鏈(DTMC)應用到數據庫系統異常檢測中，構建了一種基于DTMC的用戶行為異常檢測系統.將用戶提交的SQL語句作為用戶行為特征進行分析，并利用DTMC分別提取了正常用戶和待檢測行為的行為特征，并將兩者進行比較，如果兩者的偏離程度超過了閾值，則判定行為異常.通過實驗對所提出系統的可行性和有效性進行測試，結果表明，該系統可以較好地描述用戶行為，并有效地檢測出數據庫系統內部攻擊.

網絡安全；數據庫安全；用戶行為；內部攻擊；異常檢測；入侵檢測；SQL語句；離散馬爾科夫鏈

隨著計算機以及網絡技術的飛速發展，計算機網絡對社會發展起到了巨大的推動作用.但是，這也帶來了諸多的網絡安全問題，例如數據竊取、敏感信息泄露以及網絡欺詐等.盡管研究人員已經開發了多種網絡安全保護技術和產品，例如防火墻、入侵檢測、入侵防御、隔離網閘以及主機審計等，但是，無論在發達國家還是在發展中國家，網絡安全問題仍然日益嚴重，信息安全風險[1]正在加大，已經成為信息時代人類必須面臨的共同挑戰[2].

目前，學術界和企業界在網絡安全方面投入了大量的精力，并取得了豐碩的研究成果，但是，對于數據庫安全方面的研究則相對薄弱.然而，在信息系統的整體安全中，數據庫往往是最吸引攻擊者的目標，許多網絡攻擊的根本目的就是獲取存放在數據庫中的重要信息.傳統的數據庫安全保障方法[3]在一定程度上提高了數據庫系統的安全性，但是它們大多是被動的安全技術，以預防為主，無法有效地制止入侵行為，特別是對于數據庫用戶(如數據庫管理員等)的權限濫用等內部攻擊常常是無能為力的.據統計，對數據庫的攻擊80%來自內部，內部攻擊是數據庫系統的主要威脅.因此，針對數據庫系統中用戶異常行為檢測研究就顯得尤為重要.

基于異常的入侵檢測是入侵檢測研究領域中的一個重要課題，并取得了一定的研究成果[4-6].但是，這些研究成果主要針對操作系統和計算機網絡，針對數據庫系統的研究成果則相對較少.Chung等人將數據庫系統的語義和異常檢測系統研究緊密結合起來，提出使用用戶輪廓檢測數據庫用戶的行為，并研發出了數據庫誤用入侵檢測系統原型[7].之后，相關企業也推出了一系列數據庫入侵檢測產品，如Application Security Inc公司的數據庫入侵檢測產品AppRadar，它可針對不同的數據庫設計不同的入侵檢測系統.李銀釗等人構建了一種基于自適應模型數據庫入侵檢測方法[8]，該方法是基于矩陣和最小支持度函數的Apriori Z 關聯算法，在訓練和自適應入侵檢測階段產生數據庫的操作特征，用戶根據實際需求動態調整最小支持度函數的值，更高效地挖掘操作特征.陳大鵬提出了基于網絡用戶行為分析與識別的數據庫入侵檢測系統[9]，并給出了神經網絡算法在數據庫用戶行為入侵檢測上的應用實例.陳煒利用基于聚類分析與關聯規則挖掘的數據庫異常檢測技術，對數據庫操作行為和數據操作進行審計分析，建立用戶正常的行為模式，并通過編寫異常檢測算法來檢測用戶的異常行為[10].

本文提出了一種基于DTMC的數據庫用戶異常行為檢測方法，該方法將用戶提交的SQL語句作為用戶行為特征，并利用DTMC進行提取和分析，之后通過計算出的閾值進行判斷，最后利用相關實驗數據集進行測試，結果表明，本文系統可以有效地檢測出數據庫系統內部的攻擊行為.

1 離散馬爾科夫鏈

本文給出了與離散馬爾科夫鏈相關的定義和定理[11].

定義1一個隨機過程{Xn，n≥1}稱作具有狀態空間S={1，2，…，∞}的(一階)離散時間馬爾科夫鏈(discrete-time Markov Chain，DTMC)，如果對所有的n≥1，j∈S和sm∈S(1≤m≤n)，則有

Pr(Xn+1=j|Xn=sn，Xn-1=sn-1，…，X1=s1)=

Pr(Xn+1=j|Xn=sn)

定義2一個DTMC{Xn，n≥1}稱作時間齊次的，如果它滿足不動性假設，即對所有的j∈S和i∈S，條件概率Pr(Xn+1=j|Xn=i)與n無關.

當DTMC{Xn，n≥1}是時間齊次時，pij=Pr(Xn+1=j|Xn=i)稱作(一步)轉移概率，由(一步)轉移概率pij構成的矩陣P=[pij]稱作(一步)轉移概率矩陣.ai=Pr(X1=i)稱作狀態i的初始出現概率，由狀態的初始出現概率構成的行向量A=(ai)i∈S稱作初始概率分布.

定理1時間齊次的DTMC{Xn，n≥1}由初始概率分布A和轉移概率矩陣P完全刻畫，即

Pr(X1=s1，…，Xn-1=sn-1，Xn=sn)=

as1ps1，s2，…，psn-1，sn

定義3一個DTMC{Xn，n≥1}稱作平穩的，則其初始概率分布A和轉移概率矩陣P滿足

A=A×P

定理2對平穩的DTMC{Xn，n≥1}，則有

Pr(Xn=i)=Pr(X1=i)=ai

由定理1和定理2可得定理3.

定理3對平穩的、時間齊次的DTMC{Xn，n≥1}，則有

Pr(Xi=si，…，Xj-1=sj-1，Xj=sj)=

asipsi，si+1，…，psj-1，sj(1≤i

2 系統分析與設計

2.1 檢測流程設計

在本文系統中，用戶行為異常檢測是建立一個合法用戶的正常行為模式，通過比較該合法用戶的當前行為和正常行為特征來識別異常行為，即如果該合法用戶的當前行為較大幅度地偏離了其歷史上的正常行為特征，則認為發生了異常.這種異常可能是該合法用戶本身進行了非授權操作，也可能是系統中其他合法用戶或外部入侵者(非法用戶)冒充該合法用戶進行了非法操作.

在數據庫系統中，用戶主要通過SQL語句與數據庫管理系統進行交互，完成信息的查詢、修改以及刪除等操作.通過分析SQL語句的執行序列，就可以較為全面地描述用戶的行為特征.分析SQL語句的優點在于：當查詢通過異常檢測系統的處理時，系統負載較輕.一個新的SQL語句被分析并通過一些統計模型檢查，僅當查詢被異常檢測系統所接受時才在數據庫管理系統中運行.

在本文系統中，基于用戶行為的異常檢測主要包括兩個過程，即訓練過程和檢測過程.

1) 在訓練過程中，使系統在正常情況下運行一段時間，收集正常運行時的數據，提取用戶行為特征，建立正常的用戶行為模式(應該使建立的行為特征模式包括盡可能多的正常的系統行為).

2) 在檢測中，使系統運行于實際的環境中，收集當前用戶的行為數據并提取行為特征，比較檢測用戶的行為特征與正常行為特征，通過對比觀察正常與當前行為特征的偏離程度判斷是否發生了異常.

本文提出的數據庫用戶行為異常檢測主要包括三個階段：

1) 數據預處理階段.在該階段對用戶提交給數據庫系統的SQL語句，即數據庫用戶行為，進行采集和預處理.

2) 訓練階段.在該階段分析用戶行為特征，獲取用戶正常行為模式.訓練階段和檢測階段的流程圖如圖1所示.在訓練階段，采集的是用戶一段時間內正常操作的數據，如日志文件中的SQL語句等，從中提取用戶正常狀態下的行為規律，作為歷史行為模式.提取訓練序列的行為特征，建立正常序列庫，運用DTMC得到訓練序列的馬爾科夫鏈狀態集，并計算該馬爾科夫鏈狀態的轉移概率矩陣，以此來描述用戶的正常行為.

3) 檢測階段.在該階段采集被檢測用戶的操作數據.提取檢測數據中的行為特征作為當前被檢測用戶的行為特征.將被檢測用戶的行為特征與歷史行為特征進行對比，判斷當前行為是否為異常行為.如果兩者的偏離超過一定閾值，則認為是異常的；如果兩者的偏離在正常范圍內，則認為行為是正常的.

圖1 訓練階段和檢測階段流程Fig.1 Flow chart of training and detecting stages

2.2 系統功能設計

本文系統主要包括三個功能模塊：數據預處理模塊、數據訓練模塊和異常檢測模塊.

2.2.1 數據預處理

數據預處理模塊主要包括數據采集子模塊和預處理子模塊.

1) 數據采集子模塊.在本文系統中，采用SQL語句作為異常檢測的數據源，因此，需要收集數據庫日志文件中的用戶SQL操作請求.

2) 預處理子模塊.在該模塊中主要是對收集到的數據進行處理和加工，使之符合下一個模塊的輸入.根據正常序列庫(library of general sequence，LGS)的要求，需要將收集到的所有數據處理成一個序列.因此，需要將SQL請求中的關鍵字提取出來，組合成為一個訓練序列.在實現過程中，由于SQL語句的關鍵字通常為多個字母的英文單詞，在訓練和檢測過程中操作較為復雜，為了優化算法的執行效率，將關鍵字進行統計分類，由單個英文字母代替.

2.2.2 數據訓練

數據訓練模塊包括序列庫建立子模塊和基于DTMC的行為特征提取子模塊.

1) 序列庫建立模塊.對于經過預處理的序列，定義W種不同長度的短序列，并設置相應的出現頻率權重.

l(i)代表第i種短序列的長度，e(i)代表第i種短序列的出現頻率權重，其中，i=1，2，…，W，l(1)

(1)

將所有數據流中全部的不同短序列合并到正常序列庫中，并計算其在正常序列庫中的加權出現頻率.

(2)

2) 基于DTMC的行為特征提取模塊.在檢測異常行為之前，系統需要建立用戶正常行為的行為特征.本文利用不同長度短序列的狀態構建離散時間馬爾科夫鏈，以此作為用戶的行為特征.在本文方法里，狀態數N需要提前設置.首先需要得到訓練數據s=(s1，s2，…，sr)中每一個命令的行為模式；然后根據LGS中的N-1個分組，生成每一個行為模式的馬爾科夫鏈狀態，由此得到一個馬爾科夫鏈狀態集；最后建立馬爾科夫鏈的轉移概率矩陣P.

2.2.3 異常檢測

一旦用戶行為特征形成，異常檢測系統的基本操作就是比較檢測序列與歷史數據，并且判斷兩者是否屬于同一個用戶.被檢測用戶的行為特征與歷史數據的偏離是入侵的重要標識，因此，假設歷史數據都屬于同一個用戶.在本文系統的異常檢測階段，由轉移概率矩陣決定的分類值是判定異常行為的唯一衡量標準，這將大大減輕系統的計算負擔，系統的主要檢測步驟如下：

1) 獲取并預處理審計數據.在異常檢測階段，需要采集待檢測用戶產生的原始SQL命令行(即需要被審計的數據)，將采集到的數據經過預處理形成一個序列.c=(c1，c2，…，ct)表示經過預處理后的檢測序列，其中，cj是檢測序列中第j個命令，t代表檢測序列中的命令個數.

2) 定義檢測序列狀態，生成狀態序列.根據行為模式提取算法和Markov鏈狀態生成算法，將正常序列庫T和檢測序列c=(c1，c2，…，ct)作為輸入，可以得到與檢測序列相對應的狀態序列q=(q1，q2，…，qM′).由c=(c1，c2，…，ct)截取的短序列可能不包含在LGS中，因此在狀態序列q=(q1，q2，…，qM′)中，狀態值可能為N.

3) 對應狀態序列獲取分類值.在狀態序列q=(q1，q2，…，qM′)中，對于每一個狀態qi(1≤i≤M′-1)，由qi到qi+1的轉移概率為Pr(qi+1|qi)=aqi，qi+1.從qi轉移到qi+1的分類值定義為

(3)

式中：ψ(i)為從qi轉移到qi+1的分類值；δ為概率臨界值，需要提前設置.當ψ(i)=1時，代表一個正常的轉移；否則，表示發生了一個異常的轉移.計算所有狀態的分類值之后，得到一個分類值的序列(ψ(1)，ψ(2)，…，ψ(M′-1)).

4) 計算判定值.雖然個別轉移可能會偏離歷史先例，但是有效用戶大量的行為集合應該在主體上符合歷史行為，而入侵者的行為與歷史行為對比會有明顯的偏離.因此，本文系統對分類值序列應用滑動窗口以獲取大量的行為，然后計算其判定值.本文采用一種均值滑動窗口，在分類值序列(ψ(1)，ψ(2)，…，ψ(M′-1))中的ψ(n)處，其判定值定義為

(4)

式中：D(n)為分類值ψ(n)相對應的判定值，n逐次加1(w≤n≤M′-1)；w為窗口大小.

5) 判別用戶行為是否異常.判定用戶行為是否異常的閾值λ，需要根據系統需求提前設置，當前被檢測用戶的行為是否異常則由D(n)和λ決定.如果D(n)≥λ，認為被檢測用戶的當前行為是正常的，反之如果D(n)<λ，則認為被檢測用戶的當前行為是異常的.本文中，當前行為對應著w個分類值ψ(n-w+1)，ψ(n-w+2)，…，ψ(n)，與w+1個狀態(qn-w+1，qn-w+2，…，qn，qn+1)相關.閾值λ是靈敏度很高的參數，閾值越高，異常檢測成功率越高，同時誤報率也越高；閾值越低，異常檢測成功率越低，誤報率也降低.

3 實驗分析

3.1 測試指標

異常檢測系統對異常行為的檢測效果通常由檢測率、誤報率和漏報率三個參數來衡量.

定義7檢測率.檢測率是指檢測出的異常數據的百分比，即

(5)

定義8誤報率.誤報率是指正常的數據被誤檢為異常數據的比率，即

(6)

定義9漏報率.漏報率是指沒有被檢測出來的異常數據的比率，即

(7)

ROC(receiveroperatingcharacteristic)曲線，即接受者操作特征曲線，在信號檢測理論中被用來表示檢測率和誤報率的折中.本文也將利用ROC曲線來分析系統的性能.ROC曲線左上角的點代表著100%的檢測率和0%的誤報率.因此，ROC曲線越靠近左上角，異常檢測系統性能越好.

3.2 實驗數據

實驗使用的測試數據集是一個診所的數據庫集合[12]，包括39 322條select、insert、update、delete等SQL命令.從數據庫日志文件中采集到的原始數據是SQL命令行.SQL命令里包含操作類型、操作對象、表名等大量命令字段.為了提高檢測效率，需要對SQL語句進行預處理.

定義10語句模板是一個三元組〈OP，F，T〉，其中，OP是SQL語句的語句類型，F是SQL語句涉及的屬性集，T是SQL語句中的表集合.

每條語句都可以歸類到某個語句模板，實際使用過程中認為只要語句模板相同，則兩條語句為同一類語句.

SQL語句1：“SELECT學號，姓名，年齡FROM學生表WHERE年齡<20”；語句2：“SELECT學號，姓名，年齡FROM學生表WHERE性別=男”；語句3：“SELECT學號，數學+語文AS總分FROM學生表，成績表WHERE年齡<20”，3條語句的語句模板如表1所示.

表1 SQL語句模板示例Tab.1 Examples of SQL statement template

由表1可知，將每一條SQL語句處理成語句模板，并按照時間先后排序生成語句模板的序列(OP1，F1，T1，OP2，F2，T2，…)，所有的訓練數據和檢測數據都需按照上述過程處理.

3.3 實驗結果

本文選取了4個用戶的數據用于實驗，如果從4個用戶中選擇一個用戶作為正常用戶，其他3個用戶相對于選定的用戶來說就是異常用戶.用戶的變化會導致系統檢測到的行為模式特征發生變化，如果變化值超出了正常范圍內的波動，系統將會認定其為異常行為.

經過預處理后，用戶1的前9 999個SQL命令字段用于訓練階段構建LGS和Markov鏈，剩余的4 998個SQL命令字段在檢測階段用作測試數據，作為正常行為來檢測系統的誤報率.用戶2、用戶3、用戶4各有6 000條SQL命令字段用作異常行為來測試系統的檢測率.系統各個參數設置為：N=5，W=3，l(1)=1，l(2)=2，l(3)=3，e(1)=1，e(2)=2，e(3)=3，w=81，δ=0.28.

表2給出了每個用戶檢測序列對應的Markov鏈狀態數.由于LGS是由用戶1的訓練數據生成，那么由用戶1的訓練數據截取的短序列總是會出現在LGS中，因此，用戶1檢測序列狀態為N的概率極低，也就是對應行為模式的長度為1的可能性較低.狀態總數與行為模式的長度相關，行為模式的長度越大，狀態總數越少，所以用戶1檢測序列的狀態總數最少.

表2 不同用戶檢測序列狀態數Tab.2 Status number of different user detecting sequences

經過實驗計算得到用戶1的Markov鏈的轉移概率矩陣為

圖2給出了4個用戶的判定值曲線，從圖2中可以看出，用戶2、用戶3和用戶4的曲線可以很明顯地與用戶1的曲線區分開來，即不同用戶的行為特征不同.一旦數據庫出現內部攻擊，攻擊者的行為模式與正常用戶的行為模式一定存在較大差異，被檢測用戶的判定值曲線會出現較大幅度的波動，當系統檢測到波動已超過設定的閾值時，則可以認為該用戶出現了異常.

實驗表明，系統檢測性能和所選定的閾值λ有很大關系，λ越大，系統的檢測率和誤報率會越高，漏報率越低.因此，要通過測試選定比較合適的λ值.另外，狀態數N對系統的性能也會產生一定影響.圖3為N等于4、5、6，閾值λ不同時，系統的ROC曲線.從圖3中可以看出，N=5時，系統性能較N=6、N=4時更好，且λ=0.84時，系統性能達到最優.

圖2 各用戶的ROC曲線Fig.2 ROC curves of various users

圖3 狀態數不同時系統ROC曲線Fig.3 ROC curves of system with different status number

4 結 論

針對數據庫系統中的用戶異常行為檢測問題，利用SQL語句來提取用戶的行為特征，并應用離散Markov鏈的狀態來描述用戶的行為輪廓，設計并實現了基于DTMC的數據庫用戶異常行為檢測系統，該系統包括數據預處理模塊、數據訓練模塊和異常檢測模塊.為了驗證系統的有效性，采用數據庫日志數據進行實驗測試.實驗結果表明，離散Markov鏈的狀態可以用于刻畫數據庫用戶的行為輪廓，正常行為的判定值曲線和異常行為的判定值曲線可以很明顯地區分開，從而證明了系統的有效性.因此，本文系統在數據庫用戶異常行為檢測領域具有一定的實際應用價值.

[1] 趙剛，宮義山，王大力.考慮成本與要素關系的信息安全風險分析模型 [J].沈陽工業大學學報，2015，37(1)：69-74.

(ZHAO Gang，GONG Yi-shan，WANG Da-li.Information security risk analysis model considering costs and factors relevance [J].Journal of Shenyang University of Technology，2015，37(1)：69-74.)

[2] 沈昌祥，張煥國，馮登國，等.信息安全綜述 [J].中國科學(E輯：信息科學)，2007，37(2)：129-150.

(SHEN Chang-xiang，ZHANG Huan-guo，FENG Deng-guo，et al.An overview of information security [J].Science in China (Series E：Information Sciences)，2007，37(2)：129-150.)

[3] 吳溥峰，張玉清.數據庫安全綜述 [J].計算機工程，2006，32(12)：85-88.

(WU Pu-feng，ZHANG Yu-qing.An overview of database security [J].Computer Engineering，2006，32(12)：85-88.)

[4] Joldzic O，Djuric Z，Vuletic P.A transparent and sca-lable anomaly-based DoS detection method [J].Computer Networks，2016，104：27-42.

[5] Bhuyan M H，Bhattacharyya D K，Kalita J K.A multi-step outlier-based anomaly detection approach to network-wide traffic [J].Information Sciences，2016，348(6)：243-271.

[6] 徐明，陳純，應晶.一個兩層馬爾科夫鏈異常入侵檢測模型 [J].軟件學報，2006，16(2)：276-285.

(XU Ming，CHEN Chun，YING Jing.A two-layer Markov chain anomaly detection model [J].Journal of Software，2006，16(2)：276-285.)

[7] Chung C Y，Gertz M，Levitt K.DEMIDS：a misuse detection system for database system [C]//Proceedings of 3rd International Working Conference on Integrity and Internal Control in Information Systems.Amsterdam，Netherlands，1999：159-178.

[8] 李銀釗，閆懷志，張佳，等.基于自適應模型的數據庫入侵檢測方法 [J].北京理工大學學報，2012，32(3)：258-262.

(LI Yin-zhao，YAN Huai-zhi，ZHANG Jia，et al.A method of database instruction detection based on adaptive model [J].Transactions of Beijing Institute of Technology，2012，32(3)：258-262.)

[9] 陳大鵬.基于用戶行為分析與識別的數據庫入侵檢測系統的研究 [D].成都：電子科技大學，2015.

(CHEN Da-peng.Intrusion detection system of database based on user behavior of analysis and identification [D].Chengdu：University of Electronic Science and Technology of China，2015.)

[10]陳煒.基于網絡的數據庫審計和風險控制研究 [D].武漢：武漢理工大學，2013.

(CHEN Wei.The research about database audit and risk management based on network [D].Wuhan：Wuhan University of Technology，2013.)

[11]Karlin S，Taylor H M.A first course in stochastic processed [M].Beijing：Post & Telecom Press，2007：30-60.

[12]Yao Q S，An A J，Huang X J.Finding and analyzing database user sessions[C]//10th International Conference on Database Systems for Advanced Applications.Beijing，China，2005：851-862.

Anomalybehaviordetectionofdatabaseuserbasedondiscrete-timeMarkovchain

BI Meng1,2, WANG An-di1, XU Jian1，3, ZHOU Fu-cai1

(1.Software College, Northeastern University, Shenyang 110169, China; 2.School of Management, Shenyang University of Technology, Shenyang 110870, China; 3.State Key Laboratory of Information Security, Institute of Information Engineering of Chinese Academy of Sciences, Beijing 100093, China)

Aiming at the problem of internal attack in the database system, an anomaly detection method based on the user behaviour was introduced into the internal attack detection in the database system.The discrete-time Markov chain (DTMC) was applied to the anomaly detection of database system, and an anomaly detection system for user behaviour based on DTMC was established.The SQL statements submitted by the users were taken as the user behavior features and were analyzed.In addition, the behavior features of normal users and behavior to be detected were extracted with DTMC, and the corresponding comparison between them was performed.If the deviation degree of two behavior features was beyond the threshold, the detected behavior would be judged as an anomaly behavior.The feasibility and effectiveness of the proposed system were actually tested.The results show that the proposed system can better describe the user behavior, and can effectively detect the internal attack of database system.

network security; database security; user behavior; internal attack; anomaly detection; intrusion detection; SQL statement; discrete-time Markov chain(DTMC)

2016-10-17.

國家自然科學基金資助項目(61602102，61402095)；遼寧省科技攻關計劃項目(2013217004)；中央高校基本科研業務費專項基金資助項目(N151704002)；沈陽市科技計劃資助項目(F14-231-1-08).

畢 猛(1982-)，男，遼寧沈陽人，工程師，博士生，主要從事網絡與信息安全等方面的研究.

* 本文已于2017-10-25 21∶12在中國知網優先數字出版.網絡出版地址：http：//kns.cnki.net/kcms/detail/21.1189.T.20171025.2112.028.html

10.7688/j.issn.1000-1646.2018.01.13

(1.東北大學 軟件學院，沈陽 110169；2.沈陽工業大學 管理學院，沈陽 110870；3.中國科學院信息工程研究所 信息安全國家重點實驗室，北京 100093)

TP 309

A

1000-1646(2018)01-0070-07

鐘 媛 英文審校：尹淑英)