How integer overflow in malloc happens in C bipartite matching and how to fix it

Introduction

In the advanced graph algorithms module, we discovered a high-severity integer overflow vulnerability in src/advanced_graph_algorithms/bipartite_matching.c at line 15. The bipartite_color(), bfs_dinic_matching(), and max_bipartite_matching() functions all contained the same dangerous pattern: computing allocation sizes using unchecked multiplication like malloc(sizeof(int) * V).

When processing graph data where V (the vertex count) comes from external input, an attacker could supply a crafted value that causes sizeof(int) * V to overflow, wrapping around to a small number. The subsequent memory operations would then write beyond the allocated buffer, corrupting the heap and potentially enabling arbitrary code execution.

This vulnerability is particularly concerning because bipartite matching algorithms are commonly used in resource allocation, scheduling systems, and network flow analysis—contexts where input data often originates from untrusted sources.

The Vulnerability Explained

The Dangerous Pattern

The vulnerable code appeared in three separate functions within bipartite_matching.c. Here's the original pattern from bipartite_color():

bool bipartite_color(Graph* graph, int* color)
{
    int V = graph->V;
    for (int i = 0; i < V; i++)
        color[i] = -1;

    int* queue = malloc(sizeof(int) * V);  // VULNERABLE: unchecked multiplication
    if (queue == NULL)
        return false;
    // ... queue operations assume V elements available
}

The same pattern appeared in bfs_dinic_matching():

int* queue = malloc(sizeof(int) * V);  // Line 60: same vulnerability

And in max_bipartite_matching():

int* color = malloc(sizeof(int) * V);           // Vulnerable
int** residual = malloc(sizeof(int*) * total_vertices);  // Vulnerable
int* level = malloc(sizeof(int) * total_vertices);       // Vulnerable
int* start = malloc(sizeof(int) * total_vertices);       // Vulnerable

How Integer Overflow Causes Heap Corruption

On a 32-bit system (or when size_t is 32 bits), consider what happens when V = 1073741825 (which is 2^30 + 1):

sizeof(int) * V = 4 * 1073741825 = 4294967300

But 4294967300 exceeds 2^32 - 1 (the maximum 32-bit unsigned value), so it wraps around:

4294967300 mod 2^32 = 4

The malloc(4) call allocates only 4 bytes—space for a single integer—while the code proceeds to use this buffer as if it held over a billion integers. Every subsequent array access beyond index 0 corrupts adjacent heap memory.

Attack Scenario

An attacker targeting this containerized service could:

1. Craft malicious graph input: Submit a graph structure with V set to a value like 0x40000001 (1073741825)
2. Trigger the allocation: Call any function that processes bipartite matching
3. Exploit heap overflow: The undersized buffer allocation followed by normal graph traversal writes attacker-controlled data past the buffer boundary
4. Achieve code execution: Overwrite heap metadata or adjacent objects to hijack control flow

Because this is a containerized service, the attack surface depends on network exposure, but any endpoint accepting graph data becomes a potential entry point.

The Fix

The fix applies three defensive measures consistently across all vulnerable allocation sites:

1. Bounds Validation Before Allocation

Each function now validates that V (or total_vertices) is positive before any allocation:

// BEFORE (vulnerable)
int* queue = malloc(sizeof(int) * V);

// AFTER (fixed)
if (V <= 0)
    return false;
int* queue = calloc(V, sizeof(int));

This prevents negative values (which would be interpreted as huge unsigned values) and zero-size allocations.

2. Replace malloc() with calloc()

The critical change replaces malloc(sizeof(type) * count) with calloc(count, sizeof(type)):

// BEFORE: Unchecked multiplication happens in application code
int* queue = malloc(sizeof(int) * V);

// AFTER: calloc() performs overflow-safe multiplication internally
int* queue = calloc(V, sizeof(int));

The calloc() function is required by modern C standards to check for overflow when computing count * size. If overflow would occur, calloc() returns NULL rather than allocating an undersized buffer.

3. Consistent Application Across All Allocation Sites

The fix addresses every vulnerable allocation in the file:

Complete Before/After Comparison

Before (vulnerable max_bipartite_matching):

