|  Collapse of a hemicatenoid bounded by a solid wall: instability and
dynamics driven by surface Plateau border friction†
---|---
|  Christophe Raufaste,a Simon Cox,b Raymond E. Goldstein,c and Adriana I.
Pescid
|  The collapse of a catenoidal soap film when the rings supporting it are
moved beyond a critical separation is a classic problem in interface motion in
which there is a balance between surface tension and the inertia of the
surrounding air, with film viscosity playing only a minor role. Recently
[Goldstein, et al., Phys. Rev. E, 2021, 104, 035105], we introduced a variant
of this problem in which the catenoid is bisected by a glass plate located in
a plane of symmetry perpendicular to the rings, producing two identical
hemicatenoids, each with a surface Plateau border (SPB) on the glass plate.
Beyond the critical ring separation, the hemicatenoids collapse in a manner
qualitatively similar to the bulk problem, but their motion is governed by the
frictional forces arising from viscous dissipation in the SPBs. Here we
present numerical studies of a model that includes classical friction laws for
SPB motion on wet surfaces and show consistency with our experimental
measurements of the temporal evolution of this process. This study can help
explain the fragmentation of bubbles inside very confined geometries such as
porous materials or microfluidic devices.

##

††footnotetext: a Université Côte d’Azur, CNRS, Institut de Physique de Nice
(INPHYNI), 06100 Nice, France and Institut Universitaire de France (IUF),
75005 Paris, France. E-mail: Christophe.Raufaste@univ-
cotedazur.fr††footnotetext: b Department of Mathematics, Aberystwyth
University, Aberystwyth, Ceredigion, SY23 3BZ, United Kingdom. E-mail:
<EMAIL_ADDRESS>††footnotetext: c Department of Applied Mathematics and
Theoretical Physics, Centre for Mathematical Sciences, University of
Cambridge, Wilberforce Road, Cambridge CB3 0WA, United Kingdom. E-mail:
<EMAIL_ADDRESS>d Department of Applied
Mathematics and Theoretical Physics, Centre for Mathematical Sciences,
University of Cambridge, Wilberforce Road, Cambridge CB3 0WA, United Kingdom.
E-mail<EMAIL_ADDRESS>† Electronic Supplementary
Information (ESI) available: Videos from experiments and simulations. See DOI:
10.1039/cXsm00000x/

##  1 Introduction

Fig. 1: The full catenoid (left) vs the hemicatenoid (right). Stretching the
supporting rings of each catenoid vertically (black arrows) leads to an
instability in which the neck collapses inward. For the hemicatenoid, that
neck narrowing involves inwardly moving surface Plateau borders.

Free-boundary problems involving the collapse of unstable minimal surfaces
generally fall into two main categories: either the ultimate singularity and
surface reconnection occur in the bulk, far from any supporting boundaries, or
they occur at the boundary itself. A bulk singularity is found in the
classical problem of a collapsing catenoid supported by two rings, which was
first studied by Plateau 1 and Maxwell 2 in the XIXth century, whereas
boundary singularities were only studied recently in the context of collapsing
soap films with more exotic topologies 3, 4, 5. A typical example of a
boundary singularity is found in the collapse of a Möbius strip soap film 3,
first studied by Courant 6.

In all of these problems, the boundaries of the soap film are rigid “frames"
that are fixed in position or subjected to infinitesimal changes to induce the
collapse. In this paper, we study a distinct class of dynamics where part of
the boundary of the film moves as a consequence of the surface evolution. In
this context, the moving boundary problem gives rise to a boundary
singularity. Specifically, we study a problem introduced briefly in earlier
work 7 consisting of a catenoid film supported in the usual way by two
circular rings, but which is split into two hemicatenoids by a glass plate
oriented perpendicularly to the rings, as in Fig. 1. The closed boundary of
each half of the film thus consists of two rigid, stationary semicircular
frames and two curved, movable surface Plateau borders (SPBs) connecting the
intersections of those frames with the glass plate. As such, this is precisely
of the class of problems studied by Courant 8 as a generalization of the work
of Douglas 9, 10 on the existence of minimal surfaces bounded completely by
Jordan curves. It is one of a class of problems involving capillary surfaces
in contact with a wall, subject to various boundary conditions 11, 12, 13. As
shown in cross section in Fig. 2, the lateral balance of forces that occurs in
the surface Plateau borders involves the component of the force ${\bf
f}_{\gamma}$ parallel to the wall due to surface tension $\gamma$ and the
frictional force ${\bf f}_{v}$ due to motion of the film at velocity $v$. In
the case of a minimal surface, we know from Plateau’s laws that the contact
angle $\Psi=\pi/2$ and corresponds to equilibrium, i.e. $v=0$. The dependence
of ${\bf f}_{v}$ on the sliding velocity $v$ is a well-studied problem in foam
rheology 14, 15 and is strongly correlated with the nature of the gas-liquid
interfaces, whose properties lie between the limiting cases of a stress-free
surface and an incompressible surface covered with surfactants 16. Here, in
contrast to the case of foams, it is the three-dimensional shape of the soap
film that drives the surface Plateau border motion and thereby controls the
dynamics.

Fig. 2: Momentum balance in a plane perpendicular to the surface Plateau
border (region inside dashed green square) in contact with the wall.

The experimental setup in Fig. 1 is related to the general problem of a triple
line that becomes unstable. Examples include the collapse of liquid or air
bridges during dewetting 17, 18 and air entrainment in dynamic wetting 21, 19,
20. These situations are characterized by small bubbles and droplets,
respectively, that are left behind on the substrate. The instability of liquid
bridges is also central to the detachment of droplets from moving drops 25,
23, 22, 24 or liquid bridges 26, 27, 28. In each case, the dynamics is
essentially that of a hemicatenoid in contact with a solid wall. For the case
of soap films, the dynamics of a collapsing hemicatenoid is also relevant to
bubble fragmentation inside foams confined in porous media 29, 30 or in
microfluidic devices 31.

We study the collapse of hemicatenoids in the geometry of Fig. 1, and compare
the experimental measurements with a numerical model for the film evolution
that incorporates the friction laws for surface Plateau border motion. The
model exploits the separation of time scales between the fast film motion and
the slow creep of the SPBs. Given this time-scale separation, the film can be
approximated by a minimal surface that spans the support rings and the Plateau
borders, and its local contact angle with the plate determines the SPB speed.
This situation is similar to the retraction of a soap films inside an elastic
ring 32, whose shape and dynamics are linked to surface tension on one side as
well as on the elastic and inertial properties of the ring on the other side.
In that spirit, the properties of the ring are replaced here by the frictional
properties of the surface Plateau border.

In Section 2 of this paper we summarize the experimental methods used both in
the study of hemicatenoid collapse and also in the related problem of SPB
reconnection on surfaces described in the Discussion. The main experimental
results are presented in Sec. 3, while the formulation of the dynamical model
used in numerical studies is given in Sec. 4. Section 5 presents results of
those studies and a comparison with experiments. The concluding Discussion
section 6 connects these results to surface Plateau border reconnection and
other problems in foams.

##  2 Experimental methods

As in previous work 7, soap solutions were obtained by dissolving tetradecyl
trimethyl ammonium bromide (TTAB) into deionized water and adding glycerol in
order to vary the viscosity. The concentration of TTAB was $3$ g/l for the
aqueous solution containing no glycerol and was raised to $6$ g/l for the
solutions containing glycerol to enhance the stability of the soap films. The
viscosity $\eta$ varies from $1.0$ to $77$ mPa$\cdot$s over the range of
glycerol concentrations, while the surface tension is nearly constant at
$35-38$ mPa$\cdot$m 33, 34. Fluorescein was added to aid visualization.

In the experiments on hemicatenoids, a full catenoid is first formed between
two coaxial circular rings of radius $R=4\,$cm, whose distance apart is
adjusted with a micrometric linear stage. A glass plate of width slightly less
than $2R$ and thickness of $1\,$mm was introduced and passes through the
diameters of both rings. In this way we create two independent hemicatenoids
that become unstable once the distance $2d$ between the rings becomes larger
than a critical value.

Fig. 3: Experimental collapse sequence of a hemicatenoid stretched beyond
criticality. Images are taken at times $t-t_{p}=$-51 ms, -16 ms, -6 ms, 0 ms,
10 ms, 35 ms. Diagram indicates tangent angle $\theta$ of the interface at the
upper wire frame. Cyan contours are tracings of the left-hand surface Plateau
border of the hemicatenoid facing the camera.

In separate experiments on SPB reconnection discussed in Sec. 6, we used a
different soap film chemistry to slow down the dynamics 3 for accurate
visualization. We used deformable, transparent tubing with a large diameter
($6.4\,$mm) and a SLES/CAPB/SLES mixture 35 known for its high dissipative
properties 36. We mixed $6.6$% of sodium lauryl ether sulfate (SLES) and
$3.4$% of cocamidopropylbetaine (CAPB) by weight in ultra pure water, and then
dissolved $0.4$% by weight of myristic acid (MAc), by stirring and heating at
$60^{\circ}\,$C for one hour. We then diluted this solution by a factor of
$20$ with water containing fluorescein at a concentration of 0.5 g/L.

The dynamics of the collapsing soap films were recorded using a color high
speed camera (Phantom V641, Ametek) at speeds up to $4,000$ frames per second
while the films were illuminated from multiple directions with arrays of cyan
LEDs. The ESI† includes a video of the collapse of a 3d catenoid and videos of
collapsing hemicatenoids with $\eta=9.6$ and $77\,$mPa$\cdot$s.

##  3 Experimental results

As is well known, a full catenoid spanning two circular frames a distance $2d$
apart becomes unstable when $d/R$ exceeds the critical value $0.663...$ 7.
Using the setup shown schematically in Figure 1, we found experimentally that
essentially the same threshold exists in the case of a hemicatenoid. In
capturing images of this process with a high-speed camera aimed along the
normal to the plate, we naturally see two hemicatenoids, one in front and the
other behind the plate. It is inevitable that they are slightly different due
to imperfections in the setup, and therefore they tend to collapse at slightly
different times. We therefore introduced a deliberate, infinitesimal bias in
the position of the plate in order to assure that the hemicatenoid facing the
camera would collapse last. The consequence of this is seen in Fig. 3, where
the bubbles in the central region of the images are the satellite bubbles left
over after the collapse of the hemicatenoid that was behind the plate. The
cyan tracings in Fig. 3 indicate one of the two surface Plateau borders of the
hemicatenoid facing the camera.

The sequence of shapes of the SPB is strikingly similar to the equivalent
sequence for three-dimensional catenoids obtained by taking longitudinal
cross-sections in the plane of symmetry 7. We note in particular the evolution
toward a shape consisting of two conical films connected by a quasi-
cylindrical region (panel (c)), with a characteristic angle $\theta^{*}\simeq
67.5^{\circ}$ at the pinchoff time $t_{p}$ [panel (d)]. After pinchoff, the
two disjoint films still attached to the frame relax towards the two half
discs spanning the wire loops, while the remnants of the central cylinder
slowly round up to form satellite bubbles, as seen in panel (f).

