Introduction
Binary similarity analysis—the process of determining if two compiled code snippets originate from the same source—is fundamental to modern security workflows, including malware detection, vulnerability research, and software plagiarism audits. However, the task is increasingly complicated by aggressive compiler optimizations that radically transform code structure. PEM (Probabilistic Execution Model) addresses this by intelligently sampling execution paths to capture the underlying semantics of a program, achieving high precision where traditional static and dynamic methods fail.
The Challenge of Binary Similarity
Compilers can transform code through function inlining, loop unrolling, and instruction scheduling, making the same source code look entirely different in its binary form. Conversely, different source functions can sometimes result in similar-looking control-flow structures.
Existing approaches typically fall into two categories:
- Static Analysis: These methods examine code structure, such as Control-Flow Graphs (CFGs). As shown in the motivation examples, optimizations like those in
cat@O3can create 144 blocks and 218 edges compared tocat@O0's 83 blocks, rendering structural comparisons unreliable. - Dynamic Analysis: These methods observe code behavior during execution. While more resilient to structural changes, they suffer from the "input specification" problem: generating valid inputs for arbitrary binary functions is difficult, and inconsistent input formats between versions make behavior comparison challenging.
The PEM Framework
PEM moves beyond traditional "forced execution" by employing a Probabilistic Execution Model. Its architecture is built on four core components:
- Input Agnosticism: Rather than attempting to find "valid" inputs, PEM feeds a consistent sequence of random values to all input variables. This ensures a uniform starting state across different binaries regardless of intended types.
- Path Sampling via Dynamic Selectivity: To explore meaningful execution paths, PEM uses "Dynamic Selectivity"—a measure of how close a branch is to its decision boundary. The researchers found that predicates with extremely high or low selectivity are the most stable across optimizations. PEM uses a U-shaped Beta-distribution to prioritize flipping these "extreme" predicates, effectively sampling equivalent paths in disparate binaries.
- Probabilistic Memory Model (PMM): Flipping predicates often leads to invalid memory accesses. PEM’s PMM maps these invalid addresses to a random but consistent memory region, allowing execution to continue while ensuring that equivalent programs produce equivalent sequences of observable values (I/O, memory accesses, and jump targets).
- Semantic Signatures: The resulting distributions of observable values serve as a unique "fingerprint" for the function, compared using set-similarity metrics like the Jaccard index.
Key Insights: The Stability of Extremes
A core discovery of the PEM research is that while compilers change many syntactic elements, they rarely alter the relative ranking of predicates based on their selectivity at the extremes. By targeting these stable points, PEM focuses on what the code does (semantics) rather than what it looks like (syntax). This makes it robust against aggressive optimizations and prevents the "overfitting" common in deep learning models that rely on specific instruction sequences.
Experimental Results
The researchers evaluated PEM against state-of-the-art tools using both controlled datasets (Coreutils-8.32) and large-scale real-world datasets (35,000 functions from projects like OpenSSL and SQLite).
- Superior Precision: PEM achieved 96% precision (PR@1) on Coreutils, significantly outperforming previous dynamic tools like IMF (76%) and BLEX (69%).
- Resilience to Noise: In scenarios where a true match is hidden among 1,000 false candidates, PEM's performance remained stable, while deep learning models like SAFE and Trex saw precision drop below 20%.
- Real-World Impact: In a study of eight "1-day" vulnerabilities, PEM correctly identified the vulnerable function as the top match in 7 out of 8 cases, whereas baseline tools only succeeded in 2 cases.
- Efficiency: PEM is practical for large-scale use, analyzing over 3 functions per second and performing 2,000 comparisons per second.
Limitations and Future Work
Despite its success, PEM faces challenges with functions that rely heavily on external library calls or complex floating-point instructions. Additionally, extremely complex functions with millions of potential paths still pose a challenge for full path coverage. Future work will focus on better modeling of external library behaviors to improve precision for "thin" wrapper functions.
Summary updated