1284

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 21, NO. 4, AUGUST 2013

Synoptic Graphlet: Bridging the Gap Between
Supervised and Unsupervised Profilingof Host-Level Network Traffic
Yosuke Himura, Kensuke Fukuda, Member, IEEE, Kenjiro Cho, Member, IEEE, Pierre Borgnat, Member, IEEE,
Patrice Abry, Fellow, IEEE, and Hiroshi Esaki, Member, IEEE

Abstract—End-host profiling by analyzing network traffic
comes out as a major stake in traffic engineering. Graphlet constitutes an efficient and common framework for interpreting host
behaviors, which essentially consists of a visual representation asa graph. However, graphlet analyses face the issues of choosing
between supervised and unsupervised approaches. The former cananalyze a priori defined behaviors but is blind to undefined classes,
while the latter can discover new behaviors at the cost of difficult
a posteriori interpretation. This paper aims at bridging the gap
between the two. First, to handle unknown classes, unsupervised
clustering is originally revisited by extracting a set of graphlet-inspired attributes for each host. Second, to recover interpretability
for each resulting cluster, a synoptic graphlet, defined as a visualgraphlet obtained by mapping from a cluster, is newly developed.
Comparisons against supervised graphlet-based, port-based,
and payload-based classifiers with two datasets demonstrate theeffectiveness of the unsupervised clustering of graphlets andthe relevance of the a posteriori interpretation through synoptic
graphlets. This development is further complemented by studying
evolutionary tree of synoptic graphlets, which quantifies the growthof graphlets when increasing the number of inspected packets per
host.
Index Terms—Internet traffic analysis, microscopic graphevolution, unsupervised host profiling, visualization.

I. INTRODUCTIONAN ESSENTIAL task in network traffic engineering stems
from host-level traffic analyses, where the behavior of ahost is characterized based on traffic (i.e., packet sequence) generated from the host. Host-level traffic analyses enable to findusers of specific applications for the purpose of traffic control, toidentify malicious or victim hosts for security, and to understandthe trend of network usage for network design and management.
Flow analysis, which also constitutes an important networking
Manuscript received December 22, 2011; revised August 16, 2012; accepted
October 01, 2012; approved by IEEE/ACM TRANSACTIONS ON NETWORKING
Editor R. Teixeira. Date of publication November 30, 2012; date of current version August 14, 2013. This work was supported by CNRS/JSPS Grants “Benchmarking and statistical analysis tools for modern Internet and sensor network
traffics,” 2010 and 2012.
Y. Himura and H. Esaki are with the University of Tokyo, Tokyo 113-0033,
Japan (e-mail: him@hongo.wide.ad.jp; hiroshi@wide.ad.jp).
K. Fukuda is with the National Institute of Informatics and PRESTO, JST,Tokyo 101-0003, Japan (e-mail: kensuke@nii.ac.jp).
K. Cho is with the Internet Initiative Japan (IIJ), Tokyo 101-0051, Japan, andalso with Keio University, Tokyo 108-0073, Japan (e-mail: kjc@wide.ad.jp).
P. Abry and P. Borgnat are with the CNRS and École Normale Supérieurede Lyon (ENS de Lyon), Laboratoire de Physique, Lyon 69364, France (e-mail:patrice.abry@ens-lyon.fr; Pierre.Borgnat@ens-lyon.fr).
Color versions of one or more of the figures in this paper are available online
at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TNET.2012.2226603

Fig. 1. Examples of graphlets. Traffic from a single source host is represented
as a graph connecting attributes such as proto, srcPort, dstPort, and dstIP.
(a) Host scan for a destination port. (b) Peer to peer.

stake, can be fruitfully complemented by host profiling (e.g., bybreaking down host behaviors into flow characteristics).
Numerous attempts have been made to develop statisticalmethods for host profiling. Such methods aim at overcoming
packet encryption, encapsulation, use of dynamic ports, or
dataset without payload—situations that impair the classicalapproaches relying on payload inspection [17], [24], [26] andport-based rules [4]. The most recently proposed ones are
based on heuristic rules [15], statistical classification procedures [18], [22], [27], Google database [28], or macroscopic
graph structure [10], [11], [13], [30].
In particular, an effective yet heuristic approach to hostprofiling is based on graphlets [14], [15], [19]. A graphlet
is a detailed description of host communication patterns as
a graph, as illustrated in Fig. 1. For each flow, the 5-tuple
defining it (proto, srcIP, dstIP, srcPort, dstPort) gives a set, and the communication pattern ofof attributesa host is the union, for all flows, of edges connecting nodes
associated to flow’s attributes. This leads to diverse visualshapes of graphlets depending on the host’s flows. The graphlet
representation facilitates the intuitive analysis of differences
and resemblances among host behaviors, whereas conventional
approaches directly handle numerical values of statisticalfeatures, which are difficult to interpret.
However, as for any host-profiling approach, the use ofgraphlets faces the classical issue of choosing supervised
versus unsupervised procedures. Supervised approaches rely
on a priori determined classes or models of graphlets [15],predefined by human experts in a necessarily limited number,and these approaches cannot substantially classify new or unknown host behaviors. Unsupervised approaches are adaptive
insofar as the data directly define the output classes of graphlets
and can discover behaviors never observed before. These
approaches, however, potentially produce clusters composed of1063-6692 © 2012 IEEEHIMURA et al.: SYNOPTIC GRAPHLETa large number of numerical features that cannot receive easy
meaningful or useful interpretation.
This paper aims at bridging the gap between the two types
of approaches. The main idea for this is the combination of
two techniques: To avoid the limitation of supervised approach,
we use an unsupervised clustering of graphlets that is able tocapture previously unknown classes; to ease the difficulties of
unsupervised approach, the resulting clusters are revisualized
into synoptic graphlets that allow us to interpret the clusters
obtained. Our approach is evaluated with two large datasets oftraffic collected on two different links (Section III). This paper
is organized along three contributions.
First, the classical problem of supervised classification is revisited (Section IV). This investigation comprises two aspects:
a list of graphlet-based features is proposed to quantify in a
relevant way the visual graphlet shape associated with each
host; an unsupervised clustering method is applied to thesefeatures to yield classification in terms of graphlet shapes.
Comparisons against a supervised graphlet-based classifier(BLINC [15]), a port-based one, and a payload-based one
allow us to check that most clusters match well-known host
behaviors. This result shows that our method makes it possible
to discover unknown graphlets, which avoids the problem facedby supervised approaches.
Second, the issue of automatically providing interpretation of the output of the unsupervised clustering is addressed(Section V). We solve the inverse problem of reconstructing
a synoptic graphlet, defined as a graphlet inferred from eachobtained cluster, by using an original mapping of the cluster
attributes (cluster centroid) into a graphlet. Our developmentof synoptic graphlets shows that an interpretable meaning canbe associated automatically to each cluster without any a priori
expertise. The effectiveness of synoptic graphlets, which successfully provide interpretability for unsupervised approaches
as shown in this paper, ends up in bridging the gap between
supervised and unsupervised methods.
Third, the nature of host behavior is further studied via synoptic graphlets (Section VI). The use of synoptic graphlets is
expanded to creating an evolutionary tree, which explores thevisually intuitive growth of a set of synoptic graphlets as a function of the number of inspected packets per host. This study
is useful in integrating host-level traffic characteristics of different in an interpretable manner, and in quantifying the orderof magnitude
beyond which further increase does not leadto substantially more relevant host profiling, i.e., how many
packets we need to profile hosts.
II. PRELIMINARIES
Before turning to the method itself and the datasets used in thenext sections, we recall the definition of graphlets in the context
of Internet traffic and discuss related work. Then, we propose
an overview of our approach.
A. Graphlet
A graphlet is defined as a graph having the following characteristics in the context of network communication: 1) The
graph is composed of several columnsof nodes,where each column represents one attribute of packets or flows;

