Machine Learning for Computer Security.

Securing IMS against Novel Threats.

2009-07-09T18:35:00.005+02:00

Recently, we have published an interesting article at Bell Labs Technical Journal on detecting unknown threats in IMS and VoIP networks. This article has been the outcome of a fruitful cooperation of Fraunhofer FIRST and Alcatel-Lucent in Germany. The article's abstract is here:

Fixed mobile convergence (FMC) based on the 3GPP IP Multimedia
Subsystem (IMS) is considered one of the most important communication technologies of this decade. Yet this all-IP-based network technology brings about the growing danger of security vulnerabilities in communication and data services. Protecting IMS infrastructure servers against malicious exploits poses a major challenge due to the huge number of systems that may be affected. We approach this problem by proposing an architecture for an autonomous and self-sufficient monitoring and protection system for devices and infrastructure inspired by network intrusion detection techniques. The crucial feature of our system is a signature-less detection of abnormal events and zero-day attacks. These attacks may be hidden in a single message or spread across a sequence of messages. Anomalies identified at any of the network domain's ingresses can be further analyzed for discriminative patterns that can be immediately distributed to all edge nodes in the network domain.

Securing IMS against Novel Threats. Stefan Wahl, Konrad Rieck, Pavel Laskov, Peter Domschitz and Klaus-Robert Müller. Bell Labs Technical Journal (BLTJ), 14(1), 243-257, John Wiley & Sons, May 2009.

Some Tuning for Feature Extraction.

2009-05-29T18:05:00.009+02:00

One key to efficient application of learning methods in practice is fast extraction of features from raw data. As an example, I am currently working on methods for automatic analysis of malware, where the behavior of a malware binary is represented in a textual report and mapped to a vector space using frequencies of contained substrings (see here). However, thousands of binaries need to be processed and often the generated report files are huge. Consequently, the task of designing analysis methods gets tedious, as one has to wait several minutes just to load data and extract appropriate feature strings.

In quest for a remedy, I have experimented with OpenMP (Open Multi-Processing) and libarchive, where the first is a simple API for multi-processing programming in C and the latter a library for reading and writing of file archives, such as zip, tar and on. On the one hand OpenMP enables loading of data and extraction of features in parallel, whereas on the other hand libarchive allows for storing the data efficiently in compressed archives in favor of directories.

The figure shows some preliminary run-time measurements for extraction of feature vectors from malware reports. The application of multi-processing clearly accelerates the feature extraction, independent of the applied data format. For example, when reading from a directory the performance is doubled if two threads are used and enables processing up to 100 files per second (note this experiments was run on a dual-core machine). Surprisingly, the extraction performance is also high when using compressed archives. There is almost no difference between feature extraction from a zip/gz archive and a plain directory. Moreover, the zip/gz archive consumes only 5% of the original space and considerably reduces the amount of required storage. That's impressive. If you are dealing with loading and processing thousands of files, these tuning hacks might be an interesting option.

It's finally done.

2009-05-04T19:57:00.003+02:00

After a long period of hard and boring work, I finally submitted my Ph.D. thesis to the computer science faculty at Berlin Institute of Technology (TU Berlin). The thesis is entitled "Machine Learning for Application-Layer Intrusion Detection" and refereed by Klaus-Robert Müller, John McHugh and Pavel Laskov.

In my thesis, I tackle the problem of detecting unknown and novel attacks in the application layer of network communication and present a machine learning framework for intrusion detection. In particular, I propose a generic technique for embedding of network payloads in vector spaces such that features extracted from the payloads are accessible to statistical and geometric analysis. Efficient learning in these high-dimensional vector spaces is realized using the concept of kernel functions defined over network payload data. Based on these functions, I derive methods for anomaly detection suitable for identification of unknown attacks, where normality of network data is modeled using geometric concepts such as hyperspheres and neighborhoods.

The framework is empirically evaluated using 10 days of HTTP and FTP network traffic and over 100 real attacks unknown to the applied learning methods. A prototype of the framework outperforms related methods from Kruegel et al. (2002), Wang et al. (2006) and Ingham et al. (2007), where it identifies 80–97% unknown attacks with less than 0.002% false positives. Moreover, reasonable throughput rates between 20–60 Mbit/s are attained, though no special hardware acceleration is yet utilized.

