performance optimization for the DOS protection.
authorTobias Brunner <tobias@strongswan.org>
Tue, 25 Nov 2008 13:16:05 +0000 (13:16 -0000)
committerTobias Brunner <tobias@strongswan.org>
Tue, 25 Nov 2008 13:16:05 +0000 (13:16 -0000)
 * half-open SAs per peer are tracked in a hash table
 * charon.dos_protection setting replaced with charon.cookie_threshold and charon.block_threshold
 * chunk_hash function added

src/charon/network/receiver.c
src/charon/sa/ike_sa.c
src/charon/sa/ike_sa_manager.c
src/libstrongswan/chunk.c
src/libstrongswan/chunk.h

index 6a887ec..18a4b4f 100644 (file)
@@ -1,4 +1,5 @@
 /*
+ * Copyright (C) 2008 Tobias Brunner
  * Copyright (C) 2005-2006 Martin Willi
  * Copyright (C) 2005 Jan Hutter
  * Hochschule fuer Technik Rapperswil
 #define COOKIE_LIFETIME 10
 /** how many times to reuse the secret */
 #define COOKIE_REUSE 10000
-/** require cookies after half open IKE_SAs */
-#define COOKIE_TRESHOLD 10
-/** how many half open IKE_SAs per peer before blocking */
-#define BLOCK_TRESHOLD 5
+/** default value for private_receiver_t.cookie_threshold */
+#define COOKIE_THRESHOLD_DEFAULT 10
+/** default value for private_receiver_t.block_threshold */
+#define BLOCK_THRESHOLD_DEFAULT 5
 /** length of the secret to use for cookie calculation */
 #define SECRET_LENGTH 16
 
@@ -98,9 +99,14 @@ struct private_receiver_t {
        hasher_t *hasher;
        
        /**
-        * use denial of service protection mechanisms (cookies)
+        * require cookies after this many half open IKE_SAs
         */
-       bool dos_protection;
+       u_int32_t cookie_threshold;
+       
+       /**
+        * how many half open IKE_SAs per peer before blocking
+        */
+       u_int32_t block_threshold;
 };
 
 /**
@@ -204,12 +210,12 @@ static bool cookie_required(private_receiver_t *this, message_t *message)
        bool failed = FALSE;
                
        if (charon->ike_sa_manager->get_half_open_count(charon->ike_sa_manager,
-                                                                                                       NULL) >= COOKIE_TRESHOLD)
+                                                                                               NULL) >= this->cookie_threshold)
        {
                /* check for a cookie. We don't use our parser here and do it
                 * quick and dirty for performance reasons. 
-                * we assume to cookie is the first payload (which is a MUST), and 
-                * the cookies SPI length is zero. */
+                * we assume the cookie is the first payload (which is a MUST), and 
+                * the cookie's SPI length is zero. */
                packet_t *packet = message->get_packet(message);
                chunk_t data = packet->get_data(packet);
                if (data.len < 
@@ -242,7 +248,7 @@ static bool cookie_required(private_receiver_t *this, message_t *message)
 static bool peer_to_aggressive(private_receiver_t *this, message_t *message)
 {
        if (charon->ike_sa_manager->get_half_open_count(charon->ike_sa_manager,
-                                                               message->get_source(message)) >= BLOCK_TRESHOLD)
+                                               message->get_source(message)) >= this->block_threshold)
        {
                return TRUE;
        }
