Application-Aware Anomaly Detection of Sensor Measurements in Cyber-Physical Systems

Abstract

Detection errors such as false alarms and undetected faults are inevitable in any practical anomaly detection system. These errors can create potentially significant problems in the underlying application. In particular, false alarms can result in performing unnecessary recovery actions while missed detections can result in failing to perform recovery which can lead to severe consequences. In this paper, we present an approach for application-aware anomaly detection (AAAD). Our approach takes an existing anomaly detector and configures it to minimize the impact of detection errors. The configuration of the detectors is chosen so that application performance in the presence of detection errors is as close as possible to the performance that could have been obtained if there were no detection errors. We evaluate our result using a case study of real-time control of traffic signals, and show that the approach outperforms significantly several baseline detectors.

1. Introduction

Sensors deployed in cyber-physical systems (CPS) for monitoring and control purposes are prone to anomalies (e.g., reliability failures and cyber-attacks). To detect anomalies and prevent their harmful effects, anomaly detection systems (ADS) are utilized. However, ADS suffer from false positives (i.e., false alarms) and false negatives (i.e., missed detections), which may result in high performance degradation in CPS applications. In particular, false positives result in recovery that is not required, and false negatives result in failing to perform recovery when it is indeed required. Such detection errors can cause incorrect measurements being transmitted to a controller, and thus result in obtaining non-optimal or even destabilizing control decisions, which may compromise the performance of the system. For example, detection errors may result in disastrous events, such as reactor explosion in process control systems, water contamination in water distribution networks, and extremely heavy traffic congestion in intelligent transportation systems [1,2].

To address the challenges caused by detection errors, it is necessary to take into account the CPS application when designing anomaly detectors, and to quantify the losses in the application caused by potential detection errors. To minimize the losses, it is desirable to reduce the detection errors as much as possible. However, there exists a trade-off between them (i.e., decreasing the rate of false alarms may increase the rate of missed faults, and vice versa), which can be changed through a detection threshold. Therefore, the performance loss caused by detection errors can be minimized by selecting the right detection threshold.

Our goal is to perform these steps using a novel approach, which takes an existing anomaly detector and configures it considering the behavior of the controller. We call our framework Application-Aware Anomaly Detection (AAAD). This framework takes into account the interactions between the controller and the application, and so it can compute how each detection decision may affect the underlying application. Knowing this, the detector attempts to make detection decisions that will result in the least performance loss in the underlying application if the detection decision is not accurate due to false positive and false negative errors.

Previous works have proposed different anomaly detection methods for CPS [1]. In addition, there is a wide body of literature on machine learning-based anomaly detection [3]. The problem of finding optimal thresholds for intrusion detectors is studied in [4]. The paper shows that computing optimal attacks and defenses is computationally expensive, and proposes heuristic algorithms for computing near-optimal strategies. Further, the work in [5] studies the problem of finding optimal thresholds for anomaly-based detectors implemented in dynamical systems in the face of strategic attacks. The paper provides algorithms to compute optimal thresholds that minimize losses considering best-response attacks. However, there is little work that takes into account the tight interaction between the detector and the controller of a CPS, which as we show in this work if taken into account, can result in improved performance and robustness.

Contributions

In this paper, we propose an application-aware anomaly detection framework for minimizing the impact of detection errors in CPS. The contributions of AAAD are as follows:

• We devise an effective detector for identifying anomalies in sensor measurements using machine learning regression and an approach to recover from anomalies in order to maintain operation when detection alerts are triggered.
• We formulate the AAAD problem, in which a detector is optimally configured such that the performance loss in the presence of detection errors is minimized. In particular, the thresholds are selected so that the performance of the system in the presence of detection errors is as close as possible to the performance that could have been achieved if there were no detection errors.
• We show that the AAAD problem is computationally challenging, and then we present an efficient algorithm to find near-optimal solutions.
• We analyze two special cases of the application-aware detection problem: (a) single detector and (b) detectors with equal thresholds. We present optimal solutions for both special cases which can provide insights into the novelty of the approach.
• We evaluate AAAD using simulation experiments on a case study of real-time control of traffic signals. The evaluation results demonstrate the benefits of the approach compared with standard anomaly detection techniques.

We believe that the proposed approach can be useful in any system where there are a significant number of sensors with high variations in sensor values, which may cause many false-positive and false-negative errors. A real-world example of such a CPS application would be real-time control of traffic signals since in large cities, there are thousands of sensors that could become anomalous. Throughout the paper, we will use traffic sensors as a running example to illustrate the application of our framework, but we present the model and results using a general, domain-agnostic formulation. Alternative examples of possible application domains include sensors in water-distribution networks [6].

Related Work

Anomaly detection in cyber-physical systems presents an important and challenging problem [7,8]. As a result, a variety of approaches have been proposed in prior work on anomaly detection. In contrast to our approach, these prior results focused on the design of detectors rather than the optimal configuration of an existing detector.

Several detectors have been built on machine learning and, in particular, neural networks. Goh et al. present an unsupervised approach for anomaly detection in cyber-physical systems based on recurrent neural networks and the cumulative sum method [9]. Kosek presents a contextual anomaly detection method for smart grids based on neural networks [10]. Krishnamurthy et al. use an alternative model, Bayesian networks [11]. They present an approach for learning causal relations and temporal correlations in cyber and physical variables from unlabeled data using Bayesian networks. These networks can then be used to detect anomalies and isolate their root causes.

Jones et al. propose a formal-methods-based approach for anomaly detection in cyber-physical systems [12]. They introduce a model-free, unsupervised learning procedure that constructs a signal temporal logic (STL) formula from system output data collected during normal operations. Then, anomalies can be detected by flagging system trajectories that do not satisfy the learned formula. In a follow-up work, Kong et al. describe a formal-methods-based approach for supervised anomaly learning [13]. Chibani et al. investigate the problem of designing fault-detection filters for fuzzy systems, considering faults and unknown disturbances in discrete-time polynomial fuzzy systems [14,15]. A diagnostic observer-based system for fault detection of fuzzy systems which optimizes the worst case robustness and fault sensitivity is presented in [16].

Anomaly detection has also been considered in the context of security intrusions, that is, to detect cyber-physical attack against a CPS [17]. For example, Urbina et al. study physics-based detection of stealthy attacks against industrial control systems [1]. They review prior work on attack detection and argue that many of these use detection schemes that do not limit the impact of stealthy attacks. They then propose a new metric for measuring impact and demonstrate that attacks may be detected with a proper configuration. In contrast, Kleinmann and Wool consider detection of attacks against industrial control systems based on cyber anomalies [18].

Besides anomaly detection, other approaches have also been considered for detecting faults or attacks in traffic networks. Lu et al. review prior work on the problem of anomaly detection of traffic sensors [19]. Based on the level of data used, they divide detection methods into three levels: macroscopic (highly-aggregated data), mesoscopic (synchronized data for a section of freeways), and microscopic. They also review data-correction methods and provide practical guidelines for anomaly detection in traffic applications. Zygouras et al. present three methods—based on Pearson’s correlation, cross-correlation, and multivariate ARIMA—to detect faulty traffic measurements [20]. They discuss the performance of all three methods and demonstrate that they are complementary to each other. Further, they employ crowd-sourcing to resolve whether irregular measurements are due to faulty sensors or unusual traffic. Finally, Robinson presents a test, based on the relationship between flows at adjacent sensors, to detect faulty loop detectors [21].

Nonetheless, to the best of our knowledge, none of these papers consider the performance of the controller in the design and configuration of anomaly detectors, and they do not perform any application-aware optimization to improve detection performance.

Paper Outline

The rest of this paper is organized as follows. In Section 2, we introduce the system model. In Section 3, we discuss the regression-based anomaly detection. In Section 4, we present the application-aware detection problem for detection error-tolerant selection of thresholds in anomaly detectors. In Section 5, we analyze the application-aware detection problem and present an algorithm to obtain near-optimal solutions. In Section 6, we study two special variations of the application-aware detection problem, that is, single detector and detectors with equal threshold. In Section 7, we evaluate our approach numerically using a case study of real-time control of traffic signals. Finally, we offer concluding remarks in Section 8.

