Learning service behavior with progressive testing

We describe a comprehensive methodology for discovering service similarity (substitutability) by testing. Our solutions do not rely on the service descriptions provided by their authors and they avoid common information retrieval techniques. Our work addresses a variety of challenges raised throughout the process. These include: (1) the generation of unbiased test samples based on individual domains and their statistical properties; (2) the use of progressive sampling and Rand index convergence to minimize sample size; (3) the classification of services by their input and output structures (single values, sets of values, sequences of values, and tables), and the development of corresponding similarity measures; (4) the optimal alignment of services that have multiple inputs and outputs of the same type; (5) the management of two types of service exceptions (null values); (6) the selection of clustering methods that are most appropriate to the sets of services being clustered; and (7) the caching of tests, results, similarities, clusters and other statistical information to enable cluster evolution. Initial testing with a prototype implementation validated our methodology, yielding high accuracy at surprisingly small test sizes.