Google has rolled out a new notification for its search engine that will detect whether not a user’s connection is being intercepted. In case a user’s computer is infected with a type of malware that hijacks their search results by routing them to Google’s servers via a proxy, the search engine will display a large warning on the top of the webpage. It contains a link with advice on how to remove the malware from the user’s machine.

Why now? Because while doing routine maintenance, Google security engineer Damian Menscher recently found out just how many infected computers connect to Google’s datacenters.

Menscher said when Google takes a data center off-line, search traffic directed to that center is temporarily stopped. Unexpectedly, Menscher found that a data center recently taken off-line was still receiving thousands of requests per second.

He looked into the results a bit closer and discovered that more than a million Microsoft computers are infected with a strain of malware that intercepts traffic directed at all the major search engines to feed PPC scams. Menscher said the source of the malware is a fake AV program.

Luckily, Google came up with a way to detect machines with the malicious software installed on them and now displays a warning for those users.  The cleanup process may a bit more complicated though, mainly because this sort of malware programs commonly redirect users to fake sites when searching for an antivirus.

Google’s using the power of data analysis to help determine where to look for malware.  It’s a tactic that’s becoming very important in the security sector, as companies try to stay ahead of cyber attackers. Kirsten Nicole interviewed Kevin Mahaffey, CIO of mobile security firm Lookout Security this morning about his company’s latest offering, the Mobile Threat Network. The mobile threat detection and analytics product works with some similarity to Google’s own detection engine, by leveraging existing data and predictive analysis to discover a threat. Verizon users will be among the first to gain access to Lookout’s new product.