Research

The English version of this page is here.

目前，我的研究兴趣集中于高效的软件测试方法和软件测试理论。对软件进行测试，是保障软件正确性的关键手段，甚至是现实世界中唯一的可行手段。当然，大神Dijkstra说过：软件测试只能说明bug的存在，并不能说明bug不存在。从这个层面来说，是的，形式化方法、静态分析方法会更加完备(Complete)鉴于软件正确性的重要性，我们打算今后也要往这个方向探索！然而，从工业界的角度，在所有保障软件正确性的方法当中，测试仍然是使用得最为广泛的。因为相比于形式化验证等方法，软件测试成本更低，且更加高效便捷，更加适配当今软件开发的节奏——假如一个APP要是很久都不更新，既不增加新的特性，也不修复已有的问题，你还想用吗？

很多人都会觉得“软件测试，不就是写写test case，有什么难的？”。然而，它只是看起来简单而已——上手容易并不意味着成为一个“高端玩家”就容易了。我们组目前想做的，就是成为这个领域的高端玩家当然了，受限于我的水平，可能只是白日梦一场……。

从我的角度出发，我觉得软件测试领域有几个核心问题：

覆盖(coverage)准则设计

覆盖准则关心的是，到底要测什么，测到什么程度？基础准则主要有基本语句块覆盖、路径覆盖、输入边界值覆盖等。但是，对于深度神经网络这种的基于数据训练出来的程序，这些基础准则就完全失效了。我们组目前对这方面的研究不足，可做的方向包括研究各种覆盖准则的偏序关系（一个准则是否完全包含了另外一个准则），有效性（某种准则是否能更好地刻画某个待测对象的故障分布）等。
测试用例采样(sampling)

测试用例采样关心如何生成满足某种准则的测试用例集。最为常见的就是随机算法，比方说模糊测试(Fuzzing)，其在编译器等安全攸关的软件上简直是神器。然而在某些具体问题上，随机算法会出现低效的问题，比如程序的某条路径难以达到（路径的约束可满足解占比全空间小）。换句话说，生成满足目标条件的测试用例集是个小概率事件时，随机方法就是难以满足要求。这时候设计更加高效的采样方法就是唯一可行的做法。我们组目前对采样算法有众多研究，包括自适应算法（动态调整采样策略）、基于高阶图的整体采样方法（还在进行中）、启发式方法（禁忌表确实有其独到的地方）等。

测试用例采样关心的另一个问题是，有没有符合要求的最小的测试样例集大小？如果有，大概多大？如果要从理论上给出一个答案，那么这个问题是非常困难的。比方说，对于我们研究的组合覆盖(Combinatorial Coverage)而言，给出最小的采样大小是一个NP-hard的问题。而当软件的参数之间存在约束情况下我相信，你见过的大部分程序都存在多个输入参数之间的约束，这个问题会变得更难。目前为止当前方向的研究还很少，目前也就只有一篇TCSTheoretical Computer Science，一个理论计算机科学的期刊的文章研究了该问题中一种非常简单的情况。
结果与分析

执行一条测试用例之后，我们就要对产生的结果进行分析。
- 判断结果对错
  
  为了知道程序的运行结果是否正确，我们首先要对结果做判断：简单的错误，如崩溃(Crash)、断言违背(Assertion Violation)是可以高度自动化的。但对于复杂的功能性错误，如果我们不能很好的判断，那么测试就毫无意义It is not even wrong! 你都不知道什么才算是对的！。软件测试领域把判断程序运行结果是否正确的方法抽象成一个实体——Oracle。所以，用行内的话术来表述这个困难就是：测试的Oracle很难获取。
  
  为了解决测试的Oracle问题，我们研究了蜕变测试(Metamorphic Testing)在纯组合测试中的应用。蜕变测试通过找出软件的蜕变关系，自动给出Oracle不过，蜕变测试仅仅描述了软件的部分性质，我们觉得它还不够好，那么有没有更好的呢？还真有，最近有一个很有趣的研究叫Intramorphic Testing。
- 分析结果
  
  当我们能判断结果的对错之后，就要对结果进行分析了。程序中的哪个元素或输入中的哪个片段是测试用例发现故障的罪魁祸首？这就是故障定位问题(Fault Localization)通俗地讲，就是debugging——程序运行出问题了，是因为代码哪里写错了呢？。目前为止，我们研究了如何刻画可疑的组合空间，出现多个罪魁祸首的处理方法，给出一个具有理论保障的插桩剪枝方法等等。我们考虑在未来的研究中，能否结合概率法(The Probabilistic Method)来优化故障定位过程，以及能否将组合测试故障定位的动态方法（自适应算法）和静态方法（组合设计）统一起来（利用组合数学中的Alteration Teachnique）。

在未来的研究，除了纯软件测试的工作，我们还打算做一些更有意思的工作，比如AI+CT(Combinatorial Testing，组合测试)这个时代，有谁不爱AI呢？，比如前面提到的用形式化以及静态分析的方法加强软件的可靠性，比如设计效果更好、有理论保障的采样算法，以及我们想试试看能不能把软件测试应用到实际的安全攸关的软件，尝试在软件安全领域进行一些探索。