Hafiz Asif

Jaideep Vaidya

Basit Shafiq

Nabil Adam

Secure and Efficient k-NN Queries

Keywords: k-NN queries, k-NN classification, Privacy, Distributed computation

Given the morass of available data, ranking and best match queries are often used to find records of interest. As such, k-NN queries, which give the k closest matches to a query point, are of particular interest, and have many applications. We study this problem in the context of the financial sector, wherein an investment portfolio database is queried for matching portfolios. Given the sensitivity of the information involved, our key contribution is to develop a secure k-NN computation protocol that can enable the computation k-NN queries in a distributed multi-party environment while taking domain semantics into account. The experimental results show that the proposed protocols are extremely efficient.

Introduction

Nearest neighbor (NN) queries are an extremely important data analysis tool, and have been used in numerous domains. Indeed, they have been identified (in the form of k-NN classification) as one of the top 10 algorithms in data mining [START_REF] Wu | Top 10 algorithms in data mining[END_REF], though they can also be used for other applications such as regression, content retrieval, and structure prediction. While the typical use of k-NN does not worry about the sensitivity of the data, k-NN is also applicable in many cases where the data may be private, and the organization interested in querying is different from the organization holding the data.

Consider the financial environment, wherein we have several organizations (such as Ameritrade, Charles Schwab, etc.) which possess financial data about individuals, including their current stock positions, transactional history, etc. Now, a regulating agency such as the SEC may be interested in finding individuals who have a certain stock position, or have indulged in particular type of transactional behavior. Since perfect match is often difficult, best match queries are used to find the closest individuals of interest. Alternatively, a financial advisor service might want to provide recommendations based on similar stock positions or transactional behavior. Typically, since financial data is extremely sensitive, the organizations may be unwilling or even (legally) unable to allow unfettered access to this data. However, in certain cases, there may be a lot of value associated to be obtained through computing the best match queries. For example, one can identify trading behavior of investors from their portfolio structures as shown by [START_REF] Bohlin | Stock portfolio structure of individual investors infers future trading behavior[END_REF]; this kind of information is invaluable for numerous organizations e.g. State Exchange Commission (SEC) in the United States. Similar problems exist in the field of medicine, finance, and homeland security.

In this paper, we address this specific problem. We consider the scenario where several organizations possess independent portfolio databases, each record of which contains financial stock positions for a single portfolio. Together, these databases comprise the global database which contains the portfolios of all entities, though no third party exists which knows this global database in its entirety. Another organization, called the querier, would like to query this global database to retrieve the k portfolios that are the most similar to a particular query portfolio that it possesses. All of the organizations would like to protect the privacy of their information, while still enabling the computation. There has been some work addressing this problem in the past, especially in the context of outsourcing [START_REF] Elmehdwi | Secure k-nearest neighbor query over encrypted data in outsourced environment[END_REF][START_REF] Wong | Secure knn computation on encrypted databases[END_REF]. Our proposed solution improves on the state of the art by providing a way to incorporate the domain semantics and is significantly more efficient. Our solution is also applicable in the outsourcing environment where an organization may want to outsource its database in encrypted form and still enable best match queries. Furthermore, our solution can be extended to provide top-k results based only on private ranking criteria (without reference to a specific query point) in an even more efficient fashion. It is worth noting that while the problem has been formulated in the context of financial domain, our approach is quite general and can be used to solve k-NN and top-k query problems in any domain. Overall, our key contributions are:

1. We introduce the notion of semantic distance which is useful in taking domain semantics into account while computing k-nearest neighbor queries. 2. We propose an extremely efficient multi-party protocol to compute k-NN queries that is robust to semi-honest adversaries. 3. We show how the protocol can be adapted to the outsourced data model and used for k-NN based classification without leaking any additional information.

Problem Statement

In this paper, we build a protocol for overcoming the privacy problem for situations where organizations (or people) are interested in finding the best matches for a query over distributed data. As discussed earlier, we formulate the problem in the context of the financial domain i.e., finding investment portfolios from a distributed database, which best match a given query portfolio in a dynamic and semantic aware environment, while also providing confidentiality and security-privacy guarantees to the parties involved in the protocol. We consider a database P ∈ R N ×M is horizontally distributed among n parties P 1 , . . . , P n such that for all i ∈ [n] and N i ∈ N the database fragment P i ∈ R Ni×M is kept by P i where i∈[n] N i = N . Each party P i collects the same features of information but for different entities. These parties could be banks, hedgefunds, mutual-funds, or other institutions. Another party Q is interested in performing a k-NN query, which also incorporates structure and semantics, on this distributed data without revealing its query, while the parties owning data being queried want to avoid disclosure of their data except for the legitimate output of the query. Thus, the problem can be formally defined as follows:

Definition 1 (Distributed Secure k-NN query: DS-kNN). Given a database P ∈ R N ×M , which is horizontally distributed among n parties with party P i having fragment P i ∀i ∈ [n], a querier Q wants to privately find semantic distance (definition 3) based k-NN in P to its query q ∈ R M for N, M, n ∈ N, where n ≥ 2.

Definition 2 (Security/Privacy). A protocol Π computes DS-kNN query securely if it reveals nothing but k-NN records to Q with leakage L to all other parties with negligible probability in security parameter -a function,

µ (m), is negligible in m if µ(m) < 1 p(m)
for all sufficiently large m and polynomial p (m).

Hence definition 2 ensures that data owners do not learn anything about the query beyond what they already know or infer from leakage, and Q learns nothing about P beyond what it already knows and can infer from the output and leakage Adversarial Model: We assume all parties to be non-colluding and semi-honest (i.e., honest-but-curious) adversaries, who communicate over a secure channel. However, restriction on collusion among the data owners can be relaxed to the collusion of at least α data owners, where α ≤ n (total number of data owners). We can accomplish this (without any major change in the proposed protocol) by employing additive homomorphic encryption with threshold α, which for decryption will require α parties each performing partial decryption on an encrypted message.

Proposed Approach

We first introduce a notion of semantic awareness for distance metrics that can capture the desired level of granularity and structure for measuring similarity. For example, standard distance metrics such as Euclidean distance fails to capture structural and semantic information such as the industry or sector a stock belongs to, market capitalization, risk and type of the stock, etc. Consider an investor who would like to find similar portfolios, while incorporating portfolio structure and/or commodity relationships with regards to a particular categorization model (e.g., the industry classification of stocks [START_REF]Industry classification benchmark[END_REF]). Such a categorization model would typically be built by domain experts.

We assimilate the categorization model into the distance metric, denoted sem dist, which we term as the semantic distance. This enables the integration of semantic information representing the true interest of the querier, while evaluating similarity among portfolios (or records). We now formalize the notion of semantic aware distance and then discuss how it will be calculated in a secure (and privacy-preserving) manner.

Definition 3. Semantic Distance between two points X, Y ∈ R M is Euclidean distance between their linear projection in space R l , where l, M ∈ N and the projection is guided by a given categorization model (map, W ), and is formalized as follows.

sem dist(X,Y) = l:c l ∈C   j:c l ∈map(sj ) w lj (x j -y j )   2
Here, map : S → 2 C specifies the category c l ∈ C to which the stock s j ∈ S should be mapped with C and S being set of all the categories and set of all stocks respectively. C ⊆ C is the set of categories, for which sem dist is to be calculated, whereas w lj in W = [w lj ] |C|×M gives the number of units of c l equivalent to one unit of s j . We also define signed-distance(X,Y) at a category level (c l ) to be D l = j:c l ∈map(sj )

w lj (x j -y j ).

