# An Efficient Radar Receiver for OFDM-based Joint Radar and Communication
Systems

Mamady Delamou1, Kawtar Zerhouni1, Guevara Noubir2, and El Mehdi Amhoud1

<EMAIL_ADDRESS>1School of Computer Science, Mohammed VI Polytechnic
University, Benguerir, Morocco  2Khoury College of Computer Sciences,
Northeastern University, Boston, USA

###### Abstract

We propose in this work a radar detection system for orthogonal-frequency
division multiplexing (OFDM) transmission. We assume that the transmitting
antenna Tx is co-located with a monostatic radar. The latter knows the
transmitted signal and listens to echoes coming from the reflection of fixed
or moving targets. We estimate the targets parameters (range and velocity)
using a 2D-Periodogram. Moreover, we improve the estimation performance in low
signal to noise ratio (SNR) conditions using the discrete Fourier transform
channel estimation (DFT-CE) and we show that Zadoff-Chu precoding (ZCP)
adopted for communication, does not degrade the radar estimation in good SNR
conditions. Furthermore, since the dimensions of the data matrix can be much
larger than the number of targets to be detected, we propose a sparse Fourier
transform based Fourier projection-slice (FPS-SFT) algorithm to reduce the
computational complexity of the 2D-Periodogram. An appropriate system
parameterization in the 77GHz industrial, scientific and medical (ISM) band,
allows to achieve a range resolution of 30.52 cm and a velocity resolution of
0.67 m/s and to reduce the periodogram computation time up to around 98.84%.

###### Index Terms:

Fourier projection-slice, joint communication and radar sensing (JCAS),
monostatic radar, OFDM, periodogram, Zadoff-Chu precoding.

##  I Introduction

Wireless communication systems and radio sensing systems are two different
technologies that have evolved separately. However, nowadays, with the growing
need for radio resources [1], implementing these two technologies separately
leads to an inefficient utilization of the available spectrum. Despite their
differences, communication and radar detection systems share many common
features, particularly in terms of signal processing and equipment. This has
led several researchers to investigate the implementation possibility of a
common system for both technologies [2, 3, 4, 5, 6]. Several approaches have
been proposed in previous years, among which one of the prominent ideas is the
coexistence of communication and radar detection [7, 8, 9]. In fact, in such a
model, the radar and communication systems can be co-located and even
physically integrated. However, they transmit two different signals that
overlap in the time and/or frequency domains. They can also operate
simultaneously by sharing the same resources in a cooperative way, in order to
minimize the interference between them [10]. Nevertheless, with this
coexistence, managing interference becomes a challenging endeavour [7, 11]. In
[12, 13], the authors prove that WIFI or Zigbee signals could be used for
object sensing as well, showing the possibility to exploit communication
signals for sensing. The difficulty in mitigating congestion and interference
has led researchers to think of another solution which consists in merging the
communication and radar subsystems in a single device, using exactly the same
resources and the same materials. Such a system is called in the literature
joint communication and radar sensing (JCAS) or radio frequency (RF)
convergence [14]. JCAS is significantly different from the existing concepts
and from the aforementioned coexisting communication-radar systems. In fact,
in JCAS the same waveform is used for both communication and sensing. Knowing
that orthogonal frequency division multiplexing (OFDM) has been adopted in
several mobile communication standards [15, 16], employing OFDM waveform for
detection/radar purposes has attracted an increasing interest [17, 18, 10, 19,
20]. While the communication receiver Rx needs to perform the channel
estimation (CE) and then decode the transmitted data, the radar needs to apply
a detection algorithm on the reflected signal in order to estimate the range
and velocity of the targets. Nowadays, several detection algorithms exist such
as multiple signal classification (MUSIC), estimation of signal parameters via
rotational invariance technique (ESPRIT) [21, 22],  compressive sensing (CS)
[23, 24], as well as matrix pencil [25]. In this work we adopt the periodogram
method for a 2D signal. The periodogram algorithm is mainly computed using
discrete Fourier transform (DFT) and inverse discrete Fourier transform
(IDFT). Ranges and velocities are contained in the channel characteristics,
which means that a precise estimation of these parameters by the radar system,
requires an accurate channel state information. However, in low signal to
noise ratio (SNR) levels, achieving an error-free channel estimate is a
daunting task. To overcome this challenge, we introduce the DFT-CE in an
effort to reduce the noise level in the estimation. Additionally, knowing that
Zadoff-Chu precoding (ZCP) has many advantages in OFDM communication systems,
we aim to ensure that utilizing these transformations will not degrade the
radar performance. Furthermore, even though using fast Fourier transform (FFT)
and inverse fast Fourier transform (IFFT) to compute the periodogram is fast
enough, FFT/IFFT do not take into account the signal structure while a
plethora of algorithms can be even faster when the signal is sparse [26, 27,
28, 29]. Consequently, to improve the execution time, we apply the Fourier
projection-slice (FPS)-sparse Fourier transform (SFT) [27], which alleviates
to computation time up to 98.84%.

Our main contributions in this paper are summarized as follows:

  * •

We adapt the 2D-Periodogram to the received signals at the radar to estimate
the target parameters with a specific resolution.

  * •

We use DFT-CE to efficiently estimate the channel, which consequently improves
the targets estimation performance in low SNR conditions.

  * •

Furthermore, given all the advantages that ZCP has in OFDM communication
systems, we inspect its impact on the targets parameters estimation, aiming to
verify its suitability for the Radar system; which has not been investigated
for OFDM-based Radcom systems before.

  * •

Finally, each OFDM frame entries is a potential main frequency, which
corresponds to a target. Knowing that in practice the number of effective
targets is smaller compared to the whole frame dimension, the signal is sparse
in frequency domain. We take advantage of this characteristic and apply the
FPS-SFT to reduce the computational complexity along with the number of signal
samples needed for the estimation.

The remainder of this paper is organized as follows: In Section II, we
introduce the problem statement, the system model and we explain the
periodogram based radar processing. Afterwords, we discuss the estimation
improvements, on the one hand using the DFT-CE combined to ZCP, and on the
other hand by reducing the periodogram complexity applying the FPS-SFT in
section III. Simulation results and discussions are presented in Section IV.
Finally, Section V concludes the work and sets forth our perspectives.

##  II Problem Statement and system model

###  II-A Problem Statement

We consider a wireless communication system consisting of a transmitter and a
receiver as depicted in Fig. 1. The transmission antenna Tx of the transmitter
is co-located with the radar. In the downlink, the signal emitted from the
communication subsystem, is known to the radar, and is reflected by a certain
number of targets characterized by their range and velocity. OFDM is one of
the leading technologies used in new wireless communication systems. In fact,
a lot of attention has been given to OFDM for its many advantages, such as its
ability to avoid inter carrier interference (ICI) and remove inter symbol
interference (ISI) by making a suitable use of a cyclic prefix (CP), its
robustness to frequency selective fading in addition to its efficient spectral
usage. For the latter reasons, we adopt OFDM as the transmission technology
since using a single signal for communication and sensing is strongly
depending on the data structure [17]. The signal to be transmitted consists of
pilots which will be used for channel estimation, and the communication data.
It is important to mention that channel estimation is performed for both the
communication and the radar subsystems, but in different ways and for
different purposes. In fact, at the communication receiver, the received
frequency-domain pilots are used to perform channel estimation using either
least square (LS)-CE, minimum mean square error (MMSE)-CE or any other channel
estimation algorithm. Depending on the type of pilots arrangements, either
frequency or time domain interpolation (or both) can be performed to infer the
channel on the non-pilot subcarriers of each symbol. While at the radar, the
entire grid of the transmitted signal is used to perform the channel
estimation [30, 31]. The problem consists of estimating the channel in order
to efficiently approximate the range and velocity of the targets at the radar
using the reflected signals as shown in red in Fig. 1, and further, improve
this estimation. In this work, we just focus on the downlink.

Figure 1: System model of joint communication and radar system.

###  II-B System model

Figure 2: OFDM-based JCAS transmission system

In this section we describe the communication and radar channel model and
explain how the radar performs the targets parameters estimation. We consider
a total bandwidth $B$ which we divide into $N$ small bands with central
frequencies $f_{0}$,$f_{1}$,…,$f_{N-1}$ such that $\Delta f=\frac{B}{N}$. An
OFDM symbol is a packet of $N$ modulated data transmitted at the same time on
$f_{0}$,$f_{1}$,…,$f_{N-1}$. The OFDM useful time $T$ is given by
$T=\frac{1}{\Delta f}$.
After mapping the bits in quadrature amplitude modulation (QAM), an inverse
Fourier transform IFFT is applied to the QAM data to generate the OFDM symbols
in the time domain. Subsequently, a CP is added between consecutive symbols to
combat ISI at the receiver. Several OFDM symbols are compound to obtain an
OFDM frame. The signal goes through a multi-path channel to which an additive
white Gaussian noise (AWGN) is added. At the receiver, in order to retrieve
the transmitted data, the inverse operations are executed: First, the CP is
removed, then an FFT is performed on the OFDM symbols and the received
counterpart of the original bits are obtained as depicted in Fig. 2.

####  II-B1 Radar channel model

We consider a baseband signal $x(t)$ with a carrier frequency $f_{c}$. The
transmitted passband signal is $x_{pb}(t)=x(t)e^{j2\pi f_{c}t}$. For a given
reflecting target at the distance $d$ from the transmitter and moving at
velocity $v$, the received passband signal is impacted by [30]:

  * •

The attenuation factor $g$ which depends on the distance $d$, the radar cross
section (RCS) $\sigma_{RCS}$, the carrier frequency $f_{c}$ and the speed of
light $c$.
By using Friis equation of transmission, we obtain:

$g=\sqrt{\frac{c\sigma_{RCS}}{(4\pi)^{3}d^{4}f_{c}^{2}}}.$ (1)

  * •

The signal delay $\tau$ caused by the round-trip, $\tau=\frac{2\times d}{c}$.

  * •

The Doppler-Shift $f_{D}$ caused by the velocity of the target,
$f_{D}=\frac{2v}{c}f_{c}$.

  * •

The random rotation phase $\varphi$ introduced when the signal hits the
target.

  * •

The AWGN $z(t)$ such that $z(t)\sim\mathcal{N}(\mu,\,\sigma^{2})$.

