nmsg  0.9.0
base/ipreasm.c
1 /*
2  * Copyright (c) 2010-2012 by Farsight Security, Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 /*
18  * ipreasm -- Routines for reassembly of fragmented IPv4 and IPv6 packets.
19  *
20  * Copyright (c) 2007 Jan Andres <jandres@gmx.net>
21  *
22  * Permission to use, copy, modify, and distribute this software for any
23  * purpose with or without fee is hereby granted, provided that the above
24  * copyright notice and this permission notice appear in all copies.
25  */
26 
27 #include "nmsg_port_net.h"
28 
29 #include <assert.h>
30 #include <errno.h>
31 #include <fcntl.h>
32 #include <stdbool.h>
33 #include <stddef.h>
34 #include <stdio.h>
35 #include <stdint.h>
36 #include <stdlib.h>
37 #include <string.h>
38 #include <time.h>
39 #include <unistd.h>
40 
41 #include <pcap.h>
42 
43 #include "ipreasm.h"
44 
45 #define REASM_IP_HASH_SIZE 1021U
46 
47 /*
48  * This struct contains some metadata, the main hash table, and a pointer
49  * to the first entry that will time out. A linked list is kept in the
50  * order in which packets will time out. Using a linked list for this
51  * purpose requires that packets are input in chronological order, and
52  * that a constant timeout value is used, which doesn't change even when
53  * the entry's state transitions from active to invalid.
54  */
55 struct reasm_ip {
56  struct reasm_ip_entry *table[REASM_IP_HASH_SIZE];
57  struct reasm_ip_entry *time_first, *time_last;
58  unsigned waiting, max_waiting, timed_out, dropped_frags;
59  struct timespec timeout;
60 };
61 
62 /*
63  * Hash functions.
64  */
65 static unsigned reasm_ipv4_hash(const struct reasm_id_ipv4 *id);
66 static unsigned reasm_ipv6_hash(const struct reasm_id_ipv6 *id);
67 
68 static void remove_entry(struct reasm_ip *reasm, struct reasm_ip_entry *entry);
69 
70 /*
71  * Dispose of any entries which have expired before "now".
72  */
73 static void process_timeouts(struct reasm_ip *reasm, const struct timespec *now);
74 
75 /*
76  * Create fragment structure from IPv6 packet. Returns NULL if the input
77  * is not a fragment.
78  * This function is called by parse_packet(), don't call it directly.
79  */
80 static struct reasm_frag_entry *frag_from_ipv6(const uint8_t *packet,
81  uint32_t *ip_id, bool *last_frag);
82 
83 /*
84  * Compare packet identification tuples for specified protocol.
85  */
86 static bool reasm_id_equal(enum reasm_proto proto,
87  const union reasm_id *left, const union reasm_id *right);
88 
89 static unsigned
90 reasm_ipv4_hash(const struct reasm_id_ipv4 *id) {
91  unsigned hash = 0;
92  int i;
93 
94  for (i = 0; i < 4; i++) {
95  hash = 37U * hash + id->ip_src[i];
96  hash = 37U * hash + id->ip_dst[i];
97  }
98 
99  hash = 59U * hash + id->ip_id;
100 
101  hash = 47U * hash + id->ip_proto;
102 
103  return (hash);
104 }
105 
106 static unsigned
107 reasm_ipv6_hash(const struct reasm_id_ipv6 *id) {
108  unsigned hash = 0;
109  int i;
110 
111  for (i = 0; i < 16; i++) {
112  hash = 37U * hash + id->ip_src[i];
113  hash = 37U * hash + id->ip_dst[i];
114  }
115 
116  hash = 59U * hash + id->ip_id;
117 
118  return (hash);
119 }
120 
121 bool
122 reasm_ip_next(struct reasm_ip *reasm, const uint8_t *packet, unsigned len,
123  const struct timespec *timestamp, struct reasm_ip_entry **out_entry)
124 {
125  enum reasm_proto proto;
126  union reasm_id id;
127  unsigned hash = 0;
128  bool last_frag = 0;
129  struct reasm_frag_entry *frag;
130  struct reasm_ip_entry *entry;
131 
132  process_timeouts(reasm, timestamp);
133 
134  frag = reasm_parse_packet(packet, len, timestamp, &proto, &id, &hash, &last_frag);
135  if (frag == NULL) {
136  /* some packet that we don't recognize as a fragment */
137  return (false);
138  }
139 
140  hash %= REASM_IP_HASH_SIZE;
141  entry = reasm->table[hash];
142  while (entry != NULL &&
143  (proto != entry->protocol ||
144  !reasm_id_equal(proto, &id, &entry->id)))
145  {
146  entry = entry->next;
147  }
148 
149  if (entry == NULL) {
150  struct reasm_frag_entry *list_head;
151 
152  entry = malloc(sizeof(*entry));
153  if (entry == NULL) {
154  free(frag);
155  abort();
156  }
157 
158  list_head = malloc(sizeof(*list_head));
159  if (list_head == NULL) {
160  free(frag);
161  free(entry);
162  abort();
163  }
164 
165  memset(entry, 0, sizeof(*entry));
166  entry->id = id;
167  entry->len = 0;
168  entry->holes = 1;
169  entry->frags = list_head;
170  entry->hash = hash;
171  entry->protocol = proto;
172  entry->timeout.tv_sec = timestamp->tv_sec + reasm->timeout.tv_sec;
173  entry->state = STATE_ACTIVE;
174  entry->prev = NULL;
175  entry->next = reasm->table[hash];
176  entry->time_prev = reasm->time_last;
177  entry->time_next = NULL;
178 
179  memset(list_head, 0, sizeof(*list_head));
180  list_head->len = 0;
181  list_head->offset = 0;
182  list_head->data_offset = 0;
183  list_head->data = NULL;
184 
185  if (entry->next != NULL)
186  entry->next->prev = entry;
187  reasm->table[hash] = entry;
188 
189  if (reasm->time_last != NULL)
190  reasm->time_last->time_next = entry;
191  else
192  reasm->time_first = entry;
193  reasm->time_last = entry;
194 
195  reasm->waiting++;
196  if (reasm->waiting > reasm->max_waiting)
197  reasm->max_waiting = reasm->waiting;
198  }
199 
200  if (entry->state != STATE_ACTIVE) {
201  reasm->dropped_frags++;
202  free(frag->data);
203  free(frag);
204  *out_entry = NULL;
205  return (true);
206  }
207 
208  if (!reasm_add_fragment(entry, frag, last_frag)) {
209  entry->state = STATE_INVALID;
210  reasm->dropped_frags += entry->frag_count + 1;
211  free(frag->data);
212  free(frag);
213  *out_entry = NULL;
214  return (true);
215  }
216 
217  if (!reasm_is_complete(entry)) {
218  *out_entry = NULL;
219  return (true);
220  }
221 
222  remove_entry(reasm, entry);
223  *out_entry = entry;
224  return (true);
225 }
226 
227 bool
228 reasm_add_fragment(struct reasm_ip_entry *entry, struct reasm_frag_entry *frag, bool last_frag) {
229  bool fit_left, fit_right;
230  struct reasm_frag_entry *cur, *next;
231 
232  /*
233  * When a fragment is inserted into the list, different cases can occur
234  * concerning the number of holes.
235  * - The new fragment can be inserted in the middle of a hole, such that
236  * it will split the hole in two. The number of holes increases by 1.
237  * - The new fragment can be attached to one end of a hole, such that
238  * the rest of the hole remains at the opposite side of the fragment.
239  * The number of holes remains constant.
240  * - The new fragment can fill a hole completely. The number of holes
241  * decreases by 1.
242  */
243 
244  /*
245  * If more fragments follow and the payload size is not an integer
246  * multiple of 8, the packet will never be reassembled completely.
247  */
248  if (!last_frag && (frag->len & 7) != 0)
249  return (false);
250 
251  if (entry->len != 0 && frag->len + frag->offset > entry->len) {
252  /* fragment extends past end of packet */
253  return (false);
254  }
255 
256  fit_left = false;
257  fit_right = false;
258 
259  if (last_frag) {
260  if (entry->len != 0)
261  return (false);
262  entry->len = frag->offset + frag->len;
263  fit_right = true;
264  }
265 
266  cur = entry->frags;
267  next = cur->next;
268 
269  while (cur->next != NULL && cur->next->offset <= frag->offset)
270  cur = cur->next;
271  next = cur->next;
272 
273  /* Fragment is to be inserted between cur and next; next may be NULL. */
274 
275  /* Overlap checks. */
276  if (cur->offset + cur->len > frag->offset) {
277  /* overlaps with cur */
278  return (false);
279  } else if (cur->offset + cur->len == frag->offset) {
280  fit_left = true;
281  }
282 
283  if (next != NULL) {
284  if (last_frag) {
285  /* next extends past end of packet */
286  return (false);
287  }
288  if (frag->offset + frag->len > next->offset) {
289  /* overlaps with next */
290  return (false);
291  }
292  else if (frag->offset + frag->len == next->offset)
293  fit_right = true;
294  }
295 
296  /*
297  * Everything's fine, insert it.
298  */
299  if (frag->len != 0) {
300  frag->next = cur->next;
301  cur->next = frag;
302 
303  if (fit_left && fit_right)
304  entry->holes--;
305  else if (!fit_left && !fit_right)
306  entry->holes++;
307 
308  entry->frag_count++;
309  } else {
310  /*
311  * If the fragment has zero size, we don't insert it into the list,
312  * but one case remains to be handled: If the zero-size fragment
313  * is the last fragment, and fits exactly with the fragment to its
314  * left, the number of holes decreases.
315  */
316  if (last_frag && fit_left)
317  entry->holes--;
318  }
319 
320  return (true);
321 }
322 
323 struct reasm_ip *
324 reasm_ip_new(void) {
325  struct reasm_ip *reasm = malloc(sizeof(*reasm));
326  if (reasm == NULL)
327  return (NULL);
328 
329  memset(reasm, 0, sizeof(*reasm));
330  return (reasm);
331 }
332 
333 void
334 reasm_ip_free(struct reasm_ip *reasm) {
335  while (reasm->time_first != NULL) {
336  struct reasm_ip_entry *entry;
337 
338  entry = reasm->time_first;
339  remove_entry(reasm, entry);
340  reasm_free_entry(entry);
341  }
342  free(reasm);
343 }
344 
345 bool
346 reasm_is_complete(struct reasm_ip_entry *entry) {
347  return (entry->holes == 0);
348 }
349 
350 void
351 reasm_assemble(struct reasm_ip_entry *entry, uint8_t *out_packet, size_t *output_len) {
352  struct reasm_frag_entry *frag = entry->frags->next; /* skip list head */
353  unsigned offset0 = frag->data_offset;
354 
355  switch (entry->protocol) {
356  case PROTO_IPV4:
357  break;
358  case PROTO_IPV6:
359  offset0 -= 8; /* size of frag header */
360  break;
361  default:
362  abort();
363  }
364 
365  if (entry->len + offset0 > *output_len) {
366  /* The output buffer is too small. */
367  *output_len = 0;
368  return;
369  }
370 
371  *output_len = entry->len + offset0;
372 
373  /* copy the (unfragmentable) header from the first fragment received */
374  memcpy(out_packet, frag->data, offset0);
375  if (entry->protocol == PROTO_IPV6)
376  out_packet[frag->last_nxt] = frag->ip6f_nxt;
377 
378  /* join all the payload fragments together */
379  while (frag != NULL) {
380  memcpy(out_packet + offset0 + frag->offset,
381  frag->data + frag->data_offset,
382  frag->len);
383  frag = frag->next;
384  }
385 
386  /* some cleanups, e.g. update the length field of reassembled packet */
387  switch (entry->protocol) {
388  case PROTO_IPV4: {
389  struct nmsg_iphdr *ip_header = (struct nmsg_iphdr *) out_packet;
390  unsigned i, hl = 4 * ip_header->ip_hl;
391  int32_t sum = 0;
392  ip_header->ip_len = htons(offset0 + entry->len);
393  ip_header->ip_off = 0;
394  ip_header->ip_sum = 0;
395 
396  /* Recompute checksum. */
397  for (i = 0; i < hl; i += 2) {
398  uint16_t cur = (uint16_t) out_packet[i] << 8 | out_packet[i + 1];
399  sum += cur;
400  if ((sum & 0x80000000) != 0)
401  sum = (sum & 0xffff) + (sum >> 16);
402  }
403  while ((sum >> 16) != 0)
404  sum = (sum & 0xffff) + (sum >> 16);
405  ip_header->ip_sum = htons(~sum);
406  break;
407  }
408  case PROTO_IPV6: {
409  uint16_t plen = offset0 + entry->len - 40;
410  store_net16(out_packet + offsetof(struct ip6_hdr, ip6_plen), plen);
411  break;
412  }
413  default:
414  abort();
415  }
416 }
417 
418 static void
419 remove_entry(struct reasm_ip *reasm, struct reasm_ip_entry *entry) {
420  if (entry->prev != NULL)
421  entry->prev->next = entry->next;
422  else
423  reasm->table[entry->hash] = entry->next;
424 
425  if (entry->next != NULL)
426  entry->next->prev = entry->prev;
427 
428  if (entry->time_prev != NULL)
429  entry->time_prev->time_next = entry->time_next;
430  else
431  reasm->time_first = entry->time_next;
432 
433  if (entry->time_next != NULL)
434  entry->time_next->time_prev = entry->time_prev;
435  else
436  reasm->time_last = entry->time_prev;
437 
438  reasm->waiting--;
439 }
440 
441 void
442 reasm_free_entry(struct reasm_ip_entry *entry) {
443  struct reasm_frag_entry *frag = entry->frags, *next;
444  while (frag != NULL) {
445  next = frag->next;
446  if (frag->data != NULL)
447  free(frag->data);
448  free(frag);
449  frag = next;
450  }
451  free(entry);
452 }
453 
454 unsigned
455 reasm_ip_waiting(const struct reasm_ip *reasm) {
456  return (reasm->waiting);
457 }
458 
459 unsigned
460 reasm_ip_max_waiting(const struct reasm_ip *reasm) {
461  return (reasm->max_waiting);
462 }
463 
464 unsigned
465 reasm_ip_timed_out(const struct reasm_ip *reasm) {
466  return (reasm->timed_out);
467 }
468 
469 unsigned
470 reasm_ip_dropped_frags(const struct reasm_ip *reasm) {
471  return (reasm->dropped_frags);
472 }
473 
474 bool
475 reasm_ip_set_timeout(struct reasm_ip *reasm, const struct timespec *timeout) {
476  if (reasm->time_first != NULL)
477  return (false);
478  memcpy(&reasm->timeout, timeout, sizeof(*timeout));
479  return (true);
480 }
481 
482 static void
483 process_timeouts(struct reasm_ip *reasm, const struct timespec *now) {
484  while (reasm->time_first != NULL &&
485  reasm->time_first->timeout.tv_sec < now->tv_sec)
486  {
487  struct reasm_ip_entry *entry;
488 
489  entry = reasm->time_first;
490  remove_entry(reasm, entry);
491  reasm_free_entry(entry);
492  reasm->timed_out++;
493  }
494 }
495 
496 static struct reasm_frag_entry *
497 frag_from_ipv6(const uint8_t *packet, uint32_t *ip_id, bool *last_frag) {
498  unsigned offset = 40; /* IPv6 header size */
499  uint8_t nxt;
500  uint16_t total_len;
501  unsigned last_nxt = offsetof(struct ip6_hdr, ip6_nxt);
502  struct reasm_frag_entry *frag;
503  uint8_t *frag_data;
504 
505  nxt = packet[offsetof(struct ip6_hdr, ip6_nxt)];
506  load_net16(packet + offsetof(struct ip6_hdr, ip6_plen), &total_len);
507  total_len += 40;
508 
509  /*
510  * IPv6 extension headers from RFC 2460:
511  * 0 Hop-by-Hop Options
512  * 43 Routing
513  * 44 Fragment
514  * 60 Destination Options
515  *
516  * We look out for the Fragment header; the other 3 header
517  * types listed above are recognized and considered safe to
518  * skip over if they occur before the Fragment header.
519  * Any unrecognized header will cause processing to stop and
520  * a subsequent Fragment header to stay unrecognized.
521  */
522  while (nxt == IPPROTO_HOPOPTS || nxt == IPPROTO_ROUTING || nxt == IPPROTO_DSTOPTS) {
523  unsigned exthdr_len;
524 
525  if (offset + 2 > total_len) {
526  /* header extends past end of packet */
527  return (NULL);
528  }
529 
530  exthdr_len = 8 + 8 * packet[offset + 1];
531  if (offset + exthdr_len > total_len) {
532  /* header extends past end of packet */
533  return NULL;
534  }
535 
536  nxt = packet[offset];
537  last_nxt = offset;
538  offset += exthdr_len;
539  }
540 
541  if (nxt != IPPROTO_FRAGMENT)
542  return (NULL);
543 
544  if (offset + 8 > total_len) {
545  /* Fragment header extends past end of packet */
546  return (NULL);
547  }
548 
549  frag = malloc(sizeof(*frag));
550  if (frag == NULL)
551  abort();
552 
553  struct ip6_frag frag_hdr;
554  memcpy(&frag_hdr, packet + offset, sizeof(struct ip6_frag));
555  offset += 8;
556 
557  frag_data = malloc(total_len);
558  if (frag_data == NULL)
559  abort();
560  memcpy(frag_data, packet, total_len);
561 
562  memset(frag, 0, sizeof(*frag));
563  frag->last_nxt = last_nxt;
564  frag->ip6f_nxt = frag_hdr.ip6f_nxt;
565  frag->len = total_len - offset;
566  frag->data_offset = offset;
567  frag->offset = ntohs(frag_hdr.ip6f_offlg & IP6F_OFF_MASK);
568  frag->data = frag_data;
569 
570  *ip_id = ntohl(frag_hdr.ip6f_ident);
571  *last_frag = (frag_hdr.ip6f_offlg & IP6F_MORE_FRAG) == 0;
572 
573  return (frag);
574 }
575 
576 static bool
577 reasm_id_equal(enum reasm_proto proto, const union reasm_id *left, const union reasm_id *right)
578 {
579  switch (proto) {
580  case PROTO_IPV4:
581  return (memcmp(left->ipv4.ip_src, right->ipv4.ip_src, 4) == 0 &&
582  memcmp(left->ipv4.ip_dst, right->ipv4.ip_dst, 4) == 0 &&
583  left->ipv4.ip_id == right->ipv4.ip_id &&
584  left->ipv4.ip_proto == right->ipv4.ip_proto);
585  case PROTO_IPV6:
586  return (memcmp(left->ipv6.ip_src, right->ipv6.ip_src, 16) == 0 &&
587  memcmp(left->ipv6.ip_dst, right->ipv6.ip_dst, 16) == 0 &&
588  left->ipv6.ip_id == right->ipv6.ip_id);
589  default:
590  abort();
591  }
592 }
593 
594 struct reasm_frag_entry *
595 reasm_parse_packet(const uint8_t *packet, unsigned len,
596  const struct timespec *ts,
597  enum reasm_proto *protocol, union reasm_id *id,
598  unsigned *hash, bool *last_frag)
599 {
600  const struct nmsg_iphdr *ip_header = (const struct nmsg_iphdr *) packet;
601  struct reasm_frag_entry *frag = NULL;
602 
603  switch (ip_header->ip_v) {
604  case 4: {
605  uint16_t offset = ntohs(ip_header->ip_off);
606 
607  *protocol = PROTO_IPV4;
608  if (len >= (unsigned) ntohs(ip_header->ip_len) &&
609  (offset & (IP_MF | IP_OFFMASK)) != 0)
610  {
611  unsigned pl_hl, pl_len, pl_off;
612  u_char *frag_data;
613 
614  frag = malloc(sizeof(*frag));
615  if (frag == NULL)
616  abort();
617 
618  pl_hl = ip_header->ip_hl * 4;
619  pl_len = ntohs(ip_header->ip_len);
620  pl_off = (offset & IP_OFFMASK) * 8;
621  frag_data = malloc(pl_len);
622  if (frag_data == NULL)
623  abort();
624  memcpy(frag_data, packet, pl_len);
625 
626  frag->len = pl_len - pl_hl;
627  frag->offset = pl_off;
628  frag->data_offset = ip_header->ip_hl * 4;
629  frag->data = frag_data;
630 
631  *last_frag = (offset & IP_MF) == 0;
632 
633  memcpy(id->ipv4.ip_src, &ip_header->ip_src, 4);
634  memcpy(id->ipv4.ip_dst, &ip_header->ip_dst, 4);
635  id->ipv4.ip_id = ntohs(ip_header->ip_id);
636  id->ipv4.ip_proto = ip_header->ip_p;
637 
638  *hash = reasm_ipv4_hash(&id->ipv4);
639  }
640  break;
641  }
642 
643  case 6: {
644  uint16_t plen;
645  load_net16(packet + offsetof(struct ip6_hdr, ip6_plen), &plen);
646  *protocol = PROTO_IPV6;
647  if (len >= plen + 40U)
648  frag = frag_from_ipv6(packet, &id->ipv6.ip_id, last_frag);
649  if (frag != NULL) {
650  memcpy(id->ipv6.ip_src,
651  packet + offsetof(struct ip6_hdr, ip6_src), 16);
652  memcpy(id->ipv6.ip_dst,
653  packet + offsetof(struct ip6_hdr, ip6_dst), 16);
654  *hash = reasm_ipv6_hash(&id->ipv6);
655  }
656  break;
657  }
658 
659  default:
660  break;
661  }
662 
663  if (frag != NULL)
664  memcpy(&frag->ts, ts, sizeof(*ts));
665 
666  return (frag);
667 }