一种基于旋转TCAM 的模式匹配算法*

2020-03-27刘仲会许芳奎许红光

火力与指挥控制 2020年1期

刘仲会，许芳奎，许红光

（1.天津电子信息职业技术学院，天津 300350；2.北京理工大学，北京 100081）

0 引言

VanDyke 软件［1］公布的与安全相关的调查结果表明，尽管病毒是受调查者面临的最大威胁，但66%的用户选择了系统渗入作为最大威胁；调查还显示，采用普通防火墙来阻止可疑流量时并不总是有效；随着黑客攻击和网络蠕虫开始影响互联网，网络入侵防御系统（Network Intrusion Prevention Systems，NIPS）就被开发用于识别和报告攻击。

NIPS 系统通常由2 个主要组件构成：一个模式匹配引擎和一个补充数据包分类引擎。模式匹配引擎的输入是一个数据包，其输出是一组匹配模式，属于已知攻击签名集合。字符串匹配算法是NIPS的主要构建模块。大多数算法要么太复杂而无法在硬件中实现，要么有较差的性能［2-8］；文献［9］提出了一种改进的多模式匹配HSBOM 算法。该算法在预处理过程中建立哈希表代替SBOM 算法的Factor Oracle 自动机来存储模式集中的所有子串信息，大幅度减少算法占用的存储空间；文献［10］针对经典多模式匹配算法中的正则表达式确定有限自动机（Deterministic Finite Automata，DFA）匹配的缺点，提出对规则进行预处理，将相同类似的规则分成同一组，减少生成DFA 的总个数和构造DFA 的时间。结果表明，对系统规则的匹配速度以及减少内存使用方面均有较大的提高；文献［11］提出了一种基于流量分析算法的网络入侵模式特征对比方法。实验结果表明，算法提升了网络入侵检测效率；文献［12-13］提出了并行Bloom 滤波器算法，对每个可能的模式长度，采用一个Bloom 滤波器，通过采用4 个并行引擎来得到一个合理的成本-空间之间的权衡；文献［14］提出了一种基于移位的算法。算法采用基于内存的哈希引擎网络处理器和长度为w 的前缀滑动窗口，并采用一个大小为（28）w的移位表；三态内容寻址存储器（Ternary Content Addressable Memory，TCAM）［15］是一种先进的存储芯片，每个bit 位可以存储3 个值：0、1 和“don’t care”，正是这个第3 种状态特征，使其既能进行精确匹配查找，又能进行模糊匹配查找。在最新的模式匹配算法中，采用TCAM 的是文献［16］提出的模式匹配算法。该算法在TCAM 中放置攻击签名集并置入一个简单的“穷举法”模式匹配算法，从数据包连续构建一个w 字节长的关键字，同时TCAM 查找一个匹配。

本文针对NIPS 系统中的核心部件——模式匹配组件，提出了一种新的基于TCAM 的旋转TCAM（Rotating TCAM，RTCAM）模式匹配算法。它不仅支持现有的TCAM 使用和一些可以用硬件实现的额外逻辑，而且能够使NIPS 系统在线工作在几千兆比特每秒的总速率来实现对恶意流量数据包的有效检测，相比于现有的基于TCAM 的模式匹配算法，还能大大减少内存访问和TCAM 查找访问。

1 预备知识

1.1 Snort 数据库

Snort［3］是一个开源NIPS，常用于工业领域，它是一个包含有数千个攻击签名的规则数据库。在内部，Snort 采用一种基于软件的模式匹配算法，应用一个关键字集，这个关键字集保存在一个类似于关键字树的Aho-Corassick 中。

1.2 符号和定义

定义1 一个模式P 定义为来自于一个字母表∑的一组字符串，它需要在输入的文本内被识别。一个子模式Ps定义为一个模式P 的一个子字符串。

定义2 一个搜索窗口定义为输入文本的一部分，其中的一个子模式被搜索。

定义3 一个移位值定义为算法可以安全跳过而不会丢失任何模式匹配的字节数。从形式上来说，如果0≤s≤n-m 且T［s+1，…，s+m］=P［1，…，m］，则长度为m 的模式P 在长度为n 的文本T 中发生移位s。

定义4 一个字符串匹配算法定义如下：定义文本为一个数组T［1，…，n］，定义模式为一个数组P［1，…，m］，并假设P 和T 的元素为从一个有限的字母表∑中抽取出来的字符。字符串匹配问题就是寻找移位的问题。在一个给定的文本中寻找多个模式的扩展问题称为“多模式匹配”，其目标是输出文本中所有模式出现的位置。本文构建多模式字符串匹配问题如下：T=t［1，...，n］和r 个模式的一个集合P，使得Pj∈P，其中1≤j≤r（模式可以有不同的长度）。

2 旋转TCAM 算法

2.1 旋转TCAM 算法原理

