INTERNATIONAL JOURNAL OF NETWORK MANAGEMENT
Int. J. Network Mgmt 2010; 20: 295–316
Published online in Wiley Online Library(wileyonlinelibrary.com) DOI: 10.1002/nem.749

An evaluation of automatic parameter tuning of a statistics-based
anomaly detection algorithm
Yosuke Himura1,*†, Kensuke Fukuda2, Kenjiro Cho3 and Hiroshi Esaki1
1Graduate School of Information Science and Technology, University of Tokyo, Tokyo, Japan
2
National Institute of Informatics/PRESTO, JST, Tokyo, Japan
3
Internet Initiative Japan, Tokyo, JapanSUMMARY
We investigate an automatic and dynamic parameter tuning of a statistical method for detecting anomalies in
network traffic (this tuning is referred to as parameter learning) towards real-time detection. The main idea behindthe dynamic tuning is to predict an appropriate parameter for upcoming traffic by considering the detection resultsof past t traces of traffic. The t is referred to as the learning period, and we discuss in particular the appropriate
value of t. This automatic tuning scheme is applied to parameter setting of an anomaly detection method basedon Sketch and the multi-scale gamma model, which is an unsupervised method and does not need predefined data.
We analyze the tuning scheme with real traffic traces measured on a trans-Pacific link over 9 years (15 min from14:00 Japan Standard Time every day, and 24 consecutive hours for some dates on the same link). The detection
results with parameter prediction are compared to those with ideal parameters that maximize the detection
performance for upcoming traffic. We also analyze predictability of the ideal parameter considering the pastchanges in it. The main findings of this work are as follows: (1) the ideal parameter fluctuates day by day; (2)parameter learning with a longer t is affected by significant events included in the period, and the appropriate t
is about three traces (days) for everyday 15 min traces and around 1.5 h for 24 h traces; (3) the degradation in
detection performance caused by introducing parameter learning is 17% with t = 3 for everyday 15 min traces; (4)the changes in the ideal parameter have no periodic correlation, and can be modeled as a random process followed
by a normal distribution. We show that one cannot consistently use a fixed parameter in statistics-based algorithms
to detect anomalies in practice. Copyright © 2010 John Wiley & Sons, Ltd.

1. INTRODUCTION
As the Internet has become an infrastructure essential to human life, all users are exposed toconsiderable threats such as those posed by viruses and worms, and distributed denial-of-service
attacks. These menaces must be detected in real time so that secure networks can be maintained, andnumerous methods of detecting anomalies in network have been proposed thus far. These anomaly
detectors are generally classified into two categories; the first is a signature-based approach, which finds
specific fingerprints of packet payloads predefined in their database [1], and the second is a statisticsbased approach, which defines network anomalies as deviations from referential statistical behavior[2–11]. These statistical models are especially needed for detecting unknown anomalies, e.g. outbreaksof new worms (zero-day attacks), which are currently common in the Internet. Classical methods find*Correspondence to: Yosuke Himura, Esaki laboratory, Room 102B, Building 2 of Engineering Department, The University ofTokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo, 113-8656, Japan†
E-mail: him@hongo.wide.ad.jp
CGS: Strategic International Cooperative Program of CNRS and JST

Copyright © 2010 John Wiley & Sons, Ltd.

Received 10 February 2010
Revised 19 March 2010
Accepted 12 April 2010

296

Y. HIMURA ET AL.

abrupt changes in traffic volume [2–6], and recent detectors have tried to uncover hidden anomalies
adopting machine learning or statistical models [7,8,10].
Even though a great deal of attention has been paid to statistical anomaly detection methods, one
crucial problem not fully discussed is how parameters should be set with these methods [12,13].
Arbitrarily determined parameters may detect significant (e.g. high-volume) anomalous traffic, but they
will miss minor (hidden) anomalies. Thus the parameter setting of statistical models directly affects theperformance (i.e. accuracy) of anomaly detection. In addition, it is generally difficult to choose
appropriate parameters a priori, because the macroscopic dynamics of anomalies in Internet traffic vary
greatly depending on the temporal and spatial features to be measured. The changes in anomalous
behavior pose difficulties in learning-based detectors [7,8,10], which defines anomalies by analyzing
past traffic behavior to extract low-intensity anomalies. Even though some earlier studies haveaddressed how to set parameters [5,14] on the fly, this parameter setting is just a conversion from a
confidence value (e.g. 99% or 95%) to a threshold. Hence this tuning does not consider the dynamics
of anomalies or the efficiency of anomaly detection, and even if we used such a parameter setting basedon the confidence level, we would need to find a better confidence level leading to better detection,
which is quantified by ground truth. Consequently, there has been demand for an automatic tuning
scheme that dynamically follows macroscopic trends in anomalous traffic, in order to realize accurate
and real-time anomaly detection. Furthermore, automatic and dynamic parameter tuning is essential
not only for detecting anomalies in the real world but also for comparing anomaly detectors. To ensurea fair comparison of detection performance, the parameters of all methods must be optimized inaddition to using the same dataset. One reasonable approach toward this demand is to predict the
behavior of anomalies in upcoming traffic by considering their trends in the past, in order toautomatically tune anomaly detectors. The tuning scheme will train anomaly detectors to uncoverhigh-abnormality traffic (e.g. scanning or flooding attack) and provide network operators with
detection reports including high-priority anomalies so that they can efficiently decide how to deal withthe detected traffic according to their management policy. This tuning is different from learning-based
anomaly detectors, because they still have to set thresholds to find anomalies after defining referential
behavior computed from learning with traffic traces. Also, automatic parameter tuning scheme can beapplied to many kinds of anomaly detectors.
This paper discusses automatic and dynamic parameter tuning, referred to as parameter learning. To
the best of our knowledge, this is the first intensive work on dynamic parameter tuning for anomaly
detectors. The main idea behind our learning framework is that we predict an appropriate parameterfor upcoming traffic by considering the detection result of the past several traffic traces. We particularly
focus on the learning period t, which is the number of traces needed for parameter prediction. Intuitively,t involves a trade-off between (a) a lower t, which leads to lower accuracy because there are fewer data
points to calculate statistics appropriately, and (b) a higher t, which will miss abrupt changes in themacroscopic dynamics of anomalies in network traffic. We investigate this trade-off by evaluating ananomaly detector based on the multi-scale gamma model [9], which is an unsupervised learning tooland does not need predefined data, so this tool is promising for security and suitable for discussing
evaluation results. We analyze this tuning scheme with real traffic traces measured at a trans-Pacific linkover 9 years (15 min from 14:00 Japan Standard Time (JST) every day, and 24 h for some dates) withpseudo ground truth generator validated by BLINC [15]. Thus far, some of these issues have beenaddressed in our earlier work [13], and we have additionally (a) analyzed how predictable the ideal
parameter is with respect to periodicity and a random process and (b) extended the dataset including
9-year-long traffic traces and three sets of 24 h consecutive traces. The four main results obtained fromthis work are that (1) the ideal parameter fluctuates daily and that (2) parameter learning with a longer
t is affected by significant events included in the period, and the appropriate t is about three traces(days) for everyday 15 min traces and about 1.5 h for 24 h traces. We have also found that (3) the
performance degradation caused by introducing parameter learning is 17% with t = 3, and that (4) thechanges in the ideal parameter have no periodical correlation, and can be modeled as a random process
followed by a normal distribution. The contribution of this paper is to clarify and quantify the
Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

EVALUATION OF AUTOMATIC PARAMETER TUNING

297

importance of setting dynamic parameters with statistics-based anomaly detectors in the real world, i.e.
it is ineffective to continuously use fixed values for parameters.

2. PRELIMINARIESThis section introduces three preliminaries involving an anomaly detection method (Section 2.1), traffic
traces collected over the long term and a traffic labeling scheme (or pseudo ground truth generator) toevaluate detection performance (Section 2.2), and an automatic parameter tuning method (Section 2.3).
2.1 Anomaly detection algorithm based on Sketch and multi-scale gamma model

