#  EVIL: Exploiting Software via Natural Language

Pietro Liguori1, Erfan Al-Hossami2, Vittorio Orbinato1,
Roberto Natella1, Samira Shaikh2, Domenico Cotroneo1, and Bojan Cukic2
1University of Naples Federico II, Naples, Italy
{pietro.liguori, vittorio.orbinato, roberto.natella<EMAIL_ADDRESS>2University of North Carolina at Charlotte, Charlotte, NC
{ealhossa, samirashaikh<EMAIL_ADDRESS>
###### Abstract

Writing exploits for security assessment is a challenging task. The writer
needs to master programming and obfuscation techniques to develop a successful
exploit. To make the task easier, we propose an approach (_EVIL_) to
automatically generate exploits in assembly/Python language from descriptions
in natural language. The approach leverages Neural Machine Translation (NMT)
techniques and a dataset that we developed for this work. We present an
extensive experimental study to evaluate the feasibility of _EVIL_ , using
both automatic and manual analysis, and both at generating individual
statements and entire exploits. The generated code achieved high accuracy in
terms of syntactic and semantic correctness.

###### Index Terms:

Automatic Exploit Generation, Neural Machine Translation, Software Exploits,
Shellcode, Encoder, Decoder

##  I Introduction

In the context of software security, a solid understanding of offensive
techniques is increasingly important [1, 2]. Well-intentioned actors, such as
penetration testers, ethical hackers, researchers, and computer security teams
are engaged in developing exploits, referred to as proof-of-concept (POC), to
reveal security weaknesses within the software. Offensive security helps us
understand how attackers take advantage of vulnerabilities and motivates
vendors and users to patch them to prevent attacks [3]. Among software
exploits, code-injection attacks are the trickiest. They allow the attacker to
inject and execute arbitrary code on the victim system. Since the injected
code frequently launches a command shell, the hacking community refers to the
payload portion of a code-injection attack as a shellcode [4].

Writing code injection exploits is a challenging task since it requires
significant technical skills. Shellcodes are typically written in assembly
language, affording the attacker full control of the memory layout and CPU
registers to attack low-level mechanisms (e.g., heap metadata and stack return
addresses) not otherwise accessible through high-level programming languages.
Another challenge for shellcodes is modern antivirus (AV) and intrusion
detection systems (IDS), which actively look for malicious payloads to block
attacks. To elude detection, shellcode writers weaponize their shellcode by
implementing an encoding/decoding strategy. In other words, writers have to
develop _encoders_ (typically, using Python) to obfuscate the original
shellcode without altering its functionality, and _decoders_ (typically in
assembly language, as the shellcode) to revert to the payload once it is
loaded (and then executed) on the victim system.

In this work, we propose an approach, _EVIL_ (Exploiting software VIa natural
Language), for exploit writing based on natural language processing. The
approach aims to support both beginners and experienced researchers, by making
exploits easier to create and flattening the learning curve. In _EVIL_ , a
machine learning system learns about exploit writing from a dataset,
containing both real exploits and their description in the English language.
Then, the writer describes the exploit using the English language and lets the
machine learning system translate the description into assembly and Python
code. _EVIL_ leverages recent advances in _neural machine translation_ (NMT)
to automatically generate code from natural language descriptions using
recurrent neural networks. NMT has emerged as a promising machine translation
approach, and it is widely recognized as the state-of-the-art method for the
translation of different languages [5, 6]. NMT has been adopted in many
different areas, to generate programs in the Python language [7, 8], OS
commands for the UNIX Bash shell [9, 10], commit messages for version control
[11, 12], code completion [13], test cases from security requirements [14],
and more. However, NMT techniques have not heretofore been applied in the
field of software security in the manner described in our approach.

Our work provides three key contributions:

  * •

We release a substantive dataset111The dataset and the code to reproduce the
experiments are publicly available here: https://github.com/dessertlab/EVIL
containing exploits collected from shellcode databases and their descriptions
in the English language. The dataset includes both assembly code (i.e,
shellcodes and decoders) and Python code (i.e., encoders). Such data is
valuable to support research in machine translation for security-oriented
applications since the techniques are data-driven.

  * •

We propose a new approach that applies NMT techniques to automatically
generate exploits, including both Python code for encoding the payload, and
assembly code for decoding the payload and for the actual shellcode, based on
their description in the English language.

  * •

We perform an extensive experimental study, to evaluate the feasibility of the
proposed approach at generating real exploits. To this aim, we propose new
metrics that go beyond evaluating the translation of single lines of code [8,
15, 16, 17], but encompass entire exploits as a whole. The generated code
achieved high accuracy in terms of syntactic and semantic correctness.

In the following, Section II introduces background concepts; Section III
presents the proposed approach; Section IV describes the dataset; Section V
experimentally evaluate the approach; Section VI describes the approach
further through selected examples; Section VII discusses related work; Section
VIII discusses the ethical considerations; Section IX concludes the paper.

##  II Background

Statistics from the Common Vulnerabilities and Exposures (CVE) database show
that code-injection vulnerabilities increased dramatically during recent years
[18, 19]. Code-injection attacks deliver and run arbitrary code on victims’
machines, enabling unauthorized access and control of system resources,
applications, and data [20]. Moreover, code-injection attacks have become more
and more sophisticated, including techniques such as return-oriented
programming, heap spraying, and format string attacks.

A shellcode is a list of machine code instructions, to be loaded in a
vulnerable application at runtime. The classic way to develop shellcodes is to
write them using the assembly language, and by using an assembler to turn them
into _opcodes_ (operation codes, i.e., a machine language instruction in
binary format, to be decoded and executed by the CPU) [21, 22]. Listing 1
shows an example of shellcode222Shellcode collected from https://www.exploit-
db.com/shellcodes/47890 in assembly for the 32-bit Intel Architecture, which
runs the /bin/sh command to spawn a shell on the Linux OS. Note that the
shellcode strictly depends on the OS and the CPU architecture, thus it must be
tailored for the target system. Listing 1 also shows the shellcode as binary
opcodes (lines 17-18), where each \x followed by two hex digits represents one
byte of the payload [23]. Shellcodes typically range between few bytes to
hundreds of bytes. Other objectives of shellcodes include killing or restart
other processes, causing a denial-of-service (e.g., a fork bomb), leaking
secret data, etc.

⬇

1global _start

2section .text

3_start:

4 xor eax, eax

5 push eax

6 push 0x68732f2f

7 push 0x6e69622f

8 mov ebx, esp

9 push eax

10 mov edx, esp

11 push ebx

12 mov ecx, esp

13 mov al, 11

14 int 0x80

15

16\------------------ Binary opcodes \------------------

17"\x31\xc0\x50\x68\x2f\x2f\x73\x68\x68\x2f\x62\x69\

18x6e\x89\xe3\x50\x89\xe2\x53\x89\xe1\xb0\x0b\xcd\x80"

Listing 1: Example of shellcode to spawn a shell on Linux x32 systems.

The plain shellcodes contain explicit information of the malicious action the
attacker aims to take. For example, the shellcode in Listing 1 contains the
values 68 73 2f 2f and 6e 69 62 2f, which are the hexadecimal representation
of the strings //sh and /bin in reverse order (since the target CPU is little-
endian). Therefore, it is easy for AV and IDS software to block the execution
of this shellcode. To overcome security protections, exploit writers adopt
encoding techniques, which convert the original shellcode into a new,
functionally equivalent one, but more difficult to block [24, 25]. Encoders
are programs written in a high-level language, most often in Python (e.g.,
over the $80\%$ of the encoders on the popular Exploit Database [26] are
developed in Python language), and apply mathematical operations (as in
symmetric key cryptography) on the binary opcodes to generate new ones, and
which append additional opcodes for the decoder. Afterward, when this attack
payload is injected and executed by the victim system, it decodes itself to
obtain the original shellcode. Since the decoder is part of the attack
payload, it is developed using the assembly language.

Encoders and decoders are not just used to obfuscate the original payload from
AV and IDS. Encoding schemes are used also to eliminate “bad bytes” from the
payload. For example, since a null byte is considered as a terminator
character for strings, all the bytes of the payload following the null bytes
are not processed. Accordingly, the shellcodes must be null-free or zero-free,
i.e., they can not contain any null bytes. Moreover, most vulnerabilities
impose restrictions on the quantity of data that can be injected. Therefore,
another use of encoders is to optimize the shellcode to decrease its size.

As security attacks and defenses evolve with technology, security researchers
have been developing new encoding techniques. Among recent studies, Geczi et
al. [27] described a technique that converts x86 assembly code, such that the
resulting object code only contains printable characters. Similarly, Patel et
al. [28] developed a new encoding scheme to produce printable shellcodes but
in a more compact and reduced size. The penetration testing tool Metasploit
[29] also provides a method, named sub encoder, to convert any sequence of
binary data into ASCII characters that, when interpreted by an Intel CPU, will
decode the original sequence and execute it.

##  III Proposed Methodology

Figure 1: Architecture diagram of _EVIL_ demonstrating a six-step process: 1)
Pre-Processing of the samples in the training data, 2) Training of the neural
machine translation system with the processed training data, 3) User stating
the operation in the English language (i.e., the intent), 4) Pre-processing of
the intent, 5) NMT models generating the code snippet from the processed
intent, and lastly, 6) _EVIL_ output after post-processing applied to the
generated code snippet.

The _EVIL_ approach leverages neural machine translation (NMT) to
automatically generate exploits. A neural machine translation system is a
neural network that maximizes the conditional probability $p(a|e)$ of
translating a source sentence $e=<e_{1},...,e_{T_{e}}>$, with length
$|e|=T_{e}$, into a target sentence $a=<a_{1},...,a_{T_{a}}>$, with length
$|a|=T_{a}$. Following prior work (e.g., [30]), we build a neural network that
directly models the conditional probability $p(a|e)$ of translating an
_intent_ , in natural language into a _code snippet_ in Python or assembly
language. As a simple example, consider the sequence of English tokens [‘add’,
‘the’, ‘value’, ‘4’, ‘to’, ‘the’, ‘eax’, ‘register’] as $e$, and the sequence
of assembly tokens [‘add’, ‘eax’, ‘,’, ‘4’] as $a$, with $|e|=8$ and $|a|=4$.
The general architecture of an NMT system consists of an encoder, which
computes a representation $s$ for each source token, and a decoder, which
generates tokens in the target language333In this section, we use the terms
_encoder_ and _decoder_ to refer to deep learning architectures. In other
sections, the terms refer to parts of an exploit..

To support automatic code generation, neural machine translation is usually
accompanied by data processing steps [31, 32, 33]. These phases strongly
depend on the specific source and target languages to translate (in our case,
exploit code from the English language). The _EVIL_ approach applies steps of
processing both before the NMT task (pre-processing), to train the NMT model
and prepare the input data, and after the NMT task (post-processing), to
improve the quality and the readability of the code in output. Figure 1 shows
the architecture of our approach, along with an example of inputs and outputs
at each step, further discussed in the following.

###  III-A Pre-Processing

