Synchronous programming is a paradigm of choice for the design of safety-critical reactive systems. Runtime enforcement is a technique to ensure that the output of a black-box system satisfies some desired properties. This paper deals with the problem of runtime enforcement in the context of synchronous programs. We propose a framework where an enforcer monitors both the inputs and the outputs of a synchronous program and (minimally) edits erroneous inputs outputs in order to guarantee that a given property holds. We define enforceability conditions, develop an online enforcement algorithm, and prove its correctness. We also report on an implementation of the algorithm on top of the KIELER framework for the SCCharts synchronous language. Experimental results show that enforcement has minimal execution time overhead, which decreases proportionally with larger benchmarks.
Synthesizing enforcers from properties is an active area of research. According to how an enforcer is allowed to correct the input sequence, several RE models have been proposed. Security automata proposed by Schneider @cite_4 focus on enforcement of safety properties, where the enforcer blocks the execution when it recognizes a sequence of actions that doses not satisfy the desired property. Edit automata @cite_0 allows the enforcer to correct the input sequence by suppressing and (or) inserting events, and the RE mechanisms proposed in @cite_6 @cite_12 allows buffering events and releasing them upon observing a sequence that satisfies the desired property. Recently, compositionality of enforcers has been studied in @cite_5 . Given a set of properties over the same alphabet, the problem studied in @cite_5 addresses whether it is possible to synthesize multiple enforcers, one for each property, and whether composing enforcers (in series or in parallel) can enforce all the properties. Moreover, the enforcement framework in @cite_5 allows to buffer (delay) events. These approaches focus on uni-directional RE.
@cite_4 @cite_6 @cite_0 @cite_5 @cite_12
1973223152 2160106331 2505158018 2163458574
Runtime enforcement is a powerful technique to ensure that a running system satisfies some desired properties. Using an enforcement monitor, an (untrustworthy) input execution (in the form of a sequence of events) is modified into an output sequence that complies with a property. Over the last decade, runtime enforcement has been mainly studied in the context of untimed properties. This paper deals with runtime enforcement of timed properties by revisiting the foundations of runtime enforcement when time between events matters. We propose a new enforcement paradigm where enforcement mechanisms are time retardants: to produce a correct output sequence, additional delays are introduced between the events of the input sequence. We consider runtime enforcement of any regular timed property defined by a timed automaton. We prove the correctness of enforcement mechanisms and prove that they enjoy two usually expected features, revisited here in the context of timed properties. The first one is soundness meaning that the output sequences (eventually) satisfy the required property. The second one is transparency, meaning that input sequences are modified in a minimal way. We also introduce two new features, (i) physical constraints that describe how a time retardant is physically constrained when delaying a sequence of timed events, and (ii) optimality, meaning that output sequences are produced as soon as possible. To facilitate the adoption and implementation of enforcement mechanisms, we describe them at several complementary abstraction levels. Our enforcement mechanisms have been implemented and our experimental results demonstrate the feasibility of runtime enforcement in a timed context and the effectiveness of the mechanisms. Abstract We present an approximation technique, that can render real-time model checking of safety and universal path properties more efficient. It is beneficial, when loops lead to repetition of control situations. Basically we augment a timed automata model with carefully selected extra transitions. This increases the size of the state-space, but potentially decreases the number of symbolic states to be explored by orders of magnitude. We give a formal definition of a timed automata formalism, enriched with basic data types, hand-shake synchronization, urgency, and committed locations. We prove by means of a trace semantics, that if a safety property can be established in the augmented model, it also holds for the original model. We extend our technique to a richer set of properties, that can be decided via a set of traces (universal path properties). In order for universal path properties to carry over to the original model, the semantics of the timed automata formalism is formulated relative to the applied augmentation. Our technique is particularly useful in systems, where a scheduler dictates repetition of control over elapsing time. As a typical example we mention translations of LEGO® RCX™ programs to U ppaal models, where the Round-Robin scheduler is a static entity. We allow scheduler and associated tasks to “park”, until some timing or environmental conditions are met. We apply our technique on a brick-sorter model for a safety property and report run-time data. Runtime enforcement is a methodology used to enforce that the output of a running system satisfies a desired property. Given a property, an enforcement monitor modifies an untrusted sequence of events into a sequence that complies to that property. In practice, we may have not one, but many properties to enforce. Moreover, new properties may arise as new capabilities are added to the system. It then becomes interesting to be able to build not a single, monolithic monitor that enforces all the properties, but rather several monitors, one for each property. The question is to what extent such monitors can be composed, and how. This is the topic of this paper. We study two monitor composition schemes, serial and parallel composition, and show that, while enforcement under these schemes is generally not compositional, it is for certain subclasses of regular properties. The paper concerns the synthesis of supervisory controllers for a class of continuous-time hybrid systems with discrete-valued input signals that select differential inclusions for continuous-valued state trajectories and event-valued output signals generated by threshold crossings in the continuous state space, the supervisor is allowed to switch the input signal value when threshold events are observed. The objective is to synthesize a nonblocking supervisor such that the set of possible sequences of control and threshold event pairs for the closed-loop system lies between given upper and lower bounds in the sense of set containment. We show how this problem can be converted into a supervisor synthesis problem for a standard controlled discrete-event system (DES). A finite representation may not exist for the exact DES model of the hybrid system, however. To circumvent this difficulty, we present an algorithm for constructing finite-state Muller automata that accept outer approximations to the exact controlled threshold-event language, and we demonstrate that supervisors that solve the synthesis problem for the approximating automata achieve the control specifications when applied to the original hybrid system.