Validation of network state of Network Function Virtualization Infrastructure (NFVI) under various uncertainties are of primary importance as they directly affect Service Function Chain (SFC) provisioning and its performance. SFC provisioning against the uncertainties, including variable traffic demand and failures of link and switch makes validation challenging because the number of scenarios to validate grows exponentially with the number of such failures. This letter takes advantage of a two-stage validation framework and proposes a validation strategy to verify the underlying NFVI network state that supports SFC provisioning despite various uncertainty in the network. We demonstrate the effectiveness of our strategy through different failure and SFC placement scenarios using realistic network topologies and traffic matrix. © 1997-2012 IEEE.