Rômulo Meira-Góes

Hervé Marchand

Stéphane Lafortune

Dealing with sensor and actuator deception attacks in supervisory control

Keywords: Discrete Event Systems, Supervisory Control, Deception Attacks, Cyber-Security

We consider feedback control systems where sensor readings and actuator commands may be compromised by an attacker intending to damage the system. We study this problem at the supervisory layer of the control system, using discrete event systems techniques. The attacker can edit the outputs from the sensors of the system before they reach the supervisory controller as well as it can edit actuator commands before they reach the system. In this context, we formulate the problem of synthesizing a supervisor that is robust against a large class of edit attacks on the sensor readings and actuator commands. Intuitively, we search for a supervisor that guarantees the safety of the system even when sensor readings and actuator commands are compromised. Given the similarities of the investigated problem to the standard supervisory control problem, our solution methodology reduces the problem of synthesizing a robust supervisor against deception attacks to a supervisory control problem. This new and intuitive solution methodology improves upon prior work on this topic.

Introduction

Security concerns are a subject of increasing attention in the control community, e.g., see [START_REF] Cardenas | Secure control: Towards survivable cyber-physical systems[END_REF][START_REF] Teixeira | Attack models and scenarios for networked control systems[END_REF]. It was only recently that security aspects started to be incorporated into the design of feedback control systems. Understanding and designing feedback control systems that are robust against attacks is of critical importance nowadays.

In this paper, we assume that the underlying uncontrolled system has been abstracted as a discrete transition system (the plant in this work), where sensor outputs belong to a finite set of (observable) events. A high-level supervisory controller, or simply supervisor, driven by observable events controls the behavior of the plant via actuator commands. Based on this event-driven model, we incorporate an attacker that hijacks a subset of the observable events and actuator commands. As depicted in Fig. 1, the attacker infiltrates and manipulates both communication channels between the plant and the supervisor; this type of attack is known as a deception attack. We study the design of feedback control systems that are robust against deception attacks at their ⋆ RMG and SL are supported in part by the US National Science Foundation under grants CNS-1738103 and CNS-1801342.

Email addresses: romulo@umich.edu (Rômulo Meira-Góes), herve.marchand@inria.fr (Hervé Marchand), stephane@umich.edu (Stéphane Lafortune). supervisory layer. Conceptually, we answer the following question:

Can we find a supervisor that guarantees the safety of the plant even in the presence of attacks on both communication channels? Our solution methodology comprises two steps and employs techniques from supervisory control of partiallyobserved discrete event systems. In the first step, we build an augmented plant, called attacked plant, where the possible attacker's sensor manipulations are intertwined with the plant model. The attacked plant can be built in a manner that accounts for all possible attacks or can be built based on a known attack model. The second step poses a supervisory control problem for the attacked plant under a safety specification and incorporates the possible attacker's actuator manipulations. This supervisory control problem becomes an instance of supervisory control with arbitrary control patterns under partial observation, for which the existing theory of supervisory control of discrete event systems is leveraged (Golaszewski and Ramadge 1987, Li Preprint submitted to Automatica 24 September 2022[START_REF] Li | A generalized framework for supervisory control of discrete event systems[END_REF][START_REF] Takai | Supervisory control of partially observed discrete event systems with arbitrary control patterns[END_REF]. We show that the solution of the supervisory control problem for the attacked plant provides a solution for the problem addressed in this paper. Moreover, our solution methodology using control patterns allows a separation between the sensor and actuator attack constraints, i.e., how these attacks affect the plant and the supervisor.

Related work

Prior work on deception attacks in the field of Discrete Event Systems (DES) mainly focuses on three axes: attack detection [START_REF] Thorsley | Intrusion detection in controlled discrete event systems[END_REF], Carvalho et al. 2018[START_REF] Lima | Detectable and undetectable network attack security of cyber-physical systems[END_REF][START_REF] Lima | Security against communication network attacks of cyber-physical systems[END_REF], attack synthesis [START_REF] Su | Supervisor synthesis to thwart cyber attack with bounded sensor reading alterations[END_REF][START_REF] Zhang | Stealthy attacks for partially-observed discrete event systems[END_REF], Lin et al. 2019a[START_REF] Meira-Góes | Synthesis of sensor deception attacks at the supervisory layer of cyber-physical systems[END_REF], Meira-Góes et al. 2021c), and robust supervisor synthesis [START_REF] Wakaiki | Supervisory control of discrete-event systems under attacks[END_REF][START_REF] Su | Supervisor synthesis to thwart cyber attack with bounded sensor reading alterations[END_REF][START_REF] Meira-Góes | Towards resilient supervisors against sensor deception attacks[END_REF][START_REF] Lin | Towards bounded synthesis of resilient supervisors[END_REF], Zhu et al. 2019[START_REF] Wang | Attack-resilient supervisory control with intermittently secure communication[END_REF]. Attack detection focuses on identifying conditions for attack detection for a given closed-loop system. Attack synthesis problems investigate the automatic design of successful attack strategies for a given supervisory control system. Lastly, robust supervisor synthesis problems against attacks study techniques to synthesize supervisors that are robust-by-construction.

Our work differs intrinsically from attack detection and attack synthesis since it focuses on robust supervisor synthesis. Each work investigating the robust supervisor synthesis problem focuses on different attack constraints. For example, robustness against bounded sensor deception attacks is studied in [START_REF] Su | Supervisor synthesis to thwart cyber attack with bounded sensor reading alterations[END_REF]; robustness against parameterized sensor deception attacks is considered in [START_REF] Meira-Góes | Towards resilient supervisors against sensor deception attacks[END_REF], Meira-Góes et al. 2021d); robustness against actuator and sensor-replacement deception attacks is explored in [START_REF] Lin | Towards bounded synthesis of resilient supervisors[END_REF]; and robustness against actuator and sensor deception attacks is investigated in [START_REF] Wang | Attack-resilient supervisory control with intermittently secure communication[END_REF]. The works in [START_REF] Su | Supervisor synthesis to thwart cyber attack with bounded sensor reading alterations[END_REF][START_REF] Wakaiki | Supervisory control of discrete-event systems under attacks[END_REF][START_REF] Meira-Góes | Towards resilient supervisors against sensor deception attacks[END_REF], Meira-Góes et al. 2021d) only focus on sensor deception attacks.

Compared to [START_REF] Lin | Towards bounded synthesis of resilient supervisors[END_REF], our work complements their results by providing a general solution for the problem of synthesizing robust supervisors against both actuator and sensor deception attacks. Sensor deception attacks in [START_REF] Lin | Towards bounded synthesis of resilient supervisors[END_REF]) only encompass sensor replacement attacks, i.e., the attacker either replaces a compromised sensor reading by another reading or deletes the sensor reading. In our work, sensor deception attacks are parameterized based on prior attack knowledge, i.e., bounded attacks, replacement attacks, etc. However, we leave for future work parameterizing actuator deceptions attacks, which is possible in [START_REF] Lin | Towards bounded synthesis of resilient supervisors[END_REF]. Lastly, our solution approach reduces the robust supervisor synthesis problem to a supervisory control problem, which provides a more intuitive solution in our opinion.

The supervisory control framework in (Wang and Pajic 2019) differs from the standard framework since they assume that the supervisor can actively change the state of the physical process. Therefore, our results also differ from the ones in [START_REF] Wang | Attack-resilient supervisory control with intermittently secure communication[END_REF] since we study the robustness problem in the standard supervisory control framework.

Contributions

