Building a Dynamic Reputation System for DNS
Manos Antonakakis, Roberto Perdisci, David Dagon, Wenke Lee, and Nick Feamster
College of Computing, Georgia Institute of Technology,{manos,rperdisc,dagon,wenke,feamster}@cc.gatech.edu
Abstract
The Domain Name System (DNS) is an essential protocol
used by both legitimate Internet applications and cyber attacks. For example, botnets rely on DNS to support agile command and control infrastructures. An effective way to disrupt
these attacks is to place malicious domains on a “blocklist”(or “blacklist”) or to add a filtering rule in a firewall or network intrusion detection system. To evade such security countermeasures, attackers have used DNS agility, e.g., by using
new domains daily to evade static blacklists and firewalls. In
this paper we propose Notos, a dynamic reputation system for
DNS. The premise of this system is that malicious, agile useof DNS has unique characteristics and can be distinguishedfrom legitimate, professionally provisioned DNS services. Notos uses passive DNS query data and analyzes the networkand zone features of domains. It builds models of known legitimate domains and malicious domains, and uses these models
to compute a reputation score for a new domain indicative ofwhether the domain is malicious or legitimate. We have evaluated Notos in a large ISP’s network with DNS traffic from
1.4 million users. Our results show that Notos can identify
malicious domains with high accuracy (true positive rate of
96.8%) and low false positive rate (0.38%), and can identify
these domains weeks or even months before they appear in
public blacklists.

1 Introduction
The Domain Name System (DNS) [12, 13] maps domainnames to IP addresses, and provides a core service to applications on the Internet. DNS is also used in network security to
distribute IP reputation information, e.g., in the form of DNSbased Block Lists (DNSBLs) used to filter spam [18, 5] orblock malicious web pages [26, 14].
Internet-scale attacks often use DNS as well because they
are essentially Internet-scale malicious applications. For example, spyware uses anonymously registered domains to exfiltrate private information to drop sites. Disposable domains
are used by adware to host malicious or false advertisingcontent. Botnets make agile use of short-lived domains toevasively move their command-and-control (C&C) infrastructure. Fast-flux networks rapidly change DNS records to evade
blacklists and resist take downs [25]. In an attempt to evadedomain name blacklisting, attackers now make very aggressive use of DNS agility. The most common example of an agile malicious resource is a fast-flux network, but DNS agility
takes many other forms including disposable domains (e.g.,tens of thousands of randomly generated domain names used
for spam or botnet C&C), domains with dozens of A records or
NS records (in excess of levels recommended by RFCs, in order to resist takedowns), or domains used for only a few hoursof a botnet’s lifetime. Perhaps the best example is the Conficker.C worm [15]. After Conficker.C infects a machine, itwill try to contact its C&C server, chosen at random from a listof 50,000 possible domain names created every day. Clearly,
the goal of Conficker.C was to frustrate blacklist maintenanceand takedown efforts. Other malware that abuse DNS include
Sinowal (a.k.a. Torpig) [9], Kraken [20], and Srizbi [22]. The
aggressive use of newly registered domain names is seen inother contexts, such as spam campaigns and malicious flux
networks [25, 19]. This strategy delays takedowns, degrades
the effectiveness of blacklists, and pollutes the Internet’s namespace with unwanted, discarded domains.
In this paper, we study the problem of dynamically assigning reputation scores to new, unknown domains. Our main
goal is to automatically assign a low reputation score to adomain that is involved in malicious activities, such as malware spreading, phishing, and spam campaigns. Conversely,
we want to assign a high reputation score to domains that areused for legitimate purposes. The reputation scores enable dynamic domain name blacklists to counter cyber attacks much
more effectively. For example, with static blacklisting, by thetime one has sufficient evidence to put a domain on a blacklist, it typically has been involved in malicious activities fora significant period of time. With dynamic blacklisting ourgoal is to decide, even for a new domain, whether it is likely
used for malicious purposes. To this end, we propose Notos,
a system that dynamically assigns reputation scores to domainnames. Our work is based on the observation that agile malicious uses of DNS have unique characteristics, and can be distinguished from legitimate, professionally provisioned DNS
services. In short, network resources used for malicious andfraudulent activities inevitably have distinct network characteristics because of their need to evade security countermeasures. By identifying and measuring these features, Notos canassign appropriate reputation scores.
Notos uses historical DNS information collected passively
from multiple recursive DNS resolvers distributed across theInternet to build a model of how network resources are allocated and operated for legitimate, professionally run Internet services. Notos also uses information about malicious domain names and IP addresses obtained from sources such as
spam-traps, honeynets, and malware analysis services to builda model of how network resources are typically allocated byInternet miscreants. With these models, Notos can assign reputation scores to new, previously unseen domain names, therefore enabling dynamic blacklisting of unknown malicious domain names and IP addresses.
Previous work on dynamic reputation systems mainly focused on IP reputation [24, 31, 1, 21]. To the best of ourknowledge, our system is the first to create a comprehensive
dynamic reputation system around domain names. To summarize, our main contributions are as follows:• We designed Notos, a dynamic, comprehensive reputation system for DNS that outputs reputation scores fordomains. We constructed network and zone features that
capture the characteristics of resource provisioning, usages, and management of domains. These features enable
Notos to learn models of how legitimate and malicious
domains are operated, and compute accurate reputation
scores for new domains.
• We implemented a proof-of-concept version of our system, and deployed it in a large ISP’s DNS network in
Atlanta, GA and San Jose, CA, USA, where we observed DNS traffic from 1.4 million users. We also usedpassive DNS data from Security Information Exchange(SIE) project [3]. This extensive real-world evaluationshows Notos can correctly classify new domains witha low false positive rate (0.38%) and high true positive
rate (96.8%). Notos can detect and assign a low reputation score to malware- and spam-related domain names
several days or even weeks before they appear on public
blacklists.
Section 2 provides some background on DNS and related
works. Readers familiar with this may skip to Section 3, where
we describe our passive DNS collection strategy and otherwhitelist and blacklist inputs. We also describe three feature extraction modules that measure key network, zone andevidence-based features. Finally, we describe how these features are clustered and incorporated into the final reputationengine. To evaluate the output of Notos, we gathered an extensive amount of network trace data. Section 4 describes thedata collection process, and Section 5 details the sensitivity ofeach module and final output.

2

Background and Related Work

DNS is the protocol that resolves a domain name, likewww.example.com, to its corresponding IP address, for example 192.0.2.10. To resolve a domain, a host typicallyneeds to consult a local recursive DNS server (RDNS). A recursive server iteratively discovers which Authoritative Name
Server (ANS) is responsible for each zone. The typical resultof this iterative process is the mapping between the requested
domain name and its current IP addresses.
By aggregating all unique, successfully resolved A-type
DNS answers at the recursive level, one can build a passive
DNS database. This passive DNS (pDNS) database is effectively the DNS fingerprint of the monitored network andtypically contains unique A-type resource records (RRs)
that were part of monitored DNS answers. A typical RR
for the domain name example.com has the following format: {example.com. 78366 IN A 192.0.2.10},
which lists the domain name, TTL, class, type, and rdata. For
simplicity, we will refer to an RR in this paper as just a tupleof the domain name and IP address.
Passive DNS data collection was first proposed by Florian
Weimer [27]. His system was among the first that appearedin the DNS community with its primary purpose being theconversion of historic DNS traffic into an easily accessible
format. Zdrnja et al. [29] with their work in “Passive Monitoring of DNS Anomalies” discuss how pDNS data can beused for gathering security information from domain names.
Although they acknowledge the possibility of creating a DNS
reputation system based on passive DNS measurement, they
do not quantify a reputation function. Our work uses the ideaof building passive DNS information only as a seed for computing statistical DNS properties for each successful DNS resolution. The analysis of these statistical properties is the basic
building block for our dynamic domain name reputation function. Plonka et al. [17] introduced Treetop, a scalable way tomanage a growing collection of passive DNS data and at thesame time correlate zone and network properties. Their cluster zones are based on different classes of networks (class A,class B and class C). Treetop differentiates DNS traffic basedon whether it complies with various DNS RFCs and based on
the resolution result. Plonka’s proposed method, despite being
novel and highly efficient, offers limited DNS security information and cannot assign reputation scores to records.
Several papers, e.g., Sinha et al. [24] have studied the effectiveness of IP blacklists. Zhang, et al. [31] showed that the hit
rate of highly predictable blacklists (HBLs) decreases significantly over a period of time. Our work addresses the dynamic
DNS blacklisting problem that makes it significantly different from the highly predictable blacklists. Importantly, Notos
does not aim to create IP blacklists. By using properties of the
DNS protocol, Notos can rank a domain name as potentiallymalicious or not. Garera et al. [8] discussed “phishing” detection predominately using properties of the URL and not sta-tistical observations about the domains or the IP address. The
statistical features used by Holz et al. [10] to detect fast flux
networks are similar to the ones we used in our work, however,Notos utilizes a more complete collection of network statistical features and is not limited to fast flux networks detection.
Researchers have attempted to use unique characteristics
of malicious networks to detect sources of malicious activity.
Anderson et al. [1] proposed Spamscatter as the first system toidentify and characterize spamming infrastructure by utilizing
layer 7 analysis (i.e., web sites and images in spam). Hao et
al. [21] proposed SNARE, a spatio-temporal reputation engine
for detecting spam messages with very high accuracy and low
false positive rates. The SNARE reputation engine is the firstwork that utilized statistical network-based features to harvest
information for spam detection. Notos is complementary to
SNARE and Spamscatter, and extends both to not only detect spam, but also identify other malicious activity such as
phishing and malware hosting. Qian et al. [28] present theirwork on spam detection using network-based clustering. In
this work, they show that network-based clusters can increase
the accuracy of spam-oriented blacklists. Our work is moregeneral, since we try to identify various kinds of malicious
domain names. Nevertheless, both works leverage networkbased clustering for identifying malicious activities.
Felegyhazi et al. [7] proposed a DNS reputation blacklisting methodology based on WHOIS observations. Our systemdoes not use WHOIS information making our approaches complementary by design. Sato et al. [23] proposed a way to extend current blacklists by observing the co-occurrence of IP
address information. Notos is a more generic approach thanthe proposed system by Sato and is not limited to botnet related domain name detection. Finally, Notos builds the reputation function mainly based upon passive information from
DNS traffic observed in real networks — not traffic observed
from honeypots.
No previous work has tried to assign a dynamic domainname reputation score for any domain that traverses the edgeof a network. Notos harvests information from multiple
sources—the domain name, its effective zone, the IP address,
the network the IP address belongs to, the Autonomous System (AS) and honeypot analysis. Furthermore, Notos uses
short-lived passive DNS information. Thus, it is difficult for amalicious domain to dilute its passive DNS footprint.

