libnids中对ddos攻击的监测主要文件在scan.c中，主要原理是在tcp处理的时候每来一个syn packet，都要调用一次detect_scan函数。根据设置的参数看是否存在ddos攻击。
算法涉及到的数据结构主要有下面两个：
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的算法主要使用来发现黑客用同一个ip地址使用扫描器对不同的主机或者端口进行扫描。统计一段时间内同一个source IP对不同的主机或者端口号
发前的连接数，如果超过我们设置的阀值scan_num_ports，则认为有黑客在对我们的系统发起攻击。
算法主要的数据结构就是构造并维持一张hash table，hash表的元素类型是指向存储host节点的双向链表的头指针，host节点包含每个连接libnids保护的主机的相关信息，该hash表利用数据包的source IP来计算hash值，对于hash值相同的host会被链接到存在的host链表的next的位置。
host 节点的数据成员有source IP addr，syn packet收到的时间戳modtime， 同一source IP发出的syn packet的个数n_packets, 用于存放链接的相关信息的指针packets，这里暂时将其看为数组更好理解一些。 其中n_packets为packets数组的个数。
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 <= 0)
75 return;
76
77 th = (struct tcphdr *) (((char *) iph) + 4 * iph->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 }
鉴于源代码并不多，这里将整个函数的代码全都贴出来。这个代码给出了对于每一个syn数据包的处理流程：首先根据source address进行hash，找到相应的表项，然后在该表项指向的host双向链表中查找source IP address 域与该数据包source ip相同的host节点。
如果没有找到匹配的host节点，如果达到了每条链表最大的host节点的个数10个，则将最老的host节点替换掉。否则通过系统调用malloc新申请一个host节点，根据链表是否为空，插入到已经存在的链表中或者作为链表的第一个元素。更新host节点的时间域为系统时间。
如果找到匹配的host节点，则利用syn包的<dst_addr, dst_port>在packets数组中进行查找，如果找到匹配的数组元素，则直接返回。如果没有匹配的数组元素，则将n_packets加1， 将<dst_addr,dst_port>放到数组packets[n_packets]中。
判断n_packets是否大于设定的阀值，如果大于则给出一个警告，并且将n_packets设置为0.
通过上面可以看出这个算法是比较通用的一种算法，稍作修改就可以监测分布式tcp syn flood攻击（比如根据dest ip做hash），udp flood攻击等等。
从上面可以看出这个算法实现起来效率比较低，只能在低速网络环境下使用。要想在告诉环境下使用需要进行优化。比如去掉malloc， 采用多核并行技术， 无锁数据结构等等。基于stream的多核并行会导致相同的源地址不同的目的地址分发到不同的cpu core上，这样就会产生cache trashing，导致性能下降，这个问题可以考虑通过CAS原子操作来降低锁的开销。
关于优化后高性能的代码这里就不贴出来了。主要是算法思想。