Oliver Gerstl

Context

R is a programming language that is used in research for statistical computing and mostly by people without a background in computer science. Almost every value in the R programming language can carry attributes (metadata) like names, dim, or class that are silently attached to values and fundamentally changes how they behave (see the chapter on vectors and attributes in Advanced R [2]). A plain numeric vector becomes a matrix just by setting its dim attribute, a class attribute decides which function is actually called when using S3 dispatch (e.g., whether print(x) produces a table or a summary), and a factor is "just" an integer vector with levels. Yet, these attributes are assigned dynamically (e.g., with attr(x, "dim") <- c(2, 3), structure(...), or class(x) <- "my-class"), can be dropped unexpectedly by many operations, and are invisible when just reading the code. For a static analysis this is a problem, as without knowing the class of a value we do not know which method a call dispatches to, and without knowing dim or names we cannot judge whether an access like x[, "score"] is even valid.

Within this work we want to statically infer the attributes of R values, making this hidden metadata explicit and available to further analyses!

Problem

You have an R script together with the statically inferred data and control flow graph, and a general abstract interpretation framework that performs fixpoint iteration to infer code constraints.

The challenges are to

• design abstract domains [1] that represent the attributes a value may carry at a given program point (e.g., its potential classes, its dimension, or the names of its elements),
• track how attributes are created, propagated, modified, and dropped across assignments, function calls, and vector operations (respecting R's attribute-dropping semantics), and
• use the inferred attributes to improve downstream analyses (e.g., resolving S3 method dispatch, detecting invalid accesses, or flagging unintentionally lost attributes).

Of course, the specific scope of these challenges as well as the focus depends on whether you want to do this as a bachelor's or master's thesis as well as your personal preference.

Tasks

• Enrich flowR [3], a static analyzer for the R programming language, to infer attributes for values in R using the existing abstract interpretation framework [4]
• Start with a sensible subset of attributes (e.g., class, dim, and names) and model how common functions (attr<-, structure, class<-, dim<-, arithmetic operators, subsetting, ...) affect them
• Use the inference to answer concrete questions, such as which S3 method a call dispatches to [5], and evaluate the precision and performance of your analysis on real-world R scripts

Related Work and Further Reading

1. P. Cousot. Principles of Abstract Interpretation.
2. H. Wickham. Advanced R (2nd edition), Chapter 3: Vectors (Attributes) and Chapter 13: S3.
3. F. Sihler and M. Tichy. Statically Analyzing the Dataflow of R Programs.
4. O. Gerstl, F. Sihler, and M. Tichy. Inferring the Shape of Data Frames in R Programs using Abstract Interpretation. (original thesis)
5. F. Morandat, B. Hill, L. Osvald, and J. Vitek. Evaluating the Design of the R Language.

If you want to, you can have a first look at flowR for yourself: https://github.com/flowr-analysis/flowr

Contact and More

If you are interested and/or have any questions, feel free to contact me any time. We can discuss the topic further and try to adapt it to your personal preferences.

Oliver Gerstl

This thesis presents a theoretical concept and a proof-of-concept implementation for inferring numerical constraints to detect dead code on the statement level in R using abstract interpretation with two numerical domains.

The R programming language is mostly used by domain experts with limited programming experience. Recent studies show, that scientific code tends to suffer from bad code quality like, for example, dead code. However, current static code analysis tools for R have only limited support for detecting dead code.

To address this issue, we present a theoretical concept and proof-of-concept implementation using abstract interpretation, to infer numerical constraints for dead code detection. Therefore, we collect numerical operators and functions that are relevant for detecting dead code. We define and implement their abstract semantics using two different abstract domains, the interval and the closed pentagon abstract domain, and compare both approaches to determine which domain is better for dead code detection in R.

To identify relevant numerical operators and functions, we use flowR, a static code analysis tool for R, to extract the most frequent numerical operators and functions in conditions of if, while, and stopifnot statements in a collection of real-world R scripts. We combine the gathered information with function type signature information to identify functions that produce or consume numeric scalar values. Then, we define the abstract domains and abstract semantics of the identified concrete operators and functions for both domains. We implement and integrate the theoretical concept as a proof-of-concept implementation into the existing abstract interpretation framework of flowR. Finally, we evaluate our implementation using a selection of 90 executable and deterministic R scripts that we instrument to obtain a ground truth for evaluating the correctness and accuracy of our implementation. Additionally, we perform a large-scale evaluation on 10,000 scripts from GitHub to compare both domains regarding their ability to detect dead code and measure the runtime performance of the implementation.

There are several limitations to our concept and implementation. R is a highly dynamic language providing the user various abilities to manipulate the semantics of the language, for example, using the S3 and S4 object systems, which are only partially supported by flowR. Therefore, we rely on a set of soundiness assumptions regarding the use of these language features, which may not hold for all R scripts. As the scope of this thesis is limited, we further focus on a subset of numerical operators and functions, and refer to coarse-grained abstract semantics to support a wider range of operators and functions, instead of defining precise semantics for each operator and function.

We find that while our implementation is correct for all points of interest in the ground truth evaluation, the large-scale evaluation reveals correctness issues for both domains due to bugs in the implementation and the soundiness assumptions. In the 84 analyzed scripts, we correctly identify 31.69 % of the numeric scalar points of interest as numeric scalar, whereof we infer the exact values in 55.09 % of the cases, overapproximating the remaining cases to intervals with at least one infinite bound. Thereby, the interval and pentagon domain infer the same intervals. While the large-scale evaluation reveals that the pentagon domain infers additional non-trivial upper bounds in 1.86 % of the inferred values, the additional information does not aid in detecting more dead code.

Both domains infer the same number of dead branches. Out of the 9,962 analyzed scripts, we infer 0.68 % to contain dead code. We manually checked 37 scripts where we reported 81 dead branches and find that 44 % where actually dead, with the remaining branches being false positives.

We find that except for a few outliers, where the pentagon domain is substantially slower, our implementation of the pentagon domain is slightly faster than the implementation of the interval domain. However, we cannot conclude that the pentagon domain is generally faster than the interval domain, as we assume this to be caused by an optimization that was only applied to the implementation of the pentagon domain. The interval analysis required on average 53.91 ms with a median of 21.65 ms, while the pentagon analysis required on average 67.27 ms with a median of 17.26 ms to analyze a script. The combined 95th percentile runtime of all analyzing steps requires 743.88 ms, which we consider to be fast enough for most use cases.

For our proof-of-concept implementation, we therefore conclude, that the pentagon domain does not provide an advantage over the interval domain in terms of identifying dead branches in real-world R scripts, but rather introduces additional complexity while producing the same results as the interval domain.