Android OS supports multiple communication methods between apps. This opens the possibility to carry out threats in a collaborative fashion, c.f. the Soundcomber example from 2011. In this paper we provide a concise definition of collusion and report on a number of automated detection approaches, developed in co-operation with Intel Security.
The Android operating system (OS) is designed with a number of built-in security features such as app sandboxing and fairly granular access controls based on permissions. In real life, however, the isolation of apps is limited. In some respects even the opposite is true – there are many ways for apps to communicate across sandbox boundaries. The Android OS supports multiple communication methods which are fully documented (such as messaging via intents). The ability of apps with different security postures to communicate has a negative effect on security as an app (in a sandbox which has permissions to handle such data) is allowed to let sensitive data flow to another app (in another sandbox which has been denied permission to handle such data) and eventually leak out.
The Android ecosystem exacerbates the problem as the market pressure leads many developers to embed advertisement libraries into their apps. As a result, such code may be present in thousands of apps (all bearing different permissions). Advertisers have a known tendency to disregard user privacy in favour of monetisation. So there exists a risk that ad-libraries may communicate between sandboxes even without knowledge of apps authors to transmit sensitive data across, risking exposure and disregarding privacy.
Of course, any unscrupulous developer may also
split functionality which they prefer to hide between
multiple apps. Malicious behaviours similar to this are
evident from known cases of apps exploiting insecure
exposure of sensitive data by other apps [
Researchers have demonstrated that sets of apps
may violate the permissions model causing data leaks
or carrying malware [
In recent work [
This paper contributes towards a practical automated system for collusion detection. We give a definition of collusion in Section 2. This is followed by two potential approaches to filter down to potential candidates for collusion, using a rule based approach developed in Prolog in Section 3 and another statistical approach in Section 4. Section 5 presents a modelchecking approach to detecting collusion in Android apps. Section 6 delves into the experimental outcomes and Section 7 discusses related work. Section 8 summarises our contributions and Section 9 concludes the paper with thoughts on future work. 2
Our notion of collusion refers to the ability for a set
of apps to carry out a threat in a collaborative
fashion. This is in contrast to most existing work, where
collusion is usually associated with inter-app
communications and information leakage (see Section 7). We
consider that colluding apps can carry out any threat
such as the ones posed by single apps. The range of
such threats includes [
A threat can be described by a set of actions executed in a certain order. We model this by a partially ordered set (T, ≤), where T is the set of actions and ≤ specifies the execution order. When (T, ≤) is carried out, actions from T are sequentially executed, according to some total order ≤∗ such that ≤⊆≤∗; in other words, (T, ≤∗) is a total extension of (T, ≤). Let Ex((T, ≤)) denote the set of all possible total extensions of (T, ≤); i.e., all possible ways of carrying out threat (T, ≤). Similarly, we also define inter-app communication as a partially ordered set. In this paper we discuss overt communications channels only.
We define collusion as follows: A1: Actions are operations provided by Android API (such as record audio, access file, write file, send data, etc.). Let Act denote the set of all actions. A2: Actions can be associated with a number of attributes (such as permissions, input parameters, etc.). Let B denote the set of all action attributes and pms : Act → ℘(B) specify the set of permissions required by Android to execute an action.
READ CONTACTS
Contact_app
Weather_app Shared Prefs.
INTERNET A3: A threat t = (T, ≤) is a partially ordered set. Let τ denote the set of all threats. In the scope of this paper, τ represents the set of all known threats caused by single applications.
A4: An inter-app communication c = (C, ≤) is a partially ordered set. Let com denote the set of all known inter-app communications.
Definition 1 (Collusion). A set S consisting of at least two apps is colluding if together they execute a sequence A ∈ Act∗ such that: 1. there exists a subsequence A0 of A such that A0 ∈ Ex(t) for some t ∈ τ ; furthermore, A0 is collectively executed involving all apps in S, i.e., each app in S executes at least one action in A0; and 2. there exists a subsequence C0 of A such that C0 ∈
Ex(c) for some c ∈ com.
It is a general challenge to distinguish between benign and malicious application behaviours. Thus, our definition makes the realistic assumption that there are a number of known threats, e.g., Intel Security regularly identifies apps to be malicious, realising known threats. Now, collusion can be seen as a camouflage mechanism: the individual apps appear harmless, none of them alone poses a threat, e.g., they would not be able to execute a threat just in terms of their permissions; in combinatation, however, they realise a threat.
To illustrate our definition we present an abstract example1.
Example 1 (Stealing contact data). The two apps graphically represented in Figure 1 perform information theft: the Contact app reads the contacts database to pass the data to Weather app, which sends the data to a remote server controlled by the adversary. The information is sent through shared preferences.
Using the collusion definition we can describe the actions performed by both apps as: ActContact app = {aread contacts}, ActWeather app = {asend file}. with pms(aread contacts) = {Permission contacts} and pms(asend file) = {Permission internet }. The information threat t is given by T = {aread contacts, asend file} and defining aread contacts ≤ asend file. The inter-app communication is defined as =
comContact app {sendshared prefs}, comWeather app = {recvshared prefs} and sendshared prefs ≤ recvshared prefs.
1Concrete examples are available on request.
Our first approximation to detect app collusion utilises Logic Programming in Prolog. Its goal is to serve as a fast, computationally cheap filter that detects potentially colluding apps. For such a first filter it is enough to be based on permissions; together with a further sifting mechanism (not discussed here) on permissions, in practical work on real world apps this filter turns out to be effective to detect colluding apps in the wild.
Our filter (1) uses Androguard [
We utilise an action set Actprolog composed out of four different high level actions: accessing sensitive information, using an API that can directly cost money, controlling device services (e.g. camera, etc.), and sending information to other devices and the Internet. To find out which of these actions an app could carry out, we extract its set of permissions pmsprolog. Each permission is mapped to one or more of the four high level actions. For example, an app that declares the INTERNET permission will be capable of sending information outside the device:
uses(App, PInternet) → information outside(App) 3.2
The communication channels established by an app are characterised by its API calls and the permissions declared in its manifest file. We cover communication actions (comprolog) that can be created as follows: • Intents are messages used to request tasks from other application components (activities, services or broadcast receivers). Activities, services and broadcast receivers declare the intents they can handle by declaring a set of intent filters. • External Storage is a storage space shared between all the apps installed without restrictions. Apps accessing the external storage need to declare the READ EXTERNAL STORAGE permission. To enable writing, apps must declare WRITE EXTERNAL STORAGE. • Shared Preferences are an OS feature to store keyvalue pairs of data. Although it is not intended for inter-app communication, apps can use key-value pairs to exchange information if proper permissions are defined (before Android 4.4).
We map apps to sending and receiving actions by inspecting their code and manifest files. When using intents and shared preferences we are able to specify the communication channel using the intent actions and preference files and packages respectively. If an application sends a broadcast intent with the action SEND FILE we consider the following: send broadcast(App, Intentsend file)
→ send(App, Intentsend file) We consider that two apps communicate if one of them is able to send and the other to receive through the same channel. This allows to detect communication paths composed by an arbitrary number of apps: send(Appa, channel) ∧ receive(Appb, channel) → communicate(Appa, Appb, channel) 3.3
Our threat set τprolog considers information theft, money theft and service misuse. As our definition states, each of the threats is characterised by a sequence of actions. For example, the information theft threat is codified as the following Prolog rule: → ∧ ∧ sensitive information(Appa) information outside(Appb) communicate(Appa, Appb, channel) collusion(Appa, Appb) Currently, we do not take into account the order of action execution. 4
Assessing the collusion possibility In this section, we apply machine learning to classify app sets into colluding and non-colluding ones. To this end, we first define a probabilistic model. Then we train the model, i.e., estimate the model parameters on a training data set. As a third step we validate the model using a validation data set. Additionally, in Section 6.3, we check the model with testing data. 4.1
Estimating the collusion possibility within a set S of apps involves to estimate two different likelihood components Lτ and Lcom. Lτ denotes the likelihood of carrying out a threat. Lcom denotes the likelihood of performing some inter-app communication. Hence, the likelihood of colluding within S is given by Lτ × Lcom.
In order to estimate Lτ , we employ a so-called Naive
Bayesian informative [
To compute Lτ we define Lτ = ln{(P (Y ))−1}. This
reflects on the likelihood of an app set to “being
malicious” increasing as the number of permissions
requested increases. Therefore, any monotonically
decreasing function can be chosen [
To complete our modelling, we need to estimate
values λˆj that replace λj in the computation of Lτ . To
this end – to avoid over fitting P (Y ) – we estimate
λj using informative beta prior distributions [
P yj + αj
N + αj + βj
(1)
where N is the number of apps in the training set and
αj , βj are penalty effects. In this work we set αj = 1.
βj depend on the critical level of permissions as given
in [
We consider Lcom to be a binary function such that Lcom ∈ {1, 0} which takes the value 1 if there is any inter app communication within S, 0 otherwise. 4.2
Up to our recent discovery [
For this analysis, we implemented an automated
process using R [
Figure 2 presents Lτ values for the validation dataset in which good visual separation can be seen between two classes with a lower (=0.50) and upper (=0.69) bounds for a discriminant line. Table 1 presents the confusion matrix obtained by fitting the best possible linear discriminant line at Lτ = 0.55 in Figure 2.
n=240 Predicted Colluding
Predicted Non-Colluding
Actual Colluding
Actual
Non-Colluding 114 6 7 113
2Though our attack model is multiple apps, Lτ focuses only on operations required to execute a threat by a single app attack model. Additional communication operations required to execute the same threat in colluding model are covered by Lcom. Precision quantifies the notion of specificity while Fmeasure provides a way to judge the overall performance of the model for each class. The higher these values are, the better the performance is. Such values could be due to a bias of the validation sample towards the methodology. Further investigation on the bias of the evaluation dataset is left for future work. 5
We demonstrate the effective attempt to detect
collusion via model-checking. Figure 3 shows the basic
work-flow employed: it starts with a set of apps in the
Dalvik Executable format DEX [
The rewriting logic semantics framework K allows
the user to define configurations, computations and
rules [
const Register, Int for loading an integer constant Int into a register Register is captured by a rule which reads: provided the current instruction is to load an integer I into a register R, then the cell “regs” capturing the state of the registers is updated by binding the value I to register R. The SMALI language also includes procedure calls. These allow to access functionality provided by the Android operating system, e.g., to read protected resources such as the GPS location or to send/receive a broadcast intent. Thus, besides encoding SMALI instructions in K, we also model the infrastructure that Android provides to apps.
The executions of the above semantics, instruction after instruction, defines the computations. However, the concrete semantics is far too detailed for effective model-checking. Therefore, we implement an abstraction in form of a data flow analysis. Here we represent each method individually as a graph, where registers, types, and constants are the nodes, and there is an edge between two nodes n1 and n2 iff n2 is a parameter of the SMALI command that stores a value in n1. For example, the SMALI command const r1, 42 would lead to an edge from node “42” to node “R1”. Analysing such graphs allows to detect which commands influence the values sent, say, in a broadcast intent, or publishing via the internet; these commands can be grouped into blocks and – rather than computing with concrete values – their effect can be captured symbolically.
For the detection of collusion, our K semantics carries a “trace” cell that records which operations provided by the Android API – see Definition 1 – have been executed in a specific run. Based on the “trace” cell we define collusion via a K rule: provided that the GPS location has been accessed, this value has been sent in a broadcast, this value has been received from a broadcast, and finally this value has been published, in that case we detect collusion “information theft”.
Practical experiments with small apps demonstrate that this approach is feasible. Using the Maude modelchecker, the state space of the (abstraction) of two apps is small, with only 8 states for the given example and the check takes less than a second. When modifying the apps in such a way that the information flow is broken, by, say using a different name for the broadcast and thus disabling communication between the apps, model-checking shows that no collusion is happening.
We use symbolic analysis over the byte code of the set S in order to obtain an in-depth inspection of the communication patterns. In the byte code of each app in S we detect the flow of communication with another app and a safe over-approximation of the data being communicated. We use static analysis over the byte code of apps to extract communication-flow between apps and data-flow inside each app. The data-flow information is filtered based on the private data being read and communicated.
It is future work, to complete the encoding to cover the full DEX language and to experiment with larger apps all well as with larger number of apps to address the fundamental question of scalability. We further intend to prove the abstraction to be sound, to show that if model-checking the abstracted code detects collusion then there is collusion in the original code, and to have a more general definition of collusion.
In this section we compile first experimental results obtained by applying the three methods discussed above to an artificial set. In order to validate our different approaches against a known ground truth, we have created fourteen apps that cover all threats and use all communication channels described earlier in this paper. They are organised in four colluding sets: The Document Extractor set consists of one app (id 1 ) that looks for sensitive documents on the external storage; the other app (id 2 ) sends the information received (via SharedPreferences) to a remote server. The Botnet set consists of four apps. One app (id 3 ) acts as a relay that receives orders from the command and control center. The other colluding apps execute commands (delivered via BroadcastIntents) depending on their permissions: sending SMS messages (id 4 ), stealing the user’s contacts (id 5 ) and starting and stopping tasks (id 6 ). The Contact Extractor set consists of three apps. The first (id 7 ) reads contacts from the address book, the second (id 8 ) forwards them via the external storage to the third one (id 9 ), which sends them to the Internet. The first and second app communicate via BroadcastIntents. The Location Stealing set consists of one app (id 12 ) that reads the user location and shares it with the second app (id 13 ), which sends the information to the Internet.
The three non-colluding apps are a document viewer (id 10 ), an information sharing app (id 11 ) and a location viewer (id 14 ). The first app is able to display different file types in the device screen and use other apps (via broadcast intents) to share their uniform resource identifier (URI). The second app receives text fragments from other apps and sends them to a remote server. The third app receives a location from another app (with the same intent used by apps 12 and 13) and shows it to the user on the screen. 6.2
Table 2 shows the results obtained with our rule based approached from Section 3 on the apps from Section 6.1. The entry “dark red club” in row 1 and column 2 means: the program detects that app id 1 sends information to app id 2, and these two apps collude on an “information theft”. As we take communication direction into consideration, the resulting matrix is nonsymmetric, e.g., there is no entry in row 2 and column 1. The entry “light red club” in row 1 and column 10 means: the program flags collusion of type “information theft” though the set {id 1, id 10 } is clean.The approach identifies all colluding app sets. It also flags 5 6 7 8 9 10 11 12 13 14
♣ ♣ $♣ ♠ ♠ ♣ ♣ ♣
♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ eight false positives due to over-approximation. Note, that there are no false negatives due to the nature of our test set: it utilises only those communication methods that our Prolog approach is able to identify. Table 3 shows results from our alternative approach from Section 4 on the same set of apps. Each cell denotes the Lτ value for the corresponding pair. To minimise false negatives, we use the lower bound (=0.50) gained from the validation data set for the discriminant line as threshold for Lτ . We report possible collusion if Lτ ≥ 0.5 and Lcom = 1, otherwise we report non-collusion. This yields symmetric data – for readability we leave the lower half of the matrix empty. Dark red shows true positives, light red shows false positives, dark green shows true negatives, and light green shows false negatives.
This approach finds two of the four colluding app sets and flags five false positives. It relies on a 3rd party tool to detect inter-app communication which ignores communication using shared preferences, thus the app set {id 1, id 2 } is not detected. As we restrict ourselves to pairwise analysis only, the app set {id 7, id 9 } can’t be detected, as it communicates via id 8. Finally, app set {id 12, id 13 } was not reported since its Lτ value is less than the chosen threshold. Choosing a lower threshold could avoid this false negative, but at the cost of a lower class accuracy and performance.
A precise estimation of Lcom would be useful in
order to reduce the number of false positives in our
analysis. However, communication is only a necessary, not
a sufficient condition for collusion. A recent study [
Marforio et al. [
ComDroid [
We inspect two sets of applications, one colluding {id 12, id 13 } and another non-clouding pair {id 12, id 14 } with software model checking as described in Section 5. The sender id 12 and receiver (id 13 or id 14 ) communicate via broadcast messages containing the details of the GPS location. In the colluding case the broadcast is successful, i.e., the sender reads the GPS location then broadcasts it, and the receiver gets the broadcast then publishes the GPS location on the internet. In the non-colluding case, the sender still broadcasts the private data which reaches the receiver but this data is never published. Instead, the receiver publishes something else. The data-flow analysis shows, for the non-colluding case, that the private data is received but is never published. This aspect is not obvious for our Prolog filter. Similarly, the dataflow analysis detects collusion in the first case and re
We have presented a new and concise definition of
collusion in the context of Android OS. Colluding apps
may carry out information theft, money theft, or
service misuse; to this end, malware is distributed over
multiple apps. As demonstrated by Soundcomber (and
our own app sets), collusion is a possibility – which we
recently demonstrated to exists in the wild [
Like in [
We have to emphasise that such tools are
essential for many collusion-detection methods. Besides
our model checking approach, one could, for example,
think of the approach to merge pair of apps into a
single app to inspect aggregated data flows [
Alternatively (or additionally), to the two filters described in our paper, imprecise heuristic methods to find “interesting” app sets may include: statistical code analysis of apps (e.g. to locate APIs potentially responsible to communication, accessing sensitive information, etc.); and taking into account apps’ publication time and distribution channel (app market, direct installation, etc.).
Attackers are more likely to release colluding apps in a relatively short time frame and that they are likely to engineer the distribution in such a way that sufficient number of users would install the whole set (likely from the same app market). To discover such scenarios one can employ: analysis of security telemetry focused on users devices to examine installation/removal of apps, list of processes simultaneously executing, device-specific APK download/installation logs from app markets (like Google PlayTM) and meta-data about APKs in app markets (upload time by developers, developer ID, source IP, etc.). Such data would allow constructing a full view of existing app sets on user devices. Only naturally occurring sets (either installed on same device or actually executing simultaneously) may be analysed for collusion which should drastically reduce the number of sets that require deeper analysis.
Our goal is to build a fully automated and effective collusion detection system, and tool performance will be central to address scale. It is not clear yet where the bottleneck will be when we apply our approach to real-life apps. Further work will focus on identifying these bottlenecks to optimise the slowest elements of our tool-chain. Detecting covert channels would be a challenge as modelling such will not be trivial.
This work has been funded by EPSRC and we are excited to work on this challenging piece of research3. A special thanks goes to Erwin R. Catesbeiana (Jr) for excellent guidance through the Android ecosystem.