一句话：提出 IFDS 的稀疏化算法，将数据流事实直接传播至下一次使用点，大幅降低污点分析的时间和内存开销。
IFDS 算法在大程序上计算与内存开销高，常提前终止并导致污点分析漏报或误报。本文提出 IFDS 的稀疏替代方案：不再沿过程间控制流图向所有程序点传播事实，而是为每个数据流事实动态构建稀疏控制流图，将其直接传播到下一个可能使用点，从而同时降低时间和内存需求。在 40 个 Android 应用上，稀疏版 SPARSEDROID 与基于传统 IFDS 的 FLOWDROID 相比，在每应用 5 小时、220GB 预算下可全部完成分析，而 FLOWDROID 有 9 个提前终止，平均加速 22.0 倍；作为市场级审查工具，SPARSEDROID 在 2.13 小时内分析完 40 个应用并报告 228 个泄漏警告，FLOWDROID 同期仅分析 30 个应用并报告 147 个。
The IFDS algorithm can be compute-and memoryintensive for some large programs, often running for a long time (more than expected) or terminating prematurely after some time and/or memory budgets have been exhausted. In the latter case, the corresponding IFDS data-flow analyses may suffer from false negatives and/or false positives. To improve this, we introduce a sparse alternative to the traditional IFDS algorithm. Instead of propagating the data-flow facts across all the program points along the program’s (interprocedural) control flow graph, we propagate every data-flow fact directly to its next possible use points along its own sparse control flow graph constructed on the fly, thus reducing significantly both the time and memory requirements incurred by the traditional IFDS algorithm. In our evaluation, we compare FLOWDROID, a taint analysis performed by using the traditional IFDS algorithm, with our sparse incarnation, SPARSEDROID, on a set of 40 Android apps selected. For the time budget (5 hours) and memory budget (220GB) allocated per app, SPARSEDROID can run every app to completion but FLOWDROID terminates prematurely for 9 apps, resulting in an average speedup of 22.0x. This implies that when used as a market-level vetting tool, SPARSEDROID can finish analyzing these 40 apps in 2.13 hours (by issuing 228 leak warnings) while FLOWDROID manages to analyze only 30 apps in the same time period (by issuing only 147 leak warnings).
DOI 原文 ·
@inproceedings{paperbot5253,
title = {Performance-Boosting Sparsification of the IFDS Algorithm with Applications to Taint Analysis},
author = {Dongjie He and Haofeng Li and Lei Wang and Haining Meng and Hengjie Zheng and Jie Liu and Shuangwei Hu and Lian Li and Jingling Xue},
booktitle = {ASE},
year = {2019},
doi = {10.1109/ase.2019.00034}
}