Pre-processing starts with stopwords filtering, i.e., by removing a set of
custom compiled words (e.g., the, each, onto), in order to include only
relevant data for machine translation. This phase splits the input sequence of
natural language tokens $e_{1},...,e_{T_{e}}$ and code $a_{1},...,a_{T_{a}}$
in a process called tokenization. The tokenizer converts the input strings
into their byte representations, and learns to break down a word into subword
tokens (e.g., lower becomes [low,er]. We tokenize intents using the nltk word
tokenizer [34] and snippets using the Python tokenize package [35]. We then
use regular expressions to identify hexadecimal values (e.g., 0xbb), strings
that fall between quotation marks, squared brackets, variable name notations
(e.g., variableName, variable_name), follow underscore notation (e.g.,
next_cycle), function names, mathematical expressions, and byte arrays (e.g.,
\xe3 \xa1). We also use WordNet [36] to recognize alphabet strings that do not
belong to the English language.

Consider the natural language intent shown in Figure 1 (step 3), which
contains the phrase _jump to next_cycle_. One task for code generation systems
is to prevent non-English tokens (e.g., next_cycle) from getting transformed
during the learning process. This process is known as Standardization. Extant
code generation systems address this problem with _copying_ mechanisms in
neural network architectures [37], which are inspired by human memorization.
To perform standardization, _EVIL_ provides a novel Intent Parser tailored for
working with exploit software. The goal of the Intent Parser is to take input
in natural language (i.e. intents) and to provide as output a dictionary of
standardizable tokens, such as specific values, label names, and parameters.

All tokens selected by the Intent Parser are passed to the Standardizer. The
standardization process simply replaces the selected token in both the intent
and snippet with var#, with # denoting a number from $0$ to $|l|$, and $|l|$
is the number of tokens to standardize. In the step 4 in Figure 1, the intent
parser identifies dl, 0xbb, and next_cycle as standardizable tokens and
standardizes them to var0, var1, and var2 respectively (based on order of
appearance in the intent). To prevent the standardization of unimportant
tokens, we compile a dictionary of $45$ assembly keywords (e.g., register,
address, byte), and $38$ Python keywords (e.g., for, class, import) as non-
standardizable tokens. After the standardization process, both the original
token and its standardized counterpart (var#) are stored in a dictionary to be
used during post-processing.

Lastly, we create Embeddings, i.e., a mapping of each token (in both the
intent and code snippet sequences) into a numerical id representation in order
to capture their semantic and syntactic information, where the semantic
information correlates with the meaning of the tokens, while the syntactic one
refers to their structural roles [38].

###  III-B NMT Models

To perform neural machine translation (step 5), we consider two standard
architectures: Seq2Seq, and CodeBERT.

Seq2Seq. Seq2Seq is a common model used in a variety of neural machine
translation tasks. Similar to the encoder-decoder architecture with attention
mechanism [39], we use a bi-directional LSTM as the encoder, to transform an
embedded intent sequence $e=|e_{1},...,e_{T_{e}}|$ into a vector $c$ of hidden
states with equal length. Within the bidirectional LSTM encoder, each hidden
state $h_{t}$ corresponds to an embedded token $e_{t}$. The encoder LSTM is
bidirectional, which means it reads the source sequence $e$ ordered from left
to right (from $e_{1}$ to $e_{T_{e}}$) and from right to left (from
$e_{T_{e}}$ to $e_{1}$). To combine both directions, each hidden state for the
bidirectional LSTM encoder is computed by concatenating the hidden states of
the forward and backward orders at token $t$ as follows:

$\begin{matrix}\textbf{h}_{t}=[f(e_{t},\textbf{h}_{t-1});f(e_{t},\textbf{h}_{t+1})];\end{matrix}$
(1)

where $h_{t}$ denotes a hidden state at time step $t$, $e_{t}$ denotes an
embedded intent token $t$, and $f$ denotes an LSTM non-linear function. Next,
the model generates a context vector $c_{t}$ for each of the embedded inputs.
We use the Bahdanau-style attention mechanism [39], which uses soft attention
by representing $\textbf{c}_{t}$ as the weighted sum of the encoder hidden
states, as $\mathbf{c}_{t}=\sum_{i=1}^{{T_{e}}}\alpha_{t,i}\>\textbf{h}_{i}$,
where the scores $\alpha_{t,i}$ are parametrized by a feed-forward multi-layer
perceptron neural network. Since the encoder uses a bidirectional LSTM, each
hidden state $\textbf{h}_{i}$ is aware of the context on both ends.

The decoder generates one target token at a time by decomposing the
conditional probability $p(a|e)$ into $\prod_{t=1}^{T_{a}}p(a_{t}|a_{<t},s)$,
where $a_{t}$ is an individual output token. The target token are generated by
combining the LSTM decoder state $s_{t-1}$, the previously-generated token
$a_{t-1}$, and the context vector $c_{t}$ as follows:

$\begin{matrix}\textbf{s}_{t}=f(a_{t-1},\textbf{s}_{t-1},\textbf{c})\\\ \\\
\>\>\>\>\>\>p(a_{t}|a_{<t},e)=g(a_{t-1},\textbf{s}_{t},\textbf{c})\end{matrix}$
(2)

where $g$ is a non-linear function, and $a_{<t}$ denotes previous predicted
tokens $\\{a_{1},...,a_{t-1}\\}$.

CodeBERT. CodeBERT [40] is a large multi-layer bidirectional Transformer
architecture [41]. Like Seq2Seq, the Transformer architecture is made up of
encoders and decoders. CodeBERT has 12 stacked encoders and 6 stacked
decoders. Compared to Seq2Seq, the Transformer architecture introduces
mechanisms to address key issues in machine translation: (i) the translation
of a word depends on its position within the sentence; (ii) in the target
language, the order of the words (e.g., adjectives before a noun) can be
different from the order of words in the source language (e.g., adjectives
after a noun); (iii) several words in the same sentence can be correlated
(e.g., pronouns). These problems are especially important when dealing with
long sentences.

The Transformer architecture first refines the input embedding of each token,
by combining it with a _positional encoding_ vector. The architecture has a
different positional encoding vector for each position of the sentence, in
order to enrich the input embedding with positional information. Then, the
transformed input embeddings sequentially go through the stacked encoder
layers, which all apply a _self-attention_ process. The self-attention further
refines an input embedding, by combining it with the other input embeddings
for the sentence in a weighted way, in order to account for correlations among
the words (e.g., to get information for a pronoun from the noun it refers to,
the input embedding of the noun is given a large weight). The weights are
given by:

$Attention(Q,K,V)=softmax(\frac{QK^{T}}{\sqrt{d_{k}}})V$ (3)

where the vectors $Q$ (query), $K$ (key), and $V$ (value) are learned during
training. To further improve this mechanism, the Transformer architecture uses
_multi-headed attention_ , where input embeddings are first multiplied with
three learned weight matrices $W_{i}^{Q}$, $W_{i}^{K}$, and $W_{i}^{V}$ (where
$i$ is a “head”), then combined with vectors $Q$, $K$, and $V$. Finally, the
results from all heads are concatenated and multiplied with an additional
weights matrix $W^{O}$. Multi-headed attention enables the neural network to
correlate different parts of the sequence in different ways (e.g., short-term
vs long-term correlations).

$MultiHead(Q,K,V)=Concat(head_{1},...,head_{h})W^{O}$ (4)

Different from Seq2Seq, CodeBERT also comes with a _pre-trained_ neural
network model, learned from large amounts of code snippets and their
descriptions in the English language, and covering six different programming
languages, including Python, Java, Javascript, Go, PHP, and Ruby. The goal of
pre-training is to bootstrap the training process, by establishing an initial
version of the neural network, to be further trained for the specific task of
interest [42, 43, 44, 45]. This approach is called _transfer learning_. In our
case, we fine-tune the CodeBERT model to translate English to Python and
assembly, using our exploit dataset (see § IV).

CodeBERT undergoes unsupervised pre-training using two optimization
objectives: a masked language modeling (MLM) objective [44] and a replaced
token detection (RTD) objective [46]. These two objectives are combined into
one loss function $\underset{\theta}{min}\;\;L_{MLM}(\theta)+L_{RTD}(\theta)$.

The MLM objective selects random positions within the intent word sequence $e$
and code snippet sequence $c$, and replaces them with a special mask token
$[MASK]$. The objective of this pre-training is to predict the original tokens
that were replaced with $[MASK]$:

$L_{MLM}(\theta)=\sum_{i\in m^{e}\bigcup m^{c}}-\log
p^{D_{1}}(x_{i}|e^{masked},c^{masked})$ (5)

where $p^{D_{1}}$ is the model that predicts the masked tokens, $m^{e}$ and
$m^{c}$ are the randomly selected positions, $x=\\{e,c\\}$ is the original
intent-snippet pair, and $e^{masked}$ and $c^{masked}$ are the masked intent
and snippet.

In the RTD objective, both the intent and snippet are corrupted by replacing
the original token with incorrect ones, and the trained model is used as a
_discriminator_ (denoted as $p^{D_{2}}$) to detect whether a token is original
or replaced. To this purpose, CodeBERT uses two _generator_ models (similarly
to Generative Adversarial Networks), one for intents $p^{G_{e}}$ and one for
snippets $p^{G_{c}}$. The generator models are trained to generate plausible
token fits for the masked tokens $e^{masked}$ and $c^{masked}$. The RTD
objective is defined as follows:

$\begin{matrix}L_{RTD}(\theta)={\sum}_{i=1}^{|e|+|c|}\Big{(}\sigma(i)\log
p^{D_{2}}(x_{corrupt},i)+\big{(}1-\sigma(i)\big{)}\\\ \big{(}1-\log
p^{D_{2}}(x^{corrupt},i)\big{)}\Big{)}\\\ \\\
\sigma(i)=\Big{\\{}\begin{matrix}1,\;\;\mathrm{if}\;x_{i}^{corrupt}=x_{i}\\\
0,\;\;\mathrm{otherwise.}\end{matrix}\end{matrix}$ (6)

###  III-C Post-Processing

Post-processing is an automatic post-editing process applied during decoding
in the translation process. The Destandardizer uses the slot map dictionary
generated by the Intent Parser to replace all keys in the standardized intent
(i.e., var0, var1 and var2) with the corresponding memorized values (i.e., dl,
0xbb, and next_cycle).

The generated snippet is then further post-processed using regular expressions
(Code Snippet Cleaning). This operation includes the removal of (any) extra-
spaces in the output, such as between operations and operands, between byte
string identifiers and the byte strings, between objects and method calls in
Python, etc., and the removal of (any) extra-backslashes in escaped characters
(e.g., \\\n). Also, during the post-processing, the newline characters \n are
replaced with new lines to generate multi-line snippets. As a final step,
snippet tokens are joined to form a complete snippet (step 6).

###  III-D Implementation Details

We implement the Seq2Seq model using xnmt [47]. We use an Adam optimizer [48]
with $\beta_{1}=0.9$ and $\beta_{2}=0.999$, while the learning rate $\alpha$
is set to $0.001$. We set all the remaining hyper-parameters in a basic
configuration: layer dimension = $512$, layers = $1$, epochs (with early
stopping enforced) = $200$, beam size = $5$.

Our CodeBERT implementation uses an encoder-decoder framework where the
encoder is initialized to the pre-trained CodeBERT weights, and the decoder is
a transformer decoder. The decoder is composed of $6$ stacked layers. The
encoder follows the RoBERTa architecture [43], with $12$ attention heads,
hidden layer dimension of $768$, $12$ encoder layers, $514$ for the size of
position embeddings. We use the Adam optimizer [48]. The total number of
parameters is 125M. The max length of the input is $256$ and the max length of
inference is $128$. The learning rate $\alpha=0.00005$, batch size = $32$,
beam size = $10$, and assembly train_steps = $2800$, and Python train_steps =
$18000$.

##  IV Model Training

To automatically generate Python and assembly programs used for security
exploits, we curated a large dataset for feeding NMT techniques. We collected
exploits from publicly available databases [26, 49], public repositories
(e.g., GitHub), and programming guidelines. In particular, we focused on
exploits targeting Linux, the most common OS for security-critical network
services, running on IA-32 (i.e., the 32-bit version of the x86 Intel
Architecture). The dataset consists of two parts: (i) a Python dataset, which
contains Python code used by exploits to encode the shellcode, and (ii) an
assembly dataset, which includes shellcode and decoders to revert the
encoding. A sample in the dataset consists of a snippet of code from these
exploits and their corresponding description in the English language. The
datasets are processed though the operations described in § III-A, and used to
train the NMT models, as shown in in Figure 1 (steps 1 and 2).

To deal with the ambiguity of natural language, multiple authors worked
together to describe curated snippet intentions in English. The building
process of the datasets is similar to established corpora in the NMT field
(e.g., the authors of the widespread Django-dataset [50] hired one engineer to
create the corpus). To mitigate bias, we reused the comments written by
developers of the collected programs; when not available, we followed the
style of books/tutorials on assembly/Python and shellcode programming.

Table I summarizes the statistics of both datasets, including the size (i.e.,
the unique pairs of intents-snippets), the unique lines of code snippets, the
unique lines of natural language intents, the unique number of tokens (i.e.,
words), and the average number of tokens per snippet and intent.

TABLE I: Datasets statistics Statistic |  Encoder Dataset |  Decoder Dataset
---|---|---
Dataset size |  $15,540$ |  $3,715$
Unique Snippets |  $14,034$ |  $2,542$
Unique Intents |  $15,421$ |  $3,689$
Unique tokens (Snippets) |  $9,511$ |  $1,657$
Unique tokens (Intents) |  $10,605$ |  $1,924$
Avg. tokens per Snippet |  $11.90$ |  $4.75$
Avg. tokens per Intent |  $14.90$ |  $9.53$

###  IV-A Python Data

Our first dataset contains samples to generate Python code for security
exploits. In order to make the dataset representative of real exploits, it
includes code snippets drawn from exploits from public databases. Differing
from general-purpose Python code found in previous datasets [50], the Python
code of real exploits entails low-level operations on byte data for
obfuscation purposes (i.e., to _encode_ shellcodes). Therefore, real exploits
make extensive use of Python instructions for converting data between
different encoders, for performing low-level arithmetic and logical
operations, and for bit-level slicing, which cannot be found in the previous
general-purpose Python datasets.

In total, we built a dataset that consists of $1,114$ original samples of
exploit-tailored Python snippets, and their corresponding intent in the
English language. These samples include complex and nested instructions, as
typical of Python programming. Table II shows examples of such instructions.
In order to perform more realistic training and for a fair evaluation, we left
untouched the developers’ original code snippets and did not decompose them.
We provided English intents to describe nested instructions altogether.

TABLE II: Examples of encoding instructions in Python Code Snippet |  English Intent
---|---
sb = int(hex(leader)[3:],16) |  Convert the value of leader to hexadecimal, then slice it at index 3, convert it to an int16 and set its value to the variable sb
val2 = int( chunk[i].encode(’hex’), 16 ) ^ xor_byte |  val2 is the result of the bitwise xor between the integer base 16 of the element i of chunk encoded to hex and xor_byte

In order to bootstrap the training process for the NMT model, we include in
our dataset both the original, exploit-oriented snippets and snippets from a
previous general-purpose Python dataset. This enables the NMT model to
generate code that can mix general-purpose and exploit-oriented instructions.
Among the several datasets for Python code generation, we choose the Django
dataset [50] due to its large size. This corpus contains $14,426$ unique pairs
of Python statements from the Django Web application framework and their
corresponding description in English. Therefore, our final dataset contains
$15,540$ unique pairs of Python code snippets alongside their intents in
natural language.

###  IV-B Assembly Data

We built our assembly dataset on top of our previous work [51], in which we
released a dataset for automatically generating assembly from natural language
descriptions. This dataset consists of 3,200 assembly instructions, commented
in English language, which were collected from shellcodes for IA-32 and
written for the Netwide Assembler (NASM) for Linux [52]. In order to make the
data more representative of the code that we aim to generate (i.e., complete
exploits, inclusive of _decoders_ to be delivered in the shellcode), we
enriched the dataset with further samples of assembly code, drawn from the
exploits that we collected from public databases. Differently from the
previous dataset, the new one includes assembly code from _real decoders_ used
in actual exploits. The final dataset contains $3,715$ unique pairs of
assembly code snippets/English intents.

To better support developers in the automatic generation of the assembly
programs, we looked beyond a one-to-one mapping between natural language
intents and their corresponding code. Therefore, the dataset includes $783$
lines (${\sim}21\%$ of the dataset) of _multi-line intents_ , i.e., intents
that generate multiple lines of assembly code, separated by the newline
character \n. These multi-line snippets contain a number of different assembly
instructions that can range between $2$ and $5$. For example, the copy of the
ASCII string “/bin//sh” into a register is a typical operation to spawn a
shell, which requires three distinct assembly instructions, as shown by the
lines 6-7-8 of Listing 1: push the hexadecimal values of the words “/bin” and
“//sh” onto the stack register before moving the contents of the stack
register into the destination register. Further examples of multi-line
snippets include conditional jumps, tricks to zero-out the registers without
generating null bytes, etc. Table III shows two further examples of multi-line
snippets with their natural language intents.

TABLE III: Examples of decoding instructions in assembly Code Snippet |  English Intent
---|---
xor bl, 0xBB \n jz formatting \n mov cl, byte [esi] |  Perform the xor between BL register and 0xBB and jump to the label formatting if the result is zero else move the current byte of the shellcode in the CL register.
xor ecx, ecx \n mul ecx |  Zero out the EAX and ECX registers.

##  V Experimental Evaluation

This section presents an extensive evaluation of our approach to generating
exploits from natural language descriptions. We separate the evaluation of
Python code generation (i.e., the encoding part of the exploit) and assembly
code generation (i.e., the decoding part of the exploit). Thus, we use
distinct test sets for evaluating Python encoders and assembly language
decoders, respectively. We trained two distinct models, using respectively the
Python and the assembly dataset. The models adopt the same architecture.

Differently from previous work in code generation tasks [8, 7, 53, 15, 16,
17], we did not randomly sample individual instructions from the dataset when
dividing the data between training and test set. Indeed, since the ultimate
goal of the programmer is to generate exploits in their entirety, we took all
instructions from an exploit as a whole. Our test sets cover $20$ different
exploits (i.e., $20$ Python programs, and $20$ assembly programs). We exclude
_print_ statements in the Python source code since they are not actually
needed for the exploit. The exploits and their encoding/decoding schemes have
varying complexity and were developed by different programmers for different
purposes. The average number of lines is $23.4$ (median is $19$) for the
Python programs and $26.4$ (median is $24$) for the decoders in assembly
language. The pairs intents-snippets in the test set are unique and are not
included in the training/dev sets. Further information on the test set is
described in Appendix444https://github.com/dessertlab/EVIL.

Next, we present the experimental results using automated metrics (§ V-A) and
manual metrics (§ V-B). In § V-C, we evaluate the approach at generating
exploits in their entirety. In § V-D, we evaluate the computational cost.

###  V-A Automatic Evaluation

TABLE IV: Automated evaluation of the translation task. Bolded values are the best performance. IP= Intent Parser Dataset |  Model |  BLEU-1 (%) |  BLEU-2 (%) |  BLEU-3 (%) |  BLEU-4 (%) |  ACC (%)
---|---|---|---|---|---|---
Python |  Seq2Seq no IP |  72.34 |  62.55 |  56.88 |  52.2 |  31.2
|  Seq2Seq with IP |  86.92 |  83.68 |  81.42 |  79.69 |  45.33
|  CodeBERT no IP |  79.23 |  74.12 |  69.84 |  65.76 |  48.00
|  CodeBERT with IP |  89.22 |  86.78 |  84.94 |  83.50 |  56.00
Assembly |  Seq2Seq no IP |  35.83 |  26.1 |  21.38 |  17.69 |  25.25
|  Seq2Seq with IP |  88.38 |  86.37 |  85.51 |  85.05 |  40.98
|  CodeBERT no IP |  33.42 |  28.39 |  25.38 |  22.72 |  45.9
|  CodeBERT with IP |  88.21 |  85.53 |  84.05 |  82.99 |  45.9

We evaluate the translation ability of both models described in § III-B, i.e.,
Seq2Seq with attention mechanisms and CodeBERT. Moreover, since the Intent
Parser plays a critical role in our approach, we evaluate the ability of the
models with and without the use of the Intent Parser, in order to estimate its
contribution. The configuration without the Intent Parser still adopts the
pre/post-processing pipeline (stopwords filtering, tokenization, embeddings,
etc.) but avoids standardization.

Automatic evaluation metrics are commonly used in the field of machine
translation. They are reproducible, easy to be tuned, and time-saving. The
_BiLingual Evaluation Understudy_ (BLEU) [54] score is one of the most popular
automatic metric [50, 8, 55, 56]. This metric is based on the concept of
n-gram, i.e., the adjacent sequence of $n$ items (e.g., syllables, letters,
words, etc.) from a given example of text or speech. In particular, this
metric measures the degree of n-gram overlapping between the strings of words
produced by the model and the human translation references at the corpus
level. BLEU measures translation quality by the accuracy of translating
n-grams to n-grams, for n-gram of size $1$ to $4$ [57]. The _Exact match
accuracy_ (ACC) is another automatic metric often used for evaluating neural
machine translation [8, 7, 15, 16]. It measures the fraction of the exact
match between the output predicted by the model and the reference.

Table IV shows the best results for each model in terms of BLEU scores and
accuracy. For both the Python and assembly datasets, the results point out
that the Intent Parser notably increases the performance of the translation
task in Python and assembly. Moreover, CodeBERT outperforms the performance of
the Seq2Seq with respect to all metrics for the Python dataset. In the case of
the assembly dataset, the performance of the two models is comparable.

###  V-B Human Evaluation

We further investigate the performance of the translation task by assessing
the deeper linguistic features [58], i.e., the syntax and the semantic of the
code snippets predicted by the models. These features allow us to properly
give credit to semantically-correct code that fails to match the reference one
(e.g., jz label and je label are semantically identical code snippets, even if
they use different instructions), or to provide information whether the
generated code would compile or not. Accordingly, we define two new metrics: a
generated output snippet is considered syntactically correct if it is
correctly structured in the grammar of the target language (i.e., Python or
assembly) and compiles correctly. The output is considered semantically
correct if the snippet is an appropriate translation in the target language
given the intent description. The semantic correctness implies syntax
correctness, while a snippet can be syntactically correct but semantically
incorrect. Of course, the syntactic incorrectness also implies the semantic
one. We evaluated these metrics through manual inspection.

As a simple example, consider the intent res2 is the result of the bitwise and operation between res2 and val1. If the model generates res2 = res2 & val1, then the snippet is considered semantically and syntactically correct. If the model generates the Python instruction res2 = val2 | val1, then the snippet is considered syntactically correct for the Python syntax, but semantically incorrect both because the bitwise operation is not the intended one (i.e., the or instead of the and), and the operands are not the same specified in the intents (i.e., val2 instead of res2). If the model generates the instruction res2 = res2 _ val1, then the snippet is considered also syntactically incorrect, since the symbol _ is not a valid binary operator in Python. Notice that this type of evaluation is rigorous. Even if a single token of the generated snippet (e.g., an operation, a variable/operand, a parenthesis, etc.) is not syntactically (semantically) correct, then the whole snippet is considered syntactically (semantically) incorrect. In the case of the multi-line snippets of the assembly dataset, we compute the syntactic (semantic) correctness as the ratio number of syntactically (semantically) correct single snippets over the total number of snippets composing the multi-lines statement (c.f. § VI-B).

TABLE V: Human evaluation of the translation task. Bolded values are the best performance ($*=$ p$<$0.05). IP= Intent Parser Dataset |  Model |  Syntactic Correctness (%) |  Semantic Correctness (%)
---|---|---|---
Python |  Seq2Seq with IP |  88.53 |  50.13
|  CodeBERT with IP |  93.60* |  67.73*
Assembly |  Seq2Seq with IP |  90.16 |  56.36
|  CodeBERT with IP |  87.05 |  61.90*

We evaluated both types of correctness achieved by Seq2Seq and CodeBERT on the
entire test-sets (all 20 encoders/decoders). For the evaluation, we were
supported by the Python 2 and the NASM compiler, respectively for Python and
assembly code. Since the previous analysis showed that the Intent Parser
notably increases the performance of translation, we evaluated the syntactic
and semantic correctness only when using the Intent Parser. Table V shows the
percentage of the syntactically and semantically correct snippets generated by
the models. The table shows that, for the Python programs, CodeBERT with IP
provides a higher percentage of both syntactically and semantically correct
snippets. We conducted a paired-sample T-test to compare the syntactic
correctness and the semantic correctness values of the code snippet pairs
predicted by the two NMT models (given the same intents). We found that the
differences between CodeBERT and the Seq2Seq are statistically significant for
both metrics with $p<0.05$. For the assembly programs, Seq2Seq provides a
higher percentage of syntactically correct snippets, but these differences are
not statistically significant. Again, CodeBERT outperforms Seq2Seq in the
semantic correctness ($p<0.05$).

These findings highlight that CodeBERT predicts the highest percentage of code
snippets that are semantically equivalent to the English intent. It is
interesting that, differently from the Seq2Seq, this model provides better
performance when applied to the Python dataset. We attribute these differences
to the pre-training of the model, which benefits from knowledge from six high-
level programming languages, including Python. Finally, we investigated the
difference between the percentage of syntactic correctness and the semantic
one. We found that most of the semantically incorrect predictions are due to
wrong labels or variable names, or the omission of parenthesis around
expressions. These errors are easy to identify and correct by a programmer, as
they would require one single edit to make the predicted snippet semantically
consistent with the intent. These errors are further analyzed in § VI.

According to these results, the NMT approach can correctly translate an
individual intent with high likelihood, and the incorrect translations are
still close to being correct. These results support the use of the NMT
approach as a way for developers to look up code snippets that they could not
recall or that are not confident yet to develop themselves, getting a close-
to-correct snippet that they can use with little effort.

###  V-C Whole-exploit evaluation

The ultimate goal of the programmer is to generate entire software exploits.
While evaluation using the manual metrics indicates that the model can
correctly generate individual snippets with high likelihood, we do not know
yet whether the model can generate a correct exploit as a whole. Therefore, we
evaluated the ability of the approach to generate semantically and
syntactically correct code for entire software exploits (i.e., all of the
lines of code in the programs), using two new metrics.

Let $n_{t}^{i}$ be the the number of total lines of the $i$-th program in the
test set ($i\in[1,20]$). Let also consider $n_{syn}^{i}$ as the number of
automatically-generated snippets for the $i$-th program that are syntactically
correct, and $n_{sem}^{i}$ as the number of automatically-generated snippets
that are semantically correct. For every program of the test set, we define
the syntactic correctness of the program $i$ as the ratio
$n_{syn}^{i}/n_{t}^{i}$, and the semantic correctness of the program as the
ratio $n_{sem}^{i}/n_{t}^{i}$. Both metrics range between $0$ and $1$.

Therefore, $\forall i\in[1,20]$, we computed the values $n_{syn}^{i}$ and
$n_{sem}^{i}$ for Python and assembly programs. We performed this analysis
with CodeBERT with IP since it showed the best performance for both datasets
in the human evaluation (§ V-B). We found that the average syntactic
correctness over all the programs of the test set is ${\sim}96\%$ for the
Python programs and ${\sim}93\%$ for the assembly programs. Similarly, we
estimated the average semantic correctness, which is equal to $\sim 76\%$ and
${\sim}81\%$ for Python and assembly programs, respectively. The box-plots in
Figure 2 and Figure 3 summarize the results.

Figure 2: Distribution of the syntactic correctness of the programs. Figure 3:
Distribution of the semantic correctness of the programs.

Despite our conservative evaluation, the approach is able to generate $12$
Python programs and $6$ assembly programs fully composed by syntactically
correct snippets (i.e., the $n_{syn}^{i}/n_{t}^{i}=100\%$). However, this does
not imply that the programs are also executable. For example, the assembly
instruction jz shellcode is syntactically correct, but if the label shellcode
is not defined, then the program would not compile. Therefore, we evaluated
how many programs can be compiled, finding that the $50\%$ of syntactically
correct programs are also compilable and executable. Furthermore, one Python
program and one assembly program are fully composed of semantically correct
snippets (i.e., $n_{sem}^{i}/n_{t}^{i}=100\%$) and, therefore, implement the
original encoding and decoding schemes. We interpret these results as a
promising first research step towards automatically coding software exploits
from natural language intents.

TABLE VI: Illustrative examples of correct output. Dataset |  Natural Language Intent |  Ground Truth |  Model Output
---|---|---|---
Python |  Take the absolute value of subfs then convert subfs to an integer, then cast to a hexadecimal, slice the variable rev_suplx between the indicies 0 and 2 then cast rev_suplx to the type int16, store the value of the summation in the variable xxx |  xxx = hex(int(abs(subfs)) + int(rev_suplx[0:2],16)) |  xxx = hex(int(abs(subfs)) + int(rev_suplx[0:2],16))
|  Append 0xAA to the string encode |  encode += ‘0xAA’ |  encode += ‘0x%02x’%170
Assembly |  Jump short to decode if al is not equal to cl else jump to shellcode. |  cmp al, cl \n jnz short decode \n jmp shellcode |  cmp al, cl \n jne short decode \n jmp shellcode
|  Perform the xor between the current byte of the shellcode and the dl register. |  xor byte [esi], dl |  xor byte [esi], dl
TABLE VII: Illustrative examples of incorrect output. The prediction errors are red/bold. ~~Slashed~~ text refers to omitted predictions. Dataset |  Natural Language Intent |  Ground Truth |  Model Output
---|---|---|---
Python |  Return the result of bitwise left shift of n by rotations bitwise and with mask_value bitwise or n bitwise right shift by the subtraction of rotations from width |  return ((n<<rotations) & mask_value) | (n >> (width $-$ rotations)) |  return (~~(~~ n<<rotations~~)~~ & bitwise~~)~~ | ~~(~~ n >> ~~(~~ width $-$ rotations~~)~~)
|  Convert the value of leader to hexadecimal, then slice it at index 3, convert it to an int16 and set its value to the variable sb |  sb = int(hex(leader)[3:],16) |  sb = int(hex(leader)[3:],32)
Assembly |  Zero out the ecx register and move 25 in the lower 8 bits of the register. |  xor ecx, ecx \n mov cl, 25 |  xor ecx, ecx \n mov al, 25
|  In the decode function jump to lowbound label if the current byte of the shellcode is lower than 0x7 else subtract 0x7 from the byte of the shellcode and jump to common_commands |  decode: \n cmp byte [esi], 0x7 \n jl lowbound \n sub byte [esi], 0x7 \n jmp common_commands |  decode: \n cmp byte [esi], 0x7 \n jl lowbound ~~\n~~ ~~sub byte [esi], 0x7~~ \n jmp common_commands

###  V-D Computational Time

We performed our experiments on a Linux OS running on a virtual machine.
Seq2Seq utilized $8$ CPU cores and $8$ GB RAM. CodeBERT utilized 8 CPU cores,
16 GB RAM, and 2 GTX1080Ti GPUs.

The computational time needed to generate the output depends on the settings
of the hyper-parameters and the size of the dataset. On average, the training
time of the Seq2Seq model is ${\sim}500$ minutes for the Python dataset and
${\sim}60$ minutes for the assembly dataset, while CodeBERT requires for the
training in average ${\sim}220$ minutes for Python and ${\sim}25$ minutes for
the assembly dataset. In total, we performed $50$ different experiments for a
total computational time of ${\sim}150$ hours. Once the models are trained,
the time to predict the output is below 1 second and can be considered
negligible.

##  VI Qualitative Analysis

In this section, we present a qualitative analysis using cherry-picked
examples from our test sets to highlight both successful prediction cases and
failed ones.

###  VI-A Successful Examples

Table VI shows four cases of success predictions for both datasets. The first
row demonstrates our approach’s ability to generate a difficult Python snippet
from a nested natural language intent without any errors. Indeed, the
predicted output contains the correct variable name subfs, rev_suplx, and xxx
with the appropriate functions hex, int, abs indexed in the right order with
the correct parameters. The second row shows an example of implicit model
knowledge. The model is able to append 0xAA by converting the value 170, the
hexadecimal value of 0xAA, to hexadecimal and appending it to the string
variable encode.

The last two rows of the table show the ability of the model in generating
challenging assembly instructions. The third row highlights both the ability
of the Intent Parser in identifying all the registers’ name (i.e., AL and CL),
and the labels (i.e., decode and shellcode), and the ability of the model to
perform the right translation of the order in the if-then-else statements
described in the English intent. The last row is an interesting example of
implicit model knowledge. Indeed, even if it is not stated in the intent, the
model is able to properly predict EDI as the destination register since it is
typically used to store the encoded shellcodes.

###  VI-B Failure Examples

Table VII shows four relevant examples of failure cases. We observe nested
instructions within the intent in the Python examples. In the first row, the
intent implies the order of operations signified by parenthesis in the ground
truth snippet. While the model correctly generates all the operations in the
correct order, it does not enforce the order of operations. The model fails to
derive the implied order of operations from the intent. It also fails to
generate the correct variable mask_value, but instead generates the intent-
repeated token bitwise as a variable, likely due to bitwise being mentioned
frequently in the intent in between operations. In the second row, we observe
the model also generates all the operands and variables correctly, however it
fails to generate the correct parameter 16 to the integer conversion
operation.

The example in the third row illustrates an example of failure due to a lack
of implicit knowledge. The natural language intent does not mention to the CL
register but implicitly refers to it (lower 8 bits of the ECX register).
Therefore, the output results in a syntactically correct but semantically
incorrect prediction. The last row shows a long intent that describes an
entire function. The model is able to properly predict four of the five
assembly instructions composing the decode function. However, it misses the
sub operation after the conditional jump jl. In this case, the semantic
correctness is equal to $0.8$ ($4$ out of $5$ semantically correct snippets).

##  VII Related Work

The task of exploit generation via automatic techniques has been addressed in
several ways. ShellSwap [59] is a system that generates new exploits based on
existing ones, by modifying the original shellcode with arbitrary replacement
shellcode. Hu _et al._ [60] developed a novel approach to construct data-
oriented exploits through data flow stitching, by composing the benign data
flows in an application via a memory error. They built a prototype attack
generation tool that operates directly on Windows and Linux x86 binaries.
Avgerinos et al. [1] developed an end-to-end system for automatic exploit
generation (AEG) on real programs by exploring execution paths. Given the
potentially buggy program in source form, their proposal automatically looks
for bugs, determines whether the bug is exploitable, and produces a working
control-flow hijack exploit string. SemFuzz [61] extracts necessary
information from non-code text related to a vulnerability, using natural
language processing and a semantics-based fuzzing process, in order to
discover and trigger deep bugs. Chen et al. [62] presented techniques to find
out the gadgets, i.e., the basic building block in Jump Oriented Programming
(JOP), and showed these gadgets are Turing complete. They implemented an
automatic tool able to generate JOP shellcodes. Ding et al. [63] proposed a
reverse derivation of a transformation method driven by state machines
indicating the status of data flows, in order to transform the original
shellcode into printable Return Oriented Programming (ROP) payload. Chainsaw
[64] is a tool for analyzing web applications and generating injection
exploits. The tool performs static analysis and defines a model of the
application behavior to generate injection exploits, by leveraging application
workflow structures and database schemes. Brumley et al. [65] proposed an
approach for Automatic Patch-based Exploit Generation (APEG). Starting from a
program and its patched version, the approach identifies the security checks
added by the patch and automatically generates inputs to fail the checks.
Huang et al. [66] introduced a method to automatically generate exploits based
on software crash analysis. This method analyzes software crashes using a
symbolic failure model, to generate exploits from crash inputs and existing
exploits for several types of applications. Xu et al. [67] developed a tool to
find buffer overflow vulnerabilities in binary programs and automatically
generate exploits using a constraint solver. Vulnerability detection is
achieved through symbolic execution and the exploit generated by this tool can
bypass different types of protection.

Our work is radically different from these previous ones. First, our approach
uses natural language statements to generate exploits. Second, we adopt
neither a static nor dynamic program analysis approach (e.g., fuzzing, program
synthesis, etc.), but a statistical, data-driven approach. Therefore, our work
can be considered complementary to these previous solutions, with different
use cases.

##  VIII Ethical Considerations

_Offensive security_ is a sub-field of security research that tests security
measures from an adversary or competitor’s perspective, employing ethical
hackers to probe a system for vulnerabilities [68, 69]. Our work aims to
automate exploit generation, in order to explore critical vulnerabilities
before they are exploited by attackers [1]. Indeed, our work simplifies the
process of coding the exploits to surface security weaknesses within the
software and can provide valuable information about the technical skills,
degree of experience, and intent of the attackers. With this information, it
is possible to implement measures to detect and prevent attacks [3].

##  IX Conclusion

We presented _EVIL_ , an approach for automatic exploit generation for
security assessment purposes, using natural language processing techniques
based on neural networks. Our approach represents the first step towards the
ambitious goal of automatically generating software exploits from natural
language. We develop and released two datasets of real exploits in Python and
assembly language to enable neural network training and experimental
evaluation. We evaluated the feasibility of our approach, using both automated
and manual metrics. Our experiments have shown the ability of the approach in
generating software exploits from natural language descriptions with high
syntactic and semantic correctness.

The results have also revealed that, in most cases, the generated programs do
not execute correctly due to wrong labels or variable names. Programmers can
easily correct these problems, but our goal is full automation. Therefore,
future work includes the improvement of the post-processing phase that looks
at the program context to increase the accuracy of the program generation
task. Future work also includes the development of a single engine that
generates the encoding and decoding schemes at the same time, without
performing two separate translation tasks.

## Acknowledgment

This work has been partially supported by the University of Naples Federico II
in the frame of the Programme F.R.A., project id OSTAGE, the Italian Ministry
of University and Research (MUR) under the programme “PON Ricerca e
Innovazione 2014-2020 – Dottorati innovativi con caratterizzazione
industriale” and Cisco Systems Inc., project id BOTITS.

## References

  * [1] T. Avgerinos, S. K. Cha, B. L. T. Hao, and D. Brumley, “Aeg: Automatic exploit generation,” in _NDSS_ , 2011.
  * [2] T. Avgerinos, S. K. Cha, A. Rebert, E. J. Schwartz, M. Woo, and D. Brumley, “Automatic exploit generation,” _Communications of the ACM_ , vol. 57, no. 2, pp. 74–84, 2014.
  * [3] I. Arce, “The shellcode generation,” _IEEE security & privacy_, vol. 2, no. 5, pp. 72–76, 2004.
  * [4] J. Mason, S. Small, F. Monrose, and G. MacManus, “English shellcode,” in _ACM Conf. on Computer and Communications Security_ , 2009, pp. 524–533.
  * [5] Y. Wu, M. Schuster, Z. Chen, Q. V. Le, M. Norouzi, W. Macherey, M. Krikun, Y. Cao, Q. Gao, K. Macherey _et al._ , “Google’s neural machine translation system: Bridging the gap between human and machine translation,” _arXiv:1609.08144_ , 2016.
  * [6] O. Bojar, R. Chatterjee, C. Federmann, Y. Graham, B. Haddow, M. Huck, A. J. Yepes, P. Koehn, V. Logacheva, C. Monz _et al._ , “Findings of the 2016 conference on machine translation,” in _Conf. on Machine Translation_ , 2016, pp. 131–198.
  * [7] P. Yin and G. Neubig, “A syntactic neural model for general-purpose code generation,” _arXiv:1704.01696_ , 2017.
  * [8] W. Ling, E. Grefenstette, K. M. Hermann, T. Kociský, A. W. Senior, F. Wang, and P. Blunsom, “Latent predictor networks for code generation,” _arXiv:1603.06744_ , 2016.
  * [9] X. V. Lin, C. Wang, D. Pang, K. Vu, and M. D. Ernst, “Program synthesis from natural language using recurrent neural networks,” _University of Washington Department of Computer Science and Engineering, Seattle, WA, USA, Tech. Rep. UW-CSE-17-03-01_ , 2017.
  * [10] X. V. Lin, C. Wang, L. Zettlemoyer, and M. D. Ernst, “Nl2bash: A corpus and semantic parser for natural language interface to the linux operating system,” in _Intl. Conf. on Language Resources and Evaluation (LREC)_ , 2018\.
  * [11] S. Jiang, A. Armaly, and C. McMillan, “Automatically generating commit messages from diffs using neural machine translation,” in _IEEE/ACM Intl. Conf. on Automated Software Engineering (ASE)_. IEEE, 2017, pp. 135–146.
  * [12] Z. Liu, X. Xia, A. E. Hassan, D. Lo, Z. Xing, and X. Wang, “Neural-machine-translation-based commit message generation: how far are we?” in _ACM/IEEE Intl. Conf. on Automated Software Engineering (ASE)_ , 2018, pp. 373–384.
  * [13] M. Ciniselli, N. Cooper, L. Pascarella, D. Poshyvanyk, M. Di Penta, and G. Bavota, “An empirical study on the usage of BERT models for code completion,” _arXiv:2103.07115_ , 2021.
  * [14] X. P. Mai, F. Pastore, A. Göknil, and L. Briand, “A natural language programming approach for requirements-based security testing,” in _29th IEEE International Symposium on Software Reliability Engineering (ISSRE 2018)_. IEEE, 2018.
  * [15] P. Yin and G. Neubig, “Tranx: A transition-based neural abstract syntax parser for semantic parsing and code generation,” _arXiv:1810.02720_ , 2018.
  * [16] ——, “Reranking for neural semantic parsing,” in _Annual Meeting of the Association for Computational Linguistics_ , 2019, pp. 4553–4559.
  * [17] F. F. Xu, Z. Jiang, P. Yin, B. Vasilescu, and G. Neubig, “Incorporating external knowledge through pre-training for natural language to code generation,” _ArXiv_ , vol. abs/2004.09015, 2020.
  * [18] I.R.M. Association, _Software Design and Development: Concepts, Methodologies, Tools, and Applications_. IGI Global, 2013.
  * [19] ——, _Identity Theft: Breakthroughs in Research and Practice_. IGI Global, 2016.
  * [20] K. Z. Snow, S. Krishnan, F. Monrose, and N. Provos, “Shellos: Enabling fast detection and forensic analysis of code injection attacks.” in _USENIX Security Symposium_ , 2011, pp. 183–200.
  * [21] J. Foster, _Sockets, Shellcode, Porting, and Coding: Reverse Engineering Exploits and Tool Coding for Security Professionals_. Elsevier Science, 2005. [Online]. Available: https://books.google.it/books?id=ZNI5dvBSfZoC
  * [22] H. Megahed, _Penetration Testing with Shellcode: Detect, exploit, and secure network-level and operating system vulnerabilities_. Packt Publishing, 2018.
  * [23] J. Koziol, D. Litchfield, D. Aitel, C. Anley, S. Eren, R. Hassell, and N. Mehta, _The Shellcoder’s Handbook: Discovering and Exploiting Security Holes_. Wiley, 2004.
  * [24] J. Erickson, _Hacking, 2nd Edition: The Art of Exploitation_. No Starch Press, 2008.
  * [25] D. Regalado, S. Harris, A. Harper, C. Eagle, J. Ness, B. Spasojevic, R. Linn, and S. Sims, _Gray Hat Hacking The Ethical Hacker’s Handbook, Fourth Edition_. McGraw-Hill Education, 2015.
  * [26] “Exploit Database Shellcodes,” https://www.exploit-db.com/shellcodes?platform=linux_x86/, accessed: 2021-04-16.
  * [27] Z. Géczi and P. Iványi, “Automatic translation of assembly shellcodes to printable byte codes,” _Pollack Periodica_ , vol. 13, no. 1, pp. 3–20, 2018.
  * [28] D. Patel, A. Basu, and A. Mathuria, “Automatic generation of compact printable shellcodes for x86,” in _USENIX Workshop on Offensive Technologies (WOOT)_ , 2020.
  * [29] “Metasploit,” https://www.metasploit.com/, accessed: 2021-04-22.
  * [30] M.-T. Luong, H. Pham, and C. D. Manning, “Effective approaches to attention-based neural machine translation,” _arXiv:1508.04025_ , 2015.
  * [31] C. Park, Y. Yang, K. Park, and H. Lim, “Decoding strategies for improving low-resource machine translation,” _Electronics_ , vol. 9, no. 10, p. 1562, 2020.
  * [32] H. N. Tien and H. N. Thi Minh, “Long sentence preprocessing in neural machine translation,” in _2019 IEEE-RIVF Intl. Conf. on Computing and Communication Technologies (RIVF)_ , 2019, pp. 1–6.
  * [33] M. Oudah, A. Almahairi, and N. Habash, “The impact of preprocessing on arabic-english statistical and neural machine translation,” _arXiv:1906.11751_ , 2019.
  * [34] E. Loper and S. Bird, “Nltk: the natural language toolkit,” _arXiv:cs/0205028_ , 2002.
  * [35] Python, “tokenize,” Accessed: 2020-05-20. [Online]. Available: https://docs.python.org/3/library/tokenize.html
  * [36] G. A. Miller, “Wordnet: a lexical database for english,” _Communications of the ACM_ , vol. 38, no. 11, pp. 39–41, 1995.
  * [37] J. Gu, Z. Lu, H. Li, and V. O. Li, “Incorporating copying mechanism in sequence-to-sequence learning,” in _Annual Meeting of the Association for Computational Linguistics_ , 2016, pp. 1631–1640.
  * [38] Y. Li and T. Yang, “Word embedding for understanding natural language: a survey,” in _Guide to big data applications_. Springer, 2018, pp. 83–104.
  * [39] D. Bahdanau, K. Cho, and Y. Bengio, “Neural machine translation by jointly learning to align and translate,” _arXiv:1409.0473_ , 2015.
  * [40] Z. Feng, D. Guo, D. Tang, N. Duan, X. Feng, M. Gong, L. Shou, B. Qin, T. Liu, D. Jiang, and M. Zhou, “Codebert: A pre-trained model for programming and natural languages,” in _EMNLP_ , 2020.
  * [41] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Advances in neural information processing systems_ , 2017, pp. 5998–6008.
  * [42] M. E. Peters, M. Neumann, M. Iyyer, M. Gardner, C. Clark, K. Lee, and L. Zettlemoyer, “Deep contextualized word representations,” _arXiv:1802.05365_ , 2018.
  * [43] Y. Liu, M. Ott, N. Goyal, J. Du, M. Joshi, D. Chen, O. Levy, M. Lewis, L. Zettlemoyer, and V. Stoyanov, “RoBERTa: A robustly optimized BERT pretraining approach,” _arXiv:1907.11692_ , 2019.
  * [44] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” in _NAACL-HLT_ , 2019\.
  * [45] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell _et al._ , “Language models are few-shot learners,” _arXiv:2005.14165_ , 2020.
  * [46] K. Clark, M.-T. Luong, Q. V. Le, and C. D. Manning, “Electra: Pre-training text encoders as discriminators rather than generators,” in _Intl. Conf. on Learning Representations_ , 2019.
  * [47] G. Neubig, M. Sperber, X. Wang, M. Felix, A. Matthews, S. Padmanabhan, Y. Qi, D. S. Sachan, P. Arthur, P. Godard _et al._ , “Xnmt: The extensible neural machine translation toolkit,” _arXiv:1803.00188_ , 2018.
  * [48] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv:1412.6980_ , 2015.
  * [49] “Shellcodes database for study cases,” http://shell-storm.org/shellcode/, accessed: 2021-04-16.
  * [50] Y. Oda, H. Fudaba, G. Neubig, H. Hata, S. Sakti, T. Toda, and S. Nakamura, “Learning to generate pseudo-code from source code using statistical machine translation (t),” in _IEEE/ACM Intl. Conf. on Automated Software Engineering (ASE)_. IEEE, 2015, pp. 574–584.
  * [51] P. Liguori, E. Al-Hossami, D. Cotroneo, R. Natella, B. Cukic, and S. Shaikh, “Shellcode_IA32: A dataset for automatic shellcode generation,” in _Proceedings of the 1st Workshop on Natural Language Processing for Programming (NLP4Prog 2021)_. Online: Association for Computational Linguistics, Aug. 2021, pp. 58–64. [Online]. Available: https://aclanthology.org/2021.nlp4prog-1.7
  * [52] J. Duntemann, _Assembly language step-by-step: programming with DOS and Linux_. John Wiley & Sons, 2000.
  * [53] A. V. M. Barone and R. Sennrich, “A parallel corpus of python functions and documentation strings for automated code documentation and code generation,” _arXiv:1707.02275_ , 2017.
  * [54] K. Papineni, S. Roukos, T. Ward, and W.-J. Zhu, “Bleu: a method for automatic evaluation of machine translation,” in _Annual Meeting on Association for Computational Linguistics_ , 2002, pp. 311–318.
  * [55] C. Gemmell, F. Rossetto, and J. Dalton, “Relevance transformer: Generating concise code snippets with relevance feedback,” in _Intl. ACM Conf. on Research and Development in Information Retrieval_ , 2020, pp. 2005–2008.
  * [56] N. Tran, H. Tran, S. Nguyen, H. Nguyen, and T. Nguyen, “Does BLEU score work for code migration?” in _IEEE/ACM Intl. Conf. on Program Comprehension (ICPC)_ , 2019, pp. 165–176.
  * [57] L. Han, “Machine translation evaluation resources and methods: A survey,” _arXiv:1605.04515_ , 2016.
  * [58] L. Han, G. J. F. Jones, and A. F. Smeaton, “Translation quality assessment: A brief survey on manual and automatic methods,” _arXiv:2105.03311_ , 2021\.
  * [59] T. Bao, R. Wang, Y. Shoshitaishvili, and D. Brumley, “Your exploit is mine: Automatic shellcode transplant for remote exploits,” in _2017 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2017, pp. 824–839.
  * [60] H. Hu, Z. L. Chua, S. Adrian, P. Saxena, and Z. Liang, “Automatic generation of data-oriented exploits,” in _USENIX Security Symposium_ , 2015, pp. 177–192.
  * [61] W. You, P. Zong, K. Chen, X. Wang, X. Liao, P. Bian, and B. Liang, “Semfuzz: Semantics-based automatic generation of proof-of-concept exploits,” in _ACM Conference on Computer and Communications Security_ , 2017, pp. 2139–2154.
  * [62] P. Chen, X. Xing, B. Mao, L. Xie, X. Shen, and X. Yin, “Automatic construction of jump-oriented programming shellcode (on the x86),” in _ACM Symp. on Information, Computer and Communications Security_ , 2011, pp. 20–29.
  * [63] W. Ding, X. Xing, P. Chen, Z. Xin, and B. Mao, “Automatic construction of printable return-oriented programming payload,” in _Intl. Conf. on Malicious and Unwanted Software: The Americas (MALWARE)_ , 2014, pp. 18–25.
  * [64] A. Alhuzali, B. Eshete, R. Gjomemo, and V. Venkatakrishnan, “Chainsaw: Chained automated workflow-based exploit generation,” in _ACM Conf. on Computer and Communications Security_ , 2016, pp. 641–652.
  * [65] D. Brumley, P. Poosankam, D. Song, and J. Zheng, “Automatic patch-based exploit generation is possible: Techniques and implications,” in _2008 IEEE Symposium on Security and Privacy (sp 2008)_ , 2008, pp. 143–157.
  * [66] S.-K. Huang, M.-H. Huang, P.-Y. Huang, H.-L. Lu, and C.-W. Lai, “Software crash analysis for automatic exploit generation on binary programs,” _IEEE Trans. on Reliability_ , vol. 63, no. 1, pp. 270–289, 2014.
  * [67] L. Xu, W. Jia, W. Dong, and Y. Li, “Automatic exploit generation for buffer overflow vulnerabilities,” in _IEEE Intl. Conf. on Software Quality, Reliability and Security_ , 2018, pp. 463–468.
  * [68] S. Bratus, I. Arce, M. E. Locasto, and S. Zanero, “Why offensive security needs engineering textbooks,” _Yale Law & Policy Review_, p. 2, 2013.
  * [69] J. G. Oakley, “The state of modern offensive security,” in _Professional Red Teaming_. Springer, 2019, pp. 29–41.


#  A Gridless Fourth-order Cumulant-Based DOA Estimation Method under Unknown
Colored Noise

Jiawen Yuan This work was supported by the National Natural Science Foundation
of China under Grant nos. 61871218 and 61701046, the Fundamental Research
Funds for the Central University of China under Grant nos. 3082019NC2019002
and 3082017NP2017421, Funding of Postgraduate Research Practice & Innovation
Program of Jiangsu Province (KYCX20_0201).J. Yuan is with the College of
Electronic and Information Engineering, Nanjing University of Aeronautics and
Astronautics, Nanjing 210016, China

###### Abstract

To reduce the adverse impacts of the unknown colored noise on the performance
degradation of the direction-of-arrival (DOA) estimation, we propose a new
gridless DOA estimation method based on fourth-order cumulant (FOC) in this
letter. We first introduce the non-redundancy single measurement vector (SMV)
through FOC, which is capable of suppressing the Gaussian colored noise. Next,
we analyze the distribution of the estimation error and design an estimation
error tolerance scheme for it. We then combine the atomic norm minimization of
the non-redundancy SMV with the above constraint scheme. This combination
poses the stability of the sparsest solution. Finally, the DOA estimation is
retrieved through rotational invariance techniques. Moreover, this method
extends the gridless DOA estimation to the sparse linear array. Numerical
simulations validate the effectiveness of the proposed method.

###### Index Terms:

gridless DOA estimation method, FOC, SMV, atomic norm minimization, sparse
linear array.

##  I Introduction

Direction-of-arrival (DOA) estimation algorithms have received extensive
research attention in many engineering fields such as radar $\left[1\right]$,
$\left[2\right]$ and wireless communication $\left[3\right]$,
$\left[4\right]$. These algorithms commonly assume that the background noise
is white Gaussian. However, it is a noteworthy phenomenon that occurs in these
fields, where colored noise is output as white noise after passing through
linear components. This phenomenon inevitably mismatches the signal model
proposed by second-order statistics-based DOA estimation methods
$\left[5\right]$,$\left[6\right]$, which is the primary cause of the
performance deterioration in practical applications.

Numerous efforts have been made to deal with DOA estimation in unknown colored
noise $\left[7\right]$-$\left[14\right]$. Based on the assumption that the
noise covariance matrix follows a certain symmetric structure
$\left[7\right]$, $\left[8\right]$, it is feasible to alleviate the influence
of these noises by obtaining the covariance difference matrix. However, this
assumption is hard to satisfy and it fails to work in the circumstance with
more sources than antennas. To overcome the above deficiencies, an algorithm
based on fourth-order cumulant (FOC) $\left[9\right]$ and its variants
$\left[10\right]$-$\left[14\right]$ have been proposed. All these methods have
the ability to expand the effective aperture and to increase the degrees of
freedom without any assumption on the structure of the noise covariance
matrix. In particular, the FOC matrix-based atomic norm minimization (FOC-ANM)
$\left[14\right]$ algorithm associates sparsity with the FOC matrix to offer
reliable estimates under the uniform linear array (ULA) for it fundamentally
eliminates the effect of basis mismatch. Compared with the grid-based DOA
estimation methods $\left[4\right]$, $\left[15\right]$, FOC-ANM achieves a
satisfactory estimation performance. However, FOC-ANM ignores the influence of
the FOC matrix estimation error caused by the limited number of snapshots.

In this letter, we propose a new gridless FOC-based method, named error-
tolerant FOC-ANM (ET-FOCANM), to enhance resolution capability and estimation
accuracy under unknown colored noise. Compared with the existing FOC-based
methods, we analyze the distribution of the estimation error due to the
limited number of snapshots and attach the estimation error tolerance
constraint to an ANM-based model for ensuring a stable and sufficiently sparse
solution. The merits of the ET-FOCANM include robustness to the Gaussian
colored noise, an increased number of detectable sources in the ULA and sparse
linear array (SLA) case, expanded virtual array aperture, and no requirement
of user-parameter in the estimation error tolerance constraint.

$Notations$: $\mathbb{R}$ and $\mathbb{C}$ denote the sets of numbers in real
and complex domains respectively. For a matrix $\bm{A}$, $vec$($\bm{A}$)
represents the vectorization operator by taking column-wise from $\bm{A}$ and
$diag$($\bm{A}$) returns a column vector of the main diagonal elements of
$\bm{A}$. $\bm{A}\geq$ 0 implies that $\bm{A}$ is positive semidefinite.
$\bm{A}\in\\{0,1\\}^{M\times N}$ means that each element of $M\times N$
dimensional matrix $\bm{A}$ is contained in the binary set $\\{$0,1$\\}$. For
a vector $\bm{x}$, $diag$($\bm{x}$) is a diagonal matrix with $\bm{x}$ on the
diagonal. $\|\cdot\|_{2}$ and $\|\cdot\|_{\mathcal{A}}$ are the $l_{2}$ and
atom norms respectively. ($\cdot$)T, ($\cdot$)H, ($\cdot$)∗, and ($\cdot$)-1
are the transpose, conjugate transpose, complex conjugate, and inverse
operation respectively. $\otimes$ and $\odot$ denote the Kronecker and Khatri-
Rao products respectively. $E\\{\cdot\\}$ and $cum\left(\cdot\right)$ indicate
the mathematical expectation and FOC operation respectively.

##  II Signal Model and Preliminaries

###  II-A Signal Model

Suppose that a linear array simultaneously receives signals from $P$
narrowband far-field sources with unknown complex amplitude $s_{p}$ and
distinct DOA $\theta_{p}$, $p=1,...,P$. The antenna index set of this array is
defined as $\Omega=\\{\Omega_{1},...,\Omega_{M}\\}\subseteq\\{1,...,N\\}$ .
For convenience, we consider two linear arrays in this letter, one is ULA with
$\Omega=\\{1,...,N\\}$, and the other is SLA with
$\Omega=\\{\Omega_{1},...,\Omega_{M}\\}$ of $\Omega_{1}=1$ and
$\Omega_{M}=N\left[5\right],\left[6\right]$. Fig. 1 shows a configuration of
the 4-element ULA with $\Omega=\\{1,2,3,4\\}$, 4-element SLA with
$\Omega=\\{1,2,5,7\\}$, and 7-element ULA with $\Omega=\\{1,...,7\\}$, where
the inter-antenna spacing is taken as equaling half of the wavelength.

Figure 1: An example of the 7-element ULA, 4-element ULA and SLA.

The received signals
$\bm{Y}_{\Omega}=\left[\bm{y}_{\Omega}(1),...,\bm{y}_{\Omega}(J)\right]\in\mathbb{C}^{M\times
J}$ with multiple snapshots $J$ in the $M$-element SLA case can be expressed
as follows

$\bm{Y}_{\Omega}=\bm{\Gamma}_{\Omega}\bm{Y}=\bm{A}_{\Omega}\bm{S}+\bm{N}_{\Omega}\quad
with\quad\bm{Y}=\bm{A}\bm{S}+\bm{N},$ (1)

where $\bm{\Gamma}_{\Omega}\in\\!\\!\\{0,1\\}^{M\times N}$,
$\bm{A}_{\Omega}=\left[\bm{a}_{\Omega}(\theta_{1}),...,\bm{a}_{\Omega}(\theta_{P})\right]\in\mathbb{C}^{M\times
P}$, $\\!\\!\bm{S}=\left[\bm{s}(1),...,\bm{s}(J)\right]\in\mathbb{C}^{P\times
J}$, and
$\bm{N}_{\Omega}=\left[\bm{n}_{\Omega}(\theta_{1}),...,\bm{n}_{\Omega}(\theta_{J})\right]\in\mathbb{C}^{M\times
J}$ denote the selection matrix, the array manifold matrix, the source signal,
and the additive noise, respectively. Let
$\bm{a}_{\Omega}(\theta_{p})=\left[e^{j\pi(\Omega_{1}-1)\sin\theta_{p}},...,e^{j\pi(\Omega_{M}-1)\sin\theta_{p}}\right]^{T}$
be the $p$-th steering vector. In the $N$-element ULA, the definitions of
$\bm{Y},\bm{N}\in\mathbb{C}^{N\times J}$, and $\bm{A}\in\mathbb{C}^{N\times
P}$ are similar to the previous ones. Moreover, we assume that the source is
uncorrelated stationary non-Gaussian with zero-mean, and the noise is the
zero-mean colored Gaussian independent of the sources.

###  II-B Definition of reduce-complexity FOC (RC-FOC) matrix

Based on the above assumptions, the received signals are considered as
stationary non-Gaussian processes with zero mean. Since the FOC is blind to
Gaussian processes $\left[16\right]$, we construct the FOC matrix
$\bm{C}_{4}\in\mathbb{C}^{N^{2}\times N^{2}}$ of $\bm{y}(t)\in\mathbb{C}^{N}$
as

$\displaystyle\bm{C}_{4}$
$\displaystyle=E\left\\{\left(\bm{Y}\otimes\bm{Y}^{*}\right)\left(\bm{Y}\otimes\bm{Y}^{*}\right)^{H}\right\\}-E\left\\{\bm{Y}\otimes\bm{Y}^{*}\right\\}$
(2) $\displaystyle\quad\times
E\left\\{\bm{Y}\otimes\bm{Y}^{*}\right\\}^{H}-E\left\\{\bm{Y}\bm{Y}^{H}\right\\}\otimes
E\left\\{\bm{Y}\bm{Y}^{H}\right\\}^{*}.$

Then $\bm{C}_{4}$ can be decomposed as

$\displaystyle\bm{C}_{4}=\left(\bm{A}\odot\bm{A}^{*}\right)\bm{C}_{\bm{S}}\left(\bm{A}\odot\bm{A}^{*}\right)^{H}=\overline{\bm{B}}\bm{C}_{\bm{S}}\overline{\bm{B}}^{H},$
(3)

where $\bm{C}_{\bm{S}}=diag(\bm{\gamma})\in\mathbb{C}^{P\times P}$,
$\bm{\gamma}=\left[\gamma_{4s_{p}},...,\gamma_{4s_{P}}\right]^{T}\in\mathbb{C}^{P}$,
and its $p$-th element
$\gamma_{4s_{p}}=cum\left(s_{p},s_{p}^{*},s_{p}^{*},s_{p}\right)$.

Due to a large number of redundant elements in $\bm{C}_{4}$, the RC-FOC matrix
$\bm{R}_{4}\in\mathbb{C}^{(2N-1)\times(2N-1)}$ is designed in
$\left[14\right]$

$\displaystyle\bm{R}_{4}$
$\displaystyle=\overline{\bm{G}}^{-1}\overline{\bm{H}}^{T}\bm{C}_{4}\overline{\bm{H}}\overline{\bm{G}}^{-1}$
(4)
$\displaystyle=\overline{\bm{G}}^{-1}\overline{\bm{H}}^{T}\overline{\bm{B}}\bm{C}_{\bm{S}}\overline{\bm{B}}^{H}\overline{\bm{H}}\overline{\bm{G}}^{-1}=\bm{B}\bm{C}_{\bm{S}}\bm{B}^{H},$

where
$\overline{\bm{G}}=\overline{\bm{H}}^{T}\overline{\bm{H}}=diag\left\\{1,...,N,N-1,...,1\right\\}$
and
$\overline{\bm{H}}^{T}=\left[\overline{\bm{H}}_{1}^{T},\overline{\bm{H}}_{2}^{T},...,\overline{\bm{H}}_{N}^{T}\right]\in\mathbb{R}^{(2N-1)\times
N^{2}}$ is an orthogonal matrix. Moreover, the definition of
$\overline{\bm{H}}_{n}$ is represented as

$\\!\overline{\bm{H}}_{n}=\left\\{\begin{array}[]{cc}{\left[\mathbf{0}_{N\times(N-1)},\bm{I}_{N}\right]}&\\!n=1\\\
{\left[\mathbf{0}_{N\times(N-n)},\bm{I}_{N},\mathbf{0}_{N\times(n-1)}\right]}&\\!\quad
2\\!\leq\\!n\leq\\!\\!N\\!\\!-\\!\\!1\\!\\!\\\
{\left[\bm{I}_{N},\mathbf{0}_{N\times(N-1)}\right]}&\\!n=N.\end{array}\right.$
(5)

$\bm{B}=\left[\bm{b}(\theta_{1}),...,\bm{b}(\theta_{P})\right]\in\mathbb{C}^{(2N-1)\times
P}$ is the new array manifold matrix with the $p$-th column vector
$\bm{b}(\theta_{p})=\left[e^{-j\pi(N-1)\sin\theta_{p}},...,e^{j\pi(N-1)\sin\theta_{p}}\right]^{T}$.

##  III The ET-FOCANM Algorithm

###  III-A Introduction of non-redundancy SMV

Consider a ULA composed of $N$ omnidirectional antennas, since
rank($\bm{R}_{4}$) is tied to the number of sources in the ULA case, the
condition $P<(4N-3)$ can be taken as a priori information. Given $\bm{R}_{4}$
as in $\left(4\right)$, let us define the vector $\overline{\bm{z}}$.

$\displaystyle\overline{\bm{z}}$
$\displaystyle=vec\left(\bm{R}_{4}\right)=\left(\bm{B}^{*}\odot\bm{B}\right)\bm{\gamma}$
(6)
$\displaystyle=\sum\nolimits_{p=1}^{P}\gamma_{4s_{p}}\bm{b}\left(\theta_{p}\right)^{*}\odot\bm{b}\left(\theta_{p}\right)=\bm{HD\gamma},$

where
$\bm{D}=\left[\bm{d}(\theta_{1}),...,\bm{d}(\theta_{P})\right]\in\mathbb{C}^{(4N-3)\times
P}$, and
$\bm{d}(\theta_{p})=\left[e^{-j\pi(2N-2)\sin\theta_{p}},...,e^{j\pi(2N-2)\sin\theta_{p}}\right]^{T}$.
It can be seen that $\overline{\bm{z}}$ still has the repeating entries.
Therefore, we choose a new orthogonal matrix
$\bm{H}\in\mathbb{C}^{(2N-1)^{2}\times(4N-3)}$ whose form is consistent with
$\overline{\bm{H}}$ to perform the linear transformation on
$\overline{\bm{z}}$

$\bm{z}=\bm{G}^{-1}\bm{H}^{T}\overline{\bm{z}}=\bm{D\gamma}=\sum\nolimits_{p=1}^{P}\gamma_{4s_{p}}\bm{d}\left(\theta_{p}\right),$
(7)

where $\bm{z}\in\mathbb{C}^{4N-3}$ is the non-redundancy single measurement
vector (SMV) and $\bm{G}=\bm{H}^{T}\bm{H}$. As a byproduct, it can generate
$O\left\\{4N-3\right\\}$ degrees of freedom from only $O\left\\{N\right\\}$
antennas, which is beneficial to detect more sources.

###  III-B Estimation error tolerance scheme

Since finite snapshots inevitably lead to estimation error in the actual
situation, it has the potential to relax the above equality constraint
$\left(7\right)$ and demand instead

$\bm{z}=\bm{D}\bm{\gamma}+\bm{\varepsilon}=\bm{x}+\bm{\varepsilon},$ (8)

in which $\bm{\varepsilon}$ is the estimation error vector from non-redundancy
SMV. As shown in $\left[5\right]$, the sparse model $\bm{x}$ can be linearly
represented by $P$ atoms in a set of the continuous atoms, so we make the
following optimization to reconstruct $\bm{x}$

$\hat{\bm{x}}=\underset{\bm{x}}{\arg\min}\|\bm{x}\|_{\mathcal{A}}\quad
s.t.\quad\|\bm{\varepsilon}\|_{2}^{2}=\|\bm{z}-\bm{x}\|_{2}^{2}\leq\xi,$ (9)

where $\xi$ denotes the tolerance of error energy. Unlike the constraint in
$\left[14\right]$, this inequality is controlled by $\xi$, where $\xi$ is a
result of multiple factors, including signal-to-noise ratio (SNR) and
snapshot. Thus, it is hard to select a proper value of $\xi$ for the final
DOAs.

To proceed, we innovatively propose a new estimation error tolerance scheme
that does not depend on $\xi$ but on the statistical property. First, let
$\Delta\bm{C}_{4}=\hat{\bm{C}_{4}}-\bm{C}_{4}$ be the estimation error matrix
of FOC and $\hat{\bm{C}_{4}}$ denote the sample observation of $\bm{C}_{4}$.
Inspired by $\left[17\right]$, we deduce the distribution of error component
$vec(\Delta\bm{C}_{4})$ in the complex domain, which is expressed by

$vec\left(\Delta\bm{C}_{4}\right)\sim AsN(\bm{0},\bm{V}).$ (10)

$AsN(\bm{0},\bm{V})$ denotes asymptotic normal distribution with zero mean and
the covariance matrix $\bm{V}$. Meanwhile, the element of $\bm{V}$ can be
determined by

$\begin{array}[]{l}\\!\\!\\!\\!cov\left\\{\hat{c}_{4}(\tau),\hat{c}_{4}(\rho)\right\\}\\!\\!=\\!\\!\frac{1}{J}\\!\\!\left\\{Q_{44}(\tau;\rho)-\sum_{v=1}^{3}\\!\\!\left[\\!\\!\begin{array}[]{l}Q_{42}\left(\tau;k_{1}^{\prime},k_{v1}^{\prime}\right)\\!\\!E\\{k_{v2}^{\prime}k_{v3}^{\prime}\\}\\!+\\!Q_{42}\left(\tau;k_{v2}^{\prime},k_{v3}^{\prime}\right)\\!\\!E\\{k_{1}^{\prime}k_{v1}^{\prime}\\}\\\
+Q_{42}^{*}\left(\rho;k_{1}^{\prime},k_{v1}^{\prime}\right)\\!\\!E\\{k_{v2}k_{v3}\\}^{*}\\!+\\!Q_{42}^{*}\left(\rho;k_{v2}^{\prime},k_{v3}^{\prime}\right)\\!\\!E\\{k_{1}k_{v1}\\}^{\\!*}\end{array}\\!\\!\right]\right.\\\
\\!\\!+\\!\\!\left.\sum_{\mu,\\!v=\\!1}^{3}\\!\\!\\!\left[\\!\\!\\!\\!\begin{array}[]{l}Q_{22}\left(k_{1},k_{v1};k_{1}^{\prime},k_{\mu
1}^{\prime}\right)\\!\\!E\\{k_{v2}k_{v3}\\}^{*}\\!\\!E\\{k_{\mu
2}^{\prime}k_{\mu
3}^{\prime}\\}^{\\!*}\\!\\!+\\!\\!Q_{22}\left(k_{v2},k_{v3};k_{1}^{\prime},k_{\mu
1}^{\prime}\right)\\!\\!E\\{k_{1}k_{v1}\\}^{\\!*}\\!\\!E\\{k_{\mu
2}^{\prime}k_{\mu 3}^{\prime}\\}^{\\!*}\\\
\\!+\\!Q_{22}\left(k_{1},k_{v1};k_{\mu 2}^{\prime},k_{\mu
3}^{\prime}\right)\\!\\!E\\{k_{v2}k_{v3}\\}^{\\!*}\\!\\!E\\{k_{1}^{\prime}k_{\mu
1}^{\prime}\\}^{\\!*}\\!\\!+\\!\\!Q_{22}\left(k_{v2},k_{v3};k_{\mu
2}^{\prime},k_{\mu
3}^{\prime}\right)\\!\\!E\\{k_{1}k_{v1}\\}^{\\!*}E\\{k_{1}^{\prime}k_{\mu
1}^{\prime}\\}^{\\!*}\end{array}\\!\\!\right]\\!\\!\right\\}\\!\\!.\end{array}$
(11)

where $\tau\\!=\\!\left\\{k_{1},\\!k_{2},\\!k_{3},\\!k_{4}\right\\}$,
$\rho\\!\\!=\\!\\!\left\\{\\!k_{1}^{{}^{\prime}},\\!k_{2}^{{}^{\prime}},\\!k_{3}^{{}^{\prime}},\\!k_{4}^{{}^{\prime}}\\!\right\\}$,
$k_{11}\\!=\\!k_{2}$, $k_{12}\\!=\\!k_{3}$, $k_{13}\\!=\\!k_{4}$,
$k_{21}\\!=\\!k_{3}$, $k_{22}\\!=\\!k_{2}$, $k_{23}\\!=\\!k_{4}$,
$k_{31}\\!=\\!k_{4}$, $k_{32}\\!=\\!k_{3}$, $k_{33}\\!=\\!k_{2}$ and the same
as $k^{{}^{\prime}}$. $E\\{k_{1}k_{v1}\\}$ is the expectation of
$y_{k_{1}}y_{k_{v1}}$ and the same as
$E\\{k_{1}^{{}^{\prime}}k_{v1}^{{}^{\prime}}\\}$, $E\\{k_{v2}k_{v3}\\}$,
$E\\{\\!k_{v2}^{{}^{\prime}}k_{v3}^{{}^{\prime}}\\!\\}$,
$E\\{\\!k_{1}^{{}^{\prime}}k_{\mu 1}^{{}^{\prime}}\\!\\}$, $E\\{\\!k_{\mu
2}^{{}^{\prime}}k_{\mu 3}^{{}^{\prime}}\\!\\}$. The definition of $Q_{ij}$ is
as follows

$\displaystyle\\!\\!Q_{ij}\\!=\\!\mathop{\lim}\limits_{J\to\infty}\\!\\!Jcov\\{\hat{m}_{i},\hat{m}_{j}\\}\\!=\\!\\!\\!\\!\sum\limits_{\xi=-\infty}^{\infty}\\!\\!\\!cov\\{{f_{k}}(t),f_{{k^{{}^{\prime}}}}(t+\xi)\\},$
(12)

where ${f_{k}}(t)={y_{{k_{1}}}}(t)y_{{k_{2}}}^{*}(t)\cdots{y_{{k_{i}}}}(t)$
and
${f_{{k^{{}^{\prime}}}}}(t)={y_{k_{1}^{{}^{\prime}}}}(t)y_{k_{2}^{{}^{\prime}}}^{*}(t)\cdots{y_{k_{j}^{{}^{\prime}}}}(t)$,
$i,j\leq 4$. $y_{{k_{i}}}(t)$ denotes the $k_{i}$-th element of $\bm{y}(t)$
with $k_{i}\in\left[1,N\right]$, and the same as $y_{k_{j}^{{}^{\prime}}}(t)$.

Next, utilizing the orthogonal invariance property of Gaussian random matrix,
it can be inferred as

$\displaystyle\bm{\varepsilon}=$
$\displaystyle\bm{G}^{-1}\bm{H}^{T}vec\left(\Delta\bm{R}_{4}\right)=\bm{G}^{-1}\bm{H}^{T}vec\left(\widehat{\bm{R}}_{4}-\bm{R}_{4}\right)$
$\displaystyle=$
$\displaystyle\bm{G}^{-1}\bm{H}^{T}\left(\overline{\bm{G}}^{-1}\overline{\bm{H}}^{T}\right)\otimes\left(\overline{\bm{G}}^{-1}\overline{\bm{H}}^{T}\right)vec\left(\Delta\bm{C}_{4}\right)$
$\displaystyle=$ $\displaystyle\bm{W}vec\left(\Delta\bm{C}_{4}\right)\sim
AsN\left(0,\bm{W}\bm{V}\bm{W}^{H}\right).$ (13)

It directly results in

$\left\|\bm{W}^{-\frac{1}{2}}\bm{\varepsilon}\right\|_{2}^{2}\sim
As\chi^{2}(4N-3),$ (14)

where $As\chi^{2}(4N-3)$ denotes the asymptotic chi-square distribution with
$4N-3$ degrees of freedom.

Finally, based on the property of $\chi^{2}$ distribution, the following
inequality holds with a high probability $1-\delta$ where $\delta=0.001$ is
enough:

$\left\|\bm{W}^{-\frac{1}{2}}\bm{\varepsilon}\right\|_{2}^{2}\leq\eta.$ (15)

The choice of $\eta$ is easily calculated by the code $chi2inv(1-\delta,4N-3)$
in Matlab.

###  III-C ANM-based model attached to the above constraint

We propose the error-tolerant problem by substituting the (15) into the
constraint term of (9)

$\hat{\bm{x}}=\underset{\bm{x}}{\arg\min}\|\bm{x}\|_{\mathcal{A}}\quad
s.t.\quad\left\|\bm{W}^{-\frac{1}{2}}\bm{\varepsilon}\right\|_{2}^{2}\leq\eta.$
(16)

This problem must always yield the optimal solution at least as sparse as that
in (9). Further, the result of (16) can be solved by the SDP problem
$\left[18\right]$

$\displaystyle\\{\hat{\bm{x}},\hat{q},\bm{T}(\hat{\bm{\mu}})\\}=\underset{\bm{x},q,T(\bm{\mu})}{\arg\min}\frac{1}{2}q+\frac{1}{2}\mu_{1}$
$\displaystyle
s.t.\left\|\bm{W}^{-\frac{1}{2}}\bm{\varepsilon}\right\|_{2}^{2}\leq\eta,\left[\begin{array}[]{cc}\bm{T}(\bm{\mu})&\quad\bm{x}\\\
\bm{x}^{H}&\quad q\end{array}\right]\geq 0,$ (19)

where $q$ denotes the smallest dilation factor and
$\bm{T}\left(\bm{\mu}\right)$ represents the Hermitian Toeplitz matrix with
its first column $\bm{\mu}=\left[\mu_{1},...,\mu_{4N-3}\right]^{T}$ and
rank($\bm{T}\left(\bm{\mu}\right))=P\leq(4N-4)$. Hence, when the convex
optimization toolbox called CVX $\left[19\right]$ produces the optimal
solution $\bm{T}\left(\bm{\mu}\right)$ of (17), it is easy to estimate the
DOAs through some general techniques such as Vandermonde decomposition
$\left[5\right]$, rotational invariance techniques (ESPRIT) $\left[20\right]$,
spectral peak search $\left[9\right]$ and its variant root-MUSIC
$\left[21\right]$. To simplify the calculation, we perform rotational
invariance techniques on the ensuing DOA estimation.

##  IV The Extension to an SLA

In this subsection, we extend ET-FOCANM method to the SLA case. For
simplicity, we mainly focus on one type of the SLA, which is the minimum
redundancy array (MRA) $\left[5\right]$, $\left[6\right]$. Therefore,
according to the signal model (1) and the definition of $\bm{C}_{4}$, the FOC
matrix $\bm{C}_{4\Omega}\in\mathbb{C}^{M^{2}\times M^{2}}$ is designed as
follows

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\bm{C}_{4\Omega}$
$\displaystyle=E\left\\{\left(\bm{Y}_{\Omega}\otimes\bm{Y}_{\Omega}^{*}\right)\left(\bm{Y}_{\Omega}\otimes\bm{Y}_{\Omega}^{*}\right)^{H}\right\\}\\!-\\!E\left\\{\bm{Y}_{\Omega}\otimes\bm{Y}_{\Omega}^{*}\right\\}$
(20)
$\displaystyle\\!\quad\\!\times\\!E\left\\{\bm{Y}_{\Omega}\\!\otimes\\!\bm{Y}_{\Omega}^{*}\right\\}^{H}\\!-\\!E\left\\{\bm{Y}_{\Omega}\bm{Y}_{\Omega}^{H}\right\\}\otimes
E\left\\{\bm{Y}_{\Omega}\bm{Y}_{\Omega}^{H}\right\\}^{*}.$

Then we derive $\bm{R}_{4}$ under the SLA case

$\\!\\!\\!\bm{R}_{4}=\bm{G}_{\Omega}^{-1}\left[\left(\bm{\Gamma}_{\Omega}\otimes\bm{\Gamma}_{\Omega}\right)\overline{\bm{H}}\right]^{T}\\!\bm{C}_{4\Omega}\\!\left[\left(\bm{\Gamma}_{\Omega}\otimes\bm{\Gamma}_{\Omega}\right)\overline{\bm{H}}\right]\bm{G}_{\Omega}^{-1},$
(21)

where
$\bm{G}_{\Omega}=\left[\left(\bm{\Gamma}_{\Omega}\otimes\bm{\Gamma}_{\Omega}\right)\overline{\bm{H}}\right]^{T}\left[\left(\bm{\Gamma}_{\Omega}\otimes\bm{\Gamma}_{\Omega}\right)\overline{\bm{H}}\right]$.
The acquisition of $\bm{z}$ is the same as in (8) and let
$\Delta\bm{C}_{4\Omega}=\hat{\bm{C}}_{4\Omega}-\bm{C}_{4\Omega}$ be the FOC
matrix error in the SLA case. Since $vec(\bm{C}_{4\Omega})$ is equal to
$\left[\left(\bm{\Gamma}_{\Omega}\otimes\bm{\Gamma}_{\Omega}\right)\otimes\left(\bm{\Gamma}_{\Omega}\otimes\bm{\Gamma}_{\Omega}\right)\right]vec(\bm{C}_{4})$,
which reveals that $vec(\bm{C}_{4\Omega})\sim AsN(\bm{0},\bm{V}_{\Omega})$.
Further, we conclude the link between $\bm{\varepsilon}$ and
$\Delta\bm{C}_{4\Omega}$

$\displaystyle\\!\\!\bm{\varepsilon}=\bm{W}_{\Omega}vec\left(\Delta\bm{C}_{4\Omega}\right)\sim
AsN\left(\bm{0},\bm{W}_{\Omega}\bm{V}_{\Omega}\bm{W}_{\Omega}^{H}\right),$
(22)

where
$\bm{W}_{\Omega}\\!\\!\\!\\!=\\!\\!\\!\\!\bm{G}^{-1}\bm{\\!H}^{T}(\bm{G}_{\Omega}^{-1}\left(\left(\bm{\Gamma}_{\Omega}\otimes\bm{\Gamma}_{\Omega}\right)\overline{\bm{H}}\right)^{T}\otimes\bm{G}_{\Omega}^{-1}\left(\left(\bm{\Gamma}_{\Omega}\otimes\bm{\Gamma}_{\Omega}\right)\overline{\bm{H}}\right)^{T})$.
Similarly, we have

$\left\|\bm{W}_{\Omega}^{-\frac{1}{2}}\bm{\varepsilon}\right\|_{2}^{2}\sim
As\chi^{2}(4N-3).$ (23)

The denoising problem in the SLA case is rewritten as follows:

$\widehat{\bm{x}}=\underset{\bm{x}}{\arg\min}\|\bm{x}\|_{\mathcal{A}}\quad
s.t.\left\|\bm{W}_{\Omega}^{-\frac{1}{2}}\bm{\varepsilon}\right\|_{2}^{2}\leq\eta,$
(24)

and the problem (22) is equivalent to

$\displaystyle\\{\hat{\bm{x}},\hat{q},\bm{T}(\hat{\bm{\mu}})\\}=\underset{\bm{x},q,T(\bm{\mu})}{\arg\min}\frac{1}{2}q+\frac{1}{2}\mu_{1}$
$\displaystyle
s.t.\left\|\bm{W}_{\Omega}^{-\frac{1}{2}}\bm{\varepsilon}\right\|_{2}^{2}\leq\eta,\left[\begin{array}[]{cc}\bm{T}(\bm{\mu})&\quad\bm{x}\\\
\bm{x}^{H}&\quad q\end{array}\right]\geq 0.$ (27)

To get an accurate estimate of $\bm{T}(\bm{\mu})$ through CVX, we use
rotational invariance techniques again to retrieve the DOAs.

##  V Simulation Results

In this subsection, compared with MUSIC-LIKE $\left[9\right]$, JDS-FOC
$\left[11\right]$ and FOC-ANM $\left[14\right]$ algorithms, we provide several
simulations to demonstrate the effectiveness of the proposed method. Consider
the ULA and redundancy SLA composed of $4$ omnidirectional antennas in Fig. 1.
Furthermore, the non-Gaussian sources are modeled as
$\bm{s}\left(t\right)=\bm{F}\left(t\right)\bm{e}\left(t\right)$ where
$\bm{F}(t)=diag\\{f_{1}(t),...,f_{P}(t)\\}$ and
$\bm{e}(t)=\left[e_{1}(t),...,e_{P}(t)\right]^{T}$. The zero-mean Gaussian
processes $f_{p}(t)$ and $e_{p}(t)$ are with unit-variance and
$\sigma_{s}^{2}$-variance $\left[13\right]$, respectively. The noise is
generated by Gaussian white noise through a second-order autoregressive filter
$\left[22\right]$ with the coefficients $\left[1,-1,0.8\right]$. For each
simulation, $100$ Monte Carlo trials are collected.

Figure 2: RMSE of DOA estimation versus SNR with $J=300$. Figure 3: RMSE of
DOA estimation versus snapshots with SNR = $-3$ dB.

To illustrate the estimation precision performance of ET-FOCANM, we employ the
root mean square error (RMSE) as a metric to evaluate estimation precision.
The DOAs of the uncorrelated signals are $\theta_{1}=-23^{\circ}$ and
$\theta_{2}=17^{\circ}$ in the first simulation. Fig. 2 plots the RMSE curve
as SNR varies from $-6$ dB to $12$ dB with $3$ dB as the step. Fig. 3 depicts
the RMSE curve as snapshots $J$ varies from $100$ to $600$ with $100$ as the
step. It is indicated in Fig. 2 and Fig. 3 that ET-FOCANM outperforms the
other methods in the ULA case due to its appropriate error energy constraints.
Moreover, the resulting RMSEs verify that the estimation error of ET-FOCANM
applied to SLAs is much smaller than that applied to ULAs under the same
antenna scale.

##  VI Conclusion

In this letter, we propose a gridless FOC-based method, named ET-FOCANM, for
DOA estimation in the two linear arrays. After suppressing the colored noise
by FOC, ET-FOCANM implements the practicable estimation error tolerance scheme
and is converted into an ANM-based form. The experimental results indicate
that ET-FOCANM can achieve better angular precision and resolution capability
than the traditional algorithms. For future work, it will be worth applying
the alternating direction method of multipliers to speed up the solution of
the ANM-based form in ET-FOCANM.

## References

  * [1] Y. Fang, S. Zhu and Y. Gao, “Direction Finding by Covariance Matrix Sparse Representation With Sensor Gain and Phase Uncertainties in Unknown Non-Uniform Noise,” _IEEE Wireless Commun. Lett._ , vol. 10, no. 1, pp. 175-179, Jan. 2021.
  * [2] Y. Zhang, G. Zhang and H. Leung, “Gridless coherent DOA estimation based on fourth-order cumulants with Gaussian colored noise,” _IET Radar Sonar Navig._ , vol. 14, no. 5, pp. 677-685, Feb. 2020.
  * [3] H. Chen, W. Wang and W. Liu, “Joint DOA, Range, and Polarization Estimation for Rectilinear Sources With a COLD Array,” _IEEE Wireless Commun. Lett._ , vol. 8, no. 5, pp. 1398-1401, Oct. 2019.
  * [4] Y. Tian and H. Xu, “Calibration nested arrays for underdetermined DOA estimation using fourth-order cumulant,” _IEEE Commun. Lett._ , vol. 24, no. 9, pp. 1949-1952, Sept. 2020.
  * [5] Z. Yang and L. Xie, “On gridless sparse methods for line spectral estimation from complete and incomplete data,” _IEEE Trans. Signal Process._ , vol. 63, no. 12, pp. 3139–3153, Jul. 2015.
  * [6] X. Wu, W. Zhu and J. Yan, “A Toeplitz covariance matrix reconstruction approach for direction-of-arrival estimation,” _IEEE Trans. Veh. Technol._ , vol. 66, no. 9, pp. 8223-8237, Apr. 2017.
  * [7] S. Prasad et al., “A transform-based covariance differencing approach for some classes of parameter estimation problems,” _IEEE Trans. Acoust. Speech Signal Process._ , vol. 36, no. 5, pp. 631–641, May 1988.
  * [8] F. Wen, J. Shi, and Z. Zhang, “Direction finding for bistatic MIMO radar with unknown spatially colored noise,” _Circuits Syst. Signal Process._ , vol. 39, no. 4, Feb. 2020.
  * [9] B. Porat and B. Friedlander, “Direction finding algorithms based on high-order statistics,” _IEEE Trans. Signal Process._ , vol. 39, no. 9, pp. 2016–2024, Sep. 1991.
  * [10] C. Liu, Z. Ye, and Y. Zhang, “DOA estimation based on fourth-order cumulants with unknown mutual coupling,” _Signal Process._ , vol. 89, no. 9, pp. 1839-1843, Sep. 2009.
  * [11] W. Zeng, X. Li, and X. Zhang, “Direction-of-arrival estimation based on the joint diagonalization structure of multiple fourth-order cumulant matrices,” _IEEE Signal Process. Lett._ , vol. 16, no. 3, pp. 164-167, Mar. 2009.
  * [12] B. Liao and S. Chan, “A cumulant-based method for direction finding in uniform linear arrays with mutual coupling,” _IEEE Antennas Wirel. Propag. Lett._ , vol. 13, pp. 1717-1720, Nov. 2014.
  * [13] J. Liu, W. Zhou, and X. Wang, “Fourth-order cumulants-based sparse representation approach for DOA estimation in MIMO radar with unknown mutual coupling,” _Signal Process._ , vol. 128, pp. 123–130, Nov. 2016.
  * [14] Y. Zhang, G. Zhang and H. Leung, “Gridless sparse methods based on fourth-order cumulant for DOA estimation,” in _Proc. IGARSS_ , Yokohama, Japan, 2019, pp. 3416-3419.
  * [15] B. Wang, J. Liu and X. Sun, “Mixed sources localization based on sparse signal reconstruction,” _IEEE Signal Process. Lett._ , vol. 19, no. 8, pp. 487-490, Aug. 2012.
  * [16] N. Yuen and B. Friedlander, “DOA estimation in multipath: an approach using fourth-order cumulants,” _IEEE Trans. Signal Process._ , vol. 45, no. 5, pp. 1253-1263, May 1997.
  * [17] A. V. Dandawate and G. B. Giannakis, “Asymptotic properties and covariance expressions of kth-order sample moments and cumulants,” in _Proc. ACSSC_ , Pacific Grove, CA, USA, 1993, pp. 1186-1190.
  * [18] G. Tang et al., “Compressed sensing off the grid,” _IEEE Trans. Inf. Theory_ , vol. 59, no. 11, pp. 7465-7490, Nov. 2013.
  * [19] M. Grant and S. Boyd, “CVX: Matlab software for disciplined convex programming, version 2.0 beta,” _Available online at http://cvxr.com/cvx_ , Sep. 2013.
  * [20] J. Lin et al., “Time-Frequency Multi-Invariance ESPRIT for DOA Estimation,” _IEEE Antennas Wirel. Propag. Lett._ , vol. 15, pp. 770-773, Mar. 2016.
  * [21] B. D. Rao and K. V. S. Hari, “Performance analysis of Root-Music,” _IEEE Trans. Acoust., Speech, Signal Proces._ , vol. 37, no. 12, pp. 1939-1949, Dec. 1989.
  * [22] H. Jiang, J. Zhang, and K. Wong, “Joint DOD and DOA estimation for bistatic MIMO radar in unknown correlated noise,” _IEEE Trans. Veh. Technol._ , vol. 64, no. 11, pp. 5113–5125, Nov. 2015.