In quantifying the observed film shapes, we label the SPB location as
$\zeta(z)$, and define 7 the dimensionless radius $r=\zeta/a$, where
$a=0.5524R$ is the critical catenoid waist radius. Similarly, we use the half
disc area to define the dimensionless film area ${\cal A}=A/\pi R^{2}$, with
${\cal A}\simeq 1.199\ldots$ for the critical hemicatenoid and ${\cal A}=1$
for the configuration with two hemidiscs. The area is calculated from the
catenoid contour assuming axisymmetry. This requires that the contact angle on
the glass is close to 90∘, as observed in experiments. While we know that this
is not strictly fulfilled at all space-time points in the experiments, it is a
convenient simplification for the measurements. We have used the same
assumption in the simulations to enable direct comparison of the two; the
error in this approximation increases as the contact angle $\Psi$ decreases
away from $90^{\circ}$ and pinchoff is approached.

Fig. 4: Time evolution of neck radius and contraction speed for three-
dimensional catenoids and hemicatenoids. (a) The neck radius $\zeta_{n}$ as a
function of time relative to pinch time for the various cases as labelled. (b)
Contraction speed versus neck radius.

From the measure SPB locations we determine the time evolution of ${\cal
A}(t)$, the minimum neck radius $\zeta_{n}(t)$, and the neck contraction speed
$d\zeta_{n}/dt$ for hemicatenoids and full catenoids (also with ring radius
$R=4\,$cm). The data for $\zeta_{n}$ shown in Fig. 4a illustrate how the
contraction dynamics of even the least viscous hemicatenoids is slower than
the 3d case, and that the hemicatenoid dynamics progressively slows down with
increasing viscosity. In contrast, the 3d data shows little if any dependence
on viscosity, indicating that the 3d balance of forces is between surface
tension and air inertia.

Figure 4b plots the neck contraction speed as a function of the neck radius.
From this we see that all the data sets display a maximum contraction speed at
a neck radius $\zeta_{n}^{*}\approx 4\,$mm, independent of the film viscosity.
This is clearly associated with the incipient formation of a central satellite
droplet. The lack of variation with $\eta$, and the presence of the central
plate, indicates that it is a geometric effect in the sense that
$\zeta_{n}^{*}$ should scale with the loop radius $R$. This hypothesis is
borne out by comparison with numerical studies of inviscid capillary breakup
37, where the maximum contraction speed is reached for $\zeta_{n}/R\approx
0.1$. While the radius of maximum contraction speed is common to both 3d
catenoids and hemicatenoids, the neck radius at which the speed vanishes for
hemicatenoids is approximately one half of that for the 3d case. This
difference arises from the very different local geometries of the collapsing
necks in the two cases. Whereas the 3d catenoid maintains axisymmetry during
collapse, the hemicatenoids do not, as discussed in Section 4 below.

We can understand the crossover between inertial and viscous effects in film
collapse by means of a scaling argument for characteristic film speeds $U$.
Under inertial dynamics, we expect the Keller-Miksis 38 scaling $U\sim(\gamma
R/\rho_{a})^{1/2}$ to hold, where $\rho_{a}$ is the density of air, while in
the viscous limit the speed $U\sim\gamma/\eta$ is associated with the
capillary number of order unity 16. The ratio of these velocities defines the
Ohnesorge number of this problem $\textrm{Oh}=\eta/\sqrt{\gamma\rho_{a}R}$,
where large (small) values correspond to frictional (inertial) dynamics,
respectively. The critical viscosity $\eta_{c}$ for a balance between the two
effects is at $\textrm{Oh}=1$, namely $\eta_{c}\simeq 40\,$mPa$\cdot$s, which
is consistent with the observations in Fig. 4.

##  4 Model and simulations

A moving meniscus in contact with a wall (an SPB) experiences a frictional
force per unit length whose form depends on the spatial distribution of
dissipation, which itself depends on the stress and physical chemistry at the
liquid-air interface. This dissipation can be written as the sum of two terms
16, both of which depend on the capillary number $Ca=\eta v/\gamma\,$. The
first term represents the contribution from dissipation inside the wetting
film, and scales as $Ca^{1/3}$, while the second is the contribution from
dissipation inside the SPB, and scales as $Ca^{2/3}$. The latter contribution
is associated with mobile surfactants and stress-free interfaces. Otherwise,
both contributions are present and over a large range of $Ca$, this combined
frictional law can be approximated as $f_{v}\sim Ca^{n}$ with $n$ in the range
$1/2-2/3$. This empirical law holds for other systems in which the frictional
force is the dominant one in the balance with the capillary driving force,
such as liquid and air bridges.

The model we study here rests on this assumption, namely that the capillary
forces are balanced by the viscous friction at the contact between the soap
film and the glass plate. That contact consists of an SPB 39 that connects the
wetting film on the plate to the soap film. A slice through a plane
perpendicular to this SPB (Fig. 2) shows that the driving force density is
$f_{\gamma}\cos\Psi$, with $f_{\gamma}=2\gamma$. Balancing against the
frictional force $f_{v}=A\gamma\,Ca^{n}$, with $A$ a dimensionless constant,
we obtain

$v=v_{0}\left(\cos\Psi\right)^{1/n},$ (1)

where $v_{0}=(\gamma/\eta)\left(2/A\right)^{1/n}$ is a characteristic speed.

To apply this law to the evolution of hemicatenoids toward collapse, we
exploit the separation of time scales between the motion of the bulk surface,
resisted only by the inertia of the surrounding air, and that of the contact
lines, and view the surface spanning the moving contact lines and the two
half-rings as in quasi-equilibrium. It is therefore a minimal surface at any
instant of time, but does not necessarily meet the glass plate with
$\Psi=\pi/2$, as would be the case in static equilibrium in accordance with
Plateau’s laws. Instead, the contact line acts like a constraining wire, and
the surface meets it at the angle that yields a minimal surface. Figure 5
shows an experimental realization of this concept, where 3D printed frames,
consisting of two half-circular loops connected by contours obtained from the
numerical studies below, support minimal surfaces with contact angle
$\Psi<\pi/2$.

Fig. 5: Soap films spanning a 3D printed frame consisting of two semicircles
connected by a contour found in numerical studies of film evolution. Note in
panel (c) how the minimal surface meets the narrowest part of the neck with a
small angle $\Psi$. Fig. 6: Image sequence in simulation ($n=2/3$, stretching
factor 5%), corresponding to the times at which the images in Figure 3 were
recorded.

The dynamics of evolving hemicatenoids obeying the laws specified above were
obtained using Surface Evolver 40. We nondimensionalize lengths with the loop
radius $R$ and scale speeds with $v_{0}$, leaving $R/v_{0}$ as a
characteristic time scale in the motion. Therefore, changing $R$ in the
initial conditions or $v_{0}$ in (1) corresponds to a dilation in time and all
simulations can be rescaled with respect to time. Hence, for a given power-law
exponent $n$, there is only a single simulation needed for each initial
stretching factor. The updating algorithm involves advecting each part of the
SPB in the plane along its projected normal by a distance $d\ell=v\,dt$, with
$v$ determined by the local angle $\Psi$. The updated shape of the catenoid is
obtained by finding a minimal surface with the new position of the contact
lines, which then yields the updated $\Psi$ along the SPBs, and the velocity
for the next time step.

By symmetry, we need only simulate one quarter of the hemicatenoid. We fix the
plate thickness at $0.008R$ and first create a stable catenoid with $d=0.65R$,
close to the critical value for three-dimensional catenoids, and a
triangulation in which triangle edge lengths lie in the range $0.004-0.06$. To
begin the evolution, we stretch the catenoid by a few percent and fix all
points along the SPB. Motion then proceeds in time steps of $dt=1\times
10^{-3}$ using the algorithm outlined above, where the relaxation to a minimal
surface is done to $7$ significant figures. The initial stretching is needed
to match the initial area in experiments and in simulation. It corresponds to
5 and 7.2% for the simulations of $\eta=9.6$ and 77 mPa.s respectively.

In the numerics, several quantities are calculated as functions of time: the
dimensionless area $\mathcal{A}$, the dimensionless neck radius $r_{n}$ as
defined in Sec. 3, and the tangent angle $\theta$ at the junction of the
contact line and the supporting half-ring. As in the presentation of the
experimental results, we define the zero of time as the moment when the
apparent neck radius vanishes and the topological transition occurs. In
simulations, a cutoff radius of $0.02R$ is introduced to trigger the
transition. This choice is not critical in the analysis since the radius goes
to zero in a finite time and the transition is well defined, as seen in Fig.
7.

Fig. 7:  Numerical results for cross-sectional profiles in the plane $z=0$ for
$t<0$, color-coded from blue (early) to red (late). The initially circular
profile becomes extremely flattened, coincident with the contact line speed
reaching its maximum.

##  5 Comparison of Experimental and Numerical Results

Fig. 8: Rescaled area, neck radius and neck contraction rate as functions of
time. Simulations were performed with force-law exponent $n=1$ (black), $2/3$
(blue) and $1/2$ (red). Time has been scaled to match the maximum neck rate.

We now describe the key results obtained with the numerical implementation of
the model described in Section 4. The full temporal evolution of a collapsing
hemicatenoid is shown in Fig. 6 (and in a video in the ESI†), while Fig. 7
shows the cross-sectional shapes of the narrowest part of the neck. We observe
that the initial cross-section is nearly circular, with the angle
$\Psi\approx\pi/2$, as expected for a minimal surface. However, as the
collapse sequence progresses, the neck becomes ever flatter and $\Psi$ tends
to zero. Within the assumptions of the model (1), this implies that the neck
contraction speed $d\zeta_{n}/dt$ tends to the extremal value $-v_{0}$ before
pinchoff. As in collapsing three-dimensional catenoids 7, we observe that the
film shape connecting the pinchoff region to the supporting wire loops is
close to a (half) cone.

The experimental data shown in Fig. 4 for the neck radius and neck contraction
speed, as well as the experimental film area are plotted in Fig. 8 along with
the numerical results obtained for three different values of the exponent $n$
of the friction law (1). Simulations are rescaled with respect to experiments
using the curves of the neck contraction speed as a function of time. The
value of $v_{0}$ in simulations is set, for each viscosity $\eta$, by the
maximum contraction speed observed in experiments. This sets the time axis up
to an additive constant. There is a noticeable difference between experiments
and simulations close to pinchoff. In simulations, the neck contraction speed
remains constant in the last instants before pinchoff at its extremal value
$-v_{0}$. In experiments, the neck contraction speed reaches a maximum, used
to infer $v_{0}$, and decreases thereafter to zero. As mentioned previously,
this is associated with the complex dynamics close to pinchoff due to the air
trapped in the neck, as observed in 3D catenoids. As a consequence, we define
$t_{p}^{*}$ as the hypothetical pinchoff time assuming that the neck
contraction speed maintains its extremal value (note that $t_{p}^{*}=t_{p}$ in
simulations) and plot all the data as a function of $t-t_{p}^{*}$ in Fig. 8.
This allows a quantitative comparison between experiments and simulations. For
the two viscosities studied in Fig. 8, we see a clear tendency to favour the
exponent $2/3$ over $1/2$ and $1$. This nonlinear friction law thus seems
consistent not only with the presence of mobile surfactants and stress-free
interfaces, but also implies that dissipation occurs within the SPBs.

Experiments  $\eta$ (mPa.s) 1.0 4.3 9.6 77 $\theta^{*}$ (deg) $68.0\pm 1.0$
$68.0\pm 1.0$ $67.5\pm 1.0$ $66.6\pm 1.0$ Simulations

