How to prepare/construct features for anomaly detection (network security data)

Question

My goal is to analyse network logs (e.g., Apache, syslog, Active Directory security audit and so on) using clustering / anomaly detection for intrusion detection purposes.

From the logs I have a lot of text fields like IP address, username, hostname, destination port, source port, and so on (in total 15-20 fields). I do not know if there are some attacks in the logs, and want to highlight the most suspicious events (outliers).

Usually, anomaly detection marks the points with low probability/frequency as anomalies. However, half of the log records contain unique combination of fields. So, half of records in the dataset will have the lowest possible frequency.

If I use anomaly detection based on clustering (e.g., find clusters and then select points that are far from all cluster centers), I need to find distance between different points. Since I have 15-20 fields, it will be a multi-dimentional space, where dimesions are username, port, IP address and so on. However, Mahalanobis distance could be only applied to normally distributed features. This means that there is no way to find distance between data points and construct clusters...

For example, let's imagine that I have users Alice, Bob, Carol, Dave, Eve and Frank in the dataset of 20 records. They could have the following number of occurences in the database: 2,5,2,5,1,5. If I simply map usernames to numbers, e.g.

Alice --> 1
Bob --> 2
Carol --> 3
Dave --> 4
Eve --> 5
Frank --> 6

Then, my probability distribution for usernames will look as follows:

p(1) = 0.1, p(2) = 0.25, p(3) = 0.1, p(4) = 0.25, p(5) = 0.05, p(6) = 0.25

Of course, this is not a normal distribution, and this also does not make much sense, since I could map usernames in any different way...

Thus, simple mapping of fields like username, action, port number, IP address and so on to numbers does not bring anything.

Therefore, I would like to ask, how the text fields are processed / features constructed usually to make unsupervised anomaly/outlier detection possible?

EDIT: data structure.

I have about 100 columns in the database table, containing information from Active Directory Events. From this 100 columns I select the most important (from my point of view): SubjectUser, TargetUser, SourceIPaddress, SourceHostName, SourcePort, Computer, DestinationIPaddress, DestinationHostName, DestinationPort, Action, Status, FilePath, EventID, WeekDay, DayTime.

Events are Active Directory events, where EventID defines what was logged (e.g., creation of Kerberos ticket, user logon, user logoff, etc.).

Data sample looks like following:

+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|ID         |SubjectUser|TargetUser|SourceIPaddress|SourceHostName              |SourcePort|Computer                    |DestinationIPaddress|DestinationHostName         |DestinationPort|Action                |Status  |FilePath|EventID|WeekDay|DayTime|
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|171390673  |?          |?         |?              |?                           |?         |domaincontroller1.domain.com|1.1.1.1             |domaincontroller1.domain.com|?              |/Authentication/Verify|/Success|?       |4624   |1      |61293  |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|173348232  |?          |?         |?              |?                           |?         |domaincontroller2.domain.com|2.2.2.2             |domaincontroller2.domain.com|?              |/Authentication/Verify|/Success|?       |4624   |1      |61293  |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|180176916  |?          |?         |?              |?                           |?         |domaincontroller2.domain.com|2.2.2.2             |domaincontroller2.domain.com|?              |/Authentication/Verify|/Success|?       |4624   |1      |61293  |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|144144725  |?          |John.Doe  |3.3.3.3        |domaincontroller3.domain.com|2407      |domaincontroller3.domain.com|3.3.3.4             |domaincontroller3.domain.com|?              |/Authentication/Verify|/Success|?       |4624   |3      |12345  |
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

All together, I have about 150 million events. Different events have different fields filled in, and not all events are related to user logon/logoff.

Answer 1

I'm definitely not an expert on anomaly detection. However, it's an interesting area and here's my two cents. First, considering your note that "Mahalanobis distance could be only applied to normally distributed features". I ran across some research that argues that it is still possible to use that metric in cases of non-normal data. Take a look for yourself at this paper and this technical report.

