...(vi) finance; (vii) government; and (viii) the emergency services. These systems constitute the "lifelines" of our civilization. Our economic prosperity and social well being is jeopardized when they are damaged, disrupted, or unable to function at adequate capacity.

The US water infrastructure system is a major national asset valued at approximately $675 billion (Grigg, 1999). In recent years, the federal government has promoted risk assessment analysis of water systems, disaster response training for water facility personnel, and research aimed at improving attack detection and mitigation (Ostfeld and Salomons, 2004). Most approaches have been highly subjective and qualitative, with relatively few quantitative methods being developed or proposed. Furthermore, most approaches focus on assessment and evaluation rather than security enhancement. In contrast, this research develops a quantitative method that allocates security resources to water distribution networks to maximize resilience to intentional attacks.

An intentional attack on the water infrastructure can be classified into one of three categories: (i) physical; (ii) cyber; and (iii) chemical/biological (Haimes et al., 1998). Physical attacks target pipes, pumping stations, water tanks, and other facilities. A successful physical attack will alter the system by destroying or degrading part of the network. Since water flow is governed by nonlinear hydraulic laws, the destruction of a well-selected set of components can easily cause far-reaching hydraulic infeasibilities that result in catastrophic disruption of the water service.

Cyber attacks target the Supervisory Control and Data Acquisition system, which is the information management system for the water infrastructure, with the aim of corrupting data and damaging computers. Chemical/biochemical attacks use the water network to spread life-threatening chemical or biological agents. Chemical and biological attack scenarios are the most feared threat to the water infrastructure because they can result in major public health crises, economic impacts, and long-lasting psychological effects. However, physical attack scenarios that destroy or disrupt a water system's components are far more likely because explosive materials are readily available and require a lower level of expertise compared to the development and deployment of contaminants (Burns et al., 2002; Murray et al., 2004). Furthermore, we note that human error and natural events can often result in accidental physical destruction. Thus, this research focuses on methods to make the water infrastructure more resilient to physical destruction.

To our knowledge, the research presented in this paper is the first quantitative work that addresses the optimal allocation of security resources in a water distribution system. We believe the specific contributions of this work include:

1. An extensive literature review on mitigation strategies for networked infrastructures subject to intentional attack, natural disaster, and random failure.

2. A resilience measure integrating security cost and attack consequences.

3. A model for optimally allocating a security budget to a water distribution system.

4. An exact solution procedure that integrates optimization procedures with hydraulic simulation.

5. A heuristic method that generates constraints for the optimization procedure.

6. A benchmarking study of security allocation and resilience enhancement on a real-world network.

The paper is organized as follows. Section 2 reviews the literature on network resilience, criticality identification, and security enhancement. Section 3 then describes our assumptions and defines our problem statement. Section 4 presents our mathematical model along with a solution approach. The model is a linear program with an exponential number of constraints that uses hydraulic simulation to compute constraint coefficients. A genetic algorithm is used to iteratively generate constraints. Section 5 provides experimental results that benchmark our solution approach on two example networks, one small network taken from the literature and one large network obtained from one of our industrial research collaborators. Finally, Section 6 provides conclusions and discussions on future research.

2. Literature review

This section describes existing research that is related to physical attacks on networks. These problems arise in a variety of areas, including telecommunications, supply chains, and transportation networks. We classify the literature as relating to resilience measurement, criticality identification, and security enhancement. Resilience measurement evaluates a network's resistance to attack and potential attack consequences. Criticality identification detects those network components whose removal or degradation may result in significant negative consequences. Security enhancement increases resilience by modifying system topology and/or allocating available resources to protect arcs and nodes. We now discuss these categories in more detail.

2.1. Resilience measurement

Resilience measurement assesses adverse consequences and evaluates network resistance to attacks, failures, and disasters. Post-attack consequences are measured by the maximum flow, shortest path, network connectivity, interconnectedness, and/or the strength of the residual network. Most capacitated network problems, such as those in transportation, supply chains, and telecommunications networks, use maximum flow as a measure of resilience (McMasters and Mustin, 1970; Ghare et al., 1971; Phillips, 1993; Wood, 1993; Cormican et al., 1998), whereas time-based or distance-based network problems tend to use the shortest path to measure resilience (Golden, 1978; Corley and Sha, 1982; Ball et al., 1988; Israeli and Wood, 2002; Pan et al., 2002).

Network connectivity is commonly used in the design of telecommunications networks. Network connectivity is defined as the size of the smallest cut-set of the graph N = (V, E), the minimum number of arcs to remove before disconnecting N (Grotschel et al., 1995). That is, [phi](N) = min {|A|: A [??] E and [omega] (E - A) > 1}, where [omega](E - A) is the number of components obtained by the removal of A. By Menger's theorem (Menger, 1927), [phi](N) is also the maximum number of internally disjoint paths in N. Grotschel et al. (1995) provides a comprehensive discussion on minimum cost k-connected network design problems.

Interconnectedness is often used in the design and evaluation of computer and social networks. It is defined as the average shortest path over all pairs of nodes (Albert et al., 2000; Holme et al., 2002), that is:

l = [1/[|V|(|V| - 1)]] [summation over (v[member of]V)] [summation over (w[not equal to]v[member of]V)] d(v, w),

where v and w are unique nodes belonging to node set, V, and d(v, w) represents the shortest path length between v and w.

Graph strength is a useful concept in network security enhancement. It is the minimum average effort per new component created: [sigma](N, s) = min{s(A)/[omega](E - A): A [??] E, [omega](E - A) > 0}, where s(A) is a function returning the effort required to destroy edge subset A, and [omega](E - A) is defined above (Gusfield, 1983; Cunningham, 1985). Assuming unit costs to improve the edge strength, it is possible to define a security reinforcement problem from the perspective of network defenders whose goal is to find a minimum-cost allocation of edge strengths that increases the graph strength above a given threshold. This problem can be solved in polynomial time (Cunningham, 1985).

2.2. Criticality identification

Criticality identification detects those network components whose removal would seriously affect the operation of the network. This is the attacker's problem: organizing a budgeted attack that inflicts as much damage as possible. This family of problems is known...

NOTE: All illustrations and photos have been removed from this article.



More articles from IIE Transactions
Rebate, returns and price protection policies in channel coordination., February 01, 2007
Hierarchical cross-training in work-in-process-constrained systems.(Au..., February 01, 2007
Risk, risk aversion and the optimal time to produce.(Author abstract), February 01, 2007
Benefits of considering inventory in service parts logistics network d..., February 01, 2007
Strategic network design for multi-zone truckload shipments.(Author ab..., February 01, 2007

Looking for additional articles?
Search our database of over 3 million articles.

Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication name or publication date.

About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.

Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information.