$n$ | 1/2 | 2/3 | 1
---|---|---|---
$\theta^{*}(deg)$ | $65.8\pm 0.6$ | $68.2\pm 0.7$ | $72.1\pm 1.1$

Table 1:  Apex angle of the Martini-glass configuration in simulation and
experiment.  Fig. 9: Surface Plateau border motion during a topological
transition. Image sequence of the final stages of SPB reconnection as a soap
film Möbius strip transitions to a disc. Foreground and background segments of
the SPB are displayed by solid magenta and dashed cyan curves respectively.
Frames (a)-(c) are at times $-31\,$ms, $-12.5\,$ms, and $-5\,$ms relative to
the reconnection event in (d).

The value of the prefactor $A$ in the frictional force law (1) can be inferred
from the experimental measurements of $v_{0}$, using the exponent $n=2/3$ that
is most consistent with the data. For the data of Fig. 8, we find for
$\eta=9.6$ and $77$ mPa$\cdot$s that $v_{0}=0.52$ and $0.26\,$m$\cdot$s-1,
respectively. These yield $A\approx 7.3$ and $2.9$, respectively, in agreement
with the prediction $A\sim 5-7$ from lubrication theory in a simpler geometry
16. For the two other viscosities ($\eta=1.0$ and $4.3\,$mPa$\cdot$s), the
dynamics can not be described with the same approach since both viscous and
inertial effects are present.

In previous work 7, we have referred to the conical film shape as the “Martini
glass" configuration, and detailed a method to determine its appearance based
on the shape of the film near the supporting ring. The method involves
finding, within the time sequence, that contour whose shape displays the
minimum standard deviation in a fit to a straight line. The critical vertex
angle is then $\theta^{*}=\pi/2-\arctan(m)$, where $m$ is the associated slope
of the line. For the case of 3D catenoids, whose dynamics are driven by
inertia, we found $\theta^{*}=68^{\circ}$. For hemicatenoids bounded by a
solid wall, our measurements are reported in Table 1. In experiment, this
configuration is observed when the neck pinches. The stated uncertainties are
estimated either over repeated experiments or by assuming a 10% allowance on
the standard deviation to find its minimum value. Both estimates give typical
values around $1^{\circ}$. In the simulations, this configuration occurs
slightly after the pinchoff time and for larger $n$ this configuration occurs
later, and yields a larger $\theta^{*}$. 333For $n=1$ the local minimum is
less pronounced. We have tested a simulation with $n=4/3$ (data not shown). In
this case, the local minimum does not exist as emphasized by the absence of a
curvature inversion in the corresponding movie/image sequence (data not
shown). In the simulations, the error bars are determined with the same 10%
criterion.

We find that $\theta^{*}$ is almost constant in experiments and very close to
what was observed experimentally with 3D catenoids 7, and which was found to
be a consequence of the fact that the first few active modes dominate the
dynamics near the rigid frames. A slight decrease could be observed as the
viscosity increases, but it is difficult to give strong statements given the
error bars. We can notice that the value of $\theta^{*}$ obtained with
$\eta=9.6$ mPa.s is consistent with a 2/3 exponent. For $\eta=77$ mPa.s, the
value lies between what is obtained with exponents $1/2$ and $2/3$ in
simulation, but this method to discuss the exponent is not as robust as the
comparison through the whole time sequence as presented in Figure 8 and is
more sensitive to the exact and complex dynamics around the pinchoff time.

##  6 Discussion

In this work, we have studied the dynamics of surface Plateau borders that are
driven by unstable soap films. Unlike in the case of collapsing three-
dimensional catenoidal films, the motion of hemicatenoids bounded by solid
walls is dominated by dissipation localized in the moving SPBs. Whereas the
film viscosity plays essentially no observable role in the collapse of 3d
catenoids, we observe a strong dependence on viscosity of the collapse
dynamics of hemicatenoids. Through comparisons between experimental
observations and numerical simulations of a model that incorporates the widely
used nonlinear friction law $f\sim Ca^{n}$ for the viscous force $f$ as a
function of capillary number $Ca$, we found consistency with the exponent
$n=2/3$ associated with mobile surfactants and stress-free interfaces. Despite
this effect on the dynamics, the large-scale shapes of the collapsing films
are insensitive to the film viscosity, a fact that highlights the crucial role
played by intrinsic geometric features.

Surface Plateau border motion is also present in certain exotic topological
transitions involving soap films. For example, in previous work3, 4, 5 we
studied the interconversion of a soap-film Möbius strip to a two-sided
surface, and showed that the singularity associated with that topological
transition occurs at the boundary of the film and involves reconnection of the
SPB. Figure 9 shows a close-up of the region of the incipient singularity, in
which we see that the film evolves in such a way as to make the SPB twist ever
more tightly around the tube, until two sections of the film touch each other
and reconnect. While this is similar to the neck of a half catenoid, which
collapses with the formation of a satellite droplet, the detailed dynamics of
the twist-driven reconnection event and associated change in the orientation
of the SPB in Fig. 9 remain to be understood.

The dynamics that we describe here, driven by the shape of the interface and
the motion of the associated SPB, is found more widely during the motion of
surfactant-laden interfaces. In flow through porous media, for example during
foam enhanced oil recovery 39, lamellae are forced under a pressure gradient
through narrow pore throats between solid surfaces. The collision of two SPBs
leads to processes such as pinch-off 31, in which two interfaces separate in
the way that the hemicatenoid does, snap-off and lamella-division 30. These
process lead to variations in bubble size, which then requires an adjustment
to the pressure gradient required to mobilize the foam. SPB friction therefore
controls the rate at which foam is generated in porous media.

## Author Contributions

All authors designed and performed the research, analyzed the results and
wrote the paper.

## Conflicts of interest

There are no conflicts to declare.

## Acknowledgements

We are grateful to K. Brakke for provision and support of the Surface Evolver
software and to Médéric Argentina and Keith Moffatt for enlightening
discussions. This work was supported in part by the National Research Agency
(ANR-20-CE30-0019) and by the French government, through the UCAJEDI
Investments in the Future project of the National Research Agency
(ANR-15-IDEX-01) (CR), with additional support from the Engineering and
Physical Sciences Research Council (EP/N002326/1 to SC; Established Career
Fellowship EP/M017982/1 to REG & AIP), from the Schlumberger Chair Fund (REG),
and the European Space Agency (4000129502) (SC).

## Notes and references

  * 1 J. Plateau, Statique expérimentale et théorique des liquides soumis aux seules forces moléculaires [Experimental and theoretical statics of liquids subject to only molecular forces] (in French). (Gauthier-Villars, Paris, France, 1873).
  * 2 J.C. Maxwell, The Scientific Papers of James Clerk Maxwell, ed. W.D. Niven, Vol. 2, (Cambridge University Press, Cambridge, 1890).
  * 3 R.E. Goldstein, H.K. Moffatt, A.I. Pesci, and R.L. Ricca, Soap-film Möbius strip changes topology with a twist singularity, Proc. Natl. Acad. Sci. USA 107, 21979 (2010).
  * 4 R.E. Goldstein, J. McTavish, H.K. Moffatt and A.I. Pesci, Boundary singularities produced by the motion of soap films, Proc. Natl. Acad. Sci. USA 111, 8339 (2014).
  * 5 A.I. Pesci, R.E. Goldstein, G.P. Alexander and H.K. Moffatt, Instability of a Möbius strip minimal surface and a link with systolic geometry, Phys. Rev. Lett. 114, 127801 (2015).
  * 6 R. Courant, Soap film experiments with minimal surfaces, Am. Math. Mon. 47, 167 (1940).
  * 7 R.E. Goldstein, A.I. Pesci, C. Raufaste, and J.D. Shemilt, Geometry of catenoidal soap film collapse induced by boundary deformation, Phys. Rev. E 104, 035105 (2021).
  * 8 R. Courant, The existence of a minimal surface of least area bounded by prescribed Jordan arcs and prescribed surfaces, Proc. Natl. Acad. Sci. (USA) 24, 97-101 (1938).
  * 9 J. Douglas, Some new results in the problem of Plateau, J. Math. Phys. 15, 55-64 (1936).
  * 10 J. Douglas, Minimal surfaces of general topological structure with any finite number of assigned boundaries, J. Math. Phys. 15, 105-123 (1936).
  * 11 J.B. Bostwick and P.H. Steen, Stability of constrained capillary surfaces, Annu. Rev. Fluid Mech. 47, 539 (2015).
  * 12 A. Akbari and R.J. Hill, Liquid-bridge stability and breakup on surfaces with contact-angle hysteresis, Soft Matter 12, 6868 (2016).
  * 13 A. Akbari, R.J. Hill, and T.G.M. van de Ven, Catenoid stability with a free contact line, SIAM J. Appl. Math. 75, 2110 (2015).
  * 14 N.D. Denkov, V. Subramanian, D. Gurovich, and A. Lips, Wall slip and viscous dissipation in sheared foams: effect of surface mobility, Colloids Surf. A 263, 129–145 (2005).
  * 15 N.D. Denkov, S. Tcholakova, K. Golemanov, V. Subramanian, and A. Lips, Foam-wall friction: effect of air volume fraction for tangentially immobile bubble surface, Colloids Surf. A 282, 329–347 (2006).
  * 16 I. Cantat, Liquid meniscus friction on a wet plate: Bubbles, lamellae, and foams, Phys. Fluids 25, 031303 (2013).
  * 17 G. Reiter, Dewetting of thin polymer films, Phys. Rev. Lett. 68, 75-–78 (1992).
  * 18 G. Reiter, Unstable thin polymer films: rupture and dewetting processes, Langmuir 9, 1344–1351 (1993).
  * 19 T. D. Blake, and K. J. Ruschak, A maximum speed of wetting, Nature 282, 489–491 (1979).
  * 20 H. Benkreira, and M. I. Khan, Air entrainment in dip coating under reduced air pressures, Chem. Eng. Sci. 63, 448–459(2008).
  * 21 R. Burley, and B. S. Kennedy, An experimental study of air entrainment at a solid/liquid/gas interface, Chem. Eng. Sci. 31, 901–-911 (1976).
  * 22 S. Engelnkemper, M. Wilczek, S. V. Gurevich, and U. Thiele, Morphological transitions of sliding drops: Dynamics and bifurcations, Phys. Rev. Fluids 1, 073901 (2016).
  * 23 N. Le Grand, A. Daerr, and L. Limat, Shape and motion of drops sliding down an inclined plane, J. Fluid Mechanics 541, 293—-315 (2005).
  * 24 W. Liang, and S. Tietze, Pearls in running drops on an inclined glass substrate excited by Lamb waves, Sci. Rep. 7, 14164 (2017).
  * 25 T. Podgorski, J.-M. Flesselles, and L. Limat, Corners, Cusps, and Pearls in Running Drops, Phys. Rev. Lett. 87, 036102 (2001).
  * 26 P. Beltrame, E. Knobloch, P. Hänggi, and U. Thiele, Rayleigh and depinning instabilities of forced liquid ridges on heterogeneous substrates, Phys. Rev. E 83, 016305 (2011).
  * 27 J. A. Diez, A. G. González, and L. Kondic, Instability of a transverse liquid rivulet on an inclined plane, Phys. Fluids 24, 032104 (2012).
  * 28 R. K. Singh, J. E. Galvin, G. A. Whyatt, and X. Sun, Breakup of a liquid rivulet falling over an inclined plate: Identification of a critical Weber number, Phys. Fluids 29, 052101 (2017).
  * 29 B. Géraud, S. A. Jones, I. Cantat, B. Dollet, and Y. Méheust, The Flow of a Foam in a Two-Dimensional Porous Medium, Water Res. Research 52, 773 (2016).
  * 30 B. Géraud, Y. Méheust, I. Cantat, and B. Dollet, Lamella Division in a Foam Flowing through a Two-Dimensional Porous Medium: A Model Fragmentation Process, Phys. Rev. Lett. 118, 098003 (2017).
  * 31 R. Liontas, K. Ma, G. J. Hirasaki, and S. L. Biswal, Neighbor-Induced Bubble Pinch-off: Novel Mechanisms of in Situ Foam Generation in Microfluidic Channels, Soft Matter 9, 10971 (2013).
  * 32 F. Box, O. Kodio, D. O’Kiely, V. Cantelli, A. Goriely, and D. Vella, Dynamic Buckling of an Elastic Ring in a Soap Film, Phys. Rev. Lett. 124, 198003 (2020).
  * 33 A. Cohen, N. Fraysse, J. Rajchenbach, M. Argentina, Y. Bouret, and C. Raufaste, Inertial mass transport and capillary hydraulic jump in a liquid foam microchannel, Phys. Rev. Lett. 112, 218303 (2014).
  * 34 A. Cohen, N. Fraysse, and C. Raufaste, Drop coalescence and liquid flow in a single Plateau border, Phys. Rev. E 91, 053008 (2015).
  * 35 K. Golemanov, N. D. Denkov, S. Tcholakova, M. Vethamuthu, and A. Lips, Surfactant Mixtures for Control of Bubble Surface Mobility in Foam Studies, Langmuir 24, 9956–9961 (2008).
  * 36 N. D. Denkov, S. Tcholakova, K. Golemanov , K. P. Ananthpadmanabhan and A. Lips, The role of surfactant type and bubble surface mobility in foam rheology, Soft Matter 5, 3389–3408 (2009).
  * 37 Y.-J. Chen, and P. H. Steen, Dynamics of inviscid capillary breakup: collapse and pinchoff of a film bridge, J. Fluid Mech. 341, 245 (1997).
  * 38 J.B. Keller and M.J. Miksis, Surface tension driven flows, SIAM J. Appl. Math. 43, 268 (1983).
  * 39 I. Cantat, S. Cohen-Addad, F. Elias, F. Graner, R. Höhler, O. Pitois, F. Rouyer, and A. Saint-Jalmes. Foams: Structure and Dynamics (Oxford University Press, Oxford, 2013).
  * 40 K. Brakke,  The Surface Evolver.  _Exp. Math._ , 1 141–165, 1992. Available at http://www.susqu.edu/brakke/


