PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Strategy Generation for Boundary Value Exploration Beyond Numeric Inputs

Sabinakhon Akbarova, Felix Dobslaw, Robert Feldt

arXiv:2608.28230v1cs.SE

TL;DR

Automated BVE has been limited by hand-engineered operators tied to input types and function semantics, leaving non-numeric black-box boundary discovery unaddressed. ABEX replaces those operators with adaptive natural-language strategies generated and selected by specialized LLM agents within a QD search. Across 20 functions, it improves numeric search and fault detection while finding domain-aligned boundaries for all tested non-numeric functions.

  • Problem

    Automated BVE relies on input-type- and function-specific mutation operators, while non-numeric black-box boundary exploration lacks prior automated treatment.

  • Method

    ABEX combines a QD archive with specialized LLM agents that generate, select, refine, and execute reusable natural-language boundary-exploration strategies using execution feedback.

  • Results

    ABEX achieves the highest QD-scores on 10 of 11 numeric functions, finds domain-aligned boundaries across all 10 non-numeric functions, and reaches an 86.2% average mutation score versus 61.9% for SETBVE.

  • Takeaways & Limitations

    Adaptive LLM-guided search extends black-box BVE beyond numeric domains without datatype-specific operators, with boundary quality translating into stronger fault detection.

  • Takeaways & Limitations

    Evaluation remains vulnerable to possible LLM training-data contamination, and proprietary or newly written functions are still needed to fully rule it out.

Abstract

from arXiv · show

Software behavior often changes abruptly at boundaries between input regions, and these transitions are known to be fault-prone. Boundary Value Exploration (BVE) automates boundary discovery by searching for pairs of similar inputs that nevertheless trigger different program behaviors. Existing automated BVE techniques rely on mutation operators hand-engineered for each input type, or even for each function under test, which has confined their use to numeric inputs. We present ABEX, an agentic LLM-based framework that replaces operator engineering with adaptive strategy generation: specialized LLM agents propose, select, and execute boundary-exploration strategies, guided by execution feedback and a quality-diversity (QD) archive. Because strategies are expressed in natural language, they can encode both type-level and function-specific knowledge, and effective strategies can even be stored and reused. We evaluate ABEX in a black-box setting on 20 functions with numeric, string, array, and mixed inputs. On numeric functions, ABEX outperforms a state-of-the-art QD method on 10 of 11 functions, with average QD-scores 11.7x higher. On non-numeric functions, addressed here for the first time in automated black-box BVE, ABEX discovers domain-aligned boundary behaviors for all subjects. Mutation testing shows the discovered boundaries are fault-revealing: with equally sized test suites, ABEX reaches an average mutation score of 86.2% versus 61.9% for the QD baseline, and kills nine times as many hard-to-detect stubborn mutants. An ablation study identifies adaptive strategy generation as the primary driver of these gains.

1. Introduction

ABEX addresses the operator-engineering bottleneck in automated BVE with adaptive, natural-language strategies generated and executed by specialized LLM agents. It extends black-box BVE beyond numeric inputs and reports stronger numeric search and fault-detection results than the baselines.

  • Motivation: Boundary Value Exploration searches for nearby input pairs that trigger different program behaviors at potentially fault-prone transitions.Boundary-focused testing can find defects with relatively few test cases.
  • Research gap: Existing automated BVE depends on mutation operators tailored to input types and often to individual function semantics.This dependency has confined automated BVE largely to numeric inputs.
  • Approach: ABEX represents exploration policies as reusable natural-language strategies that specify what structures to vary and whether to generate or mutate candidate pairs.Strategies can encode type-level and function-specific knowledge, such as email-format transitions.
  • Results: On numeric functions, ABEX outperforms the QD baseline on 10 of 11 functions and achieves an average QD-score 11.7× higher under the same budget.It also achieves an average QD-score 2.8× higher than the single-prompt LLM baseline.
  • Results: ABEX discovers domain-aligned boundary behaviors across all 10 tested non-numeric functions, providing the first reported automated black-box BVE results for such inputs.The non-numeric subjects include string, array, and mixed-input functions.
  • Fault detection: With equally sized test suites, ABEX reaches an average mutation score of 86.2% versus 61.9% for the QD baseline and kills roughly nine times as many stubborn mutants.These results assess whether discovered boundary candidates detect seeded faults.

2. Background and Related Work

