Web Service is a modern technology commonly used to integrate software projects among different platforms, operating systems or even programming languages. This distributed and heterogeneous nature complicates the testing activity which is, in general, expensive and effort demanding. Adequate and cost effective testing methods are needed for Web Services. An extended approach based on XML messages perturbation has been introduced to test pairs of Web Services. Perturbation operators produce modified XML messages, which are used as test cases. This work explores the use of such promising approach by introducing new perturbation operators for SOAP messages and describing a supporting tool, named SMAT-WS. An experimental study was accomplished with this tool. The obtained results allow an evaluation of the perturbation operators regarding cost and efficacy.