AG娱乐,AG真人,AG平台,AG旗舰厅,AG视讯,AG娱乐平台,真人视讯平台,首存送彩金

　　近年来，移动设备，如智能手机，已经以指数级的速度发展。在这些设备上运行的最常用的系统是安卓软件栈，几乎占了全世界智能手机市场份额的80%。该系统运行用户从应用市场下载的安卓应用程序。该系统被称为基于权限的系统，因为它通过检查应用程序是否有必要的权限来限制对受保护资源的访问。用户使用他们设备上的应用程序存储和操作个人信息，如联系人名单或图片，并相信他们的数据是安全的。分析应用程序和它们所运行的系统是评估数据是否得到良好保护的客观方法。

　　在这篇论文中，我们旨在从安全的角度分析Android应用程序，并回答以下具有挑战性的问题： 如何分析安卓应用？ 安卓应用的权限是否得到很好的定义？应用程序能否泄露受保护的数据？动态分析如何能补充静态分析？为了回答这些问题，我们的论文围绕四个目标展开。

　　第一个目标是用静态分析工具来分析Android应用程序。我们面临的挑战是，Android应用程序是用Dalvik字节码打包的，在许多方面与Java字节码不同。我们开发了Dexpler，这是一个将Dalvik字节码转化为Jimple的工具，Jimple是Soot的一种可理解的格式，是最常用的基于Java程序的静态分析框架之一。有了Dexpler，我们现在可以分析Android应用程序了。

　　第二个目标是检查开发者是否给他们开发的安卓应用提供了太多的权限。 减少权限的数量可以减少恶意用户利用应用程序的攻击面。 我们分析应用程序的代码，以检查它们真正需要哪些权限。 这需要深入分析安卓框架，提取API方法（安卓应用程序调用）和所需权限之间的映射。我们提出了一种类似于安徒生的领域敏感方法，使用新的领域特定的优化来从安卓框架中提取映射。

　　权限能保护敏感数据。然而，拥有正确权限访问数据的应用程序可能会泄露数据。例如，恶意软件或与积极的广告库打包的应用程序就是这种情况。第三个目标是静态分析Android应用程序，以检测这种泄漏。Android应用程序与传统的Java应用程序不同。最重要的区别之一是，Android应用程序是由组件组成的。分析Android应用程序以发现泄漏，需要将一起通信的组件联系起来，并对每个组件进行建模。我们开发了IccTA来检测隐私泄漏。它在代码层面连接组件，以执行组件间和应用间的数据流分析。

　　静态分析Android应用程序可以发现安全问题，如GPS坐标从设备中泄露出来。然而，静态分析并不直接在用户的设备上运行，因此没有考虑到设备的上下文。本论文的最后一个目标是深入了解动态方法如何补充静态分析。我们首次提出了一个工具链，用于动态检测体内的Android应用，即直接在设备上检测。我们提出了两个对应用程序进行检测的用例，以表明动态方法是可行的，它们可以利用静态分析的结果，并且从安全和隐私的角度来看，它们对用户是有益的。其中一个用例是一个内粒度的权限系统原型，使用户能够随意禁用或启用应用程序的权限。

　　通过这篇论文，我们提供了使用静态分析来分析安卓应用的解决方案，检查应用的权限集，在安卓应用中ind私有数据泄漏，以及分析基于权限的框架。通过分析出错的地方，我们可以改善移动应用的安全和隐私。

　　首先，我要感谢我的导师，Yves Le Traon。能够成为他的SERVAL团队中的第一个博士生，我感到非常荣幸。我很感谢他花时间与我讨论新的想法和贡献。当遇到技术问题时，他坚持让我退一步，看一看全局，这确实有帮助。Yves告诉我好的软件工程研究是如何完成的。

　　然后，我想感谢我的日常顾问，雅克-克莱因。是他启动了第一批安卓研究项目，他把安卓设备带到我的办公桌上，引导我找到了正确的研究问题。他总是心情很好，和他一起工作真的很愉快。他教会了我如何集中思想，如何在抽象的层面上进行推理，以清楚地提出新的想法。

　　Martin Monperrus是我在里尔大学的远程顾问。我想感谢他对我工作的建设性和有洞察力的反馈，以及关于论文写作和时间管理的伟大建议。他总是激励着我努力工作，以达到顶级会议和期刊的水平。

　　在博士期间，我与卢森堡大学的许多人进行了非常有趣的技术讨论，特别是与凯文-阿利克斯（Kevin Allix）、特加文德-弗朗索瓦-迪塞斯-比桑德（Tegawendé François DAssise Bissyande）和李力（Li Li），我特别要感谢他在IccTA方面的出色工作。

　　我有机会与美国宾夕法尼亚大学和德国达姆施塔特技术大学的研究人员合作并访问他们。 我想感谢宾夕法尼亚大学的Damien Octeau和Patrick McDaniel，他们发起并领导了我们在EPICC上的成功合作。我还要感谢达姆施塔特技术大学的Eric Bodden、Steven Arzt和Siegfried Rasthofer，感谢他们在FlowDroid上的出色工作以及我们在污点分析上的富有成效的合作。

　　我感谢卢森堡国家研究基金（FNR），它是我的资金来源，使我的博士工作在三年半的时间里成为可能。

　　最后，我想感谢我的家人，感谢他们的鼓励和爱。 感谢我的父母，他们在我学习期间一直支持我。最重要的是感谢我的妻子克莱尔，她在博士期间对我的支持，我非常感激。谢谢你。

　　近年来，移动设备，如智能手机，已经以指数级的速度发展。在这些设备上运行的最常用的系统是安卓软件堆栈，几乎占了全世界智能手机市场份额的80%，然而，随着普及，为安卓系统定制的攻击也越来越多。

　　在这篇论文中，我们声称静态分析可以帮助防止这种攻击。我们使用静态分析从一个基于权限的框架1中提取权限。这使得我们能够检查在基于权限的框架之上运行的应用程序是否遵守了最小权限原则，并且没有声明太多的权限。此外，为了评估资源和用户数据是否得到了很好的保护，我们对应用程序进行静态分析，以发现可能表明恶意行为的可疑泄漏。最后，我们表明，从框架的静态分析中提取的信息可以在运行时利用，以从隐私的角度加固应用程序。例如，我们实施了一个用户驱动的动态政策执行，使用户能够启用或禁用任何应用程序的权限。

　　为了更好地理解Android权限系统，让我们回到访问控制的前提下。事实上，自从多个用户可以访问同一台计算机以来，人们就需要使用访问控制来保护他们的数据不受其他用户的影响，不管他们是恶意的还是笨拙的。在这一章中，我们介绍了访问控制的概念，并激励我们选择对一个名为Android的基于权限的系统进行分析。第1.1节和第1.2节介绍了访问控制的概念，从第一台引入密码的计算机到最新的基于权限的系统Android。

　　第1.3节说明了基于权限的系统的缺点。第1.4节解释了我们在研究和分析基于权限的系统时所面临的挑战。最后，第1.5节列出了这项工作的贡献。

　　最早允许多个用户同时工作的计算机之一是1963年的兼容时间共享系统（CTSS）[32]。 每个用户都可以访问计算机，并可以通过一个终端发送命令给它，还可以得到一个个人目录来存储文件。只要有一个以上的用户在同一台机器上存储信息，就会出现关于隐私、安全和保障的问题。任何人都应该能够看到谁创建了一个ILE吗？如果有人错误地删除了另一个用户的ile怎么办？是否应该允许任何人看到任何用户的任何ile？

　　为了解决这个问题，CTSS可能是第一个引入这个想法的操作系统，密码被用来验证用户。一旦用户被系统认证，她将只被授权访问他/她的文件，而不是任何其他用户的文件[32, 112, 133]。该系统确保iles只被授权用户访问。换句话说，它保护了系统的资源，防止恶意或笨拙的用户访问或篡改它们。 一个用户可以与其他用户共享ile，允许他们在自己的目录中放置一个称为link的特殊ile，引用共享ile。这是访问控制的第一种方法。 图1.1表示了一个访问控制的通用模型。 每当一个主体（如用户）试图访问一个对象（如链接）时，系统就会检查访问控制策略以允许或拒绝该访问。

　　1965年推出的CTSS的后继者，称为MULTICS（多路信息和计算服务）[33, 112]，从一开始就以信息保护为目的。与CTSS一样，每个用户都有一个标识符，并使用密码对系统进行验证。 然而，MULTICS引入了用户组的概念和访问控制列表（ACL）的概念。ACL是一个可调整的用户列表，这些用户被允许读取、写入、执行或追加一个对象（例如，一个程序）。对象被组织在一个由目录组成的单一层次结构树中。 如果一个用户有修改目录的权限，她可以修改该目录下所有对象的ACL。 由于用户可以改变属于他们的对象的访问权限，所以访问控制被称为自由决定的访问控制（DAC）。

