REVIEW 4 major objections 7 minor 31 references
Scalable Language Agnostic Taint Tracking using Explicit Data Dependencies
T0 review · 4 major / 7 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read A taint-tracking engine can detect vulnerabilities without library source code by over-approximating unknown calls, and its users sharpen results later by adding semantics without re-analysis.
desk verdict A genuinely useful stable-DDG design with query-time semantics, but the 'safely overapproximate' claim is too strong given the admitted aliasing and heap gaps. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the explicit data-dependence graph (DDG), a graph whose edges go from nodes that define a variable to nodes that use it without an intervening redefinition. The engine constructs this graph on top of a code property graph, treating all callees as external and giving each call site over-approximated argument-to-argument data flows; a small set of special indices lets users write annotations such as receiver-to-receiver and receiver-to-return flows to state which flows survive. At query time, a demand-driven backward or forward traversal solves per-method tasks on worker threads, checks each parent edge against the supplied semantics, caches results, and stops at a maximum call depth to guarantee termination. The stable graph plus query-time semantics is what lets annotations be added without recalculation.
What would settle it
Run the engine on a small program where taint is written into a field of a heap object through one reference and later read through a different alias, with the tainted value reaching a sink at runtime; if the engine reports no flow, the over-approximation claim is false for flows the representation does not encode.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that a whole-program data-dependence graph can be kept stable while knowledge of library semantics grows. Every callee is treated as external with unknown semantics, so each call site over-approximates data dependencies by assuming any input may taint any output. The resulting graph contains invalid paths, but those paths are filtered at query time using user-supplied flow semantics for specific methods, so the graph itself never has to be recomputed when semantics are added. The paper states that adding such summaries is not required to discover additional flows but helps eliminate false positives. The evaluated engine is reported to identify the most vulnerabilities among the compared tools, with additional false positives, and to scale well enough for partial-program analysis of modern programs.
Load-bearing premise
The approach only catches taint that travels through explicit variable definitions and uses; if taint moves through aliased objects or shared mutable state, the graph has no edge for that path and the tool will miss the flow, a limitation the paper states openly.
Editorial extensions
If this is right
- With no user-supplied semantics at all, the engine still reports flows from sources to sinks, so partial-program taint analysis can run before library dependencies are available or understood.
- Adding or refining library semantics reduces false positives on a later query without re-analyzing the program, which suits continuous integration pipelines with tight analysis budgets.
- The maximum call depth is a widening step: paths deeper than the limit are over-approximated, trading precision for guaranteed termination.
- Whole-program analysis costs considerably more runtime for only a small precision gain, so the partial-program setting is the intended operating point.
- Because the same graph construction and query machinery works across Java, Python, and JavaScript, the approach is language-agnostic in principle and demonstrated on those three languages.
Reading between the lines
- A natural consequence is that the tool's recall is fixed by what the graph encodes: any real flow that depends on aliasing or heap shape can only appear if the representation gains those edges, since summaries alone cannot invent new paths.
- The incremental-semantics property suggests a practical workflow in which heuristic or learned summaries are generated programmatically and loaded on the fly until query results stop changing, without re-running the full analysis.
- The evaluation's comparison suggests that partial-program analysis may be the right deployment mode for continuous pipelines, but the missing alias and heap sensitivity means results should be treated as candidate flows for triage rather than proof of absence.
- A natural experiment would measure how much semantic annotation is needed on a large real-world codebase to match the precision of whole-program analysis, quantifying the precision gap this paper reports.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper presents a design and implementation of a taint-analysis engine for the Joern code-analysis platform. The engine builds a whole-program data-dependence graph (DDG) and, for calls to procedures whose code is unavailable or unannotated, over-approximates data flow by assuming every input may taint every output. Users can provide semantic summaries for such external calls at query time; these summaries filter invalid paths without requiring the DDG to be recomputed. The evaluation compares Joern (with and without user semantics) against Semgrep and CodeQL on Java (Securibench Micro), Python (Thorat), and JavaScript (securibench-micro.js) benchmarks, and measures scalability on Defects4j and BugsInPy. The paper reports that Joern finds the most true positives at the cost of additional false positives, and contributes two new benchmark datasets and an open-source implementation.
Significance. The incremental-annotation property is potentially valuable: if the DDG is a sound over-approximation of all real data flows, then users can add library semantics and immediately get fewer false positives without re-analysis, which is attractive for CI pipelines. The paper also contributes reproducible benchmarks and integrates with a widely used open-source platform. However, the evaluation does not fully establish the claimed over-approximation; Section 4 concedes that aliasing and heap-allocated data structures are not tracked (weak updates only), so true flows can be absent from the DDG. The k-limit in Algorithm 1 is another source of possible false negatives. These gaps are not merely theoretical, and the benchmark suite may not exercise them, so the comparative results should be read with caution.
major comments (4)
- [3.1, 4] The paper's core design claim is that treating all callees as external with unknown semantics and over-approximating data dependencies at each call site 'safely overapproximate[s] the data flow' (Section 3.1), so that 'adding such summaries is not required to discover additional flows but helps eliminate false positives.' This is only correct if every real data flow has a corresponding path in the DDG. Section 4 states that 'aliasing and the heap of data structures are not tracked' and that assignments propagate flow 'only via weak updates.' Under weak updates, a write through one alias need not create a dependence edge to a later read through another alias, so a true taint path can be absent from the graph and no amount of added summaries can recover it. The engine is therefore not a may analysis over real executions for such flows; it is incomplete. The limitation is described as 'imprecision,' but it is actually a source of false negatives. Please either restrict the over-approximation claim to flows representable in the modeled graph, or extend the analysis to handle heap and aliasing soundly, or provide experimental evidence that the evaluated benchmarks (and the intended real-world workload) do not contain such flows.
- [3.2, Algorithm 1] The maximum call depth k_max terminates task generation at line 3-4 of Algorithm 1. When the depth limit is reached, no new tasks are created from a partial result; the text says 'flows will be over-approximated for dependent callers of this result,' but in fact sources that are more than k_max call edges away from the sink are never reached. For example, with k_max=1, a source in main() cannot be matched to a sink in a method called by main through an intermediate call, because the task from the parameter of the intermediate method to the call site in main is not created. This is an additional source of false negatives and contradicts the description of the analysis as a 'may analysis' (Section 3) and the 'safely overapproximate' phrasing. The paper should state explicitly that k_max introduces incompleteness, and should quantify the effect of k on recall/precision (e.g., in Figure 2) as part of the accuracy discussion.
- [5.3, Table 1] The maximum call depth k=5 is chosen by scanning k over exactly the same three benchmarks (Securibench Micro, Thorat, securibench-micro.js) on which the final results in Table 1 are reported, with no held-out data or cross-validation. Any monotone relationship between k and the J/F1 metrics makes the reported numbers optimistically biased. The paper should either report the full k-sweep curves for all benchmarks and select k on a separate tuning set, or present results for a range of k values and discuss the sensitivity of the comparative claims to this choice.
- [5.4, 5.5] The Joern_SEM configuration uses 'manually specified semantics' but the paper does not describe which library calls were annotated, how many annotations were written, or whether they were authored before or after examining the expected outcomes of the benchmarks. If these semantics were tuned to the test set, the precision improvement (e.g., Securibench Micro false positives decreasing from 36 to 17) is not evidence of a general benefit. The paper should document the semantics, their provenance, and ideally validate on an independent set of programs.
minor comments (7)
- [Section 2] The phrase 'the possible data dependency between result at the call to bar and its occurrence at the call to Sink.addValue is indicated by a path' is unclear; consider rewriting for readability.
- [Figure 1] The labels 'DDG' appear on multiple edges without distinguishing edge types; a legend or distinct arrow styles would improve clarity.
- [Section 5.1] 'All experiments [3] were performed on a platform' attaches citation [3] (a dataset DOI) to a hardware description; rephrase to avoid implying the hardware is part of the dataset. Also state the versions and taint-mode configurations of Semgrep and CodeQL.
- [Algorithm 2] The result table R* is described as a set, but line 6 uses R*[s0] as a map; clarify whether results are keyed by start node and define what 'prepend known path' means precisely.
- [Section 5.2] For the new Thorat and securibench-micro.js datasets, state how ground truth was established and whether the labels were independently validated; this is important since the datasets are a contribution of the paper.
- [Table 1] Runtime and memory values for Semgrep are shown without any spread; state whether these are single runs or include variance as for the other tools.
- [Conclusion] The conclusion says semantics can be added 'without having to re-analyze the dependencies,' but the evaluation does not directly demonstrate the incremental workflow; a small experiment timing a query with and without a new semantic would strengthen this claim.
Circularity Check
The architecture is not circular, but the empirical precision comparison is partly fitted: k=5 is tuned on the same benchmarks later used for evaluation, and the manual library semantics used by Joern_SEM define away false positives by construction.
-
fitted input called prediction
[Section 5.3, 'Determining a Suitable Analysis Depth'; Section 5.4, 'Taint Analysis']
"Thus, to strike a balance between precision and recall while remaining practical, we determine thatk=5is a safe value fork. ... This section outlines Joern’s performance with the presented data-flow engine, using a max call depth k=5, for the three benchmarks against Semgrep and CodeQL."
The maximum call depth k is selected by inspecting the J index and F1 score on the same taint-analysis benchmarks (Securibench Micro, Thorat, securibench-micro.js) that Section 5.4 and Table 1 then present as the evaluation. The reported vulnerability counts and precision metrics are therefore in-sample values for a configuration chosen to maximize those very metrics, rather than out-of-sample predictions from an independent test setting. The headline conclusion that the Joern-based analysis 'can identify the most vulnerabilities' is thus partially forced by the tuning step, not an independent empirical finding.
-
fitted input called prediction
[Section 3.1, 'Data-Dependence Representation'; Section 5.4, 'Taint Analysis'; Section 5.5, 'Discussion']
"Any unspecified flows will be interpreted as killed or sanitized, i.e., no flow exists between the input and output node. ... While the user-defined semantics have been shown to reduce false positives without needing to rerun the analysis, the lack of precision for dynamic languages leaves room for future work."
The Joern_SEM configuration adds 'manually curated semantics for external procedure calls' that are specific to the evaluated benchmarks. Because the semantics definitionally kill every flow not explicitly listed, removing spurious paths and reducing false positives is a direct consequence of writing semantics that exclude those paths for the benchmark's library calls. The measured false-positive reduction is therefore partly an artifact of the hand-tuned, benchmark-specific annotations rather than an independent demonstration that incremental semantics generally improve precision. This does not invalidate the architecture, but it makes the precision claim weaker than presented.
full rationale
The paper's architectural contribution—a stable data-dependence graph with over-approximated call semantics, refined only at query time—is not itself circular: it is an engineering design implemented in Joern, and the comparison against Semgrep and CodeQL is external to the paper's fitted parameters. I found no load-bearing self-citation chain: the citations to Horwitz et al., Yamaguchi et al., and the Joern platform are standard foundations, not uniqueness theorems that force the design. The main circularity concern is empirical. In Section 5.3, k=5 is chosen by inspecting J index and F1 score on the same taint-analysis benchmarks that Table 1 later presents as the evaluation, so the headline vulnerability-count and F1 results are in-sample rather than out-of-sample predictions. Similarly, the Joern_SEM false-positive reduction is obtained by manually curating semantics for the specific external calls in those benchmarks, and Section 3.1 defines unspecified flows as killed; the measured FP drop is therefore partly baked into the annotation definition and the benchmark-specific tuning. The Section 4 admission that 'aliasing and the heap of data structures are not tracked' and that assignments propagate flow 'only via weak updates' is a genuine soundness gap for the 'safely overapproximate' wording, but I treat that as a correctness risk rather than as a circular step, because it concerns the faithfulness of the representation, not a claim that reduces to its inputs. The omitted k-curves in Section 5.3 further weaken verifiability of the tuning step. Overall, the central design has independent content, but the reported precision comparison is partially fitted to the evaluation data, so the score is 4 rather than 0.
Assumptions & free parameters
free parameters (3)
- k (max call depth) =
5
- Joern_SEM semantic annotations =
e.g., 'Obj.transform: Obj(Obj)' with flows 0->0 0->-1
- Default operator/call semantics =
unspecified defaults for operators, assignments, field accesses
assumptions (4)
- domain assumption Unknown callees are assumed to allow every input parameter to taint every output parameter and the return value.
- domain assumption The PDG-based data-dependence graph, with operators and field accesses modeled as ordinary call nodes, captures every data flow relevant to taint vulnerability.
- domain assumption k-limiting at maximum call depth preserves all true source-to-sink flows, adding only spurious paths.
- domain assumption Benchmark labels (source, sink, expected outcome) are correct ground truth for taint vulnerabilities.
Cite this review
Pith. "Pith review of Scalable Language Agnostic Taint Tracking using Explicit Data Dependencies." pith.science (2026). https://pith.science/paper/ZBVKRYQJ
@misc{pith2026250606247,
author = {Pith},
title = {Pith review of: Scalable Language Agnostic Taint Tracking using Explicit Data Dependencies},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZBVKRYQJ}},
note = {Machine review of arXiv:2506.06247}
}
read the original abstract
Taint analysis using explicit whole-program data-dependence graphs is powerful for vulnerability discovery but faces two major challenges. First, accurately modeling taint propagation through calls to external library procedures requires extensive manual annotations, which becomes impractical for large ecosystems. Second, the sheer size of whole-program graph representations leads to serious scalability and performance issues, particularly when quick analysis is needed in continuous development pipelines. This paper presents the design and implementation of a system for a language-agnostic data-dependence representation. The system accommodates missing annotations describing the behavior of library procedures by over-approximating data flows, allowing annotations to be added later without recalculation. We contribute this data-flow analysis system to the open-source code analysis platform Joern making it available to the community.
Figures
Reference graph
Works this paper leans on
-
[1]
2025.securibench-micro.js Dataset
Sedick David Baker Effendi. 2025.securibench-micro.js Dataset. Stel- lenbosch University. doi:10.5281/zenodo.15396620
-
[2]
Sedick David Baker Effendi. 2025.Thorat Dataset. Stellenbosch Uni- versity. doi:10.5281/zenodo.15396362
-
[3]
Sedick David Baker Effendi and Andrei Michael Dreyer. 2025.Joern Benchmarks. Joern Open-Source Community. doi:10.5281/zenodo. 15396731
doi:10.5281/zenodo 2025
- [4]
-
[5]
Ella Bounimova, Patrice Godefroid, and David Molnar. 2013. Billions and billions of constraints: Whitebox fuzz testing in production. In Proc. of the International Conference on Software Engineering (ICSE). IEEE Press, San Francisco, CA, USA, 122–131. doi:10.1109/ICSE.2013. 6606558
-
[6]
Saikat Chakraborty, Rahul Krishna, Yangruibo Ding, and Baishakhi Ray. 2021. Deep learning based vulnerability detection: Are we there yet.IEEE Transactions on Software Engineering48, 09 (2021), 3280–3296. doi:10.1109/TSE.2021.3087402
arXiv 2021
- [7]
-
[8]
Jeanne Ferrante, Karl J Ottenstein, and Joe D Warren. 1987. The pro- gram dependence graph and its use in optimization.ACM Transactions on Programming Languages and Systems (TOPLAS)9, 3 (1987), 319–349. doi:10.1145/24039.24041
arXiv 1987
Show all 31 references
-
[9]
Martin Fowler, Jim Highsmith, et al. 2001. The agile manifesto.Software development9, 8 (2001), 28–35
2001
-
[10]
GitHub, Inc. 2024. CodeQL (Version 2.19.2).https://codeql.github.com. Retrieved June 2024
2024
-
[11]
Salvatore Guarnieri, Marco Pistoia, Omer Tripp, Julian Dolby, Stephen Teilhet, and Ryan Berg. 2011. Saving the world wide web from vul- nerable JavaScript. InProceedings of the 2011 International Sympo- sium on Software Testing and Analysis(Toronto, Ontario, Canada). Associati...
2011
-
[12]
Bill Holz and Mike West. 2019. Results Summary: Agile in the En- terprise (Updated).https://circle.gartner.com/Portals/.../Summary% 20(updated).pdf. Retrieved July 2021
2019
-
[13]
Susan Horwitz, Thomas Reps, and David Binkley. 1990. Interprocedural slicing using dependence graphs.ACM Transactions on Programming Languages and Systems (TOPLAS)12, 1 (1990), 26–60. doi:10.1145/ 77606.77608
1990
-
[14]
Joern Community. 2024. Joern (Version 4.0.119).https://github.com/ joernio/joern. Retrieved October 2024
2024
-
[15]
Neil D Jones and Steven S Muchnick. 1979. Flow analysis and optimiza- tion of LISP-like structures. InProceedings of the 6th ACM SIGACT- SIGPLAN symposium on Principles of programming languages. As- sociation for Computing Machinery, San Antonio, Texas, 244–256. doi:10.1145/56...
1979
-
[16]
René Just, Darioush Jalali, and Michael D Ernst. 2014. Defects4J: A database of existing faults to enable controlled testing studies for Java programs. InProceedings of the 2014 international symposium on software testing and analysis. Association for Computing Machinery, New ...
2014
-
[17]
Soheil Khodayari and Giancarlo Pellegrino. 2021. JAW: Studying Client- side CSRF with Hybrid Property Graphs and Declarative Traversals. In Proc. of USENIX Security Symposium. USENIX Association, Vancouver, B.C., 2525–2542
2021
-
[18]
James C King. 1976. Symbolic execution and program testing.Commun. ACM19, 7 (1976), 385–394. doi:10.1145/360248.360252
1976
-
[19]
Jie Liang, Mingzhe Wang, Yuanliang Chen, Yu Jiang, and Renwei Zhang
-
[20]
Benjamin Livshits. 2006. Securibench Micro.https://github.com/ too4words/securibench-micro. Retrieved May 2024
2006
-
[21]
Vijay Krishna Palepu, Guoqing Xu, and James A Jones. 2017. Dynamic dependence summaries.ACM Transactions on Software Engineering and Methodology (TOSEM)25, 4 (2017), 1–41. doi:10.1145/2968444
2017 doi
-
[22]
Corina S Păsăreanu and Willem Visser. 2009. A survey of new trends in symbolic execution for software testing and analysis.International journal on software tools for technology transfer11, 4 (2009), 339–353. doi:10.1007/s10009-009-0118-1
2009 doi
-
[23]
Thomas Reps, Susan Horwitz, and Mooly Sagiv. 1995. Precise in- terprocedural dataflow analysis via graph reachability. InProc. of the Symposium on Principles of programming languages (POPL). As- sociation for Computing Machinery, New York, NY, USA, 49–61. doi:10.1145/199448.199462
1995
-
[24]
Oscar Rodriguez-Prieto, Alan Mycroft, and Francisco Ortin. 2020. An efficient and scalable platform for java source code analysis using overlaid graph representations.IEEE Access8 (2020), 72239–72260. doi:10.1109/ACCESS.2020.2987631
2020
-
[25]
Semgrep, Inc. 2024. Semgrep (Version 1.95.0).https://semgrep.dev. Retrieved May 2024
2024
-
[26]
Rajiv Thorat. 2022. Benchmark For Taint Analysis Tools Python. https://github.com/rajiv-thorat/benchmark-for-taint-analysis-tools- for-python. Retrieved May 2024
2022
-
[27]
John Toman and Dan Grossman. 2017. Taming the static analysis beast. In2nd Summit on Advances in Programming Languages (SNAPL 2017). Schloss-Dagstuhl-Leibniz Zentrum für Informatik, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 18:1–18:14. doi:10.4230/L...
2017 doi
-
[28]
Ratnadira Widyasari, Sheng Qin Sim, Camellia Lok, Haodi Qi, Jack Phan, Qijin Tay, Constance Tan, Fiona Wee, Jodie Ethelda Tan, Yuheng Yieh, et al. 2020. BugsInPy: A Database of Existing Bugs in Python Programs to Enable Controlled Testing and Debugging Studies. In Proceedings ...
2020
-
[29]
Fabian Yamaguchi, Nico Golde, Daniel Arp, and Konrad Rieck. 2014. Modeling and discovering vulnerabilities with code property graphs. InProc. of IEEE Symposium on Security and Privacy. IEEE Computer Society, Los Alamitos, CA, USA, 590–604. doi:10.1109/SP.2014.44
2014 doi
-
[30]
William J Youden. 1950. Index for rating diagnostic tests.Can- cer3, 1 (1950), 32–35. doi:10.1002/1097-0142(1950)3:1<32::aid- cncr2820030106>3.0.co;2-3 Conference’17, July 2017, Washington, DC, USA Sedick David Baker Effendi, Xavier Pinho, Andrei Michael Dreyer, and Fabian Yam...
1950
-
[2018]
InIEEE Inter- national Conference on Software Analysis, Evolution and Reengineering (SANER)
Fuzz testing in practice: Obstacles and solutions. InIEEE Inter- national Conference on Software Analysis, Evolution and Reengineering (SANER). IEEE Computer Society, Los Alamitos, CA, USA, 562–566. doi:10.1109/SANER.2018.8330260
2018
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.