How integer underflow in array splice operations happens in C and how to fix it

Introduction

In tree-sitter's core array manipulation code, we discovered a critical integer underflow vulnerability in src/tree_sitter/array.h that could lead to severe memory corruption. The _array__splice() function at line 258 calculated a new array size using the expression uint32_t new_size = *size + new_count - old_count without validating that the arithmetic wouldn't underflow. Combined with assert() statements that disappear in release builds, this created a perfect storm for exploitation.

The vulnerable code also appeared in _array__erase() at line 197, where bounds checking relied entirely on assert statements. When compiled with NDEBUG defined (standard for production releases), these safety checks vanish, allowing invalid indices to trigger out-of-bounds memmove and memcpy operations. This is particularly dangerous in a Node.js library like tree-sitter, where vulnerabilities affect all downstream consumers who depend on this package for parsing operations.

The Vulnerability Explained

Let's examine the vulnerable code in _array__splice():

static inline void *_array__splice(void *self_contents, uint32_t *size, uint32_t *capacity,
                                 size_t element_size,
                                 uint32_t index, uint32_t old_count,
                                 uint32_t new_count, const void *elements) {
  uint32_t new_size = *size + new_count - old_count;  // VULNERABLE LINE
  uint32_t old_end = index + old_count;
  uint32_t new_end = index + new_count;
  assert(old_end <= *size);  // Disabled in release builds!

The critical flaw is in the size calculation. Because all variables are unsigned 32-bit integers (uint32_t), the expression *size + new_count - old_count can underflow when old_count > *size + new_count.

Example attack scenario: Imagine an attacker controlling the splice parameters calls the function with:
- *size = 10 (current array has 10 elements)
- new_count = 5 (inserting 5 new elements)
- old_count = 20 (claiming to remove 20 elements)

The calculation becomes: 10 + 5 - 20 = -5, but since we're using unsigned integers, this wraps around to 4,294,967,291 (0xFFFFFFFB). The code then attempts to allocate and copy this massive amount of memory, causing:

1. Memory exhaustion from attempting to allocate ~4GB
2. Buffer overflow when memcpy writes beyond allocated bounds
3. Heap corruption from invalid memory operations

The assert(old_end <= *size) should catch this, but it's compiled out in production builds. The similar vulnerability in _array__erase() at line 197 has the same problem:

static inline void _array__erase(void* self_contents, uint32_t *size,
                                size_t element_size, uint32_t index) {
  assert(index < *size);  // Gone in release builds
  char *contents = (char *)self_contents;
  memmove(contents + index * element_size, contents + (index + 1) * element_size,
          (*size - index - 1) * element_size);  // Out-of-bounds if index >= *size

If index >= *size, the memmove operation reads from and writes to invalid memory addresses, potentially corrupting adjacent heap structures or causing crashes that could be leveraged for code execution.

The Fix

The fix addresses both the integer underflow and the assert-only validation with two key changes:

Change 1: Reorder arithmetic to prevent underflow

// BEFORE (vulnerable):
uint32_t new_size = *size + new_count - old_count;
uint32_t old_end = index + old_count;
assert(old_end <= *size);

// AFTER (secure):
uint32_t old_end = index + old_count;
assert(old_end <= *size);
if (old_end > *size) return self_contents;  // Runtime check
uint32_t new_size = *size - old_count + new_count;  // Subtract first

By reordering the calculation to *size - old_count + new_count, we perform the subtraction first. The explicit runtime check if (old_end > *size) ensures we never reach the arithmetic if old_count would cause problems. This check remains active in all builds, unlike assert().

Change 2: Add explicit bounds validation

// In _array__erase():
assert(index < *size);
if (index >= *size) return;  // Early return prevents out-of-bounds access
char *contents = (char *)self_contents;
memmove(contents + index * element_size, ...);

The if (index >= *size) return; statement provides production-safe validation. Even when assert() is disabled, this check prevents the dangerous memmove call with invalid indices.

These changes work together to ensure that:
- Arithmetic operations never underflow
- Bounds checks remain active in release builds
- Invalid parameters cause safe early returns instead of memory corruption
- The existing test suite continues to pass, preserving intended behavior

Prevention & Best Practices

To avoid integer underflow vulnerabilities in C array manipulation code:

1. Never rely on assert() for security-critical validation: Assert statements are debugging aids, not security controls. Always use explicit runtime checks for bounds validation.

2. Order arithmetic operations carefully with unsigned integers: When working with unsigned types, subtract before adding to minimize underflow risk. Consider using signed integers when the value can legitimately be negative.

3. Validate all arithmetic inputs: Before performing calculations like a + b - c, verify that c <= a + b to prevent wraparound. Check for overflow/underflow conditions explicitly.

4. Use safe integer arithmetic libraries: Consider libraries like SafeInt (C++) or compiler built-ins like __builtin_add_overflow() that detect arithmetic errors.

5. Enable compiler warnings: Use -Wconversion and -Wsign-conversion to catch potentially dangerous implicit conversions between signed and unsigned types.

6. Static analysis in CI/CD: Integrate tools like Semgrep, CodeQL, or Clang Static Analyzer into your build pipeline to catch these patterns before they reach production.

7. Follow CERT C guidelines: Specifically, CERT C rule INT30-C (ensure unsigned integer operations do not wrap) and INT32-C (ensure operations on signed integers do not result in overflow).

The OWASP Code Review Guide emphasizes that integer vulnerabilities are particularly dangerous in memory-unsafe languages like C, where they often lead to buffer overflows. Always treat size calculations as security-critical code paths.

Key Takeaways

• The _array__splice() function calculated new_size = *size + new_count - old_count without preventing underflow, allowing wraparound to massive values when old_count exceeded the sum of other operands.

• Assert-only validation in _array__erase() and _array__splice() disappeared in release builds, removing the only bounds checks between user input and dangerous memcpy/memmove operations.

• Reordering arithmetic to subtract before adding (*size - old_count + new_count) prevents underflow by ensuring the subtraction happens when we know the relationship between operands.

• Explicit runtime checks like if (old_end > *size) return self_contents; provide production-safe validation that remains active regardless of build configuration or optimization level.

• Tree-sitter is a Node.js library, so this vulnerability affected all downstream consumers who parse code using this package—demonstrating how memory safety issues in native dependencies propagate through the ecosystem.

How Orbis AppSec Detected This

• Source: Array manipulation parameters (index, old_count, new_count) passed to _array__splice() and _array__erase() functions in src/tree_sitter/array.h
• Sink: Unsafe arithmetic operations at line 260 (*size + new_count - old_count) and subsequent memcpy/memmove calls at lines 202 and 271 that use the potentially underflowed size value
• Missing control: No runtime validation that old_count <= *size + new_count before arithmetic, and bounds checks using assert() that are disabled in production builds with NDEBUG
• CWE: CWE-191 (Integer Underflow/Wraparound) leading to CWE-120 (Buffer Copy without Checking Size of Input)
• Fix: Added explicit runtime bounds checks before arithmetic operations and reordered size calculation to prevent underflow

Orbis AppSec automatically detected this vulnerability and opened a pull request with the fix. Try Orbis AppSec on your repositories to find and fix issues like this automatically.

Conclusion

This integer underflow vulnerability in tree-sitter's array.h demonstrates why arithmetic operations on unsigned integers require the same careful validation as pointer operations in C. The combination of underflow-prone calculations and assert-only bounds checking created a critical security flaw that could lead to memory corruption in production builds.

The fix—reordering arithmetic and adding explicit runtime checks—is a template for securing similar array manipulation code. By treating size calculations as security-critical and never relying on assert() for production validation, developers can prevent this entire class of vulnerabilities.

For developers working with C arrays and dynamic memory, remember: unsigned integer arithmetic can wrap around silently, and debug-only checks provide no protection in release builds. Always validate, always check bounds explicitly, and always assume your arithmetic might be wrong.

References

• CWE-191: Integer Underflow (Wrap or Wraparound)
• CWE-120: Buffer Copy without Checking Size of Input ('Classic Buffer Overflow')
• OWASP: Buffer Overflow
• CERT C Coding Standard: INT30-C
• Semgrep Rule: Integer Overflow/Underflow Detection
• fix: add bounds check before memcpy in array.h