Non-Transitive Comparators Explained: When Sorting Quietly Walks Off the Array

You hand a sorting routine a list of numbers and a comparison function. It promises to put everything in order. What it actually does, under the right conditions, is wander past the end of your array and start rewriting whatever lives next to it on the stack.

That is the quiet power of a non-transitive comparator.

Most developers treat comparison functions as pure mathematical relations. They assume that if a < b and b < c, then necessarily a < c. When the comparison is implemented as a simple signed subtraction, that assumption dies the moment the numbers get large enough to overflow. The sorting algorithm never gets the memo. It keeps walking left, confident that it will eventually hit a proper lower bound, and ends up treating neighboring memory as part of the array.

This article walks through the idea from first principles, shows how the overflow creates the non-transitive behavior, demonstrates a concrete exploitation path that turns the write into a leak and then into code execution, and finishes with practical defenses.

---

What Is a Non-Transitive Comparator, Anyway?

A relation is transitive when the following always holds:

if a < b and b < c, then a < c

Most textbook sorting algorithms rely on this property (along with reflexivity and totality) to guarantee correct ordering and, more importantly, to stay inside the array bounds.

Now look at a typical C comparator:

int compar(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

On paper this returns a negative value when a < b, zero when equal, and positive when a > b. In reality, when the difference exceeds the range of a signed integer, the result wraps around. The mathematical relation collapses.

Concrete example with 32-bit signed integers:

a =  2_000_000_000
b = -2_000_000_000
c =  1_000_000_000

• a - b overflows and becomes negative → the comparator claims a < b
• b - c underflows and becomes positive → the comparator claims b > c
• a - c stays positive → the comparator claims a > c

You now have a < b, b > c, yet a > c. The relation is no longer transitive.

The same pattern appears with 64-bit longs. The numbers just get larger before they wrap. The core idea stays identical: signed subtraction is not a total order once overflow is possible.

Why sorting algorithms care

glibc’s qsort (in older and still-common versions) contains an insertion-sort cleanup phase after the main quicksort work. That phase walks left from the current element looking for the correct insertion point. The loop assumes that the left boundary of the array will eventually stop it. When the comparator can return “less than” even for the true left boundary, the walk continues into whatever memory sits before the array.

The insertion loop looks roughly like this in spirit:

tmp_ptr = run_ptr - size;
while ((*cmp)((void *)run_ptr, (void *)tmp_ptr) < 0)
    tmp_ptr -= size;

If cmp can keep returning negative values even when tmp_ptr has already left the array, the pointer keeps moving. Each step is a potential write when the algorithm later swaps or shifts elements.

That is the entire primitive: a controlled walk past the start of the array, driven by carefully chosen values that trigger overflow in the comparator.

---

Why Should You Care?

Sorting is everywhere. Databases, language runtimes, network stacks, configuration loaders, game engines, and small utility services all call sorting routines. Many of those routines still accept custom comparators written as simple arithmetic.

The resulting out-of-bounds write is often on the stack, right next to:

• Saved return addresses
• Function pointers (including the comparator table itself)
• Format-string arguments used for printing results
• Other local buffers that can be shifted into view

Once you control an out-of-bounds write relative to a known array, classic primitives become available:

• Partial pointer overwrites that produce leaks
• GOT overwrites that turn a later library call into an arbitrary function
• Stack pivots or function-pointer corruption that lead to code execution

In short, a “harmless” comparison bug can become a full memory-corruption primitive with almost no additional effort from the attacker. The sorting routine does the heavy lifting.

Design choice	Main risk
Plain signed subtraction in comparator	Non-transitive order, OOB walks
Large element counts under low memory	Forces insertion-sort path
Stack-adjacent array	Nearby pointers become writable
Print-after-sort	Turns shifted pointers into leaks
Writable GOT + known libc	Turns leaks into code execution

The difference that matters is between raising the cost of analysis and actually moving the decision off the client. A non-transitive comparator raises cost only until someone maps the overflow.

---

Worked Example / Scenario

Imagine a small service that lets users sort arrays of integers or longs under a configurable memory limit. The service exposes two interesting features:

1. A memory-reduction option that lowers the process’s address-space limit (RLIMIT_AS).
2. A sorting endpoint that accepts an array size, a direction (ascending or descending), and the values themselves.

When the memory limit is set low enough, malloc inside qsort fails. glibc then falls back to a path that uses the stack for temporary storage and eventually runs an insertion-sort cleanup. That cleanup is the vulnerable code path.

Discovering the primitive

You notice that the comparators are simple signed subtractions. You also notice that the service lets you control both the values in the array and the memory limit. Setting a tight RLIMIT_AS forces the slow path. Feeding the sorter a carefully crafted array of “positive” and “negative” values (chosen so that overflow produces the non-transitive results) makes the insertion phase walk past the start of the array.

Each step of the walk performs a write. By controlling the values, you control both the distance of the walk and the data that gets written.

A typical setup looks like this:

1. Lower RLIMIT_AS so malloc fails
2. Prepare an array whose first element is the value you want to plant
3. Fill the rest of the array with values that force the comparator
   to keep walking left (the "negative" companions that trigger overflow)
4. Call the sorter
5. Observe that nearby stack data has been overwritten

The walk distance is determined by how many times the comparator returns negative before it finally returns non-negative. That is fully under attacker control.

Turning the write into a leak

The array lives on the stack near a table of function pointers (the various comparators themselves) and format-string pointers used for printing results. By walking a short distance you can overwrite a low byte of a pointer, shift it into the user-controlled area, and then ask the service to print the array. The leaked value gives you a PIE base.

A concrete sequence:

- Overwrite a low byte so a known function pointer moves into the printable region
- Request a sorted dump of a small slice of the array
- Parse the printed value
- Subtract the known offset of that function to recover the binary base

Because the service already prints the sorted results, you do not need a separate information leak vulnerability. The print path is the leak path.

Escalating to code execution

With a PIE base in hand you can target the Global Offset Table. Overwriting a GOT entry (for example printf) with a known libc address turns a later print operation into an arbitrary call. A second overwrite plants system and a pointer to the string "/bin/sh". One more sort triggers the call and you have a shell.

The entire chain stays inside the original process; no new vulnerabilities are required after the initial non-transitive write.

High-level chain:

non-transitive OOB write
        ↓
partial pointer overwrite → PIE leak
        ↓
GOT overwrite (printf → system or similar)
        ↓
plant "/bin/sh" and call
        ↓
shell

Adjacent ideas and variants

• The same overflow works on 32-bit and 64-bit integers; only the constants change.
• Descending comparators (b - a) produce the mirror image of the same bug.
• If the service lets you choose element size (char, short, int, long), each size gives a different walk stride and therefore a different set of reachable stack offsets.
• Resource limits other than RLIMIT_AS can also force fallback paths in other libraries; the pattern is not unique to glibc qsort.

---

Vulnerable Code Examples

Broken comparator (C)

/* Vulnerable: signed subtraction overflows and breaks transitivity */
int broken_compar(const void *pa, const void *pb) {
    int a = *(const int *)pa;
    int b = *(const int *)pb;
    return a - b;   /* undefined behavior on overflow */
}

Why it is dangerous: any caller that assumes a transitive total order (including the insertion-sort phase of many qsort implementations) can be forced past array bounds.

Safer alternatives

/* Safe: explicit comparison avoids overflow */
int safe_compar(const void *pa, const void *pb) {
    int a = *(const int *)pa;
    int b = *(const int *)pb;
    if (a < b) return -1;
    if (a > b) return  1;
    return 0;
}

/* Also safe: unsigned subtraction or use of <stdckdint.h> checked arithmetic */
#include <stdckdint.h>

int checked_compar(const void *pa, const void *pb) {
    int a = *(const int *)pa;
    int b = *(const int *)pb;
    int diff;
    if (ckd_sub(&diff, a, b)) {
        /* overflow happened; fall back to relational operators */
        if (a < b) return -1;
        if (a > b) return  1;
        return 0;
    }
    return diff;
}

The patched version never wraps; the mathematical relation stays transitive for the entire domain of int.

Forcing the vulnerable path (conceptual)

/* Lower the address-space limit so malloc inside qsort fails */
struct rlimit rl = { .rlim_cur = 8192, .rlim_max = 8192 };
setrlimit(RLIMIT_AS, &rl);

/* Now call qsort with a large enough element count and the broken comparator.
   glibc falls back to the insertion-sort path that walks out of bounds. */
qsort(array, count, sizeof(*array), broken_compar);

A minimal harness that demonstrates the walk

/* Conceptual only — not a complete exploit */
long array[128];
array[0] = TARGET_VALUE;          /* the value we want to plant */
for (int i = 1; i < 128; i++)
    array[i] = NEGATIVE_COMPANION; /* forces continued left walk */

qsort(array, 128, sizeof(long), broken_compar);
/* nearby stack slots have now been rewritten */

---

Defense / How to Fix

1. Never implement comparators with plain signed subtraction. Use explicit relational operators or checked arithmetic. The one-line return a - b; is the classic foot-gun.

2. Audit every call site of qsort, heapsort, mergesort and language-runtime equivalents. Look for custom comparators that perform arithmetic on the values being compared. Pay special attention to code that also manipulates resource limits.

3. Treat RLIMIT_AS (and similar resource limits) as an attack surface. Code that intentionally lowers them should be reviewed for fallback paths that become more dangerous under low memory. The combination of a tight limit and a large sort is a red flag.

4. Enable compiler warnings and sanitizers. -fsanitize=undefined and -Wsign-compare catch many of these bugs at build or test time. AddressSanitizer will also flag the eventual out-of-bounds access once the walk occurs.

5. Prefer library-provided comparison helpers when they exist (for example std::less in C++ or the comparison functions in modern C standards). They are less likely to hide overflow bugs.

6. Consider replacing qsort with algorithms that do not rely on insertion-sort cleanup phases, or with implementations that have been hardened against non-transitive comparators. Some modern libraries document that they require strict weak ordering and will abort or misbehave otherwise; treat that as a feature, not a bug.

7. Fail closed on suspicious resource limits. If a process intentionally sets a very low RLIMIT_AS before a large sort, log it and consider refusing the operation.

---

Testing / Audit Points

What to look for	Why it matters
Comparator uses a - b or similar arithmetic	Overflow can break transitivity
Service exposes a memory-limit control	Can force the insertion-sort path
Large element counts are accepted	Needed to reach the slow path
Array lives on the stack near pointers	OOB write becomes useful
Results are printed after sorting	Turns shifted pointers into leaks
Writable GOT + known library	Turns leaks into code execution

Quick audit questions:

1. Does any comparator perform arithmetic on the compared values?
2. Can an attacker influence resource limits that affect allocation inside the sorter?
3. Is the sorted array adjacent to interesting stack data?
4. Does the service print results in a way that would reveal corrupted pointers?
5. Would a single explicit comparison rewrite remove the entire class of bug?

If the answers are yes, yes, yes, yes, and yes, you found a ceremony that looks like sorting and behaves like a write primitive.

---

Common Myths

“Sorting is safe; it only rearranges data.”

No. Sorting rearranges data according to a comparison function. If that function lies, the algorithm will rearrange memory outside the array as well.

“Integer overflow in a comparator is just undefined behavior, not exploitable.”

Undefined behavior is exactly what lets the compiler and the runtime produce the non-transitive results that drive the walk. In practice the wrap-around is reliable enough to be scripted.

“Modern glibc fixed this.”

Some hardening has been added over the years, but many deployed systems still run versions whose insertion-sort path can be forced. Even when the path is gone, the same comparator bug can still produce incorrect results or other undefined behavior.

“You need a separate information leak.”

Not always. If the service already prints the sorted array, a carefully shifted pointer becomes a leak for free.

---

Final Thoughts

Sorting looks like one of the safest operations a program can perform. Give it a comparison function that lies about the order of large numbers and the algorithm will happily march off the end of the array for you. The resulting write is quiet, deterministic once you understand the overflow, and powerful enough to turn a simple service into a full compromise.

The program gives you a comparator. The sorter turns that comparator into a walk. The stack turns the walk into a leak. The GOT turns the leak into a shell.

The safest comparator is the one that never does arithmetic on the values it is comparing.

---

References

• C standard, section on integer overflow and undefined behavior
• glibc source for qsort / _quicksort (historical insertion-sort path)
• OWASP – Integer Overflow
• CERT C Secure Coding – INT32-C (Ensure that operations on signed integers do not result in overflow)
• CWE-190: Integer Overflow or Wraparound
• CWE-787: Out-of-bounds Write