Propagation of Internet worms is a serious problem in our highly information oriented society. In this paper, we propose a stochastic model for Internet worm propagation to evaluate its dependability measures quantitatively. More precisely, the deterministic kill-signal model is reformulated based on a continuous-time Markov chain. We define some dependability measures and derive the recursive computation algorithms to assess them. In numerical experiments, we investigate the behavior of actual Internet worms with real infection data and characterize their propagation.