Assuming a total number of $N_{t}$ reflecting moving targets, and taking into
account all the previous constraints, the received passband signal $y_{pb}(t)$
is written as follows [31]:

$y_{pb}(t)=\sum^{N_{t}-1}_{p=0}g_{p}x(t-\alpha_{p}(t))e^{j2\pi
f_{c}(t-\alpha_{p}(t))}e^{j\varphi_{p}}+z_{pb}(t),$ (2)

with $\alpha_{p}(t)=2(\frac{d_{p}}{c}+\frac{v_{p}}{c}t)=\tau_{p}+B_{p}t$, with
$B_{p}=2\frac{v_{p}}{c}$.
At the radar, the received baseband signal $y(t)$ is obtained by demodulating
$y_{pb}$(t) as
$y(t)=y_{pb}(t)e^{-j2\pi f_{c}t}$. Thereafter, Eq. (2) becomes:

$y(t)=\sum^{N_{t}-1}_{p=0}g_{p}x(t-\alpha_{p}(t))e^{-j2\pi
f_{c}\tau_{p}t}e^{j2\pi f_{D_{p}}t}e^{j\varphi_{p}}+z(t).$ (3)

Eq. (3) is the received signal containing the attenuation $g_{p}$, the channel
delays $\tau_{p}$, the Doppler effects $f_{D_{p}}$ and the time-scale factor
$B_{p}$. $y(t)$ is the signal $x(t)$ filtered with the channel impulse:

$h(t)=\sum_{p=0}^{N_{t}-1}g_{p}e^{-j2\pi f_{c}\tau_{p}}e^{j2\pi
f_{D_{p}}t}e^{j\varphi_{p}}\delta\left((1-B_{p})t-\tau_{p}\right),$ (4)

where $\delta(t)$ is the Dirac distribution.
A discrete-time counterpart considering a sample time $T_{0}$ is given by:

$\displaystyle h[n]=h(nT_{0})=\sum_{p=0}^{N_{t}-1}g_{p}e^{-j2\pi
f_{c}\tau_{p}}e^{j2\pi f_{D_{p}}nT_{0}}e^{j\varphi_{p}}\times$ (5)
$\displaystyle\delta\left[(1-B_{p})n-\tau_{p}/T_{0}\right]$

The discrete form of Eq. (3) can be written as:

$y[n]=x[n]\otimes h[n]+z[n],$ (6)

where $\otimes$ is the convolution operation.

We assume that the complex symbols $a_{k,l}$ are generated after QAM
modulation. Taking the IFFT of the 0-th OFDM symbol $a_{k,0}$, the OFDM symbol
sampled at sampling time $T_{0}=\frac{T}{N}$ can be represented as [30]:

$\displaystyle
x\left[n\right]=x(nT_{0})=\sum^{N-1}_{k=0}a_{k,0}e^{j2\pi\frac{nk}{N}},0\leq
n\leq N-1,$ (7)

which is the IFFT of the QAM symbols.
Taking into account the CP transmission time $T_{cp}$, an OFDM symbol
transmission time $T_{s}$ becomes $T_{s}=T+T_{cp}$. In terms of symbols
number, we have $N_{s}=N+N_{cp}$ where $N_{cp}$ is the number of complex
symbols transmitted during $T_{cp}$.
Assuming that an OFDM frame is composed of $M$ OFDM symbols, the transmitted
signal can be represented as:

$x[n]=\sum^{M-1}_{l=0}\sum^{N-1}_{k=0}a_{k,l}e^{\frac{{j2\pi
k(n-lN_{s})}}{N}}.$ (8)

Knowing that $T_{0}=\frac{1}{\Delta fN}$, the discrete-time counterpart of Eq.
(3) can be obtained by introducing Eq. (5) and Eq. (8) in Eq. (6) [31]:

$\displaystyle
y[n]=\sum^{N_{t}-1}_{p=0}\sum^{M-1}_{l=0}\sum^{N-1}_{k=0}g_{p}a_{k,l}e^{j2\pi\frac{kn}{N}}e^{-j2\pi
k\Delta f\tau_{p}}e^{\frac{-j2\pi kB_{p}n}{N}}\times$ (9) $\displaystyle
e^{\frac{j2\pi klN_{s}}{N}}e^{\frac{-j2\pi f_{D_{p}}n}{N\Delta
f}}e^{j\varphi_{p}}+z[n].$

The signal for the $l^{th}$ OFDM symbol is expressed as:

$\begin{gathered}y[n,l]=\sum^{N_{t}-1}_{p=0}\sum^{N-1}_{k=0}g_{p}a_{k,l}e^{j2\pi\frac{k(n-lN_{s})}{N}}e^{-j2\pi
k\Delta f\tau_{p}}\times\\\ e^{\frac{-j2\pi
kB_{p}(n-lN_{s})}{N}}e^{\frac{j2\pi klN_{s}}{N}}e^{\frac{-j2\pi
f_{D_{p}}(n-lN_{s})}{N\Delta f}}e^{j\varphi_{p}}+z[n].\\\
=\sum^{N_{t}-1}_{p=0}\sum^{N-1}_{k=0}g_{p}a_{k,l}e^{j2\pi\frac{kn}{N}}e^{-j2\pi
k\Delta f\tau_{p}}\times\\\ e^{\frac{-j2\pi kB_{p}n}{N}}e^{\frac{j2\pi
kB_{p}lN_{s}}{N}}e^{\frac{-j2\pi f_{D_{p}}n}{N\Delta f}}e^{\frac{j2\pi
f_{D_{p}}lN_{s}}{N\Delta f}}e^{j\varphi_{p}}+z[n].\end{gathered}$ (10)

According to [30], a large sub-carrier distance heavily alleviates the de-
orthogonalizing effect of a frequency offset. Therefore, it must be ensured
that $\Delta f$ is larger than the Doppler shift caused by the object with the
maximum relative velocity $v_{max}$:

$v_{max}\ll\frac{c\Delta f}{2f_{c}},$ (11)

which depends on the wave parameterization.
Our system parameterization satisfies Eq. (11) and consequently,
($e^{\frac{-j2\pi kB_{p}n}{N}},e^{\frac{j2\pi
kB_{p}lN_{s}}{N}},e^{\frac{-j2\pi f_{D_{p}}n}{N\Delta
f}})\longrightarrow(1,1,1)$. Therefore, Eq. (10) becomes simply:

$\begin{gathered}y[n,l]=\sum^{N_{t}-1}_{p=0}\sum^{N-1}_{k=0}g_{p}a_{k,l}e^{j2\pi\frac{kn}{N}}e^{-j2\pi
k\Delta f\tau_{p}}e^{\frac{j2\pi f_{D_{p}}lN_{s}}{N\Delta
f}}e^{j\varphi_{p}}\\\ +z[n].\end{gathered}$ (12)

####  II-B2 Radar processing

$\boldsymbol{H_{v,r}}$$\boldsymbol{v}$$\boldsymbol{q}$$\boldsymbol{H_{v,d}}$$\boldsymbol{v}$$\boldsymbol{d}$$\boldsymbol{H_{s,r}}$$\boldsymbol{s}$$\boldsymbol{r}$FFT
$\Downarrow$IFFT $\Rightarrow$

Figure 3: 2D-Periodogram computation process [31]. The vertical $\Downarrow$
and horizontal $\Rightarrow$ arrows indicate an FFT over columns and an IFFT
over rows respectively.

The main purpose of using the CP is to avoid ISI. For that, the maximum
channel delay $\tau_{max}$ should be less than the cyclic prefix transmission
time.

$max_{0\leq p\leq N_{t}-1}\\{\tau_{p}\\}\leq T_{cp}.$ (13)

We say that a range $d_{un}$ (resp. a velocity $v_{un}$) is unambiguous if two
targets positioned at $d$ and $d+d_{un}$ (resp. at moving velocities $v$ and
$v+v_{un}$) cannot be distinguished [30].

$d_{un}=\frac{c}{2\Delta f},v_{un}=\frac{c}{2f_{c}T_{s}}.$ (14)

A distance $\Delta d$ (resp. velocity $\Delta v$) is called radar resolution
if it is the lowest distance (resp. velocity) such that two targets positioned
at $d$ and $d+\Delta d$ (moving at $v$ and $v+\Delta v$) can still be
distinguished [30].

$\Delta d=\frac{c}{2N\Delta f},\Delta v=\frac{c}{2Mf_{c}T_{s}}.$ (15)

Figure 4: Radar image map for 5 targets at ranges [100m, 120m, 135m, 160m,
180m] and moving at [30m/s, -25m/s, 5m/s, 17m/s, -15m/s], at SNR = 5dB.

The first step of the estimation process is the spectral division. In fact,
since the radar knows the transmitted frame, the channel information can be
retrieved by taking the ratio of the whole received signal over the whole
transmitted one, which results in LS-CE estimate of the channel. Then the
estimation matrix $\boldsymbol{H}$ has entries as follows:

$\displaystyle h_{k,l}$
$\displaystyle=\frac{y_{k,l}}{x_{k,l}}=\sum^{N_{t}-1}_{p=0}b_{p}e^{j2\pi\frac{lN_{s}f_{D_{p}}}{N\Delta
f}}e^{-j2\pi k\Delta f\tau_{p}}e^{j\Phi}+\tilde{z}_{k,l},$ (16)

where $h_{k,l}$, $y_{k,l}$, $x_{k,l}$, $z_{k,l}$ are the value at the $k^{th}$
and $l^{th}$ position in the matrix $\boldsymbol{H}$, the received frame
matrix $\boldsymbol{Y}$, the transmitted frame matrix $\boldsymbol{X}$ and the
noise matrix $\boldsymbol{\tilde{Z}}$ respectively. $\Phi$ is the phase
obtained after the element-wise division. A periodogram is an estimate of the
spectral density of a signal. Since in our case $\boldsymbol{H}$ is a two-
dimensional signal, the corresponding periodogram can also be written as [14]:

$P(s,r)=\frac{1}{NM}\left|\sum_{k=0}^{N^{\prime}-1}\left(\sum_{l=0}^{M^{\prime}-1}h_{k,l}w_{k,l}e^{-j2\pi\frac{ls}{R^{\prime}}}\right)e^{j2\pi\frac{kr}{S^{\prime}}}\right|^{2},$
(17)

