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

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.