4 ms·
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 vi
by alok-g 14y ago
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?
- brutos 14y agoFirst 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.