REDDROID: Android Application Redundancy Customization Based on Static Analysis
@inproceedings{jiang2018reddroid,
title={RedDroid: Android application redundancy customization based on static analysis},
author={Jiang, Yufei and Bao, Qinkun and Wang, Shuai and Liu, Xiao and Wu, Dinghao},
booktitle={2018 IEEE 29th international symposium on software reliability engineering (ISSRE)},
pages={189--199},
year={2018},
organization={IEEE}
}
1 INTRODUCTION
将安卓应用的软件膨胀分为两类：编译时-多余和加载时-多余
同时我们提出了一个自动化方法删除这两种软件膨胀，我们的方法主要基于静态分析和程序转化
对于 compile-time redundancy
为安卓应用构造一个近似的函数调用图，我们可以移除图中未使用过的函数和类
我们克服了在安卓应用中静态分析的多个挑战，包括 安卓应用的多入口，回调的大量运用，安卓组件的生命周期
我们方法使用静态字符串权值分析处理反射，这只是用了应用的代码而没有其它信息。
对于 instll-time redundancy：我们讨论了两个普遍存在的冗余来源的存在和解决方案，即多个软件开发包（SDKs）和嵌入式应用程序二进制接口（ABIs）。
我们实现了方法原型REDDROID，在超过500个安卓应用进行了评估
我们里算了 代码大小，代码复杂度，反射调用点，冗余SDK大小，冗 嵌入ABIs大小
我们的结果显示
代码大小
在移除 compile-time redundancy时平均15%的应用代码被移除
在移除 install-time redundancy时
如果因冗余SDKs引起，平均20%的应用代码被移除
如果因冗余嵌入ABIs引起，平均7%的应用代码被移除
如果两种冗余能够与都有，可以移除平均42%的代码
代码复杂度 ：显著减小
总结，我们作了以下贡献
我们定义个分类了安卓应用中的软件膨胀
我们提出了一个自动化静态方法来识别和移除安卓应用中的程序膨胀
我们实现了我们的方法原型REDDROID。 实验结果显示我们验证了我们方法的有效性，同时也第一次描绘了安卓应用领域中的代码膨胀现象。这些结果可以帮助开发者了解他们在应用程序资源消耗问题上的痛点，并在未来更好地规划他们的优化。
2 OBSERVATION AND INSIGHTS
A Two Types of Redundancy
基于被确定为冗余的时间进行分类
Compile-time redundancy ：
例子：加密算法库通常只用到一种
库中不适用的代码占代码膨胀的很大一部分，这既是编译时膨胀
Install-time redundancy ：
例子
尽管Java字节码是跨平台的，但软件的其它资源不一定，配置文件，资源文件，二进制文件。
在安卓中，有为了不同设备大小设置的不同配置；还有为不同设备准备的额外SDKs
加载时膨胀即应用中为其它设备平台准备的资源
B The Focus of This Paper
移除未使用的库引起的冗余
移除嵌入的ABIs和SDKs引起的冗余
ABI：与CPU架构相匹配，一旦CPU架构确定，其他的ABI就是冗余的
SDKs：不同的设备有着不同的SDK（如 智慧手表，电视，汽车，IOT设备）；
然而，除手机外，大多数设备不会联网，因此不能下载SDK，需要在手机上下载其对应的APP，APP里包含了设备需要的SDK，但是如果用户没有对应的设备，这些SDK就是多余的
3 DESIGN AND IMPLEMENTATION
A Architecture
包括两个部分：compile-time redundancy remover和install-time redundancy remover
输入：APK文件 输出：瘦身后的APK文件
compile-time redundancy remover包含4部分
dummy main generator:静态分析入口
call graph builder: 构建函数调用图，同时使用基于安卓框架的回调信息分析来增强其集过
reflection solver：解决反射对函数调用图造成的影响
code reducer：移除未在调用图上的类和方法
install-time redundancy remover
Android wear application redundancy remover
redundant embedded ABIs remover
B Call Graph
构建准确的调用图 undecidable，在我们的研究背景下，我们通过忽略调用图的完整性来保持其健全性。
正确性被定义为所有未包含在调用图中的方法都保证不会被调用。
通过忽略完整性，我们意味着调用图中包含的一些方法也可能永远不会被调用。
由于一些程序很大，我们没有使用高昂的图构建方法[8,9],而是使用了一种基于类层次分析（CHA）[10]的更直观的方法来构建它
其遍历所有类建立类的层次信息，构建有向图；其次遍历程序中所有调用点，从DunnmyMain开始，构成有根的有向图
C Android Standard Lifecycle and Dunmmy Main
Android应用不同于Java程序，其有多个入口
Android应用有4种类型的组件：Activity，Service，BroadcastReceiver，ContentProvider。
每个组件有同样的标准的生命周期。为了实现某个句子的组件，开发者必须扩展组件的基类重写一系列安卓框架的回调，如 onCreate，onStart，onStop,onDestroy。
一个组件可以表示一些有趣的事件。所以，安卓框架在不同维度的组件上进行调度，一个应用可以从任何没被 AndroidMainifest.xml上禁止的组件进入
为了使用静态分析框架和算法在安卓框架上，我峨嵋你需要生成一个dummy主方法来模拟安卓框架的调用者和各个组件的生命周期
D Cakkbacks
异步回调是不清楚的控制流转移，在安卓框架种处理和接收UI事件中广泛应用
然而B中的函数调用图不包括回调，因为其不会被用户触发而是被安卓架构触发
我们使用EdgeMiner[12]分析安卓框架，其首先辨识安卓框架中定义且在用户空间被覆写的方法，这些方法是回调的候选者，随后使用后向分析来分析这些方法，获得可能的回调方法。我们会将所有的注册方法连接到所有可能的回调方法的实现
E String Analysis and Reflections
B中方法调用图无法体现反射调用
先前工作有很多措施解决反射，包括 使用开发者的注释和使用测试套件。我们希望使用程序信息及较少的外部信息来解决反射。因此，我们使用静态分析推断在反射调用点字符串变量的集合。
我们的分析基于Violist，一个Java程序字符串静态分析框架[13]
F Sign the Customiazed Application
安卓应用程序必须经过签名才能在安卓系统上运行。
签名过程包括两个步骤。
为应用程序的apk文件中的每个文件生成消息摘要。
其次，开发者或其他代表开发者的人员使用私钥对应用程序中每个文件的消息摘要进行签名。如果一个程序在定制之前已经被签名，那么由于REDDROID会修改应用程序apk中的文件，该程序需要重新签名才能运行
G Implementation
实现原型REDDROID,主要由Java和Unix 脚本实现。包括Java写的编译时冗余移除器和Unix脚本写的安装时冗余移除
使用FlowDroid[14]生成dummy main method，并分析安卓应用
使用Soot[15]将Dalvik字节码转为Soot IR Jimple，我们的分析和代码修改基于Jimple
我们使用Apktool将apk文件中的资源文件从二进制格式反编译回人类可读的ASCII格式
4 EVALUATION
回答以下问题
Q1：compile-time redundancy remover在安卓应用大小上的效果
Q2：compile-time redundancy remover在代码复杂度上的效果
Q3：安卓应用使用的反射调用的数量和种类
Q4：install-time redundancy remover在安卓穿戴设备上的影响
Q5：应用中嵌入的ABIs的占比
Q6：install-time redundancy remover在冗余ABIs上的效果
5 DISCUSSION AND FUTURE WORK
A Issues casued by multiple Android API levels
安卓应用有不同的API级别，相当于SDK版本，然而不同版本间的功能并不是完全包含关系，因此有使用多个API级别的应用，这会导致冗余
为了优化这种情况，我们不仅需要移除包，还需要重写类的描述和包在应用代码中的重要性，这将在我们的未来工作。同时我们在未来将我们的工作放到最新的API级别上
B Feature based Customization
[19,20]讨论了在Java上基于特征的定制，他们基于分析框架API的调用点
在Android系统中，映射到某些特定Android框架API的权限为对Android应用程序进行功能优化提供了理想的处理方式。（基于权限的功能划分）
C Relationship with Other Android Application Compaction Approach
有许多基于打包和压缩来减小安卓应用大小的方法。REDRROID可以与它们一起使用
D Reflections,obfuscation and Soundness
健全性对程序转化很重要。理论上，反射不能被静态决定，然而，现实世界应用程序中反射的使用模式使我们能够绕过许多由反射引起的挑战。
即开发人员很少使用java.lang.reflect.method
代码混淆会增加在冗余和反射上分析的成本，我们可以使用反混淆技术[21,22]
A Static ANalysis on Android Applications and Frameworks
[12] 提出了一个综合的方法通过安卓框架来分析所有的模糊控制流转移
FlowDroid[14]是SOTA工具，在安卓应用的静态污点分析领域
[23]实现Dare，将Android Dalvik字节码转为Java字节码，他们使用推断算法调查转化过程中丢失的信息
Dex2java[24]开源工具，将Dalvik代码转为Java字节码
PScount[25],Stowaway[26]是两个静态分析工具，将安卓框架APIs映射到安卓权限上
Apktool[27]是一个用于对安卓应用逆向工程的工具。将 Dalvik 代码转换为 smali 表示的类。此外还可以解码二进制资源文件，将其还原为原始的可读形式。
FernFlower [28] 是SOTA Java 反编译器。有丰富的命令行选项，使其易于嵌入到脚本和现有工具链中。FernFlower 是 IntelliJ 集成开发环境的默认 Java 反编译器。
B String and Reflection Analysis
解决Java程序中反射的一个方法是后去反射调用的字符串的值，先前已经有很多方法进行字符串分析
Java String Analyzer(JSA)[29]是一个静态分析器来找到程序中给定字符串变量的可能值
Violist[13]提出了一个通用框架来分析Java和安卓程序中的字符串
[30]使用符号执行来进行字符串分析
[31]TamiFlex没有基于符号分析，他们在运行时记录反射调用，然后使用直接方法调用来实现这些间接调用，随后再进行静态分析
C Code and File Compaction Techniques
[2] 提出一个更好地方法来压缩Java class文件来减小包的总大小
[32]在移除 “常链接” 设备上代码更激进，其将代码分为热代码和冷代码，一般只加载热代码，只在必要时加载冷代码
[6,7]通过移除不用的方法和类减小Java应用的大小，但他们不能用在安卓应用上
Lint[5]是一个从安卓应用中移除冗余的注册资源的工具
7 CONCLUSION
本文，我们提出了一个在安卓应用中减少 编译时冗余和加载时冗余的方法，我们实现了一个完全自动化的工具 REDRROID
我们实验结果显示
REDDROID可以通过移除不用的字节码平均减小15%的安卓应用大小。
代码复杂度，由许多知名指标衡量，也显著减小
也可以识别和移除冗余的安卓穿戴SDKs，可以平均减少相关应用20%的大小
通过移除容易的嵌入ABIs，可以平均减小7%的大小
如果一个应用3中膨胀都有，总计可以减少42%的大小
我们的评估结果显示我们的方法在编译时和加载时冗余上是有效的，同时也第一次描绘了安卓应用领域中的代码膨胀现象。
这些结果可以帮助开发者了解他们在应用程序资源消耗问题上的痛点，并在未来更好地规划他们的优化。