Tuple (map, W ) defines categorization model. map gives the relationship among commodities e.g., Industrial Classification Benchmark (ICB) [START_REF]Industry classification benchmark[END_REF] provides a classification for stocks based on the sector and industry; equivalently map could specify the categorization based on market capitalization or some other type. W , here, could denote a weight factor to estimate equivalent worth of a stock in an industry or sector. In general, sem dist allows for a richer query specification, which is very helpful. For example, sem dist allows accounting for risk and/or diversity of each portfolio, while calculating distance between a portfolio and a query portfolio. Here we show, using an example, the effectiveness of semantic distance. Consider Table 1a, which contains three portfolios p 1 , p 2 and p 3 . Each portfolio specifies the number of stocks of AAV, RDC, ICD, GTT and NOW held in it. The stocks in Table 1a are from Oil and IT sectors. Table 1b gives the conversion factor per share of a stock to equivalent dollar value in a sector. Now, consider an investor who wants to find a portfolio from Table 1a, which is the closest in terms of its value at sector level. If Euclidean distance is directly used, then the results are not meaningful, as can be seen from the results in Table 1c; i.e., according to Euclidean distance, p 2 and p 3 are equally close (similar) to p 1 , whereas we notice that in term of the value of portfolio at sector level, p 1 should be closer to p 2 as compared to p 3 , since in contrast to p 3 , where only 15 shares of stocks are held in IT sector, p 1 and p 2 both hold 10 shares of stocks in Oil sector and 5 shares of stocks in IT sector. On the other hand if we use semantic distance then the results corroborate with our intuition and the semantic meaning of the query asked by the investor; this can be seen from the calculated distances in Table 1d. Though the calculated Euclidean distance is spatially correct, it fails to capture a lot of domain, structural and semantic information. We stress that the proposed protocol is also able to calculate secure DS-kNN query based on simple Euclidean distance measure. In semantics distance formulation, this can be accomplished by a map : S → C, which is bijective, and setting W to identity matrix of dimension |S| × |S|. This will essentially calculate the Euclidean distance between two points.

AAV RDC ICD GTT NOW

p1 p2 p3 p1 0 10 √ 2 10 √ 2 p2 10 √ 2 0 10 √ 3 p3 10 √ 2 10 √ 3 0 (c)

DS-kNN Query Protocol

Before presenting the details of the approach to compute the k closest portfolios as per the problem definition above, we first present the underlying assumptions, the notation used, and a few preliminaries. N , S and C are known to all the parties including querier. Furthermore, each data owner (P i ) knows the size (N j ∀j ∈ [n]) of all databases fragments P j . The database can be viewed as a matrix. In rest of the paper by parties/party we mean parties/party owning data, whereas Q is referred to as querier. Additive homomorphic encryption (AHE) e.g., Paillier allows addition of two encrypted values and multiplication of encrypted value with a plain-text value. The plain text values on which AHE operates come from N; let us say for a given security parameter λ AHE accepts plain-text values from P (λ) such that ∀x ∈ P (λ), x < Λ, where Λ ∈ N. We divide P (λ) into two halves where lower half is positive and upper half is negative (i.e. contains additive inverses of lower half). Whenever a text is decrypted it is converted to equivalent negative or positive value; additive inverse of an encrypted value x i.e.,

E pk [x], is E pk [x] Λ-1 .
As for the decimal values we can decide for a precision up to a decimal point d, then multiply each plain-text value with 10 d and convert it to an integer value. λ ∈ N is picked in such a manner that the finally computed plain-text value in encrypted form is always within the range. We also employ garbled circuit [START_REF] Yao | Protocols for secure computation[END_REF] for secure comparison.

The basic idea in DS-kNN is for data owners to encrypt the portfolio database and send it to Q, who calculates signed-distances w.r.t. its query, q, in encrypted form (Algorithm 1), and uses them to collaboratively calculate semantic distances in form of random shares with a data owner (Algorithm 1). A distributed rank query is then carried out to identify the indices of k portfolios with the smallest distances (Algorithm 2). Finally, Q retrieves portfolios, corresponding to the indices identified above, from the portfolio database.

We now discuss the details. In Algorithm 1 we outline the algorithm for DS-kNN, where a party P t is picked at random from data owners to initiate the protocol. P t can be picked by each party generating a random number r i from [n] and then calculating i∈[n] r i mod (n + 1) using secure sum [START_REF] Clifton | Tools for privacy preserving distributed data mining[END_REF]. P t generates public-private (pk, sk) key pair of AHE and sends it to all data owners and pk to Q. P t also picks two parties P l and P l randomly and lets all the parties know who they are. Next, every P i first permutes its database, and creates encrypted shares

EP i = E pk [P πi i -R i ] and ER i = E pk [R i ].
Note that these are homomorphically encrypted additive random shares of P i . Now P i sends EP i to P l and ER i to P l . This ensures that every database is split into two parts and thus prevents the leakage of any information to other parties or to Q. P l and P l put all of these shares together and permute them using a common random seed s (which can be done by having P l and P l each pick a random number and send it to the other and then compute the XOR of both random numbers). These encrypted permuted Permute the database Pi:

P π i i = π(si, Pi) 8:
Create encrypted random shares of

P π i i : (EPi, ERi) = (EP pk [P π i i -Ri], EP pk [Ri]) 9:
Send EPi to P l and ERi to P l 10: P l sets EP = π(s, (EP1, . . . , EPn)){seed s is picked together by P l and P l } 11: P l sets ER = π(s, (ER1, . . . , ERn)) 12: P l and P l respectively send EP and ER along with t to Q 13: Q permutes EP and ER using random seed ŝ: (EP π , ER π ) = (π(ŝ, EP ), π(ŝ, ER)) 14: Q sets qenc = E pk [q] (Λ-1) 15: Q initializes matrices, T and DQ, of sizes N × |C| and N × 1, to have E pk [0]'s and 0's resp. 16: Pt initializes Dt as matrix of 0's with size N × 1 17: for each i ∈ [N ] do 18:

for j ∈ {1, . . . , |S|} do 19:

Q sets T [i, map[j]] = T [i, map[j]] × (EP π [i][j] × ER π [i][j] × qenc[j]) W [map[j],j] 20:
for l ∈ {1 . . . |C|} do 21:

Q generates random numbers r and g and sets TQ[i, l] = -r 2 + g 22:

Q sets vr = E pk [T [i, l]] • E pk [r] (Λ-1) and vg = E pk [T [i, l]] 2r • E pk (g) (Λ-1)

23:

Q sends (vr, vg) to Pt 24:

Pt sets Tt shares (denoted EP and ER) are then sent to Q. At this point, Q also randomly permutes the received shares of the database to avoid linkage attack by data owners. Q can reconstruct the database by adding together the received shares of database in encrypted form. Q then proceeds to calculate signed-distance in encrypted form according to its specified (map, W ) and C. This steps consists of addition of encrypted values and their multiplication by values in plain-text (weights), which can be done in encrypted form thanks to the additive homomorphism.

Next, these signed distances need to be squared. This is accomplished by Q generating random numbers, r and g for each signed-distance, v i,l . Q sets its random share for the squared signed-distance to be v 1 i,l = -r 2 + g, and sends P t , E pk [v i,l -r] and E pk [2rv i,l -g]. P t decrypts the received encrypted messages, converts them to appropriate negative or positive values as explained in preliminaries and sets its share to be for i ∈ 1 . . . do 6:

v 2 i,l = (v i,l -r) 2 + 2rv i,l -g. It is obvious that (v i,l ) 2 = v 1 i,l + v 2 i,l . Summing all Algorithm 2 k-Smallest(D Q , D t ,
Q sets UQ[i] = (VQ[i] -µQ ); Pt sets Ut[i] = (-Vt[i] + µt ) 7: if UQ[i] ≤ Ut[i] {At Q, Pt: Yao Comparison} then 8:
Remove i th element from VQ and Vt and add to V Q and V t at Q and Pt respectively 9:

for j ∈ {Q, t} do 10:

if

|V j | > k then 11:
set Vj = V j 12: else 13:

For each element in V j , add to I the index of corresponding element in Dj 14:

k = k -|V j | 15: return I
shares of squared signed-distances of a portfolio will give the share of square of semantic distance for the portfolio. Thus Q and P t can compute their shares for the distance for each portfolio since sem dist(p i , q

) 2 = |C| l=1 v 1 i,l + |C| l=1 v 2 i,l
. At this point, the square of semantic distance between each portfolio and the query has been randomly split between Q and P t . For the sake of efficiency we do not compute the square root of squared semantic distance. However, this does not impact correctness of the protocol. Henceforth, Q and P t engage in an interactive protocol to compute the k smallest distances corresponding to k-NN portfolios. To find the k-smallest entries from the split distance vectors we develop a novel protocol k-Smallest that can accomplish this both securely and efficiently. We first present the simple-k-smallest (SKS) protocol, that efficiently computes the k-smallest entries without worrying about security. For a given a vector V containing unique values, v, and S = {}, the k-smallest values can be found as follows:

-1: Set µ = v∈V v |V | and divide V into V g = {v ∈ V : v > µ} and V le = V \ V g -2: If |V le | > k, set V = V le and go to step 1 -3: If |V le | ≤ k then set V = V g , S = S ∪ V le and k = k -|V le | -4: if k = 0 go to step 1, terminates otherwise
SKS terminates, since each iteration reduces size of V . Note that, only the correct distances are added to the output in step 3 since the distances in V le are guaranteed to be smaller than the ones in V g . SKS works very well for our problem setting and can easily be extended to be secure. Though any point in V instead of arithmetic mean can be used to split V without affecting correctness of the algorithm, choice of arithmetic mean as a split point is quite effective as long as subsets (of different sizes) of data are not highly skewed to the left for small values of k. This assumption does hold in real world Fig. 1: Empirical analysis data. Specifically, we show through empirical analysis that portfolio distances for real world stock market data [START_REF] Bohlin | Stock portfolio structure of individual investors infers future trading behavior[END_REF] are but slightly skewed to left. We used portfolio data of hundred thousand individuals, which was collected over the period of three years from Swedish stock market [START_REF] Bohlin | Stock portfolio structure of individual investors infers future trading behavior[END_REF]. We calculated the mean distance and variance for the mean distance over samples of various sizes (i.e., number of portfolios). Figure-1a depicts the percentile for mean distance and average percentiles for mean distances. It can be seen that mean distance is consistently at percentile 60. Figure-1b depicts the variance for the above calculated percentile for mean distance, and the average variance, which asserts that percentile for mean distance does not vary much. The complexity of SKS for such a distribution will be O(|V |) regardless of value for k. In the case where data is highly skewed or follows exponential distribution or leakage function is different a randomly picked data points can be used as a split point instead.

Now we focus on devising a secure and distributed SKS so that it can be carried out on random shares of distances without violating the privacy. It is easy to see that if the first step of SKS can be performed in a secure and distributed form (note, in our case, D Q and D t together give V ), the remaining steps can be performed locally at Q and P t . SKS requires the distances in vector to be unique i.e. ∀i ∈

[N ], D Q [i] + D t [i] is
unique. This is necessary, not only to guarantee that the protocol terminates but also to ensure security. In essence, if distances were non-unique, it could have been possible that all of the distances were same, thus resulting in V le = V for all iterations. Since, in our case, uniqueness does not generally hold; therefore, we use a perturbation mechanism to achieve uniqueness. This can be accomplished by scaling the distance of portfolio p i by N , and translating it by i. In the protocol, k-smallest, it is carried out as follows: Q multiplies D Q [i] with N while P t multiplies D t [i] with N and adds i to it (lines 1-2 of algorithm 2) (Note:

|D Q | = |D t | = |P| = N ), which will together gives us N × (D Q [i] + D t [i]) + i.
Next we need to devise a secure and distributed protocol to compute mean and identify indices of

D Q or D t for which distances (D Q [i] + D t [i]
) are greater than the mean. If we let mean distance to be µ

= µ Q + µ t , where µ Q = i D Q [i]/N and µ t = i D t [i]/N then D Q [i] + D t [i] > µ ⇐⇒ D Q [i] -µ Q > -D t [i] + µ Q
The above observation tells us that result of comparing the distance for a record against the mean distance can be equivalently obtained by comparing the difference between random share and the mean of random shares. Note that since Q and P t can locally compute this difference, the parties can simply use a secure comparison [START_REF] Yao | Protocols for secure computation[END_REF] (the garbled circuit approach) to compute the first step of SKS in a secure manner. Furthermore, Since we are using a finite integer field, it is possible that µ Q and µ t are fractional, and hence outside the field. To avoid this we use the output of floor-function on µ Q and µ t and employ the following comparison instead:

D Q [i] -µ Q > -D t [i] + µ t , but it does not affect the performance of algorithm 2 since 0 ≤ µ -( µ Q + µ t ) < 2.
Since the remaining steps are local, both parties can calculate k-smallest entries securely and identify their corresponding indices in D Q or D t . Result Extraction: Using above found indices Q can identify and obtain k-NN portfolios from the encrypted database. Let I contain the indices of k-smallest distances and ∀j ∈ I, tj and tj be the corresponding records in EP and ER then for all j, Q asks

P t for decryption of E pk [ϕ j ] = E pk [ tj ] ⊗ E pk [ tj ] ⊗ γ j ,
where γ j is uniformly picked vector of size |S| from an appropriate domain and ⊗ gives coordinate-wise product of two vectors. It is straightforward to compute E pk [ϕ j ] for homomorphically encrypted values and the original record t j from ϕ j i.e., t j = ϕ j -γ j . Thus completing the protocol for computing sem dist based k-NN for horizontally fragmented database in a privacy preserving fashion.

Extensions

We can easily extend the protocol devised above to work for the outsourced data model. It can also be used for k-NN classification. Both of these are briefly described below. Outsourcing Case: Our protocol can very simply be applied for the case where the computation of data owners is transferred to the cloud in a secure manner. Parties can pick non-colluding, semi-honest and untrusted servers C 1 and C 2 to take responsibilities of P l and P l respectively except for creation random shares of their databases and their encryption. All the responsibilities of P t for distance and k-smallest computation along with decryption for result retrieval phase are handed to one of the servers. Once responsibilities have been assigned to C 1 and C 2 , following the protocol stated in DS-kNN will compute k-NN securely in cloud. k-NN Classification Case: The proposed protocol also has the ability to carry out k-NN classification with a very small modification. Let us say there are G classes with labels {1, 2, . . . , G}. We append each database fragment with G new columns and name them 1, 2, . . . , G. For each row with class label g only column g of the appended G columns will have the value 1, and value 0 for the others. Now all the steps outlined in DS-kNN are carried on the database with appended columns, except for the result retrieval step; furthermore, appended columns are not used for k-NN computations. Once Q has identified k-NN records in encrypted database, it computes a vector G, where ∀g ∈ [G], G[g] contains k minus the sum of values in column g of k-NN records i.e., k minus the number of votes for each class; thus smaller the value G[g], higher the number of votes for class g. Next, Q permutes G, creates random shares of values in π(G) and send them to P t , after which both Q and P t follow k-smallest protocol with k = 1. At the end of k-smallest Q is able to identify the class of its instance q.

Complexity Analysis

Let N be the number of portfolios in database P horizontally distributed among parties P 1 , . . . P n , where each record is of dimension M = |S|. The asymptotic computational complexity of DS-kNN is O(N 2 ) = O(N M, N × |C| + N 2 ) since in the worst case there will be O(N M ) encryption and O(N × |C|) decryption operations along with O(N 2 ) secure comparison by data owners, whereas querier will perform O(N × |C|) arithmetic operations on encrypted values and O(N 2 ) secure comparisons; furthermore, in most of the application scenarios M, |C|, k N . It is important to note that in real world data for portfolios require only O(N ) comparison to find k smallest entries as shown in Figure 1 and is explained in section 6. Moreover, |C| would also be much smaller as compared to |S| because thousands of stocks are traded in the market. So for all practical purposes asymptotically complexity for our problem will be O(N M ) Following the same reasoning as above the asymptotic communication complexity of DS-kNN will also be O(N M ).

With respect to the communication complexity, it may appear that the cost of transferring the entire database over is excessive. While this is true in terms of the communication itself, both the monetary and time cost of doing this is negligible, since currently available bandwidth and speed are quite high e.g, currently ISPs are providing 1000 Mbps connection to residential users and small businesses, which allows an encrypted database of million rows and ten attributes to be transferred in matter of few seconds. On the other hand, in many cases cost and the time required for secure operations are significantly higher than that of required for data transfer. Additionally, many of the secure protocols including [START_REF] Elmehdwi | Secure k-nearest neighbor query over encrypted data in outsourced environment[END_REF][START_REF] Qi | Efficient privacy-preserving k-nearest neighbor search[END_REF] require transferring complete database between/among the parties. Therefore, we believe that this cost is reasonable.

Security Analysis

In this section we analyze the security of DS-kNN under the framework of definition 2. We want to show the following: DS-kNN is secure if probabilistic polynomial time simulators S i (m, P i , L P ) and S Q (m, q, (map, W ), L Q , O k ) can respectively simulate the view of P i , ∀i ∈ [n] and Q during the execution of DS-kNN. This means that if S i is provided with P i 's input (m, P i ) and leakage L P ( which gives (J, j 1 , . . . , j J , N 1 , . . . , N n , |C|) ), and S Q with Q's input (m, q, (map, W )) and output (O k i.e. k-NN records) along with L Q (which gives (J, j 1 , . . . , j P , N, S) ) then these simulators will have the same view as their respective parties; thus asserting that DS-kNN reveals no extra information and does fulfill the security definition 2. In the output of leakage functions J is the total number of iterations taken in Algorithm 2 corresponding to P and q, j is the percentile of mean distance in th iteration, whereas rest of the symbols are same as defined previously.

Let us analyze S j for the situation where j = t and also j ∈ {l, l } ( l, l and t are as per specification in Algorithm 1) since such a party, P j , will receive the biggest set of intermediate messages, in all other cases parties receive less information. P j 's view consists of its input (m, P j ), random shares (D i ∈ N Ni×|S| , ∀i ∈ [n]) of database fragments, random shares (H R ∈ N N ×|C| ) of distances at category level, random seeds (s j , s), random-tape (r j ∈ {0, 1} p(m) ) and L P . P j 's view can easily be generated by S j : based on m, P j and L P that are provided to S j , it can generate D j i ← N Ni×|S| , H j R ← N N ×|C| , (s j , s j ) ← N 2 and r j ← {0, 1} p(m) , L Pj using uniform distribution. Thus P j 's view, (m, P j , D 1 , . . . , D n , H R , s j , sj , r j , L P ), is computationally indistinguishable from S j 's view, (m, P j , D j 1 , . . . , D j n , H j R , s j , s j , r j , L P ), in polynomial time, otherwise pseudo-random generator, which is assumed to be secure, can be broken which is used to create random shares and seeds. It is straightforward that for all other cases a party's view will consist of less information than that of P j 's view; hence ∀i ∈ [n], S i will be able to generate P i 's view.

The case for S Q , is also very similar in that respective inputs, output, and leakage is provided to S Q , except for the difference that Q receives encrypted database EP ∈ N N ×|S| instead of random share of a database, but since AHE is (semantically) secure -meaning EP is computationally indistinguishable from EP ← N N ×|S| (i.e. generated uniformly)-S Q can generate a view using m, q, (map, W ) and L Q that is indistinguishable from Q's view. Thus proving that DS-kNN is secure.

Note that the defined leakage reveals information, usually known in our application scenario. If one wants to hide this information then following is one way to accomplish this. Instead of mean distance, randomly picked distances can be used for the purpose of comparison to find k-smallest distances; dummy portfolios with sentinel values can be added to hide size of database; extra columns can be added for dummy coordinates, mapping to which can be provided through a secure and modified bloom filter. |C| can be hidden by adding dummy signed-distances with value zero. Though such measures will stop the leakage, they will significantly reduce the efficiency of the protocol.

Experimental Evaluation

We implemented DS-kNN in Java. The platform used for testing is asymmetric in terms of its computational power. The querier machine had a 2.2 GH core-i7 processor and 16 GB RAM whereas each of the database owners was a Xeon E5-2680 v2, with 10 cores running at 2.80GHz, and 96 GB RAM. For AHE and garbled circuit we employed the implementation available at [START_REF]Pailliar encryption implementation[END_REF] with key size 1024 and [START_REF] Henecka | Faster secure two-party computation with less memory[END_REF] with a key size of 512 respectively. The default values for parameters are set based upon domain semantics. Specifically, even though 2k-3k stocks are traded on the stock exchange, only a few hundred of them are most often traded; thus we set |S| to be 100. |C| is set to be 10 because ICB [START_REF]Industry classification benchmark[END_REF] classification taxonomy segregates stocks to 10 industries at the top level. As for k, it is set to 1, which represents the worst case for Algorithm 2. Lastly, N is set to be 1000. For each experiment, only one parameter is varied, while keeping the We also compare our work with Elmehdwi et al. [START_REF] Elmehdwi | Secure k-nearest neighbor query over encrypted data in outsourced environment[END_REF] for outsourcing case. Figure 1c compares the complete time taken by DS-kNN and SRkNN [START_REF] Elmehdwi | Secure k-nearest neighbor query over encrypted data in outsourced environment[END_REF]. For the sake of fair comparison results are computed for same parameters and equivalent processing power. It can be seen that DS-kNN outperforms existing state of the art by an order of magni-tude. Additionally, our implementation is in Java and uses threading only for decryption at P t , whereas implementation in [START_REF] Elmehdwi | Secure k-nearest neighbor query over encrypted data in outsourced environment[END_REF] uses the openMP parallelization framework. Thus with an equivalent implementation, our results can be further improved. Performance on real data: We obtained Swiss stock market data for year 2009-2011, which is a collection of portfolios of around 100k individuals for 300 stocks; the data was previously used in [START_REF] Bohlin | Stock portfolio structure of individual investors infers future trading behavior[END_REF]. We only evaluated the performance of k-smallest protocol because time for distance computation is independent of data distribution. We randomly picked a subset of the data and choose one portfolio from it as the query portfolio, and computed the number of actual comparisons required by the k-smallest protocol for k = 1. Figure 2c plots the number of comparisons carried out for different values of N (the number of portfolios) along with a reference line for 2N . The two lines are almost perfectly in lock-step, which demonstrates the efficiency and suitability of our algorithm for real world data. However, in the worst case, it is still possible that in each iteration only one distance will be removed resulting in O(N 2 ) total comparisons.

Related Work

Privacy-preserving data mining has received a lot of attention [START_REF] Vaidya | Privacy Preserving Data Mining[END_REF]. Given the numerous practical applications of privacy-preserving k-NN search, various protocols have been developed to address this problem. [START_REF] Burkhart | Fast privacy-preserving top-k queries using secret sharing[END_REF][START_REF] Vaidya | Privacy-preserving kth element score over vertically partitioned data[END_REF] present solutions to the problem of computing k-NN, where the data is fragmented among different parties, while also preserving privacy. [START_REF] Boneh | Private database queries using somewhat homomorphic encryption[END_REF] uses a semi-trusted third party to find best k matches. In [START_REF] Qi | Efficient privacy-preserving k-nearest neighbor search[END_REF] Qi et al. introduce a single-step protocol for k-NN search, whereas [START_REF] Ghinita | Private queries in location based services: anonymizers are not necessary[END_REF] proposed a secure k-NN searching protocol based on PIR for location-based services. However, none of the above work is appropriate for computation over encrypted data. [START_REF] Kaleli | Privacy-preserving som-based recommendations on horizontally distributed data[END_REF] solves recommendation problem using Self-Organizing Map for clustering and k-NN based collaborative filtering, but reveals query to data owner. Zang et. al. in [START_REF] Zhang | Privacy-preserving distributed k-nearest neighbor mining on horizontally partitioned multi-party data[END_REF] employ homomorphic encryption for finding k-NN in distributed setting, but in contrast to our work it reveals distances, partial access pattern to the parties. In [START_REF] Xiong | Mining multiple private databases using a knn classifier[END_REF], the query along with k-NN distances is exposed and the output is less accurate. [START_REF] Kantarcıolu | Privately computing a distributed k-nn classifier[END_REF] makes use of untrusted third party and reveals query to parties. Although semantic distance can be applied here, the categorization model will be revealed to data owners. Shaneck et. al [START_REF] Shaneck | Privacy preserving nearest neighbor search[END_REF] provide a solution that reveals partial access pattern while being slower than our proposed protocol. Not only is our protocol straightforwardly extensible to provide outsourcing and k-NN classification, but it also allows for incorporation of semantic distance, while still being comparatively very efficient as compared to state of the art [START_REF] Elmehdwi | Secure k-nearest neighbor query over encrypted data in outsourced environment[END_REF].

Conclusion and Future Work

In this paper we have presented a secure approach to computing k-nearest neighbor queries for horizontally distributed data. Our approach is an order of magnitude faster than the existing state of the art. It is also applicable in the outsourcing environment, and can be used to compute top-k queries, as well as k-NN based classification. In the future, we plan to develop solutions that are resilient to stronger adversaries, some of which may collude as well.

  [i, l] = D sk [vr] 2 + D sk [vg]{D sk decrypts to equivalent +ive/-ive value} 25: Q sets DQ[i] = DQ[i] + TQ[i, l] 26: Pt sets Dt[i] = Dt[i] + Tt[i, l] 27: Q and Pt interactively find indices of k-smallest distances: I ←k-Smallest(DQ, Dt, k) 28: return portfolios corresponding to I to Q by getting their random shares decrypted from Pt

  k) Input: At Q: DQ, at Pt: Dt, such that DQ and Dt are random shares of the squared distances Input: At Q, Pt: k, the number of closest records desired Output: At Q: I, the array containing indices of smallest elements in DQ + Dt 1: At Q: ∀i, VQ[i] = DQ[i] × |DQ| 2: At Pt: ∀i, Vt[i] = Dt[i] × |Dt| + i 3: while k > 0 do 4: Q sets (µQ, ) = (mean(VQ), |VQ|), and Pt sets (µt, ) = (mean(Vt), |Vt|) 5:

  (a) mean distance's percentile (b) percentile's variance (c) Comparison with Samanthula et al. [7]

