Reconfigurable predictive control for redundantly actuated systems with parameterised input constraints

A method is proposed for on-line reconfiguration of the terminal constraint used to provide theoretical nominal stability guarantees in linear model predictive control (MPC). By parameterising the terminal constraint, its complete reconstruction is avoided when input constraints are modified to accommodate faults. To enlarge the region of feasibility of the terminal control law for a certain class of input faults with redundantly actuated plants, the linear terminal controller is defined in terms of virtual commands. A suitable terminal cost weighting for the reconfigurable MPC is obtained by means of an upper bound on the cost for all feasible realisations of the virtual commands from the terminal controller. Conditions are proposed that guarantee feasibility recovery for a defined subset of faults. The proposed method is demonstrated by means of a numerical example.     

A model checker for linear time temporal logic

This report describes the design and implementation of a model checker for linear time temporal logic. The model checker uses a depth-first search algorithm that attempts to find a minimal satisfying model and uses as little space as possible during the checking procedure. The depth-first nature of the algorithm enables the model checker to be used where space is at a premium.This work was supported both by Alvey under grant PRJ/SE/054 (SERC grant GR/D/57942) and by ESPRIT under Basic Research Action 3096 (SPEC).     

Using probabilistic model checking for dynamic power management

Dynamic power management (DPM) refers to the use of runtime strategies in order to achieve a tradeoff between the performance and power consumption of a system and its components. We present an approach to analysing stochastic DPM strategies using probabilistic model checking as the formal framework. This is a novel application of probabilistic model checking to the area of system design. This approach allows us to obtain performance measures of strategies by automated analytical means without expensive simulations. Moreover, one can formally establish various probabilistically quantified properties pertaining to buffer sizes, delays, energy usage etc., for each derived strategy.Received November 2003Revised September 2004Accepted December 2004 by M. Leuschel and D. J. Cooke     

程序模型检查器综述

模型检查实际程序设计语言编写的程序是近年来程序验证领域的研究热点之一,出现了一批针对C,C++或Java语言的程序模型检查器原型.总结了程序模型检查中的主要问题及相关技术,以是否使用中间建模语言为标准,对现有程序模型检查器进行了分类,并具体地介绍了一些代表性工具中的模型获取及化简技术,最后展望了程序模型检查器未来的研究方向.     

Case study on distributed and fault tolerant system modeling based on timed automata

This article presents the modeling of a distributed fault-tolerant real-time application by timed automata. The application under consideration consists of several processors communicating via a Controller Area Network (CAN); each processor executes an application that consists of fault-tolerant tasks running on top of an operating system (e.g. OSEK/VDX compliant) and using inter-task synchronization primitives. For such a system, a model checking tool (e.g. UPPAAL) can be used to verify the complex time and logical properties formalized as safety or bounded liveness properties (e.g. end-to-end response time considering an occurrence of a fault). The proposed model reduces the size of the state-space by sharing clocks measuring the execution time of the tasks.     

A classification and comparison of model checking software architecture techniques

Software architecture specifications are used for many different purposes, such as documenting architectural decisions, predicting architectural qualities before the system is implemented, and guiding the design and coding process. In these contexts, assessing the architectural model as early as possible becomes a relevant challenge. Various analysis techniques have been proposed for testing, model checking, and evaluating performance based on architectural models. Among them, model checking is an exhaustive and automatic verification technique, used to verify whether an architectural specification conforms to expected properties. While model checking is being extensively applied to software architectures, little work has been done to comprehensively enumerate and classify these different techniques.The goal of this paper is to investigate the state-of-the-art in model checking software architectures. For this purpose, we first define the main activities in a model checking software architecture process. Then, we define a classification and comparison framework and compare model checking software architecture techniques according to it.     

A nonlinear model predictive control system based on Wiener piecewise linear models

