论文部分内容阅读
随着信息化的不断发展,分布计算系统越来越复杂。系统运行中出现的各种异常,如网络通信系统中的病毒攻击、交通监控系统中的车辆阻塞、金融电子交易系统中隐藏的恶意洗钱等,必然会反映到系统信息状态的一系列异常变化。系统关注的信息状态变化便是事件。这就是说,系统异常与一系列事件之间存在必然联系。另一方面,在一系列事件内部,即事件与事件之间也肯定存在着某些逻辑的和时序的关系。若把涉及某种系统异常的一系列事件按其逻辑的和时序的关系组合起来,便产生了复合事件的概念。如何通过复合事件的识别及时发现和定位系统异常,是当前分布计算领域的热点研究课题。本文在分析国内外相关最新成果的基础上,围绕复合事件的描述语言、识别算法、实例筛选策略以及系统异常的主动预警技术展开深入研究,主要贡献包括:1、基于事件代数设计了复合事件的形式化描述语言CREWLan。该语言定义了事件结构,包含时序、逻辑运算的操作子,以及由操作子连接的复合事件递归生成法则。事件结构包含事件类型、发生时间和其它事件属性,其中事件发生时间由间隔时间戳表示。操作子基于事件结构和时间模型,规定了由其作用的事件在递归生成复合事件时具有的时序和逻辑关系。描述语言能清晰地表示系统异常所引起的一系列事件的结构和相互关系,具有很强的表达能力。本文给出了描述语言的BNF范式,并利用元语言工具ANTLR编译所得的语法解析器,可以为使用CREWLan描述的每个复合事件自动生成一棵代表该类系统异常的识别树。识别树中叶节点为来自外部环境的原子事件。多类系统异常对应的多棵识别树则可以构成一个森林。2、提出基于匹配限时策略的复合事件识别方法,并设计了相应的识别引擎。在网络环境下先发生的原子事件可能比后发生的原子事件晚到达系统,这就是所谓的乱序传输问题。匹配限时策略就是允许先期到达系统的原子事件等待某个时限后再进行时序匹配,可在一定程度上解决乱序传输的问题。进而,在多个复合事件识别树构成的森林中,由于多个识别树中往往存在若干语法相同,或语法不同但语义等价的节点,这些节点显然可以共享同一匹配过程。找到语法相同的共享节点已有现成算法,本文给出了基于代数等价性质的共享节点查找算法,从而有效降低了识别森林中的匹配时间。实验结果表明,在对多个复合事件进行识别的场景下,本文的识别引擎与其它类似系统相比,延迟要低25%,吞吐率要高40%。3、设计了基于最新留用原则的实例筛选策略及其实现算法,有效避免了复合事件识别过程中产生的实例数可能存在组合爆炸的问题。该策略按照最新留用原则,在复合事件识别过程中存在多个匹配实例时,只选择开始时间最新、结束时间相同的一个实例作为中间输出而归入下一步匹配实例中。代数性质的理论推理证明,该策略具有可递归应用到子复合事件的良好代数性质,其时空复杂性仅与识别树的深度D相关,为O(D2)。实验结果验证了该筛选策略的有效性。4、在忽略时序的弱复合事件中,设计了基于Top-k的系统异常主动预警方法。出于预警的需要,把复合事件仅看作一段时间内发生的无时序关系的事件集合。该方法将各种系统异常所对应的复合事件的重要性、发生概率等信息存储在数据库中并构建相应的索引,并基于Top-k,对滑动窗口内的原子事件连续计算此时复合事件的发生概率与重要性的综合值,把综合值最大的k个复合事件作为结果输出,而不必等待与复合事件相关的原子事件全部到达就可进行预警。该方法使用排序的访问阶段进行预处理,减少计算中占主要开销的随机访问次数。实验结果表明,该方法实现了快速的Top-k连续预测,且滑动窗口大小等因素对计算性能影响不明显。5、基于上述研究,设计并实现了一个基于复合事件的异常识别与预警原型系统CREW,并讨论了相关的应用问题。