Web services present a new promising software technology. However, some new issues and challenges in testing of them come out due to their characteristics of distribution, source code invisibility etc. This paper discusses the traditional mutation testing and then a new methodology of OWL-S requirement model-based web service mutation testing is brought forward. The traits of this methodology are as follows. Firstly, requirements are used effectively to reduce the magnitude of mutants. Secondly, mutants are generated by AOP technology conveniently and promptly. Thirdly, to reducing testing cost, using business logic implied in OWL-S requirement model as assistant of the process of killing the mutants. Fourthly, two sufficient measurement criteria are employed to evaluate the testing process. Finally, our empirical results have shown the usefulness of this testing method.