An asynchronous message-passing program P is nondeterministic. Given the same input, multiple executions of P may exercise different send/receive event sequences (or SR-sequences) and may even produce different results. Such nondeterminacy makes it difficult to determine the correctness of P. Let X be an input of P. Assume that any execution of P with X terminates. Reachability testing of P with X is to execute, in a systematic manner, all possible SR-sequences of P with X such that the correctness of P with X can be determined. The basic idea of reachability testing is described as follows. We first execute P with X nondeterministically to collect one or more SR-sequences. For each collected SR-sequence, we analyze its race conditions and generate race variants, which are prefixes of other SR-sequences. We replay race variants to generate new SR-sequences. For each new SR-sequence, we repeat the same process until we eventually execute all possible SR-sequences of P with X. We describe an efficient implementation of reachability testing of asynchronous message-passing programs. Our technique deals with partially-ordered SR-sequences and reduces the complexity and redundancy caused by totally-ordered SR-sequences.

Existing reachability analysis techniques for asynchronous message-passing programs assume causal communication, which means that messages sent to a destination are received in the order they are sent. In this paper, we present a new reachability analysis approach, called blocking-based simultaneous reachability analysis (BSRA). BSRA can be applied to asynchronous message-passing programs based on any communication scheme. From a global state g, BSRA allows processes to proceed simultaneously until each of them terminates or is ready to execute a receive operation. Global states reached by such executions from g are called next blocking points of g. For each next blocking point of g, waiting messages and receive operations are matched to produce immediate BSRA-based successor states of g. Intermediate global states from g to each of g's immediate BSRA-based successors are not saved. We describe an algorithm for generating BSRA-based reachability, graphs and show that this algorithm guarantees the detection of deadlocks. Our empirical results indicate that BSRA significantly reduces the number of states in reachability graphs. Extensions of BSRA for partial order reduction and model checking are discussed.

We present a method for selecting test sequences for concurrent programs from labeled transitions systems (LTS). A common approach to selecting test sequences from a set of LTSs is to derive a global LTS, called the reachability graph, and then force deterministic program executions according to paths selected from the graph. However, using a reachability graph for test path selection introduces a state explosion problem. To overcome this problem, a reduced graph can be generated using incremental reachability analysis, which consists of repeatedly generating a reachability graph for a subset of LTSs, reducing this graph, and using the reduced graph in place of the original LTSs. Unfortunately, existing incremental reachability analysis techniques generate reduced graphs with insufficient information for deterministic testing. We present an incremental approach to testing concurrent programs. Incremental testing consists of incremental reachability analysis for test path selection and deterministic testing for test execution. We define a new type of reachability graph for incremental analysis, called an annotated labeled transition system (ALTS). An ALTS is an LTS annotated with information necessary for deterministic testing. We propose practical coverage criteria for selecting tests paths from an ALTS and present an ALTS reduction algorithm. The results of several case studies are reported.

Pairwise testing is a specification-based testing criterion which requires that for each pair of input parameters of a system, every combination of valid values of these two parameters be covered by at least one test case. The authors propose a novel test generation strategy for pairwise testing.

P. Godefroid (1997) developed a state-space exploration technique that does not store states in memory. This stateless search technique is effective for testing concurrent programs. It performs deterministic executions of a concurrent program by automatically controlling the execution of synchronization operations. This technique also uses partial order reduction methods to reduce the chance of executing two or more different totally-ordered paths with the same partial order. In this paper, we propose extensions to Godefroid's technique and compare it with other stateless search techniques for testing concurrent programs. Our empirical results indicate that a combination of stateless searching and a simple cycle prediction method is very cost-effective for detecting deadlocks and violations of assertions.

Deadlocks are a common type of fault in distributed programs. To detect deadlocks in a distributed program P, one approach is to construct the reachability graph (RG) of P, which contains all possible states of P. Since the size of RG(P) is an exponential function of the number of processes in P, the use of RGs for deadlock detection has limited success. The authors present an efficient technique for deadlock analysis of client/server programs with two-way communication, where the server and clients communicate through channels supporting synchronous message-passing. We consider client/server programs in which the server saves the IDs of some clients for future communication. For such a program, we describe how to construct its abstract client/server reachability graph (ACSRG), which contains a significantly smaller number of global states than the corresponding RG. One example is that for a solution to the gas station problem with one pump and six customers, its RG has 25394 states and its ACSRG 74 states. We show that the use of ACSRGs not only greatly reduces the effort for deadlock analysis but also provides a basis for proving freedom from deadlocks for any number of clients.

