重写对策在基于HOL的形式化证明中的应用

讨论了重写对策在基于高阶逻辑定理证明系统HOL的形式化证明过程中的应用。通过REWRITE_TAC对策、ASM_REWRITE_TAC对策和RW_TAC对策,详细分析了重写对策的功能、应用方法、应用环境、应用中可能出现的问题以及解决办法,给出了DB.match搜索和DB.find搜索等重写对策的定理参数的选择方法,并进行了分析与比较。进一步说明了重写对策在基于HOL系统的形式化证明中的重要性,以期对HOL系统用户提供一些帮助与启发,促进HOL系统的进一步发展与完善,使形式化方法能够解决更多的实际问题。

基于Coq的杨忠道定理形式化证明

实现拓扑学定理的机器证明,是吴文俊院士生前的宿愿.杨忠道定理涉及一般拓扑学中的诸多基本概念,对深刻理解拓扑空间的本质有重要意义.该定理表明,拓扑空间中每一个子集的导集为闭集当且仅当此空间中的每一个单点集的导集为闭集,是一般拓扑学中的一个重要定理.基于定理证明辅助工具Coq,从公理化集合论机器证明系统出发,对一般拓扑学中的开集、闭集、邻域、凝聚点和导集等拓扑基本概念进行形式化描述,给出这些概念基本性质的形式化验证,建立了拓扑空间的形式化框架.在此基础上,实现基于Coq的杨忠道定理形式化证明.全部引理、定理和推论均完整给出Coq的形式化描述和机器证明代码,并在计算机上运行通过,体现了基于Coq的数学定理机器证明具有可读性、交互性和智能性的特点,其证明过程规范、严谨、可靠.杨忠道定理的形式化证明是一般拓扑学形式化内容的一个深刻体现.

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

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

图搜索问题算法推导及形式化证明

用非形式化方法解决图搜索问题规模受限,对于一些复杂问题难以保证其正确性.传统的形式化方法推导图搜索问题难以理解且不易于形式化证明,现有形式化方法对这类问题的解决方案较少,在保证可靠性和正确性方面有欠缺.该文通过对图搜索问题的深入研究,开发出一种针对解决图搜索算法的新方法.首先刻画问题的规约,利用循环不变式的递归定义技术给出了开发图搜索问题循环不变式的新策略,在此基础上得到Apla抽象算法程序,并对该算法程序进行了形式化证明,再将已验证的Apla算法程序自动生成C++可执行程序,实现了从抽象的形式规约推演出具体的面向计算机的程序代码的程序精化完整过程.以拓扑排序和广度优先遍历为例对所提方法进行实验,实验结果验证了所提方法的有效性,不仅可以推导和证明已知算法,而且对未知算法的推导也有指导性作用.

作为数学革命的形式化证明

随着计算机科学的兴起,数学家可以通过计算机完成对数学定理的证明与验证,由此形成了形式化证明的相关领域。在形式化证明的助力下,诸多数学难题得以攻破,这无疑改变了传统数学实践的范式。然而,学界对于形式化证明所引发的认识论转向的论述尚不充分,究其原因主要有两个方面:其一是缺乏对形式化证明的本体论考察,其二是对数学革命的定义存在分歧。对形式化证明中人脑证明和机器证明进行区分,同时厘清两种不同的革命定义,可以为形式化证明作为数学革命的观点提供辩护。

高可靠性温室环境测控系统架构形式化建模与特性证明

温室环境测控系统由多个可并发执行的子系统共同协作来构造适宜的温室环境以确保作物有效生长.为提高温室环境测控系统设计的效率和可靠性,本文提出一个能为设计者提供指导性框架的融入容错技术的高可靠性温室环境测控系统架构.并且运用PVS形式化语言对系统架构进行了精确而无二义性的形式化建模,以及PVS证明工具对系统架构的容错特性进行了机械化证明,以确保系统架构能满足高可靠性需求.

具有冲突约束的RBAC模型的形式化规范与证明

在实际应用"基于角色的访问控制"(RBAC)模型时,经常遇到由于责任分离等策略而引起的冲突问题,如权限间的互斥等.访问控制操作应满足某些约束条件,以避免冲突的存在.但这些冲突关系相当复杂,如何检测出冲突问题是模型安全实施的重要保证.借助Z语言,提出了基于状态的RBAC形式化模型,对状态转换函数进行了形式化规范,描述了操作的具体内容和应满足的冲突约束条件.根据安全不变量给出了安全性定理,分别进行数学的和形式化的证明.最后,通过实例分析,说明在实际系统中,如何形式化规约和验证RBAC系统并检测出冲突问题,从而为今后使用RBAC模型开发具有高安全保证的系统提供了一种形式化规范和证明方法.

分布实时系统的概率规范和证明形式化

1引言 随着数字系统变得越来越小、越来越便宜,它们用于物理过程控制和与物理过程互协作的机会将越来越多。互相协作的过程如果出现意外行为,后果将可能很严重。

基于PVS的飞机订票系统的形式化描述与验证

形式化方法主要应用于安全性第一的系统的规范与形式验证。原型证明系统PVS为开发和分析形式化规范和验证提供了一个集成化环境。本文介绍PVS系统的证明方法和特点 ,并利用PVS系统对飞机订票系统的需求给出了形式化规范 ,对部分关键属性完成了证明 。

Xen混合多策略模型的设计与形式化验证

