# Path-sensitive fuzzing on LibFuzzer

## 当前的实现

### 自定义插桩

首先引入`sanitizer_coverage_pc_guard`，在每一个basic block插入一个桩，在桩里面报告当前的PC和栈帧指针，这个是在libfuzzer那边做的

然后会经过一个自定义的LLVM Pass，插了以下的几种桩：

- 循环的Header Block，报告当前所在的循环的Loop ID
- 循环的Exit Block，报告当前可能退出的循环的Loop ID
- 函数入口块，报告当前的函数ID
- 函数出口块，报告当前的函数ID

循环的分析使用的是LLVM自带的LoopInfo Analyzer，由于RUST中存在静态链接的库，直接以二进制形式链接进来，所以这些插桩并不一定能够覆盖所有的函数，但可以保证用户RUST代码是全部覆盖的

### 路径计算

当前值curr初始为0，每遇到一个新的PC地址，就计算curr = SimpleHash(curr, pc)，当一个函数返回的时候，即完成了这个函数中的一条路径执行，收集当前的这个curr hash值到fuzzer里，按照函数分别储存

### 函数处理

使用一个栈保存当前的函数状态，存一个<当前函数地址，当前Hash>的数据结构，当一个新的函数调用时，就将调用前的状态压入栈中保存，然后新建一个新的函数状态处理新函数。当新函数返回时，收集该路径，然后将之前栈中的函数状态弹出来，继续向下处理此前的函数

判断函数的调用与返回主要通过自定义插桩进行，考虑到可能存在一些未插桩的函数，也用栈帧地址辅助判断，若栈帧地址发生了改变，则出现了函数的调用与返回

RUST编译时存在一些神奇操作，将RBP寄存器当作通用寄存器计算，针对此情况做了workaround，若rbp变成了一个非合法地址的值，那么无视这个栈帧的变化

### 循环处理

目前的策略是当一个循环执行超过N次（暂定N=3），那么循环体内之后执行的所有地址全部被path计算忽略，直到退出循环为止

考虑到循环也存在类似于函数的嵌套关系，实现时同样使用一个栈，保存<循环ID，第几次执行，是否需要忽略当前循环内容的Flag>的数据结构，与函数处理同理，在循环的入口和出口进行判断。当访问一个循环入口超过N次时，将Flag置为true，之后在计算路径时，若这个Flag为true，则跳过该地址。

### 覆盖率反馈

目前没有使用什么特别的算法，仅将得到的path hash本身作为feature进行反馈

### 种子调度

目前没有修改

## 遇到的问题

### 问题1：路径爆炸

- 情况1：标准库产生大量路径（solved）

解决方法：做选择性插桩，将标准库与非当前需要考虑的namespace中的自定义插桩全部删除，仅保留libfuzzer自带的coverage桩

潜在问题：如果需要的代码对于fuzzer来说本身就比较难以进入，那么删除其他代码中的桩将导致fuzzer长时间找不到合理的反馈

例如对于move-bytecode-verifier项目，输入需要先过move_binary_format::的一些check，才能到达move_bytecode_verifier::的代码，而在使用空corpus的情形下，前面的check比较难以通过，若删除这个namespace的插桩，就会导致fuzzer很长一段时间找不到interesting input

- 情况2：循环-分发器结构导致路径爆炸（solved）

解决方法：使用自定义插桩标记循环的入口和出口，当fuzzer中循环入口执行了一定次数（例如，3次）之后，在循环退出前，不记录这其中的任何代码执行

潜在问题：一些需要多循环次数才能到达的代码会被无视，例如Q7提供的move bytecode corpus，9000个文件中只有400多个能带来unique path（实际上可以认为是只考虑了前3条move指令）

- 情况3：高级别的优化带来大量inline与函数合并，使单个函数变得非常巨大（partial solved）

