  Advanced Persistent Threats (APTs) are stealthy customized attacks by
intelligent adversaries. This paper deals with 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 taints suspicious information
flows in the system and generates security analysis for unauthorized use of
tainted data. In this paper, we develop an analytical model for
resource-efficient 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 and hence has only partial state observation. 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, where the edge capacities are obtained from the cost of performing
security analysis. Finally, we implement our algorithm on the real-world
dataset for a data exfiltration attack augmented with false-negative and
false-positive rates and compute an optimal defender strategy.
