# Quantum Lattice Representation for the Curl Equations of Maxwell Equations

George Vahala  Department of Physics, William & Mary, Williamsburg, VA23185
John Hawthorne  Department of Physics, William & Mary, Williamsburg, VA23185
Linda Vahala  Department of Electrical & Computer Engineering, Old Dominion
University, Norfolk, VA 12319  Abhay K. Ram  Plasma Science and Fusion Center,
MIT, Cambridge, MA 02139  Min Soe  Department of Mathematics and Physical
Sciences, Rogers State University, Claremore, OK 74017

$\bf{Abstract}$: A quantum lattice representation (QLA) is devised for the
initial value problem of one-dimensional (1D) propagation of an
electromagnetic disturbance in a scalar dielectric medium satisfying directly
only the two curl equations of Maxwell. It si found that only 4 qubits/node
are required. The collision, streaming, and potential operators are determined
so as to recover the two curl equations to second order. Both polarizations
are considered.

##  1 Introduction

In plasma physics it is not uncommon to truncate the full Maxwell equations by
dropping enforcement of the two divergence equations
$\nabla\bm{.}(\epsilon\mathbf{E})\quad=\rho,\quad\nabla\bm{.}\mathbf{B}\ =\
0$, treating them as initial conditions. The remaining two curl equations are

$\displaystyle\nabla\times\mathbf{E}\ $ $\displaystyle=\
-\frac{\partial\mathbf{B}}{\partial t}\ $ $\displaystyle\
\nabla\times\mathbf{B}\ $
$\displaystyle=\mu_{0}\mathbf{J}+\mu_{0}\frac{\partial\,\epsilon\,\mathbf{E}}{\partial
t}.$ (1)

Here $\mathbf{E}$ and $\mathbf{B}$ are the electric and magnetic fields,
$\rho$ is the free charge density, $\mathbf{J}$ is the free current density,
$\mu_{0}$ is the (constant) magnetic permeability, and $\epsilon$ is the
(scalar) dielectric function. Of course, if $\nabla\bm{.}\mathbf{B}\ =\ 0$
initially, then theoretically it remains zero for all time. Unfortunately,
numerical codes will wobble in their time evolution of
$\nabla\bm{.}\mathbf{B}$ and thus require divergence cleaning or the
introduction of a vector potential. Gauss’ law can also be problematic and not
so easily discarded. Here we shall consider one dimensional (1D) propagation
of an electromagnetic pulse, governed by the two curl Maxwell equations of Eq,
(1). In a scalar dielectric medium these 1D pulse are transverse so that
automatically $\nabla\bm{.}(\epsilon\mathbf{E})=\nabla\bm{.}\mathbf{B}\ =\ 0$
for all times.

Recently [1-5] we have been developing quantum lattice algorithms (QLA) for
the solution of the full Maxwell equations in 1D, 2D and 3D. In this note we
wish to develop a 1D QLA for the solution of the two curl Maxwell equations.
This has been motivated by a conference paper simulation by Jestadt, Appel and
Rubio [6] in which they also restrict their attention to the two curl Maxwell
equations. Following the work of Khan [7] and the introduction of the Riemann-
Silberstein-Weber vector

$\mathbf{F^{\pm}}=\sqrt{\epsilon}\mathbf{E}\pm
i\frac{\mathbf{B}}{\sqrt{\mu_{0}}}.$ (2)

they [6] reduced their system to a 6-spinor Schrodinger-like equation. The
exponential evolution operator is then approximated using the standard Baker-
Campbell-Hausdorff expansion. This introduces both a first and second order
derivative of the refractive index
$n(\mathbf{x})=\sqrt{\epsilon(\mathbf{x}})$. Their resulting simulation of a
1D wave packet incident from a vacuum into a dielectric medium yields a
transmitted wave packet with similar wavelength to the incident wave packet.
However, one expects the transmitted wavelength to be reduced by the
corresponding ratio of the media refractive indices.

In Sec. 2 we shall develop a 1D QLA for the two curl equations of Maxwell
based on the Khan representation that draws a strong analogy with the Dirac
equation for a massless particle [8-10]. The QLA [1-5, 11-12] consists of a
sequence of non-commuting collide-stream operators and some potential
collision operators so chosen that in the continuum limit one recovers the
Khan representation. In Sec 3 we present initial value 1D QLA simulations for
a Gaussian pulse propagating in the x-direction and consider the two
polarizations: one with non-zero field components $E_{y}$ and $B_{z}$ and the
other with non-zero $-E_{z}$ and $B_{y}$. The pulse propagates from a region
of refractive index $n_{1}$ that is joined to another dielectric of refractive
index $n_{2}$ by a thin boundary layer. We recover exactly the same physics as
with the QLA for the full Maxwell equations [1,2]: in particular the
transmitted to initial field amplitude scales as
$2\sqrt{n_{1}n_{2}}/(n_{1}+n_{2})$ \- which is an extension of the standard
boundary value result [13] for a plane electromagnetic wave by the factor
$\sqrt{n_{2}/n_{1}}$. We also consider the reflection and scattering of a
Gaussian wave packet and indeed see a significant change in the wavelength of
the transmitted packet. Only 4-qubits per spatial grid point are required for
this new QLA. Finally, in Sec. 4 we present some conclusions and comments on
further work.

##  2 1D QLA for the two curl equations of Maxwell

It is convenient to introduce the qubits as just the Riemann-Silberstein-Weber
vectors, Eq. (2). With that choice we now proceed to determine the required
form of the collision, scattering and potential operators that will recover
the two curl equations of Maxwell in the continuum limit. As details are
presented in our earlier papers [1-5], we just summarize the results here.
Since we are considering 1D propagation in the x-direction, we automatically
have $E_{x}=0=B_{x}$. This reduces the number of qubits/lattice site to 4:

$\displaystyle q_{1}=n(x)E_{y}+iB_{y},\qquad q_{2}=n(x)E_{z}+iB_{z}$ (3)
$\displaystyle q_{4}=n(x)E_{y}-iB_{y},\qquad q_{5}=n(x)E_{z}-iB_{z},$ (4)

since $q_{0}=n(x)E_{x}+iB_{x}=0=q_{3}=n(x)E_{x}-iB_{x}$. An appropriate
collision matrix acting on the 4-spinor $Q=(q_{1}\quad q_{2}\quad q_{4}\quad
q_{5})^{T}$ is the $4\crossproduct 4$ unitary matrix

$C(\theta)=\begin{bmatrix}\cos\theta&i\sin\theta&0&0\\\
i\sin\theta&\cos\theta&0&0\\\ 0&0&\cos\theta&-i\sin\theta\\\
0&0&-i\sin\theta&\cos\theta\\\ \end{bmatrix}.$ (5)

and the interleaved non-commuting sequence of collide-stream operators

$U=S^{-}_{25}.C^{+}.S^{+}_{25}.C.S^{+}_{14}.C^{+}.S^{-}_{14}.C.\quad
S^{+}_{25}.C.S^{-}_{25}.C^{+}.S^{-}_{14}.C.S^{+}_{14}.C^{+}$ (6)

where $S_{14}^{+}$ streams qubits $q_{1}$ and $q_{4}$ one lattice unit to the
right while not streaming qubits $q_{2}$ and $q_{5}$. $C^{+}$ is the adjoint
of the unitary matrix $C$. To perturbatively recover the two curl equations of
Maxwell one will need to introduce the potential operators

$V_{1}(\alpha)=\begin{bmatrix}\cos\alpha&-\sin\alpha&0&0\\\
\sin\alpha&\cos\alpha&0&0\\\ 0&0&\cos\alpha&\sin\alpha\\\
0&0&-\sin\alpha&\cos\alpha\\\ \end{bmatrix}.$ (7)

and

$V_{2}(\alpha)=\begin{bmatrix}\cos\alpha&0&0&-\sin\alpha\\\
0&\cos\alpha&\sin\alpha&0\\\ 0&\sin\alpha&\cos\alpha&0\\\
-\sin\alpha&0&0&\cos\alpha\\\ \end{bmatrix}.$ (8)

and the rotation angles $\theta=-\epsilon/4n(x)$ and
$\alpha=i\,\epsilon^{2}n^{\prime}(x)/2n^{2}(x)$. The perturbation parameter
$\epsilon$ will turn out to be the speed of light in that medium. The QLA time
evolution of the 4-qubits is then determined by

$Q(t+\delta t)=V_{2}(\alpha)V_{1}(\alpha).UQ(t)$ (9)

In the continuum limit the above QLA reduces, to $\O(\epsilon^{2})$,

$\frac{\partial}{\partial t}\begin{bmatrix}q_{1}\\\ q_{2}\\\ q_{4}\\\ q_{5}\\\
\end{bmatrix}=-\frac{i}{n(x)}\frac{\partial}{\partial
x}\begin{bmatrix}-q_{2}\\\ q_{1}\\\ q_{5}\\\ -q_{4}\\\
\end{bmatrix}+\frac{i\,n^{\prime}(x)}{2n^{2}(x)}\begin{bmatrix}-q_{2}-q_{5}\\\
q_{1}+q_{4}\\\ q_{2}+q_{5}\\\ -q_{1}-q_{4}\\\ \end{bmatrix}$ (10)

From Eqs. (3) and (4), it is readily shown that the continuum Eq. (10) are
nothing but the two curl equations of Maxwell for both polarizations.

##  3 1D QLA simulations of the two curl equations of Maxwell

###  3.1 Gaussian Pulse

Consider a Gaussian pulse propagating from a vacuum (with refractive index
$n_{1}=1$) into a medium with refractive index $n_{2}=2.5$. There is a sharp
boundary layer of approximate thickness of 10 lattice units connecting $n_{1}$
to $n_{2}$, Fig. 1.

Figure 1: The refractive index of the medium: vacuum for $0<x<5000$ and
$6000<x<9000$ with dielectric in region $5000<x<6000$ with $n_{2}=2.5$. The
boundary layer is about 10 lattice units thick.

Figure 2 shows the pulse of width 600 lattice units with normalization such
that its speed of propagation is $\epsilon=0.3$, and the magnitude of the
electric field component is equal to its magnetic field component.

(a) polarization $E_{z}$

(b) polarization $E_{y}$

Figure 2: The propagation of a Gaussian pulse at time t = 6000 for
polarization with non-zero field components (a) $E_{z}<0$ (in blue) ,
$B_{y}>0$ (in red) ; (b) $E_{y}>0$ (in blue) , $B_{z}>0$ (In red). In our
normalized units, for case (b), $E_{y}=B_{z}$ and the two profiles overlay
each other.

By t = 12000, the Gaussian pulse has encountered its first
reflection/transmission. Since the propagation is from low to higher
refractive index , the reflected electric field component at the vacuum-
dielectric interface undergoes a $\pi$ phase reversal, as seen in Fig. 3.
(This, of course, agrees with the standard plane wave boundary value result
[13]).

(a) polarization $E_{z}$

(b) polarization $E_{y}$

Figure 3: The propagation of a Gaussian pulse at time t = 12000 after the
first encounter with the dielectric slab around $x=5000$. The pulse width and
speed in the dielectric are reduced by the facctor $n_{2}/n_{1}$. (a) the
reflected $E_{z}$ ( blue) changes its phase by $\pi$ and becomes positive and
overlays $B_{y}$ (red) while the transmitted pulse has these componentsout of
phase; (b) the reflected pulse now has the $E_{y}$ (blue) and $B_{z}$ (red)
out of phase while the transmitted pulse has these components in phase.

