libnids中對ddos攻擊的監(jiān)測主要文件在scan.c中，主要原理是在tcp處理的時候每來一個syn packet，都要調用一次detect_scan函數(shù)。根據(jù)設置的參數(shù)看是否存在ddos攻擊。

算法涉及到的數(shù)據(jù)結構主要有下面兩個：

9?struct?scan?{
?10???u_int?addr;
?11???unsigned?short?port;
?12???u_char?flags;
?13?};
?14?
?15?struct?host?{
?16???struct?host?*next;
?17???struct?host?*prev;
?18???u_int?addr;
?19???int?modtime;
?20???int?n_packets;
?21???struct?scan?*packets;
?22?};

最原始的libnids的scan_detect的算法主要使用來發(fā)現(xiàn)黑客用同一個ip地址使用掃描器對不同的主機或者端口進行掃描。統(tǒng)計一段時間內同一個source IP對不同的主機或者端口號

發(fā)前的連接數(shù)，如果超過我們設置的閥值scan_num_ports，則認為有黑客在對我們的系統(tǒng)發(fā)起攻擊。

算法主要的數(shù)據(jù)結構就是構造并維持一張hash table，hash表的元素類型是指向存儲host節(jié)點的雙向鏈表的頭指針，host節(jié)點包含每個連接libnids保護的主機的相關信息，該hash表利用數(shù)據(jù)包的source IP來計算hash值，對于hash值相同的host會被鏈接到存在的host鏈表的next的位置。

host 節(jié)點的數(shù)據(jù)成員有source IP addr，syn packet收到的時間戳modtime， 同一source IP發(fā)出的syn packet的個數(shù)n_packets, 用于存放鏈接的相關信息的指針packets，這里暫時將其看為數(shù)組更好理解一些。 其中n_packets為packets數(shù)組的個數(shù)。

struct scan的信息為目的主機的dst_address， dst_port。

算法主要的控制流如下：

?64?void
?65?detect_scan(struct?ip?*?iph)
?66?{
?67???int?i;
?68???struct?tcphdr?*th;
?69???int?hash;
?70???struct?host?*this_host;
?71???struct?host?*oldest;
?72???int?mtime?=?2147483647;
?73?
?74???if?(nids_params.scan_num_hosts?ip_hl);
?78???hash?=?scan_hash(iph->ip_src.s_addr);
?79???this_host?=?hashhost[hash];
?80???oldest?=?0;
?81???timenow?=?0;
?82?
?83???for?(i?=?0;?this_host?&&?this_host->addr?!=?iph->ip_src.s_addr;?i++)?{
?84?????if?(this_host->modtime?<?mtime)?{
?85???????mtime?=?this_host->modtime;
?86???????oldest?=?this_host;
?87?????}
?88?????this_host?=?this_host->next;
?89???}
?90???if?(!this_host)?{
?91?????if?(i?==?10)
?92???????this_host?=?oldest;
?93?????else?{
?94???????this_host?=?(struct?host?*)?malloc(sizeof(struct?host)?+?
?95?????????????(nids_params.scan_num_ports?+?1)?*?sizeof(struct?scan));
?96???????if?(!this_host)
?97???????????nids_params.no_mem("detect_scan");
?98???????this_host->packets?=?(struct?scan?*)?(((char?*)?this_host)?+?sizeof(struct?host));
?99???????if?(hashhost[hash])?{
100?????hashhost[hash]->prev?=?this_host;
101?????this_host->next?=?hashhost[hash];
102???????}
103???????else
104?????this_host->next?=?0;
105???????this_host->prev?=?0;
106???????hashhost[hash]?=?this_host;
107?????}
108?????this_host->addr?=?iph->ip_src.s_addr;
109?????this_host->modtime?=?gettime();
110?????this_host->n_packets?=?0;
111???}
112???if?(this_host->modtime?-?gettime()?>?nids_params.scan_delay)
113?????this_host->n_packets?=?0;
114???this_host->modtime?=?gettime();
115???for?(i?=?0;?i?<?this_host->n_packets;?i++)
116?????if?(this_host->packets[i].addr?==?iph->ip_dst.s_addr?&&
117?????this_host->packets[i].port?==?ntohs(th->th_dport))
118???????return;
119???this_host->packets[this_host->n_packets].addr?=?iph->ip_dst.s_addr;
120???this_host->packets[this_host->n_packets].port?=?ntohs(th->th_dport);
121???this_host->packets[this_host->n_packets].flags?=?*((unsigned?char?*)?(th)?+?13);
122???this_host->n_packets++;
123???if?(this_host->n_packets?>?nids_params.scan_num_ports)?{
124?????nids_params.syslog(NIDS_WARN_SCAN,?0,?0,?this_host);
125?????this_host->n_packets?=?0;
126???}
127?}

鑒于源代碼并不多，這里將整個函數(shù)的代碼全都貼出來。這個代碼給出了對于每一個syn數(shù)據(jù)包的處理流程：首先根據(jù)source address進行hash，找到相應的表項，然后在該表項指向的host雙向鏈表中查找source IP address 域與該數(shù)據(jù)包source ip相同的host節(jié)點。

如果沒有找到匹配的host節(jié)點，如果達到了每條鏈表最大的host節(jié)點的個數(shù)10個，則將最老的host節(jié)點替換掉。否則通過系統(tǒng)調用malloc新申請一個host節(jié)點，根據(jù)鏈表是否為空，插入到已經(jīng)存在的鏈表中或者作為鏈表的第一個元素。更新host節(jié)點的時間域為系統(tǒng)時間。

如果找到匹配的host節(jié)點，則利用syn包的

判斷n_packets是否大于設定的閥值，如果大于則給出一個警告，并且將n_packets設置為0.

通過上面可以看出這個算法是比較通用的一種算法，稍作修改就可以監(jiān)測分布式tcp syn flood攻擊（比如根據(jù)dest ip做hash），udp flood攻擊等等。

從上面可以看出這個算法實現(xiàn)起來效率比較低，只能在低速網(wǎng)絡環(huán)境下使用。要想在告訴環(huán)境下使用需要進行優(yōu)化。比如去掉malloc， 采用多核并行技術， 無鎖數(shù)據(jù)結構等等?；趕tream的多核并行會導致相同的源地址不同的目的地址分發(fā)到不同的cpu core上，這樣就會產生cache trashing，導致性能下降，這個問題可以考慮通過CAS原子操作來降低鎖的開銷。

關于優(yōu)化后高性能的代碼這里就不貼出來了。主要是算法思想。