2019 34th IEEE/ACM International Conference on Automated Software Engineering (ASE)

A Quantitative Analysis Framework for Recurrent
Neural Network
Xiaoning Du∗ , Xiaofei Xie∗ , Yi Li∗ , Lei Ma† , Yang Liu∗ , Jianjun Zhao†∗ Nanyang Technological University, Singapore† Kyushu University, Japan

Abstract—Recurrent neural network (RNN) has achieved great
success in processing sequential inputs for applications such as
automatic speech recognition, natural language processing andmachine translation. However, quality and reliability issues of
RNNs make them vulnerable to adversarial attacks and hinder
their deployment in real-world applications. In this paper, we
propose a quantitative analysis framework — DeepStellar—
to pave the way for effective quality and security analysis ofsoftware systems powered by RNNs. DeepStellar is generic tohandle various RNN architectures, including LSTM and GRU,
scalable to work on industrial-grade RNN models, and extensible
to develop customized analyzers and tools. We demonstrated
that, with DeepStellar, users are able to design efﬁcient test
generation tools, and develop effective adversarial sample detectors. We tested the developed applications on three real RNN
models, including speech recognition and image classiﬁcation.
DeepStellar outperforms existing approaches three hundred
times in generating defect-triggering tests and achieves 97%
accuracy in detecting adversarial attacks. A video demonstration
which shows the main features of DeepStellar is available at:https://sites.google.com/view/deepstellar/tool-demo.

I. M OTIVATIONOver the past decades, we have witnessed the emergenceand rapid development of deep learning (DL). DL has beensuccessfully deployed in many real-life applications, including
face recognition, automatic speech recognition (ASR) and autonomous driving, etc. However, due to the intrinsic vulnerability and the lack of rigorous veriﬁcation, DL systems suffer from
quality and security issues, such as the Alexa/Siri manipulationand the autonomous car accidents, which are introduced fromboth the development and deployment stages [1].
Due to the fundamentally different programming paradigm
and logic representation from traditional software, existing
quality assurance techniques can hardly be directly applied
to DL systems. Recently, signiﬁcant research efforts havebeen made on techniques speciﬁc to DL systems, including
testing [2], [3], [4], [5], [6], veriﬁcation [7], and adversarial
sample detection [8]. The existing work mainly focus on the
Feed-forward Neural Networks (FNNs), leaving the Recurrent
Neural Networks (RNNs) untouched. FNNs are with a feedforward design and take an input as a monolithic piece; eachlayer inside plays a ﬁxed role in the feature extraction process.
In contrast, RNNs consume a sequential input segment bysegment and work in an iterative manner, as illustrated inFig. 1a. In each iteration, the RNN processes an individual
element, evolves into a new state, records and forwards thestate information to the next iteration. This key feature enables

978-1-7281-2508-4/19/$31.00 ©2019 IEEE
DOI 10.1109/ASE.2019.00102

1062

RNNs to handle data rich in temporal information, such as
natural language texts, audios and videos. The fact that the rolesof layers are interchangeable, makes the quantitative analysisof RNNs much more difﬁcult, even to measure the behavioral
differences when processing two samples.
To bridge the gap, we propose a general-purpose quantitative
analysis framework, DeepStellar, which enables one to perform
effective security and quality analyses for RNN-based DL
systems. The core of DeepStellar is an abstraction of theunique hidden state space of RNNs, which models the internal
behaviors of RNNs as Discrete-Time Markov Chain (DTMC).
DeepStellar is generic to handle various RNNs architectures,
including LSTM [9] and GRU [10], and extensible to develop customized analyzers and testing tools for RNNs. To
demonstrate the effectiveness of DeepStellar, we developed an
efﬁcient test generation tool and effective adversarial sample
detectors for RNNs, based on DeepStellar. We apply bothtools on three real RNN models, including ASR and image
classiﬁcation, and observed promising results with hundreds oftimes more adversarial samples generated, and 97% accuracy inadversarial attack detection. DeepStellar facilitates developers,
users and researchers of RNN-based DL systems, allowing
them to have a better comprehension on the behaviors of
RNNs, deﬁne quantitative measures, and develop more usefultoolkit to make the systems more robust and secure.
II. T HE DeepStellar F RAMEWORK
Fig. 1b shows an overview of DeepStellar, which includes
three components: the abstract model construction module, andtwo applications – the adversarial sample detector (DeepStellarASD) and coverage-guided testing tool (DeepStellar-CGT).
The abstraction module takes the target RNN and (a part of)its training data as inputs, and constructs an abstract model.
DeepStellar provides APIs to access the state and transition
information from the abstract model, and the abstract trace
traversed by a sample. In this way, users are able to develop
customized analyzers and testing tools for RNNs by extending
DeepStellar, similar to DeepStellar-ASD and DeepStellar-CGT.
A. Abstract Model Construction
For an RNN, DeepStellar generates an abstract model (i.e.,
DTMC model) via three steps: 1) states and transitions proﬁling,2) state abstraction, and 3) transition abstraction.
Step 1: Proﬁling. DeepStellar uses inputs from the training
data to perform the proﬁling, as they can manifest the511

