{'fraction_non_alphanumeric': 0.02296268932397488, 'fraction_numerical': 0.009929811599556705, 'mean_word_length': 5.081595974119338, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
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 cover 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 behavior of a program under test is compared to 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 65%.


INTRODUCTION
Game-like programs allow players to interact with them using specific input actions, and challenge them to solve dedicated tasks while enforcing a set of rules. Once a player successfully completes the task of a game, the game usually notifies the player of his/her victory, leading to an advanced program state (winning state). Nowadays, game-like programs can be found in many software engineering domains. For example, the most common category of mobile apps in Google's Playstore 1 as well as in Apple's App Store 2 are games by far, and games are equally common in web and desktop applications. Programming education is also heavily reliant on learners building game-like programs in order to engage them with the challenges of programming. Fig. 1a shows the FruitCatching game, a typical program created by young learners of the Scratch programming language [39]: The player has to control a bowl at the bottom of the screen using the cursor keys to catch as much dropping fruit with the bowl as possible within a given time limit.
Games are intentionally designed to be challenging for human players in order to keep them hooked and entertained. Unfortunately, precisely this aspect also makes game-like programs very difficult to test, and classical approaches to automated test generation will struggle to interact with games in a successful way [11]. In Fig. 1a, a test generator would need to successfully catch all apples for 30 seconds without dropping a single one in order to win the game and reach the winning state.
While winning the game is out of question for a traditional automated test generator, it may nevertheless succeed in producing tests for partial aspects of a game, such as catching an individual banana or apple for the game shown in Fig. 1a. Such tests typically consist of static, timed input sequences that are sent to the program under test to reproduce a certain program execution path. This causes a problem: Games are inherently randomized, and playing the same game twice in a row may lead to entirely different scenarios. It may be possible to instrument the test execution environment such that the underlying random number generator produces a deterministic sequence [38]. The Whisker [58] test framework for Scratch, for example, allows setting the random number generator to a fixed seed, such that the fruit in Fig. 1a always appears at the same location in the same program. However, even the slightest change to the program may affect the order in which the random number generator is queried, thus potentially invalidating the test. For example, if the banana sprite is removed from the game in Fig. 1a, even though the code of the apple sprite is unchanged the position at which the apple spawns changes, as the order in which the random numbers are consumed in the program is different, and as a result a test intended to catch the apple sprite would likely drop the apple. Even if by chance the test would succeed in catching the apple despite the randomness, the exact program state would likely be different, and an assertion on the exact position of the apple or bowl in Fig. 1a would fail, rendering the use of classical test assertions impossible.
To tackle the test generation and oracle problem for game-like programs, we propose the use of neural networks as dynamic tests. For instance, Fig. 1b shows a network structure adapted to reaching code related to winning the FruitCatching game (Fig. 1a). It uses aspects of the program state such as sprite positions as input features, and suggests one of the possible ways to interact with the program. The architecture of this example network puts strong emphasis on the horizontal distance between the bowl and the apple which reflects that catching apples rather than bananas is necessary to win the game, and indeed the network is able to win the FruitCatching game by catching all apples for 30s. In contrast to conventional test suites consisting of static input sequences, such dynamic tests are capable of reacting to previously unseen program states, which is particularly useful for game-like programs that are heavily randomized. The same dynamic tests can also serve as test oracles in a regression testing scenario by comparing node activations of a supposedly correct program version against a modified one. For instance, Fig. 2 shows the activation distribution of node H20 from Fig. 1b at time-step 50 when executed 100 times on a correct version of FruitCatching. Since the most influential input of node H20 is the horizontal distance between the bowl and the apple, the network's effort to catch the fruit can clearly be observed from the high density around the node activation of zero. The two example incorrect program versions (mutants) depicted as orange dots disallow the player to move to the left or right, respectively, resulting in suspicious activation values that will be reported as invalid program behavior.
In this paper we introduce Neatest, an approach that implements this idea using neuroevolution [18] to automatically generate artificial neural networks that are able to test games reliably, such as the network shown in Fig. 1b. Neatest targets games created in Scratch [39], a popular block-based programming environment with over 90 million registered users and even more shared projects at the time of this writing 3 and is implemented on top of the Whisker [58] testing framework for Scratch. Given a Scratch program, Neatest iteratively targets statements based on the control dependence graph of the program, and evolves networks (i.e., dynamic tests) to reach those statements guided by an adapted reachability-related fitness function. Notably, by including statements related to the winning state of a game, the networks implicitly learn to meaningfully play and eventually win those games without requiring any domain-specific knowledge about the games. Using the dynamic tests it produces, Neatest introduces a novel test oracle approach based on Surprise Adequacy [30] to detect incorrect program behavior by analyzing the networks' node activations during the execution of a program under test.
In detail, the contributions of this paper are as follows: • We propose Neatest, a novel test generation approach that uses the NeuroEvolution of Augmenting Topologies (NEAT) [61] technique to evolve artificial neural networks capable of testing game-like programs reliably.
• Our testing tool implements this approach in the context of the Scratch educational programming environment and the Whisker test generator for Scratch.
• We empirically demonstrate that the proposed framework is capable of producing tests for 25 Scratch games that are robust against randomized program behavior.
• We empirically show through mutation analysis on 25 Scratch games that the behavior of neural networks can serve as a test oracle and detect erroneous program behavior.

BACKGROUND
In this paper we combine the ideas of search-based software testing with neuroevolution, considering the application domain of games implemented in the Scratch programming language.

Search-based Software Testing
Search-based software testing (SBST) describes the process of applying meta-heuristic search algorithms, such as evolutionary algorithms, to the task of generating program inputs. The search algorithm is guided by a fitness function, which typically estimates how close a test is towards reaching an individual coverage objective, or achieving 100% code coverage. The most common fitness function derives this estimate as a combination of the distance between the execution path followed by an execution of the test and the target statement in the control dependence graph (approach level [66]), and the distance towards evaluating the last missed control dependency to the correct outcome (branch distance [34]). The approach is applicable to different testing problems by varying the representation used by the search algorithm. For example, SBST has been used to evolve parameters for function calls [36], sequences of method calls [5,19,62], sequences of GUI interactions [22,41], or calls to REST services [3]. The search only derives test inputs to exercise a program under test, and test oracles are typically added separately as regression assertions, which capture and assert the behavior observed on the program from which the tests are derived [20,69]. Since the tests derived this way cannot adapt to different program behavior, we call them static tests.

Neuroevolution
Artificial neural networks (ANNs) are computational models composed of several interconnected processing units, so-called neurons.
An ANN can be interpreted as a directed graph where each node corresponds to a neuron model, which usually implements a nonlinear static transfer function [14]. The edges of the graph, which connect nodes with each other, are represented by weights that determine the connection strength between two neurons. Altogether, the number and type of neurons and their interconnections form an artificial neural network's topology or architecture.
Before an ANN can solve specific problems, it has to be trained in the given problem domain. During training, learning algorithms are used to find suitable network parameters, such as the weights of the connections within a network. Learning algorithms commonly apply backpropagation [51], which updates the weights by calculating the gradient for each connection individually. However, backpropagation on its own is only capable of tuning the weights of a neural network. Developing an appropriate network architecture remains a tedious task for the developer. A promising approach to eliminate these time-consuming tasks is to apply evolutionary algorithms that can optimize both, the weights of networks and their architecture.
Instead of using a conventional learning algorithm, neuroevolution encodes ANNs in genomes and gathers them in a population.
In each iteration, a subset of the current population is selected and evolved using mutation and mating procedures inspired by the principles of Darwinian evolution. Then, each genome's performance is evaluated using a fitness function, which reflects how close a given genome is to solving the problem at hand. Finally, following the paradigm of survival of the fittest, a new generation of the population is formed by selecting the fittest genomes of the population. By exploring the search space through many generations of mutating and mating these genomes, it is expected that eventually a neural network with optimal topology and weights for the given problem will be found. With this learning approach the weights, the number of neuron layers, and the interconnections between them, can be genetically encoded and co-evolved at the same time.
The popular NeuroEvolution of Augmenting Topologies [61] (NEAT) algorithm solves several challenges of Topology and Weight Evolving Artificial Neural Networks, such as the competing conventions problem [49]. NEAT solves this problem by introducing innovation numbers that enable the comparison of genes based on their historical origin. Another crucial aspect of NEAT is the use of speciation [21] to protect innovative networks. This is necessary since innovative topologies tend to initially decrease the fitness of a network, leading to architectural innovations having a hard time surviving even a single generation. Speciation ensures that neural networks with similar structures have to primarily compete against other networks in the same species, which gives them time to optimize their weights. Two networks are assigned to the same species if the number of mismatching genes and the average connection weight difference falls below a threshold, which is adjusted in each generation of the algorithm based on the number of species that are present in the current generation: if there are fewer species than desired, the threshold is reduced (e.g., by 0.3) and vice versa.
NEAT's mutation operators can be divided into two groups: structural mutations and non-structural mutations. The former modify a network's topological structure, while the latter operate on the attributes of connection genes. The crossover operator randomly selects two parents and aligns their connection genes using the assigned innovation numbers. Then, both connection gene lists are sequentially traversed, and certain rules are applied to each gene pair: Similar genes are either inherited randomly from one parent or combined by averaging the connection gene weights of both parents. On the other hand, genes with differing innovation numbers are always inherited from the more fit parent.

Testing Scratch Programs
The block-based programming language Scratch [39] provides predefined command blocks encoding regular programming language statements as well as domain-specific programming instructions that make it easy to create games. Scratch programs are created by visually arranging these command blocks according to the intended program behavior. Scratch programs consist of a stage and a collection of sprites. The former represents the application window and displays a background image chosen by the user. Sprites, on the other hand, are rendered as images on top of the stage and can be manipulated by the user. Both the stage and the sprites contain scripts formed by combining command blocks to define the functional behavior of the program. Besides control-flow structures or variables, the blocks represent high-level commands to manipulate sprites. Scratch programs are controlled via user inputs such as key presses, text, or mouse movement. To engage learners, the Scratch programs they create are usually interactive games.
Testing and dynamic analyses are important for Scratch programs: Even though the Scratch blocks ensure syntactic correctness, functional errors are still feasible, raising the need for tests to validate the desired behavior of programs. In particular, tests are a prerequisite for effective feedback [6,23,28,70] and hints [29] to learners, as well as for automated assessment [1,25]. Whisker [58] is a framework that automates testing of Scratch programs by sending inputs to Scratch programs and comparing the system's observed behavior against a predefined specification.
In order to discover as many system states as possible and thereby enhance the chances of finding violated properties, it is crucial to have a widespread set of test inputs. The Scratch inputs used to stimulate the given program under test are assembled in the socalled test harness. Whisker offers two types of test harnesses: a manually written test harness and an automatically generated test harness using search-based test generation approaches [11].
Conventional search-based test generation is often not powerful enough to cover advanced program states, especially in game-like projects [11]. In order to increase the effectiveness of automatic test generation, we introduce a novel test generation approach by extending the Whisker testing tool. The proposed test generator uses neuroevolution to produce neural networks that are capable of extensively exercising game-like programs.

TESTING WITH NEUROEVOLUTION
Traditional tests of static input sequences cannot react to deviating program behavior properly and therefore fail to test randomized programs reliably. As a robust alternative to static test suites, we introduce Neatest, an extension of the Whisker test generation framework [58] that is based on the NEAT [61] algorithm. Neatest generates dynamic test suites consisting of neural networks that are able to withstand and check randomized program behavior.
Algorithm 1 shows the test generation approach of Neatest, which starts in line 5 with the selection of a target statement based on the CDG and a list of yet uncovered program statements (Section 3.1). Next, a new population of networks is created depending on the search progress: If no statements have been covered yet, the first population consists of networks where each sprite's feature group (Section 3.2.1) is fully connected to a single hidden node that is connected to all output nodes. Otherwise, a new population is produced by cloning and mutating networks that proved to be viable solutions for previously targeted statements. By selecting prior solutions, we focus on networks already capable of reaching interesting program states, which may be prerequisites for reaching more advanced states. To avoid unnecessary complex network structures, a certain share (e.g., 10%) of every new population consists of freshly generated networks. We require hidden layer neurons to determine the correctness of a program (Section 3.4).
The following loop over all networks in line 9 starts with the play loop in which a network simulates a human player by repeatedly sending input events to a given Scratch program (Section 3.2.2). The inputs for the networks are extracted from the current state of the program, while the possible outputs are determined by the actions a player can take in the game (Section 3.2.1).
After a network has finished its playthrough, lines 11 to 16 evaluate how reliably the network can cover the current target statement This new generation is then the starting point for the next iteration of the algorithm. Once a network has been optimized to cover reliably for a user-defined number of times , the network is added as a test to the dynamic test suite, and the next target statement is selected (lines [18][19][20]. This process is repeated until the search budget is exhausted or all statements have been covered, and the dynamic test suite is returned to the user. The dynamic tests serve not only to exercise the programs, but also as test oracles for validating the functionality in a regression testing scenario (Section 3.4).

Explorative Target Statement Selection
Neatest iteratively selects increasingly more difficult target statements to guide the creation of incrementally more complex networks. In order to achieve this, targets are selected from the test program's control dependence graph (CDG) [9], a directed graph that shows which program statements depend on which control  locations. Since Scratch programs typically contain many small scripts that communicate via events and messages, we combine the scripts of a Scratch program into an interprocedural CDG that covers the control flow of the entire program. For example, Fig. 3a shows a Scratch program consisting of two scripts, which are combined into one interprocedural CDG (Fig. 3b) by introducing an artificial Entry node. Target statements are selected from children of already covered program statements, as advanced states can only be reached if previous control locations can be passed appropriately. If no statements have been covered yet, the root node of the CDG (Entry) is selected. In case more than one viable child exists, Neatest favors program statements that have accidentally been reached while focusing on other program states but have not yet passed the robustness check. Considering the example of Fig. 3b and assuming that the search was able to trigger the right key-press once without covering the corresponding event handler reliably, the next target statement would be set to the keyPressed:right statement. Otherwise, if none of the three statements that have a directly covered parent (say, stop, keyPressed:right) had been reached once, would be randomly set to one of these three statements. To avoid getting stuck trying to cover hard-to-reach statements while other, perhaps easier-to-reach states are still present, Neatest changes its currently selected target after a user-defined number of consecutive generations without improvement of fitness values.

Play Loop
Within the Play Loop, the networks govern the execution of a program by repeatedly sending input events until the execution halts, a pre-defined timeout has been reached, or the targeted statement was covered. To make a decision on which user event to select at a given moment, we provide the networks with input features extracted from the current program state. The selected event is then sent to the Scratch program to advance the program execution. • Heading direction iff the rotation style is set to all around.
• Selected costume iff the sprite contains code to change its costume. Defined as ∈ N, indexing the current costume.
• Distance to sensed sprite iff the sprite contains code that checks for touching another sprite. Defined through the x and y distance to the sensed sprite in the range [−600, 600].
• Distance to sensed color iff the sprite contains code that checks for touching a given color. Colors are measured by four rangefinders, which measure the distance on the canvas to the sensed color in the directions [0, 90, 180, −90], with 0 representing the current heading direction of the sprite. Admissible values are again restricted to [−600, 600].
In addition to relevant sprite attributes, we also add all program variables, for example, the current score of a game, to the set of input features. We add input nodes for all extracted features, and group them by the sprite they belong to. Since we only include relevant features for which corresponding code exists, the input features may not only differ between games but also within the same game, for example whenever a sprite creates a clone that has its own attributes. However, neuroevolution allows the framework to adapt to these input feature changes dynamically by adding input nodes to the networks whenever a new behavioral pattern is encountered. Finally, to ensure all extracted input features have the same weight, they are normalized to the range [−1, 1].
Output features of a network resemble the set of user events a human player can send to the Scratch application at a given point in time. The framework simulates human inputs using the following Scratch events: • KeyPress: Presses a specific key on the keyboard for a parameterized amount of time.
• TypeText: Types text using the keyboard.
• MouseMove: Moves the mouse to a parameterized position.
• MouseMoveTo: Moves the mouse to a position inferred by static analysis (e.g., location of another sprite).
• MouseDown: Presses the left mouse button for a parameterized amount of time.
• Sound: Sends simulated sound to the program.
• Wait: Waits for a parameterized amount of time. Neatest analyzes the source code of all actively running scripts for a given program state in order to select the subset of event types for which active event handlers exist. After minimizing the set of event types, we create one output node for each remaining event.
In case there are parameterized events, such as MouseMove events requiring coordinates where the mouse pointer should be moved to, the classification problem is further extended to a combination of a classification and regression problem. These parameters are produced via a multi-headed network model [27] in which regression nodes are mapped to parameterized events. Similar to input features, the set of feasible output features and the number of required output nodes may change throughout the course of a game.

Network Activation & Event
Selection. The problem of deciding which action to take at the current state of a game is cast to a multi-class single-label classification problem. Classification steps start by loading the input features of the current program state into the corresponding input nodes. Then, the neural network is activated in order to produce an output based on the fed input features. During network activation, values residing in the input nodes flow through the network in several timesteps. In every timestep, each node adds up all the activation values from the previous timestep and calculates the result of its own activation using the tanh function [26] on the summed-up values.
To not perturb values gathered during feature extraction, all input nodes send the normalized input features directly into the network without activation functions. In a single timestep, activation only flows from one neuron to the next, thus several network activations are required for the input nodes' signals to reach the output nodes.
After the input signal has reached the output nodes, a probability distribution is calculated over the set of available events using the traditional softmax function [15]. The classification task is extended into a regression problem whenever a network selects a parameterized event. Parameters for the selected event are gathered by querying the responsible nodes in the network's regression head.
Selected events are passed on to the Scratch VM, where they may trigger the activation of previously inactive scripts. Upon receiving an input event, the Scratch VM executes a Scratch step by sequentially executing blocks of currently active scripts until either a block that halts the program execution or the end of the script are reached. The Scratch step finishes by updating the state of the VM to match the effects of the executed blocks. The playing loop then starts anew by extracting the input and output features of the updated VM.

Network Evaluation
Given a selected target statement , the evolution of networks is guided by a fitness function which estimates how close a network is to reaching and, once reached, how reliably it is executed. We first calculate the objective function [11] that guides the search towards reaching using a linear combination of: • Approach level (AL): Integer defining the number of control dependencies between the immediate control dependency of the target and the closest covered statement.
• Branch distance (BD): Indicates how close a network is to satisfying the first missed control dependency. Zero if the control location has been passed towards the target statement. Scratch often allows for a precise definition of the branch distance. For example, in Fig. 3b, the branch distance for the if:touching statement is defined as the normalized distance between the corresponding sprites.
• Control flow distance (CFD): As execution may stop in the middle of a sequence of blocks (e.g., because of timed statements), the CFG counts the number of blocks between the targeted statement and the nearest covered statement. To avoid deceiving fitness landscapes, we normalize the branch distance and the control flow distance in the range [0, 1] using the normalization function ( ) = /(1 + ) [2], and multiply the approach level with a factor of two: > 0, the target statement was not covered and we set the fitness to = 1/ to create a maximization objective towards covering . Otherwise ( = 0), the network managed to cover the target once and we evaluate whether it can also cover the same target in randomized program scenarios. For this purpose, we generate up to − 1 random seeds, count for how many seeded executions the network is able to reach the target statement again, and finally set the fitness function to = 1 + . We decrement the desired robustness count and increment the fitness value by one to account for the first time was covered due to = 0. The fitness function ensures that networks that are closer or more robust in covering a specific statement are prioritized during the evolution. If a network eventually passes the robustness check ( = ), the network is added to the dynamic test suite as test for target statement and the next target is selected by querying the CDG as described in Section 3.1. Since covering one statement usually leads to reaching other related statements as well, we simultaneously evaluate whether the network may also satisfy the robustness check for other yet uncovered program statements.

Neural Networks as Test Oracles
In order to determine whether a test subject is erroneous, we observe how surprised a network behaves when confronted with the program under test and regard highly surprising observations as suspicious. As a metric, we use the Likelihood-based Surprise Adequacy (LSA) [30], which uses kernel density estimation [65] to determine how surprising the activations of selected neurons are when the network is presented with novel inputs. In the application scenario of regression testing, node activations originating from a supposedly correct program version serve as the ground truth and will be compared to activations occurring during the execution of the test subject. To incorporate many randomized program scenarios, we collect the ground truth activations by executing the networks on the sample program using a series of different random seeds. Defective programs are then detected if the LSA value surpasses a pre-defined threshold, or for the special case that all ground truth traces have a constant value, if the surprise value is above zero since in this scenario already tiny deviations are suspicious.
Neatest only evaluates activation values occurring within hidden nodes because these nodes strike a nice balance between being close to the raw inputs that represent the program state while already offering an abstraction layer by incorporating a network's behavior. This allows differentiating between suspicious and novel program behavior, an essential characteristic for testing randomized programs that is missing in traditional static test assertions. For example, in the FruitCatching game (Fig. 1a), the apple and bananas may spawn at entirely new x-coordinates, but the program state is still correct as long as they spawn at a certain height. Successfully trained networks can differentiate between novel and suspicious states because they are optimized to catch falling fruit by minimizing the distance between the bowl and the fruit, as shown by the zero-centered activation distribution in Fig. 2. Since both example defective programs, represented as orange dots, are far off the distribution center, they are rather surprising, with LSA values of 50 and 102. Therefore, given a threshold below these values, Neatest correctly classifies these program versions as faulty.
In contrast to the original definition of LSA [30], we do not compare groups of nodes that may reside in the same layer but compare the activation values of hidden nodes directly. Furthermore, we classify activation values by the Scratch step in which they occurred. This precise approach of comparing node activations offers two major advantages: First, we can detect tiny but nonetheless suspicious program deviations that may only occur within a single node by calculating the LSA value for each node separately. Second, if a suspicious activation within a node was detected, we can identify the exact point in time during the execution and the rough reason for the suspicious observation by following the suspicious node's incoming connections back to the input nodes.
Changes to the structure of a network, which may occur during an execution, can also provide strong evidence of suspicious program behavior. For instance, output nodes may be added if a game can process different user events, and input nodes may be added for new sprite clones (cf. Section 3.2). Therefore, we can deduce from a change in a network's structure that the test subject exposes diverging and maybe even erroneous program behavior.

EVALUATION
In order to evaluate the effectiveness of the proposed testing framework we aim to answer the following three research questions: • RQ1: Can Neatest optimize networks to exercise Scratch games reliably?
• RQ2: Are dynamic test suites robust against randomized program behavior?

Dataset
To establish a diverse dataset for the evaluation, we collected 187 programs that represent the educational application domain of Scratch from an introductory Scratch book 6 , prior work [58], and four tutorial websites for children (Code Club 7 , Linz Coder Dojo 8 , learnlearn 9 , junilearning 10 ). Three selection criteria were used to determine if a project included in this set of 187 programs should be considered for evaluation: First, a given project has to resemble a game that processes user inputs supported by the Whisker framework and challenges the player to achieve a specific goal while enforcing a set of rules. Second, the game must include some form of randomized behavior. Finally, we exclude games that do not have a challenging winning state and can thus be easily covered just by sending arbitrary inputs to the program. Applying all three selection criteria to the mentioned sources and skipping programs that are similar to already collected ones in terms of player interaction and the overall goal of a game resulted in a total of 25 programs (including the FruitCatching game shown in Fig. 1a); statistics of these games are shown in Table 1. Overall, each of the 25 games offers unique challenges and ways of interacting with the program.

Methodology
All experiments were conducted on a dedicated computing cluster containing nine nodes, with each cluster node representing one AMD EPYC 7443P CPU running on 2.85 GHz. The Whisker testing framework 11 allows users to accelerate test executions using a customizable acceleration factor. In order to speed up the experiments, all conducted experiments used an acceleration factor of ten.

RQ1:
We evaluate whether Neatest can train networks to cover program states reliably by comparing the proposed approach against a random test generation baseline. While Neatest produces dynamic tests in the form of neural networks, the random testing approach randomly selects input events from a subset of processable events and saves the chosen events as static test cases. Neatest maintains a population of 300 networks, and both methods generate tests until a search budget of 23 hours has been exhausted. The combination of 300 networks per population and the search budget of 23 hours allows the framework to conduct a reasonable amount of evolutionary operations in order to sufficiently explore the search space of the most challenging test subjects in the dataset. However, for some test subjects, satisfying results may already be found using a population size of 100 and a search budget of only one hour. In general, the easier a winning state can be reached and the fewer control dependencies a Scratch program has, the fewer resources are required.
We set the number of non-improving generations after which a target is switched to five because this value provides the evolution enough time to explore the search space while also avoiding wasting too much time on difficult program states. To distribute the 300 networks of a population across the species such that each species can meaningfully evolve the weights of its networks, we set the targeted species number to ten. For both test generators, the maximum time for a single playthrough was set to ten seconds, which translates to a play duration of up to 100 seconds due to the acceleration factor of ten. The remaining neuroevolution hyperparameters are set according to the original NEAT study [61].
As a metric of comparison, we consider coverage values across 30 experiment repetitions with the Vargha & Delaney (ˆ1 2 ) effect size [64] and the Mann-Whitney-U-test [40] with = 0.05 to determine statistical significance. To evaluate whether Neatest can train networks to reach challenging program states, we manually identified statements representing a winning state for each program and report how often this winning state was reached within the 30 experiment repetitions. Since we are interested in tests that are robust against randomized program behavior, we treat a statement only as covered if a given test passes the robustness check (Section 3.3) for ten randomly seeded program executions.

RQ2.
In order to explore if the generated dynamic test suites are truly robust against diverging program behavior, we randomly extract for each program ten dynamic and static test suites that were produced during RQ1. For the purpose of eliminating differences originating from the test generation process, both test suite types are extracted from the Neatest approach. The static test suites correspond to the input sequences successful networks produced when they entered the robustness check. All extracted test suites are then executed on the corresponding programs using seeds different from those during the test generation phase.
We evaluate the robustness of both test suite types by reporting the difference in coverage between the test generation and test execution phase and investigate the effectiveness of dynamic test suites against static test suites by comparing the achieved coverage andˆ1 2 values. Similar to RQ1, we use the Mann-Whitney-U-test to report statistically significant results. To match the application scenario of test suites, we do not use robustness checks and treat a statement as covered if it has been reached at least once. Within RQ2, we compensate for random influences by applying every extracted test suite to ten new random seeds, which results in 100 test runs for each test suite type on every dataset project. RQ3. To answer the question if networks can serve as test oracles, we extended Whisker with a mutation analysis feature implementing the eight different mutation operators shown in Table 2, and applied mutation analysis to all 25 projects. These mutation operators were selected based on the traditional set of sufficient mutation operators [44]. After generating mutant programs, we execute the dynamic test suites of RQ2 on the respective mutants and measure how surprised the networks are by the modified programs. The ground truth activation traces required for calculating the LSA are generated by executing each test suite 100 times on the unmodified program using randomly generated seeds. A program is marked as mutant if the LSA value of a single node activation surpasses an experimentally defined threshold of 30. Besides calculating the LSA value, mutants are also killed if the network structure changes while being executed on the mutant. We answer RQ3 by reporting the distribution of killed mutants across the eight applied operators. Furthermore, we verify that the networks do not simply mark every program as a mutant by calculating the false-positive rate on unmodified programs. Similar to RQ2, we account for randomness within the mutant generation and network execution process by repeating the experiment for all extracted test suites ten times using varying seeds. To avoid an explosion of program variations, each experiment repetition was restricted to 50 randomly selected mutants per operator.

Threats to Validity
External Validity: The dataset of 25 projects covers a broad range of game types and program complexities. Even though high priority was given to establish a dataset of games with many different objectives and ways to interact with them, we cannot guarantee that the results generalize well to other Scratch applications or games developed in different programming languages.
Internal Validity: Randomized factors within the experiments pose another threat to validity since repeated executions of the same experiments will, by definition, lead to slightly different outcomes. However, we expect 30 experiment repetitions for RQ1 and 100 test results for each project in RQ2 and RQ3 to suffice for assuming robust experiment results. The threshold that determines at which surprise value a program is marked as a mutant was determined experimentally and may not work well for other programs.
Construct Validity: For evaluating the effectiveness of Neatest in generating robust test suites, we used block coverage which is similar to statement coverage in text-based programming languages. However, coverage is not always a good indicator because Scratch programs may often already be covered by sending arbitrary inputs to the program. For exactly this reason, we focused on selecting games that have a winning state and therefore pose a true challenge to test generators. We answer whether networks can serve as test oracles by reporting the ratio of killed mutants. However, not every mutant must necessarily represent erroneous behavior and may still be considered a valid program alternative by a human.

RQ1: Can Neatest Optimize Networks to Exercise Scratch Games Reliably?
Our first research question evaluates whether neural networks can be trained to exercise randomized Scratch programs reliably. Table 3 summarizes the experiment results and shows that the random tester and Neatest reach generally high coverage values of 89.07% and 94.60%. This is because the programs tend to be small in terms of their number of statements. However, Scratch programs consist of many domain-specific blocks specifically designed for game-behavior, such that it is possible to implement fully functional game-behavior with very few blocks, which in other programming languages might require hundreds of lines of code. Blindly sending inputs, as random testing does, leads to the execution of a large share of these blocks without, however, actually playing the game. This can be seen when considering specifically how often an actual winning state was reached. For example, in FallingStars both approaches achieve almost the same average coverage (97.80% and 100%), although only Neatest is able to cover statements related to the challenging winning state. Table 3 shows that Neatest wins the game, on average, 20 times, while the random test generator has trouble meaningfully exercising the games and reaches the winning state only five times per game. For three games, Neatest fails to reach the winning state because either the allotted play duration is too short (DessertRally), the game is too complex to evolve sufficiently optimized networks using the experiment parameters (Snake), or more sophisticated evolution strategies are required to solve advanced search-problems, such as the maze problem [52] (Dodgeball).
CityDefender is the only game for which Neatest achieves less coverage than the random tester. The statements responsible for these results are linked to relatively easy program states that the random tester can easily reach through randomly firing inputs at the program under test. While Neatest also sometimes performs the required actions, the networks must be specifically trained to send those inputs regardless of which randomized program state they are confronted with. However, the relatively long duration of a single playthrough in this game sometimes leads to experiment repetitions in which the respective statements never get targeted. The three reached winning states in CityDefender that correspond to experiment repetitions in which a winning statement was actually targeted demonstrates that using a more sophisticated statement selection technique would allow Neatest to train robust networks that reliably perform the required actions.
Having execution times of 23 hours may be recognized as a limiting factor of the proposed approach. However, we selected this relatively high search budget in order to sufficiently explore those programs in the dataset that have exceptionally long fitness evaluation durations. Fig. 4 illustrates the achieved reliable coverage over time for both approaches across all evaluation subjects. The results show that Neatest is more effective than random testing by covering more program statements at any stage of the search process. Furthermore, the proposed approach covers 90% of all program statements in less than three hours (156 min), while the random tester is not able to reach the same level of coverage at all. Moreover, Neatest fully covers 5/25 projects in all 30 repetitions within the first hour, indicating that the required search time is highly dependent on the complexity of the game. In order to reduce the required search time for the more challenging programs, advanced search strategies, such as combining Neatest with backpropagation [7], could be interesting avenues for future work. tester is not able to reach the same level of coverage at all. Moreover, Neatest fully covers 5/25 projects in all 30 repetitions within the first hour, indicating that the required search time is highly dependent on the complexity of the game. In order to reduce the required search time for the more challenging programs, advanced search strategies, such as combining Neatest with backpropagation [7], could be interesting avenues for future work.
Summary RQ1: Neatest succeeds in mastering games without any domain specific knowledge by winning games 20/30 times on average, achieving 94.60% block coverage.

RQ2: Are Dynamic Test Suites Robust Against Randomized Program Behavior?
In order to evaluate the importance of training networks to reliably cover statements, RQ2 extracts static event sequences from the dynamic tests generated for RQ1, and compares them in terms of the coverage variation observed on executions with different random seeds. Each static test is the result of executing a dynamic test on the program under test once. Hence, for the particular seed of the random number generator on which the static test is derived, the coverage between both test types is by construction identical. Table 4 summarizes the effects of re-running the resulting tests for ten different random seeds on the respective programs. The results show that dynamic tests are robust against randomized programs-coverage even increases slightly by 1.22% compared to the test generation phase. In contrast, static tests have a drop of 8.17% in coverage, which is substantial considering the generally high coverage observed in RQ1. The slight increase in coverage for the dynamic test suites may seem surprising, but can be explained by the way coverage is measured: In contrast to RQ1, which measured how many statements were reliably reached by a test generator, here we count how many statements are covered on average over the 100 test executions. Thus, also statements that are only covered in some of the runs contribute to the overall coverage. The drop of 8.17% coverage for static tests demonstrates the need for robust test suites when testing randomized programs. This clear advantage of dynamic tests becomes even more apparent when looking at theˆ1 2 values (on average 0.82), which indicate that for every program in the dataset, networks perform significantly better than static test sequences.
Summary RQ2: Static test suites have a significant drop of 8.17% in coverage on re-execution, while dynamic test suites are robust and lose no coverage.

RQ3: Can Networks Serve as Test Oracles?
The randomized behavior of games impedes the generation of reliable test oracles. Hence, RQ3 aims to investigate if the networks of dynamic tests can serve as test oracles that can distinguish randomized program scenarios from faulty behavior. We generated 243835 mutants using eight different mutation operators across all games in our dataset and checked whether the networks were able to identify them. Table 5 demonstrates that the networks managed to achieve an average mutation score of 65.62 % per project, while maintaining a relatively low false-positive rate of 19.70 %. Figure 5 indicates that the average false-positive rate is deceiving as there are two extreme outliers that have a strong influence on the mean, while the median is considerably lower with a value of only 10%. In those two programs, namely Dragons and FinalFight, the networks are confronted with many sprites having attributes that are distinct in almost every program execution, resulting in activation traces that are entirely different from previously observed ones, and thus seem suspicious. This problem could be solved by either increasing the number of recorded ground truth traces or through a more sophisticated abstraction layer by restricting the set of observed hidden nodes to nodes that reside in hidden layers that are further away from the input layer.
Neatest detects the least mutants for CityDefender, which is a direct consequence of the poorly trained networks (see Section 4.4). The lowest mutation kill rate can be observed in Fig. 5 for the Single Block Deletion mutation operator, because Scratch programs often contain statements that do not change the program behavior but instead offer purely visual effects. Depending on the scope of what is recognized as faulty behavior, these visual deviations could be detected by collecting more fine-grained input features, such as the visual effects applied to the individual sprites. The highest mutation kill rate was achieved for the Key Replacement Mutation operator (99.18 %), in which an event handler's observed key gets replaced with a randomly selected one. In many of these cases, the mutant

RQ2: Are Dynamic Test Suites Robust
Against Randomized Program Behavior?
In order to evaluate the importance of training networks to reliably cover statements, RQ2 extracts static event sequences from the dynamic tests generated for RQ1, and compares them in terms of the coverage variation observed on executions with different random seeds. Each static test is the result of executing a dynamic test on the program under test once. Hence, for the particular seed of the random number generator on which the static test is derived, the coverage between both test types is by construction identical. Table 4 summarizes the effects of re-running the resulting tests for ten different random seeds on the respective programs. The results show that dynamic tests are robust against randomized programs-coverage even increases slightly by 1.22% compared to the test generation phase. In contrast, static tests have a drop of 8.17% in coverage, which is substantial considering the generally high coverage observed in RQ1. The slight increase in coverage for the dynamic test suites may seem surprising, but can be explained by the way coverage is measured: In contrast to RQ1, which measured how many statements were reliably reached by a test generator, here we count how many statements are covered on average over the 100 test executions. Thus, also statements that are only covered in some of the runs contribute to the overall coverage. The drop of 8.17% coverage for static tests demonstrates the need for robust test suites when testing randomized programs. This clear advantage of dynamic tests becomes even more apparent when looking at theˆ1 2 values (on average 0.82), which indicate that for every program in the dataset, networks perform significantly better than static test sequences.

RQ2: Are Dynamic Test Suites Robust Against Randomized Program Behavior?
In order to evaluate the importance of training networks to reliably cover statements, RQ2 extracts static event sequences from the dynamic tests generated for RQ1, and compares them in terms of the coverage variation observed on executions with different random seeds. Each static test is the result of executing a dynamic test on the program under test once. Hence, for the particular seed of the random number generator on which the static test is derived, the coverage between both test types is by construction identical. Table 4 summarizes the effects of re-running the resulting tests for ten different random seeds on the respective programs. The results show that dynamic tests are robust against randomized programs-coverage even increases slightly by 1.22% compared to the test generation phase. In contrast, static tests have a drop of 8.17% in coverage, which is substantial considering the generally high coverage observed in RQ1. The slight increase in coverage for the dynamic test suites may seem surprising, but can be explained by the way coverage is measured: In contrast to RQ1, which measured how many statements were reliably reached by a test generator, here we count how many statements are covered on average over the 100 test executions. Thus, also statements that are only covered in some of the runs contribute to the overall coverage. The drop of 8.17% coverage for static tests demonstrates the need for robust test suites when testing randomized programs. This clear advantage of dynamic tests becomes even more apparent when looking at theˆ1 2 values (on average 0.82), which indicate that for every program in the dataset, networks perform significantly better than static test sequences.
Summary RQ2: Static test suites have a significant drop of 8.17% in coverage on re-execution, while dynamic test suites are robust and lose no coverage.

RQ3: Can Networks Serve as Test Oracles?
The randomized behavior of games impedes the generation of reliable test oracles. Hence, RQ3 aims to investigate if the networks of dynamic tests can serve as test oracles that can distinguish randomized program scenarios from faulty behavior. We generated 243835 mutants using eight different mutation operators across all games in our dataset and checked whether the networks were able to identify them. Table 5 demonstrates that the networks managed to achieve an average mutation score of 65.62 % per project, while maintaining a relatively low false-positive rate of 19.70 %. Figure 5 indicates that the average false-positive rate is deceiving as there are two extreme outliers that have a strong influence on the mean, while the median is considerably lower with a value of only 10%. In those two programs, namely Dragons and FinalFight, the networks are confronted with many sprites having attributes that are distinct in almost every program execution, resulting in activation traces that are entirely different from previously observed ones, and thus seem suspicious. This problem could be solved by either increasing the number of recorded ground truth traces or through a more sophisticated abstraction layer by restricting the set of observed hidden nodes to nodes that reside in hidden layers that are further away from the input layer.
Neatest detects the least mutants for CityDefender, which is a direct consequence of the poorly trained networks (see Section 4.4). The lowest mutation kill rate can be observed in Fig. 5 for the Single Block Deletion mutation operator, because Scratch programs often contain statements that do not change the program behavior but instead offer purely visual effects. Depending on the scope of what is recognized as faulty behavior, these visual deviations could be detected by collecting more fine-grained input features, such as the visual effects applied to the individual sprites. The highest mutation kill rate was achieved for the Key Replacement Mutation operator (99.18 %), in which an event handler's observed key gets replaced with a randomly selected one. In many of these cases, the mutant 4.6 RQ3: Can Networks Serve as Test Oracles?
The randomized behavior of games impedes the generation of reliable test oracles. Hence, RQ3 aims to investigate if the networks of dynamic tests can serve as test oracles that can distinguish randomized program scenarios from faulty behavior. We generated 243835 mutants using eight different mutation operators across all games in our dataset and checked whether the networks were able to identify them. Table 5 demonstrates that the networks managed to achieve an average mutation score of 65.62 % per project, while maintaining a relatively low false-positive rate of 19.70 %. Figure 5 indicates that the average false-positive rate is deceiving as there are two extreme outliers that have a strong influence on the mean, while the median is considerably lower with a value of only 10%. In those two programs, namely Dragons and FinalFight, the networks are confronted with many sprites having attributes that are distinct in almost every program execution, resulting in activation traces that are entirely different from previously observed ones, and thus seem suspicious. This problem could be solved by either increasing the number of recorded ground truth traces or through a more sophisticated abstraction layer by restricting the set of observed hidden nodes to nodes that reside in hidden layers that are further away from the input layer.
Neatest detects the least mutants for CityDefender, which is a direct consequence of the poorly trained networks (see Section 4.4). The lowest mutation kill rate can be observed in Fig. 5 for the Single Block Deletion mutation operator, because Scratch programs often contain statements that do not change the program behavior but instead offer purely visual effects. Depending on the scope of what is recognized as faulty behavior, these visual deviations could be detected by collecting more fine-grained input features, such as the visual effects applied to the individual sprites. The highest mutation kill rate was achieved for the Key Replacement Mutation operator (99.18 %), in which an event handler's observed key gets replaced with a randomly selected one. In many of these cases, the mutant  is detected due to the network's dynamic adaption to changes in the input and output space (cf. Section 3.2.1).  is detected due to the network's dynamic adaption to changes in the input and output space (cf. Section 3.2.1).
Summary RQ3: A high mutation score of 65.62 % and a low false-positive median of 10% show that networks can distinguish between novel and erroneous behavior and may serve as suitable test oracles for randomized programs.

RELATED WORK
Due to the increasing popularity of NEAT, many variations have been proposed [32,50,60,67,68] and applied to master games in many different gaming environments, such as Atari [24] and realtime based games [45,59]. Since, to the best of our knowledge, no previous work exists that uses neuroevolution for block-based programming environments like Scratch, we applied the established variant of NEAT, and will evaluate improvements in future work. Many reinforcement learning techniques have been shown to be capable of learning to play different game genres such as strategy games [55,56], arcade games [63], first-person shooter games [37,42], and casual games [33]. We use neuroevolution rather than alternative reinforcement learning techniques since NEAT allows easy adaptation to changes in the input space. Furthermore, prior reinforcement learning-based approaches reward an agent for achieving game-specific objectives. In contrast, Neatest explores the source code and automatically derives code-based objectives to cover specific target statements, thus implicitly learning to play the games.
The Likelihood-based Surprise Adequacy metric, which we use as a test oracle, has previously been used for prioritizing test inputs for image classification tasks [30]. Kim et al. [31] reduced the cost of calculating the Surprise Adequacy by replacing the kernel density estimation with the Mahalanobis distance [10]. In future research, we will explore other metrics, such as the certainty of networks in their predictions [16], and their usability as test oracles.
Nowadays, games are either tested manually [13,17,48] or with semi-automated approaches [8,53,57]. Furthermore, many approaches do not aim to detect bugs but rather to evaluate the usability of games [12,35,54]. While recently automated game testing has been explored [4,46,47,71], overall the research area is still young, and to the best of our knowledge no automated approaches exist that generate tests using neuroevolution.

CONCLUSIONS
Games pose a considerable challenge for automated test generation because they require the test generator to master a given game. Furthermore, games tend to be heavily randomized to keep players engaged, which prevents traditional static test suites from testing such programs reliably, and static test assertions from differentiating between novel and erroneous program states. In an attempt to solve these challenges, this work combines search-based software testing with neuroevolution to produce a novel type of test suites: Dynamic test suites consist of neural networks trained via neuroevolution to reach program states such as the winning state reliably, regardless of the encountered program scenarios. By observing the network structure and measuring how surprised the networks are by a given program state, the networks serve as test oracles that detect incorrect program behavior. Our experiments confirm that Neatest manages to master and test Scratch games.
The Neatest approach provides an initial foundation for combining automated testing with neuroevolution. The Scratch games we considered in our prototype are often similar to classic arcade games, a common target for neuroevolution research. In principle, Neatest is also applicable to other domains, such as Android or iOS games, but adaptation will require engineering effort for feature extraction and implementing the play loop. Integrating recent advances in neuroevolution, such as deep learning extensions of NEAT [43], will be of interest in order to generalize further beyond arcade games. Furthermore, it may be worth exploring if Neatest provides a way to overcome the problems caused by randomized program behavior outside the domain of games (i.e., flaky tests). Finally, the Surprise Adequacy metric originates from a highly active area of research, and further research with new and alternative metrics may further improve the detection rates for erroneous program behavior. Neatest and the hosting Whisker testing framework are publicly available at: https://github.com/se2p/whisker ACKNOWLEDGMENTS This work is supported by DFG project FR2955/3-1 "TENDER-BLOCK: Testing, Debugging, and Repairing Blocks-based Programs" and the Federal Ministry of Education and Research through project 01JA2021 (primary::programming) as part of the "Qualitätsoffensive Lehrerbildung", a joint initiative of the Federal Government and the Länder. The authors are responsible for this publication's content.

RELATED WORK
Due to the increasing popularity of NEAT, many variations have been proposed [32,50,60,67,68] and applied to master games in many different gaming environments, such as Atari [24] and realtime based games [45,59]. Since, to the best of our knowledge, no previous work exists that uses neuroevolution for block-based programming environments like Scratch, we applied the established variant of NEAT, and will evaluate improvements in future work.
Many reinforcement learning techniques have been shown to be capable of learning to play different game genres such as strategy games [55,56], arcade games [63], first-person shooter games [37,42], and casual games [33]. We use neuroevolution rather than alternative reinforcement learning techniques since NEAT allows easy adaptation to changes in the input space. Furthermore, prior reinforcement learning-based approaches reward an agent for achieving game-specific objectives. In contrast, Neatest explores the source code and automatically derives code-based objectives to cover specific target statements, thus implicitly learning to play the games.
The Likelihood-based Surprise Adequacy metric, which we use as a test oracle, has previously been used for prioritizing test inputs for image classification tasks [30]. Kim et al. [31] reduced the cost of calculating the Surprise Adequacy by replacing the kernel density estimation with the Mahalanobis distance [10]. In future research, we will explore other metrics, such as the certainty of networks in their predictions [16], and their usability as test oracles.
Nowadays, games are either tested manually [13,17,48] or with semi-automated approaches [8,53,57]. Furthermore, many approaches do not aim to detect bugs but rather to evaluate the usability of games [12,35,54]. While recently automated game testing has been explored [4,46,47,71], overall the research area is still young, and to the best of our knowledge no automated approaches exist that generate tests using neuroevolution.

CONCLUSIONS
Games pose a considerable challenge for automated test generation because they require the test generator to master a given game. Furthermore, games tend to be heavily randomized to keep players engaged, which prevents traditional static test suites from testing such programs reliably, and static test assertions from differentiating between novel and erroneous program states. In an attempt to solve these challenges, this work combines search-based software testing with neuroevolution to produce a novel type of test suites: Dynamic test suites consist of neural networks trained via neuroevolution to reach program states such as the winning state reliably, regardless of the encountered program scenarios. By observing the network structure and measuring how surprised the networks are by a given program state, the networks serve as test oracles that detect incorrect program behavior. Our experiments confirm that Neatest manages to master and test Scratch games.
The Neatest approach provides an initial foundation for combining automated testing with neuroevolution. The Scratch games we considered in our prototype are often similar to classic arcade games, a common target for neuroevolution research. In principle, Neatest is also applicable to other domains, such as Android or iOS games, but adaptation will require engineering effort for feature extraction and implementing the play loop. Integrating recent advances in neuroevolution, such as deep learning extensions of NEAT [43], will be of interest in order to generalize further beyond arcade games. Furthermore, it may be worth exploring if Neatest provides a way to overcome the problems caused by randomized program behavior outside the domain of games (i.e., flaky tests). Finally, the Surprise Adequacy metric originates from a highly active area of research, and further research with new and alternative metrics may further improve the detection rates for erroneous program behavior. Neatest and the hosting Whisker testing framework are publicly available at: https://github.com/se2p/whisker