Fig. 3 :

 3 Fig. 2: k-smallest (Algorithm 2) computation time

Table 1 :

 1 Example illustrating Semantic Distance Effectiveness

		p1 0 p2 50 p1 √ 74 p3 100 √ 109 50 50 p2 √ 74 100 p3 √ 109 0 50 √ 794 √ 794 0
	Euclid distance	(d) Semantic Distance

  Algorithm 1 DS-kNN Input: (m, Pi) at Pi ∀[n], security parameter and database of portfolios Input: At Q: q, query; (map, W ), categorization model; k, number of NN; m Output: Q gets k-NN portfolios 1: Generate random seed, si, at Pi ∀i ∈ [n] 2: All data owners, P1, . . . , Pn, together pick t uniformly from [n] 3: Pt generates (pk, sk), key pair, for AHE and shares it with all data owners, and pk with Q 4: Pt picks l from [n] and l from [n] \ {l} uniformly and sends (l, l ) to all data owners 5: for each Pi ∀i ∈ [n] do 6: Generate a matrix Ri of random numbers: Ri ← N N i ×|S| {Ni is the size of Pi} 7:

The work of Shafiq is supported by HEC grant under the PAK-US Science and Technology Cooperation Program and by HEC NRPU grant. The work of Adam is supported by the National Academies of Sciences, Engineering, and Medicine under the PAK-US Science and Technology Cooperation Program. The work of Vaidya and Asif is supported in part by the National Science Foundation Grant CNS-1422501 and the National Institutes of Health Award R01GM118574. The content is solely the responsibility of the authors and does not necessarily represent the official views of the agencies funding the research.


