软件安全核的可信性问题

软件的大量应用,使控制系统面,临严峻的安全考验,陷入了安全危机中,迫切需要新的安全保障技术。安全核就是应运而生的一种安全保障新概念,其可信性直接关系到安全核的有效性和系统的安危。面对安全核可信性问题,测试和限制安全核尺寸是当前采用的方法,它们极大地制约了安全核技术在复杂系统中的应用。本文分析了安全核可信性的本质;结合安全关键系统的基本构架,提出了从安全需求分析开始到安全核生成过程中,如何通过形式化的方法采提高安全核可信性的方法,为安全核技术在复杂系统中的应用提供了一种新思路;以交通灯控制为例全过程地实现和验证了所提出思想的正确性和可行性。     

Formal change impact analyses for emulated control software

Processor emulators are a software tool for allowing legacy computer programs to be executed on a modern processor. In the past emulators have been used in trivial applications such as maintenance of video games. Now, however, processor emulation is being applied to safety-critical control systems, including military avionics. These applications demand utmost guarantees of correctness, but no verification techniques exist for proving that an emulated system preserves the original system’s functional and timing properties. Here we show how this can be done by combining concepts previously used for reasoning about real-time program compilation, coupled with an understanding of the new and old software architectures. In particular, we show how both the old and new systems can be given a common semantics, thus allowing their behaviours to be compared directly.     

一个基于COP的控制软件安全性增强方法

控制软件往往是安全攸关系统的核心,其正确性对系统安全起着至关重要的作用。然而由于系统面对的环境因素越来越复杂,软件设计之初不可能考虑到所有可能面对的环境变化因素,系统的安全性面临新的挑战。因此在软件维护阶段,以环境变化为中心,增量式地增强软件的安全性显得非常重要。面向上下文编程方法(Context-Oriented Programming,COP)正是一种以软件运行上下文环境为中心的编程方法。现有的支撑COP思想的运行机制可以使得系统根据精确的上下文信息动态地调整系统的行为,但是有些上下文引发的系统行为调整会导致系统执行器的现有运行被打断,对于这类影响系统执行器行为的上下文,现有的COP运行机制还没有提供有效处理方法。根据现有的COP方法,给出了一个基于软件上下文保存与恢复的控制软件安全性增强的编程模型,并在LegoNXT控制器上实现了相应的运行支撑和编程工具,通过一个产品分拣系统的安全性增强实例,初步验证了该编程模型的合理性。     

A formal method for building concurrent real-time software

Developing concurrent real-time programs is one of computer science's greatest challenges. Not only is such software expensive to manufacture, but its role in safety-critical systems demands that it be correct. Formal methods of program specification and refinement could strengthen the mathematical precision used to develop such software. Nevertheless, formalisms that embrace both real-time and concurrency requirements are only just emerging. The Quartz method treats time and functional behavior with equal importance in the development process. The authors argue that by modeling program development in a unified framework, we can increase our confidence in the correctness of real-time concurrent code     

设备驱动程序可靠性和正确性保障方法与技术研究进展

随着计算机技术的不断发展,计算机系统在安全攸关领域得到了广泛应用,其中的软件系统正逐渐成为重要的使能部件.在计算机系统中,设备驱动程序扮演了软件与硬件设备之间桥梁的角色.由于与计算机平台、操作系统、设备3个方面同时关联所导致的复杂性,设备驱动程序的开发难度大、成本高,程序中所存在的错误和缺陷常常导致系统失效,在安全攸关领域造成不可挽回的损失.以设备驱动程序可靠性和正确性保障为目标,分别从故障的隔离与恢复、正确性分析和验证、设计建模与复杂性控制这3个方面对当前相关方法和技术进行分析,为开展进一步深入的研究工作打下基础.     

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

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

Experimental evaluation of software development tools for safety-critical real-time systems

Since the early years of computing, programmers, systems analysts, and software engineers have sought ways to improve development process efficiency. Software development tools are programs that help developers create other programs and automate mundane operations while bringing the level of abstraction closer to the application engineer. In practice, software development tools have been in wide use among safety-critical system developers. Typical application areas include space, aviation, automotive, nuclear, railroad, medical, and military. While their use is widespread in safety-critical systems, the tools do not always assure the safe behavior of their respective products. This study examines the assumptions, practices, and criteria for assessing software development tools for building safety-critical real-time systems. Experiments were designed for an avionics testbed and conducted on six industry-strength tools to assess their functionality, usability, efficiency, and traceability. The results some light on possible improvements in the tool evaluation process that can lead to potential tool qualification for safety-critical real-time systems.     

支持抽象解释的静态分析方法的形式化体系研究

