\documentclass[11pt]{article}
\begin{document}
\title{A Network Diversion Vulnerability Problem}
\author{Ariel Cintron-Arias \thanks{Cornell University, email: ac103@cornell.edu}
\and Norman Curet\thanks{National Security Agency, email:
curet@math.umbc.edu} \and Lisa Denogean \thanks{Cornell
University, email: lrd8@cornell.edu} \and Robert
Ellis\thanks{University of California, San Diego, email:
rellis@math.ucsd.edu} \and Corey Gonzalez\thanks{University of
Maryland, email: corey@wam.umd.edu} \and  Shobha Oruganti
\thanks{Mississippi State University, email:
so1@math.msstate.edu} \and Patrick Quillen\thanks{University of
Kentucky, email: quillen@ms.uky.edu}} \maketitle

\pagestyle{myheadings}

\section{Introduction} This paper is concerned with analyzing the
susceptibility of a communications network to a specific type of attack.
Attacks may consist of
physically disabling communication links or flooding links with
information in order to prevent legitimate communications.
Large-scale denial of service attacks have been prevalent in recent years,
affecting many commercial and e-commerce sites \cite{web1}.

We focus on network diversion attacks that disable network links
and force information to flow across one or more specified
``diversionary links''.  A diversionary link may be identified as
a link that is especially vulnerable in the network, possibly
susceptible to tapping or other malice from outside sources.  Our
goal is to compute the minimum amount of resources needed to
launch a successful diversion attack in order to determine the
network's vulnerability.  Our paper's contribution is to develop
a methodology for analyzing this vulnerability. The end result is
an automated procedure that can be employed as a high-level
strategic network analysis tool \cite{c00}.

We model a given network as a directed graph containing a set of
nodes and arcs. Each arc contains a cost parameter indicating the
amount of resources required to disable or ``cut'' that arc from
the network. Given a specified source node representing the
transmission point and a sink node representing the reception
point of communication through the network, we would like to
determine a minimum cost set of arcs to cut that forces all
flow from source to sink across at least one arc in a specified
diversion set. In this paper we consider one diversionary arc and
formulate this problem as an integer linear programming (IP) model.

Unfortunately, general purpose integer programming techniques are
ineffective in providing a solution to the network diversion problem
\cite{c00}. Difficulties arise when we consider large networks
consisting of thousands of nodes and links due to the
combinatorial explosion of feasible solutions in the search space.
The main contribution of this paper is to offer a decomposition
algorithm that is capable of exploiting the special structure of
the underlying integer programming model. While, in general,
integer programming problems are NP-hard, we found that good
solutions can be found efficiently through our Lagrangian
Relaxation decomposition algorithm. Indeed, in some instances,
the solutions we found were provably optimal.