Advanced Persistent Threats (APTs) infiltrate cyber systems and compromise specifically targeted data and/or resources through a sequence of stealthy attacks consisting of multiple stages. Dynamic information flow tracking has been proposed to detect APTs. In this paper, we develop a dynamic information flow tracking game for resource-efficient detection of APTs via multi-stage dynamic games. The game evolves on an information flow graph, whose nodes are processes and objects (e.g., file, network endpoints) in the system and the edges capture the interaction between different processes and objects. Each stage of the game has pre-specified targets that are characterized by a set of nodes of the graph. The goal of the APT is to evade detection and reach a target node of each stage. The goal of the defender is to maximize the detection probability while minimizing performance overhead on the system. The resource costs of the players are different and the information structure is asymmetric, resulting in a nonzero-sum imperfect information game. We first calculate the best responses of the players and then compute Nash equilibrium for single stage attacks. We then provide a polynomial-time algorithm to compute a correlated equilibrium for the multi-stage attack case. Finally, we simulate our model and algorithm on real-world nation state attack data obtained from the Refinable Attack INvestigation (RAIN) system.

This paper deals with minimum cost constrained input selection (minCCIS) for structured systems. Our goal is to optimally select an input set from the given inputs such that the system is structurally controllable when the set of states that each input can influence is pre-specified and each input has a cost associated with it. This problem is known to be NP-hard. We give a new necessary and sufficient graph theoretic condition for checking structural controllability using flow-networks. Using this we propose a polynomial reduction of the problem to a known NP-hard problem: the minimum-cost fixed-flow problem (MCFF). Subsequently, we prove that an optimal solution to the MCFF problem gives an optimal solution to the minCCIS problem. We also show that approximation schemes of MCFF directly apply to the minCCIS problem. Using the special structure of the flow- network constructed for the structured system, we formulate a polynomial time approximation algorithm based on minimum weight bipartite matching problem and a greedy scheme for solving the MCFF problem on the system flow-network. The proposed algorithm gives an approximate solution to the minCCIS problem.

This paper addresses optimal feedback selection for arbitrary pole placement of structured systems when each feedback edge is associated with a cost. Given a structured system and a feedback cost matrix, our aim is to find a feasible feedback matrix of minimum cost that guarantees arbitrary pole placement of the closed-loop structured system. The same problem but with uniform costs has been considered recently, but the claim and the NP-hardness proof there has subtle flaws: we mention this briefly in our paper and then prove the NP-hardness of the feedback selection problem using a reduction from the weighted set cover problem. We next prove the polynomial time constant factor inapproximability of the problem by showing that a constant factor approximation for the problem does not exist, unless the weighted set cover problem can also be approximated within a constant factor. We study a subclass of systems whose directed acyclic graph constructed using the strongly connected components of the state digraph is a line graph and the state bipartite graph has a perfect matching. We propose a polynomial time algorithm based on dynamic programming principles for optimal feedba

Advanced Persistent Threats (APTs) are stealthy attacks by intelligent adversaries. This paper studies the detection of APTs that infiltrate cyber systems and compromise specifically targeted data and/or infrastructures. Dynamic information flow tracking is an information trace-based detection mechanism against APTs that tags suspicious information flows in the system and performs security analysis for unauthorized use of tagged data. In this paper, we develop an analytical model for resourceefficient detection of APTs using an information flow tracking game. The game is a nonzero-sum, turn-based, stochastic game with asymmetric information as the defender cannot distinguish whether an incoming flow is malicious or benign. The payoff functions of the game capture the cost for performing security analysis and the rewards and penalties received by the players. We analyze equilibrium of the game and prove that a Nash equilibrium is given by a solution to the minimum capacity cut set problem on a flow-network derived from the system. The edge capacities of the flow-network are obtained from the cost of performing security analysis. Finally, we implement our algorithm on a real-world dataset for a data exfiltration attack augmented with false-negative and false-positive rates and compute an optimal defender strategy.