Web services are considered a new paradigm for building software applications that has many advantages over the previous paradigms; however, Web services are still not widely used because Service Requesters do not trust Web Services that were built by others. Testing can participate in solving this problem because it can be used to assess the quality attributes of Web Services and hence increase the requesters’ trustworthiness. This paper proposes an approach that can be used to test the robustness and other related attribute of Web Services, and that can be easily enhanced to assess other quality attributes. The framework is based on rules for test case generation that are designed by, firstly, analyzing WSDL document to know what faults could affect the robustness quality attribute of Web Services, and secondly, using the fault-based testing techniques to detect such faults. A proof of concept tool that depends on these rules has been implemented in order to assess the usefulness of the rules in detecting robustness faults in different Web Services platforms.