DROPS

Document

DOI: 10.4230/LIPIcs.ECOOP.2026.10

Field-Sensitive Over-Tainting Reduction in IFDS Taint Analysis via CFL-Reachability

Authors: Yujiang Gui, Yonggang Tao, and Jingling Xue

Published in: LIPIcs, Volume 372, 40th European Conference on Object-Oriented Programming (ECOOP 2026)

Abstract

IFDS taint analysis is inherently context- and flow-sensitive, allowing precise encoding of field sensitivity in access-path generation. However, preserving this level of precision in practice is difficult, leading to over-tainting - marking more data facts as tainted than necessary. The root cause is the undecidability of solving two context-free language reachability (CFL-reachability) problems along the same dataflow path, which forces k-limiting as an over-approximation of field sensitivity. Consequently, spurious access paths are introduced, increasing analysis time, memory usage, and false positives, especially in large-scale applications. To address this challenge, we present TnFix, a CFL-reachability-based technique for mitigating over-tainting in IFDS taint analysis. The key insight is that the field sequence of any candidate tainted access path can be checked by a deterministic finite automaton (DFA) that accepts feasible sequences of field accesses. TnFix builds these DFAs by first solving a lightweight field-sensitive CFL-reachability problem to construct a Field Points-to Graph (FPG) that integrates data flows from taint sources and library summaries, and then converting the FPG into per-object DFAs. During taint analysis, TnFix queries these DFAs to prune access paths whose field sequences are rejected, eliminating the spurious paths introduced by k-limiting and improving precision without sacrificing scalability. In a comparative evaluation against FlowDroid on a set of 36 widely used Android apps for taint analysis, TnFix successfully analyzes 7 apps that FlowDroid cannot complete within a three-hour time budget. For the remaining 29 apps, it improves analysis speed by an average of 2.5× and reduces false positives by an average of 12.2%. TnFix thus establishes the first CFL-based optimization framework for reducing over-tainting in IFDS taint analysis, delivering substantial gains in both efficiency and precision for practical use.

Cite as

Yujiang Gui, Yonggang Tao, and Jingling Xue. Field-Sensitive Over-Tainting Reduction in IFDS Taint Analysis via CFL-Reachability. In 40th European Conference on Object-Oriented Programming (ECOOP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 372, pp. 10:1-10:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gui_et_al:LIPIcs.ECOOP.2026.10,
  author =	{Gui, Yujiang and Tao, Yonggang and Xue, Jingling},
  title =	{{Field-Sensitive Over-Tainting Reduction in IFDS Taint Analysis via CFL-Reachability}},
  booktitle =	{40th European Conference on Object-Oriented Programming (ECOOP 2026)},
  pages =	{10:1--10:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-423-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{372},
  editor =	{Krebbers, Robbert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2026.10},
  URN =		{urn:nbn:de:0030-drops-261068},
  doi =		{10.4230/LIPIcs.ECOOP.2026.10},
  annote =	{Keywords: Taint Analysis, CFL-Reachability, Access Path, Field Sensitivity, Pointer Analysis}
}

Document

Artifact

DOI: 10.4230/DARTS.12.1.20

Field-Sensitive Over-Tainting Reduction in IFDS Taint Analysis via CFL-Reachability (Artifact)

Authors: Yujiang Gui, Yonggang Tao, and Jingling Xue

Published in: DARTS, Volume 12, Issue 1, Special Issue of the 40th European Conference on Object-Oriented Programming (ECOOP 2026)

Abstract

Our related paper presents TnFix, a CFL (context-free language)-reachability-based technique for mitigating over-tainting in IFDS taint analysis. The approach addresses a common source of imprecision introduced by k-limiting: it prunes spurious access paths by checking candidate field sequences against per-object DFAs (deterministic finite automata). To build these DFAs, TnFix first solves a lightweight, field-sensitive CFL-reachability problem to construct a Field Points-to Graph (FPG) that integrates flows from taint sources and library summaries, and then transforms the FPG into object-specific DFAs used during analysis to reject infeasible field-access sequences. This artifact bundles the implementation of TnFix (including field-sensitive CFL-reachability solving, per-object DFA construction, and DFA-based filtering), together with the evaluation harness used in the paper. It provides scripts to run TnFix and FlowDroid under identical settings and to reproduce the reported performance and precision results on the Android app set used in our evaluation.

Cite as

Yujiang Gui, Yonggang Tao, and Jingling Xue. Field-Sensitive Over-Tainting Reduction in IFDS Taint Analysis via CFL-Reachability (Artifact). In Special Issue of the 40th European Conference on Object-Oriented Programming (ECOOP 2026). Dagstuhl Artifacts Series (DARTS), Volume 12, Issue 1, pp. 20:1-20:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{gui_et_al:DARTS.12.1.20,
  author =	{Gui, Yujiang and Tao, Yonggang and Xue, Jingling},
  title =	{{Field-Sensitive Over-Tainting Reduction in IFDS Taint Analysis via CFL-Reachability (Artifact)}},
  pages =	{20:1--20:4},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2026},
  volume =	{12},
  number =	{1},
  editor =	{Gui, Yujiang and Tao, Yonggang and Xue, Jingling},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.12.1.20},
  URN =		{urn:nbn:de:0030-drops-261573},
  doi =		{10.4230/DARTS.12.1.20},
  annote =	{Keywords: Taint Analysis, CFL-Reachability, Access Path, Field Sensitivity, Pointer Analysis.}
}

Search Results

Documents authored by Gui, Yujiang

Field-Sensitive Over-Tainting Reduction in IFDS Taint Analysis via CFL-Reachability

Abstract

Cite as

Field-Sensitive Over-Tainting Reduction in IFDS Taint Analysis via CFL-Reachability (Artifact)

Abstract

Cite as

Thanks for your feedback!

Could not send message