最近完成了南大《软件分析》课程的学习，于是顺便阅读了两位老师在今年ISSTA发表的关于太阿的论文。
1. 引言
静态分析被广泛应用在不同方面，对于学术研究和工业产品也有许多好处。静态分析框架提供了多种基本服务，包括IR生成、CFG构建、指针信息的计算等。然而，尽管静态分析在这数十年内有了可观的进展，如今流行的静态分析框架对于需要依赖它们实现分析的开发者而言并不那么易于学习和使用。要构建一个对开发者友好的静态分析框架是很复杂的，因为比起静态分析本身需要的知识，我们对于设计和实现静态分析框架的拥有的相关知识很少。这是一个有挑战性的问题，因为框架的设计通常会在简易、可用、效率等目标之间做取舍。
尽管也有一些著作分享了开发分析框架的经验，但这仍然没有解决问题的根源，目前仍然缺少一个系统的观点来从开发者的角度评估静态分析框架的质量。
1.1. 关键组件设计的权衡
1. 程序抽象：提供抽象模型，包括IR、类分层结构等，从而表示静态分析需要的所有程序元素
2. 基本分析：让开发者利用控制流图（CFG）、调用图（CG）等来实现基于图的算法，并利用程序的抽象内存信息（例如指针关系）来构建复杂的分析
3. 新分析的开发：允许用户开发与集成新的分析，例如漏洞检测、安全分析、异常分析、反射分析等
4. 多种分析的管理：当多种分析需要共同进行时，提供一种标准方法管理它们，例如配置它们的依赖关系或协调它们的输出
1.2. 贡献
1. 系统性地研究多种Java静态分析框架的设计
2. 提出太阿框架
· 易用的IR
· 扩展性和效率更高的指针分析系统
· 易于开发和集成各种分析的插件系统
3. 教学版太阿，广泛应用于多所大学和公司
2. 程序抽象
太阿的IR与Soot和Wala相比，可以让开发者实现更简洁的分析代码，并更好地理解IR。太阿在多个方面提高了对于开发者的友好程度，包括：
1. IR的设计，太阿区分不同赋值语句的类型；
2. 相关API的设计，太阿在检索表达式时使用具体的返回类型，避免使用整数索引来代表变量；
3. 程序元素（数值、类型、名称等）的组织性和可访问性，太阿将所有变量相关的信息集中到一个接口，而不是分布到不同的接口。
这些使得开发者能够编写更简洁的代码，避免在使用不同语句的时候编写不必要的条件检查和向下转型，同时也让开发者更容易地学习太阿的功能，更流畅地实现分析。
以二元语句（x = y + z）的处理为例，太阿显式地区分赋值语句的具体类型（new load store unary binary等），而Soot则需要额外的条件检查来确认类型；Soot总是需要对操作数的返回值（例如getOp1）进行类型转换，Wala的操作数返回的是整数索引，需要再在符号表里面进行查找，而太阿避免了以上的问题。
为了让IR在特定的分析中更易用，太阿还实现了一些新的IR设计。例如，为了让指针分析更便利，太阿将每个变量和它相关的IR语句关联起来，在分析的过程中，每当变量的值发生变化时，开发者可以直接方便地获取到所有相关的IR语句来进行后续操作。
3. 基本分析
3.1. 指针分析
3.1.1. 指针信息（Point-to）的表示
位集（bit set）用于表示变量的points-to set中被指向的对象，表示为1，其他为0。当只有几个对象时，许多其他bit都会被浪费，为了解决这个问题，太阿使用vm-bitset来表示pts。每个int（占用32b）指向一个256位的位集，只有包含对象的位集会被使用，其他位集不会占用空间。图中是一级页表，为了节省更多空间，太阿使用两级页表，根据对象的数量，表的大小会动态调整。在指针分析中，与Soot和Wala使用的常规的位集相比，太阿平均能够节省23%（最高40%）的内存。
3.1.2. 上下文管理
太阿可以将上下文的长度作为命令的输入参数，并且可以让开发者为方法调用或堆对象指定上下文（例如3-call-site或1-object）。
3.2. 控制/数据流分析
3.2.1. 控制流分析
· 边的分类
太阿提供了更多边的信息，例如为switch边添加case的值，为exception边添加具体的exception类型，开发更加方便。
· 异常处理
太阿会区分显式（代码中的throw catch）和隐式（由JVM抛出）的异常，并让用户选择将哪种异常添加到控制流图中。此外，太阿实现了更SOTA的异常分析，分析精确度更高。
3.2.2. 数据流分析
· 数据fact的初始化
与Wala不同，太阿、SpotBugs、Checker、Soot都能够在分析中初始化数据fact，只使用一个求解器就能驱动多种数据流分析，这样开发者就只需要实现自己的分析，而不需要了解求解器的细节。
· 边转移函数
太阿、SpotBugs、Wala都显式地支持边转移函数，而Soot和Checker不支持。边转移函数与节点转移函数的不同之处在于，前者能够沿着边将数据事实发送到多个后继节点，利用分支信息创建更有效的分析。
太阿在控制/数据流分析方面的主要提升在于让开发者更方便地开发复杂的分析，以及让控制流图更完整。
4. 新分析的开发
太阿提供了分析插件系统，能够方便地让用户开发和集成新的分析，目前已经有许多基于这个系统构建的分析，包括反射分析、异常分析、污点分析等。现有的框架在这方面都有一定的缺点，例如缺少命令交互机制、机制过于复杂、能力有限，而太阿的插件系统提供了更全面的交互特性，包括添加pts、CG边，以及生成IR。它的设计较为简单，易于学习和使用。
4.1. 基本概念
插件系统包括一个指针分析求解器（Solver）和多个与之交互的用户定义的分析插件，每个插件需要实现Plugin接口。插件和指针分析求解器之间通过调用对方的API来交互。
假设用户要实现onNewPointsToSet方法，这意味着当某个变量的pts变化（例如指向了更多对象），用户需要在其中编写代码来反映这个变化的副作用，例如修改相关指针的pts（调用addPointsTo）或者在相关的call site添加CG边（调用addCallEdge）。反过来说，在每个分析迭代中，求解器会自动调用每个插件的onNewPointsToSet或onNewCallEdge等方法来通知它们相应的变化。
4.2. 案例研究
一个污点分析插件：
假设敏感数据来自x.source()即s1，指向o1，s2.concat(s1)即s3指向o3，也就是说o3包含了o1。污点分析会报告第3行存在o1的敏感数据的泄漏，因为o3是sink方法的参数。
1 String s1 = x.source(); 2 s3 = s2.concat(s1); 3 y.sink(s3);
在处理代码第1行时，指针分析求解器添加一个新的CG边（1, source()），并调用插件的onNewCallEdge。插件会对这条边进行检查，如果是source，则创建一个污点对象，并调用求解器的addPointsTo，将污点对象添加到s1的pts中。第2行的concat是一种转移方法，在onNewCallEdge中会将污点对象添加到转移目标（s3）的pts中。最终，在onFinish方法里对sink的参数进行检查，如果参数指向污点对象，则进行报告。
5. 多种分析的管理
在许多情况下，某个分析可能会依赖于其他分析的输出结果，所以需要框架提供一个协同多种分析的机制。
5.1. 配置分析及其依赖
太阿通过一个配置文件来注册所有新的分析，并通过反射来驱动它们，从而实现代码的解耦。在分析依赖的配置方面，太阿通过分析配置文件来自动处理依赖关系，确保依赖分析的执行顺序，这样可以节省开发者编写命令参数的精力。太阿支持通过条件逻辑来描述分析选项和依赖，这样在处理分析依赖上更加灵活。总之，在配置和构建分析时，为了提供简洁的使用和维护操作，太阿让用户尽可能少地修改代码或配置。
5.2. 存储/访问分析结果
太阿提供了统一的分析结果管理机制，对于任意类型的分析，用户只需要调用getResult(id)来获取分析结果。太阿会根据分析的类型在不同位置存储分析的结果，从而实现了这种简单直接的用户接口，用户不需要记住各种复杂的方法调用并指定额外的参数来获取分析结果。
6. 评估
6.1. 研究背景
作者在学校里进行了静态分析的教学，并发布了一项作业，即使用太阿和Soot/Wala来实现反射分析。作者还对参与的学生进行了问卷调查，让学生提供他们在不同框架上实现分析的体验，并收到了其中16位学生的反馈。在这16位学生中，5位来自作者的研究组，其余11位来自其他组。在这项研究之前，3位学生对于Soot/Wala熟悉，1位对太阿熟悉，4位对两者都熟悉，其余8位对于这些框架都不熟悉。
6.2. RQ1：太阿是否对开发者更友好
参与调查的16位学生均表示太阿比Soot/Wala对开发者更友好，主要的原因包括：
1. 太阿的架构、代码和API设计更易于理解和使用；
2. 太阿的IR更易懂且更易于使用，能让用户进行更简洁的实现；
3. 太阿的插件系统很简单，但使用起来很有效；
4. 太阿拥有更强大的指针分析系统。
在熟悉框架、设计分析、开发和测试的时间上，学生在太阿上花费的平均时间比Soot/Wala更短。
6.3. RQ2：太阿的插件系统是否有帮助
16位学生均表示太阿的插件系统是有帮助的，主要在于简化了对于框架底层的分析机制的理解，在分析的开发上也更容易实现。
6.4. RQ3：太阿的主要缺点
根据参与调查的学生的反馈，太阿的主要缺点在于：
1. 文档不够全面
2. 生态不够丰富
此外也有一些API设计上的反馈。
6.5. RQ4：太阿的效率
6.5.1. 指针分析
6.5.2. 数据流分析
7. 相关工作
Lam et al. “The Soot framework for Java program analysis: a retrospective” 对Soot进行了回顾，总结了它的主要特性、变化，以及将来的开发方向。此外，他们还提出了Soot开发过程中的难点，并对于未来的编译器框架的特性提出了一些建议。
Schubert et al. “Into the Woods: Experiences from Building a Dataow Analysis Framework for C/C++” 提出了构建C/C++的数据分析框架的经验，其中提到了一些有用的方法，例如通过插桩之类的方法来辅助分析相关的debug，作者也会考虑在太阿中开发类似的功能。
Sadowski et al. “Lessons from Building Static Analysis Tools at Google” 总结了构建静态分析工具的经验，他们建议尽早将静态分析整合到工作流中。这么做需要对太阿的基础架构进行修改，但值得进行深入研究。
Facebook的研究 “Scaling Static Analyses at Facebook” 强调了过程间分析对于发现深层漏洞和安全漏洞的价值。太阿的分析插件系统的设计让开发复杂的过程间分析更加容易。
“What developers want and need from program analysis: an empirical study“、”Why Do Software Developers Use Static Analysis Tools? A User-Centered Study of Developer Needs and Motivations“、”A Large-Scale Study of Usability Criteria Addressed by Static Analysis Tools” 从用户需求的角度对静态分析工具进行了评估。例如，一个好的静态分析工具应该生成高质量的分析结果、减少误报、支持与用户知识的整合等。
Chord（”Eective static race detection for Java“） 是一个Java静态分析框架，它使用Java开发，并使用bddbddb来处理Datalog。Chord的优势在于它对于同步问题（例如数据竞争）的检测，作者将来也会在太阿中开发这样的功能。
OPAL（”A Software Product Line for Static Analyses: The OPAL Framework“）是一个Java静态分析框架，使用Scala开发。尽管它们实现了分析的协作，但是对于开发分析而言太复杂。同作者的”Judge: identifying, understanding, and evaluating sources of unsoundness in call graphs” 对多个框架的CG生成的完整性，强调了有效处理语言特性的重要性。
TAJS（”Type Analysis for JavaScript“）是一个经典的JS静态分析框架，太阿的某些设计受到了它的启发，包括回归测试和插件系统的最初思路，尽管TAJS的目标、方法和API与太阿不同。
8. 总结
现有的流行的静态分析框架对于开发者而言不易于学习和使用，要构建一个对开发者友好的框架也是一件困难的事。该论文遵循HGDC原则，系统性地对静态分析框架中的关键组件的设计取舍做了对比和讨论。基于这些研究，作者提出了太阿，一个对开发者友好的Java静态分析框架。作者希望这项工作能够对于构建静态分析框架提供有用的材料和观点，同时作者将来也会继续对太阿进行开发，使之支持更多的分析。