Risk Measurement Method for Privilege Escalation Attacks on Android Apps Based on Process Algebra

Abstract

On the Android platform, information leakage can use an application-layer privilege escalation attack composed of multi-app collusion. However, the detection effect of a single app that can construct privilege escalation attacks is not good. Furthermore, the existing software and app measurement methods are not applicable to the measurement of collusion privilege escalation attacks. We propose a method for measuring the risk of a single app by using process algebra to model and determine the attack behavior, and we construct a measurement function based on sensitive data transitions and the feature set of attack behavior. Through the analysis of the privilege escalation attack model, the feature set of attack behavior is obtained. Then, based on the extracted behavior feature set, process algebra is used to model the dangerous behavior of an app. The dangerous behavior of the app is determined by weak equivalence and non-equivalence, and finally the risk of the app is measured based on the measurement function. Three known applications are used to verify the attack, and the risk measurement values are above 0.98. Based on the classification of applications on the market, we select typical apps in each category to build the test set. Benchmark tests and test set experiments show that the risk measurement results are consistent with the actual detection results, verifying the feasibility and effectiveness of this method.

1. Introduction

With the rapid development of the mobile internet and the Internet of Things(IoT), the Android system, which accounts for 40.39% of operation system (OS) market share, has become an important application platform [1]. Therefore, Android apps are widely used in smart homes, smart healthcare, online education, transportation, tourism, and other aspects closely related to people’s lives. From the perspective of trends in mobile threats, security problems related to the mobile internet and the IoT are highlighted in the 5G era [2,3,4]. There are also more and more threats to Android apps that carry a large amount of users’ privacy data [5,6]. The Nokia Thread Intelligence Report2019 points out that, in 2018, the average monthly infection rate in mobile networks was 0.31%, and Android devices were responsible for 47.15% of the observed malware infections [7]. Based on the report in [8], it was found that 98.7% of the devices in the security analysis results of the system vulnerability. Compared with 89.7% in 2018, the percentage of privilege escalation vulnerabilities has increased, and the threat by privilege escalation attacks has increased. However, application-layer collusion privilege escalation attacks composed of multi-app collusion is based on multiple independent and secure app collusions. Such attacks can complete the theft of user’s privacy data and destructive operation through the collusion of multiple apps. The attack behavior of collusion privilege escalation attacks is more covert and more threatening. Therefore, more and more researchers are focusing on collusion privilege escalation attacks on Android apps.

At present, researchers have made remarkable detection and prevention methods for collusion privilege escalation attacks on Android apps. However, for the current permission granting mechanism, most existing detection and prevention methods become costly or rigid in the recent Android dynamic permission environment [9]. Risk measurement method can avoid the detection of communication between applications and reduce the cost of the method, so it is a feasible solution to measure the risk of the app which can constitute the collusion privilege escalation attacks. At the same time, researchers have put forward many classical methods for the security measurement of software and apps. Therefore, it has a solid research foundation and technical feasibility.

However, due to the strong concealment of collusion privilege escalation attacks, the use of existing methods to measure a single app is not effective. The main problems are as follows: (1) the measurement is mainly based on the overall behavior, performance, or development process of the software, without considering the attack behavior features of collusion privilege escalation attacks; (2) the risk measurement of the app is only based on one feature, such as permission or application programming interface (API) calls, without considering the multi-feature nature of collusion privilege escalation attacks. There is a lack of research on the security measurement of collusion privilege escalation attacks on a single app. Therefore, this paper proposes a method to measure collusion privilege escalation attacks on Android apps based on process algebra. The specific method is described as follows:

(1)

Extraction of the attack behavior feature set and the number of transitions. Based on an analysis of the model of collusion privilege escalation attacks, six features of the app, namely dangerous permissions of the app, dangerous permissions of the components, component intent communication, sensitive API calls, sensitive data flow acquisition, and dissemination of sensitive data, are obtained as the feature set of attack behavior, and the number of transitions is extracted by using static technology.

(2)

Attack behavior modeling and determination. Based on the extraction of the attack behavior features set, process algebra is used to model app behavior and attack behavior, and weak equivalence is used to determine app behavior.

(3)

Risk measurement. According to the result of the behavior determination, the number of behavior features and the number of transitions, a measurement function is constructed to measure the risk of the single app.

The contributions of this paper are as follows:

(1)

Construction and extraction of the feature set of collusion privilege escalation attacks. After obtaining the attack behavior feature set, the static extraction method is used to extract the behavior feature set and the number of transitions of sensitive data. This is done in order to make up for the lack of collusion privilege escalation attack features in the existing app measurement methods.

(2)

Modeling and determination of app behavior using process algebra. The behavior of the app is modeled and determined based on semantics and the equivalence concept of process algebra, and any app that is weakly equivalent to attack behavior is measured. In view of the particularity of collusion attacks, this makes up for the inaccurate measurement results caused by the existing measurement methods that do not distinguish the equivalence relationship of test objects.

(3)

Construction of the measurement function and test set experiment. Based on the number of features in the feature set and the number of transitions, the measurement function is constructed. The case, benchmarks test and test set experiments are completed by using the measurement function. The experimental results show that the method is feasible and effective.

2. Related Work

For the detection of and protection against malware in Android systems, researchers have put forward many classical solutions, from the initial signature-based detection method to the behavior-based dynamic and static detection methods, and then to the data mining and machine learning-based detection methods [10,11,12,13]. However, due to their lack of analysis of the features of collusion privilege escalation attacks, these detection methods have a poor detection effect on a single app that can construct collusion privilege escalation attacks. Based on these previous achievements, researchers have carried out in-depth analysis on privilege escalation attacks on Android apps, and produced remarkable research results. Kernel-level privilege escalation attacks are detected by stain tracking and monitoring permission information [14,15], while for application-level privilege escalation attacks, references [16,17] respectively detect and protect against application-level privilege escalation attacks that function by Android security modules (ASM) access control and monitoring of important system calls. However, application-layer collusion privilege escalation attacks occur on the basis of the collusion of multiple independent and secure apps, so it is particularly important to detect the dangerous path between apps [9,16]. However, the existing detection methods have shortcomings in the following two aspects: (1) their lack of detection of inter-application communication that can construct privilege escalation attacks; (2) their lack of analysis and detection of the features of collusion privilege escalation attacks. With the continuous improvement of Android security mechanisms, the cost of inter-application communication detection and multi-feature detection is increasing. Therefore, the measurement of application-layer collusion privilege escalation attacks has attracted the attention of researchers.

