## 1

Muhammad Ikram1,3, Pierrick Beaume2, and Mohamed Ali Kaafar12
1Macquarie University, 2Data61 CSIRO, 3University of Michigan
{Muhammad.Ikram<EMAIL_ADDRESS><EMAIL_ADDRESS>

## DaDiDroid: An Obfuscation Resilient Tool for Detecting Android Malware via
Weighted Directed Call Graph Modelling

Muhammad Ikram1,3, Pierrick Beaume2, and Mohamed Ali Kaafar12
1Macquarie University, 2Data61 CSIRO, 3University of Michigan
{Muhammad.Ikram<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

With the number of new mobile malware instances increasing by over 50%
annually since 2012 [25], malware embedding in mobile apps is arguably one of
the most serious security issues mobile platforms are exposed to. While
obfuscation techniques are successfully used to protect the intellectual
property of apps’ developers, they are unfortunately also often used by
cybercriminals to hide malicious content inside mobile apps and to deceive
malware detection tools. As a consequence, most of mobile malware detection
approaches fail in differentiating between benign and obfuscated malicious
apps. We examine the graph features of mobile apps code by building weighted
directed graphs of the API calls, and verify that malicious apps often share
structural similarities that can be used to differentiate them from benign
apps, even under a heavily “polluted” training set where a large majority of
the apps are obfuscated. We present DaDiDroid an Android malware app detection
tool that leverages features of the weighted directed graphs of API calls to
detect the presence of malware code in (obfuscated) Android apps. We show that
DaDiDroid significantly outperforms MaMaDroid [24], a recently proposed
malware detection tool that has been proven very efficient in detecting
malware in a clean non-obfuscated environment. We evaluate DaDiDroid’s
accuracy and robustness against several evasion techniques using various
datasets for a total of 43,262 benign and 20,431 malware apps. We show that
DaDiDroid correctly labels up to 96% of Android malware samples, while
achieving an 91% accuracy with an exclusive use of a training set of
obfuscated apps.

##  2 INTRODUCTION

In recent years, Android OS and mobile applications (apps in short) have
experienced an exponential growth with over 3 Million apps on Google Play [15]
in 2017. This popularity naturally attracted malware developers leading to a
continuous 50% yearly increase of the number of malware apps for over five
years [25]. Several research studies (e.g., [20, 18, 12]) focused on dynamic
runtime-network analysis to detect potential malicious behaviour of Android
apps. Another line of research (e.g., [23, 4, 8, 1]) aimed to reduce the
resources required to perform dynamic analysis by adopting static code
analysis approaches [20, 19]. DroidAPIMiner [1], for instance, uses the
frequency of API calls to classify malware apps. Recently, MaMaDroid [24]
leverages the similarity in the code of apps as extracted from the transition
probabilities between different API calls to build an efficient Android
malware detection system. However, the increased code complexity and the use
of obfuscation techniques as a way to protect apps from code theft, reverse
engineering and code inspection, pose several challenges to static analysis of
malware apps.

We set the objective of building an effective mobile malware detection tool
that is resistant to code obfuscation techniques. We propose DaDiDroid, a tool
that runs static code analysis, leveraging apps’ API call graphs to
characterize the functional behaviour of apps and filter out malicious
behaviour, even in presence of an obfuscated code. Specifically, DaDiDroid
builds, for each Android app, the API families calls graph (e.g., API packages
such as android.util.log are abstracted to android) and extracts the weighted
directed graphs features (we use 23 unique graph features) to model the
Android app behaviour. Using the graph features, we then rely on a classifier
to establish whether or not the directed weighted graph belongs to a benign
app.

This paper makes the following contributions:

Open Source Malware Detection Tool: We present our open source111For further
research, we plan to release DaDiDroid to the research community. malware
detection tool, DaDiDroid, that leverages features from the weighted directed
graph representation of apps’ API calls (§ 4).

Efficacy of Graph Features: We empirically evaluate our proposed system and
demonstrate the efficacy of the graph features as peculiar features
distinguishing between benign and malicious apps. We use a combination of six
publicly available datasets to evaluate the effectiveness of DaDiDroid and
determine that, in a clean environment (i.e., no obfuscation used by apps) it
detects malware apps with an accuracy of 96.5%. We present the distributions
of some selected graph features to show how they could be used as
discriminating features of (obfuscated) malware and benign apps.

Comparison against MaMaDroid:  We empirically show (cf. § 6 and § 6.3) that
the accuracy of MaMaDroid, a recent static analysis mobile malware detection
tool, is heavily dependent of the balance in the training dataset as captured
by the ratio of benign versus malicious apps. In addition, we show that
MaMaDroid is prone to obfuscation techniques with a generated false negatives
as high as 86.3%.

DaDiDroid’s Robustness Against Obfuscation: We show that DaDiDroid is robust
against several code obfuscation techniques. With no obfuscated apps present
in the training set, DaDiDroid accurately classifies 91.2% of all obfuscated
apps222Android apps that use several code obfuscation techniques, further
reviewed in § 3 and discussed in § 6.3., an average 17.7% higher success rates
when compared to MaMaDroid.

##  3 OVERVIEW OF OBFUSCATION TECHNIQUES

An Android app package (i.e., APK) comes a compressed file containing all the
module and content. Generally, the compressed APK include: four directories
(res, assets, lib, and META-INF) and three files (AndroidManifest.xml,
classes.dex, and resources.arsc). Among these components, classes.dex contains
Java classes of an app, organized in a way the Dalvik virtual machine can
interpret and execute.

In general, obfuscation attempts to obscure a program and makes the source
code333Some obfuscation techniques may also attempt to transform machine code,
however, in this work we consider source code obfuscation techniques. more
difficult for humans to understand, to evade malware detection tools, or both.
Developers can deliberately obfuscate code (i.e., Java classes in classes.dex)
to protect app’s (malicious) logic or purpose, prevent tampering, or to deter
reverse engineering efforts. Common obfuscation techniques used by apps
include:

Call Indirection: This involves the manipulation of apps’ call graphs by
calling any two methods from each others. In essence, in this obfuscation
technique, a method invocation is moved into a new method which, in turn, is
invoked in place of the original method.

String Encoding and Encryption: Strings are very common-used data structures
in software development. In an obfuscated app, strings could be encrypted to
prevent information leakage. Based on cryptographic functions, the original
plain texts are replaced by random strings and restore at runtime. As a
result, string encryption could effectively hinder hard-coded static scanning.

Packing: In this obfuscation, an APK file is composed of an origin APK and a
wrapper APK. Generally, a wrapper APK launches the origin APK into memory and
executes it on Android devices. A wrapper APK may employ encryption to hide
(or limit access to) the original APK which are decrypted at runtime thus
often evade static code analysis.

Identifier Renaming: In software development, for good readability, code
identifiers’ names are usually meaningful, though developers may follow
different naming rules. However, these meaningful names also accommodate
reverse-engineers to understand the code logic and locate the target functions
rapidly. Therefore, to reduce the potential information leakage, the
identifier’s name could be replaced by a meaningless string. Generally, with
this obfuscation technique, a given API’s name such as myApp.net.myPackage is
transformed to at most three-letters words such as a.bc.def.

##  4 THE DADIDROID SYSTEM

Figure 1 depicts an overview of the four steps of the DaDiDroid’s malware
detection system. By leveraging source code analysis and graph theory, we
extract APIs call graphs of Android apps (step 1) and then model the
relationships among APIs (step 2). We use various graph features (step 3) and
machine learning algorithms (step 4) to classify apps. We provide details of
these steps in the following.

APIs Call Graph Extraction: We aim to model the behaviour of apps (benign and
malware) from the API calls in the source code. To this end, the first step in
DaDiDroid is to extract the apps’ call444An Android often requires user’s
interactions to switch back to app’s main GUI. The switching among apps GUIs
as programming is termed method callback or simply callback. For ease of
presentation, we use a generic term, “call”, to also denote callback. graphs
by performing static analysis on the apps’ APKs (Android Apps packages). We
use Soot [30], a Java optimization and analysis framework, to extract API call
graphs and then instrument FlowDroid (v2.5) [5] to extract dependencies among
the APIs.

Our intuition is that malware may use calls for various operations, in a
different graph structure, than benign apps (further elaborated in Section
6.1). To ensure the benign graph structures (resp. graph features such as
diameter, in/out degree, see Table 4) are different enough from the malicious
ones, we abstract API calls package to their respective families.

Figure 1: Overview of DaDiDroid: The dashed-arrows represent calls to other
functions that are not shown in the figure.

The APIs calls abstractions refers to all possible calls of APIs from every
and each API present in the code. That is, for each app in our dataset (see
Table 1), we determine all possible calls amongst the APIs. For instance, as
depicted in Figure 1 (step 1), we find that the API call com.fac.ex:Execute()
instantiates the functions android.util.log:d() and
java.lang.Throwable:getMessage(). For the API family abstraction, we first
derive the family names of the APIs and then construct the family call graphs.
For example, from android.net.http and java.sql APIs we obtain API family
names android and java, respectively and build the graph of calls based solely
based on the family names of the APIs.

The abstraction provides resilience to API changes in the Android framework as
families are often added and deprecated less frequently than single API calls.
At the same time, this does not abstract away the behavior of an app. To
implement similar functionalities or operations, families include and assemble
classes and interfaces that may be frequently modified by developers. By using
API family names for modeling the types of operation, we can limit the
consequences of any modification to the included classes or interfaces. For
instance, java.sql provides in/out and update operations to modify databases.
However, java family also provides additional classes for other operations.
Thus by using abstract family names of APIs, we not only capture the behaviour
of a given app but also ensure the resiliency of DaDiDroid against frequent
changes to methods or functions of classes and interfaces.

Developer may extend the functionalities of their apps by importing a self-
defined API. As mentioned earlier, developers also often resort to obfuscate
the APIs in the source code. To capture the self-defined and obfuscated APIs
in during our call graph extraction process, we rely on previous work [24] and
introduce two types of family names in our APIs calls abstraction: self-
defined and obfuscated. We rely on previous works [28] [24] to further
determine the difference between these two APIs. In principle, we describe an
API to be obfuscated if either at least 50% of its functions or methods are at
most 3 characters (see § 6.3 for further information) or if we are unable to
determine what is implemented, extended, or inherited by its class [28, 24].
When operating in API abstraction level, we abstract an API call to its
package name using the list of Android packages, which as of Android OS v8.0
[16] includes 243 Android and 101 Google APIs.

DaDiDroid detects if malware developers attempt to define their “self-defined”
APIs such as com.google.MyMalware with API names com.google (or family name
com). The derived lists of Android and Google APIs and classes ensure the
detection of any attempt that malware developers may perform to evade
DaDiDroid by naming their self-defined APIs to legal android and google APIs
such as com.google.MyMalware which could have been abstracted as com.google
without APIs classes whitelist.

Overall, for Android API Level 26 [16], we obtain 387 distinct APIs and 12
different families (Android, dalvik, java, javax, junit, apache, json, com,
xml, google, self-defined, and obfuscated). We evaluated DaDiDroid in family
and API abstraction modes. We observe that DaDiDroid’s results were similar to
that of its operation in API abstraction mode. To ease presentation, in § 6,
we present our analysis of DaDiDroid operating in family abstraction mode.

Graph Generation: We model the relationships among API calls (resp. API
families) in the Android apps as weighted, directed graph $G({\bf V},{\bf
E},{\bf W})$. As DaDiDroid uses static analysis, the graph obtained from Soot
and FlowDroid represents the flow of functions that are potentially called by
the app. Each node in ${\bf V}$ corresponds to a unique API call (resp. API
family name) in the Android app. A directed link $(u,v)\in{\bf E}$ is
presented in the graph if and only if an API, $u\in{\bf V}$, calls a method in
another API, $v\in{\bf V}$. A weight $w\in{\bf W}$ represents the number of
times $u$ calls a method in $v$. Note that the links $(u,v,w)$ and $(v,u,w)$
may both exist if Android app’s APIs are calling each other methods
reciprocally.

For each Android app, we represent the relationships among API calls (resp.
API families) as adjacency matrix containing the number of occurrence of
possible transitions from $v_{i}$ to $v_{j}$.

Features Extraction: We leverage graph metrics (or features, listed in Table
4) to quantify the relationship among API calls. As some of the graph metrics,
such as clustering coefficient, are defined only for undirected graphs, we
first convert our directed graphs into a weighted, undirected graphs and then
extract the corresponding graph metrics.

Classification: The last step in DaDiDroid is to perform classification, i.e.,
labelling apps as either benign or malware. To this end, we use a supervised
two-class Support Vector Machine (SVM) classifier [26], $k$-Nearest Nighbours
($k$-NN) [2], and Random Forest [6], all implemented using _Weka_ [17], an
open source machine learning library in Java programming language.

We form two classes by labelling malware and benign apps’ graph features (cf.
Table 4) as positives and negatives, respectively. We use 80% of the instances
for training and 20% for testing. For two-class SVM, appropriate values for
parameters $\gamma$ (_radial basis function kernel_ parameter [27]) and
$\upsilon$ (SVM parameter) are set empirically by performing a greedy grid
search on ranges $2^{-10}\leq\gamma\leq 2^{0}$ and $2^{-10}\leq\upsilon\leq
2^{0}$, respectively, on each training dataset. Likewise, for other
classifiers, we perform empirical tests to set their parameters.

##  5 DATASET IN USE

Dataset: We use previously published datasets which include 63,693 Android
apps (apk files) consisting of 43,262 benign and 20,431 malware samples. Table
1 summaries the dataset in use. We aim to verify that DaDiDroid is robust to
the existence of a variety of Android malware samples as well as to
heterogenous APIs. We then consider a dataset that includes a mix of
obfuscated and non-obfuscated apps as well as newer and (relatively) older
apps with a publication date ranging from August 2010 to June 2018. Our
dataset consists of samples from the following data sources:

Marvin [22]. This source consists of a total of 38,740 apps, constituted from
28,181 benign apps and 10,559 malware samples.

Drebin [4]. It consists of 5,525 malware samples collected from August 2010 to
October 2012.

Old Benign. This dataset includes a sample of 5,879 benign apps collected by
PlayDrone [31] between April and November 2013 and published on the Internet
Archive Machine [3].

New Benign. We use a customised crawler and unofficial Google Play API [14] to
download a sample of 1,788 free apps, belong to 29 different categories, from
the Google Play. We use VirusTotal to determine whether or not the app’s embed
in their source codes.

ObData I. We obtained this dataset from Garcia et al., [13] which consists of
obfuscated apps employing various code transformation (i.e., obfuscation)
techniques such as Encoding and Call Indirection (explained later in § 6.3).

ObData II. Apps developers often minify apps’ source code by mapping the API
names to names such as myApp.net.myPackage with at most three letters: a.b.c
or a.bc.def (cf. § 6.3). By parsing the API names that correspond to a given
Android app in the Marvin dataset, we construct a sample of 7,975 apps that
employ source code minification technique.

Dataset | #Apps | # Benign | # Malicious | Date Range
---|---|---|---|---
Marvin [22] | 38,740 | 28,181 | 10,559 | 06/12–05/14
Drebin [4] | 5,525 | - | 5,525 | 08/10–10/12
OldBenign | 5,909 | 5,909 | - | 04/13–11/13
NewBenign | 1,788 | 1,788 | - | 06/17–06/17
ObData I [13] | 883 | - | 883 | 06/12–05/14
ObData II [22] | 7,975 | 5,884 | 2,091 | 05/13–03/14
PackedApps [11] | 2,873 | 1,500 | 1,373 | 07/16–02/17
Total | 63,693 | 43,262 | 20,431 | 08/10–06/18
Table 1: Overview of the datasets used in our analysis. We obtain two samples
of obfuscated apps: We acquire “ObData I” from authors of [13] and use the
Marvin dataset for obfuscated apps (cf. Section 6.3) to construct “ObData II”.

PackedApps. We obtained this dataset from Dong et al., [11] which consists of
1,500 and 1,371 packed–original APK wrapped in another APK–benign and
malicious APKs, respectively.

Datasets Annotation: To analyze the classification results of DaDiDroid, we
annotate our datasets considering reports from VirusTotal [32]. VirusTotal is
an online service that aggregates the scanning capabilities provided by more
than 68 antivirus (AV) tools, scanning engines and datasets. It has been
widely used in research literature to detect malicious apps, executables,
software and domains [20]. After completing the scanning process for a given
app, VirusTotal generates a report that indicates which of the participating
AV scanning tools detected any malware activity in the app under consideration
and the corresponding malware signature (if any). By parsing VirusTotal
reports, we extract the number of affiliated AV tools that identified any
malware activity and annotate each app in our dataset with the corresponding
results.

##  6 EVALUATION OF DADIDROID

In this section, we present a detailed experimental evaluation of DaDiDroid.

###  6.1 The Intuition

We first conduct preliminary experiments in order to verify our main intuition
that graph features are valuable to differentiate benign and malicious apps.

To further analyze the importance of our features in classifying malware and
benign apps, we use an information-theoretic metric, information gain ratio
[10]. This metric is used to quantify the differentiation power of features
i.e., our graph metrics or features. In this context, information gain is the
mutual information between a given graph metric $X_{i}$ and the class label
$C$ $\in$ {Benign, Malware}. Formally, for a given graph feature $X_{i}$ and
the class label $C$, the information gain of $X_{i}$ with respect to $C$ is
defined as:

$GainRatio(X_{i},C)=\frac{(H(C)-H(C|X_{i}))}{H(X_{i})}$ (1)

where H($X_{i}$) = $-\sum_{i\in N}p(x_{i})log(p(x_{i}))$ denotes the marginal
entropy of the graph feature $X_{i}$ and H(C$|$ $X_{i}$) represents the
conditional entropy of class label $C$ given graph feature $X_{i}$. In other
words, information gain ratio quantifies the reduction in the uncertainty of
the class label $C$ given that we have the complete knowledge of feature
$X_{i}$. Figure 2 shows the information gain ratio of our graph features
extracted from the Marvin dataset and the Drebin dataset (cf. Table 1). We
observe that the “algebraic connectivity” and the “assortativity” are the most
distinct between benign and malicious apps. This analysis reveals that the
minimum betweenness centrality (see Figure 2) and the number of weakly
connected components (see Figure 2) are insignificant in classifying malware
and benign apps that correspond to Marvin and Drebin dataset.

(a) Marvin Dataset

(b) Drebin+Oldbenign

Figure 2: Information gain ratio of our graph features for the (a) Marvin
dataset and (b) Drebin+Oldbenign dataset.

###  6.2 Effectiveness of DaDiDroid

Using the datasets summarised in Table 1, we perform experiments to analyze
the effectiveness of DaDiDroid’s classification on benign and malicious
samples. We also study the effect of unbalanced training data on DaDiDroid’s
performance. We chose to compare to MaMaDroid, as the most recent work in the
space, since MaMaDroid also aims to leverage API-calls to extract
probabilistic-features building a Hidden Markov model of transitions between
API calls.

We use the classic F-measure = $2~{}\times$
($\frac{precision~{}\times~{}recall}{precision~{}+~{}recall})$, where
precision = $\frac{TP}{TP+FP}$ and recall = $\frac{TP}{TP+FN}$, to evaluate
the classification accuracy. TP means true positives denoting the number of
apps correctly classified as malicious. Likewise, FN (false negatives) and FP
(false positives) indicate the number of samples mistakenly identified as
benign and malicious, respectively. For all experiments, we perform 10-fold
cross validation using at least one malicious and one benign dataset from
Table 1.

Effectiveness of Classifiers: In order to generalize the classification of
DaDiDroid, we use three machine learning classification algorithms: two-class
SVM, $k$-NN, and Random Forest.

Table 2 summarizes the performance of the classifiers. Our results show that
the Random Forest classifier achieves the highest accuracy with an accuracy of
90% and 96% in classifying malware and benign drawn from the Drebin+oldbenign
and the Marvin datasets, respectively. Perhaps due to an overfitting effect in
our dataset, two-class SVM showed poor results and may require further pruning
and detailed analysis of parameters, as well as a selection of the optimal set
of prominent features to improve the classification performances [21, 6]. We
resort to the Random Forest classifier as our best classifier and use it next
to compare against MaMaDroid and in our analysis of the effect of unbalanced
training sets as well as the study of the resilience against the obfuscation
techniques.

Dataset | Classifier | TP | FP | Precision | Recall | FM | Accuracy
---|---|---|---|---|---|---|---
| RF | 90.3% | 9.7% | 90.3% | 90.3% | 90.3% | 90.1 %
Drebin+OB | SVM | 70.5% | 29.2% | 71% | 70.5% | 70.4% | 71.4 %
|  $k$-NN | 86.8% | 13.2% | 86.8% | 86.8% | 86.8% | 87.3 %
| RF | 95.7% | 6.6% | 95.7% | 95.7% | 95.7% | 96.5 %
Marvin | SVM | 81.8% | 32.4% | 81.1% | 81.8% | 81.1% | 82.7 %
|  $k$-NN | 94.1% | 9.6% | 94% | 94.1% | 94.1% | 94.3 %
Table 2: Performance of our classifiers in classifying malware and benign
drawn from Marvin [22] and Drebin+oldbenign (OB) datasets. Here RM means
Random Forest while FM, TP, FP represent F1-Measure, True Positives rate and
False Positives rate respectively.

Effectiveness of DaDiDroid with Unbalanced Training Dataset: In order to
determine the minimum number of apps required to train DaDiDroid, we analyze
several sets of training and testing datasets drawn from the Marvin dataset
(see in Table 1). Figure 3 depicts the effect of unbalanced dataset on
performance of DaDiDroid (with Random Forest). In the case of using fixed size
of benign apps and various sets of malware apps (resp. benign apps) in the
training phase, we observe that DaDiDroid outperforms MaMaDroid with on
average 12% higher accuracy.

Moreover, the results also show that DaDiDroid achieves higher accuracy (96%)
in case of limited number (i.e, 1,500) of benign apps in training phase. In
contrast, MaMaDroid [24] shows vulnerability to unbalanced training dataset.
In Figure 3b, in the case of using fixed size of malicious apps and a set
1,500 of benign instances in the training phase, we observe that DaDiDroid
outperforms MaMaDroid with on average 26% higher accuracy.

(a)

(b)

Figure 3: Analyzing the effect of unbalanced dataset on the performance of
DaDiDroid (with Random Forest in classification phase) and MaMaDroid: In (a)
we use 2,990 benign apps and vary sets of malware apps to measure the accuracy
while in (b) we use a fixed size of malware apps (7,390) and vary the set of
benign apps.

###  6.3 Robustness Against Obfuscation Techniques

The main goal of obfuscation is to either secure apps’ source codes or to hide
apps’ malware components. In this section, we evaluate the robustness of our
proposed system against several types of obfuscation techniques.

Whitespace: To reduce the readability of source code, this (basic) obfuscation
technique adds or removes white-spaces in apps source code. As DaDiDroid
leverages API calls (and API family names) only, this obfuscation technique
should have no effect on the accuracy of DaDiDroid.

Call Indirection (CI): This involves the manipulation of apps’ call graphs by
calling any two methods from each others. To measure the performance of
DaDiDroid to Call Indirection, we use the Drebin and OldBenign datasets (cf.
Table 1) for training our classifiers. We use NewBenign and 210 Call
Indirecting malware apps drawn from ObData I [13] for testing. Table 3 shows
the robustness of DaDiDroid against this type of obfuscation. We observe that
15 (7%) of apps, having Call Indirection obfuscation, were classified as
benign. In contrast, MaMaDroid [24] mis-classified 63 (30%) apps that employ
Call Indirection obfuscation techniques.

String Encoding and Encryption (SEE): With this obfuscation technique, an
app’s developer encodes the used APIs to unintelligible ones. To evaluate the
performance of DaDiDroid to String Encoding and Encryption, we use the Drebin
and OldBenign datasets (cf. Table 1) for training our classifiers. We use
NewBenign and 673 malware apps, with this obfuscation technique, drawn from
ObData I [13] for testing. Table 3 shows the robustness of DaDiDroid against
String Encoding and Encryption obfuscation. We found that 20% of apps, having
String Encoding and Encryption obfuscation, were classified as benign. In
contrast, MaMaDroid [24] results in 86% of false negatives.

Obf. Tech. | Scheme | TP | FP | P | R | FM | A
---|---|---|---|---|---|---|---
| DaDiDroid | 92.9% | 4.5% | 70.7% | 92.9% | 80.2% | 95.2%
CI | MaMaDroid [24] | 70.0% | 3.5% | 70.0% | 70.0% | 70.0% | 93.7%
| DaDiDroid | 79.5% | 4.5% | 86.9% | 79.5% | 83.1% | 91.1%
SEE | MaMaDroid [24] | 13.7% | 23.2% | 59.4% | 13.7% | 22.2% | 73.8%
| DaDiDroid | 98.4% | 0.9% | 97.9% | 98.4% | 98.2% | 98.8%
Packing | MaMaDroid [24] | 98.4% | 1.2% | 97.5% | 98.4% | 97.9% | 98.7%
| DaDiDroid | 77.1% | 7.1% | 91.6% | 77.1% | 83.7% | 95.2%
IR | MaMaDroid [24] | 65.2% | 2.2% | 70.0% | 96.8.0% | 77.8% | 65.2%
| DaDiDroid | 82.7% | 4.5% | 90.1% | 82.7% | 86.2% | 91.2%
CI+SEE+Packing+IR | MaMaDroid [24] | 27.1% | 3.5% | 79.1% | 27.1% | 40.3% | 73.5%

Table 3: Comparison of our proposed system, DaDiDroid, with MaMaDroid on
obfuscated datasets (cf. Section 5). Here, FM means F-measure while P, R, and
A represent precision, recall, and accuracy, respectively.

Packing: With this obfuscation technique, an app’s developer wraps the
original APKs inside another APKs. To evaluate the performance of DaDiDroid to
packing obfuscation, we use 80% and 20% of the PackedApps dataset (cf. Table
1) for training and testing our classifiers, respectively, and use 10-fold
cross validation in our experiments. Table 3 shows the robustness of DaDiDroid
against Packing obfuscation. We found that 1.6% of apps, having Packing
obfuscation, were classified as benign. In contrast, MaMaDroid [24] results in
1.2% of false positives.

Identifier Renaming: With Identifier Renaming, a given API’s name such as
myApp.net.myPackage is transformed to at most three-letters words such as
a.bc.def. By parsing the API names that correspond to a given Android app in
Marvin dataset, we determine this type of obfuscation in our datasets.
Leveraging previous works [28, 24], we describe an API to be obfuscated if
either at least 50% of its functions or methods are at most 3 characters or if
we are unable to determine what is implemented or extended by its class.

We draw apps with no Identifier Renaming from Marvin dataset to train
MaMaDroid and DaDiDroid and use ObData II (cf. Table 2) to measure their
robustness against minification. Once again, we use 80% and 20% of the data
for training and testing, respectively, and use 10-fold cross validation in
our experiments.

(a)

(b)

Figure 4: Robustness of DaDiDroid against Identifier Renaming (or
minification): (a) F1-Measure and accuracy; and (b) false negatives and false
positives.

Table 3 overviews and Figure 4 further illuminates on the robustness of
DaDiDroid against Identifier Renaming. With increasing proportions of apps
that employ Identifier Renaming, in Figure 4a, we observe a decreasing trend
in DaDiDroid’s and MaMaDroid’s performance. When tested with 100% of ObData
II, we observe that DaDiDroid outperforms MaMaDroid: F1-Measure of MaMaDroid
drops from 87% to 78% whereas we notice merely 5% (from 88% to 83%) decrease
in DaDiDroid’s F1-Measure. In Figure 4b, we notice that minimification mainly
affects the number of false negatives. With 83% of F1-Measure, DaDiDroid miss-
classifies only 20% of the malware apps in testing dataset as benign. In
contrasts, besides its lower F1-Measure (78%), MaMaDroid results in 35% of
false negatives. Overall, for its high F1-Measure and low false negatives,
DaDiDroid pays a very reasonable cost of 7% of false positives rate.

Overall, when tested on samples of benign and malware apps that involve four
types obfuscation techniques, we observe (cf. Table 3) that DaDiDroid
outperforms MaMaDroid with on average 46.2% and 17.7%, respectively, higher
F1-Measure and accuracy, however, with a cost of 1% higher false positive rate
than that of MaMaDroid.

##  7 RELATED WORK

A number of studies have characterised and detected malicious activities in
Android apps. Several works [20, 18, 12, 9] rely on dynamic runtime-network
analysis to detect potential malicious behaviour of Android apps. To reduce
the resource required in performing dynamic analysis, a large body of works
[23, 4, 8] perform static code analysis to detect malware component in Android
apps. However, due recent development in obfuscation techniques and malware
developers’ affinity to obfuscate their apps [11], static analysis of Android
malware apps is an active research topic. CrowDroid [7] performed dynamic
analysis apps network traces to detect malware activities of Android apps. By
collecting sequence of requests sent to remote servers, it built features
vectors that consisted of number of calls of a specific API to differentiate
malware apps from benign apps. Drebin [4] performed static analysis of API
calls and requests to permission. It also analyzed hard-coded URLs in apps’
source codes to determine apps’ benign or malicious activities. DroidApiMiner
[1] proposed a new approach by using the frequencies of API calls to sensitive
APIs. StormDroid [8] improved the detection of DroidApiMiner by analyzing APIs
calls sequences along with the API calls frequencies analysis.

Similarly, MaMaDroid [24] improved the in-efficiency of both DroidAPIMiner and
StormDroid [8] by using the transitions probabilities among API calls as
features. However, we empirically analyzed that MaMaDroid is dependent on the
type of data used for training (i.e., apps categories, ratio benign on
malicious apps, and apps release dates) and is prone to obfuscation techniques
(see Section 6.3) employed by malware apps. Overall, these techniques focused
on sensitive API calls and privileged permissions that often lead to high
false positives: a large number of benign apps often use sensitive API calls
and request permissions for certain functionalities thus they are wrongly
classified as malware. Moreover, these solutions seldom detect obfuscated
malware components in apps, resulting in poor performance. Zhang et al., [33]
used weighted graph models, extracted from Android apps’ codes semantics, to
quantify the similarities among malware apps. In contrast, we used metrics
derived from weight directed graphs to differentiate among benign and malware
apps. To analyze malicious software in desktop computing platform, GZero [29]
collected the call sequences of software executables to build graph theoretic
features. In the same spirit, in this work, we extracted an extended set of
graph features and used showed the efficacy of graph theoretic metrics in
classifying benign and malware apps. Moreover, we evaluate the robustness of
our proposed scheme against unbalanced datasets as well as shown its
resiliency against several type obfuscation techniques.

##  8 CONCLUSION

We presented DaDiDroid, an obfuscation resilient tool to detect Android
malware based on modeling the API calls as a weighted, directed graph. We
evaluated the effectiveness of DaDiDroid with several datasets and tested its
robustness against different types of obfuscations. We shown that DaDiDroid
classify up to 96.5% of benign and malicious apps. In worst case, when no
obfuscated apps in training set and testing set contain all obfuscated apps
(i.e., apps “Encoding” obfuscation technique), DaDiDroid achieved 91.2% of
accuracy with only 17.3% of false negative rate and 4.5 false positive rate.
Moreover, DaDiDroid use small features vectors which can be customized with
more or less features from the graph theory and even the extraction process
depending on the context of the classification. We compared DaDiDroid to
MaMaDroid [24], a Markov chain modeling tool for Android apps, showing that
beside achieving similar high results on common datasets, DaDiDroid is much
more resilient to changes in the datasets and especially to obfuscation
techniques. In the future we plan to improve DaDiDroid by complementing
features derived from dynamic runtime analysis of apps.

#### Acknowledgments

This work was partially supported by research grants from Macquarie University
Deputy Vice-Chancellor Research (MQ-DVCR) and Optus Macquarie University Cyber
Security Hub (OMUCSH). Any opinions, findings, and conclusions or
recommendations expressed in this material are those of the authors or
originators and do not necessarily reflect the views of the MQ-DVCR or of the
OMUCSH. The authors would like to thank Minhui (Jason) Xue and the anonymous
reviewers for their constructive feedback on the preparation of the final
version of this paper.

## REFERENCES

  * [1] Y. Aafer, W. Du, and H. Yin.  Droidapiminer: Mining api-level features for robust malware detection in android.  In ICSPCS. Springer, 2013.
  * [2] A. Andoni and P. Indyk.  Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions.  Communications of the ACM, 2008.
  * [3] Archive.  Playdrone apk’s : Free software : Free download, borrow and streaming : Internet archive.  https://archive.org/details/playdrone-apks, 2019.
  * [4] D. Arp, M. Spreitzenbarth, M. Hubner, H. Gascon, K. Rieck, and C. Siemens.  Drebin: Effective and explainable detection of android malware in your pocket.  In NDSS, 2014.
  * [5] S. Arzt, S. Rasthofer, C. Fritz, E. Bodden, A. Bartel, J. Klein, Y. Le Traon, D. Octeau, and P. McDaniel.  Flowdroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for android apps.  In PLDI. ACM, 2014.
  * [6] L. Breiman.  Random forests.  Machine Learning, 2001.
  * [7] I. Burguera, U. Zurutuza, and S. Nadjm-Tehrani.  Crowdroid: behavior-based malware detection system for android.  In WSPSMD, pages 15–26. ACM, 2011.
  * [8] S. Chen, M. Xue, Z. Tang, L. Xu, and H. Zhu.  Stormdroid: A streaminglized machine learning-based system for detecting android malware.  In CCS, 2016.
  * [9] A. Continella, Y. Fratantonio, M. Lindorfer, A. Puccetti, A. Zand, C. Kruegel, and G. Vigna.  Obfuscation-resilient privacy leak detection for mobile apps through differential analysis.  In NDSS, 2017.
  * [10] T. M. Cover and J. A. Thomas.  Elements of information theory.  John Wiley & Sons, 2012.
  * [11] S. Dong, M. Li, W. Diao, X. Liu, J. Liu, Z. Li, F. Xu, K. Chen, X. Wang, and K. Zhang.  Understanding android obfuscation techniques: A large-scale investigation in the wild.  arXiv preprint arXiv:1801.01633, 2018.
  * [12] W. Enck, P. Gilbert, S. Han, V. Tendulkar, B.-G. Chun, L. P. Cox, J. Jung, P. McDaniel, and A. N. Sheth.  Taintdroid: an information-flow tracking system for realtime privacy monitoring on smartphones.  In TOCS, 2014.
  * [13] J. Garcia, M. Hammad, B. Pedrood, A. Bagheri-Khaligh, and S. Malek.  Obfuscation-resilient, efficient, and accurate detection and family identification of android malware.  Department of Computer Science, George Mason University, Tech. Rep, 2015.
  * [14] E. Girault.  Google Play Unofficial Python API.  https://github.com/egirault/googleplay-api, 2019.
  * [15] Google.  Google Play Store.  https://play.google.com, 2019.
  * [16] Google.  Package Index (APIv26) — Android Developers.  https://developer.android.com/reference/packages.html, 2019.
  * [17] M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, and I. H. Witten.  The weka data mining software: an update.  ACM SIGKDD Explorations, 2009.
  * [18] P. Hornyack, S. Han, J. Jung, S. Schechter, and D. Wetherall.  These aren’t the droids you’re looking for: Retrofitting android to protect data from imperious applications.  In CCS, 2011.
  * [19] M. Ikram and M. A. Kaafar.  A first look at mobile ad-blocking apps.  In Network Computing and Applications (NCA). IEEE, 2017.
  * [20] M. Ikram, N. Vallina-Rodriguez, S. Seneviratne, M. A. Kaafar, and V. Paxson.  An analysis of the privacy and security risks of android vpn permission-enabled apps.  In IMC, 2016.
  * [21] R. Kohavi and D. Sommerfield.  Feature Subset Selection Using the Wrapper Method: Overfitting and Dynamic Search Space Topology.  In KDD, 1995.
  * [22] M. Lindorfer, M. Neugschwandtner, and C. Platzer.  Marvin: Efficient and comprehensive mobile app classification through static and dynamic analysis.  In COMPSAC, 2015.
  * [23] C. Mann and A. Starostin.  A framework for static detection of privacy leaks in android applications.  In ASAC, 2012.
  * [24] E. Mariconti, L. Onwuzurike, P. Andriotis, E. De Cristofaro, G. Ross, and G. Stringhini.  MaMaDroid: Detecting Android Malware by Building Markov Chains of Behavioral Models.  In NDSS, 2017.
  * [25] McAfee.  McAfee Labs Threat Report.  https://www.mcafee.com/au/resources/reports/rp-quarterly-threats-sept-2017.pdf, 2017\.
  * [26] K.-R. Müller, S. Mika, G. Rätsch, K. Tsuda, and B. Schölkopf.  An Introduction to Kernel-based Learning Algorithms.  IEEE ToNE, 12(2), 2001.
  * [27] B. Schölkopf, J. C. Platt, J. C. Shawe-Taylor, A. J. Smola, and R. C. Williamson.  Estimating the support of a high-dimensional distribution.  Neural Computation, 2001.
  * [28] P. Schulz.  Code protection in android.  In Rheinische Friedrich-Wilhelms-Universitat Bonn, Germany, 2012\.
  * [29] Z. Shafiq and A. Liu.  A graph theoretic approach to fast and accurate malware detection.  In IFIP Networking, 2017.
  * [30] R. Vallée-Rai, P. Co, E. Gagnon, L. Hendren, P. Lam, and V. Sundaresan.  Soot - a java bytecode optimization framework.  In CASCON, 1999.
  * [31] N. Viennot.  Github-nviennot/playdrone: Google play crawler, 2014.
  * [32] VirusTotal.  VirusTotal.  https://www.virustotal.com, 2019.
  * [33] M. Zhang, Y. Duan, H. Yin, and Z. Zhao.  Semantics-aware android malware classification using weighted contextual api dependency graphs.  In CCS, 2014.

Feature |  Description
---|---
Graph Size |  Denotes number of edges (i.e., relationships) of a node (i.e., API or family) in a graph.
Graph Order |  Corresponds to the number nodes in a graph.
Number of Cycles |  A cycle is a path of edges and vertices wherein a vertex is reachable from itself.
Degree Assortativity Coefficient |  In a Directed graph, in-assortativity and out-assortativity measure the tendencies of nodes to connect with other nodes that have similar in and out degrees as themselves, respectively. To compute this feature we use the Pearson correlation approach which is way faster and provide representative results. Positive values of assortivity coefficient, $r$, indicates a correlation between nodes of similar degree, while negative values indicate relationships between nodes of different degree. In general, $r$ lies between $-1$ and $1$. When $r$ = $1$, the network is said to have perfect assortative mixing patterns, when $r$ = $0$ the network is non-assortative, while at $r$ = $-1$ the network is completely disassortative.
Strongly Connected Components |  The number of strongly connected components. A vertex $v_{i}$ is said to be strongly connected if it is reachable from every other vertex $v_{k}$.
Weakly Connected Components |  A weakly connected component is a maximal subgraph of a directed graph such that for every pair of vertices $(u,v)$ in the subgraph, there is an undirected path from $u$ to $v$ and a directed path from $v$ to $u$.
Node Connectivity |  The node connectivity is the minimum number of nodes that must be removed to disconnect $G$.
Avg. Shortest Path Length |  Average shortest path length is a concept in network topology that is defined as the average number of steps along the shortest paths for all possible pairs of network nodes.
Degree Centrality |  The degree centrality a vertex $v_{i}$ is the fraction of nodes it is connected to.
Betweenness Centrality |  Measures the fraction of all pair shortest paths, except those originating or terminating at it, that pass through it, $\frac{2I(P_{jk},i)}{|V|(|V|-1)}$, where $P_{jk}$ denote the shortest path from vertex $v_{j}$ to vertex $v_{k}$, $P_{jk}$ = $(v_{j},v_{l},v_{m},v_{n},...,v_{k})$ and $I(P_{jk},i)=1$ if $v_{i}$ $\in$ $P_{jk}$ otherwise $I(P_{jk},i)=0$ when $v_{i}$ $P_{jk}$.
Vitality |  Closeness vitality of a node is the change in the sum of distances between all node pairs when excluding that node.
Attracting Components |  An attracting component in a directed graph G is a strongly connected component with the property that a random walker on the graph will never leave the component, once it enters the component.
Graph Density |  It measures number of edges of graph is close to the maximum number of edges.
Clustering coefficient |  It is a measure of the degree to which nodes in a graph tend to cluster together.
Algebraic connectivity |  The algebraic connectivity (also known as Fiedler value or Fiedler eigenvalue) of a graph $G$ is the second-smallest eigenvalue of the Laplacian matrix of $G$. This eigenvalue is greater than 0 if and only if $G$ is a connected graph. This is a corollary to the fact that the number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph.
Clique Number |  It corresponds to the size (number of vertices $V$) of the largest clique of the graph. A clique $C$ in an undirected graph is a subset of the vertices such that every two distinct vertices are adjacent.
Biconnected Components |  They are maximal subgraphs such that the removal of a node (and all edges incident on that node) will not disconnect the subgraph.
Diameter |  The diameter of a graph is the maximum eccentricity of any vertex in the graph. The eccentricity $\epsilon(v)$ of a graph vertex $v_{i}$ in a connected graph $G$ is the maximum graph distance between $v_{i}$ and any other vertex $v_{j}$ of $G$.
Radius |  The radius $r$ of a graph $G$ is the minimum eccentricity of any vertex.
Center Number |  The center is the set of nodes with eccentricity equal to radius, $r$.
Periphery Number |  The periphery is the set of nodes with eccentricity equal to the diameter.

Table 4: List of our graph metrics (or features) to quantify the relationship
among API calls as well API families.


# Biosignature Line Ratios of [P II] in Exoplanetary and Nebular Environments

Kevin Hoy1, Sultana N. Nahar1, Anil K. Pradhan1,2,3
1 Department of Astronomy, 2 Chemical Physics Program, 3 Biophysics Graduate
Program, The Ohio State University, Columbus, OH 43210, USA

(Accepted xxxxxx Received xxxxxx; in original form xxxxxx)

###### Abstract

Being the backbone element of DNA, phosphorus is a key component in the search
for life in the Universe. To aid in its detection, we present line emissivity
ratios for the five lowest-lying forbidden [P II] transitions, namely those
among the levels
$3s^{2}3p^{2}(^{3}P_{0},^{3}P_{1},^{3}P_{2},^{1}D_{2},^{1}S_{0})$. The
wavelengths range between 0.44-70 $\mu$m , and several lie within the
spectroscopic domain observable with the James Webb Space Telescope (JWST).
These line ratios have been calculated using a new collisional-radiative-
recombination (CRR) model combining calculated collision strengths and level-
specific recombination rate coefficients; with both datasets computed using
the accurate Breit-Pauli R-Matrix method. The CRR model includes a new scheme
for (e + ion) recombination to emission line formation. We compare its effect
to models incorporating only electron impact excitation and spontaneous
radiative decay. We find that (e + ion) recombination has a significant impact
on all line ratios, and represents a major improvement in physical accuracy of
emission line models.

###### keywords:

ISM: atoms ¡ Interstellar Medium (ISM), Nebulae, ISM: supernova remnants,
Physical Data and Processes, atomic processes, astrobiology, infrared:
general, exoplanets

††pagerange: Biosignature Line Ratios of [P II] in Exoplanetary and Nebular
Environments–Data Availability††pubyear: 2022

##  1 Introduction

Phosphorus could be of key importance in the search for life in the Universe.
As the backbone element of DNA, it could be a fundamental prerequisite for the
formation of life. It is thus of keen interest to perform theoretical
calculations that can provide a basis of comparison for real observations of
exoplanets. In order to determine if phosphorus is present in an observed
exoplanet, we must first understand the elements spectral signature. To that
end, it is necessary to build an accurate model of as many physical processes
that influence the emission spectrum of phosphorus as possible.

Previous studies on phosphorus abundance have been confined to ionized sources
such as nebulae (Pottsch et al. 2008, Pottasch and Bernard-Salas 2008, Otsuka
et al. 2011), and FGK dwarf stars (Maas et al. 2017). The former are
associated with star-forming regions, and the latter are potential sources for
Earth-like extra-solar planets. Nucleosynthesis leading to phosphorus (Z=15)
production can occur in AGB stars, but mainly in supernovae by neutron capture
with silicon (Z=14). Koo et al. (2013) analyzed the P/Fe abundance ratio in
the supernova remnant Cassiopia A using forbidden P ii 1.189 $\mu$m line and
Fe ii 1.257 $\mu$m lines to deduce about 100 times the average ratio in the
Milky Way. Otherwise, phosphorus abundances are generally low in solar system
$2.6\times 10^{-7}$ by number relative to hydrogen (Asplund et al. 2009).
Also, its gas phase abundance is difficult to determine due to dust and grain
formation since phosphorus is very reactive.

Of all biosignature elements H, C, N, O, P and S, atomic data for P-ions is
the least available, except a limited number of energies from the National
Institute for Standards and Technology (NIST), theoretial photoionization and
(e + ion) recombination data (Nahar 2016, 2017), experimental measurements and
comparison with theory for P ii (Hernandez et al. 2015, Nahar et al. 2017),
and collision strengths for P iii (Naghma et al. 2018). With the aim of more
comprehensive analysis of observational data, we compute the relevant atomic
parameters and line intensity ratios for P ii . In particular, we study lines
that might be detectable with JWST in the NIR range 0.6-28 $\mu$m . The
primary focus of this work is the description of a major improvement to
modelling emission lines by the inclusion of detailed and accurate (e + ion)
recombination contribution to forbidden lines from recombination-cascades via
high-lying levels up to $n\leq 10$, and its application to the modelling of P
ii emission. Generally, we consider collisional-radiative models wherein
electron impact excitation is the primary means of populating low-lying
excited levels which produce forbidden emission lines. In this work, we
generalize the model to a collisional-radiative-cascade (CRR) model in which
(e + ion) recombination followed by myriad radiative pathways significantly
populate upper levels. This additional contribution yields considerable change
in level populations and line emissivities, demonstrating the importance of
utilizing models with (e + ion) recombination and radiative cascades. The
treatment described is generally applicable to modeling atomic spectra.

##  2 Theory & Computational Method

A theoretical description of key atomic parameters is outlined here.

###  2.1 Energy Levels & Einstein A Coefficients

In order to calculate the necessary energy levels and Einstein A-coefficients
for spontaneous radiative decays, we have employed the atomic structure code
SUPERSTRUCTURE (Eissner et al. 1974). The code operates using the Breit-Pauli
approximation, and produces fine structure level energies and associated
radiative transition rates. Figure 1 presents the Grotrian energy level
diagram for the 5 lowest fine structure levels of P ii . All levels presented
are within the ground configuration $1s^{2}2s^{2}3s^{2}3p^{2}$. The energy
difference between the ground state ${}^{3}P_{0}$ and the highest level
${}^{1}S_{0}$ is about 0.2 Ryd or 2.72 eV. All levels are of even parity, thus
all transitions between them and discussed in this work are forbidden due to
electric quadrupole E2 and magnetic dipole M1 second order relativistic
interactions.

Figure 1: Energy diagram of P ii showing the fine structure levels in the
ground configuration $3s^{2}3p^{2}$, and a few transitions in the JWST
wavelength range.

###  2.2 Electron Impact Excitation

When considering the effects of of Electron Impact Excitation there are two
quantities to consider. First, the collision strengths which are related to
the probability and cross section as function of energy of an incident
electron at a given energy E causing an excitation from a given initial level
$i$ to a final level $j$. For astrophysical plasma sources we generally assume
a Maxwellian distribution of electron energies correspnding to a given
electron kinetic temperature $T_{e}$. Therefore, for calculating line
emissivity ratios, we compute and employ Maxwellian averaged effective
collision strength $\Upsilon(T_{e})$ at a range of $T_{e}$ characteristic of
the source, and that is related to the rate at which a given transition is
collisionally excited,

$\Upsilon_{ij}(T_{e})=\int_{0}^{\infty}\Omega_{ij}(E)\exp(-E/kT_{e})d(E/kT_{e}).$
(1)

Here, $\Omega_{ij}(E)$ is the collision strength for the transition
$i\rightarrow j$; $k$ is the Boltzman constant. Fig. 2 shows a sample of
computed collision strengths and effective collision strengths. As seen,
collision strengths demonstrate extensive resonance structures which make them
highly dependent on electron energy, while effective collision strengths are
slowly varying with $T_{e}$, also implying that slight errors in temperature
have a less significant impact on any derived result.

Effective collision strengths have been calculated for the 67 lowest lying P
ii levels. We also compare the computed line ratios from the present CRR model
using previously calculated P ii collision strengths (Tayal 2004). We have
employed level-specific recombination rate coefficients (Nahar 2017a, 2017b)
for 243 levels. For levels not included in the models the effective collision
strengths are set to zero. The inclusion of many more levels for (e + ion)
recombination-cascades should offset the insignficant loss of accuracy from
omitting the electron impact excitation to higher levels.

###  2.3 Electron-ion recombination

The contribution of recombination is contained in two key parameters,
recombination rate coefficients and cascade coefficients. Level-specific
recombination rates refer to electron recombining with an ion, in this case P
iii to form P ii in an excited state. They are defined by Eq. 2, where gj is
the statistical weight factor of the final state of the ion being recombined,
gs is the statistical weight of the initial state of the recombining ion, k is
the Boltzmann constant, T is the temperature of the plasma, m is the mass of
the electron, c is the speed of light, $\epsilon$ is the energy of the
incident electron, and $\sigma_{PI}(\epsilon,j$) is the photoionization cross
section a given electron energy. The Milne relation gives the level-specific
rate coefficient into level $j$ as:

$\displaystyle\alpha_{R}(j,T)$ $\displaystyle=$
$\displaystyle\frac{g_{j}}{g_{s}}\frac{2}{kT\sqrt{2\pi
m^{3}c^{2}kT}}\int_{0}^{\infty}(I+\epsilon)^{2}\sigma_{PI}(\epsilon,j)e^{\frac{-\epsilon}{kT}}d\epsilon$
$\displaystyle=$ $\displaystyle 1.8526\times
10^{4}\frac{g_{j}}{g_{s}}\int_{0}^{\infty}(\epsilon+I)^{2}e^{\frac{-\epsilon}{kT}}\sigma_{PI}(\epsilon,j)d\epsilon\>cm^{3}s^{-1}.$

The cascade coefficients Cji are calculated from BPRM A-values and used to
obtain the fractional contribution $j\rightarrow i$ due to (e + ion)
recombination into an upper level $j$ to a lower level $i$. The Cji take into
account all spontaneous radiative decays via dipole E1 transtions through
intermediate levels $k$ such that $i<k<j$ as follows,

$C_{ji}=\frac{A_{ji}}{\sum_{i^{\prime}<j}A_{ji^{\prime}}}+\sum_{k>i}C_{jk}\frac{A_{ki}}{\sum_{i^{\prime}<k}A_{ki^{\prime}}}$
(3)

The A-values are the only necessary quantities for calculating cascade
coefficients; C${}_{j}k$ are subsets of intermediate cascade coefficients, and
combining these we obtain the total effective recombination contribution to a
given level population.

###  2.4 Line Emissivities & Ratios

Combining the results above we obtain line emissivity ratios from CRR models.
The theoretical line emissivity is the amount of energy per unit time per unit
volume for a given transition. For a given P ii transition $j\rightarrow i$ it
may be expressed as,

$I([PII];\lambda_{ji})=\frac{h\nu_{ji}A_{ji}}{4\pi}\times\frac{N_{j}}{\sum_{k}N_{k}}\times\frac{n(PII)}{n(P)}$
$\times\frac{n(P)}{n(H)}\times n(H)\;erg\;cm^{-3}\;s^{-1}.$ (4)

$N_{j}$ refers to the population of the upper state. Summation over $N_{k}$
refers to the total population of all levels included in the calculation, and
n(P ii )/n(P) is the density ratio relative to phosphorus abundance P/H. In
order to obtain line emissivities form Eq. 4 one needs ionization fractions P
ii /P in the plasma source at the appropriate temperature and density, which
are generally unknown a priori and are model dependent. We compute line ratios
in a temperature-density range of exoplanetary ionospheres as

$\frac{I(PII;\lambda_{ji})}{I(PII;\lambda_{mn})}=\frac{N_{j}A_{ji}\nu_{jk}}{N_{m}A_{mn}\nu_{mn}},$
(5)

for any two transitions $j\rightarrow i$ and $m\rightarrow n$. The ratio in
Eq. 5 eliminates the number density factors and instead leaves only the
relative population factor, Einstein A values, and energies of the two
transitions being considered. The key quantities here are relative populations
of upper levels computed by our CRR models.

###  2.5 Code SPECTRA

These results have been produced by a new version of the code SPECTRA,
employed in many past calculations of line ratios. Previously, the code
considered electron impact excitation and photoexcitation for populating
excited levels. The updated version accounts for (e + ion) recombination as
described. Moreover, the new code is written in C++ rather than Fortran which
increases its utitliy, efficiency, and portability.

The computational work was performed in two distinct stages. First, there was
a direct unaltered translation from Fortran to C++. During this stage, the
primary goal was to produce matching results with identical input data to many
significant figures. The second stage included the recombination-cascade
formalism described herein. As there are no previous results to compare with,
extensive testing was performed and checked several different ways (including
manually) to ensure accuracy and reliability for modelling emission lines with
recombination contributions in general.

##  3 Results and discussion

The main results presented are the newly calculated collision strengths,
Maxwellian-averaged effective collision strengths, and line emissivity ratios.
The former two have been computed for all transitions among the first 67 P ii
levels, with a small sample of select results presented in table 1, and shown
in Fig. 2 for two transitions ${}^{3}P_{1}-^{1}D_{2}$ and
${}^{3}P_{1}-^{1}S_{0}$ at wavelengths 8751$\AA$ and 4413$\AA$, respectively.
The emissivity ratios are presented in Figures 3 & 4.

###  3.1 Effective Collision Strengths

The collision strengths and effective collision strengths for two select
transitions can be seen in Figure 2. The strong resonant structures in the
former are clearly visible, as is the signature smoothing of the effective
collision strengths.

Figure 2: Collision Strengths vs. E(Ryd) (upper panels), and Maxwellian
averaged effective collision strengths vs. Log T(K) (lower panels) for
${}^{3}P_{1}-^{1}D_{2})$ (left) and ${}^{3}P_{1}-^{1}S_{0})$ (right). The
Collision strengths are dominated by autoionizing resonances in the near-
threshold energy region, whereas the effective collision strengths vary
smoothly with temperature but strongly peaked around $10^{4}$K.

