SEAL: Integrating Program Analysis and Repository Mining

In a preparation step, we map information from the version control system into a representation on which we later conduct the program analysis. As program representation, we use the compiler’s intermediate representation (IR), which is a common abstraction used in modern compilers and static analysis tools. It is important to note that SEAL and the definitions in Section 2.2 are based on, but not restricted to, a given IR. A key mechanism of our approach is that, during the construction of the IR, we add information to the specific IR instructions that relate them to the commit that introduced the corresponding code. The compiler determines the last change for each source-code line by accessing repository meta-data (e.g., git-blame³) and then annotates the commit hash to the respective instruction. Each commit itself is a snapshot of the repository that represents the changes compared to the previous commit.

Figure 2(a) lists a C program that serves as our running example. The hash of the commit that introduced each source-code line is shown on the right ( \(\triangleright\) ). During compilation, SEAL adds this information to the IR, as shown in Figure 2(b). Each of the IR instructions is annotated by its corresponding commit hash (right side).

We devise a formal framework that serves as a basis for SEAL. In particular, the framework defines the abstract structure of commit interactions and commit-interaction paths, based on a given relationship between program elements, data flows, in our case.

A program \(\mathcal {P}\) is a composition of instructions \(i_{\mathrm{1}},\ \ldots ,\ i_{\mathrm{n}} \in \mathcal {P}\) stemming from a sequence of commits \(c_{\mathrm{1}},\ \ldots ,\ c_{\mathrm{m}} \in \mathcal {C}\) , where \(\mathcal {C}\) is the set of all commits from the repository.

The base commit represents the initial commit that introduced the source line in question to the code base, as illustrated on the right-hand side of Figure 2(b).

Applied to our example of Figure 2(b), instructions returns for commit \(\texttt {3e8882e}\) a set containing the two instructions alloca in Line 3 and store in Line 6.

Next, we define interactions between commits. We define the relation \(\rightsquigarrow\) (relates to) to represent data-flow interactions. In general, our framework abstracts from any concrete relationship and does not require specific properties of the relation \(\rightsquigarrow\) . However, in a concrete instantiation, certain properties can be defined by the user to express desired analysis semantics. In our case, we require \(\rightsquigarrow\) to be transitive and not symmetric, because the effects of data-flow interactions are directional, meaning, a write to a variable does only affect subsequent reads and not preceding ones.

Function interactions applied to \(\texttt {3e8882e}\) and \(\texttt {0872f49}\) , for our running example in Figure 2(b), would return an empty set, since there are no data flows between instructions added by \(\texttt {3e8882e}\) and instructions added by \(\texttt {0872f49}\) . Applied to \(\texttt {ea8426c}\) and \(\texttt {0872f49}\) , we obtain: \(\lbrace \:(\,\color{green}{\texttt{alloca}}\!:\!4, \color{green}{\texttt{load}}\!:\!9\,), (\,\color{green}{\texttt{store}}\!:\!7, \color{green}{\texttt{load}}\!:\!9\,),\:\dots \:\rbrace\) , where \(\color{green}{\texttt{inst}}\) \(\!:\!n\) denotes instruction inst at line number n from Figure 2(b).

Once we created a fixed mapping from commit information to IR and determined the interactions for our program, we can investigate interactions between commits derived from interactions between instructions.

Intuitively, two commits interact when code added by the first commit interacts with code from the second commit. In our example, we obtain the commit interaction \((\, \texttt {ea8426c}\,,\ \texttt {0872f49} \,)\) for the pair \((\, \color{green}{\texttt{alloca}}\!:\!4, \color{green}{\texttt{load}}\!:\!9 \,)\) of instructions. That is, code changes from \(\texttt {ea8426c}\) interact with changes introduced by \(\texttt {0872f49}\) .

To further aggregate information from commit interactions and add a context-specific meaning, we group commit interactions for every instruction into a commit-interaction path.

A commit-interaction path aggregates over multiple commit interactions based on a target instruction i. All commits, except the base commit of the target instruction i, belonging to the interaction set of i are merged into a single set. For the ret instruction in Line 12 from Figure 2(b), we obtain the corresponding \(\mathrm{CIP} (\color{green}{\texttt{ret}}:12) =\) \((\lbrace \, \texttt {c4d9b1a},\,\texttt {ea8426c} \,\rbrace \,,\ \texttt {0872f49})\) , which indicates that two other commits, c4d9b1a and ea8426c, interact with the base commit 0872f49 at instruction ret.

For computing commit interactions, we have implemented a flow- and fully context-sensitive, alias-aware, inter-procedural taint analysis based on Interprocedural Distributive Environments (IDE) [50].

