计算机、软件和应用程序会议（COMPSAC）

INTRODUCTION

        深度代码片段是需要复杂的触发条件或隐藏在不太频繁调用的函数中的代码段，确定这些代码的可达性仍然是一项重大的挑战，符号执行和模糊测试都有局限性。所以本文提出一种近似模糊技术，给定目标代码片段，模糊器收集执行路径(w.r.t.)，测试输入，计算路径和目标之间的执行距离，将可达性问题转为优化问题，然后变异种子以探索输入空间，并将模糊过程引导到生成到达目标代码片段的测试输入。

PROBLEM FORMULATION

        定义执行距离为输入到达或接近深代码片段的有效性，P为被测程序。tcs为P中目标代码片段，可以是程序语句或程序语句中的块。

        定义执行路径tr(t)为执行到的代码片段的序列，则路径和目标之间的距离DIS被定义为：

行距离：定义目标代码片段从lb到le，而路径tr(t)包含[s0, s1, ……, sn],那么在x行的si到tcs的行距离为：

         所以行距离被定义为在路径上的任意语句si和tr(t)的最短距离。

CG（调用图）距离：TM为包含tcs的方法，则CG距离为调用链上的任意方法到TM的距离：

         其中shortest(...)计算在CG(P)上Mi到TM的最短路径，使用迪杰斯特拉或弗洛伊德算法。

CFG（控制流图）距离：建立一个TM的控制流图，Bi为基本块，block(t, TM):{B0, B1,...,Bn}为被一次运行t覆盖的基本块，TB为包含tcs的基本块，CFG距离为：

        CFG距离计算从block(t,TM) 到TB的最短距离。

APPROACH

流程：1.变异输入 2.执行和收集执行路径 3.选择性接受变异输入。

1. 种子池中元素按照执行距离排序，距离短的种子应该被更频繁地选中，概率公式为：

2. 记录执行路径和测试输入，基本策略是计算行距离。另一种策略是计算CG和CFG距离。

3. 微调策略：计算条件距离以加快变异过程。

        条件语句可以表示为：if(lv op rv) cs1 else cs2.假设cs1在测试中被覆盖了，但cs2离目标更近，微调策略会检查if语句中的值并验证一个变异是否让它更接近cs2.

         一次执行路径中会有两个或多个条件语句，所以我们需要计算归一化的条件距离：

 4. 实现：使用Jacoco进行代码插桩，使用soot构建调用图和控制流图，将字节码转换成Jimple代码从而高效收集条件下的可变值，通过AFL来随机变异输入文件。