05-07-2012, 10:41 AM
Detecting Spam Zombies by Monitoring Outgoing Messages
Detecting Spam Zombies by.pdf (Size: 621.91 KB / Downloads: 70)
1 INTRODUCTION
Amajor security challenge on the Internet is the existence
of the large number of compromised machines. Such
machines have been increasingly used to launch various
security attacks including spamming and spreading malware,
DDoS, and identity theft [1], [10], [14]. Two natures of
the compromised machines on the Internet—sheer volume
and widespread—render many existing security countermeasures
less effective and defending attacks involving
compromised machines extremely hard. On the other hand,
identifying and cleaning compromised machines in a
network remain a significant challenge for system administrators
of networks of all sizes.
In this paper, we focus on the detection of the compromised
machines in a network that are used for sending spam
messages, which are commonly referred to as spam zombies.
Given that spamming provides a critical economic incentive
for the controllers of the compromised machines to recruit
these machines, it has been widely observed that many
compromised machines are involved in spamming [17], [19],
[25]. A number of recent research efforts have studied the
aggregate global characteristics of spamming botnets (networks
of compromised machines involved in spamming)
such as the size of botnets and the spamming patterns of
botnets, based on the sampled spam messages received at a
large e-mail service provider [25], [26].
Rather than the aggregate global characteristics of spamming
botnets, we aim to develop a tool for system
administrators to automatically detect the compromised
machines in their networks in an online manner.Weconsider
ourselves situated in a network and ask the following
question: How can we automatically identify the compromised
machines in the network as outgoing messages pass
the monitoring point sequentially? The approaches developed
in the previous work [25], [26] cannot be applied here.
The locally generated outgoing messages in a network
normally cannot provide the aggregate large-scale spam
view required by these approaches. Moreover, these approaches
cannot support the online detection requirement in
the environment we consider.
The nature of sequentially observing outgoing messages
gives rise to the sequential detection problem. In this paper,
we will develop a spam zombie detection system, named
SPOT, by monitoring outgoing messages. SPOT is designed
based on a statistical method called Sequential Probability
Ratio Test (SPRT), developed by Wald in his seminal work
[21]. SPRT is a powerful statistical method that can be used
to test between two hypotheses (in our case, a machine is
198 IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 9, NO. 2, MARCH/APRIL 2012
. Z. Duan and F. Sanchez are with the Department of Computer Science,
Florida State University, Tallahassee, FL 32306-4530.
E-mail: {duan, sanchez}[at]cs.fsu.edu.
. P. Chen is with Juniper Networks, Sunnyvale, CA 94089.
E-mail: g_chenpeng[at]hotmail.com.
. Y. Dong is with the Department of Electrical Engineering, University of
Hawaii, 2540 Dole Street, Holmes Hall 483, Honolulu, HI 96822.
E-mail: yingfei[at]hawaii.edu.
. M. Stephenson is with Information Technology Services, Florida State
University, 2035 E. Paul Dirac Drive, 200 BFS, Tallahassee, FL 32310.
E-mail: mstephenson[at]fsu.edu.
. J.M. Barker is with Information Technology Services, The University of
North Carolina at Chapel Hill, 211 Manning Drive, Chapel Hill, NC
27599-3420. E-mail: michael_barker[at]unc.edu.
Manuscript received 27 Aug. 2010; revised 9 May 2011; accepted 9 June 2011;
published online 30 Sept. 2011.
For information on obtaining reprints of this article, please send e-mail to:
tdsc[at]computer.org, and reference IEEECS Log Number TDSC-2010-08-0149.
Digital Object Identifier no. 10.1109/TDSC.2011.49.
1545-5971/12/$31.00 2012 IEEE Published by the IEEE Computer Society
compromised versus the machine is not compromised), as
the events (in our case, outgoing messages) occur sequentially.
As a simple and powerful statistical method, SPRT
has a number of desirable features. It minimizes the
expected number of observations required to reach a
decision among all the sequential and nonsequential
statistical tests with no greater error rates. This means that
the SPOT detection system can identify a compromised
machine quickly. Moreover, both the false positive and
false negative probabilities of SPRT can be bounded by
user-defined thresholds. Consequently, users of the SPOT
system can select the desired thresholds to control the
false positive and false negative rates of the system.
In this paper, we develop the SPOT detection system to
assist system administrators in automatically identifying
the compromised machines in their networks. We also
evaluate the performance of the SPOT system based on a
two-month e-mail trace collected in a large US campus
network. Our evaluation studies show that SPOT is an
effective and efficient system in automatically detecting
compromised machines in a network. For example, among
the 440 internal IP addresses observed in the e-mail trace,
SPOT identifies 132 of them as being associated with
compromised machines. Out of the 132 IP addresses
identified by SPOT, 126 can be either independently
confirmed (110) or are highly likely (16) to be compromised.
Moreover, only seven internal IP addresses associated with
compromised machines in the trace are missed by SPOT. In
addition, SPOT only needs a small number of observations
to detect a compromised machine. The majority of spam
zombies are detected with as little as three spam messages.
For comparison, we also design and study two other spam
zombie detection algorithms based on the number of spam
messages and the percentage of spam messages originated
or forwarded by internal machines, respectively. We
compare the performance of SPOT with the two other
detection algorithms to illustrate the advantages of the
SPOT system.
The remainder of the paper is organized as follows: in
Section 2, we discuss related work in the area of botnet
detection (focusing on spam zombie detection schemes). We
formulate the spam zombie detection problem in Section 3.
Section 4 provides the necessary background on SPRT for
developing the SPOT spam zombie detection system. In
Section 5, we provide the detailed design of SPOT and the
two other detection algorithms. Section 6 evaluates the
SPOT detection system based on the two-month e-mail
trace, and contrasts its performance with the two other
detection algorithms. We briefly discuss the practical
deployment issues and potential evasion techniques in
Section 7, and conclude the paper in Section 8.
2 RELATED WORK
In this section, we discuss related work in detecting
compromised machines. We first focus on the studies that
utilize spamming activities to detect bots and then briefly
discuss a number of efforts in detecting general botnets.
Based on e-mail messages received at a large e-mail
service provider, two recent studies [25], [26] investigated
the aggregate global characteristics of spamming botnets
including the size of botnets and the spamming patterns of
botnets. These studies provided important insights into the
aggregate global characteristics of spamming botnets by
clustering spam messages received at the provider into
spam campaigns using embedded URLs and near-duplicate
content clustering, respectively. However, their approaches
are better suited for large e-mail service providers to
understand the aggregate global characteristics of spamming
botnets instead of being deployed by individual
networks to detect internal compromised machines. Moreover,
their approaches cannot support the online detection
requirement in the network environment considered in this
paper. We aim to develop a tool to assist system administrators
in automatically detecting compromised machines in
their networks in an online manner.
Xie et al. developed an effective tool named DBSpam to
detect proxy-based spamming activities in a network
relying on the packet symmetry property of such activities
[23]. We intend to identify all types of compromised
machines involved in spamming, not only the spam proxies
that translate and forward upstream non-SMTP packets (for
example, HTTP) into SMTP commands to downstream mail
servers as in [23].
In the following, we discuss a few schemes on detecting
general botnets. BotHunter [8], developed by Gu et al.,
detects compromised machines by correlating the IDS
dialog trace in a network. It was developed based on the
observation that a complete malware infection process has a
number of well-defined stages including inbound scanning,
exploit usage, egg downloading, outbound bot coordination
dialog, and outbound attack propagation. By correlating
inbound intrusion alarms with outbound communications
patterns, BotHunter can detect the potential infected
machines in a network. Unlike BotHunter which relies on
the specifics of the malware infection process, SPOT focuses
on the economic incentive behind many compromised
machines and their involvement in spamming.
An anomaly-based detection system named BotSniffer [9]
identifies botnets by exploring the spatial-temporal behavioral
similarity commonly observed in botnets. It focuses
on IRC-based and HTTP-based botnets. In BotSniffer, flows
are classified into groups based on the common server that
they connect to. If the flows within a group exhibit
behavioral similarity, the corresponding hosts involved are
detected as being compromised. BotMiner [7] is one of the
first botnet detection systems that are both protocol and
structure independent. In BotMiner, flows are classified into
groups based on similar communication patterns and
similar malicious activity patterns, respectively. The intersection
of the two groups is considered to be compromised
machines. Compared to general botnet detection systems
such as BotHunter, BotSniffer, and BotMiner, SPOT is a
lightweight compromised machine detection scheme, by
exploring the economic incentives for attackers to recruit the
large number of compromised machines.
As a simple and powerful statistical method, Sequential
Probability Ratio Test has been successfully applied in many
areas [22]. In the area of networking security, SPRT has been
used to detect portscan activities [12], proxy-based spamming
activities [23], anomaly-based botnet detection [9], and
MAC protocol misbehavior in wireless networks [16].
DUAN ET AL.: DETECTING SPAM ZOMBIES BY MONITORING OUTGOING MESSAGES 199
3 PROBLEM FORMULATION AND ASSUMPTIONS
In this section, we formulate the spam zombie detection
problem in a network. In particular, we discuss the network
model and assumptions we make in the detection problem.
Fig. 1 illustrates the logical view of the network model.
We assume that messages originated from machines inside
the network will pass the deployed spam zombie detection
system. This assumption can be achieved in a few different
scenarios. For example, the outgoing e-mail traffic (with
destination port number of 25) can be replicated and
redirected to the spam zombie detection system.
A machine in the network is assumed to be either
compromised or normal (that is, not compromised). In this
paper, we only focus on the compromised machines that are
involved in spamming. Therefore, we use the term a
compromised machine to denote a spam zombie, and use the
two terms interchangeably. Let Xi for i ¼ 1; 2; . . . denote the
successive observations of a random variable X corresponding
to the sequence of messages originated from machine m
inside the network. We let Xi ¼ 1 if message i from the
machine is a spam, and Xi ¼ 0 otherwise. The detection
system assumes that the behavior of a compromised
machine is different from that of a normal machine in
terms of the messages they send. Specifically, a compromised
machine will with a higher probability generate a
spam message than a normal machine. Formally,
PrðXi ¼ 1jH1Þ > PrðXi ¼ 1jH0Þ; ð1Þ
where H1 denotes that machine m is compromised and H0
that the machine is normal. The spam zombie detection
problem can be formally stated as follows: as Xi arrives
sequentially at the detection system, the system determines
with a high probability if machine m has been compromised.
Once a decision is reached, the detection system
reports the result, and further actions can be taken, e.g., to
clean the machine.
We assume that a (content-based) spam filter is deployed
at the detection system so that an outgoing message can be
classified as either a spam or nonspam [20]. None of existing
spam filters can achieve perfect spam detection accuracy,
and they all suffer from both false positive and false negative
errors. The false negative rate of a spam filter measures
the percentage of spam messages that are misclassified, and
the false positive rate measures the percentage of nonspam
messages that are misclassified. We note that all widely
deployed spam filters have very low false negative and false
positive rates, and such small spam classification errors will
only have a marginal impact on the performance of the spam
zombie detection algorithms (see Section 6).
We also assume that a sending machine m as observed
by the spam zombie detection system is an end-user client
machine. It is not a mail relay server. This assumption is just
for the convenience of our exposition. The proposed SPOT
system can handle the case where an outgoing message is
forwarded by a few internal mail relay servers before
leaving the network. We discuss practical deployment
issues in Section 7.
In addition, we assume that an IP address corresponds to
a unique machine and ignores the potential impacts of
dynamic IP addresses on the detection algorithms in the
presentation of the algorithms [3], [24]. We will investigate
the potential impacts of dynamic IP addresses on the
detection algorithms in Sections 5 and 6.
4 BACKGROUND ON SEQUENTIAL PROBABILITY RATIO TEST
In this section, we provide the necessary background on
the Sequential Probability Ratio Test for understanding the
proposed spam zombie detection system. Interested readers
are directed to [21] for a detailed discussion on the
topic of SPRT.
In its simplest form, SPRT is a statistical method for
testing a simple null hypothesis against a single alternative
hypothesis. Intuitively, SPRT can be considered as an onedimensional
random walk with two user-specified boundaries
corresponding to the two hypotheses. As the samples
of the concerned random variable arrive sequentially, the
walk moves either upward or downward one step,
depending on the value of the observed sample. When
the walk hits or crosses either of the boundaries for the first
time, the walk terminates and the corresponding hypothesis
is selected.
As a simple and powerful statistical tool, SPRT has a
number of compelling and desirable features that lead to
the widespread applications of the technique in many areas
[22]. First, both the actual false positive and false negative
probabilities of SPRT can be bounded by the user-specified
error rates. A smaller error rate tends to require a larger
number of observations before SPRT terminates. Thus,
users can balance the performance (in terms of false positive
and false negative rates) and cost (in terms of number of
required observations) of an SPRT test. Second, it has been
proved that SPRT minimizes the average number of the
required observations for reaching a decision for a given
error rate, among all sequential and nonsequential statistical
tests. In the following, we present the formal definition
and a number of important properties of SPRT. The detailed
derivations of the properties can be found in [21].
Let X denote a Bernoulli random variable under
consideration with an unknown parameter , and X1;
X2; . . . the successive observations on X. As discussed
above, SPRT is used for testing a simple hypothesis H0 that
¼ 0 against a single alternative H1 that ¼ 1. That is,