IDE is an algorithmic framework to implement data-flow analysis. To check whether a property of interest holds at a certain point in a program, IDE constructs a so-called exploded super-graph (ESG). An ESG is constructed by replacing each node in the program’s inter-procedural control-flow graph with a bipartite graph representation of the corresponding flow function. Flow functions for identity (id), generating (gen), and removing (kill) data-flow facts are distributive and can be represented as bipartite graphs, as Figure 3 shows. Thus, all gen/kill-problems such as uninitialized variables, available expressions, reaching definitions, and taint analysis can be expressed in IDE. If a node \((i,d)\) in the ESG is reachable from a special tautological node \(\Lambda\) , then the data-flow fact d ( \(\in D\) , the data-flow fact domain) holds at instruction i ( \(\in I\) , the set of program instructions). In addition, ESG edges can be annotated with lambda functions to specify value computations that are solved over a separate value domain V. These so-called edge functions allow one to encode an additional value computation problem that is solved while performing a reachability check. The runtime of IDE is \(\mathcal {O}(|N| \cdot |D|^3)\) [50], where \(|N|\) is the number of nodes in the inter-procedural control-flow graph and \(|D|\) is the size of the data-flow domain D. Thus, the analysis efficiency highly depends on the size of the underlying data-flow domain. The value domain V can even be infinite and does not affect the algorithm’s complexity. Rather than encoding a linear-constant propagation using flow functions that operate on the data-flow fact domain \(D := \langle v, c \rangle\) , with \(v \in \mathcal {V}\) the set of program variables and \(c \in \mathbb {Z}\) that comprises tuples of program variables and their constant integer values, a linear-constant propagation can be instead encoded much more efficiently using \(D := \mathcal {V}\) and \(V := \mathbb {Z}\) . This enables the IDE framework to propagate only constant program variables as data-flow facts while computing their constant values on the separate edge function domain. The effect of a set of instructions can be summarized by composing flow (and edge) functions. The composition \(h = g \circ f\) of two flow functions f and g, called jump function, can be obtained by combining their bipartite graph representations. h can be produced by merging the nodes of g with the corresponding nodes of the domain of f. Once a summary for a complete procedure p has been constructed, it can be (re)applied in each subsequent context where the procedure p is called. Figure 4 shows an excerpt of a program and its respective ESG for the taint analysis that SEAL uses to compute commit interactions.

Taint analysis is a parameterizable analysis that tracks values that have been tainted by one or more sources through the program and that reports potential leaks if a tainted value reaches a sink. Sources and sinks may comprise functions and instructions. The taint analysis \(\mathcal {T}\) that we use in our experiments tracks data flows between the instructions of a given target program. It treats all variable declarations as sources and propagates these variables through the program. As we are interested in all instructions that interact with tainted variables, our set of sinks is empty. We then lift the data flows (i.e., the interactions of instructions with each other) to their respective commits, such that we can determine commit interactions (cf. Section 2.2).

We define the relevant intra-procedural (normal) flow and edge functions, which utilize our definitions from Section 2.2 to access commit information, formally in Figures 5 and 6. For the sake of brevity, we omit a formal description for inter-procedural (i.e., call, return, call-to-return) flow and edge functions and describe them only informally! The call and return flow functions map actual parameters onto the formal parameters at a call site, and vice versa at a callee’s exit instructions (return or throw instructions). The call-to-return flow function generates flow facts for calls to heap-allocating functions, such as, malloc() or operator new(), and propagates all data-flow facts alongside a call site that are not involved in the function call under analysis. The call and return edge function implementations are realized as identity, and the call-to-return edge function implementation forwards to the normal edge function implementation.

The analysis \(\mathcal {T}\) , starting at the program’s entry point main, taints the target program’s variables (e.g., alloca instructions, cf. Figure 2(b)) as they occur and propagates them as data-flow facts through the program. When analyzing libraries, the analysis treats every publicly accessible function as an entry point. Each tainted variable (i.e., data-flow fact) is associated with a set of commits that is encoded in lambda calculus using IDE’s edge functions. Initially, it contains only a data-flow fact’s base commit produced by \(base(i)\) . Whenever an instruction i interacts with one of the data-flow facts d, \({\mbox{base}}(i)\) is added to d’s associated set of commits. A set of commits of a data-flow fact d can be overwritten if it is used as a target of a store instruction. In this case, all elements of d are removed and the commit of the store instruction itself as well as all elements of the set whose associated data-flow fact is to be stored are added. An excerpt of the exploded super-graph for our taint analysis \(\mathcal {T}\) conducted on the program from Figure 2(b) is shown in Figure 4.

In the context of our general definitions from Section 2.2, \(\mathcal {T}\) computes the interactions (data flows) and constructs a \(\mathrm{CIP} _{i}\) for every instruction \(i \in \mathcal {P}\) as output.

The first step of our analysis pipeline (cf. Figure 7) is the lowering step from an abstract syntax tree (AST) to LLVM-IR, in which we enrich LLVM-IR with commit meta-data. During the compilation of a translation unit, Vlang computes for each AST node the last commit that modified the related code and adds it as meta-data to the corresponding generated IR instructions. When lowering an instruction, Vlang queries our framework for relevant commit information, providing a corresponding file, line number, and line offset from the AST node’s expansion location (i.e., the location in the file before macro expansion). The framework then computes the blame of the file using the library libgit2.⁵ It is important to note that the method for identifying last modifying commits can be configured by the user. In our study, we use git blame. Then, Vlang generates a commit meta-data object based on the line number’s commit hash and the commit meta-data returned back to Vlang and attaches it to the instruction.

For illustration, consider our example of Figure 2(a): On the right, we show commit hashes per code line. During compilation, Vlang creates an AST and lowers it to LLVM-IR. Figure 2(b) shows the LLVM-IR output after lowering. Let us start with the first statement in Line 3. During lowering, Vlang creates two instructions for this statement: one allocation for the stack variable (alloca in Line 4 of Figure 2(b)) and one to initialize it to 20 (store in Line 7). As one can see, Vlang added commit meta-data to both of these instructions referenced by the meta-data tag !Commit and an identifier ID. The ID !9 points to the meta-data section of the file containing the commit hash. For the sake of simplicity, we leave out the actual meta-data nodes and depict the hash on the right-hand side of Figure 2(b).

After Vlang has processed the input file, all generated LLVM-IR that are related to commits from the project’s Git repository are tagged with the corresponding commit meta-data. The enriched LLVM-IR serves as input to our data-flow analysis (cf. Section 3.3).

A precise commit-interaction analysis requires the data-flow analysis to be inter-procedural, i.e., whole program and context sensitive [53]. Analyzing every compilation unit in separate bitcode file leads to approximations whenever callees of a call site are defined in another translation unit. We thus implemented our analysis to be whole program. To create a whole-program bitcode file from the project’s source code, we inject our tool Vlang into the build process. This enables us to reuse the existing build scripts by using using Whole Program LLVM (WLLVM)⁶ as a compiler wrapper, which invokes Vlang and generates and links bitcode files.