The temperature dependence of effective collision strengths due to
autoionizing resonances is quite pronounced, and is different from that of (e
+ ion) recombination. The competition between the two processes populating
upper levels and leads to very different line emissivity ratios.

###  3.2 Line Emissivity Ratios

Line ratios for select transitions among the first 5 P ii levels can be seen
in Figure 3. The key features to note are the differences among the three
independent curves in each plot with inclusion of (e + ion) recombination and
without. We find a large increase with (e + ion) recombination-cascades in the
CRR model (red curves), and much lower emissivity ratios without (blue and
black curves) using our newly calculated collision strengths and earlier work
by Tayal (2004), respectively. Although the two sets of collision strengths
data yield practically the same values at low densities $N_{e}<10^{5}$ cm-3,
the differences increase at higher densities. That is owng to collisional
coupling among the 5 levels which becomes more prominent and manifested in
line ratios. Tayal’s collision strengths are higher than present ones for
excitation of upper levels considered and yield higher line ratios at
$N_{e}>10^{5}$ cm-3; those would be even higher if (e + ion) recombination is
included. This illustrates not only a significant improvement in accuracy
using the CRR model, but also that (e + ion) recombination using detailed and
precise level-specific recombination rates should be used as basis of
comparison with observed emission-line spectra.

Figure 3: [P ii ] line emissivity ratios as function of temperature and
density demonstrating the effects of newly calculated collision strengths and
the incorporation of (e + ion) recombination-cascades. The red curve
represents results including recombination and present collision strengths.
The black and blue curves are calculated without recombination using present
collision strengths (blue) and those from Tayal (2004; black), respectively.