3URILOLQJRI6WDWHV
DQG7UDQVLWLRQV

676LP$EVWUDFW0RGHO

RNN

Output6WDWH$EVWUDFWLRQ

unrollOutput:y0… yi-1
Si-1

yi
Si

6DPSOH
WR7HVW

7HVWLQJ'DWD''HHS6WHOODU$6'

state vector

Input$GYHUVDULDO
6DPSOHV

7UDLQLQJ
'DWD

yi+1

…

7UDQVLWLRQ$EVWUDFWLRQ

Si+11'HWHFWRU'HHS6WHOODU&*7
7

0XWDWLRQ

6HHG4XHXH

S0

776LP

$GYHUVDULDO"

7UDFH6LPLODULW\0HWULFV

%6&RY

:6&RY

%7&RY

:7&RY

7HVWLQJ&ULWHULD*XLGDQFH

1HZ7HVW'DWD$GYHUVDULDO
6DPSOHV'HHS6WHOODUU

Input:x0… xi-1xi

xi+1

6HHG'DWD…

(b) Overview of DeepStellar.

(a) A Simple RNN.

Fig. 1: Architecture of RNN and Overview of DeepStellar.
characteristics of a trained RNN model. Via executing the RNN
on an input, a trace consisting of state vectors is generated.
In this way, from the training data, we obtain a set of traces
recording the concrete states visited and the concrete transitions
taken during the training stage. Based on the concrete states andtransitions, we then perform the state and transition abstraction.

because visible differences exists between these two pictures.
With DeepStellar, we can capture ﬁner-grained behaviors of
RNNs and even to measure the differences between samples
with minor perturbations. Speciﬁcally, we designed two trace
similarity metrics, and developed an algorithm to detect
adversarial samples based on them.

Step 2: State Abstraction. We ﬁrst group all the concrete
state vectors and apply Principle Component Analysis (PCA)
to identify the ﬁrst k principle components which distinguishthe vectors to the most extend. Then, we project the concrete
state vectors onto the k-dimensional component basis. This
is to reduce the dimension of the state space and improve
computation efﬁciency, since concrete state vectors may comewith very high dimension. Next, we perform an interval
abstraction by dividing each axis into m equal-length intervals,
and the k-dimensional space are split into mk regular grids [11].
Finally, we map concrete states falling into the same grid to thesame abstract state. Note that the precision of state abstraction
is conﬁgurable by the parameters (k, m).

Trace Similarity Metrics. The two similarity metrics (referto [12] for the detailed deﬁnitions) are from both the state andtransition levels, i.e., state-based trace similarity (SBTS IM) andtransition-based trace similarity (TBTS IM). They are derived
to compare the trace similarity between samples from the
Jaccard index of their abstract states or transitions covered.
Given two samples, we can leverage DeepStellar to get theset of states or transitions covered by each, and calculate theJaccard index between the two sets.

