Visible to the public A Game Theoretic Approach for Dynamic Information Flow Tracking with Conditional Branching

TitleA Game Theoretic Approach for Dynamic Information Flow Tracking with Conditional Branching
Publication TypeConference Paper
Year of Publication2019
AuthorsSahabandu, Dinuka, Moothedath, Shana, Bushnell, Linda, Poovendran, Radha, Aller, Joey, Lee, Wenke, Clark, Andrew
Conference Name2019 American Control Conference (ACC)
Date Publishedjul
Keywordsadvanced persistent threats, Analytical models, APT, computational complexity, conditional branching, conditional-branch tracking, control-flow commands, data flow analysis, data protection, data-flow handling, DIFT, Dynamic Information Flow Tracking, game theoretic approach, game theoretic security, Games, human factors, infinite-horizon stochastic game, infinite-horizon undiscounted stochastic games, linear optimization problem, Linear programming, Nash equilibrium, NetRecon attack, nonlinear programming, polynomial-time algorithm, Predictive Metrics, probability, process control, pubcrawl, reachability analysis, reachability probability, Scalability, security, security of data, stochastic games, Stochastic processes, system security
AbstractIn this paper, we study system security against Advanced Persistent Threats (APTs). APTs are stealthy and persistent but APTs interact with system and introduce information flows in the system as data-flow and control-flow commands. Dynamic Information Flow Tracking (DIFT) is a promising detection mechanism against APTs which taints suspicious input sources in the system and performs online security analysis when a tainted information is used in unauthorized manner. Our objective in this paper is to model DIFT that handle data-flow and conditional branches in the program that arise from control-flow commands. We use game theoretic framework and provide the first analytical model of DIFT with data-flow and conditional-branch tracking. Our game model which is an undiscounted infinite-horizon stochastic game captures the interaction between APTs and DIFT and the notion of conditional branching. We prove that the best response of the APT is a maximal reachability probability problem and provide a polynomial-time algorithm to find the best response by solving a linear optimization problem. We formulate the best response of the defense as a linear optimization problem and show that an optimal solution to the linear program returns a deterministic optimal policy for the defense. Since finding Nash equilibrium for infinite-horizon undiscounted stochastic games is computationally difficult, we present a nonlinear programming based polynomial-time algorithm to find an E-Nash equilibrium. Finally, we perform experimental analysis of our algorithm on real-world data for NetRecon attack augmented with conditional branching.
Citation Keysahabandu_game_2019