Publications

We present an approach for measuring the vulnerability of a wireless network. Our metric, n-Robustness, measures the change in a network’s total signal strength resulting from the optimal placement of n jammers by an attacker. Toward this end, we develop a multi-period mixed-integer programming interdiction model that determines the movement of n jammers over a time horizon so as to minimize the total signal strength of users during a sustained jamming attack. We compared several solution approaches for solving our model including a Lagrangian relaxation heuristic, a genetic algorithm, and a stage decomposition heuristic. We tested our approach on a wireless trace dataset developed as part of the Wireless Topology Discovery project at the University of California San Diego. We found that the Lagrangian approach, which performed best overall, finds a close-to-optimal solution while requiring much less time than solving the MIP directly. We then illustrate the behavior of our model on a small example taken from the dataset as well as a set of experiments. Through our experiments we conclude that the total signal power follows a sigmoid curve as we increase the number of jammers and access points. We also found that increasing access points only improves network robustness initially; after that the benefit levels off. In addition, we found that the problem instances we considered have an n-Robustness of between 39 and 69%, indicating that the value of the model parameters (e.g., number of jammers, number of time periods) has an effect on robustness.

In this research, we study the vulnerability of landscapes to wildfires based on the impact of the worst-case scenario ignition locations. Using this scenario, we model wildfires that cause the largest damage to a landscape over a given time horizon. The landscape is modeled as a grid network, and the spread of wildfire is modeled using the minimum travel time model. To assess the impact of a wildfire in the worst-case scenario, we develop a mathematical programming model to optimally locate the ignition points so that the resulting wildfire results in the maximum damage. We compare the impacts of the worst-case wildfires (with optimally located ignition points) with the impacts of wildfires with randomly located ignition points on three landscape test cases clipped out from three national forests located in the western U.S. Our results indicate that the worst-case wildfires, on average, have more than twice the impact on landscapes than wildfires with randomly located ignition points.

Defense against jamming attacks has been an increasing concern for the military and disaster response authorities. The military uses jamming attacks as a tool to attack and disrupt terrorist׳s communications, because the open nature of wireless networks makes them vulnerable to various attacks. Many studies and a few survey papers are available in the literature, but none of these papers classify the attacks or the defense strategies by the type of wireless network affected, the attacker or defender׳s perspective, the type of game used to model the problem, such as Bayesian game, Stackelberg game, or the type of solution methodology, such as mathematical programming model and algorithm. This paper provides a comprehensive survey and a taxonomic classification to help interested researchers find the gaps in the literature and guide them to research areas that need to be explored.

In this paper we use a well-accepted methodology, fault-tree analysis, to identify delay risks and proactively propose a cost-effective mitigation strategy within a low volume high value supply chain. The basis for the assessment is the bill of materials of the product being studied. The top-level event of interest represents the delay in delivering a product to a customer and lower-level events represent the probabilities associated with delays caused by quality and capability deficiencies within the supply chain of the product being studied. Supply chain risk mitigation strategies have been well documented in academic literature. However, much of what has been documented addresses such topics as facility location, inventory buffers, and is generally focused on response strategies once the risk has been realized. This paper presents a robust method to reduce the likelihood of delays in material flow by representing the system of suppliers within a supply chain as a fault-tree and proactively determining the optimum mitigation strategy for the portfolio. The approach is illustrated via real-world numerical scenarios based on hypothetical data sets and the results are presented.

We study the effect that installing sidewalks and crosswalks, as traffic calming facilities, has on the safety and usability of a transportation network with automobile, public transit and walking as modes of transportation. A mathematical programming model is proposed for this problem whose objective is to minimize the safety hazard for pedestrians and the total transportation cost of the network. We utilize a customized greedy heuristic and a simulated annealing algorithm for solving the problem. The computational results indicate that installing sidewalks and crosswalks at proper locations can reduce the overall transportation cost and improve pedestrians’ safety.

