Towards a Timely Causality Analysis
for Enterprise Security
Yushan Liu∗§ , Mu Zhang†§¶ , Ding Li‡¶ , Kangkook Jee‡ , Zhichun Li‡¶ , Zhenyu Wu‡ , Junghwan Rhee‡ , Prateek Mittal∗¶∗ Princeton University, † Cornell University, ‡ NEC Labs America∗ {yushan,pmittal}@princeton.edu, † mz496@cornell.edu, ‡ {dingli,kjee,zhichun,adamwu,rhee}@nec-labs.com

Abstract—The increasingly sophisticated Advanced PersistentThreat (APT) attacks have become a serious challenge for enterprise IT security. Attack causality analysis, which tracks multi-hop
causal relationships between files and processes to diagnose attack
provenances and consequences, is the first step towards understanding APT attacks and taking appropriate responses. Since
attack causality analysis is a time-critical mission, it is essential
to design causality tracking systems that extract useful attack
information in a timely manner. However, prior work is limited
in serving this need. Existing approaches have largely focused onpruning causal dependencies totally irrelevant to the attack, but
fail to differentiate and prioritize abnormal events from numerous
relevant, yet benign and complicated system operations, resulting
in long investigation time and slow responses.
To address this problem, we propose P RIOT RACKER, a backward and forward causality tracker that automatically prioritizes
the investigation of abnormal causal dependencies in the tracking
process. Specifically, to assess the priority of a system event, weconsider its rareness and topological features in the causality
graph. To distinguish unusual operations from normal system
events, we quantify the rareness of each event by developinga reference model which records common routine activities incorporate computer systems. We implement P RIOT RACKER, in
20K lines of Java code, and a reference model builder in 10K linesof Java code. We evaluate our tool by deploying both systems ina real enterprise IT environment, where we collect 1TB of 2.5
billion OS events from 150 machines in one week. Experimental
results show that P RIOT RACKER can capture attack traces thatare missed by existing trackers and reduce the analysis time by
up to two orders of magnitude.

I.

I NTRODUCTION

The increasingly sophisticated Advanced Persistent Threat(APT) attacks have become a serious challenge for enterprise
IT security. In the past decade, over 6000 severe incidents [1]have been reported. Particularly, large enterprises, such as
Target [2] and HomeDepot [3], have been intentionally targeted§ This work was conducted when Yushan Liu was an intern at NEC Labs,
mentored by Mu Zhang, who was a Researcher at NEC.
¶ Mu Zhang, Ding Li, Zhichun Li and Prateek Mittal are corresponding
authors.

Network and Distributed Systems Security (NDSS) Symposium 201818-21 February 2018, San Diego, CA, USA
ISBN 1-1891562-49-5
http://dx.doi.org/10.14722/ndss.2018.23254
www.ndss-symposium.org

and suffered significant financial loss and reputational damage.
APT attacks are conducted in multiple stages, including initial
compromise, internal reconnaissance, lateral movement andeventually mission completion.
An intrusion may be detected at any of the stages. However,detection by itself only reveals unconnected attack traces.
Besides, a large portion of individual attack footprints are
seemingly insignificant and thus not suspicious enough toraise alarms. Hence, to see the forest from the trees, system administrators must carefully perform attack causality
analysis [4]–[11], in order to achieve a complete and soundunderstanding of a detected attack. This is the very first step
towards a safe system recovery from cyber attacks. To doso, administrators need to first discover how the adversary
gained access to the system, and then determine both exposed
and hidden damage inflicted on the system, such as information leakage, compromised files and installed backdoors.
More concretely, to identify the sequence of steps in an APT
attack, prior work reconstructs multi-hop causal dependencies
between OS-level system objects including processes, files andsockets. Starting from a detected event, system dependencies
are traced backward and forward in temporal order, so as toeventually reveal the attack provenances and uncover all theconsequences, respectively.
Despite the fact that attack causality analysis is performed
in a post-mortem fashion, it is a considerably time-sensitive
mission due to two reasons. First, a compromised system requires complete cleanup before returning to normal operation.
Before recovery, financial loss caused by decreased system
uptime can easily grow to millions of dollars [12]. A timely
causality analysis can accelerate the discovery of all attack
traces and reduce such recovery cost. Second, APT attacks are
performed in multiple stages. A detected point may not be thevery end of attack sequence and the intrusion could further
develop to cause more damage. A timely attack causality
analysis can help understand attack intentions and prevent
future damage.
As a result, we believe a practical security causality
analysis must take time limit into account and extract usefulattack information in a timely manner. Unfortunately, this has
been largely overlooked by the prior work. Previous efforts
have mainly focused on addressing the dependency explosion
problem [5], [6], [10], [11] via data reduction. Particularly, they
have attempted to eliminate irrelevant system dependencies
via either 1) heuristics-based pruning [4], [5] or 2) binary
instrumentation [6], [7] and taint analysis [8], [9]. However,reducing the data volume of irrelevant dependencies does notRelevant yet
Normal Activities

uname

uname

x.x.x.x:80

dash

uname

dash
sshd

info_strealer.sh

dash

dash

uname

run-parts
dash

wget

dash

dash

dash
dash

grep

run-parts

grep

dash
date

run-parts

dash

dash

dash

dash
dash

cut

python2.7
who

bc

motd

dash
tar

env

intellectualproperty.tar

run-parts

ldconfig
run-parts

dash

dpkg

run-parts

dpkg
dash

dash

ssh

python3.4

known_hosts
run-parts

dash

cat

dpkg

dash

scp

dash

find

run-parts

scp

dash

dash

dash

cat

expr

stat

date

cut

dash
dash

sshd

dash
date

date

stat

gawk

sshd

Attack Traces

dash

dash
dash

sshd

bash

scp

intellectualproperty.tar

cp

ftp

y.y.y.y:21

Fig. 1: Reduced Version of Forward Tracking Graph for the Attack Scenario. Rectangles represent processes; ovals denote files;
diamonds indicate sockets. Grey background represents one host, while white background denotes the other.

necessarily lead to a decrease in attack investigation time. Prior
studies still have to invest excessive time in analyzing relevant,yet benign and complex OS events, which dominate the system(see Figure 1 and Section II for an example). Essentially, thisis because they lack the capability of differentiating unusual
activities from common system operations. Therefore, they
have to treat all relevant dependencies, abnormal and normal,
equally and simply keep track of every causal relation.

fuzzing [17] and digital forensics [18], [19] through measuring
the priority of either program-level constructs or user-level
physical entities. In contrast, we enable a priority-based analysis in a completely different domain, and therefore have toaddress the unique challenge of quantifying priority in OSlevel dependency tracking. To the best of our knowledge,
we are the first to accelerate attack causality analysis via
identifying and prioritizing abnormal causal relations.

To address this problem, we propose P RIOT RACKER, abackward and forward causality tracker that automaticallyprioritizes the search for abnormal causal dependencies inthe tracking process. We further formalize a time-constrained
causality analysis to be an optimization problem, which aims
to reveal the maximum number of anomalies within a certain
time limit.

We implement P RIOT RACKER in 20K lines of Java code,
and a reference model builder in 10K lines of Java code.
Our experiments are performed on 54 Linux and 96 Windows
machines used daily by researchers, developers and administrators in an anonymous IT enterprise. Over ten months, weuse an audit log system to capture OS-level events from hostmachines and store them in a database. We also record thecommon system operations to build the reference model. We
evaluate our tool on 8 attack cases, which involve 2.5 billion
OS events spanning one week, and 75 points of interest, which
generate 429,900 sophisticated causal relations. Experimental
results show that P RIOT RACKER can capture attack traces thatare missed by existing trackers and can reduce the analysis
time by up to two orders of magnitude.

To distinguish abnormal operations from normal system
events, we quantify the rareness of each event by developinga reference model which records common routine activities incorporate computer systems. To build such a model, we takefull advantage of the homogeneous IT environment in enterprises, and collect normal OS events from copious amountsof peer systems. Consequently, we enable a “crowd-sourcing”
based method to distill outliers from regular behaviors.

In summary, this paper makes the following contributions:

We associate every event with a priority score and selectthe event with the highest priority score in the process of tracking. The priority score of an event is computed based on its
rareness and other topological features in the causality graph.
We assign weights to these features, which are optimized using
the Hill Climbing algorithm to find the maximum numberof rare events before a given deadline. Note that althoughrareness and other topological features are heuristically chosen,
their weights are formally assigned using machine learningalgorithm to reflect their effectiveness.
Priority-based methods have been widely used in security analyses. Previous efforts have been made to expedite
static data-flow analysis [13], symbolic execution [14]–[16],2•

We are the first to formalize timely attack causality
analysis and to introduce priority to attack graphconstruction. We present P RIOT RACKER, an anomalyprioritized backward and forward causality tracker
which computes the priority score of a causal dependency based on its rareness and topological characteristics in the causality graph. We leverage the Hill
Climbing algorithm to optimize the feature weights inthe priority score.

•

We create a reference model via observing the OSlevel activities from peer systems in homogeneousenterprise hosts. Based upon this model, we propose

Particularly, Figure 1 exposes all the subsequent system
events that are caused by the data exfiltration incident. The
graph begins with the network event where malicious script
info stealer.sh is downloaded by wget from x.x.x.x:80 to theserver machine. The script is then executed in dash, whichconsequently locates sensitive files and triggers tar to compress
the discovered documents into one single file, intellectualproperty.tar. The tarball is further delivered to another Linux
desktop using the scp
sshsshd
scp channel. Oncethe file has reached the desktop system, a new copy is madeand eventually sent to remote cite y.y.y.y:21 through ftp.

a “crowd-sourcing” based method to differentiate unusual behaviors from normal ones, and thus to assist
the computation of the priority score. Our reference
model is able to be customized based upon the system events collected from any specific enterprise IT
environment.
•

We have implemented P RIOT RACKER and a reference
model builder, and deployed them into a real-world
enterprise computer environment. We collect a datasetthat is orders of magnitude larger than the ones usedin previous work [9], [20]. Our experimental results
are promising, showing that P RIOT RACKER can findattack related activities significantly faster than thestate-of-the-art technique.
II.

In the meantime, the result graph also reveals that sshd
executes massive Linux commands through triggering a seriesof run-parts programs. In fact, many of these Linux commands
are intended to update the environmental variables, such as
motd (i.e., message of the day), so as to create a custom
login interface. These are relevant activities that are causedby scp operation but are relatively more common behaviors
compared to transferring a previously unseen file. However,existing causality trackers cannot differentiate them from thereal attack activities. Thus, they may spend a huge amount oftime analyzing all the events introduced due to run-parts, even
before studying data breach through ftp. To our experience, this
could delay the critical attack investigation for a significant
long period of time, ranging from minutes to hours depending on different cases. Unfortunately, Verizon Data Breach
Report [24] discovered that nearly 90 percent of intrusions
saw data exfiltration just minutes after compromise. Thus, any
delay in incident response literally means more lost records,
revenue and company reputation.

OVERVIEWIn this section, we explain the notion of causality analysis
and forward tracking graph via a motivating attack scenario
example. Next, we introduce the problem statement, systemarchitecture and threat model.
A. Motivating Example: Forward Tracking the Impact of Insider Related Data Leaks
1) Attack Scenario: An employee worked at a computer networking company which services a customer in thesemiconductor industry. In order to do business with thesemiconductor firm, the networking company had access tothe customer’s critical server which stored its most sensitive
intellectual property. When the networking company employee
got his new job in another semiconductor firm, he used his
remaining time at his old job to steal the sensitive data. To
do so, he downloaded a malicious BASH script to the dataserver via HTTP, and executed the script in order to discoverand collect all the confidential documents on the server. Then,he compressed the files into a single tarball, transferred thetarball to a low-profile desktop computer via SSH, and finally
uploaded it to the file server via FTP under his control.
Note that similar attack scenarios have happened in the reallife insider incidents of DuPont [21], Barclays [22], Ellery
Systems [23], etc.

In this case, the large causal graph is caused mostly byintensive process creations. Process forking leads to a greater
amount of dependencies particularly in forward tracking thanin backtracking because one process only has one parent but
may have multiple children. However, it is noteworthy that,the delay of attack inspection is a common problem for bothforward and backward dependency tracking. Excessive file or
network accesses can also take up a significant portion ofanalysis time in both practices.
Also note that, the lack of analysis priority is orthogonal tothe data quantity problem which has been intensively studied
by prior data reduction efforts [6], [7], [25]. Even if the overall
data volume has been reduced, a security dependency analysis, without distinguishing between common and uncommon
actions, can still be much delayed due to tracking the hugeamount of normal activities.

2) Causality Analysis: The incident was eventually caught
manually by his colleagues in the new company, and thus
reported to the victim semiconductor firm. The corporate IT
administrators then started an investigation and discovered
the malicious script on the data server. Furthermore, to fully
recover from this attack, they also expected to locate anddestroy all the copies of leaked sensitive files, so that thesecopies would not be accessed by any other unauthorized
personnel in the future. To this end, they leveraged attack
causality analysis [4], [5] to conduct causal dependency forward tracking, which connects the OS-level objects (files,
processes and sockets) via system events in temporal order.

B. Problem Statement
To address this problem, we propose P RIOT RACKER,
which prioritizes the investigation of abnormal operations
based upon the differentiation between routine and unusual
events. Concretely speaking, we expect P RIOT RACKER tomeet the following requirements.

3) Forward Tracking Graph: Figure 1 demonstrates theresulting dependency graph of forward tracking in this attack
case. In the dependency graph, each node represents a process,file or network socket. An edge between two nodes indicates asystem event involving two objects (such as process creation,
file read or write, network access, etc.). Multiple edges arechained together based on their temporal order.
3•

Accuracy. Given sufficient analysis time, our causality
tracker must capture all the critical activities. It must
not miss system events caused by attacks.

•Time Effectiveness. Incident response is time critical and thus a practical attack investigation mustPrioTracker
Event Database•

Dependency Graph

Incident

be subject to time constraints. Given limited analysis
time, our dependency tracking system must find the
maximum number of highly abnormal behaviors.
Runtime Efficiency. The proposed prioritization technique must not introduce a significant amount of additional runtime overhead to the underlying dependency
tracking system.

Causality
Tracker

Reference
Database

Reference
Model Builder

KV

Stream Processing Platform

Particularly, when analyzing the aforementioned attack
scenario, we hope P RIOT RACKER to directly reach the ftp
branch without touching the majority of run-parts branch inadvance, so that provided a temporal limit is applied to theanalysis, the real attack can still be revealed in time.

Collecting OS-Level Events

Fig. 2: Architecture Overview of P RIOT RACKER.

1) System Architecture.: To achieve these goals, we
design the architecture of our system, depicted in Figure 2.
P RIOT RACKER consists of three major components, i.e., apriority-based causality tracker, a reference model builder anda reference database. Our system is designed to be deployed
in a large-scale and homogeneous enterprise IT environment.
In this environment, OS-level events are collected from every
individual host and are pushed to a stream processing platform,
and are eventually stored into the event database.

III. T IME -C ONSTRAINED A NOMALYP RIORITIZED C AUSALITY T RACKING
In this section, we present the design details of timeconstrained anomaly prioritized causality tracking. First, wegive the basic algorithm of P RIOT RACKER. Next, we discuss
the features considered when computing the priority score of asystem event. Then, we introduce the Hill Climber algorithm
used for weight assignment in the priority score.

We retrieve low-level system events from Linux and Windows machines using kernel audit [26] and ETW kernel event
tracing [27], respectively. Specifically, we collect three typesof events: 1) file events, including file read, write and execute,2) process events, such as process create and destroy, and3) network events, including socket create, destroy, read andwrite.

A. Basic Algorithm
In practice, attack investigation time is not unlimited. Our
P RIOT RACKER considers time as a key factor and aims to
track more abnormal behaviors with higher potential impact
with a certain time limit.

Our reference model builder subscribes to the stream inorder to count the occurrences of the same events over all
the hosts. The computed occurrences are then saved into our
key-value store -based reference database so that they canbe efficiently queried by causality tracker. Once an incident
happens, the triggering event is presented to our causality
tracker to start a dependency analysis. The causality tracker
will consequently search for related events from database. At
the same time, it also queries reference database in order tocompute the priority score for the events to be investigated. An
event bearing higher priority score will be analyzed first. In theend, the causal dependencies are generated based upon event
relationships, and are presented as result graphs for further
human inspection.

Tracking tasks start from a detection point, which usuallyis an intrusion alert detected by the monitoring system. Algorithm 1 illustrates our basic algorithm to perform a timeconstrained causality tracking. In general, we follow the priortechnique [4] to build the dependencies between OS-level
events. However, to enable timely security causality analysis,
we prioritize the dependency tracking of abnormal events, incontrast to the previous work which blindly selects the next
event for processing.
More concretely, our dependency tracker internally maintains a priority queue PQ to hold all the events that wait forprocessing. This queue is sorted in descending order basedon the priority scores of enclosed events, so that the eventwith highest priority is always placed at the head and will
be processed first. Upon receiving a starting event se, ourtracker computes its priority score using function P riority()
and adds it into this queue. Then, P RIOT RACKER iteratively
processes each item until the queue becomes empty or the
given analysis time limit Tlimit is reached. In each iteration,
it fetches an event from the head of queue, adds this event to
the result graph G, and invokes C OMPUTE D EPS () to computeits causal dependencies based on temporal relationships [4].
C OMPUTE D EPS () returns a set of events E for further analysis.
Then, we compute the priority score for each element in thisset before inserting them into the priority queue. In the end,
Algorithm 1 outputs the dependency graph G for forensic
analysis. Events that are not tracked within the time limit

2) Threat Model.: We follow the threat model of previous work [4]–[9], [28]. Particularly, we define the trusted
computing base (TCB) for causality analysis to be the kernel
mechanisms, the backend database that stores and manages
audit logs, and the causality tracker. With respect to our TCB,
we assume that audit logs collected from kernel space [26],[27] are not tampered, since kernel is trusted. Kernel-levelattacks that deliberately compromise security auditing systems
are beyond the scope of this study.
We do consider that external attackers or insiders have fullknowledge of “normal” activities, so that they can intentionallycraft attacks with seemingly normal operations and may poison
our reference database using a burst of repeated malicious
activities.
4

Algorithm 1 Dependency Tracking Algorithm

far is less interesting for tracking attack consequences
forward. The former one is introduced by prior workas the “read-only” pruning heuristic [4] in backtracker.
The latter case, however, cannot be completely ignored
because a currently “write-only” file may still beaccessed at a future point.

