Stochastic Dynamic Information Flow Tracking Game using
Supervised Learning for Detecting Advanced Persistent Threats

Information Flow Graph (IFG) provides a graphical representation of the whole-system execution during the entire period of monitoring. We use RAIN recording system [15] to construct the IFG. RAIN comprises a kernel module which logs all the system calls that are requested by the user-level processes in the target host. The target host then sends the recorded system recorded logs to the analysis host. The analysis host consists of a provenance graph builder, which then constructs the coarse-grained IFG. The coarse-IFG is then refined using various pruning techniques. A brief discussion on the pruning steps is included in Section 7. For more details, please refer [15].

IFGs are widely used by analysts for effective cyber response [10], [15]. IFGs are directed graphs, where the nodes in the graph form entities such as processes, files, network connections, and memory objects in the system. Edges correspond to the system calls and are oriented in the direction of the information flows and/or causality [10]. Let directed graph ${\pazocal{G}}=(V_{{\pazocal{G}}},E_{{\pazocal{G}}})$ represent IFG of the system, where $V_{{\pazocal{G}}}=\{v_{1},\ldots,v_{N}\}$ and $E_{{\pazocal{G}}}\subseteq V_{{\pazocal{G}}}\times V_{{\pazocal{G}}}$. Given a system log, one can build the corase-grained-IFG which is then pruned and refined incrementally to obtain the corresponding IFG [15].

This paper consider advanced cyberattacks called as APTs. APTs are information security threats that target sensitive information in specific organizations. APTs enter into the system by leveraging vulnerabilities in the system and implement multiple sophisticated methods to continuously and stealthily steal information [10]. A typical APT attack consists of multiple stages initiated by a successful penetration and followed by initial compromise, C&C communications, privilege escalation, internal reconnaissance, exfiltration, and cleanup [10]. Detection of APT attacks are very challenging as the attacker activities blend in seamlessly with normal system operation. Moreover, as APT attacks are customized, they can not be detected using signature-based detection methods such as firewalls, intrusion detection systems, and antivirus software.

Dynamic information flow tracking (DIFT) is a promising technique to detect security attacks on computer systems [7, 9, 32]. DIFT tracks the system calls to detect the malicious information flows from an adversary and to restrict the use of these malicious flows. DIFT architecture is composed of (i) tag sources, (ii) tag propagation rules, and (iii) tag sinks (traps). Tag sources are the suspicious locations in the system, such as keyboards, network interface, and hard disks, that are tagged/tainted as suspicious by DIFT. Tags are single bit or multiple bit markings depending on the level of granularity manageable with the available memory and resources. All the processed values of the tag sources are tagged and DIFT tracks the propagation of the tagged flows. When anomalous behavior is detected in the system, DIFT initiates security analysis and tagged flows are inspected by DIFT at specific locations, referred to as traps. DIFT conducts fine grain analysis at traps to detect the attack and to perform risk assessment. While tagging and trapping using DIFT is a promising detection mechanism against APTs, DIFT introduces performance overhead on the system. Performing security analysis (trapping) of tagged flows uses considerable amount of memory of the system [9]. Thus there is a tradeoff between system log granularity and performance [15].

The state of the game at a time step $t$, denoted as $s_{t}$, is defined as the position of the tagged information flow in the system. Let ${\bf S}=\{v_{0},v_{1},\ldots,v_{N},\phi,\tau_{{\scriptscriptstyle{A}}},\tau_{{\scriptscriptstyle{B}}}\}$ be the finite state space of the game. Here, $s_{t}=\phi$ denotes the state when the tagged flow drops out by abandoning the attack, $s_{t}=\tau_{{\scriptscriptstyle{A}}}$ denotes the state when DIFT detects the adversary after performing the security analysis, and $s_{t}=\tau_{{\scriptscriptstyle{B}}}$ denotes the state when DIFT performs security analysis and concludes a benign flow as malicious (false positive). Let $\pazocal{D}$ be the destination (target) node set of the adversary and $|\pazocal{D}|=q$. Without loss of generality, let $\pazocal{D}=\{v_{1},v_{2},\ldots,v_{q}\}$. We assume that both agents know the IFG and the destination set $\pazocal{D}$. The state $v_{0}$ corresponds to a virtual state that denote the starting point of the game. In the state space ${\bf S}$, $v_{0}$ is connected to all nodes in $\lambda$. Thus the state of the game at $t=0$ is $s_{0}=v_{0}$.

