Binvariants: Enhancing Fuzzing of Closed-Source Binary Executables via Register-Level Likely Invariants

Closed-source software is ubiquitous in everyday computing, underscoring the need for robust security vetting of “binary-only” executable code. While code-coverage-guided fuzzing has long proven effective at unearthing software bugs, fuzzing in open-source contexts has since evolved beyond code coverage as its principal guiding metric. State-of-the-art fuzzing advancements demonstrate that likely data invariants—data-level properties which, if violated, expose unusual and often bug-preceding program states—significantly widen fuzzing’s reach to defects ordinarily occluded by coverage-only testing. Unfortunately, current invariant-guided fuzzing universally depends on source-level abstractions, rendering it unportable to binary-only targets. Consequently, closed-source software fuzzing—and more importantly, binary-only bug discovery—remain stalled at now-obsolete coverage-only techniques, even as open-source software fuzzing advances well past them.

To bridge this longstanding gap, this paper introduces register-level likely invariants: the first technique to integrate likely data invariants within binary-only fuzzing. In contrast to contemporary source-level data invariant mining, our approach operates directly on CPU registers, capturing the low-level program states that themselves encode higher-level data relationships. From these low-level states, we automatically derive likely data invariants and expose their violations as fuzzer-observable signals via runtime instrumentation, steering fuzzing into states often unreachable by code coverage alone. In doing so, our approach surfaces qualitatively different states, complementing traditional coverage-guided fuzzing with distinct bug-finding capabilities.

We implement our approach as a prototype, Binvariants, and evaluate its performance across 25 benchmark applications: 7 closed-source, as well as 18 open-source programs compiled as binary-only executables. Our results show that, compared to driving binary fuzzing solely via code coverage, register-level likely invariants helps fuzzing trigger over 27× more unique invariant violations beyond coverage-only fuzzing, thereby exercising a mean 52% more distinct code regions. Moreover, our approach uncovers 143 total bugs versus coverage-only fuzzing’s 137—including 20 missed by code coverage—demonstrating how register-level likely invariants extends binary-only fuzzing’s reach into execution states beyond what coverage alone is capable of.