Beyond Symbols: Introducing XEGMAP for Adaptive Binary Analysis and GMAP Discovery

Analyzing Commercial Off-The-Shelf (COTS) and stripped binary software has long been a foundational bottleneck in advanced reverse engineering. When debug symbols are stripped, function names vanish, data structures flatten into raw offsets, and traditional static analysis hits a wall. Compounding this is the notorious scalability wall of symbolic execution: state explosion, massive memory consumption, and constraint-solving overhead often prevent deep path exploration in complex binaries.

To addressing these limitations, Keith Makan from KMSEC’s latest research has officially been published as a pre-print: XEGMAP: Adaptive Symbolic Execution for Race Condition Detection in Binary Programs (available on Research Square). XEGMAP introduces a novel, adaptive approach to binary analysis designed specifically to operate without requiring source-level semantics, bridging the gap between symbolic exploration and real-world COTS binaries.

The Core Challenge: Navigating the Dark Without Symbols

When dealing with binaries in the wild—whether analyzing custom JNI libraries, proprietary firmware, or hardened application packages—analysts frequently encounter stripped codebases devoid of human-readable context.  Traditional symbolic execution engines attempt to explore every feasible execution path, but they quickly drown in state explosion. Without semantic landmarks, engines waste precious cycles exploring dead-end paths rather than focusing on high-value concurrency hotspots—specifically, locations where multiple execution threads contend for shared memory. To make sense of binaries lacking structural annotations, an analysis engine must be able to adapt dynamically, switching gears when semantic clues or memory interaction patterns emerge. This is part of the novelty of XEGMAPs design.

How XEGMAP Works: A Two-Phase Adaptive Strategy

XEGMAP overcomes problem of symbol availability, by implementing an adaptive, two-phase symbolic execution framework built on top of the angr binary analysis platform:

1. NEGMAP (Naive Execution Phase): In the absence of symbols, the framework initiates a baseline exploration mode designed to monitor for available semantic markers or semantic-like patterns. Rather than crashing against the state explosion wall, it casts a wide net to map out basic block trajectories.
2. DEGMAP (Directed Phase): Once semantic guidance is detected or triggered, the engine transitions into a directed phase. DEGMAP dynamically steers state exploration toward areas of high memory interaction, focusing computational resources where they matter most.

Pinpointing Global Memory Access Points (GMAPs)

At the heart of XEGMAP’s directed phase is its ability to prioritize the discovery of Globally Accessed Memory Points (GMAPs)—locations in the binary where multiple threads contend for shared memory. To determine whether these interactions are genuinely hazardous, XEGMAP applies a hybrid lock-set and happens-before analysis directly at the binary level. This enables the framework to surface subtle, complex concurrency flaws and race conditions in environments where traditional stochastic fuzzers or loop-focused engines typically fail.

Performance and Results

Empirical evaluations detailed in the pre-print demonstrate significant improvements over existing framework defaults:

• Massive Code Coverage: XEGMAP consistently achieves high block coverage, scaling up to 36,755 code blocks on complex binary samples—metrics traditionally associated with state-of-the-art fuzzing engines rather than pure symbolic execution.
• Targeted Discovery: The framework successfully identified up to 360 distinct GMAPs in complex COTS environments without requiring access to source code or symbol tables.
• Robust Concurrency Detection: By intelligently balancing naive discovery with targeted state direction, XEGMAP reliably uncovers thread-safety violations buried deep within compiled binaries

Moving Forward

At KMSEC, our research directly feeds into our engineering philosophy: moving beyond checkbox auditing through bespoke tooling and rigorous, academically grounded research. XEGMAP represents a major step forward in automating the analysis of opaque, stripped binaries—helping security engineers make sense of complex codebases in the wild.

You can read the full pre-print paper over on Research Square. Stay tuned to the blog as we continue to unpack the underlying mechanics of our automated tooling, binary reverse engineering workflows, and advanced memory analysis techniques.