PEM: Representing Binary Program Semantics for Similarity Analysis via a Probabilistic Execution Model

Xiangzhe Xu, Zhou Xuan, Shiwei Feng, Siyuan Cheng, Yapeng Ye, Qingkai Shi, Guanhong Tao, Le Yu, Zhuo Zhang, Xiangyu Zhang

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.

Motivation examples showing how compiler optimizations (cat@O3 vs cat@O0) and different source codes (cat vs touch) create deceptive structural similarities and differences.

Existing approaches typically fall into two categories:

  1. Static Analysis: These methods examine code structure, such as Control-Flow Graphs (CFGs). As shown in the motivation examples, optimizations like those in cat@O3 can create 144 blocks and 218 edges compared to cat@O0's 83 blocks, rendering structural comparisons unreliable.
  2. 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

Abstract

Binary similarity analysis determines if two binary executables are from the same source program. Existing techniques leverage static and dynamic program features and may utilize advanced Deep Learning techniques. Although they have demonstrated great potential, the community believes that a more effective representation of program semantics can further improve similarity analysis. In this paper, we propose a new method to represent binary program semantics. It is based on a novel probabilistic execution engine that can effectively sample the input space and the program path space of subject binaries. More importantly, it ensures that the collected samples are comparable across binaries, addressing the substantial variations of input specifications. Our evaluation on 9 real-world projects with 35k functions, and comparison with 6 state-of-the-art techniques show that PEM can achieve a precision of 96% with common settings, outperforming the baselines by 10-20%.
BibTeX
@inproceedings{xu2023pem,
  author = {Xiangzhe Xu and Zhou Xuan and Shiwei Feng and Siyuan Cheng and Yapeng Ye and Qingkai Shi and Guanhong Tao and Le Yu and Zhuo Zhang and Xiangyu Zhang},
  title = {{PEM: Representing Binary Program Semantics for Similarity Analysis via a Probabilistic Execution Model}},
  booktitle = {ESEC/SIGSOFT FSE},
  year = {2023},
  doi = {10.1145/3611643.3616301},
}
Figure