Recent advances on formal methods for safety and security of cyber-physical systems

Cyber-physical systems (CPSs) are engineering systems with both computational and physical components [1]. Typical CPSs include energy systems, transportation systems, autonomous vehicles, etc. CPSs are usually hybrid involving complex interactions of continuous dynamics with discrete logics. The development of controller design and verification algorithms for such complex systems are crucial and challenging tasks. Ever-increasing demands for safety and security of CPSs put stringent constraints on their analysis and design, and necessitate the use of formal model-based approaches. In recent years, we have witnessed a substantial increase in the use of formal techniques for the verification and design of safety–critical and security-sensitive CPSs [2]. Due to the complex functionalities of safety–critical CPSs, ensuring safety is extremely challenging. In particular, since CPSs involve both continuous and discrete dynamics, safety not only requires that the low-level physical trajectory is within constrained regions, e.g., the value of the state should never exceed a threshold, but also requires that the high-level behavior of the system satisfies some desired specifications, e.g., executing a set of tasks in a right order. However, existing control theory mainly focuses on simple low-level specifications such as stability. To describe functional safety of the high-level behaviors of CPSs, more rich specification languages, such as regular languages and linear temporal logics (LTL), are needed. Also, security-related attacks are increasingly becoming pervasive in safety–critical cyber-physical systems; such security vulnerabilities related to information leaks in CPSs are extremely difficult to discover and mitigate as the interaction between the embedded control software and the physical environment exposes numerous attack surfaces for malicious exploitation. To enforce complex specifications for safety–critical cyber-physical systems, one of the most popular approaches developed in the past 50 years is the abstraction-based approach, which consists of the following steps: 1) abstract the original infinite continuous system as a finite symbolic system; 2) synthesize a supervisory controller based on the symbolic model to enforce desired specifications; 3) refine the symbolic controller synthesized to control the original system. To construct the symbolic model, a typical approach is to discretize the state-space to induce a finite quotient system. The key here is to establish certain relationship between the original system and its abstraction. In the seminal work of [3], the notion of approximate bi-simulation relation was proposed to capture the equivalence of two models with guaranteed abstraction error; this idea was further extended to the notion of alternating bi-simulation relation for the purpose of control [4]. Recently in [5], a more unified relation called feedback refinement relation was proposed. Compositional approaches have also been developed to compute finite abstractions for large-scale interconnected CPSs [6]....     

Identification of integrating and critically damped systems with time delay

This paper presents identification of second order plus dead time(SOPDT) integrating and critically damped systems based on relay feedback testing. Relay with hysteresis is applied to the unknown system to get the sustained oscillations also called as limit cycle. The limit cycle parameters are utilized in mathematical expressions which are derived using state space technique so that exact process model parameters are estimated. As the relay with hysteresis helps in generating sustained oscillations and also reduces effect of measurement noise which is an important issue in system identification. Different types of processes in the form of transfer function models are considered to show the efficacy of the proposed method and results are compared with available methods in the literature with and without noise effect.     

Decentralized Networked Control System Design Using Takagi-Sugeno (TS) Fuzzy Approach

This paper proposes a new method for control of continuous large-scale systems where the measures and control functions are distributed on calculating members which can be shared with other applications and connected to digital network communications.At first, the nonlinear large-scale system is described by a Takagi-Sugeno(TS) fuzzy model. After that, by using a fuzzy LyapunovKrasovskii functional, sufficient conditions of asymptotic stability of the behavior of the decentralized networked control system(DNCS),are developed in terms of linear matrix inequalities(LMIs). Finally, to illustrate the proposed approach, a numerical example and simulation results are presented.     

Delay-dependent robust stabilization for uncertain singular systems with discrete and distributed delays

This paper investigates the problem of delay-dependent robust stabilization for uncertain singular systems with discrete and distributed delays in terms of linear matrix inequality （LMI） approach. Based on a delay-dependent stability condition for the nominal system, a state feedback controller is designed, which guarantees the resultant closed- loop system to be robustly stable. An explicit expression for the desired controller is also given by solving a set of matrix inequalities. Some numerical examples are provided to illustrate the less conservativeness of the proposed methods.     

Analysis of synchronization in a supermarket refrigeration system