12852) a node (vertex) in a column is a unique instance of the attribute; and 3) there is an edge between two nodes of neighboring columns if at least one packet/flow has the two corresponding attributes. Columns of a graphlet are usually related toflow attributes (5-tuple): proto (protocol number), srcIP (source
IP address), dstIP (destination IP address), srcPort (source port
number), and dstPort (destination port number), which are specified in the header field of every packet.
Fig. 1 illustrates two manually annotated examples ofgraphlets drawn withpackets per source host.
Fig. 1(a) shows that the source host, which is represented as the
single node in srcIP column, sends packets to a specific destination port of many destination hosts (almost one packet perflow); This suggests that the source host is a malicious scanner
aiming to find hosts running a vulnerable application corresponding to the port. Fig. 1(b) displays a host communicatingwith several hosts without any specific source/destination port,
and hence this host is a peer-to-peer user (not server or client).
As shown in these examples, a strong merit of graphlets isthe visual interpretability of host characteristics as compared
to examining a large number of raw packet traces or directly
handling a set of numerical statistics.
We draw a graphlet from host-level traffic. Here, host-leveltraffic is defined as the sequence of packets sent from thehost; Headers in those packets contain source IP addresses
equivalent to the host’s address. Note that this measurement
does not necessarily capture initiation of communication (e.g.,
TCP handshake). Each graphlet is drawn from a certain numberof observed packets
sent from each host. The graphlet
we use is composed of six columns, which represent srcIP-proto-srcPort-dstPort-dstIP-srcPort.1 The orderof columns is different from the original definition [15].
We consider that srcIP-srcPort-dstPort-dstIP should be morecomprehensive because it clarifies the activity of computer
processes inside end-hosts (IP-Port pairs) and network-wide
interprocess communication among hosts (srcPort-dstPort
pairs). We place srcPort at the right side again to capture therelation between dstIP and srcPort (inspired by [14]). Since wedraw one graphlet per source host, there is only one point in theleft column (srcIP).
B. Related Work and Open Issues
Here, the standpoints of the graphlet-based works and of thispaper are presented in the context of network traffic classification conducted over the course of a decade.
Many statistics-based methods for traffic analyses have been
proposed to classify flows and host characteristics by meansof supervised and unsupervised methods. These studies havemade use of various supervised machine learning methods suchas nearest neighbors [8], [16], [20], Bayesian statistics-based
techniques [16], [20], [23], [25], decision tree [16], [20], [25],Support Vector Machine (SVM) [16], [20], or even natural
language processing on Google search results [28]. The others
have leveraged unsupervised ones including K-means clustering [1], [7], [18] or hierarchical clustering [18]. Both theapproaches have been applied to traffic features from various
aspects—packet sizes only [1], [8], combinations of packet
1We define “pseudo” source and destination ports for ICMP to be

in order to consistently draw graphlets.

1286

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 21, NO. 4, AUGUST 2013

Fig. 2. Overview of our approach.

sizes, flow sizes, interarrival times, flow durations, etc. [7],[20], [23], [25], and/or entropy regarding the number of related hosts/ports [18], [30]. Those statistics-based methods
are capable of overcoming packet encryption, encapsulation,use of dynamic ports, or dataset without payload, which are
limitations on conventional approaches relying on payload
inspection [17], [24], [26] and port-based rules [4].
Several recent studies particularly focused on large-scale
host-to-host connections [10], [11], [13], [22], [27], [29],the use of which promisingly enables to visualize how hosts
communicate with one another and enables to find groups ofhosts communicating with each other. These works leverage
existing graph-based analytical capabilities such as feature extraction regarding complex networks [10], community mining
techniques [11], or block identification in communication(adjacency) matrix [13], [29].
Different from those previous works, the approach described here focuses on graphlets—detailed aspects of host
behaviors including the usage of protocols and source/destination ports. The use of graphlets has been motivated bytheir visual interpretability (as shown before) and has been
conducted in a few works. For example, Karagiannis et al.
perform supervised classification of flows based on graphletmodels predetermined by human experts [15]. Other works
characterize graphlet-based host behaviors in unsupervisedmanners as follows. Karagiannis et al. discuss in-degrees andout-degrees of nodes and average degrees of graphlets in [14]and focus on manual finding of typical graphlets as well as ontime transition of those features; In [6], Dewaele et al. classify
hosts, making use of various features (some of them inspiredby graphlets) applied to an unsupervised clustering technique.
To overcome the various limitations of supervised/unsupervised approaches that were discussed previously, and in contrast
to previous works, this paper aims at bridging the gap between
the two analytical approaches on graphlets by proposing a newframework for graphlet manipulation.
C. Overview of Our Approach
The three contributions of this work are: 1) the automationof finding typical graphlets via unsupervised clustering in aninterpretable manner; 2) a method to revisualize graphlets fromclustering results; and 3) an analysis on evolution of typicalgraphlet shapes while increasing the number of packets pergraphlet, which is complementary to analyses on time-transition of graphlet features. Each contribution is an important stepof our method. Steps (1) and (2) are depicted in Fig. 2, andstep (3) is detailed in Section VI. Our method is organized asfollows.
As a preprocessing step, aggregated traffic traces are firstcomputed [Fig. 2(a)]. The traffic is measured in a backbone link
and composed of packets sent from hundreds of thousands ofhosts (Section III). We identify per-host traffic [Fig. 2(b)] according to the source IP addresses specified in the packets anddraw graphlets from the first measured packets sent from eachhost [Fig. 2(c)].
Step (1): An unsupervised clustering over graphlets is conducted to find typical graphlets (Section IV). A numerical feature vector , which represents shape-based characteristics ofa graphlet, is extracted from the graphlet of packets sent fromhost . The set of feature vectors, representing a setof hosts, is used for hierarchical clustering to produce clustersof hosts[Fig. 2(d)]. Cluster consists of hosts thatare similar in terms of their feature vector in the feature space.
For each cluster, we obtain the components of a representative
feature vector , which will be converted to graphlets in the next
step.
Step (2): Resulting clusters are visualized to recover interpretability (Section V). Since unsupervised clustering
handles numerical features and thus loses visual informationof graphlets, we revisualize a representative graphlet associated with each cluster [Fig. 2(e)]. The reproduced graphlet,
called synoptic graphlet, is derived from the feature vectorof the centroid of a cluster. We develop an original method
to revisualize synoptic graphlets in a deterministic mannersince conventional probabilistic ways of graph rewiring are notsuitable for highly structured graphlets.
Step (3): Additionally, the evolutionary nature of synoptic
graphlets is studied (Section VI). The key observation is that
our knowledge of hosts may evolve asincreases from 1
to larger numbers. To study the evolution of the associatedsynoptic graphlets, we build an evolutionary tree of synoptic
graphlets that evolve from the single-line graphlet (the only
existing shape for) to the diversity of synoptic graphlets.
This evolutionary tree is obtained by combining the clusteringresults of increasing(detailed in Section VI). It provides
intuitive understanding of the divergences and convergences in
the growth of host characteristics as increases.

HIMURA et al.: SYNOPTIC GRAPHLET

III. DATASETSThis section first describes the two datasets used for the validation of the proposed method and, second, discusses how combining three different and classical traffic classifiers produces
surrogates for real traffic ground-truth.
A. Traffic Traces
We analyze traffic traces stored in the MAWI repository [3], [21] and traces measured at Keio University,
Tokyo, Japan (used in [16] as Keio-I and Keio-II). MAWI
traffic [3], [21] is measured on a transpacific IPv4 link between
the US and Japan for 15 min everyday. The public repository
removes packet payloads, while the private repository retains
payloads, up to the first 96 B. Results are reported here basedon 12 MAWI traces collected once a month (on the 14th) in
2008. Keio traces used here are those presented in [16] andmeasured for 30 min, for two different days in 2006, on abidirectional edge link in a campus of Keio University. Packet
payloads up to 96 B were also preserved. We first removed thepackets related to protocols other than TCP, UDP, and ICMP.
In the results reported below, we use the source hosts2
sending at least 1000 packets for MAWI trace (respectively,
100 packets for Keio trace). This choice balances the tradeoff
between: 1) having a lower reliability when hosts do not exchange enough packets, and 2) not keeping enough hosts when
the required number of packet is too high. It has been checkedthat this arbitrary choice is not crucial. Results (e.g., the evolution of the number of clusters) similar to those obtained with
were drawn with
, or
with
for MAWI traces, where denotes thenumber of packets sent by a host (observed in a trace). We willquantitatively evaluate the differences of results regarding the
choice of in the future.
Each of the 12 MAWI traces contains about 1700 analyzed
hosts, yielding approximately a number of analyzed hosts
in total for the 12 traces, and the two Keio traces contain about
hosts in total ( is the number of analyzed hosts). Those analyzed hosts for MAWI data account for
1.1% (19K out of 1.7M) regarding the number of hosts, 86%
regarding the number of packets (207M out of 239M), and 93%
regarding the number of bytes (1.43T out of 1.52T).
B. Pseudo Ground-Truth Generators
Traffic analysis methods generally have to be evaluated withdataset annotated from ground-truth. A crucial issue raised in
the recent literature, however, lies in designing a procedure toobtain ground-truth on actual traffic traces. Most research indeed has regarded ground-truth as the labels put by a single
payload-based packet classifier. However, a lot of packets arelabeled as unknown by payload classifiers (as exhibited in thispaper). Also, payload-based methods do not necessarily produce correct outputs. To improve the ground-truth coverage andaccuracy, we carefully create three sets of pseudo ground-truth
from different methods detailed here.
2It should also be meaningful to analyze destination hosts. With this analysis,for instance, we will be able to capture hosts receiving lots of attack packets. As afirst step, we selected to analyze source hosts because of the easier interpretationof results. Packets sent from a host can be well explained by the application of
the host, compared to packets received by a host.