3 Notos: A Dynamic Reputation System
The goal of the Notos reputation system is to dynamicallyassign reputation scores to domain names. Given a domainname d, we want to assign a low reputation score if d is involved in malicious activities (e.g., if it has been involved withbotnet C&C servers, spam campaigns, malware propagation,etc.). On the other hand, we want to assign a high reputation
score if d is associated with legitimate Internet services.

Notos’ main source of information is a passive DNS(pDNS) database, which contains historical information about
domain names and their resolved IPs. Our pDNS database isconstantly updated using real-world DNS traffic from multiple
geographically diverse locations as shown in Figure 1. We collect DNS traffic from two ISP recursive DNS servers (RDNS)
located in Atlanta and San Jose. The ISP nodes witness 30,000
DNS queries/second during peak hours. We also collect DNS
traffic through the Security Information Exchange (SIE) [3],which aggregates DNS traffic received by a large number of
RDNS servers from authoritative name servers across North
America and Europe. In total, the SIE project processes approximately 200 Mbit/s of DNS messages, several times thetotal volume of DNS traffic in a single US ISP.
Another source of information we use is a list of known
malicious domains. For example, we run known malware
samples in a controlled environment and we classify as suspicious all the domains contacted by malware samples that do
not match a pre-compiled white list. In addition, we extract
suspicious domain names from spam emails collected using alarge spam-trap. Again, we discard the domains that match
our whitelist and consider the rest as potentially malicious.
Furthermore, we collect a large list of popular, legitimate domains from alexa.com (we discuss our data collection andanalysis in more details in Section 4). The set of known malicious and legitimate domains represents our knowledge base,and is used to train our reputation engine, as we discuss in
Section 4.
Intuitively, a domain name d can be considered suspicious
when there is evidence that d or its IP addresses are (or were inprevious months) associated with known malicious activities.
The more evidence of “bad associations” we can find aboutd, the lower the reputation score we will assign to it. On theother hand, if there is evidence that d is (or was in the past) associated with legitimate, professionally run Internet services,
we will assign it a higher reputation score.

3.1

System Overview

Before describing the internals of our reputation system, we introduce some basic terminology. A domainname d consists of a set of substrings or labels separated by a period; the rightmost label is called the toplevel domain, or TLD. The second-level domain (2LD)
represents the two rightmost labels separated by a period; the third-level domain (3LD) analogously contains thethree rightmost labels, and so on. As an example, given
the domain name d=“a.b.example.com”, T LD(d)=“com”,
2LD(d)=“example.com”, and 3LD(d)=“b.example.com”.
Let s be a domain name (e.g., s=“example.com”). We define Zone(s) as the set of domains that include s and all domain names that end with a period followed by s (e.g., domains ending in “.example.com”).
Let D = {d1 , d2 , ..., dm } be a set of domain names. We

Dynamic
Reputation
ScoresPassive DNS
Database

S.I.E

Resource Record (RR)
Domain Name - IP

Reputation
EngineBlack List

Notos

SubnetISP Recursive
DNS Server(Atlanta)

SubnetInternet

pDNS

pDNS
Query

Honeypot
Data

Network BasedFeature Extraction

Zone BasedFeature Extraction

Evidence BasedFeature Extraction

SubnetSubnetF1

SubnetISP Recursive
DNS Server(SJC)

Figure 1. System overview.

call A(D) the set of IP addresses ever pointed to by any domain name d ∈ D.
Given an IP address a, we define BGP (a) to be the setof all IPs within the BGP prefix of a, and AS(a) as the setof IPs located in the autonomous system in which a resides.
In addition, we can extend these functions to take as input
a set of IPs: given IP set A = a1 , a2 , ..., aN , BGP (A) =S
k=1..N BGP (ak ); AS(a) is similarly extended.
To assign a reputation score to a domain name d we proceed
as follows. First, we consider the most current set Ac (d) ={ai }i=1..m of IP addresses to which d points. Then, we query
our pDNS database to retrieve the following information:• Related Historic IPs (RHIPs), which consist of the unionof A(d), A(Zone(3LD(d))), and A(Zone(2LD(d))).
In order to simplify the notation we will refer toA(Zone(3LD(d))) and A(Zone(2LD(d))) as A3LD (d)and A2LD (d), respectively.
• Related Historic Domains (RHDNs), which comprise theentire set of domain names that ever resolved to an IP
address a ∈ AS(A(d)). In other words, RHDNs containall the domains di for which A(di ) ∩ AS(A(d)) 6= ∅.
After extracting the above information from our pDNS
database, we measure a number of statistical features. Specifically, for each domain d we extract three groups of features,as shown in Figure 2:• Network-based features: The first group of statisticalfeatures is extracted from the set of RHIPs. We measurequantities such as the total number of IPs historically associated with d, the diversity of their geographical location, the number of distinct autonomous systems (ASs)in which they reside, etc.
• Zone-based features: The second group of features we
extract are those from the RHDNs set. We measure the

F2

F3... F18

Network BasedFeatures Vector

F1

F2

F3

... F17

Zone BasedFeatures Vector

F1

F2

F3

...

F6

Reputation
EngineEvidence BasedFeatures Vector

Figure 2. Computing network-based, zone-based,
evidence-based features.

average length of domain names in RHDNs, the numberof distinct TLDs, the occurrence frequency of different
characters, etc.
• Evidence-based features: The last set of features includes the measurement of quantities such as the numberof distinct malware samples that contacted the domain d,
the number of malware samples that connected to any of
the IPs pointed by d, etc.
Once extracted, these statistical features are fed to thereputation engine. Notos’ reputation engine operates in twomodes: an off-line “training” mode and an on-line “classification” mode. During the off-line mode, Notos trains the reputation engine using the information gathered in our knowledge
base, namely the set of known malicious and legitimate domain names and their related IP addresses. Afterwards, during
the on-line mode, for each new domain d, Notos queries thetrained reputation engine to compute a reputation score for d(see Figure 3). We now explain the details about the statisticalfeatures we measure, and how the reputation engine uses themduring the off-line and on-line modes to compute a domainnames’ reputation score.

3.2

Statistical Features

In this section we identify key statistical features and theintuition behind their selection.
3.2.1

Network-based Features

Given a domain d we extract a number of statistical featuresfrom the set RHIPs of d, as mentioned in Section 3.1. Our
network-based features describe how the operators who own dand the IPs that domain d points to, allocate their network resources. Internet miscreants often abuse DNS to operate theirmalicious networks with a high level of agility. Namely, theOff-Line "Training" Mode

d

Train
Reputation
FunctionEV(d)Network &Zone
ClusteringNM(d)Network Profile
Modeling

Passive
DNS DBdClassification
Confidences

2-Class Meta
ClassifierNM(d)Network
Based Vectors

DC(d)

(a)