In a supermarket refrigeration, the temperature in a display case, surprisingly, influences the temperature in other display cases. This leads to a synchronous operation of all display cases, in which the expansion valves in the display cases turn on and off at exactly the same time. This behavior increases both the energy consumption and the wear of components. Besides this practical importance, from the theoretical point of view, synchronization, likewise stability, Zeno phenomenon, and chaos, is an interesting dynamical phenomenon. The study of synchronization in the supermarket refrigeration systems is the subject matter of this work. For this purpose, we model it as a hybrid system, for which synchronization corresponds to a periodic trajectory.To examine whether it is stable, we transform the hybrid system to a single dynamical system defined on a torus. Consequently,we apply a Poincar ′e map to determine whether this periodic trajectory is asymptotically stable. To illustrate, this procedure is applied for a refrigeration system with two display-cases.     

An LMI approach to robust H-infinity control for uncertain singular time-delay systems

The problem of robust H-infinity control for a class of uncertain singular time-delay systems is studied in this paper. A new approach is proposed to describe the relationship between slow and fast subsystems of singular time- delay systems, based on which, a sufficient condition is presented for a singular time-delay system to be regular, impulse free and stable with an H-infinity performance. The robust H-infinity control problem is solved and an explicit expression of the desired state-feedback control law is also given. The obtained results are formulated in terms of strict linear matrix inequalities （LMIs） involving no decomposition of system matrices. A numerical example is given to show the effectiveness of the proposed method.     

模式转换未知的一类混杂系统的状态估计

Since the state of hybrid systems is determined by interacting continuous and discrete dynamics, the state estimation of hybrid systems becomes a challenging problem. It is more complicated when the discrete mode transition information is not available, and the modes of hybrid systems are nonlinear stochastic dynamic systems. To address this problem, this paper proposes a novel hybrid strong tracking filter (HSTF) for state estimation of a class of hybrid nonlinear stochastic systems with unknown mode transition, the method for designing HSTF is presented. The HSTF can estimate the continuous state and discrete mode accurately with unknown mode transition information, and the estimation of hybrid states is robust against the initial state. Simulation results illustrate the effectiveness of the proposed approach.     

Robust stability and stabilization of discrete singular systems with interval time-varying delay and linear fractional uncertainty

The robust stability and robust stabilization problems for discrete singular systems with interval time-varying delay and linear fractional uncertainty are discussed. A new delay-dependent criterion is established for the nominal discrete singular delay systems to be regular, causal and stable by employing the linear matrix inequality (LMI) approach. It is shown that the newly proposed criterion can provide less conservative results than some existing ones. Then, with this criterion, the problems of robust stability and robust stabilization for uncertain discrete singular delay systems are solved, and the delay-dependent LMI conditions are obtained. Finally, numerical examples are given to illustrate the e?ectiveness of the proposed approach.     

Editorial: Special issue on multiagent-based system modeling and control practices

Dealing with a large-scaled system as multi-agent system is not a new methodology in system control field. The root of multi-agent system is longer than half century, however, it is recently spotlighted again due to the needs of theoretical tools for dealing with large-scale system such as smart city, global behavior of traffic system, networked systems, and machine learning. Common characteristic of this kind of systems is that the whole system consists of a larger number of autonomous agents which are coupled and connected each other, and the individual agent is under local control but it accomplishes a task as the whole system. This collection of research papers is from the submissions to the special issue with title ``multiagent-based system modeling and control practices''. The aim of the special issue is to provide a stage for both of theorists and practitioners in this field to exchange challenging results in new issues, especially biological, bio-inspired systems, mean-field game, and connected network systems. The collection is divided as three groups: The survey paper by K. Hou et al. presented an overview on recent advances in control and communication of multi-robot swarms. A biomolecular control scheme is proposed in the paper by P. Rong and T. Nakakuki which demonstrated how the dynamic DNA nanotechnology can be used in system control field. The last brief paper of this group is from S. Azuma which discussed the network structure for Boolean network systems. The second group includes three case studies from the view of creating new theoretical tools. The paper by T. Wang et al. proposed an online iterative algorithm for solving multi-agent dynamic graphical games which showd the possibility of online solution of Bellman equation. Y. Du et al. presented in their paper a distributed scheme for ensemble learning under a diffusion strategy which aimed to the classification problem on big data. The paper by Z. Lu et al. addressed a mixed-triggered finite-time non-fragile filtering problem for interval type-2 T-S fuzzy network control systems. The last group of this collection includes three papers with practical background. The paper by J. Zhang and F. Xu investigated the problem of minimizing energy consumption for connected hybrid electric vehicles, and the paper from Q. Fu et al. presented a challenge of applying mean-field game theory to achieve speed consensus for the vehicle driving in a large-scale traffic flow. Targeted on the alternative transportation devices, high-speed train with connected real-time traffic information is addressed in the paper by D. He et al. with energy-efficient receding horizon trajectory planning method.     

