基于对AndroidAPK程序的研究，移动程序效果最优化，到ILP的缩减

　　基于对AndroidAPK程序的研究，移动程序效果最优化，到ILP的缩减

　　作者:五年宝

　　

　　文丨五年宝

　　

　　编辑丨五年宝

　　前言

　　随着移动应用程序的规模迅速增长，自2012年以来，

　　AndroidAPK的平均大小增长了五倍多

，直到2021年美国下载量排名前10位的iPhone应用总共需要2.2GB的存储空间。

　　这种增长的主要部分来自于新功能的不断添加，举一个代表性的例子，由于Gmail不断扩展的功能集，其移动应用程序比五年前大了18倍。

　　截至2021年从

　　19MB

增长到

　　355MB

，规模和复杂性的急剧增加使得更广泛的用户更难访问移动应用程序。

　　可较大的应用程序大小会降低用户安装应用程序的积极性，所以

　　移动数据

和

　　设备存储

都非常宝贵。

　　计算资源有限的低端设备尤其无法访问如此大型的应用程序，应用程序安装率通常与应用程序大小

　　成反比

。

　　移动应用程序

　　为了更好地访问移动应用程序，流行的方法是使用

　　常规原始应用程序

的一小部分但具有代表性的部分来重新实现精简版本，并遵守简化版本大小的限制。

　　代表性的例子有Android即时应用程序和iOSAppClip，Android即时应用程序是一种小型应用程序，使最终用户

　　无需安装即可测试

本机Android应用程序的一部分。

　　开发人员可以选择从头开始创建即时应用程序，也可以将成熟的应用程序转变为即时应用程序。

　　将传统的本机应用程序转变为即时应用程序，需要开发人员

　　将应用程序模块化为单独的代码组件

，而且应用程序应小于15MB，以便快速启动。

　　iOSAppClip是原始应用程序的快速且轻量级的小部分，其目标类似于Android即时应用程序，而且AppleAppClip还要求开发人员重构应用程序的代码，使其模块化且可重用。

　　未压缩的AppClip应小于10MB才能立即启动，可重构原始应用程序同时遵守大小限制是相当重要的，这就是为什么很少使用这些功能的原因。

　　除游戏外，所有Android应用程序中只有不到

　　0.1%

提供即时应用程序，在

　　Google

展示的38个Android即时应用的著名案例中，迄今为止仅剩19个即时应用可用。

　　迄今为止，只有少数iOS应用程序提供

　　AppClip的轻量级版本

，为此提供了一个有用的系统，使用户能够自定义和减少Android应用程序。

　　系统将要简化的应用程序、简化版本的大小上限以及执行其所需核心功能的使用场景作为输入。

　　系统会生成应用程序的简化版本，该版本小于大小限制，但仍然能够执行给定的使用场景。

　　在研究中，

　　MADUSA

的高级架构作为输入，所以

　　MADUSA

采用原始应用程序、精简版本大小的上限n以及展示所需功能的使用场景。

　　研究人员需要考虑的是将应用程序作为

　　APK文件

提供的设置，以便即使整个源代码由于各种原因不可用，MADUSA也可以普遍适用。

　　在此设置中的练习使用场景，MADUSA首先通过在其

　　smali中检测Dalvik

字节码来测量代码覆盖率为代表。

　　当有了覆盖范围信息时，生成所需轻量级版本的直接方法是使用使用场景中涵盖的说明打包应用程序。

　　除了代码之外，代码使用的其他资源文件也必须包含在生成的应用程序中，可这种简单的方法可能会

　　损害最终应用程序的稳健性

，所以使用场景可能不够详尽，无法展示所需的功能。

　　好比如生成的应用程序可能会因使用场景中从未见过的事件而崩溃，研究人员为了提高

　　鲁棒性

，只要不超过大小限制，就会在生成的应用程序中包含尽可能多的原始指令。

　　这是因为生成的应用程序中包含的指令越多，生成的应用程序与原始应用程序相比将表现出更相似的行为。

　　最后研究人员将此优化问题简化为整数线性规划实例：给定指令以及有关

　　代码覆盖率

和

　　代码使用的资源文件

的信息，可以导致应用程序小于大小限制的指令的最大子集是什么？

　　借助现成的ILP求解器找到的解决方案，MADUSA有效地生成了一个精简但强大的应用程序，该应用程序可以执行所需的功能，

　　同时遵守大小限制

。

　　没有现有的解决方案意味着尺寸限制太严格而

　　无法满足

，从而也导致MADUSA增加上限n并重复该过程。

　　研究人员在

　　GooglePlay商店