Finally we plot the pulses after their interaction with the backside of the
$n_{2}$ dielectric at $x=6000$, Fig. 4. Since the pulse now is propagating
from higher to lower refractive index, $n_{2}>n_{1}$, it is now the reflected
magnetic field that undergoes a $\pi$-phase reversal.

(a) polarization $E_{z}$

(b) polarization $E_{y}$

Figure 4: The propagation of a Gaussian pulse at time t = 24000 after the
seccond encounter with the dielectric slab-vacuum interface, but now at
$x=6000$. The pulse width and speed in the dielectric are reduced by the
factor $n_{2}/n_{1}$. (a) the reflected $B_{y}$ (red) changes its phase by
$\pi$; (b) the reflected pulse now has the $E_{y}$ (blue) and $B_{z}$ (red)
out of phase while the transmitted pulse has these components in phase.

In our earlier 1D QLA for the full set of Maxwell equations, we showed and
developed a theory that for normal incidence the electric field amplitude of
the transmitted to incident pulse is augmented by a factor of
$\sqrt{n_{2}/n_{1}}$ over the plane wave boundary value result of
$2n_{1}/(n_{1}+n_{2})$. For reflection/transmission at the first interface, we
find that both polarizations yield $|E_{trans}/E_{inc}|=0.91$, Fig. 3. For the
subsequent reflection/transmission at the back face of the dielectric slab, we
find the $E_{z}$ polarization that $|E_{trans}/E_{inc}|=0.88$, Fig. 4a. For
the $E_{y}$ polarization, the ratio $|E_{trans}/E_{inc}|=0.89$, Fig. 4b. The
theoretical initial value problems result for $n_{1}=1,n_{2}=2.5$ is 0.90 .
(The simple standard boundary value for plane waves, however, yields a ratio
of $0.57$.)

###  3.2 Gaussian wave packet

We plot the electric field $E_{y}$ for the Gaussian wave packet as it
propagates towards the dielectric slab which starts around x = 5000, Fig 5.

Figure 5: The electric field $E_{y}$ of a Gaussian wave packet in medium
$n_{1}=1$ as it propagates towards a dielectric slab $5000<x<6000$ with
$n_{2}=2$.

After the first reflection/transmission at $x=5000$ one notices the
$n_{1}/n_{2}$ reduction in the wavelength of the transmitted wave packet
within the dielectric $n_{2}$. The reflected electric field of the wave packet
undergoes a $\pi=$phase change as expected from plane wave boundary value
theory. However the relative field amplitudes do not seem to follow a simple
mathematical expression - clearly nothing like that for a boundary value plane
wave or an intial value pulse. Partly this could arise from the importance of
the normalization constraint in the Gaussian pulse theory [2]: with
oscillations in the profile this constraint becomes much less effective.
Interestingly, there is a slight break in symmetry in the transmitted electric
field - as seen in Fig. 6

Figure 6: The electric field $E_{y}$ of a Gaussian wave packet following the
first reflection/transmission at the interface $x=5000$.

Finally in Fig 7 we plot the electric field of the wave packet following the
second reflection/transmission at the back of the dielectric slab at $x=6000$.

Figure 7: The electric field $E_{y}$ of a Gaussian wave packet following the
second reflection/transmission at the back of the dielectric interface,
$x=6000$.

The asymmetry continues in the transmitted part of the wave packet into the
vacuum region, $x>6000$.

##  4 Conclusions and Comments

We [1-5] have been developing QLAs for the full Maxwell equations for 1D, 2D
and 3D electromagnetic propagation in scalar dielectric media. While these
algorithms utilize quantum information science their actual implementation on
error-correcting quantum computers will be decades away. However, these QLAs
are ideally parallelized on classical supercomputers up to the maximum cores
available. Indeed, on the IBM $Mira$ supercomputer, the parallelization of
QLAs (for spinor Bose-Einstein condensates [14-16]) still scaled even to over
750 000 cores. The QLA building blocks are the Khan [7] representation of the
full Maxwell equations using the two Riemann-Silberstein-Weber polarization
4-vectors in that medium. We [1-5] have seen that for both 1D x- and y-
propagation one requires a QLA of at least 8 qubits. For 1D
z-propagation,however, the QLA will requre a 16 qubit representation per
lattice node. This is because the QLA now involves the diagonal Pauli spin
matrix $\sigma_{z}$, and since the collision operator must entangle at least 2
qubits at each site the QLA representation requires 16 qubits/node.

An interesting, and somewhat unexpected result of our 1D QLA pulse simulations
[1-2] was that the transmitted to incident electric field amplitude was

$\frac{2n_{1}}{n_{1}+n_{2}}\sqrt{\frac{n_{2}}{n_{1}}}$ (11)

\- a factor of $\sqrt{{n_{2}}/{n_{1}}}$ different from the standard boundary
value plane wave result [13]. We [2] then developed a theory on Gaussian
pulses that explained this QLA result. However for an electromagnetic wave
packet, the 1D QLA results are much more complicated and one does not recover
such a universal result as Eq. (9).

The central point of this note was to develop a 1D QLA for the two curl
equations of Maxwell, Eq. (1). For 1D transverse pulse propagation in a scalar
dielectric, the two divergence equations of Maxwell are identically zero - but
now, for each polarization and x-propagation, there are only two non-zero
field components: either non-zero $(E_{y},B_{z})$ or $(-E_{z},B_{y})$. Thus
only a 4-qubit QLA is needed. We have here developed such a 4-qubit QLA and
performed simulations for both polarizations. Once again, Eq. (9) is recovered
for the ratio of transmitted to incident electric field amplitudes. For wave
packets, there is no such simple universal relationship: the dominant result
is that the wavelenth of the transmitted to incident wave packets scales as
$n_{1}/n_{2}$. These simulations were undertaken partly to examine the
conference paper by Jestadt et. al. [6]. While they too base their algorithm
on the Khan representation for the two curl equations, they directly move to
an approximation of the exponential of the sum of two non-commuting operators.
While we have moved to a QLA representation, Jestadt et. al.[6] applied the
Baker-Campbell-Hausdorff approximation. In their method the final equations
involve both $n^{\prime}(x)$ and $n^{\prime\prime}(x)$ derivatives of the
refractive index. One unexpected result of their simulations was that the
transmitted and incident wave packets had approximately the same wavelengths.
Our 1D QLA 4-qubit simulations yielded wavelength ratios of $n_{1}/n_{2}$. We
feel that this could be due to the occurrence of the second derivative in the
refractive index, $n^{\prime\prime}(x)$ in [6]. A little thought had us
realize that the first derivative in the refractive index, $n^{\prime}(x)$, is
a term introduced by use of the Khan Riemann-Silberstein-Weber vector in the
medium, Eq. (2). Because in the 1D scalar dielectric problem there is no
derivative $n^{\prime}(x)$ introduced when looking at the curl equations of
Maxwell, this $n^{\prime}(x)$ introduced by the material media
$\mathbf{F^{\pm}}$ must be counter-balanced by a similar term coming from the
introduction of appropriate QLA potential operators. Similar cancellations
most likely occur for the Jestadt representation for the $n^{\prime}(x)$, but
there may not be such a similar cancellation for the $n^{\prime\prime}(x)$.

Clearly these results indicate that one should actually work with the vacuum
Riemman-Silberstein-Weber vectors $\sqrt{\epsilon_{0}}\mathbf{E}\pm
i\mathbf{B}/\sqrt{\mu_{0}}$ rather than the medium Riemann-Silberstein-Weber
vectors $\sqrt{\epsilon}\mathbf{E}\pm i\mathbf{B}/\sqrt{\mu_{0}}$. This will
be explored in future research.

##  5 Acknowledgments

This research was partially supported by Department of Energy grants DE-
SC0021647, DE-FG02- 91ER-54109, DE-SC0021651, DE-SC0021857, and DE-SC0021653.

##  6 References

[1] VAHALA, G, VAHALA, L, SOE, M $\&$ RAM, A, K. 2020. Unitary Quantum Lattice
Simulations for Maxwell Equations in Vacuum and in Dielectric Media, J. Plasma
Phys $\bf{86}$, 905860518

[2] RAM, A. K., VAHALA, G., VAHALA, L. $\&$ SOE, M 2021 Reflection and
transmission of electromagnetic pulses at a planar dielectric interface -
theory and quantum lattice simulations, AIP Advances $\bf{11}$, 105116

[3] VAHALA, G, SOE, M, VAHALA, L, $\&$ RAM, A. K. 2021 Two Dimensional
Electromagnetic Scattering from Dielectric Objects using Quantum Lattice
Algorithm, submitted J. Comp. Physics: arXiv:2110.05480

[4] VAHALA, G, VAHALA, L, SOE, M $\&$ RAM, A, K. 2021 One and Two Dimensional
Quantum Lattice Algorithms for Maxwell Equations in Inhomogeneous Scalar
Dielectric Media I: Theory, Radiat. Eff. Defects Solids $\bf{176}$, 49-63

[5] VAHALA, G, SOE, M, VAHALA, L, $\&$ RAM, A, K. 2021 One and Two Dimensional
Quantum Lattice Algorithms for Maxwell Equations in Inhomogeneous Scalar
Dielectric Media I: Theory, Radiat. Eff. Defects Solids $\bf{176}$, 64-72

[6] JESTADT, R, APPEL, H, $\&$ RUBIO, A. 2014 Real-time evolution of Maxwell
equations in spinor representation, Conference paper.

[7] KHAN, S. A. 2005 Maxwell Optics: I. An exact matrix representation of the
Maxwell equations in a medium. Physica Scripta 71, 440-442; also arXiv:
0205083v1 (2002)

[8] LAPORTE, O. $\&$ UHLENBECK, G. E. 1931 Application of spinor analysis to
the Maxwell and Dirac equations. Phys. Rev. 37, 1380-1397.

[9] OPPENHEIMER, J. R. 1931 Note on light quanta and the electromagnetic
field. Phys. Rev. 38, 725-746.

[10] MOSES, E. 1959 Solutions of Maxwell’s equations in terms of a spinor
notation: the direct and inverse problems. Phys. Rev. 113, 1670-1679

[11] YEPEZ, J. 2002 An efficient and accurate quantum algorithm for the Dirac
equation. arXiv: 0210093.

[12] YEPEZ, J. 2005 Relativistic Path Integral as a Lattice-Based Quantum
Algorithm. Quant. Info. Proc. 4, 471-509.

[13] JACKSON, J, D. 1998. Classical Electrodynamics, 3rd Ed., (Wiley, New
York)

[14] YEPEZ, J, VAHALA, G, VAHALA, L $\&$ SOE, M. 2009b Superfluid turbulence
from quantum Kelvin wave to classical Kolmogorov cascades. Phys. Rev. Lett.
103, 084501.

[15] VAHALA, G, ZHANG, B, YEPEZ, J, VAHALA. L $\&$ SOE, M. 2012 Unitary Qubit
Lattice Gas Representation of 2D and 3D Quantum Turbulence. Chpt. 11 (pp. 239
- 272), in Advanced Fluid Dynamics, ed. H. W. Oh, (InTech Publishers, Croatia)

