﻿ 应用于拟态Web服务器的相似度求解方法
 计算机系统应用  2019, Vol. 28 Issue (1): 75-80 PDF

Similarity Calculation Method Applied to Mimic Web Server
WANG Can, NI Ming, YU Wei-Dong, LI Xiang
East China Institute of Computing Technology, Shanghai 201808, China
Foundation item: National Key Research and Development Program of China (2016YFB0800100)
Abstract: The voter in the mimic Web server calculates the similarity of the heterogeneous executor response webpage in order to judge whether the response is legal output and thus to prevent webpages tempering. At present, the voter treats entire Webpage as a string and uses the string edit distance to calculate the similarity of the webpages. In this way, it caused problems such as large amount of calculation, ignorance of the original structure information of the webpages, and so on. In this study, the improved simple tree matching method is used to calculate the similarity of the webpages by calculating the similarity of the DOM tree of the webpages. The matching degree of DOM tree node is determined by the editing distance of the node string. The proposed algorithm is applied to the mimic Web server to verify the webpage tamper. Compared with the existing algorithms, the algorithm used in this study not only adapts itself to the heterogeneous but also improves the efficiency and accuracy of the voter.
Key words: mimicry Web server     editing distance     simple tree matching     similarity     webpage tamper-proof     DOM tree

1 基于字符串编辑距离的相似度求解

1.1 字符串编辑距离求解

 ${\rm{L}}{{\rm{D}}_{(m{\rm{ + 1}}) \times (n{\rm{ + 1}})}}{\rm{ = }}\left\{ {{d_{ij}}} \right\}(0 \leqslant i \leqslant m, 0 \leqslant j \leqslant n)\;\;$ (1)

 {d_{ij}} = \left\{ \begin{aligned}& i, \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad {j = 0} \\& j, \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad {i = 0}\\& \min ({d_{i - 1, j - 1}}, {d_{i - 1, j}}, {d_{i, j - 1}}) + {a_{i, j}}, \quad {i, j = 0}\end{aligned}\right. (2)

1.2 基于LD的相似度计算公式

 $Similar(A, B) = 1 - \frac{{ld}}{{\max (\left| A \right|, \left| B \right|)}}$ (3)

2 基于改进简单树匹配的相似度求解

2.1 简单树匹配基本原理

ST为两棵树, ij分别为ST上的节点. 定义ST的匹配为映射M, 节点对(i, j)∈M, ij不是根节点. S=(RS, S1,…, Sm)和T=(RT, T1,…, Tn)是两棵DOM树, RSRT分别表示子树S和子树T的根节点, SiTj为第i个和第j个第1层子树. 根据编辑距离判断ST两棵树的对应节点是否匹配, 当RSRT匹配时, ST最大匹配为MS, T+1, MS, T是<S1, S2,…, Sm>和<T1, T2,…, Tn>最大匹配.MS, T由动态规划算法求出 , 步骤如下:

2.2 节点相似度计算

 $Similar(n1, n2) = 1 - \frac{{ed}}{{ed + lcs + \min \left( {\left| {pref} \right|, \left| {stuff} \right|} \right)}}$ (4)

2.3 基本简单树匹配算法

IF 树ST的根节点不相似

RETRUN 0

ELSE

m=树S第一层节点数

n=树T第一层节点数

Initialize M[i, 0]=0 (i=0,…, m)

M[0, j]=0 (j=0,…, n)

FOR i=1:m

FOR j=1:n

M[i, j] = max(M[i, j–1], M[i–1, j], M[i–1, j–1]+W[i, j]);

W[i, j]=STM(Si, Tj);

ENDFOR

ENDFOR

RETURN M[m, n]+1

END

 图 1 两颗DOM树

 图 2 部分节点匹配矩阵

2.4 相似度计算

 $similarity(T_1, T_2) = \frac{{STM(T_1, T_2)}}{{\left( {|T_1| + |T_2|} \right)/2}}$ (5)

3 拟态Web服务器防网页篡改应用

3.1 拟态Web服务系统基本模型

 图 3 拟态Web服务器架构图

3.2 求解方法在拟态Web服务器的应用

 图 4 表决器处理流程图

4 实验结果分析

 图 5 a网站相似度求解算法结果对比

 图 6 b网站相似度求解算法结果对比

 图 7 篡改网页检测效果

5 结论与展望

 [1] 邬江兴. 拟态计算与拟态安全防御的原意和愿景. 电信科学, 2014, 30(7): 2-7. DOI:10.3969/j.issn.1000-0801.2014.07.001 [2] 仝青, 张铮, 张为华, 等. 拟态防御Web服务器设计与实现. 软件学报, 2017, 28(4): 883-897. DOI:10.13328/j.cnki.jos.005192 [3] 马博林, 张铮, 刘健雄. 应用于动态异构web服务器的相似度求解方法. 计算机工程与设计, 2018, 39(1): 282-287. [4] 姜华, 韩安琪, 王美佳, 等. 基于改进编辑距离的字符串相似度求解算法. 计算机工程, 2014, 40(1): 222-227. DOI:10.3969/j.issn.1000-3428.2014.01.047 [5] 祁钰, 关毅, 吕新波, 等. 网页结构树相似度计算. 黑龙江大学自然科学学报, 2009, 26(5): 627-632. DOI:10.3969/j.issn.1001-7011.2009.05.012 [6] 张瑞雪. 基于DOM树的网页相似度研究与应用[硕士学位论文]. 大连: 大连理工大学, 2011. [7] 何昕, 谢志鹏. 基于简单树匹配算法的Web页面结构相似性度量. 第二十四届中国数据库学术会议论文集(研究报告篇). 海口, 中国. 2007. 1–6. [8] 陈秋. 移动互联网内容相似性研究[硕士学位论文]. 武汉: 华中科技大学, 2013. [9] 林森杰, 刘勤让, 王孝龙. 面向拟态防御系统的竞赛式仲裁模型. 计算机工程, 2018, 44(4): 193-198. [10] 斯雪明, 王伟, 曾俊杰, 等. 拟态防御基础理论研究综述. 中国工程科学, 2016, 18(6): 62-68. [11] 郑小昌. 基于可信度和语义相似度的网页信息甄选研究[硕士学位论文]. 南京: 南京理工大学, 2016. [12] 黄亮, 赵泽茂, 梁兴开. 基于编辑距离的Web数据挖掘. 计算机应用, 2012, 32(6): 1662-1665.