1 引言

本文在深入分析網絡掃描軟件NMAP源碼了解其掃描原理和運行流程的基礎上，結合Tile64多核開發板強大的并行處理能力，研究提出基于多核的并行多功能掃描實現方案。方案基本思路是將掃描流程模塊化劃分，每個任務模塊由Tile64的一個內核執行，從而實現掃描過程的流水化；在此基礎上，通過建立負載均衡模塊控制調度多條流水線，實現多條流水線并行掃描。

2 NMAP

NMAP是一個網絡探測和安全掃描程序，使用NMAP可以掃描大型網絡，獲取任意主機正在運行以及提供服務的信息。NMAP支持很多掃描技術，例如：UDP、TCP connect()、TCP SYN(半開掃描)、ftp代理(bounce攻擊)、反向標志掃描、ICMP掃描、FIN掃描、ACK掃描、圣誕樹(Xmas Tree)、SYN掃描和null掃描。它還提供了一些高級的功能，例如通過TCP/IP協議棧特征探測操作系統類型，秘密掃描，通過ping掃描探測關閉的主機，誘餌掃描，避開端口過濾檢測，直接RPC掃描、碎片掃描以及靈活的目標和端口設置功能。NMAP主要掃描功能可以分為四類。

第一，主機發現掃描。主機發現掃描也稱為ping掃描，NMAP的功能遠遠超過ping命令的功能，它可以將TPC SYN/ACK、UDP和ICMP等數據包任意組合起來發送，以探測目標主機是否是活動的。　第二，端口掃描。NMAP提供了多種端口掃描技術，探測端口的狀態。例如上面提到的：UDP、TCP connect()、TCP SYN(半開掃描)、ftp代理(bounce攻擊)、反向標志、ICMP、FIN、ACK掃描、圣誕樹(Xmas Tree)、SYN掃描和null掃描等。防火墻等網絡隔離設備使得對網絡的探測變得更加困難，簡單的搜索不再有效，NMAP提供了很多功能用于探測復雜的網絡，并且檢驗過濾設備是否正常工作。此外，NMAP還提供了繞過某些較弱的防范機制的手段。

第三，服務和版本探測。探測目標主機端口運行的服務，NMAP自建包括大約2,200個著名服務組成的NMAP-services數據庫，通過對遠程機器端口的探測，報告使用者哪些端口對應于郵件服務器 (SMTP)，哪些端口對應Web服務器(HTTP)或域名服務器(DNS)。

第四，操作系統探測。NMAP最著名的功能之一，使用TCP/IP協議棧fingerprinting進行遠程操作系統探測。NMAP向目標主機發送一系列TCP和UDP報文，并檢查響應中的每一比特。在進行多項測試如TCP ISN采樣、TCP選項支持和排序、IPID采樣和初始窗口大小檢查之后，NMAP把結果和數據庫NMAP-os-fingerprints中超過1500個已知的操作系統的fingerprints進行比較，查找匹配操作系統。如果匹配上，就打印出該操作系統的信息。每個fingerprint包括一個關于OS的描述文本和一個分類信息，包括供應商名稱(如Sun)，旗下的操作系統(如Solaris)、OS版本(如10)和設備類型(如通用設備、路由器、Switch、游戲平臺等)。#p#

3 Tile64多核開發板

2004年，麻省理工學院（MIT）的阿南特·阿加瓦爾（Anant Agarwal）教授創辦了Tilera公司。2007年，該公司推出了一款帶有64個可編程內核、90nm工藝的RISC處理器——Tile64。與英特爾和AMD采用的前端總線架構不同，Tile64處理器內核之間采用的是一種“網狀”架構（MESH）進行數據交換，有些類似于AMD HyperTransport總線的點對點架構，并集成了4個DDR2內存控制器，分布在核心陣列的周圍。Tile64的64個核心排成8×8的陣列，每個核心由有一個計算單元、一個緩存單元和一個交換單元組成，這些交換單元構成了一個名為iMesh的mesh網絡。

每個處理器核是完整的處理器，包括共5MB的L1和L2高速緩存，連接核和網絡的無阻塞開關，使得每個處理器核能運行完整操作系統，或多個處理器核一起運行多處理器操作系統SMP Linux。Tlie64工作頻率500MHz - 866MHz，每秒可達4430億次運算（443BOPS）。這些內核通常稱為tile，在處理器外擴展了一些常用外部接口如Gbe交換器，每個tile都可以自由的與外部接口通信。

