Method and apparatus for generating conformance test data sequen

Details Method and apparatus for generating conformance test data sequen Method and apparatus for generating conformance test data sequen

1994-06-27

1997-04-22

Voeltz, Emanuel T.

Excavating

364578, G11C 2900

Patent

active

056234996

ABSTRACT:
A method and apparatus for generating a conformance test data sequence of minimal length to verify that a device conforms to a protocol entity which can be characterized by a simplified extended finite state machine. The method generates an expanded directed graph of the protocol wherein each state is represented by a state vertex and a dummy vertex which are connected to other similar state and dummy vertices by directed edges in a configuration corresponding to the operation of the machine. The directed edges are then assigned traversal numbers corresponding to the minimum number of times a respective directed edge need be traversed in order to test values in a predetermined test data set. The traversal numbers of the expanded directed graph are balanced to form a symmetric expanded directed graph. An Euler tour and a corresponding unique input-output sequence of the last state of the Euler tour are generated to form the conformance test data sequence. The generated conformance test data sequence exhaustively tests the values in the test data set, and achieves an efficiency in conformance testing by minimizing the amount of time required to perform the conformance test.

REFERENCES:
patent: 4692921 (1987-09-01), Dahbura et al.
patent: 4696006 (1987-09-01), Kawai
patent: 4991176 (1991-02-01), Dahbura et al.
patent: 5003470 (1991-03-01), Carpenter et al.
patent: 5163016 (1992-11-01), Har'El et al.
patent: 5230061 (1993-07-01), Welch
patent: 5299206 (1994-03-01), Beaverson et al.
Bahar et al. "An ADD-Based Algorithm for Shortest Path Back-Tracing of Large Graphs," Proceedings Design Automation of High Performance VLSI System GLSV '94 pp. 248-251.
Aho, A.V. et al., "An Optimization Technique for Protocol Conformance Test Generation Based on UIO Sequences and Rural Chinese Postman Tours", Symposium of Protocol Specification, Testing and Verification, 1988.
Chan, W.Y., Vuong, S.T., Ito, M.R., "An Improved Protocol Test Generation Procedure Based on UIOS," 1989, pp. 283-289.
Chanson, S.T., Zhu, J., "A Unified Approach to Protocol Test Sequence Generation," Proceedings of IEEE INFOCOM '93, Mar. 1993, pp. 106-114.
Chun, W., Amer, P.D., "The Case Generation for Protocols Specified in Estelle," Oct. 1990.
DeMillo, R.A., et al, "Constraint-Based Automatic Test Data Generation," IEEE Transactions on Software Engeneering, vol. 17, No. 9, Sep. 1991, pp. 900-910.
DeMillo, R.A. et al., "Hints on Test Data Selection: Help for the Practicing Programmer," IEEE, 1978, pp. 34-41.
Frankl, P.G., Weyuker, E.J., "Provable Improvements on Branch Testing," IEEE Transactions on Software Engineering, Oct. 1993, 29 pages.
McHugh, J.A., Algorithmic Graph Theory, Prentice Hall, 1990, pp. 42-44, 190-197.
Miller, R.E., Paul, S., "Generating Maximal Fault Coverage Conformance Test Sequences of Reduced Length for Communication Protocols," IEEE, 1993, pp. 217-224.
Miller R.E., Paul, S., "On the Generation of Minimal-Length Conformance Tests for Communication Protocols", IEEE/ACM Transactions on Networking, vol. 1, No. 1, Feb. 1993, pp. 116-129.
Rapps, S., Weyuker, E.J., " Selecting Software Test Data Using Data Flow Information," IEEE Transactions on Software Engineering, vol. SE-11, No. 4, Apr. 1985, pp. 367-375.
Sabnani, K., Dahbura, A., "A Protocol Test Generation Procedure," North-Holland Computer Networks and ISDN Systems 15, Elsevier Science Publishers B.V., 1988, pp. 285-297.
Sarikaya, B., et al., "A Test Design Methodology for Protocol Testing," IEEE Transactions on Software Engineering, vol. SE-13, No. 5, May 1987, pp. 518-539.
Sidhu, D., Leung, T., "Fault Coverage of Protocol Test Methods," IEEE, 1988, pp. 80-85.
Ural, H., Yang, B., "A Test Sequence Selection Method for Protocol Testing," IEEE Transactions on Communications, vol. 39, No. 4, Apr. 1991, pp. 514-523.

Affiliated with

Also associated with

Rating

Method and apparatus for generating conformance test data sequen does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for generating conformance test data sequen, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating conformance test data sequen will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-346821