Step 3: Transition Abstraction. We abstract the concrete
transitions based on the state abstraction. An abstract transition
represents a set of concrete transitions which share thesame source and destination abstract states. For each abstract
transition t, we calculate its transition probabilities by taking
the number of concrete transitions, that mapped to t, over thenumber of all outgoing concrete transitions that share the same
source abstract state as t.
B. Applications
Based on the abstract model, we developed two applicationsfor 1) adversarial sample detection (DeepStellar-ASD), and 2)
coverage-guided testing (DeepStellar-CGT) of RNNs. Here,
we give a brief description about their designs and usage.
1) Adversarial Sample Detection: Adversarial samples areable to fool RNNs with human-imperceptible perturbations. We
speculate that there exist some abnormal behaviors during theprocess of predicting over the adversarial samples, comparedwith benign samples. For example, when a perturbed panda
picture is recognized as a gorilla, the behavioral trace of
RNN is supposed to be different from that of a real gorilla,

Usage. DeepStellar-ASD takes a set of adversarial samples
and a (partial) set of testing data (highlighted with step 2 inFig. 1b) as inputs, and outputs a detector which checks whether
a given sample (step 3 ) is adversarial.
To check whether a given sample (step 3 ) is adversarial,
DeepStellar-ASD ﬁrst generates reference samples which havethe same the prediction output as the target. The trace similarity
between the original sample and its reference samples are used
as an indicator to differentiate between benign and adversarial
samples. Basically, the similarity between a benign sample
and its references is larger than that of an adversarial sample.
For the panda as gorilla example, its reference samples are
all gorilla, thus the similarity would be much larger than thatbetween gorilla pictures. For the image classiﬁcation task, we
get 50 reference samples from the training data based on thelabel of the original sample. For the ASR models, we use offthe-shelf text-to-speech engines to generate a standard audio
from the transcript of the original sample.
2) Coverage-Guided Testing: With the proﬁling of samples
from training data, DeepStellar is able to capture the major
behavioral space and transitions in normal cases. The objectiveof testing is to systematically generate test cases, which may
also explore regions outside the major behavioral space. We
derive a set of coverage criteria to facilitate the guided testing1063

TABLE I: Studied subject model information.
Kernel RNN

Subject Model
Type

State vec. shape

DeepSpeech 0.1.1 Bi-LSTM (None, 4096)
MNIST-LSTM
LSTM(None, 128)
MNIST-GRU
GRU(None, 128)

# Traina.
Param.
122x106
81,674
61,578TABLE II: AUROC results (%) of trace similarity based
adversarial detection by conﬁgurations.

Acc. (%)
Train.

Conﬁg. DeepSpeech-0.1.1

Test.

99.69 98.66
99.70 98.61(k, m) STS IM TTS IM(2, 40)(2, 80)(3, 5)(3, 10)(3, 20)(3, 40)(3, 80)Coverage Criteria. For the coverage criteria, basic state
coverage (BSC OV), weighted state coverage (WSC OV), basic
transition coverage (BTC OV) and weighted transition coverage(WTC OV) are designed to quantify the portion (or weighted
portion considering the visiting probabilities) of abstractstates/transitions visited by any test dataset. They indicate
how adequately the internal states/transitions are exercised.

III. I MPLEMENTATION AND F EATURES
We have implemented DeepStellar in Python based on Keras2.2.4 and TensorFlow-1.11. Its command line interface provides
three key features: (1) RNN abstract model construction, (2)RNN adversary example detection, and (3) RNN coverageguided testing. These features can help end users to performthe quality and security analysis of RNN directly. Furthermore,
DeepStellar provides a comprehensive set of APIs to assist
further application development for RNN analysis: (1) APIs for
retrieving the detailed information of the abstract model, and(2) APIs to visualize the runtime traces of RNN predictions.
To validate the practical value of DeepStellar, we applied
DeepStellar-ASD on detecting adversarial samples generated
by state-of-the-art attack techniques. We further applied DeepStellar-CGT on image classiﬁcation RNN models trainedwith MNIST dataset, and generated a number of adversarial
samples effectively. The results demonstrate that DeepStellar
is useful on revealing and evaluating the defects of RNN-based
DL systems. With these engineering efforts and experimental
results, we believe that DeepStellar is scalable and effective
in attacking and defending real-world RNNs.

