混合自动机的多项式phase-portrait近似

抽象近似是验证混合系统安全性的主要方法,模型转换是构造一个可判定的(或半判定的)混合自动机来近似原混合自动机.本文将线性phase-portrait近似推广到多项式phase-portrait近似,叙述了如何自动构造多项式phase-portrait近似自动机及如何精化近似模型.     

基于定性推理的矩形phase-portrait近似

矩形phase-portrait近似的关键是控制模态的有效划分.本文提出了基于定性推理的phase-portrait近似,给出了一种基于向量场、感兴趣多项式及其李导数动态特性的模态空间划分方法,并进一步给出了基于精化多项式的抽象模型精化方法.实验结果表明,基于定性推理划分的phase-portrait近似验证明显地减少了模态空间的划分数目,提高了验证的效率.     

基于时间自动机的测试用例自动生成及执行方法

为了实现对时间自动机模型的测试,采用符号状态拆分算法对时间自动机的状态空间进行等价划分,以得到最简稳定符号状态转移图,并将其中的抽象时间延迟转移替换为时间延迟变量;针对系统中每个时间自动机建立各自的符号状态转移图,再采用基于符号迁移系统的测试方法分别生成相应的转移动作序列;最后通过对这些序列进行组合产生系统的测试用例,为了执行测试用例,利用TTCN-3的多PTC并发执行能力来实施测试.     

对时间自动机进行空性检测的过程和改进

为了提高对时间自动机进行空性检测的效率,研究了使用基于时钟区域(zone)的符号化方法和抽象对时间自动机进行空性检测,提出了针对时间自动机自身特点对检测过程进行改进的方法.通过使用基于zone的符号化表示方法和抽象,一个符号化状态表示显式的状态的集合,时间自动机的状态空间会显著缩小,不同的抽象方法对状态空间有不同的效果.符号化状态间不仅有相等关系还有包含关系,通过判断这种包含关系可以尽早的找到接收路径和避免不必要的状态展开从而提高空性检测的效率.实现了改进的检测过程,对一些例子进行了数据比较,取得了较好的实验结果.     

基于抽象和搜索空间划分的安全性判定方法

为满足访问控制策略安全性快速判定的要求,提出一种基于谓词抽象和验证空间划分的访问控制策略状态空间约减方法,将在访问控制策略原始状态机模型上的安全性分析工作转移到包含较少状态的抽象模型上,并进一步划分抽象模型的验证空间,以提高效率.理论分析和实验数据均表明,其安全性分析所需的时间和空间都得到有效约减.与传统方法相比,它具有速度更快、自动化程度更高等优点.     

一种基于混合自动机模型的节点动态功耗管理机制研究

为了降低传感器节点的能耗,从而延长传感网络的使用寿命,本文将传感器节点的工作状态划分为四种,并设计了一种基于混合自动机的节点工作状态转换模型.为降低事件丢失率,文中定义了温度和相对湿度两种环境变量,该模型根据这两种环境变量是否跳变来决定节点进入何种工作状态;同时该模型考虑了节点的剩余能量,提高了节点能量使用的均衡性.仿真实验结果表明:该方法是有效的.     

自动验证并发实时系统的线性时段性质

介绍了一个就线性时段性验证实时系统正确性的工具的设计思想以及相关算法,使用时间自动机作为产时系统的描述模型,同时,为了便珩描述并发实时系统,使用带共享变量和通道的时间自动机网作为模型描述并发实时系统,在检验时间自动机网时,用户可以使用工具提供的合成程序将其合并为一个时间自动机然后进行检验,由于时间自动机的状态空间是无究的,通过引入整数状态和状态等价关系的概念,将整个状态0空间划分为有限的状态等价类空间,模型检验过程只需要通过对等价类空间的搜索就可以完成,但往往等价类空间的规模很大,超出了现在计算机的处理能力,原始搜索算法仅仅在理论上是可知地的,为了增工具的使用性,工具中使用的算法运用了一些优化技术来避免对等价类空间的穷尽搜索,使得工具在使用时具有比较好的时间和空间效率。     

一种基于时间自动机的域构造方法