with $r=0,\ldots,N^{\prime}-1\quad$ and $\quad
s=\left\lfloor\frac{-M^{\prime}}{2}\right\rfloor,\ldots,\left\lfloor\frac{M^{\prime}}{2}\right\rfloor-1$.
Where $\left\lfloor\frac{M^{\prime}}{2}\right\rfloor$ indicates the floor of
$\frac{M^{\prime}}{2}$ and the negative values of $r$ allow estimating
negative velocities.

Figure 5: Channel MSE for LS-CE, LMMSE based LS-CE, DFT-CE and LMMSE based
DFT-CE.

The problem here can be stated as finding the optimal $s$ and $r$ in
$\boldsymbol{P}$ where the dominant frequencies are present. Those frequencies
will represent the reflection points which are effective targets. In Eq. (17),
$w_{k,l}$ is the value at the $k^{th}$ and $l^{th}$ position in the matrix
$\boldsymbol{W}$. It is a window function that reduces the side-lobe levels of
each dominant frequency. $N^{\prime}$ and $M^{\prime}$ are the extended values
of N and M such that $N^{\prime}\geq N$ and $M^{\prime}\geq M$. They can
improve the precision of the estimation, but do not have any effect on the
radar resolution. Eq. (17) is equivalent to taking an $M^{\prime}$-FFT of each
column of $\boldsymbol{H}$ then an $N^{\prime}$-IFFT of each row of the
previous resulting matrix as depicted in Fig. 3. Consequently, Eq. (17)
outputs dominant peaks where targets are supposed to be located. Due to the
whiteness of the noise, the detection threshold is equal to
$\sigma^{2}\ln(P_{fa})$ [30]. More explicitly, as established in Eq. (18), any
point ($s$, $r$) such that $P(s,r)\geq\sigma^{2}\ln(P_{fa})$ is considered as
a target, otherwise it is a noise, so a false target, where $P_{fa}$ is the
desired probability of false alarm.

$P(s,r)\begin{cases}\geq\sigma^{2}\ln(P_{fa})&\text{target}\\\
\leq\sigma^{2}\ln(P_{fa})&\text{noise\leavevmode\nobreak\ \leavevmode\nobreak\
only}\end{cases}$ (18)

Once we get the list of the estimates $\hat{s}$ and $\hat{r}$, the
corresponding targets range and velocity values are deduced as follows:

$\hat{d}_{p}=\frac{c\hat{s}_{p}}{2N^{\prime}\Delta
f},\hat{v}_{p}=\frac{c\hat{r}_{p}}{2f_{c}M^{\prime}T_{0}}.$ (19)

Fig. 4 shows a radar range-Doppler map, also called a radar image, of 5
targets at ranges [100m, 120m, 135m, 160m, 180m], moving at velocities [30m/s,
-25m/s, 5m/s, 17m/s, -15m/s] respectively at SNR = 5dB. As shown in the
figure, the first target at range 100m and velocity 30m/s (moving away from
the transmitter), which is the closest to the transmitter is well detectable
(the top right target). While the last target, the farthest at range 180m and
velocity -15m/s (moving toward the transmitter) is slightly detectable (the
bottom left target).

Figure 6: Periodogram’s normalized peaks diagram for 5 targets, SNR = 0dB.

##  III Enhancement capabilities for radar estimator

###  III-A Channel estimation using DFT-CE

As presented previously, since targets velocity and range can be evaluated
from the channel, the entire detection process depends on the quality of
$\boldsymbol{H}$ predicted using Eq. (16). The intuition is that an accurate
estimation of $\boldsymbol{H}$ would output a precise parameter approximate.
The approach that we propose here, consists of estimating the channel using
the DFT-CE.
It is worth mentioning that the CP is longer than the channel delay. Each path
delay of the multipath channel is lower than the time it takes to transmit the
CP. More explicitly, in order to estimate ranges and velocities, instead of
using all the channel impulse for the whole OFDM frame transmission time, we
only use a short part of the channel impulse equivalent to the $T_{CP}$
transmission time. In very low SNR conditions, the noise level is higher than
many targets peaks. Thus, the periodogram can pick up wrong peaks as targets
with very high probability since each subcarrier index is a potential target.

(a) LS-CE.

(b) DFT-CE.

(c) ZCP based LS-CE.

Figure 7: Normalized peak level as a function of the subcarrier index for
256-OFDM with $N_{cp}$ = 64 and SNR = -25dB.

Using DFT-CE eliminates all the unuseful part where targets cannot be, which
reduces the probability of false peaks detection.
The DFT-CE process can essentially be performed in 3 steps [32]:

  * •

Transform the frequency domain LS-CE to time domain using an IFFT.

$\displaystyle\hat{h}(n)=\frac{1}{K}\sum_{k=0}^{K-1}\hat{H}(k)e^{j2\pi\frac{nk}{K}},$
$\displaystyle 0\leq n\leq K-1.$ (20)

  * •

Restrain the effect of noise by keeping only the cyclic prefix equivalent part
of the signal.

