资源列表

一、SM3算法介绍SM3是国家密码管理局编制的商用算法，它是一种杂凑算法，可以应用于数字签名、验证等密码应用中。其计算方法、计算步骤和运算实例可以在国家商用密码管理办公室官网查看。
该算法的输入是一个长度 L 比特的消息m，其中 L < 2^64 ，经过填充、迭代压缩后，生成一个256比特的输出。
二、算法步骤2.1 填充长度假设消息m 的长度为 L 比特。首先将比特“1”添加到消息的末尾,再添加k 个“0”, k是满足L + 1 + k ≡ 448 mod 512 的最小的非负整数。然后再添加一个64位比特串,该比特串是长度L的二进制表示。填充后的消息m′的比特长度为512的倍数。
在具体的实现过程中，首先获取消息超过512比特整数倍部分的长度L。由于在最后一个分组分组中，要将1个比特位“1”添加到消息的末尾，并且要添加64比特来存储消息的长度。
当 L <= 512-(64+1)时，可以直接填充比特位“1”、 512-(64+1)个比特位“0”、64位的消息长度，；当 L > 512-(64+1)时，最后一个512比特的分组不够填充，需要再添加一个512位的分组，此时填充的“0”的个数为k=512-L-1+(512-64)。
2.2 迭代压缩在迭代的过程中，首先对填充后的消息m′按512比特进行分组。然后对每一个分组进行迭代压缩。迭代方式如下:
FOR i=0 TO n-1 V (i+1) = CF (V (i) , B (i) )ENDFOR上述算法中，n是填充后消息分组的个数，即有多少个消息分组，就迭代多少次。Vi是256位的向量，V0为初始值IV，即前一个分组计算完后的结果Vi会当作下一个分组的参数传入CF函数中，此即是密码学中扩散原则，即原始消息的任意比特位的变化都会造成结果产生大的改变。
在CF压缩函数中，需要用到的参数有向量V (i)、B(i)、常量Tj、Wj和Wj′。其中Wj和Wj′是对512比特的消息分组进行扩展后产生的132个字。由于消息分组有多个，Wj和Wj′也对应有多个。在具体实现时，要在CF函数中对每一个消息分组进行消息扩展计算。
在迭代完最后一个消息分组后，CF函数返回的值Vn就是最终的计算结果。
三、实现过程3.1 创建项目打开Eclipse创建项目SM3，在项目SM3中创建类SM3。创建完成后目录结构如下所示：

3.2 定义算法中的常量、函数算法中需要用到函数FFj、GGj、P0、P1、常量Tj等，以及原始消息、填充后的消息定义如下：
// 字符集private String charset = "ISO-8859-1";// 要哈希的字符串private String message = "abc";// 填充后的字符串private String PaddingMessage;// 获取常量T0和T1private int T(int j){ if(j <= 15){ return 0x79cc4519; }else{ return 0x7a879d8a; }}// 布尔函数 FFprivate int FF(int X, int Y, int Z, int j){ int result = 0; if(j >= 0 &&j <= 15) { result = X ^ Y ^ Z; }else if(j >= 16 && j <= 63) { result = (X & Y) | (X & Z) | (Y & Z); } return result; }// 布尔函数GGprivate int GG(int X, int Y, int Z, int j){ int result = 0; if(j >= 0 &&j <= 15) { result = X ^ Y ^ Z; }else { result = (X & Y) | (~X & Z); } return result;}// 置换函数P0private int P0(int X){ return X ^ (CircleLeftShift(X, 9)) ^ CircleLeftShift(X, 17);}// 置换函数P1private int P1(int X){ return X ^ (CircleLeftShift(X, 15)) ^ CircleLeftShift(X, 23);}
在上述函数定义中，用到的CircleLeftShift函数用于实现循环左移，它的两个参数分别是要移位的32位int型数据和循环左移的位数。在循环左移中，循环左移k位，相当于将二进制位最左边的k位移动到最右边。
3.2 调试方法编写在课本的运算示例中，每一步运算的中间结果都有。在编写算法时，每写一步都要与课本上的中间结果对照，以确定当前得到的中间结果是否正确。由于算法运行的中间结果都是二进制形式，为方便查看，编写了dump方法用于将中间结果显示为16进制的形式。如将填充后的消息打印出来的dump方法如下：
private void dump() { System.out.println("========开始打印========"); try{ byte bts[] = this.PaddingMessage.getBytes(this.charset); for(int i = 0; i < bts.length; i ++) { if(i%16 != 0 && i%2 == 0 && i != 0){ System.out.print(" "); } if(i%16 == 0 && i != 0){ System.out.println(); } System.out.printf("%02x", bts[i]); } }catch(Exception e){ System.out.println("Error Catch"); } System.out.println("\n========结束打印========");}
在输入消息为“abc”的情况下，打印填充后的消息的十六进制形式如下所示：

其中开头的61、62、63是字母a、b、c对应的ASCII码，80是填充消息时附加的比特位1，该比特位与后面填充的比特位0，构成了二进制1000 0000，所以对应的十六进制是80。最后的18也是十六进制形式，对应的十进制是24，表示消息的长度是24位。
由于在使用Java编写SM3算法时，计算的中间结果有字符串、整型数组等多种类型，为方便查看对应数据的十六进制形式，编写了多个dump方法，用于打印各种类型的数据。
/* 将字符串输出为16进制形式 */private static void dump(String str)/* 将整型数组输出为16进制形式 */private static void dump(int nums[])
3.3 遇到的错误及解决方案3.3.1 循环左移计算结果偶尔不正确在Java中，只有按位左移<<操作符，按位左移溢出的比特位直接丢弃，而SM3算法需要的循环左移需要将溢出的比特位存储到操作数最右边。
在实现循环左移时，假设要移位的32位比特位的数据为Y，则循环左移位可以分为三步：

把Y按位左移k位的值赋值为l，此时l最右边的k位为0；
把Y按位右移(32-k)位的值赋值为r，此时r左边的(32-k)位为0；
将l和r进行按位或运算，即得到循环左移后的结果。

例如将0x1234 5678按位左移8位，则Y左移8位得到 l=0x3456 7800，Y右移32-8=24位得到r=0x0000 0012，最后将l和r进行按位或运算得到最终结果0x34567812。
循环左移的实现过程如下：
// 将x循环左移N位 private static int CircleLeftShift(int x, int N) { return (x << N) | (x >> (32 - N)); }
在使用此方法进行按位左移时，发现偶尔计算出来的结果与预期不符合。经过调试，发现是在按位右移时没有得到预期的结果，导致最终循环左移结果出错。具体原因及分析如下:
按位左移是直接在右边补0，而按位右移分为两种情况，一种是逻辑右移（有符号移位），一种是算术右移（无符号移位）。
逻辑右移是当最高位为0是，说明这是一个正数，右移时在最左边补0；当最高位为1时，说明这是一个负数，负数在计算机中以补码形式存储，所以逻辑右移时在最左边补1。
而算术左移在移位时忽略符号位，即无论最高位是0还是1，都往最左边补0。
在SM3算法中，需要的是算术右移。而在Java的语法中，>>是逻辑右移，>>>是算术右移。最初使用逻辑右移，导致循环左移最高位为1的数时运算结果与期望值不符。修改后的循环左移方法如下:
// 将x循环左移N位 private static int CircleLeftShift(int x, int N) { return (x << N) | (x >>> (32 - N)); }
3.3.2 填充消息时附加比特位1结果不对根据算法的计算步骤，填充消息时，首先在消息后面附上一个比特位1。在实现算法时，由于用户输入的都是以字节为单位的字符串，所以1之后填充的0的个数k肯定是符合7+8*Z的，其中Z为非负整数。所以可以附加一个比特位“1”的操作可以转化为附加二进制1000 0000。实现代码如下：
padding += (byte)0x80; // 先填充一个“1000 0000”其中padding是一个字符串类型的数据，用于存储附加的数据。填充完比特位1、k个0以及消息长度后，将填充后的消息打印出来，如下：

测试时输入的消息依旧是abc，理论上得到的是6162 6380 0000 0000 .....，将消息c即63后的十六进制位2d 3132 38与ASCII表对照，发现是-128。原因很明确，byte类型的0x80表示的数正是-128。而将-128与字符串padding进行 +=操作时，byte类型的数据被转换成字符串-128，所以得到上图的结果。
既然不能直接将byte类型的数据与字符串相连接，那可以尝试使用new String(byte[] bytes[])方法将一个byte数组转换成字符串。修改代码如下：
byte a[] = { (byte) 0x80 }; padding += new String(a); // 先填充一个“1000 0000”
再次运行后结果还是不正确，如下图所示：

结果显示原本的0x80变成了0x3f。经过测试发现，0x01最后会得到0x01，0x02会得到0x02，0x7f也会得到0x7f，只有当大于0x7f是结果才会不正确，而且得到的都是0x3f。
在网上搜索之后，得出错误的原因：ASCII是每个字节对应一个字符，一个字节的表示范围是-128~127，而ASCII只对0~127这个范围进行了编码。也就是每个字节最大值是0x7f，用二进制表示就是最高位为0。上面的0x80的二进制位是1000 0000，最高位是1，不在ASCII编码的范围之内。Java使用的是Unicode字符集，当进行将0x80转换成字符时，Java在Unicode代码页中查询不到对应的字符，Java会默认返回一个0x3f。所以上面试验中，小于0x80的byte可以正确转换成字符串，而大于等于0x80的byte数据将会返回0x3f.
解决方法是将byte数组转化成字符串时设置编码为“ISO-8859-1”。ISO-8859-1是按字节编码的，并且它对0~255的空间都进行了编码，所在在转换时它能够正确的将0x80转换为字符串。实现代码如下:
byte a[] = {(byte)0x80};padding += new String(a, charset);
其中第二个参数charset是在最前面定义的字符集，它是一个字符串“ISO-8859-1”。再次运行并打印填充后的消息，发现结果跟预期一致：

3.3.3 迭代时结果出错在进行迭代的时候，导出了迭代前的数据，包括Wj，Wj′等，都与课本上的示例一样。说明迭代前的步骤已经正确的完成。迭代后的结果却不正确，说明错误出现在迭代这里。将中间结果ABCDEFGH导出后与课本上的对照，发现最开始出错的位置是G0，而G0之前的A-F都是正确的。课本上的：

实验中的：

查看课本上的算法G赋值的位置，算法如下：
G ← F <<< 9此时怀疑移位算法是否编写正确，经过手算移位算法后，发现结果和实验中的显示的一样。对照国家密码管理局发布《SM3密码杂凑算法》发现，课本上的算法不对，正确的移位数应该是19，即：
G ← F <<< 19修改为正确的移位数后再次运行，发现结果与课本上的一致，SM3密码算法完成。哈希结果如下:
66c7f0f462eeedd9d1f2d46bdc10e4e24167c4875cf2f7a2297da02b8f4ba8e0

Python+Selenium+PIL+Tesseract真正自动识别验证码进行一键登录

Python 2.7
IDE Pycharm 5.0.3
Firefox浏览器：47.0.1
Selenium：Selenium的介绍及使用，强烈推荐@ Eastmount的博客
PIL : Pillow-3.3.0-cp27-cp27m-win_amd64.whl PIL第三方库的下载，win下安装whl文件
Pytesser：依赖于PIL ，Tesseract 了解pytesser及基本使用
Tesseract：3.0.2 tesseract下载及安装

前言
自动登陆时候遇到验证码，采用Tesseract+PIL进行识别和自动填充，不让验证码成为我们自动化登录的阻碍，哈哈哈

Talk is cheap, Show me the code
自动识别验证码模拟登陆，注意是自动，一键登录，不是那种扫出验证码，然后手动输入登录！首先来代码实现吧！

# -*- coding: utf-8 -*-from selenium import webdriverimport osimport pytesserimport sys,timefrom PIL import Image,ImageEnhance#shift+tab多行缩进(左)reload(sys)PostUrl = "http://yjsymis.hrbeu.edu.cn/gsmis/indexAction.do"driver=webdriver.Firefox()driver.get(PostUrl)i=0while 1:#sb登录系统，即使输对所有消息还是登不进去的，需要登录两次及以上 i=i+1 try: elem_user = driver.find_element_by_name('id') elem_psw = driver.find_element_by_name('password') elem_code = driver.find_element_by_name('checkcode') except: break #-------------------对验证码进行区域截图，好吧，这方法有点low------------------ driver.get_screenshot_as_file('C:\Users\MrLevo\image1.jpg')#比较好理解 im =Image.open('C:\Users\MrLevo\image1.jpg') box = (516,417,564,437) #设置要裁剪的区域 region = im.crop(box) #此时，region是一个新的图像对象。 #region.show()#显示的话就会被占用，所以要注释掉 region.save("e:/image_code.jpg") #------------------------------------------------------------------- #--------------ImageGrab.grab()直接可以区域截图，但是有bug，截图不全------- ''' bbox = (780, 0, 1020, 800) img = ImageGrab.grab() img.save("E:\image_code.jpg") img.show() ''' #-------------------------手动输入验证码：适用范围更广，但不够方便------------------------------ ''' response = opener.open(CaptchaUrl) picture = response.read() with open('e:/image.jpg', 'wb') as local: local.write(picture) # 保存验证码到本地 #------------对于不能用pytesser+ocr进行识别，手动打开图片手动输入-------- # 打开保存的验证码图片 输入 #SecretCode = raw_input('please enter the code: ') #---------------------------------------------------------------------- ''' #--------------------图片增强+自动识别简单验证码----------------------------- #time.sleep(3)防止由于网速，可能图片还没保存好，就开始识别 def image_file_to_string(file): cwd = os.getcwd() try : os.chdir("C:\Users\MrLevo\Anaconda2\Lib") return pytesser.image_file_to_string(file) finally: os.chdir(cwd) im=Image.open("E:\\image_code.jpg") imgry = im.convert('L')#图像加强，二值化 sharpness =ImageEnhance.Contrast(imgry)#对比度增强 sharp_img = sharpness.enhance(2.0) sharp_img.save("E:\\image_code.jpg") #http://www.cnblogs.com/txw1958/archive/2012/02/21/2361330.html #imgry.show()#这是分布测试时候用的，整个程序使用需要注释掉 #imgry.save("E:\\image_code.jpg") code= pytesser.image_file_to_string("E:\\image_code.jpg")#code即为识别出的图片数字str类型 print code #打印code观察是否识别正确 #---------------------------------------------------------------------- if i <= 2: # 根据自己登录特性，我这里是验证码失败一次，重填所有，失败两次，重填验证码 elem_user.send_keys('S315080092') elem_psw.send_keys('xxxxxxxxxx') elem_code.send_keys(code) click_login = driver.find_element_by_xpath("//img[@src='main_images/images/loginbutton.gif']") click_login.click()#time.sleep(5)#搜索结果页面停留片刻#driver.save_screenshot('C:\Users\MrLevo\image.jpg')#driver.close()#driver.quit()
Show Gif ( :
遇到问题及解决方法
验证码取得问题，因为每次刷新之后验证码动态刷新，所以如果不采用cookie的话（我还不太会用cookie）,根本捉不到元素，这个我在下篇文章中采用cookie来登录的，但不是调用浏览器，这个跑远了，下次说。
解决方案：用了driver.get_screenshot_as_file方法，机智的进行全截图，然后采用PIL中的crop进行再截图操作，可能有人会说，为什么不采用ImageGrab.grab()函数来做，好吧，因为这个函数在win10上尽然！截不了全图！！自己试了才知道，btw，我的分辨率1920x1080，难道和分辨率有关？反正这个我截了好久都没有成功，到最后才想到，截全部看看，结果，tmd只有一半，我说怎么都找不到要截图的部分！

验证码验证错误率高问题
解决方案，采用PIL强大的图像处理功能，我先将图片二值化，本来是蓝色字体的，，然后再进行对比度强化来锐化图片，然后再调用Tesseract.exe进行处理，提高的识别精度不是一点两点：看图比较，左1是用cookie抓的原图，右边是全景截图，再定位截图，再进行二值化和锐化处理的图，本来我想着用matlab做图像识别的，但是想想还要调用，感觉有点麻烦。。。


调用Tesseract.exe问题
解决方案因为程序执行图像识别需要调用Tesseract.exe，所以必须把路径切到有这个exe的路径下，刚开始，以为和包依赖，结果根本没有识别出任何图！折腾一个多小时才写好验证码识别的问题——单独测试的确很重要，记一笔！

登录失败问题—mdzz学校教务系统二次验证
解决方案，写了一个while循环，把主程序很大部分都扔进去了，目的也很明确，如果第一次登录失败，再重复进行登录，注意采用try试探元素是否仍然存在，except来抛出break结束循环，因为登录成功后，比如说driver.find_element_by_name('id')是不存在的！所以当这个元素在登陆后的界面找不到时，那就说明登录成功，ok，跳出循环，进行下一步操作。

明明图片已截取，为什么没有识别
解决方案，这个我真的没想到，我一直以为可能因为save时候还没下载好，导致库中没有这张图，那就不能识别，但是我用time.sleep函数让它停下来缓缓，还是不行，我就很无语了，想了半天，可能是因为图片被占用！因为我有一个img.show()函数，为了检测有没有截取到标准的图，然后show之后这个图像就被占用了！就像你在编辑word时候，是无法删除word文档一样！果然在注释掉show之后，一切可行，真是差错查了小半天啊！！

元素一切就位，为什么不执行操作
解决方案，这个有点脑残了，不过的确是我遇到的，还是记上一笔，然后骂自己一遍sb，没有click()你让它怎么处理！！！就像用cookie登录时候还有个ENTRY呢！

两次验证失败后，用户名重复累加
解决方案，直接加了个变量，计数循环次数，观察到只要超过两次没有登录上，就会累加登录名和用户密码，直接写了个if进行判断，完事！

im.crop(box)裁剪区域选择困难症
解决方案，多试几次，反正我是试出来的。。。。当然，你点击图片进行审查元素时候，可以看到图片大小，那么，你就可以知道横纵坐标差值多少，但是大范围区域还得自己试，如有更好的办法，请告知，以下为我截图实验次数，次数30+


导入不了Image,ImageEnhance
解决方案，因为PIL用的是第三方库，所以，采用的导入方式是这样的，多看看官方文档就可以，官方描述如下Usefrom PIL import Imageinstead ofimport Image.

找不到应该键入的元素
这个问题，请单击要输入的空白处右键，审查元素，就可以看到，然后根据driver.find_element_by_各种方法来定位元素，如果输入进行了隐藏，在当前页面找不到怎么办，就像如下图，需要先点击我的图书馆，才能看到输入的账户和密码，那么先找我的图书馆的元素，进行click操作，之后再找元素，一句话，把自己想成浏览器，阿不，把python想成浏览器。。。。。

上图的代码我也放上，大同小异，比有验证码的简单，但是多了一个click操作。
# -*- coding: utf-8 -*-from selenium import webdriverimport timeimport sys#shift+tab多行缩进(左)reload(sys)PostUrl = "http://lib.hrbeu.edu.cn/#"driver=webdriver.Firefox()driver.get(PostUrl)elem_user = driver.find_element_by_name('number')elem_psw = driver.find_element_by_name('passwd')#选择我的图书馆，点击后才能看到输入账号密码click_first = driver.find_element_by_xpath("//ul[@id='imgmenu']/li[4]")click_first.click()elem_user.send_keys('S315080092')elem_psw.send_keys('xxxxxxxx')#点击登录click_second = driver.find_element_by_name('submit')click_second.click()time.sleep(5)#登陆后选择click_third = driver.find_element_by_xpath("//*[@id='mainbox']/div/div/ul/li/a")click_third.click()time.sleep(5)#搜索结果页面停留片刻#driver.save_screenshot('C:\Users\MrLevo\image.jpg')driver.close()driver.quit()

利用N-Gram模型概括数据（Python描述)

Python 2.7
IDE PyCharm 5.0.3

什么是N-Gram模型？
在自然语言里有一个模型叫做n-gram，表示文字或语言中的n个连续的单词组成序列。在进行自然语言分析时，使用n-gram或者寻找常用词组，可以很容易的把一句话分解成若干个文字片段。摘自Python网络数据采集[RyanMitchell著]

