Jayaraman J Thiagarajan

Karthikeyan N Ramamurthy

Andreas Spanias
email: spanias@asu.edu

Dimensionality Reduction for Distance Based Video Clustering

Keywords: Clustering, Random projections, Gaussian mixtures, Video summarization

Clustering of video sequences is essential in order to perform video summarization. Because of the high spatial and temporal dimensions of the video data, dimensionality reduction becomes imperative before performing Euclidean distance based clustering. In this paper, we present non-adaptive dimensionality reduction approaches using random projections on the video data. Assuming the data to be a realization from a mixture of Gaussian distributions allows for further reduction in dimensionality using random projections. The performance and computational complexity of the K-means and the K-hyperline clustering algorithms are evaluated with the reduced dimensional data. Results show that random projections with an assumption of Gaussian mixtures provides the smallest number of dimensions, which leads to very low computational complexity in clustering.

Introduction

Classification of data is an important problem in machine learning, where data sets are separated into several disjoint classes based on predefined criteria. The predefined criteria, referred as the hypothesis, can be supplied by the user or learned by the machine itself from classes of labeled training samples. In supervised learning, hypotheses of multiple classes are learned from a set of labeled training data for each class [START_REF] Alpaydin | Introduction to Machine Learning[END_REF]. Clustering is a more general problem in machine learning where the observed unlabeled data need to be grouped into different clusters. A cluster is a group of similar data where the similarity is quantified based on a well-defined measure. A useful similarity measure for clustering is the Euclidean distance measure and clustering based on Euclidean distance is an NP-hard problem [START_REF] Kannan | Spectral Algorithms[END_REF].

Clustering of video frames is more than just a generalization of clustering of images. This is because the video frames that convey meaning as a group are both statistically and semantically related. One of the popular approaches to video clustering involves extracting the keyframes by shot boundary detection and clustering the keyframes together to derive a semantic interpretation [START_REF] Vailaya | Video Clustering[END_REF].

However, it is important to understand that extraction of the keyframes by detecting the shot boundaries itself is a fundamental clustering problem which we address in this paper. Video frames of a single shot have similar background structure and they can be clustered together using color histograms or distance measures.

In this paper, we address the problem of clustering high dimensional long video sequences. In general, this kind of video clustering involves grouping the frames with similar background together for the purpose of extracting keyframes. Using the fact that the video frames that have similar backgrounds are close together in terms of the Euclidean distance measure (l 2 norm), we perform distance based clustering. It is important to clarify the notion of background in this problem. Background is the region in a frame that remains relatively motionless. Even if some objects in the foreground are relatively motionless they can be treated as background. The very high spatial and temporal dimensionality of the video data makes l 2 norm based clustering intractable in the absence of tremendous computational power. Therefore, it becomes essential to reduce the dimensionality of the video data in order to perform clustering with low complexity. This problem is highly significant in scenarios where fast summarization of video needs to be performed at a reduced computational cost. In this paper, we propose a framework for dimensionality reduction to cluster video frames having similar background structure. The framework is based on non-adaptive dimensionality reduction using the theory of random projections [START_REF] Vempala | The Random Projection Method[END_REF] and assumption of Gaussian mixture (GM) models for data.

K-Means and K-Hyperline clustering

The K-means clustering problem seeks to cluster the T data samples into K clusters by minimizing the sum of intracluster distances across all clusters. It converges to a locally optimal solution closest to the initial values. This is a 2step alternating minimization problem where the samples are associated to the cluster centroids in the first step and the centroids are recalculated in the second step using the associated member samples. The member sample is associated to a cluster centroid that is closest in terms of the Euclidean distance measure. The centroid that minimizes the sum of distances to all its member samples is computed by solving,

xj = min r ∑ i∈Λj ∥x i -r∥ 2 , ( 1
)
where xj is the cluster centroid and Λ j is the index set containing the memberships of the j th cluster. The solution obtained for xj is the mean of member samples. K-hyperline clustering seeks to compute a rank-1 subspace using Singular Value Decomposition (SVD) for each cluster that minimizes the sum of distance of the member data to the subspace [START_REF] He | K-hyperline clustering learning for sparse component analysis[END_REF]. K-hyperline clustering is more accurate and general than K-means clustering in that the minimization problem yields lesser sum of distances than the K-means clustering and it can easily generalize to higher rank subspaces. The association rule for the member sample for the nearest rank-1 subspace is based on a maximum correlation measure. In K-hyperline clustering the rank-1 subspace is of unit norm, whereas no such constraint is imposed in K-means clustering on the cluster centroid.

Random Projections

Consider a high dimensional data matrix, X, with dimensions M × T , where each column represents a single data observation. In order to project this onto a random low dimensional space, we define a matrix R of dimensions M × N with N < M , whose entries are chosen independently from the standard normal distribution N (0, 1). The Random Projection (RP) of the data vectors is,

Y = 1 √ N R T X. (2)
RP reduces the dimensionality of the data from M to N while approximately preserving pair-wise distances with high probability [START_REF] Vempala | The Random Projection Method[END_REF]. This is formalized by the Johnson-Lindenstrauss (JL) lemma, which states that for a large enough N (N ≥ C ln T ϵ 2 ) (3) holds with high probability.

(

-ϵ) ∥y i ∥ 2 ≤ 1 N ∥R T x i ∥ 2 ≤ (1 + ϵ) ∥y i ∥ 2 , 1
where y i and x i represent the columns of the matrices Y and X respectively and 0 < ϵ < 1. It is important to note that the JL lemma does not depend on the actual dimensionality of the data and depends only on the number of data vectors. The K-means clustering defines the cluster centroid as the mean of data vectors in a cluster. It is easy to observe from JL lemma that the distances between the cluster centroid and the data vectors will be approximately preserved even after random projections. Hence we can use the JL lemma to reduce the dimensionality of the data matrix for use in K-means clustering.

Computation of SVD using Random Projections