1: procedure P RIOT RACK(se, Tlimit )2:
PQ ← ∅
3:
PQ.I NSERT(se, P riority(se))
4:while !PQ.I S E MPTY() and Tanalysis < Tlimit do5:e ← PQ.D EQUEUE()
6:
G←G∪e
7:
E ← C OMPUTE D EPS(e)8:for ∀e0 ∈ E do
9:
PQ.I NSERT(e0 , P riority(e0 ))10:
end for11:
end while
12:
return G
13: end procedure

Hence, to generate the priority score for each event, weneed to first compute the scores for edge rareness, fanout anddataflow termination, respectively.
2) Rareness Score: First, we define the rareness score ofan event rs(e) base upon our reference model:(
1,
if e has not been observed by reference modelrs(e) =1
ref (e) , otherwise

are not included in the resulting graph but are stored in the
database for further analysis.

ref (e) is the reference score of event e, which is computedby reference model according to the historical occurrence of e.
We elaborate the computation of reference score in Section IV.

P RIOT RACKER supports across-host tracking by performing IP channel event matching. For an IP channel event on host
A talking to host B, we search for its match on host B withthe reverse of the IP and port information, which are, withinsome tolerance, occurring at the same time.

3) Fanout Score: Second, we formalize the fanout scoreof an event f s(e) to be the reciprocal of its fanout: f s(e) =1
f anout(e) . An event with higher fanout score will be examined
first. Note that when we compute fanout, we do not consider
outgoing socket edges whose destinations are external networks or specific internal servers (e.g., DNS), which are notunder our monitoring and thus will not be further tracked in
the first place.

B. Priority Score
1) Important Factors: We consider three factors to beimportant when determining the priority of system events tobe processed.
•

Rareness of Events. In general, attack behaviors andmalware activities are deviated from massive normal
operations. Particularly, APT incidents often enablezero-day attacks, which by nature have never been
observed in regular systems. As a result, special attention needs to be paid to rarer events compared toroutine activities.

•

Fanout. As illustrated in our motivating example,
routine system operations can be performed in a batch,which consists of multiple sub-operations. Besides,
regular system activities (e.g., creating or accessing
numerous temporary files) may happen periodicallyover time. This in turn generates events with very highfanout in a dependency graph (up to tens of thousands), which does not contribute to attack forensics.
In addition, analysis of causalities with high fanout
can be very time-consuming and therefore may delay
or even disable timely investigation of other attack
traces. Essentially, there exists a trade-off between
time effectiveness and analysis coverage, where abalance needs to be struck.

•

We prefer edges with low fanout due to the consideration ofboth security and efficiency. Analyzing causal relations withhuge fanout is often very slow because dependencies growexponentially. Thus, putting them first may lose the chance toexplore other system dependencies which could also be causedby attacks. In contrast, analysis of causalities with lower fanout
is comparatively simpler and costs much less time to complete.
Even if, in the worst-case scenario, fast-tracking an event withlow fanout does not reveal any attack traces, it only introduce
a small amount of delay to the examination of other complex
causalities.
We admit, as a potential evasion technique, an attacker may
attempt to leverage system causality with high fanout to hide
their attack footprints, in order to delay our analysis. However,
it is worth noting that, though we deprioritize paths with highfanout, we do not prune off them as prior work [4] does. If
an attack is indeed buried in branches bearing high fanout,
given enough time and computation resources, our tracker
can eventually reach that point. Besides, an attack cannot belaunched solely using complex dependencies with high fanout,
while the other portion of attack-related causalities can still be
discovered by our approach from numerous normal edges in a
faster fashion. Since the entire attack footprints are logicallyconnected, any uncovered portion can help human experts findthe remaining ones. On the contrary, without prioritization,
processing benign dependencies with huge fanout can excessively consume computing resources. Consequently, none of
attack traces can be reached before analysis deadline, andtherefore the entire attack is missed.

Dataflow Termination. To invade an enterprise system, attackers have to first exert an external influence
on internal system objects (e.g., malware dropping,malicious input to vulnerable network services, etc.)
to persist; then, they can further use the compromised
persistent objects (e.g., malicious executables, victim
long-running services) to cause impact on other partsof the system. Consequently, a file without being
written in the past is less critical for backtracking
intrusions; a file the has never been read or executed so4) Dataflow Termination: Terminated dataflow is a special case, where fanout equals zero. Therefore, we complete
5Definition 2. The Weight Assignment is an optimization
our definition of fanout score by also checking whether anproblem to maximize the result of an objective function for a
event has further impacts:given set of starting events E:0, if e reaches a read-only file in backtracking
max f (E, (α, β)) =f s(e) = σ, if e reaches a write-only file in forward tracking
X1
EdgeCountθ (P rioT rack(α,β) (e, Tlimit )) (2),otherwisef anout(e)e∈EHence, if backward dataflow is terminated due to read-only
files, we deprioritize the analyses of associated events via
assigning 0 to the score. However, when forward dataflow
ends with “write-only” files, we do not completely rule out thepossibility that these files will later be accessed. Therefore, we
instead give them a lower but non-zero score σ. Empirically,
we set σ to be 0.3.

s.t. 0 ≤ α ≤ 1, α + β = 1, where α and β are the weight parameters for rareness, fanoutand dataflow scores respectively. These scores are further used
to derive the priority score in dependency tracking P rioT rack.
EdgeCount function counts the number graph edges whose
rareness score is greater than a given threshold θ. Empirically,
we set θ to be 0.1 and set time limit Tlimit to be 60
minutes. Note that these values can be customized for specificenvironments and security requirements.

5) Priority Score: The priority score of each event can bederived from the composition of these factors.
Definition 1. The Priority Score of a system event,
P riority(e), is the weighted sum of rareness score rs(e) andfanout score f s(e):P riority(e) = α × rs(e) + β × f s(e)We then utilize the Hill Climbing [29] algorithm to achieve
the optimization of Equation 3. This algorithm can gradually
improve the quality of weight selection via feedback based
method. We have implemented such a feedback loop, whichtakes a set of starting events E and an initial weight vector (α,β) as inputs. To create the starting event set E, we randomly
select 1,113 system events, within a timespan of 10 months
from August 2016 to May 2017, which lead to excessively
large dependency graphs (up to 73,221 edges with 2,391
edges on average). At each iteration, the algorithm adjusts
an individual element in the weight vector and determines
whether the change improves the value of objective functionf (E, (α, β)). If so, such a positive change is accepted, andthe process continues until no positive change can be found
any more. Eventually, the algorithm produces the optimized
weight parameters, where α = 0.27 and β = 0.73.

(1), where α and β are the weights that need to be determined.
An event with higher priority score will be investigated first.
C. Weight Assignment
The next step is to give a proper weight to each parameter of the priority function. Ideally, when weights arecorrectly assigned, we expect our dependency tracker to findthe maximum amount of attack traces within a finite timebound. Nevertheless, it is very hard, if not impossible, tomeasure the relatedness between a single event between two
OS-level objects and an attack, especially before the attack iscompletely known. This is by nature due to the diversity andrandomness of cyber crimes committed by human attackers,
and by itself can be a challenging research problem. Therefore,
to date, expert knowledge has to be kept in the loop to evaluate
automatically generated security causality graphs and to draw
a decisive conclusion.

Note that the rareness and fanout features demonstrate a
trade-off between analysis coverage and time effectiveness.
The fact that the weight of fanout is three times as much asthat of rareness indicates the trained tracking system prefers toquickly expand the search area to reach a global optimal. As aresult, on one hand, it tends to prioritize low-fanout eventsand avoid high-fanout events that cause the search to sink
into a very busy local neighborhood. On the other hand, it
depends less on the rareness score of the current event under
examination because it cannot adequately reflect the overall
rareness of following events. This in fact reveals a limitationof our reference model, which quantifies rareness in a contextinsensitive fashion. We discuss the potential improvement in
Section VI.

To address this problem, we instead use rareness as a
metric to approximate the connection between a causal relation and unknown attacks. As a result, our goal of weightassignment is to enable our tracker to uncover as many unusual
events as possible within a certain time limit. Admittedly, an
adversarial could utilize many normal system operations when
launching an attack, and therefore the overall amount of rare
events does not necessarily indicate the presence of attacks.
However, at certain points of a stealthy crime, an attacker has
to perform some harmful and thus abnormal operations, suchas data exfiltration or system tampering, in order to serve thepurpose. Then, a discovery of more unusual activities may
increase the chance of capturing real attack footprints.

D. Implementation
We have developed the priority-based dependency tracker
in 20K lines of Java code. When acquiring the enabling
information (i.e., rareness, fanout and write-only/read-only),
we pay special attention to runtime efficiency in order to copewith the massive amounts of system events collected from large
enterprises. Particularly, we introduce several optimization
techniques to accelerate data query.

To achieve the discovery of the maximum number of
unusual events, we need to strike a balance among the aforementioned factors. On one hand, at every step of dependency
tracking, we always expect to choose a rare and impactful event
over a common or uninteresting one. On the other hand, we
also hope to quickly explore the entire search space, and findthe direction that leads to more rare activities. Essentially, thisis a global optimization problem, which we define as follows:

1) In-Memory Key-Value Store: Our tracking algorithm
requires frequent access to reference database in order toquery reference score of individual events. Traditional databasepersisted on hard disks cannot satisfy such performance6