int max_bipartite_matching(Graph* graph, int** match_pairs, int* match_count)
{
    if (graph == NULL || match_pairs == NULL || match_count == NULL)
        return 0;

    int V = graph->V;
    int* color = malloc(sizeof(int) * V);  // No overflow check
    if (color == NULL)
        return 0;
    // ...
    int** residual = malloc(sizeof(int*) * total_vertices);  // No overflow check

After (fixed):

int max_bipartite_matching(Graph* graph, int** match_pairs, int* match_count)
{
    if (graph == NULL || match_pairs == NULL || match_count == NULL)
        return 0;

    int V = graph->V;
    if (V <= 0)           // NEW: bounds validation
        return 0;
    int* color = calloc(V, sizeof(int));  // FIXED: safe multiplication
    if (color == NULL)
        return 0;
    // ...
    int** residual = calloc(total_vertices, sizeof(int*));  // FIXED: safe multiplication

Prevention & Best Practices

Safe Allocation Patterns in C

1. Always use calloc() for array allocations: The two-argument form provides built-in overflow protection
   ```c
   // Prefer this:
   int* arr = calloc(count, sizeof(int));

// Over this:
int* arr = malloc(count * sizeof(int));
```

1. Validate bounds before allocation: Check that counts are positive and within reasonable limits
   c if (count <= 0 || count > MAX_REASONABLE_SIZE) { return ERROR_INVALID_SIZE; }

2. Use safe multiplication helpers: For cases where malloc() is required, use overflow-checking multiplication:
   c size_t size; if (__builtin_mul_overflow(count, sizeof(int), &size)) { return NULL; // Overflow detected } int* arr = malloc(size);

Static Analysis Integration

Configure your CI pipeline to detect this pattern:

• Semgrep rule: utils.custom.integer-overflow-malloc catches malloc(a * b) patterns
• Compiler warnings: Enable -Warray-bounds and -Walloc-size-larger-than=
• AddressSanitizer: Runtime detection of heap overflows during testing

Code Review Checklist

When reviewing C code that handles dynamic allocation:

• [ ] Are all malloc() size calculations checked for overflow?
• [ ] Is calloc() used for array allocations?
• [ ] Are size parameters validated before use?
• [ ] Is the allocation result checked for NULL?

Key Takeaways

• Never use malloc(sizeof(type) * count) with untrusted count values—the multiplication can overflow silently
• The bipartite_matching.c functions now validate V <= 0 before any allocation, preventing both negative wraparound and zero-size edge cases
• calloc(count, size) is safer than malloc(count * size) because calloc performs overflow-checked multiplication internally
• Graph algorithm implementations are high-risk because vertex/edge counts often come from parsed input data
• All five allocation sites in this file required the same fix pattern—when you find one instance, search for similar patterns throughout the codebase

How Orbis AppSec Detected This

• Source: The graph->V field containing the vertex count, which originates from graph input data
• Sink: malloc(sizeof(int) * V) calls in bipartite_color(), bfs_dinic_matching(), and max_bipartite_matching() functions
• Missing control: No overflow check on the multiplication sizeof(int) * V before allocation
• CWE: CWE-190 (Integer Overflow or Wraparound) leading to CWE-122 (Heap-based Buffer Overflow)
• Fix: Replaced malloc(sizeof(type) * count) with calloc(count, sizeof(type)) and added bounds validation (if (V <= 0) return)

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

Integer overflow vulnerabilities in memory allocation are among the most dangerous bugs in C programs because they combine silent arithmetic errors with heap corruption—a recipe for exploitable memory safety violations. The fix in bipartite_matching.c demonstrates the defensive pattern every C developer should follow: validate bounds, use calloc() for arrays, and never trust arithmetic with untrusted inputs.

This vulnerability in graph algorithm code highlights that security issues aren't limited to obvious attack surfaces like network parsers. Any code path that processes external data and performs memory allocation is a potential target. By adopting safe allocation patterns and integrating static analysis into your development workflow, you can catch these issues before they reach production.

References

• CWE-190: Integer Overflow or Wraparound
• CWE-122: Heap-based Buffer Overflow
• OWASP Buffer Overflow Prevention Cheat Sheet
• C11 Standard - calloc() specification
• Semgrep C memory allocation rules
• fix: add integer overflow check in bipartite_matching.c...