Figure 4 includes line ratios for select transitions whose wavelengths are
within JWST spectrographic instrumental range 0.6-28$\mu$m at the three
different temperatures. However, in this case the upper level $1D_{2}$ is the
same for all ratios and therefore line emissivities depend only on the
respective A-values, and to a smaller extent on the energy differences. The
A-values for the three transitions $1D_{2}\rightarrow 3P_{0,1,2}$ are:
$2.177\times 10^{-5},\ 6.744\times 10^{-3},\ 1.938\times 10^{-2}$ sec-1,
respectively. Therefore, the proportion of line ratios 0.898$\mu$m/0.890$\mu$m
and 0.875$\mu$m/0.890$\mu$m due to ${}^{1}D_{2}-^{3}P_{2}$/${}^{1}S_{0}$ and
${}^{1}D2-^{3}P_{1}$/${}^{1}S_{0}-^{1}D2$ remains approximately constant 3:1
(modulo the small energy differences). Again, we find large differences upon
inclusion of recombination-cascade contributions to emission lines owing to
upper levels being populated predominantly by (e + ion) recombination rather
than excitation due to electron impact.

As the electron density increases above $N_{e}>10^{4}$ cm$-3$, recombination-
cascades are relatively less important compared to electron collisions and the
two curves are eventually seen to converge at high densities, though the
proporation remains the same as it should owing to origin of line emissivity
from a single upper level. We note in passing that there are several
transitions orginating from the same level ${}^{1}D_{2}$ where the line ratios
show similar behavior and are constant across temperatures and densities since
only the upper level’s population is sensitive to either and present in both
numerator and denominator. As such line ratios depend only on ratios of
A-values and energy differences, and provide a an accuracy check on input
data.

