Optimization Algorithms for Cyber Security

My first foray into cyber security was a study of how to control virus outbreaks within a network. There has been a considerable amount of work done on how contagion spreads through a network; however, there is been much less work on how to design control strategies based on a network’s topology. One of my former Ph.D. students and I developed a compact integer programming formulation along with several heuristics for determining the links to block in a social network in order to minimize the number of connections between susceptible and infected persons.

I have also performed research on modeling cyber networks using a concept called an attack graph along with approaches for optimizing the allocation of resources to protect the graph. Our team has developed an approach that models a two-player game on the graph as a bi-level integer program with a binary inner problem. To overcome the non-convexity in the inner problem, we developed a customized solution approach. We have continued this work by including the concepts of bounded rationality; in addition, another Ph.D. student has incorporated conditional value-at-risk into the model.

In addition, I have also begun to develop big data analytic approaches for cyber security, focus on large-scale graph analytics. This work has been funded by the Pacific Northwest National Laboratory.

1. A stochastic programming model with endogenous uncertainty for proactive supplier risk mitigation of low-volume-high-value manufacturers considering decision-dependent supplier performance
   Rui Zhou, Bhuiyan, Tanveer Hossain, Michael Sherwin, and Medal, H.. Zhou, Rui, Tanveer Hossain Bhuiyan, Hugh R. Medal, Michael D. Sherwin, and Dong Yang. "A stochastic programming model with endogenous uncertainty for selecting supplier development programs to proactively mitigate supplier risk." Omega 107 (2022): 102542.
   Publication Year: 2022
   [Link to Article] Abstract
   Poor supplier performance can result in delays that disrupt manufacturing operations. By proactively managing supplier performance, the likelihood and severity of supplier risk can be minimized. In this paper, we study the problem of selecting optimal supplier development programs (SDPs) to improve suppliers’ performance with a limited budget to proactively reduce supplier risks for a manufacturer. A key feature of our research is that it incorporates the uncertainty in supplier performance in response to SDPs selection decisions. This uncertainty is endogenous (decision-dependent), as the probability of supplier performance depends on the selection of SDPs, which introduces modeling and algorithmic challenges. We formulate this problem as a two-stage stochastic program with decision-dependent uncertainty. We implement a sample-based greedy algorithm and an accelerated Benders’ decomposition method to solve the developed model. We evaluate our methodology using the numerical cases of four low-volume, high-value manufacturing firms. The results provide insights into the effects of the budget amount and of the number of SDPs on the firm’s expected profit. Numerical experiments demonstrate that an increase in budget results in profit growth, e.g., 5.09% profit growth for one firm. At a lower budget level, increasing the number of available SDPs results in more profit growth. The results also demonstrate the significance of considering uncertainty in supplier performance and considering multiple supplier risks for the firm. In addition, computational experiments demonstrate that our algorithms, especially our greedy approximation algorithm, can solve large-sized problems in a reasonable time.

2. Identifying and mitigating supply chain risks using fault tree optimization
   Sherwin, M., Brown, K. J., Medal, H., and Mackenzie, C.. Michael D. Sherwin, Hugh R. Medal, Cameron A. MacKenzie & Kennedy J. Brown (2020) Identifying and mitigating supply chain risks using fault tree optimization, IISE Transactions, 52:2, 236-254
   Publication Year: 2020
   [Link to Article] Abstract
   Although supply chain risk management and supply chain reliability are topics that have been studied extensively, a gap exists for solutions that take a systems approach to quantitative risk mitigation decision making and especially in industries that present unique risks. In practice, supply chain risk mitigation decisions are made in silos and are reactionary. In this article, we address these gaps by representing a supply chain as a system using a fault tree based on the bill of materials of the product being sourced. Viewing the supply chain as a system provides the basis to develop an approach that considers all suppliers within the supply chain as a portfolio of potential risks to be managed. Next, we propose a set of mathematical models to proactively and quantitatively identify and mitigate at-risk suppliers using enterprise available data with consideration for a firm’s budgetary constraints. Two approaches are investigated and demonstrated on actual problems experienced in industry. The examples presented focus on Low-Volume High-Value (LVHV) supply chains that are characterized by long lead times and a limited number of capable suppliers, which make them especially susceptible to disruption events that may cause delays in delivered products and subsequently increase the financial risk exposure of the firm. Although LVHV supply chains are used to demonstrate the methodology, the approach is applicable to other types of supply chains as well. Results are presented as a Pareto frontier and demonstrate the practical application of the methodology.

3. A stochastic programming model with endogenous and exogenous uncertainty for reliable network design under random disruption
   Bhuiyan, T. H. and Medal H.. Bhuiyan, T. H., Medal, H. R., & Harun, S. (2020). A stochastic programming model with endogenous and exogenous uncertainty for reliable network design under random disruption. European Journal of Operational Research, 285(2), 670-694.
   Publication Year: 2020
   [Link to Article] Abstract
   Designing and maintaining a reliable and efficient transportation network is an important industrial problem. Integrating infrastructure protection with the network design model is efficient as these models provide strategic decisions to make a transportation network simultaneously efficient and reliable. We studied a combined network design and infrastructure protection problem subject to random disruptions where the protection is imperfect and multi-level and the effect of disruption is imperfect. In this research, we modeled a resource-constrained decision maker seeking to optimally allocate protection resources to the facilities, and construct links in the network to minimize the expected post-disruption transportation cost (PDTC). We modeled the problem as a two-stage stochastic program with both endogenous and exogenous uncertainty: a facility’s post-disruption capacity depends probabilistically on the protection decision, making the uncertainty endogenous, while the link construction decision directly affects the transportation decision. We implemented an accelerated L-shaped algorithm to solve the model and predictive modeling techniques to estimate the probability of a facility’s post-disruption capacity for a given protection and disruption intensity. Numerical results show that solution quality is sensitive to the number of protection levels modeled; average reduction in the expected PDTC is 18.7% as the number of protection levels increases from 2 to 5. Results demonstrate that the mean value model performs very poorly as the uncertainty increases. Results also indicate that the stochastic programming model is sensitive to the estimation error of the predictive modeling techniques; on average the expected PDTC becomes 6.38% higher for using the least accurate prediction model.

