软件测试与检验复习2（Structural Testing - Path Testing(Part Ⅰ/Part Ⅱ/Part Ⅲ)）

标签：node 路径 Testing number Part coverage path 节点 软件测试

• Connectedeness, Components and Cyclomatic Number 连通性、组件和循环数

Two nodes are connected if they are on ther same path. 如果两个节点在同一条路径上，它们就是相连的。

A component of a graph is a maximal set of connected nodes. 图的一个组成部分是连接节点的最大集合

• Directed Graphs 有向图

• Indegree(indeg) of a node is the number of distinct edges that have the node as terminal node.节点的入度是以该节点为终端节点的不同边的数量。
• Outdegree(outdeg) of the node is the number of distinct edges that have the node as start node.节点的出度是以该节点为起始节点的不同边的数量。
• source node: A node n with indeg(n)=0;   一个节点n的入度=0。
• sink node: A node n with outdeg(n)=0;  一个节点的出度=0。
• Directed path: Sequence of edges such that for any adjacent pair of edges ei, ej, the terminal node of ej is the start node of ej.

　　　有向路径：　　边的序列，对于任何相邻的一对边ei，ej，ej的终端节点是ej的起始节点。

• Circle: Directed path that begins and ends at the same node. 圆：开始和结束于同一节点的定向路径。
• Chain: Sequence of nodes such that each node ni has indeg(ni)=1 and outdeg(ni)=1 and the source and sink nodes are distinct.

　　　　链： 节点的序列，使每个节点ni的indeg(ni)=1和outeg(ni)=1，并且源节点和汇节点是不同的。

• Maximal chain : A chain that is not conotained in any other chain. 最大链：一个不被任何其他链所包含的链。
• (Directed)semi-path: Sequence of edges such that for at least one adjacent pair of edges ei, ej, the terminal node of ei is the terminal node of ej or the start node of ei is the start node of ej.  (定向)半路径：边的序列，使得至少有一对相邻的边ei，ej，ei的终端节点是ej的终端节点，或者ei的起始节点是ej的起始节点。

• Connectedness between nodes  节点之间的连接性

• 0-Connected: Two nodes n1 and n2 are 0-connected iff no path and no semi-path exists between them.
• 0-连接: 如果两个节点n1和n2之间不存在路径和半路径，则这两个节点是0连接的。

  　 　　                

• 1-Connected:Two nodes n1 and n2 are 1- connected iff a semi-path but no path exist between them.
• 1-连接：两个节点n1和n2是1-连接的，如果它们之间有半路径但没有路径。

　　　　　　　　

• 2-Connected:Two nodes n1 and n2 are 2-connected iff a path exist between them.
• 2-连接: 两个节点n1和n2是2-连接的，如果它们之间存在一条路径。

　　　　　　　　

• 3-Connected:Two nodes n1 and n2 are 3- connected if there is a path from n1 to n2 and a path from n2 to n1. 
• 3-连接: 两个节点n1和n2是3-连接的，如果有一条从n1到n2的路径和一条从n2到n1的路径。

　　　　　　　　

• Strong components and condensation graphs  强成分和凝结图

• A strong component of a directed graph is the maximal set of 3-connected nodes. 一个有向图的强成分是3个连接的节点的最大集合。
• calculate the cyclomatic number V of as strongly connected directed graph G=(V, E) is given by:(must be a strongly connected directed graph)
• 计算强连接有向图G=(V, E)的循环数V的方法是：(必须是强连接有向图)

-V(G) = e - n + p, where 

e is the number of edges in G, e是G中的边的数量,

n is the number of nodes in G,  n是G中的节点数,

p is the number  of components in G, where there is  only one component in G.  p是G中组件的数量，其中G中只有一个组件

• Control flow graph 控制流程图

　　　　　　　　　　　　

　　　　　　　　

• 　Example:

　　　　

• Cyclomatic compelexity of CFGs (CFG图的圈复杂度)

• V(CFG) = V(V , E , s , t ) = e - n + 2
• the number of basis paths = the number of linearly 基础路径的数量=线性路径的数量
• independent paths = cyclomatic compexity  独立路径=循环复杂度

　　　　

 

• Decision to decision paths  决策到决策路径

• Let a number of constructs are collapsed into single nodes known as DD-Paths, it are nodes in a  directed graph that adhere to certain definitions, 5 types of chains: 

   让一些构造被折叠成单一的节点，称为DD-路径，它是有向图中坚持某些定义的节点，5种类型的链:

• • Type 1:  A single node with an in-degree = 0;　　类型1：一个内度=0的单一节点。
  • Type 2:  A single node with an out-degree = 0;　　类型2：一个外度=0的单一节点。
  • Type 3:  A single node with in-degree >=2 or out-degree >=2;　　类型3：一个节点的in-egree>=2或out-egree>=2。
  • Type 4: A single node with in-degree =1 or out-degree =1;      类型4：一个单节点，in-egree=1或out-degree=1。
  • Type 5: It is a maximal chain id length >=1.      类型5：它是一个最大的链id长度>=1。

• Exercise:

Draw the DD-graph for the CFG:

• Coverage Criteria覆盖率标准

• white box test criteria: 白盒测试标准

