排序方式: 共有29条查询结果,搜索用时 468 毫秒
1.
基于自动机理论的模型检测技术在形式化验证领域处于核心地位, 然而传统自动机在时态算子上不具备可组合性, 导致各种时态逻辑的模型检测算法不能有机整合.本文为了实现集成限界时态算子的实时分支时态逻辑RTCTL*的高效模型检测, 提出一种RTCTL*正时态测试器构造方法, 以及相关符号化模型检测算法.证明了所提出的RTCTL*正时态测试器构造方法是完备的.也证明了该算法时间复杂度与被验证系统呈线性关系, 与公式长度呈指数关系.我们基于JavaBDD软件包成功开发了该算法的模型检测工具MCTK 2.0.0.我们完成了MCTK与著名的符号化模型检测工具nuXmv之间的实验对比分析工作, 结果表明MCTK虽然在内存消耗上要多于nuXmv, 但是MCTK的时间复杂度双指数级小于nuXmv, 使得利用MCTK验证大规模系统的实时时态性质成为可能. 相似文献
2.
在很多应用领域中,我们都需要获取逻辑公式所有无冗余的可满足解集合,即集合中的任意两个解不能互相蕴涵。为了获取无冗余解集合,本文提出了两种实现方案。由于二叉决策图BDD具有对逻辑公式的高效表达特性,因此两种方案都是在逻辑公式转换成BDD的基础上实现的[1]。一种方案是直接对该BDD进行遍历,获取从根节点到终端节点1的所有路径集合,然后借助一致性理论获取无冗余解的一致性算子的实现。另一种方案借助香农分解定理对BDD先进行逐层分解,然后对分解后的BDD再进行一致性运算的可满足赋值算子的实现。本文最后对两种方案的实验效果进行对比分析。 相似文献
3.
开放逻辑中基于一优先序的R-重构 总被引:2,自引:0,他引:2
苏开乐 《计算机研究与发展》1999,36(5):523-527
在开放逻辑中,R-重构作为一知识库或信念集修正的结果并不唯一,有时甚至太多而难于明确计算和表示,为此,文中给出了基于一优先序的R-重构的概念,基于一优先序的R-重构往往要比R-重构少得多,不存在上述R-重构的问题,在用户给出的关于一知识库中知识的优先序时,基于该优先序的R-重构可以用来刻画对该知识库的合理维护。 相似文献
4.
在对弈的研究中,验证对弈双方是否存在必胜策略的问题一直没能很好地解决,因为这涉及到超大规模的状态空间搜索。而随着符号化模型检测技术的发展,大规模系统的验证成为了可能。给出了使用符号化模型检测来验证对弈必胜策略的一般方法,并给出了一个井字棋必胜策略验证的实例。 相似文献
5.
模型检测技术一直以来主要是检验用时态逻辑描述的规范,人们很少注意认知逻辑的模型检测问题,而在分布式系统领域,系统和协议的规范已广泛地采用知识逻辑来描述.着重研讨了时态认知逻辑的模型检测算法.在SMV(symbolic model verifier)模型检测器的基础上,根据知识的语义和集合理论,提出了多种检验知识和公共知识的算法,从而使SMV的检测功能由时态逻辑扩充到时态认知逻辑.这些方法也适用于其他以状态集合作为输出的模型检测方法和工具的功能扩充. 相似文献
6.
安全协议认证的形式化方法研究 总被引:6,自引:0,他引:6
安全协议认证是网络安全领域中重大课题之一。形式化方法多种多样。该文首先论述了模型检测技术及其在安全协议验证中的应用,然后介绍了各种定理证明方法和定理证明工具,接着讨论其它形式化验证方法,最后论述形式化方法的一些研究方向。 相似文献
7.
苏开乐 《计算机工程与科学》1998,20(4):37-41
D.W.Etherington提出了一类总是有扩充的缺省理论,即有限有序缺省理论,同时使用接连近似的方法给出产生这类缺省理论的所有扩充的算法,并证明该算法对有限有序网络缺省理论总是收敛到一扩充。本文首先举例说明D.W.Etheringtond的算法对一般的有限有序缺省理论并非总是收敛,然后给出了该算法对
对一般的有限有序缺省理论收敛的一个充分条件。 相似文献
对一般的有限有序缺省理论收敛的一个充分条件。 相似文献
8.
实例化空间:一种新的安全协议验证逻辑的语义模型 总被引:1,自引:0,他引:1
给出了一个称为“实例化空间(instantiation space)”的安全协议验证逻辑的语义模型.该语义模型是建立在一种自然的加密信息交换(cryptographical message exchange)模型上的.在此语义模型基础上,文章提出了一系列与安全属性相关的验证公理,由此可以证明它们在此语义模型下的正确性.更重要的是,在此语义下的公理集在算法上是完全可以实现的,其对应的工具SPV(Security Protocol Verifier)已经开发成功,并且可以验证复杂的协议.在这套安全协议验证模型理论下,可以很方便地处理包括公钥、私钥、共享密钥和Hash函数组成的复杂信息格式.而且,在此语义基础上的公理集是纯命题逻辑的,因此所需要的验证目标可以很方便地转化成可满足性问题(SAT),从而可以利用工业上快速高效的SAT求解器实现. 相似文献
9.
基于实例化空间逻辑理论,使用知识推理方法,在SPV(Security Protocol Verifier)下对完整SET证书申请协议的秘密性、认证性等安全性质进行了完全自动化证明,并对协议进行了改进.SPV调用工业级SAT求解器,能够高效验证安全协议是否满足CAPSL(Common Authentication Protocol Specification Language)协议规范及单层、多层认知规范.应用一个逻辑或工具对协议进行验证首先必须对该协议进行简化,而SET协议作为当前最复杂的工业级协议,其原始文档有上千页,因此简化过程相当困难,相关研究较少,已有的一些简化模型也不够完整.因此,文章针对SET证书申请协议,给出了比以往更贴近原协议的简化模型,并详细阐述了该模型在SPV下的形式化描述及验证过程、验证结果,分析了由于协议不满足某些认知规范所带来的安全隐患,从而对协议进行改进,最后证明了改进后协议的有效性.该工作也充分说明了SPV足以处理复杂的工业级协议. 相似文献
10.
多主体系统时态认知规范的"On the Fly"模型检测算法研究 总被引:1,自引:0,他引:1
时态认知逻辑已被广泛应用于分布式系统和协议的规范描述,模型检测时态认知规范已成为一个新的研究领域,因此着重研讨时态认知规范的“On the Fly”模型检测算法.在“On the Fly”模型检测时态逻辑描述规范的基础上,根据自动机理论、深度优先方法和知识的语义,提出了“On the Fly”模型检测时态认知规范的算法,该算法在模型检测带有知识算子的时态规范时,在找到一个反例之前,往往只需构造系统的部分甚至小部分状态空间,从而避免了时态认知规范的模型检测中内存不足和状态爆炸等问题,实现了“On the Fly”模型检测时态认知规范,并且算法的复杂性是多项式时间的.最后,通过该方法在验证TMN密码协议中的应用来作为一个例子说明该方法的有效性. 相似文献