We have four main contributions in this paper: (i) using the idea of control patterns, we describe a new modeling technique to define the closed-loop behavior of supervisory control systems under sensor and actuator attacks; (ii) we reduce the robust supervisor synthesis problem against both sensor and actuator attacks to an instance of the supervisor synthesis problem under arbitrary control patterns constraints; (iii) we provide sufficient conditions on the existence of the supremal robust supervisor against sensor and deception attacks; and (iv) we discuss necessary modifications on supervisory control synthesis algorithms (Hadj-Alouane et al. 1996, Yin and[START_REF] Yin | A uniform approach for synthesizing property-enforcing supervisors for partially-observed discrete-event systems[END_REF] to synthesize maximal robust supervisors and all robust supervisors. Preliminary results of this paper appeared in [START_REF] Meira-Góes | Towards resilient supervisors against sensor deception attacks[END_REF], where only sensor deception attacks were considered. Herein, we extend our previous work by considering both sensor and actuator attacks as well as providing the missing proofs in [START_REF] Meira-Góes | Towards resilient supervisors against sensor deception attacks[END_REF].

Organization

This paper is organized as follows. Section 2 introduces necessary background used throughout the paper. The framework of supervisory control theory under sensor and actuator deception attacks and the synthesis of robust supervisors are presented in Section 3. In Section 4, we provide the solution methodology for the studied problem and discuss its correctness. Sections 5 discusses two different algorithms that synthesize robust supervisors and the trade-off between them. We conclude the paper in Section 6.

Preliminaries

We consider systems modeled as automata. Mathematically, an automaton G is defined as a tuple G := (X G , Σ, δ G , x 0,G ), where X G is a finite set of states; Σ is a finite set of events; δ G : X G ×Σ → X G is a partial transition function; and x 0,G ∈ X G is the initial state. The function δ G is extended in the usual manner to domain X G × Σ * , where * is the standard Kleene star operation. The language generated by G is defined as L(G) := {s ∈ Σ * |δ G (x 0 , s)!}, where ! means "is defined". For x ∈ X G , we define En G (x) := {e ∈ Σ | δ G (x, e)!} as the active event set at state x. For K ⊆ Σ * , we denote by pr(K) the set of all prefixes of strings in K and K is said to be prefix-closed if K = pr(K).

In the context of supervisory control theory of DES [START_REF] Ramadge | Supervisory control of a class of discrete event processes[END_REF]), an uncontrolled system (plant) G is controlled by a supervisor, denoted by S. This controlled system is a new DES denoted by S/G with closed-loop language L(S/G) defined in the usual manner (see, e.g., [START_REF] Cassandras | Introduction to Discrete Event Systems[END_REF]Lafortune 2008, Wonham and[START_REF] Wonham | Supervisory Control of Discrete-Event Systems[END_REF]). Usually, the supervisor S has limited actuation and sensing capabilities described by the pair of partitions of Σ (Σ c , Σ uc ) and (Σ o , Σ uo ), which represent the sets of controllable, uncontrollable, observable, and unobservable events, respectively. Intuitively, the supervisor only observes events in Σ o and only disables events in Σ c . Formally, it is a function S : P o (L(G)) → Γ, where P o is the natural event projection from Σ * to Σ * o extended to sets, and the set Γ is the set of admissible control decisions, i.e., Γ := {γ ∈ 2 Σ : Σ uc ⊆ γ}. Without loss of generality, we assume that S is realized by an automaton R = (X R , Σ, δ R , x 0,R ) (see, e.g., [START_REF] Cassandras | Introduction to Discrete Event Systems[END_REF]Lafortune 2008, Wonham and[START_REF] Wonham | Supervisory Control of Discrete-Event Systems[END_REF]). While the domain of events in R is Σ not Σ o , its transitions are only driven by observable events, i.e., transitions with unobservable events are self-loops. We use both notations S and R interchangeably throughout the paper. Example 1 We model the road intersection example depicted in Fig. 2(a), which will be used as a simple illustrative running example hereafter. The cars must cross the intersection without colliding with each other, or equivalently, both cannot be at the intersection at the same time. This system is modeled by the automaton G shown in Fig. 2(b). Every event is controllable and observable. The supervisor realization R that guarantees the above specification is obtained by deleting state 5. Events with B(lue) are related to car 1, while events with R(ed) are related to car 2.

Fig. 2. Intersection example

3 Robust Supervisory Control against Deception Attacks

Supervisory control under sensor deception attacks

Figure 1 pictorially describes deception attacks in the supervisory control framework, where the attacker intervenes in both communication channels. In the communication channel between the plant and the supervisor, the attacker has the ability to observe the same observable events as the supervisor. Even more, it has the ability to alter some of these observed events, where "alter" means that it can insert or delete events. The subset of affected sensor readings is denoted by Σ sen ⊆ Σ o , where only observable events can be compromised since unobservable events have no effect on the supervisor.

In the communication channel between the supervisor and the plant, the attacker has the ability of enabling/disabling some of the controllable events that are disabled/enabled by the current control decision. The subset of affected controllable events is denoted by Σ act ⊆ Σ c , where only controllable events can be compromised since uncontrollable events are always enabled by the supervisor.

First, we must characterize the closed-loop behavior of this controlled system under deception attacks. After this

Attacked control actions

Attacked observations Fig. 3. Attacked Controlled System characterization, we will formalize robustness against deception attacks. Our characterization follows similar lines as in [START_REF] Carvalho | Detection and mitigation of classes of attacks in supervisory control systems[END_REF][START_REF] Lima | Detectable and undetectable network attack security of cyber-physical systems[END_REF]. The conceptual diagram of deception attacks, as shown in Fig. 1, is transformed into an attacked controlled system depicted in Fig. 3. This attacked system is constructed based on the original controlled system and attacker assumptions.

Intuitively, the attacked plant is constructed by intertwining the possible attacker's sensor manipulations with the plant model. On the other hand, the attacked supervisor is built based on these possible sensor modifications as well as incorporating possible event enablements by the attacker. Combining both models characterize the closed-loop behavior under deception attacks.

Closed-loop system under deception attacks

Attacked plant

As was mentioned above, the attacked plant is constructed by intertwining the possible attacker's sensor manipulations with the plant model. Let us look at a concrete example of the construction of the attacked plant using G from Example 1 and Σ sen := {R int }. If we assume that the plant is at its initial state, state 1, then the plant can execute events B int or R int . Since we combine the attacker with the plant actions, the attacker can insert event R int in the communication channel before the plant executes event B int or R int . Lastly, when the plant executes R int , the attacker can delete this event from the communication channel.

Figure 4(a) depicts the above described transitions in state 1 of the attacked plant. Insertions are encoded by two transitions: transition from 1 to (1, R int ) with event R int,ins ; and transition from (1, R int ) to 1 with event R int . This encoding simulates the insertion of event R int in state 1 since the plant remains in the same state after the insertion. The sequence R int,ins R int uniquely identifies the insertion of event R int in the attacked plant, i.e., event R int,ins signals that the following event R int is inserted by the attacker. The reasoning behind this encoding becomes clear in the closedloop system as we will discuss it later. Intuitively, event R int,ins is defined to be unobservable, i.e., the supervisor cannot observe R int,ins . If the attacked plant executes the sequence R int,ins R int , the plant remains in state 1 while the supervisor will receive observation R int . As to ensure the correct encoding of this behavior, we must introduce the new state (1, R int ) to enforce the execution of event R int after event R int,ins occurs.

On the other hand, event R int,del identifies the execution and deletion of event R int . The deletion event is defined in parallel to transition R int since event R int must be executed by G in order to be deleted from the communication channel. Looking at the closed-loop system, event R int,del will also be unobservable to the supervisor. Therefore, if the attacked plant executes event R int,del , the plant moves to state 4 while the supervisor will not receive any information. Moreover, note that the attacked plant generates more behavior than the original plant since the attacked plant combines attacker actions with legitimate plant executions. Nevertheless, the attacked plant correctly captures the state evolution of the original plant while combining the attacker actions with legitimate plant executions. To formalize the definition of the attacked plant, we need to distinguish the attack actions from legitimate events generated by G, e.g., R int,ins and R int,del . Thus, we define the set of attacked events Σ att := Σ ins ∪ Σ del , where Σ ins := {e ins | e ∈ Σ sen } and Σ del := {e del | e ∈ Σ sen } denote insertion and deletion events, respectively. These sets are pairwise disjoint with Σ sen . We also define the operator M that removes the ins and del subscripts from events: M(e ins ) = M(e del ) := e for all e ∈ Σ sen and M(e) := e for all e ∈ Σ.

Based on Σ att , we augment the plant G with Σ att to create the attacked plant G a , i.e., G a is a copy of G with additional events Σ att and additional states. In the attacked plant G a , events e ins simulate the insertion ability of the attacker, whereas events e del simulate the deletion ability of the attacker. Formally, G a is defined as follow:

Definition 2 Given G and Σ sen , we define G a := (X Ga , Σ m , δ Ga , x 0,Ga ), where

X Ga := X G ∪ (X G × Σ sen ), Σ m := Σ ∪ Σ att , x 0,Ga := x 0,G and δ Ga (x, e) :=              δ G (x, M(e)) if x ∈ X G and e / ∈ Σ ins (x, M(e)) if x ∈ X G and e ∈ Σ ins x 1 if x = (x 1 , e 1 ), e = e 1 undefined otherwise (1)
To complete our encoding of G a , the unobservable event set in G a is defined as Σ m,uo := Σ uo ∪ Σ att . Unobservable events in G continue to be unobservable in G a . The attacker actions Σ att are also considered unobservable in our encoding since the supervisor does not observe them. Insertions events e ins can be considered unobservable since they are immediately followed by the observable event M(e ins ) = e in G a , e.g., 1

Rint,ins -----→ (1, R int ) Rint ---→ 1 in

Attacked supervisor

The construction of the attacked supervisor is similar to the construction of the attacked plant. However, we combine the possible attacker's actuator manipulations with the supervisor model. Moreover, the attacked supervisor is constructed for the attacked plant, which contains attacked events Σ att . For this reason, the attacked supervisor must include the set of attacked events Σ att defined in the previous section. First, we define the set of control patterns that a supervisor for G a must follow. This set is defined based on the set of compromised actuator events Σ act and the attacked event Σ att . Next, we augment the supervisor R based on this new set of control patterns to obtain the attacked supervisor R a .

