一种基于二叉表达式树预编译的短路求值规则匹配方法及系统与流程

摘要: 本发明属于计算机软件、网络安全与流量分析,具体提供了一种用于网络流量异常检测的规则匹配方法及系统。背景技术:1、随着网络安全监测和流量分析需求的持续增长,深度包...
一种基于二叉表达式树预编译的短路求值规则匹配方法及系统与流程

本发明属于计算机软件、网络安全与流量分析,具体提供了一种用于网络流量异常检测的规则匹配方法及系统。

背景技术:

1、随着网络安全监测和流量分析需求的持续增长,深度包检测(dpi, deep packetinspection)系统需要在极高报文处理速率下,通常为每秒百万级报文数量,对每个数据包的元数据字段,如ip地址、端口号、协议类型、http url、tls(传输层安全)证书字段、dns查询域名等,进行实时规则匹配,以判断该报文是否命中预定义的检测规则,并触发相应的处置动作,如告警、丢弃、上报等。

2、规则通常以包含多层逻辑组合的布尔表达式形式给出,涵盖关系运算、算术运算、字符串匹配、正则匹配及逻辑and/or组合,例如:

3、

4、上面示例中,第一行用于检测http请求的url路径,当访问以/login(登录页)或/admin(管理页)开头的链接时会触发;第二行检查http响应状态码是否为200;第三行包含两个逻辑或判断:ip数据包的生存时间ttl大于64,或者源ip地址为192.168.1.100。在百万包/秒的处理速率下,每个数据包可用于规则匹配的时间仅为微秒量级。如何高效地对包含多层逻辑组合的规则表达式进行求值,是规则引擎性能的核心瓶颈。

5、现有技术存在基于运行时解析的规则引擎,将中缀规则表达式字符串与规则一起存储,在每次报文到来时对中缀字符串进行实时词法分析和语法分析,动态生成求值计划后执行匹配。但这种方案存在如下缺陷:词法分析和语法分析的时间复杂度与表达式字符串长度成正比,每次报文匹配均需重复执行完整解析过程,在百万包/秒的处理速率下,累积解析开销极大;在规则匹配吞吐量达到百万包/秒时,解析开销占总处理时间的比例超过50%,严重制约系统性能。

6、现有技术还存在基于传统后缀表达式顺序求值的引擎,将中缀表达式预先转换为后缀表达式(逆波兰表达式),在匹配时通过操作数栈按顺序遍历后缀表达式的每个元素执行计算。这种方案消除了运行时解析开销,但存在以下核心缺陷:后缀表达式的顺序求值模型要求对每个操作数均进行完整计算,不支持逻辑短路。以规则"a && b && c && d && e"为例,当子条件a不满足时,按照逻辑短路原则,子条件b、c、d、e的求值对整体结果没有任何影响,但该方案仍然完整地执行b、c、d、e的计算,造成大量无效计算开销。

技术实现思路

1、现有技术对每秒百万级网络包进行实时规则匹配的安全检测时,若采用中缀规则表达式求值方式存在解析开销大的问题,若采用后缀表达式顺序求值方式存在大量无效计算开销的问题。本发明的目的是提供一种基于二叉表达式树预编译的短路求值规则匹配方法及系统,以解决现有技术网络流量实时规则匹配时存在的运行期构建开销大、不支持逻辑短路、cpu缓存局部性差、多线程锁竞争以及缺乏自适应路径选择和热更新过渡保障等问题。

2、本发明提供的一种基于二叉表达式树预编译的短路求值规则匹配系统,包括操作符注册模块、中缀转后缀编译器、字符串预编译器、合法性验证模块、树预构建模块以及三级自适应求值引擎。所述系统加载用于网络流量检测的规则,所述规则为使用中缀规则表达式的字符串;编译器为每条规则创建一个规则对象存入预设的存储区域,所述规则对象包含逻辑运算符标志has_logic_ops、后缀表达式数组item、字符串池mpool以及二叉表达式树;所述二叉表达式树包含一个用于存储树中节点的固定字节数组expr_heap,以及一个缓存树的根节点指针的字段expr_root;所述标志has_logic_ops初始为假。

3、在编译期,操作符注册模块将规则中的操作符注册到设备操作系统的操作符映射表中;中缀转后缀编译器将规则的中缀表达式转换为后缀表达式数组,并存入规则对象中;中缀转后缀编译器在将中缀表达式转换为后缀表达式数组的过程中,将检测到的字符串存入字符串池mpool,在将逻辑操作符and或or写入后缀表达式数组时,同步设置标志位has_logic_ops为真;字符串预编译器对规则中的字符串常量操作数执行预编译;合法性验证模块对规则中的协议要素操作数执行合法性验证;树预构建模块进行二叉树预构建,包括:若一条执行路径中标志位has_logic_ops为真,通过节点栈将后缀表达式数组还原为二叉表达式树,将树的全部节点连续存储在规则对象的固定字节数组expr_heap中,将根节点指针缓存于expr_root字段;树中节点以区间索引(start, end)引用后缀表达式数组中的操作数或操作符。