At every time instant in the game, the players choose their actions from their respective action sets. The action set of the adversary is defined as the possible set of transitions the adversarial flow can execute at a state. The defender has limited resources and hence can perform security analysis at one information flow at a time. Thus the defender’s action set is defined such that, at every decision point, the defender chooses one node to perform security analysis, among the possible nodes that the adversary can transition to.

Let the action set of the adversary and the defender at a state $s_{t}$ be $\pazocal{A}_{{\scriptscriptstyle{A}}}(s_{t})$ and $\pazocal{A}_{{\scriptscriptstyle{D}}}(s_{t})$, respectively. At a state $s_{t}\in V_{{\pazocal{G}}}$, the adversary chooses an action either to drop out, i.e., abort the attack, or to continue the attack by transitioning to a neighboring node. Thus $\pazocal{A}_{{\scriptscriptstyle{A}}}(s_{t}):=\{\phi\}\cup\{v_{j}:s_{t}=v_{i}\leavevmode\nobreak\ {\rm and\leavevmode\nobreak\ }(v_{i},v_{j})\in E_{{\pazocal{G}}}\}$. On the other hand, the defender’s action set at state $s_{t}$ $\pazocal{A}_{{\scriptscriptstyle{D}}}(s_{t}):=\{0\}\cup\{v_{j}:s_{t}=v_{i}\leavevmode\nobreak\ {\rm and\leavevmode\nobreak\ }(v_{i},v_{j})\in E_{{\pazocal{G}}}\}$, where $\pazocal{A}_{{\scriptscriptstyle{D}}}(s_{t})=0$ represents that the tagged information flow is not trapped and $\pazocal{A}_{{\scriptscriptstyle{D}}}(s_{t})=v_{j}$ represents that defender decides to perform security analysis at the node $v_{j}\in V_{{\pazocal{G}}}$ at instant $t$.

The game originates at $t=0$ with state $s_{0}=v_{0}$ with $\pazocal{A}_{{\scriptscriptstyle{A}}}(v_{0}):=\lambda$ and $\pazocal{A}_{{\scriptscriptstyle{D}}}(v_{0}):=0$. The definition of action sets at $v_{0}$ captures the fact that the adversarial flow originates at one of the entry points. Performing security analysis at entry points can not detect the attack as there are not enough traces to analyze. Moreover, the game terminates at time $t$ if the state of the game $s_{t}\in\{\phi,\tau_{{\scriptscriptstyle{A}}},\tau_{{\scriptscriptstyle{B}}}\}\cup\pazocal{D}$. The set of states $\{\phi,\tau_{{\scriptscriptstyle{A}}},\tau_{{\scriptscriptstyle{B}}}\}\cup\pazocal{D}$ are referred to as the absorbing states of the game. For $s_{t}\in\{\phi,\tau_{{\scriptscriptstyle{A}}},\tau_{{\scriptscriptstyle{B}}}\}\cup\pazocal{D}$, $\pazocal{A}_{{\scriptscriptstyle{D}}}(s_{t})=\pazocal{A}_{{\scriptscriptstyle{A}}}(s_{t})=\emptyset$. At a non-absorbing state, the players choose their actions from their respective action set and the game evolves until the state of the game is an absorbing state.