4 NMAP代碼分析

4.1 掃描流程分析

通過對NMAP源碼的分析，得出NMAP主要運行流程分為三部分。第一部分初始化，在這個階段NMAP主要解析用戶輸入的命令及參數，并判斷其是否有誤。根據用戶輸入的命令設置NMAP掃描參數，如掃描延時，日志記錄，設置傀儡主機等。第二部分掃描，NMAP所有功能均在此階段完成，如端口掃描、操作系統掃描等，當完成掃描后，輸出掃描結果。第三部分是最后階段，主要工作是釋放系統資源。

NMAP第二部分掃描，主要在NMAP.cc文件中的NMAP_main中的第1603行至1868行完成。這部分開始時，首先設置一些基本信息為后面的掃描做準備，如DNS解析，路由設置，如果不是主機發現掃描，還需執行ping掃描，判斷目標主機是否開機。當準備工作完成后，開始發送探測進行掃描。根據用戶輸入的命令，NMAP執行相應的掃描。NMAP只允許輸入一種類型的探測，只有少數端口掃描允許輸入兩種端口掃描類型。具體NMAP掃描流程，先判斷是否為用戶所輸入的類型，如果不是繼續判斷下一個類型。直到找到匹配的類型，完成相應的探測功能。

NMAP中大部分端口掃描功能都是在函數ultra_scan中完成的，它根據掃瞄類型對目的主機的端口發送相應的探測，并通過截取目的主機返回的數據包來分析主機與端口的狀態，其函數的原型為void ultra_scan（vector &Targets, struct scan_lists *ports, stype scantype, struct timeout_info *to）參數具體如下：

Targets： 要掃描的目標主機，可以是一臺或多臺，Target是一個在Target.h中定義的類。這個類封裝了一些NMAP掃描所需要的目標主機的信息。

ports： 所要掃描的端口列表。

scantype： 掃描類型。

to： 超時信息，可以默認。

Ultra_scan可以完成10類型的掃描。

在NMAP.cc文件的第1744行至1772行可以看出，這十種掃描也是順序執行的。

NMAP進行多目標主機多端口掃描時的順序如下：先固定一個端口號，然后給所有目標主機的這個端口號發送同一掃描類型的數據包；發送完畢后再固定另一個端口號，給所有目標主機發送數據包，直到遍歷到每個端口號。

NMAP所有掃描的底層工作模式基本相同，可歸納為四步。

（1）組裝數據包。根據用戶的輸入的掃描類型，目標主機及端口，組裝合適的數據包。

（2）發包。在windows下，調用libdnet函數庫中的函數eth_send進行發包。在Linux下，調用sendto發包。（3）收包。調用pcap函數庫中的函數pcap_next進行抓包。

（4）最后對目標主機返回的數據包進行分析，得出結論。#p#

4.2 NMAP的局限性

NMAP的功能全面而強大，設計者也采用多種算法以提高NMAP運行速度，如在idle_scan中采用遞歸調用的算法，以加速NMAP掃描速度。但是NMAP自身還存在著缺陷，主要有兩點。

第一，NMAP只能運行在一臺主機上的，還沒分布式的設計。如果一個管理員需要維護一個大型的網絡時，需要掃描大量的主機及多個端口時，NMAP需要大量時間來運行。因為每次NMAP只能對一臺主機的一個端口發送數據包，當目標主機增多時，NMAP發送一組數據包，然后等待所有目標主機的響應，當有數據包后才能對數據包進行分析，所以每次對一定數量的端口掃描完后，才能進行下一次掃描、組包、發包等工作。時間消耗在等待對方返回數據包到再次組包之間。

第二，NMAP不允許同時對不同主機進行不同類型的掃描。例如參數：-sS，表示使用SYN 端口掃描方式；-O，表示運行操作系統掃描。輸入掃描命令：NMAP ╞sS hostname1 ╞O hostname2是不允許的。

5 設計思路

設計一個高效的并行程序并非易事，本文并行設計采用PCAM 算法。PCAM算法的過程分為四步：即任務劃分（Partitioning）、通信（Communication）分析、任務組合（Agglomeration）和處理器映射（Mapping）。它反映了并行算法設計的自然過程，其首先盡量開拓算法的并發性和滿足計算的可拓放性，然后著重優化算法的通信成本和全局執行時間。同時，通過必要的整個過程的反復回溯，以期最終達到一個滿意的設計。

PCAM設計方法的四個階段。

