《Neural Networks》：SemDiff: Binary Similarity Detection by Diffing Key-Semantics Graphs
编辑推荐：
二进制代码相似性检测（亦称二进制差分）对漏洞搜索、补丁生成与分析、恶意软件检测以及抄袭检测均具有重要意义。现有工作可分为基于机器学习的方法与基于程序分析的方法。基于机器学习的方法或从二进制代码中捕获语法、结构与语义特征以训练相似性检测模型，或借助自然语言处理（
二进制代码相似性检测（亦称二进制差分）对漏洞搜索、补丁生成与分析、恶意软件检测以及抄袭检测均具有重要意义。现有工作可分为基于机器学习的方法与基于程序分析的方法。基于机器学习的方法或从二进制代码中捕获语法、结构与语义特征以训练相似性检测模型，或借助自然语言处理（NLP）学习语义信息。尽管此类方法在理论上有效，但其性能高度依赖训练数据的构建质量。真实世界的二进制代码具有多样性，即同一段源代码因使用不同编译器（优化级别）而被编译为不同的二进制代码，因此难以构建具有代表性的训练数据集；若训练数据构建不佳，相应方法将受到显著影响。无监督学习从上下文指令中自动学习每条指令的嵌入，然而优化或不同编译器会改变函数中不可忽略的部分，使该类方法准确性下降。另一方面，基于机器学习的方法旨在通过预测汇编语法嵌入来保留语义信息，但这些嵌入可能无法准确保留精确语义。基于程序分析的方法通常执行静态/动态分析以从二进制代码中提取信息（如数据/控制依赖），随后基于特定定义的规则量化相似性。然而，静态函数级处理方法匹配基本块或指令序列，将函数内的每个基本块或每条指令定义为相似性量化的最小单元。考虑使用不同编译优化处理同一源代码的情形，通过块拆分各函数的基本块将变得完全不同，指令也可能因指令替换而不同。因此，块或指令比较并非处理二进制相似性比较的理想方法。为解决上述局限，研究人员提出并实现了一种新颖的语义感知方法SemDiff，用于在不考虑开发者所用编译器与优化级别的情况下比较任意二进制代码。具体而言，SemDiff由两个模块组成，即图生成（Graph Generation）与图差分（Graph Diffing）。在图生成中，SemDiff以一对二进制函数为输入，并通过以下步骤为每个函数构建关键语义图（key-semantics graph）：1）识别反映主要函数行为的关键指令（key instructions）（如调用函数、赋值）；2）应用符号执行（symbolic execution）提取每条指令的符号表达式及指令依赖关系；3）将符号表达式转换为自定义的关键表达式（key expressions），并使用有向边连接所有相关指令。在获得两个二进制函数的一对关键语义图后，图差分以这些图为输入，利用拓扑排序（topological sort）将两个图分别序列化为两个序列；随后对每个序列进行分词（tokenize），并执行基于局部敏感哈希（locality-sensitive hash，LSH）的比较，为每个关键语义图计算LSH值。若两个图的LSH值相似，则两个图（即二进制函数）被视为相似。需注意，关键指令是研究人员凭经验提出的有效启发式规则，旨在尽可能多地捕获代码语义。研究人员使用九个库评估了SemDiff的二进制相似性性能，包括openssl、libtomcrypt、coreutils、ImageMagick、libgmp、curl、sqlite3、zlib与Puttygen，并将SemDiff与五种最先进的工具进行比较，即Asm2Vec、Gemini、Palmtree、JTrans与UniASM。结果表明，无论源代码由同一编译器（不同优化级别）编译还是由不同编译器在同一优化级别下编译，SemDiff平均均优于基线工具。SemDiff的优越性能源于保持语义的关键表达式以及有效的基于LSH的图差分。此外，研究人员将SemDiff应用于漏洞检测与库版本检查，发现SemDiff可显著提高此类依赖相似性的检测性能。SemDiff与现有方法相比，采用简单规则、无需汇编语法嵌入且无需训练。研究人员总结了主要贡献：提出了一种新颖的语义感知二进制相似性检测方法，通过仅选择关键指令抽象二进制代码，并执行符号执行以提取指令关联以供进一步分析，该方?法通过提炼精确语义信息有效简化了二进制代码；提出了一种将指令摘要转换为图的方法，为实现准确比较，提出了一种基于LSH的方法将图转换为序列以进行最终相似性计算，该方法可应用于多种场景（如漏洞搜索与恶意软件检测），比较规则非常简单且无需训练；使用52个包中的2106个二进制文件（考虑各种编译器、编译选项、源代码版本与混淆）评估了SemDiff的性能，并与最先进的工具比较检测结果，结果表明SemDiff不仅在二进制相似性检测中表现优越，还可用于辅助其他需要二进制比较的工具，且SemDiff的准确率高于基于图神经网络（GNN）的方法；研究人员已将SemDiff工具与实验数据发布至其仓库以供评审者检查与测试，论文被接收后工具与数据集将公开发布。需注意，本文中的二进制代码指由编译器编译得到的可执行二进制文件（如ELF、PE文件）。
**研究背景与问题**：二进制代码相似性检测（又称二进制差分）在漏洞搜索、补丁生成与分析、恶意软件检测及抄袭检测中具有重要价值。现有方法主要分为基于机器学习与基于程序分析两类。基于机器学习的方法依赖训练数据质量，而真实世界二进制代码因编译器与优化级别差异呈现高度多样性，同一源代码经不同优化编译后语法与结构显著不同（如条件分支被sbb指令替换、基本块被合并或拆分），导致有监督方法对未见的优化或编译器失效，无监督方法在上下文非平凡部分改变时准确性下降；基于程序分析的方法以基本块或指令为最小相似性单元进行匹配，或采用最长公共子序列（LCS）进行序列对齐，但优化会改变块结构、指令及顺序，且LCS为NP-hard问题、依赖人工定义比较规则，难以扩展。为此，研究人员提出并实现语义感知方法SemDiff，旨在函数级比较任意二进制代码而不受编译器与优化级别限制。
**关键技术与方法**：SemDiff由两个模块构成。图生成模块对给定的每对二进制函数执行定制化符号执行，通过完全指令遍历（以深度优先搜索覆盖全部指令而非全部路径，避免路径爆炸）与轻量级循环处理（循环仅执行两次并将变化变量标记为循环迭代计数前缀ITER）提取关键指令的符号表达式；关键指令经人工检查分为调用行为、比较方式、间接分支与内存存储四类，符号表达式经表达式合成简化为关键表达式，并依据函数控制流连接形成关键语义图。图差分模块经拓扑排序将图序列化（先去除循环最后一条边并添加WHILE标记以消除环），对关键表达式分词（省略加号、保留括号并添加类型前缀），拼接全部令牌后用LSH哈希并采用Jaccard相似度量化函数相似性。实现包含12527行C++代码（作为IDA Pro插件）与2913行Python代码，使用msynth包合成表达式。数据集为9个开源项目（openssl-3.3.0、libtomcrypt-1.18.2、coreutils-8.32、ImageMagick-7.1.010、libgmp-6.2.1、curl-7.80、sqlite3-3.37.0、zlib-1.2.11、Puttygen-0.74）中13个程序的52个项目包，编译得到2106个二进制、逾416000个汇编函数；机器学习基线使用busybox、coreutils、libgmp与libMagickCore的7000个函数训练，并仅考虑至少含5个基本块的函数，以precision@1为指标。
**研究结果**：RQ1语义表示准确性：随机选取200个函数由三名程序员人工标注，SemDiff可正确翻译85%的指令，失败源于不支持部分x64指令变体（如movzx）及IDA Pro字符串解析错误。RQ2跨GCC优化级别检测：在O0、O1、O2、O3、Os下SemDiff平均精确率为73%（表5中为0.768、0.663、0.771），优于其他工具18%至74.9%的水平，且在NCD分数显示最不相似的二进制对（如O3与O0）上仍保持高性能。RQ3跨编译器检测：在GCC 12.4与CLANG 19.1.0同一优化级别下，SemDiff平均精确率达81%，部分情况下略逊于JTrans、UniASM与Asm2Vec。RQ4混淆选项检测：对CLANG 3.8.0 O0编译与OLLVM三种混淆（SUB、BCF、FLA）后的程序，SemDiff平均得分分别为0.925、0.779、0.714，大幅领先Gemini与Palmtree。RQ5跨版本检测：39对二进制中SemDiff在10个程序上最优、3个程序（coreutils、libgmp、sqlite3）次优，平均得分0.870居首。RQ6漏洞检测：40个CVE函数中SemDiff top-1得分为80.0%（32/40），高于Asm2Vec的75.0%、Gemini的52.5%与UniASM的42.5%，8个失败案例中6个仍排名前10。RQ7关键指令代码覆盖：经数据流分析，各优化级别下覆盖率约95%，未传播的指令多为函数序言（如push eax; push ebx）及MULX、MOVS、LSL等罕用指令。RQ8加权LSH：对逾10000个函数赋予不同权重后准确率基本不变（约77.8%至78.15%），对调用与间接分支加权时准确率略降，可能因符号执行已缓解低级地址差异。
**讨论与结论**：讨论部分指出，关键表达式准确性可通过支持更多罕用助记符、将硬编码优化知识（如call strlen与repne scasb等价）加入SemDiff来提升，并可解析GCC与Clang源码自动学习此类知识；图差分中LSH对各令牌与各关键指令类型赋予相同重要性，而长立即数匹配、参数更多的调用指令应具有更高权重，权重可借助充分训练数据由机器学习习得；继承性局限包括IDA Pro无法分析间接跳转目标、展开循环与折叠循环难以匹配（可通过固定次数展开或归并展开循环解决）以及msynth在时间效率与准确性上的潜在问题。结论部分译文：本文提出了SemDiff，一种用于二进制相似性检测的新颖语义方法。SemDiff包含两个模块：图生成与图差分。在图生成中，研究人员提出了对给定函数的完全指令遍历与轻量级循环处理以生成关键指令符号表达式，进一步将符号表达式转换为关键表达式并形成关键语义图；研究人员利用LSH对两个关键语义图进行差分。在评估中，研究人员将SemDiff与5种最先进的二进制相似性检测基线工具进行比较，结果表明SemDiff平均优于所有基线工具。虽然当前版本的SemDiff适用于基于x86的二进制文件，但在未来工作中可扩展以支持跨架构（如x86与ARM）的相似性检测，特别是将扩展图生成模块以从目标架构中提取并转换关键指令为关键表达式。
