Abstraction Techniques In Security Games With Underlying Network Structure

In a multi-agent system, multiple intelligent agents interact with each other in an environment to achieve their objectives. They can do this because they know which actions are available to them and which actions they prefer to take in a particular situation. The job of game theory is to analyze the interactions of the intelligent agents by different solution techniques and provide analysis such as predicting outcomes or recommending courses of action to specific players. To do so game theory works with a model of real-world scenarios which helps us to make a better decision in our already complex daily life. Game theory also has a growing role in protecting us and our infrastructure, as well as protecting wildlife from crimes. In this Thesis, I particularly focus on adversarial game theoretic models where the interacting agents\u27 decision space involves network structure both in the physical domain and cyber domain. In this type of game model, the strategy space is typically represented by a network with interconnected nodes representing valuable entities that the defender wants to protect from the adversaries. However, due to the underlying network structure, the decision space of the interacting agents increases exponentially in the representation size of the game. This makes analyzing the game models almost intractable due to the limitation of computational resources. Despite the state of the art in hardware where the processing power is becoming faster, this is not sufficient to scale in exponential spaces where we have limited computational resources. In fact, the majority of people do not have access to the state of the art processing power which is also very expensive. A common way to utilize the best available resource is using a smaller, abstracted model of a larger model that can be analyzed within a feasible time duration. Doing so is not straightforward since we can lose overall quality. In this Thesis, I particularly try to exploit the pattern, characteristics, and structure of the underlying network of a game-theoretic model to make algorithmic analysis scalable. My first project is on Green Security Games that focuses particularly on the problem of protecting wildlife and natural resources against illegal exploitation, such as poaching and illegal logging. The illegal activities can be prevented by patrolling the important areas using patrollers by following a particular route. The game model has an underlying network structure to capture the physical terrain. However, the graph representation entails a huge number of possible patrolling paths which grows exponentially with the size of the graph and it creates a computational challenge for the decision makers to find an optimal patrolling strategy. In this scenario, the poaching tends to happen more where there are high animal activities which create sparseness in the network. I present an algorithm that exploits the sparseness characteristic of the underlying network of the terrain to create a smaller representation which can be handled easily to compute the optimal strategy for the decision makers. The experiments show significant improvement over the base algorithms. Next, I use a game-theoretic model based on a cyber defense scenario where a botnet spreads through the network and a network admin tries to increase the security of the network to stop that botnet. The network admin has limited resources. On top of that, a real-world network can have a huge number of machines which makes it difficult for the network admin computationally to allocate his limited resources for increasing the security of the network. However, most real-world networks are divided into subnets to increase performance and security. Botnets often spread easily within a subnet using worms that exploit existing vulnerabilities, but spreading between subnets is harder compared to intra-subnet due to existing security and monitoring. This locality leads to a game model with a particular structure that can be solved by decomposing the game into smaller games. I present an algorithm that utilizes this subnet structure in a network to achieve a highly scalable game model. The experiments show that using network decomposition the algorithm can give the best decisions within seconds. Finally, I consider a cybersecurity game mode where an attacker tries to hide his identity and reach his goal node. He has some tool-sets and exploits in his possession which can overlap with other attacker types. The defender tries to pro-actively deploy deception to reveal more information about the attacker\u27s identity. I show that the strategic use of honeypots can reveal an attacker\u27s identity earlier. However, in this scenario, both the defender\u27s and the attacker\u27s action space increases exponentially. To mitigate the scalability issue I reveal localized information of the attacker to the defender to help to reduce the action space. I also consider a real world network with Virtual Machines where I show that by analyzing sensor data the defender can get information on the attacker\u27s location and reduce his action space to deploy honeypot strategically and dynamically to identify an attacker type earlier. This contribution is also relevant to the strategic use of resources rather than just fixed incident response from the defender\u27s part which makes it harder for the attacker to pinpoint the defender\u27s strategy