Simultaneous reachability analysis (SRA) is a recently proposed technique to alleviate the state space explosion problem in reachability analysis of concurrent systems. Its goal is to reduce the number of generated states while guaranteeing the detection of certain types of faults in the system such as deadlock and unexecutable transitions. The main idea of SRA is to allow a global transition in a reachability graph to contain a set of local transitions (i.e. transitions of individual processes) such that the state reached by the global transition is independent of the execution order of the associated local transitions. In this paper, we show how to apply the SRA approach to systems modeled as extended finite state machines (EFSM) with multiple ports. Empirical results from applying our SRA algorithm to the dining philosophers problem indicate that our algorithm reduces the number of generated states and the computation time by about 90%.

Deadlocks are a common type of fault in distributed programs. To detect deadlocks in a distributed program P, one approach is to construct the reachability graph (RG) of P, which contains all possible states of P, and analyze the RG to detect deadlocks. Since the size of RG(P) is an exponential function of the number of processes in P, the use of RG for deadlock detection has limited success. In this paper, we show an efficient technique for deadlock analysis of client/server programs. We present a theory of deadlock analysis of client/server LTS systems, in which a server or client is represented as a labeled transition system (LTS). For a client/server LTS system, we define its client/server reachability graph (CSRG), which has its size being a polynomial function of the number of clients. We show that the use of CSRG not only significantly reduces the effort for deadlock analysis but also provides a basis for proving freedom from deadlock for any number of clients.

Algorithms for vector timestamps have been developed to determine the "happened before" relations between events of an execution of a message passing program. Many message passing programs contain variables shared by multiple processes (including threads). Such programs need to have vector timestamps for send, receive, read and write events. We define two "happened-before" relations, called strong happened-before (SHB) and weak happened-before (WHB), between events of an execution involving send, receive, read and write statements. We then present two timestamp assignment algorithms, one for SHB and the other for WHB, and show how to use such timestamps to determine the SHB or WHB relation between any two events of an execution involving send, receive, read and write statements. For a program containing n processes, the size of a vector timestamp for SHB or WHB is n, regardless of the number of shared variables in the program. Finally, we show how to apply WHB timestamps to perform race analysis for programs using messages and shared variables.

One major problem in inter class integration testing of object oriented software is to determine the order in which classes are tested. This test order, referred to as inter class test order, is important since it affects the order in which classes are developed, the use of test stubs and drivers for classes, and the preparation of test cases. The paper first proposes a number of desirable properties for inter class test order and then presents a new inter class test order strategy. In this new strategy, classes are integrated according to their major and minor level numbers. Major level numbers of classes are determined according to inheritance and aggregation relations between classes, where an aggregation relation refers to a class' inclusion of objects of another class. For classes with the same major level number, their minor level numbers are determined according to association relations between these classes, where an association relation refers to a class' dependency (other than inheritance and aggregation relations) on another class.

An execution of a message-passing program is nondeterministic if message races exist. In this paper, a formal definition of a message race for asynchronous communication is presented. The trace of an execution of a message-passing program is a sequence of send and receive events. For a receive event r in a trace T, its race set is the set of messages in T that have a race with the message received at r and can be received at r during some possible executions of the same program with the same input. A race analysis algorithm analyzes a trace to determine the race set for each receive event in the trace. Three race analysis algorithms are given for three different types of sequences of send and receive events. It is shown that these race analysis algorithms can be used to solve a number of problems in testing and debugging message-passing programs.

