# An Android Application Risk Evaluation Framework Based on Minimum Permission
Set Identification

Jianmao Xiao  Shizhan Chen  Qiang He  Zhiyong Feng  Xiao Xue
<EMAIL_ADDRESS>College of Intelligence and Computing, Tianjin
University, Tianjin, China  School of Software and Electrical Engineering,
Swinburne University of Technology, Hawthorn, VIC 3122, Australia

###### Abstract

Android utilizes a security mechanism that requires apps to request permission
for accessing sensitive user data, e.g., contacts and SMSs, or certain system
features, e.g., camera and Internet access. However, Android apps tend to be
overprivileged, i.e., they often request more permissions than necessary. This
raises the security problem of overprivilege. To alleviate the overprivilege
problem, this paper proposes MPDroid, an approach that combines static
analysis and collaborative filtering to identify the minimum permissions for
an Android app based on its app description and API usage. Given an app,
MPDroid first employs collaborative filtering to identify the initial minimum
permissions for the app. Then, through static analysis, the final minimum
permissions that an app really needs are identified. Finally, it evaluates the
overprivilege risk by inspecting the app’s extra privileges, i.e., the
unnecessary permissions requested by the app. Experiments are conducted on
16,343 popular apps collected from Google Play. The results show that MPDroid
outperforms the state-of-the-art approach significantly.

###### keywords:

Permission overprivilege, app risk evaluation, minimum permissions, static
analysis, collaborative filtering

††journal: Journal of Systems and Software

##  1 Introduction

In the past decade, the popularity and ubiquitous use of smartphones have
greatly fueled the growth of mobile application (referred to as app
hereafter). According to
AppBrain111http://developer.Android.com/guide/platform/index.html., as of
September 2018, the number of available apps on Google Play-the world largest
Android app store, has exceeded 2.8 million. Apps are now playing an extremely
important role in our daily life. Many mobile users store a lot of sensitive
and private data on their devices. Such data are at the risk of exposure to
malicious activities, which has become a major vulnerability of the entire
mobile ecosystem [1].

Android has long been a major target of malicious apps [2]. One of its major
vulnerabilities is the permission mechanism [3]. Android’s permission
mechanism requires apps to request permission for accessing sensitive user
data, e.g., contacts and SMSs, or certain system features, e.g., camera and
Internet access. Thus, the security of Android heavily depends on the
effectiveness of this permission mechanism. A major threat is that a malicious
app may furtively request extra permissions for accessing users’ sensitive and
private data. To minimize this threat, some researchers have designed user-
oriented permission prompts to ensure that smartphone users are properly
notified of the permissions requested by apps. However, due to the complexity
of Android’s permission mechanism, most of these efforts have proven to be
ineffective [4] [5]. The main reason is that most users do not fully
understand Android’s permissions mechanism. They often simply ignore the
prompts and accept apps’ requests for permissions without inspecting the
prompts [6]. As a result, apps can easily obtain extra permissions, which
increase the risks of user privacy leaks. This is referred to as the over
privilege problem [7]. A study conducted by Yu et al. [8] shows that more than
80% of Android apps are overprivileged. The vulnerability of Android’s
permission mechanism puts mobile users at the risk of privacy leak in the
mobile ecosystem [9]. This has become one of the major threats to the health
of mobile ecosystem [10]. This threat is made even more serious by benign apps
that are overprivileged by excessively requested permissions [7] [11].

The mainstream approach for enhancing the Android permission mechanism is to
identify over-declared permissions requested by an app [12] [13] [14] [15] and
recommend reasonable permissions for an app [16] [17] [18]. A major and common
limitation of these approaches is that the requested permissions are
considered as the permissions that the app really uses. However, this is not
always true, especially for malicious apps, they often declare more
permissions than they really needs. To address this issue, it is important to
identify the minimum permissions, i.e., permissions that are truly needed by
an app for the implementation of its functionalities. When given the minimum
permission for an app, whether it is a malicious or benign application, the
over-declared permissions can be identified and pruned without impacting the
functionalities of the app.

In this paper, we propose Minimum Permission for Android (MPDroid), an
approach for Android app risk evaluation based on the identification of
minimum permissions. MPDroid identifies the initial minimum permissions for
the target app by inspecting the permissions requested by apps that are
similar to the target app, following the main idea of collaborative filtering-
_if two users (apps) u and v have similar behaviors (functional description),
they will act on other items (permissions) similarly_ [19]. Then, it obtains
the final minimum permissions for the target app by using a functionality
point222The functionality point in this paper refers to functionality topic
which is obtained from the description of the app by LDA model-permission
identify method based on API-used code permission and the app declared
permission. The major contributions of this paper are as follows:

  * 1.

An over-declared permission identification algorithm is proposed. MPDroid
employs the LDA technique and an improved collaborative filtering
recommendation algorithm to identify and remove over-declared permission by an
app. It then obtains a initial minimum permission set corresponding to the
app’s description (i.e., declaration functionalities).

  * 2.

We employ static analysis to statically parse app related code permissions and
analyze the permissions that the app actually calls. In addition, we present a
functionality point-permission set model to further improve the permission
configuration of the apps and obtain the final minimum permission set.

  * 3.

Based on MPDroid, a permission-based risk assessment framework is proposed to
detect the risk coefficient for the target app, compared with the state-of-
the-art methods, the performance of detecting app risks is improved by 67.5%
for the benign apps. In addition, to enable others to use MPDroid, we have
published our source code and dataset on
GitHub333https://github.com/ztxjm123/MPDroid.

The rest of this paper is organized as follows: Section 2 motivates this
research. Section 3 presents the risky app identification process. Section 4
evaluates MPDroid experimentally. Section 5 reviews the related work and
Section 6 concludes the paper.

##  2 Motivation

The permissions needed by an app are often related to its functionalities,
which can be extracted from the app’s description. For example, an application
that describes itself as a social networking will likely need permissions
related to the mobile device’s address book and will need the permission
“READ_CONTACTS”. A number of malware and privacy-invasive applications have
been known to declare more permissions than their purported functionality
warrants [33], which is usually considered to be unreasonable. Take a screen
wallpaper app named bollywoodlive for example. We parsed its APK file and
found that it actually applied for WAKE_LOCK, CHANGE_WIFI_STATE and
RECEIVE_BOOT_COMPLETED permissions. These permissions are completely
irrelevant to its own functional description which may be harm for the privacy
of app users.

An app should not request more permissions than necessary to support its
functionalities, and the developer should minimize the number of permissions
required by apps to reduce the app security risk. This is also recommended by
the Android official444
https://developer.android.com/training/articles/security-tips.html#
RequestingPermissions. However, sometimes the permissions requested by an app
deviate significantly from the permissions required by the functionalities
specified in the app’s description [20], not only the malicious app, but also
for many benign apps [21], there are also exist declaration the unnecessary
permissions problems. In this context, the research problem is defined as:

_Q1:Given an app $a_{i}$ and its functional description information $DF_{i}$,
then how to obtain the minimum permission set that the app really needs?_

Figure 1: Association between app’s functionalities and permissions

To solve the above problem, MPDroid is proposed in this paper with the aim to
identify the minimum permissions for an app, which is referred to as the
_description-minimum permission set_ in our work. The basic idea of MPDroid is
to establish a mapping relationship between functionalities and corresponding
permissions to identify abnormal permissions. As shown in Figure 1, the
functionalities and the permissions of an app are correlated. An app usually
provides multiple functionalities and requests permissions. A mapping
relationship between its functionalities and permissions can be established.

Figure 2: The Process of Overprivileged App Identification

Figure 2 presents MPDroid’s process of identifying the minimum permissions of
an app. We assume that the target app obtains the permission set
PS=$\left\\{P1,P2,P3,P4,P5,P6\right\\}$ extracted from its APK. When the
target app is processed by the Over-declared Permissions Identification Module
(Step 1), the target app’s permission set becomes
PS=$\left\\{P1,P2,P4,P5\right\\}$. $P3$ and $P6$ will be removed as over-
declared permissions. For instance, Table 1 shows an example of an app
processed by MPDroid. The app Bollywood Live applied for 12 permissions. The
permission CHANGE_WIFI_STATE, GET_TASKS, RECEIVE_BOOT_COMPLETED are over-
declared permissions, because the functionalities in the application
description do not refer to these three permissions.

