一种针对DFA状态爆炸的正则表达式匹配方法

针对基于确定有限状态自动机的匹配引擎在大规模、复杂规则下会出现状态爆炸的问题,提出正则表达式子串抽取算法。通过将子串抽取算法应用于DFA状态爆炸场景,设计基于子串抽取的正则匹配引擎。实验结果表明,该算法在单个规则上运行时间可达10 ms量级,抽取率高达99%,同时匹配引擎具有较好的稳定性和可拓展性,且匹配速度优于相关开源匹配引擎。

模型检测中状态爆炸问题研究综述

模型检测已成为保证软件系统正确性和可靠性的重要手段,但随着软件功能日益强大,其规模和复杂度也越来越大,在模型检测过程中容易产生状态爆炸问题。如何解决模型检测中的状态爆炸,已成为工业界和理论界无法回避的重要课题。系统地综述模型检测领域解决状态爆炸问题的关键技术和主要方法,并提出该领域的最新研究进展与方向。

基于随机Petri网的路由器的建模与状态爆炸的解决

提出了切换路由器的一个随机Petri网模型。在建模分析的过程中,通过逐步分解与迭代,解决了因系统规模扩充所带来的著名的状态爆炸问题,其结果证明了概算法的有效性与可行性。对于存在两个或以上的“资源”竞争的复杂环境,这种概算分析法也可以得到应用。

软件模型检测中状态爆炸问题的解决方法

在软件模型检测中,系统所对应的状态数会随着系统大小成指数级增长,即状态空间爆炸问题。为了研究近年来该问题的解决方法,按照系统综述的方法,归类整理近年来对近年来解决状态空间爆炸的方法,并对每类方法的应用、限制以及该领域的未来发展方向进行分析和总结。

用于克服程序状态空间爆炸的条件化预处理

提出用条件化技术对程序进行预处理的方案,以克服软件模型检测中状态空间爆炸问题。以程序性质公式中蕴涵式的前件作为约束条件,通过对程序符号化执行后各控制点的路径条件进行逻辑推理,删除那些对性质检测无关的语句。理论分析和实验结果表明,条件化可以有效缩减程序状态空间,并且满足软件模型检测对状态缩减的安全性要求。

JP-10燃料燃爆特性及无约束爆炸状态场参数试验研究

以云爆武器的液态燃料组分筛选为应用背景,基于JP-10燃料密度高、综合性能佳以及成本低等特点,开展了爆轰管内JP-10燃料的燃爆特性试验研究以及外场无约束空间下JP-10燃料的分散效果及爆炸状态场研究。研究发现:在强起爆作用下,JP-10燃料爆轰管内的爆炸超压约为0.6 MPa;在无约束条件下,JP-10燃料抛撒爆炸过程中,其云雾区内超压峰值要高于同体积的乙醚燃料,且爆炸温度峰值达到1 366.9℃,1 000℃以上高温持续时间是乙醚燃料的2倍,说明JP-10燃料的高热值特性有利于提高云爆武器的热毁伤效果。

基于状态约减的信息攻防图生成算法

针对攻防图构建中存在的状态爆炸问题,提出一种基于状态约减的攻防图生成算法。该算法在分析攻击者和目标网络特点的基础上,对独立状态节点的权限进行对比;其在保留最高权限节点的前提下,实现对低权限节点的约减,并去除冗余攻击路径。仿真实验表明算法具有计算复杂度低、能有效降低状态爆炸以及控制攻防图规模等优点。

基于状态约束的大规模正则表达式匹配算法

通过观察不确定有限自动机NFA到确定性有限自动机DFA的转化过程,分析内存增长的原因,提出了一种基于状态间约束关系的正则表达式匹配算法Group2-DFA。Group2-DFA通过两级分组,利用状态间的约束关系,将原始NFA转化为NFA和DFA的混合结构。实验表明,在保持一定处理速率的前提下,Group2-DFA能够有效地减少内存占用。在300条规则下,Group2-DFA吞吐率能够达到1Gbps,并且减少约75%的状态数。

并发系统模型检测中的状态约减算法

组合可达性分析是对并发系统模型分析验证的基础和关键,但是难于解决验证中的所谓的状态爆炸问题。对此提出了基于假定状态约减验证算法(ABSR),通过自动构造子系统接口定义来约束其状态规模,在验证过程中约减冗余状态,能更大程度降低状态爆炸几率和提高验证效率。借助假定-保证(Assume-Guarantee)算法有效性定理和组合可达性分析(CRA)算法安全性验证定理,证明该验证算法的有效性。通过采用通信系统演算(CCS)描述的任务模型为例证,证明上述算法比传统CRA算法更有效。

时间自动机可达性分析中的状态空间约减技术综述

时间自动机是检验实时系统建模的有效工具,其可达性分析可以检验系统是否可能达到某些特定的状态,其算法通常采用对符号状态的枚举来遍历其状态空间。因为引入了时钟变量,时间自动机的可达性分析算法会产生大量的中间状态,需要巨大的存储空间,往往超出了计算机能力的极限,导致分析和检验不能完成。这就是所谓的“状态空间爆炸”。研究人员设计了很多种优化技术来约减可达性分析所需的存储空间,以解决或者缓解这个问题。本文首先介绍了时间自动机及其可达性分析的基本概念,然后分类讨论了现有的空间约减优化技术并对此做出总结,最后提出了一些未来的研究方向。

基于敏感位置识别的状态化简技术研究