We propose a new technique for automatic generation of test cases for predicates. Earlier we proposed an efficient and effective test generation strategy for Boolean expressions. We now extend this strategy to predicates. Our new strategy addresses a number of issues, including: analysis of dependencies between relational expressions in a predicate P; generation of test constraints for P based on the detection of Boolean and relational operator faults in P; and generation of actual tests according to the generated test constraints for P. We propose the use of constraint logic programming (CLP) to automate test data generation for a predicate. Furthermore, we propose an incremental approach to apply CLP techniques to solve a constraint system. Since our technique is specification-based, it can facilitate generation of expected outputs for actual tests.

Structural testing of a concurrent program P involves the selection of paths of P according to a structure-based criterion. A common approach is to derive the reachability graph (RG) of P, select a set of paths of P, derive one or more inputs for each selected path, and force deterministic executions of P according to the selected paths and their inputs. The use of RG(P) for test path selection has the state explosion problem, since the number of states of RG(P) is an exponential function of the number of processes in P.In this paper, we present a new incremental approach to structural testing of P. Based on the hierarchy of processes in P, our incremental testing approach is to integrate processes in P in a bottom-to-top manner. When a set S of processes in P at the same level are integrated, we construct a reduced RG for S such that the reduced RG contains all synchronizations involving the processes in S and some of the synchronizations involving processes at lower levels in order to connect synchronizations involving processes in S. Based on the reduced RG for S, we can select test paths to focus on the detection of interface faults involving processes in S. After the selection of paths, RG(S) is further reduced in order to retain only some of the synchronizations involving processes in S that are needed in order to connect synchronizations between S and other processes in P. Our incremental approach alleviates the state explosion problem and offers other advantages.

The authors propose a new technique for the automatic generation of test cases for predicates. Earlier, they proposed an efficient effective test generation strategy for Boolean expressions. They now extend this strategy to predicates. Their new strategy addresses several issues, including: analysis of dependencies between relational expressions in a predicate /spl Pscr/; generation of test constraints for /spl Pscr/ based on the detection of Boolean and relational operator faults in /spl Pscr/; and generation of actual tests according to the generated test constraints for /spl Pscr/. They propose: the use of constraint logic programming (CLP) to automate test-data generation for a predicate; and an incremental approach to apply CLP techniques to solve a constraint system. Since their technique is specification-based, it can facilitate generation of anticipated outputs for actual tests.

Predicates appear in both the specification and implementation of a program. One approach to software testing, referred to as predicate testing, is to require certain types of tests for a predicate. In this paper, three fault-based testing criteria are defined for compound predicates, which are predicates with one or more AND/OR operators. BOR (boolean operator) testing requires a set of tests to guarantee the detection of (single or multiple) boolean operator faults, including incorrect AND/OR operators and missing/extra NOT operators. BRO (boolean and relational operator) testing requires a set of tests to guarantee the detection of boolean operator faults and relational operator faults (i.e., incorrect relational operators). BRE (boolean and relational expression) testing requires a set of tests to guarantee the detection of boolean operator faults, relational operator faults, and a type of fault involving arithmetical expressions. It is shown that for a compound predicate with n, n>0, AND/OR operators, at most n+2 constraints are needed for BOR testing and at most 2*n+3 constraints for BRO or BRE testing, where each constraint specifies a restriction on the value of each boolean variable or relational expression in the predicate. Algorithms for generating a minimum set of constraints for BOR, BRO, and BRE testing of a compound predicate are given, and the feasibility problem for the generated constraints is discussed. For boolean expressions that contain multiple occurrences of some boolean variables, how to combine BOR testing with the meaningful impact strategy (Weyuker et al., 1994) is described.

An abstract program is a formal specification that describes the valid behavior of a distributed program without describing particular implementation mechanisms that achieve this behavior. Valid behavior can be modeled as the possible sequences of events that may be observed of a conforming concrete implementation of the abstract program. In this paper, we address the problem of how to select event sequences from an abstract program to test its concrete implementation. Sequencing constraints make explicit certain types of required properties that are expressed only implicitly by an abstract program. The sequencing constraints derived from an abstract program can be used to guide the selection of event sequences during testing. We describe a constraint notation called CSPE and show how to achieve coverage and detect violations of abstract CSPE constraints. Abstract constraints address the problem of how to compare two programs written at different levels of abstraction. Results of an empirical study of CSPE-based testing are reported.