Figure 4: Emissivity ratios of [P ii ] lines at ionospheric and nebular
temperatures 500K, 1000K, and 10,000K lying within and potentially observaby
by JWST spectrometers.

Line emissivities for [P ii ] transitions within the ground configuration are
computed using two sets of collision strengths of data, computed as part of
the present work as as previously reported in literature (Tayal 2004).
Although the line ratios are in good agreement, they differ significantly; the
new values should be more accurate. The CRR models can be further improved by
the consideration of fluorescent excitation due to an external source of
radiation, namely the planet’s host star. SPECTRA maintains the ability to
account for that process and can incorporate that mechanism, though it is
likely to be much smaller than electron excitation and (e + ion)
recombination-cascade processes for forbidden line formation.

Table 1: Effective Maxwellian averaged collision strengths for select transitons in P ii $N_{e}(cm^{-3}$) | ${}^{3}P-^{1}D$ | ${}^{3}P-^{1}D$ | ${}^{3}P-^{1}D$ | ${}^{1}D-^{1}S$ |  $N_{e}(cm^{-3}$) | ${}^{3}P-^{1}D$ | ${}^{3}P-^{1}D$ | ${}^{3}P-^{1}D$ | ${}^{1}D-^{1}S$
---|---|---|---|---|---|---|---|---|---
J-J’ | 0-2 | 1-2 | 2-2 | 2-0 | J-J’ | 0-2 | 1-2 | 2-2 | 2-0
$\lambda$ | 8862.6 $\AA$ | 4441.7 $\AA$ | 2916.7 $\AA$ | 1571.2 $\AA$ | $\lambda$ | 8862.6 $\AA$ | 4441.7 $\AA$ | 2916.7 $\AA$ | 1571.2 $\AA$
2.0 | 5.04(-1) | 1.40(-1) | 2.97(-3) | 2.01(-56) | 3.6 | 6.11(-1) | 1.693 | 2.552 | 2.91(-2)
2.1 | 5.07(-1) | 2.23(-1) | 1.20(-2) | 5.29(-45) | 3.7 | 6.19(-1) | 1.740 | 2.683 | 5.77(-2)
2.2 | 5.10(-1) | 3.39(-1) | 3.62(-2) | 6.23(-36) | 3.8 | 6.27(-1) | 1.781 | 2.798 | 1.01(-1)
2.3 | 5.12(-1) | 4.63(-1) | 8.73(-2) | 1.00(-28) | 3.9 | 6.34(-1) | 1.822 | 2.902 | 1.59(-1)
2.4 | 5.14(-1) | 5.94(-1) | 1.76(-1) | 5.29(-23) | 4.0 | 6.45(-1) | 1.866 | 3.005 | 2.32(-1)
2.5 | 5.16(-1) | 7.23(-1) | 3.06(-1) | 1.86(-18) | 4.1 | 6.57(-1) | 1.915 | 3.113 | 3.21(-1)
2.6 | 5.17(-1) | 8.47(-1) | 4.77(-1) | 7.62(-15) | 4.2 | 6.72(-1) | 1.972 | 3.228 | 4.25(-1)
2.7 | 5.20(-1) | 9.61(-1) | 6.78(-1) | 5.64(-12) | 4.3 | 6.89(-1) | 2.031 | 3.343 | 5.41(-1)
2.8 | 5.23(-1) | 1.065 | 8.99(-1) | 1.07(-9) | 4.4 | 7.03(-1) | 2.084 | 3.444 | 6.65(-1)
2.9 | 5.28(-1) | 1.160 | 1.129 | 6.94(-8) | 4.5 | 7.11(-1) | 2.117 | 3.511 | 7.89(-1)
3.0 | 5.36(-1) | 1.250 | 1.362 | 1.91(-6) | 4.6 | 7.10(-1) | 2.119 | 3.524 | 9.00(-1)
3.1 | 5.47(-1) | 1.337 | 1.593 | 3.00(-5) | 4.7 | 6.95(-1) | 2.081 | 3.469 | 9.91(-1)
3.2 | 5.60(-1) | 1.421 | 1.817 | 2.20(-4) | 4.8 | 6.66(-1) | 2.000 | 3.340 | 1.050
3.3 | 5.75(-1) | 1.501 | 2.030 | 1.14(-3) | 4.9 | 6.25(-1) | 1.879 | 3.143 | 1.071
3.4 | 5.89(-1) | 1.574 | 2.226 | 4.31(-3) | 5.0 | 5.73(-1) | 1.725 | 2.890 | 1.054
3.5 | 6.01(-1) | 1.638 | 2.400 | 1.24(-2) |  |  |  |  |

