计  算  机  学  报  2019 年 are  launch-type-insensitive,  which  cannot  capture  special  launch  types,  thus  simulating  the  transitions  among different back stack states incorrectly and producing infeasible activity transition paths for the apps using special launch types. To address above mentioned problems, we formalize the changes of back stack states triggered by activity  launchings configured with 7 different launch types respectively, and propose activity  launching graph (ALG).  The  ALG  represents  activity  launchings  in  an  app  and  can  be  constructed  by  launch-type-sensitive activity  transition  analysis.  Launch-type-sensitive  activity  transition  analysis  first  constructs  a  harness  main(), which consists of one allocation site per activity class and all overridden callback calls organized according to control flows. Then the object-oriented field-sensitive point-to analysis is conducted to extract the target activity classes  for  activity  launchings  and  launch  type  related  configurations.  Finally,  for  each  activity  launching,  an edge from source object to target object is constructed with determined launch type. Moreover, we propose and implement  a  framework  named  ALCAnalyzer  to  conduct  the  static  ALC  analysis.  ALCAnalyzer  can  generate ALGs  for  Android  applications  automatically  and  generate  the  set  of  ALCs  based  on  an  ALG.  Based  on  the maximum number (infinity, two, and one) of activity instances produced for an activity class in the back stack by repeated  executions  of  ALCs,  the  ALCs  can  be  divided  into  three  types  (TYPE1,  TYPE2,  and  TYPE3).  This paper summarizes the characteristics of different type of ALCs. ALCAnalyzer can simulate the changes of back stack states accurately during the repeated executions of ALCs and predict whether there are multiple instances of an activity class in a back stack state at runtime by determining the type of an ALC. Experimental evaluations consist of two parts. The first part is conducted on 1179 open source Android applications from F-Droid. Manual examinations  on  the  results  of  ALCAnalyzer  analysis  show  the  high  precision  of  our  launch-type-sensitive activity transition analysis. We also conduct studies on the ALCs in different kinds of apps in the first part of our experiments.  The  results  indicate  that:  ALCs  and  special  launch  types  are  widely  used  in  Android  apps;  more than half of the ALCs can produce multiple activity instance for an activity class, which request reasonable back stack  managements;  more  than  sixty  percent  of  the  ALCs  are  longer  than  two  which  are  difficult  to  identified manually and requests a tool to identify them automatically; news- and reading-related apps are more complex in structure.  The  second  part  of  experiments  is  conducted  on  20  apps  from  Google  Play.  The  results  show  that comparing with launch-type-insensitive activity transition analysis, ALCAnalyzer can model the changes of back stack  states  more  accurately,  and  ALCAnalyzer  can  also  provide  the  software  engineers  with  more  effective information to manage the back stack behaviors to make user experience smoother and more consistent. Key words  Android applications; activity launching graph; launch type; back stack; activity launching cycle  1  引言 近几年，人们已经见证了移动设备在各个领域的广泛应用。Android 系统是移动设备中最为流行的系统之一。Android 平台上的应用软件类型丰富，数量庞大，且层出不穷。Activity 作为 Android 应用(Android application，简称 app)重要组件之一，负责提供用户交互功能的界面窗口。软件运行过程中产生的 activity 实例以栈的形式组织在返回栈中，以便用户正确返回上层界面。用户通过与返回栈最顶端实例进行交互来完成 activity 间的跳转。Activity跳转由activity的启动和返回动作触发。不同activity类间的启动关系，构成了一个 app 的整体框架。本文关注于 activity 循环启动所构成的一种特殊结构，activity 启动环(activity launching cycle，简称 ALC)。 ALC 的重要特性是其存在允许 app 在被使用过程中多次启动同一 activity 类。默认的 activity 启动方式（standard）要求 Android 平台创建一个目标activity 的新实例并压入返回栈，所以返回栈中可能出现同一类型 activity 的多个实例。过多的同类型activity 实例会占用大量系统资源，以致出现卡顿甚至闪退；另外，同类型 activity 实例也会使得用户回退操作繁复，影响用户体验[1]。Android 平台提供了多种特殊配置，使得 ALC 中的 activity 以特殊的启动方式启动。这些特殊启动方式要求系统在软件使用过程中重用或清除特定 activity 类的实例，以避免同类型 activity 实例的产生。例如：activity  A以 singleTop 的方式启动 A，构成了 activity 启动环ALC1。Android 平台并不会在执行 ALC1 时向返回计算机学报刘奥等：Android 应用 Activity 启动环研究  3 栈中压入一个 A 的新实例，而是重用栈顶实例。通过对大量开源应用中 ALC 的调研，本文根据持续重复执行 ALC 产生同类型 activity 实例的三种情况，将 ALC 归纳为 3 类。准确对 ALC 进行分类，能够帮助开发人员调整 ALC 中的启动方式，合理管理返回栈以提升软件质量。 如上所述，开发人员为了完成特定功能，追求更流畅便捷的用户体验，常在 ALC 中使用特殊启动方式。然而当前 activity 跳转静态分析方法[1-5]对启动方式不敏感，即它们假设所有的 activity 均以默认启动方式被启动。所以若 ALC 中使用了特殊启动方式，当前分析方法则无法正确模拟其引起的返回栈状态变化，也就无法正确模拟返回动作所触发的 activity 跳转以及无法对 ALC 正确分类。另外，基于 activity 跳转路径的研究与应用中，包含错误activity 跳转的非法 activity 跳转路径会带来意料之外的错误，比如 GUI 测试和缺陷检测中的测试用例执行失败[5-8]。 为了弥补当前 activity 启动关系相关分析对启动方式不敏感的缺陷，解决返回栈模拟不正确、产生非法 activity 跳转路径的问题，并正确判定 ALC类别，本文：1)  深入研究了 activity 启动环使用的特殊启动方式，并形式化表示了以 7 种不同启动方式启动 activity 带来的返回栈变化。2)  提出 activity启动图（activity  launching  graph，简称 ALG），该图节点表示 activity 对象，有向边表示 activity 间的启动关系且记录了启动方式。ALG 可以被用于多种上层研究，比如 Android 应用动态探索[2,3,9]，GUI模型构建[5,8]，漏洞挖掘[10-16]，缺陷检测[6,7,17,18]等。3)提出启动方式敏感的 activity 跳转静态分析方法用于自动构建 ALG。4)  提出基于 ALG 的 ALC 定位算法和 ALC 分类算法。 对 Android 应用进行启动方式敏感的 activity跳转分析从而构建 ALG 是本文工作的关键也是难点所在。Android 平台使用 intent 对象来帮助进行组件间通信（inter-communication call,  简称 ICC），从而启动目标组件。为了确定目标 activity 和提取部分启动方式相关配置，需要通过指向分析来解析intent 对象的字段内容。与典型 Java 程序只有一个入口不同，Android 应用程序包含大量回调函数，用户和系统动作都会触发相应回调，即 Android 应用程序包含多个入口。因此，如何有效处理 Android程序的事件驱动复杂控制流是指向分析需要克服的挑战。另外，由于 Android平台提供大量系统 API，很多代码被隐藏，使得对 Android 应用进行精准的指向分析更加困难[1-4,11,13,16,19-21]。 本文提出并实现了如图 1 所示的 ALC 静态分析框架 ALCAnalyzer 来完成 ALG 构建，ALC 定位和 ALC 分类。ALG 生成器为 Android 应用构造辅助主函数：为每个 activity 类构造一个对象的堆内存分配点，对于每个 activity 对象，依据控制流组织被重写的回调函数调用顺序。之后通过面向对象的字段敏感指向分析构建 activity 对象的启动图。ALC 生成器以 ALG 为输入，定位 ALG 中全部 ALC并输出 ALC 集合。返回栈模拟器能够模拟 7 种activity 启动方式对返回栈的影响。ALC 分类器被集成在返回栈模拟器中，根据每次模拟执行 ALC后返回栈的状态来判断 ALC 的类别，最终给出 app在运行过程中可能产生多个实例的 activity 集合。 本文的主要贡献如下： 1.  对 Android 应用中的特殊启动方式进行了深入研究，形式化表示了以不同启动方式启动 activity带来的返回栈状态变化。 2.  提出 activity 启动图，以及启动方式敏感的activity 跳转静态分析方法用于自动构建 ALG。 3.  提 出 并 实 现 了 ALC 静 态 分 析 框 架ALCAnalyzer，该框架能自动完成 ALG 构建、ALC定位、返回栈变化模拟、ALC 分类； 4．对开源应用市场 F-Droid 中的 1179 个 Android应用进行了自动分析。人工检查结果表明了分析方法的有效性和分析工具的实用性。对 Google  Play中 20 个 Android 应用进行分析，结果证明了ALCAnalyzer 能够准确模拟返回栈状态变化，防止非法路径产生，并为开发人员管理返回栈提供有效信息。 计算机学报 计  算  机  学  报  2019 年 launchModeintentFilter其他反编译 ALG生成器 ALC生成器返回栈模拟器无效配置 A1A3 A2standardsingleTopstandard-clearTop有效启动方式A1 A2singleTopstandard-clearTop返回栈状态变迁图生成器ALC分类器分析结果预处理 图 1   ALCAnalyzer 框架图 2  研究动机 本节通过一款 SSH 客户端应用 ConnectBot 的例子来说明现有启动方式不敏感的 activity 跳转分析方法的局限性。 2.1   一个ALC实例   (a)  三个 activity 类的代码片段和 AndroidManifest.xml 配置文件  (b)  三个 activity 类间的启动关系  图 2   ConnectBot 代码片段及部分启动关系 图 2 (a)展示了 ConnectBot 中三个 activity 类以及配置文件 AndroidManifest.xml 的代码片段。代码片 段 30-33 行 决 定 了 该 应 用 main  activity 是HostListActivity。当应用被启动时，系统会首先创建一个 HostListActivity 的实例并压入该应用的返回栈。图 2(b)展示了 ConnectBot 中三个 activity：A1，A2，A3 间的启动关系。当 A1 中的列表项“test”被点击时，如第 9 行所示的 ICC 函数 startActivity()被调用从而启动 A2。由于 ConsoleActivity 的“launchMode”设置为“singleTop”（35 行）,所以A1 以 singleTop 方式启动 A2。第 13 行通过 API setIntent()设置目录项的响应。当 A1 中右侧“设置”目录项被点击时，A3 以 standard 方式被启动。当 A2左 上 角 “ ” 被 点 击 时 ， A2 通 过 ICC 函 数startActivity()来启动 A1（24 行）。由于 intent 对象的标志设置为“FLAG_ACTIVITY_CLEAR_TOP”（23 行）且 HostListActivity 没有设置“launchMode”的值，所以 A2 以 standard-clearTop 方式启动 A1。系统如何通过 intent 对象决定目标 activity及如何根据返回栈相关配置判断启动方式将在 4.3 节详述。 从图 2(b)可已看出，ConnectBot 中存在 activity启动环 ALC2 。该环中的两个启动关系均配置为特殊的启动方式。 2.2   现有分析方法局限性 当前对启动方式不敏感的 activity 跳转静态分析方法[1-5]无法提取 activity 启动方式，且在模拟返回栈状态变化时假设所有 activity 均以 standard 方式被启动。所以现有分析方法只能模拟两种返回栈变化：以默认启动方式启动 activity 带来的实例入栈和返回动作带来的 activity 实例出栈。图 3(a)展示了现有分析方法针对 ALC2 所模拟的部分返回栈状态变迁，e1、e2 表示启动 activity 带来的返回栈变化，e3、e4 表示返回动作带来的返回栈变化，s1、s2、s3 表示三个返回栈的状态。图 3(a)模拟了如下场景：计算机学报——— 本课题得到国家自然科学基金项目(No.61402264)、天津市自然科学基金重点项目(No.17JCZDJC30700)、天津市科技支撑项目(No.17YFZCGX00610)资助.  刘奥，男，1994年生，博士研究生，主要研究领域为软件分析技术、软件测试、信息安全技术. E-mail: 18271390154@163.com.  过辰楷（通信作者），男，1988年生，博士，讲师，主要研究领域为软件分析技术、信息安全技术、模型检测. E-mail: chenkai.guo@163.com.  王伟静，女，1992年生，硕士研究生，主要研究领域为软件分析技术、软件测试、信息安全技术. E-mail: 2120170469@mail.nankai.edu.cn.  候晓磊，男，1995年生，硕士研究生，主要研究领域为软件分析技术、软件测试、信息安全技术. E-mail: 953421587@qq.com.  朱静雯，女，1992年生，硕士，助理实验师，主要研究领域为软件分析技术、软件测试.E-mail: zhujingwennk@163.com.  张森，男，1989年生，硕士研究生，主要研究领域为软件分析技术、软件测试、信息安全技术. E-mail: balamuxuan@163.com.  许静，女，1967年生，博士，教授，中国计算机学会(CCF)高级会员(E200009005S)，主要研究领域为软件分析技术、软件工程、软件测试、信息安全技术.E-mail: xujing@nankai.edu.cn. Android 应用 Activity 启动环研究  刘奥1)   过辰楷1)   王伟静1)   候晓磊1)   朱静雯2)   张  森1)   许静3)  1)(  南开大学计算机学院，天津  300350) 2)(南开大学软件学院，天津  300350) 3)(南开大学人工智能学院，天津  300350)  摘  要  Activity 的循环启动构成了 activity 启动环（ALC），它是一种 Android 应用开发工程师为了完成特定功能而广泛使用的结构。由于缺乏对 ALC 特性的系统研究，致使当前 activity 跳转分析方法对启动方式不敏感，使其无法正确模拟使用特殊启动方式的 Android 应用的返回栈状态变化，从而产生非法路径。本文形式化表示了以 7 种不同方式启动 activity 带来的返回栈状态变化，并提出表示 activity 间启动关系的 activity 启动图（ALG），以及启动方式敏感的 activity 跳转静态分析方法用于自动构建 ALG。该方法首先为 Android 应用构造辅助主函数：为每个 activity 类构造一个对象的堆内存分配点，对于每个 activity 对象，依据控制流组织被重写的回调函数调用顺序。然后通过面向对象的字段敏感指向分析提取 activity 启动关系中的目标 activity 类和启动方式相关配置，从而构建 activity 对象的启动图。另外，本文设计并实现了 ALC 静态分析框架ALCAnalyzer，该框架能为 Android 应用自动生成 ALG，基于 ALG 生成 ALC 集合，并能准确模拟重复执行 ALC 时的返回栈状态变化，预测应用在运行过程中是否会产生同类型 activity 实例。对 1179 个 Android 开源应用进行自动分析及人工验证的实验结果证明了启动方式敏感的 activity 跳转分析的准确性和分析工具的实用性，同时展现了 ALC 分布的广泛性和特殊启动方式被使用的广泛性。对 Google  Play 的 20 个应用进行实验，结果证明相比于启动方式不敏感的 activity 跳转分析，ALCAnalyzer 能够更准确模拟返回栈状态变化，从而防止非法路径产生，并能够为返回栈管理提供有效信息。 关键词  安卓应用；activity 启动图；启动方式；返回栈；activity 启动环 中图法分类号  TP311 Research on Activity-Launch Cycles in Android Applications LIU Ao1)  GUO Chen-Kai1)  WANG Wei-Jing1)  HOU Xiao-Lei1)  ZHU Jing-Wen2)  ZHANG Sen1)  XU Jing3) 1) (College of Computer Science, Nankai University, Tianjin 300350, China) 2) (College of Software, Nankai University, Tianjin 300350, China) 3) (College of Artificial Intelligence, Nankai University, Tianjin 300350, China)  Abstract Activity  launching  cycle  (ALC)  allows  an  activity  class  to  be  launched  repeatedly,  which  is  widely used in Android applications (apps) to support specific functions. Special launch types can be used in ALC to prevent multiple instances of each activity class in the back stack. However, existing activity transition analyses 计算机学报刘奥等：Android 应用 Activity 启动环研究  5 初始时返回栈中只有一个 A1 的实例（s1），用户点击 A1 中的列表项“test”后，一个 A2 的新实例被创建并压入返回栈中（e1）；用户继续点击 A2 中的“ ”，启动方式不敏感的分析方法模拟 standard 启动方式向返回栈压入 A1 的新实例（e2），此时返回栈状态为 s3；若继续遍历 ALC2，那么将会持续向返回栈压入 A2 和 A1 的新实例；若在状态 s3 时，用户执行了返回动作，则栈顶实例被销毁（e4）。  (a)  启动方式不敏感                 (b)  启动方式敏感  图 3   针对 ALC2 的返回栈变化模拟示意图 真实的返回栈变化如图 3(b)所示，其模拟的场景如下：singleTop 要求当源 activity 的类型和目标activity 的类型相同时，系统重用栈顶实例，否则创建一个目标 activity 的新实例并压入栈中。由于 A1和 A2 类型不同，所以点击“test”后引起的返回栈状态变化如 e6。standard-clearTop 要求若栈中已经存在目标 activity 的实例，则销毁该实例及以上全部实例，并创建一个目标 activity 的新实例。所以点击“ ”引起的返回栈状态变化如 e5。 可以看出，图 3(a)中 s3 是不可能出现的错误状态，e3，e4 为错误的状态变迁。在基于 activity 跳转路径的研究与应用中，包含错误返回栈状态变迁的非法路径会带来意料之外的错误。比如：在 GUI测试和缺陷检测[2,3,5-7,9,12-15]中，需要以动作序列作为测试输入。启动方式不敏感的分析方法允许生成非 法 路 径 “ e1,  e2,  e4,  e3 ” 对 应 的 动 作 序 列es 。显 然 该 测 试 用 例 执 行 完 动 作 序 列< >后，ConnectBot应用已经退出，根本无法继续执行后续动作从而导致测试失败。对于 ConnectBot 来说，启动方式不敏感的分析方法允许产生 920 条长度为 4 的路径（只考虑返回动作和 activity 启动），其中 483 条为非法路径。 显然，当 ALC 中使用了特殊启动方式，当前分析方法无法正确模拟其引起的返回栈的状态变化，也无法正确模拟返回动作所触发的 activity 跳转，从而产生非法路径；更无法对 ALC 正确分类。本文提出的 ALCAnalyzer 则能够自动构建 ALG，准确模拟返回栈状态变化，并对 ALC 准确分类。 3  Activity 启动关系和启动环 本节对返回栈和 activity 的启动方式做了简述；形式化表示了以不同启动方式启动 activity 引起的返回栈状态变化；定义了表示 activity 间启动关系的 activity 启动图及 activity 启动环；并阐述了 ALC分类及各类 ALC 特性。 3.1   相关Android特征 (1)  返回栈（task） 软件运行过程中产生的 activity 实例以栈的形式组织在返回栈中，以便用户正确返回上层界面。（本文“界面”指一个 activity 实例向用户提供的可视化组件的全集。本研究关注于 activity 间启动关系的建模及返回栈状态的模拟。Activity 内部组件内容变更引起的界面变化，如 webview 组件内容的变更，不在本文研究范围。）栈顶实例为当前activity，用户按回退按钮时，当前  activity 会从栈顶部弹出并销毁。返回栈可形式化为 BS  =  <ac1, ac2, …, acn>,其中 aci表示 activity 类 ci的一个实例，ac1为栈底实例，acn为栈顶实例。可通过为 activity设定启动方式来帮助管理返回栈。若两个返回栈中activity 实例个数相同且对应位置的两个 activity 实例类型相同，本文称这两个返回栈状态相同。Android 平台为每个应用维护一个返回栈，其名称与应用包名相同。 (2) Activity 的启动方式 源 activity cn以启动方式 lt 启动目标 activity cx记为 cn  cx  。Android 应用中，为 intent 对象设定的标志、finish()的调用、AndroidManifest.xml 文件中为 activity 设定的 launchMode 属性及 taskAffinity属性共同决定了 activity 的启动方式。本文称这四个属性为 activity 启动方式相关属性。表 1 归纳了 7种影响单个返回栈状态的 activity 启动方式并形式化的说明每种启动方式对返回栈的影响。各种启动方式的详细配置在第 4.3.3 节详述。 表 1 以不同启动方式启动 activity 带来的返回栈变化。设启计算机学报 计  算  机  学  报  2019 年 动关系为 cn  cx，当前返回栈状态为<ac1, ac2, …,   acx-1,  acx,  acx+1, …, acn>，其中 ac1为栈底实例，acn为栈顶实例，a’cx是区别于 acx的 cx的新实例 启动方式（lt）  启动目标 activity 后的返回栈 standard  <ac1, ac2, …, acx-1, acx, acx+1, …, acn, a’cx> singleTop  :   else :   standard-clearTop  <ac1, ac2, …, acx-1, a’cx> singleTop-clearTop  <ac1, ac2, …, acx-1, acx> reorderToFront  <ac1, ac2, …, acx-1, acx+1, …, acn, acx> singleTask  <ac1, ac2, …, acx-1, acx > standard|finish  <ac1, ac2, …, acx-1, acx+1, …, acn-1, acx> ·  standard。无论当前返回栈中是否已经包含目标activity 的实例，一个目标 activity 的新实例均会被创建并压入当前返回栈中。 ·  singleTop。若栈顶实例类型与目标 activity 类型相同，则不会在栈顶创建新实例。 ·  standard-clearTop。若栈中已经存在目标 activity的实例 acx，那么该实例及之上的实例都会被销毁，系统重新创建一个目标 activity 的新实例a’cx并压入栈中。 ·  singleTop-clearTop。若栈中已经存在目标 activity的实例 acx，那么该实例之上的实例都会被销毁，acx成为栈顶实例。 ·  singleTask。效果与 singleTop-clearTop 相同，只是配置不同。 ·  reorderToFront。若栈中已经存在目标 activity 的实例 acx，则将该实例置于栈顶，其余元素位置不变。 ·  伴随 finish()的启动（standard|finish）。目标 activity的新实例被创建的同时伴随着当前 activity 实例由于 finish()的调用而销毁。该种启动方式并不一定要在 activity 启动环中才能发挥作用。 3.2   Activity启动图和启动环 定义 1. activity 启动图（ALG)是一个三元组：表示 activity 类型集合。   是有向边集合： ，其中 ns表示边的始点，ne表示边的终点，lt 是启动方式集合 LT 中的元素，表示 ns以 lt 的方式启动 ne。的起始节点为 st，为 Android 应用的 main activity。 定义 2. activity 启动环（activity launching cycle，简称 ALC)是 ALG 中的一个初级回路。若两个 ALC有向边集合相同，则称他们具有相同的结构。起始节点不同的两个 ALC 可能具有相同的结构。 3.3   ALC分类 若一个 Android 应用的 ALG 中没有 ALC，那么activity 不可能被循环启动，返回栈中肯定不会产生同类型 activity 实例。Android 应用存在 ALC 是其产生同类型 activity 实例的必要条件。根据重复执行 ALC 时，返回栈中产生同类型 activity 实例的情况将 ALC 分为 3 类。针对这 3 类情况各展示了一个样例，如图 4 所示，其中 ALC 用深色虚线标记。表 2 展示了这三类 ALC 被连续执行 2 次过程中返回栈的变化过程，表中用小写字母“a”表示activity 实例，下标指示类型，上标指示其为该类型的第几个实例。每启动一个 activity，返回栈状态就更新一次，同类型 activity 实例用黑框标出，类型相同则线型相同。 图 4  三类 ALC 的样例：(a)第一类，(b)第二类，(c)第三类 表 2 重复执行两次 ALC 过程中返回栈状态变化情况 A1: ChooseFileActivityA2: OpenFileActivityA3: Options A4: AboutPDFViewActivitystandard standardstandard standardstandard standard A1 A2A3A4standardstandard| finish()singleTop-clearTopreorderToFront A1: HostListActivityA2: ConsoleActivity A3: SettingActivitysingleTopstandard-clearTopstandard (a) APV 中的 ALC3  (b) Test Example 中的 ALC4  (c) ConnectBot 中的 ALC2 计算机学报刘奥等：Android 应用 Activity 启动环研究  7 ALC 名称   ALC3 (TYPE1)   ALC4 (TYPE2)   ALC2 (TYPE3) 重复次数   init   1   2   init   1   2   init   1   2 返回栈状 态变化   1   2  3   4  5   1   2  3  4  5   6  7  8  9   1   2  3   4  5 a11  a21 a11 a12 a21 a11 a22 a12 a21 a11 a13 a22 a12 a21 a11 a11  a21 a11 a31 a11 a41 a31 a11 a11 a41 a31 a22 a11 a41 a31 a32 a11 a41 a31 a41 a31 a12 a41 a31 a11  a21 a11 a12  a22 a12 a13                                     第一类 ALC．其特征在于：1、ALC 中至少存在一个 activity 类 c，重复执行 ALC t 次后，返回栈中 c 的实例个数 n 满足：  且返回栈中总 activity 实例数量不会超 tl ，其中l 表示 ALC 长度。当 t 足够大时，应用程序会因为过多的同类型 activity 实例严重占用系统而强制退出。2、由于持续重复执行ALC 会产生无限个activity实例，所以也会有无限个返回栈状态，并且每次执行结束后的返回栈状态均不相同。图 4(a) APV 中的ALC3 即为第一类，从表 2 可以看出两次执行 ALC3的过程中返回栈状态完全不同。重复执行 ALC3  t次后，ChooseFileActivity 的实例个数为 ，OpenFileActivity 的实例个数为 。用户想返回栈底界面则需要 2t 次的回退操作。 第二类 ALC．其特征在于：1、重复执行 ALC过程中，至少存在一个能够产生两个实例的 activity类 c，并且返回栈中每种类型 activity 最多出现两个实例，即返回栈中的实例总数最多为 ，其中 l 表示 ALC 长度。2、重复执行 t 次后，之后每次执行结束后的返回栈状态均与第 t 次执行结束后返回栈状态相同且第 次执行过程中的返回栈状态将会重复出现，所以返回栈状态数有限。为详细说明该类 ALC 的特征，本文结合多种 activity 启动方式构造了 ALC4，如图 4(b)所示。从表 2 可知，返回栈只有在状态 7 时才会出现两个 A3 类型的实例。第二次执行完 ALC4 的返回栈状态 9 和第一次执行ALC4 的状态 5 相同，继续执行下去与 6、7、8、9相同的返回栈状态会重复出现。   第三类 ALC．其特征在于：1、在持续重复执行ALC 过程中每个类型 activity 最多产生一个实例。2、执 行 过 程 中 出 现 的 返 回 栈 状 态 是 有 限 的 。ConnectBot 中的 ALC2 就属于第三类。从表 2 可以看出，返回栈的 1、3、5 状态相同，2、4 状态相同，每个状态都没有同类型 activity 实例。继续执行ALC2，有限的返回栈状态依旧会循环出现。 ALC 的分类本质上取决于 ALC 中各类 activity间启动方式的组合。 4  启动方式敏感的 activity 跳转分析 面向对象的字段敏感指向分析能够帮助构建Android 应用的 activity 启动图。本节首先介绍了Android 平台启动 activity 的组件间通信机制；然后阐 述 了 构 建 ALG 前 的 预 处 理 ， 包 括AndroidManifest.xml 文件的解析和基于 Android 控制流的辅助主函数构造；最后详述了利用面向对象的字段敏感指向分析构造 ALG 的规则。 4.1  Activity间通信 Android 平台通过调用 ICC 相关 APIs 来启动activity ， 这 些 APIs 包 括 startActivity() 、startActivityForResult()、startActivityIfNeeded()，被记为 startActivity(intent)。为了全面提取启动关系，在指向分析中考虑了以上三个 APIs。 对象 intent 决定了目标 activity。Intent 可以分为两种类型，显式和隐式。显式 intent 记录了明确的目标 activity 类型（如图 2(a)的 13-14 行和 22 行）。隐式 intent 记录了目标 activity 需要执行的动作（如图 2(a)第 8 行），只有具备执行该动作能力的activities 才可能被启动。Activity 能够执行的动作被注册在 AndroidMainfest.xml 的 intent 过滤器中（如图 2(a)第 36-38 行）。Android 平台提供了 APIs 来帮助 intent 对象记录目标 activity 相关信息，比如setComponent()，setAction()。对于显式 intent，目标 activity 类 型 被 存 储 在 字 段Intent.mCompont.mClass 中。对于隐式 intent，目标计算机学报 计  算  机  学  报  2019 年 activity 需 要 执 行 的 动 作 被 存 储 在 字 段Intent.mAction 中。 为 intent 设置标志字段能够在启动 activity达到特 殊 的 效 果 ， 比 如“FLAG_ACTIVITY_CLEAR_TOP”标志要求系统首先查找返回栈中与目标 activity 同类型的实例，若存在，则将返回栈中该实例以上的实例全部销毁。Android 平台提供了 setFlags()和 addFlags()来设置和添加标志。标志被存储在字段 Intent.mFlags 中。 4.2  预处理 预 处 理 包 括 两 个 部 分 ， 第 一 部 分 是 解 析AndroidManifest.xml 文件，第二部分是为指向分析构建辅助 main()。从 AndroidMainfest.xml 中提取的重点信息包括：1)Android 应用包名；2)注册的activity 类名集合 ACT；3)各 activity 类的 intent 过滤器；4)部分返回栈相关配置信息，包括各 activity类的 taskAffinity 和 launchMode。  图 5  辅助主函数结构 与传统的 Java 程序只有一个程序入口（main函数）不同，Android 应用程序为事件驱动，由大量回调函数构成。这些回调函数包括生命周期回调和非生命周期回调。非生命周期回调又包括系统回调和 GUI 回调。为了进行指向分析，需要构建一个辅助主函数将这些回调函数依照控制流组织起来。构建辅助 main()时，由于指向分析前 activity 间的启动关系并不可知，因此构建辅助 main()时只需考虑单个 activity 类内部的回调函数调用顺序。图 5 展示了辅助 main()的结构。对于 activity 生命周期回调函数：onCreate()和 onDestroy()分别指示 activity 生命周期的开始和结束；onStart()和 onStop()分别在activity 可视与不可视时自动调用；onResume()和onPause()则指示了可操作周期，用户可在这段周期内操作 activity，比如点击按钮。系统自行触发的系统回调（比如 onLocationChanged()）和用户行为触发的 GUI 回调（比如 onClick()）均在可交互周期内被调用。为 Android 应用构建辅助主函数时，只需要考虑被重写的回调函数。 4.3  面向对象的字段敏感指向分析 4.3.1  符号定义 程序相关符号 类：  c    C, act    ACT, ACT    C 方法：  m    M 变量：  x, y, z, num, cpt, action    R 字段：  f    F 语句：  s, si    S  s  = s1; s2 | x  = new c() | x  = y | x  = y.f | x.f  = y | x  = y.m(z)  对象实例化 赋值语句 字段读 字段写 方法调用语句 对象：  oi, oj, ok, ol,    O 指向分析相关方法 Pt：  R    O FPt：  R    O 启动方式相关符号 launchMode：  lm    LM = {Std, Top, Task, Inst} taskAffinity：  taf   TAF intent 标志：  flag   FLAG = VFLAG ⋃ IVFLAG ⋃ OFLAG 有效标志：  VFTAG =  {f_singleTop, f_clearTop, f_reorderToFront} finish()调用：  fin   FIN = {true, false} 启动方式：  lt   LT    {standard,  singleTop,  standard-clearTop, singleTop-clearTop,  reorderToFront,  singleTask, standard|finish} ALG 相关符号 ALG：   节点：  oi    N    O 边：  oi  oj    E    N    N    LT 图 6  符号定义 图 6 列出了 ALG 构建方法使用的符号。第一部分是 Java 程序的抽象。C 表示类和接口的集合，ACT 表示所有 activity 类的集合。每一个方法体都可表示成语句 s。方法体可由对象实例化、赋值、字段读、字段写、方法调用五种原子语句组成。对象实例化意味着堆内存的分配。第二部分定义了指向分析过程中用到的相关方法。Pt(r)表示指针 r 所指向的对象集合。FPt(r, f)给出指针 r 的字段 f 所指向的对象集合。第三部分给出确定启动方式所用到的符号。被启动 activity 的 launchMode，taskAffinity，启动时 ICC 方法传递的 intent 对象的标志和 finish()方法的调用共同影响着返回栈状态，决定了启动方式。根据 Intent 标志对返回栈的影响将其分为无效标志（IVFLAG），有效标志（VFLAG）和其他（OFLAG）。由于现阶段本文提出的返回栈建模方法无法模拟多个返回栈的交互，因此本文把引起多计算机学报10  计  算  机  学  报  2019 年 (oi, flags, lm, taf, fin)    ol  (ConfigVali(flags, lm, taf))   (   flag    flags: flag is f_reorderToFront) oi    ol    E  [RULE-15] (oi, flags, lm, taf, fin)    ol  (ConfigVali(flags, lm, taf))   (   flag    flags: flag is f_clearTop)   ((   flag    flags: flag is f_singleTop)   (lm is Top)) oi    ol    E  [RULE-16] (oi, flags, lm, taf, fin)    ol  (ConfigVali(flags, lm, taf))   (   flag    flags: flag    VFTAG)    fin   (lm is Std)) oi    ol    E  [RULE-17] (oi, flags, lm, taf, fin)    ol  (ConfigVali(flags, lm, taf))   (   flag    flags: flag    VFTAG)    fin   (lm is Std)) oi    ol    E  [RULE-18] 5  ALC 静态分析框架 本文提出并实现了 ALC 自动静态分析框架ALCAnalyzer，如图 1 所示。该框架以 Android package（简称 apk）作为输入，包括三个核心组件：ALG 生成器、ALC 生成器和返回栈模拟器，返回栈模拟器中集成了 ALC 分类器。ALG 生成器实现了第 4 节基于面向对象字段敏感指向分析的 ALG构建方法，有效启动方式可随着对无效配置的深入研究和对多个返回栈变迁建模而得到扩展。ALC 生成器以 ALG 作为输入，输出 Android 应用程序中的ALC 集合。返回栈模拟器依据表 1 对 7 种不同有效方式启动 activity 带来的返回栈变化进行模拟。ALC分类器以 ALC 集合作为输入，输出每个 ALC 的分类结果并预测 Android 应用程序在运行过程中能够产生同类型实例的 activity 类的集合。本节对 ALC生成器和 ALC 分类器进行详述。 5.1   ALC生成器 ALC 生成器实现了如算法 1 所示的基于 ALG的 ALC 生成算法。算法 1 以 ALG 的 main  activity节点为起点对 ALG 进行递归深度优先遍历来探测ALC。trace 记录了访问过的节点，当 trace 中已经存在即将要访问的当前节点 currentNode 时，表明存在一个 ALC（第 4-8 行）。第 5 行 ALC 不仅记录了 一 个 初 级 回 路 cycle 和 cycle 的 起 始 节 点startNode，还记录了从 ALG 起始节点到 startNode的路径。cycle 即为 trace 中 currentNode 之后的节点序列，而 preCycle 为 currentNode 之前的节点序列。使用第 6 行的 AddALC()向 ALCs 添加新的 ALC 时，若 ALCs 中已经存在与 ALC 结构相同的元素，则保留具有较短 pre Cycle 的 ALC。若没有发现 ALC，那么继续访问当前节点的后继节点（第 10-13 行）。第10行通过GetSuccessors()获取当前节点的后继节点集合，第 11-13 行处理各后继节点。 如果最终的有效 ALC 集合为空，说明该应用在使用过程中不可能出现同类型 activity 实例。 算法 1.   ALC 集合生成算法. 输入：ALG； 输出：Android 应用的有效 ALC 集合 ALCs． 1.   ALCs ，initialize trace with an empty list； 2.   Traverse(entryNode(ALG))； 3.   PROCEDURE Traverse(currentNode) 4.     IF currentNode in trace THEN 5.       ALC GetALC(currentNode, trace)； 6.       AddALC(ALCs, ALC)； 7.       RETURN； 8.     END IF 9.     add currentNode to trace； 10.    successors GetSuccessors(currentNode) 11.    FOREACH nextNode    successors DO 12.      Traverse(nextNode)； 13.    END FOR 14.    remove the last node from trace； 15. END PROCEDURE 5.2   ALC分类器 依据 3.3 节阐述的各类 ALC 特征，可以对 ALC类别进行判定，方法为：1、若重复执行 ALC 过程中发现某次执行结束后的返回栈状态与前一次结束后相同，则肯定是第二类或第三类；2、根据执行过程中是否产生同类型 activity 实例来区分第二类和第三类 ALC；3、重复执行第二类 ALC，返回栈中最多有 2*Length(ALC)个实例，重复执行第三类 ALC，返回栈中最多有 Length(ALC)个实例，因此当返回栈中实例个数大于 2*Length(ALC)时，即可判定其为第一类。 具体判别过程如算法 2 所示。4-8 行模拟了一次 ALC 的执行过程，t Stack 和 oldStack 分别记录当前返回栈状态及上次执行结束后返回栈状态。9-17行根据返回栈状态判别 ALC 类型，第 9 行中SameStates 用来判定两个返回栈状态是否相同。 计算机学报刘奥等：Android 应用 Activity 启动环研究  9 个返回栈的交互的 intent 标志称为无效标志。这些标志会在未来工作中考虑。第四部分给出了 ALG相关符号。通过指向分析所构造的 activity 启动图中每个节点都为一个 activity 类的对象。 4.3.2  面向对象的字段敏感指向分析规则 对 辅 主 函 数 进 行 指 向 分 析 ，[RULE-1]-[RULE-6]给出了五条原子语句所对应的指向规则。初始时 ALG 的节点集合 N 和边的集合 E都为空。[RULE-1]对应于类实例化语句。[RULE-2]专门针对于 activity 类的实例化。每个 activity 对象的 创 建 都 为 ALG 新 增 一 个 节 点 。[RULE-3]-[RULE-5]分别对应赋值、字段读、字段写语句。[RULE-6]对应了方法的调用语句。每个方法 m 包含其方法名，形参 thism和 pm，返回值 rm。对方法 m 进行指向分析可拆解为对方法体 sm及辅助语句 x = rm的分析。    si:   x = new c()    c ACT oiPt(x)  [RULE-1] si:   x = new act()    act ACT oiPt(x)   oi    N  [RULE-2] x = y    oi    Pt(y) Pt(y)    Pt(x)  [RULE-3] x = y.f    oi    Pt(y) FPt(oi, f)    Pt(x)  [RULE-4] x.f = y    oi    Pt(x) Pt(y)    FPt(oi, f)  [RULE-5] x  = y.m(z)    oi    Pt(y)    oj    Pt(z) sm; x = rm    oi    Pt(thism)    oj    Pt(pm)  [RULE-6]    [RULE-7]-[RULE-10]是组件间通信相关语句指向规则。[RULE-7]对 intent 标志进行分析。Intent标志为整数类型。Intent 对象 oi通过调用方法addFlags()将标志值存储在 mFlags 字段；也可以通过调用方法 setFlags()，将添加的新标志与已有标志进行按位或运算并存储在 mFlags 字段。[RULE-8]和[RULE-9]分别对显式和隐式 intent 进行分析。为intent 对 象 oi构 造 了 字符 串 类 型 的 辅 助 字 段targetClassName 来存储目标 activity 类名。[RULE-9]中的 FindTarget()方法返回能够执行 oj动作的目标activity 集合。[RULE-10]分析了所有 activity 启动相关 APIs。在该项规则中，this 表示一个 activity 实例；启动 activity 所传递的 intent 对象 oj的字段targetClasssName 记录了目标 activity 类名 ok；GetActObj()根据类名获取其在堆内存中的唯一实例 ol；GetFlags()将 intent 对象 oj的字段 m Flags 所存储的整数转化为标志集合并返回；GetLM()和GetTA()分别获取目标 activity 对象的 launchMode 和taskAffinity；GetFIN()获取正被分析的方法 m 的方法体有没有调用 finish()；(oi,  config)    ol表示 oi以启动方式相关配置 config 下启动 ol。 intent.mFlags  = num oi    Pt(intent)    oj    Pt(num) <oi, mFlags> = oj  [RULE-7] intent.mComponent  = cpt oi    Pt(intent)    oj    Pt(cpt) FPt(oj, m Class)   FPt(oi, targetClassName)  [RULE-8] intent.mAction  = action oi    Pt(intent)    oj    Pt(action) FindTarget(oj)    FPt(oi, targetClassName)  [RULE-9] this.startActivity(intent) oi    Pt(this)    oj    Pt(intent)   ok    FPt(intent, targetClasssName) ol = GetActObj(ok)   flags = GetFlags(<oj, m Flags>) lm = GetLM(ol)   taf = GetTA(ol)   fin = GetFIN(m) (oi, flags, lm, taf, fin)    ol  [RULE-10]    4.3.3 Activity 启动边构建规则 [RULE-11]-[RULE-18]给出了根据 activity 间启动关系和配置信息生成 ALG 启动边的规则。[RULE-11]对应于无效配置的判定，其中 pk Name是当前 Android 应用的包名。当 taf 与当前包名不相同时，若系统安装了与 taf 相同的应用，则会在该应用的返回栈中启动目标 activity。无效配置会引起多个返回栈的交互，没有为无效配置的 activity 启动生成启动边。  [RULE-12]-[RULE-18]对应有效边的生成，其中方法 ConfigVali()根据规则 11 来判定配置信息是否有效，若有效，则返回 true。    (oi, flags, lm, taf, fin)    ol  (lm is Inst)    (taf is pkName)   (  flag    flags: flag    IVFLAG) oi    ol  [RULE-11] (oi, flags, lm, taf, fin)    ol  (ConfigVali(flags, lm, taf))    (lm is Task) oi    ol    E  [RULE-12] (oi, flags, lm, taf, fin)    ol  (ConfigVali(flags, lm, taf))   (   flag    flags: flag is f_clearTop)   ((   flag    flags: flag is f_singleTop)   (lm is Top)) oi    ol    E  [RULE-13] (oi, flags, lm, taf, fin)    ol  (ConfigVali(flags, lm, taf))   (   flag    flags: flag is f_clearTop)   ((   flag    flags: flag is f_singleTop)   (lm is Top)) oi    ol    E  [RULE-14] 计算机学报