《Finding Application Errors and Security Flaws Using PQL a Program Query Language》论文笔记

文章发布时间:

最后更新时间:

Finding Application Errors and Security Flaws Using PQL: a Program Query Language 论文笔记

0x1. 概要

对于漏洞检错工具而言，重要的规则设计在于如何处理事件和关联对象之间相联系。本文提出了一种称为PQL（程序查询语言）的语言，它允许程序员在特定于应用程序的上下文中轻松地表达此类问题。查询类似代码的摘要信息，对应于违反设计规则的最短代码量，是对目标应用程序实现细节的抽象概括。程序员还可以在发现匹配时指定行为，例如记录相关信息或者即时纠错。

同时，本文借助了静态分析和动态分析技术来解决 PQL 查询。首先静态分析使用了：

  1. 上下文敏感分析
  2. 流敏感分析
  3. 基于包含的指针别名分析

以此寻找潜在的匹配结果，进一步用它来减少动态分析时的插桩点。我们的动态分析器对源程序进行检测，以便在程序运行时准确地捕获所有违规行为，并有选择地执行用户指定的操作

0x2. Introduction

本文采用 PQL 查询的思想在于能够让开发者自定义特定于应用的代码模式规则。同时系统自动地从查询生成一对互补的检验器：

  • 静态检查器：寻找应用中所有的潜在匹配
  • 动态检查器：运行时捕获所有产生的匹配，并且可以在匹配时启动用户指定的日志记录或恢复操作

关于概要中所说的事件和关联对象的处理问题，它的意思是说这些相关对象可能存储并在不同的局部变量之间传递、或者作为参数甚至保存在类集合中，同时一系列事件也覆盖在不同的方法不同的谓词上。PQL 可以利用最简单的原型码来表示关联事件，通过抽象不相关的控制流和无视对象的命名（也就是堆抽象？）, PQL 系统可以自动匹配程序中所有等效的行为

静态检查器利用基于 found 的、上下文敏感指针分析（非流敏感）找出所有的潜在匹配，然后动态分析对这些匹配进行插桩标记，检验运行时是否真正发生

  • simple example:

    image-20230326121629770

    利用指针分析来匹配 getParameter 返回 object 和 execute 参数的 object 是否存在交集，如果存在交集就动态插桩标记这些点，当运行时也匹配到时就将 execute 函数替换为 checkedSQL 函数

  • Contributions

    1. 开发了强大的静态分析检查器。并且将复杂的程序分析利用简单的查询语句来表述，开发者使用简单。同时，采用的指针别名分析是 sound 的，意味着会收集到所有的指针指向关系，而不会产生漏报，进一步提供给优化动态检查器
    2. 优化的动态插桩。它这里做了两点改进：首先，PQL 并没有采样传统的基于语法的方法来检测匹配，而是通过匹配对象实例的历史事件信息（调用栈）来判断是否触发；第二，静态分析器产生的结果进一步减少了动态检查时的观测点数。
    3. 动态错误恢复。匹配发现时允许将最后一个触发事件替换为用户指定的函数
    4. 实验评估：程序可有效发现数据库中断或拒绝服务攻击（包括）；查询语句的产生是通过阅读 Java 库的 API 以及错误模式的描述得到

0x3. PQL Language

