Combination of Model Checking and Theorem Proving to Verify Embedded Software

In this paper, a scheme of combining model checking and theorem proving techniques to verify high trustworthy embedded software is proposed. The software model described in state machine of unified model language is transformed into the input modeling language of a model checker in which the model is analyzed with associated property specifications expressed in temporal logic. The software model which has been verified by model checker is then transformed into abstract specifications of a theorem prover , in which the model will be refined, verified and translated into source C code. The transformation rules from state machine to input language of model checker and abstract specifications of theorem prover are given. The experiment shows that the proposed scheme can effectively improve the development and verification of high trustworthy embedded software.

基于口令认证的密钥交换协议的安全性分析

在串空间理论模型引入了描述DH问题的方法以及分析猜测攻击的攻击者能力 ,对基于口令认证的密钥交换协议的安全性进行了形式化分析。提出一个对DH EKE协议的简化 ,并证明了该协议的安全性 :口令的秘密性 ,认证性 ,以及会话密钥的秘密性 .根据分析给出基于口令认证的密钥交换协议抵抗猜测攻击的基本条件 .将分析方法应用到基于口令的三方密钥交换协议上 ,给出单纯基于口令进行密钥交换协议的安全性需要满足的一个必要条件 .

模型检测与定理证明相结合开发并验证高可信嵌入式软件

首先将软件的UML状态机模型转换为模型检测工具MOCHA的输入语言REACTIVEMODULES,在MOCHA中进行正确性验证,利用模型检测工具针对错误情况给出的反例路径,尽早修改软件的UML设计模型;然后将已验证过的UML模型转换为定理证明工具B方法的抽象规约,利用B方法的精化、验证及代码生成功能,直接生成正确的C代码。并给出了从UML状态机到REACTIVE MODULES建模语言及B AMN抽象规约的转换规则。实验结果表明,该方法可在软件工程中有效地提高高可信嵌入式软件开发和验证的效率。

操作系统对象语义模型(OSOSM)及形式化验证

操作系统的复杂性使得其安全性问题日益突出.有不少的研究工作采用形式化的方式对现有的操作系统进行了正确性的验证,这些工作主要是采用程序形式逻辑验证代码级的功能实现性.从系统设计的角度,以高阶逻辑和类型论为基础,提出了操作系统对象语义模型(OSOSM).OSOSM采用分层结构,包括基本功效层、实现层和优化层.OSOSM将操作系统中的行为主体和资源抽象为操作系统对象,建立操作系统的论域,利用以操作系统对象变元集合为定义域到论域的映射表示操作系统的状态,描述操作系统系统调用等行为的语义,使用逻辑系统的谓词公式表达操作系统的安全属性,给出如何验证操作系统在运行过程中保持安全策略和属性的形式化描述方法.以实现并经过形式化验证的可信操作系统(VTOS)为例,阐述OSOSM的语义正确性.使用Isabelle定理证明工具验证设计和安全需求的一致性,以说明VTOS具有预期的安全属性.

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

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

BLP改进模型的形式化描述及自动化验证

在《信息安全技术操作系统安全技术要求》中,提出访问验证保护级安全操作系统的研发过程需要完全形式化的安全策略模型。针对该情况,对经典的数据机密性BLP模型进行相应改进,为系统中的主客体引入多级安全标签以及安全迁移规则,使其满足实际系统开发的需求。运用完全形式化的方法对改进模型的状态、不变量、迁移规则等进行描述,使用Isabelle定理证明器证明了迁移规则对模型的不变量保持性,从而实现对模型正确性的自动形式化验证,并保证了模型的可靠性。

面向命题投影时序逻辑的安全协议模型检测

针对无条件安全通信协议,特别是Russian Cards协议的安全性验证问题,提出基于命题投影时序逻辑(PPTL)的模型检测方法.根据协议构造规则建立了Russian Cards协议的ProMeLa模型;利用chop算子将多个交互事件进行顺序复合,以表达协议所期望的通信序列;由projection算子定义了协议在该序列上的安全性质,再将该性质转为Never Claim语法结构并连同协议模型作为模型检测器SPIN的输入,以完成验证工作.验证结果表明,由协议规则构造的Russian Cards通信协议是安全可靠的,该方法也适用于一般的无条件安全通信协议的验证.

嵌入式操作系统的形式化验证方法

对嵌入式操作系统类安全关键软件,测试、模拟、分析等传统软件验证方法不能保证其正确性,需要使用形式化方法。综述了主流商用嵌入式操作系统所采用的形式化验证方法,分析了操作系统内核不同特性的形式化验证思路。通常对空间隔离、信息流控制、系统调用、进程间通信等的证明采用定理证明方式,而对时间隔离的证明则采用模型检测方式。se L4的通用抽象和逐层精化方法、模型检测和定理证明的混合方法在工程使用中都有前途。

典型安全协议形式化分析工具比较

介绍了当前安全协议分析领域的典型形式化工具,阐述了其基本原理和在协议描述、归约、验证方面的研究现状,对它们的优缺点进行了综合比较,提出了如何在已有条件下开发协议分析工具的观点。

安全协议攻击序列重构技术

攻击者攻击序列在安全协议形式化分析技术中用于描述攻击者对安全漏洞的攻击步骤。目前,攻击序列重构技术是安全协议形式化分析研究的热点与难点。对国际流行的方法进行了介绍和总结,重点分析和比较了基于模型检测的方法、基于定理证明的方法、基于逻辑程序的方法等能够进行攻击序列重构的各种方法,指出了各自的优缺点及技术手段、技术特点,最后给出了该领域的进一步研究方向。

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

伴随着网络和通信的迅速发展,安全已经成为一个备受关注的问题,为确保不同系统的安全,出现了许多的安全协议。文中描述了安全协议验证的形式化需求,并且详细阐述了目前流行的几种形式化的验证技术及各自的优缺点,探讨了形式化验证技术所面临的挑战,指出目前在这方面所做的工作以及有待发展的方向。

密码协议的一种安全模型(英文)

将密码协议与密码算法视为一个系统,建立了密码协议系统的一种安全模型.基于假设/保证的组合推理技术提出了新的假设/保证推理规则和假设/保证推理算法,证明了该规则的完备性,实现了密码协议系统的模型检查,并重点解决了系统分解问题、假设函数的设定问题、进程+逻辑的系统特性描述问题等难题.以kerberos密码协议系统为例,利用该安全模型和假设/保证推理技术对密码协议系统进行了安全验证.

电子商务中安全协议的验证方法

该文简述了电子商务中的安全协议验证技术,对目前的一些重要的研究方法进行了分析和比较,重点针对形式化的方法在电子商务中的安全协议验证中的优势和不足,结合实际,提出了一些可能的发展趋势。

硬件设计的形式化验证技术

形式化验证用数学可证明的方式来验证系统.硬件设计的形式化验证通常有三种方法:定理证明、等价性检验和模型检验.文章着重分析了这三种方法的优缺点,探讨了形式化验证技术所面临的挑战,以及目前形式化验证技术可能的一些研究方向.

实用模型的自动化形式验证

通过给传统的Biba模型增加相应的敏感级函数,完善其主客体完整性标签,并对其安全操作规则进行相应的改进,使其适应实际的应用需求.采用完全形式化的方法对改进后模型中的各元素、模型必须满足的不变式以及模型迁移规则进行描述,并在此基础上利用定理证明器Isabelle完成对该模型的自动化形式验证,从而实现高等级安全操作系统研发过程中对安全策略模型的形式化需求.

安全协议分析的界——综合模型检查与Strand Spaces(英文)

Strand Spaces是一种用于分析安全协议的机器证明方法.简要介绍了 Strand Spaces的基本特点,分析了其优劣,提出了构造协议的理想子环的算法,并以此来约束协议入侵者的能力和协议并行运行的次数.将模型检查与 Strand Spaces结合在一起,提出了一种综合分析方法来验证协议的安全特性,该方法可充分发挥模型检查与 Strand Spaces二者的优势.

ROS中XML-RPC协议实现的形式化验证

XML-RPC协议是ROS节点通讯的核心调用机制,其实现的正确性关乎整个系统的顺利运行.使用模型检测和定理证明结合的方法对ROS系统中的XML-RPC协议进行验证.首先使用CBMC模型检测工具逐个验证协议源代码的函数,然后对模型检测不能全面验证的循环结构使用霍尔逻辑建立模型并在Isabelle/HOL定理证明器中验证.本文的工作结合两种形式化方法的优点,既克服了定理证明人工干预过多、工作量繁杂的问题,又避免了模型检测中出现状态爆炸的问题.

基于串空间的Athena分析技术研究

基于串空间模型的研究是当前安全协议领域的一个研究热点。Song对串空间模型进行了扩展,将模型检验和定理证明结合起来,提出了一种取名为Athena的安全协议分析方法,并基于该方法开发了自动证明工具APV,Song的工作被认为是串空间理论发展的一个重要事件。本文对Athena进行了系统的分析,介绍了Athena的假设条件,给出了Athena的语法和语义,分析了该逻辑的优点和局限性,在此基础上,分析了Athena的核心算法,讨论了A-thena算法自动高效的原因,以及该算法如何避免状态空间爆炸的技术,指出了该算法的缺陷,形成原因以及解决的一般方法。最后对Athena方法的发展方向进行了讨论。

机器人形式化验证方法综述

机器人的形式化验证方法通常很复杂,目前还没有一种通用的方法。本文对机器人的形式化设计和验证的概念进行介绍,描述其框架和基本方法。调查多个设计和验证项目,阐述项目的验证目标、方法、优缺点和进展情况。在总结研究现状的基础上,分析和展望机器人形式化设计和验证的发展趋势,从机器人模型设计、验证工具、代码实现等方面给出形式化设计和验证的思路。

一种基于Isabelle/HOL的安全通信协议验证方法

传统对称密钥加密协议的加密和解密速度较快,但用户无法进行身份认证,容易造成通信代理持有密钥过多导致管理困难的问题,而非对称密钥加密协议可实现用户的合法身份认证,但密钥复杂度高,使其在处理大容量消息时运行速度较慢。为解决上述问题,结合对称和非对称密钥加密方式,构建D_protocol混合密钥加密协议。使用Isabelle/HOL定理证明辅助工具对D_protocol协议建立通信代理和消息序列的形式化模型,采用形式化操作语义描述用户行为,通过归纳分析方式对通信协议消息交互过程涉及的相关定理展开验证,结果表明D_protocol协议在提高通信效率的同时具有较高的安全性,并且可在一定程度上抵抗外部攻击和中间人攻击。