基于LCS的WEB站点指纹识别设计+文献综述(5)
( 3)Wpcap.dll 是高级系统无关库,也工作在用户级,它和应用程序编译在一起,并使用低级动态连接库Pack2et.dll 提供的服务,向应用程序提供完善的监听接口。WinPcap 通过这3 个模块提供了以下的各项功能:①捕获原始数据报,包括在共享网络上各主机发送/接收的以及相互之间交换的数据报;②在数据报发往应用程序之前,按照自定义的规则将某些特殊的数据报过滤掉;③在网络上发送原始的数据报;④收集网络通信过程中的统计信息。
图2.4 winpcap基本体系结构
2．3 LCS算法
LCS是Longest Common Subsequence的缩写，即最长公共子序列。有字母表Σ，令序列A= a1a2 . . . am ，序列 B = b1b2 . . . bn且m≤n。可以通过删除另一序列的某些符号而得到的任意序列被称作该源序列的一个子序列。A和B的一个公共子序列同时是A的子序列，也是B的子序列。一对序列可以有多种不同的LCS。此外，一个LCS也可能有许多不同的嵌入，即LCS的字符在两列序列中的位置相对一致。对于每个不同的LCS我们都可以找出能区别开的嵌入，例如，从一个LCS的起始位置开始，按某种规则将LCS中的字符尽可能小范围地匹配嵌入到两序列对应的位置。最长公共子序列（LCS）问题就是找到最大长度的一个公共子序列。
对于一般的LCS问题，都属于NP问题。当数列的量为一定的时，都可以采用动态规划法去解决。动态规划的一个计算最长公共子序列的方法如下，以两个序列 X、Y 为例子： 设有二文数组 f[i][j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度，则有：f[1][1]=same(1,1)，f[i][j]=max{f[i-1][j-1]+ same(i,j),f[i-1][j],f[i][j-1]}。 其中，same(a,b)当 X 的第 a 位与 Y 的第 b 位完全相同时为“1”，否则为“0”。此时，f[i][j]中最大的数便是 X 和 Y 的最长公共子序列的长度，依据该数组回溯，便可找出最长公共子序列。该算法的空间、时间复杂度均为O(n^2)，经过优化后，空间复杂度可为O(n)，时间复杂度为O(nlogn)。
3 系统设计与实现
3．1 系统体系结构
课题实现的总体思路是通过捕获HTTPS流量，继而分析网络数据包，预先已做多次测试得到一些主流网站的指纹即训练集，针对当次获得的数据建立指纹即测试集，利用LCS算法将测试集与训练集中的成员一一比对，从而找到指纹匹配最相似的站点，完成识别的功能。系统结构如图3.1所示。系统的主要功能模块是：
（1）通信流的捕获：通过代码实现基于winpcap的抓包程序，可以截获数据。
（2）数据解析：对截获数据的有效载荷分析从而进行前期指纹库的建立以及新生指纹。
（3）指纹分析：基于LCS算法的指纹匹配分析，推测出访问的站点。