The computation of SVD can also be performed using the reduced dimensional matrix from random projections [START_REF] Vempala | The Random Projection Method[END_REF]. It can be shown that for the same low rank approximations of Y and X, the Frobenius norms will be approximately preserved with high probability. This can be mathematically expressed as,

s ∑ i=1 λ 2 i ≥ (1 -ϵ) s ∑ i=1 σ 2 i , ( 4
)
where λ i and σ i are the singular values of Y and X respectively and s is the desired rank of the approximation [START_REF] Vempala | The Random Projection Method[END_REF]. In particular, considering a rank-1 approximation, it can be shown that, with high probability [START_REF] Vempala | The Random Projection Method[END_REF][START_REF] Dasgupta | Learning Mixtures of Gaussians[END_REF] (

1 -ϵ)σ 2 1 ≤ λ 2 1 ≤ σ 2 1 . ( 5
)
The existence of such upper and lower bounds motivates the use of K-hyperline clustering on Y instead of X.

Gaussian Mixture Models for Clustering

Statistical clustering algorithms assume that the data is a realization from a mixture of probability distributions. In the case of mixture of K arbitrary distributions, the overall probability density is given by,

f = K ∑ i=1 w i f i s.t. w i ≥ 0 and K ∑ i=1 w i = 1, (6)
where f i is the probability distribution function (pdf) and w i is the non-negative weight of the i th distribution. The best SVD subspace for a spherical Gaussian distribution is any subspace through its mean [START_REF] Kannan | Spectral Algorithms[END_REF]. More importantly, the best K-dimensional SVD subspace for a mixture of K Gaussians whose covariance is a scalar multiple of identity, contains the span of the means of the component distributions. This can also be extended to a mixture of arbitrary distributions. In general, we do not have the exact statistics of a GM and we have only the samples of realizations. The covariance matrix is also not a scalar multiple of identity. Even under these conditions, it has been proved that the SVD subspace of the sample matrix is not far from the subspace spanned by the actual component means [START_REF] Kannan | Spectral Algorithms[END_REF].

Separation Between Spherical Gaussians

Two spherical Gaussians N (µ 1 , σ 2 1 I) and N (µ 2 , σ 2 2 I) are considered to be c-

separated if ∥µ 1 -µ 2 ∥ 2 2 ≥ c 2 M max(σ 2 1 , σ 2 2
), where M is the dimension of the Gaussian [START_REF] Dasgupta | Learning Mixtures of Gaussians[END_REF]. A 2-separated mixture corresponds to almost completely separated Gaussians, whereas a 1-or 1/2-separated mixture contains Gaussians which overlap significantly. By projecting the Gaussian mixtures on to a K-dimensional subspace spanned by the means of K Gaussians, we are equivalently projecting the Gaussian mixtures onto their best rank-K SVD subspace. This preserves the distance between the means (intercluster distance), whereas the intracluster distance reduces drastically [START_REF] Kannan | Spectral Algorithms[END_REF]. Therefore, the separation between the Gaussians in the mixture increases and the clustering performance improves. Similar results can also be shown for mixtures of Gaussians with arbitrary covariances [START_REF] Kannan | Spectral Algorithms[END_REF].

Proposed Clustering Framework

In this paper, we use both the K-means and the K-hyperline clustering algorithms for clustering the video data. We consider four different approaches: a) basic K-means/K-hyperline clustering on the high dimensional data, b) reducing the dimensions of the data using random projections prior to clustering, c) reducing the dimensions of the data assuming it as a mixture of Gaussians prior to clustering and d) reducing the dimensions, first using RP and then under the mixture of Gaussians assumption, prior to clustering. Both centroid and left singular vector of a group of video frames retrieve the background information effectively. This motivates the use of both K-means/K-hyperline clustering in our approaches. We will assume that we have K clusters of the T video frames and we vectorize each video frame into a M dimensional vector thereby generating the M × T matrix X. The K index sets of the clusters are given by {Λ i } K i=1 and T i = |Λ i |. In the remaining part of this section, we describe the different approaches for clustering.

Random Projection based Clustering

The RP method can be used to reduce the dimensionality of the data matrix X according to (2), preserving the length of the data vectors, pairwise distances and angles with high probability. We have also seen in Section 3 that the centroid and SVD of a set of data vectors are approximately preserved with a high probability, given a sufficiently large number of measurements N .

Assuming that K = 1, the centroid and the first singular vector of Y are approximately equal to that of X for a sufficiently large N . If K > 1, the centroid and first singular vector of each cluster will still be approximately preserved because T i < T . Therefore, the RP method will be useful regardless of the number of clusters, provided we choose N based on the assumption of single cluster. The linear increase in the number of data vectors T will not change N significantly because N ∝ ln T . Therefore, in order to perform RP based clustering, we use either the K-means or the K-hyperline clustering algorithm on the reduced dimensional data.

Gaussian Mixture based Clustering

We know from Section 4 that the rank-K SVD subspace of the sample matrix is not far from the space spanned by the K component means even when the Gaussians are not spherical. In this approach for clustering, we assume that X contains realizations from a mixture of K Gaussians, not necessarily spherical, where each Gaussian represents a cluster. We compute the best rank-K subspace of X using SVD and denote the basis vectors of the rank-K subspace (first K left singular vectors of X ) by U K . The projection to the rank-K subspace is given by,

W = U T K X, (7)
where W contains the K dimensional data vectors after projection. Because of the reasoning provided in Section 4.1, the clusters in the K dimensional space are more separated than the clusters in the M dimensional space. Therefore, we perform K-means or K-hyperline clustering on W and identify the index sets of the clusters.

Goal: To perform clustering of high-dimensional long video sequences using the approach given in Section 5.3

Variables

High-dimensional data matrix, X of size M × T . Intermediate data matrix after RP, Y of size N × T . Final data matrix used for clustering, Z of size K × T . Initial number of clusters, J.

Actual number of clusters, K.

Cluster centroid matrix (J Clusters), B of size K × J.

