Technical Summary: CoCoMagic for Differential Metamorphic Testing of Autonomous Systems

1. Problem Statement

Autonomous Systems (ASs), particularly Autonomous Driving Systems (ADSs), undergo frequent iterative updates involving model retraining, hyperparameter tuning, and architectural changes. These updates risk introducing unintended behavioral degradations or safety violations that were not present in previous versions. Testing these systems faces three primary challenges:

1. The Oracle Problem: In complex, open-ended environments, defining a ground-truth expected output for every scenario is often infeasible.
2. Scenario Realism: Artificially constructed edge cases may expose weaknesses but often lack practical relevance. Failures in scenarios resembling real-world operational conditions are more critical for safety assessment.
3. Interpretability: When behavioral differences are detected between versions, developers often lack actionable insights into the root causes (e.g., specific environmental factors or interactions) driving these divergences.

Existing search-based testing methods often struggle with computational efficiency in high-dimensional spaces and fail to systematically compare versions to isolate update-induced degradations. Furthermore, standard Differential Testing (DT) identifies output differences but cannot assess safety implications without a test oracle, while standard Metamorphic Testing (MT) addresses the oracle problem but may not efficiently target version-specific divergences.

2. Methodology: CoCoMagic

The authors propose CoCoMagic (Cooperative Co-evolutionary differential and Metamorphic Automated Generator for Interpretable Cases), a framework that integrates Differential Testing, Metamorphic Testing, and Cooperative Co-Evolutionary Algorithms (CCEA) with an interpretability layer.

2.1 Core Framework

CoCoMagic formulates test case generation as a constrained search problem to find pairs of source scenarios ($s$) and metamorphic perturbations ($q$) that maximize the difference in Metamorphic Relation (MR) violations between a reference version ($V_{ref}$) and a test version ($V_{test}$).

• Differential Testing (DT): Compares the outputs of two AS versions under identical inputs to detect behavioral divergences.
• Metamorphic Testing (MT): Addresses the oracle problem by defining MRs—relations between inputs and expected output relationships (e.g., "if a pedestrian appears, speed should decrease"). Violations occur when the output relation does not hold.
• Cooperative Co-Evolutionary Algorithm (CCEA): The search space is decomposed into two co-evolving populations:
  1. Source Scenarios ($P_s$): Represent the initial operating conditions.
  2. Perturbations ($P_q$): Represent transformations derived from MRs (e.g., adding a pedestrian, changing weather).
     Individuals from both populations collaborate to form complete solutions (scenario-perturbation pairs). The fitness of an individual is determined by its best collaboration with members of the opposite population.

2.2 Key Mechanisms

• Fitness Function: The objective is to maximize the absolute difference in MR violation extents between $V_{ref}$ and $V_{test}$:
  $$\text{Diff}(s, q) = | \max(E(s, q, V_{test}), 0) - \max(E(s, q, V_{ref}), 0) |$$
  where $E$ quantifies the extent of MR violation.
• Constrained Search & Realism: To ensure generated test cases are practically relevant, the search is constrained by a set of execution scenarios ($S$) collected from real-world system runs. A dissimilarity metric penalizes solutions that deviate significantly from these realistic scenarios, guiding the search toward operationally plausible conditions.
• Runtime Initialization (RI): The initial population is seeded with scenarios sampled from the execution scenario set $S$, rather than random generation, to accelerate convergence toward realistic failure modes.
• Interpretability (Root Cause Analysis): Post-generation, the authors employ the RuleFit algorithm. RuleFit trains a model on the identified test cases to extract human-readable rules (e.g., "IF speed > 70km/h AND foggy, THEN violation increases"). This explains why the versions diverge, linking specific scenario attributes to the observed behavioral differences.

3. Key Contributions

1. Novel Testing Method: The introduction of CoCoMagic, which uniquely combines MT and DT within a cooperative co-evolutionary framework to specifically target behavioral divergences between AS versions.
2. Realism-Guided Search: The integration of constraints and runtime initialization strategies to ensure generated test cases reflect real-world operational conditions, addressing the "realism gap" in automated testing.
3. Interpretability Integration: The incorporation of a RuleFit-based analysis layer that transforms high-dimensional test results into actionable, human-readable rules for debugging and safety assessment.
4. Empirical Validation: A comprehensive evaluation on an industry-grade ADS (InterFuser) within the Carla simulator, demonstrating superiority over baseline search methods.

4. Experimental Results

The authors evaluated CoCoMagic against Random Search (RS) and a Standard Genetic Algorithm (SGA) using the InterFuser ADS in the Carla simulator.

• Effectiveness (RQ1): CoCoMagic identified significantly more distinct test cases revealing MR violations than baselines. It achieved an average fitness (severity of discrepancy) 53% higher than SGA and 40% higher than RS.
• Efficiency (RQ2): CoCoMagic discovered distinct solutions faster, achieving a 126% improvement in Area Under the Curve (AUC) over SGA and 169% over RS. It also reduced execution time by approximately 17% compared to baselines, partly because it generated fewer invalid (simulator-crashing) scenarios.
• Impact of Constraints and Initialization (RQ3):
  • Applying constraints and Runtime Initialization (RI) significantly improved the Average Execution Distance (AED), making test cases ~50% more similar to real-world execution scenarios.
  • However, this focus on realism resulted in a trade-off: a reduction in the total number of distinct solutions found (up to ~34% reduction with combined RI and constraints) and a slight decrease in the severity of the most extreme edge cases found.
• Interpretability (RQ4):
  • Accuracy: RuleFit achieved accuracy comparable to complex black-box models (Random Forest and GBDT) while producing a compact set of rules (~29 rules vs. thousands of paths in GBDT).
  • Expert Validation: Industrial experts rated the generated rules as highly understandable (average score 4.0/5.0) and useful for prioritizing testing conditions (average score 3.8/5.0).

5. Significance and Claims

The paper claims that CoCoMagic offers an efficient, effective, and interpretable approach for the differential testing of evolving autonomous systems. Its significance lies in:

• Bridging the Oracle Gap: By using MRs, it validates safety properties without needing ground-truth outputs.
• Version-Aware Testing: Unlike previous methods that test a single version, CoCoMagic explicitly optimizes for differences between versions, directly supporting regression testing and update validation.
• Actionable Insights: The interpretability component moves beyond simply flagging failures to explaining the specific conditions (e.g., weather, speed, object proximity) that cause an update to degrade performance, thereby supporting targeted debugging.
• Practical Applicability: The use of constraints ensures that the testing effort focuses on scenarios likely to occur in deployment, increasing the practical value of the testing process for safety-critical systems.

The authors maintain a modest stance, acknowledging that while their method improves realism and efficiency, there is an inherent trade-off between exploring the full breadth of the search space (finding rare, severe edge cases) and focusing on realistic, operationally grounded scenarios. They position CoCoMagic as a tool to support, rather than replace, human judgment in safety assessment.