一种基于分支覆盖的测试数据自动生成算法

通过构造新的程序流图，利用Fibonacci法优化选取路径．为指定的分支生成测试数据。提出了路径测试数据生成代价的概念，并给出了代价的计算方法。当所选路径的分支谓词均为线性表达式时，直接求解线性约束集即可生成测试数据，或判定路径不可行；当分支谓词含有非线性表达式时，利用均差近似导数将非线性函数线性化，通过简单的迭代，亦能容易生成测试数据或判定路径在很大程度上不可行。若所选路径不可行或在很大程度上不可行，则选取新的路径，重复以上过程，直至求出所期望的数据，或无新的路径被选取，给定分支不可达。实例和实验表明，算法可行、有效。

Automatic Test Data Generation Algorithm on Branch Coverage

In order to generate test data for a given branch, a new program flow graph is constructed, and Fibonacci method is used to optimize the path selection. The conception and calculation to path-based test data generation complexity is presented. If all branch predicates on the selected path are linear expression, the linear constrain set is constructed and solved to generate test data, otherwise the path can be determined infeasible. Else, the derivatives of a predicate function is approximated by its divided difference, and the nonlinear function is linearized. The test data can also be generated by simple iteration or the path is determined as likely infeasible. If the selected path is infeasible or likely infeasible, a new path is selected. The process above is repeated until the desired test data is obtained or there is no new path to be selected, and the given branch is infeasible. Example and experiment show that the algorithm is feasible and effective.