Prior BVE methods use objective-based or quality-diversity search, while non-numeric black-box boundary exploration remains unaddressed. ABEX combines QD search with adaptive LLM-generated strategies to broaden this scope.

  • Boundary testing: Boundary analysis targets inputs near transitions between behavioral domains, where faults are more likely to occur.Traditional boundary identification has largely been manual.
  • Boundary discovery: White-box and specification-driven automation can identify boundaries, but depends on internal structure, explicit partitions, or well-defined specifications.These requirements limit applicability when specifications are incomplete or ambiguous.
  • Automated BVE: AutoBVA searches for boundary-inducing pairs by optimizing program derivative, whose larger values indicate sharper behavioral transitions.Program derivative is output distance divided by input distance.
  • Automated BVE: Optimizing only program derivative can favor high-contrast regions, while distance metrics may not capture boundariness consistently across domains.Consequently, lower program-derivative regions may still be informative for testing.
  • Non-numeric inputs: Automated black-box BVE for non-numeric inputs had not previously addressed unknown behavioral partitions.Earlier character and string techniques were manual or white-box.
  • Quality diversity: MAP-Elites maintains diverse elite solutions across behavioral regions, and SETBVE applies this QD formulation to automated BVE.SETBVE uses four descriptors derived from input and output characteristics.
  • LLM-based testing: Most LLM testing approaches use single-shot or fixed prompting without execution feedback, potentially producing redundant, low-quality, or invalid tests.ABEX instead integrates LLM-driven strategy generation with QD search and adaptive exploration.

3. Framework

ABEX separates strategic decisions, tactical strategy construction, and operational execution, using feedback from the search to adapt exploration. Its strategies vary by generation or mutation mode and by access to function context.

  • Architecture: ABEX uses strategic, tactical, and operational layers to decide exploration actions, construct strategies, and execute candidate generation.This separation supports resource allocation and different LLM configurations across layers.
  • Coordinator: The Coordinator chooses whether to repeat the latest strategy, select another pooled strategy, or request a new one.It uses iteration progress, function information, archive updates, and stagnation indicators.
  • Coordinator: When exploration stagnates, the Coordinator can request a strategy targeting a specified mode, type, and search gap.This allows the search to revisit promising strategies or address uncovered behavior.
  • Strategy representation: A strategy is a tuple of mode, type, and ordered natural-language steps that produces candidate input pairs for a function under test.Generation works from scratch, whereas mutation may use an archived input pair.
  • Strategy modes: Generation strategies create pairs from scratch, while mutation strategies modify sampled archive entries to explore nearby input-space regions.Each archive cell stores one pair, and archive cells are sampled uniformly at random.
  • Strategy types: Generic generation uses only input counts and types, whereas context-aware generation additionally uses the function signature and docstring.Context-aware strategies can target domain-specific transitions such as month changes or leap years.
  • Tactical layer: The Ideator selects or proposes a conceptual direction, filtering redundancy and low-yield ideas before full strategy construction.It evaluates expected boundary behavior, specificity, diversity, mode consistency, and likely validity.
  • Tactical layer: The Strategy Generator converts a selected idea into executable natural-language steps with an output format and variation for diverse repeated executions.The resulting procedure is passed to the operational layer.

4. Evaluation

The evaluation tests ABEX across diverse black-box functions, compares it with established and LLM baselines, and measures boundary quality, diversity, and fault detection. It also examines strategy effects, component contributions, model choices, and methodological assumptions.

  • Research questions: Additional analyses examine numeric and non-numeric boundary discovery, strategy characteristics, mutation-based fault detection, and the effects of ABEX components and underlying LLMs.The research questions cover effectiveness, generalization beyond numeric inputs, strategy usage, mutation testing, ablations, and model choice.
  • Subjects: The benchmark covers 20 functions: 10 integer, 5 string, 3 array, and 2 mixed-input functions spanning varied boundary behaviors.Subjects include classifiers, format checkers, string transformations, and array transformations.
  • Metrics: The evaluation measures archive quality and diversity with QD-score, while BC count records occupied archive cells containing boundary candidates.QD-score aggregates fitness values across occupied cells, with program derivative as fitness; BC count uses cells with PD > 0.
  • Baselines and budget: ABEX is compared with SETBVE and a single-prompt LLM baseline using repeated runs and a matched 1000-candidate iteration budget.ABEX uses 100 iterations with 10 candidates each, while SETBVE uses 1000 iterations; both generate 1000 candidate pairs.
  • Fault detection: Mutation testing evaluates mutation scores and stubborn-mutant detection, with stubbornness defined relative to each function’s pooled kill distribution.A mutant is stubborn when it is killed by at most 5% of the test cases that kill the easiest-to-kill mutant.
  • Limitations: The setup does not remove equivalent mutants because reliable identification remains unresolved and manual inspection does not scale to 1,158 mutants across 20 functions.Identical mutant sets across configurations preserve relative comparisons, although equivalent mutants reduce absolute mutation scores.

