# Confidence Trigger Detection: An Approach to Build Real-time Tracking-by-
detection System

Zhicheng Ding
<EMAIL_ADDRESS>Edward Wong
<EMAIL_ADDRESS>
###### Abstract

With deep learning based image analysis getting popular in recent years, a lot
of multiple objects tracking applications are in demand. Some of these
applications (e.g., surveillance camera, intelligent robotics, and autonomous
driving) require the system runs in real-time. Though recent proposed methods
reach fairly high accuracy, the speed is still slower than real-time
application requirement. In order to increase tracking-by-detection system’s
speed for real-time tracking, we proposed confidence trigger detection (CTD)
approach which uses confidence of tracker to decide when to trigger object
detection. Using this approach, system can safely skip detection of images
frames that objects barely move. We had studied the influence of different
confidences in three popular detectors separately. Though we found trade-off
between speed and accuracy, our approach reaches higher accuracy at given
speed.

##  1 Introduction

Object detection has become a popular topic since the deep learning model’s
performance of image classification is better than any previous methods in
ILSVRC(2012) [8, 19, 20]. Many researchers has started to use deep learning
approaches to analyze images. Since a video consists of a continuous sequence
of image frames, the methods in video analysis are related to image analysis
and the new proposed approaches in image analysis can be used in video
analysis. In video analysis, besides analyzing images, it is significant to
explore association [1, 16, 25, 26] among image frames.

Tracking multiple objects [27] has many practical applications [2]:
surveillance camera, intelligent robotics, and autonomous driving. Most of the
recent studies have focused on tracking-by-detection [15] which requires
detecting, tracking, and objects association. First, the detector detects
objects in each image frame. Then, the tracker uses the information detected
in the previous frame to predict the current status of the object. Lastly,
building objects association using the locations and features provided by both
the detector and tracker [11].

To put such systems into real-world practices require both high tracking
accuracy and real-time performance [5]. Although there has been a large number
of algorithms proposed for multiple objects tracking in recent years, very few
of these algorithms can achieve real time performance. From the leaderboard of
MOTChallenge [17], we can observe trade-offs between speed and accuracy among
the differrent tracking algorithms proposed. High speed (Hz) in lower results
in lower multiple object tracking accuracy (MOTA) and higher MOTA results in
lower speed.

Skipping particular number of detection in image frames is a commonly used way
to increase the speed. The system could also skip all the frames until it is
ready after each tracking assignment [9]. Since the total amount of computing
is decreased, the time complexity of the system is increased. However, this
method has defects to the accuracy of tracking system [7]. For example, some
critical images get skipped and the tracking objects shift to a new location
or even get lost in a sudden.

Inspired by skipping frame, we proposed an approach that uses the confidence
of object association to trigger the object detection. Using this approach,
system safely skips the detection of image frame in which objects have small
movement. It triggers a new detection if any objects’ location between
prediction and detection is large. Thus, our proposed approach decreases the
time complexity of the system. The defects of accuracy is much lower than
skipping a fixed number of image frames. Specifically, the confidence is
inferred when associating the objects. The confidence is low if the distance
between the prediction of tracker and detection of the detector is long.
Compared with vanilla skipping frame, our approach has high accuracy at the
certain speed. In this paper, we demonstrate the benefits of this approach
using three different object detection models (YOLOv3 Tiny [22, 23],
MobileNet-SSD111https://github.com/chuanqi305/MobileNet-SSD [10], and
SqueezeNet [12]).

##  2 Related Work

###  2.1 Tracking-by-detection

Tracking-by-detection contains a detector and a tracker. For each image frame,
the detector detects and locates all the objects. Tracker predicts current
objects’ location using the previous state provided by detector. Then
associating objects information provided by detector and tracker. Finally,
updating the state of the tracker for object prediction in next image frame
[3]. The tracking-by-detection performs better accuracy because tracker’s bias
could be quickly fixed with up-to-date detector information.

###  2.2 Real-time Object tracking

It is impossible to use a certain speed to describe real-time performance of
all videos because the different camera capture the video in different speed.
But it is totally acceptable to describe a system performs a real-time
tracking if the output speed surpasses input speed [14]. Otherwise, the delay
of output aggregated and then the video and real event are out of sync. One
common way to achieve real-time performance is to skip all the image frames
until the system is ready for next image frame. An improvement of this method
suggests to skip a fixed number of images after each tracking assignment. But
it may skip critical image frames in which objects move in fast speed. As a
result, the accuracy decrease dramatically.

Our approach increases the speed by skipping detection in some image frame as
well. But we introduce confidence to actively trigger a new detection which
can quickly fix the bias. We will keep running tracker in each image frame
such that we know how further are tracker’s predictions away from latest
detection. This difference of distance will be used to infer confidence.
Comparing to skipping a fixed number of image frames, our approach skips less
important images frame in which objects have small movement. As a result, we
could use the confidence to trigger the detection before bias growing high and
help system performs faster.

###  2.3 Lightweight Detectors

Deep learning based lightweight detectors usually have fewer parameters or
have less pass of computation. Comparing with heavier detector, the
lightweight detector performs faster, but has less accuracy. We will use three
different level lightweight detectors (YOLOv3 Tiny, MobileNet-SSD, and
SqueezeNet) in this paper. The speed of tracking-by-detection system using
these detectors are 10.915 Hz, 15.604 Hz, and 21.673 Hz respectively. Then we
will apply CTD in each system to reach real-time performance. The frame of
test videos are 20 FPS.

####  2.3.1 YOLOv3 Tiny

YOLOv3 is an upgraded version of YOLO [23]. It changes to use a more complex
backbone for feature extraction [23]. To better detect small objects, YOLOv3
adds Feature Pyramid. Since YOLOv3 scans the images in one round, its time
complexity is much smaller than heavier detectors (e.g., R-CNN [6]). Using
YOLOv3, the system reaches the highest MOTA (0.328), but with lowest speed
(10.915 Hz).

####  2.3.2 MobileNet-SSD

MobileNets are neural networks that perform efficiently. It can also be used
on mobile devices and reach a fairly high accuracy [10]. SSD [18] uses VGG16
[24] to extract feature maps. SSD classifies and locates objects in a single
forward pass. MobileNet-SSD combines SSD and MobileNets which performs high
speed and relatively high accuracy. Using MobileNet SSD, the system reaches
the 0.175 MOTA and performs 15.604 Hz of speed.

####  2.3.3 SqueezeNet

SqueezeNet uses a squeeze layer and an expanded layer to reach a really fast
performance. The paper of SqueezeNet provides a quantitative analysis to show
that SqueezeNet can be 510 times fewer parameters to reach the same accuracy
as AlexNet [13]. Using SqueezeNet, the system reaches the lowest MOTA (0.094)
but performs the fastest (21.673 Hz).

###  2.4 Deep SORT

Deep SORT [25] is an extension of SORT [1] which incorporates appearance
information to match the objects. Because of this, it is possible to track the
objects even for a long period of occlusion. Besides, It uses Mahalanobis
distance [4] to incorporate motion information.

In our approach, we choose to use Deep SORT for two reasons. Firstly, Deep
SORT can match the objects even for long period occlusion. This is significant
because this can ensure objects can be matched after a proper number of frames
skipped. Secondly, we will use the Mahalanobis distance to infer the low
confidence to trigger detection.

Figure 1: framework of tracking-by-detection, including seven modules. Live
Video Stream provides a raw video stream to track. MOT Processing Center
receives live video stream and responses to data extracting and transmission.
Detector Warehouse storages pre-trained weights and corresponding models.
Detector loads model and weights, then detect the image if confidence is low.
Tracker Warehouse storages the tracker and pre-trained weight and model if
using deep learning based tracker. Tracker loads tracker model, makes
predictions, associated objects, and eventually output confidence. Output
Video shows raw video stream with tracking result of each detected objects.
The units in blue typically exist in the tracking-by-detection system. The
units green are our proposed units that utilize the confidence to trigger
detection. Figure 2: flowchart of confidence trigger detection. There are two
conditions to trigger detection: 1) a fixed detect frequency. 2) system is in
low confidence. Reset counter to 0 if the either detection condition is
matched, otherwise counter increment by 1. The confidence is set to low if
Mahalanobis distance is further than the threshold. The units in blue
typically exist in the tracking-by-detection system. The units green are our
proposed units that utilize the confidence to trigger detection.

##  3 Methodology

In this section, we will first give an overview of the tracking-by-detection
framework. Then, we will explain how the system infers the low confidence
status using Mahalanobis distance. Finally, we describe the work flow of our
proposed approach in this system.

###  3.1 Tracking-by-detection Framework

Figure 1 illustrates our tracking-by-detection framework which is easy to
integrate and combine different deep learning based detectors and trackers. We
will describe the responsibility of seven models in this framework below.

  * •

Live Video Stream is a video capturing module that captures the real-world
video using camera devices or loading video file in the local computer or
uniform resource locator (URL) in remote devices. In this study, we use local
2D video files provided by MOTChallenge 2015 [17].

  * •

MOT Processing Center processes image sequences frame-by-frame in three
different components: image preprocessing, detection info processing, and
tracking info processing. Specifically, we tried to reduce the noise and
resizing the image for neural network in Image Preprocessor unit. Detection
Info Processing unit discards the objects which are in low confidence. Then it
sends objects in high confidence to Tracker. As for Tracking Info Processor,
it embeds the location of objects on the image frame and decides when to send
the signal to the trigger detection.

  * •

Detector Warehouse storages pre-trained weights and corresponding models.

  * •

Detector loads the selected model and weights during initialization. Then
detector detects objects in image frame with a fixed frequency (e.g., detect
after 5 image frames) or gets triggered if low confidence condition is
matched. The detail of how tracker confidence work with detector would be
explained in section 3.3. In our study, we use YOLOv3 Tiny, MobileNet-SSD, and
SqueezeNet as detection respectively.

  * •

Tracker Warehouse storages both classic trackers and pre-trained deep learning
based trackers.

  * •

Tracker loads selected tracker model during initialization. Then the tracker
makes the prediction based on current parameters. Tracker information get
updated in every image frame. Hungarian algorithm is used to associate the
objects detected by the detector and predicted by the tracker. Then
Mahalanobis distance is used to associate motion information because the
Mahalanobis distance between prediction by tracker and new arrived location
follows a specific probability threshold of cumulative distribution function
(cdf) of inverse chi-square with four degrees of freedom. If Mahalanobis
distance is further, that means the tracker is in low confidence, and an
urgent detection is needed. We will describe how to calculate the distance in
detail in section 3.2. In our paper, we will use the Deep SORT which was
proposed recently.

  * •

Output Video contains both location and id of objects.

###  3.2 Confidence Inference

Firstly We followed the assignment strategy in Deep SORT that uses Mahalanobis
distance to incorporate states in Kalman Filter and detection information. The
Mahalanobis distance is defined as:

$M(i,j)^{2}=(x_{j}-\hat{y_{i}})^{T}(S_{i})^{-1}(x_{j}-\hat{y_{i}})$ (1)

where $i$ denotes the information at the $i$-th frame and $j$ denotes the
information at $j$-th frame. The $x_{j}$ is the matrix of all the predicted
bounding boxes at the $j$-th frame. The $y_{i}$ and $S_{i}$ represent the mean
and covariance of detected bounding boxes. Mahalanobis distance follows a chi-
square distribution [4]. Therefore, given probability $p$ and degrees of
freedom $v$, we can calculate the cdf of inverse of the chi-square with
degrees of freedom [21, 25] to get the distance threshold of certain
probability:

$d=F^{-1}(p|v)$ (2)

where $p$ can be calculated using cdf, shown as equation (3).

$p=F(x|v)=\int_{0}^{x}\frac{t^{(v-2)/2}\exp({x/2})}{2^{v/2}\Gamma(v/2)}dt$ (3)

where $\Gamma(\cdot)$ represents the Gamma function. In our paper, we will set
the degrees freedom $v$ as $4$. Then we will evaluate the performance of the
model with different probability $p$.

###  3.3 Workflow of Confidence Trigger Detection

Figure 2 demonstrates the flowchart of our proposed approach in a tracking-by-
detection system. Firstly, the system initializes parameters. Specifically, it
initialize the counter as 0 and the confidence as low. This force the system
trigger a detection in the first round. Then, the system captures the image
frame from a video stream and pre-processes the image frame, such as reducing
noise and resizing the image. Later on, the system decides to trigger
detection or directly make the prediction using the current state in the
tracker. The output of prediction and detection includes classes (i.e.,
pedestrian or background), confidences, and bounding boxes location (i.e., x
coordinate and y coordinate of top left point, width, and height) of each
object detected. The information from detector and tracker are used to
associate objects using Hungarian algorithm. Then, Mahalanobis distance is
used to incorporate motion information. After calculating Mahalanobis
distance, we compare it with the distance threshold $d$ which is the inverse
of the chi-square cdf with degrees of freedom $v$ and probability $p$. If
Mahalanobis distance is further than distance threshold $d$, the confidence is
lower than $p$. The confidence will be set to low and trigger a new detection
in the next round. Finally, the tracker gets updated and all tracking
information is added to the image frame for display. The confidence status and
counter status are sent back as the condition to trigger detection for the
next image frame.

(a) Frame 55

(b) Frame 56

(c) Frame 57

(d) Frame 58

(e) Frame 59

(f) Frame 60

(g) Frame 61

Figure 3: tracking result from frame 55 to frame 61 using confidence trigger
detection and image frames are cropped. There are 2 objects detected in these
image frames. The man wearing a black jacket is tagged with id 4 and the woman
with a baby are identified as id 2. The bounding boxes in white line are
predicted by tracker, and the bounding boxes in the blue line are detected by
the detector. The detect frequency is 10, and the latest detection is at frame
55. Therefore, there is no detection from frame 56 to frame 60. A detection is
triggered by low confidence status at frame 61.

(a) Speed of Different Confidence Threshold

(b) Accuracy of Different Confidence Threshold

Figure 4: speed (Hz) and accuracy (MOTA) of different confidence threshold
change along with detect frequency. We chose the integer from 1 to 11 as
detect frequency and 10%, 30%, 50%, 70%, 80%, 90%, 95%, and 100% as confidence
threshold. It worth mentioning that the system with 100% of confidence
threshold is equivalence of not using CTD. The detect frequency is 1 means
detection is used for each time frame whatever confidence threshold is. We
take 100% confidence threshold as baseline since it doesn’t use CTD.

(a) Accuracy of Different Speed (YOLOv3 Tiny)

(b) Accuracy of Different Speed (MobileNets SSD)

(c) Accuracy of Different Speed (SqueezeNet)

Figure 5: The accuracy (MOTA) of different confidence threshold change along
with speed . We chose 10%, 30%, 50%, 70%, 80%, 90%, 95% and 100% (i.e., not
using CTD) as confidence threshold. We take 100% confidence threshold as
baseline since it doesn’t use CTD. (a), (b), and (c) are the result of
different level of models. (a) YOLOv3 Tiny has the highest accuracy but also
has lowest speed. (b) MobileNets SSD performs average of accuracy and speed.
(c) SqueezeNet has lowest accuracy but has highest speed. It performs in real-
time without skipping any image frames.

