DroidGen: Constraint-based and Data-Driven
Policy Generation for Android
Mohamed Nassim Seghir1 and David Aspinall2
1

arXiv:1612.07586v1 [cs.CR] 22 Dec 2016

2

University College London
University of Edinburgh

Abstract. We present DroidGen a tool for automatic anti-malware policy inference. DroidGen is data-driven: uses a training set of malware and
benign applications and makes call to a constraint solver to generate a
policy under which a maximum of malware is excluded and a maximum
of benign applications is allowed. Preliminary results are encouraging.
We are able to automatically generate a policy which filters out 91% of
the tested Android malware. Moreover, compared to black-box machine
learning classifiers, our method has the advantage of generating policies
in a declarative readable format. We illustrate our approach, describe its
implementation and report on experimental results.

1

Introduction

Security on Android is enforced via permissions giving access to resources on the
device. These permissions are often too coarse and their attribution is based on
an all-or-nothing decision in the vast majority of Android versions in actual use.
Additional security policies can be prescribed to impose a finer-grained control
over resources. However, some key questions must be addressed: who writes the
policies? What is the rational behind them? An answer could be that policies
are written by experts based on intuition and prior knowledge. What can we
do then in the absence of expertise? Moreover, are we sure that they provide
enough coverage?
We present DroidGen a tool for the systematic generation of anti-malware
policies. DroidGen is fully automatic and data-driven: it takes as input two
training sets of benign and malware applications and returns a policy as output.
The resulting policy represents an optimal solution for a constraint satisfaction
problem expressing that the discarded malware should be maximized while the
number of excluded benign applications must be minimized. The intuition behind
this is that the solution will capture the maximum of features which are specific
to malware and less common to benign applications. Our goal is to make the
generated policy as general as possible to the point of allowing us to make
decisions regarding new applications which are not part of the training set.
In addition to being fully push-button, DroidGen is able to generate a policy
that filters out 91% of malware from a representative testing set of Android
applications with only a false positive rate of 6%. Moreover, having the policies

in a declarative readable format can boost the effort of the malware analyst
by providing diagnosis and pointing her to suspicious parts of the application.
In what follows we present the main ingredients of DroidGen, describe their
functionality and report on experimental results.

2

Application Abstraction

DroidGen proceeds in several phases: application abstraction, constraint extraction and constraint solving, see Figure 1. Our goal is to infer policies that distin-

Fig. 1: Illustration of DroidGen’s Main Ingredients

guish between good and bad behaviour. As it is not practical to have one policy
per malicious application, we need to identify common behaviours of applications. Hence the first phase of our approach is the derivation of specifications
(abstractions) which are general representations of applications. Given an application A, the corresponding high level specification Spec(A) consists of a set of
properties {p1 , . . . , pk } such that each property p has the following grammar:
p := c : r
c := entry point | activity | service | receiver
| onclick handler | ontouch handler | lc
lc := oncreate | onstart | onresume | . . .
u := perm | api
A property p describes a context part c in which a resource r is used. The resource
part can be either a permission perm or api referring to an api method identifier
which consists of the method name, its signature and the class it belongs to.
The context c can be entry point referring to all entry points of the app, activity representing methods belonging to activities, service for methods belonging
to service components3 , etc. We also have onclick handler and ontouch handler
respectively referring to click and touch event handlers. Moreover, c can be an
activity life-cycle callback such as oncreate, onstart, etc.4 Activity callbacks as
well as the touch and click event handlers are also entry points.
A property p of the form c : r belongs to the specification of an application A
if r (perm or api) is used within the context c in A. In other words: it exists at
3
4

activity, service and receiver are some of the building blocks of Android applications.
Some components have a life-cycle governing their callbacks invocation.

least one method matching c from which r is transitively called (reachable). To
address such a query, we compute the transitive closure of the call graph [9]. We
propagate permissions (APIs) backwards from callees to callers until we reach a
fixpoint.
For illustration, let us consider the example in Figure 2. On the left hand
side, we have code snippets representing a simple audio recording application
named Recorder which inherits from an Activity component. On the right hand
side, we have the corresponding specifications in terms of APIs (Figure 2(a))
and in terms of permissions (Figure 2(b)). The method setAudioSource, which
sets the recording medium for the media recorder, is reachable (called) from
the Activity life-cycle method onCretae, hence we have the entry oncreate: setAudioSource in the specification map (a). We also have the entry oncreate:
record audio in the permission-based specification map (b) as the permission
record audio is associated with the API method setAudioSource according
to the Android framework implementation. Similarly, the API method setOutputFile is associated with the context onclick (a) as it is transitively reachable
(through startRecording) from the click handler method onClick. Hence permission write external storage, for writing the recording file on disk, is also
associated with onclick (b). Both APIs and permissions are also associated with
the context activity as they are reachable from methods which are activity members. We use results from [3] to associate APIs with the corresponding permissions.

