Dynamic Information Flow Tracking Games for Simultaneous Detection of Multiple Attackers

Dynamic Information Flow Tracking (DIFT) has been proposed to detect and prevent various cyber attacks in computer systems. DIFT tracks suspicious information flows in the system and generates security analysis when anomalous behavior is detected. A system threatened by attackers of different capabilities demands simultaneous analysis of multiple flows. As the number of information flows in a system is typically large and the amount of resource required for analyzing different flows varies, an optimal allocation of the limited resources available to DIFT is essential. We address the problem of detecting multiple attackers using resource constrained DIFT and develop a model that captures the interaction of adversaries and a DIFT-based defender as a multi-player dynamic game. Our model consists of a multi-stage game, in which each stage represents the subset of processes in the system that correspond to the locations of the information flows, and captures the notion of benign flows. Given the attackers' strategies, we prove that finding an optimal defense strategy is equivalent to maximizing an increasing DR-submodular function that enables us to propose an approximation algorithm. Further, given a defense strategy and strategies of other attackers, we show that finding an optimal attacker strategy is equivalent to solving a shortest path problem, where the edge weights are derived from the strategies of the other players. Based on this mapping we propose a polynomial-time algorithm for computing an optimal attacker strategy. Finally, we evaluate the performance of our algorithm on a real-world dataset of a nation state attack obtained using the Refinable Attack INvestigation (RAIN) framework.