##  4 Conclusion

The computed data and results are useful for both temperature/density
diagnostics and possible detection of phosphorus in astrophysical sources,
particularly exoplanetary ionosopheres as biosignatures or precursors of DNA-
based life forms. Line emissivity ratios and new collision strengths for P ii
are computed for comparison with observation and diagnostics. The inclusion of
(e + ion) recombination has a large impact on forbidden line emissivities, and
considerably improve the physical accuracy of models. Many transitions, with a
sample of results presented, occur within the 0.6-28.3 $\mu$m range of the
spectrometers aboard JWST. Given the sensitivity of JWST, these emission lines
might be present in the spectra of exoplanets that have detectable amounts of

Future work will involve a more complete CRR modelling of resultant spectrum
with SPECTRA involving emission and absorption processes. This entails user
input of ionization fractions and abundances to produce individual line
emissivities, in addition to line ratios. Data from this new code can then be
combined with codes for a full-scale modelling of planetary atmospheres, such
as a new version of the code GEANT4-EXOP code in progress (M. Rothman, private
communication). These models will include atomic-ionic-molecular data as input
to produce absorption and emission spectra of other biosignature elements.

## Acknowledgments

The computational work was carried out at the Ohio Supercomputer Center in
Columbus Ohio.

## Data Availability