2. Model

In this section, we present the system model and informally introduce the problem of application aware anomaly detection. We also present a running example of real-time control of traffic signals that is used throughout the paper to demonstrate our approach.

2.1. Notation

Vectors are denoted by bold symbols. Vector $\mathit{y}$ at timestep k is described by ${\mathit{y}}^k$. We omit the timestep symbol when all symbols have same timestep k. However, timestep symbol is used when there are different timesteps present or when it eases understanding. Given vector $\mathit{y}$ and set of indices I, vector ${\mathit{y}}_I$ is defined as a vector with same size as $\mathit{y}$ that has the same size as $\mathit{y}$ for indices in I, and is zero otherwise. For a list of symbols used in this section, see

Table 1. List of Symbols.

Symbol	Description
S	Set of sensors
$a_s$	Actual value for sensor s
$m_s$	Measured value for sensor s
$p_s$	Predicted value for sensor s
$T{P}_s\left(\tau \right)$	True positive probability of the detector for sensor s given detection threshold $\tau$
$F{P}_s\left(\tau \right)$	False positive probability of the detector for sensor s given detection threshold $\tau$
$T{N}_s\left(\tau \right)$	True negative probability of the detector for sensor s given detection threshold $\tau$
$F{N}_s\left(\tau \right)$	False negative probability of the detector for sensor s given detection threshold $\tau$
$w_s$	Recovered measurement transmitted to the controller for sensor s
$r_s$	Residual signal for sensor s

.

2.2. System Model

Consider a CPS, for example, an intelligent transportation system or a process control system, consisting of a plant and a controller as shown in Figure 1. At each timestep, given measurements $\mathit{w}$ containing information about the system, a controller computes a control input u that maximizes a utility function $J(\mathit{w},u)$. In other words, the controller determines the optimal control input $u^{\ast }$ defined as

$$u^{\ast }\in \underset{u}{argmax}J(\mathit{w},u),$$

(1)

where the optimal utility is denoted by $J^{\ast }\left(\mathit{w}\right)$.

Anomalous Sensors

Sensors may be anomalous due to hardware failures or sensor attacks. If sensor $s\in S$ is anomalous, there is a discrepancy between the actual and observed measured values. In other words, if $a_s$ is the actual value and $m_s$ is the observed measurement at a timestep, for an anomalous sensor we have $m_s=a_s+e_s$, where $e_s\in \mathbb{R}$ is the error value at that timestep.

2.3. Example: Real-Time Traffic Signal Control

We present real-time control of traffic signals as a running example that is used throughout the paper to demonstrate the applicability of our approach. In the following, we describe the widely-popular max-pressure controller for optimal control of traffic signals [22]. In the original max-pressure algorithm presented in [22], the traffic state is represented using exogenous demands that are then routed through the network using routing ratios. In this work, instead of using exogenous demands that are then transformed to internal demands through using routing ratios, we assume that the internal demands are directly provided. Please note that this does not affect the max-pressure algorithm as the algorithm effectively uses internal demands in its computations.

Max-Pressure Controller

Consider a network of intersections I with road links L. Movement from a link $i\in L$ to a link $j\in L$ is denoted by a pair $(i,j)\in E$. Further, let each movement $(i,j)$ have a queue associated with it, and at each timestep, let $x(i,j)$ represent the length of this queue. The length of the queue shows how many vehicles intend to travel from i to j. For each movement $(i,j)$, the pressure is defined as

$$P(i,j)=x(i,j)-\sum _{p}x(j,p),$$

which is simply the number of cars in the queue minus the total number of cars in the downstream queues.

Each intersection n has a traffic signal with a set of admissible stages ${\Phi }_n$. Each stage $u_n\in {\Phi }_n$ is a set of simultaneous movements that are permitted by the traffic signal. If $u_n$ permits a movement $(i,j)$, then $u_n(i,j)=1$, otherwise $u_n(i,j)=0$. Let $c(i,j)$ be the saturation flow of movement $(i,j)$. Given a stage $u_n\in {\Phi }_n$, pressure-release (i.e., utility) for intersection n is defined as

$$J_n\left(u_n\right)=\sum _{i,j}c(i,j)P(i,j)u_n(i,j).$$

Traffic sensors can be used to measure $x(i,j)$ for all $(i,j)\in E$ and they are prone to failures.

Algorithm 1 presents the max-pressure (MP) controller in detail. At each intersection n, the MP controller selects the stage $u_n$ that results in the maximum pressure-release. In other words, the MP controller computes

$$u_n^{\ast }\in \underset{u_n\in {\Phi }_n}{argmax}\sum _{i,j}c(i,j)P(i,j)u_n(i,j).$$

(2)

Please note that at each intersection, the MP control selects a stage that depends only on the queues adjacent to the intersection. It is shown that the MP controller maximizes network throughput [22].

Algorithm 1 Max-Pressure Controller [22].

Input:$x(i,j)$ for all $(i,j)\in E$ 1: for all$n\in I$do 2:     for all $(i,j)\in E$ do 3:         $P(i,j)\leftarrow x(i,j)-{\sum }_{p}x(j,p)$ 4:     end for 5:     $u_n^{\ast }\leftarrow {argmax}_{u_n\in {\Phi }_n}{\sum }_{i,j}c(i,j)P(i,j)u_n(i,j)$ 6: end for 7: return${\left\{u_n^{\ast }\right\}}_{n\in I}$

The overall utility for traffic network can be calculated by adding individual utilities for the intersections. That is, $J(x,u)={\sum }_n{J}_n(x,u_n)$ where $u={\left\{u_n\right\}}_{n\in I}$. Please note that using this representation, the MP optimization problem becomes the same as (1).

2.4. Anomaly Detection, Recovery, and Resilience

Next, we discuss anomalies caused by sensor faults and their detection, and we informally introduce the problem of optimal detector configuration, which we will formalize in Section 4.4. In contrast to the previous subsection, where we introduced our running example, the discussion here will again be domain agnostic.

Anomalies may cause damage to the system and significantly degrade the performance of the CPS application (as measured by the utility function $J(\mathit{w},u)$). Consequently, we must employ an anomaly detector to detect faults in sensor measurements. In our running example, anomalies can affect the traffic measurements, and therefore, degrade the utility of the traffic signal control. Suppose that we have an anomaly detection method. Upon detection, the system must recover from anomalies and continue operation. To this end, we must employ a recovery method in order to continue operation in the presence of detection alerts. In the traffic signal control example, operation must continue even in the presence of anomalous traffic measurements.

Now, suppose that we have a recovery approach that computes a recovered vector of measurements in the presence of detection alerts. In anomaly detectors, there are detection errors, that is, false positives (i.e., false alarms) and false negatives (i.e., missed faults). If there were no detection errors, the recovered vector of measurements would be close to the actual values (of course assuming that the recovery approach works well). However, in the presence of detection errors, false positives result in recovery that is not required, and false negatives result in failing to perform recovery when it is indeed needed.

To illustrate the effect of detection errors on the application, let ${\mathit{w}}^{\prime }$ denote the recovered measurement vector, which will result in the utility $J^{\prime }={max}_{u}J({\mathit{w}}^{\prime },u)$. However, if there were no detection error, we could have obtained the optimal utility $J^{\ast }={max}_u(\mathit{a},u)$. Hence, we face the problem of optimally configuring an anomaly detector through the selection of detection thresholds so that the actual obtained utility in the presence of detection errors (i.e., $J^{\prime }$) is as close as possible to the utility that would have been obtained if there were no detection errors (i.e., $J^{\ast }$). In the traffic signal control example, the utility is quantified by the pressure release for an intersections that can be used as a proxy for maximizing network throughput.

3. Anomaly Detection

In this section, we construct an example regression-based anomaly detector for identifying anomalous sensor measurements. We then discuss detection errors and some metrics that are used to characterize them.

3.1. Regression-Based Anomaly Detector

