finding multi-step attacks in computer networks using heuristic search and mobile ambients
Virginia N. L. Franqueira · 2009
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 an 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 multistep 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.v SamenvattingEen belangrijk aspect van de besturing van IT-beveiliging is de pro-actieve en continue identificatie van mogelijke aanvallen op computernetwerken.Dit is gecompliceerd vanwege de complexiteit en omvang van dergelijke netwerken, en als gevolg van het feit dat netwerkaanvallen gewoonlijk worden uitgevoerd in meerdere stappen.Dit proefschrift stelt een aanpak voor genaamd MsAMS (Multi-stap Attack Modelleren een Simulatie), gedemonstreerd met een proofof-concept tool om dergelijke meerstapsaanvallen automatisch te vinden.Het orginele aspect van MsAMS is het feit dat het mobile ambients en combinatorische optimizatie, meer specifiek heuristisch zoeken, toepast in het domein van meerstaps-netwerkaanvallen.Een variant van ambient calculus wordt gebruikt om netwerken te modelleren, en heuristische zoeken wordt gebruikt om aanvallers te simuleren die zoeken naar mogelijke aanvallen in het gemodelleerde netwerk.Daarnaast en ter ondersteuning van deze twee aspecten gebruikt MsAMS algoritmen uit het domein van link analyse ranking, die traditioneel toegepast worden in het domein van zoekmachines voor het Web.Mobiele ambients stellen ons in staat om de hiërarchische topologie van een netwerk volledig te representeren als onderdeel van het netwerkmodel zelf.Dit is essentieel om inzichten uit het model te relateren aan het echte netwerk.Bovendien kunnen wij dynamiek van aanvallen representeren, zoals diefstal van credentials, wat het spectrum van mogelijkheden verhoogt voor aanvallers omdat op deze manier zowel niet-kwetsbare als kwetsbare hosts als aanvalsstappen overwogen kunnen worden.Optimalisatie voorziet in beheersing van de complexiteit van het probleem van het vinden van meerstapsaanvallen met credentials zonder schaalbaarheid van de aanpak voor praktisch gebruik tekort te doen.Daarom bestaat de MsAMSaanpak uit: (i) een formele representatie van de oplossing, zodanig dat automatische berekening van de oplossing mogelijk is: in ons geval de representatie van een aanvalsstap in een notatie gebaseerd op Mobile ambients, (ii) een zoekmachine die een heuristische methode implementeert voor het samenstellen van meerstaps-aanvallen uit aanvalsstappen, en (iii) fitness-functies die de zoekmachine gebruikt voor de selectie van de aanvalsstappen uit alternatieven, volgens automatisch berekende metrieken.Net zoals bij zoekmachines die gebruik maken van de structuur van het World Wide Web om webpagina's te scoren, stelt de MsAMS-aanpak voor om gebruik te maken van de structuur van het netwerk om netwerk-assets te scoren.In het bijzonder maakt MsAMS gebruik van PageRank en het HITS ranking scheme als bronnen van schaalbare metrieken voor:1. automatische toewijzing van asset-waardes aan alle ambients in het netwerk, gebaseerd op netwerkconnectiviteit en niet op financiële waarde, die voorzien in een absoluut en vergelijkbaar overzicht van asset-waarde.Deze waarden ondersteunen de netwerkbeheerder in het proces van het kiezen van een aanvalsdoel.vii 2. automatische toewijzen van kosten aan alle ambients in het netwerk, ook gebaseerd op netwerkconnectiviteit in plaats van op financiële waarde.Hiermee wordt voorzien in een absoluut en vergelijkbaar overzicht van de kosten van de aanvalsstappen.Een dergelijke inschatting van de kosten maakt het mogelijk om rationaliteit in acht te nemen van de ambient-aanvaller die een strategie van een werkelijke aanvaller simuleert.