$\hat{h}_{r}(n)=\left\\{\begin{array}[]{cc}\hat{h}(n)&0\leq n\leq N_{cp}-1\\\
0&\text{ otherwise }\end{array}\right..$ (21)

  * •

Convert the channel estimate back to the frequency domain using FFT.

$\displaystyle\hat{H}^{\prime}(k)=$
$\displaystyle\frac{1}{K}\sum_{k=0}^{K-1}\hat{h}_{r}(n)e^{-j2\pi\frac{nk}{K}},$
(22) $\displaystyle 0\leq n\leq K-1.$

The operations of converting the frequency channel to time domain, then the
time domain channel to the frequency one is fast since the IDFT and DFT are
implemented through IFFT and FFT respectively. This improves the channel
estimates with low complexity.

In order to obtain a good channel state information, a better approach could
be using MMSE-CE, which performs better than both LS-CE and DFT-CE. However,
MMSE-CE is limited by its high complexity and also by the fact that we need
the real channel statistics properties (which are unknown in practice) such as
the co-variance matrix to compute it. Even though in [32] the authors proposed
MMSE based DFT-CE, which is faster than the MMSE-CE, its complexity remains
very high in some applications when handling very large matrices.
Fig. 5 depicts the mean square error (MSE) of LS-CE, linear minimum mean
square error (LMMSE) based LS-CE, DFT-CE and LMMSE based DFT-CE. From the
figure, its clear that LMMSE based DFT-CE outperforms the others followed by
DFT-CE. In contrast, DFT-CE is a good trade-off with good estimation (compared
to LS-CE) and low complexity (compared to LMMSE based DFT-CE).
Fig. 6 and Fig. 7 present the peaks level according to OFDM subcarriers index
for 5 targets case. When SNR is high, all the 5 targets are clearly detectable
as can be seen in Fig. 6. However, knowing that targets can be located at
subcarrier indexes $i$ such that $0\leq i\leq N_{cp}-1$, when SNR becomes very
low (for instance SNR = -25dB, as presented in Fig. 7), some or all targets
peaks are confused with the noise ones. Subsequently, they can be incorrectly
selected in subcarrier index $i$, such that $i\geq N_{cp}-1$, which increases
the detection error as shown in Fig .7(a). By applying the DFT-CE, targets can
still be erroneously selected, however in the right subcarrier index range,
i.e., $0\leq i\leq N_{cp}-1$, hence reducing the estimation error as depicted
in Fig. 7(b).

###  III-B Zadoff-Chu precoding

Zadoff-Chu sequences are known as a polyphase complex valued sequences with
constant amplitude zero auto-correlation waveform (CAZAC). Because of their
good auto-correlation properties, these sequences have many applications
especially in 3GPP Long Term Evolution (LTE) for synchronization of mobile
phones with base stations.
A Zadoff-Chu sequence of length $L$ can be defined as :

$Z_{seq}(k^{\prime})=\begin{cases}e^{\frac{j2\pi
r^{\prime}}{L}\left(\frac{k^{\prime 2}}{2}+q^{\prime}k^{\prime}\right)}&\text{
for $L$ even }\\\ e^{\frac{j2\pi
r^{\prime}}{L}\left(\frac{k^{\prime}(k^{\prime}+1)}{2}+q^{\prime}k^{\prime}\right)}&\text{
for $L$ odd }\end{cases},$ (23)

where $k^{\prime}=0,1,...,L-1$, $q^{\prime}\in\mathbb{Z}$, $r^{\prime}$ is any
integer relatively prime to $L$. From a Zadoff-Chu sequence of length $L$, we
can construct a square Zadoff-Chu matrix $Z_{m}$ such that [33]:

$\displaystyle Z_{seq}(k^{\prime})=Z_{seq}(iD+j)=Z_{m}(i,j),$ (24)
$\displaystyle 0\leq i,j\leq D-1,D=\sqrt{L}.$

In OFDM transmission, ZCP consists of multiplying the modulated signal by
$\boldsymbol{Z_{m}}$ before the IFFT, wich effect will be discarded at the
receiver using $\boldsymbol{(Z_{m}})^{-1}$. However, this operation increases
the noise level in the channel estimate as shown in Fig. 7(c). One of the
major drawbacks of OFDM is its high peak-to-average power ratio (PAPR). As
demonstrated in [33], adopting ZCP shows a good PAPR reduction with a
significant bit error rate (BER) enhancement. When an OFDM signal with high
PAPR passes through a high power amplifier (HPA), PAPR reduction techniques
may be employed to help improve the adjacent channel interference (ACI) [33,
34]. Fig. 8 shows the spectrum of one QAM symbol in the 128-OFDM signal with
$B$ = 20MHz. The signal goes through an HPA with an output:

$f_{x}=\frac{|x|}{\sqrt{(1+(|x|/(\overline{x}\times 10^{q/10}))^{2})}},$ (25)

with state level $q$ = 2. $|x|$ and $\overline{x}$ are the modulus and the
mean of $x$ respectively, $\Delta f=\frac{B}{128}$. Each data symbol belong to
$[-\Delta f/2,\Delta f/2]$.

Figure 8: Spectrum of a single QAM symbol as a function of the frequency. The
ZCP reduces the ACI after the non-linear HPA.

As a result, the ACI of each modulated symbol in the OFDM based ZCP,
represented by the red curve in Fig. 8, is low compared to the ACI of the
ordinary OFDM illustrated by the yellow curve in Fig. 8. In this work, we aim
to analyse the impact of ZCP on the range and velocity estimations. It is
important to mention that at the radar processing, when using ZCP, the matrix
$\boldsymbol{H}$ can be computed by taking the ratio of the signal after the
OFDM FFT over the one before the OFDM IFFT. By applying the previous ZCP on
the OFDM signal, we end up with a lower PAPR and lower ACI signal. After
transmission, the target estimation process is the same at the radar as
described previously. As a result, ZCP outputs imprecise assessments when
dealing with low SNR as it increases the noise level. However, in high SNR
conditions, in addition to its multiple advantages for the communication
subsystem, its radar estimates converge, which means that it can be used in
JCAS systems.

###  III-C Complexity reduction: Sparse Fourier Transform based Fourier
Projection-Slice (FPS-SFT)

The DFT is one of the most important and widely used algorithms in
computational tasks such as in signal processing, communications, and
audio/image/video compression. It is often implemented through FFT which
computes the DFT of an $n$-dimensional signal in $\mathcal{O}(n\log n)$ time.
FFT does not make any assumption about the structure of the signal. However,
in many applications, the signal is highly sparse in the frequency domain as
depicted in Fig. 9. A signal $x$ is exactly $K$-sparse (resp. approximately
$K$-sparse) in frequency domain if its Fourier transform contains exactly $K$
non-zeros values and the others are zeros (resp. the Fourier transform
contains only $K$ dominant values and the others are close to zero). In radar
application, only a few targets are concerned such as buildings, trucks,
walls, thus, the final output is often sparse.

Figure 9: 2D sparse signal : The entire block is the signal frame, each slot
represents a potential target. The green slots represent the effective
detected targets.

Due to the importance of processing sparse data in many areas, several
algorithms have been proposed to reduce not only the sample complexity but
also the computational complexity of the FFT. A detailed study of such
algorithms can be found in [26, 27, 28, 29]. Some of these algorithms can even
reach a computational complexity of $\mathcal{O}(K\log K)$ for exactly
$K$-sparse signals. The basic principle of all SFT algorithms is to reduce the
signal samples and computational complexity. Thus, the significant frequencies
in the signal are first localized and then estimated either iteratively or
simultaneously. However, most of these algorithms are only proposed for one-
dimensional signals and their extension to multi-dimensional signals is not
straightforward. When dealing with multi-dimensional signals, it is required
to create a large one-dimensional vector containing the entire signal, then
after the processing step, to return to the initial dimensions to determine
the index of dominant frequencies. To solve many of the drawbacks of the
aforementioned techniques, in [27], Shaogang Wang et al. proposed the FPS-SFT,
which is a multidimensional, iterative SFT algorithm. It processes a multi-
dimensional sparse signal with low complexity and small samples in both noise-
free and noisy conditions. Consequently, since we are working with a highly
sparse signal ($K\ll N\times M$), we adapt the FPS-SFT algorithm to our
estimation process in order to reduce the computational complexity. The
details of the algorithm can be found in [27].

Let’s assume that the FPS-SFT executes $I$ iterations and $Q$ is the least
common multiple of the signal dimensions $N$ and $M$. In the 2-D signals case,
each iteration uses $3Q$ samples, since it is required that 3 $Q$-length
slices are extracted to decode the two frequency components of a 2-D
frequency. Thus, the sample complexity of FPS-SFT is
$\mathcal{O}(3IQ)=\mathcal{O}(IQ)$. The core processing of FPS-SFT is the
$Q$-point 1-D DFT, which can be implemented by the FFT with the computational
complexity of $\mathcal{O}(Q\log Q)$. In addition to the FFT, each iteration
needs to evaluate up to $Q$ frequencies. Hence the computational complexity of
FPS-SFT is $\mathcal{O}(I(Q\log Q+Q))=\mathcal{O}(IQ\log Q)$. If we let the
iteration size $I$ equal to $I_{max}$ (which is sufficiently large so that
FPS-SFT converges for a given $K$-sparse signal), the sample and the
computational complexity of FPS-SFT become $\mathcal{O}(Q)$ and
$\mathcal{O}(Q\log{}Q)$ respectively. For $K=\mathcal{O}(Q)$, FPS-SFT achieves
the lowest sample and computational complexity, i.e., $\mathcal{O}(K)$ and
$\mathcal{O}(K\log K)$, respectively, among all considered SFT algorithms
[27].

Figure 10: 2D-Periodogram and 2D-FPS-SFT estimate comparison for 5 targets a
2048-OFDM, $M=560$. Each target identified by its coordinates $(n,m)$.

##  IV Simulation results and analysis

Figure 11: 2D-Periodogram and 2D-FPS-SFT execution time comparison with 5 targets, varing the OFDM subcarrier number size over $B$ = 60MHz and $M$ = 200. Table I: Simulation parameters Parameter | Symbol | Value
---|---|---
Number of OFDM symbols | $M$ | 560
Number of subcarriers | $N$ | 2048
False alarm probability | $P_{fa}$ | $10^{-2}$
Carrier frequency | $f_{c}$ | 77 GHz
Light speed | $c$ |  $3\times 10^{8}$ m/s
QAM-Size | $-$ | 16
Subcarrier space | $\Delta_{f}$ | 240 KHz
Bandwidth | $B$ | 491,52 MHz
Slots per subframe | $-$ | 4
Maximum range | $d_{max}$ | 156.25 m
Symbols per slot | $-$ | 14
Range resolution | $\Delta d$ | 30.52 cm
Velocity resolution | $\Delta v$ | 0.67 m/s
Cyclic prefix | $N_{cp}$ | 512

We evaluate the performance of the radar estimate in the 77 GHz industrial
scientific and medical (ISM) band for a total bandwidth of B = 491,52 MHz
using the proposed algorithms. The simulation parameters are inspired from the
5G New Radio (NR) specifications [35], and are summarized in Tab. I. In 5G NR,
each frame duration is 10 ms, corresponding to 10 subframes. The 240 KHz
subcarrier spacing configuration contains 16 slots per subframe and 14 OFDM
symbols by slot. Consequenty, this gives a total of 2240 OFDM symbols per
frame with $T_{cp}=7\%\times T$ (normal CP). This CP length is very small and
can allow the radar to achieve only up to $d_{max}$ = 43.73 m. For the
purposes of our simulation, we have considered 4 slots per subframe along with
a CP such that $T_{cp}=25\%\times T$, which results in a total of 560 OFDM
symbols per frame and $d_{max}$ = 156.25 m. In our simulations we are assuming
that all the $N$ OFDM subcarriers carry useful information except the first
OFDM symbol of each frame, which contains block-type pilots for channel
estimation at the communication receiver Rx. We also assume that the multipath
channel has long coherence time, which makes it unchanged during the
transmission of an OFDM frame. The radar cross section is assumed to be unity.
For the sake of simplicity we set $N^{\prime}$ and $M^{\prime}$ equal to $N$
and $M$ respectively. With $N$ = 2048 and $M$ = 560. A Hamming window is used
as the window function in Eq. (17). This configuration allows us to achieve a
range resolution of 30.52 cm and a velocity resolution of 0.67 m/s. Such a
radar can distinguish very close targets in terms of ranges and velocities.
Thus, a good parameterization of the radar and wave characteristics is very
crucial to achieve a good targets detection performance.

Figure 12: Range RMSE as a function of SNR for ZCP based LS-CE, LS-CE and DFT-
CE.

Fig. 10 shows the ordinary periodogram and the FPS-SFT (5-Sparse signal case)
estimates of 5 targets at SNR = 20dB. We plot only the useful part of the
signal where targets are located. From Fig. 10, we can clearly say that FPS-
SFT and periodogram estimates match, which means that FPS-SFT can correctly
estimate the dominant frequencies while drastically reducing the execution
time.

Fig. 11 shows the execution time comparison of the FPS-SFT and the
periodogram. From the figure, we can notice that the periodogram execution
time depends on the OFDM size while the FPS-SFT is almost constant depending
on the sparsity order $K$ of the signal.

Fig. 12 and Fig. 13 show the root mean square error (RMSE) of the range and
velocity estimation for standard periodogram using LS-CE, ZCP based LS-CE and
the DFT-CE. From the figure, we can say that DFT-CE outperforms the LS-CE and
Zadoff-Chu based LS-CE in low SNR intervals. However, the three algorithms
converge in higher SNR regions.It seems that applying DFT-CE to ZCP might
yield better estimates than the ZCP based LS-CE, but such an attempt has not
been successful.

Figure 13: Velocity RMSE as a function of SNR for ZCP based LS-CE, LS-CE and
DFT-CE.

##  V Conclusion

In this work, we proposed an improved targets detection using several emergent
techniques for the periodogram estimation proceeding. The periodogram
algorithm outputs estimation in the limit of the radar resolution which
depends on the signal parameterization. Through our simulations, we
established that when dealing with low SNR s, the estimation using LS-CE
performs poorly since the targets peaks are confused with noise. By using DFT-
CE, we improved the channel estimate and we reduced the targets estimation
error. Moreover, we concluded that ZCP, in addition to its important
applications in OFDM transmission for PAPR reduction, can also be applied in
estimating targets parameters in high SNR conditions. Taking into account that
the received signal is often sparse, the FPS-SFT effectively reduces the
estimation complexity. In our future works, we aim to apply a noise reduction
method to the Zadoff-Chu precoded signal in order to provide better channel
estimates for low SNRs. An extended version of those algorithms could be
applied to unmanned aerial vehicles where targets are moving in three
dimensions. The overall estimation can be improved using machine learning.

## References

  * [1] M. Jouhari, E.M. Amhoud, N. Saeed, and M.S. Alouini, “A Survey on Scalable LoRaWAN for Massive IoT: Recent Advances, Potentials, and Challenges,” _arXiv preprint arXiv:2202.11082_ , 2022.
  * [2] C. Sturm and W. Wiesbeck, “Waveform design and signal processing aspects for fusion of wireless communications and radar sensing,” _Proceedings of the IEEE_ , vol. 99, no. 7, pp. 1236–1259, 2011.
  * [3] A. Gameiro, D. Castanheira, J. Sanson, and P. Monteiro, “Research challenges, trends and applications for future joint radar communications systems,” _Wireless Personal Communications_ , vol. 100, 05 2018.
  * [4] M. Lushanur Rahman, J.A. Zhang, X. Huang, Y.J. Guo, and J. Heath, Robert W., “Framework for a Perceptive Mobile Network using Joint Communication and Radar Sensing,” _arXiv e-prints_ , p. arXiv:1901.05558, Jan. 2019.
  * [5] A. Hassanien, M.G. Amin, E. Aboutanios, and B. Himed, “Dual-function radar communication systems: A solution to the spectrum congestion problem,” _IEEE Signal Processing Magazine_ , vol. 36, no. 5, pp. 115–126, 2019.
  * [6] L. Zheng, M. Lops, Y.C. Eldar, and X. Wang, “Radar and communication coexistence: An overview: A review of recent methods,” _IEEE Signal Processing Magazine_ , vol. 36, no. 5, pp. 85–99, 2019.
  * [7] F. Liu, C. Masouros, A. Li, and T. Ratnarajah, “Robust MIMO beamforming for cellular and radar coexistence,” _IEEE Wireless Communications Letters_ , vol. PP, pp. 1–1, 04 2017.
  * [8] R. Saruthirathanaworakun, J.M. Peha, and L.M. Correia, “Opportunistic sharing between rotating radar and cellular,” _IEEE Journal on Selected Areas in Communications_ , vol. 30, no. 10, pp. 1900–1910, 2012.
  * [9] A.F. Martone, K.A. Gallagher, and K.D. Sherbondy, “Joint radar and communication system optimization for spectrum sharing,” _2019 IEEE Radar Conference (RadarConf)_ , pp. 1–6, 2019.
  * [10] M.L. Rahman, J.A. Zhang, K. Wu, X. Huang, Y.J. Guo, S. Chen, and J. Yuan, “Enabling joint communication and radio sensing in mobile networks - a survey,” _ArXiv_ , vol. abs/2006.07559, 2021.
  * [11] E. Yousif, F. Khan, T. Ratnarajah, and M. Sellathurai, “On the spectral coexistence of colocated MIMO radars and wireless communications systems,” _2016 IEEE 17th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)_ , pp. 1–5, 2016.
  * [12] J. Liu, G. Teng, and F. Hong, “Human activity sensing with wireless signals: A survey,” _Sensors_ , vol. 20, p. 1210, 02 2020.
  * [13] S. Wang and G. Zhou, “A review on radio based activity recognition,” _Digital Communications and Networks_ , vol. 9, 03 2015.
  * [14] C.B. Barneto, L. Anttila, M. Fleischer, and M. Valkama, “OFDM radar with lte waveform: Processing and performance,” _IEEE Radio and Wireless Symposium (RWS)_ , pp. 1–4, 2019.
  * [15] E.M. Amhoud, M. Chafii, A. Nimr, and G. Fettweis, “OFDM with Index Modulation in Orbital Angular Momentum Multiplexed Free Space Optical Links,” _IEEE 93rd Vehicular Technology Conference (VTC-Spring)_ , pp. 1–5, 2021\.
  * [16] K. Zerhouni, E.M. Amhoud, and M. Chafii, “Filtered Multicarrier Waveforms Classification: A Deep Learning Based Approach,” _IEEE Access_ , 2021.
  * [17] A. Evers and J.A. Jackson, “Analysis of an LTE waveform for radar applications,” _IEEE Radar Conference_ , pp. 0200–0205, 2014.
  * [18] C. Sturm, T. Zwick, and W. Wiesbeck, “An OFDM system concept for joint radar and communications operations,” _VTC Spring 2009 - IEEE 69th Vehicular Technology Conference_ , pp. 1–5, 2009.
  * [19] A. Zhang, M.L. Rahman, X. Huang, Y.J. Guo, S. Chen, and R.W. Heath, “Perceptive mobile networks: Cellular networks with radio vision via joint communication and radar sensing,” _IEEE Vehicular Technology Magazine_ , vol. 16, no. 2, pp. 20–30, 2021.
  * [20] E.M. Amhoud, G.R.B. Othman, and Y. Jaouën, “Concatenation of space-time coding and fec for few-mode fiber systems,” _IEEE Photonics Technology Letters_ , vol. 29, no. 7, pp. 603–606, 2017.
  * [21] X. Wu, W.P. Zhu, and J. Yan, “A fast gridless covariance matrix reconstruction method for one- and two-dimensional direction-of-arrival estimation,” _IEEE Sensors Journal_ , vol. 17, no. 15, pp. 4916–4927, 2017.
  * [22] Y. Liu, G. Liao, Y. Chen, J. Xu, and Y. Yin, “Super-resolution range and velocity estimations with OFDM integrated radar and communications waveform,” _IEEE Transactions on Vehicular Technology_ , vol. 69, no. 10, pp. 11 659–11 672, 2020.
  * [23] M. Davenport, M. Duarte, Y. Eldar, and G. Kutyniok, “Introduction to compressed sensing,” _Preprint_ , vol. 93, 01 2012.
  * [24] S. Ji, Y. Xue, and L. Carin, “Bayesian compressive sensing,” _IEEE Transactions on Signal Processing_ , vol. 56, no. 6, pp. 2346–2356, 2008.
  * [25] Y. Hua, “Estimating two-dimensional frequencies by matrix enhancement and matrix pencil,” _IEEE Transactions on Signal Processing_ , vol. 40, no. 9, pp. 2267–2280, 1992.
  * [26] A.C. Gilbert, M.J. Strauss, and J.A. Tropp, “A tutorial on fast fourier sampling,” _IEEE Signal Processing Magazine_ , vol. 25, no. 2, pp. 57–66, 2008.
  * [27] S. Wang, V.M. Patel, and A. Petropulu, “Multidimensional sparse fourier transform based on the fourier projection-slice theorem,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 1, pp. 54–69, 2019.
  * [28] P. Indyk, M. Kapralov, and E. Price, “(nearly) sample-optimal sparse fourier transform,” _Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms_ , pp. 480–499, 01 2014.
  * [29] B. Ghazi, H. Hassanieh, P. Indyk, D. Katabi, E. Price, and L. Shi, “Sample-optimal average-case sparse fourier transform in two dimensions,” _51st Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pp. 1258–1265, 2013.
  * [30] K.M. Braun, “OFDM radar algorithms in mobile communication networks,” Ph.D. dissertation, Karlsruher Institut für Technologie (KIT), 2014.
  * [31] I. Khelouani, K. Zerhouni, F. Elbahhar, R. Elassali, and N. Idboufker, “UFMC waveform and multiple-access techniques for 5G radcom,” _Electronics_ , vol. 10, no. 7, p. 849, 2021.
  * [32] J. Ma, H. Yu, and S. Liu, “The MMSE channel estimation based on DFT for OFDM system,” _5th International Conference on Wireless Communications, Networking and Mobile Computing_ , pp. 1–4, 2009.
  * [33] I. Baig and V. Jeoti, “PAPR reduction in ofdm systems: Zadoff-chu matrix transform based pre/post-coding techniques,” _2nd International Conference on Computational Intelligence, Communication Systems and Networks_ , pp. 373–377, 2010.
  * [34] E.M. Amhoud, G.R.B. Othman, L. Bigot, M. Song, E.R. Andresen, G. Labroille, M. Bigot-Astruc, and Y. Jaouën, “Experimental demonstration of space-time coding for mdl mitigation in few-mode fiber transmission systems,” _European Conference on Optical Communication (ECOC)_ , pp. 1–3, 2017.
  * [35] “5G; NR; physical channels and modulation,” 3GPP, TS 38.211 version 15.3.0 Release 15, 2018.


