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)

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