两种用于静态分析的快速字节码前端实现方法

《Proceedings of the ACM on Programming Languages》：Two Approaches to Fast Bytecode Frontend for Static Analysis

现有Java静态分析框架的字节码前端效率不足，本文提出新型前端通过模式感知的3地址码转换和剪枝式类型推断优化，实现比Soot、WALA等工具快14.2至75.2倍的效率提升，同时增强可靠性。

　　

摘要

在Java的静态分析框架中，字节码前端是一个关键组件，它将复杂的、基于栈的Java字节码转换为更易于分析的、基于寄存器的、带类型的3地址代码表示形式。这种转换通常会显著影响分析框架的整体性能，尤其是在处理大规模Java应用程序时，因此字节码前端的效率对于静态分析至关重要。然而，目前主流的Java静态分析框架Soot和WALA尽管经过了时间考验并被广泛采用，但在效率方面仍存在局限性，这限制了它们提供更好用户体验的能力。

为了解决效率问题，我们引入了一种新的字节码前端。通常，字节码前端包括两个关键阶段：（1）将Java字节码转换为无类型的3地址代码；（2）对这种代码进行类型推断。对于3地址代码的转换，我们发现了字节码中的某些常见模式，这些模式能够比传统方法实现更高效的处理。在类型推断方面，我们发现传统算法中常常包含一些冗余的计算，从而影响性能。基于这些发现，我们提出了两种新颖的方法：基于模式的3地址代码转换和基于剪枝的类型推断，这两种方法共同构成了我们的新字节码前端，并显著提升了效率。此外，我们的方法还可以生成SSA中间表示（SSA IR），从而增强了其在各种静态分析技术中的可用性。

我们将新的字节码前端实现到了Tai-e中，这是一个最新的Java静态分析框架，并在多种Java应用程序上对其性能进行了评估。实验结果表明，我们的前端在效率方面明显优于Soot、WALA和SootUp（Soot的改进版本）——平均速度分别快14.2倍、14.5倍和75.2倍。此外，进一步的实验还表明，我们的前端在处理Java字节码时比这些工具更加可靠，从而为Java静态分析提供了更坚实的基础。