QM Logo Fabrizio

Mebomine Logo

How to spend it: optimal investment for cyber security

Fabrizio Smeraldi and Pasquale Malacaria, 1st International Workshop on Agents and Cybersecurity (ACySe2014), Paris (France), May 5th 2014


A basic cyber security problem is how to optimally spend a security budget. We cast this problem in the framework of combinatorial optimization and explore its relationship with the classical knapsack problem. As in the latter, given a budget, we wish to optimally select a set of resources, each having a cost and a benefit. We propose optimisation algorithms that can deal with resources that depend non linearly on each other, and an optimal budget allocation algorithm for the case of several targets covered by target-specific resources. The general case of resources each of which benefits multiple targets leads to the multiple objective knapsack problem. Also in this case, we extend the standard dynamic programming solution to deal with non-linear dependencies between resources.

Full paper (PDF)

Backlinks: Publications