[16] VAHALA, G, SOE, M $\&$ VAHALA, L. 2020 Qubit Unitary Lattice Algorithm
for Spin-2 Bose Einstein Condensates: II Vortex Reconnection Simulations and
non-Abelian Vortices. Rad. Eff. Def. Solids 175, 113-119


#  ACETest: Automated Constraint Extraction for Testing Deep Learning
Operators

Jingyi Shi  Institute of Information Engineering, CAS; School of Cyber
Security, UCASBeijingChina Key Laboratory of Network Assessment Technology,
CASBeijing Key Laboratory of Network Security and Protection Technology
<EMAIL_ADDRESS>,  Yang Xiao  Institute of Information Engineering, CAS;
School of Cyber Security, UCASBeijingChina<EMAIL_ADDRESS>,  Yuekang Li
University of New South WalesSydneyAustralia<EMAIL_ADDRESS>,  Yeting Li
Institute of Information Engineering, CAS; School of Cyber Security,
UCASBeijingChina<EMAIL_ADDRESS>,  Dongsong Yu  Zhongguancun
LaboratoryBeijingChina<EMAIL_ADDRESS>,  Chendong Yu  Institute of
Information Engineering, CAS; School of Cyber Security, UCASBeijingChina
<EMAIL_ADDRESS>,  Hui Su  Institute of Information Engineering, CAS;
School of Cyber Security, UCASBeijingChina<EMAIL_ADDRESS>,  Yufeng
Chen  Institute of Information Engineering, CAS; School of Cyber Security,
UCASBeijingChina<EMAIL_ADDRESS>and  Wei Huo  Institute of Information
Engineering, CAS; School of Cyber Security, UCASBeijingChina<EMAIL_ADDRESS>
(2023; 2023-02-16; 2023-05-03)

###### Abstract.

Deep learning (DL) applications are prevalent nowadays as they can help with
multiple tasks. DL libraries are essential for building DL applications.
Furthermore, DL operators are the important building blocks of the DL
libraries, that compute the multi-dimensional data (tensors). Therefore, bugs
in DL operators can have great impacts. Testing is a practical approach for
detecting bugs in DL operators. In order to test DL operators effectively, it
is essential that the test cases pass the input validity check and are able to
reach the core function logic of the operators. Hence, extracting the input
validation constraints is required for generating high-quality test cases.
Existing techniques rely on either human effort or documentation of DL library
APIs to extract the constraints. They cannot extract complex constraints and
the extracted constraints may differ from the actual code implementation.

To address the challenge, we propose ACETest, a technique to automatically
extract input validation constraints from the code to build valid yet diverse
test cases which can effectively unveil bugs in the core function logic of DL
operators. For this purpose, ACETest can automatically identify the input
validation code in DL operators, extract the related constraints and generate
test cases according to the constraints. The experimental results on popular
DL libraries, TensorFlow and PyTorch, demonstrate that ACETest can extract
constraints with higher quality than state-of-the-art (SOTA) techniques.
Moreover, ACETest is capable of extracting 96.4% more constraints and
detecting 1.95 to 55 times more bugs than SOTA techniques. In total, we have
used ACETest to detect 108 previously unknown bugs on TensorFlow and PyTorch,
with 87 of them confirmed by the developers. Lastly, five of the bugs were
assigned with CVE IDs due to their security impacts.

Constraint Extraction, Deep Learning Library Testing, Symbolic Execution, Test
Generation

††copyright: rightsretained††doi: 10.1145/3597926.3598088††journalyear:
2023††submissionid: issta23main-p168-p††isbn:
979-8-4007-0221-1/23/07††conference: Proceedings of the 32nd ACM SIGSOFT
International Symposium on Software Testing and Analysis; July 17–21, 2023;
Seattle, WA, United States††booktitle: Proceedings of the 32nd ACM SIGSOFT
International Symposium on Software Testing and Analysis (ISSTA ’23), July
17–21, 2023, Seattle, WA, United States††ccs: Software and its engineering
Software testing and debugging††ccs: Software and its engineering Software
reliability

##  1\. Introduction

Deep learning (DL) has been applied in almost every inch of modern society,
including computer vision (He et al., 2016; Li et al., 2022b), natural
language processing (Devlin et al., 2019; Qian et al., 2022), and program
comprehension (Ahmad et al., 2020; Patrick-Evans et al., 2021; Liu et al.,
2019), etc. As the backbone of DL systems, DL models are used to process the
multi-dimensional inputs, which are called tensors. To develop, deploy and
execute DL models with reusable code, data scientists and engineers have
developed various DL libraries such as TensorFlow (Abadi et al., 2016) and
PyTorch (Paszke et al., 2019). Inside the DL libraries, DL operators are the
key components to perform computational tasks on tensors and one library API
may use multiple DL operators. Since the logic of the DL operators is
computational intensive, the DL operators are implemented as low-level
components of the libraries with C/C++ programming language in order to
execute faster. As a result, bugs in these DL operators are often memory
errors with security impacts and can affect the functionality of multiple APIs
in the DL library. Unfortunately, DL operators are vulnerable to bugs. For
example, TensorFlow, one of the most popular DL libraries, has disclosed 378
vulnerabilities in the CVE database since 2019 (MITRE, 2022). Furthermore, 249
(65.87%) of them are related to DL operators. Therefore, early detection of
bugs in DL operators is important for assuring the quality of DL libraries and
applications.

Testing (Sen et al., 2005; Wang et al., 2020; Cadar et al., 2011; She et al.,
2018; Wang et al., 2017a) is a popular technique for detecting bugs in
programs. Compared with static analysis techniques (Liu et al., 2021; Xiao et
al., 2020; Cai et al., 2022; Fan et al., 2019; Wang et al., 2017b), it
produces much fewer false positives and provides proof-of-concept test cases
for human experts to reproduce the bugs. However, generating high-quality test
cases for DL operators is challenging. The main reason is that most of the
bugs in DL operators reside within the core functional logic responsible for
processing tensors, while reaching this logic requires the test cases to pass
a set of validity checks. Randomly generated test cases can hardly pass these
validity checks, and passing the validity checks requires the test cases to
satisfy the constraints of the input validation logic. Therefore, acquiring
the constraints for valid inputs is important for generating high-quality test
cases.

Several techniques have been proposed to acquire the input constraints for DL
operators or DL library APIs in recent years. Both Duo (Zhang et al., 2021a)
and Predoo (Zhang et al., 2021b) require to supply the input constraints
manually when detecting bugs in DL operators. The drawback of manual input
constraints extraction is two-fold. On the one hand, it requires a lot of
manual effort. On the other hand, some input constraints are too complex to be
extracted manually. To save manual effort, FreeFuzz (Wei et al., 2022)
proposes to mine test cases from open source and DeepREL (Deng et al., 2022)
leverages existing test cases to test more APIs by inferring relational APIs.
IvySyn (Christou et al., 2022) directly tests the C/C++ native code of DL
operators by instrumenting to obtain type constraints of input parameters.
However, due to the lack of clarity regarding constraints when generating test
cases, they can not generate test cases effectively. To automatically extract
complex constraints, DocTer (Xie et al., 2022) uses rule-based approaches to
collect constraints from the API function descriptions of the documentation.
Nevertheless, DocTer has difficulties in extracting input constraints
effectively for DL operators. The quality of the extracted constraints heavily
relies on the API function descriptions. If the API function description is
absent or inaccurate, the extracted constraints will be affected. Moreover,
the API function description may not fully reflect the logic of the actual
implementation. Therefore, an approach to automatically extract the input
constraints accurately for DL operators is needed.

Symbolic Execution (SE) (King, 1976; Li et al., 2013; Dudina and Belevantsev,
2017) is a widely used approach to extract constraints by traversing all paths
in the source code. However, it suffers from scalability problems because of
the infamous path explosion problem. Additionally, the constraint solving can
be time-consuming and challenging for large programs (Zhang et al., 2020).
Directed Symbolic Execution (DSE) (Sen, 2005) can partially mitigate the
scalability problems by extracting constraints related to specific paths
instead of all the paths in the program. However, the problem of whichever
specific paths to traverse is left untouched. If the paths are not selected
properly, the collected constraints can still cause scalability issues. Hence,
directly applying existing SE or DSE techniques cannot fulfill the need.

To fill the research gap, we propose ACETest, a technique which can
automatically extract input validation constraints from the code of DL
operators and use the constraints to generate high-quality test cases for
detecting bugs in DL operators. The overall idea of ACETest is to extract
constraints related to the user-controllable inputs for input validation and
leverage them to generate the test cases randomly within the valid input
space. Thus, the generated test case is valid enough to reach the core
functional logic, and is diverse enough to find bugs. ACETest works in three
steps: input validation path extraction, constraint extraction and testing.
Initially, ACETest gathers meta information of the DL operators, including
their names and parameter types. Next, by traversing backwards on the control-
flow graph (CFG) from the error-handling basic-blocks (BBs), ACETest
identifies the input validation code. With the input validation code, ACETest
extracts all execution paths that do not result in errors during input
validation. For each path, ACETest extracts constraints related to the user-
controllable inputs. To accomplish this, a general constraint model is
proposed to guide the constraint extraction process. The tool employs
controllability propagation rules to identify user-controllable values in a
restricted manner during the constraint extraction process. Additionally, a
set of constraint construction rules is utilized to construct constraints
while traversing the path. Once the constraints are extracted, the tool
employs Z3 (de Moura and Bjørner, 2008) to generate solutions and subsequently
generates test cases based on these solutions. The generated test cases are
then utilized to test the DL operators, and any resulting crashes are reported
accordingly.

We implemented ACETest as an automatic DL operator testing framework and
evaluated its performance on 610 and 485 operator-level APIs for TensorFlow
and PyTorch, respectively. The experiment results demonstrate that ACETest can
extract 96.4% more constraints than DocTer. With the extracted constraints,
the generated test cases of ACETest can increase the pass rate on TensorFlow
and PyTorch by 162.60% and 138.58% than DocTer, respectively. Consequently,
ACETest detects 1.95 to 55 times more bugs than SOTA techniques. Notably,
ACETest is able to detect 108 previously unknown bugs, with 87 already
confirmed by the developers, and five of them received CVE numbers.

In summary, our paper makes the following contributions:

  * •

Dimension. This paper opens a new dimension for generating high-quality test
cases for DL operators by automatically extracting input validation
constraints from the code.

  * •

Technique. We build ACETest, a DL operator testing framework that can extract
input validation constraints automatically and generate high-quality test
cases. ACETest can automatically identify the input validation paths and
extract the constraints related to user inputs from the code of the DL
operators.

  * •

Evaluation and Impact. With experiments conducted on operator-level APIs of
TensorFlow and PyTorch, we found that the constraints extracted by ACETest
exhibit a higher quality than those extracted by existing SOTA techniques.
Furthermore, ACETest detected 108 previously unknown bugs with 87 of them
confirmed by the developers. Additionally, five of the bugs were assigned CVE
IDs.

The source code of ACETest as well as the list of identified bugs will be
publicly accessible at https://github.com/shijy16/ACETest.

##  2\. Background

###  2.1. DL Library Testing