首先 PQL 关注于追踪方法调用以及获取关联对象的属性和数组元素。另外，本文将动态程序执行抽象为基本事件序列，检查器会去判断是否会有子序列匹配上给出的具体模式。

  • 抽象调用栈

    程序执行被抽象为基本事件的调用序列。PQL 关注于对象上，事件的匹配意味着对象的匹配

    每个事件包含唯一的事件 ID、事件类型和一个属性列表，以下是抽象的 8 类事件：

    • 属性的 loads 和 stores

      属性：[source, target, field name]

    • 数组的 loads 和 stores

      属性：[source, target]

    • 方法调用和返回

      属性：[method invoke, 传参中的对应 object, 返回 object] 返回事件参数包含对应调用事件的 ID

    • 对象创建

      属性：[object, class]

    • 程序结束（无属性）

    ex. 如下针对数组的执行操作代码

    image-20230328093947196

    得到的抽象调用序列如下：

    image-20230328094026525

  • PQL 查询

    PQL 查询分为模式匹配和基于匹配的行为执行两部分。

    首先看模式匹配，对应语法如下。它是由一系列基本事件通过排序、部分排序或交替构成的

    image-20230328095113520

    • 查询变量../../racerz/Desktop/论文笔记

      查询变量对应的是程序中待匹配的对象。

      • object 变量 ：代表堆上的单一 object，拥有 class 名来限制能匹配的对象实力种类。如果以 ! 为前缀，则表示不能匹配的类
      • member 变量：代表属性或方法名。通过文本名来匹配，但是可以采用通配符 * 或 _ 的形式来匹配

    • Statements

      方法的调用会去匹配从调用事件到返回事件之间的所有事件。

      在基本事件中，对象的引用需要在 object 查询变量中声明（或 _ 无视）；成员或方法的引用可以通过字面量或者 member 查询变量中声明

      接下来是三种连接操作符：

      1. a;b 指定 a 之后会跟 b ，但是之间并非连续的 。可以利用 ~ 作排除，因此 a;~_;b 可以表示连续
      2. a|b 表示匹配事件中的任何一个
      3. 偏序语句 a,b,c 用来匹配多个独立事件

      within 可以用来指定全匹配模式（位于 call 和 return 之间）

    • 子查询

      允许指定递归事件序列或递归对象关系。递归的作用在于可以匹配无限数量的对象（只要满足要求），类似上下文无关文法的机制，每个产生式都是相对于堆上的对象独立量化的

      对于递归查询中的 base case ，需要用 a:=b 来强制将返回值与参数统一。同时要保证形参于实参的统一、返回值与调用变量的统一

      以下图为例：

      image-20230328114124081

    • 对匹配的反应

      PQL 提供两种机制来记录匹配信息或执行恢复行为

      1. execute 子句 内置 Util 类中的方法 Util.PrintStackTrace，参数为 * 会打印参数和调用栈信息；Util.Abort 不需要参数，直接结束程序。

        对于自定义方法，返回值要设置为 void

      2. replace 子句 替换监视的方法为想要执行的方法，对于自定义方法需要返回值设置为和被替换方法相同类型

  • Dynamic Macher

    首先说下传统朴素的 PQL 查询匹配方法：

    • 将每一个子查询转换为非确定状态机，输入为事件序列，查找匹配查询语句的子序列，并记录每个匹配项绑定到返回查询变量的值
    • 插桩目标应用以产生完整的抽象调用栈
    • 使用查询识别器来解释所有调用栈上的状态机来检索匹配

    本文在这里所做的优化是：

    1. 插桩代码只会关注于可能产生与匹配查询相关的事件的点
    2. 类型分析排除与查询中的对象无关的类型上的操作
    3. 静态分析排除掉所有无法指向查询中涉及到的对象的语句
    Translation From Queries To State Machines

    状态机代表的查询由下列组成：

    • 状态集合，包括起始状态、失败状态和接受状态
    • 变量参数
    • 状态转移集合

    部分匹配由当前节点和一系列 bindings （PQL 查询中的变量到运行时堆上的映射构成）

    状态机就是以 NFA 的模式作状态转移

    三种特殊的状态转移：

    • Skip transitions 表示自己到自己的状态转移，条件就是只要没匹配到排除事件的集合就发生
    • Null transitions 不对应任何事件，直接发生转换
    • Subquery invocation transitions 也就是匹配支持递归

    本文采用语法制导的方法构建查询的状态机，一个 statement 前后通过 bef(s) 和 aft(s) 状态关联，对应匹配 s 前和后。

    接下来讲一下这两个状态在处理基本事件时是如何表示的：

    • Array and field operations 对于语句 s ，类型为 t。要求输入事件也是类型 t ，并且属性要求和 s 以及当前 bindings 中描述的相统一：即要么相同，要么还未绑定（之后就绑定上去）

    • Exclusion bef(s) = aft(s) skip transitions 修正为不匹配到 s’

    • Sequencing 如果 s = s1; s2 => bef(s) = bef(s1), aft(s) = aft(s2), 且 aft(s1) = bef(s2)

    • Alternation 如果 s = s1|s2 =>

      image-20230329005126044

    • Partial order 如果 s = s1, s2 =>

      image-20230329005336605

    • Method invocation

      image-20230329155940454

    • Creation points

      对象创建通过方法 <init>，处理和 Method invocation 一样

    • Context

      通过将自动机嵌套在 within 子句中来表示，中间有任何匹配未完成都会失败

    • Unification statements

      表示空转移的两端变量值保持一致，要么值相等，要么一个未绑定另一个绑定（然后绑定的值传递给未绑定的）

    • Subquery invocation 子查询匹配可作为基本事件来看待，由识别器单独处理

    Instrumenting the Application

    插桩点：编码（未定事件 + 相关对象）=> 查询识别器 => 更新未定匹配的状态 => 返回

    The Query Recognizer

    识别器会从 main 查询的部分匹配开始，每当匹配上一个事件就会产生一个新的状态，同时会绑定或更新每个事件中涉及的变量。

    一旦部分匹配转移到了 accept 状态，就会以 replaces 或 executes 来处理。

    对于子查询的处理，一旦匹配完成后，就会将返回值更新到调用查询处，并且持续接受新的子查询更新

    为了支持长输入的跟踪，本文维护了一个 hashmap 来记录每个状态转移到事件的映射，每个状态转移中还记录了变量到值的映射集

