在做项目，记录一篇论文的阅读笔记

摘要

JAVA程序中的AC漏洞

一. 引言

一些AC漏洞例子 Decompression Bombs: https://en.wikipedia.org/wiki/Zip_bomb Bilion Laughs Attach: https://en.wikipedia.org/wiki/Billion_laughs_attack ReDoS: https://en.wikipedia.org/wiki/ReDoS Hash-table DoS Attack: https://fahrplan.events.ccc.de/congress/2011/Fahrplan/events/4680.en.html Zip Bomb: https://www.theregister.com/2001/07/23/dos_risk_from_zip/
目前存在的一些问题 state explosions
ACQIRER的优势
1. 继承静态分析器
2. 构建必要的调用上下文和目标程序仪器，自动生成动态符号执行的测试线束，以此来验证漏洞，然后使用注入的程序，执行的测试线束。然后，它使用注入的程序，在从这些模式中学到的分支策略指导下执行选择性动态符号执行，从而高效地验证是否存在两条具有显著成本差异的路径。这种动态验证器有助于ACQIRER排除误报。
3. 它报告的路径约束还能帮助开发人员分析和修复漏洞。

二. 背景

AC DOS AC DOS attack是一种新的low-bandwidth DoS attack，它利用了程序中的算法缺陷，具体地说，对于目标程序中接受用户输入的函数，存在两个大小相似的输入，他们的运行时间可能大不相同。

问题一：整理常见的、具有时间复杂度缺陷的算法，并理解为什么会造成这些缺陷

常见诱发AC DOS的算法
1. 排序
  1. 插入排序
2. 树遍历
AC DOS自动/半自动检测方法
1. 代码结构分析：识别执行时间可变的程序结构
  1. 举例：循环/递归
  2. 工具：DISCOVER 最先进的静态分析工具
    1. 定义并收集了一个“循环特征”列表
    2. 只能分析基本循环，不能分析包含其他控制结构（条件、跳转和内循环）的复杂循环，因为它们的控制流很难静态确定
2. 计算成本分析
  1. Fuzz：生成不同的测试输入，以测试不同的程序路径，从而检测高成本路径
    1. 需要大量工程工作来开发测试线束
    2. 自动测试生成功能，要么需要人类定义的现有测试线束，要么为单个方法生成不考虑其调用上下文的人工测试线束
  2. SE：这块没读明白，之前没了解过SE

问题二：了解Fuzz工作原理，了解AC漏洞建模是什么，了解SE，

三. 问题陈述

研究目标与挑战
1. AC漏洞建模：提出适用于具有不同计算成本的不同程序的易受攻击代码模式
2. Path Explosion：找到潜在的易受攻击路径
3. 自动测试：为每个程序自动生成兼容的测试数据
定义
1. 定义了绝对和相对计算成本，通过测量JVM中已执行指令的数量来估算计算成本，假定所有指令的计算成本顺序大致相同，真正成本取决于具体架构
2. 条件和分支策略生成器

四. 成本差异代码模式-modeling AC vulnerability

Vulnerable Conditional Patterns
1. 概述：生成分支策略的决策依据
2. 分类
  1. Non-Determined Loops：没看明白
  2. Single-Branch Conditionals in Loops：只有一个分支的条件语句，采用该分支会增加计算成本
  3. Termination-Branch Conditionals in Loops：return/exception，不进入return/exit/异常，就会增加计算成本，但有时异常处理代码的成本也可能会更高(tru-catch)

五. ACQUIRER

5.1 功能简介 按照第四部分介绍的模式来静态分析代码漏洞，并且生成接下来要讲的branch policies。然后按照policies，通过动态符号执行，来找出一条快速路径和一条慢速路径，并得出他们的计算开销。并且还可以为每一个潜在的漏洞生成test harness。有选择性地过滤非漏洞循环
5.2 Branch Policy(分支策略)

概述
1. 目的：确定快慢路径
2. 程序内静态分析通过全局CFG(控制流图)
  1. 全局CFG是目标程序的字节码来分析的
  2. We enhance the global CFG with a call graph, where the call target at a call site includes all the possible callees for polymorphic calls.这句没读懂
  3. 将一些调用函数视作内联函数
3. 支持通过用户注释来分析external methods
Determining Branch Choices
1. 终止条件：有一条边连到循环外的代码块 / 包含return或throw的代码块
2. 单分支（没太读懂）：
3. 决策(参考listing 1)：绕过结束分支，然后根据单分支的两条路径，选择计算开销大的那个，并继续迭代
Resolving Branch CHoice Conflicts
1. Conditional in Loop：终止分支 > 未确定循环 > 单分支条件,
2. Alternative Loops：
3. Nested Loops：内层循环 < 外层循环
Loop-level Policy
1. 概述：循环级策略，构造了一个循环的“条件-值”的映射
Function-level Policy
1. 概述：函数级策略，我们先通过函数内包含的循环来生成慢速策略，然后通过合并慢速策略来生成函数级策略
2. Reaching Vulnerable Loops：没看懂
3. Generating Function Policy：没看懂

5.3Selective Dynamic Symbolic Execution

概述：依据5.2生成的分支策略，通过符号执行来测试快慢分支的绝对和相对计算开销，进而为后续报告漏洞提供数据。
Selective Path Exploration：没太看懂路径约束是啥，路径约束器求解的又是啥
Vulnerability Validation：有点抽象

5.4 Test Harness Generation

概述：包含一个测试执行程序和相关测试脚本，测试脚本应指定要调用的函数/方法，并提供必要的调用上下文（如参数、对象等）
calling context
1. 出现目的：当代码量巨大时，编译代码并运行到漏洞位置将会耗费相当长的时间，所以我们希望能够自动生成上下文，然后通过测试脚本来针对这一小段代码进行测试
2. 注意上下文只包含必要的函数/语句，因为有些传进来的参数可能经过”消毒“，已经变得不可控

5.5 Non-Vulnerable Code Block Filtering 1. 概述：过滤不可能利用的循环，进而减少分析时间。该论文采取的策略相对保守 2. 分类 1. Unreachable Loops：过滤绝对无法调用的函数 2. (Almost) - Constant Cost Loops：迭代器/计数器以常量为界，或者以”以常量为界“的变量为界的循环，迭代次数可以确定，过滤。 3. Determined Loops：有点没理解

六. Implementation

6.1 Calling Context Construction
1. 有点晕乎，跟符号执行有关，应该就是生成一段代码，这段代码截取了程序的一个慢速路径和该路径上的所有的传参过程。目的是尽快测试出这条路径的计算开销。

Code Instrumentation
1. 更懵了...看起来像是拿自己写的工具里面的一些自己做的类，替换了原来的数据类型，方便在自己的工具里面进行下一步的操作？
Dynamic Symbolic Execution
1. 没读懂

问题三：了解一下符号执行

NaN. 一些想法

程序主体
1. 我们也要构建CFG的话，首先要对二进制程序的字节码进行反汇编，并且根据反汇编的一些跳转语句，来生成CFG
2. 根据CFG来决策Branch，是否需要一些图论的知识？
3. modeling AC vulnerability 需要我们人工设定一些路径选择
扩展
1. 可以耦合一些反混淆工具
2. 论文5.4中说”想要静态分析任意代码段的可执行性十分困难“，这个可以作为我们一个进步点来用
全局问题
1. 有什么应用呢？服务器上有什么服务可以让我们通过AC DoS来打一下？
2. 架构不同，机器码不同，反汇编不同。怎么保证都可以用？

HeyGap's_Blog

2023CCS-Acquirer 算法复杂性漏洞论文阅读笔记

摘要