路径覆盖自动生成技术研究

路径覆盖是路径测试最重要的课题之一。文章给出了ddgraph图的支配树、蕴含树和非限制弧的构造方法,提出了一种基于最小路径测试子集的寻找单个测试路径算法,该算法可有效地生成从入口到出口且覆盖非限制弧的路径子集,并给出了具体的应用实例。     

基于DDGRAPH图的路径覆盖研究

软件测试分为静态分析、路径选择、测试数据生成和动态分析四个阶段,而路径选择的自动生成是软件测试的关键技术之一。路径覆盖是软件测试中一种十分重要的方法,它使程序的每个分支至少执行一次。文中通过对DDGRAPH图的分析,提出了DDGRAPH图中弧的支配树和蕴含树的表示方法,然后给出由支配树和蕴含树确定非限制弧的方法,通过近似最少谓词覆盖策略以确定覆盖所有非限制弧的路径测试子集。     

Finding a minimal set of base paths of a program

An approach to finding a minimal set of base paths of a program is described. The program digraph is reduced to a weighted loopfree graph (WLFG) in which a node represents a subgraph of the program digraph that contains at most one outermost loop of the program. An algorithm for finding a maximal cutset of the WLFG is given such that (1) a maximal cutset does not contain two arcs that lie on a single path of the WLFG, and (2) its capacity is equal to the cardinality of a minimal set of base paths of the program. The algorithm repeatedly finds an eliminable arc and removes it from the WLFG until either the WLFG contains three nodes or no more eliminable arc can be found. An illustration is given for finding a maximal cutset and subsequently a minimal set of base paths.     

Qualified Data Flow Problems

It is known that not aU paths are possible in the run time control flow of many programs. It is also known that data flow analysis cannot restrict attention to exactly those paths that are possible. It is, therefore, usual for analytic methods to consider aU paths. Sharper information can be obtained by considering a recursive set of paths that is large enough to include aUl possible paths, but smaU enough to exclude many of the impossible ones. This paper presents a simple uniform methodology for sharpening data flow information by considering certain recursive path sets of practical importance. Associated with each control flow arc there is a relation on a finite set Q. The paths that qualify to be considered are (essentially) those for which the composition of the relations encountered is nonempty. For example, Q might be the set of all assignments of values to each of several bit variables used by a program to remember some facts about the past and branch accordingly in the future. Given any data-flow problem together with qualifying relations on Q associated with the control flow arcs, we construct a new problem. Considering all paths in the new problem is equivalent to considering only qualifying paths in the old one. Preliminary experiments (with a smaUl set of real programs) indicate that qualified analysis is feasible and substantialy more informative than ordinary analysis.     

分支测试中测试路径用例的简化生成方法

结构性测试是对过程式和面向对象程序都非常有效的测试方法，分支覆盖准则被实践证明是其中性价比最高的一种策略．通过深入研究DD图的性质并分析FTPS算法的不足，提出了一种简便、快捷和适合于大规模程序的非约束边集近似求解算法Find_SemiUE；还给出了基于正（逆）向广度（深度）生成树的分支测试路径用例集的简化生成算法Generate_PathSet，该算法在时间和空间开销上较FTPS算法均有较大提高．此外，所证明的关于DD图的结论也值得借鉴用于该图的更深一步研究．     

On Path Cover Problems in Digraphs and Applications to Program Testing

In this paper various path cover problems, arising in program testing, are discussed. Dilworth's theorem for acyclic digraphs is generalized. Two methods for fmding a minimum set of paths (minimum path cover) that covers the vertices (or the edges) of a digraph are given. To model interactions among code segments, the notions of required pairs and required paths are introduced. It is shown that rmding a minimum path cover for a set of required pairs is NP-hard. An efficient algorithm is given for findng a minimum path cover for a set of required paths. Other constrained path problems are contsidered and their complexities are discussed.     

A Branch-Checking Algorithm for All-Pairs Shortest Paths