All data underlying the results presented are available publicly from the
online database Nahar-OSU-Atomic-Radiative-Data (NORAD), maintained by co-
author S.N. Nahar at the Department of Astronomy of the Ohio State University
from the website https://norad.astronomy.ohio-state.edu.

## References

  * Asplund (2009) Asplund, M., Grevesse, N., Jacques Sauval, A. and Scott, P., 2009, Ann. Rev. Astron. Astrophys. 209, 47
  * Blum (1991) Blum, R. D. and Pradhan, A. K., 1991, Phys. Rev. A 44, 6123
  * Burke (2011) Burke, P.G., R-Matrix Theory of Atomic Collisions, 2011, Springer
  * Ganas (1998) Ganas, P. S., 1998, Eur. Phys. J. D-1, 165
  * Hernández (2015) L. Hernández a, A.M. Covington b, E.M. Hernández a,d, A. Antillón a, A. Morales-Mori a, Kiattichart Chartkunchand b, A. Aguilar c, G. Hinojosa, JQSRT 159, July 2015, Pages 80-86
  * Maas (2017) Maas, Z. G., Pilachowski, C. A. and Cescutti, G., 2017, Astrophys. J. 841, 108
  * Nahar (2017) Nahar, S. N. et al. , JQSRT 187, 215 (2017)
  * Nahar (2017) Nahar, S. N., Mon. Not. R. astr. Soc. 469, 3225 (2017a)
  * Nahar (2017) Nahar, S. N., New Ast 50, 19 (2017b)
  * Naghma (2018) Naghma, R., Nahar, S. N., Pradhan, A. K., Mon. Not. R. astr. Soc. 479, L60 (2018)
  * Otsuka (2011) Otsuka, M., Mexner, M., Riebel, D., Hyung, S., Tajitsu, A. and Izumiura, H., 2011, Astrophys. J. 729, 39
  * Peng (1994) Peng, J. and Pradhan, A. K., 1994, Astrophys. J. Lett. 432, L123
  * Pottasch (1999) Pottasch, S. R. and Beintema, D. A., 1999, Astron. Astrophys. 347, 975
  * Pottasch (2008) Pottasch, S. R., Bernard-Salas, J. and Roelig, T. L., 2008, Astron. Astrophys. 481, 393
  * Pottasch (2008) Pottasch, S. R. and Bernard-Salas, J., 2008, Astron. Astrophys. 490, 715
  * Pradhan (2011) Pradhan, A. K. and Nahar, S. N., 2011, Atomic Astrophysics and Spectroscopy, Cambridge University Press
  * Wang (2016) Wang, H., Jiang, G. and Duan, J., 2016, Eur. Phys. J. D 70, 122


# Pushing the Limit of Range Resolution Beyond Bandwidth Constraint with
Triangle FMCW