The transition probabilities of the game are governed by the uncertainty associated with DIFT. DIFT is not capable of performing security analysis accurately due to the generation of false-positives and false-negatives. Consider a tagged flow incoming at node $v_{i}\in V_{{\pazocal{G}}}$ at time $t$. Let the action chosen by the defender and the adversary at $s_{t}$ be $d_{t}$ and $a_{t}$, respectively. If defender chooses not to trap an information flow, then the flow proceeds to the node in ${\pazocal{G}}$ chosen by the adversary. That is, if $d_{t}=0$, then $s_{t+1}=a_{t}$. If the defender chooses to trap the node at which the adversary also decides to transition to, then the adversary is detected with probability $1-FN(d_{t})$ and the flow transition to the node in ${\pazocal{G}}$ corresponding to the action of the adversary with the remaining probability. That is, if $d_{t}=a_{t}=v_{i}$, then $s_{t+1}=\tau_{{\scriptscriptstyle{A}}}$ with probability $1-FN(d_{t})$ and $s_{t+1}=a_{t}$ with probability $FN(d_{t})$. If the defender decides to trap a node which is not the node the adversary decides to transition to, then the defender generates a false-positive with probability $FP(d_{t})$ and the flow transition to the node in ${\pazocal{G}}$ corresponding to the action of the adversary with the remaining probability. That is, if $d_{t}\neq 0$ and $d_{t}\neq a_{t}$, then $s_{t+1}=\tau_{{\scriptscriptstyle{B}}}$ with probability $FP(d_{t})$ and $s_{t+1}=a_{t}$ with probability $1-FP(d_{t})$.

Let $P(s_{t},s_{t},d_{t},s_{t+1})$ denote the probability of transitioning to a state $s_{t+1}$ from a state $s_{t}$ under actions $a_{t}$ and $d_{t}$. Then,

The transition probabilities $FN(v_{i}),FP(v_{i})$, for $v_{i}\in V_{{\pazocal{G}}}$, denote the rates of generation of false-negatives and false-positives, respectively, at the different nodes in the IFG. We note that, different nodes in IFG have different capabilities to perform security analysis and depending on that the value of $FN(\cdot)$ and $FP(\cdot)$ are different. The numerical values of these transition probabilities also depend on the type of the attack. As APTs are tailored attacks that can manipulate the system operation and evade conventional security mechanisms such as firewalls, anti-virus software, and intrusion-detection systems, $FN(\cdot)$’s and $FP(\cdot)$’s are often unknown and hard to estimate accurately.

A strategy for a player is a mapping which yields probability distribution over the player’s actions at every state. Consider mixed (stochastic) and stationary player strategies. When the strategy is stationary, the probability of choosing an action at a state depends only on the current state of the game. Let the stationary strategy space of the attacker be ${\bf P}_{{\scriptscriptstyle{A}}}$ and that of the defender be ${\bf P}_{{\scriptscriptstyle{D}}}$. Then, ${\bf P}_{{\scriptscriptstyle{A}}}:{\bf S}\rightarrow[0,1]^{|\pazocal{A}_{{\scriptscriptstyle{A}}}|}$ and ${\bf P}_{{\scriptscriptstyle{D}}}:{\bf S}\rightarrow[0,1]^{|\pazocal{A}_{{\scriptscriptstyle{D}}}|}$. Let $p_{{\scriptscriptstyle{A}}}\in{\bf P}_{{\scriptscriptstyle{A}}}$ and $p_{{\scriptscriptstyle{D}}}\in{\bf P}_{{\scriptscriptstyle{D}}}$. Here, $p_{{\scriptscriptstyle{D}}}=[p_{{\scriptscriptstyle{D}}}(v_{q+1}),\ldots,p_{{\scriptscriptstyle{D}}}(v_{N})]$, where $p_{{\scriptscriptstyle{D}}}(v_{i})$ denotes the probability distribution over all the actions of the defender at state $v_{i}$, i.e., out-neighboring nodes of $v_{i}$ in IFG and not trapping. For $p_{{\scriptscriptstyle{A}}}=[p_{{\scriptscriptstyle{A}}}(v_{0}),p_{{\scriptscriptstyle{A}}}(v_{q+1}),\ldots,p_{{\scriptscriptstyle{A}}}(v_{N})]$, $p_{{\scriptscriptstyle{A}}}(v_{i})$ is a probability distribution over all possible out-neighbors of the node $v_{i}$ in the IFG and $\phi$. We note that, $\pazocal{A}_{{\scriptscriptstyle{A}}}(s_{t})=\pazocal{A}_{{\scriptscriptstyle{D}}}(s_{t})=\emptyset$, for $s_{t}\in\{\phi,\tau_{{\scriptscriptstyle{A}}},\tau_{{\scriptscriptstyle{B}}}\}\cup\pazocal{D}$. Also, $\pazocal{A}_{{\scriptscriptstyle{D}}}(v_{0})=\emptyset$.