As was defined in Section 3.1, the events in Σ act are the compromised actuator events, which the attacker can enable or disable at any given point. Disabling events can be advantageous for the attacker to better steer the plant to desired states, but it can only reduce the overall controlled behavior, i.e., it reduces the set of reachable states. Therefore, for the problem of synthesizing robust supervisors, it is sufficient to only consider actuator enablements [START_REF] Carvalho | Detection and mitigation of classes of attacks in supervisory control systems[END_REF]. In this manner, events in Σ act must be deemed as uncontrollable since the attacker can arbitrarily enable them.

Next, we introduce attacked events Σ att into the attacked supervisor model. These events cannot be directly controlled by the supervisor since the attacker decides when to attack. However, if a compromised event e ∈ Σ sen is controllable, then the supervisor can indirectly control the events in Σ att . For example, if event R int is disabled when the plant is in state 1, then the event R int,del is also disabled since event R int will not be executed. In the case of insertion events, for convenience and without loss of generality, we state the following assumption.

Assumption 3 The attacked supervisor enables insertion events if and only if it enables the corresponding legitimate event.

We could have assumed that the insertion of a disabled event is simply ignored by the supervisor, i.e., it does not change its state. Since inserting events also does not change the state of the plant (Def. 2), Assumption 3 does not reduce the power of the attacker, i.e., it is without loss of generality. Based on this assumption, the insertion of event R int also depends on the enablement of event R int . Therefore, if event e ∈ Σ sen is enabled, then it consequently enables events e ins and e del . Based on the above discussion, the control patterns C a is defined as:

C a ={γ ∈ 2 Σm | Σ uc ∪ Σ act ⊆ γ ∧ ((e ∈ γ ∩ Σ sen ) ⇔ (e ins , e del ∈ γ))} (2)
The condition Σ uc ∪ Σ act ⊆ γ implies that events in Σ act are treated as uncontrollable events. The second condition states that enabling an event in Σ sen implies enabling its insertion and deletion. Note that the set C a is closed under union, i.e., if γ 1 , γ 2 ∈ C a , then γ 1 ∪ γ 2 ∈ C a . The attacked supervisor R a is constructed such that it only emits control decisions in C a . Definition 4 Given R, Σ att and Σ act , we define the attacked supervisor R a := (X Ra , Σ m , δ Ra , x 0,Ra ), where X Ra := X R , x 0,Ra := x 0,R , and for e ∈ Σ m δ Ra (x, e) :=

       δ R (x, P m,o (e)) if M(e) ∈ En R (x) x if M(e) ∈ Σ act \ En R (x) undefined otherwise (3)
Let us look at a concrete example of the construction of the attacked supervisor using R from Example 1, Σ sen := {R int }, and Σ act = {R out }. Figure 4(b) depicts all transitions defined by Eq. ( 3) in state 1 of the attacked supervisor. The first condition in Eq. ( 3) states that if a compromised event e ∈ Σ sen is enabled in state x ∈ X R , then e, e ins , and e del are enabled in x ∈ X Ra . In Fig. 4(b), events R int,ins , R int,del are defined as self-loops in state 1, i.e.,

δ Ra (1, R int,ins ) = δ R (1, P m,o (R int,ins )) = δ R (1, ǫ) = 1, On the other hand, event R int in state 1 is defined as in R, i.e., δ Ra (1, R int ) = δ R (1, P m,o (R int )) = δ R (1, R int ) = 4.
If the event is not compromised, then only this event is enabled in R a , as for event B int in Fig. 4(b). The second condition in Eq. ( 3) guarantees that compromised actuator events are always enabled in R a , i.e., event R out is defined as a self-loop in state 1 of the attacked supervisor. In this manner, supervisor R a is a copy of R with additional selfloops based on Σ att and Σ act .

Closed-loop system

The definition of the control pattern set C a goes hand in hand with the attacked plant encoding. To execute the sequence R int,ins R int , the supervisor enables events R int,ins and R int (State 1 in Fig. 4b). After the execution, the supervisor moves to state 2 in Fig. 4b, i.e., as if it had observed event R int . On the other hand, the attacked plant goes through state (1, R int ) and reaches state 1 after the sequence R int,ins R int in Fig. 4a, i.e., the plant remains in state 1 after the attacker insertion. Event deletion happens in a similar way.

In this manner, the closed-loop system under deception attacks is captured by the parallel composition of G a ||R a , where || is the parallel composition operator as in [START_REF] Cassandras | Introduction to Discrete Event Systems[END_REF]. Since R a is a supervisor realization, the closed-loop system under deception attacks is also denoted by R a /G a . The language L(R a /G a ) generated by this system is defined as the usual closed-loop language of the supervised system. Remark 5 The definitions of G a and R a are based on the worst-case attack scenario in which the attacker can attack whenever it is possible. This attack strategy introduced in [START_REF] Carvalho | Detection and mitigation of classes of attacks in supervisory control systems[END_REF][START_REF] Lima | Detectable and undetectable network attack security of cyber-physical systems[END_REF]) is called the "allout" attack strategy. Although this model is simple, it is wellsuited to the problem we are investigating since we want to design a supervisor that is robust against any deception attack. At the end of this section, we generalize our closedloop behavior based on prior attack knowledge.

Supervisor robust against deception attacks

We assume that the plant G contains a set of critical states defined as X crit ⊂ X G ; these states are unsafe in the sense that they are states where damage to the plant might occur. Although damage is defined in relation to the set X crit , it could be generalized in relation to any regular language by state space refinement in the usual way [START_REF] Cho | On supremal languages of classes of sublanguages that arise in supervisor synthesis problems with partial observation[END_REF]Marcus 1989, Cassandras and[START_REF] Cassandras | Introduction to Discrete Event Systems[END_REF]. Since X G ⊂ X Ga and with an abuse of notation, we say that X crit defines the critical states of G a . Definition 6 Given plant G, X crit , supervisor R, and sets Σ sen , Σ act , we say that R is robust with respect to G and

(Σ act , Σ sen ) if δ Ga (x 0 , s) / ∈ X crit for any s ∈ L(R a /G a ).

Prior attack knowledge

In the previous section, we defined the attacked behavior based on the "all-out" attack strategy. We now relax this assumption based on some prior knowledge of the attack strategy used by an attacker. We only restrict the attacker based on a sensor deception attack strategy, and we leave restricting actuator attacks for future work. Using such knowledge, we can build the attacked plant similarly as it was built for the "all-out" attack strategy. Namely, we need to modify the construction of the attacked plant G a . However, the construction of R a remains the same as before.

There are different ways of describing attack strategies. We assume that the known attack strategy is encoded as an automaton A = (X A , δ A , Σ m , x 0,A ) as in [START_REF] Meira-Góes | Synthesis of sensor deception attacks at the supervisory layer of cyber-physical systems[END_REF], Meira-Góes et al. 2021d). If automaton A correctly encodes the attack strategy, then we can restrict G a as defined in Def. 2 based on A, i.e., G ′ a := G a ||A. In this manner, the attacked system is defined by G ′ a := G a ||A and R a is as in Def. 4.

We give one example of an attack strategy to demonstrate how G ′ a is constructed. The automaton in Fig. 6 encodes an attack strategy where the attacker deletes at most one event. The attacker is initialized in state 1, where it has not performed any deletion. In state 1, the attacker can observe legitimate events (self-loop with Σ) or it can delete an event (transition 1

Σ del ---→ 2).
Once the attacker deletes one event, it moves to state 2, where it only observes legitimate events. In the rest of the paper, we present our results for G a as defined in Def. 2. However, these results are applicable to G ′ a constructed based on a known attack strategy A by simply replacing G a by G ′ a . Remark 9 In [START_REF] Lin | Towards bounded synthesis of resilient supervisors[END_REF], attack strategies are constrained based on prior knowledge of the attack strategy. However, their techniques to constrain actuator attacks do not apply to our framework since they reduce the robustness problem to a quantified Boolean formula problem. Moreover, sensor attacks are restrained to sensor replacement attacks.

Solution of the Robust Supervisory Control Problem

Supervisory control with arbitrary control patterns

As described in the definition of the attacked supervisor, the supervisor for the attacked plant must select its control decision based on the set of control patterns C a , i.e., a supervisor for the attacked plant is defined as S : Σ * o → C a . This supervisor is more constrained compared to the general supervisor defined in Section 2, in which the supervisor leverages the entire set of feasible control decisions. For this reason, prior results from supervisory control theory with arbitrary control patterns are essential for our proposed framework [START_REF] Golaszewski | Control of discrete event processes with forced events[END_REF][START_REF] Li | A generalized framework for supervisory control of discrete event systems[END_REF][START_REF] Takai | Supervisory control of partially observed discrete event systems with arbitrary control patterns[END_REF]. We state these results for the attacked plant G a and the set of control patterns C a .

