基于前綴樹的工控入侵檢測算法

林幼玲，朱林全，李揚，邢鑌,4，陳彥如

（1.四川大學計算機學院，成都610065；2.重慶工業大數據創新中心有限公司，重慶400707；3.西南通信研究所保密通信重點實驗室，成都610041；4.工業大數據應用技術國家工程實驗室，北京100043）

0 引言

隨著信息技術的發展及提高，傳統工業也逐漸向智能生產和智能工廠轉型，各種工業設備、傳感器等都成為了工業網絡中的一部分。這使得原本較為封閉的工業環境漸漸被打破，各種業務系統相互協作，數據在不同的系統、平臺間流動。然而，由于工業網絡中的對象直接連接到不安全的互聯網上，設備很容易遭到攻擊者的入侵。工業控制系統作為基礎設施的重要組成部分，一旦遭受網絡攻擊，會造成財產損失、人員傷亡等嚴重后果。同時，由于工業網絡中設備的資源和能量均有限，無法支持傳統或復雜的智能決策支持系統的運行。因此，使用入侵檢測系統來檢測工業物聯網中工業控制系統的入侵是十分有必要的。

入侵檢測系統主要用于檢查網絡的狀態和行為，當檢測到入侵時，會出發警報。入侵檢測系統主要有四種類型。第一種是基于簽名的入侵檢測系統，它記錄了入侵檢測系統應該檢測到的每種類型的攻擊的特征，當可疑行為與特征相匹配時，則被識別為入侵行為。這種方式可以高效地檢測入侵，具有較高的準確率，但只能檢測已知的入侵。第二種是基于異常的入侵檢測系統，其需要先收集系統正常行為的數據，然后確定一個閾值，若可疑行為超過該閾值，則發出警報。該方式可以檢測未知攻擊，但計算量大，需要大量的內存用于數據分析。第三種是基于異常和基于簽名的混合入侵檢測系統，它結合了基于簽名的方式檢測效率高、準確率高，以及基于異常的方式可以檢測未知入侵的優點。第四種是基于規范的入侵檢測系統，它指定通常的系統行為，并根據指定的行為驗證當前的行為。

雖然基于簽名的入侵檢測方法具有較高的準確率、較低的漏報率，但其需要較大的存儲空間用于存儲入侵的簽名，同時，其匹配效率取決于使用的匹配算法。當前已有不少的可用于工控系統的基于簽名的入侵檢測算法，如Suresh 等人提出的基于區塊鏈和單字符匹配的入侵檢測算法，程冬梅等人提出的基于規則匹配的分布式工控入侵檢測算法等。

綜上，為了降低入侵簽名庫的存儲空間，提高入侵的檢測效率，本文提出了基于前綴樹的可用于工業控制系統的入侵檢測算法。

1 理論基礎

前綴樹的本質是N 叉樹，也叫字典樹、查找樹或者鍵樹，其最典型的應用是統計和排序字符串，因此常用于搜索引擎的詞頻統計。

前綴樹的根節點不存儲字符信息，除根節點以外的每個節點都存儲一個字符的信息，而每一個節點都包含多個子節點，從根節點到葉子節點之間所代表的字符組成了一個字符串。如圖1 所示，從根節點開始，選擇最左邊的路徑“a”，然后選擇它的第二個孩子節點“d”，接著選擇它的第3 個孩子節點“d”，最終得到字符串“add”。從上圖我們可以看出，某一個節點的后代節點所代表的字符串都與該節點擁有著相同的前綴。例如‘e’節點的后代所表示的字符串為“leaf”和“leg”都有著相同的前綴“le”。

圖1 前綴樹

前綴樹的具體實現方式有很多種，如數組、哈希表、位圖等。若用數組的方式來實現，假設只存儲含有字母“a”-“z”的字符串，則可以在每個樹的節點中聲明一個長度為26 的數組來進行存儲其子節點。若要判斷某個字符是否存在時，則只需要通過其下標進行索引。若使用哈希表的方式進行實現，則每個樹的節點中包含了一個哈希表，而哈希表中則存儲了該節點所包含的子節點。使用數組的方式進行實現可以十分高效地進行查詢，但會造成空間浪費；而使用哈希表進行實現，則不會造成空間浪費，但查詢效率卻會有所下降。

2 系統設計與算法實現

2.1 系統設計

本文所提出的工控入侵檢測系統主要是通過捕獲工控網絡中的網絡層數據，通過對網絡層的數據進行分析，以達到檢測入侵的目的。該系統的核心為入侵檢測，該系統中的入侵檢測功能主要包括四個模塊，第一個是報文捕獲模塊，該模塊主要負責獲取工控網絡中的網絡層數據。第二個是報文提取模塊，該模塊負責對捕獲的報文中的信息進行提取，以用于入侵的檢測。第三個模塊是入侵檢測模塊，該模塊通過對前一個模塊獲得的信息進行分析，以判斷該次行為是否為入侵行為。第四個模塊是響應模塊，該模塊根據入侵檢測模塊的結果做出響應，若該次行為為正常行為，則不進行任何操作；反之，若該次行為為入侵，則攔截該次請求并觸發警報。