Meanwhile, researchers have made many achievements in the field of software and app security trust measurement. Zhao Qian et al. [18] used pi-calculus, an important branch of process algebra, to measure software dependability by comparing real running results with expected results, so as to conduct quantitative research on software credibility. Although this method uses runtime in behavior modeling, it can reflect the credibility of real-time software changes. However, for collusion privilege escalation attacks, it can disguise the attack result as the expected target and rationalize the attack behavior. Based on the trust theory in the field of human sociology, a measurable software trust framework (social to software, S2S) is proposed in reference [19]. From the point of view of software capability, it gives an overall measurement solution for software trustworthiness. However, as for a single app that constitutes collusion privilege escalation attacks, the app is secure and non-threatening when it alone running, which will make the measurement method invalid. In reference [20], evidence is considered as the basic element for establishing software trustworthiness and supporting a trustworthiness evaluation, and a software process trustworthiness model is proposed based on process assurance. Although the establishment of this method runs through the whole development process, and its considerations are more comprehensive, it is difficult to measure collusion privilege escalation attack by this method in cases where developers have designed an app as part of a collusion privilege escalation attack from the beginning. Reference [21] introduces a risk assessment method based on an analysis of the relationship between permission and function, and it is found that standardizing permission application by Android developers can provide reasonable permission configuration to users in real time and reduce the risk of permission abuse. However, this method only considers the risk of using permissions in the implementation of functions, but fails to consider other attack features. Xu Junfeng et al. [22] proposed a credit index measurement method for Android app security based on analytic hierarchy process (AHP) combined with the Android software certification strength and the violation records in the third-party application market. This method considers the violation records of third-parties. Therefore, the credibility evaluation is more objective. However, the concealment of the attack associated with collusion privilege escalation attacks makes it difficult for the third-party’s violation record to mark the app’s violation in time. Li Danjun et al. [23] proposed an application risk assessment method based on behavioral analysis by using a sandbox approach to dynamically monitor and record the behavior of applications on Android. However, this method only considers the system’s API calls, not other attack features. Reference [24] proposed a criterion to measure the security risks of the apps based on analyzing requested permissions of large numbers of malwares and benign apps. This method used the concepts of entropy given that more informative permissions have higher impacts on the computed risk values. Although this method considers the scale of information in permissions, the permissions for collusion attack may not have more information.

Therefore, previous research results on software and app credibility measurement have been achieved. However, due to the strong concealment and camouflage of application-layer collusion privilege escalation attacks, the detection effect of existing software measurement methods for collusion privilege escalation attacks is not good. The main problems are as follows:

(1)

Up to now, there has been no method to measure the credibility of a single app that constructs collusion privilege escalation attacks.

(2)

The existing methods do not consider the feature set of attack behavior when measuring the credibility of a single app, and they only focus on one feature.

Therefore, it is very important to measure the risk of a single app that constructs collusion privilege escalation attacks. In view of this, the present paper proposes a method for app risk measurement using process algebra.

3. Background Information

In order to better describe and understand this measurement method, some background concepts are explained.

(1)

Definition and classification of privilege escalation attacks on android app.

Privilege escalation attacks means that an application with lower (less) permissions can access components with higher (more) permissions without being restricted by tasks. That is, a malicious program without any permission can obtain the required permission through a third-party app.

This attack can be divided into two categories: kernel-level and application-level. There are two kinds of application-layer privilege escalation attacks: confused deputy attacks and collusion privilege escalation attacks. Our study is focused on the application-layer collusion privilege escalation attack.

(2)

Definition of application-layer privilege escalation.

The privilege escalation attack occurs in the application-layer of Android architecture. Android apps access components with more permissions than themselves through third-party apps and intent communication.

(3)

Definition of confused deputy attacks.

This is a kind of application-layer privilege escalation attack. It exploits privileged app interface vulnerability and exploits the interface vulnerability. One component of the app has applied for dangerous permissions that it does not need, and there are interfaces that allow other apps to access through intent. By scanning the interface, malware can use its implementation to confuse agent attacks.

(4)

Definition of collusion privilege escalation attacks.

This is a kind of application-layer privilege escalation attack. It takes place on the basic of collusion of multiple apps, and completes the attack by gradually upgrading permission. App A obtains sensitive information but does not apply for permission P, but component comA of A has the ability to access the component comB of App B. At this time, B applies for P. ComB has the ability to access the component comC of App C, and comC has applies for P. Therefore, from comA does not apply for P to comA completes access to comC with using comB and P, which constitutes collusion privilege escalation attacks, and completing sensitive information leaks and other attacks.

(5)

Definition of privilege escalation vulnerabilities.

It has the threat proposed in privilege escalation attacks. One component of the app accesses a component of another app with permissions through intent communication. At this time, Intent communication is a vulnerability that may constitute a privilege escalation attacks.

4. Construction and Extraction of the Attack Behavior Feature Set

4.1. Construction of the Attack Behavior Feature Set

Figure 1 describes a privilege escalation attack based on multi-app collusion [25]. AppA and AppC do not apply for permission P1, while AppB applies for P1, and component ComC₁ applies for P1; therefore, componentComA₁ is not protected by P1, while components ComB₁ and ComC₁ are protected by P1. As can be seen in Figure 1:

(1)

ComA₁ can access ComB1 that with the protection of P1.

(2)

ComB₁ and ComC₁ have the same permission P1, and ComB₁ can access ComC₁.

(3)

ComA₁ accesses ComC₁ through ComB₁ by (1) and (2), and AppA, AppB, and AppC escalate permissions on P1.

Therefore, based on the analysis of Figure 1, we can obtain the behavior feature set F of the privilege escalation attack as

$$\mathrm{F}=\left\{\mathrm{F}1,\mathrm{F}2,\mathrm{F}3,\mathrm{F}4,\mathrm{F}5,\mathrm{F}6\right\}$$

(1)

where:

(1)

F1 indicates the dangerous permissions of the application.

(2)

F2 indicates the dangerous permissions of the components.

(3)

F3 indicates the component intent communication.

(4)

F4 indicates the sensitive API calls.

(5)

F5 indicates the sensitive data flow acquisition.

(6)

F6 indicates the dissemination of sensitive data.

