# Low-Cost Active Anomaly Detection with Switching Latency
## 2 System Model and Problem Formulation  
### System Model  
Consider the problem of detecting \(L\) abnormal processes among \(M\) processes. Each process may be in a normal state (denoted by \(H_{0}\)) or an abnormal state (denoted by \(H_{1}\)). Process \(m\) is abnormal with a priori probability \(\pi_{m}\), while process \(m\) is in a normal state with a priori probability \(1-\pi_{m}\). Let  
\[\mathcal{H}_{0} \triangleq\{m:1\leq m\leq M,\text{process $m$ is normal}\},\] \[\mathcal{H}_{1} \triangleq\{m:1\leq m\leq M,\text{process $m$ is abnormal}\}\]  
be the set of normal and abnormal processes, respectively. Each abnormal process \(m\) incurs a cost \(c_{m}(0\leq c_{m}\leq\infty)\) per unit time until its state has been identified, while the normal processes do not incur any cost. We focus on the case where \(c_{m}\) is the same for each abnormal process, in another word, \(c_{m}=c\) holds for all abnormal processes. The detection procedure starts at time \(n=0\) and the decision-maker can choose one process to probe at each time. Let \(\phi(n)\in\{1,2,\cdots,M\}\) be the selection rule indicating which process is chosen to be probed at time \(n\). The time series vector of selection rules can be denoted by \(\boldsymbol{\phi}=(\phi(n),n\geq 0)\). When process \(m\) is probed at time \(n\), an observation \(y_{m}(n)\) is obtained from a distribution and is independent over time. If process \(m\) is in a normal state, the observation \(y_{m}(n)\) follows distribution \(f(y)\); if process \(m\) is in an abnormal state, the observation \(y_{m}(n)\) follows distribution \(g(y)\). In this paper, we focus on the case where the distributions \(f(y)\) and \(g(y)\) are completely known. In practice, we can obtain the distribution \(f(y)\) by observing the normal processes and analyzing the observation data. As for the distribution \(g(y)\) of anomalies, it can be roughly judged based on experience. For example, consider the anomaly detection problem among a cyber system. An IDS monitors the traffic over the normal components and takes the packet size values that have arrived in a given interval as statistics. By data analysis, we can know that the observations from normal processes follow a certain distribution. Furthermore, it is known that DoS attacks aim to flood the target component with massive useless traffic. Thus the observations of the process being attacked by DoS will follow a distribution with a large mean. To detect the anomalies, we can assume that the observations from abnormal processes follow a prior distribution of interest. Then, it can be considered that the distribution is known. We define the stopping time \(\tau_{m}\), which is counted from the beginning of the entire detection procedure, as the time when the state of process \(m\) is declared and the decision-maker stops probing the process \(m\). The vector of stopping times for \(M\) processes can be denoted by \(\mathbf{\tau}=(\tau_{1},...,\tau_{M})\). We define the stage of the detection procedure as the period time between the stopping times of two processes whose states are successively declared. Besides, the stopping time of the entire detection procedure is denoted by \(\tau_{end}\), which means all the abnormal processes have been identified. We define \(\delta_{m}\in\{0,1\}\) as the decision rule that the decision-maker uses to declare the state of process \(m\) at stopping time \(\tau_{m}\). We have \(\delta_{m}=0\) if the decision-maker declares that process \(m\) is in a normal state, while \(\delta_{m}=1\) if the decision-maker declares that process \(m\) is in an abnormal state. Let \(N_{m}\) be the random sample size required to declare the state of process \(m\). Let \(\delta_{end}\) denote the final decision rule that the decision-maker uses to declare the set of anomalies at the stopping time \(\tau_{end}\). The abnormal process \(m\) continues incurring costs until its states are identified at the corresponding stopping time \(\tau_{m}\).