News for hackers. Stuff that matters.
Re:Antivirus Makers Struggle to Adapt by alok-g on Monday December 31, 2012 @11:03PM (#4991825)
Newbie questions (I have searched the Internet a bit, did not find information to answer these):

I understand that anti-viruses (AVs) maintain signatures of viruses (which as I understand are byte patterns present in that virus not present in non-infected software code). They also look for executables modifying others.

Questions:

1. If AVs have to match byte patterns for a very large number of known viruses (millions??), would this not make scanning each executable very slow? This seems to be O[e*v] operation where e is the number of executables and v is the number of viruses. Since it does not seen as slow intuitively, what is going on?

2. I presume AVs would also track check-sums of known executables so that these can be safe guarded against new viruses for which signatures are not yet available. Is this right?

Re:Antivirus Makers Struggle to Adapt by brutos on Monday December 31, 2012 @11:20PM (#4991853)
First I don't really have an idea about security software. But to your first question:

The algorithm that is used is probably a variation of the Aho-Corasick algorithm. This is a string matching algorithm that can match k patterns in O(kn+m).

This is basically linear and doable.

Two your second question I can only point to a flaw in some virus scanner a couple years ago where it detected a false positive in an essential Windows file, removed the file and left Windows in an unbootable state. I do hope that there was some learned lesson.