面向上下文图形可视化挖掘企业网络行为

陶维成

（南京航空航天大学 计算机科学与技术学院，江苏 南京 210026;芜湖职业技术学院 信息工程系，安徽 芜湖，241006）

面向上下文图形可视化挖掘企业网络行为

陶维成

（南京航空航天大学 计算机科学与技术学院，江苏 南京 210026;芜湖职业技术学院 信息工程系，安徽 芜湖，241006）

在企业分布式网络系统中，精确地识别谁在做什么日益具有挑战性。 目前的网络管理系统依赖于对用户身份的推理，此类方法由于收集到的数据或缩放比例粗糙，从而在大规模的网络环境下不能精确地对网络行为挖掘、发现和管理。对主机、用户、应用程序和数据访问等网络上下文内容进行可视化挖掘、发现，从而为网络管理过程的动态化提供了重要帮助。

网络行为；可视化；上下文图形；可视化挖掘

1 引言

本文提出一个动态的，可视化的，知道谁何时何地在使用网络做什么，为此，应实现如下目标：

何人，何事，何时，何处(4W)：知道在网络上正在发生什么事情，也就是何人(哪个用户)在何处(哪个主机)何时(什么时间)正在运行何种程序(应用程序)，将与其连接需求相关的上下文信息被记录下来。

简单，有效和可定制：大多数用户将不需要修改基本的视图集合，通过一个模块查看器实现自定义功能，用户能够自定义他们的配置和构建一个他们最感兴趣的环境(如排在前10的应用程序，当前连接人力资源(HR)用户数，网格计算结点统计等)。

智能化：将可视化与数据挖掘结合起来进行日常网络监控和管理实务。如构建决策树来对网络事件分类，或为了通过用户/应用程序理解相似行为进行集群计算并且识别潜在的问题。

从广义上讲，一个应用视图存在三种形式，本地用户(本地目录或用户路径)，本地机器(根层安装，如/usr/bin)，以及企业服务(根层装载)。 数据融合形成每个在概念上的网络连接上下文信息，如图1所示。

图1 4W网络上下文

2 在上下文图形中可视化挖掘

2.1 可视的变化性与网络图的不变性

为了帮助管理员/研究者理解他们的网络，由此对非正常活动的探测。对于变化的和不变的网络图形的集合是个重要决定因素。通过可视的最大公共子图(MCS)和最小的公共子图(MCP)来表示这个问题的答案。图的最大公共子图(MCS)被定义为出现在所有超图中的最大的子图。重要的是要注意所有n个网络图的MCS跨越整个监控周期具有不变性。换句话说，主机，用户和应用程序结点，以及它们之间总是出现连接的边。有关计算的复杂度，最大公共子图同构是一个最优化问题，即著名的NP难题[1]。然而，在一个企业网络集合中，由于每一个结点被唯一地标贴(IP地址，用户ID或进程二元路径)，实际上，许多NP难题问题能被有效地解决(通常是线性时间)[2]。

网络图的最小公共子图(MCP)被定义为包括所有图的最小图的子图。 网络图在MCP和MCS之间的变化性是不同的，即：VARn=MCPn-MCSn。

子图MCS和子图MCP在网络监控和管理中是重要的，因为当MCPs测量能在网络中生长为最大可能活动，MCSs作为不变式蕴含强连接和在构成稳定的长期存活的网络结点中的一致关系。然而，上述子图和超图表现出离散属性(即：0表示不出现，或1表示出现)，用概率能表示结点/边，最小公共子图的概率(MCPP)是一个在此概率中扩展的MCP被作为边权计算，即：，式中F(u,ν)是 edge(u,ν)的出现频率，|G|表示快照图的数目。结点/边出现概率的关系是 PMCS=1>P{pi…j}>Pi∧Pj>0。对于MCPP构造此类图的概率可用于预测网络链接和探测异常现象的可能性。例如，假设一个用户U对应用程序A1和主机H1的连接概率为0.9，并且对应用程序A2和主机H2的概率是0。任何在图U，A1和 H1中边的丢失，或在 U，A2和 H2中突然出现新的连接，这些情况是值得怀疑和需要深入跟踪调查。

2.2 图距离方差

对于一个只有数十个结点组成的网络的可视化检查可能是容易的，当网络有数千个结点时，进行手工可视地比较几乎是不可能，如图2所示。图3所显示可改变的视图来测量每个来自于期望图的快照图是如何不同(或相似)。为了实现这些，试建立三个图，即：MCS，MCP和MCPP，包括链接的连通性概率，然后在所有超时图的距离方差中生成一个统计图表。一般而言，更高的方差得分，图就越“异常”。 随图可能生长，MCS越小，MCP作为最大图，距离方差在它们之间有一相对位置。在图12中，我们发现MCS本质上是一个阈值为1的MCCP，类似地，MCP是一个趋近于0的无限小的MCPP。 当阈值设为0.5时，MCPP的曲线更加平滑以及在19-22和26(图3中红色的高亮部分)更加精确指出需要进一步跟踪研究的网络图。

图2 大规模网络连接图

