# Malware Collusion Attack against SVM: Issues and Countermeasures
## 3 Motivation
### Collusion Apps to Evade SVM Detection
#### 3.3.2 Collusion Attack on SVM  
In Section 3.2, we have introduced a general idea of how to make collusion apps. Since we did not have the source codes of the malware samples in our data set, we cannot separate the malware into collusion apps manually from the source codes. Thus, we try to conduct Collusion Attack by simulation. From Section 3.3.1, we know that all the test apps will be mapped as a d-dimensional feature vector \(x\)Thus, to simulate collusion apps is equivalent to simulating the feature vector of these collusion apps. In order to separate the function of original malware into two apps, we can simulate this separation by splitting its feature vector into two sets. The problem is that the two simulated split apps may not be able to run properly, as the apps require some basic API calls to run, such as _com.android.Activity: void onCreate()_ etc. Thus, we wrote a blank template app that contained all the necessary APIs. Then, we combined the split feature with the features of the blank template app; we could obtain runnable apps. In addition, the split feature set could have overlap features so that the simulated split apps can be closer to reality. We assume that the collusion attackers have perfect knowledge of the SVM classification model so that they can maximize the effect of Collusion Attack. This assumption can illuminate the worst case of this collusion problem. We referred to the two split feature sets as \(A\) and \(B\), and the split apps as \(App_{A}\) and \(App_{B}\), respectively. Then, our splitting problem could be formulated as finding a split strategy \(S\) that could split the complete feature set \(F\) into two sets \(A\) and \(B\) to minimize the probability of labeling \(App_{A}\) and \(App_{B}\) as malicious by our pre-trained detection model. The split problem can be formulated as:  
\[S^{*}=argmax_{x}g(s)=\frac{|F(M_{\phi_{A}(s)})\bigcap F(M_{\phi_{B}(s)})|}{|M| }, \tag{2}\]  
where \(M\) is malware test set; \(|M|\) represents the number of malware in the data set; \(F(x)\) is the app set where app \(x\) is false labeled; and \(\phi_{A}(x)\) is a function that maps from individual \(x\) to features that belongs to set \(A\). The optimal split strategy is to find a strategy \(S^{*}\) to maximize \(g(\cdot)\). This problem is a discrete optimal problem [24]. An evolution algorithm would be a suitable solution to it. Thus, we employ a Genetic Algorithm. A genetic algorithm is often used to generate high-quality solutions to optimization and search problems. It has a standard workflow and usually starts from a population of randomly generated individuals. It is an iterative process, with the population in each iteration called a generation. In each generation, the fitness of every individual in the population is evaluated; after mutation and crossover of each, it forms a new generation. The new generation is then used in the next iteration of the algorithm. The algorithm usually terminates when a maximum number of generations has been produced. A typical genetic algorithm requires: (1) a genetic representation of the solution also called Individual; (2) a fitness function to evaluate the solutions. Thus, we defined the individual, fitness function and the other parameters as follows, to apply the algorithm to our problem. **Individual** When splitting the features, for every single feature, it can be split into set \(A\), \(B\) or both \(A\) and \(B\). As a result, for every feature \(x\), there are three possible values, as shown in Equation (3). Individual consists of all the features, and can be formulated as Equation (4). It means that Individual is defined as an integer list that contains all the features. The value of \(i_{th}\) item in the list represents the \(i_{th}\) feature should be split into set A, B or both:  
\[x=\left\{ \begin{array}{ll}0&x\in A,\\ 1&x\in B,\\ 2&x\in A\bigcap B,\end{array} \right. \tag{3}\]  
\[Ind=x_{0}x_{1}\cdots x_{n}, \tag{4}\]  
where \(n\) is the number of features.