利用區(qū)間管理算法實(shí)現(xiàn)的TCP流重組技術(shù)*

俞祥基，蒲俊良，周 川，張隆春，唐 林，陳巧靈

（成都深思科技有限公司，四川 成都 610095）

0 引言

近年來(lái)，隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)安全也愈加被人們所重視，許多行業(yè)領(lǐng)域都需要對(duì)網(wǎng)關(guān)出口的流量數(shù)據(jù)進(jìn)行嗅探捕獲，并針對(duì)其進(jìn)行流量審計(jì)，從而確保數(shù)據(jù)安全。在審計(jì)過(guò)程中，都會(huì)采用傳輸控制協(xié)議（Transport Control Protocol，TCP）流重組技術(shù)，只有將TCP流數(shù)據(jù)報(bào)文重組以后，才能還原完整的TCP會(huì)話，從而獲取TCP傳輸?shù)恼鎸?shí)內(nèi)容，用于流量審計(jì)。當(dāng)在網(wǎng)絡(luò)中使用TCP協(xié)議進(jìn)行數(shù)據(jù)傳輸時(shí)，需要將完整的數(shù)據(jù)內(nèi)容拆分成多個(gè)數(shù)據(jù)報(bào)文進(jìn)行傳輸。由于網(wǎng)絡(luò)環(huán)境的復(fù)雜性較高，比如網(wǎng)絡(luò)設(shè)備參差不齊、信號(hào)傳輸過(guò)程存在衰減和干擾等，經(jīng)常會(huì)導(dǎo)致TCP數(shù)據(jù)報(bào)文亂序或丟包重傳等，因此嗅探重組TCP流就需要考慮TCP數(shù)據(jù)報(bào)文的亂序、重疊、丟包、重傳等許多復(fù)雜情況。而現(xiàn)有的TCP流重組技術(shù)大都存在效率低下、重組不完整、程序內(nèi)存占用過(guò)高等問(wèn)題。

本文針對(duì)上述情況，研究了TCP流重組技術(shù)，旨在提供一種穩(wěn)定且準(zhǔn)確、高效且快速的TCP流重組技術(shù)，為后續(xù)的網(wǎng)絡(luò)數(shù)據(jù)安全審計(jì)提供有力的技術(shù)支撐。該技術(shù)具有一定的工程應(yīng)用價(jià)值。

1 分片重組技術(shù)研究現(xiàn)狀

TCP是目前Internet中廣泛采用的一種傳輸協(xié)議，是一種面向連接的、可靠的、基于字節(jié)流的通信協(xié)議，它為各個(gè)主機(jī)之間提供可靠、按序傳輸、端到端的數(shù)據(jù)包傳輸服務(wù)。TCP協(xié)議發(fā)出的每一個(gè)數(shù)據(jù)包都要求確認(rèn)，其中如果有一個(gè)數(shù)據(jù)包丟失就收不到確認(rèn)，發(fā)送方就必須重發(fā)這個(gè)數(shù)據(jù)包。為了保證傳輸?shù)目煽啃?，TCP協(xié)議建立了3次對(duì)話的確認(rèn)機(jī)制，即必須先與對(duì)方建立可靠連接才能正式發(fā)送數(shù)據(jù)。TCP的數(shù)據(jù)包沒(méi)有長(zhǎng)度限制，理論上可以無(wú)限長(zhǎng)，但為了保證網(wǎng)絡(luò)效率，通常都會(huì)將TCP數(shù)據(jù)包依照TCP/IP模型中傳輸數(shù)據(jù)時(shí)所能使用的最大傳輸單元（Maximum Transmission Unit，MTU）進(jìn)行分片，以太網(wǎng)的MTU默認(rèn)是1 500，即一個(gè)TCP數(shù)據(jù)報(bào)文默認(rèn)長(zhǎng)度均為1 500。由于TCP協(xié)議具有重發(fā)與分片特點(diǎn)，結(jié)合網(wǎng)絡(luò)空間的延時(shí)、信號(hào)衰減等實(shí)際情況，導(dǎo)致現(xiàn)有TCP流分片重組技術(shù)實(shí)際的局限性。

早期的分片重組技術(shù)主要通過(guò)高性能的硬件堆高計(jì)算性能，從而實(shí)現(xiàn)高速的TCP流重組，但在目前網(wǎng)絡(luò)流量呈指數(shù)級(jí)增長(zhǎng)的情況下，再通過(guò)獨(dú)立的高性能硬件達(dá)到TCP重組性能要求，成本實(shí)在過(guò)于高昂且低效。目前主流的分片重組技術(shù)研究，大多是考慮硬件與軟件相結(jié)合，以及提高軟件算法在TCP流重組技術(shù)中的占比，主要應(yīng)用在為CPU減負(fù)、流量重組、提高重組效率等場(chǎng)景。

