Poirot: Efficient Patch-based Auditing for Web Application Vulnerabilities

This is part of a week(-ish) blog series where I deep-dive on a cool technology. I am an investor at Dell Technologies Capital in Silicon Valley, and occasionally reminisce about my previous life in academia. Follow me on Twitter and LinkedIn.

This week, I am discussing the work of another good friend, Taesoo Kim, a professor at Georgia Tech and a very prolific researcher. In his system, Poirot, tries to solve a common problem: I have found a vulnerability in my system. Has anyone exploited it?

Let’s start with an example. Say I’m using Github, which authenticates based on an SSH public key. On March 2012, there was a publicly announced vulnerability that allowed an attacker to modify any user’s public key. In fact, an unauthorized user modified the Ruby on Rails project after modifying a developer’s public key.

Hack of Ruby on Rails project in Github

The question for a security team is who else exploited this vulnerability. Other attackers might have known about the attack for months or years and have been able to exploit it silently. Ideally, the team can detect past attacks that exploited this vulnerability.

Github’s response was to immediately block all users and ask them to audit their SSH public key. Is there a better way? Well… detecting past attacks is hard. Current tools require manual log analysis, and logs might be incomplete and/or large. There’s also too many vulnerabilities, e.g. 4,000 CVEs per year.

Their approach is to automate auditing using patches. The insight is that a security patch renders an attack harmless. The technique is to compare the execution of each request before and after a patch is applied. If execution result is the same, then there is no attack, but if the execution result is different, then it’s a potential attack!

However, the challenge is that it is necessary to audit a huge number of requests. The vulnerability might have existed for a long time, and busy web applications may have many requests. Auditing one month worth of traffic requires two months in the naive solution — two re-executions (old and new code) per request.

This work’s contribution is an efficient patch-based audit system for web apps. It is 12–51 times faster than original execution for challenging patches.

Overview of design

There are three key ideas in Poirot.

1. Control flow filtering: Auditing only affected requests
2. Function-level auditing: Sharing common code during re-execution
3. Memoized re-execution: Reusing memoized code across multiple requests

Control Flow Filtering

First, compute the basic blocks of source code.

As you can see, line 1–3 is one block. Line 4, 5, 6 are all individual blocks.

During normal execution, they log the control flow trace (CFT) of each request. Below, they show a request where the CFT is line 4 and 6.

Next is indexing. They have to compute the executed basic blocks of each request, which is line 4 and 6.

Then, there’s auditing where they compute the basic blocks modified by the patch. Let’s say that an applied patch affects line 2 as shown below.

The patch to line 2 affects the basic block containing lines 1–3. During auditing, they filter out all requests that did not execute the basic block. In the request example above (/s.php?q=test), it was not part of this basic block with the patch, so it would be filtered.

Function level auditing

There are two main optimizations.

1. Sharing common code: Share code up to the patched function.
2. Early termination: Stop after the last invocation of the patched functions

Memoized re-execution

The motivation is that many requests run similar code. Here are the main steps:

• Determine input differences among requests (template variables)
• Generate a template: efficient way to re-execute a request given an assignment of template variables
• Re-execute each request using the template

I won’t go into detail about these steps, but if you want to find more information, I refer you to his paper.

System Performance

Here are some highlights from the evaluation of the system.

Poirot can detect real attacks:

Poirot efficiently audits attacks. Here is a comparison of auditing naively (complete re-execution) vs. auditing using Poirot.

Finally, Poirot only imposes moderate runtime overhead. If you want more details on the workloads and specific details on the system evaluation, I refer you to the paper.

This is an interesting line of work that allows for the discovery of past attacks so that an organization can know the damage done by a security bug. Fast and efficient auditing remains an important part of a security program in an organization, and it’s great to see security researchers finding ways to improve it.

If you have questions, comments, future topic suggestions, or just want to say hi, please send me a note at frank.y.wang@dell.com.