基于BPA算法的软件测试方法研究

王绍婷　伦立军

摘 要：在白盒测试中，包括的测试方法有代码检查法、静态结构分析法、静态质量度量法、逻辑覆盖法、基路径测试法等等，而这其中，最为普遍运用测试的方法是基路径测试法。它是在程序控制流图的基础上，分析控制结构的圈复杂度，导出一个基本可执行路径的集合，从而设计并产生测试用例的方法，它拥有着最强壮的覆盖标准。本文从实际出发，理论结合实践，深入研究基路径测试的概念、定义、理论，并设计出一个新的基路径算法BPA算法获取基路径，并给出一个案例研究证明该算法的有效性。

关键词：软件测试；基路径；BPA

中图分类号：TP311 文献标识号：A 文章编号：2095-2163（2014）06-

Abstract： There are some testing methods in white box testing such as code inspection， static structure analyzing， static quality measurement， logical coverage， basis path testing. The method of basis path testing has been widely used among those. Based on the program control flow graph， the method analyzes the cyclomatic complexity of control structure， derives the set of basis executable paths， and finally， devises and generates the test cases. It is the strongest coverage criterion. The paper proceeds from the actual situation， bonding the theory and practice， researching deeply the concept， definition and theory of basis path testing. Thus， propose a new strategy BPA to obtain the basis testing paths. As a result， give a case study to show the efficiency.

Key words： Software Testing； Basis Path； BPA

0 引言

随着软件产业的兴盛发展，软件系统的设计规模与复杂程度正在与日俱增，并且软件的生产成本也将随之而一路走高；连带性地，在软件系统中暗存的bug所可能造成的损失也已不可小视，甚至可能发生灾难性的后果。有鉴于此，软件产品作为人脑高度智力化的精粹与明证，而且正是基于这一特殊重要性，就是的软件产品的质量得到了学界广泛的重视与研究。

软件质量就是软件的生命。为了保证软件产品的质量，人们在长期的开发过程中累积了大量经验和有效方法。虽然如此，也只能尽量减少软件中的错误与不足，却未能完全避免软件系统中不再有bug。

针对以上状况，软件测试即应运而生。测试就是检查软件质量，排除软件故障的最有效和完备的技术手段与方法，并由此推进了软件测试理论在现实应用中的蓬勃发展。其中，运用最为广泛的就是基路径测试法[1]。

1 基路径测试

基路径测试方法是在程序控制流图的基础上，通过分析控制构造的圈复杂度[2]，以导出基本可执行路径的集合，从而设计出测试用例的方法。基路径测试的实现步骤如下[3]：

（1）程序控制流图。根据程序内容，画出程序控制流图[4]。

（2）程序圈复杂度。计算程序的环路复杂性，导出程序基路径集合中的独立路径数，这是确定程序中每个可执行语句至少执行一次所必须的测试用例数目的上界。

（3）导出测试用例。根据圈复杂度和程序结构设计用例数据输入和预期结果。

（4）准备测试用例。确保基路径集合中的每一条路径的执行。

2 一个新的基路径算法BPA

运用基路径测试法（三种方式）计算从结点1到结点13的基路径数为6；运用新提出的算法也找到了6条基路径，且路径相同，证明了新算法的有效性、正确性、完备性。

4 结束语

基路径测试是白盒测试中应用最普遍的技术，利用圈复杂度计算独立路径数目，即能保证测试的完备性。本文正是以此为基础，设计了一个新的算法来实现基路径集合的获取，找到所有独立的基路径，旨在以使程序达到合理有效地覆盖测试，下一步工作将考虑研发基路径覆盖工具，并结合遗传算法实现基路径集合的获取，再与测试工具[6]进行性能上的比较分析。

参考文献：

[1]杜庆峰，肖潇.基本路径测试技术研究[J].信息与电脑（理论版），2010，（6）：129-130.

[2]肖自乾，王弗雄，陈经优. 基本路径测试方法之圈复杂度计算[J].软件导刊，2009，8（7）：10-12.

[3]贾晓强. 基于白盒测试的基本路径测试[J].渭南师范学院学报，2008，23（2）：71-73

[4]解圣霞.基于基本路径测试的程序图自动生成的应用研究[J].通化师范学院学报，2009，30（12）：32-35.

[5]GHIDUK A S. Automatic generation of basis test paths using variable length genetic algorithm[J]. Information Processing Letters，2014，114（6）：304-316.

[6]单锦辉，王戟，齐治昌，等. 面向路径的测试数据自动生成工具的设计与实现[J].计算机工程与科学，2002，24（1）：103-107.