# Evaluating data-flow coverage in
spectrum-based fault localization

Henrique L. Ribeiro, Roberto P. A. de Araujo, Marcos L. Chaim  Software
Analysis and Experimentation Group — SAEG
School of Arts, Sciences and Humanities
University of São Paulo
<EMAIL_ADDRESS>Higor A. de Souza, Fabio Kon
Department of Computer Science
Institute of Mathematics and Statistics
University of São Paulo
<EMAIL_ADDRESS>
###### Abstract

Background: Debugging is a key task during the software development cycle.
Spectrum-based Fault Localization (SFL) is a promising technique to improve
and automate debugging. SFL techniques use control-flow spectra to pinpoint
the most suspicious program elements. However, data-flow spectra provide more
detailed information about the program execution, which may be useful for
fault localization. Aims: We evaluate the effectiveness and efficiency of ten
SFL ranking metrics using data-flow spectra. Method: We compare the
performance of data- and control-flow spectra for SFL using 163 faults from 5
real-world open source programs, which contain from 468 to 4130 test cases.
The data- and control-flow spectra types used in our evaluation are
definition-use associations (DUAs) and lines, respectively. Results: Using
data-flow spectra, up to 50% more faults are ranked in the top-15 positions
compared to control-flow spectra. Also, most SFL ranking metrics present
better effectiveness using data-flow to inspect up to the top-40 positions.
The execution cost of data-flow spectra is higher than control-flow, taking
from 22 seconds to less than 9 minutes. Data-flow has an average overhead of
353% for all programs, while the average overhead for control-flow is of 102%.
Conclusions: The results suggest that SFL techniques can benefit from using
data-flow spectra to classify faults in better positions, which may lead
developers to inspect less code to find bugs. The execution cost to gather
data-flow is higher compared to control-flow, but it is not prohibitive.
Moreover, data-flow spectra also provide information about suspicious
variables for fault localization, which may improve the developers’
performance using SFL.

###### Index Terms:

Fault localization; Spectrum-based; Debugging; Structural testing; Data-flow;
Control-flow.

##  I Introduction

Testing and debugging are among the most expensive tasks during the
development cycle [1]. Debugging consists of locating and fixing program bugs
(faults). These activities are accomplished with the help of static (e.g.,
source code, bug reports) and dynamic information (e.g., variable values, test
results). Nevertheless, a developer may spend too much time trying to
understand and locate a bug, affecting considerably the overall cost of the
software. This is so because fault localization is in general a tedious, time-
consuming, and error-prone manual task [2, 3]. Several fault localization
techniques have been proposed to improve the developer’s productivity during
the debugging process [4].

Spectrum-based fault localization (SFL) is a promising debugging technique due
to its relative low overhead in test execution time. SFL techniques use data
collected during a test suite execution, called program spectra, to infer
which source code elements are more likely to contain a bug [5, 6, 2]. Program
spectra111Henceforth, we use indistinctly the terms spectra and coverage.
comprise program elements, from fine-grained to coarse ones, that are tracked
during a test case execution. They include statements, blocks, predicates,
definition-use associations (DUAs), and function or method calls that are
associated with each test case. SFL is based on strategies to pinpoint faulty
program elements. Most of them make use of metrics [7, 8, 5, 9, 10] to rank
suspicious elements. The rationale is that program elements frequently
executed in failing test cases are more likely to be faulty. Thus, the
frequency with which elements are executed in passing and failing test cases
is used to calculate a suspiciousness score for each element. Subsequently,
these suspicious elements are mapped onto lines of code likely to be faulty.

Thus, SFL is built upon two foundations: spectra and ranking metrics. Many
studies have been conducted to determine which is the best metric to support
SFL [11, 12]. Ochiai [7] has been suggested as the most effective metric for
fault localization [12]. However, a very recent study shows that the best
metrics are indistinctive for real faults, meaning that there is hardly any
difference in which metric one chooses since the results will be very similar
[11].

It remains then to tackle the role of the spectra in SFL. Few studies compared
the use of different spectra in fault localization. Santelices et al. [6]
suggest that DUA spectrum performs better than statements and branches to
locate bugs. Masri shows that DIFA (Dynamic Information Flow Analysis)
spectrum, along with DUA and branch, performed better than statement spectrum
[13]. DIFA consists of interactions occurred in an execution, and comprises
data and control dependencies from statements and variables. Both DUAs and
DIFAs are data-flow spectra.

These studies, though, used only small- to medium-sized programs and
artificial faults in their assessments. In Santelices et al. [6], most of the
programs belongs to the Siemens Suite [14], which is composed of programs with
few hundred lines of code (LOC); in Masri [13], two programs with less than 10
KLOC were used in the evaluation. Both studies only utilize artificial faults.
Pearson et al. [11], however, show that many claims verified with artificial
faults do not hold for real bugs.

There is a reason why most SFL studies [15, 16, 7, 17] use only control-flow
spectra, namely, statement, predicate, and branch coverage: cost. To obtain
the spectra for fault localization, the original source or object code needs
to be modified (instrumented) to track the elements executed by each test
case. Moreover, test case results (i.e., fail or success) should also be
recorded. The cost to obtain data-flow spectra is higher because definition-
use associations (DUAs), for example, comprise all value assignments (variable
definition) and their subsequent references (variable uses) in a program [14,
6]. As a result, there are much more DUAs to track at run-time than
statements, which implies both execution and memory overheads during test case
execution. Previous studies show that statements and branches can be monitored
with a run-time overhead of 9% to 18% while DUAs have a run-time overhead of
66%-127% [18, 19]. Recent results, though, show that DUA spectra can be
obtained with fairly moderate execution and memory overheads [20, 21]. They
allow the use of data-flow spectra in fault localization for large and long
running programs.

This paper assesses the use of data-flow spectra in fault localization.
Because programs have more DUAs than statements or branches, the likelihood of
correlating critical DUAs with failing test runs should be higher. Thus, our
hypothesis is that data-flow spectra is more effective than control-flow
spectra for fault localization. Moreover, we investigate whether the possible
increase on the effectiveness is worth the data-flow extra cost for large
programs. We compared data- and control-flow spectra using definition-use
associations (DUAs) and statement (line222The term line in this work refers to
an executable line or statement.), respectively. DUAs and lines are two of the
least expensive program elements that represent both spectra.

We used the Jaguar SFL tool (_JAva coveraGe faUlt locAlization
Ranking_)333github.com/saeg/jaguar [22] to compare data- and control-flow
spectra in fault localization. Jaguar provides ranking lists for several
ranking metrics. It uses JaCoCo444eclemma.org/jacoco and BA-
DUA555github.com/saeg/ba-dua to collect line and DUA spectra, respectively.
JaCoCo has been utilized to assess control coverage of large systems. Moir
reports that JaCoCo was run against 37,000 Eclipse JDT core tests with an
execution overhead of 2% [23]. BA-DUA, in turn, was able to collect DUA
spectra with run-time overhead of 38% on average for large programs [21].

Differently from previous work, we assess both techniques using 163 real
faults from five real open-source programs. The program sizes vary from 10 to
96 KLOC, which contains from 468 to 4130 test cases. Additionally, we compare
data- and control-flow spectra using ten SFL ranking metrics. The goal is to
assess which spectrum is more effective; i.e., the one that locates more bugs
by inspecting fewer lines of code. Furthermore, we compare the efficiency
(i.e., run-time overhead) of SFL based on data- and control-flow spectra. The
following research questions summarize the issues addressed in this paper:

  1. 1.

Which spectrum is more effective to locate bugs: data- or control-flow?

  2. 2.

Which spectrum is more efficient to locate bugs: data- or control-flow?

Our results indicate that data-flow spectrum ranks more faults in upper
positions compared to control-flow spectrum with statistical significance for
all ten ranking metrics. DUA outperforms line spectrum, classifying more
faults in the range of 7 to 40 most suspicious lines in the SFL ranking lists.
By investigating from the top 9 to the top 25 most suspicious lines, a
practitioner can reach from one quarter to half of all faults using DUA
spectrum and Ochiai. To achieve the same result with line spectrum, one needs
to inspect 14 more lines. After the 70th position, control-flow surpass data-
flow for most ranking metrics. Since each DUA contains from 2 to 3 lines, its
performance worsens for faults that are far from the top positions.

Data-flow cost is high, but it is not prohibitive. It took from 22 seconds to
8:35 minutes to obtain the suspicious lines. However, control-flow spectrum
can also be expensive, up to 4:25 minutes. The average time for all programs
using data-flow and control-flow are 2:58 and 1:18 minutes, respectively.
Data-flow has an average overhead of 353% for all programs, while the average
overhead for control-flow is of 102%.