（1）劃分：將整個計算分解為一些小的任務，以便盡可能的挖掘并行計算的機會。

（2）通信：確定各任務在執行過程中所需要交換的數據并協調各任務的執行，同時可以檢驗任務劃分的合理性。

（3）組合：根據性能要求和實現的代價來考察前兩步的結果，必要時可將一些小的任務組合成略大的任務，以減少通信開銷或提高性能。

（4）映射：將每個任務分配到一個處理器上，其目的是最小化全局執行時間和通信成本以及最大化處理器的利用率。

PCAM算法提供了一種針對一個任務如何實現并行處理的設計思想，本文的設計思路也遵循此設計思想，有幾個步驟。

第一，流水線設計。將NMAP的掃描過程分成幾個功能獨立的模塊，每個模塊完成自己的工作，并將運行結果傳遞給下一個模塊。每個功能模塊由Tile64開發板上的一個tile負責運行，不同模塊之間通過Tile64提供的tile間通信機制進行通信。根據NMAP掃描流程的模塊化劃分，配置相應的tile，組成一條完整的掃描流水線。流水線模式不提升任何單個進程或線程的性能，但是可以提高整個系統的性能。

第二，并行設計。在流水線前增加一個調度模塊，實現多條流水線的控制，同時負責解析復雜命令行和均衡負載等工作。NMAP一共有16種掃描功能，每種掃描功能可分成獨立的模塊，通過往Tile64上的移植修改可將不同模塊改為并列關系，通過調度模塊對包含多種掃描指令的復雜命令行進行解析，將不同掃描指令分配給不同流水線執行，即可實現多種掃描功能的并行執行，即可解決NMAP不能同時進行多種類型掃描的問題。通過對用戶輸入的主機數量和端口數量進行分析，可以將大量的主機端口掃描任務拆分成多個小任務，通過調度模塊可將命令行中目標主機的數量和端口的數量進行統計，平均分給每條流水線，即可實現多流水線并行掃描。#p#

5.1 流水線設計

NMAP一次掃描的主要過程可分為四個步驟：組包、發包、收包、分析，且四個步驟是順序執行的，固可將NMAP掃描過程的流水設計為6個獨立的模塊，除了組包、發包、收包、分析之外，在流水線前后分別加入命令行解析模塊和結論輸出模塊。

NMAP流水掃描工作步驟。

每個模塊起一個進程，由一個tile運行。每個進程只負責自己的工作，與其他進程沒有沖突。

第一個tile負責對用戶輸入命令進行解析。獲得用戶輸入的探測類型、目的主機、目的端口、掃描參數等信息。并將關鍵信息（探測類型、目的主機、目標端口）傳遞給第二個tile。

第二個tile根據所接收到得信息組裝正確的數據包，并將數據包傳給第三個tile。

第三個tile負責網卡發包，并通知第四個tile接收返回數據包。

第四個tile負責抓包，并判斷所抓的數據包是否為所需的數據包。如果是則將包送給下一個tile；如果不是則丟棄。

第五個tile對數據包進行分析，找出關鍵信息并將信息傳遞給第六個tile。

第六個tile負責保存結果，對之前收到一組相關信息進行總結都得出結論并輸出。

5.2 流水線與單核運行比較

單核運行NAMP在多次收發的過程中，當組包后，必須等到收到返回數據包才能進行下一次組包。當采用多核流水線模式后，由于每個tile獨立運行，當組包完成后，進行發包，第二個tile不用等待收包完畢，就可以繼續進行下一次組包。同理，當第三個tile發包完后也可以繼續發送下個數據包。

為了更方便地描述多核程序計算的性能，一般采用加速比指標來進行度量。加速比定義為：

S(n) = 單處理器上最優串行化算法計算時間 / 使用n個處理器并行計算時間加速比通常都小于CPU核數，只有極少數并行算法可以或得超線性加速比，如并行順序搜索。因此，加速比一般要求向CPU核數靠近；加速比越大，程序性能越好。

假設每個核運行一次用時相同，設為t，則發送n個數據包，單處理器上運行NMAP的時間為：4nt +2t。在流水線模式下運行時間為：(n-1)t + 4t + 2t。S(n) = 4nt +2t / (n-1)t + 4t + 2t = 4n +2 / n + 5，當n→∞時，S(n) = 4。5.3 并行設計

