Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> OVERVIEW OF CHALLENGES IN REPACKAGED APP DETECTION <s> A device for feeding flowable materials, e.g., a mixture of inter-reactive components, into a mold cavity, has a mixing chamber opening directly into the mold cavity without constriction and a pair of inlets connected to respective supply lines for the components. A control member or plunger is provided in the reaction chamber to close its outlet flush with a mold surface and is provided with grooves in a closed condition of the slider which create recirculation paths for the components when they are not fed to the mixing chamber. <s> BIB001 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> OVERVIEW OF CHALLENGES IN REPACKAGED APP DETECTION <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> BIB002 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> OVERVIEW OF CHALLENGES IN REPACKAGED APP DETECTION <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> BIB003 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> OVERVIEW OF CHALLENGES IN REPACKAGED APP DETECTION <s> Malicious activities involving Android applications are rising rapidly. As prior work on cyber-crimes suggests, we need to understand the economic incentives of the criminals to design the most effective defenses. In this paper, we investigate application plagiarism on Android markets at a large scale. We take the first step to characterize plagiarized applications and estimate their impact on the original application developers. We first crawled 265,359 free applications from 17 Android markets around the world and ran a tool to identify similar applications ("clones"). Based on the data, we examined properties of the cloned applications, including their distribution across different markets, application categories, and ad libraries. Next, we examined how cloned applications affect the original developers. We captured HTTP advertising traffic generated by mobile applications at a tier-1 US cellular carrier for 12 days. To associate each Android application with its advertising traffic, we extracted a unique advertising identifier (called the client ID) from both the applications and the network traces. We estimate a lower bound on the advertising revenue that cloned applications siphon from the original developers, and the user base that cloned applications divert from the original applications. To the best of our knowledge, this is the first large scale study on the characteristics of cloned mobile applications and their impact on the original developers. <s> BIB004 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> OVERVIEW OF CHALLENGES IN REPACKAGED APP DETECTION <s> Mobile applications (or apps) are rapidly growing in number and variety. These apps provide useful features, but also bring certain privacy and security risks. For example, malicious authors may attach destructive payloads to legitimate apps to create so-called "piggybacked" apps and advertise them in various app markets to infect unsuspecting users. To detect them, existing approaches typically employ pair-wise comparison, which unfortunately has limited scalability. In this paper, we present a fast and scalable approach to detect these apps in existing Android markets. Based on the fact that the attached payload is not an integral part of a given app's primary functionality, we propose a module decoupling technique to partition an app's code into primary and non-primary modules. Also, noticing that piggybacked apps share the same primary modules as the original apps, we develop a feature fingerprint technique to extract various semantic features (from primary modules) and convert them into feature vectors. We then construct a metric space and propose a linearithmic search algorithm (with O(n log n) time complexity) to efficiently and scalably detect piggybacked apps. We have implemented a prototype and used it to study 84,767 apps collected from various Android markets in 2011. Our results show that the processing of these apps takes less than nine hours on a single machine. In addition, among these markets, piggybacked apps range from 0.97% to 2.7% (the official Android Market has 1%). Further investigation shows that they are mainly used to steal ad revenue from the original developers and implant malicious payloads (e.g., for remote bot control). These results demonstrate the effectiveness and scalability of our approach. <s> BIB005 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> OVERVIEW OF CHALLENGES IN REPACKAGED APP DETECTION <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> BIB006 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> OVERVIEW OF CHALLENGES IN REPACKAGED APP DETECTION <s> Besides traditional problems such as potential bugs, (smartphone) application clones on Android markets bring new threats. That is, attackers clone the code from legitimate Android applications, assemble it with malicious code or advertisements, and publish these ``purpose-added" app clones on the same or other markets for benefits. Three inherent and unique characteristics make app clones difficult to detect by existing techniques: a billion opcode problem caused by cross-market publishing, gap between code clones and app clones, and prevalent Type 2 and Type 3 clones. Existing techniques achieve either accuracy or scalability, but not both. To achieve both goals, we use a geometry characteristic, called centroid, of dependency graphs to measure the similarity between methods (code fragments) in two apps. Then we synthesize the method-level similarities and draw a Y/N conclusion on app (core functionality) cloning. The observed ``centroid effect" and the inherent ``monotonicity" property enable our approach to achieve both high accuracy and scalability. We implemented the app clone detection system and evaluated it on five whole Android markets (including 150,145 apps, 203 million methods and 26 billion opcodes). It takes less than one hour to perform cross-market app clone detection on the five markets after generating centroids only once. <s> BIB007 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> OVERVIEW OF CHALLENGES IN REPACKAGED APP DETECTION <s> As the techniques for Android malware detection are progressing, malware also fights back through deploying advanced code encryption with the help of Android packers. An effective Android malware detection therefore must take the unpacking issue into consideration to prove the accuracy. Unfortunately, this issue is not easily addressed. Android packers often adopt multiple complex anti-analysis defenses and are evolving frequently. Current unpacking approaches are either based on manual efforts, which are slow and tedious, or based on coarse-grained memory dumping, which are susceptible to a variety of anti-monitoring defenses. ::: ::: This paper conducts a systematic study on existing Android malware which is packed. A thorough investigation on 37,688 Android malware samples is conducted to take statistics of how widespread are those samples protected by Android packers. The anti-analysis techniques of related commercial Android packers are also summarized. Then, we propose AppSpear, a generic and fine-grained system for automatically malware unpacking. Its core technique is a bytecode decrypting and Dalvik executable DEX reassembling method, which is able to recover any protected bytecode effectively without the knowledge of the packer. AppSpear directly instruments the Dalvik VM to collect the decrypted bytecode information from the Dalvik Data Struct DDS, and performs the unpacking by conducting a refined reassembling process to create a new DEX file. The unpacked app is then available for being analyzed by common program analysis tools or malware detection systems. Our experimental evaluation shows that AppSpear could sanitize mainstream Android packers and help detect more malicious behaviors. To the best of our knowledge, AppSpear is the first automatic and generic unpacking system for current commercial Android packers. <s> BIB008 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> OVERVIEW OF CHALLENGES IN REPACKAGED APP DETECTION <s> The rapid growth of mobile application (or simply app) economy provides lucrative and profitable targets for hackers. Among OWASP’s top ten mobile risks for 2014, the lack of binary protections makes it easy to reverse, modify, and repackage Android apps. Recently, a number of packing services have been proposed to protect Android apps by hiding the original executable file (i.e., dex file). However, little is known about their effectiveness and efficiency. In this paper, we perform the first systematic investigation on such services by answering two questions: (1) what are the major techniques used by these services and their effects on apps? (2) can the original dex file in a packed app be recovered? If yes, how? We not only reveal their techniques and evaluate their effects, but also propose and develop a novel system, named DexHunter, to extract dex files protected by these services. It is worth noting that DexHunter supports both the Dalvik virtual machine (DVM) and the new Android Runtime (ART). The experimental results show that DexHunter can extract dex files from packed apps effectively and efficiently. <s> BIB009 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> OVERVIEW OF CHALLENGES IN REPACKAGED APP DETECTION <s> The Android platform now features more than a million apps from thousands of developers. This abundance is convenient, as it caters to almost every need. But users and researchers also worry about the security and trustworthiness of these apps. While precise program-analysis tools are helpful in this context, unfortunately they do not scale to the large number of apps present in current app stores. In this work we thus present DroidSearch, a search engine that aids a multi-staged analysis in which fast pre-filtering techniques allow security experts to quickly retrieve candidate applications that should be subjected to further automated and/or manual analysis. DroidSearch is supported by DroidBase, a middleware and back-end database which associates apps with metadata and the results of lightweight analyses on bytecode and configuration files that DroidBase automatically manages and executes. Experiments on more than 235,000 applications from six different application stores including Google Play reveal many interesting findings. For instance, DroidSearch identifies 40 known malware applications in Google Play and detects over 35,000 applications that use both http and https connections for accessing the same resources, effectively rendering the https protection ineffective. It also reveals 11,995 applications providing access to potentially sensitive data through unprotected content providers. <s> BIB010 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> OVERVIEW OF CHALLENGES IN REPACKAGED APP DETECTION <s> Android developers heavily use reflection in their apps for legitimate reasons, but also significantly for hiding malicious actions. Unfortunately, current state-of-the-art static analysis tools for Android are challenged by the presence of reflective calls which they usually ignore. Thus, the results of their security analysis, e.g., for private data leaks, are inconsistent given the measures taken by malware writers to elude static detection. We propose the DroidRA instrumentation-based approach to address this issue in a non-invasive way. With DroidRA, we reduce the resolution of reflective calls to a composite constant propagation problem. We leverage the COAL solver to infer the values of reflection targets and app, and we eventually instrument this app to include the corresponding traditional Java call for each reflective call. Our approach allows to boost an app so that it can be immediately analyzable, including by such static analyzers that were not reflection-aware. We evaluate DroidRA on benchmark apps as well as on real-world apps, and demonstrate that it can allow state-of-the-art tools to provide more sound and complete analysis results. <s> BIB011 </s> Rebooting Research on Detecting Repackaged Android Apps: Literature Review and Benchmark <s> OVERVIEW OF CHALLENGES IN REPACKAGED APP DETECTION <s> In most of the approaches aiming at investigating Android apps, the release time of apps is not appropriately taken into account. Through three empirical studies, we demonstrate that the app release time is key for guaranteeing performance. Indeed, not considering time may result in serious threats to the validity of proposed approaches. Unfortunately, even approaches considering time could present some threats to validity when release times are erroneous. Symptoms of such erroneous release times appear in the form of inconsistencies with the APIs leveraged by the app. We present a tool called MoonlightBox for uncovering time inconsistencies by inferring the lower bound assembly time of a given app based on the used API lifetime information: any assembly time below this lower bound is considered as manipulated. We further perform several experiments and confirm that 1) over 7% of Android apps are subject to time inconsistency, 2) malicious apps are more likely to be targeted by time inconsistency, compared to benign apps, 3) time inconsistencies are favoured by some specific app lineages. We eventually revisit the three motivating empirical studies, leveraging MoonlightBox to compute a more realistic timeline of apps. The experimental results confirm that time indeed matters. The accuracy of release time is even crucial to achieve precise results. <s> BIB012
Before detailing the different solutions presented in the literature, we propose to review the challenges that researchers should seek to address in repackaged app detection. These challenges are brought up by the realities in the app industry, practical requirements for assessing a detection approach, as well as specificities of Android development. (1)Meeting market-scale constraints. Android developers have produced millions of apps distributed in several markets, raising scalability issues in the detection of repackaged apps. In this work, we consider that the scalability of detecting repackaged apps is referred to two challenges: (1) combinatorial explosion and (2) impractical aspect, e.g., to have the original app counterparts in the dataset. Regarding combinatorial explosion, let us take Google Play as an example, the official Android app market has hosted already over 3 million Android apps  , while several  . https://www.appbrain.com/stats/number-of-android-apps alternative markets such as AppChina have also passed the one-million mark. A simple and intuitive, pairwise similarity comparison between apps (combinatorial explosion) is thus not scalable in practice. For example, using such an approach to detect repackaged apps in Google Play alone, one would need to perform about C 2 3 * 10 6 comparisons. If we consider a computing platform with 10 cores each starting 10 threads to compare pairs of apps in parallel, it would still take several months to complete the analysis when optimistically assuming that each comparison would take about 1ms. From a practical point of view, unfortunately, the problem is further exacerbated by the fact that repackaged apps and their original counterparts are often hosted on different markets. A pairwise comparison approach would then require collecting as many apps as possible across all markets and repositories. Failing to collect such app set would result in an unfair evaluation for repackaged app detection approaches. Indeed, on the one hand, because of missing original apps, some repackaging detection approaches (e.g., pairwise-based approaches) would be unsuccessful for flagging some repackaged apps, although those approaches by themselves are capable of achieving that. On the other hand, given a flagged repackaged app (e.g., by ML-based classifiers), not being able to identify its original counterpart in the testing app set does not necessarily mean the flagged app is a false alarm, because it could be the case that the testing app set is just not big enough, where the original counterpart happens to not be in it. (2)Having a reference dataset. Despite the awareness in academia and industry on the problem of app repackaging, the community lacks relevant datasets to support research work. Building a large and consistent ground truth of repackaging pairs indeed requires substantial efforts. Unfortunately, unless such efforts are made, we can hardly expect significant advances towards producing reliable approaches and tools for addressing repackaged app detection. Indeed, on the one hand, in the absence of a reference dataset, which can serve as a pseudo ground truth, state-of-the-art work cannot be benchmarked and compared one against the other. On the other hand, existing approaches that claim to be successful cannot convince the reader on the precision of their techniques, since confirmation is manually performed by the authors and the detected repackaged apps are not disclosed to the community for additional checking. (3)Recognising the original app in a repackaging pair. Given a repackaging pair, constituted by two similar apps, one being a repackaged version of the other, it is commonly accepted that it remains challenging to distinguish which app is the original BIB004 , BIB005 . Instead, the literature often relies on heuristics such as app packaging/compilation time (e.g., timestamp of classes.dex ). Although such heuristics are intuitive, they are not fully reliable in a sophisticated malware development scenario. Indeed, it is possible for malware writers to manipulate compilation time of their repackaged apps BIB012 . Yet, a number of state-of-the-art approaches depend on such heuristics to flag repackaged apps in the wild. (4)Accounting for potential obfuscation. Obfuscation is known to be effective to help developers to hide their code logic for preventing potential plagiarism. Many obfuscation algorithms have been implemented in frameworks such as DexGuard [79] and SandMark BIB001 which are already used in the Android community. At the same time, however, obfuscation can be leveraged by pirates and malware writers to evade the detection of their repackaging operations. As shown by Huang et al. BIB006 , most static approaches for repackaged app detection are ineffective in the presence of obfuscated apps. (5)Dealing with noise of common libraries. Common libraries, such as the popular com.google.ads and com.revmob advertisement libraries, which are extensively used across many apps, can significantly impact the effectiveness in repackaged app detection  . Indeed, when common libraries are substantially larger than core functionality code, a pairwise comparison approach can lead to false positives, presenting two different apps, but with similar libraries, as a repackaging pair. Similarly, when a large library is replaced during repackaging by another library, a pairwise comparison will fail to detect the repackaging scenario, leading to a false negative. To overcome this challenge, researchers build whitelists of common libraries that are filtered out during repackaged detection processes BIB007 . Unfortunately, it is also challenging to build an exhaustive list of common libraries. (6)Constructing and exploiting a call/dependency graph. Call and dependency graphs are appealing for repackaged app detection as they can abstract the behaviour implemented in a software to allow effectively identifying similar behaviour BIB002 , BIB003 . Unfortunately, there are several challenges in constructing an Android call/dependency graph that will be reliable for comparison experiments. First, Android is event-based and most behavioural actions are performed via user-triggered events (e.g., clicking a button) or system events (e.g., incoming phone call), through callback methods. A call graph may not properly account for the sequences in which callback methods are called. Second, the Inter-component communication mechanism further involves the use of callback methods to allow interaction among different parts of an app. Since those parts are not directly linked at the code level, the constructed call/dependency graph of the app will eventually be incomplete, depending on the choice of starting point for exploring the app. Finally, heavy use of reflection further complicates the building of sound call/dependency graphs BIB011 . The size of the graphs can also challenge the detection of repackaged apps. Indeed, when the graphs are small (e.g., with less than four nodes), comparisons often lead to numerous false positives BIB007 . When the graphs are very large, the challenge of finding isomorphisms may become prohibitive. (7)Dealing with corner-cases. Besides the aforementioned challenges, some corner cases are often eluded in the literature of app analysis. First, some apps cannot be decompiled by popular Baksmali and Soot de-compilers. Indeed, malware writers may intentionally include code which is specifically engineered to prevent such compilers to work BIB008 . Second, all apps are not strictly packaged with common assets: for example, some apps do not have layouts, which may cause failures for approaches that assume that apps always do. Finally, app hardening techniques, where the main app code in classes.dex is encrypted and loaded at runtime through Java Native Interface (JNI), also raises the bar for the research in repackaged app detection BIB009 . (8)Dealing with legal issues. Aside from technical barriers, legal concerns, including copyright/licensing issue in exposing third-party apps and liability in redistributing malware can impact the advances in research on repackaged app detection. Indeed, as previously warned by Bodden et al.  , data security and user privacy on one side and intellectual property rights on the other side, are slowly emerging in the field of informational self-protection. Thus, for example, researchers are often forced to hold back their dataset, hindering adequate comparisons that could lead to tangible improvement of the state-of-the-art. As suggested by Rasthofer et al. BIB010 , there is a need in our community to analyze legal issues.