The results suggest that data-flow spectrum can leverage SFL; however,
practitioners should be educated to inspect more code—from 10 to 25 suspicious
lines—to take advantage of SFL.

The remainder of the paper is organized as follows. Section II presents
concepts and definitions of control- and data-flow spectra, and Spectrum-based
Fault Localization (SFL). Sections III, IV, V, and VI describe, respectively,
the experiment design, the results, the discussion, and the threats to the
validity of our experimental assessment. The related work is discussed in
Section VII. We draw our conclusions and present future work in Section VIII.

##  II Background

In what follows, we present an example to illustrate the concepts of control-
and data-flow spectra, and spectrum-based fault localization.

###  II-A Running example

Figure 1 shows the code of a simple function, named max [20]. The first three
columns represent line, statement, and block numbers, respectively. The
function receives two parameters: the first is an int array and the second is
the array size. It should return the largest number of an array, but there is
a fault at line 4: array[++i] should be array[i++]; that is, the increment
(++) must come _after_ the variable i. This causes variable max to be assigned
to the second position of the array.

Line | Statement | Block | Code
---|---|---|---
1 | - | - | int max(int[] array, int length)
2 | - | 1 | {
3 | 1 | 1 | int i = 0;
4 | 2 | 1 |  int max = array[++i]; //array[i++];
5 | 3 | 2 |  while(i $<$ length)
6 | - | 3 | {
7 | 4 | 3 |  if(array[i] $>$ max)
8 | 5 | 4 |  max = array[i];
9 | 6 | 5 |  i++;
10 | - | 5 | }
11 | 7 | 6 | return max;
12 | - | 6 | }
Figure 1: Code of max program

###  II-B Control-flow spectra

Fault localization techniques use different types of control-flow spectra:
statements are executable lines of code; basic blocks (or simply blocks) are
sets of statements that are always executed together; branches are statements
that transfer the control-flow execution among blocks.

Control-flow information of a program is represented by a _graph_ with _nodes_
and _edges_ , in which a _node_ represents a _basic block_ and an _edge_
represents a _branch_. Figure 2 shows the control-flow graph of the _max_
program.

Table I describes, in the _all-nodes_ and _all-edges_ columns, the control-
flow spectra that can be tracked during the execution of _max_ ’s test suite.
The nodes and edges are also known as the testing requirements of structural
testing criteria all-nodes and all-edges [24]. A node (edge) is considered as
covered if there is a test case that traverses a path that includes such a
node (edge). All-nodes and all-edges criteria require that every node and
every edge of a program, respectively, must be covered by at least one test
case to be satisfied.

###  II-C Data-flow spectra

Data-flow spectrum concerns paths in a program between every point in which a
value is assigned to a variable and its subsequent references. When a variable
receives a new value, it is said that a definition has occurred; a use of a
variable happens when its value is referred to. A distinction is made between
a variable referred to compute a value and to compute a predicate. When
referred to in a predicate computation, it is called a p-use and is associated
with edges; otherwise, it is called a c-use when associated with nodes. A
definition-clear path with respect to (wrt) a variable $X$ is a path where $X$
is not redefined in any node in the path, except possibly in the first and
last ones. Figure 2 contains _max_ ’s control-flow graph annotated with data-
flow information.

123456 def={i,array,length,max} c-use={i,array} p-use={i,length}
p-use={i,length} p-use={i,array,max} def={max} c-use={i,array} c-use={max}
p-use={i,array,max} def={i} c-use={i}

Figure 2: Control-flow graph of _max_ program

Data-flow spectra can be formally defined using the concept of definition-use
associations (DUAs) [24]. The triple $D$ = ($d$, $u$, $X$), called c-use DUA,
represents a data-flow testing requirement involving a definition in node $d$
and a c-use in node $u$ of variable $X$ such that there is a definition-clear
path wrt $X$ from $d$ to $u$. Likewise, the triple $D$ = ($d$, ($u^{\prime}$,
$u$), $X$), called p-use DUA, represents the association between a definition
and a p-use of a variable $X$. In this case, a definition-clear path
($d$,$\ldots$,$u^{\prime}$,$u$) wrt $X$ should exist.

The data-flow spectrum is also the testing requirements of the _all-uses_
testing criterion [24]. This criterion requires the set of paths executed by
the test cases of a test set $T$ to include a definition-clear path for each
DUA ($d$, $u$, $X$) or ($d$, ($u^{\prime}$, $u$), $X$) of a program $P$. The
DUAs exercised by a test set are said to be covered by it. Table I contains
the DUAs required for the _max_ program.

TABLE I: Data- and control-flow spectra for the max program All-nodes | All-edges | All-uses
---|---|---
1 | (1,2) | (1, 6, max) | (4, 6, max) | (1, (3,4), max)
2 | (2,3) | (1, (3,5), max) | (4, (3,4), max) | (4, (3,5), max)
3 | (2,6) | (1, 1, i) | (1, 4, i) | (1, 5, i)
4 | (3,4) | (1, (2,3), i) | (1, (2,6), i) | (1, (3,4), i)
5 | (3,5) | (1, (3,5), i) | (5, 4, i) | (5, 5, i)
6 | (4,5) | (5, (2,3), i) | (5, (2,6), i) | (5, (3,4), i)
| (5,2) | (5, (3,5), i) | (1, 1, array) | (1, 4, array)
|  | (1, (3,4), array) | (1, (3,5), array) | (1, (2,3), length)
|  | (1, (2,6), length) |  |

###  II-D Spectrum-based fault localization

Program spectrum or coverage [25, 7] consists of program elements (e.g.,
statements, blocks, predicates, DUAs, methods) covered during a test case
execution [26, 27]. Spectrum-based fault localization techniques use ranking
metrics to assign suspiciousness scores to these elements. The outcome is a
list of elements ranked in descending order of suspiciousness.

Several ranking metrics have been proposed or used to indicate elements most
likely to contain faults [5, 7, 28]. The most effective metrics are
characterized by identifying suspicious code excerpts from the frequency of
elements exercised in passing and failing test cases. The ranking metrics use
four parameters to calculate the suspiciousness of an executed program
element. These parameters represent the four possible states during a test
execution: $c_{ef}$ indicates the number of times a program element ($c$) is
executed ($e$) in failing ($f$) test cases, $c_{nf}$ is the number of times an
element is not ($n$) executed by failing ($f$) test cases, $c_{ep}$ is the
number of times an element is executed ($e$) by a passing ($p$) test case, and
$c_{np}$ represents the number of times an element is not ($n$) executed by
passing ($p$) test cases.

TABLE II: Ranking metrics for fault localization Ranking metric | Formula | Ranking metric | Formula
---|---|---|---
Ochiai[7] |  $\frac{c_{ef}}{\sqrt{(c_{ef}+c_{nf})(c_{ef}+c_{ep})}}$ | Jaccard[7] |  $\frac{c_{ef}}{c_{ef}+c_{nf}+c_{ep}}$
Kulczynski2[8] |  $\frac{1}{2}\left(\frac{c_{ef}}{c_{ef}+c_{nf}}+\frac{c_{ef}}{c_{ef}+c_{ep}}\right)$ | Zoltar[10] |  $\frac{c_{ef}}{c_{ef}+c_{nf}+c_{ep}+10000\cdot\frac{c_{nf}c_{ep}}{c_{ef}}}$
McCon[8] |  $\frac{c_{ef}^{2}-c_{nf}c_{ep}}{(c_{ef}+c_{nf})(c_{ef}+c_{ep})}$ | Minus[29] |  $\frac{\frac{c_{ef}}{c_{ef}+c_{nf}}}{\frac{c_{ef}}{c_{ef}+c_{nf}}+\frac{c_{ep}}{c_{ep}+c_{np}}}-\frac{1-\frac{c_{ef}}{c_{ef}+c_{nf}}}{1-\frac{c_{ef}}{c_{ef}+c_{nf}}+1-\frac{c_{ep}}{c_{ep}+c_{np}}}$
$O^{p}$[8] |  $c_{ef}-\frac{c_{ep}}{c_{ep}+c_{np}+1}$ | DRT[30] |  $\frac{c_{ef}}{1+\frac{c_{ep}}{\mid T\mid}}$ , where $\mid T\mid$ is the size of test suite _T_
Tarantula[5] |  $\frac{\frac{c_{ef}}{c_{ef}+c_{nf}}}{\frac{c_{ef}}{c_{ef}+c_{nf}}+\frac{c_{ep}}{c_{ep}+c_{np}}}$ | Wong3[9] |  $c_{ef}-p$ , where $p=\begin{cases}c_{ep}&\text{ if }c_{ep}\leq 2\\\ 2+0.1(c_{ep}-2)&\text{ if }2<c_{ep}\leq 10\\\ 2.8+0.001(c_{ep}-10)&\text{ if }c_{ep}>10\end{cases}$

SFL ranking metrics have been studied by different authors, 16 of them are
listed by Mao et al. [2]. In Table II, we present the ten SFL ranking metrics
utilized in our empirical assessment. Table III shows five test cases
($t_{1},t_{2}$, $t_{3}$, $t_{4}$, and $t_{5}$) of the max program. The test
cases $t_{4}$ and $t_{5}$ fail, while $t_{1},t_{2}$, and $t_{3}$ pass. Table
IV presents the statement and the block spectra (indicated by the bullets
associated with each statement, block, and test case) of max, the number of
times whether an element is executed or not by failing and passing test cases,
and the suspiciousness score assigned using Ochiai in the $M_{O}$ column.

The suspiciousness score for block 1 is 0.63, and 0.35 or 0 for the remaining
blocks (shown in Table IV). For Ochiai, the most suspicious elements are lines
3 and 4 (or statements 1 and 2). In this example, control-flow spectra, in
particular, blocks, were ranked. These blocks are then mapped onto lines 3 and
4 to be inspected by the developer. Thus, the top suspicious lines contain the
bug. Similarly, one could utilize Ochiai to rank DUAs, which can then be
mapped onto a list of suspicious lines. We describe how we mapped DUAs onto
lines in Section III.

TABLE III: Test Suite $T_{n}$ | Test | Expected Result | Actual Result
---|---|---|---
$t_{1}$ | max( [1,2,3] , 3 ) | 3 | 3
$t_{2}$ | max( [5,5,6] , 3 ) | 6 | 6
$t_{3}$ | max( [2,1,10] , 3 ) | 10 | 10
$t_{4}$ | max( [4,3,2] , 3 ) | 4 | 3
$t_{5}$ | max( [4] , 1 ) | 4 | error
TABLE IV: Program spectra and suspiciousness of the max program with Ochiai metric Line | Statement | Block | $t_{1}$ | $t_{2}$ | $t_{3}$ | $t_{4}$ | $t_{5}$ | $c_{np}$ | $c_{ep}$ | $c_{nf}$ | $c_{ef}$ | $M_{O}$
---|---|---|---|---|---|---|---|---|---|---|---|---
1 | - | - | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | 0 | 3 | 0 | 2 | 0.63
2 | - | 1 | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | 0 | 3 | 0 | 2 | 0.63
3 | 1 | 1 | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | 0 | 3 | 0 | 2 | 0.63
4 | 2 | 1 | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ | 0 | 3 | 0 | 2 | 0.63
5 | 3 | 2 | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ |  | 0 | 3 | 1 | 1 | 0.35
6 | - | 3 | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ |  | 0 | 3 | 1 | 1 | 0.35
7 | 4 | 3 | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ |  | 0 | 3 | 1 | 1 | 0.35
8 | 5 | 4 | $\bullet$ | $\bullet$ | $\bullet$ |  |  | 0 | 3 | 2 | 0 | 0.00
9 | 6 | 5 | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ |  | 0 | 3 | 1 | 1 | 0.35
10 | - | 5 | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ |  | 0 | 3 | 1 | 1 | 0.35
11 | 7 | 6 | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ |  | 0 | 3 | 1 | 1 | 0.35
12 | - | 6 | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ |  | 0 | 3 | 1 | 1 | 0.35
|  |  | ✓ | ✓ | ✓ | ✗ | ✗ |  |  |  |  |