4、在运行期,三级自适应求值引擎读取编译器存储的规则对象的后缀表达式数组、字符串池以及二叉表达式树,对报文实时匹配,自适应选择求值路径,输出匹配结果;所述自适应选择求值路径包括:检查expr_root和has_logic_ops,若expr_root非空执行路径1,若expr_root为空且has_logic_ops为真执行路径2,若has_logic_ops为假执行路径3;其中,路径1通过递归遍历二叉表达式树执行短路求值,若and节点左子树为假时立即截断,若or节点左子树为真时立即截断;路径2在热更新过渡期通过线程本地堆动态构建临时树后执行短路求值;路径3直接线性遍历后缀表达式数组执行求值。

5、相应地,本发明提供的一种基于二叉表达式树预编译的短路求值规则匹配方法,在编译期执行步骤1-5,在运行期执行步骤6,包括:

6、步骤1,编译器为加载的中缀表达式的规则创建一个规则对象存入预设的存储区域,对规则执行操作符注册,将规则中的操作符注册到设备操作系统的操作符映射表中;所述规则对象包含逻辑运算符标志has_logic_ops、后缀表达式数组item、字符串池mpool以及二叉表达式树;所述二叉表达式树包含一个用于存储树中节点的固定字节数组expr_heap,以及一个缓存树的根节点指针的字段expr_root;所述标志has_logic_ops初始为假;

7、步骤2,将规则的中缀表达式转换为后缀表达式数组,并存入规则对象中;在将中缀表达式转换为后缀表达式数组的过程中,将检测到的字符串存入字符串池mpool,在将逻辑操作符and或or写入后缀表达式数组时,同步设置标志位has_logic_ops为真;

8、步骤3,对规则中的字符串常量操作数执行预编译;所述字符串常量操作数从字符串池mpool中读取;

9、步骤4,对规则中的协议要素操作数执行合法性验证;

10、步骤5,进行二叉树预构建,包括:若一条执行路径中标志位has_logic_ops为真,通过节点栈将后缀表达式数组还原为二叉表达式树,将树的全部节点连续存储在规则对象的固定字节数组expr_heap中,将根节点指针缓存于expr_root字段;树中节点以区间索引(start, end)引用后缀表达式数组中的操作数或操作符计算范围;

11、步骤6,对报文实时匹配时,读取编译器存储的规则对象的后缀表达式数组、字符串池以及二叉表达式树,自适应选择求值路径,输出匹配结果;

12、所述自适应选择求值路径包括:检查expr_root和has_logic_ops,若expr_root非空执行路径1,若expr_root为空且has_logic_ops为真执行路径2,若has_logic_ops为假执行路径3;其中,路径1通过递归遍历二叉表达式树执行短路求值,若and节点左子树为假时立即截断右子树求值,若or节点左子树为真时立即截断右子树求值;路径2在热更新过渡期通过线程本地堆动态构建临时树后执行短路求值;路径3直接线性遍历后缀表达式数组执行求值。

13、本发明的优点与积极效果在于:

14、(1)本发明方法及系统首先将网络流量检测规则的中缀表达式通过调度场算法转换为后缀表达式数组,在规则加载阶段,将后缀表达式还原为二叉短路求值表达式树,并将其缓存至规则对象内部的固定存储区,然后在报文实时匹配阶段,通过三级自适应路径实现逻辑短路,从而完成规则匹配。本发明方法及系统通过短路求值大幅减少无效计算,能应用于高并发、低时延的网络深度包检测场景。

15、(2)本发明方法及系统通过预构建树消除运行期构建开销,提升cpu缓存局部性,所有树节点连续存储于物理地址连续的固定字节数组,提升了l1/l2 cache命中率,树节点不复制操作数/操作符数据,仅存储区间索引共享后缀数组,显著降低了内存占用。

16、(3)本发明方法及系统在三级自适应路径选择时,仅需检查2个字段,时间复杂度o(1),并且三种路径兼顾各类规则,保障规则热更新过渡期时的匹配连续性。设置多个并发匹配线程,各线程使用独立的堆空间,无任何互斥锁或原子操作,匹配吞吐量可随cpu核数线性扩展。