ComputeVectors
Network & Zone
AssigmentDC(d`)

dNetwork Based
Clustering

Zone Based
Clustering

Cluster
Characterization

Network
Based Vectors

Zone
Based Vectors

Radius(R) &KNN(z)

DC(d)d`Network Profile
Classification

NM(d`)New RR
Dynamic
Reputation
RatingOn-Line Modef(d')

Reputation
Assignment(b)
EV(d`)

Figure 4. (a) Network profile modeling in Notos.
(b) Network and zone based clustering in Notos.

Figure 3. Off-line and on-line modes in Notos.
domain names and IPs that are used for malicious purposes
are often short-lived and are characterized by a high churnrate. This agility avoids simple blacklisting or removals by
law enforcement. In order to measure the level of agility ofa domain name d, we extract eighteen statistical features that
describe d’s network profile. Our network features fall into thefollowing three groups:• BGP features. This subset consists of a total of nine features. We measure the number of distinct BGP prefixes
related to BGP (A(d)), the number of countries in whichthese BGP prefixes reside, and the number of organizations that own these BGP prefixes; the number of distinct
IP addresses in the sets A3LD (d) and A2LD (d); the number of distinct BGP prefixes related to BGP (A3LD (d))
and BGP (A2LD (d)), and the number of countries inwhich these two sets of prefixes reside.
• AS features. This subset consists of three features,
namely the number of distinct autonomous systems related to AS(A(d)), AS(A3LD (d)), and AS(A2LD (d)).
• Registration features. This subset consists of six features.
We measure the number of distinct registrars associatedwith the IPs in the A(d) set; the diversity in the registration dates related to the IPs in A(d); the number ofdistinct registrars associated with the IPs in the A3LD (d)and A2LD (d) sets; and the diversity in the registration
dates for the IPs in A3LD (d) and A2LD (d).
While most legitimate, professionally run Internet services
have a very stable network profile, which is reflected into low
values of the network features described above, the profiles ofmalicious networks (e.g., fast-flux networks) usually change
relatively frequently, thus causing their network features to be
assigned higher values. We expect a domain name d from alegitimate zone to exhibit a small values in its AS features,

mainly because the IPs in the RHIPs should belong to thesame organization or a small number of different organizations. On the other hand, if a domain name d participates inmalicious activities (i.e., botnet activities, flux networks), thenit could reside in a large number of different networks. The listof IPs in the RHIPs that correspond to the malicious domainname will produce AS features with higher values. In the same
sense, we measure that homogeneity of the registration information for benign domains. Legitimate domains are typicallylinked to address space owned by organizations that acquireand announce network blocks in some order. This means thatthe registration-feature values for a legitimate domain named that owned by the same organizations will produce a list of
IPs in the RHIPs that will have small registration feature values. If this set of IPs exhibits high registration feature values,
it means that they very likely reside in different registrars andwere registered on different dates. Such registration-feature
properties are typically linked with fraudulent domains.
3.2.2

Zone-based Features

The network-based features measure a number of characteristics of IP addresses historically related to a given domain named. On the other hand, the zone-based features measure thecharacteristics of domain names historically associated withd. The intuition behind the zone-based features is that while
legitimate Internet services may be associated with many different domain names, these domain names usually have strong
similarities. For example, google.com, googlesyndication.com, googlewave.com, etc., are all related toInternet services provided by Google, and contain the string“google” in their name. On the other hand, malicious domainnames related to the same spam campaign, for example, often
look randomly generated and share few common characteristics. Therefore, our zone-based features aim to measure thelevel of diversity across the domain names in the RHDNs set.
Given a domain name d, we extract seventeen statistical features that describe the properties of the set RHDNs of domainnames related to d. We divide these seventeen features into
two groups:• Blacklist features. We measure three features, namely the
number of IP addresses in A(d) that are listed in public
IP blacklists; the number of IPs in BGP (A(d)) that arelisted in IP blacklists; and the number of IPs in AS(A(d))
that are listed in IP blacklists.

• String features. This group consists of twelve features.
We measure the number of distinct domain names in
RHDNs, and the average and standard deviation of theirlength; the mean, median, and standard deviation of theoccurrence frequency of each single character in the domain name strings in RHDNs; the mean, median andstandard deviation of the distribution of 2-grams (i.e.,pairs of characters); the mean, median and standard deviation of the distribution of 3-grams.

Notos uses the blacklist features from the evidence vector
so it can identify the re-use of known malicious network resources like IPs, BGP prefixes or even ASs. Domain names
are significantly cheaper than IPv4 addresses; so malicious
users tend to reuse address space with new domain names. We
should note that the evidence-based features represent only
part of the information we used to compute the reputation
scores. The fact that a domain name was queried by malware
does not automatically mean that the domain will receive a
low reputation score.

• TLD features. This group consists of five features. For
each domain di in the RHDNs set, we extract its top-leveldomain T LD(di ) and we count the number of distinct
TLD strings that we obtain; we measure the ratio between
the number of domains di whose T LD(di )=“.com” andthe total number of TLD different from “.com”; also, wemeasure the mean, median, and standard deviation of theoccurrence frequency of the TLD strings.
It is worth noting that whenever we measure the mean, median and standard deviation of a certain property, we do so inorder to summarize the shape of its distribution. For example, by measuring the mean, median, and standard deviationof the occurrence frequency of each character in a set of domain name strings, we summarize how the distribution of thecharacter frequency looks like.

3.3

Reputation Engine

Notos’ reputation engine is responsible for deciding
whether a domain name d has characteristics that are similar to either legitimate or malicious domain names. In orderto achieve this goal, we first need to train the engine to recognize whether d belongs (or is “close”) to a known class of
domains. This training can be repeated periodically, in an offline fashion, using historical information collected in Notos’
knowledge base (see Section 4). Once the engine has been
trained, it can be used in on-line mode to assign a reputation
score to each new domain name d.
In this section, we first explain how the reputation engine
is trained, and then we explain how a trained engine is used toassign reputation scores.

3.2.3 Evidence-based Features
We use the evidence-based features to determine to what extent a given domain d is associated with other known malicious domain names or IP addresses. As mentioned above,
Notos collects a knowledge base of known suspicious, malicious, and legitimate domain names and IPs from public
sources. For example, we collect malware-related domainnames by executing large numbers of malware samples in acontrolled environment. Also, we check IP addresses against
a number of public IP blacklists. We elaborate on how webuild Notos’ knowledge base in Section 4. Given a domainname d, we measure six statistical features using the information in the knowledge base. We divide these features into twogroups:• Honeypot features. We measure three features, namely
the number of distinct malware samples that, when executed, try to contact d or any IP address in A(d); thenumber of malware samples that contact any IP address
in BGP (A(d)); and the number of samples that contact
any IP address in AS(A(d)).

3.3.1

Off-Line Training Mode

During off-line training (Figure 3), the reputation engine
builds three different modules. We briefly introduce each
module and then elaborate on the details.
• Network Profiles Model: a model of how well known
networks behave. For example, we model the network
characteristics of popular content delivery networks (e.g.,
Akamai, Amazon CloudFront), and large popular websites (e.g., google.com, yahoo.com). During the on-line
mode, we compare each new domain name d to thesemodels of well-known network profiles, and use this information to compute the final reputation score, as explained below.
• Domain Name Clusters: we group domain names into
clusters sharing similar characteristics. We create theseclusters of domains to identify groups of domains that
contain mostly malicious domains, and groups that contain mostly legitimate domains. In the on-line mode,given a new domain d, if d (more precisely, d’s projection into a statistical feature space) falls within (or closeto) a cluster of domains containing mostly malicious domains, for example, this gives us a hint that d should be
assigned a low reputation score.
• Reputation Function: for each domain name di , i = 1..n,in Notos’ knowledge base, we test it against the trained
network profiles model and domain name clusters. Let
N M (di ) and DC(di ) be the output of the Network Profiles (NP) module and the Domain Clusters (DC) module, respectively. The reputation function takes in input
N M (di ), DC(di ), and information about whether di andits resolved IPs A(di ) are known to be legitimate, suspicious, or malicious (i.e., if they appeared in a domainname or IP blacklist), and builds a model that can assign
a reputation score between zero and one to d. A reputation score close to zero signifies that d is a malicious
domain name while a score close to one signifies that d
is benign.
We now describe each module in detail.
3.3.2 Modeling Network Profiles
During the off-line training mode, the reputation engine builds
a model of well-known network behaviors. An overview of the
network profile modeling module can be seen in Figure 4(a).
In practice we select five sets of domain names that share similar characteristics, and learn their network profiles. For example, we identify a set of domain names related to very popular
websites (e.g., google.com, yahoo.com, amazon.com) and foreach of the related domain names we extract their network features, as explained in Section 3.2.1. We then use the extracted
feature vectors to train a statistical classifier that will be able
to recognize whether a new domain name d has network characteristics similar to the popular websites we modeled.
In our current implementation of Notos we model the following classes of domain names:• Popular Domains. This class consists of a large
set of domain names under the following DNS
zones: google.com, yahoo.com, amazon.com, ebay.com,
msn.com, live.com, myspace.com, and facebook.com.
• Common Domains. This class of domains includes domain names under the top one hundred zones, according to alexa.com. We exclude from this group all the
domain names already included in the Popular Domains
class (which we model separately).
• Akamai Domains. Akamai is a large content delivery network (CDN), and the domain names related tothis CDN have very peculiar network characteristics. To
model the network profile of Akamai’s domain names,
we collect a set of domains under the following zones:

akafms.net, akamai.net, akamaiedge.net, akamai.com,
akadns.net, and akamai.com.
• CDN Domains. In this class we include domainnames related to CDNs other than Akamai. For example, we collect domain names under the following zones: panthercdn.com, llnwd.net, cloudfront.net,
nyud.net, nyucd.net and redcondor.net. We chose notto aggregate these CDN domains and Akamai’s domains
in one class, since we observed that Akamai’s domains
have a very unique network profile, as we discuss in Section 4. Therefore, learning two separate models for theclasses of Akamai Domains and CDN Domains allows
use to achieve better classification accuracy during theon-line mode, compared to learning only one model forboth classes (see Section 3.3.5).
• Dynamic DNS Domains. This class includes a large setof domain names registered under two of the largest dynamic DNS providers, namely No-IP (no-ip.com) and
DynDNS (dyndns.com).
For each class of domains, we train a statistical classifier
to distinguish between one of the classes and all the others.
Therefore, we train five different classifiers. For example,
we train a classifier that can distinguish between the class ofPopular Domains and all other classes of domains. That is,given a new domain name d, this classifier is able to recognize whether d’s network profile looks like the profile of awell-known popular domain or not. Following the same logic
we, can recognize network profiles for the other classes of domains.
3.3.3

Building Domain Name Clusters

In this phase, the reputation engine takes the domain names
collected in our pDNS database during a training period, andbuilds clusters of domains that share similar network and zone
based features. The overview of this module can be seenin Figure 4(b). We perform clustering in two steps. In thefirst step we only use the network-based features to createcoarse-grained clusters. Then, in the second step, we split
each coarse-grained cluster into finer clusters using only thezone-based features, as shown in Figure 5.
Network-based Clustering The objective of network-based
clustering is to group domains that share similar levels ofagility. This creates separate clusters of domains with “stable” network characteristics and “non-stable” networks (likeCDNs and malicious flux networks).
Zone-based Clustering After clustering the domain names
according to their network-based features, we further split the
network-based clusters of domain names into finer groups.
In this step, we group domain names that are in the same

Domain Name (d)Evidence
Features

Zone
Features

Domain Clustering
Module

F1

...

F6

EV(d)

F1

...

F5

Network
Features

Network Profiling
Module

F1

...

F5

NM(d)

DC(d)
u(d)

Reputation Function
F1

Reputation Engine

Figure 5. Network & zone based clustering process in Notos, in the case of a Akamai [A] and amalicious [B] domain name.

network-based cluster and also share similar zone-based
features. To better understand how the zone-based clustering
works, consider the following examples of zone-based clusters:
Cluster 1:..., 72.247.176.81 e55.g.akamaiedge.net, 72.247.176.94 e68.g.akamaiedge.net, 72.247.176.146
e120.g.akamaiedge.net, 72.247.176.65 e39.na.akamaiedge.net, 72.247.176.242
e216.g.akamaiedge.net, 72.247.176.33 e7.g.akamaiedge.net, 72.247.176.156
e130.g.akamaiedge.net, 72.247.176.208 e182.g.akamaiedge.net, 72.247.176.198
e172.g.akamaiedge.net, 72.247.176.217 e191.g.akamaiedge.net, 72.247.176.200
e174.g.akamaiedge.net, 72.247.176.99 e73.g.akamaiedge.net, 72.247.176.103
e77.g.akamaiedge.net, 72.247.176.59 e33.c.akamaiedge.net, 72.247.176.68
e42.gb.akamaiedge.net, 72.247.176.237 e211.g.akamaiedge.net, 72.247.176.71
e45.g.akamaiedge.net, 72.247.176.239 e213.na.akamaiedge.net, 72.247.176.120
e94.g.akamaiedge.net, ...

Cluster 2:..., 90.156.145.198 spzr.in, 90.156.145.198 vwui.in, 90.156.145.198 x9e.ru, 90.156.145.50v2802.vps.masterhost.ru, 90.156.145.167 www.inshaker.ru, 90.156.145.198 x7l.ru,
90.156.145.198 c3q.at, 90.156.145.198 ltkq.in, 90.156.145.198 x7d.ru,
90.156.145.198 zdlz.in, 90.156.145.159 www.designcollector.ru, 90.156.145.198
x7o.ru, 90.156.145.198 q5c.ru, 90.156.145.159 designtwitters.com, 90.156.145.198
u5d.ru, 90.156.145.198 x9d.ru, 90.156.145.198 xb8.ru, 90.156.145.198 xg8.ru,
90.156.145.198 x8m.ru, 90.156.145.198 shopfilmworld.cn, 90.156.145.198
bigappletopworld.cn, 90.156.145.198 uppd.in, ...

Each element of the cluster is a domain name - IP address pair. These two groups of domains belonged to thesame network cluster, but were separated into two different
clusters by the zone-based clustering phase. Cluster 1 contains domain names belonging to Akamai’s CDN, while thedomains in Cluster 2 are all related to malicious websites that
distribute malicious software. The two clusters of domains
share similar network characteristics, but have significantly
different zone-based features. For example, consider domainnames d1 =“e55.g.akamaiedge.net” from the first cluster, andd2 =“spzr.in” from the second cluster. The reason why d1 andd2 were clustered in the same network-based cluster is because
the set of RHIPs (see Section 3.1) for d1 and d2 have similar
characteristics. In particular, the network agility properties ofd2 make it look like if it was part of a large CDN. However,

...

F16

f(d)

S

Figure 6. The output from the network profiling
module, the domain clustering module and the evidence vector will assist the reputation function toassign the reputation score to the domain d.

when we consider the set of RHDNs for d1 and d2 , we cannotice that the zone-based features of d1 are much more “stable” than the zone-based features of d2 . In other words, while
the RHDNs of d1 share strong domain name similarities (e.g.,they all share the substring “akamai”) and have low variance ofthe string features (see Section 3.2.2), the strong zone agility
properties of d2 affect the zone-based features measured on
d2 ’s RHDNs and make d2 look very different from d1 .
One of the main advantages of Notos is the reliable assignment of low reputation scores to domain names participating in “agile” malicious campaigns. Less agile malicious
campaigns, e.g., Fake AVs campaigns may use domain names
structured to resemble CDN related domains. Such strategies would not be beneficial for the FakeAV campaign, sincedomains like virus-scan1.com, virus-scan2.com,
etc., can be trivially blocked by using simple regular expressions [16]. In other words, the attackers need to introduce
more “agility” at both the network and domain name level inorder to avoid simple domain name blacklisting. Notos would
only require a few labeled domain names belonging to the malicious campaign for training purposes, and the reputation engine would then generalize to assign a low reputation score to
the remaining (previously unknown) domain names that belong to the same malicious campaign.
3.3.4

Building the Reputation Function

Once we build a model of well-known network profiles (seeSection 3.3.2) and the domain clusters (see Section 3.3.3), we
can build the reputation function. The reputation function willassign a reputation score in the interval [0, 1] to domain names,with 0 meaning low reputation (i.e., likely malicious) and 1
meaning high reputation (i.e., likely legitimate). We implement our reputation function as a statistical classifier. In order
to train the reputation function, we consider all the domain

names di , i = 1, .., n in Notos’ knowledge base, and we feedeach domain di to the network profiles module and to the domain clusters module to compute two output vectors N M (di )and DC(di ), respectively. We explain the details of how
N M (di ) and DC(di ) are computed later in Section 3.3.5. For
now it sufficient to consider N M (di ) and DC(di ) as two feature vectors. For each di we also compute an evidence features vector EV (di ), as described in Section 3.2.3. Let v(di )be a feature vector that combines the N M (di ), DC(di ), andEV (di ) feature vectors. We train the reputation function using the labeled dataset L = {(v(di ), yi )}i=1..n , where yi = 0
if di is a known malicious domain name, otherwise yi = 1.

in Section 3.3.2, and Spam Domains, Flux Domains, and Malware Domains.
In order to compute the output vector DC(d), we computethe following five statistical features: the majority class label
L (e.g., L may be equal to Malware Domain), i.e., the labelthat appears the most among the vectors vi ∈ Vd ; the standard deviation of label frequencies, i.e., given the occurrence
frequency of each label among the vectors vi ∈ Vd we com(L)pute their standard deviation; given the subset Vd ⊆ Vd ofvectors in Vd that are associated with label L, we computethe mean, median and standard deviation of the distribution(L)of distances between zd and the vectors vj ∈ Vd .

3.3.5 On-Line Mode

3.3.6

After training is complete; the reputation engine can be usedin on-line mode (Figure 3) to assign a reputation score to new
domain names. For example, given an input domain named, the reputation engine computes a score S ∈ [0, 1]. Values of S close to zero mean that d appears to be related tomalicious activities and therefore has a low reputation. On
the other hand, values of S close to one signify that d appears to be associated with benign Internet services, and therefore has a high reputation. The reputation score is computed
as follows. First, d is fed into the network profiles module,
which consists of five statistical classifiers, as discussed in
Section 3.3.2. The output of the network profiles module isa vector N M (d) = {c1 , c2 , ..., c5 }, where c1 is the output of
the first classifier, and can be viewed as the probability thatd belongs to the class of Popular Domains, c2 is the probability that d belongs to the class of Common Domains, etc.
At the same time, d is fed into the domain clusters module,
which computes a vector DC(d) = {l1 , l2 , ..., l5 }. The elements li of this vector are computed as follows. Given d, we
first extract its network-based features and identify the closest
network-based cluster to d, among the network-based clusters
computed by the domain clusters module during the off-line
mode (see Section 3.3.3). Then, we extract the zone-based
statistical features and identify the zone-based cluster closest
to d. Let this closest domain cluster be Cd . At this point, weconsider all the zone-based feature vectors vj ∈ Cd , and weselect the subset of vectors Vd ⊆ Cd for which the two following conditions are verified: i) dist(zd , vj ) < R, where zd
is the zone-based feature vector for d, and R is a predefined
radius; ii) vj ∈ KN N (zd ), where KN N (zd ) is the set of knearest-neighbors of zd .
The feature vectors in Vd are related to domain names extracted from Notos’ knowledge base. Therefore, we can assign
a label to each vector vi ∈ Vd , according to the nature of thedomain name d from which vi was computed. The domains in
Notos’ knowledge base belong to different classes. In particular, we distinguish between eight different classes of domains,
namely Popular Domains, Common Domains, Akamai, CDN,
and Dynamic DNS, which have the same meaning as explained

