# Detecting Semantic Conflicts using Static Analysis

Galileu Santos de Jesus<EMAIL_ADDRESS>0000-0001-8749-0302 Centro de
Informática, Universidade Federal de PernambucoAv. Jorn. Aníbal
FernandesRecifePernambucoBrazil50740-560 ,  Paulo Borba<EMAIL_ADDRESS>0000-0002-0381-2843 Centro de Informática, Universidade Federal de
PernambucoAv. Jorn. Aníbal FernandesRecifePernambucoBrazil50740-560 ,  Rodrigo
Bonifácio<EMAIL_ADDRESS>0000-0002-2380-2829 Universidade de
BrasíliaCampus Universitário Darcy RibeiroBrasiliaFederal
DistrictBrazil70910-900 and  Matheus Barbosa de Oliveira<EMAIL_ADDRESS>0000-0001-8758-2389 Centro de Informática, Universidade Federal de
PernambucoAv. Jorn. Aníbal FernandesRecifePernambucoBrazil50740-560

(2024)

###### Abstract.

Version control system tools empower developers to independently work on their
development tasks. These tools also facilitate the integration of changes
through merging operations, and report textual conflicts. However, when
developers integrate their changes, they might encounter other types of
conflicts that are not detected by current merge tools. In this paper, we
focus on dynamic semantic conflicts, which occur when merging reports no
textual conflicts but results in undesired interference— causing unexpected
program behavior at runtime. To address this issue, we propose a technique
that explores the use of static analysis to detect interference when merging
contributions from two developers. We evaluate our technique using a dataset
of 99 experimental units extracted from merge scenarios. The results provide
evidence that our technique presents significant interference detection
capability. It outperforms, in terms of F1 score and recall, previous methods
that rely on dynamic analysis for detecting semantic conflicts, but these show
better precision. Our technique precision is comparable to the ones observed
in other studies that also leverage static analysis or use theorem proving
techniques to detect semantic conflicts, albeit with significantly improved
overall performance.

Merge conflicts; Configuration management; Software evolution; Static
analysis.

††copyright: acmcopyright††journalyear: 2024††doi: ENDERECO††conference: 46th
International Conference on Software Engineering; April 2024; Lisbon,
Portugal††price: 15.00††isbn: 978-1-4503-XXXX-X/18/06

##  1\. Introduction

Textual (line-based) merge tools report conflicts when merging two code
versions that apply changes to the same or consecutive lines. Although common
and widely studied, such _textual conflicts_ aren’t the only problem that can
occur when integrating code from two developers.

As textual merge tools focus simply on combining lines, they aren’t able to
detect incompatible changes that occur in areas of the code separated by at
least a single line. So, for instance, if one developer changes a method’s
signature and another developer adds, lines apart, a call to the method with
the original signature, textual merge tools will integrate the code with no
conflicts or warnings. The merged code, however, won’t compile, characterizing
a _static semantic conflict_ (Sarma et al., 2011; Brun et al., 2013; Towqir et
al., 2022; Silva, 2022; Zhang et al., 2022; Sung et al., 2020).

Even worse, textual merge tools also can’t detect _dynamic semantic conflict_
(Horwitz et al., 1989; Yang et al., 1992; Shao et al., 2009; Brun et al.,
2013; Pastore et al., 2017; Barros Filho, 2017; Sousa et al., 2018; Da Silva
et al., 2020; Zhang et al., 2022), like when the changes made by one developer
affect a state element that is accessed by code changed by another developer,
who assumed a state invariant that no longer holds after merging. In such
cases, textual integration is automatically performed generating a merged
program, a build is created with success for this program, but its execution
reveals unexpected behavior.111We use a conflict terminology based on the
language aspect that causes a conflict another common terminology is based on
the process phase in which a conflict is detected. In this one, _merge_
conflict corresponds to textual conflict. _Build_ conflict corresponds to
syntactic and static semantic conflicts. _Test_ and _production_ conflicts
(and undetected ones) corresponds to dynamic semantic conflicts. Following
Horwitz et al. (Horwitz et al., 1989), we put this more formally by
considering dynamic semantic conflicts to be _undesired interference_ , where
interference is defined as follows: separate changes $L$ and $R$ to a base
program $B$ interfere when the integrated changes does not preserve the
changed behavior of $L$ or $R$, or the unchanged behavior of $B$.

As dynamic semantic conflicts, hereafter simply semantic conflicts, can
negatively impact development productivity and the quality of software
products, researchers (Horwitz et al., 1989; Sousa et al., 2018; Da Silva et
al., 2020) have proposed techniques to detect them. In fact, as developer’s
desire (specification) is hard to capture and is often not available for
automated tools, these techniques simply try to detect interference. The
techniques based on theorem proving (Sousa et al., 2018) and static analysis
with system dependence graphs (SDGs) (Binkley et al., 1995; Barros Filho,
2017) are computationally expensive. Although an existing technique based on
dynamic analysis (Da Silva et al., 2020) has been proven less expensive, it
suffers from low recall.

This motivates us to explore a new alternative technique for approximating
interference when merging changes made by two developers: we propose the use
of lightweight static analysis on the merged version of the code, which we
annotate with metadata indicating instructions modified or added by each
developer. Two of the analyses we implement (Interprocedural Data Flow and
Program Dependence Graph) try to find data and control flows between
instructions changed by one developer to instructions changed by the other.
When they do find, they report interference. The other two analysis
(Interprocedural Confluence and Interprocedural Override Assignment), as
explained latter, try to capture other aspects that are also suggestive of
interference.

To evaluate our technique, with the aim of understanding whether it could be
useful as the basis of semantic conflict detection, we conduct an experiment
to understand how _accurate_ and _computationally efficient_ our analyses are
for detecting interference. We run our analyses on a dataset of 99
experimental units extracted from merge scenarios (quadruples formed by a
merge commit, its two parents, and a base commit) mostly reused from three
previous work (Barros Filho, 2017; Sousa et al., 2018; Da Silva et al., 2020)
on semantic conflicts.

Our experiment results show that our analyses have significant interference
detection capability, but with potentially significant costs for handling
false positives (analysis incorrectly reports interference). We compare that
with the accuracy results from previous work, running experiments with
subsamples of scenarios common to our work and previous work that contains an
evaluation. Our technique shows much better F1 score and recall than the
dynamic analysis technique, but with much worse precision. Our precision is
comparable to the ones presented by the SDG and theorem proving techniques;
due to the experimental design of these other studies, we can’t compare recall
measures. We also manually analyze and classify our analyses’ false positives
and negatives, and discuss how they could be mitigated. The performance
results show that our analyses should have much better performance than
previous techniques.

##  2\. Motivating Example

To illustrate the concept of semantic conflict and how our static analysis
technique is capable of detecting them, consider the Merge commit code in
Figure 1. It integrates changes made by two developers, say Left and Right, to
a Base commit. In Line 6, highlighted in yellow, we see Left’s change. In Line
8, highlighted in green, we see Right’s change. The rest of the code
originates from the Base commit, which is the most recent common ancestor of
the two integrated versions. As the changes made by Left and Right were not in
the same or consecutive lines, the textual merge was successful, resulting in
the illustrated code with no merge conflict or warning.

Figure 1. Semantic conflict example. We highlight one developer’s change in
yellow and the other’s in green.

⬇

