JOURNAL OF NETWORKS (JNW)

ISSN : 1796-2056

Volume : 4 Issue : 5 Date : July 2009

**Searching for Optimal Homing Sequences for Testing Timed Communication Protocols**

Ariel Stulman

Page(s): 315-323

Full Text: PDF (492 KB)

**Abstract**

With the eruption of communication technology and its supportive protocols, the field of testing of

timed-IUT (Implementation Under Test with time constraints) was quick to follow. New and

extended test generation methods using timed automata were in the need. Many papers were

written on a broad range of timed automata testing. Few papers, however, dealt with generation of

state identification sequences problems. Those who did, keyed their algorithms towards

transformation of a timed-IUT into a regular, untimed IUT; thus, avoiding the need of redefining well

known generation algorithms. This method, however, only functions if we search for optimal

sequences w.r.t. their lengths. Optimality w.r.t. execution time was not considered in this context. In

this paper we present a search algorithm for the direct generation of timed homing sequences

optimal w.r.t. to execution time. This is accomplished by expanding and modifying the search tree

used in previous algorithms such that it contains the capability of satisfying our goal. The solution

found is proven to be optimal with respect to execution time. A comparison with other related

algorithms is presented.

**Index Terms**

homing sequence, state identification, timed automata, testing

ISSN : 1796-2056

Volume : 4 Issue : 5 Date : July 2009

Page(s): 315-323

Full Text: PDF (492 KB)

timed-IUT (Implementation Under Test with time constraints) was quick to follow. New and

extended test generation methods using timed automata were in the need. Many papers were

written on a broad range of timed automata testing. Few papers, however, dealt with generation of

state identification sequences problems. Those who did, keyed their algorithms towards

transformation of a timed-IUT into a regular, untimed IUT; thus, avoiding the need of redefining well

known generation algorithms. This method, however, only functions if we search for optimal

sequences w.r.t. their lengths. Optimality w.r.t. execution time was not considered in this context. In

this paper we present a search algorithm for the direct generation of timed homing sequences

optimal w.r.t. to execution time. This is accomplished by expanding and modifying the search tree

used in previous algorithms such that it contains the capability of satisfying our goal. The solution

found is proven to be optimal with respect to execution time. A comparison with other related

algorithms is presented.