To protect the system against anomalies, we must detect them quickly and accurately. Many different anomaly detection systems have been proposed in the literature. For a comprehensive review of anomaly detection methods, we refer the reader to [3] for machine-learning-based detectors and [1] for detectors used in CPS. In this work, we use regression-based anomaly detectors because in addition to high detection performance, such detectors require no knowledge of the physical system, can take into account complex and nonlinear behaviors of the system, and are easy to implement and can be highly scalable.

3.1.1. Architecture

Figure 2 shows the architecture of regression-based anomaly detector. The detector consists of two main components: (1) Predictor and (2) Statistical Test. The predictor predicts the value of a sensor given some information about the system state (e.g., current value of other sensors, previous control inputs). Then, the statistical test compares the computed prediction to the observed measurement and decides whether the sensor is normal or anomalous. We describe each component in more detail considering the running example of real-time traffic control.

3.1.2. Predictor

Our goal is to find a function $f^{\left(s\right)}$ that maps spatial or temporal features to the actual value of a sensor s (e.g., traffic flow or occupancy). In practice, two traffic sensors are highly correlated if they are in close proximity. Thus, we let the features be the measured values of other adjacent sensors at the same timestep, denoted by ${\mathit{m}}_{A\left(s\right)}$ where $A\left(s\right)$ is a set of sensors adjacent to $A\left(s\right)$ found using cross-validation. Please note that this approach is particularly applicable to traffic networks as there are usually many redundant sensors in the network. The function $f^{\left(s\right)}$ can then be obtained using suitable machine learning regression algorithm such as deep neural networks [23], Gaussian Processes [24], and many others [25]. Thus, for sensor s, we obtain the prediction as $p_s=f^{\left(s\right)}\left({\mathit{m}}_{A\left(s\right)}\right)$.

3.1.3. Statistical Test

The statistical test efficiently detects anomalies for each sensor $s\in S$ by comparing the measured value $m_s\left(k\right)$ with the predicted value $p_s\left(k\right)$. Given a set of measured values $\mathit{m}={\langle m_s\rangle }_{s\in S}$ and predicted values $\mathit{p}={\langle p_s\rangle }_{s\in S}$, residual signals are computed as $\mathit{r}=|\mathit{m}-\mathit{p}|$. Then, given the residuals, the statistical test makes detection decisions $\mathit{d}={\langle d_s\rangle }_{s\in S}$, where for each sensor s, the decision $d_s$ is either normal or anomalous.

Different detection algorithms can be used to implement the statistical test [26]. In this work, we consider a stateless threshold-based detector defined as follows. It should be noted that for ease of presentation, our model assumes that a detector can be configured using a single threshold value ${\tau }_s$. However, our results can be easily applied to detectors that are configured using multiple parameter values. We discuss how to incorporate such detectors into our framework in Section 3.2. Given detection thresholds $\mathit{\tau }={\langle {\tau }_s\rangle }_{s\in S}$, for each sensor s, if the residual $r_s$ is less than or equal to the threshold ${\tau }_s$, then s is marked normal and otherwise, s is marked anomalous. Thus