Given a domain d, once we compute the vectors N M (d) andDC(di ) as explained above, we also compute the evidence
vector EV (d) as explained in Section 3.2.3. At this point, weconcatenate these three feature vectors into a sixteen dimensional feature vector v(d), and we feed v(d) in input to ourtrained reputation function (see Section 3.3.4). The reputation function computes a score S = 1 − f (d), where f (d) canbe interpreted as the probability that d is a malicious domainname. S varies in the [0, 1] interval, and the lower the value ofS, the lower d’s reputation.

Assigning Reputation Scores

4 Data Collection and Analysis
This section summarizes observations from passive DNS
measurements, and how professional, legitimate DNS services
are distinguished from malicious services. These observations
provided the ground truth for our dynamic domain name reputation system. We also provide an intuitive example to illustrate these properties, using a few major Internet zones like
Akamai and Google.

4.1

Data Collection

The basic building block for our dynamic reputation rating
system is the historical or “passive” information from successful A-type DNS resolutions. We use the DNS traffic fromtwo ISP-based sensors, one located on the US east coast (Atlanta) and one located on the US west coast (San Jose). Additionally we use the aggregated DNS traffic from the different
networks covered by the SIE [3]. In total, our database collected 27,377,461 unique resolutions from all these sources
over a period of 68 days, from 19th of July 2009 to 24th
September 2009.
Simple measurements performed on this large data set
demonstrate a few important properties leveraged by our selected features. After just a few days the rate of new, uniquepDNS entries leveled off. The graph in Figure 7(b) shows
only about 100,000 to 150,000 new domains/day (with a brief
outage issue on the 53rd day), despite very large numbers of