2012年，王文豪[1]等人提出了一種基于現(xiàn)場(chǎng)可編程邏輯陣列（Field Programmable Gate Array，F(xiàn)PGA）的IP分片重組技術(shù)，目標(biāo)是減輕CPU負(fù)擔(dān)，提高重組效率。文中采用中央地址存儲(chǔ)器（Central Address Memory，CAM）來(lái)設(shè)計(jì)和擔(dān)當(dāng)IP分片重組的信息識(shí)別核心模塊，并追加片外大容量隨機(jī)動(dòng)態(tài)存儲(chǔ)器來(lái)實(shí)現(xiàn)IP分片的數(shù)據(jù)緩存，最終實(shí)現(xiàn)IP分片報(bào)文的快速識(shí)別及有效重組。該技術(shù)可以應(yīng)用于亂序、重復(fù)等異常場(chǎng)景，其處理數(shù)據(jù)的效率為1 Gbit/s以上。使用CAM作為運(yùn)算核心，雖然具有查找速度快的優(yōu)點(diǎn)，但是其硬件資源消耗很高，無(wú)法持續(xù)支撐大數(shù)量的IP分片信息存儲(chǔ)、查詢等，在持續(xù)運(yùn)行大數(shù)量IP分片重組時(shí)，會(huì)導(dǎo)致系統(tǒng)的資源緊張，進(jìn)而影響處理能力，造成IP分片重組失敗，甚至系統(tǒng)崩潰。

2014年，竇衍旭[2]提出了一種基于哈希表對(duì)高速網(wǎng)絡(luò)中的IP分片進(jìn)行重組的技術(shù)，主要用于高速網(wǎng)絡(luò)中的流量嗅探還原。該文中先將由源IP地址、源端口、目的IP地址、目的端口組成的4元組作為關(guān)鍵字構(gòu)建了具有高速查詢效率的哈希表，并通過(guò)TCP超時(shí)檢測(cè)機(jī)制提升了哈希表查詢的穩(wěn)定性及效率性，實(shí)現(xiàn)了IP分片的快速查詢管理，再進(jìn)行具體的流重組操作，最終實(shí)現(xiàn)了1 Gbit/s流量下的IP分片重組。然而，由于沒(méi)有對(duì)網(wǎng)絡(luò)環(huán)境中存在的丟包重發(fā)情況進(jìn)行深入研究處理，其重組的準(zhǔn)確率受到嚴(yán)重影響，只有68%。

2016年，劉賢熜[3]采用了一種MapReduce編程模式的并行結(jié)構(gòu)對(duì)流量進(jìn)行分析和統(tǒng)計(jì)，對(duì)TCP報(bào)文按照關(guān)鍵4元組信息完成輔助排序與分類(lèi)，再基于Hadoop進(jìn)行數(shù)據(jù)報(bào)文的大量并行處理。該文中利用滑動(dòng)窗口來(lái)尋找相鄰兩個(gè)數(shù)據(jù)包的時(shí)間戳，實(shí)現(xiàn)數(shù)據(jù)報(bào)文的定位及分割；利用分布式設(shè)備不受單機(jī)設(shè)備計(jì)算瓶頸影響的特點(diǎn)，實(shí)現(xiàn)TCP數(shù)據(jù)包的高效重組。

2016年，許青林[4]通過(guò)基于三維立體空間的重組算法優(yōu)化重組流程，引入多級(jí)雙循環(huán)緩沖隊(duì)列提高重組效率，并利用自適應(yīng)動(dòng)態(tài)哈希內(nèi)存池進(jìn)行緩存映射，去除數(shù)據(jù)報(bào)文在排序重組過(guò)程中的多次拷貝轉(zhuǎn)移過(guò)程，最終實(shí)現(xiàn)了900 Mbit/s流量的TCP報(bào)文重組。

2018年，趙勇[5]提出了結(jié)合Hash表的分段管理與伸展樹(shù)算法的TCP流排序重組算法。該文優(yōu)化了分片排序重組過(guò)程中5元組的快速查找性能，并結(jié)合TCP狀態(tài)機(jī)的約簡(jiǎn)策略，迅速地將數(shù)據(jù)報(bào)文的重組速率提升到了2 Gbit/s，但其在面對(duì)并發(fā)數(shù)量多、分片數(shù)量多的場(chǎng)景時(shí)，性能快速下降。利用TCP狀態(tài)機(jī)的研究還有2019年由程子帥[6]提出的并行TCP雙向數(shù)據(jù)流重組技術(shù)，其通過(guò)優(yōu)化TCP狀態(tài)機(jī)生成TCP的值，適用于數(shù)據(jù)報(bào)文亂序、重發(fā)等異常情況下的TCP報(bào)文重組。

2020年，黃銳[7]提出了一種基于FPGA實(shí)現(xiàn)的TCP亂序報(bào)文重組辦法，利用硬件實(shí)現(xiàn)底層TCP/IP協(xié)議棧，解放了CPU的計(jì)算性能，可以解決網(wǎng)絡(luò)中網(wǎng)絡(luò)堵塞或傳輸誤碼造成的數(shù)據(jù)報(bào)文丟失，多路由轉(zhuǎn)發(fā)導(dǎo)致的數(shù)據(jù)報(bào)文亂序等異常情況。文中充分利用硬件特點(diǎn)來(lái)記錄數(shù)據(jù)報(bào)文的偏移信息，在緩存中比較排序重組。該方法資源占用低且非常有效，但同樣受限于硬件特點(diǎn)，最大只能支持3個(gè)分段的數(shù)據(jù)并發(fā)重組，無(wú)法用于并發(fā)重組數(shù)量較多的場(chǎng)景。