4. A Model-Based Systems Engineering Approach to Critical Infrastructure Vulnerability Assessment and Decision Analysis
   Huff, J. D., Medal, H., and K. A. Griendling. Submitted to Systems Engineering 22(2), 114–133.
   Publication Year: 2019
   [Link to Article] Abstract
   Securing critical infrastructure against attack presents significant challenges. As new infrastructure is built and existing infrastructure is maintained, a method to assess the vulnerabilities and support decision makers in determining the best use of security resources is needed. In response to this need, this research develops a methodology for performing vulnerability assessment and decision analysis of critical infrastructure using model‐based systems engineering, an approach that has not been applied to this problem. The approach presented allows architects to link regulatory requirements, system architecture, subject matter expert opinion and attack vectors to a Department of Defense Architecture Framework (DoDAF)‐based model that allows decision makers to evaluate system vulnerability and determine alternatives to securing their systems based on their budget constraints. The decision analysis is done using an integer linear program that is integrated with DoDAF to provide solutions for how to allocate scarce security resources. Securing an electrical substation is used as an illustrative case study to demonstrate the methodology. The case study shows that the method presented here can be used to answer key questions, for example, what security resources should a decision maker invest in based on their budget constraints? Results show that the modeling and analysis approach provides a means to effectively evaluate the infrastructure vulnerability and presents a set of security alternatives for decision makers to choose from, based on their vulnerabilities and budget profile.


5. NATO Human View Executable Architectures for Critical Infrastructure Analysis
   Huff, J. D., Leonard, W., B. Smith, K. Griendling, and Medal, H.. Engineering Management Journal. 31:4, 224-245.
   Publication Year: 2019
   [Link to Article] Abstract
   Engineering managers are responsible for the secure operation of critical infrastructure systems and need tools and methods to identify and mitigate potential insider threats such as physical damage to equipment, information leakage, malware, and identify theft. This research examines the benefit of development and analysis of the NATO Human View to aid engineering managers with this responsibility. In an illustrative case study, the NATO Human View is used to analyze electrical grid personnel; the results demonstrate that the NATO Human View can be used to enable engineering managers to make investment decisions that can mitigate security threats.

6. Proactive Cost-Effective Risk Mitigation in a Low Volume High Value Supply Chain Using Fault-Tree Analysis
   Michael D. Sherwin, Hugh Medal, Steven A. Lapp. International Journal of Production Economics, Volume 175, Pages 153–163
   Publication Year: 2016
   [PDF]   [Link to Article] Abstract

   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.


7. A Bi-objective Analysis of the R-All-Neighbor P-Center Problem
   Hugh R. Medal, Chase E. Rainwater, Edward A. Pohl, Manuel D. Rossetti. Computers & Industrial Engineering, Volume 72, Pages 114–128
   Publication Year: 2014
   [PDF]   [Link to Article] Abstract

   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.


8. A Multi-objective Integrated Facility Location-Hardening Model: Analyzing the Pre- and Post-Disruption Tradeoff
   Hugh R. Medal, Edward A. Pohl, Manuel D. Rossetti. European Journal of Operational Research, Volume 237, 257– 270
   Publication Year: 2014
   [PDF]   [Link to Article] Abstract

   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.


9. Robust Facility Location: Hedging Against Failures
   Ivan Hernandez, Jose Emmanuel Ramirez-Marquez, Chase Rainwater, Edward Pohl, Hugh Medal. Reliability Engineering & System Safety, Volume 123, Pages 73–80
   Publication Year: 2014
   [PDF]   [Link to Article] Abstract
   While few companies would be willing to sacrifice day-to-day operations to hedge against disruptions, designing for robustness can yield solutions that perform well before and after failures have occurred. Through a multi-objective optimization approach this paper provides decision makers the option to trade-off total weighted distance before and after disruptions in the Facility Location Problem. Additionally, this approach allows decision makers to understand the impact on the opening of facilities on total distance and on system robustness (considering the system as the set of located facilities). This approach differs from previous studies in that hedging against failures is done without having to elicit facility failure probabilities concurrently without requiring the allocation of additional hardening/protections resources. The approach is applied to two datasets from the literature.

10. Vulnerability Assessment and Re-routing of Freight Trains Under Disruptions: A Coal Supply Chain Network Application
    Ridvan Gedik, Hugh Medal, Chase Rainwater, Ed A. Pohl, Scott J. Mason. Transportation Research Part E, Volume 71, 45–57
    Publication Year: 2014
    [PDF]   [Link to Article] Abstract

    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.


11. Models for reducing the risk of critical networked infrastructures
    Hugh Medal, Stevenson J. Sharp, Ed Pohl, Chase Rainwater, Scott J. Mason. International Journal of Risk Assessment and Management, Volume 15 (No. 2/3), Pages 99-127
    Publication Year: 2011
    [PDF]   [Link to Article] Abstract
    In this paper, we review the literature studying how to reduce the disruption risk to critical networked infrastructures. This is an important area of research because huge consequences result from infrastructure disruptions. As a result, this research area has grown a lot in the last decade. In this review we discuss articles from the literature, place them into categories, and suggest topics for future research. Our review shows that although this area is growing in popularity, there are still many important opportunities for future work.