As the thesis is under review, I will not provide an online version now. However, I am going to present some interesting results on visualization of detected attack payloads in later posts. Stay tuned.

Fun and Pain with ZFS.

2009-04-07T20:06:00.004+02:00

Recently, I found the time to experiment with ZFS – Sun's next-generation file system – using an external USB drive. In particular, I have been playing with ZFS to test whether it alleviates typical tasks of machine learning research, such as loading directories containing ten thousand of files or repeating experimental runs with large data chunks. As I am not running a Solaris system, I had to install the userland utilities and kernel modules for OSX (Leopard) available at Macforge. Note that Leopard natively supports read-only access to ZFS pools but lacks write functionality.

Apart from great read access time, the first interesting issue I noticed is ZFS's ability to create hierarchical file systems on-the-fly. Instead of dumping all contents into a single volume, the hierarchical layout enables fine-grained control of different experimental data sets and allows for assigning quota and options individually per data. For example, the ability to easily split data comes handy, if one enables the transparent compression in ZFS. This snippet of commands creates two file systems named tank/dataset1 and tank/dataset2 where uses automatic compression.

% zfs create tank/dataset1
% zfs create tank/dataset2
% zfs set compress=on  tank/dataset1
% zfs set compress=off tank/dataset2

Compression might not be desired when running certain experiments. Thus, it can be disabled and enabled per file system, such that archived data is stored effectively while the current workbench is accessible with full processing power. A nice feature for working with experimental data. The compression ratio of each file system can be queried using the following command.

% zfs get compressratio tank
NAME            PROPERTY         VALUE         SOURCE
tank/dataset1   compressratio    3.14x         -
tank/dataset2   compressratio    1.00x         -

Another interesting issue is ZFS's ability to store snapshots of file systems. Initially, a snapshot does not consume any memory as only the differences to the original version are stored. If one is working with multiple copies of the same data, say one version described in a publication and a refined variant, snapshots are a great tool, as they allow one to quickly jump back and forth between different versions of data. One can access the content of each snapshot using the directory .zfs in the root of the considered file system. Here's an example how a snapshot is created for a given data set.

% zfs snapshot tank/dataset1@paper

As it can see from a call to zfs list there is no memory associated with the snapshot directly after creation and thus no storage is wasted.

% zfs list
tank/dataset1          2.38G   222G  2.38G  /Volumes/tank/dataset1
tank/dataset1@paper        0      -  2.38G  -

This feature is really nifty if one needs to "freeze" the state of experimental data if a paper is accepted for publication while still continuing to work with the data set.

Unfortunately, all my enthusiasm and great plans to work with ZFS have been eliminated by the instability of the current Leopard driver. The driver does not really handle USB devices. If the device is accidentally removed or the computer falls asleep, the ZFS module simply crashes the kernel. I even managed to corrupt the ZFS partition such that any call to zpool status issues a kernel panic. Game over.

Call for Papers: DIMVA 2009.

2009-01-25T17:02:00.002+01:00

I am a member of the program committee of this year's conference on Detection of Intrusions and Malware & Vulnerability Assessment (DIMVA) in Milan, Italy. The conference invites paper submissions from the domain of computer security with focus on intrusion detection and malware research.

Deadline for paper submission: February 6, 2009
Notification of acceptance or rejection: March 30, 2009
Final paper camera ready copy: April 10, 2009
Conference dates: June/July, 2009

Contributions can be submitted as full papers (limited to 20 pages) or short papers (limited to 10 pages). A detailed "call for papers" is available here. I am looking forward to interesting contributions and an awesome DIMVA conference—as in the last five years.

Unpleasant Facts about Data Clustering.

2008-12-18T13:55:00.025+01:00

Data clustering is a popular technique of data mining and machine learning. The objective is to automatically partition a set of given objects into "meaningful" groups. Clustering is intuitive and fits a variety of problem settings, for example intrusion detection and malware categorization in computer security. However, application of clustering methods is laborious and error-prone in practice. Here are my unpleasant facts of clustering:

Generic clustering is NP-hard. Formally, clustering aims at partitioning data such that a predefined quality criterion is maximized. Unfortunately, there is no generic way for determining an optimal solution in this setting except for testing all possible combinations. All practical clustering methods, such as k-means and linkage clustering, limit the search space by discarding partitionings and thus provide only an approximation to the best clustering (a local optimum). If you cluster data, you will likely obtain an approximate solution.
Hierarchy is no clustering. Linkage clustering is a form of hierarchical clustering, where the data is first mapped to a hierarchical representation and then partitioned into clusters. In practice, people often consider the hierarchical representation of data as the final clustering result. However, a hierarchy encodes an exponential number of possible partitionings and the more involved step is to flatten the hierarchy into a clustering. As a negative example consider the Wikipedia entry on hierarchical clustering which almost solely focuses on constructing hierarchies—omitting details on the subsequent clustering procedure.
Statistical consistency unclear. An important term from statistical learning theory is consistency. Shortly put a learning algorithm is consistent if it converges to the true solution the more training data is provided. Surprisingly, little is known about the consistency of clustering. For instance, most clustering methods aim at partitioning provided data but not the underlying data distributions. That is, if you provide more data to a clustering, there is no guarantee that the solution improves (see the work of Luxburg [1, 2]).
Model selection vs. Clustering. Clustering is often controlled using a model parameter that determines the granularity of the partitioning. This parameter can be the number of clusters as for k-means but may also take the form of a numeric quantity as in linkage clustering. Clearly, this parameter needs to be adapted prior to application. However, model selection contradicts with the purpose of clustering. On the one hand, to validate the parameter on given data a reference partitioning needs to be available, thus no clustering is required in this case. On the other hand on unlabeled data the parameter can never be validated directly. In practice, one resorts to model selection on reference data and application of the best model to unknown data. Consequently, this setting requires a representative reference partitioning obtained without clustering.

Besides these facts, I like clustering methods and have been successfully working with several of them. Nevertheless, special care needs to be taken when running experiments to achieve sound results—the application of clustering is more involved as it seems at a first glance.

Incorporation of Application Layer Protocol Syntax into Anomaly Detection.

2008-12-17T17:33:00.010+01:00

The majority of current intrusion detection, anti-virus and anti-malware products builds on the concept of misuse detection, that is malicious activity is identified using rules and signatures of known misuse patterns. Consequently, much effort has been devoted to defining expressive and discriminative features for construction of misuse rules. In the domain of network security such features are often derived from the syntax of application layer protocols, for example to answer the questions "who did what to which data when?"

In contrast to misuse detection, a second strain of intrusion detection research investigates methods for anomaly detection, that is malicious activity is identified in terms of unusual and abnormal events. Surprisingly, the use of features from protocol syntax in this setting has been considered in only few research, for example Kruegel et al. and Ingham et al. Access to syntactical features is clearly beneficial for anomaly detection, and hence some of my colleagues (Patrick and Christian) have been working on extending previous approaches to incorporate protocol syntax into a generic anomaly detection framework.

Recent results of this work are presented at the International Conference on Information Systems Security. In particular, we introduce new features for network intrusion detection, which combine sequential features (such as byte frequencies and n-grams) with syntactical tokens. Here is the abstract of our contribution:

The syntax of application layer protocols carries valuable information for network intrusion detection. Hence, the majority of modern IDS perform some form of protocol analysis to refine their signatures with application layer context. Protocol analysis, however, has been mainly used for misuse detection, which limits its application for the detection of unknown and novel attacks. In this contribution we address the issue of incorporating application layer context into anomaly-based intrusion detection. We extend a payload-based anomaly detection method by incorporating structural information obtained from a protocol analyzer. The basis for our extension is computation of similarity between attributed tokens derived from a protocol grammar. The enhanced anomaly detection method is evaluated in experiments on detection of web attacks, yielding an improvement of detection accuracy of 49%. While byte-level anomaly detection is sufficient for detection of buffer overflow attacks, identification of recent attacks such as SQL and PHP code injection strongly depends on the availability of application layer context.

Incorporation of Application Layer Protocol Syntax into Anomaly Detection. Patrick Düssel, Christian Gehl, Pavel Laskov and Konrad Rieck. Proc. of International Conference on Information Systems Security (ICISS), December 2008.

An Architecture for Inline Anomaly Detection.

2008-12-03T21:16:00.004+01:00

I am currently finishing my doctoral thesis, thus there is almost no time for interesting activities and fun. Fortunately, I am not the only one, see for instance here.

