Abstract: Business process execution language for Web service (WS-BPEL) is an executable XML-based and process-oriented service composition language. Due to unique features of Web services, such as dynamics, loose coupling, and open deployment and execution environment, it is an important issue how to assure the quality of WS-BPEL programs. Although mutation testing has a strong fault detection capability, it fails to be widely practiced due to the large number of mutants, the long execution period, and the high computation cost. In order to improve the practicability of mutation testing, we investigate how to decrease the cost of mutation testing for WS-BPEL programs, and propose two kinds of optimization techniques from the perspectives of second-order mutation and prioritization of operators. We also develop an integrated tool named μBPEL to support the mutant generation, optimization, and execution of the proposed optimization techniques. Finally, an empirical study has been conducted where six representative WS-BPEL programs are used to validate and evaluate the effectiveness of the proposed optimized mutation testing techniques. Experimental results show that the proposed optimization techniques for WS-BPEL programs are able to reduce the number of mutants without significantly jeopardizing their fault detection effectiveness and thus improve the efficiency of mutation testing.