[go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v278y2019i3p894-903.html
   My bibliography  Save this article

Scalable min-max multi-objective cyber-security optimisation over probabilistic attack graphs

Author

Listed:
  • Khouzani, MHR.
  • Liu, Zhengliang
  • Malacaria, Pasquale
Abstract
We present a framework to efficiently solve a multi-objective optimisation problem for cyber-security defence. Facing an attacker who can mount a multi-stage attack (modelled using attack graphs), the defence problem is to select a portfolio of security controls which minimises the security risk and the (direct and indirect) costs of the portfolio of controls. The main challenges for the optimisation are: (a) the effect of the security controls is in general probabilistic, for example, the effect of staff anti-phishing training; moreover, some controls like taking regular back-ups do not have an attack-preventing effect, but rather, mitigate the losses of a successful attack; (b) each control may affect multiple vulnerabilities; and each vulnerability may be affected by multiple controls; (c) there can be a prohibitively large number of attack paths, each involving exploitation of different vulnerabilities. Our mathematical framework deals with all these problems. In particular, we model the problem as a min-max multi-objective optimisation. Using techniques such as ILP conversion, exact LP relaxation and dualisation, we convert the problem into a very efficient MILP. For instance, it returns the optimal solution for attack graphs with 20,000 nodes in less than four minutes typically.

Suggested Citation

  • Khouzani, MHR. & Liu, Zhengliang & Malacaria, Pasquale, 2019. "Scalable min-max multi-objective cyber-security optimisation over probabilistic attack graphs," European Journal of Operational Research, Elsevier, vol. 278(3), pages 894-903.
    • Handle: RePEc:eee:ejores:v:278:y:2019:i:3:p:894-903
    DOI: 10.1016/j.ejor.2019.04.035
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719303728
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.04.035?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Schilling, Andreas & Werners, Brigitte, 2016. "Optimal selection of IT security safeguards from an existing knowledge base," European Journal of Operational Research, Elsevier, vol. 248(1), pages 318-327.
    2. Akgün, Ibrahim & Tansel, Barbaros Ç. & Kevin Wood, R., 2011. "The multi-terminal maximum-flow network-interdiction problem," European Journal of Operational Research, Elsevier, vol. 211(2), pages 241-251, June.
    3. H. Donald Ratliff & G. Thomas Sicilia & S. H. Lubore, 1975. "Finding the n Most Vital Links in Flow Networks," Management Science, INFORMS, vol. 21(5), pages 531-539, January.
    4. J. Cole Smith & Churlzu Lim, 2008. "Algorithms for Network Interdiction and Fortification Games," Springer Optimization and Its Applications, in: Altannar Chinchuluun & Panos M. Pardalos & Athanasios Migdalas & Leonidas Pitsoulis (ed.), Pareto Optimality, Game Theory And Equilibria, pages 609-644, Springer.
    5. Baykal-Gürsoy, Melike & Duan, Zhe & Poor, H. Vincent & Garnaev, Andrey, 2014. "Infrastructure security games," European Journal of Operational Research, Elsevier, vol. 239(2), pages 469-478.
    6. Alan Washburn & Kevin Wood, 1995. "Two-Person Zero-Sum Games for Network Interdiction," Operations Research, INFORMS, vol. 43(2), pages 243-251, April.
    7. Altannar Chinchuluun & Panos Pardalos, 2007. "A survey of recent developments in multiobjective optimization," Annals of Operations Research, Springer, vol. 154(1), pages 29-50, October.
    8. Rakes, Terry R. & Deane, Jason K. & Paul Rees, Loren, 2012. "IT security planning under uncertainty for high-impact events," Omega, Elsevier, vol. 40(1), pages 79-88, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Fan, Lurong & Xu, Jiuping, 2020. "Authority–enterprise equilibrium based mixed subsidy mechanism for carbon reduction and energy utilization in the coalbed methane industry," Energy Policy, Elsevier, vol. 147(C).
    2. Da, Gaofeng & Xu, Maochao & Zhao, Peng, 2021. "Multivariate dependence among cyber risks based on L-hop propagation," Insurance: Mathematics and Economics, Elsevier, vol. 101(PB), pages 525-546.
    3. Răzvan Florea & Mitică Craus, 2022. "A Game-Theoretic Approach for Network Security Using Honeypots," Future Internet, MDPI, vol. 14(12), pages 1-15, November.
    4. Zhang, Xiaoyu & Xu, Maochao & Su, Jianxi & Zhao, Peng, 2023. "Structural models for fog computing based internet of things architectures with insurance and risk management applications," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1273-1291.
    5. Bhuiyan, Tanveer Hossain & Medal, Hugh R. & Nandi, Apurba K. & Halappanavar, Mahantesh, 2021. "Risk-averse bi-level stochastic network interdiction model for cyber-security risk management," International Journal of Critical Infrastructure Protection, Elsevier, vol. 32(C).
    6. Wang, Zhen & Li, Chaofan & Jin, Xing & Ding, Hong & Cui, Guanghai & Yu, Lanping, 2021. "Evolutionary dynamics of the interdependent security games on complex network," Applied Mathematics and Computation, Elsevier, vol. 399(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Lee, Sangjae & Costello, Francis Joseph & Lee, Kun Chang, 2021. "Hierarchical balanced scorecard-based organizational goals and the efficiency of controls processes," Journal of Business Research, Elsevier, vol. 132(C), pages 270-288.
    2. Smith, J. Cole & Song, Yongjia, 2020. "A survey of network interdiction models and algorithms," European Journal of Operational Research, Elsevier, vol. 283(3), pages 797-811.
    3. Michel Benaroch, 2018. "Real Options Models for Proactive Uncertainty-Reducing Mitigations and Applications in Cybersecurity Investment Decision Making," Information Systems Research, INFORMS, vol. 29(2), pages 315-340, June.
    4. Abumoslem Mohammadi & Javad Tayyebi, 2019. "Maximum Capacity Path Interdiction Problem with Fixed Costs," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(04), pages 1-21, August.
    5. Leitner, Markus & Ljubić, Ivana & Monaci, Michele & Sinnl, Markus & Tanınmış, Kübra, 2023. "An exact method for binary fortification games," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1026-1039.
    6. Schilling, Andreas & Werners, Brigitte, 2016. "Optimal selection of IT security safeguards from an existing knowledge base," European Journal of Operational Research, Elsevier, vol. 248(1), pages 318-327.
    7. Furini, Fabio & Ljubić, Ivana & Martin, Sébastien & San Segundo, Pablo, 2019. "The maximum clique interdiction problem," European Journal of Operational Research, Elsevier, vol. 277(1), pages 112-127.
    8. Hannah Lobban & Yasser Almoghathawi & Nazanin Tajik & Kash Barker, 2021. "Community vulnerability perspective on robust protection planning in interdependent infrastructure networks," Journal of Risk and Reliability, , vol. 235(5), pages 798-813, October.
    9. Sreekumaran, Harikrishnan & Hota, Ashish R. & Liu, Andrew L. & Uhan, Nelson A. & Sundaram, Shreyas, 2021. "Equilibrium strategies for multiple interdictors on a common network," European Journal of Operational Research, Elsevier, vol. 288(2), pages 523-538.
    10. Matteo Fischetti & Ivana Ljubić & Michele Monaci & Markus Sinnl, 2019. "Interdiction Games and Monotonicity, with Application to Knapsack Problems," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 390-410, April.
    11. Paul, Jomon A. & Zhang, Minjiao, 2021. "Decision support model for cybersecurity risk planning: A two-stage stochastic programming framework featuring firms, government, and attacker," European Journal of Operational Research, Elsevier, vol. 291(1), pages 349-364.
    12. Brian Lunday & Hanif Sherali, 2012. "Network interdiction to minimize the maximum probability of evasion with synergy between applied resources," Annals of Operations Research, Springer, vol. 196(1), pages 411-442, July.
    13. Shen, Yeming & Sharkey, Thomas C. & Szymanski, Boleslaw K. & Wallace, William (Al), 2021. "Interdicting interdependent contraband smuggling, money and money laundering networks," Socio-Economic Planning Sciences, Elsevier, vol. 78(C).
    14. Matthews, Logan R. & Gounaris, Chrysanthos E. & Kevrekidis, Ioannis G., 2019. "Designing networks with resiliency to edge failures using two-stage robust optimization," European Journal of Operational Research, Elsevier, vol. 279(3), pages 704-720.
    15. Tayyebi, Javad & Mitra, Ankan & Sefair, Jorge A., 2023. "The continuous maximum capacity path interdiction problem," European Journal of Operational Research, Elsevier, vol. 305(1), pages 38-52.
    16. Leonardo Lozano & J. Cole Smith, 2017. "A Backward Sampling Framework for Interdiction Problems with Fortification," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 123-139, February.
    17. Gabriele Dragotto & Amine Boukhtouta & Andrea Lodi & Mehdi Taobane, 2024. "The critical node game," Journal of Combinatorial Optimization, Springer, vol. 47(5), pages 1-20, July.
    18. Matteo Malavasi & Gareth W. Peters & Pavel V. Shevchenko & Stefan Truck & Jiwook Jang & Georgy Sofronov, 2021. "Cyber Risk Frequency, Severity and Insurance Viability," Papers 2111.03366, arXiv.org, revised Mar 2022.
    19. Laan, Corine M. & van der Mijden, Tom & Barros, Ana Isabel & Boucherie, Richard J. & Monsuur, Herman, 2017. "An interdiction game on a queueing network with multiple intruders," European Journal of Operational Research, Elsevier, vol. 260(3), pages 1069-1080.
    20. Duque, Daniel & Lozano, Leonardo & Medaglia, Andrés L., 2015. "An exact method for the biobjective shortest path problem for large-scale road networks," European Journal of Operational Research, Elsevier, vol. 242(3), pages 788-797.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:278:y:2019:i:3:p:894-903. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.