In the APT-DIFT game, the aim of the APT is to choose transitions in the IFG in order to reach destination by evading detection by DIFT. The aim of DIFT is to select the security check points to secure the system from the APT attack. Recall that APTs are stealthy attacks that undergo for a long period of time with the ultimate goal of stealing information over a long time. The destructive consequences of APTs are often unnoticeable until the final stages of the attack [4]. In this paper we consider the payoff functions of the APT-DIFT game such that players achieve reward ($\beta$) when their respective aim is achieved. DIFT achieves the aim under two scenarios: (1) when the APT is detected successfully and (2) when APT drops out the attack. We note that, in both cases (1) and (2), DIFT secures the system from the APT attack and hence is rewarded $\beta$. On the other hand, APT achieves the aim under two scenarios: (i) when APT reach destination and (ii) when a benign flow is concluded as malicious, i.e., false-positive. We note that, when a benign flow is concluded as malicious, DIFT no longer analyzes the flows (as it believes APT is detected) and hence the actual malicious flow evades detection and can achieve the aim. Thus in both cases (i) and (ii) APT achieves the aim and receives a reward of $\beta$.

Let the payoff of player $k$ at an absorbing state $s_{t}$ be $r^{k}(s_{t})$, where $k\in\{A,D\}$. At state $\tau_{{\scriptscriptstyle{A}}}$ DIFT receives a payoff of $\beta$ and APT receives $0$ payoff. At state $\tau_{{\scriptscriptstyle{B}}}$ the APT receives a payoff of $\beta$ and DIFT receives $0$ payoff. At a state in the set $\pazocal{D}=\{v_{1},v_{2},\ldots,v_{q}\}$, APT receives a payoff of $\beta$ and DIFT receives $0$ payoff. At state $\phi$ DIFT receives a payoff of $\beta$ and APT receives $0$ payoff. Then,

At each stage in game, $s_{t}$ at time $t$, both players simultaneously choose their action $a_{t}$ and $d_{t}$ and transition to a next state $s_{t+1}$. This is continued until they reach an absorbing state and receive the payoff defined using Eqs. (2) and (3).

Let $T$ denote termination time of the game, i.e., $s_{t+1}=s_{t}$ for $t\geqslant T$. At the termination time $s_{T}\in\{\phi,\tau_{{\scriptscriptstyle{A}}},\tau_{{\scriptscriptstyle{B}}}\}\cup\pazocal{D}$. Let $U_{{\scriptscriptstyle{A}}}$ and $U_{{\scriptscriptstyle{D}}}$ denote the payoff functions of the adversary and the defender, respectively. As the initial state of the game is $v_{0}$, for a strategy pair $(p_{{\scriptscriptstyle{A}}},p_{{\scriptscriptstyle{D}}})$ the expected payoffs of the players are

where $\mathbb{E}_{v_{0},p_{{\scriptscriptstyle{A}}},p_{{\scriptscriptstyle{D}}}}$ denotes the expectation with respect to $p_{{\scriptscriptstyle{A}}}$ and $p_{{\scriptscriptstyle{D}}}$ when the game originates at state $v_{0}$. The objective of APT and DIFT is to individually maximize their expected total payoff given in Eq. (4) and Eq. (5), respectively. Thus the optimization problem solved by DIFT is

