PhD Thesis: A logic-programming approach to network security analysis

I have read this interesting PhD thesis called A logic-programming approach to network security analysis (2005) from Princeton University Computer Science Department. It is about modeling a network with respect to its security flaws. The model consists of logical statements written in Datalog that looks very similar to Prolog rules. The author captures the network topology, network and computer configurations and vulnerabilities in the model by analyzing a high-level security policy, the output from a scanner and firewall configurations.

From this model the author claims that he is able to do the following analysis (page 23):

• checking network configurations against a high-level policy specification that captures data confidentiality and integrity,
• hypothetical analysis that assumes various vulnerability situations, and
  
• the generation of attack trees.

Security Architecture Analysis

When I have been looking for work related to my research I stumbled over this survey from the Australian government: A Survey of Techniques for Security Architecture Analysis. It's quite an interesting survey. Only too bad that it is rather old from 2003. However, It contains a lot of interesting stuff and I have not found any other paper that covers as much work in this field in the same context. The abstract of the survey says (my layout and emphases):

This technical report is a survey of existing techniques which could potentially be used in the analysis of security architectures. The report has been structured to section the analysis process over three phases:

• the capture of a specific architecture in a suitable representation,
• discovering attacks on the captured architecture, and
• then assessing and comparing different security architectures.

Each technique presented in this report has been recognised as being potentially useful for one phase of the analysis. By presenting a set of potentially useful techniques, it is hoped that designers and decisionmakers involved in the development and maintenance of security architectures will be able to develop a more complete, justified and usable methodology other than those currently being used to perform analyses.

Does anybody know of any other work that covers all the three phases above?

Computer Security Strength & Risk

Previously on this blog I have related to an ongoing discussion on risk analysis with FAIR. Also related to this problem is this doctoral dissertation at Harvard university from 2004:

http://citeseer.ist.psu.edu/631841.html

In this dissertation the author suggests an economical model to measure security of a software product. By deriving an upper and lower the bound for the price for finding a new vulnerability he is able to set a value of a vulnerability and a higher value means a more secure product.

My questions are: Has anybody implemented ideas similar to this? What do you think of such an approach?

Other paper: Remodeling and Simulation of Intrusion Detection Evaluation Dataset

