Robust detection in the presence of integrity attacks

We consider the estimation of a binary random variable based on m noisy measurements that can be manipulated by an attacker. The attacker is assumed to have full information about the true value of the variable to be estimated and about the value of all the measurements. However, the attacker has limited resources and can only manipulate n of the m measurements. The problem is formulated as a minimax optimization, where one seeks to construct an optimal detector that minimizes the worst-case probability of error against all possible manipulations by the attacker. We show that if the attacker can manipulate at least half the measurements (n m/2) then the optimal worst-case estimator should ignore all m measurements and be based solely on the a-priori information. When the attacker can manipulate less than half the measurements (n m/2), we show that the optimal estimator is a threshold rule based on a Hamminglike distance between the (manipulated) measurement vector and two appropriately defined sets. For the special case where m 2n 1, our results provide a constructive procedure for the optimal estimator.