程序不可达路径的检测方法

姚婷

摘要：对于复杂的大型软件，程序中不可达路径存在会浪费软件测试的资源也影响了测试的准确性。通过对程序基本路径集中不可达路径存在的问题进行了研究，提出基于条件语句之间具有的相关性检测不可达路径的方法，通过考察这些条件语句之间的相关性，可以检测不可达路径，生成程序的可達路径集。

关键词：软件测试；不可达路径；条件相关性

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）29-0084-04

Abstract： To complex large-scale software， the inaccessible path in the program will waste resources for software testing and also affect the accuracy of the test. Through the research on the problem of the unreachable path in the basic path of the program， this paper proposes a method based on the correlation between the conditional statements to detect the unreachable path. By examining the correlation between these conditional statements， the unreachable path can be detected. Generate a set of program reachable paths.

Keywords： software testing； unreachable path； conditional correlation

在软件测试中，路径覆盖是一种最常用的测试充分性准则，该准则要求采用合适的方法生成测试用例，以覆盖给定的目标路径。[1]对于给定的目标路径，如果任何输入都不能覆盖该路径，该路径就称为不可达的。研究不可达路径的检测试用例的方法非常重要，若无法明确某且标路径是不可达的，测试者将花费很多计算资源用于寻找覆盖该路径的测试用例，从而浪费宝贵的计算资源[2]；相反，如果已经知道其目标路径是不可达的，测试者就根本不需要寻找覆盖该路径的测试用例，从而能够将有限的计算资源用于寻找覆盖可执行目标路径的测试用例。

鉴于不可达路径产生的主要原因是该路径包含的条件语句之间的相关性，所以，通过考察这些条件语句之间的相关性，可以检测出不可达路径。在此提出基于条件语句相关性的不可达路径自动检测理论与方法，生成程序的可达路径集。

1 已有的研究方法

已有的检测不可达路径的方法有动态法和静态法。动态法难以直接判定某目标路径是不可达的，通常根据试图覆盖某目标路径，所需要的测试用例迭代次数，或者测试用例迭代一定次数时已经覆盖的路径深度等，判定某目标路径是不可达的。[3]容易看出，覆盖某目标路径需要的测试用例迭代次数，除了与该路径的覆盖难度相关之外，还与测试用例的初始位置、采用的迭代方法等密切相关。[4]因此，即使满足设定的迭代终止条件，判定某目标路径是不可达的也往往是不准确的。

静态法检测不可达路径有符号估值法和分支相关性检测法。符号估值法使用符号代替程序的输入变量，得到覆盖目标路径应该满足的条件。缺点是缺乏有针对性的路径覆盖条件信息，难以确定哪个符号对路径覆盖起关键作用。[5]通常得到上述条件需要付出非常大的代价，实用性不高。

2 基于条件语句相关性的不可达路径检测

研究表明，在复杂软件中，有13%-50%的条件语句之间具有某种相关性，[6]而不可达路径产生的主要根源在于该路径包含的条件语句之间具有相关性，因此，通过考察这些条件语句之间的相关性，有可能检测不可达路径。鉴于此，本文通过考察某目标路径包含的条件语句之间的相关性，提出不可达路径的自动检测理论与方法，思想是：将不同条件语句谓词表达式的取值看成随机事件，定义相应的随机变量，并根据这些随机变量取值的概率提出条件语句不同类型相关性的判定定理。上述随机变量取值的概率难以精确得到，且对判定条件语句之间具有的相关性非常重要，因此，可采用数理统计中的极大似然估计方法对其进行估计；基于条件语句之间具有的相关性，自动检测不可达路径。在大量程序测试的实验结果表明，本文提出的方法能够简便且准确地检测程序的全部或绝大部分不可达路径，为程序可达路径集生成奠定了坚实的基础。

可以看出，条件语句相关性的判定，随机变量取值概率的估计及不可达路径的自动检测是本文的关键技术所在。下面将分别详细阐述这些关键技术。

2.1 条件语句相关性

首先定义条件语句之间的相关性，然后提出条件语句相关性的判定定理，并给出该定理的证明过程。

2.1.1 条件语句相关性的定义

记被测程序为G，其输入变量为x1，x2，…，xk，由此构成的输入向量为X=（x1，x2，…，xk）。如果xi的取值域为Di（i=1，2，…，k），则G的取值域为D=D1XD2X…XDk。

定义2.1如果存在X∈D，使得当输入为X时，程序G执行的路径为P，则称路径P为可执行的；否则，如果对于任意X∈D，当输入为X时，G都不能执行P，则称P为不可达的。

考虑路径P的两个条件语句si和sj，如果sj的谓词表达式的取值能够由si谓词表达式的取值确定，则称si和sj是相关的，或者说，条件语句si和sj之间具有相关性。容易知道，对于具有相关性的条件语句对，至少存在一条不可达路径[7]。因此，通过条件语句之间具有的相关性能够检测程序包含的不可达路径。

大部分条件语句之间的相关性难以被及时发现，特别是多个条件语句之间存在相关性时。研究发现，仅有12%的条件语句之间具有的相关性能够在编译阶段被发现。[8]因此，如何准确且高效地判定条件语句之间的相关性是一个非常值得研究的问题。

