WSS一个基于NS2的蠕虫模拟系统-中国科学院

WSS 一个基于 一个基于 NS2 的蠕虫模拟系统的蠕虫模拟系统 马铭 1 2 白硕1 1中国科学院计算技术研究所软件室 2中国科学院研究生院 北京 maming bai 摘摘 要要 网络蠕虫严重威胁着互联网的安全 然而由于其爆发所具有的突然性和大规模性 使得蠕虫研究面临巨大挑战 本文介绍了一个基于 NS2 的蠕虫模拟系统 WSS 该系统的建立主要分为三部分 首先通过处理 BGP 路由表信息来获 取模拟中用到的 Internet 抽象网络 然后以传染病学模型为基础对蠕虫传播进行建模 最后将两者在 NS2 中相结合实现对 蠕虫传播的模拟 实验证明 WSS 能够在实验室环境中获取同实际蠕虫爆发时类似的统计数据 在理解蠕虫的宏观行为 预测蠕虫的流量 传播速度及危害等方面有着广泛的应用前景 关键词关键词 蠕虫 模拟 Internet 抽象拓朴 传染病学模型 NS2 WSS a Novel Worm Simulation System Based on NS2 MA Ming1 2 BAI Shuo1 Software Division 1Institute of Computing Technology Chinese Academy of Sciences 2Graduate School of Chinese Academy of Sciences Beijing maming bai Abstract Internet worms have been a severe threat to the Internet infrastructure and hosts recently However the inherent suddenness and large scale of these phenomena pose significant challenges for research on it To facilitate the study of worms this article describes the design of a worm simulation system based on NS2 WSS which can be divided into three parts First acquire abstract Internet topology used for simulation by processing BGP routing data Second model the spread of worms based on the epidemiological model Finally integrate the previous two in NS2 to realize the simulation of worm propagation Experiment shows that WSS can obtain similar statistical data in a laboratory setup to those from actual worm explosion so that it has a comprehensive application prospect in better understanding of the behavior of worms prediction of their traffic and speed and harm evaluation etc Key words worm simulation Internet topology epidemiological model NS2 马铭 1978 男 硕士研究生 主要研究方向为网络安全 大规模网络模拟 白硕 1956 男 研究员 博士生导师 主要研究方向为网络与信息安全 计算语言学 1 1 引言引言 自从 1988 年 Morris 蠕虫问世以来 此起彼伏的 蠕虫攻击严重威胁着网络的安全 尤其近几年 Nimda CodeRed Blaster 等蠕虫的大规模爆发更是 感染了数以万计的主机 造成几亿甚至几十亿美元的 巨额经济损失 在这种形势下蠕虫检测 防御 建模 等等一系列研究纷纷展开 但这些研究一般都面临两 个问题 1 可供分析的蠕虫爆发数据稀少 由于 蠕虫爆发的突然性和大规模性 要想对其进行全面监 控非常困难 目前的蠕虫爆发数据大部分是在进行其 它网络实验时意外获得 其可靠性和完整性难以满足 统计分析的需要 2 没有合适的实验环境来验证研 究结果 如果我们使用若干台主机搭建实验网络来分 析蠕虫传播 则无法体现其在互联网上传播时的大规 模特性 若我们直接在 Internet 上释放蠕虫进行此类 实验则本身就是违法的 正是从这两点出发 我们开发了一个基于 NS2 8 的蠕虫模拟系统 WSS Worm Simulation System 该系统能够在实验室环境中真实重现大规模蠕虫爆发 时的景象 这在理解蠕虫的宏观行为 预测蠕虫的流 量 传播速度及危害方面有很大帮助 而且该系统还 能根据要求为蠕虫检测系统生成丰富的测试用例 更 为检测系统的开发提供了重大助力 模拟蠕虫传播的困难主要在于蠕虫是在整个互联 网上传播 需要模拟的是 Internet 这一包含数亿主机 的庞大系统 所以要进行蠕虫模拟 适当的抽象必不 可少 在 WSS 中 抽象分为两个方面 对 Internet 的 抽象及对蠕虫传播的建模 我们将 Internet 抽象成一 个由 AS 自治系统 构成的网络 并且引入了决定 域间路由的重要因素 AS 间商业关系 蠕虫传播 模型我们以传染病学模型 9 为基础进行适当修改后得 到 最后将抽象拓扑和传播模型在 NS2 上相结合以实 现蠕虫模拟 2 2 Internet 抽象拓扑的生成抽象拓扑的生成 为了将 Internet 抽象为一个由 AS 自治系统 构 成的网络 通常的方法是通过处理 BGP 路由表来获 取 AS 之间的邻接关系 以此建立一个由 AS 组成的 网络 然而使用上述方法建立的抽象网络仅包含 AS 之间的连接情况 遗漏了对域间路由有重要影响的 AS 间商业关系 2 2 1 1 AS 之间的商业关系之间的商业关系 互联网在其商业化后在规模和复杂性上都有了很 大程度的增长 Internet 连接着上万的 AS AS 内的 路由是由域内路由协议控制 如静态路由 OSPF IS IS 和 RIP 等 而 AS 之间的路由是由域间 路由协议来控制 如边界网关协议 BGP 域间路 由协议与域内路由协议的最大不同是域间路由协议允 许每个 AS 的管理者在选择最佳路由 要发布的路由 和接受的路由信息方面有自主的路由策略 而决定路 由策略的一个重要因素就是 AS 之间的商业关系 在 1 中将 AS 之间的关系分为了三类 1 提供者 客户关系 提供者为它的付费客 户转发数据 而客户不会在它的两个提供者之间转发 数据 该关系又可根据视角的不同分为客户 提供者 关系和提供者 客户关系 2 对等关系 一对对等关系的 AS 会互相转发 发往各自客户的数据 3 兄弟关系 一对兄弟关系的 AS 会互相转发 所有的数据 由上述内容可以发现即使在网络中存在某条路径 也不能代表该路径是能通行的 例如有三个 AS A B C 其中 C 同时是 A 和 B 的客户 根据 商业关系的定义 A 的数据不能经由 C 转发给 B 所 以 A B 之间的端到端性能不能由 A C B 这条路 径来评估 可以看出 AS 之间的商业关系对互联网 的端到端性能有着重要影响 因此在模拟 Internet 时 不能忽略这一关键因素 在 1 中提出了一种通过分析 BGP 路由表获取 AS 之间商业关系的算法 所以我们仅需对 BGP 路由 表进行不同处理 就能获取 AS 之间的连接关系 商 业关系及每个 AS 所包含的地址空间范围等信息 从 而建立一个包含 AS 间商业关系的抽象网络 但目前 整个 Internet 中包含的 AS 数量超过了 18000 个 我 们由于条件所限 不能使用大规模网络进行实验 所 以需要合并其中的一些 AS 结点和边 为保证抽象拓 扑的整体结构在合并前后相一致 我们将按照 AS 之 间的商业关系进行合并 2 2 2 2 依照 依照 ASAS 间商业关系进行合并间商业关系进行合并 根据 1 中的统计 在 Internet 中 AS 之间的关系 90 5 以上是提供者 客户关系 兄弟关系低于 1 5 对等关系低于 8 而且对等关系一般出现在 核心的 AS 之间 可以看出 对一对具有提供者 客 户关系的 AS 进行合并是一个合适的选择 此外在合 并过程中不应合并具有对等关系的 AS 以免将核心 AS 合并后对整体拓扑结构造成巨大影响 根据上述 分析 我们提出第一条合并规则 合并规则合并规则 1 1 设有两个 AS A 和 B 若 A 是 B 的唯一提供者 且 B 同其它 AS 间不存在对等关系 则可以将 B 并入 A 若 B 存在客户和兄弟 则将它 们都变为 A 的客户 合并 AS 的先后顺序我们根据 Internet 中的幂率 关系 10 来确定 该幂率关系指出一个 AS 的重要程 度同它的度 其邻接 AS 的个数 在统计学上有着指 数关系 即一个 AS 的度越大 它越可能是一个关键 AS 因此我们在合并过程中优先选择度小的 AS 进行 处理 图 1 描述的是采用规则 1 进行合并的过程 观察 图 1 可以发现 我们的合并规则还不能处理拥有一个 以上提供者的 AS 然而在实际环境中存在大量拥有 多个提供者的 AS 并且其中大部分是拥有两个提供 者的度为 2 的边缘 AS 所以如果我们想进一步合并 抽象网络 就需要对拥有 2 个提供者的 AS 进行处理 在处理拥有 2 个提供者的 AS 时 涉及到的 AS 一共有三个 两个提供者 AS 和一个客户 AS 当前 可以采用的处理方法有两个 将三个 AS 合并在一起 或合并其中的一对提供者 客户 AS 选择合并两个 提供者 AS 其效果显然同合并三个 AS 相同 使用上面提到的任一办法 都会对 AS 间的商业 关系造成一些破坏 若将三个 AS 合并成为一个 就 表明两个提供者 AS 将通过它们的客户 AS 相连接 这明显同提供者 客户商业关系的定义相矛盾 而且 这种影响还会由于迭代合并操作进一步扩大 使原本 存在于边缘 AS 间的连接关系逐渐成为关键 AS 之间 的连接 从而使整体网络结构发生改变 若我们合并 其中一对提供者 客户 AS 虽然客户 AS 必须同另 一个提供者 AS 断开连接 但由于这种影响不会被迭 代操作一步步的放大 同前一种方法相比 对整体结 构造成的影响要小很多 而且还可以通过选择度为 2 的边缘节点来降低对整体拓扑结构的影响 可以看出 使用第二种方法进行处理是一个合适的折中选择 所 以我们在此提出第二条合并规则 合并规则合并规则 2 若一个 AS 拥有两个提供者 并且 这个 AS 的度为 2 则可将其同一个提供者的连接切 断 然后将它与另一提供者合并 图 2 显示了增加规则 2 后的合并过程 在合并 Internet 抽象拓扑的过程中这条规则发挥了重要作用 实验中我们所使用的 BGP 路由表数据来自 Oregon 大 学的 Route Views 项目 2 该项目定期将数十台 AS 边界路由器的 BGP 路由表数据整理公布供研究者使 用 这是目前能够获得的公开的最完备的 BGP 路由 表数据 3 3 蠕虫传播模型 蠕虫传播模型 为了理解蠕虫传播的特性 大量研究采用数学模 型来描述其传播过程 3 4 5 其中使用较多的是传 染病学模型 本节我们将对该模型作出适当改进 然 后以此为基础对蠕虫传播进行模拟 传染病学模型定义如下 设系统中个体数量为 N 其中每个个体处于三种状态之一 S 代表容易被 疾病感染 I 代表已被感染 R 代表移除 例如被隔 离 死亡或免疫 个体的状态转变过程是 S I R 也就是常说的 SIR 模型 该模型的数学表 述如下 其中 s t i t r t 分别为 t 时刻系统中的易感个 体数量 已感染个体数量和移除个体数量 为感染 参数 为移除参数 并且在任意时刻 s t i t r t N 在描述蠕虫传播时 三个状态 S I R 分别代表 漏洞主机 被感染主机和不会被感染的地址 对应无 漏洞主机 未被分配的地址等情况 为了理解上面 公式的含义 我们先考虑一个采用均匀随机扫描的蠕 虫传播时的情况 设该蠕虫扫描的地址空间大小为 图图 1 应用合并规则应用合并规则 1 后的合并过程后的合并过程 对等关系兄弟关系提供者 客户关系 图图 2 同时应用规则同时应用规则 1 2 后的合并过程后的合并过程 对等关系兄弟关系提供者 客户关系 ti dt tdr tits dt tds titits dt tdi 1 2 3 蠕虫扫描频率为 scans s 在时间 t 时网络中 漏洞主机的数量为 s t 被感染主机数量为 i t 则一 个扫描包击中一个漏洞主机的概率 P inf s t 1 i t 个 被感染主机在 秒内发出的扫描包数量为 I t 若 为一很小值 则可以认为这些扫描包互不相关 且目的地址都不相同 由此可推出在 秒内新产生的 被感染主机数量 Xt符合二项分布 B I t P inf 设在这 秒内有 Yt台被感染主机被移除 于是我们 可以得到一个描述这个系统的离散时间模型 由于 Xt符合二项分布 所以它的数学期望为 E Xt I t P inf I t s t 1 将这组公式同 前面一组相比我们很容易看出公式 1 2 3 的来历并可得出 1 但这个模型在描述蠕虫传播时没有体现修补漏洞 主机这一环节 即 S R 过程 而这种情况在蠕虫爆 发的后期常大量出现 所以我们将移除参数 变为 漏洞主机移除参数 1和被感染主机移除参数 2 由于在模拟中并不体现 R 状态主机数量的变化 所以 将公式 3 从模型中去掉 修改后的模型如下 为获得 WSS 能够使用的传播模型 我们对上面 的公式作进一步推导 设 ASi的地址空间为 Ai 在时 间 t 时 ASi有 Ii t 个被感染主机 Si t 个漏洞主机 在 秒内 ASi收到的扫描包数量为 x 注意这里扫描 包的数量 x 是在模拟过程中的实际数据 因为是在 ASi范围内分析 所以一个扫描包击中漏洞主机的概 率为 P inf Si t Ai 1 于是在 秒内新产生的被感染 主机数量符合二项分布 B x P inf 我们可得出在 t 时刻 ASi的状态为 在 WSS 中 漏洞主机和被感染主机的移除参数 1i 2i在 tT 时线性增加到 1 我们发 现这样设置得到的结果同蠕虫实际爆发时的情况比较 吻合 设 ASj的地址空间为 Aj ASi在 秒内生成 了 Ii t 个扫描包 则这段时间由 ASi发向 ASj的 扫描包数量为 公式 9 10 11 就是在 WSS 中使用的蠕虫 传播模型 4 4 NS2 的扩充及测试用例的生成的扩充及测试用例的生成 NS2 是一个用于网络研究的离散事件模拟器 能 够进行包一级的模拟实验 该模拟器采用 C 和 TCL 语言混和编写 拥有标准 TCP IP 协议族 IP ICMP TCP UDP HTTP 是目前最优秀 的网络模拟器之一 WSS 是在 NS2 上开发的系统 它通过对 NS2 的功能进行扩充实现对蠕虫传播过程的 模拟 4 4 1 1 新的节点类型 新的节点类型 ASNode WSS 的核心是一个代表 AS 的节点类型 ASNode 它将 Internet 抽象拓扑同蠕虫传播模型结合 在一起 ASNode 依照 NS2 的规范建立 由 Application Agent 和 Classifier 三层组成 在 WormApp 中实现了上一章推导出的蠕虫传播模型 WormAgent 负责接收来自所有 AS 的扫描包并通知其 上层 WormApp 负责路由的分类器我们采用了系 统原有的 AddrClassifier 模块 整个结构如图 3 所示 4 4 2 2 路由算法 路由算法 在 NS2 中计算路由使用的是 Dijkstra 最短通路搜 索算法 为了在路由计算中考虑 AS 间商业关系 我 们算法中添加了对路径进行商业关系标注的操作 修 改后的算法定义如下 N 网络中所有节点的集合 S 源节点 M 已由路由算法归并的节点的集合 标注节点 x 到 y 的商业关系 若 x 同 y 不是直接相连 则标注为 若 x 到 y 的商业关系 为对等关系或提供者 客户关系 则标注为 Y 其他 1 tSx A tS tStS ii i i ii 2 tIx A tS tItI ii i i ii 9 10 WormApp WormAgen t AddrClr ASNode AS 级 Internet 拓扑 蠕虫传播模型 图图 3 ASNode 示意图示意图 2 titits dt tdi 1 tstits dt tds 7 8 t Xtsts tt YXtiti 4 5 t Ytrtr 6 tI A Scans i j ij 11 情况标注为 N L i j 节点 i 与 j 之间邻接链路的权值 距离 若两节点之间无直接相连的链路 或 S 到 i 的路径被 标注为 Y 且 i 为 j 的客户 则等于 C n 算法求得的当前从 S 到节点 n 的最小代价 路由的代价 算法步骤 1 置 M S 标注 S 到自身的路径为 N 对 每个节点 n N S 置 C n L S n 标注 S 到 n 的路 径为 2 找出 C W 最小的节点 W N M 加进 M 对每一个节点 n N M 置 C n min C n C W L W n 如果 C W L W n 小于 C n 则从 S 到 n 的路径就变成 S 到 W 的路径再加上从 W 到 n 的路径 并按下述方法修改其路径标注 若 S 到 W 的路径标 注为 N 且为 N 则将新路径标注为 N 否则标 注为 Y 3 重复执行 2 直到 M N 图 4 展示了使用此算法找出 A 到其它节点的最短 路径的过程 其中黑色节点为已确定最优路径节点 斑点节点为当前工作节点 白色节点为未确定节点 节点编号后面的三元组中第一项为路径的代价 第二 项指出路径中的前一节点 第三项为该路径的商业关 系标注 4 4 3 3 测试用例的生成 测试用例的生成 在进行本节讨论之前 我们先看一下 Slammer 蠕 虫爆发时的情况 根据统计该蠕虫至少感染了 75 000 台主机 其平均扫描频率为 4000 扫描包 秒 7 假设 这些扫描包平均经过 h 个路由器到达目的主机 若进 行包一级模拟 则 NS2 每秒需要处理的事件数量至少 为 75000 4000 h 3 108 h 显然进行这样的模拟是不 现实的 所以在 WSS 中 我们采用发送伪扫描包的 方法来解决这一问题 即所有 AS 每隔一段固定时间 向其它 AS 发送一个伪扫描包来通告在这段时间内 发送的扫描包总量 由于在 WSS 中传递的不是实际的扫描包 为了 给蠕虫检测系统提供测试用例 需要根据模拟结果生 成实际的扫描包 为了生成一个扫描包 我们需要知 道的主要信息有源 目的 IP 地址 包的到达时间及 负载内容 其中 IP 地址可以在对应 AS 的地址空间中 随机生成 负载可以根据需求指定任意数据 扫描包 的到达时间我们通过下面的方法获取 在每个长度为 的时间段内均匀的取若干个时间点 然后将该时间 段内到达的扫描包在这些时间点上进行泊松展开 来 确定每个包的到达时间 我们将生成的扫描包按 tcpdump 格式写入文件 作为测试用例提供给蠕虫检 测系统 5 5 验证和总结 验证和总结 为了验证 WSS 的有效性 我们将模拟实验得到 的结果同 CodeRed Iv2 和 Slammer 爆发时的情况进行 对比 CodeRed Iv2 根据 6 中的数据 CodeRed Iv2 感染了大约 359 000 台主机 一个蠕虫平均每分钟发出 358 个扫 描包 其扫描空间为整个 IPv4 地址空间 所以在我 们的实验中设置漏洞主机数量 N 370 000 扫描频率 5 9 扫描包 秒 扫描空间 232 伪扫描包的发送 时间间隔 10 秒 而且根据统计 CodeRed Iv2 第一 次爆发时极少用户采取了修补系统漏洞的措施 所以 模型中的两个移除参数 1 2一直取 0 图 5 a 是对 CodeRed Iv2 第一次爆发时被感染主机数量在最 初 32 小时内变化的评估 图 5 b 为使用 WSS 生 成的结果 可以看出 两者在很大程度上吻合 Slammer 据统计 Slammer 蠕虫至少感染了 75 000 台主机 一个蠕虫平均每秒发送 4000 个扫描包 7 所以我们 设置漏洞主机数量 N 80 000 扫描频率 4000 扫描 包 秒 扫描空间 232 由于 Slammer 的扫描频率 很高 所以我们采用一个较小的时间间隔 1 秒 而且由于这次模拟的是蠕虫爆发最初 5 分钟的情况 所以两个移除参数也取 0 图 5 c 摘自 7 是对 Slammer 爆发后最初 5 分钟整个网络中扫描包数量的 对等关系兄弟关系提供者 客户关系 DC B A E F E D C B 1 A N A F E F 2 B Y B 1 A N D 3 C Y C 2 B N A E 4 D Y F 2 B Y B 1 A N D 3 C Y C 2 B N A E 4 D Y F 2 B Y B 1 A N D 3 C Y C 2 B N A F 2 B Y B 1 A N D C 2 B N A E 3 1 4 2 5 6 图图 4 计算从计算从 A 到其它节点的最短路到其它节点的最短路 径径 评估 数据来源是 Wisconsin 大学高级网络实验室的 一个捕包网络 由于在采集的过程中程序出错 导致 中间一部分数据缺失 WSS 得出的结果如图 5 d 中实线所示 我们发现在这次模拟中蠕虫传播的速度 比实际情况快很多 在 7 中指出 Slammer 蠕虫的随机 数发生器存在缺陷 单个蠕虫扫描的地址空间不完全 虽然大量的蠕虫能够覆盖整个地址空间 但必然会影 响蠕虫的扩散速度 我们认为这正是导致模拟结果比 实际的情况传播快的原因 于是我们将扫描频率 降到 3700 扫描包 秒后重新实验 得出的结果如图 5 d 中点划线所示 可以看出 这次的结果同实际 情况比较贴近 以上对比结果表明 WSS 能够在实验室环境中 获取同实际蠕虫爆发时类似的统计数据和流量 这为 蠕虫研究尤其是蠕虫检测系统的开发提供了一个有力 的工具 相信会有十分广阔的应用前景 参考文献参考文献 1 L X Gao On inferring autonomous system relationships in the Internet In IEEE ACM Transactions on Networking December 2001 Vol 9 No 6 pp 733 745 2 University of Oregon Route Views Project Available on http www routeviews org 3 M Liljenstam Y Yuan B J Premore and D M Nicol A mixed abstraction level simulation model of large scale internet worm infestations In 10th International Workshop on Modeling Analysis and Simulation of Computer and Telecommunication Systems MASCOTS IEEE Computer Society 2002 pp 109 116 4 C C Zou W Gong and D Towsley On the performance of Internet worm scanning stra