特征码

　　特征码（attribute code）用来判断某段数据属于哪个计算机字段。共计40个字符。

　　概念

　　特征码的获取不可能再是简单的取出一段代码来，而是分段的，中间可以包含任意的内容（也就是增加了一些不参加比较的“掩码字节”，在出现“掩码字节”的地方，出现什么内容都不参加比较）。这就是曾经提出的广谱特征码的概念。

　　基于特征码的网页去重

　　随着网络技术和信息技术的飞速发展，网络已经成为人们获取信息的一个重要途径。现有的搜索引擎面临的最大一个问题就是返回的结果集中包含大量重复的信息。如何更有效地帮助用户获取所需要的信息，能够快速、准确地为用户提供信息，是网络信息服务面临的新课题。优化搜索结果可以采用多种手段，如通过提取网页的特征进行基于内容的信息检索，利用用户反馈的信息进一步精确检索结果，将结果集中的重复信息尽可能地消除等。

　　由于网络信息分布的特点，网站上的信息存在相互转载及镜像站点等情况。出现相同网页主要有以下几种情形：网页的URL完全相同；网页的URL形式不同，但网站域名所对应的IP是相同的；URL虽然不同，但网页内容完全相同；URL不同，为不同的网页形式，但网页上主要内容是相同的。本文主要讨论对于网页内容重复性的消除。

　　网页去重系统结构

　　网页为半结构化的信息形式，它与单纯的文本文档并不完全相同。网页中的有效信息主要包括以下几方面的内容：网页标题、网页正文、导航信息、超链接信息、图片声音等多媒体信息等。从以上信息中可以提取出有关网页内容的一些特征。首先对检索结果集中的网页进行预处理，将其余信息屏蔽，获得网页的正文信息，然后用后面介绍的算法对网页正文进行去重处理。即判断是否已经有相同内容的网页在结果集中，若有，则进行删除或合并处理，若没有，则将该网页保留在检索结果集中。网页去重系统主要结构如图1所示。

　　基于特征码的网页去重算法

　　对网页进行去重处理，实质上是从一批网页中将内容相同或相近的网页分为一类，进行聚类处理。用传统算法进行聚类处理，只能将同一大类的网页聚合为一类，与传统意义上的聚类处理不同，网页去重需要对网页进行较为精确的归类。如果严格按照网页内容进行分类，则分类结果中类别会很大，导致在确定一个网页属于哪一类时计算所花费的时间过大。如果直接将网页正文逐字进行匹配处理来实现归类，也同样会出现计算量过大，而在响应时间上无法承受的问题。较好的方法是从网页正文中抽取出少量信息构成特征码，在归类时，以特征码取代网页，通过判断特征码是否相同或相近来判断相应的网页内容是否是重复的。

　　（1）网页特征码

　　网页特征码首先必须能够较为全面地反映网页的内容，其次为了计算上的方便，特征码在长度上有一定的限制，不能太长。采用以下方法构造网页特征码:特征码由主码和辅码两部分构成。依次提取网页正文中每段段首的第一个字，组成主码。再从各段中将每一个标点符号前面的一个字提取出来，依次构成辅码，考虑特征码长度方面的限制，辅码提取中只对每段的前n个标点符号进行提取。若某一网页正文共有5段，取n值为3，则提取出来的网页特征码结构如图2所示。

　　（2）网页重复性判断算法

　　提取出网页的特征码之后，下一步工作是依据特征码判断网页正文是否重复。假设网页a对应的特征码为Ta，网页b所对应的特征码为Tb，判断a与b是否为重复网页的主要步骤为：

　　1)比较Ta与Tb的主码部分，若两者主码完全相同，则认为网页a与网页b是内容相同的网页，转4)，否则转2)；

　　2)若Ta与Tb的主码比较结果为以下情形之一：①其中一个的主码为另一个主码的真子集；②两者不互为真子集，但两者主码取交集的结果较大，则转3)作进一步判断；若两者主码取交集为空或交集结果较小，则认为网页a与网页b是内容不同的网页，转4)；

　　3)对Ta、Tb主码的交集，即两者相同的主码部分进行处理，判断对应的辅码是否相同，若完全相同或大部分相同，则认为网页a与网页b是内容相同的网页，若相同的辅码很少，则认为网页a与网页b是不同的网页，转4)；

　　4)算法结束。

　　在判断算法中，对于以下情况认为两个网页是相同的：一个网页内容是另一个网页的部分内容，或两个网页虽然不完全相同，但其中大部分内容是相同的。可以通过设定一定的阈值对算法中的不确定因素进行判定。如两者交集结果超过其中任何一个的80%，则表示两者交集结果较大，反之当小于20%时，认为两者交集结果较小;在对辅码进行比较时，当相同的辅码占80%以上时，认为辅码大部分相同。可以根据实际检索的结果，将阈值调整至一个比较合适的取值范围，获取较为满意的检索结果。

　　（3）算法有效性分析