Depending on the test targets, existing DL library testing techniques fall
into three categories: model-related testing, high-level API testing, and
operator testing. In model-related testing, DL models are generated as test
cases and executed using the target DL library. This form of testing focuses
on evaluating various aspects of the library’s functionality, such as model
parsing logic, computational graph optimization logic, execution scheduling
logic, and other aspects of model handling. While multiple components within
the DL library are tested, it is often challenging to reach the deep logic of
each component. This difficulty arises from the lack of clear linkage between
the features of the models and the features of the underlying code, making it
hard to generate models that can specifically exercise certain code
components. High-level API testing focuses on the high-level APIs in DL
libraries. By generating test cases for each high-level API directly, these
techniques enjoy more flexibility than model-related testing and they can test
deeper into each API function. Operator testing further narrows the scope to
the operators in DL libraries. Operator testing can be conducted by invoking
the API for each operator (namely, operator-level API), which is typically a
lower-level approach compared to testing high-level APIs. Operators are the
key components for carrying out computational tasks. They are the essential
building blocks for the DL library APIs as well as model handling logic.
Moreover, operators are often implemented with C/C++, meaning that they are
vulnerable to memory errors which are security critical.

###  2.2. Running Example

Figure 1. A running example

Figure 1 shows the source code of OperatorA which is a running example crafted
by modifying the operator Conv2D from TensorFlow. A bug exists in the
ComputeWithThreadPool function (line 26 in Figure 1). From Figure 1, we can
obtain the following observations step-by-step. ❶ Although symbolic execution
can be used for solving path constraints and exploring various program states,
the buggy function can be too complex to handle for symbolic execution. In
this example, ComputeWithThreadPool is using a thread pool which introduces a
tremendous amount of program states. So, symbolic execution is very likely to
encounter the path explosion problem here. Therefore, testing is a more
practical approach to detect bugs in DL operators. ❷ In order to reach the
buggy function, the test inputs must fulfill several input validation
constraints so that the value of output_size is larger than or equal to zero.
Therefore, fulfilling input validation constraints is important for generating
meaningful test inputs to test the core logic of the DL operators. In this
example, the constraints are relatively complex and they are not described in
the documentation. Hence, an approach to extract constraints from the source
code is needed. ❸ To extract the input validation constraints, we need to
identify the input validation code. From the example, we can observe that the
input validation code contains error handling logic to deal with invalid
inputs (line 22 in Figure 1). Thus, error handling logic can help to locate
the input validation code. ❹ Not every line of code before the core logic is
related to input validation. In this example, the call to the CreateThreadPool
function is not relevant with input validation, despite its placement within
the input validation code. Therefore, we need to exclude irrelevant code when
extracting input validation constraints.

##  3\. Approach

Figure 2. Overview of ACETest

###  3.1. Overview

Figure 2 shows the workflow of ACETest. The overall input is the source code
of the target DL operators and the overall output is a set of test inputs
which can crash the DL operators (crashes). The workflow contains three main
steps: validation path extraction, constraint extraction and testing.

Input Validation Path Extraction. ❶ ACETest extracts the basic information of
the DL operators from the source code of the DL library, including the
information shown in Table 1. ❷ ACETest identifies the input validation logic
of the DL operators according to the extracted information in the previous
step. ❸ ACETest extracts the execution paths of the input validation code.

Constraint Extraction. ❹ For every extracted input validation path, ACETest
first identifies the user controllable inputs which can serve as the entrances
for testing. ❺ Then, ACETest propagates the user controllability along the
path and extract the input constraints at the same time. After this step,
ACETest can get the constraints for each extracted input validation path.

Testing. ❻ Given a set of constraints for an input validation path, ACETest
uses Z3 to get the solutions. ❼ ACETest generates test cases by filling up the
constraint solutions and randomly generating the rest. This ensures that the
test cases can both pass the input validation logic and have enough diversity
to explore the core functional logic. ❽ ACETest executes the target DL
operator with the test cases and observes for crashes.

Table 1. Operator Meta Information

Item Name Example (Running Example) Used By Operator Name OperatorA ❶
Operator-level API Name tf.raw_ops.OperatorA ❽ Parameter List x, y, format ❹,
❼ Parameter Type tensor, tensor, int ❺, ❼ Source Code Location
tensorflow/core/kernels/OperatorA.cc ❷

###  3.2. Validation Path Extraction

####  3.2.1. Operator Information Extraction

Table 1 shows the meta information of operators that ACETest extracts from the
code. Operator name is needed in this step for extracting all other
information. Operator-level API name is needed for invoking the DL operators
for testing. Parameter list is useful for locating the user controllable
inputs in the source code of operators and generating test cases. Parameter
types are needed for collecting the constraints and solving them. Source code
locations of the DL operators are used for extracting the input validation
logic.

Figure 3. Input validation path extraction in the running example. Line 22 is
the error-handling function call, while line 26 represents the core functional
logic of the operator. ACETest identifies the input validation code by
performing a backward traversal from line 22, marking all blue nodes as input
validation code. ACETest then extracts the execution paths within the input
validation code and its direct successors. Paths that reach the core
functional logic (line 26) are saved, and in this example, Path C and D are
saved.

####  3.2.2. Input Validation Code Identification

Identifying the input validation code is an important step for extracting
validation paths. In conventional software, distinguishing between input
validation logic and core functional logic automatically can be challenging,
as they are often intertwined. However, DL operators possess two distinct
characteristics which enable the automatic extraction of input validation
logic. ❶ Input validation is always conducted before the core functional logic
in DL operators. DL operators in popular DL libraries (such as TensorFlow and
PyTorch) usually support multiple devices such as Intel CPU, Nvidia GPU, AMD
GPU, and TPU. To optimize hardware resource utilization, these DL operators
implement device-specific core functional code. Consequently, input validation
is uniformly performed prior to entering separate core functional code
tailored for different devices. ❷ In case of input validation failure,
specific error handling functions will be invoked. Since DL operators are
usually executed in parallel as part of DL models, a global execution context
is employed to manage multiple processes. Error handling functions are used
across all operators to notify the context about validation failures.

Based on the two characteristics, ACETest effectively identifies the input
validation code by performing a backward trace from the error handling
function calls on the control flow graph (CFG). Specifically, ACETest employs
a Depth-First Search approach to traverse the CFG and pinpoint the input
validation code. Figure 3 shows how ACETest utilizes the backward traversal
method to identify the input validation code in the running example. To
address the potential issue of path explosion associated with backward
traversal, ACETest sets a threshold to limit the max number of iterations for
the search process. The default value for this threshold is set to 1 million.
To mitigate the risk of missing basic blocks when the fixed threshold is
reached, we propose an online algorithm that dynamically determines whether a
basic-block should be considered as input validation code or not. This
algorithm is invoked only when the threshold is reached, as the DFS process
can already find all the basic-blocks associated with input validation. The
rationale of this algorithm is to perform a quick and approximate check of
reachability from a given basic-block to the error-handling function calls by
examining whether any of the error-handling function calls are in the
successors of the given basic-block. If at least one error-handling function
call can be reached from the basic-block, it is considered part of the input
validation code. The detailed algorithm is shown in Algorithm 1. In Algorithm
1, $current\\_bb$ is the basic-block under examination, and is served as a
parameter. Additionally, $reachable\\_cache$, $unreachable\\_cache$ and
$eh\\_bbs$ are global variables. $reachable_{c}ache$ and $unreachable_{c}ache$
are lists that respectively store the basic blocks marked as reachable and
unreachable, providing a performance boost to the algorithm. $eh\\_bbs$
represents the list of error-handling basic-blocks.

Algorithm 1 Basic-block reachability check.

0: $current\\_bb$, $reachable\\_cache$, $unreachable\\_cache$, $eh\\_bbs$

1: if $reachable\\_cache$.find($current\\_bb$) then

2: return true

3: if $unreachable\\_cache$.find($current\\_bb$) then

4: return false

5: $worklist\leftarrow[{current\\_bb}]$

6: $visited\leftarrow[{current\\_bb}]$

7: while $!worklist.$empty() do

8: $bb\leftarrow worklist.pop()$

9: if $eh\\_bbs.$find($bb$) or $reachable\\_cache$.find($bb$) then

10: $reachable\\_cache$.insert($current\\_bb$)

11: return true

12: for $succ:bb.$successors() do

13: if $!visited.$find($succ$) then

14: $visited.$insert($succ$)

15: $worklist.$insert($succ$)

16: for $bb:visited$ do

17: $unreachable\\_cache$.insert($bb$)

18: return false

####  3.2.3. Path Extraction

After identifying the basic-blocks of the input validation code, ACETest
extracts the execution paths that will be used for constraint extraction in
the next stage. Technically, ACETest can extract two types of paths from the
input validation code and its successors. The first type of paths end up
calling the error-handling functions while the second type of paths lead to
the core functional logic. In practice, the first type of paths never reach
the core functional logic, which is generally much more buggy than the input
validation logic and the error handling logic. Furthermore, missing/wrong
validation checks can also lead to crashes in the functional logic. Therefore,
ACETest ejects the first type of paths and retains only the second type. For
the running example, as shown in Figure 3, Path C and Path D are kept while
Path A and Path B are ejected.

###  3.3. Constraint Extraction

Figure 4. Extracting constraints from a path in the running example. The
column 1 and 3 show the line number for the propagation on its right. Each
node represents a value in the path, the color represents its value type: dark
blue for parameters, light blue for properties, gray for other controllable
values, green for constants, red for non-controllable values. Black arrow
means a propagation goes from left to right, red arrows means non-propagation.
Above each arrow is a current function/instruction, and bellow the arrow is
the matched propagation rule. The constraints constructed when propagating are
labeled with the same number as the propagation rule.

This stage aims at extracting constraints from the paths extracted in the
previous stage. Symbolic execution is a common solution for extracting
constraints from programs. However, complex structures such as tensor are
common in DL operators. The overhead of blindly symbolizing all parameters in
DL operators would be unacceptable. Thus, to extract constraints from the
given paths in DL operators in a light-weight manner, we propose a novel
constraint extraction technique for DL operators. The technique identifies
user-controllable parameters(3.3.1) at first and collects constraints for them
by traversing the path from the first instruction to the last instruction.
During the traversal process, other user-controllable values are identified
through controllability propagation(3.3.2). A constraint model and a set of
propagation rules are introduced to restrict the propagation, minimizing the
overhead and extraneous constraints. Furthermore, constraint construction
rules are applied in the propagation process to construct constraints for
user-controllable values based on each instruction.

####  3.3.1. User-Controllable Parameter Identification

User-controllable parameters play a crucial role in constraint extraction.
Before extracting constraints in paths, we have to identify all of the user-
controllable parameters in DL operators. User-controllable parameters are
passed to operators in different ways across different DL libraries, including
direct transmission via operator function parameters or through dedicated
function calls that retrieve parameters from the execution context. For the
first kind, identifying user-controllable parameters is straightforward. And
the second kind requires manual identification and annotation of relevant
functions within the target DL library. The user-controllable parameters are
then recognized by identifying calls to these functions.

For Example, PyTorch passes user-controllable parameters directly through the
parameters of the operator functions, while TensorFlow through specific
function calls.

####  3.3.2. Controllability Propagation

We traverse the path and propagate the controllability from the values of
user-controllable parameters. Constraints are extracted in the propagation
process. But propagating blindly to every value polluted by controllable
values can result in increasing the overhead of constraint extraction,
collecting redundant constraints, and thus burdening constraint solving.
Hence, a controllability propagation technique is proposed to address the
problem. The technique consists of constraint model, propagation rules, and
constraint construction rules. The constraint model helps to reduce the
propagation scope. It provides a foundation for the application of propagation
rules, which dictate the propagation behavior of each instruction within the
given path. Simultaneously, the constraint construction rules are employed to
generate corresponding constraints.

