1
$\begingroup$

BACKGROUND:

Consider the problem in cybersecruity that consists of classifying domain names as either malicious or legitimate based on various features such as the URL string, the name of the registrant, the HTML content, the IP address, etc.

Without the use of machine learning, this would typically be done by a simple lookup to a black list of domains that have been manually reported as harboring malware. Any new domain which hasn't been seen before is then, by default, considered as legitimate. (This would be the case for the overwhelming majority of domains unless, say, one of them is reported as malicious, at which point it will be moved to the black list.)

In addition to the fact that this approach is expensive in terms of human involvement and has no predictive power, it also leads to

  1. false negatives from new domains that are malicious and haven't been blacklisted yet
  2. false negatives from old domains that are malicious but managed to evade detection through human error
  3. false positives from old domains that are legitimate but were wrongly blacklisted through human error

QUESTION:

Can machine learning be of any use here? I.e., can it outperform the accuracy of manual black lists and at the same use them as training targets? At first glance, one should use the the black lists to train a classifier in a supervised fashion. This could presumably automate the classification such that (1) above is mitigated. It is however much less obvious how that it can mitigate (2) and (3).

The alternative is to use a full-fledged unsupervised technique such as k-means. But then again, it seems that not exploiting the human labels provided by the black lists is a waste of precious information. K-means is furthermore prone to capture clusters that have little to do with maliciousness.

So which method would be the most robust? Should this be a supervised or unsupervised problem? As for semi-supervised, what would that mean exactly in this case?

$\endgroup$
  • $\begingroup$ There's other categories of false negatives/positives besides the 3 listed above. It's sites that were previously legit but now malicious, or previously malicious but now legit. (with variations on if and when the statuses were correctly found). I know this from painful experience because I had a web site that was hacked. I fixed it, but the effects of links to/from malicious sites persisted for a long time, not to mention getting blacklisted for e-mail from my domain. This has a big impact on what you do, because it means an adaptive system that can change its opinion, not keep it forever $\endgroup$ – gms Oct 31 '17 at 15:30
  • $\begingroup$ @gms I agree. I just left out this added complication from my question, but it's definitely another issue I'm grappling with, namely the drift of the maliciousness hyperplane over time. Any ideas? $\endgroup$ – Tfovid Nov 1 '17 at 7:59
  • $\begingroup$ Selectively forget old information. People tried weighting based on age, but that has a major flaw: it forgets useful information when newer information doesn't replace it. A better approach to forgetting old data is to de-emphasize or delete old data only when nearby newer data directly replaces it (and averaging in some way over time so that a single outlier won't completely destroy old but good data). Examples of this sort of are in RTEFC, RTMAC, and "Recursive Density Estimation with Forgetting". See gregstanleyandassociates.com/whitepapers/BDAC/Clustering/… $\endgroup$ – gms Nov 1 '17 at 14:12
1
$\begingroup$

It will be semi-supervised learning since you know the answer (harmful or not) for some of the sites that you know the features of (url,the name of the registrant, the HTML content, the IP address, etc.) but not for others. It would be better if you also kept track of sites that were explicitly examined but not found harmful. That's a labeled example with the answer "not harmful" and not the same as an unlabeled example that is whitelisted per default.

You want to use the information contained in the supervised examples as well as in the unsupervised examples and extrapolate it to new examples. Especially if you only know the answer to a small fraction of examples, this can be the best approach.

But there is no guarantee, it might also be useless or harmful to add unsupervised examples to the data-set. You can always make it supervised learning by ignoring all the urls that you don't know the answer to and by extrapolating only from those where you know the answer towoards new urls that you want to judge. That should be your baseline. Only include unsupervised examples if it increases your classification performance.

Also look here to understand the differences between semi-supervised and supervised learning.

Can machine learning be of any use here?

In principle yes. You would need to try a couple of features that describe websites and feed them to different algorithms and you will know how useful it is.

To compare performance metrics in semi-supervised learning, you need to set aside a test-set where you know the answers and have a training-set where you know some but not all of the answers. Train supervised algorithm(s) only on the supervised part of the training data and train semi-supervised algorithms on all data (supervised training-, unsupervised training- and test-data the last one obviously stripped of the answers). Compare the test set predictions of all algorithms.

can it outperform the accuracy of manual black lists and at the same use them as training targets?

On an example where you already know the answer (by human judgement or though hindsight knowledge after it turned out the site was harmful) it will most of the time (exceptions for your scenarios 2. and 3. are described below) not be better than those methods. That's because a machine learning algorithm would take those answers and extrapolate patterns it finds in them to unseen examples. (Semi-supervised algorithms are often transductive and can only extrapolate to a pre-defined set of new examples while supervised algorithms are inductive and construct models that can predict any example you feed them at any moment.)

But this can still be quite useful since you would avoid the false negative default scenarios 1. for new examples that you describe in your list.

This could presumably automate the classification such that (1) above is mitigated. It is however much less obvious how that it can mitigate (2) and (3).

Some semi-supervised algorithms (learning with local and global consistency) learn transductively from supervised examples towards unsupervised new examples. They allow to change some of the initial labels if they are considered to be probably wrong in light of all the other labels. This would address your scenarios 2. and 3. Basically, local consistency means that similar examples need to have similar labels most of the time and global consistency means that there shouldn't be too many initially labelled examples that are attributed other labels than what they initially had (but there can be some).

Measuring similarity of examples (which all the graph based semi supervised algorithms rely on) will not be easy with your mixed data where a website is described by such dissimilar variables as url strings, IPs, names etc. You will at the very least need Gower's distance metric.

The alternative is to use a full-fledged unsupervised technique such as k-means. But then again, it seems that not exploiting the human labels provided by the black lists is a waste of precious information. K-means is furthermore prone to capture clusters that have little to do with maliciousness.

Correct, I wouldn't do that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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