1class Text {

2 String text;

3 int words, spaces, comments, fixes;

4

5 public void cleanText() {

6 if (text != null && hasWeaselWords()){

7 removeWeaselWords();

8 removeDuplicateWords();

9 }

10 }

11 ...

The resulting code declares the Text class, which has a field named text,
representing the string associated with objects of this class. It also has the
cleanText method, which was originally responsible for removing weasel words
(like _may_ , _possibly_ , etc.) from text, provided it was not null. To
improve text cleaning, Right added a call to the removeDuplicateWords method,
which removes duplicate consecutive words from text. Unaware of Right’s
change, Left independently changed the if condition; it now checks for the
presence of weasel words before trying to remove them.

Although these changes don’t result in textual conflicts, we have a problem:
Right won’t be happy with the resulting method behavior. Contrary to Right’s
intent, duplicated words will only be removed when the text contains weasel
words. For instance, running the Base version of the method with the text
‘‘the␣the␣dog’’ results in the same string, but running Right’s version with
the same text results in ‘‘the␣dog’’, reflecting Right’s intent. However,
running the merged method in the figure results in ‘‘the␣the␣dog’’, as the
input string has no weasel words. Following the interference definition we
give in the introduction, this shows that Right’s behavior change is not fully
preserved by the merge process, and is evidence that Left’s change undesirably
interferes with Right’s change, causing what we call a semantic conflict.

Both developers effectively carried out their tasks in an independent way.
Each version, Left and Right, individually fulfills the requirements or
specifications they were supposed to satisfy. However, due to unintended
interference, the merged code does not satisfy the specification Right
correctly implemented. That’s why semantic conflicts of this nature are often
complex and costly to identify and resolve (Da Silva et al., 2020; Towqir et
al., 2022; Silva, 2022). This directly affects the quality and outcome of the
products, as the final result is not as expected.

Resolving these conflicts may require careful manual investigation, which can
impact productivity. If not detected immediately after integration, addressing
these conflicts can become even more challenging as it involves reconciling
semantic and behavioral incompatibilities. In our example, it would be
necessary to investigate whether the issue lies within the individual
implementations of Left and Right or in interference between them. This would
require a thorough investigation that goes beyond the abstraction boundaries
established by the methods that cleanText calls.

##  3\. Detecting Interference using Static Analysis

To detect interference and help mitigate the negative consequences of semantic
conflicts, we propose a technique that runs static analyses on the merged
version of the code, which we annotate with metadata indicating instructions
modified or added by each developer. In particular, by running a static
_control dependence analysis_ (Ferrante et al., 1987; Horwitz et al., 1989) on
the example illustrated in the previous section, a tool could report that a
method invoke instruction added by Right is control dependent on a conditional
instruction modified by Left, warning about the existing interference.

We implement and rely on four analyses we describe in the following:
Interprocedural Data Flow, Interprocedural Confluence, Interprocedural
Override Assignment, and Program Dependence Graph, which includes the control
dependency that detects the interference illustrated in the previous section.
They all try to explore likely interference situations by keeping track of the
changes developers make and how they affect state elements such as global
variables, object fields, system files, variables that hold method return
values or raised exceptions, etc. We consider field accesses like o.a and o.b
to refer to different state elements, even if o holds the same reference; the
variable o also corresponds to a different state element.

###  3.1. Static Analysis Algorithms

For each of the four analyses we propose here, we implemented the algorithms
targeting the Java programming language and took advantage of the Soot
framework (Vallée-Rai et al., 2010) as the underlining infrastructure for Java
program analyses. In this section, we present the algorithms and how we use
them to detect interference.

####  3.1.1. Interprocedural Data Flow

Consider the example in Figure 2, showing the implementation of the cleanText1
method of the Text class (Figure 1). This method is responsible for removing
extra spaces, comments, and duplicate words from the string in the text field.
Line 12 is a change made by one developer (Left), while Line 14 is a change
from another developer (Right). In Line 12, the call to the method
normalizeWhiteSpace might lead to a _definition_ of the text field, as it is
changed during method execution when it contains consecutive duplicate
whitespace. On the other hand, in Line 14, the call to the method
removeDuplicateWords executes an instruction that _uses_ the text field, as it
has to be checked for duplicate words. These two changes lead to a _def-use_
data flow relationship when there are no comments in text; in this case they
will involve both the definition and the use of the same state element (text).

Figure 2. Data Flow (DF) example based on (Da Silva et al., 2020).

⬇

11void cleanText1(){

12 normalizeWhiteSpace();

13 removeComments();

14 removeDuplicateWords();

15}

Here we characterize these _def-use_ relationships involving Left and Right
contributions as _Data Flow_ (DF). They are important for interference
detection because definitions changed or inserted by one developer might
affect the behavior of uses changed or inserted by the other developer. For
example, consider the execution of the base version of cleanText1 with text
set to ‘‘the␣the␣␣dog’’, with two spaces between the and dog. It results in
the same string. Contrasting, running Left’s version results in
‘‘the␣the␣dog’’, as the extra space is removed. However, running the merged
version results in ‘‘the␣␣dog’’, given that the removeDuplicateWords method
careless removes the second the in the input string, leaving the original
space between the two duplicates, breaking Left’s intention of producing a
string without duplicate whitespace. We say then that Right’s change
interferes wih Left’s.

To implement DF interference detection, we integrate a Sparse Value Flow
Analysis (SVFA) implementation that borrows from (Sui and Xue, 2016) the rules
for creating a sparse graph that allows us to find interprocedural paths from
_defs_ to _uses_ involving a given state element. SVFA is often used in the
context of taint analysis (Sui et al., 2014; Shi et al., 2018) to identify
source-sink paths (Arzt et al., 2014; Grech and Smaragdakis, 2017). So we run
it twice: the first execution considers Left and Right contributions as source
and sink statements, respectively; the second execution is the inverse. This
way we cover data flows from Left to Right contributions and vice versa. In
the first execution, we mark “definitions” in the Left contributions as
_source_ vertices and “uses” from the Right contributions as _sink_ vertices
in the graph. In the most basic case, we can define a data flow edge in the
SVFA graph as one that connects a vertex where a variable is defined to
another vertex where the same variable is used. More complex cases deal with
the flow of data when binding actual and formal arguments in method calls,
return statements, and field stores and field loads. We report interference
when there is a path in the graph that starts with a source vertice and ends
with a sink vertice.

####  3.1.2. Interprocedural Confluence

Interference can also occur when there is no data flow between the integrated
changes, but there are data flows from the integrated changes to a common
statement; this statement behavior might be affected by both changes,
characterizing interference. The Text method in Figure 3 illustrates that. The
countFixes method returns the sum of the number of needed changes stored in
the spaces and words fields (see Figure 1). Left inserted Line 17, and Right
inserted Line 19. These inserted method calls simply modify different state
elements (spaces and words), so there is no data DF between them. However
their state changes flow to the return statement on Line 20. In this case, the
result of a call to the method countFixes will be different when considering
the Left version, the Right version, and the Merge version, characterizing
interference.

Figure 3. Confluence Flow (CF) example.

⬇

16int countFixes(){

17 countDupWhiteSpace();

18 countComments();

19 countDupWords();

20 returnspaces + words;

21}

To detect _Confluence_ (CF), we execute our interprocedural data flow analysis
algorithm (SVFA) twice, once marking Left statements as _source_ and base
statements as _sink_ , and once marking Right statements as _source_ and the
base statements as _sink_. The goal is to determine if there are _definitions_
from Left and Right that assign expressions to state elements flowing to Base
statements that _use_ these state elements.

####  3.1.3. Interprocedural Override Assignment

Differently from the previous two analyses, which focus on detecting data
flows between the integrated changes or from them to a common statement, here
we capture situations where state updates from one developer are overridden by
the other. Interference occurs in such cases because the behavior of the
changes from one developer is not preserved in the merge version. Figure 4
illustrates that. Left inserted the call to the countDupWhitespaces method,
while Right inserted the call to countDupWords. Both methods simply set the
instance field fixes with the number of needed fixes they counted, whereas
removeComments sets another field. Because of Right’s change, the count of the
number of duplicate whitespace is then lost in the merge revision,
characterizing the interference.

To implement _Override Assignment_ (OA), we use an interprocedural algorithm
that records definitions in two sets: $S_{l}$ contains the definitions coming
from the analysis of code annotated as Left, whereas $S_{r}$ contains the
definitions coming from the Right. As soon as we analyze Base code that
defines a state element in one of the sets, we remove this element from the
set. We report interference when we try to record in one of the sets a
definition of a state element that is already in the other set, or when there
is a containment relationship between the elements: o is in one of the sets
and we try to record o.a, or vice-versa.

Figure 4. Override Assignment (OA) example.

⬇

22void generateReport() {

23 countDupWhitespaces();

24 countComments();

25 countDupWords();

26}

27}//end of the Text class