Cluster centroid matrix (K Clusters), A of size K × K. Index set for the i th cluster, Λi.

Gaussian i.i.d. random matrix, R of size M × N . Algorithm 1. Compute the RP, Y = (1/ √ N )R T X. 2. Compute rank-K SVD, [UK , SK , VK ] = SVD(Y, K) . 3. Project on to the K-dimensional SVD space, Z = U T K Y. 4.
Initialize B with J randomly chosen columns of Z. 5. Perform K-means/K-hyperline clustering for J clusters. 6. Using greedy combinations of columns of B, create A. 7. Perform K-means/K-hyperline clustering for K clusters using A as initial centroids. 8. Using the index sets Λi obtained from clustering, identify the keyframes.

Table 1. Algorithm to cluster video data and identify keyframes.

Random Projection and Gaussian Mixture based Clustering

Similar to the previous case, in this approach we assume X to be a set of T realizations of K Gaussians. Furthermore, as RP approximately preserves the pairwise distances of the samples, realizations from a mixture of K Gaussians in M dimensions preserve their structure in N dimensions. This fact is used to further reduce the computational complexity of the framework.

In this approach, we first project X to obtain Y according to [START_REF] Kannan | Spectral Algorithms[END_REF]. The elements of Y are treated as realizations of a mixture of K Gaussians in N dimensions. From the arguments in Section 5.2, we project Y onto a K dimensional SVD subspace to obtain Z. K-means or K-hyperline clustering can be performed on Z to identify the index sets of the clusters. Note that in this case, we first perform an initial level of dimensionality reduction using RP, which aids in a faster computation of the SVD subspace. In the second stage, we reduce the dimensionality further using the GM assumption. Hence, this approach combines the advantages of both the previous approaches in terms of a much reduced computational complexity due to RP and improved clustering performance along with further reduction in computational complexity due to the assumption of Gaussian mixtures. The outline of the algorithm to perform video clustering and identify the keyframes is shown in Table 1. 1.

To improve the clustering performance, we adopt a two stage approach to clustering. This reduces the possibility of the clustering algorithm being stuck in a local minima. Initially, we solve the clustering problem for a number of clusters J that is larger than the actual number K. Then, we greedily combine the columns of the cluster centroid matrix B in order to obtain the matrix A (step 6 of Table 1). In this greedy combination method we first choose the two most similar vectors of B and combine them. We repeat this procedure for two columns at a time until we are left with only K columns. In the Kmeans method two most similar vectors are the ones that have the minimum pairwise Euclidean distance and the combined vector is the mean of the two. In K-hyperline clustering two most similar vectors are the ones that have the maximum correlation and the combined vector is principal left singular vector of the matrix of the two vectors.

Experimental Results

The video sequences in QCIF format, used for evaluating the performance of the algorithms, were obtained from [START_REF]YUV Video Sequences[END_REF] and the spatial resolution was changed to 128 × 128. The first test data set was generated by stitching 10 different video sequences and it contains 1900 frames in total. The second test data set has a total of 550 frames obtained from 3 different video sequences. The initial number of clusters J is set to 3 times the actual number of clusters K. For the first data set K = 10 and for the second data set K = 3. The keyframes are identified using all the four approaches for both K-means and K-hyperline clustering. The keyframes obtained for the first data set are shown in Figure 1. The keyframes identified are similar with the all the four approaches and we also obtain 100% clustering performance. 2. Comparison of running time for the different clustering approaches in MAT-LAB. Wherever applicable, the running times include dimensionality reduction phase also. The results for the first and the second data sets are separated by a slash (/). The third approach could not run for the first data set owing to memory issues because of high dimensionality.

The running times for the different approaches in MATLAB (version R2007b) to cluster the test data are listed in Table 2. It can be seen that the approach based on RP and GM is of least computational complexity. The running time for the K-means and the K-hyperline clustering algorithm are close to each other except for the case of the basic approach, which however is not the choice when clustering high dimensional data.

Fig. 1 .

 1 Fig. 1. Keyframes obtained by clustering the test data using the algorithm in Table1.

Conclusions

In this paper, we proposed different approaches for dimensionality reduction based on random projections in order to cluster video data. These approaches provide a practical solution to clustering video frames with similar background for fast video summarization. Incorporation of outlier rejection and compensating for global motion between the video frames are possible extensions to the proposed dimensionality reduction approaches for robust clustering.


Sofiane Lagraa

Jérôme Franc

Abdelkader Lahmadi

Marine Miner

Christian Hammerschmidt

Radu State

BotGM: Unsupervised Graph Mining to Detect Botnets in Traffic Flows

Keywords:

Botnets are one of the most dangerous and serious cybersecurity threats since they are a major vector of large-scale attack campaigns such as phishing, distributed denial-of-service (DDoS) attacks, trojans, spams, etc. A large body of research has been accomplished on botnet detection, but recent security incidents show that there are still several challenges remaining to be addressed, such as the ability to develop detectors which can cope with new types of botnets. In this paper, we propose BotGM, a new approach to detect botnet activities based on behavioral analysis of network traffic flow. BotGM identifies network traffic behavior using graph-based mining techniques to detect botnets behaviors and model the dependencies among flows to traceback the root causes then. We applied BotGM on a publicly available large dataset of Botnet network flows, where it detects various botnet behaviors with a high accuracy without any prior knowledge of them.

I. INTRODUCTION

Botnet detection and tracking has been a major research topic in the last decade in the area of network security with numerous surveys revealing the large range of techniques to track and mitigate them [START_REF] Khattak | A taxonomy of botnet behavior, detection, and defense[END_REF], [START_REF] García | Survey on network-based botnet detection methods[END_REF]. The evolving of botnets, and the inability of traditional protection mechanisms to stop them, has led security researchers and practitioners to develop behavior-based techniques [START_REF] Wang | Behavior-based botnet detection in parallel[END_REF]- [START_REF] Liu | Flow-based anomaly detection using access behavior profiling and time-sequenced relation mining[END_REF]. Unlike statistical or signature-based techniques [START_REF] Wurzinger | Automatically Generating Models for Botnet Detection[END_REF], [START_REF] Alzahrani | Real-time signature-based detection approach for sms botnet[END_REF] used for years to detect the presence of known bots, behavior-based techniques observe the actions of potential bots and attempt to match them against pre-defined specifications of bots' behaviors, or try to assess how they differ from the normal behavior exhibited by other hosts. However, the continuously apparition of new botnet propagation and command-and-control (C&C) mechanisms shows the limitation of those detection techniques, which cannot cope with unknown and more and more complex behaviors.