Constraint model. The basic idea of controllability propagation is to focus
only on values and instructions that might be related with constraints.
According to our knowledge, most constraints for tensors only constrain their
properties such as shape and number of dimensions. Values of elements in
tensors are not constrained in most cases. Thus, the propagation can be
restricted by focusing on specific properties of each parameter. Based on the
above observation, we propose a general constraint model for DL operator
parameters to guide the propagation process. The model specifies the
properties that are commonly constrained for each type of parameter, as shown
in Table 2.

Table 2. Constraint model

Argument Property Property Description Type Type tensor $dtype$ dtype The data
type of the tensor. $ndim$ int The number of dims of the tensor, also the
length of the tensor’s shape. $num\\_element$ int The total number of elements
in the tensor. $shape[]$ list of int The shape of the tensor. list
$element\\_type$ type The type of the list’s elements. $length$ int The length
of the list. $iter$ int The iterator value of the list, a general
representation of all the values in the list. $value[]$ list of
$element\\_type$ The concrete value of the list. string $value$ string The
value of itself. $format\\_id$ int The format id of this string if it is a
format string that specifies the dimension order of input tensors. int $value$
int The value of itself. float $value$ float The value of itself. bool $value$
bool The value of itself.

Propagation rules. With the help of constraint model, we construct a set of
propagation rules to identify properties included in the model and other
intermediate values related to constraints. As each instruction is traversed,
we match that instruction to one of the propagation rules and perform the
corresponding propagation behavior. There are three kinds of propagation
rules: (1) parameter to property; (2) property to property; (3) general
propagation.

Figure 5. Propagation rules for tensors

Parameter to property rules define the propagation behaviour from a parameter
to one of its properties. The blue arrows in Figure 5 show parameter to
property rules for tensors. For example, $s=t.GetShape()$ is a behaviour
propagating the controllability from parameter $tensor\ t$ to $s$, and $s$ is
then bound to $t$’s property $shape$.

Properties of a parameter can propagate from one to another in specific
conditions. The black arrows in Figure 5 show the property to property rules
for tensor. For example, the behavior expressed by $n=t.shape.GetLength()$
propagates the controllability from property $shape$ of $tensor\ t$ to another
property $ndim$, and $n$ is then bound to $t$’s property $ndim$.

The first two kinds of rules are involved with transformation between
parameters and properties, and transformation between properties themselves.
Function calls to specific functions that get properties from parameters or
properties are mapped into behaviours defined in these rules. For instance,
calls to $Tensor::shape()$ in TensorFlow are mapped to $GetShape$. On the
other hand, general propagation rules are employed to handle propagation in
instructions taht do not involve such transformations, such as numerical
calculation instructions and addressing instructions. The basic idea of
general propagation rules is to propagate to the output values of an
instruction only when all input values are controllable or constant. The
general propagation rules are constructed for all types of instructions in
LLVM bit-code.

Utilizing the three kinds of rules, we conduct a traversal from the initial
instruction to the final instruction along each path. During the traversal, we
propagate the controllability from the user-controllable parameters to other
values in a restricted manner based on the rules. The first two kinds of rules
help us identify the values representing properties defined in the constraint
model. And the third kind of rules propagate facilitates the propagation of
controllability to other values related to these properties.

Constraint construction rules. The rules of constraint construction composites
of two parts: natural constraint construction and propagation constraint
construction.

Natural constraint construction rules are used to restrict the properties of
different parameters based on the nature of them. These constraints must be
fulfilled by all parameters, otherwise it would contradict the construction of
a valid parameter. For example, a tensor’s shape length must equal its number
of dims. Additionally, to make sure the size of generated parameters are
acceptable, we add rules to limit the size of tensor and list in this step.
Natural constraints construction rules are applied to each parameter before
the path traversal.

Propagation constraint construction rules are applied during the propagation
process. As controllability is propagated from the input values to the output
values of an instruction, a constraint is constructed to capture the semantics
of the instruction. This process involves mapping each type of instruction to
its corresponding rule. Furthermore, to improve the accuracy and efficiency of
constraint construction, we manually implement construction process for common
functions frequently used in input validation. This allows for the skipping of
the propagation and constraint construction process within these functions.

####  3.3.3. Constraint Extraction Example

Figure 4 shows how ACETest extracts constraints from path C (Figure 3) in the
running example. The detail process is described as follows:

  * •

Line 1-5: The controllable values $tensor\ x$, $tensor\ y$ and $int\ format$,
are identified by matching the called functions $input$ and $GetAttr$. In the
meantime, ACETest dose not enter $input$ and $GetAttr$ as they are already
handled.

  * •

Line 7: Function $CreateThreadPool$ is called without any controllable inputs,
but ACETest still enters its body to check for constant return values or
potential calls to specific functions that could provide input. But nor of the
mentioned situations happens, thus $*thread\\_pool$ is not controllable.

  * •

Line 8: Similarly, function $NumThreads$ is traversed but its return value
$var8$ is not controllable. Thus, the instruction $add$ does not match the
propagation rule for it. As the rule requires all its parameters to be
controllable or constant, but one of its parameter is not controllable or
constant. Thus, its result $t$ is not controllable, and no constraints are
constructed.

  * •

Line 10: The function $Tensor::dims()$ called here is matched with propagation
rule $GetNdim$ for tensors, and its implicit argument is tensor $x$. Thus the
return value of this function call, $var10\\_1$, is propagated as
controllable, and the constraint construction rule bound to $GetNdim$ is also
triggered, resulting in the construction of a corresponding constraint (❶).
And then, the propagation rule for the $Add$ instruction is fulfilled because
its parameters are either constant or controllable. Thus $channel\\_dim$ is
propagated to be controllable and a corresponding constraint construction rule
for $Add$ is triggered (❷).

  * •

Rest of the path: In the rest of the path, propagation rules and constraint
construction rules are applied in the same manner for each instruction.
Finally, a total of 11 constraints are constructed as a result.

###  3.4. Testing

####  3.4.1. Constraints Solving

The constraints are stored as SMT formulas after constraint extraction. Thus,
ACETest can leverage Z3 for sampling random solutions from the complex SMT
formulas with bit-vectors, arrays, and uninterpreted functions. As Z3 does not
have a built-in batch sampling function, in order to obtain diverse solutions,
we continuously insert new constraints to block the newly obtained solution.
After this step, ACETest can get a batch of unique solutions for the
constraints.

####  3.4.2. Test Case Generation

ACETest uses the constraint solutions for the constrained properties and
randomly generates the remaining unconstrained properties. To generate
additional edge cases, ACETest mutates the dimension sizes of tensors, int and
float values by assigning them extremely large values with a probability $p$.
Moreover, ACETest wraps the test inputs with a Python script which invokes the
operator-level APIs , serving as the final test code for execution.

####  3.4.3. Test Case Execution

We observe that DL libraries suffer a lot from the cold boot overhead (about
1-5 seconds) for each run. Thus, ACETest maintains a test process which keeps
acquiring and executing the final test code from a queue until it crashes.
After a crash, ACETest will restart the test process and continue testing.
Since there are much more normal test cases than crashing ones, the test
process can greatly increase the testing speed of ACETest by allowing it to
execute up to 300 test cases per second.

##  4\. Implementation

We implemented ACETest in about 5K lines of C++ code and 3K lines of Python
code. Input validation path extraction and constraint extraction are
implemented as a compiler pass based on LLVM (Lattner and Adve, 2004). We
employed SVF (Sui and Xue, 2016) to generate Value Flow Graphs (VFGs) and
CFGs. To avoid path explosion and ensure that constraints are solvable, we
only unrolled loops once and ignored loop-continuation condition. The
constraints are constructed, processed, and solved based on Z3.

Preprocessing. For efficiency, ACETest leverages LLVM to compile single
operator code file into bitcode and link it with necessary libraries.

Input Validation Path Extraction. We traverse from each operator’s entry to
explore all paths in validation code. If the code of operator is divided into
several blocks with different entries, we extract paths from different code
blocks separately and combine them for the input generation process.

Testing. The generated python scripts were executed with target DL library in
different modes. We tested TensorFlow’s operators in three modes, i.e., native
mode, OneDNN mode (executing operators with Intel-optimized operators) and
CUDA mode (executing operators with CUDA operators). PyTorch’s operators were
tested in native mode and CUDA mode. We reproduced all crashes in order to
filter out false positives and identified them based on their return code.

Extending for other DL libraries. ACETest is designed to be easily extended to
new DL libraries. To support a new DL library, several interfaces in three
parts, namely, preprocessing, constraint extraction, and test case generation,
need to be implemented. In the preprocessing part, a script is required to
extract the operator list and meta info of the operators. We wrote 300 lines
of Python code for both TensorFlow and PyTorch. In the constraint extraction
part, some input property handling functions must be manually specified to
enable ACETest to understand their mechanism and determine the propagation
rules, such as the $GetDim$ function of tensors. Developers can also add more
propagation rules for better performance. We wrote 1000 lines of C++ code for
both TensorFlow and PyTorch. Finally, in the test case generation part, Python
code is needed for building the actual test cases that invoke the specific DL
library APIs. This part requires about 100 lines of Python code. Compared to
the size of ACETest, the amount of manual work required to support a new DL
library is minimal.

##  5\. Evaluation

###  5.1. Experiment Setup

####  5.1.1. Research Questions

Our evaluation aims to answer the following research questions (RQs).

  * •

RQ1. (Constraint Extraction.) How effective is ACETest in extracting
constraints from DL operator code? (§5.2)

  * •

RQ2. (Test Case Generation.) Can the extracted constraints enable ACETest to
generate high-quality test cases? (§5.3)

  * •

RQ3. (Bug Detection.) How is the bug detection capability of ACETest? (§5.4)

####  5.1.2. Dataset Selection.

To investigate the three research questions, we collected operator-level APIs
from two of the most widely used DL libraries, TensorFlow 2.9.0 and Pytorch
1.13.0, and applied several exclusion criteria to filter out APIs that ❶ have
unsupported input parameters such as handler, ❷ cannot be executed
independently as they rely on other APIs, ❸ are deprecated, ❹ only support TPU
mode, or ❺ are not explicitly bound to an operator. Furthermore, we selected
only one of the APIs that called the same operator to prevent redundancy.
Following these guidelines, we identified a total of 610 and 485 operator-
level APIs for Tensorflow 2.9.0 and PyTorch 1.13.0, respectively.

####  5.1.3. Baselines.

We compared ACETest with several state-of-the-art approaches to assess its
effectiveness.

  * •

DocTer (Xie et al., 2022), a documentation-guided fuzzing technique for
testing DL API functions.

  * •

DocTer*, a variant of DocTer that we implemented, which transforms DocTer’s
constraints into ones following the format of ACETest and then generates input
using the input generation component of ACETest 111The input generation
component of ACETest requires a specific type for each parameter, while DocTer
dynamically infers the type during the input generation phase. Therefore,
DocTer* uses the types extracted by ACETest and obtains other constraints from
DocTer’s results..

  * •

ACETest*, a baseline that we implemented, which leverages the meta information
(mentioned in Table 1) to generates test cases without relying on constraints
extracted from the source code.

  * •

FreeFuzz (Wei et al., 2022), a mutation-based fuzzing technique that extracts
DL high-level API usages from open source.

  * •