We implement our taint analysis \(\mathcal {T}\) as an IDE [50] analysis in the PhASAR [51] framework. PhASAR has been built on top of LLVM and provides, among others, a generic IDE solver implementation and all required infrastructure (e.g., control-flow analysis) to solve concrete client data-flow analysis problems.

PhASAR’s generic IDE [50] solver operates on a problem interface type whose implementations correspond to concrete data-flow analysis problems. The interface mainly comprises flow and edge function factories that are queried by the data-flow solver to construct the exploded super-graph and solve the value computation problems that are specified along the edges. We implemented these flow and edge functions factories according to our descriptions in Section 2.3.

SEAL aims to be extendable, and the results shall be integratable into existing study setups and tool. For this purpose, SEAL has a four-layered design, where at each layer the relevant information can be extracted for use by external tools. In what follows, we give a short overview of the data that is produced by each layer and describe how other tools can access it.

AST-level commit information. . In the preparation step, before data-flow analysis, SEAL’s compiler extension Vlang makes commit information accessible through LLVM’s AST. The commit data is provided by a general abstraction in Vlang that offers an interface to map AST nodes to commit hashes. Through this interface, tools have an easy way to query commit information related to a particular AST node (e.g., to combine commit information with error messages).

LLVM-IR with commit information. . During LLVM-IR code generation, Vlang attaches commit information provided by the AST interface to the generated llvmir information in form of meta-data. This way, commit information is attached to LLVM’s internal representation and can be queried, like any other meta data, through the usual framework API (e.g., to attribute LLVM’s warnings about missed optimizations with author information).

Data-flow-based commit interactions. . After commit interactions have been computed, they can be accessed within LLVM’s analysis infrastructure, enabling other analyses to query this information. As described in Section 4.2, this enables other analyses to attach socio-technical information to their analysis results (e.g., an analysis that detected an SQL injection can automatically determine developers interacting with the vulnerable code and include them in the resolving process). In addition, these raw commit-interaction data can be exported into a yaml for further analysis.

Aggregated socio-technical information. . To ease the analysis of data-flow-based commit interactions, SEAL provides different graph aggregations of the raw commit interaction data, including: commit, author, and commit-author graphs, which we use in Section 4.1. With these graphs, existing approaches have a straightforward way to integrate the data-flow-based commit information.

First, we address three problems related to the field of repository mining and similar areas of research that are hard to approach using only high-level or low-level information, but become much more tangible when combining these two. For our evaluation, we aggregate commit interactions in a commit interaction graph. Not only does a graph representation come very naturally, because of the data-flow relation that is used to compute commit interactions, but it also allows us to use methods from graph theory to reason about commit interactions. We can also apply transformations to the graph to access different kinds of information, e.g., information about commit authors.

Central code . With commit interactions, we are able to quantify the impact of the changes made by a commit on the program’s data-flow dependency structure. This is related to the area of change impact analysis, where researchers have developed a multitude of techniques on how to estimate the impact of a change on a software project, using either high-level information or dependency information [36, 38]. While there are approaches that use both [15, 18, 20, 31], with SEAL, we can combine both kinds of information at the same time in a joint analysis.

Previously, Zimmermann and Nagappan [63] used dependency graphs to identify central program units in a software project and highlight their role as a proxy for defect-prone code. In a similar fashion, Ferreira et al. [14] investigated how interactions between functions in the presence of preprocessor directives relate to the occurrence of vulnerabilities. With commit interactions, we can identify code locations that are central in the dependency structure of the software system under analysis at a much finer granularity and, in addition, link them to commit meta-data (e.g., when or by whom the code was introduced). Changes to such central code are interesting, because their effect on the data that flows through the program is likely very high. For example, the function int align(int i) from the audio codec opus—one of the subject projects of our evaluation in Section 5—calculates how much memory an object of size i needs when it is stored with proper memory alignment (Figure 8). The function receives the size of the object via the parameter i. That parameter is then used to calculate the size with alignment, which is then returned from the function, meaning that there is a data flow from the parameter to the return value. As a consequence, there are also data flows between values passed to the function and usages of its return value. Also, the function is widely used throughout opus with 67 usages across 8 of 22 source files, which causes it to have many data flow connections to many different locations in the system. So, it is fair to say that this function is indeed central. To show how commit interactions can be used to identify such central code, we formulate the following problem:

P₁: Which fraction of commits affects central code?

It is important to reiterate at this point that this problem, while being interesting in itself, serves here as a showcase of demonstrating SEAL’s ability to address this and similar problems in practice and research in a more systematic and efficient way to what is possible so far. Before we measure the centrality of the code introduced by a commit, we first define how we represent commit interactions in a commit interaction graph.

In this definition, \(\mathcal {CI}\) refers to the set of all commit interactions of a program, and \(\mathcal {C^{\prime }} \subseteq \mathcal {C}\) is the set of commits that participates at least in one commit interaction, that is, \(\mathcal {C^{\prime }}=\,\lbrace \: c_{\mathrm{1}}, c_{\mathrm{2}}\ \,|\ \,(c_{\mathrm{1}}, c_{\mathrm{2}}) \in \mathcal {CI} \:\rbrace\) . Note that this graph may contain multi-edges, since there may be commit interactions that originate from different instructions but have the same base commits.

