Juxtapp: A Scalable System for Detecting Code Reuse Among Android Applications
Abstract
Mobile application markets such as the Android Marketplace and the Amazon Android store provide a centralized showcase of applications that end users can purchase or download for free onto their mobile phones. Despite the influx of applications to the markets, applications are either largely unreviewed or only cursorily reviewed by marketplace maintainers due to the vast number of submissions; furthermore, they rely on user policing and reporting to detect mis- behaving applications. This reactive approach to application security, especially when programs can contain bugs, malware, or pirated (inauthentic) code, puts too much responsibility on the end users.
In light of this, we propose Juxtapp, a scalable infrastructure for code similarity analysis among Android applications. Juxtapp provides a key solution to a num- ber of problems in Android security, including determining if apps contain copies of buggy code, have significant code reuse that indicates piracy, or are instances of known malware. We evaluate our system using more than 58,000 Android appli- cations and demonstrate that our system scales well and is effective. Our results show that Juxtapp is able to detect: 1) 463 applications with confirmed buggy code reuse of Google-provided sample code that lead to serious vulnerabilities in real-world apps, 2) 34 instances of known malware and variants (including 13 distinct variants of the GoldDream malware), and 3) pirated variants of a popular paid game.
1 Introduction
As mobile devices (e.g., smartphones, tablets) gain popularity, software marketplaces have become centralized locations for users to download applications. For the An- droid operating system, Google hosts the official Android Market while Amazon and many others provide third party markets. The wide range of devices that are Android- compatible combined with the open source nature of the Android operating system and development platform have led to explosive growth of the Android market share. As of August of 2011, Android has grown to a 52% market share[1].
The rapidly increasing volume of applications, increased demand for diversified functionality, and existence of piracy and malware places large obstacles in the way of a healthy and sustainable Android market.
Vulnerable code reuse. Android developers often misuse coding idioms in Android, either due to copying and pasting of vulnerable code or lack of developer understand- ing[2, 3]. For instance, Google has provided sample code to interface with the License Verification Library and the In-Application Billing APIs, which are responsible for ver- ifying that a user is authorized to execute a program and purchasing virtual items within an application, respectively[4, 5]. Google explicitly warns developers that they need to modify certain parts of the code, because the unmodified template code is subject to certain security vulnerabilities and requires developer intervention in order to ensure security properties.
Malware. With the exploding growth in the number of Android applications, the occur- rence of Android malware has also increased. As of August 2011, users are 2.5 times more likely to encounter malware on their mobile devices than only 6 months ago and it is estimated that as high as 1 million users have been exposed to malware[6].
Piracy. Furthermore, the Android software marketplaces are home to many pirated ap- plications. A common occurrence is for an illegitimate author to repackage and rebrand a paid or popular app with additional program functionality in order to generate revenue and even execute malicious code[7].
The current markets usually rely on two approaches to identify and remove poten- tially dangerous applications: 1) review-based approach, which requires mostly expert manual review and security examination, and 2) reactive approach, e.g., user policing, reporting, and user ratings as indicators that an application may be misleading in its functionality or misbehaving. Given the existence of hundreds of thousands of appli- cations on the markets, neither approach is scalable and reliable enough to mitigate threats to users. To empower and expedite this process, we need an automated analysis of Android applications in order to pare down large application datasets into a small set of noteworthy candidates for further investigation.
Each of the aforementioned problems appears to be unrelated. However, we observe a common invariant among them, namely, code reuse, which sheds light on the fact that a unified approach in detecting common code (or code similarity) may address all of our goals. Using this observation, we propose to build a fast and scalable infrastructure for detecting code reuse in Android applications which allows for 1) early detection and developer notification of known vulnerable or buggy code, 2) detection of instances of known malware, either in isolation or repackaged with an innocuous program, and 3) detection of pirated applications.
It is a challenging task to develop a system to automatically detect code reuse in An- droid applications. The system must be able to quickly compare code and detect reuse, and scale to hundreds of thousands applications or more; the system need to be resilient to certain levels of code modification and obfuscation, which are common in Android applications; the system should be able to r
剩余内容已隐藏，支付完成后下载完整资料
Juxtapp:一个用来在安卓应用中发现代码复用的测量系统
史蒂夫 汉娜
令胡昂
艾华德
李珊
查尔斯贝
因特尔实验室
摘要：
移动应用市场例如安卓市场和亚马逊安卓市场提供一个集中的应用展柜让终端用户可以购买或者免费下载到他们的移动手机里。大量应用涌入市场，然而应用由于数量巨大的上传，或者大部分未被审核或者只经过市场管理员的粗略审核。因此，他们依赖用户监督和举报来发现不良应用。这种反馈式方法对应用安全，特别是当程序可能有故障，恶意软件，或者盗版代码，需要终端用户肩负很大责任。
鉴于此，我们提出JUXTAPP，一个在安卓应用中用来分析代码类似的测量体系。JUXTAPP提供一个对安卓安全的一些问题的关键解决方法，包括判断是否APP含有故障代码的副本，有重大盗版嫌疑的复用，或者有已知的恶意软件的情况。我们评价我们的系统用了超过58，000个安卓应用，证明了我们的系统测量好和有效的。我们的结果说明JUXTAPP能够发现：1）463个由谷歌提供的样本代码中确定有故障代码的会在真实世界的APP导致严重的弱点的应用，2）34种有已知恶意软件和变体的情况，包括13个独有的GOLDDREAM恶意软件的变体，和3）一个流行的付费游戏的盗版变体。
1 介绍
随着移动设备（例如：智能手机，平板电脑）越来越受欢迎，软件市场变成了一个让用户下载应用的集中的地方。对于安卓开放系统，谷歌主持着官方安卓市场，同时亚马逊和很多其它公司提供着第三市场。大规模的与安卓兼容的并连接安卓开放系统资源环境的设备和开发平台导致安卓市场份额爆发性的增长。到2011年8月为止，安卓已经增长了52%市场份额。
急速增长的应用数量，对各种功能的需求量，和盗版与恶意软件的存在，放置了一个大障碍阻碍着安卓市场的健康和持续发展。
漏洞代码的复用：安卓开发者经常滥用安卓编码习惯，或者由于复制粘贴了易受影响的代码或者缺乏开发理解力。例如，谷歌提供了样本代码来与执照核实库和应用内账单APIs连接，它们分别用来负责核实用户被授权去使用程序和在应用内购买虚拟物品。谷歌明确地警告开发者他们需要修改某些部分的代码，因为不变的代码常遭受某些安全弱点，和要求开发者介入是为了保证性能安全。
恶意软件：随着安卓应用的数量爆炸式增长，安卓恶意软件发生量也增加了。到2011年8月止，用户相对于仅仅6个月之前增加了2.5倍机会在他们的移动设备遭遇恶意软件，估计高达1百万用户已经受到恶意软件的影响。
盗版：而且，安卓软件市场是很多盗版应用的家园。一个普遍的情况是一个非法的作者去重新包装和给一个付费的或受欢迎的APP增加额外的功能再给一个新名称，为了得到盈利甚至执行恶意代码。
现在的市场经常依赖2个方法去判断和移除有潜在危险的应用：1）基于检查的方法，这通常要求专家们手工检查和安全测试，和2）反馈式的方法，例如，用户监督，举报，和用户充当一个指示者的角色发现一个应用是否可能在它的功能上面存在误导或者不良行为。考虑到市场上存在成千上万的应用，两个方法都不可测量和不够可靠来减轻对用户的威胁。为了解决和加快这个进程，我们需要安卓应用的自动分析工具去削减大应用数据库为较小的值得注意的库来进一步研究。
上述提到的每一点似乎没有关联。然而，我们观察到它们之中一个共有的不变量，那就是，代码复用，它指出一个事实：我们有标准的方法去发现相同的代码或许能达到我们的目标。用这种观察法，我们提出去建造一个快速的和可测量体系去发现在安卓应用中代码复用，考虑到1）早期的发现和开发通知中已知的漏洞或故障代码，2）已知恶意软件的发现，或者独立出现，或者在一些无害的软件中重装，和3）盗版应用的发现。
这是一个具有挑战性的任务去研发一个在安卓应用中自动发现代码复用。这个系统必须能够快速比较代码和发现复用，而且测量成千上万的代码甚至更多。这个系统需要能工作在一定程度的代码修改和模糊度的情况下，这些在安卓应用中很常见；这个系统应该能够在号称海底捞针的应用比较中有意义的，精确的描绘出差异，所有这些都能在一会儿保持低的出错率。
作为解决方法的第一步，我们使用编译应用的操作码顺序的k-grams和特征杂乱去有效地处理大测量难题。操作码顺序k-grams能够在一定程度上工作在某些类型的代码修改和能够有效地从应用中提取出来。另外，特征杂乱在纬度下降和分类的情况下使用良好。我们用这种技术和特定领域的知识结合，用来评估在安卓应用中的代码复用，已知恶意软件，和盗版问题。我们用k-grams和特征杂乱结合是为了有粗略的有效的应用表示。使用这种表示法，我们可以快速地计算在应用中成对的相似点，在成千上万的应用中发现代码复用。
然而，仍然存在一个简单的问题：关于特征匹配?使用特征匹配工具，例如GREP或者其它更复杂的技术可以在数据库中确定代码复用或者已知恶意软件；但是，这种分析法只能挑选特征来搜索，假定一个最重要的特征是优先的，假定不是这种情况。而且，代码变化，字符串修改，分类名变化，等等，都会被GREP忽略除了最简单的情况。
在这篇文章，我们提出JUXTAPP，一个可以在安卓应用中快速发现代码复用的测量系统。我们用HADOOP实现我们的分类体系，用亚马逊EC2来运作。它能够快速去分析数据库，意味着能够经得起频繁更新和大量新应用的考验。我们应用JUXTAPP解决3种问题：漏洞代码复用，已知的恶意软件，盗版。我们为了评价JUXTAPP的能力，用它在58，000个应用发现了这些问题出现，从大小把它们从千字节排到兆字节，，这些都是从官方安卓市场和ANZHI第三方市场收集的。我们发现这个系统表现和测量良好。
漏洞代码复用。我们说明应用大量使用在谷歌应用内账单和执照核实库中有意义的部分，让它们远离漏洞的影响。
已知恶意软件的情况。我们在安卓市场发现34种恶意软件，其中13种是独特的，先前没见过的变体，它们已经被重新安装在看起来无害的应用中。
盗版。我们在第三方市场中识别盗版应用，说明JUXTAPP可以发现模糊化的和与原版有重大变化的盗版应用。
2 问题界定
在这篇文章中，我们考虑在安卓应用中自动发现相似情况和目标是发现已知故障代码模式和漏洞，重新包装过的盗版应用，和已知恶意软件的问题。在安卓应用中发现代码复用提供了一个发现应用可能对用户的安全产生不好影响和经历或者欺骗开发者的盈利的可能性。我们研发JUXTAPP，一个可以在安卓应用中自动检测代码内容的体系。我们识别代码内容去测量在2个安卓应用中相关代码的相同情况。用这种方法，我们检测了各种各样的安卓市场的漏洞代码，已知恶意软件，盗版应用。
故障和漏洞代码复用。以前在安卓应用中手工的对开发者错误的研究说明开发者经常复制和粘贴和重复使用从安卓特定开发者网站且未修改的样本代码，利用应用相似的情况，我们可以检测安卓市场发现是否他们包含已知的故障或者漏洞代码。
已知的恶意软件。在安卓市场中恶意软件的发生率急速上升。在2011年1月，80个应用被为人熟知的恶意软件入侵，与2011年6月相反，恶意应用的发生率上升超过400个。恶意软件的作者经常用一个恶意载荷重新包装合法的应用为了诱使用户去下载一个感染了的应用。
盗版和重新包装的应用。流行的安卓应用和游戏普遍被以修改过的代码重新包装盗版来逃避版权保护和获得盈利。经过与安卓官方市场和第三方市场发现，我们展示了我们能够发现盗版情况。
范围。我们限制我们自己在安卓应用领域，包括在功能代码变化形式上模糊。例如，我们能够发现2中相似的模糊化的代码的情况，但是我们限制我们自己在这个领域，不考虑已经被转换成等价功能的匹配代码。
2.1 目标和挑战
JUXTAPP在安卓应用中发现代码复用中肯定会遇到各种各样的挑战。一些我们平台的具体的目标是：
在安卓应用中自动分析代码复用。自2011年9月止，安卓市场拥有超过310，000个应用。从2011年5月中旬到2011年9月，安卓市场增加100，000个应用，增加50%。这种在市场应用中急速的增长，同时盗版和恶意应用的数量也增长，强调了快速的自动化分析应用的需求。
测量大规模应用。正如上述提到，安卓市场有成千上万的应用，并且不断有新的应用进入。我们的体系必须能够测量市场的增长来发现大规模的相似的应用。这包括了能够以有效的方法递增地更新我们应用资源库。
通过分析精确和有效地描绘应用。在处理成千上万的应用中，JUXTAPP必须能够精确地描述和快速识别应用中的代码复用。这包含了精确分析和空间数量的权衡，需要经过分析来描述一个应用。
安卓特性。除普遍的挑战外，当计算安卓应用的相似时有若干特定领域考虑。
JAVA 源代码难以获得。对安卓市场的大多数应用，源代码难以获得。安卓应用通过JAVA编译成DALVIK位矢量（熟知的DEX格式），这是DALVIK虚拟机的字节码。这些编译码和应用资源被打包成应用程序包，被称为APK。
多入口系统。不像传统的桌面程序，安卓应用有潜在的多入口。安卓应用被分为几个部分，这些部分每个可以有自己的入口，经过安卓进程交流机构被称为因特网调用。因此，所有类型的程序分析必须把这些加以考虑。
外数据库的重复包含。安卓应用都在一个有安卓开放系统的应用沙盒里面。这意味着每个应用必须包含能被要求运作应用的数据库。这导致有意义的代码通过应用复制。例如，广告库如ADMOB，重复地包含应用。JUXTAPP必须考虑这个事实当识别相似时，因为这些类型的库可能在分析应用时占主要方面。
所有资源需要在APK中运行应用。档案文件都是相关要求去安装和使用应用。安卓应用通过JAVA编写而且编译成DWX，DALVIK虚拟机可执行的格式。所有JAVA应用代码都被包含在CLASSES.DEX文件，是我们用来提取，处理和特征杂乱。我们将在4.1节再讨论细节。
模糊度。安卓开发者被鼓励用PROGUARD去模糊化它们的代码。PROGUARD可以移除未用过的代码和用模糊化的名字去重新命名类别，方式和文件来使安卓应用的逆向工程更加困难。然而，这个进程是确定的，所以2个相同的应用会被用同一方法转换。正如我们上述提到的，我们考虑模糊码，而且我们可以匹配相似的模糊码，但是我们限制我们自己不要考虑匹配相同功能的代码片段。
3背景
像静态代码复用打算在[14,15],我们用k-grams操作码顺序特征来描述应用。然而，从代码数序提取的k-grams经常产生一个巨大的特征空间（例如, 2的128次方），阻止有效的特征储存和相似比较，甚至发生在中等数量的应用中。为了分析大量的移动应用，我们需要有效的应用的特征表示和在其中的一个快速的比较特征。
特征拼凑。我们使用的主要技术是特征杂乱。特征杂乱是一个受欢迎的强大的用来减少被分析的数据范围的技术。使用简单的拼凑功能，把压缩原来大数据空间压缩变小，使特征空间随机化，再在里面特征拼凑，描述和成对的比较都非常有效。这种功能以在拼凑时潜在的冲突为代价的。然而，从匹配学习交流的理论和实验的结果看，成对的相似保证着高精确度，因此算法如分级群聚，变得非常需要。特征拼凑最近被引用在恶意软件分析的安全交流上。
这种作为结果的表示法可以被编码成简洁的位矢量，在数据中表示特征出现。一如既往，选择一个好的拼凑功能和一个基本长度的位矢量表示对减少矢量冲突是至关重要的。相似。我们通过它们的特征库来识别2个应用的相似点。我们使用JACCARD相似度量标准定义为J (A, B) = |Acap;B| ,A和B分别是2个应用的k-gram特征库。因为我们拼凑 k-gram设成布尔数学体系的矢量，用每个入口表示特征的出现或不出现。与项目库相反，我们可以非常有效率地用比特式操作J (A, B) = |Acap;B| 近似这些数量，这里A和B分别表示k-gram位矢量的A和B。如图[9]所示，只要位矢量的大小足够大，J (Acirc;, Bcirc;) 非常接近 J(A,B）。这里JACCARD距离D（A,B），测量2个特征矢量的不相似点，从D(Acirc;, Bcirc;) = 1 minus; J (Acirc;, Bcirc;)通过减去JACCARD相似点。2个JACCARD相似和距离都在[0,1]内有值。
4 我们的方法
如图一所示，我们的方法，JUXTAPP，设计一下步骤来分析安卓应用：1）应用预处理，2）特征提取。和3）收集和内容分析。
4.1 应用预处理
我们预处
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[147300]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
