1 /*
2 * Copyright (c) 2014-2020, Peter Haag
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright notice,
11 * this list of conditions and the following disclaimer in the documentation
12 * and/or other materials provided with the distribution.
13 * * Neither the name of the author nor the names of its contributors may be
14 * used to endorse or promote products derived from this software without
15 * specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 * POSSIBILITY OF SUCH DAMAGE.
28 *
29 */
30
31 #include "config.h"
32
33 #include <stdio.h>
34 #include <stdlib.h>
35 #include <stddef.h>
36 #include <stdarg.h>
37 #include <string.h>
38 #include <errno.h>
39 #include <sys/types.h>
40 #include <sys/socket.h>
41 #ifdef HAVE_NETINET_IN_SYSTM_H
42 #include <netinet/in_systm.h>
43 #endif
44
45 #ifdef HAVE_NETINET_IN_H
46 #include <netinet/in.h>
47 #endif
48
49 #include <sys/socket.h>
50 #include <netinet/in.h>
51 #include <netinet/ip.h>
52 #include <arpa/inet.h>
53 #include <unistd.h>
54 #include <stdint.h>
55
56 #include "util.h"
57 #include "rbtree.h"
58 #include "ipfrag.h"
59
60 #define KEYLEN (offsetof(IPFragNode_t,data_size) - offsetof(IPFragNode_t, src_addr))
61 static int IPFragNodeCMP(struct IPFragNode *e1, struct IPFragNode *e2);
62
63 static struct IPFragNode *New_frag_node(void);
64
65 static void Free_node(struct IPFragNode *node, int free_data);
66
67 static void Remove_node(struct IPFragNode *node, int free_data);
68
69 // Insert the IP RB tree code here
70 RB_GENERATE(IPFragTree, IPFragNode, entry, IPFragNodeCMP);
71
72 static IPFragTree_t *IPFragTree;
73 static uint32_t NumFragments;
74 static time_t lastExpire = 0;
75
IPFragNodeCMP(struct IPFragNode * e1,struct IPFragNode * e2)76 static int IPFragNodeCMP(struct IPFragNode *e1, struct IPFragNode *e2) {
77 uint32_t *a = &e1->src_addr;
78 uint32_t *b = &e2->src_addr;
79 int i;
80
81 // 2 x sizeof(uint32_t) (8) + frag_offset == 12
82 i = memcmp((void *)a, (void *)b, KEYLEN );
83 return i;
84
85 } // End of IPFragNodeCMP
86
New_frag_node(void)87 static struct IPFragNode *New_frag_node(void) {
88 struct IPFragNode *node;
89
90 node = calloc(1, sizeof(struct IPFragNode));
91 if ( !node ) {
92 LogError("malloc() error in %s line %d: %s", __FILE__, __LINE__, strerror(errno) );
93 return NULL;
94 }
95
96 node->data = calloc(1, IP_MAXPACKET);
97 if ( !node->data ) {
98 LogError("malloc() error in %s line %d: %s", __FILE__, __LINE__, strerror(errno) );
99 free(node);
100 return NULL;
101 }
102
103 node->eod = node->data;
104 node->data_size = 0;
105
106 node->holes = calloc(1, sizeof(hole_t));
107 if ( !node->holes ) {
108 LogError("malloc() error in %s line %d: %s", __FILE__, __LINE__, strerror(errno) );
109 free(node->data);
110 free(node);
111 return NULL;
112 }
113 node->holes->next = NULL;
114 node->holes->first = 0;
115 node->holes->last = IP_MAXPACKET;
116 NumFragments++;
117
118 return node;
119
120 } // End of New_frag_node
121
Free_node(struct IPFragNode * node,int free_data)122 static void Free_node(struct IPFragNode *node, int free_data) {
123 hole_t *hole, *h;
124
125 hole = node->holes;
126 while (hole) {
127 h = hole->next;
128 free(hole);
129 hole = h;
130 }
131 if (free_data)
132 free(node->data);
133 free(node);
134 NumFragments--;
135
136 } // End of Free_node
137
Remove_node(struct IPFragNode * node,int free_data)138 static void Remove_node(struct IPFragNode *node, int free_data) {
139 struct IPFragNode *n;
140
141 n = RB_REMOVE(IPFragTree, IPFragTree, node);
142 if ( n ) {
143 Free_node(n, free_data);
144 } // else - node not in tree
145
146 } // End of Remove_node
147
IPFragTree_init(void)148 int IPFragTree_init(void) {
149 IPFragTree = calloc(1, sizeof(IPFragTree_t));
150 if ( !IPFragTree ) {
151 LogError("malloc() error in %s line %d: %s", __FILE__, __LINE__, strerror(errno) );
152 return 0;
153 }
154 RB_INIT(IPFragTree);
155 NumFragments = 0;
156 dbg_printf("IPFrag key len: %lu\n", KEYLEN);
157 return 1;
158 } // End of IPFragTree_init
159
IPFragTree_free(void)160 void IPFragTree_free(void) {
161 struct IPFragNode *node, *nxt;
162
163 nxt = NULL;
164 for (node = RB_MIN(IPFragTree, IPFragTree); node != NULL; node = nxt) {
165 nxt = RB_NEXT(IPFragTree, IPFragTree, node);
166 RB_REMOVE(IPFragTree, IPFragTree, node);
167 Free_node(node, 1);
168 }
169
170 free(IPFragTree);
171 IPFragTree = NULL;
172 NumFragments = 0;
173
174 } // End of IPFragTree_free
175
IPFragTree_expire(time_t when)176 static void IPFragTree_expire(time_t when) {
177 struct IPFragNode *node, *nxt;
178
179 uint32_t expireCnt = 0;
180 nxt = NULL;
181 for (node = RB_MIN(IPFragTree, IPFragTree); node != NULL; node = nxt) {
182 nxt = RB_NEXT(IPFragTree, IPFragTree, node);
183 if ( (when - node->last) > 15 ) {
184 RB_REMOVE(IPFragTree, IPFragTree, node);
185 Free_node(node, 1);
186 expireCnt++;
187 }
188 }
189 dbg_printf("Expired %u incomplete IP fragments, total fragments: %u\n", expireCnt, NumFragments);
190 if ( expireCnt )
191 LogInfo("Expired %u incomplete IP fragments, total fragments: %u", expireCnt, NumFragments);
192
193 } // End of IPFragTree_expire
194
IPFrag_tree_Update(time_t when,uint32_t src,uint32_t dst,uint32_t ident,uint32_t * length,uint32_t ip_off,void * data)195 void *IPFrag_tree_Update(time_t when, uint32_t src, uint32_t dst, uint32_t ident, uint32_t *length, uint32_t ip_off, void *data) {
196 struct IPFragNode FindNode, *n;
197 hole_t *hole, *h, *hole_parent;
198 uint16_t more_fragments, first, last, max;
199 dbg(int found_hole;)
200 char src_s[16], dst_s[16];
201
202 if ( (when - lastExpire ) > 10 ) {
203 IPFragTree_expire(when);
204 lastExpire = when;
205 }
206
207 #ifdef DEVEL
208 inet_ntop(AF_INET, &src, src_s, 16);
209 inet_ntop(AF_INET, &dst, dst_s, 16);
210 printf("Update %s - %s\n", src_s, dst_s);
211 #endif
212
213 FindNode.src_addr = src;
214 FindNode.dst_addr = dst;
215 FindNode.ident = ident;
216 FindNode.last = 0;
217
218 n = RB_FIND(IPFragTree, IPFragTree, &FindNode);
219 if ( !n ) {
220 n = New_frag_node();
221 n->src_addr = src;
222 n->dst_addr = dst;
223 n->ident = ident;
224 n->last = when;
225 if ( RB_INSERT(IPFragTree, IPFragTree, n) ) {
226 // must never happen
227 LogError("Node insert returned existing node - Software error in %s line %d", __FILE__, __LINE__);
228 }
229 }
230
231 hole = n->holes;
232 hole_parent = NULL;
233
234 first = (ip_off & IP_OFFMASK) << 3;
235 more_fragments = (ip_off & IP_MF) != 0 ? 1 : 0;
236 last = first + *length - 1;
237
238 if ( last > IP_MAXPACKET ) {
239 LogError("Fragment assembly error: last > IP_MAXPACKET");
240 LogError("Fragment assembly: first: %u, last: %u, MF: %u\n", first, last, more_fragments);
241 return NULL;
242 }
243
244 // last fragment - sets max offset
245 dbg(found_hole = 0;)
246 max = more_fragments == 0 ? last : 0;
247 dbg_printf("Fragment assembly: first: %u, last: %u, MF: %u, ID: %x\n", first, last, more_fragments, ident);
248 while (hole) {
249 uint16_t hole_last;
250 if ( max ) {
251 dbg_printf("max in last fragment: %u\n", max);
252 // last fragment offset/length
253 if ( hole->last == IP_MAXPACKET ) {
254 // last fragment has max size
255 if ( max >= hole->first ) {
256 dbg_printf("set max of last fragment: %u\n", max);
257 hole->last = max;
258 } else {
259 inet_ntop(AF_INET, &src, src_s, 16);
260 inet_ntop(AF_INET, &dst, dst_s, 16);
261 LogError("last fragment offset error - teardrop attack?? SRC: %s, DST: %s",
262 src_s, dst_s);
263 }
264 }
265 }
266 dbg_printf("Check Hole: first: %u, last: %u\n", hole->first, hole->last);
267
268 if ( first > hole->last ) {
269 hole_parent = hole;
270 hole = hole->next;
271 dbg_printf("Fragment right outside hole\n");
272 continue;
273 }
274 if ( last < hole->first ) {
275 hole_parent = hole;
276 hole = hole->next;
277 dbg_printf("Fragment left outside hole\n");
278 continue;
279 }
280
281 // check for overlapping - cut off overlap
282 if ( last > hole->last ) {
283 dbg_printf("Truncate right overlapping fragment: %u -> %u\n", last, hole->last);
284 last = hole->last;
285 }
286
287 if ( first < hole->first ) {
288 dbg_printf("Truncate left overlapping fragment: %u -> %u\n", first, hole->first);
289 first = hole->first;
290 }
291
292 if ( first > last ) {
293 LogInfo("fragment error first %u >= last %u", first, last);
294 return NULL;
295 }
296 // fragment fits into hole
297 dbg(found_hole = 1;)
298 if ( last > n->data_size )
299 n->data_size = last;
300
301 hole_last = hole->last;
302 if ( first == hole->first ) {
303 dbg_printf("Fragment matches first\n");
304 // fragment fits at beginning of hole
305 if ( last == hole->last ) {
306 dbg_printf("Fragment matches last\n");
307 // fragment fits completly into hole - delete hole
308 if ( hole_parent ) {
309 hole_parent->next = hole->next;
310 } else {
311 n->holes = hole->next;
312 }
313 free(hole);
314 hole = NULL;
315 } else {
316 // fragment smaller than hole
317 dbg_printf("Fragment smaller than hole\n");
318 hole->first = last+1;
319 }
320 } else {
321 // fragment start within hole
322 dbg_printf("Fragment inside hole\n");
323 hole->last = first - 1;
324 if ( last < hole_last ) {
325 // fragment ends within hole - add another hole
326 h = malloc(sizeof(hole_t));
327 if ( !h ) {
328 LogError("malloc() error in %s line %d: %s", __FILE__, __LINE__, strerror(errno) );
329 return NULL;
330 }
331 h->first = last + 1;
332 h->last = hole_last;
333 h->next = n->holes;
334 n->holes = h;
335 }
336 }
337 memcpy(n->data + first, data, *length);
338
339 break;
340 }
341
342 #ifdef DEVEL
343 if ( !found_hole ) {
344 hole_t *h = n->holes;
345 dbg_printf("No space in fragment list for: first: %u, last: %u\n", first, last);
346 while ( h ) {
347 dbg_printf("first: %u,last: %u\n", h->first, h->last);
348 h = h->next;
349 }
350 }
351 #endif
352
353 if ( n->holes == NULL ) {
354 void *data = n->data;
355 n->data_size++;
356 *length = n->data_size;
357 Remove_node(n, 0);
358 dbg_printf("Defragmentation complete - size: %u\n", n->data_size);
359 return data;
360 } else {
361 return NULL;
362 }
363
364 } // End of IPFrag_tree_Update
365
IPFragEntries()366 uint32_t IPFragEntries() {
367 return NumFragments;
368 } // End of IPFragEntries
369