　　受MULTICS的启发，UNIX [108]在20世纪60年代末70年代初出现。在UNIX中，ILE-系统是一棵由ILE和目录组成的树。每个ILE和目录都属于一个用户和一个组。此外，每个ILE和目录都有权限位，允许所有者为拥有该ILE的用户、该ILE所属的组或其他用户激活或取消读、写或执行的权限。

　　在接下来的几年里，计算机已经在能够负担得起的公司和军队中普及和使用。这引起了人们对计算机安全，特别是访问控制的兴趣。人们努力将访问控制正式化为数学模型。Bell-LaPadula访问控制模型[16]是在1973年设计的，重点是保密性，这在军事应用中特别有用。在这个模型中，主体（如用户）可以观察、改变或修改对象（如档案）。为主体和客体分配一对，决定类别和分类，称为安全级别（例如，类别 密码学 和分类 未分类，类别 核 和分类 秘密，类别 化学 和分类 最高机密，......）。 实施Bell-LaPadula模型的系统必须确保一些属性是成立的（例如，一个分类为 秘密 的用户不能阅读 最高机密 的文件）。这些访问规则是由管理员在一个集中的政策中确定的，用户不能修改或绕过。这种访问控制被称为强制性访问控制（MAC）。

　　Bell-LaPadula侧重于保密性，因此只限制对数据的访问，但对保护数据的损坏没有任何作用。简而言之，它不能确保数据的完整性。1977年，另一个模型被设计来解决这个问题：比巴模型[21]。这个模型确保一个主体不能破坏数据，其安全级别高于主体的级别。

　　在20世纪70年代末、80年代初，最初的UNIX系统诞生了许多基于相同理念的版本。最著名的系统可能是GNU/Linux、基于BSD和MAC X的操作系统。它们的基本访问控制类型是DAC，但也存在MAC的实现，例如SELinux[121]是Linux内核的MAC扩展。

　　确定一个系统的安全策略（即所有访问控制规则的集合）是一项复杂的任务，需要对系统的访问控制模型有深入的了解。 今天，计算机无处不在，新手和专家都在使用。确定访问控制策略不是一件容易的事，甚至可能被那些只想让系统工作而不关心安全问题的新手用户所忽视。

　　在欧洲，手机的人口覆盖率几乎达到100%[73]。 它们已经从运行一个主要目的是打电话和接电话的系统的设备发展到了完全边缘化的计算机。这些设备能够连接到互联网，观看高分辨率的电影和玩最新的3D游戏，并与电话应用捆绑在一起。这些电脑，或称智能手机，运行用户从互联网上的应用市场下载的应用程序。对于智能手机来说，应用程序在对系统资源进行操作时（例如，GPS、互联网访问......），通常受到开发商为其规定的一系列权限的限制。

　　当下载一个应用程序时，用户可以看到该应用程序所需的权限列表，并可以决定允许该应用程序被授予列表中的所有权限并安装该应用程序，或者选择根本不安装该应用程序。这种访问控制的权限模型使用户处于管理员的地位：他/她必须在每次安装新的应用程序时更新设备的访问控制策略。 我们称这种系统为基于权限的系统。我们在这项工作中研究的基于权限的系统是Android。

　　下面三节(1.3.1, 1.3.2 和 1.3.3)介绍了一些例子，激励我们分析运行在基于权限的系统之上的应用程序。这些例子代表了基于权限的系统设计中的一个环节，因此与正在研究的基于权限的系统无关。 此外，第1.3.4节说明了这样一个事实：由于文档不完整，开发者可能会无意中在他们开发的应用程序中产生漏洞。这促使我们对基于权限的系统本身进行分析，以改进文档和/或应用程序的开发过程。最后，第1.3.5节强调了安卓系统在权限方面给予用户的自由的局限性，并提出了一个替代方案，该方案依赖于安卓基于权限的系统的分析结果。

　　应用程序可以一起交流。 如果一个应用程序被赋予一个权限，另一个应用程序可以利用这个应用程序来滥用其权限。 这种攻击被称为混乱的副手攻击，如图1.2所示。这种攻击经常发生，因为混乱的副手应用程序错误地认为只有一个有限的和受信任的应用程序可以访问它的接口。由于这个原因，它的接口没有得到很好的保护，可以被意识到这个漏洞的恶意应用程序所滥用。在图1.2的例子中，混乱的副程序拥有网络权限，因此能够启用或禁用网络。 它错误地认为只有受信任的应用程序才能访问其接口，因此没有正确地保护它。攻击者利用这个不受保护的接口，让混乱的副手使用其权限代表攻击者禁用网络。

　　应用程序被授予权限，可以一起通信。因此，没有什么能阻止一个应用程序从受权限保护的资源中获取数据（例如GPS坐标），并与另一个可能没有权限访问受保护资源的应用程序分享这些数据。当多个应用程序为了一个共同的恶意目标而合作时，它们就会串通起来。

　　图1.3说明了应用程序串通的情况。 攻击者必须在目标设备上安装两个（或更多）应用程序。 一旦应用程序被安装，它们就会一起交流，分享它们的权限。在安装单个应用程序时，用户只能看到每个应用程序的有限权限。在图1.3的例子中，第一个应用只有GPS的权限，第二个应用只声明了互联网的权限。

　　然而，应用1可以与应用2分享它通过GPS权限获得的数据。应用程序2可以访问互联网，它可以将GPS坐标发送到互联网上的一个远程主机。互联网上的一个远程主机。

　　图1.3的例子说明了两个应用程序共享GPS坐标并将其发送到互联网上。我们说，GPS数据从App1中检索GPS坐标的语句（源）泄漏到App2中发送坐标到互联网的语句（汇）。这种特殊的数据泄露发生在两个应用程序之间，这在恶意软件应用程序中并不常见。为了更有效，大多数恶意软件在一个单一的应用程序中泄漏数据。

　　一个Android应用程序包含一个权限列表，描述了该应用程序可以访问哪些资源（例如，访问GPS）。安卓应用的开发者负责编写这个权限列表。为了实现这一目标，他们依靠文档，但遗憾的是，文档并不完整[53]。此外，他们还依赖在论坛或网站上找到的带有权限列表的代码片段[53]。然而，权限表可能包含了超过必要的权限。 因此，开发人员可能会编写一个包含比应用程序所需更多权限的权限列表，增加应用程序的攻击面（即攻击者可以进入系统并可能造成损害的所有方式[85]）。事实上，如果一个攻击者破坏了应用程序，她就可以访问更多的资源，而不是在减少权限列表的情况下访问。

　　在本论文中，权限缺口被定义为一个应用程序声明但不使用的一组权限。为了检测权限差距，我们首先要计算出所有API方法的权限集合。然后，通过查看应用程序调用的API方法，可以从应用程序代码中自动计算出一个权限列表。映射到这些API方法的权限构成了应用程序需要的权限列表，以便正常工作。这个自动计算的权限列表和应用程序的开发者编写的权限列表之间的差异被称为权限差距。

　　用户往往自愿或不自愿地在他们的设备上存储大量他们认为是隐私的信息，如图片、联系信息、GPS坐标、电子邮件或日历信息。一方面，他们认为这些信息是私有的，受到设备的保护。 另一方面，他们希望从互联网上的远程存储库（可信和不可信）安装应用程序，并精确控制这些应用程序的权限列表。然而，他们没有可能配置一个细化的权限政策。

　　在这项工作中，我们探讨了在用户设备上直接实现这样一个系统的挑战。新的软件修改了安卓应用程序的字节码，并在代码中编织了访问控制策略。该策略可以在运行时由用户决定，例如，禁用所有安装的应用程序的权限。

　　总而言之，我们在本节中看到：（1）混乱的副手、应用程序串通和数据泄漏的例子促使在应用程序中进行泄漏检测；（2）不完整的文件表明应该对框架本身进行分析；（3）为了改善数据保护，应该让用户对设备的安全策略有更多控制。

　　在这篇论文中，我们旨在从安全的角度分析Android应用程序和Android框架。从激励性的例子中，我们将回答以下具有挑战性的问题：如何分析Android应用？每项任务都是为安卓应用设计的吗？ 应用程序会泄露受保护的数据吗？ 动态分析如何补充静态分析？ 下一节将描述我们在回答这些问题时面临的技术挑战。

