PaperlayerView exact revision on arXiv

Source-linked AI summary

Search-based Software Testing Driven by Automatically Generated and Manually Defined Fitness Functions

Federico Formica, Tony Fan, Claudio Menghi

arXiv:2207.11016v2cs.SE

TL;DR

Fitness-function design for search-based testing remains complex and time-consuming. ATheNA combines automatically generated and engineer-defined fitness functions, and ATheNA-S applies this approach to Simulink models. In the evaluated benchmarks, ATheNA-S generated more failure-revealing test cases than baseline tools without statistically significant runtime differences, and revealed violations in two case studies.

  • Problem

    Fitness-function design remains complex and time-consuming, despite its importance to guiding search-based testing toward software failures.

    Source: §1 · p. 2

  • Method

    ATheNA combines requirement-derived automatic fitness functions with manually defined functions that encode engineers’ domain knowledge; ATheNA-S targets Simulink models.

    Source: §1 · p. 2

  • Results

    Across evaluated combinations, ATheNA-S generated more failure-revealing cases than both baselines (+7.9% and +11.9% versus automatic fitness; +8.1% and +12.1% versus manual fitness), with no statistically significant efficiency differences.

    Source: §8 · p. 30

  • Takeaways & Limitations

    ATheNA-S revealed a failure-revealing test case for CC4 that the baselines could not find, and generated such cases for representative automotive and medical case studies.

    Source: §6 · p. 26, §8 · p. 30

    ATheNA-S explicitly targets Simulink models, and generalizability to other model types or software remains a conjecture requiring further empirical studies.

    Source: §6 · p. 28

Abstract

from arXiv · show

Search-based software testing (SBST) typically relies on fitness functions to guide the search exploration toward software failures. There are two main techniques to define fitness functions: (a) automated fitness function computation from the specification of the system requirements, and (b) manual fitness function design. Both techniques have advantages. The former uses information from the system requirements to guide the search toward portions of the input domain more likely to contain failures. The latter uses the engineers' domain knowledge. We propose ATheNA, a novel SBST framework that combines fitness functions automatically generated from requirements specifications and those manually defined by engineers. We design and implement ATheNA-S, an instance of ATheNA that targets Simulink models. We evaluate ATheNA-S by considering a large set of models from different domains. Our results show that ATheNA-S generates more failure-revealing test cases than existing baseline tools and that the difference between the runtime performance of ATheNA-S and the baseline tools is not statistically significant. We also assess whether ATheNA-S could generate failure-revealing test cases when applied to two representative case studies: one from the automotive domain and one from the medical domain. Our results show that ATheNA-S successfully revealed a requirement violation in our case studies.

1 INTRODUCTION

Testing failures in cyber-physical systems can be costly, while designing effective fitness functions remains complex and time-consuming. ATheNA combines automatically generated and engineer-defined fitness functions, with ATheNA-S targeting Simulink models.

1 INTRODUCTION

  • The motivation is safety: cyber-physical software failures can cause severe injuries, loss of life, costly recalls, and reputational damage.Automated testing tools are used in automotive, aerospace, and medical safety-critical domains.Source: §1 · p. 1
  • Fitness-function design remains complex and time-consuming despite fitness landscape analysis helping characterize search behavior and its probability of success.The paper frames this as a challenge for SBST, which relies on fitness functions to guide test generation toward failures.Source: §1 · pp. 1–2
  • Automated fitness functions use requirement structure to target likely failure regions, while manual functions use domain knowledge but can bias search toward failure-free regions.Automated functions are general purpose and do not use engineers’ domain knowledge in fitness computation.Source: §1 · p. 2
  • ATheNA combines requirement-derived fitness with engineers’ domain knowledge to direct black-box search toward input regions likely to reveal failures.ATheNA-S instantiates the framework for Simulink models and is implemented as an S-Taliro plugin.Source: §1 · p. 2
  • The evaluation compares ATheNA-S with automatic- and manual-fitness baselines across seven models, 27 requirements, and 39 assumption-requirement combinations.The models and requirements come from the ARCH 2021 Simulink competition.Source: §1 · p. 2

2 AUTOMATIC-MANUAL SBST

ATheNA repeatedly generates inputs, executes the system, and assesses fitness until it finds a failure-revealing test case or exhausts its time budget. Its fitness combines automatic and manual functions, with flexible prioritization.

