基于顶点信息采样的随机包标记IP追踪算法NSPPM

２相关工作
为了对分布式拒绝服务攻击的发起者进行追踪，从而通 过对其施加威慑来减少该类攻击事件的发生，人们提出了很 多解决方案。这些方案主要分为两大类：即需要上游ＩＳＰ协 作的ＩＰ追踪方案（文［７～９］）和通过为网络中的路由器增加 相应的功能以实现自动ＩＰ追踪过程（文［４，１０～１２］）。按照 执行ＩＰ追踪操作入手的不同角度，本节将这些方案分成４类
Ａｂｓｔｒａｃｔ Ｉｎ ｔｈｅ ｄｅｆｅｎｄｉｎｇ ｏｆ ｔｈｅ ｄｉｓｔｒｉｂｕｔｅｄ ｄｅｎｉａｌ—ｏｆ－ｓｅｒｖｉｃｅ ａｔｔａｃｋ．ｗｈｉｃｈ ｉＳ ｔｈｅ ｍｏｓｔ ｉｎｔｒａｃｔａｂｌｅ ｐｒｏｂｌｅｍ ｉｎ Ｉｎｔｅｒｎｅｔ ｓｅｃｕｒｉｔｙ ｎｏｗａｄａｙｓ，ｔｒａｃｉｎｇ ａｎｏｎｙｍｏｕｓ ｆｌｏｏｄｉｎｇ ｐａｃｋｅｔｓ ｔｏ ｔｈｅｉｒ ｓｏｕｒｃｅｓ ｏｆ ｏｒｉｇｉｎ（ＩＰ ｔｒａｃｅｂａｃｋ）ｉｓ ｏｆ ｇｒｅａｔ ｉｍｐｏｒｔａｎｃｅ ａｎｄ ｉｎ ｌｉｔｅｒａｔｕｒｅ ｔｈｅｒｅ ｈａｓ ｂｅｅｎ ｃｏｎｓｉｄｅｒａｂｌｅ ｉｎｔｅｒｅｓｔ ｉｎ ｔｈｉｓ ｔｏｐｉｃ．Ｂｙ ｅｍｐｌｏｙｉｎｇ ａｎｏｖｅＩ ａｌｇｏｒｉｔｈｍ ｏｆ ｎｏｄｅ ｓａｍｐｌｉｎｇ ａｎｄ ｔｈｅ ｓｕｂｓｅｑｕｅｎｔ ａｌｇｏｒｉｔｈｍ ｏｆ ａｔｔａｃｋ ｐａｔｈｓ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ，ｗｅ ｐｒｅｓｅｎｔ ｉｎ ｔｈｉｓ ｐａｐｅｒ ａ ｎｅｗ ｓｏｌｕｔｉｏｎ，ｎａｍｅｌｙ ＮＳＰＰＭ，ｔＯ ａｄｄｒｅｓｓ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ＩＰ ｔｒａｃｅｂａｃｋ，ｗｈｉｃｈ ｃａｎ ｂｅ ｄｅｐｌｏｙｅｄ ｉｎｃｒｅｍｅｎｔａｌｌｙ ｗｈｉｌｅ ｐｒｏｖｉｄｉｎｇ ｂａｃｋｗａｒｄｓ ｃｏｍｐａｔｉｂｉｌｉｔｙ ｗｉｔｈ ｔｈｅ ｅｘｉｓｔｉｎｇ ｎｅｔｗｏｒｋ ｉｎｆｒａｓｔｒｕｃｔｕｒｅ Ａｓ ｃｏｍｐａｒｅｄ ｗｉｔｈ ｐｒｅｖｉｏｕｓ ｗｏｒｋ，ｏｕｒ ａｐｐｒｏａｃｈ ａｌｌｏｗｓ ａ ｖｉｃｔｉｍ ｔｏ ｉｄｅｎｔｉｆｙ ｔｈｅ ｐａｔｈｓ ｏｆ ｍｕｌｔｉｐｌｅ ａｔｔａｃｋ ｔｒａｆｆｉｃｓ ｂｏｔｈ“ｏｎ－ｇｏｉｎｇ＂ａｎｄ“ｐｏｓｔ－ｍｏｒｔｅｍ＂ｗｉｔｈｏｕｔ ｒｅｑｕｉｒｉｎｇ ｔｈｅ ｏｐｅｒａｔｉｏｎａｌ ｓｕｐｐｏｒｔ ｏｆ Ｉｎｔｅｒ— ｎｅｔ Ｓｅｒｖｉｃｅ Ｐｒｏｖｉｄｅｒｓ（ＩＳＰｓ）ｏｎｌｙ ａｔ ｔｈｅ ｃｏｓｔ ｏｆ ｓｏｍｅ ｃｏｍｐｕｔａｔｉｏｎｓ ａｄｄｅｄ ｔＯ ｅａｃｈ ｒｏｕｔｅｒ ｗｉｔｈ ａ ｔｒｉｖｉａｌ ｏｖｅｒｈｅａｄ．Ｍｏｒｅｏ－ ｖｅｒ，ｔｈｅ ａｐｐｒｏａｃｈ ｏｆｆｅｒｓ ａｎ ｅｆｆｉｃｉｅｎｔ ａｔｔａｃｋ ｐａｔｈ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈ ｓｕｃｃｅｓｓｆｕｌｌｙ ｃｉｒｃｕｍｖｅｎｔｓ ｔｈｅ ｃｏｍｂｉｎａ— ｔｏｒｉａｌ ｅｘｐｌｏｓｉｏｎ ｐｒｏｂｌｅｍ ｉｎｃｕｒｒｅｄ ｂｙ ｏｔｈｅｒ ｔｅｃｈｎｉｑｕｅｓ． Ｋｅｙｗｏｒｄｓ ＩＰ ｔｒａｃｅｂａｃｋ，Ｐｒｏｂａｂｉｌｉｓｔｉｃ ｐａｃｋｅｔ ｓａｍｐｌｉｎｇ，ＮＳＰＰＭ
Ａ Ｎｏｄｅ Ｓａｍｐｌｉｎｇ Ａｐｐｒｏａｃｈ ｔｏ Ｐｒｏｂａｂｉｌｉｓｔｉｃ Ｐａｃｋｅｔ Ｍａｒｋｉｎｇ－ｂａｓｅｄ ＩＰ Ｔｒａｃｅｂａｃｋ
ＪＩＮ Ｓｈｕ ＬＩＵ Ｆｅｎｇ－Ｙｕ （Ｎａｍｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｎａｍｉｎｇ ２１００９４）
＊）本文受到国家自然科学基金资助项目（６０２７３０３５）－－“软件抗衰和自愈”、南京理式在学科研发燕尾服基金２００５－＂网络性能诊断与安全”资助。 金舒博士研究生；刘凤玉教授，博士生导师，研究方向：信息安全技术、软件抗衰技术．
· ３８·
万方数据
并分别对其做出具体介绍。 ２．１源地址过滤 攻击发起者对ＩＰ伪装技术的应用是ＩＰ追踪的一大障
碍。若没有经过舻伪装，任何ＤＤｂＳ攻击流中的数据包都可 以被用来进行协议分析，提取其源ＩＰ地址，从而轻易地追踪 到该次攻击的发源地。为了彻底防止ＩＰ伪装的发生，Ｐ． Ｆｅｒｇｕｓｏｎ与Ｄ．Ｓｅｎｉｅ提出了“Ｉｎｇｒｅｓｓ Ｆｉｌｔｅｒｉｎｇ岖阳的概念，即 在网络服务提供者的接入服务器上加入简单的认证机制，对 于发自用户方并准备送入Ｉｎｔｅｒｎｅｔ的数据包，接入路由器会 逐一检查其源地址。如果其源地址在用户所处的子网范围之 内（或更进一步，来自该用户），接入路由器将对其进行正常转 发；若其源地址在用户所处的子网之外（包括无效ＩＰ地址）， 接入路由器将丢弃该数据包。虽然该技术一经采用将能有效 地防止ＩＰ伪装的发生，但由于对该技术的应用并不会为各 ＩＳＰ带来大于其投入成本的经济利益，这项技术一直没有得 到大规模的采用。具有同样命运的“Ｅｇｒｅｓｓ Ｆｉｌｔｅｒｉｎｇ，，［９］技术 也基于类似的原理，其源地址过滤机制位于局域网连接１１１一 ｔｅｒｎｅｔ的出口路由器上，且仅允许以局域网内有效ＩＰ地址作 为源ＩＰ地址的数据包通过。
考虑到Ｉｎｔｅｍｅｔ设计上的局限Ｉ－１～３］，在不对其路由基础 设施做出重大改进的情况下，并不可能找到一种彻底杜绝分 布式拒绝服务攻击的方法。出于这些原因，特别是Ｐ伪装技
术的存在，我们为研究设定了一个更实际的目标即尽可能 地［４￣６］追踪至ＤＤｏＳ攻击的源头：攻击发起者的计算机（攻击 数据包没有进行ＩＰ伪装）或攻击发起者所处的局域网（攻击 数据包进行了ＩＰ伪装）。在我们给出的ＩＰ追踪方案中，经过 功能增强（加入用于采样数据包传递路径中的顶点信息的随 机包标记技术）后的路由器以一定的概率随机地对过往的数 据包进行采样并将自身的识别信息通过带外数据流一同发送 至被采样数据包的目的地址。这样，当受害主机通过某种机 制（如入侵检测）确认其正在遭受分布式拒绝服务攻击时，该 主机可以通过收集由攻击路径上各路由器发送来的带外数据 重建整个攻击路径，从而追踪到该次攻击的发起方（即使此时 攻击已结束）。
１前言
随பைடு நூலகம்诸如电子邮件、网络购物、即时通讯等服务在人们Ｅｔ 常生活中的使用，Ｉｎｔｅｒｎｅｔ正在社会和经济领域产生着越来 越大的影响。在任何时问、任何地点向任何人提供网络连接 的同时，Ｉｎｔｅｒｎｅｔ的应用也随之带来了很多安全问题。其中 分布式拒绝服务攻击（ＤＤｂＳ）被认为是一类最难解决的问题。 近年来发生的一些重大网络安全事件，如２０００年Ｙａｈｏｏ、 ｈｎｌａｚｏｎ、ＥＢａｙ等电子商务网站遭遇ＤＤｏＳ攻击而瘫痪；２００１ 年称为“Ｒｅｄ Ｃｏｄｅ”的蠕虫攻击白宫网站迫使其将内容转移至 备用服务器等。据媒体报道，２０００年全年网络安全入侵使全 球范围内的企业共损失了约１４亿美元，这其中６０％的损失 源于病毒及ＤＤｏＳ攻击。而考虑到某些企业为了形象而隐瞒 了网络安全事件，上述数据可能仅是冰山的一角。结合近来 各种网络攻击软件越来越容易操作且被不断大量地传播， ＤＤｂＳ攻击数量在将来的一段时期内仍将处于一个不断上升 的状态。
２．２链路测试 一种符合直觉的ＩＰ追踪方案（“Ｉｎｐｕｔ Ｄｅｂｕｇｇｉｎｇ”）是：当 发现自身正受到分布式拒绝服务攻击时（短时间内有大量数 据涌入），受害者将向直接与其相邻的路由器（位于其“上游” 的ＩＳＰ接人路由器）询问其来源。在确定该组攻击数据流入 接口后，该路由器将进一步向位于其上游的（与该接口相连） 路由器发送相应的查询。该过程将被持续地执行，直至追踪 到攻击的发起者。上面描述的入侵追踪过程由于极大地依赖 于攻击路径上各级安全相关工作人员的相互协作和干预，因 而实用性大大地受到限制。为解决该问题而提出的“Ｃｅｎｔｅｒ－ Ｔｒａｃｋ”［７］方案，可以自动地执行上述的逐级状态查询操作，从 而使链路测试技术能够真正得到实际应用。 Ｂｕｒｃｈ与Ｃｈｅｓｗｉｃｋ提出了一种类似的ＩＰ追踪方案—— 受控洪泛（“Ｃｏｎｔｒｏｌｌｅｄ Ｆｌｏｏｄｉｎｇ”）［５］。在该方案中，受攻击的 网络主机将以自身为出发点构建其周围Ｉｎｔｅｍｅｔ的连接拓扑 图［１孔Ｈ］，在此基础上，该主机将向与其直接连接的路由器逐 个发送大量噪声数据，并观察ＤＤＯＳ攻击数据流是否有减少。 如果有减少，则表明攻击数据来自该路由器。再以该路由器 为出发点进行同样的受控洪泛操作，持续执行该过程，直至最 终追踪到攻击的发起者。由于Ｉｎｔｅｒｎｅｔ拓扑结构的动态性， 为其建立连接拓扑图将十分困难。作为链路测试（“Ｉｎｐｕｔ Ｄｅ— ｂｕｇｇｉｎｇ”）技术的两种实现，受控洪泛与ＣｅｎｔｅｒＴｒａｃｋ一样都 只能迫踪正在进行中的ＤＤｂＳ攻击。一旦攻击停止（或依照 一定的时间间隔发起），这两种方案都将无能为力。 ２．３路由端日志 日志机制作为一种与系统性能实现相关的权衡因素总会 引发一些争论。不考虑随之带来的有关隐私的问题，在路由 器上加入数据日志功能，以记录下所有来往数据包的信息，可 以为事后追查入侵者提供证据支持。考虑到Ｉｎｔｅｒｎｅｔ上一个 典型的路由器每秒将转发约２０００万个数据包［１ ５１，若每个数 据包平均长１２０字节，为了将这些数据包记入日志，每秒钟需 要约２．４Ｇ的存储空间。即使仅记录协议相关信息（设为２８ 个字节：２０字节的ＩＰ数据包头部加上负载的上层应用协议 的前８个字节），每秒也需要占用超过５００Ｍ的存储空间。巨 大的数据开销使得在路由器端记录所有的数据包信息几乎不
计算机科学２００７Ｖ０１．３４ＮＱ．３
基于顶点信息采样的随机包标记ＩＰ追踪算法ＮＳＰＰＭ＊）
金舒刘凤玉 （南京理工大学计算机科学与技术系 南京２１００９４）
摘要本文通过提出一种顶点采样算法及与之相对应的攻击路径重建算法，给出了一种新型的基于随机包标记技 术的入侵追踪方案ＮＳＰＰＭ。该方案保持了对现有网络基础设施的兼容并且可以增量地逐渐布置到整个Ｉｎｔｅｒｎｅｔ中。 相比较于一些前期的相关工作，ＮＳＰＰＭ方案可以在仅带来较小开销的情况下为受攻击方提供对多重ＤＤｏＳ攻击路径 （活跃的或非活跃的）的识别且不需要上游ＩＳＰ的协作。同时，较之传统的基于边采样的攻击路径重建策略，基于顶点 采样算法的攻击路径重建策略具有更低的计算复杂度。 关键词ＩＰ追踪，随机包标记，ＮＳＰＰＭ
万方数据
可能。在对安全性要求较高的场合，有选择地将部分数据包 中的信息记入日志中就成为一种较现实的选择。