12871) Reverse BLINC: BLINC was originally proposed in [15]and extended to Reverse BLINC in [16], which is now state-ofthe-art. BLINC profiles a pair of a source address and a port, andonce the pair is matched with one of the heuristic rules based on
the graphlet models, all pairs connected to that pair are classified. We used the default setting of Reverse BLINC as in [16].
BLINC’s classification framework is WWW, CHAT, DNS, FTP,
MAIL, P2P, SCAN, and UNKN (unknown). Since this classifier
reports classification results as flow records, we need to convert
them into a host-level database. For each source host, we collect a set of flows generated from the host and select the category(except for UNKN) that is the most frequent among the flows.
For example, if 10 flows from a host are classified into three
DNS, one WWW, and six UNKN, then the type of the host is
identified as DNS.
2) Port-Based Classifier: We use another classifier, which
was originally developed in [5] and also used in [2] and [9]. This
tool inspects a set of packets sent from a host, considering port
numbers, TCP flags, and the number of higher/lower source/
destination ports and destination addresses. The classification
categories are WWWS (Web server), WWWC (Web client),
SCAN, FLOOD (flooding attacker), DNS, MAIL, OTHERS,
and UNKN [9]. This tool reports host-level classification resultsby itself.
3) Payload Classifier: We also use the payload-based classifier developed in [16].3 This classifier inspects the payload
string of each packet by comparing it to its signature database.
The classification categories we select are WWW, DNS, MAIL,
FTP, SSH, P2P, STREAM, CHAT, FAILED (when the packets
have no payload), OTHERS (minor flows such as games, nntp,
smb, and snmp), and UNKN. Since this tool also generates outputs in the form of flow tables, we merge them into host-level
reports by the same means used to aggregate outputs from Reverse BLINC.
The hosts annotations given by the three classifiers of different perspectives are used to evaluate the unsupervised analysis on graphlets that is presented in Section IV.
IV. UNSUPERVISED GRAPHLET ANALYSIS
We detail the first step of the method, which is an unsupervised classifier for typical behaviors of hosts that does not rely
on predefined models. However, it will still allow us afterwards
to provide visual interpretation of the behaviors found.
A. Methodology for Unsupervised Graphlet Analysis
1) Extracting Shape-Based Features From Graphlets: We
first extract numerical feature values from graphlets because visual graphlets cannot be used directly as input to conventional
statistical methods (except for image processing). We choose
afterwards several types of features related to shapes. We notethe feature vector for the graphlet of host .
Notations on Graphlets: We denote the six attributes. In column , the(srcIP- -srcPort) as column
total number of nodes is , and nodes are. We
as the direction fromto, which is used todefine3In our preliminary experiment, we examined l7-filter [17] and found thatthe tool generated rather unreliable outputs because of loose payload signaturesthat are represented as regular expressions with a few bytes. Also, we found that
OpenDPI [24] produced mostly unknown reports because it uses strict rules.

1288

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 21, NO. 4, AUGUST 2013

TABLE IINOTATIONS FOR GRAPHLET CLUSTERING

Fig. 3. Shape-based features for a graphlet (i.e., behavior of a host).

TABLE INOTATIONS FOR GRAPHLET DESCRIPTION. AN ATTRIBUTE HAS
TWO DIFFERENT DEGREE DISTRIBUTIONS BASED ON DIRECTION(E.G.,IS SEPARATED INTOAND).
SEE SECTION II-A FOR DETAILS

define the in-degree and out-degree of nodes in column(or). The in-degree of node
is definedas, namely,is theon directionthat are connected to nodein
number of nodes in. The out-degree is similarly defined on directionas. As a consequence, nodeis characterized by.
the pair of the in-degree and out-degreeas
We define the array of in/out degrees for direction, whereis the number of nodes
gives the empirical distribution measured
in column .
from an observed graphlet. Table I summarizes these notations.
Feature Extraction: The proposed features are based on five
types of shape-related information, described formally as follows and visually in Fig. 3 (the relevance of the features is discussed later).
is the number of nodes in column. Note that1)
and.
it is equal to the size of arrays(six columns), whereis the indi2)
cator function, is the number of nodes that have degree 1(with). (10 directions)in directionis the average degree of3). (10 directions)direction
4)is the maximum degree. (10 directions)of direction, whereis,
5)(i.e.,
for the node having maximum degree in
Feature 4), its degree in the backward direction. If more than one node has the maximum degree for
Feature 4, the pair with the highest degree is selectedfrom among the candidates. A similar definition holds

for the reverse direction. (eight directions, since
the edge columns have degree for only one direction)
As a result, from the graphlet for host , we obtain a feature,,
vector,,of dimension of. We examine packet
traces or flow lists (input) to compute these features (output).
is omitted when not needed.
The index
Examples: Fig. 3 shows an example of features. For direction, there are four nodes
and three nodes of
one degree, and the average degree is 1.5. The second bottom node has the highest degree of three, and the degree of the node for the other direction isone.
Practical Meanings: Even though these features are selectedfrom the viewpoint of graphlet revisualization (Section V), a
few of them can also be interpreted as traffic characteristics ina practical sense.
is the number of unique instances of theflow attribute (e.g., the number of destination addresses).
andare respectively the average and maximum numberof unique flows of an instance of the attribute among all the
instances.
Relevance of Features: The selection of the five types of features is empirically motivated by two objectives: 1) the expectedability to obtain relevant clustering results because a few of thefeatures are already well known and well studied [6], and 2) theability to revisualize graphlets from the resulting clusters as explained in Section V. Also, the relative importance of the five
types of features is evaluated by a feature selection method in
Section IV-B.4. Macroscopic degree-related features such as betweenness, the assortativity coefficient, or eigenvalues are notused because graphlets are microscopic and highly structured.
We only use graph-based features to evaluate the interpretabilityof graphlet clustering results, although there are many otherwell-studied features such as TCP flag, packet size, and flow
size. Such features and ours are not exclusive but complementary. Using both types would enhance host profiling schemes.
2) Applying Graphlet Features to Unsupervised Clustering:
Here, we establish a method to find typical host behaviors interms of graphlet shapes. At a high-level view, a set of hosts
is grouped into clusters(clusters are
disjoint sets of the hosts). Table II lists the notations used forthe graphlet clustering.
Feature Normalization: Each feature value
from feature
is mapped onto a log space as. For
vectorthe features related to the ID of the transport protocol, the possible ranges of the values are adjusted to the other features (i.e.,addresses and ports) as follows:, whereis the number of analyzed packets to be drawn as a graphlet,
and the value 3 stems from the number of analyzed protocols(TCP, UDP, and ICMP). Hence, this type of feature is distributed

HIMURA et al.: SYNOPTIC GRAPHLET