# Memory Error Detection in Security Testing

Nasif Imtiaz  Laurie Williams

###### Abstract

We study 10 C/C++ projects that have been using a static analysis security
testing tool. We analyze the historical scan reports generated by the tool and
study how frequently memory-related alerts appeared. We also studied the
subsequent developer action on those alerts. We also look at the CVEs
published for these projects within study timeline and investigate how many of
them are memory related. Moreover, for one of this project, Linux, we
investigate if the involved flaws in the CVE were identified by the studied
security tool when they were first introduced in the code.
We found memory related alerts to be frequently detected during static
analysis security testing. However, based on how actively the project
developers are monitoring the tool alerts, these errors can take years to get
fixed. For the ten studied projects, we found a median lifespan of 77 days
before memory alerts get fixed. We also find that around 40% of the published
CVEs for the studied C/C++ projects are related to memory. These memory CVEs
have higher CVSS severity ratings and likelihood of having an exploit script
public than non-memory CVEs. We also found only 2.5% Linux CVEs were possibly
detected during static analysis security testing.

###### Index Terms:

static analysis, tools, alerts, warnings, developer action

##  I Introduction

Software development is an error-prone activity. Code written and reviewed by
skilled developers may end up with various types of bugs some of which can be
security-critical, i.e. vulnerability. Developers use security testing tools
(e.g. static analysis, fuzzing) in order to identify the potential
vulnerabilities. However, given the non-perfect nature of these tools and the
cost of fixing the alerts they generate, developer response to such alerts may
vary. Further, even after extensive security testing, undetected
vulnerabilities may still remain in the code that get discovered years after
it was introduced.

Memory-related bugs, such as buffer overflows and uninitialized reads, are an
important class of security vulnerabilities typically more prevalent in non
memory-safe languages such as C, C++. Security testing techniques such as
static analysis can detect a wide range of potential memory issues in the
code. Tools performing such analysis present their results as alerts to the
developers. However, it is yet to be studied how frequently do memory-related
alerts get identified by security tools and how developers respond to these
alerts. Further, vulnerabilities that leak through all security testing, may
get discovered years later. If reported to the National Vulnerability Database
(NVD), the discovered vulnerabilities are tracked in a central database with a
unique identifier called CVE. However, it is yet to be studied if these
vulnerabilities (CVEs) appeared in the code because security testing
techniques failed to identify them or the testing could have had indeed
identified the flaw but the developers did not take a corrective action in
time.

In this paper, we study 10 C/C++ projects that have been using a static
analysis security testing tool. We analyze the historical scan reports
generated by the tool and study how frequently memory-related alerts appeared.
We also studied the subsequent developer action on those alerts. We also look
at the CVEs published for these projects within study timeline and investigate
how many of them are memory related. Moreover, for one of this project, Linux,
we investigate if the involved flaws in the CVE were identified by the studied
security tool when they were first introduced in the code. We state our
research questions as:

  * •

