Reducing the Memory Footprint of IFDS-Based Data-Flow Analyses using Fine-Grained Garbage Collection
Dongjie He, Yujiang Gui, Yaoqing Gao, Jingling Xue · 2023
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).