Rather than analyzing individual host behavior, our approach, named BotGM, considers multiple host behaviors to represent dependencies among their flows which can be then traced back in a comprehensive manner to investigate root causes of the detected abnormal behaviors.

Our method relies on NetFlow because it is widely used in security and monitoring of computer networks [START_REF] Franc ¸ois | Bottrack: Tracking botnets using netflow and pagerank[END_REF], [START_REF] Hofstede | Flow monitoring explained: From packet capture to data analysis with netflow and ipfix[END_REF]. On one hand, it is considered privacy-preserving and scalable due to the little information which has to be collected and stored in comparison with full-packet capture. On the other hand, a single flow information is rather limited, only providing protocol, source and destination IP addresses, source and destination ports, number of packets, number of bytes, timestamp and duration. In order to work with this limited information, we used a specific modeling method to reveal meaningful knowledge, especially by merging multiple flow records in a unique representation. We propose a new graph-based behavioral model which represents causal relations among flows by automatically extracting frequent time-dependent relations among similar ones. Using this model, efficient detection is applied to extract malicious activities, especially those exhibited by botnets. Instead of simply raising alerts, BotGM identifies particular graphs whose the structure also eases the root cause analysis.

This paper has the following major contributions: 1) We develop a graph-based models of NetFlow records which, instead of focusing on spotting interactions among hosts, focuses on modeling dependencies among flows. The generic model can be finely tuned. 2) We apply an unsupervised graph mining approach to track botnets with the ability to trace root causes. Hence, no a-priori knowledge is assumed about botnet communication models. 3) We instantiate and evaluate our method on a recent dataset and assess its ability to detect individually infected hosts as well as groups of them. We rely on outlier detection and clustering techniques based off our models. We also discuss the impact of model parameter settings. 4) We compare our method detection accuracy with existing botnet detection techniques. The rest of the paper is organized as follows. Section II reviews and discusses related works. We detail our mining approach in Section III. We then present the experimental results on real botnet datasets in Section IV. Section V concludes and gives some future research directions.

II. RELATED WORK

Unlike our method which relies on modeling dependencies among flows, statistical analysis or machine learning algorithms have been mainly applied on features available in flow records or aggregated properties over a set of flows (duration, number of packets, number of flow records towards each destination, etc.). For example, in [START_REF] Li | A network behavior-based botnet detection mechanism using pso and kmeans[END_REF], the authors combined Particle Swarm Optimization (PSO) and K-means algorithms for botnet detection. In [START_REF] Zhao | Botnet detection based on traffic behavior analysis and flow intervals[END_REF], the authors classified network traffic properties based on time intervals using a decision tree classifier. They mainly used as features the properties of a flow in a given time window to evaluate how it evolves in time. CAMNEP [START_REF] García | An empirical comparison of botnet detection methods[END_REF] combines results from several anomaly detectors from state-of-the-art in order to improve accuracy. In the same work, rather than focusing on the analysis of single flow records, BClus first groups hosts based on their behavioral similarity.

Although our approach does not consider any particular type of botnet related traffic, the analysis of a specific traffic such as DNS activity has been investigated in several works. In particular by detecting co-occurrence of DNS requests from numerous hosts [START_REF] Choi | Botgad: Detecting botnets by capturing group activities in network traffic[END_REF], by tracking algorithmically generated domain names [START_REF] Bilge | Exposure: A passive dns analysis service to detect and report malicious domains[END_REF] or by using signal processing techniques over a large-scale and distributed dataset [START_REF] Kwon | Psybog: A scalable botnet detection method for large-scale {DNS} traffic[END_REF] for example. Botnets can be also detected by correlating other types of attacks (spam, denial-of-service, etc.) which can have been triggered from infected hosts as highlighted in BotHunter [START_REF] Gu | Bothunter: Detecting malware infection through ids-driven dialog correlation[END_REF]. In [START_REF] Wang | Behavior-based botnet detection in parallel[END_REF], the authors employed fuzzy pattern recognition and combined DNS and TCP flow analysis by considering packet counts and packet sizes Graph-based methods have been used in many papers either to model connectivity among hosts in the network [START_REF] Franc ¸ois | Bottrack: Tracking botnets using netflow and pagerank[END_REF], [START_REF] Nagaraja | Botgrep: Finding p2p bots with structured graph analysis[END_REF], among flows [START_REF] Wang | Flowrank: Ranking netflow records[END_REF], [START_REF] Jiang | Detecting p2p botnets by discovering flow dependency in c&c traffic[END_REF] or services [START_REF] Sofiane | Knowledge discovery of port scans from darknet[END_REF], [START_REF] Kandula | What's going on?: Learning communication rules in edge networks[END_REF]. In [START_REF] Strayer | Botnet Detection Based on Network Behavior[END_REF], the authors proposed a two steps approach which first detects potential malicious traffic flows with methods mentioned before and then correlate those ones in order to build a graph whose topology is finally analyzed. In [START_REF] Park | Fast malware classification by automated behavioral graph matching[END_REF], the authors proposed malware classification method based on maximal common subgraph detection. Their behavioral graph is obtained by collecting system call traces. However, their approach differs from ours since we are focusing on the analysis of passively collected network flows. Recently, HERCULE [START_REF] Pei | Hercule: Attack story reconstruction via community discovery on correlated log graph[END_REF] models heterogeneous log entries as vertices in the graph and generates connections based on defined correlation rules. The authors then applied graph analytics techniques to detect attack communities inside these graphs. Similarly, the authors in [START_REF] Satoru | Mining causes of network events in log data with causal inference[END_REF], mine network log data (e.g., syslog). They reconstruct causality of network events from a set of the time series of events and extract causal relations beyond co-occurrences in log messages in order to identify important network events and their causes.

