Decision and Game Theory for Security

We formulate intrusion tolerance for a system with service replicas as a two-level game: a local game models intrusion recovery and a global game models replication control. For both games, we prove the existence of equilibria and show that the best responses have a threshold structure, which enables efficient computation of strategies. State-of-the-art intrusion-tolerant systems can be understood as instantiations of our game with heuristic control strategies. Our analysis shows the conditions under which such heuristics can be significantly improved through game-theoretic reasoning. This reasoning allows us to derive the optimal control strategies and evaluate them against 10 types of network intrusions on a testbed. The testbed results demonstrate that our game-theoretic strategies can significantly improve service availability and reduce the operational cost of state-of-the-art intrusion-tolerant systems. In addition, our game strategies can ensure any chosen level of service availability and time-to-recovery, bridging the gap between theoretical and operational performance.

Penetration testing is an essential means of proactive defense in the face of escalating cybersecurity incidents. Traditional manual penetration testing methods are time-consuming, resource-intensive, and prone to human errors. Current trends in automated penetration testing are also impractical, facing significant challenges such as the curse of dimensionality, scalability issues, and lack of adaptability to network changes. To address these issues, we propose MEGA-PT, a meta-game penetration testing framework, featuring micro tactic games for node-level local interactions and a macro strategy process for network-wide attack chains. The micro- and macro-level modeling enables distributed, adaptive, collaborative, and fast penetration testing. MEGA-PT offers agile solutions for various security schemes, including optimal local penetration plans, purple teaming solutions, and risk assessment, providing fundamental principles to guide future automated penetration testing. Our experiments demonstrate the effectiveness and agility of our model by providing improved defense strategies and adaptability to changes at both local and network levels.

The well-worn George Box aphorism “all models are wrong, but some are useful” is particularly salient in the cybersecurity domain, where the assumptions built into a model can have substantial financial or even national security impacts. Computer scientists are often asked to optimize for worst-case outcomes, and since security is largely focused on risk mitigation, preparing for the worst-case scenario appears rational. In this work, we demonstrate that preparing for the worst case rather than the most probable case may yield suboptimal outcomes for learning agents. Through the lens of stochastic Bayesian games, we first explore different attacker knowledge modeling assumptions that impact the usefulness of models to cybersecurity practitioners. By considering different models of attacker knowledge about the state of the game and a defender’s hidden information, we find that there is a cost to the defender for optimizing against the worst case.

A ransomware game involves a ransomware attacker \(\mathcal {A}\) and a victim \(\mathcal {V}\) deciding to cooperate or not. The victim may or may not trust the ransomware attacker to unlock files after paying the ransom to prevent data loss. Simultaneously, the attacker can strategically decide whether or not to unlock the files after receiving payment. This can be modelled as a strategic game, repeated over time. In addition, the attacker may change their mind at any point and stop the game. Likewise, the victim, at any time, might become incapable of playing by being bankrupt, or uninterested by having established recovery and resilience. We develop a novel stochastic game-theoretic model for analysing this scenario and provide equilibria for a single victim and multiple victims. We also study convergence towards equilibria from mutual experience collected by victims and the attacker and compare the equilibrium limits of the model with recommendations from real-life reported experience.

Quantum computing as an inevitable technology can revolutionize many aspects of our society. One potential impact is on cryptocurrency such as Bitcoin, which relies on proof-of-work mining to secure the underlying blockchain protocol. Miners empowered by quantum computers will have superior computational power to win the competition. The quantum advantage jeopardizes the security and trustworthy of cryptocurrency and the transaction validation process by taking over a majority of the network’s computing power, known as a \(51\%\) attack. Fraudulent Bitcoin transactions in the form of double spending can happen, and the emerging quantum miner could enable double spending and benefit from it. How much double spending is optimal without causing too much “inflation”? What shall be the optimal strategy of the first quantum miner facing the competition from other quantum miners? What are the implications of having one or multiple quantum miners to the security of the Bitcoin network? We conduct a novel game theoretic and economic analysis to address these questions. Simulation illustrates that quantum miners would have to collude to gain from double spending in a quantum competitive environment. The distribution of cryptocurrency between quantum miners and classical miners and how cost-effective classical miners are can affect the profitability and the sustainability of double spending as well as the collusion of quantum miners. Intensified quantum competition will decrease the chance of collusion and eventually make the Bitcoin network secure again. The critical point of quantum popularity that will eliminate double spending is found.

We describe a new complete algorithm for computing Nash equilibrium in multiplayer general-sum games, based on a quadratically-constrained feasibility program formulation. We demonstrate that the algorithm runs significantly faster than the prior fastest complete algorithm on several game classes previously studied and that its runtimes even outperform the best incomplete algorithms. We expect our algorithm to be applicable to important game models in economics, political science, security, and many other fields.