　　网页重复性判断算法是否有效，关键是特征码与网页正文内容之间的对应关系，若不同内容的网页对应的特征码是不同的，则保证了算法的有效性。若出现多个不同内容的网页有相同的特征码，则会将不同内容的网页归并到一类进行处理。若单纯从文字上看，以中文网页为例，常用的汉字大约为6700个，特征码主码的长度为n，则对于不同网页出现相同特征码主码的概率为1/(6700)n。虽然对于一些热门新闻，段首文字多以“据报道”、“新华社”等文字开头，若有m段文字以这样的固定词开头，(m小于n)，出现重复特征码的概率为1/(6700)n-m，当n-m或n的取值稍大，如大于5时，这样的概率值是很小的。同时在算法中，还考虑了辅码的作用，当出现主码部分相同时，进一步判断辅码的分布以确定特征码是否相同。

　　算法实现

　　（1）数据结构的选择

　　检索结果集中的网页具有动态变化和数量巨大两个特征，必须选择一种合适的数据结构，减少去重过程(相同网页合并过程)的比较次数，同时又能较好地表示动态变化的特征码集合。二叉排序树能较好地满足上述要求，选择二叉排序树作为算法实现的主要数据结构。二叉排序树或为一空树；或是具有下列特征的二叉树：1)若左子树不空，则左子树上所有结点的值均小于它的根结点的值；2)若右子树不空，则右子树上所有结点的值均大于它的根结点的值；3)它的左、右子树也分别为二叉排序树。

　　为描述方便，以下所说相等是指两个特征码对应的网页内容相同或相近，不等是指两个特征码对应的网页内容不同。当出现特征码相等的情况时，需要进行合并处理。算法采用扩展二叉排序树为主要的数据结构，在传统的二叉排序树的每个结点中增加一个指针，该指针指向由特征码构成的链表，称为“辅指针”。辅指针指向与该结点对应网页内容相近的网页特征码，这样就可以较方便地处理网页合并的情形。最终保留在检索结果集中的是扩展二叉排序树中各结点表示的特征码对应的网页。扩展二叉排序树结构如图3所示。

　　（2）特征码归类过程

　　二叉排序树的构建过程也就是对特征码进行归类处理的过程。对于一个新处理的特征码，在二叉排序树中没有找到可以合并的结点时，直接对该特征码进行插入操作即可。在二叉排序树中找到相等的特征码时，该特征码要进行合并操作，而不同于普通意义上二叉排序树的查找操作。当二叉排序树为空时，将新处理的特征码作为新结点插入树中，插入新结点时，该结点的辅指针为空。当二叉排序树非空时，首先将新处理的特征码与根结点表示的特征码比较，若相等，则进行合并处理，若不等，则根据新处理的特征码与根结点表示的特征码之间的大小关系，分别在左子树或右子树上继续进行比较，在比较过程中，若出现相等的情形，则将新处理的特征码与相应的结点进行合并，若在整个比较过程中，始终出现的是不等的情况，则说明新处理的特征码所对应的网页内容还没有在二叉排序树中，将其作为一个新接点插入。

　　假设网页x对应的特征码为Tx，网页y所对应的特征码为Ty，Tx为新处理的特征码，Ty为二叉排序树中出现的与Tx相等的特征码，采取以下策略进行合并：1)若Tx与Ty的主码完全相同，则二叉排序树不需要做任何改动，直接将检索结果集中网页x删除；2)若Tx主码为Ty主码的真子集，则将Tx与Ty辅指针所指向链表中各结点的特征码进行比较，若无相等的特征码，则将Tx作为一个新结点插入Ty辅指针所指向链表中；3)若Ty主码为Tx主码的真子集，将Tx取代二叉排序树中结点Ty，同时将Ty依据2)中的原则插入Tx辅指针所指向链表中；4)Tx与Ty不互为真子集，但两者主码取交集的结果较大，处理方法同2)。

　　（3）算法效率分析

　　不管新处理特征码是进行合并或插入，均要先进行查找比较，已确定插入的位置或合并的结点。对二叉排序树进行比较，在结点出现概率为随机概率分布的情况下，平均查找长度小于等于2(1+1/m)lnm，m为二叉排序树中结点的个数，平均查找长度与logm成数量级，即比较过程的时间复杂度为O(logm)。插入结点过程只是一些指针的移动，时间可以忽略不计。由于特征码主要由各段段首字及每段中前n个标点符号前的文字构成，因此对特征码的提取不需要对整个网页正文都扫描一次，特征码的提取时间与处理的网页正文长度有关，可以看成是一线性关系，特征码提取的时间复杂度为O(n)。1

　　基于特征码技术的攻防策略

　　当前单纯意义上的病毒已逐步被木马、蠕虫所代替。操作系统的升级为后门病毒大规模的破坏提供了便利，并且从自启动发展为注册系统服务，从单进程发展为守护进程和远程线程注入，甚至采用驱动技术来隐藏后门程序，让用户手动查找愈加困难。在这种局势下，各种新技术和杀软被不断开发出来，和病毒进行着没有硝烟的较量。2