Our approach BotGM is a passive traffic analysis method modeling dependencies among flows as graphs. It differs from aforementioned approaches because we do not focus on a particular type of traffic such as DNS and we do not assume any knowledge about bot behaviors, the detection of botnetrelated attacks or dependency rules among flows. In addition, we built a database of graphs to be compared, instead of a single mined graph, which allows to identify a sequence of flows as abnormal and the root causes of the anomaly.

Our work is close to [START_REF] Chen | Detecting botnet by anomalous traffic[END_REF] which consider sequences of flows to track botnets. In contrast, our method does not rely on the assumption that a periodic behavior in the botnet exists. Similarly, our work is close to [START_REF] Pellegrino | Learning behavioral fingerprints from netflows using timed automata[END_REF] and [START_REF] Hammerschmidt | Efficient learning of communication profiles from ip flow records[END_REF], where statistical relationships between flows are leveraged to obtain variants of automata as fingerprints. Hence our approach, not relying on periodicity or statistics of individual flow sequences, is more generic.

III. SYSTEM DESIGN

A. Overview

Our goal is to establish probable causal relationships among flow records which can be compared to track abnormal activities and their root causes. As a preliminary step, flow records are divided into time windows. The size of time window is controlled through a parameter ω.

Then, the process consists of six components as illustrated in Figure 1.

1) Event extraction. To build causal models, NetFlow records are considered as events. Each individual flow is transformed into an attribute-based event where each attribute is directly derived from standard NetFlow features such as IP addresses or ports. In addition, selected attributes are divided in two categories: keys and values. Fixing a key, values are then used for building a graphbased fingerprint in the next processing steps. In the example of Figure 1, keys are the source and destination IP addresses while respective ports are the values. 2) Sequence extraction. Sets of sequences of states from events are extracted to model the full behavior of hosts. Events sharing the same key, such as source and destination IP address, are used for building individual sequences whose states are represented by the value attributes. In Figure 1, sequences of pairs of source and destination ports are built for each key (the couple source and destination IP address). 3) Graph construction. This step allows us to construct a graph from each sequence. This reduces the behavioral representation from a long sequence to a graph that aggregates redundant patterns while still keeping all existing interactions. It is a primordial step for scalability. As shown in Figure 1, the first sequence has been reduced to three vertices. 4) Outlier detection. Through pair-wise comparisons among graphs, the outliers are extracted. It is thus possible to track back to the associated keys. For example in Figure 1, the couple of source and destination IP addresses (147.32.84.138, 147.32.80.9) represents the outlier graph G 1 . As a result, the communication flows between these hosts are considered as abnormal and e.g labeled as botnet communication.

B. Event extraction

