# Illegal But Not Malware: An Underground Economy App Detection System Based
on Usage Scenario

Zhuo Chen  Zhejiang University  Ant Group  Jie Liu  Ant Group  Yubo Hu  Xidian
University  Lei Wu  Zhejiang University  Yajin Zhou  Zhejiang University
Xianhao Liao  Ant Group  Ke Wang  Ant Group

###### Abstract

This paper focuses on mobile apps serving the underground economy by providing
illegal services in the mobile system (_e.g._ , gambling, porn, scam). These
apps are named as underground economy apps, or UEware for short. As most
UEware do not have malicious payloads, traditional malware detection
approaches are ineffective to perform the detection.

To address this problem, we propose a novel approach to effectively and
efficiently detect UEware by considering the transition orders of the user
interfaces (UIs), which determine the usage scenarios of these apps. Based on
the proposed approach, we design a system named DeUEDroid to detect the UEware
via scene graph. To evaluate DeUEDroid, we collect $26,591$ apps to evaluate
DeUEDroid and build up the first large-scale ground-truth UEware dataset
($1,720$ underground economy apps and $831$ legitimate apps). The evaluation
result shows that DeUEDroid can construct scene graph accurately, and achieve
the accuracy scores of $77.70$% on the five-classification task (_i.e._ ,
gambling game, porn, financial scam, miscellaneous, and legitimate apps),
reaching obvious improvements over the SOTA approaches. Running further on
$24,017$ apps, DeUEDroid performs well in the real-world scenario to mitigate
the threat. Specifically, by using DeUEDroid, we found that UEware are
prevalent, _i.e._ , 61% apps in the wild and 21% apps in the app stores are
UEware (with over 72% accuracy after the manual investigation). We will
release our dataset and system to engage the community after been accepted.

##  1 Introduction

Mobile apps have been an indispensable part of our daily life, from online
shopping, entertainment, and even financial business [7]. At the same time,
apps that serve the underground economy by providing illegal services 111The
services that violate local laws, for example, most countries and regions
around the world have strict legal regulations on online gambling., are
prevalent in the wild nowadays [4, 35, 10], and thereby lead to serious
damages. For example, the porn scam apps caused more than $$304$ million
losses in 2020 [3]. Meanwhile, the gambling apps made more than $$53$ billion
revenue in the US in 2021 [13, 14]. As an essential role in reported losses
[4], these apps serve the underground economy by providing illegal services in
the mobile system (_e.g._ , gambling, porn, scam). In this study, we call them
underground economy apps, or UEware for short.

Unlike the traditional malware (_e.g._ , backdoor, trojan, spyware), UEware
are characterized based on the legitimacy of the services, while (most of)
them do not necessarily engage malicious payloads. As the concept of UEware is
(partially) orthogonal to that of the malware, it is possible to give a more
comprehensive categorization for mobile apps by considering the combination of
the existence of the malicious payloads and the legitimacy of the services. As
such, apps could be further categorized into four categories, i.e., legitimate
apps, malware, malware & UEware and UEware, respectively, as shown in Figure
1. Obviously, UEware consist of both the third and the fourth categories;
while the majority of UEware fall into the fourth category, occupying over 80%
(see Section 8.3) among all UEware.

Figure 1: The definition of UEware compared to malware.

The proliferation of UEware calls for effective solutions to mitigate this
threat. Specifically, there is a great demand for an efficient detection
technique due to the large volume of apps that need to be verified. For
instance, there were over two million new apps released on GooglePlay in 2021
[12]. However, only a few previous studies [47, 32, 46, 24] have focused on
UEware by analyzing some special sort of them (_i.e._ , gambling and scam) and
proposing some recommendations to users and legal authorities. Nonetheless,
none of the existing works propose feasible detection approaches.

Furthermore, the malware detection approaches could not be applied to identify
UEware. Specifically, as most UEware do not have malicious payloads, those
static detection methods [29, 61, 65, 44] focusing on the malicious payloads
will inevitably lead to high false negative rates. They generally rely on
either the code structure (_e.g._ , API flow [29, 61]) or the configuration
(_e.g._ , permission [54]) of apps to perform the detection. Alternatively,
the dynamic detection methods are not feasible to perform the large-scale
detection due to the inherent scalability limitation, i.e., they have to
execute the apps to examine their behaviors [60] and fetch the screenshots
[27], thus consuming huge resources [42].

Our approach. In this paper, we propose a novel approach to effectively and
efficiently detect UEware by considering the transition orders of the user
interfaces (UIs), which determine the usage scenarios of these apps.
Specifically, for a given app, the service is presented to the users through
multiple UIs in a specific order. These ordered UIs are aware of the usage
scenarios, which further constitute a scene-aware UI transition graph. In the
following context, this graph is named as scene graph for short.

Figure 2: A core scene graph of an underground loan App.

Our approach is based on two key observations. First, the scene graphs of
UEware are different from those of the legitimate apps. On average, UEware
have fewer transition pairs and UI widgets than legitimate apps, _i.e._ , $11$
vs. $22$ and $29$ vs. $227$, respectively (see Section 8). Unlike the
legitimate apps, UEware opt to serve as single-purpose apps 222As UEware have
been observed in the wild for a decade [1], such a phenomena might come from
the lack of motivation to provide plentiful functionalities due to the huge
profits of the illegal services.. For example, most underground loan apps are
used for only one purpose, _i.e._ , loan application. On the contrary, normal
financial apps not only serve for loan applications, but also for financial
derivatives purchasing, asset evaluation, and other purposes. Second, the
scene graphs of the same type of UEware are extremely similar, while the scene
graphs of different types of UEware vary from each other. For instance,
underground loan apps have a similar scene graph, such as the transition from
the personal page to loan apply, as shown in Figure 2. Note that, this scene
graph is different from that of other types, _e.g._ , the gambling apps, as
shown in Figure 3.

However, identifying UEware based on scene graph is a challenging task. First,
it is difficult to build a precise scene graph, which requires effectively:
(i) identifying the UI widgets and their attributes; and (ii) determining the
UI transition orders. However, the existing UI analysis studies [53, 39] only
focus on native widgets (_i.e._ , XML widget and dynamic widget) but omit web
widgets (_i.e._ , Webview). Meanwhile, the existing transition identification
studies [50] only focus on the Inter-Component Communication (ICC) of the
activity but ignore the processing of fragment and navigation. Second, it is
hard to directly leverage scene graph to perform the detection. A scene graph
is expressed via a mixture of graph topology and unstructured UI attributes,
and the correlations of them cannot easily be applied as an effective
representation.

Figure 3: A core scene graph of a gambling App.

This work. We design a system named DeUEDroid to detect UEware by addressing
the above challenges. DeUEDroid consists of three modules: (i) scene graph
builder, which is used to construct a precise scene graph. This module
consists of two phases, _i.e._ , UI widget identification and UI transition
determination. Specifically, in the first phase, DeUEDroid proposes a hybrid
widget identification approach, which covers both the native widgets and the
web widgets by properly integrating two previous studies, _i.e._ , SOTA UI
analysis tool [31] and network imprint [23]. While in the second phase,
DeUEDroid proposes a new activity transition graph (ATG) construction
algorithm to accurately capture UI transition pairs. By doing so, DeUEDroid is
capable of building scene graph in a precise manner. (ii) scene graph feature
extractor, which is responsible for extracting the feature from the scene
graph. Specifically, DeUEDroid follows the success of graph embedding, and
adopts the self-supervised graph auto encoder (GAE) to combine the scene graph
topology and UI attributes together as the scene graph representation. (iii)
UEware detector. The detector leverages the self-supervised representation
learning to detect and classify UEware based on the scene graph features.

To evaluate the effectiveness and efficiency of DeUEDroid, we build up three
datasets, containing $26,591$ apps. First, we use $23$ open-source apps to
evaluate the effectiveness of scene graph construction. The evaluation result
suggests that DeUEDroid can construct accurate scene graph, which can
accurately identify transition pairs (over 72%) and imprint tokens (over 90%).
Then, we build up the ground-truth UEware dataset, which is the first large-
scale ground-truth dataset ($2,551$ apps) of UEware, to evaluate the
effectiveness of UEware detection. The evaluation result shows that DeUEDroid
can detect discrepancies with accuracy values $77.70$% for demystifying
gambling game, porn, underground loan, financial scam, and legitimate apps.
Our system has a significant effect on improving detection accuracy. Finally,
we perform a large-scale experiment on $24,017$ apps collected from app stores
(and the wild), to measure the effectiveness and efficiency of large-scale
UEware detection. The evaluation result demonstrates that DeUEDroid achieves
good performance to mitigate the real-world threats. By using DeUEDroid, we
found that UEware are prevalent, _i.e._ , $61$% apps in the wild and $21$%
apps in the app stores are UEware (with over 72% accuracy after the manual
investigation).

Contributions. We make the following contributions:

  * •

We proposed a novel approach to detect UEware based on scene graph. This
approach first builds scene graph for the training APKs, and then extracts
features of scene graph. After that, it applies a machine learning method to
train the classifier to detect UEware. We proposed and implemented a prototype
system named DeUEDroid to perform the detection. The evaluation results
demonstrate the effectiveness and efficiency of the proposed system.

  * •

Based on DeUEDroid, we found that the UEware are proliferating, which occupies
61% apps in the wild. What’s more, even in the app stores, there are still a
lot of undetected UEware (21% of all apps).

  * •

We built up a ground-truth UEware dataset with $2,551$ Android apps. To our
best knowledge, this is the first large-scale UEware dataset. We will release
our system and datasets to engage the community.

##  2 Background

In this section, we introduce the usage service of the Android app, which
consists of user interfaces (UI) and their transitions. Then we describe the
definition of the Android scene graph. For better understanding, we show a
core scene graph of an underground loan app in Figure 2 as an example (the
real screenshots are in Figure 13 in appendix).

###  2.1 User Interface