模型检验是一种重要的形式化自动验证技术,通过状态空间搜索来保证软硬件设计的正确性。由于TCTL不是针对时间自动机,而是针对有限状态变迁系统的,从而无法使用TCTL直接对时间自动机进行模型检验。给出了一种从时间自动机到有限状态变迁系统的方法,并在不改变时间自动机的语义上,使时间自动机等价后的域状态数尽可能少,在一定程度上有效地解决了状态空间爆炸问题。     

基于多维度抽象和广度优先搜索空间划分的隐蔽信息流检测方法*

隐蔽信息流检测是开发可信计算机系统中的关键问题,而状态空间爆炸是基于状态机模型检测隐蔽信息流的主要障碍。提出一种多安全级系统中基于主体安全级的二维抽象方法,在此基础上设计了广度优先的搜索空间划分方法,使得划分变量的选取范围更大,扩展了搜索空间划分的应用范围,克服了深度优先划分方法中划分变量难以选取的问题。实验数据表明,结合抽象和搜索空间划分的方法有效降低了模型的验证规模,因此有效缓解了状态空间爆炸问题。     

一种获得有限自动机状态间关系的高效算法

正则表达式匹配在网络安全应用中发挥着重要的作用.确定有限自动机(deterministic finite automaton,DFA)具有高速稳健的性能,因而更适合于在骨干网络环境下执行正则表达式匹配.然而,DFA存在状态膨胀的问题.很多研究工作基于状态关系来解决DFA的状态膨胀问题.然而目前对如何获得状态间的关系仍然缺少一种时空高效的解决办法.提出了一个通过有限自动机(finite automaton,FA)的活跃状态集来准确计算状态关系的算法,并给出了一个高效的获取所有活跃状态集的方法.实验结果证明,该方法不仅能准确地得到状态关系,而且其空间占用和时间消耗仅是已有方法的1?256和15%左右.     

Algorithmic analysis of nonlinear hybrid systems

We present two methods for translating nonlinear hybrid systems into linear hybrid automata. Properties of the nonlinear systems can then be inferred from the automatic analysis of the translated linear hybrid automata. The first method, called clock translation, replaces constraints on nonlinear variables by constraints on clock variables. The second method, called linear phase-portrait approximation, conservatively overapproximates the phase portrait of a hybrid automaton using piecewise-constant polyhedral differential inclusions. Both methods are sound for safety properties. We illustrate both methods by using HYTECH, a symbolic model checker for linear hybrid automata, to automatically check properties of a nonlinear temperature controller and of a predator-prey ecology     

Discrete approximation and supervisory control of continuoussystems

Addresses the following hybrid control problem: a continuous plant (its state evolving in Euclidean space) is to be controlled via symbolic output feedback-both measurement and control signal “live” on finite sets of symbols. We adopt the following approach: the hybrid problem is first translated into a purely discrete problem by approximating the continuous plant model by a (nondeterministic) finite-state machine. By taking into account past measurement and control symbols, approximation accuracy can be improved and adjusted to the specification requirements. Supervisory control theory for discrete-event systems (DES) is then applied to find the optimal controller which enforces the specifications. As the behavior of the approximating automaton is guaranteed to contain the behavior of the underlying continuous plant model, the controller also forces the latter to obey the specifications     

Deterministic finite automata representation for model predictive control of hybrid systems

As is well known, the computational complexity in the mixed integer programming (MIP) problem is one of the main issues in model predictive control (MPC) of hybrid systems such as mixed logical dynamical systems. Thus several efficient MIP solvers such as multi-parametric MIP solvers have been extensively developed to cope with this problem. On the other hand, as an alternative approach to this issue, this paper addresses how a deterministic finite automaton, which is a part of a hybrid system, should be expressed to efficiently solve the MIP problem to which the MPC problem is reduced. More specifically, a modeling method to represent a deterministic finite automaton in the form of a linear state equation with a smaller set of binary input variables and binary linear inequalities is proposed. After a motivating example is described, a derivation procedure of a linear state equation with linear inequalities representing a deterministic finite automaton is proposed as three steps; modeling via an implicit system, coordinate transformation to a linear state equation, and state feedback binarization. Various significant properties on the proposed modeling are also presented throughout the proofs on the derivation procedure.     

On the existence of regular approximations

