> For the complete documentation index, see [llms.txt](https://dizzzzy.gitbook.io/notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dizzzzy.gitbook.io/notebook/vulnerability-detection/bcsd/bcsd1-awesome-binary-similarity.md).

# BCSD1-Awesome-Binary-Similarity

现有研究方法调研（仅关注支持跨架构的研究）

## CI-Detector,2024,CCF-A

{% embed url="<https://github.com/island255/cross-inlining_binary_function_similarity>" %}

{% embed url="<https://dl.acm.org/doi/10.1145/3597503.3639080>" %}

提出了一个基于模式的模型 CI-Detector，用于交叉内联匹配。CI-Detector 使用**带属性 的CFG（attributed CFG）** 来表示二元函数的语义，使用 **GNN** 将二元函数嵌入到向量中。CI-Detector 分别针对这三种交叉内联模式训练一个模型。文章使用的数据集跨架构（作者构建一个交叉内联数据集，使用 9 个编译器，4 种优化器，将 51 个项目编译到 6 个架构——2 个内联标志中，从而得到两个数据集，每个数据集都有 216 种组合）文章核心关注的是对交叉内联匹配的相似性检测。

## HermesSim,2024,CCF-A

{% embed url="<https://github.com/NSSL-SJTU/HermesSim>" %}

{% embed url="<https://www.usenix.org/conference/usenixsecurity24/presentation/he-haojie>" %}

之前的大多数BCSD研究方式可以归纳为两大流派：

* 基于指令流的（instruction streams）：使用NLP对二进制代码进行分析
* 基于图表示的，如基于控制流图&#x7684;***（control flow graphs ，CFGs）***&#x548C;基于数据流图的（data flow graphs，DFGs）：使用图机器学习进行分析

作者认为基于指令流的方法将二进制代码视为自然语言，忽略了明确定义的语义结构。基于 CFG 的方法仅利用控制流结构，而忽略了代码的其他基本方面。

文章作者的见解是与自然语言不同，二进制代码具有明确定义的语义结构，包括指令内结构、指令间关系（例如，def-use、分支）和隐式约定（例如调用约定）。所以作者尝试构建一种新的&#x56FE;***（semantics-oriented graph ，SOG）***&#x6765;表达二进制程序完整语义结构，递交给深度神经网络。此外提出了一个轻量级的多头 softmax 聚合器，以有效、高效地融合二进制代码的多个方面。

<figure><img src="https://3730186196-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FrCG00nTO3O6DVWijfDnr%2Fuploads%2FpSTPogugZUnsRtaAWP5E%2Fimage.png?alt=media&amp;token=4210be9c-e40f-45fe-9051-314ee56f652a" alt=""><figcaption></figcaption></figure>

<figure><img src="https://3730186196-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FrCG00nTO3O6DVWijfDnr%2Fuploads%2FvCsW98OPcEZFgrVpXTTp%2Fimage.png?alt=media&amp;token=25a761e6-2418-4ccb-a232-b3503eb2b14e" alt=""><figcaption></figcaption></figure>

文章举例说明了SOG设计的思路，以基于NLP的方式缺陷为例，这种方式输入token包含两个方面的信息： token content 和 position in the sequence，即内容信息和序列中的位置，假设对一段gadget进行三个简单的语义等效转换：

* Trans.1，此代码片段的前两个指令可以交换而不修改代码语义。但是，这种转换会导致基于 NLP 的模型生成的嵌入集发生变化。例如，现在将标记 LOAD 的标记嵌入添加到索引 5 的位置嵌入（如图 2b 所示），而它最初添加的是索引 2 的位置嵌入。因此，模型需要学习某些指令的顺序可以在不修改语义的情况下进行调整，而其他指令则不能。
* Trans.2，整个代码片段被放置在序列中的不同位置，例如，由于在序列开头插入了一些虚拟指令
* Trans.3，所有对寄存器 r0 的使用都被之前未使用的寄存器 r2 所取代。模型需要学习的是，选择使用哪种寄存器与语义无关。

<figure><img src="https://3730186196-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FrCG00nTO3O6DVWijfDnr%2Fuploads%2Fuek7BFb3kqyUacaKTj3g%2Fimage.png?alt=media&amp;token=c2ba3af8-465f-4a57-8065-1c4853b9640d" alt=""><figcaption></figcaption></figure>

所以作者提出**通过寄存器的数据流**是代码语义不可或缺的一部分，这个例子也说明了**基于NLP的方式需要大量的样本模型才能有效的学习**：如果仅给出图 2a 和图 2c 中的代码片段，模型可能会学习到位置 0 和位置 k 处给定的代码片段在语义上是等价的，而当给出另一个代码片段或将代码片段放在另一个位置时，模型则不必学习类似的规则是否成立。此外，它还需要额外的网络参数和层数。总的来说，学习这些额外的语义使得基于 NLP 的方法更加昂贵，也更难以推广

## Gemini，2017，CCF-A

原文：Neural Network-based Graph Embedding for Cross-Platform Binary Code Similarity Detection

{% hint style="info" %}
在2017年取得了SOTA，目前已相对落后，**常用于baseline对比**
{% endhint %}

{% embed url="<https://dl.acm.org/doi/10.1145/3133956.3134018>" %}

**Struct2vec+孪生神经网络**

文中使用的图是**属性控制流图(ACFG)，**&#x5BF9;二进制函数的控制流图(Control-Flow Graph,CFG)提出了一种新的基于神经网络图嵌入方法，通过衡量 embedding 之间的距离来计算两个函数的相似度

基于 graph embedding network 把图转化为 embedding。之前的 graph embedding networks 被提出来用于分类和回归任务，但本文考虑的场景是相似度，因此对 graph embedding networks 采用了 ***Siamese network（孪生网络）***&#x53EF;以自然的实现让两个相似函数的 embedding 也相似的目标。这整个网络可以端到端的训练以实现相似度检测。&#x20;

{% embed url="<https://blog.csdn.net/qq_42734492/article/details/131445675>" %}

**常见的距离计算方式**

* 欧式距离；
* 余弦相似度（归一化为1）；
* 汉明距离；
* 曼哈顿距离（折线欧式距离，高维中不一定路径对短）；
* 切比雪夫距离（两个向量在任意坐标维度上的最大差值，棋盘距离，不常用）；
* 闵氏距离（Minkowski）
* 雅卡尔指数（Jaccard Index) $$D(x,y)=(\sum^n\_{i=1}|x\_i-y\_i|^p)^{\frac{1}{p}}$$
  * p=1：曼哈顿距离
  * p=2：欧氏距离
  * p=∞：切比雪夫距离