The UI is responsible for communicating with users, which shows the contents
of the app. Specifically, UI consists of the UI widgets on the same
activity/fragment. And it is worth noting that all widgets depend on activity
or fragment for drawing.

First, the activity is the fundamental component for drawing the UI widgets
with which users can interact with [2]. And since Android 3.0, fragments can
also render the UI widgets. However, the fragment is a portion of the
activities, which can not exist independently. Second, the UI widget is the
fundamental accessible view for the users that contains data or functionality.
All widgets inherit from the view class, such as TexitView and LinearLayout.
The widget can be dived into two types: native widget and web widget. The
native widgets are statically recorded in the XML file or dynamically added in
code. But the web widgets are loaded from a web URL.

###  2.2 User Interface Transition

An android app is consist of multiple UIs for handling complex business
requirements. When some special conditions are triggered, the app will transit
from one UI to another. Specifically, UI is rendered on activity/fragment, so
these UI transitions are triggered in three ways: (i) triggered by explicitly
invoking activity transition API, _e.g._ , the StartActivity,
StartActivityForResult; (ii) triggered by implicitly invoking conversions,
_e.g._ , Android Inter-Component Communication (ICC); (iii) triggered by
invoking system listener, _e.g._ , onKeyDown. The activity transition is
closely integrated with Android lifecycle, _i.e._ , the target activity will
gain the focus and invoke Oncreate and OnStart while the origin one lose the
focus and invoke the OnPause or OnStop.

Besides, the fragment navigation also reflects the UI transition within an
activity. The navigation consists of three key parts: (i) Navigation graph, an
XML resource that contains all navigation-related information. (ii) NavHost,
an empty container that displays navigation graph. (iii) NavController, an
object that manages navigation within a NavHost. Fragment navigation extremely
improves the flexibility of transitions, and has been widely used in recent
years [8].

###  2.3 Formal Definition of Scene Graph

For a given app, its service is presented to the users through multiple user
interfaces (UIs) in a specific order. These specific ordered UIs are aware of
the app usage scenarios, which further constitute a scene-aware UI transition
graph, or scene graph for short.

Definition I: A scene graph is a directed graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ in a node attribute space $\Omega$,
where: 1\. $\mathcal{V}$ is a node set, with each node being an
activity/fragment; 2\. Each node is assigned UI attribute labels in $\Omega$:
_e.g._ , layout, widget type, button, and network imprint. 3\. Directed edge
set $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is a set of transitions
between activity/fragment and $\varepsilon$ is the single edge within the
$\mathcal{E}$.

Static Detection Approach | Detection Studies | Feature Selection
---|---|---
Code | UI | Manifest
Bytecode | API | Method | Activity | XML widget | Dynamic widget | Web widget | Dveloper signature | Permission
Signature Based | ViewDroid [67], MassVert [21] | - | - | ✔ | - | ✔ | - | - | - | -
DriodMoss [45] | ✔ | - | - | - | - | - | - | - | -
Retriever [55], AndroSimilar [30] | - | - | - | - | - | - | - | ✔ | -
PUMA [54] | - | - | - | - | - | - | - | - | ✔
Kirin [29], DroidMat [61] | - | ✔ | - | - | - | - | - | - | ✔
Machine Learning Based | Kim et al. [37] | - | ✔ | ✔ | - | - | - | - | - | ✔
DroidSIFT [66] | - | ✔ | - | - | - | - | - | - | -
SIGPID [40], Droid-Sec [15] | - | ✔ | - | - | - | - | - | - | ✔
DeUEDroid(Ours) | - | - | - | ✔ | ✔ | ✔ | ✔ | - | -

TABLE I: The feature selection comparison with previous static detection
studies.

##  3 Motivation

In this section, we first illustrate the limitation of the traditional malware
detection approaches 333Note that, here we focus on the static approaches
which are feasible to perform the large-scale detection.. Specifically, we
summarize the features adopted by representative systems/tools to detect
malware, which cannot be applied to detect UEware. After that, we detail the
feasibility of our approach by demonstrating the validity of the key
observations.

###  3.1 Limitation of the Traditional Approaches

Features used by those traditional malware detection approaches can be
categorized into the following three categories: code, UI, and Manifest, as
shown in Table I. Specifically, they mainly focus on code features at the
method granularity. In addition, a few studies focus on UI features for XML
widgets, while some other studies make extensive use of the Manifest
information, including app name, package name, developer signatures, and
permissions.

However, all of these features are ineffective to detect UEware due to the
following reasons:

  * •

Lack of malicious payload. Most UEware do not have any malicious payloads,
which inevitably leads to the failure of control flow based detection
approaches (_e.g._ , API flow).

  * •

Incomplete UI content. Nowadays, the dynamic loading and web widgets are
widely adopted by UEware. As a result, those approaches [67, 21] that only
analyze XML widgets become ineffective due to the low identification coverage.
On the other side, the UI content (_e.g._ , pictures, videos) is always
downloaded from the remote server at runtime. Obviously, the detection
approaches based on native resources [48, 43, 22] are not feasible due to the
high false negative rate.

  * •

Ineffective Manifest. The Manifest information cannot be used as the unique
features to detect UEware. Specifically, the permissions acquired by UEware
are similar to those of legitimate apps [32], while the developer signatures
can always be arbitrarily customized (in Android).

###  3.2 Feasibility of Our Approach

As mentioned in Section 1, our approach is based on two key observations:

  * •

Observation-I: the scene graphs of UEware are different from those of the
legitimate apps.

  * •

Observation-II: the scene graphs of the same type of UEware are extremely
similar, while the scene graphs of different types of UEware vary from each
other.

As the first observation can be concluded from the statistical result, hence
here we mainly focus on the second observation by providing two concrete
examples.

To demonstrate that the scene graphs of the same type of UEware are extremely
similar, we randomly choose two loan apps (with different Manifest
information) that serve the underground loan application. The runtime
screenshots of these two apps are shown in Figure 13 (in appendix) and Figure
14 (in appendix), respectively. Although the texts and images of these two
screenshots are different from each other, they share the same (core) scene
graph, as shown in Figure 2.

To demonstrate that the scene graphs of different types of UEware vary from
each other, we additional use a gambling app to perform the comparison. The
runtime screenshot and the core scene graph of the gambling app are shown in
Figure 15 (in appendix) and Figure 3, respectively. Obviously, the (core)
scene graph of the gambling app is different from that of the loan app, _i.e._
, Figure 3 vs. Figure 2.

##  4 Design Overview

Figure 4: The design overview of DeUEDroid.

Based on the proposed approach, we design a system named DeUEDroid to detect
the UEware via scene graph. Specifically, DeUEDroid first builds scene graph
for the training APKs, and then extracts features of scene graph. After that,
it applies a machine learning method (_i.e._ , self-supervised representation
learning) to train the classifier to detect UEware.

Figure 4 shows the architecture of DeUEDroid. There are three modules, _i.e._
, Scene Graph Builder, Scene Graph Feature Extractor and UEware Detector, as
follows:

  * •

Scene Graph Builder. This module accepts Android APK files as the input, and
outputs the scene graphs. It consists of two phases: UI widget identification
and UI transition determination. Specifically, in the first phase, the builder
covers both the native widgets and the web widgets by properly integrating two
previous studies, _i.e._ , SOTA UI analysis tool [31] and network imprint
[23]. While in the second phase, the builder considers all transition types
and proposes a new ATG construction algorithm to accurately capture UI
transition pairs.

  * •

Scene Graph Feature Extractor. Based on the scene graphs, this module combines
both graph topology and UI attributes together and outputs the scene graph
representation. Specifically, it leverages the Graph Automatic Encoder (GAE)
[38] with a 2-layer GCN [25] to embed scene graph. In particular, before the
graph embedding, the DeUEDroid additionally adopts the Mask strategy to
enhance the embedding robustness.

  * •

UEware Detector. Based on the scene graph features, this module leverages the
self-supervised representation learning to train a UEware classifier, which
will be used to perform the detection. Note that the scene graph based
approach allows further classifying the apps into different categories of
UEware. Hence currently fives categories, including gambling game, porn,
financial scam, Miscellaneous and legitimate apps, are supported by the
system.

The detailed design of these three modules will be illustrated in Section 5,
Section 6 and Section 7, respectively.

Figure 5: The design of scene graph builder.

##  5 Scene Graph Builder

In this section, we describe the design of scene graph builder by first
providing the module overview, and then introducing the two phases of this
module one after another.

###  5.1 Module Overview

This module has two phases: (i) UI widget identification, and (ii) UI
transition determination, as shown in Figure 5. All phases take an Android APK
file as the input. The output of UI widget identification is a set of UI
widgets and their attributes. Notably, the native widget attributes are well
collected, such as widget layout, types, and button listener. And the web
widget (_e.g._ , WebView) attributes are represented by their network
imprints. The output of UI transition determination is a directed graph
representing the transition relationship between activities/fragments, also
called the activity transition graph (ATG). In the end, the scene graph of
apps is well constructed as a directed graph, in which each node is an
activity/fragment, and each directed edge describes a transition from one
activity to another.

###  5.2 UI Widget Identification

In Android, the UI widgets are rendered on an activity or a fragment, and can
be dived into native widgets and web widgets. Specifically, DeUEDroid proposes
different analysis methods for two different types of widgets.

Native Widgets. As mentioned in Section 2, the native widgets can be
statically recorded in the XML file or dynamically added at runtime. Generally
speaking, XML file are loaded through API calls like “setContentView” or
“inflate”. And the XML widgets can be loaded via API calls such as
“findViewByID”. The dynamic loading widgets will be identified in code (_e.g._
, new TextView()) directly, and be attached to some existing layout. And
through these API calls, we map the widget to their corresponding activity.

To perform native widgets analysis, we adopt FrontMatter [39], the SOTA static
UI analysis tool, to figure out the native widgets. Considering the lifecycle
of Android, the FrontMatter only restores the UI creation process within the
“OnCreate” phase. This design improves the analysis speed and is suitable for
massive dataset situations.

The analysis performs on XML files to identify the widget types (_e.g._ ,
ImageView, ConstrainLayout), the widget layout, the widget icon (_e.g._ ,
@drawable/ic_button), and the event listeners (_e.g._ , OnClick). And the
analysis also performs on code and leverages taint flow analysis to identify
the dynamic widget attributions. Finally, it combines the results on both the
XML files and the code to identify all native widgets and their attributes. In
addition, based on the special API calls, we analyze relationships between
activities/fragments and widgets to map the activities and their native
widgets together.

Figure 6: The example of network token generation.

Web Widgets. Nowadays, the hybrid development paradigm is commonly used in app
development, occupying $74$% top 50 apps in markets [9]. These hybrid apps
acquire remote resources through web widgets. Specifically, the WebView starts
a local browser and invokes the “LoadURL” API with a java.lang.String type
parameter. Then the URL corresponding to the parameter will be shown in the
local browser. For these web widgets, the essential part is the URL parameter.

However, it’s nearly impossible to get the accurate network URL in static
analysis [26]. So we refer to the previous studies [23] and generate the
network imprint of web widgets instead. The network imprint consists of any
field token with invariable content (_e.g._ , IP address, hostname, key, and
value) to identify the web widget. To generate imprint, there are two key
observations we leverage for variable identification: (i) the URL parameter of
Webview and its related tokens are all in string type (_i.e._ ,
java.lang.String,java.lang.StringBuilder and java.lang.StringBuffer). (ii)
almost always, a parameter related token originates from some constant values
within the program, such as constants, XML resources, and Manifest. Based on
the two key observations, we propose a special backward taint analysis scheme.
Specifically, we only focus on the variables in string type and methods
related to string (_e.g._ , assign(), add(), replace()) to reduce the
magnitude of taint analysis. We then instantiate variables from constant
values and discard runtime-generated variables (_e.g._ , user input).

Here we use an example (Figure 6) to present the whole backward taint process.
First, the program loads activities/fragments, and searches special API calls
(_e.g._ , WebView.loadURL()). Once the sink statement is found in Class Y
method C, the sink variable is url. Then the program will perform backward
taint analysis to check whether any variable affect url. After running, v4 and
X.B() is determined to affect url using java.lang.StringBuilder.append()
method. And the v4 is considered that unrelated to any invariant source within
the app but instantiated from runtime-generated variables, which can not be
determined in static analysis, so we discard the v4. Turn to the X.B(), since
it is an inter-procedure call, the program additionally loads Class X and sink
the v2. Going further, the program finds that A() and v3 affect the v2. At
this time, v3 is determined to be an ImmediateBox variable, so the program
instantiates v3 with a concrete value. At last, program finds that A() is
assigned by v1 from XML resource (R.string.baseUrl). In this sample, the
variable is from res/values/string.xml, which will be dynamically loaded by
the program and instantiated with a concrete value. To sum up, v1,v3 are
instantiated as constant variables, v4 is instantiated as runtime-generated
variable and discarded. In the end, the program outputs a set of tokens
(_e.g._ , [v1,v3]) and removes some common tokens (_e.g._ , github). These
tokens are used as network imprints to identify web widget attributes.

Top-Class Name | Run Method | Start Method
---|---|---
| onPreExecute | execute
| doInBackground | onPreExecute
AsyncTask | doPostExecute | doInBackground
OnClickListener | setOnClickListener | OnClick
Runnable | run | start
Message | handleMessage | sendMessage

TABLE II: The implicit run and start pairs.

Data: $apk$: the APK file.

Result: $ATG=(Nodes,Edges)$: the generated activity transition graph for
$apk$.

Function  _ATG_Construction( apk)_:

$Nodes\leftarrow\\{\\}$;

$Edges\leftarrow\\{\\}$;

$cg\leftarrow\textnormal{{get\\_CallGraph}}(apk)$;

$classes\leftarrow\textnormal{{get\\_AllClasses}}(apk)$;

for  _$class$ in $classes$_ do

if  _$\textnormal{{is\\_Fragment}}(class)$ $or$
$\textnormal{{is\\_Activity}}(class)$_ then

$Nodes~{}\cup\\{class\\}$;

end if

$methods\leftarrow\textnormal{{get\\_AllMethods}}(class)$;

for  _$method$ in $methods$_ do

$units\leftarrow\textnormal{{get\\_AllUnits}}(method,cg)$;

for  _$unit$ in $units$_ do

if  _$\textnormal{{is\\_Transition}}(unit)$_ then

$callees~{}\cup\textnormal{{get\\_Callees}}(unit)$;

$callers~{}\cup\textnormal{{get\\_CallerActs}}(class,cg)$;

$Edges~{}\cup\\{callers,callees\\}$;

end if

end for

end for

if  _$\textnormal{{has\\_Navigation}}(class)$_ then

$caller\leftarrow\textnormal{{get\\_CallerActs}}(class,cg)$;

$callees\leftarrow\textnormal{{get\\_NavTargets}}(class)$;

$Edges~{}\cup\\{caller,callees\\}$;

end if

end for

return $ATG(Nodes,Edges)$;

Function  _get_CallerActs(_$class,cg$_)_:

if  _$\textnormal{{is\\_Fragment}}(class)$_ then

$callers\leftarrow\\{class,\textnormal{{get\\_ActsWithFragment}}(class,cg)\\}$;

else if  _$\textnormal{{is\\_InnerClass}}(class)$_ then

$callers\leftarrow\textnormal{{get\\_OuterActs}}(class,cg)$;

else $callers\leftarrow class$ ;

return $\\{callers\\}$;

Algorithm 1 The ATG Construction Algorithm

###  5.3 UI Transition Determination

As mentioned in Section 2.2, the UI transition can be triggered by multiple
methods. And it is worth noting that fragments have become an essential part
of transition relationships, with independent transition functions and UI
widgets. However, previous studies [19, 50, 22] have overlooked this part,
leading to some omissions. To build up an appropriate UI transition graph, we
propose a new Activity Transition Constriction (ATG) Algorithm 1.
Specifically, we first initialize Nodes and Edges as empty sets, which stores
the activity/fragment and their transition relationships respectively. Then we
generate the call graph (cg) of the given APK, and fetch out all classes
defined in the Manifest. Notably, considering there are some implicit run and
start pairs (see in Table II) in Android, which will affect the integrity of
the call graph. We manually add these pairs and complete the call graph in our
studies.

To each class in APK, we judge whether they inherit from activity or fragment,
and if so, add them to the Nodes set. Then for all methods in each class, we
get all units according to the previous call graph. To these units, we judge
whether they have transition movements. As mentioned in Section 2.2, the
explicitly transition and implicitly transition have special APIs (_e.g._ ,
StartActivity(), Intent()). By comparing the API signatures, we can locate the
translation units. Besides the special APIs, we analyze the navigation by
searching special structures (_e.g._ , NavController) defined in classes.
Finally, we monitor whether the activity has overloaded system-level calls,
such as onKeyDown(), to implement the transition.

Figure 7: The design of scene graph feature extractor.

If there lives an activity transition unit, we first get the target activities
(callees) by analyzing the unit arguments based on taint analysis. Due to the
difficulty in handling conditional judgments, all possible target
activities/fragments are included. Then we get the source activities
(callers). Specifically, three different processing methods are adopted
according to the class type: (i) If the class is a fragment, the callers are
the union of this fragment and all activities that own this fragment. (ii) If
the class is an inner class, the callers are the union of the outer classes of
this inner class. (iii) Else, the caller is the current class itself. Finally,
for the callers and callees found by a transition, we traverse all callers and
callees and add all pairs (caller $\to$ callee) to the Edges set. The activity
transition graph consists of the nodes in Nodes and the directed edges in
Edges.

##  6 Scene Graph Feature Extractor

In this section, we describe the design and implementation of scene graph
feature extractor. We first provide the module overview, and then introduce
the detail of Mask strategy, the GAE, and the loss calculation.

###  6.1 Module Overview

The overview of this module is shown in Figure 7. For an input APK, its scene
graph is produced from the previous module, and the scene graph definition is
shown in Sec 2. We first encode the activity’s UI attributes $\Omega$ into UI
matrix $X$ and adopt the Mask strategy to mask the graph to produce two masked
graphs $\mathcal{G}$ and $\mathcal{\widehat{G}}$. We then use GAE with 2-layer
GCN to combine the graph $\mathcal{G}$ and UI matrix $X$ into a feature
representation $\mathcal{Z}$ as the node embedding. Note that even UI
properties and graph topology can be seen as independent features of the apps,
the correlation information will be ignored, resulting in the loss of
accuracy. Consequently, we correlate these two features together as a joint
feature. Finally, to improve the quality of the embedding, we calculate the
decode loss, which consists the global contrastive loss between the two masked
graphs and the local reconstruction loss within the same map.

###  6.2 Mask Strategy

In the underground economy, developers always generate new apps by modifying
parts of the code or functions of existing apps to improve development
efficiency.

To counteract the impact of code modifications, it requires a high robustness
of the graph embedding model. To this end, we find that the Mask strategy is
very suitable. First, the Mask strategy can be viewed as an adversarial attack
that provides a new view of the graph as data augmentation. Second, according
to previous work [41], masking a certain part of the fringe edges/nodes can
significantly reduce the redundancy of two paired subgraphs, thereby avoiding
trivial overlapping subgraphs. Furthermore, previous empirical evidence [52]
shows that fringe information is often redundant for downstream tasks such as
node classification. In general, Mask strategies can be divided into Edge-wise
random masking and Path-wise random masking. In this study, we adopt the Edge-
wise random masking, which is defined as:

$\varepsilon_{mask}\sim Bernoulli(p)$ (1)

where $\varepsilon$ denotes the edge within the $\mathcal{E}$. We use the
Bernoulli random function to mask a part of edges as the input for the next
stage.

###  6.3 Graph Auto Encoder

