您的位置:首页 > 参评方案展示 > 基础设施

清华大学:基于DNS的用户在线检测的算法与应用

  编辑点评:用DNS日志来检测用户的上、下线时间(或时刻)比其它方法有部署和实施简单的优势,其研究成果有较大的应用价值。

  1 引言

  根据《第37次中国互联网络发展状况统计报告》[1],我国互联网普及率已经达到了50.3%,网民规模更是达到了惊人的6.68亿,这个数量已经多于世界第三大国的人口总数。我国早已成为世界第一网络大国。

  在这个背景之下,理解获知用户使用网络的行为,发现其中的规律,具有了更加重要的意义。对于互联网监管方来说,了解网民的基本状态是了解网络动向,制定网络相关政策的重要基础。对于网管人员来说,能了解网络中的用户使用网络的状态和偏好、设备分布,不管对于网络安全管理、网络方针制定还是网络资源管理调配,都有着决定性的作用。对于网络的研究者来说,用户/设备往往是一个最小的独立单位,能从纷繁复杂的网络中提取这些单位的信息,获知他们的行为模式,在网络模拟等各类网络研究中都具有难以忽视的科学价值。最后,对于互联网产品的开发者,互联网产品的开发也往往离不开对用户使用习惯的了解和熟悉。

  不同的工作试图从各种角度揭示用户和设备的网络特征。在论文[2]中,通过对一个校园网内部分用户的长期测量,统计了各类的流量细节、设备移动特性和AP详细信息等网络、用户特征。而文献[3]中则通过采集了一次会议的数据,测量了用户分布、流量使用、在线时长等网络特征。

  也有一些文章希望从设备的网络特征中提炼出模型。文献[4]利用TCP链接的信息,给出了一个复合的网络模型。文献[5]中,Wang等人测量了手机移动网络的数据,通过测量用户上下线时间、用户ID等信息,从基站的角度出发为网络建立了模型,从流量的角度探讨了不同的基站类型。在文献[6]中,Benevenuto等人从社交网络的访问数据中挖掘用户的特征,研究了用户会话的时长分布。文献[7]使用了从在线网络游戏服务器中收集的用户信息,对用户数量、到达时间和会话时长进行了建模和分析。

  这些研究都关注了一个基本的问题,如何判断设备或用户到达、离开网络的时间,如何识别设备的在线状态。

  此前,在线检测的方法也有许多不同的方法。其一是使用登陆认证的时间。这种方法限制很大,只能应用在各个有联网认证的网络,而即使是校园网络的强认证环境,也有大量的机器是不使用认证系统的。其二,是基于DHCP的方法。由于设备在访问网络前需要使用DHCP服务来获取网络参数,所以可以使用DHCP的租约系统做在线的管理。DHCP服务也不是广泛使用的,在IPv6的场景下则应用更加有限。除了和登陆系统有同样的通用性问题之外, DHCP对于用户离网时间不能很好地估计。其三,有些研究[2,3]中使用TCP信息或者SNMP采集的信息判断用户在线,这需要在网络中部署大量检测节点,或者需要大量的流量抓取,不便于统一化的管理和增量部署。最后,也有一些研究使用了其他的方法,比如[5]中使用基站的数据来判定移动用户的在线情况。[6]中则在社交网站上研究用户的在线状态。这些研究针对性太强,不适用于一般性的网络研究和网络管理。

  针对此,本文引入DNS日志分析的方法,来识别设备在线的检测。通过这种方法,可以快速、有效地识别设备的在线时段。对于通用性的问题,由于DNS几乎是网络的基础设施,所以会被广泛的应用。也可以无缝迁移到IPv6的环境。所以它的适用性更好。同时,对比DHCP的方法,DNS信息代表着用户使用网络的行为,所以对到达、离开网络的时间能够得到更为准确的估计。同时,DNS的方法仅需要使用DNS日志,不需要改变现有的网络,也方便增量部署。对于现实的网络管理有诸多的优势。同时,该方法不旦可利用于校园网络,也可以被应用在整个教育网等全国性的大型网络上。

  文章组织如下。在第二章,介绍了在线检测算法,并给出了相关讨论。在第三章,设计实验讨论了算法的有效性。在第四章,本文给出了在线检测算法的应用。最后,本文在第五章给出了结论。

  2 基于DNS分析的用户检测方法

  域名系统(Domain Name System,DNS)[8,9]是一个用户访问网络时都会用到的分布式名称查询系统。不论用户访问何种类型的网络资源,都不可避免的会从域名解析开始。通过分析DNS日志,我们就可以解析出用户、设备的网络在线行为,为网络建模提供基础。

  我们使用一个IP、用户、时间、查询域名的四元组来代表IP为的用户在时刻查询了域名。所以,一个IP地址的全部查询可视作IP相同的一系列二元组。从这一系列的信息中,得知用户到达、离开网络的时间,进一步推测出何时有用户在线,是在线检测算法的主要目的。

  由于现代操作系统经常通过DNS系统进行周期性的网络任务如更新检查、各种网络应用也会在后台不停地访问网络以预加载、同步配置和接受推送,用户本身也有使用网络的行为,我们可以做出如下的基本假设:一个在线的设备会以短间隔不停地发送DNS请求。相反地,当设备离开时,自然就不会有任何来自该IP的DNS请求,表现出网络端的静默状态。

  根据这一思路,我们检测来自同一个IP地址的查询序列,如果两个时间相邻的查询和的查询间隔小于某个阈值,则我们认为这个查询来自同一个用户,期间该用户保持在线。反之,如果间隔,即,则我们认为这段时间内发生了“用户切换”,即它们分别属于两个先后使用该IP地址的用户与.而被视作用户的离网时刻,则被视作用户的入网时刻。用伪代码则可以表示如下:

  图1 DNS用户在线检测算法示意图

  如图1,图像是一个从左到右的时间轴,中间的圆形和菱形标记是发出DNS请求的时间。而下方则指示出用户/设备在线状态的标记结果。

  当相邻的请求,比如左边的两个圆形标记的间隔小于T时,则视作从同一个设备发出,User 1仍然标记为在线。反之,如果相邻请求间隔大于T,比如中间的圆形标记和方形标记,则视作User 1离网,User 2则加入了网络,将时间靠前(左边)的圆形标记视作User 1的离开时刻,靠后(右边)的菱形标记视作User 2到达时刻。并将两者中间的时间记录为离线时间,没有任何用户在线。

  这个算法虽然看起来并不复杂,但是其中包含有一个重要的问题,即阈值T的选取。阈值T代表着两个在线的用户或设备之间大约有多久的离线时间。如果选取的T太小,会错误地将一个用户的网络行为分为多段;如果T的取值过大,则会导致无法正确识别用户的上下线时间点,将多个用户识别成同一个用户。

  此前文献[4]中指出用户内的连接到达间隔满足韦伯分布,DNS也满足这一分布。所以,T较小时理论错误发现率会迅速升高。另一方面,在使用动态IP地址的系统中,IP地址会在收回后的一段时间后才重新发放。这在一定程度上限制了T的上限。这些因素都影响了T的选取。接下来本文会使用现实数据,设计实验进行比对,进一步研究T的恰当取值。

  3 实验和评估

  3.1 数据集和数据标定

  我们使用2014年11月某一天的DNS数据为例,来实验评估这个在线检测算法的准确性。这一天的总数据量包含88191个独立的IP地址,共计有328,386,774条DNS请求。

  我们使用同一天的DHCP数据作为真实值,来对DNS的方法进行实验和评估。DHCP (Dynamic Host Configuration Protocol)[10]是一种自动配置协议,用来自动提供IP地址、子网掩码、默认网关等网络配置信息。客户端主机在支持DHCP协议的网络中,可以向DHCP服务器索取这些信息,进而实现自动化的网络配置,而不需手工设置静态IP地址即可访问网络。根据RFC 2131[10],客户端在接收到网络参数之后,需多播发送DHCPREQUEST信息选择租约,而DHCP服务器最终返回DHCPACK信息确认租约,此后客户端就可以正常使用网络参数连接网络了。所以,根据这个信息,我们可以推测出设备的到达时刻。不过,由于很多设备并不是显式地离开,而是租约到期被收回地址,所以无法通过DHCP信息精确地测量一个设备的离网的时间。

  需要说明的是,DHCP本身可以作为一种检测用户到达的手段。但是,如同在引言部分讨论的那样,DHCP方法有诸多的缺点和限制。而DNS方法则是一种更加通用的方法。

  此外,DHCP方法标定用户上下线并不可能达到完全准确。在实验和评估的部分,本文也会分析数据标定对结果造成的影响。

  3.2 效果评估和最佳阈值选取

  为了验证算法的有效性,并选取算法中最合适的阈值T,我们使用DHCP方法标定的用户到达时间和DNS方法的结果进行比对,以检验准确性。如果DNS方法错判了一个用户的离开时刻,则会影响下一个用户的到达时刻。所以,仅通过对比到达时刻的准确度,即可以评估整个在线检测算法的准确性。

  我们将DHCP方法标定的用户到达时间点称作“DHCP切换”,而将DNS方法得出的用户到达时间称作“DNS切换”。定义精确率(precision rate)和召回率(recall rate)如下:

  图3是在不同阈值参数T下的pr曲线图。横轴是在上文中提到的时间间隔T。如图3所示,在阈值T较小时,召回率保持在一个很高的水准,而精确率上升很快。这是因为在DNS分割策略激进的情况下,DHCP的判定结果被很好的概括了,但是却出现了大量的误分段现象。随着T变大,精确率一直在升高,这是自然地结果——DNS方法的策略越来越保守了。而此时相应地,召回率出现了缓慢的下降,意味着时间阈值T可能开始接近并超过IP释放的时间。

  图3 DNS用户在线检测算法效果PR曲线

  F1-score是精确率和召回率的调和平均。公式如下:

  其中p和r分别是精确率和召回率。它综合考量了精确率和召回率的功效。根据图3显示的结果,阈值T在40-45分钟左右都可以取得较好的效果。我们以下取 分钟作为阈值。这时的精确率90.7%,召回率为89.9%,DNS方法很好地符合DHCP所标定的真实值。此外,在这一估计下,DNS方法检测出该时间段内用户/设备总数量为98771,与DHCP所标记的共99551个用户的数目非常接近。这也从另一个角度说明这一估计非常精确。

  从图3中可以发现,即使在x轴的最左边(这里DNS算法的参数选取十分激进,此时一个设备不出现2分钟就会被当作下线),召回率仍然只有90%左右。这说明DHCP的数据并不能和DNS完全重合,意味着数据标定过程带来了潜在的误差。

  我们选取分钟,并对所有的DHCP数据进行检查,发现在所有的约9000个左右无法被DNS识别在线的DHCP到达时刻的样本中,有超过4200个是由于该用户申请地址之后没有任何的后续活动就离开了网络。这种情况在移动网络中十分常见,用户其实并没有真正使用网络,只是误加入之后申领了一个地址。另有将近1800个用户,经过交叉的比对没有使用DHCP服务所配置的DNS,而是使用了自定义的DNS。所以,这些样本的DNS数据本不包括在数据集中。这种情况在小部分PC机或者笔记本上会发生。此外还有3748个用户的错判仍不属于之上两类的情况。

  去除因为误联网和使用其他DNS服务所造成的样本的错误标定,在精确率不发生变化的情况下,召回率达到96.3%。这是对基于DNS算法准确度的一个更优的估计。

来源:CERNET第二十三届学术年会论文集作者:
var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "//hm.baidu.com/hm.js?b841bd73360946ada23db9fa82c9c6ae"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })();