Using Bounded Binary Particle Swarm Optimization to Analyze Network Attack Graphs

Binary particle swarm optimization (BPSO) is a technique widely used to solve combinatorial problems. In this paper, we propose a variant of BPSO to find most likely attack paths in an attack graph. The aim is to find an attack path with the highest attack probability and least path length. In such combinatorial optimization problem, the set of feasible solutions is usually discrete and an exhaustive search may lead to unnecessary examination of those segments of the search space, which are assured to not include a solution. The paper introduces the concept of bounding the solution space of BPSO. The minimum and maximum value of each objective called bound of the solution is computed. The search space of BPSO is restricted within these solution bounds and hence we name our approach as bounded binary particle swarm optimization (BBPSO). By bounding the solution space, those particles of BPSO which are guaranteed to be infeasible are not considered for feasibility check. Experimental results show that the proposed approach provide a 50 percent performance improvement as compared to the conventional BPSO.