Florian Kerschbaum

Martin Härterich

Patrick Grofig

Mathias Kohler

Andreas Schaad

Axel Schröpfer

Walter Tighzert

Optimal Re-encryption Strategy for Joins in Encrypted Databases

Keywords: Encrypted Database, Proxy Re-encryption, Adjustable Join

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Recently, encrypted databases [START_REF] Binnig | Dictionary-based order-preserving string compression for main memory column stores[END_REF][START_REF] Hacigümüs | Executing SQL over encrypted data in the database-service-provider model[END_REF][START_REF] Popa | CryptDB: Protecting confidentiality with encrypted query processing[END_REF] that provide the client with additional protection in the cloud or database-as-a-service setting have emerged. In these databases all data are encrypted at the client -where also the keys are exclusively stored -and queries are performed over encrypted data. In order to perform a selection, e.g. SELECT x FROM y WHERE z = 1, the columns for selection (z in the example) needs to be encrypted using deterministic encryption, i.e., a plaintext always enciphers to the same ciphertext. In order to perform a join, e.g. SELECT a.b, c.d FROM a, c WHERE a.e = c.f, the columns for the join (e and f in the example) need to be encrypted using the same key. This is achieved using an operation called proxy re-encryption (PRE) [START_REF] Blaze | Divertible protocols and atomic proxy cryptography[END_REF]. In PRE a proxy translates a ciphertext under one key K A to a ciphertext under another key K B without knowing either of the two keys.

The encrypted database performs this PRE when required, i.e. when it has received a query performing a join over two previously unjoined columns. The client then issues a PRE key to the databases which re-encrypts at least one column, such that both columns are encrypted under the same key. The (equi-) join operator can then operate using the same algorithm as on an unencrypted database.

The reason for dynamically adjusting the database encryption to the queries is that this PRE reveals additional information to an attacker observing the database. He now obtains additional ciphertexts he can use in cryptanalysis of the keys. Deterministic encryption is only provably secure in high-entropy domains [START_REF] Bellare | Deterministic and efficiently searchable encryption[END_REF], such that these additional ciphertexts may be of significant help.

When the database issues the PRE key, it has to choose a column which to re-encrypt; in the example either e or f. Furthermore, it has to make this choice under an unknown schedule of future joins. Naive approaches may even lead to an infinite number of re-encryptions.

In this paper we present a re-encryption column selection algorithm that results in at most O(n 3/2 ) re-encryptions for n columns under any schedule of join operations. Furthermore we give a second algorithm that occasionally leads to re-encryption of both columns to be joined, but which results in a better bound of at most O(n log n) re-encryptions (where, of course, the PRE of two columns counts as two PREs). We show that this is the best possible bound we can achieve under the assumption of an a priori unknown schedule.

The remainder of the paper is structured as follows. We review related work and background on encrypted databases in Section 2. Section 3 gives an introduction to the problem using the naive approaches. Our algorithms including proofs of bounds on the number of re-encryptions are shown in Section 4 . We show our experimental evaluation in Section 5. Section 6 summarizes our findings.

Related Work

The design goal of encrypted databases in the database-as-a-service setting is to move the encryption layer above the query processing layer. All query process operators are supposed to work on encrypted data. This ensures that (almost) any query can be processed on the encrypted data.

The first such database was introduced in [START_REF] Hacigümüs | Executing SQL over encrypted data in the database-service-provider model[END_REF]. It provided special operators for many queries and it was necessary to post-process and filter many queries. This was improved by [START_REF] Binnig | Dictionary-based order-preserving string compression for main memory column stores[END_REF] where the database operators remain unchanged. This enables using existing, commercial database systems for encryption in the cloud. Nevertheless, it requires the use of special encryption schemes such as orderpreserving encryption [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF].

In [START_REF] Binnig | Dictionary-based order-preserving string compression for main memory column stores[END_REF] the encryption was replaced by using the identifiers in the data dictionary and leaving the dictionary at the client. This requires even less modification to the database and is as secure as order-preserving encryption. Nevertheless, it does not allow aggregation.

Order-preserving [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF] or even deterministic encryption is commonly not considered very secure. It is therefore advisable to encrypt only the columns necessary for performing the queries using these encryption schemes. Yet, these columns may not be known in advance and the database must adjust its encryption state to the queries performed.

In order to adjust the encryption to the queries on the fly, [START_REF] Popa | CryptDB: Protecting confidentiality with encrypted query processing[END_REF] proposed the use of onion encryption. While it is possible to choose an optimally secure encryption, if all queries are known upfront, it is difficult to do so, if any queries are processed on the fly. Therefore each data item is encrypted using onion encryption and decrypted to the corresponding onion layer on the fly. Our encryption onion is composed of the following layers:

-L3 -Randomized Encryption: IND-CPA secure encryption allowing only retrieval using AES encryption in CBC mode. -L2 -Deterministic Encryption: Allows processing of equality comparisons.

In deterministic encryption one plaintext always enciphers to the same ciphertext. -L1 -Order-Preserving Encryption: Allows processing of greater-than comparisons using the encryption scheme of [START_REF] Boldyreva | Order-preserving symmetric encryption[END_REF]. -L0 -Data: The data to be encrypted.

The layers of the onion represent a strict order, i.e. the lower the layer the less secure, but also the more operations it supports. It is important that each lower layer supports all operations that the upper layer supports, such that a decryption never needs to be undone.

The client analyzes each query before executing it. It determines the necessary encryption layer in the onion encryption in the database. Then, before sending the query, the client performs the decryption of the column to that onion layer. No encryption from a lower to a higher encryption layer is ever performed. As such, the level (layer) of encryption in the database is dynamically adjusted to the queries processed.

In order to perform an equi-join operation data is decrypted to the deterministic layer L2, but different columns may still be encrypted using different keys. In this case proxy re-encryption (PRE) [START_REF] Blaze | Divertible protocols and atomic proxy cryptography[END_REF] can be performed. In PRE a proxy translates a ciphertext encrypted under one key into a ciphertext under another key without decrypting it first, i.e. the proxy does not learn the plaintext or any of the two keys. The proxy does, however, learn a relation between the two keys, such that the security against cryptanalysis is reduced to the secrecy of one key.

We use a proxy re-encryptable, deterministic encryption scheme. An example is the symmetric Pohlig-Hellman encryption [START_REF] Pohlig | An improved algorithm for computing logarithms over GF(p) and its cryptographic significance[END_REF].

Let p be the prime order of a group Z p . Let m be an element of Z p representing a message to encipher. Let ord(p) = p-1 be the order of the multiplicative group Z * p of invertible elements in Z p . We uniformly choose an element e of Z ord(p) , such that gcd(e, ord(p)) = 1. We encrypt m to the ciphertext c as c = m e mod p

We decrypt the ciphertext c as

m = c e -1 mod ord(p) mod p
The element e is the secret key. Let two database columns A and B have two different keys e A and e B , respectively, but both encrypted at the deterministic layer L2. Furthermore, assume we have chosen to re-encrypt column A to the key of columns B. We then compute the PRE key k as

k = e -1
A e B mod ord(p)

The database can now perform the proxy re-encryption operation. Each ciphertext c of column A is re-encrypted to a ciphertext c ′ using the PRE key k as

c ′ = c k = m eAk = m eAe -1 A eB mod ord(p) = m eB mod p
In [START_REF] Popa | CryptDB: Protecting confidentiality with encrypted query processing[END_REF] the authors suggest to use this encryption scheme, but on elliptic curves. Unfortunately, their encryption scheme is not decryptable, since they use g m instead of m. This may require additional storage on the database. Old-fashioned Pohlig-Hellman encryption over multi-precision integers is decryptable. The authors also provide a cryptanalysis of their scheme in [START_REF] Popa | Cryptographic treatment of CryptDB's adjustable join[END_REF] under an adjustable join attack. This extends to Pohlig-Hellman encryption.

Naive Approaches

