摘要
为解决当前Tor网络拓扑研究中存在的难以快速分析其网络重要节点,进而难以发现薄弱环节和隐藏服务的问题,提出一种基于改进ELECTRE(elimination and choice translating reality)算法的Tor网络节点重要度评估方法。该方法将熵权法(the entropy weight method,EWM)与ELECTRE算法相结合,将节点参数矩阵规范化后加权,确定一致性矩阵和不一致性矩阵,得出聚合优势矩阵,对各个节点的重要度进行排序。采用全局网络效率、自然连通度和最大连通子图对Tor网络的抗毁性进行量化,通过删除节点后抗毁性的变化对节点重要度评估方法进行比较。实验结果表明:在删除15个节点后,基于本文方法的网络抗毁性下降了79.25%;与5种对比方法相比,网络抗毁性的下降比例分别高出0.31%、0.60%、0.68%、3.68%和0.98%,说明本文方法节点重要度评估准确度更高,并且简化了计算过程,避免了人为因素带来的评估偏差,提高了计算效率。所提方法能够准确定位Tor网络中的重要节点,反映节点在维持网络结构稳定性中的关键作用,有助于对目标节点进行追踪,发现潜在威胁,为Tor网络安全防护与脆弱性分析提供了有力支持。
Abstract
To address the challenge in current Tor network topology research of rapidly identifying critical nodes for detecting weak links and hidden services, this paper proposes a node importance evaluation method for the Tor network based on an improved ELECTRE (elimination and choice translating reality) algorithm. The proposed method integrates the entropy weight method (EWM) with the ELECTRE algorithm. After normalizing the node parameter matrix and applying entropy-based weights, the method constructs the concordance and discordance matrices, derives the aggregated dominance matrix, and ranks the nodes according to their importance. The global network efficiency, natural connectivity, and largest connected subgraph size are employed to quantify the network's invulnerability. Changes in these metrics after node removal are used to compare different node importance evaluation methods. Experimental results show that after removing 15 nodes, the network resilience of our method decreased by 79.25%; compared with the five comparison methods, the decrease in network resilience is 0.31%, 0.60%, 0.68%, 3.68%, and 0.98% higher, indicating that the method proposed in this paper has higher accuracy in node importance evaluation. Moreover, it simplifies the calculation process, avoids evaluation bias caused by human factors, and improves computational efficiency. Overall, the proposed method effectively identifies critical nodes in the Tor network, highlights their role in maintaining network structural stability, and provides strong support for threat detection, target node tracking, and vulnerability analysis in Tor network security.
Tor作为一种当前使用最为广泛的匿名网络,利用洋葱路由协议实现匿名通信[1],通过一组中继设备重定向流量,其中每个中继设备均会为转发的数据添加一层加密内容,进而实现身份匿名,规避网络监管,有效保护用户隐私。Tor还可以为功能不同的服务器提供匿名服务,避免其泄露任何位置信息。这些服务通过洋葱统一资源定位系统(onion uniform resource locator, Onion Url)标识,不与任何IP地址关联,只通过支持Tor的浏览器访问,实现双向匿名。
作为一种比较成熟的匿名网络,Tor网络实现了高度的匿名性。同时,许多不法分子借Tor网络躲避网络监管,从事非法活动[2],给网络的可管可控带来了极大威胁。为此,研究人员尝试在流量侧分析其通信行为和结构以洞察Tor网络上的承载行为。目前关于Tor网络的研究大体分为4类:1)评估其实际匿名水平,寻找Tor的漏洞和弱点,设计有效攻击,并提出可能的应对措施[3-5]。2)分析Tor隐藏服务的主题及其内容与受欢迎程度的关系,以了解Tor与非法活动的关联程度[6-7]。3)分析通信拓扑,从图论的角度展开研究,尝试总结Tor网络的结构性质特征[8-11],如网络的度分布、社团结构以及承载内容相关的分布与指标。4)根据Tor网络流量的各种特征,对其进行分类识别,从而找出隐藏的恶意代码和恶意流量,提升网络监管水平[12-14]。上述研究工作大多数集中在Tor网络的承载业务识别和匿名性能分析上,对其拓扑结构和各个节点重要性的研究十分有限,这将影响对Tor网络匿名性、隐藏服务等方面的深入研究。
鉴于此,本文提出一种基于改进ELECTRE算法[15]的Tor网络节点重要度评估方法,根据熵权法分配各属性权重,利用改进的ELECTRE算法筛选出重要度较高的节点,旨在弥补节点重要性方面工作的不足,方便科研人员更好地了解Tor网络的拓扑结构,辅助识别关键节点。
1 Tor网络拓扑研究现状
截至目前,针对Tor网络拓扑结构的研究已经取得许多成果。Zabihimayvan等[16]收集了1 766个不同洋葱域的7 782个页面数据,分析了页面的主题与网络,借此评估了英文Tor网页的内容。根据托管的信息和服务将域分为9类,发现其中某些域会有意将自身与Tor的其余部分分隔。与之类似,Takaaki等[17]通过ichidan搜索引擎和fresh onions网站收集了大量的洋葱域,将其分为6类,创建了有向图以研究每个实例的特征及其之间的关系。Ghosh等[18]利用另一种自动化工具探索Tor网络并分析其网站的内容,在此基础上,通过聚类Tor服务将内容进行分类。这些工作往往只是利用拓扑图辅助研究网页的内容和语义,没有分析Tor网络节点和拓扑结构。
De Domenico等[8]提取出了部分暗网拓扑的特征,并提出了一个Tor网络的生成模型以研究其弹性,但该模型是在自治系统(autonomous system)级别上考虑整个网络拓扑的。2017年,Bernaschi等[9]利用BUbiNG爬虫收集数据,并从页面级(page graph)、主机级(host graph)和服务级(service graph)3个层次对Tor的网络拓扑图进行了分析。研究中同时考虑了有向图与无向图,并结合语义分析方法探讨了其与网络拓扑特征之间的关系。然而,该研究主要聚焦于拓扑图自身的基本指标分析,如度分布、中心性以及连通分量等,尚未深入探讨其结构性质在网络安全或匿名性方面的具体影响。Alharbi等[10]对一个包含48 174个节点和103 526条边的Tor网络拓扑图进行了实证研究。结果表明,节点的入度服从幂律分布,并与网页排名及特征向量中心性高度相关,而出度则不符合幂律分布。此外,类似于传统互联网的拓扑结构,Tor网络同样表现出小世界性和无标度性特征。Bernaschi等[11]进一步研究了Tor网络在动态波动环境下的拓扑结构演化,推测了网络中用户之间可能存在的交互模式。研究指出,Tor网络拓扑结构中包含一个规模较小的强连接子图,其在整体网络连通性中起核心作用。从该子图出发,仅需少数跳数即可抵达网络的其他区域,因此外围节点的波动对整体拓扑结构的影响较小。
在网络节点重要度研究方面,Lalou等[19]分类讨论了关键节点检测问题(critical node detection problem,CNDP),并对其若干变体的最新研究进展进行了分类综述,涵盖了理论复杂性分析、精确求解算法、近似方法及启发式策略等方面。该研究指出,CNDP可广泛应用于网络风险管理、脆弱性评估、社会网络分析及通信网络优化等多个领域。针对鲁棒性研究,很少考虑攻击代价和传统的度指标不能完全反映节点重要性的问题,Wang等[20]在综合航空货运网络的拓扑结构、行业特性与网络方向性的基础上,提出了一种基于topsis方法的节点重要性评估框架,用以更有效地衡量节点在面临攻击时的关键程度。此外,研究还构建了一个考虑攻击代价约束的最优攻击策略模型,该模型能够根据攻击预算以及防御方对关键节点关注程度的不同灵活调整攻击路径,从而提升攻击效率。Ruan等[21]提出了一种基于局部结构特征的关键节点识别方法,目的是识别在维持网络连通性方面具有关键作用的节点。该方法不仅考虑了节点本身的连接情况,还引入了其邻域结构的连通性特征。通过在多个真实网络上的仿真实验表明,该方法在识别关键节点方面优于若干传统启发式算法。上述研究主要集中在一般的复杂网络和现实世界的交通网络上,没有针对Tor网络研究其节点重要度。
综上所述,在关于Tor网络的研究中,目前主要的方向还是分析网络中的内容,针对拓扑图结构的研究仍不充分,且只是通过一些指标将其简单陈述,并没有深入探讨某个关键节点对网络的影响以及整个网络的抗毁性[22]。因此,本文将研究如何判断Tor网络拓扑中节点重要度、整个网络的抗毁性以及两者之间的关联。
2 本文方法
基于改进ELECTRE算法[15]的Tor网络节点重要度评估方法是将节点参数矩阵规范化后加权,根据加权规范化决策矩阵确定一致性矩阵和不一致性矩阵,再得出聚合优势矩阵,对各个节点的重要度进行排序。其节点重要度计算流程如图1所示。
图
1
节点重要度计算流程
Fig.
1
Process of node importance evaluation
2.1 节点重要度指标
节点重要度的计算大都利用几种经典识别算法或对算法加以改进得出,因此,从节点本身的重要性、相邻节点的重要性等维度综合考量,选取归一化度中心性[23]、网页排名[24]、特征向量中心性[25]和介数中心性[26]作为本文方法的4个指标,保证排序精度。
2.1.1 归一化度中心性
在无向图中,节点v的度中心性被定义为直接与该节点关联的边的条数,度中心性越大,该节点在网络中越重要,其计算式为
(1)
式中:Cd(vi)为节点vi的度中心性;N为所有节点的数量;aij反应了节点间的连接情况,若顶点vi和vj之间有边,则aij=1,反之则为0。
考虑到大规模网络度中心性差距较大的情况,需要对其进行归一化,计算式为
(2)
式中Cnd(vi)为节点vi的归一化度中心性。
2.1.2 网页排名
网页排名的工作原理是计算页面链接的数量与质量,以确定网站的重要性,计算式为
(3)
式中:Rp(pi)、Rp(pj)分别为页面pi、pj的网页排名;d为阻尼系数,取0.85;M(pi)为链入pi页面的集合;L(pj)为链出pj页面的数量。
由于网页排名的计算是通用的,适用于任何领域的图形或网络,所以将其作为计算节点重要度的一个指标。无向图中节点vi的网页排名为
(4)
2.1.3 特征向量中心性
特征向量中心性综合了节点自身的度以及其邻居节点的重要性,特征向量中心性高意味着该节点与许多本身特征向量中心性高的节点相连,具体计算式为
(5)
式中:Ce(vi)为节点vi的特征向量中心性,λ为邻接矩阵的最大特征值,fij为最大特征值λ对应的特征向量。
2.1.4 介数中心性
介数中心性是基于最短路径的中心性度量,每个节点的介数中心性即为这些最短路径穿过该节点的次数。介数中心性代表了节点彼此之间互动的程度,其越高意味着节点的控制能力越强,因为会有更多的信息流经该节点。介数中心性表达式为
(6)
式中:Cb(vi)为节点vi的介数中心性;σst为从节点s到节点t的所有最短路径的条数;σst(vi)为节点s到节点t的所有最短路径中,经过节点vi的路径条数。
2.2 改进的ELECTRE算法及其效率分析
改进的ELECTRE算法结合熵权法[27]计算每个节点的重要度,传统算法在得出一致性矩阵和不一致性矩阵后分别计算出阈值,将原矩阵的元素逐一与阈值比较后得出一致性、不一致性优势矩阵,在此基础上得出的聚合优势矩阵只包含0和1两个元素,随着节点的增多,精度会大幅下降。
传统ELECTRE算法和改进的ELECTRE算法区别如图2所示。改进的ELECTRE算法省略了计算阈值和生成一致性、不一致性优势矩阵两步,直接根据一致性矩阵和修正型不一致性矩阵计算聚合优势矩阵,提高精度的同时简化了计算。
图
2
改进的ELECTRE算法
Fig.
2
Improved ELECTRE algorithm
改进的ELECTRE算法步骤如下:
1)构建决策矩阵。通过可用信息构造m个节点和n项指标的决策矩阵A。
(7)
式中xmn为第m个节点在第n项指标下的度量。
2)构建规范化决策矩阵。将决策矩阵的条目转换为无量纲的可比较条目。规范化决策矩阵R及其第i行第j列元素\begin{equation}r_{ij}\end{equation}的计算式分别为:
(8)
(9)
式中xij、xkj分别为第i、k个节点在第j项指标下的度量。
3)根据熵权法计算每个指标的权重。首先,将决策矩阵A归一化后计算第j项指标下第i个节点占该指标的比重\begin{equation}ρ_{ij}\end{equation}。
(10)
其次,求第j项指标的熵值sj。
(11)
式中u为常数,通常为指标总数取对数后的倒数。
然后,计算第j项指标的差异系数dj。
(12)
最后,得到第j项指标的权重ωj。
(13)
4)构建加权规范化决策矩阵。将规范化决策矩阵R的每一列乘以对应指标的权重,得到加权规范化决策矩阵V。
(14)
其中
(15)
式中W为权重矩阵。
由于\begin{equation}\sum _{}\end{equation}\begin{equation}ω_{n}\end{equation}=1,则V可以表示为
(16)
5)确定一致性集和不一致性集。两个不同节点Ak和Al(m≥k,l≥1)的一致性集Ckl定义为Ak不劣于Al的所有元素的集合,即
(17)
式中:j=1,2,3,···,n;vkj、vlj分别为Ak、Al的第j个元素。
Ckl的补集Dkl为不一致性集,即Ak劣于Al的所有元素的集合。
(18)
6)构建一致性矩阵和不一致性矩阵。一致性矩阵C中元素的相对值通过一致性指数估计。一致性指数\begin{equation}c_{kl}\end{equation}是与一致性集中包含的指标相关联的权重之和,即
(19)
一致性矩阵C的表达式为
(20)
式中“-”表示矩阵中元素值缺失。
不一致性矩阵D表示节点\begin{equation}A_{k}\end{equation}弱于节点\begin{equation}A_{l}\end{equation}的程度。D及其元素dkl的表达式分别为:
(21)

