Machine Learning for Computer Security.

Second Call for Papers: EC2ND 2010.

noreply@blogger.com (Konrad Rieck) — Mon, 14 Jun 2010 06:17:00 +0000

Only three weeks to go: The sixth European Conference on Computer Network Defense (EC2ND) invites submissions presenting novel ideas in the areas of network defense, intrusion detection and systems security. We specifically encourage submissions presenting work at an early stage with the intention to act as a discussion forum for innovative security research.

Paper submission deadline: July 2, 2010
Paper acceptance or rejection: August 6, 2010
Conference dates: October 28-29, 2010

More information on EC2ND 2010 and paper submission are available at the conference website. Additionally, you can also follow on twitter: ec2nd.

TokDoc: The Token Doctor.

noreply@blogger.com (Konrad Rieck) — Thu, 22 Apr 2010 17:20:00 +0000

Detecting and preventing network intrusions is a basic task in computer security. Thus, it no surprise that there exists several security products capable to block network attacks, though with moderate success and restricted to a database of known attack patterns. For a security researcher two issues with these systems are not satisfactory. First, current intrusion prevention systems rely on a up-to-date database of attack signatures. Novel and unknown attacks will likely go undetected. Second, network traffic is either passed or completely blocked—often with fatal consequences and cut-off of benign communication.

In recent years, security research has focused on addressing the first issue by extending intrusion detection systems with techniques of statistics and machine learning. The resulting systems proof effective in many scenarios. Still, they build on a binary pass-or-block decision on every analyzed event. What if we question this rigid decision making? Together with Tammo Krueger, Christian Gehl and Pavel Laskov, we have dared to go one step beyond. In a recent paper, we propose a web-application firewall that is not only capable to detect network attacks, but provides means to "heal" abnormal content to some degree. We call it the Token Doctor.

The Token Doctor, or short TokDoc, acts as a reverse proxy and inspects incoming requests of HTTP traffic. Each requests is parsed into its individual tokens, such as the URL, parameters, headers and so on. Each tokens is then analyzed individually using anomaly detection techniques. If an anomaly is spotted in a token, a fine-grained process is launched. Some tokens, such as usernames and cookie values, can not be corrected, hence there are simply dropped from the request as with usual prevention systems. Other tokens, however, are "healed" by replacing them with benign content. This replacement is automatically selected by determining similar tokens in a pool of benign HTTP requests.

The "healing" implemented in TokDok is not guaranteed to succeed. Frankly speaking, automatic amending of network data is a controversial idea and one can image a lot of things going wrong. Nevertheless, our experiments demonstrate the opposite. TokDoc provides an excellent detection accuracy while significantly reducing false positives in comparison to state-of-the-art methods. For example, several benign requests, which would been dropped by a regular systems due to minor irregularities, are slightly amended without effects on functionality. Overall, there is room for discussion: Either stick to a rigid decision with painful blocking or choose a fuzzy amending with lots of promises but no guarantees. I don't know.

A corresponding paper has been published at the 24th ACM Symposium on Applied Computing (SAC) this year. Its abstract is here:

The growing amount of web-based attacks poses a severe threat to the security of web applications. Signature-based detection techniques increasingly fail to cope with the variety and complexity of novel attack instances. As a remedy, we introduce a protocol-aware reverse HTTP proxy TokDoc (the token doctor), which intercepts requests and decides on a per-token basis whether a token requires automatic "healing". In particular, we propose an intelligent mangling technique, which, based on the decision of previously trained anomaly detectors, replaces suspicious parts in requests by benign data the system has seen in the past. Evaluation of our system in terms of accuracy is performed on two real-world data sets and a large variety of recent attacks. In comparison to state-of-the-art anomaly detectors, TokDoc is not only capable of detecting most attacks, but also significantly outperforms the other methods in terms of false positives. Runtime measurements show that our implementation can be deployed as an inline intrusion prevention system.

TokDoc: A Self-Healing Web Application Firewall. Tammo Krueger, Christian Gehl, Konrad Rieck and Pavel Laskov. Proc. of 25th ACM Symposium on Applied Computing (SAC), 1846-1853, March 2010.