Besides all the work, the good news is that we will present an interesting paper on combining anomaly detection and intrusion prevention at the European Conference on Computer Network Defense (EC2ND). Here is the abstract from our contribution:

In this paper we propose an intrusion prevention system (IPS) which operates inline and is capable to detect unknown attacks using anomaly detection methods. Incorporated in the framework of a packet filter each incoming packet is analyzed and—according to an internal connection state and a computed anomaly score—either delivered to the production system, redirected to a special hardened system or logged to a network sink for later analysis. Run-time measurements of an actual implementation prove that the performance overhead of the system is sufficient for inline processing. Accuracy measurements on real network data yield improvements especially in the number of false positives, which are reduced by a factor of five compared to a plain anomaly detector.

An Architecture for Inline Anomaly Detection. Tammo Krueger, Christian Gehl, Konrad Rieck and Pavel Laskov. Proc. of European Conference on Computer Network Defense (EC2ND), December 2008.

Generalized Suffix Trees and Distinct Substrings.

2008-11-14T08:53:00.014+01:00

This is a technical post on strings, substrings and suffix trees. This could get boring. You have been warned.

Everybody knows the concept of longest common substring, where a set of strings is given and the task is to determine the longest substring shared by the set. While intuitive and straightforward to implement using a generalized suffix tree, this setting is not robust against "noise", such as corrupted or truncated strings. Moreover, finding the longest common substring is useless, if the considered strings derive from different data distributions, thus not necessary sharing any substring.

These shortcomings can be addressed by determining a set of shared substrings, which are shared by at least m strings but not necessary all strings in the set. To restrict the amount of small shared substrings, one requires the substrings to have a minimum length. This setting has been applied in the PolyGraph and Hamsa paper for automatic signature generation from network data. Again, an implementation is easily realized using a depth-first traversal of a generalized suffix tree. Unfortunately, many of the shared substrings will be prefixes and suffixes of each other.

This issue is resolved by the set of distinct shared substrings, where a distinct substring x is not contained in any other distinct substring y, unless x appears in at least m strings independently of y. Implementing this setting using generalized suffix trees is a little bit more involved. Together with a colleague, I came up with this approach:

We start to determine interesting substrings by a depth-first traversal of a generalized suffix tree.

This time, however, we are looking for distinct substrings and hence can not afford to output a substring that later turns out to be non-distinct. We thus first visit nodes which give rise to longer substrings, that is for each node we order the child nodes according to the length of possible substrings. Consequently, we find longer substrings first.

If we have determined a first substring x shared by m strings, we can be sure that it is distinct as no longer substrings exist. Next, we need to mark all non-distinct substrings of x. We do this by traversing the suffix links and parent nodes of x, thereby processing all suffixes and prefixes of x. For each node we maintain a counter indicating the number of strings the corresponding substring is shared by. When processing the prefixes and suffixes of x, we decrement this counter by the number of occurences of x.

Finally, we continue the depth-first traversal. We do not descend to nodes with a counter smaller than m, as no distinct shared substring can be determined on the corresponding path.

To be honest, I have not thoroughly thought about the complexity of this algorithm. Yet, I expect it to be "somewhat linear" in the length of the considered strings. The output of the algorithm resembles the concept of distinct substrings proposed in PolyGraph, where the authors apply a costly post-processing of shared substrings. Note that this approach can also be implemented using suffix and LCP arrays with the traversal techniques studied by Kasai et al.

Did I mention that I like string algorithms?

Automatic Feature Selection for Anomaly Detection.

2008-10-16T08:59:00.009+02:00

Network intrusion detection requires discriminative features from network traffic, which for the case of misuse detection allow for the precise formulation of signatures and rules, and which, on the other end, enable application of learning methods for anomaly detection. However, devising a set of features is not trivial, as attacks are reflected in all sorts of different patterns and numerical measures. A good example is the work of Kruegel at al. (see 1, 2, 3), in which various heterogeneous features are proposed and manually combined into an effective anomaly detection system.

Recently, colleagues at our lab came up with a method for automatic selection and weighting of such features for intrusion detection. Instead of defining a weighting of different features manually, the method automatically determines the mixture which optimizes the performance of anomaly detection. This optimization is realized by incorporating the process of feature selection directly into an anomaly detection method—a rather involved mathematical procedure. The paper will be presented at the AISec Workshop co-located with CCS. Following is its abstract:

A frequent problem in anomaly detection is to decide among different feature sets to be used. For example, various features are known in network intrusion detection based on packet headers, content byte streams or application level protocol parsing. A method for automatic feature selection in anomaly detection is proposed which determines optimal mixture coefficients for various sets of features. The method generalizes the support vector data description (SVDD) and can be expressed as a semi-infinite linear program that can be solved with standard techniques. The case of a single feature set can be handled as a particular case of the proposed method. The experimental evaluation of the new method on unsanitized HTTP data demonstrates that detectors using automatically selected features attain competitive performance, while sparing practitioners from a priori decisions on feature sets to be used.

Automatic Feature Selection for Anomaly Detection. M. Kloft, U. Brefeld, P. Düssel, C. Gehl, and P. Laskov. Proceedings of the First ACM Workshop on AISec, October 2008.

Approximate Kernels for Trees.

2008-09-28T08:42:00.012+02:00

The majority of machine learning and artificial intelligence methods are designed to work on vectorial data. In practice, however, data does not always come in the form of simple vectors. For instance, analysis of HTML documents requires processing and matching tree structures. The state-of-the-art techniques for learning with trees are convolutional kernel functions. These functions are effective but painfully slow on large trees. To speed-up such kernels for security applications, we came up with approximate tree kernels. Here is the abstract from the corresponding technical report:

Convolution kernels for trees provide effective means for learning with tree-structured data, such as parse trees of natural language sentences. Unfortunately, the computation time of tree kernels is quadratic in the size of the trees as all pairs of nodes need to be compared: large trees render convolution kernels inapplicable. In this paper, we propose a simple but efficient approximation technique for tree kernels. The approximate tree kernel (ATK) accelerates computation by selecting a sparse and discriminative subset of subtrees using a linear program. The kernel allows for incorporating domain knowledge and controlling the overall computation time through additional constraints. Experiments on applications of natural language processing and web spam detection demonstrate the efficiency of the approximate kernels. We observe run-time improvements of two orders of magnitude while preserving the discriminative expressiveness and classification rates of regular convolution kernels.

Approximate Kernels for Trees. Konrad Rieck, Ulf Brefeld and Tammo Krueger. Technical Report FIRST 5/2008, Fraunhofer Institute FIRST, September 2008.

Low throughput? The imbalance of network traffic.

2008-09-20T19:19:00.012+02:00

I have been recently running experiments with a "fast" learning method for anomaly detection in HTTP and FTP payloads. While the method performed well in terms of attack detection, the realized throughput was frustrating. Incoming traffic was processed at 15 mbit/s (HTTP) and 30 mbit/s (FTP) on a single CPU, including traffic normalization, TCP reassembly and anomaly detection.

How useful is such a low throughput?

Well, better than one might think. Depending on the considered application-layer protocol, there is often an imbalance of ingress and egress traffic. For example, the HTTP traffic at our institute has an ingress-egress ratio of 1/50, while the FTP traffic recorded at LBNL (port 21 only) reaches a ratio of 1/6. Thus, when looking at the total throughput the considered learning method yields around 770 mbit/s (HTTP) and 200 mbit/s (FTP) throughput. That's not so frustrating, given that the performance could be easily increased using multi-core systems.

For other protocols, however, the ingress-egress is not a small fraction and one can not indirectly benefit from the imbalance of traffic. In conclusion, when analyzing the run-time performance of an intrusion detection method it really matters which protocol and direction is monitored for evil things.

Portscanning the Internet.

2008-08-30T13:18:00.005+02:00

I just returned from a long holiday trip. While browsing through the list of blog postings I missed during this period, I noticed an interesting article on large-scale port scanning:

Portscanning the Internet posted at the THC blog.

The author reports on his experience with port scanning methods, which are capable to scan the entire Internet in a reasonable time frame. Besides several remarks on how to conduct such scans and how to threshold a scanning system, there is also a funny side note on a false worm outbreak caused by scanning activities.

Slides for Talk on Learning Malware Behavior.

2008-07-11T18:26:00.011+02:00

I just noticed that heise security posted a short note on our recent paper presented at DIMVA 2008. Cool. As an addition to the technical paper, I am thus also providing the slides for my talk. Have fun.