##  III Experiment design

We conducted an experiment666The datasets and results are available at
doi.org/10.5281/zenodo.3258116 to compare the use of data- and control-flow
spectra in fault localization. We applied ten ranking metrics to assess the
effectiveness of both spectra. In what follows, we describe the programs and
bugs used in the experiment, the data collection procedure, and the analysis
criteria used to answer our research questions.

###  III-A Subject programs and faults

We used five real-world programs for the experiment. JFreeChart, Commons Lang,
Commons Math, and Joda-Time were obtained from the Defects4J
database777github.com/rjust/defects4j [31]. The jsoup’s faults were obtained
by us from its source code repository888github.com/jhy/jsoup by looking at the
commit history. Therefore, all programs used in our experiment are composed of
real faults along with their original test cases.

Table V lists our subject programs, their number of lines of code (KLOC), the
number of test cases (TC), and the number of faulty versions (Faults). Each
version contains a single fault that may be spread in several lines. That is,
changes in more than one line were required to fix the bug. In this scenario,
each line of a multiple-line fault is deemed as the bug. The rationale is
that, if a developer reaches at least one of these lines, s/he locates the
bug.

TABLE V: Programs characteristics and number of faults Program | KLOC | TC | Faults
---|---|---|---
Commons Lang | 22 | 2,245 | 30
Commons Math | 85 | 3,602 | 43
JFreeChart | 96 | 2,205 | 26
Joda-Time | 28 | 4,130 | 26
jsoup | 10 | 468 | 38
Total | — | — | 163

However, in selecting faults for our experiment, we only selected bugs for
which data-flow spectra was complete. BA-DUA is unable to collect reliable
data-flow spectra in two cases: 1) the fault throws an exception and it is
located in a code block with a non-handled exception; and 2) the bug is in a
single-block method. The first case happens because BA-DUA marks the exercised
DUAs whenever the method is exited; in this case, the method is exited in a
non-predictable way so that the BA-DUA library does not mark the exercised
DUAs as covered. The second case occurs because BA-DUA does not cover DUAs
when the definition and use are in the same block. Hence, we removed faults
with incomplete data-flow spectra for a fair comparison between spectra.

###  III-B Data collection procedure

We used Jaguar [22] to generate the lists of suspicious DUAs and lines for
each fault. Jaguar is an open source SFL tool that utilizes the
instrumentation libraries of two testing tools: BA-DUA [21] to gather data-
flow spectra and JaCoCo to gather control-flow spectra. It then calculates the
suspiciousness value of each element according to a chosen ranking metric. The
cost of determining the suspiciousness values is very low in comparison to the
time for test suite execution and spectra data collection.

We applied this procedure for all ten ranking metrics (see Table II) used in
this evaluation: Ochiai, Kulczynski2, McCon, $O^{p}$, Tarantula, Jaccard,
Zoltar, Minus, DRT, and Wong3. In this work, we did not intend to compare the
ranking metrics; thus, we were not exhaustive in the selection of ranking
metrics. Instead, we selected different metrics only to assess whether the
spectra’s performance is affected by the chosen metric.

We identified the faulty lines of jsoup and the programs from Defects4J by
comparing the buggy and fix commits in their repositories. For faults occurred
due to missing code, we deemed the previous line of code as the bug site.
However, if the previous line contains non-executable code (e.g., comments,
blank lines, closing brackets), the line after the change was deemed as the
faulty one. When ties occur, the worst case is considered. It means that if
two or more lines have the same suspiciousness score, the position of the
faulty line includes all tied lines, since they have equal chances of being
inspected.

As the data-flow spectra are DUAs, we mapped them onto lines to determine
their faulty sites. A DUA has always a definition line and a use line, and
possibly a source line (for p-use DUAs). To check whether the bug was found,
the faulty line is compared to these three lines (definition, use, and
source). When the result is false, all these lines are added to the number of
lines inspected until finding the fault.

We created a script to check the position of the faults over each respective
DUA and line suspiciousness lists generated by Jaguar. It records the number
of lines until reaching the faulty line considering the above criteria.

###  III-C Measurement criteria

To answer our research questions, we measured the effectiveness of data- and
control-flow to locate the faults by the _absolute number_ of lines inspected
until reaching the faults. We restricted the number of lines inspected to 99
lines of code. If a fault is beyond the 99th position we considered that it
was not found. Indeed, this is a very large limit since developers in practice
inspect only the first picks of the suspiciousness lists [32, 33].

We also measured the efficiency of data- and control-flow spectra by
collecting the _time spent_ to create the suspiciousness lists of each faulty
version. The total overhead cost comprehends running all unit tests, storing
the spectra data, calculating the suspiciousness of each element, and
generating the suspiciousness list.

###  III-D Statistical Analysis

We carried out a statistical analysis to evaluate the results obtained by
data- and control-flow spectra with different ranking metrics. First, we
applied the Anderson-Darling normality test [34] to our data, which follows a
non-normal distribution. Then, we used the Wilcoxon signed-rank test [35] for
the hypothesis test and Cliff’s delta [36] to measure the effect size. These
statistical methods are suitable to use with non-parametric data. The
significance level applied was 5%. The Wilcoxon signed-rank test assesses
differences in the magnitude of measurements between the compared techniques.
The Cliff’s delta calculates the amount of difference between the two
techniques. We explain our null and alternative hypotheses for each test in
Section IV.

##  IV Results

First, we present the effectiveness of data- and control-flow spectra for
different ranking metrics and then the run-time overhead to assess the
efficiency of the two spectra.

###  IV-A Effectiveness of data- and control-flow spectra

We compared the effectiveness of data- and control-flow spectra using the ten
ranking metrics described in Table II. The most suspicious DUAs and lines,
ranked according to the metrics, are mapped onto lines to be inspected.
Figures 3 and 4 describe the number of faults located when a developer
inspects different amounts of suspicious lines.

DUA and line spectra have similar behaviors for all ranking metrics, except
Wong3. They locate the same number of faults up to 7 investigated lines. After
that, and up to 40 lines, DUA spectrum locates more faults. The largest gap is
located at 15 lines—for almost all metrics, DUA locates 60 faults whilst line
spectrum locates 40 faults. There is no difference between DUA and line
spectra for more than 40 lines inspected up to 70 lines. For more than 70
lines, line spectrum performs better. For Wong3, DUA spectrum performs better
after 5 lines, with a constant gap of 20 more faults located. This difference
maintains almost constant until the end. However, Wong3 perform poorly
locating at most 60 faults when using DUA and 40 with line spectrum. The other
metrics locate more than 100 faults inspecting up to 100 lines using line
spectrum. DUA spectrum locates about 80 faults by inspecting only 20 lines
using Ochiai, Jaccard, Kulczynski2, McCon, $O^{p}$, and Minus.

(a) Ochiai

(b) Kulczynski2

(c) McCon

(d) Jaccard

(e) Zoltar

(f) Tarantula

Figure 3: Effectiveness of DUA and line spectra in fault localization using
different ranking metrics

(a) Op

(b) DRT

(c) Minus

(d) Wong3

Figure 4: Effectiveness of DUA and line spectra in fault localization using
different ranking metrics

Table VI presents the results of the statistical analysis. The null hypothesis
is that there is no difference in the effectiveness of data- and control-flow
spectra to locate faults. The alternative hypothesis is that data-flow
spectrum is more effective than control-flow spectrum—i.e., data-flow spectrum
requires the examination of less suspicious lines to locate faults.

TABLE VI: Statistical results comparing data- and control-flow Metric | P-value | Effect Size | B-T-W | Min | Q1 | Q2 | Q3
---|---|---|---|---|---|---|---
(%) | DF | CF | DF | CF | DF | CF | DF | CF
Ochiai | 1.59 | 0.032 (I) | 73-50-40 | 2 | 1 | 9 | 15 | 25 | 39 | 100 | 100
Kulczynski2 | 1.66 | 0.023 (I) | 74-49-40 | 2 | 1 | 9 | 11.5 | 26 | 36 | 100 | 100
McCon | 1.66 | 0.023 (I) | 74-49-40 | 2 | 1 | 9 | 11.5 | 26 | 36 | 100 | 100
Jaccard | 1.02 | 0.029 (I) | 74-49-40 | 2 | 1 | 9 | 11.5 | 26 | 36 | 100 | 100
Zoltar | 1.12 | 0.024 (I) | 75-49-39 | 2 | 1 | 9 | 12.5 | 27 | 37 | 100 | 100
Tarantula | 0.59 | 0.035 (I) | 75-48-40 | 2 | 1 | 10 | 15 | 27 | 39 | 100 | 100
$O^{p}$ | 1.39 | 0.027 (I) | 69-57-37 | 1 | 1 | 9 | 13.5 | 30 | 40 | 100 | 100
DRT | 2.32 | 0.025 (I) | 68-57-38 | 1 | 1 | 9 | 13.5 | 30 | 39 | 100 | 100
Minus | 2.03 | 0.033 (I) | 68-57-38 | 1 | 1 | 9 | 14.5 | 30 | 39 | 100 | 100
Wong3 | 0.01 | 0.331 (S) | 46-100-17 | 2 | 1 | 12 | 70 | 100 | 100 | 100 | 100

The P-value column presents the results of the significance test. For all
metrics, DUA spectrum locates more faults inspecting less code with
statistical significance (p-value $\leq$ 5%). The Effect Size column presents
the Cliff’s delta results for all metrics, in which I means that the size is
insignificant and S is a small effect. Except for Wong3, for which the effect
size is small, the other metrics effect size is insignificant.

The B-T-W column shows the number of times DUA spectrum was better than (B),
tied with (T) or worse than (W) line spectrum. It shows that DUA was better
than line for near to half of the faults (46% or 75 faults for Ochiai and
Zoltar). Line spectrum was better for one-quarter of the bugs (e.g., Ochiai,
Tarantula, Jaccard).

Table VI also presents the minimum number of inspected lines to find a bug
(Min), the first (Q1), second (Q2), and third (Q3) quartiles for both data-
flow (DF) and control-flow (CF). DUA spectrum with Ochiai locates half of the
faults by inspecting 25 lines while line spectrum needs 39 lines to reach the
same amount of faults. The difference in Q2 varies from 14 (Ochiai) to 9
(DRT). The first quartile also indicates that DUA spectrum is more effective
to locate one-quarter of the faults. It requires the inspection of 9 lines for
almost all metrics while it can require 15 lines using line spectrum with
Ochiai. Both DF and CF were not able 75% of all faults as shown in the Q3
column.

