基于UIO测试序列的错误诊断算法

唯一输入输出(Unique Input Output)测试序列是协议测试中常用的一种测试序列,在一个已有的错误诊断算法基础上,结合UIO测试序列的一些特点,该文提出了一种应用于UIO测试序列的错误诊断算法。该算法充分利用了UIO测试序列给出的判定消息,及测试结果中可能的错误转换后的输入/输出消息,从而能高效完全地诊断单个错误。最后用实验数据给出了该文算法和原始算法之间的比较结果。     

Structural analysis of protocol specifications and generation ofmaximal fault coverage conformance test sequences

A theoretical analysis of the fault coverage of conformance test sequences for communication protocols specified as finite state machines is presented. Faults of different types are considered, and their effect on testing is analyzed. The interaction between faults of different categories and the impact it has on conformance testing is investigated. Fault coverage is defined for the testing of both incompletely-specified machines (ISMs) and completely-specified machines (CSMs). An algorithm is presented to generate test sequences with maximal fault coverage for the testing of ISMs. It is then augmented for the testing of CSMs, and finally a technique is presented for generating test sequences which provides guaranteed maximal fault coverage for the conformance testing of communication protocols     

Probabilistic testing of OSI protocols

Protocols are large and complex software systems. Complete conformance testing of an implementation against its standard may not be feasible in terms of the resources available. This paper discusses a new approach, the P-method, to the testing of meaningful subsets of communication protocols for an asynchronous model of communication. The approach is based on the probabilistic verification of protocols, which is carried out on the more probable part of the protocol first. The technique can be used for generating probabilistic test sequences for the conformance testing of communication protocols to standards. The proposed method yields meaningful protocol test sequences which test the most probable behaviors of a protocol when the testing of the complete protocol is not feasible. Probabilistic test sequences can be categorized into different classes. The higher the class a probabilistic test sequence is in, the larger the extent of the protocol it covers, and the better is the fault coverage. If the class of a test sequence is high enough, its fault coverage is comparable to the fault coverage of test sequences generated by other methods. Results from a study of the P-method, using alternating bit protocol (ABP) and a subset of NBS TP4 as examples, support the claims above. It can also be shown that if errors are introduced only to the more probable part of the protocol, the fault coverage of P-method is also comparable to other methods     

Synchronizable test sequences based on multiple UIO sequences

A test sequence generation method is proposed for testing the conformance of a protocol implementation to its specification in a remote testing system where both external synchronization and input/output operation costs are taken into consideration. The method consists of a set of transformation rules that constructs a duplexU digraph from a given finite state machine (FSM) representation of a protocol specification; and an algorithm that finds a rural postman tour in the duplexU digraph to generate a synchronizable test sequence utilizing multiple UIO sequences. If the protocol satisfies a specific property, namely, the transitions to be tested and the UIO sequences to be employed form a weakly-connected subgraph of the duplexU digraph, the proposed algorithm yields a minimum-cost test sequence. X.25 DTE and ISO Class 0 transport protocols are shown to possess this property. Otherwise, the algorithm yields a test sequence whose cost is within a bound from the cost of the minimum-cost test sequence. The bound for the test sequence generated from the Q.931 network-side protocol is shown to be the cost sum of an input/output operation pair and an external synchronization operation     

基于改进FSM的协议一致性测试方法

介绍了一种基于FSM(finite state machine)的生成一致性测试序列的改进算法,该方法混合了UIO(unique input/output)方法和T方法,UIO方法的测试能力优于T方法,但是生成的测试序列的长度较后者要长一些。实验结果表明,本改进方法的能力与UIO方法相同,并且测试序列的长度接近于T方法。     

Protocol conformance testing using multiple UIO sequences

Automatic generation of conformance test sequences for communication protocols by means of unique input/output (UIO) sequences is addressed. It is shown that if multiple minimum-length UIO sequences are computed for each state of the finite-state-machine (FSM) specification, then the length of the resulting test sequence is significantly reduced without an appreciable increase in the time needed to compute the sequence. An algorithm for assignment of the multiple UIO sequences is given. This algorithm, which is based on network flow, is polynomial in the number of states and transitions of the FSM and is effective in reducing the overall length of the test sequence     

On the generation of minimal-length conformance tests forcommunication protocols

A technique for generating a test sequence for conformance testing of communication protocols is presented. This approach shows that it is possible to generate optimal-length test sequences which include multiple unique input/output (UIO) sequences and overlapping under certain conditions. In the absence of the above-mentioned conditions, a heuristic technique is used to obtain suboptimal solutions which show significant improvement over optimal solutions without overlapping. The technique is illustrated by the example of the NBS Class 4 Transport Protocol (TP4). The computational complexity of the algorithm is compared with that of previous techniques. A brief discussion of bounds on test sequence length is presented, and the results are compared with these bounds     