We use an algorithm based on Sketch and the multi-scale gamma model [9]. The reasons for adopting
this method are (a) the technical advantage of detecting low-intensity (hidden) anomalies on multiple
timescales, (b) the ability to detect unknown events deviating from dynamically calculated reference
data (i.e. no need for learning data or predefined anomalies), and (c) availability of an implementation
tuned practically. The appropriateness of using a multi-scale gamma model has been discussed
elsewhere [16]. The main idea underlying detection is to find outliers in the normalized values ofstatistics computed from longitudinal behavior. The method is currently used in detecting source hoststhat generate anomalous traffic, and the overview of the detection procedure includes four steps:
1. Sketch: traffic is divided approximately into a set of sub-traffic from a source host. This is donewith the hash function of a quasi-huge hash table called Sketch [4] and using a source IP addressfor hashing keys. This quasi-huge hash table is created with N hash functions of table-size M.
2. Multi-scale gamma model: for each piece of sub-traffic, the histogram for the number of packets
arriving during a certain timescale D is approximated as a gamma distribution. The gamma
distribution has two parameters: a determines the shape of the histogram, and b the scale. a ishelpful for detecting hidden anomalies. This approximation is conducted on multiple timescales(D = D0 ¥ 2j with j = 0, . . . , 7), and the computed parameters are aggregated as one measure for eacha and b.
3. Anomaly identification: the a of the set of sub-traffic are compared each other, and the sub-traffic
having outlier a is an anomaly, that is, if |a - ma| > qa ¥ sa, the sub-traffic is judged to be an
anomaly, where ma and sa stand for the average and standard deviation of a among the set of
sub-traffic in the data, and qa is the threshold for a. The same technique is applied to b.
4. The above procedures are carried out for each time window T. A source host detected over at least
one window is regarded as one anomaly. The detector focuses on host that sends more than P
packets in a trace, which is referred to as an event, to calculate reliable statistics (a and b). Also,a large amount of packets allows us to identify whether the detected traffic is truly an anomaly.

α − μαis a kind of Mahalanobis distance (i.e. a normalized metric), the threshold qa represents
σα
the normalized degree of deviation from referential behavior. Hence lower qa leads to a higher numberof detected events, including all events detected by any higher qa.
For all traces, we empirically set N = 8, M = 32, P = 1000, and D0 = 5 ms, following Dewaele et al. [9],and T = 15 min. Although the algorithm requires several parameters, we concentrate on a main
parameter qa and do not use qb, because the changes in the shape parameter clarify low-intensity
anomalies (i.e. qa can detect hidden anomalies better than qb), and the use of both thresholds leads tocomplicated discussion on evaluation results. Also, detection by qa and by qb are independent, so thischoice for evaluation of learning is compatible with other studies using this anomaly detector. Also, thisdetection tool empirically focuses on host traffic composed of more than 1000 packets per trace (which
we call an event), because larger numbers of packets allow us to identify abnormalities in detectedtraffic. After this, the main threshold qa is referred to as q.
Since

Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

298

Y. HIMURA ET AL.

2.2 MAWI dataset and predefined pseudo ground truth for computing detection performance

Rather than using synthetic traffic, we conduct our evaluation by using a measurement and analysis
of wide-area Internet (MAWI) traffic repository [17]. The traffic traces have been captured at atrans-Pacific link between the USA and Japan (from 14:00 to 14:15 JST) since 2001, and they consist of
15 min pcap traces. The payloads of all packets were removed for all traces, and both source anddestination IP addresses were anonymized, preserving the prefix structure. The observed link had been
upgraded twice up to the end of 2009; the first was from 18 Mbps to 100 Mbps in July 2006, and thesecond was from 100 Mbps to 150 Mbps in July 2007. The link was congested before the first upgrade.
In addition to the 15 min traces every day, we used some consecutive 24 h traces known as the Day in
the Life of the Internet (DITL) dataset [18] (these data are also collected at the same link and stored as
15 min traces). The long-term everyday traces and 24 h all-day traces will subsequently be referred toas 15 min traces and 24 h traces.
We analyze 15 min traces from 1 January 2001 to 31 December 2009, and 24 h traces on 3 March 2006,
10 January 2010, and 19 March 2008. The long-term measurements make this dataset suitable forinvestigating changes in optimal parameters for statistical anomaly detectors. In addition, the dataset
provides us with generality of results: time generality thanks to the long measurements, and link state
generality due to the two upgrades. Moreover, as these traffic traces are available to the public, using
this dataset adds reproducibility and comparability to our study. (Also, this dataset has been wellstudied [9,19,20]). This dataset has 3098 traces from 1 January 2001 to 31 December 2009 (some traces
could not be provided because of measurement failures), i.e. 900 GB in size in the gzip file format. Even
though these 15 min traces are not consecutive (every 15 min throughout the day), the measurement
location and the start time (14:00 JST) for all traces are the same. Hence these traces are sufficient toevaluate the algorithm’s ability to follow macroscopic (e.g. several days level) changes and microscopic(e.g. hours or 1-day level) changes in traffic anomalies to be discussed.
We classify events into six categories (Attack, Victim, Warning, OK, Special, and Unknown) according
to the abnormality (or harmfulness) of the events by using our heuristics based on port number, TCP
flag, and communication structure as used in Himura et al. [13]. This heuristics is a hybrid made up
of a traditional approach (based on port number) and a state-of-the-art method (based on communication pattern [15]) to leverage the advantages of both. Table 1 lists the categories and examples ofheuristics, and we show all rules to identify Attack events in Appendix A. Also, we validate theseheuristics in Appendix B by Reverse BLINC used in Kim et al. [21], showing that these heuristics canuncover more Attack events, including those identified by BLINC. Here, we define Anomalous asincluding both Attack and Victim categories, and we define Normal as including Warning, OK, Special,and Unknown categories. We found out that most Unknown events are generated by P2P software asshown in Appendix B. Figure 1 shows the classification results of the MAWI dataset, plotting thenumber of events in a trace. Figure 1(a) shows the evolution of the breakdown over 9 years. The
continuously high number of Anomalous events in the last half of 2004 is due to the massive outbreakof a worm. The other figures show that of 24 h traces: (b) 3 March 2006, (c) 10 January 2007, and (d)19 March 2008. For each figure, there are constant number of Anomalous events, whereas Normal
events represent the daily periodicity. With these data, we can identify whether an event reported by
the anomaly detector is an actual anomaly or not, so that these heuristics enable us to investigate
parameter learning.
2.3 Automatic parameter tuning and learning period

Here we explain the automatic parameter tuning method, which is schematically represented in
Figure 2. The basic idea behind this method is that the optimal threshold for upcoming traffic on datet (referred to as qt(t)) is determined to be the one that has produced the best accuracy (detection
performance a(qt(t - 1))) in the past t traffic traces on dates t - 1, . . . , t - t. We define this t as thelearning period. The detailed procedure to determine qt involves five steps. (modification note: we use
qt(t) instead of qt if needed.)
Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

EVALUATION OF AUTOMATIC PARAMETER TUNING

299

Category

Explanation of category

Example of heuristics

Attack

The host sends many
malicious packets

If SYN flagged packets account for more than 20%
of all packets, then the host is regarded as ‘anattacker of SYN flooding attack’ and the eventis classified into the Attack category

VictimThe host receives many
malicious packets

If the ratio of SYN/ACK flagged packets is morethan 20%, then the host is regarded as ‘a victim
of a SYN flooding attack’ and the event isclassified into the Victim category

Warning

The host is legitimate,
but can be malicious
in some cases

If over 50% of packets are HTTP requests, thenthe host is regarded as ‘a sender of many HTTP
requests’ and the event is classified into theWarning category

OK

The host is legitimate

If more than 50% of packets are from source port
80, then the host is regarded as ′a web server’and the event is classified into the OK category

SpecialThe host is a server orclient of a specificapplication such as
DNS, FTP, mail, or
P2P

If more than 50% of packets are from source port
53, then the host is regarded as ‘a DNS server’and the event is classified into the Special
category
If (a) higher source and destination ports accountfor more than 50% of total port usage, (b) themost dominant host-to-host traffic accounts forless than 30% in the number of packets, and (c)the host sends packets to more than 10
destinations, then the host is regarded as ‘a P2P
application user’ classified into the Special
category

Unknown

The host is not classified
into any of thesecategories

If the host cannot be classified into any of thesecategories, then the event is classified into the
Unknown category (most of them related to P2P
by BLINC validation. See also Appendix B)