Let F = f 0 , . . . , f N be a set of flows where each f i is described by a set of attributes as illustrated in Table I. Each flow will be transformed into an event assuming a set e 1 ={ 147. [START_REF] Hang | Entelecheia: Detecting P2P botnets in their waiting stage[END_REF]

G 2 G 0 G 1 Analysis (4) Graph Comparison G 2 G 0 G 1 G 2 G 0 G 1 E d i t D i s t a n c e G 1
(3) Graph Construction of selected attributes (keys and values as introduced in the previous section). Let Att be the set of flow attributes. We define:

• K ⊆ Att a set of attributes to be used as keys,

• V ⊆ Att a set of attributes to be used as values. Regarding Table I, f i is defined as follows:

f i = {ts i , dur i , proto i , sip i , sport i , dip i , dport i , tos i , totpkts i , totbytes i }
Such a representation can be extended depending on the data sources.

Definition For each f i , the event e i is defined as e i = (ts i , k i , v i ) consists of a the same timestamp ts i of the flow f i and a compound key k i and value v i composed respectively from the set of attributes K and V of the same flow f i .

As an example, having the flow:

f 0 = {11

C. Sequence extraction

After the extraction of events, dependencies among events are built based on keys and timestamps to identify successive events which are part of a some global action (e.g. an attacker performing multiple steps of an attack). To transform the set of events into sequences, events are first grouped using shared key attributes. For example, all events (i.e. flows) with same source and destination IP addresses are merged into a single sequence as previously illustrated in Figure 1. This sequence representation allows to characterize the order of events of a specific IP address connecting to a destination IP address.

Definition Assuming E = {e 0 , . . . , e n} the set of events of the considered time windows, a unique sequence S i is built for each unique k

i , k i ∈ ej ∈E k j such that S i = [v 0 i , . . . , v m i ]
where:

s k i ∈ E ∀(e t = v k i ∈ S i , e u = v l i ∈ S i )k t = k u ∀(e t = v k i ∈ S i , e u = v l i ∈ S i , k < l)ts t < ts u (1)
The first condition guarantees that a sequence is built from extracted events. The second one guarantees that all events of a sequence shared the same key and the last one ensure that they are ordered by time using their respective timestamp attribute ts. It is worth mentioning that events sharing both keys and values will appear individually in the sequence.

D. Construction of behavioral graphs

A behavioral graph is constructed from a sequence S i , i.e. originally extracted from flow records sharing the same userdefined keys k u that occur in a given time window.

It is a directed graph that represents successive relationships between events of an event sequence. Therefore, each unique element of a sequence appears once while it can be observed multiple times in the sequence. Thus, a cycle in the graph indicates successive repetitive events.

Definition Assuming a given sequence S i = [v 0 i , . . . , v m i ], a behavioral graph over a set of event values V is a labeled directed graph G = (V G , E G ):

• The vertex V G is the set of vertex of unique events in the sequence S i sharing the same values

V = v k i i=1...m (2)
• The edges E G are derived from dependency rules. Let v t i and v u i two vertices of G, an edge exists, i.e, (v t i , v u j ) ∈ E, if and only if those events appear consecutively at least once in S i :

∃v k i ∈ S i , ∃v l i ∈ S i , k + 1 = l (3)
By compressing sequence information, behavioral graphs ease interpretation of long sequences of events. Intuitively, considering a particular time window and K (as an example source IP address), an edge between two vertices assumes a causal dependency and a path between two nodes represents a causal path among events where each of them is representative of similar events (same values but at different time). Since the flows of an host or an application can be intertwined, our built causal dependency may seem unadapted. However, a good tuning of the key K to be used allows to reduce the flows used when building such relations and so limit this effect. In addition, BotGM leverages a graph structural analysis based on the edit distance (detailed in the next section) which actually helps to reduce the impact of noise, i.e. incorrect dependencies.

E. Graph analysis

BotGM constructs and maintains a behavioral graph for each unique keys (e.g. source and destination IP addresses in the previous example). The challenge is to mine the graphs in each time period in order to detect, find and quantify suspicious behavior which deviated to another behavior.

1) Graph edit distance: Graph edit distance (GED) is a flexible fault-tolerant similarity measure for graphs. The fault-tolerant similarity means that the measure accounts for noise, i.e. structural deformations. Exact approaches (subgraph isomorphism) may not be adopted. The edit distance between two graphs g 1 g 2 is defined by the minimum set of edit operations that are necessary to transform the graph g 1 into g 2 using elementary edit operations [START_REF] Bunke | Inexact graph matching for structural pattern recognition[END_REF], [START_REF] Sanfeliu | A distance measure between attributed relational graphs for pattern recognition[END_REF]. An edit operation is either an insertion or deletion for both vertices and edges as well as a relabelling of a vertex. A cost function c(o i ) associates a cost to each edit operation o i and the edit distance between two graphs g 1 and g 2 is then the minimum cost related to the set of operations that transform g 1 into g 2 .

d(g 1 , g 2 ) = min (o1,...,o k )∈γ(g1,g2) n i=1 c(o i ) (4)
where γ(g 1 , g 2 ) is the set of edit operations that transform g 1 into g 2 . In our case, without prior knowledge, each has a cost of one, c ( o i ) = 1

F. Outlier detection

We analyzed the pair-wise distances between the constructed graphs by means of a statistical outlier detection technique. Let O denote all the average distances between a given graph and all others. Assuming R, a set of all graph at a particular time,the value of the average distance of the graph g i ∈ Ris as follows:

O i = gj ∈R,gj =gi d(g i , g j ) |R| -1 (5)
A well used and simple statistical technique for outlier detection is the inter-quartile method [START_REF] Chandola | Anomaly detection: A survey[END_REF]. First the quartiles of O are computed, Q 1 , Q 2 (median) and Q 3 .

Definition Assuming the average distance distribution O computed at a given time t, a graph g i is related to a botnet activity if O i > Q 3 + α × IQR Usually, we set α = 1.5 but fine tuning of this parameter is addressed in section IV. As a result, the outlier behavioral graphs are thus considered as the abnormal behavioral graphs. They show the infrequent and the uncommon behaviors of flows belonging to the same keys (such as source and destination IP addresses) in comparison with others.

IV. EXPERIMENTAL RESULTS

A. Dataset

We used the publicly available CTU-13 dataset of different botnet families [START_REF] García | An empirical comparison of botnet detection methods[END_REF]. The NetFlow records include both normal flows, C&C communication and attack traffic such as spam or DDoS. The dataset contains 13 separate scenarios whose general characteristics are described in Table II

B. Parameter settings

Our proposed framework depends on three main parameters which will vary over the next experiments in order to evaluate the accuracy, the robustness and runtime performance of our approach under their variations:

• ω: The size of the time window is an essential parameter.

When it increases, sequences will be longer, emphasizing the importance of transforming the latter in a reduced representation, i.e. behavioral graphs. In our reported experiments, this parameter ranges between 1, 5, 10, and 20 seconds.

• K: The set of flow record attributes defined as key guides how to build behavioral graphs. Source and destination IP addresses have been widely used in the intrusion detection domain as being usually representative of the attackers and the victims. For botnet detection [START_REF] Hang | Entelecheia: Detecting P2P botnets in their waiting stage[END_REF], [START_REF] Beigi | Towards effective feature selection in machine learning-based botnet detection approaches[END_REF], the primary value comes from the possibility to quantify the number of distinct connections. In this paper, we consider two cases. First, the global behavior of an host can be investigated by only using the source IP address (sip). Second, a more fine-grained approach will assess the connection from one host to another one using both source and destination IP address (dip). Finally, the protocol (TCP, UDP), proto, is always used (event if not mentioned) to avoid mixing TCP and UDP ports in behavioral graphs.

• V : The set of flows record attributes defined as values to extract sequence and build graphs is primordial. They represents attributes of the graph vertices. In this work, we are particularly interested in dependencies of services leveraged by the hosts. Hence, we propose to use either both source (sport) and destination (dport)

ports, a single port, or the minimum value (minport = min(sport, dport)). The rationale behind this second choice is to potentially retrieve the most meaningful port in most of cases, i.e. a reserved port for a well-known and/or standard application.

C. Extracting abnormal behavioral graphs

Based on the example of dataset 13 (Virut botnet), this section illustrates how an analyst can rely on outlier detection and clustering to extract abnormal graphs. To perform this extraction, we set K = (sip, dip, proto), V = (sport, dport), and ω = 5s.. An expert can then analyze corresponding graphs and even sort them regarding the distance of those outliers to prioritize his analysis. Unlike using a fixed threshold, our outlier detection method adapts dynamically the threshold, which is necessary regarding the variation of the distance as depicted in Figure 2. As an illustrative example, Figure 3 highlights two outliers which are true positive, i.e. represent botnet flows. In Figure 3(a) represents a bot performing a vertical scan on another host, i.e. trying to discover open ports and therefore accessible services. Although detecting such scans can be done using dedicated and probably less complex methods, this shows the generecity of our method to to be also applicable in this case. At a first glance in Figure 3(b), the abnormal activity is not so visible as it seems that a host is contacting DNS (e.g. to request domain names). However, the same source ports are re-used multiple times as highlighted by the loop in the graph, which is highly improbable within a 5 seconds period. Hence, the structure of the graph itself is discriminative in that case.

D. Automated detection of botnet

In one hand, the previous section shows the ability of BotGM to extract abnormal graph candidates on specific samples and show how an analyst can thus retrieve the graph allowing her to analyze root cause. In the other hand, this section is dedicated to assess how botnets can be automatically detected. To achieve that, we employed the outlier method and computed standard metrics (false positive rate, true positive rate and accuracy).

However, it is worth to mention that the ground-truth is composed of labeled NetFlow records while the output of our method are supposedly abnormal graphs, potentially mixing both normal and botnet flows. For labeling a graph, and for validation purposes only, we have thus to traceback botnet original flow records which have been used for sequence and graph construction.

For a given time window, BotGM leads to the construction of n graphs: {g 1 , . . . , g n }. For each g i , our method will assign a class c i equal to 1 when the graph is an outlier (botnet) or 0 otherwise (benign). In addition, each g i is built based on an original list of events created from flow records. If at least one of them has been labeled as botnet in the original dataset, we assign a label l i = 1, otherwise l i = 0. In fact, those labels constitutes our ground-truth.

Relying on classes and labels, standard detection performance metrics are computed:

• Accuracy:

Acc = |{g i , c i = l i = 1}| + |{g i , c i = l i = 0}|
N As highlighted by the formula, the accuracy indicates within a single value the ability to classify properly the graphs as normal or as benign. A bias may be however introduced with unbalanced dataset similar to the one we used. Indeed botnet is not the major activity that is observed as highlighted in Table II and is representative of the reality. That is why true and false positive rates are important complementary metrics to consider.

• True Positive Rate (TPR):

T P R = |{g i , c i = l i = 1}| |{g i , l i = 1}|
• False Positive Rate (FPR):

F P R = |{g i , c i = 1, l i = 0}|
|{g i , l i = 0}| These metrics are computed per time window for all datasets and then we compute their average. Figure 4(a) shows how accuracy changes with varying parameters: time window size (ω) and attributes used to build the graphs (K and V ). When the time window is too small, the captured activity is limited to a few sets of flow records merging into a single graph which is not representative of the activity of the IP addresses. For example, a botnet may open multiple connections for C&C and attacks, but this may not be observed at a very short time scale. However, even if observed, the related activities can last for several seconds and longer, partial representative behaviors can still be properly identified by our method with an accuracy around 90% using five or ten seconds. As an example, Acc = 0.923 when ω = 10s, K = (sip) and V = (sport, dport).

Differences can be noticed among the cases. On one hand, using only the source IP addresses leads to better results. It allows to represent 1-to-n interactions of a host which are intuitively more significant to the behavior of a host or an application in a today's Internet. Actually, a bot usually opens multiple connections to synchronize and perform malicious activities. On the other hand, using both ports as values in events is beneficial since they allow better characterization of graphs.

We use a ROC (Receiver Operating Characteristic) curve as depicted in Figure 4(b) to jointly evaluate the variation of TPR and FPR according to the different configuration. The results show that for false positive rate of less than 10%, the detection rate is above 95% as the time window size increases. Again, using both ports in values V provides better results. As highlighted in the plotted results, almost no false alarms are raised while a TPR rate of 83% can be achieved in the best cases.

E. Runtime evaluation

All experiments were conducted on a Intel(R) Xeon(R) CPU E5-2420 v2 @ 2.20GHz with 62 GB main memory running on Ubuntu 16.04.2 LTS (GNU/Linux 4.4.0-59-generic x86 64). As depicted in Figure 5, the processing time logically grows with increasing window width for two reasons. First, the number of candidates keys (K) for constructing sequences and graphs increases, leading to more pair-wise pattern matches. Second, even if the graph representation avoids the drawback of the expansion of dependency rules in the sequence, previously unseen values in values (V ) create new vertices, thus leading to larger graphs to analyze. Also, when selected keys (K) or values (V ) are more fine-grained, same phenomena occurs with same consequences. Assuming the particular cases of using the protocol and IP addresses for keys, i.e. K = (proto, sip, dip), and both ports as values, i.e. K = (sport, dport), or only destination port as value, i.e. K = (dport), Figure 6(b) shows the average number of graphs and vertices per graph in each time window while varying the window size, ω. It confirms the two reasons mentioned above but highlights that the increase of vertices in graphs is limited since set of values remains stable when ω ≥ 5. Moreover, Figure 6(a) shows the number of individual flow records (original data). In comparison with Figure 6(b), our method greatly reduces the size of data to handle for analysis and so helps to improve scalability. Although the cost of preprocessing and comparing graphs has to be considered, Figure 5 demonstrates that the processing time is lower than the window size, ω, when the latter is lower than 10 seconds (ω < 10). Assuming the best configuration trade-off established in Section IV-D with ω = 5, our approach will be practicable to return results, and so raise alerts, in near real-time.

F. Comparison with other detection methods

To evaluate our contribution better, we compared BotGM with BClus, CAMNEP, and BotHunter described in Section II. These algorithms are presented as the most promising ones in [START_REF] García | An empirical comparison of botnet detection methods[END_REF]. The comparison is based on different dataset scenarios (1, 2, 6, 8 and 9) whose the results have been reported in [START_REF] García | An empirical comparison of botnet detection methods[END_REF]. [START_REF] García | An empirical comparison of botnet detection methods[END_REF] and compared to BotGM.

As shown in Table III, the best accuracy among these algorithms achieves 50% while ours achieves up to 95%. For fairness, it is important to point out and emphasize that BotGM classifies graphs rather than single flows like other algorithms and, as explained in Section IV-D, a single graph is considered as true positive while it have been inferred from normal and botnet flows. Although fine-grained classification (i.e. per individual flow record) is more prone to classification errors (and so lower accuracy), results obtained with BotGM are still very competitive.

V. CONCLUSION This paper introduced BotGM, a new approach for tracking botnet activities with passive network monitoring. It relies on a behavioral graph modeling of NetFlow records. However, rather than building a single massive graph being difficult to analyze, BotGM creates a collection of smaller graphs for comparison with each other and thus indirectly comparing the behavior of end-hosts. The proposed approach combines unsupervised techniques to detect outliers and to group similar behaviors. Hence, in addition to detect botnet activity, BotGM offers several advantages. Through our experiments, we illustrated how BotGM can raise alerts and extract relevant suspect behavioral graphs. We compared our method with recently proposed techniques on a public dataset and results underlined its competitiveness and usability in a real-time manner.

Our future work consists in building signatures, a set of single behavioral graph equivalent to a cluster of graphs, in order to reduce the knowledge database. As a result, the time complexity of BotGM will be reduced.

Fig. 1 :

 1 Fig. 1: Processing steps of NetFlow records in BotGM.

Fig. 2 :

 2 Fig.2: Outlier graphs marked with a dot in a set of selected widows of size 5 seconds.

Figure 2

 2 Figure 2 represents a box plot of outlier distances calculated from Equation 5 in Section III-F with α = 1.5. In this figure, dots represents the outliers. The figure represents a sample of time windows (between 9 and 30) where the botnet is active and have been identified over multiple time windows.An expert can then analyze corresponding graphs and even sort them regarding the distance of those outliers to prioritize his analysis. Unlike using a fixed threshold, our outlier detection method adapts dynamically the threshold, which is necessary regarding the variation of the distance as depicted in Figure2.

Fig. 3 :

 3 Fig. 3: Abnormal behavioral graphs of a bot performing a vertical scan over TCP (a), and a bot DNS activity over UDP (b).

Fig. 4 :

 4 Fig. 4: Detection performance of BotGM regarding (a) average accuracy and (b) ROC curves measuring TPR against FPR.

Fig. 5 :

 5 Fig. 5: Processing time in seconds for graph and sequence construction while varying ω. The y-axis is in log scale.

  Window width ω (Sec) (a) Average number of flow records within a single time window while varying window size (ω).

  size (Avg.) # of vertices (Avg.) Window size ω (Sec) # graphs, V=(sport, dport), # vertices, V=(sport, dport) # graphs, V=(dport) # vertices, V=(dport) (b) Average number of graphs and vertices (per graph) within a single time window while varying window size ω.

Fig. 6 :

 6 Fig. 6: Volume of data while varying windows size ω.

  .84.165 , 147.32.80.9 } e 2 ={ 147.32.84.138 , 147.32.80.9 } e 3 ={ 86.144.192.16 , 147.32.84.229 } e 4 ={ 147.32.84.138 , 147.32.80.9 } e 5 ={ 147.32.84.165 , 147.32.80.9 } e 6 ={ 147.32.84.165 , 147.32.80.9 } Sip,Sport,Dip,Dport,ToS,TotPkts,TotBytes 11:09:44,0.422243,udp,147.32.84.165,1025,147.32.80.9,53,2,182,71 11:09:49,0.201243,udp,147.32.84.165,1291,147.32.80.9,53,2,553,78 11:09:49,0.000185,udp,147.32.84.138,51724,147.32.80.9,53,2,214,81 11:09:49,30.08,udp,86.144.192.16,12365,147.32.84.229,13363,8,542,302 11:09:49,0.000223,udp,147.32.84.138,51757,147.32.80.9,53,2,214,81 11:09:51,0.336250,udp,147.32.84.165,1025,147.32.80.9,53,2,215,71 11:10:38,0.131772,udp,147.32.84.165,1025,147.32.80.9,5634,2,283,71

	Flow Records		Events
	Timestamp,duration,proto,(1) Event Extraction	{ 1025 , 53 } { 1291 , 53 } { 51724 , 53 }
			{ 12365 , 13363 }
			{ 51757 , 53 }
			{ 1025 , 53 }
			{ 1025 , 5634 }
			(2) Sequence
	Sequence database	Extraction
	S 2 S 1 S 0	(86.144.192.16, 147.32.84.229) (12365,13363) (147.32.84.165, 147.32.80.9) (1025,53) (1291,53) (1025,53) (1025,5634) (147.32.84.138, 147.32.80.9) (51724,53) (51757,53) Sequence Key
	Key	Graph
		(1025,5634)