With commit interactions represented in a graph, we can now employ methods from graph theory to identify commits affecting central code. We identify such commits by identifying central nodes in the commit interaction graph using the node degrees of the commits. We use the node degree to measure centrality, since it relates to our definition of central code quite well; other centrality measures are possible as well. A high node degree means that a commit participates in interactions with many other commits, which is an indicator that the code introduced by that commit is central in the dependency structure of the software system under analysis. We are particularly interested in commits that introduce a relatively small change, since such commits are more easily overlooked than very large commits. This does not mean, however, that large commits cannot introduce central code. In fact, just because of their size, we expect large commits to be very likely to introduce, at least, some central code. For our example from opus, each usage of function align produces incoming interactions (size of the object) and outgoing interactions (size with alignment), and thus, commits associated with that function have a high node degree. Therefore, any—even small—change to align that affects its return value affects every location the function is used at. At the same time, the function itself and consequently any commit that touches only that function is only a few lines long. This scenario is illustrated in Figure 9(a), where a small change to central code introduces many outgoing interactions with other commits. In Figure 9(b), new code is introduced that is not central by itself, but merely interacts with central code. In this case, only a few interactions are attributed to the new commit. This scenario illustrates that commits touching central code can have a large effect on the rest of a software project and, if such commits can be detected, this information might guide testing and review efforts on these critical changes to the code base. SEAL helps to identify such cases.

Author interactions . Commits consist not only of code changes, but they also contain meta-data, such as when or by which author a commit was created. From these data, SEAL can extract information about socio-technical interactions in a software project. Socio-technical interactions are often analyzed using communication or collaboration relationships between developers at the file or function level and may also include dependencies between artifacts [17, 24, 25, 26, 42]. However, indirect dependencies are missed this way, which may still be relevant to properly characterize certain aspects of the socio-technical interactions in a project, e.g., classifying the roles of developers.

For example, consider the function ssh_handle_packets from libssh in Figure 10. In this function, a context object, which is returned by ssh_poll_get_ctx, is passed to ssh_poll_ctx_dopoll, creating an indirect dependency between the two functions. This indirect dependency is interesting, because information carried by the context object could be relevant for the computation in ssh_poll_ctx_dopoll. Thus, if a developer modifies the context object in ssh_poll_get_ctx, then he/she also indirectly influences the function ssh_poll_ctx_dopoll but might not be aware of that. With SEAL, we can incorporate such indirect dependencies in socio-technical analyses that can only be detected with a data-flow analysis and, thus, uncover hidden dependencies between developers. We formulate the following problem to demonstrate that SEAL’s information on commit interactions are useful for answering socio-technical questions about a software project:

P₂: Which authors interact via commit interactions and what are the characteristics of the arising socio-technical structure?

By lifting SEAL’s commit interaction graph to author information, we can easily identify which authors interact with each other indirectly via data flow. For this purpose, we project on the commit interaction graph such that the authors of the commits become nodes and interactions between authors become directed edges. This projection can be implemented with vertex identification, that is, all nodes whose commits have the same author are identified with each other. The remaining edges then represent interactions between authors at a data-flow level. With this information, we can not only see which authors interact with each other, but also which authors interact with especially many (or few) other authors, for example, to determine an author’s role in a software project [8, 25].

Commit–author interactions . A commit can interact with commits from one (Figure 11(a)) or multiple authors (Figure 11(b)). The fact that a high number of authors participate in interactions for a commit suggests that the author needs to be familiar with code from many different developers rather than with their own code or the code of only few developers. This again may have implications for the bug-proneness of the associated source code [23] and emerging coordination requirements between authors [22]. Another example where commit–author interaction data is useful is to select potential candidates for code review by determining which authors’ code is affected by the commit to be reviewed. To collect this information, we need both, commit interaction data (data flow) and commit meta-data (author names). We demonstrate that with SEAL, we indeed can combine these, addressing the following problem: P₃: How many authors interact via commit interactions?

To address this problem, we combine the commit and author interaction graphs. The resulting graph contains all commits and authors as nodes, and a directed edge from a commit \(c_{\mathrm{1}}\) to an author a if and only if there is an edge \((c_{\mathrm{1}}, c_{\mathrm{2}})\) in the program’s commit interaction graph and a is the author of commit \(c_{\mathrm{2}}\) . Note that this graph can also be constructed directly from information contained in the commit interaction graph. The outgoing node degree of commit nodes gives us the number of interacting authors showing whether a commit interacts with many or only a few authors.

Data-flow analysis is typically not concerned with commit or socio-technical information, but it can highly benefit from this additional information. First, computing commit interactions helps solve a multitude of additional data-flow problems with virtually no additional overhead compared to computing commit interactions only. Second, combining information on commit interactions computed by SEAL with information of a client data-flow analysis provides new insights that were previously locked away. As an example, taint analysis is frequently used to detect code injection vulnerabilities, such as SQL injections, but it can report only the detected potential security issues; it cannot attribute its findings to a specific project version, author(s), or development team.

As described in Section 2.3, our commit interaction analysis \(\mathcal {T}\) needs to exhaustively compute the precise, full exploded supergraph using IDE [50] to generate the commit data. It propagates all variables of a given target program and therefore computes all data flows for all program variables. Thus, \(\mathcal {T}\) also solves all data-flow problems that are concerned with data flows of program variables. All variations of taint analysis—for any given set of sources and sinks—can therefore be directly answered using the exploded supergraph that has already been constructed for \(\mathcal {T}\) . Reusing the parts of a previously computed exploded supergraph for a new analysis is beneficial, since IDE’s [50] runtime complexity is \(\mathcal {O}(|N|\cdot |D|^3)\) .

More importantly, a taint analysis that is set up to detect SQL injections, for example, cannot only be solved on \(\mathcal {T}\) ’s exploded supergraph, but, in contrast to a traditional data-flow analysis, also access commit information. SEAL allows one to compose different data-flow analyses with commit information and, for the first time, allows us to embed statements obtained by program analysis into the socio-technical context of a software project. To demonstrate that augmenting client data-flow analysis results with information on commit interactions indeed provides novel insights, we formulate the following problem:

P₄: Can commit information be utilized to gain additional insights from traditional data-flow analyses by making them change-aware?

