污点分析理解

关于污点分析的一些理解

• 污点分析的定义

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

    1. source 即污点源,代表直接引入不受信任的数据或者机密数据到系统中
    2. sink 即污点汇聚点,代表直接产生安全敏感操作(违反数据完整性)或者泄露隐私数据到外界(违反数据保密性)。
    3. sanitizer 即无害处理,代表通过数据加密或者移除危害操作等手段使数据传播不再对软件系统的信息安全产生危害。

    污点分析就是分析程序中由污点源引入的数据是否能够不经无害处理，而直接传播到污点汇聚点。如果不能，说明系统是信息流安全的；否则，说明系统产生了隐私数据泄露或危险数据操作等安全问题

  • 在漏洞分析中，使用污点分析技术将所感兴趣的数据（通常来自程序的外部输入）标记为污点数据，然后通过跟踪和污点数据相关的信息的流向，可以知道它们是否会影响某些关键的程序操作，进而挖掘程序漏洞。即将程序是否存在某种漏洞的问题转化为污点信息是否会被sink点上的操作所使用的问题

• 分为静态污点分析和动态污点分析

  • 静态污点分析只使用程序代码模拟污点传播过程。是指在不运行且不修改代码的前提下，通过分析程序变量间的数据依赖关系来检测数据能否从污点源传播到污点汇聚点。分析对象一般是程序的源码或中间表示。可以将显式流分析转化为怼程序中静态数据依赖的分析

  • 当前，利用数据流分析解决显示污点传播分析中的直接赋值传播和函数调用传播已经相当成熟。研究的重点是如何为别名传播的分析提供更精确、高校的解决方案。由于精度越高（上下文敏感、流敏感、域敏感、对象敏感等）的程序静态分析技术往往伴随着越大的时空开销。追求全敏感且高效的别名分析难度较大。又由于静态污点传播关注的是从污点源到污点汇聚点之间的数据流关系，分析对象并非完整的程序，而是确定的入口和出口之间的程序片段，因此可以采用按需定制的别名分析方法来解决显式流污点分析中的别名传播问题。

    • TAJ工具 使用混合切片结合对象敏感的别名分析来进行Java Web应用上的污点分析
    • Andromeda工具使用了按需的对象敏感别名分析技术解决对象的访问路径(access path)问题
    • FlowDroid工具提出一种按需的别名分析,从而提供上下文敏感、流敏感、域敏感、对象敏感的污点分析,用以解决 Android的隐私泄露问题

  • 过程内分析

    • 基本思想：从上至下遍历数据流图，若未标记的变量依赖于污点变量，则新变量要被标记为污点变量
    • 
    • 显式流分析：通过分析变量的数据依赖关系进行污点传播（图中的实线箭头）-----基于数据流的污点分析
    • 隐式流分析：考虑控制依赖进行污点传播（图中的虚线箭头）分析复杂，容易产生误报-----基于依赖关系的污点分析
    • 基于数据流的污点分析
      1. 记录污点信息。通常为变量添加一个污染标签，最简单的是一个布尔型变量，表示变量是否被污染。更复杂的标签可以记录变量的污染信息来自哪些 Source 点，甚至精确到 Source 点接收数据的哪一部分。当然也可以不使用污染标签，这时我们通过对变量进行跟踪的方式达到分析污点信息流向的目的。例如使用栈或者队列来记录被污染的变量。
      2. 程序语句的分析。通常只关注赋值语句、控制转移语句以及过程调用语句
         • 赋值语句
           • 对于简单的赋值语句，形如 a = b 这样的，记录语句左端的变量和右端的变量具有相同的污染状态。程序中的常量通常认为是未污染的，如果一个变量被赋值为常量，在不考虑隐式信息流的情况下，认为变量的状态在赋值后是未污染的
           • 对于形如 a = b + c 这样带有二元操作的赋值语句，通常规定如果右端的操作数只要有一个是被污染的，则左端的变量是污染的（除非右端计算结果为常量）
           • 对于和数组元素相关的赋值，如果可以通过静态分析确定数组下标的取值或者取值范围，那么就可以精确地判断数组中哪个或哪些元素是污染的。但通常静态分析不能确定一个变量是污染的，那么就简单地认为整个数组都是污染的
           • 对于包含字段或者包含指针操作的赋值语句，常常需要用到指向分析的分析结果
         • 控制转移语句
           • 首先考虑语句中的路径条件可能是包含对污点数据的限制，在实际分析中常常需要识别这种限制污点数据的条件，来判断这些条件是否足够包含程序不会受到攻击。如果路径条件的限制是足够的，那么可以将相应的变量标记为未污染的
           • 对于循环语句，规定循环变量的取值范围不能受到输入的影响。例如在语句 for (i = 1; i < k; i++){} 中，规定循环的上界 k 不能是污染的
         • 过程调用语句
           • 使用过程间的分析或者直接应用过程摘要进行分析。过程摘要主要描述怎样改变与该过程相关的变量的污染状态，以及对哪些变量的污染状态进行检测。这些变量可以是过程使用的参数、参数的字段或者过程的返回值等。例如在语句 flag = obj.method(str); 中，str 是污染的，那么通过过程间的分析，将变量 obj 的字段 str 标记为污染的，而记录方法的返回值的变量 flag 标记为未污染的
           • 在实际的过程间分析中，可以对已经分析过的过程构建过程摘要。例如前面的语句，其过程摘要描述为：方法 method 的参数污染状态决定其接收对象的实例域 str 的污染状态，并且它的返回值是未受污染的。那么下一次分析需要时，就可以直接应用摘要进行分析
      3. 代码遍历。通常使用流敏感或者路径敏感的方式遍历，并分析过程中的代码。
         • 如果使用流敏感的方式，可以通过对不同路径上的分析结果进行汇集，从而发现程序中的数据净化规则
         • 如果使用路径敏感的分析方式，则需要关注路径条件，如果路径条件中涉及对污染变量取值的限制，可认为路径条件对污染数据进行了净化。还可以将分析路径条件对污染数据的限制进行记录，如果在一条程序路径上，这些限制足够保证数据不会被攻击者利用，就可以将相应的变量标记为未污染的

  • 过程间分析

    • 构造函数调用流图，搜索存在source的函数，对于每一个source的函数，自顶向下分析（也可以自底向上）。遇到函数调用时，跟进被调函数，进行过程内污点分析，将分析结果表达为摘要信息，然后根据函数摘要，再进行过程内分析，如此往复直至分析完函数所有代码块或是污点传播到sink点，报告漏洞
    • 
    • 如上图所示，分析过程从左侧函数开始request.getParameters("xss")于是将污点传递到了p，接着调用func(p)，于是对func做过程内分析，得到其函数摘要，回到调用者的函数内，变量q被标记为污点。然后第三行response.getWriter.print()是一个sink点，并且参数为污点，于是报告此处有漏洞，并根据汇聚点可以判断该漏洞是一个xss漏洞

  • 动态污点分析是在程序运行的基础上，对数据流或控制流进行监控，从而实现对数据在内存中的显式传播、数据误用等进行跟踪和检测。首先需要为污点数据扩展一个污点标记的标签，并将其存储在存储单元（内存、寄存器、缓存等）中，然后根据指令类型和指令操作数设计相应的污点逻辑传播污点标记

  • 可以被分为基于硬件、基于软件以及混合型的污点传播分析

    • 基于硬件：需要定制的硬件支持，一般需要在原有体系结构上为寄存器或者内存扩展一个标记位，用来存储污点标记，代表的系统有Minos, Raksha等

    • 基于软件：通过修改程序的二进制代码来进行污点标记位的存储与传播，代表的系统有TaintEraser, TaintDroid等

    • 混合型：通过尽可能少的硬件结构改动以保证更高的语意逻辑的安全策略，代表的系统有Flexitaint, PIFT等

    • 基于软件的污点传播的优点在于不必更改处理器等底层的硬件，并且可以支持更高的语义逻辑的安全策略(利用其更贴近源程序层次的特点)，但缺点是使用插桩(instrumentation 在保证被测程序原有逻辑完整性的基础上在程序中插入一些探针)或代码重写(code rewriting)修改程序往往会给分析系统带来巨大的开销。相反地，基于硬件的污点传播分析虽然可以利用定制硬件降低开销，但通常不能支持更高的语义逻辑的安全策略，并且需要对处理器结构进行重新设计

    • 目前,针对动态污点传播分析的研究工作关注的首要问题是如何设计有效的污点传播逻辑,以确保精确的污点传播分析.

    • 分为三个部分

      1. 污点数据标记。来自外部的输入数据会被标记为污点数据。根据输入数据来源的不同，可分为三类：网络输入、文件输入和输入设备输入

      2. 污点动态跟踪。在污点数据标记的基础上，对过程进行指令粒度的动态跟踪分析，分析每一条指令效果，直至覆盖整个程序的运行过程，跟踪数据流的传播。

         • 通常基于以下三种机制：
         1. 动态代码插桩。可以跟踪单个进程的污点数据流动，通过在被分析程序中插入分析代码，跟踪污点信息在进程中的流动方向
         2. 全系统模拟。利用全系统模拟技术，分析模拟系统中每条指令的污点信息扩散路径，可以跟踪污点数据在操作系统内的流动
         3. 虚拟机监视器。通过在虚拟机监视器中增加分析污点信息流的功能，跟踪污点数据在整个客户机中各个虚拟机之间的流动
         • 通常需要影子内存（shadow memory）来映射实际内存的污染情况，从而记录内存区域和寄存器是否是被污染的。对每条语句进行分析的过程中，污点跟踪攻击根据影子内存判断是否存在污点信息的传播，从而对污点信息进行传播并将传播结果保存于影子内存中，进而追踪污点数据的流向
         • 一般情况下，数据移动类和算数类指令都将造成显示的信息流传播。为了跟踪污点数据的显示传播，需要在每个数据移动指令和算数指令执行前做监控，当指令的结果被其中一个操作数污染后，把结果数据对应的影子内存设置为一个指针，指向源污染点操作数指向的数据结构

      3. 污点误用检查。在正确标记污点数据并对污点数据的传播进行实时跟踪后，就需要对攻击做出正确的检测即检测污点数据是否有非法使用的情况

    • 优缺点

      • 优点：误报率较低，检测结果可信度较高
      • 缺点：
        • 漏报率较高：由于程序动态运行时的代码覆盖率决定的
        • 平台相关性较高：特定的动态污点分析工具只能够解决在特定平台上运行的程序
        • 资源消耗大：包括空间上和时间上

  • 静态污点分析不真正运行程序，而是通过模拟程序的执行过程来传播污点标记，而动态污点分析技术需要运行程序，同时实时传播并检测污点标记