DeepREL (Deng et al., 2022), a fuzzing technique that infers relational high-
level APIs by analyzing APIs sharing similar input and outputs.

To answer RQ1, we compared the constraints extracted by ACETest and DocTer, as
other tools were unable to extract constraints, and we manually analyzed the
recall and precision of ACETest’s constraint extraction. To answer RQ2, we
compared the branch coverage and pass rate of ACETest with DocTer, DocTer* and
ACETest*, as FreeFuzz and DeepREL concentrate on high-level APIs and cannot be
easily adapted to our test targets. To answer RQ3, we compare the bugs
detected by ACETest with the other four tools.

####  5.1.4. Metrics.

To assess ACETest’s and DocTer’s constraint extraction capabilities, we
evaluated them with the following metric.

  * •

Constraint Number of the Property (CNP): The CNP indicates the frequency of a
specific property being constrained among all extracted constraints. The CNP
for property $dtype$ of tensor is calculated using the following equation:

(1) $CNP=\sum_{p\in tensors}IsConstrained(p.dtype)$

Here, $tensors$ is a set of all parameters with tensor type among all the
constraints. By having more properties being constrained and each property
being constrained more frequently, we can indicate a higher diversity of the
constraints present.

To evaluate the quality of test cases, we execute the generated test cases
with target DL library, and obtain the quality in two aspects:

  * •

Pass Rate: Pass rate evaluates ratio of generated test cases that can pass all
input validation checks. And therefore demonstrates the validity of generated
test cases (Xie et al., 2022). Pass rate of a test round for an API can be
calculated with the following equation:

(2) $PassRate=\frac{api.validate\\_cases.size()}{api.test\\_cases.size()}$

  * •

Branch Coverage: Branch coverage is widely adopted in software testing for
measuring the quality of the test cases (Chen et al., 2019). It reveals the
path exploration ability of test cases.

####  5.1.5. Evaluation Configuration.

Our experiments were run on a machine with Intel Xeon CPU (24 cores, 2.20
GHz), NVIDIA V100 GPU, Ubuntu 20.04, and Python 3.8. We test 2000 rounds for
each API until (1) the test time of the API reached 30 minutes; (2) 50 crashes
or round timeouts are triggered. As DocTer generates VI (Violating Input) and
CI (Conforming Input) each for 1000 rounds, we compute its pass rate only for
CIs and branch coverage for both VIs and CIs. In RQ2 and RQ3, all experiments
are conducted 5 times to reduce the impact of randomness. For RQ2, the
reported results are the average of 5 test runs. For RQ3, we used all bugs
detected in 5 test runs as the final results. In addition, to ensure fair
comparison, FreeFuzz and DeepREL, which target high-level APIs, were
configured to run 2000 times for each API and were limited to run within 72
hours (all other tools can complete the test runs within 72 hours).

###  5.2. RQ1: Effectiveness of Constraint Extraction

####  5.2.1. Comparison with DocTer.

DocTer utilizes documents to extract API constraints. And DocTer was only able
to extract constraints for 608 APIs in tensorflow and 205 APIs in PyTorch due
to the unavailable of documents for other APIs. To ensure a fair comparison,
we only considered the constraints extracted from these APIs.

Table 3 presents the CNP results. ACETest extracted 3280 constraints in total,
almost twice the number of constraints extracted by DocTer, which is 1670. In
terms of parameter properties, ACETest is more effective than DocTer,
especially in terms of the length and value properties of the list type, where
DocTer fails to extract any constraints. Since the tensor is the most common
parameter of the operator, it has the largest number of corresponding
constraints. Moreover, $dtype$-related constraints can be expressed in simple
natural language, so DocTer can easily obtain such constraints from the
documents, which leads to the similar constraint numbers of dtype in the
table.

Table 3. CNP of constraints extracted by DocTer and ACETest

Parameter Type Base Type list tensor Total Property value dtype length value
dtype dim shape DocTer 220 256 0 0 919 212 63 1670 ACETest 402 283 176 68 1168
639 554 3280

####  5.2.2. Manual Validation.

To examine the completeness and accuracy of the extracted constraints by
ACETest, we randomly selected 25 operators from each of TensorFlow and
PyTorch, and conducted a manual verification. The manual analysis was
conducted independently by three authors of this paper, and the final results
reached unanimous agreement among all three authors. The constraints for each
operator consist of multiple SMT scripts, with each script corresponding to a
path in the input validation code of the operator that passes the check. As
some operators have hundreds of scripts, each contains hundreds of lines of
code. For example, Conv2DOp of TensorFlow has 104 scripts, with 998 lines of
code each222The constraints of Conv2DOp extracted by ACETest can be downloaded
at https://github.com/shijy16/ACETest. Manually analyzing all of them would be
too labor-intensive. Hence, in cases where the number of scripts for an
operator exceeded 10, we randomly chose 10 scripts for verification purposes
(64% of the operators had 10 or fewer scripts). We evaluate the extracted
constraints in two dimensions: ❶ The integrity of individual constraint
scripts ($Recall_{s}$), calculated by determining the proportion of satisfied
checks within the script’s corresponding path. ❷ The coverage of all
constraints on the checking paths in an operator ($Recall_{op}$). Precision in
the extracted constraints and the time cost for verifying each operator are
also recorded.

Table 4. Manual analysis result for constraints extraction

$Recall_{s}$ $Recall_{op}$ Precision Avg. Cost(min) TensorFlow 87% 90% 100% 24
PyTorch 68% 75% 100% 23

The results are shown in Table 4. Overall, ACETest is able to extract complete
constraints for most operators in TensorFlow and PyTorch and cover all paths
with 100% precision. However, constraints in some operators are not fully
extracted. We examined the operators with incomplete constraint extraction and
identified several main reasons: ❶ Loops in the input validation code: We only
unrolled the loop once and ignored the loop condition to avoid false
positives, which also resulted in missing constraints within the loop. ❷
Incomplete compilation: Due to the large size of DL libraries, we could not
perform static analysis on the entire code base. As a fallback, we only
compiled the code file of each single operator and linked it with necessary
code files, resulting in some functions not being linked. ❸ C++ pointers:
Despite the implementation of virtual memory in ACETest to handle pointers,
the inaccuracy of current static analysis can still result in false negatives.
Additionally, ACETest is currently unable to retrieve function pointers. ❹
Constraints on tensor’s value or number of elements: These properties are out
of the scope of ACETest’s constraint model, as they are rare and too expensive
too handle. Moreover, the manual verification process of constraints for each
operator required an average of 23-24 minutes, and manually extracting
constraints could take up to 10 times longer. The manual extraction process
involves identifying each path, verifying the logic in each path, and
formatting the constraints into SMT scripts. In contrast, ACETest can extract
constraints for most operators in 1 minute.

Result for RQ1: Compared to DocTer, ACETest is capable of extracting more
constraints, and its precision and recall in constraints extraction are
satisfactory.

###  5.3. RQ2: Effectiveness of Test Case Generation

To investigate the effectiveness of test case generation, we compared ACETest
against three baselines (i.e., ACETest*, DocTer, and DocTer*) in terms of pass
rate and branch coverage.

####  5.3.1. Pass Rate.

Table 5 shows the pass rate results of different techniques. We observe that
ACETest significantly outperforms DocTer, DocTer* and ACETest*, achieving the
state-of-the-art result of 32.51% and 43.66% pass rate on TensorFlow and
PyTorch. Compared with DocTer, ACETest increased the pass rate by 162.60% and
138.58% on TensorFlow and PyTorch, respectively. It also achiev-es significant
pass rate improvements compared to DocTer* (47.73% and 39.22% on TensorFlow
and PyTorch) and outperforms ACETest* by 34.51% and 36.65%. These results
demonstrate ACETest’s ability to generate valid test cases that thoroughly
explore the core functional code.

Table 5. Comparison on pass rate

DocTer* DocTer ACETest* ACETest TensorFlow 22.00% 12.38% 24.17% 32.51% PyTorch
31.36% 18.3% 31.95% 43.66%

####  5.3.2. Branch Coverage.

Figure 6 presents the average branch coverage of each operator. It
demonstrates that among the four tools, ACETest achieves the highest branch
coverage. And the coverage of ACETest keeps growing as the number of testing
rounds increases, and the upward trend persists until the end of the testing
process. The results suggest that ACETest has a higher branch coverage in DL
operators and continuously generates diverse test cases that explore new
paths.

Table 5 and Figure 6 indicate that DocTer had relatively lower overall pass
rate and branch coverage. This can be attributed to the incorrect and
incomplete extraction of parameter types from the documents, resulting in
lower coverage and pass rate of certain operators. In contrast, the other
three tools use the parameter types obtained by ACETest from the operator
registration, which are less prone to errors. Additionally, at the 1000th
round, DocTer switches from generating test cases that satisfy the constraints
to generating test cases that violate the constraints, which leads to a sharp
increase in coverage.

Figure 6. The average branch coverage for each operator compared with
baselines. The curve represents the average of 5 tests, with a 95% confidence
interval.

Result for RQ2: Compared to the three baselines (i.e., DocTer, DocTer*, and
ACETest*), ACETest generates a more varied and valid set of test cases with
the aid of extracted constraints.

###  5.4. RQ3: Effectiveness of Bug Detection

In this section, we performed an evaluation to assess the effectiveness of bug
detection. The overall evaluation results are listed in Figure 7 and Table 6.

Figure 7. The Effectiveness of Bug Detection Table 6. The Distribution of
Different Types of Bugs Detected in TensorFlow and PyTorch

Tools TensorFlow PyTorch Total ABRT FPE SEGV Total ABRT FPE SEGV Total
FreeFuzz 22 0 0 22 0 0 1 1 23 DeepREL 2 1 0 3 0 0 0 0 3 DocTer* 42 2 21 63 0 0
5 5 68 DocTer 42 0 15 57 0 0 0 0 57 ACETest* 54 0 24 78 1 1 29 31 109 ACETest
85 11 35 131 2 2 33 37 168

####  5.4.1. Result Analysis.

In particular, as we can see from Figure 7, the bar chart in the left-hand
side illustrates the total number of bugs found by each tool. The two vertical
bar charts together present the number of bugs (see the upper vertical bar
chart) that can be detected uniquely by the corresponding tool(s) (see the
lower vertical bar chart with lined black dots to represent the use of the
corresponding tool(s)). ACETest significantly outperformed ALL five state-of-
the-art tools. It could detect the most 168 bugs and further detected 63
unique bugs, which is a 37.50% improvement. ACETest* performed the second, by
finding 109 ($47.81\%$) while the four remaining tools, namely DeepREL,
FreeFuzz, DocTer, and DocTer*, were less effective, reporting between 3 and 70
bugs, with an average of 38.25 ($\frac{3+23+57+70}{4}=38.25$) bugs.

Besides, we analyzed the distribution of three types of crashes, namely Abort
(ABRT), Floating Point Exception (FPE), and Segmentation Fault (SEGV), over
all bugs. The results are presented in Table 6. The findings indicate that
ACETest detected more bugs of each crash type in both TensorFlow and PyTorch
compared to other tools. Specifically, ACETest was able to detect 1.95 to 55
times more bugs than SOTA techniques (e.g., DeepREL and DocTer). Among all the
bugs detected by ACETest, 29 bugs in PyTorch and 79 bugs in TensorFlow were
new, of which 87 were confirmed by the developers, and 35 were fixed.

