基于Coq的微内核操作系统程序验证方法研究

机载嵌入式程序的可信属性验证是新一代飞机研制最关注的软件质量保障问题;基于定理证明的程序形式化验证方法是一种可靠和严格的软件正确性验证技术;文中在深入分析微内核操作系统的基础上,应用霍尔逻辑针对机载嵌入式软件核心代码开展程序验证技术研究,根据霍尔逻辑的相关推理规则进行程序验证,并在定理证明辅助工具Coq中形式化表示霍尔逻辑的推理规则,针对机载操作系统的部分程序代码实例进行验证;实验结果表明基于定理证明的程序验证方法可以对软件程序代码的正确性进行验证,从而帮助软件提供商开发高可信的机载嵌入式软件。     

基于交互式定理证明的并发程序验证工作综述

并发程序与并发系统可以拥有非常高的执行效率和相对串行系统较快的响应速度,在现实中有着非常广泛的应用。但是并发程序与并发系统往往难以保证其实现的正确性,实际应用程序运行中的错误会带来严重的后果。同时,并发程序执行时的不确定性会给其正确性验证带来巨大的困难。在形式化验证方法中,人们可以通过交互式定理证明器严格地对并发程序进行验证。本文对在交互式定理证明中可用于描述并发程序正确性的验证目标进行总结,它们包括霍尔三元组、可线性化、上下文精化和逻辑原子性。交互式定理证明方法中常用程序逻辑对程序进行验证,本文分析了基于并发分离逻辑、依赖保证逻辑、关系霍尔逻辑等理论研究的系列成果与相应形式化方案,并对使用了这些方法的程序验证工具和程序验证成果进行了总结。     

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

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

机械化定理证明研究综述

随着现代社会计算机化程度的提高,与计算机相关的各种系统故障足以造成巨大的经济损失.机械化定理证明能够建立更为严格的正确性,从而奠定系统的高可信性.针对机械化定理证明的逻辑基础和关键技术,详细剖析了一阶逻辑和基于消解的证明技术、自然演绎和类型化的λ演算、3种编程逻辑、基于高阶逻辑的硬件验证技术、程序构造和求精技术之间的联系和发展变迁,其中,3种编程逻辑包括一阶编程逻辑及变体、Floyd-Hoare逻辑和可计算函数逻辑.然后分析、比较了各类主流证明助手的设计特点,阐述了几个具有代表性的证明助手的开发和实现.接下来对它们在数学、编译器验证、操作系统微内核验证、电路设计验证等领域的应用成果进行了细致的分析.最后,对机械化定理证明进行了总结,并提出面临的挑战和未来研究方向.     

基于ZigBee技术的无线温度采集系统

详细阐述了ZigBee技术及其应用,提出了一种基于ZigBee技术的无线温度采集系统的方案.针对所提方案设计了系统的硬件电路及相关软件,并通过实验证明了方案的可行性及正确性.     

舰载机弹药保障作业调度的形式化建模与验证

航母舰载机弹药保障作业的智能规划作为一种高效能航保作业调度方法,是助推航母工程先进技术建设发展的重要途径之一.高安全攸关属性下作业规划方案的正确性保证已经逐渐成为制约其实际应用部署安全的关键技术瓶颈.针对方案正确性验证中存在的弹药保障系统难建模、作业执行行为难描述、形式验证工具难实现等挑战,基于分离逻辑的思想,提出一种弹药保障系统的行为模型,并利用定理证明器Coq对作业规划方案进行形式化验证.首先提出一个符合弹药保障作业特征的序列化双层资源堆模型;基于该模型,构造一套可用于描述作业执行行为的建模语言及其操作语义;最后在Coq中实现一种证明辅助工具.通过几个典型弹药保障作业规划方案的交互式证明实例,验证工具的可用性与工程实用性.     

基于约束的服务化软件测试系统

面向服务的软件体系结构近年来不仅在民用领域得到广泛应用，也越来越多地应用于军用装备软件系统研制。服务化软件的测试技术得到了越来越多的关注。传统的服务化软件测试工具大多关注于测试流程的自动化，在测试用例的自动生成等方面，还远不够成熟。现有测试技术和工具尤其难以表达真实应用中的业务逻辑规则，给生成高质量的测试带来许多困难。鉴于此，研发了一款针对服务化系统的软件测试原型工具。该工具运用一阶逻辑公式表达业务逻辑约束，基于Z3 SMT约束求解器生成测试用例、进行故障注入等，使得测试数据的生成更契合待测软件业务特征，为服务化软件的测试实践提供了更有力支持。     

模拟Boyer-Moore定理证明器

