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

算法涉及到的數(shù)據(jù)結(jié)構(gòu)主要有下面兩個(gè)：

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)黑客用同一個(gè)ip地址使用掃描器對(duì)不同的主機(jī)或者端口進(jìn)行掃描。統(tǒng)計(jì)一段時(shí)間內(nèi)同一個(gè)source IP對(duì)不同的主機(jī)或者端口號(hào)

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

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

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

struct scan的信息為目的主機(jī)的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?}

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

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

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

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

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

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

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