  Assuring quality of contemporary software systems is a very challenging task
due to the often large complexity of the deployment environments in which they
will operate. Service virtualization is an approach to this challenge where
services within the deployment environment are emulated by synthesising service
response messages from models or by recording and then replaying service
interaction messages with the system. Record-and-replay techniques require an
approach where (i) message prototypes can be derived from recorded system
interactions (i.e. request-response sequences), (ii) a scheme to match incoming
request messages against message prototypes, and (iii) the synthesis of
response messages based on similarities between incoming messages and the
recorded system interactions. Previous approaches in service virtualization
have required a multiple sequence alignment (MSA) algorithm as a means of
finding common patterns of similarities and differences between messages
required by all three steps.
  In this paper, we present a novel MSA algorithm based on Generalized Suffix
Trees (GSTs). We evaluated the accuracy and efficiency of the proposed
algorithm against six enterprise service message trace datasets, with the
proposed algorithm performing up to 50 times faster than standard MSA
approaches. Furthermore, the algorithm has applicability to other domains
beyond service virtualization.
