1

Detection of Early-Stage Enterprise Infection by

Mining Large-Scale Log Data
Alina Oprea, Zhou Li, RSA Laboratories, Cambridge, MA, USA
Ting-Fang Yen, E8 Security, Palo Alto, CA, USA
Sang Chin, Draper Laboratory, Cambridge, MA, USA
Sumayah Alrwais, Indiana University, Bloomington, IN, USA
arXiv:1411.5005v2 [[Link]] 24 Nov 2014

Abstract—Recent years have seen the rise of more sophisticated stage, victim hosts often visit several domains under the
attacks including advanced persistent threats (APTs) [14], [33], attacker’s control within a short period of time as a result of
[1], [2] which pose severe risks to organizations and governments redirection techniques employed by attackers to protect their
by targeting confidential proprietary information. Additionally,
new malware strains are appearing at a higher rate than ever malicious infrastructures [36]. After delivery, backdoors are
before [29]. Since many of these malware are designed to evade installed on the compromised machines to allow footholds into
existing security products, traditional defenses deployed by most the targeted organization [26], where the machines initiate
enterprises today, e.g., anti-virus, firewalls, intrusion detection outbound connections regularly to a command-and-control
systems, often fail at detecting infections at an early stage. server to receive instructions from the attacker. Malware com-
We address the problem of detecting early-stage infection in
an enterprise setting by proposing a new framework based on munications commonly take place over HTTP/HTTPS, since
belief propagation inspired from graph theory. Belief propagation web traffic is typically allowed by firewalls. More importantly,
can be used either with “seeds” of compromised hosts or domains used in the same attack campaign are often related,
malicious domains (provided by the enterprise security operation meaning that they may share locality in either IP address
center – SOC) or without any seeds. In the latter case we space, time of access or set of hosts contacting them. These
develop a detector of C&C communication particularly tailored
to enterprises which can detect a stealthy compromise of only a patterns of infections have been observed in advanced targeted
single host communicating with the C&C server. attacks (e.g., APT1 group [26], Shady RAT [20], Mirage [12]),
We demonstrate that our techniques perform well on detecting as well as botnet infections (e.g., Zeus, Citadel [13] and
enterprise infections. We achieve high accuracy with low false ZeroAccess [23]).
detection and false negative rates on two months of anonymized In this work, we leverage these observations to detect early-
DNS logs released by Los Alamos National Lab (LANL), which
include APT infection attacks simulated by LANL domain stage malware infections in enterprise networks. Our focus on
experts. We also apply our algorithms to 38TB of real-world enterprises stems from their unique point of view and new
web proxy logs collected at the border of a large enterprise. challenges present in those networks. As the victims of many
Through careful manual investigation in collaboration with the cyber attacks, enterprises are pressed on detecting infections
enterprise SOC, we show that our techniques identified hundreds early to prevent further damage. However, the amount of
of malicious domains overlooked by state-of-the-art security
products. network traffic generated by a large enterprise can be terabytes
per day, requiring extremely efficient analysis methods to
maintain a reasonable detection time. Yet, even though there is
I. I NTRODUCTION much data, it is of limited scope — only containing traffic as
The cybersecurity landscape is evolving constantly. More observed from that enterprise, making prior approaches using
sophisticated attacks including Advanced Persistent Threats ISP-level data (e.g., [9], [6]) inapplicable.
(APTs) [14], [33], [1], [2] have emerged recently targeting or- We propose a graph-theoretic framework based on belief
ganizations’ intellectual property, financial assets, and national propagation [31] to identify small communities of related
security information. Well-funded attackers use advanced tools domains that are indicative of early-stage malware infections.
and manually orchestrate their campaigns to adapt to the We first restrict our attention to traffic destined to rare desti-
victim’s environment and maintain low profiles of activity. nations. These are “new” domains, not visited before by any
Additionally there are also more malware than ever before. host in the organization within an observation window (and
A whitepaper published by Panda Labs [29] found 30 million thus more likely to be associated with suspicious activity), and
new malware strains in circulation in 2013 alone, at an average contacted by a small number of internal hosts (since we expect
of 82,000 malware a day. Many of these are variants of the initial infection to be small). In each iteration of our belief
known malware designed to evade existing security products, propagation algorithm, the rare domains are scored according
such that existing defenses, e.g., anti-virus, firewalls, intrusion to several features and similarity with domains detected in
detection systems, often fail at detecting infections at an early previous iterations.
stage. Our algorithm can be applied either with “hints” (starting
However, certain infection patterns still persist across mal- from “seeds” of known compromised hosts or domains), or
ware variants and families due to the typical infection vectors without (when no information about compromised hosts or
used by attackers. For example, during the malware delivery domains is given). In the first case, seeds can be obtained
 2

from commercial blacklists and external intelligence sources Solve the LANL challenge. We apply the belief propagation
containing Indicators of Compromise (IOCs) that the enter- algorithm to the LANL challenge and identify the malicious
prise security operations center (SOC) has access to. Currently, domains in the 20 simulated campaigns with high accuracy
SOC security analysts manually investigate incidents starting and low false detection and false negative rates.
from IOCs, and we aim here to facilitate this process. In the Evaluate on real-world data from large enterprise. We
latter case, our method first identifies automated, regular C&C apply our solution to a large dataset (38.41 TB) of web proxy
communications that can then be used as seeds. Our C&C de- logs collected at an enterprise’s network border. We identify
tector leverages unique properties of enterprise networks (e.g., hundreds of suspicious domains contacted by internal enter-
popularity of user-agent strings and web referer information in prise hosts which were not detected previously by state-of-
the HTTP traffic) as well as features utilized in previous works the-art security products. Among the 375 domains detected in
(e.g., timing patterns, domain age and registration validity) and total over a month, 289 (accounting for 77.07%) are confirmed
it can detect a single compromised host. malicious or suspicious through careful manual investigation.
We demonstrate the effectiveness of our techniques on While 191 (50.93%) are also reported by VirusTotal (but
two different datasets, one containing DNS records and the unknown to the enterprise of our study), we identify 98
other web proxy logs. The first consists of two months of (26.13%) that are entirely new discoveries (not reported by
anonymized DNS records from Los Alamos National Lab VirusTotal or the enterprise).
(LANL) in early 2013 amounting to 1.15TB. This dataset also
includes 20 independent APT-like infection attacks simulated II. P ROBLEM STATEMENT
by LANL domain experts and was released along with a
challenge problem to the community (APT Infection Discovery Our goal is to detect malware infection within an organiza-
using DNS Data [15]) requesting methods to detect compro- tion in early stages of the campaign. We describe below the
mised internal hosts and external domains in the simulated characteristics of common enterprise infections (due to either
attacks. The challenge included “hints” of varying details (e.g., targeted or opportunistic attacks), why existing solutions fail
one or multiple known compromised hosts), as well as answers against such threats and the challenges we had to overcome
for validation. Our techniques proved effective at detecting for detecting them.
the LANL simulated attacks achieving an overall 98.33% true
detection rate, at the cost of 1.67% false detection rate and A. Enterprise Infections
6.25% false negative rate. Common infection vectors for targeted attacks are social en-
Our second dataset contains two months of web proxy logs gineering [26] and compromise of legitimate sites [39]. In the
collected from a large enterprise in early 2014. Detecting ma- case of social engineering, attackers craft legitimate-looking
licious infections in this dataset proved to be more challenging spear-phishing email addressed to several employees within
due to its large scale (38TB of data), inconsistent information the targeted organization including a malicious attachment
(host IP addresses are dynamically assigned using DHCP in or a hyperlink to a malicious file. Attack vectors employed
most cases), and also the lack of ground truth. Through careful by mainstream malware include spam emails, USB drives,
manual analysis in collaboration with the enterprise SOC, and a variety of web-based attacks (e.g., drive by download,
we identify hundreds of malicious domains not previously clickjacking, malvertising, etc.). Many of these attacks (both
detected by state-of-the-art security products deployed on the targeted and mainstream) have a common pattern during early-
enterprise network. Interestingly, a large number of these (98 stage infection [26], [20], [12], [13]:
distinct domains) are entirely new discoveries, not reported Delivery stage: During delivery, the victim machine gets
yet by VirusTotal several months after we detected them. This the malicious payload, for example by an email attachment,
demonstrates the ability of our techniques to detect entirely or drive-by-download attack, etc. Many times, the first-stage
new, previously unknown attacks. malware is generic and needs to download additional malware
To summarize our main contributions in the paper are: (second stage) specifically crafted for the victim environ-
Belief propagation framework for detecting enterprise ment [38].
infection. We develop a graph-theoretic framework based Establishing foothold: After delivery a backdoor is usually
on belief propagation for detection of early-stage enterprise installed on the victim’s machine and the attacker establishes
infections. Given “seed” hosts or domains, we automatically a foothold within the organization [26]. In almost all cases,
infer other compromised hosts and related malicious domains backdoors initiate outbound connections to evade firewalls that
likely part of the same campaign. Our approach uniquely block connections from outside the network. Most commu-
leverages relationships among domains contacted in multiple nications go through HTTP or HTTPs since these ports are
stages of the infection process. allowed by most enterprise firewalls [34], [28].
Detector of C&C communication in enterprise. By exploit- Command-and-control (C&C): Typically, backdoors connect
ing novel enterprise-specific features and combining them with regularly to the command-and-control center operated by
features used in previous work, we build a detector of C&C attackers to receive further instructions and allow attackers
communication tailored to an enterprise setting. Domains la- backdoor access into the victim environment [26], [13].
beled as potential C&C can be seeded in the belief propagation Based on these infection patterns, we extract several com-
algorithm to detect other related domains. mon characteristics of enterprise infections:
 3