into
as well as the other features for any .
This normalization onto the log space is motivated by our empirical observation that graphlet shapes can be logarithmicallywell characterized. For example, by inspecting graphlet shapeswith changing , we observed that difference in graphlet shapes
and
was intuitively similarly signifbetween
icant toand(rather thanand).
Unsupervised Clustering: Unsupervised clustering finds
groups of hosts that are similar in terms of feature valuesby analyzing thehosts. The hierarchical clustering [18] with Ward’s method is used, as it is known tooutperform other methods (e.g., single-linkage method). The
similarity between a pair of clusters
is defined as amerging cost:,withthe intra cluster variance in
Cluster , the Euclidean distance
between vectors
and , and the average feature vectorof all hosts in .
The distance-based threshold is used to separate clusters inclusthis feature space. The clustering produces a set ofters, depending only on (each host is included
in a single cluster only). The selection of is discussed in
Section IV-B.
Motivation for Distance-Based Threshold Instead of NumberBased One: The distance-based threshold is preferable compared to cluster-number-based thresholds (such as the one forthe K-means technique). This is because a consistent value ofcan be used for any , which mitigates the burden of parametertuning in analyses with several
as performed in Section VI.
Number-based thresholds would have to be appropriately tuned
through trial-and-error independently for each , as the numberof typical clusters for each cannot be known. The consistentuse of a single threshold over different
is empirically enabled by the normalization of the feature spaces as
because distance between two clusters of typical behaviors willremain mostly the same for different ’s. Instead, conventional
normalization into
would induce clusters with different
behaviors at larger
to be located closer, requiring to be
decreased.
Computational Load: We used hcluster methods in the amap
R-library. Approximately 1.5 GB memory was required forabout
instances ofdimensional
vectors. It took around 2.4 min with a 2.8-GHz Intel Core 2
Duo CPU with 4 GB memory. By performing the clusteringwith changing , we empirically confirmed that time and spacecomplexities were both.
B. Results: Finding Typical Patterns of Host Behaviors
1) Threshold Selection: The distance-based threshold
eventually determines the number of extracted clusters
according to a conventional tradeoff: A too high misses anumber of typical host behaviors, while a too low produces
redundant clusters (i.e., different clusters having similar compositions). By changing the value of , we inspected the listof synoptic graphlets (representative graphlets for resulting
clusters—details are defined in Section V) to identify whether
there are redundant clusters (having same shape of synoptic
graphlets) and whether there are new types of clusters thatcannot be found by large . We experimentally found thatthresholds that balance this tradeoff well arewith the1289

Fig. 4. Clustering threshold characterized by the dependency on the number
and the number of resulting clusters . (a) MAWI (of analyzed hosts). (b) Keio ().

MAWI traces (about
hosts) for, producing approximately
clusters, andwith theKeio traces (about
hosts) for, resulting
clusters. This tradeoff has been manually inspectedin
because it is quite difficult to computationally identify redundancy of clusters in terms of the shapes of graphlets, which are
one of our major focus and are enumerated in Section V.
Fig. 4 addresses the characteristics of by showing its relationship to the number of analyzed hosts
and the number
obtained from: (a) MAWI (for), andof clusters(b) Keio (for). Each set of analyzed hosts was selected from a random sample of the total number of original
hosts by changing the sampling rate. This figure suggests referential values of for each dataset to obtain a certain number ofclusters that balances the tradeoff well for any .
We note that this value of can be consistently used forother , and this is the reason why we do not directly use thenumber-based threshold. Since is based on the distance in thefeature space, we can compare the clustering outputs from various with a single consistent criteria. For example, smallermight lead to fewer numbers of clustering with regard to thefeature space. We confirmed that the value of is consistently
appropriate for other as shown in Section VI.
2) Typical Patterns of Host Behaviors: Table III shows theclustering result, withhosts atof MAWI
data, obtained from a comparison between the graphlet clustering and the three classifiers, i.e., Reverse BLINC (R-BLINC),
port-based classifier (Port), and payload-based classifier (Payload). This table displays the total number of hosts in each category, and each cell shows the number of hosts in the intersection between two classes of two classifiers. The first row of
the column headings is auto-generated labels. The second row
shows graphlets revisualized from clusters (Section V), and thebottom row is discussed in Section VI.
The sparseness of Table III indicates that each cluster mostly
corresponds to a type of host behavior. For instance,(containing 1427 hosts) is characterized by one typical category because most of the hosts are labeled as a category of each classifier: 1361 hosts as WEB by R-BLINC, 1351 hosts as WWWC
by Port, and 1316 hosts as WEB by Payload. In addition, theoverall similarity among the results from the three classifiers
cross-validates their effectiveness.
Clusters can show the typical host behaviors hidden in asingle category. WEB of R-BLINC, for example, is separated into a few clusters, reflecting the different behaviors of
Web hosts such as server, client, and P2P user
as suggested by1290

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 21, NO. 4, AUGUST 2013

TABLE III) COMPARED TO THREE CLASSIFIERS: REVERSE BLINC (R-BLINC), PORT-BASED CLASSIFIER (PORT),RESULTING CLUSTERS (MAWI WITH
AND PAYLOAD-BASED CLASSIFIER (PAYLOAD).
CLUSTERS ARE OBTAINED FROM THE ANALYZEDHOSTS
WITH THE SELECTED THRESHOLD

WWWS, WWWC, and P2P of Port, respectively. Moreover,
the WWWC (Web client) category of Port is clustered into a
few groups, and a plausible reason for this is that there are a
few typical behaviors of Web clients based on the usage of
Web such as large-file transfer, Web browsing, and ajax-based
activity. Also, the MAIL category of Port shows the behaviors
or bothof only server, only client
server and client. This observation can also be validated
by the other categories in the same cluster (e.g., P2P of Port in).
In particular, the ability to cluster unknown data is an advantage of the unsupervised approaches. Our clustering method
provides key information to profile hosts that R-BLINC classifies as UNKN4 by separating these hosts into different categories. For example,
separates 577 UNKNs of R-BLINC
from the total 5268 UNKNs of the classifier, and we can speculate that most of the 577 UNKNs are Web servers as most hosts
in the cluster are classified as Web servers (e.g.,
mainly consists of 348 WEB hosts labeled by R-BLINC other than the
577 UNKN hosts). The same is true for other UNKNs of thethree classifiers. Thus, the results of the classifiers and of ourapproach complement each other.
The effectiveness of a connection pattern-based approach canalso be complementarily improved by port- and payload-based, which contains theapproaches. One notable example ismost of UNKN hosts from R-BLINC. The port and payload
4We provide an example of UNKN hosts labeled by R-BLINC by examining, which consists of 1283 hosts. This cluster consists of mainly WEB
Clusterhosts as suggested by the three classifiers and the shape of synoptic graphlet.
As mentioned above, this synoptic graphlet can be mapped with BLINC’s original WEB graphlet, but this cluster contains 242 UNKN hosts classified by
R-BLINC. A plausible reason of the UNKN hosts is as follows. As one of theclassification rules, R-BLINC considers WEB hosts to follow “,” where is one of the 28 thresholds and its value with our default. The average and standard deviation of “”
setting isfor WEB hosts of R-BLINC inside(991 hosts), and arearefor UNKN hosts of R-BLINC inside(242 hosts), which does
not follow the above-mentioned R-BLINC’s classification rule for WEB.

classifiers both indicate that this cluster is mainly related to Web
server and client hosts. Actually, for the 2348 UNKN hosts in, our additional inspection found that 1150 hosts are classified
as Web server or client by both the port- and payload-based classifiers; This suggests that such cross-validation would reduce
the UNKN classification. Another example is that 1404 hosts
are identified asout of the 1612 WEB hosts for R-BLINC in
Web server or client as well by both the port- and payload-basedclassifiers, which indicates those hosts can be considered as
Web-related ones with high “plausibility.”
3) Intercluster Distance: We examined the distributionof clusters in the feature space by using the intercluster disdefined as, wheretance metric:is the centroid vector for. We define. The average and standard devia, with minimum
tion ofisand maximum
in the log space.
This means that the clusters are not uniformly distributed. Our
observation was that graphlets with low number of flows (e.g.,) have low
between each other, i.e., they
are densely distributed yet clustered due to the high numberof hosts, whereas highderives from graphlets with highnumber of flows (e.g.,,) having
similar shape but different typical number of flows.
4) Dominant Features: Here, we extend the discussion
by evaluating which out of thefeatures sigobtained clusters
nificantly contributed to the(Table III). For this evaluation, we use Fast Correlation-Based
Filter (FCBF) [16], [23], [31], a feature ranking and selection
method. We note that FCBF is used only for evaluating therelative contribution of the features to the clustering results andis not used for other parts of this paper.
FCBF selects the most effective and smallest set of featureswith respect to symmetric uncertainty (SU), which measures a form of correlation between two random variables:

HIMURA et al.: SYNOPTIC GRAPHLET

1291

TABLE IV
GRAPHLET FEATURES EVALUATED BY FCBF

Fig. 5. Synoptic graphlet. Graphlets obtained from hosts are clustered. In turn,each cluster is associated with a representative a posteriori synoptic graphlet.
The second row of Table III displays the synoptic graphlets revisualized fromthe actual clusters of hosts.

