信息流分析是防止信息的保密性和完整性被破坏的一种有效手段，它通过分析程序中数据传播的合法性来保证信息安全。而污点分析技术作为信息流分析技术的一种实践方法，目前被广泛用于系统隐私数据泄露检测、系统安全漏洞发掘等领域。

污点分析可以抽象成一个三元组<sources,sinks,sanitizers>的形式：

污点分析就是观察程序中由source引入的数据是否能不经sanitizer，直接传播到sink。如果不能，说明系统信息流是安全的；否则，说明系统可能存在隐私数据泄露或危险数据操作等安全问题。

污点分析的处理过程可以分为三个阶段，如下图所示：

（1）识别污点源和汇聚点

（2）污点传播分析

（3）无害处理   

目前，识别污点源和汇聚点没有普适的方法。究其原因有两方面：一方面，系统模型和编程语言存在差异；另一方面，根据关注的安全漏洞类型不同，需要采用的识别方法也会不同。目前使用的方法可以分成以下3类：

污点传播分析是分析标记为taint的数据在程序中的传播途径，可以将其分为显式流分析和隐式流分析两类。

显式流分析是分析taint标记如何随程序中变量之间的数据依赖关系传播。以下图所示的程序为例，首先变量a、b被污点源函数source标记为taint。由于x和y的值在计算过程中依赖于a和b，因此a和b将taint标记传播给了x和y。x和y被标记为taint后，又分别可以到达sink，所以该代码存在信息泄露问题。

隐式流分析是分析taint标记如何随程序中变量之间的控制依赖关系传播。以下图所示的程序为例，变量X被污点源函数source标记为taint，变量Y和变量X之间并没有直接的数据依赖关系，但通过以下循环，Y和X的值最终相同。X上的taint标记就这样隐式地传播到Y，Y最后到达sink，所以该程序存在信息泄露问题。

通过这个例子可以发现隐式流分析不容易发现且可能误判，由此引出了两类问题。对隐式流污点传播处理不当导致本应被标记的变量没有被标记的问题称为欠污染问题。相反地，污点标记的数量过多而导致污点变量大量扩散的问题称为过污染问题。

taint数据在传播的过程中可能会经过sanitizer，sanitizer是指taint数据经过它的处理后，数据本身不再携带敏感信息或者针对该数据的操作不会再对系统产生危害。

对sanitizer的识别有这几种情况：对于携带敏感信息的数据，考虑到保密性通常会对其进行加密处理，因此加密函数应该被识别为sanitizer。对于用户可以输入的地方，考虑到完整性通常会对其进行验证，因此输入验证模块应该被识别为sanitizer。除了输入验证函数外，系统可能还使用其他输入验证工具，这些工具也应该被识别为sanitizer。

静态污点分析是指在不运行且不修改代码的前提下, 通过分析程序变量间的数据依赖关系来检测数据能否从污点源传播到污点汇聚点。针对Android的静态污点传播分析是围绕组件展开的，可以分为组件内污点传播、组件间污点传播、组件与库函数之间的污点传播这3类。如下图所示，下面会对每一类污点传播分析遇到的问题进行说明，并给出开源工具FlowDroid的解决方法。

组件内部污点分析面临的主要问题是如何构建完整的分析模型。和C/C++程序有单一入口函数main不同的是，Android应用程序有多个入口函数。这个情况是因为 Android 应用程序有复杂的运行生命周期以及程序中存在大量的回调函数和异步函数调用。由于任何的程序入口都有可能是taint的来源，在静态的污点分析开始之前必须构建完整的应用程序模型，这样才能确保程序中每一种可能的执行路径都会被静态污点传播分析覆盖到。

FlowDroid采用的解决方法是：首先，在XML配置文件中提取与Android生命周期相关的入口函数，将这些方法作为节点，并根据Android生命周期构建调用图，如下图所示。对于回调函数，FlowDroid在调用图的基础上增加不透明谓词节点（图中P节点），然后增量式地将回调函数加入这个调用图。最后将调用图上所有的执行入口连接到一个虚拟的Main函数上。这样FlowDroid就可以以虚拟Main函数作为唯一入口对调用图进行遍历。

组件间通信是通过组件发送Intent消息对象完成的。如下图所示，显式Intent使用一个包含目标组件名称的参数指定通信的下一个组件；而隐式Intent使用action，category等域隐式地让Android系统通过IntentFilter自动选择下一个组件调用。目前解决该问题的主要思想是利用Intent参数信息分析组件间的数据流。

解决组件间数据流的前提是解析Intent的目的地，解析Intent目的地包括解析显式Intent的目的地和隐式Intent的目的地这两种情况。解析显式Intent目的地的常用方法是使用字符串分析工具提取Intent中字符串参数的信息。解析隐式Intent目的地的主要方法是分析配置文件信息与Intent Filter注册器之间的映射关系，建立发送Intent组件和接受Intent组件之间的配对关系。

组件与库函数之间的污点传播分析面临的主要问题包括对Android库函数自身庞大的代码量的分析以及组件和某些库函数使用的实现语言不同这两方面。

FlowDroid采用的方法：根据库函数的参数与返回值之间的关系手动地提供显式传播规则，FlowDroid依照该规则进行标记。对于没有制定规则的库函数，FlowDroid 使用保守的策略：只要库函数的参数中包含taint数据,就将该函数的返回值标记为taint。

参考文章

[1] https://en.wikipedia.org/wiki/Taint_checking

[2] 王蕾,李丰,李炼,冯晓兵.污点分析技术的原理和实践应用.软件学报,2017,28(4):860−882.

[3] 任玉柱，张有为，艾成炜.污点分析技术研究综述[J].计算机应用，2019，39（8）：2302-2309.

[4]https://firmianay.gitbooks.io/ctf-all-in-one/content/doc/5.5_taint_analysis.html