Proposition 10 (Takai 2000) Let K ⊆ L(G a ) be a nonempty and prefix-closed language and let C a be the available control patterns set. There exists a supervisor S : P m,o (L(G a )) → C a such that L(S/G a ) = K if and only if K satisfies the following condition:

(∀s ∈ K)(∃γ ∈ C a )(∀t ∈ P -1 m,o [P m,o (s)] ∩ K) s.t. γ ∩ Σ L(Ga) (t) = Σ K (t)
where P -1 m,o is the inverse projection operator and Σ K (s) := {e ∈ Σ m | se ∈ K} is the one event continuation from s ∈ K.

Proposition 10 reduces to the standard controllability and observability conditions when C a = {γ ∈ 2 Σm | Σ uc ∪ Σ act ⊆ γ} (Takai 2000, Cassandras and[START_REF] Cassandras | Introduction to Discrete Event Systems[END_REF]. When K does not satisfy Proposition 10 given the set C a , the set

CO(K, C a ) = {K ′ ⊆ L(G a ) | K ′ = pr(K ′ ) ⊆ K s.t. K ′ satisfies
Proposition 10} is defined. This set is non-empty since ∅ ∈ CO(K, C a ). As in the standard partial observation supervisory control problem, there does not exist in general a supremal element in CO(K, C a ) [START_REF] Takai | Supervisory control of partially observed discrete event systems with arbitrary control patterns[END_REF].

Existence of solution for the RSS problem

Our definition of robustness against deception attacks, Def. 6, focuses exclusively on the language L(R a /G a ), which is the language of the attacked system. Therefore, this language becomes the center of our study, where we search for a supervisor for the attacked plant G a such that the controlled attack system satisfies the robustness property. Here, we investigate G a in the supervisory control framework with arbitrary control patterns C a and observable event set Σ o .

Let K spec := L(Ac(G a , X crit )) be the language specification on L(G a ), where Ac(G a , X crit ) is the accessible subautomaton of G a after deleting states X crit ⊂ X Ga . From [START_REF] Takai | Supervisory control of partially observed discrete event systems with arbitrary control patterns[END_REF], it follows that for any Definition 11 Let the supervisor R a satisfy L(R a /G a ) ∈ CO(K spec , C a ). Build supervisor R := (X R , Σ, δ R , x 0,R ), where X R := X Ra , x 0,R := x 0,Ra , and δ R (x, e) := δ Ra (x, e) for e ∈ Σ and x ∈ X R , i.e., δ R is δ Ra restricted to events in Σ.

K ′ ∈ CO(K spec , C a ), if K ′ = ∅,
Definition 11 constructs the supervisor R by simply removing events in Σ att from R a . The transitions with events in Σ att on R a are self-loops since they are unobservable in the attacked plant G a . Therefore, Def. 11 is the "inverse construction" of Def. 4.

Robust supervisors with respect to G, X crit , and (Σ act , Σ sen ) are directly related to supervisors R a such that L(R a /G a ) ∈ CO(K spec , C a ). Intuitively, if a supervisor R is robust, then the language L(R a /G a ) ∈ CO(K spec , C a ), where R a is constructed via Def. 4. On the other hand, let R a be a supervisor such that L(R a /G a ) ∈ CO(K spec , C a ), then the supervisor R constructed via Def. 11 is robust. The following theorem formally states this connection.

Theorem 12 A supervisor R is robust w.r.t. G, X crit , and (Σ act , Σ sen ) if and only if L(R a /G a ) ∈ CO(K spec , C a ).

Proof. We start with the only if part. Assuming that R is robust w.r.t. G and (Σ act , Σ sen ), we need to show that L(R a /G a ) ∈ CO(K spec , C a ), where R a is constructed via Def. 4. In other words, we need to show that L(R a /G a ) ⊆ K spec and satisfies Prop. 10. We show this result directly by constructing the language L(R a /G a ). Language K * := L(R a /G a ) is a subset of K spec since R is robust w.r.t. (Σ act , Σ sen ), i.e., no string in K * reaches the critical states. Next, every control decision in R a satisfies by construction the set of control patterns in C a . We just need to show that for any s ∈ K * , there exists γ ∈ C a such that γ∩Σ L(Ga) (t) = Σ K * (t) for any t ∈ P -1 m,o [P m,o (s)]∩K * (as stated in Prop. 10). Let γ := En Ra (δ Ra (x 0,Ra , P m,o (t))) so that we compare both sides of the equation. Note that, δ Ra (x 0,Ra , P m,o (t)) is well defined since s ∈ K * and P m,o (s) = P m,o (t). In the right hand side, by definition of the controlled language L(R a /G a ), e ∈ Σ K * (t) if and only if t ∈ K * = L(R a /G a ), e ∈ γ, and te ∈ L(G a ). Since we assumed that t ∈ P -1 m,o [P m,o (s)] ∩ K * , then e ∈ Σ K * (t) if and only if e ∈ γ and te ∈ L(G a ). On the left hand side, e ∈ γ ∩ Σ L(Ga) (t) if and only if t ∈ L(G a ), e ∈ γ, and te ∈ L(G a ). Again, since we assumed that

t ∈ P -1 m,o [P m,o (s)] ∩ K * ⊆ L(G a ), then e ∈ γ ∩ Σ L(Ga) if and only if e ∈ γ and te ∈ L(G a ). It follows that γ ∩ Σ L(Ga) (t) = Σ K * (t).
We now show the if part. We assume that L(R a /G a ) ∈ CO(K spec , C a ) and prove that R constructed via Def. 11 is robust with respect to (Σ act , Σ sen ). By definition of CO(K spec , C a ), it follows that of L(R a /G a ) ⊆ K spec . Since L(R a /G a ) ⊆ K spec , the critical states in G a are unreachable by any s ∈ L(R a /G a ). Therefore, R is a robust supervisor with respect to (Σ act , Σ sen ).

Theorem 12 provides a set of sufficient and necessary conditions for existence of a solution for our RSS problem. In words, there exists a robust supervisor if and only if there exists a supervisor R a such that L(R a /G a ) ∈ CO(K spec , C a ). Corollary 13 clearly states this result. Corollary 13 There exists a solution for the RSS problem if and only if CO(K spec , C a ) = {∅}.

Theorem 12 also states one way of obtaining a solution for the RSS problem, when one exists. A solution can be obtained by constructing the set CO(K spec , C a ) or constructing specific elements in CO(K spec , C a ). However, no algorithm to construct supervisors in CO(K spec , C a ) is described in [START_REF] Takai | Supervisory control of partially observed discrete event systems with arbitrary control patterns[END_REF]. For this reason, we discuss two methods to obtain solutions of the RSS problem based on the set CO(K spec , C a ) in Section 5.

Sufficient condition for the existence of the supremal robust supervisor

In the previous sections, we showed how to solve the general problem of synthesizing robust supervisors. Since there does not exist in general a supremal supervisor for this problem, we investigate sufficient conditions for the existence of such a supremal robust supervisor.

The first condition, also known as normality condition, is well known in the partially observed supervisory control problem: Σ c ⊆ Σ o . When Σ c ⊆ Σ o , it follows that the observability plus the controllability conditions imply the normality condition [START_REF] Cassandras | Introduction to Discrete Event Systems[END_REF]. Since the supremal controllable and normal sublanguage always exists, then, with this condition imposed, the supremal controllable and observable sublanguage also exists. Recall that, in the case of G a , the events in Σ act are treated as uncontrollable. Therefore, the above condition is Σ c \ Σ act ⊆ Σ o . However, this condition is not enough to guarantee the existence of the supremal robust supervisor. In fact, our running example demonstrates the nonexistence of a supremal element even when Σ c \ Σ act ⊆ Σ o as we will see in Section 5.

In cyber-physical system models, we normally assign actuators signals to be controllable and observable events while sensors signals are uncontrollable and observable. Since we study sensor deception attacks, let us assume that the set of affected sensor events is a subset of the uncontrollable events, besides being a subset of observable events. Thus, the second condition is

Σ sen ⊆ Σ o ∩ Σ uc . Theorem 14 If Σ c \ Σ act ⊆ Σ o and Σ sen ⊆ Σ uc ∩ Σ o , then there exists a supremal element K ↑ ∈ CO(K spec , C a ) and supervisor R a such that K ↑ = L(R a /G a ).

Computing Robust Supervisors

Herein, we discuss two methods to compute robust supervisors. Due to space limitations, the complete discussion on these methods is described in (Meira-Góes et al. 2021a).

Computing a Maximal Robust Supervisor

In order to synthesize a robust supervisor, Corollary 13 states that we can select any supervisor R a that satisfies L(R a /G a ) ∈ CO(K spec , C a ). Since the supremal element of CO(K spec , C a ) does not exist in general, we search for a supervisor that generates a maximal language in CO(K spec , C a ). A maximal language L ∈ CO(K spec , C a ) satisfies:

∄L ′ ∈ CO(K spec , C a ) such that L ⊂ L ′ .
We can adapt standard algorithms that compute maximal controllable and observable sublanguages to consider control patterns. For example, the VLP-PO algorithm from [START_REF] Hadj-Alouane | Centralized and distributed algorithms for on-line synthesis of maximal control policies under partial observation[END_REF] can be adapted such that it considers control patterns. Intuitively, the only difference between modified VLP-PO algorithm and the VLP-PO algorithm presented in [START_REF] Hadj-Alouane | Centralized and distributed algorithms for on-line synthesis of maximal control policies under partial observation[END_REF] is that the latter selects control decisions from the set of all possible feasible control decisions, i.e., {γ ∈ 2 Σm | Σ uc ∪ Σ act ⊆ γ}, where the former will select control decisions from C a . For this reason, the modified algorithm guarantees the same results as the VLP-PO algorithm, e.g., correctness and complexity.

Finding all Robust Supervisors

Although the modified VLP-PO algorithm provides some flexibility on the computation of robust supervisors through the event ordering of the controllable events, it limits its search to computing maximal robust supervisors for each ordering. For this reason, we would like to investigate an algorithm that would provide more flexibility for synthesizing robust supervisors.

In [START_REF] Yin | A uniform approach for synthesizing property-enforcing supervisors for partially-observed discrete-event systems[END_REF]Lafortune 2016, Meira-Góes et al. 2021b), a uniform approach for synthesizing all state-based propertyenforcing supervisors for partially observed DES is presented. Their method constructs a finite bipartite transition systems, called All Enforcement Structure (AES), which embeds all admissible supervisors that enforce a desired statebased property. Our definition of robustness, Def. 6, is a state-based property in G a . Thus, we can alter the original AES construction to adapt it to the set C a and obtain the "modified AES"; full details are presented in (Meira-Góes et al. 2021a). The modified AES guarantees the same results as the original AES, e.g., correctness and complexity.

