Previous work has shown that one can often greatly speed up static analysis by computing data flows not for every edge in the program's control-flow graph but instead only along definition-use chains. This yields a so-called sparse static analysis. Recent work on SparseDroid has shown that specifically taint analysis can be "sparsified" with extraordinary effectiveness because the taint state of one variable does not depend on those of others. This allows one to soundly omit more flow-function computations than in the general case.

Abstract Since its inception two decades ago, Soot has become one of the most widely used open-source static analysis frameworks. Over time it has been extended with the contributions of countless researchers. Yet, at the same time, the requirements for Soot have changed over the years and become increasingly at odds with some of the major design decisions that underlie it. In this work, we thus present SootUp, a complete reimplementation of Soot that seeks to fulfill these requirements with a novel design, while at the same time keeping elements that Soot users have grown accustomed to.

To resolve aliasing, precise program analyses rely on pointer analyses. Demand-driven pointer analysis seeks to be efficient by computing information only for variables on which a demand is raised, through a points-to or alias query. Yet, research has shown that when applied to large-scale programs even demand-driven analyses can become expensive in terms of memory and runtime. This paper thus investigates to what extent demand-driven pointer analysis can be accelerated further if being executed over a sparse control-flow graph (CFG), specialized to those queries. We investigate two designs: First, typeaware sparsification, in which the resulting CFG only consists of statements containing variables that are type compatible with the query variable. Second, alias-aware sparsification, where the resulting CFG consists of the def-use chains of the query variable and all its intra-procedural aliases.We implement both designs in SparseBoomerang by extending Boomerang, a pointer analysis framework based on push-down systems. We evaluate SparseBoomerang by comparing it to Boomerang in terms of precision and performance. On the Pointerbench micro-benchmark suite for alias analysis, SparseBoomerang maintains the precision of Boomerang, in both designs. We evaluate the runtime and memory performance of SparseBoomerang by using Flowdroid as a taint analysis client on real-world apps. Compared to the baseline Boomerang, on average SparseBoomerang solves alias queries 2.4x faster when using the type-aware sparsification strategy, and 2.8x faster when using the alias-aware variant with negligible memory overhead.

Static code features are necessary components when using machine learning-based techniques to reason about a program of interest. To extract static code features, researchers develop their own feature extractors specific to their own studies. This causes two problems for the follow-up studies that build on the same set of features. First, the current feature extractors are intertwined with the rest of their codebases, and accessing them alone is time-consuming. Second, new kinds of features that are introduced in the follow-up studies are not incorporated back into the original feature extractors. Therefore, it is a tedious task for researchers to track all these individual feature extractors from different projects. In this work, we present SootFX, a generic stand-alone tool that enables the extraction of static code features from Java and Android programs. We explain its design, which makes it easily extensible for supporting new features and resource providers. We introduce its client APIs in Java as well as in Python, a popular programming language among machine learning practitioners. We illustrate a few of its possible use cases on a set of real-world Java libraries and Android applications.