操作系统形式化验证综述

介绍操作系统验证理论、语言和工具等技术基础,阐述验证路径、精化关系验证和大规模验证等新的验证方法和理念。比较分析多个操作系统验证项目研究内容、验证方法、主要贡献以及最新进展。分析操作系统验证过程中存在的问题,认为验证成本高、验证工具局限性是制约操作系统形式化验证的关键因素,随着验证工具、框架和定理库的完善,以及深度学习等新技术的应用,操作系统更多的安全性质能够被形式化验证。     

PLC程序形式化的设计与验证

从形式化方法的角度出发,阐述可编程逻辑控制器(PLC)程序的形式化设计和验证方法的相关研究.在形式化设计方面,分析了根据Petri网和自动机模型判断程序正确性和可靠性的研究成果;在形式化验证方面,分析了PLC语言与形式化模型的转换和基于NuSMV或UPPAAL的验证方法.最后,比较将两种形式化方法应用到PLC程序的特点,探讨现有成果中存在的问题及研究发展方向.     

基于条件谓词逻辑的可信计算形式化分析

随着可信计算应用的不断发展,针对可信计算的形式化分析理论将成为可信计算领域研究的热点。在深入研究可信计算相关技术、信任链建立和信任传递过程影响因素的基础上,提出了基于条件谓词逻辑的可信计算形式化分析方法。通过定义不同的谓词和推演规则,并在谓词逻辑中添加可信性的影响因素作为约束条件,实现对可信计算信任模型的形式化验证。利用提出的方法举例对可信计算平台安全引导过程进行了分析,并且根据分析结果提出了委托受限的安全引导过程。结果表明,基于条件谓词逻辑的形式化验证方法,能够清晰、有效的实现对可信计算信任模型的形式化分析,为可信计算应用模型的设计和完善提供参考。形式化方法的提出,对于丰富可信计算信任评估理论,促进可信计算应用发展具有一定的意义。     

一种验证Web应用设计的方法

提出一种表示Web应用的请求/响应导航关系的形式化行为模型,给出一种基于模型检查的Web应用设计的验证方法并描述了用时态逻辑CTL表示Web应用性质的方法.设计了一个检验方法可行性的原型框架,该原型嵌入自动化模型检查工具NuSMV,提供从UML设计模型到形式化模型的自动转换,在将用户输入的性质和形式化模型合并为NuSMV程序后,运行NuSMV进行自动化验证.     

在数字电路验证中使用模型检验

形式化方法作为仿真方法的补充,为电路功能验证提供了新的途径.介绍了形式化验证方法之一,模型检验的理论基础和实现方法.介绍了分支时态逻辑CTL、CTL的固定点算法,二元决策图BDD,以及符号模型检验方法.最后使用SMV工具在一个CISC处理器的存储管理单元(MMU)上应用了模型检验,验证了模型检验在模块级验证中的可行性.     

基于攻击者的“角色冒充”的协议验证方法

网络的普及使得网络安全问题日益重要 ,协议的安全性和密码算法的安全性是网络数据安全的两个最基本的概念。介绍了几种具有代表性的安全协议的形式化验证工具 ,并提供了用 JAVA语言实现的基于攻击者和秘密的安全协议验证算法。提出了身份验证协议必须交换秘密的概念 ,还为协议的形式化验证过程设计了框架。实现的验证工具是证伪的     

分布式仿真系统验证工具设计与开发

为实现分布式仿真系统的自动验证，设计并开发了一个基于多Agent技术的验证工具．该工具采用形式化描述和校核方法完成多Agent系统的设计，利用Q学习算法实现多Agent之间的协调和协作，并使用面向对象知识表示方法表示了分布式仿真系统的验证知识，从而实现了统计验证、图灵测试和表面验证等任务．实际应用证明，该工具极大的提高了分布式仿真系统验证的自动化水平．     

Aziz-Diffie协议的形式化分析及其改进

形式化分析方法由于其精炼、简洁和无二义性逐步成为分析密码协议安全性的一条可靠而准确的途径。作为形式化分析方法的典型代表BAN逻辑由于其直观、易用等优点得到广泛的应用。概述了BAN逻辑,并基于BAN逻辑对Aziz-Diffie无线网络密钥协议进行了形式化描述和分析,验证了协议存在的漏洞,同时提出了该协议的改进方案。     

投影时序逻辑在系统建模中的应用

目的为了解决形式化验证时需要分别使用不同工具进行系统建模和性质描述的问题。方法利用投影时序逻辑PTL(projection temporal logic)在同一逻辑框架内完成待验证系统的建模和性质的描述。结果对PTL投影操作符的特点和用途进行了详细分析,并结合实例展示了PTL系统建模的使用。结论 PTL具备强大的表达能力,可广泛的应用于各类软硬件系统的验证。     

安全协议的形式化验证技术研究

对安全协议形式化验证方法所应用的技术进行了研究，总结了当前安全协议的各种形式化验证方法的特点，指出今后一段时期内安全协议形式化验证技术的研究方向．     

一种安全协议的形式化验证方法