It is noteworthy that both DeepREL and FreeFuzz exhibit relatively lower
performance compared to their original results. After careful investigation,
two primary factors were identified: ❶ Test oracle. Both approaches employ
distinct test oracles to identify bugs, excluding crash bugs. FreeFuzz detects
wrong-computation bugs and performance bugs, while DeepREL additionally
targets relational API bugs. To ensure a fair comparison, our experiments only
consider crash bugs for all tools. ❷ Target version. The versions of
TensorFlow and PyTorch used in their respective papers are significantly older
than the version we utilized for testing. Consequently, the update in version
has led to a decrease in the occurrence of superficial bugs.

####  5.4.2. Case Study.

Furthermore, we conducted a case study to illustrate the efficacy of ACETest.
The bug resided in the operator Conv2D of TensorFLow. The buggy input is shown
in Figure 8. Conv2D consists of 7 parameters and complex input constraints.
For instance, when data_format is ”NHWC”, the first and third elements of
strides must be 1. Furthermore, the shape of output tensor is calculated and
validated using intricate logic, with at least 5 parameters involved in the
calculation. None of the other tools were able to generate valid test cases
that passed the checks and entered the functional code, where the bug was
located. Specifically, the bug could be triggered when the functional code was
executed with input having zero elements. Only ACETest was able to generate
valid test cases and trigger the bug. This case study demonstrates ACETest’s
superiority in extracting constraints, as this bug is detected only by
ACETest.

####  5.4.3. Failure Analysis.

Although ACETest detected 63 unique bugs that were not found by the five
baselines, it missed 60 bugs that these tools were able to detect. After
analyzing these bugs, we identified four main reasons for ACETest’s failure to
detect them: ❶ FreeFuzz and DeepREL have different test targets than ACETest,
resulting in unique bugs that they are able to detect. ❷ DocTer implements an
input mutation technique that can generate more edge cases, allowing it to
find bugs that other tools may miss. ❸ Since all tools generate test cases
with randomness, the results can be unpredictable. ❹ Although input validation
code has fewer bugs than functional code, some bugs may still be present.
However, ACETest only generates test cases to test the core functional code,
not input validation code, which could lead to missing bugs.

Result for RQ3: ACETest outperforms state-of-the-art approaches in terms of
bug detection. In particular, ACETest found the most 168 ($73.68\%$) bugs and
further found 63 unique ones, which is a 37.50% improvement.

Figure 8. PoC for Conv2D in TensorFlow

##  6\. DISCUSSION

Threats to Validity. A potential threat to the validity of our study is the
randomness of the testing process, which may lead to our results being
specific to certain cases. To mitigate this risk, we conducted five rounds of
testing and generated 2000 test cases for each API in each round to ensure
that our results are consistent and not influenced by randomness. However, it
is still possible that our testing results may not fully capture the behavior
of the tools under all possible scenarios. Another potential threat to the
validity of our study is the subjectivity of the manual analysis process. To
address this risk, we had three experts conduct independent analyses, and we
cross-validated the results to reduce the impact of subjectivity on our
findings. Finally, ACETest relies on the SVF tool to extract the VFG and CVG,
which may have implementation flaws that could affect the accuracy of our
results.

Bug Identification. When performing DL operator testing, we only consider
crashes as bugs and ignore some bugs that do not crash, such as bugs with
incorrect functional implementation. These bugs may be detected with
differential testing used in (Gu et al., 2022; Wei et al., 2022). Besides,
with ASAN (Jeon et al., 2020) enabled, we may detect more bugs.

##  7\. RELATED WORK

DL Operators Testing. DL operators are the fundamental components of DL
libraries, bugs in operators may affect the behavior of DL models. As a
consequence, several approaches have been proposed (Zhang et al., 2021a, b;
Wei et al., 2022). To detect precision bugs in operators, Predoo (Zhang et
al., 2021b) treats DL operators testing problem as a searching problem to
maximize output precision errors. FreeFuzz (Wei et al., 2022) extracts API
usage via mining from open source. It collects the types and values of each
parameter, and shapes of input/output tensors by running all the code/models,
and performs differential testing for each API. DocTer (Xie et al., 2022)
proposes to extract DL-specific input constraints for DL API functions by
analyzing API documentation. With a set of manually annotated API documents
with precise constraint information, DocTer can derive constraint extraction
rules, which can be used to predict API parameter constraints. DeepREL (Deng
et al., 2022) focuses on inferring relational APIs by analyzing APIs sharing
similar input parameters and outputs. With formalizing the notion of value
equivalence and status equivalence for relational APIs, it can find potential
inconsistencies with testing. IvySyn (Christou et al., 2022) utilizes the
static typing feature of operators’ native code (C/C++) through
instrumentation and direct of operators’ native APIs. As a result, it can
generate inputs with the correct type, which sets it apart from other Python
API testing approaches.

These methods share the same goal with ours. They extract API usage or
operator constraints from open source or document, which are limited or
incorrect. Instead, we extract constraints by analyzing code of DL libraries.
These constraints are more precise, and can express the relations among each
parameter.

DL Library Testing. To detect bugs in DL libraries, multiple techniques
(Nejadgholi and Yang, 2019; Guo et al., 2020; Wang et al., 2020; Luo et al.,
2021; Wang et al., 2022; Gu et al., 2022; Wu et al., 2022; Yang et al., 2023)
have been proposed to test them by generating or mutating DL models. Luo et
al. (Luo et al., 2021) design a graph-based fuzz testing method, which
introduced six different mutations by exploring combinations of model
structures, parameters, and data inputs. EAGLE (Wang et al., 2022) proposes to
test a single DL library with generating equivalent graphs, which use
different APIs, data types, or optimizations to achieve the same
functionality. CRADLE (Pham et al., 2019) takes pre-trained model as input and
performs cross-implementation inconsistency checking to detect bugs. Instead
of focusing on detecting bugs in model inference phase, Muffin (Gu et al.,
2022) proposes to make differential testing feasible in the model training
phase by tailoring a set of metrics to measure the inconsistencies between
different DL libraries. MEMO (Li et al., 2022a) proposes a coverage based
model generation technique with a customized Markov Chain Monte Carlo
algorithm to explore new layer types, layer pairs, and layer parameters.
LLMFuzz (Deng et al., 2022) directly adopts large pre-trained Language model
to generate input programs for fuzzing DL libraries.

These approaches focus on detecting either logic bugs by differential testing
in single or multiple DL libraries, or memory bugs by monitoring crashes. One
common challenge is how to generate various models. Instead, we pay attention
to detect bugs in operators, and try to generate diverse parameter inputs of
operators, which are different from model.

Symbolic Execution. To test program deeper, many researchers proposed to
augment fuzzing through symbolic execution (Stephens et al., 2016; Noller et
al., 2018; Wu et al., 2018; Peng et al., 2019). However, symbolic execution
suffers from path explosion problem and constraint solving limitations. To
make it more practical, David et al. (Trabish et al., 2018) represents chopped
symbolic execution that leverages various on-demand static analyses at runtime
to automatically exclude code fragments. Specifically, it allows users to
specify uninteresting parts of code to exclude during the analysis. PHchop
(Singh and Khurshid, 2020) introduces a parallel approach to chopped symbolic
execution. Learch (He et al., 2021) proposes a learning-based strategy, that
can select promising states for symbolic execution. Cha et al. (Cha et al.,
2022) proposes a method that can automatically learn search heuristics by
defining a class of search heuristics and finding an optimal heuristic for
each subject program efficiently. Directed Symbolic Execution (DSE) is a
technique that explores specific paths and collects and solves the relevant
constraints instead of all possible paths. It is used in various testing
techniques, such as DART (Sen, 2005), to reduce the limitations of symbolic
execution. DSE is similar to the constraint extraction technique of ACETest.
However, while DSE extracts constraints for all values, ACETest focuses on
constraints for certain types of values.

##  8\. Conclusion

In this paper, we present a technique called ACETest, which can automatically
extract input validation constraints to aid DL operator testing. Specifically,
ACETest can automatically identify the input validation code in DL operators,
extract the related constraints and build test cases according to the
constraints. ACETest has demonstrated superior performance on popular DL
libraries, TensorFlow and PyTorch. Experiments results demonstrate that
ACETest is capable of extracting 96.4% more constraints than DocTer, which is
a SOTA technique for extracting constraints from documentation. Moreover,
ACETest can detect 1.95 to 55 times more bugs than SOTA techniques. In total,
we have used ACETest to detect 108 previously unknown bugs on TensorFlow and
PyTorch, with 87 of them confirmed and five of them assigned with CVE IDs.

## Acknowledgment