——  Statement coverage: Every statement is executed at least ones (node coverage)　　-- 语句覆盖率。每条语句至少被执行一次（节点覆盖率）

——  Branch coverage: Every decision is executed at least ones (edge coverage)　　-- 分支覆盖率。每个决策都至少执行一个（边缘覆盖）。 

　　　　　　注： 出度>=2 的都是决策

——  Simple paths coverage: All simple paths are executed　　-- 简单路径覆盖率。所有的简单路径都被执行

——  Visit each loop coverage: Simple paths coverage + all loops are skipped and executed ones.　-- 访问每个循环的覆盖率。简单路径覆盖率+所有循环被跳过并执行1。

——  Basis path coverage: All linear independent path are executed　　-- 基础路径覆盖率。所有线性独立路径被执行

• Statement coverage 语句覆盖

Select a test  set T such that each statement of program P is executed at least once. 选择一个测试集T，使程序P的每个语句至少被执行一次。

• Branch Coverage 边覆盖

• Every program branch is executed at least once  每个程序分支都至少被执行一次
• In terms of flowgraph: find a set of paths such that every edge lies on at least one path  就流程图而言：找到一个路径集，使每条边至少位于一条路径上。

 　　　　　　

• Simple path coverage简单路径覆盖

　　　　Every simple path (which does not contain the same edge more than once) is executed once. 每条简单的路径（不多次包含相同的边）被执行一次

　　　　　　

• Visit each loop coverage 访问每个循环的覆盖

Simple path coverage + additional test cases such that for each loop there is one test case that: 简单的路径覆盖+额外的测试用例检查每一个循环

• • skips the loop entity 跳过该循环实体
  • only makes one pass through the loop  只通过一次循环

　　　　　　

 

• All path coverage: 所有的路径覆盖

If there is at least one circle ,the minimum number of test cases are infinite. 如果至少有一个圆圈，测试用例的最小数量是无限的。

• Basis Paths Coverage: 基本路径覆盖 

Every linearly independent path is executed ai least once 每条线性独立的路径都至少执行一次    即该覆盖每必有至少一条路径在前面没有出现过

minimum number of test cases: 最小的测试案例数量

　　V(G) = e - n + 2 = #decision points + 1(if graph entails binary decision points only)

　　V(G) = e - n + 2 = #决策点 + 1(如果图只涉及到二进制决策点)   注：节点出度>=2此处必为二分

 

 

---

 

 

 

• The baseline method 基准法

  • Systematic approach to determine the set of basis paths. 用系统的方法来确定基础路径集。
  • The method will retuen a minimal set of basis paths 该方法将重建一个最小的基础路径集。
  • Mathematical background:　数学背景:

1. a path p is a linear combination of paths 路径p是路径的线性组合
2. A set of paths is linearly independent iff no path in the set is a linear combination of any other paths in the set.

  一组路径是线性独立的，如果这组路径中没有任何路径是这组路径中任何其他路径的线性组合。

• Prime Decomposition Theorem 主体分解定理

Prime Decomposition Theorem: Any structured program graph can be uniquely decomposed into a hierarchy of sequencing and nesting primes.

主体分解定理: 任何结构化的程序图都可以被唯一地分解为一个排序和嵌套主体的层次结构。

• Primes and their Flowgraphs 主体及其流图

　　　　　

• Prime Decomposition Tree 主体分解树

  • Example： Draw the corresponding prime decomposition tree:

　　　　　　

• Essential complexity and structuredness 基本复杂度和结构化程度

• Essential complexity of a program P with flowgraph G is given by: 带有流图G的程序P的基本复杂度由以下公式给出

ev(G) = v(G) - m

V(G) is the cyclomatic complexity of G ( v(g) = e - n + 2 = decision node number + 1 );　　　　m is the number of sub-flowgraphs in G;

V(G)是G的循环复杂性(v(g)=e-n+2=决策节点数+1)；m是G中子流图的数量。

• Essential complexity of a flowgraph G corresponds to the cyclomatic complexity of the graph obtained by recursively replacing all prime flowgraphs in G by a single node.

流图G的基本复杂度对应于用一个节点递归替换G中所有质数流图所得到的图的循环复杂度。

• P is fully structured iff ev(G) = 1  如果ev(G)=1，P就是完全结构化的 即代码结构极好

　　　　　　 　　　　 

 

• Minimun number  of test cases for primes

• Minimum number of test cases for Sequencing                                                  

　　　

•  Minimum number of test cases for Nesting

  

•   Code coverage of 70-80% is a reasonable goal for system test of most projects with most coverage metrics.
•   70-80% 的代码覆盖率是大多数具有最多覆盖率指标的项目的系统测试的合理目标
•   Empirical studies of real projects found that increasing code coverage above 70-80% is time consuming and therefore leads to a relatively slow bug detection rate
•   对实际项目的实证研究发现，将代码覆盖率提高到 70-80% 以上非常耗时，因此会导致相对缓慢的错误检测率
•   Minimum code coverage for unit testing can be 10-20% higher than for system testing
•   单元测试的最低代码覆盖率可以比系统测试高 10-20%

 

---

 

 

 

  　

　  

 

　　　　　　

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

标签：node,路径,Testing,number,Part,coverage,path,节点,软件测试
From： https://www.cnblogs.com/chen1chen/p/17094505.html