In this paper a nonlinear model predictive control (NMPC) based on a Wiener model with a piecewise linear gain is presented. This approach retains all the interested properties of the classical linear model predictive control (MPC) and keeps computations easy to solve due to the canonical structure of the nonlinear gain. Some guidelines for the identification of the nominal model as well as the uncertainty bounds are discussed, and two examples that show the possibility of application of this control scheme to real life problems are presented.     

Extending model checkers for hybrid system verification: the case study of SPIN

A hybrid system is a system that evolves following a continuous dynamic, which may instantaneously change when certain internal or external events occur. Because of this combination of discrete and continuous dynamics, the behaviour of a hybrid system is, in general, difficult to model and analyse. Model checking techniques have been proven to be an excellent approach to analyse critical properties of complex systems. This paper presents a new methodology to extend explicit model checkers for hybrid systems analysis. The explicit model checker is integrated, in a non‐intrusive way, with some external structures and existing abstraction libraries, which store and manipulate the abstraction of the continuous behaviour irrespective of the underlying model checker. The methodology is applied to SPIN using Parma Polyhedra Library. In addition, the authors are currently working on the extension of other model checkers. Copyright © 2013 John Wiley & Sons, Ltd.     

Word level bitwidth reduction for unbounded hardware model checking

In this paper we present a word-level model checking method that attempts to speed up safety property checking of industrial netlists. Our aim is to construct an algorithm that allows us to check both bounded and unbounded properties using standard bit-level model checking methods as back-end decision procedures, while incurring minimum runtime penalties for designs that are unsuited to our analysis. We do this by combining modifications of several previously known techniques into a static abstraction algorithm which is guaranteed to produce bit-level netlists that are as small or smaller than the original bitblasted designs. We evaluate our algorithm on several challenging hardware components.     

Formalising and analysing the control software of the Compact Muon Solenoid Experiment at the Large Hadron Collider

The control software of the CERN Compact Muon Solenoid experiment contains over 27 500 finite state machines. These state machines are organised hierarchically: commands are sent down the hierarchy and state changes are sent upwards. The sheer size of the system makes it virtually impossible to fully understand the details of its behaviour at the macro level. This is fuelled by unclarities that already exist at the micro level. We have solved the latter problem by formally describing the finite state machines in the mCRL2 process algebra. The translation has been implemented using the ASF+SDF meta-environment, and its correctness was assessed by means of simulations and visualisations of individual finite state machines and through formal verification of subsystems of the control software. Based on the formalised semantics of the finite state machines, we have developed dedicated tooling for checking properties that can be verified on finite state machines in isolation.     

A stabilizing model predictive control for networked control system with data packet dropout

A constrained model predictive control （MPC） algorithm for networked control system with data packet dropout is proposed in this paper. A buffer is designed to store the predicted control sequence between controller and actuator. It is shown that if the control horizon of MPC is not less than the number of data packets lost continuously, feasibility of MPC at initial time implies asymptotical stability of the closed-loop system. A simulation example illustrates the effectiveness of the proposed approach.     

基于模型检测的并发程序分析综述

程序分析可以被看作抽象解释的模型检测,这使得程序分析的系统化方法成为可能。并发程序日益重要,在多核平台和分布式系统有着广泛的应用。而并发程序分析仍然有巨大的困难,实践上的复杂性和理论上的不可判定性都使得程序分析难以简单进行。文献[19]指出即使只有两个递归线程的交互,断言检测也是不可判定的。为了克服这类障碍,一些并发程序的静态分析方法被提了出来。对基于模型检测的并发程序分析给出一个详尽的综述,包括使用的数学模型、已有工具、可判定以及不可判定结果。     

Stochastic model predictive control for remanufacturing system management