FSGM

BIM

DeepFool

STS IM TTS IM STS IM TTS IM STS IM TTS IM

of RNNs, with the aim to improve the testing dataset adequacy
and uncover more defects.

Usage. DeepStellar-CGT begins with a set of initial seeds(step 4 in Fig. 1b), and returns a set of augmented test data
and a group of adversarial samples discovered. Firstly, theinitial seed data are put into a seed queue, then DeepStellarCGT iterates to increase a chosen coverage criteria of the seed
queue with sample mutation and selection. In each iteration,
we select a seed from the queue and generate a series ofmutants. Mutation strategies to augment the test data aredesigned for image, natural language, and audio, respectively.
The mutation follows metamorphic relations such that the
perturbations applied are minor and would not change the truthlabel. For the newly generated samples, if they are adversarial,
we keep them in the adversarial sample group. Otherwise,
we check their contribution to the speciﬁc coverage criteria,
and retain the test cases that cover new states or transitions.
DeepStellar-CGT iteratively continues the above steps until
the given time budget exhausts.

MNIST-LSTM

81.00
70.25
69.41
89.26
85.25
50.49
50.00

50.00
50.00
85.40
85.19
50.00
50.00
50.00

79.95
90.54
86.95
90.05
89.4
90.56
96.63

88.01
96.55
85.31
89.74
92.62
93.79
93.64

77.9
82.38
84.71
86.18
84.63
85.97
92.97

80.77
92.12
83.25
85.28
84.72
86.62
89.75

76.82
84.43
82.42
85.23
83.53
84.05
93.44

81.86
92.46
80.15
83.78
85.46
87.47
90.43

IV. E VALUATION
We demonstrate the usefulness of the DeepStellar applications, on three RNNs from domains of speech recognition andimage classiﬁcation. Details of the subject models can be foundin Table I. The ASR model used is Mozilla’s implementation of
DeepSpeech 0.1.1, which is of industrial-level performance. For
image classiﬁcation, we trained two RNNs with the LSTM andGRU architectures over the MNIST dataset, respectively. Bothmodels achieve over 98% test accuracy. They covered different
RNN architectures including LSTM, bidirectional LSTM and
GRU. The largest model, DeepSpeech 0.1.1, contains over
one hundred millions of trainable parameters, and the statevectors are in 4,096 dimensions. In addition, we evaluatedthe usefulness of the proposed quantitative measures on
two application tasks, namely detecting adversarial examples
and coverage guided testing for RNNs. More details on theexperiment setup and results can be found in [12].
(1) Adversarial Sample Detection. Adversarial samples foreach model are generated with state-of-the-art attack methods.
We use the C&W audio attack [13] to generate adversarial audios for DeepSpeech 0.1.1, and use FGSM, BIM and DeepFool
to generate adversarial samples for image classiﬁcation models.
For each RNN, we generate 13 abstract models under multigrained (k, m) abstraction conﬁgurations. Finally, for eachattack method, we generated 5,000 adversarial samples andrandomly select the same number of benign samples. With thesesamples, we separately sampled the SBTS IM and TBTS IM
measures, and trained a linear regression classiﬁer for detecting
adversarial examples. We show several AUROC results inTable II for two RNNs – DeepSpeech 0.1.1 and MNIST-LSTM,
and the best detection accuracy hits 89% and 97%. The results
demonstrate that models with different abstractions can achievedifferent detection accuracy. DeepStellar is useful on detecting
adversarial examples by selecting suitable abstract models.
(2) Coverage-guided Testing. We evaluated the usefulnessof DeepStellar-CGT on coverage increase and the number ofadversarial examples with the BSCov guidance and BTCovguidance. We selected the abstract model with the conﬁguration(k=3, m=10). Results for the MNIST models are shown in
Table III. For each coverage guidance, we analyze the coverageincrease on all testing criteria (ı.e., the ﬁrst column). Column“Seed” shows the initial coverage from the initial seeds. The
coverage results from state- and transition- coverage guidance1064

