Dynamic probing for intrusion detection under resource constraints

We consider a large-scale cyber network with N components. Each component is either in a healthy state or an abnormal state. To model scenarios where attacks to the network may not follow a stochastic process and the attackers may adapt to the actions of the intrusion detection system (IDS) in an arbitrary and unknown way, we adopt a non-stochastic model in which the attack process at each component can be any unknown deterministic sequence. Due to resource constraints, the IDS can only choose K (K < N) components to probe at each time. An abnormal component incurs a cost per unit time (depending on the criticality of the component) until it is probed and fixed. The objective is a dynamic probing strategy under the performance measure of regret, defined as the performance loss compared to that of a genie who knows the entire attack processes a priori and probes optimally (under certain constraints) based on this knowledge. We propose a policy that achieves sublinear regret order, thus offers the same time averaged performance as that of the omniscient genie.