SBMTP(Simulate Boyer-Moore Theorem Prover)系统是在IBM-PC-386微机上用GCLISP语言实现的一个定理证明系统。该系统采用的思想方法和理论基础是Boyer-Moore的计算逻辑理论. SBMTP主要由三部分组成:知识库管理部分、定理证明部分及中断恢复部分。 知识库管理部分包括一个基本知识库和一系列知识库构造工具。用户可根据具体问题 灵活地组织自己所需要的知识库,定理证明部分采用启发式方法逐步推演,完成证明。中断恢复部分在证明产生中断的情况下提供了较强的恢复能力,提高了证明效率。     

模拟Boyer-Moore定理证明器

SBMTP(Simulate Boyer-Moore Theorem Prover)系统是在IBM-PC-386微机上用GCLISP语言实现的一个定理证明系统。该系统采用的思想方法和理论基础是Boyer-Moore的计算逻辑理论. SBMTP主要由三部分组成:知识库管理部分、定理证明部分及中断恢复部分。 知识库管理部分包括一个基本知识库和一系列知识库构造工具。用户可根据具体问题 灵活地组织自己所需要的知识库,定理证明部分采用启发式方法逐步推演,完成证明。中断恢复部分在证明产生中断的情况下提供了较强的恢复能力,提高了证明效率。     

基于MQTT协议扩展的IoT设备完整性监控

随着物联网飞速发展,设备数量呈指数级增长,随之而来的IoT安全问题也受到了越来越多的关注.通常IoT设备完整性认证采用软件证明方法实现设备完整性校验,以便及时检测出设备中恶意软件执行所导致的系统完整性篡改.但现有IoT软件证明存在海量设备同步证明性能低、通用IoT通信协议难以扩展等问题.针对这些问题,本文提供一种轻量级的异步完整性监控方案,在通用MQTT协议上扩展软件证明安全认证消息,异步推送设备完整性信息,在保障IoT系统高安全性的同时,提高了设备完整性证明验证效率.我们的方案实现了以下3方面安全功能:以内核模块方式实现设备完整性度量功能,基于MQTT的设备身份和完整性轻量级认证扩展,基于MQTT扩展协议的异步完整性监控.本方案能够抵抗常见的软件证明和MQTT协议攻击,具有轻量级异步软件证明、通用MQTT安全扩展等特点.最后在基于MQTT的IoT认证原型系统的实验结果表明, IoT节点的完整性度量、MQTT协议连接认证、PUBLISH报文消息认证性能较高,都能满足海量IoT设备完整性监控的应用需求.     

超长整数运算的PVS规范与验证

超长整数的运算是现代密码系统的应用基础,运算的正确性关系到密码系统的应用价值。为了验证超长整数算法的设计与需求目标之间的一致性,利用原型验证工具PVS对算法的正确性进行了证明。在介绍了超长整数的加法和减法算法并分析了其设计思想之后,给出了超长整数及其算法的形式规范,通过把算法需要满足的性质描述为定理,将算法的一致性验证问题转化为逻辑定理证明的问题,在PVS定理证明器上完成了相关定理的证明,从而表明这些算法是满足设计需求的。     

GJK算法的一种特殊情形的形式化验证和应用

计算几何算法经常用于机器人避碰运动规划等安全攸关领域,对这些算法进行正确性证明非常重要.用形式化方法对算法进行验证是一种十分有效的手段,尤其是定理证明的方法用严格的数学公理和定理推理证明逻辑模型的性质,对所验证的性质而言是完备的.基于GJK算法设计了计算空间两条线段间距离的算法,用定理证明器HOL4对其相关的定义和定理进行形式化定义和证明,进而基于霍尔逻辑完成形式化表示和证明,对该算法的正确性实现了形式化验证.最后,给出了这一经过验证的算法在双臂机器人无碰撞运动规划中的应用.     

支持索引式的PPTL定理证明器的实现

定理证明是目前主流的形式化验证方法,拥有强大的抽象和逻辑表达能力,且不存在状态空间爆炸问题,可用于有穷和无穷状态系统,但其不能完全自动化,并且要求用户掌握较强的数学知识.含索引式的命题投影时序逻辑(PPTL)是一种具有完全正则表达能力,并且包含LTL的时序逻辑,具有较强的建模和性质描述能力.目前,一个可靠完备的含索引式的PPTL公理系统已被构建,然而基于该公理系统的定理证明尚未得到良好工具的支持,存在证明自动化程度较低以及证明冗长易错的问题.鉴于此,首先设计了支持索引式的PPTL定理证明器的实现框架,包括公理系统的形式化与交互式定理证明;然后,在Coq中形式化定义了含索引式的PPTL公式、公理与推理规则,完成了框架中公理系统的实现;最后,通过两个实例的交互式证明验证了该定理证明器的可用性.     

区间时序逻辑的标记相继式演算