To showcase how SEAL can be used to enrich existing data-flow analyses, we employ an existing taint analysis from PhASAR. We parameterize the taint analysis for detecting SQL injection vulnerabilities, and we enrich it with commit information. For an example, consider Figure 12, which depicts a program snippet that is vulnerable to SQL injection attacks. Any user input is considered as tainted and must be sanitized by a call to function sanitizeSQLString before it is sent to the SQL database server using the sink function executeQuery.

By allowing the taint analysis to exchange information with the commit analysis \(\mathcal {T}\) , SEAL can attribute the findings directly to the commits, authors, as well as development teams that are involved in the critical data flows (and potential security vulnerabilities) as reported by the taint analysis. This allows one to determine which commit introduced a potential vulnerability, which authors worked on the code that caused the data flows involved, and which developers should look into and the reported issue. A further illustration of how commit data can help to find code authors related to an SQL injection vulnerability is given in Section 7.2. In practice, static analysis—especially if conducted in a whole program manner—produces lots of potential findings, many of which may be false positives [2, 19], such that it has become a real challenge to prioritize and check them. It is important to note that SEAL cannot determine per se whether a finding is a true or false positive with respect to the original analysis’ semantics. But with socio-technical information, one can contextualize the results to asses their likelihood, and SEAL helps to prioritize and distribute them by providing socio-technical context information. For example, findings that concern multiple people are potentially more complex and could therefore be processed later, or findings could be filtered to involve developers only from a specific team, so people who potentially understand the issue better can look at it.

In the first part of our evaluation, we address the problems P₁–P₃ of Section 4: (1) quantitatively using our subject projects and (2) qualitatively highlighting interesting insights we obtained.

Central code. P₁ is concered with the fraction of commits that affects code that is central in the dependency structure of a program. Thereby, we are interested in commits that introduce a relatively small change (cf. Section 4).

As an example, Figure 13 depicts a scatterplot of the two relevant variables—commit size and node degree in the commit interaction graph—for opus and htop.⁷ The horizontal line denotes the 20-percentile and the vertical line the 80-percentile, respectively, putting small commits with a high node degree in the upper left quadrant. The marginal distributions show that most commits are relatively small and have a low node degree. While the distribution of the commit size has a similar shape for all of our subject projects, there are some differences when it comes to node degrees. For example, for opus, we have three clusters: The biggest cluster consists of commits with a low node degree (below 400), followed by a smaller cluster with medium-sized node degrees (400–800), and an even smaller one where the commits have very high node degrees (above 800). It is this latter cluster that is relevant to identify small commits with central code.

As an example for a change to central code, we qualitatively inspect commit \(\texttt {348e694}\) from opus (marked in Figure 13(a)). This commit has a very high node degree but touches only one line that belongs to the function int align(int i) (cf. Figure 14), which we already established to play a central role in the program’s data flow in Section 4. This demonstrates how even a small change can have a huge influence on the data that flows through a program, also showing that blame interactions carry different information than code churn.

A second example is commit \(\texttt {5e4b182}\) from htop. This commit refactors functions that are intended to replace C’s memory allocation functions and shows a very high node degree. These functions were initially introduced back in commit \(\texttt {a1f7f28}\) , and its successor commit \(\texttt {b54d2dd}\) replaced all occurrences of the original memory allocation functions in htop with the new substitutes contributing to their central role in the project. Commit \(\texttt {b54d2dd}\) also has a high node degree, but it is much larger and it touches 42 different files. This example matches the scenario described in Figure 9(a) that we used to motivate our notion of central code: Commit \(\texttt {5e4b182}\) modifies central code and, thus, affects many commit interactions despite being relatively small.

Investigating P₁ demonstrates that, with SEAL, one can gain deep insights into the structure of a software project by combining high-level repository information and low-level data-flow information into novel software metrics, e.g., estimating the importance of a change.

Author interactions. P₂ is concerned with the socio-technical structure of a software project demonstrating how meta-data associated with commits can be utilized with SEAL. In particular, we investigate how developers interact with each other at a data-flow level.

As an example, Figure 15 shows for each author of opus, libssh, and libtiff (blue dots) the number of surviving commits (commits that occur in the commit interaction graph) and the number of other authors his/her commits interact with at a data-flow level. It is immediately apparent that, in opus, there is one main developer who authored the vast majority of commits and hence, interacts with code from all other authors. All other authors submitted only comparatively few commits to the project. This pattern can be observed in many of our subject projects, especially the smaller ones. One notable exception to this pattern is libtiff (Figure 15(c)), which has more authors that contributed a larger number of commits. Interestingly, despite this inequality in the distribution of number of commits, the number of interacting authors is more evenly distributed. That is, there are authors who introduce interactions to code from many other authors with only a few commits, whereas the other authors’ code interacts with only very few other authors. Such information is useful to identify which authors contributed to central or only peripheral parts of a project [25], which is interesting, since changes to central code can have a bigger impact on the project.

SEAL is able to identify interactions between authors that cannot be detected by purely textual or syntactical approaches, which are commonly used when analyzing socio-technical aspects of software projects [17, 24, 25, 26]. Figure 16 shows the difference between author interactions computed by a file-based approach, where one considers two commits interacting if they edit the same file (co-edits), and \(\textrm {CI}\) -based author interactions as computed by SEAL. We notice that SEAL identifies less interactions as compared to the file-based approach, which is apparent in the negative range of the y-axis (orange). This result is in line with recent findings that a file-based approach reports many spurious links that using a more precise static analysis can avoid [18]. In addition to removing spurious interactions, for almost all of our subject projects, SEAL also finds unknown interactions between authors that the file-based approach could not detect, especially in larger projects. This includes interactions across files and among distant code fragments that are connected via data flow.