　　在这一节中，我们将介绍在分析Android框架和Android应用程序以回答第1.3节所列研究问题时面临的技术挑战。

　　第1.4.1节解释了Android应用程序使用一种特殊的字节码，需要将其转换为可分析的表示。第1.4.2和1.4.3节分别描述了分析Android框架和Android应用程序的困难。最后，第1.4.4节强调了直接在设备上运行分析Android应用程序的挑战。

　　Android应用程序是用Java编写的，然后编译成Java字节码，最后编译成Dalvik字节码。现有的静态分析工具可以在应用程序的源代码或Java字节码可用时分析Android应用程序。然而，这种情况并不常见，因为大多数应用程序是通过市场分发的，而市场只提供最初的Dalvik字节码。 例如，在官方的Google Play市场上有超过一百万的应用程序2，而在F-Droid（免费和开源的安卓应用程序）网站上只有大约一千个应用程序3。这就促使我们使用一个软件模块将Dalvik字节码转换为可分析的表示。

　　在本论文开始的时候，也就是2010年，还没有可用的工具来对Dalvik字节码进行复杂的静态分析。为了能够分析Android应用程序，我们开发了一个名为Dexpler的模块，将Dalvik字节码转换成可分析的表示。 我们利用了一个现有的名为Soot的工具，其内部的代码表示被称为Jimple。如图1.4所示，Soot能够分析Java源代码和Java字节码，将它们转换为Jimple表示法。 Dexpler将Dalvik字节码转换为Jimple，以便Soot能够分析Dalvik字节码。

　　当把Java字节码转换为Dalvik字节码时，一些关于变量类型的信息会丢失。对于字节码中每个有这种信息丢失的方法，Dexpler通过分析该方法的代码将这些信息找回来。

　　静态分析最初是用在程序或应用程序上，而不是API上。对于一个程序，通常有一个单一的入口点，分析从这里开始。然而，对于一个框架或API来说，没有入口点：我们必须为所有的入口点构建包装代码。封装代码的作用是构建入口点方法被调用的对象，以及被调用的入口点方法的参数。 此外，构建封装代码并不是一件容易的事，因为我们必须考虑到如何调用API的方法以及如何初始化其参数。

　　对一个框架的静态分析从构建封装代码的调用图开始。在Android的情况下，API代码是系统运行的其他程序或应用程序的接口。仅仅从封装代码中构建调用图是不行的，因为系统程序（负责检查权限）没有被正确初始化。由于系统程序是在安卓设备启动时启动和初始化的，所以初始化代码是无法从入口点方法中到达的。 我们采用的解决方案是将所有的系统程序独立出来，从入口点调用图中单独初始化它们，并且每当在入口点调用图中遇到它们时，就引用初始化的程序。

　　图1.5展示了一个有三个入口点（如ep1、ep2和ep3）的框架。分析这个框架需要对这些入口点进行包装。这是通过处理入口点初始化和参数实例化的 入口点包装器 节点实现的。在构建调用图时，ep3调用了 srv1 服务的代码。 这个服务已经被单独初始化了（图1.5，右），调用图的构建参考了初始化的服务。如果没有服务的初始化，调用图是不完整的，因为该服务应该是不存在的。

　　分析Android应用程序与分析Java应用程序不同，后者有一个单一的入口点（即主方法）。Android应用程序的特点是，每个组件都有一个由Android系统管理的生命周期。图1.6a代表了一个叫做activity的Android组件的生命周期的简化视图。这个生命周期有四个状态，s1到s4，在事件产生后从一个状态移动到另一个状态（e1到e7）。事件触发了组件的指定方法（m1到m7）。组件的生命周期在Android应用程序中是不存在的。Android系统处理Android应用程序的组件的生命周期。由于为每个应用程序分析Android系统以考虑到组件的生命周期，成本太高，所以我们使用生命周期的模型来代替。

　　此外，任何组件都可以被同一应用程序或另一应用程序的另一个Android组件调用。一个安卓应用没有单一的入口点，但至少有和组件一样多的入口点。一个应用程序的组件被列在应用程序的清单中。在图1.6b中，没有源组件的黑色箭头代表应用程序一的组件C1和C3以及应用程序二的组件C5和C6的入口点。

　　有些组件可以在应用程序的组件代码中定义，而不是在清单中定义。因此，仅仅分析清单是不够的，还必须检查组件的代码以确定动态注册的组件。此外，组件之间可以相互通信。组件是松散耦合的，因为它们之间的连接是在运行时完成的，它们之间的通信依赖于被称为Intents的抽象消息。在图1.6b中，应用一的组件C1和C2之间以及C2和C4之间有应用内通信，应用一的C3和应用二的C5之间有应用间通信。

　　简而言之，当使用静态分析来分析一个Android应用程序时，我们必须对组件的生命周期进行建模，并计算组件之间的通信链接。

　　虽然在设备外对应用程序进行分析和转换很有趣，但直接在设备上进行分析会更有趣。例如，用户将直接受益于允许他们拥有细化权限政策的软件（即允许对权限进行细化调整的政策。例如，INTERNET权限不允许完全的网络访问，而是可以将网络访问限制在用户自定义的URL列表中）。主要的挑战是能够在对可用内存和处理能力有限制的设备上进行一些分析，以及对一个进程的可用堆有硬编码限制。 在桌面上需要100MB堆的分析不能在标准的安卓设备上运行，因为安卓设备的堆限制是80MB或更少。

　　在本节中，我们提出了我们的贡献，以回答第1.3节中提出的研究问题，并解决第1.4节中提出的相关挑战。 在这项工作中，有七个主要的贡献，推动了Android和基于权限的系统研究的最先进水平：

　　- 一种转换Dalvik字节码Jimple的算法。 由于Jimple是静态分析框架Soot的内部代表，Dexpler使Soot能够静态地分析Android应用程序。我们在一组2.5万个应用程序上评估了Dexpler。Dexpler正确地转换了99.9%的应用程序的方法。

　　- 一种将API方法映射到权限的算法。我们提出了一种算法，首先从API方法中生成入口点，然后从基于权限的框架的API方法中建立一个调用图，最后使用深度优先搜索来进行权限检查并提取权限名称。

　　- 对Android基于权限的系统进行实证分析。我们已经实现了我们的算法，将API方法映射到权限，并对其进行了定制，以分析Android框架。 安卓特有的修改包括服务重定向、服务身份反转、系统服务和管理者初始化。

　　- 对权限差距的实证分析。 该分析是在两组Android应用程序上进行的。在第一组中，有18%的应用程序来自官方的安卓市场，第二组来自另一个市场，有12%的应用程序存在权限差距。

　　- 一个检测Android应用程序内部和之间泄漏的工具。我们的工具叫IccTA，在Jimple级别上链接Android组件。这允许检测组件间和应用间的数据泄露。

　　- 对IccTA进行实证评估，以检测组件间的泄漏。我们在DroidBench上评估了IccTA，这是一套专门为测试组件内和组件间泄漏的工具而设计的Android应用程序。 我们的算法优于现有的工具，精确度为95%，召回率为82%。 我们还在一组3000个安卓应用中评估了我们的算法。它在其中450个应用程序中检测到了泄漏。

　　- 第一个关于体内仪器化的实证分析。这项研究显示了直接在设备上对安卓应用进行检测的可行性。我们还提出了两个用例：第一个用例是将广告从应用程序中移除，第二个用例是允许用户制定一个细化的权限策略，这在本地安卓系统中是不可能的。 这些案例表明，该方法是可行的，进行高级分析的主要限制是系统施加的堆大小。

　　本论文的组织结构如下。在第二章中，我们介绍了静态分析的基本原理、调用图的构建、Android应用程序和基于权限的Android系统。在第三章中，我们讨论了Dexpler，一个将Dalvik字节码转换为Jimple的软件，以便分析Android应用程序和Android系统。在第四章中，我们分析了Android框架，将权限映射到入口点方法。我们利用这些知识来识别那些声明了太多权限的应用程序，这增加了终端用户的攻击面。在第五章中，我们描述了一种在安卓应用中识别私人数据泄露的技术。接下来，在第6章中，我们介绍了关于体内安卓应用工具和分析的第一个结果。 最后，在第八章中，我们总结了论文，并讨论了未来的工作和开放的研究问题。

　　本章介绍了理解本博士论文所需的主要技术背景。本章分为三个部分。第2.1节介绍了安卓系统：包括安卓应用程序及其组件、系统服务和许可访问控制。 然后，第2.2节向读者介绍了静态分析，特别是基于Java程序的调用图构造和程序间数据流分析。

