When searching for vulnerability variants, the approach you take depends heavily on the scope of your analysis. While a single repository allows for more specific, detailed rules, hunting for vulnerabilities across multiple repositories requires a different strategy. This article will explore the challenges and techniques of multi-repository variant analysis, using powerful tools like CodeQL and Semgrep.
The Challenges of Multi-Repository Analysis
In a single repository, you can often write general code-scanning rules because most projects follow a consistent set of coding conventions. However, this luxury disappears when you move to a multi-repository environment. Developers use an infinite number of ways to call a function, from simple calls to complex macros and function pointers. A rule looking for a specific function name, such as REALLOC, may work in one codebase but fail completely in another.
Since a “one pattern to match them all” solution is not realistic, researchers must adjust their strategies. By scanning thousands of repositories at once, you can accept a higher rate of false negatives (missing out on potential vulnerabilities) in favor of sheer scale. Even a 1% hit rate on 1,000 repositories can yield at least 10 new vulnerabilities.
However, it is crucial to remember that this logic is not universally applicable. A rule targeting a specific misconfiguration in a particular framework will have a much smaller pool of potential targets.
Leveraging Data Flow Analysis with CodeQL
To combat a high false positive rate, a more sophisticated approach is required. Instead of relying on pure pattern matching, you can use data flow analysis and taint tracking. For this, you can turn to CodeQL’s powerful capabilities.
Fortunately, you don’t need to master CodeQL’s complex syntax from scratch. You can adapt and simplify existing standard library queries that deal with integer overflows in memory allocation sizes. Two such queries are cpp/integer-overflow-tainted and cpp/uncontrolled-allocation-size.
The following CodeQL query combines and simplifies these to find potential integer overflows:
/**
* @id integer-overflow-allocation-size
* @name Integer Overflow in Allocation Size
* @description Potential integer overflow passed to allocation size.
* @kind path-problem
* @severity error
*/
import cpp
import semmle.code.cpp.rangeanalysis.SimpleRangeAnalysis
import semmle.code.cpp.dataflow.new.TaintTracking
module IntegerOverflowConfig implements DataFlow::ConfigSig {
predicate isSource(DataFlow::Node source) {
exists(Expr e | e = source.asExpr() |
(
e instanceof UnaryArithmeticOperation or
e instanceof BinaryArithmeticOperation or
e instanceof AssignArithmeticOperation
) and
convertedExprMightOverflow(e)
)
}
predicate isSink(DataFlow::Node sink) {
exists(Expr e, HeuristicAllocationExpr alloc | e = sink.asConvertedExpr() |
e = alloc.getAChild() and
e.getUnspecifiedType() instanceof IntegralType and
not e instanceof Conversion
)
}
}
module IntegerOverflowFlow =
TaintTracking::Global;
import IntegerOverflowFlow::PathGraph
from IntegerOverflowFlow::PathNode source,
IntegerOverflowFlow::PathNode sink
where IntegerOverflowFlow::flowPath(source, sink)
select sink.getNode(), source, sink,
"Potential integer overflow $@ passed to allocation size $@.",
source.getNode(), "source",
sink, "sink"To test this rule, you can compile the Expat database with CodeQL.
- Create the database:
(This command creates a CodeQL database from thecodeql database create --language cpp --source-root expat expat-codeql-databaseexpatdirectory.) - Add the database to your VS Code workspace: Follow the steps to add the database to your CodeQL starter VS Code workspace.
- Run the query: Run the query as you would for a single-repository analysis.
This query may not return the results you expect initially, as it is designed for standard library memory allocation functions and does not follow macro invocations. To fix this, you would need to modify the isSink predicate to specifically look for macros like REALLOC.
predicate isSink(DataFlow::Node sink) {
exists(Expr e, ExprCall ec, MacroInvocation mi | e = sink.asExpr() |
ec = mi.getExpr() and
mi.getMacroName() = "REALLOC" and
e = ec.getAnArgument() and
e.getUnspecifiedType() instanceof IntegralType
)
}This modified rule will successfully find some vulnerability variants, similar to what Semgrep can find. However, for a generic, multi-repository analysis, it is important to revert the rule to the more general standard library memory allocation functions.
Scaling with Multi-Repository Variant Analysis (MRVA)
Scanning thousands of repositories is a relatively straightforward task with Semgrep, which does not require a database creation step. You can simply clone the repositories and run Semgrep directly on them.
CodeQL, on the other hand, requires a database to be built for each repository individually. This process can be challenging, as it may fail due to nonstandard build processes or third-party dependencies.
Fortunately, the CodeQL team at GitHub provides prebuilt databases of the top repositories, allowing you to scan up to 1,000 repositories through GitHub Actions. This distributed CI/CD workflow runs in the cloud and streamlines the process.
Setting up MRVA with CodeQL and GitHub
To set up multi-repository variant analysis with CodeQL and GitHub in VS Code, you can follow the official instructions in the CodeQL documentation.
When setting up your controller repository, make sure to set the workflow permissions to “Read and write permissions.” After the initial setup, return to VS Code and follow these steps:
- Click CodeQL in the Activity Bar on the left.
- Under “Variant Analysis Repositories,” select “Top 100 repositories.”
- Right-click anywhere in your custom integer overflow query and select “CodeQL: Run Variant Analysis.”
Your multi-repository variant analysis should start without any issues.
Analyzing the Results
After several minutes, you will start to receive results. The number of results will appear next to each repository name. You can expand the findings to view the data flow paths in the source code.
Even with just 100 repositories, it’s common to receive tens of thousands of results, making it infeasible to triage all of them in a limited timeframe. However, you will notice that the number of findings varies greatly; some repositories have thousands of results, while others have less than 10.
A good strategy is to begin with the repositories that have fewer findings, as they are less likely to be false positives. You can refine your rule by filtering out common validation patterns and false positives based on this initial set of results. As your rule becomes more accurate, you can move on to the larger repositories. With this scalable approach, you can successfully identify real variants of vulnerable code.
For a more focused analysis, you can also use GitHub’s custom code search to refine the list of repositories you wish to analyze. For example, if you are looking for XML-specific vulnerabilities, you can focus your analysis on repositories that use XML.
Conclusion
Automated code analysis tools offer a powerful way to analyze source code at scale. The trade-offs you make and the types of rules you write will vary depending on your strategy. Single-repository and multi-repository variant analysis require different tactics, but when used appropriately, these tools enable you to discover vulnerabilities far more efficiently with limited resources.
This article explored the use of static code analysis tools like CodeQL and Semgrep for automated variant analysis. The process involved identifying the root cause of a known vulnerability (CVE-2021-46143) and using tools to write rules that match the vulnerable patterns. We also explored how to write taint tracking and data flow queries with CodeQL to perform deeper source-to-sink matching across multiple files and how to experiment with multi-repository variant analysis to find vulnerabilities at scale.
Understanding how to translate typical vulnerable patterns in code to automated tools will lay a strong foundation for future work, such as reverse engineering binaries. Code review is similar to reading the schematics of a complex machine, while reverse engineering is about figuring out how the machine works without any schematics. Without prior knowledge of how such machines are typically designed, you would be lost. Similarly, the knowledge gained from code review is invaluable for the next steps in vulnerability research.