We approximate context-free, or more general, languages using finite automata. The degree of approximation is measured, roughly speaking, by counting the number of incorrect answers an automaton gives on inputs of length m$m$ and observing how these values behave for large m$m$. More restrictive variants are obtained by requiring that the automaton never accepts words outside the language or that it accepts all words in the language. A further distinction is whether a given (context-free) language has a regular approximation which is optimal under the measure of approximation degree or an approximation which is arbitrarily close to optimal. We study closure and decision properties of the approximation measure.     

Discrete reachability of hybrid systems

This paper concerns hybrid systems subject to discrete-event supervisory control. It investigates the discrete reachability, where the hybrid system should be moved from a discrete initial state z init into a given discrete goal state z goal by a sequence of discrete inputs. The reachability analysis is carried out in three steps. First, a discrete-event model of the hybrid system is set up. Stochastic automata are used to describe all state sequences which may be generated by the hybrid system. Such a model is called complete. Second, methods for the reachability analysis of stochastic automata are elaborated which concern a weak and a strong condition for reachability. Third, these methods are applied to the hybrid system. It is shown that the reachability of the automaton implies the discrete reachability of the hybrid system, because the model is complete. Therefore, the weak and the strong condition for reachability of the stochastic automaton yield a necessary and a sufficient condition for discrete reachability of the hybrid system.     

The real-time supervisory control of an experimental manufacturing system based on a hybrid method

In this paper, the real-time supervisory control of an experimental manufacturing system is reported based on a recently proposed hybrid (mixed PN/automaton) approach. Assuming that an uncontrolled bounded Petri net (PN) model of a (plant) discrete event system (DES) and a set of forbidden state specifications are given, the proposed approach computes a maximally permissive and nonblocking closed-loop hybrid model. The method is straightforward logically, graphically and technologically. This paper particularly shows the applicability of a hybrid (mixed PN/automaton) approach to low-level real-time DES control. To do this, programmable logic controller (PLC) based real-time control of an experimental manufacturing system is considered.     

Inclusion dynamics hybrid automata

Hybrid systems are dynamical systems with the ability to describe mixed discrete-continuous evolution of a wide range of systems. Consequently, at first glance, hybrid systems appear powerful but recalcitrant, neither yielding to analysis and reasoning through a purely continuous-time modeling as with systems of differential equations, nor open to inferential processes commonly used for discrete state-transition systems such as finite state automata. A convenient and popular model, called hybrid automata, was introduced to model them and has spurred much interest on its tractability as a tool for inference and model checking in a general setting. Intuitively, a hybrid automaton is simply a “finite-state” automaton with each state augmented by continuous variables, which evolve according to a set of well-defined continuous laws, each specified separately for each state. This article investigates both the notion of hybrid automaton and the model checking problem over such a structure. In particular, it relates first-order theories and analysis results on multivalued maps and reduces the bounded reachability problem for hybrid automata whose continuous laws are expressed by inclusions (x′f(x,t)) to a decidability problem for first-order formulæ over the reals. Furthermore, the paper introduces a class of hybrid automata for which the reachability problem can be decided and shows that the problem of deciding whether a hybrid automaton belongs to this class can be again decided using first-order formulæ over the reals. Despite the fact that the bisimulation quotient for this class of hybrid automata can be infinite, we show that our techniques permit effective model checking for a nontrivial fragment of CTL.     

Symbolic systems,explicit properties: on hybrid approaches for LTL symbolic model checking

In this work we study hybrid approaches to LTL symbolic model checking; that is, approaches that use explicit representations of the property automaton, whose state space is often quite manageable, and symbolic representations of the system, whose state space is typically exceedingly large. We compare the effects of using, respectively, (i) a purely symbolic representation of the property automaton, (ii) a symbolic representation, using logarithmic encoding, of explicitly compiled property automaton, and (iii) a partitioning of the symbolic state space according to an explicitly compiled property automaton. We apply this comparison to three model-checking algorithms: the doubly-nested fixpoint algorithm of Emerson and Lei, the reduction of emptiness to reachability of Biere et al., and the singly-nested fixpoint algorithm of Bloem et al. for weak automata. The emerging picture from our study is quite clear, hybrid approaches outperform pure symbolic model checking, while partitioning generally performs better than logarithmic encoding. The conclusion is that the hybrid approaches benefit from state-of-the-art techniques in semantic compilation of LTL properties. Partitioning gains further from the fact that the image computation is applied to smaller sets of states.