Autoencoders [34] are designed to reconstruct certain inputs given the
contexts and do not enforce any decoding orders. In this study, our encoder
$f_{\theta}$ (parameterized by $\theta$) is 2-layer graph convolutional
networks (GCN) [25], a well-established GNN architecture widely used in
literature [58]. Specifically, the encoder first calculate
$\widehat{A}=\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}$
in the pre-processing step, where $\widehat{A}$ is the adjacency matrix of the
graph $\mathcal{G}$ with added self-connections, $I_{N}$ is the identity
matrix, and $D$ stands for the degree matrix of $\mathcal{G}$. The forward
model then takes a simple form:

$\mathcal{Z}=f(X,A)=softmax(\widehat{A}ReLU(\widehat{A}XW^{(0)})W^{(1)})$ (2)

Here, $W^{0}\in R^{C\times H}$ is an input-to-hidden weight matrix for a
hidden layer with H feature maps, while $W^{(1)}\in R^{H\times F}$ is a
hidden-to-output weight matrix. The softmax activation function, defined as
$softmax(x_{i})=\frac{1}{z}exp(x_{i})$ with $\mathcal{Z}=\sum_{i}exp(x_{i})$,
is applied row-wise.

The decoder aggregates pairwise node representations as link representations
to decode the graph. There are several decoders in previous literature, such
as inner product or a neural network. We define the structure decoder
$h_{\omega}$ with parameters $\omega$ as:

$h_{w}(z_{i},z_{j})=Sigmoid(MLP({{z_{i}}^{T}}\circ z_{j}))$ (3)

where MLP denotes a multilayer perceptron and $\circ$ denotes an element-wise
product.

###  6.4 Loss Calculation

Our loss calculation consists of two parts: local reconstruction loss
$L_{local}$ and global contrastive loss $L_{global}$. For the masked graph, we
divide the edges as remaining edges and masked edges. The masked edges are
selected as positive samples, while the disconnected node’s edges are selected
as negative samples. For the embeddings from the decoder, we calculate their
inner product as the probability of the edge existing.

$\displaystyle\mathcal{L}_{Local}=-(\frac{1}{|\varepsilon^{+}|}\sum_{(u,v)\in\varepsilon^{+}}\log{h_{w}(z_{u},z_{v})}$
(4)
$\displaystyle+\frac{1}{|\varepsilon^{-}|}\sum_{(u^{{}^{\prime}},v^{{}^{\prime}})\in\varepsilon^{-}}\log{(1-h_{w}(z_{u^{{}^{\prime}}},z_{v^{{}^{\prime}}}))})$

where $\mathcal{Z}$ is the graph embedding result from the encoder;
$\varepsilon^{+}$ is a set of positive edges while $\varepsilon^{-}$ is a set
of negative edges sampled from the graph.

Further, we calculate the distance between the two representations
$(Z,\widehat{Z})$ as the global contrastive loss. Specifically, we leverage
the MSE to normalize the loss value into the range of $[0,1]$ to facilitate
model optimization.

$\mathcal{L}_{Global}=\frac{\sum_{i=1}^{N}(z_{i}-\widehat{z}_{i})^{2}}{N}$ (5)

Finally, we combine the global loss and local loss into the total loss and use
gradient descent to minimize it.

$\mathcal{L}_{Total}=\mathcal{L}_{Local}+\alpha\mathcal{L}_{Global}$ (6)

Where $\alpha$ denotes a non-negative hyperparameter trading off two terms.

##  7 UEware Detecting

Figure 8: The design of UEware detector.

In the above sections, the system has constructed scene graph and extracted
scene graph representation. In this section, we describe the design and
implementation of UEware detector, especially the classifier.

###  7.1 Module Overview

The UEware detector leverages the self-supervised representation learning
[41], which is widely adopted in previous studies [58, 33]. In detail, it
consists of two stages: self-supervision training task, and downstream
training task, see Figure 8. The self-supervised training task refers to the
algorithm in the previous scene graph feature extractor (see Section 6),
however, their inputs and outputs are different. In detail, the scene graph
feature extractor accepts the scene graph topology $\mathcal{G}$ and the UI
attributes $X$ to trains the scene graph encoder $f_{\theta}$. But the self-
supervision training task accepts the APK relation graph $\mathcal{H}$ and the
APK feature $X$, and trains the encoder $f_{\psi}$. Referring to previous
studies [69], the APK relation graph $\mathcal{H}$ is an undirected graph,
while the node of the graph is APK, and the edge of the graph is the overlap
strong features (_i.e._ , PackageName, AppName, signature) between APKs.
Meanwhile, the APK feature $X$ is the scene graph representation produced by
encoder $f_{\theta}$.

And the downstream task uses the encoder $f_{\psi}$ and to train the
classifier $q_{\psi}$ for UEware detection.

###  7.2 Classifier

The APK encoder $f_{\psi}$ learned from self-supervision training is set
frozen and directly introduced into the downstream task. According to this
frozen encoder, the downstream task then calculates the $\mathcal{Z}$.
Finally, the classifier $q_{\psi}$ (also called the downstream decoder) is
trained based on the labeled dataset. In this study, we leverage a linear
classifier (_i.e._ , a logistic regression model) and the labeled information
is the app types (_i.e._ , gambling game, porn trading, investment scam,
miscellaneous and legitimate apps). Specifically, the detection task decoder
parameter is calculated as:

$\mathcal{\psi}=argmin\mathcal{L}_{sup}(f_{\theta},q_{\psi},\mathcal{H},y)$
(7)

where $\mathcal{H}$ is the APK relation graph and y is the label of UEware.

In the end, when input test APKs, the DeUEDroid first combine the test APKs
and training APKs together to construct a new graph $\mathcal{H}$. And then,
the DeUEDroid labels the test APKs through the encoder $f_{\psi}$ and decoder
$q_{\psi}$.

##  8 Evaluation

In this section, we evaluate the performance of DeUEDroid based on the
following three research questions:

  * •

RQ1: How effective is DeUEDroid in scene graph construction?

  * •

RQ2: How effective is DeUEDroid in UEware detection?

  * •

RQ3: How effective and efficient is DeUEDroid in large-scale UEware detection?

###  8.1 Evaluation Setup