RQ1: How frequently do memory-related alerts get identified by a static
analysis security testing tool? How do developers respond to these alerts?

  * •

RQ2: What portion of publicly known vulnerabilities, CVEs, are memory related?
How many of these CVEs were identified by a static analysis security testing
tool when the involved flaws were first introduced in the code?

##  II Dataset

We primarily work with two datasets:

Figure 1: Determining actionability of static analysis alerts TABLE I: Studied projects Project | Scan Reports | Start Date | End Date | Scan Interval (days) | Total Alerts | Triaged Alerts (%) | Lines of Code
---|---|---|---|---|---|---|---
Linux | 648 | 2012-05-17 | 2020-06-15 | 3 | 19,514 | 13.66 | 13,959,859
Firefox | 662 | 2006-02-22 | 2018-10-27 | 2 | 12,944 | 36.33 | 8,223,984
LibreOffice | 414 | 2012-10-13 | 2020-06-26 | 4 | 11,982 | 55.42 | 6,130,847
Samba | 770 | 2006-02-23 | 2020-06-17 | 3 | 4,507 | 52.58 | 2,941,352
VTK | 74 | 2015-12-21 | 2017-08-12 | 7 | 2,522 | 2.50 | 2,354,516
OpenCV | 553 | 2012-12-12 | 2020-06-30 | 2 | 2,443 | 9.41 | 1,264,056
Kodi | 489 | 2012-08-28 | 2020-05-16 | 3 | 2,393 | 42.42 | 743,623
!CHAOS Control System | 170 | 2015-01-14 | 2019-03-19 | 1 | 1,980 | 12.37 | 880,411
Chromium EC | 1,713 | 2016-01-15 | 2020-07-06 | 0 | 964 | 28.11 | 61,040
Thunderbird | 438 | 2006-04-12 | 2020-02-29 | 1 | 885 | 27.23 | 640,424

  1. 1.

A proprietary dataset that consists of historical scan reports for 10 C/C++
projects by a static analysis security testing tool, we refer to this dataset
as ’scan history’ dataset;

  2. 2.

The CVE dataset from National Vulnerability Database [2]. Alerts in scan
history dataset and CVEs in NVD database have corresponding CWE mapping
(Common Weakness Enumeration, CWE, is a list of software and hardware
weaknesses [1]). Two human reviwers independently classified the CWE
identifiers as memory vs. non-memory to separate out the memory-related issues
in our dataset.

The following subsections explain the data sources, and subsequent CWE
classification.

###  II-A Scan History Dataset

We study historical scan reports by an industry-leading static analysis
security testing tool for ten C/C++ projects. For each project, we have a
range of scan reports between a certain time period with short intervals for
the latest code version on the corresponding scan date. We confirmed that
developers of respective projects monitor these scan reports by looking at the
alert triage rate (how many alerts were triaged by developers).

For each scan report, the alerts are tagged as either i) Fixed (the security
tool stopped detecting the alert in the code, we will refer to this as
eliminated), ii) Dismissed (When developers have explicitly marked an alert as
False Positive or Intentional), or iii) New (the security tool still detects
the alert in the current scan, we refer to these as alive alerts). For the
eliminated alerts, to distinguish between developer fix and other modes of
elimination (e.g. alert suppression, file deletion/renaming), we track any
commit made on the affected files for an alert to see if there were any valid
code change made when the alert was marked as fixed in a subsequent scan. The
alerts that were fixed through code change made by developers, we refer to
them as actionable alerts. We also calculated the lifespan of each alert (the
time span the security tool kept detecting an alert), and the fix complexity
for the actionable alerts (change in files, lines of code, and logical blocks
of code in the commit that fixed the alert). Figure 1 explains the workflow.
The details of projects used in this paper are listed in Table I.

###  II-B CVE dataset

For the ten projects from scan history dataset, we intended to get the
published CVEs since the first scan report of the dataset. We searched the
CVEs from NVD API through the Common Product Enumeration (CPE) identifier for
each project. However, for Chromium EC, VTK, and !CHAOS Control System, we
could not find a matching CPE identifier. We pulled the CVEs for rest of the
seven projects.

Further, we augmented the CVE dataset with patch commits for a CVE whenever
available (Patch commit is the exact commit that were merged to the product
code to fix a vulnerability). We looked for the patch commits for each CVE
through the reference links provided in the CVE data and respective project
repositories. For Firefox, LibreOffice, and Thunderbird, we could not find the
commits while Kodi had only 3 CVEs in our dataset (all are non memory-
related). While it is possible to collect patch commits in the case of Samba,
and OpenCV, they also have low number of CVEs published. Therefore, we only
focus on Linux when answering parts of RQ2.

We also looked for publicly available exploit scripts for the CVEs in our
dataset. We use a open source tool, cve_searchsploit
111https://github.com/andreafioraldi/cve_searchsploit, in order to find the
available exploit scripts. The tool pulls its data from publicly curated
’Exploit Database’ 222https://www.exploit-db.com/.

TABLE II: Memory related alerts Project | Total Alerts | Memory Alerts
---|---|---
Linux | 19,514 | 7,903 (40.5%)
Firefox | 12,944 | 5,448 (42.09%)
LibreOffice | 11,982 | 3,975 (33.17%)
Samba | 4,507 | 1,700 (37.72%)
VTK | 2,522 | 1,166 (46.23%)
OpenCV | 2,443 | 710 (29.06%)
Kodi | 2,393 | 682 (28.5%)
!CHAOS Control System | 1,980 | 282 (14.24%)
Chromium EC | 964 | 306 (31.74%)
Thunderbird | 885 | 357 (40.34%)

###  II-C CWE classification for memory vs. non-memory

In order to focus on memory-related errors, we classified the alerts in scan
history dataset and the CVEs as memory and non-memory through their
corresponding CWE identifier. CWE [1] is a list of common weakness types in
software and serves as a common measuring stick for security tools. Each CWE
identifier has a name, description, and various details on how to detect,
mitigate, or exploit software weaknesses. Two human reviewers, one graduate
student and one industry professional, independently reviewed the CWE ids and
classified them as memory or non-memory. We defined CWEs as memory-related
when a weakness can make software to access memory in a way that was
unintended by the developer. These weaknesses include access errors, use of
uninitialized variables, and memory leaks which can all lead to accessing
system memory in an unintended way.

There are 161 distinct CWE identifiers covering both of our data set. Two
reviewers independently classified them as memory vs. non-memory with a
Kohen’s Kappa agreement rate of 0.79, which is interpreted as substantial
agreement [4]. On the CWE identifiers that were classified differently, the
reviewers had a discussion and came to a negotiated agreement for a final
classification. We classified 43 CWE ids as memory (26.7%) and the rest as
non-memory.

TABLE III: Actionability of memory alerts Project | Total Memory Alerts | Eliminated | Actionable | Triaged Bug by Devs.
---|---|---|---|---
Linux | 7903 | 73.06% | 43.54% | 3.11%
Firefox | 5448 | 77.22% | 49.72% | 12.43%
LibreOffice | 3975 | 80.63% | 73.46% | 51.35%
Samba | 1700 | 77.88% | 39.88% | 3.82%
VTK | 1166 | 12.78% | 7.2% | 0.43%
OpenCV | 710 | 89.15% | 32.54% | 0.28%
Kodi | 682 | 68.62% | 54.11% | 25.07%
Thunderbird | 357 | 63.31% | 24.37% | 12.61%
Chromium EC | 306 | 93.46% | 29.74% | 17.65%
!CHAOS Control System | 282 | 80.14% | 39.01% | 1.42%
TABLE IV: Unactionable memory alerts Project | Total memory alerts | Marked intentional | Marked false positive | Alive at last scan |  Eliminated through undetermined ways
---|---|---|---|---|---
Linux | 7,903 | 1.64% | 4.02% | 21.08% | 28.22%
Firefox | 5,448 | 3.82% | 9.69% | 8.87% | 25.11%
LibreOffice | 3,975 | 0.78% | 18.39% | 0.08% | 7.02%
Samba | 1,700 | 0.82% | 2.88% | 18.12% | 35.53%
VTK | 1,166 | 0.09% | 0.17% | 86.96% | 4.8%
OpenCV | 710 | 0.56% | 1.97% | 8.31% | 41.55%
Kodi | 682 | 10.56% | 9.38% | 11.44% | 9.09%
Thunderbird | 357 | 0.28% | 0.28% | 31.37% | 38.94%
Chromium EC | 306 | 0.33% | 2.61% | 3.59% | 63.73%

##  III Findings: How frequently do memory-related alerts get identified by a
static analysis security testing tool? How do developers respond to these
alerts?

We investigate the scan history dataset to answer the following questions:

###  III-A To what extent do memory related alerts appear when C/C++ projects
are scanned by a static analysis tool?

While the rate of alerts that are memory related vary among projects,
approximately one-third of static analysis alerts were found to be memory
related (median rate of 35.4% among ten projects). Table II lists the rate of
memory related alerts for each project.

###  III-B What percent of memory related alerts are actionable (i.e. acted on
by developers)? What percent of memory related alerts were marked as false
positives by the developers?

We then looked at how many memory related alerts were eliminated (elimination
does not necessarily mean developer fix), how many were acted on by developers
(fixed through valid code change), and how many were explicitly triaged as bug
by the respective project developers. We find 39.9% (median among ten
projects) memory alerts to be acted on by the developers while 12.4% of them
are explicitly marked as bug. We also compared the elimination rate,
actionable, and bug rate between memory and non-memory alerts through Mann-
Whitney U test for the ten projects. However, we do not find any statistical
significant difference between memory and non-memory alerts. Table III lists
details of actionable memory alerts for each studied project.

We then looked at the unactionable memory alerts. Developers in our dataset
had the ability to mark an alert as False Positive or Intentional which gives
us direct feedback about the alerts from the respective project developers. We
see that memory alerts are rarely to be intentional coding (median rate of
0.8%) and are significantly less than non-memory alerts (5.7%). However, we do
not find any difference in being false positive or alive between memory and
non-memory related alerts. Table IV lists details of unactionable memory
alerts for each studied project.

###  III-C What is the lifespan of memory related alerts on the codebase?