Call for Papers: SICHERHEIT 2010

noreply@blogger.com (Konrad Rieck) — Sat, 20 Mar 2010 11:48:00 +0000

I am happy to serve on the program committee of the conference "Sicherheit, Schutz und Zuverlässigkeit" (SICHERHEIT) which will take place in October 2010 in Berlin. SICHERHEIT is the German forum for experts from academia and industry to discuss aspects of safety (protection from catastrophic events of technical systems) and security (protection of confidentiality and integrity of information in technical systems).

The organizers seek submissions from the broad range of safety and security, for example on the following topics:

biometrics, privacy, data protection
e-commerce, e-government
certification of safe and secure systems
cryptography, digital signatures, steganography
development and maintenance of safe and secure systems
formal methods for safe and secure systems
management of safe and secure systems
management of information security
network security
reactive security
reliability and availability

The conference language is English and SICHERHEIT welcomes participants and submissions from non-German-speaking countries. More information can be found at www.sicherheit2010.de. Deadline for paper submissions is March, 29th. So hurry up!

Efficient Machine Learning with Trees.

noreply@blogger.com (Konrad Rieck) — Wed, 03 Mar 2010 18:50:00 +0000

Trees are a natural and intuitive representation of data in many domains of computer science. Although ubiquitous, analysis of tree data is far from trivial. Most techniques of machine learning are confined to operate in vector spaces and lack the ability to process trees. A solution to this problem is provided by tree kernels which allow for application of kernel-based learning methods to tree data. Unfortunately, the run-time complexity of tree kernels is inherently quadratic in the number of nodes. While small trees can be processed with minor overhead, learning with larger trees gets intractable. For example, the computation of a regular kernel for two parse trees of HTML documents comprising 10,000 nodes each, requires about 1 Gigabyte of memory and takes over 100 seconds on a recent computer system. Given that kernel computations are performed millions of times in large-scale learning, it is evident that regular tree kernels are an inappropriate choice in many learning tasks.

As a result, we have often abstained from using tree data in our research. However, we recently found the time to address this problem and devised approximate tree kernels. Instead of fiddling with algorithmic issues and implementations, we propose to approximate the computation of kernel functions for trees. To this end, we narrow the kernel computation to a sparse subset of subtrees rooted at relevant symbols and thereby avoid considering all possible subtrees as in regular tree kernels. This sparse subset is automatically selected with respect to a given learning task, such that the expressiveness of the approximate kernel is preserved while its run-time is reduced. Though simple in design, this approximation enables speed-ups up to three orders of magnitude and, for the first time, allows to compare HTML documents for detection of Web spam efficiently.

The concept of approximate tree kernels as well as several applications are described in a recent article published in the Journal of Machine Learning Research. The abstract for the article is given below:

Convolution kernels for trees provide simple means for learning with tree-structured data. The computation time of tree kernels is quadratic in the size of the trees, since all pairs of nodes need to be compared. Thus, large parse trees, obtained from HTML documents or structured network data, render convolution kernels inapplicable. In this article, we propose an effective approximation technique for parse tree kernels. The approximate tree kernels (ATKs) limit kernel computation to a sparse subset of relevant subtrees and discard redundant structures, such that training and testing of kernel-based learning methods are significantly accelerated. We devise linear programming approaches for identifying such subsets for supervised and unsupervised learning tasks, respectively. Empirically, the approximate tree kernels attain run-time improvements up to three orders of magnitude while preserving the predictive accuracy of regular tree kernels. For unsupervised tasks, the approximate tree kernels even lead to more accurate predictions by identifying relevant dimensions in feature space.

Approximate Tree Kernels. Konrad Rieck, Tammo Krueger, Ulf Brefeld and Klaus-Robert Müller. Journal of Machine Learning Research (JMLR), 11(Feb):555−580, Microtome, 2010.

Call for Papers: EC2ND 2010.

noreply@blogger.com (Konrad Rieck) — Fri, 19 Feb 2010 09:08:00 +0000

As program chair, I am happy to announce the sixth European Conference on Computer Network Defense (EC2ND 2010) in Berlin, Germany. The conference brings together researchers from academia and industry within Europe and beyond to present and discuss current topics in applied network and systems security.

