基于行为的可信动态度量的状态空间约简研究

针对复杂并发计算机系统行为可信的动态度量研究中,细粒度动态度量所引发的状态空间爆炸问题一直是研究的难点.文中基于并发理论研究复杂并发计算机系统行为可信问题,在保障度量可靠性的前提下对系统状态空间进行约简,即通过标记变迁系统模型描述行为系统,通过事件结构模型研究行为关系,依据行为关系对变迁系统中各条路径进行重构,合并重构路径中相同的路径,实现变迁关系集约简,缩小状态空间.通过上述方法缓解了状态空间爆炸,并且,根据约简后的状态空间得到面向行为的可信动态度量的行为预期,增加细粒度动态度量方法在复杂系统中应用的可行性.

安全协议状态空间的束动作偏序约简算法

目前安全协议分析的偏序归约算法较为复杂、不易实现,限制了其适用范围,且以动作为基础,粒度较小,对减少状态空间的作用有限。针对该问题提出了一种束动作偏序约简算法,将同一会话中的动作序列看做一个束动作,根据攻击者截获的消息与攻击者知识集间的关系,判断迹等价的束动作迁移所到达的后继状态是否为冗余节点,以约简状态空间。该算法思想简单、易于实现;实例表明它有效地约简了安全协议的状态空间。

面向程序验证的并行程序状态空间态约简技术综述

程序验证是保证程序安全性的重要手段。随着采用多核技术的硬件环境日渐普及,越来越多的软件正通过转向基于共享内存的并行程序模型来充分利用现有的计算资源。各线程在并行执行时通过共享内存的访问互相干扰执行状态,导致可能执行路径数成几何级数增长,进而产生可达状态空间爆炸问题。由于验证并行程序安全性主要通过分析程序可达状态来实现,因此,对并行程序可达状态空间的约简是决定并行程序验证效率的关键因素。首先对面向并行程序验证的并行程序可达状态空间约简方法进行了分类,然后对各类可达状态空间约简方法分别进行了分析和总结,最后指出了当前存在的问题和未来解决这些问题的研究方向。

基于时间自动机的符号状态拆分优化算法

为约简时间自动机的状态空间,对时间抽象互模拟技术进行研究,提出一种改进的符号状态拆分算法。通过在符号状态拆分的过程中将隐含的时钟约束加入符号状态来缩小符号状态的时间域,减少符号状态拆分的次数,提高符号状态拆分算法的效率。为实现符号状态拆分算法,提出一种改进的DBM(difference bound matrices)减法算法。将减法算法得到非凸多面体用互不重叠DBM集合来表示,使得由符号状态拆分算法得到的等价类中没有冗余的等价类。实验结果表明了改进后的符号状态拆分算法和DBM减法的有效性。