Meanwhile, the Functionality Point-Permission Set Identification Module (Step
2) can further identify the target app’s permission set
PS=$\left\\{P1,P2,P4\right\\}$ as its final _description-minimum permission
set_. $P5$ is removed because its support degree (details see in Section 3.4)
is too low. For example, In Table 1, permission P5 means SET_WALLPAPER,
READ_LOGS, and SEND_SMS. Because their permission support degree is lower than
the threshold, they will be filtered out. The lower the permission support
degree means the lower possible of the permissions required by the app. Then,
the rest permissions we regard as the final minimum permissions set of the
app.

Table 1: An Example of App Processed by MPDroid App Name |  Bollywood Live
---|---
declared permission |  ACCESS_NETWORK_STATE, ACCESS_WIFI_ STATE, CHANGE_WIFI_STATE, GET_ACC OUNTS, GET_TASKS, INTERNET, READ_L OGS,  RECEIVE_BOOT_COMPLETED, R EAD_PHONE_STATE, SEND_SMS, SET_WALL PAPER, WAKE_LOCK
| After processed by
---
step 1
ACCESS_NETWORK_STATE, ACCESS_WIFI_ STATE, GET_ACCOUNTS, INTERNET,
SET_WALLPAPER, READ_PHONE_STATE, SEND_SMS, READ_LOGS, WAKE_LOCK
| After processed by
---
step 2
ACCESS_NETWORK_STATE, ACCESS_WI FI_STATE, GET_ACCOUNTS, INTERNET,
READ_PHONE_STATE, WAKE_LOCK

Finally, the Permission-Based Risk Evaluation Module (Step 3) identifies the
permission $P3$ as a risk permission (defined as equation (14) in Section
3.5). As a result, the target app is regarded as a risk app because $P3$
belongs to both unexpected permissions (defined as equation (13) in Section
3.5) and risk permissions. The details of each module will be discussed in
Section 3.

##  3 Risk App Identification

MPDroid employs a permission-based app risk evaluation process for measuring
the risk level of an app. Figure 3 shows the process which includes the
following 4 phases.

  1. 1.

Over-declared permissions identification. In this phase, MPDroid employs an
improved collaborative filtering algorithm to identify and remove over-
declared permissions in the app.

  2. 2.

Initial Description-minimum Permission Set Identification. In this phase,
MPDroid iterates the over-declared permissions identification process to
obtain the app’s initial _description-minimum permission set_.

  3. 3.

Functionality Point-permission Set Identification. In this phase, MPDroid
recommends the app permissions that combine with the actual declared
permission and real requested permissions of the app actually uses by calling
APIs. As a consequence, MPDroid further refines the initial description-
minimum permission set of the app to obtain the final _description-minimum
permission set_.

  4. 4.

Permission-based Risk Evaluation. In this phase, MPDroid calculates the risk
level of the app and classifies the app as risky or not.

Figure 3: The Overview of MPDroid

###  3.1 Definitions

In order to establish the mapping relationship between app functionalities and
permissions, MPDroid first identifies the functionality points implemented by
all the local apps’ descriptions, and then establishes a mapping relationship
between the app and its functionalities. This is referred to as description
functionality point extraction. Secondly, MPDroid detects the list of
permissions that the app actually requests, and establishes a mapping
relationship between the app and its permissions. This is referred as declared
permission extraction. Here, we give some formal definitions.

_Definition 1: An app $a_{i}$ is defined as:_

$a_{i}=<DF_{i},DP_{i},CP_{i},\operatorname{Min}P_{i}>$ (1)

where $DF_{i}$ represents $a_{i}^{\prime}s$ functionalities, $DP_{i}$
represents $a_{i}^{\prime}s$ declared permissions, $CP_{i}$ represents
$a_{i}^{\prime}s$ API-based permissions, i.e., permissions parsed from the
code, and $MinP_{i}$ represents $a_{i}^{\prime}s$ minimum permissions
identified by MPDroid.

_Definition 2: An app’s declared functionalities are defined as:_

$DF_{i}=<DF_{i,1},\ldots,DF_{i,k}>,0<DF_{i,k}<1$ (2)

where $DF_{i,k}$ is the probability of declared functionality point of the app
and $k$ is the number of description functionality points contained in app’s
description.

_Definition 3: Declarative permission information for Android app._

$DP_{i}=<DP_{i,1},\ldots,DP_{i,m}>$ (3)

$DP_{i}$ represents the permission set declared by $a_{i}$, and $m$ represents
the number of permissions extracted from $a_{i}^{\prime}s$ AndroidManifest
file.

_Definition 4: Code permission information for Android apps._

$CP_{i}=<CP_{i,1},\ldots,CP_{i,n}>$ (4)

where $CP_{i}$ represents the code permissions of $a_{i}$. MPDroid first
employ static analysis to obtain the Android-related API that the APK calls,
followed by the Android-related API to map to the its permissions. Here, $n$
is the number of permissions that are parsed based on the code and $n$$\geq$
0.

_Definition 5: Minimum permission set information for Android app._

$\operatorname{Min}P_{i}=<\operatorname{Min}P_{i,1},\ldots,\operatorname{Min}P_{i,q}>$
(5)

where $MinP_{i}$ represents $a_{i}^{\prime}s$ minimum permissions identified
by MPDroid, and $q$ is the number of permissions in ${Min}P_{i}$.

Based on the above definitions, MPDroid can now perform data (i.e.,
functionality point and permission data) feature extraction, MPDroid extracts
the functionality information and the declared permissions from the textual
functional description of the Android app and its corresponding APK file
respectively. The goal here is to extract the app data features for building
the mapping relation between the declared functionalities and declared
permissions for each app. It consists of the following three contents.

Description functionality Point Extraction. We obtain the declared
functionality topics for all the app based on their functionality
descriptions, and use the Latent Dirichlet Allocation (LDA) on the
descriptions to cluster app into different functionality topics. We define the
functionality vector set for each app as a $Func$ matrix, formulated as
follows:

$Func=\left[\begin{array}[]{cccc}{DF_{1,1}}&{DF_{1,2}}&{\dots}&{DF_{1,n}}\\\
{DF_{2,1}}&{DF_{2,2}}&{\dots}&{DF_{2,n}}\\\
{\ldots}&{\ldots}&{\ldots}&{\ldots}\\\
{DF_{m,1}}&{DF_{m,2}}&{\dots}&{DF_{m,n}}\end{array}\right]$ (6)

$DF_{i,j}$ represents the probability that app $a_{i}$ belongs to topic
$F_{j}$, $0<DF_{i,j}<1$ , $n$ represents the number of topics in all app, $m$
represents the number of apps. For the newly target app, we can get the
declaration functionality vector of the app by matching the described
information with the LDA trained model.

Declared Permission Extraction. For each app, MPDroid extracts its APK file
with apktool555http://ibotpeaches.github.io/apktool and obtains the declared
permissions from its AndroidMainfest file. By parsing the AndroidMainfest
file, the full permission set can be obtained as follows:

$DP=\left[\begin{array}[]{cccc}{DP_{1,1}}&{DP_{1,2}}&{\dots}&{DP_{1,n}}\\\
{DP_{2,1}}&{DP_{2,2}}&{\dots}&{DP_{2,n}}\\\
{\ldots}&{\ldots}&{\ldots}&{\ldots}\\\
{DP_{m,1}}&{DP_{m,2}}&{\dots}&{DP_{m,n}}\end{array}\right]$ (7)

where $DP_{i,j}=1$ represents that $a_{i}$ applies for permission $DP_{j}$ or
0 otherwise.

API-based Permission Extraction. Certain permissions will be required when an
app calls the Android APIs. To find out the real requested permissions that an
app actually uses by calling APIs, MPDroid adopts an open-source tool named
Androguard666Androguard: https://code.google.com/p/androguard to statically
analyze the app’s APK, and obtains the code permissions of the app. MPDroid
first traverses all the code files in the APK, and detects the API in the file
to obtain all the Android-related methods. Then, according to the result of
Pscout [22], the correspondence relation table between the API and the
permissions is built, and the Android API obtained by the traversal scan is
mapped with the permissions. Finally, we obtain the app’s code permissions. In
our study, 16,343 apps were parsed, and a tree-shaped relationship diagram of
app API-permission information is constructed.

Compared to the information extracted from the AndroidManifest file, the
permissions obtained from the code are often more accurate, and in addition,
the code permissions are the foundation for the implementation of the
Functionality Point-Permission Set Identification in Section 3.4.

###  3.2  Over-declared permissions identification

The purpose of this phase is to identify and remove the permissions that are
over-declared in the app by the recommendation algorithm for the target app.
Figure 4 shows the overall framework of the over-declared permission
identification in MPDroid.

Figure 4: Overall framework of over-declared permission identification

MPDroid leverages two datasets, i.e., the benign app dataset and the malicious
app dataset. We divided the benign app dataset into $N$ parts, $N$-1 parts
form the benign training set, and the remaining part as the target app set
that needs to remove the over-declared permissions. For the malignant app, we
perform the same operation. Our goal is to map the declared functionality
information to the corresponding reasonable permissions for the target app.
MPDroid employs an improved collaborative filtering algorithm to recommend
permissions for the remaining app set, i.e., the target app. The permission
recommendation procedures include following contents.

####  3.2.1 Similarity Computation

We assume that there are $m$ apps. Each app has $n$ functionalities, the
relationship between apps and functionalities is denoted by an $m$$\times$$n$
matrix, i.e., the $Func$ matrix. Each entry $DF_{ij}$ in the matrix represents
the probability that the app belongs to this functionality point. The larger
the probability value, the more likely the app belongs to this functionality.
Conversely, the smaller the probability value, the less likely the app
includes this functionality. Here, the “Euclidean distance” is employed for
the similarity computation. “Euclidean distance” employs the Equation (8) to
compute the distance between the target app and the app located in the
training set:

$\operatorname{D}ist(X,Y)=\sqrt{\sum_{i=1}^{n}\left(X_{i}-Y_{i}\right)}$ (8)

where X and Y represent the functionality vectors of app $a_{i}$ and $a_{j}$
respectively. $\operatorname{D}ist(X,Y)$ represents the distance between app
$a_{i}$ and $a_{j}$, the similarity between app is calculated as equation (9):

$\operatorname{S}im\left(a_{i},a_{j}\right)=\frac{1}{1+\operatorname{D}ist(X,Y)}$
(9)

####  3.2.2 Similar App Selection

After calculating the similarity values between the target app and the app
located in the training set, a set of similar apps can be identified. On the
other hand, in the process of permission identification, if a part of the high
similarity application is used for recommendation, the effect will be better
than the recommendation using all the applications. It is worth noting that
since the number of similar members obtained by the Top-K algorithm is fixed
each time, in fact, the number of similar members of the app is not well
determined and the number of similar members for each app is not necessarily
the same, which may lead the quality of similar members of the app being
unguaranteed, and resulting in poor recommendation results. Thus, MPDroid
employs the similarity threshold method to obtain a subset of similar app by
setting a certain threshold parameter T.

####  3.2.3 Permission Recommendation

MPDroid selects similar app with similarity greater than the threshold T as
candidate recommendation members for each target app, and then it uses the
similarity of the declaration functionality vectors of these similar members
to perform a comprehensive weighted calculation on the permissions they
declare, finally, it obtains a list of the permission recommendation results
for the target app. For example, the permission $p_{i}$ that the app $a_{i}$
may declare is weighted according to the similarity value to calculate the
recommended permission for the target app, it is similar to the user-based
collaborative filtering method. The comprehensive recommendation value is
defined as $\mathrm{Rv}_{a_{i},i}$, and the calculation formula is as equation
(10):

$Rv_{a_{i},i}=k\sum_{a_{j}\in
F}\operatorname{S}im\left(a_{i},a_{j}\right)Rv_{a_{j},i}$ (10)

where $k$ is a normalizing factor defined as $1/\sum_{a_{j}\in
F}\operatorname{S}im\left(a_{i},a_{j}\right)$ , $F$ refers to the app
recommended member set whose similarity is greater than the threshold T,
$Rv_{a_{j},i}$ is equals to 1 if app $a_{j}$ declares the permission,
otherwise $Rv_{a_{j},i}$ is equals to 0 that indicates app $a_{j}$ does not
declare the permission. After calculating a recommended value vector of the
target app, we can get a list of recommended permissions ranking from high
recommended value to low. The larger the value is, the higher possibility that
the permission is needed for the app. Finally, MPDroid uses the adaptive
parameter based method [16] to generate the final permission list.

It is worth noting that in order to avoid the wrong removal of normal
permissions, MPDroid uses the malicious apps and the benign apps as the
training sets separately, and treats the difference between the recommendation
result of the malicious app and the benign app recommendation result as the
permission difference set. If the permissions are located in the difference
set and also locted in the target app’s permissions, so we call them the over-
declared permissions. Thus for the given target app, the difference set of the
two recommended permission is removed from the declared permissions. As the
recommendation result of benign app often represents the permissions necessary
for the app to implement the functionality, so we do not remove this part
permissions. But for the results of malicious app recommend permissions often
tend to be more, because in addition to the permissions required to support
normal functionalities, there are also include many dangerous permissions. So
we believe that the different set of recommendation permissions between a
malicious app and a benign app also represents dangerous permissions.

For each app in the training set, MPDroid extracts the declared functionality
from the description of the app and then establishs a mapping between
functionalities and permissions. Note that our method is a reasonable
permission cross recommendation process as shown in Figure 4, after updating a
set of target app permissions, we put the set of apps back into training set
and continue to train until all apps in the training set are recommended with
reasonable permissions, i.e., removing the over-declared permissions, compared
with the Figure 2 in Section 2, we remove the over-declared permissions ($P3$,
$P6$) of the target app through the over-declared permission identification
module.

###  3.3 Initial Description-minimum permission set identification

In order to generate a minimum set of permissions corresponding to the
description information, we propose an iterative algorithm called description-
minimum permission set identification, its purpose is to generate a minimum
permission sets corresponding to the Android app description (declaration
functionality). The whole process of iterations can be described as follow:

  1. 1.

Initialize the training set: We divide the entire benign app set into $N$
parts marked as $<A_{1},A_{2},\dots,A_{N}>$. Next we use the rest of $N$-1
parts $<A_{2},A_{3},\ldots,A_{N}>$ to identify the over-declared permissions
for the target app set $<A_{1}>$ by using the over-declared permission
identification method in Section 3.2.

  2. 2.

Get the over-declared permissions for $<A_{1}>$ and then remove them.

  3. 3.

Update the training set: Put $<A_{1}>$ that had removed the over-declared
permissions back to the training set and use the next part of the app as the
target app to identify the over-declared permissions. For example, we use the
app $<A_{1},A_{3},\ldots,A_{N}>$ to identify the over-declared permissions for
the $<A_{2}>$. Finally, all the $N$ parts would be removed the over-declared
permissions.

  4. 4.

After all the $N$ parts have been removed the over-declared permissions, we
get the new update dataset, we call this process _one-time iteration_. Next,
we repeat the step 1) to step 3) until the permissions do not change. We
finally get the minimum permission set of the benign app after several times
iteration.

###  3.4 Functionality Point-Permission Set Identification

MPDroid obtains the initial minimum permission set corresponding to the target
app by Description-minimum permission set identification algorithm in Section
3.3. However, that is only the theoretical result. We need to further combine
the permissions of the app actually calls to further refine the minimum
permission set corresponding to the target app. So in this phase, we will mine
the permission set corresponding to the functionality point obtained by the
LDA topic model from the perspective of the functionality point-permission
set. We use the static parsing permissions and the permission of the app
declare itself to build a model to obtain each functionality point
corresponding permissions. Thus, it can further refine the initial
_description-minimum permission set_. Through this, we can obtain our final
_description-minimum permission set_.

We select all the apps with the same functionality topic in $Func$ matrix and
traverse all the apps for each topic $T_{m}$. For each app $a_{i}$, the
permission that it contains is expressed as
$a_{i}=\left[P_{1},P_{2},P_{l},...P_{N}\right]$. Accordingly, we define the
support degree corresponding to each permission as equation (11):

$RP_{l}\left(a_{i}|P_{l}\right)=Pr_{m}\times 1$ (11)

where $RP_{l}\left(a_{i}|P_{l}\right)$ represents the support degree for each
permission, $Pr_{m}$ is the probability corresponding to the functionality
$T_{m}$.

Next, we add up the values of the same permissions for all apps (assuming that
total number of apps is $n$) under each topic $T_{m}$. Then for each
permission $P_{l}$, its total permission support degree to the topic $T_{m}$
is:

$RP_{l}\left(T_{m}|P_{l}\right)=\frac{\sum_{i=1}^{n}RP_{l}\left(a_{i}|P_{l}\right)}{\sum_{i=1}^{n}\operatorname{Pr}_{m}\left(a_{i}|T_{m}\right)}$
(12)

where $\operatorname{Pr}_{m}\left(a_{i}|T_{m}\right)$ represents the
probability that $a_{i}$ belongs to $T_{m}$. We calculate the permission with
the highest $m$ value as the most relevant permission for the topic. If give
out a new app with the functionality topic is
$a_{j}=\left[T_{1},T_{2},T_{m},\ldots,T_{N}\right]$, and its corresponding
permissions probability is
$\left[{Pr}_{1},{Pr}_{2},{Pr}_{m},\ldots,{Pr}_{N}\right]$. As for the topic
$T_{m}$, the corresponding most relevant $t$ permissions value is
$\left\\{RP_{1}\times{Pr}_{m},RP_{2}\times{Pr}_{m},\ldots,RP_{t}\times{Pr}_{m}\right\\}$.
Then we plus the permission values of all the same permissions in
$\left[T_{1},T_{2},T_{t},\ldots,T_{N}\right]$ and arrange them from large to
small to obtain the permission that the $RP_{l}$ value is greater than the
value of support degree threshold $\theta_{\text{support}}$, i.e., the
permissions recommended according to the functionality point directly.

Finally, we inspect whether the initial _description-minimum permission set_
in Section 3.3 exists the permission that the support degree is too low. If it
exists, we remove these permissions. This way, we obtain the final
_description-minimum permission set_ according to the target app. As show in
Figure 2, the permission set of the target app changes from
$\left\\{P1,P2,P4,P5\right\\}$ to $\left\\{P1,P2,P4\right\\}$ in this phase
since $P5$ is the permission whose support degree is too low.

###  3.5 Permission-Based Risk Evaluation

We can perform permission-based risk evaluation with MPDroid. Figure 5 shows a
permission-based risk evaluation framework. The key idea is to take use of the
_description-minimum permission set_ , when a target app comes, we recommend
the permissions to the target app by use the collaborative filtering method.
Then, we compare the difference between the recommendation permissions and the
actually declared permissions of the target app, and through this, we can
further calculate the risk value for the target app.

Figure 5: Permission-based risk assessment framework

Considering the fact that almost all the malicious apps have declared more
permissions than what the original application needs, we calculate the risk
level based on the gap between the malicious app and the benign app.
Specially, the minimum permission set of the benign app has been identified
already. Since the permissions recommended by benign apps often represent
normal and required permissions, so the one that is not recommended in the
app’s declare permissions can be regarded as abnormal or does not support the
permissions required by its declare functionalities. Therefore, given a target
app $a_{i}$, its declared permissions are $DP_{i}=<DP_{i,1},\ldots DP_{i,M}>$
and the recommended candidate permissions are
$RP^{*}\left(a_{i}\right)=<p_{i,1},p_{i,2},\dots,p_{i,N}>$. We can define the
unexpected permissions $UP\left(a_{i}\right)$ as equation (13):

$p_{i}\in UP^{*}\left(a_{i}\right)\leftrightarrow p_{i}\in
DP\left(a_{i}\right)-RP^{*}\left(a_{i}\right)\cap DP\left(a_{i}\right)$ (13)

where $*\in\\{B,M\\}$. $B$ represents the permissions recommended by the
benign app, $M$ represents the list of permissions recommended by the
malicious app.

Also, the recommended permissions by the malicious set
$RP^{M}\left(a_{i}\right)$ will contain not only the necessary permissions but
also the risk permissions. On the contrary, most of the permissions
recommended by the benign set are likely to be necessary. Thus, we define the
risk permissions based on the permission gap
$RP^{M}\left(a_{i}\right)-RP^{M}\left(a_{i}\right)\cap
RP^{B}\left(a_{i}\right)$. The gap between the malicious sets and benign sets
can be used to find the risk permissions, such as the permission $P3$ of
target app in Figure 2. Here, the risk permissions $RiP\left(a_{i}\right)$ can
be formally defined as equation(14):

$p_{i}\in RiP\left(a_{i}\right)\leftrightarrow p_{i}\in
RP^{M}\left(a_{i}\right)-RP^{M}\left(a_{i}\right)\cap
RP^{B}\left(a_{i}\right)$ (14)

If the target app has an unexpected permission and also belongs to the risk
permissions, we consider the app is a risky app, a risky app is defined as
follow equation:

$a_{i}\in Risk\leftrightarrow p_{i}\in RiP\left(a_{i}\right)\&p_{i}\in
UP^{B}\left(a_{i}\right)$ (15)

Finally, we can calculate the risk value as follow equation:

${Risk}\left(a_{i}\right)=\sum_{p_{j}\in\left(UP^{\mathrm{B}}\left(a_{i}\right)\cap
RiP\left(a_{i}\right)\right)}r\left(p_{j}\right)$ (16)

We calculate the risk level based on the permissions protection levels: normal
and dangerous according to the Android permission mechanism. The scores of the
permissions for two protection levels are assigned as 1 and 2 respectively.
Here, $r\left(p_{j}\right)$ refers to the risk of permission based on its
protection level.

##  4 Experiments

###  4.1 Experimental Setup

We use the app market dataset from [23]. After processing the dataset, we
choose 16,343 app with at least 100+ downloads and five stars in Google Play
as the benign dataset finally. The malicious dataset was retrieved from
VirusShare777http://virusshare.com. Since the VirusShare does not offer app
descriptions, so we use the package identifier to map it into the one in the
“app market” dataset. Finally, we find 524 matched items and regard them as
the malicious app dataset. For the dataset of functionality point-permission
set, we have selected 32,671 apps as the dataset to mine functionality point-
permission relationships, which contains both the text information and APK
files.

There are two kinds of permissions in the Android ecosystem: one is the system
permission which is defined by the Android platform, and the other is the
custom permission defined by developers themselves. In our experiment, we do
not consider the custom permissions in the app because they are only defined
and used by developer themselves. Especially, as the Android platform has many
different versions, we take all permissions that have ever been defined,
whatever used or not. Table 2 summarizes the dataset [24] and Table 3
summarizes the experiment parameters.

Table 2: DataSet Summary App Datasets | Number of Applications
---|---
Benign App | 16343
Malicious App | 524
|  App for Functionality Point-Permission
---
Set Identification
32671
Permission Dataset | Number of Permissionss
System permissions | 285
Table 3: Experimental Parameter Descriptions Symbols | Descriptions
---|---
Topic Number | the numbers of the topic in LDA
Similarity threshold ${T_{b}}$, ${T_{m}}$ |  | the threshold value of the similarity
---
member selected employed for
permission recommendation
Support degree threshold $\theta_{\text{support}}$ |  | the support degree filter value in
---
Functionality Point-Permission set
identification phase
Test set ratio | the ratio of the test app set

###  4.2 Analysis the results for each phase

####  4.2.1 Over-declared permissions identification

Over-declaration permission identification process has been described in
Section 3.2. In fact, the results by the LDA model often result in a sparse
declaration functionality matrix. Therefore, in the specific implementation
process, we made an inverted table according to the functionality relevance,
and only the functionality-related app is calculated, which can greatly reduce
the amount of calculation. On the other hand, considering that the number of
benign app is much larger than the malicious app, so we select the threshold
for the benign app as $T_{b}$=0.6 and malicious app we have chosen the
threshold $T_{m}$=0.4 according to [16]. Furthermore, we use the method based
on adaptive parameter in [16] to filter out all the permissions that are
significantly higher than other permissions until the data is balanced.
Finally, we remove the difference set recommended by the malicious and benign
app in declared permissions, thus an over-declared permission identification
process is completed.

####  4.2.2 Initial Description-minimum permission set identification

In this phase, our goal is to identify the minimum permission set information
corresponding to the app. We first randomly divide the benign apps into 5
parts, i.e., $N$=5 in Section 3.3. Then we perform the initial _description-
minimum permission set_ identification method. In the actual experiments, we
found that after 2 iterations, the permission data no longer changes, which
means that the initial _description-minimum permission set_ is obtained.