• 优势和不足

  • 污点分析能够对程序上下文有一定理解，往往能产生误报率相对较低以及可解释的漏洞报告，对web类型的安全漏洞覆盖率较高
  • 仍有可能发生误报。以下面四例说明
    • 
      1. 无法对容器类型做很好处理。如(a)所示，当污点传入容器类型(map)时，静态污点传播只能将这类变量的传播规则设为传播/不传播污点，从而造成过污染/欠污染。如果设为传播污点，由于案例实际从容器中取出的是没有污点的变量，即过污染。如果设为不传播，若q取出参数p，那么欠污染。
      2. 无论是静态污点传播还是动态污点传播，其对污点清洁点的识别能力几乎为0。如(b)所示，该函数是一个典型的防御 SQL 注入的污点清洁函数，即在第 2∼5 行对待拼接 SQL 字符串存在的特殊字符进行替换和过滤，但 是污点传播并不能识别这些清洁函数，导致误报
      3. 静态污点传播对控制流无法做很好的处理。如图(c)所示，在第三行，程序已经对可能产生的 SSRF 漏洞进行了处理，即如果是内部地址则直接返回，但是不论是考虑显式流还是隐式流，污点传播都不能避免这一类误报
      4. 对于特殊触发条件的漏洞，污点传播无法很好处理。如图(d)所示，在第二行，因为 SSRF 要求攻击者能够操控主机名，所以即使用户输入的污点变量拼接在一个正常主机名之后，程序也不会出现 SSRF ，而按照污点传播分析法，毫无疑问它会报告这段程序存在 SSRF 漏洞

