面向SPARC处理器架构的操作系统异常管理验证

航天器等安全关键系统是典型的嵌入式系统,具有多任务并发、中断频发等特点,操作系统是其最基础的软件,构建一个正确的操作系统是保障航天器系统高可信运行的关键.异常管理作为操作系统最底层的功能负责引导系统控制流的突变来响应处理器状态中的某些变化,异常管理的正确性是整个操作系统正确性的基础.本文提出了一种基于Hoare-logic的验证框架,用于证明面向SPARC处理器架构操作系统异常管理的正确性,特别针对多任务并发和中断频发实时操作系统异常嵌套与异常中发生任务切换的情况,将异常管理划分为五个阶段进行全面的形式化建模,并且在Coq证明定理辅助工具中实现了此框架.基于该框架验证了我国北斗三号在轨实际应用的航天器嵌入式实时操作系统SpaceOS异常管理功能的正确性.     

微内核操作系统互斥量模块功能正确性的形式化验证

操作系统在许多安全攸关领域为软件系统提供关键性底层支撑，操作系统中一个微小的错误或漏洞都可能引起整个软件系统的重大故障，造成巨大经济损失或危及人身安全.为了减少此类安全事故的发生，对操作系统正确性进行验证十分必要.传统测试手段无法穷尽系统中的所有潜在错误，因而操作系统验证有必要使用具有严格数学理论基础的形式化方法.在操作系统中，互斥量可协调多任务对资源的访问，是一种常用的任务同步方式，其功能正确性对于保障多任务应用的正确性十分关键.本文基于定理证明方法，在交互式定理证明器Coq中对某抢占式微内核操作系统的互斥量模块进行代码级形式化建模，给出其接口函数的形式化规范，并实现这些接口函数的功能正确性验证.     

操作系统形式化设计与安全需求的一致性验证研究

采用数学形式化方法对操作系统进行设计和验证可以保证系统的高度安全性.目前已有的操作系统形式化研究工作主要是验证系统的实现在代码级的程序正确性.提出一种操作系统形式化设计和验证的方法,采用操作系统对象语义模型(OSOSM)对系统的设计进行形式化建模,使用带有时序逻辑的高阶逻辑对操作系统的安全需求进行分析和定义.对象语义模型作为系统设计和形式化验证的联系.以实现和验证过的可信微内核操作系统VTOS为实例,阐述形式化设计和安全需求分析,并使用定理证明器Isabelle/HOL①对系统的设计和安全需求的一致性进行验证,表明VTOS达到预期的安全性.     

复杂内核数据结构程序形式化验证

操作系统内核作为软件系统的基础组件, 其安全可靠是构造高可信软件系统的重要环节, 但是, 在实际的验证工作中, 操作系统内核中全局性质的不变式定义, 复杂数据结构程序的形式化描述和验证仍存在很多困难. 本文针对操作系统内核中满足的全局性质, 在代码层以函数为单位, 用全局不变式进行定义, 并在不同的函数中进行形式化验证, 从而证明各个函数符合操作系统内核的全局性质; 针对操作系统内核中经常使用的复杂数据结构程序, 本文通过扩展形状图理论, 提出一种使用嵌套形状图逻辑的方法来形式化描述复杂数据结构程序, 并对该方法进行了正确性证明, 最终成功验证操作系统内核中关于任务创建与调度, 消息队列创建与操作相关的代码.     

操作系统汇编级形式化设计和验证方法

由于系统的巨大规模,操作系统设计和实现的正确性很难用传统的方法进行描述和验证.在汇编层形式化地对系统模块的功能语义进行建模,提出一种汇编级的系统状态模型,作为汇编语言层设计和验证的纽带.通过定义系统状态模型的合法状态和状态转换函数来建立系统状态模型的论域,并以此来描述汇编层的论域.通过验证汇编层的功能模块的正确性来保证汇编语言层设计的正确性,达到对系统功能实现的正确性验证.同时,使用定理证明工具Isabelle/HOL来形式化地描述这一系统状态模型,基于这一形式化模型,在Isabelle/HOL中验证系统模块的功能语义的正确性.以实现的安全可信OS（verified secure operating system,简称VSOS）为例,阐述了所提出的形式化设计和验证方法,说明了这一方法的可行性.     

