With the Internet becoming the dominant channel for marketing and promotion, online advertisements are also increasingly used for illegal purposes such as propagating malware, scamming, click activities, which we call malvertising, we perform a largescale study through analyzing ad-related Web traces crawled over a three-month period. Our study reveals the rampancy of malvertising: hundreds of top ranking Web sites fell victims and  leading ad networks such as DoubleClick were infiltrated. To mitigate this threat, we identify prominent features from malicious advertising nodes and their related content delivery paths, and leverage them to build a new detection system called MadTracer. MadTracer automatically generates detection rules and utilizes them to inspect advertisement delivery processes and detect malvertising activities. Our evaluation shows that MadTracer was capable of capturing a large number of malvertising cases, 15 times as many as Google Safe Browsing and Microsoft Forefront did together, at a false positive rate of around 0.1%. It also detected new attacks, including a type of click-fraud attack that has never been reported before.