Today's organizations are inherently open and connected, sharing knowledge and ideas in order to remain innovative. As a result, these organizations are also more vulnerable to information theft through different forms of security breaches caused by hackers and competitors. One way of understanding the vulnerability of an information system is to build and analyze the attack graph of that system. The attack graph of an information system contains all the paths that can be used to penetrate the system in order to breach critical assets. Although existing literature provides an abundance of attack graph generation algorithms, more methods are required to help analyze the attack graphs. In this paper, we study how best to deploy security countermeasures to protect an organization by analyzing the vulnerability of the organization through the use of its attack graph. In particular, we present an approach to find an optimal affordable subset of arcs, called an interdiction plan, on an attack graph that should be protected from attack to minimize the loss due to security breaches. We formulate this problem as a bi-level mixed-integer linear program and develop an exact algorithm to solve it. Experiments show that the algorithm is able to solve relatively large problems. Two heuristic methods, one with and the other without a heuristic to solve the master problem and both limiting the master problem branch-and-bound tree to only one node solve the large problems remarkably well. Experiments also reveal that the quality of an interdiction plan is relatively insensitive with respect to the error in the estimate of the attacker's budget, and that the breach loss drops sharply at the beginning, then levels off before finally dropping sharply again with increases in the security budget.

Minimizing the spread of infections is a challenging problem, and it is the subject matter in many different fields such as epidemiology and cyber-security. In this paper, we investigate link removal as an intervention strategy and study the relative effectiveness of different link removal methods in minimizing the spread of infections in a network. With that in mind, we develop four connectivity-based network interdiction models and formulate these models as mixed integer linear programs. The first model minimizes the number of connections between infected and susceptible nodes; the second the number of susceptible nodes having one or more connections with infected nodes; the third the total number of paths between infected and susceptible nodes; and the fourth the total weight of the paths between infected and susceptible nodes. We also propose heuristic algorithms to solve the models. The network interdiction models act as link removal methods, i.e., each return a solution consisting of a set of links to remove in the network. We compare the effectiveness of these four methods with the effectiveness of an existing link removal method, a method based on link betweenness centrality, and random link removal method. Our results show that complete isolation of susceptible nodes from infected nodes is the most effective method in reducing the average number of new infections (reduce occurrence) under most scenarios, and the relative effectiveness of the complete isolation method increases with transmission probability. In contrast, removing the highest probability transmission paths is the most effective method in increasing the average time to infect half of the susceptible nodes (reduce speed) under most scenarios, and the relative effectiveness of this method decreases with transmission probability.

In this paper we consider a generalization of the p-center problem called the r-all-neighbor p-center problem (RANPCP). The objective of the RANPCP is to minimize the maximum distance from a demand point to its r  th-closest located facility. The RANPCP is applicable to facility location with disruptions because it considers the maximum transportation distance after (r-1) facilities are disrupted. While this problem has been studied from a single-objective perspective, this paper studies two bi-objective versions. The main contributions of this paper are (1) algorithms for computing the Pareto-efficient sets for two pairs of objectives (closest distance vs rth-closest distance and cost vs. rth-closest distance) and (2) an empirical analysis that gives several useful insights into the RANPCP. Based on the empirical results, the RANPCP produces solutions that not only minimize vulnerability but also perform reasonably well when disruptions do not occur. In contrast, if disruptions are not considered when locating facilities, the consequence due to facility disruptions is much higher, on average, than if disruptions had been considered. Thus, our results show the importance of optimizing for vulnerability. Therefore, we recommend a bi-objective analysis.

Two methods of reducing the risk of disruptions to distribution systems are (1) strategically locating facilities to mitigate against disruptions and (2) hardening facilities. These two activities have been treated separately in most of the academic literature. This article integrates facility location and facility hardening decisions by studying the minimax facility location and hardening problem (MFLHP), which seeks to minimize the maximum distance from a demand point to its closest located facility after facility disruptions. The formulation assumes that the decision maker is risk averse and thus interested in mitigating against the facility disruption scenario with the largest consequence, an objective that is appropriate for modeling facility interdiction. By taking advantage of the MFLHP’s structure, a natural three-stage formulation is reformulated as a single-stage mixed-integer program (MIP). Rather than solving the MIP directly, the MFLHP can be decomposed into sub-problems and solved using a binary search algorithm. This binary search algorithm is the basis for a multi-objective algorithm, which computes the Pareto-efficient set for the pre- and post-disruption maximum distance. The multi-objective algorithm is illustrated in a numerical example, and experimental results are presented that analyze the tradeoff between objectives.

In this paper, we present a two-stage mixed integer programming (MIP) interdiction model in which an interdictor chooses a limited amount of elements to attack first on a given network, and then an operator dispatches trains through the residual network. Our MIP model explicitly incorporates discrete unit flows of trains on the rail network with time-variant capacities. A real coal rail transportation network is used in order to generate scenarios to provide tactical and operational level vulnerability assessment analysis including rerouting decisions, travel and delay costs analysis, and the frequency of interdictions of facilities for the dynamic rail system.