基于抽象解释的Prolog程序验证技术研究

作为一种通用的语义近似理论,抽象解释已广泛应用于各类程序的形式化验证中.现有基于抽象解释的逻辑程序验证技术未涉及与程序点相关联的程序性质的验证,设计能够描述此类性质的逻辑程序具体语义和抽象语义是构造相应验证工具的关键.本文给出了一种基于抽象解释的Prolog程序验证方法,该方法采用了具有路径信息的Prolog语义及其抽象作为语义基础,因而可用于验证与程序点相关联的程序特性.本文例子表明了该验证方法的有效性.     

流体随机Petri网的一阶混杂Petri网模型

为了借用一阶混杂Petri网(First-Order Hybrid Petri Nets)的建模原语和分析方法来分析流体随机Petri网(Fluid Stochastic Petri Nets)以克服流体随机Petri网数值分析方法的局限性,本文提出了一种流体随机Petri网转换成一阶混杂Petri网的形式化描述方法,并对其转换的正确性进行了证明,最后通过实例分析了流体随机Petri网转换成一阶混杂Petri网的必要性.     

一类具有"开端"结构的安全协议分析方法研究

开端协议(Open-ended Protocol)的分析是安全协议领域中一个待解决的重要问题,而IKE则是一个有代表性的具有"开端"结构的安全协议.本文基于串空间的Athena方法,针对IKEv2协议中的"开端"结构涉及的DH(Diffie-Hellman)问题,增加了群、散列函数等原语,给出并证明了一个新的消减规则;针对"开端"结构,引入了集合的数学概念,建立了新的消息类型,重新定义了串空间中的消息项、替换、入侵者模型,以及Athena相应的内在项、目标和目标绑定,给出了一个新的替代关系.应用扩展后的方法,分析了协议,发现一个新的认证性缺陷,给出了解决该缺陷的方法.     

目标独立的Prolog程序路径依赖分析语义

在Prolog程序分析中,考虑程序的执行路径和非逻辑的cut操作可提高程序分析的精度.当前用于Prolog程序路径依赖分析的语义因依赖于程序执行的目标而不适合目标独立的程序分析.为此,本文采用了一种携带路径信息并允许cut操作的Prolog抽象语法,在此基础上给出了Prolog的操作语义和一种目标独立的标号树(LT)语文,并证明了LT语义相对于操作语义的正确性.LT语义可作为目标独立的Prolog程序路径依赖分析的基础.     

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

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