We introduce Contested Logistics Games, a variant of logistics problems that account for the presence of an adversary that can disrupt the movement of goods in selected areas. We model this as a large two-player zero-sum one-shot game played on a graph representation of the physical world, with the optimal logistics plans described by the (possibly randomized) Nash equilibria of this game. Our logistics model is fairly sophisticated, and is able to handle multiple modes of transport and goods, accounting for possible storage of goods in warehouses, as well as Leontief utilities based on demand satisfied. We prove computational hardness results related to equilibrium finding and propose a practical double-oracle solver based on solving a series of best-response mixed-integer linear programs. We experiment on both synthetic and real-world maps, demonstrating that our proposed method scales to reasonably large games. We also demonstrate the importance of explicitly modeling the capabilities of the adversary via ablation studies and comparisons with a naive logistics plan based on heuristics.

Ransomware attacks continue to be a major concern for critical systems that are vital for society e.g., healthcare, finance, and transportation. Traditional cyber defense mechanisms fail to pose dynamic measures to stop ransomware attacks from progressing through various stages in the attack process. To this end, intelligent cyber deception strategies can be effective when they leverage information about attacker strategies and deploy deceptive assets to increase the cost or complexity of a successful exploit or discourage continued attacker efforts. In this paper, we present a novel game theoretic approach that uses deception-based defense strategies at each of the ransomware attack stages for optimization of the decision-making to outsmart attacker advances. Specifically, we propose a multistage ransomware game model that deploys a combination of deception assets i.e., honeytokens, honeypots, honeyfiles, and network honeypots in subgames. Using closed-form backward induction, we evaluated Subgame-Perfect Nash Equilibrium (SPNE). We perform a numerical analysis using real-world data and statistics pertaining to the impact of ransomware attacks in the healthcare sector. Our healthcare case study evaluation results show that the use of deception technologies is favorable to the defender. This work elucidates the profound implications of strategic deception in cybersecurity, demonstrating its capacity to complicate successful exploits and consequently bolster the defense of key societal infrastructures.

Deception is helpful for agents masking their intentions from an observer. We consider a team of agents deceiving their supervisor. The supervisor defines nominal behavior for the agents via reference policies, but the agents share an alternate task that they can only achieve by deviating from these references. As such, the agents use deceptive policies to complete the task while ensuring that their behaviors remain plausible to the supervisor. We propose a setting with centralized deceptive policy synthesis and decentralized execution. We model each agent with a Markov decision process and constrain the agents’ deceptive policies so that, with high probability, at least one agent achieves the task. We then provide an algorithm to synthesize deceptive policies that ensure the deviations of all agents are small by minimizing the worst Kullback-Leibler divergence between any agent’s deceptive and reference policies. Thanks to decentralization, this algorithm scales linearly with the number of agents and also facilitates the efficient synthesis of reference policies. We then explore a more general version of the deceptive policy synthesis problem. In particular, we consider a supervisor who selects a subset of agents to eliminate based on the agents’ behaviors. We give algorithms to synthesize deceptive policies so that, after the supervisor eliminates some agents, the remaining agents complete the task with high probability. We demonstrate the developed methods in a package delivery example.

Network/interdependent security games have been extensively used in the literature to gain insights into how firms make optimal security decisions when accounting for spillovers of risks from other firms with whom they have risk interdependencies. We extend these models by proposing K-hop network (security) games, in which agents have extended awareness of network effects: an agent in a K-hop network game accounts for not only its immediate neighbors (those with whom it directly has joint operations or shared infrastructure), but also the spillover of the (security) risks from agents up to K-hops away from it. We first establish an equivalence between our proposed K-hop network games and a one-hop game played on an appropriately defined adjacency matrix. Then, through analytical results and numerical examples, we illustrate how subtle changes in a network can significantly alter equilibrium behaviors when accounting for multi-hop risk spillovers, emphasizing the dependency of agents’ efforts on the nature of their dependencies (complement vs. substitute nature of efforts), agents’ different levels K of awareness of the network effects, and the reactive vs. passive nature of lower awareness (lower K) agents to those with higher awareness (higher K). Our findings show that extended awareness of network effects can, in general, benefit agents by allowing them to optimize their security planning and resource allocation, but that decision makers who are less sophisticated and lack this awareness can suffer, and that consequently, overall investment levels in security may deteriorate.

We present FlipDyn-G, a dynamic game model extending the FlipDyn framework to a graph-based setting, where each node represents a dynamical system. This model captures the interactions between a defender and an adversary who strategically take over nodes in a graph to minimize (resp. maximize) a finite horizon additive cost. At any time, the FlipDyn state is represented as the current node, and each player can transition the FlipDyn state to a node based on the connectivity from the current node. Such transitions are driven by the node dynamics, state, and node-dependent costs. This model results in a hybrid dynamical system where the discrete state (FlipDyn state) governs the continuous state evolution and the corresponding state cost. Our objective is to compute the Nash equilibrium of this finite horizon zero-sum game on a graph. Our contributions are two-fold. First, we model and characterize the FlipDyn-G game for general dynamical systems, along with the corresponding Nash equilibrium (NE) takeover strategies. Second, for scalar linear discrete-time dynamical systems with quadratic costs, we derive the NE takeover strategies and saddle-point values independent of the continuous state of the system. Additionally, for a finite state birth-death Markov chain (represented as a graph) under scalar linear dynamical systems, we derive analytical expressions for the NE takeover strategies and saddle-point values. We illustrate our findings through numerical studies involving epidemic models and linear dynamical systems with adversarial interactions.

