Yujiang Gui Dongjie He Jingling Xue
MergeDroid is a novel approach to improve the efficiency and precision of IFDS-based taint analysis, which is introduced in our paper titled "Merge-Replay: Efficient IFDS-Based Taint Analysis by Consolidating Equivalent Value Flows", ASE'23.
To maintain flow sensitivity between the forward and backward solvers, FlowDroid decorates data facts with activation statements (i.e., statements triggering alias queries). However, when distinct activation statements are linked with the same data abstraction, this mechanism introduces equivalent yet redundant value flows. We proposed a merge-and-replay strategy to eliminate redundant value flow propagation. Specifically, activation statements linked to the same data abstraction from various reachable data facts that are reachable at a given program point during the backward pass are merged by a symbolic activation statement. In addition, spurious value flows can be pruned by leveraging context-sensitive insights from symbolic activation statements, resulting in improved precision.
The tar.gz file includes the source code of MergeDroid.