We formulate and study an algorithm for all-pairs shortest paths in a network with $n $ nodes and $m $ arcs of positive length. Using the dynamic programming principle of optimality of subpaths the algorithm avoids redundant updates of distance labels. A shortest $v$--$w$ path, say $\langle v, r_{1} , r_{2} , \ldots , r_{k } = w \rangle$ with $k $ arcs ($k \geq 1$), is only then combined with an arc $(w,t) \in A$ to update the distance label of pair $v$--$t$, if $(w,t) $ is present on the shortest $r_{\ell } $--$ t$ path for each node $r_{\ell}$ $(\ell=k- 1 , k- 2, \ldots, 1) $. The algorithm extracts shortest paths in order of length from a data structure and builds two shortest path trees per node, an extra effort of $O(n^{2})$. This way it can execute efficiently only the aforementioned distance updates, by picking the arcs $(w,t)$ out of these trees. The time complexity order per distance update and path extraction is similar as in other algorithms. An implementation with a data structure of heaps is possible, but a bucket-type data structure may be more appropriate. The implied number of distance updates does not exceed $nm_{0}$ ($m_{0}$ being the total number of shortest path arcs), but is frequently much lower. In extreme cases the new algorithm applies $O(n^{2})$ distance updates, whereas known algorithms require $\Omega( n ^{3})$ updates. The algorithm is especially suited for undirected graphs; here the construction of one tree per node is sufficient and the computation times halve.     

A Branch-Checking Algorithm for All-Pairs Shortest Paths

We formulate and study an algorithm for all-pairs shortest paths in a network with $n $ nodes and $m $ arcs of positive length. Using the dynamic programming principle of optimality of subpaths the algorithm avoids redundant updates of distance labels. A shortest $v$--$w$ path, say $\langle v, r_{1} , r_{2} , \ldots , r_{k } = w \rangle$ with $k $ arcs ($k \geq 1$), is only then combined with an arc $(w,t) \in A$ to update the distance label of pair $v$--$t$, if $(w,t) $ is present on the shortest $r_{\ell } $--$ t$ path for each node $r_{\ell}$ $(\ell=k- 1 , k- 2, \ldots, 1) $. The algorithm extracts shortest paths in order of length from a data structure and builds two shortest path trees per node, an extra effort of $O(n^{2})$. This way it can execute efficiently only the aforementioned distance updates, by picking the arcs $(w,t)$ out of these trees. The time complexity order per distance update and path extraction is similar as in other algorithms. An implementation with a data structure of heaps is possible, but a bucket-type data structure may be more appropriate. The implied number of distance updates does not exceed $nm_{0}$ ($m_{0}$ being the total number of shortest path arcs), but is frequently much lower. In extreme cases the new algorithm applies $O(n^{2})$ distance updates, whereas known algorithms require $\Omega( n ^{3})$ updates. The algorithm is especially suited for undirected graphs; here the construction of one tree per node is sufficient and the computation times halve.     

路径测试中基本路径集的自动生成

路径测试是一种重要的白盒测试技术，具有较高的故障覆盖率。基本路径集覆盖了程序中所有语句和分支，该文测试了基本路径集中的路径，在测试资源有限的情况下得到较好的测试效果，并提出了基于图的深度优先搜索的基本路径集的生成方法，该算法采用的生成子路径的方法可以有效地减少路径生成过程中的搜索过程，提高路径生成的效率。 关键词：     

一种路径覆盖自动生成的改进方法

路径覆盖是考察软件测试充分性的一种重要准则，它使程序的每个分支至少执行一次。该文通过对DDGRAPH图的定义及相关概念的分析，对构建DDGRAPH图及支配树、蕴含树、非限制弧的方法进行了改进。通过具体的应用实例对比了改进前后的方法，改进后的方法可以减少生成的路径数，用更少的测试用例发现更多的错误。     

Enumerating message paths for interaction testing of object-oriented systems