上提供的一套包含19个Android应用程序的平台上对MADUSA进行了评估。

　　最终MADUSA有效地融合到所需的简化应用程序，并且它可以平均减少应用程序大小40%，通过在应用程序上运行最先进的

　　模糊器Monkey

来验证简化应用程序的稳健性。

　　研究人员们提出了一种减小移动应用程序大小的通用方法，其目的是从原始移动应用程序中删除不需要的功能，以提高更广泛用户的可访问性。

　　首先使用一组真实的Android应用程序来评估MADUSA，最后的实验表明，

　　它有效地减小了应用程序的大小。

　　MADUSA的输入

　　在开始之前，MADUSA使用现成的代码覆盖率工具来检测原始APK文件，以便在应用程序执行期间测量应用程序的

　　代码覆盖率和资源使用情况

。

　　在检测后用户需要编写一个使用场景来练习

　　轻量级应用程序

的所需功能，而MADUSA的输入是一个包含入口点和事件序列的规范。

　　通过这样一个输入规范，可以生成NOS的简化版本，其功能与官方即时应用程序相同，提供查看一篇特定新闻文章的功能。

　　输入包括两部分：首先用户需要指定所需应用程序的入口点，其次当所需应用程序从

　　原始主Activity以外的Activity

启动时才需要此信息。

　　在此示例中研究人员指定了一个

　　特定的入口点

，因为他们希望用户从一开始就体验核心功能，而无需像原始版本一样经历任何准备步骤应用程序。

　　仅当需要其他数据来初始化启动活动时，才需要

　　“入口点数据”

，而通过研究人员的发现，上文提供了一个指向要向用户显示的文章的链接。

　　启动活动指令后，执行核心功能的事件序列包括触摸新闻视频的

　　缩略图

、

　　播放

和

　　停止视频

、

　　切换到全屏模式

、

　　滚动向下到文章底部

，最后单击另一篇相关文章的链接。

　　理想情况下，此类使用场景应广泛运用所需简化应用程序的全部功能，可结果并不总是能够设计出如此详尽的事件序列。

　　只能将展示基于

　　ILP的方法

如何在大小限制允许的范围内弥补这种不足。

　　基于ILP的缩减

　　MADUSA首先通过在原始应用程序上运行使用场景来测量代码覆盖率，通过MADUSA目前在方法级别测量覆盖率。

　　这可以表明使用现有的用于测量

　　Android应用程序代码

覆盖率的工具来完成，也可以使用任何代码覆盖率工具。

　　而MADUSA分析原始应用程序并获取资源使用信息，该信息涉及每个单独方法使用的资源，这些信息可以通过分析应用程序中的

　　代码

和

　　XML文件

来获取。

　　给定代码覆盖率和资源使用信息，MADUSA构建了一个有向图，研究人员称之为

　　应用程序依赖图

，在这项研究中每个节点代表应用程序中的一个方法或一个资源文件。

　　方法节点包含有关完全限定方法名称，以及运行场景时是否覆盖该方法的信息，而资源节点包含有关资源文件的类型和大小的信息。

　　在研究中

　　NOS的ADG的子部分

，每个方形节点代表一个方法节点，每个圆形节点对应一个资源节点。

　　虚线和实线分别表示资源使用和方法调用，绿色和红色节点在运行场景时分别被

　　覆盖和未覆盖方法。

　　有了这些信息，生成原始应用程序的修剪版本的直接方法，是

　　仅包含使用场景所涵盖的方法

，以及这些方法使用的资源。

　　在这种方法中，可以生成的应用程序将包括绿色的方法以及可从这些方法访问的资源，而这种仅基于代码覆盖率的方法可能会导致

　　应用程序脆弱

。

　　在特定使用场景中从未见过的事件上很容易崩溃，比如在

　　onRestart

和

　　mute

的方法不会包含在生成的应用程序中。

　　为了增强鲁棒性，研究人员的关键思想是包含尽可能多的方法、资源，同时通过整数线性规划遵守

　　15MB大小限制

。

　　对于给定的ADG，MADUSA通过求解ILP实例生成应用程序的

　　精简版本

，这也是研究人员的目标，最终找到ADG中满足以下约束的最大节点子集。

　　如果包含一个方法并且它使用资源，则必须包含所有使用的资源，如果包含一个方法并且它有调用者，则必须至少包含一个调用者方法。

　　ILP问题的解决方案代表简化应用程序中应存在的一组方法和资源，研究人员通过简单地排除ILP解决方案中不存在的方法和资源来生成应用程序的

　　轻量级版本。