##  4 Experiment

In this section, we will describe the video clips and models that are chosen
for this study. Next, we will explain the reason for such combination in
detailed. Then, we will demonstrate how CTD helps tracking-by-detection system
improve the performance at a certain speed. Lastly, we compared the vanilla
tracking-by-detection approach and using CTD approach in multiple object
tracking platform.

###  4.1 Setting

We developed the tracking-by-detection system followed the framework described
in section 3.1. We firstly choose Deep SORT as the tracker because it performs
in real-time, the fewest number of identity switches and competitive MOTA
scores [25]. We chose three different performance of detectors (i.e., YOLOv3
Tiny, MobileNets SSD, and SqueezeNet). The integrated YOLOv3 Tiny, MobileNets
SSD, and SqueezeNet perform 10.915 Hz, 15.604 Hz, 21.673 Hz of speed
respectively. The similar tradeoff also exists among these three model, the
tracking accuracy (MOTA) of the vanilla model in the system is 0.328, 0.175,
0.094 respectively.

We choose 2D video clips in MOTChallenge 2015 [17]. It provides 11 video clips
for training and the other 11 video clips for testing. The variations of
target motion, camera viewing angle, and pedestrian density in these video
clips are high. We study how different confidence threshold influences the
accuracy and speed using the training dataset. Then, we choose the confidence
threshold with the best accuracy and over 20 Hz speed (i.e., YOLOv3 Tiny with
detection frequency 4 and confidence threshold 30%) and evaluate the accuracy
and speed using testing dataset.

Table 1: Comparison of using and not using CTD model in 2D MOT 2015 Method | MOTA $\uparrow$ | MOTP $\uparrow$ | MT $\uparrow$ | ML $\downarrow$ | ID Sw. $\downarrow$ | FP $\downarrow$ | FN $\downarrow$ | Runtime (Hz) $\uparrow$
---|---|---|---|---|---|---|---|---
EAMTTpub | 22.3 | 70.8 | 5.4% | 52.7 % | 833 | 7924 | 38982 | 12.1
lightgray TraByDetOriginal (vanilla) | 22.2 | 71.0 | 6.0% | 47.9% | 1371 | 4664 | 41767 | 8.1
SAS_MOT15 | 22.2 | 71.1 | 3.1% | 61.6% | 1240 | 5591 | 41531 | 8.9
OMT_DFH | 21.2 | 69.9 | 7.1% | 46.5% | 1255 | 13218 | 34657 | 7.2
DCO_X | 19.6 | 71.4 | 5.1% | 54.9 | 819 | 10652 | 38232 | 0.3
lightgray TraByDetRT (CTD) | 19.5 | 70.6 | 5.1% | 54.0% | 1289 | 5115 | 43059 | 21.2
TC_SIAMESETC_SIAMESE | 19.3 | 70.7 | 2.6% | 67.5 | 294 | 6127 | 42596 | 13.0
RMOT | 18.6 | 69.6 | 5.3% | 53.3 | 684 | 12473 | 36835 | 7.9
lightgray TraByDetSF (skip frame) | 18.3 | 70.5 | 5.0% | 55.2 | 1280 | 5437 | 43465 | 22.9
ALExTRAC | 17.0 | 71.2 | 3.9% | 52.4 | 1859 | 9233 | 39933 | 3.7

###  4.2 Trigger Detection in Low Confidence Condition

We use YOLOv3 Tiny to show the result due to its high MOTA. To better
distinguish which factor trigger the detection, we set the detection frequency
as 10 because the detection is triggered by either counter reach detection
frequency or low confidence status. We observe that a new detection is trigger
at frame 55 and another detection is trigger due to low confidence at frame
61. Thus, we use frame 55 to frame 61 to demonstrate our experiment.

Figure 3 shows how CTD work from frame 55 to frame 61. To better illustrate
the result, we crop the image frames and leave only two objects in the image.
The white bounding box is predicted by tracker using last states, and the blue
bounding box is detected by detection. There are two objects in this scenario.
The system tag the man wearing a black jacket and the woman with a baby as id
4 and id 2 respectively. The woman with the baby and other cropped objects
barely move during these image frames, and only the man is moving to the right
in relatively fast speed. As a result, in this case, man in the black jacket
is the target that trigger low confidence condition. So we will focus on
analyzing the bounding boxes of the man below.

  1. 1.

Trigger Detection. At frame 55, a new detection is triggered. As a result of
the bounding box of tracking (white) shift to the bounding box of the detector
(blue). The previous bias between the bounding boxes quickly fix. In this
case, the confidence is strongly high.

  2. 2.

High Confidence Frames. From frame 56 to frame 59, the blue bounding box stays
still because the detection gets skipped. However, the white bounding box is
still predicted by the tracker. The prediction shows that the man is moving to
the right with a rough speed according to the motion of the man. Consequently,
the white bounding box is slightly moved to the right frame by frame. The
confidence is fairly high because the bounding boxes are still close.

  3. 3.

Detect Low Confidence. At frame 60, the white bounding box keeps moving to the
right and the blue bounding box doesn’t change. But the white bounding box
exceeds the blue bounding box too much such that confidence turns to low and
trigger a detection in the next image frame.

  4. 4.

Trigger Detection. At frame 61, the blue bounding box gets updated because a
new detection is triggered by the condition of low confidence. So the
tracker’s white bounding box shift to the detector’s blue bounding box.

Based on the motion of bounding boxes from frame 55 to frame 61, we
demonstrate that the CTD helps the system to improve the speed by skipping the
detections in some image frames. In addition, according to the distance
between the white bounding box and blue bounding box, we find that system only
skips detection when the Mahalanobis distance is close. Once the distance gets
far away and confidence is low, the detection is trigged in next image frame.
Accordingly, our proposed approach helps the system to skip the detection at
the image frame when objects have less movement.

###  4.3 Tradeoff between Accuracy and Speed

Similar to the method of using a fixed detection frequency, the CTD increases
overall speed by skipping detection at image frames. Therefore, this approach
also has defects to the accuracy. Therefore, we choose different confidence
threshold to study the tradeoff between accuracy and speed using confidence
trigger detection approach.

First of all, we will compare the speed of YOLOv3 detector with different
detection frequency and different confidence threshold. We chose the integer
from 1 to 11 as detect frequency. We chose confidence threshold 10%, 30%, 50%,
70%, 80%, 90%, 95% and 100% (i.e., not using CTD) to study. We choose 100%
confidence threshold as a baseline for further comparison. Figure 4 (a) and
(b) shows how the speed (Hz) and accuracy (MOTA) change along with different
detect frequency. We observed that 95% confidence threshold was very close to
baseline which has the highest speed but lowest accuracy almost all the time.
As confidence threshold getting smaller, the speed increases smaller. but also
the accuracy decrease smaller.

Then we plot speed (Hz) and accuracy (MOTA) in the same plot. Figure 5 (a)
shows how accuracy changes along with speed using YOLOv3 Tiny as the detector.
We notice that using CTD can increase the accuracy at a certain speed.
Furthermore, lower confidence threshold cannot reach fast speed since the
condition of low confidence is met easily. Figure 5 (b) and (c) demonstrates
that other level of detectors (MobileNets SSD and SqueezeNet) have the similar
improvement.

Lastly, we submit the tracking result of three models to 2D MOT 2015. All the
models are using YOLOv3 Tiny as detector since it has the highest accuracy
among these model. Model #1 doesn’t use CTD and detects at each image frame.
Model #2 has real-time speed and best performance; the confidence threshold is
30% and detects frequency is 5. Model #3 doesn’t use CTD and its detect
frequency is 5.

Table 1 illustrates the result of using and not using CTD in MOTChallenge. The
TraByDetOr (vanilla) is the model #1 which detect in every image frame. The
TraByDetRT (use CTD) represents model #2 which performs in real-time and has
the highest accuracy. The TraByDetSF (skip frame) is model #3 which doesn’t
use CTD and has the same detect frequency as model #2

Comparing with the baseline model #1, model #2 and model #3 have increased
speed by 161.73%, 182.72% and have decreased accuracy by 12.16%, 17.56%
respectively. Hence, the CTD approach improves speed by skipping the detection
with less accuracy decreased.

##  5 Conclusion

In this paper, we proposed a novel approach that uses the confidence of
tracker for actively trigger detection. The confidence is low if the
prediction of the tracker is far away from the detection. As a result, the
system skips the detection in some image frames. This approach increases the
speed of the tracking-by-detection system. Using CTD in the system reaches a
higher particular range of speed with a much smaller accuracy drop comparing
with skipping with a fixed number of frames.

## References

  * [1] A. Bewley, Z. Ge, L. Ott, F. Ramos, and B. Upcroft.  Simple Online and Realtime Tracking.  2016\.
  * [2] I. Bouchrika, J. N. Carter, and M. S. Nixon.  Towards automated visual surveillance using gait for identity recognition and tracking across multiple non-intersecting cameras.  Multimedia Tools and Applications, 2016.
  * [3] M. D. Breitenstein, F. Reichlin, B. Leibe, E. Koller-Meier, and L. Van Gool.  Online multiperson tracking-by-detection from a single, uncalibrated camera.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011\.
  * [4] G. Chang.  Robust Kalman filtering based on Mahalanobis distance as outlier judging criterion.  Journal of Geodesy, 2014.
  * [5] A. Cvpr and P. Id.  Speed / accuracy trade-offs for modern convolutional object detectors - 3562.  Cvpr, pages 7310–7319, 2017.
  * [6] R. Girshick, J. Donahue, T. Darrell, and J. Malik.  Rich feature hierarchies for accurate object detection and semantic segmentation.  In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2014.
  * [7] S. Gould, J. Arfvidsson, A. Kaehler, B. Sapp, M. Messner, G. Bradski, P. Baumstarck, S. Chung, and A. Y. Ng.  Peripheral-foveal vision for real-time object recognition and tracking in video.  International Joint Conference on Artificial Intelligence, 2007\.
  * [8] Y. Guo, Y. Liu, A. Oerlemans, S. Lao, S. Wu, and M. S. Lew.  Deep learning for visual understanding: A review.  Neurocomputing, 2016.
  * [9] T. Hall.  In vivo real-time freehand palpation imaging.  Ultrasound in Medicine & Biology, 2003.
  * [10] A. G. Howard, M. Zhu, B. Chen, D. Kalenichenko, W. Wang, T. Weyand, M. Andreetto, and H. Adam.  MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications.  2017\.
  * [11] C. H. Huang, E. Boyer, B. D. C. Angonese, N. Navab, and S. Ilic.  Toward user-specific tracking by detection of human shapes in multi-cameras.  In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2015.
  * [12] F. N. Iandola, M. W. Moskewicz, K. Ashraf, S. Han, W. J. Dally, and K. Keutzer.  SqueezeNet.  arXiv, 2016.
  * [13] A. Krizhevsky, I. Sutskever, and G. E. Hinton.  Alexnet.  Advances In Neural Information Processing Systems, 2012.
  * [14] S. M. Kuo, B. H. Lee, and W. Tian.  Real-Time Digital Signal Processing: Fundamentals, Implementations and Applications.  2013\.
  * [15] N. Le, A. Heili, and J. M. Odobez.  Long-term time-sensitive costs for CRF-based tracking by detection.  In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2016.
  * [16] L. Leal-Taixe, C. Canton-Ferrer, and K. Schindler.  Learning by Tracking: Siamese CNN for Robust Target Association.  In IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, 2016.
  * [17] L. Leal-Taixé, A. Milan, I. Reid, S. Roth, and K. Schindler.  MOTChallenge 2015: Towards a benchmark for multi-target tracking.  arXiv:1504.01942 [cs], Apr. 2015.  arXiv: 1504.01942.
  * [18] W. Liu, D. Anguelov, D. Erhan, C. Szegedy, S. Reed, C. Y. Fu, and A. C. Berg.  SSD: Single shot multibox detector.  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9905 LNCS:21–37, 2016.
  * [19] H.-W. Ng, V. D. Nguyen, V. Vonikakis, and S. Winkler.  Deep Learning for Emotion Recognition on Small Datasets using Transfer Learning.  Proceedings of the 2015 ACM on International Conference on Multimodal Interaction - ICMI ’15, pages 443–449, 2015.
  * [20] M. Oquab, L. Bottou, I. Laptev, and J. Sivic.  Learning and Transferring Mid-Level Image Representations using Convolutional Neural Networks.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2014.
  * [21] K. Pearson.  On the Criterion that a Given System of Deviations from the Probable in the Case of a Correlated System of Variables is Such that it Can be Reasonably Supposed to have Arisen from Random Sampling, pages 11–28.  Springer New York, New York, NY, 1992.
  * [22] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi.  （2016 YOLO）You Only Look Once: Unified, Real-Time Object Detection.  Cvpr 2016, 2016.
  * [23] J. Redmon and A. Farhadi.  YOLOv3: An Incremental Improvement.  2018\.
  * [24] K. Simonyan and A. Zisserman.  Very Deep Convolutional Networks for Large-Scale Image Recognition.  International Conference on Learning Representations (ICRL), 2015\.
  * [25] N. Wojke, A. Bewley, and D. Paulus.  Simple online and realtime tracking with a deep association metric.  Proceedings - International Conference on Image Processing, ICIP, 2017-Septe:3645–3649, 2018.
  * [26] Y. Xiang, A. Alahi, and S. Savarese.  Learning to track: Online multi-object tracking by decision making.  In Proceedings of the IEEE International Conference on Computer Vision, 2015.
  * [27] B. Zhong, Y. Chen, Y. Shen, Y. Chen, Z. Cui, R. Ji, X. Yuan, D. Chen, and W. Chen.  Robust tracking via patch-based appearance model and local background estimation.  Neurocomputing, 2014.


††thanks: These two authors contributed equally††thanks: These two authors
contributed equally

# Provably-secure randomness generation from
switching probability of magnetic tunnel junctions

Hong Jie Ng  Department of Electrical & Computer Engineering, National
University of Singapore, Singapore  Shuhan Yang  Department of Electrical &
Computer Engineering, National University of Singapore, Singapore  Zhaoyang
Yao  Department of Electrical & Computer Engineering, National University of
Singapore, Singapore  Hyunsoo Yang<EMAIL_ADDRESS>Department of
Electrical & Computer Engineering, National University of Singapore, Singapore
Charles C.-W. Lim<EMAIL_ADDRESS>Department of Electrical & Computer
Engineering, National University of Singapore, Singapore

###### Abstract

In recent years, true random number generators (TRNGs) based on magnetic
tunnelling junction (MTJ) have become increasingly attractive. This is because
MTJ-based TRNGs offer some advantages over traditional CMOS-based TRNGs, such
as smaller area and simpler structure. However, there has been no work thus
far that quantified the quality of the raw output of an MTJ-based TRNG and
performed suitable randomness extraction to produce provably-secure random
bits, unlike their CMOS-based counterparts. In this work, we implement an MTJ-
based TRNG and characterise the entropy of the raw output. Using this
information, we perform post-processing to extract a set of random bits which
are provably-secure.

##  I Introduction

Random numbers are used in a myriad of applications, from Monte Carlo
simulations for scientific research to encryption for data security. Without a
doubt, random numbers are widely sought after, and much research has been done
to construct random number generators (RNGs) that output high quality random
numbers. The quality of random numbers can be characterised by two properties
- uniformity and predictability. Indeed, in the ideal scenario, random numbers
ought to be uniformly random and unpredictable from any perspective.

There are typically two classes of generators. They are the pseudo random
number generator (PRNG) and true random number generator (TRNG). PRNGs make
use of an algorithm, together with a short input random seed, to produce a
longer sequence of random numbers that are uniformly distributed. However,
PRNGs are deterministic algorithms at their core. Thus, any party with
knowledge of the seed could predict the output of the PRNG perfectly. It is
also possible for an observer to use the first few outputs of a PRNG to gain
information about its current state, allowing the observer to accurately
predict the subsequent outputs of the PRNG. RandCrack [1], a Python script
that was written in 2017, only requires the first 624 numbers of the Mersenne
Twister [2] PRNG to be able to predict the following output numbers with high
accuracy. In fact, the Mersenne Twister PRNG is widely used in C, Matlab, and
Python due to its supposedly strong generator properties.

Briefly speaking, TRNGs utilise the randomness from physical processes (e.g.
time taken for atomic decay) to generate random numbers. These processes are
inherently random and unpredictable. Hence, they do not exhibit the
shortcomings of PRNGs. Over the years, there have been many variations of
TRNGs that have been implemented [3, 4, 5, 6, 7, 8, 9]. TRNGs based on
magnetic tunnelling junction (MTJ) were first proposed in 2014 [10]. Compared
to their CMOS-based counterparts, some attractive features of MTJ-based TRNGs
include a smaller area, a simpler structure, and scalability with silicon
large-scale integration technology [11].

An MTJ device consists of two magnetic layers, which are the fixed layer and
free layer. Depending on the relative magnetic alignment of the two magnetic
layers, the MTJ exhibits two different stable states, namely the parallel (P)
state and anti-parallel (AP) state. To switch between these states, we can
take advantage of spin transfer torque (STT), which utilizes current to
manipulate the direction of the magnetic moment of the free layer [12]. In a
memory device, current pulses are applied to set the MTJ in one of the stable
states. However, by adjusting the amplitude and width of the current pulses,
the MTJ can be perturbed to the metastable state, as shown in Fig. 1. At the
metastable state, thermal fluctuations determine the final state of the MTJ
and give rise to randomness [10].

Figure 1: Illustration of STT-MTJ random number generation principle. (left)
Two stable low energy states; (right) the metastable state.

A system is considered as provably-secure if the system’s security can be
formally expressed or bounded using mathematical statements, under some
general assumptions about the generator and its physics. This is in contrast
to the usual heuristic analysis, which typically considers the bounded
adversary model, i.e., computationally bounded adversaries. Indeed, a
provably-secure framework is most desirable, especially for important systems
such as encryption and random number generation, where their security has to
be lasting and independent of technological advancements. In addition, such a
classification provides an operational meaning as well. In the case of RNGs,
this definition implies that an adversary will be unable to distinguish the
output of the RNG from a truly uniform and random data, except with a
vanishingly small probability.

To the best of our knowledge, previous works that have implemented MTJ-based
TRNGs did not obtain provably-secure random numbers. One of the works [13]
performed entropy estimation on a 1 Mbit dataset, which is too small in size.
Thus, they did not perform suitable post-processing to obtain provably secure
random numbers. Other works did not characterise the entropy of the raw output
[10] or provided only a partial characterisation of the raw output by assuming
that the raw bits are independent [14, 15]. In this work, we implement a MTJ-
based TRNG setup and characterise the min-entropy of the raw output. Our min-
entropy characterisation is carried out with minimal assumptions as we do not
assume that the raw output bits are independent. We then perform suitable
post-processing in the form of randomness extraction to obtain a set of
provably-secure random numbers.

The remaining of this paper is organised as follows. In section II, we provide
the implementation details for our work, including the experimental setup of
our MTJ-based TRNG and the tuning of parameters. In section III, we explain
the idea behind provably-secure randomness extraction, and give a mathematical
definition for the ideal output of an RNG. In section IV, we characterise the
raw output of our MTJ-based TRNG and choose a suitable function to perform
randomness extraction. Lastly, we present the final post-processed results in
section V and give a conclusion in section VI.

##  II Implementation

Figure 2: Measured R-V hysteresis curve of the fabricated MTJ device. The gray
arrow represents the P to AP switching, and the red arrow represents the AP to
P switching.

In this work, the TRNG is implemented using STT-MTJ. Fig. 2 shows the measured
resistance against voltage (R-V) hysteresis curve of the fabricated MTJ
device. The tunnelling magneto-resistance ratio (TMR) is $\sim$200%. The
writing operation of the STT-MTJ is a stochastic process, which is influenced
by thermal fluctuations [16, 17, 18]. By carefully tuning the input pulses’
amplitude and width, the switching probability of MTJ can be set to 50%. This
makes it possible to implement TRNG using STT-MTJ. Moreover, because MTJ-based
TRNGs can be integrated with CMOS chips in high density [19], it can be a
great candidate for future true random number generation devices.

Figure 3: Random number generation setup. Keysight 81134A generates reset
pulses from CH1, and perturb pulses from CH2. The trigger signal from the DAQ
card ensures the simultaneous start of the pulse generation and the reading
operation. Equipment is controlled by LabVIEW interface.

Fig. 3 shows the setup of our MTJ-based TRNG. The setup includes a pulse
generator (Keysight 81134A) for generating reset and perturb pulses, a DAQ-mx
(NI-USB 6363), and a R=3 k$\Omega$ resistor for reading operation. To
guarantee the simultaneous start of the pulse generation and the reading
operation, a trigger signal from DAQ to the pulse generator is applied. The
negative reset pulse from CH1 of the pulse generator and the positive perturb
pulse from CH2 are combined in the power combiner. Due to the non-volatility
of MTJ devices, a reset step is required before every bit of random number
generation. Thus, a random number generation cycle consists of three steps:
reset, perturb, and read [19].

For the reading purpose, a DC offset voltage ($V_{\text{offset}}$) of 50 mV is
superpositioned to the input signal. The MTJ resistance can be expressed as

$R_{\text{MTJ}}=\frac{V_{\text{MTJ}}}{V_{\text{offset}}-V_{\text{MTJ}}}R.$ (1)

where $R_{\text{MTJ}}$ is the MTJ resistance, $V_{\text{MTJ}}$ is the voltage
drop across the MTJ, $V_{\text{offset}}$ is the offset voltage applied for
reading purpose, R is the resistor in series to the MTJ. Fig. 4 shows the time
sequence of one random bit generation cycle. A negative reset pulse
($V_{\text{reset}}$) with an amplitude of -900 mV and width of 1 $\mu$s is
first applied to reset the MTJ to the low resistance parallel state. After the
reset pulse, a positive pulse ($V_{\text{perturb}}$) with an amplitude of 652
mV and width of 1 $\mu$s is applied to perturb the MTJ to the metastable
state. One cycle of random number generation takes 8 $\mu$s. The reading
operation performed by the DAQ card is conducted at 2 MHz throughout the whole
process. Thus, the DAQ card can read out 16 data points for one cycle. To
obtain MTJ resistance, only data points corresponding to sequence III should
be used. To ensure this, it is required that the data points corresponding to
reset and perturb pulses can be clearly identified. Therefore, the pulse width
of reset and perturb pulses cannot be too short, otherwise it would be hard to
differentiate them. This is why in our case, 1 $\mu$s pulse width is chosen.
After selecting out the correct sequence of data points, we take the average,
and set 4 k$\Omega$ as the threshold in order to split the raw data into 2
bins. Finally, binary random numbers are output according to the final state
in which the MTJ is in.

Figure 4: Random number generation time sequence. One cycle of random number
generation comprises three sub-sequences, which are I: reset operation; II:
perturb operation; III: reading operation.

##  III Provably-secure randomness extraction from weakly random source

Consider an RNG that outputs a binary string. In the ideal scenario, the
output has to satisfy 2 conditions, which are 1) all the bits in the string
are uniformly distributed, and 2) all the bits are independent from any
perspective. An $m$-bit string that satisfies both criteria is referred to as
the ideal output and denoted as $U_{m}$.

For our MTJ-based TRNG, the raw output is most definitely not uniformly
distributed. This is because the thermal noise (or any of the other noise
sources present) is unlikely to remain constant throughout the entire
experiment. Deviations in the thermal noise, no matter how small in magnitude,
would skew the distribution of the output bits away from the uniform
distribution. In addition, it would be naive to assume that the raw output
bits are independent of each other. Imperfections in the experimental setup
(e.g. noisy reader) might introduce correlations to the raw output bits. In
fact, the raw output data failed the permutation test and Chi-square test
outlined in the NIST 800-90B test suite [20], which tests for independence. A
sequence under test can be classified as independent and identically
distributed (i.i.d.) if they pass these tests.

Clearly, the $n$-bit raw output of our MTJ-based TRNG does not satisfy the 2
criteria stated at the beginning of the section. Hence, it is classified as a
weakly random source, which we denote as $X$. We thus have to utilise
functions known as randomness extractors (with the help of a seed, $S$) to
extract an $m$-bit almost ideal output, $Z$, from the raw output of our MTJ-
based TRNG. The process can be written as $Z=\mathrm{Ext}(X,S)$. We use the
notion of statistical distance to determine how close $Z$ is to the ideal
output $U_{m}$.

The statistical distance between two random variables, $Y$ and $Y^{\prime}$,
is defined as

$\triangle(Y,Y^{\prime}):=\frac{1}{2}\sum_{y\in\mathscr{Y}}\bigg{|}P_{Y}(y)-P_{Y^{\prime}}(y)\bigg{|},$
(2)

where $\mathscr{Y}$ is the range of values that $Y\text{ and }Y^{\prime}$ can
take. If $Y$ and $Y^{\prime}$ are identically distributed, then their
statistical distance is 0. On the other hand, if they are perfectly
distinguishable, then their statistical distance is 1.

Intuitively, $m<n$, because it is not possible to generate randomness from
nothing. This also means that for the extraction to be possible, $X$ must
contain at least $m$-bits of randomness. To characterise the amount of
extractable random bits that is present in a weakly random source, we use the
notion of min-entropy. The min-entropy of $X$ is defined as

$H_{\mathrm{min}}(X):=\min_{x\in\mathscr{X}}\bigg{[}-\mathrm{log}_{2}P_{X}(x)\bigg{]},$
(3)

where, $\mathscr{X}$ is the range of values that $X$ can take. Notice that we
use min-entropy instead of the Shannon entropy to characterise the extractable
randomness. To explain why, let us consider an extractor that outputs an ideal
$Z$, i.e. $P_{Z}(z)=2^{-m}\text{ for all }z\in\mathscr{Z}$, where
$\mathscr{Z}$ is the range of values that $Z$ can take. Any $z\in\mathscr{Z}$
thus has to satisfy

$P_{Z}(z)=\sum_{x:\mathrm{Ext}(X)=z}P_{X}(x)=2^{-m}.$ (4)

Clearly, the implication is that $P_{X}(x)\leq 2^{-m}$ for all
$x\in\mathscr{X}$. Therefore, to extract $m$ random bits from $X$, it is
necessary that $H_{\mathrm{min}}(X)\geq m$.

Now that the preliminaries have been introduced, we provide a formal
definition for randomness extraction.

######  Definition 1 (Strong seeded extractors [21]).

The function
$\mathrm{Ext}:\\{0,1\\}^{n}\times\\{0,1\\}^{r}\rightarrow\\{0,1\\}^{m}$ is a
$(k,\varepsilon)$-strong extractor if for any source $X$ with
$H_{\mathrm{min}}(X)\geq k$ and seed $S=U_{r}$, its output
$Z=\mathrm{Ext}(X,S)$ satisfies $\triangle(ZU_{r},U_{m}U_{r})\leq\varepsilon$,
where $YY^{\prime}$ represents the concatenation of the strings $Y$ and
$Y^{\prime}$.

The implication of a strong extractor is that the output $Z$ remains uniformly
random even in the presence of seed $S$, i.e. $Z$ and $S$ are independent of
each other. Operationally, this means that we are able to concatenate the seed
used to the output of the strong extractor, without any increase in the
security parameter. This is important because in Toeplitz hashing, the seed
used is longer than the output length. Thus, if we do not use a strong
extractor, there will be no net randomness extracted since we consume more
randomness than we extract. We follow up by providing the definition of
universal hashing.

######  Definition 2 (Universal hash functions [22]).

A family of hash functions
$\mathscr{F}=\\{f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{m}\\}\text{ with }n\geq
m$ is called universal if for $f$ randomly chosen from $\mathscr{F}$,

$\mathrm{Pr}[f(x)=f(x^{\prime})]\leq 2^{-m},\hskip 5.69054pt\forall\text{
}x\neq x^{\prime}\in\\{0,1\\}^{n}.$ (5)

In our application, we use the random seed $S$ to choose a function from the
family of universal hash functions. We denote the chosen function as $f_{s}$.
This also means that the family of universal hash functions has size
$|\mathscr{F}|=2^{r}$. Importantly, the work in [23] showed that universal
hash functions can be used to construct strong seeded extractors. We provide
the definition below.

######  Definition 3 (Leftover hash lemma [23]).

Let $X$ be a min-entropy source with $H_{\min}(X)\geq k$ and
$\mathscr{F}=\\{f_{s}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{m}\\}$ be a universal
hashing family of size $2^{r}$ with $m=\lfloor
k-2\log_{2}(1/\varepsilon)+2\rfloor$. Furthermore, let
$\mathrm{Ext}(X,s)=f_{s}(X)$. Then, the extractor is a
$(k,\varepsilon)$-strong extractor with seed length $r$ and output length $m$.

Hence, using a family of universal hash functions to perform randomness
extraction allows us to obtain an extracted output that is provably-secure,
i.e. we are able to bound how close our extracted output is to the ideal
output. Another advantage is that such a security definition also adheres to
the universal composability framework proposed in [24, 25]. The implication is
that if we use the extracted output in other protocols, the security parameter
of that protocol will increase by $\varepsilon$.

##  IV Entropy estimation and extraction

We shall denote the $n$-bit raw binary random numbers that our MTJ-TRNG
produces as $X$. We can classify $X$ as uniformly random if
$H_{\text{min}}(X)=n$. However, as mentioned in section III, more often than
not, our MTJ-TRNG produces a string that is not uniformly random, i.e.
$H_{\text{min}}(X)<n$. Thus, we have to lower-bound the min-entropy of $X$
using techniques like the NIST 800-90B entropy estimation suite [20] to
certify that $H_{\text{min}}(X)\geq k$. Using this estimate of $k$, we are
able to quantify the amount of extractable randomness in $X$ and extract an
$m$-bit output string $Z$, such that $m\leq k$. The string produced is
$\varepsilon$-close to the ideal uniform $m$-bit distribution, $\text{U}_{m}$,
i.e. $\triangle(Z,\text{U}_{m})\leq\varepsilon$.