Graph database (147.32.84.165, 147.32.80.9) (147.32.84.138, 147.32.80.9) (86.144.192.16, 147.32.84.229)

TABLE I :

 I NetFlow attributes.

  .

	ID	#flows	Duration #Bots #Bot flows (hours)	#unique IP addresses
	1 2 3 4 5 6 7 8 9 10 11 12 13	2,824,637 1,808,123 4,710,639 1,121,077 129,833 558,920 114,078 2,954,231 2,087,509 1,309,792 107,252 325,472 1,925,150	6.15 4.21 66.85 4.21 11.63 2.18 0.38 19.5 5.18 4.75 0.26 1.21 16.36	1 1 1 1 1 1 1 1 10 10 3 3 1	41,270 21,022 32,031 3,350 912 4,714 67 6,506 185,716 113,737 8,865 6,391 40,362	607,534 442,448 434,947 186,229 41,642 107,325 38,192 383,764 367,239 197,806 41,910 94,419 315,749

TABLE II :

 II Datasets overview.

TABLE III :

 III Accuracy of different algorithms evaluated in

ACKNOWLEDGMENTS

This work was partially funded by HuMa, a project funded by Bpifrance and Region Lorraine under the FUI 19 framework. It is also supported by the High Security Lab hosted at Inria Nancy Grand Est (http://www.lhs.loria.fr).