BAN(Burrows,Abadi and Needham)类逻辑可以辅助设计、分析和验证网络和分布式系统中的安全协议。介绍BAN逻辑的产生、成分和分析步骤，指出BAN逻辑的缺陷，由此而产生的改进BAN逻辑和现状，并对BAN类逻辑作全面的回顾与展望，得出：BAN类逻辑仍然是密码协议分析和设计的主要工具，但理想化步骤是BAN类逻辑的致命缺陷的结论。展望了BAN类逻辑研究。对未来协议的形式化分析工作具有指导意义。     

BAN类逻辑的由来与发展

BAN(Burrows,Abadi and Needham)类逻辑可以辅助设计、分析和验证网络和分布式系统中的密码协议。该文介绍了 BAN逻辑的产生、成分和分析步骤 ,进而全面指出了 BAN逻辑的缺陷 ,由此而产生的改进的 BAN逻辑和现状 ,从而对 BAN类逻辑作了全面的回顾与展望 ,并得出结论 :BAN类逻辑仍然是密码协议分析和设计的主要工具 ,但理想化步骤是 BAN类逻辑的致命缺陷。指出了 BAN类逻辑研究工作的展望。这些结论对未来协议的形式化分析工作具有指导意义     

基于模型驱动的Web服务符号执行与验证

Web服务测试与验证是保证Web服务功能正确的关键,目前大多数Web服务的研究无法对程序路径穷举遍历,不能保证分析的完备性.针对该不足,在基于模型驱动的3阶段Web服务模型转换生成方法的基础上,该文对转换生成的Java代码进行符号执行与形式化验证.符号执行方法可对程序运行的所有路径进行分析,为程序测试提供高覆盖率的测试...     

基于KG逻辑的3GPP AKA协议形式化分析与改进

3GPP AKA协议的设计者使用BAN逻辑对协议进行形式化的分析，并生成所有的安全目标已经达到。但是由于BAN逻辑的局限性，设计者并没有找到协议对于重定向攻击和重放攻击的脆弱性。本文给出基于信仰变化的KG逻辑方法，指出脆弱性所在，并对改进后的协议方案进行验证。     

基于特征加权的汉字点笔画生成研究

针对汉字字形设计和开发的困难, 提出基于特征点抽象的汉字字形描述方法和汉字字形生成方法, 研究特征点、特征表达式、特征点的权值和权矢量等在汉字字形生成中的应用技术和方法, 并以点的生成为例, 设计汉字点笔画的生成算法, 并进行验证实验。实验结果证明该算法可靠并实用, 可切实提高汉字字形设计的效率, 为汉字其他笔画的生成提供一种解决方案。     

Quantum programming: From theories to implementations

This paper surveys the new field of programming methodology and techniques for future quantum computers, including design of sequential and concurrent quantum programming languages, their semantics and implementations. Several verification methods for quantum programs and communication protocols are also reviewed. The potential applications of programming techniques and related formal methods in quantum engineering are pointed out.     

FPGA组合逻辑程序的Petri网建模方法

针对现场可编程门阵列(FPGA)组合逻辑程序,提出其普通Petri网建模方法.首先,将状态变量描述为库所对,程序中的逻辑运算描述为变迁,从而将系统程序转换为一个普通Petri网结构;然后,根据Petri网的动态分析性能,给出系统状态可达图的计算方法,实现了状态可达图等价描述FPGA组合逻辑系统运行过程.研究结果表明:该Petri网能够准确地描述变量间的逻辑关系,提出的方法可以为FPGA组合逻辑程序的形式化设计和验证提供建模依据.     

Rigorous Modeling of Real-time System Based on UML and PVS

Rigorous modeling could improve the correctness and reduce cost in embedded real-time system development for models could be verified. Tools are needed for rigorous modeling of embedded real-time system. UML is an industrial standard modeling language which provides a powerful expressi-veness, intuitive and easy to use interface to model. UML is widely accepted by software developer. However, for lack of precisely defined semantics, especially on the dynamic diagrams, UML model is hard to be verified. PVS is a general formal method which provides a high-order logic specification language and integrated with model checking and theorem proving tools. Combining the widely used UML with PVS, this paper provides a novel modeling and verification approach for embedded real-time system. In this approach, we provide 1) a timed extended UML statechart for modeling dynamic behavior of an embedded real-time system; 2) an approach to capture timed automata based semantics from timed statechart; and 3) an algorithm to generate a finite state model expressed in PVS specification for model checking. The benefits of our approach include flexible and friendly in modeling, extendable in formalization and verification content, and better performance. Time constraints are modeled and verified and its a highlight of this paper.     

模糊目标信息系统上的逻辑及决策规则

基于模糊目标信息系统模型，并结合粗糙集相关的逻辑理论，提出了模糊粗糙决策语言FRDL，给出了FRDL中公式的定义、语义、可满足性有效性的形式化描述以及相关的性质。在此语言的基础上，给出了模糊目标信息系统上的决策规则、逆决策规则形式化描述和构造方法。FRDL所描述的逻辑表达方法以及规则推理公式为建立在模糊目标信息系统之上的决策支持系统、推理机提供了形式化的表示和推理方法。最后，在眼科近视诊断上进行的数据实验表明，这种形式化描述和推理方法比较合理。