As an example, let us consider the author of commit \(\texttt {3659e8c}\) of libssh. This author contributed only one commit affecting source code to the project, which happens to implement asynchronous socket handling and, according to the commit message, “is intended as a ground work for making libssh asynchronous.” The implementation is mostly restricted to a single file, so approaches based on file- or function-level co-edits can only ever find author interactions within that file. However, since socket handling is a very integral part to libssh, this commit actually interacts with code from all over the code base written by many different authors (we consider this a central commit according to P₁). Some of the interactions even originate from indirect dependencies that can only be detected with a precise data-flow analysis. Indeed, the indirect dependency in the function ssh_handle_packets as described in Section 4 involves the commit in this example. With SEAL, we not only detect this case, indeed, we find 50 additional authors that interact with code from the author in question, indirectly, via data flow.

Another common approach for calculating interactions between authors relies on call relations between functions. Figure 16 and 17 compares SEAL to an analysis that extracts call-graph data directly from LLVM (i.e., that establishes a link between two authors if a function where one contributed code to calls another where the other author contributed code to). It is important to note that both the call-based approach and SEAL report less author interactions than the file-based approach. This is further evidence that the links inferred by the file-based approach are spurious. Furthermore, the \(\textrm {CI}\) -based approach finds considerably more links than the call-graph-based approach, especially for larger projects. This is because SEAL also considers indirect dependencies that can propagate across functions that are not connected via a call-relation. We refer the reader to Section 7.1 for a detailed example illustrating the role of indirect dependencies.

Commit–author interactions. P₃ is concerned with identifying which other authors’ code a commit affects via data flow. To address this problem, we need both commit interactions and author information. Figure 18 shows for each commit its number of interacting authors, normalized by the number of distinct authors per subject project that have at least one commit participating in a commit interaction. The violin plot visualizes the associated probability density. There are significant differences across projects. An extreme is xz: All surviving commits are from the same author and, hence, every commit interacts with commits from that one author. For other projects with few authors, such as gzip and lrzip, most commits interact only with code from few other authors. As projects grow and gain more contributors, most commits tend to interact with more authors (relative to the total number of authors of a project), as can be observed, for example, for bison and lz4. However, we do not only observe differences between projects of different size, but also between projects of similar size and a similar number of contributors. For example, while for opus most commits interact with about half of the authors, the results for libssh show two groups of commits—one where commits interact with comparatively few authors and one where commits interact with comparatively many authors. There could be various reasons for such differences, and they cannot all be explained by commit interactions alone. For example, the roles of the authors in a project can influence with which authors their commits interact [25], and the architecture of a project could also be of relevance. The crucial point is that, with SEAL, we are able to study these kinds of socio-technical problems in the first place.

To illustrate that making a data-flow analysis change-aware provides additional insights, let us apply SEAL’s augmented taint analysis (Section 4.2) on the program shown in Figure 12. The taint analysis will reveal an SQL injection vulnerability in Line 11. The analysis is able to detect the undesired data flow by checking the data-flow information for variable argv already computed by the commit analysis. The data-flow path that causes the potential SQL injection vulnerability comprises the following sequence of instructions: \(p = i_{\mathrm{9}} \rightarrow i_{\mathrm{10}}^{\mathrm{callsite}} \rightarrow i_{\mathrm{2}} \rightarrow i_{\mathrm{10}}^{\mathrm{retsite}} \rightarrow i_{\mathrm{11}}\) .

Besides being able to answer data-flow queries directly, the taint analysis is able to access any information on commit interactions at any point in the program. For example, the analysis can query the commit that generated an instruction with \({\mbox{base}}(i)\) . It can therefore determine that the commit \({\mbox{base}}(i_{\mathrm{3}})\) does—contrary to the intended semantics of sanitize—circumvent the sanitization of variable s. Or, using \(\mathrm{CIP} (i)\) , the analysis can determine all commits—and thus all authors—involved in the disallowed data-flow path. This is highly interesting in actual software development practice, since the findings of any data-flow analysis can now be associated with the commits and developers that have been involved in the code for which an issue has been found. Combining commit and data-flow information opens up a multitude of useful scenarios: The taint analysis, in our example, is able to compute \(\mathrm{CIP} (i_{\mathrm{13}})\) , and it can therefore report that the authors of the commits \(\texttt {3e8882e}\) and \(\texttt {ea8426c}\) have been working on the code between which the undesired data flow has been found. It can report the potential SQL injection directly to these authors. Since the commit information is data-flow sensitive, the taint analysis can relate commits and their corresponding authors to the SQL injection even when they did not touch the part of the code that executes the SQL statement directly. Furthermore, the analysis is able to issue that commit \(\texttt {ea8426c}\) and its respective author (knowingly or unknowingly) introduced the vulnerability by only sanitizing the input when the test switch is disabled. This ability has a huge potential for addressing a large number of interesting follow-up research questions.

Example . SEAL leverages a data-flow analysis to determine which commits interact, and by that, which code written by one developer influences the code of other developers. In Section 5.1, we demonstrated that SEAL can identify small but central changes to a code base by using information on data flow. We also showed that, by lifting SEAL’s commit interaction graph to author information, we can build an author-interaction graph that establishes interactions based on data-flow relationships between their code. Author interactions hint at coordination requirements between authors [4, 5, 34] in that when one author’s code consumes data produced by another author, the two should coordinate. Compared to existing approaches to compute coordination requirements, such as file-based [26] or call-graph-based approaches [41], considering data flow has two clear benefits: First, using data-flow information, spurious connections can be excluded (if there is no data flow between two code parts, they do not influence each other). Second, data flows, especially inter-procedural data flows, reveal dependencies between code that current approaches cannot find.

