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

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

基于系统理论过程分析的软件安全性需求分析与验证方法

针对传统系统理论过程分析（STPA）方法缺乏自动化实现手段、自然语言结果分析存在歧义性的问题,提出一种基于STPA的软件安全性需求分析与验证方法。首先,提取软件安全性需求,并利用算法将其转化为形式化表达式;其次,建立状态图模型来描述软件安全控制行为逻辑,并将其转化为程序可读的形式化语言;最后,采用模型检验技术进行形式化验证。结合某武器发射控制系统案例验证了方法的有效性,结果表明,该方法能够实现安全需求分析的自动化生成与形式化验证,解决了传统方法对于人工干预的依赖问题及自然语言描述问题。     

一种结合线性时序逻辑和故障树的软件安全验证方法

嵌入式软件在安全关键领域的广泛应用使得保障软件的安全性成为学界的研究热点。故障树技术是工业界常用的传统的安全分析方法之一。然而,传统的故障树无法精确描述安全关键系统中具有时序特征的系统故障。针对此问题,给出了一种结合线性时序逻辑和故障树的安全验证方法。该方法运用线性时序逻辑对故障树进行形式化规约,从中抽取出软件安全属性并用时序逻辑公式进行描述,用以支持对安全关键软件的模型检验。最后,以某机载控制系统软件数据处理故障模块的模型检验为例,来说明该方法的有效性和可行性。     

一种基于模型检测的二进制程序脆弱性分析框架

针对二进制程序脆弱性分析的实际需求,提出了一种基于模型检测的二进制程序脆弱性分析框架。首先定义了二进制程序的抽象模型,描述了基于有限状态自动机的软件脆弱性形式化表示和基于事件系统的软件安全属性表示方法。在此基础上,提出了基于模型检测的脆弱性分析过程和算法。根据该分析框架,设计并实现了二进制程序脆弱性分析工具原型。通过脆弱性分析实验,详细说明了该框架的工作原理,验证了该分析方法的有效性。     

基于系统理论过程分析的软件安全性需求分析与验证方法

针对传统系统理论过程分析（STPA）方法缺乏自动化实现手段、自然语言结果分析存在歧义性的问题，提出一种基于STPA的软件安全性需求分析与验证方法。首先，提取软件安全性需求，并利用算法将其转化为形式化表达式；其次，建立状态图模型来描述软件安全控制行为逻辑，并将其转化为程序可读的形式化语言；最后，采用模型检验技术进行形式化验证。结合某武器发射控制系统案例验证了方法的有效性，结果表明，该方法能够实现安全需求分析的自动化生成与形式化验证，解决了传统方法对于人工干预的依赖问题及自然语言描述问题。     

支持模型检测的故障树生成方法研究

论文运用时序逻辑对传统故障树进行形式化规约,并从中抽取出描述软件安全属性的时序逻辑公式,来支持对安全关键软件的模型检测。文章以对某一机载控制系统软件数据交互模块的模型检测为案例研究,实验结果证明本文提出方法有效。     

软件漏洞静态检测模型及检测框架

软件漏洞静态分析是信息安全领域的重点研究方向,如何描述漏洞及判别漏洞是漏洞静态分析的核心问题。提出了一种用于描述和判别漏洞的漏洞静态检测模型。首先对软件漏洞的属性特征进行形式化定义,并对多种软件漏洞和其判定规则进行形式化描述;其次,针对传统的路径分析存在的状态空间爆炸问题,提出了一个新的程序中间表示——漏洞可执行路径集,以压缩程序状态空间。在该模型的基础上,设计了一个基于漏洞可执行路径集的软件漏洞静态检测框架,利用定义的漏洞语法规则求解漏洞可执行路径集上的漏洞相关节点集,利用漏洞判定规则对漏洞相关节点集进行判别得出漏洞报告。实验分析验证了该漏洞检测模型的正确性和可行性。     

面向DO-333的襟缝翼控制单元安全性分析

