Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.05463 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- Basis path testing is a cornerstone of structural testing, yet traditional automated methods, relying on greedy graph-traversal algorithms (e.g., DFS/BFS), often generate sub-optimal paths. This structural inferiority is not a trivial issue; it directly impedes downstream testing activities by complicating automated test data generation and increasing the cognitive load for human engineers. This paper reframes basis path generation from a procedural search task into a declarative optimization problem. We introduce a Mixed Integer Programming (MIP) framework designed to produce a complete basis path set that is globally optimal in its structural simplicity. Our framework includes two complementary strategies: a Holistic MIP model that guarantees a theoretically optimal path set, and a scalable Incremental MIP strategy for large, complex topologies. The incremental approach features a multi-objective function that prioritizes path simplicity and incorporates a novelty penalty to maximize the successful generation of linearly independent paths. Empirical evaluations on both real-code and large-scale synthetic Control Flow Graphs demonstrate that our Incremental MIP strategy achieves a 100\% success rate in generating complete basis sets, while remaining computationally efficient. Our work provides a foundational method for generating a high-quality structural "scaffold" that can enhance the efficiency and effectiveness of subsequent test generation efforts.