I also hope that you'll find useful the following resources on unsupervised anomaly detection (AD) in the IT network security context, using various approaches and methods: this paper, presenting a geometric framework for unsupervised AD; this paper, which uses density-based and grid-based clustering approach; this presentation slides, which mention using of self-organizing maps for AD.

Finally, I suggest you to take a look at following answers of mine, which I believe are relevant to the topic and, thus, might be helpful: answer on clustering approaches, answer on non-distance-based clustering and answer on software options for AD.

Answer 2

First of all, I think there are some things that you may have to resign yourself to.

One hard constraint that I see on this problem is that you should probably be prepared to have a quite high false positive rate. As far as I know, the base rate of records being part of a network anomaly is quite low (citation needed). Let's call it 1000:1 odds, for the sake of argument. Then even if you observe a pattern that is 100 times more likely to happen if the record is an intrusion then if it's legit, Bayes' Rule says that the posterior odds are 10:1 that the traffic is still legit.

The other problem is that some intrusions are hard to detect even in principle. For instance, if somebody socially engineered me into giving them my computer, and then they logged into this service and downloaded one top-secret file which I had been working on, this would be quite hard to find. Basically, a sufficiently determined attacker can make their intrusive behavior almost arbitrarily close to the normal behavior of the system.

Furthermore, your adversaries are intelligent, not statistical processes, so if you start detecting some pattern and shutting it out, they may simply respond by not following that pattern anymore. This is why, for instance, you'll see lots of spam messages with spaces in between all the letters (offering you "V I A G R A" or whatever). Spam filters figured out that the string "viagra" was spammy, so the attackers just started doing something else.

Because of this, I think it's worth thinking pretty hard about what types of intrustions you think it's worth the effort to be able to detect. There are certainly low-hanging fruit here, so don't let the perfect be the enemy of the good and try to come up with an algorithm that can detect all intrusions.

---

That aside, let's talk about the low-hanging fruit. Here, I think it might be productive for you to shift your unit of analysis from individual records, to a group of records.

For instance, you said that half of all records have unique combinations of fields. But presumably, for instance, most source IPs appear in more than one record--it's the other fields in the request that are changing and making the combination unique. If you group the requests by IP, you can then ask questions like:

• Do some IPs seem to authenticate as unusually many users (or unusually few)?
• Do some IPs have an unusually large number of authentication failures?
• Do some IPs have an unusual pattern of access timings (for instance, lots of activity around 3am in their timezone, or requests every 1 second throughout the day)?

You can do similar things for other groupings, like username:

• Is this user authenticating from a different computer when they previously used the same computer for all requests?
• Is this user suddenly touching a part of the filesystem they've never touched before?

I don't know of any off-the-shelf classifiers that seem particularly suited to this, because the potential behavior of your users is so varied, and you're probably mostly interested in changes in behavior over time. That means you probably want to build some kind of model of what each user/IP/whatever is likely to do in the future, and flag any deviations from this model. But that's quite an intensive process if your users have different behavior patterns!

Because of this difficulty, I think for now it might be more productive to do the kind of exploratory-mode analysis I outlined above. That's likely to inform you about what types of patterns are the most interesting ones, and then you can start using fancy statistical algorithms to detect those patterns.

Answer 3

I think that in first place you need to have a dataset which records data for a period of no attacks. This dataset should capture the variations that are inherent to a system behaving normally. I would like to stress the point that this is not about having an annotated dataset.

Next, I would try to combine all (or subset) of metrics into one. This new metric should reflect the amount of "surprise". For example, low value means system runs normally, high value peak/plateau means that there is some rapid change. Here I am thinking about CUSUM or Shewhart chart style charts.

Can you provide some examples of the available data? Is it mainly strings, numbers, 1/0 indicators?

Answer 4