Decentralized H-infinity state feedback control for discrete-time singular large-scale systems

The decentralized H-infinity control problem for discrete-time singular large-scale systems is considered. Based on the bounded real lemma of discrete-time singular systems, a sufficient condition for the existence of decentralized H-infinity controller for discrete-time singular large-scale systems is presented in terms of the solvability to a certain system of linear matrix inequalities by linear matrix inequality (LMI) approach, and the feasible solutions to the system of LMIs provide a parameterized representation of a set of decentralized H-infinity controller. The given example shows the application of the method.     

离散广义大系统的Lyapunov稳定性分析

广义大系统的稳定性是广义大系统理论的基本问题之一,对其稳定性的研究要比状态空间大系统复杂得多,因为广义大系统不仅需要考虑稳定性,而且还要考虑正则性和因果性(离散广义系统)及脉冲自由(连续广义系统).本文在所有孤立子系统都是正则的且具有因果关系的条件下,利用Lyapunov方程,应用Lyapunov函数方法,研究了广义离散线性大系统和广义离散非线性大系统的稳定性和不稳定性问题,给出了离散广义大系统稳定性和不稳定性判定定理,得到了离散广义大系统的关联稳定参数域和不稳定域.     

FluNet: A hybrid internet simulator for fast queue regimes

Motivated by the scale and complexity of simulating large-scale networks, recent research has focused on hybrid fluid/packet simulators, where fluid models are combined with packet models in order to reduce simulation complexity as well as to track dynamics of end-sources accurately. However, these simulators still need to track the queuing dynamics of network routers, leading to considerable simulation complexity in a large-scale network model. In this paper, we propose a new hybrid simulator – FluNet – where queueing dynamics are not tracked, but instead, an equivalent rate-based model is used. The FluNet simulator is predicated on a fast-queueing regime at bottleneck routers, where the queue length fluctuates on a faster time-scale than end systems. This allows us to simulate large-scale systems, where the simulation “time step-size” is governed only by the time-scale of the end-systems, and not by that of the intermediate routers; whereas a queue-tracking based fluid simulator would require decreasingly smaller step-sizes as the system scale size increases. We validate our model using a ns-2 based implementation. Our results indicate a good match between packet systems and the associated FluNet system.     

毫米波大规模MIMO系统中基于PAST算法的低复杂度混合预编码

在毫米波大规模MIMO系统中,一般采用混合模拟和数字预编码替代全数字预编码来减少射频链和能量消耗.然而,在计算最优无约束混合预编码时,奇异值分解(SVD)具有较高的复杂度.因此,提出了一种基于投影近似子空间跟踪(PAST)的低复杂度混合预编码算法.该算法在计算每个子速率的最优无约束混合预编码时,利用PAST算法估计需要的右奇异矩阵部分主要列向量,从而避免了高复杂度的SVD过程.仿真结果表明,不论是在全连接、混合连接还是在子连接系统结构中,该算法在频谱效率上都接近基于SVD的混合预编码,并且随着发送天线数的增加,提出的算法的复杂度和耗时远低于基于SVD的混合预编码.同时该算法的系统误码率较小,具有较好的可靠性.     

Markov切换系统的随机稳定性分析

根据混合系统离散状态的动态行为和Markov链的状态也是离散的特点，提出了一类离散状态的动态行为是Markov链的混合系统。与传统的混合系统相比，这类系统能够刻画出混合系统离散动态行为的随机性，可以用来描述系统受到外界环境因素制约和内部突发事件等随机因素影响而发生变化的动态行为。根据动态系统的稳定性定义以及随机过程理论，给出了Markov线性切换系统的随机稳定性定义，并且分析了Markov线性切换系统的随机稳定性问题，给出了判定随机稳定性的充分必要条件。     

Hybrid MARTE statecharts