####  3.1.4. Program Dependence Graph

The last analysis we discuss is illustrated in our motivating example (see
Sections 2). There, however, we mention only the _control dependency_ aspect.
But our implementation builds a Program Dependence Graph (PDG) (Ferrante et
al., 1987; Horwitz et al., 1989); the program instructions are vertices, while
the edges represent either control or data dependencies. Due to the control
dependencies, we detect interference in the motivating example. We build our
graph using similar rules to Ferrante et al. (Ferrante et al., 1987). We
generate a PDG for each method under analysis, and report interference when
there is a path (having control or data dependencies) from a Left instruction
to a Right instruction, or vice-versa. The existence of a path indicates
suggests that the changes made by one developer might have an influence on the
execution of changes made by the other.

###  3.2. Limitations

Our analyses suffer from limitations that are typical in static analyses.
First, we do not detect interference that might result from the execution of
code that uses Java reflection, and we do not analyze Java native methods.
Second, our analyses do not differentiate specific positions of an array. We
also have to compromise precision with the analysis complexity and execution
time. For instance, our current implementation for detecting OA is not
_object-sensitive_. This could lead the analyses to report interference that
does not exist (a false positive). Similarly, the current SVFA implementation
we use is not fully accurate (as expected) and might lead to false positives
and false negatives. This is particularly true for corner cases whose state
elements involve fields.

##  4\. Evaluation Method

To evaluate the potential of our static analyses for detecting interference,
we follow the experimental design illustrated in Figure 5 and explained in the
rest of this section. We want to understand how _accurate_ and
_computationally efficient_ our analyses are for detecting interference, with
the aim of understanding whether they could be useful as the basis of semantic
merge conflict detection tools.

Figure 5. Experiment setup. We start with open-source Java projects from
GitHub, and select merge scenarios with methods or constructors changed by
both developers. For each scenario, we build the merge commit version,
generating a JAR file without external project dependencies. We also extract
information about the method changed by both developers, and the specific
lines they have changed; this method is given as the analyses entry point, and
the line information is used to annotate the internal code representation
adopted by our analyses. Finally, we run the implemented static analyses,
collect execution time information, and compare interference ground truth with
the logical disjunction of the four analyses results.

###  4.1. Merge Scenario Selection

We start with open-source Java projects from GitHub, and select merge
scenarios (quadruples formed by a merge commit, its two parents, and a Base
commit) having operations (methods or constructors) that were independently
changed by both developers. We rely on a number of Java projects and scenarios
that appeared in previous studies on semantic merge conflicts (Barros Filho,
2017; Sousa et al., 2018; Da Silva et al., 2020; Silva, 2022), and mine new
ones following similar criteria.

We discard fast-forward and criss-cross merge commits (Chacon and Straub,
2014). The former don’t correspond to code integration from _two_ developers,
the phenomenon we want to investigate; the latter don’t have a single most
recent common ancestor, therefore not characterizing a single merge scenario.
Following previous work, we focus on scenarios with declarations changed by
both developers, as, in this way, one can more easily establish interference
ground truth. Contrasting with previous work on dynamic analysis (Da Silva et
al., 2020; Silva, 2022), we discard scenarios having only _field_ declarations
changed by both developers; this is also adopted by related work on
information flow analysis (Barros Filho, 2017) and verification (Sousa et al.,
2018) since they also require a _method_ or _constructor_ declaration as the
analysis entry-point.

As a merge scenario might have more than one operation that was independently
changed by both developers, we consider pairs $(scenario,operation)$ as our
_experimental units_. We mostly reuse units that originally appeared in the
datasets of previous work: 35 units from (Silva, 2022), 31 from (Barros Filho,
2017), and 30 from (Sousa et al., 2018), as illustrated in Table 1. Together
with the three new units that first appear in this work, we have a total of 99
experimental units, associated with 54 merge scenarios extracted from 39
projects.

Table 1. Summary of reused experimental units. Second column shows the number of units we reused in our dataset, whereas the third column shows the number of units that originally appear in the dataset of the corresponding source. Source | Our Dataset | Original in paper
---|---|---
(Silva, 2022) | 35 | 42
(Barros Filho, 2017) | 31 | 35
(Sousa et al., 2018) | 30 | 52

As our experiment requires entry points and the creation of JAR files for each
unit, we discard from the related work datasets the experimental units with
build issues222Units with compilation problems, need for installing extra
frameworks, generated JAR without method to be analyzed, or several JARs but
none conforms to the name conventions adopted by our experimental
infrastructure. or no operation changed by both developers; so the differences
in numbers appearing in the second and third columns of Table 1. All the
information (commit hashes, source project and class, summary of changes made
by each developer, etc.) about the projects, scenarios, and units is available
from our online appendix (onl, 2023). Among the projects, we have
elasticsearch and webbit, showing a considerable degree of diversity
concerning dimensions such as project domain (the first is a search engine,
the second is an HTTP server), size (1096 KLOC versus 20 KLOC), stars (4,232
versus 68,509), commits (69,697 versus 770), forks (23,351 versus 186), and
number of collaborators (2,054 versus 39).

###  4.2. Preparing Analyses Inputs

For each scenario selected in the previous section, we build the merge commit
version.333As we don’t analyze the other commits in a scenario, there is no
need to build them. The resulting JAR file is used as input for our static
analysis infrastructure, which translates Java bytecode into the Jimple
intermediate representation (one of the representations the Soot framework
supports) (Vallée-Rai et al., 2010), before running the analyses. We generate
JAR files without external project dependencies. This improves analysis
performance, as less code is analyzed. On the downside, this likely degrades
analysis accuracy. As this trade-off seems promising for potential practical
uses of static analysis for detecting interference, we opted for this
experimental design.

Besides a JAR file, our analysis infrastructure requires two more inputs. So,
for each merge scenario we also extract information about the operation (class
method or constructor) changed by both developers, and the specific lines they
have changed, that is, included or modified; pure deletions are not
considered. The operation is given as the analyses entry points. In case more
than one operation was changed by both developers, the scenario yields more
than one experimental unit.