, whereis the information-theois the conditional entropy.
is theretical entropy andcorrelation between feature and clusters (SU against clusters),
andis that between features and (SU against features).
means that feature contributes to detecting one
A higheror more clusters, whereas a higher
indicates that joint useof features and is redundant. The method first removes irrel) and then excludes redundantevant features (having low
features (having higher
than).
Table IV lists the selected features showing their SU againstclusters for MAWI and Keio data:clusters for MAWI
with
, and
clusters for Keio with.
The features selected by FCBF are mainly(the numberof one-degree nodes), and this result suggests that this type offeature is more relevant and less redundant than the other features. Our interpretation is that
represents well a part of theand) in term of its shapegraphlet (i.e., the area between[e.g., a square (parallel line(s) between columns) or a triangle (aknot on a column)] and of its number of lines (i.e., visual complexity) (e.g., one line, a few lines, or many lines). These arebasic characteristics of the behavior of hosts, and the features
represent such characteristics better than the other features. Square shapes suchused here. Fig. 1 shows examples foras the area between
andin Fig. 1(b) occur when both thevalues ofandare high. On the other hand, triangle
andin the figure appear
shapes such as the area between
when one ofandis quite low (e.g., zero or one).
In particular,
between srcPort and dstPort contributes significantly to the clustering (first and second ranks in Table IV).
The relation between the ports represents the detailed behavior
of interprocess communication, which is an important aspect of
networking.
Even though other features also have discriminative power,such features are not part of the best set of features. For example,
we observe that for srcPort has, andof srcPort to dstPort hasfor MAWI data, indicating thatthese features are also useful. These features, however, were removed because of their high correlation with corresponding(e.g., a higher
will be provided by a higher ). It means thatthey have similar but weaker effect on the clustering comparedto. In other words,
is a good approximation of the shapesof graphlets. Even so, the other features are also necessary for
inferring synoptic graphlets (see Section V), and this is why wekeep all the features.
V. SYNOPTIC GRAPHLET
According to the unsupervised procedure described in
Section IV, graphlets associated with hosts are clustered with

Fig. 6. Procedure of revisualizing synoptic graphlets. A synoptic graphlet of acluster is reproduced from the graphlet features of the cluster centroid. Graphletfeatures are defined in Section IV-A.1 and Fig. 3.

respect to their feature vectors. Now, as an inverse problem
aiming at associating each cluster with a representative graphlet,
as sketched in Fig. 5, we propose a method to construct a synoptic graphlet from the feature vector representing a cluster.
A. Synoptic Graphlet: Construction
An original mapping from a feature vector into a set of bipartite graphs that constitute a graphlet is detailed here and illustrated in Fig. 6. This mapping is applied to the feature vector of
the cluster centroid. We will address the motivation to use synoptic graphlets instead of centroid-nearest graphlets at the endof this section.
Median Centroid: Recalling that the feature vector of hostwas defined as, let us define
as the centroid features of Cluster , wheretheth largest value ofamong
is selected as themedian feature.5 6
5As an example, for, if a cluster contains 100 hosts, the 50th largest value
is chosen as the median ( anddo not necessarily derive frominthe same host).
6We note that statistics other than the median could be chosen as a representative. We also tried to use average as representative, but average is not robust to
outlier features, and more critically taking the averages leads to decimal values,-dimensional mewhich are difficult to deal with for graph rewiring. The
dian features are converted from a log scale into a linear scale by inverting thenormalization function defined in Section IV-A.2.

1292

1) Considering a Graphlet as a Set of Bipartite Graphs: To
infer a graphlet from the centroid features of a cluster, we construct a graphlet as a set of bipartite graphs.
and
are a
disjoint set of a bipartite graph,andare another, and soon. In other words, we break down the graphlet reproduction
problem into: 1) reproducing the degree distributions of eachbipartite graph; 2) rewiring each bipartite graph based on the degree distributions; and 3) merging neighboring bipartite graphs.
2) Reproducing Degree Distributions: From a feature vector,
we build the degree distribution of direction(or), denoted aswhere is thetotal number of nodes as defined in Section IV-A.1 (“” isomitted fromandfor brevity). We first consider the
one-degree nodes as follows:. If
all the nodes have degree of one (i.e.,), this procedure
ends; otherwise, we rebuild the remaining part of the degree
distribution. We define the number of remaining nodes andthe remaining degrees as
and. The degrees are estimated as follows:,, where,. This process to distributewhich satisfies
the remaining degrees to the remaining nodes is based on theusual appearances of graphlets (e.g., some “knot” nodes, only
one, etc.).
3) Rewiring Bipartite Graphs: A bipartite graph is generated from
andcomputed above. Nodes ofhigher degrees ofare connected with those of lower degrees of, which reflects an empirical traffic characteristic(one-to-many connection rather than two-to-many). An example of this characteristic is server–client behavior, where:
1) a source port is connected with several destination hosts,
and also 2) a destination host is associated with a set of several
destination ports, which are not related to other hosts. By
definingas (right) andas (left), we connectwith, and then connectwith, where is the largest label of nodes
that have degree remaining after the previous connections. We
iterate this connection procedure until
is dealt with andconsequently obtain a bipartite graph.
4) Merging Bipartite Graphs Into a Synoptic Graphlet:
A synoptic graphlet is then drawn by combining each pairof neighboring bipartite graphs. We additionally define thedirection:as (forward) andas (backward).
The two directions have different degree distributions with thesame number of nodes:
and, and a pairismerged into a node
, where , , andare determined
as follows. We first compute the degree correlation between
and, which we define as
,
with
and
of the centroid features. If the correlationis positive, we combine the nodes in the same orderof degree value:.
Conversely, for, the combination order is reversed:.
Synoptic Versus Centroid Graphlets: Instead of synoptic
graphlets, centroid graphlets (i.e., hosts whose features arenearest to the centroid ones) may have been selected as cluster
representative. For clusters with very large number of flows,
both choices likely yield close representatives. However,centroids suffer from a number of disadvantages: 1) Centroid

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 21, NO. 4, AUGUST 2013graphlets may show a very large variability (hence lacking
robustness) for clusters with small number of flows, while synoptic graphlets are less dependent on the actual number of flow
per host because it is regenerated from all the representative
features of a cluster; 2) centroid graphlets do not necessarily
result into the typical representative of cluster because notnecessarily all the features of a single host correspond to thecentroid features. The centroid may occasionally correspondto a specific behavior, only when most of its
features areclose to the median, to the contrary of synoptic graphlets thatsomehow make the visualization/interpretation step independent from the classification phase (in a semi-supervised spirit).7
Therefore synoptic graphlets should be more effective tools torepresent what actually happens in the feature space and thus toprofile and interpret host behaviors. More detailed comparisons
between centroid and synoptic graphlets are beyond the scopeof this paper and will be discussed elsewhere.
B. Synoptic Graphlet: Interpretation
The second row of the column headings in Table III shows
the synoptic graphlets, revisualized from theclusterspresented in Section IV-B (larger versions are displayed in
Section VI).
Effectiveness of Synoptic Graphlets: One of the advantages ofsynoptic graphlets is the ability to construct an intuitive understanding of clustering results. The “complexity” of the shapesof synoptic graphlets meaningfully represents the intensity offlows. For example, a graphlet of many lines is derived fromthe use of many flows, indicating that the corresponding hostuses an application for many peers and/or many ports (e.g., DNS
and MAIL are the categories of the many-lines graphlets suchas). In addition, the number of nodes for each column
is also meaningful. For instance, if(srcPort) has only a few
nodes, then the corresponding host can be speculated to be aserver (e.g.,
is mainly labeled as WWWS by Port).
BLINC Models Validity: Most of the synoptic graphlets inTable III correspond to most of the BLINC graphlets8 (listedin [15]), and thus our result validates the intuitions behind the
BLINC series. An exception, though, is pointed out by.
7We briefly compared the synoptic graphlet and centroid-nearest graphlet foreach cluster. Approximately 80% of clusters produced intuitively similar shapesof the two kinds of graphlets. This is plausibly due to the well-tuned thresholdand enough number of hosts inside a cluster. Such correspondence between thetwo kinds implicitly validates the overall procedure of rewiring graphlets. We
also found the differences in shapes of the two kinds. For example, in Cluster, there were differences in the #nodes in the dstIP column between the corresponding synoptic graphlet and centroid-derived graphlet. Indeed, the collapse
in the shape of the synoptic graphlet (Table III) indicates that this graphlet does
not represent per-host behavior well, but rather represents an aggregated view.
and found that this cluster conWe manually inspected the composition oftained two types of typical host behaviors. This graphlet suggests that it would
into different clusters.
be meaningful to further separate
8For example, the synoptic graphlet ofcan be mapped with WEB graphlet[shown in Fig. 5(d) of the original paper], because the two graphlets commonly
represent one srcPort, and several dstPort, and a few dstIP nodes. The relevanceof this mapping is supported by the fact that R-BLINC classifies most of theas related to WEB. For another example, the synoptic graphlet ofhosts incan be related to DNS graphlet [shown in Fig. 5(g) of the original], because
the two graphlets commonly represent many srcPort, and one dstPort, and a few
dstIP nodes. The original graphlet represents both client-side and server-side
can be mapped with clientbehavior in a single figure, yet the graphlet ofside one. The relevance of this mapping is supported by the fact that R-BLINC
as related to DNS.
classifies most of the hosts in