2 AUTOMATIC-MANUAL SBST

  • Each search iteration generates an assumption-satisfying input, executes the model, and assesses the resulting fitness value to guide the next input.The framework takes a system model, input assumption, time budget, and requirement as inputs.Source: §2 · pp. 3–4
  • A test case is failure-revealing when its input satisfies the assumption and its fitness is below a threshold, typically zero.Fitness is typically negative when the property is violated and positive otherwise.Source: §2 · p. 4
  • ATheNA returns a failure-revealing test case when found, or an NFF indication if the time budget expires first.The framework repeats its steps until one of those termination conditions is met.Source: §2 · pp. 3–4
  • ATheNA combines automatic and engineer-defined fitness functions, allowing either value to be prioritized or the prioritization policy to change during search.The automatic function is generated from the requirement; the manual function is defined by engineers for system executions.Source: §2 · p. 4

3 AUTOMATIC-MANUAL SBST FOR SIMULINK®

ATheNA-S applies the ATheNA framework to Simulink models whose inputs and outputs are time-varying signals. It combines STL-derived automatic fitness with engineer-defined fitness to guide testing.

3 AUTOMATIC-MANUAL SBST FOR SIMULINK®

  • ATheNA-S generates one time-varying input signal per inport, selecting control-point values within the assumed ranges and interpolating between them.The input assumption specifies each signal’s interpolation function, value range, and number of control points.Source: §3 · p. 6
  • The Simulink simulator executes the model to produce output signals, and fitness assessment can also use input signals when model connections permit.The automatic-transmission example produces Speed, RPM, and Gear outputs.Source: §3 · p. 6
  • ATheNA-S linearly combines automatic and manual fitness using p, which ranges from 0 to 1 and shifts priority toward automatic fitness as p increases.The two functions can also be combined with more complex policies or reprioritized dynamically during search.Source: §3 · pp. 6–7
  • ATheNA-S automatically translates logic-based requirements, such as STL, into fitness values that are negative when the property is violated and positive otherwise.The fitness magnitude reflects relative distance from failing or satisfying the requirement.Source: §3 · p. 7
  • Engineers can define manual fitness functions using simulation inputs, the system model, and input assumptions to target domain-specific regions of the input space.For the automatic-transmission example, a Brake-minus-Throttle function prioritizes high throttle and low brake values when searching for speed-limit violations.Source: §3 · p. 7

4 IMPLEMENTATION

ATheNA-S is implemented as an S-Taliro plugin that reuses its input-generation and execution modules. Its fitness-assessment extension supports requirement-based, manual, and combined fitness functions, with a stop criterion tied to automatic fitness.

4 IMPLEMENTATION

  • ATheNA-S is a Matlab application and Simulink add-on implemented as a plugin for the open-source S-Taliro SBST tool.The authors selected S-Taliro because it was classified as ready for industrial development and had been used in industrial systems.Source: §4 · p. 7
  • ATheNA-S reuses S-Taliro modules for input generation and system execution, while modifying fitness assessment to accept a subclass of its fitness-assessment class.S-Taliro offers multiple search algorithms and uses Matlab’s sim command to run Simulink models.Source: §4 · p. 7
  • The fitness-assessment class defines methods for automatic fitness, manual fitness, their combination, and the condition that stops the search.The automatic method uses S-Taliro’s callTaliro with the execution outputs and requirement.Source: §4 · p. 8
  • For the automatic-transmission example, manual fitness is scaled average brake minus scaled average throttle, prioritizing high throttle and low brake during minimization.The resulting manual fitness ranges from -1 to 1; -1 represents maximum throttle with no brake, while 1 represents the opposite.Source: §4 · p. 9
  • The example ATheNA fitness averages automatic and manual values, while its stopping criterion ends search when automatic fitness falls below zero.The mean keeps the combined fitness within [-1, 1] and equally prioritizes both measures.Source: §4 · p. 9

5 EVALUATION

The evaluation assesses manual and combined fitness-function configurations before comparing ATheNA-S with single-source baselines and testing it on automotive and medical case studies. Its experiments examine failure-revealing test generation and efficiency.

Configuration of ATheNA

  • RQ1 and RQ2 select the manual and combined fitness functions and examine the influence of parameter p on effectiveness.The authors also assess how difficult it is to design manual functions and identify optimal p values for the benchmark models.Source: §5 · p. 11