綜上所述，目前主流的分片重組技術(shù)已經(jīng)較為成熟，但是其技術(shù)特性都不夠全面，無(wú)法滿足高速率、復(fù)雜場(chǎng)景下的高并發(fā)需求，因此TCP分片重組技術(shù)仍然具有一定的改進(jìn)空間。

2 基于平衡樹(shù)算法拓展的區(qū)間管理算法

平衡樹(shù)（Balance Tree，BT）算法指的是在一棵樹(shù)中，其任意節(jié)點(diǎn)的子樹(shù)的高度差都小于或等于1。平衡樹(shù)由2-3樹(shù)改造而來(lái)，它的時(shí)間復(fù)雜度和空間復(fù)雜度都比2-3樹(shù)要低，并在實(shí)現(xiàn)對(duì)集合的并、交、差等系列操作時(shí)可以始終保持平衡，提升存儲(chǔ)空間的利用率。

2.1 現(xiàn)有拓展算法

2.1.1 二叉平衡搜索樹(shù)

二叉平衡樹(shù)，又稱為AVL樹(shù)，是符合平衡樹(shù)特征的一種特殊的二叉排序樹(shù)。它可以是空樹(shù)，當(dāng)不是空樹(shù)時(shí)，每一個(gè)節(jié)點(diǎn)的左右兩子樹(shù)都是平衡二叉樹(shù)，且子樹(shù)高度之差的絕對(duì)值不超過(guò)1。

二叉排序樹(shù)支持快速地插入、刪除、查找操作，各個(gè)操作的完成時(shí)間都在O(logn)以內(nèi)，O(logn)也稱為時(shí)間復(fù)雜度，其中，O是和樹(shù)的高度成正比的。但是，在頻繁的插入、查詢過(guò)程中，二叉排序樹(shù)不斷更新，可能會(huì)出現(xiàn)樹(shù)的高度遠(yuǎn)大于logn的情況，導(dǎo)致樹(shù)退化成鏈表，時(shí)間復(fù)雜度也變成了O(n)。為了避免這種復(fù)雜度退化的問(wèn)題，二叉平衡樹(shù)被提出。二叉平衡樹(shù)讓樹(shù)盡量保持左右平衡，提升插入、查找、刪除的效率，并引入節(jié)點(diǎn)平衡因子（Balance Factor，BF），使得左子樹(shù)的高度減去右子樹(shù)的高度的絕對(duì)值小于等于1。圖1給出了一個(gè)平衡的二叉平衡樹(shù)的示例。

圖1 二叉平衡樹(shù)

二叉平衡樹(shù)在插入或者刪除節(jié)點(diǎn)時(shí)，可能打破樹(shù)的平衡，而通過(guò)左旋與右旋兩種選擇操作，就可以使樹(shù)恢復(fù)平衡。例如插入一個(gè)新節(jié)點(diǎn)到根節(jié)點(diǎn)的左子樹(shù)的左子樹(shù)，導(dǎo)致根節(jié)點(diǎn)的平衡因子變成2，就可以進(jìn)行右旋操作使樹(shù)恢復(fù)平衡，如圖2所示。

圖2 二叉平衡樹(shù)右旋

通過(guò)左、右兩種基本旋轉(zhuǎn)的互相組合，結(jié)合遞歸算法的思想，不斷重復(fù)進(jìn)行左旋或右旋，最終即可盡量保持二叉平衡樹(shù)的平衡結(jié)構(gòu)[8]。

2.1.2 多路平衡搜索樹(shù)

從上文介紹的二叉平衡樹(shù)的內(nèi)容可以看出，二叉平衡樹(shù)每一個(gè)節(jié)點(diǎn)最多只能保存一個(gè)關(guān)鍵字和兩個(gè)子節(jié)點(diǎn)，在維護(hù)過(guò)程中還會(huì)進(jìn)行大量的磁盤(pán)尋址和讀寫(xiě)操作。為了在同一個(gè)節(jié)點(diǎn)內(nèi)能夠存儲(chǔ)更多的信息，減少磁盤(pán)尋址的次數(shù)，增強(qiáng)數(shù)據(jù)的查詢性能，多路平衡搜索樹(shù)被提出。它突破了二叉平衡樹(shù)每個(gè)節(jié)點(diǎn)只能保存1個(gè)關(guān)鍵字和2個(gè)子節(jié)點(diǎn)的限制，并引出了如2-3樹(shù)、2-3-4樹(shù)、B樹(shù)等多種多路平衡搜索樹(shù)[9]。

B樹(shù)是多路平衡搜索樹(shù)中最為典型的一種，它的操作時(shí)間復(fù)雜度同為O(logn)。一棵B樹(shù)有以下性質(zhì)：