Gheorghe Hȃjmȃşan
email: gheorghe.hajmasan@cs.utcluj.ro

Octavian Cret
email: octavian.cret@cs.utcluj.ro

Evasive Malware Detection using Groups of Processes

Fueled by a recent boost in revenue, cybercriminals are developing increasingly sophisticated and advanced malicious applications. This new generation of malware is able to avoid most of the existing detection methods. Even behavioral detection solutions are no longer immune to evasion, mostly because existing solutions focus on the actions or characteristics of a single process. We propose shifting the focus from malware as a single component to a more accurate perspective of malware as multi-component systems. We propose a dynamic behavioral detection solution that identifies groups of related processes, analyzes the actions performed by processes in these groups using behavioral heuristics and evaluates their behavior such that even evasive, multiprocess malware can be detected. Using the information provided by groups of processes, once a malware has been detected, a more comprehensive system cleanup can be performed, to ensure that all traces of an attack have been removed and the system is no longer at risk.

Introduction

Malicious software has become the foundation of a highly profitable industry. To maximize profit, malware authors are developing increasingly sophisticated attacks. The new breed of malware is able to avoid static detection through various methods, like obfuscation or encryption. To make detection even more difficult, thousands of new malware or variants of existing malware are being released every day. Consequently, dynamic detection has become more important, representing a last line of defense in security solutions.

Currently, the majority of dynamic malware detection techniques evaluate the behavior of a process and, using a set of rules, decide if that process is malicious or not. The rule set must accurately differentiate between malicious and non-malicious processes. Because a balance between detection rate and number of false positives must be assured, a dynamic detection system can not be too aggressive when evaluating a single process. Advanced malware may take advantage of this lack of aggression. They can evade being detected by separating malicious actions into multiple processes through process creation or code injection. This separation causes current dynamic detection systems to be unable to detect some of the malware components or, even worse, not to detect the malware at all. This is a major issue, because if a malware attack is only partially detected and the malicious components are not entirely removed from a system, they will continue to represent a serious security risk for the user.