(d) CDN Class GrowthOver Time (Days)

20

30
40
Days

50

60

70

(b) New RRs Growth In pDNS DB For All Zones

1000
Volume

10

10000

1000

Unique RRs
0Volume Of
New RRs(c) Akamai Class GrowthOver Time (Days)
10000

VolumeVolume Of
Unique RRs(a) Unique RRs In The Two ISPs Sensors (per day)
4e+06
3.5e+06
3e+06
2.5e+06
2e+06
1.5e+06
1e+06
500000
0

100

100
10

1e+07
1e+06
100000
10000
1000
100
10

1

0

10

20

30

40

50

60

70

Days
(e) Pop Class GrowthOver Time (Days)(f) Dyn. DNS Class GrowthOver Time (Days)

10000010110Unique DN
Unique IPs
New RRs

New RRs

100(g) Common Class GrowthOver Time (Days)

1000

100

1
10
Unique DNs
Unique IP
New RRs

100(h) CDF Of RR Growth
For All Classes
100000
10000

10000

1000

VolumeVolumeVolume

100
1000
10
100

10
100

10

10

1
1
10
Unique DN
Unique IP
New RRs

100

1

1
10
Unique DN
Unique IP
New RRs

100

1

10Unique DN
Unique IPs
New RRs

100

1
0.01
AkamaiCommon
Pop

0.1

1

CDN
Dynamic

Figure 7. Various RRs growth trends observed in the pDNS DB over a period of 68 days
RRs arriving each day (shown in Figure 7(a)). This suggeststhat most RRs are duplicates, and approximately after the firstfew days, 94.7% – on average – from the unique RRs observed in daily base at the sensor level are already recorded by
the passive DNS database. Therefore, even a relatively small
pDNS database may be used to deploy Notos. In Section 5, we
measure the sensitivity of our system to traffic collected fromsmaller networks.
The remaining plots in Figure 7 show the daily growth of
our passive DNS database, from the point of view of five different zone classes. Figure 7(c) and (d) show the growth rate
associated with CDN networks (Akamai, and all other CDNs).
The number of unique IPs stays nearly constant with the number of unique domains (meaning that each new RR is a new
IP and a new child domain of the CDN). In a few weeks, mostof the IPs became known—suggesting that one can fully map
CDNs in a modest training set. This is because CDNs, although large, always have a fixed number of IP addresses used
for hosting their high-availability services. Intuitively, we believe this would not be the case with malicious CDNs (e.g.,flux networks), which use randomly spreading infections tocontinually recruit new IPs.
The ratio of new IPs to domains diverges in Figure 7(e),a plot of the rate of newly discovered RRs for popular websites (e.g., Google, Facebook). Facebook notably uses uniquechild domains for their Web-based chat client, and other top
Internet sites use similar strategies (encoding information in

the domain, instead of the URI), which explains the growthin domains shown in Figure 7(e). These popular sites use avery small number of IPs, however, and after a few weeks oftraining our pDNS database identified all of them. Since these
popular domains make up a large portion of traffic in any trace,
our intuition is that simple whitelisting would significantly reduce the workload of a classifier.
Figure 7(f) shows the rate of pDNS growth for zones inDynamic DNS providers. These services, sometimes used bybotmasters, demonstrate a nearly matched ratio of new IPs to
new domains. The data excludes non-routable answers (e.g.,
dynamic DNS domains pointing to 127.0.0.1), since this contains no unique network information. Intuitively, one can thinkof dynamic DNS as a nearly complete bijection of domains to
IPs. Figure 7(g) shows the growth of RRs for alexa.com
top 100 domains. Unlike dynamic DNS domains, these points
to a small set of unique addresses, and most can be identified
in a few weeks’ worth of training.
A comparison of all the zone classes appears in Figure 7(h),which shows the cumulative distribution of the unique RRs detailed in Figure 7(c) through (g). The different rates of change
illustrate how each zone class has a distinct pattern of RR use:some have a small IP space and highly variable domain names;
some pair nearly every new domain with a new IP. Learning
approximately 90% of all the unique RRs in each zone class,however, only requires (at most) tens of thousands of distinct
RRs. The intuition from this plot is that, despite the very large

data set we used in our study, Notos could potentially workwith data observed from much smaller networks.

4.2 Building The Ground Truth
To establish ground truth, we use two different labelingprocesses. First, we assigned labels to RRs at the time of theirdiscovery. This provided an initial static label for many domains. Blacklists, of course, are never complete and always
dynamic. So our second labeling process took place during
evaluation, and monitored several well-known domain blacklists and whitelists.
The data we used for labeling came from several sources.
Our primary source of blacklisting came from services
such as malwaredomainlist.com and malwaredomains.com. In order to label IP addresses in our pDNS
database we also used the Sender Policy Block (SBL) list from
Spamhaus [18]. Such IPs are either known to send spam or
distribute malware. We also collected domain name and IP
blacklisting information from the Zeus tracker [30]. All thisblacklisting information was gathered before the first day ofAugust 2009 (during all the 15 days in which we collectedpassive DNS data). Since blacklists traditionally lag behind
the active threat, we continued to collect all new data until theend of our experiments.
Our limited whitelisting was derived from the top 500alexa.com domain names, as of the 1st of August 2009. We
reasoned that, although some malicious domains become popular, they do not stay popular (because of remediation), andnever break into the top tier of domain rankings. Likewise, weused a list of the 18 most common 2LDs from various CDNs,
which composed the main corpus of our CDN labeled RRs.
Finally a list of 464 dynamic DNS second level domains allowed us to identify and label domain name and IPs comingfrom zones under dynamic DNS providers. We label our evaluation (or testing) data-set by aggregating updated blacklist
information for new malicious domain names and IPs fromthe same lists.
To compute the honeypot features (presented in Section 3.2.3) we need a malware analysis infrastructure that canprocess as many “new” malware samples as possible. Our
honeypot infrastructure is similar to “Ether” [4] and is capable of processing malware samples in a queue. Every malware
sample was analyzed in a controlled environment for a time
period of five minutes. This process was repeated during thelast 15 days of July 2009. After 15 days of executions weobtained a set of successful DNS resolutions (domain names
and IPs) that each malware looked up. We chose to executemalware and collect DNS evidence through the same periodof time in which we aggregate the passive DNS database. Our
virtual machines are equipped with five popular commercial
anti-virus engines. If one of the engines identifies an executable as malicious, we capture all domain names and thecorresponding IP mappings that the malware used during ex-