区间逻辑在许多领域如人工智能,形式化方法中都有成功应用。其中,区间时序逻辑及其各种扩充近年来越来越多地受到人们的重视,由于区间时序逻辑具有较强的表达能力,这也使得该逻辑的定理证明变得相当困难,该文提出了区间时序逻辑的一个标记相继式演算,并给出其可靠性和相对完备性结论。该演算应用于机器辅助定理证明工具中,可以有效地提高证明的自动化程度,在高阶逻辑证明了工具ＰＶＳ中,作者尝试性地实现了这一演算,获得了     

基于演化Agent的推理模型

本文描述了一种基于演化 agent的推理模型 ,并用这种推理模型来处理定理机器证明 .传统上 ,定理机器证明常常使用某种逻辑表示 ,然后再进行推理 ,这些方法往往缺乏灵活性 ,且证明过程难以理解 .在本文所叙述的方法中 ,演化 agent能将目标即待证定理分解成越来越小且越来越容易证明的子目标 ,最后完成定理证明 .这种方法非常类似于人类在证明定理时一般所采用的思维方式 ,因而 ,显得更灵活、更具有适应性     

一种基于分离逻辑的块云存储系统验证工具

云存储技术目前被广泛应用于人们的生产与生活中.验证云存储系统中管理程序的正确性,能够有效地提高整个系统的可靠性.块云存储系统(CBS)具有最接近底层的存储架构.运用交互式定理证明器Coq,实现了一种辅助验证工具,用于分析和验证CBS中管理程序的正确性.基于分离逻辑的思想,对工具中证明系统的实现主要包括:首先,将CBS抽象为两层堆结构,定义建模语言形式化表示CBS的状态和管理程序;其次,定义描述CBS状态性质的堆谓词,并说明堆谓词间的逻辑关系;最后,定义描述程序行为的CBS分离逻辑三元组,以及制定验证三元组所需的推理规则.此外,还引入了几个证明实例,以此展示工具对实际CBS管理程序表示和推理的能力.     

粒计算研究现状及基于Rough逻辑语义的粒计算研究

综述了粒计算的提出背景、研究现状及其发展趋势,也给出了作者的评论;论述了粒计算应用的广泛性,包括AI中的图像检索、医学诊疗系统、连续数学中的积分学及其它许多逻辑推理等方面的应用.讨论了粒计算将有希望成为处理信息和研究其它学科的理论工具和方法学.讨论了粒计算中基于Rough逻辑语义的粒及其相关性质,建立了这种粒的演绎推理.提出了基于Rough逻辑语义的粒归结原理和归结策略,包括λ-归结策略和锁归结策略.证明了这种粒归结的完全性.基于Rough逻辑语义的粒在AI的问题求解、专家系统以及机器定理证明中都将成为一种新的研究思想和新的理论工具.最后,提出了这种基于Rough逻辑语义的粒计算研究前景.     

验证带有线程的动态创建和退出的多线程程序

近来在程序验证领域,Feng和Shao提出一个类Hoare逻辑的验证框架以验证包含中断的底层程序.在该工作基础上进行扩展,提出一个验证包含线程的动态创建和退出机制程序的框架.框架包含抽象机器模型、指令规范、逻辑推理系统、框架可靠性定理其证明.框架采用Hoare风格的推导方式,使用高阶逻辑描述指令的推理规则和安全策略,为证明带有线程的动态创建和退出的多线程程序的部分正确性提供了一种实用的方法.     

基于UPPAAL的微内核操作系统程序验证方法研究

随着航天、航空工业的发展,机载嵌入式软件的可信属性验证是新一代飞机研制最关注的软件质量保障问题。形式化方法具有严密的数学基础,能够准确的对系统进行建模、描述和验证,能够在软件系统的设计初期发现潜在的错误,是保证机载软件可信性和安全性的软件正确性验证技术。形式化验证以形式化描述为基础,对所描述系统的特性进行分析和验证,以评判系统是否满足期望的性质,分为定理证明和模型检测两类。文章研究模型检测方法应用于程序形式化描述和验证的技术,提出基于模型检测的验证程序正确性的方案,并进行微内核操作系统程序分析,最后在UPPAAL中进行程序属性的验证。     

断言语言支持自定义谓词的程序验证器原型

基于逻辑推理的方法进行程序验证是形式化程序验证的研究热点.目前的自动验证工具为了保证自动性,对描述程序性质的断言语言都有较多限制,导致程序的某些递归性质难以用断言语言表述.本文在一个面向指针程序、基于先前自行设计的形状图逻辑、依赖于自动定理证明工具Z3的自动程序验证原型系统上,通过在断言语言中引入自定义谓词来增强断言语言的表达能力,使得该原型系统不仅能自动验证含操作易变数据结构的程序的性质,也能自动验证一些不含指针的程序的性质.