PerfFuzz: Automatically Generating Pathological Inputs
1 介绍
已有的检测性能问题的研究大多数假设已有一定规模的输入。这些输入来源包括：
- 人工编写的性能测试
- benchmark
- 在使用过程中常用的输入
- 用户遇到的触发性能问题的输入
往往这些输入引发的问题已经发现或修复，不能发现新的性能问题。
Pathological inputs：造成最坏算法复杂度的输入
本文提出PERFFUZZ，基于反馈导向的变异fuzzing生成输入。实验结果表明在4个C语言项目中，PERFFUZZ找到最多执行的程序分支是基于覆盖率fuzzing（AFL）的2X~39X。
与SlowFuzz相比，最多执行程序分支的5X~69X，最长执行路径的1.9X~24.7X。
本文贡献：
- 提出PERFFUZZ，并开源
- 与传统基于覆盖率的fuzzing工具（AFL）进行比较
- 与相似的反馈导向的fuzzing工具（SlowFuzz）进行比较
- 人工分析PERFFUZZ发现的
hot spots，并描述insight
2 概览
2.1 一个例子
2.2 性能fuzzing
目标是最大化控制流图中每条边的执行次数生成测试用例。实验中需要一个或多个种子输入开始，这些种子输入用例验证程序的正确性。实验中往往只需要1个种子输入就够了，最多只需要4个。
PERFFUZZ的流程：
- 初始化输入，称为parent inputs，包括seed inputs
- 从parent inputs中选择一个最大化程序执行数的输入
- 从选择的输入中生成更多地输入，称为child inputs。变异策略包括：1) 翻转输入比特 2) 删除比特序列 或3)随机提取其他输入的一部分拼接到当前输入
- 所有child inputs中，若该孩子输入是程序执行了更多次，则把他加入到parent inputs
- 重复2-4直到时间限制
3 PERFFUZZ算法
流程如上2.2所述。
program components:
malloc语句分配字节数- cache misses或page faults数
- I/O操作数
- …
Definition 1：performance map是一个函数$\mathit{perfmap}: \mathcal{K}\rightarrow \mathcal{V}$，其中$\mathcal{K}$表示program components对应的相关的键值，$\mathcal{V}$表示根据性能值（执行次数？）排序的集合。
Definition 2：位于时间戳t的cumulative maximum map是函数$\mathit{cumulmax_t}: \mathcal{K}\rightarrow \mathcal{V}$。
大致意思就是求对于某个program components的执行次数最大值。
Definition 3: NEWMAX在输入i位于某个时间戳t满足以下条件时返回true。
大致就是这个时间点的输入i的执行次数大于之前所有执行次数的最大值。这个输入i让程序执行了更多次，更可能引发性能问题。
Definition 4: 输入i最大化组件k性能值当且仅当性能属性注册了目前观测到的最大值：
Definition 5: 输入i被favored当且仅当满足以下条件：
也就是输入i使某个组件$\mathcal{K}$的执行次数达到最大。
Definition 6: 选择概率：
$\alpha$默认为0.01。
最后为了评价PERFFUZZ的性能，提出了maximum path length和maximum hot spot作为度量。设$\mathcal{E}$为测试程序的控制流图上的边集，$\mathcal{I_t}$为fuzzing工具在时间$t$生成的输入集合，那么：
Definition 7. maximum path length是所有输入经过的最长执行路径：
Definition 8. maximum hot spot是控制流图的边中执行次数最多的边的执行数：
4 实现
上面说的差不多了
5 评价
选择的benchmarks：
- libpng
- libjpeg-tubo
- zlib
- libxml2
5.1 与SlowFuzz比较
5.2 与基于覆盖率的fuzzing进行比较
这里使用AFL作为baseline
5.3 Case Studies
6 效度威胁
PERFFUZZ依赖于启发式的方法产生输入来完成测试目的，这也是和其他算法模型的输入生成技术相似的。
这里使用CFG边的执行次数而非总体执行时间衡量计算复杂度。
这个方法解决了在非凸性能空间上陷入局部最大的问题。