Tile64開發板的64個tile，6個網口，為多條流水線并行運行提供了必要的硬件條件。多流水線并行設計是在單流水線設計的基礎上，對組包、發包、收包、分析等四個主要提高掃描性能的模塊實施了并行化，由調度模塊負責并行掃描命令的解析和流水線控制。

理論上，該設計可以使用62個tile，其中命令行解析和結論各用一個tile，每條流水線用4個tile，最大可以建立15條流水線。調度模塊負責接受用戶的指令，解析指令，并實現負載均衡。

由于NMAP指令輸入方式存在局限性，需要對指令進行修改，以滿足多種掃描指令同時輸入的需求。可將用戶輸入命令中的目標主機、端口和掃描類型，設定為一組參數傳遞給每條流水線的組包進程，參數為一個成員相同、長度固定的結構體，結構體的元素如表2所示。

每個元素也為一個結構體，通過該元素確定掃描目標為一臺或一組主機的一個或一組端口，以及掃描的類型。通過使用結構體命令行可以解決NMAP不能同時輸入多種掃描指令的問題，同時也使調度模塊更容易計算掃描任務的工作量，便于進行負載的分配。假設掃描的主機數量為X，端口數量為Y，掃描類型的發包次數為Z（不同掃描類型收發包次數不同），則總的掃描次數為N = X * Y * Z。如果N = 15，則理論上多流水線并行掃描消耗時間將與N = 1時相同。#p#

5.3 負載平衡

在單核CPU中運行，不需要考慮負載平衡問題。而在多核CPU中，必須考慮各個線程計算量均衡地分配到各CPU核上的問題，也就是計算負載平衡問題。如果線程間的計算量無法取得好的負載平衡，那么某些CPU和計算量大、耗時多，另外一些CPU計算量小、耗時少；耗時少的CPU和運行完成后，將處于空閑狀態，出現CPU饑餓現象。

如果CPU核間負載不均衡，對加速比指標的影響也很大，舉例如下：

假設一個4核CPU系統中有4個任務，各個任務耗時分別為20ms、5ms、3ms、2ms。

S(n) = (20+5+3+2) / 20 =1.5

多核CPU效率=S(n) / CPU核數 = 1.5 / 4 = 37.5%

如果將各個任務的時間調整為10ms、8ms、6ms、6ms，那么加速比將變成

S(n) = (10+8+6+6) / 10 = 3

對應的多核CPU效率將變成75%，效率增加一倍。可見，CPU核間負載不均衡對加速比的影響很大。

發包和收包消耗的時間最長，其不可再分成更小的任務。在操作系統掃描中，分析模塊也占有很大工作量，所以將NMAP掃描流程盡量分成任務量接近的單獨任務，以提高負載均衡度。

一條流水線包括組包、發包、收包、分析當做一個負載，設耗時為T，命令行解析和結論耗時分別設為t。當運行時間為T+2t時，流水線完成一次掃描，理論上最多能完成15次掃描。

S(n) = (2t + 15T) / (T + 2t)，當T遠大于t時，S(n) = 15。

5.4 面臨問題

調度模塊在整個系統中占有重要地位，其負載均衡功能是保障系統高效運行的關鍵。本文在考慮平衡負載時沒有對每個任務的運行時間進行嚴格精確地測量，只是憑個人使用經驗對任務進行劃分。下一步將強化調度模塊負載均衡功能的設計，對每種掃描任務進行評估，重新劃分任務，使每個內核的負載盡可能達到均衡。

其次，雖然并行掃描可以實現多類型、多端口、多主機的并行掃描，但是由于掃描類型的不同，所消耗的時間也不同。下一步將對每種掃描的負載進行測量，并深入每種掃描模式的內部，根據掃描內部運行負載重新劃分任務，將負載較重的任務再劃分為多個并行的進程，進一步提高掃描速度。比如對操作系統掃描過程進行分解，將指紋匹配過程分解為多個進程并行運行。

6 結論

本文研究提出了基于多核的NMAP并行掃描設計方案。基于對高速網絡掃描的需求，將NMAP整體掃描流程分成多個獨立的模塊，并設計提出流水線的掃描方式，通過流水設計減少每次等待目標主機返回數據包到再次組包之間所消耗的時間，并在此基礎上，提出多流水線并行掃描設計，進一步提高NMAP的掃描速度，改進NMAP的不足。文章最后推導了并行設計方案的理論加速比。本文中NMAP并行掃描的設計思想在863計劃“密碼算法和安全協議自動化檢測工具開發及測評系統”中得到了應用，效果良好。