On the Security of Machine Learning in Malware C&C Detection: A Survey <s> Affected algorithms. <s> Clustering algorithms have been increasingly adopted in security applications to spot dangerous or illicit activities. However, they have not been originally devised to deal with deliberate attack attempts that may aim to subvert the clustering process itself. Whether clustering can be safely adopted in such settings remains thus questionable. In this work we propose a general framework that allows one to identify potential attacks against clustering algorithms, and to evaluate their impact, by making specific assumptions on the adversary's goal, knowledge of the attacked system, and capabilities of manipulating the input data. We show that an attacker may significantly poison the whole clustering process by adding a relatively small percentage of attack samples to the input data, and that some attack samples may be obfuscated to be hidden within some existing clusters. We present a case study on single-linkage hierarchical clustering, and report experiments on clustering of malware samples and handwritten digits. <s> BIB001 </s> On the Security of Machine Learning in Malware C&C Detection: A Survey <s> Affected algorithms. <s> Clustering algorithms have become a popular tool in computer security to analyze the behavior of malware variants, identify novel malware families, and generate signatures for antivirus systems. However, the suitability of clustering algorithms for security-sensitive settings has been recently questioned by showing that they can be significantly compromised if an attacker can exercise some control over the input data. In this paper, we revisit this problem by focusing on behavioral malware clustering approaches, and investigate whether and to what extent an attacker may be able to subvert these approaches through a careful injection of samples with poisoning behavior. To this end, we present a case study on Malheur, an open-source tool for behavioral malware clustering. Our experiments not only demonstrate that this tool is vulnerable to poisoning attacks, but also that it can be significantly compromised even if the attacker can only inject a very small percentage of attacks into the input data. As a remedy, we discuss possible countermeasures and highlight the need for more secure clustering algorithms. <s> BIB002 </s> On the Security of Machine Learning in Malware C&C Detection: A Survey <s> Affected algorithms. <s> Clustering algorithms are largely adopted in security applications as a vehicle to detect malicious activities, although few attention has been paid on preventing deliberate attacks from subverting the clustering process itself. Recent work has introduced a methodology for the security analysis of data clustering in adversarial settings, aimed to identify potential attacks against clustering algorithms and to evaluate their impact. The authors have shown that single-linkage hierarchical clustering can be severely affected by the presence of a very small fraction of carefully-crafted poisoning attacks into the input data, highlighting that the clustering algorithm may be itself the weakest link in a security system. In this paper, we extend this analysis to the case of complete-linkage hierarchical clustering by devising an ad hoc poisoning attack. We verify its effectiveness on artificial data and on application examples related to the clustering of malware and handwritten digits. <s> BIB003
The attack has been demonstrated against variant of the hierarchical clustering algorithm. The attack should be effective against any clustering algorithm that uses the intercluster distance. The attack may have an effect against centroid-based algorithms such as k-means clustering, although to a lesser extent. The introduction of points between clusters will have an effect on the final placement of centroids, which could cause points to be clustered with points with which they would not have previously been clustered. The clusters are unlikely to merge (depending on the structure of the data and initial location of the centroids), but if the attack points are chosen carefully, the attack points could cause clusters to merge. Demonstrated attacks. The Malheur system is the target of work by BIB002 . Malheur  ] applies single-(or complete)-linkage hierarchical clustering to MIST malware behavior reports, which contain sequences of host-based system events, where individual execution flows of threads and processes are grouped in a single, sequential report. The paper assumes the scenario in which the attacker has PK and reduces the attack to an optimization problem, in which the objective function to be maximized is the distance of the clusters formed when under attack from the clusters formed in absence of the attack. The attack goal is to cause clusters to merge until the system becomes unusable. The attack is run on a local version of the system, where all possible attack points are considered, and only the one that has the largest impact is used. The attack is applied iteratively, continuously adding points until the objective function is maximized. The attacks also propose two variations that are less computationally expensive, as they instead estimate the effect of the attack points rather than re-run the clustering algorithm. To generate attack samples, an existing malware sample is taken and features are manipulated by increasing their value (to maintain the malicious capability of the samples). When tested on two datasets, the same dataset used in the original Malheur paper and a new malware dataset collected by the authors, the bridge attack is able to reduce the number of clusters from 40 to 5 with only 2% of injected samples. The estimation-based approaches require more injected samples but are far less computationally expensive. To verify the results, two random-based attacks (one that generates an attack point at random and one that chooses the best of several random attack points) are shown to be ineffective. Finally, an attack that works as the bridge attack but minimizes the F-measure achieves comparable results to the bridge attack. Very similar attacks are applied to three different datasets in BIB001 : the banana-shaped dataset from PRTOOLS, a malware C&C dataset, and a dataset of handwritten digits. As before, PK on behalf on the attacker is assumed. The attack aims to cause clusters to split or merge to impact on the availability of the algorithm. The attacks are compared against a random approach. On the banana-shaped dataset, the bridge attacks are found to outperform the random attacks. The best approach results in a lower number of final clusters than in the unpoisoned dataset. On the malware dataset, the results are similar. On the digits dataset, the random approaches are shown to be ineffective. The three bridge-based approaches cause significant fragmentation of the final clusters. Attack limitations. To achieve maximum results, the attack requires PK of the target classifier, which can be an unrealistic assumption in the real world. The attack could still be successful if a surrogate dataset is used to approximate the target classifier, although this has not been explored in the literature. The attacker only requires knowledge of one other cluster to perform the bridge attack. This cluster could be estimated with a high accuracy (e.g., the traffic to "facebook.com" will be similar wherever it appears and thus may be reliably estimated). 6.4.2. Gradient Descent Attacks. As with classifiers, gradient descent poisoning attacks on clustering algorithms are causative availability attacks. In the clustering case, attack points are inserted to cause clusters to split and possibly merge with others, reducing the accuracy the clustering. Attack points are created and the most effective points are found by maximizing the objective function using a gradient descent approach. Affected algorithms. This class of attack has been demonstrated against hierarchical clustering. As this type of attack exploits the distance function used within the clustering algorithms, it is theoretically applicable to other types of clustering, such as k-means. However, whereas a single attack point can be sufficient to cause a cluster to split in algorithms that use intracluster distance (e.g., hierarchical clustering), to cause a split in centroid-based algorithms would likely require a larger number of attack points to significantly shift the centroids, causing changes to the generated clusters. Demonstrated attacks. The complete-linkage variant of hierarchical clustering is also attacked by BIB003 . The attack is again a poisoning attack with PK on behalf of the attacker. In this attack, attack points are added to the edge of clusters with a goal of causing the cluster to split, and possibly merge with another. As before, the attack is run iteratively with the goal of maximizing the objective function (which represents the distance between the clustering output under attack compared to not under attack). There are also two variants that use estimation to reduce the number of iterations required. This attack is tested against three datasets (taken from BIB001 ). In the first, taken from PRTools, the extend attack causes the clustering to result in a smaller number of more distinct clusters. The second dataset, which contains malware C&C behavior represented by six features, gives similar results. Finally, a dataset of handwritten digits, represented by 28 × 28 greyscale images converted into 784 dimensional data, is used. In this case, the estimation attacks are more effective than the fully iterative attack.