论文部分内容阅读
访问超点是网络中在一段时间内与远大于平均值数量的对端有交互行为的主机。访问超点检测算法的目标就是找出流量中连接对端数大于阈值的所有主机。访问超点一般是服务器、代理、扫描器和被DDoS攻击的主机。访问超点检测对网络安全和网络管理有重要的意义，也是这个领域一个没有完全解决的热点问题。
现有访问超点检测算法存在如下缺陷：算法运行时间长，无法实时处理高速网络数据；不能在滑动时间窗口下运行，无法检测跨越时间窗口边界的访问超点；分布式环境下通信开销大等。本文针对上述三个问题分别进行了研究。
本文将GPU（Graphics Processing Unit）并行计算方法引入了访问超点检测的研究领域，解决了访问超点检测的实时性问题。基于Bernstein条件等并行计算的相关基础理论，给出了一组用于判定访问超点检测算法是否能在GPU环境中并行运行的条件，并提出了一个基于GPU的通用访问超点检测框架。利用该框架，将三个现有的符合条件的访问超点检测算法移植到了三个不同性能的GPU平台上，并基于10Gb/s和40Gb/s带宽的实测流量进行了测试。实验结果表明，对于符合条件的访问超点检测算法，GPU通用访问超点检测框架不仅能保证估算准确率与CPU环境下相同，而且有效运行时间只有CPU平台上有效运行时间的1/50到1/2050。
滑动时间窗口下的访问超点检测需要解决检测次数频繁、增量式更新主数据结构和快速的主数据结构状态维护三个挑战。本文提出了用模糊估值器和滑动时间窗口下的计数器相结合的方法解决了上述问题。本论文首次提出了将模糊估值器（Rough Estimator，RE）引入访问超点检测算法的研究思路。具体的方法是基于统计学领域经典的基数模糊估值算法，提出一种面向IPv4地址的轻量级估值器，用其对海量的原始流量数据进行筛选，从而大大减少了估值的压力。论文证明了在常规参数下，用RE进行访问超点筛选的准确率超过99.9%。距离计数器（Distance Recorder，DR）是本文提出的一种能在滑动时间窗口下增量式更新且内存最优的计数器。在设计了模糊估值器和距离计数器所有相关细节的基础上，本文提出了一个滑动时间窗口下的实时访问超点检测算法-滑动模糊线性算法（Sliding Rough and Linear Algorithm，SRLA）。SRLA算法将RE作为初筛工具，在处理网络数据流的同时，在线生成候选访问超点列表。由于初筛环节大大减少了估算对象的数量，所以在估算环节，SRLA算法使用了一种高精度的估值器，线性估值器（Linear Estimator，LE），能够更加准确地估算出候选列表中各主机的连接对端数。实验表明，对10Gb/s和40Gb/s的高速网络，在离散时间窗口下，SRLA算法的错误率接近于现有算法，但估算访问超点的时间平均只有现有算法的1/520。估算访问超点时间的降低，使得SRLA在需要进行频繁检测的滑动时间窗口下运行成为可能。通过将RE和LE与DR结合，SRLA算法实现了在滑动时间窗口下对主数据结构增量式地更新。在10Gb/s和40Gb/s实测流量条件下，SRLA算法能在时间窗口为300秒，滑动步长为1秒的条件下支持实时访问超点检测。
针对SRLA算法在DR数量增多时对DR进行状态维护的时间瓶颈问题，本论文提出了一种低状态维护时间的计数器，异步时间戳计数器（Asynchronous Timestamp，AT）。AT比DR多占用一个比特的内存。对于具有k个时间片的滑动时间窗口，维护AT状态的时间复杂度只有O(1/k)，而维护DR状态的时间复杂度为O(1)。基于AT，本文提出了一种滑动时间窗口下低状态维护时间的连接对端数估算算法-虚拟异步时间戳估计器（VirtualAsynchronous Timestamp Estimator，VATE）。实验表明，当AT个数越多时，VATE估算准确率越高。当AT个数达到232时，VATE在每个时间片里维护所有AT状态的时间不超过2.6毫秒，小于维护同等数量的DR所用时间的1/400。用AT替换SRLA算法里的DR，可以进一步降低SRLA算法的运行时间。
在分布式环境下，数据汇聚会占用大量带宽或造成流量尖峰。为了降低分布式环境下的通信开销，本论文设计了一个三阶段托付的分布式访问超点检测算法-基于模糊估值器的分布式异步访问超点检测算法（Rough Estimator based Asynchronous Distributed algorithm，READ）。READ算法利用RE在分布式环境下生成候选访问超点。READ算法仅向全局服务器传递与候选访问超点相关的数据，而不是全部主数据结构，从而降低了通信开销。本文从理论上证明了READ算法在分布式环境下的错误率不高于汇聚检测数据条件下的错误率。实验表明，对10Gb/s和40Gb/s的高速网络数据，READ算法可以将通信量减少95%以上。
本博士论文从各种不同的角度对高速网络访问超点检测算法进行了深入细致地研究。利用本文的研究成果，可以实现滑动时间窗口下高速网络的实时访问超点检测，以及在分布式环境下高效快速的访问超点检测。
现有访问超点检测算法存在如下缺陷：算法运行时间长，无法实时处理高速网络数据；不能在滑动时间窗口下运行，无法检测跨越时间窗口边界的访问超点；分布式环境下通信开销大等。本文针对上述三个问题分别进行了研究。
本文将GPU（Graphics Processing Unit）并行计算方法引入了访问超点检测的研究领域，解决了访问超点检测的实时性问题。基于Bernstein条件等并行计算的相关基础理论，给出了一组用于判定访问超点检测算法是否能在GPU环境中并行运行的条件，并提出了一个基于GPU的通用访问超点检测框架。利用该框架，将三个现有的符合条件的访问超点检测算法移植到了三个不同性能的GPU平台上，并基于10Gb/s和40Gb/s带宽的实测流量进行了测试。实验结果表明，对于符合条件的访问超点检测算法，GPU通用访问超点检测框架不仅能保证估算准确率与CPU环境下相同，而且有效运行时间只有CPU平台上有效运行时间的1/50到1/2050。
滑动时间窗口下的访问超点检测需要解决检测次数频繁、增量式更新主数据结构和快速的主数据结构状态维护三个挑战。本文提出了用模糊估值器和滑动时间窗口下的计数器相结合的方法解决了上述问题。本论文首次提出了将模糊估值器（Rough Estimator，RE）引入访问超点检测算法的研究思路。具体的方法是基于统计学领域经典的基数模糊估值算法，提出一种面向IPv4地址的轻量级估值器，用其对海量的原始流量数据进行筛选，从而大大减少了估值的压力。论文证明了在常规参数下，用RE进行访问超点筛选的准确率超过99.9%。距离计数器（Distance Recorder，DR）是本文提出的一种能在滑动时间窗口下增量式更新且内存最优的计数器。在设计了模糊估值器和距离计数器所有相关细节的基础上，本文提出了一个滑动时间窗口下的实时访问超点检测算法-滑动模糊线性算法（Sliding Rough and Linear Algorithm，SRLA）。SRLA算法将RE作为初筛工具，在处理网络数据流的同时，在线生成候选访问超点列表。由于初筛环节大大减少了估算对象的数量，所以在估算环节，SRLA算法使用了一种高精度的估值器，线性估值器（Linear Estimator，LE），能够更加准确地估算出候选列表中各主机的连接对端数。实验表明，对10Gb/s和40Gb/s的高速网络，在离散时间窗口下，SRLA算法的错误率接近于现有算法，但估算访问超点的时间平均只有现有算法的1/520。估算访问超点时间的降低，使得SRLA在需要进行频繁检测的滑动时间窗口下运行成为可能。通过将RE和LE与DR结合，SRLA算法实现了在滑动时间窗口下对主数据结构增量式地更新。在10Gb/s和40Gb/s实测流量条件下，SRLA算法能在时间窗口为300秒，滑动步长为1秒的条件下支持实时访问超点检测。
针对SRLA算法在DR数量增多时对DR进行状态维护的时间瓶颈问题，本论文提出了一种低状态维护时间的计数器，异步时间戳计数器（Asynchronous Timestamp，AT）。AT比DR多占用一个比特的内存。对于具有k个时间片的滑动时间窗口，维护AT状态的时间复杂度只有O(1/k)，而维护DR状态的时间复杂度为O(1)。基于AT，本文提出了一种滑动时间窗口下低状态维护时间的连接对端数估算算法-虚拟异步时间戳估计器（VirtualAsynchronous Timestamp Estimator，VATE）。实验表明，当AT个数越多时，VATE估算准确率越高。当AT个数达到232时，VATE在每个时间片里维护所有AT状态的时间不超过2.6毫秒，小于维护同等数量的DR所用时间的1/400。用AT替换SRLA算法里的DR，可以进一步降低SRLA算法的运行时间。
在分布式环境下，数据汇聚会占用大量带宽或造成流量尖峰。为了降低分布式环境下的通信开销，本论文设计了一个三阶段托付的分布式访问超点检测算法-基于模糊估值器的分布式异步访问超点检测算法（Rough Estimator based Asynchronous Distributed algorithm，READ）。READ算法利用RE在分布式环境下生成候选访问超点。READ算法仅向全局服务器传递与候选访问超点相关的数据，而不是全部主数据结构，从而降低了通信开销。本文从理论上证明了READ算法在分布式环境下的错误率不高于汇聚检测数据条件下的错误率。实验表明，对10Gb/s和40Gb/s的高速网络数据，READ算法可以将通信量减少95%以上。
本博士论文从各种不同的角度对高速网络访问超点检测算法进行了深入细致地研究。利用本文的研究成果，可以实现滑动时间窗口下高速网络的实时访问超点检测，以及在分布式环境下高效快速的访问超点检测。