public c l a s s R e c o r d e r extends A c t i v i t y
implements O n C l i c k L i s t e n e r {
private MediaRecorder myRecorder ;
...
public void o n C r e a t e ( . . . ) {
myRecorder = new MediaRecorder ( ) ;
// u s e s RECORD AUDIO p e r m i s s i o n
myRecorder . s e t A u d i o S o u r c e ( . . . ) ;
}
private void s t a r t R e c o r d i n g ( ) {
// u s e s WRITE EXTERNAL STORAGE
myRecorder . s e t O u t p u t F i l e ( . . . ) ;
recorder . start ( ) ;
}
public void o n C l i c k ( . . . ) {
startRecording ( ) ;
}

Spec(Recorder)
oncreate:
onclick:
activity:
activity:

setAudioSource
setOutputFile
setAudioSource
setOutputFile
(a)

Spec(Recorder)
oncreate:
onclick:
activity:
activity:

record audio
write external storage
record audio
write external storage
(b)

}

Fig. 2: Code snippets sketching a simple audio recording application together with the
corresponding specifications based on APIs (a) and based on permissions (b)

3

Specifications to Policies: an Optimisation Problem?

DroidGen tries to derive a set of rules (policy) under which a maximum number
of benign applications is allowed and a maximum of malware is excluded. This
is an optimization problem with two conflicting objectives. Consider
Spec(benign1 ) = {pa }
Spec(benign2 ) =
{pc }
Spec(benign3 ) = {pb , pe }

Spec(malware1 ) = {pa , pb }
Spec(malware2 ) = {pa , pc }
Spec(malware3 ) =
{pd }

Each application (benign or malware) is described by its specification consisting
of a set of properties (pi ’s). As seen previously, a property pi can be for example
activity : record audio, meaning that the permission record audio is used within an
activity. A policy excludes an application if it contradicts one of its properties.
We want to find the policy that allows the maximum of benign applications and
excludes the maximum of malware. This is formulated as:
M ax[I(pa ) + I(pc ) + I(pb ∧ pe ) − (I(pa ∧ pb ) + I(pa ∧ pc ) + I(pd ))]
{z
} |
{z
}
|
benign

malware

where I(x) is the function that returns 1 if x is true or 0 otherwise. This type
of optimization problems where we have a mixture of theories of arithmetic and
logic can be efficiently solved via an SMT solver such as Z3 [7]. It gives us the
solution: pa = 0, pb = 1, pc = 1, pd = 0 and pe = 1. Hence, the policy will
contain the two rules ¬pa and ¬pd which filter out all malware but also exclude
the benign application benign1 . A policy is violated if one of its rules is violated.
Policy Verification and Diagnosis. Once we have inferred a policy, we want
to use it to filter out applications violating it. A policy P = {¬p1 , . . . , ¬pk }
is violated by an application A if {p1 , . . . , pk } ∩ Spec(A) 6= ∅, meaning that A
contradicts (violates) at least one of the rules of P . In case of policy violation,
the violated rule, e.g. ¬p, can give some indication about a potential malicious
behaviour. DroidGen maps back the violated rule to the code in order to have
a view of the violation origin. For p = (c : u), a sequence of method invocations
m1 , .., mk is generated, such that m1 matches the context c and mk invokes u.

4

Implementation and Experiments

DroidGen5 is written in Python and uses Androguard6 as front-end for parsing
and decompiling Android applications. DroidGen automatically builds abstractions for the applications which are directly accepted in APK binary format.
This process takes around 6 seconds per application. An optimization problem
in terms of constraints over the computed abstractions is then generated and
5
6

www0.cs.ucl.ac.uk/staff/n.seghir/tools/DroidGen
https://github.com/androguard

the Z3 SMT solver is called to solve it. Finally, the output of Z3 is interpreted
and translated to a readable format (policy). Policy generation takes about 7
seconds and its verification takes no more than 6 seconds per app on average.
We derived two kinds of policies based on a training set of 1000 malware
applications from Drebin7 and 1000 benign ones obtained from Intel Security
(McAfee). The first policy Pp is solely based on permissions and is composed
of 65 rules. The other policy Pa is exclusively based on APIs and contains 152
rules. Snippets from both policies are illustrated in the appendix. We have applied the two policies to a testing set of 1000 malware applications and 1000
benign ones (different from the training sets) from the same providers. Results
are summarised in Table 1. The policy Pa composed of rules over APIs performs
Policy

Malware filtered out Benign excluded