0x4. 静态检查器 & 优化

本文设计了一种算法可以自动地将 PQL 查询转换为查询指针分析结果

静态分析采用的是 sound cloning-based context-sensitive inclusion-based pointer alias analysis

这种分析在计算每个调用边的指向关系时不需要递归，通过将每个强连通分量视为单个节点，递归程序中的调用路径被简化（？）。

分析结果存储在演绎数据库中，数据表示简化为二元决策图。可通过 Datalog 语言查询

The bddbddb Program Database

本文预设了 PQL 查询中的变量到 bddbddb 数据库输入的转换规则：

数据库的字段：bytecodes B, variables V, methods M, contexts C, heap ob-jects named by their allocation site H, and integers Z

源程序由一系列输入关系来表示：actual, ret, fldld, fldst, arrayld, arrayst 分别对应参数传递，方法返回，field loads, field stores, array loads 和 array stores,

其他针对 datalog 中的关系谓词的设置基本和现在一样

Translation from PQL to Datalog

将每个查询的匹配部分视为交替的 statements 序列

每个基本 PQL 结构的处理如下：

  • Primitive statements

    image-20230329175927367

  • Alternation

  • Sequencing

    根据流不敏感的特性，可直接将; 替换为 , 每一个 Datalog 变量在每个事件中保持新鲜。每个事件对应着一个 bytecode 的触发，如果所带参数未绑定，则说明该参数并未出现在程序中

  • Partial order

    同样每个自居可看作 sequence 的一部分

  • Exclusion

    为了保证 soundess，所有 excluded 事件都直接忽略掉而不考虑其所在位置

  • Within

    需要找到由 m 调用的方法匹配的字节码。可以通过指针分析得到的调用图上找到

  • Unification

    转为堆分配点相等

  • Subqueries

    对应 Datalog relation，子查询中的任何非参数变量将会匹配通配符

Extracting the Relevant Bytecodes

对于每一个子查询，都会找出所有参数对应的程序位置和堆对象，不管是否真正调用。所以我们需要抽离出所有真正参与到查询匹配当中的 bytecodes

通过两步实现：

  1. 找到所有相关的子查询匹配，也就是促成最终结果的查询：这里用分为两种情况：
    1. main 关系中的所有成员都是相关的
    2. 任何查询关系的成员，如果作为子查询调用的转换结果出现在相关关系中，则是相关的。
  2. 抽离出相关的程序位置，将相关查询投影到 bytecode 上：任何出现在由 1 得到的相关结果上的程序位置对于任何查询都是相关的

0x5. Experiment

首先是针对多个开源 Java 应用 bugs 评估静态分析、动态分析（未优化 / 优化）开销以及相应的分析结果

image-20230330203742082

其次针对常见的漏洞特别是 SQL 注入，设计了对应的 PQL 查询语句，构建污点传播分析

image-20230330215936294

本文利用 PQL 开发了一套运行时安全防御系统 「SECURIFLY」，相比于传统防火墙针对模式匹配和流量监控的防御方式，本文的构建防御体系可以更加细粒度因为它观测的是数据流在应用中的流向

0x6. Applications Of PQL

本文提到 PQL 可以编码对系统特定规则的知识，也就是抽象成一种操作模式。如何自动的去发现基于系统的规则是一个挑战性问题。本文提出了污点查询模式：数据 source 产生，通过各种技术传播，最终被用作 sink

其次，对于漏洞匹配查询后调用的事件，通常情况下是将不安全参数替换为安全参数。但这里也可以使用故障注入的方式，即故意注入不安全的值来测试系统的鲁棒性。特别地，他可以很有效地检验 Java 中依赖于特定平台的、C / C++ 编写的 native 方法（常见参数为 Object / array[]），可以通过传入超大数组或者 null 对象来测试是否会导致 JVM 崩溃来判断系统是否健壮。

那么在分析之前，如何找到所有的入口点？

  1. 对框架插桩并查看 this 指针在目标模块调用时的类型
  2. 捕获调用栈（within 范围），检查控制是在哪里开始从框架转到应用

其次，对于反射这种妨碍调用图或者跨函数分析的特性，可以在运行时关注超类的实例（因为经过反射类加载的实例通常都会转换为接口类或抽象类来表示），利用 PQL 表达也很方便

≡