For RQ1, we investigate the capability of scene graph construction. To
evaluate the capability, we build up the Open-source Dataset, consisting of
$20$ open-source self-developed apps and $3$ real-world open-source apps.
Specifically, we self-developed $5$ initial apps as our ground-truth
benchmark, which covers different transitions (_i.e._ , the transitions
between activity - activity, activity - fragment, fragment - fragment, and
navigation) and widgets. Then, to investigate the anti-obfuscation capability,
we perform popular obfuscation techniques (_i.e._ , rename [5], code [11],
reflect [16]) on the initial $5$ apps to generate another $15$ obfuscated
apps. We claim that this solution is the only way to accurately understand the
ground truth of transitions and widgets, and this solution has been widely
used in previous studies [22]. In addition, to strengthen the conviction of
our experiments, we additionally compare the SOTA work IC3 [50] and analyze
several famous open-source apps (_i.e._ , org.woheller69.wather
444https://f-droid.org/en/packages/org.woheller69.weather,
site.leos.setter555https://f-droid.org/en/packages/site.leos.setter,de.digisocken.antherrss
666https://f-droid.org/en/packages/de.digisocken.anotherrss). Note that there
are some studies [22, 23] mentioned about static transition identification or
imprint generation, we have no way to compare with them since they do not
release code or dataset.

Dataset | Component | Setup Time | Detail | Number
---|---|---|---|---
Open-Source Dataset | Self-Developed | July, 2022 | No Obfuscation Apps | 5
Renaming Obfuscation Apps | 5
Code Obfuscation Apps | 5
Reflect Obfuscation Apps | 5
Real-World | 2021-2022 | site.leos.setter | 1
de.digisocken.antherrss | 1
org.woheller69.weather | 1
Total |  | 23
Ground-Truth Dataset | UEware | June, 2022 | Gambling Game | $470$
Porn | $497$
Investment Scam | $300$
Miscellaneous | $453$
legitimate apps | June, 2022 | - | $831$
Total |  |  | $2,551$
Large-Scale Dataset | Wild | June-July, 2022 | Apps from websites | $13,460$
Appstore | June-July, 2022 | Apps from AppStore | $10,557$
Total |  |  | $24,017$

TABLE III: The dataset for evaluation.

For RQ2, we evaluate the capability in UEware detection. To the best of our
knowledge, there is no released dateset of UEware. To perform our evaluation,
we first put a lot of effort into building up the Ground-truth Dataset. This
dataset is built up by our group of four members who have worked on easing the
underground economy for at least two years. We first collect the apps from the
wild, and then manually inspect whether these apps are UEware. Specifically,
each app is assigned to four members for them to mark independently. And we
will decide which attribute to apply based on the majority rule. If a
consensus cannot be reached, we will exclude this sample. Finally, the ground-
truth dataset consists of $1,720$ UEware (_i.e._ , $470$ gambling game apps,
$497$ porn apps, $300$ investment scam apps, $453$ miscellaneous) and $831$
legitimate apps. Notably, DeUEDroid is not limited to the UEware types in our
ground-truth dataset. The coverage of DeUEDroid depends on the training
dataset. But in this study, due to the limited time and human resources of our
team, we mainly focus on these most common UEware types. We randomly select
$70$% of them as the training input, $20$% as the validation set, and $10$% as
the test set.

For RQ3, we conduct a large-scale evaluation to test the performance of
DeUEDroid on the real-world large-scale tasks. For this goal, we first
implement a web crawler to collect real-world apps and setup the Large-scale
Dataset. Based on the source of acquisition, we divide these apps into two
categories: AppStore apps and wild apps. The AppStore apps are collected from
formal app markets, such as Mi Store, 360 Software Manager. In contrast, wild
apps are collected from covert channels, such as social platforms or websites.
In total, the large-scale dataset consists of $13,460$ wild apps and $10,557$
market apps. After setup the dataset, we evaluate the DeUEDroid’s performance
by investigating the UEware detection rate, and the time consumption. What’s
more, we perform a measurement on the large-scale dataset based on DeUEDroid
analysis.

In total, we setup three datasets (_i.e._ , open-source dataset, ground-truth
dataset, and large-scale dataset) containing $26,591$ android apps, see
details in Table III. Note that all hardened apps that cannot be analyzed have
been removed from our dataset. To the best of our knowledge, this is the first
large-scale ground-truth UEware dataset, and we will release our datasets.

###  8.2 Implementation

To implement scene graph builder, we perform taint analysis based on Soot [56]
and flowdroid [18]. We decode apps using ApkTool [6], and leverage Frontmatter
[39] for UI analysis. In network imprint analysis, we additionally adopt Java
string analysis techniques [26], and customize the conditions of instantiate.
For scene graph feature extractor and UEware detector, we implement the
algorithm based on the pytorch, with torch geometric, torch sparse, ntorch
cluster, scikit learn and numpy. Our server to analyze these apps has 16 cores
with 2.1GHz CPU, 256GB memory, and 8TB hard drives.

###  8.3 Evluation Result

####  8.3.1 For RQ1

As mentioned in Sec 5, our scene graph builder has two phases: (i) UI widget
identification, and (ii) UI transition determination. Note that the native
widget analysis is implemented by Frontmatter [39], a SOTA GUI analysis
framework that covers $84.7$% native widgets. We only evaluate the
effectiveness of imprint generation for web widgets and UI transition
determination, which are implemented by ourselves.

First, for the imprint generation of the web widget, we list our evaluation
result in Table IV. For the self-developed apps, the token number is clearly
identified by our developers. In total, the App1-App5 have $36$ tokens, such
as IP host, domain name, and keyword. In the end, DeUEDroid identifies $37$
tokens from the self-developed apps, with $3$ false positive and $8$ false
negative (F1-score is $84.3$%). For the real-world apps, we first identify the
real tokens used by their web widgets. In order to guarantee the accuracy of
identification, we combine dynamic and static analysis. Specifically, we first
insert some logging code (_i.e._ , logging.log()) in the source code after the
network API, which does not affect the functionality of the app. Then we run
the app dynamically to generate the log, and also manually analyze the source
code to get the final token. The F1-score of real-world apps are range from
$90.01$% to $95.0$%, which shows that our imprint generation is accurate with
sufficient coverage.

Dataset Component | Token (#) | Identified (F1-score) |
---|---|---|---
Self-Developed App |  |  |
$\qquad\vdash$# No Obfuscation | 36 | 84.3% |
$\qquad\vdash$# Rename Obfuscation | 36 | 84.3% |
$\qquad\vdash$# Code Obfuscation | 36 | 84.3% |
$\qquad\vdash$# Reflect Obfuscation | 36 | 84.3% |
Real-World App |  |  |
$\qquad\vdash$# site.leos.setter | 21 | 95.0% |
$\qquad\vdash$# de.digisocken.anotherrss | 40 | 90.5% |
$\qquad\vdash$# org.woheller69.weather | 43 | 90.1% |

TABLE IV: The evaluation of imprint generation.

Second, for the UI transition determination, we list our evaluation result in
Table V. Specifically, these self-developed apps are designed to be developed
by certain transition types. The App1 to App4 consist of single transition
type (_e.g._ , Activity - Fragment) to evaluate the accuracy of different
transition types, and App5 is implemented by all transition types to mimic the
real development scenario 777The design overview of App5 is showed in Figure 5
in appendix . It can be seen from the evaluation results that IC3 can
accurately identify the transition between Activity, but cannot accurately
identify the transition between Activity and Fragment, nor can it handle the
transition between Fragment and Navigation. What’s more, to the real-world
apps, the IC3 is ineffective and even can not get the result within $30$
minutes. In contrast, DeUEDroid can identify all transition types and is more
accurate than IC3 ($97.6$% vs $57.4$%). To real-world apps, DeUEDroid also
receives high accuracy and even the lowest F1-score is more than $72.7$%.

Finally, we evaluate the anti-obfuscation capability of DeUEDroid (_i.e._ ,
rename, code, reflect obfuscation). The evaluation result shows that DeUEDroid
has an extremely good anti-obfuscation ability, see Table IV and Table V. The
F1-scores of imprint generation ($84.3$%) and UI transition determination
($97.6$%) are not affected by the obfuscation techniques.

Dataset Component | Transition | Identified (F1-score) |
---|---|---|---
Type | # | IC3 | DeUEDroid |
Self-Developed App |  |  |  |  |
$\qquad\vdash$# No Obfuscation | All | 62 | 57.4% | 97.6% |
$\qquad\qquad\vdash$# App1 | Act-Act1 | 13 | 96.0% | 96.3% |
$\qquad\qquad\vdash$# App2 | Act-Frag. | 13 | 76.2% | 92.3% |
$\qquad\qquad\vdash$# App3 | Frag.-Frag. | 13 | 0% | 100% |
$\qquad\qquad\vdash$# App4 | Navigation | 12 | 0% | 100% |
$\qquad\qquad\vdash$# App5 | All | 11 | 62.4% | 100% |
$\qquad\vdash$# Rename Obfuscation | All | 62 | 57.4% | 97.6% |
$\qquad\vdash$# Code Obfuscation | All | 62 | 57.4% | 97.6% |
$\qquad\vdash$# Reflect Obfuscation | All | 62 | 57.4% | 97.6% |
Real-World App |  |  |  |  |
$\qquad\vdash$# site.leos.setter | All | 5 | 0% | 72.7% |
$\qquad\vdash$# de.digisocken.anotherrss | All | 4 | 50% | 80.0% |
$\qquad\vdash$# org.woheller69.weather | All | 12 | -2 | 91.7% |

  * 1

Act. means Activity, and Frag. means Fragment.

  * 2

IC3 timed out within the 30 minute time limit.

TABLE V: The evaluation of UI transition determination. The boldfaced score
denotes the best result.

The results demonstrate the effectiveness of DeUEDroid in scene graph
construction. We further explain the evaluation results. First, since we take
into account all transition types rather than only activity transitions,
DeUEDroid can label all kinds of sensitive APIs and perform a more accurate
algorithm to identify the transition pairs. It results in the high accuracy of
UI transition determination. Second, because the obfuscation (_e.g._ ,
renaming, code obfuscation) has no impact on atomic APIs (_e.g._ , transition
APIs, network APIs), our UI transition determination and imprint generation
are not affected by the obfuscation techniques. The well anti-obfuscation
ability shows our system is enough robust against adversarial. Finally, to
ensure the efficiency of our system, we set a maximum taint depth and it leads
to some omissions of transition and token identification. For example, we show
a mission edge in the evaluation, the mission edge consists of a long call
chain (_i.e._ , onClick() - func1() - func2() - … - func9() - actionStart() -
startActivity()) that beyond our maximum recursion. At the same time, due to
the nature of the static analysis, false positives are inevitable.

Answer RQ1: DeUEDroid is effective in scene graph construction, which can
accurately identify transition pairs (over $72$%) and imprint tokens (over
$90$%). Besides, DeUEDroid is obfuscation-resilient.

####  8.3.2 For RQ2

|  | Manifest 1 | Manifest + Web widget | Manifest + Native widget | Manifest + ATG | Manifest + Scene Graph
---|---|---|---|---|---|---
Supervised | LR | $47.57_{\pm 0.35}$ | $47.95_{\pm 0.13}$ | $58.40_{\pm 0.22}$ | $52.54_{\pm 0.17}$ | $60.72_{\pm 0.16}$
GAT | $49.92_{\pm 0.21}$ | $49.19_{\pm 0.51}$ | $58.67_{\pm 0.07}$ | $53.47_{\pm 0.20}$ | $62.55_{\pm 0.60}$
GraphSAGE | $54.81_{\pm 0.20}$ | $55.87_{\pm 0.2}$ | $62.59_{\pm 0.19}$ | $64.29_{\pm 0.22}$ | $71.23_{\pm 0.20}$
GCN | $55.96_{\pm 0.20}$ | $56.97_{\pm 0.11}$ | $64.34_{\pm 0.37}$ | $65.70_{\pm 0.31}$ | $71.28_{\pm 0.25}$
Self-supervised | GAE | $56.39_{\pm 0.23}$ | $57.54_{\pm 0.32}$ | $66.48_{\pm 0.23}$ | $71.88_{\pm 0.12}$ | $75.44_{\pm 0.26}$
DeUEDroid (Ours) | $\textbf{59.22}_{\pm 0.22}$ | $\textbf{59.55}_{\pm 0.28}$ | $\textbf{70.22}_{\pm 0.15}$ | $\textbf{74.41}_{\pm 0.23}$ | $\textbf{77.70}_{\pm 0.19}$

TABLE VI: The UEware classification accuracy (%) of different features and
algorithm. In each column, the boldfaced score denotes the best result.

To answer RQ2, we evaluate the effective of DeUEDroid in UEware detection on
ground-truth dataset. First, we evaluate the effectiveness of malware
detection techniques in UEware detection. We randomly select $100$ UEware from
our ground-truth dataset, and upload them to VirusTotal, the largest online
malware detection platform. In total, there are $63$ security vendors in
VirusTotal platform. However, after their analysis, we find that only $17$
apps have caused more than $2$ vendor warnings, while the rest are either
considered benign or cause only one vendor warning. What’s more, the sandbox
checking does not find any malicious behaviors in the input apps. This
phenomenon proves that the malware detection techniques are inefficient for
UEware detection and have high false negative (over $80$%), which justifies
our motivation in Sec 3. Therefore, in the following evaluations, we no longer
compare previous malware detection studies due to the large differences in
tasks.

To prove the effectiveness of our system, we need to evaluate our system from
two perspectives: (i) the effectiveness of scene graph features. (ii) the
effectiveness of DeUEDroid algorithm. In order to prove the effectiveness of
the scene graph features, we take a comparative experiment and divide the
scene graph features into four parts: (i) Manifest. The Manifest feature
consists of the basic app Manifest information (_i.e._ , permission,
certificate, size, app name, package name). (ii) Native widget. The Native
widget features include XML widgets, dynamic loading widgets and their
attributes (see Section 5.2). (iv) Web widget. The web widget features consist
of the network imprint tokens (see Section 5.2). (iii) ATG. The ATG consists
of the activities/fragments and their transition pairs (see Section 5.3). And
we perform multiple sets of alignment measures, _i.e._ , Manifest, Manifest +
Native widget, Manifest + Web widget, Manifest + ATG, and Manifest + scene
graph. Note that scene graph is the cooperation of the Native widget, Web
widget, and ATG (see Section 5). What’s more, to evaluate the effectiveness of
our algorithm, we further compare other SOTA supervised algorithms (_i.e._ ,
LR, GraphSAGE, GCN [25], GAT [57]) and self-supervised algorithms (_i.e._ ,
GAE) with our algorithm. We closely follow the linear evaluation scheme as
introduced in [58] and report the classification accuracy of our experiment in
Table VI.

Figure 9: The effect of Alpha and mask ratio to DeUEDroid

First of all, DeUEDroid achieves $77.70$% accuracy rate based on the scene
graph. This proves that our algorithm is effective in UEware detection.
Specifically, we further observe the effectiveness of scene graph features and
DeUEDroid algorithm, respectively.

To observe the effectiveness of scene graph features, we compare the accuracy
rate between column#3 and column#4-6. The result shows that these features can
improve the detection performance of all algorithms individually. In addition,
from the comparison between column#7 and column#4-6, the scene graph features
perform much better than all individual features. It further demonstrates that
scene graph can synthesize these individual features well, with outstanding
accuracy improvement across all algorithms (ranging from $12.63$% to
$19.05$%). The effectiveness of the scene graph features is shown by the
outstanding improvement of the comparative experiments.

To observe the effectiveness of DeUEDroid algorithm, we comparing the accuracy
scores of DeUEDroid line#7 with other algorithms line#2-6. And our system
achieves leading performance among all algorithms, which on average exceeds
the supervised algorithm $11.26$% and exceeds GAE $2.26$%. Note that the
comparison with GAE proves that our Mask strategy can improve the robustness
of our detection model. This proves that our algorithm is effective and can
better handle the scene graph information.

Further, since we introduce the GAE and masking strategy, we show the Alpha
and mask ratio effect of our detection results in Figure 9. From the alpha
ratio effect in Figure 9, we can see that by increasing the alpha ratio from
$0.0001$ to $100$, the accuracy first smoothly improves to $78.43$% and
declines then to $77.61$%. The gap of ratio influence fluctuates very little,
only around $0.82$%. And the same to the masking ratio, the ratio influence
gap is around $1.26$%. The ratio effect indicates that our model is very
stable and insensitive to the influence of hyper-parameters, which can
guarantee stable detection results.

To show more details, we present our case study in appendix 16.

Answer RQ2: DeUEDroid is effective in UEware detection, achieving $77.70$%
accuracy rate. Specifically, the scene graph features improve the detection
capability of all algorithms (ranging from 12.63% to 19.05%), and the
DeUEDroid algorithm also has a better performance than others STOA algorithms.
Besides, DeUEDroid is stable and insensitive to the hyper-parameters.

Figure 10: Detection results on the large-scale dataset.

####  8.3.3 For RQ3

We perform our system on the large-scale dataset to evaluate the DeUEDroid in
the reality. We first observe the detection result and the performance of
DeUEDroid. And then, we conduct a measurement on the scene graph.

Detection Result. After demonstrating the detection effectiveness of
DeUEDroid, we perform our system on the large-scale dataset to evaluate the
detection capability on real-world large-scale tasks. The detection results
are astounding, as shown in Figure 10. First, we observe the detection results
of wild apps. There are more than half of apps ($61$%) in the wild are UEware
(_i.e._ , $12$% of gambling, $9$% of porn, $19$% of investment scam, and $21$%
of miscellaneous), and only $39$% apps are legitimate ones. Then we observe
the detection results of the AppStore apps. Unexpectedly, we find the apps in
the AppStore are not completely safe. Specifically, there are $21$% apps in
the AppStore are UEware (_i.e._ , $2$% gambling game, $1$% porn, $8$%
investment scam and $10$% miscellaneous).

To further confirm the effect of our system, we additional select detected
UEware from the two dataset components for manual review. In the wild dataset,
we review a total of $200$ UEware, $156$ apps are consistent with the manual
review results, and the main inconsistency occurred in the judgment of
investment scam and miscellaneous. In addition, we review $200$ detected
UEware in the AppStore dataset, $132$ apps are consistent with the manual
inspection results. In conclusion, the manual review shows DeUEDroid is
effective, with the accuracy above $72$%.

Further, we explain the reason why the classification accuracy of the large-
scale dataset is lower than the ground-truth dataset (5% lower than the
ground-truth dataset). Due to the huge difference between the UEware
distribution of the ground-truth dataset and the large-scale dataset, the Out-
of-distribution (OOD) of our detection model is unavoidable, and thus causes a
lower accuracy rate.

Finally, the detection result shows that DeUEDroid is effective for large-
scale UEware detection tasks (achieving over 72% accuracy rate after manual
investigation). Even though the app stores have manually checked their apps,
we still find that there are some undetected UEware (21% of all apps) in
AppStore.

Figure 11: Time consumption distribution.

Performance. In addition, we evaluate the time consumption of our system.
Overall, each app costs about $213$ seconds on average, ranging from $9$
seconds to $2,347$ seconds. We show the average time consumption of different
app sizes in Figure 11. We can see that the time consumption increases with
the size of the app. However, the time increase is stable that the time
consumption fluctuation in the range of $15$M-$57$M is within $67$s. The
performance results show that DeUEDroid is large-scale resilient, which is
important for real-world tasks.

We further explain that the stable time consumption is attributed to scene
graph based detection method. Since the app size is mainly determined by its
resource files, the increase in source code (especially activity-level) is
modest. Our detection method is less affected by app size, resulting the
stable time consumption.

Measurement. In Section 3, we have an insight that the UEware are different
from legitimate apps, and opt to serve as single-purpose applications. To
confirm our insight, we investigate the scene graphs produced by our system,
including the number of transition pairs, the widgets, and the imprint tokens,
shown in Figure 12. Specifically, the UEware are the detected ones from the
large-scale dataset, while the legitimate apps are the remaining ones.

The investigation shows that the services of UEware and legitimate apps are
significantly different in statistics. First, the median of transition pairs
is only $71$ in UEware, while there is $91$ in legitimate apps. And the
average transition pairs in legitimate apps are twice as many as UEware ($22$
in legitimate apps vs. $11$ in UEware). Second, the average number of widgets
owned by legitimate apps is much higher than that of UEware ($227$ in
legitimate apps vs. $29$ in UEware). Finally, turning to the network imprint.
We find that their hybrid ratios are nearly the same ($30$% in legitimate apps
vs. $29$% in UEware). But the average number of tokens owned by legitimate
apps is higher than that of UEware ($211$ in legitimate apps vs. $121$ in
UEware). In general, when a service is complex and multi-purpose, more
transition pairs, widgets, and imprint tokens are required. So the statistical
result proves that UEware is more simple.

Figure 12: The comparison of scene graph between UEware and legitimate apps.

Answer RQ3: DeUEDroid is effective and efficient in large-scale detection. One
one side, the detection accuracy is $72$% after manually investigating $400$
detected UEware in AppStore and wild. On the other side, DeUEDroid is large-
size resilient. Besides, the result suggests that $61$% apps in the wild and
$21$% apps in the AppStore are UEware.

##  9 Discussion

Scene Graph Construction. As scene graph is built using static analysis, apps
may leverage app harden techniques to disrupt static analysis. In addition,
even though the static analysis takes into account the major factors
introduced by Android (_i.e._ , multi-threading, lifecycle, and ICCs), apps
may evade our analysis by invoking sensitive APIs via reflections, native
libraries, and Jsbridge. In the future, we plan to incorporate dynamic
analysis techniques to deal with the app harden techniques, reflections, and
native libraries. Moreover, the static analysis can produce incorrect
associations between activities and UIs due to its overapproaximations. We
plan to mitigate such issues using dynamic techniques to filter out false
associations.

Network Imprint. Since DeUEDroid is built upon static techniques, it uses
network imprints to identify the network features rather than fetching the
real remote resources. While the network imprints are highly malleable, they
are still inaccurate compared to real remote resources. In the future, we plan
to combine dynamic analysis techniques to capture real network remote
resources. And further, use the network discovery technology to fetch more
network information.

Anti Adversary. Our model is learned from the behaviors of the ground-truth
UEware dataset. To avoid our detection, adversaries may download our dataset
and find patterns of behavior that are not covered in it. For example, they
can use native reflections and specially designed activity transformations to
mislead our detection model. And we admit that these adversaries against the
dataset cannot be prevented due to our limited dataset. Since the dataset is
collected manually by our team, the number and coverage of samples are
limited.

However, we claim that enterprises can supplement the dataset by themselves to
improve the coverage, thereby improving the accuracy and avoiding attacks on
the model coverage. What’s more, to improve our model robustness, we have
introduced many techniques, such as anti-obfuscation, and Mask strategy. Due
to our anti-adversary techniques, designing a UEware pretending to be normal
from the learned model are non-trivial. As a result, our technique
significantly raises the bar for potential attacks.

##  10 Related Work

Android Static Analysis. To better analyze the Android app, existing works
[18, 59, 63] have made a lot of work on building up the call graphs. Since the
complex Android environment, they connect edges by enumerating all possible
combinations within lifecycle methods. Due to the addition of taint analysis,
it consumes too much time and is unavoidable to have a high false positive
when introduced in UI handler analysis. Meanwhile, to build up an accurate
call graph, the ICC requires additional solutions. There are some works[49,
51, 50] focused on the ICC analysis by leveraging the taint analysis and
program analysis techniques. And some works [70] leveraged machine learning
approaches. In addition, considering the impact of multi-threading, some works
[51, 62] connected certain multi-thread handles, so as to better improve the
accuracy of the call graph. Then based on the call graph, Azim et al. [19]
first present the activity transition graph, Chen et al. [22] took into
account the inner class extra. However, their activity transition graphs
lacked consideration for system-level callback listener and fragment
navigation. Our static analysis is based on the above-mentioned works, and has
supplemented some shortcomings.

Android GUI Analysis. Yang et al. [63, 64] leveraged context-sensitive
analysis of callback methods and developed a client analysis that builds a
static GUI model and window transition graph. StoryDroid [22] recorded all XML
layout code and dynamic view binding code, rebuild a new app based on this
code, and finally took a snapshot. StoryDroid used these screenshots as the
representation of the GUI. AppIntent [65] used the taint analysis from the UIs
to analyze the location that may cause sensitive data leakage. AsDroid [36]
compares the GUI attribution and code behavior to find out the stealthy
behavior against the normal GUI attribution. UIPicker [48] extracted UI layout
resources and program code, and further analyzed them for the sensitive
information locations. PERUIM [43] focused on the permissions used behind the
UIs, and connected the UIs with their handlers.

Malware Detection. Arora et al. [17] proposed a detection model by extracting
the permission pairs from the Manifest file. Chen et al. [20] characterized
existing Android ransomware and proposed a real-time detection system by
monitoring the user interface widgets. DeepReflect [28] focused on malicious
functionalities based upon binary, improved the robust of malware detection.
Zhang et al. [68] proposed a enhanced framework to help AI-based module detect
evolved Android malware.

##  11 Conclusion

In this study, we have proposed a novel UEware detection approach based on the
scene graph. This approach first builds scene graph for the training APKs, and
then extracts features of scene graph. After that, it applies a machine
learning method to train the classifier to detect UEware. We then proposed and
implemented a prototype system named DeUEDroid to perform the detection. Our
evaluation demonstrates that DeUEDroid is efficient and effective. First,
DeUEDroid can accurately construct the scene graph, which can accurately
identify transition pairs (over 72%) and imprint tokens (over 90%). Then the
evaluation result shows that DeUEDroid can detect discrepancies with accuracy
values 77.70% for demystifying gambling game, porn, underground loan,
financial scam, and legitimate apps. Our system has a significant effect on
improving detection accuracy. Finally, DeUEDroid is effective and efficient
for large-scale tasks. By using DeUEDroid, we found that UEware are prevalent,
_i.e._ , $61$% apps in the wild and $21$% apps in the app stores are UEware
(with over 72% accuracy after the manual investigation).

## References

  * [1] https://www.gamblingsites.org/apps/popularity, June 2012.  Accessed June, 2012.
  * [2] https://developer.android.com/guide/components/activities/intro-activities, November 2021.  Accessed November 23, 2021.
  * [3] Bbc report about romance scammer.  https://edition.cnn.com/2021/02/21/us/losses-to-romance-scams-trnd/index.html, January 2021.  Accessed January 1, 2021.
  * [4] China gambling report.  http://english.www.gov.cn/statecouncil/ministries/202101/06/content_WS5ff570dac6d0f7257694358b.html, January 2021.  Accessed January 1, 2021.
  * [5] Android studio r8.  https://developer.android.com/studio/build/shrink-code?hl=zh-cn, June 2022\.  Accessed June 4, 2022.
  * [6] Apktool-a tool for reverse engineering android apk files.  https://ibotpeaches.github.io/Apktool/, June 2022.  Accessed June 4, 2022.
  * [7] Apps for economy.  https://42matters.com/blog/?p=the-state-of-the-app-economy-and-app-markets, June 2022.  Accessed June 4, 2022.
  * [8] Fragment navigation.  https://developer.android.com/guide/navigation/navigation-getting-started, June 2022.  Accessed June 4, 2022.
  * [9] Hybrid app percentage in appstore.  https://venturebeat.com/2020/11/23/why-74-of-the-top-50-retail-apps-are-hybrid-apps-not-native-apps/, June 2022.  Accessed August 8, 2022.
  * [10] India loan scam.  https://www.bbc.com/news/business-61564038, June 2022.  Accessed June 4, 2022.
  * [11] Reflect obfuscation technique.  https://allatori.com, June 2022.  Accessed June 8, 2022.
  * [12] State of mobile in 2022.  https://www.data.ai/en/go/state-of-mobile-2022, June 2022.  Accessed June 8, 2022.
  * [13] Us gambling report.  https://www.forbes.com/sites/willyakowicz/2022/02/15/us-gambling-revenue-hit-record-53-billion-in-2021/?sh=7a27d75d7f50, June 2022.  Accessed June 6, 2022.
  * [14] Us scam app report.  https://indianexpress.com/article/technology/tech-news-technology/apple-app-store-84-scam-applications-100-million-dollars-8035829, June 2022.  Accessed June 6, 2022.
  * [15] Faraz Ahmed, Haider Hameed, M Zubair Shafiq, and Muddassar Farooq.  Using spatio-temporal information in api calls with machine learning algorithms for malware detection.  In Proceedings of the 2nd ACM Workshop on Security and Artificial Intelligence, pages 55–62, 2009.
  * [16] Simone Aonzo, Gabriel Claudiu Georgiu, Luca Verderame, and Alessio Merlo.  Obfuscapk: An open-source black-box obfuscation tool for android apps.  SoftwareX, 11:100403, 2020.
  * [17] Anshul Arora, Sateesh K Peddoju, and Mauro Conti.  Permpair: Android malware detection using permission pairs.  IEEE Transactions on Information Forensics and Security, 15:1968–1982, 2019.
  * [18] Steven Arzt, Siegfried Rasthofer, Christian Fritz, Eric Bodden, Alexandre Bartel, Jacques Klein, Yves Le Traon, Damien Octeau, and Patrick McDaniel.  Flowdroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for android apps.  Acm Sigplan Notices, 49(6):259–269, 2014.
  * [19] Tanzirul Azim and Iulian Neamtiu.  Targeted and depth-first exploration for systematic testing of android apps.  In Proceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications, pages 641–660, 2013.
  * [20] Jing Chen, Chiheng Wang, Ziming Zhao, Kai Chen, Ruiying Du, and Gail-Joon Ahn.  Uncovering the face of android ransomware: Characterization and real-time detection.  IEEE Transactions on Information Forensics and Security, 13(5):1286–1300, 2017.
  * [21] Kai Chen, Peng Wang, Yeonjoon Lee, XiaoFeng Wang, Nan Zhang, Heqing Huang, Wei Zou, and Peng Liu.  Finding unknown malice in 10 seconds: Mass vetting for new threats at the $\\{$Google-Play$\\}$ scale.  In 24th USENIX Security Symposium (USENIX Security 15), pages 659–674, 2015.
  * [22] Sen Chen, Lingling Fan, Chunyang Chen, Ting Su, Wenhe Li, Yang Liu, and Lihua Xu.  Storydroid: Automated generation of storyboard for android apps.  In 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE), pages 596–607. IEEE, 2019.
  * [23] Yi Chen, Wei You, Yeonjoon Lee, Kai Chen, XiaoFeng Wang, and Wei Zou.  Mass discovery of android traffic imprints through instantiated partial execution.  In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 815–828, 2017.
  * [24] Zhuo Chen, Lei Wu, Jing Cheng, Yubo Hu, Yajin Zhou, Zhushou Tang, Yexuan Chen, Jinku Li, and Kui Ren.  Lifting the grey curtain: A first look at the ecosystem of culpritware.  arXiv preprint arXiv:2106.05756, 2021.
  * [25] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh.  Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks.  In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 257–266, 2019.
  * [26] Aske Simon Christensen, Anders Møller, and Michael I. Schwartzbach.  Precise analysis of string expressions.  In Proc. 10th International Static Analysis Symposium (SAS), volume 2694 of LNCS, pages 1–18. Springer-Verlag, June 2003.  Available from http://www.brics.dk/JSA/.
  * [27] Feng Dong, Haoyu Wang, Li Li, Yao Guo, Tegawendé F Bissyandé, Tianming Liu, Guoai Xu, and Jacques Klein.  Frauddroid: Automated ad fraud detection for android apps.  In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pages 257–268, 2018.
  * [28] Evan Downing, Yisroel Mirsky, Kyuhong Park, and Wenke Lee.  Deepreflect: Discovering malicious functionality through binary reconstruction.  In 30th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 21), 2021.
  * [29] William Enck, Machigar Ongtang, and Patrick McDaniel.  On lightweight mobile phone application certification.  In Proceedings of the 16th ACM conference on Computer and communications security, pages 235–245, 2009.
  * [30] Parvez Faruki, Vijay Laxmi, Ammar Bharmal, Manoj Singh Gaur, and Vijay Ganmoor.  Androsimilar: Robust signature for detecting variants of android malware.  Journal of Information Security and Applications, 22:66–80, 2015\.
  * [31] Tatiana Frenklach, Dvir Cohen, Asaf Shabtai, and Rami Puzis.  Android malware detection via an app similarity graph.  Computers & Security, 109:102386, 2021.
  * [32] Yuhao Gao, Haoyu Wang, Li Li, Xiapu Luo, Guoai Xu, and Xuanzhe Liu.  Demystifying illegal mobile gambling apps.  In Proceedings of the Web Conference 2021, pages 1447–1458, 2021\.
  * [33] Kaveh Hassani and Amir Hosein Khasahmadi.  Contrastive multi-view representation learning on graphs.  In International Conference on Machine Learning, pages 4116–4126. PMLR, 2020.
  * [34] Geoffrey E Hinton and Richard Zemel.  Autoencoders, minimum description length and helmholtz free energy.  Advances in neural information processing systems, 6, 1993.
  * [35] Yangyu Hu, Haoyu Wang, Yajin Zhou, Yao Guo, Li Li, Bingxuan Luo, and Fangren Xu.  Dating with scambots: Understanding the ecosystem of fraudulent dating applications.  IEEE Transactions on Dependable and Secure Computing, 2019.
  * [36] Jianjun Huang, Xiangyu Zhang, Lin Tan, Peng Wang, and Bin Liang.  Asdroid: Detecting stealthy behaviors in android applications by user interface and program behavior contradiction.  In Proceedings of the 36th International Conference on Software Engineering, pages 1036–1046, 2014.
  * [37] TaeGuen Kim, BooJoong Kang, Mina Rho, Sakir Sezer, and Eul Gyu Im.  A multimodal deep learning method for android malware detection using various features.  IEEE Transactions on Information Forensics and Security, 14(3):773–788, 2018.
  * [38] Thomas N Kipf and Max Welling.  Variational graph auto-encoders.  arXiv preprint arXiv:1611.07308, 2016.
  * [39] Konstantin Kuznetsov, Chen Fu, Song Gao, David N Jansen, Lijun Zhang, and Andreas Zeller.  What do all these buttons do? statically mining android user interfaces at scale.  arXiv preprint arXiv:2105.03144, 2021.
  * [40] Jin Li, Lichao Sun, Qiben Yan, Zhiqiang Li, Witawas Srisa-An, and Heng Ye.  Significant permission identification for machine-learning-based android malware detection.  IEEE Transactions on Industrial Informatics, 14(7):3216–3225, 2018\.
  * [41] Jintang Li, Ruofan Wu, Wangbin Sun, Liang Chen, Sheng Tian, Liang Zhu, Changhua Meng, Zibin Zheng, and Weiqiang Wang.  Maskgae: Masked graph modeling meets graph autoencoders.  arXiv preprint arXiv:2205.10053, 2022.
  * [42] Li Li, Tegawendé F Bissyandé, and Jacques Klein.  Simidroid: Identifying and explaining similarities in android apps.  In 2017 IEEE Trustcom/BigDataSE/ICESS, pages 136–143. IEEE, 2017\.
  * [43] Yuanchun Li, Yao Guo, and Xiangqun Chen.  Peruim: Understanding mobile application privacy with permission-ui mapping.  In Proceedings of the 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing, pages 682–693, 2016.
  * [44] Bin Liu, Suman Nath, Ramesh Govindan, and Jie Liu.  $\\{$DECAF$\\}$: Detecting and characterizing ad fraud in mobile apps.  In 11th USENIX symposium on networked systems design and implementation (NSDI 14), pages 57–70, 2014.
  * [45] Chao Liu, Chen Chen, Jiawei Han, and Philip S Yu.  Gplag: detection of software plagiarism by program dependence graph analysis.  In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 872–881, 2006.
  * [46] Collins W Munyendo, Yasemin Acar, and Adam J Aviv.  “desperate times call for desperate measures”: User concerns with mobile loan apps in kenya.  In 2022 IEEE Symposium on Security and Privacy (SP), pages 1521–1521. IEEE Computer Society, 2022.
  * [47] Nicole L Muscanell, Rosanna E Guadagno, and Shannon Murphy.  Weapons of influence misused: A social influence analysis of why people fall prey to internet scams.  Social and Personality Psychology Compass, 8(7):388–396, 2014.
  * [48] Yuhong Nan, Min Yang, Zhemin Yang, Shunfan Zhou, Guofei Gu, and XiaoFeng Wang.  Uipicker: User-input privacy identification in mobile applications.  In 24th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 15), pages 993–1008, 2015.
  * [49] Damien Octeau, Somesh Jha, Matthew Dering, Patrick McDaniel, Alexandre Bartel, Li Li, Jacques Klein, and Yves Le Traon.  Combining static analysis with probabilistic models to enable market-scale android inter-component analysis.  In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 469–484, 2016.
  * [50] Damien Octeau, Daniel Luchaup, Matthew Dering, Somesh Jha, and Patrick McDaniel.  Composite constant propagation: Application to android inter-component communication analysis.  In 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering, volume 1, pages 77–88. IEEE, 2015.
  * [51] Damien Octeau, Patrick McDaniel, Somesh Jha, Alexandre Bartel, Eric Bodden, Jacques Klein, and Yves Le Traon.  Effective inter-component communication mapping in android: An essential step towards holistic security analysis.  In 22nd $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 13), pages 543–558, 2013.
  * [52] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang.  Dropedge: Towards deep graph convolutional networks on node classification.  arXiv preprint arXiv:1907.10903, 2019.
  * [53] Atanas Rountev and Dacong Yan.  Static reference analysis for gui objects in android software.  In Proceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization, pages 143–153, 2014.
  * [54] Borja Sanz, Igor Santos, Carlos Laorden, Xabier Ugarte-Pedrero, Pablo Garcia Bringas, and Gonzalo Álvarez.  Puma: Permission usage to detect malware in android.  In International Joint Conference CISIS’12-ICEUTE 12-SOCO 12 Special Sessions, pages 289–298. Springer, 2013.
  * [55] Silvia Sebastian and Juan Caballero.  Towards attribution in mobile markets: Identifying developer account polymorphism.  In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 771–785, 2020.
  * [56] Raja Vallée-Rai, Etienne Gagnon, Laurie Hendren, Patrick Lam, Patrice Pominville, and Vijay Sundaresan.  Optimizing java bytecode using the soot framework: Is it feasible?  In International conference on compiler construction, pages 18–34. Springer, 2000.
  * [57] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  arXiv preprint arXiv:1710.10903, 2017.
  * [58] Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm.  Deep graph infomax.  ICLR (Poster), 2(3):4, 2019.
  * [59] Fengguo Wei, Sankardas Roy, and Xinming Ou.  Amandroid: A precise and general inter-component data flow analysis framework for security vetting of android apps.  In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pages 1329–1341, 2014.
  * [60] Michelle Y Wong and David Lie.  Intellidroid: a targeted input generator for the dynamic analysis of android malware.  In NDSS, volume 16, pages 21–24, 2016.
  * [61] Dong-Jie Wu, Ching-Hao Mao, Te-En Wei, Hahn-Ming Lee, and Kuo-Ping Wu.  Droidmat: Android malware detection through manifest and api calls tracing.  2012 Seventh Asia Joint Conference on Information Security, pages 62–69, 2012.
  * [62] Shengqu Xi, Shao Yang, Xusheng Xiao, Yuan Yao, Yayuan Xiong, Fengyuan Xu, Haoyu Wang, Peng Gao, Zhuotao Liu, Feng Xu, et al.  Deepintent: Deep icon-behavior learning for detecting intention-behavior discrepancy in mobile apps.  In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 2421–2436, 2019.
  * [63] Shengqian Yang, Dacong Yan, Haowei Wu, Yan Wang, and Atanas Rountev.  Static control-flow analysis of user-driven callbacks in Android applications.  In International Conference on Software Engineering, pages 89–99, 2015.
  * [64] Shengqian Yang, Hailong Zhang, Haowei Wu, Yan Wang, Dacong Yan, and Atanas Rountev.  Static window transition graphs for Android.  In IEEE/ACM International Conference on Automated Software Engineering, pages 658–668, 2015.
  * [65] Zhemin Yang, Min Yang, Yuan Zhang, Guofei Gu, Peng Ning, and X Sean Wang.  Appintent: Analyzing sensitive data transmission in android for privacy leakage detection.  In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pages 1043–1054, 2013.
  * [66] Zhenlong Yuan, Yongqiang Lu, Zhaoguo Wang, and Yibo Xue.  Droid-sec: deep learning in android malware detection.  In Proceedings of the 2014 ACM conference on SIGCOMM, pages 371–372, 2014.
  * [67] Fangfang Zhang, Heqing Huang, Sencun Zhu, Dinghao Wu, and Peng Liu.  Viewdroid: Towards obfuscation-resilient mobile application repackaging detection.  In Proceedings of the 2014 ACM conference on Security and privacy in wireless & mobile networks, pages 25–36, 2014.
  * [68] Xiaohan Zhang, Yuan Zhang, Ming Zhong, Daizong Ding, Yinzhi Cao, Yukun Zhang, Mi Zhang, and Min Yang.  Enhancing state-of-the-art classifiers with api semantics to detect evolved android malware.  In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 757–770, 2020.
  * [69] Yutao Zhang, Fanjin Zhang, Peiran Yao, and Jie Tang.  Name disambiguation in aminer: Clustering, maintenance, and human in the loop.  In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1002–1011, 2018.
  * [70] Jinman Zhao, Aws Albarghouthi, Vaibhav Rastogi, Somesh Jha, and Damien Octeau.  Neural-augmented static analysis of android communication.  In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pages 342–353, 2018.

