Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-06-08
2004-01-20
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C702S118000, C703S016000, C714S030000, C714S724000
Reexamination Certificate
active
06681374
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to embedded testing of components in a system that can be modeled through extended finite state machines.
2. Description of the Prior Art
With the advanced computer technology and the increasing demand from the users for sophisticated services, communication protocol systems are becoming more complex, yet less reliable. Conformance testing, which ensures correct protocol implementations, has become indispensable for the development of reliable communication systems. Traditional testing methods tend to test these systems as a whole or alternately test their components in isolation. Testing these systems as a whole becomes difficult due to the formidable size of the systems. Furthermore, testing system components in isolation may not be always feasible due to the interactions among the individual system components. Typically, the tester does not have a direct access to the component under test; access is obtained through other components of the system. As a result, Embedded testing or testing in context has become one of the main focuses of conformance testing research in recent years. The goal of embedded testing is to test whether an implementation of a system component conforms to its specification in the context of other components. If control and observation are applied through one or more implementations that are above the protocol to be tested, the testing methods are called “embedded.”
Different approaches for embedded testing are currently in use. These approaches are based on (1) fault models, (2) on reducing the problem to testing of components in isolation, (3) on test suite minimization, (4) on fault coverage, and (5) on the test of systems with semi-controllable and uncontrollable interfaces. Most of these approaches resort to reachability graphs to model the joint behaviors of all the system components. Unfortunately, the implementation of these approaches is plagued by state space explosion, as well as random walk errors.
The problem of random walk remains prevalent under current systems. For example, for a given system component, there is generally a need to test all the transitions or certain boundary values of system variables. Conventionally, a reachability graph is constructed, which is the Cartesian product of all the system components involved. Next, a test is derived that covers all the pre-specified parts of the component under test. Unfortunately, this exhaustive search technique is often impractical; it is impossible to construct a reachability graph for practical systems due to the state space explosion. To avoid this problem random walks have been proposed. At any moment, it is only necessary to keep track of the current states of all the components and determine the next step of test at random. This approach avoids the state space explosion but it may repeatedly test covered parts and take a long time to move on to the untested parts.
Furthermore, a random walk may become “trapped” at a certain part of the component under test or in a small neighborhood. Also, random walks have a low probability of crossing a “narrow bridge” to test the parts beyond the bridge, and may also miss unmarked transitions, even if they are nearby (more than one step from the current node). Finally, the great reliance on reachability graphs restricts space requirements in testing, and is dependent on the system under consideration.
SUMMARY OF THE INVENTION
The present invention, referred to as “Hit-or-Jump” provides a more efficient and accurate modeling environment through the use of communicating extended unit state machines (CEFSM). Specifically, a new method and system is disclosed for embedded testing of CEFSM's. The CEFSM model can also be easily adapted to other mathematical models such as Transition Systems, Labeled Transition Systems, and Petri Nets.
Specifically, the present invention tests pre-specified parts of a system component that is embedded in a complex communication system. The pre-specified parts are determined by practical needs or by system certification requirements. Thus, all the transitions or certain boundary values of system variables may be tested for a given system component. Under the “Hit-or-Jump” method and system, a local search is conducted from the current state in a neighborhood of the reachability graph. If an untested part is found (a “Hit”), that part is tested, and the process continues from that point. Otherwise, a subsequent random move is made to the frontier of the neighborhood searched (“Jump”), where the process then continues. This procedure avoids the construction of a complete system reachability graph. Furthermore, the space required is determined by the user, and it is independent of the systems under consideration. While a random walk may get “trapped” at certain part of the component under test, the disclosed method and system is designed to “jump” out of the trap and pursue the exploration further.
In a preferred embodiment, the Hit-or-Jump method is applied to the embedded testing of services on a telephone network. The examples given below typify the invention utilized in a system using the signaling data link (SDL) language. The telephone services associated with the invention appear in an Intelligent Network (IN) architecture with Basic Call Services (BCSs). In addition to BCS, five other services are included: Originating Call Screening (OCS), Terminating Call Screening (TCS), Call Forward Unconditional (CFU), Call Forward on Busy Line (CBL) and Automatic Call Back (ACB).
REFERENCES:
patent: 4914659 (1990-04-01), Erickson
patent: 5450586 (1995-09-01), Kuzara et al.
patent: 5586125 (1996-12-01), Warner
patent: 5884082 (1999-03-01), Seidel et al.
patent: 5909452 (1999-06-01), Angelotti
patent: 5911059 (1999-06-01), Profit, Jr.
patent: 5918037 (1999-06-01), Tremblay et al.
patent: 6181320 (2001-01-01), Fredrickson
patent: 6209120 (2001-03-01), Kurshan et al.
Olson et al., “State assignment for low-power FSM synthesis using genetic local search”, Proceedings of the IEEE 1994 Custo Integrated Circuits Conference, May 1, 1994, pp. 140-143.*
Rekleitis et al., “Efficient topological exploration”, Proceedings of 1999 IEEE International Conference on Robotics and Automation, May 10, 1999, vol. 1, pp. 676-681.
Kik Phallaka
Lucent Technologies - Inc.
Siek Vuthe
LandOfFree
Hit-or-jump method and system for embedded testing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hit-or-jump method and system for embedded testing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hit-or-jump method and system for embedded testing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3262579