The results that we obtain from NIST 800-90B indicate that the min-entropy per
bit of $X$ is 0.778584. It should be noted that we do not assume independence
of the raw bits when performing min-entropy estimation. We collected
$n=217,504,350$ bits, which translates to $k=169,345,406$ bits. We set our
security parameter to be $\varepsilon=10^{-10}$, and employ the leftover hash
lemma [23] to obtain $m=\lfloor
k-2\text{log}_{2}(1/\varepsilon)+2\rfloor=169,345,260$ bits.

The extraction is carried out via Toeplitz hashing, which belongs to a family
of universal hash functions [26]. Toeplitz hashing utilises a Toeplitz matrix,
T. The Toeplitz matrix is an $m\times n$ diagonal-constant matrix, and it is
constructed by filling up the first column and first row of the matrix with a
uniform seed, denoted by $S$. Thus, the seed length required for Toeplitz
hashing is $n+m-1$ bits. $Z$ is obtained by performing $Z=\textbf{T}\cdot X$,
which is expressed as

$\begin{bmatrix}s_{n}&s_{n-1}&\cdots&s_{2}&s_{1}\\\
s_{n+1}&s_{n}&\cdots&s_{3}&s_{2}\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
s_{n+m-1}&s_{n+m-2}&\cdots&s_{m+1}&s_{m}\end{bmatrix}\cdot\begin{bmatrix}x_{1}\\\
x_{2}\\\ \vdots\\\ x_{n-1}\\\ x_{n}\end{bmatrix}=\begin{bmatrix}z_{1}\\\
z_{2}\\\ \vdots\\\ z_{m}\end{bmatrix}.$

The computational complexity of Toeplitz hashing is $O(n^{2})$ due to the need
to perform matrix-vector multiplication. However, this is undesirable, as $n$
needs to be a large number for us to be able to accurately characterise the
min-entropy of the raw data. To improve the computational complexity of
Toeplitz hashing, we utilise the fast Fourier transform (FFT) algorithm. The
FFT algorithm speeds up matrix-vector multiplications when the matrix used is
a circulant matrix. In this case, Toeplitz matrix T is not a circulant matrix,
but it can easily be converted into one by padding T with additional rows and
columns, and filling up these rows and columns with 0s and 1s accordingly to
obtain $\textbf{T}_{\text{circ}}$. As $\textbf{T}_{\text{circ}}$ has a larger
number of columns than T, we have to pad $X$ with 0s to get $X_{\text{pad}}$.
The main process of Toeplitz hashing accelerated by FFT can then be expressed
as

$Z_{\text{pad}}=IFFT(FFT(X_{\text{pad}})\cdot
FFT(\text{T'}_{\text{circ}}))=\textbf{T}_{\text{circ}}\cdot X_{\text{pad}},$

where $FFT\text{ and }IFFT$ are the FFT algorithm and its inverse
respectively, $\text{T'}_{\text{circ}}$ is the first column of
$\textbf{T}_{\text{circ}}$, and $Z_{\text{pad}}$ is the extended output. The
original output $Z$ can be recovered by keeping the first $m$ bits of
$Z_{pad}$. The computational complexity of Toeplitz hashing with FFT is
$O(n\log n)$, which is an exponential improvement from the initial
computational complexity.

##  V Results

| Raw data | Extracted data
---|---|---
Statistical test | P-value | Proportion | Result | P-value | Proportion | Result
Frequency | 0.0000 | 0.1901 | Failure | 0.2315 | 1.0000 | Success
Block frequency | 0.0000 | 0.8651 | Failure | 0.9233 | 0.9882 | Success
Cumulative sums | 0.0000 | 0.1839 | Failure | 0.4201 | 1.0000 | Success
Runs | - | - | - | 0.8606 | 0.9941 | Success
Longest run | 0.0000 | 0.1797 | Failure | 0.6436 | 1.0000 | Success
Rank | 0.1806 | 1.0000 | Success | 0.4547 | 0.9822 | Success
FFT | 0.0000 | 0.5253 | Failure | 0.4666 | 1.0000 | Success
Non-overlapping template | 0.0000 | 0.0000 | Failure | 0.0001 | 0.9704 | Success
Overlapping template | 0.0000 | 0.0335 | Failure | 0.0024 | 0.9941 | Success
Universal | 0.0000 | 0.0000 | Failure | 0.6825 | 0.9882 | Success
Approximate entropy | - | - | - | 0.5659 | 0.9941 | Success
Random excursions | 0.0003 | 0.8182 | Failure | 0.2307 | 0.9703 | Success
Random excursions variant | 0.0909 | 0.9091 | Success | 0.0780 | 0.9604 | Success
Serial | 0.0000 | 0.0000 | Failure | 0.1597 | 0.9763 | Success
Linear complexity | 0.3781 | 0.9862 | Success | 0.3979 | 0.9882 | Success
Table 1: Results of the NIST 800-22 statistical test suite for the raw and
post-processed data. The minimum values for each test are tabulated and
rounded down to 4 decimal places. To pass an individual statistical test, the
post-processed data needs to obtain 1) P-value $\geq 0.0001$; and 2)
proportion $\geq 0.9670$, except for random excursion variant test, which
requires proportion $\geq 0.9603$. Similarly, the raw data needs to obtain 1)
P-value $\geq 0.0001$; and 2) proportion $\geq 0.9697$, except for random
excursion variant test, which requires proportion $\geq 0.9000$.

We performed Toeplitz hashing on a personal computer with an Intel Xeon
E5-2697 CPU and 128 GB of random access memory (RAM). The total time taken for
the extraction was 72.285 seconds, which translates to a throughput speed of
2.3427 Mbits/s.

The output from Toeplitz hashing is saved in a text file, and NIST 800-22
statistical test suite [27] was employed to test the quality of both the raw
and extracted random numbers. To run the test, the extracted (raw) data is
split into 169 (217) blocks, each with length $10^{6}$ bits. The blocks are
passed to all 15 statistical tests, which perform hypothesis testing at the 1%
significance level, and returnOr 2 values, the P-value and proportion.

The proportion parameter is the proportion of sequences that pass the test at
the selected significance level. The range of acceptable proportions is
determined using the confidence interval. It is calculated as

$\widehat{p}\pm 3\sqrt{\frac{\widehat{p}(1-\widehat{p})}{k}},$

where $\widehat{p}=1-\alpha$ and $k$ is the number of sequences. When testing
the extracted output, we substitute $\alpha=0.01\text{ and }k=169$ to obtain a
confidence interval of 0.9670. The interpretation of this value is that if the
returned value of proportion for a specific test is below 0.9670, we conclude
that our extracted output fails that test and is therefore not uniformly
random. Similarly, when testing the raw output, we substitute
$\alpha=0.01\text{ and }k=217$ to obtain a confidence interval of 0.9697.

The P-value parameter for a specific test, denoted as $P\text{-value}_{T}$, is
the result of the Goodness-of-Fit Distributional Test on the P-values obtained
for that statistical test. The Goodness-of-Fit Distributional Test tests if
the distribution of P-values obtained follows a uniform distribution. If the
returned $P\text{-value}_{T}<0.0001$, then the P-values failed the uniformity
test, and thus, the sequence under test is considered to be non-uniformly
distributed as well.

