一句话：将域敏感访问路径生成重构为 CFL 并归约为 IDE 问题，显著减少 IFDS 数据流事实数，加速污点分析。
IFDS 算法常用于域敏感数据流分析，但传统用访问路径实现域敏感会生成大量数据流事实，在大程序上可扩展性差。本文提出一种新的域敏感技术，把访问路径的生成重新解释为用于域敏感性的上下文无关语言（CFL），并将其表述为 IDE 问题；由此显著减少分析中生成和处理的数据流事实数。作者在 IFDS/IDE 框架上实现了污点分析工具 IDEDroid，并在 24 个主流 Android 应用上与 FlowDroid 对比。结果显示，IDEDroid 加速 2.1× 至 2368.4×，平均 222.0×，同时理论上保证精度不降，误报最多减少 20.0%。
The IFDS algorithm is pivotal in solving field-sensitive data-flow problems. However, its conventional use of access paths for field sensitivity leads to the generation of a large number of data-flow facts. This causes scalability challenges in larger programs, limiting its practical application in extensive codebases. In response, we propose a new field-sensitive technique that reinterprets the generation of access paths as a Context-Free Language (CFL) for field-sensitivity and formulates it as an IDE problem. This approach significantly reduces the number of data-flow facts generated and handled during the analysis, which is a major factor in performance degradation. To demonstrate the effectiveness of this approach, we developed a taint analysis tool, IDEDroid, in the IFDS/IDE framework. IDEDroid outperforms FlowDroid, an established IFDS-based taint analysis tool, in the analysis of 24 major Android apps while improving its precision (guaranteed theoretically). The speed improvement ranges from 2.1 × to 2,368.4 × , averaging at 222.0 × , with precision gains reaching up to 20.0 % (in terms of false positives reduced). This performance indicates that IDEDroid is substantially more effective in detecting information-flow leaks, making it a potentially superior tool for mobile app vetting in the market.
@article{LiS00X24,
title = {Boosting the Performance of Alias-Aware IFDS Analysis with CFL-Based Environment Transformers},
author = {Haofeng Li and Chenghang Shi and Jie Lu and Lian Li and Jingling Xue},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {OOPSLA2},
year = {2024},
doi = {10.1145/3689804}
}