基于前缀树的工控入侵检测算法

林幼玲，朱林全，李扬，邢镔,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 结语

本文提出了基于前缀树的工控入侵检测算法，首先对前缀树的理论进行了介绍，其次对本文中提出的入侵检测系统和入侵算法进行了详细的描述，最后对该入侵算法进行了多个维度的性能分析。该入侵检测算法可以在一定的程度上降低内存的使用率，且具有较高的查询效率，可用于工控网络系统中的入侵检测，具有一定的实际意义。然而，基于前缀树的入侵检测中对内存的使用仍无法达到最优，因此在接下来的工作中将从降低内存占用入手，使得该入侵检测算法具有更高的性能。