Identify Memory Allocation Bugs in C
One common bug relating to heaps involves arithmetic operations performed on the parameters of memory allocation functions such as malloc(). These arithmetic operations can lead to integer overflow (and therefore less memory than desired being allocated) or compute to zero. In either instance, the condition may lead to exploitable vulnerabilities.
This article will walk you through three scenarios using Ocular to determine if such conditions exist.
Sample Program
This article will use allocation.c as an example.
#include <stdio.h>
#include <stdlib.h>
int getNumber() {
int number = atoi("8");
number = number + 10;
return number;
}
void *scenario1(int x) {
void *p = malloc(x);
return p;
}
void *scenario2(int y) {
int z = 10;
void *p = malloc(y * z);
return p;
}
void *scenario3() {
int a = getNumber();
void *p = malloc(a);
return p;
}
Analysis
First, identify the call sites of malloc in the code. There are three call sites in the sample program, and we can find them using Ocular as follows:
cpg.method.callOut.name("malloc").map(x => (x.location.filename, x.lineNumber.get)).l
List[(String, Integer)] = List(
("../../Projects/tarpitc/src/alloc/allocation.c", 23),
("../../Projects/tarpitc/src/alloc/allocation.c", 17),
("../../Projects/tarpitc/src/alloc/allocation.c", 11)
)
Looking at the atoi Case
The following query examines data flow from the return of atoi to the argument of malloc at all malloc call sites
def sink = cpg.method.callOut.name("malloc").argument
def source = cpg.method.name("atoi").methodReturn
sink.reachableBy(source).flows.p
The query returns the following:
_______________________________________________________________________________________________
| tracked | lineNumber| method | file |
|==============================================================================================|
| ret | N/A | atoi | N/A |
| atoi("8") | 5 | getNumber | ../../Projects/tarpitc/src/alloc/allocation.c|
| p2 | N/A | <operator>.assignment| N/A |
| p1 | N/A | <operator>.assignment| N/A |
| number | 5 | getNumber | ../../Projects/tarpitc/src/alloc/allocation.c|
| number | 6 | getNumber | ../../Projects/tarpitc/src/alloc/allocation.c|
| p1 | N/A | <operator>.addition | N/A |
| ret | N/A | <operator>.addition | N/A |
| number + 10| 6 | getNumber | ../../Projects/tarpitc/src/alloc/allocation.c|
| p2 | N/A | <operator>.assignment| N/A |
| p1 | N/A | <operator>.assignment| N/A |
| number | 6 | getNumber | ../../Projects/tarpitc/src/alloc/allocation.c|
| number | 7 | getNumber | ../../Projects/tarpitc/src/alloc/allocation.c|
| ret | 4 | getNumber | ../../Projects/tarpitc/src/alloc/allocation.c|
| getNumber()| 23 | scenario3 | ../../Projects/tarpitc/src/alloc/allocation.c|
| p2 | N/A | <operator>.assignment| N/A |
| p1 | N/A | <operator>.assignment| N/A |
| a | 23 | scenario3 | ../../Projects/tarpitc/src/alloc/allocation.c|
| a | 24 | scenario3 | ../../Projects/tarpitc/src/alloc/allocation.c|
You can check to see if the data flow passed through arithmetic operations using the following query:
sink.reachableBy(source).flows.passes(".*(multiplication|addition).*").p
If the condition is true, the query will return the same flow as the previous query you ran.
Verifying Arithmetic Operations
The following query looks for a parameter of some function to an argument of malloc (at all malloc call sites) that pass through an arithmetic operation:
def sink = cpg.method.callOut.name("malloc").argument
def source = cpg.method.name(".*scenario.*").parameter
sink.reachableBy(source).flows.passes(".*multiplication.*").p
The query returns the following:
_______________________________________________________________________________________________
| tracked| lineNumber| method | file |
|==============================================================================================|
| y | 15 | scenario2 | ../../Projects/tarpitc/src/alloc/allocation.c|
| y | 17 | scenario2 | ../../Projects/tarpitc/src/alloc/allocation.c|
| p1 | N/A | <operator>.multiplication| N/A |
| ret | N/A | <operator>.multiplication| N/A |
| y * z | 17 | scenario2 | ../../Projects/tarpitc/src/alloc/allocation.c|
If you want to generalize the source and examine all parameters for all functions, use:
def source = cpg.method.parameter
Generalizing the Query using Filters
This query defines a source by:
- Examining all call sites of all methods
- Filtering out the methods with malloc (sink of interest) and any arithmetic operation
- Making the source a return (
methodReturn) of the call sites' methods (atoiandgetnumber) - Finding data flow from the methods to the malloc call site argument as a sink
def sink = cpg.method.callOut.name("malloc").argument
def source = cpg.method.callOut.nameNot(".*(<operator>|malloc).*").calledMethod.methodReturn
sink.reachableBy(source).flows.p
The query returns the following:
_______________________________________________________________________________________________
| tracked | lineNumber| method | file |
|==============================================================================================|
| ret | N/A | atoi | N/A |
| atoi("8") | 5 | getNumber | ../../Projects/tarpitc/src/alloc/allocation.c|
| p2 | N/A | <operator>.assignment| N/A |
| p1 | N/A | <operator>.assignment| N/A |
| number | 5 | getNumber | ../../Projects/tarpitc/src/alloc/allocation.c|
| number | 6 | getNumber | ../../Projects/tarpitc/src/alloc/allocation.c|
| p1 | N/A | <operator>.addition | N/A |
| ret | N/A | <operator>.addition | N/A |
| number + 10| 6 | getNumber | ../../Projects/tarpitc/src/alloc/allocation.c|
| p2 | N/A | <operator>.assignment| N/A |
| p1 | N/A | <operator>.assignment| N/A |
| number | 6 | getNumber | ../../Projects/tarpitc/src/alloc/allocation.c|
| number | 7 | getNumber | ../../Projects/tarpitc/src/alloc/allocation.c|
| ret | 4 | getNumber | ../../Projects/tarpitc/src/alloc/allocation.c|
| getNumber()| 22 | scenario3 | ../../Projects/tarpitc/src/alloc/allocation.c|
| p2 | N/A | <operator>.assignment| N/A |
| p1 | N/A | <operator>.assignment| N/A |
| a | 22 | scenario3 | ../../Projects/tarpitc/src/alloc/allocation.c|
| a | 23 | scenario3 | ../../Projects/tarpitc/src/alloc/allocation.c|
_______________________________________________________________________________________________
| tracked | lineNumber| method | file |
|==============================================================================================|
| ret | 4 | getNumber | ../../Projects/tarpitc/src/alloc/allocation.c|
| getNumber()| 22 | scenario3 | ../../Projects/tarpitc/src/alloc/allocation.c|
| p2 | N/A | <operator>.assignment| N/A |
| p1 | N/A | <operator>.assignment| N/A |
| a | 22 | scenario3 | ../../Projects/tarpitc/src/alloc/allocation.c|
| a | 23 | scenario3 | ../../Projects/tarpitc/src/alloc/allocation.c|
To further filter the results, you can use passes and passesNot to check if operations were performed on the malloc argument.
Advanced Control Flow Graph Analysis
You can use the following query to examine a specific malloc call site, then looking at the Control Flow Graph, listing expressions, line numbers, etc. to reach the source.
This action is typically performed ad hoc to reach the source variable by listing code expressions during a backward trace.
The following example is a follow-up to the first query you ran in this article, where the second-to-last row of the results table indicated that line 23 was of interest.
cpg.method.callOut.name("malloc").filter(_.lineNumber(23)).repeat(_.cfgPrev)(_.emitAllButFirst).map( x=> (x.code, x.location.filename, x.lineNumber.get)).l
result: List[(String, String, Integer)] = List(
("a", "alloc/allocation.c", 23),
("p", "alloc/allocation.c", 23),
("a = getNumber()", "alloc/allocation.c", 22),
("getNumber()", "alloc/allocation.c", 22),
("a", "alloc/allocation.c", 22)
)