为了从预期的图中计算距离，采用基于编辑距离的思想进行距离度量。在信息理论上，编辑距离是将其中之一转换成另一个的操数。为了量化网络图的相似度，图编辑距离(GED)[2]建议用来测量拓扑的变化。图编辑距离的基本思想是修改图的相关代价以至于使它变成与其它图同构。通常有三种转换操作：插入，删除及置换。由于顶点标签置换不是有效的编辑操作，因为每个结点在企业网络中表示一个独特的主机，用户或应用程序，标签置换是一个基本的二步操作，如：移除旧的结点插入新的结点之后是更多步骤执行从一个图到另一个更大距离的置换。计算编辑距离的一个途径是从g1到MCS(g1，g2)计算删除代价，以及加上从 MCS(g1，g2)到 g2的插入代价。使用下面方程来计算在两个图之间的图编辑距离：

图3 MCS、MCP及MCPP的距离方差

如果两个图完全一样，那么分子将为0，其结果是距离为0。另一方面，如果两个图不共享一个结点或边，那么结果是其中之一的距离值。

一旦对所有成对的图计算了距离矩阵，需要绘制和可视化图相关位置。一般而言，已知点的确切位置，容易计算出它们的距离 (如：欧氏距离)。然而，按不同方式，如：已知它们成对距离，在一个2D欧几里得空间寻找它们确切的X/Y坐标不是很容易。实际上，当要确定性地在给定的n个快照图和它们成对距离矩阵的(n-1)维空间定位时，它在低维度空间可能也不可能找到确切的点。就可视化目的，维度通常仅有2D 或3D。多维度尺寸(MDS)[3，4]已提出了将高维度数据通过映射它们到低维度空间进行可视化。应用MDS模型之一，它通过映射网络图到2D空间对相关的位置进行可视化。每个结点表示一个具体日期内的一个网络图，被绘出的一条边指出超过为期一个月的演化。期望图(EG)是一个MCPP，其连接概率的阈值设为0.5。在这个可变的视图中，我们不但能看到来自预期的图(已被高亮)的网络图的距离，而且在所有网络图自身中距离变化也同样显示了出来。尽管EG位于所有图的中央，它被定位在更接近大多数图的右边，那些异常图清楚地孤立在图的左边（如图4所示）。

图4 一个可变的MDS视图的演化和相关关系

2.3 可视化的聚集图

可视化的聚集图。通常说，将聚集归类为企业内部网（内网）图的聚集和英特网（外网）聚集图。将企业内网聚集图看成图中相似结点或边的分组，外网聚集图探寻在不同时间的不同图的相似度。无论是内网还是外网聚集图，为了分组项相同，必须定义相似度的概念。由于结点是异构的，要么是主机，用户，应用程序结点，要么是文件结点。对于内网聚集图，必须在结点和外网聚集图之间利用重要的网络连接信息，任何一对图之间必须定义一个恰当的相似度尺寸。传统的聚集算法从简单的K-近临到贝叶斯聚集，到期望最大化(EM)。 除非能将结点映射到欧几里德空间，否则改变基于图的社区探测方法是必须的。

选择Walktrap算法作为随机游动的方法。 相似度测量是基于一个简单的且有效的假设，即倾向于在一个高度连接的或致密区来捕获随机游动。在图5中，属于不同簇(聚集)的结点用易于看清的不同的颜色标志。簇编号1和2是与web有关的社区，其中簇号1表示通过Firefox连接的所有外部域名，簇号2表示已经通过一群主机访问的内部的web服务。簇编号3表示7个企业用户共享一相似的目录服务(directory.nuaa.edu.cn)产生怀疑的应用集合。 巨大的簇编号4表示通过一些本地用户形成的结构合理的社区[4]。

图5 用Walktrap算法实现一个聚集视图(不同颜色表示不同聚集)

3 结论

在上下文图形中进行可视化挖掘，识别何人在何时何处做何事，简单、有效和可定制性突破的网络行为管理的局限性，智能化使得日常网络行为管理变得轻松起来。通过对可视的变化性与网络图的不变性，图的距离方差的研究，为对网络图进行可视化奠定理论基础。

[1]M.R.Garey,D.S.Johnson.Computers and Intractability:A Guide to the Theory of NP-Completeness[M].Hampshire:W.H.Freeman and Company,1979.

[2]H.Bunke,P.J.Dickinson,M.Kraetzl,W.D.Wallis,A Graph-Theoretic Approach to Enterprise Network Dynamics[M].2nd ed BirkhSuser,2007.

[3]T.F.Cox,M.Cox.MultidimensionalScaling,[M].Znd.ed.London:Boston:Chapman&Hall/CRC,2000.

[4]H.Bunke,P.Dickinson,A.Humm,C.Irniger,M.Kraetzl.Applied graph theory in computer vision and pattern recognition,Ch Graph Sequence Visualisation and its Application to Computer Network Monitoring and Abnormal Event Detection[M].Berlin:Springer,2007.

Visualizing Enterprise Network Behavior on the Context of Graph

Tao Weicheng
(School of Information Science and Technology,University of Aeronautics and Astronautics,Nanjing,210026,China;Department of Information Engineering,Wuhu Institute of Technology,Wuhu,241006,China)

In distributed network systems of enterprises,precisely identifying who is doing what is increasingly a challenge.Current management systems rely on inference of user identity,which fails to find and manage network behavior in large-scale network due to the inaccurate data.Visualization of network context including main computers,users,application programs and data access provides important help for dynamic management of network process.

Network Behavior;Visualization;Context Graph;Visualization

TP 311

A

1674-1102(2011)06-0032-03

2011-11-12

陶维成（1972-），男，安徽无为人，芜湖职业技术学院信息工程系讲师，工学硕士，研究方向为软件工程、嵌入式系统软件。

[责任编辑：曹怀火]