　　Android是一个为智能手机、平板设备以及更广泛的任何种类的个人设备开发的软件系统。它最初是由安卓公司在2000年初开发的[78]。谷歌在2005年收购了该公司以进一步开发该系统。第一个公开可用的设备出现在2008年[79]，运行的是安卓1.0。从那时起，大约每三个月就有一个新的版本发布。在写这篇文章的时候（2014年）

　　在本节中，我们首先在第2.1.1节中对安卓系统进行了概述。然后，我们在第2.1.2节中介绍了Android应用程序的结构。最后，在第2.1.3节中，我们详细介绍了系统服务，这是Android系统的一个主要部分。

　　Android是一个软件栈，意味着它有四个主要的软件层，如图2.1所示（从上到下）：应用层、框架层、运行时和本地库层以及内核层。

　　顶层的特点是Android应用程序。典型的安卓应用有：主页应用，它是第一个运行的应用，显示启动其他应用的图标；联系人应用，管理联系人列表；电话应用，拨打电话；浏览器应用，访问网络资源。运行安卓系统的设备的用户可以在他们的设备上安装更多的应用程序，通常是通过从FDroid1或名为Play Store2的谷歌官方市场上下载。 应用程序主要用Java编程语言编写，但也可以包含本地代码。 应用程序依靠框架层与系统进行通信。

　　框架层是应用程序和系统其他部分之间的一个用Java编写的接口。它提供了从系统资源中检索信息的设施（例如，应用程序可以通过LocationManager检索GPS坐标）或要求系统在有新事件时回调它们（例如，要求TelephonyManager在有电话时通知应用程序）。

　　- Android运行时由Dalvik虚拟机和Android核心库组成，前者执行Android应用程序的Dalvik字节码3，后者基本上是应用程序可以利用的Java类（例如，应用程序可以使用HttpsURLConnection类来打开与网站的安全连接）。 有些库包含对本地库的封装。 例如，处理与网站安全连接的核心库的Java类，如HttpsURLConnection，可以使用OpenSSL本地库，这取决于环境的配置。

　　- 本机库4提供了可以被应用程序、框架层或核心库使用的基本构建块。应用程序可以有直接使用本地OpenGL库进行快速图形处理的本地代码。框架层可以使用本地SQLite库来存储数据。

　　最低的一层是Linux内核。从上层的软件层来看，它可以被看作是硬件（CPU、内存......）的一个界面。事实上，它负责在CPU上运行程序5，它有许多驱动来处理不同的硬件，如显示器、网络和管理网络通信的驱动。它还具有一个特殊的驱动，用于有效的进程间通信，称为Binder驱动[116]。

　　正如我们所看到的，这些层并没有明确分开。 一个Android应用程序可以使用框架层、核心和本地库中的元素，也可以直接与内核通信。安卓系统实现了安全功能，以防止应用程序访问系统的每个部分。简而言之，开发者给他们编写的每个应用程序提供了一个权限列表。这个列表规定了应用程序被允许在系统上做什么，并且必须在安装时由用户进行验证。当一个应用程序被安装时，它被赋予一个用户ID（UID）。每个安卓应用都可以被看作是一个Linux用户。此外，安卓系统有一个列表，将每个权限映射到一个组ID（GID）。对于应用程序声明的每一个权限，系统都会将该应用程序（或更确切地说，相应的Linux用户）添加到相应的GID中。因此，如果一个应用程序没有GPS权限，并想通过LocationManager或GPS的Linux驱动来检索GPS坐标，Android系统会检测到该应用程序不在GPS组中，并阻止它访问GPS数据。

　　一个安卓应用程序是一个用开发者的私钥K签名的压缩zip文件。它包含应用程序的Dalvik字节码（由Java源代码编译而成）、应用程序需要的数据（图片、声音......）以及描述应用程序结构和应用程序所需权限的清单文件。简而言之、

　　安卓应用是用开发者的私钥签名的，这确保了应用只能由同一个开发者签名的代码来更新，而且用同一个密钥签名的应用有可能共享权限和UID。然而，它并不保证应用程序作者的真实性，因为证书可以是自签的（例如，任何人都可以声称是无名氏）。

　　Android应用程序是由组件组成的。有四种组件：活动、服务、内容提供者和广播接收器。活动组件用于图形用户界面（GUI）。它们显示图形元素，如按钮、列表或图片。服务组件用于计算密集型任务或需要长时间的任务，如播放音频文件。 内容提供者被用来在应用程序之间共享数据。例如，联系人列表被实现为一个内容提供者，这样任何应用程序都可以访问它（如果它有适当的权限）。最后，广播接收器组件接收来自系统或其他应用程序的消息（例如，系统已经收到了一条短信）。具体来说，每个组件都是一个Java类，它继承自一个特定的超类，如活动、服务等。图2.2表示一个由三个活动和一个广播接收器组成的Android应用程序。

　　Android应用程序的组件通常使用特殊的系统方法进行通信，这些方法称为组件间通信（ICC）方法。 大约有40个ICC方法，一个组件可以用来与另一个组件通信。 最常用的ICC方法是startActivity(Intent)。 这个方法用来告诉系统启动一个由该方法的参数描述的新活动组件。

　　通信可以发生在单个应用程序的组件之间或多个应用程序的组件之间。当组件A想与组件B通信时，它初始化一个Intent并将组件B设置为目的地。这种通信被认为是显式的，因为目标组件是明确规定的。通信也可以是隐式的，在这种情况下，源组件用它想执行的动作来初始化Intent（例如，查看pdf文档）。当组件发送Intent时，系统会检查在其意图中是否有该动作的组件。目标组件的选择可以由系统自动完成，如果有多个组件可以处理该动作，则可能需要用户干预。例如，如果图2.2中的Activity3发送了一个带有 查看txt 动作的Intent，系统就会启动Activity2，因为它是唯一具有 查看txt 意图的组件。Intent可以将数据以键/值对的形式封装在称为Bundles的对象中。 Intents被用于活动、服务和广播接收者之间的通信。

　　URI。 URI，即统一资源识别器，用于识别抽象或物理资源[19]。简而言之，URI被用来与内容提供者通信。它们也可用于初始化针对特定资源的意图。以下面的URI为例：tent://comandroid calendar/events。它可以被切割成三个部分。第一部分，内容，称为方案，确定了如何访问资源。读者可能已经知道通过HTTP协议访问网页的http方案。这里，内容意味着对资源的访问是通过内容提供者完成的。第二部分，com .android .calendar，称为au- thority，标识了资源的持有者。读者可能熟悉诸如样的权威机构，它识别互联网上的一个注册主机。在我们的例子中，权威标识了被称为com .android .calendar的内容提供者，它已经被注册到Android系统中。最后，事件，称为路径，是识别目标资源的部分。读者可能熟悉诸如index .html这样的路径来识别网页资源。在我们的例子中，这就是内容提供者的数据库表事件。

　　清单以组件的形式描述应用程序的结构。 一个组件可以被导出，以便其他应用程序可以使用它。它还可以声明意图过滤器，以便向系统指定它所处理的行动或数据的种类。 清单还列出了应用程序要求的所有权限（如INTERNET、GPS）。图2.3展示了一个清单的例子。它声明了一个有一个内容提供者、一个服务、一个活动和一个广播接收器的应用程序。 该服务只接受带有动作SyncAdapter的意图，活动意图带有动作MAIN和类别UNIT_TEST，广播接收器意图带有动作BOOT_COMPLETED。该清单为应用程序声明了一个权限：INTERNET权限。

　　安卓系统的启动过程如图2.4所示。当安卓设备被打开时，CPU首先执行启动加载程序，初始化RAM（随机存取存储器）和硬件，然后加载内核并跳转到它。内核初始化驱动程序，挂载根系统并启动第一个进程：init。init进程挂载所有ile-系统，设置ile-系统的权限，并启动本地守护程序。 本地守护程序是在后台运行的程序。这些程序包括管理所有蓝牙设备的bluetooth d（蓝牙守护进程）和Rild（无线电接口层守护进程），它是无线电设备（例如全球移动通信系统的无线电设备）的接口。 一个本地守护进程，app_process，启动Dalvik虚拟机的一个实例，并初始化Zygote，一个用于分叉新的Android应用程序的程序。当Zygote启动时，它启动了系统服务器，这是一个初始化所有系统服务的进程6（例如GPS的系统服务），并启动活动管理器。最后，活动管理器启动主页应用程序。

　　在这一点上，用户面对的是主应用程序的图形界面。 这个图形界面显示设备上安装的Android应用程序的图标。当用户点击一个图标时，主应用程序调用startActivity方法。 活动管理器处理这个方法调用，并要求Zygote分叉自己，以创建和启动与用户点击的图标相对应的新的Android应用程序。