The authors would like to thank the anonymous reviewers for their helpful
feedback on an earlier version of this paper. This work is partly supported by
National Key R&D Program of China under Grant #2022YFB3103900, Strategic
Priority Research Program of the CAS under Grant #XDCO2030200 and Chinese
National Natural Science Foundation (Grants #62032010, #62202462).

## References

  * (1)
  * Abadi et al. (2016) Martín Abadi, Paul Barham, Jianmin Chen, Z. Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek Gordon Murray, Benoit Steiner, Paul A. Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zhang. 2016\.  TensorFlow: A system for large-scale machine learning.  _12th USENIX Symposium on Operating Systems Design and Implementation, OSDI_ (2016).
  * Ahmad et al. (2020) Wasi Uddin Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai-Wei Chang. 2020.  A Transformer-based Approach for Source Code Summarization.  _ArXiv_ abs/2005.00653 (2020).
  * Cadar et al. (2011) Cristian Cadar, Patrice Godefroid, Sarfraz Khurshid, Corina S. Pasareanu, Koushik Sen, Nikolai Tillmann, and Willem Visser. 2011\.  Symbolic execution for software testing in practice: preliminary assessment.  _2011 33rd International Conference on Software Engineering (ICSE)_ (2011), 1066–1071.
  * Cai et al. (2022) Yuandao Cai, Chengfeng Ye, Qingkai Shi, and Charles Zhang. 2022\.  Peahen: fast and precise static deadlock detection via context reduction.  _Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ (2022).
  * Cha et al. (2022) Sooyoung Cha, Seongjoon Hong, Jiseong Bak, Jingyoung Kim, Junhee Lee, and Hakjoo Oh. 2022\.  Enhancing Dynamic Symbolic Execution by Automatically Learning Search Heuristics.  _IEEE Transactions on Software Engineering_ 48 (2022), 3640–3663.
  * Chen et al. (2019) Peng Chen, Jianzhong Liu, and Hao Chen. 2019.  Matryoshka: Fuzzing Deeply Nested Branches.  _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security_ (2019).
  * Christou et al. (2022) Neophytos Christou, Di Jin, Vaggelis Atlidakis, Baishakhi Ray, and Vasileios P. Kemerlis. 2022\.  IvySyn: Automated Vulnerability Discovery for Deep Learning Frameworks.  _ArXiv_ abs/2209.14921 (2022).
  * de Moura and Bjørner (2008) Leonardo Mendonça de Moura and Nikolaj S. Bjørner. 2008.  Z3: An Efficient SMT Solver. In _International Conference on Tools and Algorithms for Construction and Analysis of Systems_.
  * Deng et al. (2022) Yinlin Deng, Chun Xia, Haoran Peng, Chenyuan Yang, and Lingming Zhang. 2022.  Fuzzing Deep-Learning Libraries via Large Language Models.  _ArXiv_ abs/2212.14834 (2022).
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  _ArXiv_ abs/1810.04805 (2019).
  * Dudina and Belevantsev (2017) IA Dudina and AA Belevantsev. 2017.  Using static symbolic execution to detect buffer overflows.  _Programming and Computer Software_ 43 (2017), 277–288.
  * Fan et al. (2019) Gang Fan, Rongxin Wu, Qingkai Shi, Xiao Xiao, Jinguo Zhou, and Charles Zhang. 2019\.  SMOKE: Scalable Path-Sensitive Memory Leak Detection for Millions of Lines of Code.  _2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE)_ (2019), 72–82.
  * Gu et al. (2022) Jiatao Gu, Xuchuan Luo, Yangfan Zhou, and Xin Wang. 2022\.  Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing.  _2022 IEEE/ACM 44th International Conference on Software Engineering (ICSE)_ (2022), 1418–1430.
  * Guo et al. (2020) Qianyu Guo, Xiaofei Xie, Yi Li, Xiaoyu Zhang, Yang Liu, Xiaohong Li, and Chao Shen. 2020.  Audee: Automated Testing for Deep Learning Frameworks.  _2020 35th IEEE/ACM International Conference on Automated Software Engineering (ASE)_ (2020), 486–498.
  * He et al. (2021) Jingxuan He, Gishor Sivanrupan, Petar Tsankov, and Martin T. Vechev. 2021.  Learning to Explore Paths for Symbolic Execution.  _Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security_ (2021).
  * He et al. (2016) Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. 2016\.  Deep Residual Learning for Image Recognition.  _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ (2016), 770–778.
  * Jeon et al. (2020) Yuseok Jeon, Wookhyun Han, Nathan Burow, and Mathias Payer. 2020\.  FuZZan: Efficient Sanitizer Metadata Design for Fuzzing. In _USENIX Annual Technical Conference_.
  * King (1976) James C King. 1976\.  Symbolic execution and program testing.  _Commun. ACM_ 19, 7 (1976), 385–394.
  * Lattner and Adve (2004) Chris Lattner and Vikram S. Adve. 2004.  LLVM: a compilation framework for lifelong program analysis & transformation.  _International Symposium on Code Generation and Optimization, 2004. CGO 2004._ (2004), 75–86.
  * Li et al. (2022b) Hangyu Li, N. Wang, Xi Yang, Xiaoyu Wang, and Xinbo Gao. 2022b.  Towards Semi-Supervised Deep Facial Expression Recognition with An Adaptive Confidence Margin.  _2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ (2022), 4156–4165.
  * Li et al. (2022a) Meiziniu Li, Jialun Cao, Yongqiang Tian, Tsz On Li, Ming Wen, and S. C. Cheung. 2022a.  MEMO: Coverage-guided Model Generation For Deep Learning Library Testing.  _ArXiv_ abs/2208.01508 (2022).
  * Li et al. (2013) You Li, Zhendong Su, Linzhang Wang, and Xuandong Li. 2013\.  Steering symbolic execution to less traveled paths.  _Proceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications_ (2013).
  * Liu et al. (2021) Dinghao Liu, Qiushi Wu, Shouling Ji, Kangjie Lu, Zhenguang Liu, Jianhai Chen, and Qinming He. 2021.  Detecting Missed Security Operations Through Differential Checking of Object-based Similar Paths.  _Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security_ (2021).
  * Liu et al. (2019) Shangqing Liu, Cuiyun Gao, Sen Chen, Lun Yiu Nie, and Yang Liu. 2019.  ATOM: Commit Message Generation Based on Abstract Syntax Tree and Hybrid Ranking.  _IEEE Transactions on Software Engineering_ 48 (2019), 1800–1817.
  * Luo et al. (2021) Wei Luo, Dong Chai, Xiaoyue Run, Jiang Wang, Chunrong Fang, and Zhenyu Chen. 2021\.  Graph-Based Fuzz Testing for Deep Learning Inference Engines.  _2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)_ (2021), 288–299.
  * MITRE (2022) MITRE. 2022.  Common Vulnerabilities and Exposures.  https://cve.mitre.org/index.html.
  * Nejadgholi and Yang (2019) Mahdi Nejadgholi and Jinqiu Yang. 2019.  A Study of Oracle Approximations in Testing Deep Learning Libraries.  _2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE)_ (2019), 785–796.
  * Noller et al. (2018) Yannic Noller, Rody Kersten, and Corina S. Pasareanu. 2018\.  Badger: complexity analysis with fuzzing and symbolic execution.  _Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis_ (2018).
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019.  PyTorch: An Imperative Style, High-Performance Deep Learning Library.  _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019_ (2019).
  * Patrick-Evans et al. (2021) James Patrick-Evans, Moritz Dannehl, and Johannes Kinder. 2021\.  XFL: Naming Functions in Binaries with Extreme Multi-label Learning.
  * Peng et al. (2019) Jiaqi Peng, Feng Li, Bingchang Liu, Lili Xu, Binghong Liu, Kai Chen, and Wei Huo. 2019.  1dVul: Discovering 1-Day Vulnerabilities through Binary Patches.  _2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)_ (2019), 605–616.
  * Pham et al. (2019) Hung Viet Pham, Thibaud Lutellier, Weizhen Qi, and Lin Tan. 2019\.  CRADLE: Cross-Backend Validation to Detect and Localize Bugs in Deep Learning Libraries.  _2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE)_ (2019), 1027–1038.
  * Qian et al. (2022) Jing Qian, Li Dong, Yelong Shen, Furu Wei, and Weizhu Chen. 2022.  Controllable Natural Language Generation with Contrastive Prefixes. In _Findings of the Association for Computational Linguistics: ACL 2022_.
  * Sen (2005) Koushik Sen. 2005\.  DART: directed automated random testing. In _ACM-SIGPLAN Symposium on Programming Language Design and Implementation_.
  * Sen et al. (2005) Koushik Sen, Darko Marinov, and Gul A. Agha. 2005\.  CUTE: a concolic unit testing engine for C. In _ESEC/FSE-13_.
  * She et al. (2018) Dongdong She, Kexin Pei, Dave Epstein, Junfeng Yang, Baishakhi Ray, and Suman Sekhar Jana. 2018\.  NEUZZ: Efficient Fuzzing with Neural Program Smoothing.  _2019 IEEE Symposium on Security and Privacy (SP)_ (2018), 803–817.
  * Singh and Khurshid (2020) Shikhar Singh and Sarfraz Khurshid. 2020.  Parallel Chopped Symbolic Execution. In _ICFEM_.
  * Stephens et al. (2016) Nick Stephens, John Grosen, Christopher Salls, Andrew Dutcher, Ruoyu Wang, Jacopo Corbetta, Yan Shoshitaishvili, Christopher Krügel, and Giovanni Vigna. 2016\.  Driller: Augmenting Fuzzing Through Selective Symbolic Execution. In _NDSS_.
  * Sui and Xue (2016) Yulei Sui and Jingling Xue. 2016.  SVF: interprocedural static value-flow analysis in LLVM.  _Proceedings of the 25th International Conference on Compiler Construction_ (2016).
  * Trabish et al. (2018) David Trabish, Andrea Mattavelli, Noam Rinetzky, and Cristian Cadar. 2018.  Chopped Symbolic Execution.  _2018 IEEE/ACM 40th International Conference on Software Engineering (ICSE)_ (2018), 350–360.
  * Wang et al. (2017a) Junjie Wang, Bihuan Chen, Lei Wei, and Yang Liu. 2017a.  Skyfire: Data-Driven Seed Generation for Fuzzing.  _2017 IEEE Symposium on Security and Privacy (SP)_ (2017), 579–594.
  * Wang et al. (2022) Jiannan Wang, Thibaud Lutellier, Shangshu Qian, Hung Viet Pham, and Lin Tan. 2022.  EAGLE: Creating Equivalent Graphs to Test Deep Learning Libraries.  _2022 IEEE/ACM 44th International Conference on Software Engineering (ICSE)_ (2022), 798–810.
  * Wang et al. (2017b) Yu Wang, Linzhang Wang, Tingting Yu, Jianhua Zhao, and Xuandong Li. 2017b.  Automatic detection and validation of race conditions in interrupt-driven embedded software.  _Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis_ (2017).
  * Wang et al. (2020) Zan Wang, Ming Yan, Junjie Chen, Shuang Liu, and Dongdi Zhang. 2020.  Deep learning library testing via effective model generation.  _Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ (2020).
  * Wei et al. (2022) Anjiang Wei, Y. Deng, Chenyuan Yang, and Lingming Zhang. 2022\.  Free Lunch for Testing: Fuzzing Deep-Learning Libraries from Open Source.  _2022 IEEE/ACM 44th International Conference on Software Engineering (ICSE)_ (2022), 995–1007.
  * Wu et al. (2022) Jiawei Wu, Senyi Li, Junqiang Li, Long Luo, Hongfang Yu, and Gang Sun. 2022\.  DeepCov: Coverage Guided Deep Learning Framework Fuzzing.  _2022 7th IEEE International Conference on Data Science in Cyberspace (DSC)_ (2022), 399–404.
  * Wu et al. (2018) Wei Wu, Yueqi Chen, Jun Xu, Xinyu Xing, Xiaorui Gong, and Wei Zou. 2018\.  FUZE: Towards Facilitating Exploit Generation for Kernel Use-After-Free Vulnerabilities. In _USENIX Security Symposium_.
  * Xiao et al. (2020) Yang Xiao, Bihuan Chen, Chendong Yu, Zhengzi Xu, Zimu Yuan, Feng Li, Binghong Liu, Yang Liu, Wei Huo, Wei Zou, and Wenchang Shi. 2020.  MVP: Detecting Vulnerabilities using Patch-Enhanced Vulnerability Signatures. In _USENIX Security Symposium_.
  * Xie et al. (2022) Danning Xie, Yitong Li, Mijung Kim, Hung Viet Pham, Lin Tan, X. Zhang, and Michael W. Godfrey. 2022.  DocTer: documentation-guided fuzzing for testing deep learning API functions.  _Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis_ (2022).
  * Yang et al. (2023) Chenyuan Yang, Yinlin Deng, Jiayi Yao, Yuxing Tu, Hanchi Li, and Lingming Zhang. 2023\.  Fuzzing Automatic Differentiation in Deep-Learning Libraries.  _ArXiv_ abs/2302.04351 (2023).
  * Zhang et al. (2021a) Xufan Zhang, Jiawei Liu, Ning Sun, Chunrong Fang, Jia Liu, Jiang Wang, Dong Chai, and Zhenyu Chen. 2021a.  Duo: Differential Fuzzing for Deep Learning Operators.  _IEEE Transactions on Reliability_ 70 (2021), 1671–1685.
  * Zhang et al. (2021b) Xufan Zhang, Ning Sun, Chunrong Fang, Jiawei Liu, Jia Liu, Dong Chai, Jiang Wang, and Zhenyu Chen. 2021b.  Predoo: precision testing of deep learning operators.  _Proceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis_ (2021).
  * Zhang et al. (2020) Yufeng Zhang, Zhenbang Chen, Ziqi Shuai, Tianqi Zhang, Kenli Li, and Ji Wang. 2020\.  Multiplex Symbolic Execution: Exploring Multiple Paths by Solving Once.  _2020 35th IEEE/ACM International Conference on Automated Software Engineering (ASE)_ (2020), 846–857.