Offensive Security Researcher & Quantum Cryptography Analyst

Semgrep: Pattern-Oriented Powerhouse for Code Analysis

Abdul Wahab Junaid
Semgrep: Pattern-Oriented Powerhouse for Code Analysis

In the realm of code analysis, tools like Semgrep and CodeQL stand out as essential for identifying vulnerabilities and ensuring code quality. While both serve a similar purpose, their underlying philosophies and approaches to code analysis differ significantly. This article delves into Semgrep, exploring its pattern-oriented rule syntax, unique capabilities, and ideal use cases, especially in contrast to CodeQL’s query-oriented paradigm.

The Genesis of Semgrep: A Static Analysis Journey

To truly appreciate Semgrep’s design, it’s worth understanding its origins. The insightful blog post “Semgrep: A Static Analysis Journey” by Yoann Padioleau, the author of Semgrep’s predecessor, sgrep, offers a fascinating glimpse into its development. You can read more about this journey on the official Semgrep blog.

Unpacking Semgrep Rules: A Deeper Look

Let’s examine a practical example to understand Semgrep’s rule syntax. Consider the express-injection.yml rule designed to detect a command injection vulnerability, similar to what a CodeQL query might identify:

YAML
rules:
  - id: express-injection              # Unique ID for the rule
    mode: taint                        # Enables taint tracking (dataflow from source to sink)
    
    pattern-sources:
      - pattern: req.query.$PARAMETER  # Source: any user input from query params (e.g., req.query.ip)

    pattern-sinks:
      - pattern: execSync(...)         # Sink: usage of execSync with tainted input

    message: >
      Passing user-controlled Express query parameter to a command injection.
      # Message shown when the rule matches

    languages:
      - javascript                     # Language the rule applies to

    severity: ERROR                    # Severity level shown in report

    metadata:
      interfile: true                  # Enables tracking across function boundaries and files

While a deep dive into every nuance of Semgrep rule syntax isn’t necessary for all users, understanding its core components is crucial for effective use:

Combining Metavariables and Ellipsis for Targeted Matches

Metavariables and ellipsis operators are frequently used in conjunction to create highly effective patterns. For example, imagine you need to identify hardcoded secrets in code where variables are prefixed with SECRET_, such as:

JavaScript

JavaScript
var SECRET_KEY = "D3ADB33F"
var SECRET_TOKEN = "1337"

You’re not interested in the exact values of the strings, as they can vary. The following Semgrep pattern effectively achieves this:

YAML
patterns:
  - pattern: var $VARIABLE_NAME = "..."
  - metavariable-regex:
      metavariable: $VARIABLE_NAME
      regex: SECRET_.*

Composing Semgrep Patterns: AND and OR Operations

Semgrep offers flexible ways to combine patterns:

Semgrep vs. CodeQL: A Tale of Two Approaches

As previously mentioned, a fundamental distinction between Semgrep and CodeQL lies in their syntax and underlying philosophy:

Source Code Representation and Data Flow Analysis

Another key differentiator lies in how Semgrep and CodeQL represent source code for data flow analysis:

The Trade-Offs: Depth vs. Speed

While Semgrep’s generic AST approach offers language flexibility, it comes with certain trade-offs in terms of program analysis data:

Semgrep Pro: Bridging the Gaps

To address the limitations of the open-source Semgrep engine, its developers created Semgrep Pro. This paid offering enhances the analysis capabilities by adding support for:

You can experience these advanced features through the Semgrep Playground, a web-based environment where you can test Semgrep rules against code snippets.