在安全关键领域中,如何保证软件的安全性已经成为了一个广受关注的重要课题。静态程序分析是一类十分有效的程序自动化验证方法。基于抽象解释的静态分析技术在验证软件的非功能性安全属性上表现十分突出。可配置程序分析(Configurable Program Analysis,CPA)是一种通用静态分析方法形式化体系,旨在用一种形式化体系对静态分析的分析阶段进行建模。使用CPA对基于抽象解释的静态分析进行建模,给出如何使用CPA形式化体系描述基于抽象解释的静态分析,给出了从待分析程序到CPA形式化体系的转换规则;提供了一种在安全关键性领域中的软件正确性自动验证方法,为基于抽象解释的静态分析工具的实现提供了一种可行方案。     

可编程保护测控功能通用性设计与实现

介绍了保护测控装置中可编程保护测控功能的概念、应用场景及实现要求,提出适用于不同软硬件平台的可编程功能通用化设计方案.在分析可编程功能与保护测控装置标准或通用功能之间的数据接口及其描述方法的基础上阐述了编程语言的设计以及用户程序转换为中间代码和目标代码的实现方法,讨论了装置虚拟机通过构造逻辑堆栈高效地执行用户程序的过程,并提出了配套图形化编程工具软件的实现思路.该方案为保护测控装置提供了灵活的通用化二次可编程接口.     

Software testing with code-based test generators: data and lessons learned from a case study with an industrial software component

Automatically generating effective test suites promises a significant impact on testing practice by promoting extensively tested software within reasonable effort and cost bounds. Code-based test generators rely on the source code of the software under test to identify test objectives and to steer the test case generation process accordingly. Currently, the most mature proposals on this topic come from the research on random testing, dynamic symbolic execution, and search-based testing. This paper studies the effectiveness of a set of state-of-the-research test generators on a family of industrial programs with nontrivial domain-specific peculiarities. These programs are part of a software component of a real-time and safety-critical control system and integrate in a control task specified in LabVIEW, a graphical language for designing embedded systems. The result of this study enhances the available body of knowledge on the strengths and weaknesses of test generators. The empirical data indicate that the test generators can truly expose subtle (previously unknown) bugs in the subject software and that there can be merit in using different types of test generation approaches in a complementary, even synergic fashion. Furthermore, our experiment pinpoints the support for floating point arithmetics and nonlinear computations as a major milestone in the path to exploiting the full potential of the prototypes based on symbolic execution in industry.     

Software Reliability—Status and Perspectives

It is essential to assess the reliability of digital computer systems used for critical real-time control applications (e.g., nuclear power plant safety control systems). This involves the assessment of the design correctness of the combined hardware/software system as well as the reliability of the hardware. In this paper we survey methods of determining the design correctness of systems as applied to computer programs.     

Stochastic software safety/reliability measurement and its application

Safety and reliability have become important software quality characteristics in the development of safety-critical software systems. However, there are so far no quantitative methods for assessing a safety-critical software system in terms of the safety/reliability characteristics. The metrics of software safety is defined as the probability that conditions that can lead to hazards do not occur. In this paper, we propose two stochastic models for software safety/reliability assessment: the data-domain dependent safety assessment model and the availability-related safety assessment model. These models focus on describing the time- or execution-dependent behavior of the software faults which can lead to unsafe states when they cause software failures. The application of one of these models to optimal software release problems is also discussed. Finally, numerical examples are illustrated for quantitative software safety assessment and optimal software release policies. This revised version was published online in June 2006 with corrections to the Cover Date.     

Automated test generation using model checking: an industrial evaluation

In software development, testers often focus on functional testing to validate implemented programs against their specifications. In safety-critical software development, testers are also required to show that tests exercise, or cover, the structure and logic of the implementation. To achieve different types of logic coverage, various program artifacts such as decisions and conditions are required to be exercised during testing. Use of model checking for structural test generation has been proposed by several researchers. The limited application to models used in practice and the state space explosion can, however, impact model checking and hence the process of deriving tests for logic coverage. Thus, there is a need to validate these approaches against relevant industrial systems such that more knowledge is built on how to efficiently use them in practice. In this paper, we present a tool-supported approach to handle software written in the Function Block Diagram language such that logic coverage criteria can be formalized and used by a model checker to automatically generate tests. To this end, we conducted a study based on industrial use-case scenarios from Bombardier Transportation AB, showing how our toolbox CompleteTest can be applied to generate tests in software systems used in the safety-critical domain. To evaluate the approach, we applied the toolbox to 157 programs and found that it is efficient in terms of time required to generate tests that satisfy logic coverage and scales well for most of the programs.     

基于着色时间Petri网的实时系统的形式验证