habstract-eventi ::= hprocess-eventi| hfile-eventi| hnetwork-eventi
hprocess-eventi ::= hprocessi hprocess-opi hprocessi
hfile-eventi::= hprocessi hfile-opi hfilei
hnetwork-eventi ::= hprocessi hnetwork-opi hsocketi
hprocessi::= hexecutable-pathi
hfilei::= hpath-namei
hsocketi::= hremote-addressi ‘:’ hremote-porti
hprocess-opi ::= ‘create’| ‘destroy’
hfile-opi::= ‘read’| ‘write’| ‘execute’
hnetwork-opi ::= ‘create’| ‘destroy’| ‘read’| ‘write’requirements. As a result, we store the reference data in
RocksDB [30], which on one hand enables an in-memory keyvalue store for fast access, and on the other hand can still
persist data in the traditional way.
2) Event Cache: To compute the fanout of an event or todetermine if an event reaches a read-only or write-only file,
we enable a look-ahead method to examine a further one hopof dependencies. In fact, these additional query results are not
only used for the current computation of priority scores, butalso later become part of result dependency graph. Thus, toavoid redundant query overhead, we cache these results for
future usages.
3) Look-Ahead with a Limit: Sometimes, the fanout ofan event is extremely high. For instance, a Firefox process may
touch hundreds of temporary files. In this case, counting theexact fanout via database query is very time-consuming, andcould lead to degradation of runtime efficiency. Besides, insuch a case, the exact value of fanout becomes less interestingin terms of computing and comparing the priority score.
Therefore, we approximate the fanout by putting a limit n on
the query, so that it only looks for the first n events that are
dependent on the current one. In effect, if the fanout is greaterthan n, the fanout score f s(e) is in practice defined to be 1/n
instead of 1/f anout(e).
IV.

Fig. 3: An Abbreviated Syntax of Event Abstraction
from 3 communities separately and build a reference model foreach of the detected communities. In this way, the generated
models can be adapted for individual environments.
2) Abstraction of Events: To quantify the rareness of
system events, our reference model builder expects to countthe occurrences of same events. Nonetheless, OS events arehighly diverse over time or across hosts, even if they bear
the same semantics. For instance, the same program can bear
several process IDs when it has been executed for multiple
times; two identical system files are assigned with different
inode numbers on two Linux hosts.

R EFERENCE M ODELIn this section, we elaborate on the reference model, whichquantifies the rareness of system events and helps distinguishthe anomalies from noisy normal system operations. First, wegive the details of data collection in an enterprise IT system.
Next, we formally define the reference score of a system event,which is a crucial factor in the rareness score.

To capture high-level common behaviors, while tolerating
low-level system diversity, we summarize events using theirinvariant properties. To this end, we first extract semanticlevel information from system objects. Particularly, a process
is modeled using its executable path, a file is represented by its
path name, and a socket is denoted with remote IP address plus
remote port number. Then, on top of these representations, weconstruct the abstraction of events, which follows a grammar
illustrated in Figure 3 using Backus-Naur (BNF) form. As aresult, events sharing the same abstraction are considered tobe same ones.

A. Data Collection
To build the reference model of system events, we collectand compute the statistical data for event occurrences on
54 Linux and 96 Windows machines used daily for productdevelopment, research and administration in an enterprise IT
system. Particularly, we make special efforts to ensure therepresentativeness, generality and robustness of the reference
model.
1) Discovery of Homogeneous Hosts: The basic ideaof reference model is to identify common behaviors acrossa group of homogeneous hosts. Therefore, to enable thistechnique, the homogeneity of hosting environment is required;
otherwise, the generated model cannot be representative.

Note that, due to customization, the path name of same
system files may still be different on individual hosts. For
example, the user account name can be part of the path
name, which in turn becomes unique for each user. To allow
such differences, normalization of path name is needed. We
address this problem by retrieving a mapping between user
account name and the corresponding home directory namefrom both local machines and global directory services (e.g.,
active directory, NIS), and replacing the home directory namein the path with the same wildcard.

In general, enterprise IT systems could satisfy such arequirement due to the overall consistency of daily tasks.
However, it is still possible that computers from individual
departments in the same corporate carry on different types ofworkloads, and therefore their system behaviors may vary. To
be able to discover the homogeneous groups, we performed
a community detection within an enterprise. Particularly, we
utilized the Mixed Membership Community and Role model(MMCR) proposed in a prior study [31] and eventually discovered 3 communities within 150 machines. In fact, these
3 communities can be roughly mapped to three different
departments in this company. Hence, we collect system events

3) Time Window: The naı̈ve way to count the occurrenceof an event is simply increasing the counter, whenever asame one is observed. Nevertheless, this may be subject
to poisoning attacks. An adversary can intentionally create
repeated malicious activities, and such a burst of vicious events
7

Week

h2

h3

1

h1

x

x

2

x

3

x

4

x

x

Bit-vector for
current week

1

1

h4

h5

2
x
x

4
x

x
0

we present the details of experiment setup. Next, we introduce
the metrics and the attack cases used for the evaluations. Then,
we provide some insights into the common system operations
recorded in the reference model.

Total Count

1

7

A. Experiment Setup

10

We perform all experiments on 54 Linux and 96 Windows
machines used daily by researchers, developers and administrators in an enterprise IT environment, with an audit log system
capturing OS-level events on host machines. We evaluate
P RIOT RACKER on a dataset including 1TB of 2.5 billion
events collected from 150 hosts in one week. Our dataset isorders of magnitude larger than the ones used in previous
work [9], [20]. ProTracer [9], which is an instrumentationbased tracker, was tested on only 2GB event data; Sleuth [20],a real-time heuristics-based attack graph builder, used merely
20GB data from 6 isolated hosts and did not support cross-hosttracking.

0

Fig. 4: Computation of Reference Score

may trick the naı̈ve model to believe that these are common
behaviors due to their high counts.
To address this problem, we introduce a time window whenincreasing counters. Within a single time window, repeated occurrence of an event on the same host will only be considered
once. As a result, a sudden spike of recurring events only
cause limited impacts. We configure the time window to be
one week. This is because enterprises are generally operated on
weekly basis. Besides, host behaviors within and without work
hours, or system activities on weekdays and weekends can be
fairly different by nature. Thus, a time window greater thana week can avoid such a vibration of event occurrence while
preserving high-level consistency of corporate workloads. Notethat the time window is configurable and can be adjusted todifferent enterprise systems.

To evaluate the correctness and time effectiveness of ourapproach, we test P RIOT RACKER in eight representative attacks as described in Table I, including data theft, the infamous Shellshock attack, email phishing, Backdoor, as well
as attacks and test cases proposed in prior work [9], [25].
The difference is that prior work simply crafted “clean” attack
traces isolated from normal system operations. However, inpractice, noise (i.e., complex and normal system operations)is always interleaved with attack traces due to program logic,
shared files and long-running processes. From the daily logsof the enterprise, we observe several typical normal events
which connect the malicious activities to benign ones and thus
introduce a tremendous amount of noise to the causality graph,and list some examples in Table II. To incorporate the impactsof such noise, we reproduced eight representative attacks ina “noisy” environment where numerous normal activities are
considered.

B. Reference Score
With the aforementioned factors being considered, weformally define the reference score of a system event.
Definition 3. The Reference Score ref of an OS-level event
e is its accumulative occurrence on all homogeneous hosts for
all weeks.
XX
ref (e) =count(e, w, h)(3)

To further verify the time efficiency in real-world causality
tracking, we randomly select 75 points of interest (POI), whichtake excessive time to analyze.

h∈hosts w∈weeks, where hosts is the set of homogeneous machines, weeks
represents the set of weeks when data is collected, and
1, if e occurred in week w on host hcount(e, w, h) =0, otherwise

To perform comparative experiments, we also implementa baseline forward-tracker following the prior approach [4],[5], which does not consider priority at all. Instead, thissystem enables breadth-first search when processing incoming
dependencies. We do not use depth-first search because it does
not have the capability to escape from a deep branch and thus
is usually less effective than breadth-first search.

1) Implementation: When computing the score, we in fact
update it incrementally using an online algorithm. As depicted
in Figure 4, we maintain a total count and a bit-vector of
current week for each abstracted event. The bit-vector indicatesthe occurrence of event on all hosts in the current week, where
each bit represents a host. The present data can only affect theexistence of event in the current week, and thus will be checkedagainst the bit-vector. By the end of each week, the total countis updated using the bit-vector and the vector will be cleared.
In this way, we only store the minimum necessary data so as
to ensure efficient storage and query.
V.

We run causality trackers on a server equipped with Intel(R) Xeon(R) CPU E5-1650 CPU (12M Cache, 3.20GHz)
and 64GB of physical memory. The operating system is
Ubuntu 12.04.5 LTS (64bit). Without loss of generality, weonly perform forward tracking instead of bi-directional analyses for all the attacks and selected POIs in the experiments. Ourreference model is constructed and stored on the same server.
Only local I/O overhead is caused when causality tracker
queries reference database.
B. Accuracy

E VALUATION

We use our attack cases to evaluate the accuracy of
P RIOT RACKER. To this end, we forward-track all the attacks

In this section, we conduct experiments to evaluate the correctness, effectiveness and efficiency of P RIOT RACKER. First,
8

TABLE I: Overview of Attack Cases.
Attack Case

Description of Scenario

Data Theft