We define lifespan of an alert as the difference in days between when an alert
was first detected and when it was last detected. Below tables present
lifespan in days for actionable alerts and then specifically the alerts that
were triaged as bug by the project developers with a breakdown between memory
vs. non-memory. The median lifespan among ten projects for actionable memory
alerts are 77 days and 98.5 days when the alert was triaged as bug. The
difference in lifespan for memory and non-memory alerts were statistically
insignificant. Table V and VI lists lifespan of actionable alerts for each
project.

###  III-D What is the fix complexity of memory related alerts on the
codebase?

In our prior work [3], we found fix of static analysis are low in complexity;
a median of 4 lines of code change in the affected file. We find similar
results for memory alerts in this paper. When reporting median, for memory
alerts: we find 2.5 files are changed with 6.6 lines of code change and 2
blocks of logical change (change in consecutive lines). Within the affected
file, there is 3.5 lines of code change and 1 block of logical change.

###  III-E What is the prevalence and developer response of alerts in terms of
CWE identifiers?

Here, we present a breakdown of our prior analyses in term of CWE-identifier.
Table VII presents information for top 10 CWE-identifiers prevalent in scan
history dataset with ’Null Pointer Dereference’ being the most common alert.

TABLE V: Lifespan of actionable alerts Project |  Lifespan of all Actionable alerts (days) |  Lifespan of Memory alerts(days) |  Lifespan of Non-memory alerts (days)
---|---|---|---
Thunderbird | 915.5 | 1591 | 490
OpenCV | 345.5 | 342 | 380
Linux | 258 | 257 | 258
!CHAOS Control System | 136.5 | 48 | 203
Firefox | 124 | 44 | 154
ovirt-engine | 102 | 77 | 119
Chromium EC | 93 | 247 | 70
Samba | 70 | 143 | 37
Kodi | 62 | 6 | 82
VTK | 31 | 24 | 42
LibreOffice | 18 | 16 | 18
TABLE VI: Lifespan of alerts marked as bug Project |  Lifespan of alerts marked as bug (days) |  Lifespan of Memory alerts (days) |  Lifespan of Non-memory alerts (days)
---|---|---|---
Thunderbird | 1385 | 1779 | 970
Samba | 665 | 665 | 911
Chromium EC | 377 | 429 | 367
Linux | 190 | 134 | 252
Firefox | 64 | 63 | 71.5
ovirt-engine | 46 | 39.5 | 49.5
VTK | 24 | 24 | 30
LibreOffice | 15 | 21 | 6
OpenCV | 5 | 850.5 | 5
Kodi | 2 | 2 | 2
TABLE VII: Top CWE categories of alerts CEW-Id |  CWE-name | No. of alerts | Eliminated | Actionable | lifespan (days) |  Triaged Bug by Devs. |  Triaged False Positive
---|---|---|---|---|---|---|---
476 |  NULL Pointer Dereference | 8,689 (14.45%) | 81.86% | 58.42% | 44 | 21.99 | 4.12%
404 |  Improper Resource Shutdown or Release | 4,250 (7.07%) | 66.92% | 43.41% | 122 | 14.33 | 18.99%
119 |  Improper Restriction of Operations within the Bounds of a Memory Buffer | 2,125 (3.53%) | 67.06% | 33.22% | 278 | 4.42 | 12.89%
457 |  Use of Uninitialized Variable | 1,862 (3.1%) | 74.01% | 53.49% | 135 | 15.52 | 6.12%
190 |  Integer Overflow or Wraparound | 1,003 (1.67%) | 54.24% | 35.39% | 315 | 7.88 | 7.48%
125 |  Out-of-bounds Read | 939 (1.56%) | 67.41% | 42.81% | 244 | 8.2 | 11.82%
416 |  Use After Free | 877 (1.46%) | 73.43% | 36.26% | 71 | 7.41 | 19.27%
120 |  Buffer Copy without Checking Size of Input (’Classic Buffer Overflow’) | 751 (1.25%) | 78.7% | 15.98% | 515 | 2.13 | 3.6%
170 |  Improper Null Termination | 378 (0.63%) | 68.78% | 56.88% | 379.5 | 7.94 | 9.26%
590 |  Free of Memory not on the Heap | 363 (0.6%) | 50.96% | 30.03% | 322 | 0 | 6.89%

##  IV Findings: What portion of publicly known vulnerabilities, CVEs, are
memory related? How many of these CVEs were identified by a static analysis
security testing tool when the involved flaws were first introduced in the
code?

Common Vulnerabilities and Exposures (CVEs) are a reference method for
publicly known software vulnerabilities[2]. While softwares typically go
through security testing before being released, vulnerabilities may still
remain in the code either due to testing techniques not having a perfect
recall or inadequate developer corrective action. In this paper, we
investigate how many CVEs could have been identified by a security tool when
the bug was first introduced in order to estimate the contribution of testing
inefficacy vs. developer inaction.

In the following subsections, we first investigate how many CVEs were memory
related for the projects in scan history dataset. We then choose Linux as a
case study to determine how many of its CVEs were identified by the studied
static analysis security testing tool when first introduced.

###  IV-A What percent of CVEs are memory related?

We pulled CVEs for seven projects from the scan history dataset that were
published after the first scan and before the last scan report in our dataset.
We further classified CVEs as memory vs. non-memory based on their
corresponding CWE ids. Table VIII shows a breakdown of CVEs for these
projects.

As a median for the seven projects, we find that 40% of the CVEs are memory
related. We further look at the severity ratings, in the form of CVSS2 and
CVSS3 scores for these CVEs in Table IX. We find that median CVSS2 score for
memory alerts for all seven projects is 7.35 which is significantly greater
than non-memory alerts (5.0). Similarly for CVSS3 rating, memory alerts median
rating is 9.3, significantly larger than non-memory alerts (6.6)

TABLE VIII: Memory related CVEs Project |  No. of CVEs (within study timeline) | memory-related CVEs
---|---|---
Linux | 3,144 | 45.4%
Firefox | 1,731 | 36.0%
Thunderbird | 940 | 45.3%
Samba | 138 | 29.7%
LibreOffice | 40 | 40.0%
OpenCV | 33 | 75.8%
Kodi | 3 | 0.0%
TABLE IX: Severity scores of Memory and Non-memory CVEs Project | Memory CVEs | Median CVSS2 score | Median CVSS3 score | Non-Memory CVEs | Median CVSS2 score | Median CVSS3 score
---|---|---|---|---|---|---
Linux | 1427 | 7.2 | 7.8 | 1150 | 4.9 | 6.7
Firefox | 624 | 7.5 | 9.8 | 737 | 5 | 6.1
Thunderbird | 426 | 7.55 | 9.8 | 308 | 5 | 6.5
Samba | 41 | 5 | 6.5 | 84 | 5 | 6.5
OpenCV | 25 | 6.8 | 8.8 | 6 | 4.65 | 6.7
LibreOffice | 16 | 7.5 | 9.8 | 20 | 6.8 | 7.8

###  IV-B What percent of memory related CVEs have exploit scripts available?

If all vulnerabilities can be exploited in the wild to attack the involved
system is debatable. However, for many CVEs, there are exploit scripts
publicly available. We find that for 396 CVEs among the seven projects, there
is an exploit script available out of which 234 (59 %) are memory related.
Table X present a CWE-breakdown for memory CVEs with an exploit.

TABLE X: CVEs with exploit script available CWE-id | CWE-name | portion among memory CVEs
---|---|---
119 | Improper Restriction of Operations within the Bounds of a Memory Buffer | 145 (62.0%)
416 | Use After Free | 41 (17.5%)
787 | Out-of-bounds Write | 13 (5.6%)
190 | Integer Overflow or Wraparound | 9 (3.8%)
125 | Out-of-bounds Read | 7 (3.0%)
824 | Access of Uninitialized Pointer | 4 (1.7%)
476 | NULL Pointer Dereference | 3 (1.3%)
122 | Heap-based Buffer Overflow | 2 (0.9%)
191 | Integer Underflow (Wrap or Wraparound) | 2 (0.9%)
415 | Double Free | 2 (0.9%)

###  IV-C How many Linux CVEs were identified by a static analysis tool when
the vulnerability was first introduced in the code?

For this question, we focus on only Linux product. In the NVD data feed for
Linux product, there can be link to the patch commit (the code change merged
into codebase to fix a CVE) among the reference links. For 1,427 Linux memory
related CVEs, we found patch commits for 592 CVEs. The rest of the CVEs were
mostly in external product code (e.g. flash player) and not in Linux code
itself.

We then analyzed the patch commit(s) for each CVE, to extract the names of the
files that were changed in the fix with an assumption that the vulnerability
related code are among these files. We then look at the time when these patch
commit(s) were merged into the main codebase of Linux. If there were a memory
alert in scan history dataset on the involved files of the CVE, the alert
should get fixed when the patch commit is merged (alert last appears before
patch commit is merged, and get fixed after the merge). If there is such
memory alerts on the involved files that get fixed when a CVE get fixed, we
assume that the studied security tool had an alert relevant to the certain
CVE.

Only for 15 CVEs (2.5%), we found there was a possible static analysis alert.
We further looked at the 15 cases manually by looking at the CVE description
and type of the alert raised by the static analysis tool. For 12 cases, the
alert type somewhat matches CVE description, while we could not determine such
matching for rest of the three cases. We further looked at the lifespan for
these 15 alerts and found their median lifespan to be 567 days.

##  V Conclusion

We found memory related alerts to be frequently detected during static
analysis security testing. However, based on how actively the project
developers are monitoring the tool alerts, these errors can take years to get
fixed. For the ten studied projects, we found a median lifesspan of 77 days
before memory alerts get fixed.

We also find that around 40% of the published CVEs for the studied C/C++
projects are related to memory. These memory CVEs have higher CVSS severity
ratings and likelihood of having an exploit script public than non-memory
CVEs. We also found only 2.5% Linux CVEs were possibly detected during static
analysis security testing.

## References

  * [1] Common weakness enumeration.  https://cwe.mitre.org/index.html.
  * [2] National vulnerability database.  https://nvd.nist.gov/vuln/full-listing.
  * [3] Nasif Imtiaz, Brendan Murphy, and Laurie Williams.  How do developers act on static analysis alerts? an empirical study of coverity usage.  In 2019 IEEE 30th International Symposium on Software Reliability Engineering (ISSRE), pages 323–333. IEEE, 2019.