　　当启动顺序完成后，Android系统已经被初始化，其内核正在运行图2.5中所示的进程。 左边是一个进程的堆栈，上面是bluetoothd进程。在bluetoothd进程的右边是服务管理器进程，它被提前使用，因为它被系统服务器用来注册系统服务。这些都是由init进程启动的本地守护进程。在中间的是Zygote，用于启动新的Android应用程序的进程。Zygote启动的第一个进程是系统服务器，它初始化、向服务管理器注册，并运行所有的系统服务。最后，在图的右边是一个代表Android应用程序的堆栈。第一个运行的Android应用程序是Home应用程序。通过Home应用的界面，用户可以启动其他的Android应用。

　　Zygote、系统服务器和Android应用程序堆栈正在运行一个带有Dalvik虚拟机的进程，执行Dalvik字节码。 该虚拟机也可以通过Java本地接口（JNI）执行本地代码或共享库。另一方面，本地服务不运行一个Dalvik虚拟机。

　　本地服务和Zygote以根用户的身份运行。系统服务器以系统用户的身份运行，以遵守最小特权原则[113]（例如，作为一个普通用户，系统用户不能访问其他用户的数据）。正如在第2.1.2节中已经提到的，Android应用程序作为普通用户运行，每个应用程序分配一个用户ID。

　　Android系统运行Android应用程序。这些应用程序可以访问系统资源，如GPS、联系人列表或摄像头。安卓系统用权限来保护系统资源。如果应用程序没有适当的权限，系统就会阻止它们访问某个资源。

　　图2.6说明了一个安卓应用如何访问GPS资源。 GPS资源需要特定的硬件，因此需要一个内核驱动来向硬件发送命令。一个Android应用程序在Dalvik虚拟机中运行，可以通过JNI执行本地代码。理论上，应用程序可以使用本地库，通过适当的内核驱动程序与设备直接通信。 图2.6中的虚线表示从应用程序到设备驱动的这种通信。然而，这种直接通信是Android系统所不允许的，因为应用程序是作为普通用户运行的，而驱动只能由系统用户读写。

　　相反，应用程序必须通过绑定器驱动程序与系统服务器进行通信（关于应用程序访问绑定器的技术细节被Manager类所隐藏）。 由于绑定器是作为内核模块运行的，它可以向系统服务器证明调用应用程序的用户ID（也就是说，应用程序不能伪造它的ID）。然后，系统服务器检查调用程序是否有权访问该资源（即有正确的Android权限）。如果没有，那么系统服务器就会抛出一个异常，通信结束。如果它有，系统服务器就会与驱动程序对话，获取信息并将其送回给调用者应用程序。由于系统服务器是以系统用户身份运行的，所以允许对驱动程序进行访问。

　　权限被分为四类或权限级别：正常、危险、签名和签名或系统。正常权限保护对用户来说风险较低的资源（例如，读取电池状态的权限）。危险权限保护的是那些一旦被窃取就会对用户造成伤害的资源（如联系人列表）或使其损失的资源（如发送短信）。安卓系统只授予应用程序一个签名权限，如果它的签名与声明该权限的应用程序所使用的签名具有相同的认证。安卓系统只授予应用程序签名或系统权限，前提是它与声明权限的应用程序的签名证书相同，或者该应用程序在安卓系统镜像中。

　　Android 4.2定义了200个权限。其中，29个权限级别为正常，47个权限级别为危险，63个权限级别为签名，61个权限级别为标志或系统。在实践中，大多数时候，开发者只处理正常和危险权限（29+47=76个权限）。

　　流行的编程语言，如Java，使用类和方法来表示现实世界的概念，并分别操作这些概念（即改变其状态）。对使用类和方法构建的程序进行静态分析，可以使用程序内方法（即逐个方法）或程序间方法（即把方法连接在一起，把程序作为一个整体进行分析）。后面的方法需要连接方法。这可以通过计算程序的调用图来实现。

　　在本节中，我们将介绍调用图的构造，并着重介绍面向对象的语言，特别是Java语言，因为我们在第四章和第五章中分析了这种语言的代码。

　　在面向对象编程中，程序是由类组成的。每个类代表一个概念（如汽车），有一组表示其他对象（如车轮）的单元和一组包含操作对象的代码的方法（如驱动汽车前进）。 代码可以调用其他方法来创建对象的实例或操纵现有对象。

　　一个程序通常以一个叫做主方法的单一入口点方法开始。 通过分析主方法的代码，我们可以找出它在调用哪些方法。然后，通过分析被调用方法的代码，我们可以找出它/它们在调用什么方法。只要有方法调用其他方法，这个过程就可以重复进行。

　　其结果是一个有向图，称为调用图，它将方法联系在一起。 该图从代表主方法的节点开始，通过被调用的方法向下扩展。

　　图2.7说明了一个Java程序的调用图生成过程（a）。 有两个Java类，MyObject和MyOtherObject。程序的起点是MyObject中的main方法。这个主方法也是调用图的起点（b）。主方法首先通过调用MyOtherObject的构造方法（Java中的init方法）创建一个实例。 然后它在新创建的对象上调用方法method1和method2。方法1不调用其他方法，只调用自己。方法2只调用大小。方法3不能从主方法中到达，因此没有出现在调用图中。

　　继承和多态 面向对象的语言，如Java[61]，使用了诸如继承和多态的概念。图2.8说明了这两个概念。继承是对一个抽象概念（这里是抽象的动物类）进行建模，然后将这个抽象概念扩展到这个抽象概念的具体元素（这里是人类和猫类）的能力。这个抽象概念通过行走方法定义了一个行为。人类和猫咪都在行走，但它们以不同的方式在自己的行走方法中描述。

　　假设我们用Java语言建立一个由猫和人组成的世界。我们将把对猫和人的每一个引用存储在一个动物的容器中。 动物通过迭代容器中的元素并对其调用行走方法来进行行走。当执行这段代码时，如果动物是人类，对动物的行走方法调用将被重定向到Human .walk，如果动物是猫，则重定向到Cat .walk。为不同种类的实体提供一个单一的接口被称为多态性。在分析一个Java程序时，处理多态性的方式对调用图的精度有直接影响。

　　流程敏感度 流程敏感度分析考虑到了语句的顺序。以图2.9a的代码片断为例。在第二行，一个新的Human实例被创建，并被动物引用a引用。在第三行，方法walk被调用到a上。这意味着在执行时只有方法Human .walk在第三行被调用。 在第四行，a现在引用了一个新的猫的实例。在第三行，一个ow-sensitive分析给出了a只指向一个Human对象，而不是一个Cat对象。 因此，ow-sensitive调用图包含一条通往Human .walk的边。另一方面，一个不敏感的分析给出了a可能指向Human或Cat对象，因为它不考虑语句的顺序。对于一个不敏感的分析，在第二行和第三行之间有第四行的程序会得到同样的结果。因此，ow-insensitive调用图包含两条边：一条指向Human .walk，另一条指向Cat .walk。

　　路径敏感性 路径敏感性分析将执行路径考虑在内。 以图2.9b的代码片断为例。 在第二行，动物引用a指向没有对象。如果第三行的条件为真，a指向一个新的人类对象（第四行）。如果第三行的条件为假，a指向一个新的猫对象（第六行）。对这个例子进行路径敏感的分析会产生两条路径：路径1 , l2 -l3 -l4 -l8，和路径2 , l2 -l3 -l6 -l8。在第八行，path1有一个指向Human对象的指针，因此方法Human .walk在调用图中。路径2有一个指向猫对象的指针，因此方法Cat .walk在调用图中。对路径不敏感的方法不考虑路径，在第八行会有一个指向Human对象和Cat对象的指针。因此，对路径不敏感的调用图将包含Human .walk方法和Cat .walk方法。 一个对路径敏感的方法可以为每一个可能的路径产生一个图。路径的数量会呈指数级增长，这种方法也就不具有可扩展性。

　　场敏感度 场敏感度方法对每个对象的每个场进行建模。以图2.9c的代码片段为例。 在第二行，c1指向一个新的C对象。 这个对象包含两个动物字段。在第三行，第一个字段，f1，指向一个新的人类对象。在第四行，第二个字段，f2，指向一个新的猫对象。 一个对字段敏感的分析为每个对象的每个字段建模。因此，在第i行，f1的模型只能指向一个Human对象，并且只有Human .walk方法在ield敏感的调用图中。基于字段的方法只对每一类对象的每个字段进行建模。 这意味着在这个例子中，ield c1 .f1和c2 .f1有相同的模型。因此，在第ive行，f1指向一个Human对象和一个Cat对象，Human .walk和Cat .walk这两个方法都在ield-不敏感的调用图中。 最后，请注意，一个不敏感的方法只对 对象 进行建模。所有的元素都被聚合到它们相应的对象上。不敏感的方法不太可能用于Java这样的语言，而只能用于具有类型不安全的指针操作的语言，如C。