We propose a new strategy for generating test cases for Boolean expressions. In the past, we reported the BOR (Boolean Operator) strategy for generating test cases for predicates which are singular: which contain only one occurrence of each constituent Boolean variable. We also reported results of the empirical studies that were carried out to study the effectiveness of the strategy, but the BOR algorithm did not work well with non-singularities: multiple occurrences of constituent Boolean variables. The solution we propose for the problem is a combination of the original BOR strategy and the MI (Meaning Impact) strategy reported elsewhere. Our approach is to divide a Boolean expression into components that do not have common variables, apply the MI strategy to non-singular components, and the BOR strategy to singular components, and then apply the BOR strategy to combine the test sets generated for all component. Our empirical results indicate that our hybrid approach produces fewer tests for a Boolean expression than the MI strategy. The fault detection capability of our proposed approach has also been found to be comparable to that of the MI strategy. Our test generation strategy can be used to improve the reliability and safety of a program.

Concurrent programs are more difficult to test than sequential programs because of non-deterministic behavior. An execution of a concurrent program non-deterministically exercises a sequence of synchronization events called a synchronization sequence (or SYN-sequence). Non-deterministic testing of a concurrent program P is to execute P with a given input many times in order to exercise distinct SYN-sequences. In this paper, we present a new testing approach called reachability testing. If every execution of P with input X terminates, reachability testing of P with input X derives and executes all possible SYN-sequences of P with input X. We show how to perform reachability testing of concurrent programs using read and write operations. Also, we present results of empirical studies comparing reachability and non-deterministic testing. Our results indicate that reachability testing has advantages over non-deterministic testing.

Concurrent programs are more difficult to test than sequential programs because of nondeterministic behavior. An execution of a concurrent program nondeterministically exercises a sequence of synchronization events, called a synchronization sequence (or SYN-sequence). Nondeterministic testing of a concurrent program P is to execute P with a given input many times in order to exercise distinct SYN-sequences and produce different results. We present a new testing approach, called reachability testing. If P with input X contains a finite number of SYN-sequences, reachability testing of P with input X can execute all possible SYN-sequences of P with input X. We show how to perform reachability testing of concurrent programs using read and write operations. Also, we present results of empirical studies comparing reachability and nondeterministic testing. Our results indicate that reachability testing has advantages over nondeterministic testing.>

This paper introduces the use of sequencing constraints for specifying, testing, and debugging concurrent programs. An execution of a concurrent program P nondeterministically exercises a sequence of synchronization events, called a synchronization sequence (or SYN-sequence). Sequencing constraints (or constraints) specify restrictions on the allowed SYN-sequences of P. Constraints for P are derived from a formal or informal specification of P and do not have to be complete. The SYN-sequences collected during nondeterministic testing of P can be used to measure coverage and detect violations of P's constraints. Also, SYN-sequences can be generated according to P's constraints and used for deterministic testing of P. This paper shows in detail how to accomplish coverage and detect violations of constraints written in CSPE (Constraints on Succeeding and Preceding Events) by nondeterministic and deterministic testing.

Deadlock, livelock, starvation, and other terms have been used to describe undesirable situations involving blocking or not making progress for processes in a concurrent program However, definitions of these terms are inconsistent and often informal This paper provides formal definitions of deadlock, livelock, and starvation in terms of the reachability graph of a concurrent program Also, this paper shows algorithms for the detection of deadlock, livelock, and starvation.

We report the results of three empirical studies of fault detection and stability performance of the predicate-based BOR (Boolean Operator) testing strategy. BOR testing is used to develop test cases based on formal software specification, or based on the implementation code. We evaluated the BOR strategy with respect to some other strategies by using Boolean expressions and actual software. We applied it to software specification cause-effect graphs of a safety-related real-time control system, and to a set of N-version programs. We found that BOR testing is very effective at detecting faults in predicates, and that BOR-based approach has consistently better fault detection performance than branch testing, thorough (but informal) functional testing, simple state-based testing, and random testing. Our results indicate that BOR test selection strategy is practical and effective for detection of faulty predicates and is suitable for generation of safety-sensitive test-cases.>