Efficient computation of unique input/output sequences in finitestate machines

This paper makes two contributions toward computing unique input/output (UIO) sequences in finite-state machines. Our first contribution is to compute all UIO sequences of minimal lengths in a finite-state machine. Our second contribution is to present a generally efficient algorithm to compute a UIO sequence for each state, if it exists. We begin by defining a path vector, vector perturbation, and UIO tree. The perturbation process allows us to construct the complete UIO tree for a machine. Each sequence of input/output from the initial vector of a UIO tree to a singleton vector represents a UIO sequence. Next, we define the idea of an inference rule that allows us to infer UIO sequences of a number of states from the UIO sequence of some state. That is, for a large class of machines, it is possible to compute UIO sequences for all possible states from a small set of initial UIOs. We give a modified depth-first algorithm, called the hybrid approach, that computes a partial UIO tree, called an essential subtree, from which UIO sequences of all possible states can be inferred. Using the concept of projection machines, we show that sometimes it is unnecessary to construct even a partial subtree. We prove that if a machine remains strongly connected after deleting all the converging transitions, then all of the states have UIO sequences. To demonstrate the effectiveness of our approach, we develop a tool to perform experiments using both small and large machines     

UIO序列优化搜索算法的研究

UIO序列是对有限状态机进行功能测试的有效手段,在VLSI、通信协议等时序系统中有很强的实际应用背景.本文基于可区分状态组这一概念设计了一个搜索算法,进一步利用搜索信息建立了一个基于"小于"关系的启发策略,有效的剪枝策略的设计将尽可能消除没有意义的搜索分枝,新设计出的多路OPEN/CLOSED表存储机制也加快了相关的判别、处理过程.根据实验结果,分析了优化措施对于改进了搜索过程、减少搜索信息的产生、提高搜索速度有显著的贡献.该算法与以往的算法相比,在时间复杂度和空间复杂度两方面都得到了很大改进.     

RTL DFT Techniques to Enhance Defect Coverage for Functional Test Sequences

Functional test sequences are often used in manufacturing testing to target defects that are not detected by structural test. However, they suffer from low defect coverage since they are mostly derived in practice from existing design-verification test sequences. Therefore, there is a need to increase their effectiveness using design-for-testability (DFT) techniques. We present a DFT method that uses the register-transfer level (RTL) output deviations metric to select observation points for an RTL design and a given functional test sequence. Simulation results for six ITC′99 circuits show that the proposed method outperforms two baseline methods for several gate-level coverage metrics, including stuck-at, transition, bridging, and gate-equivalent fault coverage. Moreover, by inserting a small subset of all possible observation points using the proposed method, significant fault coverage increase is obtained for all benchmark circuits.     

一种基于存储器故障原语的March测试算法研究

研究高效率的系统故障测试算法,建立有效的嵌入式存储器测试方法,对提高芯片良品率、降低芯片生产成本,具有十分重要的意义.从存储器基本故障原语测试出发,在研究MarchLR算法的基础上,提出March LSC新算法.该算法可测试现实的连接性故障,对目前存储器的单一单元故障及耦合故障覆盖率提升到100%.采用March LSC算法,实现了内建自测试电路(MBIST).仿真实验表明,March LSC算法能很好地测试出嵌入式存储器故障,满足技术要求.研究结果具有重要的应用参考价值.     

基于扫描链结构重组的低功耗BIST方案

设计了一种改进扫描链结构的内建自测试(BIST)方案.该方案将设计测试序列发生器(TPG)中合适的n状态平滑器与扫描链的重新排序结合起来,从而达到低功耗测试且不致丢失故障覆盖率的目的.通过对15位随机序列信号的测试,发现此TPG中的n状态平滑器在降低功耗的同时还减小了故障覆盖率,遂又设计了重组扫描链的结构来解决这一问题.实验结果表明,该设计方案对于降低平均测试功耗和提高故障覆盖率都具有显著的效果.     

Hardware Generation of Random Single Input Change Test Sequences

The combination of higher quality requirements and sensitivity of high performance circuits to delay defects has led to an increasing emphasis on delay testing of VLSI circuits. As delay testing using external testers requires expensive ATE, built-in self test (BIST) is an alternative technique that can significantly reduce the test cost.It has been proven that Single Input Change (SIC) test sequences are more effective than classical Multiple Input Change (MIC) test sequences when a high robust delay fault coverage is targeted. It has also been shown that random SIC (RSIC) test sequences achieve a higher fault coverage than random MIC (RMIC) test sequences when both robust and non robust tests are under consideration; the experimental results were based on a software generation of RSIC sequences that are easily generated.Obviously, a hardware RSIC generation providing similar results can be obtained. However, this hardware generator must be carefully designed. In this paper, it is explained what are the criteria which must be satisfied for this purpose. A solution is proposed and illustrated with an example. Then, it is shown that a bad result may be obtained if one of these criteria is not satisfied.     