4.2. Extraction of the Attack Behavior Feature Set

For Android application package (APK), APKTool is used to convert APK into a Smali file for analysis. The AndroidManifest.xml file is the information description file of the application, which defines the permissions, components, intent filter and other information contained in the application. The behavior feature set is extracted from Smali and AndroidManifest.xml.

The latest dangerous permissions list is obtained from Google official documents, and permissions disabled after version 5.0. PScout [26] summarizes the relationship between the permissions and API calls of multiple versions of Android, and builds sensitive API sets based on the dangerous permissions list.

• Permissions of the application

The application permissions are extracted according to the <uses-permission> tag in the AndroidManifest.xml file.

2.

Permissions of components

(1)

The component information is extracted according to the <activity></activity> tag in the AndroidManifest.xml file.

(2)

The permissions of components are extracted on the basis of (1).

3.

Component Intent communication

Based on the extraction of the component information, the special function calls (getExtra, putExtra, etc.) in the Smali file are used to extract the information on Intent communication.

4.

Sensitive API calls

The system call sequence is extracted by the Android Software Development Kit’s(SDK’s) strace, and the sensitive API calls are obtained by combining the sensitive API set.

5.

Sensitive data flow acquisition

FlowDroid [27] is used to extract sensitive data flow pairs, that is, <source, sink>, where source is the information’s source and sink is the leakage point.

6.

Dissemination of sensitive data

FlowDroid [27] is used to detect the data dissemination path from source to sink.

7.

Applying for the dangerous permissions of the application and components

On the basis of 1 and 2, the dangerous permissions applied by the app are obtained according to the dangerous permissions list.

4.3. Attack Case

According to the attack model in Section 4.1, we designed three apps to constitute aprivilege escalation attack [28], and the key code is shown in Figure 2.

According to the above code:

(1)

comAppA does not apply for any dangerous permission. Its component inputInfromShowActivity obtains the user’s private information (username and password) through edittext, and sends it to the component whose <intent-filter> is sensitiveInfo through the intentAppA.

(2)

comAppB has applied for the dangerous permission android.permission.SEND_SMS, and its component sendNewsToFriend has <intent-filter> as sensitiveInfo. The user’s private information (username and password) is obtained by bundleB and is sent to the component whose <intent-filter> is sensitiveInfoSend through intentAppB.

(3)

comAppC has not applied for any dangerous permission, but its component sendMessage has applied for android.permission.SEND_SMS dangerous permission and has <intent-filter> as sensitiveInfoSend. Using bundleC, the username and password are obtained and sent to the mobile phone number by SMS.

5. Attack Behavior Modeling Based on Process Algebra

5.1. Process Algebra Based on Behavior Features

Process algebra [29] can effectively describe the Android architecture and message communication characteristics, and it can be used in the creation of an application attack behavior model according to the attack behavior feature set. The following is the syntactic and semantic specification of process algebra based on behavior features.

$$\mathrm{appComBehavior}\colon\colon ={{\displaystyle \sum }}_{\begin{array}{c}\mathrm{i}\in \mathrm{I}\\ \mathrm{j}\in \mathrm{K}\end{array}}{\mathrm{P}}_{\mathrm{i}}·{\mathrm{a}}_{\mathrm{j}}\left|{\mathrm{Feature}}_1\right|{\mathrm{Feature}}_2\left|\cdots \left|{\mathrm{Feature}}_{\mathrm{w}}\right|\left(\overline{\mathrm{X}}\langle {\mathrm{y}}_1,{\mathrm{y}}_2,\cdots ,{\mathrm{y}}_{\mathrm{n}}\rangle |\mathrm{X}\left({\mathrm{y}}_1,{\mathrm{y}}_2,\cdots ,{\mathrm{y}}_{\mathrm{n}}\right)\right)\right|\left(\mathrm{action}\right)\mathrm{P}$$

(2)

where:

(1)

${{\displaystyle \sum }}_{\begin{array}{c}\mathrm{i}\in \mathrm{I}\\ \mathrm{j}\in \mathrm{K}\end{array}}{\mathrm{P}}_{\mathrm{i}}·{\mathrm{a}}_{\mathrm{j}}$ is a summation, where I and K are any finite indexing set. ${\mathrm{a}}_{\mathrm{j}}$ is protected by ${\mathrm{P}}_{\mathrm{i}}$, because ${\mathrm{a}}_{\mathrm{j}}$ must start activities after the action represented by ${\mathrm{P}}_{\mathrm{i}}$ occurs. It represents a collection of behaviors of a component of an app under permission.

(2)

${\mathrm{Feature}}_1|{\mathrm{Feature}}_2|\cdots |{\mathrm{Feature}}_{\mathrm{w}}$ represents that the component has w features at the same time.

(3)

$\left(\overline{\mathrm{X}}\langle {\mathrm{y}}_1,{\mathrm{y}}_2,\cdots ,{\mathrm{y}}_{\mathrm{n}}\rangle |X\left({\mathrm{y}}_1,{\mathrm{y}}_2,\cdots ,{\mathrm{y}}_{\mathrm{n}}\right)\right)$,where $\overline{\mathrm{X}}\langle {\mathrm{y}}_1,{\mathrm{y}}_2,\cdots ,{\mathrm{y}}_{\mathrm{n}}\rangle$ represents the action of message transmission; $\mathrm{X}\left({\mathrm{y}}_1,{\mathrm{y}}_2,\cdots ,{\mathrm{y}}_{\mathrm{n}}\right)$ represents the action of message receipt; ${\mathrm{y}}_1,{\mathrm{y}}_2,\cdots ,{\mathrm{y}}_{\mathrm{n}}$ represents n sensitive data.

(4)

$\left(\mathrm{action}\right)\mathrm{P}$ represents that the action is under the protection of permission P.

5.2. Attack Behavior Modeling

In the Android architecture, apps are made up of several services and components. A component is the basic unit of an app. In the case of a privilege escalation attack, a component with dangerous behavior must complete the collection, transmission and sending of sensitive information under the protection of dangerous permission. The four components of Android are as follows:

(1)

Activity, which is used to express the function.

(2)

Service, which runs in the background and does not provide interface presentation.

(3)

BroadcastReceiver, which is used to receive broadcast information.

(4)

ContentProvider, which supports data storage and reading across multiple applications and is equivalent to a database.

