A Rewriting Based Monitoring Algorithm for TPTL? Ming Chai and Bernd-Holger Schlingloff Humboldt University Berlin, Berlin D-10099, Germany {ming.chai, hs}@informatik.hu-berlin.de Abstract. In this paper, we present a rewriting based monitoring algo- rithm for time propositional temporal logic (TPTL), which is a classic time extension of linear temporal logic (LTL). TPTL has been shown to be more expressive than other real-time extensions of LTL, e.g., metric temporal logic (MTL). We first describe the syntax and semantics of TPTL on finite time-traces. Using Maude, which is an executable envi- ronment for various logics, we give rewriting clauses to check whether a finite time-trace satisfies a TPTL formula. We use our algorithm to test a concrete example from the European Train Control System (ETCS), and evaluate it on several benchmarks. The results show the feasibility of our approach. 1 Introduction Runtime verification is proposed for checking whether a run of a system satisfies or violates a given correctness property [1]. It is seen as a lightweight verification technique when compared to model checking and testing. Runtime verification is able to avoid the following problems of model checking: i) when checking a high complexity system, model checking could suffer from the so-called state explosion problem; ii) when checking a black-box system, a model of the system may not be available for model checking; iii) the object of model checking is a model of the system, not the system itself. Runtime verification is performed by using a monitor. This is a device or a piece of software that reads a behavior of the system under monitoring and gives a certain verdict (true or false) as the result. A behavior of the system is presented by its trace, which is an observable execution sequence of the system. Unlike model checking, runtime verification does not check all executions of the underlying system, but a finite trace. Hence it does not suffer from the state explosion problem when dealing with a large system. Furthermore, runtime verification does not need a model of the system. Therefore, it is well suited to check black-box systems. Finally, the checking object of runtime verification is the system itself. Thus, the possibility of introducing additional errors in the modeling is excluded. ? This work was supported by the State Key Laboratory of Rail Traffic Control and Safety (Contract No.: RCS2012K001), Beijing Jiaotong University 62 Ming Chai, B.-H. Schlingloff One of the most interesting problems in runtime verification is how to build a monitor from a high level specification. Havelund et al. [2] propose a formula rewriting based runtime verification approach, constituting part of a project named Java PathExplorer (JPAX). Their work aims at monitoring Java pro- grams and has been used in Mars Exploration Rover missions. Feng et al. [3] propose an MOP framework for software development and analysis, in which the satisfaction/violation of properties can be detected by executing the code. Barringer et al. [4] propose a rule-based system for trace analysis RuleR. They also propose the LOGSCOPE system, which is an extension of RuleR with a simple, user-friendly temporal logic. d’Amorim et al. present a modified Büchi automata, which is used for monitoring a system [5]. For checking time-relevant properties, real-time logics have been introduced into runtime verification. Bauer et al. [6] work on TLTL based runtime verifica- tion for monitoring real-time properties. They define TLTL by introducing two operators (Ba ∈ I) and (Ca ∈ I) with a being an event, and I being a time in- terval. They build a monitor for a TLTL property, and use event-clock automata to detect whether a trace is accepted or rejected. Metric temporal logic (MTL) [7] is a well studied real-time logic. It is obtained by extending standard LTL with a time bounded temporal operator U[a, b] , where a, b are natural numbers. Several MTL based monitoring approaches have been proposed. Thati et al. [8] propose a formula rewriting based monitoring algo- rithm for MTL. Nickovic et al. propose monitoring algorithms for a restricted version of MTL, named MITL. Basin et al. [9] propose a monitoring algorithm for metric first-order logic. Their approach can cope with variables ranging over infinite domains. They also develop algorithms for MTL with discrete events and continuous states [10]. Alur et al. [11] propose a “more temporal” real-time logic, named time propo- sitional temporal logic (TPTL). It is obtained from LTL by introducing a freeze quantifier “x.”. A TPTL formula can “reset” a formula clock at some point by as- signing variables in the formula to the time value when the formula is evaluated. The expressiveness of TPTL and MTL is studied in [12, 13]. It has been proven that TPTL is strictly more expressive than MTL. Although the verification and model checking problem for TPTL has been studied intensely, the number of TPTL based runtime verification approaches is quite limited. One example is Kristoffersen et al. [14], who give a monitoring algorithm for LTLt , which also extends LTL by a freeze quantifier. The difference between TPTL and LTLt is that the latter needs an extra clock variable r for expressing time. In this paper, we propose a formula rewriting based runtime verification approach for TPTL. The monitor consists of a TPTL formula and a formula rewriting algorithm, where the formula is generated from a high level specifica- tion. The monitor receives a time-trace, which is generated from the underlying system. It detects failures through checking whether this time-trace violates the formula. The process is shown in Fig. 1. Our algorithm is developed directly based on the syntax and semantics of TPTL. A Rewriting Based Monitoring Algorithm for TPTL 63 Fig. 1. The runtime verification process Our algorithm is based on Maude [15], which is a high performance system for model checking, theorem proving, and programming. It can be used for runtime verification implementation. We use the Maude rewriting logic, in the style of the LTL rewriting program proposed by Havelund [16]. Additionally, we present a case study of a concrete example in the railway domain. We translate several properties contained in the specifications of a signaling system to TPTL formu- lae, and abstract some executions of the system to time-traces. Then we monitor these time-traces in Maude. The results show that our approach is feasible for monitoring time-traces. The rest part of the paper is organized as follows. Section 2 introduces the definition of TPTL, including the syntax and semantics. Section 3 presents the Maude-based program for TPTL based monitor. Section 4 shows a case study with a concrete example from the railway domain. Section 5 contains the con- clusion and future work. 2 Preliminaries 2.1 Time-events and Time-traces Given a (finite) set of atomic propositions AP and a (finite) alphabet Σ = 2AP , an event is defined as any single element of Σ, i.e. e = {p1 , · · · , pm } with p1 , · · · , pm ∈ AP . If e is a singleton, we omit the curly brackets in the denotation. If we denote the set of natural numbers by N≥0 and t ∈ N≥0 , then a time-event is defined as a pair te = (e, t) from the set Σ × N≥0 . The natural number t in a time-event te is a discrete time stamp, to identify the time of the event emitted by a running real-time system. Given a time-event te = (e, t), we define Event(te) , e and T ime(te) , t. A time-trace is defined as a (possibly infinite) sequence of time-events, i. e. tt = (te [0], te [1], · · · , te [n]), where for each i < n with i ∈ N≥0 , it holds that T ime (te [i]) < T ime (te [i+1]) (strict monotonicity). The length of tt is denoted by |tt|. 64 Ming Chai, B.-H. Schlingloff 2.2 Syntax and Semantics of TPTL LTL is a widely-accepted logic for specifying properties of infinite traces. TPTL is an extension of LTL to express real-time properties. It contains a freeze quantifier “x.”, which assigns the time value when the formula is evaluated to the variable x. A TPTL formula x. ϕ(x) is satisfied by a time-trace tt iff ϕ(time(tt[0])) is satisfied by tt. For instance, a TPTL formula ( x. (Request → ♦ y. (Ack ∧ y < 5 + x))) expresses the property “whenever an event Request occurs, then the acknowledg- ment event Ack must occur within 5 time units”. This formula is satisfied, e.g., by the time-trace (· · ·, (Request, 7), · · ·, (Ack, 11), · · ·), since 11 < 5 + 7. More precisely, TPTL is defined as follows. Definition 1. (Syntax for TPTL) Given the finite set AP of atomic propo- sitions and a set V of free variables, the terms π and formulae ϕ of TPTL are inductively formed according to the following grammar, where x ∈ V , r ∈ N≥0 , p ∈ AP and ∼ ∈ {≤, <, =, >, ≥}: π ::= x + r | r ϕ ::= ⊥ | p | (ϕ1 → ϕ2 ) | (ϕ1 U ϕ2 ) | π1 ∼ π2 | x. ϕ. The following shorthands are used in TPTL as in LTL: ♦ ϕ stands for > U ϕ,  ϕ stands for ¬♦ ¬ϕ, and ϕ stands for ⊥ U ϕ. Assume that E is a function E: V → N≥0 for assigning free variables in N≥0 (time value) such that E(x + r) = E(x) + r and E(r) = r. Given a variable x and a natural number r, we denote E[x := r] for the evaluation E 0 such that E 0 (x) = r, and E 0 (y) = E(y) for all y ∈ V \{x}. In runtime verification, the time-traces to be checked are finite. Hence, we give TPTL finite semantics as follows. Definition 2. (Semantics for TPTL) Let tt be a finite trace with i ∈ N≥0 being a position, p a proposition, and ϕ1 and ϕ2 any TPTL formulae. The sat- isfaction relation (tt, i, E) |= ϕ is defined inductively as follows: (tt, i, E) 2 ⊥; (tt, i, E) |= p iff p ∈ Event(tt[i]); (tt, i, E) |= (ϕ1 → ϕ2 ) iff (tt, i, E) |= ϕ1 implies (tt, i, E) |= ϕ2 ; (tt, i, E) |= (ϕ1 U ϕ2 ) iff there exists i < j < |tt| with (tt, j, E) |= ϕ2 and for all i < j 0 < j it holds that (tt, j 0 , E) |= ϕ1 ; (tt, i, E) |= π1 ∼ π2 iff E(π1 ) ∼ E(π2 ); (tt, i, E) |= x. ϕ iff (tt, i, E[x := T ime(tt[i])]) |= ϕ. As is proven in [13], TPTL is strictly more expressive than MTL. The property “whenever an a-event occurs, then a b-event will occur in the future and, later a c-event will occur within 3 time units” can be expressed by a TPTL formula as:  x. (a → ♦ (b ∧ ♦ y. (c ∧ y < x + 3))). This property cannot be expressed in MTL. A Rewriting Based Monitoring Algorithm for TPTL 65 3 The Rewriting Algorithm for TPTL in Maude Subsequently, we develop an algorithm for checking whether a finite time-trace satisfies a TPTL formula. More specifically, when checking the satisfaction rela- tion between a finite time-trace and a TPTL formula, the formula is continuously transformed to another formula by consuming the first time-event in the time- trace. This procedure processes iteratively, until the last time-event is consumed. It will output a boolean value in B ={true, f alse}. Our algorithm is implemented in Maude, which provides an executable environment for various logics. Here we informally describe some of Maude’s features which are related to the algorithm, more details can be found in the manual [17]. 3.1 Basic Rewriting Operators and Logic Connectives In Maude, we use the functional modules following the pattern fmod is emdfm. The body of a functional module consists of a collection of declarations, of which we will use sorts (sort and sorts), subsorts (subsort and subsorts), operations (op and ops), variables (var and vars) and equations (eq). We first need to define all necessary data types involved in the program, including atomic proposition (Atom), event (Event), time-event (T imeEvent), time-trace (T imeT race) and free variable (FreeV). These types are defined ac- cording to their definition shown above. The following Maude program defines operators “__”, “_:-_ ”, “_,_” and “_ of _” for generating an event, a time- event, a time-trace and a free variable, respectively. Every operator has a priority feature, which is declared through “[prec n]” with n ∈ N≥0 . op __ : Atom Event -> Event [prec 23] . op _:-_ : Event Nat -> TimeEvent [prec 23] . op _,_ : TimeEvent TimeTrace -> TimeTrace [prec 25] . op _ of _ : Nat Atom -> FreeV [prec 23]. //receive a Nat (stands for the value of the variable) and an Atom (stands for the name of the variable), and generate a FreeV as the result. op nil : -> Event . //an emptyset is an event We also define Atom to be a subsort of Event, T imeEvent to be a subsort of T imeT race, and FreeV and N at to be subsorts of Atom. Based on the syntax and semantics of TPTL described above, we define several operators, “_{_}”, “_{_}0 ” and “_|=_”, for checking whether a time- trace satisfies a formula. The operator “_{_}” receives a formula and an event. It yields the formula >/⊥ depending on whether the event satisfies the formula or not. The operator “_{_}0 ” is defined on basis of “_{_}” for checking the satisfaction relation between a time-event and a formula. A time-event te satisfies a formula ϕ iff ϕ{Event(te)} returns >. By extending “_{_}0 ”, the operator 66 Ming Chai, B.-H. Schlingloff “_|=_” is defined for checking whether a time-trace satisfies a formula. This operator receives a time-trace and a formula, and generates a boolean value in B. Given a formula ϕ and a time-trace (te, tt) consisting of a time-event te and its suffix tt, then (te, tt) |= ϕ returns true/false iff ϕ{te}0 returns >/⊥ as the result. The calculation rules of logic connectives → (implication), ∧ (and), ∨ (or), ++ (exclusive or), ! (negation) and ↔ (equivalence) are declared as usual [16]. In our program, the comparison operators (≤, <, =, > and ≥) and the primi- tive operator (+) in TPTL are denoted by ≤0 , <0 , =0 , >0 , ≥0 and +0 respectively, to distinguish the original definition of these operators in Maude. See < as an example of comparison operators, the declaration for <0 is shown as follows. vars R R’ N N’ : Nat . vars A A’ : Atom . op _<’_ : Formula Formula -> Formula [prec 40] . ceq R <’ R’ = true if R < R’ . ceq R <’ R’ = false if R > R’ or R == R’ . ceq ( N of A ) <’ R = true if N < R . ceq ( N of A ) <’ R = false if N > R or N == R . ceq ( N of A ) <’ ( N’ of A’ ) = true if N < N’ . ceq ( N of A ) <’ ( N’ of A’ ) = false if N > N’ or N == N’ . 3.2 Temporal Operators and Freeze Quantifiers In this part we describe the Maude program for temporal operators and freeze quantifiers in TPTL. Let TE be a time-event, TT be a time-trace, X and Y be formulae, and U’ be an operator, which receives two formulae and generates a formula. The rewriting rules for the temporal operator U is presented as follows. eq TE |= X U Y = false . eq TE, TT |= X U Y = TT |= X U’ Y . eq TE, TT |= X U’ Y = TE, TT |= Y or TE, TT |= X and TT |= X U’ Y . eq TE |= X U’ Y = TE |= Y . In Maude, we denote the formula x. ϕ by (R of x) @ ϕ with x ∈ AP being the name of the quantifier, R ∈ N≥0 being the value of the quantifier, and ϕ being a TPTL formula. In addition, we define an operator “@@” for assigning free variables in ϕ. The rewriting process of tt |= (R of x) @ ϕ is separated into two steps as follows. 1. The variable x of x. ϕ is set to the time when the formula is evaluated. Hence, the formula (R of x) @ ϕ is rewritten to another formula ((T ime(tt[0]) of x) @@ ϕ), where (T ime(tt[0]) is the initial time value from the given time-trace; 2. The operator @@ assigns all occurrences of variable x in ϕ to the value (T ime(tt[0]), and proceeds with the tt |= ϕ checking process. The Maude program is as follows. A Rewriting Based Monitoring Algorithm for TPTL 67 /* the value of a freeze quantifier (R of A) equals to T, which is the time of the first time-event in the time-trace */ eq E :- T, TT |= (R of A) @ X = E :- T , TT |= ((T of A ) @@ X) . eq E :- T |= (R of A) @ X = E :- T |= ( T of A ) @@ X . ceq (M of A) @@ (M’ of A’) = (M of A’ ) if A == A’ . // a FreeV (M’ of A’) is assigned to the value of the freeze quantifier (M of A) if they have the same name ceq (M of A) @@ (M’ of A’) = (M’ of A’ ) if A =/= A’ . // a FreeV (M’ of A’) is not assigned to the value of the freeze quantifier (M of A) if they have different names /* the value assignment rule for an algebraic formula. */ ceq (N of A) @@ (N’ of A’ +’ R) = N + R if A == A’ . ceq (N of A) @@ (N’ of A’ +’ R) = (N’ of A’ +’ R) if A =/= A’ . In addition, we introduce the following equivalences into the program for the op- erator @@. These equivalences are declared in the module FREE-QUAN, where N , N 0 , M and M 0 are natural numbers; A, A0 , B and B 0 are atomic propositions; E is an event; and X, Y , true and f alse are formulae. eq (N of A) @@ (X /\ Y) = (N of A) @@ X /\ (N of A) @@ Y eq (N of A) @@ (X ++ Y) = ((N of A) @@ X) ++ ((N of A) @@ Y) eq (N of A) @@ E = E eq (N of A) @@ (X <’ Y) = ((N of A) @@ X) <’ ((N of A) @@ Y) eq (N of A) @@ true = true . eq ( N of A ) @@ false = false eq (N of A) @@ ((N’ of A’) @ X) = (N’ of A’) @ ((N of A) @@ X) eq (N of A) @@ (<> X) = <> ((N of A) @@ X) eq (N of A) @@ ([] X) = [] ((N of A) @@ X) eq (N of A) @@ (X U Y) = ((N of A) @@ X) U ((N of A) @@ Y) eq (N of A) @@ (o X) = o ((N of A) @@ X) 4 Case Study: the RBC/RBC Handover Process In this section, we apply our TPTL runtime verification implementation to a concrete example from the European Train Control System (ETCS). ETCS is a signaling, control and train protection system that is replacing the national, incompatible safety systems within Europe. ETCS consists of the on-board sub- system (composed of ERTMS/ETCS on-board equipment, the on-board part of the GSM-R radio system and specific transmission modules for existing national train control systems), and the track-side sub-system (composed of balise, line- side electronic unit, GSM-R, radio block center (RBC), euroloop and radio infill unit) [18]. In ETCS, the RBC is responsible for providing movement authori- ties to allow the safe movement of trains. A movement authority is generated by computing messages to be sent to the trains, where the messages are on the 68 Ming Chai, B.-H. Schlingloff basis of information received from external track-side systems and information exchanged with the on-board sub-system. A route is divided into several RBC supervision areas. Here we consider the RBC/RBC handover specification. When a train approaches the border of an RBC supervision area, an RBC/RBC han- dover process takes place (see Fig. 2). The RBC/RBC handover specification specifies how a train moves from one RBC supervision area to an adjacent one. Fig. 2. The RBC/RBC handover process We consider properties on basis of the two different specifications: FIS for the RBC/RBC Handover [19] and RBC-RBC Safe Communication Interface [20]. An execution of the system refers to the following properties in the FIS for the RBC/RBC Handover. – Property 1: “the handing over RBC is responsible to send information about an approaching train to the accepting RBC area (i.e. pre-announcement)” (4.2.2.1); – Property 2: “the handing over RBC must send Acknowledgment after receiv- ing route related information” (5.2.2.5); – Property 3: “if the Acknowledgment for route related information is missing, the accepting RBC must send route related information again” (5.2.3.5). Based on the specification of the Safe Communication Interface, we assume that the time to take into account an incoming message and produce an answer is between 30 and 60 time units. We also assume that the tolerance window for the messages transition time is between 0 and 50 time units. Table 1 shows the abbreviations used in our case. Let Mess be any message. We write “sendMess” for the Mess which is sent by a component, and “recvMess” for the Mess which is received by a component. The above properties can be expressed by the following TPTL formulae. A Rewriting Based Monitoring Algorithm for TPTL 69 Table 1. Abbreviations in case study Abbreviation Definition HOVcond Handover condition detected PreANN Pre-announcement RRI Route related information Ackn Acknowledgment AcknMissing The Acknowledgement is missed RRIReq Route related information request MAReq Movement authority request PosRep Position report Ann Announcement TOR Taking Over Responsibility BPSRE Position report: “Border passed by safe rear end” BPFE Position report: “Border passed by max safe front end” – Property 1: ϕ1 =  x.(sendPreANN → ♦ y. (recvPreANN ∧ (y ≤ x + 50))). – Property 2: ϕ2 =  x.(recvRRI → ♦ y.(sendAckn ∧ (y ≥ x + 30) ∧ (y ≤ x + 60))). – Property 3: After an RRI message is sent by the accepting RBC, three time intervals must be considered: the transition time of RRI (0 < r1 ≤ 50), the time for producing acknowledgment (30 ≤ r2 ≤ 60) and the transition time of the message acknowledgment (0 < r3 ≤ 50). Hence, if the accepting RBC does not receive the acknowledgment between 30 and 160 (= 50 + 60 + 50) time units after sending an RRI, an AcknMissing message should occur. The accepting RBC should resend an RRI after the AcknMissing message occurs, within 50 time units. Now property 3 can be expressed by the TPTL formula ϕ3 , : • ϕ31 =  (x.(sendRRI → ♦ y.(recvAckn ∧ (y ≤ x + 160) ∧ (y ≥x + 30))) ++ x.(sendRRI → ♦ y.(AcknMissing ∧ (y > x + 160)))); • ϕ32 =  x.(AcknMissing → ♦ y.(sendRRI ∧ (y < x + 50))); • ϕ3 =ϕ31 ∧ ϕ32 . We assume that the handing over RBC and the accepting RBC have a syn- chronized clock, beginning at time 0. An example of RBC/RBC handover pro- cess is given in the FIS for the RBC/RBC Handover specification. Based on the RBC-RBC Safe Communication Interface specification, we design a poten- tial time stamp for each event, get an example of real-time executions of this process, shown in Fig. 3. A corresponding time-trace is as follows. tt1 = (sendPreANN, 0), (sendRRIReq, 20), (recvPreANN, 35), ({sendR- RIReq, recvRRIReq}, 50), (sendRRI, 90), (recvRRIReq, 97), (recvRRI, 115), (sendAckn, 157), (sendRRI, 180), (recvAckn, 191), (AcknMissing, 350), (sendRRI, 360), (recvRRI, 373), (sendAckn, 403), (recvAckn, 437), (recvMAReq, 492), (sendRRIReq, 536), (recvRRIReq, 542), (sendRRI, 583), (recvRRI, 592), (send Ackn, 639), (recvAckn, 652), (recvBPFE, 700), (sendTOR, 738), (sendAnn, 741), (recvAnn, 752), (recvTOR, 759), (recvCBPRE, 800). 70 Ming Chai, B.-H. Schlingloff Fig. 3. An example of message sequence The calculation results of tt1 |= ϕ1 , tt1 |= ϕ2 and tt1 |= ϕ3 in Maude are all true. It means that this execution satisfies all the three properties. Time-trace tt2 represents an execution in which some errors occur: i) the accepting RBC receives the pre-announcement 60 time units after it is sent; ii) the handing over RBC does not send the acknowledgment after reception of an RRI; iii) when missing the acknowledgment of an RRI, the accepting RBC does not resend it. tt2 = (sendPreANN, 0), (sendRRIReq, 20), (recvPreANN, 60), ({sendR- RIReq, recvRRIReq}, 65), (sendRRI, 90), (recvRRIReq, 97), (recvRRI, 115), (sendRRI, 180), (recvMAReq, 492), (sendRRIReq, 536), (recvRRIReq, 542), (sendRRI, 583), (recvRRI, 592), (sendAckn, 639), (recvAckn, 652), (recvBPFE, 700), (sendTOR, 738), (sendAnn, 741), (recvAnn, 752), (recvTOR, 759), (recv CBPRE, 800). The calculation results of tt2 |= ϕ1 , tt2 |= ϕ2 and tt2 |= ϕ3 are all false, which means that this execution of the system violates the properties. We repeated similar experiments several times with difference traces. The checking efficiency is shown in Fig. 4. The case study shows that our TPTL based runtime verification implementation is feasible to detect failures in the executions of a system. A Rewriting Based Monitoring Algorithm for TPTL 71 Fig. 4. The monitoring efficiency in Maude 5 Conclusion In this paper, we have proposed a runtime verification method for TPTL. We developed a formula rewriting based algorithm, and implemented the algorithm in Maude. This makes it possible to check the satisfaction relation between a long time-trace and a complex TPTL formula automatically. Furthermore, we have presented a case study with a concrete example from the railway domain. The results show the feasibility of our implementation. There are several interesting topics for future work. Firstly, as is well known, LTL with two truth values gives misleading results when checking finite traces. For this reason, we want to develop a three-valued TPTL, introducing a third truth value “inconclusive”. This truth value means the satisfaction relation be- tween a time-trace and a TPTL formula is decided by the potential suffix of the given initial fragment of the time-trace. Secondly, the clock reset principle in a TPTL formula x.ϕ is to freeze the variable x in ϕ when the formula is evaluated. This makes TPTL unintuitive in the cases when a property contains a “clock-reset” condition. Hence an extension of TPTL with modifying the freeze quantifier “x.” to “ψ.” is worth to be studied, where ψ is any formula. Last but not least, to solve the difficulty of writing formal specifications in runtime ver- ification, we are going to study specification techniques. The long-term goal is to develop a methodology to semi-automatically translate system specifications from the railway domain into temporal formulae. References 1. Leucker, M., Schallhart, C.: A Brief Account of Runtime Verification. Journal of Logic and Algebraic Programming 78, 293-303 (2009) 2. Havelund, K., Roşu, G.: Monitoring Java Programs with Java PathExplorer. Elec- tronic Notes in Theoretical Computer Science 55, 200-217 (2001) 3. Chen, F. and G. Roşu.: Mop: an efficient and generic runtime verification frame- work. ACM SIGPLAN Notices, pp. 569-588 (2007) 4. Barringer, H., Havelund, K., Rydeheard, D., Groce, A.: Rule Systems for Runtime Verification: A Short Tutorial. In: Runtime Verification, pp. 1-24. Springer, (2009) 72 Ming Chai, B.-H. Schlingloff 5. d’Amorim, M., Roşu, G.: Efficient Monitoring of ω-languages. In: Computer Aided Verification, pp. 364-378. Springer, (2005) 6. Bauer, A., Leucker, M., Schallhart, C.: Runtime verification for LTL and TLTL. ACM Transactions on Software Engineering and Methodology (TOSEM) 20, (2011) 7. Koymans, R.: Specifying Real-time Properties with Metric Temporal Logic. Real- time systems 2, 255-299 (1990) 8. Thati, P., Roşu, G.: Monitoring Algorithms for Metric Temporal Logic Specifica- tions. Electronic Notes in Theoretical Computer Science 113, 145-162 (2005) 9. Basin, D., Klaedtke, F., Müller, S., Pfitzmann, B.: Runtime Monitoring of Met- ric First-order Temporal Properties. In: IARCS Annual Conference on Founda- tions of Software Technology and Theoretical Computer Science, pp. 49-60. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, (2008) 10. Basin, D., Klaedtke, F., Zălinescu, E.: Algorithms for Monitoring Real-time Prop- erties. In: Runtime Verification, pp. 260-275. Springer, (2011) 11. Alur, R., Henzinger, T.A.: A Really Temporal Logic. Journal of the ACM (JACM) 41, 181-203 (1994) 12. Alur, R., Henzinger, T.A.: Real-time Logics: Complexity and Expressiveness. In- formation and Computation 104, 35-77 (1993) 13. Bouyer, P., Chevalier, F., Markey, N.: On the Expressiveness of TPTL and MTL. Information and Computation 208, 97-116 (2010) 14. Kristoffersen, K.J., Pedersen, C., Andersen, H.R.: Runtime Verification of Timed LTL Using Disjunctive Normalized Equation Systems. Electronic Notes in Theo- retical Computer Science 89, 210-225 (2003) 15. Clavel, M., Durán, F., Eker, S., Lincoln, P., Martí-Oliet, N., Meseguer, J., Que- sada, J.F.: Maude: Specification and Programming in Rewriting Logic. Theoretical Computer Science 285, 187-243 (2002) 16. Havelund, K., Rosu, G.: Monitoring Programs Using Rewriting. In: Automated Software Engineering, 2001.(ASE 2001). Proceedings. 16th Annual International Conference on, pp. 135-143. IEEE, (2001) 17. Clavel, M., Durán, F., Eker, S., Lincoln, P., Martí-Oliet, N., Meseguer, J., Talcott, C.: Maude Manual (version 2.6). University of Illinois, Urbana-Champaign 1, 4.6 (2011) 18. UNISIG: SUBSET-026: System Requirements Specification. (2008) 19. UNISIG: SUBSET-039: FIS for the RBC/RBC Handover. (2005) 20. UNISIG: SUBSET-098: RBC-RBC Safe Communication Interface. (2007)