applications of DeepStellar with a test generation tool andadversarial sample detector. For future work, we intend toaugment the abstraction with transition labels, i.e., the input
triggering a transition, and abstraction techniques can handle
inputs from continuous space. We are also interested ininvestigating what and how critical properties can be veriﬁed
over the abstract model to unveil deeply buried defects in RNNs.

TABLE III: Results of coverage and unique adversarial samples
by different testing strategies.
Criteria (%)

MNIST-LSTM

MNIST-GRU/Adv (#)

Seed S-Guid. T-Guid. Ran. DeepT. Seed S-Guid. T-Guid.

BSCov
WSCov
BTCov
WTCov

54.59
96.44
15.13
77.80

#Unique Adv.

97.78
99.99
53.43
94.81

97.78 86.23
99.99 99.66
96.43 73.88
99.90 98.02- 87,596 41,614 2,219

65.35 63.20
98.04 97.03
26.23 14.42
85.12 63.40
300

95.87
99.98
42.80
88.78

96.04
99.98
93.89
99.69

Ran. DeepT.
88.78
99.80
71.82
96.95

68.98
98.05
21.32
72.34

- 69,777 35,228 19,738

244

are shown under Column “S-Guid.” and “T-Guid.”, respectively.
For comparison, we included a random testing without coverage
guidance (Column “Ran.”) and an existing neuron coverageguided testing tool for RNN based on unrolling [3] (Column“DeepT.”). We can see that DeepStellar-CGT outperforms all thebaseline approaches on both the coverage criteria increase andthe generation of adversarial samples. Speciﬁcally, DeepStellarCGT discovers 3 to 40 times more adversarial samples thanrandom testing, and around 300 times more than DeepTest.

Acknowledgment. This research was supported (in part) by
Singapore National Research Foundation, under its National Cybersecurity R&D Program (Award No. NRF2018NCR-NCR0050001) and National Satellite of Excellence in Trustworthy
Software System (Award No. NRF2018NCR-NSOE003-0001),
and NTU research grant NGF-2019-06-024, and JSPS KAKENHI Grant 19K24348, 19H04086, and Qdaijump Research
Program NO.01277. Also, we would like to thank Nvidia forthe hardware support of GPU cards and servers, and Mr. Yun
Tang for the great help during preparation of the demo.

V. R ELATED W ORK
Abstraction of RNN. There exist some pioneer studies on the
abstraction techniques for RNNs, but they mostly used Finite
State Automaton (FSA) to capture RNNs’ internal dynamics,
which lacks the transition probability distributions as in DTMC.
In the literature, the existing studies are mostly concernedwith the strategy for the internal state space partition, which
is one of the most important techniques in the abstraction.
Proposed partitioning strategies include equal division of eachdimension for regular grids [11], unsupervised classiﬁcation
algorithms such as k-means and its variants [14], [15] anddynamic partition schemes with kernel algorithms [7]. However,they all suffer from the scalability problem when applied to realworld RNNs where the internal state space can be extremely
large and in high dimension. Instead, DeepStellar employs
PCA for a much cheaper abstraction.
RNN Adversarial Example Detection. Adversarial example
detection for RNNs is still at an early stage. Techniques [8],[16], [17] specially designed for feedforward nerual networks
cannot be applied to RNNs. The softmax probability based
approach [16] could possibly be used to detect RNN adversarial
examples for classiﬁcation problem only. As far as we know,
DeepStellar-ASD is the ﬁrst tool speciﬁcally designed to detect
adversarial samples for RNNs with sequential output.
Deep Learning Testing. Recently, DNN testing has been
widely studied including the study on testing criteria [2], [4]and testing tool [2], [3], [5], [6], [18]. However, most of them
mainly focus on feed forward neuron networks. DeepTest [3]can be used on RNNs by unrolling. However, it unrolls the
RNN with ﬁxed iterations and is not scalable. TensorFuzz [18]can be used on RNN as it only considers the output of thelogits layer. However, it lacks internal analysis of the RNNs.
VI. C ONCLUSION AND F UTURE W ORK
DeepStellar provides a fundamental infrastructure supporting
versatile analyses of RNNs. We demonstrate two typical1065

R EFERENCES[1] Q. Guo, S. Chen, X. Xie, L. Ma, Q. Hu, H. Liu, Y. Liu, J. Zhao, and X. Li,“An empirical study towards characterizing deep learning development
and deployment across different frameworks and platforms,” in ASE,
2019.
[2] K. Pei, Y. Cao, J. Yang, and S. Jana, “Deepxplore: Automated whitebox
testing of deep learning systems,” in SOSP, 2017, pp. 1–18.
[3] Y. Tian, K. Pei, S. Jana, and B. Ray, “Deeptest: Automated testingof deep-neural-network-driven autonomous cars,” in ICSE, 2018, pp.
303–314.
[4] L. Ma, F. Juefei-Xu, J. Sun, C. Chen, T. Su, F. Zhang, M. Xue, B. Li,
L. Li, Y. Liu et al., “Deepgauge: Multi-granularity testing criteria fordeep learning systems,” 2018, pp. 120–131.
[5] X. Xie, L. Ma, F. Juefei-Xu, M. Xue, H. Chen, Y. Liu, J. Zhao,
B. Li, J. Yin, and S. See, “Deephunter: A coverage-guided fuzz testing
framework for deep neural networks,” in ISSTA, 2019, pp. 146–157.
[6] X. Xie, L. Ma, H. Wang, Y. Li, Y. Liu, and X. Li, “Diffchaser: Detecting
disagreements for deep neural networks,” in IJCAI, 2019, pp. 5772–5778.
[7] G. Weiss, Y. Goldberg, and E. Yahav, “Extracting automata from recurrent
neural networks using queries and counterexamples,” in ICML, 2018, pp.
5244–5253.
[8] J. Wang, G. Dong, J. Sun, X. Wang, and P. Zhang, “Adversarial sample
detection for deep neural network through model mutation testing,” in
ICSE, 2019, pp. 1245–1256.
[9] S. Hochreiter and J. Schmidhuber, “Long Short-Term Memory,” Neuralcomputation, vol. 9, no. 8, pp. 1735–1780, 1997.
[10] K. Cho, B. Van Merriënboer, D. Bahdanau, and Y. Bengio, “On theproperties of neural machine translation: Encoder-decoder approaches,”arXiv preprint arXiv:1409.1259, 2014.
[11] C. W. Omlin and C. L. Giles, “Constructing Deterministic Finite-State
Automata in Recurrent Neural Networks,” JACM, vol. 43, no. 6, pp.
937–972, 1996.
[12] X. Du, X. Xie, Y. Li, L. Ma, Y. Liu, and J. Zhao, “Deepstellar: Modelbased quantitative analysis of stateful deep learning systems,” in FSE,
2019, pp. 477–487.
[13] N. Carlini and D. Wagner, “Audio Adversarial Examples: Targeted
Attacks on Speech-to-Text,” in SPW, 2018, pp. 1–7.
[14] A. L. Cechin, D. R. P. Simon, and K. Stertz, “State Automata Extraction
from Recurrent Neural Nets Using k-Means and Fuzzy Clustering,” in
SCCC, 2003, pp. 73–78.
[15] B.-J. Hou and Z.-H. Zhou, “Learning with Interpretable Structure from
RNN,” oct 2018. [Online]. Available: http://arxiv.org/abs/1810.10708[16] D. Hendrycks and K. Gimpel, “A baseline for detecting misclassiﬁed
and out-of-distribution examples in neural networks,” arXiv preprint
arXiv:1610.02136, 2016.
[17] W. Xu, D. Evans, and Y. Qi, “Feature squeezing: Detecting adversarial
examples in deep neural networks,” arXiv preprint arXiv:1704.01155,
2017.
[18] A. Odena and I. Goodfellow, “Tensorfuzz: Debugging neural networks
with coverage-guided fuzzing,” in ICML, 2019, pp. 4901–4911.