Table 1. Categories and examples of heuristics. Attack and Victim events are regarded as
Anomalous category, whereas events of the other four categories are referred to as Normal category.
All heuristics to identify Attack events are listed in Appendix A
1. The initial optimal parameter is empirically set to qt(0) = 1.7. This value is used only during the
beginning of parameter learning, i.e. we do not have t traces in the past for learning (i.e. whilet < t), and once qt(t) is determined then the initial value is no longer used. In our experiment, t = 0
is the date 1 January 2001, t = 1 is 2 January 2001, and so on.
2. Run the anomaly detector on the past t traces while changing qt(t) (increase it by d = 0.1 from 0.0)
to find a (local) maximum.
A
3.
, where A
Compute the performance of the past detection a(qt(t)) for each qt(t) as a (θτ ( t ) ) =A+N
and N are the total counts of Anomalous and Normal events detected with the threshold qt(t).
4. Find the optimal threshold for date (t + 1), which produces the (local) maximum in performance:θτopt ( t + 1) = arg maxθ a (θα ( t ) ) that satisfies a(qt(t)) - d ) < a(qt(t)) and a(qt(t)) + d) < a(qt(t)). d is also
empirically determined, and the selection of d has a trade-off between precision of optimizationand possibility of failing in finding the optimal value; for example, e << d leads toa(qt(t)) = a(qt(t) + e) in most cases, and it fails to find appropriate θτopt satisfying the above
condition.
Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

300

Y. HIMURA ET AL.

Figure 1. Breakdown of MAWI dataset: (a) 9-year 15 min traces, and 24 h traces on (b) 3 March
2006, (c) 10 January 2007, and (d) 19 March 2008. An event is defined as a source host that sends
over 1000 packets per trace

Heuristics toidentify Attacks

Upcoming traffic
trace

trace

trace

trace

trace

performance a(qt)trace

Optimal parameter estimation by using pasttraffic data (τ=4)

Offlineanomalydetection

threshold qt
opt

qt

trace

Onlineanomalydetection

Time

Past

Current

Figure 2. Method of parameter learning. Optimal parameter θτopt for upcoming traffic is estimatedby using past t traffic traces; θτopt maximizes the detection performance of the past t traces(t = 4 in this figure)5. If there is no qt(t) satisfying the above condition to determine θτopt ( t + 1) , θτopt ( t ) for the previous
traffic trace is used for detecting anomalies in upcoming traffic: θτopt ( t + 1) = θτopt ( t ) . The same policy
is used if there are no traffic traces of corresponding t dates.
Anomalies are detected separately for each 15 min traffic trace, and A is the total number of detected
Anomalous events over the past t days (the same for N), whereas the consecutive 24 h traces areconcatenated into one trace in order to avoid recounting an anomaly event existing in more than one
traces. We define the learning with 15 min and 24 h traces as 15 min and 24 h learning.
This procedure for parameter learning is not specific to the anomaly detector; learning is an
optimization problem (i.e. finds the best solution that maximizes a function), and it can be applied toother parameters of different anomaly detectors. Also, this procedure is applicable to optimize multiple
parameters; that is, the learning is a kind of combinatorial optimization. Searching optimal parameters
is enhanced by traditional methods such as hill climbing, simulated annealing, or genetic algorithm.
The performance a(qt(·)) can be interpreted as detection efficiency—the percentage of the number ofdetected Anomalous events over that of total detected events—and θτopt ( ⋅) maximizes this. In this sense,
Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

EVALUATION OF AUTOMATIC PARAMETER TUNING

Ratio of detected events

opt

opt

q1

1

(a) Past 1 day
0.8
0.6

301

q28

1

OK
WarningSpecialUnknown
AttackVictim(b) Past 28 days
0.8
0.6

0.4

0.4

0.2

0.2

0

OK
WarningSpecialUnknown
AttackVictim

0
0

1

2

3

Threshold q

4

5

0

1

2

3

4

5

Threshold q

Figure 3. Example of determining optimal parameter θτopt : (a) t = 1 day of learning; (b) t = 28 daysof learning. Detected events are classified into six categories by the pseudo ground truth generator
based on our heuristics. The detection performance is the summation of Attack (red)and Victim (blue)
detected Normal events can be interpreted as false alarms. Although this metric is different from thecommon performance metrics (i.e. the false positive rate or the false negative rate), a(qt) is more suitablefor determining θτopt ( ⋅) ; these common metrics must take into consideration all undetected events, but
we may not necessarily be able to identify them. Also, since no classification method (ground truth
generator) is perfect, we must consider misclassified events (e.g. some of the Unknown events are
actually Anomalous). Both the denominator and numerator used by the two common metrics areaffected by misclassifications, whereas the denominator of a(qt(·)) is not affected because A + N is thetotal number of detected events. Another reasonable choice of performance metric might be to remove
Unknown events from denominator and numerator from the common two metrics, but since wemanually found most of the Unknown events are P2P, this removal of Unknown would lead tooverestimation of performance. Another way to quantify performance is scoring detection results
according to abnormality of detected events (1 point for Attack, -1 point for OK, and so on). However,since it is generally difficult to set reasonable weights of abnormality, we focus only on Anomalous
events, which should be detected first. Therefore, a(qt(·)) is more suited to computing θτopt .
Figure 3 shows an example of parameter determination. The x-axis is the value of qt and the y-axis
plots the fraction of detected events of a category over the total number of detected events. Figure 3(a,b) shows the detection results of past t = 1 and t = 28 days since 6 December 2005. The performancea(qt) is the fraction of Attack (red) and Victim (blue) events over the total number of detected events.
Since no Victim events were detected on this day, a(qt) is identical to that plotted by the red line.
• The best performance in Figure 3(a) is provided by qt(t) ∈ [4.4,4.6], because a(qt(t)) = 1.0 (i.e. 100%).
However, these parameters are not reasonable due to the few detected events (only one event is
detected and many Anomalous events have been missed). When only a few events are detected,a(qt(t)) exhibits the step-like curve as shown in Figure 3(a) (i.e. this means a(qt(·)) = a(qt(·) + d ) anddoes not satisfy the condition in step 4). Hence choosing a local maximum is better for retaining
a reasonable number of detected events. Here, we have one local maximum at qt(t) = 1.8, and four
Anomalous events are detected, and thus θτopt ( t + 1) = 1.8. Conversely, only one Anomalous event
is detected for qt > 2.0.
• The qt = 2.4 in Figure 3(b), on the other hand, is optimal according to our heuristics. Thus a large
amount of learning data makes it easier to determine a good θτopt, and θτopt ( t + 1) = 2.4 .
Thus far, we have found that the typical longitudinal pattern of events detected by using a tuned qa
is continuous, such as that in Figure 4(a). However, there are few spiky traffic patterns such as that in
Figure 4(b), while a tuned qb would detect more. Since spiky traffic is easily detected unlike continuous
traffic, this finding also supports our motivation to discuss qa prior to qb.
Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

302

Y. HIMURA ET AL.

Traffic [pps]

10
10

4

10

(a) Continuous traffic
3

4

102

102

10

1

10

1

10

0

10

0

0

100

200

300

400

500

600

(b) Spiky traffic

103

700

800

900

0

100

Time [sec]

200

300

400

500

600

700

800

900

Time [sec]Figure 4. Example of anomalous traffic detected by tuned qa: (a) typical traffic and (b) atypicaltraffic. Both types of traffic are judged to be ‘SYN flooding attacks’Intuitively (but not analyzed with real traces), t has a trade-off:• When t is lower, θτopt cannot be determined because there are few data points to obtainappropriate statistics.
• When t is higher, θτopt is not suitable because a longer t causes unexpected delays, affecting theability to follow macroscopic changes in anomalies.
Thus we need to find an appropriate value for t.
To evaluate the effect of parameter learning on detection performance, we compare detection resultsof predicted threshold θτopt ( t ) and the ideal threshold θ 0opt ( t ) which leads to the best performance fordetecting anomalies in upcoming traffic (we use t = 0 to explain this ideal parameter). We define θ 0opt ( t )as maximizing the detection performance of upcoming traffic on date t θ 0opt ( t ) = arg max a (θ 0( t ) ),whereas θτopt ( t ) maximizes the detection performance of past t traces on dates t - 1, . . . , t - t. We willrefer to θτopt ( ⋅) as qt(·), because we will only discuss the changes in the optimal threshold, and webasically omit ‘(t)’ from qt(t) if t is not needed to discuss the results.