例如，[https://github.com/solana-labs/rbpf/blob/main/src/jit.rs](https://github.com/solana-labs/rbpf/blob/main/src/jit.rs)的emit_subroutines函数

将代码优化全部关闭（`-Copt-level = 0`），可以防止全部的inline，但此时执行效率过低

使用annotation（`#[inline(never)]`）与LLVM的参数（`Cllvm-args="-inline-threshold=0 -inlinehint-threshold=0”`），可以防止部分的inline，但这只是针对编译器的建议，无法完全防止inline，例如[https://godbolt.org/z/WKfevdW37](https://godbolt.org/z/WKfevdW37)

一些数据：（测试项目为move-bytecode-verifier，用了一个大小为200的corpus）

标准优化，经过了112个函数，执行速度约1500exec/s

手工关inline，经过了428个函数，执行速度约300exec/s，corpus被保留162个

关闭全部优化，经过了1019个函数，执行速度约50exec/s，corpus被保留133个

- 情况4：函数真的有过多的basic block，例如超过1000个

这个情况不多，之前的inline实际上也是最终会变成这个情况，考虑限制单个函数中path的数量？

### 问题2：执行效率过低

由于原版Libfuzzer使用Feature去做反馈，效率非常高，且是先判断是否有新Feature，有的话再收集coverage，而目前我们的实现里面对于所有的执行，都要计算path然后才能判断是否存在新path coverage，所以会带来很大的overhead

目前相比于原版，执行速度约为1/20，可以先进行一些工程上的优化？

## 一些想法

### 将path coverage作为标准libfuzzer的补充

目前我们的这个fuzzer，由于执行效率问题，在相同时间内对于程序的探索能力是不如原版libfuzzer的，而且在遇到path相当多的函数时，很容易卡死在这一个函数里不断的增加path。

考虑首先使用原版的反馈方式探索程序，待coverage收敛之后，再以一个缓慢增长的函数的形式将path引入？

### 降低path sensitive的级别

Fuzzer对path的敏感程度，实际上与计算单个Coverage使用的地址数量有关，例如一个函数执行路径是1-2-3-4-5-6-7：

- 使用1个地址计算出来的，是Basic Block coverage（1, 2, 3, 4, ……）
- 使用连续2个地址计算出来的，是Edge coverage（1-2, 2-3, 3-4, ……）
- 使用当前函数中所有连续访问的地址计算出来的，是Intra-procedural Path coverage (1-2-3-4-5-6-7)
- 使用整个程序中所有连续访问的地址计算出来的，是Inter-procedural Path coverage (xxx-1-2-3-4-5-6-7-xxx-……)

是否可以考虑使用不太大的n个地址去计算，而不是使用所有地址计算（类似1-2-3, 2-3-4, 3-4-5这样）？这样可以降低整个coverage的空间，还可以兼顾path sensitive

## Update 2023.03.10:
需要确认一些东西：
1. 是不是收敛了
再做一遍实验
3. 是不是mutation不好
有多少新seed可以pass check，检查一下
3. 是不是真的没bug
写一个洞？toy example?

选择性插桩，留的稍微多一些，看一下crate的依赖

sub-path可以试一试，要确认一下n怎么选
写一个版本，看看跑出来的path和之前是不是一样的，还有看看n会不会炸

拿SBFT workshop benchmark来跑

提高循环限制的数字，实验一下

使用move测试，保留move_bytecode_verifier move_binary_format move_borrow_graph move_core_types这四个namespace的选择性插桩，另外发现load_code build_common_tables函数炸了，手动去除

fuzzing harness使用最简单版本，无semantic/structure aware，无corpus

| uptime | original cov | original exec/s | with-path cov | with-path exec/s |
| ------ | ------------ | --------------- | ------------- | ---------------- |
| 0 | 0 | ~20000 | 0 | ~11000 |
| 1h | 2064 | ~13000 | 1909 | ~9000 |
| 6h | 2086 | ~9000 | 1920 | ~8400 |
| 12h | 2086 | ~8700 | 1930 | ~8000 |
| 24h | 2086 | ~8700 | 1931 | ~8000 |

看上去mutation确实不太行，带一个较小的corpus(10个real world seed)再跑一组

| uptime | original cov | original exec/s | with-path cov | with-path exec/s |
| ------ | ------------ | --------------- | ------------- | ---------------- |
| 0 | 10566 | ~900 | 10572 | ~500 |
| 1h | 12064 | 624 | 11788 | 282 |
| 2h | 12161 | 614 | 11859 | 281 |
| 4h | 12301 | 591 | 11963 | 272 |
| 12h | 12742 | 499 | 12225 | 254 |
| 24h | 12830 | 486 | 12315 | 256 |
| 48h | 12875 | 456 | 12412 | 255 |
| 72h | 12941 | 459 | 12446 | 267 |
| 96h | 12956 | 455 | 12459 | 269 |
| 120h | 13001 | 432 | 12467 | 262 |
| 168h | 13051 | 431 | 12478 | 271 |

**统计coverage overlap**

几乎一样，只有下面的函数有区别（前面是原版的cov，后面是path版的cov）：

SignatureToken::fmt::Debug  13  11
move_binary_format::deserializer::load_signature_token 15 14
move_binary_format::deserializer::read_u32_internal 5 4
move_binary_format::deserializer::load_ability_set 25 23
move_binary_format::deserializer::build_common_tables 30 28
move_binary_format::deserializer::load_codes 1 0
move_binary_format::deserializer::load_struct_def_inst_index 3 2
move_binary_format::deserializer::load_code 179 145
move_binary_format::constant::sig_to_ty 11 10
move_bytecode_verifier::SignatureChecker::verify_code_units 12 11
move_bytecode_verifier::locals_safety::execute_inner 31 30
move_bytecode_verifier::InstructionConsistency::check_instructions 72 71
move_bytecode_verifier::InstructionConsistency::verify_module_impl 9 8
move_bytecode_verifier::type_safety::verify_instr  287 261
move_bytecode_verifier::reference_safety::execute_inner 195 191
move_bytecode_verifier::reference_safety::call 20 19
move_bytecode_verifier::reference_safety::AbstractState::call 22 21
move_bytecode_verifier::reference_safety::AbstractState::move_loc 10 9
move_bytecode_verifier::reference_safety::AbstractState::ret 19 18
move_bytecode_verifier::control_flow::verify_fallthrough 5 4
move_bytecode_verifier::CodeUnitVerifier::verify_function 14 13
move_bytecode_verifier::StackUsageVerifier::verify_block 25 26
move_core_types::MoveTypeLayout::DeserializeSeed::deserialize::Deserializer 12 11 
move_core_types::AccountAddress::Deserialize::deserialize::Deserializer 6 4

换mixed harness，无corpus，发现BoundsChecker::check_code SignatureChecker::verify_code 又炸了，因为有大量inline，暂时去除插桩

| uptime | original cov | original exec/s | with-path cov | with-path exec/s | subpath cov | subpath exec |
| ------ | ------------ | --------------- | ------------- | ---------------- | --- | --- |
| 0 | 0 | ~400 | 0 | ~50 | | |
| 1h | 5996 | 351 | 4490 | 34 | | |
| 6h | 7139 | 351 | 5793 | 35 | | |
| 12h | 7541 | 352 | 5930 | 36 | | |
| 24h | 7757 | 347 | 6099 | 36 | | |
| 48h | 7855 | 336 | 6268 | 35 | 7223 | 105 |
| 72h | 7906 | 337 | 6505 | 35 | | |
| 96h | 7962 | 330 | 6532 | 35 | | |
| 120h | 8323 | 312 | 6535 | 34 | | |
| 168h | 8352 | 296 | 6586 | 33 | | |

看上去block coverage跟总执行次数有很大的关系，运行速度的影响很大

发现一个小问题：目前这一版实现是intra-procedural path coverage，当fuzzing发现新函数的时候，如果这个函数比较大，那么会在这个函数产生非常多的path，然后fuzzer的power schedule机制就会优先给这些种子分配能量，最后导致fuzzer卡死在这一个函数里，直到差不多探索完了或者又发现新函数了才会多给一些power给其他种子

update：sub path的版本写完了，先取n=5，修改了一些实现，提升了性能

**RQ：目前的种子能过move bytecode verifier的几个check？**

对目前覆盖率最高的几个corpus做coverage可视化
正常checker一共有12个

BoundsChecker::verify_module
LimitsVerifier::verify_module
DuplicationChecker::verify_module
SignatureChecker::verify_module
InstructionConsistency::verify_module
constants::verify_module
friends::verify_module
ability_field_requirements::verify_module
RecursiveStructDefChecker::verify_module
InstantiationLoopChecker::verify_module
CodeUnitVerifier::verify_module
script_signature::verify_module

script_signature 代码量比较少，而且很大一部分不在verify_module的逻辑里，不考虑

mixed 的corpus 12个checker都执行到了，模块覆盖率:

BoundsChecker 65%
LimitsVerifier 47%
DuplicationChecker 69%
SignatureChecker 55%
InstructionConsistency 33%
constants 53%
friends 63%
ability_field_requirements 81%
RecursiveStructDefChecker 53%
InstantiationLoopChecker 26%
CodeUnitVerifier 72%

simple 带初始seed的corpus 12个checker都执行到了

BoundsChecker 92%
LimitsVerifier 49%
DuplicationChecker 92%
SignatureChecker 90%
InstructionConsistency 82%
constants 69%
friends 100%
ability_field_requirements 92%
RecursiveStructDefChecker 89%
InstantiationLoopChecker 93%
CodeUnitVerifier 74%

simple 不带初始seed的corpus，几乎过不了check

BoundsChecker 92%
LimitsVerifier 0%

**Bug Finding test**

加了 https://github.com/move-language/move/pull/751/files 这个bug进去

这个位置在normalized里面，需要把module转换成normalized::Module才能触发，这个函数要求module被verify过

从0开始fuzz的话，serialize几乎都过不了，所以就进不来这个函数，开了一个试试
选了1个seed作为initial seed，分别用原版和sub path版fuzz
都可以触发，而且都在20分钟以内，时间比较短，没什么参考意义

在check_bound里写了个bug，要求经过3个指定的分支，从0开始fuzz，几个fuzzer加起来跑了近30亿次都没有触发到
带corpus进行fuzz，几乎瞬间触发

增加一下这个bug的难度，要求按顺序经过3个指定的分支，跑了3次，subpath版crash需要执行次数分别是73000 99800 84640，原版是200000 156600 140050，似乎确实subpath能够带来一定的提升，但是bug触发难度还是太低了，再加一点

提升了bug难度，需要按顺序经过6个指定的分支，并且降低了corpus强度，用1个helloworld程序，而不是real world的程序

subpath版crash所需运行次数 325990816 69855658 214688715 732853333
原版crash所需运行次数 651451746 90636904 743163187

希望能看一下motivating example，看看什么样的洞传统fuzzing不行但是path sensitive容易找到

最近有一篇讨论是否需要使用细粒度coverage进行fuzzing的文章https://dl.acm.org/doi/pdf/10.1145/3587158
作者不推荐使用这种细粒度的cov指导fuzzing，大概有以下几个结论：
> ### 细粒度coverage对程序的影响
> - 细粒度的cov确实能够细分程序的执行状态，使得能够引导到这些状态的更多的种子被保留下来，理论上增加了发现新程序状态和bug的可能性
> - 细粒度的cov会增加程序本身执行的开销，加上能够保留更多的种子，也会增加fuzzer种子调度等流程的开销，导致fuzz吞吐量明显降低
> - 这两者产生一种对抗的关系，对最终fuzzing的表现是难以预计的
> ### 细粒度coverage的实验数据
> - 在benchmark上，大部分情况下，这些更细粒度的cov都没有带来fuzzing表现（branch cov，bug数量）的提升，甚至还有下降
> - 少数几个case bug数量获得了提升，这几个case的特点是程序足够小，或程序大但bug密度足够大
> - 作者认为，对于bug密度大的情况，细粒度cov可以帮助fuzzer保留更多走向不同bug的种子，但在程序较大且bug很少的情况下，引入细粒度cov增加了整体的搜索空间，加上fuzz吞吐量的下降，使得bug finding难度变得更大
> - 如果精细地选择在程序的哪些部分引入细粒度cov，那么是可以有一定的提升的，但作者是人工选取，只在4个程序中选就花了20多个小时，而且最后表现还是不如原版AFL++

## Update 2023.3.27

在SBFT上做一下长时间，bug多的实验
看一下long term上的情况

尝试一下优化性能，探索一下新的可能

## Update 2023.4.13

SBFT Bug Benchmark跑了100多个小时，使用Subpath长度=5的版本测试

数据在 https://leoq7.github.io/fuzzing-results/test_100h/

### Coverage

Coverage在时间足够长之后区别不是很大，在libxml和libpcap两个程序上subpath版本明显优于原版，需要进一步分析一下

分析了libxml和libpcap，起10组fuzzer取平均，发现libxml在取了平均之后subpath版的coverage和原版差不多，还稍微差一点

libpcap的话，会比原版好6%-7%，进一步分析原因，发现是在subpath版上，libpcap的运行速度比原版快，每秒执行次数差不多是1.8倍左右

因为libpcap的单组case执行路径相对比较短，而subpath版的路径收集算法是O(N)的，在N小的情况下，复杂度比原版的常数低

### Bug Finding

Bug finding上，subpath版明显落后，主要在assimp这一个case上(31 : 14)，去掉之后总数差不多，两个fuzzer找出来的都不多

subpath版本找出来3个unique bug，分析一下是什么原因

lcms上找到了一个整数溢出，一个除零异常

整数溢出

lcms2_internal.h:151:91: runtime error: signed integer overflow: 2147450881 + 32767 cannot be represented in type 'int'

是一个纯数据流上的bug，跟控制流的状态区分关系不大，当那个位置的数据大于(0xFFFFFFFF-0x7FFF)的时候会溢出

除零异常是UBSan的FP，分析代码发现进触发crash的分支的时候除数不可能等于零，去掉ubsan也复现不了

harfbuzz上多找出来一个bug，分析发现是此前发现的另一个SEGV bug在不同的地方触发了ASAN，而被fuzzbench算作了一个新的bug
rdi在541c2f前如果发现shadow memory在redzone里，就会触发ASAN，否则会到下一句，此时rdi是个非法地址就出现了另一种crash（SEGV）

## Update 2023.4.20

fuzzing 跨链的smart contract? bridges?
- oracle: invariant
找几个application
fuzzing distributed systems
不需要知道message长什么样？

针对MEV miner extractable value的fuzzing, sequence fuzzing?

fuzzing vm?
- crash bug，correctness bug？
- oracle：SMT data type
eg. true + 1 会违反type safety，可以用SMT model

smart contract本身的fuzzing

zkevm

VM, consensus, API

VM fuzz
成功：ton
失败：solana，aptos，zkevm
尝试的 path sensitve
code coverage
复杂性太高，需要domain knowledge
需要调整fundamental的东西
有没有fuzz出不来的bug？如果有的话，不行的原因是什么？
API fuzz
成功：jump crypto
可以看看：ton的API
把工具port过来，用一些手工的工作，最好看看能不能自动化
consensus/protocol
失败：rippled
有一些research，但很少，可以拿过来跑一跑，改一改

找个时间讲一下这些现在的工作

## Update: 2023.5.22

### RPC Interface Fuzzing
现在相关的工作比较少，SBFT上有一篇talk：Grammar-based Evolutionary Fuzzing for JSON RPC APIs
https://www.twitch.tv/videos/1819279026?t=6h11m4s
使用的例子是rippled (XRP ledger)
提到现在的相关工作例如EvoMaster, RestCT等，基本上都是用黑盒的方法去测试
不用白盒的原因：这种复杂的系统，在插桩环境下进行运行，速度会减慢很多，可能会导致时序的变化，然后会导致结果和正常情况下不一致
- 使用Snapshot Fuzzing（nyx）在zend（https://github.com/HorizenOfficial/zen/tree/v4.0.0-rc3 ） 进行了适配，让zend在nyx里面运行起来了，并且改造了zend的输入接收部分，从stdin接收输入，然后做了snapshot的延迟加载，可以达到约2000请求/s的执行速度

**Update**

- 第一版没有初始seed空跑，跑了大概两三天，map density 0.6%，非常差，看了看corpus，几乎生成不了合法的json输入
- 自己制作了一些seed corpus，大概三四十个，基本上都是单个请求，跑了7天，map density 4.07%，还是不太够，看了看corpus，发现能够提升覆盖率的很多都是在`decoderawtransaction` `sendrawtransaction`之类的请求中变异了raw transaction这个field，导致的覆盖率提升
- 看上去输入问题是个比较大的问题，目前的方案基本上都依赖于定义好的API specification，但对于blockchain ledger来说，基本上不会提供这个东西，且每一种chain的API定义都区别很大，如果人工编写的话，可能需要针对每一个独立的目标去编写，不知是否有意义
- 2000req/s的速度够不够，greybox相对blackbox能够多获取的信息（来自instrumentation）能够在哪些方面提供比blackbox更高的效率
- 有一个比较奇怪的想法：能否用fuzz来做API specification生成，然后再用生成的specification来指导fuzz，反复这个过程得到高质量的specification和seed corpus

可能需要一个东西去measure seed在程序中是否走得更远
stack depth ， map density

hybrid fuzzing ? + snapshot ？ 可以试一试symcc

cmplog

state ? 用type
说不定可以用LLM？每个seed是一个word，目标是生成一个sentence

distributed， coverage？ client - server的coverage接起来
interleaving

savior

语法：输入的合法内容，数字？字符串？
语义：数字与数字之间的关联？
1. 多
2. 有一些相对成熟的技术
3.

另外还提到现在的黑盒测试基本都用状态码来做fitness function，这是不准确的，这也是它主要解决的问题
它的解决方案是用UPGMA（非加权组平均法）来做层次聚类，聚类的依据是返回数据包的曼哈顿距离，将返回数据包抽象成向量，例如<accepted, ledger_index, status, validated>这种，然后在层次聚类的结果中划一条线，这个线以下的每一个类都完全分开，那么这每一类中的返回数据都是差距很大的，就只需要在每个类中保留若干测试数据，反复这样操作，就可以让测试数据的variety尽可能大

rational fuzzing

RPC 换了一个场景
RPC fuzzing和传统API fuzzing有什么区别

实验效果：测36小时，随机生成的测试样例达到7500cov，它的方法达到7750cov

它提到的几个工作
EvoMaster https://github.com/EMResearch/EvoMaster
比较全功能的工业界Web API测试工具，用AI和静态程序分析
可以进行黑盒测试，然后对于跑在JVM的程序也可以进行白盒测试
需要一个API的Swagger Schema (https://swagger.io/， 就是OpenAPI specification)，对于Java的程序可以自动生成

RestCT https://github.com/GIST-NJU/RestCT
ICSE 22, 也是根据Swagger Schema自动生成测试用例，根据schema中的资源依赖去生成测试请求序列，用NLP的方法去infer field之间的约束

Restler https://github.com/microsoft/restler-fuzzer
微软的REST API 黑盒fuzzing方案，从2019年一直更新到现在，根据OpenAPI specification生成测试样例，当时的创新点是可以推断producer-consumer dependencies，以及可以动态feedback，从此前的测试返回值中学习

parse document信息，转换成Rust代码，然后变成一个自动生成种子的东西
先不管semantic，也不管取值的合法性，先把每一个功能至少生成一个种子

wuyuhang usenix paper

evalutate patch正确性
种子选择没有改，energy也没有改
patch 分析，修改的代码和哪些相关，都是感兴趣的点
可能可达，但是context不对
用了grebe的技术，用data structure导向，把分配这些数据结构的点也作为fuzz的点
没有考虑先后触发

再加个队列