为便于阐述，首先给出两个条件语句之间相關性的定义，然后将其推广到三个及以上条件语句的情况。

定义2.2 对于两个条件语句si和sj，如果si的谓词表达式取真时，sj的谓词表达式也取真，则称条件语句对（si，sj）具有真-真相关性。类似的，可以给出（si，sj）具有真-假相关性、假-真相关性及假假相关性的定义。

将上述概念进一步推广，能够给出三个及以上条件语句之间的相关性定义。

有了上述定理，当需要检测某程序的不可达路径时，仅需要考查某路径包含的条件语句之间具有的相关性类型。鉴于程序的绝大部分不可达路径都是由语句之间存在相关性造成的，本文方法能够检测程序的全部或绝大部分不可达路径。

2） 循环体中条件语句不可达路径的检测

在实际的程序中，很多条件语句是包含在循环体内的，这使得某条件语句可能会执行多次。[9]对于该类程序，在设定目标路径时，往往仅考虑循环体执行有限次的情况。此时，作如下规定：如果循环次数很少，则将每次循环都作为程序的一部分。如果循环次数很多，可以只考虑循环体执行次数较少时相应条件语句和其他条件语句之间的相关性，具体次数由目标语句的选取情况而定[10]。

3） 不可达路径自动检测步骤

利用条件语句之间具有的相关性自自动检测不可达路径的步骤如下：

步骤1 根据目标路径包含的语句确定需要考查的两（或多）个条件语句。

步骤2 采用2.2节的方法，定义相应的随机变量及条件语句谓词表达式取值的概率。

步骤3 采用2.2节的方法，估计条件语句谓词表达式取值的概率。

步骤4 根据条件语句谓词表达式取值的概率，采用2.2节的方法，考查条件语句之间是否具有相关性。若是，确定相关性类型；否则，转步骤6。

步骤5 根据条件语句之间具有的相关性类型，采用2.1节的方法，确定不可达路径。

3 程序可达路径生成

对使用本文方法检测出的不可达路径，不能简单地剔除，需要对不可达路径进行的分析。若该分支结点出现在复用路径中，通过改变复用路径，使不可达路径变为可达，若未出现在复用路径中，则说明该路径为恒不可达路径，需要把恒不可达路径从基本路径集中剔除，并加以说明。

4 实验结果分析

为评价本文所提方法的性能，选择工业程序进行一系列实验检测工业程序不可达路径的性能。选择4个程序作为被测程序，对于每个被测程序，选择部分子函数进行实验。实验程序中，存在大量的条件语句，且很多条件语句之间具有相关性。表1给出这些被测程序的基本信息。

对于每个被测程序，考查不同条件语句之间具有的相关性，并基于此检测不可

达路径，结果如表2所示。BC（）指i个条件语句之间具有相关性的个数； IBDC（i） 表示通过考查i个条件语句之间具有相关性，检测的不可达径数（i= 2，3.4）；检测率是检测到的不可达径数与不可达路径总数的比。

由表2可知，在四个被测程序中，具有相关性的条件语句大量存在。

对于程序Spacs，存在2个条件语句之间具有相关性的有24 组，存在3个条件语句之间具有相关性的有22 组，存在4个条件语句之间具有相关性的有20 组；其他程序也是如此。基于上述条件语句具有的相关性，对于程序run.spacs，remove，利用本文提出的方法检测到所有不可达路径；尽管程序print 未检测到全部不可达路径，但检测率也高达99.19%。这充分说明本文提出的方法检测不可达路径是很有效的。

5 结束语

本文阐述了基本路径集的生成方法，方法具有通用性。重点介绍了基于条件语句相关性的不可达路径检测的方法，给出了条件语句之间相关性的定义，并建立了相关判定定理。给出基于极大似然估计方法估计条件语句谓词表达式取值概率的方法，证明了基于条件语句之间具有的相关性，自动检测不可达路径的方法的可行性。

参考文献：

[1] 单锦辉，姜瑛，孙萍，软件测试研究进展[J].北京大学学报：自然科学版，2005， 41（1）： 134-145.

[2] 李东，宫云战，软件测试方法综述[J].装甲兵工程学院学报， 2003， 17（2）： 9-13.

[3] 陈蕊，张广梅，李晓维.程序中不可达路径的检测方法[J].计算机工程，2006，32（16） ： 86-88.

[4] 张艳梅，姜淑娟，王庆坛，等.不可达基路径的静态检测方法[J].计算机科学与探索， 2012，6（2） ： 144-155.

[5] Beizer B. Software Testing Techniques [M].India： Dreamtech Press， 2002.

[6] Maiocchi M.Software engineering[J].Future Generation Computer Systems，1991，7（1）：23-29.

[7] Coward P D.A review of software testing[J].Information and Software Technology， 1988， 30（3）： 189-198.

[8] Goldberg A， Wang T.C and Zimmerman D. Applications of feasible path analysis to program testing[J].Proceedings of the 1994 International Symposium on Software Testing and Analysis （ISSTA） ， 1994： 80-94.

[9] 赵云山.基于符号分析的静态缺陷检测技术研究[D].北京：北京邮电大学，2012.

[10] 韩寒，姜淑娟.路径测试中基本路径集自动生成方法的研究[J].微电子学与计算机，2013，30 （1）：104-109.

[通联编辑：梁书]