Letting a vulnerability detector see how code runs
Reading code as text, a model will flag a division by zero that can never run. Concoction adds run-time information from symbolic execution on a few chosen paths, and earned 37 new CVE IDs across 20 open-source projects.
Look at this code:
static int a[] = {0, 0};
int *p = &a[1];
int b(int c) { return a[1] % c; }
if (*p)
b(0);A model that reads code as text will report a division by zero in b(), since c could be 0. But b() is only called when *p is nonzero, and *p is a[1], which is always 0. The function never runs. GCC and LLVM can’t tell either, because working out where a pointer points is hard in itself.
False positives like this are common for static methods. With redundant statements, complex data structures and countless execution paths, a model reading text can only guess conservatively.
Why not just run it?
Run the program and you see that b() is never called. The catch is that running every path is far too expensive; in real projects the number of paths explodes. Earlier work such as LIGER used execution traces, but it looks only at executed statements, so coverage is poor, and it samples traces at random, which gets costly on large projects.
How Concoction works
Concoction, our ICSE 2024 paper, takes both. The static program graph shows every behavior that is possible. Symbolic execution on a small, chosen set of paths then uses real run-time information to settle what is ambiguous.
- Static side: an enriched abstract syntax tree plus a data- and control-dependence graph.
- Path selection: an unsupervised active-learning model ranks the paths, and only the top 30% go to KLEE for symbolic execution. Functions with fewer than 10 paths run them all.
- Combining: the static and dynamic sides each get a Transformer encoder, and the two are joined to decide whether the function is vulnerable.
- Confirming: functions judged vulnerable go to AFL++ for fuzzing, to produce an input that triggers the bug.
Results
31 / 35bugs found in three projects with known CVEs
100%precision in that experiment
37new CVE IDs assigned
On three projects with known CVEs, Concoction found 31 of 35 bugs with no false positives. Given the same 12 hours, AFL++ alone found 8; fuzzing guided by Concoction found 31. We compared 16 methods in all, including 11 deep-learning models, KLEE, CodeQL and Infer. ReGVD, the static deep-learning model with the best recall, found 21.
Then we ran it on 20 open-source projects that played no part in training, including the Linux kernel, ImageMagick and assimp. We reported 54 issues. Developers confirmed 53, fixed 27, and 37 new CVE IDs were assigned. Fourteen of the issues were resolved within 48 hours.
A memory leak in ImageMagick (CVE-2021-3574) is a good example of how. In the trace, memory was allocated using samples_per_pixel and freed using MaxPixelChannels. The two didn’t match.
Limitations
Most of the cost is symbolic execution, capped at five minutes per function in deployment. Recursion, pointer aliasing and dynamically dispatched function pointers aren’t supported yet, and when an external library comes without source the trace is incomplete; that is how the four missed CVEs were missed. It handles only C for now, and it says whether a function is vulnerable, not what kind of bug it has.
Labeling the training data took four security researchers 600 hours. We keep coming back to that number: in this field, data costs more than models. The code and data are on GitHub.