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

The IFDS framework [34] tackles a special type of dataflow problem known as the IFDS problem (interprocedural, finite, distributive, subset), of which an instance IP is defined as a quintuple $\text{IP}=(G^{\ast },D,F,M,\sqcap )$, where $G^{\ast }=(N^{\ast },E^{\ast })$ is the supergraph of the program, $D$ is a finite set of data facts, $F\subseteq 2^D\to 2^D$ is a set of distributive dataflow functions, $M:E^{\ast }\mapsto F$ is a map from the supergraph edges to dataflow functions, and the meet operator $\sqcap$ varies as either union or intersection, depending on the problem modeled.

The supergraph $G^{\ast }$ is composed of multiple control flow graphs (CFGs), one for each method in the program. Each method $m$ has its own CFG $G_m$, with a unique start node $s_m\in N^{\ast }$ and an exit node $e_m\in N^{\ast }$. A callsite is denoted by a call node $c\in N^{\ast }$ and a return node by $r\in N^{\ast }$. The remaining nodes, called normal nodes, represent statements and predicates as in typical flow graphs, including assign nodes for assignment statements. Edges in $E^{\ast }$ are classified into four kinds: call edges (linking a call node to a start node), return edges (linking an exit node to a return node), call-to-return edges (linking a call node to a return node), and normal edges (linking normal nodes).