Therefore, the dangerous behavior of a privilege escalation attack must be carried out by a component, and the behavior of the application components constitutes the behavior of the application. According to Formulas (1) and (2), the definition of component attack behavior under P1 can be obtained, as shown in Formula (3).

$$\mathrm{attackAction}\colon\colon ={\displaystyle \sum }_{\mathrm{i}ϵ6}{\mathrm{P}}_1·{\mathrm{a}}_{\mathrm{i}}\left|\mathrm{F}1\right|\mathrm{F}2\left|\cdots \left|\mathrm{F}6\right|\left(\overline{\mathrm{X}}\langle {\mathrm{y}}_1,{\mathrm{y}}_2,\cdots ,{\mathrm{y}}_{\mathrm{n}}\rangle |\mathrm{X}\left({\mathrm{y}}_1,{\mathrm{y}}_2,\cdots ,{\mathrm{y}}_{\mathrm{w}}\right)\right)\right|\left(\mathsf{\chi }\right)\mathrm{P}$$

(3)

where:

(1)

${\displaystyle \sum }_{\mathrm{i}ϵ6}{\mathrm{P}}_1·{\mathrm{a}}_{\mathrm{i}}$ represents the attack behavior set under P₁.

(2)

$\mathrm{F}1|\mathrm{F}2|\cdots |\mathrm{F}6$ represents the six features of a component.

(3)

$\left(\overline{\mathrm{X}}\langle {\mathrm{y}}_1,{\mathrm{y}}_2,\cdots ,{\mathrm{y}}_{\mathrm{n}}\rangle |\mathrm{X}\left({\mathrm{y}}_1,{\mathrm{y}}_2,\cdots ,{\mathrm{y}}_{\mathrm{w}}\right)\right)$, where $\overline{\mathrm{X}}\langle {\mathrm{y}}_1,{\mathrm{y}}_2,\cdots ,{\mathrm{y}}_{\mathrm{n}}\rangle$ represents the action of message transmission and $\mathrm{X}\left({\mathrm{y}}_1,{\mathrm{y}}_2,\cdots ,{\mathrm{y}}_{\mathrm{w}}\right)$ represents the action of message receipt. ${\mathrm{y}}_1,{\mathrm{y}}_2,\cdots ,{\mathrm{y}}_{\mathrm{n}}$ represents n sensitive data.

(4)

$\left(\chi \right)\mathrm{P}$ represents the behavior $\chi$ ofan application is protected by permission P.

6. Behavior Determination and Risk Measurement Based on Process Algebra

According to the state relations of strong equivalence, weak equivalence and non-equivalence defined in process algebra, we use the concept of weak equivalence to determine the dangerous behavior and then combine the risk measurement function to measure the risk.

Definition 1.

Labelled transition system(LTS).Suppose the action of application is under the protection of permission P, and the set of app actions $Act=\left\{a_1,a_2,\cdots ,a_t,a_1^{\prime },a_2^{\prime },\cdots ,a_t^{\prime }\right\}$ is a pair (Q,T) which is the LTS, where $Q=\left\{\left(a_1,P\right),\left(a_2,P\right),\cdots ,\left(a_t,P\right),\left(a_1^{\prime },P\right),\left(a_2^{\prime },P\right),\cdots ,\left(a_t^{\prime },P\right)\right\}$ is a set of states; $T\subseteq \left(Q\times Act\times Q\right)$ is a ternary relation, known as a transition relation. If $\forall \left(a_i,P\right)\in Q$, $\forall \left(a_i^{\prime },P\right)\in Q$, $\exists a_i\in Act\left(or\exists a_i^{\prime }\in Act\right)$ and $\left(\left(a_i,P\right),a_i,\left(a_i^{\prime },P\right)\right)\in T\left(or\left(\left(a_i,P\right),a_i^{\prime },\left(a_i^{\prime },P\right)\right)\in T\right)$, we written $\left(a_i,P\right)\stackrel{a_i}{\to }\left(a_i^{\prime },P\right)\left(or\left(a_i,P\right)\stackrel{a_i^{\prime }}{\to }\left(a_i^{\prime },P\right)\right)$.

Definition 2.

Weak simulation.Suppose $S=\left\{\left(\left(a_1,P\right),\left(a_1^{\prime },P\right)\right),\left(\left(a_2,P\right),\left(a_2^{\prime },P\right)\right),\cdots ,\left(\left(a_t,P\right),\left(a_t^{\prime },P\right)\right)\right\}$ is a binary relation in the state space $\mathcal{P}$ of a component, and $P,P^{\prime },Q,Q^{\prime }\in \mathcal{P},\stackrel{\lambda }{\to }$ represents any action by a feature of a component. S is a weak simulation if and only if, whenever PSQ, if $P\to P^{\prime }$, then there exists $Q^{\prime }$ such that $Q{Q}^{\prime }$ and $P^{\prime }S{Q}^{\prime }$; if $P\stackrel{\lambda }{\to }{P}^{\prime }$ then there exists $Q^{\prime }$ such that $Q\stackrel{\lambda }{\Rightarrow }{Q}^{\prime }$ and $P^{\prime }S{Q}^{\prime }$. This means that state P has passed a finite number of state transitions to state Q. An interaction action of P can be corresponding to a series of interaction actions of Q, or even no action.

Definition 3.

Behavior weak equivalence.Based on Definitions 1 and 2, a binary relation S over P is said to be a weak bisimulation if both S and its converse are weak simulations. We say that P and Q are weakly bisimilar, wrtttenas $P\approx Q$, if there exists a weak bisimulation S such that PSQ. This means that there is a certain equivalence relationship between the actions of the component and the dangerous behavior model, which needs to be measured by the measurement function.

Definition 4.

Behavior non-equivalence.Based on Definitions1,2, and 3, P and Q are the LTS. Whenever P chooses any transition, Q cannot find an appropriate transition to match. That is, if there is no strong (weak) simulation R, then P and Q are not equivalent, which is written as $P\ne Q$. This means that there is no equivalent relationship between the actions of this component and the dangerous behavior model, and the risk measure is 0.

Definition 5.

Sensitive data transition.There exists a set $Act=\left\{a_0,a_1,\cdots \right\}$ of actions, a state set $Q=\left\{q_0,q_1,\cdots \right\}$ of states, and a subset T of $Q\times Act\times Q$ called the transitions. That is, $q,q^{\prime }\in Q,a\in Act$, then $q\times a\times q^{\prime }$, called q transition $q^{\prime }$. We use FlowDroid to obtain the path of stain dissemination, so as to obtain the number of sensitive data transitions.