MM path is integration artifact of object-oriented systems and is characterized by interleaved sequence of messages and method execution paths. In the context of UML sequence diagrams, an MM path is usually found common in many message paths and concatenation of one MM path with different MM paths results in distinct message paths. Adequate testing of all message paths in UML sequence diagrams implies the coverage of all possible concatenation of constituent MM paths in different object-states, which may not be fully achieved in practical situations. With limited test effort, practitioners are compelled to consider a subset of all message paths in ad-hoc manner or priority basis. It can be possible that the selected paths may not include at least one instance of highly critical MM path, whereas less critical MM paths may have been included with multiple instances. It is, therefore, necessary that the selected message paths would contain one instance of all MM paths and their additional instances as per their priorities. To address this problem, we propose two coverage criteria: all MM paths and prioritized MM paths and an MM path-based coverage model. To obtain such coverage model, we build a graph model called as sequence integration graph from the sequence diagram and thereafter, synthesize MM paths to merge them into a set of connected trees. Further, we capture priority information of the MM paths by means of edge weights and order of concatenation among the MM paths by means of connector edges between the trees. These information captured in the MM coverage model helps to determine effective coverage of the MM paths. Our experimental results substantiate usefulness of our MM path-based coverage model for selecting message paths to satisfy all MM paths and prioritized MM paths coverage criteria in the context of integration testing of object-oriented systems with the limited testing effort.     

Disjoint multipath routing using colored trees

Multipath routing (MPR) is an effective strategy to achieve robustness, load balancing, congestion reduction, and increased throughput in computer networks. Disjoint multipath routing (DMPR) requires the multiple paths to be link- or node-disjoint. Both MPR and DMPR pose significant challenges in terms of obtaining loop-free multiple (disjoint) paths and effectively forwarding the data over the multiple paths, the latter being particularly significant in IP datagram networks.This paper develops a two-disjoint multipath routing strategy using colored trees. Two trees, red and blue, that are rooted at a designated node, called the drain, are formed. The paths from a given source to the drain on the two trees are link- or node-disjoint. The colored tree approach requires every node to maintain only two preferred neighbors for each destination, one on each tree. This paper (1) formulates the problem of colored-trees construction as an integer linear program (ILP); and (2) develops the first distributed algorithm to construct the colored trees using only local information. We demonstrate the effectiveness of the distributed algorithm by evaluating it on grid and random topologies and comparing to the optimal obtained by solving the ILP.     

Using spanning sets for coverage testing

A test coverage criterion defines a set E/sub r/ of entities of the program flowgraph and requires that every entity in this set is covered under some test Case. Coverage criteria are also used to measure the adequacy of the executed test cases. In this paper, we introduce the notion of spanning sets of entities for coverage testing. A spanning set is a minimum subset of E/sub r/, such that a test suite covering the entities in this subset is guaranteed to cover every entity in E/sub r/. When the coverage of an entity always guarantees the coverage of another entity, the former is said to subsume the latter. Based on the subsumption relation between entities, we provide a generic algorithm to find spanning sets for control flow and data flow-based test coverage criteria. We suggest several useful applications of spanning sets: They help reduce and estimate the number of test cases needed to satisfy coverage criteria. We also empirically investigate how the use of spanning sets affects the fault detection effectiveness.     

随机时间依赖网络的K期望最短路径

首先给出了随机时间依赖网络模型，K期望是短路径问题的形式化描述，并针对公交网络推导出到达弧头结点的时刻所服从的概率密度函数，路径期望耗费的计算方法，然后，基于随机一致性假设和胡机优势的概念给出了K期望最短路径问题的理论基础和算法并证明了算法的正确性，最后，给出了公交网络的应用实例和实验结果。     

Efficient circular arc interpolation based on active tolerance control

In this paper, we present an efficient sub-optimal algorithm for fitting smooth planar parametric curves by G¹ arc splines. To fit a parametric curve by an arc spline within a prescribed tolerance, we first sample a set of points and tangents on the curve adaptively as well as with enough density, so that an interpolation biarc spline curve can be with any desired high accuracy. Then, we construct new biarc curves interpolating local triarc spirals explicitly based on the control of permitted tolerances. To reduce the segment number of fitting arc spline as much as possible, we replace the corresponding parts of the spline by the new biarc curves and compute active tolerances for new interpolation steps. By applying the local biarc curve interpolation procedure recursively and sequentially, the result circular arcs with no radius extreme are minimax-like approximation to the original curve while the arcs with radius extreme approximate the curve parts with curvature extreme well too, and we obtain a near optimal fitting arc spline in the end. Even more, the fitting arc spline has the same end points and end tangents with the original curve, and the arcs will be jointed smoothly if the original curve is composed of several smooth connected pieces. The algorithm is easy to be implemented and generally applicable to circular arc interpolation problem of all kinds of smooth parametric curves. The method can be used in wide fields such as geometric modeling, tool path generation for NC machining and robot path planning, etc. Several numerical examples are given to show the effectiveness and efficiency of the method.     