Figure 13: The screenshots of an underground loan App#1. Figure 14: The
screenshots of an underground loan App#2. Figure 15: The screenshots of a
gambling App. Figure 16: The design overview of App5. The edge label 1 means
transition between Activity, 2 means transition between Activity-Fragment, 3
means transition between Fragment.

Case Study To better illustrate the effectiveness of our proposed method, we
show some example details. First, we use the visualization technology TSNE to
show the clustering result through manifest feature (_i.e._ , app name,
package name, certificate, app size), and clustering result through scene
graph, as shown in Figure 17. Specifically, we take two same type apps as an
example (com.a0gq1n.dpoe9, com.a16gpj.y8or7). Their manifest information is
different, which leads to a long distance in the manifest clustering. However,
since their scene graph embeddings are highly similar, we can attribute them
to the same type in scene graph clustering.

Figure 17: The clustering comparison between manifest based and scene graph
based.

Notably, web widget feature is valid for hybrid apps. We show some cases
implemented by a single activity and several webview widgets (_e.g._ antv.com,
chunyuzb.com). These cases cannot be accurately identified by graph topology
and UI widgets, as their implementation relies mainly on webview and lacks
scene graph information (only $3$ transition pairs and $2$ webview widgets).
But since we generated their imprint tokens (_e.g._ , 1080kan.cc,
api/ui/share, 91porn), we can well identify such UEware based on their token
similarity .