dataesr/scientific-paragraphs-categorization huggingface dataset:
In this article, we describe a semi-supervised system for the analysis of massive datasets of malicious applications. We created a platform able to suggest new families of applications to human experts; the platform also generates an intelligible YARA rule  [14]  to identify family members with high precision. We explicitly minimize false positives, a business hazard and a reputation blow for AV vendors. The approach alleviates human experts from the burden of manually inspecting thousands of Android applications, while letting them take critical decisions. The main contributions of this article can be summarized as: • We introduce a scalable system for the analysis of massive Android malware datasets based on careful feature engineering, and a standard clustering algorithm. The mechanism is demonstrated to be robust and able to overcome the well-known limitations of traditional signature-matching mechanisms.
• We propose an algorithm that, starting from a cluster of samples, generates its family signature as a YARA rule. Thanks to exact and heuristic evaluations, such rules are intelligible and appear reasonable to human experts. Moreover, the algorithm guarantees zero false positives in the existing dataset, and limits the possibility of false positives in the future. • We report experiments on a dataset of about 1. 5 million Android applications, and results show the scalability of the approach. We use a set of internal and external indicators to demonstrate that the proposed system performs an accurate and efficient automatic identification of groups of similar applications. By exploiting limited data, the framework is able to propose insightful extensions to the rule detecting suspicious applications.
III. KOODOUS Koodous is a collaborative platform for researching on Android malware that combines online analysis tools with social interactions between the analysts. Started in 2014, in 4 years it collected one of the largest repositories of Android applications: its databases contain more than 30 millions of applications, among which 7 millions have already been identified as malicious. Fig. 1  illustrates the trend of application submission and detection from October 2014, until March 2017. Koodous provides both analysis service and end-point protection: upon submission, each application is analyzed both statically and dynamically, and the final report is accessible through a web interface specifically designed to help analysts detect new malware threats. Analysis tools include a custom version of Androguard  [15] , CuckooDroid 2  and DroidBox  [16].
A. ITERATIVE CLUSTERING Clustering provides a mechanism to automatically categorize applications into groups that reflect their similarity, both in source code and runtime behavior. We exploit HDBSCAN, a density-based algorithm, as it fits most of our requirements. Density-based clustering algorithms locate high-density regions in the feature space; DBSCAN (density-based spatial clustering of applications with noise) is probably the best known among them  [17]. Density-based algorithms can effectively discover clusters of arbitrary shape and filter out outliers, eventually increasing cluster homogeneity. Additionally, the number of expected clusters to be found in the data is not required: our aim is to discover groups of similar applications without any prior knowledge about their composition, otherwise the number of clusters is hard to guess a priori.
In 2013, Campello et al. [18]  proposed HDBSCAN, a new density-based algorithm that converts the original DBSCAN into a hierarchical clustering algorithm. As a matter of fact, HDBSCAN find clusters of varying densities, and is more robust to parameter selection. Moreover, it supports the GLOSH (global-local outlier score from hierarchies) outlier detection algorithm: during the fitting phase, each data point is associated to a score that represents its likelihood of being an outlier; at the end of the process, outliers are selected via upper quantiles  [19]. In low-dimensional spaces, HDBSCAN has an average complexity of approximately O(n log n), while its space requirement is O(n), making it applicable to moderately large datasets  [20]. As the number of samples in malware datasets is in the tens of millions, we exploit an iterative process where the original dataset D is divided into m chunks d i of fixed size N (m = |D| N ).
D = m-1 i=0 d i (1) The parameter N balances the quality of the results with the time required for the analysis, and can be set experimentally according to the available resources. HDBSCAN is applied to each chunk of data d i finding, at each step, a set of clusters c i and a set of outliers o i. Finally, all the outliers O = m-1 i=0 o i , are clustered together in order to find even those small groups of applications whose samples are spread through several chunks of data. In the end, the total number of required iterations is equal to m + 1. Since HDBSCAN could be executed in parallel on the first m chunks, the benefit of the iterative approach is the huge reduction in the time required for the analysis. On the other hand, few applications could be misclassified as outliers and the same group of similar applications could be found multiple times, although, as shown in section IV-B, those corner cases do not limit the framework efficacy.
g. , number of DNS resolved, HTTP requests). These are the standard type of information extracted in the field of malware analysis. Because the range of each feature is quite different, the dataset is firstly normalized so that the features have mean equal to zero and variance equal to one. Since the choice of the distance to use during cluster analysis is tied to the type and the dimension of selected features, we experimentally found that the combination with the Euclidean distance delivered the best performances. composed of strongly related applications. In some cases, by combining this result with the information already available in Koodous, these families may be automatically labeled, as they extend either known threats or legitimate software. In the other cases, experts are required to manually evaluate the family, but they need to analyze only few representative samples of the group and not all applications, therefore drastically reducing the time required by the analysis.
C. FAMILY SIGNATURES GENERATION In the last step of our framework, a signature is generated for each family that has been identified as malicious. 5 We developed an automatic procedure that starts from a set of applications, and eventually produces a YARA rule describing them. The program has no requirements on the origin of the set: it could be the result of automatic clustering or manual selection, although the more the applications in the set are related, the better the result. Authoring an effective signature requires a considerable effort and experience. Good signatures are compact, and they have the ability to generalize, that is, to identify all known variants of the malware and even possible new ones. Moreover, they do not yield false-positive results by detecting non-family members, and finally, they appear intelligible to human experts and are almost self-explanatory.
5 Our system could generate family signatures of legitimate applications as well, but they would be of no use for Koodous 59544 VOLUME 6, 2018 More formally, a signature S is the disjunction of n clauses S = n i=0 c i. A clause c i is a finite conjunction of m i literals c i = m i k=0 l k i. In the present context, a literal l k i is a single feature specified in the report resulting from the analysis of the application. Traditionally, a YARA rule is defined on unique strings found in malware but not present in legitimate programs; quite differently, we generate precise, descriptive rules using the structural properties extracted by the static and dynamic analyses. Our program identifies an optimal set of clauses for matching all target applications while yielding no false positive in the current database; moreover, thanks to some heuristics, the rule has a good ability to generalize, a low risk of detecting false positives in the future, and it appears reasonable to the eye of the human experts.
An example of an automatically generated YARA rule for the Syringe malware family is shown below. 6. It may be noted that the statistical features exploited during clustering (Section IV-A) are not used in the in the rule, as they would result in over-complicated rules hardly understandable by humans. rule YaYaSyringe { condition: androguard. filter(''action. BATTERYCHECK'') and androguard. number_of_services == 3 and androguard. permission(''SYSTEM_ALERT_WINDOW'') and androguard. url(''http://s. adslinkup. com/v2''). } The process is performed in three steps: a reasonable signature composed of a small number of clauses is generated; the signature is checked against the full database of applications, and false positives are identified; the generation procedure is run again, but explicitly taking into consideration the false positives discovered in the second step.
Fig. 3  exemplifies the idea of the process of generation of a signature for two malware m a and m b , and two legitimate applications g a and g b. In the first phase, the algorithm defines a signature Y = r, where r is a single clause composed by the common features between the two malware: r = m a ∩ m b. Indeed, a rule Y detects an application m only if Y is a subset of m: Y ⊆ m. During the second phase, the rule Y is checked against the complete database, where it generates two false positives matching two legitimate applications g a and g b. The clause r is therefore too generic to be used as a signature. As it is not possible to find features common to malware that do not matches legitimate applications (m a ∩m b )\g a = ∅ and (m a ∩ m b ) \ g b = ∅, the third step generates a signature with the disjunction of two clauses Y * = (r ∧ r a ) ∨ (r ∧ r b ).
V. CASE STUDY As a case study we used a dataset of 1. 5 million Android applications collected over the 2016. The dataset is recent and diverse in the set of attack vectors it represents: in order to have the same ratio between detected and undetected applications as in Koodous, we sampled a subset of 1 million apps. 9 s result, the dataset under analysis is composed by 65% undetected applications, 31% detected by signatures, and 4% detected through triage only.
A. EVALUATING CLUSTERING RESULTS HDBSCAN has two parameters that mostly influence the results of the clustering: min cluster size (mss) determines the smallest size of a cluster, while min samples (ms) how conservative are the results. A higher value of min samples restricts clusters to more dense areas, but it also increases the number of outliers. We use mss = 3 and ms = 1; in other words, we considered only malware clusters containing a minimum of three samples as representative of a malware family. We used a high-performance, open-source implementation of HDBSCAN in Python from Leland McInnes  [21]. All experiments were performed on a 6-core Intel Xeon (CPU E5-1650 v2 @ 3. 50GHz), with 128 GB of RAM, although HDBSCAN only used up to four cores and 6 GB of RAM in each run. The quality of the clustering results is evaluated as a measure of the ability of correctly extending malware detection to undetected applications.
2) EVALUATION OF MALWARE DETECTION EXTENSION Aiming at evaluating the detection extension performance in a real-world case, we evaluate how the proposed system is accurate in relationship to the information of the detections availavable in VirusTotal. We choose VirusTotal as a well-known and trustworthy source of information about existing threats since it collects the detection results from tens of independent AV companies. Moreover, recently other researches used the same metric  [25]. TABLE 6. Comparison of the detection results between VirusTotal and two datasets of 50,000 applications, respectively undetected (und. ) and detected (det. ) by Koodous. Columns indicate the number of applications unknown (unk. ), undetected (und. ), detected by at least one AV (det. ), and detected by more than three AVs, as reported by VirusTotal.
In order to evaluate the detection extension results, we firstly assessed how precisely Koodous detects malware samples, and how effectively covers all the malware variants. Starting from two randomly sampled subsets of 50,000 applications, respectively originally undetected and detected in Koodous, we cross-checked their maliciousness using VirusTotal. Results are illustrated in Table  6. The first line of the table (Koodous det. ) shows that among detected applications, Koodous has 100% of precision, and very high recall (99. 8%), as almost all Koodous detected applications are completely identified as malware by traditional AVs too, while only 100 applications (the 0. 2% of the dataset) are unknown or undetected by VirusTotal. However, the second line of the table (Koodous und. ) shows a very low accuracy (27.
As shown in Table  12 , the time required to generate a rule for few hundreds malware is always less than a minute, although when the target increases to a few thousands applications, the time required grows up to several minutes, as the most expensive part of the process is the check for false positives against a reference dataset. This is not considered a limitation, since all the process is automatic, and given the goodness of the results, it is of invaluable support for the family signature generation process. Table  12  reports the number of literals (i. e. , application features) and the final score for each generated YARA rule: referring to Section IV-C, each score is higher than the minimum threshold T min = 400, satisfying the minimum 15 Example rulesets could be found at the following address: https:// koodous.
16 https://koodous. com/my_rulesets/3466 Neither Lee and Mody  [26] , nor Bailey et al. [27]  have any specific solution to large-scale clustering. On the other hand, Bayer et al. [13] , Rieck et al. [28] , and Jang et al. [12]  directly address the problem of managing large datasets, developing methods to scale the clustering process. Bayer et al. [13]  propose a scalable malware clustering approach using a combination of approximate and hierarchical clustering with Local Sensitive Hashing (LSH)  [29]  to significantly reduce the number of distance computations. By extending Anubis  [30] , they are able to extract detailed behavioral-reports based on taint tracking results and network captures from malware execution. In particular, the taint engine allows them to map low-level operations (e.
While the underlying idea of a multi-step clustering refinement process is quite interesting, this practically results in the biggest limitation to the scalability of their work. Moreover, Perdisci et al. limit behavioral analysis to HTTP-based malware only, which in practice can be easily bypassed by using an encrypted protocol (e. g. , HTTPS). In 2013 Hu et. al  [10]  present MutantX-S, focusing on malware comparison and triage on a large scale. Their system falls into the static-analysis category, since it relies on features extracted from the malware instructions. MutantX-S can efficiently cluster a large number of samples into families based on program static features, by extracting N-gram features directly from the x86 opcode sequences and exploiting a feature hashing technique to reduce features dimensionality, thus  VOLUME 6, 2018  significantly lowering the memory requirement and computation costs.
MutantX-S adopts the same prototype-based algorithm of  [31]  because of its efficiency and explicit expression of malware features. In the Android context, ClusTheDroid  [33]  is the first research to combine behavioral analysis and clustering to specifically target Android malware. The goal is both to develop a tool, and to evaluate clustering alternatives. Finally they focused on single and complete linkage HAC, using a feature set composed of 38 numerical quantities extracted from the CopperDroid  [34]  report, and weighted according to a three-level interpretation of malware behaviors. Differently from most of the previous works  [5] ,  [11] ,  [13] ,  [27] ,  [33]  that rely on the HAC algorithm (which is both computationally and storage expensive, O(n 2 log n) and O(n 2 )  [35] ), we use HDBSCAN, that with N data points has an average complexity approximately O(N log N )  [20] , and a space requirement O(n), making it applicable to large datasets.
Moreover, different AV products apply different criteria and granularity to rule generation, resulting in inconsistent results. Despite the complexity and intrinsic challenges of the procedure, given the importance of automatically building a malware reference dataset to evaluate clustering results, the problem was directly tackled in different researches, such as VAMO  [38]  and AVclass  [23]. In the literature of malware clustering, several techniques are proposed. Bayer et al. [13]  and Jang et al. [12]  use precision and recall to compare the results of their system-level behavioral clustering to a reference dataset, defining a manual mapping between labels assigned by different AVs. However, as the dataset size increase this method becomes hardly sustainable and quite costly. Similarly, ClusTheDroid  [33]  used a reference set developed through manual analysis  [39].
On the other hand, Apel et al. [5]  choose to take into consideration the amount of ''shared behaviour'' that can be found among different analysis traces within the same cluster of applications. In practice, each system call is modeled as a single character, and the evaluation is computed in linear time finding all substrings in a generalized suffix tree, using the algorithm described in  [40]. The main limitation of this technique is related to the choice of the reference dataset, since Apel et al. use an artificial dataset starting from three real-world malware traces, then divided into blocks of system calls and randomly permutated. Differently, Perdisci et al. [11]  tackle the problem by measuring the cohesion and separation of each cluster, in terms of agreement between labels assigned by cluster and multiple AV scanners.
Polygraph is tested against three real-world exploits and is able to successfully generate HTTP and DNS signatures with a low false positive rate. Perdisci et al. [11]  also tackles the problem of automatically generate network signatures for cluster centroids, with the aim of deploying them into an IDS at the edge of a network in order to detect malicious HTTP traffic. Since malware samples may contact legitimate websites for malicious purposes, instead of pre-filtering HTTP traffic against legitimate websites, authors apply a pruning process by testing the signature set against a large dataset of legitimate traffic, while discarding signatures that generate false positives, although such an approach is as effective as it is the legitimate traffic available. In the Android context, Faruki et al.
[54]  propose AndroSimilar, a statistical signature-based solution that generates variable-length signatures for the application under test and identifies malware on the basis of a similarity percentage with a dataset of known malicious samples. Another approach is presented in DroidAnalytics  [55] , a signature-based analytic system, which extracts and analyzes applications at opcode level. Firstly, a three-level signature (i. e. , methods, classes, application) is generated by combining the API call traces, then the malware is associated to a family according to its malicious content. While  [54]  shows robustness against control-flow obfuscation, junk method insertion and string encryption,  [55]  could fail in the detection of repackaged malware. On the the other hand, both solutions are affected by a high false-positive rate due to the wrong choice of signature patterns available in both malicious and benign applications.
Since the release of YARA  [56] , a patten-matching language designed to help to identify and classify malware samples, a few automatic tools have been proposed to generate malware signatures which balance the required generality to catch future samples with the need of avoiding false positives detections. In 2013, Chris Clark develops YaraGenerator,  19  a python program which automatically generates YARA rules by sampling a small subset of common strings between malware, while blacklisting goodware ones. Although the tool is designed to work with any type of malicious file, in order to increase the efficacy of the results, specific dataset of goodware strings are available for several file formats (e. g. , Windows executable, PDF, email and office document). Similarly, yarGen 20  is a python tool developed by Florian Roth to automatically generate YARA rules by combining the topmost malware strings, while removing those that also appear in goodware files.
By using fuzzy regular expressions, each malware string is assigned a score proportionally to the inverse of its frequency, and the ''Gibberish Detector'' allows to select real language over character chains without any meaning. The tool also exploits a naive-bayes-classifier to classify candidate strings, avoiding compression or encryption garbage in favor of more generic strings. Finally, each rule is created by combining the 20 strings with the highest score. The result of the generation process may be a single rule, specific to one sample, or a super rule, catching malware variants and groups. While both YaraGenerator and yarGen have been developed aiming at supporting the rule creation, rather then completely replacing the role of expert analysts, as a major drawback, their efficacy strongly relies on the completeness of the dataset of goodware strings.
VII. LIMITATIONS A major limiting factor of the described semi-supervised approach is represented by the ability to extract meaningful information from the applications under analysis. Indeed, the accuracy of the analysis directly affects the clustering results and the automatic rule generation process. The Android platform lacks of mature reverse engineering tools compared to the ones used for x86 malware  [57]. Since each malware is different, automatically finding the malicious code by means of static analysis is difficult, because it is mixed with benign code; moreover dynamic code loading and reflections make the analysis even harder. Unfortunately, most malware include trigger-based anti-analysis techniques that delay or hide their malicious activities at the first application run or in an emulated environment.
IX. CONCLUSION In this paper, we introduced a set of semi-supervised techniques with the ultimate goal of assisting human experts in the generation of malware family signatures. As a result, we developed a scalable framework able to dig into massive datasets of Android applications with the main purpose of identifying new malware samples, while reducing false positive detections. Our study shows that combining the scalability of the automatic techniques with the inherent flexibility of the manual analysis, achieves the best performances. Eventually, the proposed approach introduces two essential automation improvements in a well known and tested AVs standard detection mechanism based on signatures. An iterative clustering algorithm allows for easy identification of hard to find potential threats, reducing the human intervention from the manual analysis of thousands of applications to the validation of a much smaller number of clusters where applications reflect a similar class of behavior.