杀毒原理

杀毒软件编程精华——特征码扫描技术

2006-11-05 21:08

特征码扫描技术是反病毒技术中的常规武器，虽然特征码扫描技术有着一定的局限性，但是，改进的基于特征码扫描技术的广谱特征串过滤技术却有着无比的优越性和广阔的应用前景。但是，无论是上面提到的哪种技术，最终都难以逃脱扫描算法的效率要求。而学过《数据结构》的读者应该知道一种快速的字符串扫描算法叫做“模式匹配算法”，这种算法可以对字符串进行快速扫描。但是，深入进去就会发现，我们的特征码扫描算法中经常会用到通配符，如：%和*（这里我令%匹配一个字符，*匹配32个字符），对于这样一些非常规的串，没有现成的算法可以引用。笔者在做防治木马技术的研究中，对常规的模式匹配算法进行了改进，写出了如下的快速查找算法，暂且命名为“半回溯的模式匹配算法”，以与常规的“无回溯的模式匹配算法”区别。

这里，我之所以称之为“半回溯”，就是因为在对通配符进行匹配时要进行适当的回溯，以减少因为采用通配符所带来的过长推进，虽然这是一种带有回溯的算法，但是实际上它的效率并不比“无回溯的模式匹配算法”低多少，其对算法的效率不能构成真正的威胁。这个算法比较抽象，如果没有基础的读者最好先回头看一下《数据结构》的教材中的“无回溯的模式匹配算法”，会对您接下来对算法的理解产生很大的帮助。光说不练，不是好汉，下面我们就开始艰辛而又刺激的模式匹配算法之旅。

对于“无回溯的模式匹配算法”，我不想做过多的说明，因为相关书籍上已经说得够明白了。下面，我们一起来看一下带通配符的半回溯的匹配算法（用%号匹配一个字符，用*匹配32个字符）：

1.[初始化]

i=1; j=1;

counter1=0; counter2=0;

2.[利用next[i]反复进行比较，直到i等于m+1]

循环 当i<=m且j<=n时，反复执行

若（p[i]!=’*’且p[i]==t[j]）

则i=i+1; j=j+1;

否则若p[i]==’%’

则 i=i+1; j=j+1; counter1=counter1+1;

否则若p[i]==’*’

则i=i+1; j=j+32; counter2=counter2+1;

否则若next[i]>0

则i=next[i] j=j -

(counter1+counter2*32);counter1=0;counter2=0;

否则

i=1; j=j -

(counter1+counter2*32);j++;counter1=0;counter2=0;

其中，counter1是用来统计%的个数，而counter2用来统计*的个数，其中m是子串的长度，n是被搜索串的长度。每次碰到子串中

有%的时候就自动将counter1加一，若是碰到counter2就自动将counter2加一。i用来指明子串的当前的比较的位置，而j用来指明被搜索串当前比较的位置，如果一旦子串与被搜索串不能满足搜索条件，就要将被搜索串的比较位置进行回溯，以回到被通配符漏过的字符的个数，以便重新匹配。

这里，涉及到了与“无回溯的模式匹配算法”中相同的要使用的Next数组，其中，Next数组的计算方法如下：

1.[初始化]

j=0; i=1;

next[1]=0;

2.[反复比较计算next[i+1]

循环 当i<m时，反复执行

(1)[找出p1p2?pi中最大的相同的前缀和后缀，并将长度送j] 循环 当j>0且p[i]!=p[j] 且p[i]!=’%’且p[j]!=’%’时，反复执行

j=next[j]

(2)[计数器加1]

i=i+1; j=j+1;

(3)[计算next[i]]

若p[i]==p[j]或p[i]==’%’或p[j]==’%’

则next[i]=next[j];

否则next[i]=j;

Next数组的计算方法，与“无回溯匹配算法”稍有不同，因为%用来匹配一个字符，所以对于%的处理，可以看作比较的字符相等的情况来处理，而对*的比较，无论如何一个字符都不可能与一个32字符的字符串相等，所以对于*始终认为不相等。

这个算法的描述，无论我作何解释，读者总会感觉到有一些抽象，而难于真正理解。下面，笔者写了一个简单的程序，来对这个算法进行测试，希望对您会有所帮助。这个程序是在VC6.0的控制台下运行的，非常简单，基本上就上将以上的算法翻译成了C++语言。源程序可以在附书光盘中找到，名称为“带通配符的无回溯模式匹配算法源程序”。

在这个程序中，首先就是要建立一个子串和被搜索串，并确定算法中提到的m和n的值，如下所示。

//被搜索的串

char*

t="nihaoaxishanchangshanchangaoyejiehhe*%dfisd%shanchashanchanghongioejw";

//子串

char* p="shanchang%*%hong";

//next数组中元素的个数等于子串的长度

int next[16];

int i,j;

//initialize variable

j=0;i=1;next[0]=0;

接下来，要计算next数组的值，对上面的算法进行翻译，得到如下代码。

//计算next数组的循环

while(i<16)

{

while(j>0&&p[i-1]!=p[j-1]&&p[i-1]!='%'&&p[j-1]!='%') j=next[j-1];

i++;

j++;

if(p[i-1]==p[j-1]||p[i-1]=='%'||p[j-1]=='%')

next[i-1]=next[j-1];

else

next[i-1]=j;

}

有了至关重要的next数组之后，就要使用改进了的模式匹配算法，从被搜索串中搜索出子串，代码如下：

//模式匹配的循环

i=1;

j=1;

int counter1=0,counter2=0;

while(i<=16&&j<=69)

{

if(p[i-1]!='*'&&p[i-1]==t[j-1])

{i++;j++;}

else if(p[i-1]=='%')

{

i++;

j++;

counter1++;

}

else if (p[i-1]=='*')

{

i++;

j+=32;

counter2++;

}

else if (next[i-1]>0)

{

i=next[i-1];

j-=(counter1+counter2*32);

counter1=0;

counter2=0;

}

else

{

i=1;

j-=(counter1+counter2*32);

j++;

counter1=0;

counter2=0;

}

//如果I等于17，说明对子串的搜索已经走到尽头，并搜索到了子串，跳出循环。

if(i==17) break;

}

如果您需要使用这个算法进行特征码的查找，可以直接将其中的计算next数组和模式匹配的部分进行移植。

到这里，基本上将要说的都说完了，可能您对这个算法还是有一些迷惑，如果您对其的正确性有疑问的话，可以使用上面的程序，对不同的子串和被搜索串进行操作。另外，如果您对next数组不太了解，还是建议您找出教材来好好看一下。本算法的效率是比较高的，至于它的计算复杂度，我想在这里我就不能做过多的说明了，有兴趣的读者，或者从事反病毒研究的读者，希望能对你们有一定的帮助，同时，如果有不对的地方，可以在黑防的论坛上面提一下，以期获得改进。

后记：对于一个真正的程序员来说，其任务决不应该仅仅只是机械地拖拖控件，动动鼠标。更重要的应该是编程开始前的软件的整体安排和设计，而相关算法设计也应该是非常重要的一部分。对于一个扫描软件来说，其扫描算法的设计也定是其精华所在。本文专门对算法进行相关分析，希望能够对您有所启发。