In proceedings of the 2006 International Conference on Security & Managment (SAM'06) I have found this paper: Remodeling and Simulation of Intrusion Detection Evaluation Dataset
In the paper, the authors describe how they simulate network traffic (both innocent and malicious traffic) for testing intrusion detection systems.

They want to improve on the MIT LL dataset that is widely thought to have major drawbacks. The drawbacks make it less useful for testing intrusion detection systems.

The paper's main contribution is to create personalized simulations of users' web browsing behavior while MIT's dataset had only rough distribution of the overall behavior. They model real users' behavior as probabilistic transition diagrams for sessions of browsing that are complemented with daily connection distributions, daily connection cumulative densities and session length distributions. Then browsing traffic is generated from the collection user models either with a one to one mapping from a user model to a simulated user or by generating more simulated users than there are user models

Email traffic is simulated using a public corpus of emails while the MIT dataset used a combination of filtered real emails and automatically generated emails. The emails are clustered into four classes but it is not clear what the classes are used for. It is neither clear if the class in the cluster relates to the classes created from the source and destination addresses mentioned earlier. As well, it is not quite clear how the emails are used in the simulation.

Then they claim to have a larger set of attacks than in the MIT datset, such as DDoS, probes, WWW attacks, RPC, etc.

Finally they show that their simulated web browser behavior more resembles their reference network than the MIT dataset simulation that lacks certain characteristics.

Comment: I would like to be able to use the generated traffic as basis for my research - too bad there is no link to a public data set.

Background reading: Polygraph - Automatically Generating Signatures for Polymorphic Worms

The next paper from RAID 2006 I will comment is about manipulating Polygraph. Thus it seemed natural that I looked at the original publication Polygraph: Automatic Signature Generation for Polymorphic Worms (2005).

Polygraph is a program that automatically generates signatures for Polymorphic worms; that are worms that change (obfuscate) their appearance from time to time between attacks. Existing worm blocking solutions (before 2005) assumes that worms have the same content from time to time. Thus it is easy to automatically generate signatures (simple single strings of bytes) that filter out worms. However, this assumption does not apply for polymorphic worms.

Since however, the polymorphic worms are targeting specific vulnerabilities some of the payload must be same between all worms, so Polygraph collects suspicious and innocuous payloads, classified using a simple flow classifier, and then extract content signatures from them. Instead of just extracting one single string of bytes, as in previous algorithms, Polygraph extracts sets of byte sequences.

The extracted byte sequences are used in three different ways for detecting worms :

• All byte sequences must be present in payload to indicate an worm
  
• All byte sequences must be present in correct order to indicate an worm
  
• All byte sequences are weighed together using a Naïve Bayes Classifier:
1. A byte sequence has probability being in a worm or not: P(seq | worm) and P(seq | ~worm)
2. A score is computed for a payload being a worm were {seq} means all sequences in a payload: score = P({seq} | worm) / P({seq} | ~worm)
3. Then the score is compared to a threshold and if true, the payload is believed to be an worm: score > tau

To handle the case that there are more than one type of polymorphic worms among the suspicious payloads, Polygraph uses hierarchical clustering of the byte sequences of the payloads. The sequences are merged into clusters by minimizing the false positives tested of the innocuous payloads.

Comment: First of all I think this an interesting paper, since I have a background in machine learning and Bayesian learning. However, the learning algorithms could probably be improved, for instance, by applying a more fully Bayesian approach than the used Naïve Bayes Classifier.

In addition I found an interesting comment at Mohit's security blog: IPS algorithms... that is as follows:

Most signatures in good products are vulnerability based so even if you change the attack it still gets stopped.

Thus, Polygraph might not be needed! Or what should we believe?

Follow up on: Can Machine Learning Be Secure?

In the previous post I mentioned I did not understand the relative distance metric they used for analyzing the security simple learning problem. However, in the paper they refer to a Master thesis that explains the metric in more detail.

The keys to understanding are the following:

1. To move the decision boundary as much as possible, each data point equals the previous mean added with the radius: Xt-1 + R
2. This is done alpha times at each iteration: (Xt-1 + R) * at
3. The next mean will be Xt = [Xt-1 * (n + a1+ ... +at-1) + (Xt-1 + R) * at ]/(n + a1+ ... +at-1 +at) where n is the number of previous data points
4. If we simplify the expression we will get: Xt = Xt-1 + R * at /(n + a1+ ... +at)
5. Assuming that the attacker has complete control of the learning process then n=0 thus: Xt = Xt-1 + R * at /(a1+ ... +at)
6. Using Mt = (a1+ ... +at) as the effort of the attacker and by noticing that the recursion leads to: Xt = X0 + R * [1 + a2/M2+ ... +at /Mt]
7. Thus: (Xt - X0)/R = [1 + a2/M2+ ... +at /Mt]
8. Noticing that ai/Mi = (Mi - Mi-1)/Mi = 1 - Mi-1/Mi
9. Thus we have the relative displacement (Xt - X0)/R = 1 + a2/M2+ ... +at /Mt = 1 + 1 - M1/M2 + ... +1 - Mt-1/Mt = t - [M1/M2 + ... + Mt-1/Mt]
10. The relative distance (or displacement) is then for t = T as in the paper:

• D({Mi}) = T − [M1/M2 + ... + MT-1/MT]
  

Background reading: Can Machine Learning Be Secure?

The next paper from the RAID 2006 proceedings cites a paper called Can Machine Learning Be Secure? as it's source of inspiration. This is a theoretical paper while the RAID paper complements it by being experimental. Thus it seemed reasonable to read it before reading the next RAID paper.

Can Machine Learning Be Secure? That seems to be a good question. This paper analyzes how secure a learning system can be.

A learning system adjusts it's model given new data, these are some of the questions asked:

• Can it be trained by an attacker to allow malicious calls?
• Can it be degenerated such that it becomes useless and must be shut down?
• Are there any defenses against these attacks?

The paper tries to create a taxonomy of attacks on a learning system but I don't think it is that successful. The taxonomy has three axes:

1. Influence: the part of the learning system that is manipulated, causative (alter the training data) or exploratory (trying to discover information about the system)
2. Specificity: a continuous spectrum, from achieving a specific goal, for instance to manipulate the learning system to accept a specfic malicious call, to acheiving a broader goal, for instance to manipulate the learner to reveal the existence of any possible malicious call.
3. Security violation: what security goal is violated, integrity (false negative) or availability (many classification errors making the system useless).

Comment: I don't think the paper gives enough reasons for this taxonomy. It is not that clear to me that these axes and scales are completely orthagonal or at least describes the space of attacks in a good way. Although I cannot, at the movement, come up with something better, I think it should be possible to think this through again and come up with something better. Maybe it is the vocabulary that is problematic; maybe by using different words, the taxonomy will be more readable.

Then the paper lists defenses against the different attacks, such as adding prior distributions (robustness) that makes the system less sensitive to altered data, detecting attacks with intrusion detection mechanism that analyzes the training data, confusing the attacker using disinformation that hinders the attacker from learning decision boundaries and, what seems to be a special case of the former, randomization of the decision boundaries.

Comment: Bayesian learning methods seems to a be natural choice since prior distributions are in the essence of the Bayesian concept.

Last in the paper, they analyze a simple learning example for outlier detection on the bounds of the effort an attacker has to use to manipulate the learning system into wrongly classify a malicious call.

Comment: I cannot write much about this analysis since I could not understand the definition of the relative distance they use. I don't understand why they use it and what it means. Thus I do not understand the result. Is there anybody out there that can help me with this?

See follow up post on this issue.

powered by performancing firefox

Paper 3: Automated Discovery Of Mimicry Attacks

This papers describes an approach to checking that the models of model-based anomaly detection approachs really detect malicious system calls. Especially, the approach is aimed at discovering Mimicry Attacks, that is, calls that, for instance uses a buffer overflow, to invoke malicious system call sequences disguised as none-dangerous call sequences. Previously, the discovery of mimicry attacks were done manually.

A model-based anomaly detection approach uses a model describing the "normal" and allowed behavior of a monitored system. However, model-based anonaly detection can sometimes be cheated by the use of mimicry attacks that imitates "normal" behavior and thus these attacks are not detected.

In this paper they create a model of the Operating System (OS) monitored by a model-based anomaly detection system. Then they use the OS model to create a Push Down Automaton/Push Down System of the anomaly detection system. Thereafter a model checker, given a malicious goal for an attack (for instance, to create a new user account), can automatically either find a successful attack call sequence not detected by the detection system or prove that there are no attack call sequences for that goal not detected by the modeled automaton. This means that the reliability of this approach depends heavily on that the OS model is correct.

I think this was a quite interesting paper with nice results, though I am not that familiar with model checking and formal methods.

powered by performancing firefox

Paper 2: Behavioral Distance Measurement Using Hidden Markov Models

In this paper, the authors describes how they to use a hidden markov model (HHM) to model the execution similarities between two process performing the same work. For instance, two Apache web servers running on two different platforms, Linux and Windows. The assumption is that the two process will not have the same vulnerabilities, and thus by measuring the behavioral distance between the two process, we can detect anomalies.

Much of the paper describes the HHM and whether the overhead is small enough to make the algorithm usefull.

Something missing is the significance of the results. For instance, when comparing another distance metric algorithm called an ED-based approach, the result is that the HHM-based approach is 6.32% faster, but nothing about the variance or significance. I would recommend any researcher to choose a good statistical test so results cannot be so easily questioned. A good online handbook for such tests can be found at the NIST/SEMATECH e-Handbook of Statistical Methods.

Paper 1: A Framework For The Application Of Association Rule Mining In Large Intrusion Detection Infrastructures

This paper is about using data mining in form of association rules to extract rules describing correlations between alarms from a large set of intrusion detection systems. The rules can then be used as basis for creating new rules to detect correlated intrusions.

Since the system mines for correlations between a huge amount of alarms it needs some form of data filtering. As filtering approach, the system uses graph algorithms with a graph where IP addresses are vertices and detected alarms are edges, drawn from source to destination IP addresses. Only connected components of the graph are used for mining.

Amongst the most interesting things in this article are the following:

• The number of rules generated each day can be used to detect weired (anomalous) network activites.
• This can also be done for each subnet of the network and thus find high risk networks.

A problem is though that the results they get are not able to repeat. I can imagine that this is often a problem in security research with sensitive data. Many of their results are like anecdotes that makes it hard to compare the results to other's work.