基于范畴论的业务目标模型形式化

面向目标需求语言模型（goal-oriented requirement language,GRL）聚焦于待定的需求,被广泛地应用于业务系统的初始需求建模,其模型的正确性影响到业务系统的开发质量。鉴于业务目标模型的形式化可以验证模型的正确性,提出了一种利用范畴论形式化GRL模型的方法。首先,依据GRL元模型结构,应用范畴论中的态射机制形式化描述GRL模型中目标与目标、目标与任务以及任务与任务等节点之间的关系;然后,通过增加范畴模型中的初始对象和终止对象,设计紧邻序列来表示多个目标与任务实施的因果关系;最后,设计业务目标模型系统的正确性结构性质。应用Web Payment系统实验表明,形式化业务范畴模型能够验证GRL模型的正确性,提高目标建模的质量。     

基于DH标定的机器人正向运动学形式化验证

DH坐标系在机器人运动学分析中发挥着重要的作用。在基于DH坐标系构建的机器人控制系统中,机器人结构的复杂性使得构建安全的控制系统成为一个难题,仅仅依靠人工方法可能导致系统漏洞和安全风险,从而危及机器人的安全。形式化方法通过演绎推理与代码抽取实现了对软硬件系统的设计、开发及验证。基于此,本文设计了基于DH标定的机器人正向运动学的形式化验证框架。在Coq中构建了机器人运动理论的形式化证明,并验证控制算法的正确性以确保机器人的运动安全。首先,对DH坐标系进行形式化建模,构建相邻坐标系间转换矩阵的形式化定义,并验证了该转换矩阵与复合螺旋运动的等价性;其次,构建了机械臂正向运动学的形式化定义,并对机械臂运动的可分解性进行形式化验证;再次,本文对工业机器人中常见连杆结构及机器人进行形式化建模,并完成了正向运动学的形式化验证;最后,本文实现了Coq到OCaml的代码抽取,并对抽取的代码进行分析与验证。     

XSM语义模型及安全需求形式化验证

Xen作为一种开源流行的虚拟化工具,使用越来越频繁。作为Xen的安全框架XSM(Xen Security Module)也受到广泛的关注。许多研究者通过形式化的方式对现有的操作系统进行正确性的验证,目前已有的形式化研究主要是验证系统实现的代码正确性。从系统功能角度提出了一种以主体行为为操作系统语义模型对系统进行形式化建模,并采用CTL时序逻辑对XSM安全需求进行分析。语义模型作为系统设计合理性和形式化验证的联系,对XSM进行形式化验证,并使用Isabelle/HOL验证功能和安全需求的一致性,以说明XSM是否符合安全需求。     

基于模型的开发方法在多应用智能卡中的应用

安全性、可靠性是嵌入式软件的重要性质。为了更好地保证开发的嵌入式软件是可靠和安全的,提出了一种基于模型的开发方法学,包括提炼需求、建立抽象模型及逐层精化三个步骤。首先从环境、功能、性质三个主要方面提取需求,同时明确层次化的精化策略;然后利用形式化方法建立抽象模型并对该模型进行形式化验证,在正确的抽象模型上逐层精化,并对每层模型进行验证;最后,基于满足需求的模型,进一步利用工具完成代码自动生成。该方法从抽象到具体,以逐层递增的方式明确被开发系统的需求及性质,进行形式化建模,通过反馈机制确保模型的正确性及可用性。为了证明该方法学的可行性,文章以多应用智能卡为开发实例,基于Event—B方法及Rodin平台给出了实际建模及证明的过程和结果。     

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

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

Verification of Real Time Operating System Exception Management Based on SPARCv8