嵌入式实时系统多数应用在安全性要求较高的场合,因此需要保证系统的正确性.复杂性不断增加的实时系统迫切需要在系统开发早期引入形式化分析技术来验证系统的期望性质.时间Petri网是有严格数学基础的图形表达工具,适合对实时系统建模;时间自动机(Timed Automata,TA)有成熟的验证工具,被广泛用于实时系统的模型检验和验证.本文提出一种基于着色时间Petri网(Colored Time Petri Net,CTPN)的实时系统的验证方法,用CTPN对带有控制流和数据流的实时系统建模,通过转换规则将CTPN模型转换成语义等价的TA模型,利用模型检验工具UPPAAL验证系统的性质.最后,用实例证明此方法有效.     

安全关键软件术语推荐和需求分类方法

安全关键软件需求中的相关知识大多需要手工提取,既费时又费力。近年来,人工智能技术逐渐被应用于安全关键软件设计与开发过程中,以减少工程师的手工劳动,缩短软件开发的生命周期。文中提出了一种安全关键软件术语推荐和需求分类方法,为安全关键软件需求规约提供了基础。首先,基于词性规则和依存句法规则对候选术语进行提取,通过术语相似度计算和聚类方法对候选术语进行聚类,将聚类结果推荐给工程师;其次,基于特征提取方法和分类方法将安全关键软件需求自动分为功能、安全性、可靠性等需求;最后,在AADL(Architecture Analysis and Design Language)开源建模环境OSATE中实现了原型工具TRRC4SCSTool,并基于工业界案例需求、安全分析与认证标准等构建实验数据集进行了实验验证,证明了所提方法的有效性。     

A data flow-based structural testing technique for FBD programs

With increased use of programmable logic controllers (PLCs) in implementing critical systems, quality assurance became an important issue. Regulation requires structural testing be performed for safety-critical systems by identifying coverage criteria to be satisfied and accomplishment measured. Classical coverage criteria, based on control flow graphs, are inadequate when applied to a data flow language function block diagram (FBD) which is a PLC programming language widely used in industry. We propose three structural coverage criteria for FBD programs, analyze relationship among them, and demonstrate their effectiveness using a real-world reactor protection system. Using test cases that had been manually prepared by FBD testing professionals, our technique found many aspects of the FBD logic that were not tested sufficiently. Domain experts, having found the approach highly intuitive, found the technique effective.     

软件功能安全验证活动的应用

软件功能安全验证活动对提高安全关键系统的安全性具有重要作用,它贯穿于软件安全生命周期的各个阶段.通过对各阶段输出文档的审查和分析,可尽早发现软件问题,降低软件修复成本.完整的问题闭环处理流程可有效解决软件验证活动中发现的问题,给出各方均满意的处理结果.     

Do you trust your compiler?

As our society becomes more technologically complex, computer systems are finding an alarming number of uses in safety-critical applications. In many such systems, the software component's reliability is essential to the system's safe operation, so it becomes natural to ask, “How can software be made to behave correctly when executed?” Using program transformations to produce trusted software simplifies verification. Program transformations use proven laws to manipulate programs in a manner analogous to algebraic transformations. The authors sketch how a formal method based on program transformations can be used to construct a verified compiler. Such a compiler has been proved to correctly compile any correct program into assembly language. While the compiler itself may not execute efficiently-after all, you need only use the verified compiler the last time you compile a program-the transformational approach should enable the verified compiler to produce efficient assembly code     

A high-level Petri net for goal-directed semantics of Horn clauselogic

A new high level Petri net (HLPN) model is introduced as a graphical syntax for Horn clause logic (HCL) programs. We call these nets: Horn clause logic goal directed nets (HCLGNs). It is shown that there is a bijection between the queried definite programs and the class of HCLGNs. In addition, a visualization of SLD resolution is realized through the enabling and firing rules and net markings. The correctness of these rules with respect to SLD resolution is also proven. We model SLD refutations and failing computations. It is shown how HCLGNs can be used to model built in atoms and provide a new AND/OR parallel execution model. Recently, several software packages (graphical editors) have become available for editing and executing HLPNs. The simulation capabilities of the HLPN software offer opportunities to perform automated, interactive code walk throughs and also have potential for providing a framework for visual debugging environments. However, HCLGNs differ from the major classes of HLPNs for which software tools have been developed in primarily two ways: the tokens in the markings can have variables; and the firing of a transition may not only update the marking of the adjacent places, but may instantiate variables in tokens in the markings of places that are non adjacent to the fired transition. Thus, the existing packages can only provide graphical syntax editing and are not appropriate for graphical simulation of HCLGNs. We provide an algebraic characterization of HCLGNs that can serve as a design guideline for implementing HCLGNs