We propose a behavioral detection solution that overcomes the issue of detecting evasive malware. We propose renouncing the current view of malware as single component systems and adopting a more accurate and comprehensive, multi-component based, method of evaluation and detection.

The following sections present a method to detect malicious groups of processes instead of single malicious processes. This research will provide a method for constructing such groups, together with a way to evaluate their actions so that malware groups can be detected. We also present a way to clean the infected system based on the actions performed by the processes in the detected group.

This paper is organized as follows: Sect. 2 presents the current state of research concerning behavioral malware detection and how most common solutions can be evaded. The proposed solution is described in Sect. 3 and the results of the proposed solution are presented in Sect. [START_REF] Ispoglou | malwash: Washing malware to evade dynamic analysis[END_REF]. The conclusions are mentioned in Sect. 5.

Related Work

An approach used in behavioral malware detection consists of extracting features based on the API calls performed by an analyzed sample. Devesa et. al. [START_REF] Devesa | Automatic behaviour-based analysis and classification system for malware detection[END_REF] propose identifying which actions were performed, based on API calls records. These actions represent features, used to classify a sample as malicious or clean.

Constructing graphs based on the relations between system calls represents another approach in behavioral malware detection. Elhadi et. al. [START_REF] Elhadi | Improving the detection of malware behaviour using simplified data dependent api call graph[END_REF] propose creating data dependent graphs, with nodes representing system calls and the edges, relations between their parameters or return values. An algorithm based on the Longest Common Subsequence is used to match the obtained graph to those of known malware stored in a database. Behavior graphs are also used in [START_REF] Kolbitsch | Effective and efficient malware detection at the end host[END_REF]. Compared to other similar solutions, the solution proposed by Kolbitsch et. al. has the advantage of matching the behavior graphs in real time, providing protection on the end host. Naval et. al. [START_REF] Naval | Employing program semantics for malware detection[END_REF] propose representing the behavior of a sample as an ordered system call graph and extracting relevant paths, which are considered features used for classifying the sample as malicious or benign.

Most dynamic malware detection solutions that focus on analyzing the behavior of individual processes are highly vulnerable to a certain type of evasion that is increasingly used by sophisticated malware and advanced threats. The evasion mechanism is quite simple: instead of executing all the malicious actions from a single process -which could be more easily detected by advanced security solutions -the malicious payload is distributed to multiple, distinct processes, and may be executed over a long period of time. Because behavior based detec-tion solutions can not usually detect a process based on a single action, multiple individual processes, each performing a smaller set of actions, may go unnoticed, allowing the malware to achieve its target goal undetected.

Ma et al. [START_REF] Ma | Shadow attacks: automatically evading system-call-behavior based malware detection[END_REF] developed a prototype tool, working at compiler level, that can generate multiple "shadow" processes from the original malware code. Each "shadow" process executes some of the payload, such that the original behavior of a process remains unchanged. Various methods to deliver malware distributed into multiple files are presented in [START_REF] Ramilli | Multi-stage delivery of malware[END_REF]. Another method of distributing the malicious payload, presented in [START_REF] Ispoglou | malwash: Washing malware to evade dynamic analysis[END_REF] consists of injecting parts of the payload into clean processes running on a system. This approach makes cleanup more difficult because, if only one injected process is terminated, the malware is capable of reinstantiating itself from another injected process. The distinct malicious processes may communicate using traditional inter process communication, supported by the operating system, or through purposely implemented special mechanisms.

This evasion mechanism is extremely effective especially against detectors based on API or code flow graph. Since the API calls are distributed to multiple distinct processes, this type of detectors may have difficulties in matching the obtained graphs, or may be unable to do so. The effectiveness of distributing malicious behavior to multiple processes is also recognized by [START_REF] Ramilli | Multiprocess malware[END_REF] and [START_REF] Ji | A mulitiprocess mechanism of evading behavior-based bot detection approaches[END_REF].

A solution designed to combat multi-process malware is proposed in [START_REF] Ji | Combating the evasion mechanisms of social bots[END_REF]. In the approach presented by Ji et. al., the actions performed by each process are represented as feature vectors and then correlated with the actions performed by its child processes. The correlation phase in malware detection may be a complex problem, both in terms of implementation and efficiency. Additionally, this solution does not consider code injection when correlating processes.

Evasion mechanisms such as those previously described represent a strong argument to show that behavioral-based security solutions need to evolve past analyzing a single process, individually and in isolation from other entities. Focus should shift to developing more advanced security solutions, capable of analyzing each process in the broader context of all the processes executed on a computing system and taking into account any relations between them.

Proposed Solution

A high level view of the proposed solution, illustrating its major components and the interactions between them is presented in Fig. 1. Our implementation is intended for the Windows Operating System (OS), but the proposed approach may be applied for other operating systems.

The essential requirement for a behavioral detection solution is to monitor the actions performed by processes. This is implemented within the Event Interceptors. They use mechanisms specific to the Windows OS and are located both in Kernel Mode and User Mode (UM). In Kernel Mode, the solution uses a minifilter driver [START_REF]MSDN: File system minifilter drivers[END_REF] that registers callback routines, which are notified whenever changes occur in the file system, registry keys or when processes are created. At User Mode level, the actions are filtered using API interception (hooking) through a DLL injection [START_REF] Blunden | The Rootkit Arsenal: Escape and Evasion in the Dark Corners of the System[END_REF] into the monitored process. The intercepted actions are encapsulated in events and sent to the Behavior Manager, consisting of the Heuristic Engine and the Entity Manager.

The detection is based on behavioral heuristics located in the Heuristic Engine. A heuristic is an algorithm that analyzes the actions performed by processes, using the intercepted events. Some heuristics are defined in signature files and are retrieved by the engine from the Heuristics Database.

The Entity Manager uses information provided by the Event Interceptors, together with information from some heuristics (e.g. for detecting code injection) to manage the processes and groups on a system and their relations.

When a heuristic decides a malicious action has been performed, it sends an alert to the Scoring Engine, where it is evaluated. This component computes scores for the entities that caused the alert and decides whether they are potentially malicious. If a process or group of processes is considered malicious a detection alert will be sent to the Cleanup Module. This module is responsible with taking anti-malware actions against the target entity. The Cleanup Module and the Scoring Engine use the information provided by the Entity Manager in order to identify all the relations between the malicious entities.

In a broader perspective such a solution should be integrated (as a last line of defense) in a modern security application, together with other components such as URL blocking, firewall, classic AV signatures, etc.

The Management of Groups

In order to function effectively, the solution must have a complete overview of the running processes. To accomplish that, the Entity Manager maintains a collection of processes executing on the client system. The Entity Manager dynamically updates this collection to reflect the addition of new processes in response to process creation, and the removal of other processes in response to process termination. The Entity Manager divides the processes in the collection into one or multiple groups and maintains a set of associations indicating the groups each of those process belongs to. An example illustrating multiple groups of processes is presented in Fig. 2.

P1 P5 P6 P7 P8 P14 P15 P2 P9 P11 P10 P12 P3 P13 P4 P14 P15 G1 G2 G3 G4 G5 G6 G7 G8 G9 G10 G11 Fig. 2.

Groups of processes

Categories of Processes. Processes are divided into three distinct categories: group creators -illustrated using triangles, group inheritors -circles and unmonitored processes -squares. By assigning a category -or a role -to each process, the groups of processes are much easier to identify and manage. Smaller groups, consisting of processes that are actually related, can be created, avoiding the creation of a single, large group per system. The category which a process belongs to is identified based on certain features of the respective process. Examples of such features are the file path, the digital signature or a hash computed for the executable file corresponding to the process.