3. EVALUATION
To discuss the automatic parameter tuning, we study the changes in optimal parameters qt (Sections
3.1 and 3.2), an appropriate t, and the performance degradation in anomaly detection caused byintroducing parameter learning (Sections 3.3 and 3.4), the predictability of the ideal parameters (Section
3.5), and the difference between 15 min and 24 h learning (Sections 3.6 and 3.7).
3.1 Changes in values of optimal parameter and number of detected eventsFirst, we assess changes in the value of optimal parameter qt for 15 min learning with some fixedlearning periods t. Figure 5 plots the transition in qt from the beginning of 2001 to the end of 2009. The
upper figure depicts microscopic (day-to-day) changes in q0 (the ideal parameters), while the lower
figure plots macroscopic (monthly) changes in q0 (ideal) with the red line, q3 (3 days of learning) withthe green line, and q28 (28 days of learning) with the blue line, plotting the averages and standard errors
for each month. The x-axes plot the dates, and the y-axes have the values of qt in both figures. The
upper figure indicates that the ideal parameter q0 fluctuates day by day around q0 ª 1.5. The averageand standard deviation of q0 for 9 years are 1.43 and 0.57. The fluctuations in q0 emphasize how
important it is to dynamically tune parameters for statistics-based anomaly detectors, because q0 is notstable over time. On the other hand, the lower figure shows that the parameter prediction with a highert (blue) leads to a larger deviation in the value of qt from the ideal parameter (red) than that with alower t (green). Since Pearson’s correlation coefficient between q0 and q3 is 0.80, but that between q0 and
q28 is 0.35, a higher t fails to follow the changes in q0. A significant case is the change in qt from April
2003 to May 2003. The q0 decreases from 1.54 to 1.25, but q28 increases from 1.52 to 2.91, whereas q3
varies from 1.80 to 1.82. The high value of q28 during May 2003 derives from qt = 3.9 from 14 May 2003
Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

Threshold q t(monthly averages)

Threshold q o

EVALUATION OF AUTOMATIC PARAMETER TUNING

4
3.5
3
2.5
2
1.5
1
0.5
0
01/01/01 01/01/02 01/01/03 01/01/04
4
3.5
3
2.5
2
1.5
1
0.5
0
01/01/01 01/01/02 01/01/03 01/01/04

303

(a)

01/01/05 01/01/06 01/01/07 01/01/08

01/01/09 01/01/10(b)

28 days learn
3 days learn
No learn
01/01/05 01/01/06 01/01/07 01/01/08

01/01/09 01/01/10

Date

Figure 5. Changes in qt for 15 min learning: (a) microscopic (daily) changes in ideal threshold q0; (b)monthly averages in qt for t = 0, t = 3, and t = 28 (past 3 or 28 days of learning). The ideal
threshold q0 fluctuates daily, and longer learning period t leads to higher and more unstable qt

to 22 May 2003. By manually checking this cause, we found that the data from 24 April 2003 and 12
May 2003 had an influence on q (one Anomalous event is detected with q28 = 3.9 for the traces of 24
April 2003 and 12 May 2003, respectively). The data from 12 May 2003 triggered the q28 = 3.9 from 14
May 2003, and the q28 = 3.9 rapidly decreased when the date of 14 April 2003 was beyond the range ofthe past t days. This case study also points out the inefficiency of a longer t. A higher t, on the other
hand, yields a higher and more fluctuating qt over 9 years, but the standard deviation of each plot (i.e.
the variance within a month) is small. The averages and standard deviations of the plots are 1.42 ⫾ 0.23
for q0, 1.78 ⫾ 0.32 for q3, and 2.26 ⫾ 0.62 for q28. A plausible reason for the inappropriateness of a longer
t is that the prediction of optimal qt can be affected by significant events during the learning period,
and these events will fix qt to a certain value.
Figure 6(a–c) highlights the microscopic (day-to-day) changes in q0, q3, and q28 (from November 2005
to April 2006), and Figure 6(d–f) presents the results of anomaly detection with the thresholds
determined from parts (a–c), plotting the number of detected Anomalous and Normal events. The
x-axes are the dates, the y-axes in the upper figures are the values of qt, and the y-axes in the lower
figures are the values of detected events (red: Anomalous events; green: Normal events). Obviously, ahigher t is inappropriate for estimating the optimal threshold, because q28 stably remains higher andthere are fewer detected events than those with q0. The stable values of q28 also reminds us of theinfluence of significant events on determining qt. In other words, the parameter estimation with alonger t cannot follow the changes in anomalous traffic. Thus learning with a longer t is inappropriate
for obtaining a suitable qt to detect anomalies in practice, and we need to find an appropriate t.
Consequently, the ideal threshold q0 fluctuates daily, and a longer learning period (higher t) produceshigher and more stable qt, which decreases the number of detected events. The next section discusses
our further investigations into the reason for worsened performance caused by a longer learning
period.
3.2 Variable learning period

We study the strong influence of specific events on the estimates of optimal threshold qt by computing
the best performance with unfixed t among [0,28]. We choose an optimal learning period of
Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

Estimated threshold q t

304

Y. HIMURA ET AL.

3.5
3

3

2.5

3.5

(b) Past 3 days

3

2.5

2

2

2

1.5

1.5

1

1

1

0.5

0.5

0.5

0
11/01/05

01/01/06

005/01/06 11/01/05

03/01/06

Normal(d) No learning Anomalous

1000

01/01/06

005/01/06 11/01/05

03/01/06

Normal(e) Past 3 daysAnomalous

1000

100

100

100

10

10

10

1
11/01/05

01/01/06

Date

03/01/06(c) Past 28 days

2.5

1.5

1000

# of detected events

3.5(a) No learning

1
05/01/0611/01/05

01/01/06

Date

03/01/06

05/01/06

Normal(f) Past 28 days
Anomalous

1
05/01/0611/01/05

03/01/06

01/01/06

01/01/06

Date

03/01/06

05/01/06

Figure 6. Changes in qt and the number of detected events (from November 2005 to April 2006) for
15 min learning: (a, d) no learning (t = 0), i.e. the ideal threshold; (b, e) past t = 3 days of learning;(c, f) past t = 28 days of learning. Longer learning period provides high and continuous qt, whichleads to lower number of detected events, and this learning misses dynamics of traffic anomalies

25

|

5

(a)

4.5

|

Estimated
threshold q t

Optimal learning
period t

30

20
15
10
5

A

0
11/01/05 12/01/05

01/01/06

02/01/06 03/01/06

3.5
3
2.5
2
1.5
1

B
Date

(b)

4

04/01/06 05/01/06

0.5
11/01/05 12/01/05 01/01/06 02/01/06 03/01/06 04/01/06 05/01/06

Date

Figure 7. Changes in (a) unfixed optimal learning period τ (from 1 to 28) and (b) corresponding
threshold θτ . Learning is highly affected by significant days’ data, because the best performance isprovided by increasing t (slanted lines in (a)), which is tuned to include influential dates such as Aor B. Correspondingly, qt is fixed to a certain value by significant events, so t should beappropriately fixed to avoid such effect of significant events

τ = arg max a (θτ ) , and investigate changes in the values of τ and θτ . Figure 7 plots the results withthe data from November 2005 to April 2006. The x-axes are the dates, the y-axis in Figure 7(a) is τ , andthe y-axis in Figure 7(b) is θτ derived from Figure 7(a). In Figure 7(a) there are several slanted lines witha slope of one, which means that some data had a strong influence on determining qt during the periodof t days that included these influential traces (until t reaches 28, i.e. the upper bound of ourexperiment). To investigate the reasons for this effect, we inspect labels A and B, which are two of theroots of these lines.
A: Data for 9 September 2005 (label A) set θτ = 2.6. The detected events on the data consist of five
Attacks.
B: The combination of data from 18 and 19 December 2006 (label B) sets θτ = 2.5. This thresholddetected three Attacks, four Warnings, and one Unknown.
Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

# of detected events (left)
Performance (right)

EVALUATION OF AUTOMATIC PARAMETER TUNING(a) 2004 last half

140
120
100

(b) 2006 first half

0.4 140

NormalAnomalous
Performance
No Detection Performace

0.3
0.25

80

100

0.16 100

80

0.15

40

0.1

20

60

0

0
0

5

10

15

20

25

Learning period t [days]

0.16
0.14

0.12

0.12

0.08

0.05 200.18

0.14 80

0.1

40

0.2

NormalAnomalous
Performance
No Detection Performace

0.18 1200.2
60(c) 2008 first half

0.2 140

NormalAnomalous
Performance
No Detection Performace

0.35 120

305

60

0.1

40

0.08

20

0.06

0

0.06
0

0

5

10

15

20

25

Learning period t [days]

0

5

10

15

20

25

Learning period t [days]

