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!
|
| _version_ | 1866909985567408128 |
|---|---|
| author | Wei, Chao Peng, Xinyi Yan, Yawen Luo, Mao Cai, Ting |
| author_facet | Wei, Chao Peng, Xinyi Yan, Yawen Luo, Mao Cai, Ting |
| 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_05463 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Rethinking Basis Path Testing: Mixed Integer Programming Approach for Test Path Set Generation Wei, Chao Peng, Xinyi Yan, Yawen Luo, Mao Cai, Ting Software Engineering 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. |
| title | Rethinking Basis Path Testing: Mixed Integer Programming Approach for Test Path Set Generation |
| topic | Software Engineering |
| url | https://arxiv.org/abs/2601.05463 |