Fuzzing Book
Coverage Assignment
写在前面：文档中标注此次作业会查重，有需要的同学记得稍微修改一部分，别完全照搬了
还没有在本地配置好Fuzzing Book的同学可以参考：
Fuzzing Book安装指南
《Fuzzing Book》的"Code Coverage"章节介绍了用于测量Python程序覆盖率的Coverage类。在模糊测试的上下文中，覆盖率信息用于引导测试向未覆盖的代码位置。该章节主要介绍了Coverage类基础用法：
- 基本语法：使用with Coverage() as cov:上下文管理器来捕获代码执行
- 可视化输出：打印覆盖率对象会显示已覆盖和未覆盖的代码行（未覆盖行用#标记）
作业任务：改写Coverage类，增加event的种类为：line，call，return。
通过调用fuzzer()，随机生成长度在100个字符以内的字符串，连续跑10次，分别输入到cgi_decode()，观察程序的执行情况，打印出执行trace和覆盖率。
我们对任务进行分解：
首先我们分析一下原Coverage类：
- __init__函数：
首先定义了一个初始化函数，该部分会初始化一个空列表_trace，用于存储按执行顺序记录的每一行代码（因为原Coverage定义了event是"line"）的位置。
- 接下来我们先看这部分（与with配合使用）：
我们在这里先介绍一下with的使用方法。
with需要配套实现__enter__()和__exit__()两个方法，这里定义通过OBJECT进行管理，然后将__enter__()的返回值给VARIABLE，之后执行BODY
那原Coverage这部分代码中:
首先__enter__()保存了原有的追踪函数（保存为original_trace_function），接下来将追踪函数设为我们自己实现的traceit()，然后返回自身给cov（相当于Coverage类的一个示例，可以用来访问和调用函数变量）
然后__exit__()恢复原有的追踪函数，返回None(表示让所有异常通过，即异常会向外抛出)
- traceit函数
该函数是追踪函数，如果original_trace_function不是None，即先调用原有的追踪函数（如果存在的话），这时候会将frame（帧，上下文）、event（事件类型），arg（参数）传给原有的追踪函数；如果不存在就执行下面的内容：判断事件是否是"line"（原Coverage只定义了追踪换行事件），如果是的话，获取当前行的函数名、行号（如果是__exit__函数就跳过，避免追踪自己的退出函数，否则结果会含有大量的__exit__行号），将函数名和行号加入_trace列表。
- 结果获取方法（trace、coverage、function_names）
- 该部分是对外返回结果的函数。trace会直接返回_trace（原始结果）；coverage会对原始结构进行去重操作(set是集合)；function_names会返回所有执行过的函数名（也会去重，有set操作）
- __repr__函数
这部分是可视化输出，遍历所有执行过的函数名，通过eval将函数名对应到具体的函数位置；如果出现异常会进入except块，把异常赋值给exc，然后记录跳过原因（跳过某个函数，因为什么原因），然后继续执行下一个函数。
之后通过inspect.getsourcelines(fun) 获取函数的源代码行数和起始行号，分别赋值给source_lines，start_line_num，对于源代码的所有行进行遍历，如果这个行没有出现在我们的_trace中，就将开头标记上#，执行过的行就在前面加上空格（与上面对齐），然后加上对应的行号（格式化对齐，至少两个字符宽度），接下来把这行的内容加到后面。
- fuzzer函数
这个函数是最fuzzing book介绍的最基础的函数：
这个函数是用来生成一组随机字符串，定义了最大字符串长度是100，起始char（ASCII码）值是32，char可选长度是32，即可以选择32-63的字符。接下来用随机数随机初始化字符串长度（0到100），然后构建字符串：每一位字符通过随机生成32-63的值，然后通过chr函数得到一个字符，将字符作为字符串out的当前位。最终输出out
- cgi_decode函数
这个函数是用来对字符串进行处理，遇到“+”会转为空格，如果是%，后续会读取两个字符，通过预先定义的hex_values，将其作为十六进制数转为十进制数，然后再转成ASCII码对应的字符（如果出现不符合的值就弹出错误）。如果是普通的字符就直接拷贝，最终返回处理完的字符串。
- 作业实现
首先对返回结果我们定义一个四元组，分别是函数名字，行号，触发的事件类型，和如果是return类型额外添加了其返回值（补充实现）
之后分别将cgi_decode和fuzzer函数拷贝过来直接复用即可。
之后便是修改Coverage类：
通过前面对于这个类各个功能的实现，我们很容易发现需要修改的地方：
- traceit中对于event的操作：
前面原实现只进行了行的追踪，所以判断只需要判断event是否是line即可，而我们需要扩展为line、call、return，故需要对其进行修改：
使用in来判断event是否是其中之一。
我们前面提到return不同于其他两个，它应该多一个元素（即返回值）需要记录，所以我们还需要单独对其进行处理：
注意这里的哈希是为什么，因为原返回值可能是数字，字符串等可哈希的结果（为什么需要可哈希，因为coverage方法采用了集合，集合中的元素要求是可哈希的对象），直接返回就可以看见真实返回值；如果不可哈希就通过repr将返回值变成字符串类型（与str()相似）
然后返回四个元素（注意line和call第四个元素是None）
- __repr__函数的实现：
主要修改这一部分（跟输出挂钩）
我们使用了一个嵌套生成器表达式+any函数，作用：
检查追踪的事件集合中是否存在函数名为当前函数名、行号是当前行号、事件类型符合我们的要求的结果，只要有一个满足条件（any）就返回True（表示这一行被覆盖）——即判断当前函数的当前行有没有被line、call、return任意一个事件触发。
虽然这样修改后直接执行以及能得到大概符合要求的结果了，但是依旧存在一个问题：
为什么会出现这个问题？
因为原__repr__函数在获取当前函数名的时候使用了eval来获取该函数的具体位置
而我们出现的错误是这些都是系统内部函数，无法通过eval()获取。需要修复__repr__方法：
我们还是先尝试使用eval调用，如果不能获取（捕获两种异常：找不到函数名或解析失败），那就尝试从全局主命名空间寻找函数对象：
导入__main__（python当前运行的主模块命名空间，存放所有在主脚本定义的函数/变量），使用hasattr，检查当前主命名空间是否存在当前名为function_name的对象，如果存在就使用getattr来获取这个对象，并且赋值给fun（跟前面正常情况对应）
如果__main__也不能获取到该函数名（hasattr返回false），就降级打印，只显示函数名和行号（并且去重并且按行号排序）
尽管后续运行基本上二次搜索也会失败，但可视性会比之前好很多
这部分尝试获取源代码，如果出现异常（源代码文件不存在或为内置函数）则降级（跟前面类似），只显示函数名+覆盖的行号
如果能获取源代码，这部分是我们修复前的部分，就不重复讲了。
接下来是测试代码：
首先定义了一个全局变量all_coverage记录覆盖情况（去重）
接下来使用range(1,11)实现遍历十次（含前不含后，且默认步长是1）
调用fuzzer生成一个随机字符串作为测试的输入，然后讲这个字符串先进行一个打印
然后进入with部分：使用Coverage类进行跟踪，为了增强代码的健壮性与测试的可视性，我们增加了对执行结果的判断：
执行目标cgi_decode，进行解码，如果成功就把值返回给result并且打印成功信息，如果出现异常：ValueError(这部分是原本cgi_decode实现了的，对于%后的两位数进行十六进制转十进制，如果是无效编码就会返回这个)、IndexError（越界情况，即%可能出现后面不足两个字符的情况）、Exception（其他异常），然后打印具体异常类型的情况。
代码如下：
接下来是输出部分
首先我们使用print(cov)这个会自动调用Coverage类里面的__repr__函数，即可以将具体的覆盖情况打印出来：
如图，结果与我们预期的__repr__中的结果一致，对于前面和后面出现的内置函数，无法获取源码，我们只打印函数名和覆盖的行号，对于可以获取源码（也是我们核心目标）的cgi_decode，我们可以按照预期讲整个函数的覆盖情况打印出来，标记未运行到的行号
然后打印我们追踪的三个事件，每个事件的不同情况：
由于覆盖的行号很多，全部显示不太合理，我们只显示前20条
接下来打印call事件的情况：
然后是return事件（注意我们前面在traceit中提到了return应该相比前两种方法加上对应的返回值）：
需要注意有些函数是没有返回值的，所以我们需要兼容原本考虑三个元素的情况，单独考虑返回值
每一轮执行完成，我们进行一个覆盖率总结：
按每个事件类型单独统计（使用set，会去重），通过前面定义的location元组的第2位即event类型来区分
然后分别打印每个事件覆盖的位置数，将具体的覆盖情况打印出来，最后将这一轮的情况存入前面定义的all_coverage中：
最后对十次结果进行一个统一的总结：
- 输出优化
我们刚才的实现以及符合要求了，但是在可视化方面仍然有缺陷，因为我们还是不能直观的了解程序是怎么执行的（执行顺序），所以可以对输出进行优化：
将结果按照执行的顺序依次打印，line，call，return混合，可以帮助我们更好的了解程序怎么执行，在哪里做了什么操作：
可以看看结果：
对于这样一串成功运行的字符串：
我们可以查看追踪结果
首先进行了call调用cgi_decode，然后在该程序中进行运行
然后在循环进行字符串格式转换后，在33行return，返回了操作完成的字符串；
接着call了write函数（调用cgi_decode后续我们进行了print操作，打印了执行结果）
这部分进行write内的调用操作，一直到：
这里返回了我们写了62位字符。
其实这里主要原因是因为我们在调用Coverage类的时候在里面使用了print语句，如果不希望出现这些函数可以将print删除。
不过针对这个作业，我们还是希望出现多用的call与return事件的，所以我进行了保留。