一个大小为M 的TCAM，可以构建为有「M/w⏋行，w 是TCAM 的宽度。TCAM 是驻留在脱机过程的2个阶段。在第1 阶段，将规则签名（模式）进行划分，以适合所选择的w。比w 长的模式占据1 行以上，第1 行的模式标记为“模式前缀”，把标记为前缀的那些短模式通过采用TCAM 的“don’t care”位填充为w 的大小。每个TCAM 行有一个对应的移位值，这个移位值表示当匹配发生时，可以在数据包中安全移位的字节数。在这个阶段，全部TCAM 行的移位值为0；在下一个阶段，通过将前缀向右移，丢弃最右端的字符并在左边添加“don’t care”，为每个模式前缀创建一组移位子模式。这样旋转使移位值增加1，故称为旋转TCAM（Rotating TCAM，RTCAM）。重复这样的过程，直至全部模式的字节都是“don’t care”。由于TCAM 查找返回第1 个匹配的行，故TCAM 行是根据它们的移位值按升序排序的，最后的行对应最大的移位值，且包含w 个“don’t care”字节，从而提供默认的匹配行。

2.2 旋转TCAM 算法的实现描述

本节给出RTCAM 算法的具体实现描述。算法运行3 步或4 步：（i）从位置position=pos（初始pos=0）的数据包构造大小为w 的关键字；（ii）调用TCAM 查找并得到匹配的行；（iii）返回相应的行移位（shift）值。一个大于0 的移位值表示没有一个模式匹配给定的关键字，可以用position=position+shift重复步骤（i）。一个为0 的shift 值意味着一个前缀模式匹配了关键字，并调用步骤（iv）。这一步骤查询内部数据结构来定位潜在的攻击模式。如果匹配的模式小于关键字的大小（w），则出现简单的情况，这时，将相关的模式添加到专用的“匹配模式列表”中，并用position=position+1 调用步骤（i）；如果模式是部分匹配（即它匹配一个较长模式的前缀），则模式的剩余部分也应当被匹配，一种方法是采用内存指令比较数据包和模式的其余部分，更快的方法是再次采用TCAM 来减少内存访问延迟。步骤（iv）通过将它分割成几个w 长的子模式并用TCAM 迭代查找，多次使用TCAM 来匹配模式的剩余部分。这个操作是在特定规则（模式所属的规则）的环境中执行的。只有当全部TCAM 匹配的行对应于0 移位值时，该模式才可以被标记为完全匹配，否则，用position+1 再次调用步骤（i）。算法实现过程的伪代码如算法1 所示。

2.3 算法中的数据结构

2.3.1 模式列表

在算法的步骤（iv）中访问模式列表数据结构，用于比较一个模式的后缀与数据包内容。一个模式列表记录（entry）包含几个字段，保存有需要实现各种Snort 关键字的信息：1）len：模式长度；2）root：是一个布尔值，表明这种模式是否是一个规则的第一个模式；3）offset：表明模式应当从数据包的哪里搜索；4）distance：两个连续匹配（即先前模式匹配和当前模式匹配）之间允许的最小字节数；5）within：两个连续模式匹配之间允许的最大字节数；6）depth：对于指定模式，算法应当搜索数据包多远；7）TCAM_Ptrs：TCAM 引用数组，用于算法的步骤（iv）。

2.3.2 TCAM 规则表

该表将一个TCAM 行和模式列表之间关联起来。每个表记录包含移位值、一个包含（inclusion）模式列表和一个关联（association）模式列表。当一个TCAM 匹配发生时，将匹配的TCAM 行内容与包含匹配行的模式集相关联作为它们的前缀。包含模式列表用于识别小于w 的模式，它们是匹配模式（TCAM 行）的前缀。

2.3.3 匹配模式列表该列表保存当前处理数据包的匹配模式，每个记录包含匹配模式及其在数据包中相应的结束位置。

2.3.4 规则列表规则列表在一个规则及其对应模式之间进行映射。

2.4 算法实例及NIPS 中的数据包流

用下页图1 所示的实例来阐明RTCAM 算法的具体操作过程。假设TCAM 的宽度为4，输入的数据包是“wwabcdeftxyzabcdarp”，我们来寻找在表1 中出现的规则。

表1 Snort 规则示例

在阶段0，匹配模式列表是空的。

首先搜索位置0 的数据包。第1 个关键字是wwab（数据包的前4 个字节），TCAM 查找返回??ab记录，且移位值是2。数据内包的关键字位置然后增加2。接下来的关键字是abcd，采用这个关键字的查找匹配第1 个TCAM 记录，且相应的移位值为0。现在调用算法步骤（iv），并使用关联指针来比较完整模式和数据包的内容。第1 个关联指针指向包含模式abcdef 的节点。该模式没有offset 或depth，因此，没有位置限制，模式的长度为6，故算法取接下来的2 个字节并采用关键字cdef（加上来自于先前查找的最后2 个字节）执行一个TCAM 查找。这个关键字也得到0 作为移位值，而且TCAM 记录的指标出现在TCAM_Ptrs 数组中。算法寻找到一个匹配，并将该模式添加到匹配模式列表中。算法还打开规则记录位图中的模式位。关键字abcd 的关联列表中的下一个指针指向包含abcdarp 模式（该模式不匹配数据包内容，查找关键字darp 失败）的节点。

