论文研究-基于追踪部署的着色包标记算法的研究.pdf
需积分: 9 149 浏览量
2019-07-22
23:24:09
上传
评论
收藏 425KB PDF 举报
收 稿日期 : 2008-01-14; 修 回日期 : 2008-03-25 基 金项 目: 国 防基 础研究 基金 资助项 目( A1420061266)
作 者简介 : 刘渊( 1967- ) , 男 , 教授, 硕导 , 主 要研 究方向 为网 络安全 及网 络信息 系统; 陈 彦( 1984- ) , 男, 江苏 扬州 人, 硕士 , 主 要研究 方向 为网 络
安全( cy1984817@ 163. com) ; 李 秀珍( 1982- ) , 男 , 江苏徐 州人, 硕 士, 主要研 究方 向为网 络安 全.
基 于 追 踪 部 署 的 着 色 包 标 记 算 法 的 研 究
*
刘 渊, 陈 彦, 李秀珍
( 江南大 学 信息 工程 学院 , 江苏 无锡 214122)
摘 要: 基 于追 踪部 署的 相关 理论 和着 色包 标记算 法, 针 对 当前 危 害 很 大 的 分 布式 拒 绝 服 务 攻 击, 提 出 一 种 基
于追 踪部 署的 IP 回溯算法 。该 算法 是以 贪心 算法为 基 础, 利 用 K-剪枝 算 法 在网 络 拓 扑 图 中 找 出一 些 关 键 的 路
由器 , 利 用这 些路 由器 也就 是只 让 tracers 对过 往的 数据包 按 照 着色 包 标 记算 法 进 行标 记 , 这 样 不但 减 少 了 重 构
路径 所需 的数 据包数 , 降低 了路 径误报 率, 提 高了追 踪到 攻 击 者 的速 度 , 而 且 大 大减 轻 了 路 由 器 标 记 的负 担 , 从
而能 够迅 速准 确地找 到攻 击源 。
关键 词: 追 踪部 署; 分 布式 拒绝 服务 攻击 ; 贪心 算法 ; K-剪枝算法; 着色 包标记 算法
中图 分类 号: TP393 文 献标 志码: A 文 章编 号: 1001-3695( 2008) 10-3102-03
Research on coloring packetmarking algorithm based on tracers placement
LIU Yuan, CHENYan, LI Xiu-zhen
( College of Information Engineering, Jiangnan University, Wuxi Jiangsu 214122, China)
Abstract: Based on the theory of tracers placementand coloring packetmarking algorithm, thispaper proposedan IPtraceback
algorithm based on tracersplacement againstDDoS. The algorithmwas based on the greedy algorithmusing K-Diameter-Cutal-
gorithminthe network topology map to identifysome key routers. Using these routers also tracers to mark the packetsaccording
with coloring packetmarking algorithm not only could reduce the number of packetsneeded for path reconstruction and number
of false positives, speed the tracing to attacker but also greatly reduced the burdenon the router marker. Therefore, it can lo-
cate the attack origins rapidly and accurately.
Key words: tracers placement; distributed denial of service( DDoS) ; greedy algorithm; K-Diameter-Cut algorithm; coloring
packetmarking algorithm
拒绝服务攻击( DoS、DDoS) 已经成为 Internet 的严重威胁,
造成了极大的经济损失, 难 以防范。这 类攻击 实施简 单、攻 击
流量大、隐蔽性强。可利用的安全性低而资源丰富的网络主机
越来越 多, 因此, 如何 快速、有效地找出攻 击源, 并及时采用 相
应的防御措施,就成了 DDoS攻击防御研究中的关键课题。
1 相关工作
为了解决追踪攻击源的 问题, 提出了 很多方 案, 如 入口 过
滤( ingress filter)
[ 1, 2]
、输入 调试 ( input debugging)
[ 1,3]
、有限 洪
泛( controlled flooding)
[ 4]
、日 志记录 ( logging)
[ 5]
、ICMP 追踪 报
文( ICMP traceback message)
[ 6]
和 包 标 记 ( packetmarking)
[ 1,4]
等。但是包标记是目前最为有效的追踪方法, 它通过向包中添
加标记使其携带路径信息,因此具有许多其他方法所不具备的
优点。例如不需 要 ISP 的配 合, 避 免 了 调试 中 高 昂的 管 理开
销; 不会产生巨大的网络流量, 给网络路由器带来过大的负载,
而且还支持事后追踪等。最早由 Savage 等人
[ 1]
进 行了深入 研
究的概率包标记方案就是为了追踪攻击者或傀儡机而提出的。
Savage 方案的最大问题在于追 踪所需 数据包 数量 随攻 击路 径
长度急剧增 加。Wang 等人
[ 7]
提 出一 种追 踪 部署 策略 来 防 御
DDoS攻击, 解决了怎样在一 个网络 拓扑图 中部署 tracers 以 追
踪到攻击者, 但其中没有提到具体的包标记策略和重构路径的
收敛速度。 M. Muthuprasanna 等 人
[ 8]
提出 一 种 着色 包 标 记 算
法, 虽然减轻了路由器 标记数 据包 的负 担, 减少了重构 路径时
所需的数据包数, 能够比较有效地重构出攻击路径, 但是求出的
攻击路径的误报率仍比较高。本文借鉴 他们的思想, 利用各自
的优点, 提出了一种基于追踪部署的着色包标记算法, 通过模拟
路由环境下的实验, 取得了较好的效果。
2 网络模型和定义
网络模型可以抽象成无向图 G = ( V, E) 。其中: V 表示 点
的集合; E 表示边的集合。由( V
1
, V
2
) , ( V
2
, V
3
) , …, ( V
n- 1
, V
n
)
这些边构成一条路径。V
1
和 V
n
分别叫做起点和终点, V
1
到 V
n
的路径长度为 n - 1。在 G中如果任意两个节点 都存在一条 路
径, 就称此图是连通的。定义 G中 u 和 v两点的距离为图中存
在于 u 和 v 中所有 路径中 最短 的, 否则 记 d( u, v) = ∞。如 果
删除图中的一个点图不再连通, 那么这个点称为割点。割点集
就是使图不连通所要删除的最少 点数的 集合, 记为 k( G) 。 如
果一个点的集合能够 覆盖 图 G 中的 所有 边, 那 么就 称此 集 合
为 G的点覆盖。最少的 点覆盖 集合记 为 β( G) 。离心 率 e( v)
定义为图中离 v最长 的距 离。 半径 r( G) 为最 小的 离心 率, 直
径 d( G) 为最大的离心率。
3 Tracers 的部署算法
K-剪枝问题是 指在 图 G中 设 法找 到 最少 的节 点 数, 使 得
第 25 卷 第 10 期
2008 年 10 月
计 算 机 应 用 研 究
Application Research of Computers
Vol. 25 No. 10
Oct. 2008
资源评论