（1）根節(jié)點(diǎn)中最多有m棵子樹(shù)，有x(0≤x≤m)棵子樹(shù)Pi(1≤i≤m)和m-1個(gè)關(guān)鍵字Ki(1≤i≤m)；

（2）一個(gè)節(jié)點(diǎn)中的所有關(guān)鍵字Ki(1≤i≤m)，滿足Ki＜Ki+1，子樹(shù)Pi中的所有關(guān)鍵字都大于Ki-1，小于Ki；

（3）根節(jié)點(diǎn)至少有一個(gè)關(guān)鍵字及兩個(gè)子節(jié)點(diǎn)，除根結(jié)點(diǎn)外的所有非終端結(jié)點(diǎn)至少有m/2棵子樹(shù)；

（4）所有內(nèi)部節(jié)點(diǎn)至少有t個(gè)子節(jié)點(diǎn)，最多有2t個(gè)子節(jié)點(diǎn)，至少有t-1個(gè)關(guān)鍵字，最多有2t-1個(gè)關(guān)鍵字；

（5）所有的葉子節(jié)點(diǎn)都在同一層，子葉節(jié)點(diǎn)不包含任何信息。

圖3給出了一棵3階B樹(shù)的示例。

圖3 3階B樹(shù)

在B樹(shù)的實(shí)際操作中，對(duì)于葉節(jié)點(diǎn)已經(jīng)寫(xiě)滿的情況，引入了分裂操作，它可以將該葉節(jié)點(diǎn)分裂，把中間的關(guān)鍵字升至父節(jié)點(diǎn)的正確位置，保證B樹(shù)的插入操作不會(huì)導(dǎo)致B樹(shù)不合法，如圖4所示。此外，刪除操作也引入了向上回溯來(lái)保證B樹(shù)對(duì)于結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量的限制。

圖4 B樹(shù)插入分裂

2.2 拓展區(qū)間管理算法

多路平衡搜索樹(shù)的一個(gè)重要思想是擴(kuò)展了二叉平衡樹(shù)1個(gè)節(jié)點(diǎn)只能保存1個(gè)關(guān)鍵字和2個(gè)子節(jié)點(diǎn)的概念。根據(jù)這個(gè)思想，本文嘗試將這個(gè)概念再次進(jìn)行擴(kuò)展，提出了區(qū)間管理算法。將TCP流報(bào)文中元素的動(dòng)態(tài)集合，即報(bào)文分片，作為要保存的關(guān)鍵信息，在平衡樹(shù)基礎(chǔ)上進(jìn)行擴(kuò)展得到支持以區(qū)間為元素的動(dòng)態(tài)集合的操作，其中每個(gè)節(jié)點(diǎn)的關(guān)鍵值是區(qū)間的左端點(diǎn)。通過(guò)建立這種特定的結(jié)構(gòu)，使區(qū)間元素的查找和插入都可以在O(logn)的時(shí)間內(nèi)完成，該算法的具體流程如圖5所示。

圖5 區(qū)間管理算法

每一個(gè)節(jié)點(diǎn)代表一個(gè)報(bào)文，節(jié)點(diǎn)區(qū)間的左右值分別為報(bào)文的序列號(hào)（seq）和序列號(hào)+當(dāng)前報(bào)文長(zhǎng)度（len）-1，比如數(shù)據(jù)報(bào)文seq為1，len為100，此數(shù)據(jù)報(bào)文對(duì)應(yīng)的節(jié)點(diǎn)的區(qū)間為[1,100]。

區(qū)間管理算法和TCP協(xié)議自身的確認(rèn)應(yīng)答機(jī)制（Acknowledge character，ACK）非常搭配。ACK包確認(rèn)機(jī)制是對(duì)接收到的數(shù)據(jù)進(jìn)行確認(rèn)，在發(fā)送端一次性發(fā)送多個(gè)數(shù)據(jù)報(bào)文時(shí)，如201、301、401的數(shù)據(jù)報(bào)文，不必等到接收端的一一確認(rèn)，只需要知道401的確認(rèn)報(bào)文，即可認(rèn)為201、301、401報(bào)文都接收到了。序列號(hào)包確認(rèn)機(jī)制是當(dāng)發(fā)送端一次性發(fā)生多個(gè)數(shù)據(jù)報(bào)文時(shí)，如201、301的數(shù)據(jù)報(bào)文，接收端的ACK暫未到來(lái)，若201數(shù)據(jù)報(bào)文的序列號(hào)加上當(dāng)前報(bào)文長(zhǎng)度等于301數(shù)據(jù)報(bào)文的序列號(hào)，則可以判斷301即為201后面連續(xù)的包。通過(guò)將ACK機(jī)制確認(rèn)后的TCP分片報(bào)文直接作為區(qū)間管理算法節(jié)點(diǎn)中的保存數(shù)據(jù)，可以大幅提升數(shù)據(jù)的查詢效率，尤其針對(duì)亂序、丟包等異常的TCP流分片。

