[1,2]C. Bray

1]Colorado School of Mines, Golden, Colorado, USA

2]Lawrence Livermore National Laboratory, Livermore, California, USA

3]XIA LLC, Oakland, California, USA

4]Pacific Northwest National Laboratory, Richland, Washington, USA

5]Facility for Rare Isotope Beams, East Lansing, Michigan, USA

6]TRIUMF, Vancouver, BC, Canada

7]NOVA School of Science and Technology, Lisbon, Portugal

8]Université de Strasbourg, Strasbourg, France

9]Star Cryoelectronics, Santa Fe, New Mexico, USA

10]Laboratoire de Physique Corpusculaire, CNRS/IN2P3, Caen, France

11]CEA Saclay, Paris, France

# The Data Acquisition System for Phase-III of the BeEST Experiment

<EMAIL_ADDRESS>S. Fretwell  I. Kim  W. K. Warburton  F. Ponce  K. G. Leach
S. Friedrich  R. Abells  P. Amaro  A. Andoche  R. Cantor  D. Diercks  M.
Guerra  A. Hall  C. Harris  J. Harris  L. Hayen  P. A. Hervieux  G. B. Kim  A.
Lennarz  V. Lordi  J. Machado  P. Machule  A. Marino  D. McKeen  X. Mougeot
C. Ruiz  A. Samanta  J. P. Santos  C. Stone-Whitehead  [  [  [  [  [  [  [  [
[  [  [

###### Abstract

The BeEST experiment is a precision laboratory search for physics beyond the
standard model that measures the electron capture decay of 7Be implanted into
superconducting tunnel junction (STJ) detectors. For Phase-III of the
experiment, we constructed a continuously sampling data acquisition system to
extract pulse shape and timing information from 16 STJ pixels offline. Four
additional pixels are read out with a fast list-mode digitizer, and one with a
nuclear MCA already used in the earlier limit-setting phases of the
experiment. We present the performance of the data acquisition system and
discuss the relative advantages of the different digitizers.

###### keywords:

Superconducting Tunnel Junctions (STJs), Data Acquisition Systems (DAQs),
Linearity, Timing Jitter, BeEST Experiment

##  1 Introduction

The Beryllium-7 Electron capture in Superconducting Tunnel junctions (“BeEST”)
experiment [1] currently sets leading laboratory-based exclusion limits on
heavy neutrinos in the 100-850 keV mass range through precise measurements of
7Be decay [2]. For the experiment, 7Be is implanted into superconducting
tunnel junction (STJ) sensors at the TRIUMF-ISAC rare isotope beam facility,
and its decay is measured in an adiabatic demagnetization refrigerator at 100
mK at LLNL. The electron capture decay deposits of order $\sim$100 eV in the
STJ from the 7Li recoil and the relaxation of its electronic shell [1]. This
produces $\sim$10 nApp current signals with a rise time of $\sim$1 $\mu$s and
a decay time of $\sim$100 $\mu$s that are read out with a specialized
transimpedance amplifier from XIA LLC [3]. The STJ detector array is
calibrated in-situ by illuminating it with a pulsed 355 nm laser (Spectra
Physics, model J40-B16-106Q) at a rate of 100 Hz throughout the data
acquisition. The number of detected photons varies and produces a comb of
spectral lines whose energies are precise multiples of 3.49865 $\pm$ 0.00015
eV [4]. In addition, $\gamma$ rays from two of the 7Be decay branches can
Compton scatter in the Si substrate below the STJ and produce a broad spectral
background [5]. Heavy neutrinos would produce an offset 7Li recoil spectrum at
a reduced energy determined by the neutrino mass with a relative intensity set
by its admixture to the electron neutrino. To improve current limits to
admixtures $<10^{-5}$, exquisite energy precision and artifact rejection are
required.

Phase-III of the BeEST experiment [1] aims to improve the sensitivity of the
heavy neutrino search and evaluate scaling-related challenges for Phase-IV by
scaling from a single STJ to a small array of STJ sensors. This introduces the
possibility of correlating signals in different pixels and assessing pixel-to-
pixel variations. The data acquisition system (DAQ) should provide maximum
flexibility to understand spectral details and the needs and trade-offs in
future upgrades. Additionally, the digitizer must not contribute to the
electronic noise beyond the pre-amplifier contribution of $\sim$1 eV [6],
should be capable of timing accuracy of order $\sim$1 $\mu$s to tag coincident
events, and must demonstrate calibration residuals $<$0.1 eV so that
nonlinearity artifacts cannot produce a false heavy neutrino signal in the
mass range of interest [2]. This paper discusses the DAQ and its performance
in Phase-III.

##  2 Data Collection

In order to comprehensively analyze the spectral features of the BeEST and
assess the full response characteristics of the STJ detectors, we constructed
a new DAQ that saves continuous synchronous waveforms from 16 STJ channels.
The accumulated data stream is later processed offline, enabling, for the
first time, pulse shape analysis of the 7Be decay signals. The DAQ is designed
around two NI PXIe-6356 cards, each of which digitizes 16-bit differential
voltage samples from 8 STJs at a rate of 1.25 MSa/s. The voltage samples are
captured on a range of [-1,1] V to match the pre-amplifier output range, and
time synchronized with each other by deriving all of the sample clocks from
the same 100 MHz backplane clock. Additionally, each PXIe-6356 offers 24
separate digital inputs, one of which is used to synchronously acquire the
laser trigger TTL signal. To minimize aliasing, we designed an external
differential low pass filter around the Mini-Circuits LPF-B0R35+. In testing,
each channel achieved an attenuation of at least 10 dB at 625 kHz.

Figure 1: Waveforms from 16 STJ channels showing seven 7Be events, two laser
pulses, and one substrate event. Inset: Short and long trapezoidal filters of
a sample pulse.

Over the course of the 50-day acquisition for the Phase-III physics run, the
NI DAQ saved 160 TB of data, a sample of which is shown in Figure 1. We chose
to save waveforms in 10 minute segments for data integrity and ease-of-use,
with a few seconds of downtime between segments. While handling the data
volume was nontrivial, the data acquisition was particularly robust because
there was no on-line processing that could be incorrectly configured.

The waveforms were processed with two trapezoidal filters - a short filter
with shaping and flat-top times of 16 and 4 $\mu$s, respectively, and a long
filter with 48 and 24 $\mu$s for those values as well as decay time
correction. The inset of Figure 1 shows the results of processing a 7Be pulse
with these filters. The short filter is used to identify pulses in the data
stream by using a rising edge trigger with the trigger level set 5$\sigma$
above the filtered baseline. Next, we fit three line segments to the pre-
trigger baseline, rising edge, and flat top of the long filter, and calculate
the pulse arrival time as the intersection of the fitted baseline and rising
edge. Finally, as an estimate of the event energy, we measure the pulse height
by taking the difference between the center of the long filter flat-top and
the pre-trigger baseline.

The four remaining operational STJs are digitized with an XIA MPX-32D [3]
which is configured to save the trapezoidally filtered pulse maximum and
rising-edge trigger time for each pulse in list mode. The trapezoidal filter
is calculated by an onboard FPGA, which is fed by four 8-channel 12-bit ADCs
that operate at 50 MSa/s. Similar to the continuous DAQ, there are two
trapezoidal filter options; however the longer filter is used for both pulse
height determination and for detecting pulses in the data stream because its
lower noise reduces the minimum trigger level. The longer filter uses shaping
and flat-top times of 16 and 1 $\mu$s, and features pixel-specific decay time
correction. In addition to saving data in list mode, the XIA MPX-32D provides
the crucial ability to save I(V) curves, digitally control the bias voltage,
and analyze real-time MCA spectra from the entire array for setup and
diagnostic purposes.

Finally, we duplicate the signal from one STJ at the pre-amplifier output,
filter it with an Ortec 672 Shaping Amplifier, and read it out with an Ortec
Aspec 927 nuclear MCA. The shaping amplifier is configured with a 10 $\mu$s
shaping time and pole-zero correction tuned to match the pulse decay time, and
the Ortec Aspec 927 saves two spectra of filtered pulse maxima - one in
coincidence with the laser trigger TTL and the other in anticoincidence. A
relatively short 90-second MCA window is chosen for flexible drift correction
and to reject short periods of increased pickup. Despite being limited to a
single channel, the Ortec Aspec 927 is a valuable comparison for the other
digitizers because it was the digitizer used in Phase-II of the BeEST
experiment and because it features sliding-scale linearization to achieve DAQ
nonlinearity as low as 1.6 meV rms [7, 6].

##  3 DAQ Performance

To calibrate the data, we use iminuit [8] to simultaneously fit several
Gaussian functions to the laser spectrum from each 10 minute segment, with the
their centroids providing energy calibration points. A second-order polynomial
is fit to the centroids in the energy range from 42 to 147 eV and used to
calibrate that segment. The calibrated segments are summed and fit once again
with a comb of Gaussian functions to more precisely extract the centroid and
width of each laser peak, which are respectively used to measure the energy
linearity and resolution of the system. Specifically, the FWHM of the
Gaussians measures the energy resolution of each STJ pixel as a function of
energy and the Gaussian centroids are used to determine the fit residuals from
a second order polynomial, both of which are shown in Figure 2. In the
calibration range, the NI PXIe-6356 has a mean residual of 5.9 meV rms with a
channel-to-channel variation of $\pm$ 2.5 meV. The MPX-32D has residuals of
9.5 $\pm$ 4.0 meV rms, and the Ortec Aspec 927 has a calibration residual of
only 3.4 meV rms on its single channel. The residuals of the Ortec DAQ are
higher than the 1.6 meV rms it has previously demonstrated [7] due to reduced
statistics and uncertainty in detector drift correction.

The timing accuracy of the NI and XIA DAQs is evaluated by calculating the
measured arrival time differences between nominally simultaneous laser signals
in different pixels, which are shown in Figure 4. As expected for a rising
edge trigger [9], the MPX-32D displays energy walk due to the finite signal
rise time. The energy walk is fit to and corrected using iminuit [8].
Afterwards, pile-up and random coincidence events are removed by rejecting
events with a time difference $>$3$\sigma$, and the standard deviation of the
remaining events from each laser peak is plotted in Figure 4. We observe that
the NI PXIe-6356 can achieve a timing jitter much smaller than its sampling
rate, which is possible because the pulse arrival time is determined using
data from the entire pulse, rather than just a single point on the rising
edge. Its timing jitter is also slightly better than the MPX-32D, despite a 40
times slower sampling rate. That is in part because we chose to trigger using
the long filter on the MPX-32D in order to achieve a lower energy threshold at
the expense of a degraded timing resolution.

Figure 2: One day of calibrated laser energy spectra (top row), energy
resolutions (middle row), and calibration residuals (bottom row) from the NI
PXIe-6356 (left, 16 channels in different colors), XIA MPX-32D (middle, 4
channels) and Ortec Aspec 927 (right). The dotted lines show AWG results.

Figure 3: Time distributions between simultaneous laser events from the NI
(top) and XIA (middle) DAQs in log scale. Channels with different trigger
levels create multiple bands in the middle plot, which are corrected for in
the bottom plot. Events outside the central bands are 7Be events in random
coincidence with laser events.

Figure 4: Comparison of the timing jitter of the NI and XIA DAQs across the
three days of unblinded data (solid lines represent different channels). The
increase at high energies for some channels is due to low statistics and
increased pile-up fraction. Comparison with AWG pulses is shown for both DAQs
(dashed lines), assuming 150 mV/keV.

Finally, an NI PXIe-5423 arbitrary waveform generator (AWG) is connected to
the pre-amplifier input to evaluate the intrinsic energy and timing resolution
of each DAQ using a comb of artificial STJ-like pulses. The same methods as
above were used to extract the energy resolution and timing jitter, which are
compared with the real STJ signals in Figures 2 and 4.

##  4 Discussion and Conclusions

To determine the performance of each DAQ, we evaluated the resolution,
calibration residuals, and timing jitter of each channel using the small set
of unblinded data and AWG tests. First, the DAQ resolution is measured to be
$<$ 1.1 eV for all three digitizers, which meets our requirements and
indicates that the channel-to-channel resolution variations are due to STJ
device differences (Figure 2). Second, both the XIA MPX-32D and the NI
PXIe-6356 meet our timing resolution target of $\sim$1 $\mu$s, with slightly
higher timing jitter only near the trigger threshold outside the energy range
of primary interest (Figure 4, 4). This is particularly impressive for the NI
PXIe-6356, which is able to achieve sub-sample timing resolution because of
the pulse arrival time extraction algorithm. On the other hand, the Ortec
Aspec 927 does not meet the timing or channel number needs for Phase-III,
which limits the types of analysis that can be performed with its data.
Nonetheless, it is still a valuable comparison to the Phase-II DAQ. Third, the
calibration residuals are typically $\lesssim$10 meV rms in the calibration
range and thus well below the 0.1 eV target. In summary, we have demonstrated
that two of the three DAQ setups meet the requirements for Phase-III of the
BeEST experiment, and expect that the ultimate sensitivity for the physics
goals will be limited by other systematic uncertainties.

Still, improvements to the DAQ are highly desirable as we scale up to $>$100
channels for Phase-IV [1]. First, combining the pulse arrival time algorithm
with a faster sampling rate would significantly improve the timing resolution.
That would allow for shorter coincidence windows and improved pile-up
identification, which is critical at increased count rates. Additionally,
capturing waveforms with a faster ADC could enable rise-time analysis to
discriminate between top and bottom electrode events [10]. To mitigate the
increase in data volume from increasing both the sampling rate and number of
channels, an ideal Phase-IV DAQ would save only triggered waveforms. The data
throughput could be further reduced by recording the pre- and post-trigger
sections of each pulse at a slower sampling rate compared to the rising edge.
Furthermore, as we scale to a larger number of detectors, manual per-device
per-cooldown processes need to be minimized. These include optimizing the STJ
bias point, STJ zero, decay time correction, and trigger level. Finally, real-
time monitoring will be necessary to quickly identify poorly performing
devices, and the DAQ control software needs to be robust and error tolerant.

We have collected a wealth of data from the three DAQs and are exploring new
analysis techniques enabled by the multi-channel setup and the continuous DAQ.
This includes pulse shape analysis to extract an experimental pile-up
spectrum, substrate event tagging, and trigger efficiency studies. Using those
techniques and the small set of currently unblinded data, we are in the
process of developing robust analysis tools to project Phase-III’s sensitivity
to sub-MeV neutrinos.

Acknowledgments C. Bray gratefully acknowledges support from the DOE Office of
Science SCGSR program. The BeEST experiment is funded by the Gordon and Betty
Moore Foundation (10.37807/GBMF11571), the DOE-SC Office of Nuclear Physics
(DE-SC0021245, DE-FG02-93ER40789, and SCW1758), and the LLNL LDRD grant
20-LW-006. F. Ponce is supported by PNNL under contract DE-AC05-76RL01830.
TRIUMF receives federal funding via a contribution agreement with the National
Research Council of Canada. The theoretical work was performed as part of the
European EMPIR Projects 17FUN02 MetroMMC and 20FUN09 PrimA-LTD. This work was
performed under the auspices of the U.S. Department of Energy by LLNL under
Contract No. DE-AC52-07NA27344.

## References

  *   * Leach et al. [2022] Leach, K.G., Friedrich, S., BeEST Collaboration: The BeEST Experiment: Searching for Beyond Standard Model Neutrinos Using 7Be Decay in STJs. Journal of Low Temperature Physics 209(5), 796–803 (2022) https://doi.org/10.1007/s10909-022-02759-z
  * Friedrich et al. [2021] Friedrich, S., Kim, G.B., Bray, C., Cantor, R., Dilling, J., Fretwell, S., Hall, J.A., Lennarz, A., Lordi, V., Machule, P., McKeen, D., Mougeot, X., Ponce, F., Ruiz, C., Samanta, A., Warburton, W.K., Leach, K.G.: Limits on the Existence of sub-MeV Sterile Neutrinos from the Decay of ${}^{7}\mathrm{Be}$ in Superconducting Quantum Sensors. Phys. Rev. Lett. 126, 021803 (2021) https://doi.org/10.1103/PhysRevLett.126.021803
  * Warburton et al. [2015] Warburton, W.K., Harris, J.T., Friedrich, S.: High density processing electronics for superconducting tunnel junction x-ray detector arrays. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 784, 236–241 (2015) https://doi.org/10.1016/j.nima.2015.02.004 . Symposium on Radiation Measurements and Applications 2014 (SORMA XV)
  * Ponce et al. [2018] Ponce, F., Swanberg, E., Burke, J., Henderson, R., Friedrich, S.: Accurate measurement of the first excited nuclear state in ${}^{235}\mathrm{U}$. Phys. Rev. C 97, 054310 (2018) https://doi.org/10.1103/PhysRevC.97.054310
  * Fretwell et al. [2020] Fretwell, S., Leach, K.G., Bray, C., Kim, G.B., Dilling, J., Lennarz, A., Mougeot, X., Ponce, F., Ruiz, C., Stackhouse, J., Friedrich, S.: Direct Measurement of the ${}^{7}\mathrm{Be}$ $L/K$ Capture Ratio in Ta-Based Superconducting Tunnel Junctions. Phys. Rev. Lett. 125, 032701 (2020) https://doi.org/10.1103/PhysRevLett.125.032701
  * Friedrich et al. [2022] Friedrich, S., Marino, A., Ponce, F., Carpenter, M.F., Kim, G.-B., Drury, O.B., Drake, J., Bray, C.R., Fretwell, S., Leach, K.G., Harris, J., Warburton, W.K., Hall, J.A., Cantor, R.: Characterization of Non-uniformities in Superconducting Tunnel Junction Radiation Detectors. Journal of Low Temperature Physics 209(5), 1063–1069 (2022) https://doi.org/10.1007/s10909-022-02825-6
  * Friedrich et al. [2020] Friedrich, S., Ponce, F., Hall, J.A., Cantor, R.: Non-linearities in Superconducting Tunnel Junction Radiation Detectors and Their MCA Readout. Journal of Low Temperature Physics 200(5), 200–205 (2020) https://doi.org/10.1007/s10909-020-02360-2
  * Dembinski and et al. [2020] Dembinski, H., al., P.O.: scikit-hep/iminuit (2020) https://doi.org/10.5281/zenodo.3949207
  * Knoll [2000] Knoll, G.F.: Radiation Detection and Measurement, 3rd edn. John Wiley and Sons, New York (2000)
  * Nakamura et al. [2000] Nakamura, T., Kishimoto, M., Katagiri, M., Ohkubo, M., Fukuda, D., Takahashi, H., Nakazawa, M.: Novel improvement method of energy resolution for superconducting tunnel junction X-ray detectors. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 444(1), 11–14 (2000) https://doi.org/10.1016/S0168-9002(99)01317-0


# TSSB-3M: Mining single statement bugs at massive scale

Cedric Richter  Carl von Ossietzky University OldenburgAmmerländer Heerstraße
114-118OldenburgGermany26129<EMAIL_ADDRESS>and  Heike
Wehrheim  Carl von Ossietzky University OldenburgAmmerländer Heerstraße
114-118OldenburgGermany26129<EMAIL_ADDRESS>
(2022)

###### Abstract.

Single statement bugs are one of the most important ingredients in the
evaluation of modern bug detection and automatic program repair methods. By
affecting only a single statement, single statement bugs represent a type of
bug often overlooked by developers, while still being small enough to be
detected and fixed by automatic methods. With the rise of data-driven
automatic repair the availability of single statement bugs at the scale of
millionth of examples is more important than ever; not only for testing these
methods but also for providing sufficient real world examples for training. To
provide access to bug fix datasets of this scale, we are releasing two
datasets called SSB-9M and TSSB-3M. While SSB-9M provides access to a
collection of over 9M general single statement bug fixes from over 500K open
source Python projects , TSSB-3M focuses on over 3M single statement bugs
which can be fixed solely by a single statement change. To facilitate future
research and empirical investigations, we annotated each bug fix with one of
20 single statement bug (SStuB) patterns typical for Python together with a
characterization of the code change as a sequence of AST modifications. Our
initial investigation shows that at least 40% of all single statement bug
fixes mined fit at least one SStuB pattern, and that the majority of 72% of
all bugs can be fixed with the same syntactic modifications as needed for
fixing SStuBs.

Datasets, single statement bugs, Python, open software repositories.

††copyright: acmcopyright††journalyear: 2022††doi:
10.1145/1122445.1122456††conference: MSR ’22: Proceedings of the 19th
International Conference on Mining Software Repositories; May 23–24, 2022;
Pittsburgh, PA, USA††price: 15.00††isbn: 978-1-4503-XXXX-X/18/06

##  1\. Introduction

Software bugs, i.e. unintended behavior introduced by a programmer mistake,
come in many forms ranging from small errors affecting only a single token to
major design flaws requiring complete program rewrites. Especially small bugs
in a single line or statement only can be easily overlooked by a developer.
For this reason and to relieve the developer from the burden of manually
localizing and repairing small, simple bugs, several works have explored
automatic methods for bug identification (Pradel and Chandra, 2022; Richter
and Wehrheim, 2021; Allamanis et al., 2018; Pradel and Sen, 2018; Richter and
Wehrheim, 2022; Hellendoorn et al., 2019) and program repair (Chen et al.,
2019; Tufano et al., 2019; Vasic et al., 2019; Lutellier et al., 2020). While
traditional methods (Sadowski et al., 2015; Ayewah et al., 2008) often rely on
hand-crafted rules to identify potential bugs, recent methods (Pradel and Sen,
2018; Pradel and Chandra, 2022; Vasic et al., 2019) started to explore data-
driven techniques. Such techniques, however, require access to huge databases
of known bugs for training. Collecting single statement bugs at the required
scale is difficult, though, as they only rarely occur in open source projects.
Therefore, existing methods often had to rely on generated pseudo bugs for
producing a sufficient amount of training data.

In this paper, we address the lack of available training examples (for Python)
by releasing two new ultralarge collections of single statement bug fixes. For
this, we mined over 500K Python open source projects for bug-fixing commits
that only change a single statement. By following a mining process similar to
previous work (Karampatsis and Sutton, 2020), we derived a dataset of more
than 9M bug fixes (SSB-9M). Since the collected patches do not always fix the
bug in isolation (e.g. the full patch might require further code edits), we
additionally explored a more restrictive definition of single statement bug
fixes. More precisely, we filtered our dataset for code changes that fully
patch a bug with a single statement change - without modifying source code in
other files or statements in the same file at a different location. This more
restrictive process produced a collection of over 3M ”true” single statement
bugs (TSSB-3M).

To compare the distribution of bugs in our datasets with previous such
collections like PySStuBs for Python (Kamienski et al., 2021), we annotate
each bug fix with one of 20 simple single statement bug (SStuB) patterns. In
total, we find that around 40% of all mined bugs can be assigned to at least
one pattern. To also explore the remaining bugs, we additionally annotate each
bug with an AST edit script. Using four edit operation types, a script
describes how the AST of the buggy code has to be changed to arrive at its
repaired version. Based on the computed edit script, we find that the majority
of single statement bugs (72% of all collected bugs) can be fixed with the
same edit operation needed to fix a SStuB. Still, there exists a small
percentage (2% of all collected bugs) which are not even remotely similar to
bugs matching a SStuB pattern and, hence, require special care when addressed
with automatic repairing methods. We hope that a collection of bug fixes at
this scale can not only facilitate future research in data-driven bug
detection and repairing methods, but can also shed light on what types of
simple single statement bugs developers introduce in code and how they fix
them.

Our datasets and data generation tool are publicly available:

https://cedricrupb.github.io/TSSB3M/

##  2\. Methodology

In the following, we provide a detailed overview over our methodology and the
individual steps necessary for building the datasets.

###  2.1. Identifying Appropriate Python Projects

In order to find suitable repositories for mining single statement bugs we
employ the Libraries.io 1.6 (Katz, 2020) package index. The package index
includes over 2 million references to Python Git repositories which we employ
as a starting point for our mining process. Although mining on popular
projects ensures a well-maintained code base, we intentionally decided against
excluding repositories based on their popularity. We believe that all bug
fixes are equally valuable for gaining insights. Repositories of lower
popularity might provide access to bugs which typically occur during the
development, but would be caught before arriving in a better maintained
project. Furthermore, we also include fork projects since they might provide
access to bugs not occurring in the original project. To avoid commit
duplication, we later remove all duplicate commits. Finally, note that our
datasets do not include commits from all projects listed in the index since
not all projects are publicly accessible or contain a single statement commit.

###  2.2. Mining Single Line Edits

To effectively mine single statement bugs at the scale of millionth of
repositories, we start by determining potential bug candidates with a cheap
approximative process. Instead of identifying single statement bugs directly,
we first crawl the repositories for commits that modify exactly one line per
modified file. During this process, we ignore all changes to the formatting
and comments since they do not alter the program behavior. Checking whether a
commit contains a single line edit can be performed at a textual level without
requiring to parse the complete abstract syntax tree (AST) of the program. In
addition, lines in Python generally correspond to single statements by design.
Even if a statement is defined over multiple lines, we still capture single
statement modifications that are only performed at a single location. However,
we do not capture modifications to a single multi-line statement at multiple
locations. To finally determine whether a commit contains a single line edit,
we compute the difference between the program before and after the patch.
Similar to the Unix diff algorithm, we consider all file modifications as
removing old lines and adding the modified lines. To identify single line
changes, we count how many lines have been modified by comparing removed and
added lines. For the comparison, we tokenize each line and compare the
respective token sequences. By employing a tokenizer111For tokenization, we
employ the tokenize package., we automatically ignore any changes to the code
formatting. In addition, our tokenizer is configured to ignore all changes to
comments since they do not alter the program behavior. Finally, we store all
commits that modify exactly one line together with all computed file
differences.

For the mining process, the workload is distributed on a cluster of over 1000
workers. Each worker iteratively clones the assigned projects and searches
through the commit history for single line commits. During this process, we
ignore all commits that either add or remove complete files, since we are only
interested in single code changes. The complete mining process took around two
weeks and produced a total of over 66M single line edits from more than 500K
git projects.

###  2.3. Selecting Single Statement Changes

After collecting single line edits from thousands of projects, we were
interested in finding all single statement changes. For this, we iterate over
all collected commits, while analyzing the previously stored file difference
for single statement changes. We exclude all commits that (1) are duplicates
introduced by fork projects, (2) do not contain a full parsable statement or
(3) change multiple statements in a single line. For identifying whether a
commit changes a statement, we compute the AST for the file difference. It
usually contains changed lines in addition to some context code lines.
Although the code in a file difference is generally not enough to build the
full AST, it is enough for the purpose of single statement change
identification. We employ a best-effort AST parser222To parse partial code, we
employ the tree-sitter library. to compute the two ASTs for the code line
before and after the fix. To locate the difference in the AST representation,
we perform a simultaneous depth-first search, similar to Kampastsis and Sutton
(Karampatsis and Sutton, 2020), until we find the first node where the two
ASTs differ. We exclude all commits where the computed AST node is not located
inside a statement or is a root for multiple statements.

After filtering, we now remain with over 28M single statement changes from
over 460K Git projects. Note that already by deduplication the size of the
dataset nearly halves to over 33M single line edits. Since we believe that
this dataset of single statement changes can be valuable for future research
on the evolution of software projects, we publish it under the name SSC-28M.
However, our main focus is still on the study of real single statement bugs.

###  2.4. Identifying True Single Statement Bugs

In this work, we consider two types of bug-fixing commits: Single Statement
Bugs, which are obtained following the procedure of previous works, and True
Single Statement Bugs, which are determined with a more restrictive but also
more precise selection procedure. First of all, to determine whether a commit
is bug-fixing, we check its commit message for the occurrence of at least one
of the following keywords: ‘error’, ‘bug’, ‘fix’, ‘issue’, ‘mistake’,
‘incorrect’, ‘fault’, ‘defect’, ‘flaw’, and ‘type’. This heuristics was
repeatedly shown to be highly precise (Karampatsis and Sutton, 2020; Tufano et
al., 2019; Chen et al., 2019; Kamienski et al., 2021) (with an accuracy of at
least 90%). In addition, this is a common procedure to filter for bug-fixing
commits when the created datasets are too large to be manually inspected
(Karampatsis and Sutton, 2020; Tufano et al., 2019).

While this heuristics is effective to identify bug-fixing commits, it assumes
that commit message and code change are related. However, as shown by prior
work (Herzig and Zeller, 2013), a significant portion of bug fixing commits
are entangled commits and, hence, change more code than it is necessary to fix
a bug. Therefore, as soon as we look at the commit not as a whole, but only a
part of it (in our case a single statement change), we risk that the change is
unrelated to the bug fix. This motivates our second bug category of True
Single Statement Bugs (TSSBs). TSSBs refer to bug fixing commits that fully
patch a bug with exactly one single statement change. This is not only a
helpful property for the evaluation of bug detection methods333A common
assumption in the evaluation of bug detection methods is that the code before
the patch is buggy and correct after the patch. This is generally not true for
commits belonging to traditional single statement bugs., but also avoids
entangled commits by definition. In addition, we do not apply commit unrolling
(Karampatsis and Sutton, 2020; Kamienski et al., 2021), which would split a
single bug-fixing commit into multiple partial fixes. Now, after filtering the
dataset for single statement bugs and true single statement bugs, we obtain
two datasets SSB-9M and TSSB-3M, which contain over 9M and 3M bug fixes,
respectively.

###  2.5. Characterizing Bug Patching Edits

For analyzing the types of bugs collected in our datasets, we employ two ways
for characterizing a bug fix: (1) SStuB patterns and (2) AST Edits. SStuB
patterns (Karampatsis and Sutton, 2020) are used to categorize bug fixes into
frequently occurring bug type categories like changes in the usage of function
names or binary operators. To categorize the collected bug fixes, we assign
each commit to a unique bug pattern. Similar to (Kamienski et al., 2021), we
assign each bug to the most specific category when it is matched by more than
one SStuB pattern. In general, we distinguish 20 typical SStuB patterns as
identified for Python and described by previous work (Kamienski et al., 2021).
If a commit does not fit a bug pattern, we assign it to a generic single
statement pattern or single token pattern (when the commit only modifies a
single token). In total, we found 50% to 60% of all instances in our datasets
to not fit a single SStuB pattern.

To better characterize how developers make single statement mistakes, we
further analyze the AST edits between the code before and after the code
change. An AST edit script (Falleri et al., 2014) describes how the AST of the
buggy code has to be transformed to arrive at its fixed version. Every edit
script consists of four types of AST operations: INSERT (inserting a new AST
node at a given location), MOVE (moving an existing AST node to another
position in the same AST), UPDATE (updating the value of a single node) and
DELETE (removing a single node). For computing the AST difference, we employ
the same two ASTs employed to filter the datasets and computed from the file
difference. Then, we compute for each bug patch an AST edit script by
employing a reimplementation of the GumTree algorithm (Falleri et al., 2014).
By characterizing a bug patch through an AST edit script, we are able to
analyze which operations have to be supported by a bug repairing method to fix
a given bug. Overall, we found that single statement bugs can be fixed on
average with 4.20 AST operations in SSB-9M and 4.52 AST operations in TSSB-3M.

###  2.6. Datasets

As a result of our mining process, we are releasing three new datasets: (1)
TSSB-3M, a dataset of over 3M isolated single statement bug fixes, (2) SSB-9M,
a dataset of over 9M general single statement bugs and (3) SSC-28M, a dataset
of over 28M general single statement changes. Our intention is to facilitate
future research on large scale datasets in software evolution, data-driven bug
detection or repair. All collected datasets are novel and were not used in
previous studies. To store millionth of bug fixes, all mined data is stored in
a compressed jsonlines444https://jsonlines.org format. Every dataset entry
contains information about (1) the project and commit hash of the bug fix, (2)
the file difference as a Unix diff between the code before the change and
after and (3) additional analytical results such as the identified SStuB
pattern and AST edit script. Because of concerns regarding licensing, we
cannot redistribute the complete code related to a bug fix. However, source
code is available in the original projects and can be referenced via our
datasets. All released datasets are publicly available on
Zenodo555https://doi.org/10.5281/zenodo.5845439 and our tool for generating
the datasets can be found on Github666https://github.com/cedricrupb/TSSB3M and
Zenodo777https://doi.org/10.5281/zenodo.5898547.

##  3\. Analysis of Datasets

Our main contribution is a collection of bugs a magnitude larger than any
existing bug dataset. Nevertheless, we also explored the datasets to gain new
insights into developer bugs and their fixes. Specifically, we were interested
in the following two questions:

RQ1:

Do we find the same distribution of SStuBs in our datasets as in previously
collected datasets?

RQ2:

How different are general single statement bugs from those selected by SStuB
patterns?

Table 1. SStub pattern statistics for SSB-9M, TSSB-3M and PySStuBs

SStuB Pattern TSSB-3M SSB-9M PySStuBs (Kamienski et al., 2021) Count % Count %
Count % Change Identifier Used 237K 16 659K 18 9K 12 Change Binary Operand
174K 12 349K 9 4K 6 Same Function More Args 150K 10 457K 12 10K 14 Wrong
Function Name 134K 9 397K 11 9K 12 Add Function Around Expression 117K 8 244K
6 6K 9 Change Attribute Used 104K 7 285K 8 5K 7 Change Numeric Literal 97K 6
275K 7 5K 7 More Specific If 68K 5 121K 3 2K 3 Add Method Call 60K 4 118K 3 3K
5 Add Elements To Iterable 57K 4 175K 5 2.5K 3 Same Function Less Args 50K 3
169K 4 3.4K 5 Change Boolean Literal 37K 3 82K 2 1.5K 2 Add Attribute Access
32K 2 74K 2 1.5K 2 Change Binary Operator 29K 2 71K 2 ¡1K 1 Same Function
Wrong Caller 25K 2 46K 1 1.2K 2 Less Specific If 22K 2 45K 1 ¡1K 1 Change
Keyword Argument Used 20K 1 59K 2 1.5K 2 Change Unary Operator 15K 1 23K ¡1 2K
3 Same Function Swap Args 8K ¡1 77K 2 ¡1K 1 Change Constant Type 6K ¡1 12K ¡1
2K 3 NoSStuB - Single Statement 1.15M - 3.37M - - - NoSStuB - Single Token
740K - 2.20M - - - Total SStubs 1.46M 100 3.74M 100 73K 100 Total 3.34M -
9.34M - - -

RQ1. We measure the frequency of SStuBs in datasets TSSB-3M, SSB-9M and a
previously explored Python SStuB dataset called PySStuBs (Kamienski et al.,
2021). The number of occurrences of each pattern in each dataset is given in
Table 1. In general, we find that the distribution of SStuBs changes between
datasets while the ranking of pattern frequencies is highly correlated (with a
Spearman rank correlation of $0.94$ between TSSB-3M and SSB-9M and $0.86$
between TSSB-3M and PySStuBs). In particular, we observe that patterns such as
Change Identifier Used and Same Function More Args are highly frequent in all
datasets. Interestingly enough, some bug categories such as Change Binary
Operand become more dominant in the TSSB-3M dataset. This could indicate that
these types of bugs are harder to identify by a developer and, hence, are more
likely to be fixed after the main development phase in an independent fix.
Finally, we find that only 40% - 43% of all Python single statement bugs fit a
SStuB pattern. While this finding is inline with previous observations on Java
SStuBs (Karampatsis and Sutton, 2020), we are interested in the types of bugs
occurring in the remaining dataset which is what we study in RQ2.

SStuB-alikeSStuB-relatedSStuB-unrelated

Figure 1.  Similarity of NonSStuBs with SStuBs given as the Jaccard distance
between edit operations. The x-axis corresponds to the binned distance to the
most similar SStuB bug and the y-axis corresponds to observed frequencies.

RQ2. We measure the similarity between single statement bugs that do not fit a
SStuB pattern (NonSStuBs) and those that classify as a SStuB in the TSSB-3M
dataset. The similarity between bug types is computed by the Jaccard distance
(Jaccard, 1901) between the edit scripts of the respective bug fixes.
Therefore, two bug fixes are similar if they share the same edit
operations888Instead of the concrete edit operation that is highly specific to
the modified AST we employ the type of an edit operation composed of operation
name and types of its arguments. For example, the type of an operation that
adds a binary operator to an assignment is Insert(binary_op, assign).. For the
comparison, we always look at the minimal distances between NonSStuB and SStuB
pairs. Figure 1 report on the distribution of computed distances. The distance
allows us to categorize NonSStuB bugs into three classes: SStuB-alike
(distance of $0$), SStuB-related (distance of around $0.5$) and SStuB-
unrelated (distance of $1$). We find that SStuBs + SStuB-alike bugs populate
around 72% of the dataset and can therefore be repaired by the same edit
operations. Another frequent class are SStub-related bugs, which are related
to existing SStuB patterns but do not classify as a SStuB. For example, bug
fixes that operate on inline if-conditions. While being if statement related,
they are not covered by any actual SStuB pattern. Finally, we find that around
2% of all bugs (SStuB-unrelated) are completely unrelated to any SStuB
pattern. Those types of bugs are often highly related to the specifies of the
Python language. For example, we observed that developers commonly forget to
add the implicit self argument to a Python method. The fact that this class of
bugs has, however, a low frequency is quite promising for the research on bug
detection and repairing methods: Methods that supports the detection and
repair of SStuBs are also likely well suited to identify and fix a wide range
of the most common single statement bug types.

##  4\. Related Work

Single statement bugs, especially SStuBs, were explored in previous works, not
only as a data source (Karampatsis and Sutton, 2020; Kamienski et al., 2021;
Beyer et al., 2021) but also for methods that can detect and prevent this
simpler type of bugs (Tufano et al., 2019; Chen et al., 2019; Mashhadi and
Hemmati, 2021; Lutellier et al., 2020). Karampatsis and Sutton (Karampatsis
and Sutton, 2020) collected around 63 thousand Java single statement bugs from
1000 popular projects that fit at least one of 16 SStuB categories. They found
out that around 33% of all mined bugs can be classified as a SStuB. Kamienski
et al. (Kamienski et al., 2021) explored similar types of bug fixes for the
1000 most popular Python projects999Since our dataset mining is more recent
and some of the projects mined in PySStuBs might not be public any longer, our
datasets are not necessarily supersets of PySStuBs. while introducing 7 new
SStuB patterns typical for Python. Their collection of bugs is of similar size
with around 73 thousand examples. Similar to Kamienski et al. we also explored
bugs that fit SStuB patterns in Python. However, our mining process allowed us
to go beyond the most popular Python projects, which resulted in a dataset
more than 20x larger than all existing SStuB collections. In addition and in
contrast to previous bug collections, we also analyze edit operations needed
to fix a bug. Therefore, we were able to explore bug types that are not
covered by SStuB patterns. With the objective of machine-learning based
program repair for single line bugs, Tufano et al. (Tufano et al., 2019)
collected a set of 787 thousand bug-fixing single line commits in Java. They
used the same heuristics we employed for identifying bug-fixing code changes.
In addition, their method is trained to translate buggy code lines into its
fixed version. Finally, Bader et al. (Bader et al., 2019) showed that AST edit
scripts can be effectively employed for automatic program repair by predicting
bug fixes based on previously seen AST transformations. Not only does our
dataset provide more than 11x more training data (SSB-9M), which has the
potential to improve the performance of existing methods (Halevy et al., 2009;
Sun et al., 2017), but also by annotating each bug fix with an AST script our
dataset can directly be employed in various training setups.

##  5\. Limitations - Threats to validity

Even though the employed heuristics for identifying bug fixing commits has
been repeatedly shown to be highly precise, there is still a chance for false
positives in our datasets. To mitigate this problem, we have designed our
mining process to be as precise as possible by avoiding commit unrolls and by
filtering for isolated bug fixes in TSSB-3M. The latter not only guarantees
that the causal relationship between commit message indicating a bug fix and
code change persists, but also avoids the mining of entangled code changes.
While we mined a large portion of all available open source projects, we were
restricted to projects accessible to the public. The distribution of simple
bugs in closed source projects or projects without version control might be
different. Finally, while the mining process is general enough to be applied
to other languages, our datasets are restricted to single statement bugs in
Python. The concrete instantiations and frequency of bugs might vary for other
programming languages and projects.

##  6\. Conclusion

In this work, we explored a new mining process for single statement bugs which
enabled us to crawl through the commits of more than 500K public git
repositories. As a result of our mining process, we are releasing two new
datasets of single statement bug fixes that are a magnitude larger than any
existing collection of bug fixes. More precisely, we introduce SSB-9M, a
dataset consisting of over 9M single statement changes in Python, as well as
the 3M bug fix dataset TSSB-3M. TSSB-3M guarantees that every collected bug
can be fixed by modifying only a single statement. We hope that datasets of
this size will facilitate future research in data-driven bug detection and
automatic program repair.

###### Acknowledgements.

The authors gratefully acknowledge the funding of this project by computing
time provided by the Paderborn Center for Parallel Computing (PC²).

## References

  * (1)
  * Allamanis et al. (2018) Miltiadis Allamanis, Marc Brockschmidt, and Mahmoud Khademi. 2018\.  Learning to Represent Programs with Graphs. In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_. OpenReview.net.  https://openreview.net/forum?id=BJOFETxR-
  * Ayewah et al. (2008) Nathaniel Ayewah, William Pugh, David Hovemeyer, J David Morgenthaler, and John Penix. 2008\.  Using static analysis to find bugs.  _IEEE software_ 25, 5 (2008), 22–29.
  * Bader et al. (2019) Johannes Bader, Andrew Scott, Michael Pradel, and Satish Chandra. 2019.  Getafix: Learning to fix bugs automatically.  _Proceedings of the ACM on Programming Languages_ 3, OOPSLA (2019), 1–27.
  * Beyer et al. (2021) Dirk Beyer, Lars Grunske, Thomas Lemberger, and Minxing Tang. 2021\.  Towards a Benchmark Set for Program Repair Based on Partial Fixes.  _CoRR_ abs/2107.08038 (2021).  arXiv:2107.08038 https://arxiv.org/abs/2107.08038
  * Brill and Moore (2000) Eric Brill and Robert C. Moore. 2000.  An Improved Error Model for Noisy Channel Spelling Correction. In _Proceedings of the 38th Annual Meeting on Association for Computational Linguistics_ (Hong Kong) _(ACL ’00)_. Association for Computational Linguistics, USA, 286–293.  https://doi.org/10.3115/1075218.1075255
  * Chen et al. (2019) Zimin Chen, Steve James Kommrusch, Michele Tufano, Louis-Noël Pouchet, Denys Poshyvanyk, and Martin Monperrus. 2019.  Sequencer: Sequence-to-sequence learning for end-to-end program repair.  _IEEE Transactions on Software Engineering_ (2019).
  * Falleri et al. (2014) Jean-Rémy Falleri, Floréal Morandat, Xavier Blanc, Matias Martinez, and Martin Monperrus. 2014\.  Fine-grained and accurate source code differencing. In _ACM/IEEE International Conference on Automated Software Engineering, ASE ’14, Vasteras, Sweden - September 15 - 19, 2014_. 313–324.  https://doi.org/10.1145/2642937.2642982
  * Gu et al. (2016) Jiatao Gu, Zhengdong Lu, Hang Li, and Victor OK Li. 2016\.  Incorporating copying mechanism in sequence-to-sequence learning.  _arXiv preprint arXiv:1603.06393_ (2016).
  * Halevy et al. (2009) Alon Halevy, Peter Norvig, and Fernando Pereira. 2009\.  The unreasonable effectiveness of data.  _IEEE Intelligent Systems_ 24, 2 (2009), 8–12.
  * Hellendoorn et al. (2019) Vincent J Hellendoorn, Charles Sutton, Rishabh Singh, Petros Maniatis, and David Bieber. 2019\.  Global relational models of source code. In _International conference on learning representations_.
  * Herzig and Zeller (2013) Kim Herzig and Andreas Zeller. 2013.  The impact of tangled code changes. In _2013 10th Working Conference on Mining Software Repositories (MSR)_. IEEE, 121–130.
  * Jaccard (1901) Paul Jaccard. 1901\.  Étude comparative de la distribution florale dans une portion des Alpes et des Jura.  _Bull Soc Vaudoise Sci Nat_ 37 (1901), 547–579.
  * Kamienski et al. (2021) Arthur V Kamienski, Luisa Palechor, Cor-Paul Bezemer, and Abram Hindle. 2021.  PySStuBs: Characterizing Single-Statement Bugs in Popular Open-Source Python Projects. In _2021 IEEE/ACM 18th International Conference on Mining Software Repositories (MSR)_. IEEE, 520–524.
  * Karampatsis and Sutton (2020) Rafael-Michael Karampatsis and Charles Sutton. 2020.  How often do single-statement bugs occur? the manysstubs4j dataset. In _Proceedings of the 17th International Conference on Mining Software Repositories_. 573–577.
  * Katz (2020) Jeremy Katz. 2020\.  Libraries.io Open Source Repository and Dependency Metadata.  https://doi.org/10.5281/zenodo.3626071
  * Lutellier et al. (2020) Thibaud Lutellier, Hung Viet Pham, Lawrence Pang, Yitong Li, Moshi Wei, and Lin Tan. 2020.  Coconut: combining context-aware neural translation models using ensemble for program repair. In _Proceedings of the 29th ACM SIGSOFT international symposium on software testing and analysis_. 101–114.
  * Mashhadi and Hemmati (2021) Ehsan Mashhadi and Hadi Hemmati. 2021.  Applying CodeBERT for Automated Program Repair of Java Simple Bugs. In _18th IEEE/ACM International Conference on Mining Software Repositories, MSR 2021, Madrid, Spain, May 17-19, 2021_. IEEE, 505–509.  https://doi.org/10.1109/MSR52588.2021.00063
  * Pradel and Chandra (2022) Michael Pradel and Satish Chandra. 2022.  Neural software analysis.  _Commun. ACM_ 65, 1 (2022), 86–96.  https://doi.org/10.1145/3460348
  * Pradel and Sen (2018) Michael Pradel and Koushik Sen. 2018.  Deepbugs: A learning approach to name-based bug detection.  _Proceedings of the ACM on Programming Languages_ 2, OOPSLA (2018), 1–25.
  * Richter and Wehrheim (2021) Cedric Richter and Heike Wehrheim. 2021.  DeepMutants: Training neural bug detectors with contextual mutations.  _arXiv preprint arXiv:2107.06657_ (2021).
  * Richter and Wehrheim (2022) Cedric Richter and Heike Wehrheim. 2022.  Learning Realistic Mutations: Bug Creation for Neural Bug Detectors.  _15th IEEE International Conference on Software Testing, Verification and Validation_ (2022), to be published.
  * Sadowski et al. (2015) Caitlin Sadowski, Jeffrey Van Gogh, Ciera Jaspan, Emma Soderberg, and Collin Winter. 2015.  Tricorder: Building a program analysis ecosystem. In _2015 IEEE/ACM 37th IEEE International Conference on Software Engineering_ , Vol. 1. IEEE, 598–608.
  * Sun et al. (2017) Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta. 2017.  Revisiting unreasonable effectiveness of data in deep learning era. In _Proceedings of the IEEE international conference on computer vision_. 843–852.
  * Tufano et al. (2019) Michele Tufano, Cody Watson, Gabriele Bavota, Massimiliano Di Penta, Martin White, and Denys Poshyvanyk. 2019.  An empirical study on learning bug-fixing patches in the wild via neural machine translation.  _ACM Transactions on Software Engineering and Methodology (TOSEM)_ 28, 4 (2019), 1–29.
  * Vasic et al. (2019) Marko Vasic, Aditya Kanade, Petros Maniatis, David Bieber, and Rishabh Singh. 2019.  Neural Program Repair by Jointly Learning to Localize and Repair.  _CoRR_ abs/1904.01720 (2019).  arXiv:1904.01720 http://arxiv.org/abs/1904.01720

##  Appendix A Statistics of single statement bugs

Using the AST edit scripts computed for each single statement bug, we aim to
provide some further insights what is really needed to fix a single statement
bug. For this, we answer the following research questions.

###  A.1. How many AST edit operations are typically needed to fix a single
statement bug?

Figure 2. Single statement bugs can be typically repaired with only a few AST
edit operations. However, there exists bugs with much larger edit scripts. The
largest one employs 3708 operations which we exclude in the histogram for
brevity. The x-axis corresponds to the binned number of AST operations needed
to fix a single statement bug computed on the TSSB-3M dataset.

Fixing bugs with a short AST edit script is typically easier. These changes
only modify simple structures of the buggy code and do not require to
introduce completely new structures. Therefore, we are interested how the AST
edit scripts with varying lengths are distributed. To give an insight, we
compute the length of all AST edit scripts, which is depicted in the histogram
in Figure 2. Overall, we find that the distribution of AST edit script lengths
follow the Zipf law. In other words, single statement bugs that can be fixed
with only a few edit operations are much more common than scripts which
require a large set of operations. This is promising for the field of
automatic repair since researcher can focus on edits to programs that rather
small while still covering a large portion of possible single statement bug
fixes.

###  A.2. What types of AST edit operations are needed to successfully repair
a single statement bug?

Table 2. Typical AST edit operations needed to fix a single statement bug

Frequency Insert…(1.55M) 441K identifier into new attribute (self._
$\rightarrow$ self.a) 414K argument list into call (f() $\rightarrow$ f(x))
148K new boolean operator (if ... $\rightarrow$ if ... and ...) 147K new
comparison operator (if ... $\rightarrow$ if ... <= ...) 123K string into
argument list (f(x) $\rightarrow$ f(x, "arg")) Frequency Move…(1.25M) 172K
identifier to a new attribute (self._ $\rightarrow$ self.a) 109K identifier to
argument list (f(x) $\rightarrow$ f(x, y)) 52K comparison to boolean operator
(x < 1 $\rightarrow$ x < 1 and ...) 48K call to argument list (f(x)
$\rightarrow$ g(f(x))) 42K attribute to new attribute (a.b $\rightarrow$
a.b.c) Frequency Update…(1.75M) 845K string 811K identifier 100K integer 14K
floating point number 570 binary operator Frequency Delete…(848K) 364K
identifier 187K binary operator 163K attribute 139K string 110K call

Automatic program repair (APR) methods often are either tailored to perform
certain code change operation or are more likely to perform certain code
transformations. Therefore to guide future research, we investigate which edit
operations are most likely to be needed to fix a single statement bug. Our
results are summarized in Table 2. We summarize the frequency of each edit
type (Insert, Move, Update, Delete) together with top 5 most frequent abstract
operation types (see Section 3) in Table 2. Before we start interpreting this
statistics, note that every type of operation relate to certain feature
supported by the APR technique. The most simplest is the Update operation,
which only requires to map each token to the same or a new update token in a
program. Insert operations require to map a shorter token sequence to a longer
one and Delete requires to do the inverse. While a Move operation can be
represented as an Insert and Delete, the occurrence of Move operation can
motivate the use of a copy mechanism (Gu et al., 2016) which copy some tokens
from one location to another. If we now look at the statistics in Table 2, we
will find that operations that modify or extend the buggy program are much
more common than Delete operations. This indicates that a single statement bug
fix typically adds something to a program to fix a given bug. Interestingly
enough, Update operations have the highest frequency in the dataset. However,
we have to note that Update operations are dominated by changes to strings.
For a string fix, it is not always clear whether it really changes the program
behavior or has just a documenting function. This is in particular true when
the fix changes a docstring which is still counted as a string token in
Python. Therefore, by ignoring string fixes, we observe that most operations
modify function and method calls (e.g. ”Insert argument list into call” or
”Move identifier to attribute”). This is inline with our observation in
Section 3 that the most frequent SStuBs address modifications of function
calls. Finally, to successfully repair a single statement bug, APR method
should focus on operations that modify tokens directly or extend program.
Based on the high frequency of Move operations, a copy mechanism can be a
useful addition to an existing APR method. Fixing errors that are related to
function calls are most helpful for a developer since they are most frequent
bug fixes.

###  A.3. How frequently do single statement bug fixes fix typos?

Table 3. Percentage of single statement bugs that potentially occur due to a
typo.

Commit type TSSB-3M SSB-9M All single statement bugs 22.84% 22.65% Change
identifier used 30.50% 26.94% Change string used 42.10% 45.19%

An initial investigation revealed that single statement bugs occurring due to
a programmer typo are rather common (i.e. the developer forgets a bracket or
misspelled an identifier). Therefore, we are interested how frequent single
statement bugs occur due to typos. For this, we assume that commits that
modify not more than two characters (by inserting, removing, changing or
transposing) represent a typo fix. To compute the number of text changes, we
therefore employ the Damerau-Levenshtein edit distance (Brill and Moore, 2000)
between the code before and after the fix and count all changes with an edit
distance smaller equal 2. Our results for TSSB-3M and SSB-9M are presented in
Table 3. We compute the percentage of single statement bugs per dataset that
are considered to be a typo according to our heuristic. Additionally, we
compute the same metric for all single statement bugs that only change a
single identifier or string (since these are the most common single token
fixes). To avoid counting single identifier fixes that completely replaces the
identifier within two edit operations, we only count identifier that are at
least 3 characters long. We apply the same rule for string fixes. In total, we
found that typos are rather common which occur in at least 20% of all our
datasets. If we view only single identifier or string changes, the percentage
even increases to over 30% and over 40% respectively. This indicates that are
large portion of the single statement bug datasets are in fact likely related
to typos. Therefore, it could be interesting direction for future research to
explore APR methods that employ classical spelling correction techniques.


# Relationship between Number of Subjects and Biometric Authentication Equal
Error Rates

Lee Friedman
Department of Computer Science
Texas State University
San Marcos, Texas, USA, 78666
<EMAIL_ADDRESS>
&Hal S Stern
Department of Statistics
University of California - Irvin
Irvine, California, USA, 92697
<EMAIL_ADDRESS>
&Vladyslav Prokopenko
Department of Computer Science
Texas State University
San Marcos, Texas, USA, 78666
<EMAIL_ADDRESS>
&Oleg V. Komogortsev
Department of Computer Science
Texas State University
San Marcos, Texas, USA, 78666
<EMAIL_ADDRESS>

###### Abstract

The relationship between the number of subjects included in a biometric
authentication study and biometric performance assesed with equal error rate
(EER) is not well studied. In the present paper, we use both synthetic and
real data to study this relationship. Although we and others had hypothesized
that more information would be required to authenticate more subjects at a
given EER, our report does not support this hypothesis, with rare exception.
With synthetic data sets of N = 1,000, N= 10,000 and N = 100,000 we found
remarkably similar (and specifically not statistically different) EERs. In a
real face recognition data set, with data subsets of N = 1,000 subjects and N
= 10,000 subjects, we also found very similar EERs. Our evidence indicates
that EER does not change as a function of number of subjects, at least in the
range of subject numbers studied herein.

_K_ eywords number of subjects, biometric performance, synthetic data sets

##  1 Introduction

As a general matter, several authors consider that there is an influence of
number of subjects on biometric performance. Jain [5] has stated: "… that the
accuracy estimates of biometric systems are dependent on a number of test
conditions, including sensor characteristics, number of subjects in the
database,…". No specific examples are cited in this reference however.
Similarly, Chan et al. [2] state "…as the number of subjects increases, it
becomes increasingly difficult for the system to accurately classify users."
In this case as well, no citations supporting this statement are provided.

Jain [6] discuss numerous approaches to the evalation of biometric
performance. Two common approaches that our laboratory employs are the equal
error rate (EER) and the rank-1 identification rate. There is evidence that
the rank-1 identification rate decreases with increasing numbers of subjects
in biometric data sets [10, 7]. In the conduct of the present research,
although we did not formally study it, we also noted a marked decline in
Rank-1 identification rates as a function of the number of subjects in a data
set.

However, there is little published research on the impact of increasing
numbers of subjects on the EER. Although it is well established that
increasing the number of subjects will decrease the confidence limits on any
ROC curves produced [3], this evidence does not imply anything about the
central tendency of any estimated error rate.

Two earlier papers from out laboratory have addressed the relationship between
number of subjects in a database and EER [10, 7]. In these studies, biometric
authentication was performed using various eye movement features. The goal was
to authenticate subjects tested on two occasions. The total sample was either
200 [10] or 335 subjects [7]. For the purpose of evaluating "Database Scaling
Performance", the ROC analysis was repeated for randomly drawn subsets of
subjects (N=50 to 200 or 335). The authors report that "there was no
discernable difference in equal error rates produced for a subject pool of 50
or a subject pool of 323".

We were interested in in evaluating the influence of changes in numbers of
subjects on a much larger scale (N = 1,000, 10,000 and 100,000 subjects). For
reasons of convenience and availability, we relied in large part on synthetic
data sets. However, we were able to replicate our key finding with a real
face-recognition data set [9]

In the second section of the manuscript. we present a method for creating
synthetic data sets with a number of properties that are helpful for studying
biometric performance. Because the data are synthetic, we are able to control
the degree of temporal persistence of the features while also ensuring that
features are approximately independent of each other and thus provide unique
pieces of information for biometric verification. (The concept of "temporal
persistence" and the method for its measurement are covered in [4]. In other
contexts, this measure is used to assess the inter-rater reliability of a
feature.) We think that having unique pieces of information will allow us to
address several theoretical notions relevant to biometric analysis in this and
subsequent studies. Also in the second section, we present our methods for
biometric assessment. In the third section we present Experiment 1, a study
designed to determine the number of features required to get essentially
perfect performance (EER <= 0.0001). In the fourth section (Experiment 2), we
evaluate the EERs as a function of number of features and temporal persistence
of the features. In the fifth section (Experiment 3), we use real data to
achieve the same goal as section four. Our discussion is then presented.

##  2 Creation and Analysis of Synthetic data sets

###  2.1 Creation of Synthetic Data

Recall that the intraclass correlation coefficient (ICC) is a measure of the
correlation expected for repeated measurements of the same feature on
different occasions. Unlike the Pearson r correlation coefficient, which is
typically applied as an interclass measure of relative agreement (i.e., two
series can be correlated even if they differ substantially in level and
spread), the ICC is an intraclass measure of absolute agreement [4]. Measures
from the same set of subjects at two different times are intraclass
measurements (same metric and variance). ICC ranges from 0.0 to 1.0 with the
latter corresponding to perfect temporal persistence. Our goal is to create
synthetic features with a specified target ICC (denoted $ICC_{Target}$). Let
$X_{ijm}$ denote the measurement of feature $j$ ($j=1,\dotsc,k$) on session
(occasion) $m$ ($m=1,\dotsc,s$) for individual $i$ ($i=1,\dotsc,n$). Although
the ICC can be calculated based on many sessions, in our experience, biometric
assessment is typically performed comparing only two points in time.
Therefore, henceforth we will set $s=2$. We generate normally distributed
features such that the theoretical intraclass correlation of repeated
measurements of the same feature on the same subject is $ICC_{Target}$ while
the theoretical correlation of measurements of different features on the same
individual and the theoretical correlation of measurements from different
individuals are zero. In practice when data are simulated there are small
variations in the empirical ICCs and there are small intercorrelations between
features (and individuals) due to chance.

The algorithm that we use is described briefly here and spelled out in
Algorithm 1. The starting point is to populate the full set of session one
measurements $X_{ij1}$ values with random draws from a standard normal
distribution (mean zero and variance one). Then the measurements for the
second session are set equal to the value of the given feature from the first
session, $X_{ij2}=X_{ij1}$ for ($i=1,\dotsc,n$). At this point both sessions
have the same data and each feature has ICC equal to one (perfect
persistence). We obtain the desired ICC by adding a draw from a normal
distribution with $\text{mean}=0$ and
$\text{variance}=(1-ICC_{Target})/ICC_{Target}$ to each of the measurements.
At the end we apply a z-score transform to each feature (with all sessions
concatenated together) so that they all have mean 0 and standard deviation
one. It can be shown that the resulting measurements have the desired ICC (up
to simulation noise). R code to create such synthetic data sets and to assess
the resulting ICC is presented publicly available at Link to R code and
associated output

Input : $n$ (subjects), $k$ (features), $ICC_{Target}$

Output : 3-dimensional feature matrix $X_{ijm}$ with desired correlation
structure

  1. 1.

Set $X_{ij1}=Z$ where $Z$ is a random standard normal deviate for
$i=1,\dotsc,n$; $j=1,\dotsc,k$

  2. 2.

Set $X_{ij2}=X_{ij1}$ for $i=1,\dotsc,n$; $j=1,\dotsc,k$

  3. 3.

Set $X_{ijm}=X_{ijm}+W$ for $i=1,\dotsc,n$; $j=1,\dotsc,k$; $m=1,2$; where $W$
is a random

normal deviate with mean = 0 and standard deviation =
$\sqrt{(1-ICC_{Target})/ICC_{Target}}$

* 4.

For each feature $j$, treat $X_{ijm}$ as a single vector of length $n\cdot s$
and apply a z-score

transform to ensure mean = 0 and standard deviation = 1

Algorithm 1 Algorithm to create synthetic feature sets

Using this method, we can create features which are normally distributed, that
have specified ICCs, with as many subjects and sessions as we desire. These
features all have mean = 0 and SD = 1. These features are generally
independent, but there are some small intercorrelations between features due
to chance. To illustrate the approach, we generated data for 10000 subjects,
1000 features and 2 occasions with $ICC_{Target}=0.7$. Figure 1(A) shows a
histogram of the resulting empirical ICCs. Figure 1(B) shows a histogram of
the resulting inter-feature correlations.

Figure 1: (A) Frequency histogram of ICCs for 1,000 features with an
$ICC_{Target}=0.7$. This is from a synthetic data set with 10,000 subjects.
(B) Frequency histogram of correlations between 1,000 features for 10,000
subjects, two sessions, with an $ICC_{Target}=0.7$. Note that the median and
maximum are of the absolute value of the correlations.

###  2.2 Creation of Synthetic Sets of Features for (Experiment 1)

To study the number of features required to get essentially perfect
performance, we generate a synthetic data set with ICCs in the range of 0.8 to
0.9, 500 features, 100,000 subjects and two sessions.

###  2.3 Creation of Synthetic Sets of Features for (Experiment 2)

To study the EERs resulting from a given number of features across multiple
ICC Bands, we create 7 different data sets with each data set consisting of 50
features and 100,000 subjects tested twice. The features in each data set have
ICC values that vary over a small interval (e.g. 0.6 to 0.7). We denote the
data sets as “Bands” to indicate that they cover different bands of the range
of possible ICCs. Band 3 consists of 50 features simulated to have ICCs
between 0.3 and 0.4, Band 4 with ICCs between 0.4 and 0.5 and so on through
Band 9 which has ICCs between 0.9 and 1.0.

###  2.4 Real Face Recognition Data Set (Experiment 3)

We would have preferred to find a publicly available data set with 100,000 or
more subjects. We were not successful. However, we did find the MORPH
Craniofacial Longitudinal Morphological Face Database [9] (Link to MORPH Data
Base Description). The MORPH data set contains face images for 13,006
subjects. There are at least 2 distinct images per subject, and, in some
subjects, many more repeats (up to 53 images of the same person over time).
The images are colored (RGB), have various dimensions, include more than just
the face, and are not spatially registered.

###  2.5 Biometric Performance Assessment

The precise details of the biometric assessment are unique for each of the 3
experiments. In general, let’s assume that you know in advance which ICC Band
data set you want to use, and you know how many features p you want to include
in the analysis, and you also how many subjects n you want to include. If the
number of features P in the complete data set is greater than the number of
features requested p, then for each run, a random subset of the features is
chosen. If the number of subjects N in the complete data set is greater than
the number of subjects requested n, then for each run, a random subset of the
subjects (from each session) is chosen.

We employed the cosine distance metric, since we have shown in an earlier
report that the best biometric performance is produced with this choice [8]
(Link to prior report). The resulting distance measures were scaled to go from
0 to 1 and then they were reflected ($1-\text{distance}$) to compute
similarity scores. In a typical analysis, a “genuine” distribution of
similarity scores is constructed from the similarity scores for each subject
and his/her self. All other similarity scores are considered impostors. These
data are then submitted to a ROC analysis and the EER is computed.

Typically, with less than approximately 10,000 subjects, this analysis can be
performed in memory. For number of subjects n, the number of similarity scores
is equal to $n\textsuperscript{2}$. For $n\textsuperscript{5}$ subjects,
$n\textsuperscript{10}$ scores are needed. This is too large to run on
conventional desktop computers running MATLAB. (On the first author’s system,
with 16 GB of RAM, the maximum single precision MATLAB array that can be
created is 38,000 X 38,000.) To compute similarity scores for 100,000
subjects, special procedures are required.

To find the EER, we must find a similarity score threshold where the false
acceptance rate (FAR) is equal to the false rejection rate (FRR). Since the
difference between FAR and FRR (FAR - FRR) is monotonic, it is appropriate to
employ a binary search strategy to find the EER. Similarity scores are
computed for a marked subset (e.g., 1000) of all subjects (called a batch),
and similarity scores are computed just for a batch at a time. At first, the
upper and lower bound similarity thresholds are set to the minimum (0) and
maximum (1) possible similarity scores. Then a single threshold - an average
between the minimum and maximum, which is 0.5 - is evaluated. For each batch,
the number of impostor similarity scores above the threshold is counted as
well as the number of genuine similarity scores below or equal to the
threshold. These counts are accumulated for each batch through the entire data
set, and after each complete pass through the data, the FAR and FRR are
calculated. If the FRR is greater than FAR, then on the next iteration, the
upper threshold will be set to midpoint between the lower and upper
thresholds, and the lower threshold will not change. If the FRR is less or
equal to the FAR, then on the next iteration, the lower threshold will be set
to midpoint between the lower and upper thresholds, and the upper threshold
will not change. This continues until there are only 40 similarity scores
between the lower and upper threshold. At this point, iteration through the
entire dataset stops and we calculate the values of the difference function
(FAR - FRR) for these remaining 40 values. Then intermediate values are
linearly interpolated and the threshold level for equal FAR and FRR is chosen
as the final threshold, and the error rate (EER) is evaluated at that
threshold. As of June 3, 2019, the publicly available Python code that
implements this analysis is in preparation and will be available at GitHub
link to Binary Search Python code when complete.

##  3 Experiment 1: Number of Features Required to Obtain Perfect Performance

###  3.1 Methods

For this analysis, only Band 8 was employed. This data set consisted of 500
features and 100,000 subjects. The data in Band 8 was processed according to
Algorithm 2:

For N_Subjects = [1000;10000;100000]

For N_Features = 1:100

For Repetitions = 1:20

  1. 1.

Randomly choose N_Subjects (for N = 100,000, use all subjects)

  2. 2.

Randomly choose N_Features

  3. 3.

Compute EER

Algorithm 2 Steps to determine the number of features required to achieve
various levels of performance (EER)

These data were processed according to Algorithm 3:

For EER_Target = [10.0;5.0;2.5;1.0;0.1;0.01;0.001;0.0001;0.0]:

Find Number of Features which always (over 20 reps) produces EER<=EER_Target

Algorithm 3 Steps in the analysis:

###  3.2 Results

The results of this analysis is presented in Figure 2. For EER targets larger
than 0.001, approximately the same number of features are required to achieve
the target EER across data sets with 1,000, 10,000 and 100,000 subjects. As
EER targets decrease from EER <= 0.001 to 0.0, a linear trend appears with
more features required to achieve target for 10,000 subjects compared to 1,000
subjects and also for 100,000 subjects compared to 10,000 subjects.

Figure 2: Number of features required to achieve specific EER targets.

###  3.3 Discussion

For most typical cases, with target EERs > 0.01, there is no systematic change
in the number of features required. However, as the EER target approaches 0.0,
the number of features required increases as the number of subjects in the
data sets increase. Note that these effects are extremely unlikely to occur in
practice, since few if any real data sets with 10,000 or 100,000 subjects will
ever occur with EERs in this extremely small range.

##  4 Experiment 2: EERs for a Given Number of Features and Data Set Sizes of
1,000, 10,000 and 100,000 Subjects

###  4.1 Methods

There are two goals of this experiment. The first is to determine the EER of
Band 3 to 8 data sets, all with 10 features, for data set sizes of 1,000
subjects, 10,000 subjects and 100,000 subjects. The second goal is to
determine the EER of the Band 9 data set for 7, 8, 9, 10 or 11 features.

For this experiment, each of the data sets are created to have 100,000
subjects and 50 features.

We will be statistically comparing the mean EER obtained for each band for
each target number of features across number of subjects. The first question
this analysis presents is: How many EERs to estimate when N= 1,000, 10,000 or
100,000. The steps in this procedure are detailed in algorithm 4, and the
resulting number of data sets is presented in Table 1.

  1. 1.

Compute the standard error for N=100,000, 48 data sets.

  2. 2.

Determine, for N=1,000 and N = 10,000, the number of data sets required to
match the standard error for from Step 1.

  3. 3.

Use that number of data sets for all subsequent analyses.

Algorithm 4 Determine the number of data sets needed to get stable EER estimates Table 1: Number of data sets used across Band and number of subjects Band Number | Number of Features | 1,000 Subjects | 10,000 Subjects | 100,000 Subjects
---|---|---|---|---
3 | 10 | 106 | 51 | 48
4 | 10 | 103 | 59 | 48
5 | 10 | 158 | 68 | 48
6 | 10 | 83 | 34 | 48
7 | 10 | 93 | 48 | 48
8 | 10 | 114 | 55 | 48
9 | 7 | 61 | 48 | 48
9 | 8 | 46 | 38 | 48
9 | 9 | 77 | 45 | 48
9 | 10 | 64 | 54 | 48
9 | 11 | 113 | 37 | 48

###  4.2 Results

The results for the analysis of Bands 3 to 8, (10 features) are displayed in
Figure 3 and Tables 2 and 3. In Figure 3, for each Band, and for 10 features,
the EERs across number of subjects looks very stable. This is also evident in
the means and SDs presented in Table 2. Statistical results are provided in
Table 3. Given that different numbers of data sets were used for each
comparison, Welch’s t-test, which adjusts for different numbers of
observations in each group, was employed. Note that none of the 18 p-values
was statistically significant.

Figure 3: Relationship between number of subjects and EER for Bands 3 to 8, number of features = 10. Table 2: Means (SDs) for synthetic data - Bands 3 to 8, 10 features | Number of | N=1,000 | N=10,000 | N=100,000
---|---|---|---|---
Band | Features | Mean EER | SD | Mean EER | SD | Mean EER | SD
3 | 10 | 28.740 | 0.836 | 28.840 | 0.537 | 28.730 | 0.525
4 | 10 | 22.880 | 0.795 | 22.980 | 0.545 | 22.870 | 0.505
5 | 10 | 17.360 | 0.726 | 17.320 | 0.473 | 17.300 | 0.402
6 | 10 | 11.980 | 0.579 | 12.030 | 0.365 | 12.100 | 0.456
7 | 10 | 7.100 | 0.526 | 7.210 | 0.426 | 7.270 | 0.424
8 | 10 | 3.110 | 0.415 | 3.130 | 0.302 | 3.190 | 0.273
Table 3: P-Values for synthetic data - Bands 3 to 8, 10 features | N = 1,000 vs 10,000 | N = 1,000 vs 100,000 | N = 10,000 vs 100,000
---|---|---|---
Band | t-value | df | p-value | t-value | df | p-value | t-value | df | p-value
3 | -0.934 | 142 | 0.352 | 0.05 | 136 | 0.958 | 1.023 | 97 | 0.309
4 | -0.916 | 155 | 0.361 | 0.10 | 135 | 0.919 | 1.059 | 103 | 0.292
5 | 0.483 | 189 | 0.629 | 0.67 | 144 | 0.502 | 0.193 | 110 | 0.847
6 | -0.528 | 95 | 0.598 | -1.34 | 117 | 0.184 | -0.827 | 79 | 0.411
7 | -1.345 | 114 | 0.181 | -2.03 | 114 | 0.045 | -0.644 | 94 | 0.522
8 | -0.324 | 141 | 0.746 | -1.43 | 131 | 0.156 | -1.069 | 101 | 0.288

The results for the analysis of Band 9, (7 to 11 features) are displayed in
Figure 4 and Tables 4 and 5. Although the changes in EER across subjects look
less stable than in Figure 3, note the much lower range of EERs plotted
(ordinate). Aside from the data for 7 features, the changes in EER across
numbers of subjects appears reasonably stable. The means and SDs are also
quite close (Table 4). Statistical results are provided in Table 5. Only 1
p-value, shown in bold, is statistically significant. One of a total of 33
t-tests was statistically significant. With 33 tests, 1.65 comparisons would
be statistically significant by chance alone. As a general matter then, these
data indicate that EERs do not change across numbers of subjects from 1,000 to
100,000.

Figure 4: Relationship between number of subjects and EER for Band 9, number of features = 7 to 11 Table 4: Means (SDs) for synthetic data, Band 9, 7 to 11 features | Number of | N=1,000 | N=10,000 | N=100,000
---|---|---|---|---
Band | Features | Mean EER | SD | Mean EER | SD | Mean EER | SD
9 | 7 | 1.710 | 0.458 | 1.600 | 0.403 | 1.790 | 0.402
9 | 8 | 1.140 | 0.315 | 1.110 | 0.285 | 1.130 | 0.316
9 | 9 | 0.720 | 0.250 | 0.730 | 0.177 | 0.800 | 0.182
9 | 10 | 0.520 | 0.166 | 0.510 | 0.128 | 0.530 | 0.121
9 | 11 | 0.330 | 0.121 | 0.330 | 0.069 | 0.350 | 0.088
Table 5: P-Values for synthetic data, Bands 9, 7 to 11 features Number of | N = 1,000 vs 10,000 | N = 1,000 vs 100,000 | N = 10,000 vs 100,000
---|---|---|---
Features | t-value | df | p-value | t-value | df | p-value | t-value | df | p-value
7 | 1.414 | 106 | 0.1602 | -0.915 | 106 | 0.3621 | -2.34 | 94 | 0.0214
8 | 0.395 | 81 | 0.6941 | 0.16 | 92 | 0.8735 | -0.238 | 83 | 0.8123
9 | -0.14 | 115 | 0.8893 | -2.002 | 120 | 0.0476 | -1.934 | 91 | 0.0562
10 | 0.221 | 115 | 0.8255 | -0.303 | 110 | 0.7622 | -0.575 | 100 | 0.5666
11 | 0.222 | 110 | 0.8251 | -0.865 | 120 | 0.3889 | -1.077 | 83 | 0.2847

##  5 Experiment 3: Analysis with Real Data: Face-Recognition

###  5.1 Methods

We wish to note that although we are presenting a face-recognition analysis
and we are using a common and reasonable approach, we are doing so in the
service of our study of the relationship between numbers of subjects and EER.
We are not attempting to develop a state-of-the-art facial recognition
analysis with performance competitive with other modern approaches.

As noted above, in the MORPH Data Base there are at least 2 distinct images
per subject, and, in some subjects, many more repeats. The images are colored
(RGB), have various dimensions, include more than just the face, and are not
spatially registered. Prior to applying facial recognition analyses to these
data, we wanted to transform the original images, for all 13,006 subjects, to
2 grayscale (zscore transformed) images that each have 120 X 100 pixels, with
face only (almost). And we wanted these images to be spatially registered.

The original database comes in the form of a single directory with 55,134
separate JPG images. They each have file names which include a subject ID
code, the repeat number, a gender code and the age of the subject. The steps
in the preparation of these raw images into a set of images ready for
biometric assessment are provided in Algorithm 5.

  1. 1.

Convert images from color (RGB) to grayscale

  2. 2.

Detect faces in the images using the Viola-Jones algorithm and save the face-
only images.

  3. 3.

Z-score transform the images (subtract the mean across all pixels from every
pixel and divide by the SD across all pixels.)

  4. 4.

Register the face-only, z-score transformed images using an affine
transformation (translation, rotation, scale, and shear).

  5. 5.

Save registered images as 120 X 100 pixels.

  6. 6.

For each subject, correlate each image with each other image

  7. 7.

For each subject, choose the 2 most highly correlated images, and discard all
other images.

  8. 8.

Prepare image data for PCA analysis - Take the first image from the first
1,000 subjects and create a file with 1 row and 12,000 columns (120X100
pixels) for each of the images.

  9. 9.

Perform PCA on first 1000 first images and save the PCA coefficients.

  10. 10.

Apply these coefficients to the remaining 12,003 subjects, first and second
paired images.

  11. 11.

Drop all but the first 500 PCA components (out of 12,000).

  12. 12.

Normalize the PCA components with a z-score transformation

  13. 13.

Perform biometric assessment

Algorithm 5 Steps in the preparation of images for facial recognition

The first 1000 subjects, used to compute the PCA coefficients, were discarded
from further analysis. These first 1,000 images can be thought of as a
training set. For the remaining 12,003 subjects, biometric assessment
proceeded using the first 500 PCA components from the first matched image as
session 1 and with the second matched image as session 2. Data subsets were
created with a random selection of 1,000 or 10,000 subjects, using either the
first 3, 5, 9, 19, or 85 features. Random feature selection was not performed
due to the inherent ordered relationship between PCA components. We created 50
subsets for the N=10,000 subsets. The number of subsets created for the
N=1,000 subsets was chosen to match the standard error for the N=10,000
subsets.

###  5.2 Results

The EER results are illustrated in Figure 5 and Tables 6 and 7. It is clear
from Figure 5 that there is almost no change in EER for N=1,000 subjects
subsets compared to N=10,000 subject subsets. The mean EERs are extremely
close (Figure 5 and Table 6). Given this, it is not surprising that none of
the t-test comparisions are statistically significant.

Figure 5: Relationship between number of subjects and EER for a given number of features - MORPH Data Set Table 6: Means (SDs) for MORPH Face Database Number of | N = 1,000 | N = 10,000
---|---|---
Features | Mean EER | SD | SE | N Data Sets | Mean EER 0 | SD 0 | SE 0 | N Data Sets
3 | 22.85 | 0.656 | 0.0125 | 2737 | 22.85 | 0.088 | 0.0124 | 50
5 | 16.01 | 0.608 | 0.0117 | 2695 | 16.01 | 0.1 | 0.0141 | 50
9 | 13.09 | 0.586 | 0.0102 | 3293 | 13.07 | 0.07 | 0.0099 | 50
19 | 10.03 | 0.505 | 0.0078 | 4188 | 10.04 | 0.056 | 0.0079 | 50
85 | 5.58 | 0.466 | 0.009 | 2673 | 5.56 | 0.062 | 0.0088 | 50
Table 7: Statistical results for the MORPH Face Database Number of |  |  |
---|---|---|---
Features | t-value | df | p-value
3 | -0.224 | 197 | 0.8233
5 | -0.363 | 139 | 0.7171
9 | -1.449 | 206 | 0.1489
19 | 0.388 | 189 | 0.6988
85 | -1.688 | 203 | 0.093

##  6 General Discussion

For EER > 0.01, we have found no evidence that biometric performance, as
assessed by the EER, is affected by the number of subjects (N=1,000, 10,000,
100,00). To indicate how small this EER is, we note that the best fingerprint
authentication systems have EERs above 2.0 [1]. AimBrain, a business
enterprise that provides biometric services, recently (2019) proclaimed an EER
near 0.03 for their face recognition module AimBrain announcement. Using both
synthetic data and the (MOPRH) face database, and assuming EER targets > 0.01,
we find no evidence for any systematic change in EER as a function of the
database size. These observations only apply to the EER, and may well not
apply to other measures of performance. For example, evidence indicates that
identifications rates do decrease with increasing data set size [10, 7]. Our
observation regarding EER is consistent with the observations of [10, 7], who
studied this issue for from N=50 to N=335 subjects. This evidence suggests
that, if one’s goal is to estimate the EER of very large data sets (>>1,000),
there is no need to collect more than 1,000 subjects. Aside from the
theoretical interest of our results, this observation should be of real
practical value to the biometric community, when planning biometric modalities
at a large scale.

However, this stability was violated when the EER target was very close to 0.0
(<0.01). This was only observed in synthetic data. We we were not able to
find, nor is there likely to be, a biometric system with more than 1000
subjects that can produce an EER in this near-perfect range. We observed a
monotonic increase in the number of features required to achieve near-perfect
performance as the number of subjects in the data sets increased from 1,000 to
10,000 to 100,000. We state this observation as a fact, but have no ready
explanation for this observation.

##  7 Acknowledgments

The study was funded by 3 grants to Dr. Komogortsev: (1) National Science
Foundation, CNS-1250718 and CNS-1714623, www.NSF.gov; (2) National Institute
of Standards and Technology, 60NANB15D325, www.NIST.gov; (3) National
Institute of Standards and Technology, 60NANB16D293. Dr. Stern’s contributions
were partially funded through Cooperative Agreement #70NANB15H176 between NIST
and Iowa State University, which includes activities carried out at Carnegie
Mellon University, University of California Irvine, and University of
Virginia.

## References

  * Cappelli et al. [2006] R. Cappelli, D. Maio, D. Maltoni, J. L. Wayman, and A. K. Jain.  Performance evaluation of fingerprint verification systems.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 28(1):3–18, Jan 2006.  ISSN 0162-8828.  doi: 10.1109/TPAMI.2006.20.
  * Chan et al. [2018] H.-L. Chan, P.-C. Kuo, C.-Y. Cheng, and Y.-S. Chen.  Challenges and future perspectives on electroencephalogram-based biometrics in person recognition.  volume 12, 2018.  doi: 10.3389/fninf.2018.00066.
  * Dass et al. [2006] S. C. Dass, Z. Yongfang, and A. K. Jain.  Validating a biometric authentication system: Sample size requirements.  volume 28, pages 1902–1319, 2006.  doi: 10.1109/TPAMI.2006.255.
  * Friedman et al. [2017] L. Friedman, M. S. Nixon, and O. V. Komogortsev.  Method to assess the temporal persistence of potential biometric features: Application to oculomotor, gait, face and brain structure databases.  volume 12, page e0178501, 2017.  doi: 10.1371/journal.pone.0178501.  URL https://www.ncbi.nlm.nih.gov/pubmed/28575030.
  * Jain [2006] A. K. Jain.  Biometric authentication.  volume 3, page 3716, 2006.  URL http://www.scholarpedia.org/article/Biometric_authentication.
  * Jain et al. [2011] A. K. Jain, A. A. Ross, and K. Nandakumar.  _Introduction to biometrics_.  Springer, New York, 2011.  ISBN 9780387773254 (alk. paper) 0387773258 (alk. paper) 9780387773261 (e-ISBN).
  * Komogortsev et al. [2016] O. Komogortsev, A. Karpov, and C. Holland.  Oculomotor plant characteristics: The effects of environment and stimulus.  2016\.
  * [8] O. K. Lee Friedman.  Analysis of the effect of pca component normalization and choice of distance metric on biometric performance.  doi: DOI:10.13140/RG.2.2.17510.06727.  URL https://www.researchgate.net/publication/330714244_Analysis_of_the_effect_of_PCA_component_normalization_and_choice_of_distance_metric_on_biometric_performance.
  * Ricanek Jr and Tesafaye [2006] K. Ricanek Jr and T. Tesafaye.  Morph: A longitudinal image database of normal adult age-progression.  In _EEE 7th International Conference on Automatic Face and Gesture Recognition, Southampton, UK_ , pages 341–345, 2006.
  * Rigas and Komogortsev [2014] I. Rigas and O. V. Komogortsev.  Biometric recognition via probabilistic spatial projection of eye movement trajectories in dynamic visual environments.  volume 9, pages 1743–1754, 2014.