Similarly, the optimization problem of the APT is

To bring out the structure of the payoffs well, we let $R_{s_{0}}(s)$ be the cumulative probability with which the state of the game at the termination time is $s$, when the game originates at $s_{0}$. With slight abuse of notation, we use $R_{s_{0}}(\pazocal{D})$ to denote the cumulative probability with which the state of the game at the termination time lies in set $\pazocal{D}$, when the game originates at $s_{0}$. At the time of termination, i.e., $t=T$, the state of the game satisfies one of the following: (i) $s_{T}=\tau_{{\scriptscriptstyle{A}}}$, (ii) $s_{T}=\tau_{{\scriptscriptstyle{B}}}$, (iii) $s_{T}\in\pazocal{D}$, and (iv) $s_{T}=\phi$. Using these definitions Eqs. (4) and (5) can be rewritten as

Using the reformulation of the payoff functions, we present the following property of the APT-DIFT game.

This subsection presents our solution approach for solving the APT-DIFT game when the false-positive and false-negative rates (transition probabilities) are known. By Proposition 5.2, there exists an NE for the APT-DIFT game. Our approach to compute NE of the APT-DIFT game is presented below.

Let $s\in{\bf S}$ be an arbitrary state of the APT-DIFT game. The state value function for a constant-sum game, analogous to the Bellman equation, can be written as

where the $Q$-values are defined as

The min in Eq. (14) can also be defined over mixed (stochastic) policies, but, since it is ‘inside’ the max, the minimum is achieved for a deterministic action choice [17]. The strategy selected by Eq. (14) is referred to as the minimax strategy, and given by

The aim here is to compute minimax strategy $p^{\star}_{{\scriptscriptstyle{D}}}$. Our proposed algorithm and convergence proof is given below.

Let $V=\{V(s):s\in{\bf S}\}$ denote the value vector corresponding to a strategy pair $(p_{{\scriptscriptstyle{A}}},p_{{\scriptscriptstyle{D}}})$. The value for a state $s\in{\bf S}$, $V(s)$, is the expected payoff under strategy pair $(p_{{\scriptscriptstyle{A}}},p_{{\scriptscriptstyle{D}}})$ if the game originates at state $s$. Then, $V^{\star}(s)$ is the expected payoff corresponding to an NE strategy pair $(p^{\star}_{{\scriptscriptstyle{A}}},p^{\star}_{{\scriptscriptstyle{D}}})$ if the game originates at state $s$. Algorithm 6.1 presents the pseudocode to compute the value vector of the APT-DIFT game.

Algorithm 6.1 is a value iteration algorithm defined on a value vector $V=\{V(s):s\in{\bf S}\}$, where $V(s)$ is the value of the game starting at the state $s$. Thus $V(s)=\beta$, for $s\in\{\phi,\tau_{{\scriptscriptstyle{A}}}\}$, and $V(s^{\prime})=0$, for $s^{\prime}\in\{\tau_{{\scriptscriptstyle{B}}}\}\cup\pazocal{D}$. The values of the states is computed recursively, for every iteration $k=1,2,\ldots$, $V^{(k)}(s)$, as follows:

where $\mbox{val}(s,V^{(k-1)})=$

The value-iteration algorithm computes a sequence $V^{(0)},$ $V^{(1)},$ $V^{(2)},\ldots$, where for $k=0,1,2\ldots$, each valuation $V^{(k)}$ associates with each state $s\in{\bf S}$ a lower bound $V^{(k)}(s)$ on the value of the game. Algorithm 6.1 need not terminate in finitely many iterations [26]. The parameter $\delta$, in step 2, denotes the acceptable error bound which is the maximum absolute difference in the values corresponding to two consecutive iterations, i.e., $\max\{|V^{(k)}(s)=V^{(k+1)}(s)|:s\in{\bf S}\}$, and serves as a stopping criteria for Algorithm 6.1. Smaller value of $\delta$ in Algorithm 6.1 will return a value vector that is closer to the actual value vector. Below we prove that as $k$ approaches $\infty$, the values $V^{(k)}(s)$ approaches the exact values $V(s)$ from below, i.e., $\lim_{k\rightarrow\infty}V^{(k)}(s)$ converges to the value of the game at state $s$. Theorem 6.3 proves the asymptotic convergence of the values.