Table 4: An Example of the Initial Description-Minimum Permission Set Functional Description |  | Over-Declared
---
Permission
| Initial Minimum
---
Permission Set
mission real music studio stude nt love reach locat midtown stu dio offer instruct level excel mu sicianship piano voic drum invo lv north food spring station ped estrian access teacher cost lesso n registr date event program ap p latest watch tab wall share fa mily class amp loop tube class channel latest music video |  |  | ACCESS_COARSE
---
_LOCATION
CALL_PHONE |  | ACCESS_FINE_LO
---
CATION
AMERA |  | ACCESS_NETWORK
---
_STATE
SEND_SMSC | RECORD_AUDIO
|  | WRITE_EXTERNAL
---
_STORAGE
|  | READ_PHONE_STA
---
TE

In addition, to illustrate our experimental results, we also provide an
example of the minimum permission set identification as shown in Table 4. From
that, we can see that an app in our benign dataset requires 10 permissions
which are more than it actually needs. We identify the over-declared
permissions and generate the initial minimum permission set. The words like
“locat, video, music, north” in the functionality descriptions are related to
‘location’ or ‘audio’. Thus, these permissions like RECORD_AUDIO and
ACCESS_FINE_LOCATION enable the basic functionalities of the app and they are
in the minimum permission set identified by MPDroid. On the contrast, we
identify three permissions which are over-declared from the app descriptions:
the functional descriptions do not include words related to ‘call’, ‘sms’ or
‘camera’. This means that these three permissions are unrelated permissions
different from the most apps with the similar description, which may lead to
the leak of sensitive information.

In fact, the apps with a set of fixed functionalities will contain a minimum
set of permissions corresponding to itself in theory. However, in the actual
operation process, due to the inaccuracy of the app description data, the
limitation of the amount of the app data, and the accuracy of the
recommendation algorithm, it is impossible to find the minimum permission set.
Through our method, we can continue to narrow the scope of the declare
permissions without removing the reasonable permissions. This way, we can
obtain we can get the most reasonable permission set of the app (i.e., the
minimum permission set in this article). According to our iterative algorithm
in Section 3.3, it does not delete reasonable permissions. The specific
theoretical proof is as follows:

For a testing app, suppose its declared permission set is $DP$, and the
permission set recommended by the bengin app is $BP$, and the permission set
recommended by the maclicious app is $MP$, assume the minimum permissions set
of the app is $MinP$. From a overall perspective: MPDroid will remove some
permissions for each iteration. Thus, the number of permissions originally
declared by the app will gradually decrease. However, since $MinP\subseteq
BP,MinP\subseteq MP$, there is $MP-BP\cap MinP=\emptyset$, i.e., the
permissions that are removed each time are not the permissions in the minimum
permission set, which can guarantee the lower bound of the final recommended
result is greater than or equal to $MinP$.

From the perspective of the recommendation process: the difference set of $MP-
BP$ will removed from the declaration permission set $DP$ in each iteration,
and $MP$ includes a minimum set permissions and the risk permissions distinct
from $BP$, i.e., the result of $MP-BP$ is risk permission (also called over-
declared permission). In the $n$-th iteration, the recommendation result of
the $MP$ is unchanged, and $BP$ removes some of the $MP$ recommended
permissions in the $n$-1 iterations. Thus, the permissions are gradually
reduced compared to $n$-1 times, which also leads to fewer permissions being
removed in $DP$. When the permission gap is reduced to 0 or close to 0, the
permissions removed during the iteration process will be fewer, and the $DP$
set tends to be stabilize. At this time, the $DP$ set basically does not
include the risk permissions and basically converges. Therefore, MPDroid does
not incorrectly remove the permissions that the app actually uses.

In addition, the over-declared permission identification of the testing set
app is based on difference set recommended by the malicious training set apps
and the benign training set apps, as shown in phase 1 and phase 2 in Figure 3.
In this step, we mainly identify the over-declared permission for 80% of
benign data (16,343) in training set, i.e., 13,075 apps, and the result is
that 635 permissions were removed, involving 479 apps, accounting for 3.66% of
the total apps. For the bengin test apps (3,268), the result is that 301
permissions were removed, involving 205 apps, accounting for 6.27% of the
total benign testing apps. This also shows that there are also cases of over-
declared permissions even for the benign app. However, for the malicious
testing apps, 58 permissions were removed, involving 37 apps, accounting for
35.58% of the total malicious testing apps. These results show that the
proportion of malicious apps which with over-declared permissions is much
higher than that of a benign apps, which is in line with the real-world common
sense.

####  4.2.3 Functionality Point-Permission Set Identification

The purpose of this phase is to mine the relationship between the
functionality points obtained by LDA and the declared permissions directly. We
calculate the relationship between app functionality points and permissions in
real calls, and get the closest permission for each functionality point, then
we get the actual permission set for each app. During the experiment, 32671
benign apps were selected, which contains the text information and APK file.

We map the functionality point information and the declared permission
information of all apps, and implement the functionality point permission set
mining according to Section 3.4. Then we obtain the support degree of each
functionality point corresponding to the permission and arrange them from high
to low. In terms of the code permission, we do the same thing. Then, we select
the permission with the support degree greater than 0.1 and take the union of
code permission and the declaration permission corresponding to the same
functionality point. Meanwhile, we combine the results of the two to obtain
the functionality point-permission set relationship. Finally, we inspect
whether the initial minimum description permission set after the iterations in
Section 3.3 exist the low support degree permissions. If it exists, remove
these permissions, and thus we get the final description-minimum permission
set corresponding to the app.

Figure 6: An Example of Functionality point-permission set identification

Figure 6 shows the functionality point-permission set relationship
corresponding to the app named screener2. The permission with the highest
permission support degree is permission ACCESS_NETWORK_STATE, and its support
degree is 0.89. It is the actual permissions required by the app, and the
minimum permission support degree is the permission DEVICE_POWER, whose
support degree is 0.0000146. This permission will be removed by our method
since the permission support degree is too low. In this way, we have
implemented the functionality point-permission set identification.

####  4.2.4 Permission-Based Risk Evaluation

In order to prove the effectiveness of our method, we conduct an analysis
comparison on our approach and the previous method [16] by using the following
evaluation metrics, the metrics are defined as follows:

Mean Average Precision (MAP): $MAP$ is a comprehensive evaluation of the
accuracy for the recommended permissions. In our study, to test whether the
recommended permission is in the actual declared permission list, we also
consider the relative order of the recommendation results, the calculation
formula is as follow:

$MAP=\frac{\sum_{k=1}^{M}\frac{1}{N_{k}}\sum_{l=1}^{N_{k}}\frac{R_{l}}{l}I_{l}}{M}$
(17)

where $M$ represents the total number of app in the test set, $N_{k}$
represents the number of permissions recommended for the $k^{th}$ app .
$R_{l}$ indicates the number of permissions that really apply for the top $l$
recommended permissions. $I_{l}$=1 indicates that the $l^{th}$ permission in
the recommended ranking is really applied by the app, otherwise $I_{l}$=0
indicates that the recommended permission does not been applied.

The ratio of the app with Unexpected Permissions (AUPR): The AUPR is defined
as the percent of the app which has unexpected permissions in the testing
dataset.

$AUPR=\frac{1}{M}\sum_{i=1}^{M}K\left(UP^{B}\left(a_{i}\right)\right)$ (18)

where if $\left|UP^{B}\left(a_{i}\right)\right|>0$, then
$K\left(a_{i},Risk\right)=1$, otherwise $K\left(a_{i},Risk\right)=0$.

Risk app Ratio (RAR): The RAR is defined as the ratio of risk app in the test
datasets.

$RAR=\frac{1}{M}\sum_{i=1}^{M}K\left(a_{i},\text{Risk}\right)$ (19)

where if $a_{i}\in\operatorname{Ris}k$, then $K\left(a_{i},Risk\right)=1$,
Otherwise $K\left(a_{i},Risk\right)=0$.

Necessary recall (NR): The $NR$ is used to measure the recall of our approach,
it defined as follow:

$NR\left(APP_{t}\right)=\frac{|APs\text{\emph{ in top-n} }|}{n}$ (20)

where $n$ is the number of the necessary permissions of $APP_{t}$, the
$AP_{s}$ are $APP_{t}$’s necessary permissions, and
$\operatorname{\emph{top}}-n$ is the set of top-n permissions returned by an
approach. For a set of apps, $NR$ is the mean of the $NR$ values for all apps
in it.

Total-recall ratio (TRR): The $TRR$ is used to measure the effort our approach
requires to achieve total recall, i.e., to recommend all the correct
permissions for an app. It defined as follow:

$\operatorname{TRR}\left(APP_{t}\right)=\left\\{\begin{array}[]{l}{\frac{n_{mim}}{\left|AP_{s}\right|},\text{
if }AP_{s}-RP_{s}=\emptyset}\\\ {\frac{n_{all}}{\left|AP_{s}\right|},\text{
otherwise }}\end{array}\right.$ (21)

where $AP_{s}$ are $APP_{t}$’s necessary permissions, and $RP_{s}$ are the
recommend permissions by our mehtod. In a nutshell, $TRR$ measures that if we
want to recall all the correct permissions of $APP_{t}$, how many permissions
on average will be recommended by an approach for one correct permission. More
specifically, if the approach can achieve total recall for $APP_{t}$, we
simply compute the ratio of the minimal number of recommended permissions to
achieve total recall, i.e., $n_{mim}$, and the number of $APP_{t}$’s correct
permissions, i.e., $\left|AP_{s}\right|$, $APP_{t}$’s $TRR$. Otherwise, we
penalize $TRR$ by replacing $\boldsymbol{n}_{mim}$ with the total number of
permissions captured by the training set, i.e., $\boldsymbol{n}_{all}$. The
closer $TRR$ is to one, the better it is. For a set of apps, $TRR$ is the mean
of the $TRR$ values for all apps in it.

To evaluate the performance of MPDroid, we compare it with the SF method,
which is the state-of-the-art bias-based recommendation method [16]. In the
experiments, we randomly selected 80% of the benign app as the training set to
establish a description information and permissions mapping, as well as for
the malicious app. The remaining 20% benign apps and 20% of the malicious apps
constitute the test set. After using the _description-minimum permission set_
identification algorithm to identify and remove over-declared permissions in
benign app set, the corresponding _description-minimum permission set_
relationship is obtained. Next, according to the description-permission
mapping, the training set is used to recommend permissions to the test apps.
We set the Topic Number=100, $T_{b}$=0.6, $T_{m}$=0.4, $\theta_{\text{support
}}$=0.1, and then calculate the $MAP$, $AUPR$, $RAR$ and $ARISK$ evaluation
indicators. $ARISK$ represents the average risk value for the test set app
calculate by equation(16).

Table 5: Comparison of experimental results (20% benign app as a test set) Approach | $AUPR$ | $RAR$ | $ARISK$ | $MAP$ | $NR$ | $TRR$
---|---|---|---|---|---|---
MPDroid | 0.334 | 0.104 | 0.335 | 0.931 | 0.865 | 1.257
SF | 0.314 | 0.068 | 0.200 | 0.927 | 0.859 | 1.489
Improvement | 6.4% | 52.9% | 67.5% | 0.4% | 0.6% | 18.5%
Table 6: Comparison of experimental results (20% malicious app as a test set) Approach | $AUPR$ | $RAR$ | $ARISK$ | $MAP$ | $NR$ | $TRR$
---|---|---|---|---|---|---
MPDroid | 0.846 | 0.356 | 2.221 | 0.854 | 0.712 | 1.72
SF | 0.779 | 0.288 | 1.817 | 0.844 | 0.705 | 2.619
Improvement | 10.9% | 23.6% | 22.2% | 0.4% | 0.1% | 52.3%

Tables 5 and Tables 6 are the experiment results compared with SF method.
Specifically, Table 5 is a benign apps that are used as a test set. Table 6
presents the results where malicious apps are used as the test set. The
experimental results shows:

  * 1.

1) Under the experimental settings, MPDroid obtains higher $AUPR$, $RAR$,
$ARISK$, $MAP$ and $NR$ values consistently, and $TRR$ is the opposite, which
indicates higher risk identification performance.

  * 2.

2) Not only for the malicious apps, some of the benign apps are overprivileged
(i.e., over declared the unexpected or risk permissions). In generally, the
malicious apps are generally much more likely to be overprivileged than benign
apps.

  * 3.

3) For the benign apps, the proposed MPDroid outperforms on $RAR$ and $ARISK$
compared with SF by 52.9% and 67.5% respectively. This shows that MPDroid can
provide developers and users with more reasonable permission configuration,
and reducing the over privilege problem.

  * 4.

4) The $MAP$ in SF and MPDroid changes little. This indicates that although
the benign app has over-declared permissions, but the number of over-declared
permissions is still small compared to the total number of permissions of the
app. Generally, the over-declared permissions often appear in a few popular
apps.

####  4.2.5 Studies on the Parameters

In this Section, we discuss how the parameters impact the results in terms of
$AUPR$, $RAR$, $ARISK$, $MAP$ since they are the main goal of MPDroid.

#### (1) Impact of Number of Topic

Figure 7: Benign apps as the test set

MPDroid uses the LDA topic model to process the app description informations
to obtain the functional feature vector. In order to study the impact of
different topics on the final experimental results, we use the benign apps and
the malicious apps as test sets respectively to evaluate the performance of
MPDroid under different number of topics. In the experiments, the number of
topics varies from 60 to 100 with a step value of 5, the test set ratio is set
as 20%. In addition, according to [16], we set the similarity threshold
$T_{b}$=0.6, $T_{m}$=0.4 since it can obtain better results.

Figure 8: Malicious apps as the test set

Figure 7 and Figure 8 show the experimental results of benign apps and
malicious apps as the test set respectively, we can obtain that:

  * 1.

whether it is a benign app or a malicious app as a test set, MPDroid can
obtain better experimental results overall. This indicates that removing the
over-declaration permission of the benign app can better identify over-
declared permissions.

  * 2.

the number of topics has a certain impact on each metric. For the benign app
as the test set, the $RAR$, $ARISK$ are higher when the number of topics is
60. However, for malicious app as the test set, the number of topics is 65.
This indicates that the same number of topics has little impact on different
test sets.

  * 3.

For the $AUPR$ and $MAP$, the number of topics will affect $AUPR$ and $MAP$ to
a certain extent, but there is no fixed rule. For example, for the benign app
as a testing set, when the number of topics is 60, the $MAP$ is the lowest,
and for the malicious app as the testing app set, the $MAP$ achieve the lowest
value is when the number of topics is 90.

#### (2) Impact of Support degree threshold $\theta_{\text{support}}$

The support degree threshold $\theta_{\text{support}}$ in Section 3.4 mainly
considers the permissions required for the actual API call in the app, which
can make the recommended permissions more accurate. To study the impact of the
support degree threshold, we tested the benign app and the malicious app test
set separately and compared the test results with different support degree
thresholds. We set the initial value is 0.0.5, and then we vary the
$\theta_{\text{support}}$ from 0.1 to 0.6 with a step value of 0.1, the
similarity threshold $T_{b}$=0.6, $T_{m}$=0.4, and the test set ratio is 20%.
In addition, since the support calculation only occurs in the MPDroid method,
and the SF method is not affected by the parameter so that the result of SF is
a horizontal line.

Figure 9: Benign apps as the test set

Figure 10: Malicious apps as the test set

Figure 9 and Figure 10 show the experimental results of benign apps as the
test set and malicious apps as the test set, respectively. we can know that:

  * 1.

Regardless of whether it is a benign or malignant test set, when the support
threshold vary from 0.1 to 0.4, $AUPR$, $RAR$, and $ARISK$ change little.
However, when the $\theta_{\text{support}}$ is greater than 0.4, the detection
decreases, indicating that the risk permission is not filtered when the
$\theta_{\text{support}}$ below 0.4. When $\theta_{\text{support}}$ is too
high (greater than 0.4), the app risk permissions are filtered basically, the
remaining permissions are likely to belong to the app itself and the detected
risk is smaller.

  * 2.

The recommendation accuracy rate of the benign test set is always greater than
the malicious test set on the $MAP$. When the $\theta_{\text{support}}$
changes, the $MAP$ of the benign test set changes little, but the malicious
test set changes significantly. It indicats that the risk permission contained
in the malicious app are more, and it will affect the accuracy of the
recommendation.

#### (3)Impact of test set ratio

The test set ratio indicates the performance of MPDroid under different data
scales. In order to study the effect of different test set ratios on
experimental performance, we also tested the benign apps and the malicious
apps test set separately, and compared the test results under different test
set ratio. In the experiments, we vary the test set ratio from 10 to 40
percent with a step value of 5 percent and the similarity threshold is
$T_{b}$=0.6, $T_{m}$=0.4, $\theta_{\text{support}}$=0.1.

Figure 11: Benign apps as the test set