Relations of Processes. The solid arrows indicate process creation, while the dashed arrows indicate code injection. The direction of each arrow indicates the direction of the relationship between the respective entities. For example, process P 6 is a child of process P 5 while process P 7 has injected code into process P 14 . Groups of related processes are represented as dashed lines, encircling those processes, and are denoted as G i , i ∈ {1, 11}. For example, P 1 is the sole member of group G 1 , while G 5 contains processes P 5 . . . P 8 , P 14 and P 15 .

Group creators are processes that are known to create other processes, not necessarily related to them. As their name suggests, whenever a process from this category spawns a process, a new group will be created, initially consisting of the child process. This category includes, among others, winlogon.exe, svchost.exe, cmd.exe and other processes or services of the OS, Windows Explorer, Total Commander and similar file manager applications, Internet Explorer, Firefox, Chrome and other browsers. When a group creator spawns a process a new group is created (e.g. group creator P 1 creates group G 5 when it spawns P 5 ).

Processes that are unmonitored by the security application include the various components of the security solution and certain components of the OS, for example csrss.exe and smss.exe on the Windows OS. These processes are implicitly treated as group creators.

The group inheritor category includes the majority of user processes, as well as processes that are unknown or are not identified as group creators. Whenever a group inheritor spawns a process or injects code into another process, the other process is included in the same group as the group inheritor ( e.g. process P 6 is included in the same group with its parent process, P 5 ; P 14 is included in the same group as process P 7 , as a result of receiving injected code from P 7 ).

The category of a process is updated in response to certain events or when it becomes part of a group. In Fig. 2, process P 14 was initially a group creator, as shown in group G 11 . At a later moment, it received code injected by process P 7 , a member of G 5 . As a result, process P 14 was included in the group of the injector process, G 5 , and was re-marked as a group inheritor.

A process may also simultaneously belong to multiple groups, due to code injection. However, such situations are not so frequent. In the example illustrated in Fig. 2, process P 14 has become a group inheritor and is included in both G 5 and G 11 groups, as described above. When process P 14 -now a group inheritor -spawns the new process P 15 , the latter will be included in both the G 5 and G 11 groups. In other words, changing the category of a process impacts how the processes it spawns or injects code into are handled.

The groups of processes are managed by the Entity Manager, which receives notifications from various Event Interceptors whenever an event related to the life cycle of a process occurs. Process life cycle events consist of process creation, code injection and process termination. If the event indicates the creation of a new process, the Entity Manager determines whether the parent process is a group inheritor or not, in order to assign the newly created process to the appropriate group. If the parent is a group inheritor, the manager will add the child process to the parent's group and will mark it as a group inheritor. Otherwise, the manager determines if the parent process is a group creator. If so, a new group will be created and the child process will be added to that group.

Fig. 3 presents a real-world example using a TrojanSpy.MSIL4 malware. During the two minutes the sample was run, it launched multiple processes, including cmd.exe and reg.exe (used to modify registry). Under normal circumstances, cmd.exe is a group creator, but because the first process in the group is a group inheritor, all its descendant processes become group inheritors.

If the process life cycle event is a code injection, the Entity Manager will determine if it represents a trusted injection. Usually, each code injection event is considered suspicious, possibly indicating a malicious action. However, some processes of the OS may, in some specific situations, legitimately inject code into other processes. These situations should not be considered malicious in order to avoid false positives. The Entity Manager attempts to match the details of the code injection event to a whitelist, containing details of legitimate injections. If the current event is not recognized as a known kind of legitimate injection, the Entity Manager will add the processes receiving the injected code to the group of the process performing the code injection. Then the injected process is marked as a group inheritor, even if initially it was categorized as a group creator.

If the analyzed event indicates the termination of a process, that process is marked as dead. However, it will not be removed from a group until all the other processes in that group have terminated. This strategy will allow a security solution to perform a comprehensive cleanup of the protected system, eliminating even evasive malware that, for instance, only spawn child entities and then exit.

Heuristics

The proposed security solution relies on behavioral heuristics to analyze the actions performed by processes, based on the information provided by Event Interceptors. Whenever a heuristic identifies that a targeted action is being performed, it triggers an alert to the Scoring Engine. Each alert consists of several information about the detected action and the entity that performed it. An alert also has an associated score, that is used to evaluate the potential of a process or group of being malicious.

Some of the actions that can be identified using heuristics are: creating a copy of the original file, hiding a file, injecting code into another process, creating a startup registry key such that the malicious application will be executed after a system restart, deactivating some critical OS functionalities (e.g. Windows Update), terminating critical processes or processes associated with security solutions or modifying an executable file belonging to the OS.

Fig. 4A illustrates a heuristic that listens for events to identify six actions in a certain time order. If these actions are identified, the heuristic will trigger an alert. In the proposed solution the logic of the heuristic is implemented in two ways, as function-callbacks or as heuristic signatures, depending on the com-plexity of the heuristic. In the first case the heuristics are procedures (functions) that are called whenever an event that they registered for occurs. The second one uses signatures to store the logic of simpler heuristics and an engine that tries to match the signatures with the intercepted events. If a heuristic listens for actions performed only by a process it is called process heuristic. If it listens for actions performed by all the processes inside a group it is called group heuristics. An example of group heuristic is illustrated in Fig. 4B. Whenever processes P 1 . . . P 4 perform actions A 1 . . . A 6 in a specific order, such a heuristic will trigger an alert for the group that contains, among others, processes P 1 . . . P 4 . Process creation is illustrated as a zigzagged arrow. The life history of each process is represented as a solid vertical line. For example, process P 1 terminates after it spawns process P 2 . Process P 3 becomes a part of the illustrated group in response to receiving injected code from P 2 . Some actions of the respective processes are not part of the heuristic presented in Fig. 4B, for example the spawning of process P 4 by process P 3 , mainly because they are not invariants between multiple executions.

The sequence of actions A 1 . . . A 6 describes a ransomware attack. Ransomware is a type of malware that encrypts a set of files on the user's computer and demands a ransom payment in order to recover the files. It has become very popular recently among malware authors, because it represents an almost sure source of revenue. In this example, the malicious actions are distributed among a group of processes P 1 . . . P 4 . Each member of the malicious group performs only a small amount of these actions. The actions performed by the ransomware are: A 1 : dropping a copy of itself on disk, A 2 : launching a copy of itself, A 3 : deleting backup (shadow) files, A 4 : injecting code into another process, A 5 : enumerating and encrypting files, A 6 : displaying a message demanding the ransom.

Individually, each action A 1 . . . A 6 may be performed legitimately by a clean application. For example, dropping a copy of itself on disk or launching it (actions A 1 and A 2 ) are commonly performed by installers. Additionally, deleting backup files (action A 3 ) may be performed by certain tools or the Operating System to free disk space. Many clean applications perform code injection (action A 4 ) for various purposes, such as adding functionalities to an existing, previously released product. Most applications for management of media libraries can legitimately enumerate or modify certain files (action A 5 ). Finally, displaying a message to the user (action A 6 ) is specific to almost every GUI application.

An experienced behavior-based detection researcher may observe that a more generic heuristic is possible, that triggers when the group executed the action A 3 or A 4 , but the presented heuristic was extended for the sake of the example. Also, one may observe that the flexibility granted by using such heuristics may allow detecting various versions, variants or an entire class of malware. For example, the heuristic presented in Fig. 4 triggers an alert for the CTB Locker5 sample, whose group is presented in Fig. 5. Regardless of how the actions A 1 . . . A 6 are distributed among processes within the group, if they are executed in the same order as presented in Fig. 4A, the heuristic will trigger an alert on the group. Heuristic's Evaluation. The Scoring Engine receives scoring alerts from the Heuristic Engine whenever a heuristic determines that the occurrence of an event indicates a malicious action. Based on these alerts, the Scoring Engine maintains and updates the aggregated scores for the involved entities, process or group. Depending on the heuristic, the alert can influence the aggregated scores of a single process, of a group of processes or of both types of entities.