Comparison with existing SBST frameworks

  • RQ3 compares optimally configured ATheNA-S with automatic-only ATheNA-SA and manual-only ATheNA-SM on failure-revealing test generation.ATheNA-SA corresponds to S-Taliro; the authors use ATheNA-SM as the manual-only baseline because they found no generic manual-fitness Simulink framework.Source: §5 · p. 11
  • RQ4 compares the number of search iterations each tool requires to generate failure-revealing test cases.The comparison uses ATheNA-S's optimal configuration identified in RQ2.Source: §5 · p. 11

Assessment of usefulness

  • RQ5 assesses effectiveness and efficiency on two representative Simulink case studies, one automotive and one medical.The automotive model has an injected fault; the case-study question is not a comparison with other tools.Source: §5 · pp. 11–12

5.1 Benchmark

The benchmark combines seven ARCH Simulink models from varied domains and behavior types with 27 temporal-logic requirements. Tests are generated under specified input assumptions, yielding 39 assumption–requirement combinations.

Benchmark models

  • The benchmark uses seven ARCH models spanning automotive, neural-network, and energy domains, with both discrete and continuous behaviors.The models vary in block, inport, and outport counts; the set includes Toyota's AFC model.Source: §5.1 · p. 12

Requirements

  • The models have 27 STL requirements, of which only CC1 and F16 are invariants.Other requirements scoped by G need not hold at every simulation instant when their time bound is shorter than the simulation.Source: §5.1 · p. 12

Input assumptions

  • Input assumptions specify interpolation, value ranges, and control-point counts, with additional ranges used where tools behaved similarly.Interpolation and control-point settings follow Aristeo's publicly available replication package because the ARCH configuration does not specify them.Source: §5.1 · p. 12, Table 3 · p. 13

Experimental units and metric

  • The benchmark yields 39 assumption–requirement combinations, and tool comparisons use iterations to failure because runtime per iteration reduces to model simulation time.Generating tests and computing manual fitness values take negligible time compared with simulation.Source: §5.1 · p. 13

5.2 Manual Fitness Function Design — RQ1

The authors reverse-engineered benchmark models to design manual fitness functions, then assessed their effectiveness and the effort required for novice subjects to write them. Manual functions produced failure-revealing runs for most tested combinations.

Manual fitness function design

  • The authors designed functions by reverse-engineering each model and targeting input regions they considered critical for each requirement.For AT1, for example, they sought to maximize Throttle and minimize Brake although the requirement constrains Speed.Source: §5.2 · pp. 14–15

Scope of the manual-function results

  • The authors do not know whether their manual functions are the most effective, since they were not model developers and had limited model knowledge.They expect practicing engineers to know their models better.Source: §5.2 · p. 15

Manual fitness function effectiveness

  • 90% (35 out of 39) of the assumption–requirement combinations had at least one failure-revealing run with the designed manual fitness functions.ATheNA-SM was run 50 times per combination, with a 300-iteration maximum. The authors note that the aim is a framework combining manual and automatically generated functions, not a method for helping engineers write manual functions.Source: §5.2 · p. 15, Table 5 · p. 16

Manual fitness function effort

  • In the experiment, two students took approximately 6.1 minutes on average to design manual fitness functions, and at least one proposed an effective function for 5 of 6 assumption-requirement combinations (83%).Source: §5.2 · pp. 15–16

5.3 Influence of ATheNA Fitness — RQ2

Across most benchmark combinations, changing the balance between automatic and manual fitness values affected failure-revealing rates. The best parameter value varied by combination, motivating average and per-combination-best configurations for later experiments.

Method and configurations

  • The experiments tested seven p values across 39 combinations, with 50 runs per combination; the full experiment took about 35 days.The authors define ATheNA-S_avg using the average optimal p and ATheNA-S_best using a best p for each combination.Source: §5.3 · pp. 17, 19

RQ2 results

  • For 18 of the 34 affected combinations (52.9%), the highest failure-revealing rate came from combining automatic and manual fitness values with 0 < p < 1.In other combinations, the highest rate could occur at p = 0, p = 1, or include an endpoint.Source: §5.3 · pp. 17–18
  • 87.2% (34 out of 39) of combinations were affected by parameter p, with rate variation from 2% to 62% runs (avg = 23.6%, sd = 19.2%).For the other five combinations, rates were unchanged across p values: two had 100% failure-revealing runs and three had 0%.Source: §5.3 · pp. 17–19, Table 8 · p. 19

5.4 Effectiveness — RQ3

ATheNA-S generated more failure-revealing runs than either baseline across the benchmark, with gains depending on how its automatic and manual fitness functions were prioritized. The average-priority configuration was at least as effective as both baselines for most combinations, while the tailored configuration matched or exceeded them for all combinations.