An insider stole sensitive intellectual property, secure-copied the data to a low-profile
machine and then leaked it via Internet.
A malicious Trojan was downloaded as an Outlook attachment and the enclosed macro
was triggered by Excel to create a fake “java.exe”, and the malicious “java.exe” further
SQL exploited a vulnerable server to start cmd.exe in order to create an info-stealer.
An attacker utilized an Apache server to trigger the Shellshock vulnerability in Bashmultiple times. In each round, she started several Linux commands and cleared Bashhistory in the end.
An attack downloaded the netcat utility and used it to open a Backdoor, from which a
port scanner was then downloaded and executed.
A student downloaded midterm scores from Apache, and uploaded a modified version.
A server administrator created a directory under another user’s home directory,
and downloaded the illegal files to the directory.
Malicious source files were downloaded and then compiled.
An attack stole user account information from passwd file, compressed it using gzip
and transferred the data to a remote machine.

Phishing Email

Shellshock

Netcat Backdoor
Cheating Student
Illegal Storage
wget-gcc
passwd-gzip-scp

References
Motivating Example
CVE-2008-0081

CVE-2014-6271

Persistent Netcat
Backdoor [32]
ProTracer [9]ProTracer [9]Xu et al. [25]Xu et al. [25]TABLE II: Examples of Normal Activities That Connect the Malicious Activities to Benign Ones and Cause Graph Explosion.
Noise Source

Activity

Reason to Interleavesshd-run-parts

Cascade Forking

Program Behavior

sshd-ypserv

Cascade Forking.bash history

Multiple Reads

Conditional
Program Behavior
Shared Log File

Explorer

Multiple Writes

Shared GUI
ProgramDescription of Scenario
Upon receiving file transferring request, SSH daemon starts a large number ofroutine processes to update messages (e.g., motd) used for user interaction.
When a global account requests a SSH connection, SSHD checks user credentialfrom directory service (i.e., NIS) via ypserv, which forks tons of child processes.
Once an attacker has cleared the .bash history to erase her attack footprints, thesame history file will further get read by all future benign Bash terminals.
Once an attacker has dropped some malware to a local directory, the file Propertiesare viewed in Explorer by a normal user, who later uncompresses a ZIP file andtherefore creates many files using 7ZIP from the same Explorer.

TABLE III: Forward Tracking Results.
Attack Case
Data Theft
Phishing Email
Shellshock
Netcat Backdoor
Cheating Student
Illegal Storage
wget-gcc
passwd-gzip-scp

CriticalEvents

Rare
CE

CE

Baseline
All
FNR

CE

Prio
All

FNR

13
148
25
14
37
12
25
15

12
148
23
14
33
10
23
11

13
148
25
14
14
12
25
9

297
3282
11252
1355
7526
8048
6415
2718

13
148
25
14
37
12
25
15

297
3282
11262
1361
7201
8201
6742
2364

0%
0%
0%
0%
0%
0%
0%
0%

via P RIOT RACKER. As a comparison, we also run baseline
forward-tracker on the same cases. We run both trackers for
one day 1 on each case.

0%
0%
0%
0%
62%
0%
0%
40%

Theft” and “Phishing Email”) have the same total numberof tracked dependencies for baseline and P RIOT RACKER,
indicating that the other incidents cannot complete tracking all
causalities within one day, despite the moderate size of attack
traces. Nevertheless, we find that P RIOT RACKER captures all
the crucial attack causalities within the time limit, whereas
the baseline tracker misses 62% and 40% critical events in“Cheating Student” and “passwd-gzip-scp” cases, respectively,
due to its intensive computation of noisy dependencies. We
also observe that most of CEs are rare, which justifies our
choice to prioritize rare events in the causality tracking.

We summarize the results in Table III. Based upon ourfull knowledge of the attack workflow, we manually collectthe ground truth of these attack. Particularly, critical events(“CE”) indicate the number of essential causal dependencies
in an attack. Transitional events such as bash
bash, which
are caused by the underlying system rather than the attack, are
not interesting and thus excluded. Among these CEs, we countthe ones that occur infrequently (“Rare CE”), i.e., the rarenessscore is greater than our configured threshold (i.e. θ = 0.1).
For the baseline forward-tracker and P RIOT RACKER, We countthe CEs and all dependencies discovered within the time limit(“All”) and compute the false negative rate (“FNR”), which isthe proportion of missed CEs, respectively.

Since all attack cases are conducted in normal noisy
enterprise environment, the resulting graphs are up to 600
times larger than essential attack traces. We exemplify thenoisy activities that link malicious traces to normal ones inTable II. These noises are interleaved with attack activities
fundamentally due to inherent program logic, globally sharedlogs and central user interfaces that access both malware andbenign files.

From Table III, we can see that only two incidents (“Data
1 Note that the time limit for tracking is configurable and can be extended
to capture stealthier attackers. We empirically configure their values at thispoint, and we leave the systematic investigation and optimization of theseparameters to future work.

9TABLE IV: Elapsed Analysis Time When 100%, 90% and 50% Attack Traces Have Been Revealed, and Average Elapsed Time.
Attack Case
Data Theft
Phishing Email
Shellshock
Netcat Backdoor
Cheating Student
Illegal Storage
wget-gcc
passwd-gzip-scp

Runtime (100%CEs)
Baseline
Prio

Runtime (90%CEs)
Baseline
Prio

Runtime (50%CEs)
Baseline
Prio

Avg. Runtime for All CEs
BaselinePrio

16.76s
1m2s
2m3s
8.83s
> 1d
27m51s42m9s> 1d14.01s
1m1s
2m2s
8.81s
> 1d
26m27s29m45s
> 1d

4.03s
1m
15.16s
7.01s
> 1d
14m3s
12m5s
3m32s

6.29s
45.90s37.45s6.85s
NA15m31s
18m31s
NA

2.62s
1m4s
12.08s1.28s
40m21s14m10s
6m23s
1m24s

2.48s
28.48s11.83s1.23s
40m19s14m10s
5m54s
1m23s

2.03s
28.47s
6.48s
0.90s
35m14s
13m51s
5m48s
42s

1.55s
27.51s
9.13s
0.88s
24m47s12m39s
5m37s
57s

TABLE V: Ordinal of the Events, Upon Analyzing Which, 100%, 90% and 50% of Attack Traces Have Been Revealed, andAverage Ordinal of All Critical Events.
Attack Case
Data Theft
Phishing Email
Shellshock
Netcat Backdoor
Cheating Student
Illegal Storage
wget-gcc
passwd-gzip-scp

Ordinal (100%CEs)
Baseline
Prio

Ordinal (90%CEs)
Baseline
Prio

Ordinal (50%CEs)
Baseline
Prio

Avg. Ordinal of All CEs
Baseline
Prio

174
3281
11255
1347
>7526
3971
4820
>2718

120
1694
117
1342
>7526
3322
2473
>2718

48
202
65
529
>7526
1487
1181
278

60.54
1000.83
1241.26740.69NA
1742.081434.64
NA

31
3281
35
35
5481
70
610
210

27
244
33
34
5478
69
509
208

24
105
19
16
4424
58
493
58

dash

dash

dash
uname

dash

16.38
581.8323.21
15.21
3248.1151.42
481.04
98.27

uname

uname

run-parts
x.x.x.x:80
0/0
wget
1/1
info_strealer.sh
2/3
dash

34/34
dash
45/35

3/2
23/24

tar
6/4
intellectualproperty.tar
10/6
scp

dash

dash
124/293

dash

dash

dash
35/33

grep

run-parts

cut

dash

163/181
python2.7

date

who

bc

motd

ldconfig

env
59/85
run-parts

run-parts

dash

dash

dash
230/271dash
dpkg

python3.4
run-parts

dpkg

dash

ssh
15/9

dash

dash

dash
run-parts

dash
cat

find

dpkg

run-parts

scp

24/22

191/81
grep

uname

dash
run-parts

sshd
26/32

dash

known_hosts

dash

dash

dash

dash

dash

dash
cat

dash

sshd

stat

date

cut

date

240/302date

237/300
expr
dash

243/301
stat

gawk

sshd
27/23

Attack Traces

sshd

36/25

bash

49/26

scp

62/27

intellectualproperty.tar

cp
121/28ftp
147/29175/30206/31y.y.y.y:21

Fig. 5: Reduced Version of Forward Tracking Graph for Motivating Example.

of all critical events and obtain the ordinal of events, andanalyze which 50%, 90% and 100% of attack traces have been
uncovered.

C. Time EffectivenessWe evaluate the time effectiveness of our proposed method.
To this end, we examine both baseline tracker and P RIO T RACKER on 1) attack scenarios and 2) randomly selected
POIs.

As illustrated in Table IV and Table V, our results showthat P RIOT RACKER can almost always find all critical eventsin shorter time within fewer edges. The lower average runtime
and ordinals indicate that our tracker can prioritize and stay
focused on the exploration and analysis of attack traces. In
contrast, baseline tracker may concentrate on attack investigation in the beginning but then quickly lose focus andeasily get distracted by environmental noise (i.e., normal
system operations). For instance, in the “passwd-gzip-scp”
case, the baseline system manages to find 50% of criticalevents within 3.5 minutes and 278 edges, which are stilla) Attack Cases: First, we would like to see if P RIO T RACKER can reach attack-related events in a faster manner.
Also, we expect to understand in which order these two
trackers explore the causality space and whether anomalies canbe prioritized by P RIOT RACKER. To this end, we first acquire
the total elapsed time to reveal 100%, 90% and 50% criticalevents for both trackers, and calculate the average elapsed time
for reaching every attack-related event. Then, we retrieve theordinals of all discovered events, compute the average ordinal10