Figure 8. Evaluation of t for 15 min learning: (a) last half of 2004; (b) first half of 2006; (c) first halfof 2008. Appropriate t is around 3 days except for period of worm (a), considering the balance
between the number of detected events and detection performance. ‘No Detection Performance’
indicates the fraction of Attack events over all events in analyzed traffic
Since such events have a strong effect on a(qt), variable t is inappropriate to follow the macroscopicchanges in Internet traffic. In addition, the changes in θτ for variable t (Figure 7(b)) are almost the sameas those for t = 28 (Figure 6(f)), and the performance with τ is lower than that with t = 3. Thus t must
be appropriately fixed, and we discuss our evaluation of this in the following section.
3.3 Optimal learning period

Now let us discuss the most appropriate learning period for setting the automatic and dynamic
thresholds. Figure 8 summarizes the detection results and performance as a function of learning period
t with different periods of data: (a) the last half of 2004; (b) the first half of 2006; and (c) the first halfof 2008. The x-axes are t (from 1 to 28 days), the left-hand y-axes plot the number of events detectedwith qt (red: Anomalous; green: Normal), and the right-hand y-axes depict the detection performancea(qt) (blue). Each plot shows the averages and their standard errors in the 15 min detection results fora half year. In the last half of 2004 there was a massive outbreak of a worm lasting until the end of thisyear. This caused the t-independent result shown in Figure 8(a); any t retains certain values for thenumber of detected events and performance. This should derive from the long-term dominance of only
one kind of anomaly. In contrast, for other periods (Figure 8(b, c)), we can confirm the trade-off in t.
• The red and green lines indicate that a longer t yields to fewer detected events than a shorter t. Thisis because a longer t results in high qt (Figure 6), and a higher qt leads to fewer detected events.
• The blue line explains that a shorter t (1 or 2 days) leads to worsened performance; i.e. a shorter tcannot obtain a sufficient amount of data to appropriately determine qt.
The increasing value of performance for shorter t means that the decrease in the number of detected
Normal events is larger than that of Anomalous events; that is, parameter learning with appropriate
t can follow the trends in anomalies. From these results, we can conclude that a t of around 3 isempirically the most appropriate because a(qt) is larger and the number of detected Anomalous eventsis also higher in our dataset. In addition, we compare the performance a(qt) with the percentage ofAnomalous events in the original dataset—(a) 30.5%, (b) 8.2%, and (c) 7.4%—which are indicated by
the gray lines in the figures. Increase in a(qt) with respect to the percentage for any t in Figure 8(b, c)
indicates the algorithm’s efficiency. Conversely, in Figure 8(a), the scanning activities of the worm form
statistical referential behavior, so that they spoil the anomaly detection method.
3.4 Performance degradation caused by introducing parameter learning

Next, we compare the performance of 15 min learning with t = 0 (the ideal threshold) and that witht = 3 (the most appropriate prediction of qt) in Figure 9. The x-axis is the date, the y-axis in Figure 9(a)Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

306

Y. HIMURA ET AL.

Figure 9. Performance degradation caused by introducing parameter learning: (a) number ofdetected Anomalous events; (b) performance for t = 0 and t = 3(b) t = 3 days

Difference in q t between
this day and previous day

Difference in q t between
this day and previous day

Frequency(a) t = 0 (ideal parameter)

Figure 10. Random process analysis of changes in (a) q0 and (b) q3 of 15 min learning for 150 Mbps
link during 2008 (related to Figure 6(a, b)). q0 can be treated as a random process followed bynormal distribution

is the number of detected Anomalous events, and the y-axis in Figure 9(b) is the fraction of the numberof detected Anomalous events over that of all detected events for each day. In both figures, the gray lines
plot the results for t = 0 (Figure 6(d)), and the red lines plot those for t = 3. Figure 9(b) represents thedegradation in performance of parameter learning; however, the degradation is acceptable for detecting
anomalies in practice. The performance with parameter learning worsens by 16.6% on average, and its
standard error is 9.2%. Also, learning reduces the number of detected anomalies by about 50%(Figure 9(a)). t = 0 results in 10.8 ⫾ 1.3 detected Anomalous events, whereas t = 3 produces 5.4 ⫾ 0.9.
3.5 Predictability of ideal threshold

In addition to evaluating degradation in detection performance, we investigate the predictability of q0
for upcoming traffic from the past q0 by doing time series analysis. This is also practically important
for real-time anomaly detection.
First, we inspect the time correlation of q0 for 15 min learning, and Figure 14 highlights
N −t −1 ( θ 0( n ) − μθ ) ( θ 0( n + t ) − μθ 0 ), and (b) power spectrum
the results of (a) autocorrelation Rθθ (t ) = ∑
n=0
σ θ20
2
f
N −1
X ( f ) 2 = ∑ n=0 θ 0 ( n ) × exp −2π i n , where q0(n) is q0 on date n as shown in Figure 5(a). Here, q0(0) isNthe estimated threshold of 1 January 2001 (q0(1) is that of 2 January 2001, and so on), μθ0 and σ θ20 are
the average and variance of q0(·), p is the circle ratio, and i is an imaginary unit. N is the total number(

Copyright © 2010 John Wiley & Sons, Ltd.

)

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

EVALUATION OF AUTOMATIC PARAMETER TUNING

307

of q0(·), i.e. N = 1826 days for the sequence from 1 January 2001 to 31 December 2005, so that we can
avoid the long-term lack of data in 2006. These two figures reveal that there is no strong periodic
correlation in q0. Also, the low value of Rqq(t) for lag t = 1,2,3 represents almost no time correlations
among consecutive q0(·). These results also imply that anomalous traffic does not have significant
periodicity, and the optimal learning period t = 3 shown in the previous section results from thewell-balanced amount of data rather than the macroscopic tendencies of anomalies, i.e. shorter learning
leads to insufficient amount of information for estimating q0(·), while longer learning is affected byevents on significant days, so that it cannot follow fluctuating q0(·). In summary, the nonexistence of
periodicity in q0(·) suggests that we have to find alternative methods to predict q0(·) for upcoming traffic.
Second, we investigate how much q0(·) changes daily. Figure 10 displays the distribution of differences in the values of qt (i.e. qt(n) - qt(n -1)) for (a) t = 0 and (b) t = 3 during 2008 (Figure 6(a, b) shows
the changes in the values of qt(·) for both t). The x-axes represent the day-to-day differences in qt(·), andthe y-axes count the frequency of the differences. The histogram in Figure 10(a) is bell-shaped, and we2
1⎛ (x − μ ) ⎞exp ⎜ −
with m = 0.00 and s = 0.78; that is, the q0(·)
fit it as a normal distribution f ( x ) =σ 2 ⎟⎠
2πσ⎝
for upcoming traffic is predicted to be the same as that for the previous day’s traffic with a prediction
error of 0.78 ¥ 2 at 95% probability, according to the two-sigma rule. The histogram in Figure 10(b), on
the other hand, is more skewed (m = 0.01 and s = 0.56). Considering that a longer t leads to higher
counts in 0, this figure also implies that events on significant days influence the determination of qt.
To obtain a better approximation of this model, we may use zero-inflated models, even though themodel of the changes in q3(·) makes less practical sense.
In summary, the changes in q0(·) have no temporal correlation, and represent a random process
followed by a normal distribution (i.e. we observed few significant jumps in the changes in q0(·)).

3.6 Parameter learning with consecutive 24 h traffic traces

We evaluate 24 h learning, i.e. parameter learning with the consecutive 24 h traces measured on the same
link (also stored in the same repository as 15 min traces). The same set of parameters for 15 min learning
is applied to that of 24 h learning. However, this 24 h learning is slightly different from the 15 min one
in that the anomaly detection method is run for consecutive traffic traces to avoid repeatedly recounting
an anomaly event included in more than one trace. Therefore, as the number of events detected with 24 hdata will be fewer than that with 15 min data, the amount of data required should be larger.
Figure 11(a–c) highlights the changes in the value of qt for (a) t = 0, i.e. the ideal threshold, (b) t = 4,
i.e. 1 h of learning, and (c) t = 12, i.e. 3 h of learning. Also, Figure 11(d–f) shows the changes in thenumber of Anomalous and Normal events detected with qt in the above figures. The x-axes plot
the dates, the y-axes in the upper figures are the values of qt, and the y-axes of the lower figures are
the number of detected events. The fluctuations in qt and the number of detected events with 24 htraces are similar to those with 15 min traces (Figure 6). Also, a longer t leads to higher and continuous
values for qt, which results in fewer detected events. The averages and standard deviations of optimal
thresholds qt are (a) 1.43 ⫾ 0.49 for t = 0 (ideal), (b) 1.74 ⫾ 0.59 for t of 1 h, and (c) 2.45 ⫾ 0.59 for t of
3 h. In addition, the averages and standard errors for the number of detected events are (d) 69.2 ⫾ 13.9
for Normal and 5.8 ⫾ 1.1 for Anomalous, (e) 53.0 ⫾ 16.8 for Normal and 4.5 ⫾ 1.3 for Anomalous, and(f) 4.6 ⫾ 1.6 for Normal and 0.6 ⫾ 0.2 for Anomalous. This also suggests that an appropriate value fort can be chosen to efficiently detect anomalies on an hourly scale.
Figure 12 plots the performance as a function of t with the data from (a) 3 March 2006, (b) 10 January
2007, and (c) 19 March 2008. For each figure, the x-axis represents the value for t, the left-hand y-axis
plots the number of detected Anomalous (red) and Normal (green) events, and the right-hand y-axis
shows the performance (blue). Both y-axes plot the average values with standard errors in 24 h traces.
These figures reveal that the number of detected events decreases with the increase in t, andappropriate learning periods are (a) t = 7, i.e. 1.75 h, (b) t = 6, i.e.1.5 h, and (c) t = 3, i.e. 0.75 h,
Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

