# Libtrace實作(1) ## 項目 1. 計算 payload 分布並化成圖 2. 實現簡易Multistage Filter ## 結果 ### Questions (b.1) ***What do you see in the output messages when you execute the program of yk_source_demo ?*** 執行後可以看到圖一的結果  **▲Fig.1 yk_source_demo result** 細看程式碼內部中main()在一系列處理trace檔案後，以一個while迴圈連續讀取封包內容，如圖二紅框所示。  **▲Fig.2 yk_source_demo main()** 在while迴圈中可以看到每一個封包都是經由一個per_packet()來處理，因此我們再細看其函式內容，如圖三所式。  **▲Fig.3 yk_source_demo per_packet()** 基本上可以看到我們想要對封包做怎樣的處理都可以定義在per_packet()函式中，我們將封包丟進libtrace所提供的API中可以得到個別資訊，如mac或是來源端地址等，但是幾個透過API回傳的值皆為指標，且必須去辨別是否為我們想要處理的封包格式(如IPv4等)，因此我們定義了下方的涵式來處理該指標資訊。 ==如果想要知道有哪一些API以及API會回傳哪種資料型態可以參考[官方文件](https://research.wand.net.nz/software/libtrace-docs/html/index.html)== 圖四中定義了我們如何將mac地址印出，操作的概念是利用指標與陣列的關係，我們可以把傳入的指標當作起始陣列的位置，並以陣列的方式以index讀取接續記憶體位置的值，***注意:需要先知道指標的記憶體位置長度以及其儲存的資料型態大小，才可以以這種方式來操作，否則可能會產生記憶體位置存取錯誤的發生***  **▲Fig.4 yk_source_demo print_mac()** 圖五中定義了我們如何把IP地址印出，利用了存取記憶體位址來轉換結構型態的方式操作，可以看到在函數輸入參數的部分為==struct sockaddr== 的指標，但我們在判別完是否為IPv4或是IPv6後我們分別將他們轉為==sockaddr_in==和為==sockaddr_in6==，有兩個原因(1)兩種封包所占用的記憶體長度不一樣(2)方便讀取資料內容。 以下為socket傳輸介面中兩種結構的定義，可以理解struct sockaddr為一種通用結構，他可以容納得下現今使用的所有種類傳輸封包，但是缺點是他將除了長度以及通訊協定家族的識別碼以外的資訊通通包在一個陣列裡面，也就是說我今天要讀取特定資料我還必須要以輸入index來存取，相當麻煩，因此當我們辨識完該封包種類後我們可以透過==存取相同起始記憶體位置==的方式來將sockaddr的結構轉為特定協議的結構，可以方便我們在我們之後可以以結構運算子來方便存取結構中的成員。 舉例來說，今天我們不轉換的情況下想要讀取ipv4封包的port號，我必須先知道這個Port號幾個byte以及他是存放在哪一個記憶體位置，然後以迴圈讀取sa_data[]中的特定位置在組合成Port號;相反的如果我們轉換結構後，可以簡單地以sockaddr_in.sin_port來存取特定資訊。***.為一般結構的成員運算子，->為指標的成員運算子*** ``` struct sockaddr { __uint8_t sa_len; /* total length */ sa_family_t sa_family; /* [XSI] address family */ char sa_data[14]; /* [XSI] addr value (actually larger) */ }; ``` ``` struct sockaddr_in { __uint8_t sin_len; sa_family_t sin_family; in_port_t sin_port; struct in_addr sin_addr; char sin_zero[8]; }; ``` [參考資料](https://stackoverflow.com/questions/21099041/why-do-we-cast-sockaddr-in-to-sockaddr-when-calling-bind)  **▲Fig.5 yk_source_demo print_ip()** 基本上，這個簡單的print out程式，是以libtrace所提供的demo檔案以及API所組成，流程就是main()解析trace後以per_packet()來處理每一個封包。 ### Questions (b.2)(b.3) ***What do you see in the output messages when you execute the program of yk_demo_hash?*** 這題跟前一題大同小異，差別只在於印出了(1)frame和payload的長度(2)調用hash function，圖六為輸出的結果。  **▲Fig.6 yk_demo_hash** Questions (b.3)中問到，圖七中紅框裡標示了調用API來顯示封包frame和payload的長度。  **▲Fig.7 yk_demo_hash frame and payload length** 圖八中展示了如何調用其它函式庫中的hash31()。需要注意的地方是，這格hash function他所需要的輸入是long long因此我們必須要注意我們給予的資料型態。  **▲Fig.8 yk_demo_hash hash** ### Questions (b.4) ***Please modify the file so that you can analyze the trace and get the payload length histogram. The bin size is 100 bytes. That is, how many packets for payload size of 1~100, 101~200, 201~300, …, 1401~1500?*** 我們套用前兩個範例的流程，在main()中解析封包，以per_packet()來處理封包，並簡單定義幾個函式就可以達成。 圖九，簡單定義一下會用到的參數。基本上我定義一個計數器來數個區間範圍內的封包數量。然後以print_bin()印出。  **▲Fig.9 Finn_payload_bin parameters declaration** 我將讀到的封包解析長度後，以switch來分類並在計數器中計數，如圖十所示。  **▲Fig.10 Finn_payload_bin per_packet()** 並以用一個函數來印出，雖然有點多此以舉，簡單的函釋內容可以用inline來處理或是直接寫在main()裡面。  **▲Fig.11 Finn_payload_bin print_bin()** 可以看到輸出結果如圖十二所示，並將結果畫成柱狀圖如圖十三所示。  **▲Fig.12 Finn_payload_bin result**  **▲Fig.13 Finn_payload_bin bin** ### Questions (b.5) ***Please code a multi-stage filter to identify the heavy hitters. Please design and specify reasonable parameters (threshold, number and entries of your array) for your multi-stage filter.*** 這題就稍微複雜一點，必須設計一格個過濾器來處理封包，但是其實只要用幾個計數器就可以達到，我定義了閥值Threshold以及一個流量表HH_Table，剩餘的就是用來實現Filter的計數器以及最後統計用的計數器。  **▲Fig.14 Finn_MultiStage_Filter declaration** 在per_packet()中我解析了封包payload的長度，因為等等在計數時我以封包長度來計數，在這個實作中我僅僅只使用SrcIP來當作我的FlowID，因此我只解析了SrcIP，並在計數總長度後丟進Filter裡面來計數過濾。  **▲Fig.15 Finn_MultiStage_Filter per_packer()** 過濾器中，我只處理IPv4的封包其餘種類都直接忽略，接著以前面範例的概念我將結構轉換，並執行三次hash31()取我所設定的HashCounterNumber的餘數(10000)作為counter index。 在這邊的過濾器邏輯很簡單，我先 (1)判別目前的flow是否在三個計數器上的值有任一個仍小於等於閥值，是的話進入到裡面在每個計數器相對應的位置增加payload長度，並在進行第二次判斷 (1-1)==計數後==目前的flow是否在三個計數器上的值都大於等於閥值，是的話則將IP紀錄於表上，結束封包處裡。 (2)目前的flow在三個計數器上的值都已經大於等於閥值，則單純紀錄payload長度。  **▲Fig.16 Finn_MultiStage_Filter MultiStageFilter()** 接著在處理完所有封包後，將所表上的結果印出，如圖十七所示，而我在印出時有把該Flow所傳輸的byte數印出，因此我寫了一個判斷最小值的方法來選擇三個計數器中最小值作為實際的輸出(當然會有誤差)如圖十八所示，最後的執行結果如圖十九所示。  **▲Fig.17Finn_MultiStage_Filter print out**  **▲Fig.18 Finn_MultiStage_Filter Minof3**  **▲Fig.18 Finn_MultiStage_Filter result** ## gcc編譯 gcc 指令 -o :打包成執行打 -g :for gdb -Wall:印出所有警告 -ltrace,-lm:告訴編譯器要去哪裡找header file