3 利用區(qū)間管理算法實(shí)現(xiàn)TCP流重組

3.1 TCP流量采集與預(yù)處理

本文主要研究的是TCP流的重組技術(shù)，但通過(guò)網(wǎng)絡(luò)出口直接嗅探到的流量報(bào)文是不能直接投入流重組系統(tǒng)中的。因此，需要從網(wǎng)絡(luò)出口盡量獲取高完整性、高可靠性的流量，快速準(zhǔn)確地分離出其中的TCP流報(bào)文，并將需要重組的報(bào)文進(jìn)行高效的篩選緩存，排除其中無(wú)效和重復(fù)的報(bào)文，再投入流重組系統(tǒng)中進(jìn)行TCP流重組，最終輸出重組后完整的TCP報(bào)文。

3.1.1 TCP流采集

在網(wǎng)絡(luò)空間中，如流量分析、網(wǎng)絡(luò)狀態(tài)分析等很多功能都依賴于獲取的網(wǎng)絡(luò)基礎(chǔ)流量，因此網(wǎng)絡(luò)流量采集技術(shù)一直在不斷發(fā)展，從以前的基于偵聽(tīng)網(wǎng)絡(luò)數(shù)據(jù)包的采集技術(shù)、基于網(wǎng)絡(luò)探針的流量采集技術(shù)、基于PF_ING框架的高性能數(shù)據(jù)包流量監(jiān)測(cè)及處理技術(shù)，到近些年流行的基于數(shù)據(jù)平面開(kāi)發(fā)套件（Data Plane Development Kit，DPDK）框架的高速流量采集技術(shù)，高效獲取網(wǎng)絡(luò)空間流量不再是難以達(dá)到的目標(biāo)。

基于偵聽(tīng)網(wǎng)絡(luò)數(shù)據(jù)包的數(shù)據(jù)包采集技術(shù)[10]具體是通過(guò)將網(wǎng)卡模式設(shè)置為“混雜”模式，使得處于共享介質(zhì)網(wǎng)絡(luò)上的任何流經(jīng)該網(wǎng)卡的數(shù)據(jù)包都可以被偵聽(tīng)到，但該模式難以保證偵聽(tīng)數(shù)據(jù)的完整性。

基于網(wǎng)絡(luò)探針的流量采集技術(shù)利用了Ethernet總線結(jié)構(gòu)的思想，以IP為單位，將網(wǎng)絡(luò)監(jiān)聽(tīng)程序安裝到待監(jiān)聽(tīng)設(shè)備上，詳細(xì)記錄該設(shè)備的每一次的通信，再根據(jù)IP進(jìn)行數(shù)據(jù)匯總統(tǒng)計(jì)，但此方法對(duì)流量統(tǒng)計(jì)的核心設(shè)備要求極高，需要有足夠的緩存空間和運(yùn)算速度，不適用于本文場(chǎng)景。

基于PF_RING框架的高性能數(shù)據(jù)包流量監(jiān)測(cè)和處理技術(shù)，其核心概念是通過(guò)直接內(nèi)存訪問(wèn)（Direct Memory Access，DMA）將流經(jīng)網(wǎng)卡的網(wǎng)絡(luò)流量作為對(duì)象，直接映射進(jìn)用戶空間，跳過(guò)繁瑣的網(wǎng)卡到內(nèi)核、內(nèi)核到用戶空間的方式，節(jié)約CPU處理時(shí)間及壓縮數(shù)據(jù)拷貝次數(shù)。PF_RING技術(shù)實(shí)現(xiàn)的新式SOCKET連接，可以直接實(shí)現(xiàn)應(yīng)用程序與PF_RING內(nèi)核的通信，即可以通過(guò)PF_RING句柄完成數(shù)據(jù)包的直接讀取，不存在對(duì)每個(gè)數(shù)據(jù)包的內(nèi)存分配釋放動(dòng)作。但要實(shí)現(xiàn)最大性能的數(shù)據(jù)包抓取，PF_RING技術(shù)需要對(duì)網(wǎng)卡驅(qū)動(dòng)進(jìn)行定制化重寫(xiě)，實(shí)現(xiàn)難度較大。

2022年由鄧金祥[11]提出的基于DPDK框架的高速流量采集技術(shù)，通過(guò)DPDK平臺(tái)中的大頁(yè)內(nèi)存方式提高內(nèi)存訪問(wèn)效率，并采用零拷貝技術(shù)降低了數(shù)據(jù)報(bào)文在處理過(guò)程中的流轉(zhuǎn)消耗，優(yōu)化了數(shù)據(jù)報(bào)文從內(nèi)核態(tài)到用戶態(tài)的處理流程帶來(lái)的大量性能消耗，實(shí)現(xiàn)了大流量場(chǎng)景下的流量還原及采集。本文通過(guò)該技術(shù)實(shí)現(xiàn)了高完整性、高可靠性的網(wǎng)絡(luò)流量采集，并為后續(xù)的TCP流重組過(guò)程預(yù)留足夠的性能資源。

3.1.2 TCP流量預(yù)處理

