一句话：提出 FPC 细粒度垃圾回收，在保持 IFDS 正确性、精度与终止性的同时减少路径边存储和重哈希，降低内存占用。
基于 IFDS 的数据流分析需要存储大量路径边并迭代至不动点，许多路径边仅被访问一次，导致内存开销高、哈希重散列频繁，从而影响可扩展性与效率。本文提出细粒度垃圾回收算法 FPC，在数据事实级别回收不再用于建立其他路径边的非活跃路径边，并避免重复处理已回收边，即使未来迭代中可能出现未知递归环，也能保持 IFDS 的正确性、精度与终止性。与在方法级别粗粒度回收路径边的 CleanDroid 相比，FPC 可回收更多路径边并减少重哈希。评估在 28 个 Android 应用上运行基于 IFDS 的污点分析：FPC 能完成 CleanDroid 因内存溢出而无法完成的 3 个应用；在其余 25 个应用上，路径边数和内存使用平均分别降低 4.4 倍和 1.4 倍，性能平均提升 1.7 倍，最佳达 18.5 倍。
The IFDS algorithm can be both memory- and compute-intensive for large programs as it needs to store a huge amount of path edges in memory and process them until a fixed point. In general, an IFDS-based data-flow analysis, such as taint analysis, aims to discover only the data-flow facts at some program points. Maintaining a huge amount of path edges (with many visited only once) wastes memory resources, and consequently, reduces its scalability and efficiency (due to frequent re-hashings for the path-edge data structure used). This paper introduces a fine-grained garbage collection (GC) algorithm to enable (multi-threaded) IFDS to reduce its memory footprint by removing non-live path edges (i.e., ones that are no longer needed for establishing other path edges) from its path-edge data structure. The resulting IFDS algorithm, named FPC, retains the correctness, precision, and termination properties of IFDS while avoiding re-processing GC’ed path edges redundantly (in the presence of unknown recursive cycles that may be formed in future iterations of the analysis). Unlike CleanDroid, which augments IFDS with a coarse-grained GC algorithm to collect path edges at the method level, FPC is fine-grained by collecting path edges at the data-fact level. As a result, FPC can collect more path edges than CleanDroid, and consequently, cause fewer re-hashings for the path-edge data structure used. In our evaluation, we focus on applying an IFDS-based taint analysis to a set of 28 Android apps. FPC can scalably analyze three apps that CleanDroid fails to run to completion (under a 3-hour budget per app) due to out-of-memory (OoM). For the remaining 25 apps, FPC reduces the number of path edges and memory usage incurred under CleanDroid by 4.4× and 1.4× on average, respectively, and consequently, outperforms CleanDroid by 1.7× on average (with 18.5× in the best case).
@inproceedings{HeGGX23,
title = {Reducing the Memory Footprint of IFDS-Based Data-Flow Analyses using Fine-Grained Garbage Collection},
author = {Dongjie He and Yujiang Gui and Yaoqing Gao and Jingling Xue},
booktitle = {ISSTA},
year = {2023},
doi = {10.1145/3597926.3598041}
}