Exception management,as the lowest level function module of the operating system,is responsible for making abrupt changes in the control flow to react to exception events in the system.The correctness of the exception management is crucial to guaranteeing the safety of the whole system.However,existing formal verification projects have not fully considered the issues of exceptions at the assembly level.Especially for real-time operating systems,in addition to basic exception handling,there are nested exceptions and task switching by exceptions service routine.In our previous work,we used high-level abstraction to describe the basic elements of the exception management and verified correctness only at the requirement layer.Building on earlier work,this paper proposes EMS(Exception Management SPARCv8),a practical Hoare-style program framework to verify the exception management based on SPARCv8(Scalable Processor Architecture Version 8) at the design layer.The framework describes the low-level details of the machine,such as registers and memory stack.It divides the execution logic of the exception management into six phases for comprehensive formal modeling.Taking the executing scenario of the real-time operating system SpaceOS on the Beidou-3 satellite as an example,we use the EMS framework to verify the exception management.All the formalization and proofs are implemented in the interactive theorem prover Coq.     

同步数据流语言高阶运算消去的可信翻译

Lustre是一种广泛应用于工业界核心安全级控制系统的同步数据流语言,采用形式化验证的方法实现Lustre到C的编译器可以有效地提高编译器的可信度.基于这种方法,开展了从Lustre*(一种类Lustre语言)到C子集Clight的可信编译器的研究.由于Lustre*与Clight之间巨大的语言差异,整个编译过程划分为多个层次,每个层次完成特定的翻译工作.阐述了其中高阶运算消去的翻译算法,翻译过程采用辅助定理证明工具Coq实现,并进行严格的正确性证明.     

面向安全关键内存管理系统分层验证方法

安全关键系统的失败会造成很严重的后果,确保其正确性非常重要.空间嵌入式操作系统是一个典型的安全关键系统,在其内存管理的设计上,必须保障其高效的分配与回收,同时对系统资源的占用降到最低.在传统的软件开发过程中,通常是在整个软件开发结束后再进行集中测试及验证,这样势必会造成开发进展的不确定性.因此,将形式化验证方法和软件工程领域内的“需求-设计-实现”的3层开发框架相结合,通过性质分层传递验证的方法,保证了各个层次间的一致性.首先,从需求层面的需求分析开始,引入形式化证明的思路,证明对需求层逻辑的正确性,从而可以更好地指导程序的设计.其次,在设计层面的验证可以极大地减少开发代码的错误率,证明设计算法和需要实现的函数之间调用逻辑的正确性.最后,在实现层,证明所实现代码与函数设计的一致性,并且证明代码实现的正确性.使用交互式定理证明辅助工具Coq,以某一国产空间嵌入式操作系统的内存管理模块为例,证明了其内存管理算法的正确性以及需求、设计、实现的一致性.     

Linux中SystemV进程通信机制安全性形式化验证

基于Linux开发安全操作系统是提高计算机安全的重要途径，而形式化验证则是开发过程的重要和必要的环节，我们从Linux的各个子系统着手进行验证，逐步搭建起整个操作系统的验证模型。考虑到访问控制机制是实现操作系统安全性的关键，本文主要讨论使用SPIN模型检验器对IPC子系统中的SystemV进程通信机制进行形式化验证的过程与方法法。查找安全漏洞并改进现有的机制，为开发工程提供理论上的保证。     

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

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

TD-LTE系统中MAC层子帧调度研究与实现

为满足TD-LTE系统对实时性的要求,通过对媒体接入控制(MAC)层和物理层之间的实时性研究以及对操作系统Nucleus PLUS的机制分析,实现了MAC层子帧调度。根据TD-LTE无线综合测试仪中的设计要求,详细介绍了Nucleus PLUS任务循环调度以及MAC子帧调度的流程设计。在实现MAC层基本功能的同时满足了TD-LTE对系统实时性、子帧同步与任务资源管理的需求。     

基于Z3的Coq自动证明策略的设计和实现

形式化验证方法被认为是一种构建高可信软件系统的有效手段.在定理证明工具通过手动写证明脚本来验证系统软件的功能正确性,这种验证方式表达力强,可以证明复杂系统,但是自动化程度低、验证代价比较高,而使用程序验证器接受经过规范标注的源代码生成验证条件,并将验证条件交给约束求解器自动求解,这种方式自动化程度高,缺点在于它很难验证复杂系统软件的全部功能的正确性.本文结合上述两种方式的优点,在定理证明工具Coq中实现了一个自动证明策略smt4coq,它通过在Coq中调用约束求解器Z3自动证明32位机器整数相关的数学命题,提高了自动化验证的程度,减轻用户手动验证程序的开销.