　　引言

　　所谓特征码，就是防毒软件从病毒样本中提取的不超过64字节且能代表病毒特征的十六进制代码。主要有单一特征码、多重特征码和复合特征码这三种类型。特征码提取的思路是：首先获取一个病毒程序的长度，根据样本长度可将文件分为若干份(分段的方法在很大程度上避免了采用单一特征码误报病毒现象的发生，也可以避免特征码过于集中造成的误报)，每份选取16B或32B的特征串，若该信息是通用信息或者全零字节则舍弃，认为或随机调整偏移最后重新选取。最后，将选取出来的几段特征码及它们的偏移量存入病毒库，标示出病毒的名称即可。根据这个思路可编写出特征码提取程序实现自动提取，并保存病毒记录。在扫描病毒时，防毒软件将目标文件通过模式匹配算法与病毒库中的特征码进行比对，以确定是否染毒。

　　特征码的检测与处理

　　（1）特征码的定位

　　单一特征码扫描，就是从病毒样本中提取连续的能标示此病毒的若干个字节。其好处在于开销小，便于升级和维护病毒库。但这种技术容易导致误查误杀，已较少使用。对于多重特征码，可在单一特征码扫描的基础上进一步提取不连续的若干段特征码，仅当待检测文件完全符合这多段特征码时才报苦。这样可以减少误杀率，提高查杀的准确度，因此成为多数防毒软件的首选技术。用“逐字节替换法”可手动定位多重特征码。把目标木马服务端或病毒逐字节地替换为OOh或fh(其他亦可)，每替换一次存为一个文件，然后对生成的几份文件杀毒，未被删除的就是被修改了特征码的文件。汇总被修改的字节就得到了杀软对该木马或病毒所定义的“特征码”。然而，手工操作和占用空间都过于庞大，可用分段法加以改进，即逐步缩小特征码所在范围。实验中选取某防毒软件对黑客工具进行特征码定位。首先以128 B为替换单位，从查杀后的文件可知特征码的偏移和范围，之后还原代码，再以32 B为单位对该范围进行替换并查杀，最后使用逐字节替换定位出连续的特征码字节。这样每次仅需几兆的空间，且速度很快。整个由粗略到精细的定位。至此，多重特征码定位成功，只需任选一段特征码来定位，修改后就可以逃过查杀。

　　（2）特征码的修改

　　对定位后的特征码进行修改便能逃过查杀。对可执行文件，要根据汇编代码来修改特征码，首先进行反汇编，使用调试器(如ollydbg)调试程序，并根据特征码的文件偏移地址转换成的虚拟地址找到汇编指令。修改方法主要有：修改字符串大小写法、等价替换法、指令顺序调换法、通用跳转法。许多病毒采用自动变形技术来逃避特征码检测，即所谓的多动态病毒，它在外观形态上没有固定的特征码川。病毒的多态致使对其代码段的加密能完全改变原有特征码，因此摇在零区域加入解密代码来解密，然后使用JMP指令跳回原指令代码执行，由于对某一字节执行XOR两次后可还原代码，因此可以手动加密代码，下次病毒执行时，可以解密代码并执行。致使特征码完全变样，达到免杀。

　　策略改进与技术展望

　　特征码技术具有低误报率、高准确性、高可靠等不可比拟的优势，其技术机理和执行流程也非常成熟。为了弥补特征码技术的被动性，建议辅以如下几种防病毒新技术：

　　（1）输入表关联特征码

　　病毒运行时需要调用存在于输入表中的API函数，如果将特征码锁定在可执行文件的“敏感”区域—输入表中，由于输入表位置固定，因此不能用通用跳转法来修改特征码，这样能有效地保护特征码。

　　（2）伪特征码

　　防病毒软件可以检测某一段自己的特征码，如果发现它被填充为O，那么就激活原先设置的随机效用的伪特征码并报替，就算能找到这些特征码，对于查杀没有影响。

　　（3）广谱特征串过滤技术

　　为应对不断变化和未知的病毒，启发式扫描方式出现了。启发式扫描是通过分析指令出现的顺序，或特定组合情况等常见病毒的标准特征来决定文件是否感染未知病毒。因为病毒要达到感染和破坏的目的，通常的行为都会有一定的特征，例如非常规读写文件，终结自身，复制自身到系统目录，修改注册表某一键值，调用特定的AIP函数等等。所以可以根据扫描特定的行为或多种行为的组合来判断一个程序是否为病毒。这种启发式扫描比起静态的特征码扫描要先进的多，可以达到一定的未知病毒处理能力，但仍会有不准确的时候。特别是因为无法确定一定是病毒，而不可能做未知病毒杀毒。3

　　本词条内容贡献者为:

　　陈红 - 副教授 - 西南大学