HIMURA et al.: SYNOPTIC GRAPHLET

Fig. 7. Creation of evolutionary tree.

Most hosts are identified as UNKN by R-BLINC, whereas they
are mainly identified as FLOOD by Port (probably because ofa large amount of SYN packets and few targeted hosts). On
the other hand, some clusters having similar shape of synoptic
graphlets consist of similar breakdown such asand. As
implied by the different number of lines in the shapes of synoptic graphlets for the two clusters (Table III), this result indicates two typical numbers of flows of graphlets, which might
not easily be found by applying untuned heuristic rules.
One-Flow Graphlets:
represents synoptic graphlets composed of one flow (4594 in total—about 25% among the analyzed hosts), and the three classifiers unfortunately identify
many of them as UNKN. This kind of isolated communication
has been observed in prior studies [10], [12], [13] as well. Although one-flow graphlets are classified into various application
categories as the three classifiers point out, the one-line shapeitself reveals the important information thatpackets
from a single host constitute only one flow. In other words, a
one-flow graphlet possibly implies large file transfer because
we do not observe any control flows or the other flows. Thisplausible interpretation is supported by the finding that many ofthese hosts identified by the three classifiers are Web or P2P
users, which are occasionally used for host-to-host large-filetransfer in some cases.
In summary, synoptic graphlets are effective for an intuitiveand visual understanding of the clustering output, and thecomparison result indicates the relevance of the overall ideaof BLINC, while alleviating the difficulty of manually setting
appropriate rules and parameters.
VI. EVOLUTIONARY NATURE OF HOST-LEVEL TRAFFIC
Let us further discuss the effectiveness of the new methodby introducing evolutionary tree of synoptic graphlets, which
provides a way to understand the evolution of information about host behaviors when the numberof analyzed
packets increases. To achieve this, we analyze the same set ofhosts by changing the value of (Fig. 7). This
tree can also answer the question “How many packets do weneed to find all typical patterns?” and “How accurately hosts
can be profiled with a given ?”A. Evolutionary Tree: Creation
Snapshot: The next key question in the assessment of synoptic graphlets is raised by the choice of the numberofpackets that need to be involved in graphlet construction to find1293

Fig. 8. Characteristics of the threshold for evolutionary tree . (a) MAWI. (b)Keio.

all typical patterns and thus permit accurate host profiling. Thisis addressed via the concept of synoptic graphlet evolutionary
tree that characterizes host behavior profiling evolution whenincreases. For example, a single packet (thus a single flow)
produces a single-line graphlet, whereas two packets may result
either in a single line if they belong to the same flow or in twolines sharing nodes and edges if they share common attributes.
Any graphlet may hence evolve from an identical single-line
shape toward a complex pattern as increases. An evolutionary
tree is thus obtained from combining different snapshots , i.e.,graphlets obtained from different values of.9 For MAWI
data,
for snapshots; for Keio data,
for.
Tree Creation: Let
denote the set ofclusters obpackets). For each ,istained at snapshot (i.e., fromobtained with a value of the sole threshold that remains constant and does not depend on . Thus, serves as distance basis
in the feature space, and hence does not determine a priori thenumber of clusters, which permits to compare clustering outputs obtained with different . The evolutionary tree is createdfrom a single criteria, relying on a threshold : If the number ofhosts inis larger than( being the total
number of analyzed hosts), the two clustersandareconnected by an edge, which materializes that the typical behavior
at snapshot tends to evolve intoat.
Finally, an evolutionary tree provides an intuitive overview ofthe behavioral growth of hosts.
Threshold: Setting the threshold , which determines
whether neighboring clusters are connected or not, resultsfrom the following tradeoff: Too high may yield “isolated”
clusters, not connected to any other clusters on any neighboring
snapshot; too low may yield many “impossible” evolutions
in graphlet shapes. For example, for some synoptic graphlets,might be reduced from tobecause of the changes in theset of hosts within a cluster, despite the fact that this never occurs in the evolution of the graphlet of a single host. Therefore,
the connection between Cluster at snapshot and Cluster at
is declared impossible if either of parameters , , andis reduced. Fig. 8 illustrates the tradeoff, plotting the number ofisolated clusters and that of impossible evolutions as a functionof . Empirically, the threshold is set to(i.e., about(i.e., about
150 hosts) for MAWI data, and to
9It should also be interesting to analyze this by increasing the number of flows
per host (instead of increasing the number of packets ). However, we have toelaborate on the appropriate way to deal with hosts with low number of flows(e.g., 25% of hosts have only one flow).

1294

Fig. 9. Evolutionary tree of synoptic graphlets as a function ofIEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 21, NO. 4, AUGUST 2013(or ).

70 hosts) for Keio data, which maintain no isolated cluster anda low number of impossible evolutions.
B. Evolutionary Tree: Interpretation
1) Intuition From Evolutionary Tree—Visual Analysis:
Global View: Fig. 9 depicts the resulting evolutionary tree,
, cf. Section IV-B.1,
for MAWI data (, cf. Section IV-A). Synoptic graphlets at snapshot
are shown in the th column, and related synoptic graphlets(from successive snapshots) are linked with arrows. The synoptic graphlets atcorrespond to the evaluations presented in Sections IV-B and V.
Fig. 9 thus provides an intuitive and comprehensive overview
of the evolution of typical host behaviors, from(originof graphlets) to large , permitting interpretation of graphletchanges with . Interestingly, clusters do not only separate, butalso merge asincreases. This suggests that there exist different evolution footprints, even when hosts are clustered intoa same group at a given snapshot. Evolutionary trees thus enhance the profiling by providing richer information.

Early Stages: For, by nature, there are only
one-flow graphlets. For, although there are theoreticallypossible graphlets (combination of four attributes:
proto, srcPort, dstPort, and dstIP), only seven are actually observed. Although some graphlets are actually different from theseven synoptic graphlets and have different transitions, these
are not typical, and hence do not appear in the figure. Suchminor graphlets could be found by finer-grained clustering,with lower .
Late Stages: The final forms of graphlets become apparent
in the late stages. For example, one-flow graphlet A is destined, as indicated by theto mostly remain one-flow, after
abrupt increase in predictability discussed in Section VI-B.2.
Other examples are provided by synoptic graphlets B and C,
and 50, respectively. They are mainly
prominent at
related to scanning activities, which thus indicates thatis large enough to permit separation of scanners from otheractivities. As a whole, the total number of clusters at
remains quasi-unchanged compared to that at. Thus,can be considered as the reference number of packets
required for accurately discovering typical host behaviors. Also,
this result implies thatprovides some longitudinal

HIMURA et al.: SYNOPTIC GRAPHLET

Fig. 10. Predictability of evolution as a function of1295. (a) MAWI. (b) Keio.