如圖6所示，對(duì)還原TCP流的前期預(yù)處理，本文首先采用了通信數(shù)據(jù)校驗(yàn)中常用的循環(huán)冗余校驗(yàn)碼（Cyclic Redundancy Check，CRC）[12]對(duì)數(shù)據(jù)報(bào)文進(jìn)行快速校驗(yàn)，排除其中的錯(cuò)誤及重復(fù)報(bào)文；其次對(duì)分片數(shù)據(jù)幀進(jìn)行內(nèi)容解析，快速排查ACK及序列號(hào)（Sequence Number，SEQ）的值，保留需要重組的數(shù)據(jù)幀分片，不需要重組的數(shù)據(jù)報(bào)文直接輸出至存儲(chǔ)單元；最后采用Hash索引算法對(duì)TCP數(shù)據(jù)報(bào)文的分片幀進(jìn)行快速索引計(jì)算，并建立Hash列表，用于后續(xù)重組流程。

圖6 報(bào)文處理流程

CRC利用了除法及余數(shù)原理來(lái)進(jìn)行傳輸錯(cuò)誤偵測(cè)，其在數(shù)據(jù)發(fā)送前，對(duì)待發(fā)送數(shù)據(jù)n進(jìn)行計(jì)算并得出一個(gè)冗余位k（校驗(yàn)幀）；然后將k添加到n后，形成新的待發(fā)送數(shù)據(jù)幀T；發(fā)送后接收方獲得數(shù)據(jù)幀T，采用相同的計(jì)算方式，對(duì)n進(jìn)行計(jì)算，如果k相同則傳輸正確，反之則傳輸錯(cuò)誤。CRC的檢錯(cuò)能力十分出色，目前它發(fā)現(xiàn)錯(cuò)誤的概率在99.99%以上，且其資源消耗小。常用的CRC計(jì)算多項(xiàng)式如表1所示。TCP數(shù)據(jù)報(bào)文中的校驗(yàn)幀為4位，按照TCP/IP協(xié)議標(biāo)準(zhǔn)，本文可以確定使用的是CRC-32。

表1 常見(jiàn)CRC多項(xiàng)表達(dá)式

Hash索引算法是基于待查詢數(shù)據(jù)利用Hash函數(shù)計(jì)算出一個(gè)Hash值，并將其構(gòu)建為一個(gè)Hash列表，在需要數(shù)據(jù)查詢時(shí)，直接使用列表中的Hash值作為查詢地址進(jìn)行查詢，實(shí)現(xiàn)了數(shù)據(jù)的快速讀寫(xiě)操作。Hash函數(shù)又被稱為散列函數(shù)，它通過(guò)某種確定性的算法將輸入按照算法轉(zhuǎn)變?yōu)檩敵觯嗤臄?shù)據(jù)輸入永遠(yuǎn)可以得到相同的數(shù)據(jù)輸出，而即使極其細(xì)微的偏差也會(huì)導(dǎo)致輸出的不同。常見(jiàn)的Hash算法包括直接尋址法、除留余數(shù)法、位運(yùn)算法、偽隨機(jī)數(shù)法等。

在Hash索引實(shí)現(xiàn)的過(guò)程中，由于輸入數(shù)據(jù)的值域特點(diǎn)不同，出現(xiàn)了Hash運(yùn)算后Hash值相同的情況，即Hash沖突，這會(huì)使得不同的分片幀的存儲(chǔ)地址相同，從而出現(xiàn)存儲(chǔ)信息覆蓋、丟失等問(wèn)題，最終導(dǎo)致數(shù)據(jù)報(bào)文無(wú)法按正確順序進(jìn)行重組。解決Hash沖突的常用辦法有如下4種：

（1）鏈地址法：為每個(gè)Hash值建立一個(gè)單向鏈表，對(duì)于相同的Hash值，將其加入對(duì)應(yīng)的鏈表中。

（2）再Hash法：Hash函數(shù)的計(jì)算方式多樣，如果第1個(gè)計(jì)算方式得出的key值沖突，就輪換使用第2個(gè)計(jì)算方式，直到無(wú)Hash沖突產(chǎn)生。

（3）開(kāi)發(fā)尋址法：當(dāng)對(duì)應(yīng)的Hash值的存儲(chǔ)地址P產(chǎn)生沖突時(shí)，以P為基礎(chǔ)，向上或者向下，找到一個(gè)未存儲(chǔ)數(shù)據(jù)的可用實(shí)際地址P1來(lái)進(jìn)行數(shù)據(jù)存儲(chǔ)，若已存儲(chǔ)數(shù)據(jù)則跳過(guò)該地址。

（4）建立公共溢出區(qū)：將整個(gè)Hash列表分為基礎(chǔ)表和溢出表兩部分，凡是和基礎(chǔ)表發(fā)生沖突的元素，都填入溢出表中。

3.2 TCP流重組流程設(shè)計(jì)

