Scalable Language Agnostic Taint Tracking using Explicit Data Dependencies CCS: Software and its engineering Software testing and debugging CCS: Software and its engineering Formal software verification

Sedick David Baker Effendi, Xavier Pinho, Andrei Michael Dreyer, Fabian Yamaguchi · 2025

Read Scalable Language Agnostic Taint Tracking using Explicit Data Dependencies CCS: Software and its engineering Software testing and debugging CCS: Software and its engineering Formal software verification by Sedick David Baker Effendi, Xavier Pinho, Andrei Michael Dreyer, Fabian Yamaguchi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06247.txt.

Introduction

Sedick Baker Effendi and three co-authors present in 2025 a language-agnostic system for taint tracking, a way to follow untrusted data through a program to find security flaws. Their approach builds whole-program data-dependence graphs, which are powerful but face two walls: library behavior needs hand-written notes, and the graphs grow huge.

The new design over-approximates flows through libraries whose notes are missing, so notes can be added later without redoing the analysis. Because the representation ignores language quirks, one engine serves many languages. The system joins the open-source Joern platform for public use. Faster, scalable taint analysis fits the quick cycles of modern development pipelines, where security checks often get squeezed out.

Catalog record

CREATORSedick David Baker Effendi, Xavier Pinho, Andrei Michael Dreyer, Fabian Yamaguchi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-06247

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Scalable Language Agnostic Taint Tracking using Explicit Data Dependencies CCS: Software and its engineering Software testing and debugging CCS: Software and its engineering Formal software verification Sedick David Baker Effendi, Xavier Pinho, Andrei Michael Dreyer, Fabian Yamaguchi 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. † † cc-license: by 1. Introduction Continuous integration and deployment ( Fowler et al. 2001 ) are now standard in many organizations ( Holz and West 2019 ) , but achieving continuous vulnerability detection without slowing down the release process remains an ambitious goal. Vulnerability discovery techniques such as symbolic execution ( King 1976 ; Păsăreanu and Visser 2009 , e.g.) or fuzz testing ( Bounimova et al. 2013 ; Liang et al. 2018 , e.g.) fall short in this environment, as they assume a relatively static target. Expensive state exploration, however, stands in direct conflict with the need for quick feedback in modern pipelines. Researchers have explored using graph databases to store and process whole-program representations of code ( Rodriguez-Prieto et al. 2020 ) . In this context, explicit data-dependence representations have proven particularly useful in vulnerability discovery ( Khodayari and Pellegrino 2021 ) , as they can model a wide range of taint-style vulnerabilities, including command injections, file inclusion vulnerabilities, and cross-site scripting (XSS) vulnerabilities. These representations facilitate combining taint propagation information with syntactic and control-flow information to identify vulnerable code ( Yamaguchi et al. 2014 ) and enable automated processing using graph-based machine learning algorithms ( Chakraborty et al. 2021 ) . However, their accuracy hinges on knowing the taint propagation semantics of all methods. We present and implement a taint-tracking strategy based on a whole-program data-dependence representation that can be incrementally updated as knowledge about the semantics of external libraries becomes available, avoiding full recomputation when adding new annotations. We contribute our resulting work to an existing open-source code analysis platform, Joern ( Joern Community 2024 ) , and make it available to the research community. We evaluate the efficiency of our analysis on Java, Python, and JavaScript programs. 2. Background Consider a simple example of data flow that spans external calls to motivate our approach. Listing 1 defines two methods, foo and bar . The foo method obtains an object u from an external source ( Source.getValue ), creates a new object v , and calls u.transform(v) to produce result , which is then passed to bar(result, v) . The bar method calls an external method ( Sink.addValue ) on both its parameters. We want to know whether data from the source, i.e., the return of Source.getValue , can reach the first argument of Sink.addValue . This means checking if a call to Source.getValue defines a value w that is later used as w^{\prime} in a call to Sink.addValue( w^{\prime} ) . In other words, is w^{\prime} obtained through a series of transformations from w ? ⬇ public class Example { public static void foo () { Obj u = Source . getValue (); Obj v = new Obj (); if ( Config . isPrivileged ()) { Obj result = u . transform ( v ); bar ( result , v ); // internal } } static void bar ( Obj x , Obj y ) { Sink . addValue ( x ); // sink Sink . addValue ( y ); // sink } } Listing 1: Sample Java code with methods foo and bar that call external methods getValue , isPrivileged , addValue , and transform . This perspective on code as operations on variables for which arguments are used , defined , or used and defined within a method can be expressed via a data dependence graph . Originally developed for program slicing ( Ferrante et al. 1987 ) , this graph contains edges from nodes describing operations that define a variable to those that use it without prior redefinitions. When no information is available about external methods, an analyzer has two options: assume the calls have no effect or assume they taint everything. With the former approach, we obtain an under-approximated graph where no data dependencies are established between the external method calls. With the latter approach, we obtain an over-approximated graph with spurious data dependency paths that may not reflect actual taint propagation. Compared to the under-approximated graph, the over-approximated graph offers the advantage that 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 in the data dependence graph. Similarly, the potential re-definition of u or v introduced by the call to transform is visible due to the inability to traverse from the node of bar to that of Sink.addValue without passing through that of transform . This is an example of a transitive data dependency, where a dependency from one variable to another is due to a chain of intermediate steps or functions ( Horwitz et al. 1990 ) . To deal with these transitive dependencies, Horwitz et al. 1990 proposes an elegant extension of intraprocedural data dependence graphs, which they refer to as system dependence graphs . In the system dependence graph, separate nodes for input and output arguments are introduced, and transitive dependencies are encoded via direct edges from input to output nodes. This compresses transitive dependencies onto a representation that only perceives local (non-transitive) dependencies. Nonetheless, the idea of maintaining a representation of data dependencies that is independent of transitive data dependencies – and that therefore does not need to be recalculated as new information about external methods becomes available – forms the intellectual basis for our approach. This fits our scenario well, where the behavior of external methods may be characterized in greater detail by the user over time. 3. Design The Joern ( Joern Community 2024 ) code analysis platform is extended with a data-flow engine. Joern ’s language frontends and standard stages generate a unified abstract syntax tree (AST) , control flow graph (CFG) , and control dependence graph (CDG) , forming a near-complete code property graph (CPG) ( Yamaguchi et al. 2014 ) . The data-flow engine provides the necessary primitives to construct the intermediate data dependence graph (DDG) for a full CPG . It includes a querying engine to determine flows on the fly for specified sources and sinks. This scheme is a may analysis that identifies flows from sources to sinks, considering user-provided semantics of external methods. The following sections describe the design and implementation in greater detail. 3.1. Data-Dependence Representation The data-dependence representation is based

Read the complete text