LmPa: Improving Decompilation by Synergy of Large Language Model and Program Analysis

Xiangzhe Xu Purdue University West Lafayette, USA xu1415@purdue.edu

Zhuo Zhang Purdue University West Lafayette, USA zhan3299@purdue.edu

Shiwei Feng Purdue University West Lafayette, USA feng292@purdue.edu

Yapeng Ye Purdue University West Lafayette, USA ye203@purdue.edu

Zian Su Purdue University West Lafayette, USA su284@purdue.edu

Nan Jiang Purdue University West Lafayette, USA jiang719@purdue.edu

Siyuan Cheng Purdue University West Lafayette, USA cheng535@purdue.edu

Lin Tan Purdue University West Lafayette, USA lintan@purdue.edu

Xiangyu Zhang Purdue University West Lafayette, USA xyzhang@cs.purdue.edu

引用

Xu X, Zhang Z, Feng S, Ye Y, Su Z, Jiang N, Cheng S, Tan L, Zhang X. LmPa: Improving Decompilation by Synergy of Large Language Model and Program Analysis[J].

论文：https://arxiv.org/abs/2306.02546

摘要

这篇文章介绍了一种利用大型语言模型和程序分析协同来改进反编译技术的新方法。该技术针对反编译中的变量名恢复这一关键问题，提出利用大型语言模型生成变量名，并通过程序分析来传播这些生成的名字，为后续的查询提供上下文信息。实验结果显示，该方法恢复的75%的变量名被认为是高质量的，并且与当前最先进的技术相比，精确率和召回率分别提高了16.5%和20.23%。这种方法在反编译领域具有很高的应用价值。

1 引言

反编译技术在众多安全领域和软件工程任务中扮演着关键角色。例如，在恶意软件分析中，反编译通常是首步，涉及人工分析师研究恶意代码以理解其行为。它在二进制漏洞分析中至关重要，分析师需识别可执行文件中的关键缺陷。此外，软件供应链分析和代码重用（如移植或加固遗留执行文件的需求）也依赖反编译技术。反编译工具如IDA和Ghidra的广泛使用进一步证明了其重要性，特别是在安全威胁分析等方面。

然而，根据该文的实验，最先进的名字恢复方法DIRTY仅实现了17.3%的准确率和10.9%的召回率。在反编译中，关键词恢复可以说是最有价值的步骤之一，因为像标识符名称这样的自然语言工具有助于开发人员有效地理解代码。然而，与少数其他任务相比，关键词恢复往往更具挑战性。除了由上述编译转换引起的问题外，在二进制级别引入了大量的中间变量，它们可能与任何源变量都没有对应关系；函数名和变量名依赖于应用程序和上下文，因此具有少量语法差异的机器指令可能有截然不同的名称。

该研究提出了一种创新的名称恢复技术，该技术结合了预训练的大型语言模型（LLM）和程序分析的优势。LLM模型通常在大规模数据集上进行训练，这些数据集包含多种模态，如源代码、二进制代码和自然语言。我们利用这些模型的训练规模，以及它们在处理复杂任务时的优越性能，来提升名称恢复技术的泛化能力。

该研究开发了一种命名传播算法，其性质与类型推断相似。在一轮查询中，如果LLM能够为查询代码片段中的某个反编译变量推导出一个有意义的名称，这个名称可以根据程序的语义传播到其他地方。这为未来的LLM查询提供了更多的上下文信息。

该文的研究贡献可以总结如下：

1. 提出了一种新的名称恢复方法，结合了LLM和程序分析的迭代算法，适用于二进制可执行文件。

2. 开发了一种系统的方法来构建LLM查询，能够包括从前几轮查询中收集的最新信息。

3. 提出了一种名称传播分析，可以将LLM预测的名称传播到其他地方，甚至构造新的有意义的名称。

4. 设计了一个后处理步骤，用于过滤掉无意义的名称，并从收敛后的分析结果中选择合适的名称。

5. 实现了一个原型系统LmPa，并在多个流行二进制分析基准上进行了评估。实验结果表明，LmPa在名称恢复任务上表现出色，大幅优于传统的DIRTY方法。

2 技术介绍

LmPa的工作流程可以用图1来描述。它主要处理二进制程序作为输入，并输出反编译后带有名称的程序。首先，LmPa使用IDA工具将输入的二进制程序转换成C代码。然后，它通过迭代的方式，利用ChatGPT来生成C代码中函数和变量的名称。

图1 LmPa工作流程