Uncertainties in the quality, quantity, and operational time of used products pose a challenge to the management of remanufacturing systems. In addition, it becomes a necessity to optimize the operation of the remanufacturing system to balance the quality of products, remanufacturing efficiency, and service level. In this study, a stochastic discrete-time dynamical model is proposed to represent a remanufacturing system, where the relationship between the market satisfaction, inventory status, and operational actions is explicitly modeled. This includes production and inventory planning, resource allocation and acquisition. To handle uncertainties, a stochastic model predictive control approach is proposed to plan the actions that optimize the remanufacturing efficiency. Our results in the simulation examples show that: (a) without supplies, the remanufacturing system has better stability and robustness than a conventional manufacturing system with the same initial stocks; and (b) with insufficient initial stocks, the remanufacturing system demands fewer and more gradual supplies, thereby keeping the system stable. Finally, a sensitivity analysis is conducted for testing the performance of the remanufacturing system. By changing the operational action capacity, different state equilibria are discovered, which correspond to distinct system response characteristics. The study reveals notable managerial insights and effects of product commonality, demand patterns, and operational actions scheduling on the efficiency of the remanufacturing system.     

A multiple model approach for predictive control of nonlinear hybrid systems

This paper presents modeling and control of nonlinear hybrid systems using multiple linearized models. Each linearized model is a local representation of all locations of the hybrid system. These models are then combined using Bayes theorem to describe the nonlinear hybrid system. The multiple models, which consist of continuous as well as discrete variables, are used for synthesis of a model predictive control (MPC) law. The discrete-time equivalent of the model predicts the hybrid system behavior over the prediction horizon. The MPC formulation takes on a similar form as that used for control of a continuous variable system. Although implementation of the control law requires solution of an online mixed integer nonlinear program, the optimization problem has a fixed structure with certain computational advantages. We demonstrate performance and computational efficiency of the modeling and control scheme using simulations on a benchmark three-spherical tank system and a hydraulic process plant.     

基于模型检测的工作流访问控制策略验证*

访问控制策略的有效性对工作流管理系统的安全稳定运行具有重要影响,针对这一问题,提出了一种基于模型检测的工作流管理系统访问控制策略验证方法。建立了工作流管理系统的访问控制策略模型与工作流执行主体任务权限状态模型,并在此基础上对访问控制策略的有效性进行验证。实验表明该算法具有有效性和合理性,为访问控制策略的验证提供了一条新的解决途径。     

OFMC: A symbolic model checker for security protocols

We present the on-the-fly model checker OFMC, a tool that combines two ideas for analyzing security protocols based on lazy, demand-driven search. The first is the use of lazy data types as a simple way of building efficient on-the-fly model checkers for protocols with very large, or even infinite, state spaces. The second is the integration of symbolic techniques and optimizations for modeling a lazy Dolev–Yao intruder whose actions are generated in a demand-driven way. We present both techniques, along with optimizations and proofs of correctness and completeness.Our tool is state of the art in terms of both coverage and performance. For example, it finds all known attacks and discovers a new one in a test suite of 38 protocols from the Clark/Jacob library in a few seconds of CPU time for the entire suite. We also give examples demonstrating how our tool scales to, and finds errors in, large industrial-strength protocols.     

Boolean and Cartesian abstraction for model checking C programs

We show how to attack the problem of model checking a C program with recursive procedures using an abstraction that we formally define as the composition of the Boolean and the Cartesian abstractions. It is implemented through a source-to-source transformation into a Boolean C program; we give an algorithm to compute the transformation with a cost that is exponential in its theoretical worst-case complexity but feasible in practice.     

Efficient SAT-based bounded model checking for software verification

This paper discusses our methodology for formal analysis and automatic verification of software programs. It is applicable to a large subset of the C programming language that includes pointer arithmetic and bounded recursion. We consider reachability properties, in particular whether certain assertions or basic blocks are reachable in the source code, or whether certain standard property violations can occur. We perform this analysis via a translation to a Boolean circuit representation based on modeling basic blocks. The program is then analyzed by a back-end SAT-based bounded model checker, where each unrolling is mapped to one step in a block-wise execution of the program.