应用于拟态Web服务器的相似度求解方法①

王 灿， 倪 明， 喻卫东， 黎 想

(华东计算技术研究所， 上海 201808)

国家互联网信息中心2016年12月报告显示， 中国网站总量达到475.4万个. 网站给人们生活提供多种便利， 同时也遭受越来越多的安全威胁， Web服务器作为网站承载平台， 已经成为了网络攻击中的主要目标.为应对越来越严峻的网络安全挑战， 我国独立自主提出了拟态防御技术[1]， 拟态防御技术使用动态调度策略切换等价异构执行体， 构造出动态异构冗余的拟态环境， 利用所构建环境的不确定性和非持续性切断网络攻击链.

拟态Web服务器[2]是拟态防御技术在网站系统中一个应用， 在拟态网站系统中， 对每个异构执行体输出结果合法性的判决是安全的前提， 表决器中的相似度求解算法则是表决器的核心内容.

目前现有拟态Web服务器的表决器中， 通过字符串编辑距离衡量异构执形体响应网页的相似度[3]. 但是拟态Web服务器的异构执行体在发挥防御能力的同时也一定程度上造成了不同平台响应的差异性， 其中很多差异并不会影响网页的输出效果， 却很大程度上干扰了响应网页之间相似性的判决结果. 本文采用改进简单树匹配算法计算异构执行体响应网页的相似度，并应用于拟态Web服务器的表决器中， 提高了表决器的效率和准确性.

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

字符串编辑距离是一种常用的字符串相似度指标.通过一些操作编辑一个字符串， 使其变成另外一个字符串， 编辑的最少次数即为衡量两个字符串的相似度[4]指标. 在网页相似性比较、网页相关性排序以及快速模糊匹配等方面有很多应用.

1.1 字符串编辑距离求解

编辑距离是指原字符串A经过插入、删除、替换三种编辑操作， 变成字符串B所需要的最少编辑次数.

设有2个字符串A和B:A=a1a2…am，B=b1b2…bm.式(1)构造了A与B的(m+1)×(n+1)阶匹配关系矩阵LD，矩阵的第1列是字符串A， 第1行是字符串B:

匹配关系矩阵中的元素被称为单元， 按如下方式计算:

匹配关系矩阵中元素dmn即为字符串A和B之间的编辑距离， 用ld表示.

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

字符串A和B的相似度可通过ld计算，ld越小，A和B越相似， 反之， 差异越大. 根据编辑距离求解A和B的相似度公式如下:

式中，ld为字符串A和B之间的编辑距离， |A|和|B|分别表示2个字符串的长度.Similar(A，B)值越大， 说明字符串A和B越相似.

异构Web服务器对于网页的请求响应存在差异性， 通常情况下这种差异并不会影响输出， 但是利用字符串编辑距离求解网页相似度时， 却会干扰相似度的计算结果. 而且网页作为一种结构化的内容[5，6]， 将网页转化成字符串利用编辑距离计算相似性时， 会跨越结构层级比较， 忽略网页原有结构信息， 可能计算结果相似， 但呈现的结果却有较大差异. 因此现有字符串编辑距离计算方法在拟态Web服务器系统应用中存在短板. 本文为适用拟态Web服务器的要求， 给出了对节点采用编辑距离比较相似性的改进简单树匹配计算方法.

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

针对拟态Web服务器中采用字符串编辑距离处理网页字符串计算量大， 忽略原有网页结构信息等问题， 本文将异构执行体响应网页转化成保留原结构信息的DOM树， 利用改进简单树匹配算法[7]计算异构执行体响应网页的相似度. DOM树的节点是响应网页部分内容， 为兼容异构执行体造成的差异性， 在比较DOM树的节点时， 计算节点间的编辑距离， 根据编辑距离与所设阈值的大小判定节点是否相似.

2.1 简单树匹配基本原理

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

步骤1. 若Sm和Tn最大匹配大于任意一个Sm和Ti(1≤i＜n)最大匹配， 那么MS，T是＜S1，S2，…，Sm-1＞和＜T1，T2， …，Tn-1＞之间的最大匹配加上Sm和Tn的最大匹配.

步骤 2. 否则，MS，T等于＜S1，S2， …，Sm-1＞和＜T1，T2，…，Tn＞之间的最大匹配或＜S1，S2， …，Sm＞和＜T1，T2，…，Tn-1＞之间的最大匹配相似.

2.2 节点相似度计算

拟态Web服务器异构执行体输出结果会存在一定差异， 计算待匹配节点的编辑距离， 根据编辑距离差异程度判断是否在可接受范围内. 网页DOM树节点内容的字串量不大， 采用改进字符串编辑距离方法计算对应节点的相似度， 方法如下:

式中，n1、n2 是 2 个节点内容字符串， |pref|、|stuff|是字符串n1、n2最长公共前缀长度和最长公共后缀长度；lcs是n1、n2 去掉|pref|、|stuff|后剩余部分n1’、n2’的最长公共子串的长度；ed为n1、n2去掉|pref|和|stuff|后的编辑距离.

如果Similar(n1，n2)＞K1， 则判为相似， 否则判为不同.

2.3 基本简单树匹配算法

对树S和T第一层进行递归匹配， 得到最大匹配，结果保存在W矩阵中， 根据矩阵W中的值计算矩阵M中的值. 算法如算法1.

算法1. 简单树匹配STM(S， T)输入: S， T输出: 匹配的节点数IF 树S和T的根节点不相似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

图2举例说明了基本简单树匹配算法执行过程.为求图1中树S和T的最大匹配， 首先进行第一层子树的匹配， 定义M1-17[5， 3]是树S和T第一层子树的最大匹配； 由W1-17计算得到M1-17； 矩阵W1-17中的W[i，j]表示S和T第一层第i个和第j个子树的最大匹配，继续对M递归计算W值.

执行图2运算流程， 可以求出两棵树的匹配节点个数. 显然， 图1中S、T两棵树有7个节点匹配.

图1 两颗DOM树

图2 部分节点匹配矩阵

2.4 相似度计算

拟态Web服务器网页防篡改应用中， 表决器根据异构执行体响应网页的相似度进行判决. DOM树T1和T2相似度定义[8]如下:

式中， |T1|、|T2|分别是两个树的节点数， STM(T1，T2)是树T1和T2的最大匹配值.similarity(T1，T2)值越大， 表示网页T1和T2越相似.

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

网站作为复杂信息系统， 漏洞无法避免. 常见Web服务系统包括Web服务器硬件漏洞、数据库漏洞、操作系统漏洞、网站源码漏洞等， 攻击者通常利用其中的一个或多个漏洞进行攻击.

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

拟态防御技术中动态异构冗余机制[9，10](Dynamic Heterogeneous Redundancy， DHR)使得攻击者无法建立稳定的攻击链接. 执行体的冗余使得即便某个执行体被攻击破坏， 也不会对系统的输出结果产生直接影响， 并且动态性保证了攻击结果无法重现， 大大降低了攻击者攻击成功的可能性.

拟态Web服务器借助动态异构冗余机制， 把Web服务系统部署在异构执行体上， 对输出结果的一致性进行择多判决后再输出， 实现抗攻击的目的.

图3是拟态Web服务系统架构图. 拟态Web服务系统由前端接入模块、Web服务器池和控制器三部分组成. 前端输入模块主要实现了输入代理和输出代理两个功能， 是用户访问的实际入口和实际出口. 输入代理根据特定分发机制将用户请求分发至Web服务器池中的执行体上， 输出代理也被称为表决器， 根据特定判决算法对来自不同执行体响应进行表决输出. 池中包含多样、异构、冗余的执行体， 对外界提供Web服务. 实际使用中， Web服务器池中只有一个执行体在线， 接收前端接入模块分发请求并做出回应； 池中其余执行体一直处于待机状态， 等待控制器模块的上线指令. 控制器模块根据系统异构性最大化策略调度池中的执行体， 降低了执行体的持续暴露时间和系统中存在一致性漏洞的可能性.

图3 拟态Web服务器架构图

图3中的管理中心模块主要起到监测作用， 检测系统中其他模块运行状态， 处理各个模块的正异常信息， 保证拟态Web服务器正常运行.

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

在拟态Web服务器的表决器中， 将响应网页解析成DOM树形式， 使DOM树除了包含网页展示的文本信息外[11，12]， 还包含动态脚本信息. 对处理后的网页 DOM树用改进简单树匹配方法求最大匹配， 计算相似度值.

计算两个网页的相似度值时， 采用递归方式对DOM树进行匹配， 求解树的待匹配节点的字符串计算编辑距离， 根据对应节点编辑距离的差异程度判断是否匹配. 统计出DOM树中节点匹配的个数.