The specification of modeling and analysis of real-time and embedded systems (MARTE) is an extension of the unified modeling language (UML) in the domain of real-time and embedded systems. Even though MARTE time model offers a support to describe both discrete and dense clocks, the biggest effort has been put so far on the specification and analysis of discrete MARTE models. To address hybrid real-time and embedded systems, we propose to extend statecharts using both MARTE and the theory of hybrid automata. We call this extension hybrid MARTE statecharts. It provides an improvement over the hybrid automata in that: the logical time variables and the chronometric time variables are unified. The formal syntax and semantics of hybrid MARTE statecharts are given based on labeled transition systems and live transition systems. As a case study, we model the behavior of a train control system with hybrid MARTE statecharts to demonstrate the benefit.     

Practical verification of decision-making in agent-based autonomous systems

We present a verification methodology for analysing the decision-making component in agent-based hybrid systems. Traditionally hybrid automata have been used to both implement and verify such systems, but hybrid automata based modelling, programming and verification techniques scale poorly as the complexity of discrete decision-making increases making them unattractive in situations where complex logical reasoning is required. In the programming of complex systems it has, therefore, become common to separate out logical decision-making into a separate, discrete, component. However, verification techniques have failed to keep pace with this development. We are exploring agent-based logical components and have developed a model checking technique for such components which can then be composed with a separate analysis of the continuous part of the hybrid system. Among other things this allows program model checkers to be used to verify the actual implementation of the decision-making in hybrid autonomous systems.     

Quantifier-free encoding of invariants for hybrid systems

Hybrid systems are a clean modeling framework for embedded systems, which feature integrated discrete and continuous dynamics. A well-known source of complexity comes from the time invariants, which represent an implicit quantification of a constraint over all time points of a continuous transition. Emerging techniques based on Satisfiability Modulo Theory (SMT) have been found promising for the verification and validation of hybrid systems because they combine discrete reasoning with solvers for first-order theories. However, these techniques are efficient for quantifier-free theories and the current approaches have so far either ignored time invariants or have been limited to hybrid systems with linear constraints. In this paper, we propose a new method that encodes a class of hybrid systems into transition systems with quantifier-free formulas. The method does not rely on expensive quantifier elimination procedures. Rather, it exploits the sequential nature of the transition system to split the continuous evolution enforcing the invariants on the discrete time points. This way, we can encode all hybrid systems whose invariants can be expressed in terms of polynomial constraints. This pushes the application of SMT-based techniques beyond the standard linear case.     

Assume–guarantee verification of nonlinear hybrid systems with Ariadne

In many applicative fields, there is the need to model and design complex systems having a mixed discrete and continuous behavior that cannot be characterized faithfully using either discrete or continuous models only. Such systems consist of a discrete control part that operates in a continuous environment and are named hybrid systems because of their mixed nature. Unfortunately, most of the verification problems for hybrid systems, like reachability analysis, turn out to be undecidable. Because of this, many approximation techniques and tools to estimate the reachable set have been proposed in the literature. However, most of the tools are unable to handle nonlinear dynamics and constraints and have restrictive licenses. To overcome these limitations, we recently proposed an open‐source framework for hybrid system verification, called Ariadne , which exploits approximation techniques based on the theory of computable analysis for implementing formal verification algorithms. In this paper, we will show how the approximation capabilities of Ariadne can be used to verify complex hybrid systems, adopting an assume–guarantee reasoning approach. Copyright © 2012 John Wiley & Sons, Ltd.     

Timed Petri Nets in Hybrid Systems: Stability and Supervisory Control

In this paper, timed Petri nets are used to model and control hybrid systems. Petri nets are used instead of finite automata primarily because of the advantages they offer in dealing with concurrency and complexity issues. A brief overview of existing results on hybrid systems that are based on Petri nets is first presented. A class of timed Petri nets named programmable timed Petri nets (PTPN) is then used to model hybrid systems. Using the PTPN, the stability and supervisory control of hybrid systems are addressed and efficient algorithms are introduced. In particular, we present sufficient conditions for the uniform ultimate boundness of hybrid systems composed of multiple linear time invariant plants which are switched between using a logical rule described by a Petri net. This paper also examines the supervisory control of a hybrid system in which the continuous state is transfered to a region of the state space in a way that respects safety specifications on the plant's discrete and continuous dynamics.