EC2ND 2010 invites submissions presenting novel ideas in the areas of network defense, intrusion detection and systems security. Topics for submission include but are not limited to:

Intrusion Detection
Malicious Software
Web Security
Security Policy
Peer-to-Peer and Grid Security
Wireless and Mobile Security
Network Forensics
Network Discovery and Mapping
Incident Response and Management
Privacy Protection
Cryptography
Legal and Ethical Issues

A detailed call for papers is available here. Note the following important dates:

Paper submission deadline: July 2, 2010
Paper acceptance or rejection: August 6, 2010
Final paper camera ready copy: August 13, 2010
Conference dates: October 28–29, 2010

I am looking forward to interesting contributions and an awesome conference.

Malheur is out!

noreply@blogger.com (Konrad Rieck) — Wed, 30 Dec 2009 11:39:00 +0000

After almost a year of work, I am proud to announce the first public release of Malheur—a tool for automatic analysis of program behavior recorded from malicious software (www.mlsec.org/malheur).

Malicious software (malware) is one of the major threats in the Internet today and millions of hosts are currently infected with malware programs, such as computer worms, backdoors and trojan horses. The sheer amount of malware renders manual analysis of malicious files impossible and, even worse, automatic inspection of file content is strongly obstructed by obfuscation techniques. An alternative for efficiently crafting new defenses against malware is behavior-based analysis: Malware programs are collected in the wild and executed in a sandbox environment, where their behavior is monitored. The execution of each binary results in a report of monitored behavior which can be used to characterize and ultimately defend against malicious software.

As the first publicly available tool, Malheur analyzes program behavior of malicious software and enables automatic discovery and discrimination of novel variants. This ability is rooted in well-known concepts of machine learning. Discovery of novel malware classes resembles a clustering problem and discrimination between classes matches a classification task. Both techniques are implemented in Malheur with effectivity and efficiency in mind. Instead of fiddling with esoteric learning concepts, Malheur resorts to basic methods, such as linkage clustering and nearest-prototype classification, which are efficiently implemented by means of parallel programming. Expressive access to recorded behavior is realized by embedding reports in a vector space spanned by short behavioral patterns, similar in spirit to bag-of-words models.

Malheur is a joint effort of Berlin Institute of Technology and University of Mannheim. The merits of Malheur along with an empirical evaluation using real malware are detailed in a technical report:

Automatic Analysis of Malware Behavior using Machine Learning. Konrad Rieck, Philipp Trinius, Carsten Willems and Thorsten Holz. Technical Report 18-209, Berlin Institute of Technology, 2009.

My Thesis as a Paperback.

noreply@blogger.com (Konrad Rieck) — Thu, 26 Nov 2009 08:17:00 +0000

It may sound a little odd, but when I submitted my thesis to the library of my university, I was missing something. Back then, all I had to do was to send in some PDF file and fill out some form. Had the outcome of several months of hard work been yet another PDF document?

Recently, I started to alleviate this strange pain by publishing my thesis as a print-on-demand book at lulu.com. The process is pretty straightforward and, given that most of us work with latex, took only a couple of hours to adapt the sources. Needless to say, that I felt much better, once I held the first paperback version of the thesis in my hands. And, if you are truly interested in reading this work, you can also grab a paperback copy for only 9.99€.

Of course, if you aim for true scientific glory, it might be more appropriate to hunt for a renowned publisher, convince the editors, struggle with presentation and content requirements and finally receive a real book at about 99€.

Visualization of Payload-based Anomaly Detection.

noreply@blogger.com (Konrad Rieck) — Sun, 15 Nov 2009 12:47:00 +0000

Two paradigms for detection of attacks against computer systems have been widely studied in security research: First, misuse detection which aims at identifying known patterns of misuse and, second, anomaly detection which tries to detect deviations from normal usage. While both concepts have their individual pros and cons, only one of the two paradigms, namely misuse detection, has made its way into regular security products. For example, almost all anti-virus scanners and intrusion detection systems employ a database of known misuse patterns for spotting security problems. Although successful on the market, misuse detection inherently fails to protect from novel threats, such as zero-day exploits. In turn, anomaly detection methods provide means to identify unknown threats with high precision and low run-time overhead (see for instance work by Cretu, Ingham, Perdisci or myself). So, why is there still a lack of acceptance for anomaly detection in practice?