Xen作为一种虚拟化工具因开源、高效等特点而受到越来越多的关注。作为Xen安全的基础,XSM决定了其安全性。原生XSM没有对系统资源进行安全分级,并且以虚拟机为管理对象使得Dom0作为一个唯一管理域不符合最小特权,文中设计了一种混合多策略模型SV_HMPMD。在该模型中,针对BLP引入多级安全标签,从而增加BLP的实用性,并通过DTE和RBAC对特权进行更细致的划分,从而对Dom0特权进行合理限制。提出了一种分层模型,利用该模型对混合模型进行形式化的描述。运用系统不变量构造访问规则的安全属性需求,通过Isabelle/HOL对模型设计与安全需求的一致性进行验证。

面向无线传感器网络的认证密钥协商机制

无线传感器网络(Wireless Sensor Networks,WSN)是物联网的重要组成部分,因为WSN能通过因特网将采集到的数据发送到云服务器.认证和密钥协商机制是一个重要的密码学概念,可以确保数据传输的安全和完整性.传感器节点是资源受限的设备,因此目前多数认证和密钥协商机制在计算效率上并不适用于WSN.针对该问题,本文提出了一种新的认证和密钥协商机制,该方案是一种基于椭圆曲线的轻量级认证和密钥协商方案.在eCK安全模型下,将方案的安全性规约到CDH数学困难假设之上,形式化的证明了方案的安全性.最后通过方案对比,表明文章所提出的方案实现了计算效率和安全属性之间的平衡.

面向HDFS的可证明安全的单点登录协议

针对Hadoop distributed file system(HDFS)的安全机制中密钥管理复杂、用户需进行多次身份认证的问题,提出一个适合HDFS的基于身份的单点登录协议。协议采用基于身份的密码技术实现了用户的单点登录,同时根据各个节点上一次为用户提供服务的情况对用户登录票据的流转过程进行了优化,并且运用Capser形式化证明工具对协议的安全性进行了证明。协议降低了HDFS在密钥管理上的开销,解决了用户访问HDFS可能需要频繁认证的问题,提高了登录票据流转的效率,同时协议还具有较高的安全性。理论分析和安全性验证表明,本协议对HDFS的安全高效运行有较大的帮助。

一个出具证明编译器原型系统的实现

出具证明编译器是随着人们对现今的软件提出更高的可靠性和安全性要求而产生的工具,它结合了以往程序设计和程序安全性证明的技术。论文介绍了一个出具证明编译器原型系统的实现。

基于Coq构造携带证明的安全程序

对可靠程序的需求随着高可信软件在信息社会中的作用日益重要而增加。基于形式化证明工具构造携带证明的安全程序,给出严格的程序规范及其证明是提高软件可靠性的重要途径。论文介绍使用形式化证明工具Coq构造安全程序的过程和经验。

Lebesgue积分在PVS中的证明分析

为了有效解决函数系统建模、信号实时分析等数理支持领域验证与测试的定理证明形式化问题,设计并实现了利用Lebesgue积分的运算特征在PVS定理证明器中进行形式化证明与分析.主要对其分裂定理、不等式计算、闭区间子集可积分性、多重分部、线性运算、Cauchy可积分准则和极限定理等多个方面进行了形式化,且依据数学定理与推论形式化,说明Lebesgue积分在PVS中的形式化是可行的、有效的.以标准反相积分器为应用模型,对其通用电路原理与机制进行了形式化证明,通过数理分析测试了本文Lebesgue积分形式化定理库的正确性.

刑事证明标准客观化的理论与实践审视

“案件事实清楚,证据确实、充分”证明标准因其立法理想化而受到诸多批判。为强化其实践指引功能,学界及司法实务部门对证明标准进行了外在化、具体化的客观化探索。证明标准客观化具有现实的社会基础和正当性价值,但也存在使诉讼证明走向形式化的法治风险。对此,未来刑事证据立法应当明晰证明标准客观化的合理界限,转变从立法上追求证明标准明确化的思路,激活法官排除合理怀疑的心证功能。同时,随着人工智能在司法领域的深度运用,实践中亦当理性对待证明标准数据化问题。

基于标识的无线Mesh网络接入认证协议

为解决无线Mesh网络节点高效、安全入网认证的问题,提出了一种新的基于标识认证的无线Mesh网络接入认证协议。该协议针对无线Mesh网络的特点,将标识认证体制引入到无线Mesh节点接入认证当中,并在标识认证的基础上一次性完成了入网节点的双向身份认证、网络认证和空口密钥的建立3个步骤。简化了认证的流程,减少了认证的时延,达到了分布式认证的效果,为大规模的节点接入提供了一种新的认证方案。通过BAN逻辑形式化方法证明了协议的安全性,通过效率分析说明了协议的高效性。

新物联网下的RFID双向认证协议

针对物联网发展的新形势提出一个新型的双向认证协议.有别于传统的RFID认证协议,通过基于零知识证明的认证方法来认证成员身份,并将参与主体的身份安全规约到其自身身份密钥的安全性上.解决了传统的基于加密算法的认证协议中主体的身份安全依赖于所有参与实体信息安全的问题.新协议能够满足一个标签在多个互联的RFID系统中应用时的认证安全.本文给出新协议的详细描述,并且用基于串空间模型的形式化证明方法证明了协议至少满足认证性、秘密性和标签不可追踪性的要求.

基于位替换运算的RFID双向认证协议

安全性是射频识别系统面临的重要隐患,针对该问题,设计了用于加密的位替换运算,并提出了一种新的基于位替换运算的RFID双向认证协议(SRMAP)。安全与性能分析表明:SRMAP可抵抗多种潜在攻击,且能够使标签内计算操作、存储空间及通信量得以降低。最后,采用BAN逻辑方法形式化证明了该协议的正确性与安全性。

eCK模型下的密钥协商

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