Figure 11 and Figure 12 show the experimental results with benign apps as the
test set and malicious apps as the test set, respectively. It can be obtained
that:

  * 1.

For the benign app as the test set, the $AUPR$, $RAR$, $ARISK$ value are the
highest when the test set ratio is 10 percent, indicating that the test
performance is the best. For the malicious test set, there is no fixed rule,
indicating that different data sets and test set ratios will affect the effect
of the model, and MPDroid is generally better than the SF method.

  * 2.

For the $MAP$, the recommended effect is best when the benign test set ratio
is 20%, and for the malicious test set app, the test set ratio is 25%. It
shows that different test sets and test set ratios will affect the accuracy of
the recommendations.

Figure 12: Malicious apps as the test set

###  4.3 Limitations

MPDroid has some limitations:

  1. 1.

The implementation of MPDroid relies on the mapping the functionalities to
permissions, but the functionality is only the features extracted from the app
description. If the app description does not describe the functionalities of
the app properly, the recommendation results will also be affected. To
alleviate this issue, we use a large amount of app description information as
a training set for training, which can largely ensure that the training model
contains most of the description information, thus it can ensure the accuracy
of subsequent permission recommendations. Meanwhile, we will also try to
extract more granular and accurate functional features, such as adding other
auxiliary information in future. In addition, we would add manual annotation
if necessary.

  2. 2.

Currently, the method of _description-minimum permission set_ identification
relies on the recommendation precision, and the establishment of model depends
on data set. To alleviate this issue when we choose the dataset, the apps with
at least 100+ downloads and five stars in Google Play are considered as the
benign dataset, and the malicious app set we select from VirusShare website
directly, which can slove the problem to some extent. In the future, we will
enrich the mechanism for model building and further optimize the model to make
it more generalized.

  3. 3.

In the static analysis phase of the model, we cannot achieve the completely
correct permissions to parse the app since some malicious apps re-packaging,
or the interference of code mixing. Generally, some developers are not
familiar with Android’s business logic and lead to some useless code, result
in matching too many permissions. Therefore, we will focus on improving static
analysis and increasing the accuracy of the analysis in our follow-up work.

##  5 RELATED WORK

The spurt development of mobile Internet has promoted the security problem of
mobile app to become a hot spot in the industry. Due to the imperfection of
the Android permission mechanism, some irresponsible developers use the
permissions of the Android app indiscriminately, and the user does not realize
the importance of the problem so that led to a series of privacy leaks and
would pose significant risks to users and the entire mobile ecosystem.

One cornerstone of the Android security design is the permission system. An
app must hold the permissions to successfully access the security and privacy
critical methods. The permissions or the risk caused by the permissions have
received a lot of attentions by many security types of research. Some studies
are also dedicated to reminding users to potential risks through study
permission dialogs, further or through improvements to enhance the permissions
dialog [6] [8], but the impact of these methods on end users is still very
small, users may still experience the risk behind it.

The above research is mainly based on the permission mechanism already
contained in Android, and does not modify the underlying architecture of
Android permissions. Their research content mainly focuses on two aspects. On
the one hand, it is aimed at users, they try to make users understand the
permissions by giving hints. For example, Kelley [25] designs the dialog
content of the permission prompt box in more detail, reminds the user of the
consequences when using specific permissions and what is the implied risk will
cause, but they does not explain the details of the resources accessed and
whether it may lead to the disclosure of some private information, Bin Liu
[26] propose a methodology PPA to learn privacy profiles for permission
settings and leverage these profiles in a personalized privacy assistant that
actively supports users in configuring their permission settings. On the other
hand, it is mainly facing for developers, it remind the developers to
strengthen their understanding of permissions, do not declare unnecessary or
wrong permissions during the development process, but because Android
development document do not have mature API descriptions, not only not enough
details, but there may be some errors [27]. So in a summarize, no matter
whether it is for users or developers, the issue of permissions has always
been an urgent problem to be solved.

In order to solve the above problems, many studies decided to turn to use
machine learning [1] [28] or recommended algorithms to solve the problem of
permission redundancy, and then recommend reasonable permissions. For example,
Min Peng [28] proposed a app risk score calculating method ARSM based on app-
permission bipartite graph model which combine the correlation of apps’
permissions and users’ interests. Whyper [13] and AutoCog [14] extracts
various feature word combinations from the description information of the
Android app as the app’s declaration functionality and map them to the app
declared permission, and through the gap between them to determine whether the
declared permission meets the described functionality, and further determine
the risk.

Besides, there are some other methods to extract a variety of feature vectors
through code analysis to detect malicious apps. For example, Bartel [29]
proposed a tool named “COPES” to detecting permission gaps using static
analysis. It extracts from the Android framework bytecode a table that maps
every method of the API to a set of permissions the method needs to be
executed properly. Mujahid [30] implement an technique in a tool called
PERMLYZER which automatically detects permission issues from apps APK to study
the permission related issues in Wearable apps. More recently, some studies
[31] [32] [33] also focus on recommend permissions by the used APIS, such as
Karim [31] presented a tool named ApMiner which combines static analysis and
association rule discovery to make app permission recommendations, and the
results shown that ApMiner performs better than PScout and Androguard in terms
of app permission recommendations. However, the average F1-score of APMiner is
not sufficiently high (only approximately 55%) for it to be used in practice.
Bao [32] propose an approach named APRecCF ,which is based on collaborative
filtering technique, the start point is that apps that use similar APIs often
support similar features, it measures the similarity of two apps based on the
APIs used by the apps and the result show that their approach achieve
significant improvement in terms of the precision, recall, F1-score and MAP of
the top-k results over Karim et al.’s approach. More over, based on [32], Bao
[33] also propose two novel approaches to realize permission recommendation,
the first approach utilizes a collaborative filtering technique utilizes and
the second approach recommends permissions based on a text mining technique
that uses a naive Bayes multinomial classification algorithm, which show a
better preference than the others. To best of our knowledge, the best work of
permission recommendation is PerRec [18], which leverages mining-based
techniques and data fusion methods to recommend permissions for given apps
according to their used APIs and API descriptions, and their results show that
PerRec significantly improves the state-of-the-art approaches APRecCF [33],
APRecTEXT [33] and Axplorer [34].

The main disadvantage of the above methods is that the permissions declared by
the app are treated as actually needed permissions by the app, but this is not
always true, Android apps tend to be overprivileged. According to several
studies, e.g., [7] and [8], overprivileged apps are not the minority, but the
majority. Therefore, it is necessary to identify the permissions that an app
really needs, that is, its minimum permissions set as the permissions the app
actually needs. Further, if given a functionality point, we can find a way to
identify the minimum permission set corresponding to the functionality point,
i.e., an app can declare the permissions to implement this functionality
point. Then, it is possible to significantly improve the performance of over-
declared permission detection so that to find a minimum set of permissions for
the app of its describe information.

In order to achieve the goals, different from the above methods, at a higher
level, our study is similar and creative to these former approaches. Our
approach combines static analysis and collaborative filtering to identify the
minimum permission set of Android apps. We measure the textual descriptions of
the app in Google Play and the relevant permissions it required in a more
accurate way.

##  6 CONCLUSION AND FUTUREWORK

Detecting the overprivileged permissions for the mobile applications is
considered as a critical and valuable task to enhance the permission system
for the mobile service ecosystem. Considering the miss match between the
declared functionalities and the requested permissions to support the declared
functionalities, we propose an iteration approach that combines static
analysis and collaborative filtering to identify the minimum permission set
for the mobile apps. The static analysis is used to achieve the real requested
permissions for each mobile app, and a _description-minimum permission set_
iteration algorithm based on collaborative filtering is developed to mine the
relationships between the declared functionalities and the minimum requested
permissions, so that we can detect the over-requested permissions and identify
the high risk applications. Comparing with the previous state-of-the-art
method, our MPDroid method can effectively identify the abnormal use of
permissions and generate better permission recommendation configuration
results, thereby reducing the problem of mismatch between functionalities and
permissions. For the users, only need to have a description information of the
app, so we can predict the permission required for the description information
according to our model. In addition, this model also can be used to analyze
the permissions of existing Android applications and evaluate the risks of the
app.

