Machine-Learning to Hack

To date the most important security vulnerabilities have been found via laborius code auditing. Also, this is the only way vulnerabilities can be found and fixed during development. However, as software production rates increase, so does the need for a reliable, automated method for checking or classifiying this code in order to prioritize and organize human efforts in manual checks. We’re living in an age where machine learning is playing well in several other technological fields, how about applying it to our bug-finding appetite?

In this and upcoming articles, we are interested in the use of machine learning (ML) techniques to find security vulnerabilities in source code. It is important to specify this since, as we will see, there are many other related, but different, approaches such as:

The idea of using ML techniques for VD is not new. There are papers on the matter as old as 2001. Here we’ll try to describe in simple terms:

We will be following and building on top of two previous state-of-the-art papers

We feel the grouping by semantic features extracted from code approach makes more sense, as do Ghaffarian and Shahriari (2017)^[2], These are further subdivided into:

Most of the papers in this category are not security-focused, but their ideas can be used for VD. Also most of these works revolve around extracting features such as:

The system Chucky by Yamaguchi et al. (2013) is the one that interests us the most since it is more compatible with our interests, i.e., lightening the burden of manual code auditors; also, they achieve both the aforementioned objectives: detecting missing checks through security logic (v.g. access control) and secure API usage (v.g. checking buffer size). It uses the bag-of-words model to represent the code and the k-nearest-neighbors technique to analyze it. 'Chucky' discovered 12 new vulnerabilites in high-profile projects such as Pidgin and LibTIFF. See our article on Chucky for details.

A year later, Yamaguchi et al. (2014) reuse this idea of exploiting graph representations of code in order to find vulnerable code patterns. This time they propose automating the design of effective traversals which might lead to vulnerability detection using the unsupervised clustering approach. This resulted in the tool 'Joern', which was able to find 5 zero-day vulnerabilities in products like Pidgin.

Most of the papers in this category are not security focused. All of them use frequent itemset mining, only with different features to mine and different targets to extract. We summarize them here for the sake of completeness:

In general terms, anomaly detection approaches have the following limitations:

The aim is to take a large dataset of vulnerability samples and extract vulnerable code patterns using (usually supervised) machine learning algorithms. The key is the technique used for extracting features, which range from convential parsers, data-flow and control-flow analysis, and even directly text mining the source code. Most of these papers use classification algorithms.

Once more Yamaguchi et al. (2011, 2012) take the lead, mimicking the mental process behind the daily grind of the code auditor: searching for similar instances of recently discovered vulnerabilities. They sensibly call this 'vulnerability extrapolation'. The gist: parse, embed into vector space via a bag-of-words-like method, perform semantic analysis to obtain particular matrices, and then compare to known-vulnerable code using standard distance functions.

Other approaches in this category are Scandariato et al. (2014) and Pang et al. (2015), who attempted to use techniques such as n-gram analysis using bag-of-words, but with limited results, probably due to shallow information and simple methods.

The binary analysis tool VDiscover doesn’t exactly fit our definition, but deserves mentioning. They identify each trace of a call to the standard C library as a text document and process them as n-grams and encode them with word2vec. They have tested several ML techniques such as logistic regression, MLP and random forests.

In the last few months, some in-scope papers have appeared. Li et al. propose two systems: VulDeePecker (2018a) and SySeVR (2018b), which claim to extract both syntactic and semantic information from the code, thus also considering both data and control flow. They report good results with low false positives and 15 zero-day vulnerabilities in high-profile open source libraries. See our article on these systems.

Lin et al. (2017) propose a different variant which simplifies the feature extraction, going back to just AST with no semantic information, using deep learning in the form of bidirectional long short-term memory (BLSTM) networks, plus a completely new element: unlike the vast majority of previous works, which work in the within-project domain, POSTER involves software metrics (see below) in order to compare to other projects.

However interesting these approaches seem, they are not without limitations:

Software metrics such as:

have been proposed as 'predictors' for the presence of vulnerabilities in software projects. These studies use mostly manual procedures based on publicly available vulnerability sources such as NVD. According to [2] and Walden et al. (2014), predicting the existence of vulnerabilities based on software engineering metrics could be thought of as a case of "confusing symptoms and causes":

Hence, most papers reviewed in this category present high false positive rates and hardly one of them has explored automated techniques.

That was the panorama of machine learning in software vulnerability research as of late 2018. Some limitations that are common:

Thus our good old pentest is not dead. Even at the level of cutting-edge research, automated vulnerability discovery, and especially confirmation and exploitation, are tasks for human experts.