Malware or malicious code is a rapidly evolving threat to the computing community. Zero-day malware are exploiting vulnerabilities very soon after being discovered and are spreading quickly. However, anti-virus tools, which are the most widely used countering mechanism, are unable to cope with this. They are based on signatures which need to be computed for new malware strains. After a new malware strikes and before the signature is found allows sufficient time for the malware to perform its damage. We propose a new framework, codenamed MalTRAK, which, when deployed on a clean system, guarantees that any effects of a known or unknown malware can always be reversed and the system can be restored back to a prior clean state. Our framework also maintains detailed dependency lists of system operations which can be used for further forensic analysis. We are able to achieve this without imposing any restrictions on the nature of programs that can be executed by the user and without the user noticing any perceptible system slowdown due to the framework. Furthermore, we are able to track modifications to the system at a level that ensures that we can always monitor any changes to the system state even if a malware modifies the system during execution. We implemented and evaluated MalTRAK on Windows, using 8 known malware assuming they were unknown strains. We then compared our results with two popular commercial anti-virus tools. We were able to successfully restore all the effects of the 8 malware, while the commercial tools, on an average were only able to restore 36% of all their effects put together. For one of the malware samples, the commercial tools could only detect it but could not repair any of its damage. Further, for two of the malware samples, the commercial tools were completely unable to detect or restore any of their effects. Our results show that signature based mechanisms in addition to not being able to prevent infection by new malware strains, are not very effective in removing an infection even after a signature has been developed. Our experience shows that non-signature based approaches, such as MalTRAK, are the next step towards combating the threat of ever-evolving malware.