无回路网络中最短路问题的高效算法

无回路网络是一类重要的网络,给出在无回路网络中求解最短路树形图和任意顶点对间最短路的高效算法。该算法将顶点进行重新编号,结合广度优先探索法,从源顶点出发依次搜索每个顶点的所有出弧,并在弧的头部进行权值变换操作,可以得到最短路树形图和任意顶点对间最短路,算法复杂度分别为O(m)和O(m(n-m1/2))。该算法思想简便、复杂度低、易于操作。 关键词：     

一种改进的移动机器人全局路径规划算法

基于移动机器人的安全考虑，提出了一种改进的可视图法。该方法用尽可能远离障碍物的路径表示弧，先确定可能的路径点作为节点，然后考虑可能路径，建立结点间的弧，并用Dijkstra算法求出图中的最短路径。最后通过仿真研究表明，用文章提出的方法规划的路径可以达到或接近最优路径。     

Designing a Fault-tolerant Fully-Chained Combining Switches Multi-stage Interconnection Network with Disjoint Paths

Multi-stage Interconnection Networks (MINs) are designed to achieve fault-tolerance and collision solving by providing a set of disjoint paths. Ching-Wen Chen and Chung-Ping Chung had proposed a fault-tolerant network called Combining Switches Multi-stage Interconnection Network (CSMIN) and an inaccurate algorithm that provided two correct disjoint paths only for some source-destination pairs. This paper provides a more comprehensive and accurate algorithm that always generate correct routing-tags for two disjoint paths for every source-destination pair in the CSMIN. The 1-fault tolerant CSMIN causes the two disjoint paths to have regular distances at each stage. Moreover, our algorithm backtracks a packet to the previous stage and takes the other disjoint path in the event of a fault or a collision in the network. Furthermore, to eliminate the backtracking penalties of CSMIN, we propose a new design called Fault-tolerant Fully-Chained Combining Switches Multi-stage Interconnection Network (FCSMIN). It has similar characteristics of 1-fault tolerance and two disjoint paths between any source-destination pair, but it can tolerate only one link or switch fault at each stage without backtracking. Our simulation and comparative analysis result shows that FCSMIN has added advantages of destination-tag routing, lower hardware costs, strong reroutability, lower preprocessing overhead, and higher fault-tolerance power in comparison to CSMIN.     

Reducing the Height of Independent Spanning Trees in Chordal Rings

This paper is concerned with a particular family of regular 4-connected graphs, called chordal rings. Chordal rings are a variation of ring networks. By adding two extra links (or chords) at each vertex in a ring network, the reliability and fault-tolerance of the network are enhanced. Two spanning trees on a graph are said to be independent if they are rooted at the same vertex, say, r, and for each vertex v neq r, the two paths from r to v, one path in each tree, are internally disjoint. A set of spanning trees on a given graph is said to be independent if they are pairwise independent. Iwasaki et al. [CHECK END OF SENTENCE] proposed a linear time algorithm for finding four independent spanning trees on a chordal ring. In this paper, we give a new linear time algorithm to generate four independent spanning trees with a reduced height in each tree. Moreover, a complete analysis of our improvements on the heights of independent spanning trees is also provided.     

Fractional Path Coloring in Bounded Degree Trees with Applications

This paper studies the natural linear programming relaxation of the path coloring problem. We prove constructively that finding an optimal fractional path coloring is Fixed Parameter Tractable (FPT), with the degree of the tree as parameter: the fractional coloring of paths in a bounded degree trees can be done in a time which is linear in the size of the tree, quadratic in the load of the set of paths, while exponential in the degree of the tree. We give an algorithm based on the generation of an efficient polynomial size linear program. Our algorithm is able to explore in polynomial time the exponential number of different fractional colorings, thanks to the notion of trace of a coloring that we introduce. We further give an upper bound on the cost of such a coloring in binary trees and extend this algorithm to bounded degree graphs with bounded treewidth. Finally, we also show some relationships between the integral and fractional problems, and derive a 1+5/3e≈1.61—approximation algorithm for the path coloring problem in bounded degree trees, improving on existing results. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (wdm) optical networks.