Example 15 Back to the intersection example, we calculate two maximal robust supervisors. Recall that we have defined Σ sen = {R int } and Σ act = {R out }. We construct the attacked plant based on Def. 2, where G a has 18 states since G has 9 states and Σ sen = {R int }. At this point, we want to enforce that the critical state 5 is not reachable, i.e., the specification is defined by automaton Ac(G a , {5}). We can use either the modified VLP-PO or the modified AES algorithms to obtain these supervisors. These two supervisors are shown in Fig. 7. Note that whenever R int is enabled, then both R int,ins and R int,del are enabled. Moreover, the event R out is enabled in every state of both supervisors. Therefore, the control pattern constraint is satisfied. We obtain a robust supervisor for G by removing events Σ att from the supervisors in Fig. 7, according to Def. 11. We have considered a class of problems in cyber-security where sensor readings and actuator commands in a feedback control system may be manipulated by a malicious attacker. We leverage techniques from supervisory control of partially-observed discrete event systems, with arbitrary control patterns, to develop a solution methodology to prevent damage to the system when some sensor readings and actuator commands may be edited by the attacker. We showed how this problem can be reduced to a partially observed supervisory control problem with a specific class of control patterns. Then, we provided two different algorithms to obtain these robust supervisors. In Section 3, we only introduced restrictions to sensor attacks when prior knowledge is available, but we left actuator attacks restrictions to future work. We believe that it will be possible to restrict actuator attacks using control patterns and maintain the separation between sensor and actuator constraints. Synthesizing nonblocking robust supervisors is a potential extension of our work. The problem of synthesizing nonblocking supervisors with arbitrary control patterns is still an open problem, as the results in [START_REF] Takai | Supervisory control of partially observed discrete event systems with arbitrary control patterns[END_REF] only tackle prefix-closed specifications.

Fig. 1 .

 1 Fig. 1. Deception attack framework

  (a) Intersection with two cars (b) Road intersection model.

  Fig. 4. Attacked plant and attacked supervisor

  Fig. 4(a) . Fi-nally, the natural string projection function P m,o projects strings in Σ * m to Σ * o , i.e., P m,o : Σ * m → Σ * o .

Finally

  , we are able to formally pose the Synthesis of Robust Supervisor Problem. Problem 7 (RSS-Robust Supervisor Synthesis) Given plant G, X crit , and sets Σ sen ⊆ Σ o , Σ act ⊆ Σ c , synthesize a robust supervisor R with respect to (Σ act , Σ sen ), if one exists.Example 8 Let us return to our intersection example, where we assume that Σ sen = {R int } and Σ act = {R out }. Using G and R as given in Example 1, we construct the pair G a and R a . Based on them, we obtain the attacked system R a /G a shown in Fig.5. The string s = R int,del B int , in red in Fig.5, is feasible in R a /G a and takes G a to state 5. Therefore, this supervisor is not robust with respect to Σ sen = {R int } and Σ act = {R out }.

Fig. 5 .

 5 Fig. 5. The attacked controlled system for Ra/Ga

Fig. 6 .

 6 Fig. 6. One deletion attack strategy

  there exists a supervisor S : P m,o (L(G a )) → C a such that L(S/G a ) = K ′ . Since the languages L(G a ) and K spec are regular languages, without loss of generality we assume that the supervisor S : P m,o (L(G a )) → C a such that L(S/G a ) ∈ CO(K spec , C a ) is encoded by a DFA R a .

  Fig. 7. Two robust supervisors for the intersection example


Joris Guérin
email: joris.guerin@ird.fr

Kevin Delmas
email: kevin.delmas@onera.fr

Raul Sena Ferreira

Jérémie Guiochet
email: jeremie.guiochet@laas.fr

Out-Of-Distribution Detection Is Not All You Need

The usage of deep neural networks in safety-critical systems is limited by our ability to guarantee their correct behavior. Runtime monitors are components aiming to identify unsafe predictions and discard them before they can lead to catastrophic consequences. Several recent works on runtime monitoring have focused on out-of-distribution (OOD) detection, i.e., identifying inputs that are different from the training data. In this work, we argue that OOD detection is not a well-suited framework to design efficient runtime monitors and that it is more relevant to evaluate monitors based on their ability to discard incorrect predictions. We call this setting out-ofmodel-scope detection and discuss the conceptual differences with OOD. We also conduct extensive experiments on popular datasets from the literature to show that studying monitors in the OOD setting can be misleading: 1. very good OOD results can give a false impression of safety, 2. comparison under the OOD setting does not allow identifying the best monitor to detect errors. Finally, we also show that removing erroneous training data samples helps to train better monitors.

Introduction

With the recent progress in machine learning (ML) research, deep neural network (DNN) architectures are now used to address safety-critical tasks, e.g., self-driving cars [START_REF] Stocco | Misbehaviour prediction for autonomous driving systems[END_REF], surgical robots [START_REF] Haidegger | Autonomy for surgical robots: Concepts and paradigms[END_REF], drones landing (Guerin, Delmas, and Guiochet 2022). Online fault tolerance approaches, or runtime monitors, are promising research directions to improve the safety of such systems. A runtime monitor is a component aiming to identify and reject unsafe data encountered at inference time. As in most of the recent literature, this paper focuses on the unsupervised setting, where we do not have access to examples of "unsafe input data" during monitor training. In other words, to separate safe data instances from unsafe ones, we need to fit a one-class classifier [START_REF] Khan | One-class classification: taxonomy of study and review of techniques[END_REF] using only the DNN training dataset. Figure 1 illustrates the life cycle of a DNN runtime monitor (training and inference phases).

Many approaches have been proposed to tackle the DNN runtime monitoring problem defined above. However, in the literature, they are found under different names as they adopt different definitions of "unsafe data instances". On the one hand, the field of Out-Of-Distribution (OOD) detection aims at identifying input data that are not from the training distribution [START_REF] Wang | ViM: Out-Of-Distribution with Virtual-logit Matching[END_REF][START_REF] Sun | React: Out-of-distribution detection with rectified activations[END_REF][START_REF] Schorn | FACER: A universal framework for detecting anomalous operation of deep neural networks[END_REF]. On the other, several works consider directly the problem of identifying input data that lead to errors of the monitored DNN [START_REF] Granese | DOCTOR: A Simple Method for Detecting Misclassification Errors[END_REF][START_REF] Wang | Dissector: Input validation for deep learning applications by crossing-layer dissection[END_REF][START_REF] Kang | Model assertions for debugging machine learning[END_REF]. In this work, we name this second view Out-of-Model-Scope (OMS) detection. In practice, the approaches to address OOD and OMS detection are not different and follow the same workflow: they use the DNN training dataset to build a one-class classifier (the monitor) to characterize safe data instances and use it to reject unsafe samples (Figure 1). These two paradigms only differ in their objectives (definition of normal data samples), and by extension in how new approaches are evaluated. We emphasize that OOD and OMS are evaluation settings and not monitoring approaches per se.

In this work, we claim that the real goal of a DNN runtime monitor is to tackle the OMS problem, i.e., to identify prediction errors before they can propagate through the system. We argue that OOD detection was designed as a proxy task for OMS detection, based on the belief that what the DNN knows is equivalent to the information contained in the dataset that was used to train it. The first objective of this paper is to discuss the conceptual differences between the OOD and OMS detection settings. Then, we conduct experiments to determine whether OOD detection is a good proxy for OMS detection. In other words, we want to know whether the OMS performance of a runtime monitor can be correctly assessed under the OOD setting. Finally, based on the insights gained from these discussions, we formalize a good practice to train better monitors. We show experimentally that, when fitting the monitor, it is better to remove erroneous samples from the DNN training dataset.

This paper is organized as follows. In section 2, notations are introduced and the concepts of OMS and OOD are clearly defined. In section 3, we present the existing literature about OMS and OOD detection. In section 4, we discuss the differences between OOD and OMS and explain why the OOD setting can lead to an inaccurate perceived performance of a monitor. In section 5, we conduct experiments to verify whether these limitations of OOD detection actually occur in practical scenarios. Finally, in section 6, we introduce a new training trick to build better monitors.

Notations and definitions

Let T be an ML task, defined by an oracle function Ω, on a domain X , i.e., ∀x ∈ X , the ground-truth for T is Ω(x). This work mostly discusses classification, but could easily be extended to other ML tasks. Let f be a DNN used to solve T , and let m f be a monitor of f , i.e., a one-class classifier used during inference to reject unsafe predictions of f .

The Out-of-Model-Scope detection setting

We define the scope of f , D f , to be the set of data instances where f is correct:

D f = {x ∈ X | f (x) = Ω(x)}
(1) Ideally, we want m f to identify data points that lead to errors of f . The perfect monitor for f , noted m * f , is defined by

∀x ∈ X , m * f (x) = 0 if x ∈ D f , 1 else. (2)
We call Out-of-Model-Scope (OMS) detection, the task of designing a monitor that reproduces the behavior of m * f . OMS detection is defined with respect to a specific model f . Indeed, if another neural network f (different architecture or weights) is used, the model scope will likely be different (D f = D f ), and so will the optimal monitor (m * f = m * f ).

The Out-Of-Distribution detection setting

In practice, the monitored DNN f is trained using a supervised training dataset, i.e., a small subset of n data points in X for which the ground truth is known:

D train = {(x i , y i ) | ∀i ∈ {1, ...n} x i ∈ X , y i = Ω(x i )}.
A common practice for DNN monitoring is to define an indistribution domain D ID , that comprises all data instances drawn from the same distribution as D train . The Out-Of-Distribution (OOD) detection task aims to build a monitor m to identify data instances that do not belong to D ID , i.e., the perfect OOD monitor (m * ) is defined by

∀x ∈ X , m * (x) = 0 if x ∈ D ID , 1 else. ( 3
)
The rationale behind OOD detection is that DNNs trained on D train must be good for input data similar to D train (x ∈ D ID ), but should not perform well on other data (x / ∈ D ID ). The evaluations conducted in the OOD setting are independent of f , they only depend on the task and training dataset.

Related works

This section presents several monitoring approaches. Conceptually, OOD and OMS detectors are not different, i.e., one-class classifiers fitted to D train , usually using feature representations extracted from f (Figure 1). However, in practice, they differ in the way they are evaluated experimentally.

OMS in the literature

Several previous works have studied the problem of OMS detection, i.e., they developed DNN runtime monitoring approaches and assessed their performance based on their ability to detect errors of f . [START_REF] Granese | DOCTOR: A Simple Method for Detecting Misclassification Errors[END_REF] developed a monitor called DOCTOR, which computes an optimal rejection score based on the softmax vector returned by f . [START_REF] Wang | Dissector: Input validation for deep learning applications by crossing-layer dissection[END_REF] proposed a monitor called DISSECTOR, which rejects inputs with incoherent activations among different layers of f . The monitor proposed by [START_REF] Kang | Model assertions for debugging machine learning[END_REF] is specific to object detection. They developed a model assertion technique to specify constraints on the shape of the predicted bounding boxes. [START_REF] Cheng | Runtime monitoring neuron activation patterns[END_REF] proposed to store neuron activations of D train in the form of binary decision diagrams, and reject patterns that were not seen previously.

OOD detection in the literature

The definition of OOD in equation 3 is frequently seen in the literature. However, the boundaries of D ID are fuzzy and there is no clear definition of whether a data point was drawn from the same distribution as D train . To overcome this issue, OOD detection works consider that the test split associated with D train belongs to D ID . Then, different approaches exist to construct OOD sets, and the monitors are evaluated based on their ability to distinguish whether a data point is from the test set or the OOD set. In the literature, three main concepts of "OODness" are used to build OOD datasets.

Novelty A data point x ∈ X is OOD if the ground-truth Ω(x) is not among the predefined classes handled by f , i.e., f cannot be correct (e.g., an image of a frog presented to a cat vs. dog classifier). A large body of works was developed and evaluated in this configuration. [START_REF] Liang | Enhancing The Reliability of Out-of-distribution Image Detection in Neural Networks[END_REF] proposed ODIN, an approach using input preprocessing and temperature scaling on the softmax outputs to maximize ID/OOD separation. [START_REF] Liu | Energy-based out-of-distribution detection[END_REF] proposed an en-ergy score (logsumexp of the logits) to detect OOD data. [START_REF] Sun | React: Out-of-distribution detection with rectified activations[END_REF] showed that clipping the highest values of the last layer can help to build better logits for OOD detection. Their approach is called ReAct and can be combined with any logits-based scores. [START_REF] Lee | A simple unified framework for detecting out-of-distribution samples and adversarial attacks[END_REF] proposed to fit Gaussian distributions to features extracted from f , and to use the Mahalanobis distance as an OOD score. All the above approaches used another dataset, with disjoint label classes, as the OOD set. Another idea to build OOD sets is to remove data samples from certain classes while training f and m f , and use them as OOD examples to test the monitor. This was done by [START_REF] Henzinger | Outside the Box: Abstraction-Based Monitoring of Neural Networks[END_REF], who developed a monitor called Outsidethe-Box, using the smallest bounding boxes containing all features representing D train to model the boundary of D ID .

Covariate shift OOD data instances present different characteristics than D train , but with valid ground-truth. Covariate shift comes from changes in external conditions, sensor failures, or modifications to the environment. Such threats to DNN safety were discussed extensively by [START_REF] Hendrycks | Benchmarking Neural Network Robustness to Common Corruptions and Perturbations[END_REF]. Most works dealing with covariate shift detection have built OOD sets by injecting perturbations to test images. [START_REF] Schorn | FACER: A universal framework for detecting anomalous operation of deep neural networks[END_REF] injected different kinds of noise patterns and evaluated their monitor called FACER. Cai and Koutsoukos (2020) used a variational auto-encoder and anomaly detection to detect abnormal rain conditions (injected in simulation). Chen, Yoon, and Shao (2020) applied brightness changes to the test images to build an OOD set to test their approach. Finally, [START_REF] Zhang | DeepRoad: GAN-based metamorphic testing and input validation framework for autonomous driving systems[END_REF] used distances in the feature space of a DNN to separate sunny images (used for training) from rainy or snowy images (from YouTube).

Adversarial attack A data sample that was modified to make a DNN fail with high confidence. The difference with covariate shift is in the malicious intent to generate imperceptible perturbations. Several works presented above also tested their approaches for adversarial attack detection. In addition, [START_REF] Kantaros | Real-time detectors for digital and physical adversarial inputs to perception systems[END_REF] proposed to detect adversarial attacks by testing the robustness of a prediction against input image transformations. Similarly, [START_REF] Wang | Adversarial sample detection for deep neural network through model mutation testing[END_REF] considered the robustness against random mutations of f . They also reported the OMS detection performance. However, in both of these papers, OOD and OMS are simply viewed as separate problems. Here, we consider that OOD is simply a proxy for OMS, and we discuss whether both paradigms are useful for the field of DNN monitoring.

Approaches considering both OMS and OOD

Limitations of OOD detection

In this work, we claim that a successful runtime monitor m f should perform well under the OMS setting, i.e., reject data samples that correspond to errors of f , and accept others. DNNs are usually good on their training dataset (train, validation, and test splits), while their performance decreases when data move away from D train [START_REF] Hendrycks | Benchmarking Neural Network Robustness to Common Corruptions and Perturbations[END_REF]. These two facts gave rise to the highly studied problem of OOD detection, aiming to reject samples that are far from the training distribution. Studying the alternate OOD detection problem in place of OMS detection presents several conceptual issues, which are highlighted in this section.

The definition of OOD is ambiguous