Let there be a database with n columns A, B, C and so forth. Initially each column is deterministically encrypted under its own key. We then perform a number of queries on the database, possibly involving join operations. We write

Join(A, B) Join(B, C)
for first joining columns and A and B and then columns B and C. Joins with k ≥ 2 columns can be simulated by joining k -1 pairs. However, the order in which the pairs are chosen is not arbitrary. We will give more details on how to do this efficiently in section 4.8. In order to perform a join operation, at least one column needs to be re-encrypted. We write

Join(A, B): A ← B

if column A gets re-encrypted to the key of column B.

The order of the two columns in the join operation is determined by the query string. Therefore the database connector has to choose the right column to re-encrypt.

We consider the effect of a few simple, straight-forward strategies. This should highlight that such simple strategies -while plenty -do not result in the best performance. The first strategy is to always use the first column in the query string. Assume the following schedule

Join(A, B): A ← B Join(A, C): A ← C Join(A, B): A ← B Join(A, C): A ← C . . .

Algorithms

Data Structures

In our algorithms we store two types of objects: columns and keys. For the sake of exposition, we store these objects as database table rows, but it could as well be Java objects or C/C++ structures. Storing them in database tables enables to be shared between multiple clients of the encrypted database and ensures persistence between different runs of the application of one client.

In the table Keys we store -KeyId: An unique identifier for the key. It is the primary database key of the table. -Rank: A rank of the key.

In the table Columns we store -ColumnId: An unique identifier for the column. It may be or be generated from the name of the column TABLE.COLUMN which enables searching using the name. It is the primary key of the table.

-Cost: The cost of re-encrypting this column. For now we assume uniform cost of 1 for each column. We discuss non-uniform costs in 4.9. -KeyId: The identifier of the associated key. This is a foreign key of this table and the primary key of the Keys table.

Initialization

Algorithm We initialize each column with its own key and cost of 1. Each key is initialized with the cost of the associated column. This is performed as in Algorithm 1. When uploading the encrypted data into the database, the data of each column will be encrypted under its associated key. Subsequently we can perform queries with optional joins.

Key Retrieval Algorithm 2 Key Retrieval function GetKey(column)

return Select keyId From Columns Where columnId = column end function

When we perform a query we must encrypt parameters and decrypt return values. We therefore need to retrieve the corresponding key identifier for the accessed columns. Algorithm 2 shows that this can be performed using a simple query.

Column Selection

When performing a join between two columns A and B we need to select one for re-encryption. The function in Algorithm 3 returns the identifier of the column to be re-encrypted. It has already updated the data structure to reflect its new key -that of the other column. We call the column that does not get re-encrpyted the steady column. We make the choice simply by the rank of the key. The column with the key with the lower rank gets re-encrypted. Afterwards, we add the cost of the re-encrypted column to the rank of the steady column and subtract the same cost from the rank of the key of the re-encrypted column.

Algorithm 3 Column Selection

If the rank of the key of the re-encrypted column reaches 0, then we can delete the key entry, since it no longer encrypts any column.

Note that for any (infinite) schedule of joins the algorithm leads to a finite number of proxy re-encryptions only (i.e. it returns a value different from null only a finite number of times). This can be seen easily if we consider a variant of the algorithm where we omit the deletion of keys of rank 0 (lines 22 through 24). Then the sum of the absolute values of differences of the ranks over all pairs of keys is a non-negative integer which is bounded (by

( n 2 )
times the maximal possible rank) and which increases by at least 2 in each re-encryption step.

The algorithm is reminiscent of the Union-Find algorithm [START_REF] Galler | An improved equivalence algorithm[END_REF], but we do not join the entire group, just the selected column. This reduces the cost for one join operation, since we need to re-encrypt at most one column and not an entire group, but does not increase worst-case cost -due to the re-encryption of columns in shrinking groups -as we show in our analysis next.

Analysis

We analyse the worst-case performance of our re-encryption selection algorithms. Here (and also in the analysis of the enhanced algorithm in section 4.7) we obtain the maximal security simply by taking the maximal possible number of different keys given the required functionality, i.e. whenever two columns are not joined in any previous step of the schedule they remain encrypted under different keys.

Let there be n columns and let t(n) be the maximum number of re-encryptions that Algorithm 3 performs where the maximum is taken over all possible schedules of join operations. We now provide a proof that t(n) = O(n 3/2 ).

Theorem 1 Algorithm 3 needs at most 2n 3/2 re-encryptions for any schedule. This bound is optimal in the sense that the asymptotic behavior of t(n) is O(n 3/2 ).

Before we start with the proof of this theorem we recall some notation: A partition of n is a sequence λ = (λ 1 , . . . , λ k ) where The dominance order on partitions is defined by

λ 1 ≥ . . . ≥ λ k ≥ 1 are integers such that λ 1 + λ 2 + . . . + λ k = n.
λ µ : ⇐⇒ ∀i ≥ 1 : λ 1 + . . . + λ i ≥ µ 1 + . . . + µ i .
(Here λ i = 0 resp. µ i = 0 for i greater than the number of rows of λ resp. µ.) It is well known (see [START_REF] James | The representation theory of the symmetric groups[END_REF]) that λ µ iff λ can be obtained from µ by succesively moving single boxes from lower to higher rows. The set of all partitions of n together with the dominance order is a poset L n and (1, . . . , 1) resp. (n) is the unique minimal resp. maximal element of L n .

Partitions as well as the dominance order occur naturally in our algorithm: Let λ 1 ≥ . . . ≥ λ k ≥ 1 be the sizes of the groups at any time during the execution of the algorithm (ordered non-increasingly). Then clearly λ = (λ 1 , λ 2 , . . . , λ k ) is a partition of n.

This way for every given schedule of join operations the Algorithm 3 produces a series of partitions λ (1) , λ (2) , . . . of n. The first partition in the sequence is always (1, 1, . . . , 1) (n ones) and the schedule can be further extended as long as there is more than one group left i.e. until it reaches the maximal partition (n).

We observe how λ changes when a single step of the algorithm is applied. We remove one element (database column) from one group and add it to another group of at least the same size. In terms of the associated Young diagrams this amounts simply to moving one box up into a higher row. In other words, the series of partitions derived from a join schedule is an increasing (w.r.t. ) chain in the poset L n .

On the other hand for any series of partitions λ (1) , λ (2) , . . . of n such that λ (i+1) is obtained from λ (i) by moving-up one box we can easily derive a join schedule that produces exactly this series of tableau in the way described above. To this end we just annotate each box with a database column label at the begin. Thereafter, we interpret moving-up such a box (keeping its label) by executing a join of the corresponding database column with any other column in the target row. 1Therefore, finding the worst case number of steps of our algorithm is equivalent to finding the longest totally ordered chain in the lattice L n of partitions. Hence the theorem follows directly from Proposition 1 (a) The longest increasing sequence in the poset (L n , ) consists of at most 2n 3/2 elements. (b) The longest increasing sequence in the poset consists of at least 2 3 n 3/2 elements.

Proof. (a) Let k = [

√ n] and consider an increasing (w.r.t. ) series of Young diagrams of maximal length. We obtain this maximal length by counting the total number of move-up operations of boxes (and adding 1 for the initial diagram).

To do so we have a look at the path of each of the n boxes individually. The key observation is that in each step the box not only moves up, but also moves to the right at least one place. Therefore after at most k of its moves it has reached (the end of) a row in the Young diagram with length ≥ k + 1. Since there are only n < (k + 1) 2 boxes altogether this must be a row with index less than k + 1. Hence, the box we considered can from now on only have k -1 further moves which is a total of 2k -1.

This holds for every box and hence we obtain n(2k -1) + 1 ≤ 2n 3/2 as an upper bound on the length of the given sequence.

(b) We write n = 1 2 k(k +1)+r for suitable non-negative integers k and r ≤ k. Then we can construct a sequence of "triangular shaped" Young diagrams:

(1, . . . , 1) → (2, 1, . . . , 1) → (3, 2, 1, . . . , 1) → (4, 3, 2, 1, . . . , 1)

→ • • • • • • → (k, k -1, . . . , 2, 1, . . . , 1)
(In the last diagram there are 1 + r ones at the end.) Each step in this sequence further decomposes into a certain number of move-up operations for single boxes. Now let's count these single move-up operations . To go from (j, j -1, . . . , 2, 1, . . . , 1) to (j + 1, j, . . . , 2, 1, . . . , 1) we need to move one box j times, the next box j -1 times and so on. This sums up to 1 2 j(j + 1). Altogether we have

∑ k j=1 j(j+1) 2 = k(k+1)(2k+7)
12 single moves. Next we move the "remaining" r ones to the first row. This amounts to rk single moves.

We continue from (k + r, k -1, . . . , 2, 1) to (n) in a symmetric (but reverse) way. Just interchange the role of rows and columns in the diagrams. This adds another k(k+1)(2k+7) 12 and hence we get the lower bound k(k+1)(2k+7)

6

+ kr + 1 for the length of the maximal chain. From this we get the claim by a direct calculation.

⊓ ⊔ Algorithm 3 is very well suited for practical purposes. We give some experimental data of its behavior in section 5.

Enhanced version of the Algorithms

We show how to improve the worst case behavior of the algorithm. Note that choosing a key that is neither of the two columns but from a third column is in general not a viable option. While this may decrease the overall cost, it may also decrease security. Consider an example where columns A and B are joined under C's key.

Join(E, C): E ← C Join(D, C): D ← C Join(A, B): A ← C, B ← C
Clearly, if this schedule continues with

Join(B, C) Join(A, C)
then the overall cost is optimal, but the operation is speculative in terms of security. If the schedule does not continue, the adversary is given more information. All columns are encrypted under the same key. He now can use all of them for cryptanalysis.

In the alternative where we replace the third join operation with

Join(A, B): A ← B

there are two remaining, disjunct keys: one for C, D, E and one for A, B.

Clearly, this complicates cryptanalysis. Choosing one of the two keys of the joined columns always yields the minimal amount of ciphertexts for cryptanalysis, since at least one re-encryption is necessary in order to perform the join.

As a consequence we only consider re-encryption selection algorithms as admissible that guarantee that two columns have different keys unless there is a chain of (previous) joins which links these two columns. Now for our enhanced algorithm we group columns not by the fact that they share a common key but by the fact that there is a chain of previous join operations that links one column to another. To distinguish this from the groups (cf. section 4.4) we considered before we will call a cluster of columns (at any given time) the set of columns that is connected w.r.t. previous joins. Note that clusters are unions of groups. Let's call a cluster key the (common) key of the largest group in a cluster.

We modify our data structures and algorithms to be able to account for cluster keys by introducing the additional column The main change in the column selection algorithm (cf. Algorithm 4) is that now it may return two columns which shall be re-encrypted. By keeping track of the cluster a column belongs to we can without degrading the security reencrypt both columns of a join to the cluster key of higher rank (which they will eventually have anyway). This means there need not be a steady column any more.

Analysis of the Enhanced Algorithm

Consider the function T defined by T (1) = 0 and

T (n) = T (⌊ n 2 ⌋) + T (⌈ n 2 ⌉) + ⌊ n 2 ⌋ for n = 2, 3, . . . (1)
or, more explicitly,

T (2i) = 2T (i) + i (2) T (2i + 1) = T (i) + T (i + 1) + i . ( 3
)
Remark. Using these recursions for T one can also easily prove that

T (n) = ∑ i<n Q(i) where Q(i)
is the sum of the digits of i in its binary expansion. We omit the details here because we will not need this representation in the sequel. Lemma 1. For all n ≥ 1 we have T (n) ≤ n 2 log 2 n where equality holds iff n is a power of 2.