圖2 為該入侵檢測系統的結構圖，該系統主要包括展示層、應用層、數據管理層和入侵檢測層。入侵檢測層是該系統的核心，其能實時的檢測入侵。入侵檢測層通過其內部預置的基于前綴樹構建的入侵簽名庫，來實現入侵檢測的目的。數據管理層主要用于各種數據的存儲，包括入侵簽名、報警信息、系統狀態信息、系統日志記錄等。應用層主要是為管理人員提供服務，如為管理員提供簽名配置功能，包括增加、刪除、修改和查詢簽名；日志查詢或審計功能；入侵信息查詢功能等。展示層主要可視化地顯示系統狀態、報警日志、日志統計等信息。

圖2 入侵檢測系統結構圖

2.2 入侵檢測算法

由于需要判別的數據包括行為數據和內容數據，行為數據包括源IP 地址、源端口號、目的IP 地址、目的端口號、源端和目的端的設備地址、源端和目的端的功能代碼，而內容數據則為數據包中的數據字段。因此本文中的入侵檢測采用布隆過濾器和前綴樹結合的方式來實現入侵檢測。布隆過濾器用于行為的檢測，而前綴樹則用于數據包中數據字段的檢測。布隆過濾器和前綴樹分別對對應的數據進行檢測，若某一部分數據存在于對應的數據結構中，則認為該次請求為入侵；反之，若兩部分的數據都不存在與對應的數據結構中，則認為該次請求為正常行為。

本系統中入侵檢測模塊中的核心檢測算法偽代碼如下所示：

輸入：行為參數，內容參數

輸出：是否為入侵數據

//判斷某個元素是否存在于布隆過濾器中

Boolean contains（String value,BloomFilter bf）{

boolean res=true；

//遍歷k 個哈希函數

for（HashFun f：func）{

//判斷計算得到的位置上的值是否都為1

res=res&&bits.get（f.hash（value）;

}

return res;

}

//判斷某個元素是否存在于前綴樹中

Boolean isExist（String value）{

TrieNode node=root;

for（int i=0;i ＜value.length（）;i++）{

char cur=value.charAt（i）;

//判斷樹的當前節點是否包含該字符

if（node.containsKey（cur））{

node=node.get（cur）;

}else{

return false;

}

}

//判斷當前結點是否為葉子節點

return node!=null&&node.isEnd（）;

}

//判斷是否為入侵

Boolean isIntrusion（String value1,String value2）{

//value1 表示行為參數

//value2 表示內容參數

boolean res1=contains（value1）;

boolean res2=isExist（value2）;

//如果res1 和res2 有一個為入侵數據，則為入侵

if（res1||res2）{

return true;

}

else{

return false;

}

}

本文通過對已知的基于Modbus 協議的工控系統中的網絡層數據進行分析，整理出了一系列的入侵特征數據，并將這些數據存儲到前綴樹中，以此來構建并初始化了工控入侵檢測的簽名數據庫。同樣地，出于對內存的考慮，本文以入侵特征來構建入侵檢測的簽名數據庫，而非以正常的行為特征作為檢測的依據。主要原因如下，正常行為特征可能遠多于入侵行為特征，若以正常行為特征來構建前綴樹的話，可能會導致前綴樹過大，從而占用過多的內存空間。同時，出于對內存占用情況的考慮，本文中前綴樹節點的實現擬采用位圖的方式實現。位圖相較于數組的方式，能很大程度上降低內存的開銷。而位圖相對于哈希表的方式，又能在一定程度上提高查詢效率。

3 實驗結果與分析

該實驗的數據集為密西西比州立大學關鍵基礎設施保護中心于2014 年發布的用于工控系統入侵檢測評估的數據集，該數據集中的數據是通過兩個數據采集系統獲得的，分別來自于天然氣管道數據采集系統和儲水箱數據采集系統。本文通過對天然氣管道的數據集進行分析后，基于前綴樹構建了入侵數據的簽名特征庫，經過多次的實驗與優化，在該數據集上，該入侵檢測算法的準確率大約為92%。而檢測準確率無法達到100%的原因主要是入侵簽名規則的提取不夠準確，未能將所有的入侵簽名規則都總結出來。同時，通過實驗對比得到，基于位圖構建的前綴樹相對于數組實現的前綴樹能在很大程度上節省內存空間；而基于位圖構建的前綴樹相較于基于哈希表構建的前綴樹具有較高的檢測效率。

4 結語

本文提出了基于前綴樹的工控入侵檢測算法，首先對前綴樹的理論進行了介紹，其次對本文中提出的入侵檢測系統和入侵算法進行了詳細的描述，最后對該入侵算法進行了多個維度的性能分析。該入侵檢測算法可以在一定的程度上降低內存的使用率，且具有較高的查詢效率，可用于工控網絡系統中的入侵檢測，具有一定的實際意義。然而，基于前綴樹的入侵檢測中對內存的使用仍無法達到最優，因此在接下來的工作中將從降低內存占用入手，使得該入侵檢測算法具有更高的性能。