Small scale: Attackers are motivated to maintain stealthy oper- Systems to detect botnet communication or malicious do-
ations to avoid detection by security products deployed within mains have been extensively proposed in the literature. Some
enterprise perimeter and we focus on detecting infections with of them (e.g., [37], [22]) require malware samples for training.
small scale. In some cases a single host might get infected and Unsupervised systems (e.g., [16], [18], [41]) typically require
communicate with the C&C center. multiple synchronized hosts compromised by the same mal-
Uncommon domains: Attackers tend to use uncommon des- ware, and do not scale to large networks. ExecScent [28]
tinations for different stages of the campaign (e.g., delivery, identifies C&C domains from enterprise web traffic, though
C&C). To examine the popularity of domains used in attacks, it requires malware samples as input to generate traffic tem-
we obtained a list of 14,915 IOCs reported between 2011 plates. Our approach is also tailored to large enterprise net-
and 2014 from the SOC of a large enterprise. None of the works like ExecScent, but does not require malware binaries,
indicators are among the Alexa top one million most popu- and can identify multiple related malicious domains used in
lar domains [4]. Additionally, [26] points out that attackers the campaign (not only the C&C stage).
use more frequently domain names rather than direct IP
connections for their C&C communication so that they can C. Challenges
dynamically flux the domains. Among the 14,915 IOCs in There were several challenges we had to overcome in
the enterprise list, the vast majority (13,232 or 88.71%) are the process of developing our detection methodology. First,
domain names. security products deployed within the enterprise perimeter
HTTP/HTTPs Communication. The communications be- record large volumes of data daily. For example, the two
tween malware and C&C servers is typically done through datasets we used to evaluate our system are 1.15 TB and 38.14
HTTP or HTTPs since other ports are blocked by enterprise TB, respectively. To perform efficient analysis, we describe
firewalls [34], [28]. in §IV-A a suite of techniques that reduce the data volume by
Communities of domains: A compromised host usually an order of magnitude while retaining the valuable information
contacts several malicious domains within a relatively short about communication of internal hosts to external domains.
time interval. For instance, a user clicking on an embedded In practical situations, we have to deal with different log
link in an email might visit the front-end attacker site, get formats generated by a variety of deployed security products.
redirected to a site hosting malicious payload and shortly after We focus on general patterns of infections that is common
the backdoor is established will initiate the first connection to in various types of network data (e.g., NetFlow, DNS logs,
the C&C server. These domains form small communities ex- web proxies logs, full packet capture) and demonstrate the
hibiting similarity in connection timing, set of hosts contacting effectiveness of the algorithms on two distinct datasets (DNS
them (if multiple hosts are infected in the same campaign) and logs in §V and web proxies logs in §VI). In the web proxies log
sometimes proximity in IP address space [19], [26]. dataset we enrich the set of features with context information
Automated C&C communication: Backdoors typically com- available in HTTP connections.
municate with C&C servers on a regular basis to allow Finally, while most existing detection systems focus on
attackers access into the victim environment. In many pub- general malware, we aim to also tackle sophisticated infections
licized APT campaigns (e.g., NightDragon [11], Mirage [12], which could be part of a targeted attack. APT attacks are
Shady RAT [20]) as well as botnet infections (e.g., Zeus, extremely stealthy, maintain low profiles and adapt to the
Citadel [13], ZeroAccess [23]), C&C communication occurs victim environment, leaving only small amount of evidence
at regular time intervals (minutes or hours). We also examined in the log data. We develop an algorithm for identifying
malware samples provided by Mandiant on the APT1 group suspicious C&C domains in §IV-C (even when contacted by
to test their communication patterns. Among 43 backdoor a single host) requiring no prior knowledge of the malware
samples, only 4 exhibit randomized communication patterns sample. We use these domains as seeds to identify other related
while the remaining ones periodically communicate back to malicious domains and compromised hosts part of the same
C&C servers (with small variation between connections). campaign through belief propagation. In the case when IOCs
are provided (which is common in enterprise settings), they
can be used as seeds in the same belief propagation algorithm.
B. Current Defenses Our algorithms are unique in identifying relationships among
Large enterprises deploy different security products (anti- domains used in different infection stages, e.g., delivery, C&C.
virus, intrusion-detection, firewalls, etc.). Detection and re- The evaluation on LANL dataset shows that our approach
sponse are largely the responsibility of the Security Operations is able to detect simulated APT infections and thus has the
Center (SOC). The SOC consists of a team of security analysts potential of detecting targeted attacks in the wild.
that monitors the network activities inside the enterprise net-
work, often relying on commercial blacklists or external intel- III. M ETHODOLOGY
ligence sources (i.e., IOCs) to identify malicious domains and In this section, we provide an overview of our approach to
infected hosts, followed by manual investigation to determine detecting early-stage enterprise infection. Our system analyzes
the scope of the threat. As IOCs are by no means complete, log data collected at the enterprise border on a regular basis
the investigation phase is particularly labor-intensive. It is this (e.g., daily), maintains profiles of normal activity within the
process that we aim to facilitate in this paper. enterprise, and detects malware infections by exploiting the
 4

relationship between suspicious external destinations used in • Unpopular: Visited by a small number of internal hosts.
different infection stages. We first describe the datasets used in The intuition is that attackers are likely to compromise
this study, then introduce our main framework based on belief only a few hosts during initial infection.
propagation, the features for detecting suspicious external To identify the “new” destinations, we keep track of external
destinations, and conclude with an overview of the system destinations contacted by internal hosts over time. This “his-
operation. Details on our techniques and features are given in tory” of destinations is initialized during a bootstraping period
the next section. (e.g., one month), and then updated incrementally daily.
These new and unpopular domains are called rare destina-
A. Datasets tions and are the starting point of our detection. We found in
The first dataset used in this study consists of anonymized the enterprise of our study that the number of rare destinations
DNS logs collected from the Los Alamos National Lab is on the order of 50,000 daily, and the challenge we face is
(LANL) internal network. It includes DNS queries initiated by identifying in this set potential malicious domains.
internal hosts, DNS responses from the LANL DNS servers,
timestamps of those events, and IP addresses of the sources B. Modes of operation
and destination hosts. All of the IP addresses and domain
Our detection method operates in two modes. In the first,
names are anonymized (consistently — i.e., the same IP
called SOC hints, we use the incidents that the enterprise SOC
always maps to the same anonymized IP). In addition to real-
investigated as starting points. Given either hosts or domains
world DNS logs, the dataset also includes simulated DNS
confirmed malicious by an analyst as seeds, our algorithm
traffic that is representative of those observed during the initial
identifies other related malicious domains (likely part of the
stage of stealthy, targeted attacks (i.e., APTs). A total of 20
same campaign) and internal compromised hosts that were
distinct attack campaigns are included.
unknown previously.
The second dataset AC consists of logs collected by web
The second is the no-hint mode, in which no known
proxies that intercept HTTP/HTTPs communications at the
compromised hosts or malicious domains are available. In
border of a large enterprise network with over 100,000 hosts.
this mode, we develop a new C&C communication detector
The logs include the connection timestamp, IP addresses of the
utilizing connection timing patterns from hosts to domains,
source and destination, full URL visited, and additional fields
domain registration information, and enterprise-specific fea-
specific to HTTP communications (HTTP method, status code,
tures extracted from the web proxy logs. Compared to previous
user-agent string, web referer, etc.). As such, the AC dataset
work, our C&C detector does not require malware samples for
is much richer compared to the LANL dataset.
training, and can detect C&C communication when only one
In addition to the web proxy logs, we also obtained access to
infected host in the enterprise communicates with the external
a list of domain IOCs used by the SOC for detecting malicious
C&C domain. Interestingly, the detected C&C domains and
activities, and compromised internal hosts communicating to
the hosts contacting them can be used to seed the same
those domains. The IOCs are gathered from external intelli-
belief propagation algorithm and identify additional related
gence sources and commercial blacklists, and often serve as
suspicious domains and compromised hosts, i.e., serve as input
the initial point of investigation by SOC analysts. This data
to the SOC hints mode.
was collected at the same time as the web proxies logs.
All of our datasets span an interval of two months (in
early 2013 for LANL, and early 2014 for AC) and are C. Belief propagation framework
extremely large (1.15TB and 38.14TB, respectively), raising We model the communication between internal hosts and
a number of scalability challenges. While the AC dataset is external domains with a bipartite graph G = (V, E), in which
much richer in information, the main advantage of LANL is there are two types of vertices, hosts and domains. An edge
that it includes the simulated infection campaigns by LANL is created between a host and a domain if the host contacts
domain experts and thus provides a labeled dataset by which the domain at least once during the observation window (e.g.,
to validate our methods. Our main results, however, are from one day). We would like to label each domain as malicious
evaluations performed on the AC dataset in collaboration with or benign, and each host as compromised or clean, with high
the enterprise SOC. confidence.
In the analysis and results presented in the following Our main insight is to apply a graph theoretic technique
sections, we focus on “rare” destinations in our datasets. called belief propagation [31], commonly used to determine
Our insight is that popular websites (visited by a large user the label of a node given prior knowledge about the node
population) are better administered and less likely to be itself and information about its graph neighbors. The algorithm
compromised, but connections to uncommon destinations may is based on iterative message-passing between a node and
be indicative of suspicious behavior. More specifically, we are its neighbors until convergence or when a specified stopping
interested in external destinations that are: condition is met. For our purposes, the messages (or “beliefs”)
• New: Not visited before by any internal hosts. The passed between nodes are an indication of suspicious activities
rationale is that attackers tend to use new domains under observed during early-stage malware infections. In typical im-
their control for at least some of the attack stages, and plementations, the entire graph is constructed in advance and
also that those malicious domains would not be contacted “beliefs” are transmitted from every node to all its neighbors
by benign hosts. in each iteration. Since the graphs in our case are very large
 5