The authors present an incremental strategy for reachability analysis of communication protocols modeled as sets of communicating finite state machines (CFSMs) with synchronous communication and direct naming. A set of CFSMs is organized into a hierarchy. The authors present an algorithm that, for a given hierarchy of a set M of CFSMs, incrementally composes and reduces subsets of CFSMs in M and finally produces a minimum CFSM describing the external behavior of M. It is also showed that this incremental reachability analysis guarantees the detection of global deadlocks. An algorithm for selecting a hierarchy for a set of CFSMs and some empirical results are provided.>

Two pumping theorems are derived for a network N of CFSMs (communicating finite state machines). Each pumping theorem describes a set of conditions under which a feasible event sequence of N can be pumped to produce an infinite set of feasible event sequences of N. The authors show that if a feasible event sequence E satisfying the conditions in one pumping theorem does not result in a deadlock or unspecified reception, neither does any event sequence derived by pumping E. Based on these results, they develop a pumping-based approach for detecting deadlocks and unspecified receptions in a network of CFSMs. The experimental results of applying this new approach to validate several communication protocols are shown.>

A static analysis method is introduced for detecting synchronization errors. This method is to derive constraints on the feasible synchronization sequences of a concurrent program (or program module) P according to P's syntactic and semantic information. These constraints, called feasibility constraints for P, can be compared with constraints in the specification of P to detect specification-dependent errors and can be analyzed to detect specification-independent errors such as deadlock. Feasibility constraints for P can be used to improve the accuracy of existing methods for deriving approximations of the set of feasible SYN-sequences of P.>

A language-based approach to deterministic execution debugging of concurrent Ada programs is presented. The approach is to define synchronization (SYN)-sequences of a concurrent Ada program in terms of Ada language constructs and to replay such SYN-sequences without the need for system-dependent debugging tools. It is shown how to define a SYN-sequence of a concurrent Ada program in order to provide sufficient information for deterministic execution. It is also shown how to transform a concurrent Ada program P so that the SYN-sequences of previous executions of P can be replayed. This transformation adds an Ada task to P that controls program execution by synchronizing with the original tasks in P. A brief description is given of the implementation of tools supporting deterministic execution debugging of concurrent Ada programs.>

The author defines two condition testing strategies, BRO (Boolean and relational operator) and BRE (Boolean and relational expression) testing. These two testing strategies are different from existing condition testing strategies in that they are based on the detection of both Boolean and relational expression errors in a condition. For a condition with n operands, the number of tests required by BRO or BRE testing is at most 2(n+1). Based on empirical studies of the algorithms SBEMIN and SBEMINSEN and the theoretical properties of BRO and BRE testing, it is believed that BRO and BRE testing is practical and effective for testing programs containing complicated conditions.>

Although a lot of research has been done in software testing, how to test concurrent programs effectively has not received much attention. Two early papers on testing concurrent programs were written by P. Brinch Hansen (see Software-Practice and Experience, vol.8, p.145-50 and p.721-9 (1989)) K.C. Tai's paper (1985) addressed several issues on testing concurrent programs and started the work on deterministic execution testing and debugging of concurrent programs. These and other research results on testing concurrent programs are briefly examined. The following approaches to testing concurrent programs are discussed: single execution testing, multiple execution testing, and deterministic execution testing. Problems in deterministic execution testing and debugging of concurrent programs are examined.>

The authors show how to accomplish deterministic execution debugging of a concurrent Ada program according to a given synchronization (SYN) sequence. They first define the format of a SYN sequence of a concurrent Ada program in order to provide sufficient information for deterministic execution. They show how to transform a concurrent Ada program P into a slightly different Ada program P' so that any execution of P' with (X,S) as input, where S is the SYN sequence of a previous execution of P with input X, definitely repeats S. Tools for transforming concurrent Ada programs for deterministic execution debugging are described.>

