Multi-stage Dynamic Information Flow Tracking Game

Advanced persistent threats (APTs) consist of multiple attack stages between entry and exit points of the attack. In each stage of the attack, the adversary gathers more privileges, resources, and information about the system and uses this information to gain access to the targeted data of the next stage to reach the final goal. APTs are not only persistent but also stealthy and hence difficult to detect. The persistent nature of APTs, however, creates information flows in the system that can be monitored. One monitoring mechanism is Dynamic Information Flow Tracking (DIFT), which taints and tracks malicious information flows through a system and inspects the flows at designated traps. Since tainting all flows in the system will incur prohibitive resource costs, efficient tagging policies are needed to decide which flows to tag in order to maximize the probability of APT detection while minimizing resource overhead. At present such an analytical model for DIFT for multi-stage APT detection does not exist. In this paper, we propose a game theoretic framework modeling real-time detection of multi-stage APTs via DIFT. We formulate a two-player (APT vs DIFT) nonzero-sum stochastic game with incomplete information to obtain an optimal tagging policy. Our game model consists of a sequence of stages, where each stage of the game corresponds to a stage in the attack. At each stage, the goal of the APT is to reach a particular destination, corresponding to a targeted resource or privilege, while the goal of the defender is to detect the APT. We first derive an efficient algorithm to find locally optimal strategies for both players. We then characterize the best responses of both players and present algorithms to find the best responses. Finally, we validate our results on a real-world attack data set obtained using the Refinable Attack INvestigation (RAIN) framework for a ScreenGrab attack.