　　上下文敏感度 上下文敏感度方法对方法被调用的每个上下文进行建模。 对上下文进行建模的主要方式有两种：对调用地点进行建模，这在本段中有所描述；对方法调用的分配地点进行建模，也称为对象敏感，在下一段中有所描述。以图2.9d的代码片段为例。在第二行，一个人类对象被实例化了。 变量h指的是这个对象。 在第三行，一个猫对象被实例化。变量c指的是这个对象。在第四行，用c调用方法，该方法返回存储在a中的动物引用。在第五行，用h调用方法，该方法返回存储在a中的动物引用。也就是说，对于第一个方法的调用，参数模型指向c，返回值模型指向c；对于第二个方法的调用，参数模型指向h，返回值模型指向h。另一方面，对于一个给定的方法，上下文不敏感的方法只有一个参数模型和一个返回值模型。在上下文不敏感的方法中，参数模型指向c和h，返回值指向c和h。因此，上下文不敏感的方法在调用图中既有Human .walk方法，也有Cat .walk方法。

　　对象敏感度 对象敏感度方法是一种上下文敏感度方法，它区分了对不同对象进行的方法调用。以图2.9e的代码片断为例。在第二行和第三行，两个Contains对象被实例化了。变量c1和c2指的是这些对象。Contains类有一个动物类型的实例ield animal和一个实例方法setAnimal，用于将一个值与ield animal联系起来。在第四行，方法setAnimal被调用到c1，参数为Human对象。在第5行，方法setAnimal在c2上被调用，参数是猫对象。最后，在第六行，方法walk被调用到对象c1的animal ield。在第四行和第五行，一个对对象不敏感的方法会认为c1和c2是同一个接收器。其结果是，第四行和第六行的方法调用不能区分接收器，并将c1和c2作为一个独特的含有类型的对象cu的模型。因此，在第六行对对象cu调用的方法walk在调用图中由两个方法表示： Human .walk和Cat .walk。另一方面，一个对对象敏感的方法将为setAnimal的每次调用分别建立c1和c2的模型。因此，第六行的调用在调用图中只由方法Human .walk表示。

　　不可知性 使用静态分析来确定哪些指针在运行时可以指代哪些对象的问题是不可知的[77]。这意味着对于所有的程序来说，都无法计算出精确的解决方案（即，既合理又完整）。然而，存在许多保守的解决方案。这些解决方案是合理的，因为它们计算的是 真实 结果的超近似值。正如我们在上面的段落中所看到的，它们在精度上是不同的（也就是说，有些方法比其他方法产生更多的假阳性结果）。例如，一般来说，上下文敏感的方法比上下文不敏感的方法更精确。

　　Java是一种面向对象的语言，支持多态性。因此，在进行程序静态分析时，方法被调用的对象的确切类型（这种对象也被称为接收器）可能并不为人所知。在下面的段落中，我们将介绍一些静态地构建Java程序调用图的算法。

　　CHA 第一种方法叫做类层次分析（CHA），由Dean等人提出[39]。该方法是非常保守的，它假定对于一个给定的接收器，接收器的声明类型T以及T的所有子类型（例如所有子类）在运行时都是可能的类型。例如，当在一个程序上运行CHA时，该程序有一个对动物类型的接收器r的方法调用walk()，CHA假定动物、人类和猫在运行时是r的可能类型。即使在分析的程序中没有实例化的猫对象，情况也是如此。

　　RTA 后来，Bacon等人提出了一种叫做快速类型分析（RTA）的方法[10]。这种方法与CHA类似，但是只有在被分析的程序中创建了T类型的对象时，才会将T类型视为可能的类型。例如，当对一个有方法调用walk()的程序运行RTA时，RTA假设动物、人类和猫在运行时是r的可能类型，当且仅当人类和猫的对象在分析的程序中的某个地方被创建。

　　VTA Sundaresan等人[126]后来提出了另一种方法，称为可变类型分析（VTA）。这种方法比CHA或RAT更精确，因为它只考虑能到达接收器的类型作为可能的类型。

　　Andersen Andersen算法[2]的Java扩展[83, 110]进行了对字段敏感的基于子集的点到分析。点到分析描述了一个指针表达式可能指向哪些内存位置（即局部变量、全局变量和动态分配的内存）。一个调用图几乎可以直接从点到分析的结果中计算出来。如上所述，一个对字段敏感的方法对每个创建的对象的每个字段进行单独建模。给定一个语句，如a = b，一个子集方法增加了以下约束：a ⊇ b。这意味着b的点到集是b的点到集的一个子集。该算法收集了所有这样的约束，并使用一个工作表来解决这些约束并为所有指针构建点到集。在现实的Java程序上，类似Andersen的指针分析的最坏情况下的复杂度是四次方的[122]。

　　Steensguard 与Andersen的算法相反，Steensguard的算法[124]是基于平等的。这意味着，它使用的不是子集约束，而是平等约束。 这个约束意味着a的点到集与b的点到集相同。这个方法不如Andersen的精确，但更具有可扩展性（接近线]）。

　　其他方法 其他点对方法已经被开发出来[135, 119, 134, 64, 65]，以提高Andersen引入的基于子集的点对分析的效率，或者提高Steensguard引入的基于平等的点对分析的精度。有兴趣的读者可以参考[80]，了解这些方法的概况。

　　数据流分析[1]是一种在程序的每一个点上计算一组可能的值的技术。 这组值取决于使用数据流分析所要解决的问题的种类。 例如，在达到定义问题中，人们想知道在每个程序点上可达到的定义（例如，int x = 3;这样的语句）的集合。 在这个特定的问题中，程序点P的可能值集合是到达P的脱式集合（即变量在到达P之前没有被赎回）。以图2.10为例。第二行的定义到达第三和第四行，但没有到达ive，因为变量x在第四行被重新定义。第三行的删除到达第四行和ive。第4行的删除到达第ive行。

　　数据流分析使用一个方程系统来计算每个程序点或语句的信息。 每个语句都有一组可能的值，称为in，它代表了语句之前的有效信息。每条语句都有一组可能的值被叫出来，这代表了语句之后的有效信息。每个语句都有一个方程，描述语句对in集的影响。语句Stmt可以创建由Stmt.gen表示的新的可能值，并杀死现有的值，由Stmt.kill表示。

　　前向和后向 达成定义的问题是用前向分析来解决的。这意味着分析从程序的第一条语句开始，一直向前走，直到到达程序的终点。其他问题则采用后向分析法解决，即从最后一条语句开始分析，并向后追溯到第一条语句。

　　到目前为止，我们一直在研究程序内（即在单个方法内）的数据运算分析。程序间分析则是对相连的程序（或Java中的方法）进行分析。正如我们在第2.2.1节中所看到的，计算一个调用图可以得到关于方法是如何连接的信息。

　　为了说明程序间分析，我们依靠程序间有限分布子集（IFDS）框架[106]。IFDS框架通过将问题转化为图-可达性问题，在多项式时间内解决问题。用于解决该问题的算法被称为 制表 算法。它比以前的方法，如 迭代 或 调用字符串 算法[87]有所改进，后者在最坏的情况下可能需要指数时间。

　　IFDS 以图2.12为例。 这个例子来自[106]，说明了程序间可能未初始化的变量的数据流问题。 在这个例子中，我们假设方法read(a)是一个系统方法，读取一个整数并将其存储在局部变量a中，方法print(a,b)是一个系统方法，在屏幕上打印出整数a和b的值。图2.12b分别表示方法main和p的控制ow图。

　　图2.12代码的调用图显示，方法main在第6行调用方法p，方法p在第13行调用自己。每个方法的调用由两个节点表示：调用节点c和返回点节点r。通过添加三条边来连接这些方法：一条从c到r的程序内边，一条从c到被调用方法开始节点的程序间边，一条从被调用方法退出节点到r的程序间边。图2.12中的例子的超图表示在图2.13中。