A possibility is to learn a bayesian network between the features given some background data with no attacks. Learning a bayesian network is useful because it brings out conditional independence between features. Hence, you are not dealing with each and every possible combination of features. For example, if feature A affects B and C and features B and C together affect D, then you only learn a model for how A affects B, how affects C, and how B and C jointly affect D. This model will require far fewer parameters than the entire probability distribution and is the primary reason why bayesian networks are used instead of just storing the entire joint probability distribution. To test for anomaly given a Bayesian network, calculate the probability of incoming datapoint using the learnt Bayesian network model. If the probability is very low, you can flag that as an anomaly.

Answer 5

I thought that the response from Ben Kuhn was pragmatic and insightful.

Now my own background includes in text classification, expert systems, clustering and security. Given this background, I would like to think that I might have something to add to the conversation. But the previous statements by Ben Kuhn highlight that straightforward approaches could produce many false positives. IT staff, when faced with many false positives, typically "tune out" because they simply do not have the time to chase false positives all the time.

So what to do?

Certainly logs with attacks in them could be helpful but then we have a catch-22 unless companies somehow share attack data. While some Silicon Valley start-ups might be pursuing such threat sharing, what else might we do?

One possible approach is to create a simulation of the network and then find a way to generate attacks against the simulation. That is, suppose we create a simulation where the black hats (also simulated) are not known in advance to the white hats. Given these attacks, we can then attempt to create algorithms that should discover these attacks. If the black hats operate independently of the white hats, then we have a real battle that will play out. If the attackers break into the system, or are undetected, then the white hats have, to some degree, failed.

One could even have an incentive structure when the security analysts on the black hat team are rewarded for their successes (breeches or undiscovered attacks). Similarly, the group comprising the white hats are rewarded for stopping breeches and/or detecting attacks.

There is nothing perfect about this arrangement. Obviously real black hats might exceed the talents of the "friendly" black hat team. Nonetheless, as person who has a fair amount of data analysis, it seems to me that it is very hard to quantify the success of white hats without a better understanding of the black hats. Bottom line is this. If we can't know what real black hats are doing, the next best thing is friendly black hats.

I also have a rather unusual idea. Suppose in addition to the friendly black hats and the white hats, there is a gray hat team. What does it mean to be a grey hat? The idea is simple. Grey hats are permitted to look at what the friendly black hats are doing and the white hats. But why?

Suppose that the friendly black hats launch attacks using approaches A, B and C, and the white hats never discover any of these three approaches. Well, the grey hats are empowered to look at what both the friendly black hats are doing as well as the white hats are doing, and they try to consider what principles might be used to discover these undetected attacks. If the grey hat finds such principles, the grey hat team can then share these principles with the white hat team without describing the exact attacks in detail.

The hope is that these "hints" provided by the grey hat team give the white hat team a push in the right direction without revealing too much.

In retrospect, I apologize if my response is really not about specific techniques. Obviously my response is not about specific techniques. But in my experience, a lot of problems in machine learning - including those in security - often fail because the data is inadequate. This approach, using white hats, grey hats and black hats, might help produce the data that would allow a security company (or IT staff) to not only quantify the effectiveness of their defenses, but provide an organizational structure that pushes the white hat team to progressively improved their defenses and their monitoring.

I really don't have any idea if the approach I am suggesting is original. I have never heard of grey hats, but I actually think that the role of grey hats could be critical to pushing the white team forward, without revealing too much.

---

Note: my use of the term "grey hat" here is not standard. See http://www.howtogeek.com/157460/hacker-hat-colors-explained-black-hats-white-hats-and-gray-hats/. So some other term, perhaps "striped hat" should be used instead.

But still the idea remains the same: a striped hat can help mediate between the work of friendly black hats and defenders (white hats), so that certain ideas and hints can be judiciously shared with the white hats.

Answer 6

Since I have posted the original question, I have performed a lot of research on this topic and can now provide my results as an answer.

First of all, in our lab, we develop a SIEM system that utilizes anomaly detection algorithms. The description of the system and algorithms is available in my paper Towards a system for complex analysis of security events in large-scale networks

Besides that I wrote a short summary on how to deal with such data in my answer to a similar question on Cross Validated