【基础知识】
本文主要对自动生成单元测试工具的基础知识进行介绍学习，主要从三大技术模块方向进行介绍。
首先假设现在要求我们自动生成单元测试用例，我们该从哪些方面入手？要求的关键词在于“自动”“单元测试”。先不管自动，我们怎么手动写一个单元测试用例呢？我们得给出输入，或者说得给出代码调用我们测试的函数块。但是我们也知道函数之间是相联的，不是彼此独立的，所以单独测试一个函数块必然会涉及到外部函数或者外部变量的调用，那么这时候我们就要通过插桩替换掉本来的外部调用，这也就是我们的第一部分内容——桩函数。
接下来再考虑，我们插桩结束，我们也可以手动给出测试用例了。但是手动写几个测试用例小问题，如果涉及到大型项目，我们怎么保证我们给出的测试用例就能保证项目安全性呢？这就涉及到了覆盖率问题。虽然覆盖率高不代表一定安全，但是覆盖率低必然不安全。这也就是我们的第二部分内容——使用探针统计覆盖率。
那最后就是我们的技术关键部分了，如何自动生成 单元测试用例呢？这就涉及到另一个概念：符号执行。通过符号执行进行条件求解，给出具体的测试用例，以实现自动生成测试用例。比如自动测试用例生成工具KLEE，即采用符号执行状态，当到达接收态或运行超时时再通过条件求解器给出具体的测试用例。
接下来我们将从以上三个方面详细介绍基础知识，对于具体实现的技术细节不做深入。
【打桩】
桩函数，即stub函数、存根函数，用一个桩函数替换一些接口函数，用于测试当前函数的特性。
一般情况下使用桩函数可以用来1、排除故障，用于排除bug 2、彻底替换，用于开发过程中的模拟 3、特定目的。那在我们这里就是使用桩函数来替代原来的外部调用函数，达到单元测试的目的。
但是对于单元测试，需要打桩的也不仅仅是外部调用函数。还可能涉及到外部变量，传入参数等。外部变量和传入参数我们都可以通过打桩模拟，外部调用函数也可以根据返回值模拟，比较棘手的问题就是调用外部函数的时候把变量地址作为参数传出去，这就可能涉及到变量值的变化。在模拟这种情况的桩函数时候需要注意。
桩函数的实现可以通过1、宏定义 2、修改函数内存地址，通过jump指令跳转到stub函数进行。
【探针覆盖率】
代码覆盖率是一种度量，它描述了对程序源代码的测试程度。这是白盒测试的一种手段，它可以发现测试用例无法覆盖到的程序。测试人员可以创建代码覆盖缺失的测试用例，以增加覆盖率并确定代码覆盖率的定量度量。在大多数情况下，代码覆盖系统会收集有关正在运行程序的信息。它还将其与源代码信息相结合，以生成有关测试套件的代码覆盖率的报告。
那么在”自动生成单元测试用例“中，我们采用覆盖率作为标准衡量生成的测试用例的质量。通过查看CFG覆盖分析检查是否每一种状态分支都可以到达，以此确保测试的安全性、完整性。
这里介绍一种高要求的覆盖率标准MC/DC（modified condition/decision coverage），即修正判定条件覆盖。修正条件判定覆盖要求在一个程序中每一种输入输出至少得出现一次，在程序中的每一个条件必须产生所有可能的输出结果至少一次，并且每一个判定中的每一个条件必须能够独立影响一个判定的输出，即在其他条件不变的前提下仅改变这个条件的值，而使判定结果改变。可以理解为MC/DC在要求实现条件覆盖、判定覆盖的基础上，对于每一个条件C，要求存在符合以下条件的两次计算：
1）条件C所在判定内的所有条件，除条件C外，其他条件的取值完全相同；
2）条件C的取值相反；
3）判定的计算结果相反。
介绍完覆盖率的基础知识后，就是我们怎么检测覆盖率的问题了。最基本的方法就是注入（Instrumentation）。简单地说，注入就是在被测代码中自动插入用于覆盖率统计的探针（Probe）代码，并保证插入的探针代码不会给原代码带来任何影响。
参考学习了《Approach to C+ + Code Instrumentation for Coverage Analysis with Clang/LLVM》论文，该论文提出的方法就是针对语句覆盖、分支覆盖和MC/DC覆盖通过重载函数MyASTVisitor: : VisitStmt(Stmt s)进行统计代码插桩。如1、语句覆盖：根据单行语句和复合语句分情况注入 STMT_ INSTRU (index)，其中index用于统计计数。2、分支覆盖：以if语句为例，当程序运行到分支覆盖插装点时，若 condition 值为 true ，则 index_true 对应的计数值增加，否则 index_false 对应 的计数值增加。3、MC/DC覆盖：当遇到IfStmt时，插装IF_CONDITION_MCDC_INSTRU(index,mcdc_condition) 用来检测是否满足 MC/DC 组合测试条件 mcdc_condition 。当程序运行到 MC/配覆盖插装点时，若 mcdc_condition 值为true ，则 index对应的计数值增加，即指定的测试用例条件为真。如下图所示：
【测试用例】
接下来我们介绍如何自动生成测试用例。
自动生成测试用例的关键点在于符号执行。
【静态符号执行】
参考学习了《Symbolic execution for software testing: three decades later》一文。
符号执行是把输入变为符号值，使得程序计算的输出值就是一个符号输入值的函数。在程序执行过程中会根据条件分支生成执行树，执行树包含符号化执行路径，路径确定了函数的约束条件。最终我们执行结束时会根据约束条件对函数进行求解，得到确定的值。这个确定的值就是我们的测试输入了。如下图所示：
在上图中我们就可以很好的看到左边的代码符号执行生成的执行树是怎样的。根据每一个分支添加条件判定，最终到达终态的时候利用约束求解器给出满足条件的一组解，该组解即为我们的测试输入。如在判断2*y==x这一步假设进入true，在x>y+10这一步也为true，那我们得到的条件组就是：(x=2y)∧(x>y+10)，在遇到ERROR语句时求解得(x=2y)∧(y>10)即可。
静态符号执行也存在一些问题。1、如果循环或递归的终止条件是符号化的，包含循环和递归的符号执行会导致无限数量的路径。我们在面对实际情况时候，可以通过限制运行时间、限制搜索深度等等方式来终止循环、递归。2、当符号路径约束包含不能由求解器高效求解的公式时，我们就无法求解，也就无法产生输入。所以之后提出了动态符号执行，也叫做混合执行(concolic execution)，将具体执行和符号执行结合起来。
【动态符号执行】
混合执行维护一个实际状态和一个符号化状态：实际状态将所有变量映射到实际值，符号状态只映射那些有非实际值的变量。Concolic执行首先用一些给定的或者随机的输入来执行程序，收集执行过程中条件语句对输入的符号化约束，然后使用约束求解器去推理输入的变化，从而将下一次程序的执行导向另一条执行路径。简单地说来，就是在已有实际输入得到的路径上，对分支路径条件进行取反，就可以让执行走向另外一条路径。这个过程会不断地重复，加上系统化或启发式的路径选择算法，直到所有的路径都被探索，或者用户定义的覆盖目标达到，或者时间开销超过预计。
Conclic执行会预先产生一些随机输入，然后在遇到不同的条件分支时候符号执行会在不同路径上生成路径约束，然后进行路径探索。如KLEE即采用了混合执行的方法。KLEE创新提出了执行生成的测试（Execution-Generated Testing），简称EGT，即在每次计算前都会判断该输入是否是实际输入。如果是实际输入则直接执行，反之会通过更新当前路径的条件符号化地进行。
通过混合执行可以解决无法求解约束的情况，当无法求解时我们随机输入实际值即可。但采用实际输入也意味着我们生成的测试用例可能无法覆盖全部路径。
对于混合执行的几个关键技术点介绍：
1、路径选择：代码量增大，条件分支可能会出现指数爆炸。那么面对分支，如何高效进行路径选择是我们需要考虑的问题。主要方法如下：1）启发式搜索，确定最值得探索的路径 2）利用程序分析和软件验证减少路径探索的复杂性。比如采用静态融合将路径选择的复杂性转移到求解器中；或重用，减少计算的复杂性；或剪除冗余路径。
2、约束求解：约束求解可以从以下两个方面进行优化。1）不相关约束消除，当程序分支通常只依赖一小部分程序变量，可以尝试从当前路径条件中移除与识别当前分支结果不相关的约束。2）增量求解，即KLEE采用的方法，重用以前相似请求的结果，提升约束求解的速度。
【总结】
综上所述，我们对自动生成单元测试用例的相关基础知识有了基本理解。即我们通过插桩实现”单元测试“，通过符号执行实现"自动生成"，最后再通过探针检查覆盖率，确保测试用例生成的完整性。对于具体技术实现，还需要更底层的探索学习。