Malware is at the root of a large number of information security breaches. Despite widespread effort devoted to combating malware, current techniques have proven to be insufficient in stemming the incessant growth in malware attacks. In this paper, we describe a tool that exploits a combination of virtualized (isolated) execution environments and dynamic binary instrumentation (DBI) to detect malicious software and prevent its execution. We define two isolated environments: (i) a Testing environment, wherein an untrusted program is traced during execution using DBI and subjected to rigorous checks against extensive security policies that express behavioral patterns of malicious software, and (ii) a Real environment, wherein a program is subjected to run-time monitoring using a behavioral model (in place of the security policies), along with a continuous learning process, in order to prevent non-permissible behavior. We have evaluated the proposed methodology on both Linux and Windows XP operating systems, using several virus benchmarks as well as obfuscated versions thereof. Experiments demonstrate that our approach achieves almost complete coverage for original and obfuscated viruses. Average execution times go up to 28.57X and 1.23X in the Testing and Real environments, respectively. The high overhead imposed in the Testing environment does not create a severe impediment since it occurs only once and is transparent to the user. Users are only affected by the overhead imposed in the Real environment. We believe that our approach has the potential to improve on the state-of-the-art in malware detection, offering improved accuracy with low performance penalty.