ecution. After excluding all domain names that belong to the
top 500 most popular alexa.com zones, we assemble themain corpus of our “honeypot data”. We automated the crawling and collection of black list information and honeypot execution.
The reader should note that we chose to label our data inas transparent way as possible. We used public blacklisting
information to label our training dataset before we build ourmodels and train the reputation function. Then we assigned
the reputation scores and validated the results again using thesame publicly available blacklist sources. It is safe to assume that private IP and DNS blacklist will contain significant
more complete information with lower FP rates than the public
blacklists. By using such type of private blacklist the accuracyof Notos’ reputation function should improve significantly.

5 Results
In this section, we present the experimental results of ourevaluation. We show that Notos can identify malicious domainnames sooner than public blacklists, with a low false positive rate (FP%) of 0.38% and high true positive rate (TP%)
of 96.8%. As a first step, we computed vectors based on
the statistical features (described in Section 3.2) from 250,000
unique RRs. This volume corresponds to the average volumeof new – previously unseen – RRs observed at two recursive
DNS servers in a major ISP in one day, as noted in Section 4,
Figure 7(b). These vectors were computed based on historicpassive DNS information from the last two weeks of DNS traffic observed on the same two ISP recursive resolvers in Atlanta
and San Jose.

5.1

Accuracy of Network Profile Modeling

The accuracy of the Meta-Classification system (Figure 4(a)) in the network profile module is critical for the overall performance of Notos. This is because, in the on-line mode,
Notos will receive unlabeled vectors which must be classified
and correlated with what is already present in our knowledge
base. For example, if the classifier receives a new RR and assigns to it the label Akamai with very high confidence, that
implies the RR which produced this vector will be part of a
network similar to Akamai. However, this does not necessarily mean that it is part of the actual Akamai CDN. We will seein the next section how we can draw conclusions based on theproximity between labeled and unlabeled RRs within the samezone-based clusters. Furthermore, we discuss the accuracyof the Meta-Classifier when modeling each different network
profile class (profile classes are described in Section 3.3.2).
Our Meta-Classifier consists of five different classifiers,
one for each different class of domains we model. We chose touse a Meta-Classification system instead of a traditional single classification approach because Meta-Classification systems typically perform better than a single statistical classi-

False Positive Rate vs True Positive Rate
1

0.99

0.99

0.98

0.98

0.96
0.95
0.94
0.93
0.92
0.91
0.9
0

0.05

True Positive Rate

TP over All Pos. vs Threshold
1
0.98
0.96
0.94
0.92
0.9
0.88
0.86
0.84
0.82
0.8

0 0.10.20.30.40.50.60.70.80.9 Akamai
CDNs
ThresholdPopularCommonDynamic
0.1
False Positive Rate

0.15

0.97

TP over All Pos. vs Threshold

0.96
Precision

0.97

Precision

True Positive Rate

False Positive Rate vs True Positive Rate
1

0.95
0.94
0.93

1
0.98
0.96
0.94
0.92
0.9
0.88
0.86
0.84
0.82
0.8

ROC
0 0.10.20.30.40.50.60.70.80.9 1
Threshold

0.92
0.91

ROC

0.9
0.2

Figure 8. ROC curves for all network profileclasses shows the Meta-Classifier’s accuracy.

fier [11, 2]. Throughout our experiments this proved to bealso true. The ROC curve in Figure 8, shows that the MetaClassifier can accurately classify RRs for all different network
profile classes.
The training dataset for the Meta-Classifier is composedof sets of 2,000 vectors from each of the five network profileclasses. The evaluation dataset is composed of 10,000 vectors,
2,000 from each of the five network profile classes. The classification results for the domains in the Akamai, CDN, dynamic
DNS and Popular classes showed that the supervised learning process in Notos is accurate, with the exception of a small
number of false positives related to the Common class (3.8%).
After manually analyzing these false positives, we concluded
that some level of confusion between the vectors produced by
Dynamic DNS domain names and the vectors produced bydomain names in the Common class still remains. However,this minor misclassification between network profiles does not
significantly affect the reputation function. This is because
the zone profiles of the Common and Dynamic DNS domainnames are significantly different. This difference in the zone
profiles will drive the network-based and zone-based clustering steps to group the RRs from Dynamic DNS class and Common class in different zone-based clusters.
Despite the fact that the network profile modeling processprovides accurate results, it doesn’t mean this step can independently designate a domain as benign or malicious. The
clustering steps will assist Notos to group vectors not only
based their network profiles but also based on their zone properties. In the following section we show how the network andzone profile clustering modules can better associate similar
vectors, due to properties of their domain name structure.

0

0.02

0.04
0.06
False Positive Rate

0.08

0.1

Figure 9. The ROC curve from the reputation function indicating the high accuracy of Notos.

5.2

Network and Zone-Based Clustering Results

In the domain name clustering process (Section 3.3.3, Figure 4(b)) we used X-Means clustering in series, once for the
network-based clustering and again for the zone-based clustering. In both steps we set the minimum and maximum number of clusters to one and the total number of vectors in ourdataset, respectively. We run these two steps using different
numbers of zone and network vectors. Figure 11 shows thatafter the first 100,000 vectors are used, the number of networkand zone clusters remains fairly stable. This means that bycomputing at least 100,000 network and zone vectors—using
a 15-day old passive DNS database—we can obtain a stable
population of zone and network based clusters for the monitored network. We should note that reaching this network andcluster equilibrium does not imply that we do not expect tosee any new type of domain names in the ISP’s DNS recursive. This just denotes that based on the RRs present in our
passive DNS database, and the daily traffic at the ISP’s recursive, 100,000 vectors are enough to reflect the major network
profile trends in the monitored networks. Figure 11 indicatesthat a sample set of 100,000 vectors may represent the major
trends in a DNS sensor. It is hard to safely estimate the exact
minimum number of unique RRs that is sufficient to identify
all major DNS trends. An answer to this should be based upon
the type, size and utilization of the monitored network. Without data from smaller corporate networks it is difficult for us
to make a safe assessment about the minimum number of RR
necessary for reliably training Notos.
The evaluation dataset we used consisted of 250,000 uniquedomain names and IPs. The cluster overview is shown in Figure 10 and in the following paragraphs we discuss some in-1st Level (Network Based) Clusters
2nd Level (Zone Based) Clusters
100

Number of Clusters Produced

90
80
70
60
50
40
30
20
10
0
0

50000

100000150000
Number of Vectors Used

200000250000Figure 10. With the 2-step clustering step, Notos
is able to cluster large trends of DNS behavior.

Figure 11. By using different number of networkand zone vectors we observe that after the first
100,000, there is no significant variation in the absolute number of produced clusters during the 1st
and 2nd level clustering steps.

teresting observations that can be made from these networkbased and zone-based cluster assignments. As an example,
network clusters 0 and 1 are predominantly composed of zones
participating in fraudulent activities like spam campaigns (yellow) and malware dropping or C&C zones (red). On the other
hand, network clusters 2 to 5 contain Akamai, dynamic DNS,
and popular zones like Google, all labeled as benign (green).
We included the unlabeled vectors (blue) based on which weevaluated the accuracy of our reputation function. We have asample of unlabeled vectors in almost all network and zone
clusters. We will see how already labeled vectors will assist
us to characterize the unlabeled vectors in close proximity.
Before we describe two sample cases of dynamic characterization within zone-based clusters, we need to discuss our
radius R and k value selection (see Section 3.3.5). In Section 3.3.5, we discuss how we build domain name clusters.
At that point we introduced the dynamic characterization process that gives Notos the ability to utilize already label vectors
in order to characterize a newly obtained unlabeled vector byleveraging our prior knowledge. After looking into the distribution of Euclidean distances between unlabeled and labeled
vectors within the same zone clusters, we concluded that in the
majority of these cases the distances were between 0 and 1000.
We tested different values of the radius R and the value of kfor the K-nearest neighbors (KNN) algorithm. We observedthat the experiments with radius values between 50 and 200
provided the most accurate reputation rating results, which we
describe in the following sections. We also observed that if
k > 25 the accuracy of the reputation function is not affected
for all radius values between 50 and 200. Based on the resultsof these pilot experiments, we decided to set k equal to 50 andthe radius distance equal to 100.
Figures 12 and 13 show the effect of this radius selection
on two different types of clustering problems. In Figure 12,
unknown RRs for akamaitech.net are clustered with alabeled vector akamai.net. As noted in Section 4, CDNs
such as Akamai tended to have new domain names with each
RR, but to also reuse their IPs. By training with only a small
set of labeled akamai.net RRs, our classifier put the new,
unknown RRs for akamaitech.net into the existing Akamai class. IP-specific features therefore brought the new RRs
close to the existing labeled class. Figure 12 compresses allof the dimensions into a two-dimensional plot (for easier visual representation), but it is clear the unknown RRs were allwithin a distance of 100 to the labeled set.
This result validates the design used in Section 4, where
just a few weeks’ worth of labeled data was necessary fortraining. Thus, one does not have to exhaustively discover all
whitelisted domains. Notos is resilient to changes in the zoneclasses we selected. Services like CDNs and major web sites
can add new IPs or adjust domain formats, and these will be
automatically associated with a known labeled class.
The ability of Notos to associate new RRs based on limited labeled inputs is demonstrated again in Figure 13. In
this case, labeled Zeus domains (approximately 2,900 RRs
from three different Zeus-related BLs) were used to classify new RRs. Figure 13 plots the distance between the labeled Zeus-related RRs and new (previously unknown) RRs
that are also related Zeus botnets. As we can see from
Section 4, most of the new (unlabeled) Zeus RRs lay very