Computed chaining and predictors are two recent techniques for resolving hashing collisions which use a pseudolink field instead of an actual address link to group records which map to the same home address. With additional computation on the pseudolink, the actual address can be determined. The advantage of the pseudolink is that it often takes much less storage than an actual address would take. The authors note problems with the predictor method which must be overcome if the method is to be used successfully. They also compare the predictor method to computed chaining. They conclude with a discussion of the utility of multiple predictor, i.e. having more than one chain of pseudolinks for records with the same home address.

Communicating algorithms and processes is an integral part of computer science education yet in many instances is difficult to carry out effectively using traditional techniques. Using the computer as an aid in visualizing and understanding an algorithm is one way to improve this communication process. With the computer technology available to us today, it would be unfortunate if we did not make effective use of it in computer science education. (We don't want to be like the shoemaker's children.)

Abstract This paper studies the use of text signatures in string searching. Text signatures are a coded representation of a unit of text formed by hashing substrings into bit positions which are, in turn, set to one. Then instead of searching an entire line of text exhaustively, the text signature may be examined first to determine if complete processing is warranted. A hashing function which minimizes the number of collisions in a signature is described. Experimental results for two signature lengths with both a text file and a program file are given. Analyses of the results and the utility and application of the method conclude the discussion.

A predictor of a context-free grammar G is a substring of a sentence in $L(G)$ which determines unambiguously the contents of the parse stack immediately before (in top-down parsing) or after (in bottom-up parsing) symbols of the predictor are processed. Two types of predictors are defined, one for bottom-up parsers and the other for top-down parsers. Algorithms for finding predictors are given and the possible applications of predictors are discussed.

This paper explores the testing complexity of several classes of programs, where the testing complexity is measured in terms of the number of test data required for demonstrating program correctness by testing. It is shown that even for very restrictive classes of programs, none of the commonly used test criteria, namely, having every statement, branch, and path executed at least once, is nearly sufficient to guarantee absence of errors.

There are three commonly used criteria for program testing: each and every statement (branch) (path) in a program is executed at least once. This paper explores the complexity of proving the correctness of several classes of programs by testing. It turns out that even for very restrictive classes of programs, none of the commonly used test criteria is nearly sufficient to guarantee absence of errors. Then this paper proposes two new test criteria which suggest how to select test data to obtain confidence on program correctness beyond the requirement of having each statement, branch, or path to be executed at least once.

The tree-to-tree correctmn problem Is to determine, for two labeled ordered trees T and T', the distance from T to T' as measured by the mlmmum cost sequence of edit operaUons needed to transform T into T' The edit operations investigated allow changing one node of a tree into another node, deleting one node from a tree, or inserting a node into a tree An algorithm Is presented which solves this problem m time O(V* V'*LZ* L'2), where V and V' are the numbers of nodes respectively of T and T', and L and L' are the maximum depths respectively of T and T' Possible apphcatmns are to the problems of measuring the similarity between trees, automatic error recovery and correction for programming languages, and determining the largest common substructure of two trees KEY WORDS AND PHRASES tree correction, tree modification, tree similarity CR CATEGORIES 3 79, 4A2, 4 22, 5 23, 5 25 Edit Operations on Trees

Two noncanonical extensions of the simple LR(1) (SLR(1)) method are presented, which reduce not only handles but also other phrases of sentential forms. A class of context-free grammars called leftmost SLR(1) (LSLR(1)) is defined by using lookahead symbols which appear in leftmost derivations. This class includes the SLR(1), reflected SMSP, and total precedence grammars as proper subclasses. The class of LSLR(1) languages properly includes the deterministic context-free languages, their reflections, and total precedence languages. By requiring that phrases which have been scanned be reduced as early as possible, a larger class of context-free grammars called noncanonical SLR(1) (NSLR(1)) is defined. The NSLR(1) languages can be recognized deterministically in linear time using a two-stack pushdown automaton. An NSLR(1) parser generator has been implemented. Empirical results show that efficient NSLR(1) parsers can be constructed for some non-LR grammars which generate nondeterministic languages. Applications of the NSLR(1) method to improve the parsing and translation of programming languages are discussed.

A technique for syntactic error correction, called pattern mapping, is developed. A pattern is used to describe how to map or change one string into another. Using a preconstructed list of patterns, for each detected error, the first pattern with successful mapping is found and a correction is made based on this pattern.