Neuroevolution-Based Generation of Tests and Oracles for Games

Game-like programs have become increasingly popular in many software engineering domains such as mobile apps, web applications, or programming education. However, creating tests for programs that have the purpose of challenging human players is a daunting task for automatic test generators. Even if test generation succeeds in finding a relevant sequence of events to exercise a program, the randomized nature of games means that it may neither be possible to reproduce the exact program behavior underlying this sequence, nor to create test assertions checking if observed randomized game behavior is correct. To overcome these problems, we propose Neatest, a novel test generator based on the NeuroEvolution of Augmenting Topologies (NEAT) algorithm. Neatest systematically explores a program’s statements, and creates neural networks that operate the program in order to reliably reach each statement—that is, Neatest learns to play the game in a way to reliably reach different parts of the code. As the networks learn the actual game behavior, they can also serve as test oracles by evaluating how surprising the observed inputs of a program under test are compared to the inputs obtained on a supposedly correct version of the program. We evaluate this approach in the context of Scratch, an educational programming environment. Our empirical study on 25 non-trivial Scratch games demonstrates that our approach can successfully train neural networks that are not only far more resilient to random influences than traditional test suites consisting of static input sequences, but are also highly effective with an average mutation score of more than 70%.

类游戏程序在移动应用、Web应用及编程教育等诸多软件工程领域中愈发普及。然而，针对以挑战人类玩家为目标的程序生成测试用例，对自动化测试生成器而言是一项极具挑战性的任务。即便测试生成器成功找到了可覆盖程序执行的相关事件序列，游戏的随机性本质也意味着，既无法复现该序列对应的精确程序行为，也无法编写测试断言以验证观测到的随机游戏行为是否正确。为解决上述难题，我们提出了Neatest——一款基于增强拓扑神经进化（NeuroEvolution of Augmenting Topologies, NEAT）算法的新型测试生成器。Neatest会系统性地遍历程序的所有语句，并构建用于操控程序的神经网络，以可靠抵达每一条语句——换言之，Neatest会以可靠覆盖代码不同分支的方式学习游玩该游戏。随着神经网络掌握了游戏的实际运行逻辑，它们还可作为测试预言：通过对比被测程序的观测输入与预设正确版本程序所得到的输入，评估观测输入的异常程度。我们在编程教育环境Scratch中对该方法进行了评估。针对25款具有一定复杂度的Scratch游戏开展的实证研究表明，本方法训练得到的神经网络不仅比由静态输入序列构成的传统测试套件更能抵御随机干扰，且具备极高的有效性，平均变异得分超过70%。