The PostgresChecker: Hunting Use-after-free Bugs in PostgreSQL (4)

[1] Use-after-free – Problem Description
[2] Static Program Analysis – Approaches to Handle Use-after-frees
[3] Analyzing PostgreSQL – Extracting Information from the Codebase
[4] Implementing a Custom Static Analysis Tool – The PostgresChecker
[5] Applying the Checker – Finding Bugs in PostgreSQL
[6] Conclusio – Lessons Learned

In this blog series I am going to present the PostgresChecker: a static analysis tool that is able to detect use-after-free bugs in source code using the PostgreSQL API.

In the last blog posts we looked at pitfalls of the C programming language in the context of the PostgreSQL API, highlighted static analysis tools that can help mitigate these problems, and showed how to extract useful information about memory-handling functions from a codebase (such as PostgreSQL) using the tool Coccinelle. In this blog post we are going to look at how to actually implement a static checker with this information using the Clang Static Analysis Framework. So grab your favorite PostgreSQL functions and let’s get to it.

The Clang Static Analysis Framework

Clang is part of the LLVM project, which itself is a set of tools for building compilers and toolchains. In this ecosystem, Clang serves as the frontend for the LLVM compiler. As such it represents a full-fledged compiler, being able to do everything from parsing the source code to translating it to machine code. In this process we are able to jump in and perform some checks.

More precisely, the C program is parsed and syntactically analyzed. The code is then represented using a so-called Abstract Syntax Tree (AST).

Consider the following piece of code:

This might be represented by the compiler with a tree like this:

In the same manner, functions are represented by nodes in the AST.

The Clang Static Analyzer, however, does more than walk this tree. It symbolically executes the program: it explores the possible execution paths through the code and maintains a separate program state for each path, tracking symbolic values for variables and memory. A checker hooks into this process and gets notified at interesting points, for example, right before a function call is evaluated on a given path. This path-sensitivity is very useful and we will rely on it later.

Helper Classes in the Framework

The Clang Static Analysis Framework provides a list of helpful classes to interact with the AST and the analysis (see also [1]):

• ASTContext: holds the AST nodes.
• ProgramState: stores the program environment on the current execution path, including memory regions.
• FunctionDecl: represents a function declaration or definition.
• CallEvent: abstracts a function call and stores information like the program state and location context.
• MemRegion: abstraction used to represent memory regions.

This gives developers the means to access nearly all data processed by the compiler. So-called checks can be used to query the elements described above. The checks used by a checker are declared via the class template (see for example [2]):

Available options include PreCall, PostCall, and DeadSymbols. These checks can then be used in the checker by implementing callbacks following the pattern checkCheckName [3]. For example, checkPreCall is triggered before a function call is evaluated on a path and provides access to the CallEvent and the FunctionDecl.

Implementing a Checker

To implement the PostgresChecker we need two maps: a function catalog to reference the functions we found with Coccinelle, discussed in the last blog post, and a memory map to keep track of freed memory:

In our function catalog the function name is mapped to the position of the parameter that is freed (starting from 0 for the first argument).

Consider the following code:

In the first line we create a Bitmapset: an internal data structure where bits represent the members of a set. Reading the bits right to left starting at 0, the bitmap 010010 represents a set where the numbers 1 and 4 are members. In our code example, bms_make_singleton(5) allocates a new Bitmapset and adds 5 as the initial member (i.e., 100000). The address of the allocated memory in our example is 0x42 and is stored in the pointer bms.

(A quick disclaimer: a static analyzer never sees real runtime addresses. Internally, the checker tracks symbolic memory regions. The concrete address 0x42 is only used here to make the illustrations easier to follow.)

A few lines later the pointer is used:

It is passed to the function bms_is_member, which checks whether a certain number is a member of a given set. Our checker now needs to look up the function in the function catalog. The catalog returns nothing, so the pointer is not freed. The memory map is also empty, so we simply continue.

On the next line bms_free is called on bms:

We look into the function catalog again and find bms_free. We check the position of the freed parameter, with 0 representing the first argument. So we know that our pointer will be freed and we go ahead and save the address in our memory map:

Along with it we record additional information like the function and variable names. Additionally, we create a new program state so that we can track frees on different execution paths.

Now that we have processed the function call, we can continue in the code.

On the very next line bms_free is called on bms again:

We find the function in the function catalog again and confirm that the argument used is really freed. This time, however, we also find an entry for address 0x42 in our memory map: the memory has already been freed before, a classic double free. We inform the developer with a warning like this:

Note that the same mechanism catches genuine use-after-frees, not just double frees. Suppose that after the free the code called bms_is_member(bms, 7). Our checkPreCall callback fires, the function catalog lookup comes back empty, bms_is_member does not free anything, but the memory map already contains an entry for 0x42. A freed pointer is being passed to a function, so we report a use-after-free instead of a double free. The only difference between the two cases is whether the called function is itself a freeing function.

This is only the crude logic that drives the PostgresChecker. For the actual implementation with all its details, feel free to check out [4].

Handling Categories

As discussed in the last blog post, we found five categories of memory-handling functions in the PostgreSQL codebase:

• Strict Functions: always free the parameter.
• Dependent Functions: free the parameter depending on the value of another parameter.
• Arbitrary Functions: may or may not free the parameter, and we cannot tell from the outside.
• Functions to Reassign: return a (possibly new) pointer that must be reassigned, invalidating the old one.
• Functions Returning Boolean: return whether the parameter was actually freed.

The PostgresChecker needs to handle the given categories accordingly.

The first three categories are fairly easy to implement. We just need to set up different maps for the different categories. In case a strict function frees the parameter, we tell the user „Watch out, the parameter has been freed“; in case an arbitrary function frees the parameter, we tell the user „Watch out, the parameter MIGHT have been freed“.

Where it gets tricky is when it comes to Dependent Functions. Remember the function from our last blog post:

Whether mtup is freed depends on the parameter shouldFree. However, this value is not available in the AST at compile time. You would need to analyze the control flow of the program and derive the value.

This is precisely where the symbolic execution described above pays off. The analyzer exposes symbolic values via the class SVal: a symbolic expression that can be evaluated against the current program state. With this we can actually check the value of shouldFree on the current path: if it is true we warn the developer; if it is false we don’t. And if the value cannot be determined on the current path, we simply treat the function call as an arbitrary free.

For the last two categories we implement two additional maps and adjust the warning message accordingly. However, we can also explicitly check whether the return value was actually used: a call to a Function to Reassign whose result is discarded, or a Function Returning Boolean whose result is ignored, is suspicious in itself. For an implementation of this using Clang-Tidy see [5].

 What’s Next

We now have a checker that knows PostgreSQL’s memory-handling functions, tracks freed memory across execution paths, and handles all five function categories. In the next blog post we will unleash it on the PostgreSQL codebase itself and see what it finds.

[1] https://clang-analyzer.llvm.org/checker_dev_manual.html
[2] https://github.com/llvm/llvm-project/blob/2cb32e29408a6c598072ea0f066a246957be69f9/clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp#L343
[3] https://github.com/llvm/llvm-project/blob/2cb32e29408a6c598072ea0f066a246957be69f9/clang/lib/StaticAnalyzer/Checkers/MallocChecker.cpp#L3120
[4] https://github.com/berndreiss/pg_ladybug/tree/fa080c4ab39b71fec5db44299b45edee2dc2e11c/src/staticAnalyzer
[5] https://github.com/timescale/pg_ladybug/blob/3a50bfd767a3e0dad61b0bd7a6bd9542d2a4ae6e/src/postgres/PostgresCheck.cpp