5.4 Effectiveness — RQ3

  • The comparison used ATheNA-SA, ATheNA-SM, ATheNA-Savg, and ATheNA-Sbest on 39 assumption-requirement combinations, with each tool's failure-revealing-run percentage evaluated over 50 runs.Source: §5.4 · p. 20
  • ATheNA-Savg matched or exceeded both baselines for 29 of 39 combinations and found failure-revealing tests for CC4 that neither baseline found.Source: §5.4 · p. 20
  • For the 10 combinations where ATheNA-Savg had fewer failure-revealing runs than a baseline, its average decrement was 4.0% versus ATheNA-SA and 10.6% versus ATheNA-SM.The individual decreases ranged from 2% to 24% relative to the best baseline.Source: §5.4 · p. 20
  • ATheNA-Sbest matched or exceeded both baselines for all 39 combinations, averaging 11.9% more failure-revealing runs than ATheNA-SA and 12.1% more than ATheNA-SM.Source: §5.4 · p. 20
  • ATheNA-Savg produced 7.9% more failure-revealing runs than ATheNA-SA and 8.1% more than ATheNA-SM on average across 39 combinations.Table 9 reports failure-revealing-run percentages by tool and assumption-requirement combination.Source: §5.4 · pp. 20–21, Table 9 · p. 21

5.5 Efficiency — RQ4

ATheNA-S's efficiency relative to ATheNA-SA and ATheNA-SM depended on the fitness-priority setting, but the iteration differences were statistically nonsignificant or negligible. The largest reported overhead was small in runtime terms for the most computation-intensive model.

5.5 Efficiency — RQ4

  • The efficiency comparison used iteration counts for failure-revealing runs because per-iteration execution-time differences among the tools were negligible.Source: §5.5 · p. 22
  • For model F16, 12 additional iterations meant less than a minute of runtime because each iteration took 3 seconds.The analysis considered only failure-revealing runs, which included more runs for the more effective average- and best-priority configurations and therefore penalized them in the efficiency comparison.Source: §5.5 · pp. 22–23
  • Across the tested priority settings, iteration differences were statistically nonsignificant or negligible, depending on the value of p.ATheNA-Sbest required a statistically higher median iteration count than either baseline, but differed by at most 12 median and 6.1 average iterations.Source: §5.5 · pp. 22–23, Table 10 · p. 22, Figure 4 · p. 22

5.6 Usefulness — RQ5

ATheNA-S was assessed on an automotive hybrid-electric vehicle model and a medical mechanical-ventilator model. It generated failure-revealing tests in both case studies, including a test exposing a pressure-threshold violation in the ventilator model.

5.6.1 Automotive case study.

  • For the 4,775-block HEV model, the test varied speed demand over 400 seconds and checked whether speed tracking stayed within 3 Kph over the simulation.The test used five control points, smooth pchip interpolation, and a manual fitness function favoring substantial speed-demand changes; after an initial run found no failure, the authors injected a fault by changing the Cruise_mode-to-Accelerate_mode threshold by 50%.Source: §5.6.1 · pp. 23–24
  • With the injected HEV fault, ATheNA-S found a violation in 12 iterations and 199 seconds when speed demand changed substantially during the first five seconds.The vehicle-speed difference exceeded the 3 Kph threshold.Source: §5.6.1 · p. 24, Figure 5 · p. 24

5.6.2 Medical case study.

  • For the 241-block ventilator model, the requirement checked respiratory pressure and lung-volume limits over 30 seconds, while the manual fitness function targeted abrupt breathing changes and high body temperature.The pressure threshold was 30 cmH2O; the input assumptions included muscle pressure, body temperature, and room temperature.Source: §5.6.2 · pp. 24–25
  • ATheNA-S found a ventilator pressure violation in 8 iterations and 452 seconds: abrupt reduction in voluntary breathing led pressure to reach 34.3 cmH2O against the 30 cmH2O threshold.The authors note that the model was a starting point for designers and its developers had not ensured its correctness.Source: §5.6.2 · pp. 25–26, Figure 6 · p. 25

5.6 Usefulness — RQ5

  • ATheNA-S found failure-revealing tests in both case studies: after 12 iterations for the automotive model and 8 for the medical model.The runs took approximately three and seven minutes, respectively.Source: Figure 5 · p. 24, Figure 6 · p. 25, §5.6.2 · p. 26

6 DISCUSSION AND THREATS TO VALIDITY

