Multi-objective evolutionary optimization of computation-intensive simulations - The case of security control selection
Elmar Kiesling, Andreas Ekelhart, Bernhard Grill, Christian Stummer, Christine Strauß · PUB – Publications at Bielefeld University (Bielefeld University) · 2015
Simulation-based optimization with multiple objectives is a challenging problem that is relevant in a broad range of application domains. A common characteristic of these problems is that they are computationally expensive because (i) the size of the search space is vast for nontrivial problem instances and (ii) the simulation-based evaluation of each candidate solution is runtime-intensive. Multi-objective evolutionary optimization algorithms tackle the first problem and can provide good approximations of the Pareto front even for large problem instances if the evaluation of an individual solution is not too expensive. However, these algorithms typically require a substantial number of computation-intensive evaluations (i.e. simulation runs) before they might converge. We encountered this issue in the context of a highly relevant practical application within the context of a multi-year research project on analyzing and improving the security of complex information systems. In this project, we combine conceptual modeling of security knowledge, behavioral modeling of threat agents, simulation of attacks, multi-objective evolutionary optimization, and interactive decision support (cf. Figure 1 for an overview). Our model includes a set of security controls (such as firewalls, patch policies, and employee trainings) that can be applied to a modeled target organization’s infrastructure. The simulation component evaluates the security of a given system configuration by performing repeatedly step-by-step attacks on the system following heterogeneous attackers’ particular objective(s). It delivers metrics such as the expected impact in terms of confidentiality, integrity and availability losses, detected intrusions, and monetary costs. We apply multi-objective evolutionary optimization techniques to determine Pareto-efficient portfolios of security controls based on the simulation outcomes (details can be found in [2]). Initial experiments showed that evaluating a single individual’s (i.e., a control portfolio’s) fitness based on the outcome of numerous simulation runs may require several seconds. In order to improve overall optimization runtime performance for this problem, we employ multiple levers. First, selecting an appropriate metaheuristic technique together with carefully tested parameter settings with suitable convergence properties is a crucial task. To this end, we conducted extensive experiments with multiple population-based metaheuristics and parameter settings. Second, due to the stochastic nature of the problem, each candidate solution must be evaluated via multiple simulation replications. In order to reduce the overall computational cost, we can hence reduce the (average) number of required simulation replications for each individual and/or reduce the runtime spent for each replication. Third, we can adapt the optimization to the problem at hand, e.g., by exploiting domain-knowledge on the genotype structure when creating an initial population. In the following, we discuss our ongoing work on approaches to mitigate these issues and identify good solutions in terms of fitness, convergence, and diversity.