DO-333是对机载软件安全性标准DO-178C关于形式化方法的补充,为机载软件开发过程中形式化方法的使用提供指导。模型检验作为一种形式化方法,可以应用于对软件需求和设计阶段制品的严格验证。基于DO-333,使用模型检验对飞控系统中襟缝翼控制单元不同阶段的软件制品进行验证与分析,判断其是否满足DO-178C的相关验证目标并提供证据支持。首先,对控制单元中襟翼与缝翼必须互斥更新的高级需求进行规约和验证;其次,对单个机翼控制逻辑的低级需求进行规约和验证。通过以上验证与分析,分别为标准中关于高级和低级需求的验证目标提供证据。文中展示了模型检验在一个机载软件认证中的应用实例,该工作将为机载软件的安全性保障和适航认证提供技术支持。     

面向DO-178C的襟缝翼控制系统需求的形式化描述

DO-178C是对机载软件适航认证标准DO-178B的改进和补充,用于对民用飞机机载系统和设备软件质量控制提供指导。SCR(Software Cost Reduction)方法作为一种形式化方法,基于四变量模型,可以对复杂和大型的嵌入式系统进行需求描述。文中基于DO-178C,使用SCR方法对原飞机系统中的襟缝翼控制系统的需求文档进行形式化的需求描述,针对襟缝翼控制系统中的襟翼电机转速控制模块进行详细的案例分析,判断其是否满足DO-178C的相关验证指标。通过分析和验证,提出了SCR方法中的一些应用技巧。该工作可为SCR方法在机载软件系统中的应用提供依据。     

一种用描述逻辑刻画多代理系统规约的方法

支持模块化的语言机制和严格性能够很好地推动代理技术向更广泛的、更大规模的应用发展.朱宏等人提出的基于模型的多代理系统开发方法提出了符合面向Agent软件工程思想的语言机制,如Caste和Scenario.以该方法为基础提出了基于描述逻辑的对多代理系统的规约进行形式化刻画和分析证明系统属性的方法.利用描述逻辑的强大的表达力刻画多代理系统的规约,利用其自身的推理机制对系统属性进行推理、证明和验证,可以增强基于代理系统的严格性.     

Gray-box monitoring of hyperproperties with an application to privacy

Formal Methods in System Design - Runtime verification is a complementary approach to testing, model checking and other static verification techniques to verify software properties. Monitorability...     

The role of model checking in software engineering

Model checking is a formal verification technique. It takes an exhaustively strategy to check hardware circuits and network protocols against desired properties. Having been developed for more than three decades, model checking is now playing an important role in software engineering for verifying rather complicated software artifacts.This paper surveys the role of model checking in software engineering. In particular, we searched for the related literatures published at reputed conferences, symposiums, workshops, and journals, and took a survey of (1) various model checking techniques that can be adapted to software development and their implementations, and (2) the use of model checking at different stages of a software development life cycle. We observed that model checking is useful for software debugging, constraint solving, and malware detection, and it can help verify different types of software systems, such as object- and aspect-oriented systems, service-oriented applications, web-based applications, and GUI applications including safety- and mission-critical systems.The survey is expected to help human engineers understand the role of model checking in software engineering, and as well decide which model checking technique(s) and/or tool(s) are applicable for developing, analyzing and verifying a practical software system. For researchers, the survey also points out how model checking has been adapted to their research topics on software engineering and its challenges.     

基于SysML的机载软件分层精化建模与验证方法

机载软件被广泛应用于航空航天领域, 大幅提升了机载设备的性能.但随着机载软件规模逐渐增大、功能逐渐增多, 给软件的开发带来了难度, 如何保障机载软件的正确性和安全性也成为一个难题.基于模型的开发可以有效提升开发效率, 而形式化方法能够有效保障软件的正确性.为了降低开发难度, 同时保障机载软件的正确性、安全性, 本文提出一种基于SysML状态机图子集的机载软件分层精化建模与验证方法.首先使用SysML状态机图对机载软件的动态行为进行建模, 根据提出的精化规则, 对初始模型进行手动逐层精化得到精化设计模型.然后针对软件模型动态变化的特性, 将SysML状态机模型自动转换为时间自动机网络, 并从软件需求中手动提取形式化TCTL性质进行模型检验.其次, 为了实现编码自动化, 将SysML模型自动转换至Simulink, 利用Simulink Coder生成源代码.最后, 以一个自动飞行控制软件为例进行了开发和验证, 实验结果表明了该方法的有效性.     

Modeling and formal verification of embedded systems based on a Petri net representation