The discussion presents empirical support for combining automatically generated and manually defined fitness functions, while emphasizing that practical guidance and generalizability remain bounded by the study’s scope.

6 DISCUSSION AND THREATS TO VALIDITY

  • ATheNA-S detected more failure-revealing test cases than the baseline frameworks without significant runtime performance overhead, and generated such cases in the case studies.These conclusions apply to the benchmark models and requirements considered.Source: §6 · p. 26
  • The proposed workflow starts with automatic fitness functions, moves to manual functions if they find no failure-revealing case, and then combines them if needed.The authors describe this as one possible workflow based on their empirical investigation, requiring further evaluation in practice.Source: §6 · p. 26
  • Manual fitness functions are designed around each requirement and relevant model behavior, and a function can be reused across requirements such as CC1 and CC3.ATheNA-SM runs each assumption–requirement combination with the fitness functions associated with that requirement.Source: §6 · p. 26
  • ATheNA-S uses S-Taliro’s STL-to-fitness-function translation and inherits its limitations, while other translations and Test Assessment support are possible extensions.The paper leaves an extensive comparison of alternative translations out of scope and proposes integrating an approach that converts Test Assessment blocks.Source: §6 · pp. 26–27
  • For CC4, combining automatic and manual fitness functions generated failure-revealing test cases that neither approach returned on its own.The paper identifies this as evidence of the complementarity of the two fitness-function types.Source: §6 · p. 27
  • Manual fitness functions improved the search process on the considered benchmark, but did not improve it for NN-R and worsened performance for WT3-R.The authors note that manual functions can worsen search, so the benchmark evidence is not uniformly positive.Source: §6 · p. 27
  • External validity is constrained by model and requirement selection, reverse-engineered fitness functions, and the injected fault; scalability factors and manual-effort evidence also need further study.The effort study involved two subjects, and the authors identify input signals, control points, input ranges, model blocks, and simulation time as factors affecting scalability.Source: §6 · pp. 27–28
  • The experiments found that ATheNA outperformed ATheNA-SA and ATheNA-SM, despite reverse-engineering the models and selecting the combination parameter through the evaluation procedure.The authors argue that engineers who know their models may choose parameter values better suited to development stage and testing priorities.Source: §6 · pp. 28–29

7 RELATED WORK

The related-work review finds no prior classification of automatically generated versus manually defined fitness functions and no framework combining them. ATheNA combines both as a multi-objective fitness function and is evaluated across models and domains.

7 RELATED WORK

  • The authors found no prior classification of automatically generated and manually defined fitness functions or framework combining them.They report reviewing a broad SBST literature and surveys.Source: §7 · p. 29
  • Logic-based specifications commonly underpin automatically generated fitness functions, with temporal-operator values computed through several alternative methods.Options include min/max, smooth distance approximations, interval means, cumulative values, and signal perturbations.Source: §7 · p. 29
  • Manually defined fitness functions cover diverse objectives, including output behavior and signal diversity, reference-signal differences, code coverage, and exploration.Some approaches also combine coverage-based and feature-interaction measures.Source: §7 · p. 29
  • The framework’s benefits were assessed on seven models and 27 requirements, plus two complex automotive and medical case studies.The benchmark includes models spanning different domains.Source: §7 · p. 29
  • ATheNA combines automatic and manual fitness functions as a multi-objective fitness function, with support applicable across different domains.The authors identify enabling engineers to use both types as a significant contribution.Source: §7 · p. 30

8 CONCLUSION AND FUTURE WORK

ATheNA combines automatically generated and manually defined fitness functions, with ATheNA-S supporting Simulink models. Its two versions generated more failure-revealing tests than baseline tools, with no statistically significant efficiency differences.

8 CONCLUSION AND FUTURE WORK

  • ATheNA combines automatically generated and manually defined fitness functions; ATheNA-S is its instance for Simulink models.The authors plan to infer parameter p automatically and dynamically adjust the prioritization of the two fitness-function types at runtime.Source: §8 · p. 30
  • +7.9% and +11.9% failure-revealing test cases versus the automatic-fitness baseline, and +8.1% and +12.1% versus the manual-fitness baseline.The two ATheNA-S versions were preferable for approximately 79% and 100% of assumption-requirement combinations, respectively.Source: §8 · p. 30
  • ATheNA-S showed no statistically significant efficiency differences from baseline tools and generated failure-revealing tests for representative automotive and medical case studies.The case studies were described as large and representative.Source: §8 · p. 30
Loading 2207.11016v2…