面向上下文圖形可視化挖掘企業網絡行為

陶維成

（南京航空航天大學 計算機科學與技術學院，江蘇 南京 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-），男，安徽無為人，蕪湖職業技術學院信息工程系講師，工學碩士，研究方向為軟件工程、嵌入式系統軟件。

[責任編輯：曹懷火]