@@ -287,11 +293,10 @@ static job_requeue_t receive_packets(private_receiver_t *this)
        }
        
        if (message->get_request(message) &&
-               message->get_exchange_type(message) == IKE_SA_INIT &&
-               this->dos_protection)
+               message->get_exchange_type(message) == IKE_SA_INIT)
        {
                /* check for cookies */
-               if (cookie_required(this, message))
+               if (this->cookie_threshold && cookie_required(this, message))
                {
                        u_int32_t now = time(NULL);
                        chunk_t cookie = cookie_build(this, message, now - this->secret_offset,
@@ -319,7 +324,7 @@ static job_requeue_t receive_packets(private_receiver_t *this)
                }
                
                /* check if peer has not too many IKE_SAs half open */
-               if (peer_to_aggressive(this, message))
+               if (this->block_threshold && peer_to_aggressive(this, message))
                {
                        DBG1(DBG_NET, "ignoring IKE_SA setup from %H, "
                                 "peer too aggressive", message->get_source(message));
@@ -373,8 +378,10 @@ receiver_t *receiver_create()
        this->secret_used = 0;
        this->rng->get_bytes(this->rng, SECRET_LENGTH, this->secret);
        memcpy(this->secret_old, this->secret, SECRET_LENGTH);
-       this->dos_protection = lib->settings->get_bool(lib->settings,
-                                                                                               "charon.dos_protection", TRUE);
+       this->cookie_threshold = lib->settings->get_int(lib->settings,
+                                                                       "charon.cookie_threshold", COOKIE_THRESHOLD_DEFAULT);
+       this->block_threshold = lib->settings->get_int(lib->settings,
+                                                                       "charon.block_threshold", BLOCK_THRESHOLD_DEFAULT);
 
        this->job = callback_job_create((callback_job_cb_t)receive_packets,
                                                                        this, NULL, NULL);
index d2eebb8..cc74a95 100644 (file)
@@ -1381,7 +1381,7 @@ static status_t process_message(private_ike_sa_t *this, message_t *message)
                        switch (status)
                        {
                                case NOT_SUPPORTED:
-                                       DBG1(DBG_IKE, "ciritcal unknown payloads found");
+                                       DBG1(DBG_IKE, "critical unknown payloads found");
                                        if (is_request)
                                        {
                                                send_notify_response(this, message, UNSUPPORTED_CRITICAL_PAYLOAD);
index 2bf954b..666bc71 100644 (file)
@@ -1,4 +1,5 @@
 /*
+ * Copyright (C) 2008 Tobias Brunner
  * Copyright (C) 2005-2006 Martin Willi
  * Copyright (C) 2005 Jan Hutter
  * Hochschule fuer Technik Rapperswil
@@ -89,6 +90,11 @@ struct entry_t {
        host_t *other;
        
        /**
+        * As responder: Is this SA half-open?
+        */
+       bool half_open;
+               
+       /**
         * own identity, required for duplicate checking
         */
        identification_t *my_id;
@@ -138,6 +144,7 @@ static entry_t *entry_create(ike_sa_id_t *ike_sa_id)
        this->message_id = -1;
        this->init_hash = chunk_empty;
        this->other = NULL;
+       this->half_open = FALSE;
        this->my_id = NULL;
        this->other_id = NULL;
        
@@ -207,7 +214,43 @@ struct segment_t {
        /* mutex to access a segment exclusively */
        mutex_t *mutex;
        
-       /* the number of items in this segment */
+       /* the number of entries in this segment */
+       u_int count;
+};
+
+typedef struct half_open_t half_open_t;
+
+/**
+ * Struct to manage half-open IKE_SAs per peer.
+ */
+struct half_open_t {
+       /* chunk of remote host address */
+       chunk_t other;
+       
+       /* the number of half-open IKE_SAs with that host */
+       u_int count;
+};
+
+/**
+ * Destroys a half_open_t object.
+ */
+static void half_open_destroy(half_open_t *this)
+{
+       chunk_free(&this->other);
+       free(this);
+}
+
+typedef struct half_open_segment_t half_open_segment_t;
+
+/**
+ * Struct to manage segments of the "half-open" hash table.
+ */
+struct half_open_segment_t {
+       /* rwlock to access a segment exclusively */
+       rwlock_t *lock;
+       
+       /* the number of half-open IKE_SAs in this segment (i.e. the sum of all
+        * half_open_t.count in a segment) */
        u_int count;
 };
 
@@ -253,6 +296,16 @@ struct private_ike_sa_manager_t {
         u_int segment_mask;
         
         /**
+         * Hash table with half_open_t objects.
+         */
+        linked_list_t **half_open_table;
+        
+        /**
+         * Segments of the "half-open" hash table.
+         */
+        half_open_segment_t *half_open_segments;
+        
+        /**
          * RNG to get random SPIs for our side
          */
         rng_t *rng;
@@ -268,7 +321,6 @@ struct private_ike_sa_manager_t {
         bool reuse_ikesa;
 };
 
-
 /**
  * Acquire a lock to access the segment of the table row with the given index.
  * It also works with the segment index directly.
@@ -577,6 +629,88 @@ static bool wait_for_entry(private_ike_sa_manager_t *this, entry_t *entry,
 }
 
 /**
+ * Function that matches half_open_t objects by the given IP address chunk.
+ */
+static bool half_open_match(half_open_t *half_open, chunk_t *addr)
+{
+       return chunk_equals(*addr, half_open->other);
+}
+
+/**
+ * Put a half-open SA into the hash table.
+ */
+static void put_half_open(private_ike_sa_manager_t *this, entry_t *entry)
+{
+       half_open_t *half_open = NULL;
+       linked_list_t *list;
+       chunk_t addr = entry->other->get_address(entry->other);
+       u_int row = chunk_hash(addr) & this->table_mask;
+       u_int segment = row & this->segment_mask;
+       
+       rwlock_t *lock = this->half_open_segments[segment & this->segment_mask].lock;
+       lock->write_lock(lock);
+       if ((list = this->half_open_table[row]) == NULL)
+       {
+               list = this->half_open_table[row] = linked_list_create();
+       }
+       else
+       {
+               half_open_t *current;
+               if (list->find_first(list, (linked_list_match_t)half_open_match,
+                                                        (void**)&current, &addr) == SUCCESS)
+               {
+                       half_open = current;
+                       half_open->count++;
+                       this->half_open_segments[segment].count++;
+               }
+       }
+       
+       if (!half_open)
+       {
+               half_open = malloc_thing(half_open_t);
+               half_open->other = chunk_clone(addr);
+               half_open->count = 1;
+               list->insert_last(list, half_open);
+               this->half_open_segments[segment].count++;
+       }
+       lock->unlock(lock);
+}
+
+/**
+ * Remove a half-open SA from the hash table.
+ */
+static void remove_half_open(private_ike_sa_manager_t *this, entry_t *entry)
+{
+       linked_list_t *list;
+       chunk_t addr = entry->other->get_address(entry->other);
+       u_int row = chunk_hash(addr) & this->table_mask;
+       u_int segment = row & this->segment_mask;
+       
+       rwlock_t *lock = this->half_open_segments[segment & this->segment_mask].lock;
+       lock->write_lock(lock);
+       if ((list = this->half_open_table[row]) != NULL)
+       {
+               half_open_t *current;
+               enumerator_t *enumerator = list->create_enumerator(list);
+               while (enumerator->enumerate(enumerator, &current))
+               {
+                       if (half_open_match(current, &addr))
+                       {
+                               if (--current->count == 0)
+                               {
+                                       list->remove_at(list, enumerator);
+                                       half_open_destroy(current);
+                               }
+                               this->half_open_segments[segment].count--;
+                               break;
+                       }
+               }
+               enumerator->destroy(enumerator);
+       }
+       lock->unlock(lock);
+}
+
+/**
  * Implementation of private_ike_sa_manager_t.get_next_spi.
  */
 static u_int64_t get_next_spi(private_ike_sa_manager_t *this)
@@ -1050,12 +1184,30 @@ static status_t checkin(private_ike_sa_manager_t *this, ike_sa_t *ike_sa)
                /* signal waiting threads */
                entry->checked_out = FALSE;
                entry->message_id = -1;
-               /* apply remote address for DoS detection */
+               /* check if this SA is half-open */
                other = ike_sa->get_other_host(ike_sa);
-               if (!entry->other || !other->equals(other, entry->other))
+               if (entry->half_open && ike_sa->get_state(ike_sa) != IKE_CONNECTING)
+               {
+                       /* not half open anymore */
+                       entry->half_open = FALSE;
+                       remove_half_open(this, entry);
+               }
+               else if (entry->half_open && !other->ip_equals(other, entry->other))
                {
+                       /* the other host's IP has changed, we must update the hash table */
+                       remove_half_open(this, entry);
                        DESTROY_IF(entry->other);
                        entry->other = other->clone(other);
+                       put_half_open(this, entry);
+               }
+               else if (!entry->half_open &&
+                                !entry->ike_sa_id->is_initiator(entry->ike_sa_id) &&
+                                ike_sa->get_state(ike_sa) == IKE_CONNECTING)
+               {
+                       /* this is a new half-open SA */
+                       entry->half_open = TRUE;
+                       entry->other = other->clone(other);
+                       put_half_open(this, entry);
                }
                /* apply identities for duplicate test */
                my_id = ike_sa->get_my_id(ike_sa);
@@ -1122,6 +1274,11 @@ static status_t checkin_and_destroy(private_ike_sa_manager_t *this, ike_sa_t *ik
                        /* they will wake us again when their work is done */
                        entry->condvar->wait(entry->condvar, this->segments[segment].mutex);
                }
+               
+               if (entry->half_open)
+               {
+                       remove_half_open(this, entry);
+               }
        
                remove_entry(this, entry);
                entry_destroy(entry);
@@ -1144,33 +1301,40 @@ static status_t checkin_and_destroy(private_ike_sa_manager_t *this, ike_sa_t *ik
  */
 static int get_half_open_count(private_ike_sa_manager_t *this, host_t *ip)
 {
-       enumerator_t *enumerator;
-       entry_t *entry;
-       u_int segment;
        int count = 0;
 
-       enumerator = create_table_enumerator(this);
-       while (enumerator->enumerate(enumerator, &entry, &segment))
+       if (ip)
        {
-               /* we check if we have a responder CONNECTING IKE_SA without checkout */
-               if (!entry->ike_sa_id->is_initiator(entry->ike_sa_id) &&
-                       entry->ike_sa->get_state(entry->ike_sa) == IKE_CONNECTING)
+               linked_list_t *list;
+               chunk_t addr = ip->get_address(ip);
+               u_int row = chunk_hash(addr) & this->table_mask;
+               u_int segment = row & this->segment_mask;
+               
+               rwlock_t *lock = this->half_open_segments[segment & this->segment_mask].lock;
+               lock->read_lock(lock);
+               if ((list = this->half_open_table[row]) != NULL)
                {
-                       /* if we have a host, count only matching IKE_SAs */
-                       if (ip)
-                       {
-                               if (entry->other && ip->ip_equals(ip, entry->other))
-                               {
-                                       count++;
-                               }
-                       }
-                       else
+                       half_open_t *current;
+                       if (list->find_first(list, (linked_list_match_t)half_open_match,
+                                                                (void**)&current, &addr) == SUCCESS)
                        {
-                               count++;
+                               count = current->count;
                        }
                }
+               lock->unlock(lock);
+       }
+       else
+       {
+               u_int segment;
+               for (segment = 0; segment < this->segment_count; ++segment)
+               {
+                       rwlock_t *lock;
+                       lock = this->half_open_segments[segment & this->segment_mask].lock;
+                       lock->read_lock(lock);
+                       count += this->half_open_segments[segment].count;
+                       lock->unlock(lock);
+               }
        }
-       enumerator->destroy(enumerator);
        
        return count;
 }
@@ -1227,6 +1391,10 @@ static void flush(private_ike_sa_manager_t *this)
        while (enumerator->enumerate(enumerator, &entry, &segment))
        {
                charon->bus->set_sa(charon->bus, entry->ike_sa);
+               if (entry->half_open)
+               {
+                       remove_half_open(this, entry);
+               }
                remove_entry_at((private_enumerator_t*)enumerator);
                entry_destroy(entry);
        }
@@ -1250,13 +1418,21 @@ static void destroy(private_ike_sa_manager_t *this)
                {
                        list->destroy(list);
                }
+               if ((list = this->half_open_table[i]) != NULL)
+               {
+                       list->destroy(list);
+               }
        }
        free(this->ike_sa_table);
+       free(this->half_open_table);
        for (i = 0; i < this->segment_count; ++i)
        {
                this->segments[i].mutex->destroy(this->segments[i].mutex);
+               this->half_open_segments[i].lock->destroy(this->half_open_segments[i].lock);
        }
        free(this->segments);
+       free(this->half_open_segments);
+       
        this->rng->destroy(this->rng);
        this->hasher->destroy(this->hasher);
        free(this);
@@ -1341,6 +1517,17 @@ ike_sa_manager_t *ike_sa_manager_create()
                this->segments[i].count = 0;
        }
        
+       /* we use the same parameters as above for the hash table to track half-open SAs */
+       this->half_open_table = (linked_list_t**)calloc(this->table_size, sizeof(linked_list_t*));
+       memset(this->half_open_table, 0, this->table_size * sizeof(linked_list_t*));
+       
+       this->half_open_segments = (half_open_segment_t*)calloc(this->segment_count, sizeof(half_open_segment_t));
+       for (i = 0; i < this->segment_count; ++i)
+       {
+               this->half_open_segments[i].lock = rwlock_create(RWLOCK_DEFAULT);
+               this->half_open_segments[i].count = 0;
+       }
+       
        this->reuse_ikesa = lib->settings->get_bool(lib->settings,
                                                                                                "charon.reuse_ikesa", TRUE);
        return &this->public;
index 4cd2c57..e234502 100644 (file)
@@ -1,4 +1,5 @@
 /*
+ * Copyright (C) 2008 Tobias Brunner
  * Copyright (C) 2005-2006 Martin Willi
  * Copyright (C) 2005 Jan Hutter
  * Hochschule fuer Technik Rapperswil
 #include <debug.h>
 #include <printf_hook.h>
 
+/* required for chunk_hash */
+#undef get16bits
+#if (defined(__GNUC__) && defined(__i386__))
+#define get16bits(d) (*((const u_int16_t*)(d)))
+#endif
+#if !defined (get16bits)
+#define get16bits(d) ((((u_int32_t)(((const u_int8_t*)(d))[1])) << 8)\
+                      + (u_int32_t)(((const u_int8_t*)(d))[0]) )
+#endif
+
 /**
  * Empty chunk.
  */
@@ -251,7 +262,7 @@ static char hexdig_lower[] = "0123456789abcdef";
  */
 chunk_t chunk_to_hex(chunk_t chunk, char *buf, bool uppercase)
 {
-       int i, len;;
+       int i, len;
        char *hexdig = hexdig_lower;
        
        if (uppercase)
@@ -483,6 +494,75 @@ bool chunk_equals(chunk_t a, chunk_t b)
 }
 
 /**
+ * Described in header.
+ * 
+ * The implementation is based on Paul Hsieh's SuperFastHash:
+ *      http://www.azillionmonkeys.com/qed/hash.html
+ */
+u_int32_t chunk_hash(chunk_t chunk)
+{
+       u_char *data = chunk.ptr;
+       size_t len = chunk.len;
+       u_int32_t hash = len, tmp;
+       int rem;
+       
+       if (!len || data == NULL)
+       {
+               return 0;
+       }
+       
+       rem = len & 3;
+       len >>= 2;
+       
+       /* Main loop */
+       for (; len > 0; --len)
+       {
+               hash += get16bits(data);
+               tmp   = (get16bits(data + 2) << 11) ^ hash;
+               hash  = (hash << 16) ^ tmp;
+               data += 2 * sizeof(u_int16_t);
+               hash += hash >> 11;
+       }
+       
+       /* Handle end cases */
+       switch (rem)
+       {
+               case 3:
+               {
+                       hash += get16bits(data);
+                       hash ^= hash << 16;
+                       hash ^= data[sizeof(u_int16_t)] << 18;
+                       hash += hash >> 11;
+                       break;
+               }
+               case 2:
+               {
+                       hash += get16bits(data);
+                       hash ^= hash << 11;
+                       hash += hash >> 17;
+                       break;
+               }
+               case 1:
+               {
+                       hash += *data;
+                       hash ^= hash << 10;
+                       hash += hash >> 1;
+                       break;
+               }
+       }
+       
+       /* Force "avalanching" of final 127 bits */
+       hash ^= hash << 3;
+       hash += hash >> 5;
+       hash ^= hash << 4;
+       hash += hash >> 17;
+       hash ^= hash << 25;
+       hash += hash >> 6;
+       
+       return hash;
+}
+
+/**
  * output handler in printf() for chunks
  */
 static int chunk_print(FILE *stream, const struct printf_info *info,
index 8d63f60..46ac7db 100644 (file)
@@ -1,4 +1,5 @@
 /*
+ * Copyright (C) 2008 Tobias Brunner
  * Copyright (C) 2005-2008 Martin Willi
  * Copyright (C) 2005 Jan Hutter
  * Hochschule fuer Technik Rapperswil
@@ -200,6 +201,12 @@ int chunk_compare(chunk_t a, chunk_t b);
 bool chunk_equals(chunk_t a, chunk_t b);
 
 /**
+ * Computes a 32 bit hash of the given chunk.
+ * Note: This hash is only intended for hash tables not for cryptographic purposes.
+ */
+u_int32_t chunk_hash(chunk_t chunk);
+
+/**
  * Get printf hooks for a chunk.
  *
  * Arguments are: