密码协议安全性证明系统解析器的设计与实现*

可证明安全性是密码协议安全性评估的重要依据,但手写安全性证明容易出错且正确性难以判定,利用计算机辅助构造游戏序列进而实现自动化证明是当前一种可行的方法。为此提出一种基于进程演算的密码协议形式化描述模型,定义了描述密码协议安全性证明中攻击游戏的语法规则,并借助工具LEX和YACC,设计出解析器程序,将密码协议及其安全性的形式化描述解析为自动化安全性证明系统的初始数据结构,并用实例来说明这种方法的可行性。     

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

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

基于ProVerif的安全协议形式化分析与验证

形式化方法是分析与验证安全协议属性的强有力的工具.在对一阶定理证明器ProVerif深入研究的基础上,对简化的Needham-Schroeder认证协议进行了形式化分析.     

基于函数式语义的循环和递归程序结构通用证明技术

各类安全攸关系统的可靠运行离不开软件程序的正确执行.程序的演绎验证技术为程序执行的正确性提供高度保障.程序语言种类繁多,且用途覆盖高可靠性场景的新式语言不断涌现,难以为每种语言设计支撑其程序验证任务的整套逻辑规则,并证明其相对于形式语义的可靠性和完备性.语言无关的程序验证技术提供以程序语言的语义为参数的验证过程及其可靠性结果.对每种程序语言,提供其形式语义后可直接获得面向该语言的程序验证过程.提出一种面向大步操作语义的语言无关演绎验证技术,其核心是对不同语言中循环、递归等可导致无界行为的语法结构进行可靠推理的通用方法.特别地,借助大步操作语义的一种函数式形式化提供表达程序中子结构所执行计算的能力,从而允许借助辅助信息对子结构进行推理.证明所提出验证技术的可靠性和相对完备性,通过命令式、函数式语言中的程序验证实例初步评估了该技术的有效性,并在Coq辅助证明工具中形式化了所有理论结果和验证实例,为基于辅助证明工具实现面向大步语义的语言无关程序验证工具提供了基础.     

基于Coq的软件安全性验证

针对数组越界、空指针应用和缓冲区溢出三类威胁软件安全的不规范操作,提出了一种基于Coq验证上述三类操作的形式化方法。首先编写三类安全问题的程序实例,并采用形式化方法进行标注;其次运用Frama-C和Why工具对标注程序进行解析,生成需要证明的定理;最后基于Coq集成开发环境证明定理,实现安全问题的验证。结果表明,该方法有效验证了软件安全中的三类问题,为形式化方法在软件安全性验证方面的应用奠定了基础。     

满足对应性属性的平台配置证明

针对完整性报告协议（IRP）存在局部和全局攻击的安全隐患,对StatVerif进行语法扩展,增加了与完整性度量相关的构造算子和析构算子,通过对平台配置证明（PCA）安全进行分析,发现其存在的局部攻击和全局攻击,包括通过未授权命令对平台配置寄存器和存储度量日志进行篡改。对攻击者能力进行了建模,详细说明了攻击者如何通过构造子和析构子形成知识,进而对平台配置证明进行攻击。最后,在平台配置证明不满足对应性属性的情况下,从理论上证明了攻击序列的存在,并给出了平台配置证明满足局部可靠和全局可靠的条件,通过形式化验证工具Proverif证明了命题的合理性。     

一种安全协议的形式化设计方法

本文以协议分析器为辅助工具,结合定理证明方法,给出一个安全协议形式化设计方法。该方法首先根据协议规范构造全信息项及冗余协议,使用定理证明保证冗余协议的安全性。对冗余协议利用安全性保持约简规则和随机约简规则进行约简,从而得到最优约简协议。该方法实现了安全协议的自动设计,具有良好的扩展性,可以根据需求和协议的发展增加设计规则和约简规则。     

eCK模型下的密钥协商

如何构造安全的密钥协商协议是信息安全领域富有挑战性的问题之一。目前安全协议只能达到"启发式"安全,协议的安全假设也不够理想。针对这一问题,提出了基于计算性假设(CDH)的三方认证密钥协商协议,并运用陷门测试定理形式化地证明该协议在eCK模型下是安全的,更好地支持了敌手的询问。     

SpaceWire译码电路在HOL4中的形式化验证

SpaceWire是在苛刻环境下的高速通信总线协议,译码电路是其接收端的关键电路,对该电路进行形式化验证具有重要的现实意义.形式化验证方法中的定理证明将需要分析的电路进行形式化建模,结合定理证明器,对模型的性质进行严格推理从而完成验证.本文运用定理证明的方法,在高阶逻辑证明工具HOL4中对SpaceWire总线的译码电路进行形式化验证.首先根据SpaceWire标准规范抽取相关性质,用高阶逻辑语言形式化描述;然后分析电路设计中的VHDL代码,依据代码实现的功能用相应的逻辑谓词建模;最后在HOL4中证明了译码电路设计的模型能满足所提取的性质.本文同时给出了形式化建模的方法和验证过程.     

eCK模型下可证明安全的双方认证密钥协商协议

如何构造安全的密钥协商协议是信息安全领域富有挑战性的问题之一.然而目前多数安全协议只能达到"启发式"安全,协议的安全性假设和效率也不够理想.针对这些问题,文中提出了一种新的两轮双方认证密钥协商协议,通过分析新协议的安全属性指出了构造双方认证密钥协商的一些原则.随后,在eCK模型下对新协议进行了严格的形式化证明,根据相关...     

基于定理证明的内存安全性动态检测算法的正确性研究

随着软件运行时验证技术的发展,出现了许多面向C语言的运行时内存安全验证工具.这些工具大多是基于源代码或者中间代码插桩技术来实现内存安全的运行时检测.但是,其中一些没有经过严格证明的验证工具往往存在两方面的问题,一是插桩程序的加入可能会改变源程序的行为及语义,二是插桩程序并不能有效保证内存安全.为了解决这些问题,文中提出...     

An abstract programming language and correctness proofs

The realization of an abstract programming language is a good approach for automating the software production process and facilitating the correctness proof of a software system.

This paper introduces a formal language for programming at the abstract level by combining Pascal with VDM (Vienna Development Method). The notation provided by the language obliges programmers to consider the correctness of programs throughout the whole process of programming, and the proof axiom and rules presented in this paper may be used to prove the correctness of programs. A complete example is given to illustrate how to program using APL and how to prove the correctness of programs using the given axiom and rules.     

面向形式化证明的命令生成技术

随着软件规模的不断增大,软件安全问题日益严重.作为软件系统安全检测的有效手段,形式化证明旨在利用数学方法完成对软件属性的严格验证.常用的形式化证明方法利用模式匹配来进行定理证明,但存在策略生成不完备等缺陷.本文提出一种基于注意力机制的命令预测框架,将LSTM与Coq结合,预测定理证明过程中的策略和参数.实验结果表明本文...     

动态存储管理安全验证的Coq实现

随着软件规模和复杂度的日益提升,软件安全的问题变得越来越严峻,同时有越来越多的研究工作集中在高可信软件的开发上 .由于类型系统表达能力的不足,现有的研究不触及底层软件的验证 .由于Hoare逻辑更好的表达能力,采用Hoare逻辑风格的推理,在汇编语言级别,使用Coq形式化与定理证明工具可以实现一个经过安全验证的动态存储管理函数库,这是程序验证技术一次有意义的实践 .实践表明,程序验证技术可以应用到高可信软件的开发上 .     

一种新的安全协议形式化分析方法——证据逻辑

形式化分析技术对于安全协议的正确设计至关重要,考虑到现有信仰逻辑分析方法的不足,该文提出一种新的安全协议形式化分析方法——证据逻辑,即通过对协议主体证据的推理来实现安全协议的形式化分析。与现有的方法相比,该方法不仅能够用于认证协议、密钥协商(交换)协议的分析,也能用于电子商务协议的不可否认性和公平性的分析,因此具有更好的通用性和更强的协议分析能力。     