91/445

Outlook.exe
0/0
3/1
Excel.exe

7ZG.exe
Mal.xls
7/2

166/268

89/209
Explorer.exe
13/13

Excel.exe

8/7

2/5

1318/723

90/1844

Sqlservr.exe
26/23
cmd.exe

java.exe
11/11

cmd.exe

1.dumpcmd.exe……

cmd.exe

666.jpg

667.jpg

55/122cmd.exe

cmd.exe
osql.exe

164/203280/3280

1692/37

1688/44
csript.exe

Attack Traces…

334.jpg
333.jpg2225/3000
SearchProtocolHost.exe

cqwqk.vbs

java.exe

1000.jpg634/2316

100/24

88/19

6/18

…

1.jpg

0.jpg

7ZG.exe

7ZG.exe

gucio.exe1693/34

osql.exe

3278/39

gucio.exe

cmd.exe

1694/38

3281/3281

Fig. 6: Reduced Version of Forward Tracking Graph for Email Phishing Attack.

Attack Traces

x.x.x.x

bash

bash

35/66

39/75

ls

ls

data.tar.bz2
11251/35
wget

0/0

0/0
apache2
1/1
bash
5/41
bash
9/42
nc.traditional
12/43
bash

apache2
3/3
bash
7/8
bash
13/10
11/9
nc.traditional

bash

32/55

bash

bash

bash
bash
bash
bash
42/80
41/26
40/78
ls
tar
ls
86/28
58/27
data.tar
87/29

33/68

34/73

bash
36/70

ls

cat

ls

cat

55/58
cat

56/60
cat

dir
52/59

54/93
bash

cat
bash

bash
38/69

bash

bash
44/15

bash
48/71

bash
49/76

ls

ls
91/17

bzip2

cp

data.tar.bz2

60/16

59/19

88/33
/var/www/...bz2

46/79.bash_history

53/61

57/81
bash

274/9836bash

251/9832

bash

bash

wc

112/34
apache2

61/21

cp

92/18

bash

39/65

51/101
74/94
bash

bash

bash
bash
50/67
43/40
ls

102/122

ls

ls

tar

who

rm

find

wc

ls

ls

rm

mkdir

Fig. 7: Reduced Version of Forward Tracking Graph for Shellshock Attack.

comparable to 42s and 58 edges for P RIOT RACKER. However,while P RIOT RACKER eventually finds all attack traces at the210th edge in 1 minute 24 seconds, baseline tracker cannot
reach even 90% of traces within one day or 2718 edges. In
the “Phishing Email” attack, however, it takes both trackers
the same number of edges to reach full coverage of attack
traces, and P RIOT RACKER even spends two more seconds tocomplete the analysis. This is because this attack ends witha few seemingly common activities, which are not prioritizedby our tracker. Nevertheless, P RIOT RACKER can discover the
major portion (90%) of this phishing attack twice as fast as
the baseline system. Besides, it merely needs 122 edges tocover attack traces in the causality graph, whereas the baseline
tracker takes 1400 edges to achieve the same goal.

and Figure 7, respectively. In these graphs, attack traces are
enclosed by dotted lines. Areas with different backgrounds(e.g., grey or white) correspond to different hosts. Interestingedges are labeled with two numbers indicating how manyedges are needed to visit them in the baseline tracker and
P RIOT RACKER, respectively. We color-code these labels in thepresentation: red if the corresponding edge is visited earlier
in P RIOT RACKER; blue if it is visited earlier in baseline
system; green if it bears the same ordinal using both searching
methods.
Data Theft. In the case of motivating example (Figure 5),
P RIOT RACKER immediately pursues the direction that leads tothe sink of data leakage and can cover all the attack causalities
in 31 edges. Our system can focus on attack traces because itprioritizes the transfer of a single new file over the spawn ofLinux utilities that are commonly observed. On the contrary,baseline tracker spends analysis time equally on all causalities
and therefore jumps back and forth between the attack branch

To gain further insights, we study the visiting order of
causalities in P RIOT RACKER and the baseline tracker in threecases, i.e., “Data Theft”, “Phishing Email” and “Shellshock”.
Their attack graphs are presented in Figure 5, Figure 6
11and normal activities. As a result, for all the attack-related
events, P RIOT RACKER outperforms baseline tracker.

10 5
10 4

# Rare Edges

Phishing Email. This attack also involved two hosts. As
illustrated in Figure 6, once the victim Windows host was compromised by an email attachment containing malicious Macro,a malware program (fake java.exe) started and connected to a
SQL Server. It then used the SQL Server to create 71 cmd.exe
processes in order to incrementally craft the malicious script
cqwqk.vbs. Then, this script file was launched by cscript.exe,
which thus created another malware instance gucio.exe. Thismalware process issued two SQL commands on SQL Server
via osql.exe and then received the database dump generated bythese commands.

10

3

10 2
10 1
10

baseline
PrioTracker

0

0

20

40

60

80

Index

Fig. 8: Number of Rare Edges Discovered Within 1 Hour for
75 Large Graph Testing Samples.

The noise was introduced by accident. Once the fakejava.exe was written into a directory, a legitimate user opened
the same directory using Explorer and unzipped about 1000
files into this folder. The shared GUI programs thus becamea bridge for connecting the attack activities to benign events,
which hence became relevant. Unfortunately, again, baseline
tracker lacks the capability of distinguishing anomalies from
common behaviors, and thus cannot purely target attack causalities. Due to the frequent switches between attack and noise,
the baseline tracker cannot reach specific critical dependencies
until 1600 edges later (e.g., cqwqk.vbs
cscript.exe or
cscript.exe
gucio.exe).

heuristics and does not track any dependencies beyond thisshared log file. As a comparison, we address this problem
by quantifying the priority of causalities to be analyzed,
and therefore can automatically deprioritize the normal Bashactivities due to the high fanout of .bash history. In addition,
since .bash history is preserved, further dependencies can still
be examined at a later stage. In this way, we strike a balance
between security and efficiency.
As depicted in Figure 7, P RIOT RACKER prioritizes theinvestigation of data exfiltration that happened in one of
attacker-controlled terminals. It prefers the data leakage pathto other launched commands due to two reasons: 1) creationand transfer of new files are more unusual than running Linuxutilities; 2) the data exfiltration path can bring significant
further consequences while ls or dir has little future impact.
As a result, P RIOT RACKER can find the last hop of attack (i.e.,wget) after 34 edges. Also, when time permits, P RIOT RACKER
eventually studies all the normal causalities, such as data
decompression (tar) after around 9800 edges.

P RIOT RACKER prefers the dependency java.exe
SqlServr.exe to Explorer.exe
7ZG.exe in terms ofrareness. Fake java.exe is considered special and to be different
from authentic Java program because of its unique path.
Similarly, our system can quickly scan the majority of attack
traces because they are relatively abnormal compared to the
7ZIP program. However, cmd.exe
osql.exe is a seemingly
common causality, though it is started by the attacker. As
a result, P RIOT RACKER decides to traverse the benign file
decompression first before it eventually comes back to assess
these two events as the 3280th and 3281th edges.

In general, since the baseline tracker spends time evenly on
all branches, as the tracking progresses and an exponentiallygrowing number of dependencies get involved, the baseline
tracker cannot reach the deepest stage of attack before going
through all normal activities. P RIOT RACKER prioritizes theinvestigation of anomalies and automatically find the major
attack traces in a much more effective and timely manner.

It is worth noting that although the exact events that issue
SQL query are not discovered at an early stage, their impactsof dumping and transferring database records have alreadybeen captured as the 19th and 20th edges. This indicates that
attack footprints are pervasively connected, and partial analysis
results are still useful in that they are context clues to infer the
existence of other hidden malice, as long as the majority of
attack traces are covered. This well motivates P RIOT RACKER
which seeks the maximum amount of abnormal activities
before analysis deadline.

1) Random POI: Next, we hope to understand if P RIO T RACKER can identify the maximum amount of uncommon
events within a certain time limit (configured to be one hourin our training phase). To this end, we run P RIOT RACKER
and baseline tracker on 75 randomly selected POI which on
average can generate a forward tracking graph of 5,732 edges.

Shellshock. In this incident, the attacker launched the Bashexploits twice. In the first round, she simply checked environment using Linux utilities without doing serious damage
but at the end of this round, she still erased her footprints byclearing Bash history. In the second round, she stole sensitive
data. To do this, she archived (tar) and compressed (bzip2)
the files, transferred (cp) it to Apache directory so that she
can download (wget) it from another host. Again, she cleared
the history of commands. Later, noises were introduced when anormal user, whose home directory is also /var/www/, opened
new Bash terminals. These terminals would read the modified.bash history and forwardly propagated such a causality.

Figure 8 illustrates the number of rare edges for 75 cases,
captured by both trackers within one hour. Here, a“rare” edge
bears a rareness score that is greater than the threshold θ weset. As depicted in the chart, the red curve representing our
result is always above the blue one for baseline tracker, whilein certain cases, P RIOT RACKER can show up to three ordersof magnitude improvement. This also justifies the effectivenessof our priority computation and weight selection.
D. Insight into Reference Model
1) Runtime Overhead: P RIOT RACKER performs two additional queries to compute the priority scores: 1) look-ahead

