# libgit2 — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

One O(n²) defect in libgit2's filesystem reference backend. `ref_available()` performs an O(R) packed-ref list scan per path segment check — called at 17 sites — causing O(R²) total overhead for repositories with many references. Patch ready for upstream review.

## The Defects

**libgit2-0001 (PATCHED — HIGH):** `src/libgit2/refs.c`

```c
/* git_refdb_backend_fs.ref_available() — per segment per path check: */
/* Called at 17 sites */
static int ref_available(git_refdb_backend *_backend,
                         const char *refname, ...)
{
    /* O(R) packed-ref list scan per segment */
    git_sortedcache_rlock(backend->refcache);
    size_t i;
    for (i = 0; i < git_sortedcache_entrycount(backend->refcache); i++) {
        struct packref *ref = git_sortedcache_entry(backend->refcache, i);
        if (is_prefix_of(ref->name, refname)) { ... }
    }
    /* O(R²) total across 17 call sites */
}
```

O(R) packed-ref scan per path segment check, at 17 call sites. **O(R²) total**. **Measured ratio: 17 sites.**

## Complexity Proof

For R packed references:
- Per `ref_available()` call: O(R) scan
- 17 call sites per ref operation: O(17×R) per operation
- R operations: O(R²) total
- Fixed: binary search on sorted refs → O(R × log R)
- **17 call sites measured.**

## Impact

All libgit2 users and all software built on libgit2: GitHub's Rugged (Ruby), pygit2 (Python), git2go (Go), NodeGit, libgit2sharp (.NET), and Git GUI clients. Repositories with many references (many branches, many tags — common in large monorepos and CI/CD systems) hit O(R²) during reference creation, renaming, and deletion. libgit2 is the foundation of most non-C Git tooling.

## The Fix

Use binary search on the sorted reference cache instead of linear scan:

```c
/* Before */
for (i = 0; i < git_sortedcache_entrycount(backend->refcache); i++) {
    struct packref *ref = git_sortedcache_entry(backend->refcache, i);
    if (is_prefix_of(ref->name, refname)) { ... }
}

/* After */
/* CWE-407 fix: binary search on sorted refcache for O(log R) per check. */
size_t pos;
int error = git_sortedcache_lookup_raw(backend->refcache, &pos, refname);
/* Binary search gives insertion point; check neighbors for prefix overlap */
```

## Patch

`defects/libgit2/patch/libgit2-0001-refs-binary-search.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your reference backend test suite.
3. Assess CVE eligibility — affects all 17 ref_available call sites in large repositories.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

Contact: see cover email. This brief is confidential until coordinated disclosure.