The first issue with OOD detection is that D ID is not welldefined. Figure 2 shows examples of brightness covariate shifts to illustrate this problem. Here, it is not clear how to set a threshold on the perturbation factor to define OODness. At a perturbation level of 2, the accuracy of f has dropped about 13%, but it can still produce above 80% of correct predictions. Hence, should the second column be considered OOD? This limitation also applies to adversarial examples, as different attacks lead to different levels of performance drop. For example, if we can generate a few additional misclassifications by changing random pixels, is it an adversarial attack? Regarding novelty detection, the problem is better defined: an image is OOD if its label is not among the output classes handled by f (e.g., an image of a dinosaur is clearly OOD for CIFAR10). However, it is not easy to decide whether a highly corrupted image should hold its label. In figure 2, is the last image of the fourth row still a dog?

There is no simple answer to the questions raised in the previous paragraph. As a matter of fact, [START_REF] Balestriero | Learning in high dimension always amounts to extrapolation[END_REF] showed that for high-dimensional data spaces, such as images, interpolation almost never happens. Even test data, which are traditionally considered ID, are not in the convex hull of D train and require extrapolation capabilities of f . In other words, the only data samples that are unambiguously ID are the training data themselves. This way, building an OOD evaluation dataset requires making subjective choices regarding the definition of OODness.

Recently, [START_REF] Wang | ViM: Out-Of-Distribution with Virtual-logit Matching[END_REF] attempted to build a less ambiguous OOD benchmark dataset by asking two independent human annotators to label OOD images for ImageNet. The resulting OOD set contains all images labeled as OOD by both annotators. Unfortunately, this approach does not really solve the problem, as difficult images for humans are not necessarily what the DNN will struggle to process. In addition, even if this dataset is actually difficult for f , how can we know that it is not too simple for m f ? What about images that are less clearly OOD?

A less ambiguous way to discuss the concept of OOD is to use ideas from the field of DNN calibration [START_REF] Guo | On calibration of modern neural networks[END_REF]): a set of images is OOD if the accuracy of f falls below a fixed user-defined threshold on this set. This definition is still threshold dependent, but it describes OODness unambiguously. However, under this definition, OODness depends on f and is a property of a set, not defined at the individual sample level. This definition could be used to detect a performance drop over time by evaluating the OOD rate in consecutive data, but it is a different problem than the one studied in most OOD detection works.

OOD does not always represent OMS

Even if we had access to an unambiguous boundary of D ID , OOD and OMS detection would still remain distinct problems. In the schematic representation of figure 3, we can see that D ID and D f can differ in two different ways.

Model generalization

The first difference, represented by the light blue region, is when input data are OOD but correctly classified by f (e.g., the top-right image of figure 2). The limits of the ID domain are often defined by human programmers, independently of the generalization capabilities of f . For such cases, a good OOD monitor will reject perfectly valid inputs (false positives), thus decreasing the availability1 of the model f . For the special case of novelty detection, this region does not exist because the model cannot be correct on data representing novel classes.

In-distribution errors

The second difference between OOD and OMS lies in the orange region in figure 3. Indistribution errors are data samples that are similar to training data, but that are misclassified by f (e.g., the bottom-left image of figure 2). Such cases can have catastrophic outcomes for safety-critical applications, since if an OOD monitor accepts wrong predictions as long as they are similar to D train , it also let hazardous predictions through the system (false negatives) and decreases its safety. This problem is an issue even when considering novelty detection.

Furthermore, it is counter-productive to expect a monitor to accept misclassified training data. If a data sample is misclassified, its representation by the DNN is likely not similar to other representatives of its class, and forcing the monitor to say otherwise does not make sense.

Switching to OMS

The above discussion showed that it is hard to come up with an objective definition of what OOD means, and that building good OOD monitors might not be sufficient to ensure the safety of a system using a DNN. The good news is that such a definition is not necessary, as we can simply use OMS as a generic setting for studying DNN runtime monitoring. The OMS paradigm is defined unambiguously and actually corresponds to what we want to achieve, i.e., reject wrong predictions of f . In practice, it is common to define a proxy task (here OOD detection) to address a more complex generic task of interest (OMS detection). However, when the actual performance at the true task is easy to compute, we should use it to evaluate the performance of new techniques. In our case, computing OMS detection performance is easy as we have access to labeled datasets and we can compute the predictions of f . For these reasons, we argue that DNN runtime monitors should be evaluated with respect to the OMS setting, instead of the ambiguous OOD setting.

Experimental validation

So far, we have argued that if the ultimate goal is to increase DNN safety, we should always evaluate runtime monitors under the OMS setting. However, many recent works have reported the performance of their approaches under the OOD setting (Section 3.2). In this section, we conduct experiments on common OOD datasets from the literature, to see whether analyzing OOD results can lead to misleading conclusions about the safety of the system.

Experiments description

Our experiments consist of 27 OOD datasets, 2 DNN architectures (54 OOD scenarios), and 6 monitoring approaches.

We use three popular image datasets as ID: CIFAR10, CI-FAR100, and SVHN [START_REF] Krizhevsky | Learning multiple layers of features from tiny images[END_REF][START_REF] Netzer | Reading Digits in Natural Images with Unsupervised Feature Learning[END_REF]. For each ID dataset, the train split is used to fit the monitors, while the test split serves as the ID set for evaluation. Each ID set is combined with 9 distinct OOD sets:

• Three novelty tasks -For CIFAR10 we use CIFAR100, SVHN, and LSUN [START_REF] Yu | Lsun: Construction of a large-scale image dataset using deep learning with humans in the loop[END_REF] to represent novel data. For CIFAR100 we use CIFAR10, SVHN, and LSUN. For SVHN we use CIFAR10, LSUN, and Tiny-ImageNet (subset of ImageNet [START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF]). With these choices, ID and OOD classes never overlap. • Three covariate shift tasks -For each ID dataset, we apply three image transformations from the AugLy library [START_REF] Papakipos | AugLy: Data Augmentations for Robustness[END_REF]: Brightness (fac-tor=3), Blur (radius=2), and Pixelization (ratio=0.5). • Three adversarial attacks -For each ID dataset, we apply three adversarial attacks from Torchattacks (Kim 2020), with default parameters: FGSM, DeepFool, and PGD.

For each of these 27 OOD scenarios, we experiment with two DNN architectures: DenseNet and ResNet. We use the pre-trained models from [START_REF] Lee | A simple unified framework for detecting out-of-distribution samples and adversarial attacks[END_REF]. For monitoring, we test two feature-based approaches: Mahalanobis (Maha) [START_REF] Lee | A simple unified framework for detecting out-of-distribution samples and adversarial attacks[END_REF]) and Outside-the-Box (OtB) [START_REF] Henzinger | Outside the Box: Abstraction-Based Monitoring of Neural Networks[END_REF]. We use the last layer before classification as their data representation. We also use four logit-based approaches: Max Softmax Probability (MSP) [START_REF] Hendrycks | A Baseline for Detecting Misclassified and Out-of-Distribution Examples in Neural Networks[END_REF], Energy (Ene) [START_REF] Liu | Energy-based out-of-distribution detection[END_REF], and ReAct combined with both MSP (R-MSP) and Energy (R-Ene) [START_REF] Sun | React: Out-of-distribution detection with rectified activations[END_REF]. Except for OtB, the techniques used in our experiments require selecting a rejection threshold on the monitoring scores. This is a complex question that is not studied here. Instead, we consider the optimal F1 threshold, as described by [START_REF] Guérin | Robust Detection of Objects under Periodic Motion with Gaussian Process Filtering[END_REF].

The complete code to reproduce our experiments can be found at https://github.com/jorisguerin/neural-networkmonitoring-benchmark

OOD can give a false sense of safety

Here, we want to answer the following question: if we manage to develop a perfect OOD detector m * , can we guarantee that (f , m * ) is safe to use in critical applications?

Let's suppose that we are able to build m * , which rejects all OOD samples and accepts all ID samples (precision and recall of 1 at OOD detection). In our experiments, we can easily simulate the predictions of m * using the known binary ID/OOD labels. Then, we want to know how well m * performs the task of detecting OMS data samples. An OMS recall below one means that there exist ID data points for which f is erroneous. It represents a threat to the safety of the system. An OMS precision below one means that there exist OOD data points for which f is correct. It represents a decrease in the availability of the system.

We conduct this experiment for both DNN architectures, across the 27 OOD datasets. The distribution of the OMS performances obtained for the different OOD types is reported in Figure 4. We can see that the OMS recall is not close to 1 for most of the experiments conducted. Even for novelty, the median OMS recall of the 18 experiments is below 0.93. In other words, in most cases, more than 7% of the errors of f are not detected by the perfect OOD monitor m * , which can lead to catastrophic outcomes for safety-critical applications. This effect is even more pronounced for covariate shifts and adversarial attacks.

These results show that, even if perfect OOD detectors are developed, it will not allow us to guarantee the safety of critical systems using ML. Indeed, an OOD recall of 1 does not guarantee the absence of prediction errors. Even worse, reporting very good OOD results can be detrimental as it gives a false sense that the (f , m * ) system is safe.

Regarding OMS precision, we first note that it is always 1 for novelty datasets. This is because f cannot be correct for novel samples, by definition. For other OOD types, we acknowledge an important drop in precision, i.e., an important proportion of correct predictions of f on OOD data.