LmPa的整体工作流程如图1所示。它以二进制程序作为输入，输出带有恢复名称的反编译程序。LmPa首先利用IDA将输入的二进制程序反编译成C代码，然后迭代地查询ChatGPT以生成C代码中的函数和变量的名称。在反编译后，LmPa首先为输入的C程序中的每个函数生成提示符（图1中的步骤1），然后使用生成的提示符通过ChatGPT API进行查询，每次查询一个函数（步骤2）。LmPa在收到ChatGPT的响应后，解析这些自然语言输出，并将ChatGPT提出的名称映射回C代码（步骤3）。接着，应用程序分析（图1中的名称传播器）在函数之间传播这些名称（步骤4）。利用传播的结果，LmPa构造下一轮对ChatGPT的查询，随着时间的推移实现改进（步骤4）。在收敛之后，LmPa从多轮预测过的名称中选择最合适的名称，以进一步处理最终的结果（步骤5）。

接下来将简述各部分的技术细节。

2.1 与ChatGPT的交互

LmPa首先用自然语言描述任务，然后将反编译后的C代码附加到查询中。它列举出每个变量，并遵循特定的输出格式要求ChatGPT在回答时遵循指定的格式要求，这使得LmPa能够通过解析来识别每个建议的变量名及其对应的置信度。

LmPa使用预定义的正则表达式来解析ChatGPT的回答，以识别建议的变量名和置信度。然后在后续迭代中使用之前查询的结果来构建新的查询，并更新变量名预测结果。LmPa最终使用多数表决的方式从每个变量的候选名列表中选择一个最佳名称。

2.2 命名传播

LmPa开始时认为所有高置信度的ChatGPT预测变量名都是"good namess"，并赋予每个常量以它的文本形式作为"good names"。随后，LmPa定义了一系列规则来传播"good namess"。例如，一个好的调用函数名将被传播到它的调用者函数中的调用位置。LmPa使用一组规则进行迭代分析，直到达到一个固定的点。这期间，它会不断从更易于理解的函数中推导出上下文信息，并利用这些信息来改善ChatGPT的性能。names propagation是全局的，意味着一个变量可能具有多个"good namess"。LmPa通过逐渐推导出越来越多的关系来传播"good namess"。并且，LmPa使用传播的结果来构造下一轮的查询，从而提高查询的性能。

2.3 查询更新

在names propagation之后，LmPa进一步利用传播的名称来构建下一轮的查询。查询更新算法接收一个函数的查询文本和通过传播规则获得的GoodNamesOf关系作为输入，并为该函数输出一个新的查询。几个查询构建规则在图2中展示。

图2 LmPa如何组成新的查询。

绿色方框显示了推导出的GoodNamesOf关系，棕色方框显示了函数。在图2a中，LmPa在函数id0的上下文中推导出调用者函数id1的"good names"。它将所有对id1的调用重命名为这个"good names"。请注意，一个函数/变量可能有多个"good names"，LmPa会选择具有最新时间戳的那个。图2b显示了如何利用有关表达式的"good names"信息，包括单变量表达式。该文的names propagation允许为复合表达式生成名称。因此不能简单地将任何标识符重命名为利用此信息。所以，LmPa通过代码注释传播信息。如图2b所示，它在表达式ei之前添加了传播的name。请注意，即使相关的表达式是一个单变量表达式，简单地用一个"good names"替换它的标识符也可能导致不理想的结果。原因是ChatGPT倾向于不重命名已经在代码中有意义的变量。因此，直接在代码中设置变量名会阻止ChatGPT生成任何新的名称。图2c显示，当一个调用者函数及其实际参数表达式都有"good names"时，它们可以用于该函数的被调用者的查询。

3 实验评估

3.1 研究问题

RQ1: LmPa能有效地帮助开发人员理解反编译的代码吗?它与SOTA相比如何?

RQ2: LmPa和SOTA生成的名称在源代码中的匹配程度如何?

RQ3:名称传播分析对LmPa的整体性能有什么影响?

RQ4: LmPa在真实数据上的可扩展性好吗?

RQ5: LmPa能够适应LLM答案的不确定性吗?

3.2 数据集和基线

1) 数据集：

使用了6个流行的二进制分析基准，总共包含16,212个函数。

从这些基准中随机选取了1,258个函数，共计4,277个变量作为实验数据集。

2) 评估指标：

3) 方法比较：

将本文提出的LmPa方法与当前最先进的方法DIRTY进行了比较。

还比较了LmPa与直接查询ChatGPT（没有传播机制）以及一个简单的算法（仅将调用函数附加到查询中）。

3.3 实验结果

