- Network traffic identification is the first and most important step in network management and security. Numerous methods introduced by researchers. One solution depends on processing both packet header and payload, which is costly from both time and processing aspects. Another solution depends on the flow of statistical information such as packet header length, flow duration. Blind classifiers are not accurate yet very fast and do not violate privacy. Machine learning fills the gap between accuracy and time by using the blind classifier method and comparing the results with grand truth then adapting and increasing the accuracy. K-NN is used widely for its effectiveness and simplicity. However, a major drawback of K-NN is its dependency on the training set, being a lazy classification algorithm with no classification model to build. In this work, we aim first at assessing the KNN algorithm in traffic classification. Then we introduce a new deficiency, related to the training samples distribution in the n-dimensional space we measure and propose an enhancement for K-NN adapting to the new problem and outperforming native K-NN classifier. We weight the classes, not the instance, based on the intersections of class clusters in the dataset. Finally, we propose a new Class Weight based K-NN Classifier (CWKNN), an enhanced K-NN algorithm that can easily adapt to the newly explored training set deficiency.
The ability to identify network applications is centric to many
network management and security tasks, including quality of
service assignment, traffic engineering, content-dependent
pricing, resource allocation, traffic shaping, and others. With
the proliferation of applications, many of them using different
kinds of obfuscation, traditional port-based classification has
long become obsolete.
inspection as in [
On the other hand, blind classifiers do not inspect the payload and have the potential ability to deal with these obstacles, at the expense of an acceptable sacrifice in accuracy. However, less accurate, the so-called blind methods are preferred in most environments because they guarantee the users’
privacy, have the potential to classify encrypted communications and usually require less computational power.
Most of these techniques are based on traffic attributes at the network and transport layers, such as packet sizes and interarrival times. Due to the problem dimensionality, Machine Learning (ML) techniques can be used in the classification context. ML classification is considered an instance of supervised learning, i.e., learning where a training set of correctly identified observations is available. An algorithm that implements classification, especially in a concrete implementation, is known as a classifier. In machine learning, the observations are often known as instances, the explanatory variables are termed features (grouped into a feature vector), and the possible categories to be predicted are classes. The term "classifier" sometimes also refers to the mathematical function, implemented by a classification algorithm that maps input data (traffic attributes in the traffic classification case) to a category (Application type like HTTP, NTP, DNS…etc.).
There is a relevant research activity in network traffic
classification, employing different Machine learning
approaches. Among them, K-NN was used in several papers
[
Cover and Hart first proposed K-NN (K Nearest Neighbor)
algorithm in 1968. The algorithm itself is simple and
effective, which is a typical lazy or instance-based learning
algorithm. It is not essential for the classifier to use the
training set to train and the training time complexity is 0.
With K-NN, the function is only approximated locally and all
computation is deferred until classification. The principle of
K nearest neighbor classification algorithm
(Kneighborhood) is that if the K samples in the eigenvalue space
most closed to the sample to be identified almost belong to
the same class, we determine this sample also belongs to such
a class. The key difference between classification and
regression tree in [
In section two, we included the most significant papers available in the literature. In section three, we explained the known knn problems which is assessing knn in classifying the datasets in each application. In section four we introduced the new problem and we proposed and applied a solution. In section 5 we will describe briefly the Experimental design (for the lack of space). And provide the results of this work. In section 6 there is a conclusion.
A large number of traffic classification approaches exist in the
literature, some are based on deep packet inspection, which
discloses the packet payload and raises privacy concerns,
while others rely on discriminative traffic attributes at the
network and transport layers, such as packet sizes and
interarrival times. This emergent research needs to arise since
IANA Port-based classification in [
In [
Known DPI methods were enhanced in [
III.
K-NN CHALLENGES
The K value has a major impact in determining the nature of
the instance to be classified, selecting a small value of K
means that noise will have a higher influence on the result and
a large value make it computationally expensive as explained
in [
The distance function plays a major role in K-NN
classification accuracy. Researches constantly enhance
distance functions and add a new attribute to increase
accuracy. To determine the proximity of two objects in the
feature space, any distance type method can be applied.
(Euclidean, Manhattan, Minkowski, etc.) yet researcher must
test different distance types for each dataset application . In
[
An outlier is a data point that differs significantly from other observations. An outlier may be due to variability in the measurement or it may indicate the experimental error; the latter are sometimes excluded from the data set. Outliers, when found in the training dataset, can decrease the classification accuracy of KNN voting.
Finding such exception has received much attention
in the data mining field. For example, one of the
solutions used in [
Another Solution is weighting each Instance which is quantifying each Instance contribution in the Classification process. And adding that number to the voting process.
Authors in [
A drawback of the basic "majority voting" classification occurs when the class distribution is skewed. That is, examples of a more frequent class tend to dominate the prediction of the new example because they tend to be common among the k nearest neighbors due to their large number.
One way to overcome this problem is to weight the classification, taking into account the distance from the test point to each of its k nearest neighbors. The class (or value, in regression problems) of each of the k nearest points is multiplied by a weight proportional to the inverse of the distance from that point to the test point.
Another Intersecting application of weighting is
Introduced by authors in [
WKS algorithm boost the weight of instances surrounded by “friendly neighbors” and the decreases the weight if the instance is surrounded mostly with different class members. They were able to decrease the error rate that ranged from 0.007 to 0.025 for 10 different datasets. We find that their work was the most significant to our algorithm so we implemented their algorithm in the experimental setup we built and compared the results between the native, WKS, and CWK-NN.
IV. PROPOSED ALGORITHM (CLASS WEIGHT K-NN) As mentioned previously, the dataset may have various deficiencies, most commonly, outliers (samples with errors) and, imbalance in the dataset classes (some classes are predominant over the others). To address these deficiencies, weighing samples (outliers problem), or clustered samples (imbalance problem) are among the most common solutions found in the literature.
To explore and understand further KNN training set deficiencies, let us consider the ideal training set for KNN, as derived from the way KNN classifies best any unknown sample.
In a very ideal training-set situation, space is made of one representative sample for each class so that any unknown point will fall in the n-dimensional (n is the number of features or attributes) “exactly” (i.e. coincides) in the location where only one of the class samples exist.
In real training-sets, however, the location of the unknown point and existing sample can rarely coincide. They might rather be close enough for KNN to be able to derive the classification decision through majority voting. When each class has many samples, KNN voting described earlier will make the assumption about the eventual class of the unknown point.
As such, in a less or near-ideal training-set situation, an unknown point may fall then within the zone in the ndimensional space where only members of the same class surround it, in this case, KNN voting will be more reliable since the unknown point shall undoubtedly belong to the same class of its surrounding neighbors. Following the same reasoning, the closer the samples are to the class centroid (i.e. higher density near the centroid), the more reliable KNN decision shall be.
To illustrate this concept, Figure 1 shows, the distribution of labeled training points. The set of labels belonging to each class (Classes 1, 2 and 3), are clustered into circles for n=2 or spheres for n=3. The point labeled with X is the unknown point. Class cluster radius is defined by the standard deviation of the training samples distances from the centroid, and the distance between two clusters is the distance between their centroids. For example, D12 denotes the distance between centroid C1 of class 1 and C2 of class 2 Fig. 2. ideal distribution for a KNN-based classifier
Fig 2. Shows a near-ideal distribution where the clusters are disjoint and do not intersect at all, mimicking the near ideal situation. In this case, a test point falling into only one of the class clusters will lead to a highly deterministic KNN voting decision since all nearest neighbors to X will have the same label, class 2 in this case.
In the case where unknown points fall out of the radius of any of the existing clusters, KNN voting decision still applies however with less reliability. In other words, the points falling in the intersections or between zones are those for which KNN decision will be controversial (i.e. not all of the nearest neighbors have the same class label), which will decrease the overall reliability of KNN classification decisions when compared to the ideal training-set distribution in Fig 2.
To highlight more on this aspect and for simplicity, in Fig3. we introduce a dataset having only four classes. Each instance has only two attributes. Please notice that the classes are balanced yet two classes is intersecting.
Consider the reliability of the KNN classification decision when classifying the instances that belong to collide classes. The reliability of KNN decisions is very weak. yet for the classes not intersecting the reliability is supposed to increase evidently for training sets having the distribution similar to class one and class 3. Since the reliability of KNN decisions for points, falling inside the clusters will be higher than those falling outside any of the existing clusters or at the intersections. Except for the differences in the neighbors’ distances considerations, the reliability of the classification decision shall be quite the same for points falling outside any of the existing clusters or at the intersections in both cases.
Therefore, when the circles representing class clusters are more distant and dense as in Fig2, KNN classification is supposed to become more reliable, at least for the unknown points falling within class clusters. On the contrary, having too close cluster centroids with lower density (i.e. more spread distribution) will result in additional intersections between clusters, which will decrease the reliability of KNN classification for the unknown points falling on the intersecting zones between classes (e.g. C2 and C3 in Fig 1.).
In other words, when class clusters have no or fewer intersections, the training dataset shall become closer to the “near-ideal distribution” in Fig 2. . Thus leading for better classification results.
Despite the fact that imbalanced sets are likely to have class clusters intersections, having one characteristic (i.e. class imbalance or class intersections) does not necessarily imply the other:
A dataset can be imbalanced but classes do not intersect A dataset can be balanced but classes do intersect
The latter case, depicted in Fig 1. is the most relevant to our approach where we measure the new KNN training set deficiency related to relative points’ distribution within the ndimensional space rather than their relative numbers. To the best of our knowledge, “Class explored clusters intersections” is not yet
as a deficiency for KNN training sets, nor was it regarded in separate from the imbalanced class problem.
Up to this level, we have theoretically explained and discussed what we think to be ideal for KNN training set distribution and speculated about its impact on KNN classification. However, most of the presented assumptions have to be proven through experimentation.
For this reasons, we attempt next to measure and quantify the value of “class clusters intersections” inside
KNN training sets. Then, we attempt to derive a new KNN classifier in order to experimentally demonstrate the importance and impact of considering of class intersections or training points distribution in the training set on KNN classification.
A Class Weight based KNN Classifier or CWKNN is simply a KNN classifier that takes into consideration the samples distribution or class intersections described earlier. As mentioned, intersections should be expressed in terms of newly defined class weights. The WCKNN algorithm is a two-phase process that includes the training and the testing described as follows: 123
Calculate the variance instance of each class.
Calculate the distance between centroids.
if the distance is larger than the sum of two radiuses the classes does not intersect and the weight of the two classes remain the same. Else if the distance between centroids is smaller than the sum of radiuses there is an intersection and the weights of the classes must be decreased. 4
Assign the weight calculated for all instances.
Training phase: For each class we add two instances the first instance is The centroid, and second instance represents the avarge distribution of the class in the n dimensions (where n is the number of attributes).
The centroid is the instance core instance having the average value of all attributes. The radius is the distance between centroid and the instance having the variance of value for all attributes.
Thus it’s the allowed normal margin for class distribution in the n dimensional space. All the instances outside the threshold is considered as outliers and they are not significant comparing to the majority of the class instances. Distances between centroids are accordingly calculated. To formalize how CWKNN operates in the training phase refers to simply formalize how class weights are calculated. The main idea of setting the class weights is that classes who do not intersect have less error margin. We boost the weight of all of Instances having the same class. However, classes with intersections should have decreased weights.
Let M be the total number of classes in the dataset For each class i, find the distance between the class centroid and all other centroids.
= 1 + − Equation 2 =
∑ =1 , 1] (1 + aij is a discrete value indicating if there is an intersection Ai is a value measuring the level of intersections between class i and the rest of classes.
As shown in equation 1, if Ai, denoting the number of class i’s intersections with other classes, increases then Wi should decrease.
1
(since each class intersects with itself at least)--when the class is disjoint from all other classes-- and a maximum value for Ai=1 when theoretically it intersects with all other classes.
Intersecting classes are not thus explicitly punished, but rather, they are not rewarded higher weights.
Test phase: each training sample belonging to class i is assigned the weight of the class. The weighted voting of K neighbors is combined, and the weight of each neighbor is the function of the class to which the neighbor the training phase.
As per equation 1, the class weight decreases exponentially when the value of the number of intersections increases towards M.
The contributions of the classification for the training sample belonging to a good class is regulated thus by the weight value when the numbers of intersections get considerably higher. The completion of traffic these accomplishment of some additional objectives related to building the experimental setup.
In this experiment we used a server that has 16 GB of ram , 2 Intel(R) Xeon(R) 2.66 GHz processors with 4 cores each. With Ubuntu 18.01 OS to capture network traffic and converting the flows into a dataset. We captured network flows by using tcp dump. then we used nDPI to detect the real nature of the flow traffic and to set the flow attributes. was collected the flow , over an extended period of time spanning around 3 days and totaling around 1.2 GB of real traffic. we have excluded the encrypted traffic. The 3 days span of collecting the data was due to our desire to collect, a large dataset for testing and classification and then we were obliged to use a part of the data collected 51752 labeled flow for the lack of resources. The part was selected randomly. Knn classification algorithm stores all training dataset in the in the RAM.
After obtaining the dataset we have used weka open source software to add wks and our algorithm.
To validate the obtained Result we have used many other datasets from the weka library. We will only include the results from three dataset for the lack of time.
CONCLUSION
n-dimensional space and classes’ intersections.
We weighted classes accordingly in the training set. Then, we suggested class weighting scheme, then we derived a newly proposed
Class
Weight based
KNN
Furthermore, we have assessed KNN algorithm in traffic classification contexts through an experimental test-bed that we build for this purpose.
Our tests on real captured and Internet-based datasets showed up top 7%
enhancements in the classification results, compared to the native and samples’ weighted KNN approaches.
Moreover, and as per our testbed, we showed that K=3 and Euclidean distance type can lead to more than 98% of overall Tp in computer traffic classification context.
VII.
REFRENCES
J. Khalife J. Verdejo, and A. Hajjar A multilevel taxonomy and requirements for an optimal traffic-classification model [Journal]. [s.l.] : Int. Journal of Network Management , 2014. - 2 : Vol. 24.