Introduction to variant analysis with QL and LGTM (Part 1)

February 19, 2019


Technical Difficulty

Reading time

In software development, we often see the same coding mistakes being made repeatedly over the course of a project's lifetime. These same mistakes can even show up across multiple projects. Sometimes there are a number of simultaneously active instances of these mistakes, and sometimes there’s only ever one active instance at a time, but they keep reappearing. When such mistakes lead to security vulnerabilities, the consequences can be quite severe.

In this post, I'll explain how you can use variant analysis with QL to solve this problem, and demonstrate how you can utilize LGTM for variant analysis on your own projects, using a real-life example on systemd.

Are repeated mistakes that common?

Before we get into variant analysis, I want to start with an example. There have been a lot of high profile cases in which the same bugs have reappeared over and over again. Take for instance this vulnerability found by Tavis Ormandy of Google’s Project Zero:

ghostscript 1

We can see from this comment that this is not the first bug that Tavis has found in Ghostscript. He was reviewing the fix for a bug that he had reported previously and discovered that they hadn’t fixed it properly.

So let’s follow the trail to issue 1690:

ghostscript 2

Yet again, we see a comment referring to a previous bug!

And if we follow the link, the trail of misery continues!

ghostscript 3

The same bug is repeatedly being discovered month after month in different parts of the codebase. Each time one instance is fixed, another variant of the issue is discovered. Let's stop here, because you probably get the picture.

This teaches us a very important lesson: bugs are rarely unique. They keep cropping up in different locations as a project develops over time, often in slightly modified forms or variants.

So what is variant analysis?

Whenever a security vulnerability is discovered (whether through security research, during code review, through a bug bounty program, or by any other process), we are presented with an opportunity. We should investigate how often the mistake is repeated, determine whether there are any other similar vulnerabilities in the codebase, and implement a process to prevent the mistake from happening again.

variant analysis 2

The first step is to diagnose what went wrong so that we can find and fix the bug. But, as we have learned, that’s typically not enough since most bugs are not unique. This is where variant analysis comes into play.

Variant analysis is the process of taking an existing vulnerability, finding the root cause, and searching for variants of the problem in a codebase. Traditionally, this is done by security researchers and not developers, but this need not be the case, as I explain below. It is important to find all such variants and patch them simultaneously, otherwise these vulnerabilities could potentially be exploited in the wild. Once all variants have been found, the final step is to make sure that similar bugs aren't introduced again.

How do we go about finding variants?

The most common automated security research techniques used today include regression testing, unit testing, and fuzzing. They are valuable tools for helping to secure a codebase, but none of these methods are optimal for finding variants of known vulnerabilities. Beyond automation, you could manually review code for variants; however on any reasonably-sized project (or collection of projects), manually combing through the entire codebase is completely infeasible, especially for anything that is more than just syntactic. Additionally, a manual process that only checks incoming code changes doesn't give you any insight into what existing vulnerabilities may exist, and, of course, is susceptible to human error.

Another issue developers face when attempting to secure their code is that they often lack certain security knowledge, or understanding of how vulnerabilities could potentially be exploited. This specialized knowledge and tooling is usually found only among members of a company’s security team. The developers are forced to rely solely on their company's security team for this information, and therefore have little control over the state of the security of their projects. For example, when working on open source projects, contributors might not have complete context-specific knowledge of the entire codebase, and inadvertently introduce code that leads to security vulnerabilities.

Luckily, there is a resource available that can automate much of the heavy lifting of variant analysis, removing the need to manually comb through source code, and sharing security knowledge and best practices. The best part though is that this technology is completely free for open source projects.

Meet QL, the technology behind LGTM. QL adopts an entirely new approach to analyzing code: treat it as data. Firstly, every aspect of a codebase is pulled into a special relational database. You can query this database to find anything from basic syntactic patterns to complex issues that require deep interprocedural analysis or data-flow, and which were previously impossible to detect automatically. This allows developers to utilize QL to automate and scale variant analysis: After root cause analysis has been performed, you write and modify queries to find code patterns that are semantically similar to the original vulnerability. Any results are triaged as usual and provided to the engineering teams to implement fixes. Beyond this, each query can then be placed in a central repository to be shared with others, both inside and outside an organisation. These queries are then run continuously to catch new variants before they can cause problems.

How can you use QL on LGTM?

If you’re using LGTM, you’re already using QL! LGTM has an alert view for the latest version of a project's source code, produced by running QL’s standard queries against that code base. These queries are all open source, and are constantly updated, pulling in shared knowledge from security teams at our customers, our in-house experts, and other users of QL too. You can also use LGTM’s automated code review integration to run these queries for each pull request, and catch problems before they are merged. Beyond this, you can add your own specialized queries to your repositories, and have LGTM run them alongside the standard queries.

Let’s take a look at an example of how one well-known open source project utilized all of these features to make use of LGTM as a platform for variant analysis.

In the middle of October 2018, Jann Horn from Google discovered a vulnerability for systemd, a core part of many Linux distributions:

systemd cve

It was discovered that systemd was vulnerable to a state injection attack when line splitting via fgets(). Since systemd is an open source project, the lead developers needed a way to warn contributors against adding features which utilized fgets(). They added a paragraph to the end of their CODING_STYLE document to do just that. However...

systemd pr

As systemd’s maintainers noted, a paragraph at the end of their CODING_STYLE document is not enough to prevent all further uses of fgets(). In order to improve the situation, the systemd team decided to add a custom QL query to their project on LGTM to catch any use of fgets():

import cpp

predicate dangerousFunction(Function function) {
  exists (string name | name = function.getQualifiedName() |
    name = "fgets")

from FunctionCall call, Function target
where call.getTarget() = target
  and dangerousFunction(target)
select call, target.getQualifiedName() + " is potentially dangerous"

This query checks to see if there are any calls to fgets(), then it displays an LGTM alert for each one explaining that these functions are potentially dangerous.

With their custom query written, the developers of systemd were able to easily track down all uses of fgets() in their codebase. First, they ran the query in LGTM’s interactive query console to check results. Then they added the query to their repository so that LGTM ran it alongside all the standard queries, allowing them to continuously monitor the calls to fgets() in the systemd codebase. We can see these alerts in action if we view src/udev/udev-rules.c in one of their commits shortly after this query was created.

systemd alerts

By utilizing LGTM as a continuous integration tool to automatically review code in pull requests before it reaches the main branch, the systemd team are able to stop other developers from accidentally reintroducing calls to fgets() into their code. That is the true power of QL and LGTM. Together, they provide continuous monitoring and scalable variant analysis for your projects, even if you don’t have your own team of dedicated security engineers.

While this query was quite simple, it proved to be extremely helpful to the systemd team. With QL, it is possible to write more advanced queries to solve significantly more challenging problems. In my next post, we will start to examine QL in greater depth as I take you through writing your own query from scratch, and also demonstrate how you can use this to modify existing queries for your own project.

Want to learn more? Continue on to part 2.

Note: Post originally published on on 02/19/2019

Join us in securing the software that runs the world!

Enter your email address below to stay up-to-date with Semmle news, security announcements and product updates.