基于哈希证明系统的区块链两方椭圆曲线数字签名算法研究

椭圆曲线数字签名算法(ECDSA)是区块链密码学技术中常见的数字签名之一,其在加密货币、密钥身份认证等方面已被广泛应用.然而当前的区块链ECDSA算法灵活性较低、匿名性较弱且分散性不高,性能相对高效的应用实例也十分有限.基于哈希证明系统,文章提出一种适用于区块链的两方椭圆曲线数字签名算法.通过给定签名算法的数理逻辑及其...     

Recursive Program Optimization through Inductive Synthesis Proof Transformation

The research described in this paper involved developing transformation techniques that increase the efficiency of the original program, the source, by transforming its synthesis proof into one, the target, which yields a computationally more efficient algorithm. We describe a working proof transformation system that, by exploiting the duality between mathematical induction and recursion, employs the novel strategy of optimizing recursive programs by transforming inductive proofs. We compare and contrast this approach with the more traditional approaches to program transformation and highlight the benefits of proof transformation with regards to search, correctness, automatability, and generality.     

Proof planning for strategy development

Proof planning extends the tactic-based theorem proving paradigm through the explicit representation of proof strategies. We see three key benefits to the proof planning approach to the development of proof strategies: flexibility, re-usability and synergy. Here we demonstrate these benefits in terms of reasoning about imperative programs where we reuse strategies developed previously for proof by mathematical induction. In particular, we focus upon strategies for automating the discovery of loop invariants. Our approach tightly couples the discovery of invariants with the process of patching proof strategy failures. This revised version was published online in June 2006 with corrections to the Cover Date.     

基于自证明公钥和零知识证明的身份认证协议

在分析几种典型零知识身份认证协议的基础上,利用Girault自证明公钥原理、结合椭圆曲线公钥密码的优点提出一种基于自证明公钥和零知识证明的身份认证协议,并为协议增加了密钥协商功能。分析表明该方案具有较高的安全性,与同类方案相比,该方案对存储空间、网络通信量和计算开销的要求较低,有较高的效率。     

基于国密SM2的高效范围证明协议

在范围证明这类特殊的零知识证明协议中,证明者无需提供具体元素信息即可向验证者证明某一承诺的元素在指定集合内.范围证明已被广泛应用于区块链、匿名证书、电子现金、群/环签名等需要身份/数据隐私保护的场景.范围证明协议的设计方法包括平方分解(Square Decomposition)、签名基(Signature-based)、内积(Innerproduct Argument)等,其中使用较为广泛的是Camenisch等在ASIACRYPT 2008会议上提出的签名基方法.然而,Camenisch等提出的范围证明协议不仅需要高耗时的双线性对运算,还涉及繁琐的证书管理,实用性还有待提高.虽然何德彪等(专利申请公布号:CN110311776A)利用国密SM9数字签名算法设计新的协议,避免了证书管理,但仍需要双线性对运算,所以协议的计算开销还较高.为了进一步减少计算量,丰富国产密码的应用,本文采用签名基方法,利用基于国密SM2的标识数字签名算法设计新的集合关系证明协议,有效解决证书管理和双线性对开销问题,在此基础上构造新的数值范围证明协议,支持更大范围的零知识证明.为了证明所设计协议的安全性,本文先证明基于国密SM2的标识数字签名算法在自适应选择消息和身份攻击下具有存在不可伪造性(EUF-CMID-A),在此基础上证明所设计协议满足完备性、可靠性和诚实验证者零知识性.与Camenisch等和何德彪等提出的协议相比,在相同优化参数情况下,本文协议的主要通信带宽约为1568字节,分别减少了41.66%和78.12%;主要计算开销约为491.5075毫秒,分别减少了85.93%和85.85%.这说明了本文设计的协议具有更强的实用性,更能满足前述场景的身份/数据隐私保护与有效性验证需求.