Clang Checkers and CodeQL Queries for Detecting Untrusted Pointer Derefs and Tainted Loop Conditions

The first part of the problem is defining the taint sources. Clang Static Analyzer (CSA) provides an experimental checker alpha.security.taint.TaintPropagation for performing static taint analysis. Implemented as GenericTaintChecker, it has a set of built-in taint sources. Since the Signal data used by message handlers does not come directly from these built-in taint sources, it is necessary to find an alternative approach to define taint sources. Lucas Leong had a quick approach to work around the problem - rewrite all access to signal->theData with getenv(). Since the return value of getenv() is considered tainted by GenericTaintChecker, taint propagation works after rewrite. Refer to his blog post “MindShaRE: When MySQL Cluster Encounters Taint Analysis” for details on using existing taint checkers and CodeQL to find memory corruption bugs.

One has to be careful with this approach to avoid missing potential taint sources. Though MySQL Cluster has defined APIs like Signal::getDataPtr() to fetch the Signal data pointer, various handlers don’t follow the standard. Instead, signal->theData is accessed in numerous other ways from offset 0 or from various other offsets. I rewrote some common patterns using find and sed. This may not be exhaustive but provides sufficient taint sources to experiment with the checkers.

The situation is much different when working with CodeQL, where defining taint sources is far more flexible. All we have to do is override the isSource() predicate to something like this:

To detect this vulnerability using CSA, I relied on path-sensitive checker callback check::Location which fires every time a program accesses memory for read or write. The information below is from the checker documentation:

The SVal symbolic value Loc points to the memory region being accessed. IsLoad indicates whether the access is a read or a write. To check if a memory load is happening from a tainted memory region, we can check if Loc is tainted. If so, we can use the statement S to get the type of the expression:

Whenever the expression type is a pointer, it is logged as a bug. Scanning MySQL Cluster with this checker gave about 86 results, which is significantly high and also has false positives. Here is what the scan results look like:

The large number of results is due to the fact that any pointer derived from a tainted value (via pointer arithmetic, array indexing, etc.) is also considered tainted, irrespective of whether the tainted value is constrained by validation. In some cases, OOB reads which load pointers are also reported. Understanding the nature of false-positive results significantly improves the triage experience.

Considering the high number of results, we can sort the results by “File” which is likely to organize the result by feature, or for a less familiar code base, sorting by “Path Length” can help identify code paths reachable with minimum complexity.

Using a known bug pattern, it is possible to apply filters to reduce the results in addition to the taint check. For example, we can check the AST statements for pointer loads which are only assignment statements like above. The checker can be tweaked as per the nature of bugs in the codebase.

To perform a similar analysis in CodeQL, one can possibly rely on expression classes such as PointerDereferenceExpr, VariableAccess, FieldAccess and its subtypes. But in this case, I was curious to explore CodeQL’s Intermediate Representation (IR) to track memory loads. Since the documentation around CodeQL’s IR is limited, I used the Instruction class to dump the IR for further analysis. Here is a partial dump of IR for the line EmulatedJamBuffer * jambuf = (EmulatedJamBuffer*)req->jamBufferPtr in function execDIH_SCAN_TAB_REQ():

The CodeQL query used to dump the IR along with source code information:

Consider the below set of instructions in the IR:

Overlap defines the relationship between the definition of a memory location and its usage. The most interesting relationship for this analysis is MustExactlyOverlap - the set of bits written by the definition is identical to the set of bits read by the use, and the data type of both the definition and the use are the same. For more clarity on the overlap relationship, refer to the SSA test case found in the repository. In the case of untrusted pointer load bugs, it is very likely that there will be a mismatch of data type between definition and usage (type casting) or that the number of bits read will be a subset of the definition. Therefore, we can skip Load operations where the source value operand has an exactly overlapping relationship with its definition. The getOperandMemoryLocation() predicate provides information regarding the MemoryLocation read by a memory operand. Consider the output of the following query:

The memory operands that are marked with tilde “~” are the ones that do not have an exactly overlapping relationship. This can also be checked using isDefinitionInexact() predicate. Putting all this together, we can override the isSink() predicate to get a meaningful number of results to work with.

Many of the false-positive results were due to multiple load operations performed using some misidentified pointer. These results can be either skipped or removed by adding further constraints to the query, such as ignoring certain variable names in the sink or checking for AST patterns.

In the case of MySQL Cluster, one such constraint explored for filtering memory access to the Signal structure is VirtualVariable. As per the documentation, “Each MemoryLocation is associated with exactly one VirtualVariable. A VirtualVariable represents a set of MemoryLocations such that any two MemoryLocations that overlap have the same VirtualVariable.” VirtualVariable information can be fetched from a MemoryLocation using the getVirtualVariable() predicate.

When the variable names are consistent, we can add a constraint to consider only Load operations where the memory operand points to the signal variable. A more generic option is to fetch the type information of the virtual variable to check if it is a Signalstructure. Such a query is still restrictive (not as much variable name) but significantly reduces false positives and returns results involving jamBufferPtr:

For loop operations we are only interested in 3 AST statement classes – WhileStmtClass, DoStmtClass and ForStmtClass. Below is the loop detection code used in the checker:

So how does it matter in our analysis? Consider the below code:

Here is buffer->index is validated and the loop operation is considered safe. But the checker still reports a false positive bug.

What seems to be happening here is, the symbolic expression gets evaluated analyzer-max-loop number of times i.e., for each visit to the basic block.

The analyzer seems to evaluate that the decrement operation can underflow resulting in a value greater than 0x10000, therefore reporting it as a bug. I’m not entirely sure of the right way to solve this issue, but a quick workaround is to set analyzer-max-loop to 1. This can also be done in scan-build using the maxloop parameter. In this case, the expression is evaluated only once and it does not report the bug.

        (reg_$3<unsigned int Element{SymRegion{conj_$2{char *, LC2, S26616, #1}},0 S64b,struct index_buf}.index>) > 65536U

The scan reported around 46 bugs, with some valid ones including previously found issues like ZDI-CAN-14488, ZDI-CAN-15120, ZDI-CAN-15121.

Here is the example bug report for vulnerability in Dbdict::execLIST_TABLES_CONF():

Using the analysis done earlier for CSA, an equivalent query in CodeQL can be implemented using the Loop class. The isSink() predicate essentially looks as follows:

Building and Performing the Scan

In order to build clang with custom checkers, copy the source files to the clang/lib/StaticAnalyzer/Checkers directory in the LLVM toolchain. Then add the filenames to the CMakeLists:

Also update the clang/include/clang/StaticAnalyzer/Checkers/Checkers.td file to add the package information:

Once you make clang, the new checkers will be listed alongside other alpha checkers.

Now we can use scan-build to perform the analysis. Use the maxloop and use-analyzer configurations if necessary.

Building with checkers can be slow. To speed up the scan, limit the target path by either modifying the Makefile as necessary or use the custom Makefile by Lucas. All this analysis was performed on clang 12.0 and MySQL Cluster 8.0.25

Scanning with CodeQL requires creating a database, followed by running any queries we are interested in against the created database.