The line information is used to annotate the internal code representation
adopted by our analyses, which, for example, detect interference by finding
data and control flows between instructions changed by one developer to
instructions changed by the other. So knowing which instructions were changed
by each developer is essential for our analyses to work. We obtain the lines
changed by one parent by taking its syntactical diff with the Base commit. For
that, we use the DiffJ tool.444DiffJ compares Java files based on their code,
available at: https://github.com/jpace/diffj Comparing to a textual diff,
DiffJ brings direct and more accurate information about the changed
declarations and the lines changed inside them. Using the extracted line
information, our infrastructure annotates the Jimple representation of the
code.

As two of the 99 selected experimental units have entry points containing long
chains of method calls that spread across a number of lines, they were
slightly refactored before building their JAR files. We manually extracted
local variables that are initialized with subexpressions of the chain, in such
a way that the original behavior is preserved, but changed line information is
more accurately carried on to the bytecode and the intermediate representation
used by our analyses. We illustrate this in Figure 6, showing the original
code on the left and the refactored one on the right.

Figure 6. Realistic experimental unit example. Original code on the left,
refactored one on the right. Commit 0d6914dc757d from project _elasticsearch_.

In the original code, line 144 corresponds to a change made by one developer,
say Left; line 143 is a change made by developer Right. As the same statement
(the assignment starting on line 142) contains changes made by both
developers, incorrect line information might reach the analyses. In fact, the
method call on line 144 is translated to instructions that first store on an
array the put arguments, and then invoke this method. The array storage
instructions, though, are incorrectly annotated as Right, leading to incorrect
analysis results indicating that there is a dataflow from Right to Left. With
the refactored example on the right, each statement is on a different line,
leading to accurate annotation and analyses results. Similarly, we manually
refactored a ternary if expression that was spread across two lines. So we can
say our sample consists of 96 real scenarios and three realistic scenarios.

For 31 merge scenarios, we could not automatically build the project with the
existing build configuration files. In these cases, we manually changed the
configuration files, for example by updating dependencies and removing test
execution steps in the build process. In most cases, we had to simply change
the configuration file to properly use the Maven Assembly plugin (mav, 2023).
In two cases we had to manually change the code to successfully build the
project. In one of them we just commented part of a test code that was
breaking the build due to the lack of external resources. In the other we had
to refactor the code to work with a newer version of a dependency, as it had
changed a constructor interface. For helping replication, all modifications
are documented in README files available in our repository with the whole
dataset (see our online appendix (onl, 2023)).

###  4.3. Running Analyses

With the prepared analyses inputs, in this step we run, for each experimental
unit, the algorithms we implemented to detect interference (Section 3). For
performance reasons, the interprocedural analyses (that detect Data Flow,
Confluence, and Overriding Assignments interferences) are all executed with
nesting level five, meaning that they only analyze methods called up to five
levels deep from the entry point.

These analyses are also configured to use the Spark (Lhoták and Hendren, 2003;
Lhoták, 2003) points-to analysis framework, increasing the call graph
precision—in comparison to other alternatives like Rapid Type Analysis and
Class Hierarchy Analysis (Smaragdakis and Balatsouras, 2015). We also
configured Soot so that it keeps line numbers obtained from bytecode and does
not consider classes in standard Java libraries, except for basic classes like
String, RuntimeException, and the ones that simply encapsulate primitive types
(Integer, Long, etc.). So classes like ArrayList and HashMap are not
considered, for example.

Besides collecting the analysis results reporting interference or its absence,
we collect execution time information for each analysis and the logical
disjunction of all the analysis results. For that, we run each analysis ten
times for each of the 99 experimental units.

###  4.4. Summarizing Results

In this final step of our experiment, we compare the interference ground truth
with the logical disjunction of the analyses results, and compute precision,
recall, F1, and accuracy metrics. At least two researchers manually analyze
each unit and check for interference using the definition in the introduction,
and conditions that imply interference (Horwitz et al., 1989).555There is a
state element $x$ such that Base, Left, and Right compute different values for
$x$; Left (or Right) computes a different value for $x$ compared to both the
Base program and the merged version; or Base, Left, and Right compute the same
value for $x$, but the merged version computes a different value.

In case of disagreement, the researchers discuss the experimental unity with
one more researcher and reach a verdict. In case of agreement, they present
the experimental unity and its evaluation to the other researchers in the
group. To significantly reduce the chances of misjudgment, each interference
verdict comes with a manually designed test case that reveals the interference
(for instance, by breaking on the Base version, passing on one of the parents
version, and breaking again in the merge version). Similarly, each non-
interference verdict has an explanation of why we could not design such a test
case.

We also summarize and analyze the execution time information in a number of
ways. These activities and the ones in the previous step are automated and
implemented as a docker container for reproducibility purposes (see our online
appendix (onl, 2023)).666The activities in the first two steps are also
automated, but require manual effort in a number of scenarios, as explained
earlier. That is why the replication container contains only the activities in
the last two steps of our experiment.

Additionally, we manually investigate all the scenarios classified as false
positives (the analyses incorrectly report interference) and false negatives
(the analyses don’t report existing interference). We classify the causes
behind the analyses inaccuracies, to better explain our results and understand
how it can be improved by future work.

##  5\. Evaluation Results

We now report the _accuracy_ and _computational efficiency_ results we
obtained by running the experiment as described in the previous section, using
our sample of 99 experimental units.

###  5.1. Accuracy Results

We depict the confusion matrix of our experiment as Table 2, which shows that
our sample contains 33 units with interference, and 66 without interference.
The logical disjunction of our analyses results— hereafter “our analyses,” for
simplicity— reports 26 false positives (incorrectly predicted interference)
and 13 false negatives (non reported interference).

Table 2. Confusion matrix. Prediction is established by the logical disjunction of the four analyses results. | Actual |
---|---|---
| Positive | Negative | Total
Predicted | Positive | $20$ | $26$ | $46$
Negative | $13$ | $40$ | $53$
| Total | $33$ | $66$ | $99$

These numbers result in the accuracy measures we show in the first SA (for
Static Analysis, that is, the technique we evaluate here) column grouped under
Techniques in Table 3. The last row in that column indicates the number of
experimental units considered for computing the measures. With 26 false
positives, our analyses precision reaches only 0.43, but our recall reaches
0.60. This shows significant interference detection capability, but with
potentially significant costs for handling false positives.

To better contextualize these accuracy results, we investigate how our
analyses compare with interference detection techniques proposed by previous
work, which report at least enough information for computing precision. As
comparing accuracy measures based on different datasets could introduce bias
that would be hard to identify and explain, and running other people tools on
a larger sample could be difficult, we recompute the SA metrics for subsamples
that are common to our dataset and the datasets used by each related work.

Table 3. Accuracy metrics and comparison with previous work and their datasets. We use SA for the Static Analyses we propose here, IF for the Information Flow analysis used in (Barros Filho, 2017), DA for the Dynamic Analysis used in (Da Silva et al., 2020; Silva, 2022), and VA for the Verification Algorithm used in (Sousa et al., 2018). Metrics | Techniques
---|---
| SA | SA | DA | SA | IF | SA | VA
Precision | 0.43 | 0.45 | 0.80 | 0.65 | 0.54 | 0.16 | 0.22
Recall | 0.60 | 0.60 | 0.14 | 0.88 | - | 0.20 | -
F1 Score | 0.50 | 0.52 | 0.24 | 0.75 | - | 0.18 | -
Accuracy | 0.60 | 0.58 | 0.66 | 0.67 | - | 0.70 | -
Units | 99 | 75 | 75 | 31 | 31 | 30 | 30