(potentially tens of thousands of domains and hosts daily), we updates). Restricting our focus to rare domains significantly
propose an incremental method of building the bipartite graph reduces the number of considered domains, but we need to
in which hosts and domains are added to the graph only when leverage additional features to identify the truly suspicious au-
the confidence of their compromise is high. tomated connections. Some of these features have been used in
We build a graph starting from the known compromised previous work for identifying generic malicious activities (e.g.,
hosts (and optionally suspicious domains) given as seeds. In domain age and registration validity extracted from WHOIS
each iteration, we compute scores for those rare domains data), and some are tailored to an enterprise environment (e.g.,
contacted by known compromised hosts, and label the domains popularity of user-agent strings within that network and web
with the highest scores as suspicious. The set of compromised referer information in the HTTP traffic).
hosts is also expanded to include other hosts contacting the Combining these features, we train a linear regression model
newly labeled suspicious domains. The algorithm terminates to output a score for each domain that is detected to receive
when the score of the top-ranking domain is below a thresh- automated, periodic, communications. More specifically, the
old, or when the maximum number of iterations is reached, score for a domain is a weighted sum of the features, where
and returns a list of labeled malicious domains ordered by the weights are determined by the regression model during
suspiciousness level. training. Domains with score higher than a threshold (deter-
The score for a domain is computed based on 1) the degree mined based on tradeoffs between accuracy and coverage) are
to which the domain exhibits C&C-like behavior (described considered potential C&C domains.
in §III-D), or 2) its similarity to labeled suspicious domains
from previous iterations of the belief propagation. In the E. Putting it all together
latter case, the similarity of two domains is based on the Our system for detecting early-stage enterprise infection
overlap in hosts that contacted them, time difference between consists of two main phases: training (during a one-month
connections by the same host, and proximity of their IP bootstrapping period) and operation (daily after the training
addresses. These features, combined with properties of the period). An overview diagram is presented in Figure 1.
domain itself (domain age, registration validity, popularity of
Training. The training period is specific to each organization
user-agent string and web referer information), are used in a
and its role is to create a benchmark of normal activity of
regression model to compute a similarity score for the domain
enterprise hosts. It consists of several steps.
relative to the set of domains already labeled suspicious during
(1) Data normalization and reduction: The first stage pro-
belief propagation. More details about domain similarity is
cesses the raw log data (either HTTP or DNS logs) used for
provided in §IV-D.
training and applies normalization and reduction techniques.
D. Detecting C&C communication (2) Profiling: Starting from normalized data, the system pro-
files the activity of internal hosts. It builds histories of external
As discussed in §II communication to the C&C center
destinations visited by internal hosts as well as user-agent
happens in many campaigns on a regular basis to allow the
(UA) strings used in HTTP requests (when available). These
attacker backdoor access into the compromised system. Such
histories are maintained and incrementally updated during the
communications are automatically generated by a malicious
operation stage when new data is available.
process on the victim’s machine, and exhibit certain regular-
ity in connection timing patterns. By contrast, normal user (3) Customizing the C&C detector: The detector of C&C
activities are largely variable. communication is customized to the characteristics of the
We leverage these insights to build a novel detector for enterprise. Enterprise-specific features (e.g., rare destinations,
automated communication that compares the inter-connection popularity of user-agent strings used in a connection, web
histogram of the communication between a host and a domain referer information) are used in combination with other generic
to that of a periodic (regular) distribution. The communication features utilized in previous work (automated connections,
between a host and a domain is labeled “automated” if the domain age and validity). A regression model is trained to
statistical distance between the two histograms is below a determine the feature weights for the particular enterprise and
certain threshold. Compared to other methods for identify- the threshold above which a domain is flagged as C&C.
ing automated connections (e.g., Fast-Fourier transform in (4) Customizing the domain similarity score: The domain sim-
BotFinder [37] and autocorrelation in BotSniffer [18]) our ilarity score used during belief propagation is also customized
method can be tuned for resiliency to outliers and random- to the enterprise during the training phase. The weights of the
ization between connections through several parameters. Our features used for determining domain similarity scores during
detector (like previously proposed timing-based C&C detec- belief propagation, as well as the score threshold, are also
tion methods) will miss communications with large variability chosen by a regression model.
in timing patterns, but these methods are not commonly Operation. After the initial training period, the system enters
used by attackers [26]. Detecting C&C communication with into daily operation mode. Several stages are performed daily:
completely randomized timing patterns (without access to (1) Data normalization and reduction: The system processes
known malware samples) remains an open problem to the new data for that day, normalizes it and performs data reduc-
community. tion.
However, thousands of legitimate requests have regular (2) Profile comparison and update: New data is compared with
timing patterns as well (due to site refreshes or automatic historical profiles, and rare destinations, as well as rare UAs
 6

Training (one month) Operation (daily)

1 Normalization Normalization
1
Reduction Reduction
HTTP/ 2 Host 2 Profile New data
Histories
DNS Profiling comparison
Training Update
Data
C&C Communication Feature C&C SOC
3 3
Model weights Detector seeds
WHOIS
Domain similarity Feature Belief
4 4
scoring weights propagation
No-hint SOC hints

Suspicious Suspicious
domains domains

Fig. 1: Overview of training and operation stages in our system for detecting enterprise infection. Training stage is on the left
and operation on the right. Input data is shown in red, processing steps in blue and various outputs in black.

(used by a small number of hosts) are identified. Histories of information. Compared to LANL data in which all timestamps
external destinations and UAs are updated with new data, so are in the same time zone and IP addresses are statically
that changes in normal behavior are captured in the profiles. assigned, the AC dataset has some inconsistencies due to
(3) C&C detector: The C&C detector is run daily, and scores multiple time zones (as the collection devices are in different
of automated domains are computed with weights determined geographical locations) and DHCP and VPN assignment for
during training. Automated domains with scores above a most of the IP address space.
threshold are labeled as potential C&C domains. We omit here a detailed description of our normalization
(4) Belief propagation: The belief propagation algorithm is procedure, but we converted all timestamps into UTC and
run in two modes (with or without hints). The output is an DHCP and VPN IP addresses to hostnames (by parsing the
ordered list of suspicious domains presented to SOC for further DHCP and VPN logs collected by the organization). After
investigation. normalization, we extract the timestamp, hostname, destination
domain, destination IP, user-agent string, web referrer and
IV. S YSTEM D ETAILS HTTP status code fields for our analysis. We do not consider
After providing an overview of our system for detecting destinations that are IP addresses.
early-stage enterprise infection, we give here more technical
details of our methods. 1e+07
All
Filter internal queries
A. Data Normalization and Reduction Filter internal servers
New destinations
1e+06 Rare destinations
LANL dataset. LANL released a dataset comprised of
Number of domains

anonymized DNS traffic collected over two months (February

and March 2013) from their internal network [15]. The entire
100000
LANL dataset consists of 3.81 billion DNS queries and 3.89
billion DNS responses, amounting to 1.15 TB. To allow
efficient analysis, we employ a number of data reduction 10000
techniques. We first restrict our analysis only to A records, as
they record the queries to domain names and their responses
(IP addresses) and information in other records (e.g., TXT) 1000
03-04 03-05 03-06 03-07 03-08 03-09 03-10
is redacted and thus not useful. This step prunes 30.4% of
Day
DNS records on average per day. We also filter out queries
for internal LANL resources (as our focus is on detecting
Fig. 2: The number of domains encountered daily in LANL
suspicious external communications), and queries initiated
after data reduction for the first week of March.
by internal servers (since we aim at detecting compromised
hosts).
AC dataset. The AC dataset consists of web proxies logs Rare destinations. For both datasets, we use the first month of
generated at the border of a large enterprise over a period data for profiling and building a history of external destinations
of two months (January and February 2014). Analyzing the visited by internal hosts. We determine for each day of the
AC dataset proved difficult due to its large scale, as well second month a list of new destinations not visited before by
as inconsistent information. There are on average 662GB of any internal host. The rationale is that attackers tend to use new
log data generated daily, resulting in a total of 38.14TB of domains under their control not visited previously by internal
data over the two months of our investigation. This dataset hosts, and benign hosts (the large majority) are unlikely to
is 33 times larger than the LANL dataset, and much richer in visit malicious sites contacted by compromised hosts.
 7

For profiling external destinations, we first “fold” the do- above a certain threshold Ts ) is included in set M. Finally
main names to second-level (e.g., [Link] is folded the set of compromised hosts is expanded to include other
to [Link]), assuming that this captures the entity or or- hosts contacting the newly labeled malicious domain(s). The
ganization responsible for the domain. Since domain names algorithm iterates until the stoping condition is met: either
are anonymized in the LANL dataset, we conservatively fold no new domains are labeled as malicious (due to their scores
to third-level domains (as we don’t have information on top- being below the threshold) or the maximum number of iter-
level domains). We then maintain a history of (folded) external ations has been reached. The output is an expanded lists of
destinations queried by internal hosts, updated at the end of compromised hosts H and malicious domains M.
each day to include all new domains from that day. A domain
is considered to be new on a particular day if it has not been Algorithm 1 [Belief Propagation]
contacted before, and unpopular is it has been queried by less /* H ← set of seed hosts */
than a certain threshold of distinct hosts in a single day. We /* M ← set of seed domains */
/* dom host is a mapping from a domain to set of hosts contacting it */
set the threshold at 10 hosts based on discussion with security /* host rdom is a mapping from a host to set of rare domains visited */
professionals at a large organization. These rare destinations function B ELIEF PROPAGATION(H,M):
R ← set of rare domains contacted by hosts in H
are the starting point for our investigation. while stop condition do
Following the steps detailed above, we greatly reduce the N ←Φ /* set of newly labeled malicious domains */
for dom in R \ M do
size of both datasets. The number of domains after each if Detect C&C(dom) then
reduction step in LANL for one week in March is shown in N ← N ∪ {dom}
R ← R \ {dom}
Figure 2. On average, while the full dataset contains queries if N = Φ then
from almost 80,000 hosts to more than 400,000 domains per for dom in R \ M do
score[dom] ← Compute SimScore(dom)
day, in the reduced dataset only 3,369 hosts querying 31,582 max score ← max[score[dom]]
domains are included daily on average. In the AC dataset max dom ← dom of maximum score
if max score ≥ Ts then
starting from 120K hosts and 600K domains in the original N ← N ∪ {dom}
dataset, after data reduction we encounter on average 20K if N 6= Φ then
hosts and 59K rare domains daily. M ← M∪N
H ← H ∪ (∪d∈N dom host[d])
R ← R ∪ (∪h∈H host rdom[h])