Prior work [4] prunes off all the .bash historys based upon12

k-hop neighborhood, into consideration. We will leave it to
future work.

query and 2) reference model query. Look-ahead query does
not introduce additional runtime overhead in the long run
because query results are cached for future dependency construction. Reference database query, in contrast, may cause
additional I/O overhead, and therefore needs evaluation. To
this end, we record the elapsed time of each query to reference
database. Our result shows that every access merely causes
negligible slowdown, on average 0.95 microseconds.

2) Adversarial Setting: Reference scores are naturally resilient to poisoning attacks, since repeated occurrences ofan event on the same host in a week are only considered
once. APT adversaries has limited power in compromising asufficient number of hosts and performing the same malicious
behaviors across weeks, which can lead to higher risk of being
detected.

2) Case Study: We then look into the content of ourreference model and attempt to understand its validity based
upon case studies.

2a) Evasion Using High-fanout Events: We admit that,as a potential evasion technique, an attacker may attempt toleverage system causality with high fanout to hide their attack
footprints. However, an attack cannot be launched solely using
dependencies with big fanout. For instance, apachebash
is an essential low-fanout step when a web server gets compromised. Other attack-related edges can be discovered by ourapproach from thousands of benign edges in a faster fashion.
Since the entire attack footprints are logically connected, any
uncovered part can help analysts to identify the other parts.
Even if, in the worst case scenario, fast-tracking an event withlow fanout does not expose any attack traces, only a small
delay will be incurred to the investigation of other complex
causalities. On the contrary, processing benign dependencies
with huge fanout (up to tens of thousands) can be time
consuming such that none of attack traces can be reached
before analysis deadline.

Process Creation. Many models are generated becauseof common “forking” relation between parent and childprocesses. Particularly, the top ones are caused by mutual
invocation of system processes. For instance, in Windows,
services.exe is the parent of multiple service programs, suchas taskhost.exe and conhost.exe; in Linux, it is common tosee bash forking other terminals, bash and dash, or utilities such as cat, grep, date, etc. Common user programs,
such as python2.7, acrobat.exe, iexplorer.exe, outlook.exe andchrome.exe, may also bear regular invocation behaviors. Program updaters, including dpkg, apt-get, googleupdate.exe andespecially antivirus updater, sesclu.exe (Symantec Endpoint
Security Client LiveUpdate), frequently start subroutines toacquire new packages manually or automatically.
File Access. A even greater amount of models have been
generated from file accesses. However, they become partof our model not because the files are popular ones that
commonly read/written by different processes. On the contrary,
they become prevalent mainly due to the popularity of theprocesses. For example, on Windows, system processes, suchas svchost.exe, services.exe, taskhost.exe, system.exe frequently
access their libraries, logs, metadata, configurations, font etc;
antivirus scanners coh64.exe also accesses a list of specificfiles for detection and management purposes. On the Linuxside, man-db utility may repeatedly access its own database,indexes and caches, while updatedb.mlocate keeps updatingthese cache files; apt-get reads its configuration very often;
find frequently accesses its cached records; python2.7 loads
functions from a list its internal libraries.

2b) Evasion Using Low-fanout Events: An attacker may
intentionally fill the priority queue with numerous benign
low-fanout events to conceal the later steps in an attack.
However, due to the low-fanout constraint, she has to crafta sufficiently long chain of low-fanout events, which by itself
is a extremely suspicious topological pattern. As a result, ourtechnique significantly raises the bar for potential attacks.
2c) Slow Attack: A slow attacker is a general challenge forall causality tracking systems but may also risk being detectedeven before she can cause serious damage, as defenders could
also take advantage of the longer time window.
Note that our work is a general framework that prioritizes abnormal activities for timely security causality analysis,
which is able to further incorporate multi-hop dependency
based attack patterns or user defined priority scores customized
for specific environments and security requirements.

File Execution. File execution is a special class of read
operation and bears completely different semantics. Especially,
due to the fundamental difference in design and implementation, file execution on Windows is very different from thaton Linux: most of the executed Windows files are .DLL files,
which are dynamically loaded by various of system processes,
while Linux usually directly forks a process from an individual
executable file.
VI.

3) Distributed Causality Tracker: The construction of
causality graphs can be potentially parallelized with distributed
computing. Any individual branch to be explored can beprocessed separately; branches may bear different priorities
and therefore are assigned with corresponding computing
resources; dependencies on each host can also be pre-computedin parallel and cross-host tracking thus becomes the concatenation of multiple generated graphs. Nonetheless, the massive
and pervasive dependencies among system events bring significant challenges to parallel processing, and therefore distributed
causality tracking by itself is an interesting research directionthat requires non-trivial efforts.

D ISCUSSION

1) Context Sensitivity of Reference Model: In this paper, weonly consider the rareness of one event edge. However, given
an event edge, the nature of tracking provides the knowledgeof subsequent events in backtracking and preceding eventsin forwardtracking, which can form the context of this eventand be leveraged to differentiate attack-related activities fromnormal ones more accurately. Given an event, priority scores
can take its context, i.e., rareness of event edges within its

In this work, however, we do not enable distributed computation in our causality tracking. Instead, we retrieve audit
logs from multiple hosts, store them in a centralized database,and then perform causality analysis in a centralized manner.
13

graph construction but rather followed original work [4], [5] togenerate causality graphs via simply traversing all nodes (bothnormal and abnormal). P RIOT RACKER focuses on improving
the underlying graph generation algorithm, and therefore isorthogonal to the prior research.

Hence, our analysis only generates one single holistic graphto demonstrate an attack sequence even if the attack is acrossmultiple hosts. Cross-host tracking is conducted in an ondemand manner: only if the causality tracker discovers acommunication channel from a sender machine to a receiver,
it will start to build dependencies on the latter one.

2) Priority-Based Security Analysis: Priority-based methods have been widely used in security analyses. Previous
efforts have been made to expedite static data-flow analysis [13], symbolic execution [14]–[16], fuzzing [17] and digitalforensics [18], [19]. To be able to prioritize certain tasks, thesestudies have attempted to measure the priority of low-level
constructs, including functions, code paths, program inputs
or user-level entities, such as textual documents and physicaldevices.

Again, we would like to point out that the major focus of
our work is how to enable priority-based search in causality
tracking, which is orthogonal to the computing paradigms ofunderlying tracking systems.
VII.

R ELATED W ORK

1) Causality Analysis: Plenty of research efforts havebeen made to reconstruct OS-level system dependencies forsecurity purposes. King and Chen [4] first proposed to build
dependency graph based on OS-level system events in orderto capture the attack sequences and provenances. King etal. [5] further improved the dependency analysis by enabling
cross-host tracking as well as forwardly tracking attack consequences. Chow et al. [33] leveraged taint analysis to understandthe lifetime of sensitive data. Taser [10] also performed tainttracking to find files affected by a past attack. Retro [11]recorded an action history graph, which describes system’s execution, in order to repair a desktop or server after an adversary
compromises it. Jiang et al. [34] enabled a provenance-aware
tracing of worm break-in and contamination. MuniswamyReddy et al. [35] designed a provenance collection structure
facilitating the integration of provenance across multiple levelsof abstraction. Krishnan et al. [36] provided a forensic platformthat transparently monitors and records data access events using only the abstractions exposed by the hypervisor. Hi-Fi [37]presented a kernel-level provenance system that collects highfidelity whole-system provenance. Ma et al. [8] proposed a
Windows based audit logging technique that features accuracy
and low cost.

In contrast to the prior work, we enable a priority-based
analysis in the specific domain of causality tracking. As aresult, we have to invent a unique technique to quantify thepriority in OS-level dependency tracking.
VIII.

C ONCLUSION

In this paper, we propose P RIOT RACKER, a backward andforward causality tracker that automatically prioritizes the investigation of abnormal causal dependencies for enterprise security. Specifically, to assess the priority of a system event, weconsider its rareness and topological features in the causality
graph. To distinguish unusual operations from normal system
events, we quantify the rareness of each event by building areference model which records common routine activities incorporate computer systems. We implement P RIOT RACKER,
in 20K lines of Java code, and a reference model builder in
10K lines of Java code. We evaluate our tool by deploying both
systems in a real enterprise IT environment which consists of
150 machines. Experimental results show that P RIOT RACKER
can capture attack traces that are missed by existing trackers
and reduce the analysis time by up to two orders of magnitude.

Further studies have attempted to mitigate the dependency
explosion problem by reducing data volume and performing
fine-grained causality tracking. BEEP [6] identified the event
handling loops in long running programs so as to enable
selective logging for unit boundaries and unit dependencies.
LogGC [7] proposed an audit logging system with garbage
collection capability. ProTracer [9] presented a lightweight
provenance tracing system that alternates between logging
and taint tracking. Xu et al. [38] attempted to reduce thenumber of log entries while still preserving high-fidelity causal
dependencies.

ACKNOWLEDGMENT
We would like to thank anonymous reviewers and our
shepherd, Prof. Adam Bates, for their feedback in finalizing
this paper. Prateek Mittal and Yushan Liu were partially
supported by the National Science Foundation Grant CNS1553437, CIF-1617286, and CNS-1409415, and Yan Huo *94
Graduate Fellowship. Any opinions, findings, and conclusions
made in this material are those of the authors and do notnecessarily reflect the views of the funding agencies.
R EFERENCES

