Software rejuvenation has been used to improve reli- ability of systems by periodically checkpointing and restarting them. In this paper, we propose to use rejuvenation as a mechanism to enhance the security of Cloud infrastructure and eliminate malware by continuous and periodic rejuvenation. To evaluate the effectiveness of rejuvenation in eliminating malware, we defined an experimental setup, and utilizing complete sys- tem rejuvenation, as well as application level rejuvenation we investigated which malware were eliminated. We also describe a cost model for rejuvenation so that one can determine how often systems and applications should be rejuvenated, trading cost against security. Our experiments and models show that rejuvenation once every 24 hours is cost-effective.