As shown in Algorithm 1, Reps et al. [34] reduce the IFDS problem to a graph reachability problem on an exploded supergraph $G_{\mathrm{𝐼𝑃}}^{\mathrm{\#}}=(N^{\mathrm{\#}},E^{\mathrm{\#}})$ derived from $G^{\ast }$, where $N^{\mathrm{\#}}=N^{\ast }\times (D\cup \{\text{0}\})$ and $E^{\mathrm{\#}}=\{⟨m,d_1⟩\to ⟨n,d_2⟩|m\to n\in E^{\ast },f=M(m,n),d_2\in f(d_1)\}$. Note that $f\in F$ is the dataflow function of the edge $m\to n\in E^{\ast }$, 0 represents a special fact that facilitates the generation of new facts at certain program points, and $Sum$ summarizes the interprocedural dataflow facts obtained across the function boundaries (lines 11 and 16).

The graph-reachability problem is solved using an efficient tabulation algorithm implemented as a worklist. The analysis begins from the initial path edge $⟨s_{\mathrm{main}},\text{0}⟩\to ⟨s_{\mathrm{main}},\text{0}⟩$ – with “main” denoting the program entry – and incrementally accumulates new path edges until a fixed point is reached. Each path edge $⟨s_m,d_1⟩\to ⟨n,d_2⟩$, where $s_m$ is the start node of method $m$, represents a feasible context-sensitive path in $G_{\mathrm{𝐼𝑃}}^{\mathrm{\#}}$ from $⟨s_{\mathrm{main}},\text{0}⟩\to ⟨n,d_2⟩$. The IFDS algorithm shown in Algorithm 1 is the standard tabulation procedure used in mainstream implementations [30]; full details can be found in [34, Figure 3].

CFL-reachability [32] is a foundational abstraction used in a wide range of program analyses, including pointer analysis, shape analysis, slicing, and information-flow reasoning. It is defined over an edge-labeled graph $G=(V,E)$ together with a context-free grammar $𝔊=(N,\mathrm{\Sigma },P,S)$, where $N$ is the set of non-terminals, $\mathrm{\Sigma }$ the terminals, $P$ the productions, and $S$ the start symbol. Each edge $u\stackrel{𝛼}{\to }v\in E$ is labeled with $\alpha \in \mathrm{\Sigma }$; its inverse $v\stackrel{\overline{\alpha }}{\to }u$ is also included, enabling bidirectional traversal and supporting analyses that require matching paired operations such as stores and loads [40].

A path in $G$ forms a word by concatenating its edge labels. For any non-terminal $X\in N$, a path $p$ from $p_s$ to $p_e$ witnesses the relation $p_{s}X{p}_e$ if its label sequence is derivable from $X$ in $𝔊$. The grammar thereby specifies the well-formed traversal patterns considered feasible by the analysis – for example, balanced sequences of field stores and loads or properly nested invocation contexts.

The all-pairs CFL-reachability problem computes, for every non-terminal $X\in N$, all node pairs $(p_s,p_e)$ whose connecting paths satisfy this relation. Classical solutions rely on dynamic programming techniques [28] to enumerate all derivable relations specified by $𝔊$. CFL-reachability therefore provides a unifying basis for expressing recursive, interprocedural, and field-sensitive relationships in static analysis.

We illustrate the practical impact of over-tainting using a real-world example extracted from com.kanedias.vanilla.metadata, an open-source Android app from F-Droid [6] that retrieves music metadata. As shown in Figure 1a, the example involves three classes: FetchActivity, an Android UI activity (lines 5–12); Wrapper, which manages data loading from external sources (lines 23–37); and Extractor, an inner class of FetchActivity that mediates interactions between the activity and the wrapper (lines 13–22). Note that although Extractor is defined inside FetchActivity, it is shown separately in the figure for clarity.

The dummyMain() method simulates the lifecycle of the activity (lines 1–4). Within onCreate(), an Extractor instance is created and its extract() method is invoked (lines 10–11). Inside extract(), the FetchActivity object is referenced by x (line 17), and p is assigned the associated Wrapper instance via getWrapper() (line 18). Subsequent data loading on p calls loadCover() and loadMetadata() (lines 19–20).

The taint source appears in loadCover(), where sensitive data is read into is (line 28) and then stored into the field this.c (line 29). The sink is located in loadMetadata(), which reads the field this.f into file and logs its content (lines 33–36). Finally, at line 21, the field value p.f is transferred to x.m via getAudioFile().

No data leak occurs in this program because the source and sink operate on distinct object fields. The sensitive data is written to field c of the Wrapper object (line 29), whereas the sink reads exclusively from field f of that same object (lines 34–36). Since c and f are different fields of the Wrapper instance allocated at line 6, the taint on p.c never flows into p.f. Consequently, msg at line 36, which is derived from p.f, remains untainted, ensuring that no leak occurs at line 36, the sole sink statement in this example.

Below, we explain how FlowDroid reports a false leak at this sink due to over-tainting, while TnFix effectively prevents it. We consider access paths under $2$-limiting ($k=2$).

FlowDroid [4], illustrated in Figure 1b, performs IFDS taint analysis [34] using concurrent forward and backward passes, each encoded as a reachability problem on its own exploded supergraph (Algorithm 1). In these graphs, gray nodes mark tainted access paths discovered by the forward pass, while red nodes represent aliases computed by the backward pass. The two passes interact by iteratively injecting path edges into one another (shown by $\mathbf{\to }$), allowing aliasing information to influence taint propagation and vice versa. Summary edges ($\mathbf{\to }$) capture entry-to-exit effects across method boundaries.

Flow sensitivity is preserved by temporarily deactivating a data fact (prefixed with an underscore ‘_’) when the backward pass identifies it as an alias of a tainted access path and injects it into the forward pass. Because such aliases arise at program points lexically earlier than where the taint was originally established, the injected fact is propagated forward but activated only at the point where that access path is actually tainted ($\mathbf{⇢}$ or $\mathbf{⇢}$). This ensures that path edges are reintroduced only at flow-correct locations, maintaining the precision guarantees of the IFDS formulation.

In this example, the analysis begins in the forward pass at line 28 in loadCover(). The zero fact 0 initiates taint propagation, marking is as tainted. Using the library summary of readAllBytes() (described in Section 4.1), the taint then flows to this.c at line 29. This triggers the backward pass (shown by $\mathbf{\to }$) to trace aliases: starting from _this.c (①), it identifies _p.c at line 18 via parameter passing, _x.w.c at line 17 based on the load at line 8, and subsequently _this.a.w at line 17 based on the load at that line (②).

The critical precision loss occurs during the backward pass at line 17 (②). Although _this.a.w.c is derived from _x.w.c, its final field c is truncated by 2-limiting ($k=2$). This truncation discards the specific field being accessed and causes the analysis to treat the entire Wrapper object referenced by w as tainted. The backward pass then propagates _this.a.w, revealing its alias _e.a.w at line 10 (③).

During the subsequent forward pass at line 17 (④), _this.a.w is recognized as tainted, which in turn marks _x.w and _p as tainted at lines 17 and 18. At line 21, x.m becomes tainted due to the load of field f from p (line 32), triggering another backward pass (⑤) that identifies its aliases: _e.a.m and _this.m in onCreate() (⑥), as well as _this.a.m in extract() (⑦). In parallel, file becomes tainted at line 35 after loadMetadata() is invoked at line 20, causing msg to be tainted at line 36 (⑤’).

Ultimately, FlowDroid reports a false leak at line 36.

Due to $k$-limiting in access-path management, classic IFDS taint analyses like FlowDroid suffer from two major limitations:

• $\mathrm{■}$

  Limited Field Sensitivity. As shown in Figure 1b, under $k=2$, the taint propagation path constructed by FlowDroid for the call p.loadMetadata() at line 20 is:

  	is (①)	$\to \text{\_p.c}\text{(}\text{②}\text{)}\to \text{\_x.w.c}\text{(}\text{②}\text{)}\to \text{\_e.a.w}\text{(}\text{③}\text{)}$
  		$\to \text{\_x.w}\text{(}\text{④}\text{)}\to \text{\_p}\text{(}\text{④}\text{)}\to \text{this.f}\text{(}\text{⑤}\text{’)}$
  		$\to \text{file}\text{(}\text{⑤}\text{’)}\to \text{msg}\text{(}\text{⑤}\text{’)}$

  When p is (incorrectly) tainted at line 20, this.f becomes tainted at line 34, leading FlowDroid to report a leak at line 36. Under $k=3$, however, the taint path becomes:

  $$\text{is}\to \text{\_p.c}\to \text{\_x.w.c}\to \text{\_e.a.w.c}\to \text{\_x.w.c}\to \text{\_p.c}$$

  so this.f is never tainted, since fields c and f do not match. Thus, the leak warning produced under $k=2$ is a false positive, caused by truncating _this.a.w.c to _this.a.w at line 17 – an imprecision that over-taints this.f due to insufficient field sensitivity.

• $\mathrm{■}$

  Limited Scalability, Efficiency, and Precision. Spurious access paths degrade scalability, efficiency, and precision. As shown in Figure 1b, the propagation of the spurious taint on this.f triggers unnecessary alias searches (⑤ through ⑦) and ultimately causes the false positive reported at line 36 (⑤’).

We present TnFix, a staged taint analysis framework designed to mitigate the over-tainting inherent in traditional IFDS-based tools such as FlowDroid. TnFix prunes spurious access paths using lightweight, field-sensitive enhancements that recover the precision lost under $k$-limiting. By eliminating these infeasible paths before they enter the IFDS propagation, TnFix substantially improves scalability, efficiency, and precision.

At the core of TnFix is a fully field-sensitive data structure called the field points-to graph (FPG), which can be viewed as a nondeterministic finite automaton (NFA). To enable efficient queries, TnFix constructs field-sensitivity-aware DFAs from the NFA. While the CFL-based construction from the program’s supergraph $G^{\ast }$ [34] and its adaptation for taint analysis are detailed in Section 4, the basic idea is intuitive: each DFA encodes the valid field access sequences from a given object, filtering out access paths that violate field sensitivity.

Figure 2 illustrates how TnFix models field sensitivity for our motivating example in Figure 1a. Figure 2(a) shows the FPG derived from the example, where each edge ${\text{O}}_i\stackrel{\text{f}}{\to }{\text{O}}_j$ represents a possible field access O_i.f = O_j. We use ${\text{O}}_{\mathrm{\ell }}$ to denote an object allocated at line $\mathrm{\ell }$. For example, the edge ${\text{O}}_6\stackrel{\text{c}}{\to }{\text{S}}_{28}$ captures the flow at line 29, where the taint source ${\text{S}}_{28}$ (line 28) is written into field c of the Wrapper object ${\text{O}}_6$ allocated at line 6. Other edges are derived analogously from field-access relations in Figure 1a. The edge ${\text{O}}_2\stackrel{\text{m}}{\to }{\text{O}}_{25}$ arises from x.m = p.getAudioFile() at line 21: x may point to the FetchActivity object ${\text{O}}_2$ allocated at line 2, and p.getAudioFile() returns the File object ${\text{O}}_{25}$ allocated at line 25, which is then stored into x.m. Similarly, ${\text{O}}_2\stackrel{\text{w}}{\to }{\text{O}}_6$ captures the initialization of field w in FetchActivity (line 6), where the Wrapper object ${\text{O}}_6$ allocated at line 6 is stored into ${\text{O}}_2$.w; and ${\text{O}}_{10}\stackrel{\text{a}}{\to }{\text{O}}_2$ records the assignment this.a = y in the constructor of Extractor at line 15.

The corresponding NFA ${𝒩}_{\mathrm{fpg}}$ in Figure 2(b) mirrors the structure of the FPG, with all nodes serving as start states. Since ${\text{S}}_{28}$ is the source object, all nodes that can reach it form the accepting set $𝒜=\{{\text{O}}_{10},{\text{O}}_2,{\text{O}}_6,{\text{S}}_{28}\}$. For instance, ${\text{O}}_{10}$ is accepting because it reaches ${\text{S}}_{28}$ along the field sequence awc, whereas ${\text{O}}_{25}$ is rejected because it has no path to the source.

Finally, ${𝒩}_{\mathrm{fpg}}$ is transformed into per-object, field-sensitivity-aware DFAs (as detailed in Section 4.3), as illustrated in Figure 3. Figure 3(a) and Figure 3(b) present the resulting automata for ${\text{O}}_{10}$ and ${\text{O}}_6$, respectively. An object field access of the form O₁₀.$f_1\mathrm{\cdots }{f}_k$ or O₆.$f_1\mathrm{\cdots }{f}_k$ is considered valid only if its sequence of field accesses causes the corresponding DFA to reach an accepting state.

We now revisit the example in Figure 1a to illustrate how TnFix mitigates the over-tainting issue (Figure 1c). Recall that under $k=2$, FlowDroid reports a false leak at line 36 because it propagates taint along the following path analyzed from loadMetadata() (Figure 1b):

TnFix blocks this false leak by consulting its field-sensitivity-aware DFAs, which validate whether an access path $v.f_1\mathrm{\cdots }{f}_k$ is feasible before propagation. At line 17, FlowDroid truncates this.a.w.c to this.a.w due to the access-path limit $k=2$ (② in Figure 1b). TnFix then checks this truncated path against its DFA family ${𝒟}_{\mathrm{fpg}}({\text{this}}_{17})=\{{𝒟}_{\mathrm{fpg}}({\text{O}}_{10})\}$ (Section 4.4). As shown in Figure 3(a), ${𝒟}_{\mathrm{fpg}}({\text{O}}_{10})$ accepts the field sequence aw, transitioning from $\{{\text{O}}_{10}\}$ to $\{{\text{O}}_6\}\in 𝒜$, so propagation is allowed.

At line 34, FlowDroid considers this.f potentially tainted (⑤’ in Figure 1b). TnFix performs a second check using ${𝒟}_{\mathrm{fpg}}({\text{this}}_{34})=\{{𝒟}_{\mathrm{fpg}}({\text{O}}_6)\}$. As shown in Figure 3(b), ${𝒟}_{\mathrm{fpg}}({\text{O}}_6)$ rejects this.f: it transitions from $\{{\text{O}}_6\}$ to $\{{\text{O}}_{25}\}$, a non-accepting state, meaning ${\text{S}}_{28}$ cannot taint this.f under field-sensitive semantics (Section 4.1). TnFix therefore discards this spurious access path, preventing the tainting of file and msg at lines 35–36 and suppressing the false leak reported at line 36 (as indicated by the ✗ symbols at ⑤’ in Figure 1c).

TnFix also reduces unnecessary alias searches by pruning spurious flows. At ⑤ in Figure 1b, FlowDroid taints x.m from p via getAudioFile(), but TnFix rejects this.f at line 32 using ${𝒟}_{\mathrm{fpg}}({\text{this}}_{32})=\{{𝒟}_{\mathrm{fpg}}({\text{O}}_6)\}$ (Figure 3(b)). As a result, x.m is not tainted at line 21 (marked with ✗ at ⑤ in Figure 1c), eliminating all alias searches from ⑤ through ⑦.

Below we highlight three key features of TnFix:

• $\mathrm{■}$

  Staged Field-Sensitive Reasoning. TnFix uses a staged framework that decouples field-sensitive reasoning from IFDS propagation. By validating access paths against lightweight, field-sensitivity-aware DFAs, it filters out spuriously tainted access paths introduced by $k$-limiting in traditional IFDS taint analyses such as FlowDroid.

• $\mathrm{■}$

  Enhanced Efficiency and Scalability. By eliminating spurious taints and pruning unnecessary data flows, TnFix significantly improves the efficiency and scalability of FlowDroid. This is illustrated by the pruned flows at ⑤ and ⑤’, marked with ✗ in Figure 1c.

• $\mathrm{■}$

  Improved Precision. TnFix increases the precision of FlowDroid by removing infeasible flows, preventing the false leak at line 36 that FlowDroid would otherwise report (⑤’ in Figure 1c).

Figure 5 presents the context-free grammar $𝔊$ used to define ${ℒ}_{ℱ}$, a CFL that models Java field accesses as a balanced-parentheses problem, adapted from [40]. Let $ℱ$ denote the set of fields, with each $f\in ℱ$. The grammar includes four kinds of terminals: new (object allocation), assign (assignment), ${[}_f$ (field store), and $]{}_f$ (field load).

The nonterminal flowsto captures how an object $o$ flows into a variable $v$ along a flowsto-path. Intuitively, an object created at a new instruction may flow into a variable through a sequence of direct assignments (assign) or through indirect assignments mediated by matched stores and loads (captured by balanced). Its inverse, $\overline{\text{flowsto}}$, corresponds to the standard points-to relation: $o\text{flowsto}v$ iff $v\overline{\text{flowsto}}o$.

Because $\text{balanced}{\Rightarrow }^{\ast }{{[}_f\overline{\text{flowsto}}\text{flowsto}]}_f$, the composition $\overline{\text{flowsto}}\text{flowsto}$ characterizes the standard alias relation: two variables $x$ and $y$ are aliases iff

We transform the program’s supergraph $G^{\ast }$ into a Pointer Assignment Graph (PAG) $G_{\text{pag}}$, labeling edges with field identifiers drawn from ${ℒ}_{ℱ}$. In $G_{\text{pag}}$, nodes represent variables and objects in $𝒪$, with $𝒮\subseteq 𝒪$ marking source objects for taint analysis. Edges encode data flows induced by assignments (Table 1), object allocations via new, and source introduction via [New] and [Source]. Call and return edges are treated as direct assignments. Every edge $u\stackrel{\ell }{\to }v$ in $G_{\text{pag}}$ is paired with its inverse $v\stackrel{\overline{\mathrm{\ell }}}{\to }u$, enabling bidirectional traversal [40]. This bidirectionality is essential for capturing object flows governed by the balanced relation, which connects the flowsto relation to its inverse, the points-to relation $\overline{\text{flowsto}}$.

To ensure soundness in constructing $G_{\text{pag}}$, we must represent all data flows that are implicitly defined as access paths in taint sources and library code using CFL-reachability.

A Field Points-to Graph (FPG) summarizes the indirect data flows between abstract objects induced by field accesses. Each node $o_i\in 𝒪$ represents an abstract object, and a directed edge $o_i\stackrel{𝑓}{\to }{o}_j$ indicates that the field $o_i.f$ may point to $o_j$.

We construct the FPG by aggregating the reachability results computed over $G_{\text{pag}}$ (Algorithm 2), using the following inference rule:

Intuitively, $o_i\stackrel{{\text{store}}_f}{\to }v$ states that the value in variable $v$ is written into field $f$ of object $o_i$, while $o_j\stackrel{\text{flowsto}}{\to }v$ states that $v$ may point to object $o_j$. Combining these relations yields the field points-to edge $o_i\stackrel{𝑓}{\to }{o}_j$.

As discussed in Section 3.3, the FPG can be viewed as a nondeterministic finite automaton (NFA) ${𝒩}_{\mathrm{fpg}}=(𝒬,ℱ,\delta ,ℐ,𝒜)$. The state space $𝒬=\{o\mid o\in 𝒪\}$ corresponds to the FPG nodes, where $𝒪$ contains all abstract objects and $𝒮\subseteq 𝒪$ denotes the source objects in taint analysis. The alphabet $ℱ$ consists of all field labels. The transition function $\delta :𝒬\times ℱ\to 𝒫(𝒬)$ mirrors the points-to edges: an FPG edge $o_i\stackrel{𝑓}{\to }{o}_j$ becomes a transition from $o_i$ to $o_j$ on input $f$. All objects serve as start states ($ℐ=𝒬$), reflecting that reachability may begin from any object. The accepting states $𝒜$ comprise the source objects and all objects that can reach a source through the FPG.

For the FPG (Figure 2(a)) derived from the motivating example in Figure 1a, the NFA (Figure 2(b)) is defined by $𝒬=\{{\text{O}}_{10},{\text{O}}_2,{\text{O}}_{25},{\text{O}}_6,{\text{S}}_{28}\}$, $ℱ=\{\text{a},\text{m},\text{w},\text{f},\text{c}\}$, and a transition function $\delta$ that directly reflects the FPG edges. All objects in $𝒬$ are start states, and the accepting set is $𝒜=\{{\text{O}}_{10},{\text{O}}_2,{\text{O}}_6,{\text{S}}_{28}\}$.

To support efficient access-path recognition, we convert ${𝒩}_{\mathrm{fpg}}$ into a family of deterministic automata, one per object, denoted ${𝒟}_{\mathrm{fpg}}(o)$, using essentially the standard subset-construction algorithm (Algorithm 3). Rather than constructing each DFA independently, BuildDFAs() computes all per-object DFAs concurrently using a shared transition function ${\delta }^{\prime }$. Line 13 introduces the helper map fields: $𝒪\to 𝒫(ℱ)$, which associates each object $o$ with the set of fields labeling its outgoing edges. This concurrent construction is substantially more efficient: our evaluation (Section 5) shows a geometric-mean speedup of $18.7\times$ across 36 apps compared to building DFAs separately. As a result, TnFix’s field-sensitive reasoning stage remains lightweight and practical, enabling effective reduction of over-tainting in IFDS taint analysis.

Although subset construction can theoretically cause exponential state blowup, in practice the resulting DFA is often smaller than its NFA counterpart – one reason it is widely used in lexical analyzers. In our setting, no such blowup occurs: the number of objects $|𝒪|$ remains modest, with a maximum of 9115 across our benchmark suites (Figure 8).

To determine whether a candidate access path $d_2=v.f_1.\mathrm{\cdots }.f_k$ is spuriously tainted during IFDS taint propagation (line 22 of Algorithm 1), we consult the set of field-sensitivity-aware DFAs associated with $v$, defined as:

An access path $v.f_1.\mathrm{\cdots }.f_k$ is considered valid if its field sequence $f_1.\mathrm{\cdots }.f_k$ is accepted by at least one automaton in ${𝒟}_{\mathrm{fpg}}(v)$. Conversely, if all DFAs in the set reject the sequence, the access path is deemed spurious and is immediately discarded.

Algorithm 4 extends the standard IFDS propagation in Algorithm 1 by modifying Propagate(): line 23 is replaced with line 23a, which invokes Recognize(). This function returns true if $d_2=v.f_1.\mathrm{\cdots }.f_k$ is a valid access path, and false if it is spurious and should be ignored.

To maintain high performance, our implementation does not iterate over individual DFAs. Instead, Recognize() queries the shared transition function ${\delta }^{\prime }$ used by all field-sensitivity-aware DFAs constructed in Section 4.3, allowing the validity of an access-path prefix to be checked efficiently.

We analyze TnFix’s soundness and precision by relating its field-sensitive CFL semantics to the standard CFL-reachability formulation of IFDS [34, 48]. The central goal is to show that (1) TnFix never removes any access path corresponding to a valid IFDS computation (soundness), and (2) under $k$-limiting, TnFix removes only those paths that FlowDroid introduces spuriously due to $k$-limiting (precision).

We assess the overhead introduced by TnFix when reducing FlowDroid’s over-tainting, separating the costs of the field-sensitive reasoning from those of the main IFDS analysis.

We evaluated the time and memory overhead of TnFix’s field-sensitive reasoning stage. Figure 6 shows the absolute and relative reasoning time for each app in Table 2. On average, field-sensitive reasoning accounts for 12.44% of the total analysis time. The most time-consuming case, org.fdroid.fdroid, took 18.1 seconds, only 4.6% of its total. The highest percentage occurred in org.openpetfoodfacts.scanner at 75.6%, with a reasoning time of 3.1 seconds. Among the four excluded apps due to scalability limits, the time from field-sensitive reasoning ranged from 2.7 seconds (de.k3b.android.androFotoFinder) to 82.4 seconds (fr.gouv.etalab.mastodon), averaging 24.1 seconds. Note that Table 2 includes the reasoning cost in total time, yet TnFix still achieves an average speedup of 2.5$\times$, showing that the field-sensitive reasoning stage adds little overhead.

Figure 7 reports memory usage during the field-sensitive reasoning stage for the apps in Table 2. The highest consumers are org.gateshipone.odyssey (1925  MB), org.fdroid.fdroid (1679  MB), and com.fastaccess.github.libre (1539  MB). Their peak memory footprint during the main analysis increases to 3871, 4198, and 1665  MB, respectively.

Overall, TnFix’s field-sensitive reasoning stage is substantially less memory-intensive. TnFix adopts an aggressive memory-management strategy that releases intermediate data structures as soon as they are no longer needed. For example, once DFA construction completes (Algorithm 3), TnFix discards $G_{\text{pag}}$, which is required only during the initial FPG construction.

Figure 8 reports the number of objects $|𝒪|$ in $G_{\text{pag}}$ for each app after solving the field-sensitive CFL-reachability problem (Algorithm 2). The average is 2619, and the maximum, 9115, occurs in com.adobe.reader. These results confirm that the number of per-object DFAs constructed by TnFix remains well within manageable bounds (Section 4.6).

Figure 9 then quantifies the proportion of edges added to $G_{\text{pag}}$ to capture implicitly defined data flows derived from taint sources (#TaintSourceEdges/Total) and library summaries (#LibraryEdges/Total), as detailed in Section 4.1. The most edges added for taint sources, 62504, are in org.gateshipone.odyssey, which has 44 taint sources, while the peak for library summaries, 205510 edges, is at org.fdroid.fdroid, which has 7928 objects. Capturing these flows is crucial for TnFix’s soundness and effectiveness in reducing over-tainting in IFDS taint analysis.

To empirically validate TnFix’s soundness and precision, complementing the guarantee in Theorem 3, we used two benchmark suites: (1) DroidBench [42], the standard suite for FlowDroid, and (2) TaintBench [27], a recent real-world Android malware benchmark. On DroidBench (119 apps), with the default source-sink setup, TnFix and FlowDroid produced identical results. For TaintBench (39 apps), we evaluated both suite-level and app-level source-sink configurations, excluding six apps that crashed FlowDroid. For the rest, both tools reported the same expected taint flows, confirming that TnFix preserves FlowDroid’s precision and recall. As expected, on these micro-benchmarks, TnFix matches FlowDroid’s precision.

In practical scenarios involving real-world apps listed in Table 2, TnFix demonstrated improved precision over FlowDroid by effectively eliminating false-positive warnings. Specifically, TnFix reduced false leak warnings in 13 out of 29 scalable-group apps. On average, TnFix decreased leak warnings by 12.2% across apps analyzable by both tools, achieving the most substantial reduction (5) in the app org.secuso.privacyfriendlyweather.

We manually inspected the removed leaks in the 13 apps where TnFix reports fewer leaks and confirmed that these removed warnings were false positives arising from field mismatches due to FlowDroid’s access-path truncation.

For instance, in org.openpetfoodfacts.scanner, a false positive reported by FlowDroid stems from a taint through the Android API queryIntentActivities(), propagated through eight field accesses. Due to $k=5$, FlowDroid truncates the access path at 5 fields, with the last being <bd: MainActivity a>. Subsequent loads lead to a false positive at the sink from <MainActivity: boolean G>. TnFix excludes this by verifying that <MainActivity: boolean G> is not field-sensitively reachable from any source. Similarly, TnFix corrects false positives in com.kanedias.vanilla.metadata. Inspired by these patterns, we designed the example in Figure 1 to motivate our approach, detailed in Section 3.

In industry settings, reducing false positives is crucial. TnFix’s pruning reduces analysis, allowing developers to focus on real issues instead of false alarms.

In Table 2, TnFix significantly outperforms FlowDroid by analyzing all 36 apps within a 3-hour time budget. For the 7 apps where FlowDroid timed out, TnFix completed analysis in 1750 seconds. Speed improvements for the other 29 apps varied from 0.7$\times$ (com.github.yeriomin.dumbphoneassistant) to 1622.8$\times$ (org.openpetfoodfacts.scanner), with an average of 2.5$\times$. This variance indicates that smaller apps, which are already efficiently analyzed by FlowDroid, are less affected by over-tainting; in such cases, TnFix’s recognizer overhead may not be fully amortized by pruning, leading to marginal slowdowns. In contrast, larger apps often exhibit more severe over-tainting from spuriously generated access paths, where TnFix’s pruning substantially reduces propagation and analysis time.

Real-world Android apps often exhibit common patterns – such as mutual references between activities, recursive data structures, and inner-class cycles – that exacerbate over-tainting when $k$-limiting is applied. In such cases, spurious access paths can proliferate, inflating analysis overhead. Our experiments show that for these large apps, increasing $k$ further offers little to no benefit in terms of precision and scalability (RQ4). TnFix effectively eliminates these spurious access paths using lightweight filtering, enabling faster analysis for large apps with the default $k=5$, a widely adopted setting for balancing precision and scalability [10, 1, 9, 8].

The scalability of TnFix primarily results from a significant reduction in the number of path edges processed. We observe strong positive correlations between this reduction and decreases in analysis time and memory usage. Figure 10 shows a correlation coefficient of 0.957 between $\frac{\text{FlowDroid}\text{’s\hspace{0.33em}\#PathEdge}}{\text{TnFix}\text{’s\hspace{0.33em}\#PathEdge}}$ and $\frac{\text{FlowDroid}\text{’s\hspace{0.33em}Analysis\hspace{0.33em}Time}}{\text{TnFix}\text{’s\hspace{0.33em}Analysis\hspace{0.33em}Time}}$, and 0.835 between $\frac{\text{FlowDroid}\text{’s\hspace{0.33em}\#PathEdge}}{\text{TnFix}\text{’s\hspace{0.33em}\#PathEdge}}$ and $\frac{\text{FlowDroid}\text{’s\hspace{0.33em}Memory\hspace{0.33em}Usage}}{\text{TnFix}\text{’s\hspace{0.33em}Memory\hspace{0.33em}Usage}}$, computed using scipy’s pearsonr function in Python 3.

The considerable reduction in path edges is due to TnFix eliminating spuriously tainted access paths. Figure 11 shows the percentage reduction of access paths in TnFix compared to those processed by FlowDroid for each app listed in Table 2, averaging a reduction of 31.65%.

Early pruning in IFDS is especially effective because the tabulation algorithm is path-edge driven (Algorithm 1). Once a spurious access path is placed on the worklist, it is propagated through normal, call, and return flow functions, generating cascades of derived path edges (lines 8–21). Even if a post-hoc filter were able to discard the resulting data facts, the solver would still incur the full cost of producing and processing all intermediate path edges. In contrast, TnFix performs recognition exactly at the point where an access path is about to be propagated (Algorithm 4), rejecting many spurious access paths before they ever enter the worklist. By preventing these access paths from triggering downstream propagation, TnFix avoids the explosion of path edges caused by $k$-limited over-tainting. This explains why comparatively modest reductions in access-path counts (Figure 11) yield disproportionately large reductions in path edges, analysis time, and memory usage (Figure 10).

To improve efficiency under $k$-limiting, FlowDroid uses a type-based heuristic to truncate recursive fields, enabling longer access paths but increasing false positives. Without it, over-tainting worsens due to strict $k$-field limits. TnFix still achieves a $2.5\times$ speedup on 23 commonly analyzable apps, scales to 9 more, and reduces false positives by 17.4%. For compatibility, TnFix conservatively avoids pruning such over-approximated paths, preserving soundness and scalability.

To examine the sensitivity of TnFix to the access-path limit $k$, we evaluated TnFix and FlowDroid under $k\in \{1,3,5,7\}$, with results summarized in Table 3. FlowDroid uses $k=5$ by default because $k$-limiting exposes a precision–efficiency tradeoff: smaller limits () aggressively collapse access paths, increasing alias imprecision and false positives, whereas larger limits ($k>5$) preserve more field information but introduce more access-path facts, increasing runtime and memory consumption. TnFix remains effective across these settings by validating access paths semantically before propagation.

The results in Table 3 are consistent with this tradeoff, and the speedup trend is not necessarily monotonic. At smaller $k$, aggressive truncation amplifies over-tainting, allowing TnFix to achieve larger precision gains by removing false positives, as shown by the 21.5% leak reduction at $k=1$. At larger $k$, FlowDroid preserves longer access paths but incurs higher propagation cost. By validating access paths semantically using field-sensitive CFL-reachability, TnFix mitigates both sources of overhead and achieves consistent average speedups across $k$.

Overall, these results highlight a fundamental distinction between the two designs. Increasing $k$ in FlowDroid extends access paths only syntactically and still conflates distinct heap locations in recursive or deeply nested structures, allowing over-tainting to persist. In contrast, TnFix validates access paths semantically using field-sensitive CFL-reachability, independent of the chosen $k$. Since recursive structures prevent any finite $k$ from eliminating over-tainting, TnFix systematically mitigates it for any fixed $k$, adding a new precision dimension orthogonal to the traditional choice of access-path limit in IFDS taint analysis.

The IFDS framework [34] and its IDE extension [36] form the foundation of precise interprocedural dataflow analysis. Naeem et al. [30] later introduced dynamic exploded-supergraph construction, and these frameworks have since been integrated into major compiler infrastructures such as WALA [46], SootUp [16], and LLVM [17, 37].

To reduce the computational and memory overhead of IFDS/IDE analyses, prior work has proposed a range of optimizations. Reviser [2] supports incremental IDE analysis by selectively clearing and recomputing only information affected by code changes, thereby avoiding full recomputation while preserving equivalent results. SparseDroid [10] and Sparse IDE [15] employ sparse propagation, restricting computation to relevant program points along def-use chains. DiskDroid [19] reduces memory pressure through disk-assisted storage and recomputation, while DStream [48] adopts a streaming-based out-of-core model with fine-grained parallelism. MergeDroid [8] consolidates equivalent value flows to reduce redundant alias queries. CleanDroid [1] and Fpc [9] reclaim memory during fixpoint computation using method-level and data-fact-level garbage-collection policies, respectively.

A separate line of work investigates alternatives to standard access-path propagation. IFDS-APA [18] avoids $k$-limiting by grouping access paths by base variable and reconstructing full paths on demand. IFDS-APA targets Java rather than Android and its implementation is not fully available, which precludes a direct empirical comparison. While this design improves memory scalability, its precision and efficiency gains are modest because it does not eliminate spurious paths; it only stores them more compactly. IDEDroid [20] improves performance by propagating only base variables and generating access paths via a CFL formulation inside an IDE solver. Although this yields notable speedups and some precision improvement over FlowDroid, it still constructs access paths syntactically and does not prevent infeasible field sequences from flowing through the analysis.

TnFix differs fundamentally from these approaches. It is the first technique to directly mitigate over-tainting in IFDS taint analysis for Android apps by enforcing semantic field sensitivity: it constructs a global Field Points-to Graph (FPG) via field-sensitive CFL-reachability and compiles it into per-object deterministic finite automata that recognize exactly the realizable field sequences in the heap. These DFAs act as on-the-fly filters during IFDS propagation, eliminating spurious access paths before they enter the solver. No prior IFDS/IDE optimization – including IFDS-APA and IDEDroid – builds such per-object DFAs or uses automata-guided pruning to remove infeasible paths during propagation.

As shown in our evaluation, this semantic pruning is crucial: it substantially improves FlowDroid’s scalability, efficiency, and precision and enables successful analysis of apps that FlowDroid cannot complete within a three-hour budget.

Numerous static taint-analysis tools have been proposed for Android, addressing challenges such as lifecycle modeling, callbacks, libraries, and inter-component communication. CHEX [25] detects component-hijacking vulnerabilities, such as permission leakage and intent spoofing, using customized system dependence graphs and reachability tests. Amandroid [49] computes flow- and context-sensitive points-to information for individual components and stitches component-level results to support inter-component and inter-app analysis. IccTA [21] focuses on inter-component communication by propagating context information across components to identify cross-component privacy leaks. FlowDroid [4] provides lifecycle-aware IFDS taint analysis for Android, achieving high precision through context-, flow-, field-, and object-sensitive reasoning. DroidSafe [7] improves soundness by modeling the Android runtime and resolving dynamic communication targets. DroidInfer [12] uses a context-sensitive information-flow type system based on CFL-reachability. Heapster [5] augments FlowDroid with runtime heap snapshots to improve precision and efficiency. Among these, FlowDroid remains the most widely adopted and serves as the baseline for evaluating TnFix.

CFL-reachability originated in database theory [50] and has become foundational in program analysis [32], supporting pointer analysis [40, 51], shape analysis [32], slicing [35, 41], and information-flow analysis [4]. Recent work uses refined CFLs to enhance context sensitivity: Eagle [24] boosts $k$-object-sensitive pointer analysis using selective context sensitivity, while FlowCFL [29] reduces inverse edges via type-based annotations.

TnFix differs in focus: it applies CFL-reachability specifically to mitigate over-tainting in IFDS-based Android taint analysis by validating field-sensitive access paths.

For multiple CFL constraints, SPDS [38] intersects constraints using separate pushdown automata. This deferred pruning requires enumerating infeasible paths, increasing overhead and false positives. Boomerang [39] uses access graphs for field sensitivity, with recursion bounding to ensure termination; however, this merging of recursive structures can reduce precision. In contrast, TnFix uses per-object DFAs derived from a global FPG to prune infeasible paths during propagation, avoiding deferred intersection and arbitrary recursion bounds.

Finally, TnFix integrates Android-specific taint-flow semantics – such as sub-field tainting and StubDroid library summaries (Section 4.1 and Algorithm 2 lines 9–13) – directly into its CFL and DFA formulation. SPDS and Boomerang focus on Java pointer analysis and do not support Android taint analysis, precluding a direct empirical comparison in our setting.