法律状态公告日
法律状态信息
法律状态
2019-01-25
未缴年费专利权终止 IPC(主分类):H04L12/26 授权公告日:20110914 终止日期:20180207 申请日:20070207
专利权的终止
2011-09-14
授权
授权
2007-10-31
实质审查的生效
实质审查的生效
2007-09-05
公开
公开
技术领域
本发明涉及入侵检测技术，特别是涉及一种入侵检测中模式匹配的方法和装置。
背景技术
为了更好地保证网络安全，阻止破坏资源完整性、可用性和保密性等的入侵行为，目前提出一种可以识别未经授权或越权访问系统资源的行为的软、硬件系统，即入侵检测系统(IDS，Intrusion Detection System)。由于入侵检测系统能够实时地监控系统的活动，及时发现攻击行为并采取相应的抵御措施来避免进一步的攻击，减少攻击造成的危害，已成为目前网络安全研究的热点。
实现网络入侵检测常用的方法可以分为两类：一类是异常检测，另外一类是特征检测。其中，异常检测是根据对被检测系统的某种定量或定性的描述，得出一系列目标系统的正常统计数据和行为参量，一旦检测出这些参量发生了一定程度的偏离，则认为有异常发生。特征检测则是通过将当前网络数据包与已知攻击及系统漏洞的特征库进行模式匹配来发现入侵。由于异常检测需要长时间的学习才能提高检测的准确性，否则，其检测误报率比较高，很难适应大流量网络的实时检测要求，因此大多数网络入侵检测系统都采用基于模式匹配的检测方法。
模式匹配虽然具有易于实现，检测精度高等优点，但是网络速度的迅速提高以及模式库的日益增大，对基于模式匹配的网络入侵检测系统的实时检测性能提出了挑战。当待检测的网络数据流的产生速度超过了系统检测引擎的处理能力时，必然导致数据包来不及检测就被丢弃的情况出现。如果这些被丢弃的数据包含有具有攻击特征的恶意数据，入侵检测系统就会遗漏该攻击事件。攻击者往往会利用入侵检测系统的这一弱点，通过发送大量的数据包使系统过载而造成拒绝服务攻击(DoS，Denial of Service)或逃避入侵检测。因此，为了适应大流量网络的发展，必须提高基于模式匹配的入侵检测系统的性能。
在入侵检测系统性能评价中，模式匹配是一个重要的指标，也是入侵检测系统主要的性能瓶颈。常用的模式匹配有：BM、AC、AC-BM等。这些模式匹配方法虽然在理论上有较优的时间复杂度，但随着网络带宽的增加，在现有条件下单纯依赖软件方法来实现模式匹配，系统的性能往往难以达到实时检测的要求，必须考虑从硬件方面来寻求模式匹配问题的解决途径。
目前，提出一种利用三态内容可寻址存储器(TCAM，Ternary ContentAddressable Memory)进行的模式匹配方法，其大致思想是：将预先设置的各个模式输入一个TCAM中，直接利用TCAM对接收到的数据包中的字符串进行匹配。这里所述的模式就是为判定入侵行为的规则对应的字符串。如果TCAM中的模式与数据包中字符串匹配成功，则上报给系统。之后，系统就可以根据匹配结果进行相应的处理，比如丢弃、转发等。
在上述基于TCAM的模式匹配方法中，入侵系统整体性能基本取决于TCAM的查找速度。但由于TCAM本身在目前的工艺水平下，很难提高查询速度，已成为进一步提高入侵系统性能的瓶颈。在这种情况下，如果用于模式匹配的字符串比较多，就难以保证入侵检测系统性能的要求。
发明内容
有鉴于此，本发明实施例提供一种入侵检测中模式匹配的方法和装置，可以在模式匹配的字符串比较多的情况下，保持入侵检测系统的性能。
为了达到上述第一个目的，本发明提出的技术方案为：
一种入侵检测中模式匹配的方法，设置两个三态内容可寻址存储器TCAM，其中一个为头部TCAM，另外一个为尾部TCAM，该方法为：
将已有的用于模式匹配的各个模式字符串输入头部TCAM，并将所述输入头部TCAM的字符串首尾倒置后输入尾部TCAM；所述头部TCAM和尾部TCAM再分别同时从待检测数据的头部和尾部向中间依次进行模式匹配，并将匹配结果上报给系统。
为了达到上述第二个目的，本发明提出的技术方案为：
一种入侵检测中模式匹配的装置，该装置包括：
头部三态内容可寻址存储器TCAM，用于在匹配控制单元的控制下，根据输入给自身的模式字符串从缓冲区中头部数据开始进行模式匹配；
尾部TCAM，用于在匹配控制单元的控制下，根据输入给自身的模式字符串从缓冲区中尾部数据开始进行模式匹配；
匹配控制单元，用于将模式字符串输入给头部TCAM，将模式字符串首尾倒置后输入给尾部TCAM，将待检测数据输入给缓冲区，还用于控制头部TCAM和尾部TCAM分别同时从缓冲区中待检测数据的头部和尾部向中间依次进行模式匹配，并将匹配结果上报给系统；
缓冲区，用于保存待检测数据。
综上所述，本发明实施例提出的一种入侵检测中模式匹配的方法和装置，由于设置了两个三态内容可寻址存储器TCAM，即头部TCAM和尾部TCAM，所述头部TCAM和尾部TCAM分别同时从待检测数据的头部和尾部向中间依次进行模式匹配，可以提高整体的匹配速度，从而提高入侵检测系统的性能。
附图说明
图1是本发明方法实施例一的流程图；
图2是本发明方法实施例二中访问特征表的寻址方式示意图；
图3是本发明方法实施例二中TCAM_H、TCAM_T、计数器以及缓冲区的初始状态示意图；
图4是本发明方法实施例二的流程图；
图5是一种实现条件关联模式匹配时的示意图；
图6是本发明实现模式匹配的装置实施例的示意图。
具体实施方式
为使本发明的目的、技术方案和优点更加清楚，下面将结合附图及具体实施例对本发明作进一步地详细描述。
为了提高模式匹配的速度，本发明用两个三态内容可寻址存储器(TCAM)同时从待检测数据的头部和尾部向中间进行模式匹配，这里所述的两个TCAM，其中一个为头部TCAM，另外一个为尾部TCAM。
图1是应用本发明方案的实施例一的流程图。如图1所示，本实施例实现入侵检测中模式匹配的方法可以为：
步骤101：将已有的用于模式匹配的各个模式字符串输入头部TCAM，并将所述输入头部TCAM的字符串首尾倒置后输入尾部TCAM。
这里所述已有的用于模式匹配的各个模式字符串就是入侵检测系统规则库中的模式字符串，可以事先设置并存储在规则库中。至于如何设置所述的模式字符串则与实际的入侵检测系统相关，此处不再赘述。
另外，为了后续能够从待检测数据的尾部向中间进行模式匹配，需要字符串首尾倒置后再输入尾部TCAM。
步骤102：所述头部TCAM和尾部TCAM再分别同时从待检测数据的头部和尾部向中间依次进行模式匹配，并将匹配结果上报给系统。
这里所述待检测数据就是入侵检测系统所捕获到的数据包中的字符串，捕获之后，入侵检测系统就可以将所述数据包中的字符串输入缓冲区中，再利用头部TCAM和尾部TCAM同时从缓冲区的两端向中间进行匹配。
在匹配的过程中，根据TCAM中模式字符串之间的关系，可以将匹配的方式分为两类：一类是模式字符串之间无关联关系的匹配方法，另外一类是模式字符串之间有关联关系的匹配方法。这里所述关联关系指各个模式字符串彼此是否独立，如果每一个模式字符串匹配成功并不受其它模式字符串匹配结果的影响，那么，这些模式字符串就是独立的，或者说是无关联关系的。比如：有两个模式字符串，分别为“CHINA”和“CANADA”。如果从缓冲区待检测数据中成功匹配到“CHINA”，并且可以立即将其对应的规则号上报给系统，那么模式字符串“CANADA”对模式字符串“CHINA”并不造成影响。这种情况下，“CHINA”和“CANADA”就是无关联关系的模式字符串。又比如：从缓冲区待检测数据中成功匹配到“CHINA”和“CANADA”，并规则只有在“CHINA”和“CANADA”这两个模式字符串保持预先规定的顺序时，才可以将这两个有顺序的模式字符串对应的规则号上报给系统。这种情况下，“CHINA”和“CANADA”就是有关联关系的模式字符串。当然，实际应用中，模式字符串之间还可以存在其它的关联关系，此处不再详细描述。
另外，如果模式字符串的长度大于TCAM字宽，即长模式字符串，还需要将长模式字符串按照TCAM的字宽分割为子模式字符串，输入TCAM的模式字符串就为分割后的子模式字符串，以便于可以按照TCAM字宽依次对缓冲区中的字符串进行匹配。由于长模式字符串自身并不能在一次匹配中真正参与匹配，所以需要记录各子模式字符串匹配情况，并从各子模式字符串的匹配情况最终获取长模式字符串的匹配结果。实际应用中，可以用匹配表、部分命中列表等来记录各子模式字符串匹配情况，所述匹配表和部分命中列表一般保存在内存中。
由于访问内存比查找TCAM耗时要多得多，如果要提高模式匹配的整体性能，就需要控制访问内存的次数和占用内存的空间。
为了有效地减少访问内存的次数和占用内存的空间，可以为头部TCAM和尾部TCAM构造统一的匹配表，其构造方法可以为：
X1、先将每一个长模式字符串根据TCAM字宽进行划分，获得前缀子串、中缀子串和后缀子串的组合，所述前缀子串、中缀子串和后缀子串组合为一个完整的长模式字符串；
X2、再将所有划分出的前缀子串、中缀子串和后缀子串按照组合的对应关系填入匹配表，并为每一个前缀子串、中缀子串和后缀子串分配索引号；
X3、对于每一个组合，如果由前缀子串和中缀子串构成的新的前缀子串与匹配表中其它组合已有的前缀子串相同，则将所述其它组合已有的前缀子串的索引号作为所述构成新的前缀子串的组合信息记录下来；如果由后缀子串和中缀子串构成的新的后缀子串与匹配表中其它组合已有的后缀子串相同，则将所述其它组合已有的后缀子串的索引号作为所述构成新的后缀子串的组合信息记录下来；如果由前缀子串和后缀子串构成一个完整的长模式字符串，则直接将该完整的长模式字符串对应的规则号作为组合信息记录下来。
匹配表中各组合的前缀子串、中缀子串和后缀子串是对称的，头部TCAM所匹配到的前缀子串就是尾部TCAM所匹配到的后缀子串，头部TCAM所匹配到的中缀子串可以与尾部TCAM所匹配到的中缀子串相同，头部TCAM所匹配到的后缀子串则是尾部TCAM所匹配到的前缀子串。这样，头部TCAM和尾部TCAM就可以使用同一个匹配表，可以有效地节约内存空间。
同样，头部TCAM和尾部TCAM也可以使用同一个用于记录TCAM中字符串对应的类型值的特征表，此处不再赘述。
基于上述分析，下面分别对无关联关系、有顺序关联关系、有条件关联关系的匹配方法进行描述：
1、对于模式字符串之间无关联关系的情况，头部TCAM进行模式匹配的方法与尾部TCAM进行模式匹配的方法相同，都是各自从待检测数据的两端向中间进行匹配，并且在匹配到自身保存的每一个完整的短模式字符串或完整的长模式字符串时向系统上报。其匹配的具体方法可以为：
步骤A1：根据TCAM字宽从待检测数据确定TCAM的当前检测数据；
步骤A2：TCAM根据输入给自身的各个字符串与自身的当前检测数据进行匹配，如果匹配成功，则执行步骤A4；否则，执行步骤A3；
步骤A3：判断TCAM是否已经匹配完待检测数据的一半，如果已经匹配完，则退出本流程，如果没有匹配完，则TCAM向待检测数据的中间移动一个字符，确定新的当前检测数据，然后继续执行步骤A2；
步骤A4、判断TCAM匹配成功时所对应的字符串是否为长度不大于TCAM字宽的短模式字符串，如果是，则直接上报系统，再执行步骤A3；否则，通过在内存中查找事先构造的匹配表和自身的部分命中列表来确定匹配结果，如果仅匹配到完整的长模式字符串，则上报系统，再执行步骤A3；否则，则根据当前匹配情况更新自身部分命中列表，再执行步骤A3。
实际应用中，如果匹配成功时所对应的字符串既为短模式字符串又为长模式字符串的一部分，那么，可以先将匹配到短模式字符串的情况上报给系统，同时查找匹配表和自身的部分命中列表来确定匹配结果，如果匹配到完整的长模式字符串，就再次上报系统，然后执行步骤A3；否则，根据当前匹配情况更新自身部分命中列表，再执行步骤A3。
当然，如果匹配成功时所对应的字符串不是短模式字符串，而是长模式字符串的一部分，也可能在通过在内存中查找事先构造的匹配表和自身的部分命中列表后，既匹配到完整的长模式字符串又同时是某个更长的长模式字符串的一部分，那么不但要将匹配到的长模式字符串上报给系统，还需要根据当前匹配情况更新自身部分命中列表。
2、对于模式字符串之间有顺序关联关系的情况，用于模式匹配的n个模式字符串之间存在顺序关联关系，所述n为大于或等于2的整数，即P1P2P3…Pn这些模式字符串之间存在顺序。那么，每一个TCAM向中间依次进行模式匹配并将匹配结果上报给系统的方法为：
B1、根据TCAM字宽从待检测数据确定TCAM的当前检测数据；
B2、TCAM根据输入的字符串与自身的当前检测数据进行匹配，如果匹配成功，则执行步骤B4；否则，执行步骤B3；
B3、判断TCAM是否已经匹配完待检测数据，如果已经匹配完，则在匹配到所述保持顺序关联关系的n个模式字符串时，将所述保持顺序关联关系的n个模式字符串对应的规则号上报给系统，并退出本流程；如果没有匹配完，则向待检测数据的中间移动一个字符，确定各自新的当前检测数据，然后继续执行步骤B2；
B4、如果匹配成功时所对应的字符串是短模式字符串，则将所述短模式字符串记录下来，并判断记录下来的所有字符串是否保持顺序关联关系，如果是，则执行步骤B3；否则，退出本流程；
B5、如果匹配成功时所对应的字符串不是短模式字符串，则TCAM通过在内存中查找事先构造的匹配表和自身的部分命中列表来确定匹配结果，如果仅匹配到完整的长模式字符串，则执行步骤B6；如果匹配到长模式字符串的一部分，则根据当前匹配情况更新自身部分命中列表，再执行步骤B3；
B6、将所述长模式字符串记录下来，并判断记录下来的所有字符串是否保持所述顺序关联关系，如果是，则执行步骤B3；否则，退出本流程；
3、对于模式字符串之间存在条件关联关系的情况，又可以根据条件的不同分为两种基本类型：一类是在匹配成功时满足P1·Px·P2的条件，其中，P1和P2为两个输入给TCAM的模式字符串，Px为P1和P2之间长度为X的任意的字符串；另外一类则是在匹配成功时满足P1·Px·P2的条件，其中，P1、P2和Px的含义与P1·Px·P2条件中的含义相同，其区别仅仅在于匹配成功时，后一个字符串应该不是P2，即P2。
对于第一类条件关联关系的情况，即满足P1·Px·P2的条件，每一个TCAM向中间依次进行模式匹配并将匹配结果上报给系统的方法可以为：
C1、根据TCAM字宽从待检测数据确定TCAM的当前检测数据；
C2、TCAM根据输入的字符串与自身的当前检测数据进行匹配，如果匹配成功，则执行步骤C4；否则，执行步骤C3；
C3、判断TCAM是否已经匹配完待检测数据的一半，如果已经匹配完，则退出本流程；如果没有匹配完，则向待检测数据的中间移动一个字符，确定各自新的当前检测数据，然后继续执行步骤C2；
C4、如果匹配成功时所对应的字符串是短模式字符串，则记录下当前匹配成功时的位置，并在另一TCAM也匹配成功时，判断两个TCAM之间当前匹配的距离是否满足所述条件关联关系，如果满足，则将存在条件关联关系的两个模式字符串所对应的规则号上报给系统，并退出本流程；
C5、如果匹配成功时所对应的字符串不是短模式字符串，则TCAM通过在内存中查找事先构造的匹配表和TCAM的部分命中列表来确定匹配结果，如果仅匹配到完整的长模式字符串，则执行步骤C6；如果匹配到长模式的一部分字符串，则根据当前匹配情况更新自身部分命中列表，再执行步骤C3；
C6、记录下当前匹配成功时的位置，并在另一TCAM也匹配成功时，判断两个TCAM之间当前匹配的距离是否满足所述条件关联关系，如果满足，则将存在条件关联关系的两个模式字符串所对应的规则号上报给系统，并退出本流程。
对于第二类条件关联关系的情况，即满足P1PxP2的条件，每一个TCAM向中间依次进行模式匹配并将匹配结果上报给系统的方法可以为：
D1、根据TCAM字宽从待检测数据确定TCAM的当前检测数据；
D2、TCAM根据输入的字符串与自身的当前检测数据进行匹配，如果匹配成功，则执行步骤D4；否则，执行步骤D3；
D3、判断TCAM是否已经匹配完待检测数据的一半，如果已经匹配完，则退出本流程；如果没有匹配完，则向待检测数据的中间移动一个字符，确定各自新的当前检测数据，然后继续执行步骤D2；
D4、如果匹配成功时所对应的字符串是短模式字符串，则记录下当前匹配成功时的位置，并在两个TCAM之间匹配的距离满足所述条件关联关系时，判断另一TCAM是否匹配成功，如果没有匹配成功，则将存在条件关联关系的两个模式字符串所对应的规则号上报给系统，并退出本流程；
D5、如果匹配成功时所对应的字符串不是短模式字符串，则TCAM通过在内存中查找事先构造的匹配表和TCAM的部分命中列表来确定匹配结果，如果仅匹配到完整的长模式字符串，则执行步骤D6；如果匹配到长模式的一部分字符串，则根据当前匹配情况更新自身部分命中列表，再执行步骤D3；
D6、记录下当前匹配成功时的位置，并在两个TCAM之间匹配的距离满足所述条件关联关系时，判断另一TCAM是否匹配成功，如果没有匹配成功，则将存在条件关联关系的两个模式字符串所对应的规则号上报给系统，并退出本流程。
为了更好地说明本发明方案，下面用较佳实施例进行详细描述。
在实施例二中，输入给TCAM的模式字符串为无关联关系的模式字符串，分别为：P1＝“CANADA”、P2＝“CANADA-＞CHINA”、P3＝“CHINA”、P4＝“CHI”；TCAM的字宽为4，那么，P4为短模式字符串，P1～P3为长模式字符串；入侵检测系统捕获到的数据包中输入给缓冲区的字符串，即待检测数据为“CANADA-＞CHINA”。
本实施例中有两个TCAM，一个为头部TCAM，记为TCAM_H；另外一个为尾部TCAM，记为TCAM_T。在将模式字符串输入TCAM中时，如果为短模式字符串，则直接输入，并且在长度不足TCAM字宽时用通配符“？”补足，表示可以忽略“？”处的字符，即“？”处的字符可以为任意的字符。如果是长模式字符串，为了便于TCAM进行匹配，需要将各个长模式字符串分割为子模式字符串。分割时，可以按照TCAM的字宽进行分割，如果最后一个子串不足TCAM字宽长度，就可以利用上一个子串的尾部将其补足4个字符。这样，本实施例中输入给头部TCAM的字符串有6个，分别为“CANA”、“NADA”、“DA-＞”、“CHIN”、“HINA”、“CHI？”。同时，将输入给头部TCAM的字符串首尾倒置后，再输入给尾部TCAM。
实际应用中，按照上述的分割方式在某些特殊情况下可能会产生问题。例如：长模式字符串“CANADA”和“CANANADA”分割后会产生一样的子模式字符串，即“CANA”和“NADA”。这样，在匹配成功时就不知道应该将“CANA”和“NADA”合并为“CANADA”还是“CANANADA”。上述这种现象可以称为“分割冲突”。所以，实际应用中，如果存在分割冲突的长模式字符串，可以将其最后一个子串改成以“？”来补足，即将“CANADA”分割成“CANA”和“DA？？”，将“CANANADA”分割成“CANA”和“NADA”，便可以消除冲突。
另外，本实施例中，为了记录匹配时字符串的在待检测数据中的位置，还可以设置一个计数器Counter，并将其初始值设置为缓冲区的长度13。进行匹配时，每一个TCAM在一个时钟节拍完成一个匹配操作，计数器Counter在一个时钟节拍结束时减2，不但可以指示头部TCAM和尾部TCAM匹配数据之间的距离，还可以指示待检测数据是否已经匹配完。
从上述分析的情况来看，本实施例匹配过程中可能出现三种情况：第一种情况是匹配到短模式字符串，可以直接上报给系统；第二种情况是匹配到长模式字符串的前缀子串，则需要记录当前匹配情况；第三种情况是匹配到长模式字符串的后缀子串，可以与之前已经匹配的部分组合为完整的长模式字符串并上报给系统。其中，第二种和第三种情况都涉及长模式字符串，可以在静态内存(SRAM)中构造匹配表、特征表和部分命中列表，并在匹配过程中由匹配表、特征表和部分命中列表配合。
构造头部TCAM和尾部TCAM统一的匹配表时，首先需要将每一个长模式字符串根据TCAM字宽进行划分，获得前缀子串、中缀子串和后缀子串的组合。以“CANADA-＞CHINA”这里长模式字符串为例，其组合状态可以如表一所示：
表一
其次，将所有划分出的前缀子串、中缀子串和后缀子串按照组合的对应关系填入匹配表，并为每一个前缀子串、中缀子串和后缀子串分配索引号。本实施例中，可以按照出现的顺序为前缀子串、中缀子串和后缀子串分配索引号。这里所述匹配表的格式可以如表二所示：
表二
再次，对于每一个组合，在TCAM_H匹配时，如果前缀子串和中缀子串构成的新的前缀子串与匹配表中其它组合的前缀子串相同，则将所述其它组合已有的前缀子串的索引号作为所述构成新的前缀子串的组合信息记录下来；如果由后缀子串和中缀子串构成的新的后缀子串与匹配表中其它组合已有的后缀子串相同，则将所述其它组合已有的后缀子串的索引号作为所述构成新的后缀子串的组合信息记录下来；如果由前缀子串和后缀子串构成一个完整的长模式字符串，则直接将该完整的长模式字符串对应的规则号作为组合信息记录下来。
比如：匹配表第三行中，前缀子串“CANA”和中缀子串“DA-＞”构成的新的前缀子串为“CANADA-＞”，并且经与匹配表第四行中的前缀子串相同，那么，可以将第四行前缀子串的索引号作为第三行中TCAM-H匹配对应的组合信息记录下来。又比如：匹配表第五行，后缀子串“HINA”和中缀子串“CHIN”构成新的后缀子串为“CHINA”，并且与匹配表第三行中的后缀子串相同，那么，可以将第三行后前缀子串的索引号作为第五行中TCAM-T匹配对应的组合信息记录下来。再比如：匹配表第一行的前缀子串和后缀子串可以组合为一个完整的长模式字符串“CANADA”，则将“CANADA”对应的规则号作为组合信息记录下来。匹配表中其它的组合信息都可以按照上述的方式获取，此处不再赘述。之后，所述匹配表可如表三所示：
表三
实际应用中，匹配表可以存储在一个三维数组里，匹配表中前三列索引号可以作为三维数组的下标，后面两列的项作为每个数组元素存储的内容。这样，就可以保证仅需一次内存访问即可找到相应的项，以达到减少内存访问的次数的目的。比如：给定三元地址(1，0，1)就可以查询到匹配表的第一项。假设前缀索引、中缀索引和后缀索引的最大值分别为h、b和t，则三维数组大小为h*b*t项，且实际占用空间与匹配表的项数无关。这是因为数组空间一经分配便可以固定，匹配表项数只影响数组的利用率。可以推证，若一个长模式字符串包含n个中缀子串，则该长模式会在匹配表中产生2*n+1项，特别地，若n＝0则只产生一项，例如“CANADA”在匹配表中仅产生一项。所以，对于包含m个长模式字符串的匹配表，数组空间利用率可以近似估算为其中ni表示第i个长模式字符串所包含的中缀子串数。
本实施例中，当匹配表构造完成后，为了便于在匹配过程中确定匹配到的字符串的类型值，可以事先设置一个头部TCAM和尾部TCAM共同的特征表。其中，如果字符串为短模式字符串，则类型值为短模式字符串对应的规则号，如果字符串为前缀子串、中缀子串或后缀子串，则类型值为对应的索引号。这样，本实施例的特征表可以如表四所示：
表四
在表四中可以看到，“CANA”为前缀子串，其对应的索引号为1；“NADA”为后缀子串，其对应的索引号为1；“DA-＞”为中缀子串，其对应的索引号为1；“CHIN”包括了短模式字符串，同时也为前缀子串和中缀子串，对应的索引号分别为4和2；“HINA”为后缀子串，其对应的索引号为4；“CHI？”为短模式字符串。
实际应用中，为了更好地访问特征表，可以采用基址+偏移地址的寻址机制。比如：利用TCAM提供的索引值，加上特征表的基地址组成一个实际地址，再利用这里实际地址来访问特征表，其访问方式可以如图2所示。
图3是本实施例在开始进行模式匹配时，TCAM_H、TCAM_T、计数器Counter、缓冲区的初始状态。如图3所示，所述TCAM_H已经输入参与匹配的各个字符串，所述TCAM_T已经输入首尾倒置的各个字符串，所述计数器Counter的值为13，所述缓冲区中待检测数据为“CANADA-＞CHINA”。
图4是本实施例实现模式匹配的流程图。如图4所示，本实施例可以包括以下步骤：
步骤401：在第一个时钟节拍中，将缓冲区中待检测数据头部的4个字符作为TCAM_H的当前检测数据，将缓冲区中待检测数据尾部的4个字符作为TCAM_T的当前检测数据；
步骤402：TCAM_H将自身当前检测数据与自身保存的各个字符串进行匹配，并匹配到字符串“CANA”，TCAM_T将自身当前检测数据与自身保存的各个字符串进行匹配，并匹配到字符串“HINA”；
步骤403：通过查询特征表确定匹配到的字符串“CANA”为前缀子串，对应的索引号为1，将该索引号添加到TCAM_H的部分命中列表中；同时，通过查询特征表确定匹配到的字符串“HINA”为后缀子串，对应的索引号为4，将该索引号添加到TCAM_T的部分命中列表中。
这里，需要注意的是，由于TCAM_T是从缓冲区的尾部逆向开始匹配的，在匹配表查询到的后缀子串实际上是TCAM_T匹配到的前缀子串，相应的索引号应该前缀索引。另外，为了便于记录匹配成功时字符串所在的位置，可以将计数器Counter的当前值13记录在两个部分命中列表中。所述两个部分命中列表分别为表五和表六，其中表五为TCAM_H的部分命中列表，表六为TCAM_T的部分命中列表。
表五 表六
步骤404：根据计数器Counter的值判断出还没有匹配完待检测数据，TCAM_H向中间移动一个字符，确定新的当前检测数据为“ANAD”；同时，TCAM-T向中间移动一个字符，确定新的当前检测数据为“CHIN”，计数器Counter的值减2；
此时，将开始第二个时钟节拍中的匹配工作。
步骤405：在第二个时钟节拍中，TCAM_H将自身当前检测数据“ANAD”与自身保存的各个字符串进行匹配，并确定此次无成功的匹配；同时，TCAM_T将自身当前检测数据“CHIN”与自身保存的各个字符串进行匹配，并确定匹配到字符串“CHIN”；
步骤406：通过查询特征表确定TCAM_T匹配到的字符串“CHIN”是索引号为2的中缀子串，再联合TCAM_T的部分命中列表中已有的索引号4查询匹配表，将匹配表中新构成的后缀子串对应的索引号3添加到TCAM_T的部分命中列表中。
这里需要注意的是，TCAM_T部分命中列表中记录的前缀索引实际上是匹配表中后缀子串对应的索引，所以，联合中缀子串索引号2和TCAM_T部分命中列表中的索引号4，实际上则是查询匹配表中缀索引为2，后缀索引为4的项，并确定该项中TCAM_T匹配对应的组合信息为3，即：当前匹配成功时的字符串并不是一个完整的长模式字符串的规则号，而是部分字符串对应的索引号。
本步骤中，通过查询特征表确定TCAM_T匹配到的字符串“CHIN”是索引号为2的中缀子串，而实际上，“CHIN”也同时是一个索引号为4的后缀字符串，并可以与TCAM_T部分命中列表中的索引号联合查询匹配表，获取完整的长模式字符串“CHINA”，上报给系统。但至于是仅将匹配到的长模式字符串上报给系统；或者仅匹配一个更长的长模式字符串的一部分；或者既将匹配到的长模式字符串上报给系统，又匹配一个更长的长模式字符串的一部分，则与实际的设计相关，此处不再详细叙述。
另外，本步骤执行后，TCAM_H的部分命中列表保持不变，而TCAM_T的部分命中列表更新为表七：
表七
步骤407：根据计数器Counter的值判断出还没有匹配完待检测数据，TCAM_H向中间移动一个字符，确定新的当前检测数据为“NADA”；同时，TCAM-T向中间移动一个字符，确定新的当前检测数据为“＞CHI”，计数器Counter的值减2；
此时，将开始第三个时钟节拍中的匹配工作。
步骤408：在第三个时钟节拍中，TCAM_H将自身当前检测数据“NADA”与自身保存的各个字符串进行匹配，并确定匹配到字符串“NADA”；同时，TCAM_T将自身当前检测数据“＞CHI”与自身保存的各个字符串进行匹配，并确定匹配到字符串“CHI”；
步骤409：通过查询特征表确定TCAM_H匹配到的字符串“NADA”是索引号为1的后缀子串，再联合TCAM_H的部分命中列表中已有的索引号1查询匹配表，确定匹配到完整的长模式字符串“CANADA”，并将对应的规则号上报给系统；同时，通过查询特征表确定TCAM_T匹配到的字符串为短模式字符串，并将对应的规则号上报给系统；
步骤410：根据计数器Counter的值判断出还没有匹配完待检测数据，TCAM_H向中间移动一个字符，确定新的当前检测数据为“ADA-”；同时，TCAM-T向中间移动一个字符，确定新的当前检测数据为“-＞CH”，计数器Counter的值减2；
此时，将开始第四个时钟节拍中的匹配工作。
步骤411：在第四个时钟节拍中，TCAM_H将自身当前检测数据“ADA-”与自身保存的各个字符串进行匹配，并确定无成功匹配；同时，TCAM_T将自身当前检测数据“-＞CH”与自身保存的各个字符串进行匹配，并确定无成功匹配；
步骤412：根据计数器Counter的值判断出还没有匹配完待检测数据，TCAM_H向中间移动一个字符，确定新的当前检测数据为“DA-＞”；同时，TCAM-T向中间移动一个字符，确定新的当前检测数据为“A-＞C”，计数器Counter的值减2；
此时，将开始第五个时钟节拍中的匹配工作。
步骤413：第五个时钟节拍中，TCAM_H将自身当前检测数据“DA-＞”与自身保存的各个字符串进行匹配，并确定匹配到字符串“DA-＞”；同时，TCAM_T将自身当前检测数据“A-＞C”与自身保存的各个字符串进行匹配，并确定无成功匹配；
步骤414：通过查询特征表确定TCAM_H匹配到的字符串“DA-＞”是索引号为1的中缀子串，再联合TCAM_H的部分命中列表中已有的索引号1查询匹配表，将匹配表中新构成的前缀子串对应的索引号2添加到TCAM_H的部分命中列表中。
本步骤中，更新后的TCAM_H的部分命中列表可以如表八所示：
表八
实际应用中，假设TCAM字宽为w，每经过一个时钟节拍后计数器Counter值减2，不难推证，当部分命中列表中两项位置差大于或等于2w时，就可以将前一项删除。这是由于表中两项位置差大于或等于2w时，各自对应的字符串的距离在待检测数据中相差大于或等于w，说明TCAM已经移动了w或w以上的字符，即使再有匹配的情况发生，也不会与前一项字符串进行组合了。此时，前一项的信息已经无法被后续的匹配过程利用。为了节约部分命中列表的大小，减少访问部分命中列表的时间，可以将已经无用的项删除。在本实施例中，由于步骤414中，TCAM_H部分命中列表的第一项与第二项的位置差为8，等于2倍TCAM字宽，可以将其删除。这样，TCAM_H的新的部分命中列表可以如表九所示：
表九
步骤415：将TCAM_H和TCAM_T各自部分列表中保存的索引号进行组合，并根据组合结果查询匹配表，如果匹配到完整的长模式字符串，则将匹配表中对应的规则号上报给系统。
本步骤中，由于TCAM_H保存有索引号2，TCAM_T保存有索引号4和3，可以分别组合成(索引2，索引4)以及(索引2，索引3)，再利用每一个组合查询匹配表。需要注意的是，这里所述索引号在部分命中列表中都是前缀索引，但实际上TCAM_T的前缀索引在匹配中应该对应为后缀子串。也就是说，如果以(索引2，索引4)去查询匹配表，实际上是以前缀索引2和后缀索引4去查询匹配表，并确定无法构成一个完整的长模式字符串。如果以前缀索引2和后缀索引3去查询匹配表，则可以匹配出一个完整的长模式字符串“CANADA-＞CHINA”，并将对应的规则号上报给系统。
至此，本实施例匹配到三个完整的模式字符串，一个为步骤409中由TCAM_H匹配到的“CANADA”，一个为步骤409中TCAM_T匹配到的“CHI”，另外一个为步骤415中TCAM_H和TCAM_T共同匹配到的“CANADA-＞CHINA”。实际应用中，如果某字符串匹配成功时，既将匹配到的长模式字符串上报给系统，又匹配一个更长的长模式字符串的一部分，那么，本实施例步骤405中TCAM_T还匹配到了“CHINA”。当然，由于本实施例各个模式字符串无关联关系，匹配后可以立即将对应的规则号上报给系统，系统再根据规则号对应的动作对数据包进行相关处理，比如：报警、丢弃、转发等等。至于各个模式字符串对应的规则号以及动作，则与具体的实现相关，此处不再详细描述。
本实施例中，当TCAM_H和TCAM_T匹配到待检测数据的中间时，各自的部分命中列表中也可能没有仍然保存的索引号，则无需执行步骤415。
另外，本实施例是以各个模式字符串为无关联关系为例来说明本发明方案的。实际应用中，如果各个模式字符串有关联关系，其实现方法与本实施例相似，其区别在于：
对于各个模式字符串有顺序关联关系的情况来说，即P1P2P3...Pn这些模式字符串之间存在顺序。当TCAM_H和TCAM_T匹配到完整的模式字符串时，不会马上上报给系统，而是暂时记录下来，等到所有的模式字符串全部匹配成功，并且保持顺序时，才可以将P＝P1P2P3...Pn对应的规则号上报给系统。
对于各个模式字符串有条件关联关系的情况来说，即需要满足P1·Px·P2的条件或满足P1·Px·P2的条件。以满足P1·Px·P2为例，当TCAM_H和TCAM_T各自从待检测数据两端匹配到模式字符串P1和模式字符串P2时，不能马上上报给系统，而是判断两个字符串之间是否存在某个符合长度的任意的字符串，只有在满足这种条件下，才将P＝P1·Px·P2对应的规则号上报给系统。比如：
一条针对POP3协议溢出攻击的规则为：“content：USER；nocase；content：！’0a’；within：128”，表示如果在检测到“USER”之后128个字符内没有检测到回车符，就认为是一次攻击。如图5所示，假设缓冲区长度为256个字符，TCAM_H在第100个字符处检测到“USER”，如果TCAM_T在第156到228的位置内已经检测到回车符，则可以马上判断这不是一个攻击，而无需继续向中间进行匹配。如果TCAM_T在第156到228的位置内没有检测到回车符，则最多还需(256-2*100)/2＝28步就可以判断出结果，TCAM_H的部分命中列表中与匹配到“USER”相关的信息只需要保留28个时钟节拍。这样，利用本实施例中的TCAM_H和TCAM_T两个TCAM同时向待检测数据的中间进行匹配，不但可以大大减少匹配次数，而且可以防止攻击者利用“USER”和回车符之间的空隙设计攻击数据，从而可以有效地提高模式匹配的性能。
针对上述实现模式匹配的方法，本发明还提出一种实现模式匹配的装置。该装置实施例可以如图6所示，包括：
头部TCAM601，用于在匹配控制单元603的控制下，根据输入给自身的模式字符串从缓冲区604中头部数据开始进行模式匹配；
尾部TCAM602，用于在匹配控制单元603的控制下，根据输入给自身的模式字符串从缓冲区604中尾部数据开始进行模式匹配；
匹配控制单元603，用于将模式字符串输入给头部TCAM601，将模式字符串首尾倒置后输入给尾部TCAM602，将待检测数据输入给缓冲区603，还用于控制头部TCAM601和尾部TCAM602分别同时从缓冲区604中待检测数据的头部和尾部向中间依次进行模式匹配，并将匹配结果上报给系统；
缓冲区604，用于保存待检测数据。
实际应用中，为了更好地控制头部TCAM601和尾部TCAM602的匹配工作，该装置还可以进一步包括：
计数器605，可以为一个寄存器，用于记录头部TCAM601和尾部TCAM602所匹配字符串之间的距离。
时钟产生单元606，用于生成时钟信号，并输出给头部TCAM601、尾部TCAM602和匹配控制单元603。
当然，如果TACM中包括长模式字符串，不能一次匹配成功，可以构造匹配表、特征表和部分命中列表来实现匹配。所述匹配表、特征表和部分命中列表用于记录与长模式字符串匹配相关的信息，可以保存在长模式信息存储单元607中，所述长模式信息存储单元607可以是内存，比如采用静态内存(SRAM)来实现。至于匹配表、特征表和部分命中列表中的具体信息可以参见上述方法的相关描述，此处不再赘述。
当需要进行模式匹配时，匹配控制单元603将模式字符串输入头部TCAM601中，并将模式字符串首尾倒置后输入尾部TCAM602中，将捕获到的数据包中待检测数据输入缓冲区604中，并设置计数器初始值。之后，当匹配控制单元603接收到时钟产生单元606所产生的时钟时，在时钟节拍内，控制头部TCAM601和尾部TCAM602分别同时从缓冲区中待检测数据的头部和尾部向中间依次进行模式匹配，并将匹配结果上报给系统。当然，在匹配过程中，如果匹配的字符串为长模式字符串，还可能需要访问长模式信息存储单元607，查询其中的匹配表、特征表和部分命中列表。另外，在每一个时钟节拍结束时，匹配控制单元603还需要控制计数器605减2，以记录头部TCAM601和尾部TCAM602所匹配字符串之间的距离。
当然，如果TCAM中都是短模式字符串，则可以不用设置长模式信息存储单元607。如果无需获取匹配成功时字符串的位置，匹配控制单元603事先可以知道需要匹配多少个时钟节拍就可以完成缓冲区中待检测数据的匹配，也可以不设置计数器605。
实际应用中，用于入侵检测的规则很多，比如可以达到3000条以上，其中95％以上对应的模式字符串长度小于30，其中又有超过70％的长度小于20。现有的制造工艺可以使单片TCAM的容量达到20Mbit以上。如果使用本方案，只需要使用16Mbit的芯片，并将其配置为字宽64字节、深度32k，即可容纳所有的模式字符串，并可以使大部分归为短模式字符串。由于实际应用中，长模式需要被分割为3个以上子串的情况比较少，本发明实施例中构造的匹配表将不会占有很多内存。当然，如果所有的长模式都无需划分成3个或以上子串的话，也可以将匹配表和特征表的中缀索引一列去掉。
另外，本发明实施例中是以两个TCAM为例进行说明的，实际应用中，还可以使用4个、8个等更多的TCAM同时进行匹配。比如：用两个TCAM从待检测数据的前半部进行匹配，另外两个TCAM从待检测数据的后半部进行匹配，其匹配的方法可以与本实施例中提供的方法相同。
应用本发明方案，由于使用两个TCAM从待检测数据的两端同时向中间匹配，不但可以提高TCAM的查询速度，将入侵检测系统的性能提高一倍，而且在关联模式匹配的情况下，可以有效防止攻击者的攻击，保证系统的性能。另外，由于头部TCAM和尾部TCAM可以同时访问相同的匹配表和特征表，从而可以减少内存空间开销，节约资源，也可以减少访问内存的次数，提高匹配的效率。
综上所述，以上仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
机译： 使用基于Perl兼容正则表达式的模式匹配技术的网络入侵检测装置和方法
机译： 入侵检测/预防系统的模式匹配方法和装置
机译： 入侵检测/预防系统的模式匹配方法和装置