* 半正矢（Haversine）半正矢距离是指球面上的两点在给定经纬度条件下的距离。半正矢距离不可能有直线，因为这里的假设是两个点都在一个球面上。
* Sørensen-Dice 系数是度量样本集的相似性和多样性的,夸大了很少或没有真值的集合的重要性;\
  $$f(x) = x \* e^{2 pi i \xi x}$$$$D(x,y)=\frac{2|x\cap y|}{|x|+|y|}$$

## CLAP，2024，CCF-A

原文：CLAP: Learning Transferable Binary Code Representations with Natural Language Supervision

{% embed url="<https://arxiv.org/pdf/2402.16928>" %}

文章主要想解决的问题：（1）目前方法在应用于新的数据集或任务时通常需要大量数据进行重新训练，导致在训练样本稀疏的场景下性能不佳（few-shot和zero-shot问题）。（2）现有的汇编代码编码方案经常导致关键信息丢失，例如调用指令的参数、字符串和变量名，作者认为大多数方法倾向于使用特殊词汇标记来规范化字符文本、常量数值和外部函数，这**无意中导致遗漏了重要细节**。

引入了一种新颖的二进制代码表示学习主干网络，它结合了 WordPiece 标记化（例如，Llama \[36] 使用）和跳跃感知嵌入（例如，jTrans \[39] 使用）设计

文章训练出来的模型效果是能给出二进制代码的自然语言描述：

