Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> Splitting the search space <s> A common task in signal processing is the estimation of the parameters of a probability distribution function. Perhaps the most frequently encountered estimation problem is the estimation of the mean of a signal in noise. In many parameter estimation problems the situation is more complicated because direct access to the data necessary to estimate the parameters is impossible, or some of the data are missing. Such difficulties arise when an outcome is a result of an accumulation of simpler outcomes, or when outcomes are clumped together, for example, in a binning or histogram operation. There may also be data dropouts or clustering in such a way that the number of underlying data points is unknown (censoring and/or truncation). The EM (expectation-maximization) algorithm is ideally suited to problems of this sort, in that it produces maximum-likelihood (ML) estimates of parameters when there is a many-to-one mapping from an underlying distribution to the distribution governing the observation. The EM algorithm is presented at a level suitable for signal processing practitioners who have had some exposure to estimation theory. <s> BIB001 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> Splitting the search space <s> We present DNADroid, a tool that detects Android application copying, or “cloning”, by robustly computing the similarity between two applications. DNADroid achieves this by comparing program dependency graphs between methods in candidate applications. Using DNADroid, we found at least 141 applications that have been the victims of cloning, some as many as seven times. DNADroid has a very low false positive rate — we manually confirmed that all the applications detected are indeed clones by either visual or behavioral similarity. We present several case studies that give insight into why applications are cloned, including localization and redirecting ad revenue. We describe a case of malware being added to an application and show how DNADroid was able to detect two variants of the same malware. Lastly, we offer examples of an open source cracking tool being used in the wild. <s> BIB002
Because of time and computing resources constraints, it is virtually infeasible to perform pairwise comparisons for all possible app combinations in a dataset such as AndroZoo. Instead, we propose to rely on a clustering-based approach to split the search space, so as to focus on comparing only likely similar apps. As illustrated in Fig. 3 , this phase is actually made up of three steps: • Step (1): Feature Extraction. We abstract each app into a representative feature vector. To ensure processing speed, we focus on features that are easily extractable from an APK file. Those include class names, declared permissions, declared actions and intent-filters. These features will prevent for example from regrouping a game app with a messenger app and will ensure that similar apps are included together in the same cluster. • Step (2): EM Clustering. We leverage the Expectation Maximization (EM) algorithm BIB001 to regroup the AndroZoo apps into different clusters. EM is preferred to other popular clustering algorithms, such as K-mean, because it does not require to be parameterised with the number of clusters that should be produced. • Step (3): Candidate Pairing. At the end of this phase, we consider the set of apps in each cluster and form candidate combinations of repackaging pairs. Given two apps in a cluster, the candidate pair is formed by considering the one created before (based on the creation time of the DEX file) as the original app while the remaining one as the repackaged version. Because we Step (1), BIB002 , and (3) for Splitting the Search Space. Step (4) for Fast, Approximate, Brute-force Similarity Comparison. consider repackaging to be mostly a parasite activity, we drop candidate pairs where the apps have been signed with the same developer certificate. Indeed, apps that are signed by the same certificate are usually considered to be app variants of a same company or app versions of the same app, which are unlikely to be repackaged versions.