School of Electronic Engineering and Computer Science

News & Events menu

Seminar: Theory Research Group

15 May 2018

Time: 11:00am - 12:00pm
Venue: ITL top floor, Queen Mary University of London

Scalable bi-level multi-objective cyber security optimisation over probabilistic attack graphs

Speaker: Ethan Liu

In this paper, we present a framework that efficiently solves a multi-objective optimization problem for cyber-security defence. Given an attack graph, and a set of possible security controls each mitigating attack steps (edges) in the attack graph our optimization select a portfolio of security controls which minimizes the security risk and the (direct and indirect) costs of the portfolio of controls.

This is a challenging multi-criteria decision problem: there are many counter-measures to choose from, each affecting a certain subset of vulnerabilities in different ways. Specifically, the reduction in the cyber-security risks should be balanced with their monetary costs as well as the negative operational side-effects of the counter-measures.
Among the challenging aspects of the problem are:
(a) the defensive effect of counter-measures is in general probabilistic, e.g. the effect of staff anti-phishing training; moreover, some counter-measures like taking regular back-ups does not have an attack-preventing effect, but rather, mitigate the losses of a successful attack; (b) each counter-measure may affect multiple vulnerabilities; and each vulnerability may be affected by multiple counter-measures; (c) there can be a prohibitively large number of attack paths, each involving exploitation of different vulnerabilities;
(d) the choice of security controls affects the attack graph, and hence, the optimal choice of security measures is coupled with the problem of risk assessment. Our mathematical framework is flexible and powerful enough to deal with all these problems.

In particular, we model the problem as a bi-level multi-objective optimisation. Using non-trivial techniques such as ILP conversion, exact LP relaxation, and dualization, we convert the problem into a very efficient MILP optimization. For instance, it returns the optimal solution for attack graphs with 2550 attack paths in under 3 minutes.

Directions, if coming from outside QMUL

Queen Mary is on Mile End Road, with nearest tube stations being Stepney Green (closest one to the seminars) and Mile End. The seminars are in the Informatics Teaching Laboratory, floor 2.  As the building has card access, it is best to inform us that you will be coming.

Return to top