Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I recently read a paper which stated that "Traditional anomaly detection algorithms require a set of purely normal data from which they train their model" [1]. But as in K-means, or other unsupervised clustering algorithms, what does this mean? How they work if there is only one cluster? Their point is that they can cluster different unlabeled data classes.

Another paper says that there are two assumption in unsupervised techniques: 1. there should be much more normal traffic than attack traffic, and 2. attack traffic should be different than normal traffic [2]. Why? K-means can separate two sets of the same number of elements.

References:

[1] Page 2 of "Intrusion detection with unlabeled data using clustering", Leonid Portnoey, Eleazar Eskin, Sal Stolfo, DMSA 2001.

[2] Section 3.3 of Jose F. Nieves, "Data Clustering for Anomaly Detection in Network Intrusion Detection", Research Alliance in Math and Science, 2009.

share|improve this question
    
One justification for the two assumptions that I can't understand: "The basic idea is that since the intrusions themselves are both different from normal and rare, they will appear as outlier in data which can be detected." –  Yas Nov 18 '12 at 12:05
    
or this: "under first assumption the normal instances should form large clusters compared to intrusion". so what? what role the size of cluster has here? As I know, normal cluster(s) should be label manually. The raduis of cluster could not be found from algorithms. –  Yas Nov 18 '12 at 12:13
4  
Providing a link to, or at least the title of, the papers you're referring to would be nice. –  Peanut Nov 18 '12 at 14:57
    
I added the references to my question. Thanks for your comment. –  Yas Nov 19 '12 at 6:03
    
@YasserMZadeh, I'm surprised that you didn't provide a link to the papers (especially since all it took in case was a web search, and after several folks asked for it). I think it's the least you can do, if you are going to ask other people to volunteer their time to help you understand the papers. I did it for you this time... but in the future, if you want to ask others for help, I do expect you to put in more effort of your own first. See also How to ask. –  D.W. Nov 19 '12 at 20:38
show 2 more comments

1 Answer

up vote 1 down vote accepted

This is a puzzling question. The explanation is provided right there in the paper, in some cases right near the quotations you provided. Perhaps it is worth re-reading the papers through a second time, as it sounds like you might have missed a few details on the first pass.

On the first quotation ("traditional anomaly detection algorithms require..."):

  • Well, that's just how traditional anomaly detection algorithms work. Those algorithms work by starting with a training set of normal traffic, and then they use the training set to build a model of what normal traffic looks like. For this to work right, you need a large collection of normal traffic. As the paper states in the very next sentence, "if the data contains some intrusions buried within the training data, the algorithm may not detect future instances of these attacks because it will assume that they are normal". If you want more details on how those sort of algorithms work, then your best bet might be to read some papers that provide examples of algorithms of this form.

On the second quotation (assumptions in unsupervised techniques):

  • I think it's obvious why we need to assume that attack traffic looks different from normal traffic. If they looked the same, we'd have no way to detect attack traffic.

  • As far as why the unsupervised technique of Nieves needs legitimate traffic to be a lot more common than attack traffic: this is explained in Section 4.4 of the paper. It's because the paper assumes that small clusters represent attack traffic. Without this assumption, it's not clear how we could tell which of the traffic in our training set was normal and which was attack traffic, without labels. Remember, the paper assumes we have a training set with a lot of traffic, containing a mixture of both normal and attack traffic, and we don't have any labels to tell of us which of the data in the training set is normal and which is malicious.

    As the paper explains, "Based on our assumption that a real network contains many more normal connections than attacks, [we consider] the smaller clusters to contain attacks and the bigger clusters [...] to contain normal or good connections" (slight adjustments to grammar to make it clearer). In other words, that's just how Nieves' proposal works. Of course there's nothing that says this is the only possible way to do intrusion detection -- but it gives some explanation why Nieves chose to try out the particular scheme he did.


My earlier answer:

It's hard to know without context (you should've provided a link or citation to the specific paper you're referring to). Without that, we can only guess.

They might be referring to the difference between supervised learning and unsupervised learning. In supervised learning, we assume that we have a large training set containing many packets, and every packet is labeled as either 'malicious' or 'legit'.

In unsupervised learning, we assume we have a large data set containing many packets, but none of them are labeled. If you don't have labels for the training data, about all you can do is cluster the data into one or more clusters.

Finally, there's one more situation that is common for anomaly-based IDS's: we are given a large training set containing many packets, and it is assumed that everything in this training set is legit (non-malicious) and representative of normal non-malicious traffic. Then, one can try to build a model of what normal traffic looks like; during operation, if you see any packet that deviates from the model, then it might be an attack. This is the basic concept of anomaly detection. There are many ways to build a model of normal traffic, but one possibility is to use clustering (e.g., K-means) to cluster the normal traffic into one or more clusters; during operation, any packet in or near one of those clusters is assumed to be normal, non-malicious traffic. If this is what's going on, you can see that this works even if there is only one cluster.

If I had to make a guess, my guess would be on the latter explanation. But without a paper citation, it's hard to say for certain.

P.S. No matter what technique is used, you can hopefully see why it is important that anomalies (i.e., malicious traffic) differs from normal traffic. If malicious traffic looked the same as normal traffic, you'd have no hope of detecting it. And, indeed, the entire definition of an anomaly is "something that's different from normal", so for anomaly detection to be useful at detecting attacks, we have to assume that malicious traffic is anomalous (different from normal traffic).

share|improve this answer
    
Thanks. I added the context. Consider separating apples (normal) from bananas (anomaly), K-means can separate two clusters, one being normal and one being anomaly. So there is no need for pure apple set or less anomalous traffic. –  Yas Nov 19 '12 at 6:24
    
Thank you very much for your comment. It was so helpful. The problem I had with the Traditional one was that I was considering clustering approaches only and it seems traditional ones are statistical. About the assumptions, you are correct again. but why smaller clusters should be related to anomalies? if the number of bananas (anomalies) are less than apples (normals) in a dataset, this should not mean necessarily that their cluster in feature space are of smaller size. Maybe the bananas are more noisy (having various shapes) and apples are more of the same shape. Is this heuristic? –  Yas Nov 20 '12 at 6:33
    
@YasserMZadeh, when we talk about the size of a cluster, it's important to avoid conflating two different measures of size: the number of elements in the cluster, vs its radius. You seem to be talking about radius. I don't think the papers claim that clusters with smaller radius tend to be attacks (indeed, as you suggest, the opposite might well be true). Rather, they assume that attack traffic corresponds to a cluster with fewer elements. (continued...) –  D.W. Nov 20 '12 at 8:19
    
(cont.) In particular, they assume attacks are a lot rarer than legitimate traffic. That assumption was almost certainly true at the time the paper was written, and probably remains true today. This assumption (assuming it is valid) is helpful for the reasons explained in my answer: it gives us a heuristic to guess which cluster(s) are attack traffic and which one(s) are normal traffic. –  D.W. Nov 20 '12 at 8:19
    
Thank you very much for your help. Now I can understand better what is going on in this report. Being small was about cardinality of clusters, not the radius. Thanks. –  Yas Nov 20 '12 at 9:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.