密码协议的符号模型检测及分析

对密码协议模型检测的方法作了理论上的研究,并用SMV检测工具给出了一个实际分析的例子。结果表明,利用符号模型检测方法分析并发现密码协议重放攻击的漏洞是一种行之有效的方法。

基于符号模型检测的SDG模型可诊断性验证

由于定量信息和非线性因果关系的丢失,符号有向图(signed directed graph,SDG)模型的可诊断性需要进一步地进行校核与验证。为此,提出了基于符号模型检测的SDG模型可诊断性形式化验证方法。首先定义了SDG模型的有限状态变迁系统形式化描述,建立了符号模型验证器(symbolic model verifier,SMV)模型;其次利用SDG的深层知识,构造了可诊断性函数,设定了可诊断性上下文,给出了可诊断性定义。然后,构造了SDG耦合孪生SMV模型,定义了可诊断性的计算树时态逻辑公式,提出了验证算法SDGD_CSMV。最后,通过一个实例验证了可诊断性的判定和算法的有效性。

多智能体系统时态认知规范高效符号模型检测的算法研究

Clarke和McMillan提出了利用mu演算和OBDDs符号模型检测时态逻辑的方法.这些方法是非常有效的,能用于验证许多具有极大状态空间的实际系统(状态个数可以超过1020).但是,这些方法不能检测知识逻辑.而时态认知逻辑能更精确地描述分布式领域中系统和协议的规范.文章首先讨论了Kripke结构和mu演算的扩展,然后提出了利用扩展mu演算和OBDDs符号模型检测时态认知逻辑的方法.

基于符号模型检测的符号有向图故障诊断解形式化验证

由于定量信息和非线性因果关系的丢失,符号有向图(SDG)的故障诊断解需要进一步进行校核与验证.将SDG故障诊断解的验证置于符号模型检测框架中进行研究,提出了基于符号模型检测的SDG故障诊断解形式化验证方法.首先定义了SDG模型的有限状态变迁系统形式化描述,建立了符号模型检测(SMV)模型;其次引入故障传播时间定义了模型观测变量的动态验证信息,提出了基于步进式监控的动态推理验证策略;然后扩展了动态推理验证过程的SMV模型,提出了验证算法SSDGFD SMC;最后,通过一个简单贮水罐系统的SDG模型实例验证了算法SSDGFD SMC的有效性.

Verilog程序的命题投影时序逻辑符号模型检测

为了保证以Verilog硬件描述语言设计的片上系统的正确性,提出了Verilog程序的符号模型检测方法.依据形式化操作语义将Verilog程序建模为有限状态机,将设计规范用命题投影时序逻辑公式描述,并采用命题投影时序逻辑符号模型检测工具对程序进行验证,从而证明片上系统满足设计规范.以Verilog程序描述的四位同步二进制计数系统的验证实例表明,Verilog程序的命题投影时序逻辑符号模型检测方法是可行的.

一个命题投影时序逻辑符号模型检测器

现有模型检测工具的形式化规范语言,如计算树逻辑(computation tree logic,简称CTL)和线性时序逻辑(linear temporal logic,简称LTL)等的描述能力不足,无法验证ω正则性质.提出了一个命题投影时序逻辑(propositional projection temporal logic,简称PPTL)符号模型检测工具——PLSMC(PPTL symbolic model checker)的设计与实现过程.该工具基于著名的符号模型检测系统NuSMV,实现了PPTL的符号模型检测算法.PLSMC的规范语言PPTL具有完全正则表达能力,这使得定性性质和定量性质均可被验证.此外,PLSMC可以有效地缓解模型检测工具中容易发生的状态空间爆炸问题.最后,利用PLSMC对铁路公路交叉道口护栏控制系统的安全性质和周期性性质进行验证.实验结果表明,PPTL符号模型检测工具扩充了NuSMV系统的验证能力,使得时间敏感、并发性和周期性等实时性质可以被描述和验证.

WISHBONE片上总线符号模型检测

随着多核体系结构的出现和普及,片上总线逐渐成为影响片上系统功能和性能的关键部件.因此,片上总线的验证成为片上系统设计中一个重要组成部分.模型检测作为一种主流的形式化验证方法,可以自动化穷举搜索系统行为以决定片上系统的设计是否满足设计规范.然而,模型检测受制于状态空间爆炸问题,且现有规范语言如计算树逻辑和线性时序逻辑等的描述能力有限.提出了一种基于命题投影时序逻辑的WISHBONE片上总线符号模型检测方法.该方法将以Verilog硬件描述语言实现的WISHBONE总线转化为以NuSMV模型检测工具的建模语言SMV描述的系统模型,使用命题投影时序逻辑描述WISHBONE总线期望的性质,通过PLSMC工具验证系统模型是否满足期望的性质.实验结果表明该方法能够有效验证WISHBONE片上总线的定性性质,以及时间敏感和迭代性等定量性质.

模糊计算树逻辑的符号模型检测

对含有模糊不确定性信息的系统进行模型检测时,状态空间爆炸问题成为了亟待解决的主要问题。将形式化的系统模型用拟布尔公式表示,用多终端二叉决策图来对拟布尔公式进行存储。对模糊计算树逻辑的不动点语义给出了解释和证明,然后给出模糊计算树逻辑的符号化模型检测算法,最后通过一个实例验证算法的正确性。该算法可有效缓解对模糊模型检测验证时的状态空间爆炸问题,并扩展了模型检测的应用范围。

基于符号模型检测的Web服务组合形式化验证