5. Results

ABEX achieves stronger boundary quality than both baselines on most numeric functions and discovers meaningful, domain-aligned boundaries across string, array, and mixed-input functions. Its strategy mix separates coverage breadth from quality refinement, while mutation testing shows higher fault-detection effectiveness than SETBVE.

  • RQ1: Numeric Boundary Discovery: 18.7 average QD-score gives ABEX the highest score on 10 of 11 numeric FUTs, exceeding single-prompt and SETBVE baselines.The sole exception is bytecount, where SETBVE scores 15.1 versus ABEX’s 10.6.
  • RQ1: Numeric Boundary Discovery: Holm-corrected p < 0.05 and maximal effect sizes (Â12 = 1.00) support ABEX’s advantage over SETBVE on 10 of 11 numeric FUTs.The bytecount exception favors SETBVE, while complexCheck_full shows no significant ABEX versus single-prompt difference.
  • RQ2: Non-numeric Boundaries: ABEX discovers meaningful, domain-aligned string boundaries across all string FUTs, with most boundary types found in 8–10 of 10 runs.For passwordStrength, all five boundary types appear in at least 9 of 10 runs.
  • RQ2: Non-numeric Boundaries: Array and mixed-input FUTs yield structural boundaries in most runs, although rarer error boundaries are less consistent.Examples include normalize’s empty-vs-non-empty boundary at 4/10 runs, binarySearch’s unsorted-array error at 5/10, and tcas’s IndexError boundary at 4/10.
  • RQ3: Strategy Effectiveness: Generic generation leads coverage breadth, while mutation leads quality refinement, and their coordinated use is key to boundary-discovery performance.This division of labor is reported across numeric, string, and array/mixed FUT groups.
  • RQ4: Fault Detection: 86.2% average mutation score versus 61.9% for SETBVE shows that equally sized ABEX suites detect more seeded faults.ABEX scores higher on 8 of 10 numeric FUTs and ties on date and findMiddle; doubling SETBVE candidates raises its average only to 63.7%.

6. Discussion

ABEX extends boundary value exploration beyond numeric inputs through adaptive, LLM-guided strategies, achieving higher-quality boundaries and stronger fault detection than baseline approaches. Its benefits are broad but constrained by compute cost, benchmark scope, descriptor quality, stopping efficiency, and untested strategy transfer.

  • General findings: ABEX extends black-box BVE to heterogeneous inputs without manually engineered mutation operators, finding domain-aligned boundaries across all 10 non-numeric functions.The evaluation covers string, array, and mixed-input functions, in addition to numeric functions.
  • General findings: On 10 of 11 numeric functions, ABEX achieves the highest QD-scores, averaging 2.8× the single-prompt baseline and 11.7× the QD-based search baseline.These comparisons position adaptive, LLM-guided search as a way to extend BVE beyond numeric domains.
  • Adaptive strategy generation: Adaptive strategy generation, rather than model capability alone or fixed-strategy iteration, accounts for the main performance gains.Using the same underlying LLM, single-prompt averages 6.7 QD-score versus 18.7 for ABEX; fixed-strategy ExplorerOnly remains substantially lower on shared functions.
  • Complementarity with optimized QD search: ABEX prioritizes boundary quality over breadth: SETBVE finds 353 versus 62 candidates on average, while ABEX’s mean PD is roughly 150× higher.Approximately 99% of SETBVE candidates have PD < 0.001, so many candidates may represent near-zero-PD equivalence differences rather than strong boundaries.
  • Implications for research and practice: ABEX is best viewed as complementary to SETBVE: it supports non-numeric inputs and higher boundary quality, whereas SETBVE is faster, cheaper, and often broader on numeric search.A suggested numeric hybrid uses SETBVE for broad exploration and ABEX to refine promising regions.

7. Conclusion

ABEX combines quality-diversity search with adaptive LLM-driven strategy generation to explore behavioral boundaries across heterogeneous inputs without manually engineered, datatype-specific operators.

  • ABEX discovers boundaries across heterogeneous input types within a single unified framework.
  • ABEX produces higher-quality boundary candidates than traditional search-based methods and a baseline LLM approach.
  • In numeric domains, ABEX achieves the highest QD-scores on most functions, while non-numeric inputs yield meaningful, domain-aligned boundary behaviors without datatype-specific operators.
  • Mutation testing confirms that ABEX's boundary candidates provide fault-detection capability, including improved detection of hard-to-detect stubborn mutants.
  • Strategy generation expands coverage, while mutation refines boundary quality, indicating complementary roles within ABEX's search process.
Loading 2608.28230v1…