如圖1所示，TCP流重組設(shè)計(jì)實(shí)現(xiàn)了將分片數(shù)據(jù)幀重組為完整的原始TCP報(bào)文的功能，這是本課題研究的核心重點(diǎn)。該TCP流重組設(shè)計(jì)完成了分片數(shù)據(jù)幀的排序、緩存、重組等處理，詳細(xì)的重組流程如下文所述。

步驟1：接收TCP報(bào)文，按4元組計(jì)算session hash值，從緩存中取出session相關(guān)信息，如為空，則新建session相關(guān)結(jié)構(gòu)。

步驟2：判斷確認(rèn)隊(duì)列是否為空，為空則將報(bào)文直接放進(jìn)確認(rèn)隊(duì)列、更新區(qū)間樹(shù)、記錄報(bào)文傳輸方向和next seq，返回步驟1；不為空，則執(zhí)行步驟3。

步驟3：根據(jù)4元組判斷報(bào)文傳輸方向，如與上一條報(bào)文方向一致，則執(zhí)行步驟5；不一致，則執(zhí)行步驟4。

步驟4：判斷當(dāng)前報(bào)文ACK是否等于上一報(bào)文next seq，等于則表示兩報(bào)文為連續(xù)報(bào)文，將報(bào)文放入確認(rèn)隊(duì)列，更新區(qū)間樹(shù)，并記錄報(bào)文傳輸方向和next seq，否則執(zhí)行步驟6。

步驟5：判斷當(dāng)前報(bào)文seq是否等于上一報(bào)文next seq，等于則表示兩報(bào)文為連續(xù)報(bào)文，將當(dāng)前報(bào)文放入確認(rèn)隊(duì)列，更新區(qū)間樹(shù)，并記錄報(bào)文傳輸方向和next seq，否則執(zhí)行步驟6。

步驟6：計(jì)算當(dāng)前報(bào)文的區(qū)間值，從區(qū)間樹(shù)中查詢此區(qū)間值；如果查到，則表示當(dāng)前報(bào)文為重復(fù)報(bào)文，丟棄即可；如未查到，則表示當(dāng)前報(bào)文為亂序報(bào)文，放入待確認(rèn)隊(duì)列，執(zhí)行步驟7。

步驟7：當(dāng)待確認(rèn)隊(duì)列中報(bào)文數(shù)量大于n，有n個(gè)報(bào)文堆積待重組時(shí)，如果n大于5，很可能傳輸過(guò)程中有丟包行為，從而產(chǎn)生數(shù)據(jù)空洞，導(dǎo)致后續(xù)報(bào)文不能確認(rèn)。這時(shí)應(yīng)從待確認(rèn)報(bào)文隊(duì)列中取出報(bào)文無(wú)視空洞，按后續(xù)順序強(qiáng)制加入確認(rèn)隊(duì)列。

步驟8：當(dāng)前TCP報(bào)文重組結(jié)束，繼續(xù)返回執(zhí)行步驟1。

新設(shè)計(jì)的TCP流重組流程，通過(guò)優(yōu)化程序步驟，引入分片數(shù)據(jù)幀預(yù)處理機(jī)制和Hash索引算法，解決了傳統(tǒng)TCP流重組方式因亂序報(bào)文查詢效率過(guò)低導(dǎo)致重組效率低，不能滿足大流量環(huán)境下的TCP流重組，以及重組完整度不足的問(wèn)題。

圖7 TCP流報(bào)文重組流程

4 測(cè)試結(jié)果與分析

本文利用區(qū)間管理算法實(shí)現(xiàn)的TCP流重組技術(shù)的核心目的在于支持?jǐn)?shù)據(jù)完整、有序地完成重組工作，且重組效率得到大幅度提升。為測(cè)試報(bào)文重組的正確性及重組效率，構(gòu)建了由4臺(tái)萬(wàn)兆級(jí)別數(shù)據(jù)包發(fā)送服務(wù)器、1部萬(wàn)兆路由器、1臺(tái)基于本文所提技術(shù)的萬(wàn)兆數(shù)據(jù)采集及重組服務(wù)器組成的測(cè)試環(huán)境。4臺(tái)萬(wàn)兆級(jí)數(shù)據(jù)包發(fā)送服務(wù)器將通過(guò)控制最大傳輸單元（Maximum Transmission Unit，MTU）來(lái)模擬實(shí)際真實(shí)網(wǎng)絡(luò)的無(wú)序狀態(tài)。

4.1 區(qū)間管理算法重組TCP流的正確性測(cè)試

本節(jié)對(duì)利用區(qū)間管理算法的TCP流重組技術(shù)進(jìn)行正確性測(cè)試，首先選擇1臺(tái)數(shù)據(jù)包發(fā)送服務(wù)器，使用文件傳輸協(xié)議（File Transfer Protocol，F(xiàn)TP）向另一臺(tái)目標(biāo)數(shù)據(jù)包發(fā)送服務(wù)器傳輸1個(gè)大小為4.82 MB的壓縮文件test.rar，并在目標(biāo)數(shù)據(jù)包發(fā)送服務(wù)器上使用TcpDump進(jìn)行抓包；其次使用區(qū)間管理算法的TCP流重組技術(shù)對(duì)抓到的數(shù)據(jù)包進(jìn)行報(bào)文重組；最后分別計(jì)算發(fā)送前的test.rar文件MD5值和重組得到文件的MD5值。重組結(jié)果及MD5驗(yàn)證結(jié)果如圖8所示，兩個(gè)文件的大小、MD5值均相等，說(shuō)明重組文件的結(jié)果是正確的。