APIs (Pa )
910/1000
59/1000
Permission (Pp )
758/1000
179/1000
Table 1: Results for a permissions-based policy (Pp ) vs. an API-based one (Pa )

better than the one that uses permissions in terms of malware detection as it is
able to filter out 91% of malware while Pp is only able to detect 76%. It also has
a better false positive rate as it only excludes 6% of benign applications, while
Pp excludes 18%. Being able to detect 91% of malware is encouraging as it is
comparable to the results obtained with some of the professional security tools
(https://www.av-test.org/)8 . Moreover, our approach is fully automatic and the
actual implementation does not exploit the full expressiveness of the policy space
as we only generate policies in a simple conjunctive form. We plan to further
investigate the generation of policies in arbitrary propositional forms.

5

Related Work

Many tools for analysing various security aspects of Android have emerged [2,
5, 6, 8]. They either check or enforce certain security properties (policies). These
policies are either hard-coded or manually provided. Our work complements
such tools by providing the automatic means for inferring the properties to be
checked. Hence, DroidGen can serve as a front-end for a verification tool such
as EviCheck [9] to keep the user completely out of the loop.
Also various machine-learning-based approaches have been proposed for malware detection [1,4,10,11]. While some of them outperform our method, We did
not yet exploit the entire power of the policy language. We are planning to
allow more general forms for the rules, which could significantly improve the results. Moreover, many of the machine-learning based approaches do not provide
further indications about potential malicious behaviours in an application. Our
7
8

http://user.informatik.uni-goettingen.de/∼darp/drebin/
We refer to AV-TEST benchmarks dated September 2014 as our dataset was collected during the same period.

approach returns policies in a declarative readable format which is helpful in
terms of code inspection and diagnosis. Some qualitative results are reported in
the appendix. To the best of our knowledge, our approach is unique for being
data-driven and using a constraint solver for inferring anti-malware policies.

6

Conclusion and Future Work

We have presented DroidGen a tool for the automatic generation of anti-malware
policies. It is data-driven and uses a constraint solver for policy inference. DroidGen is able to automatically infer an anti-malware policy which filters out 91% of
the tested malware with the additional benefit of being fully automatic. Having
the policies in declarative readable format can boost the effort of the malware
analyst by pointing her to suspicious parts of the application. As future work,
we plan to generate more expressive policies by not restring their form to conjunctions of rules. We also plan to generate anti-malware policies for malware
families with the goal of obtaining semantics-based signatures (see appendix).

References
1. D. Arp, M. Spreitzenbarth, M. Hubner, H. Gascon, and K. Rieck. DREBIN: effective and explainable detection of android malware in your pocket. In NDSS,
2014.
2. S. Arzt, S. Rasthofer, C. Fritz, E. Bodden, A. Bartel, J. Klein, Y. L. Traon,
D. Octeau, and P. McDaniel. Flowdroid: precise context, flow, field, object-sensitive
and lifecycle-aware taint analysis for android apps. In PLDI, page 29, 2014.
3. K. W. Y. Au, Y. F. Zhou, Z. Huang, and D. Lie. Pscout: analyzing the Android
permission specification. In CCS, pages 217–228, 2012.
4. V. Avdiienko, K. Kuznetsov, A. Gorla, A. Zeller, S. Arzt, S. Rasthofer, and E. Bodden. Mining Apps for Abnormal Usage of Sensitive Data. In ICSE, pages 426–436,
2015.
5. M. Backes, S. Gerling, C. Hammer, M. Maffei, and P. von Styp-Rekowsky. Appguard - enforcing user requirements on Android apps. In TACAS, pages 543–548,
2013.
6. E. Chin, A. P. Felt, K. Greenwood, and D. Wagner. Analyzing inter-application
communication in Android. In MobiSys, pages 239–252, 2011.
7. L. M. de Moura and N. Bjørner. Z3: An efficient smt solver. In TACAS, pages
337–340, 2008.
8. S. Fahl, M. Harbach, T. Muders, M. Smith, L. Baumgärtner, and B. Freisleben.
Why Eve and Mallory love Android: an analysis of Android SSL (in)security. In
ACM Conference on Computer and Communications Security, pages 50–61, 2012.
9. M. N. Seghir and D. Aspinall. Evicheck: Digital evidence for android. In ATVA,
pages 221–227, 2015.
10. C. Yang, Z. Xu, G. Gu, V. Yegneswaran, and P. A. Porras. Droidminer: Automated mining and characterization of fine-grained malicious behaviors in android
applications. In ESORICS, pages 163–182, 2014.
11. W. Yang, X. Xiao, B. Andow, S. Li, T. Xie, and W. Enck. Appcontext: Differentiating malicious and benign mobile app behaviors using context. In ICSE, pages
303–313, 2015.