1. RQ1: LmPa能有效地帮助开发人员理解反编译的代码吗?它与SOTA相比如何?

为了回答这个问题，研究人员进行了一个用户研究，评估了LmPa恢复的变量名称对开发人员理解反编译代码的帮助程度，并与当前最先进的技术DIRTY进行了比较。

LmPa：在用户研究中，LmPa恢复的变量名有75%被认为是“好的”，即与真实变量名意义相近或更好。

DIRTY：在用户研究中，DIRTY恢复的变量名只有6%被认为是“好的”。

结论：LmPa能够更有效地帮助开发人员理解反编译的代码，其性能明显优于当前最先进的技术DIRTY。

2. RQ2: LmPa和SOTA生成的名称在源代码中的匹配程度如何?

为了回答这个问题，研究人员使用了相似度函数来评估LmPa和SOTA生成的名称与源代码中真实名称的匹配程度。他们使用了最长公共子序列（LCS）来计算预测名称和真实名称之间的相似度。

实验结果如下：

LmPa：当相似度阈值设置为0.6时，平均人类评分超过了4，这表明LmPa生成的预测名称是可接受的替代品。因此，他们选择了相似度阈值为0.6，意味着如果预测名称的相似度得分超过0.6，则认为这是一个“好名称”。

DIRTY：DIRTY在大多数数据集上在精度和召回率上都低于LmPa。

结论：LmPa生成的预测名称与源代码中真实名称的匹配程度明显高于SOTA技术DIRTY。尽管LmPa的预测名称与真实名称之间的精确匹配率不是非常高，但它们通常是可接受的替代品。这表明LmPa能够更准确地预测脱编译代码中的变量名称。

3. RQ3:名称传播分析对LmPa的整体性能有什么影响?

为了回答这个问题，研究人员进行了三项消融研究，以评估名称传播分析对LmPa性能的影响。

与一次ChatGPT查询的比较：结果显示，LmPa的性能略优于一次ChatGPT查询，这主要是因为一次ChatGPT查询可能无法生成足够的信息来预测变量名称。

与简单内联算法的比较：简单内联算法仅将调用函数附加到查询中，其性能明显低于LmPa，这表明调用函数和被调用函数之间的上下文信息对于LLM非常重要。

迭代次数的影响：实验结果表明，在初始几轮分析中，性能提升显著，但当迭代次数达到10轮时，性能达到最优。

结论：名称传播分析对LmPa的整体性能产生了显著影响。它提高了LmPa的召回率，通过在函数之间传播信息，为后续查询提供了更好的上下文。此外，迭代次数的增加对性能提升至关重要，尤其是在初始几轮中。这表明名称传播分析在LmPa框架中扮演着重要角色，并且可以继续改进以进一步提高性能。

4. RQ4: LmPa在真实数据上的可扩展性好吗?

为了回答这个问题，研究人员从两个角度评估了LmPa在真实数据上的可扩展性。

时间和查询成本：在每个数据集上，LmPa平均查询了ChatGPT 1791次，每次查询大约需要22.8秒。这导致了较高的时间成本，但考虑到反编译是一次性任务，这样的资源成本在实践中是可以接受的。

处理更大工作负载的能力：当处理更大的数据集时，LmPa的性能实际上有所提高。这主要是因为更大的数据集提供了更多的上下文信息来传播，从而为后续查询提供了更准确的信息。

结论：尽管LmPa在真实数据上的可扩展性相对较差，主要是由于每次查询需要较长时间，但它在处理更大的数据集时能够获得更好的性能。考虑到反编译是一次性任务，这样的资源成本在实践中是可以接受的。因此，可以认为LmPa具有一定的可扩展性，特别是在处理更大的数据集时。未来可以通过优化查询策略来进一步提高LmPa的可扩展性。

5. RQ5: LmPa能够适应LLM答案的不确定性吗?

为了评估LmPa是否能够适应LLM（大型语言模型）答案的不确定性，研究人员在Coreutils数据集上重复了8次实验，每次实验都让LmPa进行4轮名称传播。

实验结果显示，LmPa在不同运行之间的性能变化非常小，精确度和召回率的变化都不到0.04%。此外，每轮传播的性能提升显著大于运行之间的方差。

结论：LmPa能够很好地适应LLM答案的不确定性。其性能在不同运行之间保持稳定，且每轮传播都能显著提升性能。这表明LmPa在LLM的不确定性下能够稳定工作，并且能够通过多次迭代来提高性能。因此，LmPa具有很强的适应性和稳健性，能够在LLM的不确定性下有效地工作。

转述：朱云峰