So the SA–DA column group under Techniques in Table 3 shows the accuracy
measures we obtained by running our analyses and the Dynamic Analysis (DA)
proposed in (Silva, 2022), using 75 experimental units that are common to both
our dataset and the one used by this related work.777This work dataset
contains 85 units, 42 of which originally appear in that paper, and 43 are
reused from previous work. Of these 85 units, we could use in our experiment
only 75, as four of them are related to changes in field declarations, and six
we could not successfully build. With this subsample, our analyses precision
is at 0.45, slightly higher than with our complete dataset; we see no change
on recall. The DA precision is 0.8 (against 0.69 in their complete dataset,
but not shown in the table), but recall is at 0.14 (0.32 in their dataset).

In the SA–IF column group we compare our analyses with the Information Flow
analysis (IF) proposed in (Barros Filho, 2017). We had only 31 common
experimental units in the two datasets. With this subsample, our analyses
precision (0.65) and recall (0.88) are much higher than with our complete
dataset. Our precision is also higher than the one presented by IF (0.54,
against 0.57 in their full dataset). Unfortunately, due to the experiment
design adopted by the authors— they only collect and manually analyze merge
scenarios for which their tool reports interference— we cannot compute recall
and the other metrics for IF.

Finally, in the SA-VA column group we compare our analyses with the
Verification Algorithm (VA) proposed in (Sousa et al., 2018). We had only 30
common experimental units in the two datasets. With this subsample, our
analyses precision (0.16) is much lower than with our complete dataset, but
comparable to theirs (0.22, against 0.85 with their complete dataset). This
variation is due to a subsample with only five positives, our tool missing
four of them; the percentage of true positives in the sample is approximately
seven times lower than in the complete sample, significantly affecting
precision.888With five false positives (among 25 negatives), the percentage of
false positives in the sample is comparable to the complete dataset. As the
authors manually analyze only merge units for which their tool reports
interference, their paper has no information on false negatives, and therefore
doesn’t report recall and the other metrics.

### Manual analysis of false positives and negatives

To better understand the reasons for our analyses inaccuracies, we manually
analyze the 26 false positives and 13 false negatives we show in Table 2.
Figure 7 summarizes the analysis results, giving the reasons for
misclassification, and the number of units misclassified in each category.

Figure 7. Classification of our analyses false positives (incorrectly reported
interference) and false negatives (non reported interference).

The main reason for false positives, with 14 misclassifications, is
refactoring changes. Figure 8 illustrates an example. The changes on the Right
correspond to an extract method refactoring, where direct accesses to the
metricsRegistry field were replaced by calls to the corresponding get method.
This does not affect the behavior of the illustrated method, and therefore
does not interfere with the change illustrated on the left. However, our DF
analysis incorrectly reports interference because all calls to the get method
are annotated as _right_ , the new call to forRegistry is annotated as _left_
, and there is a dataflow from _right_ to _left_ instructions; the forRegistry
call reads the metricsRegistry field that is written by the register method
calls.

Figure 8. Refactoring false positive. The Base version appears on the center.
The parents changes appear on the left and the right. Experimental unit from
project _dropwizard_ , merge commit 4aba1556eb88.

In summary, _structural_ refactorings999Not all refactorings are interference
free. Consider code with a redundancy, like two null pointer checks. If
developer Left removes one of the checks, and Right removes the other, both
applied non structural refactorings, but the changes interfere. lead to
unnecessary code annotation in our technique, and that might incorrectly
trigger our analyses interference detection.

The are a number of other reasons for false positives. We observe Harmless
code insertion when both developers add new statements— like assignments to
different fields— that change behavior but affect unrelated state elements; a
new flow, though, is created due to the insertions. Harmless code change is
similar, but the developers modify existing code instead of inserting new
statements. Harmless flow is when there is a valid flow but it existed before
integration, that is, it wasn’t created by the changes. Conservative flow is
due to the conservative nature of static analysis; it detects a flow that in
practice cannot occur, for instance, because our analyses are not object
sensitive. Lastly, there could be annotated related false positives when line
information is incorrectly carried on to the bytecode and internal
representation.

Moving now to false negatives, one significant reason for misclassification is
when the changes made by at least one of the developers consist of line
deletions, instead of modifications or insertions. As our analyses are
executed on the Merge commit version, they see no trace of the deleted lines,
and therefore cannot compute new flows or overridings caused by the deletions.
Figure 9 illustrates a case, where both developers delete lines that interfere
as they have an effect on the final returned value. Our analyses, however,
fail to detect interference as no instruction is annotated in this case.

Figure 9. Removed lines false negative. The Base version appears on the
center. The parents changes appear on the left and the right. Experimental
unit from project _Storm_ , merge commit 8110162b7ac

.

This reveals a drawback of our static analysis technique, which relies on the
merged version and instruction annotation information associated with the
integrated changes (deletions excluded).

A number of false negatives are due to limitations of our analyses current
implementation or how we invoke them. Interface implementation, for example,
occurs because the analyses don’t exploit global information that could
provide potential implementations for an interface or abstract class; so the
analyses end up not visiting methods that could reveal the interference. Class
dependencies false negatives occur because we run the analysis with JARs that
don’t include external dependencies, but interference could occur in classes
from these dependencies. Exception and Recursive methods false negatives
respectively result from our analyses not computing exceptional control flows,
and analyzing recursive methods just once. Finally, Complex conditions false
negatives are caused by a Soot current limitation that doesn’t correctly carry
on correct line information for conditions involving more than two
subexpressions.

###  5.2. Performance Results

We carry out our experiments using the procedures we explained in Section 4
and an Ubuntu docker container running on an Intel Xeon Gold 6338 server with
2Tb of RAM. Figure 10 shows the average execution time results for each
experimental unit (red dots in the figure), as we run our four analysis 10
times for each unit. Variation across the 10 executions is small, with
standard deviation ranging from 0.04s (in a scenario with 11.74s average) to
11.74s (in a scenario with 340.45s average).

Figure 10. Execution time results. Each red dot depicts the average time of 10
executions of our four analyses with one experimental unit. Median is depicted
by the red line at 17.8s. For legibility, we omit one outlier, which takes
1421.44 to execute.

The median is at 17.8s for executing together the four analyses, including
their setup, graph or abstraction construction, interference checking, and
result reporting. Most units are analyzed in less than 100s, with an
implementation that isn’t optimized, and could be significantly improved in a
number of ways, like by computing a lazy logical disjunction of the analyses,
by sharing common setup tasks among the analyses, and by parallelizing
analysis execution, as they are independent from each other. Closely related
work benchmarked in the accuracy results either report no performance results,
or report much larger execution times. One can take hours running IF— which
relies on the construction of System Dependence Graphs (Graf et al., 2013;
Snelting et al., 2015; Graf et al., 2015)— for a single merge scenario; or
five minutes only to generate tests with DA, the time to execute them being
considerable depending on the project.

The depicted outliers, and especially the one that we omitted and that takes a
little more than 1400s to execute, consume most time running the
interprocedural Data Flow (DF) analysis, both directly and indirectly through
Confluence Flow (CF). They all involve a large number of methods that are
visited by DF and CF.

For DF, the number of visits is not directly associated with the size of the
entry-point method, although the 1400s outlier has a large entry-point with
235 LOC. What matters is the number of annotated instructions, which
corresponds to the number of lines changed by the developers and integrated in
the merge commit. The more annotated instructions, the more methods are
visited and the bigger is the resulting graph. However, as annotated method
calls with DF lead to annotated method bodies, the size of the methods called
by the entry-point, and recursively, matters as well. In the longest outlier,
the entry-point method has an annotated method call for a method with 219 LOC,
all of which are annotated as well, recursively leading to 570 methods being
visited by our analysis. The deepest level reached in such a case was four,
indicating that time was spent in a breadth rather than depth exploration from
the entry-point.

