基于符号化模型检测的对弈必胜策略验证

在对弈的研究中,验证对弈双方是否存在必胜策略的问题一直没能很好地解决,因为这涉及到超大规模的状态空间搜索。而随着符号化模型检测技术的发展,大规模系统的验证成为了可能。给出了使用符号化模型检测来验证对弈必胜策略的一般方法,并给出了一个井字棋必胜策略验证的实例。     

实例化空间:一种新的安全协议验证逻辑的语义模型

给出了一个称为“实例化空间（instantiation space）”的安全协议验证逻辑的语义模型．该语义模型是建立在一种自然的加密信息交换（cryptographical message exchange）模型上的．在此语义模型基础上，文章提出了一系列与安全属性相关的验证公理，由此可以证明它们在此语义模型下的正确性．更重要的是，在此语义下的公理集在算法上是完全可以实现的，其对应的工具SPV（Security Protocol Verifier）已经开发成功，并且可以验证复杂的协议．在这套安全协议验证模型理论下，可以很方便地处理包括公钥、私钥、共享密钥和Hash函数组成的复杂信息格式．而且，在此语义基础上的公理集是纯命题逻辑的，因此所需要的验证目标可以很方便地转化成可满足性问题（SAT），从而可以利用工业上快速高效的SAT求解器实现．     

关于D.W.Etherington的扩充产生算法的一个注记

Ｄ．Ｗ．Ｅｔｈｅｒｉｎｇｔｏｎ提出了一类总是有扩充的缺省理论，即有限有序缺省理论，同时使用接连近似的方法给出产生这类缺省理论的所有扩充的算法，并证明该算法对有限有序网络缺省理论总是收敛到一扩充。本文首先举例说明Ｄ．Ｗ．Ｅｔｈｅｒｉｎｇｔｏｎｄ的算法对一般的有限有序缺省理论并非总是收敛，然后给出了该算法对
对一般的有限有序缺省理论收敛的一个充分条件。     

可满足赋值算子的设计与实现

在很多应用领域中,我们都需要获取逻辑公式所有无冗余的可满足解集合,即集合中的任意两个解不能互相蕴涵。为了获取无冗余解集合,本文提出了两种实现方案。由于二叉决策图BDD具有对逻辑公式的高效表达特性,因此两种方案都是在逻辑公式转换成BDD的基础上实现的[1]。一种方案是直接对该BDD进行遍历,获取从根节点到终端节点1的所有路径集合,然后借助一致性理论获取无冗余解的一致性算子的实现。另一种方案借助香农分解定理对BDD先进行逐层分解,然后对分解后的BDD再进行一致性运算的可满足赋值算子的实现。本文最后对两种方案的实验效果进行对比分析。     

开放逻辑中基于一优先序的R-重构

在开放逻辑中,Ｒ－重构作为一知识库或信念集修正的结果并不唯一,有时甚至太多而难于明确计算和表示,为此,文中给出了基于一优先序的Ｒ－重构的概念,基于一优先序的Ｒ－重构往往要比Ｒ－重构少得多,不存在上述Ｒ－重构的问题,在用户给出的关于一知识库中知识的优先序时,基于该优先序的Ｒ－重构可以用来刻画对该知识库的合理维护。     

基于时态测试器的实时分支时态逻辑模型检测

基于自动机理论的模型检测技术在形式化验证领域处于核心地位, 然而传统自动机在时态算子上不具备可组合性, 导致各种时态逻辑的模型检测算法不能有机整合.本文为了实现集成限界时态算子的实时分支时态逻辑RTCTL*的高效模型检测, 提出一种RTCTL*正时态测试器构造方法, 以及相关符号化模型检测算法.证明了所提出的RTCTL*正时态测试器构造方法是完备的.也证明了该算法时间复杂度与被验证系统呈线性关系, 与公式长度呈指数关系.我们基于JavaBDD软件包成功开发了该算法的模型检测工具MCTK 2.0.0.我们完成了MCTK与著名的符号化模型检测工具nuXmv之间的实验对比分析工作, 结果表明MCTK虽然在内存消耗上要多于nuXmv, 但是MCTK的时间复杂度双指数级小于nuXmv, 使得利用MCTK验证大规模系统的实时时态性质成为可能.     

安全协议认证的形式化方法研究

安全协议认证是网络安全领域中重大课题之一。形式化方法多种多样。该文首先论述了模型检测技术及其在安全协议验证中的应用,然后介绍了各种定理证明方法和定理证明工具,接着讨论其它形式化验证方法,最后论述形式化方法的一些研究方向。     

多智体系统时态认知规范的模型检测算法

模型检测技术一直以来主要是检验用时态逻辑描述的规范,人们很少注意认知逻辑的模型检测问题,而在分布式系统领域,系统和协议的规范已广泛地采用知识逻辑来描述.着重研讨了时态认知逻辑的模型检测算法.在SMV(symbolic model verifier)模型检测器的基础上,根据知识的语义和集合理论,提出了多种检验知识和公共知识的算法,从而使SMV的检测功能由时态逻辑扩充到时态认知逻辑.这些方法也适用于其他以状态集合作为输出的模型检测方法和工具的功能扩充.     

开放逻辑中的合理事实反驳模型类

本文给出开放逻辑中合理事实反驳模型类的概念，讨论了它们的重要性质。通过给定一假说中名子的线性序关系，得到了假说的最大前节重构的概念，并由此给出了合理事实反驳模型类的一个具体例子。     

基于角色PMI的电子政务安全模型

论文介绍了角色规范属性证书和角色指派属性证书,讨论了基于角色的PMI体系结构,探讨了基于角色PMI的电子政务安全模型。