模型构建是模型检验的基础,在微控制器代码模型构建过程中面临状态爆炸的问题。由于生成模型的状态数量与代码规模密切相关,通过简化代码可以有效缩减生成的状态数量。该文提出了敏感变量和敏感位置的概念,并以此为基础提出了结合子程序摘要信息的敏感位置识别算法;该算法从待验证的性质出发,提取敏感变量,识别代码中与敏感变量相关的敏感位置;模型构建过程中只对敏感位置对应代码进行建模,从而实现对模型状态的缩减。实验结果表明所提的方法能够有效缓解微控制器代码模型生成过程中的状态爆炸问题。

多智体系统中约简状态空间的限界模型检测算法

为了形式化描述多智体系统中与概率、实时、知识相关的性质,提出了一种概率实时认知逻辑PTCTLK.模型检测是验证多智体系统是否满足PTCTLK公式的主要技术,状态空间爆炸是该技术实用化的主要瓶颈,为此提出一种PTCTLK的限界模型检测算法.其基本思想是,在有限的局部可达空间中逐步搜索属性成立的证据,从而达到约简状态空间的目的.首先,将PTCTLK的模型检测问题转换为无实时算子的PBTLK的模型检测问题;其次,定义PBTLK的限界语义,并证明其正确性;然后,设计基于线性方程组求解的限界模型检测算法;最后,依据概率度量的演化规律,探索检测过程终止的判别准则.实例研究结果表明,与无界模型检测相比,在属性为真的证据较短的情况下,限界模型检测完成验证所需空间更小.

基于动态内存和状态管理的模型检测新方法

模型检测是并发系统验证的主要形式化方法之一,但其存在因状态空间爆炸而导致内存不够的问题,这也是大规模并发系统验证的瓶颈。很多研究人员尽管做了很多相关研究,但仍然没有很好地解决这个问题。在研究动态内存和状态管理的基础上,提出了一种新的模型检测方法,避免了因为内存不足而无法模型检测的问题。

基于固定内存和状态管理的模型检测方法

在研究固定内存和状态管理的基础上,提出了一种新的模型检测方法,使得在任何计算机上都能对任意规模的并发系统进行模型检测。

基于展开的状态空间搜索方法

对于Petri网,与基于可达图的状态空间搜索方法相比,基于展开的状态空间搜索方法不需要考虑并发事件间的所有可能交织,可避免状态空间爆炸问题。通过例子,直观比较可达图和出现网的规模,由此说明基于展开的状态空间搜索不会产生状态空间爆炸。

基于局部攻击图的最小关键漏洞集分析方法

为缓解攻击图应用在工业互联网安全防护中的状态空间爆炸问题,提出一种基于局部攻击图的最小关键漏洞集分析方法。提出一种以重要资产节点为目标的局部攻击图生成算法,通过裁剪不可达目标节点的攻击路径缓解状态空间爆炸问题;基于局部攻击图生成过程中得到的攻击路径漏洞集直接进行最小关键漏洞集分析,节省传统分析方法在搜索关键漏洞过程中对攻击图进行二次遍历的时空开销。在此基础上,通过工业网络实例进行分析并开展相关工作比较,实验结果表明,所提方法合理可行,可高效分析网络系统中的最小关键漏洞集。

并发反应式系统的组合模型检验与组合精化检验

模型检验和精化检验是两种重要的形式验证方法,其应用的主要困难在于如何缓解状态爆炸问题.基于分而治之的思想进行组合模型检验和组合精化检验是应对这个问题的重要方法,它们利用系统的组合结构对问题进行分解,通过对各子系统性质的检验和综合推理导出整个系统的性质.在一个统一的框架下对组合模型检验和组合精化检验作了系统的分析和归纳,从模块检验的角度阐述了上述两种组合验证方法的原理及其相应的组合验证策略.同时总结了各类问题的复杂性,并对上述两种方法作了比较分析,揭示了它们之间的内在联系.最后展望了组合模型检验与组合精化检验的发展方向.

构件组合的抽象精化验证

针对构件组合的状态爆炸问题,改进了反例引导的抽象精化框架,提出了组合式的抽象精化方法,使构件组合的模型检验转化为各成分构件的局部抽象精化,降低了分析的复杂度.提出了在构件组合情况下基于等价关系和存在商的构件抽象方法,用构件抽象的组合建立构件组合的抽象;提出了组合确认定理并给出证明,使反例确认分解为在各构件上对反例投影的确认;通过对单个构件的等价关系的精化实现构件组合的抽象模型的精化.在模型检验构件组合的过程中,不需要为构件组合建立全局的具体状态空间.

安全协议验证模型的高效自动生成

为了能高效地利用模型检测技术对安全协议进行分析与验证,提高工作效率,提出了一种适用范围广,自动化程度及验证效率均较高的建模算法。开发了一个基于该建模算法"网络安全协议验证模型生成系统",该系统可高效地对安全协议进行分析与验证,系统在对攻击者建模时采用偏序规约、语法重定序及类型检查等优化策略以提高验证效率,有效地缓解了模型检测过程中的状态爆炸问题。

随机Petri网的分解和压缩技术

本文综述了在随机Petri网的分解和压缩技术方面的一些最近的工作，着重介绍了时间数量级分解、接近无关分解、响应时间保留压缩、流等价压缩、层次模型和分层分析与乘积形式解等技术的基本思路、方法和操作过程．本文也描述了解决系统模型状态空间爆炸问题所面临的困难和进一步的研究方向．