stationarity of aggregated view of host behaviors. The bottom
stops
row in Table III lists each stage at which each Cluster
its evolution along the tree (i.e., becomes predictable).
Keio Data Case: Similar results were obtained for Keio data,
but for the fact that one-flow graphlets continue to evolve at. We interpret that the stagnation of one-flow graphlets for
MAWI could stem from the partial view of the traffic, measured
at the backbone link, whereas Keio traffic is measured at an edge
router.
2) Predictability in Evolution—Quantitative Analysis: To
complement the understanding of synoptic graphlet evolution,
the evolution predictability of a given host in the tree is quantified. Let us define,atwhich measures the probability that hosts in Cluster
snapshotevolves into Cluster at. We
define the predictability of Clusteras, whereis the final snapshot andthe corresponding number
is hence a normalized entropy thatof clusters.
characterizes the dispersion of transition probabilities. Thus,
ifgrows only to, then, whereas if
can evolve into any future shapes with equal probability,then. Note that this predictability is computed
considering all possible evolutions (i.e.,).
Fig. 10 displays the predictabilities of all clusters
as a function of (or ) for MAWI and Keio. Each dot stands
for a synoptic graphlet (i.e., a cluster) for a given snapshot.
The dashed line represents the transition in the average predictability and shows that the predictability is approximately
linear with
(Pearson’s correlation coefficient is 0.95).
is almost 0, which suggests that
The predictability at
the corresponding origin of a graphlet can evolve into any final
graphlet. Conversely, this predictability becomes higher withhigher . In addition, predictabilities for someabruptly
become higher than for others, which indicates the end of theevolution for that synoptic graphlet, as shown by Points A andB atand C at(that correspond to synoptic
graphlets A–C in Fig. 9). The high predictability value forthese synoptic graphlets at low snapshots confirms the observation made from the evolutionary tree that the future of thesegraphlets is early set and hence that can be easily distinguishedwith fewer packets than other types of graphlets.
VII. DISCUSSION
Revisiting BLINC: The results presented in Sections IV-B
and V validate the concepts at work in BLINC, as most of theauto-generated synoptic graphlets can be related to empiricallydefined BLINC graphlet models [15]. However, such heuristic
model-based approaches face the potential difficulties in: 1) designing appropriate rules as indicated by the observed unknown
clusters, and in 2) determining the relevant values of thresholds for accurate classification as partially implied by a priorwork [16], which conducted a number of trials to determine appropriate parameters. Instead, unsupervised approaches can potentially uncover new types of applications with the tuning of
only a very limited number of threshold levels. In addition, an
advantage of our approach should be to avoid the assumptionthat the traffic of one host should be mostly explained by a single
application.10
Traffic Characteristic Evolution When Increasing the
Number of Analyzed Packets: Section VI showed that themethod requires around 100 packets to classify hosts. This islarger than the findings of a few previous works. For instance,
the work reported in [1] showed that major TCP flows can be
identified on bidirectional links from their size and direction
by examining only the first four or five packets (after the handshake) in a connection. Other works [8], [20], [25] also claimed
such an ability. This paper, however, deals with more generalassumptions about traffic: unidirectional links, legitimate aswell as anomalous and unknown traffic, a few protocols besides
TCP, uncertainty of observing the first packets of flows. In
this context, the need to collect a larger amount of information
to predict traffic characteristics does not come as a surprise.
Moreover, our work is to profile hosts, not only identifying theapplication in a TCP connection.
Limitations:1) The degree-based features used here do not include relations among nonneighboring columns such as
and .
2) In addition, real graphlets are not as clean as rewired ones
because they include packets unrelated to the main behaviors of the hosts. Features could be weighted to remove
such noise, e.g., the width of edges and the radius of nodes
could be set based on the number of packets.
3) In some cases, host behaviors may result from two dominant kinds of applications, e.g., a host serving both mailand DNS, or a NAT gateway with a Web client and a P2P
user. Such a host cannot easily be profiled.
4) In general, synoptic graphlets only provide shape information. Although such information provides meaningful insight into host behaviors as shown throughout this paper, it
is still difficult to identify the exact application names usedby hosts. If we want to identify them, it would be helpful
to put port numbers in the graphlet figure or to cross-compare with classifiers based on port numbers, payloads, IP
addresses [28], packet sizes [1], [8], and so on.
Application to Supervised Approaches: A potential application is to create a reliable dataset of known flows, which an
10To show the nonnegligible amount of application mixture of a host, we, wherequantify the degree of this for a host as
is an application (except for UNKN),
is the total number of ’s
flows identified as a certain application (except for UNKN) by the payload clasis the number of ’s flows identified as application by thesifier,is the fraction of most dominant application
classifier. In other words,
hosts in the 12 MAWI traces,in terms of #flows. For the result for, bottom 20% have
we found that bottom 10% of hosts have
, and bottom 25% have(i.e., remaining 75%
of hosts are mostly characterized by a single application).

1296

IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 21, NO. 4, AUGUST 2013

approach like that of Iliofotou et al. [11] could then use. Thisis because our experiment found graphlets corresponding to asingle application (sayin Table III). Such graphlets could beknown signatures for any supervised methods. This approach is
better than just using a signature generator (say a payload-basedclassifier), as any classifier will have some misclassification.
The clustering scheme presented here can group highly interrelated flows that can be characterized as learning data of enhanced reliability.
Application to Unsupervised Approaches: Another use caseof our method is to help researchers (or network administrators)
to interpret the results of unsupervised clustering over graphlets.
In general, interpretation of resulting clusters should require to
examine a lot of numerical features, as a prior work [6]does, which becomes significantly difficult as the dimension increases. On the other hand, the use of synoptic graphlet supports
such interpretation by converting those features in a single intuitive figure. For example, if a synoptic graphlet for Cluster
contains only a single node in the column for srcPort and thenode has several edges, one can easily interpret that is mostly
composed of server hosts (similarly, that for dstPort implies thatis related to client hosts). With such assistance in interpretation, operators will efficiently notice and understand the emergence of new types of application usages (e.g., malicious hosts,
P2P software users, or rapid increase in Web clients) appearing
as new clusters in the monitored link.
VIII. CONCLUDING REMARKSThe main issue of this paper was the tradeoff in choosing
between supervised and unsupervised approaches to end-hostprofiling. The former is comprehensive but is blind to undefined classes, while the latter can uncover unknown pattens of
behavior at the sacrifice of interpretability. We aimed to bridge
the gap between the two in this paper. The proposed method
was designed to perform unsupervised clustering for finding
undefined classes and to revisualize the resulting clusters assynoptic graphlets for providing interpretability. We compared
the method against a graphlet-based state-of-the-art classifier (BLINC) as well as against a classical port-based inspector
and a payload-based one by applying these methods to two
sets of actual traffic traces measured at different locations. The
proposed method spontaneously generated synoptic graphlets
that are typical in their shape, which validates the graphletmodels heuristically predefined in earlier works. Also, formethodological study of the improvements brought to hostprofiling, this work demonstrated how to extend beyond a
simple classification to the production of an evolutionary tree
by increasing the number of observed packets per host. The
entire procedure requires only a few threshold to be tuned while
the state-of-the-art method needs many. The new achievementsin this contribution are as follows: 1) an unsupervised clustering applied to graphlet shape-based characteristics; which
is further significantly extended to 2) a visualization-oriented
auto-enumeration of typical host behaviors generated from
actual data, successfully resulting in validating the relevance of
past works, and 3) an analysis on evolutionary characteristicsof the growth of host behaviors both in visual and quantitative
manners, which is useful in understanding the evolutionary
nature of host behaviors.