(22)
7)确定修正型不一致性矩阵。修正型不一致性矩阵D′中的元素与一致性矩阵中的元素相同,其值越小代表节点越重要,表达式为
(23)
式中d′m3=1-dm3。
8)确定聚合优势矩阵。聚合优势矩阵Q中的元素由一致性矩阵和修正型不一致性矩阵对应位置的元素相乘得到,即
(24)
式中qm3=cm3d′m3。
9)计算每个节点的重要度。节点重要度即为聚合优势矩阵Q对应列所有元素之和。节点\begin{equation}v_{i}\end{equation}的重要度为
(25)
式中:Ino(vi)为节点vi的重要度,qij为聚合优势矩阵Q第i行第j列的元素。
对所有节点的重要度进行排序,其值越小代表节点越重要。
改进后的ELECTRE算法与传统ELECTRE算法虽然整体的时间复杂度均为O(m2),但传统算法确定阈值和构建一致性、不一致性优势矩阵时需要进行5次时间复杂度为O(m2)的计算,改进后的算法则只需进行1次时间复杂度为O(m2)的计算即可确定修正型不一致性矩阵,因此,改进后的算法在实际运算中效率更高。
3 实验与分析
3.1 实验环境与数据集
实验主机配置:操作系统为64位Windows 10,CPU为Intel Core i7-9700H@ 3.00 GHz,32 G内存,所有实验均在MATLABR2021B上完成。
采用数据集“22Feb2017.services.edges”验证所提节点重要度评估方法的有效性。该数据集使用一个带有种子列表的定制爬虫,通过从标准的Tor专属搜索引擎获得的Onion Url或者合并Tor wiki和链接目录上发布的Onion Url组合而成,从2017年1月1日至2017年2月22日运行53 d,得到一个共计12 832个节点和72 556条边的Tor网络拓扑。
3.2 评价指标与算法
采用网络抗毁性评价节点重要度算法的准确性。网络抗毁性即网络在面对各种不利因素或者攻击时,仍然能保持其功能性、稳定性和连通性的能力。本文采用网络效率[28]、自然连通度[29]和极大连通子图[30]的相对大小进行简化表征。节点的重要度越高,其对网络抗毁性的影响越显著;当该节点被移除时,网络抗毁性下降更为明显。
网络效率是衡量网络交换信息效率的指标。在全局范围内,其量化了整个网络的信息交换能力,局部效率则在小范围内量化了网络的抗故障能力。如果一个网络具有较高的局部效率,那么即使网络中的某个节点受到损坏或移除,其邻居节点之间依然可以快速、有效地传递信息。相较于局部效率,全局效率考虑了网络中所有节点对之间信息传递路径的效率,能够综合评估网络中信息传递的速率,从而很好地反映网络的整体连通性,更适合分析整个网络的性能和结构,因此,本文所述网络效率为全局效率。Tor网络的全局效率EG的表达式为
(26)
式中:dij为节点间最短路径的长度,H为网络中所有节点的集合。
自然连通度是一种基于图谱的复杂网络的鲁棒性度量,网络鲁棒性可以由顶点间路线的冗余来表示,存在的替代路线越多,顶点间的连通性越强。自然连通度反映网络中节点之间冗余路径的丰富程度,公式为
(27)
式中λi为邻接矩阵的第i个特征值。
极大连通子图在无向图中又称连通分量,是指网络图中节点数尽量最多、范围最大的一个子图,其值越大,网络的抗毁性越强。为了避免网络规模过大导致连通分量过大的问题,采用相对极大连通子图进行计算,其公式为
(28)
式中Crc为网络图的相对极大联通子图。
网络抗毁性I可以表示为
(29)
网络抗毁性计算算法的流程如图3所示。按照节点重要度由高至低的顺序依次删除节点及其相应的连接边,每删除一个节点,Tor网络的拓扑结构将发生变化,网络抗毁性也随之下降;计算每一次删除节点后的网络抗毁性,共计删除15个节点,实现对节点重要度算法的评价。
3.3 实验结果
为验证本文节点重要度评估方法的有效性,将其与EW-VIKOR[31]、Cnd[23]、Rp[24]、Ce[25]和Cb[26]5种方法在数据集“22Feb2017.services.edges”上分别进行15次实验,得出每种方法排名重要度前15的节点,其节点序号见表1。
图
3
网络抗毁性计算算法流程
Fig.
3
Process of network invulnerability evaluation algorithm
表
1
节点重要度排序
Tab.
1
Ranking of node importance
依次删除排名前15的节点,并分别记录每种方法网络抗毁性的变化,结果如图4所示。由图4可以看出:删除15个节点后,本文方法和其他5种方法的网络抗毁性分别下降为0.148、0.151、0.151、0.152、0.173和0.154;随着失效节点的增加,每种方法的网络抗毁性均逐渐下降,原因是失效节点可能会中断网络中的重要路径或通信链路,导致信息传输受阻或延迟,从而使得网络效率和自然联通度降低。
图
4
网络抗毁性变化曲线
Fig.
4
Variation curves of network invulnerability
删除15个节点后,每种方法网络抗毁性下降比例见表2。
表
2
6种方法网络抗毁性下降比例
Tab.
2
Percentage of network invulnerability reduction for six methods
由表2可以看出,本文方法在 “22Feb2017.services.edges” 数据集上删除15个节点后,网络抗毁性的下降比例达到了79.25%,相较于其他5种方法,分别高出了0.31%、0.60%、0.68%、3.68%和0.98%,说明本文方法能更有效地识别对网络影响较大的节点,在定位Tor网络关键节点方面具有更高的准确性,能够高效准确地完成节点重要度评估任务。
4 结论
1)本文提出的基于改进ELECTRE算法的Tor网络节点重要度评估方法可以很好地解决使用传统ELECTRE算法在面对大量备选方案时,计算聚合优势矩阵导致的各方案之间的差别不明显,难以判断优劣的问题;提高了节点排序结果的精度,且不需要计算阈值,简化了计算过程。
2)提出了一种网络抗毁性的新型简化算法,利用网络效率、自然连通度和极大连通子图实现了对节点重要度计算方法的准确评价。
3)在公开数据集上进行的对比实验得出,本文方法的网络抗毁性下降比例达到了79.25%;与对比方法相比,网络抗毁性的下降比例分别高出了0.31%、0.60%、0.68%、3.68%和0.98%,说明本文方法在判断节点重要度方面优于对比方法,准确性更高。