For CF, the size of the entry-point method (and recursively the methods it
calls) matter, as this analysis essentially visits all called methods. So the
size of the entry-point method in this outlier explains much of the long
execution time.

Running the experiment with a depth limit of 10, instead of 5, increases
execution time by a factor of 3 to 6, depending of the analysis. This,
however, brings no significant change on accuracy results. So we found no need
to experiment with other depth limits.

###  5.3. Threats to Validity

#### Construct validity

Checking for dynamic semantic conflicts is hard with the type of experiment we
describe here, as with such design we don’t have access to developers desires
or even specification they worked against. So we follow previous work on
dynamic semantic conflicts and adopt a study design that checks for
interference, and uses interference ground truth. There is still, though, a
construct threat that is common to previous work: we focus on _locally
observable interference_ , that is, we consider only interference that can be
detected in the method being analyzed and, recursively, in the methods called
from it. It would be hard to manually carry on a global interference analysis
considering the whole project.

#### Internal validity

Line annotation as used by our technique is sensitive to the Java compiler
version. Different compilers might carry on to bytecode slightly different
line information, consequently leading to different analyses results. We used
the JDK Java compiler, as it is likely one of the most widely used. So our
results would hopefully be observed by a significantly number of developers.

As described earlier, some of the scenarios and experimental units in our
dataset required manual modifications, especially in configuration files, to
compile or to make line information more accurate. The compilation changes
mostly involve dealing with newer dependencies versions; as these are used
only to successfully compile the project, and are not included in the analyzed
JAR files, there is limited risk of affecting analysis results. The line
information change in three cases might impact the results; so we say that our
experiment relies on three realistic and 96 experimental units.

#### External validity

Although larger than the datasets used in previous work on dynamic semantic
conflicts, our dataset is still limited. So we can’t generalize the obtained
results for other samples of merge scenarios and projects, not to mention
programming languages. Even with a larger dataset, we would still have limited
generalization power, as illustrated by the varying results we obtain with the
different subsamples used for comparing our technique with each closely
related work.

##  6\. Discussion

Based on the accuracy and performance results reported in the previous
section, we discuss whether our static analyses could be useful as the basis
of semantic merge conflict detection tools.

A tool that first applies textual (Khanna et al., 2007) or structured merge
(Apel et al., 2012; Cavalcanti et al., 2017; Seibt et al., 2021) and then runs
our analyses on the merged code could benefit from the interference detection
capability of the analyses. This capability is evidenced by the experiment
recall results; SA being much superior than DA. We expect that such a tool
would be more effective than current practices for semantic conflict
detection, which are based on code review and running project tests.
Nevertheless, given our analyses are unable to detect interference in a non
neglectable percentage of cases, the tool should be used in addition to the
practices, especially when avoiding semantic conflicts is critical.

The precision results, though, show that these benefits would come with
potentially significant costs for handling false positives from an SA based
tool. The costs would be inferior than if using IF, for example, and could
nevertheless be worth in more critical contexts where letting conflicts escape
to the production environment can be harmful or costly. In less critical
contexts, a DA based tool— with better precision, but much worse recall —
could be more adequate, in spite of the higher computational costs of running
test based dynamic analysis.

The false positives costs could be likely reduced by a tool that is also able
to detect refactoring changes (Silva and Valente, 2017; Tsantalis et al.,
2022). If all the changes from one developer are structural refactorings, the
tool can simply report no interference; no need for calling the analyses in
this case. Otherwise, the tool can invoke the analyses and filter out
resulting flows if either the start or the end of the flow is an instruction
associated with a refactoring change. This could avoid a significant part of
the false positives in our sample. We need, however, further study to
understand how the inaccuracies of SA interplay with those from refactoring
detection tools.

Making the analyses more accurate could also help to reduce the false positive
costs, by reducing the conservative flows we report in the previous sections.
But we expect no major impact from that. The other false positive categories
(harmless code insertion, change, and harmless flow, etc.) are inherent to our
technique and cannot be avoided.

Most false negatives we observed are due to limitations of our analyses
current implementation or how they are invoked. Improving that could increase
the potential of an SA based tool. But there is a complex trade-off between
such improvements and their impact on performance and false positives, and
further study is necessary to understand that. The removed lines false
negatives are inherent to our technique, and the complex condition one can be
eliminated by fixing the Soot analysis infrastructure we use.

The performance results suggest that an SA based tool has the potential to be
invoked for most merge situations, especially considering that the current
analyses implementation has plenty of room for optimization, as discussed in
the previous section. Although analysis depth is controlled by our
implementation, breadth is not and could be a problem for a few cases, as the
discussed outliers show. In these cases, background checking as, for instance,
with continuous integration servers would be an option. A SA based tool,
though, should have much better performance than an IF, DA, and likely a VA
tool as well.

A semantic merge conflict detection tool could not be restricted to changes in
the same operation, as considered in our experiment. Handling such situations
would simply require an algorithm for finding or creating a proper entry point
that captures the integrated changes. This, however, could require running the
analyses with different depth levels, leading to longer execution times.

Although we have focused on Java projects, a large part of our analysis
infrastructure could be applied to other languages compiled to Java bytecode.
Most ideas could also be applied to other languages. Results would be likely
inferior for dynamic languages. For such languages, DA could be a more
promising alternative. This technique can also capture interference due to
changes in field declarations with initializations (Da Silva et al., 2020). To
capture that, a SA based tool would require a simple preprocessing
transformation for creating an entry-point method containing the
initialization code. Similarly, extract variable transformations would help to
to avoid the line annotation issues we mentioned in Section 4.

##  7\. Related Work

Horwitz et al. first studied dynamic semantic conflicts (Horwitz et al., 1989,
1990; Yang et al., 1992) and formalize the interference definition we use
here. They, however, propose the construction of PDGs (Horwitz et al., 1989)
and SDGs (Horwitz et al., 1990) for the four program versions in a merge
scenario, and compute differences between these to detect and resolve
interference; to compute differences, they rely on the use structured editors
to identify AST nodes changed in each of the revisions. Although inspired by
this seminal work, and also using PDGs, our technique only analyzes the merge
version— which is annotated with line changing information— and avoids some of
the heavyweight analysis needed to construct SGDs. By not dealing with four
graphs as they do, we can’t detect the effects that line deletions might have
on interference. On the other hand, we gain in efficiency, and likely in
precision, but losing in recall. We can’t know for sure as they don’t
empirically evaluate their technique, nor provide implementations. More recent
work (Barros Filho, 2017) gets close to that, using the JOANA framework
(Hammer and Snelting, 2009) to build a single SDG for the merge version in a
scenario. This, however, can take hours to construct, whereas our analyses run
much faster. In Section 5, we compare this in more detail with our approach,
showing experimental results. Overall, our technique presents better but
comparable precision; we were not able to compare recall due to the related
work experiment design.

Instead of static analysis, Silva et al. (Da Silva et al., 2020) detects
interference by using a dynamic analysis based on automated unit test
generation. They rely on test passing criteria that suggests interference— if
a generated test breaks with the Base version, and passes in one of the
parents, and breaks again in the merge is evidence that the change carried on
by this parent is not preserved in the merge version. They need no line change
information, and can detect interference due to removed lines and changes in
field declarations. We compare this in more detail in Section 5. Overall, our
technique presents much better recall but much inferior precision. Our
performance should also be much better than theirs, based on the little
information (only test generation time, not test execution time) they provide
about that. The combination of both techniques could be a promising direction
for future work.