For the future works, we will consider more declarative functionality
information, such as user’s comment information, app privacy policy
information, and the classification information to improve the accuracy of the
description functionality. At the same time, we will also add a new data
cleaning mechanism to ensure the security of the declare permissions. In
addition, since the _description-minimum permission set_ identification module
relies on datasets, we will further improve our model by focusing on related
data cleaning and mining techniques, combining with the most advanced
permission identification algorithms. We envision our method would help the
developers to configure the requested permissions and design the declared
functionality.

## Acknowledgment

This work is supported by the National Key R&D Program of China grant
No.2017YFB1401201, the National Natural Science Foundation of China grant
No.61572350, the National Natural Science Key Foundation of China grant
No.61832014 and the Shenzhen Science and Technology Foundation (JCYJ201708
16093943197).

## References

## References

  * [1] S. Roy, J. DeLoach, Y. Li, N. Herndon, D. Caragea, X. Ou, V. P. Ranganath, H. Li, N. Guevara, Experimental study with real-world data for android app security analysis using machine learning, in: Proceedings of the 31st Annual Computer Security Applications Conference, ACM, 2015, pp. 81–90.
  * [2] K. Huang, J. Zhang, W. Tan, Z. Feng, An empirical analysis of contemporary android mobile vulnerability market, in: 2015 IEEE International Conference on Mobile Services, IEEE, 2015, pp. 182–189.
  * [3] Y. Zhang, M. Yang, G. Gu, H. Chen, Rethinking permission enforcement mechanism on mobile systems, IEEE Transactions on Information Forensics and Security 11 (10) (2016) 2227–2240.
  * [4] P. Wijesekera, A. Baokar, A. Hosseini, S. Egelman, D. Wagner, K. Beznosov, Android permissions remystified: A field study on contextual integrity, in: 24th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 15), 2015, pp. 499–514.
  * [5] Y. Acar, M. Backes, S. Bugiel, S. Fahl, P. McDaniel, M. Smith, Sok: Lessons learned from android security research for appified software platforms, in: 2016 IEEE Symposium on Security and Privacy (SP), IEEE, 2016, pp. 433–451.
  * [6] A. P. Felt, E. Ha, S. Egelman, A. Haney, E. Chin, D. Wagner, Android permissions: User attention, comprehension, and behavior, in: Proceedings of the eighth symposium on usable privacy and security, ACM, 2012, p. 3.
  * [7] A. P. Felt, E. Chin, S. Hanna, D. Song, D. Wagner, Android permissions demystified, in: Proceedings of the 18th ACM conference on Computer and communications security, ACM, 2011, pp. 627–638.
  * [8] L. Yu, X. Luo, C. Qian, S. Wang, Revisiting the description-to-behavior fidelity in android applications, in: 2016 IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering (SANER), Vol. 1, IEEE, 2016, pp. 415–426.
  * [9] A. Algarni, Y. Malaiya, Software vulnerability markets: Discoverers and buyers, International Journal of Computer, Information Science and Engineering 8 (3) (2014) 71–81.
  * [10] T.-E. Wei, C.-H. Mao, A. B. Jeng, H.-M. Lee, H.-T. Wang, D.-J. Wu, Android malware detection via a latent network behavior analysis, in: 2012 IEEE 11th International Conference on Trust, Security and Privacy in Computing and Communications, IEEE, 2012, pp. 1251–1258.
  * [11] X. Wei, L. Gomez, I. Neamtiu, M. Faloutsos, Permission evolution in the android ecosystem, in: Proceedings of the 28th Annual Computer Security Applications Conference, ACM, 2012, pp. 31–40.
  * [12] A. Gorla, I. Tavecchia, F. Gross, A. Zeller, Checking app behavior against app descriptions, in: Proceedings of the 36th International Conference on Software Engineering, ACM, 2014, pp. 1025–1035.
  * [13] R. Pandita, X. Xiao, W. Yang, W. Enck, T. Xie, $\\{$WHYPER$\\}$: Towards automating risk assessment of mobile applications, in: Presented as part of the 22nd $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 13), 2013, pp. 527–542.
  * [14] Z. Qu, V. Rastogi, X. Zhang, Y. Chen, T. Zhu, Z. Chen, Autocog: Measuring the description-to-permission fidelity in android applications, in: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, ACM, 2014, pp. 1354–1365.
  * [15] J. Wang, Q. Chen, Aspg: Generating android semantic permissions, in: 2014 IEEE 17th International Conference on Computational Science and Engineering, IEEE, 2014, pp. 591–598.
  * [16] K. Huang, J. Han, S. Chen, Z. Feng, A skewness-based framework for mobile app permission recommendation and risk evaluation, in: International Conference on Service-Oriented Computing, Springer, 2016, pp. 252–266.
  * [17] S. Jana, Ú. Erlingsson, I. Ion, Apples and oranges: Detecting least-privilege violators with peer group analysis, arXiv preprint arXiv:1510.07308.
  * [18] Z. Liu, X. Xia, D. Lo, J. Grundy, Automatic, highly accurate app permission recommendation, Automated Software Engineering (2019) 1–34.
  * [19] K. Goldberg, T. Roeder, D. Gupta, C. Perkins, Eigentaste: A constant time collaborative filtering algorithm, information retrieval 4 (2) (2001) 133–151.
  * [20] Y. Zhou, Z. Wang, W. Zhou, X. Jiang, P. Ning, Detecting malicious apps in official and alternative android markets, in: Proceedings of the second ACM conference on Data and Application Security and Privacy, 2012.
  * [21] A. P. Felt, M. Finifter, E. Chin, S. Hanna, D. Wagner, A survey of mobile malware in the wild, in: Proceedings of the 1st ACM workshop on Security and privacy in smartphones and mobile devices, ACM, 2011, pp. 3–14.
  * [22] K. W. Y. Au, Y. F. Zhou, Z. Huang, D. Lie, Pscout: analyzing the android permission specification, in: Proceedings of the 2012 ACM conference on Computer and communications security, ACM, 2012, pp. 217–228.
  * [23] N. Viennot, E. Garcia, J. Nieh, A measurement study of google play, in: ACM SIGMETRICS Performance Evaluation Review, Vol. 42, ACM, 2014, pp. 221–233.
  * [24] J. X. Shizhan Chen, Qiang He, Mpdroid, http://dx.doi.org/10.17632/p52dpmbb8v.1.
  * [25] P. G. Kelley, L. F. Cranor, N. Sadeh, Privacy as part of the app decision-making process, in: Proceedings of the SIGCHI conference on human factors in computing systems, ACM, 2013, pp. 3393–3402.
  * [26] B. Liu, M. S. Andersen, F. Schaub, H. Almuhimedi, S. A. Zhang, N. Sadeh, Y. Agarwal, A. Acquisti, Follow my recommendations: A personalized privacy assistant for mobile app permissions, in: Twelfth Symposium on Usable Privacy and Security ($\\{$SOUPS$\\}$ 2016), 2016, pp. 27–41.
  * [27] A. P. Felt, S. Egelman, M. Finifter, D. Akhawe, D. A. Wagner, et al., How to ask for permission., HotSec 12 (2012) 7–7.
  * [28] M. Peng, G. Zeng, Z. Sun, J. Huang, H. Wang, G. Tian, Personalized app recommendation based on app permissions, World Wide Web 21 (1) (2018) 89–104.
  * [29] A. Bartel, J. Klein, Y. Le Traon, M. Monperrus, Automatically securing permission-based software by reducing the attack surface: An application to android, in: Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering, ACM, 2012, pp. 274–277.
  * [30] S. Mujahid, R. Abdalkareem, E. Shihab, Studying permission related issues in android wearable apps, in: 2018 IEEE International Conference on Software Maintenance and Evolution (ICSME), IEEE, 2018, pp. 345–356.
  * [31] M. Y. Karim, H. Kagdi, M. Di Penta, Mining android apps to recommend permissions, in: 2016 IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering (SANER), Vol. 1, IEEE, 2016, pp. 427–437.
  * [32] L. Bao, D. Lo, X. Xia, S. Li, What permissions should this android app request?, in: 2016 International Conference on Software Analysis, Testing and Evolution (SATE), IEEE, 2016, pp. 36–41.
  * [33] L. Bao, D. Lo, X. Xia, S. Li, Automated android application permission recommendation, Science China Information Sciences 60 (9) (2017) 092110.
  * [34] M. Backes, S. Bugiel, E. Derr, P. McDaniel, D. Octeau, S. Weisgerber, On demystifying the android application framework: Re-visiting android permission specification analysis, in: 25th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 16), 2016, pp. 1101–1118.