The PostgresChecker: Hunting Use-after-free Bugs in PostgreSQL (3)
[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 two blog posts we looked at pitfalls of the C programming language in general and the PostgreSQL API in particular. Then we highlighted static analysis tools that can help mitigate these problems. In this blog post we are going to discuss how we can extract information from the PostgreSQL codebase using the tool Coccinelle, and we are also going to look at some PostgreSQL internals. So settle in and let’s start.
Finding Memory-Managing Functions with Coccinelle
If we are going to implement a checker that is able to detect use-after-frees in code using the PostgreSQL API, we first need to identify all the functions that might potentially free memory. As we have seen in the last blog post, Coccinelle is an excellent tool for detecting patterns in C code.
Here is a semantic patch that finds functions that free a passed parameter in any capacity:
In the header we define identifiers and types as placeholders for both the function and parameter to be matched. The position records information about the found match, such as file name, line, column, etc.
The body itself resembles actual C code. We define a function using the placeholders we defined above and use some Coccinelle-specific notation: the ellipsis (…, lines 6-9) stand for any amount of code, and the diamond brackets with a plus (<+…+>, lines 7-9) stand for one or more occurrences (similar to notation in regular expressions).
This means that this patch will match every function that has any call to free on a passed parameter inside. The bottom part defines a Python script where we pass information we want to print out for the found matches, including the function name and the position.
Examples
Here are two examples that are matched by the template:
Both examples have calls to free. However, we can already see that they follow different patterns: example one frees the passed parameter unconditionally, and the second one only does so if it is not null (which should have been checked in the first example anyway). We will discuss different categories of functions in the next section.
The following two functions are not matched by our patch:
The first one returns before the free occurs, and the second one does not free a passed parameter.
Iterating over the Codebase
After finding a set of functions using the Coccinelle path, the idea is to take all the found matches and recursively find all functions calling those matches. For example, our first trip through the codebase finds the function pfree: the PostgreSQL equivalent of free. In our next trip we search for all functions that call pfree on a parameter, and continue with all new matches until no new functions can be found.
For that, of course, we need to create a patch template. So our example from before might look more like this:
Now we can replace __FUNCTION__ with any function name we like when we iterate. With a little Bash magic we can automate the process and get all interesting functions from the PostgreSQL codebase.
In the next section we will discuss different categories of functions the PostgresChecker was able to identify when looking at the PostgreSQL source code.
Categories of Functions
Category 1: Strict Functions
These are functions that unconditionally free a passed parameter. We have seen an example of this category in our first blog post:
The parameter stmt will always be freed when calling this function. Therefore, it strictly behaves like a standard free.
Note: In PostgreSQL version 18 this function has been refactored and no longer includes the call to free.
Here is what a basic template for this category would look like:
The template ensures that the freeing or reallocating function call occurs along all execution paths. In Coccinelle this is achieved using the forall keyword in line 1. Additionally, the template excludes functions where a return statement might occur before the relevant function call. The when condition in line 8 excludes all matches where a return occurs before the function call. The code from line 10 onwards allows for zero or more further occurrences.
This excludes edge cases like functions returning after a check for NULL. Anyone interested can find the bachelor’s thesis introducing the PostgresChecker, with the full templates, at [1].
For these functions the PostgresChecker should always report use-after-frees when the passed parameter is used again after the function call.
Category 2: Dependent Functions
These functions may modify the passed parameter, but only under certain conditions. Often the free depends on another parameter passed to the function call. The following function from execTuples.c exemplifies this:
The parameter mtup is only freed if shouldFree is set to true. Our checker should be able to distinguish the two cases and only warn users if the flag is set.
A Coccinelle template might look like this:
Note: The keyword exists here is not entirely correct, since it does not guarantee that the parameter is freed on any path. In practice, however, the free occurs on the main branch of the function most of the time. Furthermore, these functions need to be reviewed manually anyway, as we will discuss in the next blog post in this series.
The call to the freeing function depends on the parameter b in line 9. Again, this does not cover edge cases. For the complete templates, see [1].
For these functions the PostgresChecker should report use-after-frees dependent on the flag.
Category 3: Arbitrary Functions
This category includes all remaining functions. They may free or reallocate the passed parameter, but the conditions under which this happens cannot be determined statically.
Here is an example from the PostgreSQL codebase:
A path in this context refers to an execution plan. The function add_path adds a new path to a relation only if it is better than the existing paths already known by the relation. Otherwise, the new path is freed. Since this decision is based on runtime data, the behavior is unpredictable for a static analyzer, and such functions are therefore referred to as arbitrary.
The PostgresChecker should therefore report a potential use-after-free in this case.
Category 4: Functions to Reassign
These functions can be identified by their usage pattern rather than their freeing behavior. They might free a passed parameter internally but always return a pointer that should be assigned and used instead. Here is an example from list.c:
The function takes a pointer to a list and deletes the nth element of that list. If the list becomes empty, it is freed and NIL is returned (representing an empty list in PostgreSQL); otherwise, the modified list is returned.
As long as we reassign the returned pointer to list, it does not matter whether a free occurred inside the function call.
To retrieve these functions, we can simply use the previously aggregated functions and filter them for matching return types and parameter types. The resulting function set can then be manually inspected.
The PostgresChecker should reflect the incorrect usage pattern in the message presented to the user. The use-after-free here is only a symptom of bad coding patterns.
Category 5: Functions Returning Boolean
A single function called ecpg_check_PQresult represents the last category: it always returns false if the passed parameter is freed, and true otherwise. In this case, correct usage requires the caller to check the return value and set the variable to NULL if false is returned, representing a clear usage pattern as well.
Similar to Category 4, developers should be warned if the return value is ignored.
In the next post in this series we are going to discuss how a static checker for the PostgreSQL API with custom messages for these categories can be implemented using the Clang Static Analyzer Framework.