Learning and Classification of Malware Behavior.

2008-07-11T09:24:00.005+02:00

Yesterday, I have been presenting some of our joint work with the University of Mannheim on malware analysis at this year's DIMVA. The corresponding paper is available online:

Learning and Classification of Malware Behavior. To appear in Proceedings of Fifth Conference on Detection of Intrusions and Malware & Vulnerability Assessment (DIMVA), 2008.

Thorsten Holz wrote a nice summary of our key results in his blog yesterday. In essence, we devise a method for automatic classification of malware families based on their behavior. The method proceeds by learning behavioral patterns from malware monitored in a sandbox. Starting from a set of malware binaries labeled by an anti-virus scanner, the method generalizes observed behavior so that variants undetected by anti-virus products can be identified. Moreover, the method is transparent to the security practitioner as the learning model can be examined and decisions made by the system can be traced back to behavioral patterns discriminative for each malware family.

A Self-Learning System for VoIP Security.

2008-06-26T23:52:00.009+02:00

Next week I will present some of our research on learning-based security systems on the IPTCOMM 2008 conference. The resulting paper is available at the following link:

A Self-Learning System for Detection of Anomalous SIP Messages. To appear in Proceedings of Principles, Systems and Applications of IP Telecommunications (IPTCOMM), 2008.

In this joint work with Bell Labs Germany, we propose a system for automatic detection of unknown attacks in SIP. The system
identifies anomalous content by cleverly mapping SIP messages to a vector space, in which deviation from normality can be expressed geometrically. We present some nice experiments demonstrating the high accuracy of the proposed system (no false-positives on a data set of real SIP traffic) and, also, its moderate througput rate (about ~70 mbit/s).

Ph-Neutral on an Island.

2008-05-25T18:09:00.009+02:00

I have spent part of the weekend at Ph-Neutral, a mini-conference bringing together blackhat and whitehat people.

This year the organizers did an excellent job choosing a location: the conference took place on an island in the middle of Berlin called "Die Insel". The island featured two different bars, room for talks and a cosy beach. What a nice location.

A Honeypot at Home.

2008-05-10T09:49:00.006+02:00

I am running a small honeypot at my home dialup capturing unsolicited traffic. Today I found the time to view through its logs. Although I could not spot anything special, I had a good time examining the catch, such as various scans for proxies, relays and vulnerabilities, e.g.

GET http://www.woqianqi.cn/go.php HTTP/1.0
CONNECT mx3.mail2000.com.tw:25 HTTP/1.0
GET /cacti/cmd.php HTTP/1.0
GET /w00tw00t.at.ISC.SANS.DFind:) 
[...]

While not a professional tool for monitoring internet threats, a honeypot at home suffices to observe incoming cruft and, eventually, have a good time.

First ACM Workshop on AISec.

2008-04-17T22:19:00.006+02:00

At this year's CCS conference there will be a special ACM workshop on artificial intelligence for security, named AISec. The call for papers and further information on the workshop are available at the workshop site www.aisec.info.

This looks like some pretty interesting event. The deadline for submissions of full papers is the 9th May 2008. Proceedings will be published by the ACM.

Machine Learning Open Source Software.

2008-04-09T12:48:00.007+02:00

In case you missed it, there is a new track in JMLR dedicated to open source software for machine learning (MLOSS). As a first result of this effort, a community-driven web site has been started providing a platform for distribution and discussion of open machine learning software. The web site is available at www.mloss.org and features a large body of learning software to download.

I like it a lot and plan to submit some of my recent software projects; given they reach a mature state (which of course might never happen).

Casting out Demons.

2008-04-03T12:03:00.013+02:00

There is an interesting paper at this year's IEEE S&P: Gabriela Cretu and colleagues propose a method for sanitizing of training data for anomaly detection. The sanitization procedure essentially builds on learning small models from random samples and performing majority voting. Sounds familiar? This is another variant of bagging, here in the context of security for removal of unknown attacks from training data.

Casting out Demons: Sanitizing Training Data for Anomaly Sensors. To appear in the Proceedings of the IEEE Symposium on Security & Privacy, May 2008, Oakland, CA.

A small nit: I missed a comparison to anomaly detection methods capable to learn on dirty data, and thus eliminating the need of prior sanitization. But anyway...