In this paper we concentrate on aspects related to modeling and formal verification of embedded systems. First, we define a formal model of computation for embedded systems based on Petri nets that can capture important features of such systems and allows their representation at different levels of granularity. Our modeling formalism has a well-defined semantics so that it supports a precise representation of the system, the use of formal methods to verify its correctness, and the automation of different tasks along the design process. Second, we propose an approach to the problem of formal verification of embedded systems represented in our modeling formalism. We make use of model checking to prove whether certain properties, expressed as temporal logic formulas, hold with respect to the system model. We introduce a systematic procedure to translate our model into timed automata so that it is possible to use available model checking tools. We propose two strategies for improving the verification efficiency, the first by applying correctness-preserving transformations and the second by exploring the degree of parallelism characteristic to the system. Some examples, including a realistic industrial case, demonstrate the efficiency of our approach on practical applications.     

Efficient verification of railway infrastructure designs against standard regulations

In designing safety-critical infrastructures s.a. railway systems, engineers often have to deal with complex and large-scale designs. Formal methods can play an important role in helping automate various tasks. For railway designs formal methods have mainly been used to verify the safety of so-called interlockings through model checking, which deals with state change and rather complex properties, usually incurring considerable computational burden (e.g., the state-space explosion problem). In contrast, we focus on static infrastructure models, and are interested in checking requirements coming from design guidelines and regulations, as usually given by railway authorities or safety certification bodies. Our goal is to automate the tedious manual work that railway engineers do when ensuring compliance with regulations, through using software that is fast enough to do verification on-the-fly, thus being able to be included in the railway design tools, much like a compiler in an IDE. In consequence, this paper describes the integration into the railway design process of formal methods for automatically extracting railway models from the CAD railway designs and for describing relevant technical regulations and expert knowledge as properties to be checked on the models. We employ a variant of Datalog and use the standardized “railway markup language” railML as basis and exchange format for the formalization. We developed a prototype tool and integrated it in industrial railway CAD software, developed under the name RailCOMPLETE^®. This on-the-fly verification tool is a help for the engineer while doing the designs, and is not a replacement to other more heavy-weight software like for doing interlocking verification or capacity analysis. Our tool, through the export into railML, can be easily integrated with these other tools. We apply our tool chain in a Norwegian railway project, the upgrade of the Arna railway station.     

模式驱动的系统安全性设计的验证

随着万维网和移动计算技术的广泛应用,系统安全性得到了越来越多的关注,使用安全模式对系统安全解决方案进行设计并验证是提升系统安全性的一种有效途径。现有方法根据系统安全需求选择适用的安全模式,在此基础上将模式组合为系统的安全解决方案,并通过模型检测方法验证其安全性。但是,这些方法往往将方案看作整体进行验证,忽略了内部安全模式的组合细节,难以在包含大量模式的复杂系统中定位缺陷。提出一种模式驱动的系统安全性设计的验证方法,首先使用代数规约语言SOFIA描述安全模式及其组合,以构建系统安全解决方案的形式化模型;然后将SOFIA规约转换为Alloy规约后,使用模型检测工具验证模式组合的正确性和系统的安全性。案例研究表明,该方法能够有效地验证系统安全解决方案的正确性。     

Model checking of healthcare domain models

This paper shows the application of a type of formal software verification technique known as lightweight model checking to a domain model in healthcare informatics in general and public health surveillance systems in particular. One of the most complex use cases of such a system is checked using assertions to verify one important system property. This use case is one of the major justifications for the complexity of the domain model. Alloy Analyzer verification tool is utilized for this purpose. Such verification work is very effective in either uncovering design flaws or in providing guarantees on certain desirable system properties in the earlier phases of the development lifecycle of any critical project.     

基于模型检测的OpenFlow多交换机数据包转发协议的分析与验证

OpenFlow协议是SDN网络中控制平面与数据转发平面之间进行交互的规范与标准,其正确性将直接影响到整个网络功能的实现。通过模型检测技术实现一种验证OpenFlow协议正确性的形式化方法。首先提取OpenFlow协议的核心子协议,即OpenFlow多交换机数据包转发协议作为验证的实例;然后运用协议行为自动机对该子协议进行形式化建模,并且通过时态逻辑描述协议需要进行验证的性质;最后给出算法验证协议模型是否满足给定的性质要求,以此检测OpenFlow协议是否存在正确性漏洞,以便对其进行修正。