现在，算法采用包含列表并检查模式数2。由于对offset 值的约束是8，而当前的位置是2，故算法不匹配这个模式。算法对数据包内的搜索位置增加1，并构建搜索关键字bcde。这个关键字匹配最后的TCAM 记录，所以移位值为4，因而下一个关键字为ftxy。在两个查找操作内，关键字xyza 得到一个为0的移位值。

算法再次采用关联指针，这时，关联指针包含模式xyz。由于这不是root 模式，故算法检查先前模式的匹配模式列表。先前模式出现在列表中，且它的结束位置是7。xyz 模式的内部值为5，它的长度为3，且当前位置为9。算法确认9+3≤7+5+1，因而匹配模式被插入到匹配模式列表中。算法还采用规则记录位图设置模式位。由于位图中的全部位被设置，算法就可以“宣布”一个攻击。最后，数据包中的搜索位置被移位1。

两个查找得到一个具有移位值为0 的匹配关键字abcd。算法再一次采用关联指针，第一个节点包含模式abcdef。由于关键字cdar 的查找得到一个大于0 的移位值，故得到该模式不匹配，并继续下一个关联指针（abcdarp）。depth 值为25，当前位置为11，模式长度为7。算法检查11+7≤25。由于模式长度为7（大于w），故算法取下一个字节并用关键字darp 调用TCAM。这个关键字得到0 作为移位值，且TCAM 记录的指标在TCAM_Ptrs 数组中，所以算法把该模式添加到模式匹配列表中，并采用规则设置对应于该模式的位。由于这是规则中唯一的模式，所以算法触发一个攻击警报。

算法继续扫描数据包作为进一步的攻击检测，直至整个数据包被分析完。

图1 算法示例

当然，在执行算法时，还要考虑最坏情况下的性能以及窗口大小。在前者中，对算法可以引入一个简单的预处理阶段，将每个长模式转换成一组短模式（每个短模式的长度等于或小于w），然后采用distance 和within 关键字把这些短模式关联起来；在后者中，需要对RTCAM 内存需求进行计算。总之，选择w 是一个在成本和性能之间的权衡。

3 算法实验结果

为了对算法的性能进行评价，采用2 个模式集来进行仿真测试。第1 个测试集是来自于ClamAV的病毒签名集［17］，它仅包含简单的模式（比较长），第2 个测试集来自于从Snort［18］工具的入侵检测签名构成，这些大多数签名由相关模式构成；用几个不同的TCAM 宽度来仿真基于本文提出的旋转TCAM匹配算法，并将本文提出的旋转TCAM 匹配算法与文献［16］同样基于TCAM 的匹配算法进行比较。

3.1 ClamAV 模式集的仿真结果

ClamAV 的0.82 版有26 986 个简单模式，其平均模式长度为124.1。当在ClamAV 数据库上运行本文的NIPS 时，得到的性能结果如表2 所示。

表2 TCAM 宽度对平均移位值的影响（ClamAV 模式集）

可见，随着TCAM 宽度的增大，TCAM 内存大小需求和平均移位值会随之增大。

3.2 Snort 模式集的仿真结果

Snort 模式包含许多短模式（≤4）。在大多数情况下，这些模式是关联规则的一部分。因此，除了模式本身外，可通过加入更多信息到每个TCAM 行来消除TCAM 匹配。如创建一个哈希函数h，它的输入是额外的数据D，输出是关键字k，即h（D）=k。把k加入到TCAM 的每个记录中；为主协议添加1 个字节的位图和另一个表示与该模式相关联的最低端口和最高端口范围的值。采用这种扩展，得到如表3 所示的对于每个不同TCAM 宽度的TCAM 内存大小需求和移位平均值，对照表2 可见，在短模式的情况下，尽管这些模式是关联规则的一部分，但明显得到了更好的结果。

下面来比较本文提出的算法和文献［16］提出的算法在TCAM 查找访问和内存访问（SRAM 访问）两方面的性能。图2（a）所示为2 种算法在不同TCAM 宽度时的内存访问数量与数据包长度之间的关系曲线，图2（b）所示为2 种算法在不同TCAM 宽度时所需要的TCAM 查找访问数量与与数据包长度之间的关系曲线。从图2 可见，尽管文献［16］提出的算法在TCAM 调用时并不一定需要内存调用，而本文提出的算法在每次TCAM 调用时需调用内存来得到移位值，但本文的算法相比于文献［16］的解决方案来说，调用TCAM 的次数明显减少，即使本文算法对于每次TCAM 调用都要调用内存，但内存调用的总数量也明显少于文献［16］的解决方案，所以本文的算法明显优于文献［16］的算法。