dorsal/arxiv
View SchemaRethinking Basis Path Testing: Mixed Integer Programming Approach for Test Path Set Generation
| Authors | Chao Wei, Xinyi Peng, Yawen Yan, Mao Luo, Ting Cai |
|---|---|
| Categories | |
| ArXiv ID | 2601.05463vv1 |
| URL | https://arxiv.org/abs/2601.05463 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
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.
{
"annotation_id": "e67d378c-1876-41c1-b0bc-f1518dcd3cde",
"date_created": "2026-02-17T05:53:03.793000Z",
"date_modified": "2026-02-17T05:53:03.793000Z",
"file_hash": "56a3e7685669ca8c85ba526c9e228ce537f5c449c49aae3eb00bb5832e0b479c",
"private": false,
"record": {
"abstract": "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.",
"arxiv_id": "2601.05463",
"authors": [
"Chao Wei",
"Xinyi Peng",
"Yawen Yan",
"Mao Luo",
"Ting Cai"
],
"categories": [
"cs.SE"
],
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Rethinking Basis Path Testing: Mixed Integer Programming Approach for Test Path Set Generation",
"url": "https://arxiv.org/abs/2601.05463",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "10a4cebb-f52d-4812-8dd9-b24e1292af63",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}