圖8 文件重組及MD5結(jié)果驗(yàn)證

4.2 區(qū)間管理算法重組TCP流的性能測(cè)試

本節(jié)對(duì)利用區(qū)間管理算法的TCP流重組技術(shù)的性能進(jìn)行測(cè)試。該次測(cè)試主要關(guān)注在不斷增長(zhǎng)的網(wǎng)絡(luò)流量下，TCP流重組技術(shù)是否能正常穩(wěn)定運(yùn)行。測(cè)試其每秒處理數(shù)據(jù)包（Packets Per Second，PPS）、設(shè)備內(nèi)存使用情況和流量重組準(zhǔn)確率3個(gè)方面的性能。流量發(fā)送方面，由4臺(tái)萬(wàn)兆級(jí)別數(shù)據(jù)包發(fā)送服務(wù)器平均分配TCP數(shù)據(jù)流進(jìn)行發(fā)送，發(fā)送速率依次為250 MB/s、500 MB/s、1.25 GB/s、2 GB/s和2.5 GB/s，構(gòu)造出在路由器網(wǎng)絡(luò)節(jié)點(diǎn)處的網(wǎng)絡(luò)流量總量依次為1 GB/s、2 GB/s、5 GB/s、8 GB/s、10 GB/s的網(wǎng)絡(luò)流量環(huán)境。4臺(tái)數(shù)據(jù)包發(fā)送服務(wù)器的MTU值依次設(shè)為256，512，1 024和1 500字節(jié)，用于模擬真實(shí)網(wǎng)絡(luò)環(huán)境的亂序現(xiàn)象。將路由器的網(wǎng)絡(luò)流量旁路接入利用了本文區(qū)間管理算法重組技術(shù)的萬(wàn)兆數(shù)據(jù)采集及重組服務(wù)器，對(duì)上述3個(gè)性能參數(shù)進(jìn)行監(jiān)測(cè)，其結(jié)果如圖9所示。

圖9 不同流量下每秒處理的數(shù)據(jù)包

綜合上述測(cè)試數(shù)據(jù)，可以看出采用區(qū)間管理算法的TCP流重組技術(shù)在準(zhǔn)確性上有著顯著的性能優(yōu)勢(shì)。如圖9、圖10和圖11所示，隨著網(wǎng)絡(luò)流量的提高，重組準(zhǔn)確性并沒(méi)有下降太多，而PPS和內(nèi)存使用情況都隨著網(wǎng)絡(luò)流量的增加呈線性增長(zhǎng)，且暫時(shí)沒(méi)有出現(xiàn)算法程序上的瓶頸。至于在更大網(wǎng)絡(luò)流量下的運(yùn)行情況，受限于硬件條件，本次沒(méi)有進(jìn)行相應(yīng)測(cè)試。此外，每一個(gè)層級(jí)的網(wǎng)絡(luò)流量重組場(chǎng)景都運(yùn)行了至少4個(gè)小時(shí)，也證明了利用區(qū)間管理算法的TCP流重組技術(shù)的穩(wěn)定性。

圖10 不同流量下內(nèi)存使用情況

圖11 不同流量下流量重組準(zhǔn)確率

毫無(wú)疑問(wèn)，對(duì)比前文所述的各項(xiàng)分片重組技術(shù)，本文所研究的利用區(qū)間管理算法的TCP流重組技術(shù)在性能上有著不小的優(yōu)勢(shì)。

5 結(jié)語(yǔ)

在現(xiàn)在網(wǎng)絡(luò)加速發(fā)展的時(shí)代，對(duì)網(wǎng)絡(luò)空間中準(zhǔn)確流量的需求越來(lái)越明顯。不論是網(wǎng)絡(luò)安全行業(yè)、審計(jì)監(jiān)管行業(yè)還是其他互聯(lián)網(wǎng)企業(yè)，有效、高速且準(zhǔn)確的網(wǎng)絡(luò)流量重組技術(shù)都是后續(xù)各應(yīng)用場(chǎng)景的數(shù)據(jù)來(lái)源基礎(chǔ)，只有高度準(zhǔn)確且高度可靠的數(shù)據(jù)源才能帶給項(xiàng)目最堅(jiān)實(shí)的基礎(chǔ)。

本文通過(guò)查閱文獻(xiàn)，對(duì)現(xiàn)有的分片重組技術(shù)做了詳盡的分析，在理清了目前技術(shù)的局限性后，根據(jù)平衡樹(shù)算法，提出了適用于大流量高并發(fā)的區(qū)間管理算法，并解決了TCP流分片重組流程，解決了因亂序、重發(fā)、查詢效率低導(dǎo)致的重組效率低、重組完整度不足的技術(shù)難題。