# SyzVegas: Beating Kernel Fuzzing Odds with Reinforcement Learning
[SyzVegas: Beating Kernel Fuzzing Odds with Reinforcement Learning](https://www.usenix.org/system/files/sec21-wang-daimeng.pdf) 是一篇 2021 年发表在 USENIX 的研究型论文（工程创新）。一作是来自 University of California, Riverside 的 Daimeng Wang，其它作者同样来自 University of California, Riverside，他们是 Zheng Zhang, Hang Zhang Zhiyun Qian, Srikanth V. Krishnamurthy, Nael Abu-Ghazaleh。
该论文的贡献：基于 Syzkaller 借助 reinforcement learning，修改 Syzkaller 中两个最关键的决策点——task selection and seed selection，提出了新 kernel fuzzer——**SyzVegas**，对比 Syzkaller，在执行效率与覆盖率方面有了一定的提升。
### 背景
1. *Kernel fuzzing is uniquely **challenging** for the following reasons: (1) modern OS kernel often has a huge code base and many dependencies across components; (2) the input to an OS kernel is via the system call interface that needs special handling; and (3) an OS kernel maintains a massive state space that a single input (i.e., test case) may not be able reproducible.*
2. workflow overview of Syzkaller
### **问题**
1. Syzkaller 硬编码策略无法适应动态变换的模糊测试环境与任务，同时基于作者的 observations，Syzkaller 性能方面仍存在提升的空间；
2. 作者将问题 1 转化成如下问题：确定 **SyzVegas** 的目标在于提升 coverage 的前提下，（1）选择最有价值的模糊测试任务；（2）选择最有效的突变种子。
### **设计与实现**
对于上述**问题 2**，既然要求选出最有价值的任务和种子，则需要一个标准进行衡量。如何建构这个标准？
基于 observations，作者发现“正确”的任务和种子是随着时间的推移而动态变化的，因此需要一种自动化的方式来识别给定时间最有价值的任务，并且适当地调用与该任务相关的最佳种子。
> To identify these, a reinforcement-learning scheme is a natural fit, wherein a model to maximize the **coverage rewards** relative to the **time cost of execution** is applicable.
在众多的 reinforcement-learning 中，Multi-Armed Bandit (MAB) 是最适合的，因为 MAB 的设计目标是在面对不确定性的情况下，用局部最优去追求全局最优，最大化总体累积奖励。加上 Syzkaller 本质上是对未知空间进行搜索，reward 分布是未知的。因此在 reward 未知的前置条件下，选用 MAB 能在 exploration 与 exploitation 之间做到很好的平衡。
最终，作者决定在 **SyzVegas** 中通过 Adversarial MAB（especially, Exp3），去解决[**问题 2**](#wen-ti)。
**SyzVegas** 的实现效果与更多其它细节，读者可自行去原文查阅。
目前笔者对顶级研究者的研究思路总结如下：
phenomenon
→ observation & intuition
→ strategy(scenario taken into account) & implementation
→ evaluation & rethink
→ improverment?
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://blog.kaisuping.cn/paper-reading/cumulative-reasoning/syzvegas-beating-kernel-fuzzing-odds-with-reinforcement-learning.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.