```python
with open(bubble_output) as fp:
    asm = json.load(fp)

prompts = [
    "This is a function related to bubble sort ",
    "This is a function related to selection sort",
    "This is a function related to insertion sort",
    "This is a function related to merge sort",
    "This is a function related to quick sort",
    "This is a function related to radix sort",
    "This is a function related to shell sort",
    "This is a function related to counting sort",
    "This is a function related to bucket sort",
    "This is a function related to heap sort",
]

with torch.no_grad():
    asm_input = asm_tokenizer([asm], padding=True, pad_to_multiple_of=8, return_tensors="pt", verbose=False)
    asm_input = asm_input.to(device)
    asm_embedding = asm_encoder(**asm_input)

with torch.no_grad():
    text_input = text_tokenizer(prompts, padding=True, truncation=True, return_tensors='pt')
    text_input = text_input.to(device)
    text_embeddings = text_encoder(**text_input)

logits = torch.einsum("nc,ck->nk", [asm_embedding, text_embeddings.T])
_, preds = torch.max(logits, dim=1)
preds = torch.softmax(logits / 0.07, dim=1).squeeze(0).tolist()

print("bubblesort zeroshot:")
for i in range(len(prompts)):
    print(f"Probability: {round(preds[i]*100, 3)}%, Text: {prompts[i]}")
```

Output：

```
bubblesort zeroshot:
Probability: 17.954%, Text: This is a function related to bubble sort 
Probability: 6.919%, Text: This is a function related to selection sort
Probability: 11.567%, Text: This is a function related to insertion sort
Probability: 5.261%, Text: This is a function related to merge sort
Probability: 9.474%, Text: This is a function related to quick sort
Probability: 12.454%, Text: This is a function related to radix sort
Probability: 12.879%, Text: This is a function related to shell sort
Probability: 9.756%, Text: This is a function related to counting sort
Probability: 9.351%, Text: This is a function related to bucket sort
Probability: 4.385%, Text: This is a function related to heap sort
```

<figure><img src="https://3730186196-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FrCG00nTO3O6DVWijfDnr%2Fuploads%2F8NlcxFkDRlw47JCBIioy%2Fimage.png?alt=media&amp;token=63f03974-ecda-479a-b74f-e6f71682251a" alt=""><figcaption></figcaption></figure>

* 给每条指令都做了独立的embedding，保证模型能够学习区分不同指令。基于WordPiece在数据集上训练了一个专门的Tokenizer。这里有一个创新点，之前的工作都是直接将地址标准化为相同标记，这里将每一个地址rebase，但保留了跳转指令的offset，这是为了保证模型能够理解指令引起的控制流变化。每个token会被转换为三个embedding（token, position, instruction），将三个embedding的和作为输出。
  \*

  ```
  <figure><img src="/files/o3HesQz7iJmPrck5H36Z" alt=""><figcaption></figcaption></figure>
  ```
* encoder：用一个对数损失函数对掩码语言模型（MLM）和跳转目标预测（JTP）进行训练
* 对齐自然语言：用于预测汇编代码和文本解释的对应关系。这里使用了InfoNCE Loss来实现。InfoNCE Loss公式：
  \*

  ```
  <figure><img src="/files/ps5qRDjarAmN2xWB6riE" alt=""><figcaption></figcaption></figure>
  ```

## CEBin，2024，CCF-A

原文：CEBin: A Cost-Effective Framework for Large-Scale Binary Code Similarity Detection

{% embed url="<https://arxiv.org/pdf/2402.18818>" %}

CEBin 框架分为三个主要阶段：预训练、微调和推理，如图 [2](https://arxiv.org/html/2402.18818v1#S3.F2) 所示。 在预训练阶段，我们利用综合数据集来训练针对表示二进制代码而优化的语言模型。 在微调过程中，这种预训练的语言模型被进一步细化以产生两个不同的模型：嵌入模型和比较模型。 这一阶段的一个显着增强是可重用嵌入缓存机制（RECM）的集成，旨在引入大量负样本来微调嵌入模型。 在最后的推理阶段，我们使用嵌入模型来检索最接近查询函数的前 K 个候选函数。 随后，比较模型有助于精确的最终选择

<figure><img src="https://3730186196-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FrCG00nTO3O6DVWijfDnr%2Fuploads%2FWz70s4aiqjVU8lgKpdgy%2Fimage.png?alt=media&amp;token=f73bdf43-44d3-4ea9-bb12-cf3ebe2fdb0f" alt=""><figcaption></figcaption></figure>

## FASER，2023

原文：FASER: Binary Code Similarity Search through the use of Intermediate Representations

原文：Improving Binary Code Similarity Transformer Models by Semantics-Driven Instruction Deemphasis

{% embed url="<https://dl.acm.org/doi/pdf/10.1145/3597926.3598121>" %}

## DiEmph，2023，CCF-A