Anonymous messaging and payments have gained momentum recently due to their impact on individuals, society, and the digital landscape. Fuzzy Message Detection (FMD) is a privacy-preserving protocol where an untrusted server performs message filtering for its clients in an anonymous way. To prevent the server from linking the sender and the receiver, the latter can set how much cover traffic they should download along with genuine messages. Clearly, this could cause unwanted messages to appear on the user’s end, thereby creating a need to balance one’s bandwidth cost with the desired level of unlinkability.

Previous work showed that FMD is not viable with selfish users. In this paper, we model and analyze FMD using the tools of empirical game theory and show that the system needs at least a few altruistic users to operate properly. Utilizing real-world communication datasets, we characterize the emerging equilibria, quantify the impact of different types and levels of altruism, and assess the efficiency of potential outcomes versus socially optimal allocations. Moreover, taking a mechanism design approach, we show how the betweenness centrality (BC) measure can be utilized to achieve the social optimum.

Model explanations improve the transparency of black-box machine learning (ML) models and their decisions; however, they can also enable privacy threats like membership inference attacks (MIA). Existing works have only analyzed MIA in a single interaction scenario between an adversary and the target ML model, missing the factors that influence an adversary’s capability to launch MIA in repeated interactions. These works also assume the attacker knows the model’s structure, which isn’t always true, leading to suboptimal thresholds for identifying members. This paper examines explanation-based threshold attacks, where an adversary uses the variance in explanations through repeated interactions to perform MIA. We use a continuous-time stochastic signaling game to model these interactions. Unaware of the system’s exact type (honest or malicious), the adversary plays a stopping game to gather explanation variance and compute an optimal threshold for membership determination. We propose a sound mathematical formulation to prove that such an optimal threshold exists, which can be used to launch MIA and identify conditions for a unique Markov perfect equilibrium in this dynamic system. Finally, we evaluate various factors affecting an adversary’s ability to conduct MIA in repeated settings through simulations.

In this work, we propose a two-phase game-theoretic framework to model and defend against Advanced Persistent Threat (APT) attacks in Autonomous Ground Robots (AGRs) running a ROS2-based autonomy stack for safety-critical navigation. In our scenario, the attacker seeks to penetrate the autonomous navigation system and take control over the AGR, causing it to crash into obstacles or fail in its navigation mission, potentially causing catastrophic damage. We use an attack tree abstraction to break the APT attack into two phases and analyze it using appropriate game-theoretical models and solutions to determine the optimal defense strategy for the defenders. For the first phase, we propose a variation of the popular cut-the-rope (CTR) security model by extending it to a probabilistic setting in which applying a spot-check at a given attack tree node does not necessarily result in a “cut” of the “rope”. We model this attack tree based on a curated library of real-world exploits in robotic systems and potential security measures that can counter these exploits. We show that this formulation admits a unique mixed Nash Equilibrium (NE) and determines the optimal defense policy for the first phase. Next, we address the scenario in which the defense mechanisms against the APT attack have failed to prevent the attacker from reaching the safety-critical target node in the network and the robotic asset is commandeered. We equip the robot system with a data-driven end-point Anomaly Detection System (ADS) that monitors the robot odometry data and detects anomalous entities being injected into the autonomy stack. We model this phase of the attack using a two-player zero-sum game where the defender needs to select optimal thresholds for the ADS monitor to balance the need for detecting data-poisoning attacks quickly while minimizing the possibility of false alarms and the attacker needs to select the intensity of the attack for the opposing objectives. We use experiments on a Nova Carter AGR running a Nav2-based autonomy stack within a Secure-ROS2 (SROS2) framework to inform the second-phase game-theoretic model and demonstrate the attack and defense mechanisms.

As autonomous Cyber-Physical Systems (CPS) increasingly operate in critical environments, ensuring their security and reliability becomes paramount. This paper presents a robust anomaly detection framework designed to enhance the resilience of CPS by integrating multiple sensor modalities, including Lidar, Odometry, and Network Traffic. Our approach leverages the strengths of each modality, compensating for potential weaknesses when individual modalities are considered in isolation. A vector-based reconstruction loss function is introduced, significantly improving the detection of subtle anomalies by preserving the contributions of individual features.

Our experimental evaluation, conducted on a custom-built Unmanned Ground Vehicle (UGV) platform, shows that the proposed system achieves an anomaly detection accuracy of up to 98% when using the improved vector-based reconstruction loss, compared to 72% with a standard scalar-based loss. Even when the training data is reduced by 50%, bringing the total training set size down to 92 samples, the system maintains a high accuracy of 97%, demonstrating its robustness under constrained data conditions. These results indicate the effectiveness of our multimodal approach in real-world applications where data availability may be limited. Our work focuses on generalizability and modularity, ensuring adaptability across various CPS platforms and evolving threats, ultimately enhancing the reliability of autonomous systems in real-world scenarios.