###  IV-B Efficiency of data-flow and control-flow

To understand the costs of using data- and control-flow spectra, we measured
the time spent to use both spectra for SFL. The time spent for DF and CF
comprises: (1) running all tests, (2) collecting the spectra data, (3)
calculating suspiciousness of all program elements, and (4) creating the SFL
lists. Table VII shows the results for the efficiency comparison. The _JUnit_
, _DF_ , and _CF_ columns show the time spent (in seconds) for executing,
respectively, only the JUnit tests, Jaguar with data-flow spectra, and Jaguar
with control-flow spectra. These values consist of the average execution time
for all versions of a project for all ten ranking metrics.

The DF/JUnit column shows the overhead to collect data-flow spectra compared
to the execution of JUnit. The CF/JUnit column presents the overhead to
collect control-flow spectra compared to JUnit. The average overhead for all
programs using data-flow and control-flow are 353% and 102%, respectively. The
DF/CF column shows the ratio between the data-flow time and control-flow time.
It indicates how much extra time is needed to execute Jaguar with data-flow
compared to control-flow. For JFreeChart, generating a list of suspicious DUAs
requires 143% more time than generating a list of suspicious statements.
However, the total time to generate the list of suspicious DUAs in this case
is 88 seconds.

TABLE VII: Data-flow and control-flow efficiency for each program Program | Run-time (s) | Overhead (%)
---|---|---
JUnit | DF | CF | DF/JUnit | CF/JUnit | DF/CF
Commons Lang | 18.83 | 89.67 | 33.92 | 376.08 | 80.09 | 164.36
Commons Math | 144.32 | 515.95 | 265.16 | 257.51 | 83.74 | 94.58
JFreeChart | 22.27 | 88.62 | 36.36 | 298.0 | 63.3 | 143.72
Joda-Time | 4.88 | 165.42 | 47.93 | 3287.71 | 881.67 | 245.1
jsoup | 4.35 | 22.95 | 11.37 | 427.52 | 161.38 | 101.82
Average | 38.93 | 176.52 | 78.95 | 353.43 | 102.8 | 123.58

##  V Discussion

To better understand the results of Section IV, we discuss and analyze the
results next. The discussion is organized by our research questions.

### Which spectrum is more effective to locate bugs: data- or control-flow?

The results confirm our hypothesis that data-flow, by providing more detailed
information, improves fault localization. DUA spectrum leads the developer to
inspect less code than line spectrum with statistical significance for all
ranking metrics. However, the effect size is insignificant, except for Wong3.
DUA spectrum outperforms line spectrum in the range of 7 to 40 investigated
lines. After that, there is no difference or line spectrum performs better,
which explains the insignificant effect size. For most ranking metrics,
control-flow reaches more faults than data-flow after the 70th position.

Indeed, if the faulty DUA is not the first or second pick, the bug will hardly
be located at the top 5 suspicious lines since DUAs are composed of a
definition, a use, and possibly a source, if a p-use DUA. Thus, each ranked
DUA adds 2 to 3 lines to be investigated. Being able to beat line spectrum at
the top 10 lines shows that data-flow spectrum singles out specific faulty
DUAs to be investigated. Additionally, DUA spectrum demanded less code to be
inspected for a large number of faults: 75 out of 163 using Ochiai and Zoltar
whilst line spectrum required the inspection of less code only for 40 and 39
faults, respectively, for the same ranking metrics—a difference of 87.5%.

Around 20 out of 163 (12%) faults can be located by investigating only the top
5 lines, using either DUA or line spectra. On the other hand, one can reach 40
faults (25%) by investigating only 9 lines using DUA spectrum and all metrics,
excepting Tarantula and Wong3. Furthermore, if the developer investigates up
to 25 suspicious lines, s/he will reach half of the faults using Ochiai and
DUA spectrum. If the practitioner decides to use line spectrum, s/he will need
to inspect 14 more lines to achieve the same result.

Some studies have shown, though, that practitioners may give up on using an
SFL technique if the fault is not located at the top 5 picks [32, 33]. Since
there is no difference between DUA and line spectra up to 7 suspicious lines,
the difference is too little to be useful in practice. Notwithstanding,
sticking to only the first 5 lines is not practical either since too few
faults can be located in this short range, in our study, only 12%. Data-flow
spectrum can leverage SFL techniques. However, practitioners should be
educated to inspect 10 to 25 lines to reach a quarter to half of the faults,
respectively. Other recent results have shown that SFL can help developers to
locate faults even when the faulty line is not ranked among the top suspicious
ones [37].

### Which spectrum is more efficient to locate bugs: data- or control-flow?

Table VII summarized the run-time costs for each project. The data-flow
suspiciousness lists require from 94% to 245% more time to be generated than
the control-flow lists. This result differs from the 38% overhead presented by
BA-DUA [21]. Such a discrepancy is justified by the extra work needed to run
an SFL technique.

Data-flow implies more information than control-flow: if on the one hand it
provides detailed data for fault localization; on the other hand, more time is
needed to compute such data. Thus, control-flow is more efficient, providing
fault localization information with less overhead.

However, the amount of time needed to generate the lists of suspicious DUAs
for the medium- and large-sized real programs used in this assessment is not
prohibitive. For four out of five subjects, the time varies from 22 seconds to
2:45 minutes. Only for Commons-Math, the time jumps to 8:35 minutes. For this
particular program, line spectrum is also expensive to obtain: 4:25 minutes.
Since DUA spectrum can improve the fault localization effectiveness, the extra
time to create the suspiciousness lists seems affordable at industrial
settings.

##  VI Threats to validity

The internal validity threats to our experiment are related to the Jaguar
tool. To mitigate them, we manually checked the Jaguar’s output using small
programs. Regarding the data-flow efficiency results, it is certainly possible
to optimize the Jaguar tool to reduce its run-time overhead for both spectra.
Our chosen strategy aimed to get a first picture of the performance benefits
from the recent promising data-flow spectra tool (BA-DUA). As we explain in
Section III, we only selected bugs for which data-flow spectrum was complete.
Thus, we excluded faults that throws exceptions without handling them and
faults in single-block methods. Improvements in BA-DUA can allow us to use
such faults in future experiments.

All faults were found in their source code repositories. We assumed that each
code change between a faulty version and its consecutive fixed version was
made to fix the bug. We disregarded changes that do not affect the program
behavior such as adding or removing empty lines and line indentation changes.
For multiple-line faults, we considered the best case scenario. A fault is
deemed as found when the top ranked one of its lines is reached. However, this
scenario occurs for both spectra. For tie cases, we considered the worst case,
in which all lines with the same suspiciousness score of the faulty one are
deemed to calculate its position.

Regarding external validity threats, we used five programs from different
domains and sizes to expose the techniques to different scenarios. Although
the programs utilized in the experimental assessment are quite heterogeneous,
we caution the reader that the techniques may present different results for a
different set of programs. Also, all programs assessed in this experiment have
a single fault per version. The results may differ for programs containing
multiple faults.

Regarding construct validity threats, we assessed the techniques using
statistical tests and descriptive data. Our experiment was built to evaluate
how quickly a technique will reach the fault site. One issue, though, deems
the assumption that the ranked elements will be followed as they were
presented, which may not actually happen in practice. Another issue is that
reaching the bug site does not necessarily mean locating the defect, which is
known as perfect bug detection [32].

##  VII Related work

Despite the ability to exercise different aspects during a test execution,
data-flow is rarely used to support SFL. Few initiatives use definition-use
associations (DUAs) [6, 13] while others use program slicing [38, 39] or
different types of data and control dependencies [13, 40, 41]. All these
approaches demand a costly time overhead to collect data-flow spectra.

Santelices et al. [6] proposed a technique, avg-SBD, that combines different
spectrum types for fault localization: statements, branches, and du-pairs—a
variant of data-flow information that takes into account only c-use DUAs. They
also introduce an approximate DUA spectrum, avg-SBD approx, which has lower
overhead at run-time. The results, assessed using small- to medium-sized
programs, showed that their approach locates more faults than each spectrum
isolated. They also showed that different faults are best located by different
coverage types.

Masri [13] uses a spectrum called Dynamic Information Flow Analysis (DIFA) for
fault localization. DIFA is composed of interactions performed in an
execution, including inter-procedural data- and control-flow dependences from
statements and variables. The author compared DIFA with statement, branch, and
DUA spectra using 18 faults of medium-sized programs. DIFA presented better
performance to locate the bugs. However, the time to generate DIFA spectra was
2–10 times slower than DUA and branch spectra.

Hemmati [42] assessed the ability of data- and control-flow coverage criteria
to reveal faults on programs from the Defects4J database. Du-pair criterion
covered 79% of faults that were not covered by control-flow criteria. He also
showed that 15% of all faults were not covered by any criterion. The author
did not report issues regarding run-time costs.

Yu et al. [40] presented the LOUPE technique, which combines data- and
control-dependencies for fault localization. The output is a list of
statements. Their experiments using the Siemens suite presented better
performance than the compared techniques. They also assessed LOUPE in the
space program, which took 100 minutes to execute. Eichinger et al. [41]
propose the data-flow enabled call graphs (DEC graphs), which is a method call
graph with data-flow information. DEC graphs register also parameters and
method-return values. To reduce the number of possible parameter values, they
discretize numerical parameter and return values using Data Mining approaches.
They assessed the technique including ten faults in the Weka program—which has
301 KLOC. The authors do not reported the run-time overhead of the technique.

As with the works of Santelices et al. [6] and Masri [13], our study compares
DUA and statement spectra to investigate their effectiveness for fault
localization. Differently from the previous works, we assessed both spectra
using ten different ranking metrics. Moreover, we used medium- to large-sized
programs containing real faults. We also evaluated their performance to locate
faults for absolute values and compared the overhead of SFL techniques based
on data- and control-flow spectra. Finally, we carried out a statistical
analysis in our assessment, showing that data-flow spectrum can be useful for
fault localization at an affordable cost.

##  VIII Conclusions

We carried out an experiment comparing the use of data-flow spectrum
(definition-use associations—DUAs) and control-flow spectrum (lines) in fault
localization. Our goal was to corroborate the body of evidence with more
robust results, showing that data-flow is more effective than control-flow in
fault localization. In addition, we aimed to verify whether new approaches to
collect DUAs would allow the application of data-flow-based SFL in programs
similar to those developed in the industry. We used 163 real faulty versions
of five industry-like programs whose sizes vary from 10 to 96 KLOC.

DUA spectrum located more bugs inspecting less code for all ranking metrics
with statistical significance. DUA spectrum outperforms line spectrum in the
range from 7 to 40 inspected lines. By inspecting from 10 to 25 lines, a
practitioner will reach the bug site for a quarter to half of the faults. Line
spectrum requires to investigate 14 more lines to reach half of the faults.
After 70 inspected lines, line spectrum can reach more bugs than DUA spectrum.
As each DUA has 2 or 3 lines, its performance is overcome by line spectrum as
the number of inspected lines increases.

It is known that practitioners expect the fault to be located in the first 5
most suspicious lines. Nevertheless, such a tight target is successful for
only 12% of the faults in our experiment. SFL will hardly be adopted in
practice with this small success rate. Data-flow spectrum can help the
adoption of SFL techniques at industrial settings, but the practitioners
should be educated to inspect a few more code excerpts to take advantage of
SFL techniques.

