Don’t recurse on untrusted input

Alexis Challande, Brad Swain
recursion, vulnerability-disclosure, java
Page content

A single malicious request can take down web applications that use recursive functions to process untrusted user input. We developed a simple CodeQL query to assist in finding stack overflows and used it to find denial-of-service (DoS) vulnerabilities in several high-profile Java projects. All of these projects are maintained by security-conscious organizations with robust development practices:

Our findings indicate that recursion, while a powerful programming tool, becomes a severe liability when used to process untrusted data in applications with availability requirements. All of the above vulnerabilities have been fixed; however, if large-scale projects like these are vulnerable, you may have similar issues in your code. Read on to learn about how we discovered these issues and how to prevent them, or check out our full white paper.

How recursion is harmful

Recursion can be elegant, simple, and, most importantly, practical. It is often the go-to method for dealing with nested structures, whether traversing a tree, visiting nodes in a graph, or parsing nested structures like JSON.

public int fibonacci(int n)  {
  if(n == 0) return 0;
  else if(n == 1) return 1;
  else return fibonacci(n - 1) + fibonacci(n - 2);
}
Figure 1: Recursive Fibonacci function from Stack Overflow

However, if attackers control the input, it is often trivial to craft an input that will exhaust the stack before reaching the recursive function’s base case. While developers often think about preventing infinite recursion, it may be possible to crash an application by simply providing a single malicious input that triggers a stack overflow.

Exception in thread "main" java.lang.StackOverflowError
    at Fibonacci.fibonacci(Fibonacci.java:8)
    at Fibonacci.fibonacci(Fibonacci.java:8)
    at Fibonacci.fibonacci(Fibonacci.java:8)
Figure 2: StackOverflowError from Stack Overflow

While client-side crashes may be inconvenient, server-side crashes can take down critical services, even with DDoS protection. In applications with availability requirements, this is a real risk with the potential for real harm.

Protobuf Java case study

To illustrate how these vulnerabilities manifest in practice, let’s examine our discovery of CVE-2024-7254 in Google’s protocol buffers (Protobuf) library. This issue demonstrates how even security-conscious organizations can miss recursive processing vulnerabilities.

According to Protobuf’s official documentation:

Protocol buffers are Google’s language-neutral, platform-neutral, extensible mechanism for serializing structured data – think XML, but smaller, faster, and simpler. (source)

Parsing untrusted data is notoriously tricky, and security researchers have targeted parsers for every format. Google developed protocol buffers to provide a serialized exchange format with automatically generated parsers in various languages. They are used extensively both within Google and in the greater ecosystem.

However, they are also vulnerable to recursion error attacks.

For instance, an attacker could crash a Java application parsing an external message using the protobuf-lite library by simply sending this one message:

with open("recursive.data", "wb") as f:
    f.write(bytearray([19] * 5_000_000))
Figure 3: A malicious message in Protobuf

This message will throw a StackOverflowError. The problem lies in how Protobuf parses Unknown Fields. According to the Protobuf documentation:

Unknown fields are well-formed protocol buffer serialized data representing fields that the parser does not recognize. For example, when an old binary parses data sent by a new binary with new fields, those new fields become unknown fields in the old binary.

When this issue is combined with Groups—a deprecated feature that is still parsed because of backward compatibility—you get an explosive mix:

  1. A group can contain another group.

  2. The new group is parsed as an unknown field if the attacked schema does not contain a group.

  3. An unknown group can contain another group.

  4. Goto 2

Below is an excerpt of the code responsible for the parsing:

final boolean mergeOneFieldFrom(B unknownFields, Reader reader) throws IOException {
  int tag = reader.getTag();
  /* ... */
  switch (WireFormat.getTagWireType(tag)) {
    /* ... */
    case WireFormat.WIRETYPE_START_GROUP:
      final B subFields = newBuilder();
      /* ... */
      mergeFrom(subFields, reader);
      /* ... */
      return true;
    /* ... */
  }
}

final void mergeFrom(B unknownFields, Reader reader) throws IOException {
  while (true) {
    if (reader.getFieldNumber() == Reader.READ_DONE
        || !mergeOneFieldFrom(unknownFields, reader)) {
      break;
    }
  }
}
Figure 4: mergeFrom function in Protobuf

The exciting thing about this vulnerability is that it has one precondition on the attacked target: it must use the Java lite version of the Protocol Buffer library. There are no requirements for the scheme used by the targeted application.

While the official documentation of the C++ API advises discarding Unknown Fields for security reasons, it advises doing it after parsing the message. At this point, it is already too late. While Protobuf parsing is usually resilient against recursion attacks (using depth counters), Google forgot about this one code path during development. We responsibly disclosed this issue to Google, and it was assigned CVE-2024-7254.

While investigating this problem, we found that it also applied to other Protobuf implementations, including Rust-protobuf, an unofficial implementation of Protocol buffers in Rust.

Protecting your code

As software systems increasingly need to handle nested data formats like JSON, XML, and Protocol Buffers, the risk from recursive processing has grown. Our initial research focused primarily on Java projects, but the underlying pattern of recursing on untrusted input transcends language boundaries, suggesting a systemic security risk.

Here are two concrete steps to protect applications:

  1. Audit your code. Identify recursive functions processing untrusted data, and look for parsing operations on nested data formats. Pay special attention to library code that handles deserialization. Static analysis tools like our CodeQL query can help streamline the auditing process.

  2. Implement safety measures. Consider iterative alternatives, add explicit depth limits to recursive operations, and validate input size and nesting depth before processing, if possible.

Here is an example of adding a depth counter to prevent malicious recursion:

public static final int MAX_DEPTH = 100;

public static int fibonacci(int n) throws InputTooBigException {
   return _fibonacci(n, 0);
}

public static int _fibonacci(int n, int depth) throws InputTooBigException  {
   if (depth >= MAX_DEPTH)
       throw new InputTooBigException();

   if(n == 0) return 0;
   else if(n == 1) return 1;
   else
       return _fibonacci(n-1, depth+1) + _fibonacci(n-2, depth+1);
}
Figure 5: Fibonacci updated with a depth counter

Learn more

For a deeper dive into our findings: