SemDiff: Binary Similarity Detection by Diffing Key-Semantics Graphs
summary
The gist
Binary similarity detection is addressed by SemDiff, which proposes a novel semantic-aware approach to compare arbitrary binary codes without considering specific compilers or optimization levels.
This episode discusses
- SemDiff: Binary Similarity Detection by Diffing Key-Semantics Graphs · Paper Radio
- Automated Deobfuscation of Android Native Binary Code
- SAFE: Self-Attentive Function Embeddings for Binary Similarity
The paper
SemDiff: Binary Similarity Detection by Diffing Key-Semantics Graphs · Read on arXiv
Zian Liu, Zhi Zhang, Siqi Ma, Dongxi Liu, Jun Zhang, Chao Chen, Shigang Liu, Muhammad Ejaz Ahmed, Yang Xiang
Swinburne University of Technology Department 61 CSIRO University of Western Australia University of New South Wales Data 61 CSIRO Royal Melbourne Institution of Technology
Binary similarity detection is a critical technique that has been applied in many real-world scenarios where source code is not available, e.g., bug search, malware analysis, and code plagiarism detection. Existing works are ineffective in detecting similar binaries in cases where different compiling optimizations, compilers, source code versions, or obfuscation are deployed. We observe that all the cases do not change a binary's key code behaviors although they significantly modify its syntax and structure. With this key observation, we extract a set of key instructions from a binary to capture its key code behaviors. By detecting the similarity between two binaries' key instructions, we can address well the ineffectiveness limitation of existing works. Specifically, we translate each extracted key instruction into a self-defined key expression, generating a key-semantics graph based on the binary's control flow. Each node in the key-semantics graph denotes a key instruction, and the node attribute is the key expression. To quantify the similarity between two given key-semantics graphs, we first serialize each graph into a sequence of key expressions by topological sort. Then, we tokenize and concatenate key expressions to generate token lists. We calculate the locality-sensitive hash value for all token lists and quantify their similarity. %We implement a prototype, called SemDiff, consisting of two modules: graph generation and graph diffing. The first module generates a pair of key-semantics graphs and the second module diffs the graphs. Our evaluation results show that overall, SemDiff outperforms state-of-the-art tools when detecting the similarity of binaries generated from different optimization levels, compilers, and obfuscations. SemDiff is also effective for library version search and finding similar vulnerabilities in firmware.
Transcript
Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.
Nadia: We're looking at the paper: "SemDiff: Binary Similarity Detection by Diffing Key-Semantics Graphs".
Elias: Here's the gist of the paper. Binary similarity detection is addressed by SemDiff, which proposes a novel semantic-aware approach to compare arbitrary binary codes without considering specific compilers or optimization levels.
Nadia: Core Problem and Motivation Binary code similarity detection is critical for applications like bug search, malware analysis, and code plagiarism detection.
Elias: Existing methods struggle when binaries are compiled with different optimizations or compilers because they modify syntax and structure significantly.
Nadia: Program analysis approaches often fail because basic blocks change drastically due to optimization, making instruction or block comparison ineffective.
Paper summary: Nadia: So we're looking at this paper called SemDiff: Binary Similarity Detection by Diffing Key-Semantics Graphs. Essentially, it tackles the problem of finding similar binary code even when compilers or optimization levels change things a lot and you can't just compare the raw syntax or structure <ref:2308.01463#pg1>.
Elias: Exactly. The paper points out that while different compilers or optimizations can drastically alter the syntax and structure of a binary, they don't always change what the key code behaviors are doing <ref:2308.01463#pg2>. So, the thesis is that we need to capture those core behaviors rather than just looking at instruction sequences.
Priya: But how do you actually isolate these key behaviors without getting bogged down in overly complex intermediate representations that don't simplify things <ref:2308.01463#pg2>? I mean, when you're dealing with binaries, the details matter a lot for finding real vulnerabilities.
Nadia: That’s where SemDiff comes in by extracting a set of key instructions that reflect major function behaviors, like function invocations or value assignments <ref:2308.01463#pg2>. Then, they use symbolic execution to pull out symbolic expressions for each instruction and its dependencies <ref:2308.01463#pg2>.
Elias: Once you have those symbolic expressions, the paper translates them into self-defined key expressions and connects all the correlated instructions using directed edges to form what they call a key-semantics graph <ref:2308.01463#pg2>. Each node in that graph represents a key instruction, and the attribute of that node is its corresponding key expression.
Priya: So, you’re essentially building a semantic map of the function's control flow based on what the instructions are actually doing at a high level <ref:2308.01463#pg2>? I’m wondering if this graph structure helps you handle those differences between binaries?
Nadia: It does, because they then serialize each graph into a sequence of key expressions by topological sort <ref:2308.01463#pg2>. They tokenize and concatenate these key expressions to generate token lists, and then they calculate the locality-sensitive hash value for all those token lists to quantify similarity <ref:2308.01463#pg2>.
Paper summary: Elias: That LSH comparison is how they measure the similarity between two graphs by looking at those token lists <ref:2308.01463#pg2>. It seems like a way to get around the problem of comparing instructions directly when their syntax is different.
Priya: What are some specific examples of these key expressions? I mean, if I wanted to know what’s in this paper, you need concrete examples of how they define what a "key instruction" actually is <ref:2308.01463#pg3>?
Nadia: They define four types of key instructions: calling behavior, comparing manner, indirect branch, and memory store <ref:2308.01463#pg3>. For example, for calling behavior, they use something like RET FuncAddr(exp1, expn) <ref:2308.01463#pg3>. This process involves symbolically executing the function to derive symbolic expressions for operands first <ref:2308.01463#pg3>.
Elias: So, the whole point is that they are creating a self-defined key expression for every key instruction based on what it's doing, not just what its machine code looks like <ref:2308.01463#pg2>. This allows them to compare the semantics even if the assembly instructions are totally different.
Priya: When you talk about that symbolic execution, is that process computationally expensive? And what are the assumptions they make about binaries for this approach to work <ref:2308.01463#pg3>?
Nadia: Well, it’s a bit heavy because of the symbolic execution part <ref:2308.01463#pg2>. But they make three main assumptions that are practical in the real world <ref:2308.01463#pg3>. One of those is that binaries are stripped with certain information, which is a big assumption for analysis <ref:2308.01463#pg3>.
Elias: They also make assumptions based on previous work, like what's practical in the real world <ref:2308.01463#pg2>. For instance, they assume that similar binaries will have similar key code behaviors even if they come from different compilers or optimization levels <ref:2308.01463#pg1>.
Priya: So what does this mean for us on the outside? If a security researcher is looking for malware variants or checking library versions, how does this method actually compare to existing tools like Bindiff or Palmtree <ref:2308.01463#pg5>?
Nadia: The evaluation shows that SemDiff outperforms state-of-the-art tools when detecting the similarity of binaries generated from different optimization levels, compilers, and obfuscations <ref:2308.01463#pg5>. It’s also effective for library version search and finding similar vulnerabilities in firmware <ref:2308.01463#pg5>.
Paper summary: Elias: The results they show are pretty strong when you look at the specific comparisons, like ranking a target vulnerable function at the first place in fifty-five point six percent of cases, which is better than Asm2vec's top-one score of fifty percent <ref:2308.01463#pg5>.
Priya: That’s a specific number, so that gives some weight to the claim that it handles these variations well <ref:2308.01463#pg5>. But I still wonder about those limitations they mentioned, especially with indirect jump targets and matching folded loops <ref:2308.01463#pg6>?
Nadia: That’s right, they admit that one limitation is the reliance on IDA Pro for indirect jump targets and difficulties in precisely matching unfolded and folded loops <ref:2308.01463#pg6>. They also suggest adding hardcoded optimization knowledge or using machine learning to weight tokens for graph diffing as future directions <ref:2308.01463#pg6>.
Elias: It sounds like they acknowledge that the method isn't perfect and they have a roadmap for improving the accuracy with more data or better heuristics <ref:2308.01463#pg6>. This paper, SemDiff: Binary Similarity Detection by Diffing Key-Semantics Graphs, proposes this semantic method using graph generation and LSH-based graph diffing to abstract binary code by selecting key instructions and using symbolic execution to preserve essential semantic information <ref:2308.01463#pg5>.
Priya: So for someone just listening, it means that instead of comparing the raw machine code which gets messy fast, you can compare the high-level functional intent of the code regardless of how it was compiled <ref:2308.01463#pg5>.
Nadia: So to wrap up on SemDiff: Binary Similarity Detection by Diffing Key-Semantics Graphs, it’s a method that abstracts binary code by picking key instructions and using symbolic execution to keep the essential semantic information intact <ref:2308.01463#pg5>.
Elias: It successfully uses graph generation followed by LSH-based graph diffing to quantify similarity between two functions <ref:2308.01463#pg5>. This approach has been shown to outperform all baseline tools across different optimization levels, compilers, and obfuscations <ref:2308.01463#pg5>.
Priya: For the person listening, it means you can use this tool to find similar versions of library binaries or detect similar vulnerabilities in firmware without worrying too much about the specific compiler details <ref:2308.01463#pg5>.
Conclusion: Nadia: So, we've been looking at this paper called SemDiff, which is about using key-semantics graphs to find similar binary code without caring about the compiler or the optimization level it came from.
Elias: Yeah, and the authors are talking about how they extract these key instructions and use them to build a graph that captures what the code actually does at a semantic level.
Nadia: It seems like their main point is that you don't need to worry about every single instruction when comparing binaries; you just need to focus on those core behaviors.
Elias: Exactly, they’re showing how they can compare two different versions of code by looking at these semantic representations instead of the raw machine code structure.
Nadia: The results suggest that this method works well when comparing binaries that were built with totally different compilers or optimization levels.
Elias: It does show promise for finding similar versions of library binaries and even spotting similar vulnerabilities in firmware, which is interesting for security folks.
Nadia: So, it’s like they’ve created a way to see the functional intent of a piece of code across different implementations.
Elias: Right, it abstracts away the syntactic noise and focuses on what the instructions are actually achieving.
Nadia: It makes sense if you think about how much effort it takes to manually compare assembly code across those huge variations.
Elias: That’s the practical angle, I guess; they’re trying to solve a problem where manual comparison just doesn't scale anymore.
Nadia: But the authors did mention some sticking points, like relying on specific tools for indirect jump targets and having trouble perfectly matching folded loops.
Elias: Yeah, so it’s not a perfect solution yet, and they’re looking at ways to improve that precision with more data or maybe some machine learning to weigh the tokens.
Nadia: So while it's a solid step forward for security analysis, we still need to see how robust it is when you hit those trickier programming constructs.
Elias: That's where the next paper might come in; we’ll have to check if those future improvements actually materialize in the next iteration.
More episodes
- 2608.27496-ROPE: Routed Origin Policy Enforcement against Indirect Prompt Injection
- Daily Summary for 2026-11-19
- 2607.07085-Is Randomness Necessary for Adaptive Data Analysis?
- The day in conversation for 2026-11-19
- Daily Summary for 2026-11-19
- 2609.10601-Threshold Choice, Not Sample Size, Bounds Trustless Verification of Nondeterministic Compound AI Workflows
- 2610.38786-Adversarial Process Disturbances at a Deployable Alarm Budget: Detector Evaluation on a Simulator and a Real Plant
- 2511.08660-Binary and Multiclass Cyberattack Classification on GeNIS Dataset
- 2604.27302-Static Attribution of Android Residential Proxy Malware Using Graph Kernels
- Daily Summary for 2026-11-18