ACKNOWLEDGMENT
The authors thank Y. J. Won (IIJ), G. Dewaele (ENS de
Lyon), and R. Fontugne (Sokendai/NII) for their invaluableadvice. They also thank H. Kim (Seoul National University),
T. Karagiannis (Microsoft Research), and D. Barman (Juniper
Networks) for providing access to the payload-based classifierand BLINC.
REFERENCES[1] L. Bernaille, R. Teixeira, and K. Salamatian, “Early application identification,” in Proc. ACM CoNEXT, 2006, p. 12.
[2] P. Borgnat, G. Dewaele, K. Fukuda, P. Abry, and K. Cho, “Seven years
and one day: Sketching the evolution of Internet traffic,” in Proc. IEEE
INFOCOM, 2009, pp. 711–719.
[3] K. Cho, K. Mitsuya, and A. Kato, “Traffic data reposity at the wide
project,” in Proc. USENIX 2000 FREENIX Track, 2000, p. 8.
[4] CAIDA, La Jolla, CA, “The CoralReef project,” 1999 [Online]. Available: http://www.caida.org/tools/measurement/coralreef/[5] G. Dewaele, K. Fukuda, P. Borgnat, P. Abry, and K. Cho, “Extracting
hidden anomalies using sketch and non gaussian multiresolution statistical detection procedure,” in Proc. ACM SIGCOMM LSAD, 2007, pp.
145–152.
[6] G. Dewaele, Y. Himura, P. Borgnat, K. Fukuda, P. Abry, O. Michel, R.
Fontugne, K. Cho, and H. Esaki, “Unsupervised host behavior classification from connection patterns,” Int. J. Netw. Manage., vol. 10, no.
5, pp. 317–337, 2010.
[7] J. Erman, M. Arlitt, and A. Mahanti, “Traffic classification using clustering algorithms,” in Proc. ACM SIGCOMM MINENET, 2006, pp.
281–286.
[8] V. C. Espanol, P. B. Ros, M. S. Simó, A. Dainotti, W. D. Donato, and
A. Pescapé, “K-dimensional trees for continuous traffic classification,”in Proc. TMA, 2010, p. 14.
[9] Y. Himura, K. Fukuda, P. Abry, K. Cho, and H. Esaki, “Characterization of host-level application traffic with multi-scale gamma model,”IEICE Trans. Commun., vol. E93-B, no. 11, pp. 3048–3057, 2010.
[10] M. Iliofotou, M. Faloutsos, and M. Mitzenmacher, “Exploiting dynamicity in graph-based traffic analysis: Techniques and applications,” inProc. ACM CoNEXT, 2009, pp. 241–252.
[11] M. Iliofotou, B. Gallagher, T. E.-Rad, G. Xie, and M. V. Faloutsos,“Profiling-by-association: A resilient traffic profiling solution for theInternet backbone,” in Proc. ACM CoNEXT , 2010, p. 12.
[12] M. Iliofotou, H. C. Kim, M. Faloutsos, M. Mitzenmacher, P. Pappu,
and G. Varghese, “Graph-basedP traffic classification at the Internet
backbone,” in Proc. IEEE Global Internet Symp., 2009, p. 6.
[13] Y. Jin, E. Sharafuddin, and Z. L. Zhang, “Unveiling core network-widecommunication patterns through application traffic activity graph decomposition,” in Proc. ACM SIGMETRICS, 2009, pp. 49–60.
[14] T. Karagiannis, K. Papagianakki, N. Taft, and M. Faloutsos, “Profilingthe end host,” in Proc. PAM, 2007, pp. 186–196.
[15] T. Karagiannis, K. Papagiannaki, and M. Faloutsos, “BLINC: Multilevel traffic classification in the dark,” in Proc. ACM SIGCOMM, 2005,
pp. 229–240.
[16] H. Kim, K. C. Claffy, M. Fomenkov, D. Barman, M. Faloutsos, and K.
Y. Lee, “Internet traffic classification demystified: Myths, caveats, andthe best practices,” in Proc. ACM CoNEXT, 2008, p. 12.
[17] “l7-Filter,” 2009 [Online]. Available: http://l7-filter.sourceforge.net[18] A. Lakhina, M. Crovella, and C. Diot, “Mining anomalies using traffic
feature distributions,” in Proc. ACM SIGCOMM, 2005, pp. 217–228.
[19] S. Lee, H. Kim, D. Barman, S. Lee, C. Kim, and T. T. Kwon, “NeTraMark: A network traffic classification benchmark,” Comput. Commun.
Rev., vol. 41, no. 1, pp. 23–30, 2010.
[20] Y. Lim, H. Kim, J. Jeong, C. Kim, T. T. Kwon, and Y. Choi, “Internet
traffic classification demystified: On the sources of the discriminative
power,” in Proc. ACM CoNEXT, 2010, p. 12.
[21] “MAWI Working Group traffic archive,” [Online]. Available: http://mawi.wide.ad.jp/mawi/[22] J. McHugh, R. McLeod, and V. Nagaonkar, “Passive network forensics: Behavioural classification of network hosts based on connection
patterns,” Oper. Syst. Rev., vol. 42, no. 3, pp. 99–111, 2008.
[23] A. W. Moore and D. Zuev, “Internet traffic classification using
Bayesian analysis techniques,” in Proc. ACM SIGMETRICS, 2005,
pp. 50–60.
[24] “OpenDPI,” [Online]. Available: http://opendpi.org/

HIMURA et al.: SYNOPTIC GRAPHLET[25] M. Pietrzyk, J. L. Costeux, G. Urvoy-Keller, and T. En-Najjary,“Challenging statistical classification for operational usage: The
ADSL case,” in Proc. ACM IMC, 2009, pp. 122–135.
[26] M. Roesch, “Snort—Lightweight intrusion detection for networks,” inProc. USENIX LISA, 1999, pp. 229–238.
[27] G. Tan, M. Poletto, J. Guttag, and F. Kaashoek, “Role classificationof hosts within enterprise networks based on connection patterns,” inProc. USENIX Annu. Tech. Conf., 2003, pp. 15–28.
[28] I. Trestian, S. Ranjan, A. Kuzmanovic, and A. Nucci, “Unconstrained
endpoint profiling (Googling the Internet),” in Proc. ACM SIGCOMM,
2008, pp. 279–290.
[29] K. Xu, F. Wang, and L. Gu, “Network-aware behavior clustering ofInternet end hosts,” in Proc. IEEE INFOCOM, 2011, pp. 2078–2086.
[30] K. Xu, Z. L. Zhang, and S. Bhattacharyya, “Profiling Internet backbone
traffic: Behavior models and applications,” in Proc. ACM SIGCOMM,
2005, pp. 169–180.
[31] L. Y. Liu, “Feature selection for high-dimensional data: A fast correlation-based filter solution,” in Proc. ICML, 2003, pp. 856–863.

Yosuke Himura is a Master’s student in informationand communication engineering at the University ofTokyo, Tokyo, Japan.
His research interests include statistical analysis ofInternet traffic.

Kensuke Fukuda (M’08) received the Ph.D. degree
in computer science from Keio University, Tokyo,
Japan, in 1999.
He is an Associate Professor with the National Institute of Informatics (NII) and is a Researcher with
PRESTO, JST, Tokyo, Japan. He worked with NTT
Laboratories from 1999 to 2005, and joined NII in
2006. In 2002, he was a Visiting Scholar with Boston
University, Boston, MA. His current research interests are Internet traffic measurement and analysis, intelligent network control architectures, and the scientific aspects of networks.

1297

Kenjiro Cho (M’12) He received the B.S. degree
in electronic engineering from Kobe University, theM.Eng. degree in computer science from Cornell
University, and the Ph.D. degree in media andgovernance from Keio University.
He is Deputy Research Director with the Internet
Initiative Japan, Inc., Tokyo, Japan. He is also an Adjunct Professor with Keio University and Japan Advanced Institute of Science and Technology, Tokyo,
Japan, and a board member of the WIDE project. His
current research interests include traffic measurement
and management and operating system support for networking.

Pierre Borgnat (M’06) received the Professeur-Agrégé de Sciences Physiques degree,
M.Sc. degree in physics, and Ph.D. degree inphysics and signal processing from École Normale
Supérieure (ENS) de Lyon, Lyon, France, in 1997,
1999, and 2002, respectively.
From 2003 to 2004, he spent one year with the
Signal and Image Processing group of the IRS, IST,
Lisbon, Portugal. Since October 2004, he has been afull-time CNRS Researcher with the Laboratoire dePhysique, ENS de Lyon. His research interests are instatistical signal processing of nonstationary processes and scaling phenomena
for complex systems. He is also working on Internet traffic measurements andmodeling and analysis and modeling of dynamical complex networks.

Patrice Abry (M’05–SM’07–F’12) received theProfesseur-Agrégé degree in physics and Ph.D.
degree in physics and signal processing from École
Normale Supérieure de Lyon and Université Lyon I,
Lyon, France, in 1989 and 1994, respectively.
He has been a CNRS Researcher since 1995
and became CNRS Research Director in 2005. His
research interests include wavelet-based analysis
and modeling of scale invariance phenomena andrelated topics (self-similarity and multifractal) andrange from theory to applications.
Dr. Abry received the AFCET-MESR-CNRS prize for best Ph.D in signal
processing for the years 1993–1994.

Hiroshi Esaki (M’08) received the Ph.D. degree inelectronic engineering from the University of Tokyo,
Tokyo, Japan, in 1998.
In 1987, he joined the Research and Development
Center, Toshiba Corporation. From 1990 to 1991, he
was with the Applied Research Laboratory, Bellcore
Inc., NJ, as a Residential Researcher. From 1994 to
1996, he was with the Center for Telecommunication
Research, Columbia University, New York, NY. In
1998, he served as a Professor with the University ofTokyo and as a board member of the WIDE Project.
Currently, he is Executive Director of the IPv6 promotion council, Vice President of JPNIC, an IPv6 Forum Fellow, and a board member of the WIDE Project
and the Board of Trustees of the Internet Society.