Software testing is one of the important techniques to guarantee the quality of service composition, which will directly affect the efficiency and correctness of service testing. In this paper, a testing model for service composition is proposed by establishing the formal model for basic services, components, test cases and other components via Petri nets. Moreover, by means of the analysis of state space model, the test cases selection and implementation strategy for service composition are given. The effectiveness and feasibility of the proposed algorithm are verified by the operation semantics and related theories of Petri nets. Finally, it is shown from experimental results that the present approach can effectively simplify the testing process of service composition, and improve the testing quality and efficiency.