In the first blog of the series, we saw how CodeQL and Clang checkers can be used to find bugs in MySQL Cluster involving untrusted size arguments leading to buffer overflow or out-of-bound array accesses. Though the majority of bugs were out-of-bounds array accesses, there were also bugs involving untrusted data being used in loop conditions or casted to pointers. In this final blog of the series, we experiment with CodeQL’s IR and Clang checkers for detecting such bug classes.

Defining taint sources - CSA vs CodeQL

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:

CWE-822: Untrusted Pointer Dereference

In an untrusted pointer deference vulnerability, data from an untrusted source is casted to a pointer for further use. The impact of the bug depends on the usage of the casted pointer. This section provides details about detecting such pointer load operation using CSA and CodeQL.

Detecting untrusted pointer dereference using CSA

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.

scan-view results sorted by File

scan-view results sorted by Path Length

CSA reported a number of bugs in the code handling DBDIH block with a path length of 1. Here is an example bug report:

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.

Analyzing memory loads using CodeQL IR

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:

Here the LoadInstruction relies on 2 operands - a source address operand (r17303_4) and a source value operand (m17300_12). The source value operand is a MemoryOperand. The MemoryOperand describes the memory address accessed by the instruction, whose value gets copied to the result register (r17303_5). Moreover, the result is also associated with type information. The idea was to filter all tainted memory load operations whose return type is a pointer. However, such a query resulted in an unusably large number of results.

Adding constraints using overlap relationship and virtual variables

Consulting CodeQL’s IR SSA Construction documentation, I found a couple of features that could be useful for refining the query: the overlap relationship and VirtualVariables.

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:

CWE-606: Unchecked Input for Loop Condition

In CWE-606: Unchecked Input for Loop Condition, values from an untrusted source are used for loop termination conditions. This may lead to a DoS or other issues depending on the operations done in the loop body. This section provides details about detecting such tainted loop conditions using CSA and CodeQL.

Detecting tainted loop condition using CSA

Unlike tainted memory loads, I couldn’t find any path-sensitive callback to trigger on loop conditions. Moreover, AST-based matchers without path-sensitivity are not useful in this case. Therefore, I relied on the check::BranchCondition callback which fires every time a control flow branching occurs during analysis. The following information is from the checker documentation:

The idea here is, whenever the callback triggers due to a conditional statement, walk up the AST using ParentMap and check for a loop statement. Here is what an example AST looks like for while loop:

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:

Once we know that the condition statement triggering the callback is part of a loop statement, we can check if it is tainted. Specifically, I wanted to look for some common code patterns involving induction variables compared against untrusted values, or untrusted values used as induction variables to decide on loop termination. Consider a couple of common code patterns below that involve explicit binary comparison operations:

•      The induction variable is compared against a potentially untrusted value. For example, RHS could be tainted and LHS is not.
•      The induction variable could be potentially untrusted. Here LHS value is compared against constant 0 on RHS.

 The checker specifically looks for these cases to make decisions on bugs. When RHS is constant 0, check if LHS is tainted. Otherwise, check if RHS is tainted:

Another common code pattern is unary operations in loop statements, especially while and do while loops:

No special breakdown is necessary in case of unary operations in the way we handled binary operations. However, in certain cases, implicit Boolean conversions result in implicit conditional statements received by the check::BranchCondition callback. Here is what the AST looks like:

To handle these, if any non-binary conditional operations have a Boolean outcome, it is possibly due to implicit casting and hence we get the sub-expression associated with the expression.

Evaluating constraints on tainted variables

While it is possible to know if an input is tainted or not, there is no way to know if the tainted input value is constrained by some validation. Without this information, the checker is going to generate a lot of false-positive results. To solve this problem, I used the solution provided by Andrew Ruef in the blog post Trail of Bits - Using Static Analysis and Clang to Find Heartbleed. Since Signal data is treated as an unsigned 32-bit integer in most cases, I queried if the variable can take a value greater than 0x10000. If yes, consider the variable as unconstrained and log the bug.

Configuring analyzer-max-loop in CSA

Clang analyzer has a configuration parameter to choose the number of times a basic block in a loop gets executed. By default, this value is 4.

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():

Detecting tainted loop condition using CodeQL

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.