　　可能未初始化的变量的数据流事实集是每个方法中可用的局部和全局变量集。方法main有局部变量x和全局变量g。方法p有局部变量a和全局变量g。每个语句对数据流事实集的影响由图中每条边的函数表示。例如，read(x)的效果是初始化变量x，该函数用λS表示。（S-{x}）。这意味着数据流事实的输出集是输入集S，其中元素x被移除。事实上，由于x现在被当前语句初始化了，它可以从潜在的未初始化的变量集合中删除。类似地，语句a = a - g由函数λS表示。如果（（a∈S）或（g∈S）），那么（S∪a），否则（S -{a}）。这意味着，如果a或g在输入集中，输出集就是输入集加上元素a（即a也是无因的）。否则，输出集是输入集，其中的元素a被移除（即a和g都没有被剔除，所以a的新值不能被剔除）。

　　IFDS框架将每个ow函数f表示为一个包含以下边集的图： {(0, 0)} ∪ {(0, y) y∈f(∅)} ∪ {(x, y) y∈f(x) and y f(∅)}。 上一段描述的两个函数在表2.1中被表示为图形。一旦所有的函数都被表示成紧凑的图，它们就可以被组合起来形成爆炸的超图。图2.14说明了爆炸的超级图。该图将IFDS问题转换为图-可及性问题。 简而言之，如果爆炸超图的一个节点可以从主方法的入口节点到达，这意味着与之相关的数据流事实成立。例如，方法main中语句p(x)的变量g的节点可以从main方法的enter节点的0处到达。这意味着在main方法中的语句p(x)，变量g有可能是未初始化的。

　　IDE IFDS框架处理的问题是：数据流事实集D是有限的，数据流函数在2D→2D中。这个框架足以解决诸如 达到定义、可用表达式 或 可能未初始化的变量 等问题。然而，有些问题如 线性常数传播 问题不能用IFDS框架来编码，因为数据流事实的集合是无限的。

　　程序间分布式环境（IDE）框架[111]解决了程序点上的数据流信息由 环境 表示的问题。换句话说，数据流事实是从一个有限的符号集D到一组值L的映射。这种映射被称为环境，并被称为Env(D, L)。数据流函数被称为 环境转化器，其形式为Env(D, L) Env(D, L)。

　　IDE框架是IFDS框架的概括：所有IFDS问题都可以表示为IDE问题，但并非所有IDE问题都可以表示为IFDS问题。一个IDE问题可以由一个超图G（对于一个给定的程序，IDE超图与IFDS超图相同）、一组程序符号D、一个半晶格L和一个环境变换器对G的边的分配来表示：M：E→（Env(D, L) Env(D, L)）。

　　在本章中，我们首先介绍了Android系统和Android应用的结构。这些领域的知识对于充分理解第4、5和6章是必要的，这些章节的方法总是应用于Android框架或Android应用。然后，我们介绍了静态分析的概念，如调用图构建或程序间分析。调用图构建是第四章中介绍的Android框架分析的基础，而第五章则主要依赖于程序间分析。

　　本章的目标是使Android应用程序的静态分析成为可能。 本章介绍了Dexpler这个软件模块，它将Dalvik字节码（即Android应用程序的代码）转换为Jimple。Jimple是Soot的内部代码表示，是最流行的基于Java程序的静态分析工具之一。将Dalvik字节码转换为Jimple能够对Android应用程序进行静态分析和转换。

　　Android应用程序是用Java编写的。然而，它们不是以Java字节码的形式发布的，而是以Dalvik字节码的形式发布的。分析Android应用程序的一种可能性是使用Dalvik反汇编程序，如Smali [62] 或Androguard [41]。然而，它们并不是为执行高级静态分析而设计的，比如数据流分析，而且它们通常使用自己的字节码表示，这使得它们无法使用现有的工具来执行分析。 此外，用现有的Java静态分析工具来分析Android应用程序意味着必须有Android应用程序的Java源代码或Java字节码。

　　大多数时候，安卓应用的开发者并不分发他们应用的源代码，使得现有的Java程序分析工具无法对安卓应用进行分析。这对恶意软件的应用来说尤其如此，因为它们的源代码几乎是不可用的。

　　分析Android应用程序的另一种可能性是首先将Dalvik字节码转换为Java字节码，使用Ded[47]、Dex2jar[99]或undx[115]，然后使用Java定制的静态分析工具，如Soot[131]、BCEL[35]或WALA[70]。产生Java字节码的工具可以利用现有的Java字节码分析器。然而，从Dalvik到Java字节码的转换需要时间，可以通过直接将Dalvik字节码转换为工具的内部表示来避免。

　　为了克服这些限制，我们引入了Dexpler1，这是Soot的一个模块，它直接读取Dalvik字节码，将其转换为Jimple，即Soot的内部代码表示法，并对Jimple表示法的局部变量进行完全类型化。然后，任何静态分析和/或转换都可以应用于Jimple表示。 使用这种方法消除了从Dalvik到Java字节码的中间转换步骤，可以使用更快更简单的工具链进行静态分析。

　　本章的提醒内容组织如下。第3.2节是对Dalvik字节码的概述。在第3.3节中，我们描述了Dexpler，这个软件使Soot能够分析Dalvik字节码。在第3.4节中，我们在超过2.5万个Android应用程序上评估了Dexpler，介绍并讨论了结果。第3.5节解释了我们工具目前的局限性。最后，我们在第3.6节中总结了本章并讨论了开放的研究挑战。

　　一个Android应用程序是一个包含应用程序字节码的压缩包，描述应用程序结构的An- droid清单，它需要的组件和许可，以及数据文件（例如，图片，声音）。 在本节中，我们关注的是包含应用程序的Dalvik字节码的ILE，参照ILE名称的扩展，也称为dexILE。即使原始的Android应用程序是用Java编写的，在Android应用程序中也找不到Java字节码。Java代码首先被编译成Java字节码，然后由dx工具2转化成Dalvik字节码。使用Dalvik字节码背后的原因是，它是基于寄存器的，并为运行在内存和处理能力不足的设备上进行了优化。 dex ile的结构在第3.2.1节中描述。第3.2.2节介绍了Dalvik指令。然后，在第3.2.3节中解释了Dalvik字节码的规格。

　　在本节中，我们首先描述了Java类的结构。然后，我们描述从Java类中生成包含所有Dalvik类的dex ile的过程。

　　Java类 如图3.1a所示，每个Java类只有一个储存常量值的地方（常量池）。在Java中，常量池是异质的，因为不同类型的对象是混合的（例如，类，对方法的引用，整数，字符串）。 每个Java类都包含一个常量池。

　　Dalvik类 一个Dalvik可执行文件是由dx编译器处理的N个Java字节码类生成的。产生的Dalvik字节码被存储在一个.dex ile中，如图3.1b所示。dex ile包含对Dalvik类的描述（名称、元素、方法...）和Dalvik字节码（代表具体方法代码的结构）。此外，dex ile包含四个同质常量池：字符串、类、字段和方法。所有的Dalvik类都共享这四个常量池。此外，一个.dex ile包含多个Class Dehni- tions，每个都包含一个或多个Method dehnition。每个Method dehnition都与存在于数据部分的Dalvik字节码指令相联系。

　　Java虚拟机是基于堆栈的。这意味着操作数是根据指令的语义从堆栈中推送和弹出的。另一方面，Dalvik虚拟机是基于寄存器的。这意味着大多数指令指定了它们所操作的寄存器的名称。这使得Dalvik字节码在语法上接近于Jimple代码，因为Jimple也使用基于寄存器的代码表示。图3.2.a表示Java字节码，其中值被推到堆栈，而图3.2.b表示Dalvik字节码，其中值被分配到寄存器v0和v1。

　　在Dalvik操作码常量列表中，有237个操作码。然而，12条odex（opti- mized dex）指令不能在Android应用程序的Dalvik字节码中找到，因为它们是在Android系统中生成的不安全指令，用于优化Dalvik字节码。 此外，还有8条指令从未在应用程序代码中被发现[94]。根据这些数字，在实际应用中很可能只有217条指令。

　　这组指令可以分为提供其操作的寄存器类型的指令（例如，sub -long v1, v2, v3增加两个长寄存器并将结果存储到一个长寄存器）和不提供类型的指令（例如，const v0, 0xBEEF在寄存器v0中存储一个未定义类型的值）。此外，null和0之间没有区别，它们都被表示为0值。

　　在这一节中，我们强调了Dalvik字节码的特征，这些特征对字节码寄存器的类型解析有影响。请注意，当我们提到Dalvik字节码变量时，我们使用术语寄存器，当提到Jimple变量时，我们使用术语局部或变量。