An optimization technique for protocol conformance test generationbased on UIO sequences and rural Chinese postman tours

A method for generating test sequences for checking the conformance of a protocol implementation to its specification is described. A rural Chinese postman tour problem algorithm is used to determine a minimum-cost tour of the transition graph of a finite-state machine. It is shown that, when the unique input/output sequence (UIO) is used in place of the more cumbersome distinguishing sequence, both the controllability and observability problems of the protocol testing problem are addressed, providing an efficient method for computing a test sequence for protocol conformance testing     

1T1R结构RRAM的故障可测性设计

阻变随机存储器(RRAM)中存在的故障严重影响产品的可靠性和良率.采用精确高效的测试方法能有效缩短工艺优化周期,降低测试成本.基于SMIC 28 nm工艺平台,完成了1T1R结构的1 Mbit RRAM模块的流片.详细分析了测试中的故障响应情况,并定义了一种故障识别表达式.在March算法的基础上,提出针对RRAM故障的有效测试算法,同时设计了可以定位故障的内建自测试(BIST)电路.仿真结果表明,该测试方案具有占用引脚较少、测试周期较短、故障定位准确、故障覆盖率高的优势.     

Combining GAs and Symbolic Methods for High Quality Tests of Sequential Circuits

A symbolic fault simulator is integrated in a Genetic Algorithm (GA) environment to perform Automatic Test Pattern Generation (ATPG) for synchronous sequential circuits. In a two phase algorithm test length and fault coverage as well are optimized. Furthermore, not only the Single Observation Time Test Strategy is supported, but also test patterns with respect to the Multiple Observation Time Test Strategy are generated. However, there are circuits that are hard to test using random pattern sequences, even if these sequences are genetically optimized. Thus, deterministic aspects are included in the GA environment to improve fault coverage. Experiments demonstrate that both a priori time consuming strategies, the symbolic simulation approach and the GA, can be combined at reasonable costs: Tests with higher fault coverages and considerably shorter test sequences than previously presented approaches are obtained.     

一种并行内建自诊断测试嵌入式SRAM方案

本文提出了具有自诊断功能的位定向MARCH-TB算法和字定向MARCH-TBW算法，并且在这两个算法的基础上提出并行测试结构来实现了嵌入式内存的测试和诊断。实验结果表明，此测试算法具有故障覆盖率高，诊断故障能力强，测试需要的时间少等优点。     

基于March C＋算法的SRAMBIST设计

为了增加存储器测试的可控性和可观测性,减少存储器测试的时间和成本开销,在此针对LEON处理器中的32位宽的SRAM进行BIST设计。采用MarchC＋算法,讨论了SRAM的故障模型及BIST的实现。设计的BIST电路可以与系统很好的相连,并且仅增加很少的输入／输出端口。仿真结果证明,BIST的电路的加入在不影响面积开销的同时,能够达到很好的故障覆盖率。     

A technique to generate feasible tests for communications systems with multiple timers

We present a new model for testing real-time protocols with multiple timers, which captures complex timing dependencies by using simple linear expressions involving timer-related variables. This new modeling technique, combined with the algorithms to eliminate inconsistencies, allows generation of feasible test sequences without compromising their fault coverage. The model is specifically designed for testing to avoid performing full reachability analysis, and to control the growth of the number of test scenarios. Based on extended finite state machines, it is applicable to languages such as SDL, VHDL, and Estelle. The technique models a realistic testing framework in which each I/O exchange takes a certain time to realize and timers can be arbitrarily started or stopped. A software tool implementing this technique is used to generate test cases for the US Army wireless standard MIL-STD 188-220.     

A bitstream readback-based automatic functional test and diagnosis method for Xilinx FPGAs

In this paper, a novel bitstream readback-based test and diagnosis method including a bitstream parsing algorithm as well as a corresponding bitstream readback-based fault and diagnosis algorithm for Xilinx FPGAs is presented. The proposed method can be applied to both configurable logic block (CLB) and interconnect resource (IR) test. Further, the algorithm is suitable for all Virtex and Spartan series FPGAs. The issues such as fault coverage, diagnostic resolution, I/O numbers, as well as configuration numbers not addressed well by some previous works can be solved or partly relieved. The proposed method is evaluated by testing several Xilinx series FPGAs, and experimental results are provided.