随着经济的发展和市场竞争的加剧,企业必须能够快速且准确地满足市场和用户的各种需求。Web服务组合正是由于单个Web服务不能满足企业及用户的需求而产生的一种技术,而如何确保组合的正确性来实现服务增值是一个尚未完全解决的问题。针对此问题,提出了一种基于符号模型检测器NuSMV对Web服务组合进行验证的方法,并提出了基于消息会话的Web服务有限状态自动机的形式化定义。最后实例验证了Web服务组合交互的正确性和有无死锁状态现象,进一步证明了方法的可行性。

基于广义可能性的模态μ演算符号模型检测

随着计算机功能的不断增强,软硬件系统也变得越来越复杂,使得人们对系统的需求更高。系统建模中可能存在的诸多不确定性信息也亟待被解决,为了充分解决系统信息来源的种种不确定性特征和各种不完备性,本文引入了广义可能性决策过程理论作为系统模型。在此基础上,给出了广义可能性模态μ演算的语法和语义;然后通过约简有序二叉决策图进行布尔存储来描述广义可能性不确定信息系统的特征属性;最后给出了广义可能性的模态μ演算符号化模型检测算法和时间复杂度。同时,通过广义可能性的模态μ演算符号化模型检测算法也有效缓解了状态爆炸问题,这对不确定性信息系统的模型检测提供了一种新的思路。

可能性测度下的CTL符号化模型检测

随着系统复杂性的增加,系统中的不确定信息亟待处理,状态爆炸问题也越来越严峻,现有的模型检测技术已不能完全适用于复杂系统的验证。对可能性测度下CTL符号化模型检测进行了研究。首先用多终端二值决策图和布尔公式分别描述系统模型和待验证性质,然后再对系统模型进行归一化和简化,最后利用不动点计算完成系统验证。该研究是对可能性测度下的模型检测技术和符号化模型检测技术的整合,不但能处理系统的不确定信息,而且保持了符号化模型检测对计算时空要求低的优点,对于复杂系统模型检测具有重要意义。

和与积数迷的符号化模型检测

和与积是一个著名的数迷问题。采用公告逻辑对该问题进行建模,将其Kripke模型符号化表示为多智能体有限状态程序,并在其上采用一种基于局部命题解释系统语义的知识逻辑符号化模型检测算法计算该问题的所有解。在时态逻辑模型检测器NuSMV基础上扩展实现了本文算法,然后在相同实验平台上用动态认知建模工具DEMO对该问题进行求解。实验表明,我们的算法不仅结果正确,而且在运行效率上与DEMO相比占有绝对优势。

离散实时线性动态逻辑的符号化模型检测

实时系统的错误往往十分危险甚至是致命的,使用模型检测来保证复杂实时系统的正确性是十分有效的。针对模型检测中传统时态逻辑无法表达实时性质和所有正则属性的问题,文中首先提出一种具有表达离散实时性质、所有正则属性能力的离散实时线性动态逻辑(Real-Time Linear Dynamic Logic,RTLDL);然后使用类似程序控制流标记的方法为RTLDL公式定义起止标记,根据起止标记关系构造时态测试器,提出基于时态测试器的RTLDL符号化模型检测算法;最后基于翻译的方法在模型检测器NuXmv上实现了所提算法,并针对护栏控制系统案例与线性动态逻辑(Linear Dynamic Logic,LDL)模型检测器MCMAS-LDLK进行实验比较。实验结果表明,无论对于LDL还是RTLDL公式的检测,提出的算法的效率均显著优于MCMAS-LDLK。

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

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

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

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

ISI协议的符号模型检验分析

电子商务协议的非否认性与公平性问题已成为电子商务和信息安全领域研究的热点。本文建立了网络支付协议ISI的有限状态机模型,并用SMV检验工具对其两个重要特性———非否认性与公平性进行了分析检验,发现了ISI协议不满足公平性。结果表明利用符号模型检验方法分析检验电子商务协议的新特性是行之有效的。

CMP1协议的符号模型检验分析

提出采用模型检验方法研究电子商务协议的非否认性与公平性问题,建立了认证电子邮件协议CMP1的有限状态机模型,并用SMV检验工具对其非否认性与公平性进行了分析检验,经过分析发现了CMP1协议不满足公平性并对其进行了相应修改.结果表明,利用符号模型检验方法分析检验电子商务协议的新特性是行之有效的.

基于Groebner基的模型检测技术及其工具实现

为了减少运算复杂度和运算时间,优化检测的性能,使得计算过程更加快速高效,在符号化模型检测的过程中,利用G roebner基进行多项式约化,设计出新的模型检测算法。并且基于该算法开发出新的符号模型检测工具。该工具能更快速地验证各软件及硬件系统的性质,具有较高的实用价值。

时态认知逻辑CTL*K的符号化模型检查算法

时序认知逻辑是由时序逻辑和认知逻辑组合而成的逻辑,主要应用于多主体系统的规范定义。大多数时序认知逻辑是基于CTL的,表达能力有限。并且已知的一些模型检查算法存在内存不足和状态爆炸等问题。讨论了基于CTL*的时态认知逻辑CTL*K的语法、语义和模型,它能够在表达力很强的时态逻辑CTL*基础上描述智能体的知识、目标等意向特征。并给出了CTL*K的模型检查算法,其核心思想就是将CTL*K公式的检查问题转化为CTL*公式的模型检查问题,可以使检查的系统规模得以大幅度提高。并且将算法编码后容易集成到NuSMV模型检查器。

基于模型检测的实时模型诊断方法

提出一种基于模型检测的实时模型诊断方法.利用模型检测算法对大状态空间系统验证的高效性,使诊断系统能够更快地进行模型诊断,并对这种方法进行了系统实现,结果表明,此方法可行、有效.