　　在Java字节码中，基元变量是由一条指令初始化的，该指令规定了它的类型（例如，int, oat, long, double）。但在Dalvik中却不是这样，常量的初始化没有类型信息。图3.3中的代码片段突出了Java和Dalvik字节码之间的差异。在Java中，类型可以在每条指令中确定：整数常量是通过整数的特殊指令初始化的，而燕麦常量是从常量池中加载的，它们被标记为适当的类型（例子中的燕麦）。然而，在Dalvik中，类型信息无法在常量初始化指令中确定。然而，对于算术操作，Dalvik使用指令来指定操作数的类型。寄存器的类型也可以在它作为方法参数时被确定，因为每个被调用的方法的符号都会显示其参数的类型。简而言之，当分析Dalvik字节码时，只有当寄存器被使用时才能确定由常量初始化的寄存器的类型。

　　此外，在Dalvik中，Oat和整数常量都是以32位编码的。如图3.4所示，如果一个寄存器被32位常数初始化，那么该寄存器的使用仍然需要被分析以确定寄存器的类型。同样的，long和double常量都是以64位编码的。因此，一个64位的常数分配给一个寄存器并不能直接给出寄存器的类型。然而，分析寄存器的使用方式将给出寄存器的类型。

　　Null被分配给一个对象的引用，表示它没有引用。在Java字节码中，Null是通过一个特殊的加载常量指令（见图3.2.b）和两条if指令来处理的，以检查一个对象引用是否为null或非null。在Dalvik字节码中，没有这样的指令：null被表示为整数值0。检查一个对象引用是否为空或者非空包括检查对象引用是否是一个等于零或者不同于零的整数。图3.2表明，在Java源代码（a）和字节码（b）中，0和null之间有明显的区别，而在Dalvik字节码（c）中，根本没有区别。正如我们将在第3.3节中看到的，在将Dalvik字节码翻译成Jimple时，缺乏类型和null的表示方法就成了问题。

　　在Dalvik和Java字节码中，字节码包含异常处理程序。处理程序是方法的字节码中的一组特殊指令，当代码的某个部分抛出异常时，虚拟机会调用它。不处理Dalvik异常的特殊性就会导致代码无法打码。 这就是为什么我们在类型化过程中使用Dalvik的特殊异常模型，而不是原始的Java异常模型。

　　在构建方法的CFG时，我们必须从可能抛出异常的指令中添加边，以获得正确的异常处理程序的第一条指令。在Dalvik中处理异常的方式几乎与Java相同，但也有一些区别。在Java中，从一个方法返回的指令可以抛出一个异常，但在Dalvik中却不能。存储一个类常数和一个字符串常数的指令在Java中可以抛出异常，但在Dalvik中不能。关于数组，Dalvik只在索引超出范围或在数组引用上有一个空指针的情况下抛出数组指令的异常。

　　异常处理可以被认为是一个技术细节。然而，如果处理不当，就会破坏代码中变量的类型。 考虑一下图3.5中的代码。如果在label1和label2之间的指令可以抛出一个异常，就会调用label handler的处理指令。throw v4指令就是这种情况。如果Dalvik的返回指令被当作Java字节码的返回指令来处理，在CFG中就会有一条从返回指令之前的指令（即v1=Object getObject）到异常处理程序的边缘。这个边在图3.5中以虚线箭头表示。在这种情况下，当寄存器v1在处理程序中被使用时，其类型可能是int（来自getInt方法）和Object（来自getObject方法）。我们不可能获得这段代码的类型。

　　本节介绍Dexpler，Dalvik到Jimple的转换工具。 它利用Smali反汇编程序中的dexlib2库[62]来解析Dalvik字节码，并利用Soot快速打字，这是一个实现类型推理算法的Jimple组件[17]，来给局部变量打字。然而，类型推理算法在从Dalvik字节码自然生成的Jimple代码上不起作用。我们在第3.3.1节中描述了这个类型化问题。然后，我们在第3.3.2节中描述Dexpler如何解决这个问题。

　　图3.6表示Dalvik字节码的类型网格。 请注意，由于Dalvik字节码中的常量类型不为人所知，所以存在32位和64位的ab-stractions： 32位常量可以是Oat、char、short、byte、boolean或int类型（回顾图3.3，初始化指令不提供类型信息），64位常量是double或long类型。图3.7表示Java字节码的类型网格。在Java字节码中，oat、double、long和int的常量是通过指令指定其类型来初始化的。此外，在只能分配给对象的null和可以分配给int-like类型的值int 0之间有明显的区别。

　　我们的目标是将Dalvik字节码转换为Jimple，然后消除类型的模糊性，以便现有的类型化算法能够完全对代码进行类型化。 为了实现这一目标，我们考虑了图3.8所示的Dalvik类型网格的简化版本。 现有的类型化算法，如[18]，可以对对象和int的子类型进行类型化，所以我们没有在简化的网格中完全表示它们。 我们想从图3.8中的格子（代表Dalvik字节码中的类型）到图3.9中的格子，在那里类型之间不能有歧义。

　　更确切地说，我们要区分（1）作为null的0和作为整数值0的0，（2）作为整数的32位常量和作为燕麦的32位常量（3）作为双数的64位常量和作为长数的64位常量。

　　一旦变量的类型与图3.9所示的格子相匹配，类型的局限性就被消除了，完全的类型化算法就可以用来对变量进行完全类型化。

　　图3.10说明了将Dalvik字节码转换为Jimple代码并进行类型化的过程。 首先，原始的Dalvik字节码(1)被dexlib23库解析，每个指令都被反汇编(2)。 从这个中间表示法中，生成未定型的Jimple语句，并将其连接起来，形成控制流图（CFG）（3）。下一步（4）是解决模糊的类型。 最后，在步骤（5）中，使用Bellamy等人[18]提出的有效的局部类型推理算法对所有Jimple局部进行类型化。步骤（5）被用来验证我们的方法。下一节将详细描述步骤（4）。

　　我们在第3.2.3节中看到，以下指令缺乏类型信息：零值常量初始化指令（是零还是空？）和常量初始化指令（32位：整数还是燕麦？，64位：长还是双？） 下面通过看这些指令在代码中的使用情况来说明我们如何对这些指令的寄存器进行打字。

　　空值初始化 图3.12用图3.11的Java代码生成的字节码片段说明了这个问题。 寄存器v0在第01行被初始化为0。 在这一点上，我们不知道v0是一个整数、一个燕麦或一个对象的引用。在第02行，我们仍然没有得到答案。我们必须等到第04行的指令才知道v0的类型是Coordinate。 在这一点上，为01产生的Jimple指令必须被更新为一个空常数，而不是默认的数值为0的整数常数。 如果这一点没有得到正确处理，打字组件就会失败。 事实上，寄存器v0不可能既是一个整数又是一个坐标类型的对象。

　　数字常量的初始化 同样地，Oat常量的初始化不能与int常量的初始化区分开来，双倍常量的初始化不能与long常量的初始化区分开来。因此，我们通过Jimple语句的图形来了解常量的使用情况，并在需要时纠正Jimple语句的初始化。例如，如果一个oat/int常量（在Jimple语句中默认初始化为int）后来被用于一个oat加法，常量的初始化就会从int常量变为oat常量。

　　第1步：数组类型传播 对于每一个未定型的常数，我们要看的是用一个常数值初始化的局部变量的使用。局部可以存储在一个字段中，作为一个方法参数使用，并存储在一个数组中。 对于字段和方法，常量的类型是已知的，因为字段签名和方法签名提供了足够的类型信息。另一方面，对于一个数组来说，类型信息并不总是已知的。一个典型的例子是当数组被别名时（即分配给另一个局部）。

　　为了传播类型信息，我们从数组初始化语句开始。 对于每一个这样的语句，我们都要确定数组的使用位置。如果数组被别名，我们将类型信息从数组转移到新的局部。 当到达一个ix点时，所有本地引用的数组都被类型化了。

　　第二步：null和Zero 对于这一步，我们设计了第50页的算法1。该算法从方法nullOrZero（第1行）开始。 该算法首先收集语句，用一个值为0的整数来初始化局部变量（第3行）。 然后，对于局部变量的每一次使用，方法forEveryUse为局部变量的类型集（第5-6行）增加一个类型，要么是 作为对象使用，要么是 作为整数使用。如果一个局部变量的所有类型不一致（即它们不都是一样的），那么在该方法的字节码中就会出现类型不一致的情况，使其无法对字节码进行打字。在这种情况下，算法以错误代码结束（第8行），执行算法的代码会用一个默认的代码块来替换方法代码，这将抛出一个运行时异常。 另一方面，如果所有的类型都是一致的，那么局部变量的定义也会相应地被更新：如果常量被用作对象，那么零值会被替换为null（第10行）。

　　更确切地。