按日归档: 2007/04/16

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

特征码扫描技术是反病毒技术中的常规武器,虽然特征码扫描技术有着一定的局限性,但是,改进的基于特征码扫描技术的广 谱特征串过滤技术却有着无比的优越性和广阔的应用前景。但是,无论是上面提到的哪种技术,最终都难以逃脱扫描算法的效率要求。而学过《数据结构》的读者应 该知道一种快速的字符串扫描算法叫做“模式匹配算法”,这种算法可以对字符串进行快速扫描。但是,深入进去就会发现,我们的特征码扫描算法中经常会用到通 配符,如:%和*(这里我令%匹配一个字符,*匹配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数组不太了解,还是建议您找出教材来好好看一下。本算法的效率是比较高的,至于它的计算复杂度,我想在这里我就不能做过多的说 明了,有兴趣的读者,或者从事反病毒研究的读者,希望能对你们有一定的帮助,同时,如果有不对的地方,可以在黑防的论坛上面提一下,以期获得改进。
后记:对于一个真正的程序员来说,其任务决不应该仅仅只是机械地拖拖控件,动动鼠标。更重要的应该是编程开始前的软件的整体安排和设计,而相关算法设计也 应该是非常重要的一部分。对于一个扫描软件来说,其扫描算法的设计也定是其精华所在。本文专门对算法进行相关分析,希望能够对您有所启发。

Read: 962

掀开电脑维修的黑幕

电脑维修是一个很专业的行业,也正因为专业和普通人难以了解,因此存在着一些惊人的内幕和令人难以想象的行业灰色甚至是黑 色操作,当然,绝大多数维修业者都是勤恳专业遵纪守法的,但有极少数维修企业或者个人、作坊,他们的行为是我们不了解内情的局外人初看起来无法理解的。   计算机的主板和显卡,作为电子电路行业中的高精尖领域,其制造和维修的技能、设备和方法 专业性都很强,普通人不要说掌握,就算眼睁睁看到了,也未必能了解维修人员在干什么。大家可以拿电视、影碟机或者是音响内的电路板,去和电脑主板、显卡比 较一下,就会发现电脑的板卡要精密得多。  电脑板卡通常是4层板、6层板甚至是8层板,上 面的布线密密麻麻,大量体积极小的贴片元件和高集成度芯片占绝对主导地位,只有各个重要核心部件比如CPU、GPU的供电模块才会用到直立元件。一块典型 的主板在其30厘米*20厘米的表面上会有1000多个各种零件,而其中某些零件(比如集成显示核心的北桥芯片)一个零件就集成了几千万个晶体管!这些在 主板和显卡上面司空见惯的景象,在其他产品,比如家电产品和工业用嵌入式设备的电路板上是难以看到的。  我 上大学的时候还做过充电器,电路板都是自己画自己泡的,我记得上面还有个分立元件的桥式电路,跟现在的电脑板卡比起来真是笑掉大牙了。哈哈。这么说吧,电 脑的庞大规模和飞速发展造成了电脑板卡的高度专业化和复杂化,而这一点又造成了电脑零部件制造和维修的专业性和复杂性,从而在产业化的大潮中,为各种灰色 现象提供了温床。  [常见三种维修企业形式]
电脑维修企业一般分为三种类型

[厂商售后服务部门]第 一种是厂家或全国代理商自己开办的维修售后服务部,专门为自己的产品提供维修,不是自己的产品不接或者很少接,这通常都是大厂和很大的全国代理开设的。特 点是维修人员比较精通本职,但通常不是学识渊博的全能人才,维修点产品资料、备件都很齐备,保修期内产品占了工作量的大部分,因为维修人员大部分以工资为 主,所以黑暗现象少。这类维修点的问题一是一般都在很偏远的工业区,当然可以通过购买的经销 渠道去返修,但时间会比较长;二是超过保修期和不在保修范围内比如烧损、硬损的产品维修费比较贵。这是因为,有很多厂家对外的维修中心并不真正维修,只能 叫备件更换中心,主要的任务就是把有问题的配件换下来返回到真正板卡生产厂家去维修,他自身并没有维修设备,也没有芯片级的维修工程师,所以保修还好,只 要花钱修就会很贵,一个爆浆电容也敢收几千给换个主板。
[授权专业维修中心]
第 二种是大型的专门维修企业,这一类通常同时是某个或者某些厂家签约的特约维修中心,这些厂家自己不建对外售后服务部门,委托给专业企业来做,比如IBM笔 记本的维修通道蓝色快车。这类维修企业有很多特点跟第一类相似,比较正规,除了做厂家维修点外,同时也接其他产品,技术比较可靠,产品资料、备件都齐全, 缺点和第一类相同,只要花钱修就比较贵。
我家里的苹果ibook笔记本坏了送到特约维修中心,他们同时还做HP、Compaq等笔记本的维修,维 修人员跟我说我这个需要换主板,如果不在保修期内,换一块主板要将近七千元。我的天!我买这二手ibook还不到七千的一半呢!更奇怪的是维修人员告诉 我,修的话是免费,如果不修就要交85元的检测费,这是因为这类企业在修保修期内的产品虽然不从客户收费,但他们要从签约厂家收钱,如果客户不修,那他们 就没法从厂家收费了。

[个人维修商户]第 三种是散布在中关村内各个地方数量众多良莠不齐精华与糟粕并存的私人维修企业。这类企业通常都是在厂家或者特约维修做的时间长技术高的资深维修工程师,为 了多挣钱,自立门户出来创办的,因此公平的说虽然大型维修店都很专业,但技术最精湛水平最高的维修师傅往往在私人维修点。同时,私人维修点主要靠修水货和 过保、保外产品,它们的运营成本最低,操作方式最灵活(除非是黑心维修店,否则绝对不会为了一个电容换主板),维修价格最便宜,有的时候要比前两类低非常 多,这就是为什么私人维修点大江南北如火如荼这么红火的缘故。但是,因为私人维修点都是为了 挣钱,而且挣的都是专业基础差的最终用户的钱(相对而言,第二类企业主要利润来自签约厂家,而厂家是非常懂行的;至于第一类企业,则几乎没有利润需求), 所以各种不正规和丑恶现象也都会看到。当然,这并不是说前两类企业就没这方面的问题,只是出现机会少。

[变废为“宝”]

在中关村的中海等市场经常能看到卖废CPU、内存、硬盘等配件的柜台或个人,对,就是废件,是完全不能用的。比如一个坏的P4 CPU要卖到100多块钱,一个坏的主流容量的硬盘也要卖100元左右,其他坏显卡坏内存等等也各有其价格。谁会买废件呢?买了又有什么用呢?
可 是如果去这些柜台观察一天,就会发现这些废件,偏偏就有人买,这是为什么?当一个电脑用户的主机坏掉了,故障现象正好是黑屏,电脑根本点不亮,而急于修好 电脑的用户又在不知不觉中,把电脑搬到了一个无良的维修点,那么他就要当心了。很多黑屏故障都是因为接触不良或者是电源线、插座坏掉,更严重一些的是电脑 内的电源坏了(我们知道电源是比较便宜的配件),所有这些情况加起来占了黑屏现象的一大部分,而在这些情况下,电脑内部有价值的零部件都是完全没有问题 的,这样就使得维修点没钱可赚,正规来办只能收取一个手工费;这个时候黑心的维修点就会使出一招黑手(不妨叫做狸猫换太子),把电脑上值钱的好的配件取下 来,换上一些坏掉的,反正搬来的时候就黑屏。
维修人只要告诉用户说,您的电脑烧了,很多东西 都坏掉了,如果全修好要多少多少钱(一个高的吓人的数字)。如果用户修,就把用户电脑上的好零件再都换回去,用户搬回去的其实还是自己的电脑,但为了接触 不良甚至是插座、电源线故障付出了沉重的代价;不修,还给用户的时候表面上还是一台黑屏的电脑,但其实好的零件已经全到了维修点手里,用户搬回去的电脑里 都是废件就这么被坑了。对于笔记本用户,最危险的是液晶屏有可能会被无良维修点换掉,这比CPU内存什么被换更加可怕多了!那么给用户这些坏件哪儿来的 呢?你不能说把人家好件都拿走什么都不给装回去,那就漏了。现在大家知道为什么中海市场的坏件都有人买了吧。
[非常规手段]
“狸猫换太子”还会出现在同样是黑屏的情况下,这时虽然确实有坏掉的配件,但用户不愿意花那么多钱来修,想搬别的地儿再看看,货比三家么对不对?黑心维修点是不可能轻易放过你的,都进来了,想全身而退?哼哼……狸猫换太子法有一个共同特点,就是基本都作用在黑屏的电脑上,这是因为买来的坏件通常都是彻底不能用的,如果不是黑屏就无法互换,这种故障现象的消费者要格外注意。相 比于“狸猫换太子”,少数维修点还有一招更黑的。我们知道维修板卡的收费通常都分成若干档次,不同的维修档次收费不同,修不好当然不能收钱(能修好客户不 修例外,有些大型店要收检测费)。所以用户送去维修的板卡,经过检测以后可以报价的,肯定都是能修好的,而且我要透露个秘密给大家,这时候很多都在检测过 程已经修好了,但是不能跟客户说就是了。这个时候报价给客户,都是在维修人员心有成竹的时候,关键就看用户掏不掏钱了,
如果掏钱当然一切妥当,如 果用户嫌贵不愿意修,维修店难道白白把修好的板卡送出门?这当然是不行的,因此通常维修点都会把板卡重新弄坏,这里面的“弄坏”就有学问了,讲良心的维修 点通常会给对方恢复原状,自己自认倒霉白忙活一阵,黑心的维修业者,或者因为嫌麻烦,比如把弄好的各个焊点再开焊,把换上去的好元件再换下来,或者因为自 己损失了时间和精力,甚至出于报复心理,会把板卡彻底弄坏,谁叫你不让我修!老子是你耍得吗?让你也好受不了。
如 何把一片板卡彻底弄坏而表面上还看不出来,这在行业内有很多种黑手法,我在采写过程中就亲眼看见过一种:把一片主板用力撅成弧形,听到里面的焊点“噼噼啪 啪”开裂声,松手后主板虽然恢复“原状”,但是已经报销了。如果说“狸猫换太子”是损人利己,那么这一招是纯损人,不利己,咱们不妨叫它做“玉石俱焚” (好像有点褒奖的意味了?……小编的文学修养确实不行啊)刚才说到的是因为修好了客户不付钱 而导致产品被弄坏,更可恶的是少数水平差心肠黑的维修点,产品修不好,他们也会把板卡完全毁坏,这种人的混帐逻辑是,我这里修不好的东西,你到别人那儿给 修好了,这能行么?这不是给我难看么?所以进了这种地方的板卡,只要没修好,拿出来就别想再修了。
[维修成本雾里看花]
除 了换件和弄坏,再有一种就是虚报、夸大问题,这恐怕是最常见也最被大家所痛恨的方式了,明明实际上很小的问题,到了黑心维修点手里经过检测,就变成了很大 的问题,需要花大把银子去修;明明很简单就能排除的故障,非得给你从前到后换一个遍,大把银子掏出去才能修好。这也罢了,更差劲的是换上去的零件往往图便 宜质量不过关,维修、焊接技术往往粗糙的要命,虽然当时看着修好了,但实际上板卡质量大大打了折扣,过不了多久电感烧毁、电容爆浆、焊点开焊全出来了,还 得回去再受罪。举个例子,某知名日本品牌笔记本用户,花一万多元买的笔记本坏了,拿到特约维 修点,检测后说是主板损坏,换一块要花四千九(比五千还少一百,呵呵,看来维修人员也学过心理学),机主一听吓坏了,赶紧拿出来换了一家私人维修点,重新 检测了一阵,说是主板通过各种高科技仪器能修好,要600块,机主高兴坏了赶紧签单不一会儿修好了兴高采烈付了钱抱机器走了,其实只是换了一颗主板上的电 池。再比如,笔记本的液晶屏不亮了,用户急坏了马上拿到维修点去修,维修点热情接待手脚麻利 迅速检测完毕:液晶屏坏,需换屏,费用在4000元左右。用户这叫一个难受,换吧,4000多块大洋,不换?上万的笔记本就歇了。左思右想只好万般不情愿 的拿出一大笔银子,换了屏走了。其实笔记本屏的问题是多种多样的,比如背光灯管坏了,就会造成不亮,虽然液晶屏幕本身没问题,而灯管是可以换的;再比如笔 记本液晶屏的信号线和电源线(简称屏线)都是通过合页从底座进入上盖,合页本身比较脆弱,而且经常开合,遇到外力磕碰或者挤压就容易造成屏线断裂,从而使 得液晶屏黑屏。
[谨防维修黑手]
虚 报夸大到了极致,就变成“有故障要修,没故障创造故障也要修”。放在黑心维修点检测的电脑,往往是小问题被检测成大问题,没问题被检测成有问题,总之不赚 一笔是不会放你走的。这种手法可叫做“无中生有”。这类欺骗消费者的方法其中有一种需要特别加以注意,送修的机器往往被检测出硬盘有坏道数据全部或者大部 分丢失,需要做数据恢复,收费少则数百元多则数千元。用户觉得太贵,换到别家试试,发现别家确实也检测出来同样的故障,但却无法修复。用户大惑不解之下, 心有不甘的拿回到黑心维修点付了高额恢复费,数据果然全部恢复了!这是怎么回事?说穿了一钱不值,黑心维修点先把数据拷贝出来,然后用某种方法把硬盘轰出 一些坏道或者逻辑错误,然后,就可以正大光明骗钱了!这一招的猥亵之处还在于,除了他没人能解决这个问题。见 识了一些常见的骗钱手段,我们现在再来看看如何防止这种情况的发生。原则就是,你对产品了解越深刻,被骗的可能性就越小,反之就越大,菜鸟是最容易被骗 的。产品送修前,一定要排除软件方面的故障,比如中了病毒或者木马,造成系统死机、不稳定,主板或者显卡bios刷新失败会使得电脑黑屏,此时可通过热插 拔法或者盲操作法将问题恢复,相关操作方法网站上和各类电脑杂志多有介绍,这些都是DIYer自己动手能够解决的故障,实在解决不了要到维修点换 bios,说得清清楚楚也能避免被忽悠。除了软件问题,还要考察是否因为环境问题造成电脑故障,比如电源插线板、电源线接触不良造成的频繁重起动;电网电 压不稳造成电脑死机(电压过低会造成死机,电脑过高和电涌会造成部件损坏)、操作环境灰尘太多造成的电脑不稳定,通常可通过清洁内部消除短路和断路来解 决。总之,一切能用上的手段都应该用上,按照统计,这样能解决电脑故障中的大部分,只有少部分是用户确实无法解决,需要专业维修的。电 脑故障确实属于送修范围,就应该精心挑选维修点。这时的原则是,对于保修期内产品,一定要送到厂商维修点或者特约维修点;对于保修期外产品和无保修的产品 (一些水货),不要选择厂商维修点或特约维修点(除非你很有钱),而应该挑选一家信誉好、技术高的商业维修点。如果不知道维修点的情况,但还是必须送修的 话,那么送修的时候,最好把自己产品主要部件(cpu、主板、内存、硬盘等)的详细规格和编号列表记录清楚同 时给维修点看,或者让对方收机的时候签字确认,如果可能的话,应该把硬盘事先取下来,把故障现象详细写明,并写明排除故障的各种努力,同时把已经排出的问 题也都附上,让维修点知道你对情况很清楚了解,如果能有很懂行的人陪同去维修点就更好。尽量找透明开放操作的维修点,有可能的话最好做立即检测而不是存放 后几天内通知,检测阶段最好全程仔细参观,各个关键步骤不懂的话随时发问,不要怕招人烦,毕竟不被骗要紧。总之,只要细心大胆,不盲从不迷信,遇到问题多 问多想,一定可以把被骗的机会减少到最低的。

Read: 827

走出Windows XP系统最小化克隆误区

在病毒猖獗的互联网时代,小小的Ghost给大家帮了不少忙!–3分钟克隆,3分钟恢复,瞬间系统还原如初!  然而,人们总是在追求更简便的应用,于是,网络内外到处都有关于Ghost最小化克隆的经验技巧。可令人遗憾的是,对目前Windows XP的最小化克隆,误导性的操作比比皆是,以讹传讹!  误导之一:删除C盘根目录下的页面文件Hiberfil.sys   一种做法是教读者一步步打开“控制面板→电源选项→休眠”,取消勾选“启用电源”;另一种做法则更卖力——在DOS 6.22里找到Deltree.exe命令文件,复制到系统盘根目录,然后再通过各种方式将电脑启动到纯DOS,执行Deltree Hiberfil.sys命令以将其删除–因为在Windows下删不掉Hiberfil.sys!  误导之二:移动虚拟内存或删除Pagefile.sys文件  也有两种误导方式:一是移动虚拟内存到其他分区;二是同上面一样,启动到纯DOS通过Deltree来删除。   其实,以上两个文件尽管很大(默认情况下,Hiberfil.sys一般为255MB,Pagefile.sys一般为384MB),但用Ghost软 件进行克隆时,Ghost并没有将它们复制到.gho文件里面去–我曾用Ghost 6.0/7.0/8.0等多个版本反复进行过多次对比克隆,不管是系统盘有没有这两个文件,克隆的最终结果都是433351KB(423MB)左右;同 时,用鬼探测者(GhostEXP.exe)打开.gho文件,也都没有Hiberfil.sys和Pagefile.sys的身影!既然如此,何必多此 一举!  那么,使要克隆的系统盘最小化,可取的措施有哪些呢?  1. 通过Sfc.exe /purgecache清除文件缓存,这是最见效的一招,可将系统减少370MB左右;  2. 通过对系统盘进行搜索,找出所有的.cab、.zip压缩包,移走或删除(能减少85MB左右);  3. 通过Cleanmgr(附件里的磁盘清理工具)以及对 .tmp、$ 临时文件的搜索等方式删除临时文件;  4. 至于帮助文件、字体文件、桌面墙纸文件等,可以移走或删除;  5. 对于系统自作主张为你安装的组件,比如MSN、OE、附件里的游戏等等,可通过“添加/删除程序”将其卸载;  6. 很重要的一个习惯:将所有程序都安装在另一个分区,以减少系统分区的大小;   7. 删除系统盘根目录下的用于系统还原的记载及备份——对于XP系统来说,即便是系统刚装好,也可能在System Volume Information目录中存在几十乃至上百MB的备份文件(单击“工具→文件夹选项→查看”,取消勾选“隐藏受保护的操作系统文件”即可看到)。这一 步一般放在最后也就是克隆之前做,这样才能彻底清空,因为只要你的系统还原功能没有关闭,在其监视之下你所做的一切修改都将在C:System Volume Information里备案!当然,删除了它们,在此之前所做的一切修改也就不能还原了!

Read: 758