A third technique for interference detection is explored by Sousa et al.
(Sousa et al., 2018), which statically infers relational post-conditions from
the merge scenario code versions, establishing constraints on how state
elements can be modified by different versions in such a way to avoid
interference. It then applies theorem proving, as in SMT solving, to check if
the constraints are satisfiable. We again compare this in more detail in
Section 5, showing comparable precision to our approach; we were not able to
compare recall due to the related work experiment design. Performance from
this verification approach can be considerably higher than our approach with
larger programs that were changed in a number of places.

More recently, researchers have applied large language models to detect
integration conflicts (Zhang et al., 2022). Although their motivation involves
the three kinds of conflicts we discuss in the introduction, in the paper they
report results only about textual and static semantic (build) conflicts. They
claim that dealing with dynamic semantic conflicts would be hard, especially
for establishing ground truth to train and test such models. With static
semantic conflicts, they obtain slightly higher precision than we obtain here
with dynamic semantic conflicts. Brun et al. (Brun et al., 2013) also discuss
semantic conflicts, but mostly collect evidence of static semantic conflicts.
They use project tests to detect dynamic semantic conflicts. Previous work
(Sarma et al., 2011; Apel et al., 2011, 2012; Cavalcanti et al., 2017, 2019;
Da Silva et al., 2022) tries to prevent, detect, or resolve textual and static
semantics conflicts.

##  8\. Conclusions

We present a technique and a set of static analyses that show significant
interference detection capability, and potential for detecting dynamic
semantic conflicts. It comes, though, with potentially significant costs for
handling false positives. Comparing with previous work (Barros Filho, 2017;
Sousa et al., 2018; Silva, 2022), our technique shows much better F1 score and
recall than the dynamic analysis technique, but with much worse precision. Our
precision is comparable to the ones presented by the SDG and theorem proving
techniques. We also manually analyze and classify our analyses’ false
positives and negatives, and discuss how, for instance, our precision could be
significantly improved if we applied refactoring detection techniques before
running the analyses. The performance results show that our analyses should
have much better performance than previous techniques. In summary, besides
existing limitations, our experience suggests that our technique is feasible,
and might complement dynamic analysis alternatives that aim to detect
interference.

###### Acknowledgements.

For partially supporting this work, we would like to thank INES (National
Software Engineering Institute) and the Brazilian research funding agencies
CNPq, FACEPE (grants IBPG-0029-1.03/20), and CAPES. SPG, Christian, colegas
que ajudaram com dataset, mining, análises, ferramentas, etc.