Yanbo Zhang Yanbo Zhang, is with Nanyang Technological University, 50 Nanyang
Avenue, Singapore 639798 (e-mail<EMAIL_ADDRESS>
###### Abstract

This paper proposes a novel signal processing technique that doubles the range
resolution of FMCW (Frequency Modulated Continuous Wave) sensing without
increasing the required bandwidth. The proposed design overcomes the
resolution limit imposed by bandwidth by exploiting the phase consistency
observed in the special frequency variation of the beat signal derived from
triangle FMCW. Through this approach, the resolution is doubled while
maintaining high spectrum SNR. A system model for signal processing is
presented, and the energy distribution of the derived beat spectrum is
analyzed. The effectiveness of the proposed technique is validated through
model-based simulations.

###### Index Terms:

FMCW waveform, wireless ranging, time resolution, spectral analysis,
simulation

##  I Introduction

FMCW (Frequency Modulated Continuous Wave) technique has found wide
applications in wireless sensing such as target localization [1, 2, 3],
gesture recognition [4, 5, 6, 7], fall detection [8, 9, 10] and vital signal
monitoring [11, 12, 13]. The performance of such systems is primarily
determined by the ranging resolution of FMCW – the capability of separating
reflected signals with minimal range difference. To improve the resolution,
conventional methods rely on the common belief between range resolution and
bandwidth, by either linearly extending an FMCW symbol or increasing the
linear slope of frequency variation. Both methods lead to increased usage of
frequency bandwidth, which is however limited by available spectrum resource
in practice.

In this paper, we present a novel signal processing design for FMCW radar that
improves the range resolution without requiring increased bandwidth. The
design is based on the observation of distinct frequency variation
characteristics of the beat signal derived from triangle FMCW. Specifically,
we find that the frequency variation of the beat signal contains distinct
symmetry and continuity – in corresponding with the rising ramp and falling
ramp of a triangle waveform, the frequency of the two parts of the beat signal
is symmetric with respect to DC, and the frequency transition between these
two parts is linear and continuous. These characteristics of frequency
variation also translate to similar continuity and symmetry in the phase
variation of the beat signal, as the signal phase is the time integral of
frequency. Further analysis indicates that these properties result in
remarkable consistency of the real part of the beat signal throughout the
entire symbol duration, which we refer to as phase consistency. Through
simulations, we demonstrate that such properties are unique in beat signals
generated from triangle FMCW, and are not present when using other repetitive
or extended signals such as repeated upchirps (sawtooth). Leveraging the phase
consistency, we devise an efficient signal processing method that improves the
range resolution without increasing the bandwidth. The effectiveness of our
approach is demonstrated with rigorous theoretic analysis and real-world
experimental validation.

In the literature, researchers have been trying to achieve higher range
resolution with given bandwidth limit by designing complex signal processing
technique. In [14], the authors propose to utilize a similar triangle FMCW to
achieve improved range resolution. However, the proposed method does not
specifically handle the phase discontinuity of the complex beat signal, which
makes it difficult to extract the actual beat frequency from the side lobes
due to the spectrum leakage, limiting its effectiveness in multi-target
scenarios. In [15], the authors generate extended beat signal from consecutive
linear chirps to improve the range resolution. A coherent extension scheme is
proposed to avoid the discontinuity of the beat signal. However, such a design
requires knowing the Doppler frequency shift to identify the actual multipath
components, and is thus not applicable to signals reflected from static
objects or those with correlated moving dymanics. In [16], the authors propose
a curve fitting based spectral analysis method to accurately identify the
signal beat frequency. Similar ideas such as ZFFT [17], FFEA [18] and EDFT
[19] focus on using spectral analysis for improved DFT precision. All such
works [16, 17, 18, 19], although with improved DFT precision, cannot
fundamentally provide higher frequency resolution. Our proposed technique is
orthogonal in its design space to these spectral enhancement approaches [16,
17, 18, 19].

##  II Beat signal derived from different waveforms

(a)

(b)

(c)

(d)

Figure 1: Spectrograms of the four FMCW variations: (a) Triangle FMCW (b)
Sawtooth FMCW (c) Gentle FMCW and (d) Extended FMCW. Extended FMCW is adopted
to generate a reference beat signal which can provide twice the resolution.
Figure 2: The time domain beat signals (real part) derived with the four types
of FMCW waveforms.

The beat signal is derived by mixing the received signal with the conjugate of
the transmitted signal. The frequency components of the beat signal indicate
the propagation delays of the superimposed multipath components. In this
section, we investigate the time-domain characteristic of the beat signals
derived from different FMCW waveforms. The analysis of the characteristics is
the basis for further understanding the superiority of triangle FMCW in
providing improved range resolution.

We generate four variety of beat signals with using four different FMCW
waveforms: 1) a rising ramp stitched with a falling ramp (triangle FMCW) 2)
two repeated rising ramps (sawtooth FMCW) 3) a rising ramp with reduced slope
and (gentle FMCW) 4) a rising ramp extended to twice the bandwidth (extended
FMCW). Fig. 1 presents the spectrograms of these four FMCW variations.

We send each waveform over a fixed pre-configured wireless channel with
simulation, and the received signal is mixed with the conjugate of
corresponding transmitted signal to generate the beat signal. Note that to
clearly demonstrate the waveform characteristics of the different beat
signals, a single-tap channel model is adopted to avoid the waveform variation
caused by the superposition of different frequencies. The channel delay is set
to $\rm 1/(2B)$ for this demonstration where $\rm B$ denotes the bandwidth of
triangle FMCW.

Fig. 2 compares the obtained beat signals (real part) in time domain.Within
one symbol duration, the beat signal derived with triangle FMCW extends over a
complete cycle of a single tone and aligns well with the reference beat
signal. In contrast, the beat signal derived with sawtooth FMCW repeats its
half period, and that obtained from gentle FMCW exhibits half of a doubled
period. The different time varying patterns of these beat signals determine
their different frequency resolution (although the same frequency granularity
given the same amount of samples in time), which further determine the
different range resolution (as later demonstrated in Fig. 4).

The preliminary simulation demonstrates the special time-domain beat signal
derived from triangle FMCW. In the next section, we mathematically model the
beat signal and conduct a rigorous time-frequency domain analysis to explain
its efficacy and the rationale behind.

##  III Signal Model

A triangle FMCW symbol contains a linear up-chirp and its subsequent mirrored
down-chirp. We model the time domain waveform with the following piecewise
function (assume normalized amplitude),

$x_{tri}(t)=\begin{cases}e^{j(\pi\alpha t^{2}+2\pi f_{0}t)},&0<t\leq T_{c}\\\
e^{j[-\pi\alpha t^{2}+2\pi(f_{0}+B)t+\phi(T_{c})]},&T_{c}<t\leq
T_{s}\end{cases}$ (1)

where $B$, $\alpha$, $f_{0}$ denote the bandwidth, slope and initial frequency
of a single chirp. $T_{s}$ represents the duration of one symbol, and
$T_{c}=T_{s}/2$ denotes the duration of a single chirp. As Eq. 1 indicates,
triangle FMCW extends in the same way as linear FMCW before $T_{c}$ and then
continues with reversed slope (i.e., $-\alpha$) from $T_{c}$ to $T_{s}$. The
down-chirp contains a phase delay $\phi(T_{c})$ which leads to the smooth
phase transition from the up-chirp. Without loss of generality, the
formulation can be reduced as follows

$x_{tri}(t)=\begin{cases}e^{j(\pi\alpha t^{2})},&0<t\leq T_{c}\\\
e^{j[-\pi\alpha t^{2}+2\pi Bt+\pi BT_{c}]},&T_{c}<t\leq T_{s}\end{cases}$ (2)

where we consider single-sideband modulation (i.e., the initial frequency
equals zero). The signal is transmitted and received after time delay $\tau$,
i.e., $y_{tri}(t)=x_{tri}(t-\tau)$. Specifically,

$y_{tri}(t)=\begin{cases}0,&0<t\leq\tau\\\
e^{j[\pi\alpha(t-\tau)^{2}]},&\tau<t\leq T_{c}+\tau\\\
e^{j[-\pi\alpha(t-\tau)^{2}+2\pi B(t-\tau)+\pi BT_{c}]},&T_{c}+\tau<x\leq
T_{s}\end{cases}$ (3)

We derive the beat signal by mixing the received signal with the conjugate of
the transmitted signal as below,

$y_{b}(t)=\overline{x_{tri}(t)}\cdot y_{tri}(t)$ (4)

Specifically, the two signals are multiplied in each corresponding segment and
thus the beat signal $y_{b}(t)$ is composed of three segments which are
formulated as follows (the segment from 0 to $\tau$ is zero and thus is
omitted here),

$y_{b}(t)=\begin{cases}e^{j\pi(-2\alpha\tau t+\alpha{\tau}^{2})},&\tau<t\leq
T_{c}\\\ e^{j\pi[2\alpha
t^{2}-(4B+2\alpha\tau)t-3BT_{c}+\alpha{\tau}^{2}]},&T_{c}<t\leq T_{c}+\tau\\\
e^{j\pi(2\alpha\tau t-4B\tau-\alpha{\tau}^{2})},&T_{c}+\tau<t\leq
T_{s}\end{cases}$ (5)

As we see from the above form of the produced beat signal, the frequency of
$y_{b}(t)$ remains constant from $\tau$ to $T_{c}$ and from $T_{c}+\tau$ to
$T_{s}$, and linearly transitions between the two segments. Specifically, the
constant frequency equals to $-k\tau$ and $k\tau$ for the first and third
segment, respectively. During the second segment, the frequency increases with
a slope of $2k$. Based on such signal model, next, we analyze the spectral
leakage, explain the phase consistency of the produced beat signal, and prove
the improvement of range resolution.

Spectral leakage. The beat signal is discretized and then processed by DFT to
generate beat spectrum,

$Y_{b}(k)=\mathcal{DFT}\left[y_{b}(n)\right]=\sum_{n=N_{\tau}}^{N_{s}}y_{b}(n)e^{\frac{-j2\pi
kn}{N_{s}}}\vspace{-1.5mm}$ (6)

where $y_{b}(n)$ denotes the discretized beat signal samples and $Y_{b}(k)$
represents the frequency component located at the $k$-th bin of the discrete
spectrum, $N_{s}$ and $N_{\tau}$ denote the number of samples that correspond
to the symbol duration $T_{s}$ and the path delay $\tau$, respectively. We
show that the real part of the signal has a dominating frequency of
$\alpha\tau$ and with little spectral leakage.

Assume $T_{c}\gg\tau$ (i.e., $N_{c}\gg N_{\tau}$, the assumption can be
satisified for most wireless sensing applications [20]), the second segment of
$y_{b}(n)$ is ignorable and Eq. 6 can be approximated as,

$Y_{b}(k)=\sum_{n=N_{\tau}}^{N_{c}}y_{b}(n)e^{\frac{-j2\pi
kn}{N_{s}}}+\sum_{n=N_{c}+N_{\tau}}^{N_{s}}y_{b}(n)e^{\frac{-j2\pi
kn}{N_{s}}}$ (7)

Let $Y_{\Re_{b}}(k)$ be the DFT of real part of the beat signal. According to
the property of DFT, we can formulate $Y_{\Re_{b}}(k)$ as,

$Y_{\Re_{b}}(k)=\dfrac{1}{2}[Y_{b}(k)+\overline{Y_{b}(-k)}]$ (8)

where $\overline{Y_{b}(-k)}$ denotes the conjugate of the beat spectrum at the
negative frequency. By incorporating Eq. 7 to Eq. 8, the frequency component
at $k=\alpha\tau$ can be approximated as

$Y_{\Re_{b}}(\alpha\tau)=(N_{c}-N_{\tau})e^{-j\pi\alpha\tau^{2}}$ (9)

When $N_{c}\gg N_{\tau}$, the energy of the frequency component at
$k=\alpha\tau$ can be calculated as below,

$E_{Y_{\Re_{b}}(\alpha\tau)}=(|Y_{\Re_{b}}(\alpha\tau)|+|Y_{\Re_{b}}(-\alpha\tau)|)^{2}\approx|N_{s}|^{2}$
(10)

Eq. 10 indicates that the energy of the frequency component at $k=\alpha\tau$
greatly dominates the frequency spectrum (almost 100%) and thus spectral
leakage is ignorable. Next, we explain the underlying rationale of such low
spectral leakage.

Phase consistency. Despite the separation of the frequency varying segment
(the impact of this segment is analyzed in Sect. IV), the phase of the real
part of the third segment well aligns with the phase that is continuously
extended from the first segment. We name this observation as phase
consistency. Because of such a special characteristic, the real part of the
derived beat signal extends over a full period within the DFT window (as Fig.
2 already suggests), which takes effect to avoid the spectral leakage.

To prove the phase consistency, we derive the initial phase of the third
segment (i.e., $t=T_{c}+\tau$) with Eq. 5 as below,

$\phi_{y_{b}(T_{c}+\tau)}=\angle\left[e^{j\pi(2\alpha\tau
t-4B\tau-\alpha{\tau}^{2})}\right]_{t=T_{c}+\tau}=\pi(k{\tau}^{2}-2B\tau)$
(11)

Assuming the beat signal of the first segment extends continuously to the
third segment (like the case of using linear FMCW of twice the bandwidth), we
derive the phase at time $T_{c}+\tau$,

${\phi}^{{}^{\prime}}_{y_{b}(T_{c}+\tau)}=\angle\left[e^{j\pi(-2k\tau
t+k{\tau}^{2})}\right]_{t=T_{c}+\tau}=\pi(-k{\tau}^{2}-2B\tau)$ (12)

When $\tau=p/(2B),p\in\mathbb{Z^{+}}$,

$\phi_{y_{b}(T_{c}+\tau)}=-{\phi}^{{}^{\prime}}_{y_{b}(T_{c}+\tau)}$ (13)