$$\begin{array}{c}\hfill d_s=\left\{\begin{array}{cc}\mathrm{normal}(s\in N)\hfill & \mathrm{if}{r}_s\le {\mathit{\tau }}_s\hfill \\ \mathrm{anomalous}(s\in A)\hfill & \mathrm{otherwise}\hfill \end{array}\right..\end{array}$$

(3)

3.2. Detection Error

In anomaly detectors, there might be a false negative, which means failing to raise an alarm when an anomaly did happen. Further, there might be a false positive, which means raising an alarm when the system exhibits normal behavior. It is desirable to reduce the false positive and false negative probabilities as much as possible. However, there exists a trade-off between them, which can be controlled by changing the detection threshold. In particular, by decreasing (increasing) the threshold, one can decrease (increase) the FN probability and increase (decrease) the FP probability.

We represent the FN probability for each sensor s by the function $F{N}_s:{\mathbb{R}}_{+}\to [0,1]$, where $F{N}_s\left({\tau }_s\right)$ is the probability of FN when the threshold is ${\tau }_s$, given that the sensor is anomalous. Similarly, we denote the attainable FP probability for each sensor s by $F{P}_s:{\mathbb{R}}_{+}\to [0,1]$, where $F{P}_s\left({\tau }_s\right)$ is the FP probability when the threshold is ${\tau }_s$, given that the sensor is in normal operation. The true positive and true negative probabilities are also denoted by $T{P}_s\left({\tau }_s\right)$ and $T{N}_s\left({\tau }_s\right)$. Clearly, we have $T{P}_s\left({\tau }_s\right)=1-F{N}_s\left({\tau }_s\right)$ and $T{N}_s\left({\tau }_s\right)=1-F{P}_s\left({\tau }_s\right)$.

It should be noted that even though we assumed in Section 3.1.3 that each detector can be configured using a single threshold value ${\mathit{\tau }}_s$, our framework can actually be applied to detectors that are configured using multiple parameter values. For such a detector, each possible configuration (i.e., combination of parameter values) results in some pair of false-negative and false-positive error probabilities. By considering the Pareto optimal configurations (i.e., configurations such that neither probability can be decreased without increasing the other), we can obtain a curve that represents the best attainable pairs of false-negative and false-positive probabilities. Then, we can simply let threshold values correspond to points on this curve such that false-negative and false-positive probabilities ($F{N}_s$ and $F{P}_s$) are increasing and decreasing functions of the threshold ${\tau }_s$, respectively.

4. Application-Aware Anomaly Detection

In this section, we present the problem of application-aware anomaly detection (AAAD). First, we describe an approach for recovery in order to continue operation in the presence of detection alerts. Then, we quantify the utility losses in the application caused by potential detection errors. Based on the characterization of the utility losses, we formulate the AAAD problem, i.e., the problem of finding detection thresholds so that the obtained utility in the presence of detection errors is as close as possible to the utility that could have been obtained if there were no detection errors.

4.1. Architecture

Figure 3 shows the AAAD architecture. If there is a detection alert, the prediction is routed to the application, instead of the measurement. The threshold of each detector is selected such that in the presence of detection error, the routed value (i.e., measurement or prediction) still obtains a utility close to the utility that could have been obtained if there were no detectors. (Please note that in the figure, the predictor is not connected to the anomaly detector since this framework is applicable to any threshold-based detector, and not only regression-based detectors.)

4.2. Recovery

We consider a recovery approach in order to continue operation in the presence of detection alerts. If sensor s is marked normal, then the observed measurement $m_s$ is transmitted to the controller. However, if sensor s is marked anomalous, then the observed measurement is discarded and instead, the prediction $p_s$ is transmitted to the controller. The switch in Figure 3 illustrates this idea. To formally represent the recovery approach, let $w_s$ denote the recovered measurement transmitted to the controller. Then, $w_s$ can be described as

$$\begin{array}{c}\hfill w_s=\left\{\begin{array}{cc}{m}_s\hfill & \mathrm{if}s\mathrm{is}\mathrm{normal}\hfill \\ p_s\hfill & \mathrm{if}s\mathrm{is}\mathrm{anomalous}\hfill \end{array}\right..\end{array}$$

(4)

For the threshold-based detector defined by (3), the measurement of sensor s is marked normal if $|p_s-m_s|\le {\tau }_s$ and anomalous otherwise. Therefore, for threshold-based detectors, the above equation can be re-written as

$$\begin{array}{c}\hfill w_s\left({\tau }_s\right)=\left\{\begin{array}{cc}{m}_s\hfill & \mathrm{if}|m_s-p_s|\le {\tau }_s\hfill \\ p_s\hfill & \mathrm{otherwise}\hfill \end{array}\right..\end{array}$$

(5)

Please note that in this case, given prediction $p_s$ and measurement $m_s$, the value of $w_s$ depends on the threshold ${\tau }_s$. To highlight this dependence, we use the notation $w_s\left({\tau }_s\right)$ instead of $w_s$. To summarize, given vectors of predictions $\mathit{p}$, measurements $\mathit{m}$, and thresholds $\mathit{\tau }$, using (5), we are able to compute the recovered measurement vector $\mathit{w}\left(\mathit{\tau }\right)$ that is transmitted to the controller.

We assume that when a measurement is normal, it provides the best obtainable value for the sensor. Also, we assume that when a measurement is anomalous, the prediction provides the best obtainable value for the sensor.

4.3. Worst-Case Utility Loss Due to Detection Error

The control input u (i.e., defined by  (1)) depends on the recovered measurements $\mathit{w}\left(\mathit{\tau }\right)$ (i.e., defined by (5)), and the recovered measurements $\mathit{w}\left(\mathit{\tau }\right)$ depend on the detection thresholds $\mathit{\tau }$. Therefore, the value of control input depends on thresholds $\mathit{\tau }$. For example, if the thresholds are small (large), there will be many (few) detection alarms, and so predictions (measurements) will often be transmitted to the controller. Unfortunately, this will be problematic in the presence of detection errors.

Given threshold $\mathit{\tau }$, let N be the set of sensors that are marked normal (i.e., $\forall s\in N,r_s\le {\mathit{\tau }}_s$) and let A be the set of sensors that are marked anomalous (i.e., $\forall s\in A,r_s>{\mathit{\tau }}_s$). Based on the recovery method (5), the predictions are used for marked-anomalous sensors in A and measurements are used for marked-normal sensors in N to create the recovered measurement vector, i.e., $\mathit{w}={\mathit{p}}_A\cup {\mathit{m}}_N$. Next, given the recovered measurements ${\mathit{p}}_A\cup {\mathit{m}}_N$, the controller computes the control input $u_0\in {argmax}_{u}J({\mathit{p}}_A\cup {\mathit{m}}_N,u)$, concisely denoted by $U({\mathit{p}}_A\cup {\mathit{m}}_N)$. This is expected to obtain the utility $J({\mathit{p}}_A\cup {\mathit{m}}_N,u_0)$. However, the expected utility is obtained only if there is no detection error. Unfortunately, if there is a detection error, a different and potentially much lower utility is obtained.

4.3.1. Obtained Utility vs. Optimal Utility

We now quantify the actual obtained utility in presence of detection errors. Let $fp\subseteq A$ be the set of false positives, that is, sensors in $fp$ are normal but they are marked anomalous. Since these sensors are normal, the measurements ${\mathit{m}}_{fp}$ should have been transmitted to the controller, but due to false positives, the predictions were mistakenly transmitted. Similarly, let $fn\subseteq N$ be the set of false negatives, that is, sensors in $fn$ are anomalous but they are marked normal. Since these sensors are anomalous, the predictions ${\mathit{p}}_{fn}$ should have been transmitted to the controller but the measurements were mistakenly transmitted. Hence, for the control input $u_0=U({\mathit{p}}_A\cup {\mathit{m}}_N)$ computed above, the obtained utility will actually be $J({\mathit{p}}_{tp}\cup {\mathit{m}}_{fp}\cup {\mathit{m}}_{tn}\cup {\mathit{p}}_{fn},u_0)$. On the other hand, if there were not detection errors, the optimal control input would have been $u^{\ast }\in {argmax}_{u}J({\mathit{p}}_{tp}\cup {\mathit{m}}_{fp}\cup {\mathit{m}}_{tn}\cup {\mathit{p}}_{fn},u)$, concisely denoted by $U({\mathit{p}}_{tp}\cup {\mathit{m}}_{fp}\cup {\mathit{m}}_{tn}\cup {\mathit{p}}_{fn})$.

4.3.2. Utility Loss

To put this all together, given decisions A and N (computed given $\mathit{r}$ and $\mathit{\tau }$ as (3)), and the detection performance sets $tp$, $fp$, $tn$, and $fn$, the probability of occurrence of such detection error scenario is

$$Pr(\mathit{\tau },tp,fp,tn,fn)=\prod _{s\in tp}T{P}_s\left({\mathit{\tau }}_s\right)·\prod _{s\in fp}F{P}_s\left({\mathit{\tau }}_s\right)·\prod _{s\in tn}T{N}_s\left({\mathit{\tau }}_s\right)·\prod _{s\in fn}F{N}_s\left({\mathit{\tau }}_s\right).$$

(6)

As discussed above, in this case, we could have obtained the optimal utility $J({\mathit{p}}_{tp}\cup {\mathit{m}}_{fp}\cup {\mathit{m}}_{tn}\cup {\mathit{p}}_{fn},U({\mathit{p}}_{tp}\cup {\mathit{m}}_{fp}\cup {\mathit{m}}_{tn}\cup {\mathit{p}}_{fn}))$, but we obtained the smaller utility $J({\mathit{p}}_{tp}\cup {\mathit{m}}_{fp}\cup {\mathit{m}}_{tn}\cup {\mathit{p}}_{fn},U({\mathit{p}}_A\cup {\mathit{m}}_N))$. Thus, we incurred a utility loss of

$$\begin{array}{c}\hfill \Delta J=\underset{\mathrm{Optimal}\mathrm{Utility}}{\underbrace{J^{\ast }({\mathit{p}}_{tp}\cup {\mathit{m}}_{fp}\cup {\mathit{m}}_{tn}\cup {\mathit{p}}_{fn})}}-\underset{\mathrm{Obtained}\mathrm{Utility}}{\underbrace{J({\mathit{p}}_{tp}\cup {\mathit{m}}_{fp}\cup {\mathit{m}}_{tn}\cup {\mathit{p}}_{fn},U({\mathit{p}}_A\cup {\mathit{m}}_N))}}.\end{array}$$

(7)

Hence, the expected utility loss of detection error scenario $tp\subseteq A$, $fp=A-tp$, $tn\subseteq N$, and $fn=N-tn$ is

$$C(\mathit{\tau },tp,fp,tn,fn)=Pr(\mathit{\tau },tp,fp,tn,fn)·\Delta J.$$

(8)

where $Pr(\mathit{\tau },tp,fp,tn,fn)$ is obtained using (6) and $\Delta J$ is obtained using (7).

4.3.3. Worst-Case Analysis

Since the sets of false positives and false negatives are not know a priori, we need to consider any possible scenario. We define the worst-case loss due to detection errors as follows.

Definition 1

(Worst-Case Detection Error Loss). Given the thresholds τ and the residuals $\mathit{r}$, the worst-case loss due to detection errors is defined as

$$\begin{array}{cc}\hfill L\left(\mathit{\tau }\right)=\underset{\begin{array}{c}tp\subseteq A,tn\subseteq N\\ fp=A-tp\\ fn=N-tn\end{array}}{max}C(\mathit{\tau },tp,fp,tn,& fn),\hfill \end{array}$$

(9)

where $C(\mathit{\tau },tp,fp,tn,fn)$ is defined as (8), and A and N are found using (3).

4.4. Optimal Application-Aware Anomaly Detection Problem

To protect against the utility loss due to detection errors, the designer must choose the thresholds that result in the best performance with respect to the worst-case loss (9). An application-aware anomaly detector achieves this by finding the optimal thresholds ${\mathit{\tau }}^{\ast }$ in each time step. We call this problem the Application-Aware Anomaly Detection Problem:

Definition 2

(Application-Aware Anomaly Detection Problem). Given a system model, an anomaly detector, and measured and predicted sensor values, the Application-Aware Anomaly Detection Problem is finding the optimal thresholds ${\mathit{\tau }}^{\ast }$ that minimizes the loss (9); in other words,

$${\mathit{\tau }}^{\ast }\in \underset{\mathit{\tau }}{argmin}L\left(\mathit{\tau }\right).$$

(10)

If we are not able to change the thresholds at each timestep, and instead can change thresholds every T timesteps, we define

$$\overline{L}\left(\mathit{\tau }\right)=\frac{1}{T}\sum _{k=1}^T{L}^k\left(\mathit{\tau }\right),$$

(11)

and then we find thresholds ${\mathit{\tau }}^{\ast }$ that minimize the above equation. We call this problem the Static Application-Aware Anomaly Detection Problem:

Definition 3

(Static Application-Aware Anomaly Detection Problem). Given a system model, an anomaly detector, and measured and predicted sensor values, the Static Application-Aware Anomaly Detection Problem in a time period T is finding the optimal thresholds ${\mathit{\tau }}^{\ast }$ that minimizes the loss (11):

$${\mathit{\tau }}^{\ast }\in \underset{\mathit{\tau }}{argmin}\overline{L}\left(\mathit{\tau }\right).$$

(12)

Clearly, (10) can be solved as a special case of (12) for $T=1$.

5. Analysis

In this section, we solve the problems (10) and (12). First, we analyze the problem of worst-case detection error loss (9), and we prove that solving this problem is computationally challenging. We then present Algorithm 2 which is an efficient algorithm to obtain approximately optimal solutions. Second, we present Algorithm 3 to solve the application-aware detection problem (10) and obtain near-optimal thresholds. Finally, we propose Algorithm 4 to solve the problem of application-aware detection in a time period. The algorithm implements a variation of simulated annealing algorithm and finds near-optimal detection thresholds.

5.1. Algorithm for Worst-Case Detection Error Loss Problem

We begin our analysis by studying the computational complexity of finding worst-case loss due to detection errors (9). To this end, we formulate the problem of finding a worst-case loss as a decision problem.

Definition 4

(Worst-Case Detection Error Problem (Decision Version)). Given a set of sensors S, detection thresholds τ, residuals $\mathit{r}$, and desired loss $L^{\ast }$, determine whether there exists a detection error scenario that incurs the detection error loss of at least $L^{\ast }$.

The following theorem establishes the computational complexity of finding a worst-case detection error.

Theorem 1.

Worst-Case Detection Error Problem (WCDE) is NP-Hard.

Proof. 

We prove the above theorem using a reduction from a well-known NP-hard problem, the Maximum Independent Set Problem.

Definition 5

(Maximum Independent Set Problem (Decision Version)). Given an undirected graph $G=(V,E)$ and a threshold cardinality k, determine whether there exists an independent set of nodes (i.e., a set of nodes such that there is no edge between any two nodes in the set) of cardinality k.

Given an instance of the Maximum Independent Set Problem (MIS), that is, a graph $G=(V,E)$ and a threshold cardinality k, we construct an instance of the WCDE as follows:

• Let the set of sensors be $S:=V$.
• Let $p_s=0$ and $m_s=1$ for every sensor $s\in S$.
• For every sensor $s\in S$, let ${\mathit{\tau }}_s=ϵ$ where $ϵ<1$, so that $A=S$ and $N=\varnothing$.
• Let $T{P}_s\left({\mathit{\tau }}_s\right)=F{P}_s\left({\mathit{\tau }}_s\right)=T{N}_s\left({\mathit{\tau }}_s\right)=F{N}_s\left({\mathit{\tau }}_s\right)=0.5$ for every sensor $s\in S$.
• Let the dimension of the control signal be $\left|S\right|$. For each element i of u, let $u_i\in \{0,1\}$.
• Let the utility function be $J(\mathit{w},u)={∥\mathit{w}\circ u∥}_1$ if the non-zero elements in $\mathit{w}$ form a non-empty independent set, and $-{∥u∥}_1$ otherwise.
• Finally, let the threshold loss be $L^{\ast }:={\left(\frac{1}{2}\right)}^{\left|S\right|}k$.

Clearly, the above reduction can be performed in polynomial time. Hence, it remains to show that the constructed instance of WCDE has a solution if and only if the given instance of MIS does.

MIS then WCDE. First, suppose that MIS has a solution, that is, there exists an independent set I of k nodes. We claim that the set $fp=I$ and $tp=S-I$ is a solution to WCDE. We have

$$\Delta J=J^{\ast }({\mathit{p}}_{tp}\cup {\mathit{m}}_{fp})-J({\mathit{p}}_{tp}\cup {\mathit{m}}_{fp},U\left({\mathit{p}}_A\right)))=J^{\ast }\left({\mathit{m}}_{fp}\right)-J({\mathit{m}}_{fp},<0{>}_{i\in 1}^{\left|S\right|})={∥{\mathit{m}}_{fp}∥}_1-0=k$$

Since $Pr(\mathit{\tau },tp,fp,tn,fn)={\left(\frac{1}{2}\right)}^{\left|S\right|}$ for any given sets of detection error, we obtain $L\left(\mathit{\tau }\right)={\left(\frac{1}{2}\right)}^{\left|S\right|}·k$.

Not MIS then Not WCDE. Second, suppose that MIS has no solution, that is, every set of at least k nodes is non-independent. Then, we have that $J(\mathit{w},u)<k$ for every $\mathit{w}$; otherwise, there would exist a set of at least k nodes in I that are independent of each other, which would contradict our supposition. Then, since $Pr(\mathit{\tau },tp,fp,tn,fn)={\left(\frac{1}{2}\right)}^{\left|S\right|}$, we conclude $L\left(\mathit{\tau }\right)<{\left(\frac{1}{2}\right)}^{\left|S\right|}·k$. □

Algorithm 2 Algorithm for Computing Worst-Case Loss.

1: functionWorst_Loss($\mathit{\tau },\mathit{m},\mathit{p}$) 2:     for all $s\in S$ do 3:         ($|m_s-p_s|\le {\mathit{\tau }}_s$) ? $N\leftarrow N\cup \left\{s\right\}$ : $A\leftarrow A\cup \left\{s\right\}$ 4:     end for 5:     $tp\leftarrow A$, $fp\leftarrow \varnothing$ 6:     $tn\leftarrow N$, $fn\leftarrow \varnothing$ 7:     $L^{\ast }\leftarrow 0$ 8:     while $tp\ne \varnothing \mathit{or}tn\ne \varnothing$ do 9:         $(C_i,i)\leftarrow {max}_{i\subseteq tp}C(\mathit{\tau },tp\backslash i,fp\cup \left\{i\right\},tn,fn)$ 10:         $(C_j,j)\leftarrow {max}_{j\subseteq tn}C(\mathit{\tau },tp,fp,tn\backslash j,fn\cup \left\{j\right\})$ 11:         if $C_i<L_j$ then 12:            $C\leftarrow C_j$ 13:            $tn\leftarrow tn\backslash j$ 14:            $fn\leftarrow fn\cup \left\{j\right\}$ 15:         else 16:            $C\leftarrow C_i$ 17:            $tp\leftarrow tp\backslash i$ 18:            $fp\leftarrow fp\cup \left\{i\right\}$ 19:         end if 20:         if $C^{\ast }<C$ then 21:            $C^{\ast }\leftarrow C$ 22:         else 23:            return $C^{\ast }$ 24:         end if 25:     end while 26:     return $C^{\ast }$ 27: end function

We present Algorithm 2 which uses a greedy approach to obtain the worst-case loss due to detection errors. The algorithm starts considering a scenario of perfect detection, that is, $tp=A$, $fp=\varnothing$, $tn=N$ and $fn=\varnothing$. In each iteration, the algorithm moves an element from either $tp$ or $tn$ to respectively $fp$ or $fn$ that maximally increases the utility loss. If no such element exists, the algorithm terminates with the best solution found so far.

The runtime of Algorithm 2 depends on the function J, which depends on the considered application. If there is an oracle that computes $U\left(\mathit{w}\right)$ and $J(\mathit{w},U(\mathit{w}\left)\right)$ in constant time, the runtime of Algorithm 2 is linear with respect to $\left|S\right|$. That is, the runtime of Algorithm 2 is $\mathcal{O}\left(\right|S\left|\right)$.

5.2. Algorithm for Application Aware Anomaly Detection Problem

To solve the AAAD problem, we first prove the following lemma. The lemma shows that the problem is equal to the problem of selecting a set of normal sensors N and a set of anomalous sensors A, which has a much smaller search space than the original problem.

Lemma 1.

For sensor s with residual $r_s$, the optimal threshold with respect to (10) satisfies ${\tau }_s\in \{0,r_s,r_s^{+},M\}$.

Proof. 

We need to prove that for sensor s with residual $r_s$, the optimal threshold with respect to (10) is in the set $\{0,r_s,r_s^{+},M\}$. First, let us recall that the optimal threshold is

$$\begin{array}{c}\hfill {\mathit{\tau }}^{\ast }\in \underset{\mathit{\tau }}{argmin}\underset{\begin{array}{c}tp\subseteq A,tn\subseteq N\\ fp=A-tp\\ fn=N-tn\end{array}}{max}Pr(\mathit{\tau },tp,fp,tn,fn)·\Delta J,\end{array}$$

where $\Delta J=J^{\ast }({\mathit{p}}_{tp}\cup {\mathit{m}}_{fp}\cup {\mathit{m}}_{tn}\cup {\mathit{p}}_{fn})-J({\mathit{p}}_{tp}\cup {\mathit{m}}_{fp}\cup {\mathit{m}}_{tn}\cup {\mathit{p}}_{fn},U({\mathit{p}}_A\cup {\mathit{m}}_N))$.

Suppose there exists a set of optimal thresholds ${\mathit{\tau }}^{\ast }$ such that some of its elements are not in the set mentioned above. Let s be one such sensor, that is, ${\tau }_s^{\ast }\notin \{0,r_s,r_s^{+},M\}$. First, let $0<{\tau }_s^{\ast }<r_s$. Clearly, $\Delta J\left({\mathit{\tau }}^{\ast }\right)=\Delta J({\mathit{\tau }}_{-s}\cup \left\{0\right\})=\Delta J({\mathit{\tau }}_{-s}\cup \left\{r_s\right\})$. Then, we write $\frac{Pr({\mathit{\tau }}^{\prime },tp,fp,tn,fn)}{Pr({\mathit{\tau }}^{\ast },tp,fp,tn,fn)}=\frac{T{P}_s\left({\tau }_s^{\prime }\right)}{T{P}_s\left({\tau }_s^{\ast }\right)}>1$ if ${\tau }_s^{\prime }=0$, and so ${\tau }_s^{\ast }$ cannot be the optimal threshold if s is in the set of true positives. Also, $\frac{Pr({\mathit{\tau }}^{\prime },tp,fp,tn,fn)}{Pr({\mathit{\tau }}^{\ast },tp,fp,tn,fn)}=\frac{F{P}_s\left({\tau }_s^{\prime }\right)}{F{P}_s\left({\tau }_s^{\ast }\right)}>1$ if ${\tau }_s^{\prime }=r_s$, and so ${\tau }_s^{\ast }$ cannot be the optimal threshold if s is in the set of false positives either. Second, let $r_s^{+}<{\tau }_s^{\ast }<M$. Again, we have $\Delta J\left({\mathit{\tau }}^{\ast }\right)=\Delta J({\mathit{\tau }}_{-s}\cup \left\{r_s^{+}\right\})=\Delta J({\mathit{\tau }}_{-s}\cup \left\{M\right\})$. Then, we write $\frac{Pr({\mathit{\tau }}^{\prime },tp,fp,tn,fn)}{Pr({\mathit{\tau }}^{\ast },tp,fp,tn,fn)}=\frac{T{N}_s\left({\tau }_s^{\prime }\right)}{T{N}_s\left({\tau }_s^{\ast }\right)}>1$ if ${\tau }_s^{\prime }=M$. Also, $\frac{Pr({\mathit{\tau }}^{\prime },tp,fp,tn,fn)}{Pr({\mathit{\tau }}^{\ast },tp,fp,tn,fn)}=\frac{F{N}_s\left({\tau }_s^{\prime }\right)}{F{N}_s\left({\tau }_s^{\ast }\right)}>1$ if ${\tau }_s^{\prime }=r_s^{+}$. This means that ${\tau }_s^{\ast }$ cannot be the optimal threshold if s is in the set of true negatives or false negatives either. This contradicts our supposition, and thus, ${\tau }_s\notin \{0,r_s,r_s^{+},M\}$ can never be correct. This concludes our proof. □

Algorithm 3 Algorithm for Design of Application-Aware Detector.

1: functionApplication_Aware($\mathit{m},\mathit{p}$) 2:     $N\leftarrow S$, $A\leftarrow \varnothing$ 3:     $L^{\ast }\leftarrow \infty$ 4:     while $A\ne S$ do 5:         $(L,s)\leftarrow {argmin}_{s\in N}Worst\_Loss(A\cup \left\{s\right\},N\backslash \left\{s\right\},\mathit{m},\mathit{p})$ 6:         if $L^{\ast }<L$ then 7:            $L^{\ast }\leftarrow L$ 8:            $A\leftarrow A\cup \left\{s\right\}$ 9:            $N\leftarrow N\backslash \left\{s\right\}$ 10:         else 11:            return $L^{\ast }$ 12:         end if 13:     end while 14:     return $L^{\ast }$ 15: end function

Following the above lemma, we present Algorithm 3 to obtain application-aware detection thresholds. The algorithm begins by initializing all sensors as normal, that is, $N=S$ and $A=\varnothing$. In each iteration, the algorithm moves a sensor from N to A, which maximally decreases the worst-case loss. To compute the worst-case loss, Algorithm 2 is used.

Similar to the previous algorithm, the running time depends on the function J and the considered application. If there is an oracle that returns $U\left(\mathit{w}\right)$ and $J(\mathit{w},U(\mathit{w}\left)\right)$ in constant time, the runtime of Algorithm 3 is $\mathcal{O}\left(\right|S{|}^2)$.

5.3. Algorithm for Application-Aware Anomaly Detection in a Time Period

We present Algorithm 4 which solves the problem of application-aware detection in a time period T (2). The algorithm is based on a variation of simulated annealing algorithm, and finds near-optimal thresholds $\mathit{\tau }$. The idea is to start with an arbitrary solution $\mathit{\tau }$ and improving it iteratively. In each iteration, we generate a new candidate solution ${\mathit{\tau }}^{\prime }$ in the neighborhood of $\mathit{\tau }$. If the candidate solution ${\mathit{\tau }}^{\prime }$ is better in minimizing the loss, then the current solution is replaced with the new one. However, if ${\mathit{\tau }}^{\prime }$ increases the loss, the new solution replaces the current solution with only a small probability. This probability depends on the difference between the two solutions in terms of loss as well as a temperature parameter which is a decreasing function of the number of iterations. These random replacements decreases the likelihood of getting stuck in a local minimum.

Algorithm 4 Algorithm for Design of the Application-Aware in a Time Period.

1: Input:$\mathit{m}$, $\mathit{p}$ 2: Initialize:$\mathit{\tau }$, $n\leftarrow 1$, $T_0$ 3: $L\left(\mathit{\tau }\right)\leftarrow Worst\_Loss(\mathit{\tau },\mathit{m},\mathit{p})$ 4: while$n\le n_{max}$do 5:     ${\mathit{\tau }}^{\prime }\leftarrow Perturb(\mathit{\tau },n)$ 6:     $L\left({\mathit{\tau }}^{\prime }\right)\leftarrow Worst\_Loss({\mathit{\tau }}^{\prime },\mathit{m},\mathit{p})$ 7:     $c\leftarrow e^{(L\left({\mathit{\tau }}^{\prime }\right)-L\left(\mathit{\tau }\right))/T}$ 8:     if $(L\left({\mathit{\tau }}^{\prime }\right)<L\left(\mathit{\tau }\right))\vee (\mathtt{rand}(0,1)\le c)$ then 9:         $\mathit{\tau }\leftarrow {\mathit{\tau }}^{\prime }$, $L\left(\mathit{\tau }\right)\leftarrow L\left({\mathit{\tau }}^{\prime }\right)$ 10:     end if 11:     $T\leftarrow T_0·e^{-\beta n}$ 12:     $n\leftarrow n+1$ 13: end while 14: return$\mathit{\tau }$

In Algorithm 4, $Perturb(\mathit{\tau },n)$ defines the neighborhood of $\mathit{\tau }$ in the nth iteration, from which ${\mathit{\tau }}^{\prime }$ is randomly sampled. More specifically, $Perturb(\mathit{\tau },n)$ means that each ${\mathit{\tau }}_s$ in $\mathit{\tau }$ is replaced by ${\tau }_s^{\prime }={\mathit{\tau }}_s+\Delta {\mathit{\tau }}_s$. Here, for each $s\in S$, $\Delta {\mathit{\tau }}_s$ is randomly picked from the uniform distribution over $\left[-\alpha \left(\frac{n_{max}-n}{n_{max}}\right),\alpha \left(\frac{n_{max}-n}{n_{max}}\right)\right]$ for some $\alpha \in {\mathcal{R}}_{+}$. Moreover, since ${\tau }_s^{\prime }$ is nonnegative, we replace it with 0 if ${\tau }_s^{\prime }<0$.

6. Special Cases

In this section, we consider two special cases for the AAAD problem (10). The first special case is single detector, which means that either there is a single detector in the system or each detector is optimized independently of other detectors. The second special case is detectors with equal thresholds, where there are multiple detectors that have the same thresholds.

6.1. Single Detector

Consider a scenario where $\left|S\right|=1$. This means that either there is a single detector in the system, or each detector is optimized independently and irrespective of other detectors. Let $S=\left\{a\right\}$ be the considered sensor, and let $r_a=|p_a-m_a|$ be the residual of the sensor at a timestep. First, we consider a threshold ${\tau }_a^{\prime }$ where $r_a>{\tau }_a^{\prime }$ for this sensor. This threshold results in a detection alert, and so the set of marked-anomalous sensors becomes $A=\left\{a\right\}$ and the set of marked-normal sensors becomes $N=\varnothing$. Next, to find the worst-case detection error loss (9) for this threshold, there are two possibilities for $tp$: (1) $tp=\left\{a\right\}$ and $fp=\varnothing$, and (2) $tp=\varnothing$ and $fp=\left\{a\right\}$. For $tp=\left\{a\right\}$, i.e., no detection error, we can write

$$C({\tau }_a^{\prime },\left\{a\right\},\varnothing ,\varnothing ,\varnothing )=TP\left({\tau }_a^{\prime }\right)·\left(J(p_a,U\left(p_a\right))-J(p_a,U\left(p_a\right))\right)=0.$$

For the second scenario, i.e., $tp=\varnothing$ and $fp=\left\{a\right\}$, we should have used the measurement $m_a$ but we used the prediction $p_a$, and so the expected utility loss is

$$C({\tau }_a^{\prime },\varnothing ,\left\{a\right\},\varnothing ,\varnothing )=FP\left({\tau }_a^{\prime }\right)·\left(J(m_a,U\left(m_a\right))-J(m_a,U\left(p_a\right))\right).$$

Therefore, the worst-case utility loss for the threshold ${\tau }_a^{\prime }$, where $r_a>{\tau }_a^{\prime }$, is obtained using

$$L\left({\tau }_a^{\prime }\right)=maxC({\tau }_a^{\prime },\varnothing ,\left\{a\right\},\varnothing ,\varnothing )=C(r_a^{-},\varnothing ,\left\{a\right\},\varnothing ,\varnothing )$$

Next, we consider a threshold ${\tau }_a^{″}$ such that $r_a\le {\tau }_a^{″}$. This threshold results in no detection alert, and so $A=\varnothing$ and $N=\left\{a\right\}$. To compute the worst-case detection error loss, there are two possibilities for detection error: (1) $tn=\left\{a\right\}$ and $fn=\varnothing$, and (2) $tn=\varnothing$ and $fn=\left\{a\right\}$. Similar to the above scenario, for the first case which corresponds to no detection error, we obtain $\Delta J=0$ and so $C({\tau }_a^{″},\varnothing ,\varnothing ,\left\{a\right\},\varnothing )=0$. For the second case, we obtain

$$C({\tau }_a^{″},\varnothing ,\varnothing ,\varnothing ,\left\{a\right\})=FN\left({\tau }_a^{″}\right)·\left(J(p_a,U\left(p_a\right))-J(p_a,U\left(m_a\right))\right).$$

Therefore, the worst-case detection error loss for the threshold ${\tau }_a^{″}$, where $r_a\le {\tau }_a^{″}$, is

$$L\left({\tau }_a^{″}\right)=maxC({\tau }_a^{″},\varnothing ,\varnothing ,\varnothing ,\left\{a\right\})=C(r_a,\varnothing ,\varnothing ,\varnothing ,\left\{a\right\}).$$

The application-aware detector selects the threshold ${\tau }_a^{\ast }\in \{r_a^{-},r_a\}$ that solves

$$min(C(r_a^{-},\varnothing ,\left\{a\right\},\varnothing ,\varnothing ),C(r_a,\varnothing ,\varnothing ,\varnothing ,\left\{a\right\})).$$

In other words, the optimal threshold is

$$\begin{array}{c}\hfill {\mathit{\tau }}_a=\left\{\begin{array}{cc}{r}_a^{-}\hfill & \mathrm{if}C(r_a^{-},\varnothing ,\left\{a\right\},\varnothing ,\varnothing )\le C(r_a,\varnothing ,\varnothing ,\varnothing ,\left\{a\right\})\hfill \\ r_a\hfill & \mathrm{otherwise}\hfill \end{array}\right..\end{array}$$

(13)

6.2. Detectors with Equal Thresholds

We consider a case where all detectors have equal thresholds. Let $\overline{\tau }$ represent this threshold value, that is, $\overline{\tau }={\tau }_1=\dots ={\tau }_d$. Next, let $r_1,r_2,\dots ,r_d$ be the residual values. The result below is a direct consequence of Lemma 1.

Corollary 1.

The optimal threshold $\overline{\tau }$ for detectors with equal thresholds belongs to the following set

$${SolutionSpace}=\{0,r_1^{-},r_1^{+},r_2^{-},r_2^{+}\dots ,r_d^{-},r_d^{+},M\}.$$

Based on the above corollary, since the solution space is finite, we can find the optimal thresholds by a linear-time search, as presented by Algorithm 5.

Algorithm 5 Application-Aware Detector for Equal Thresholds.

Input:$\mathit{m}$, $\mathit{p}$ 1: $\mathit{r}\leftarrow |\mathit{m}-\mathit{p}|$ 2: for all$\overline{\tau }\in \mathtt{SolutionSpace}$do 3:     $(L\left(\overline{\tau }\right),\overline{\tau })\leftarrow$Worst_Loss($\overline{\tau },\mathit{m},\mathit{p}$) 4: end for 5: ${\overline{\tau }}^{\ast }\leftarrow argmin(L\left(\overline{\tau }\right),\overline{\tau })$ 6: return${\overline{\tau }}^{\ast }$

7. Evaluation

In the preceding sections, we presented general computational results and general-purpose algorithms for the AAAD problem. In this section, to demonstrate the practical application of our AAAD framework, we provide numerical results on our running example. In particular, we apply our approach to a case study of max-pressure control of traffic signals in a traffic network. First, we construct regression-based anomaly detectors for traffic sensors, and we generate the trade-off curves for their performance. Then, we implement the AAAD approach, and evaluate its performance compared to a baseline “application-unaware” detector configuration. Throughout this section, we use SUMO (Simulation of Urban MObility), which is a micro simulator for traffic applications [27].

7.1. Traffic Network

Consider a traffic network in a 3-by-3 grid with a total of 9 intersections, as show in Figure 4. We perform our numerical evaluation in a simulated environment, where we have accurate ground truth regarding sensor faults. Each intersection connects 4 standard two-way lanes with four possible movements {EW, WE, NS, SN}, as shown in Figure 5. Traffic volume of each movement is monitored by the set of sensors $S=\{s_{EW},s_{WE},s_{NS},s_{SN}\}$. The sensors send traffic measurements $\mathit{m}=\{m_{EW},m_{WE},m_{NS},m_{SN}\}$ at each timestep. Each traffic signal has two phases $\Phi =\{{\varphi }_{\{EW,WE\}},{\varphi }_{\{NS,SN\}}\}$. The max-pressure controller computes the optimal stage $u^{\ast }\in \Phi$ using (2).

The utility (i.e., pressure-release) function of the traffic network can be written as sum of the pressure-release of each individual intersection, and for each intersection, the utility depends only on its corresponding lanes. This means that maximizing the pressure-release of the traffic network is equal to maximizing the pressure-release of individual intersections, and so the application-aware threshold of each intersection can be designed independently of other intersections. Based on this observation, in what follows, we discuss how the detector is designed for an intersection and then extend it to all intersections.

7.1.1. Anomaly Model

Traffic measurements may be anomalous due to failures or other undesired events. To simulate the negative effects of anomalies on the system, we consider several realistic anomaly models [28],

• Overcount: Additive error equal to $3\%$ to $7\%$ of the actual values, i.e., $e_s\left(k\right)=u_s{a}_s\left(k\right)$ and $0.03\le u_s\le 0.07$.
• Undercount: Subtractive error equal to $7\%$ to $13\%$ of the actual values, i.e., $e_s\left(k\right)=u_s{a}_s\left(k\right)$ and $-0.13\le u_s\le -0.07$.
• Gaussian Noise: Error with zero mean and standard deviation $\sigma =15$ to $\sigma =35$, i.e., $e_s\left(k\right)\sim \mathcal{N}(0,{\sigma }^2)$ and $15\le \sigma \le 35$.

7.2. Regression-Based Detector and Trade-Off Curves

To protect the system against anomalies, we construct anomaly detectors. We suppose there are 8 (2 on each side) redundant sensors that are adjacent to the four critical sensors mentioned above. We use the values of these sensors to design regression-based anomaly detectors for the critical sensors. As discussed in the preceding sections, such detector consists of two main components: (1) Predictor and (2) Statistical Test.

7.2.1. Predictor

We collect simulation data that represents the traffic behavior under normal operation. We simulate the network for 4 h considering a Poisson distribution as the demand for each movement. We collect sensor measurements in 10-s aggregates. The data from the first 2 h is used to train the predictors, and the data from the remaining 2 h is used to obtain the trade-off curves. Following our previous discussion, for each predictor, we use the current value of the 8 redundant sensors as the features. Then, we train the predictor using linear regression algorithm. We obtain the performance metrics $MS{E}_{train}=2.14$ and $MS{E}_{test}=2.87$. Please note that more complex regression algorithms (e.g., Gaussian Processes [24]) can be used as well; however, we obtained satisfactory result with a simple linear regression model.

7.2.2. Trade-off Curve

To generate the trade-off curve, first, we simulate the anomalies on the test data, and evaluate the performance of the detector by counting the number of true positives and false negatives. Similarly, we simulate the system under normal operation and evaluate the performance of the detector to obtain the number of true negatives and false positives. We repeat the steps while varying the detection threshold in order to obtain the trade-off curve (i.e., true positive probability as a function of false positive probability). Figure 6 shows the resulting trade-off curve.

7.3. Application-Aware Anomaly Detector

Given the trade-off curve, we implement the application-aware anomaly detector by finding the detection thresholds that minimize the worst-case expected utility loss. First, we show how the optimal threshold can be computed at each single timestep. Then, we present the results.

7.3.1. Computing the Optimal Threshold

To show how the optimal threshold is computed at each timestep, suppose $m_{NS}=p_{NS}=15$ at a given timestep. Further, suppose there is no traffic on $SN$ and $WE$. If $w_{EW}\ge 15$, the max-pressure controller selects the stage $u={\varphi }_{\{EW,WE\}}$, and otherwise, it selects $u={\varphi }_{\{NS,SN\}}$. Next, consider the following scenarios for $m_{EW}$ and $p_{EW}$:

• $m_{EW}=30$ and $p_{EW}=10$. In this case, the threshold that solves the following equation is the optimal threshold: $min\left(C({20}^{-},\varnothing ,\left\{s_{EW}\right\},\varnothing ,\varnothing ),C(20,\varnothing ,\varnothing ,\varnothing ,\left\{s_{EW}\right\})\right)$, where $C({20}^{-},\varnothing ,\left\{s_{EW}\right\},\varnothing ,\varnothing )=FP\left({20}^{-}\right)·\left(J^{\ast }\left(30\right)-J(30,U\left(10\right))\right)=30-15=15,$ and $C(20,\varnothing ,\varnothing ,\varnothing ,\left\{s_{EW}\right\})=FN\left(20\right)·\left(J^{\ast }\left(10\right))-J(10,U\left(30\right))\right)=15-10=5.$ Thus, the optimal threshold is ${\mathit{\tau }}^{\ast }=20$. To see why this is the optimal threshold, note that if $\mathit{\tau }=20$, then there will be no detection alert and the measurement ($m_{EW}=30$) will be used in computing the optimal control input (which is $EW$). If this is incorrect (due to a false negative), then $p_{SE}=10$ is the actual value. In this case, the pressure-release of ${\varphi }_{\{NS,SN\}}$ will be 10. In the perfect detection case (no detection error), we could have obtained 15 by selecting $NS$. Thus, the detection error loss is $15-10=5$. On the other hand, if $\mathit{\tau }={20}^{-}$, the prediction will be used by the controller. This results in the movement $NS$ being selected. However, if there is a false positive, which means $m_{EW}=30$ is the actual value, then $EW$ should have been selected as the optimal stage, which could have obtained a utility of 30. Thus, the utility loss in this case is $30-15=15$, which is larger than the utility loss for the other threshold.
• $m_{EW}=30$, $p_{EW}=10$, and $a_{NS}=25$. The application-aware detector computes the minimum of $F{P}^{-}\left(20\right)·\left(J^{\ast }\left(30\right)-J(30,U\left(10\right))\right)=30-25=5$, and $FN\left(20\right)·\left(J^{\ast }\left(10\right)-J(10,U\left(30\right))\right)=25-10=15$. In this case, the threshold $\mathit{\tau }={20}^{-}$ is the optimal threshold.
• $m_{EW}=30$, $p_{EW}=25$, and $a_{NS}=15$. The application-aware detector computes $FP\left({20}^{-}\right)·\left(J^{\ast }\left(30\right)-J(30,U\left(25\right))\right)=30-30=0$ and $FN\left(20\right)·\left(J^{\ast }\left(25\right)-J(25,U\left(30\right))\right)=25-25=0$, which means that both thresholds are optimal. The same results can be obtained if $a_{NS}\ge m_{EW}$ and $a_{NS}\ge p_{EW}$.

7.3.2. Comparison

We now compare our application-aware detector configuration to a baseline detector configuration, which does not take into account the underlying CPS application. For a fair comparison, the threshold of the baseline detector is selected such that it attains the same false-alarm probability as the application-aware anomaly detector. That is, we first calculate the total number of false alarms for the application-aware detector configuration, and then select the threshold that obtains the same false-alarm probability for the baseline configuration. In our numerical example, in 2 h of evaluation time during which each of the anomalies may occur with probability of $0.05$, each application-aware detector had on average a false-alarm probability of $0.047$. The threshold values for the application-aware detector varied from $1.3$ to $26.5$ with a mean of $5.6$. The threshold for the baseline detector was selected to be $3.9$.

Figure 7 shows the pressure-release comparison between the two cases during the 2-h interval. Each tick in the figure aggregates the results from 12 min (i.e., 72 timesteps). Based on the results, the application-aware detector performs better than the baseline detector in most cases. The baseline detector performs only slight better in the aggregated timestep at $0.8$, which could be due to detection errors by the application-aware detector. However, in the rest of the 2-h period, the proposed detector perform significantly better.

8. Conclusions

We presented the application-aware anomaly detection framework for detecting anomalies in sensor measurements in cyber-physical systems. An application-aware anomaly detector configures itself such that the application performance in the presence of detection errors is as close as possible to the performance that could have been obtained if there were no detection errors. We formulated and studied the problem of optimal, application-aware configuration of an existing detector. We evaluated our result using a case study of real-time control of traffic signals, and showed that our application-aware detector configuration significantly outperforms the baseline.