Copyright © 2010 John Wiley & Sons, Ltd.

4

12:00

16:00

20:00

08:00

Time

12:00

16:00

20:00

24:00

12:00

16:00

20:00

1
00:00

04:00

08:00

Time

12:00

16:00

20:00

Normal(f) Past 3 hoursAnomalous

08:00

24:00

24:00

2

8
2 hours

10

2

6

8
2 hours

10

Learning period t

4
1 hour0.04
12
3 hours

0.06

0.08

0.1

0
0 hour

0

20

40

60

80

100

2

6

8
2 hours

10

Learning period t

4
1 hourNormalAnomalous
Performance
No Detection Performance(c) 2008

12
3 hours

0.06

0.08

0.1

0.12

0.14

0.16

0.18

0.2

Figure 12. Evaluation of t with 24 h consecutive traces: (a) 3 March 2006; (b) 10 January 2007; (c) 19 March 2008. ‘No Detection
Performance’ indicates the fraction of Attack events over all events in analyzed traffic. Appropriate t are around 1.75 h for (a),1.5 h for (b), and 0.75 h for (c), considering the balance between the number of detected events and the performance

Learning period t

12
3 hours0
0 hour6

0
4
1 hour20

0
0 hour

0.06

0.08

40

0

20

40

60

60

0.16

0.12

0.1

140
0.18 120

0.2

0.12

NormalAnomalous
Performance
No Detection Performance(b) 2007

0.14 80

0.16 1000.18 120

0.2 140

80

NormalAnomalous
Performance
No Detection Performance(a) 2006

0.14

100

120

140

Figure 11. Changes in qt for consecutive 24 h traffic data of 18 March 2006: (a) no learning, i.e. ideal threshold; (b) past 1 h oflearning; (c) past 3 h of learning. Similar to 15 min learning, higher t leads to high and continuous qt, decreasing the number ofdetected events

Time

04:00

1
00:00

24:00

1000

04:00

(c) Past 3 hours

0
00:00

1
00:00
20:00

24:00

10

16:00

20:00

10

12:00

16:00

10

08:00

12:00

100

04:00

08:00

Normal(e) Past 1 hour Anomalous

0
00:00

1
0.5

1.5
1

2
1.5

2

0.5

2.5

2.5

04:00

4
3.5
3

(b) Past 1 hour

3

1000

24:00

4
3.5

100

100

08:00

Normal(d) No learning Anomalous

04:00(a) No learning

0
00:00

0.5

1

1.5

2

2.5

3

3.5

1000

Estimated threshold q t# of detected events# of detected events (left)
Performance (right)

308
Y. HIMURA ET AL.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

EVALUATION OF AUTOMATIC PARAMETER TUNING

309

considering both the performance and the number of detected events. These t balance the trade-off
between the amount of information to determine qt versus the influence of significant events onparameter learning. In addition, the average percentages of Anomalous events for each trace in the 24 htraces without detection are (a) 7.6%, (b) 5.1%, and (c) 9.6%, as plotted by the gray lines in the figures.
These figures also indicate the algorithm’s efficiency because any increase in the percentage of detected
Anomalous events resulted from the anomaly detector.
Therefore, qt also fluctuates on an hourly scale, and an optimal qt should be determined with awell-balanced number of past traces (e.g. about 1.5 h). We note that q on a minute scale cannot be
discussed, because a few minutes of traffic have too little information to detect statistical outliers.
3.7 Performance comparison between 15 min and 24 h learning

Finally, we study the difference between 15 min and 24 h learning. Since the datasets for both types oflearning have overlap traces starting from 14:00 on the dates that 24 h measurement were conducted,
these two types can be compared by using past t traces since 14:00 on these dates. Figure 13 compares
the two types of learning with three microscopic (daily and hourly) examples: (a) 3 March 2006; (b) 10
January 2007, and (c) 19 March 2008. All the x-axes are the learning periods t (t = 1 means 1 day for
15 min learning and 15 min for 24 h learning), the y-axes of the upper figures plot the values for qt,
those of the middle figures show the number of detected Anomalous and Normal events, and those of
the lower figures highlight the detection performance a(qt).
The upper figures show two similar lines of 15 min and 24 h learning on the same date, though thelines of 15 min learning vary among the three dates (also for 24 h learning). A possible reason for thesesimilar lines is that the characteristics of Internet traffic anomalies fluctuate on at least an hourly scale,so the results for 15 min and 24 h learning do not present significant differences. Also, the learning
method can be applied on both a daily scale and an hourly scale. Additionally, the middle figuresindicate that the number of events detected with 15 min learning is higher than that with 24 h learningfor (b) and (c), so 15 min learning can macroscopically (roughly) capture changes in anomalies.
However, 15 min learning cannot detect any Anomalous events in case (a). On the other hand, the lower
figures also reflect the optimal t of t = 3 for 15 min learning, and t = 6,7, and 8 for 24 h learning,
considering the balance between the number of detected events and the detection performance. 24 hlearning provides better performance than 15 min learning on average, so 24 h learning can capture
microscopic (subtle) changes in specific anomalies.
Here we present an example of events detected by q3 for 15 min learning and q8 for 24 h learning on
19 March 2008. For upcoming traffic, 15 min learning detected three Anomalous (two continuous andone spiky) and six Normal (one continuous and five spiky) events, whereas 24 h learning found one
Anomalous (spiky) and one Normal (continuous) event. For learning traffic, 15 min learning extracted
six Anomalous (four continuous and two spiky) and 14 Normal (12 continuous and two spiky) events,
while 24 h learning uncovered six Anomalous (six spiky) and eight Normal (eight continuous) events.
The detector with 15 min learning was tuned to detect continuous Anomalous events, because thosekinds of events were dominant in the learning traces. On the other hand, the detector with 24 h learning
was tuned to find spiky Anomalous events due to the dominance of spiky anomalies in the learning
data. Hence the learning method could capture the typical behavior of Anomalous events.
Therefore, the characteristics of 15 min learning and 24 h learning are similar, so the parameter tuning
method can be applied to both daily and hourly scales.
4. DISCUSSION
4.1 Trends in traffic usage and changes in optimal parameter

The MAWI link has been upgraded twice and the application breakdown is evolving (Figure 1), butchanges in optimal parameter ( θ 0opt ) do not follow the upgrade or evolution, unlike other observations
Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

Threshold q t

1000

3.5
3
2.5
2
1.5
1
0.5
0
8

10

12

100

1000

12
0

2

2

2

8

10

6

6

10

8

10

15-min24-hour8

15-min Normal
15-min Anomalous
24-hour Normal
24-hour Anomalous

6

Learning period t

4

4

4

15-min24-hour(b) 2007-01-10 14:00

12

12

12

0

0.2

0.4

0.6

0.8

1

1

10

100

1000

3.5
3
2.5
2
1.5
1
0.5
0

0

0

0

2

2

2

8

10

6

6

10

8

10

15-min24-hour8

15-min Normal
15-min Anomalous
24-hour Normal
24-hour Anomalous

6

Learning period t

4

4

4

15-min24-hour(c) 2008-03-19 14:00

12

12

12

Figure 13. 15 min versus 24 h learning. t = 1 represents one trace (1 day for 15 min learning and 0.25 h for 24 h learning).
Characteristics of 15 min and 24 h learning are similar on a certain date, though the lines of 15 min learning vary among the threedates (also for 24 h learning). Thus the parameter-tuning method can be applied to both daily and hourly scales, and it isfavorable to macroscopically (e.g. yearly) update the appropriate t