Clustering akamai.net and akamaitech.net Vectors

Clustering The Zeus Botnet
200

400
CMD 2D Scale (1)CMD Scale (1)

0
200
0
-200

-200
-400
-600
-800

-400
-400

-200

0

akamai.net

200
400
CMD Scale (2)

600

800

1000

akamaitech.net-1000-4000 -3000 -2000 -1000
01000 2000 3000 4000
CMD 2D Scale (2)Labeled Zeus

Unlabeled Zeus

Figure 12. An example of characterizing the akamaitech.net unknown vectors as benign based on
the already labeled vectors (akamai.net) present
in the same cluster.

Figure 13. An example of how the Zeus botnet
clusters during our experiments. All vectors arein the same network cluster and in two different
zone clusters.

close, and often even overlap, to known Zeus RRs. Thisis a good result, because Zeus botnets are notoriously hardto track, given the botnet’s extreme agility. Tracking systems such as zeustracker.abuse.ch and malwaredomainlist.com have limited visibility into the botnet,
and often produce disjoint blacklists. Notos addresses thisproblem, by leveraging a limited amount of training data tocorrectly classify new RRs. During our evaluation set, Notos
correctly detected 685 new (previously unknown) Zeus RRs.

names. We experimented with bot the top 10,000 and top
100,000 Alexa domain names. The detection results for theseexperiments are as follows. When using the top 10,000 Alexa
domains, we obtained a true positive rate of 93.6% and a false
positive rate of 0.4% (again using 10-fold cross-validation anda detection threshold equal to 0.5). As we can see, these results
are not very different from the ones we obtained using only
the top 500 Alexa domains. However, when we extended ourlist of known good domains to include the top 100,000 Alexa
domain names, we observed a significant decrease of the true
positive rate and an increase in the false positives. Specifically,
we obtained a TP% of 80.6% and a FP% of 0.6%. We believe
this degradation in accuracy may be due to the fact that the
top 100,000 Alexa domains include not only professionallyrun domains and network infrastructures, but also include lessgood domain names, such as file-sharing, porn-related websites, etc., most of which are not run in a professional way andhave disputable reputation1 .
We also wanted to evaluate how well Notos performs, compared to static blacklists. To this end, we performed a numberof experiments as follows. Given an instance of Notos trainedwith data collected up to July 31, 2009, we fed Notos with
250,000 distinct RRs found in DNS traffic we collected on
August 1, 2009. We then computed the reputation score foreach of these RRs. First, we set the detection threshold to 0.5,
and with this threshold we identified 54,790 RRs that had alow reputation (lower than the threshold). These RRs where

5.3 Accuracy of the Reputation Function
The first thing that we address in this section is our decision to use a Decision Tree using Logit-Boost strategy (LAD)
as the reputation function. Our decision is motivated by thetime complexity, the detection results and the precision (truepositives over all positives) of the classifier. We compared
the LAD classifier to several other statistical classifiers usinga typical model selection procedure [6]. LAD was found toprovide the most accurate results in the shortest training time
for building the reputation function. As we can see from the
ROC curve in Figure 9, the LAD classifier exhibits a low false
positive rate (FP%) of 0.38% and true positive rate (TP%) of
96.8%. It is was noting that these results were obtained using
10-fold cross-validation, and the detection threshold was set
to 0.5. The dataset using for the evaluation contained 10,719
RRs related to 9,530 known bad domains. The list of known
good domains consisted of the top 500 most popular domains
according to Alexa.
We also benchmarked the reputation function on other two
datasets containing a larger number of known good domain

1 A quick analysis of the top 100,000 Alexa domains reported that about
5% of the domains appeared in the SURBL (www.surbl.org) blacklist, atcertain point in time. A more rigorous evaluation of these results is left to
future work.

Volume Of RRs(a) Overall Volume of Malicious RRs
10000(c)Malware/Trojans, Exploits andRogue AV RRs Identified
1000

1000

100

100

10

10

1
0

1
0

20
40
60
80
Days After Training

100

MalwareExploitVolume Of RRs(b) Flux and Spam RRs Identified
10000

20
40
60
80
Days After Training

100

Rogue AV(d) Botnet RRs Identified
100
10

1000

1
100

0
0

5

10 15 20 25 30 35
Days After Training

Flux

Spam

20

40
60
80
Days After Training

Zeus
Koobface

100

R.F.I
Various Bots

Figure 14. Dates in which various blacklists confirmed that the RRs were malicious after Notos
assigned low reputation to them on the 1st ofAugust.

related to a total of 10,294 distinct domain names (notice thata domain name may map to more than one IP, and this explains the higher number of RRs). Of these 10,294 domains,
7,984 (77.6%) appeared in at least one of the public blacklists we used for comparison (see Section 4) within 60 day
after August 1, and were therefore confirmed to be malicious.
Figure 14(a) reports the number and date in which RRs classified as having low reputation by Notos appeared in the public
blacklists. The remaining three plots (Figure 14(b), (c) and(d)), report the same results organized according to the type ofmalicious domains. In particular, it is worth noting that Notos
is able to detect never-before-seen domain names related to theZeus botnet several days or even weeks before they appearedin any of the public blacklists.
For the remaining 22.4% of the 10,294 domains we considered, we were not able to draw a definitive conclusion. However, we believe many of those domains are involved in somekind of more or less malicious activities. We also noticed
that 7,980 or the 7,984 confirmed bad domain names wereassigned a reputation score lower or equal to 0.15, and thatnone of the other non-confirmed suspicious domains received
a score lower than this threshold. In practice, this means thatan operator who would like to use Notos as a stand-alone dynamic blacklisting system while limiting the false positives toa negligible (or even zero) amount may fine-tune the detection
threshold and set it around 0.15.

5.4 Discussion
This section discusses the limits of Notos, and the potential for evasion in real networks. On of the main limitations
is the fact that Notos is unable to assign reputation scores fordomain names with very little historic (passive DNS) information. Sufficient time and a relatively large passive DNS collection are required to create an accurate passive DNS database.
Therefore, if an attacker always buys new domain names andnew address space, and never reuses either resource for any
other malicious purposes, Notos will not be able to accurately
assign a reputation score to the new domains. In the IPv4
space, this is very unlikely to happen due to the impending exhaustion of the available address space. Once IPv6 becomesthe predominant protocol, however, this may represent a problem for the statistical features we extract based on IP granularity. However, we believe the features based on BGP prefixes
and AS numbers would still be able to capture the agility typical of malicious DNS hosting behavior.
As long as newly generated domain names share some network properties (e.g., IPs or BGP prefixes) with already labeled RRs, Notos will be able to assign an accurate reputation score. In particular, since network resources are finite andmore expensive to renew or change, even if the domain properties change, Notos can still identify whether a domain namemay be associated with malicious behavior. In addition, if agiven domain name for which we want to know the reputation
is not present in the passive DNS DB, we can actively probe it,thus forcing a related passive DNS entry. However, this is possible only when the domain successfully maps to a non-empty
set of IPs.
Our experimental results using the top 10,000 Alexa domain names as known good domains, report a false positive
fate of 0.4%. While low in percentage, the absolute number offalse positives may become significant in those cases in whichvery large numbers of new domain names are fed to Notos ona daily bases (e.g., in case of deployment in a large ISP network). However, we envision our Notos reputation system tobe use not as a stand-alone system, but rather in cooperation
with other defense mechanisms. For example, Notos may be
used in collaboration with spam-filtering system. If an email
contains a link to a website whose domain name has a low reputation score according to Notos, the spam filter can increase
the total spam-score of the email. However, if the rest of theemail appears to be benign, the spam filter may still decide toaccept the email.
During our manual analysis of (a subset of) the false positives encountered in our evaluations we were able to draw
some interesting observation. We found that a number of legitimate sites (e.g., goldsgym.com) are being hosted in networks that host large volumes of malicious domain names inthem. In this cases Notos will tend to penalize the reputationof this legitimate domains because they reside in a bad neighborhood. In time, the reputation score assigned to these domains score may change, if the administrators of the networkin which the benign domain name are hosted take actions to“clean up” their networks and stop hosting bad domain names
within their address space.