OOD can be misleading for comparison

As explained in section 3.2, monitors are often compared using the OOD setting. Here, we want to verify whether comparing monitors at the OOD detection task provides relevant insights into OMS detection performance.

To do this, we compare six monitors from the literature across 27 OOD datasets and two DNNs architectures (section 5.1). For each pair of monitors, we conduct a Wilcoxon signed-rank test across the 54 OOD scenarios to determine whether one is better than the other. The Wilcoxon test is a non-parametric statistical test that can be used to compare pairs of classifiers across multiple datasets [START_REF] Demšar | Statistical comparisons of classifiers over multiple data sets[END_REF]. The results obtained are reported in figure 5.

From these experiments, we can see that the comparison matrices obtained for OOD and OMS look different. For example, OtB is clearly the most conservative approach (highest recall) when looking at the OMS results, but not when considering OOD. On another note, the benefits of using Re-Act for monitoring are best seen in the OMS setting (MSP vs. R-MSP, Ene vs. R-Ene).

From these results, it appears that conducting OOD experiments is not a reliable way to compare monitoring approaches regarding their ability to identify errors of f .

Removing training outliers to build better runtime monitors

As explained earlier (Figure 1), runtime monitors are often fitted using the DNN training dataset to represent "what is safe". The common practice in the literature is to use all available D train samples to fit the monitor. When considering OOD, the objective is to build a binary classifier that can reject "data samples from outside of the training distribution" (dissimilar to D train ). Hence, in this context, it makes sense to fit the monitor using all available training data samples. In practice, DNNs rarely perform perfectly, even on the exact data used for training. For example, the ResNet-34 used in this work misclassifies 127 of the 50, 000 training data samples (training accuracy of 99.746%). When considering the OMS setting, the objective is to build a classifier to identify data samples that are misclassified by f . Hence, it is conceptually wrong to use the misclassified training samples to represent the normal class when fitting a one-class classifier for OMS detection. In this section, we propose a simple trick to build better DNN monitors, consisting in removing erroneous training samples to fit the monitor.

To illustrate this idea, we apply a two-dimensional Uniform Manifold Approximation and Projection (UMAP) transformation [START_REF] Mcinnes | Umap: Uniform manifold approximation and projection for dimension reduction[END_REF] to the training split of CIFAR10. UMAP is an unsupervised embedding method that produces a lower-dimensional representation preserving the global distances. The 2D representation obtained allows us to investigate visually whether the misclassified training samples are outliers, which change the shape of the one-class classifier boundary. The embeddings of four CIFAR10 classes are shown in figure 6. It shows that correctly classified points form compact clusters while misclassified points appear to be clear outliers. To further illustrate our point, we draw the minimal bounding box containing all training samples, and the one containing only correctly classified samples. These bounding boxes represent the one-class classification boundaries of an Outside-the-Box monitor without K-means pre-processing (Henzinger, Figure 6 suggests that removing misclassified training data helps to fit better monitors. However, UMAP embeddings are not real data and one should not rely on intuition gained from such visualizations. Hence, we conduct more formal experiments and compare the performance of a simple OtB monitor (without K-means) when trained with and without misclassified training samples. The mean and standard deviation (St. dev.) of precision and recall are computed across all 54 OOD scenarios (section 5) and reported in table 1. We also conduct a Wilcoxon test and report the p-values obtained. These results demonstrate that removing misclassified training samples can help to increase the recall (clearly statistically significant) without impacting the precision too much. In other words, the monitor can detect more errors of f without discarding additional valid predictions.

Two previous works already had the intuition that removing misclassified training samples could reduce the false negative rate [START_REF] Henzinger | Outside the Box: Abstraction-Based Monitoring of Neural Networks[END_REF][START_REF] Cheng | Runtime monitoring neuron activation patterns[END_REF]. This section explains this intuition and shows experimental evidence of the benefits of this simple trick in the context of OMS detection.

In these experiments, we only used OtB because it is a threshold-free approach. As threshold selection strategies were not discussed in this work, other monitors were not considered here. However, when trying to select an optimal monitoring threshold, we believe that it would also be valuable to not consider misclassified samples as normal data.

Conclusion

If we want to use DNN in safety-critical applications, it is paramount to build efficient runtime monitors, which can detect and remove DNN errors from the system before they can have catastrophic consequences. As of today, many research efforts are directed toward solving the problem of out-of-distribution detection, which consists in identifying data samples that were drawn from a different distribution than the DNN training set. In this paper, we discuss the limitations of this setting to enable the safe usage of DNN in critical systems. First, the concept of OOD is not well-defined, which makes it difficult to compare different OOD detection approaches. Second, even a perfect OOD detector can have the undesirable property of discarding valid predictions of the DNN, and even worse, accepting wrong predictions. Extensive experiments conducted on popular OOD detection datasets confirm that these phenomena occur in practical scenarios. Furthermore, we show that the OOD setting cannot be used to compare monitoring approaches accurately, as the best monitor for OOD is not always the best one to detect DNN errors. Finally, we demonstrate experimentally that it is a good practice to remove training data points that the DNN cannot classify correctly before fitting the monitor.

On the bright side, adapting current OOD research to these findings will not require drastic changes. The out-ofmodel-scope (OMS) setting, defined above and discussed in several previous works, is well-defined and perfectly aligned with the DNN monitoring objectives. In addition, most approaches developed for OOD detection can be used for OMS without any modification, and OMS results can be computed straightforwardly for most OOD datasets used in the literature. Hence, the take-home message from this paper is that instead of evaluating new approaches on their ability to detect samples from other data sources, the OOD detection research community should focus on the ability to detect samples leading to erroneous DNN predictions. We also believe that it is a good idea to include OOD samples in OMS evaluation datasets, which is rarely done in OMS papers. It is worth mentioning that we recently introduced a unified evaluation formalism for runtime monitors, considering the entire system in which a DNN is included (Guerin et al. 2022).

Figure 1 :

 1 Figure 1: Neural Network Runtime Monitoring is a research area aiming to characterize safe data instances, in order to reject unsafe predictions during inference. Different definitions of safe data instances gave rise to different subfields in the literature.

  [START_REF] Hendrycks | A Baseline for Detecting Misclassified and Out-of-Distribution Examples in Neural Networks[END_REF] proposed to use the Maximum Softmax Probability (MSP) as a rejection score. They evaluated the performance of MSP under both the OOD and OMS settings. Ferreira et al. (2021) conducted a benchmark study of OOD detection methods. Their experiments included novelties, covariate shifts, and adversarial attacks.

Figure 2 :

 2 Figure 2: What is Out-Of-Distribution? Images from CI-FAR10 test set with predictions by a ResNet-34 model. The columns represent increasing brightness perturbation levels.

Figure 3 :

 3 Figure 3: Differences between OOD and OMS detection. Schematic representation of the in-distribution domain D ID for a task, as well as the model scope D f of a model f for this task.

Figure 4 :

 4 Figure 4: OMS results for optimal OOD monitors. Distribution of the OMS recall and precision obtained by the optimal OOD detector m * across the 27 OOD datasets and two neural networks tested in our experiments.

Figure 5 :

 5 Figure 5: Pairwise comparison of monitors. Popular monitors are compared across 54 OOD scenarios using a Wilcoxon test. The obtained p-values are reported. Green cells indicate that the approach corresponding to the row is better than the column, red cells indicate that the column is better than the row, and white cells indicate no statistically significant difference (p > 0.05).

Figure 6 :

 6 Figure 6: Should we use misclassified training samples to fit a monitor? Two-dimensional UMAP visualization of four selected classes from the CIFAR10 training split. Colors indicate whether they were correctly classified by the ResNet-34 model. We also show the minimal bounding boxes containing all training samples (orange) and all correctly classified training samples (blue). Misclassified training samples are often outliers, leading to much larger bounding boxes when they are included.

Table 1 :

 1 OMS results for Outside-the-boxLukina, and Schilling 2020). The blue boxes, obtained by removing misclassified samples, are much tighter than the orange ones, and appear to better represent the model scope.

		Recall	Precision
		Mean (St. dev.) Mean (St. dev.)
	All training data	0.75 (0.19)	0.68 (0.18)
	Only correct data	0.77 (0.18)	0.68 (0.18)
	Wilcoxon test	Better	Worst
	p-value	2.6e-9	1.6e-3

In the dependability literature, the availability of a system represents its readiness to deliver a correct service.

Acknowledgments

This research has benefited from the AI Interdisciplinary Institute ANITI. ANITI is funded by the French "Investing for the Future -PIA3" program under the Grant Agreement No ANR-19-PI3A-0004.

This research has also received funding from the European Union's Horizon 2020 research and innovation program under the Marie Skłodowska-Curie grant agreement No 812.788 (MSCA-ETN SAS). This publication reflects only the authors' view, exempting the European Union from any liability. Project website: http://etn-sas.eu/.