B. Belief Propagation Algorithm

The belief propagation algorithm can be applied in two
modes: with hints of compromised hosts provided by SOC, C. Detection of C&C communication
or without hints. In the first case we use as seed a list of
compromised hosts investigated and confirmed by security Dynamic histograms. We aim at detecting automated con-
analysts in SOC and optionally a list of malicious domains. In nections with fairly regular timing patters, but be resilient to
the latter case the C&C communication detector is run first to outliers (for instance large gaps in communication) and small
identify a set of potential C&C domains and hosts contacting amounts of randomization introduced by attackers between
them. These are given as seeds to the belief propagation connections.
algorithm. The algorithm is run daily in both modes and it Initially, we tested a detector for automated connections
detects malicious domains and compromised hosts that are based on standard deviation (labeling the connections between
likely part of the same campaign with the provided seeds. a host and a domain as automated if the standard deviation of
Algorithm 1 presents the pseudocode of the belief propa- the inter-connection intervals is small), but found out that a
gation algorithm. The algorithm is initialized with the set of single outlier could result in high standard deviation. Our main
compromised hosts H, and set of malicious domains M (when idea is to generate a histogram of inter-connection intervals be-
available). In the SOC hints case, H is the set of hint hosts tween a host and a domain, and compare it to that of a periodic
and M is the set of malicious domains (if provided). In the distribution using a known statistical distance. However, the
no-hint case, M is the set of potential C&C domains and H distance metric is highly sensitive to the histogram bin size
is the set of hosts contacting them. and alignment. Setting the size to a large value leads to over
The algorithm maintains several variables: R the set of smoothing, while a small value increases the sampling error.
rare domains contacted by hosts in H and N the set of When bins are statically defined, relatively close values might
newly labeled malicious domains (in a particular iteration). fall under different bins, affecting the distance metric.
In each iteration, the algorithm first detects suspicious C&C- We propose a dynamic histogram binning method instead.
like domains among set R using function Detect C&C whose Here we first cluster the inter-connection intervals (denoted
exact implementation will be provided next section. Note t1 , . . . , tm ) of successive connections from a host to a domain
that in the no-hint mode function Detect C&C will not on a particular day, and then define the bins dynamically
identify additional C&C domains (since they are used for from the generated clusters. Let the first interval t1 be the
seeding the algorithm and are already included in M). If no first cluster “hub.” An interval ti is considered as part of a
suspicious C&C domains are found, the algorithm computes cluster if it is within W of the cluster hub. Otherwise, a new
a similarity score for all rare domains in R with function cluster with hub ti is created. W is a fixed value, and acts as
Compute SimScore. The domain of maximum score (if our “bin width.” This dynamic binning method allows us to
 8

accommodate timing randomizations typically introduced by those UAs. The UA history is built during the training phase
attackers between connections. for a period of one month and then updated daily based on
Each resulting cluster is considered a bin, its frequency new ingested data. An UA is considered rare (after the training
is computed and the resulting histogram is compared to that period of one month) if it is used by less than a threshold of
of the periodic distribution with period equal to the highest- hosts (set at 10 based on SOC recommendation).
frequency cluster hub. We label the communications between Registration data features: Attacker-controlled sites tend
a host and a domain to be automated if their inter-connection to use more recently registered domains than legitimate
histogram is “close” to periodic (i.e., within a threshold JT ), ones [25]. In addition, attackers register their domains for
as determined by the Jeffrey divergence. For two histograms shorter periods of time to minimize their costs in case the
H = [(bi , hi )] and K = [(bi , ki )], if mi = (hi + ki )/2 the campaign is detected and taken down. We query WHOIS
Jeffrey divergence is defined as [35]: information and extract two features: DomAge (number of days
X since the domain was registered), and DomValidity (number of
hi ki
dJ (H, K) = (hi log + ki log ) days until the registration expires).
i
mi mi
Scoring automated domains. During the training stage, for
We choose the Jeffrey divergence metric motivated by the each rare domain identified as having automated connec-
fact that it is “numerically stable and robust to noise and size tions, we extract the six features explained above. We also
of histogram bins” [35]. We experimented with other statistical query VirusTotal for each rare automated domain and label
metrics (e.g., L1 distance), but the results were very similar it “reported” if at least one anti-virus engine reports it and
and omit them herein. The bin width W and distance threshold “legitimate” otherwise. Using the set of automated domains
JT parameters control the resiliency of the method to outliers visited in the enterprise for two weeks, we train a linear
and randomization introduced by attackers. We discuss their regression model, implemented using the function lm in the
selection according to the LANL dataset in §V-B. R package. The regression model outputs a weight for each
Additional features. For each rare automated domain visited feature, as well as the significance of that feature. The final
by an internal host we extract six additional features which score for each automated domain is a linear combination of
will be used for the C&C detector: feature values weighted by regression coefficients. Finally,
Domain connectivity features: We consider the number of based on the model, we select a score threshold Tc above
hosts contacting the domain (NoHosts) called domain con- which domains are labeled as potential C&C domains. We
nectivity and the number of hosts with automated connections provide results on the regression model and threshold selection
to the domain (AutoHosts). The intuition here is that most in Section VI-A.
rare domains (legitimate ones) are contacted by only one host, During the operation stage, domain scores are computed
but those rare domains contacted by multiple hosts are more using the weights of the regression model (built during train-
suspicious as they might indicate multiple compromised hosts ing). Function Detect C&C in Algorithm 1 returns true for a
under attacker’s control. domain if automated connections are detected to the domain
(from at least one host) and the domain score is above the
Web connection features: Based on discussions with security
threshold Tc computed during training.
professional at a large organization, web connections with no
web referrer information are more suspicious, as they are not D. Domain similarity
part of a user browsing session and might be generated by a
We consider a number of features when computing similar-
process running on the user machine. Typical user browsing
ity of a domain D with a set of domains S labeled malicious
sessions include web referer information, but in some cases the
in previous iterations of belief propagation.
web-referer is wiped out (e.g., java script or iframes embedded
in web pages). To capture this, we include a feature NoRef Domain connectivity. First is the domain connectivity as
denoting the fraction of hosts (among all hosts contacting that defined above.
domain) that use no web referer. Timing correlations. Second, we consider features related to
Additionally, most users have a fairly small number of the time when the domain D was visited by internal hosts.
user-agent strings in their HTTP connections (on average During initial infection stage of a campaign, we suspect that a
between 7 and 9 per user). Software configurations in an host visits several domains under the attacker’s control within
enterprise are more homogenous than in other networks (e.g., a relatively short time period (as explained in §II). We thus
university campus), and as such we’d expect that most user- consider the minimum timing difference between a host visit
agent strings are employed by a large population of users. With to domain D and other malicious domains in set S. The shorter
this intuition, the rare user-agent strings, those used by a small this interval, the more suspicious D is.
number of hosts, might indicate unpopular software installed IP space proximity. Third, we consider proximity in IP space
on the user machine which can potentially be associated with between D and malicious domains in set S, i.e., if they are
suspicious activities. We consider a feature RareUA denoting in the same IP/16 or IP/24. The intuition here is that attackers
the fraction of hosts that use no UA or a rare UA when host a large number of malicious domains under a small
contacting the domain. number of IP subnets (i.e., IP/24 or IP/16 subnets) [19], [26].
To determine the popularity of UA strings, we maintain a We provide measurement of the timing and IP proximity
history of UAs encountered across time and the hosts using features on the LANL dataset in §V-B. In addition, when
 9

Case Description Dates Hint Hosts

1 From one hint host detect the 3/2, 3/3, 3/4, One per day
testing set. We use the training set for selecting parameters
contacted malicious domains. 3/9, 3/10 needed for different components of the algorithm (dynamic
2 From a set of hint hosts detect 3/5, 3/6, 3/7, 3/8, Three or four histogram method, C&C communication detection, features
the contacted malicious domains. 3/11, 3/12, 3/13 per day
3 From one hint host detect the 3/14, 3/15, 3/17, One per day used for domain scoring, etc.). We show that parameters
contacted malicious domains and 3/18, 3/19, 3/20, chosen according to the training set perform well on new data
other compromised hosts. 3/21
4 Detect malicious domains and 3/22 No hints (testing set).
compromised hosts without hint.
Bin width Jeffrey distance Malicious Malicious All automated
TABLE I: The four cases in LANL challenge problem. W threshold pairs in pairs in pairs in
JT training testing testing days
5 seconds 0.0 12 15 7495
0.034 14 15 8070
0.06 15 17 8579
computing domain scores in belief propagation some of 0.35 15 18 34719
the features introduced for scoring C&C domains (NoRef, 10 seconds 0.0 12 16 15611
0.034 14 16 16224
RareUA, DomAge, DomValidity) are also used, as they might 0.06 15 18 16803
indicate suspicious activities. 20 seconds 0.0 12 15 23352
0.034 14 16 23964
During the training stage we build a linear regression model 0.06 15 18 24597
with eight features in total, using a set of (non-automated) rare
domains visited over two weeks. Results and threshold selec- TABLE II: Number of automated malicious (host, domain)
tion are provided in Section VI-A. During the operation stage, pairs in training and testing sets, as well as the number of
function Compute SimScore in Algorithm 1 computes a automated pairs for all days in testing set.
domain similarity score by using the feature weights found
by this model relative to the set of already labeled malicious Thresholds for dynamic histograms. The dynamic histogram
domains in previous iterations. method compares the histogram of inter-connection intervals
from successive connections by a host to a domain on a
V. E VALUATION ON THE LANL DATASET particular day to that of a periodic distribution with the
We start by describing the four cases in the LANL challenge goal of identifying automated communications. As described
problem. Then we discuss how we adapted our techniques de- in §IV-C the method can be configured with two parameters:
veloped for enterprise infection to detecting the LANL attacks bin width (W ) denoting the maximum distance between the
(when less information is available about domain names and bin hub and other intervals in the same bin, and the threshold
connection information). Still, using less features, we are able (JT ) denoting the maximum Jeffrey distance between the
to demonstrate that our belief propagation framework achieves two histograms. A connection with histogram at distance less
excellent results on the LANL challenge problem. than JT from the periodic histogram is considered automated.
Intuitively, the larger W and JT , the more resilience the
method provides against randomization and outliers, but more
A. The LANL Challenge Problem
legitimate connections are labeled automated as well.
The LANL dataset includes attack traces from 20 indepen- To determine the most suitable parameterization, we exper-
dent infection campaigns simulated by LANL domain experts. iment with 3 different bin widths (5, 10 and 20 seconds) and
Each simulation is an instance of the initial first-day infection choose the distance threshold JT according to the training set
stage of an independent campaign. LANL issued the APT of malicious automated connections. We manually labeled as
Infection Discovery Challenge to the community requesting automated 15 (host, domain) pairs in training set and 18 pairs
novel methods for the detection of malicious domains and in testing set corresponding to 18 distinct domains. Table II
compromised hosts involved in these attack instances [15]. shows the number of malicious (host, domain) pairs labeled
More specifically, each of the simulated attacks belongs to automated (in both training and testing sets), as well as all
one of four cases in increasing order of difficulty, described pairs labeled automated in the testing days for several choices
in Table I. Cases 1-3 include “hints” about the identity of one of W and JT . Intuitively, fixing one of the parameters W or
or multiple compromised hosts, while no hint is available for JT and increasing the other results in more legitimate domains
case 4. Answers (i.e., the malicious domains) are also given labeled automated.
for each attack for validation. For our purposes, we aim at capturing all malicious pairs in
the training and testing sets, while labeling fewest legitimate
B. Parameter selection connections automated. For the 10 and 20-second bin width,
When selecting various parameters for our algorithms, we the threshold capturing all 33 malicious pairs is 0.06, while
separate the 20 simulated attacks into two equal-size sets, for the 5-second bin width we need to increase the threshold
and use one for training (attacks from 3/2, 3/3, 3/4, 3/5, at 0.35. This larger threshold has the effect of increasing the
3/7, 3/12, 3/14, 3/15, 3/17, and 3/18), and the other for number of legitimate pairs labeled automated. Based on these
testing. We try to include attacks from each case in both results, we choose a bin size of 10 seconds and a threshold
training and testing sets, with the only exception of case 4, distance of 0.06 to achieve our desired properties.
simulated only on one day (3/22). We deliberately add this Features. Since domain names in the LANL dataset are
most challenging attack (in which no hint is provided) to the anonymized and the data contains only DNS requests, we have
 10

1
Hosts Domains Scores
0.9
Hint [Link] rainbow-.c3 1 C&C Comm. at
0.8
[Link] 10-minute interval
Fraction of domain pairs

0.7 1 [Link]
fluttershy.c3 2 0.8
[Link]
0.6
2 [Link]
0.5 pinkiepie.c3 3 0.42
2 [Link] [Link]
0.4 0.28
applejack.c3 4
0.3 3 [Link] [Link]

0.2 3 [Link]

0.1 Malicious and Malicious

Malicious and Rare Legitimate
0
0 10000 20000 30000 40000 50000 60000 70000
Interval (Seconds)
Fig. 4: Application of belief propagation to the 3/19 campaign.

Fig. 3: The CDFs between first connection to two malicious and legitimate domains in the training set. We found that 7
domains and a malicious and legitimate domain by a host. malicious domain pairs are in the same IP/24 subnet, while 18
share an IP/16 subnet. We observed few cases of legitimate
domains residing in the same subnet with malicious ones. With
access to a smaller number of features than in the enterprise the exception of 3/7, when more than 2000 pairs of malicious
case. Features related to domain registration (domain age and legitimate domains share the same IP24 or IP16 subnet
and registration validity), and features extracted from HTTP (due to a single malicious domain belonging to a popular
connections are not available in LANL. service), the rest of days we observe 20 pairs in the same
For detecting C&C communication, there are thousands of IP24 subnet and 155 pairs in the same IP16 subnet. We thus
automated domains daily (up to 5239). Restricting to rare use both IP/16 and IP/24 space features in detection but with
domains is beneficial in reducing the number of automated different weights.
domains by a factor of more than 100, but we still observe Domain similarity scores. In a particular iteration of belief
hundreds of rare automated domains. To identify C&C com- propagation a domain D is compared to the set of domains S
munications among this set, we combine multiple features that already labeled malicious in previous iterations. The domain
are available in this dataset, in particular domain connectivity score is computed as a function of three components: domain
and similarity in timing patterns across hosts. The C&C connectivity, timing correlation with a known malicious do-
detector for LANL is very simple: we consider an automated main in S (value 1 if the domain is contacted close in time
domain as potential C&C if there are at least two distinct hosts to a malicious domain and 0 otherwise), proximity in the IP
communicating with the domain at similar time periods (within space with malicious domains in M (value 2 if same /24
10 seconds). This heuristic works well because in the LANL subnet with a malicious domain, 1 if same /16 subnet with a
simulations there are always multiple infected hosts in every malicious domain and 0 otherwise). Each of these components
campaign. However, in our most general C&C detector for the increases the domain’s score. While in our general framework,
enterprise case, we consider domain connectivity as a feature we proposed a linear regression model for computing domain
which can be combined with other features extracted from scores (see §IV-C and §IV-D), we cannot apply that technique
registration data and HTTP connection. Our general method here due to limited samples of training data. Instead, we
can detect C&C domains contacted by a single host. choose a simple additive function that computes the score as
Using the LANL simulated attacks, we’d like to measure the sum of the three components above and then normalizes
the relevance of the timing and IP space similarity features it. This performs well in both cases 3 and 4 (based on the
among malicious domains. For compromised hosts in the training set we set the domain score threshold Ts at 0.25).
training set, we extract the timestamp of their first connection
to every rare domain visited. We plot in Figure 3 CDFs of the
C. Results
distributions of the time difference between visits to malicious
domains and a legitimate and malicious domain by the same We omit here description of the first two cases due to space
host. The graph confirms that connection intervals between limitations.
two malicious domains are much shorter than between a Starting from a hint host (case 3). We ran the belief
malicious and a legitimate domain. For example, 56% of propagation algorithm for a maximum of five iterations starting
visits to two malicious domains happen at intervals smaller from the provided hint host, but we stop the algorithm if the
than 160 seconds, while only 3.8% of malicious-to-legitimate maximum domain score is below the threshold Ts .
connection intervals are below this threshold (similar results An example of applying the algorithm to detecting the
are observed on testing dataset). campaign on 3/19 in the LANL dataset is given in Figure 4.
Next we measure similarity in IP space for malicious Starting from hint host [Link], in the first iteration
 11

C&C communication to domain rainbow-.c3 is detected at

10-minute average intervals. The domain is labeled malicious
and the second host ([Link]) compromised. In the follow- 1
ing three iterations, three rare domains of maximum score are
labeled malicious based on similarity with previously labeled 0.8

Fraction of domains
malicious domains (their scores are given on the right). The
algorithm stops at the fifth iteration when the maximum score 0.6
is below a threshold, at which point all labeled domains are
confirmed malicious.
0.4
The algorithm detects all 12 labeled malicious domains
in training days (with no false positives) and all 12 labeled
0.2
malicious domains in testing days at the cost of one false
positive for 3/21. Reported Legitimate
0
No hints (case 4). In the most challenging case no hint on 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8
compromised hosts are available to seed the belief propagation Domain score
algorithm. We thus identify first C&C communication and
seed the belief propagation algorithm with the C&C domains. Fig. 5: CDFs of automated reported/legitimate domain scores.
Interestingly, the same algorithm from case 3 delivered very
good results on case 4, where we did not have an opportunity
for training (case 4 was simulated only on a single day). The results are thoroughly validated through a combinations of
five domains identified by belief propagation were confirmed tools and manual analysis. The system is configurable with
malicious (by the simulation answer), and the algorithm did different parameters (e.g., scoring thresholds, number of it-
not have any false positives. erations in belief propagation, etc.) according to the SOC’s
Summary. The summary of our results on the four cases of processing capacity. We present the parameter selection, our
the LANL challenge are given in Table III. We define several validation methodology and the results in both modes of
metrics of interest: true detection rate (TDR) is the fraction of operation.
true positives and false detection rate (FDR) is the fraction of
false positives among all detected domains; and false negative A. Parameter selection
rate (FNR) is the fraction of malicious domains labeled as
legitimate by our detector. Overall, we achieve TDR of 98.33% Scoring automated domains. The parameters of the dynamic
(97.06% on the testing set), with FDR of 1.67% (2.94% on histogram method selected in §V-B result in 841 distinct
testing set) and FNR of 6.35% (2.94% on the testing set). automated domains for the month of February in the AC
dataset. We query VirusTotal for each rare automated domain
Case True Positives False Positives False Negatives and label it “reported” if at least one anti-virus engine reports
Training Testing Training Testing Training Testing
Case 1 6 4 0 0 2 0
it and “legitimate” otherwise (144 domains were reported by
Case 2 8 12 0 0 1 1 VirusTotal). We thus generate a large set of labeled automated
Case 3 12 12 0 1 0 0 domains and use it to learn the relevance of each feature in
Case 4 - 5 - 0 - 0
Total 26 33 0 1 3 1 identifying suspicious C&C domains.
In total, we observe 2888 automated (host, domain) pairs in
TABLE III: Results on LANL challenge.
the month of February for which we can extract all features
described in §IV-C. We divide the labeled set of automated
domains into a training set covering the first two weeks of
VI. E VALUATION ON E NTERPRISE DATA February, and testing set for the last two weeks. We construct
We implemented a fully operational system running in a linear regression model on the training set, which outputs
production starting from January 1 2014 to process the web a coefficient for each feature, as well as the significance of
proxies logs from the AC dataset. We use the data collected that feature. Among all features considered, the only one
in January for training various components of the system with low significance was AutoHosts, which we believe is
(e.g., the C&C detector, the domain scoring module, etc.) and highly correlated with NoHosts and thus omit it. The most
profiling external destinations and user-agent strings used by relevant features found by the model are DomAge and RareUA.
enterprise hosts in HTTP communication. Starting from Febru- DomAge is the only one negatively correlated with reported
ary 1 the system enters into the daily operation mode, in which domains (as they are in general more recently registered than
it processes new web proxies logs, applies normalization and legitimate ones), but all other features are positively correlated.
reduction techniques, compares the data with the profiles The graph in Figure 5 shows the difference between the
(which are also updated) and applies our detection techniques. scores of automated domains reported by VirusTotal and
First C&C communication is identified, and domains labeled legitimate ones on the training set. We observe that reported
as C&C are given as seeds to belief propagation. Second, domains have higher scores than legitimate ones. For instance,
domains confirmed by SOC (if available) and hosts contacting selecting a threshold of 0.4 for labeling an automated domain
them are provided as seeds in belief propagation. The detection suspicious results in 57.18% true detection rate and 10.59%
 12

false positive rate on the training set, and 54.95% true de- encountered daily. For domains whose WHOIS information
tection rate and 11.52% false positives on the testing set. We can not be parsed default values for DomAge and DomValidity
emphasize that our final goal is not identifying all automated are set at average values across all automated domains. As
domains reported by VirusTotal, but rather a significant frac- the first step, we vary the threshold for labeling automated
tion that allow us to bootstrap the belief propagation algorithm connections from 0.4 to 0.48 and present results for domains
and find new suspicious domains not yet detected by current detected as C&C domains (with score above the threshold)
anti-virus technologies. in Figure 6(a). The results demonstrate that as we increase
Domain similarity. To obtain a list of (non-automated) rare the threshold on automated domain scores from 0.4 to 0.48
domains and their features, we start from a set of compro- the number of domains labeled as C&C drops from 114 to
mised hosts (those contacting the C&C domains confirmed by 19, while accuracy increases (TDR increases from 85.08%
VirusTotal). We include each rare domain contacted by at least to 94.7%). Though FDR is higher for threshold 0.4, more
one host in this set, extract its features, query VirusTotal to get malicious domains (including 23 new ones not known to
an indication of its status, and divide the data into training and VirusTotal or SOC) are detected. They can be used to seed the
testing set, covering the first and last two weeks of February, belief propagation stage, and therefore we fix the threshold at
respectively. 0.4 to evaluate the overall effectiveness of belief propagation
We apply again linear regression on the training set to in this mode.
determine feature weights and significance. Among the eight
Next, we vary the threshold for domain scoring in belief
considered features described in §IV-D, the only one with low
propagation from 0.33 to 0.85 and the result (Figure 6(b))
significance was IP16, as we believe it’s highly correlated
shows that the number of all detected domains varies from 265
with IP24. The most relevant features identified by the model
to 114, with TDR ranging from 76.2% to 85.1%. Altogether
are RareUA, DomInterval, IP24 and DomAge. We still observe
in the most challenging case (when no hint is available), we
a difference in the score CDFs for reported and legitimate
detect 202 malicious and suspicious domains in February,
domains (we omit the plot due to space limitations).
associated with 945 hosts. Though the majority of the detected
B. Validation methodology domains are already alarmed by SOC and VirusTotal (132
We ran the detector in both modes, SOC hints and no-hints. for threshold 0.33), only 13 are reported in the IOC list
In the SOC hints mode we use domains from the IOC list and the remaining ones are unknown to the enterprise. More
provided by SOC as seeds. The domains output by our detector interestingly, we identified many new malicious and suspicious
in both modes (not considering the seeds provided by SOC) domains not known to the community (a total of 70 new
were validated as follows. We first query VirusTotal and the domains for threshold 0.33 resulting in an NDR of 26.4%).
IOC domain list to verify their status (three months after they This result suggests that our detector could greatly comple-
were detected – to allow anti-virus and blacklists to catch up). ment existing security tools by discovering new suspicious
If the domain is alerted upon by at least one scanner used by activities. Its main advantage is that it has the ability to detect
VirusTotal or it’s an IOC we consider it known malicious. new campaigns without traces of known malicious behavior.
For other domains, we collect additional information and We thoroughly examined the domains labeled as new ma-
hand them to a security analyst for manual investigation. licious and suspicious and found several prominent and inter-
Specifically, we retrieve the associated URLs from the log esting clusters. Among the new malicious domains, we found
data and crawl them to examine the responses. The URLs 5 domains hosting URLs with the same pattern /[Link]?
are also manually submitted to McAfee SiteAdvisor. Based later confirmed by the SOC as related to Sality worm. We
on the URLs, the response to our crawler and the result also found 15 domains with the same URL pattern reported
from SiteAdvisor, we classify the remaining domains into four by VirusTotal. Moreover, we identified a cluster of 10 DGA
categories: new malicious (e.g., same URL patterns as known domains with none of them reported by VirusTotal and SOC,
malicious domains, returning malicious content or flagged demonstrating our detector’s ability in capturing new mali-
by SiteAdvisor), suspicious (not resolvable when crawled, cious campaigns. All the malicious domains are under the
parked or having some questionable activities), legitimate (no TLD .info and their names have 4 or 5 characters (e.g.,
suspicious behavior or code observed) and unknown (504 [Link]). 9 out of the 10 domains hosts URLs with
HTTP response code, a sign of server error). Since we only pattern /[Link] and visiting them will be redirected to
have a few unknowns (6 in total), we remove them from the the remaining domain [Link].
final results. When reporting our results we use several metrics
of interest: TDR and FDR defined in §V-C, and new-discovery We labeled legitimate a set of 63 domains belonging to
rate (NDR) defined as the percentage of new malicious and categories like Ad-network, Gaming, Toolbar and Torrent
suspicious domains detected. Here TDR is the percentage of Tracker. They are captured by our detector because they
both known and new malicious and suspicious domains among exhibit suspicious features, like automated connections or are
all detected domains, and FDR = 1 - TDR. registered recently. Though they do not pose serious harm
to the enterprise, some of them are policy violations (e.g.,
C. Results for the no-hint case Gaming, Torrent Tracker). We labeled them legitimate since
We first evaluate the effectiveness of our detector in the we did not discover any suspicious activities, but we believe
no-hints mode. We compute scores for all automated domains these domains still need to be vetted.
 13

120 140
VirusTotal and SOC 300
VirusTotal and SOC VirusTotal and SOC
New malicious New malicious New malicious
100 Suspicious Suspicious 120 Suspicious
Number of detected domains Legitimate 250 Legitimate Legitimate
100
80 200
80
60 150
60
40 100
40

20 50 20

1
0 0 0
0.4 0.42 0.44 0.45 0.46 0.48 0.33 0.5 0.65 0.75 0.85 0.33 0.37 0.4 0.4 0.45
Domain score Domain score Domain score

Fig. 6: Statistics on detected domains. (a) C&C communication. (b) No hints. (c) SOC hints.

D. Results for the SOC hints case team performing manual investigation, and various tradeoffs
between accuracy and larger coverage.
We also present results in Figure 6(c) for the belief prop-
agation algorithm in SOC hints mode seeded with 28 IOC
domains. We do not include the seed domains in the results. VII. R ELATED W ORK
We set the domain score threshold at 0.4 for automated Our work focuses on detecting early-stage infections within
domains and vary the similarity score between 0.33 and 0.45. enterprise perimeters, including communications related to
In total, we detect between 137 domains (at threshold 0.33) to malware delivery and C&C. There has been a large body of
73 domains (at threshold 0.45), with TDR ranging from 78.8% work in this area, but to the best of our knowledge, we are
to 94.6%. Among the 137 detected domains, 108 turn out to the first to exploit the relationship between malicious domains
be malicious (either known or new) and suspicious, which is associated with the same attack campaign, and to detect them
about four times larger than the set used for seeding. by a graph-theoretic framework based on belief propagation.
Among the 108 malicious and suspicious domains, 79 We describe here related work in the literature.
domains are confirmed by SOC or VirusTotal, leaving 29 Detection of C&C communication. Some of the previous
domains as our new findings. We inspect the new findings work detecting C&C domains in botnets require malware
and identify an interesting group of domains generated through samples as input to detect connections with similar patterns
DGA. This group consists of 10 domains under TLD .info (e.g., BotFinder[37], Jackstraws[22]). Anomaly-based botnet
and the name for each domain has 20 characters (e.g., detection systems (e.g., BotMiner[16], BotSniffer[18] and
[Link]). Surprisingly, the registra- TAMD [41]) typically detect clusters of multiple synchronized
tion dates for most of the domains are later than the time hosts infected by the same malware. In contrast to these, our
when we detected them. For example, one domain is detected approach does not require malware samples and can detect a
on 2014/02/13 but registered on 2014/02/18. Attackers use single compromised host contacting the C&C server.
DGA domains to increase the robustness of their C&C centers DISCLOSURE [8] identifies C&C traffic using features
against take-downs, and they only register a portion of the extracted from NetFlow records but incorporates external in-
domains to reduce the cost. Our detector is able to detect telligence sources to reduce false positives. Our C&C detector
the malicious domains before registeration and obtain an is different in that it leverages enterprise-specific features
advantage in the arm-race. extracted from HTTP connections. From that perspective,
Finally, we compare the results of the two modes of ExecScent [28] is close to our work in detecting C&C com-
operation. Only 21 domains are detected in both modes, which munications in large enterprise network. However, ExecS-
is a small portion compared to 202 and 108 malicious and cent needs malware samples to extract templates representing
suspicious domains detected separately. When deployed by malicious C&C connections. The templates are adapted to
the enterprise, we suggest our detector configured to run in a specific enterprise considering the popularity of different
both modes, in order to have better coverage. We present two features (URL patterns, user-agent strings, etc.). Our work
case studies for both modes of operation in the Appendix. complements ExecScent in detecting new unknown malware
As we have shown, starting from a seed of known malicious that can be provided as input to the template generation
domains or hosts, the algorithm in SOC hints mode can module.
identify suspicious domains with high accuracy. The no-hint Detection of malware delivery. Nazca [21] analyzes web
case has the unique capability of identifying new unknown requests from ISP networks to identify traffic related to
attack campaigns, especially C&C communications of these malware delivery and unveils malicious distribution networks.
campaigns (even when only a single host is compromised). CAMP [32] determines reputation of binary downloads in
We recommend that C&C detected domains are first vetted by the browser and predicts malicious activities. BotHunter [17]
the SOC and then the algorithm can be used in the SOC hints identifies sequences of events during infection, as observed
mode for those confirmed malicious domains. from a network perimeter. Our approach does not depend
Both variants include configurable thresholds for scoring on specific events occurring during infection (which can be
automated and non-automated domains. These thresholds can changed easily or may not be observable), but more focused on
be chosen by the SOC according to the capacity of the detecting related malicious domains and compromised hosts.
 14

Detection of malicious domains. Domains used in malicious both domains associated with existing malware campaigns
activities are backed by highly resilient infrastructures to deal (and identified by VirusTotal), but with new presence in the
with takedowns or blacklisting, and hence exhibit unique char- enterprise of our study, as well as entirely new malware cam-
acteristics distinct from benign sites. Another branch of work paigns (not yet detected by anti-virus technologies). Since our
detects domains involved in malicious activities by patterns methods are focused on detecting the initial infection stages
observed in DNS traffic (e.g., EXPOSURE [9], Notos [5], of a campaign it is difficult to determine how many of these
Kopis [6], and Antonakakis et al. [7]). Paxson et al. [30] detect suspicious activities are related to more advanced attacks, and
malicious communication established through DNS tunnels. how many are mainstream malware variants. We believe that
Carter et al. [10] use community detection for identifying monitoring activity to these suspicious domains over longer
highly localized malicious domains in the IP space. periods of time, as well as correlating with information from
Anomaly detection in enterprise network. Beehive [40] other data sources will answer this question, and we leave this
is an unsupervised system identifying general anomalies in as an interesting avenue for future work.
an enterprise setting including policy violations and malware R EFERENCES
distribution. Our work is specifically targeting enterprise in- [1] Hackers in China attacked The Times for last 4 months.
fections which pose high risk and potential financial loss. [Link]
2013.
Targeted attacks. The threats in cyberspace keep evolving and [2] Target’s data breach: The commercialization of APT.
more sophisticated attacks recently emerged. Some targeted [Link]
attacks (APT) are well-funded, carefully orchestrated and 2014.
[3] Verizon 2014 data breach investigations report.
persist in the victim environments for years before detection. [Link] 2014.
Detecting targeted attacks in general is a very challenging [4] Alexa. AWS — Alexa Top Sites - Up-to-date lists of the top sites on
task. These attacks are usually very stealthy and able to evade the web. [Link] 2014.
[5] M. Antonakakis, R. Perdisci, D. Dagon, W. Lee, and N. Feamster.
existing defenses [3]. However during the automated infection Building a dynamic reputation system for DNS. In Proc. 19th USENIX
stage many campaigns (e.g., Shady RAT [20], Mirage [12], Security Symposium, 2010.
APT1 [26]) exhibit similar infection patterns. Recent studies [6] M. Antonakakis, R. Perdisci, W. Lee, N. Vasiloglou, II, and D. Dagon.
Detecting malware domains at the upper DNS hierarchy. In Proc. 20th
have shown that even though in theory APTs could be ar- USENIX Security Symposium, 2011.
bitrarily sophisticated, in practice goal-oriented attackers use [7] M. Antonakakis, R. Perdisci, Y. Nadji, N. Vasiloglou, S. Abu-Nimeh,
relatively low levels of sophistication [38], [27], [24]. We W. Lee, and D. Dagon. From throw-away traffic to bots: Detecting the
rise of DGA-based malware. In Proc. 21st USENIX Security Symposium,
leverage some common patterns observed during the infection 2012.
stage to build a detector tailored to an enterprise. Our detection [8] L. Bilge, D. Balzarotti, W. Robertson, E. Kirda, and C. Kruegel.
result on the LANL’s APT infection discovery challenge indi- Disclosure: Detecting botnet Command-and-Control servers through
large-scale NetFlow analysis. In Proc. 28th Annual Computer Security
cates that our techniques have potential in detecting infections Applications Conference, ACSAC, 2012.
originated from targeted attacks. [9] L. Bilge, E. Kirda, K. Christopher, and M. Balduzzi. EXPOSURE:
Finding malicious domains using passive DNS analysis. In Proc. 18th
Symposium on Network and Distributed System Security, NDSS, 2011.
VIII. L IMITATIONS AND D ISCUSSION [10] K. M. Carter, N. Idika, and W. W. Streilein. Probabilistic threat
propagation for network security. IEEE Transactions on Information
Attackers could in principle use a number of techniques Forensics and Security, 9:–, 2014.
to evade our detectors. For instance, they may communicate [11] Command Five Pty Ltd. Command and control in the fifth domain.
through different channels than HTTP/HTTPs but other ports [Link] APT [Link],
2012.
are commonly blocked at enterprise borders. Attackers could [12] Dell SecureWorks. The Mirage campaign.
also compromise popular web sites for delivering malicious [Link]
payloads or C&C communications. However, this is not 2012.
[13] Dell SecureWorks. Top banking botnets of 2013.
broadly observed. The analysis of traffic to popular sites [Link]
require different models and assumptions, due to the amount 2014.
of (benign) noise. As another evasion technique, attackers [14] N. Falliere, L. O. Murchu, and E. Chien. [Link] dossier.
[Link] response/[Link], 2011.
can randomize timing patterns to C&C servers, but according [15] P. Ferrell. APT infection discovery us-
to published reports ([26]) this is uncommon. Our dynamic ing DNS data. C3E Challenge Problem.
histogram method is resilient against small amounts of ran- [Link]
2013.
domization introduced by attackers. Detecting C&C commu- [16] G. Gu, R. Perdisci, J. Zhang, and W. Lee. BotMiner: Clustering
nication with completely randomized timing patterns (without analysis of network traffic for protocol and structure-independent botnet
having access to malware samples and without correlating detection. In Proc. 17th USENIX Security Symposium, 2008.
[17] G. Gu, P. Porras, V. Yegneswaran, M. Fong, and W. Lee. BotHunter:
activity from multiple hosts) is a challenging problem to the Detecting malware infection through IDS-driven dialog correlation. In
community. Nevertheless, we believe that the infection patterns Proceedings of 16th USENIX Security Symposium on USENIX Secu-
that we detect are quite prevalent in many attacks. rity Symposium, SS’07, pages 12:1–12:16, Berkeley, CA, USA, 2007.
USENIX Association.
The approach we proposed is meant to complement the [18] G. Gu, J. Zhang, and W. Lee. BotSniffer: Detecting botnet command
existing tools rather than replace them. The results from §VI and control channels in network traffic. In Proc. 15th Network and
demonstrate that our belief propagation algorithm in both vari- Distributed System Security Symposium, NDSS, 2008.
[19] S. Hao, N. Feamster, and R. Pandrangi. Monitoring the initial DNS
ants (SOC hints and no-hint) detects new suspicious activities behavior of malicious domains. In Proc. ACM Internet Measuremnt
overlooked by deployed defense mechanisms. These include Conference, IMC ’11, 2011.
 15

[20] Hon Lau. The truth behind the Shady RAT. We start from detecting suspicious C&C domains (24 do-
[Link] 2011. mains are identified that day). We pick for illustration one
[21] L. Invernizzi, S. Miskovic, R. Torres, S. Saha, S.-J. Lee, C. Kruegel,
and G. Vigna. Nazca: Detecting malware distribution in large-scale ([Link]) contacted by three hosts reg-
networks. In Proceedings of the ISOC Network and Distributed System ularly at the same period (120 seconds). This domain is
Security Symposium (NDSS ’14), Feb 2014. confirmed by VirusTotal and is associated with a malware
[22] G. Jacob, R. Hund, C. Kruegel, and T. Holz. Jackstraws: Picking
command and control connections from bot traffic. In Proc. 20th labeled by Sophos as Troj/Agent-AGLT. Starting from
USENIX Security Symposium, 2011. this C&C domain, belief propagation iteratively discovers two
[23] James Wyke. The ZeroAccess rootkit — Naked Security. other domains confirmed by VirusTotal (likely the delivery
[Link] 2012.
[24] S. Le Blond, A. Uritesc, C. Gilbert, Z. L. Chua, P. Saxena, and E. Kirda. stage) and two other hosts connecting to them.
A look at targeted attacks through the lense of an NGO. In Proc. 23rd
USENIX Security Symposium, 2014. Hosts
[25] J. Ma, L. K. Saul, S. Savage, and G. M. Voelker. Beyond blacklists:
Learning to detect malicious web sites from suspicious urls. In Proc. ost5
Domains
15th ACM International Conference on Knowledge Discovery and Data
Mining, KDD, 2009. ost2 [Link]
[26] MANDIANT. APT1: Exposing one of China’s cyber espionage units.
Report available from [Link], 2013. ost
[Link]
[27] W. Marczak, J. Scott-Railton, M. Marquis-Boire, and V. Paxson. When
governments hack opponents: A look at actors and technology. In Proc.
B eacon with
20
s
[Link]
23rd USENIX Security Symposium, 2014.
ost4
Beacon with
20
s
[28] T. Nelms, R. Perdisci, and M. Ahamad. ExecScent: Mining for new C&C Beacon with
20
s
ost3
domains in live networks with adaptive control protocol templates. In
Proc. 22nd USENIX Security Symposium, 2013.
[29] Panda Security. Annual report PandaLabs - 2013 summary.
[Link] [Link],
2014. Fig. 7: Example community of compromised hosts and de-
[30] V. Paxson, M. Christodorescu, M. Javed, J. Rao, R. Sailer, D. Schales, tected domains in no-hint mode on 2/13.
M. P. Stoecklin, K. Thomas, W. Venema, and N. Weaver. Practical
comprehensive bounds on surreptitious communication over DNS. In
Proc. 22nd USENIX Security Symposium, 2013. Figure 8 illustrates a community of domains detected in
[31] J. Pearl. Reverend Bayes on inference engines: A distributed hierarchical the SOC hints mode on 2/10. To bootstrap the detection, we
approach. In Second National Conference on Artificial Intelligence,
1982.
use domain [Link] from the SOC database as
[32] M. A. Rajab, L. Ballard, N. Lutz, P. Mavrommatis, and N. Provos. a seed. This appears to be a C&C server for Zeus botnet.
CAMP: content-agnostic malware protection. In Proceedings of the The domain is accessed by Host 5 which is confirmed
ISOC Network and Distributed System Security Symposium (NDSS ’13),
Feb 2013.
infected by the SOC team. Host 5 contacted 7 domains
[33] U. Rivner. Anatomy of an attack. registered under TLD .org. Four of them are confirmed by
[Link]/rivner/anatomy-of-an-attack, 2011. SOC and also reported by Sophos as contacted by different
[34] RSA. Stalking the kill chain. [Link]
2012.
malwares (Troj Ramdo-B, Troj Ramdo-K, Troj Ramdo-V
[35] Y. Rubner, C. Tomasi, and L. J. Guibas. The earth mover’s distance as and Troj Symmi-S). This indicates that the compromised ma-
a metric for image retrieval. International Journal of Computer Vision, chine downloaded additional malware after the initial compro-
40:99–121, 2000.
[36] G. Stringhini, C. Kruegel, and G. Vigna. Shady Paths: Leveraging surfing
mise. Two of the remaining .org domains are not confirmed
crowds to detect malicious web pages. In Proc. 20th ACM Conference by SOC but alarmed by VirusTotal. Interestingly, one domain
on Computer and Communications Security, CCS, 2013. ([Link]) has a similar naming pattern with
[37] F. Tegeler, X. Fu, G. Vigna, and C. Kruegel. BotFinder: Finding bots in
network traffic without deep packet inspection. In Proc. 8th International
other malicious domains, but is not picked up by either
Conference on Emerging Networking Experiments and Technologies, SOC or VirusTotal. This is an example of new discovered
CoNEXT ’12, 2012. domain. The second iteration of belief propagation discovers
[38] O. Thonnard, L. Bilge, G. OGorman, S. Kiernan, , and M. Lee. Industrial
espionage and targeted attacks: Understanding the characteristics of an
six additional hosts contacting a similar set of domains as
escalating threat. In Proc. 15th International Symposium on Recent Host 5, indicating that they could be infected with the same
Advances in Intrusion Detection, RAID, 2012. malware. Besides, four other suspicious domains are also
[39] WebSense Security Lab. WebSense 2014 Threat Report.
[Link]
identified as contacted by these hosts, with three of them
2014. confirmed by VirusTotal (including one automated domain)
[40] T.-F. Yen, A. Oprea, K. Onarlioglu, T. Leetham, W. Robertson, A. Juels, and only one ([Link]) being legitimate.
and E. Kirda. Beehive: Large-scale log analysis for detecting suspicious
activity in enterprise networks. In Proceedings of the 29th Annual
Computer Security Applications Conference, ACSAC ’13, pages 199–
208, New York, NY, USA, 2013. ACM.
[41] T.-F. Yen and M. K. Reiter. Traffic aggregation for malware detection. In
Proc. Intl. Conf. Detection of Intrusions and Malware, and Vulnerability
Assessment, DIMVA, 2008.

A PPENDIX
Below we report two interesting communities of malicious
domains and compromised hosts detected by our techniques.
Figure 7 illustrates an example of a community of ma-
licious domains detected in the no-hint mode on 2/13.
 16

Domains

[Link][Link]

aaimomuiqqqkiki.org
osts
ost kucmcamaqsgmai[Link]

ost uogwoigiuwe[Link]

ost3 cegauoqs[Link]

ost4 [Link]

ost7 kuqcu[Link]
ost5 [Link]

ost6 [Link]

eacon wit 0s [Link]

Seed
[Link]

xtremeso[Link]

Fig. 8: Example community of compromised hosts and de-

tected domains in SOC hints mode on 2/10. The yellow
diamond-shape domain is used as seed, purple ellipse-shape
domains are detected by VirusTotal and red hexagon-shape
domains are confirmed malicious by SOC. The grey rectangle-
shape domains are not confirmed by any existing tools at
the time of detection. The hostnames are anonymized. Red
hexagon-shape hosts are confirmed by SOC and purple ellipse-
shape ones are other compromised hosts.