Coupling cyber and physical systems gives rise to numerous engineering challenges and opportunities. An important challenge is the contagion of failure from one system to another, which can lead to large-scale cascading failures. However, the self-healing ability emerges as a valuable opportunity where the overlaying cyber network can cure failures in the underlying physical network. To capture both self-healing and contagion, this paper considers a graphical model representation of an interdependent cyber-physical system, in which nodes represent various cyber or physical functionalities, and edges capture the interactions between the nodes. A message-passing algorithm is proposed for this representation to study the dynamics of failure propagation and healing. By conducting a density evolution analysis for this algorithm, network reaction to initial disruptions is investigated. It is proved that as the number of message-passing iterations increases, the network reaches a steady-state condition that would be either a complete healing or a complete collapse. Then, a sufficient condition is derived to select the network parameters to guarantee the complete healing of the system. The result of the density evolution analysis is further employed to jointly optimize the design of cyber and physical networks for maximum resiliency. This analytical framework is then extended to the cases where propagation of failures in the physical network is faster than the healing responses of the cyber network. Such scenarios are of interest in many real-life applications such as smart grid. Finally, extensive numerical results are presented to verify the analysis and investigate the impact of the network parameters on the resiliency of the network.