Hands-on with Semgrep Pro in the Playground:

  1. Navigate to the Semgrep Playground.
  2. Switch to the “advanced” tab.
  3. Paste the express-injection.yml rule (from the beginning of this section) into the rule editor.
  4. In the test code editor on the right, paste the contents of utils.js and index.js one after another.
  5. Crucially, ensure the “Pro” toggle at the top right is switched on.
  6. Click “Run.” You should observe the highlighted pattern match at execSync(\ping -c 5 ${ip}`)`, confirming the vulnerability detection.

While the Playground offers a taste of Semgrep Pro’s power, a subscription is required for analyzing larger codebases. For multi-file analysis within a local environment without a Pro subscription, the open-source Semgrep (Semgrep OSS) remains a viable option.

Working with Semgrep OSS: Local Setup and Capabilities

For situations involving multiple files in a large codebase where a Semgrep Pro subscription isn’t utilized, Semgrep OSS (the base engine) is the tool of choice. You can easily install it using the pip Python package manager:

Bash

Bash
pip install semgrep

Semgrep OSS, as detailed in its official documentation (see Semgrep Data Flow Overview), provides several analyses, including:

It’s important to note that Semgrep OSS primarily performs intraprocedural analysis, meaning it analyzes data flow within a single function or method. It also incorporates design trade-offs that prioritize speed over absolute comprehensiveness, such as limited taint analysis for data passed through pointers.

Semgrep’s Speed Advantage and Ideal Use Cases

Due to its fundamental design choices at the program analysis level, Semgrep OSS boasts significantly faster execution times and less overhead compared to CodeQL. With Semgrep, you don’t need to meticulously worry about selecting the correct class or type when writing a rule. Furthermore, the absence of a database build or query compilation step allows for much faster iteration cycles.

This makes Semgrep particularly well-suited for specific vulnerability research scenarios, especially when:

In the fast-paced world of vulnerability research, efficient allocation of time and resources is paramount. Knowing which tool is best suited for a particular target is a critical skill for achieving impactful results with a reasonable investment. Semgrep, with its speed and pattern-oriented approach, offers a compelling solution for many such challenges.

The Power of Variant Analysis in Vulnerability Research

The landscape of vulnerability research has evolved dramatically. As software developers implement robust system-level mitigations and write more secure code, discovering impactful vulnerabilities in popular software has become a significantly more challenging endeavor. The days of the “Wild West” are largely behind us. Consider large open-source applications like LibreOffice, which can easily encompass millions of lines of code. While automated source code analysis tools offer a lifeline by reducing the sheer volume of code to analyze, the human element of triaging results and understanding the context of each finding remains indispensable. For instance, an seemingly unsafe memcpy operation in one file might have been entirely mitigated by a preceding size check elsewhere in the codebase. The challenge lies in striking a delicate balance: tweaking analysis rules to reduce false positives risks an increase in false negatives, potentially causing critical vulnerabilities to be missed.

Fortunately, vulnerability researchers are not alone on this path. While not all researchers publish every minute detail of their discoveries, open-source software provides two invaluable pieces of evidence for the astute investigator: the patched code diff and the public vulnerability advisory, commonly published as a Common Vulnerabilities and Exposures (CVE) record. By meticulously analyzing these sources, you can leverage past vulnerabilities to uncover a multitude of new ones. This section will explore the methodology of variant analysis, both within a single codebase (or repository) and across multiple repositories.

Single-Repository Variant Analysis: Uncovering the Echoes of Mistakes Past

Vulnerabilities rarely exist in isolation. If a developer introduced a mistake in their code that led to a vulnerability, there’s a high probability that similar errors, or variants, exist elsewhere within the same codebase. Furthermore, vulnerability researchers might not always aim to enumerate every conceivable variant of a vulnerability; sometimes, focusing on a particular exploit path and content with finding something is the more efficient approach. A critical factor contributing to the prevalence of variants is that developers, in their haste to patch a specific bug, may fail to conduct a deeper root cause analysis to understand why the vulnerability occurred. This oversight can lead to a failure in implementing secure guardrails to prevent future occurrences. These factors combine to create a surprisingly rich source of vulnerabilities and enable a less resource-intensive approach to vulnerability research.

Key avenues to pursue in single-repository variant analysis include:

Thanks to the public vulnerability advisory (CVE) and the patch code diff, you gain precise insights into how and why the original vulnerability manifested. With some dedicated root cause analysis, you can quickly pivot to scanning the codebase for similar vulnerable patterns. This approach allows you to triage results by whether they repeat the original vulnerability, rather than starting your analysis from scratch each time. Crucially, the rules you develop for this type of analysis can be significantly more specific to the particular vulnerable patterns, making them highly effective where a general ruleset might fall short.

Case Study: Integer Overflow Variants in Expat

Let’s put this methodology into practice with a concrete example: a collection of integer overflow vulnerability variants found in Expat, a widely used C library for parsing XML files. Given the pervasive nature of XML files, Expat finds applications in countless other software, including popular browsers like Firefox and programming languages like Python. This ubiquity means that a vulnerability in Expat can have significant downstream impact, especially since the library might be used in ways the original developers did not anticipate.

A quick glance at the CVEs for Expat reveals a history of multiple integer overflow vulnerabilities. Specifically, a series of related vulnerabilities, CVE-2022-22822 through CVE-2022-22827, highlight this recurring pattern. If you navigate to the individual CVE pages for any of these vulnerabilities on the CVE website, you’ll find a link under the “References” section pointing to the merged commit on GitHub that patched the vulnerability.

For the shared patch encompassing CVE-2022-22822 through CVE-2022-22827, titled “[CVE-2022-22822 to CVE-2022-22827] lib: Prevent more integer overflows,” the associated pull request comment indicates that this patch is related to earlier pull requests 534 and 538. These earlier pull requests, in turn, addressed previous integer overflows identified as CVE-2021-46143 and CVE-2021-45960. This interconnected web of vulnerabilities clearly demonstrates how variant analysis can trace a lineage of similar flaws within a single project, allowing researchers to efficiently uncover related weaknesses.

A Root Cause Analysis of Expat’s Integer Overflows

To truly master single-repository variant analysis, let’s embark on a practical exercise: rediscovering the family of integer overflow vulnerabilities, specifically CVE-2022-22822 through CVE-2022-22827, in the Expat library. Our strategy will be to craft a code analysis rule based on a prior vulnerability, CVE-2021-46143. The foundational step in this process, and indeed in writing any effective code analysis rule, is conducting a thorough root cause analysis. This involves meticulously understanding how a vulnerability occurs and, consequently, pinpointing the precise patterns to target with our rule.

Tracing the Roots: CVE-2021-46143 in Expat

Our journey begins by examining the patch for CVE-2021-46143 on GitHub. The pull request itself is helpfully titled “[CVE-2021-46143] lib: Prevent integer overflow on m_groupSize in function doProlog.” Upon reviewing the “Files changed” section, we observe that only two files were updated. The accompanying changelog entries provide crucial initial clues:

Bash
+ #532 #538 CVE-2021-46143 (ZDI-CAN-16157) -- Fix integer overflow
+ on variable m_groupSize in function doProlog leading
+ to realloc acting as free.
+ Impact is denial of service or more.

This changelog entry is incredibly informative. It directly tells us that the integer overflow in CVE-2021-46143 leads to a critical condition: “realloc acting as free.”

The realloc Mystery: From Reallocation to Deallocation

To understand “realloc acting as free,” we need to revisit the standard C library function realloc. This function takes two arguments: void *ptr (a pointer to previously allocated memory) and size_t size (the new desired size for the allocated memory). As detailed in its manual page, realloc attempts to resize the memory block pointed to by ptr to size. However, a crucial detail is that if size is zero, realloc behaves identically to free, deallocating the memory pointed to by ptr. This is a critical piece of information for our root cause analysis.

Dissecting the Patch: expat/lib/xmlparse.c

Further insights can be gleaned from the diff of the other updated file, expat/lib/xmlparse.c. The patch introduces specific changes to prevent this integer overflow:

C
@@ -5019,6 +5046,11 @@ doProlog
 if (parser->m_prologState.level >= parser->m_groupSize) {
     if (parser->m_groupSize) {
         {
+            /* Detect and prevent integer overflow */
+            if (parser->m_groupSize > (unsigned int)(-1) / 2u) {
+                return XML_ERROR_NO_MEMORY;
+            }
+
             char *const new_connector = (char *)REALLOC(
                 parser, parser->m_groupConnector, parser->m_groupSize *= 2);
             if (new_connector == NULL) {
@@ -5029,6 +5061,16 @@ doProlog
     }
 }
 if (dtd->scaffIndex) {
+
+
+
+    /* Detect and prevent integer overflow.
+     * The preprocessor guard addresses the "always false" warning
+     * from -Wtype-limits on x86_64, where sizeof(unsigned int) 
+#if UINT_MAX >= SIZE_MAX
+
+#endif
+
+    if (parser->m_groupSize > (size_t)(-1) / sizeof(int)) {
+        return XML_ERROR_NO_MEMORY;
+    }
+
     int *const new_scaff_index = (int *)REALLOC(
         parser, dtd->scaffIndex, parser->m_groupSize * sizeof(int));
     if (new_scaff_index == NULL)

This diff precisely highlights where the patch occurs and, more importantly, what it patches. The key additions are two comparison checks on parser->m_groupSize. These checks ensure that parser->m_groupSize does not exceed specific boundary values: (unsigned int)(-1) / 2u or (size_t)(-1) / sizeof(int). These are the values by which parser->m_groupSize is multiplied before being passed as the size argument to the REALLOC macro.

Demystifying the REALLOC Macro

Before proceeding, let’s take a moment to understand the REALLOC macro. In the C programming language, macros are essentially named fragments of code that undergo text substitution during the preprocessing phase. To uncover its definition, we search for #define REALLOC within the Expat source code:

C
#define REALLOC(parser, p, s) (parser->m_mem.realloc_fcn((p), (s)))

During compilation, the C preprocessor will replace every instance of REALLOC and its arguments with (parser->m_mem.realloc_fcn((p), (s))). However, this substitution alone doesn’t definitively confirm whether m_mem.realloc_fcn is equivalent to the standard library realloc function. To be thorough, we search for realloc_fcn in the codebase:

C
parserCreate(const XML_Char *encodingName,
             const XML_Memory_Handling_Suite *memsuite,
             const XML_Char *nameSep, DTD *dtd)
{
    XML_Parser parser;  // Declare a pointer to hold the newly created parser

    if (memsuite) {  // If a custom memory handling suite is provided
        XML_Memory_Handling_Suite *mtemp;
        
        // Use the custom malloc function to allocate memory for the parser structure
        parser = (XML_Parser)memsuite->malloc_fcn(sizeof(struct XML_ParserStruct));
        
        if (parser != NULL) {  // Check if allocation succeeded
            // Assign memory handling functions to the parser's internal memory suite
            mtemp = (XML_Memory_Handling_Suite *)&(parser->m_mem);
            mtemp->malloc_fcn = memsuite->malloc_fcn;
            mtemp->realloc_fcn = memsuite->realloc_fcn;
            mtemp->free_fcn = memsuite->free_fcn;
        }
    } else {  // If no custom memory suite is provided, use standard malloc/free
        XML_Memory_Handling_Suite *mtemp;
        
        // Allocate memory for the parser using standard malloc
        parser = (XML_Parser)malloc(sizeof(struct XML_ParserStruct));
        
        if (parser != NULL) {  // Check if allocation succeeded
            // Assign default memory functions (malloc, realloc, free)
            mtemp = (XML_Memory_Handling_Suite *)&(parser->m_mem);
            mtemp->malloc_fcn = malloc;
            mtemp->realloc_fcn = realloc;
            mtemp->free_fcn = free;
        }
    }

This code snippet confirms our suspicion: unless an alternative memory handling suite is explicitly passed to parserCreate, realloc_fcn is indeed assigned to the standard realloc function. This might seem like a lengthy detour, but this thoroughness is paramount in root cause analysis. After all, the REALLOC macro could have been a safe wrapper around the realloc function, a common and commendable practice employed by many developers to mitigate memory-related issues.

Understanding Integer Overflow

Returning to the patch for CVE-2021-46143, the next logical question is how these comparison checks prevent an integer overflow, and what an integer overflow signifies in this context. Let’s perform a quick experiment by compiling and running the following C code:

C
#include       // For printf
#include      // For SIZE_MAX on some systems (e.g., Linux)

int main() {
    // Print the maximum value representable by size_t
    // (size_t)(-1) is a common trick to get the max size_t value (equivalent to SIZE_MAX)
    printf("SIZE_MAX: %zu\n", ((size_t)(-1)));

    // This computation does not cause overflow:
    // Divide SIZE_MAX by sizeof(int), then multiply back — result is still within range
    printf("no overflow: %zu\n", ((size_t)(-1) / sizeof(int)) * sizeof(int));

    // This computation causes an overflow:
    // By adding 1 to the quotient, then multiplying by sizeof(int), it exceeds SIZE_MAX
    printf("overflow: %zu\n", ((size_t)(-1) / sizeof(int) + 1) * sizeof(int));

    return 0; // Exit program successfully
}

Running this code on a typical system should yield output similar to this:

C
SIZE_MAX: 18446744073709551615
no overflow: 18446744073709551612
overflow: 0

This output vividly demonstrates integer overflow. There’s a maximum numerical value that unsigned integer types can represent. In binary, this is typically a sequence of all ones (e.g., 11111...) up to the number of bits allocated for that type. Since unsigned integers cannot be negative, casting -1 to an unsigned integer type results in a two’s complement operation, which effectively produces the largest possible value for that type.

In binary arithmetic, multiplying a number by two is equivalent to a “left shift” by 1 bit. Conversely, dividing by two (rounding down) is a right shift. For example, multiplying 7 (binary 111) by two results in 14 (binary 1110). If this operation causes the value to exceed the maximum representable number for the given data type, the most significant bits are truncated. Consequently, an unsigned integer overflow can occur where, for instance, a multiplication that should result in 1000000... (in binary) is truncated to 000000..., effectively becoming 0.

Integer overflows represent a common class of vulnerabilities that can lead to a wide array of undefined behavior if the resulting erroneous value is subsequently used in other functions. In the specific context of Expat, this overflow leads to the realloc function receiving a size argument of 0, thereby causing it to unexpectedly free memory instead of reallocating it.

Pinpointing the Attack Vector: Reaching the Vulnerable Code Path

To finalize our root cause analysis, we must understand how to reach this vulnerable code path, or “sink.” Fortunately, the pull request comment for CVE-2021-46143 also links to the corresponding issue on GitHub, titled “[CVE-2021-46143] Crafted XML file can cause integer overflow on m_groupSize in function doProlog.”

The issue notes that an anonymous white-hat researcher reported the vulnerability through the Zero Day Initiative (ZDI), an organization that facilitates zero-day vulnerability disclosures and offers financial rewards for such discoveries. Furthermore, it states that “the issue is an integer overflow (in multiplication) near a call to realloc that takes a 2 GiB size craft XML file, and then will cause denial of service or more.”

Finally, the issue comment includes a snippet from the vulnerability disclosure’s analysis section, which provides the critical context of the vulnerable code:

C
This is an integer overflow vulnerability that exists in expat library. The vulnerable function is doProlog

doProlog(XML_Parser parser, const ENCODING *enc, const char *s, const char *end, int tok, const char *next, const char **nextPtr, XML_Bool haveMore, XML_Bool allowClosingDoctype, enum XML_Account account) {
#ifdef XML_DTD
static const XML_Char externalSubsetName[] = {ASCII_HASH, '\0'};
#endif /* XML_DTD */
static const XML_Char atypeCDATA[]
--snip--
case XML_ROLE_GROUP_OPEN:
    if (parser->m_prologState.level >= parser->m_groupSize) {
        if (parser->m_groupSize) {
            {
                char *const new_connector = (char *)REALLOC(
                    parser, parser->m_groupConnector, parser->m_groupSize *= 2);// (1)
                if (new_connector == NULL) {
                    parser->m_groupSize /= 2;
                    return XML_ERROR_NO_MEMORY;
                }
                parser->m_groupConnector = new_connector;
            }

The crucial detail at (1) is: “At (1), integer overflow occurs if the value of m_groupSize is greater than 0x7FFFFFFF.” This final piece of the puzzle reveals the attack vector: a specially crafted, large XML file. For m_groupSize to reach such a significant number, the XML file must contain enough tokens that match the XML_ROLE_GROUP_OPEN case during parsing.

Note: While it’s not strictly necessary to recreate the full Proof of Concept (PoC) during root cause analysis, doing so can significantly deepen your understanding of the vulnerability. If you’re keen to try reproducing CVE-2021-46143, consider looking at the pull request and related issue for CVE-2021-45960. This related vulnerability often includes more detailed information about its PoC, sometimes even linking to a script that can generate it. You can likely adapt such a script to trigger CVE-2021-46143.

The Art of Root Cause Analysis: Beyond the Obvious

While Expat extensively documents its vulnerability remediation process, it’s important to acknowledge that in real-world scenarios, you’ll often have only fragments of information from published vulnerability advisories. Depending on the criticality of a bug, developers might choose to obscure a vulnerability patch by embedding it within a much larger update, or they might fix it at a higher level in the code, making the direct link less obvious. Additionally, vulnerability advisory descriptions may be deliberately vague or unclear to prevent malicious actors from reverse-engineering the exact vulnerability and exploiting it via n-day attacks on unpatched users.

Nevertheless, it’s almost always easier to analyze a patch diff of a known vulnerability than to discover a brand-new vulnerability from scratch. Root cause analysis of disclosed vulnerabilities is a highly valuable skill that, for the careful and persistent researcher, yields rich rewards in the form of uncovering related, impactful vulnerabilities.

Variant Pattern Matching: Hunting for Recurring Vulnerabilities

Now that we have a solid understanding of the root cause of CVE-2021-46143 in the Expat library, we can leverage this knowledge to write a powerful code analysis rule. Our goal is to identify other instances of this vulnerability, or “variants,” within the codebase.

To recap the key characteristics of CVE-2021-46143:

  1. An integer overflow occurs when multiplying a variable of an unsigned integer type beyond its maximum representable value.
  2. The overflowed integer is subsequently passed as the third argument to the REALLOC macro. If this variable overflows to 0, realloc (and thus REALLOC) performs an unintended free operation instead of a reallocation.
  3. The variable triggering the overflow (e.g., parser->m_groupSize) is ultimately attacker-controlled, typically via a crafted XML file.

Crafting Our Semgrep Rule

For single-repository variant analysis, we can afford to be quite specific with our patterns. Developers often exhibit consistent coding styles throughout a codebase, leading to recurring vulnerable patterns. Our strategy will involve an iterative approach:

  1. Start with an almost-exact match of the original vulnerable code.
  2. Gradually generalize the rule until we begin finding variants.

This iterative process helps us avoid overgeneralizing from the outset and keeps our scope manageable. Therefore, it’s generally better to begin with pattern matching rather than a full data flow analysis rule. For CVE-2021-46143, we’ll focus specifically on the sink of the vulnerability rather than tracing the entire source-to-sink data flow. The sink, in this case, is the third argument to the REALLOC macro, which was mitigated by the developers adding a comparison check just before its two invocations:

C
char *const new_connector = (char *)REALLOC(
    parser, parser->m_groupConnector, parser->m_groupSize *= 2);

int *const new_scaff_index = (int *)REALLOC(
    parser, dtd->scaffIndex, parser->m_groupSize * sizeof(int));

Initial Rule Development with Semgrep Playground

The Semgrep Playground is an invaluable tool for drafting and debugging Semgrep rules, thanks to its support for Semgrep Pro features and intuitive user interface.

Let’s begin by placing these two REALLOC invocations in the “test code” section of the Playground. In the “rule” section, switch to the “advanced” tab and construct a skeleton rule that precisely matches the first invocation:

C
rules:
  - id: CVE-2021-46143
    pattern: REALLOC(parser, parser->m_groupConnector, parser->m_groupSize *= 2);
    message: Detected variant of CVE-2021-46143.
    languages: [c]
    severity: ERROR

Click “Run” to confirm that the rule correctly highlights the line containing the first REALLOC invocation.

Next, we need to generalize this rule to match both invocations. A common first thought might be to use the ellipsis operator (...) to abstract away the last two arguments, as they are the only differences between the two invocations:

C
pattern: REALLOC(parser, ...);

While this pattern would match both, it would significantly increase the number of false positives. This is because it fails to differentiate between safe and vulnerable REALLOC invocations. The root cause of the vulnerability isn’t just any REALLOC call, but specifically one where the third argument is an integer overflow caused by a multiplication (e.g., parser->m_groupSize *= 2 or parser->m_groupSize * sizeof(int)).

Refining the Pattern with Metavariables

To accurately capture the vulnerability’s essence, we must match this specific multiplication pattern using metavariables:

C
rules:
  - id: CVE-2021-46143
    pattern-either:
      - pattern: REALLOC(parser, $POINTER, $SIZE * $CONSTANT);
      - pattern: REALLOC(parser, $POINTER, $SIZE *= $CONSTANT);
    message: Detected variant of CVE-2021-46143.
    languages: [c]
    severity: ERROR

Notice the crucial use of pattern-either here. We cannot simply nest these two pattern operators directly under a patterns operator, because patterns performs a logical AND operation (meaning the code would need to match both patterns simultaneously). To achieve a logical OR operation, indicating that the code must match either of the specified patterns, we use pattern-either.

Testing on the Vulnerable Expat Commit

With this refined basic rule, we’re ready to test it on the vulnerable commit of Expat.

  1. Save the rule to a file, for example, cve-2021-46143-variant-1.yml (or copy it from the book’s code repository).

  2. Clone the Expat repository and check out the vulnerable commit:

    $ git clone https://github.com/libexpat/libexpat
$ cd libexpat
$ git checkout 0adcb34c

  3. Run the Semgrep rule on the repository:

    $ semgrep -f ../cve-2021-46143-variant-1.yml .

If everything is configured correctly, you should see output similar to this:

Bash
Scanning 18 files. 18/18 tasks 0:00:00
Results
Findings: expat/lib/xmlparse.c CVE-2021-46143
Detected variant of CVE-2021-46143.
3271 temp = (ATTRIBUTE *)REALLOC(parser, (void *)parser->m_atts,
3272 parser->m_attsSize * sizeof(ATTRIBUTE));
----------------------------------------
3279 temp2 = (XML_AttrInfo *)REALLOC(parser, (void *)parser->m_attInfo,
3280 parser->m_attsSize * sizeof(XML_AttrInfo));
----------------------------------------
5049 char *const new_connector = (char *)REALLOC(
5050 parser, parser->m_groupConnector, parser->m_groupSize *= 2);
----------------------------------------
5059 int *const new_scaff_index = (int *)REALLOC(
5060 parser, dtd->scaffIndex, parser->m_groupSize * sizeof(int));
----------------------------------------
6130 temp = (DEFAULT_ATTRIBUTE *)REALLOC(parser, type->defaultAtts,
6131 (count * sizeof(DEFAULT_ATTRIBUTE)));
----------------------------------------
7131 temp = (CONTENT_SCAFFOLD *)REALLOC(
7132 parser, dtd->scaffold, dtd->scaffSize * 2 * sizeof(CONTENT_SCAFFOLD));
Scan Summary
Some files were skipped or only partially analyzed. Scan was limited to files tracked by git.
Partially scanned: 1 files only partially analyzed due to a parsing or internal Semgrep error
Scan skipped: 6 files matching .semgrepignore patterns
For a full list of skipped files, run semgrep with the --verbose flag.
Ran 1 rule on 18 files: 6 findings.

The rule successfully identifies the original two vulnerabilities that prompted its creation, along with four additional potential variants! These variants consistently involve a potentially attacker-controlled value multiplied by the size of a data structure, ultimately passed to REALLOC.

Deep Dive into a Variant: storeAtts

Let’s take a closer look at the first identified variant, located at line 3271 of xmlparse.c:

C
/* Precondition: all arguments must be non-NULL;
 * Purpose:
 * - normalize attributes
 * - check attributes for well-formedness
 * - generate namespace aware attribute names (URI, prefix)
 * - build list of attributes for startElementHandler
 * - default attributes
 * - process namespace declarations (check and report them)
 * - generate namespace aware element name (URI, prefix)
 */
static enum XML_Error storeAtts(XML_Parser parser, const ENCODING *enc, const char *attStr, TAG_NAME *tagNamePtr, BINDING **bindingsPtr, enum XML_Account account) {
    DTD *const dtd = parser->m_dtd; /* save one level of indirection */
    ELEMENT_TYPE *elementType;
    int nDefaultAtts;
    const XML_Char **appAtts; /* the attribute list for the application */
    int attIndex = 0;
    int prefixLen;
    int i;
    int n;
    XML_Char *uri;
    int nPrefixes = 0;
    BINDING *binding;
    const XML_Char *localPart;
    /* lookup the element type name */
    elementType = (ELEMENT_TYPE *)lookup(parser, &dtd->elementTypes, tagNamePtr->str, 0);
    if (! elementType) {
        const XML_Char *name = poolCopyString(&dtd->pool, tagNamePtr->str);
        if (! name) return XML_ERROR_NO_MEMORY;
        elementType = (ELEMENT_TYPE *)lookup(parser, &dtd->elementTypes, name, sizeof(ELEMENT_TYPE));
        if (! elementType) return XML_ERROR_NO_MEMORY;
        if (parser->m_ns && ! setElementTypePrefix(parser, elementType)) return XML_ERROR_NO_MEMORY;
    }
    nDefaultAtts = elementType->nDefaultAtts; /* (1) */
    /* get the attributes from the tokenizer */
    n = XmlGetAttributes(enc, attStr, parser->m_attsSize, parser->m_atts); /* (2) */
    if (n + nDefaultAtts > parser->m_attsSize) {
        int oldAttsSize = parser->m_attsSize;
        ATTRIBUTE *temp;
    #ifdef XML_ATTR_INFO
        XML_AttrInfo *temp2;
    #endif
        parser->m_attsSize = n + nDefaultAtts + INIT_ATTS_SIZE; /* (3) */
        temp = (ATTRIBUTE *)REALLOC(parser, (void *)parser->m_atts,
                                    parser->m_attsSize * sizeof(ATTRIBUTE)); /* (4) */

With experience, you’ll develop an intuition for what a particular code snippet does without needing to meticulously enumerate every detail. This intuition becomes invaluable when navigating more complex source code. Expat is considered a relatively straightforward codebase, with much of its core logic residing within a single file. Even with incomplete information, we can gather clues to assess potential vulnerabilities.

First, the storeAtts function, where this potential variant resides, is extensively commented, detailing its purpose. In essence, it appears to handle the parsing of XML attributes, which would indeed be attacker-controlled if the library were processing untrusted XML documents. More specifically, our attention should be on parser->m_attsSize rather than sizeof(ATTRIBUTE). While both are used in the third argument to REALLOC (the sink at (4)), parser->m_attsSize is potentially attacker-controlled, whereas sizeof(ATTRIBUTE) is a fixed, compile-time constant.

Looking a few lines back, we observe that parser->m_attsSize is set to the sum of several variables at (3). We can safely disregard INIT_ATTS_SIZE, as it’s a constant. nDefaultAtts is set at (1), and based on variable names, we can reasonably assume this value represents the number of default attributes for the type of element being parsed. While this seems less likely to be directly attacker-controllable (as it relies on fixed defaults), it’s worth filing away for potential future investigation.

Finally, n is set to the return value of a function at (2) that, according to the comment, “gets the attributes from the tokenizer.” If we look up XmlGetAttributes, we find that it’s actually a macro defined in expat/lib/xmltok.h:

C
#define XmlGetAttributes(enc, ptr, attsMax, atts) (((enc)->getAtts)(enc, ptr, attsMax, atts))

This macro essentially calls the getAtts member function of the enc struct instance with the same arguments. Searching for getAtts reveals its actual implementation in expat/lib/xmltok_impl.c. While a full manual analysis of this function is possible, the comment above its definition provides sufficient information:

C
/* This must only be called for a well-formed start-tag or empty element tag.
 * Returns the number of attributes. Pointers to the first attsMax attributes are stored in atts.
 */

This strongly suggests that n is, in fact, an attacker-controllable value, as it represents the number of attributes within the XML element being parsed. Although attsMax initially caused some concern (as it could potentially limit the number of attributes returned), the comment clarifies that it only limits the number of attributes stored in atts. We can confirm this by observing the function’s logic: it increments the return value nAtts regardless of whether it has exceeded attsMax:

C
case BT_QUOT:
    if (state != inValue) {
        if (nAtts  attsMax)
            atts[nAtts].valuePtr = ptr + MINBPC(enc);
        state = inValue;
        open = BT_QUOT;
    } else if (open == BT_QUOT) {
        state = other;
        if (nAtts  attsMax)
            atts[nAtts].valueEnd = ptr;
        nAtts++; // This increment happens regardless of 'if (nAtts 
    }
    break;

For instance, even though there’s a check if (nAtts , the nAtts++; statement falls outside the if statement’s body (in C, only the statement immediately following an if is executed unless enclosed in braces). This confirms that the ultimate value passed as the third argument to REALLOC is indeed partially attacker-controllable and therefore represents a valid vulnerability. While we took a comprehensive approach here, as highlighted earlier, you can often expedite the sink-to-source analysis by making reasonable inferences based on variable names and developer comments. This is a judgment call that depends on the size and complexity of the codebase and the time available for research.

Validating the Variant: CVE-2022-22827

A review of the pull request that addressed CVE-2022-22822 through CVE-2022-22827 reveals that it added a validation check prior to the REALLOC invocation in storeAtts (see the diff on GitHub):

C
+ /* Detect and prevent integer overflow */
+ if ((nDefaultAtts > INT_MAX - INIT_ATTS_SIZE)
+ || (n > INT_MAX - (nDefaultAtts + INIT_ATTS_SIZE))) {
+ return XML_ERROR_NO_MEMORY;
+ }
+ parser->m_attsSize = n + nDefaultAtts + INIT_ATTS_SIZE;
+
+ /* Detect and prevent integer overflow.
+ * The preprocessor guard addresses the "always false" warning
+ * from -Wtype-limits on platforms where
+ * sizeof(unsigned int) 
+#if UINT_MAX >= SIZE_MAX
+ if ((unsigned)parser->m_attsSize > (size_t)(-1) / sizeof(ATTRIBUTE)) {
+ parser->m_attsSize = oldAttsSize;
+ return XML_ERROR_NO_MEMORY;
+ }
+#endif

The description for CVE-2022-22827 explicitly states that “storeAtts in xmlparse.c in Expat (aka libexpat) before 2.4.3 has an integer overflow.” This definitively confirms that our crafted rule successfully detected a genuine variant of CVE-2021-46143.

Based on the other results from our Semgrep scan, the rule also correctly identified integer overflows in defineAttribute (corresponding to CVE-2022-22824) and nextScaffoldPart (corresponding to CVE-2022-22826). However, it failed to identify the vulnerabilities in addBinding (CVE-2022-22822), build_model (CVE-2022-22823), and lookup (CVE-2022-22825).

The failures for build_model and lookup are due to the fact that the overflowed integer in those cases is passed to a malloc call instead of realloc. For addBinding, the problematic code is:

C
XML_Char *temp = (XML_Char *)REALLOC(
    parser, b->uri, sizeof(XML_Char) * (len + EXPAND_SPARE));

Interestingly, if you copy this specific code snippet into a separate file, say false_negative.c, and scan it with our current Semgrep rule, it will detect the vulnerability. This discrepancy highlights a known limitation: the “Partially scanned: 1 files only partially analyzed due to a parsing or internal Semgrep error” message we saw earlier in the Semgrep output. This indicates that the Semgrep engine, at its current development stage, doesn’t yet fully support all nuances of the C language and can sometimes fail to properly parse certain code constructs. Additionally, Semgrep’s generic representation of code, a design choice for speed and language agnosticism, may not always capture all the intricacies of the C programming language.

To gain insight into how Semgrep internally represents the code, you can use its dump-ast feature:

Bash
semgrep --lang c --dump-ast false_negative.c

The abbreviated output shows that the AST (Abstract Syntax Tree) for the REALLOC invocation begins with a Call node. Semgrep does not differentiate between macro invocations and function calls in its AST, which is why the root of this tree is the generic Call element.

Beyond Direct Multiplication: Generalizing with pattern-inside

Despite these limitations, using a code scanning engine like Semgrep allows for pattern matching capabilities that far exceed simple regular expressions. Consider a scenario where a variable is first assigned the result of a multiplication or addition operation, and then that variable is passed as the third argument to REALLOC. This creates the same integer overflow vulnerability but requires a more generic pattern to detect.

To address this, we can utilize the pattern-inside operator in conjunction with metavariables:

YAML
rules:
  - id: CVE-2021-46143
    pattern-either:
      - pattern-inside: |
          (int $SIZE) = $VARIABLE * $CONSTANT;
          ...
      - pattern-inside: |
          (int $SIZE) *= $CONSTANT;
          ...
      - pattern-inside: |
          (int $SIZE) = $VARIABLE + $CONSTANT;
          ...
      - pattern-inside: |
          (int $SIZE) += $CONSTANT;
          ...
    - pattern: REALLOC(parser, $POINTER, $SIZE);
    message: Detected variant of CVE-2021-46143.
    languages: [c]
    severity: ERROR

In this enhanced rule:

If you run this refined rule on the Expat repository, you should uncover two new results:

Bash
Scanning 19 files. 19/19 tasks 0:00:00
Results
Findings: expat/lib/xmlparse.c CVE-2021-46143
Detected variant of CVE-2021-46143.
1938 temp = (char *)REALLOC(parser, parser->m_buffer, bytesToAllocate);
----------------------------------------
2573 char *temp = (char *)REALLOC(parser, tag->buf, bufSize);
Scan Summary
Some files were skipped or only partially analyzed. Scan was limited to files tracked by git.
Partially scanned: 1 files only partially analyzed due to a parsing or internal Semgrep error
Scan skipped: 6 files matching .semgrepignore patterns
For a full list of skipped files, run semgrep with the --verbose flag.
Ran 1 rule on 18 files: 2 findings.

By carefully analyzing these two new results, you will discover that one of them is, in fact, yet another integer overflow that was discovered later: CVE-2022-25315. Take some time to understand why one finding is a true positive while the other is a false positive. Hint: Are there any validation checks before the REALLOC invocation that might mitigate the potential overflow in the false positive case?

Recap: The Path to Variant Discovery

Before delving into multi-repository variant analysis, let’s quickly recap the iterative process we undertook to discover variants of CVE-2021-46143:

  1. Root Cause Analysis: We began by performing a detailed root cause analysis of the original vulnerability. This involved meticulously examining patch diffs and related metadata, such as patch notes and vulnerability advisories.
  2. Exact Match Pattern: We then crafted an almost exact match pattern for the vulnerability’s sink.
  3. Iterative Generalization: We iteratively generalized the rule, slowly expanding its scope to catch more variants while carefully managing potential false positives.

The flexibility of Semgrep allows you to tweak your rules to be as strict or as loose as your research demands. For instance, you could explicitly exclude all matches that include a validation check by utilizing the pattern-not-inside operator. However, it’s crucial to remember that each design choice in rule creation involves a trade-off between the rates of false positives and false negatives. The art lies in finding the optimal balance for your specific vulnerability research goals.

Exit mobile version