Finding Multi-step Attacks in Computer Networks using Heuristic Search and Mobile Ambients

An important aspect of IT security governance is the proactive and continuous identification of possible attacks in computer networks. This is complicated due to the complexity and size of networks, and due to the fact that usually network attacks are performed in several steps. This thesis proposes an approach called MsAMS (Multi-step Attack Modelling and Simulation), demonstrated by a proof-of-concept tool, to automatically find such multi-step attacks. The novelty of MsAMS is the fact that it applies Mobile Ambients and Combinatorial Optimization, more specifically Heuristic Search, to the domain of multi-step network attacks. A variant of ambient calculus is used to model networks, and heuristic search is used to simulate attackers searching for possible attacks in the modelled network. Additionally, and in support to these two aspects, MsAMS uses algorithms from the domain of Link Analysis Ranking, traditionally applied to the domain of Web search. Mobile Ambients allow us to fully represent the hierarchical topology of a network as part of the network model itself. This is essential to relate insights gained from the model to the real network. Furthermore, we can represent dynamics of attacks such as credential theft, what increases the spectrum of possibilities available for attackers since it allows considering non-vulnerable as well as vulnerable hosts as attack steps. Optimization allows managing the complexity of the problem of finding multi-step attacks involving credentials without compromising the scalability of the approach for practical use. Therefore, the MsAMS approach comprises: (i) a formal representation of the solution which allows its automatic computation, in our case, the representation of an attack step in a notation based on Mobile Ambients, (ii) a search engine which implements a heuristic method for composing attack steps into multi-step attacks, and (iii) fitness functions used by the search engine for the selection of attack steps among alternatives, according to automatically computed metrics. Similar to search engines that use the structure of the World Wide Web to score webpages, the MsAMS approach proposes the use of the structure of a network to score network assets. In particular, MsAMS uses PageRank and HITS ranking schemes as sources of scalable metrics to: 1. assign asset value automatically to all ambients represented in the network, based on network connectivity rather than on financial value, providing an absolute and comparable view of asset value. Those values support the network administrator in the process of selecting a target. 2. assign a cost value automatically to all ambients represented in the network, also based on network connectivity rather than on financial value, providing an absolute and comparable view of cost for attack steps. Such a measure of cost allows the incorporation of rationality to the ambient-attacker which simulates a strategy of a real-attacker.