For illustration, let us highlight conceptual differences in the data produced by existing approaches and data-flow-based commit interactions on an exemplary study in which we want to determine coordination requirements between developers based on code dependencies. Consider the example code in Figure 19: A data processing service consisting of the service itself (Figure 19(a)), a user-data access layer (Figure 19(b)), and a computation worker (Figure 19(c)). Like in the real world, the different parts of the code base are implemented by different developers (names shown on the right).

To demonstrate key differences in the data produced, we compare the interactions computed by SEAL against the two commonly used approaches for computing artifact coupling, file-based and call-graph-based, which we did also use in our evaluation (Section 8). The coordination graphs computed by the different approaches are depicted in Figure 20. When comparing the file-based graph (Figure 20(a)) to the other two, we notice that link 1 between Eric and Ada is included only in the file-based graph. The point is that link 1 is actually spurious as, at the code level, there is no coordination requirement between the two functions in the file. The reason is that the file-based approach over-approximates by considering everything in a file as related without taking program semantics into account [18]. A programmer can easily see that these two functions are alternatives and, therefore, Eric and Ada can work independently. Furthermore, the file-based graph, compared to the other two graphs, does not contain the links, such as the one between Sven and Leonie and between Sven and Eric. This is due to the limitation of not considering dependencies across files.

When we compare the call-graph-based graph with SEAL, we notice that SEAL inverts the direction of link 2 and finds two additional links (3, 4). SEAL inverts the direction of link 2 because, from a data-flow perspective. Sven’s code consumes data produced only by Eric but does not supply input to Eric’s code.⁸ When we consider link 3, we see a bidirectional connection between Sven and Leonie, capturing the fact that data from Sven are used as an input to the code of Leonie and vice versa. SEAL differentiates between a function call with and without data. In contrast, when using a call-graph approach, we find only that there is a connection between Sven and Leonie and between Sven and Eric. With SEAL, however, we now know that Eric’s code does not depend on Sven’s code, since no input is passed to Eric’s implementation, but Leonie’s code does depend on Sven’s code, as her code works on input provided by Sven.

Many studies treat collaboration links between developers as undirected [41] or cannot infer a direction in links between artifacts, such as in co-changes retrieved from files that are commonly committed within one commit [33]. With SEAL, we obtain information about the direction that is based on the underlying data flows. This code-based directionality adds additional value, compared to temporal directionality [28], as it encodes who is using whose code. Parts of this information is also present in call graphs; we can infer only who is calling whose code but not, for instance, which data are passed to the function and how the returned data are used. Ignoring this information, we would not be able to notice indirect data dependencies, such as the one between Eric and Leonie that produces link 4. This link arises from the fact that Sven forwards data computed by Eric’s loading function to Leonie’s compute implementation. This information hints at an important coordination requirement that should not be missed, as when Eric adapts what user data are loaded, Leonie’s implementation needs to handle it. Hence, coordination between Eric and Leonie is important before Eric makes a change. This kind of coordination requirement is found only with SEAL and can be found only by utilizing a whole-program inter-procedural data-flow analysis.

Integration of SEAL into other research . A good example for illustrating SEAL’s merits arises from the work from Mauerer et al. [41]: In a large-scale empirical study, they explore the relationship between software quality metrics and socio-technical congruence by analyzing the alignment of social communication structures with technical dependencies. Important for our discussion is that they determine these dependencies by extracting them from the version control system: Two artifacts are related when they appear in the same commit, and two artifacts are dependent when they have static language-level dependencies, such as call-graph connections and type references. As explained in our example above, data flows carry additional information compared to file or call-graph-based approaches and thus enrich the artifact dependency networks of Mauerer et al. [41].

SEAL can not only help to determine artifact relationships, but with our author-interaction graph, approaches that analyze developer communities [28] or organizational structures [27] can profit from detailed data-flow-based interaction data, such as the work from Joblin et al. [28], who mine developer communities based on commit information and source-code structure. Specifically, they use a function-based and a committer-author-based approach to determine related authors. This way, they potentially miss important non-local links between developers, as conceptually shown in our example. With SEAL, they are able to extend their information on developers with data-flow-based author interactions and expand their author network as well as remove potential spurious links.

Another example in which SEAL’s commit interactions can be beneficial is in coordinating bug fixes or semantic code changes in large code bases or ecosystems. It has been reported that, for large industry code bases, even small code changes can cause severe bugs in other parts of the code [62] (e.g., a pointer can now be null, an integer variable can now have values larger than x, or a list that was previously sorted is now unsorted). As preventing changes is not an option (applying a bug fix that patches a vulnerability can not be delayed indefinitely), developers need to find ways to coordinate and let others know about the change. With commit-author interaction data produced by SEAL, we can easily figure out whose code could be affected by a change. Think about link 4 from Eric to Leonie that SEAL found because data produced by Eric are passed via Sven to Leonie’s code. With this information, Eric can proactively contact Leonie to look at his proposed change to determine that her code works well with it.

Example . Interpreting or acting on program analysis findings is a difficult task, especially in larger software projects [2]. One reason is that common program analysis tools focus on technical aspects, showing what is wrong in the code or highlighting conceptual problems [44, 45]. Typically, program analysis tools do not put their findings into a socio-technical context, ignoring the social structure around the code. Manually fitting this information post hoc onto the analysis results is cumbersome and difficult, because developers do not have this information in their heads and also because tools such as git blame provide only raw information that is not contextualized with regard to the analysis semantics. With SEAL, we build a bridge and automatically attach socio-technical information onto low-level analysis findings.

Consider the example in Figure 21 (cf. Section 4.2), where a program analysis tool, such as PhASAR, identified an SQL injection.