Using these scores, the Entity Manager determines whether a malware is present on the client system (e.g. a score threshold is reached). When this happens a detection alert is sent to the Cleanup Module, that will take the actions necessary to remove the malicious component from the system. Using these evaluation methods, even if malicious actions are distributed between several members of a group, and the aggregated scores corresponding to each individual processes are not sufficient to trigger a detection, the group-wide score may exceed the detection threshold. This is very useful for malware such as the Trojan-PSW6 sample, illustrated in Fig. 6. This malware creates many processes from the same executable file, each having different command line arguments, distributing its payload in this way.

Remediation

In order to assure the best protection of a system, once a malicious entity is detected, whether it is a process or group of processes, all traces of that entity must be removed from the system and any changes performed by it must be undone. The Cleanup Module is responsible for taking such actions, based on information received from the Scoring Engine and the Entity Manager. When the module receives the detection alert, it will first identify the process that triggered the detection and determine if it belongs to a single group or to multiple groups. If the suspect process belongs to a single group, the module will proceed to clean the entire group of that process, by applying the appropriate cleanup operation on each member of that group. Cleanup operations usually start with suspending or terminating the execution of the targeted entity. Then, the operation may continue with deleting the disk files that contain the code of that entity and undoing or rolling back a set of changes performed by the respective entity, such as changes to a registry of the OS or to the file system. In some situations, malicious activities may be related to a code injection event. In that case, the Cleanup Module terminates the process that received the injection. Special attention should be given to situations where a malware uses a clean process of the OS to carry out part of a malicious attack through code injection. In this case, the module may terminate the respective clean process, but it should not delete its executable file so that no damages are made to the OS. An example for this case is the ZBot 7 malware, illustrated in Fig. 7, which injects code into multiple clean processes. If the suspect process belongs to multiple groups, the Cleanup Module attempts to identify which of those groups is malicious. For example, it could determine how the suspect process became a member of each group: by process creation or code injection. Next, by identifying which heuristic triggered the detection, the Cleanup Module could determine what action the suspect process has performed. For example, we consider a suspect process that is member of a first group via process creation and a member of a second group via code injection. The Cleanup module will attempt to determine the source of the code that was executing when the scoring alert that caused the detection was triggered. If the alert was triggered while the suspected process was executing code from its main executable module, the Cleanup Module will determine that the first group is malicious. Otherwise, if the injected code was being executed, the Cleanup Module will determine that the second group is the malicious one. If the malicious group is successfully identified, the module will proceed with cleaning 7 MD5 hash: 0x43A6DD7D5BE93F4E5224940C67E40FF8 that group. Otherwise, it will only clean the suspect process, to prevent potential data loss for the user in case of a false positive detection.

Technical Results

When evaluating a security solution the detection rate, false positive rate and performance impact are the most important criteria to be considered. A good security solution must have a high detection rate, a low false positive rate and unnoticeable performance impact.

Detection Tests

A comparison between the detection rate of the group based approach and a non group based solution is presented. The detection tests were performed in a virtual environment consisting of machines running Windows 8.1. Each sample was run for two minutes in the virtual machine, then the results were collected and the execution was ended. For false positives tests, each sample was run for ten minutes in the virtual machine before terminating the execution.

For the detection test, two malware collections were used, the first consisting of ransomware that were collected in November 2016, while the other contains malware samples collected from various sources like: honeypots, spam email attachments, infected WEB sites and URLs used to spread malware in November 2016. The clean samples (for the false positive test) are popular applications used in 2016. Table 1 shows that the detection was improved for both collections with 10.61% and 5.16% . This shows that at least 5% of the malware in both collections are multi-component or multi-process, thus proving the need of changing the detection approach to a group based solution. This amount may not seem much at first glance, but such small differences make the distinction between an average security solutions and a good, competitive one.

The results of the false positives test, presented in Table 2, show that the number of false positives does not change when augmenting the security solution with group awareness. This is due to the fact that the groups generated for legitimate applications usually contained a small number of processes with few triggered heuristics.

Limitations of the Solution

The implementation of the solution involves maintaining in memory a set of information associated to each process in a group until the group is terminated.

For some samples, such as the TrojanSpy.MSIL sample the memory requirements are high. This can be prevented by detecting the sample before the process group too many processes or for clean processes, by simply making that process a group creator. Clean processes are added to malware groups because malware use such processes to perform different actions (e.g. reg.exe to access the registry). This problem indicates that a whitelist is needed, that will be consulted when cleaning the infected system to prevent any data loss for the user or producing any damages to the Operating System.

The solution can only detect samples which interact on the current machine. If by some means a process uses an external (i.e. not on the same machine) communication channel to force the creation of another process on the original machine the Entity Manager can not link the parent with the child and it is not able to create the group correctly.

Finally the solution is limited by the platform it runs on. Because Windows does not keep a strict relation between child processes and parent processes, managing groups can prove to be difficult, requiring OS specific knowledge. Furthermore, because Windows allows code to be injected in a trivial way and does not provide a synchronous notification for when injections occur, detecting all code injection methods is also considerably hard. The proposed solution attempts to solve this issue by identifying the most common methods for injecting code through dedicated heuristics.

Conclusions

We highlighted the problem of evasive, multi-process malware and proposed shifting the focus from evaluating the behavior of individual processes to evaluating and correlating the actions of related processes. We presented real-world malware samples, in order to better exemplify the behavior of multi-process malware. The proposed solution detected all these samples and constructed their groups correctly.

We described how groups of related processes are constructed, by dividing the processes into creators and inheritors. We presented the way groups are influenced by process creation and code injection events. We introduced groupbased behavioral heuristics, described how the behavior of processes and groups is evaluated and how detected entities can be cleaned.

A major contribution of our solution is that it automatically correlates the behavior of individual processes within a group, thus eliminating the need for a distinct correlation phase, as presented in [START_REF] Ji | Combating the evasion mechanisms of social bots[END_REF], which is both costly and complex. As a result, the heuristics are easier to develop, the evaluation is more straightforward and cleanup is better performed.

We implemented the presented concepts into a behavior-based solution and compared this approach to a non-group solution. The improvement was quite consistent: the detection rate was increased with over 10% for the ransomware samples test, a type of malware known to be highly evasive (multi-process).

Fig. 4 .

 4 Fig. 4. Heuristic's Logic Example

Fig. 5 .

 5 Fig. 5. CTB Locker ransomware

Fig. 6 .

 6 Fig. 6. Trojan-PSW malware

Fig. 7 .

 7 Fig. 7. ZBot malware

Table 1 .

 1 Malware detection test

	Samples	Detected (no groups)	Detected (no groups)[%]	Detected (with groups)	Detected (with groups)[%]
	47933 37054	77.3%	42142	87.91%
	16490 13084	79.34%	13935	84.5%

Table 2 .

 2 False positive test

	Samples	Detected (no groups)	Detected (no groups)[%]	Detected (with groups)	Detected (with groups)[%]
	1128	10	0.88%	10	0.88%

MD5 hash: 0x143FCC07CEB0F779FF1E204CEF4A20D6

MD5 hash: 0x82F941FBD483E0684DAED99F006488F1

MD5 hash: 0x609614B508622E90EEEDAA875226FEA4