Combining Search-Based and Adaptive Random Testing Strategies for Environment Model-Based Testing of Real-Time Embedded Systems

Muhammad Zohaib Z. Iqbal, Andrea Arcuri, Lionel C. BriandSSBSE 2012 · DOI

TL;DR

This paper introduces a novel hybrid testing strategy that combines evolutionary search and adaptive random testing to improve fault detection in real-time embedded systems (RTES). By intelligently switching between these approaches, the proposed method achieves consistently high success rates across various system and environment characteristics, outperforming individual strategies.

What Problem Does This Paper Address?

Testing real-time embedded systems (RTES) is a significant challenge due to their complexity, the vast number of possible test cases, and the critical nature of their applications. These systems interact with dynamic environments, and missing timing deadlines can lead to severe failures. Traditional testing methods are often insufficient. The authors' previous work introduced an environment model-based testing approach that automatically generates test cases and oracles using simulators. However, the effectiveness of individual testing strategies, like search-based testing (SBT) and adaptive random testing (ART), can vary significantly depending on the RTES and its environment models. This paper aims to bridge this gap by developing a hybrid strategy that leverages the strengths of both SBT and ART to achieve more robust and effective fault detection.

Methods

The core of this paper is the proposed Hybrid Strategy (HS), which combines a (1+1) Evolutionary Algorithm (EA) with Adaptive Random Testing (ART). The strategy begins by using (1+1) EA to generate test cases, guided by an "order function" that heuristically assesses how close a test case is to triggering an error state. This order function considers factors like approach level, branch distance, time distance, and time spent in risky states.

The novelty lies in the adaptive switching mechanism: if the (1+1) EA fails to find "fitter" test cases for a predefined number of consecutive iterations (controlled by a parameter 'n'), the strategy switches to ART. ART then takes over, rewarding test cases based on their diversity rather than just their fitness, aiming to explore different regions of the test space. This switch is crucial because it allows the system to escape potential "fitness plateaus" where EA might get stuck and leverage ART's ability to explore diverse scenarios. The paper empirically investigates different values of 'n' to find an optimal switching point.

Datasets

The authors evaluated their approach using:

  • 13 Artificial Problems (P1-P13): These were developed based on specifications from two industrial RTES and one from existing literature. They were designed to vary environmental model characteristics (e.g., guarded time transitions, loops) to understand their impact on testing strategies. Nine problems were inspired by a marine seismic acquisition system, three by an automated recycling machine, and one by a train control gate system. Each artificial problem had a single error state and manually seeded faults.
  • 1 Industrial Case Study (IC): This was a large and complex marine seismic acquisition system with strict timing deadlines. For this case study, no faults were seeded; the goal was to find existing, real faults.

Key Insights and Ideas

  • Hybridization is Key: Neither pure search-based nor pure random testing is universally superior. Combining them intelligently, with an adaptive switch, leads to more consistent and higher fault detection rates.
  • Escaping Plateaus: Evolutionary algorithms can get stuck in "fitness plateaus" where no improvement is found. Switching to a diversity-focused strategy like ART is an effective way to break out of these plateaus.
  • Environment Matters: The performance of testing strategies is highly dependent on the characteristics of the RTES and its environment models. The hybrid approach aims to mitigate this dependency.
  • Optimal Switching Point: The timing of the switch from EA to ART is critical. Too early, and the EA doesn't have enough time to converge; too late, and the budget for ART might be insufficient. The study identified an optimal range for this parameter.
  • Practicality Over Speed: While the hybrid strategy might be slower in finding faults in some cases compared to ART or RT, its significantly higher success rate and robustness make it a more practical choice for real-world RTES testing.

Key Results

  • RQ1 (Best Configuration): The study found that setting the switch parameter 'n' (consecutive test cases with no improved fitness before switching to ART) to 50 yielded the best average rank and success rate across the artificial problems. Values of 'n' below 50 led to early switching to ART, and values above 200 led to late switching, both negatively impacting performance.
  • RQ2a (Artificial Problems): The best HS configuration (n=50) demonstrated significantly better fault detection than (1+1) EA, ART, and RT. HS achieved an average success rate of 88% for artificial problems, compared to ART (63%), RT (64%), and (1+1) EA (74%).
  • RQ2b (Industrial Case Study): For the industrial case study, HS achieved a 100% success rate, matching ART and RT, and outperforming (1+1) EA. While ART and RT sometimes found faults faster, HS's consistent high success rate made it a robust choice.
  • Robustness: The hybrid strategy's performance was less drastically affected by variations in environment properties compared to the individual strategies.

Limitations and Future Work

  • Artificial Problems: While designed to be representative, the artificial problems may not fully capture the complexity of all real-world RTES.
  • Fault Seeding: Faults were manually seeded in artificial problems. While based on experience, systematic fault seeding techniques could offer broader coverage.
  • Execution Time: The experiments required significant computational resources (around 180 days of CPU time for artificial problems).
  • Future Work: The paper suggests exploring other combinations of search and random testing strategies, investigating different EA variants, and further refining the adaptive switching mechanism. The authors also note that while HS is slower in finding faults in some scenarios, its high success rate makes it practical, and further work could focus on optimizing the speed of fault detection without sacrificing effectiveness.

Summary updated

BibTeX
@inproceedings{iqbal2012combining,
  author = {Muhammad Zohaib Z. Iqbal and Andrea Arcuri and Lionel C. Briand},
  title = {{Combining Search-Based and Adaptive Random Testing Strategies for Environment Model-Based Testing of Real-Time Embedded Systems}},
  booktitle = {SSBSE},
  year = {2012},
  doi = {10.1007/978-3-642-33119-0\_11},
}
Figure