简单来说，就是找到核心主题词，那怎么算核心主题词呢，一般而言，重复率也就是提及次数最多的也就是最需要表达的就是核心词。下面的例子也就从这个开始展开
临时补充在栗子中出现，这里拿出来单独先试一下效果

string.punctuation获取所有标点符号，和strip搭配使用
import stringlist = ['a,','b!','cj!/n']item=[]for i in list: i =i.strip(string.punctuation) item.append(i)print item
['a', 'b', 'cj!/n']
operator.itemgetter()
operator模块提供的itemgetter函数用于获取对象的哪些维的数据，参数为一些序号（即需要获取的数据在对象中的序号）
栗子
import operatordict_={'name1':'2', 'name2':'1'}print sorted(dict_.items(),key=operator.itemgetter(0),reverse=True)#dict_.items()，键值对
[('name2', '1'), ('name1', '2')]当然，你可以直接直接使用这个
dict_={'name1':'2', 'name2':'1'}print sorted(dict_.iteritems(),key=lambda x:x[1],reverse=True)2-gram就以两个关键词来说吧，上个栗子来进行备注讲解
import urllib2import reimport stringimport operatordef cleanText(input): input = re.sub('\n+', " ", input).lower() # 匹配换行,用空格替换换行符 input = re.sub('\[[0-9]*\]', "", input) # 剔除类似[1]这样的引用标记 input = re.sub(' +', " ", input) # 把连续多个空格替换成一个空格 input = bytes(input)#.encode('utf-8') # 把内容转换成utf-8格式以消除转义字符 #input = input.decode("ascii", "ignore") return inputdef cleanInput(input): input = cleanText(input) cleanInput = [] input = input.split(' ') #以空格为分隔符，返回列表 for item in input: item = item.strip(string.punctuation) # string.punctuation获取所有标点符号 if len(item) > 1 or (item.lower() == 'a' or item.lower() == 'i'): #找出单词，包括i,a等单个单词 cleanInput.append(item) return cleanInputdef getNgrams(input, n): input = cleanInput(input) output = {} # 构造字典 for i in range(len(input)-n+1): ngramTemp = " ".join(input[i:i+n])#.encode('utf-8') if ngramTemp not in output: #词频统计 output[ngramTemp] = 0 #典型的字典操作 output[ngramTemp] += 1 return output#方法一：对网页直接进行读取content = urllib2.urlopen(urllib2.Request("http://pythonscraping.com/files/inaugurationSpeech.txt")).read()#方法二：对本地文件的读取，测试时候用，因为无需联网#content = open("1.txt").read()ngrams = getNgrams(content, 2)sortedNGrams = sorted(ngrams.items(), key = operator.itemgetter(1), reverse=True) #=True 降序排列print(sortedNGrams)
[('of the', 213), ('in the', 65), ('to the', 61), ('by the', 41), ('the constitution', 34),,,巴拉巴拉一堆上述栗子作用在于抓到2连接词的频率大小来排序的，但是这并不是我们想要的，你说这出现两百多次的 of the 有个猫用啊，所以，我们要进行对这些连接词啊介词啊的剔除工作。
Deeper
完整代码和测试图都在同级目录下的2_gram.ipynb,如要测试请手动下载工程，然后运行jupyter即可，不知道jupyter？百度啊，自己装

# -*- coding: utf-8 -*-import urllib2import reimport stringimport operator#剔除常用字函数def isCommon(ngram): commonWords = ["the", "be", "and", "of", "a", "in", "to", "have", "it", "i", "that", "for", "you", "he", "with", "on", "do", "say", "this", "they", "is", "an", "at", "but","we", "his", "from", "that", "not", "by", "she", "or", "as", "what", "go", "their","can", "who", "get", "if", "would", "her", "all", "my", "make", "about", "know", "will","as", "up", "one", "time", "has", "been", "there", "year", "so", "think", "when", "which", "them", "some", "me", "people", "take", "out", "into", "just", "see", "him", "your", "come", "could", "now", "than", "like", "other", "how", "then", "its", "our", "two", "more", "these", "want", "way", "look", "first", "also", "new", "because", "day", "more", "use", "no", "man", "find", "here", "thing", "give", "many", "well"] if ngram in commonWords: return True else: return Falsedef cleanText(input): input = re.sub('\n+', " ", input).lower() # 匹配换行用空格替换成空格 input = re.sub('\[[0-9]*\]', "", input) # 剔除类似[1]这样的引用标记 input = re.sub(' +', " ", input) # 把连续多个空格替换成一个空格 input = bytes(input)#.encode('utf-8') # 把内容转换成utf-8格式以消除转义字符 #input = input.decode("ascii", "ignore") return inputdef cleanInput(input): input = cleanText(input) cleanInput = [] input = input.split(' ') #以空格为分隔符，返回列表 for item in input: item = item.strip(string.punctuation) # string.punctuation获取所有标点符号 if len(item) > 1 or (item.lower() == 'a' or item.lower() == 'i'): #找出单词，包括i,a等单个单词 cleanInput.append(item) return cleanInputdef getNgrams(input, n): input = cleanInput(input) output = {} # 构造字典 for i in range(len(input)-n+1): ngramTemp = " ".join(input[i:i+n])#.encode('utf-8') if isCommon(ngramTemp.split()[0]) or isCommon(ngramTemp.split()[1]): pass else: if ngramTemp not in output: #词频统计 output[ngramTemp] = 0 #典型的字典操作 output[ngramTemp] += 1 return output#获取核心词在的句子def getFirstSentenceContaining(ngram, content): #print(ngram) sentences = content.split(".") for sentence in sentences: if ngram in sentence: return sentence return ""#方法一：对网页直接进行读取content = urllib2.urlopen(urllib2.Request("http://pythonscraping.com/files/inaugurationSpeech.txt")).read()#对本地文件的读取，测试时候用，因为无需联网#content = open("1.txt").read()ngrams = getNgrams(content, 2)sortedNGrams = sorted(ngrams.items(), key = operator.itemgetter(1), reverse=True) # reverse=True 降序排列print(sortedNGrams)for top3 in range(3): print "###"+getFirstSentenceContaining(sortedNGrams[top3][0],content.lower())+"###"
[('united states', 10), ('general government', 4), ('executive department', 4), ('legisltive bojefferson', 3), ('same causes', 3), ('called upon', 3), ('chief magistrate', 3), ('whole country', 3), ('government should', 3),,,,巴拉巴拉一堆### the constitution of the united states is the instrument containing this grant of power to the several departments composing the government###### the general government has seized upon none of the reserved rights of the states###### such a one was afforded by the executive department constituted by the constitution###从上述栗子我们可以看出，我们对有用词进行了删选，去掉了连接词，取出核心词排序，然后再把包含核心词的句子抓出来，这里我只是抓了前三句，对于有两三百个句子的文章，用三四句话概括起来，我想还是比较神奇的。

Python 2.7
IDE Pycharm 5.0.3
PyMySQL 0.7.6
MySQL 5.7
MySQL Workbench 6.3

应用场景
如果数据库是暂存在第三方，而且存入的数据又不想让第三方数据库管理员看到，消息涉及隐私，只有自己可见，那么怎么办呢，我自己设计了一套用户加密验证系统，对登录密码进行MD5/SHA1可选加密，对明文进行自定义的加密算法进行加密存储。短时间内无法破解（私以为）

特点
用户加密存储系统—用于托管第三方数据库，内容进行加密后存储，没有秘钥无法破解


用户存储，登录，查看，删除操作，存储在数据库中
用户密码加密存储，密码加密方式可选，目前只可选MD5和SHA1，用户存储内容加密存储，加密方式自定义
自定义（我自己定义了一个加密解密函数）加密序列，拿到内容没有序列无法解密（自以为）
可更改用户密码，更改自定义KEY值，更改加密存储内容
支持任何位数和形式设置密码，甚至可以设置成中文！但是请注意，最好是杂乱无序字母夹杂的，不然被破解第一层密码后，KEY值可能会暴露！

实现流程框架

其实上面流程图的最左边如果新建用户和数据库中用户重名，则有两个选择，一个是重新命名，另一个就是对原来用户名进行修改密码，线有点多，太乱了连过去，所以这里省略了，实现效果请看下面的IDE交互章节。

好了，整体的思路框架就是这样，当然一开始我没有想那么多，只是做着做着，想着不断增加功能，更加完善性考虑，才会加入那么多选择项的，因为自己设计的，所以，难免存在瑕疵，也没有参考实际大的加密工程中如何处理，下次去看看。
实现代码这里我就不贴详细代码了，太长了，估计三四百行把，我上传资源在同级目录的mysql_encryptWD中，包括源码（带注释）+exe（exe由于打包软件限制只能用于英文字符输入）+README（请先阅读）

这里只是贴上自己写的加密算法部分。

#自定义加密、解密算法子函数。结合base64def encrypt(key,content): # key:密钥,content:明文 s1 = base64.encodestring(str(content)) #将内容进行base64加密 len1 = len(key) % 7 #取余数 len1_list = list_key[len1] #取余数对应list_key中伪码 mix_first = str(key)+s1 #将key转化为字符串后拼接第一次加密的内容 mix = len1_list+base64.encodestring(mix_first) #对拼接后字符串再进行加密，再加个伪码 return mix #存入数据库中，不能被反解def decrypt(key,mix): # key:密钥,content:密文 len2 = len(key) % 7 len2_findlist = list_key[len2] if len2_findlist==mix[0]: #先确定伪码 s2_first = base64.decodestring(mix[1:])#反解出第一次的base64编码 s2_second = s2_first[0:len(key)] #获取第一次解出前缀是否为key if s2_second==str(key):#key值对应了 s2_end = base64.decodestring(s2_first[len(key):])#反解出去掉前缀后的真实内容的64位编码 print '-------------------------------Validation Succeed!-------------------------------' return s2_end else: print "Warning!Validation Failed！Can't Get Secret Words!" else: print "Warning!Validation Failed！Can't Get Secret Words!"
解释就在上面的注释上了，这里说一下实现效果，存入数据库中形式应该是这样的

对于自己的加密算法：自己尝试写，肯定会有纰漏的地方，如果以后有机会，可以学一下密码学，自己接触的到底还是太少了，只是添加了伪码表，然后两次base64加密，当然，数据库中内容直接拿来base64解码肯定是不会成功的。
登录密码是用MD5/SHA1进行加密的，而第二层，登陆之后，可以自己选择KEY值，对输入的明文进行加密，如果没有我的伪字典和KEY应该是不能反解出加密的内容的，所以对于数据库管理员来说，根本不能解密存入数据库中的内容，对于有特殊需求的记录也好，项目也好，我想应该有应用的地方。
交互效果这里显示的是整个IDE交互界面，如何处理这些；

进行新用户注册（可以选择不设置明文默认KEY为123456）
-------------------------------Mode Choice-------------------------------------Store&Encrypt-1 Login&View&Update&Delete-2 Quit System-3 Clear Database-4Select Mode:1-------------------------------Store&Encrypt-------------------------------New User:k3Set Password:k3-------------------------------Password Encrypt Algorithm-------------------------------------MD5-1 SHA1-2Select Algorithm:1
进行设置KEY和明文加密
-------------------------------What's Next?-------------------------------------Store Encrypt Plaintext-1 Maybe Next Time-2Your Choice:1Please Design Your KEY:k4Plaintext:k4'secret##############################################SHA1-Password&Plaintext Encryption Succeed!##############################################以下是默认KEY与明文设置，选择2即可
-------------------------------What's Next?-------------------------------------Store Encrypt Plaintext-1 Maybe Next Time-2Your Choice:2Default KEY '123456'Default Plaintext 'Default Storage'#############################################MD5-Password&Plaintext Encryption Succeed!#############################################
查看加密明文
（如果没有自己设置KEY等，会有个默认值进行存储）
以下为自己设置了KEY和明文（没有设置时候，则KEY为123456），查看明文
-------------------------------k4:What's Next?-------------------------------Update Plaintext-1 View Plaintext-2 Update Password-3 Update KEY-4 Log out-5 Delete User-6Your Choice: 2KEY:k4-------------------------------Validation Succeed!-------------------------------Secret Words:k4'secret更加详细的请自己测试使用。代码和上述流程图保持一致。

遇到新用户重名，解决途径，修改密码或者更换新名字
-------------------------------Mode Choice-------------------------------------Store&Encrypt-1 Login&View&Update&Delete-2 Quit System-3 Clear Database-4Select Mode:1-------------------------------Store&Encrypt-------------------------------New User:k1Warning!The Name Already Exist!-------------------------------Make Your Choice-------------------------------------Change Password-1 Create New User-2Select Mode:2New User:k2Set Password:k3
更新登录密码选择，需要有以前密码，才能修改
-------------------------------Welcome k1--------------------------------------------------------------k1:What's Next?-------------------------------Update Plaintext-1 View Plaintext-2 Update Password-3 Update KEY-4 Log out-5 Delete User-6Your Choice: 3Please Enter Original Password:k1Please Enter New Password:k2###########################Update Password Succeed!###########################
更新KEY值
-------------------------------Welcome k1--------------------------------------------------------------k1:What's Next?-------------------------------Update Plaintext-1 View Plaintext-2 Update Password-3 Update KEY-4 Log out-5 Delete User-6Your Choice: 4Please Enter Original KEY:k1Please Enter New KEY:k2-------------------------------Validation Succeed!-------------------------------######################Update KEY Succeed!######################
更新明文
-------------------------------k4:What's Next?-------------------------------Update Plaintext-1 View Plaintext-2 Update Password-3 Update KEY-4 Log out-5 Delete User-6Your Choice: 1KEY:k4-------------------------------Validation Succeed!-------------------------------Original Plaintext:k4'secretNew Plaintext:k4's secret2############################Update Plaintext Succeed!############################遇到的问题及解决方案Q: MD5/SHA1加密存储时候的类型不同引起的错误。A: 解决方案，多进行try/except使用抛出错误，定位错误，常用输出语句进行和预期值之间的排错，如下，md5加密后为元组形式，而sha1为str类型
import hashlib#MD5和SHA1加密算法def md5(str1): md = hashlib.md5() md.update(str1) md_5=md.hexdigest() return md_5,def sha1(str1): sh = hashlib.sha1() sh.update(str1) sha_1 = sh.hexdigest() return sha_1print md5("123")print type(md5("123"))print sha1("123")print type(sha1("123"))运行后
('202cb962ac59075b964b07152d234b70',)<type 'tuple'>40bd001563085fc35165329ea1ff5c5ecbdbbeef<type 'str'>知道所出现的形式之后，对症下药就可以了！
Q: 对数据库进行插入，删除，更新操作，数据库内容不改变问题A: 解决方案，没有进行事务提交！比如，我实现添加操作，最后需要添加语句commit
cur.execute("insert into store(user_name,passwd,encrypt_words,encrypt_password) VALUES (%s,%s,%s,%s)",(user_name,passwd,encrypt_str,key_content))cur.connection.commit()#commit()提交事物，做出改变后必须提交事务，不然不能更新Q: 数据库出现Lock wait timeout exceeded错误，原因是如图

A: 解决方案；这里应该运行时候断开以前运行的程序，这点我做的不好，调试的时候，以前的程序还在运行，全部断开连接，只要一个运行就行
Q: 结构功能问题A: 需要实践积累，怎样实现目的，产生比较清晰的架构，子函数应该怎么写，才能最大程度的调用，这些我都比较弱，需要不断的进行学习和测试，我的框架结构也是改了很多次，都是进行测试之后慢慢修改成型的，考虑到了几乎所有的操作需求，你能信当时我只是想弄个加密写入和读取的玩意就行了么，最后还是写成比较完善的一个小项目了，所以，这个问题，只有不断练习把，不过下次我会先拟构好一个流程图框架再写。

云服务器：ESC Ubuntu 16.04 x64
PhantomJS：beta-Linux-ubuntu-xenial 2.1.1
Python 2.7.12

前言
好久没玩点有意思的了，这次借618这个购物节，自己也要搞台mbp，顺便搞一波大新闻。

内容
对某宝的其中四家店，再加上某东一家店，对比同一款机型，对价格进行监控，至于监控时间，大概是不间断的监控吧，还有邮件提醒哦~


涉及面
爬虫中阶知识，因为涉及到动态页面抓取，一个页面对不同型号进行点击操作，之后再获取元素，使用了phantomjs包
python字符串处理中阶知识，涉及到数据清洗，重构，还有缺失值的填充，这次没用pandas进行处理，直接用的是字符串处理技巧
因为需要进行数据分析展示，故需要初级的JavaScript知识以及echarts的了解，这次构图使用的是echarts，比较简单

开搞-数据挖掘
因为涉及到商家利益，具体的代码细节将不再展开。

流程和以前的动态页面抓取一致，选择需要的url之后进行元素点击操作，目的是为了选中需要比较价格的机型，这都么有问题，主要将一些注意点

Q:元素加载过程中出现can’t find element问题A: 首先确定自己的元素位置是否写对，建议使用xpath的方法定位元素，再chrom上直接可用copy xpath，其余都对的情况可以加上wait等待时间，参考这里
Q:如果ip被封了，connection refusedA: 请参考Python爬虫防封杀方法集合


Q:动态页面加载过程中，商家交换了商品的次序，导致获取到的div位置不正确，怎么办？A: 解决方法，额，我是每天看一下log，看看有没有不正常的，不正常就kill任务然后修改位置，再接着跑，一般来说，商家不会闲着无聊去修改位置的，另一个解法是对之后的结果手动清洗，如果价格与之前的价格差值大过一定范围，则直接认为是噪声数据，毕竟，怎么可能价格涨跌超过1000的呢，还有一个解法是，确定点击元素的值代表是什么型号，然后点击的价格就是什么型号的了，这个我懒得做了。。。。
Q:我想要及时知道哪家店价格已经到我的接受阈值了，怎么通知我？A:写监控邮件,当价格低于某个阈值，直接触发邮件功能，邮件如何书写，请参考，这个是直接可用的

一、介绍本文主要介绍了系统涉及的人脸检测与识别的详细方法，该系统基于 python2.7.10/opencv2/tensorflow1.7.0 环境，实现了从摄像头读取视频，检测人脸，识别人脸的功能。
人脸识别是计算机视觉研究领域的一个热点。目前，在实验室环境下，许多人脸识别已经赶上（超过）人工识别精度（准确率：0.9427~0.9920），比如face++,DeepID3，FaceNet等（详情可以参考：基于深度学习的人脸识别技术综述）。但是，由于光线，角度，表情，年龄等多种因素，导致人脸识别技术无法在现实生活中广泛应用。本文基于python/opencv/tensorflow环境，采用FaceNet（LFW：0.9963 ）为基础来构建实时人脸检测与识别系统，探索人脸识别系统在现实应用中的难点。下文主要内容如下 ：

利用htm5 video标签打开摄像头采集头像并使用jquery.faceDeaction组件来粗略检测人脸
将人脸图像上传到服务器，采用mtcnn检测人脸
利用opencv的仿射变换对人脸进行对齐，保存对齐后的人脸
采用预训练的facenet对检测的人脸进行embedding，embedding成512维度的特征
对人脸embedding特征创建高效的annoy索引进行人脸检测

二、人脸采集采用html5 video标签可以很方便的实现从摄像头读取视频帧，下文代码实现了从摄像头读取视频帧，faceDection识别人脸后截取图像上传到服务器功能。
在html文件中添加video，canvas标签
<div class="booth"> <video id="video" width="400" height="300" muted class="abs" ></video> <canvas id="canvas" width="400" height="300"></canvas> </div>
打开网络摄像头
var video = document.getElementById('video'),var vendorUrl = window.URL || window.webkitURL;//媒体对象navigator.getMedia = navigator.getUserMedia || navagator.webkitGetUserMedia || navigator.mozGetUserMedia || navigator.msGetUserMedia;navigator.getMedia({video: true, //使用摄像头对象audio: false //不适用音频}, function(strem){ video.src = vendorUrl.createObjectURL(strem); video.play();});
利用jquery的facetDection组件检测人脸
$('#canvas').faceDetection()检测出人连脸的话截图，并把图片转换为base64的格式，方便上传
context.drawImage(video, 0, 0, video.width, video.height);var base64 = canvas.toDataURL('images/png');
将base64格式的图片上传到服务器
//上传人脸图片function upload(base64) { $.ajax({ "type":"POST", "url":"/upload.php", "data":{'img':base64}, 'dataType':'json', beforeSend:function(){}, success:function(result){ console.log(result) img_path = result.data.file_path } });}
图片服务器接受代码，php语言实现
function base64_image_content($base64_image_content,$path){ //匹配出图片的格式 if (preg_match('/^(data:\s*image\/(\w+);base64,)/', $base64_image_content, $result)){ $type = $result[2]; $new_file = $path."/"; if(!file_exists($new_file)){ //检查是否有该文件夹，如果没有就创建，并给予最高权限 mkdir($new_file, 0700,true); } $new_file = $new_file.time().".{$type}"; if (file_put_contents($new_file, base64_decode(str_replace($result[1], '', $base64_image_content)))){ return $new_file; }else{ return false; } }else{ return false; }}
三、人脸检测人脸检测方法有许多，比如opencv自带的人脸Haar特征分类器和dlib人脸检测方法等。对于opencv的人脸检测方法，有点是简单，快速；存在的问题是人脸检测效果不好。正面/垂直/光线较好的人脸，该方法可以检测出来，而侧面/歪斜/光线不好的人脸，无法检测。因此，该方法不适合现场应用。对于dlib人脸检测方法 ，效果好于opencv的方法，但是检测力度也难以达到现场应用标准。
本文中，我们采用了基于深度学习方法的mtcnn人脸检测系统（mtcnn：Joint Face Detection and Alignment using Multi-task Cascaded Convolutional Neural Networks）。mtcnn人脸检测方法对自然环境中光线，角度和人脸表情变化更具有鲁棒性，人脸检测效果更好；同时，内存消耗不大，可以实现实时人脸检测。本文中采用mtcnn是基于python和tensorflow的实现（代码来自于davidsandberg，caffe实现代码参见：kpzhang93）
model= os.path.abspath(face_comm.get_conf('mtcnn','model'))class Detect: def __init__(self): self.detector = MtcnnDetector(model_folder=model, ctx=mx.cpu(0), num_worker=4, accurate_landmark=False) def detect_face(self,image): img = cv2.imread(image) results =self.detector.detect_face(img) boxes=[] key_points = [] if results is not None: #box框 boxes=results[0] #人脸5个关键点 points = results[1] for i in results[0]: faceKeyPoint = [] for p in points: for i in range(5): faceKeyPoint.append([p[i], p[i + 5]]) key_points.append(faceKeyPoint) return {"boxes":boxes,"face_key_point":key_points}
具体代码参考fcce_detect.py。
四、人脸对齐有时候我们截取的人脸了头像可能是歪的，为了提升检测的质量，需要把人脸校正到同一个标准位置，这个位置是我们定义的，假设我们设定的标准检测头像是这样的。

假设眼睛，鼻子三个点的坐标分别是a(10,30) b(20,30) c(15,45)，具体设置可参看config.ini文件alignment块配置项。
采用opencv仿射变换进行对齐，获取仿射变换矩阵
dst_point=【a,b,c】tranform = cv2.getAffineTransform(source_point, dst_point)
仿射变换
img_new = cv2.warpAffine(img, tranform, imagesize)
具体代码参考face_alignment.py文件。
五、产生特征对齐得到后的头像，放入采用预训练的facenet对检测的人脸进行embedding，embedding成512维度的特征，以(id,vector)的形式保存在lmdb文件中。
facenet.load_model(facenet_model_checkpoint) images_placeholder = tf.get_default_graph().get_tensor_by_name("input:0") embeddings = tf.get_default_graph().get_tensor_by_name("embeddings:0") phase_train_placeholder = tf.get_default_graph().get_tensor_by_name("phase_train:0") face=self.dectection.find_faces(image) prewhiten_face = facenet.prewhiten(face.image) # Run forward pass to calculate embeddings feed_dict = {images_placeholder: [prewhiten_face], phase_train_placeholder: False} return self.sess.run(embeddings, feed_dict=feed_dict)[0]
具体代码可参看face_encoder.py。
人脸特征索引
人脸识别的时候不能对每一个人脸都进行比较，太慢了，相同的人得到的特征索引都是比较类似，可以采用KNN分类算法去识别,这里采用是更高效annoy算法对人脸特征创建索引，annoy索引算法的有个假设就是，每个人脸特征可以看做是在高维空间的一个点，如果两个很接近(相识)，任何超平面都无法把他们分开，也就是说如果空间的点很接近，用超平面去分隔，相似的点一定会分在同一个平面空间。
#人脸特征先存储在lmdb文件中格式(id,vector),所以这里从lmdb文件中加载lmdb_file = self.lmdb_fileif os.path.isdir(lmdb_file): evn = lmdb.open(lmdb_file) wfp = evn.begin() annoy = AnnoyIndex(self.f) for key, value in wfp.cursor(): key = int(key) value = face_comm.str_to_embed(value) annoy.add_item(key,value) annoy.build(self.num_trees) annoy.save(self.annoy_index_path)
具体代码可参看face_annoy.py。
六、人脸识别经过上面三个步骤后，得到人脸特征，在索引中查询最近几个点并就按欧式距离，如果距离小于0.6（更据实际情况设置的阈值）则认为是同一个人，然后根据id在数据库查找到对应人的信息即可。
#根据人脸特征找到相似的def query_vector(self,face_vector): n=int(face_comm.get_conf('annoy','num_nn_nearst')) return self.annoy.get_nns_by_vector(face_vector,n,include_distances=True)
具体代码可参看face_annoy.py。
七、安装部署建表，用于存在用户注册信息，并在web/DqMysql.php 中配置数据库信息。
create database face;CREATE TABLE `face_user` ( `id` int(11) NOT NULL AUTO_INCREMENT, `img` varchar(1024) NOT NULL DEFAULT '', `user_name` varchar(1024) NOT NULL DEFAULT '', `email` varchar(1024) NOT NULL DEFAULT '', PRIMARY KEY (`id`)) ENGINE=InnoDB DEFAULT CHARSET=utf8
系统采用有两个模块组成：

face_web：提供用户注册登录，人脸采集，php语言实现
face_server：提供人脸检测，裁剪，对齐，识别功能，python语言实现

模块间采用socket方式通信通信格式为：length+content；face_server相关的配置在config.ini文件中。
使用镜像

face_serverdocker镜像：shareclz/python2.7.10-face-image
face_web镜像：skiychan/nginx-php7

假设项目路径为/data1/face-login
安装face_server容器
docker run -it --name=face_server --net=host -v /data1:/data1 shareclz/python2.7.10-face-image /bin/bashcd /data1/face-loginrm -rf /data1/face-login/models/facedetect/20180408-102900/._model-20180408-102900.metapython face_server.py安装face_web容器
docker run -it --name=face_web --net=host -v /data1:/data1 skiychan/nginx-php7 /bin/bashcd /data1/face-login;php -S 0.0.0.0:9988 -t ./web/最终效果：
face_server加载mtcnn模型和facenet模型后等待人脸请求

未注册识别失败

人脸注册

注册后登录成功

注意由于模型文件过大，在此无法上传，整个项目放在百度云盘，地址：
链接: https://pan.baidu.com/s/1z9CFnK6fNsUl-1jVmnaOiw提取码: ktdp

1 引言在建设平安城市的进程中，安全是政府日常管理工作中的重要任务。随着城市报警和监控系统的建设，对于监控数据的分析也日显重要。
目前需要对重点街道或路口采集的视频数据进行分析，主要包括两点：

对于视频中过往机动车辆的机动车牌提取出来，生成截屏图片；
对提取的图片中机动车牌号码进行提取，并输出文件进行记录。

通过系统的自动分析提取，可以对街道或路口的车辆流量进行统计，一方面解决了从海量数据中人工分析的困难，另一方面通过机动车辆的统计，对城市道路建设以及交通管理都具有重要指导意义。
1.1 编写目的该文档是基于视频文件的车辆分析系统的设计说明书，主要是向开发人员介绍系统软件的详细设计。
1.2 背景为了对街道或路口的车辆流量进行统计，以及解决从海量数据中人工分析的困难，开发此车辆分析系统。
2 需求分析2.1 功能性需求分析视频文件转换为有车牌号码框的图片集合，将现有的视频文件按每帧进行分析，识别出存在车牌号码框的帧，并且将视频的该帧转换为图片,在图片中将识别出的车牌框使用明显的色彩框进行标注。约束条件：

视频文件支持MPEG格式，导出的图片集合为BMP格式车牌支持蓝牌、黄牌
导出图片车牌号码框标识，从视频文件所转换的图片中，将识别到的车牌号码用色

车牌号码文字识别，对图片中的车牌号码识别形成车牌号码列表，并保存号码列表到文件。约束条件:

图片为BMP格式
车牌支持蓝牌，黄牌
车牌号码支持中国车牌格式，例如：苏AXXXXX

车流量统计，通过对视频的车牌框识别与生成图片的号码文字识别，对号码进行去重处理，并计算该视频中的车流量。约束条件：

在车流量计算中，同一个车牌号码只计算为1个流量单位。
2.1 非功能性需求分析
系统内存消耗控制在1GB以内
系统可以在Windows XP操作系统上运行
支持清晰度为CIF(352*288)、4CIF(705*576)的视频文件

3 系统总体设计3.1 软件界面
3.2 系统流程图
3.3 系统详细说明3.3.1 图像处理图像处理包括灰度化，灰度均匀化，Robert算法轮廓提取，中值滤波，自适应二值化，图像的腐蚀和膨胀。

图像灰度化函数：cvThreshold()。灰度均匀化函数：cvEqualizeHist()。Robert算法是自己写的，函数名为：RobertDIB()。中值滤波函数是自己写的，这里用的是3*3的大小滤波。函数名为：myMedianFilter()。自适应二值化函数为：cvThreshold()，其中参数为：CV_THRESH_BINARY| CV_THRESH_OTSU，实现自适应。图像的膨胀与腐蚀虽然是使用的opencv封装的cvDilate函数，和cvErode函数，但是膨胀与腐蚀的结构元素和处理次数都是根据实际情况设定的。
3.3.2 车牌定位车牌定位主要是在前面对图像的处理后，车牌区域已经基本处于一块白色的区域，然后用CvMemStorage类创造出一块内存空间，再用cvFindContours()方法提取所有连通区域的所有轮廓保存到这个内存中。再对每一个轮廓进行筛选。这里进行筛选的方法是，根据轮廓用cvBoundingRect()方法得到每个轮廓的矩形区域，这里因为车辆的远近导致大小不一，所以给车牌的大小设定范围，这里我设定的范围是，宽度比高度大18个像素点，宽度在50像素和25像素之间，高度在25像素和5像素之间，宽度与高度的比值取值可以是2或者3或者4。筛选条件的代码为：
area_Rect->width-area_Rect->height>=18 &&area_Rect->width<=40 &&area_Rect->width>25 &&area_Rect->height<25 &&area_Rect->height>5 &&(area_Rect->width/area_Rect->height==2 || area_Rect->width/area_Rect->height==3 || area_Rect->width/area_Rect->height==4)
这样筛选之后，大区域的轮廓就被过滤掉了，但是还有和车牌特征相近的区域存在，比如车灯，车辆的牌子等等。于是，还需要进行下一步过滤。由于，车牌的自身特点是里面会有字符，每个字符之间有一定空隙。于是，我先灰度化，二值化这些被筛选过一次的区域，然后竖直膨胀20次（为了让竖直方向全是白色），最后从左到右的计算0变1，1变0的次数，大于12次（相当于6个字符）的时候就当做是车牌区域。
3.3.3 车牌识别车牌识别部分我用的是SVM算法+HOG特征提取的方式。先把车牌里的字符进行分割，这里分割的方式和定位车牌的时候很像。提取出每个矩形轮廓基本就是字符区域。然后用另外一个工程制作SVM分类器进行识别，制作过程分为：训练集的收集，通过训练得到分类器，这里的分类器数据我保存在HOG_SVM_DATA.xml文件中，然后主工程文件中只需要调用里面的数据生成cvSvm分类器，最后再将分割出来的每一个字符去进行识别，最后将车牌号输出到主界面的编辑框和外部文件中。
4 代码结构代码结构很简单，选择输入的视频文件之后，就设置定时器消息函数，定时为0.5s/帧。主要的代码都在MFCShowVideoTestDlg.cpp文件的onTimer()方法中，其中需要的一些函数还放在PlateLocateMethod.cpp文件中。
5 主要的算法和思路在图像处理部分用到的中值滤波算法和Robert边缘检测算法都已经很成熟，这里不作介绍。主要的算法在于字符识别阶段用到SVM算法，生成分类器，生成分类器的工程名：plateTest。
这里面用到一个比较特殊的方式，就是先在外部hb.txt文档中写好训练集每一幅图片的路径，下一行则是类别。
然后在程序中按照文件的基数偶数行分别提取出图片和类别加入训练。使用svm.train()训练，最后通过svm.save(“D://HOG_SVM_DATA.xml” )保存到D盘中。
在主工程中Findchar()函数用于识别字符，首先创建CvSVM类型的一个分类器，然后加载D盘下HOG_SVM_DATA.xml文件中的数据，代码为：svm.load(“D:/HOG_SVM_DATA.xml”)。
然后创建HOGDescriptor对象，并且用这个对象里面的compute()方法进行Hog特征计算，其中创建vector类型的动态数组用于存放结果，然后把结果归总到CvMat类型的一块空间中，再通过svm.predict()检测出最后的结果。
这里需要说明的是，最后结果是一个整型的值。因为字母我也是经过一并放入其中。所以最后的结果需要进行判断其值，如果是值在65以上的就是字符，需要进行强制转换。
6 总结由于我是一个人参赛，而且时间仓促，给我造成了很大的困难。没有时间去完善代码，和完善其功能，只实现了主体功能。并且因为SVM算法的训练集也没有时间去收集，本应该还有非样本集的，也没有时间去收集，导致了识别率严重偏低。由于识别率太低，没有办法进行去重处理，所以没办法实现流量统计。还有就是
采用SVM算法太耗时，算法的处理不应该放在主线程，代码的结构还没有时间做最后的改进，即使效果不如意，但是
方法和思路应该是正确的，只是时间和人员不够，完善好了效果应该还行。

一、概述1.1 选题背景首先现在各种安卓的游戏和APP充斥应用市场，但是创意还是有的。
首先，锁屏软件虽然不是一个创新点，我也承认好多人都做过了，也有做的很绚丽的，这个事实我也承认，但是当前背景是，很多锁屏软件，仅仅是PIN或者是九宫格密码形式，但是造成的问题是，破解起来也很容易，网上就有好多破解教程，简单粗暴。
所以锁屏软件的安全性还是一个值得考究的部分。同时网上有很多需求，百度知道等等，有好多人都需求一个真正属于他们自己的软件，能够真正的自定义。
所以基于上述两点，我选择了这个方向的开发，我的APP“ALL IN ONE”就是能为了实现这种的需求实现的，既有防盗功能，也有自定义锁屏界面的功能。
1.2 项目意义这个项目的意义十分的明显，首先是解决了当前的需求，所以说是一个使用的app，不是说为了创意而创意的产物。
其次，他的功能很多，应用层面很广阔。首先可以个人使用这款软件，用作娱乐，放松身心以及自由的用户体验。同时他也可以给企业用，企业可以用这种功能来宣传，来投放广告，可以进行营利。所以项目意义重大，one here，use in many place。所以总体上来讲，有足够多的理由证明其意义还是存在的。
二、可行性分析和目标群体2.1 可行性分析首先可行性是毋庸置疑的，首先，市场方面是存在的，我在做这个项目之前进行了简单的调研，返现有很多人还是希望能够自定义锁屏界面的，因为许多市面上的APP没有这种功能，同时对于防盗功能更是必须的，举例来说在我们的图书馆，很多同学看书看累了或者是粗心大意，就会直接把手机丢到桌子上，同时每个月都有好多同学不是丢电脑就是丢手机的。所以做一个这种的防盗功能的app更是情势所迫，这样可以在某种程度上减少手机的丢失概率。正是因为市场的需求造成这种app的诞生。
2.2 目标群体目标群体分为两种，主要是分为个人和组织，个人主要面向群体是在校学生这种手机长用户，因为他们容易丢手机，同时也容易成为盗窃的受害者，同时比如像图书管这种防盗不好进行地方，更有这种软件市场，同时对于学生来说，更喜欢个性化，喜欢追求自由。
而对于组织来说，主要面向各种手机公司，尤其是卖手机的地方，我们的APP的市场更为广阔，企业可以通过自定义锁屏的方式不断循环播放广告，低成本，但是高效率。同时也可以起到防盗的功能，比如某些不可以取下的手机。
三、作品功能和原型设计3.1 总体功能结构
3.2 具体功能模块设计3.2.1 锁屏/解锁模块监听android系统级广播，通过service和broadcast receiver共同实现锁屏界面实现。
3.2.2 九宫格密码加密模块自定义View控件，实现OnCompleteListener，同时使用sharedpreferences操作存贮密码，同时定义相关函数。
3.2.3 防盗功能模块监听Sensor，和密码加密模块通信。
3.2.4 自定义锁屏背景模块使用viewpager轮播，app自带锁屏背景，只有当你在相关文件夹中添加了相关图片才会自动载入，实现自定义。
3.3 界面设计3.3.1 主界面设计
3.3.2 密码功能界面设计


3.3.3 防盗功能界面设计

四、作品实现、特色和难点4.1 作品实现
作品实现：使用工具
IDE：adt-bundle-windows-x86_64-20140702，
SDK：API-19
Tools： sdk tool：hierarchyviewer.bat, draw9patch.bat

4.2 特色分析特色有三：

首先是正常的密码加密以及锁屏功能，有基本的保护功能
防盗功能，正如同前面分析的，有广泛的应用空间和很强的实用性
自定义锁屏背景，可以让你的生活不再单调，手机也能透露你的个性，一个好的锁屏背景不如一个真正属于你自己的锁屏背景更加适合你

4.3 难点和解决方案难点有监听系统消息，同时最重要的是对于九宫格密码的存储识别以及最后校验的过程，同时还有在进行防盗功能时候设置移动度量以及最后senor的register和unregister的事件相应问题。还有就是关于一些逻辑的设计问题，很是个难题，要考虑很多，要不就会留下bug，或者是做出交互性不好的软件。
解决方案即使查找资料，并且多次试验，找人进行用户体验试验以及重复测试，同时通过画状态图的方式进行相关状态的制约问题。

一、题目设计双任务系统设计
二、设计内容采用8086汇编语言，设计并实现双任务系统设计，对两个任务（两个窗口）进行管理和调度，能够实现任务之间的切换，保存上下文信息。任务调度程序使用循环程序来完成。在左边显示窗口，能够运行简单的贪吃蛇游戏，在右边显示窗口，能够画出等边三角形。
三、需求分析
贪吃蛇游戏采用键盘按键控制贪吃蛇前进方向，如“W、S、A、D”键分别为上下左右方向控制按键
游戏终止条件为贪吃蛇碰触窗口边框、蛇头碰触身体、身体长度达到上限，以“R”键为游戏重新开始。若游戏进行当中无键按下，则贪吃蛇保持当前方向不变直至撞墙
等边三角形位置在该显示区域的中部，参数边长由键盘输入确定
三角形每次根据输入的参数，在该窗口将三角形重新绘制出来
初始工作窗口为右边显示窗口，以后每按一次Tab键切换至旁边显示窗口
当某个显示窗口被选中时，则焦点停留在该窗口，键盘输入对当前窗口有效
整个系统按ESC键退出，返回DOS操作系统界面

四、概要设计4.1 方案设计
4.2 模块功能说明4.2.1 I/O模块说明
getInt() 读入整数函数：键盘输入一串字符，检测该字符是否为数字字符。若不是数字字符，则做无效处理。直至输入完整的数值字符保存在AX中并将ZF置1（调用者可用JZ判断是否发生特殊情况）。并做如下处理：①若键盘输入Esc键，返回AX=0，并将ZF置0。②若键盘输入Tab键，返回AX=1，并将ZF置0
getchar() 函数：输入一个字符，回显
puts() 函数：输出字符串
getch() 函数：输入一个字符，不回显
putInt() 函数：将AX寄存器中的数字以十进制的形式输出

4.2.2 控制模块说明
movCursor() 移动光标模块：将光标移动至y行x列
sDelay() 延时函数模块：控制贪吃蛇移动速度
kbhit() 模块：检测键盘有无输入
rand() 随机数发生模块：生成一定范围内的随机数

五、详细设计及运行结果5.1 流程图三角形模块流程图

贪吃蛇模块流程图

5.2 函数之间相互调用的图示函数内部调用图

顶层调用图示

5.3 程序设计主要代码任务切换
yield proc pushf ;先保存一下flags cmp ax,0 ;判断是否是esc jne yEls1 mov AH, 4CH ;esc exit int 21h yEls1: ;是tab，先在它自己的栈里保存寄存器, push ax push bx push cx push dx push di push si push bp ;再切换栈，恢复另一组寄存器 cmp yFunc,0 ;当前是tri? je yTri mov stack_snake_sp,sp mov sp,stack_tri_sp ;当前是1:snake，要切换成tri mov ax,STACK_RTI mov ss,ax mov yFunc,0 jmp yTriEd yTri: mov stack_tri_sp,sp mov sp,stack_snake_sp ;当前是0:tri，要切换成snake mov ax,STACK_SNAKE mov ss,ax mov yFunc,1 ;恢复寄存器 yTriEd: pop bp pop si pop di pop dx pop cx pop bx pop ax popf ret ;切换yield endp
贪吃蛇移动
sMove proc pushf push ax push bx push di mov ah,0 mov al,sbody_move mov di,ax ;擦除身体最后一节 shl di,1 mov bl,sbody[di] ;x di*2+0 inc di mov al,sbody[di] ;y call movCursor cmp bl,-1 jz SMEls0 mov al,' ' call putchar SMEls0: mov ah,0 mov al,sbody_move mov bx,ax mov al,x mov di,bx shl di,1 mov sbody[di],al mov al,y inc di mov sbody[di],al dec sbody_move cmp sbody_move,0 ja sMElse1 ;手动取余 mov al,blength mov sbody_move,al sMElse1: ;不需要擦除头部 ;switch(m) cmp m,'s' je sMCs1 cmp m,'a' je sMCs2 cmp m,'d' je sMCs3 cmp m,'w' je sMCs4 ;case sMCs1: inc y jmp SCsEd1 sMCs2: dec x jmp SCsEd1 sMCs3: inc x jmp SCsEd1 sMCs4: dec y jmp SCsEd1 SCsEd1: ;end of switch-case mov al,y ;重新绘制头部 mov bl,x call movCursor mov al,HEAD_CHAR call putchar cmp HEAD_CHAR,'#' jne sMElse2 mov HEAD_CHAR,'*' jmp sMIfEd2 sMElse2: mov HEAD_CHAR,'#' sMIfEd2: ;移动光标 mov bl,0 mov al,SCY call movCursor pop di pop bx pop ax popf retsMove endp
画三角形主要流程
triangle proc near pushf push AX push BX push CX push DX mov triLenth,AX ;记录AX输入的边长 call triHypotenuse ;第一次call画左边 call triHypotenuse ;第二次call画右边 call triBase ;画横线 pop DX pop CX pop BX pop AX popf ret
5.4 运行结果开始界面

输入等边三角形边长
若输入超出范围，清除输入数据并等待重新输入（此处为500）

输入符合规范（此处为200）

按Enter画等边三角形并重新打印提示信息

可循环读入等边三角形边长（此处为80）

按Enter清除右半部分屏幕并重新打印

按Tab键画等边三角形程序停止，贪吃蛇程序开始运行

食物出现在随机位置，用W A S D键控制贪吃蛇运动

若撞墙或碰到自己游戏结束并暂停

游戏过关

按R键重新开始游戏

按Tab键贪吃蛇程序暂停，画等边三角形程序等待输入

六、总结6.1 不足和改进
不足

贪吃蛇游戏制作的精细度和画面质量有待提高贪吃蛇的移动速度无法改变三角形使用整数近似计算
改进

可以通过改变蛇身的样子和食物的颜色来提高画面质量可以在界面中设置游戏的速度：慢速 中速 高速三角形可使用浮点数寄存器进行划线

6.2 体会在本次竞赛学习过程中，项目经过功能划分、肢解分为一层一层的模块调用。将计算机基本指令和中断调用整合起来形成底层模块，再由底层模块整合起来形成较大的功能模块，再由功能模块进行逻辑组合形成snake和tri模块，使用yield任务切换模块作为桥梁将整个程序整合在一起。
在实际操作中我们认识到熟练掌握汇编语言中的指令的基本用法和组织结构的重要性。只有熟练掌握指令的基本用法，我们才能在实际的编程中像运用高级语言一样灵活的变通，认清计算机组织结构才能灵活设计程序整体架构。汇编语言作为一种低级设计语言，它是最底层的、与计算机内部的结构联系密切，我们在这次竞赛过程中深刻地了解到了这一点。
在贪吃蛇程序和画等边三角形的程序设计中，加深了对计算机体系结构的理解，深刻理解汇编语言和其他语言的不同。在代码设计中也遇到很多的困难，比如一些寄存器使用冲突的问题，还有一些宏的使用问题和两个程序切换的问题等，以及如何对程序调用时对参数和返回值做一系列约定。在这个方面，我们深刻理解了团队协作能力的重要性。

1 使用说明本系统分成四个模块，包含一个应用层可执行文件(.exe)，四个内核层驱动（.sys），一个规则库数据库文件（.mdb），请保证六个文件在同一目录。
1.1 安装服务与启动监控程序不需要安装，双击即可打开可执行文件。打开后，如果需要启动服务，请点击“安装服务”，请切换至“主要”标签页，接着“启动进程监控”、“启动注册表监控”、“启动文件监控”、“启动内存加载监控”，程序开始拦截系统调用。

1.2 停止监控与停止服务如果需要停止监控，请先在各标签页“停止功能”，例如停止注册表监控，请先点击注册表监控标签页“停止功能”按钮。接着打开“主要”标签页，停止相当服务即可， 如图：

2 系统设计与架构2.1 开发环境本系统应用层采用Visual Studio 2008(C++)开发，驱动层开发环境为WDK 6001.18002、Notepad++，测试环境为VMware 6.0、Windows XP Sp3。
2.2 系统结构病毒在计算机运行之后将根据自身的目的呈现出一系列的动作，包括写注册表项，生成文件，远程线程注入等等。本系统通过拦截系统调用对程序行为进行监控，将监控的行为信息交给监控中心和网络服务器分析处理，根据程序行为分析判断病毒，云安全概念的加入，本地特征库极小，占用系统资源很少。本系统设想根据这一系列的动作所组成的行为进行智能的逻辑判断该程序是不是病毒。
系统结构示意图

2.3 系统流程本系统分为六大模块：进程监控模块、注册表监控模块、内存加载监控模块、文件创建加载模块、云安全模块、安全监控中心模块。各个模块相互独立，系统流程图如下：

3 系统实现原理3.1 Hook SSDT在 Windows NT 下，用户模式（User mode）的所有调用，如Kernel32.dll，User32.dll, Advapi32.dll等提供的API，最终都封装在Ntdll.dll中，然后通过Int 2E或SYSENTER进入到内核模式，通过服务ID，在System Service Dispatcher Table中分派系统函数。这些本地系统服务的地址在内核结构中称为系统服务调度表(System Service Dispatch Table，SSDT)中列出，该表可以基于系统调用编号进行索引，以便定位函数的内存地址。下图是Windows NT系列操作系统的体系结构，系统服务调用只是一个接口，它提供了将用户模式下的请求转发到Windows 2000内核的功能，并引发处理器模式的切换。在用户看来，系统服务调用接口就是Windows内核组件功能实现对外的一个界面。系统服务调用接口定义了Windows内核提供的大量服务。

KeServiceDescriptorTable是由内核导出的表，这个表是访问SSDT的关键，具体结构是:
typedef struct ServiceDescriptorTable { PVOID ServiceTableBase; PVOID ServiceCounterTable(0); unsigned int NumberOfServices; PVOID ParamTableBase;}
其中：

ServiceTableBase是 System Service Dispatch Table 的基地址NumberOfServices 由 ServiceTableBase 描述的服务的数目ServiceCounterTable 包含着 SSDT 中每个服务被调用次数的计数器ParamTableBase 包含每个系统服务参数字节数表的基地址
System Service Dispath Table（SSDT）：系统服务分发表，给出了服务函数的地址，每个地址4子节长。
System Service Parameter Table(SSPT)：系统服务参数表，定义了对应函数的参数字节，每个函数对应一个字节。

为了调用特定函数，系统服务调度程序KiSystemService将该函数的ID编号乘以4以获取它在SSDT中的偏移量。注意KeServiceDescriptorTable包含了服务数目，该值用于确定在SSDT或SSPT中的最大偏移量。下图也描述了SSPT。该表中的每个元素为单字节长度，以十六进制指定了它在SSDT中的相应函数采取多少字节作为参数。在这个示例中，地址0x804AB3BF处的函数采用0x18个字节的参数。

当调用INT 2E或SYSENTER指令时会激活系统服务调度程序。这导致进程通过调用该程序转换到内核模式。若将SSDT改为指向rootkit所提供的函数，而不是指向Ntoskrnl.exe或Win32k.sys,当非核心的应用程序调用到内核中时，该请求由系统服务调度程序处理，并且调用了rootkit的函数。这时，rootkit可以将它想要的任何假信息传回到应用程序，从而有效地隐藏自身以及所用的资源。
由于Windows系统版本对某些内存区域启用了写保护功能，SSDT就包括在其中，若向只读内存区域中执行写入操作，则会发生蓝屏死机(Blue Screen of Death，BSoD)。Windows中可以通过Memory Descriptor List(MDL)修改内存属性, 把原来SSDT的区域映射到我们自己的MDL区域中，并把这个区域设置成可写。MDL的结构：
typedef struct _MDL { struct _MDL *Next; CSHORT Size; //设置成MDL_MAPPED_TO_SYSTEM_VA ，这块区域就可写 CSHORT MdlFlags; struct _EPROCESS *Process; PVOID MappedSystemVa; PVOID StartVa; ULONG ByteCount; ULONG ByteOffset;} MDL, *PMDL;
知道KeServiceDscriptorTable的基址和入口数后，用MmCreateMdl创建一个与KeServiceDscriptorTable对应地址和大小的内存区域，然后把这个MDL结构的flag改成MDL_MAPPED_TO_SYSTEM_VA ，那么这个区域就可以写了。最后把这个内存区域调用MmMapLockedPages锁定在内存中。
通过微软已经导出的几个宏可以很方便地Hook SSDT。
SYSTEMSERVICE 宏采用由ntoskrnl.exe导出的Zw*函数的地址，并返回相应的Nt*函数在SSDT中的地址。Nt*函数是私有函数，其地址列于SSDT中。Zw*函数是由内核为使用设备驱动程序和其他内核组件而导出的函数。注意，SSDT中的每一项和每个Zw*函数之间不存在一对一的对应关系。
SYSCALL_INDEX宏采用Zw*函数地址并返回它在SSDT中相应的索引号。该宏和SYSTEMSERVICE宏发挥作用的原因在于Zw*函数起始位置的操作码。通过将该函数的第二个字节看作ULONG类型，这些宏能得到该函数的索引号。
HOOK_SYSCALL和UNHOOK_SYSCALL宏采用被钩住的Zw*函数的地址，获取其索引号，并自动将SSDT中该索引的相应地址与_Hook函数的地址进行交换。
#define SYSTEMSERVICE(_func) \ KeServiceDescriptorTable.ServiceTableBase[ *(PULONG)((PUCHAR)_func+1)] #define SYSCALL_INDEX(_Function) *(PULONG)((PUCHAR)_Function+1) #define HOOK_SYSCALL(_Function, _Hook, _Orig ) \ _Orig = (PVOID) InterlockedExchange( (PLONG) \ &MappedSystemCallTable[SYSCALL_INDEX(_Function)], (LONG) _Hook) #define UNHOOK_SYSCALL(_Func, _Hook, _Orig ) \ InterlockedExchange((PLONG) \ &MappedSystemCallTable[SYSCALL_INDEX(_Func)], (LONG) _Hook)
3.2 监视进程创建和销毁原理监视系统进程开始和结束的方法是通过DDK中的PsSetCreateProcessNotifyRoutine函数设置一个CALLBACK函数。该函数的原形如下：
NTSTATUS PsSetCreateProcessNotifyRoutine( IN PCREATE_PROCESS_NOTIFY_ROUTINE NotifyRoutine, IN BOOLEAN Remove);

NotifyRoutine指定了当进程被创建和结束的时候所需要调用的回调函数
Remove是用来告诉该函数是设置该回调还是移除

NotifyRoutine的类型为PCREATE_PROCESS_NOTIFY_ROUTINE，其定义为：
VOID (*PCREATE_PROCESS_NOTIFY_ROUTINE) ( IN HANDLE ParentId, IN HANDLE ProcessId, IN BOOLEAN Create);
NotifyRoutine的传入参数中，ParentId和ProcessId用来标识进程，Create则是用来表示该进程是正在被创建还是正在被结束。这样，每当进程被创建或者结束的时候，操作系统就会立刻调用NotifyRoutine这个回调函数并正确提供参数。
由于回调函数NotifyRoutine传入参数的类型为HANDLE，而PID为DWORD类型，可以通过强制转换为DWORD得到父进程、正在创建的进程的PID。
但此时仍不能得到父进程和正在创建的路径，通过调用一个未公开函数 PsLookupProcessByProcessId得到该进程的PEPROCESS，每个进程都有一个 EPROCESS 结构，里面保存着进程的各种信息，和相关结构的指针。这个函数的原型如下：
NTSTATUS PsLookupProcessByProcessId( IN ULONG ulProcId, OUT PEPROCESS * pEProcess);
得到该进程的PEPROCESS对象后，由于PEPROCESS是微软未公开的结构，而且在不同的操作系统下结构还不一样。EPROCESS 偏移0X1fc中保存着一个给人看的进程名，更准确的叫法是映像名称。
EPROCESS +1fc byte ImageFileName[16]
ImageFileName[16] 是一个16个字节长的字节数组，保存着进程名。当进程名的长度大于等于16个字节时，在 ImageFileName[16] 只保存进程名的前15个字节，ImageFileName[16] 最后一个字节为0，字符串的结束符。不同进程的进程名可以相同，比如打开多个记事本，那么每个记事本的 ImageFileName[16] 都是 “NOTEPAD.EXE”，进程名只是给人看的，每个进程的 进程ID 都是不同的。对于父进程，在PEPROCESS保存进程名，通过自定义的一个函数当前进程可以得到完整的路径，该函数定义如下：
PCWSTR GetCurrentProcessFileName() { DWORD dwAddress = (DWORD)PsGetCurrentProcess(); DWORD dwAddress1; if(dwAddress == 0 || dwAddress == 0xFFFFFFFF) return NULL; dwAddress += 0x1B0; if((dwAddress = *(DWORD*)dwAddress) == 0) return 0; dwAddress += 0x10; if((dwAddress = *(DWORD*)dwAddress) == 0) return 0; dwAddress1 = dwAddress;//2000 dwAddress += 0x3C; if((dwAddress = *(DWORD*)dwAddress) == 0) return 0; if (dwAddress < dwAddress1) dwAddress = dwAddress+dwAddress1; return (PCWSTR)dwAddress; }
但是对于正在创建的进程，并不能如此。必须使用ObOpenObjectByPointer得到进程名柄，ObOpenObjectByPointer的原型如下：
NTSTATUS ObOpenObjectByPointer( IN PVOID Object, // 进程的pEProcess IN ULONG HandleAttributes, IN PACCESS_STATE PassedAccessState OPTIONAL, IN ACCESS_MASK DesiredAccess, IN POBJECT_TYPE ObjectType, IN KPROCESSOR_MODE AccessMode, OUT PHANDLE Handle //此处将得到名柄);
得到名柄后可进一步通过未微软未公开的函数ZwQueryInformationProcess 可得到进程的镜像路径。ZwQueryInformationProcess原型如下：
NTSTATUS ZwQueryInformationProcess( IN HANDLE ProcessHandle, //传入进程句柄 IN PROCESSINFOCLASS ProcessInformationClass,// 指定此处为ProcessImageFileName OUT PVOID ProcessInformation,//此处得到进程镜像信息 IN ULONG ProcessInformationLength, OUT PULONG ReturnLength OPTIONAL);
得到镜像路径、进程PID等信息后可通知应用层用进程创建，应用层便能迅速取得进程信息，从而可以对进程在未完全加载完成时处理，在进程监控中，应该有内核事件对象、驱动层与用户层、用户层与驱动层通信的知识，首先是内核事件对象。
在内核中创建的事件对象，用户层只能读，不能给事件置信号，这多少给应用程序与驱动程序之间同步造成麻烦。
在使用KEVENT 事件对象前，需要首先调用内核函数KeInitialize Event 对其初始化，这个函数的原型如下所示：
VOID KeInitializeEvent( IN PRKEVENT Event, IN EVENT_TYPE Type, IN BOOLEAN State);

第一个参数Event 是初始化事件对象的指针
第二个参数Type 表明事件的类型，事件分两种类型：

一类是“通知事件”，对应参数为NotificationEvent另一类是“同步事件”，对应参数为SynchronizationEvent
第三个参数State 如果为TRUE，则事件对象的初始化状态为激发状态，否则为未激发状态。如果创建的事件对象是“通知事件”，当事件对象变为激发态时，需要我们手动将其改回未激发态。如果创建的事件对象是“同步事件”，当事件对象为激发态时，如果遇到相应的KeWaitForXXXX 等内核函数，事件对象会自动变回到未激发态

设置事件的函数是KeSetEvent，可通过该函数修改事件对象的状态，这个函数的原型如下：
VOID KeClearEvent( IN PRKEVENT Event);
在本系统进程监控模块中，我采用的方案是在内核监视进程的创建和销毁，并且应用程序开启新线程一直等待驱动中创建的命名事件。
在驱动层中，一旦检测到有进程进程的创建立即将事件对象置上信号， 这时应用层立即取得进程PID等信息，利用ZwSuspendProcess将进程挂起，从而可以对进程的信息进行进一步的检验，但是，ZwSuspendProcess是NTDLL.DLL中一个未导出的函数，在《Windows NT 2000 Native API Reference》中找不到其原型。我尝试过在驱动中申明NTSYSAPI的方法尝试利用其在内核层中挂起进程，可惜的是编译不能通过。
当然在用户层中挂起线程与在内核层中挂起进程是没有差别的，于是采用了在用户态下挂起进程的方法。
在用户态中使用未导出的内核函数，必须先将ZwSuspendProcess导出。导出.DLL内的函数方法之一是利用GetProcAddress ，这个函数的原型是：
FARPROC WINAPI GetProcAddress( __in HMODULE hModule, __in LPCSTR lpProcName);
传入的HMODULE的原型是：
HMODULE WINAPI LoadLibrary( __in LPCTSTR lpFileName);
于是通过下面两行代码可以将ZwSuspendProcess内核函数导出：
HANLDE hdll=LoadLibrary(L"NTDLL.DLL");SuspendProcess=(pfsuspend)GetProcAddress(hdll, "ZwSuspendProcess");
同时，还得利用相同方法将ZwResumeProcess函数导出，当然，必须得先申明函数原型。经过查阅《Windows System Call Table》，这两函数的原型如下（Nt与Zw系统函数完全相同）：
NTSYSAPI NTSTATUS NTAPI NtSuspendProcess( IN HANDLE Process);NTSYSAPI NTSTATUS NTAPI NtResumeProcess( IN HANDLE Process);
使用OpenProcess传入PID即可得到进程句柄，将获得的进程句柄传入 ZwSuspendProcess/ZwResumeProcess 中即可实现进程的挂起与恢复。
应用层传入信息的时候，可以使用WriteFile，也可以使用DeviceIoControl。
DeviceIoControl是双向的，在读取设备的信息也可以使用。DeviceIoControl 函数会使操作系统产生一 IRP_MJ_DEVICE_CONTROL 类型的IRP，然后这个IRP 会被分发到相应的派遣例程中。因此在驱动入口函数中需要先设置 IRP_MJ_DEVICE_CONTROL 的派遣例程，如
DriverObject->MajorFunctions[IRP_MJ_DEVICE_CONTROL] = MyDeviceIoControl;
DeviceIoControl 函数的原型如下：
BOOL DeviceIoControl( HANDLE hDevice, // handle to device DWORD dwIoControlCode, // operation LPVOID lpInBuffer, // input data buffer DWORD nInBufferSize, // size of input data buffer LPVOID lpOutBuffer, // output data buffer DWORD nOutBufferSize, // size of output data buffer LPDWORD lpBytesReturned, // byte count LPOVERLAPPED lpOverlapped// overlapped information);
第二个参数dwIoControlCode，它是I/O 控制码，即IOCTL 值，是一个32 位的无符号整型数值。实际上DeviceIoControl 与ReadFile 和WriteFile 相差不大，不过它可以同时提供输入/输出缓冲区，而且还可以通过控制码传递一些特殊信息。IOCTL 值的定义必须遵循DDK 的规定，使用宏CTL_CODE 来声明，如下：
#define MY_DVC_IN_CODE \(ULONG)CTL_CODE( FILE_DEVICE_UNKNOWN, \0x900, \ // 自定义IOCTL 码METHOD_BUFFERED, \ // 缓冲区I/OFILE_ALL_ACCESS)
当然在应用DeviceIoControl时，应用程序应该与驱动程序包含相同的IOCTL定义，最好的方法是共享一个头文件，并且应用程序需要包含winioctl.h头文件。
下为本系统危险进程主动防御模块的流程图

3.3 监视注册表修改/创建原理注册表监视原理是通过HOOK_SYSCALL宏勾住ZwSetValueKey, 该宏定义如下：
#define HOOK_SYSCALL(_Function, _Hook, _Orig ) \ _Orig = (PVOID) InterlockedExchange( (PLONG) \
具体挂接语句为：
HOOK_SYSCALL(ZwSetValueKey,HookZwSetValueKey,RealZwSetValueKey);
其中ZwSetValueKey用于更新或者新建一个键值，它的原型如下：
NTSTATUS ZwSetValueKey( IN HANDLE KeyHandle, IN PUNICODE_STRING ValueName, IN ULONG TitleIndex, IN ULONG Type, IN PVOID Data, IN ULONG DataSize);
由于DDK文档中没有该函数，在驱动中使用它时必须申明其原型，方法如下：
NTSYSAPI NTSTATUS NTAPI ZwSetValueKey( IN HANDLE KeyHandle, IN PUNICODE_STRING ValueName,// The name of the value to be set. IN ULONG TitleIndex, IN ULONG Type, IN PVOID Data, // Points to a caller-allocated buffer or variable that contains the data of the value. IN ULONG DataSize);
HOOK_SYSCALL时，为了保存ZwSetValueKey 函数的真实地址在RealZwSetValueKey中，须定义一个与之类似的结构：
typedef NTSTATUS (*REALZWSETVALUEKEY)( IN HANDLE KeyHandle, IN PUNICODE_STRING ValueName, IN ULONG TitleIndex OPTIONAL, IN ULONG Type, IN PVOID Data, IN ULONG DataSize);REALZWSETVALUEKEY RealZwSetValueKey=NULL;//初始化
Hook ZwSetValueKey后，当应用层修改注册时，总会先进入我们挂接的函数HookZwSetValueKey，假若在HookZwSetValueKey函数中不再调用真实的ZwSetValueKey，那么应用层无法修改、创建注册表键键值。HookZwSetValueKey定义与ZwSetValueKey一致，如下：
NTSTATUS HookZwSetValueKey( IN HANDLE KeyHandle, IN PUNICODE_STRING ValueName, IN ULONG TitleIndex OPTIONAL, IN ULONG Type, IN PVOID Data, IN ULONG DataSize);
HookZwSetValueKey传入参数包含了将要修改的信息：ValueName指向了要修改的键名。
在Win32 API中，管理内核对象是通过HANDLE，而在内核内部是通过Object来管理内核对象的。下面是Object属性结构：
typedef struct _OBJECT_ATTRIBUTES { ULONG Length; //结构长度 HANDLE RootDirectory; //根目录 UNICODE_STRING *ObjectName; //Object的名称 ULONG Attributes; //属性 PSECURITY_DESCRIPTOR SecurityDescriptor;//安全描述符 PSECURITY_QUALITY_OF_SERVICE SecurityQualityOfService;} OBJECT_ATTRIBUTES,*POBJECT_ATTRIBUTES;
我们感兴趣的是ObjectName成员，因为它包含了注册表名。
但要想进一步得到要修改的键值则必须进一步通过ObReferenceObjectByHandle得到对象，这是一个在驱动开发中经常用到的函数，该函数原型如下：
NTSTATUS ObReferenceObjectByHandle( IN HANDLE Handle, //此处传入HookZwSetValueKey的参数KeyHandle IN ACCESS_MASK DesiredAccess, IN POBJECT_TYPE ObjectType OPTIONAL, IN KPROCESSOR_MODE AccessMode, OUT PVOID *Object, //这里返回Object指针 OUT POBJECT_HANDLE_INFORMATION HandleInformation OPTIONAL);
得到PObject后，理论上可以其通过获得键名信息，由于OBJECT_ATTRIBUTES是不公开的结构，不同操作系统可能不同。为了跨越不同的版本，这里采用未公开的内核函数ObQueryNameString，才能得到键名信息，至此，只得到了操作注册表方面的信息，因为还需得到是哪个进程引发的操作，进程名可通过当前进程偏移量方法获取，而进程的完整路径同样是通过一个自定义函数取得：
PCWSTR GetCurrentProcessFileName() { DWORD dwAddress = (DWORD)PsGetCurrentProcess(); DWORD dwAddress1; if(dwAddress == 0 || dwAddress == 0xFFFFFFFF) return NULL; dwAddress += 0x1B0; if((dwAddress = *(DWORD*)dwAddress) == 0) return 0; dwAddress += 0x10; if((dwAddress = *(DWORD*)dwAddress) == 0) return 0; dwAddress1 = dwAddress;//2000 dwAddress += 0x3C; if((dwAddress = *(DWORD*)dwAddress) == 0) return 0; if (dwAddress < dwAddress1) dwAddress = dwAddress+dwAddress1; return (PCWSTR)dwAddress; }
相关方面的信息获取成功后，下一步是检查这些信息，或者让用户决定是否执行这个操作，如果执行，在HookZwSetValueKey只需将传入的各参数原样交给真实的RealZwSetValueKey的处理即可，否则不交给真实RealZwSetValueKey处理，从而导致应用程度修改操作失败。
由于应用层不能简单地通知驱动层的事件，所以本系统采用了双事件：驱动层通知应用层事件、应用层通知驱动层事件，其中应用层通知驱动层事件通过传递IOCTL ，驱动在IOCTL的派遣函数中设置事件。IOCTL定义如下：
#define IOCTL_NTPROCDRV_SET_APPEVENT_OK CTL_CODE(FILE_DEVICE_UNKNOWN,0x0911, METHOD_BUFFERED, FILE_READ_ACCESS | FILE_WRITE_ACCESS)
在驱动的派遣例程中KeSetEvent置信号方法如下：
case IOCTL_NTPROCDRV_SET_APPEVENT_OK: { KdPrint(("放行!应用层通知驱动层的事件")); RegPass=1; //全居变量，通过,事件设置必须在后面 KeSetEvent(RegAppEvent,IO_NO_INCREMENT,FALSE); status=STATUS_SUCCESS;}break;
下为本系统注册表主动防御模块的流程图

3.4 监视文件修改/创建原理文件监视原理是通过HOOK_SYSCALL宏勾住ZwWriteFile, 该宏定义如下：
#define HOOK_SYSCALL(_Function, _Hook, _Orig ) \ _Orig = (PVOID) InterlockedExchange( (PLONG) \
具体挂接语句为：
HOOK_SYSCALL(ZwWriteFile,HookZwWriteFile,RealZwWriteFile);
ZwWriteFile用于向文件写入数据. 为了能成功挂接ZwWriteFile，与注册表监控相似，必须先申明其原型、Hook函数的原型、用于保存真实地址的RealZwWriteFile。
NTSYSAPI NTSTATUS NTAPI ZwWriteFile( IN HANDLE FileHandle, IN HANDLE Event OPTIONAL, IN PIO_APC_ROUTINE ApcRoutine OPTIONAL, IN PVOID ApcContext OPTIONAL, OUT PIO_STATUS_BLOCK IoStatusBlock, IN PVOID Buffer, IN ULONG Length, IN PLARGE_INTEGER ByteOffset OPTIONAL, IN PULONG Key OPTIONAL);
申明保存真实地址的RealZwWriteFile：
typedef NTSTATUS (*ZWWRITEFILE)( IN HANDLE FileHandle, IN HANDLE Event OPTIONAL, IN PIO_APC_ROUTINE ApcRoutine OPTIONAL, IN PVOID ApcContext OPTIONAL, OUT PIO_STATUS_BLOCK IoStatusBlock, IN PVOID Buffer, IN ULONG Length, IN PLARGE_INTEGER ByteOffset OPTIONAL, IN PULONG Key OPTIONAL);ZWWRITEFILE RealZwWriteFile＝NULL;
申明Hook函数原型：
NTSTATUS HookZwWriteFile( IN HANDLE FileHandle, IN HANDLE Event OPTIONAL, IN PIO_APC_ROUTINE ApcRoutine OPTIONAL, IN PVOID ApcContext OPTIONAL, OUT PIO_STATUS_BLOCK IoStatusBlock, IN PVOID Buffer, IN ULONG Length, IN PLARGE_INTEGER ByteOffset OPTIONAL, IN PULONG Key OPTIONAL );
由于本软件不是做文件加密，因些目标是从传入HookZwWriteFile的参数中解析出进程名、进程完整路径、写入（新建）文件的完整路径。其中，进程名、进程完整路径与注册表监视中的原理相似，通过进程上下文和偏移量可获得。
将要写入的文件的完整路径（以下称目标路径）获得需几步，首先通过传入的FileHandle句柄，使用ObReferenceObjectByHandle得到文件对象，ObReferenceObjectByHandle原型如下：
NTSTATUS ObReferenceObjectByHandle( IN HANDLE Handle, //传入FileHandle IN ACCESS_MASK DesiredAccess, IN POBJECT_TYPE ObjectType OPTIONAL,//指定为*IoFileObjectType IN KPROCESSOR_MODE AccessMode, OUT PVOID *Object, //得到文件对象 OUT POBJECT_HANDLE_INFORMATION HandleInformation OPTIONAL);
由于FileObject是一个没有被文档化的对象（This information class is not implementedby any of the supported file systems.），仅知道在文件对象中FileName域保存着部分目标路径，DeviceObject域保存着卷标信息，但是对于本系统这已经够用了。
以”C:\windows\1.txt”为例，FileName这个UNICODE_STRING的Buffer中保存着“ \windows\1.txt”，经过转换后的卷标将保存着“C:”，使用的函数是IoVolumeDeviceToDosName，以下是函数原型：
NTSTATUS IoVolumeDeviceToDosName( IN PVOID VolumeDeviceObject, //传入((PFILE_OBJECT)fileobj)->DeviceObject OUT PUNICODE_STRING DosName //得到卷标);
文件监控做为本系统的一个辅助模块，主要监视的操作系统内进程的文件操作行为，是必需的一个模块，病毒的破坏操作系统的时，往往伴随着文件的释放与生成，例如木马下载者，本身可能无毒，但是后期可以从网上下载其它木马，再比如本机中了蠕虫后，exe大面积感染必然是对各文件进行了写入操作，通过文件监控即可检测到这种行为。同时，能过文件监控，在查打出木马之后，可以对其“同伙”一伙打尽，下图是本系统文件监控的流程图：

3.5 内存映射监控原理内存监视原理是通过HOOK_SYSCALL宏勾住ZwCreateSection, ZwCreateSection用于routine creates a section object.Hook方法与上类似。该函数原型为：
NTSYSAPI NTSTATUS NTAPI ZwCreateSection( OUT PHANDLE SectionHandle, IN ACCESS_MASK DesiredAccess, IN POBJECT_ATTRIBUTES ObjectAttributes OPTIONAL, IN PLARGE_INTEGER MaximumSize OPTIONAL, IN ULONG SectionPageProtection, IN ULONG AllocationAttributes, IN HANDLE FileHandle OPTIONAL//此处包含文件路径信息 );
其中最后一个参数FileHandle句柄中包含有目标文件的路径信息，与文件监视原理相同，使用ObReferenceObjectByHandle得到文件对象，在FileObject中可进一步取得文件路径与卷标。进程名可通过当前进程偏移量方法获取，进程的完整路径同样是通过一个自定义函数取得，以上原理中已多次提到。
一个程序得以运行必然要经过内存映射，勾住ZwCreateSection可以拦截记录风险程序的行为，与注册表监控模块、文件监控模块、进程监控模块共同组成完整的程序行为监控系统。
以下是本系统内存加载监控的流程图

3.6 云安全模块原理“云安全（Cloud Security）”计划是网络时代信息安全的最新体现，它融合了并行处理、网格计算、未知病毒行为判断等新兴技术和概念，通过网状的大量客户端对网络中软件行为的异常监测，获取互联网中木马、恶意程序的最新信息，传送到Server端进行自动分析和处理，再把病毒和木马的解决方案分发到每一个客户端。
未来杀毒软件将无法有效地处理日益增多的恶意程序。来自互联网的主要威胁正在由电脑病毒转向恶意程序及木马，在这样的情况下，采用的特征库判别法显然已经过时。云安全技术应用后，识别和查杀病毒不再仅仅依靠本地硬盘中的病毒库，而是依靠庞大的网络服务，实时进行采集、分析以及处理。整个互联网就是一个巨大的“杀毒软件”，参与者越多，每个参与者就越安全，整个互联网就会更安全。
本系统云安全模块分成服务器，客户端两块。
服务器采用windows+apache+php+mysql架构，复责返回客户端查询文件信息，处理客户端上传的可疑文件。
客户端集成在本系统中，可获取文件名、文件详细路径、文件MD5、文件签名等信息，在必要的情况下以这些信息向服务器查询验证信息，并且在客户机允许的情况下自动上传可疑文件，让服务器处理并且反馈结果。
同时客户端也会将众多用户处理程序行为的信息传至服务器，服务器经过统计分析，可更新各客户机上的规则，实现云规则。
下图为云模块原理：

3.7 规则动态加载原理本系统规则存储于一access数据库文件中，程序运行时将从数据库文件初始化规则，规则在程序中是以几条STL中的双向链表（LIST）实现的。
在规则未经修改时，避免了多次查询数据库而耗时浪费资源。当本系统模块修改、删除数据库时，保存着规则的双向链表将会更新，实现了规则的动态更新。
下图为规则动态更新原理图：

4 性能与测试4.1 测试环境本系统的测试环境为：

VMware 6.0
Windows XP SP3
驱动级云安全主动防御
迅雷
木马
等等

4.2 进程监控测试
测试项目：测试本系统是否能够有效监控进程创建
测试工具：驱动级云安全主动防御、记事本程序、SRVINSTW.EXE(病毒)
测试过程：

开启本系统进程监控运行”记事本” 程序将”记事本” 程序行为加入白名单,再次运行运行SRVINSTW.EXE(病毒)将SRVINSTW.EXE(病毒)行为加入黑名单,再次运行
结果及分析如下所示：

下图为在部署了本系统的主机上打开桌面” 新建 文本文档.txt”时, ” 新建 文本文档.txt”并没有被打开,而是弹出了本系统的用户确认对话框，在云安全模块已经开启的情况下，系统自动联网查询该文件信息，在行为描述一栏有提示“windows自带记事本，该程序是安全的”，用户点击”放行一次”, ” 新建 文本文档.txt”将被打开；用户点击”我认识它，永久放行”, 以后打开记事本程序将都不再提醒。

下图为把本次程序行为加入白名单，即始终允许本程序启动。

加入白名单后，再次打开桌面”新建 文本文档.txt”，本系统不再弹出提示信息框，”新建 文本文档.txt”被直接打开，如图：

此时桌面有一病毒文件SRVINSTW.EXE，在云安全模块已经开启情况下，双击打开，系统将自动联网查询该文件信息，进程打开被阻塞，本系统弹出用户确认对话框，在行为描述一栏有提示“该程序为病毒，请谨慎运行！”，用户选择“禁止一次”，该程序被阻止运行；用户选择“这个很危险，永久禁止”，将自动添加黑名单规则，该程序被阻止运行。如下图：

用户选择“禁止一次”，进程结束。接着将此进程信息加入黑名单：

再次双击桌面图标，双击后没有反应，从进程监控主页面拦截信息可知，该程序还没完全开启时已经被主动防御进程结束了。


从实验结果可以看出，本系统能成功拦截进程创建，在云安全模块和用户维护的规则下能成功阻击病毒的运行。
4.3 注册表监控测试
测试项目：测试本系统是否能够有效监控注册表创建、修改
测试工具：卓然驱动级云安全主动防御、迅雷、DAEMON Tools（虚拟光驱软件）
测试过程：

开启本系统注册表监控功能，运行迅雷，运行DAEMON Tools修改迅雷配置，设置“开机启动迅雷”，并放行一次将修改“开机启动迅雷”程序行为加入白名单,再次修改“开机启动迅雷”修改DAEMON Tools开机启动，并拒绝一次将修改DAEMON Tools开机启动行为加入黑名单,再次修改DAEMON Tools开机启动，查看结果
结果及分析如下所示：

打开迅雷，配置迅雷，勾选“开机启动迅雷”， 如图：

本系统立即暂停该操作，并且弹出对话框，请求用户确认是不是要进程该操作，在云安全模块开启的情况下，行为描述一栏会从网络获取该行为的信息，此处为“迅雷开机启动”，如图：

若此时选择“放行一次”，修改行为将生效；选择“相同一直放行”，修改行为将生效，且以后相同行为不再提醒；选择“禁止一次”，修改请求将被拒绝；选择“相同一直禁止”，修改请求将被拒绝，且以后相同行为不再提醒，直接拒绝。
测试时选择“放行一次”，再次打开迅雷的配置，可见修改已经成功。

接着，把迅雷添加启动项行为加入白名单规则，如图：

再次打开迅雷，修改配置，去掉“开机启动迅雷”前的勾，点击确认，本系统没有弹出确认对话框，修改生效。
打开DAEMON Tools，修改DAEMON Tools开机启动，如图：

并且弹出对话框，请求用户确认是不是要进程该操作，在云安全模块开启的情况下，行为描述一栏会从网络获取该行为的信息，此处为“daemon.exe添加启动项可能影响您电脑的开机速度”，如图：

因为该行为可能影响开机速度，测试时选择禁止一次，拒绝该操作，daemon.exe弹出修改注册表出错，即修改启动不成功，如图：

将DAEMON Tools添加开机启动行为加入黑名单,如图：

再次修改DAEMON Tools开机启动，本系统没有弹出确认对话框，DAEMON Tools直接报错，修改不成功，如图：

4.4 文件监控测试
测试项目：测试本系统是否能够有效监控文件修改/创建
测试工具：卓然驱动级云安全主动防御、记事本程序
测试过程：

开启本系统文件监控在桌面新建一文本文档，任意写入文本信息，保存。查看结果修改本系统注册表规则，保存。查看结果
结果及分析如下所示：

在桌面新建一文本文档，任意写入文本信息，回到本系统文件监控模块，查看信息如下：

由文件监控信息可知，explorer.exe先创建了“最近打开文件”的链接，接着notepad.exe修改了桌面“新建 文本文档.txt”,完整地记录了修改文件信息。
在注册表监控测试时，由于本程序需要修改数据库记录，查看文件监控信息，此行为也记录了下来，如图：

文件监控在新建或修改.exe/.dll/.sys等可执行文件时，在云安全模块开启的情况下，能向服务器验证MD5、签名、文件名等信息，保证不被下载者等木马从网络下载有害程序破坏系统。
此外，在有蠕虫感染系统时，同一进程将对系统众多可执行文件感染，必然要有打开的修改操作，在文件监控功能与监控中心的配合下，能在早期就察觉出这种危险行为，进而阻止。
4.5 内存加载监控测试
测试项目：测试本系统是否能够有效监控内存加载
测试工具：卓然驱动级云安全主动防御、记事本程序，
测试过程：

开启本系统内存加载监控在桌面新建一文本文档，任意写入文本信息，保存。查看结果停止本系统进程监控服务，再次启动，查看结果
结果及分析如下所示：

停止本系统进程监控服务，并再次启动，查看内存加载信息，由加载信息可看出，本系统的进程监控服务服务加载时需要一个名为ProcMon.sys加载进入内存，如图：

在桌面新建一文本文档，任意写入文本信息，回到本系统内存加载模块，查看信息如下：

从内存加载信息中，可以查看notepad.exe进程加载时哪些文件映射进入了内存，得到结果后可进一步处理。
在云安全模块开启的情况下，本系统会自己向服务器验证加载进入内存的文件信息，与其它模块相互配合，可将病毒及期衍生物一网打尽。
参考文献[1] Mark E.Russinovich, David A.Solomon .深入解析Windows操作系统. 电子工业出版社, 2007年6月.
[2] 张帆.Windows驱动开发详解.电子工业出版社.2008年2月.
[3] 张静盛.windows编程循序渐进. 机械工业出版社. 2008年6月.
[4] Jeffrey Richter.WINDOWS核心编程. 清华大学出版社. 2008年9月
[5] 谭文，杨潇，邵坚磊.寒江独钓—Windows内核安全编程.电子工业出版社.2009.6
[6] 谭文，邵坚磊.天书夜读—从汇编语言到windows内核编程.电子工业出版社.2009.3
[7] Greg Hoglund/James Butler .RootKits――Windows内核的安全防护. 清华大学出版社. 2007.4
[8] liuke_blue.黑客防线.再论进程防火墙.200809
[9] SVEN B. SCHREIBER .Undocumented Windows 2000 Secrets
[10] Windows NT 2000 Native API Reference

1 分析1.1 需要完成的功能1.1.1 基本要求
设计图形界面，可以实现英文文章的编辑与检索功能
编辑过程包括：

创建新文件；打开文件；保存文件查找：输入单词在当前打开的文档中进行查找，并将结果显示在界面中替换：将文章中给定的单词替换为另外一个单词，再存盘等
对于给定的文章片段（30<单词数量<100），统计该片段中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。在 图形界面中演示该过程
对于给定的多篇文章构成的文档集中，统计不同词汇的出现频率，并进行排序，在界面中显示 TOP 20 的排序结果
对于给定的多篇文章构成的文档集中，建立倒排索引，实现按照关键词的检索，并在界面中显示检索的结果（如：关键词出现的文档编号以及所在的句子片段，可以将关键词高亮显示）

1.1.2 扩展要求
界面设计的优化
对于编码与译码过程，可以自行设计其他算法
扩展检索：例如，可以实现多于 1 个关键词的联合检索，要求检索结果中同时出现所有的关键词
优化检索，对于检索结果的相关性排序，例如：包含关键词的数量等信息为依据
可以自行根据本题目程序的实际应用情况，扩展功能

1.2 需要处理的数据1.2.1 英文文本多个 txt 文档的导入，主要是文件路径，然后对文档中的内容进行处理。 首先读取文本。然后统计单词、字符的频率以及位置，生成索引；或者直接进行查找等功能。
1.2.2 用户输入的字符串有多个功能需要用户输入字符串，比如创建新的文档需要命名、搜索单词、修改文档、 在文档中替换内容。
1.2.3 网络爬取的信息从网站上爬取单词翻译信息，包括 HTML 页面。
1.2.4 选择的文档信息用户通过“导入文件”，通过窗口选择并导入文档。
1.3 程序开发运行选用的环境
操作系统

版次：Windows 10 家庭中文版版本：1709 OS 内部版本：16299.125
语言

Python 3.6.3
库

PyQt5==5.9.2 bs4==0.0.1 six==1.11.0 requests==2.18.4

1.4 用户界面的设计使用 PyQt5 库设计用户界面；主要窗口及功能如下： main：进入程序的 MainWindow，用来导入文件、搜索关键字等。

item：从 main 进入。主体为显示文章的文本框，同时有多个功能按钮。

1.5 主要流程图
2 数据结构设计2.1 所定义主要的数据结构2.1.1 Python 内置结构
list进行列表建立，以及一些需要排序的操作，其他大部分数据结构无法排序，需要先转化成 list，做排序再考虑转化回去(较麻烦)，或者直接进行操作。用[]表示 。
dict进行词典建立,使用键-值（key-value）存储，具有极快的查找速度，用于在不同目录下查找文本，不同文本下查找单词位置的功能，用牺牲空间的方式加快查找速度。用{}表 示。
tuple与列表一样，也是一种序列，唯一不同的是元组不能被修改。用()表示。

2.1.2 哈夫曼树给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
本次构建的哈夫曼树的权值是文章中出现的所有字符的频率。并由此生成每个字符的编 码，频率越高，其叶子结点距根越近，对应的编码也就越短。
2.1.3 索引结构构建的索引，用来更快更方便的搜索单词或统计频率。利用 Python 本身的 dict, list 以及 tuple 建立索引，结构如下：
[(文件地址 1, [{'word': 单词 1, 'pos': [位置下标]}, {'word': 单词 2, 'pos': [位置下 标…]},…]), (文件地址 2, [{'word': 单词 1, 'pos': [位置下标]} , {'word': 单词 2, 'pos': [位置下 标…]},…]),…]
2.2 程序整体结构以及各模块的功能描述
main.py：总的 main 启动文件
img.py：资源文件。图片转为文本格式，以便于程序的封装
KMP.py

def get_next(p)：寻找前缀后缀最长公共元素长度，计算字符串 p 的 next 表def kmp(s, p)：核心计算函数，返回字符串 p 的位置下标def positions(string, pattern)：查找 pattern 在 string 所有的出现位置的起始下标def count(string, pattern)：计算 pattern 在 string 的出现次数
Huffman.py

class Node:
def __init__(self, freq)：初始化属性 left, right, father, freqdef isLeft(self)：返回该节点是否是父节点的左节点
def create_Nodes(freqs)：根据频率表创建叶子结点def create_Huffman_Tree(nodes)：根据频率大小，使用队列创建哈夫曼树def Huffman_Encoding(nodes, root)：用哈夫曼树生成哈夫曼对照表def cal_count_freq(content)：计算字符频率def cal_Huffman_codes(char_freqs)：整合上述 functions
File.py

def search(files, keyword)：用 KMP 算法搜索计算所有传入的文件中 keyword 的数量，返回有序的文件及数量列表def cal_words_freq(files, reverse=True)：用 KMP 算法搜索计算所有传入的文件中所有单词各自的数量，返回有序的文件及单词列表及数量def cal_words_freq(files, reverse=True)：用 KMP 算法搜索计算所有传入的文件中所有单词各自的数量，返回有序的文件及单词列表及位置class File:
def __init__(self, file_pos)：初始化函数，传入文件路径作为属性def get_content(self)：获得文件内容def set_content(self, content)：将文件内容修改为 contentdef get_huffman_codes(self)：统计文件内容中 word 出现的次数def get_huffman_codes(self)：获得哈夫曼编码表def get_encodeStr(self)：获得文件内容通过哈夫曼编码表编码后的字符串def get_decodeStr(self, huffmanStr)：通过哈夫曼编码表将编码转换成原字 符串

SplashScreen.py

class SplashScreen:
def __init__(self)：继承 PyQt5.QtWidgets.QSplashScreendef effect(self)：启动页的渐隐渐出特效

main_UI.py

class UI:
def __init__(self)：构造函数，将属性 search_status 和 freqs 初始化def init(self)：设置事件触发def add_files(self)：调用 PyQt5 的 FileDialog 选择要添加的文件def about(self)：“关于”窗口def create_file(self)：创建文本文档，并添加文件def cal_words_freqs(self)：使用索引，统计词频并生成显示降序列表def load_package(self)：读取索引def packaging(self)：生成索引文件。使用 six 库中 pickle 打包成二进制文件def clear_list(self)：清空文件列表def get_research_content(self)：获得用户输入的需要检索的内容def get_files_from_table(self)：获得当前文件列表def creat_tableWidget(self, files, nums=[], poss=[])：在 GUI 中生成列表及相关信息def closeEvent(self, event)：窗口关闭时出发的关闭事件def search(self)：根据索引查找多个单词或词组，并显示频率及位置信息def buttonClicked(self)：debug 所用，在底部状态栏显示相关信息def itemClicked(self, row, col)：文件表单项目点击事件，打开新的 item 窗口

item_UI.py

class item_UI
def __init__(self, file_pos, keyword=None)：初始化，将属性 file 初始化为file_pos，同时高亮 keyworddef init(self, keyword, filename)：连接按钮点击事件def highlight(self, pattern, color=”yellow”)：将所有 pattern 做黄色高亮处理def hightlight_specific(self, pos=(0, 0), color=”gray”)：按位置高亮def encode(self)：调用 self.file.get_encodeStr()显示编码def decode(self)：调用函数进行译码def huffman_codes(self)：显示哈夫曼编码表def edit(self)：将文本框控件变为可编辑def save(self)：将文本框中的文本保存到文件中def search_substitute(self)：打开新窗口，查找或替换def translate(self)：翻译所选文本

about_UI.py：“关于”窗口
freq_UI.py：显示表单的窗口。用来显示词频统计
huffman_UI.py：显示表单的窗口。用来显示哈夫曼表
file_UI.py：用来选择文件的窗口
create_file_UI.py：新建文档的窗口
progressbar_UI.py：进度条窗口
search_UI.py

class search_UI:
def __init__(self, item_ui)：构造函数def init(self)：连接按钮事件def prepare(self)：计算所有用户查询的单词的位置信息def next_word(self)：高亮下一个搜索结果def count(self)：计数def substitute(self)：替换当前高亮的一个结果def substitute_all(self)：替换所有符合条件的结果


3 详细设计3.1 构造哈夫曼树
3.2 KMP 算法3.2.1 获取 next 表
3.2.2 文本匹配
3.3 UI 设计3.3.1 主界面搜索多个单词和词组

创建索引

3.3.2 item 窗口
查找下一个

翻译功能

显示哈夫曼编码表

4 总结与提高当我刚拿到题目要求的时候，我的内心是抗拒的——需要自己完成哈夫曼编码（包括统计词频，建立哈夫曼树，根据哈夫曼树计算对应的编码），KMP 算法（之前只是听说过，完全不清楚原理及算法），而且这一切都需要用图形用户界面来展现出来，于是只能硬着头皮上了。
最开始时，我决定从数据结构和算法入手，先不管图形界面。于是开始在网上学习 KMP 算法的原理及步骤。在和同学讨论的过程中，我们慢慢地结合着资料把代码写了出来，并测试了与传统算法的速度对比，很有成就感。
然后是哈夫曼树。这部分相对简单，因为其原理我们已经在上学期的课程中接触过，所以主要的时间都用来写代码。过程很顺利，达到了理想结果。
到了最麻烦的图形界面部分，开始时我本想使用 wxpython 库来实现，但在简单的了解 过后，我发现这个库的更新情况不是很理想，尤其是它的 designer 和库的版本不同步，designer 生成的代码甚至直接运行会报错，于是我放弃了，转向更为成熟的、跨平台的 PyQt5。早就 听说过 Qt 的大名，终于有机会使用下了。最开始遇到的问题，每个程序进程只能运行一个 MainWindow 类，在不知道的情况下打开多窗口一直报错，后来得以解决。随之而来的是文本的高亮问题，后来查到的方法是在文本框中控制虚拟光标选中目标然后更改其格式，已达到高亮的效果。
在完成大部分功能要求后，我开始想其他扩展功能。翻译功能是个很棒的想法。起初， 我想建立本地的词典资源文件，通过索引或二分法进行查找，但后来发现很难找到好用的文本词典资源。于是转而使用爬虫进行翻译，还好效果不错，只是需要联网。
另一个扩展功能本来是想做通过自然语言识别来对文本进行一些情感分析或者全文概括，但在查阅部分资料后发现很难实现。首先，文本本身多为记叙文，很长且情感并不明显， 其次需要的类似的数据集几乎找不到，所以最终放弃了这个想法。
最后是将整个程序封装成 Windows 下运行的 exe 应用程序，使用了 pyinstaller 库。过程很简单，只需要在命令行进行一些操作就好了。
在整个编写课设的过程中，主要学习了 PyQt5 的使用，对于以后编写简单的图形用户界 面非常有帮助。复习巩固了哈夫曼树的创建。学习了 KMP 这种字符串匹配的算法。同时我对于 Python 的使用也更加熟练。
对于自己完成课设情况的评价呢，我觉得我完成的还是不错的（哈哈哈）。虽然从美观方面来讲很一般，但是功能的实现以及代码的结构还是可以的，基本功能和扩展功能基本都做到了，后期的 Bug 调试也基本保证了正常使用过程中程序不会报错崩溃。如果要改进的话，可能更多会把注意力放在如何把各种功能的表现形式变得更美观。
非常感谢这种独自完成整个项目的机会，各方面都有所提升，也很有成就感。能看着整个程序跑起来还是非常爽的！

前 言程序不是写出来的，而是调出来的！回忆学生时代写程序的时候，遇到 bug 往往很无奈，常常是把程序从头到尾看一遍，或者是在一些关键的地方，觉得会出错的地方，printf一下，来判断是不是这里出错了。曾经还觉得这个方法不错，沾沾自喜呢。
后来工作后，或多或少要调一些程序，但是总觉得不得要领。 所以我觉得无论是软件逆向工程的研究者还是开发人员，都有必要自己实现一个调试器，当你的调试器完成的时候，或许你对软件调试会有一种顿悟的感觉。
而且可以根据自己的需要，写一个适合自己的调试器，对于逆向或者调试程序来说，都会得心应手，而且还可以过针对某些调试器的反调试哦！
因鄙人没有天马行空的创意，亦没有巧夺天工的技术!所以调试器设计得也有很多不足，但也略有心得，故拿出来，与大家分享之，希望能帮助到有需要的人。
由于本人能力有限，文中必然有错漏之处，恳请读者不吝赐教。
第一章 调试器框架1.1 框架的搭建有写过Windows程序的人都知道Windows是基于消息的，当程序创建，窗口移动，键盘按下等，窗口过程函数都会收到消息，然后根据消息做相应的处理。其实调试器也是这样的，在 MSDN 中已经给出了一个现成的框架了，如下，我已经去掉部分注释了，如果想获得祥细信息的话可以查下 MSDN。
DEBUG_EVENT DebugEv; // debugging event information DWORD dwContinueStatus = DBG_CONTINUE; // exception continuation for(;;) { // Wait for a debugging event to occur. The second parameter indicates // that the function does not return until a debugging event occurs. WaitForDebugEvent(&DebugEv, INFINITE); // Process the debugging event code. switch (DebugEv.dwDebugEventCode) { case EXCEPTION_DEBUG_EVENT: // Process the exception code. When handling // exceptions, remember to set the continuation // status parameter (dwContinueStatus). This value // is used by the ContinueDebugEvent function. switch (DebugEv.u.Exception.ExceptionRecord.ExceptionCode) { case EXCEPTION_ACCESS_VIOLATION: case EXCEPTION_BREAKPOINT: case EXCEPTION_DATATYPE_MISALIGNMENT: case EXCEPTION_SINGLE_STEP: case DBG_CONTROL_C: } case CREATE_THREAD_DEBUG_EVENT: case CREATE_PROCESS_DEBUG_EVENT: case EXIT_THREAD_DEBUG_EVENT: // Display the thread's exit code. case EXIT_PROCESS_DEBUG_EVENT: // Display the process's exit code. case LOAD_DLL_DEBUG_EVENT: // Read the debugging information included in the newly // loaded DLL. case UNLOAD_DLL_DEBUG_EVENT: // Display a message that the DLL has been unloaded. case OUTPUT_DEBUG_STRING_EVENT: // Display the output debugging string. } // Resume executing the thread that reported the debugging event. ContinueDebugEvent(DebugEv.dwProcessId, DebugEv.dwThreadId, dwContinueStatus); }
Windows 提供了一些 Debug API，他们已经实现了一般调试器所需的大部分功能，通过现有的框架和Windows提供的API我们可以很容易的搭建起一个调试器的框架出来。
1.2 调试事件种类
1.3 调试事件处理通过对上面几个事件的处理，基本可以实现我们的调试器了。当我们创建一个调试进程后，调试器会收到 CREATE_PROCESS_DEBUG_EVENT 事件，在这里我们做一些PE解析工作，比如取得OEP等等，然后在OEP处下一个Int3 断点，处理完之后,将调用ContinueDebugEvent函数来继续线程的运行，这里要注意，这个函数的 dwContinueStatus 有二个取值，DBG_CONTINUE 和DBG_EXCEPTION_NOT_HANDLED，如果这个异常我们可以处理则取DBG_CONTINUE ， 否 则 取 DBG_EXCEPTION_NOT_HANDLED 。DBG_EXCEPTION_NOT_HANDLED 则告诉操作系统，我的程序不能处理这个异常，给你处理，然后操作系统再问下调试进程能不能处理，如果不能的话，直接给干掉。
同时还有一点要注意，当创建一个调试进程的时候，系统会先调用一次DebugBreak 函数，我们只要判断一下是不是系统调用的，是的话无视掉就行了。
接着调试器再调用WaitForDebugEvent函数等待调试事件的发生，直到接收到EXIT_PROCESS_DEBUG_EVENT事件时结束。
第二章 内存断点2.1 问题的提出与分析2.1.1 问题提出因为内存断点是调试器的一个难点,所以我们这里放在最前面讲,这样也可以避免在后面的设计中一些组合问题的产生。
一个内存分页可能会存在多个断点，一个断点可能会跨多个内存分页。某个内存分页可能不具有用户要设的断点属性。某内存分页具有读与写的权限，但是用户只下了写的断点，如果将读的权限也一起拿掉，程序在读那块内存分页也要断下来，这样将大大的降低程序的效率，如何优化，以及断点信息与内存信息的存储。
2.2 问题的解决2.2.1 内断断点与内存分页的关系一个内存分页可能会存在多个断点，一个断点可能会跨多个内存分页。这个不由的让我们想起第一阶段的学生管理系统(一个学生可以选任意门课程，一门课程可能有任意个学生选)。其实二者的关系是一样的，因为是多对多的关系，所以我们要构造出第三张表来管理他们的关系。
为了检测用户下断点有效性等问题，在下断点的时候取得那个内页分页信息，判断地址是否有效，然后再判断是否具有要断下来的属性。对一个没有读属性的内存分页下读断点是无效的。
为了提高效率，中间表用了二个，一个是以内存页序号为主键，一个是以断点序号为主键，使用动态邻接表(长度自动增长)存储，这样可以提高程序的处理速度。当调试器收到异常信息，首先取得产生异常的地址，以及错误编码，再通过异常地址取得内存页的序号，再通过内存页的序号去邻接表里查他有多少个断点，如果当前有内存断点的话，恢复内存页原属性，然后再判断当前位置是否处于用户设的断点地址内，是的话，处理用户的请求，最后设单步，在单步中再将内存页的属性设成新的属性。
添加内存断点流程图如下所示：

处理异常流程图如下所示：

内存断点本来就是一件很耗资源的，为了最大的提升效率，当处理某内存分页具有读写的权限，而用户只下读或写的权限的这类情况，我们可以通过对原属性的分析，然后再减去用户新的属性，再根据结果生成新的属性,因为移除某个属性，并不能单单的通过去除某个位而完成。
相关记录项的结构：

内存页与断点关系表(邻接表)：

第三章 int3 断点与硬件断点3.1 问题的提出与解决3.1.1 问题提出如何实现软硬件断点？如何判断用户断点的正确性？如何提高效率？
3.2 问题的解决3.2.1 Int3断点的实现8086/8088 提供断点指令Int3 和单步标志TF，调试工具利用它们可以设置断点和实现单步。从 80386 开始，在片上集成了调试寄存器。利用这些调试寄存器不仅可以设置代码执行断点，而且还可以设置数据访问断点，不仅可以把断点设置在RAM 中，也可以把断点设置在ROM 中。
Int3 是Intel系列 CPU专门引入的用于表示中断的指令，对于Int3 断点,常见的做法是在用户要下断点的地方，将指令替换成CC，当调试程序运行到 CC 处,调试器将会收到EXCEPTION_BREAKPOINT消息，然后在这里将原CC处的代码还原及 EIP 减一再处理用户的请求。用 Int3 的好处很明显，可以设任意多个断点，缺点是改变了程序的原指令，容易被软件检测到，而且这里可能会遇到一个问题，当用户在某个内存分页设了一个不可读、不可写的断点，这时调试器是无法将CC 写进去的，也无法将原来的指令读出来。所以在设之前，我们先将目标内存页的属性设为可读可写的，设完之后再将内存页置为新的属性(移除了用户断点权限的新属性)，这个开销是非常大的。
本程序中，对于用户断点的正确性检测只做了如下判断，首先是判断用户的断点是否是处于有效的内存分页内，然后再判断是否重复,同一个内存地址，只能设一个断点，而对于Int3 断点和硬件执行断点并没有判断是否处于指令起始处。
当初的设想是被调试程序跑起来的时候,将被调试程序的指令全部解析一下，然后取得每条指令的正确起始位置，添加到树中，然后用户在下 Int3 断点的时候，再判断一下下的断点是否处于指令的首地址处。后来请教了一下老师以及查看windbg 等同类软件，发现也没有做这类的检测，同时分析觉得此弊大于利，所以放弃了这种做法，程序中并没有检测。
3.2.2 硬件断点的实现 80386和80486都支持6个调试寄存器，如图：

他们分别是 DR0、DR1、DR2、DR3，调试状态寄存器 DR6 和调试控制寄存器DR7。这些断点寄存器都是32位寄存器。
Dr0~3 用于设置硬件断点的线性地址，也就是断点位置，产生的异常是STATUS_SINGLE_STEP 。这些寄存器长 32 位，与 32 位线性地址长度相符，处理器硬件把执行指令所涉及的线性地址和断点地址寄存内的线性地址进行比较，判断执行指令是否触及断点。与 Int3 不同的是，硬件断点不仅可以设置在RAM 中，也可以设置在ROM 中，且速度比Int3 更快。
Dr7 是一些控制位，用于控制断点的方式。其中有四个GiLi，分别对应四个断点，Gi、Li控制DRi所指示的断点i在断点条件满足是，是否引起异常。
Gi 和 Li 分别称为全局断点允许位和局部断点允许位。在任务切换时，处理器清各 Li 位，所以 Li 位只支持一个任务范围内的断点，任务切换并不影响 Gi位，所以Gi支持系统内各任务的断点。
R/Wi分别对应四个DRi，R/Wi字段指示DRi断点信息的类型。每一个R/W占两位，所表示的类型为：

LENi字段指示DRi断点信息的长度，每一个LENi占两位。所表示的长度如下：

注意: 指令执行断点的断点长度必须为 1 字节，数据访问的断点长度可以是 1、2、4 字节。
Dr6 用于显示是哪些引起断点的原因，如果是 Dr0～3 或单步（EFLAGS 的TF）的话，则相应设置对应的位。
Bi表示由DRi所指示的断点引起的调试陷阱。
对于 DR7 的设置，原本程序中是使用位移来完成的，但是调试的时候非常之不方便，所以后来改用结构体了。结构体的定义如下：

3.2.3 对于int3断点的优化当设int3 断点的时候，判断一下当前调试寄存器有没有空闲的，有的话则优先使用调试寄存器，因为 int3 断点涉及内存分页属性，读目标进程内存，写目标进程，而硬件断点只需设调试寄存器，这样可以大大的提高效率。
第四章 函数名的解析4.1 问题的提出与分析4.1.1 问题的分析最初对于这个问题处理的想法就是分析被调试程序的导入表，后来和同学讨论，发现这样不能解决问题，因为 API 里可能还调用了别的 API，再跟进 API的话，程序就不能正确解析函数名了！
据说Windows有上万个API，如何组织这些数据，如果提高查询的效率、以及最大化的合理使用空间。
4.2 问题的解决4.2.1 函数名与函数地址的组织用一个链表用来存储已经加载的 DLL的名字已及当前状态。为了提高查询的效率，同时记录DLL名字的CRC值，当查找时，算出要查找的DLL名的CRC值，再直接查找通过CRC值查找，当 CRC值相同时，再用字符串比较是否完全相等，当加载DLL比较多的时候，或者经常要查询的话，这样可以大大的提升的效率。
同时用红黑树记录函数名地址(函数名在被调试进程里面的地址)以及函数的绝对地址(基址加偏移后的真实地址)。
红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。
4.2.2 函数名的显示在我的设计中，使用的是 OD的反汇编引擎，结构体中有记录命令的类型，首先判断他是不是call、jmp 这类的指令，然后再根据相应的值，找出API的地址，再判断目标地址是否是 API 函数的地址，是的话则从本地加载 DLL 链表中取得DLL名字，然后再通过函数名地址去调试进程中取得函数名(在程序中，并没有申请空间保存函数名，因为导出函数可能非常之多，不停的申请空间，然后字符串拷备，这个开销是非常之大的，所以在程序中我们只记录函数名在调试进程中的地址，同时 dll 名链表中有个状态值，当状态值为真时，表明那个 dll 当前已经加载，这样可以直接去内存拿函数名)。而对于call ebp 之类的指令，而需要在运行时才解析，因为在没有执行到那条语句的时候，寄存器的值是不确定的。
效果如下：

第五章 指令记录5.1 问题的提出与分析5.1.1 问题的分析当初听到这个的时候，觉得无从下手，而且也想到了很多极端的问题，比如运行的时候不停的修改原来的指令来达到往下运行的效果。然后进到 API 里面去了，那个记录量是非常之大的，而且当时 A1Pass 的测试结果是每秒只能跑 7 条指令。于是花了很多时间在想着效率提升这块，后来和同学讨论一下，他叫我学习一下OD的这个功能。
5.2 问题的解决5.2.1 数据的组织因为可能记录的数据量非常之大，所以要采用一种合理的数据结构，比如用户可以按指令跑的顺序记下来，也可以按地址的高低来记录，程序在运行中，可能某个地址的指令要跑很多次，但是我们不能重复记录很多次，所以这需要一种特定的数据结构，在程序中，我使用的是带头尾指针的链表与红黑树的结合，首先是将指令加到链表尾部,然后再插到红黑树里面去，这样查找起来的话，速度非常快的(因为我们每跑一条指令，都要先判断一下树中有没有，没有的话才插到树中去)，而且体积只是比单单的红黑树多一个指针域。

结合后的数据结构：这样就可以把链表与树的优点结合起来了，而补了链表的查找效率的不足。

5.2.2 指令记录实现在第一个解决方案中，采用的是置单步记录，但是经过测试这个效率不高，而且处理起来也很复杂，比如对于每个 call 之类的指令，判断是不是调用 API 之类的，而且经常会出现一些小问题，兼容性也不太好。
在第二个解决方案中，采用的是内存断点的方法，这个实现起来方便快捷，也不用判断是不是调用API,而且可以指定要记录的部分，不过内存断点的开销还是挺大的。
5.2.3 效率的优化假定计算机访问寄存器需要花费一个单位时间片，访问 cache可能要花费几个单位时间片，或许现代计算机已经可以像访问寄存器那样高速了，但是访问内存却要花费一百多的单位时间，则访问磁盘则更慢了。
为了充分的利用计算机时间，让写入磁盘与处理同时进行，在树节点中，我们直接记录指令的十六进制的值，而不直接记录反汇编结果，这样最大的节省空间，如果对于调用 API 的话，在节点 JmpConst 中记录，如果没有的话，这个值为零。然后在写入磁盘的时间，调用反汇编引擎将 Dump 的内容解析出来，如果JmpConst有值的话，再转成相应的DLL名和函数名。这样就可以并发处理了，从而充分的利用了CPU的时间以及节省了内存空间。
结点内存图：

第六章 反反调试6.1 问题的提出与分析一些恶意软件常常使用一些反调技手段用以阻碍对其进行逆向工程。反调试技术是一种常见的反检测技术，因为恶意软件总是企图监视自己的代码以检测是否自己正在被调试。为做到这一点，恶意软件可以检查自己代码是否被设置了断点，或者直接通过系统调用来检测调试器。
虽然在本设计中还没有来得及添加这些功能，但是想通过本章的内容，达到一个抛砖引玉的目的。
下面介绍二种常见的反调试方法：

检测CC 断点
检测调试器

6.2 问题的解决对于检测断点的反调试方法，我们可以动态的生成断点，比如 CC 断点，CD断点等等，然后在处理函数做相应的处理就可以了。
检测调试器的存在，一般是使用 IsDebuggerPresent 函数，跟进 API 我们发现他的实现很简单。
7C8130A3 > 64:A1 18000000 MOV EAX,DWORD PTR FS:[18] 7C8130A9 8B40 30 MOV EAX,DWORD PTR DS:[EAX+30] 7C8130AC 0FB640 02 MOVZX EAX,BYTE PTR DS:[EAX+2] 7C8130B0 C3 RETN
FS 指向的当前活动线程的 TEB 结构，TEB 的第一个结构是 TIB，TIB 偏移0x18 处是一个回指指针，指向自身，这里虽然是指向自身，但是我觉得这可能是微软以后为了扩展功能用的，而且从相关的代码中也可以看出来，他们都是先在TEB 偏0x18 处取值，然后再做相关的操作。 之后再取得PEB 的地址。
通过Windbg 我们可以到PEB 的结构信息：
0:000> dt _PEB 0x7ffde000 ntdll!_PEB +0x000 InheritedAddressSpace : 0 '' +0x001 ReadImageFileExecOptions : 0 '' +0x002 BeingDebugged : 0x1 '' +0x003 SpareBool : 0 '' +0x004 Mutant : 0xffffffff +0x008 ImageBaseAddress : 0x01000000 +0x00c Ldr : 0x00181ea0 _PEB_LDR_DATA +0x010 ProcessParameters : 0x00020000 _RTL_USER_PROCESS_PARAMETERS ………………
这样我们就可以看到，IsDebuggerPresent 只是简单的通过判断 PEB 结构的BeingDebugged 值来判断是否被调试器加载。
这样很简单的反反调试就出来了，我们只需将 PEB 结构的BeingDebugged的值改成0 就可以了。
__asm { mov eax, fs:[0x18] mov eax, [eax + 0x30] mov byte ptr [eax+2], 0 }
只要将这段代码写到目标进程里跑一下就可以了。当然，更好的话当然是自己实现CreateProcess这类函数。
结束语本系统的功能基本实现，因为个人努力不够的关系，很多地方不尽人意，系统原定的很多功能也被减去了，对于部分反调试功能等等，这个将作为后期的开发计划。

一、聊天机器人基本原理
语料库中的pattern是模式的意思，可理解为问题，而相应的template可理解为回答（而这一对问答被包裹在了category标签里面）。假如你的语料库像上面的xml文件这样简单，那么当你输入“你是谁”，机器人就会在内存中去一个一个的匹配pattern,最后匹配到了，就会回答“我是小龙”，而你输入其他任何语句，机器人就无从匹配了，程序会出现匹配不到的错误。那么怎样避免程序出错呢？我们修改语料库如下：

上图中的*，是AIML中的通配符，它匹配任何你输入的语句。当你输入的语句成功匹配，那么返回相应的template后，就不会再去匹配其他的category了。假如程序没有任何相匹配的，那么*总是可以匹配你的输入，机器人会输出“对不起，主人还没有教我怎么回答这个问题呢
当然AIML解析器所支持的xml标签种类远不止这些，上述是最基本的。AIML所支持的标签种类目测有20种。
二、为什么AIML解析器不支持中文国外的一款做的很好的聊天机器人（通过了图灵测试），她叫“Alice”(你可以用英文和Alice聊天）,它内部有很庞大的语料库，几乎所有用户可能说的话，语料库中都有，而且它用的就是AIML解析器。然而AIML程序中有一些地方会用正则表达式将除了英文字母和数字外的其他字符全部用空格替代，这就是Aiml解析器不支持中文的重要原因，这种正则表达式出现在bitoflife.chatterbean.text.Transformations 类中，比如下面这个函数：


其中fitting为：

上面的normalization函数是用来对用户输入做规范化处理的，它做了一下工作：

在原始输入的内容两头加空格
把句子中间的任何2个以上连续的空白字符都替换成一个空格
并对input进行字符过滤

修改完正则表达式之后，算是成功了一半，那还需要做怎么处理呢？
我们知道AIML当初仅仅是针对English语言开发的，而English单词之间都是有空格的，所以在前期载入语料库阶段，解析器默认xml语料库中的词之间都有空格，然后通过空格将句子分成一个个单词，最后在内存构建一个匹配树，而且在处理用户输入的句子时也是将其进行了规范化处理，如下代码：

而为了让它支持中文，一个比较直观的方法是在对用户输入做规范化处理的时候，我们将输入的中文句子中加入空格，比如上述代码的chineseTranslate函数：

同理，在载入语料库的时候，同样需要写一个类似的函数，功能就是将语料库中的字之间加上空格。
三、关于标签的支持与使用Aiml标签使用的官方文档
http://www.alicebot.org/TR/2005/WD-aiml
http://www.pandorabots.com/botmaster/en/tutorial?ch=4
根据上面的连接我们可以初步了解各种标签的作用和用法。k
然而，就我现在的中文聊天机器人，有些标签还不能正常使用，这是需要改进的地方。
下面是一些我尝试过的一些标签用法：
最基本：
<category><pattern>你好</pattern> <template>呵呵</template></category>
每一个问题和回答都被包裹在<category>标签中
随机返回功能：
<category> <pattern>你好</pattern> (或者在后面加一个*) <template> <random> <li>你好呀！</li> <li>嘿嘿</li> <li>我很好，你呢？</li> </random> </template></category><li>是library的意思，不是list
当你输入“你好”的时候，机器人会从random里面随机取出一句回答你。不过默认的都是先取第一句回答。
输入重定向功能（<srai>）：
<category> <pattern>你好</pattern> <template> <random> <li>你好呀！</li> <li>嘿嘿</li> <li>我很好，你呢？</li> </random> </template></category><category> <pattern>HELLO</pattern> <template><srai>你好</srai></template> </category>
输入“hello”的时候，会匹配到第二个category，而srai标签的功能是，将“你好”当成用户的输入，并重新到语料库里去匹配，最后就匹配到了第一个category。换句话说，用户输入“hello”和输入“你好”的效果是一样的。但是在使用srai标签的时候有可能会形成死循环，所以请慎重。
另外需要注意的是，如果你想要在语料库里面写英文的语料库，那么英文单词都要是大写的，而用户输入的英文可以不用大写。如果你觉得用大写很不爽，那么你可以去修改源代码。
*，<think>,<set>,<get>,<star>的使用:
<category> <pattern>我叫*</pattern> <template> <think> <set name="myname"><star/></set> </think>hello, <get name="myname"/>.</template></category>
测试结果为：

you say>
我叫小龙
Alice>hello, 小龙.

标签解释：
set和get里面的myname相当与参数名，首先在set标签中给myname赋值，然后用get标签得到相应参数的值，如果myname之前没有被赋值，那么就是空字符串。<star/>指的是pattern标签中*所匹配的内容。它还能指定index，举个例子：
<pattern>我叫*呵呵*</pattern> <template> <think> <set name="myname"><star index=”2”/></set> </think>hello, <get name="myname"/>.</template>
那么这时star标签就会被pattern中第2个*号所匹配的内容替代。而<star/>其实相当与<star index=”1”/> <think>标签可以理解为机器人在思考，它只会在“脑子”里默默的记住一些事情，或者完成一些不会被用户看到的工作。
Condition标签使用：
<category> <pattern>我叫*</pattern> <template> <think> <set name="myname"><star/></set> </think>hello, <get name="myname"/>.</template></category><category> <pattern>你好*</pattern> <template> 你好啊！ <condition name="myname" value="jack">怎么又是你？</condition> </template></category>
测试结果：

you say>
我叫jack
Alice>hello, jack.
you say>
你好啊
Alice>你好啊！ 怎么又是你？
you say>
我叫job
Alice>hello, job.
you say>
你好啊
Alice>你好啊！

标签解释：
<condition>标签中的myname是在set中被赋值的。然后在匹配到“你好*”后，就要判断是不是“jack”
input标签的用法：
<category> <pattern>我叫*</pattern> <template> <think><set name="name"><star/></set></think> 你好啊，<get name="name"/> </template></category><category> <pattern>嘿嘿</pattern> <template> 你刚才说：“<input index="2"/>”？ </template></category>
测试结果：

you say>
我叫jack
Alice>你好啊，jack
you say>
嘿嘿
Alice>你刚才说：“我 叫 jack”？

标签解释：
<input>标签指的是用户之前的输入，加上一个index，那就是说，用户倒数第几句输入，注意是“倒数”！index=”1”,就是用户倒数第一句输入的内容，以此类推，当然index是会出现越界错误的。
date标签的使用：
<category> <pattern>现在什么时间*</pattern> <template><date format="h:mm a"/>.</template></category>
测试结果：

you say>
现在什么时间啊
Alice>It is 9:49 下午.

Date标签将获得当前的系统时间
<that>元素表示先前机器人说的话，例如：
<category> <pattern>聊什么好呢*</pattern> <template>一起聊聊电影好吗？</template></category><category> <pattern>好</pattern> <that>一起聊聊电影好吗？</that> <template>那你喜欢什么电影呢？</template></category><category> <pattern>不好</pattern> <that>一起聊聊电影好吗？</that> <template>那我也不知道聊什么了~</template></category>
测试结果：

you say>
聊什么好呢？
Alice>一起聊聊电影好吗？
you say>
好
Alice>那你喜欢什么电影呢？
you say>
聊什么好呢
Alice>一起聊聊电影好吗？
you say>
不好
Alice>那我也不知道聊什么了~

这个标签还能取前面任意机器人说的话，不过不太熟…没有试验过
如果要取前面的前面机器人的话，可以用：<that index=”nx,ny”>,例如：<that index=”2,1”表示取机器人倒数第2句的话，<that index=”2,1”>也等于<justbeforethat/>
<thatstar>标签：
<category> <pattern>你好</pattern> <template>计算机的型号是什么</template> </category> <category> <pattern>*</pattern> <that>*的型号是什么</that> <template><star/> --》》这里的star标签匹配的是pattern中的*，但是奇怪的，如果把index改成2以后，却也不会出错。 这个型号是 <thatstar/> 里面 <random> <li>很好的商品</li> <li>很流行的商品</li> <li>很华丽的商品</li> </random>。 </template> </category>
测试结果：

you say>
你好
Alice>计算机的型号是什么
you say>
d
Alice>d 这个型号是 里面 很好的商品。

thatstar是匹配pattern-side that标签里面的*号的，但是这里没匹配到。
我想这里也还需要修改源代码。
set标签也有问题。
<category> <pattern>他做到了</pattern> <template>谁 ？</template></category><category> <pattern>*</pattern> <that>谁 *</that> <template> Oh, why do you think <set name="他"><star/></set> did that? I wouldn't expect that kind of behavior from <get name="他"/>. </template></category><category> <pattern>*</pattern> <template>啊哦~</template></category>
测试结果：

you say>
他做到了
Alice>谁？
you say>
小龙
Alice>Oh, why do you think did that? I wouldn’t expect that kind of behavior from .

假如这样写：<set name="he"><star/>
那么测试结果为：

you say>
他做到了
Alice>谁 ？
you say>
jack
Alice>Oh, why do you think jack did that? I wouldn’t expect that kind of behavior from jack.

也就是说这个标签不支持中文。还是需要修改源代码。
template-side input有问题：
<aiml:input index = (single-integer-index | comma-separated-integer-pair) /><category><pattern>HELLO</pattern><template>吃饭了吗？</template></category><category><pattern>吃了</pattern><template>我也吃了</template></category><category> <pattern>你好</pattern> <template>计算机 的 型 号 是 什 么</template> </category> <category><pattern>*</pattern><that>* 的 型 号 是 什 么</that><template><input index="4,1"></input> 《《----</template> </category>
测试结果：

you say>
hello
Alice>吃饭了吗？
you say>
吃了
Alice>我也吃了
you say>
你好
Alice>计算机的型号是什么
you say>
345
Alice>hello

Input标签中的index貌似当第一个参数是几，就返回倒数第几个用户的说的话，而第二个参数好像只能是1,其他的就会出现数组越界的错误。不知道为什么？
上面描述的标签部分还有问题，需要改进。
另外我想说的是，在写xml语料库的时候，一定要写一点，马上重启程序测试一次，看新加的预料是否工作正常，否则你写了一堆的预料后在去测试如果出错的话，就很难跟踪到错误的地方了。
四、项目结构总览
五、将数据库集成到聊天机器人中5.1 为什么需要使用数据库Xml文件是AIML所支持的预料载体，而且凭借AIML提供的各种丰富的标签，作者可以设计并编写出很人性化的语料库。显然，通过这种方式写语料库的特点是灵活性很好，能很容易写出“唠嗑”类型的聊天内容。然而，当时对这个项目的定位是客服机器人，也就是说，语料库还应该包含具有业务针对的预料，这部分预料将随着业务的不同而不同。于是我想把这部分预料存储在数据库中形成动态的语料库（我把xml文件中的预料称为静态预料，也就是说这部分预料完善之后就不去频繁的修改），这样做的好处有一下几点：

客服不用去学习怎样写xml预料，降低门槛
可以避免xml中预料越来越凌乱，到最后难以管理
以后可以针对数据库在开发一个语料库管理系统，方便客服管理有业务针对的这部分预料

5.2 数据库的表是怎样设计的
字段解释：

Id:预料的编号，自动生成（identify）
Createtime:该条数据创建时间，该条数据产生时自动生成（触发器）
Lastmodifytime:最近更新时间，该条数据的可填写字段被更新时自动修改（触发器）
Question:具体问题，自己填写
Replay：具体回答，自己填写
Label:标签字段（词语之间用空格隔开），里面填写的词语是要能体现question字段主题的，可以理解为一种补充说明，例：question:书是什么？那么书应该是被讨论的主题，lebel就可以填写和书意义相近的词，比如课本，教科书，教材，book,有了这个字段可以从某种程度上增强匹配效果
Copyfield:拷贝字段，这个字段会在你填写完（或者更新）question,replay,label这3个字段后自动生成（触发器），其内容为上述3个字段的合体，期间用空格隔开。这个字段是要被索引的重点字段

在以上的描述中，也许你会对某些字段存在的必要性产生疑惑，没有关系，在下面的叙述中也许能解决你的问题。
5.3 数据库里面的预料怎样使用到机器人当中这就是基于lucene的处理。当程序启动的时候，程序会在载入xml语料库后,lucene就开始对数据库进行全量索引（这其实也是一种载入语料库行为），并在项目的根目录下产生相应的索引文件index以及时间戳文件（timesTamp.txt：该文件记录了当前索引行为发生的时间。将在增量索引时用到）。索引文件会在后面响应用户输入的时候用到。
下面是索引操作的代码（在com.job包）：



其中sql语句是这样的：

5.4 在机器人处于运行状态时修改了数据库的预料，怎样做到与客户端的同步这里将用到时间戳的概念。首先当机器人程序运行的时候，里面的一个timmer任务也会同时运行，这个任务做的工作是定期（比如每隔10秒），进行一次增量索引—-lucene中的概念。增量索引所针对的数据等同与这样一条sql语句所返回的数据，该sql语句满足的逻辑是：查找出数据库中所有Lastmodifytime字段值大于timesTamp.txt中记录的时间。那么这样，每次客服对数据库做的预料修改，都会在隔一段时间后同步到客户端。

六、机器人怎样响应用户的输入在没有引入数据库前，只要调用Aiml提供的聊天接口就能得到一个字符串返回了，但是现在加入了数据库，那么我的处理的思路是这样的：我在xml语料库里面的*通配符所对应的templete做了标记，如下图：

注意到上面的红点了吗？我在这个回答最前面加上了“#”的标记。逻辑如下：

代码如下：


七、聊天机器人学习功能实现其实之前在介绍Aiml标签的时候，有2个很重要的标签还没有介绍到，那就是\<system>和\<gossip>标签。
在我的xml语料库中有一个文件叫Study.xml，它的内容如下：

（ps:如果不懂这里面一些标签的功能，可以回顾之前的标签功能解释）
我们看看这样的测试结果是什么：

等重启聊天机器人程序的时候，问同样的问题：

这其中都做了哪些工作呢？下面解释：
system标签的工作原理我还不是很清楚，但是我们可以看一下AIML解析器对应的System.java里面的process方法干了什么：

这个函数我暂时解释不清楚，但我知道上面的语料库中system标签只是会被learn函数的返回值替代。
我重点介绍一下gossip标签的工作过程：
首先看AIML解析器中对应的gossip.java文件的process方法干了什么：

match参数其实已经封装了上述语料库中learn函数的返回值“你的主人帅吗:帅到爆棚”。而super.process(match)就是取出这个字符串。
然后我们在看print函数：

看起来像是在什么文件里面写入了什么内容，我们在看outputStream()函数：

上述代码中的path其实就是指的这个文件：

很显然，客户每一次对机器人“教学”的内容，都会被写入gossip.txt文件当中，而且在写操作时是append的（即不会把原来的覆盖掉）。而当每次重启机器人程序的时侯，GossipLoad.java类都会去读gossip.txt的内容，并构造一个gossip.xml文件将其写到预料库中.该类主要代码如下：

Load函数在加载xml语料库到内存之前调用。这是必须的，因为必须先通过load函数生成gossip.xml文件后，然后统一加载到内存中去。代码如下：

Gossip.xml中的内容如下：

八、聊天机器人存在的不足
数据库匹配做的不好，或者说匹配率低，而且还不是很准确
两种语料库的结合显的有点牵强
xml语料库的设计还是比较欠缺的，首先预料不够丰富，而且靠人工编写预料不是一个好办法

游戏介绍


上面分别是下一次要改变的方向，是上、左的时候，原始状态的不同情况；右、下类似
已移动后，不擦除原来的障碍物为第一出发点
走到这种状态，是有前提的，这点很重要，也是能处理好的根本原因；不会凭空，走到某种状态
符合行为规范

注意：关于同类坦克情况，禁止互相跨越的时候，和这个障碍物的判断，还有所不同，这个 判断，要完全按照9格处理，否则，会导致无法移动；
1 子弹和坦克数据结构
2 子弹组织成链表结构敌方坦克的移动和发射子弹，主要考虑在单线程下，如何判断——时间差。
另外，在控制坦克移动时，可以使用的逻辑，但是，也要注意下，按键去抖。

3 游戏设计子弹遇到边界或这敌方子弹，消失的时候，对应要free掉产生时的空间，同时，维持链表结 构不被破坏。
子弹遇到敌方坦克，敌方坦克消失，这个处理，可以在相遇的位置，设置一个不同的值；坦 克移动的时候，检查，它的值是不是包含这个，包含，证明自己被击中，就要销毁掉它的数 据结构，尤其注意子弹的销毁。
关于，存档，如果杀死了一个坦克，这时候保存，要注意消失的是哪个，因此，需要记录下 标；不过，后来，设计的时候，每死掉一个坦克，就会自动产生一个，因此，这个也算是一 个预留的接口吧。
单线程处理起来，有时候，会感觉到控制坦克时，有时候会很快，有时候，会比较慢，这也 体现出了一定的局限性。
另外，最为重要的一点，思想要灵活，各种语言的规范，规矩，互相之间，可以在遵循某些 情况的前提下，进行变通和引进。
记录至此；至于画图，等其他功能，和贪食蛇基本类似，可以拿来主义。
4 游戏演示

1 游戏介绍一笔画是图论中一个著名的问题，它起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题，也提出了一笔画定理，顺带解决了一笔画问题。用图论的术语来说，对于一个给定的连通图存在一条恰好包含所有线段并且没有重复的路径，这条路径就是「一笔画」。
寻找连通图这条路径的过程就是「一笔画」的游戏过程，如下：

2 游戏的实现「一笔画」的实现不复杂，笔者把实现过程分成两步：

底图绘制
交互绘制

「底图绘制」把连通图以「点线」的形式显示在画布上，是游戏最容易实现的部分；「交互绘制」是用户绘制解题路径的过程，这个过程会主要是处理点与点动态成线的逻辑。
2.1 底图绘制「一笔画」是多关卡的游戏模式，笔者决定把关卡（连通图）的定制以一个配置接口的形式对外暴露。对外暴露关卡接口需要有一套描述连通图形状的规范，而在笔者面前有两个选项：

点记法
线记法

举个连通图 ——— 五角星为例来说一下这两个选项。

点记法如下：
levels: [ // 当前关卡 { name: "五角星", coords: [ {x: Ax, y: Ay}, {x: Bx, y: By}, {x: Cx, y: Cy}, {x: Dx, y: Dy}, {x: Ex, y: Ey}, {x: Ax, y: Ay} ] } ...]
线记法如下：
levels: [ // 当前关卡 { name: "五角星", lines: [ {x1: Ax, y1: Ay, x2: Bx, y2: By}, {x1: Bx, y1: By, x2: Cx, y2: Cy}, {x1: Cx, y1: Cy, x2: Dx, y2: Dy}, {x1: Dx, y1: Dy, x2: Ex, y2: Ey}, {x1: Ex, y1: Ey, x2: Ax, y2: Ay} ] }]
「点记法」记录关卡通关的一个答案，即端点要按一定的顺序存放到数组 coords中，它是有序性的记录。「线记法」通过两点描述连通图的线段，它是无序的记录。「点记法」最大的优势是表现更简洁，但它必须记录一个通关答案，笔者只是关卡的搬运工不是关卡创造者，所以笔者最终选择了「线记法」。
2.2 交互绘制在画布上绘制路径，从视觉上说是「选择或连接连通图端点」的过程，这个过程需要解决2个问题：

手指下是否有端点
选中点到待选中点之间能否成线

收集连通图端点的坐标，再监听手指滑过的坐标可以知道「手指下是否有点」。以下伪代码是收集端点坐标：
// 端点坐标信息let coords = []; lines.forEach(({x1, y1, x2, y2}) => { // (x1, y1) 在 coords 数组不存在 if(!isExist(x1, y1)) coords.push([x1, y1]); // (x2, y2) 在 coords 数组不存在 if(!isExist(x2, y2)) coords.push([x2, y2]); });
以下伪代码是监听手指滑动：
easel.addEventListener("touchmove", e => { let x0 = e.targetTouches[0].pageX, y0 = e.targetTouches[0].pageY; // 端点半径 ------ 取连通图端点半径的2倍，提升移动端体验 let r = radius * 2; for(let [x, y] of coords){ if(Math.sqrt(Math.pow(x - x0, 2) + Math.pow(y - y0), 2) <= r){ // 手指下有端点，判断能否连线 if(canConnect(x, y)) { // todo } break; } } })
在未绘制任何线段或端点之前，手指滑过的任意端点都会被视作「一笔画」的起始点；在绘制了线段（或有选中点）后，手指滑过的端点能否与选中点串连成线段需要依据现有条件进行判断。

上图，点A与点B可连接成线段，而点A与点C不能连接。笔者把「可以与指定端点连接成线段的端点称作有效连接点」。连通图端点的有效连接点从连通图的线段中提取：
coords.forEach(coord => { // 有效连接点（坐标）挂载在端点坐标下 coord.validCoords = []; lines.forEach(({x1, y1, x2, y2}) => { // 坐标是当前线段的起点 if(coord.x === x1 && coord.y === y1) { coord.validCoords.push([x2, y2]); } // 坐标是当前线段的终点 else if(coord.x === x2 && coord.y === y2) { coord.validCoords.push([x1, y1]); } })})
但是，有效连接点只能判断两个点是否为底图的线段，这只是一个静态的参考，在实际的「交互绘制」中，会遇到以下情况：

如上图，AB已串连成线段，当前选中点B的有效连接点是 A 与 C。AB 已经连接成线，如果 BA 也串连成线段，那么线段就重复了，所以此时 BA 不能成线，只有 AC 才能成线。
对选中点而言，它的有效连接点有两种：

与选中点「成线的有效连接点」
与选中点「未成线的有效连接点」

其中「未成线的有效连接点」才能参与「交互绘制」，并且它是动态的。

回头本节内容开头提的两个问题「手指下是否有端点」 与 「选中点到待选中点之间能否成线」，其实可合并为一个问题：手指下是否存在「未成线的有效连接点」。只须把监听手指滑动遍历的数组由连通图所有的端点坐标 coords 替换为当前选中点的「未成线的有效连接点」即可。
3 自动识图笔者在录入关卡配置时，发现一个7条边以上的连通图很容易录错或录重线段。笔者在思考能否开发一个自动识别图形的插件，毕竟「一笔画」的图形是有规则的几何图形。

上面的关卡「底图」，一眼就可以识出三个颜色：

白底
端点颜色
线段颜色

并且这三种颜色在「底图」的面积大小顺序是：白底 > 线段颜色 > 端点颜色。底图的「采集色值表算法」很简单，如下伪代码：
let imageData = ctx.getImageData(); let data = imageData.data; // 色值表let clrs = new Map(); for(let i = 0, len = data.length; i < len; i += 4) { let [r, g, b, a] = [data[i], data[i + 1], data[i + 2], data[i + 3]]; let key = `rgba(${r}, ${g}, ${b}, ${a})`; let value = clrs.get(key) || {r, g, b, a, count: 0}; clrs.has(key) ? ++value.count : clrs.set(rgba, {r, g, b, a, count});}
对于连通图来说，只要把端点识别出来，连通图的轮廓也就出来了。
3.1 端点识别理论上，通过采集的「色值表」可以直接把端点的坐标识别出来。笔者设计的「端点识别算法」分以下2步：

按像素扫描底图直到遇到「端点颜色」的像素，进入第二步
从底图上清除端点并记录它的坐标，返回继续第一步

伪代码如下：
for(let i = 0, len = data.length; i < len; i += 4) { let [r, g, b, a] = [data[i], data[i + 1], data[i + 2], data[i + 3]]; // 当前像素颜色属于端点 if(isBelongVertex(r, g, b, a)) { // 在 data 中清空端点 vertex = clearVertex(i); // 记录端点信息 vertexes.push(vertext); }}
但是，上面的算法只能跑无损图。笔者在使用了一张手机截屏做测试的时候发现，收集到的「色值表」长度为 5000+ ！这直接导致端点和线段的色值无法直接获得。
经过分析，可以发现「色值表」里绝大多数色值都是相近的，也就是在原来的「采集色值表算法」的基础上添加一个近似颜色过滤即可以找出端点和线段的主色。伪代码实现如下：
let lineColor = vertexColor = {count: 0}; for(let clr of clrs) { // 与底色相近，跳过 if(isBelongBackground(clr)) continue; // 线段是数量第二多的颜色，端点是第三多的颜色 if(clr.count > lineColor.count) { [vertexColor, lineColor] = [lineColor, clr] }}
取到端点的主色后，再跑一次「端点识别算法」后居识别出 203 个端点！这是为什么呢？

上图是放大5倍后的底图局部，蓝色端点的周围和内部充斥着大量噪点（杂色块）。事实上在「端点识别」过程中，由于噪点的存在，把原本的端点被分解成十几个或数十个小端点了，以下是跑过「端点识别算法」后的底图：

通过上图，可以直观地得出一个结论：识别出来的小端点只在目标（大）端点上集中分布，并且大端点范围内的小端点叠加交错。
如果把叠加交错的小端点归并成一个大端点，那么这个大端点将十分接近目标端点。小端点的归并伪代码如下：
for(let i = 0, len = vertexes.length; i < len - 1; ++i) { let vertexA = vertexes[i]; if(vertextA === undefined) continue; // 注意这里 j = 0 而不是 j = i +1 for(let j = 0; j < len; ++j) { let vertexB = vertexes[j]; if(vertextB === undefined) continue; // 点A与点B有叠加，点B合并到点A并删除点B if(isCross(vertexA, vertexB)) { vertexA = merge(vertexA, vertexB); delete vertexA; } }}
加了小端点归并算法后，「端点识别」的准确度就上去了。经笔者本地测试已经可以 100% 识别有损的连通图了。
3.2 线段识别笔者分两个步骤完成「线段识别」：

给定的两个端点连接成线，并采集连线上N个「样本点」；
遍历样本点像素，如果像素色值不等于线段色值则表示这两个端点之间不存在线段

如何采集「样式点」是个问题，太密集会影响性能；太疏松精准度不能保证。
在笔者面前有两个选择：N 是常量；N 是变量。
假设 N === 5。局部提取「样式点」如下：

上图，会识别出三条线段：AB, BC 和 AC。而事实上，AC不能成线，它只是因为 AB 和 BC 视觉上共一线的结果。当然把 N 值向上提高可以解决这个问题，不过 N 作为常量的话，这个常量的取量需要靠经验来判断，果然放弃。
为了避免 AB 与 BC 同处一直线时 AC 被识别成线段，其实很简单 ——— 两个「样本点」的间隔小于或等于端点直径。
假设 N = S / (2 * R)，S 表示两点的距离，R 表示端点半径。局部提取「样式点」如下：

如上图，成功地绕过了 AC。「线段识别算法」的伪代码实现如下：
for(let i = 0, len = vertexes.length; i < len - 1; ++i) { let {x: x1, y: y1} = vertexes[i]; for(let j = i + 1; j < len; ++j) { let {x: x2, y: y2} = vertexes[j]; let S = Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2)); let N = S / (R * 2); let stepX = (x1 - x2) / N, stepY = (y1 - y2) / n; while(--N) { // 样本点不是线段色 if(!isBelongLine(x1 + N * stepX, y1 + N * stepY)) break; } // 样本点都合格 ---- 表示两点成线，保存 if(0 === N) lines.push({x1, y1, x2, y2}) }}
4 性能优化由于「自动识图」需要对图像的的像素点进行扫描，那么性能确实是个需要关注的问题。笔者设计的「自动识图算法」，在识别图像的过程中需要对图像的像素做两次扫描：「采集色值表」 与 「采集端点」。在扫描次数上其实很难降低了，但是对于一张 750 * 1334 的底图来说，「自动识图算法」需要遍历两次长度为 750 * 1334 * 4 = 4,002,000 的数组，压力还是会有的。笔者是从压缩被扫描数组的尺寸来提升性能的。
被扫描数组的尺寸怎么压缩？
笔者直接通过缩小画布的尺寸来达到缩小被扫描数组尺寸的。伪代码如下：
// 要压缩的倍数let resolution = 4; let [width, height] = [img.width / resolution >> 0, img.height / resolution >> 0];ctx.drawImage(img, 0, 0, width, height); let imageData = ctx.getImageData(), data = imageData;
把源图片缩小 4 倍后，得到的图片像素数组只有原来的 4^2 = 16倍，这在性能上是很大的提升。