Our results suggest that from 10 to 25 lines would significantly improve the
number of faults hit by SFL techniques using data-flow spectrum. Regarding
efficiency, the overall time for the subjects of our experiment varies from 22
seconds to 8:35 minutes using data-flow spectrum, which indicates that its use
is feasible for many programs developed by the industry. Thus, the hypothesis
that data-flow generates more detailed information that improves fault
localization was verified in our experiment. Although more time is needed to
collect such an information, the overhead is affordable for real-world
software.

In future work, we will exploit contextual information associated with data-
flow spectrum, especially the use of variables from the most suspicious DUAs
to locate faults. We will also carry out user studies to evaluate whether
information regarding suspicious variables improves fault localization.

## Acknowledgment

This research was supported by FAPESP (São Paulo Research Foundation),
processes 13/24992-2, 14/23030-5, and 14/50937-1; by CNPq process
311174/2017-5; and by the Research Support Center on Open Source Software
(NAPSoL) of the University of São Paulo.

## References

  * [1] G. Tassey, “The economic impacts of inadequate infrastructure for software testing,” _National Institute of Standards and Technology, RTI Project_ , vol. 7007, no. 011, 2002.
  * [2] X. Mao, Y. Lei, Z. Dai, Y. Qi, and C. Wang, “Slice-based statistical fault localization,” _Journal of Systems and Software_ , vol. 89, no. 0, pp. 51–62, 2014.
  * [3] G. Dandan, S. Xiaohong, W. Tiantian, M. Peijun, and Y. Wang, “State dependency probabilistic model for fault localization,” _Information and Software Technology_ , vol. 57, no. 0, pp. 430–445, 2014.
  * [4] A. Zeller, _Why programs fail: A guide to systematic debugging_ , 2nd ed. Burlington, MA: Morgan Kaufmann Publishers, 2009.
  * [5] J. A. Jones, M. J. Harrold, and J. Stasko, “Visualization of test information to assist fault localization,” in _Proceedings of the 24th International Conference on Software Engineering_ , ser. ICSE’02, 2002, pp. 467–477.
  * [6] R. Santelices, J. A. Jones, Y. Yu, and M. J. Harrold, “Lightweight fault-localization using multiple coverage types,” in _Proceedings of the 31st International Conference on Software Engineering_ , ser. ICSE’09, 2009, pp. 56–66.
  * [7] R. Abreu, P. Zoeteweij, and A. J. C. van Gemund, “On the accuracy of spectrum-based fault localization,” in _Proceedings of the Testing: Academic and Industrial Conference Practice and Research Techniques - MUTATION_ , ser. TAICPART-MUTATION’07, 2007, pp. 89–98.
  * [8] L. Naish, H. J. Lee, and K. Ramamohanarao, “Spectral debugging with weights and incremental ranking,” in _Proceedings of the 16th Asia-Pacific Software Engineering Conference_ , ser. APSEC’09, 2009, pp. 168–175.
  * [9] W. E. Wong, V. Debroy, and B. Choi, “A family of code coverage-based heuristics for effective fault localization,” _Journal of Systems and Software_ , vol. 83, no. 2, pp. 188–208, 2010.
  * [10] A. Gonzalez-Sanchez, “Automatic error detection techniques based on dynamic invariants,” Master’s thesis, Delft University of Technology, 2007.
  * [11] S. Pearson, J. Campos, R. Just, G. Fraser, R. Abreu, M. D. Ernst, D. Pang, and B. Keller, “Evaluating and improving fault localization,” in _Proceedings of the 39th International Conference on Software Engineering_ , ser. ICSE’17, 2017, pp. 609–620.
  * [12] C. Ma, Y. Zhang, T. Zhang, Y. Lu, and Q. Wang, “Uniformly evaluating and comparing ranking metrics for spectral fault localization,” in _Proceedings of the 14th International Conference on Quality Software_ , ser. QSIC’14, 2014, pp. 315–320.
  * [13] W. Masri, “Fault localization based on information flow coverage,” _Software Testing, Verification and Reliability_ , vol. 20, no. 2, pp. 121–147, 2010.
  * [14] M. Hutchins, H. Foster, T. Goradia, and T. Ostrand, “Experiments of the effectiveness of dataflow- and controlflow-based test adequacy criteria,” in _Proceedings of the 16th International Conference on Software Engineering_ , ser. ICSE’94, 1994, pp. 191–200.
  * [15] M. Renieris and S. P. Reiss, “Fault localization with nearest neighbor queries,” in _Proceedings of the 18th IEEE International Conference on Automated Software Engineering_ , ser. ASE’03, 2003, pp. 30–39.
  * [16] J. A. Jones, J. F. Bowring, and M. J. Harrold, “Debugging in parallel,” in _Proceedings of the ACM SIGSOFT International Symposium on Software Testing and Analysis_ , ser. ISSTA’07, 2007, pp. 16–26.
  * [17] T. M. Chilimbi, B. Liblit, K. Mehra, A. V. Nori, and K. Vaswani, “HOLMES: Effective statistical debugging via efficient path profiling,” in _Proceedings of the 31st International Conference on Software Engineering_ , ser. ICSE’09, 2009, pp. 34–44.
  * [18] J. Misurda, J. A. Clause, J. L. Reed, B. R. Childers, and M. L. Soffa, “Demand-driven structural testing with dynamic instrumentation,” in _Proceedings of the 27th International Conference on Software Engineering_ , ser. ICSE’05, 2005, pp. 156–165.
  * [19] R. Santelices and M. J. Harrold, “Efficiently monitoring data-flow test coverage,” in _Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering_ , ser. ASE’07, 2007, pp. 343–352.
  * [20] M. L. Chaim and R. P. A. d. Araujo, “An efficient bitwise algorithm for intra-procedural data-flow testing coverage,” _Information Processing Letters_ , vol. 113, no. 8, pp. 293–300, 2013.
  * [21] R. P. A. de Araujo and M. L. Chaim, “Data-flow testing in the large,” in _Proceedings of the 7th IEEE International Conference on Software Testing, Verification and Validation_ , ser. ICST’14, 2014, pp. 81–90.
  * [22] H. L. Ribeiro, H. A. de Souza, R. P. A. de Araujo, M. L. Chaim, and F. Kon, “Jaguar: A spectrum-based fault localization tool for real-world software,” in _Proceedings of the 11th International Conference on Software Testing, Verification and Validation_ , ser. ICST’18, 2018, pp. 404–409.
  * [23] K. Moir, “Releng of the nerds: Open source release engineering,” March 2011, SDK code coverage with JaCoCo. [Online]. Available: http://relengofthenerds.blogspot.com.br/2011/03/sdk-code-coverage-with-jacoco.html
  * [24] S. Rapps and E. J. Weyuker, “Selecting software test data using data flow information,” _IEEE Transactions on Software Engineering_ , vol. 11, no. 4, pp. 367–375, 1985.
  * [25] T. Reps, T. Ball, M. Das, and J. Larus, “The use of program profiling for software maintenance with applications to the year 2000 problem,” in _Proceedings of the 6th European Software Engineering Conference Held Jointly with the 5th ACM SIGSOFT Symposium on the Foundations of Software Engineering_ , ser. ESEC/FSE’97, 1997, pp. 432–449.
  * [26] S. Elbaum, D. Gable, and G. Rothermel, “The impact of software evolution on code coverage information,” in _Proceedings of the 19th IEEE International Conference on Software Maintenance_ , ser. ICSM’01, 2001, pp. 170–179.
  * [27] M. J. Harrold, G. Rothermel, R. Wu, and L. Yi, “An empirical investigation of program spectra,” _SIGPLAN Notices_ , vol. 33, no. 7, pp. 83–90, 1998.
  * [28] V. Debroy and W. E. Wong, “A consensus-based strategy to improve the quality of fault localization,” _Software: Practice and Experience_ , vol. 43, no. 8, pp. 989–1011, 2013.
  * [29] J. Xu, W. K. Chan, Z. Zhang, T. H. Tse, and S. Li, “A dynamic fault localization technique with noise reduction for java programs,” in _Proceedings of the 11th International Conference on Quality Software_ , ser. QSIC’11, 2011, pp. 11–20.
  * [30] M. L. Chaim, J. C. Maldonado, and M. Jino, “A debugging strategy based on requirements of testing,” in _Proceedings of the 7th European Conference on Software Maintenance and Reengineering_ , ser. CSMR’03, 2003, pp. 160–169.
  * [31] R. Just, D. Jalali, and M. D. Ernst, “Defects4j: A database of existing faults to enable controlled testing studies for java programs,” in _Proceedings of the ACM SIGSOFT International Symposium on Software Testing and Analysis_ , ser. ISSTA’14, 2014, pp. 437–440.
  * [32] C. Parnin and A. Orso, “Are automated debugging techniques actually helping programmers?” in _Proceedings of the ACM SIGSOFT International Symposium on Software Testing and Analysis_ , ser. ISSTA’11, 2011, pp. 199–209.
  * [33] P. S. Kochhar, X. Xia, D. Lo, and S. Li, “Practitioners’ expectations on automated fault localization,” in _Proceedings of the 25th International Symposium on Software Testing and Analysis_ , ser. ISSTA’16, 2016, pp. 165–176.
  * [34] T. W. Anderson and D. A. Darling, “A test of goodness of fit,” _Journal of the American Statistical Association_ , vol. 49, no. 268, pp. 765–769, 1954\.
  * [35] F. Wilcoxon, “Individual comparisons by ranking methods,” _Biometrics bulletin_ , vol. 1, no. 6, pp. 80–83, 1945.
  * [36] N. Cliff, “Dominance statistics: Ordinal analyses to answer ordinal questions,” _Psychological Bulletin_ , vol. 114, no. 3, pp. 494–509, 1993\.
  * [37] H. A. de Souza, “Assessment of spectrum-based fault localization for practical use,” PhD thesis, Institute of Mathematics and Statistics – University of São Paulo, São Paulo, Brazil, April 2018.
  * [38] Y. Lei, X. Mao, Z. Dai, and C. Wang, “Effective statistical fault localization using program slices,” in _Proceedings of the IEEE 36th Annual International Computers, Software and Applications Conference_ , ser. COMPSAC’12, 2012, pp. 1–10.
  * [39] X. Ju, S. Jiang, X. Chen, X. Wang, Y. Zhang, and H. Cao, “Hsfal: Effective fault localization using hybrid spectrum of full slices and execution slices,” _Journal of Systems and Software_ , vol. 90, no. 0, pp. 3–17, 2014\.
  * [40] K. Yu, M. Lin, Q. Gao, H. Zhang, and X. Zhang, “Locating faults using multiple spectra-specific models,” in _Proceedings of the 26th ACM Symposium on Applied Computing_ , ser. SAC’11, 2011, pp. 1404–1410.
  * [41] F. Eichinger, K. Krogmann, R. Klug, and K. Böhm, “Software-defect localisation by mining dataflow-enabled call graphs,” in _Proceedings of the Joint European Conference on Machine Learning and Principles and Practice on Knowledge Discovery in Databases_ , ser. ECML PKDD 2010, 2010, pp. 425–441.
  * [42] H. Hemmati, “How effective are code coverage criteria?” in _2015 IEEE International Conference on Software Quality, Reliability and Security_ , ser. QRS’15, 2015, pp. 151–156.