Proof. From the equations ( 2) and (3) we directly derive the claim by induction because 2(

1 2 i log 2 i) + i = i ( (log 2 i) + 1 ) = 1 2 (2i) log 2 (2i
) and (using Jensen's inequality applied to the concave function x → x log 2 x)

(i log 2 i+(i+1) log 2 (i+1)) 2 ≤ i+(i+1) 2 log 2 i+(i+1) 2 = 2i+1 2 (log 2 (2i + 1) -1) hence 1 2 i log 2 i + 1 2 (i + 1) log 2 (i + 1) + i < 1 2 (2i + 1) log 2 (2i + 1)
. Moreover, it is clear that equality in T (n) ≤ n 2 log 2 n holds iff we never have to the recursion (3), i.e. iff n is a power of 2.

⊓ ⊔

The significance of the function T arises from Hence it has the optimal worst-case behavior.

The proof of this theorem uses another lemma:

Lemma 2. For all n ≥ 2 we have

T (n) = max 1≤i≤n/2 ( T (i) + T (n -i) + i ) . ( 4
)
Proof (Theorem). Let T (n) be the number of re-encryption for the worst schedule on n columns. To show that in fact T = T we look at the last step where there are two clusters of sizes i and n -i respectively (for some i ≤ n 2 ). Then

T (n) = max 1≤i≤n/2 ( T (i) + T (n -i) + i ) (for n ≥ 2).
because the columns in the cluster of size n -i contribute with T (n -i) reencryptions no matter if these are executed before or after the two clusters have been joined. Columns of the cluster of size i contribute with at most T (i) reencryptions before the two clusters are joined and with i re-encryptions after the two clusters are joined. Comparing with Lemma 2 shows that T satisfies the same recursion as T .

⊓ ⊔

Proof (Lemma). The proof is again by induction: For

1 ≤ i < ⌊ n 2 ⌋
we calculate

T (i) + T (n -i) + i = T (⌊ i 2 ⌋) + T (⌈ i 2 ⌉) + ⌊ i 2 ⌋ + T (⌊ n-i 2 ⌋) + T (⌈ n-i 2 ⌉) + ⌊ n-i 2 ⌋ + i = T (⌊ i 2 ⌋) + T (⌈ n-i 2 ⌉) + ⌊ i 2 ⌋ + T (⌈ i 2 ⌉) + T (⌊ n-i 2 ⌋) + ⌊ n+i 2 ⌋ = T (⌊ i 2 ⌋) + T (⌈ n-i 2 ⌉) + ⌊ i 2 ⌋ + T (⌊ i+1 2 ⌋) + T (⌈ n-i-1 2 ⌉) + ⌊ n+i 2 ⌋ = T (⌊ i 2 ⌋) + T (⌈ n-i 2 ⌉) + ⌊ i 2 ⌋ + T (⌊ i+1 2 ⌋) + T (⌈ n-i-1 2 ⌉) + ⌊ i+1 2 ⌋ - ⌊ i+1 2 ⌋ + ⌊ n+i 2 ⌋ ≤ T (⌊ i 2 ⌋ + ⌈ n-i 2 ⌉) + T (⌊ i+1 2 ⌋ + ⌈ n-i-1 2 ⌉) - ⌊ i+1 2 ⌋ + ⌊ n+i 2 ⌋
Note that in the last step we use the induction hypothesis (and furthermore use that

⌊ i+1 2 ⌋ < ⌈ n-i-1 2 ⌉ because i < ⌊ n 2 ⌋ ). Now ⌊ i 2 ⌋ + ⌈ n-i 2 ⌉ = ⌊ n 2 ⌋
unless n is odd and i is even (in which case the value is

⌈ n 2 ⌉
), and likewise

⌊ i+1 2 ⌋ + ⌈ n-i-1 2 ⌉ = ⌊ n 2 ⌋
unless n is odd and i + 1 is even (where again the value is

⌈ n 2 ⌉
). In any case one of the expressions

⌊ i 2 ⌋ + ⌈ n-i 2 ⌉ and ⌊ i+1 2 ⌋ + ⌈ n-i-1 2 ⌉ equals ⌊ n 2 ⌋
and the other equals ⌈ n 2 ⌉ . Hence finally

T (i) + T (n -i) + i ≤ T (⌊ n 2 ⌋) + T (⌈ n 2 ⌉) + ⌊ n 2 ⌋ because - ⌊ i+1 2 ⌋ + ⌊ n+i 2 ⌋ ≤ ⌊ n 2 ⌋ . ⊓ ⊔

Multiple Simultaneous Joins

In queries like SELECT a.b, c.d, e.f FROM a, c, e WHERE a.x = c.z AND b.y = c.z we need to re-encrypt multiple columns. As already stated we simulate this by joining pairs of columns one after the other. Given a set of k columns that need to be compared for the join, we chose a column corresponding to a key with the highest occuring rank. Then we form pairs consisting of this column and all the other columns successively. Since both our algorithms encrypt "towards the higher rank" this ensures that all columns have the same key as the chosen column after k -1 executions of the algorithm. The number of proxy re-encryptions thereby is bounded by k -1 for the Algorithm 3 and by k for the Algorithm 4 (since each of the columns is re-encrypted at most once).

Non-Uniform Costs

So far we have assumed uniform costs of 1 for each column, but some columns may be easier to re-encrypt than others. Particularly, the re-encryption cost is linear in the number of elements per column. This means, that it is easier to re-encrypt two columns of size 1 and 2, respectively, than one column of size 4. We now consider element-wise re-encryption costs by incorporating nonuniform column costs, e.g. the size of the column, in our algorithms. Simply, initialize the columns with their respective costs in Algorithm 1. This may significantly reduce the overall costs. Following the example above, consider columns A, B and C of respective sizes 2, 1 and 4 and the join schedule

Join(A, B) Join(C, A)
Uniform costs may suggest the following re-encryptions: A ← B, C ← A. This results in 6 element re-encryptions. The worst possible performance for any set of re-encryptions. Instead non-uniform costs using column sizes dictate these re-encryptions: B ← A, A ← C. The result are 3 element re-encryptions. Furthermore, the maximum number of element re-encryptions using either of our algorithms in this example is 4. This is also the minimum worst-case cost under any schedule of join operations.

It is therefore important to note that the analysis of minimum worst-case cost of re-encryption of Section 4 in the general case remains intact. We always achieve the best worst-case cost assuming any future schedule of join operations. To see this, view a column with non-uniform cost c as a group of c columns with uniform cost 1 that always operate successively. Let N be the sum of the costs of all columns, then our algorithm incurs costs of at most O(N log N ).

Nevertheless, in some cases of non-uniform costs we may perform too many re-encryptions for a specific schedule resulting in sub-optimal costs, since the future schedule is unknown. Consider columns A, B, C and D of sizes 1, 5, 2 and 3 and the following join schedule In the third join our algorithm dictates C ← A leading to 5 element reencryptions. This clearly leads to the minimal costs of also 5 for a future Join(B, C) but in case there is no future join, costs are not optimal. It would be more efficient to re-encrypt as A ← C resulting in a cost of 4 element re-encryptions. Yet, choosing to re-encrypt as A ← C will increase the worst-case cost under many future join schedules. We therefore choose to optimize the worst-case cost where our bound is tight.

The number of elements in a column may vary, because rows may be inserted or deleted. This further complicates the analysis and possible algorithms also have to account for these future operations. We leave this as future work and currently assume fixed non-uniform costs. We performed a number of experiments in order to measure the difference between the best re-encryption cost and our Algorithm 3. We chose n = 8 columns and a join schedule of length m = 16. Note that we need to find the optimum schedule in 2 m = 65536 options.

Experiments

We chose the schedule uniformly random among all possible pairs of different columns. Pairs could occur repeatedly. We chose the cost for each column uniformly random between 1 and 100.

We performed 1000 experiments. In each we recorded the optimum cost and the cost of our Algorithm 3. In 41% of the experiments our algorithm delivered the optimum schedule. The mean difference to the optimum was 26, i.e. roughly half an average column cost. The maximum difference was 193 and the median difference was 9, such that few large sub-optimal cases account for the majority of the difference.

In Figure 1 we depict our results. We have sorted all experimental results in increasing optimal cost (black line). The gray line depicts the corresponding cost of our algorithm.

Conclusion

In this paper we have considered the problem of selecting a column for reencryption in a deterministically, adjustably encrypted database. To the best of our knowledge this is the first paper considering this problem. We have provided an algorithm that achieves the best possible worst-case bound and a simpler algorithm that performs very well in experimental settings.

  The partition λ can graphically be represented by a Young diagram which is composed of k rows containing λ 1 , . . . , λ k boxes (where the top row has length λ 1 ). By abuse of notation we use λ to denote both the partition and the associated Young diagram as in λ = (5, 4, 1) =

  Join(A, B): A ← B Join(C, D): C ← D Join(A, C)

Fig. 1 .

 1 Fig. 1. Cost difference between optimum and Algorithm 3

1

  Initialization

	function Init
	for all column do
	cost ← 1
	Insert keyId, cost Into Keys
	Insert columnId, cost, keyId Into Columns
	end for
	end function

  Select rank From Keys Where keyId = keyA rankB ← Select rank From Keys Where keyId = keyB

		function Join(columnA, columnB)
		keyA ← GetKey(columnA)
		keyB ← GetKey(columnB)
		if keyA = keyB then
	5:	return null
		end if
		rankA ← if rankA > rankB then
	10:	lower ← columnB
		(lowerKey, lowerRk) ← (keyB, rankB)
		(upperKey, upperRk) ← (keyA, rankA)
		else
		lower ← columnA
	15:
		end if
	25:	return lower
		end function

(lowerKey, lowerRk) ← (keyA, rankA) (upperKey, upperRk) ← (keyB, rankB) end if lowerCost ← Select cost From Columns Where columnId = lower Update Keys Set rank = lowerRk -lowerCost Where keyId = lowerKey 20: Update Keys Set rank = upperRk + lowerCost Where keyId = upperKey Update Columns Set keyId = upperKey Where columnId = lower if lowerRank -lowerCost = 0 then Delete From Keys Where keyId = lowerKey

-

  ClusterKeyId: The identifier of key associated to the cluster this column belongs to. in the table Columns. During initialization the cluster key of a column gets the same value as the key: Hence the insert statement of Algorithm 1 now reads Insert columnId, cost, keyId, keyId Into Columns Yet another algorithm (similar to Algorithm 2) defines a function GetClus-terKey to extract the ClusterKeyId for a column.

	Algorithm 4 Column Selection (enhanced)
		function Join2(columnA, columnB)
		if GetKey(columnA) = GetKey(columnB) then
		return null
		end if
	5:	keyA ← GetClusterKey(columnA)
		keyB ← GetClusterKey(columnB)
		lowerKey
	25:	if lowerRk -lowerCost = 0 then
		Delete From Keys Where keyId = lowerKey
		end if
		if GetKey(upper) = GetClusterKey(upper) then
		return lower
	30:	end if
		Update Columns Set keyId = upperKey Where columnId = upper
		return (lower, upper)
		end function

rankA ← Select rank From Keys Where keyId = keyA rankB ← Select rank From Keys Where keyId = keyB if rankA > rankB then 10: lower ← columnB (lowerKey, lowerRk) ← (keyB, rankB) upper ← columnA (upperKey, upperRk) ← (keyA, rankA) else 15: lower ← columnA (lowerKey, lowerRk) ← (keyA, rankA) upper ← columnB (upperKey, upperRk) ← (keyB, rankB) end if 20: lowerCost ← Select Sum(cost) From Columns Where clusterKeyId = lowerKey Update Keys Set rank = lowerRk -lowerCost Where keyId = lowerKey Update Keys Set rank = upperRk + lowerCost Where keyId = upperKey Update Columns Set keyId = upperKey Where columnId = lower Update Columns Set clusterKeyId = upperKey Where clusterKeyId =

Theorem 2

 2 For any proxy re-encryption algorithm which is admissible in the sense of section 4.6 there is a schedule on n columns that needs at least T (n) re-encryptions, i.e. its asymptotic behavior is O(n log n). Algorithm 4 applied to n columns needs at most T (n) re-encryptions.

	Theorem 3
	Proof. We divide the columns into two sets of sizes of them we have a worst case schedule with at least T ( ⌊ n 2 ⌋ ⌊ n and 2 ⌋ ) resp. T ( ⌈ n 2 ⌉ . For either ⌈ n 2 ⌉ ) re-
	encryptions. After concatenating these two schedules we get a schedule which
	still ends in two clusters with different keys 2 and which can be extendend by another ⌊ n 2 ⌋ joins. Hence we end up with a schedule that by equation (1) requires
	T (n) re-encryptions.	⊓ ⊔

, i.e. O(n 2 ) re-encryptions. Clearly, this is sub-optimal, since the same schedule can be completed with n -1 PREs in the following wayJoin(A, B): A ← B Join(B, C): C ← B Join(A, B) Join(C, D): D ← B Join(B, C) Join(A, B). . .We follow this idea in the formal definition of our algorithms in the next section.

Caution: Be aware that although this reverse construction may suggest so, in the procedure of going from join schedules to Young diagrams a box is not associated with a fixed column and a row is not associated with a fixed key!

This is where we use admissibility!

Clearly, this may lead to infinitely many re-encryptions and is therefore inadvisable. There is a maximum number of re-encryptions for any schedule and ideally this should be achieved.

Next, consider a total order of columns, e.g. lexicographically. We always re-encrypt the lower to the upper. Now, assume the following schedule

This leads to n(n-1)


Yang Wang
email: yangwang@nmt.edu

Jun Zheng
email: zheng@nmt.edu

Chen Sun

Srinivas Mukkamala
email: srinivas@cs.nmt.edu

Quantitative Security Risk Assessment of Android Permissions and Applications

Keywords: Android App, Android Permission, Malware, Risk Assessment, DroidRisk

The booming of the Android platform in recent years has attracted the attention of malware developers. However, the permissionsbased model used in Android system to prevent the spread of malware, has shown to be ineffective. In this paper, we propose DroidRisk, a framework for quantitative security risk assessment of both Android permissions and applications (apps) based on permission request patterns from benign apps and malware, which aims to improve the efficiency of Android permission system. Two data sets with 27,274 benign apps from Google Play and 1,260 Android malware samples were used to evaluate the effectiveness of DroidRisk. The results demonstrate that DroidRisk can generate more reliable risk signal for warning the potential malicious activities compared with existing methods. We show that DroidRisk can also be used to alleviate the overprivilege problem and improve the user attention to the risks of Android permissions and apps.

Introduction

The use of touchscreen based mobile devices like smartphones has seen unprecedented growth in recent years due to their portability and real-time information access. According to a recent study from research firm Ovum [START_REF]Smartphone sales to top 1.7 billion by 2017, dominate mobile phone market[END_REF], smartphones will dominate the mobile phone market with a compound annual growth rate of 24.9% from 2011 to 2017 and 1.7 billion devices are estimated to be shipped by 2017. The dominance of smartphones is largely attributed to the Google Android mobile OS which took 68% of the global market in the second quarter of 2012 [START_REF]Android races past apple in smartphone market share[END_REF]. This is mainly due to it being open source and the large collection of mobile applications (apps) in the unrestricted official and third-party Android app markets. In September 2012, the Google's official app store, Google Play (previously known as Android Market [START_REF]Google play[END_REF]), hit total 25 billion app downloads with more than 675,000 apps [START_REF]Google play hits 25 billion downloads[END_REF].

However, the popularity of Android platform has also attracted the attention of malware developers. It was reported that more than 260,000 Android devices were affected by a mobile virus called DroidDream in the official Android Market within 48 hours in 2011 [START_REF]Drioddream malware has now claimed 260,000 devices[END_REF]. Felt et al. did a survey of mobile malware on three different mobile platform including Android [START_REF] Felt | The effectiveness of application permissions[END_REF]. They found that the most common malicious activities are collecting user information and sending premium-rate SMS message. Zhou et al. collected 204,040 apps from five different Android markets between May to June in 2011 [START_REF] Zhou | Hey, you, get off my market: detecting malicious apps in official and alternative android markets[END_REF]. 211 malware were found in the collected apps, where 32 from the official Android Market and 179 from the third-party markets.

The security mechanism used in Android platform to prevent the spread of malware is the permission-based model, which protects the access to sensitive privacy data (contact list, emails, phone call logs, location etc.) and system resources (GPS, camera, WiFi etc.). An Android app needs the user's approval of the requested permissions to be installed in the user's device. Felt et al. conducted two usability studies on the effectiveness of Android permission system [START_REF] Felt | Android permissions: user attention, comprehension, and behavior[END_REF]: one Internet survey of 308 Android users and a laboratory survey of 25 Android users. The studies showed that only 17% of participants paid attention to permissions during app installation, which indicates that the current Android permission system fails to protect most users from malware.

Several recommendations were made in [START_REF] Felt | Android permissions: user attention, comprehension, and behavior[END_REF] to improve the low attention and comprehension rate of Android permission system such as re-organizing and re-naming categories, description of permissions focusing on risk instead of resources, smaller permission list etc.. However, based on our own experiences of installing Android apps, the main reason causing the ineffectiveness problem is the text-based permission warning interface for app installation, which can be easily ignored by the users [START_REF] Sarma | Android permissions: a perspective combining risks and benefits[END_REF]. Our solution for this problem is to have a quantitative assessment of the risk levels of Android permissions and apps. With the quantitative risk information, users can easily understand the risk of an app to be malicious and pay more attention to those permissions with high risk levels.

This paper has made the following contributions:

-We propose DroidRisk, a framework for quantitative security risk assessment of Android permissions and apps based on permission request patterns, which follows the U.S. National Institute of Standards and Technology (NIST) guide for IT security risk management [START_REF]Risk management guide for information technology systems[END_REF]. To the best of our knowledge, this is the first attempt to quantitatively assess the risk levels of both Android permissions and apps. -We evaluate the effectiveness of DroidRisk with two datasets. The benign app dataset has 27,274 popular apps collected from Google Play in July 2012. The malware dataset consists of 1,260 Android malware samples from the Android Malware Genome Project [START_REF] Zhou | Dissecting android malware: characterization and evolution[END_REF]. We show that reliable risk signal can be generated with the quantitative risk levels of apps for warning the potential malicious activities.

-We show that DroidRisk can be applied to alleviate the overprivilege problem. -We have implemented two applications of DroidRisk to improve the user attention to the risks of Android permissions and apps: a modified App web page in Android market with the quantitative risk information of the app and its requested permissions, and an Android app to evaluate the risk levels of apps installed in local device.

Related Work

Due to its importance for Android security and user privacy, the permission system has attracted lots of research interests. There are several studies on how the permissions are used by Android apps. In [START_REF] Barrera | A methodology for empirical analysis of permission-based security models and its application to android[END_REF], Barrera et al. did an empirical analysis of the permission-based security models by analyzing 1,100 most popular Android apps using the Self-Organizing Map (SOM) algorithm. They found that among the defined permissions only a small portion of them are actively used by developers. Another finding of their study is that the requested permissions are not strongly correlated with application categories. Felt et al. did a survey of 100 paid and 856 free apps from Android Market in [START_REF] Felt | The effectiveness of application permissions[END_REF]. It was observed that 93% of free and 82% of paid apps request at least one dangerous permission. They also built a tool called Stowaway that can detect whether a compiled Android app requests more permissions than necessary, i.e. overprivileged [START_REF] Felt | Android permissions demystified[END_REF]. Among the apps they investigated, about one-third were actually overprivileged. In [START_REF] Wei | Permission evolution in the android ecosystem[END_REF], Wei et al. studied the permission evolution in the Android ecosystem. One of their key observations is that the set of dangerous-level permissions always outnumbers other permission types in all versions of the Android platform and it is still growing. Frank et al. studied the permission request patterns of Android apps using pattern mining technique [START_REF] Frank | Mining permission request patterns from android and facebook applications[END_REF]. They tried to relate the permission request pattern with the app's reputation which can be served as an indicator of app quality. Although all these works revealed something about the permission request patterns of Android apps, they didn't attempt to identify potential malware.

Recently, the app's permission request pattern has been used to generate risk signal for warning potential malicious activities. Enck et al. proposed a light weight application certification service called Kirin that uses a rule-based strategy to identify suspicious apps based on their requested permissions [START_REF] Enck | On lightweight mobile phone application certification[END_REF]. However, because the rules were defined manually, they can't adapt to the changing characteristics of current permissions and apps. For example, the 9th rule of Kirin is no longer valid because the permission SET PREFERRED APPLICATION has been deprecated since Android API level 7. In [START_REF] Zhou | Hey, you, get off my market: detecting malicious apps in official and alternative android markets[END_REF], Zhou et al. proposed a system called DroidRanger to detect malicious apps in official and alternative Android markets. The first component in DroidRanger is permission-based filtering which uses some dangerous permissions such as RECEIVE SMS and SEND SMS to find potential malicious apps. It was shown that only 0.66% of apps needed further analysis after the permission-based filtering step. Chia et al. studied permissions systems of Facebook apps, Chrome extensions and Android apps to find the reliable signals to identify potential harmful and inappropriate apps [START_REF] Chia | Is this app safe?: a large scale study on application permissions and risk signals[END_REF]. They investigated several signals including the adjusted community rating, the availability of the developer's website and the number of apps published by the developer. However, none of those signals was found to be reliable. In [START_REF] Sarma | Android permissions: a perspective combining risks and benefits[END_REF], Sarma et al. proposed a set of risk signals by examining the permission request patterns from apps in Android Market and the collected malicious apps. The proposed risk signals include rare critical permissions (RCP), rare pairs of critical permissions (RPCP), combination of RCP and RPCP, and category-based RCP (CRCP). The RCP signal is triggered if at least one of the critical permissions is requested by less than certain percentage of the Android Market apps. The RPCP signal is triggered if for a pair of critical permissions, any individual permission occurs more frequent than they occur as a pair. The CRCP signal is the combination of category information with RCP. Though RCP has shown superior performance compared with Kirin in terms of warning and detection rates [START_REF] Sarma | Android permissions: a perspective combining risks and benefits[END_REF], the users do not have any idea about the risk levels of requested permissions by an app and the app itself as there is no quantitative assessment of the risk levels.

Application Dataset

In this section, we describe the benign app and malware datasets collected for our study. We also provide the statistics of requested permissions of these two datasets.

Data Collection

Benign App Dataset Among the large number of Android markets available worldwide, Google Play is the largest and most reliable one. An antivirus system, called Google Bouncer, is deployed to detect the malicious apps uploaded by developers [START_REF]Android and security[END_REF]. Any malicious app found by Google Bouncer, that may be harmful to users or tries to steal privacy information, will be removed from Google Play. Thus, it is reasonable to assume that the apps from Google Play perform no malicious activities and can be used to construct the benign app dataset.

To collect the information of apps from Google Play, we developed a crawler to automatically extract the name, category and the requested permissions of each app from its corresponding web page. In total we collected the information of 27, 274 popular apps from Google Play in the middle of July, 2012. The collected apps belong to 26 subcategories under "Applications" category and 8 subcategories under "Games" category.

Malware Dataset

The Android malware dataset used in our study is from the Andriod Malware Genome Project [START_REF] Zhou | Dissecting android malware: characterization and evolution[END_REF]. This dataset consists of 1, 260 Android malware samples in 49 families from different markets which has a much larger size compared with the malware dataset of 121 samples used in [START_REF] Sarma | Android permissions: a perspective combining risks and benefits[END_REF]. 86% of the samples are repackaged versions of normal apps. 36.7% of them leverage root-level exploits. More than 90% try to remote control the device. 45.3% and 51.1% of them stealthily send short messages or make calls and collect privacy user information, respectively. Unfortunately, there is no category information for this malware dataset.

Statistics of Requested Permissions

Many malware request more permissions than the need of their claimed functions to perform malicious activities. For example, a game-like malware may request the permission to send short messages, which could result in a financial loss to the user. In this section, we provide the statistics of permissions requested by benign apps and malware, which inspire our work of DroidRisk.

Frequently requested permissions Figure 1 shows the top 20 requested permissions in the benign app and malware datasets. INTERNET is the most frequently used permission by both the benign apps and malware. There are many reasons to request permission for internet access: some of the apps need to log in; some are designed to use internet like browsers and email clients; some need to load advertisement etc. As a result, Internet-related permissions, such as ACCESS NETWORK STATE and ACCESS WIFI STATE, become very popular. Another set of widely used permissions are location related ones such as ACCESS FINE LOCATION and ACCESS COARSE LOCATION for location based services. The most significant differences between benign apps and malware observed from Figure 1 are: malware are more favor of changing the settings and use money-related services such as short message service (SMS). Changing settings, especially changing the network settings, generally is the first step before a malware performs any malicious activity. Sometimes malware even try to kill background processes, which could help them avoid being detected by anti-virus apps. It can be seen that SMS is a popular service among malware as four SMSrealted permissions are much more popular in malware than benign apps. In [START_REF] Zhou | Dissecting android malware: characterization and evolution[END_REF], Zhou and Jiang introduced a family of malware targeting on the financial charging. This kind of malware may stealthily edit and send out SMS to waste the user's money. They may subscribe premium-rate services without the user's consent for profit. 2(a) and 2(b) show the percentages of malware and benign apps requesting certain number of permissions, respectively. As can be seen, malware are likely to request more permissions than benign apps. It is shown that 58.8% and 92.7% of the benign apps request no more than 4 and 11 permissions respectively, while the numbers for malware are 7.5% and 49.3%. Figures 2(c) and 2(d) show the percentages of malware and benign apps requesting certain number of dangerous permissions, respectively. It can be easily seen that malware also request more dangerous permission than benign apps. More than half of the benign apps request 2 or less dangerous permissions and 91.8% of them have no more than 7 dangerous permissions. For

Number of requested permissions Figures

Quantitative Security Risk Assessment

Quantitative methods have been used to assess the financial risk for a long time [START_REF] Alexander | Market risk analysis: quantitative methods in finance[END_REF] but they are still relatively new for security risk assessment. To guide the risk management for IT systems, NIST published a set of IT security risk management best practices in 2002 [START_REF]Risk management guide for information technology systems[END_REF]. According to the NIST guide, risk assessment is the first step of IT risk management. To quantitatively assess the risk level of an system, it needs to find the risk of each potential adverse event for the system, which is defined as [START_REF]Risk management guide for information technology systems[END_REF][START_REF] Joh | Defining and assessing quantitative security risk measures using vulnerability lifecycle and cvss metrics[END_REF]:

R(E i ) = L(E i ) × I(E i ) (1)
where E i is the ith potential adverse event, R(E i ) is the risk of E i , L(E i ) and I(E i ) are the likelihood and the impact of E i , respectively. The likelihood represents the probability that a weakness is exploited by the attacker, while the impact refers to the magnitude of harm caused by this weakness being exploited [START_REF] Joh | Defining and assessing quantitative security risk measures using vulnerability lifecycle and cvss metrics[END_REF]. Assume the adverse events are independent, the system risk R sys can be obtained by summing the risk values of individual adverse events as shown in Equation ( 2):

R sys = i R(E i ) = i L(E i ) × I(E i ) (2)
where i = 1, 2, ..., n and n is the total number of potential adverse events.

DroidRisk -Quantitative Security Risk Assessment of Android Permissions and Apps

The DroidRisk framework for quantitative risk assessment of Android permissions and apps follows the NIST guide. We consider an Android app A as the system and each permission p i requested by A as the individual adverse event.

By assuming that the permissions requested by A are independent, the risk level of the app A, R A , can be defined as:

R A = i R(p i ) = i L(p i ) × I(p i ) (3)
where R(p i ) is the risk level of permission p i , L(p i ) and I(p i ) are the likelihood and the impact of permission p i respectively, i = 1, 2, ..., n and n is the total number of requested permissions by A.

The key problem to be solved in the DroidRisk framework is to calculate the likelihood L(p i ) and the impact I(p i ) for a requested permission p i . We define the likelihood L(p i ) as the probability that the app A is malware if p i is requested by A, i.e. P (A is malware | p i ). This posteriori conditional probability can be calculated using Bayes' rule as show in Equation (4):

P (A is malware | p i ) = P (p i | A is malware) × P (A is malware) P (p i ) (4)
where P (p i | A is malware) is the priori probability that a malware requests permission p i , P (A is malware) is the priori probability that an app is malware for all collected apps, and P (p i ) is the priori probability that any collected app, benign or malicious, requests permission p i .

For estimating impact levels of permissions, we consider two classes of permissions, normal and dangerous 1 . Although it is hard to evaluate the exact level of harm caused by a permission if it is requested by a malware, it is certain that dangerous permissions are more harmful than normal permissions. Thus, we set the impact level of normal permissions, I np as 1 while give dangerous permissions a higher impact level. In Section 5.2, we used an empirical method to determine the impact level of dangerous permissions, I dp .

Results

In this section, we first present the likelihood values calculated for Android permissions based on two datasets we collected. We then show how to determine the impact level for dangerous permissions with an empirical method followed by the presenting of risk levels of Android permissions and apps from the two datasets. Finally we demonstrate that DroidRisk can be used to assess the risks of apps in third-party markets.

Likelihood of Android Permissions

With the collected benign app dataset and malware dataset, we can calculate the likelihood of each Android permission using Equation (4). Figure 3 shows the top 20 permissions with highest likelihood values. The blue bar represents the likelihood of a normal permission while the red bar is for the likelihood of a dangerous permission.

There are 14 dangerous permissions on the list. WRITE APN SETTINGS has the highest likelihood among all permissions, which can change the network setting, thus to intercept and inspect the network traffic without the user's awareness. There are 5 SMS and MMS related dangerous permissions on the list, which means that SMS and MMS services are the major target of malware developers. Unlike other systems which don't pay attention to normal class permissions, we have 6 of them on the list. These permissions may be used by malware to facilitate some malicious activities. For example, INSTALL PACKAGES and DELETE PACKAGES are used by several malware families such as JSMSHider and GoldDream to perform update attack and KILL BACKGROUND PROCESSES is used by an Android Trojan named AnserverBot to avoid being detected by certain anti-virus apps [START_REF] Zhou | Dissecting android malware: characterization and evolution[END_REF] 2 .

1 Android characterizes the potential risk of the permissions using 4 protection levelsnormal, dangerous, signature and signatureOrSystem. Since signature or signature-OrSystem permissions can't be granted to third party apps, we category them into normal class. The protection level for a given permission in this study is obtained from Android API level 9. 2 KILL BACKGROUND PROCESSES has been used to replace the old name RESTART PACKAGES for permission -'kill background processes' since the release of Android API level 8.

Impact Level of Dangerous Permissions

Based on the discussion in Section 4.2, the impact level of dangerous permissions, I dp should be higher than the impact level of normal permissions, I np . Since there is no way to obtain the actual level of harm caused by normal permissions or dangerous permissions, we solved the problem with an empirical method using ROC (Receiver Operating Characteristic) curve. ROC curve is an efficient tool to evaluate the binary classification performance and select the optimal threshold setting [START_REF] Fawcett | An introduction to roc analysis[END_REF]. In our case, once I dp is determined, we can obtain the risk level of each Android permission, and then compute the risk levels of benign apps and malware according to their requested permissions. As one of our design goals is to classify benign apps and malware with a single threshold of risk level, ROC curve is the appropriate choice to find the value of I dp which gives the best classification performance. ROC curve is plotted with the true positive rate (TPR) versus the false positive rate (FPR) under various threshold settings. Figure 4 shows the ROC curve generated for I dp = 2. In Figure 4, the ideal classification performance is obtained at the upper left corner, which means no classification error. The closer the ROC curve to the upper left corner, the better the classification performance. Therefore, a popular metric used to measure the classification performance is the area under curve (AU C) [START_REF] Bradley | The use of the area under the roc curve in the evaluation of machine learning algorithms[END_REF], which is the area between the ROC curve and the x-axis. Usually a AU C greater than 0.9 is considered as excellent classification performance.The value of I dp is determined as 1.5 which gives the highest AU C value (0.9313).

Risk Levels of Android Permissions and Apps

Once the impact value of dangerous permissions is obtained, we are able to compute the risk levels of all Android permissions. Figure 5 shows the top 20 permissions with highest risk levels. Compared with the top 20 list for likelihood, there is no new permission on the list but the rankings of most dangerous permissions are promoted because of higher impact level. WRITE APN SETTINGS is still on the top of the list with highest risk level among all permissions. We also compute the risk levels for all benign apps and malware in our datasets by simply summing the risk levels of requested permissions as shown in Equation (3). Figure 6 shows the histograms of the risk levels of benign apps and malware. It can be easily observed that majority of benign apps have risk levels less than 2, while malware typically have higher risk levels.

As seen in Figure 6(b), there are few benign apps with very high risk levels. We did an investigation on top 20 benign apps with highest risk levels which are shown in Figure 7. The top 6 apps on this list are solely used for in-store demonstration of certain mobile devices. Some of them are warned by the vendors not for public use. The possible reason is that such apps may need lots of permissions to demonstrate different features of the device. It's not surprising to see 6 security apps on this list since they usually require lots of permissions to monitor the whole system and may block, intercept or change the behaviors of the system or other apps. Therefore, it is highly recommended that users should carefully choose the security apps for their devices since there are malware pretending to be anti-virus apps [START_REF]Android enesoluty -fake antivirus, spyware[END_REF]. The rest of the apps on this list are communication tools used for SMS, calls, email exchange etc. Since SMS, calls and other communications may leak privacy information or result in unexpected financial charge, users need to pay special attention to those apps.

Third Party Android Market

Besides Google Play, there are lots of third party android markets available worldwide, which are considered as the major source of malware [START_REF] Zhou | Hey, you, get off my market: detecting malicious apps in official and alternative android markets[END_REF]. Many of such markets are not capable to do a malware detection before they put a new app on the shelf. Some of them even solely depend on the feedback from users to decide whether an app needs to be removed from their markets or not. However, third party markets are more preferred than Google Play by many users. One reason is that these users need free apps which cannot be found in Google Play, e.g. free app of the day in Amazon appstore for Android. Another reason is that some users need a localized version of the original app, especially for users whose native language is not English. We arbitrarily selected a third party Android market in China, mumayi [START_REF] Mumayi | [END_REF], to investigate the risk of third party Android markets.

We downloaded 602 popular apps from mumayi using a crawler and collected their requested permission information. We then computed the risk level of each collected app using DroidRisk. Figure 8 shows the boxplots of the risk levels of apps from Google Play, apps from mumayi and malware. The median risk levels for apps from Google Play, apps from mumayi and malware are 0.32, 1.35 and 3.22, respectively. This indicates that to install an app from the third party market is more risky than the official market, Google Play. In this section, we show that reliable risk signal to identify potential malware can be generated with the quantitative risk information obtained by DroidRisk. The applications of DriodRisk for alleviating the overprivilege problem and improving the user attention to the risks of Android permissions and apps are also presented.

Reliable Risk Signal

Risk signals are used by users to identify potential malware. A reliable risk signal should be triggered by as many malware as possible, and rarely be triggered by benign apps. We compare the performance of DroidRisk with two state-of-art methods: Kirin from [START_REF] Enck | On lightweight mobile phone application certification[END_REF], RCP and RCP + RP CP from [START_REF] Sarma | Android permissions: a perspective combining risks and benefits[END_REF] using 10-fold cross-validation. The risk signal for RCP is generated with rule #RCP (θ) ≥ 1 which is the simplest one in [START_REF] Sarma | Android permissions: a perspective combining risks and benefits[END_REF]. The risk signal for RCP + RP CP is generated with rule #RCP (2) + #RP CP (1) ≥ θ which is the best performing one in [START_REF] Sarma | Android permissions: a perspective combining risks and benefits[END_REF]. The performance of Kirin is obtained with 7 rules as described in [START_REF] Sarma | Android permissions: a perspective combining risks and benefits[END_REF]. Figure 9 presents the ROC curves of different method for fold-1. For other folds, we obtained similar results. From Figure 9, we can observe that DroidRisk has significant better classification performance than other methods. One possible reason is that DroidRisk tries to capture the request patterns of both normal and dangerous permissions while there are only 9 manually defined rules in Kirin and only 24 or 26 critical permissions are used for RCP and RCP + RP CP .

Figure 9 also shows that the risk signal of Kirin is not tunable as the rules are predefined. Although the risk signals generated by RCP and RCP + RP CP are adjustable, it is not easy to find a reliable one since there are several parameters to be tuned. With the quantitative risk information generated by DroidRisk, the risk signal is generated from a single threshold of risk level which can be easily found using ROC curve. The simple thresholding operation also makes it suitable to be implemented in resource-constrained mobile devices.

The results of the 10-fold cross validation are shown in Figure 10, where Fscore is used as the performance measure. The parameters of DroidRisk, RCP and RCP + RP CP are chosen as the best performing ones for the training sets. It can be seen that DroidRisk has the best performance among all the methods.

Overprivilege Problem

Android permission system gives the app developers the ability of requesting any permission no matter they actually use it or not. Many developers and users rarely pay attention to whether the requested permissions are useful for them or not. As a result, Android apps tend to be overprivileged, which may raise security problems. We randomly selected 50 popular apps from both the third party Android market, mumayi, and Google Play. We used the Stowaway [START_REF] Felt | Android permissions demystified[END_REF] to detect unnecessary permissions in each app. Table 1 shows the statistics of the collected apps due to the overprivilege problem. The boxplots in Figure 11 show how the unnecessary permission affect the risk levels of apps from mumayi and Google play. It can be seen that the overprivilege problem is common in both the official and third party markets although the problem is much severe in third party market. The median risk level of apps from mumayi has increased from 1.04 to 1.43 due to overprivilege. Although the median risk level of apps from Google Play only increases from 0.64 to 0.66, we did find 7 apps whose risk levels raise above the threshold set by DroidRisk because of those unnecessary permissions, which makes them suspicious to be malware. Since the app developers always try to get more downloads, declaring unnecessary permissions to result in a high risk level for the app will make the user more likely to cancel the download because of the warning of our DroidRisk system. Thus, the overprivilege problem can be alleviated since the developers need to be more careful about requesting permissions for their apps, especially those related to possible malicious activities.

mumayi Google Play Percentage of overprivileged apps 64% 44%

Average # of unnecessary permissions 1.92 0.84

Table 1: Statistics of the collected apps from mumayi and Google Play due to overprivilege problem Fig. 11: Risk levels with and without unnecessary permissions for apps from, (a-b): mumayi, (c-d): Google Play

Improving User Attention to Risks of Android Permissions and Apps

One problem with current Android permission system is that all information related to the risks of permissions are text descriptions while users often do not pay attention to the text information due to various reasons [START_REF] Felt | Android permissions: user attention, comprehension, and behavior[END_REF]. One of the design goals of DroidRisk is to improve the user attention of the risks of Android permissions and apps. In the following, we show two applications that utilize the quantitative risk information obtained by DroidRisk to reach this design goal.

App web page with quantitative risk information: Each Android app has a web page after it is submitted to an Android market, official or third party. Users often browse the market to find out interesting apps for their devices. Since the text-based permission information shown in the app's web page is not effective in informing the user about the risk of the app, we developed a solution to present the quantitative risk information of the app and its requested permissions in the web page. The solution was implemented in FireFox browser by creating a GreaseMonkey3 script to change the display of the app's web page. Figure 12 uses the Fake SMS Creator Free app's web page in Aptoide, a third party market [START_REF]Aptoide[END_REF], as an example to show how the risk information of the app and its requested permissions are displayed in the web page. The current design uses a colored box that displays the risk value of an app or a requested permission. The color scheme of the design corresponds to the risk level. When the user's mouse moves above the box of the app's risk level, a textbox will be shown to alert the potential risk and ask the user to see the list of permissions. It is expected that this design with the quantitative risk information and the color-based visual cue can significantly improve the attention rate of Android permission system.

DroidRisk Android App: To let the users evaluate the risks of apps installed in their local devices, we developed an Android App of the same name as the framework. This app extracts the permissions requested by each installed app and computes the risk level of the app. Figure 13(a) shows the app's interface which shows the list of installed apps with their corresponding risk levels. The user can tap any app to see the list of permissions requested by the app and their risk levels (Figure 13(b)). The app also uses a color scheme to give the users a direct visual cue of the risk level. We plan to expand the functionalities of DroidRisk app in future to report the risk level of any app in any Android market once the user provides the corresponding information.

Conclusion

In this paper, we demonstrate that the proposed DroidRisk framework can be used to improve the efficiency of Android permission system for informing the user about the risks of Android permissions and apps. It can be easily incorporated into existing Android malware detection systems as the first barrier to prevent the spread of malware. It will be especially useful for those third party markets without malware detection capability. In our future work, we will investigate alternative ways to find the impact levels of Android permissions, e.g. based on the study of [START_REF] Felt | I've got 99 problems, but vibration ain't one: a survey of smartphone users' concerns[END_REF] which ranks the risks of permissions according to the users' ratings. We will also explore security rules involving multiple permissions and evaluate their corresponding risks which may be underestimated by DroidRisk.

Fig. 1 :

 1 Fig. 1: Top 20 most popular permissions in: (a) malware dataset (b) benign app dataset

Fig. 2 :

 2 Fig. 2: Percentage of apps requesting certain number of permissions: (a) malware (b) benign apps; Percentage of apps requesting certain number of dangerous permissions: (c) malware, (d) benign apps

Fig. 4 :

 4 Fig. 3: Top 20 permissions with highest likelihood value

Fig. 6 :

 6 Fig. 5: Top 20 permissions with highest risk levels

Fig. 7 :Fig. 8 :

 78 Fig. 7: Top 20 benign apps with highest risk levels

Fig. 9 : 1 Fig. 10 :

 9110 Fig. 9: ROC curves of different methods for fold-1

Fig. 12 :Fig. 13 :

 1213 Fig. 12: Screenshot of the Fake SMS Creator Free app's web page in Aptoide with quantitative risk information

  ) benign app dataset malware, 62.5% of them have at least 7 dangerous permissions, and around a quarter of them request 13 or more dangerous permissions. Clearly, malware are more interested in dangerous permissions for their malicious activities.

	0% 4% 8% 12% 16% 20%	0	2	4	6	8 10 12 14 16 18 20 >20	20% 16% 12% 8% 4% 0%	0	2	4	6	8 10 12 14 16 18 20 >20
						(a)						(b)
	0% 4% 8% 12% 16% 20%						0% 4% 8% 12% 16% 20%
		0	2	4	6	8 10 12 14 16 18 20 >20		0	2	4	6	8 10 12 14 16 18 20 >20
						(c)						(d)

GreaseMonkey is a Firefox add-on that allows the user to customize the display or behavior of a web page using a user script[START_REF] Greasemonkey | [END_REF].