基于特征值的多模式匹配算法及硬件实现

摘要

本文提出并用硬件实现了基于特征值的多模式匹配算法。字符串特征值是由异或电路或模3、模5等硬件电路直接计算得出(如图1、2、4、5所示)，无需CPU干预。匹配过程是先按模式字符串的长度和模式字符串的特征值把模式库组织成树形结构(如图3所示)，然后采用地址直接映射的方法，来完成对模式特征值的搜索匹配过程(如图6所示)。基于特征值匹配算法的实质是采用两次匹配的思想，第一次匹配过滤掉大量正常的数据包，第二次对可疑数据包进行进一步的匹配确认。第一次匹配完全由硬件实现，第二次匹配可以由硬件实现也可由CPU承担。当由CPU处理时，需要第二次匹配确认的数据量不到网络总流量的0.4％，甚至更低。通过实验验证，本算法可以满足高速网络误用入侵检测的要求。

主权项

1、基于特征值的多模式匹配算法及硬件实现，采用两次匹配的方法：第一次匹配过滤掉大量正常的数据包，第二次对可疑数据包进行进一步的匹配确认；第一次匹配完全由硬件实现，第二次匹配可以由硬件实现也可由CPU承担。