RETE算法并行化改进及在大规模规则匹配场景中的应用(2)
1.2 研究意义
基于规则的系统（RBS）有着广泛的应用，如商务智能，网络入侵检测等等。随着网络的不断扩大，对于网络安全技术的需求快速增加。如何提高安全管理效率，同时降低安全管理成本是必须要解决的问题，以规则为基础的网络安全管理系统应运而生。针对大规模Web应用日志安全事件分析应用需求，采用并行化Rete算法以规则匹配方式针对Web用户日志进行大数据分析功能，发觉已被定义的网络安全事件，建立异常行为规则集，从而快速发现网络入侵行为，保证网络安全。本课题最终目的就是设计并实现并行化RETE算法，验证改进的算法在大数据处理场景中实时规则匹配的效率。
1.3 本文结构
本论文的组织结构如下：第二章介绍一些背景知识，以及RETE算法其并行化的相关发展和研究现状。第三章描述解决方案的架构设计和关键技术的解析。第四章描述适用于大规模规则匹配的并行化RETE算法的具体实现，其中包括算法实现和关键技术的解决。第五章将会包括一些性能测试以及实验验证。第优尔章将会是对全文的总结，其中包含对研究课题的解决以及未解决的问题。
2 相关发展及其研究现状
2.1 RETE算法简介
2.1.1 RETE算法依据
2.1.2 RETE算法特点
2.2 RETE算法相关发展
RETE算法自从1979年首次被提出来，也经历了三十多年的历史，期间也经历了各种的改进和实现。其中包括了最明了的对于自身的RETE网络进行优化构造，同时也包括了一些不确定研究，模糊处理以及并行化的探讨。期间当然经历了很多困难，但是还是取得了一些进步。
2.2.1 结构优化
结构优化，就如其定义的名字一样，就是对构建的RETE网络进行优化，以便于提高RETE网络的灵活性和高效快速匹配。其中包含了：（1）混合逻辑符的处理。逻辑符号就是指and, not, or等逻辑符号。最原始的RETE算法设计时，只考虑了and逻辑符号。但慢慢的通过研究，RETE算法被设计的可以对除了and的其它逻辑符号进行操作。例如，在DROOLS中，就被设计成可以同时支持and和or逻辑符号的混合操作，但是DROOLS只是简单地在or逻辑符号之处，将规则切割成多条规则，这种方法将会造成大量的切割开销。（2）规则LHS部分的重排序。LHS部分的顺序就是指条件中各个模式的排列顺序，但这样会影响到条件各个模式进行连接操作的执行顺序，后续影响就是会造成中间存储状态大小的改变，这也会成为规则匹配效率的决定性因素。连接顺序不同将会影响到共享结点的数量，从而影响到匹配的效率。（3）索引方法。索引方法就是指在RETE网络中，在当前结点之中，建立对后继结点的索引，这样做的好处就是，当事实进行匹配时，如果匹配成功，就可以快速找到当前结点的后继结点继续进行匹配，而无需一个一个地进行查找，这将节省大量的时间，提高匹配的效率。DROOLS在RETE算法面向对象[7]的版本RETE-OO算法。此算法中就对类型结点（type-node）结点中加入了对后继alpha结点的索引，以事实（fact）属性为key，alpha结点为value，这样事实（fact）在通过了类型结点（type-node）的匹配验证之后，就可以顺序的找到后继结点alpha结点，继而进行后续匹配。相同的道理，对于beta结点中的左右存储区建立索引，进行快速查询。
2.2.2 功能扩展
RETE算法最初的设计，只是用来对于确定性的一阶布尔逻辑下的进行规制匹配操作。但是随着广泛应用其它逻辑，缺失数据的问题，逻辑模糊等问题的不断出现，对于传统的规则引擎的功能需求提出了更高的要求。为了解决这些复杂的问题，近年来对RETE算法不断的改进，进行了必要的扩展。（1）能够处理其余逻辑。RETE算法设计之时，只考虑了一阶的布尔逻辑的操作，因此最初的RETE算法只能对一阶布尔逻辑的表达式进行操作。近些年，RETE算法已经被扩展成能够处理其它的逻辑，并且产生了多种版本，比如像F-逻辑（F-logic），三值布尔逻辑（3-Valued Boolean）等。Florian等人研究在演绎数据库中用RETE算法进行面向集合的自底向上的规则匹配评估计算。而三值布尔逻辑广泛用于缺失数据的处理。（2）对于包含时间信息事件的处理。RETE算法是通过事实（fact）来表示当前的状态，但是有些应用中包含的一些事件流，它们中间的时间在事件的并发执行中却有着至关重要的作用。但是如前文所提到的，RETE算法其中包含的一个缺陷就是：RETE算法不提供对时间敏感模式表达的支持。这样就会催生出对于包含事件处理的RETE算法研究。其中的一种方法就是：引入包含时间戳的事件和事件之间的时间间隔的约束的概念，使得RETE算法可以对事实和事件在同一时间进行处理[6]。
下一篇：网络层不确定推理分析算法研究