Learning period t

10

0
8

0
6

0.05

0.05

4

0.1

0.1

2

0.2
0.15

0.25

0
0.3

0

0.2

0

10

15-min24-hour

8

12

0.15

0.25

0.3

6

15-min Normal
15-min Anomalous
24-hour Normal
24-hour Anomalous

6

1

4

4

1

2

2

3.5
3
2.5
2
1.5
1
0.5
0

10

0

0

15-min24-hour(a) 2006-03-03 14:00

10

100

# of detected
eventsCopyright © 2010 John Wiley & Sons, Ltd.

Performance310
Y. HIMURA ET AL.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

(a) Autocorrelation

0.8

365 days

105

1

Power

Autocorrelation

EVALUATION OF AUTOMATIC PARAMETER TUNING

0.6
0.4
0.2

10

4

10

3

311

30 days 7 days 2 days(b) Power spectrum

0

-0.2
0

10

20

30

40

Lag [days]

50

102

1

10

100

1000

Frequency

Figure 14. Frequency analysis of changes in q0 of 15 min learning for 18 Mbps link (related to
Figure 6(a)). Changes in q0 have no strong frequency, i.e. there is no typical periodicity in q0

in the 3G network [14]. Since threshold qa indicates the degree of normalized deviation from referential
statistics, the changes in θαopt should be affected by anomalies changing day by day. This explanation
can be supported by the trends in referential behavior (unnormalized average a and b) shown in
Himura et al. [22]. The average values of a and b evolve according to traffic breakdown and linkupgrades.

4.2 High degree of variability in optimal parameter

Our results illustrate the importance of dynamic parameter tuning in statistical methods for detecting
anomalies so that they can be deployed in the real Internet. An inappropriate parameter significantly
degrades detection performance, because the performance is not constant relative to the value of theparameter. In addition, even if we set an optimal parameter at a certain time, we cannot use the samevalue consistently, because the optimal parameter is not invariable, as shown in Figures 5, 6, and 11.
This feature is not specific to our method. Since Internet traffic includes the trade-off, other methods
are also likely to require parameter tuning at daily and/or hourly levels so that they can follow themacroscopic behavior of network anomalies. Also, our results show that supervised learning-based
anomaly detectors must consider their training dataset (e.g. the amount of traces).

4.3 Typical timescale of anomalous traffic

The comparison between 15 min and 24 h learning (Figure 13) points out the influence of the numberof events on parameter learning, so the microscopic trends in anomalous traffic on hourly and daily
scales are weak. Also, the weakness of the trends in anomalous traffic can be confirmed by the highlyvariable q0 (Figure 5(a)) and the nonexistence of periodicity of q0 (Figure 14). On the other hand,
Figure 5(b) plots the transition in typical q0 for each month, so fluctuating q0 should form macroscopically standard anomalous behavior on a large scale (e.g. monthly levels), but higher t cannot capture
this trend because it is affected by significant events. Consequently, the trends of anomalous traffic are
weak on each timescale from the viewpoint of parameter learning, and the number of events andexistence of significant events have stronger influence on determining optimal parameters.

4.4 Practical use of parameter learning

To use parameter learning in real situations, one can predict an optimal threshold for upcoming traffic
by evaluating the detection performance of the past t traces before detecting anomalies in upcoming
traffic. The t can be set to 3 if one captures snapshots of a certain time on each day, and can be set toaround 1.5 h if one measures consecutive traces. Also, 15 min and 24 h learning can be combined to
Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

312

Y. HIMURA ET AL.

predict an optimal threshold, and this prediction will be more robust in detecting anomalies, because
the combination of the two types of learning considers both subtle and rough changes in anomalous
behavior of Internet traffic.
4.5 Advantage of using multi-scale gamma model

Figures 5, 6, and 11 indicate that the ideal parameter q0 is quite scattered, so that the macroscopic
behavior of the anomalous traffic exhibits no typical patterns. In addition, since a determines the shapeof the histogram for the number of packets on a certain timescale, the multi-scale gamma model canfollow the fluctuating traffic patterns; otherwise qa would be constant. Also, Figures 8 and 12 indicate
the efficiency of the detection algorithm, as previously discussed. Therefore, the anomaly detector basedon the multi-scale gamma model is a promising approach.
4.6 Events of strong effect on parameter prediction

Figures 6, 7, 8, and 11 suggest that parameter learning is strongly affected by significant traces. Sucha trace provides high performance a(q) for a certain q, plausibly because of high number of detected
Anomalous events with higher thresholds, etc. One way to avoid the influence of specific data is to usetime series forecasting methods, e.g. to impose moving weights on the past data, while another way
is to adopt a median value of qt among ideal parameters q0 of each of past t traces. We will enumeratepossible learning methods and evaluate them in the future.
4.7 Formal expression of determining appropriate learning period t

In this paper we selected appropriate t by balancing the detection performance a(qt) and the numberof detected Attack events. Since the number of detected events can be interpreted as the fraction of
undetected (missed) Attack events over total Attack events b(qt), one way to formulate the balance is1with w ∈ [0.1]. The weight w
to use weighted harmonic mean between a(qt) and b(qt):1
1
w + (1 − w )αbis a parameter to be determined manually according to whether a(qt) (or b(qt)) should be focused or not,and we can computationally obtain an appropriate t maximizing the harmonic average.

5. CONCLUSION
We have discussed automatic and dynamic parameter tuning (defined as parameter learning) for astatistics-based anomaly detector. The main idea underlying parameter learning was that we predicted
an appropriate parameter for upcoming traffic by considering the results of detection over the past
several traffic traces. We assessed this learning method by evaluating a statistical anomaly detection
method with real traffic traces measured at a trans-Pacific link over 9 years (15 min from 14:00 JST every
day and 24 h for some dates) with pseudo ground truth generator validated by BLINC. We also
analyzed the predictability of the ideal parameter with respect to periodicity and a random process.
Our main findings were as follows. (1) The ideal parameter fluctuates daily. (2) Parameter learning witha longer t is affected by significant data included in the period, and the appropriate t is about three
traces (days) for learning with daily 15 min traces and around 1.5 h for that with 24 h traces. (3) The
performance degradation caused by introducing parameter learning is 17% with t = 3 for the daily
15 min traces. (4) Even though the changes in the ideal parameter had no periodicity, it could bemodeled as a random process followed by a normal distribution. Our contribution was to clarify andquantify the importance of setting dynamic parameters for statistical methods of detecting anomalies
in network traffic in the real world; i.e. it is ineffective to use fixed values for parameters. In future
Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

Copyright © 2010 John Wiley & Sons, Ltd.

A kind of scanner

Strange TCP traffic

AttackAttackTable 2. Heuristics to identify Attack events

30
49
1
58
571

30
3
71
299

flood
709

191
26

scan
620

Attack1
3

strange
4

15
16
21
2071

4414
1

OK
web srv
6538

10
8
38
158

5243

web cli
5457

Warning

34
24
17
516

2
52

ssh
645

78
4

725

dns
807

4
587
1
34

6

mail
632

Special

68
3
4
1
7
232
46

p2p
361

53
2
1
25
45

3

ftp
129

6
119

4

34
7

other
170

2
3
105

3

proxy
113

504
13
198
46
170
1 036
1295

Unknown
unkn
3262

If SYN flagged packets account for over 20% of all packets sent by a host, then thehost is regarded as a ‘SYN attacker’. If the attacker targets more than 100 hosts,
then the attacker is a scanner, else a SYN flooding attacker
If ICMP packets account for more than 20% of traffic, then the sender host is a ‘ping
attacker’. If the attacker targets more than 50 hosts, then the attacker is recognized
as a ping scanner, else ping flooding attacker
If a host targets more than 50 destination hosts, and if the 10th dominant host-to-hosttraffic consists of fewer than 5 packets, then the source host is a ‘scanner’
If over 30% of traffic is composed of TCP packets that do not include SYN or ACK
flag (e.g. RST only), the sender host is an ‘unusual traffic generator’

Table 3. Validation of classification heuristics with BLINC (row: our heuristics; and column: BLINC). Our heuristics can coverAttack events identified by BLINC, whereas BLINC can reduce Unknown events

SCAN
WEB
CHAT
FTP
DNS
MAIL
P2P
UNKN

193
10 383
24
255
920
819
1 587
5 266

Ping scan/flooding

AttackBLINC

SYN scan/flooding

AttackExample of heuristics

