运行时验证中的减少监控开销方法研究

运行时验证中的一个重要研究内容就是减少监控开销,以达到运行时开销对系统影响最小化的目标。总结了近年来运行时验证中减少监控开销技术的研究发展,首先介绍了运行时开销控制的研究现状;然后详细介绍了运行时开销减少的具体方法;最后分析了运行时开销控制技术面临的主要挑战,并对该领域未来的研究方向进行了展望。     

多核处理器架构下面向监控的软件运行时验证方法研究

面向监控的软件运行时验证(Monitor-oriented Runtime Verification:MRV)方法可以有效的提高系统可靠性,但是在传统基于单核处理器架构的嵌入式系统中采用MRV方法会给目标系统性能造成较大的影响.本文对基于多核处理器架构的MRV方法进行了初步研究,分析并设计了在线验证、离线验证以及单监视器设计与多监视器设计等多种模式的MRV方法,给出了相应的MRV实现方案,并在几个开源项目中进行了MRV实例应用.实验数据分析表明,在不同模式下,基于多核处理器架构的MRV方法能够从不同程度上有效提高系统运行时验证的性能.本文工作为进一步设计有效的多核架构下MRV方法提供了基础.     

运行时验证及其应用

计算机软件在日常生活、工业、军事、国家安全领域已占有重要地位,软件的正确性、可靠性、安全性、可用性和可维护性已经受到广泛关注和深入研究。传统的验证技术包括定理证明、模型检测、以及测试,这些方法受到程序的运行以及程序所在环境的不可控等因素的限制。运行时验证的验证过程基于被监控系统的实际运行过程进行,从而有效地避免这些限制,是传统验证技术的有效补充。     

PSL逻辑及验证技术研究进展与展望*

在简要介绍PSL的分层结构和语法与语义基础上,综述了PSL验证技术的应用研究现状,分析了各种方法、技术的优缺点,最后指出了PSL验证技术的未来研究展望。     

面向安全属性的机器人运行时验证

为了保证机器人操作系统(Robot operating system,ROS)的安全性,提出一个运行时验证框架ROS-Monitor来监控系统。将所有的监控信息分为节点消息和节点行为,并实现从用户自定义场景模型自动生成相应监控器的工具。实验证明了该方法的有效性。     

一种分布式软件运行时监控机制

软件在信息社会生活中起着越来越重要的作用,而如何提高软件系统的可信性也成为研究的重要课题,而运行时监控技术是提升软件可信性的重要方法之一.针对当前软件网络化、分布化的发展趋势,提出了一种全新的分布式软件运行时监控机制,通过建立监控服务使得远程监控客户端能够实现对软件系统跨网络、跨平台、实时的监控,从而进一步增强原有软件系统的可信性.这种机制在实际软件系统中获得了有效的应用,具有可行性和合理性.     

基于部件设计的运行时验证

研究软部件设计中的可靠性问题,对这一问题主要诉是,当一个已存软部件的正确性无法得到确认时,在具具体实现不可知的情况下,如何提高它的运行时可靠性？为解决这一问题,该文首先构造一个能够用于软部件动态语义检测的抽象模型;然后通过在设计中系统地引入一些运行时技术以保证基于部件软件的可靠性。这些运行时技术包括：（１）包裹部件。作为额外的一层设计,根据软部件的接口说明自动生成,用于检测运行时错误;（２）虚拟部     

一种基于MaC的运行时验证框架的研究

介绍一种基于Monitoring and Checking（MaC）的运行时验证框架。受预测语义概念及一种比较成熟的运行时验证工具MaC的启发,通过研究MaC的工作原理和框架,结合预测语言的定义,提出一种运行时验证框架。该工作的意义在于,一方面继承了MaC的逻辑表达能力,在事件、条件的定义上简洁方便;另一方面通过带预测语义的验证器的引入,扩展了MaC的逻辑表达能力,并使得该运行时验证框架带有一定的预测性,为进一步研究基于预测语义的在线主动监控打下良好的基础。     

基于AOP 的运行时验证中的冲突检测

现有的形式化验证方法除了在模型层面对系统进行验证以外,越来越倾向于直接针对系统的实际代码和具体运行.运行时验证技术验证的对象是具体程序,它试图把形式化验证技术部署到程序的实际运行过程中.然而在把形式化技术部署到实际运行过程中会出现一系列在模型层面验证通常不会出现的问题,对这些问题中的冲突现象进行了研究,定义了运行时验证技术中存在的两种冲突,并给出了相应的检测算法.最后,对这些算法进行了实现和实例研究,结果表明了该方法的有用性.     

A framework for computer-aided validation

This paper presents a framework for augmenting independent validation and verification (IV&V) of software systems with computer-based IV&V techniques. The framework allows an IV&V team to capture its own understanding of the application as well as the expected behavior of any proposed system for solving the underlying problem by using an executable system reference model, which uses formal assertions to specify mission- and safety-critical behaviors. The framework uses execution-based model checking to validate the correctness of the assertions and to verify the correctness and adequacy of the system under test.     

Model-based Runtime Verification Framework for Self-optimizing Systems

