Boomerang: Demand-Driven Flow- and Context-Sensitive Pointer Analysis for Java
Boomerang: Demand-Driven Flow- and Context-Sensitive Pointer Analysis for Java
复制标题
DOI：
10.4230/lipics.ecoop.2016.22
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
Johannes Späth;Lisa Nguyen Quang Do;Karim Ali;E. Bodden
中科院分区：
文献类型：
--
作者：
Johannes Späth;Lisa Nguyen Quang Do;Karim Ali;E. Bodden
许多当前的程序分析需要关于给定程序的小的目标部分的高度精确的指针信息。这激发了需求驱动的指针分析的需要，仅在需要时计算信息。指针分析通常计算指向程序变量集或回答布尔别名查询。然而，许多客户端分析需要更丰富的指针信息。例如，污点和类型状态分析通常需要知道给定变量在特定调用上下文下的所有别名的集合。对于大多数当前的指针分析，客户端必须通过重复的指向或别名查询来计算这些信息，这增加了它们的复杂性和计算时间。本文介绍了Boomerang，一个需求驱动的，流，字段和上下文敏感的指针分析Java程序。Boomerang计算丰富的结果，包括给定指针的可能分配位置（指向信息）和所有可以指向这些分配位置的指针（别名信息）。为了提高精度和可伸缩性，客户端可以查询Boomerang关于感兴趣的特定调用上下文。我们的实验表明，Boomerang比现有的需求驱动的指针分析更精确。此外，使用Boomerang，与使用其他返回简单指针信息的指针分析相比，污点分析FlowDroid发出的指针查询减少了29.4倍。此外，Boomerang的搜索空间可以通过从客户端分析请求调用上下文来显著减小。
Many current program analyses require highly precise pointer information about small, tar- geted parts of a given program. This motivates the need for demand-driven pointer analyses that compute information only where required. Pointer analyses generally compute points-to sets of program variables or answer boolean alias queries. However, many client analyses require richer pointer information. For example, taint and typestate analyses often need to know the set of all aliases of a given variable under a certain calling context. With most current pointer analyses, clients must compute such information through repeated points-to or alias queries, increasing complexity and computation time for them. This paper presents Boomerang, a demand-driven, flow-, field-, and context-sensitive pointer analysis for Java programs. Boomerang computes rich results that include both the possible allocation sites of a given pointer (points-to information) and all pointers that can point to those allocation sites (alias information). For increased precision and scalability, clients can query Boomerang with respect to particular calling contexts of interest. Our experiments show that Boomerang is more precise than existing demand-driven pointer analyses. Additionally, using Boomerang, the taint analysis FlowDroid issues up to 29.4x fewer pointer queries compared to using other pointer analyses that return simpler pointer infor- mation. Furthermore, the search space of Boomerang can be significantly reduced by requesting calling contexts from the client analysis.