The value of any state $s\in{\bf S}$ is bounded above by $\beta$. Using Lemma 6.1 and Proposition 6.2, we state the convergence result of Algorithm 6.1.

The value of any state $s\in{\bf S}$ is bounded above by $\beta$. From Lemma 6.1 we know that the sequence $V^{(k)}(s)$ is a monotonically increasing sequence. By the monotone convergence theorem [26], a bounded and monotone sequence converges to the supremum, i.e., $\lim_{k\rightarrow\infty}V^{(k)}(s)\rightarrow V^{\star}(s)$, for all $s\in{\bf S}$. Thus the value iteration algorithm converges and the proof follows.

Proof of Theorem 6.4 follows from Lemma 6.1, Theorem 6.3, and Definition 5.1.

The value of $\delta$ trades off the desired accuracy of the value vector and the computational time. For a given value of $\delta$, the number of iterations of Algorithm 6.1 depends on the size and connectivity structure of the IFG. As the size and connectivity structure of the IFG varies across different datasets, we base the selection of $\delta$ solely on the accuracy desired by the security expert. In our experiments, we set $\delta=0.01$. Theorem 6.5 presents the computational complexity of Algorithm 6.1 for each iteration.

Algorithm 6.1 is guaranteed to converge to an NE strategy asymptotically. When the state space of the APT-DIFT game has cycles, Algorithm 6.1 updates the value vector recursively and consequently finite time convergence can not be guaranteed. However, when the IFG is acyclic, the state space of the APT-DIFT game is acyclic (Theorem 6.7) and a finite time convergence can be achieved using value iteration.

Henceforth, the following assumption holds.

The IFG obtained from the system log may not be acyclic in general. However, when the IFG is a cyclic graph, one can obtain an acyclic representation of the IFG using the node versioning technique proposed in [10]. Throughout this subsection, we consider directed acyclic IFGs rendered using the approach in [10] and hence Assumption 6.6 is non-restrictive.

Theorem below presents a termination condition of the APT-DIFT game when the IFG is acyclic.

Using Theorem 6.7, we propose a value iteration algorithm with guaranteed finite time convergence. We will use the following definition in our approach.

For a directed acyclic graph, topological ordering of the node set is defined below.

For a directed acyclic graph with vertex set $B$ and edge set $E$ there exists an algorithm of complexity $O(|B|+|E|)$ to find the topological order [16]. Using the topological ordering, one can find a hierarchical level partitioning of the nodes of a directed acyclic graph. Let $\pazocal{S}$ be the topologically ordered set of nodes of ${\bf S}$. Let the number of hierarchical levels associated with $\pazocal{S}$ be $M$, say $L_{1},L_{2},\ldots,L_{M}$. Then $L_{1}=v_{0}$, $L_{M}=\{\phi,\tau_{{\scriptscriptstyle{A}}},\tau_{{\scriptscriptstyle{B}}}\}\cup\pazocal{D}$. Moreover, a state $s$ is said to be in hierarchical level $L_{j}$ if there exists an edge into $s$ from a state $s^{\prime}$ which is in some level $L_{j^{\prime}}$, where $j^{\prime}<j$, and there is no edge into $s$ from a state $s^{\prime\prime}$ which is in level $L_{j^{\prime\prime}}$, where $j^{\prime\prime}>j$.

Algorithm 6.2 presents the pseudocode to solve the APT-DIFT game using the topological ordering and the hierarchical levels, when the IFG is acyclic.