Network slicing is an emerging terminology that enables operators to partition a shared substrate network into multiple logically isolated and on-demand virtual networks to support diverse communication cases. However, the performance of network slices can be heavily deteriorated due to unexpected software or hardware malfunctions in the substrate network. Furthermore, the traffic demand is usually considered as a deterministic parameter during the network slice deployment, while it could be stochastically varied in reality, and such stochasticality may invalidate some network slices. Therefore, it is imperative to develop a robust network slicing algorithm. In this paper, we first formulate the failure recovery problem of network slicing as a mixed integer programming (MIP) and then model the robust MIP (RMIP) to capture the stochastic traffic demand. We solve the RMIP by using the robust optimization approach. Numerical results reveal that the proposed the robust network slicing algorithm can provide adjustable tolerance of traffic uncertainty in comparison with the nonrobust algorithm. In the meanwhile, the trade-off between robustness of requests and the load of substrate links can be hence efficiently managed and controlled.