　　上文中提到，解决方案中包含方法

　　onRestart

和

　　mute

，这是因为包含它们导致的大小增加并不显着，也证明了该应用程序比仅根据覆盖范围生成的应用程序更强大。

　　这样的方法自然会优先考虑与所涵盖的方法密切相关的方法和资源，好比如方法

　　moveBar

尚未包含在内，而且成本大于收益。

　　添加该方法需要添加它的所有传递被调用者以及占用1MB的使用资源，方法onRestart已被包含在内，所以它与另一个涵盖的方法

　　onCreate “共享”资源。

　　删除不包含的方法和资源后，可以获得一个

　　轻量级应用程序

，该应用程序提供所需的功能，同时不违反大小限制。

　　而MADUSA在2小时内从

　　22MB大小

的原始应用程序，成功生成了

　　10MB大小

轻量级应用程序，紧接着也可以确认MADUSA生成的版本，与NOS的官方即时应用程序完全相同。

　　方法

　　为了以方法和资源的粒度表示

　　移动应用程序

，研究人员将应用程序视为加权有向图，由一组具有实值权重的顶点和一组边组成。

　　比如说p到q的边表示为，如果存在从p到q的边，研究人员将会写为

　　p → qp→qp→*qp→∗q

。

　　当研究人员在识别原始应用程序的子部分时，可以将其视为诱导子图，比如给定V的子集，归纳图是一个顶点集且其边集包含E中具有以下特征的所有边的图，两个端点都在中。

　　就算找到最大诱导

　　ADG

，也不足以获得满足大小约束的所需简化应用程序，这是因为Android应用程序通常是

　　APK文件

格式的单个压缩容器文件。

　　这也就意味着所有代码、资源、证书和清单文件都打包到其中，由于大小限制是针对最终

　　APK文件的大小

，而不是其各个部分的大小总和。

　　这也说明白了如何确定大小限制以查找最大诱导ADG并不简单，研究人员们解决这个问题的关键思想是采用二分搜索来找到最大诱导ADG的适当大小上限。

　　实验的方法基于这样的假设：打包应用程序的压缩程序通常是单调的，压缩后保留两个未打包

　　应用程序

之间的大小顺序。

　　首先描述了他们的主要算法，这种算法采用原始

　　应用程序Apk

，一组使用场景S以及最终应用程序的大小上限n作为输入，目标是生成一个

　　简化的应用程序apk

，其大小不大于n。

　　结果apk被初始化为，这意味着失败，并且在找到所需应用程序时更新，变量

　　lb

和

　　ub

分别表示所需最大诱导ADG的的上限和下限。

　　变量lb和ub初始化为0以及应用程序所有部分的大小之和，可以通过解压APK文件获得，最初设置为n的

　　ADG≤n。

　　后来研究人员通过重播原始应用程序上的使用场景来测量代码覆盖率，根据代码覆盖率信息和原始应用程序，他们构建了一个ADG。

　　而在构建ADG时，研究人员静态分析应用程序的代码以识别不同方法和资源之间的关系，在配备ADG后，算法会重复主循环，直到时间预算到期或下限和上限相等。

　　主循环首先通过调用现成的ILP求解器来获取最大诱导ADG，如果大小限制过于严格，则无法找到

　　ILP实例

的解决方案。

　　这就回导致大小限制

　　θθ通过取区间lb

, ub上半部分的中点来增加，如果ILP实例的解决方案G存在，研究人员通过仅将解决方案中存在的方法和资源打包到APK文件中。

　　用这样的方式来构造应用程序的简化版本，下一步则是检查APK文件是否满足大小限制，如果满足，研究人员将应用程序记录为迄今为止获得的最佳结果。

　　这样就可以做到与第8行类似地增加，但更希望找到另一个包含更多方法或资源的新应用程序，同时仍然满足尺寸限制比较困难。

　　结论

　　之后研究人员为了识别资源和方法之间的依赖关系，将会进行简单的静态分析，首先就是要通过解析存储资源ID的

　　res、values、public.xml

来获取所有资源ID 。

　　并且解析资源xml文件，识别资源之间的引用关系，用这样的方法可以收集硬编码的资源ID以准确识别所使用的资源。

　　还会通过简单的程序内静态分析来跟踪每个程序变量的可能字符串值，识别

　　getIdentifier Android API

方法的可能字符串参数，这些参数用于构造完全量化的资源名称。

　　这里出现的一个复杂问题是，此类字符串参数可能会被混淆，这使得识别确切的资源变得困难，之后研究人员们将会继续往下进行研究，并决定出一个最佳方案。