Models for Assessing Vulnerability in Imperfect Sensor Networks

We examine a directed network on which sensors exist at a subset of the nodes. At each node, a target (e.g., an intruder in a physical network, a fire in a building, or a virus in a computer network) may or may not exist. Sensors detect the presence of these targets by monitoring the nodes at which they are located and all nodes adjacent from their positions. However, in practical settings a limited-cardinality subset of sensors might fail. A failed sensor may report false positives or negatives and, as a result, the network owner may not be able to ascertain whether or not targets exist at some nodes. If it is not possible to deduce whether or not a target exists at a node with a given set of sensor readings, then the node is said to be ambiguous. We show that a network owner must solve a series of combinatorial optimization problems to determine which nodes are ambiguous. Furthermore, we determine the worst-case number of ambiguous nodes by optimizing over the set of all sensor readings that could possibly arise. We also present mathematical programming formulations for these problems under varying assumptions on how sensors fail, and on what assumptions a network owner makes on how sensors fail. Our computational results illustrate how these varying assumptions impact the number of ambiguous nodes.