Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> RELATED WORK <s> This paper describes how a program called dup can be used to locate instances of duplication or near-duplication in a software system. Dup reports both textually identical sections of code and sections that are the same textually except for systematic substitution of one set of variable names and constants for another. Further processing locates longer sections of code that are the same except for other small modifications. Experimental results from running dup on millions of lines from two large software systems show dup to be both effective at locating duplication and fast. Applications could include identifying sections of code that should be replaced by procedures, elimination of duplication during reengineering of the system, redocumentation to include references to copies, and debugging. <s> BIB001 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> RELATED WORK <s> Existing research suggests that a considerable fraction (5-10%) of the source code of large scale computer programs is duplicate code ("clones"). Detection and removal of such clones promises decreased software maintenance costs of possibly the same magnitude. Previous work was limited to detection of either near misses differing only in single lexems, or near misses only between complete functions. The paper presents simple and practical methods for detecting exact and near miss clones over arbitrary program fragments in program source code by using abstract syntax trees. Previous work also did not suggest practical means for removing detected clones. Since our methods operate in terms of the program structure, clones could be removed by mechanical methods producing in-lined procedures or standard preprocessor macros. A tool using these techniques is applied to a C production software system of some 400 K source lines, and the results confirm detected levels of duplication found by previous work. The tool produces macro bodies needed for clone removal, and macro invocations to replace the clones. The tool uses a variation of the well known compiler method for detecting common sub expressions. This method determines exact tree matches; a number of adjustments are needed to detect equivalent statement sequences, commutative operands, and nearly exact matches. We additionally suggest that clone detection could also be useful in producing more structured code, and in reverse engineering to discover domain concepts and their implementations. <s> BIB002 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> RELATED WORK <s> Along with the blossom of open source projects comes the convenience for software plagiarism. A company, if less self-disciplined, may be tempted to plagiarize some open source projects for its own products. Although current plagiarism detection tools appear sufficient for academic use, they are nevertheless short for fighting against serious plagiarists. For example, disguises like statement reordering and code insertion can effectively confuse these tools. In this paper, we develop a new plagiarism detection tool, called GP LAG , which detects plagiarism by mining program dependence graphs (PDGs). A PDG is a graphic representation of the data and control dependencies within a procedure. Because PDGs are nearly invariant during plagiarism, GP LAG is more effective than state-of-the-art tools for plagiarism detection. In order to make GP LAG scalable to large programs, a statistical lossy filter is proposed to prune the plagiarism search space. Experiment study shows that GP LAG is both effective and efficient: It detects plagiarism that easily slips over existing tools, and it usually takes a few seconds to find (simulated) plagiarism in programs having thousands of lines of code. <s> BIB003 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> RELATED WORK <s> We describe the use of machine learning and data mining to detect and classify malicious executables as they appear in the wild. We gathered 1,971 benign and 1,651 malicious executables and encoded each as a training example using n-grams of byte codes as features. Such processing resulted in more than 255 million distinct n-grams. After selecting the most relevant n-grams for prediction, we evaluated a variety of inductive methods, including naive Bayes, decision trees, support vector machines, and boosting. Ultimately, boosted decision trees outperformed other methods with an area under the ROC curve of 0.996. Results suggest that our methodology will scale to larger collections of executables. We also evaluated how well the methods classified executables based on the function of their payload, such as opening a backdoor and mass-mailing. Areas under the ROC curve for detecting payload function were in the neighborhood of 0.9, which were smaller than those for the detection task. However, we attribute this drop in performance to fewer training examples and to the challenge of obtaining properly labeled examples, rather than to a failing of the methodology or to some inherent difficulty of the classification task. Finally, we applied detectors to 291 malicious executables discovered after we gathered our original collection, and boosted decision trees achieved a true-positive rate of 0.98 for a desired false-positive rate of 0.05. This result is particularly important, for it suggests that our methodology could be used as the basis for an operational system for detecting previously undiscovered malicious executables. <s> BIB004 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> RELATED WORK <s> Code duplication or copying a code fragment and then reuse by pasting with or without any modiflcations is a well known code smell in software maintenance. Several studies show that about 5% to 20% of a software systems can contain duplicated code, which is basically the results of copying existing code fragments and using then by pasting with or without minor modiflcations. One of the major shortcomings of such duplicated fragments is that if a bug is detected in a code fragment, all the other fragments similar to it should be investigated to check the possible existence of the same bug in the similar fragments. Refactoring of the duplicated code is another prime issue in software maintenance although several studies claim that refactoring of certain clones are not desirable and there is a risk of removing them. However, it is also widely agreed that clones should at least be detected. In this paper, we survey the state of the art in clone detection research. First, we describe the clone terms commonly used in the literature along with their corresponding mappings to the commonly used clone types. Second, we provide a review of the existing clone taxonomies, detection approaches and experimental evaluations of clone detection tools. Applications of clone detection research to other domains of software engineering and in the same time how other domain can assist clone detection research have also been pointed out. Finally, this paper concludes by pointing out several open problems related to clone detection research. <s> BIB005 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> RELATED WORK <s> Detecting code clones has many software engineering applications. Existing approaches either do not scale to large code bases or are not robust against minor code modifications. In this paper, we present an efficient algorithm for identifying similar subtrees and apply it to tree representations of source code. Our algorithm is based on a novel characterization of subtrees with numerical vectors in the Euclidean space \mathbb{R}^n and an efficient algorithm to cluster these vectors w.r.t. the Euclidean distance metric. Subtrees with vectors in one cluster are considered similar. We have implemented our tree similarity algorithm as a clone detection tool called DECKARD and evaluated it on large code bases written in C and Java including the Linux kernel and JDK. Our experiments show that DECKARD is both scalable and accurate. It is also language independent, applicable to any language with a formally specified grammar. <s> BIB006 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> RELATED WORK <s> As malicious codes become more complex and sophisticated, the scanning detection method is no longer able to detect various forms of viruses effectively. In this paper, we explore solutions based on multiple classifiers fusion and not strictly dependent on certain malicious code. Motivated by the standard signature-based technique for detecting viruses, we explore the idea of automatically detecting malicious code using the n-gram analysis. After selecting features based on information gain, the probabilistic neural network is used in the process of building and testing the proposed multi-classifiers system. Each one of the individual classifiers is used to produce classification evidences. Then these evidences are combined by the Dempster-Shafer combination rules to form the final classification results for new malicious code. Experimental results produced by the proposed detection engine shows improvement compared to the classification results produced by the individual classifiers. <s> BIB007 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> RELATED WORK <s> In this work, we propose Malware Collection Booster (McBoost), a fast statistical malware detection tool that is intended to improve the scalability of existing malware collection and analysis approaches. Given a large collection of binaries that may contain both hitherto unknown malware and benign executables, McBoost reduces the overall time of analysis by classifying and filtering out the least suspicious binaries and passing only the most suspicious ones to a detailed binary analysis process for signature extraction.The McBoost framework consists of a classifier specialized in detecting whether an executable is packed or not, a universal unpacker based on dynamic binary analysis, and a classifier specialized in distinguishing between malicious or benign code. We developed a proof-of-concept version of McBoost and evaluated it on 5,586 malware and 2,258 benign programs. McBoost has an accuracy of 87.3%, and an Area Under the ROC curve (AUC) equal to 0.977. Our evaluation also shows that McBoost reduces the overall time of analysis to only a fraction (e.g., 13.4%) of the computation time that would otherwise be required to analyze large sets of mixed malicious and benign executables. <s> BIB008 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> RELATED WORK <s> With the recent emergence of mobile platforms capable of executing increasingly complex software and the rising ubiquity of using mobile platforms in sensitive applications such as banking, there is a rising danger associated with malware targeted at mobile devices. The problem of detecting such malware presents unique challenges due to the limited resources avalible and limited privileges granted to the user, but also presents unique opportunity in the required metadata attached to each application. In this article, we present a machine learning-based system for the detection of malware on Android devices. Our system extracts a number of features and trains a One-Class Support Vector Machine in an offline (off-device) manner, in order to leverage the higher computing power of a server or cluster of servers. <s> BIB009 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> RELATED WORK <s> Developers sometimes maintain an internal copy of another software or fork development of an existing project. This practice can lead to software vulnerabilities when the embedded code is not kept up to date with upstream sources. We propose an automated solution to identify clones of packages without any prior knowledge of these relationships. We then correlate clones with vulnerability information to identify outstanding security problems. This approach motivates software maintainers to avoid using cloned packages and link against system wide libraries. We propose over 30 novel features that enable us to use to use pattern classification to accurately identify package-level clones. To our knowledge, we are the first to consider clone detection as a classification problem. Our results show our system, Clonewise, compares well to manually tracked databases. Based on our work, over 30 unknown package clones and vulnerabilities have been identified and patched. <s> BIB010 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> RELATED WORK <s> Because it is not hard to reverse engineer the Dalvik bytecode used in the Dalvik virtual machine, Android application repackaging has become a serious problem. With repackaging, a plagiarist can simply steal others’ code violating the intellectual property of the developers. More seriously, after repackaging, popular apps can become the carriers of malware, adware or spy-ware for wide spreading. To maintain a healthy app market, several detection algorithms have been proposed recently, which can catch some types of repackaged apps in various markets efficiently. However, they are generally lack of valid analysis on their effectiveness. After analyzing these approaches, we find simple obfuscation techniques can potentially cause false negatives, because they change the main characteristics or features of the apps that are used for similarity detections. In practice, more sophisticated obfuscation techniques can be adopted (or have already been performed) in the context of mobile apps. We envision this obfuscation based repackaging will become a phenomenon due to the arms race between repackaging and its detection. To this end, we propose a framework to evaluate the obfuscation resilience of repackaging detection algorithms comprehensively. Our evaluation framework is able to perform a set of obfuscation algorithms in various forms on the Dalvik bytecode. Our results provide insights to help gauge both broadness and depth of algorithms’ obfuscation resilience. We applied our framework to conduct a comprehensive case study on AndroGuard, an Android repackaging detector proposed in Black-hat 2011. Our experimental results have demonstrated the effectiveness and stability of our framework. <s> BIB011 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> RELATED WORK <s> At ICSE'2013, there was the first session ever dedicated to automatic program repair. In this session, Kim et al. presented PAR, a novel template-based approach for fixing Java bugs. We strongly disagree with key points of this paper. Our critical review has two goals. First, we aim at explaining why we disagree with Kim and colleagues and why the reasons behind this disagreement are important for research on automatic software repair in general. Second, we aim at contributing to the field with a clarification of the essential ideas behind automatic software repair. In particular we discuss the main evaluation criteria of automatic software repair: understandability, correctness and completeness. We show that depending on how one sets up the repair scenario, the evaluation goals may be contradictory. Eventually, we discuss the nature of fix acceptability and its relation to the notion of software correctness. <s> BIB012 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> RELATED WORK <s> An unsound claim can misdirect a field, encouraging the pursuit of unworthy ideas and the abandonment of promising ideas. An inadequate description of a claim can make it difficult to reason about the claim, for example, to determine whether the claim is sound. Many practitioners will acknowledge the threat of unsound claims or inadequate descriptions of claims to their field. We believe that this situation is exacerbated, and even encouraged, by the lack of a systematic approach to exploring, exposing, and addressing the source of unsound claims and poor exposition. ::: This article proposes a framework that identifies three sins of reasoning that lead to unsound claims and two sins of exposition that lead to poorly described claims and evaluations. Sins of exposition obfuscate the objective of determining whether or not a claim is sound, while sins of reasoning lead directly to unsound claims. ::: Our framework provides practitioners with a principled way of critiquing the integrity of their own work and the work of others. We hope that this will help individuals conduct better science and encourage a cultural shift in our research community to identify and promulgate sound claims. <s> BIB013 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> RELATED WORK <s> Malware has posed a major threat to the Android ecosystem. Existing malware detection tools mainly rely on signature- or feature- based approaches, failing to provide detailed information beyond the mere detection. In this work, we propose a precise semantic model of Android malware based on Deterministic Symbolic Automaton (DSA) for the purpose of malware comprehension, detection and classification. It shows that DSA can capture the common malicious behaviors of a malware family, as well as the malware variants. Based on DSA, we develop an automatic analysis framework, named SMART, which learns DSA by detecting and summarizing semantic clones from malware families, and then extracts semantic features from the learned DSA to classify malware according to the attack patterns. We conduct the experiments in both malware benchmark and 223,170 real-world apps. The results show that SMART builds meaningful semantic models and outperforms both state-of-the-art approaches and anti-virus tools in malware detection. SMART identifies 4583 new malware in real-world apps that are missed by most anti-virus tools. The classification step further identifies new malware variants and unknown families. <s> BIB014
Repackaging is an important issue in the Android ecosystem that must be continuously dealt with by the research community. We argue that the research around repackaged app detection is blocked by state-of-the-art work which record high performance rates in the literature while hindering comparative assessments. Related to our work are (1) studies that provide constructive discussions on the value of contributions in a research domain, (2) general research on clone detection and (3) frameworks for assessing repackaged detection approaches. Critical review of research: Recently, Blackburn et al. present to our community a pragmatic guide to assessing empirical evaluations BIB013 . They state that an unsound claim can misdirect an entire field. In this work, we attempt to follow their guidelines and thus to avoid potentially unsound claims. Although we have not focused on finding fallacies in evaluation of state-of-the-art work, our motivation is similar to that of Monperrus BIB012 and his critical review of a stateof-the-art automated repair work. We have discussed the challenges that researchers in this domain must keep in mind and further provide new data, approach and ideas for potential research directions. Code clone & software plagiarism detection: App repackaged detection deals with similar concepts as in traditional code clone detection approaches BIB005 , BIB001 , BIB002 , BIB006 , BIB003 ,  , which either work at a higher level where files are directly compared  or work at a lower level where fragments of code (or graphs/trees) are considered, their objectives were to measure the similarity of code fragments. Even if the notion of clone fragment, be it a method, file or package, could be very useful for app similarity measurements, it is not sufficient in the context of Android, since Android apps have intensively leveraged framework and library code. In other words, two apps with similar code fragments are not necessarily similar. Closely related to our new proposed approach is Clonewise BIB010 , which, to the best of our knowledge, is the first to consider clone detection as a classification problem. Our approach, also in contrast with most state-of-the-art work, considers repackaging detection as a classification problem to enable a practical use in real-world settings. Nevertheless, machine learning techniques, by allowing sifting through large sets of applications to detect malicious apps based on measures of similarity of features, have been extensively leveraged to conduct large-scale malware detection BIB004 , BIB007 , BIB009 , BIB008 . Unfortunately, through extensive evaluations, the community of ML-based malware detection has not yet shown that current malware detectors for Android are efficient in detecting malware in the wild. One among the candidate reasons to this situation is the fact that most malware are actually repackaged from benign apps, their ML-based features are probably similar to those extracted from benign apps, making them indistinguishable for ML-based malware detection. Indeed, as pointed out by Meng et al. BIB014 , the current feature-based malware detection approaches are not enough because they cannot provide detailed information beyond their mere detection. They thus propose an alternative approach that leverages semantic features (based on deterministic symbolic automaton (DSA)) to comprehensive Android malware and thereby to detect and classify them. Therefore, we believe that the detection of repackaged Android apps contributes to also valuable ingredients for detecting malicious Android apps. Assessment of repackaged detection algorithms: Complementary to our work, Huang et al. BIB011 have early proposed a framework to comprehensively evaluate the obfuscation resilience of repackaging detection algorithms. They demonstrate the obfuscation problem for repackaged detection algorithm by experimenting on Androguard. Following state-of-the-art work now regularly report on their performance with this framework. With our work, we aim for the same momentum of using a common dataset for evaluating approaches.