Today, host-based malware detection approaches such as antivirus programs are severely lagging in terms of defense against malware. Two important aspects that the overall effectiveness of malware detection depend on are the success of extracting information from malware using malware analysis to generate signatures, and then the success of utilizing these signatures on target hosts with appropriate system monitoring techniques. Today's malware employ a vast array of anti-analysis and anti-monitoring techniques to deter analysis and to neutralize antivirus programs, reducing the overall success of malware detection. In this dissertation, we present a set of practical approaches of robust and efficient malware analysis and system monitoring that can help make malware detection on hosts become more effective. First, we present a framework called Eureka, which efficiently deobfuscates single-pass and multi-pass packed binaries and restores obfuscated API calls, providing a basis for extracting comprehensive information from the malware using further static analysis. Second, we present the formal framework of transparent malware analysis and Ether, a dynamic malware analysis environment based on this framework that provides transparent fine-(single instruction) and coarse-(system call) granularity tracing. Third, we introduce an input-based obfuscation technique that hides trigger-based behavior from any input-oblivious analyzer. Fourth, we present an approach that automatically reverse-engineers the emulator and extracts the syntax and semantics of the bytecode language, which helps constructing control-flow graphs of the bytecode program and enables further analysis on the malicious code. Finally, we present Secure In-VM Monitoring, an approach of efficiently monitoring a target host while being robust against unknown malware that may attempt to neutralize security tools.