The virtual network provider (VNP) cannot diagnose all service faults of virtual networks, because thesubstrate network is transparent for VNP within the network virtualization environment. To solve this problem, thepaper presents a service fault propagation model based on mapping relationships. In terms of the large fault set, thelarge symptom set, and noisy and dynamic environments, which result in the higher false positive rate and thelonger running time of existing fault diagnosis algorithms, a service fault diagnosis algorithm based on inherentcorrelation among symptoms (SFDoIC), is proposed. Simulation results show that algorithm SFDoIC can solve thedifficult problems in fault diagnosis that are caused by the transparency of the substrate network for VNP,effectively reducing the false positive rate and decreasing running time.