In this paper we describe several methods for detecting the need for software rejuvenation in mission critical systems that are subjected to worm infection, and introduce new software rejuvenation algorithms. We evaluate these algorithms' effectiveness using both simulation studies and analytic modeling, by assessing the probability of mission success. The system under study emulates a Mobile Ad-Hoc Network (MANET) of processing nodes. Our analysis determined that some of our rejuvenation algorithms are quite effective in maintaining a high probability of mission success while the system is under explicit attack by a worm infection.