One key problems with most anomaly detection approaches is their inability to explain decisions. The detection process resembles a black-box and security operators are required to thoroughly analyze context information to assess the actual cause of a reported anomaly. We have addressed this problem in a recent paper published at the European Conference on Computer and Network Defense (EC2ND). In particular, we present visualization techniques suitable for explaining the decisions of payload-based anomaly detection systems. Instead of digging into the technical details, I herein present an example for explaining the detection of a real network attack. An in-depth discussion is provided in our paper.

The above figures shows so called feature differences of a command injection attack (awstats configdir exploit), where peaks indicate string features that strongly deviate from a model of normal network traffic. The attack exploits an insecure handling of input parameters to pass shell commands to an HTTP server. The transferred commands are mapped to the standard URI scheme, which replaces reserved characters by the symbol “%” and an hexadecimal value. For example, “%20” denotes a space symbol, “%3b” a semi-colon, “%26” an ampersand and “%27” an apostrophe. In particular, the semi-colon and ampersand are characteristic for shell commands as they reflect specific semantics of shell syntax .In the presented visualization exactly these patterns are represented as high peaks. While similar string patterns can be also observed in legitimate traffic, the high differences in the figure clearly indicate an anomalous activity involving escaped shell commands and explain the reason for reporting of an anomaly.

Another visualization technique, feature shading, is presented in the
second figure, where the payload of a reported anomaly is superimposed with color reflecting the individual deviation of each byte from a model of normal network traffic. The URI of the command injection attack is flagged as anomalous by dark shading, thus indicating the presence of abnormal strings. The part ensuing the URI, however, is indicated as normal region, as it mainly contains frequent HTTP patterns, such as “Mozilla” and “Googlebot”. This example demonstrates the ability of a shading to emphasize anomalous contents in network payloads, while also indicating benign regions and patterns.

By visualizing a “colorful” network payload a security operator is able to quickly identify relevant and malicious content in data, eventually enabling effective countermeasures. Consequently, the decisions made by a payload-based detection system – so far opaque to a security operator – can now be visually explained, such that one can benefit from early detection of novel attacks as well as an explainable detection process.

Visualization and Explanation of Payload-Based Anomaly Detection. Konrad Rieck and Pavel Laskov. Proceedings of 5th European Conference on Computer and Network Defense (EC2ND).

Detecting the "Phoning Home" of Malicious Software.

noreply@blogger.com (Konrad Rieck) — Thu, 22 Oct 2009 09:48:00 +0000

Malicious software poses a severe threat to security of computer systems. Whether you download a file, plug in the USB stick of a colleague or simply surf the Web, your computer is always at risk to be compromised by malicious software, such as computer worms, backdoors or Trojan horses. Once the evil has infiltrated your system, it usually initiates a process referred to as "phoning home": The malicious software contacts its author and hands over control of your computer to him, for example for sending spam messages or conducting a distributed flooding attack. Unfortunately, regular security tools, such as anti-virus scanners, increasingly fail to protect the many infection vectors of malicious software and thus users are often left alone with systems "phoning home" to bad people.

In our latest research (to be published at the 25th ACM Symposium on Applied Computing) we address this problem and introduce Botzilla, a method for automatically detecting the "phoning home" of malicious software. Botzilla operates by first collecting malicious software in the wild using honeypots. The malicious software is then repetitively executed in a controlled environment and its communication is recorded— similar to a rat in a lab. Invariants communication patterns, such as byte strings used for handshaking and remote control, are extracted and assembled to detection signatures using a naive-Bayes classification scheme. As a result, Botzilla is able to automatically generate signatures for malicious software within minutes and allows to counteract the propagation of evil in the first round. An abstract for this work is here:

Hosts infected with malicious software, so called malware, are ubiquitous in today's computer networks. The means whereby malware can infiltrate a network are manifold and range from exploiting of software vulnerabilities to tricking a user into executing malicious code. Monitoring and detection of all possible infection vectors is intractable in practice. Hence, we approach the problem of detecting malicious software at a later point when it initiates contact with its maintainer; a process referred to as "phoning home". In particular, we introduce Botzilla, a method for detection of malware communication, which proceeds by repetitively recording network traffic of malware in a controlled environment and generating network signatures from invariant content patterns. Experiments conducted at a large university network demonstrate the ability of Botzilla to accurately identify malware communication in network traffic with very low false-positive rates.

Botzilla: Detecting the "Phoning Home" of Malicious Software. Konrad Rieck, Guido Schwenk, Tobias Limmer, Thorsten Holz and Pavel Laskov. Proceedings of 25th ACM Symposium on Applied Computing (SAC).

The work on Botzilla is a small yet successful effort of Berlin Institute of Technology, Fraunhofer FIRST, University of Erlangen, Technical University Vienna and University of Tübingen.

Active Learning for Network Intrusion Detection.

noreply@blogger.com (Konrad Rieck) — Wed, 26 Aug 2009 13:00:00 +0000

Two paradigms for application of machine learning to security are prevalent: First, supervised learning as employed in spam filtering and, second, unsupervised learning as applied for network anomaly detection. Supervised learning methods construct models for data using label information attached to each data object. For example, email messages tagged as spam and non-spam are used to learn a discriminative model for spam filtering. In contrast, unsupervised learning methods operate on given data only and do not make use label information. For example, models for detection anomalous network payloads are usually learned from unlabeled network traffic without the need to label million of network payloads.

Besides these two paradigms, however, learning theory also provides the hybrid concept of semi-supervised learning. Although technically more involved, semi-supervised methods combine the best of the classic learning paradigms: The majority of training data can be unlabeled, whereas only few instances need to be equipped with label information for learning. Semi-supervised methods are more accurate than unsupervised methods while not suffering from the problem of labeling large amounts of data. Unfortunately, the security community has largely ignored semi-supervised learning and, consequently, often argues for either one of the two classic learning paradigms.

In a first study, we have applied the concept of semi-supervised learning to network security and devised an learning method for network intrusion detection. Our method initially operates on unlabeled data as most of previous learning approaches to intrusion detection. However, the devised method then specifically requests label information for certain network events to improve the learning model. For example, our method requests labels for points that lie close to the decision boundary and thus may sharpen the detection accuracy. With only a minimal labeling effort a security operator can tune our method to particular network data and eliminate false-positive alarms that come with the majority of regular detection approaches. A paper of this work has been recently
accepted at AISEC 2009. Here is its abstract:

Anomaly detection for network intrusion detection is usually considered an unsupervised task. Prominent techniques, such as one-class support vector machines, learn a hypersphere enclosing network data, mapped to a vector space, such that points outside of the ball are considered anomalous. However, this setup ignores relevant information such as expert and background knowledge. In this paper, we rephrase anomaly detection as an active learning task. We propose an effective active learning strategy to query low-conﬁdence observations and to expand the data basis with minimal labeling effort. Our empirical evaluation on network intrusion detection shows that our approach consistently outperforms existing methods in relevant scenarios.

Active Learning for Network Intrusion Detection. Nico Görnitz, Marius Kloft, Konrad Rieck and Ulf Brefeld. Proceedings of CCS Workshop on Security and Artificial Intelligence (AISEC), October 2009.

Twimpact: An Impact Factor for Twitter.

noreply@blogger.com (Konrad Rieck) — Tue, 18 Aug 2009 07:15:00 +0000

There is one hype that I have not made friend with in the last year: Twitter. Recently, my colleagues Mikio Braun and Matthias Jugel have launched a new project named Twimpact, which aims at providing an impact factor for twitter posts (tweets) – demonstrating that Twitter might be more than just a bunch of pointless messages. I am not sure, though. The official project website is located at www.twimpact.com. An introduction to the underlying twimpact factor is provided here.

Machine Learning for Application-Layer Intrusion Detection.

noreply@blogger.com (Konrad Rieck) — Tue, 14 Jul 2009 08:16:00 +0000