This paper describes a novel on-line model checking approach offered as service of a real-time operating system (RTOS). The verification system is intended especially for self-optimizing component-based real-time systems where self-optimization is performed by dynamically exchanging components. The verification is performed at the level of (RT-UML) models. The properties to be checked are expressed by RT-OCL terms where the underlying temporal logic is restricted to either time-annotated ACTL or LTL formulae. The on-line model checking runs interleaved with the execution of the component to be checked in a pipelined manner. The technique applied is based on on-the-fly model checking. More specifically for ACTL formulae this means on-the-fly solution of the NHORNSAT problem while in the case of LTL the emptiness checking method is applied.     

Rewriting-Based Techniques for Runtime Verification

Techniques for efficiently evaluating future time Linear Temporal Logic (abbreviated LTL) formulae on finite execution traces are presented. While the standard models of LTL are infinite traces, finite traces appear naturally when testing and/or monitoring real applications that only run for limited time periods. A finite trace variant of LTL is formally defined, together with an immediate executable semantics which turns out to be quite inefficient if used directly, via rewriting, as a monitoring procedure. Then three algorithms are investigated. First, a simple synthesis algorithm for monitors based on dynamic programming is presented; despite the efficiency of the generated monitors, they unfortunately need to analyze the trace backwards, thus making them unusable in most practical situations. To circumvent this problem, two rewriting-based practical algorithms are further investigated, one using rewriting directly as a means for online monitoring, and the other using rewriting to generate automata-like monitors, called binary transition tree finite state machines (and abbreviated BTT-FSMs). Both rewriting algorithms are implemented in Maude, an executable specification language based on a very efficient implementation of term rewriting. The first rewriting algorithm essentially consists of a set of equations establishing an executable semantics of LTL, using a simple formula transforming approach. This algorithm is further improved to build automata on-the-fly via caching and reuse of rewrites (called memoization), resulting in a very efficient and small Maude program that can be used to monitor program executions. The second rewriting algorithm builds on the first one and synthesizes provably minimal BTT-FSMs from LTL formulae, which can then be used to analyze execution traces online without the need for a rewriting system. The presented work is part of an ambitious runtime verification and monitoring project at NASA Ames, called PathExplorer, and demonstrates that rewriting can be a tractable and attractive means for experimenting and implementing logics for program monitoring.Supported in part by joint NSF/NASA grant CCR-0234524.     

Embedded Software Verification Using Symbolic Execution and Uninterpreted Functions

Symbolic simulation and uninterpreted functions have long been staple techniques for formal hardware verification. In recent years, we have adapted these techniques for the automatic, formal verification of low-level embedded software—specifically, checking the equivalence of different versions of assembly language programs. Our approach, though limited in scalability, has proven particularly promising for the intricate code optimizations and complex architectures typical of high-performance embedded software, such as for DSPs and VLIW processors. Indeed, one of our key findings was how easy it was to create or retarget our verification tools to different, even very complex, machines. The resulting tools automatically verified or found previously unknown bugs in several small sequences of industrial and published example code. This paper provides an introduction to these techniques and a review of our results.     

Runtime Verification of Timed LTL using Disjunctive Normalized Equation Systems

In this paper we present a new framework for runtime verification of properties of real time systems such as financial systems or backend databases. Such a systems has a semantics which resemples that of timed traces, namely a sequence of states where each state consists of predicates true in this state and then a timestamp explaining when the state is valid. We present a logic, LTL_t, which is an extension of LTL with time constraints and a freeze quantifier and show how formulae in this logic are able to express properties of bounded liveness and safety which are ideal for these systems. It is shown how a formula in LTL_t may be rewritten to a certain disjunctive normal form suitable for checking a real time system at runtime. The normal form captures the essential part of runtime verification by a set of mutually defined formula identifiers, each expressing two things: What should hold now and which formula identifiers that will need to hold in the next state. As part of the theoretical foundation for this work we propose a characterization of Runtime Verification and address the challenges in developing a method which is both sound and complete while at the same time efficient.     

UML Automatic Verification Tool with Formal Methods

The use of the UML specification language is very widespread due to some of its features. However, the ever more complex systems of today require modeling methods that allow errors to be detected in the initial phases of development. The use of formal methods make such error detection possible but the learning cost is high.This paper presents a tool which avoids this learning cost, enabling the active behavior of a system expressed in UML to be verified in a completely automatic way by means of formal method techniques. It incorporates an assistant for the verification that acts as a user guide for writing properties so that she/he needs no knowledge of either temporal logic or the form of the specification obtained.     

Adaptive Verification using Forced Simulation

Simulation (a pre-order) over Kripke structures is a well known formal verification technique. Simulation guarantees that all behaviours of an abstracted structure (a property or function, F) are contained in a larger structure (a model M). A model, however, may not always simulate a property due to the presence of design errors. In this case, the model is debugged manually. In this paper, we propose a weaker simulation over structures called forced simulation for automated debugging. Forced simulation is applied when normal simulation fails. Forced simulation between a model (M) and a function (F) guarantees the existence of a modifier, D, to adapt M so that the composition of M and D is observationally equivalent to F. Observational equivalence over structures called weak bisimulation is developed in this paper. It is also established that when two structures are weakly bisimilar all CTL^* properties holding over one also holds over the other structure. Forced simulation based algorithm has been used to adapt many designs which had failed certain properties during conventional verification.     

Limits of formal methods

Formal methods can help to increase the correctness and trustworthiness of the software developed. However, they do not solve all the problems of software development. This paper analyses some limitations of formal methods.