## References

  * (1)
  * mav (2023) Accessed: July 2023.  Maven Assembly plugin. available at: https://maven.apache.org/plugins/maven-jar-plugin/.
  * onl (2023) Accessed: July 2023.  Online Appendix. available at: https://anonymous.4open.science/w/papers-7D74/semantic-conflicts-static-analysis.html.
  * Apel et al. (2012) Sven Apel, Olaf Leßenich, and Christian Lengauer. 2012\.  Structured merge with auto-tuning: balancing precision and performance. In _Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering_. 120–129.  https://doi.org/10.1145/2351676.2351694
  * Apel et al. (2011) Sven Apel, Jörg Liebig, Benjamin Brandl, Christian Lengauer, and Christian Kästner. 2011\.  Semistructured merge: rethinking merge in revision control systems. In _Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering_. 190–200.  https://doi.org/10.1145/2025113.2025141
  * Arzt et al. (2014) Steven Arzt, Siegfried Rasthofer, Christian Fritz, Eric Bodden, Alexandre Bartel, Jacques Klein, Yves Le Traon, Damien Octeau, and Patrick McDaniel. 2014.  FlowDroid: Precise Context, Flow, Field, Object-Sensitive and Lifecycle-Aware Taint Analysis for Android Apps. In _Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation_ (Edinburgh, United Kingdom) _(PLDI ’14)_. Association for Computing Machinery, New York, NY, USA, 259–269.  https://doi.org/10.1145/2594291.2594299
  * Barros Filho (2017) Roberto Souto Maior de Barros Filho. 2017\.  _Using information flow to estimate interference between same-method contributions_.  Master’s thesis. Federal University of Pernambuco.
  * Binkley et al. (1995) David Binkley, Susan Horwitz, and Thomas Reps. 1995\.  Program integration for languages with procedure calls.  _ACM Transactions on Software Engineering and Methodology (TOSEM)_ 4, 1 (1995), 3–35.  https://doi.org/10.1145/201055.201056
  * Brun et al. (2013) Yuriy Brun, Reid Holmes, Michael D Ernst, and David Notkin. 2013\.  Early detection of collaboration conflicts and risks.  _IEEE Transactions on Software Engineering_ 39, 10 (2013), 1358–1375.  https://doi.org/10.1109/TSE.2013.28
  * Cavalcanti et al. (2017) Guilherme Cavalcanti, Paulo Borba, and Paola Accioly. 2017\.  Evaluating and improving semistructured merge.  _Proceedings of the ACM on Programming Languages_ 1, OOPSLA (2017), 1–27.  https://doi.org/10.1145/3133883
  * Cavalcanti et al. (2019) Guilherme Cavalcanti, Paulo Borba, Georg Seibt, and Sven Apel. 2019.  The impact of structure on software merging: semistructured versus structured merge. In _2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 1002–1013.  https://doi.org/10.1109/ASE.2019.00097
  * Chacon and Straub (2014) Scott Chacon and Ben Straub. 2014.  _Pro git_.  Springer Nature.
  * Da Silva et al. (2020) Leuson Da Silva, Paulo Borba, Wardah Mahmood, Thorsten Berger, and João Moisakis. 2020.  Detecting semantic conflicts via automated behavior change detection. In _2020 IEEE International Conference on Software Maintenance and Evolution (ICSME)_. IEEE, 174–184.  https://doi.org/10.1109/ICSME46990.2020.00026
  * Da Silva et al. (2022) Léuson Da Silva, Paulo Borba, and Arthur Pires. 2022\.  Build conflicts in the wild.  _Journal of Software: Evolution and Process_ 34, 4 (2022), e2441.  https://doi.org/10.1002
  * Ferrante et al. (1987) Jeanne Ferrante, Karl J Ottenstein, and Joe D Warren. 1987\.  The program dependence graph and its use in optimization.  _ACM Transactions on Programming Languages and Systems (TOPLAS)_ 9, 3 (1987), 319–349.  https://doi.org/10.1145/24039.24041
  * Graf et al. (2013) Jürgen Graf, Martin Hecker, and Martin Mohr. 2013\.  _Using joana for information flow control in java programs-a practical guide_.  Gesellschaft für Informatik eV, Bonn. 123–138 pages.
  * Graf et al. (2015) Jürgen Graf, Martin Hecker, Martin Mohr, and Gregor Snelting. 2015.  Checking applications using security APIs with JOANA. In _8th International Workshop on Analysis of Security APIs_.  https://pp.ipd.kit.edu/uploads/publikationen/joana15asa.pdf
  * Grech and Smaragdakis (2017) Neville Grech and Yannis Smaragdakis. 2017.  P/Taint: Unified Points-to and Taint Analysis.  _Proc. ACM Program. Lang._ 1, OOPSLA, Article 102 (oct 2017), 28 pages.  https://doi.org/10.1145/3133926
  * Hammer and Snelting (2009) Christian Hammer and Gregor Snelting. 2009.  Flow-Sensitive, Context-Sensitive, and Object-Sensitive Information Flow Control Based on Program Dependence Graphs.  _Int. J. Inf. Secur._ 8, 6 (oct 2009), 399–422.  https://doi.org/10.1007/s10207-009-0086-1
  * Horwitz et al. (1989) Susan Horwitz, Jan Prins, and Thomas Reps. 1989.  Integrating noninterfering versions of programs.  _ACM Transactions on Programming Languages and Systems (TOPLAS)_ 11, 3 (1989), 345–387.  https://doi.org/10.1145/65979.65980
  * Horwitz et al. (1990) 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.  https://doi.org/10.1145/77606.77608
  * Khanna et al. (2007) Sanjeev Khanna, Keshav Kunal, and Benjamin C Pierce. 2007\.  A formal investigation of diff3. In _FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science: 27th International Conference, New Delhi, India, December 12-14, 2007. Proceedings 27_. Springer, 485–496.  https://doi.org/978-3-540-77050-3_40
  * Lhoták (2003) Ondrej Lhoták. 2003\.  _Spark: A flexible points-to analysis framework for Java_.  Ph. D. Dissertation. McGill University.
  * Lhoták and Hendren (2003) Ondrej Lhoták and Laurie J. Hendren. 2003.  Scaling Java Points-to Analysis Using SPARK. In _Compiler Construction, 12th International Conference, CC 2003, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2003, Warsaw, Poland, April 7-11, 2003, Proceedings_ _(Lecture Notes in Computer Science, Vol. 2622)_ , Görel Hedin (Ed.). Springer, 153–169.  https://doi.org/10.1007/3-540-36579-6_12
  * Pastore et al. (2017) Fabrizio Pastore, Leonardo Mariani, and Daniela Micucci. 2017\.  BDCI: Behavioral driven conflict identification. In _Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering_. 570–581.  https://doi.org/10.1145/3106237.3106296
  * Sarma et al. (2011) Anita Sarma, David F Redmiles, and Andre Van Der Hoek. 2011\.  Palantir: Early detection of development conflicts arising from parallel code changes.  _IEEE Transactions on Software Engineering_ 38, 4 (2011), 889–908.  https://doi.org/10.1109/TSE.2011.64
  * Seibt et al. (2021) Georg Seibt, Florian Heck, Guilherme Cavalcanti, Paulo Borba, and Sven Apel. 2021.  Leveraging structure in software merge: An empirical study.  _IEEE Transactions on Software Engineering_ 48, 11 (2021), 4590–4610.  https://doi.org/10.1109/TSE.2021.3123143
  * Shao et al. (2009) Danhua Shao, Sarfraz Khurshid, and Dewayne E Perry. 2009\.  SCA: a semantic conflict analyzer for parallel changes. In _Proceedings of the 7th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering_. 291–292.  https://doi.org/10.1145/1595696.1595747
  * Shi et al. (2018) Qingkai Shi, Xiao Xiao, Rongxin Wu, Jinguo Zhou, Gang Fan, and Charles Zhang. 2018\.  Pinpoint: Fast and Precise Sparse Value Flow Analysis for Million Lines of Code.  _SIGPLAN Not._ 53, 4 (jun 2018), 693–706.  https://doi.org/10.1145/3296979.3192418
  * Silva and Valente (2017) Danilo Silva and Marco Tulio Valente. 2017.  RefDiff: Detecting refactorings in version histories. In _2017 IEEE/ACM 14th International Conference on Mining Software Repositories (MSR)_. IEEE, 269–279.  https://doi.org/10.1109/MSR.2017.14
  * Silva (2022) Léuson Mário Pedro da Silva. 2022\.  _Detecting, understanding, and resolving build and test conflicts_.  Ph. D. Dissertation. Federal University of Pernambuco.
  * Smaragdakis and Balatsouras (2015) Yannis Smaragdakis and George Balatsouras. 2015.  Pointer Analysis.  _Foundations and Trends® in Programming Languages_ 2, 1 (2015), 1–69.  https://doi.org/10.1561/2500000014
  * Snelting et al. (2015) Gregor Snelting, Dennis Giffhorn, Jürgen Graf, Christian Hammer, Martin Hecker, Martin Mohr, and Daniel Wasserrab. 2015.  Checking probabilistic noninterference using JOANA.  _Information Technology_ (2015).  https://doi.org/10.1515/itit-2014-1051
  * Sousa et al. (2018) Marcelo Sousa, Isil Dillig, and Shuvendu K Lahiri. 2018\.  Verified three-way program merge.  _Proceedings of the ACM on Programming Languages_ 2, OOPSLA (2018), 1–29.  https://doi.org/10.1145/3276535
  * Sui and Xue (2016) Yulei Sui and Jingling Xue. 2016.  SVF: interprocedural static value-flow analysis in LLVM. In _Proceedings of the 25th international conference on compiler construction_. 265–266.  https://doi.org/10.1145/2892208.2892235
  * Sui et al. (2014) Yulei Sui, Ding Ye, and Jingling Xue. 2014.  Detecting Memory Leaks Statically with Full-Sparse Value-Flow Analysis.  _IEEE Transactions on Software Engineering_ 40, 2 (2014), 107–122.  https://doi.org/10.1109/TSE.2014.2302311
  * Sung et al. (2020) Chungha Sung, Shuvendu K Lahiri, Mike Kaufman, Pallavi Choudhury, and Chao Wang. 2020.  Towards understanding and fixing upstream merge induced conflicts in divergent forks: An industrial case study. In _Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering: Software Engineering in Practice_. 172–181.  https://doi.org/10.1145/3377813.3381362
  * Towqir et al. (2022) Sheikh Shadab Towqir, Bowen Shen, Muhammad Ali Gulzar, and Na Meng. 2022.  Detecting Build Conflicts in Software Merge for Java Programs via Static Analysis. In _37th IEEE/ACM International Conference on Automated Software Engineering_. 1–13.  https://doi.org/10.1145/3551349.3556950
  * Tsantalis et al. (2022) Nikolaos Tsantalis, Ameya Ketkar, and Danny Dig. 2022.  RefactoringMiner 2.0.  _IEEE Transactions on Software Engineering_ 48, 3 (2022), 930–950.  https://doi.org/10.1109/TSE.2020.3007722
  * Vallée-Rai et al. (2010) Raja Vallée-Rai, Phong Co, Etienne Gagnon, Laurie Hendren, Patrick Lam, and Vijay Sundaresan. 2010\.  Soot: A Java bytecode optimization framework.  In _CASCON First Decade High Impact Papers_. Citeseer, 214–224.  https://doi.org/10.1145/1925805.1925818
  * Yang et al. (1992) Wuu Yang, Susan Horwitz, and Thomas Reps. 1992.  A program integration algorithm that accommodates semantics-preserving transformations.  _ACM Transactions on Software Engineering and Methodology (TOSEM)_ 1, 3 (1992), 310–354.  https://doi.org/10.1145/131736.131756
  * Zhang et al. (2022) Jialu Zhang, Todd Mytkowicz, Mike Kaufman, Ruzica Piskac, and Shuvendu K Lahiri. 2022.  Using pre-trained language models to resolve textual and semantic merge conflicts (experience paper). In _Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis_. 77–88.  https://doi.org/10.1145/3533767.3534396