Domain Name

google-bot004.cn
analf.net
pro-buh.ru
ammdamm.cn
briannazfunz.com
mybank-of.com
oc00co.com
avangadershem.com
securebizccenter.cn
adobe-updating-service.cn
0md.ruavrev.info
g00glee.cn

IP

Date

Domain Name

213.182.197.229

08-15
08-15
08-15
08-15
08-15
08-15
08-15
08-19
08-19
09-02
09-19
09-27
09-02

lzwn.in3b9.ruantivirprotect.com
1speed.info
spy-destroyer.com
free-spybot.com
a3l.atgidromash.cn
iantivirus-pro.com
ericwanhouse.cn
1165651291.com

222.186.31.169
89.108.67.83
92.241.162.55
95.205.116.55
59.125.229.73
212.117.165.128
195.88.190.29
122.70.145.140
59.125.231.252
219.152.120.118
98.126.15.186
218.93.202.100

Table 1. Sample cases form Zeus domains detected by Notos and the corresponding days
that appeared in the public BLs. All evidence
information in this table were harvested fromzeustracker.abuse.ch.

6 Conclusion
In this paper, we presented Notos, a dynamic reputation
system for DNS. To the best of our knowledge, Notos is thefirst system that can assign a dynamic reputation score to any
domain name in a DNS query that traverses the edge of amonitored network. Notos harvests information from multiple
sources such as the DNS zone domain names belongs to, therelated IP addresses, BGP prefixes, AS information and honeypot analysis to maintain up-to-date DNS information about
legitimate and malicious domain names. Based on this information, Notos uses automated classification and clustering algorithms to model network and zone behaviors of legitimate
and malicious domains, and then applies these models to compute a reputation score for a (new) domain name.
Our evaluation using real-world data, which includes traffic from large ISP networks, demonstrates that Notos is highly
accurate in identifying new malicious domains in the monitored DNS query traffic, with a true positive rate of 96.8% andfalse positive rate of 0.38%. In addition, Notos is capable ofidentifying these malicious domain weeks or even months before they appear in public blacklists, thus enabling proactive
security countermeasures against cyber attacks.

7 Acknowledgments
We thank Steven Gribble, our shepherd, for helping us to
improve the quality of the final version of this paper, andthe anonymous reviewers for their constructive comments.
We also thank Gunter Ollmann and Robert Edmonds fortheir valuable comments. Additionally, we thank the Internet
Security Consortium Security Information Exchange project(ISC@SIE) for providing portion of the DNS data used in our
experiments.

IP

Type

Src

Date

94.23.198.97

MAL
MAL
RAV
CWS
CWS
RAV
MAL
BOT
KBF
EXP
RAV

[1]
[2]
[3]
[2]
[4]
[2]
[2]
[2]
[5]
[6]
[2]

08-26
08-30
09-05
09-05
09-05
09-05
09-09
09-13
09-19
09-22
10-06

213.251.176.169
64.40.103.249
212.117.163.165
67.211.161.44
63.243.188.110
89.171.115.10
211.95.79.170
188.40.52.180
220.196.59.19
212.117.165.126

Table 2. Anecdotal cases of malicious domainnames detected by Notos and the corresponding days that appeared in the public BLs .[1]:hosts-file.net, [2]: malwareurl.com, [3] siteadvisor.com, [4]virustotal.com, [5] ddanchev.blogspot.com, [6] malwaredomainlist.com

This material is based upon work supported in part by
the National Science Foundation under grant no. 0831300,
the Department of Homeland Security under contract no.
FA8750-08-2-0141, the Office of Naval Research under grants
no. N000140710907 and no. N000140911042. Any opinions,findings, and conclusions or recommendations expressed inthis material are those of the authors and do not necessarilyreflect the views of the National Science Foundation, the Department of Homeland Security, or the Office of Naval Research.

References[1] D. Anderson, C. Fleizach, S. Savage, and G. Voelker.
Spamscatter: Characterizing internet scam hosting infrastructure. In Proceedings of the USENIX Security
Symposium, 2007.
[2] L. Breiman. Bagging predictors. Machine learning,24(2):123–140, 1996.
[3] Internet Systems Consortium. SIE@ISC : Security Information Exchange. https://sie.isc.org/, 2004.
[4] A. Dinaburg, R. Royal, M. Sharif, and W. Lee. Ether:
malware analysis via hardware virtualization extensions.
In ACM CCS, 2008.
[5] SORBS DNSBL. Fighting spam by finding and listing Exploitable Servers. http://www.us.sorbs.
net/, 2007.
[6] R. Duda, P. Hart, and D. Stork. Pattern Classification.
Wiley-Interscience, 2nd edition, 2000.

[7] M. Felegyhazi, C. Keibich, and V. Paxson. On the potential of proactive domain blacklisting. In Third USENIXLEET Workshop, 2010.

[22] S. Shevchenko. Srizbi Domain Generator Calculator.
http://blog.threatexpert.com/2008/11/
srizbis-domain-calculator.html, 2008.

[8] S. Garera, N. Provos, M. Chew, and A. Rubin. A framework for detection and measurement of phishing attacks.
In Proceedings of the ACM WORM. ACM, 2007.

[23] K. Sato, K. Ishibashi, T. Toyono, and N. Miyake. Extending black domain name list by using co-occurrence
relation between dns queries. In Third USENIX LEET
Workshop, 2010.

[9] B. Gross, M. Cova, L. Cavallaro, B. Gilbert, M. Szydlowski, R. Kemmerer, C. Kruegel, and G. Vigna. Your
botnet is my botnet: analysis of a botnet takeover. In
ACM CCS 09, New York, NY, USA, 2009. ACM.
[10] T. Holz, C. Gorecki, K. Rieck, and F. Freiling. Measuring and detecting fast-flux service networks. In Proceedings of NDSS, 2008.
[11] T. Hothorn and B. Lausen. Double-bagging: Combiningclassifiers by bootstrap aggregation. Pattern Recognition, 36(6):1303–1309, 2003.

[24] S. Sinha, M. Bailey, and F. Jahanian. Shades of grey: On
the effectiveness of reputation-based blacklists. In 3rd
International Conference on MALWARE, 2008.
[25] The Honeynet Project & Research Alliance. Know Your
Enemy: Fast-Flux Service Networks. http://old.
honeynet.org/papers/ff/fast-flux.html,
2007.
[26] URIBL. Real time URI blacklist. http://uribl.
com.

[12] P. Mockapetris. Domain names - concepts and facilities. http://www.ietf.org/rfc/rfc1034.
txt, 1987.

[27] F. Weimer. Passive DNS replication. In Proceedings of
FIRST Conference on Computer Security Incident, Hand
ling, Singapore, 2005.

[13] P. Mockapetris.
Domain names - implementationand specification. http://www.ietf.org/rfc/
rfc1035.txt, 1987.

[28] Z. Qian, Z. Mao, Y. Xie and F. Yu. On networklevel clusters for spam detection. In Proceedings of the
USENIX NDSS Symposium, 2010.

[14] OPENDNS. OpenDNS — Internet Navigation And Security. http://www.opendns.com/, 2010.
[15] P. Porras, H. Saidi, and V. Yegneswaran. An Analysis
of Conficker’s Logic and Rendezvous Points. http://mtc.sri.com/Conficker/, 2009.
[16] R. Perdisci, W. Lee, and N. Feamster. Behavioral clustering of http-based malware and signature generation using
malicious network traces. In USENIX NSDI, 2010.
[17] D. Plonka and P. Barford. Context-aware clustering of
DNS query traffic. In Proceedings of the 8th IMC, Vouliagmeni, Greece, 2008. ACM.
[18] The Spamhaus Project. ZEN - Spamhaus DNSBLs.
http://www.spamhaus.org/zen/, 2004.
[19] R. Perdisci, I. Corona, D. Dagon, and W. Lee. Detecting
malicious flux service networks through passive analysis of recursive DNS traces. In Proceedings of ACSAC,
Honolulu, Hawaii, USA, 2009.
[20] P. Royal.
Analysis of the kraken botnet.
http://www.damballa.com/downloads/
r_pubs/KrakenWhitepaper.pdf, 2008.
[21] S. Hao, N. Syed, N. Feamster, A. Gray and S.
Krasser. Detecting spammers with SNARE: Spatiotemporal network-level automatic reputation engine. In
Proceedings of the USENIX Security Symposium, 2009.

[29] B. Zdrnja, N. Brownlee, and D. Wessels. Passive monitoring of DNS anomalies. In Proceedings of DIMVA
Conference, 2007.
[30] Zeus Tracker. Zeus IP & domain name block list.
https://zeustracker.abuse.ch, 2009.
[31] J. Zhang, P. Porra, and J. Ullrich. Highly predictive
blacklisting. In Proceedings of the USENIX Security
Symposium, 2008.