M7 | 10 | 2.44(0.11) | 11.13(1.23) | 2.03(0.15) | 0.73(0.09)
50 | 2.45(0.10) | 11.23(1.28) | 2.12(0.16) | 0.68(0.05)
200 | 2.45(0.11) | 11.37(1.30) | 2.22(0.17) | 0.73(0.06)
500 | 2.46(0.12) | 11.75(1.61) | 2.24(0.21) | 0.78(0.10)
M8 | 10 | 0.83(0.02) | 1.15(0.06) | 0.15(0.08) | 0.25(0.15)
50 | 0.83(0.02) | 1.09(0.06) | 0.19(0.07) | 0.28(0.12)
200 | 0.83(0.02) | 1.09(0.07) | 0.19(0.05) | 0.30(0.16)
500 | 0.83(0.02) | 1.10(0.07) | 0.16(0.06) | 0.32(0.16)

NOTE: The corresponding simulation standard errors are given in parentheses.

Table A.6: Mean squared prediction error (MSE) of the estimated conditional
quantile for different $J$.

$X$ | Model | $J$ | $\tau=0.05$ | $\tau=0.25$ | $\tau=0.50$ | $\tau=0.75$ | $\tau=0.95$
---|---|---|---|---|---|---|---
$N(0,I_{d})$ | M1 | 10 | 0.44(0.12) | 0.12(0.03) | 0.09(0.02) | 0.15(0.05) | 0.30(0.09)
50 | 0.33(0.11) | 0.09(0.02) | 0.07(0.02) | 0.11(0.03) | 0.19(0.05)
200 | 0.29(0.07) | 0.10(0.01) | 0.09(0.02) | 0.10(0.03) | 0.23(0.06)
500 | 0.25(0.07) | 0.09(0.02) | 0.06(0.01) | 0.09(0.02) | 0.20(0.05)
M2 | 10 | 1.19(0.36) | 0.30(0.08) | 0.25(0.03) | 0.33(0.06) | 0.72(0.19)
50 | 1.01(0.29) | 0.31(0.09) | 0.24(0.04) | 0.39(0.09) | 0.87(0.29)
200 | 0.77(0.09) | 0.31(0.06) | 0.19(0.04) | 0.27(0.05) | 0.81(0.15)
500 | 0.73(0.14) | 0.30(0.05) | 0.20(0.04) | 0.29(0.05) | 0.78(0.14)
M6 | 10 | 3.30(0.64) | 2.75(0.39) | 2.61(0.25) | 2.61(0.22) | 2.86(0.26)
50 | 3.26(0.38) | 2.70(0.29) | 2.51(0.19) | 2.51(0.19) | 2.75(0.44)
200 | 3.39(0.48) | 2.70(0.24) | 2.47(0.12) | 2.50(0.21) | 2.76(0.50)
500 | 3.77(0.67) | 2.89(0.36) | 2.51(0.15) | 2.54(0.20) | 3.16(0.79)
M7 | 10 | 3.10(0.56) | 0.63(0.12) | 0.42(0.08) | 0.97(0.11) | 3.83(0.44)
50 | 1.77(0.49) | 0.30(0.06) | 0.37(0.06) | 0.80(0.16) | 4.34(0.96)
200 | 2.01(0.47) | 0.40(0.10) | 0.39(0.06) | 0.74(0.11) | 4.04(0.40)
500 | 2.80(0.63) | 0.42(0.14) | 0.42(0.06) | 0.96(0.13) | 3.99(0.68)
M8 | 10 | 0.04(0.01) | 0.03(0.01) | 0.56(0.09) | 0.05(0.01) | 0.01(0.01)
50 | 0.02(0.01) | 0.02(0.01) | 0.39(0.05) | 0.02(0.01) | 0.03(0.02)
200 | 0.03(0.01) | 0.02(0.01) | 0.40(0.04) | 0.02(0.01) | 0.03(0.02)
500 | 0.02(0.01) | 0.02(0.01) | 0.42(0.05) | 0.04(0.01) | 0.02(0.02)
$N(0,I_{100})$ | M1 | 10 | 2.29(0.46) | 1.81(0.25) | 1.74(0.20) | 1.91(0.21) | 2.62(0.50)
50 | 1.77(0.29) | 1.74(0.46) | 1.72(0.20) | 1.86(0.17) | 2.25(0.24)
200 | 1.84(0.23) | 1.69(0.20) | 1.75(0.16) | 1.88(0.13) | 2.41(0.14)
500 | 1.81(0.25) | 1.73(0.21) | 1.81(0.19) | 1.95(0.15) | 2.35(0.22)
M2 | 10 | 2.80(0.40) | 2.22(0.25) | 2.20(0.22) | 2.45(0.29) | 3.24(0.48)
50 | 2.55(0.33) | 2.17(0.23) | 2.11(0.22) | 2.36(0.31) | 3.12(0.43)
200 | 3.42(1.07) | 2.26(0.28) | 2.19(0.22) | 2.57(0.27) | 3.49(0.47)
500 | 2.52(0.45) | 2.14(0.23) | 2.18(0.23) | 2.46(0.32) | 3.40(0.49)
M6 | 10 | 4.61(0.57) | 4.42(0.57) | 4.49(0.53) | 4.72(0.56) | 5.18(0.62)
50 | 4.52(0.81) | 4.27(0.64) | 4.41(0.61) | 4.80(0.63) | 5.66(0.97)
200 | 4.47(0.76) | 4.89(0.67) | 4.72(0.79) | 4.91(0.78) | 5.65(0.71)
500 | 4.44(0.55) | 4.24(0.51) | 4.36(0.51) | 4.65(0.59) | 5.14(0.63)
M7 | 10 | 1.78(0.16) | 1.77(0.16) | 2.01(0.15) | 2.79(0.19) | 6.74(0.77)
50 | 1.72(0.19) | 1.75(0.19) | 2.09(0.21) | 3.00(0.25) | 6.77(0.52)
200 | 1.88(0.19) | 1.82(0.13) | 2.17(0.17) | 3.11(0.23) | 7.15(0.59)
500 | 2.07(0.18) | 1.86(0.16) | 2.16(0.17) | 3.16(0.24) | 7.23(0.70)
M8 | 10 | 1.60(0.13) | 1.04(0.10) | 0.36(0.12) | 1.07(0.11) | 1.63(0.14)
50 | 0.56(0.05) | 0.66(0.10) | 0.42(0.04) | 0.64(0.09) | 0.60(0.09)
200 | 0.64(0.13) | 0.64(0.13) | 0.56(0.10) | 0.66(0.11) | 0.62(0.10)
500 | 0.60(0.08) | 0.72(0.09) | 0.40(0.04) | 0.65(0.08) | 0.61(0.08)

NOTE: The corresponding standard errors are given in parentheses.

##  Appendix E Additional real data examples

###  E.1 Color image dataset: Cifar10 and STL10 dataset.

In this part, we apply the proposed method to two color image datasets:
Cifar10 and STL10 dataset available at
https://www.cs.toronto.edu/~kriz/cifar.html and
https://cs.stanford.edu/~acoates/stl10/. The images in Cifar-10 dataset and
STL10 dataset are stored in $32\times 32\times 3$ matrices and $96\times
96\times 3$ matrices, respectively, indicating that the information contained
in images from Cifar-10 dataset is less and easier to reconstruct than those
in STL10 dataset. Since the images are of different sizes, we resize all
images into the size $128\times 128\times 3$, a commonly-used size for color
image generation.

The Cifar-10 dataset contains 60000 colored images in 10 classes, with 6000
images per class. STL10 dataset contains 13000 labelled images belonging to 10
classes on average, and 100000 unlabelled images, which may be images of other
types of animals or vehicles. For comparison, we consider several settings for
training.

(S1): For Cifar-10 dataset, we randomly select 10000 images for training, 1000
images for validation, and 10000 images for testing.

(S2): For STL10 dataset, we only pick the unlabelled images from the dataset,
and randomly select 80000 images for training, 1000 images for validation, and
2000 images for testing.

(S3): For STL10 dataset, we only pick the labelled images from the dataset,
and randomly partition them into three parts: 10000 training images, 1000
validation images, and 2000 test images.

(S4): We use the same images as in setting (S3), but use the training images
in each class to obtain different generators for different classes. In other
words, 10 generators are obtained as there are 10 classes of labelled images
in STL10 dataset.

We use the Fréchet inception distance (FID) score (Heusel et al.,, 2017) to
measure the performance of our method and compare it with other methods. Table
A.7 shows the FID scores for different settings. NLS has the highest FID
scores in all settings, which means it has the worst image reconstruction
quality. WGR has lower FID scores than cWGAN in setting (S1), (S2), and (S3),
but similar FID scores in setting (S4). Setting (S4) is the easiest one,
because it only requires learning the conditional distribution of one class,
while other settings require learning a mixture conditional distribution of
all classes. Our method achieves the lowest FID scores in all settings.

Table A.7: FID score of the three methods on the test dataset of color images. Method | (S1) | (S2) | (S3) | (S4)
---|---|---|---|---
NLS | 66.093 | 116.875 | 113.659 | 110.068
cWGAN | 32.669 | 75.211 | 72.731 | 66.669
WGR | 29.513 | 69.653 | 67.565 | 67.110

####  E.1.1 Image reconstruction: STL10 dataset

In this part, we apply WGR to the reconstruction task for color images. We use
the STL10 dataset, which is available at
https://cs.stanford.edu/~acoates/stl10/.

We preprocess the STL10 dataset by resizing all the images to $128\times
128\times 3$, which is a standard size for color image generation tasks. We
then simulate a missing data scenario by masking the central quarter part of
each image. Our goal is to reconstruct the masked part of the image.
Therefore, the covariates $X$ have a dimension of $128\times 128\times
3-65\times 65\times 3=36477$ and the response $Y$ has a dimension of $65\times
65\times 3=12675$.

Figure A.1 displays the reconstructed images from three different methods. The
images produced by WGR are more faithful to the original, as they have higher
clarity than NLS and higher accuracy than cWGAN. We use the FID score to
measure the quality of reconstructed images numerically. The FID scores of
NLS, cWGAN, and WGR are 113.66, 72.73, and 67.56 respectively. In this case,
our method achieves the lowest FID score, which implies that it reconstructs
images with better quality to a certain degree.

$X$ Truth WGR NLS cWGAN

Figure A.1: Reconstructed images in STL10 test dataset.