Adversaries In Networks

As systems become more distributed, they are vulnerable to new forms of attack. An adversary could seize control of several nodes in a network and reprogram them, unbeknownst to the rest of the network. Strategies are needed that can ensure robust performance in the presence of these sorts of attacks. This thesis studies the adversarial problem in three scenarios. First is the problem of network coding, in which a source seeks to send data to a destination through a network of intermediate nodes that may perform arbitrarily complicated coding functions. When an adversary controls nodes in the network, achievable rates and upper bounds on capacity are found, and Polytope Codes are introduced, which are a nonlinear class of codes specially designed to handle adversaries in a network coding framework. Second, multiterminal source coding is studied, in which several nodes make correlated measurements, independently encode them, and transmit their encodings to a common decoder, which attempts to recover some information. Two special cases of this problem are studied when several of the nodes may be controlled by an adversary: the problem of Slepian and Wolf, in which the decoder attempts to perfectly decode all measurements, and the CEO Problem, in which the decoder attempts to estimate a source correlated with the measurements. Finally, adversarial attacks are studied against power system sensing and estimation. In this problem, a control center receives various measurements from meters in a power grid, and attempts to recover information about the state of the system. Attacks of various degrees of severity are studied, as well as countermeasures that the control center may employ to prevent these attacks