Eq. 13 indicates that the real part (cosine) of the third segment maintains
consistent phase with that of the first segment. Therefore, the two segments
connect smoothly and perform as the natural time-domain extension, which
directly results in the improved resolution on frequency domain (as later
proved). We demonstrate the improvement in Sect. IV where we also analyze the
impact when $p\notin\mathbb{Z^{+}}$.

Figure 3: The impact of increasing propagation delay on $\rm SN_{T}R$.

Range resolution. The above analysis leads to direct proof in the improvement
of range resolution.

By performing DFT on the beat signal, we separate the frequency components
contained in the beat signal, which map to different multipath ranges by
multiplying a scaling factor. Therefore, the range resolution ($\Delta
R_{min}$) is fundamentally determined by the frequency resolution ($\Delta
f_{min}$) of the beat signal, specifically,

$\Delta R_{min}=\Delta f_{min}\cdot c/\alpha\vspace{-1mm}$ (14)

where $c$ denotes the signal propagation speed. In the equation, the frequency
resolution $\Delta f_{min}$ represents the ability to distinguish two closely
spaced frequency components of the original signal, which equals the inverse
of the measurement duration of each frequency beat ($T_{b}$), i.e., $\Delta
f_{min}=1/T_{b}$. Note that, $T_{b}$ represents the actual measurement
duration that a time-domain signal is continuously sampled over, which may not
equal the length of DFT window (which instead determines the granularity of
frequency domain signal after DFT).

With phase consistency, the real part of the beat signal effectively emulates
a set of frequency beats which are continuously sampled over twice the chirp
duration and thus $T_{b}=2T_{c}$. Therefore, the range resolution can be
further derived as below,

$\Delta R_{min}=1/T_{b}\cdot c/\alpha=1/T_{b}\cdot c\cdot T_{c}/B=c/2B$ (15)

which is improved from $c/B$ (provided by the standard method) to $c/2B$ by
two times.

##  IV Simulation

In this section, we adopt simulation to demonstrate the effectiveness of the
proposed method by comparing its ranging resolution with those obtained from
other approaches as listed below: 1) using the same triangle FMCW but adopting
a different processing method [14] (referred to as triangle FMCW-Li) 2)
adopting our proposed processing method but using sawtooth FMCW and 3)
adopting our method but using gentle FMCW. The spectrograms of sawtooth and
gentle FMCW are as presented in Fig. 1.

We send the variations of FMCW waveforms over a four-tap Rayleigh channel
where the multipath profile can be self defined. The received signals are
processed with the four methods to derive separate range profiles which depict
the distribution of multipath components at different ranges.

Fig. 4 demonstrates the range profiles obtained with the four different FMCW
waveforms. With the profile obtained from triangle FMCW (Fig. 4a), we can
clearly distinguish the four paths at the ranges of 51cm, 53cm, 60cm, and 61cm
(with $p$ equalling 48, 50, 56, 57 in respective). The path range estimations
are well aligned with the ground-truth (annotated with the vertical red
lines). Fig. 4b presents the results obtained with triangle FMCW-Li, which
fails to reflect the correct number of multipath components, and cannot
provide sufficient range resolution to resolve the third and fourth path (the
two paths merge into one peak). Fig. 4c depicts the profile obtained with
sawtooth FMCW. Similarly it fails to resolve the third and forth paths when
they are close (1cm range difference). Fig. 4d shows the profile obtained with
gentle FMCW. The granularity of this profile is coarser (half range
granularity) because the slope of gentle FMCW is half of the other waveforms.
As a result its resolution of this result cannot exceed 2cm. Overall, the
range profile obtained with the triangle FMCW provides twice the range
resolution compared to the other results.

(a) triangle FMCW

(b) triangle FMCW-Li

(c) sawtooth FMCW

(d) gentle FMCW

Figure 4: The range profiles which depict the distribution of multipath at
different ranges that are obtained with the four methods. The ground-truth
ranges are annotated with red lines. Using triangle FMCW of our design can
separate the four paths with the highest resolution.

(a) extended FMCW (oracle)

(b) linear FMCW (baseline)

(c) triangle FMCW

(d) CDF of the spacing error

Figure 5: Estimation of the spacing between two close targets. The spacing is
gradually reduced over the 30 tests. (a) to (c) detail the results obtained
with different FMCW waveforms (ground truth is annotated in red dashed line)
and (d) illustrates their statistical spacing errors.  Figure 6: Range profile
derived with non-integer $p$.

Impact of non-integer $p$. If $p\notin\mathbb{Z^{+}}$, the fractional residual
causes mismatched phase at the junction of the two segments. To evaluate the
impact of this mismatch, we set the range of the two paths to 5.9cm and 8.2cm
in our simulation, and then performed multipath separation by using three
different types of signals: linear FMCW, extended FMCW and triangle FMCW. The
results of multipath separation is shown in Fig. 6. As we see from the
results, despite the deviation in accuracy – which is due to the loss of phase
consistency when $p$ is non-integer, the results derived with both extended
FMCW and triangle FMCW identifies the two peaks successfully. Therefore, the
improved resolution of extended FMCW remains even when $p$ is a non-integer
value. However, it is equally important to note that in this case, the
accuracy of the range estimation may get reduced.

Impact of increased target range. The presence of the frequency varying
segment raises the noise floor of the beat spectrum and the impact may
intensify as target range increases. We conduct a further simulation to assess
how the increasing range impacts on the spectrum $\rm SN_{T}R$ ($\rm N_{T}$
denotes the spectrum noise induced by the transition period). Specifically, a
triangle FMCW signal is sent over a single-tap channel model where the path
delay increases. We record the $\rm SN_{T}R$ of each measurement and the
result is depicted in Fig. 3. Although $\rm SN_{T}R$ reduces with increasing
range, it is still over -7.4 dB (the spike can still be detected at this $\rm
SN_{T}R$) when the delay exceeds 40% of the chirp duration, which equivalently
supports km-level target range for radio frequency based sensing applications.

##  V Conclusion

In this paper, we propose a novel signal processing technique that leverages
the phase consistency of beat signal derived with triangle FMCW to improve the
resolution of FMCW ranging with signal bandwidth limit. We prove the efficacy
of the design with spectral analysis and evaluate the improvement with model
based simulation and real world experiment. The range accuracy of the proposed
technique may reduce when the actual range does equal integer number of the
resolution. This issue can be mitigated by applying calibration or filtering
algorithms to correct the estimation results. The accuracy could also be
affected by the Doppler effect, which may be resolved by incorporating the
standard triangle FMCW based Doppler estimation approach. We leave the
detailed study on this issue as future work.

## References

  * [1] F. Adib, Z. Kabelac, D. Katabi, and R. C. Miller, “3d tracking via body radio reflections,” in _Proceedings of the 11th USENIX Conference on Networked Systems Design and Implementation_ , ser. NSDI’14. USA: USENIX Association, 2014, p. 317–329.
  * [2] R. Sorrentino, E. Sbarra, L. Urbani, S. Montori, R. V. Gatti, and L. Marcaccioli, “Accurate fmcw radar-based indoor localization system,” in _2012 IEEE International Conference on RFID-Technologies and Applications (RFID-TA)_. IEEE, 2012, pp. 362–368.
  * [3] R. Xiong, X. Feng, H. Zheng, and Z. D. Chen, “Linear fmcw radar system for accurate indoor localization and trajectory detection,” in _2020 International Conference on Computing, Networking and Communications (ICNC)_. IEEE, 2020, pp. 741–745.
  * [4] Z. Zhang, Z. Tian, and M. Zhou, “Latern: Dynamic continuous hand gesture recognition using fmcw radar sensor,” _IEEE Sensors Journal_ , vol. 18, no. 8, pp. 3278–3289, 2018.
  * [5] B. Dekker, S. Jacobs, A. Kossen, M. Kruithof, A. Huizing, and M. Geurts, “Gesture recognition with a low power fmcw radar and a deep convolutional neural network,” in _2017 European Radar Conference (EURAD)_. IEEE, 2017, pp. 163–166.
  * [6] Z. Peng, C. Li, J.-M. Muñoz-Ferreras, and R. Gómez-García, “An fmcw radar sensor for human gesture recognition in the presence of multiple targets,” in _2017 First IEEE MTT-S International Microwave Bio Conference (IMBIOC)_. IEEE, 2017, pp. 1–3.
  * [7] S.-J. Ryu, J.-S. Suh, S.-H. Baek, S. Hong, and J.-H. Kim, “Feature-based hand gesture recognition using an fmcw radar and its temporal feature analysis,” _IEEE sensors Journal_ , vol. 18, no. 18, pp. 7593–7602, 2018.
  * [8] C. Ding, Y. Zou, L. Sun, H. Hong, X. Zhu, and C. Li, “Fall detection with multi-domain features by a portable fmcw radar,” in _2019 IEEE MTT-S International Wireless Symposium (IWS)_. IEEE, 2019, pp. 1–3.
  * [9] Z. Peng, J.-M. Muñoz-Ferreras, R. Gómez-García, and C. Li, “Fmcw radar fall detection based on isar processing utilizing the properties of rcs, range, and doppler,” in _2016 IEEE Mtt-S International Microwave Symposium (IMS)_. IEEE, 2016, pp. 1–3.
  * [10] T. Yang, J. Cao, and Y. Guo, “Placement selection of millimeter wave fmcw radar for indoor fall detection,” in _2018 IEEE MTT-S International Wireless Symposium (IWS)_. IEEE, 2018, pp. 1–3.
  * [11] A. Ahmad, J. C. Roh, D. Wang, and A. Dubey, “Vital signs monitoring of multiple people using a fmcw millimeter-wave sensor,” in _2018 IEEE Radar Conference (RadarConf18)_ , 2018, pp. 1450–1455.
  * [12] M. Alizadeh, G. Shaker, J. C. M. D. Almeida, P. P. Morita, and S. Safavi-Naeini, “Remote monitoring of human vital signs using mm-wave fmcw radar,” _IEEE Access_ , vol. 7, pp. 54 958–54 968, 2019.
  * [13] M. He, Y. Nian, and Y. Gong, “Novel signal processing method for vital sign monitoring using fmcw radar,” _Biomedical Signal Processing and Control_ , vol. 33, pp. 335–345, 2017.
  * [14] Y. Li and S. O’Young, “Method of doubling range resolution without increasing bandwidth in fmcw radar,” _Electronics Letters_ , vol. 51, no. 12, pp. 933–935, 2015.
  * [15] A. Lulu and B. G. Mobasseri, “High-resolution range-doppler maps by coherent extension of narrowband pulses,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 56, no. 4, pp. 3099–3112, 2020.
  * [16] H.-H. Ko, K.-W. Cheng, and H.-J. Su, “Range resolution improvement for fmcw radars,” in _2008 European Radar Conference_ , 2008, pp. 352–355.
  * [17] E. Hoyer and R. Stork, “The zoom fft using complex modulation,” in _ICASSP ’77. IEEE International Conference on Acoustics, Speech, and Signal Processing_ , vol. 2, 1977, pp. 78–81.
  * [18] J. Liu, X. Chen, and Z. Zhang, “A novel algorithm in the fmcw microwave liquid level measuring system,” _Measurement Science and Technology_ , vol. 17, no. 1, p. 135, 2005.
  * [19] V. Liepins, “Extended fourier analysis of signals,” _arXiv preprint arXiv:1303.2033_ , 2013.
  * [20] Texas Instrument, “Intro to fmcw radars,” 2017, [Online; 28-April-2017]. [Online]. Available: https://training.ti.com/sites/default/files/docs/mmwaveSensing-FMCW-offlineviewing_0.pdf