After the tool analyzed the code, it reports that there is a possible SQL injection vulnerability at Line 11, arising from a data flow from variable sani (Line 10), which contains unsanitized user input. Following this report, an engineer from the company’s security team can investigate the problem and finds that the recent change 5341f7b, depicted in Figure 22, introduced the offending variable in Line 10. Based on this information, Leonie can be contacted by the security engineer and asked to fix the SQL injection. However, this initial conclusion is wrong! Leonie’s code did not introduce the SQL injection, since the actual problem is in the implementation of sanitize, where unsanitized data are leaked when running in test mode. This is likely found out only later when she starts digging into her code and the implementation of sanitize and refers the problem back to the security engineer.

Misattributions like this arise due to missing information and cost valuable developer time. From the point of the security engineer, the tool report was plausible, and Leonie’s change seemed related, so the ticket was forwarded to her. With SEAL, this scenario could have worked out differently if the tool’s initial report would be combined with socio-technical information, obtained by SEAL’s data-flow analysis. By attaching the commit-interaction path of the offending call instruction for executeQuery, which contains all commits that had influence on the data flowing into the call, we can determine all authors that are involved. Figure 23 depicts an exemplary error message, where the SQL injection tool’s finding is contextualized with socio-technical information. So, in our example, the security engineer would see the report about the SQL injection, together with the information that the two developers Leonie and Eric are involved. The security engineer would then assign both the ticket and involve Eric from the beginning.

Integration of SEAL to other research . Inspired by our example, a number of existing program analysis tools qualify to be extended with additional socio-technical information. For example, Bessey et al. present an extensive experience report [2] that details on how industrial-grade static analyzers are used to find bugs in the real world and how these tools are perceived by companies and software developers: When confronted with analysis findings, developers tend to get emotional; at the end, it is their code that is supposedly flawed. Experience shows that the more peers are involved in discussing and dealing with analysis findings, the more likely it is that someone can diagnose an error (or identify a reported error as a false positive), report on experiences of similar errors, and eventually fix it [2]. SEAL provides this additional socio-technical information. For instance, it reports the set of authors involved in a given analysis finding, which makes it easier to assign errors to the relevant developers.

Furthermore, the information produced by program analysis tools can be filtered according to the attached socio-technical information (e.g., an analysis tool used within an integrated development environment could show only the findings that actually have a socio-technical connection to the developer using it). In this vein, Harman and O’Hearn report on the difficulty of making bug reports more actionable [19]. In particular, they debunk the implicit assumption that analysis and testing technology that follow the “ROFL” (Report Only Failure List) strategy is enough to get engineers to fix reported bugs. Software developers, however, are never short on lists of fail and failure reports that need to be taken care of. Any additional piece of information that helps developers prioritize these todos are helpful. The report of Harman and O’Hearn underlines the importance of the following information to find and prioritize bugs: (i) relevance, the developer to whom the bug report is sent is one of the set of suitable people to fix the bug; (ii) context, the bug can be understood effectively; (iii) timeliness, the information arrives in time to allow an effective bug fix; and (iv) debug payload, the information provided by the tool makes the fix process efficient (reproduced from Reference [19]). SEAL helps to deliver such information.

The socio-technical interaction provided by SEAL may benefit scheduling code reviews, e.g., developers with a lot of data dependencies to the changed code can be suggested as reviewers, as the changes could potentially interact with their code and introduce bugs. In 2008, a Debian developer accidentally broke a random number generator in a particular version of OpenSSL with what was thought to be a fix [49]. This shows that—in practice—it can be quite difficult to assign suitable reviewers for a given pull-request. With help of information as computed by SEAL, this could possibly have been avoided by allowing peers that are familiar with this complex part of OpenSSL’s code base to intervene.

A bottleneck of using SEAL is clearly the computational cost of the underlying data-flow analysis. Table 2 depicts the overhead generated by SEAL for the projects of our study (cf. Section 5.1). We see that, for the average project, computing the blame data adds roughly two minutes. Interesting to note, computing blame information correlates with the history length of a project ( \(\rho _{\text{pearson}} = 0.75\) and \(\rho _{\text{spearman}} = 0.90\) ), so projects with longer histories should expect a bit more overhead.⁹ Overall, we can see that for nearly all projects the analysis time dominates the overhead. As described in Section 2.3, we tuned SEAL’s analysis to be as precise as practically feasible. Specifically, we made our analysis context-sensitive, alias-aware, and inter-procedural. From our point of view, this is not too problematic, since SEAL is designed to run once to capture a full and precise picture of a given software project. Nevertheless, the underlying data-flow analysis is highly configurable in the sense that PhASAR allows one to select different helper analyses and to change each analysis’ parameters to trade off precision and performance. For instance, PhASAR allows its users to choose a less precise but faster points-to analysis. Similarly, one can choose a call-graph algorithm that underapproximates information and does not resolve indirect function calls instead of the one we chose. SEAL’s call-graph algorithm more expensively tries to identify potential call targets at indirect function calls to improve analysis precision, using points-to information and type hierarchies. Especially C++ developers seem to minimize the amount of indirect jumps [52] such that underapproximating call-graph algorithms may still provide enough precision for a user’s needs. Through these tuning knobs, users can reduce the analysis time if (slightly) less precise results are acceptable for their setting.

Another limitation of SEAL is that the granularity of commit data are currently line-based, which is the common granularity used by git and other tools that work on git data. Previous work already demonstrated for different use cases [16, 37] that a syntax-based approach could, with a additional cost, improve the precision. With token-based blame information, as proposed by Germán et al. [16], SEAL could be even more precise.

Commit interactions based on data-flow dependencies provide a new way to infer dependencies between developers that is based on how their code interacts. However, there might be other kinds of dependencies that give rise to coordination requirements or are otherwise of interest. For example, external communication via file system or network, interactions through non-functional properties, side channels, and operating-system-level functionality could also require coordination between developers. Therefore, even if we can include data-flow dependencies with SEAL, we should still keep broadening the scope and exploring new kinds of information that is currently not available to determine developer interactions.