Definition 6.

Risk measurement function.In the case of extracting the behavior feature set and sensitive data transitions, we construct the measurement function f (x, y).

$$f\left(x,y\right)\{\begin{array}{ll}1-\frac{1}{e^{x+y}},& P\approx Q\\ 0,& P\ne Q\end{array}$$

(4)

where x represents the number of dangerous features in F($0\le X\le 6$), and y represents the number of transitions ($0\le y\le \infty$).

(1) 

When x tends to be 6 and Y tends to be infinite, then $\underset{x\to 6,y\to \infty }{lim}\frac{1}{e^{x+y}}=0$. That is, when the more dangerous features and transition times;$f\left(x,y\right)$ are closer to 1, the risk is greater.

(2) 

When x tends to be 0 and Y tends to be 0, then $\underset{x\to 0,y\to 0}{lim}\frac{1}{e^{x+y}}=1$. That is, when the less dangerous features and transition times; $f\left(x,y\right)$ are closer to 0, the risk is smaller.

Algorithm 1. Here, riskcom is a set of components with dangerous behavior features.

Algorithm 1. Risk measurement algorithm based on process algebra.

1:  Input: riskCom, F,attackAction, X, Y, f(x,y) 2:  Output: measureValue 3:  Assumption: use PR point to $\mathrm{riskCom}=\left\{{\mathrm{Com}}_0,{\mathrm{Com}}_1,\cdots \right\}$ 4:  Initialization: $\mathrm{PR}\to {\mathrm{riskCom}}_0,$ 5:  For each component in riskCom 6:      Construction attackActionF according to F 7:  If ${\mathrm{attackAction}}_{\mathrm{F}}\approx \mathrm{attackAction}$ Then 8:      call f(x,y) 9:      print measureValue 10:     $\mathrm{PR}=\mathrm{PR}\to \mathrm{next}$ 11: ElseIf PA ≠ PC Then 12:    print measureValue=0 13:    $\mathrm{PR}=\mathrm{PR}\to \mathrm{next}$ 14: EndIf

7. Experiment of an Attack Case

7.1. Feature Set Extraction of Attack Behavior

Using Equation (1), the behavior feature sets of comAppA, comAppB, and comAppC can be obtained respectively, as shown in

Table 1. Feature sets of comAppA, comAppB and comAppC.

	F1	F2	F3	F4	F5	F6
comAppA	F	F	T	F	T	T
comAppB	T	T	T	T	T	T
comAppC	F	T	T	T	T	T

. Because the code is tedious, in order to save space, the behavior feature is not represented directly by code, but it is represented by T and F, where T means that the feature exists, and F means that the feature does not exist.

From Table 1, it is shown that the number of Fs for comAppA, comAppB, and comAppCis 3, 6, and 5, respectively.

7.2. Attack Behavior Modeling

For the case of the privilege escalation attack given in Section 4.3, the attack behavior models of comAppA, comAppB, and comAppC can be obtained according to Table 1 and Equation (3).

(1)

The attack behavior of comAppA is modeled as shown in Equation (5).

$$\mathrm{comAppAAttack}\colon\colon =\left(\overline{\mathrm{X}}\langle {\mathrm{y}}_1\rangle |\mathrm{X}\left({\mathrm{y}}_1\right)\right)|\mathrm{F}6$$

(5)

(2)

The attack behavior of comAppB is modeled as shown in Equation (6).

$$\begin{gathered} \mathrm{comAppBAttack}\colon\colon ={\displaystyle \sum }_{\mathrm{i}=2}^6{\mathrm{P}}_1·\mathrm{Fi}\left|\left(\overline{\mathrm{X}}\langle {\mathrm{y}}_1,{\mathrm{y}}_2\rangle |\mathrm{X}\left({\mathrm{y}}_1,{\mathrm{y}}_2\right)\right)\right|\left(\mathsf{\nu }\mathsf{\chi }\right){\mathrm{P}}_1 \\ \colon\colon ={\mathrm{P}}_1·\mathrm{F}2+{\mathrm{P}}_1·\mathrm{F}3+{\mathrm{P}}_1·\mathrm{F}4+{\mathrm{P}}_1·\mathrm{F}5+{\mathrm{P}}_1·\mathrm{F}6\left|\left(\mathrm{x}\left({\mathrm{y}}_1\right)|\overline{\mathrm{x}}\langle {\mathrm{y}}_1\rangle \right)·{\mathrm{P}}_1\right|{\mathrm{P}}_1 \end{gathered}$$

(6)

(3)

The attack behavior of comAppC is modeled as shown in Equation (7).

$$\begin{gathered} \mathrm{comAppCAttack}\colon\colon ={\displaystyle \sum }_{\mathrm{j}=2}^6{\mathrm{P}}_1·\mathrm{Fj}\left|\left(\overline{\mathrm{X}}\langle {\mathrm{y}}_1,{\mathrm{y}}_2\rangle |\mathrm{X}\left({\mathrm{y}}_1,{\mathrm{y}}_2\right)\right)\right|\left(\mathsf{\nu }\mathsf{\chi }\right){\mathrm{P}}_1 \\ \colon\colon ={\mathrm{P}}_1·\mathrm{F}2+{\mathrm{P}}_1·\mathrm{F}3+{\mathrm{P}}_1·\mathrm{F}4+{\mathrm{P}}_1·\mathrm{F}5+{\mathrm{P}}_1·\mathrm{F}6|(\mathrm{x}\left({\mathrm{y}}_1\right)|\overline{\mathrm{x}}\langle {\mathrm{y}}_1\rangle )·{\mathrm{P}}_1 \end{gathered}$$

(7)

7.3. AppBehavior Modeling

The behavior models of comAppA, comAppB, and comAppC can be obtained according to Table 1 and Equation (2).

(1)

The behavior of comAppA is modeled as shown in Equation (8).

$$\mathrm{comAppABehavior}\colon\colon =\mathrm{filterIntent}\left|\left(\mathrm{X}\left(\mathrm{sensitiveInfo}\right)|\overline{\mathrm{X}}\langle sensitiveInfo\rangle \right)\right|\mathrm{sourceSink}$$

(8)

(2)

The behavior of comAppB is modeled as shown in Equation (9).

$$\begin{array}{l}\mathrm{comAppBBehavior}\colon\colon \\ ={\mathrm{P}}_1·\mathrm{comPermission}+{\mathrm{P}}_1·\mathrm{Intent}+{\mathrm{P}}_1·\mathrm{sensitiveAPI}+{\mathrm{P}}_1·\mathrm{sourceSink}\\ +{\mathrm{P}}_1·\mathrm{filterIntent}\left|\left(\mathrm{X}\left(\mathrm{sensitiveInfo}\right)\overline{\mathrm{X}}\langle sensitiveInfo\rangle \right)·{\mathrm{P}}_1\right|{\mathrm{P}}_1\end{array}$$

(9)

(3)

The behavior of comAppC is modeled as shown in Equation (10).

$$\begin{array}{l}\mathrm{comAppCBehavior}\colon\colon \\ ={\mathrm{P}}_1·\mathrm{comPermission}+{\mathrm{P}}_1·\mathrm{Intent}+{\mathrm{P}}_1·\mathrm{sensitiveAPI}+{\mathrm{P}}_1·\mathrm{sourceSink}\\ +{\mathrm{P}}_1·\mathrm{filterIntent}|\left(\mathrm{X}\left(\mathrm{sensitiveInfo}\right)\overline{\mathrm{X}}\langle sensitiveInfo\rangle \right)·{\mathrm{P}}_1\end{array}$$

(10)

(4)

To expand the case, assuming that the behavior component of comAppA has no Intent communication, the behavior model of comAppA is shown in Equation (11).

$$\mathrm{comAppAChange}\colon\colon =\mathrm{X}\left(\mathrm{sensitiveInfo}1\right)|\overline{\mathrm{X}}\langle sensitiveInfo1\rangle$$

(11)

7.4. BehaviorDetermination

App has a feature then it has a state when the feature exists. For example, App has permission P, and then its component is protected by P. The privilege escalation attacks must be a part of the action set of the application itself. Therefore, according to the Definition (1), the status and behavior of app can build LTS, and the status of Equations (6) and (9) must exist in the LTS. For the convenience of description,

Table 2. Symbol simplification of Equation (6).

	Formula Content	Simplified Symbols
dangerous permissions of the components	P1(F2)	p0
sensitive API calls	$\mathrm{F}4$	p1
component intent communication	$\mathrm{F}3$	p2
sensitive data flow acquisition	$\mathrm{F}5$	p3
dissemination of sensitive data	F6	p4

and

Table 3. Symbol simplification of Equation (9).

	Formula Content	Simplified Symbols
dangerous permissions of the application	P1	q0
dangerous permissions of the components	$\mathrm{comPermission}$	q1
sensitive API calls	$\mathrm{sensitiveAPI}$	${\mathrm{q}}_1^{\prime }$
component intent communication	$\mathrm{Intent}$	q2
sensitive data flow acquisition	sourceSink	q3
dissemination of sensitive data	filterIntent	q4

are used to simplify the states represented by related features.

Construct the state transition diagram of Equations (6) and (9), as shown in Figure 3a,b.

According to the Definition (2), suppose that $\mathrm{S}=\left\{\left({\mathrm{q}}_0,{\mathrm{p}}_0\right),\left({\mathrm{q}}_1,{\mathrm{p}}_1\right),\left({\mathrm{q}}_1^{\prime },{\mathrm{p}}_1\right),\left({\mathrm{q}}_2,{\mathrm{p}}_2\right),\left({\mathrm{q}}_3,{\mathrm{p}}_3\right),\left({\mathrm{q}}_4,{\mathrm{p}}_4\right)\right\}$.

(1)

${\mathrm{p}}_0$ weak simulation ${\mathrm{q}}_0$ verification. $\forall \left(\mathrm{q},\mathrm{p}\right)\in \mathrm{S}$, each migration of the first element q, ${\mathrm{q}}_{\mathrm{i}}\stackrel{\mathrm{a}}{\to }{\mathrm{q}}_{\mathrm{j}},0\le \mathrm{i},\mathrm{j}\le 4$ can be migrated ${\mathrm{p}}_{\mathrm{i}}\stackrel{\mathrm{a}}{\to }{\mathrm{p}}_{\mathrm{j}},0\le \mathrm{i},\mathrm{j}\le 4\mathrm{by}\mathrm{a}\sec \mathrm{ond}\mathrm{element}$ p matching (or a series of migration, or even no migration). For example, for $\left({\mathrm{q}}_1^{\prime },{\mathrm{p}}_1\right)$, ${\mathrm{q}}_1^{\prime }$ has ${\mathrm{q}}_1^{\prime }\stackrel{\mathrm{c}}{\to }{\mathrm{q}}_3$, so $\exists \left({\mathrm{q}}_3,{\mathrm{p}}_3\right)\in \mathrm{S}$, using ${\mathrm{p}}_1\stackrel{\mathrm{c}}{\to }{\mathrm{p}}_3$ matching. Therefore, s is a weak simulation, that is, ${\mathrm{p}}_0$ weak simulation ${\mathrm{q}}_0$.

(2)

In the same manner, the weak simulation relationship of each state in two state graphs can be verified.

(3)

According to the concept of weak equivalence Definition 3, S⁻¹ can be verified as a weak simulation in the way of (1).

(4)

Therefore, the weak equivalence between the states in Figure 3a,b can be verified. Then, the weak equivalence between the Equations (6) and (9) is verified.

To make the verification more automated, the mobility workbench (MWB) was chosen as the verification tool. Standardize Equations (6) and (9) according to MWB syntax [30]. For example, the output $\overline{\mathrm{a}}$ in process algebra should be converted to ‘a. Therefore, $\overline{\mathrm{x}}\langle {\mathrm{y}}_1\rangle$ in Equation (6) is convert to MWB syntax is ${}^{\prime }\mathrm{x}\langle {\mathrm{y}}_1\rangle$. In order to better distinguish the input and output, we use ${}^{\prime }\mathrm{y}\langle {\mathrm{y}}_1\rangle$ to represent the output. The comAppBBehavior in Equation (9) is represented by agent BB when it is encoded by MWB, and the comAppBAttack in Equation (6) is represented by agent BA when it is encoded by MWB. Agent BB1X and BA1X represent the components of BB and BA respectively. Weq and eq are used to verify the weak equivalence and strong equivalence of the two models. Therefore, the weak equivalence relationship between the component behavior model (BB) and the component attack behavior model (BA) can be verified, as shown in Figure 4a. At the same time, the $\mathrm{comAppAChange}$ in Equation (11) is represented by AC when it is encoded by MWB, and the comAppAAttack in Equation (5) is represented by AA when it is encoded by MWB. According to the syntax rules of MWB and the Definition 4, the non-equivalence relationship between the component model (AC) with changed features and the component attack model (AA) can be obtained, as shown in Figure 4b.

As can be seen from Figure 4, MWB can be used to verify the weak equivalence relations of Equations (5) and (8), as well as Equations (7) and (10) respectively, that is, it can be verified that comAppA, comAppB, and comAppC are weakly equivalent to the attack model.

7.5. Risk Measurement

According to Definition 5, the number of sensitive data transitions of comAppA, comAppB, and comAppC can be obtained, as shown in

Table 4. Number of transitions of comAppA, comAppB and comAppC.

	comAppA	comAppB	comAppC
number of transitions	1	2	1

.

Using Equation (4) and the risk measurement algorithm 1 based on process algebra, measurement values for the three apps can be obtained, as shown in

Table 5. Measurement values.

	X	Y	Measurement Value
comAppA	3	1	0.9816843611
comAppB	6	2	0.9996645373
comAppC	5	1	0.9975212478

.

From the measurement results in Table 5, we can see that the measurement values of comAppA, comAppB and comAppC are close to 1. The measurement values of comAppAChange, for which the relevant features have been changed, is 0. Theseresults are consistent with the actual app’s dangerous behaviors, so this shows the effectiveness of our method.

8. Method Evaluation and Effectiveness Analysis

8.1. Method Evaluation

In this paper, APKTool and FlowDroid are used to extract the attack behavior feature set. MWB is used to verify the equivalence of behavior. Java language is used to implement the risk measurement algorithm. All experiments were carried out on a machine with 8G memory and Intel (R) core (TM) i5-2520M CPU.

The key steps in this method are attack behavior feature set extraction and transition detection, and the time complexity of the dangerous behavior determination and measurement algorithm is O(n). In the experiment on the test set, due to the different of feature set and the number and path of transition, the costs of time and space are discretely distributed, as shown in Figure 5.

This method is discussed in two cases: weak equivalence and non-equivalence. According to measurement algorithms and measurement function, weak equivalence APKs must be risk measured, but non-equivalence APKs risk measurement value is 0. The size of the APK, the number of components, the number of sensitive data transitions and the number of features in the attack behavior feature set affect the time cost and space cost of this method. There are three situations as follows:

(1)

Some of the APKs have some features as small size, fewer components, or fewer sensitive data transitions and attack features. In general, those APKs are non-equivalent to attacks behavior. Those APKs have less time cost and space cost.

(2)

Another part of APKs have the following features as larger size, more components, or a greater number of sensitive data transitions and attack features. In general, those APKs will be weak equivalent to the attack behavior. Those APKs has more time cost and space cost for this method.

(3)

There will be some special APKs. For example, two APKs have similar size, but because the number of components, transitions and features of first APK is far greater than second APK, the time cost and space cost of first APK are also far greater than second APK. However, it will follow the principle that with more components, or the greater number of transitions and features there, the more this method will cost in terms of time and space.

Therefore, according to the analysis of (1) and (2) on the above, the time cost and space cost of this method are prone to the phenomenon of two groups separated, as shown in Figure 5b. According to (3) on the above, due to special circumstances, those two groups are not necessarily completely separated, as shown in Figure 5a.

8.2. BenchmarksTest and Analysis

DroidBench [31] is a set of open source real-life Android applications to be used as a testing ground for static and dynamic security and measurement methods. FieldAndObjectSensitivity, InterAppCommunication, and InterComponentCommunication test sets in DroidBeach are measured by the method in this paper. Three test sets cover sensitive data acquisition and propagation, inter-application communication and component communication, which have the attack features of collusion privilege escalation attacks. The methods, shown in Section 4, Section 5, and Section 6, and Equation (4), are used to verify the behavior equivalence and measure the risk.

Table 6. Benchmarks results.

Test Sets and Test Objects		F						Number of Transition	Equivalence	Measurement Results
		F1	F2	F3	F4	F5	F6
FieldAndObje-ctSensitivity	FieldSensitivity1	T	T	F	T	T	T	1	Weak	0.997521248
	FieldSensitivity2	T	T	F	T	T	T	1	Weak	0.997521248
	FieldSensitivity3	T	T	F	T	T	T	1	Weak	0.997521248
	FieldSensitivity4	T	T	F	T	T	T	1	Weak	0.997521248
	ObjectSensitivity1	T	T	F	T	T	T	1	Weak	0.997521248
	ObjectSensitivity2	T	T	F	T	T	T	2	Weak	0.999088118
InterAppCom-munication	SendSMS	T	T	T	T	T	T	3	Weak	0.99987659
	StartActivityForResult1	T	T	T	T	T	T	4	Weak	0.9999546
InterCompon-entCommunic-ation	ActivityCommunication1	T	T	F	T	T	T	1	Weak	0.997521248
	ActivityCommunication2	T	T	T	T	T	T	2	Weak	0.999664537
	ActivityCommunication3	T	T	T	T	T	T	2	Weak	0.999664537
	ActivityCommunication4	T	T	T	T	T	T	2	Weak	0.999664537
	ActivityCommunication5	T	T	T	T	T	T	2	Weak	0.999664537
	ActivityCommunication6	T	T	T	T	T	T	2	Weak	0.999664537
	ActivityCommunication7	T	T	T	T	T	T	2	Weak	0.999664537
	ActivityCommunication8	T	T	T	T	T	T	2	Weak	0.999664537
	BroadcastTaintAndLeak1	T	T	T	T	T	T	1	Weak	0.999088118
	IntentSink1	T	T	T	T	T	T	1	Weak	0.999088118
	IntentSink2	T	T	T	T	T	T	1	Weak	0.999088118
	IntentSource1	T	T	T	T	F	T	1	Weak	0.997521248
	ServiceCommunication1	T	T	F	T	T	T	1	Weak	0.997521248
	SharedPreferences1	T	T	F	T	T	T	1	Weak	0.997521248

shows the F sets, equivalence relations, and measurement results of each test object, where T represents the existence of feature and F represents the no-existence of feature.

The relationship between the sum of the number of behavior features and transition of the test object and the measurement results is shown in the Figure 6.

From the measurement results for 22 objects in Benchmarks, the following two conclusions are obtained:

(1)

The measurement value in Table 6 is between 0.9975–0.9999, which verifies the effectiveness of this method. The three test sets have information leak of sensitive data, communication between apps and communication between components respectively. From the measurement results, it can be seen that app with the risk of such an information leak has a higher risk of privilege escalation attacks, which is consistent with the actual situation.

(2)

Figure 6 shows that the sum of the number of behavior features and transition is directly proportional to the measurement results. The necessity of building F and extracting migration times is verified.

8.3. Test Set Test and Analysis

8.3.1. Composition of the Test Set

The test set is composed of 51 apps from the Android application market such as Google Play and 3 apps developed by the research team [32]. In order to enrich the test set, 22 categories are selected; and one to three typical apps are selected for each category. The specific classification and number of apps are shown in

Table 7. Categories of the app test set.

Category	Working	Daily Life	Shopping	Home Control	Medical Treatment	Finance	Examination	Browser	Tourism	Beauty	Social Networks
number	3	3	3	2	3	3	3	1	2	1	3
category	Picture browsing	Reading	System tools	News	Home-based elderly care	Study	Exercise	Wallpaper	Plug-in unit	Entertainm-ent	Research group
number	3	1	3	3	3	3	3	1	2	2	3

.

The selection of each typical application is as follows: (1) among the same type of app, it should be ranked as high as possible; (2) the APK should be as small as possible. Following the secondary principle, the size of APKs in the test set is shown in Figure 7. The smallest APK’s size is 0.4 M, the largest APK’s size is 22.5 M, and the average size is 5.33 M.

Meanwhile, apps from the same developer have the convenience of having collusion privilege escalation attacks deliberately created for them, and the same developer is prone to generate the same software vulnerabilities in the process of app development. Therefore, in the selection of samples, six developers and 16 apps are selected, as shown in

Table 8. Percentage of app with the same developer.

	Same Developer	Different Developer
Number	16	38
Percentage	29.6%	70.4%

.

For the test set, the detection method in reference [33] by our research group is used for detection, which is divided into three categories: constituent attack apps, hidden danger apps, and non-dangerous apps. The specific detection results are shown in

Table 9. App attack classification.

	Constituent Attack App	Hidden Dangerous App	Non-Dangerous App
Number	21	19	14
Percentage	38.9%	35.2%	25.9%

.

According to Table 9, unsafe apps account for 74.1% of the test set.

8.3.2. Measurement Results and Analysis

We use the method in Section 4 to extract the feature set F of the test set, and part of the extracted data is shown in

Table 10. Part of the feature set extraction.

Package Name	F1	F2	F3	F4	F5	F6	Transition Number
gjhs.kaoshi.namespace	T	T	T	T	T	T	110
com.hzxh.likerunning	F	F	T	F	T	T	9
com.example.healthmonitor	T	F	F	T	T	T	3
com.vpubao.zhiyue	T	F	T	T	F	T	0
com.gmail.barry2015.android.easysearch_news_cn	F	F	F	F	F	F	0
…	…	…	…	…	…	…	…

.

Using the methods in Section 5 and Section 6, the test set can be divided into weak equivalent app and non-equivalent app, as shown in

Table 11. Decision result of the equivalence relation.

	Weak Equivalence App	Non-Equivalence App
Number	40	14
Percentage	74.1%	25.9%

.

According to the data in Table 9 and Table 11, the attack behavior determination result by our method is consistent with the detection result by reference [33].

To measure the test set, the measurement algorithm is used, and the app determination results and measurement values from Table 10 are shown in

Table 12. Part of the measurement values.

Package Name	Number of Features in the Feature Set	Transition Number	Decision Result	Measurement Value
gjhs.kaoshi.namespace	6	110	weak equivalence	1
com.hzxh.likerunning	3	9	weak equivalence	0.9999938558
com.example.healthmonitor	4	3	weak equivalence	0.9990881180
com.vpubao.zhiyue	4	0	weak equivalence	0.9816843611
com.gmail.barry2015.android.easysearch_news_cn	0	0	Non-equivalence	0
…	…	…	…	…

.

The measurement values of test set are shown in Figure 8a, and the curve values of 40 weakly equivalent apps are shown in Figure 8b.

In Table 8, 13 apps developed by the same developer were verified as a weak equivalent with the attack model. The measurement results are shown in Figure 9.

From the measurement results in Figure 8 and Figure 9, the following three conclusions are obtained:

(1)

The measurement results clearly show the risk degree of the attack. From Figure 8b, it can be seen that the measurement values of weakly equivalent apps with the collusion privilege escalation attack model are all above 0.86, which is consistent with the actual danger level of the app.

(2)

The measurement value is proportional to the number of features in the feature set and the number of transitions of sensitive data. As can be seen from Figure 8b and Figure 9, the more features and sensitive data transition times, the greater the risk measurement. However, in Figure 8a, there are some particularities, so we need to further strengthen the analysis and refine the feature set and the measurement function.

(3)

The risk of collusion privilege escalation attacks is higher in an app developed by the same developer. From Figure 9, it can be seen that the measurement values of weakly equivalent apps with the attack model are all above 0.95, which proves that the risk of collusion privilege escalation attacks is high.

9. Conclusions

Process algebra was used to model a component’s behavior and attack behavior based on the extracted behavior feature set and the number of transitions. Then, weak equivalence was used for decision making. Finally, a risk measurement was carried out based on the measurement function. Through the case, benchmarks and test set experiments, it is verified that the measurement results of this method can clearly show the risk degree of collusion privilege escalation attacks for an app. From the research in this paper, it can be seen that if an app has more attack features and sensitive data transition times, then the app has a higher risk measurement value. Furthermore, the risk of collusion privilege escalation attacks for apps that were developed by the same developer is significantly higher than that of other apps. Future work will be carried out in relation to the following two aspects:

(1)

Because there are many apps with measurement values in the range of 0.86–0.99, it is necessary to refine the measurement function and privilege escalation attacks behavior feature set to ensure that the measurement value is more reasonable.

(2)

We used the same weight of features in the feature set, and different weights can be calculated using a correlation method to improve the accuracy of the measurement.