• 使用污点分析检测程序漏洞的工作原理

  • 

• 基于数据流的污点分析

  • 一些辅助分析技术。例如别名分析、取值分析等，和污点分析交替进行，沿着程序路径的方向分析污点信息的流向，检查 Source 点处程序接收的污点信息是否会影响到 Sink 点处的敏感操作

• 基于依赖关系的污点分析

  • 首先利用程序的中间表示、控制流图和过程调用图构造程序完整的或者局部的程序的依赖关系。在分析程序依赖关系后，根据污点分析规则，检测sink点敏感操作是否依赖于source点
  • 分析依赖关系的过程，可以看作是构建程序依赖图的过程。程序依赖图是一个有向图。它的节点是程序语句，它的有向边表示程序语句之间的依赖关系。程序依赖图的有向边常常包括数据依赖边和控制依赖边。对于规模较大的程序依赖图，需要按需构建依赖关系，并且优先考虑和污点信息相关的程序代码

• 动态污点分析的方法实现

  • 污点数据标记。污点数据通常是指软件系统所接受的外部输入输入，这些数据可能以内存临时数据的形式存储，也可能以文件的形式存储。当程序需要使用这些数据时，一般通过函数或系统调用来进行数据访问和处理，因此只需要对这些关键函数进行监控，即可得到程序读取或输出了什么污点信息。对于网络输入，也需要对网络操作函数进行监控

  • 识别出污点数据后，需要对污点进行标记。污点生命周期是指在该生命周期的时间范围内，污点被定义为有效。污点生命周期开始于污点创建时刻，生成污点标记，结束于污点删除时刻，清除污点标记。

    • 污点创建
      • 将来自于非可靠来源的数据分配给某寄存器或内存操作数时
      • 将已经标记为污点的数据通过运算分配给某寄存器或内存操作数时
    • 污点删除
      • 将非污点数据指派给存放污点的寄存器或内存操作数时
      • 将污点数据指派给存放污点的寄存器或内存地址时，此时会删除原污点，并创建新污点
      • 一些会清除污点痕迹的算数运算或逻辑运算操作时

  • 动态污点跟踪

    • 污点传播规则：

      指令类型	传播规则	举例说明
      拷贝或移动指令	T(a)<-T(b)	mov a, b
      算数运算指令	T(a)<-T(b)	add a, b
      堆栈操作指令	T(esp)<-T(a)	push a
      拷贝或移动类函数调用指令	T(dst)<-T(src)	call memcpy
      清零指令	T(a)<-false	xor a, a

    • 对于污点信息流，通过污点跟踪和函数监控，已经能够进行污点信息流流动方向的分析。但由于缺少对象级的信息，仅靠指令级的信息流动并不能完全给出要分析的软件的确切行为。因此，需要在函数监控的基础上进行视图重建，如获取文件对象和套接字对象的详细信息，以方便进一步的分析工作

    • 根据漏洞分析的实际需求，污点分析应包括两方面的信息

      • 污点的传播关系，对于任一污点能够获取其传播情况
      • 对污点数据进行处理的所有指令信息，包括指令地址、操作码、操作数以及在污点处理过程中这些指令执行的先后顺序等等

    • 污点动态跟踪的实现通常使用：

      • 影子内存：真实内存中污点数据的镜像，用于存放程序执行的当前时刻所有的有效污点
      • 污点传播树：用于表示污点的传播关系
      • 污点处理指令链：用于按时间顺序存储与污点数据处理相关的所有指令

    • 当遇到会引起污点传播的指令时，首先对指令中的每个操作数都通过污点快速映射查找影子内存中是否存在与之对应的影子污点，从而确定其是否为污点数据。然后根据污点传播规则得到该指令引起的污点传播效果，并将传播产生的新污点添加到影子内存和污点传播树中，同时将失效污点对应的影子污点删除。由于一条指是否涉及污点数据的处理，需要在污点分析过程中动态确定，因此需要在污点处理指令链中记录污点数据的指令信息

  • 污点误用检查

    • 污点敏感点sink点，是污点数据有可能被调用的指令或系统调用点，主要分为：
      • 跳转地址：检查污点数据是否用于跳转对象，如返回地址、函数指针、函数指针偏移等。具体操作是在每个跳转类指令（如call、ret、jmp等）执行前进行监控分析，保证跳转对象不是污点数据所在的内存地址
      • 格式化字符串：检查污点数据是否用作printf系列函数的格式化字符串参数
      • 系统调用参数：检查特殊系统调用的特殊参数是否为污点数据
      • 标志位：跟踪标志位是否被感染，及被感染的标志位是否用于改变程序控制流
      • 地址：检查数据移动类指令的地址是否被感染
    • 在进行污点误用检查时，通常需要根据一些漏洞模式来进行检查，首先需要明确常见漏洞在二进制代码上的表现形式，然后将其提炼成漏洞模式，以更有效地指导自动化的安全分析

• 优化污点分析的方法

  • 提高污点数据识别的精度。污点源识别不当很容易造成污点标签在程序中的错误扩散，继而影响污点分析技术的准确性和分析效率
  • 制定更科学的污点传播策略。污点传播策略的选择与污点分析的精度和效率关系密切，比如有的工具（如IPSSA）在处理污点传播时采用了保守的策略，将所有与五点数据有关的操作均认定为符合污染传播规则，扩大了污点属性的标记范围，降低了精确度；有的细粒度污点分析工具在执行粗粒度分析时，占用了过多的系统资源，导致分析效率不高。。。结合分析，指定科学的传播规则。例如在函数级污点的传播过程中采用函数摘要思想，使污点在函数外层快色传播，避免了函数内部指令插桩等系统开销较大的操作。。在污点分析过程中，筛选出与污点数据相关的操作的同时忽略与污点数据无关的的指令
  • 引入新的算法。一方面是将污点分析问题转换为其他问题，如：静态分析框架Parfait，，在程序预处理阶段将污点分析问题转换为图可达性问题；另一方面是采取并行处理技术进行污点分析，提高执行速度。如动态分析框架DTAM可并行执行的多线程单元的污点分析，再将分析结果聚合