在计算异构执行体Web服务器响应网页T1和T2的相似度之前， 将T1和T2作为普通字符串计算两者长度的比值， 并将计算结果与设置的阈值K2进行比较， 若比值大于K2， 则说明两个网页的差异较大， 直接判定为不同， 不予输出； 若比值小于等于阈值K2， 表决器利用特定相似度计算算法进行相似度判决， 计算出T1、T2的相似度值后与所设置的阈值K3进行比较. 若两个网页相似度大于等于K3， 则说明两个网页差异在允许的范围内， 可判定为合法响应， 予以输出； 若相似度小于K3， 则说明两个网页之间差异不在允许范围内，判定为非法响应， 不予输出. 表决器执行流程如图4所示.

图4 表决器处理流程图

4 实验结果分析

拟态Web服务器网页防篡改应用场景中， 计算效率和计算准确性是两个重要的评价指标. 本文中， 为验证本方法的可用性， 采用计算效率和计算准确性两个指标与现使用算法进行比较. 实验将中电集团某研究所的官方网站部署到拟态Web服务器上. 基于字符串编辑距离的计算方法是通过计算两个字符串的编辑距离判断相似性， 于是在现有经典算法中将响应网页看成一个字符串进行完全比较. 改进简单树匹配方法中，把响应网页所转换成的DOM树进行匹配. 首先， 分别对具有差异性的8对网页利用两种算法计算相同请求中异构执行体响应网页的相似度， 记录相似度值和计算所用时间.

实验中， 保存了Ubuntu和Centos两个虚拟机执行体Web服务器中有差异的8对网页， 在表决器中分别使用经典方法和改进简单树匹配方法计算每对网页之间的相似度值并分别记录耗时. 测试环境为CPU: E5 4 核； 内存: 8 GB； 操作系统: CentOS-7 64 位.

分别设计基于经典算法和本文算法的表决器， 对8对网页相似度进行计算. 图5和图6为得到的相似度计算结果. 图中结果显示， 两种算法所计算的正常网页的相似度的结果差异不明显， 改进的算法对网页差异容忍度比经典算法略高， 但是差异不大， 不会对比较结果造成明显影响.

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

表1中记录8对网页分别采用经典方法和本文改进简单树匹配算法计算相似度的耗时结果， 对比表中数据可以看出， 本文所用改进算法大幅降低了计算耗时， 原因是改进算法中， 仅对网页可展示部分以及部分脚本进行比较计算， 大大缩减了需要计算的字符串量.从表中还可以看出， 本文所用改进方法在计算网页的DOM树相似性时， 计算耗时与编辑距离和节点距离并不是线性关系. 其原因是， 改进的字符串匹配算法在比较网页的相似度时， 采用的是递归的方式遍历整棵DOM树， 网页被篡改的位置越靠近根节点， 所需计算时间越短， 差异地方越靠近叶节点， 所需时间越长. 实际应用场景中， DOM树叶节点对应着网页页面上重要性相对低的位置， 这些位置被篡改价值低， 通常这些位置不会发生篡改， 因此改进方法可以防范常规的网页篡改攻击.

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

表1 网页相似性计算时间

实验2， 在拟态防御系统中， 针对Centos虚拟机的在线Web服务器发起篡改网页攻击， 改变本实验中网页4的信息. 篡改形式包括更改官网标题、篡改官网超链接信息以及在网页上嵌入恶意脚本信息等. 分别利用改进简单树匹配方法和现有经典方法计算被篡改网页的相似度. 根据网页被篡改前后相似度的变化程度判断算法性能， 理论上， 变化幅度越明显， 越能反应网页被篡改的实际情况.

从图7中可看出， 网页被篡改后利用经典算法和改进简单树匹配方法所计算的相似度均出现一定程度下降. 但从图中曲线变化趋势来看， 针对前两种篡改手段， 改进简单树匹配算法在网页被篡改后有较明显的下降趋势， 在网页嵌入恶意脚本攻击情况下， 也保持了和现有经典方法相近的趋势. 实验结果表明， 在拟态Web服务器中， 与现使用方法相比， 本文所采用改进简单树匹配算法能够在一定程度适应异构执行体Web服务器自身差异的基础上， 提高了拟态防御系统中表决器对于网页相似度计算所要求的准确性和计算效率.

图7 篡改网页检测效果

5 结论与展望

针对拟态Web服务器的应用场景， 结合字符串编辑距离计算方法和简单树匹配算法， 本文设计了一种符合拟态Web服务器系统中表决器需求的改进简单树匹配算法， 并用其计算拟态Web服务器中异构执行体响应网页的相似度. 实验结果表明， 本文所使用的算法更适用于拟态Web服务器异构环境下的表决器判决场景， 在测试环境中提高了表决器的计算效率和准确性， 对于被篡改网页有明显检测效果. 今后将对插入脚本篡改攻击检测不明显、深层节点篡改检测效率优化等方面做进一步的研究.