A recent line of research [28], [39] has enabled enterpriselevel causality analysis, such as data loss prevention, via
modifying underlying operating system. To this end, it introduces Linux Provenance Modules, which produce fine-grained
provenance information. It further mitigates the dependency
explosion using SELinux information flow analysis whichremoves unrelated provenances.

[1]
[2]
[3]

[4]

Compared to the prior work, P RIOT RACKER takes the firststep to prioritizing the investigation of abnormal dependencies
during the construction of causality graph. As a result, thesubsequent causality tracking can reveal more unusual activities before a critical security analysis deadline. In contrast,
the previous work did not innovate new algorithms for attack

[5]

14

“Data breaches,” http://www.idtheftcenter.org/Data-Breaches/databreaches.html, 2016.
C. Staff, “Target: 40 million credit cards compromised,” http://money.
cnn.com/2013/12/18/news/companies/target-credit-card/, 2013.
R. Sidel, “Home depot’s 56 million card breach bigger thantarget’s,” http://www.wsj.com/articles/home-depot-breach-bigger-thantargets-1411073571, 2014.
S. T. King and P. M. Chen, “Backtracking Intrusions,” in Proceedingsof the Nineteenth ACM Symposium on Operating Systems Principles,ser. SOSP’03, 2003.
S. King, Z. M. Mao, D. C. Lucchetti, and P. M. Chen, “Enriching
Intrusion Alerts Through Multi-Host Causality,” in Proceedings ofthe 2005 Network and Distributed Systems Security Symposium, ser.
NDSS’05, 2005.

[6]

[7]

[8]

[9]

[10]

[11]

[12]
[13]

[14]

[15]

[16]

[17]

[18]

[19]
[20]

[21]

[22]

[23]
[24]
[25]

[26]

[27]

K. H. Lee, X. Zhang, and D. Xu, “High Accuracy Attack Provenance via
Binary-based Execution Partition,” in Proceedings of the 2013 Network
and Distributed Systems Security Symposium, ser. NDSS’13, 2013.
——, “Loggc: garbage collecting audit log,” in Proceedings of the 2013
ACM SIGSAC conference on Computer and Communications Security,ser. CCS’13, 2013.
S. Ma, K. H. Lee, C. H. Kim, J. Rhee, X. Zhang, and D. Xu,“Accurate, Low Cost and Instrumentation-Free Security Audit Logging
for Windows,” in Proceedings of the 31st Annual Computer Security
Applications Conference, ser. ACSAC’15, 2015.
S. Ma, X. Zhang, and D. Xu, “Protracer: Towards practical provenance
tracing by alternating between logging and tainting.” in Proceedingsof the 2016 Network and Distributed Systems Security Symposium, ser.
NDSS’16, 2016.
A. Goel, K. Po, K. Farhadi, Z. Li, and E. de Lara, “The Taser Intrusion
Recovery System,” in Proceedings of the Twentieth ACM Symposium
on Operating Systems Principles, ser. SOSP’05, 2005.
T. Kim, X. Wang, N. Zeldovich, and M. F. Kaashoek, “Intrusion recovery using selective re-execution,” in Proceedings of the 9th USENIX
Conference on Operating Systems Design and Implementation, ser.
OSDI’10, 2010.
“2015 cost of cyber crime study: United states,” http://www.ponemon.
org/blog/2015-cost-of-cyber-crime-united-states, 2015.
O. Tripp, M. Pistoia, S. J. Fink, M. Sridharan, and O. Weisman, “Taj:Effective taint analysis of web applications,” in Proceedings of the 30th
ACM SIGPLAN Conference on Programming Language Design and
Implementation, ser. PLDI ’09, 2009.
V. Chipounov, V. Kuznetsov, and G. Candea, “S2e: A platform forin-vivo multi-path analysis of software systems,” in Proceedings of
the Sixteenth International Conference on Architectural Support for
Programming Languages and Operating Systems, ser. ASPLOS XVI,
2011.
C. Cadar, D. Dunbar, and D. Engler, “Klee: Unassisted and automatic
generation of high-coverage tests for complex systems programs,” inProceedings of the 8th USENIX Conference on Operating Systems
Design and Implementation, ser. OSDI’08, 2008.
S. K. Cha, T. Avgerinos, A. Rebert, and D. Brumley, “Unleashingmayhem on binary code,” in Proceedings of the 2012 IEEE Symposium
on Security and Privacy, ser. SP ’12, 2012.
N. Stephens, J. Grosen, C. Salls, A. Dutcher, R. Wang, J. Corbetta,
Y. Shoshitaishvili, C. Kruegel, and G. Vigna, “Driller: Augmenting
fuzzing through selective symbolic execution,” in 23nd Annual Network
and Distributed System Security Symposium, NDSS 2016, San Diego,
California, USA, February 21-24, 2016, 2016.
R. Bert, F. Marturana, G. Me, and S. Tacconi, “Data mining based
crime-dependent triage in digital forensics analysis,” in Proceedings of2012 International Conference on Affective Computing and Intelligent
Interaction, 2012.
N. L. Beebe and L. Liu, “Ranking algorithms for digital forensic string
search hits,” Digit. Investig., 2014.
M. N. Hossain, S. M. Milajerdi, J. Wang, B. Eshete, R. Gjomemo,
R. Sekar, S. Stoller, and V. Venkatakrishnan, “Sleuth: Real-time attack
scenario reconstruction from cots audit data,” 2017.
“The seven largest insider-caused data breaches of 2014,”
http://www.eweek.com/security/the-seven-largest-insider-causeddata-breaches-of-2014, 2014.
“Indian call centers selling u.k.’s secrets,” http://www.siliconindia.com/
shownews/Indian call centers selling UKs secrets-nid-28560-cid2.html, 2005.
“Understanding the insider threat,” https://supportforums.cisco.com/
blog/150466/understanding-insider-threat, 2016.
“Incident response - time is of the essence,” https://www.scmagazineuk.
com/incident-response--time-is-of-the-essence/article/534765/, 2015.
Z. Xu, Z. Wu, Z. Li, K. Jee, J. Rhee, X. Xiao, F. Xu, H. Wang, andG. Jiang, “High fidelity data reduction for big data security dependency
analyses,” in Proceedings of the 2016 ACM SIGSAC Conference on
Computer and Communications Security, ser. CCS ’16, 2016.
“The linux audit framework,” https://www.suse.com/documentation/
sled10/audit sp1/data/book sle audit.html, 2016.

[28]

[29]
[30]
[31]

[32]
[33]

[34]

[35]

[36]

[37]

[38]

[39]

15

“Etw events in the common language runtime,” https://msdn.microsoft.
com/en-us/library/ff357719(v=vs.110).aspx, 2016.
A. M. Bates, D. Tian, K. R. Butler, and T. Moyer, “Trustworthy
whole-system provenance for the linux kernel.” in USENIX Security
Symposium, pp. 319–334.
S. J. Russell and P. Norvig, Artificial Intelligence: A Modern Approach,2003.
“A persistent key-value store for fast storage environments,” http://rocksdb.org/, 2016.
T. Chen, L.-A. Tang, Y. Sun, Z. Chen, H. Chen, and G. Jiang,“Integrating Community and Role Detection in Information Networks,”
in Proceedings of 2016 SIAM International Conference on Data Mining(SDM’16), 2016.
“Persistent netcat backdoor,” https://www.offensive-security.com/
metasploit-unleashed/persistent-netcat-backdoor/, 2017.
J. Chow, B. Pfaff, T. Garfinkel, K. Christopher, and M. Rosenblum, “Understanding data lifetime via whole system simulation,” in Proceedingsof the 13th Conference on USENIX Security Symposium - Volume 13,
2004.
X. Jiang, A. Walters, F. Buchholz, D. Xu, Y.-M. Wang, and E. H.
Spafford, “Provenance-Aware Tracing of Worm Break-in and Contaminations: A Process Coloring Approach,” in Proceedings of IEEEICDCS06, 2006.
K.-K. Muniswamy-Reddy, U. Braun, D. A. Holland, P. Macko,
D. Maclean, D. Margo, M. Seltzer, and R. Smogor, “Layering in provenance systems,” in Proceedings of the 2009 Conference on USENIX
Annual Technical Conference, ser. USENIX’09, 2009.
S. Krishnan, K. Z. Snow, and F. Monrose, “Trail of bytes: Efficient support for forensic analysis,” in Proceedings of the 17th ACM Conference
on Computer and Communications Security, ser. CCS ’10, 2010.
D. J. Pohly, S. McLaughlin, P. McDaniel, and K. Butler, “Hi-fi: Collecting high-fidelity whole-system provenance,” in Proceedings of the
28th Annual Computer Security Applications Conference, ser. ACSAC’12, 2012.
Z. Xu, Z. Wu, Z. Li, K. Jee, J. Rhee, X. Xiao, F. Xu, H. Wang, andG. Jiang, “High fidelity data reduction for big data security dependency
analyses,” in Proceedings of the 2016 ACM SIGSAC Conference on
Computer and Communications Security, ser. CCS’16, 2016.
A. Bates, D. J. Tian, G. Hernandez, T. Moyer, K. R. Butler, andT. Jaeger, “Taming the costs of trustworthy provenance through policy
reduction,” ACM Transactions on Internet Technology (TOIT), vol. 17,
no. 4, p. 34, 2017.