Orchestrating web services aims to compose multiple services into workflows that answer complex user requirements. Web services are software components which are exposed to errors and failures that can occur during web service orchestration execution. Thus, many error-handling and healing approaches have been proposed to guarantee reliable orchestrations. Some of these approaches rely on the identification of relevant service ubstitutes to heal (by substitution) the defected services. In this paper, we propose an identification process of web service substitutes for healing failed web service orchestrations based on the measurement of similarity between service interfaces. The process reveals both simple and complex (compositions of) substitutes. We validated the approach via a set of experiments conducted on a collection of real web services.