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

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:

+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
|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.

• "However, Mahalanobis distance could be only applied to normally distributed features." Actually, elliptical shaped. Can you post the first few lines of your data set (or some fake numbers but having the same features as the real thing)? Mar 11 '15 at 19:59
• I assume that elliptical shaped means product of two normally-distributed features, with different mean and standard deviations, but still normally distributed. Mar 12 '15 at 11:27
• No, elliptically shaped means shaped like the shadow of a football in 2D, a football in 3D and in general a D-dimension football in D dimensional space. Mar 12 '15 at 11:46
• Out of curiosity. Could you share some of the data / what dataset you're working with? Is it a public / academic research set? Mar 14 '15 at 9:23
• Unfortunately, this is not a public dataset and I'm not able to share it. However, there should be a famous KDDCup 1999 dataset, or Scan34 dataset from Honeynet (old.honeynet.org/scans/scan34). Both datasets have logs (not network traffic) for analysis (Apache, Snort, syslog, etc.). In the dataset that I have, most of logs are Active Directory logs. I'm not sure if there are any public AD / Windows Events available for analysis (earlier I used a self-generated dataset because of the absense of the real one). Also, the dataset I have is very big (150 Mio records). Mar 14 '15 at 18:42

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.

• Thank you for the links, they are very useful. (1) The first paper you mentioned is very interesting. It seems that it is possible to transform the distribution to normal to apply Mahalanobis distance later. I will try to get into it. (2) Do you know if there are some other approaches, e.g. some similarity measures like cousine distance, that do not operate on distances? (3) The presentation slides you mentioned are, however, focused on the network traffic packets, not on the logs. Mar 12 '15 at 11:17
• In regard to other approaches, I thought about following 2: (1) one-class SVM could find out correlation between features, if high-polinomial model is used; (2) threat log lines as sentences, and use cousine similarity to group/cluster them. The first I already tried to implement, but it runs already more than a week on 1 CPU (I first train a model on the first half of data, and apply to the second. Then vice versa). The second approach implies a high-dimensional space (e.g., every different value of username will be a feature). Mar 12 '15 at 12:00
• @AndreySapegin: If your current attempts' results will not be good enough, you could try some other approaches, mentioned in the papers I've referenced. That was the idea. One more thing - try GraphLab open source ML software (some of it is branded now as Dato): dato.com/products/create/open_source.html. GraphLab software is high-performance and very scalable across not only processor cores, but processors and even machines. Mar 12 '15 at 21:40
• @AndreySapegin: A paper from my university colleague just popped up in my ResearchGate stream. I think it might be very helpful to you (uses ANN approach to detect intrusion - via cool Encog ML library, of which he is the creator and main contributor - Encog is also scalable via multicore & GPU). Here's the paper: researchgate.net/profile/Jeff_Heaton/publication/…. Here's info on Encog: heatonresearch.com/encog. Mar 12 '15 at 21:54
• To whoever awarded the bounty to my answer: I appreciate your generosity as well as recognizing my efforts toward quality answers. Mar 18 '15 at 21:14

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.

• Thank you for your answer, it is a good point. As I understood you offer to focus on more simple analysis than anomaly detection. From the technical (industry) perspective, you are right. However, I'm doing a research and would like to focus on machine learning analysis. The query-based analysis like you offered we have already performed (maybe not exactly identical to queries you offered, but similar)... Another argument for doing it is that many enterprises currently TRY to do anomaly detection in addition to 'normal' (more simple, but still comples) queries and rules... Mar 14 '15 at 18:51

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?

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.

• The problem is that it is extremely complicated to get a data sample without attacks. Often nobody knows if there are some attacks in the dataset. Mar 12 '15 at 9:32

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.

• It seems you might have accidentally created a second account - see here for how to merge them. This will let you edit your own posts. Jan 30 '16 at 19:03

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