The results of the NIST test for both our raw and extracted data are displayed
in Table 1. For tests that are executed several times (e.g. non-overlapping
template), the minimum values out of all the runs are tabulated, with the
values rounded down to 4 decimal places. From the results, it can be seen that
our raw data fails 10 out of 13 tests. The Runs test was not performed on the
raw data because it carries out the Frequency test as a prerequisite. As the
Frequency test returned a failure, the Runs test will be considered as failed
by default. Similarly, because the Serial test failed, the Approximate Entropy
test was skipped as well.

On the other hand, after post-processing, the P-values returned for all the
tests are greater than 0.0001, and all the proportion values returned are also
greater than 0.9670 as well. Hence, this shows that our extracted random
numbers pass all tests in the NIST statistical test suite, and that we have
managed to extract high quality random numbers from our initial weakly random
source.

##  VI Discussion

In summary, we implemented an MTJ-based TRNG, estimated the min-entropy of the
raw output bits, and performed suitable post-processing on the raw output to
obtain a set of provably-secure random numbers. To the best of our knowledge,
this is the first-ever implementation of provably-secure random number
generation using an MTJ device. The extracted random numbers pass all the
tests in the NIST STS. Our implementation also has minimal assumptions as
well, as we do not even assume that our raw data are independent or
identically distributed when performing entropy estimation.

Our work could have been improved by performing an in-depth characterisation
of the MTJ device to model it using mathematical statements. By doing so, we
will be able to obtain an accurate value of min-entropy, instead of having to
rely on min-entropy estimation tests. We could also consider the side-
information that is held by an adversary, Eve. Performing min-entropy
estimation on the raw data conditioned on Eve’s side-information would allow
us to obtain a final extracted output that is uniformly random, even from
Eve’s perspective.

## Acknowledgement

We thank Chao Wang for useful inputs and discussions. We acknowledge funding
support from the National Research Foundation of Singapore (NRF) Fellowship
grant (NRFF11-2019-0001) and NRF Quantum Engineering Programme 1.0 grant
(QEP-P2).

## References

  * Maxim [2017] Maxim, RandCrack – Python random module cracker / predictor (2017).
  * Matsumoto and Nishimura [1998] M. Matsumoto and T. Nishimura, ACM Transactions on Modeling and Computer Simulation 8, 3 (1998).
  * Petrie and Connelly [2000] C. Petrie and J. Connelly, IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 47, 615 (2000).
  * Brederlow  _et al._ [2006] R. Brederlow, R. Prakash, C. Paulus, and R. Thewes, in  _2006 IEEE International Solid State Circuits Conference - Digest of Technical Papers_ (2006) pp. 1666–1675, iSSN: 2376-8606.
  * Liu  _et al._ [2011] N. Liu, N. Pinckney, S. Hanson, D. Sylvester, and D. Blaauw, in  _2011 Symposium on VLSI Circuits - Digest of Technical Papers_ (2011) pp. 216–217, iSSN: 2158-5636.
  * Tang  _et al._ [2014] Q. Tang, B. Kim, Y. Lao, K. K. Parhi, and C. H. Kim, in  _Proceedings of the IEEE 2014 Custom Integrated Circuits Conference_ (2014) pp. 1–4, iSSN: 2152-3630.
  * Mathew  _et al._ [2016] S. K. Mathew, D. Johnston, S. Satpathy, V. Suresh, P. Newman, M. A. Anders, H. Kaul, A. Agarwal, S. K. Hsu, G. Chen, and R. K. Krishnamurthy, IEEE Journal of Solid-State Circuits 51, 1695 (2016), conference Name: IEEE Journal of Solid-State Circuits.
  * Kim  _et al._ [2017] M. Kim, U. Ha, K. J. Lee, Y. Lee, and H.-J. Yoo, IEEE Journal of Solid-State Circuits 52, 1953 (2017), conference Name: IEEE Journal of Solid-State Circuits.
  * Chandrasekaran  _et al._ [2020] S. T. Chandrasekaran, V. E. G. Karnam, and A. Sanyal, IEEE Solid-State Circuits Letters 3, 190 (2020).
  * Won Ho Choi  _et al._ [2014] Won Ho Choi, Yang Lv, Jongyeon Kim, A. Deshpande, Gyuseong Kang, Jian-Ping Wang, and C. H. Kim, in  _2014 IEEE International Electron Devices Meeting_ (2014) pp. 12.5.1–12.5.4.
  * Fu  _et al._ [2021] Z. Fu, Y. Tang, X. Zhao, K. Lu, Y. Dong, A. Shukla, Z. Zhu, and Y. Yang, Frontiers in Physics 9, 172 (2021).
  * Brataas  _et al._ [2012] A. Brataas, A. D. Kent, and H. Ohno, Nature materials 11, 372 (2012).
  * Yang  _et al._ [2018] K. Yang, Q. Dong, Z. Wang, Y.-C. Shih, Y.-D. Chih, J. Chang, D. Blaauw, and D. Svlvester, in  _2018 IEEE Symposium on VLSI Circuits_ (IEEE, Honolulu, HI, 2018) pp. 171–172.
  * Vatajelu and Di Natale [2019] E. I. Vatajelu and G. Di Natale, IEEE Transactions on Very Large Scale Integration (VLSI) Systems 27, 491 (2019).
  * Perach and kvatinsky [2019] B. Perach and s. kvatinsky, IEEE Transactions on Very Large Scale Integration (VLSI) Systems 27, 2473 (2019).
  * Slonczewski [1996] J. Slonczewski, Journal of Magnetism and Magnetic Materials 159, L1 (1996).
  * Berger [1996] L. Berger, Phys. Rev. B 54, 9353 (1996).
  * Seki  _et al._ [2011] T. Seki, A. Fukushima, H. Kubota, K. Yakushiji, S. Yuasa, and K. Ando, Applied Physics Letters 99, 112504 (2011), https://doi.org/10.1063/1.3637545 .
  * Fukushima  _et al._ [2014] A. Fukushima, T. Seki, K. Yakushiji, H. Kubota, H. Imamura, S. Yuasa, and K. Ando, Applied Physics Express 7, 083001 (2014).
  * Turan  _et al._ [2018] M. S. Turan, E. Barker, J. Kelsey, K. A. McKay, M. L. Baish, and M. Boyle,  _NIST 800-90B Recommendation for the entropy sources used for random bit generation_, Tech. Rep. NIST SP 800-90b (National Institute of Standards and Technology, 2018).
  * Nisan and Zuckerman [1996] N. Nisan and D. Zuckerman, Journal of Computer and System Sciences 52, 43 (1996).
  * Carter and Wegman [1979] J. Carter and M. N. Wegman, Journal of Computer and System Sciences 18, 143 (1979).
  * Impagliazzo  _et al._ [1989] R. Impagliazzo, L. A. Levin, and M. Luby, in  _Proceedings of the twenty-first annual ACM symposium on Theory of computing_ (Association for Computing Machinery, 1989) pp. 12–24.
  * Canetti [2001] R. Canetti, in  _Proceedings 42nd IEEE Symposium on Foundations of Computer Science_ (2001) pp. 136–145, iSSN: 1552-5244.
  * Pfitzmann and Waidner [2000] B. Pfitzmann and M. Waidner, in  _Proceedings of the 7th ACM conference on Computer and communications security - CCS ’00_ (ACM Press, Athens, Greece, 2000) pp. 245–254.
  * Krawczyk [1994] H. Krawczyk, Advances in Cryptology-CRYPTO’94 839, 129 (1994).
  * Rukhin  _et al._ [2010] A. Rukhin, J. Soto, J. Nechvatal, E. Barker, S. Leigh, M. Levenson, D. Banks, A. Heckert, and J. Dray,  _NIST 800-22 A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications_ , Tech. Rep. (National Institute of Standards and Technology, 2010).