Reading Note: “Reformulating Branch Coverage as a Many-Objective Optimization Problem”, ICST 2015

date
Mar 23, 2024
slug
mosa
status
Published
tags
SE-Paper Reading
summary
type
Post

问题描述

单元测试生成的目标：自动生成针对给定待测软件的高覆盖率，高可理解性的单元测试程序。
When instantiated for branch coverage, the problem can be formulated as finding a set of test cases that maximize the number of covered branches in the software under test (SUT).

研究现状

传统的方法是每次考虑一个覆盖目标，尝试产生覆盖这个目标的单元测试用例，最后把所有单元测试组合起来得到一个套件；近年来有研究者在其上做了改进，通过把多个单覆盖目标的适应度函数聚合在一起得到一个测试用例套件级别的适应度函数，取得了比传统的方法更好的效果。

本文方法

前置知识

在单目标优化中，我们希望得到的解是适应度函数值最小的解，这样的解可能有一个或者多个，但是他们的适应度函数值是相同的；在多目标优化中，我们希望找到的解由 Pareto dominance 和 Pareto Optimality 来定义。
在多目标优化中，对于搜索空间 X 中的一个候选解 x，我们有一个 m 维向量来表示其适应度，记为 ，我们希望同时最小化它的每一个维度的值；Pareto Dominance （记作 ）是 X 上的一个二元关系，；我们称一个解 x 是 Pareto Optimal 的，如果它不被搜索空间中的任何一个解支配。具备 Pareto Optimality 的候选解可能很多，在一些场景下我们可以考虑它们中的大部分来做一些权衡，但是在以覆盖率为目标的测试生成这个场景下，我们感兴趣的是那些覆盖了之前没覆盖的分支的测试用例，即适应度向量的 m 个维度中有 1 个或者多个值为 0 的解。

概述

和 whole suite 把多目标聚合为一个单目标不同，本文提出了一种把测试生成问题作为多目标优化来求解的方法。由于传统的用于数值的多目标优化算法不适用于目标数量特别大的情况（分支覆盖率目标的数量往往很多），本文提出了一个新的多目标优化算法 MOSA(Many Objective Sorting Algorithm)。
MOSA 首先从一个随机生成的初始的测试用例集合开始，在停止条件之前重复以下操作，来产生越来越好的测试用例：
  1. 首先选择出亲代通过 cross over 产生子代
  1. 应用 mutation 操作
  1. 对亲代和子代进行选择，这里的选择考虑了 Pareto Optimality 和进一步定义的 preference criteria，具体见 PREFERENCE-SORTING 和 CROWDING DISTANCE
  1. 更新 archive，具体见 UPDATE-ARCHIVE, archive 中包含最后的最优解。

实验

一些细节：
  1. 覆盖率作为有效性指标，搜索预算作为效率指标，搜索预算用执行的语句的个数来度量。
  1. 每个运行被重复 100 次。

总结

本文从一个不同的求解视角来尝试解决测试生成问题，并针对测试用例生成这个场景提出了一种 specialized 的多目标优化算法。但是我暂时并没有直觉上的理解为什么这个方法好于 whole suite 的方法？

© Lifan Sun 2023 - 2024