Banzai! Yesterday, I handed over the last print outs of my Ph.D. thesis to the library of the Berlin Institute of Technology. My doctoral defense was a thrilling yet enjoyable event, especially due to challenging questions raised by John McHugh, whom I have to cordially thank for coming to Berlin. After all, it was a great success. I am now heading for a long holiday to recover from and prepare for more exciting research.

Following is the official summary of the thesis. A PDF version is available here.

Misuse detection as employed in current network security products relies on the timely generation and distribution of so called attack signatures. While appropriate signatures are available for the majority of known attacks, misuse detection fails to protect from novel and unknown threats, such as zero-day exploits and worm outbreaks. The increasing diversity and polymorphism of network attacks further obstruct modeling signatures, such that there is a high demand for alternative detection techniques.

We address this problem by presenting a machine learning framework for automatic detection of unknown attacks in the application layer of network communication. The framework rests on three contributions to learning-based intrusion detection: First, we propose a generic technique for embedding of network payloads in vector spaces such that numerical, sequential and syntactical features extracted from the payloads are accessible to statistical and geometric analysis. Second, we apply the concept of kernel functions to network payload data, which enables efficient learning in high-dimensional vector spaces of structured features, such as tokens, q-grams and parse trees. Third, we devise learning methods for geometric anomaly detection using kernel functions where normality of data is modeled using geometric concepts such as hyperspheres and neighborhoods. As a realization of the framework, we implement a standalone prototype called Sandy applicable to live network traffic.

The framework is empirically evaluated using real HTTP and FTP network traffic and over 100 attacks unknown to the applied learning methods. Our prototype Sandy significantly outperforms the misuse detection system Snort and several state-of-the-art anomaly detection methods by identifying 80-97% unknown attacks with less
than 0.002% false positives—a quality that, to the best of our knowledge, has not been attained in previous work on network intrusion detection. Experiments with evasion attacks and unclean training data demonstrate the robustness of our approach. Moreover, run-time experiments show the advantages of kernel functions. Although operating in a vector space with millions of dimensions, our prototype provides throughput rates between 26-60 Mbit/s on real network traffic. This performance renders our approach readily applicable for protection of medium-scale network services, such as enterprise Web services and applications.

While the proposed framework does not generally eliminate the threat of network attacks, it considerably raises the bar for adversaries to get their attacks through network defenses. In combination with existing techniques such as signature-based systems, it strongly hardens today's network protection against future threats.

Machine Learning for Application-Layer Intrusion Detection.
Konrad Rieck. Ph.D. thesis, Berlin Institute of Technology (TU Berlin), 2009.

Securing IMS against Novel Threats.

noreply@blogger.com (Konrad Rieck) — Thu, 09 Jul 2009 16:35:00 +0000

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.

noreply@blogger.com (Konrad Rieck) — Fri, 29 May 2009 16:05:00 +0000

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.

noreply@blogger.com (Konrad Rieck) — Mon, 04 May 2009 17:57:00 +0000

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.

noreply@blogger.com (Konrad Rieck) — Tue, 07 Apr 2009 18:06:00 +0000

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.

noreply@blogger.com (Konrad Rieck) — Sun, 25 Jan 2009 16:02:00 +0000

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.

noreply@blogger.com (Konrad Rieck) — Thu, 18 Dec 2008 12:55:00 +0000

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.

noreply@blogger.com (Konrad Rieck) — Wed, 17 Dec 2008 16:33:00 +0000

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.

noreply@blogger.com (Konrad Rieck) — Wed, 03 Dec 2008 20:16:00 +0000

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.

noreply@blogger.com (Konrad Rieck) — Fri, 14 Nov 2008 07:53:00 +0000

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.

noreply@blogger.com (Konrad Rieck) — Thu, 16 Oct 2008 06:59:00 +0000

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.

noreply@blogger.com (Konrad Rieck) — Sun, 28 Sep 2008 06:42:00 +0000

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.

noreply@blogger.com (Konrad Rieck) — Sat, 20 Sep 2008 17:19:00 +0000

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.

noreply@blogger.com (Konrad Rieck) — Sat, 30 Aug 2008 11:18:00 +0000

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.