  The resilience of Supervisory Control and Data Acquisition (SCADA) systems
for electric power networks for certain cyber-attacks is considered. We analyze
the vulnerability of the measurement system to false data attack on
communicated measurements. The vulnerability analysis problem is shown to be
NP-hard, meaning that unless $P = NP$ there is no polynomial time algorithm to
analyze the vulnerability of the system. Nevertheless, we identify situations,
such as the full measurement case, where it can be solved efficiently. In such
cases, we show indeed that the problem can be cast as a generalization of the
minimum cut problem involving costly nodes. We further show that it can be
reformulated as a standard minimum cut problem (without costly nodes) on a
modified graph of proportional size. An important consequence of this result is
that our approach provides the first exact efficient algorithm for the
vulnerability analysis problem under the full measurement assumption.
Furthermore, our approach also provides an efficient heuristic algorithm for
the general NP-hard problem. Our results are illustrated by numerical studies
on benchmark systems including the IEEE 118-bus system.