Heuristics based on port, flags, and communication pattern

Explanation

Category

EVALUATION OF AUTOMATIC PARAMETER TUNING
313

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

314

Y. HIMURA ET AL.

work, we intend to extend the evaluation of parameter learning to other learning schemes and otheranomaly detection methods with multiple parameters, by using traffic traces collected on other links
as well as improving the classification framework.

APPENDIX A: HEURISTICS TO IDENTIFY ATTACK EVENTS
Table 2 lists the rules to identify Attack events. The set of rules is derived from our best knowledge
based on port, flag, and communication pattern of traffic, and used in creating pseudo ground truth.
The heuristics basically focus on scanning activity, flooding attack, and strange use of TCP traffic.

APPENDIX B: VALIDATION OF CLASSIFICATION HEURISTICS WITH BLINC
We compare our heuristics with Reverse BLINC used in Kim et al. [21], whose parameters are set to thedefault values. Since BLINC is a flow-level traffic classifier, we converted its outputs into host level byfinding the most dominant category in a host (except for unknown). Table 3 displays the comparison
by using the hosts (events) observed in traces of every 15th from January to December 2008, and thetable shows the following:• Attack events: since BLINC only classified host scans in terms of harmful traffic, there areunclassified events such as SYN flooding attacks and ICMP traffic. Also, our classification results
include most of the scan labeled by BLINC (191 of 193).
• Unknown events: BLINC outperforms our heuristics in terms of unknown traffic. Since mostevents unclassified by our heuristics are P2P and none of them is an attack, BLINC is useful in
reducing the fraction of unknown events.
In summary, our Attack heuristics outperform the attack detection part of BLINC rules. BLINC canbe used in reducing the amount of unknown events, which are mainly P2P traffic.

ACKNOWLEDGEMENTS
We wish to thank Patrice Abry, Pierre Borgnat, and Guillaume Dewaele of École Normale Supérieurede Lyon, and Romain Fontugne of the Graduate University of Advanced Studies for their invaluableadvice. Also, we are greatly thankful to Hyun-chul Kim of Seoul National University, Dhiman Barmanof Juniper Networks, and Thomas Karagiannis of Microsoft Research for allowing us to use theirimplementation of BLINC. This work was partially supported by the Strategic International Cooperative Program of CNRS and JST.

REFERENCES
1. Roesch M. Snort: lightweight intrusion detection for networks. In USENIX LISA 99, November 1999; 229–238.
2. Brutlag J. Aberrant behavior detection in time series for network monitoring. In USENIX LISA 00, December
2000; 139–146.
3. Barford P, Kline J, Plonka D, Ron A. A signal analysis of network traffic anomalies. In ACM IMW 02, November
2002; 71–82.
4. Krishnamurty B, Sen S, Zhang Y, Chen Y. Sketch-based change detection: methods evaluation and applications.
In ACM IMC 03, October 2003; 234–247.
5. Lakhina A, Crovella M, Diot C. Diagnosing network-wide traffic anomalies. In ACM SIGCOMM 04, August
2004; 219–230.
Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

EVALUATION OF AUTOMATIC PARAMETER TUNING315

6. Soule A, Salamatian K, Taft N. Combining filtering and statistical methods for anomaly detection. In ACM IMC
05, October 2005; 331–344.
7. Gu Y, McCallum A, Towsley D. Detecting anomalies in network traffic using maximum entropy estimation. In
ACM IMC 05, October 2005; 345–350.
8. Kim Y, Lau WC, Chuah MC, Chao HJ. PacketScore: a statistics-based packet filtering scheme against
distributed denial-of-service. IEEE Transactions on Dependable and Secure Computing 2006; 3(2): 141–155.
9. Dewaele G, Fukuda K, Borgnat P, Abry P, Cho K. Extracting hidden anomalies using Sketch and non
Gaussian multiresolution statistical detection procedure. In ACM SIGCOMM 07: LSAD Workshop, August 2007;
145–152.
10. Stoeklin MP, Boudec JYL, Kind A. A two-layered anomaly detection technique based on multi-modal flow
behavior models. In PAM 2008, April 2008; 212–221.
11. Brauckhoff D, Wagner A, Dimitropoulos X, Salamatian K. Anomaly extraction in backbone networks using
association rules. In ACM IMC 09, November 2009; 28–34.
12. Ringberg H, Soule A, Rexford J, Diot C. Sensitivity of PCA for traffic anomaly detection. In ACM SIGMETRICS
2007, June 2007; 109–120.
13. Himura Y, Fukuda K, Cho K, Esaki H. An automatic and dynamic parameter tuning of a statistics-based
anomaly detection algorithm. In IEEE ICC 2009, June 2009; 6.
14. D Alconzo A, Coluccia A, Ricciato F, Maierhofer PR. A distribution-based approach to anomaly detection for3G mobile networks. In IEEE GLOBECOM 2009, November–December 2009; 8.
15. Karagiannis T, Papagiannaki K, Faloutsos M. BLINC: multilevel traffic classification in the dark. ACM
SIGCOMM 05, August 2005; 229–240.
16. Scherre A, Larrieu N, Owezarski P, Borgnat P, Abry P. Non-Gaussian and long memory statistical characterisations for Internet traffic with anomalies. IEEE Transactions on Dependable and Secure Computing 2007; 4(1):56–70.
17. Cho K, Mitsuya K, Kato A. Traffic data repository at the WIDE Project. In USENIX 2000 FREENIX Track, June
2000; 263–270.
18. Claffy KC. A day in the life of the Internet: proposed community-wide experiment. In ACM SIGCOMM
Computer Communication Review 2006; 36(2): 39–40.
19. Borgnat P, Dewaele G, Fukuda K, Abry P, Cho K. Seven years and one day: sketching the evolution of Internet
traffic. In IEEE INFOCOM 2009, April 2009; 711–719.
20. Fontugne R, Himura Y, Fukuda K. Evaluation of anomaly detection method based on pattern recognition.
IEICE Transactions on Communications 2010; E93-B(2): 328–335.
21. Kim H, Claffy KC, Fomenkov M, Barman D, Lee MFKY. Internet traffic classification demystified: myths,
caveats, and the best practices. In ACM CoNEXT 2008, December 2008; 12.
22. Himura Y, Fukuda K, Cho K, Esaki H. Quantifying host-based application traffic with multi-scale gamma
model. In PAM2009 Student Workshop, April 2009; 2. [Online]. Available: http://pam2009.kaist.ac.kr/
workshop_paper/yourconf1-paper12.pdf [11 July 2010].

AUTHORS’ BIOGRAPHIESYosuke Himura is a master course student in Department of Information and Communication Engineering,
Graduate School of Information Science and Technology, the University of Tokyo. His research interests are Internet
traffic analysis and Internet security.
Kensuke Fukuda is an associate professor at the National Institute of Informatics (NII) and is a researcher,
PRESTO, JST. He received his Ph.D degree in computer science from Keio University at 1999. He worked in NTT
laboratories from 1999 to 2005, and joined NII in 2006. His current research interests are Internet traffic
measurement and analysis, intelligent network control architectures, and the scientific aspects of networks. In 2002,
he was a visiting scholar at Boston University.
Kenjiro Cho is Deputy Research Director at Internet Initiative Japan, Inc. He received the B.S. degree in electronicengineering from Kobe University, the M.Eng. degree in computer science from Cornell University, and the Ph.D.
degree in media and governance from Keio University. He was with Sony Computer Science Laboratories, Inc.
during 1996–2004, and is with IIJ since 2004. He is also an adjunct professor at Japan Advanced Institute of Science
Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem

316

Y. HIMURA ET AL.

and Technology, and a board member of the WIDE project. His current research interests include traffic
measurement and management, and operating system support for networking.
Hiroshi Esaki received Ph.D from University of Tokyo, Japan, in 1998. In 1987, he joined Research andDevelopment Center, Toshiba Corporation. From 1990 to 1991, he has been at Applied Research Laboratory of
Bellcore Inc., New Jersey, as a residential researcher. From 1994 to 1996, he has been at Center for Telecommunication Research of Columbia University in New York. From 1998, he has served as a professor at the Universityof Tokyo, and as a board member of WIDE Project. Currently, he is executive director of IPv6 promotion council,
vice president of JPNIC, IPv6 Forum Fellow, director of WIDE Project and Emeritus Board of Trustee for InternetSociety.

Copyright © 2010 John Wiley & Sons, Ltd.

Int. J. Network Mgmt 2010; 20: 295–316
DOI: 10.1002/nem