libnids的哈希及查找

桃扇骨 2022-08-05 12:20 240阅读 0赞

# 哈希的键值    #

在Libnids中对tcp数据流的哈希关键字是“源IP、源端口、目的IP、目的端口”：

//该结构描述地址及端口
    struct tuple4       
    {
      u_short source;   //源端口
      u_short dest;     //目的端口
      u_int saddr;      //源IP
      u_int daddr;      //目的IP
    };

# 哈希表结构 #

这里的哈希表是由tcp\_stream\_table定义的：

static struct tcp_stream **tcp_stream_table;

tcp\_stream\_table存放的是指针，这些指针分别指向了一个双向链表，双向链表的节点存的是一个个的tcp\_stream，而tcp\_stream里含有指针，指向了half\_stream；在half\_stream里存放的才是tcp流的数据。每次一个新的tcp数据流到达，将其插入到双向链表的表头位置。

# 哈希函数及哈希表长度 #

文件“tcp.c"中通过如下函数实现哈希，它调用的函数mkhash在源文件hash.c中，参考文章：[Libnids的哈希函数][Libnids]

//该函数调用mkhash将源/目的IP和端口号hash为一个int数，该数已经
    //具有了足够的随机性，然后在通过取余操作得到其在哈希表中的位置
    static int
    mk_hash_index(struct tuple4 addr)
    {
      int hash=mkhash(addr.saddr, addr.source, addr.daddr, addr.dest);
      return hash % tcp_stream_table_size;
    }

某次捕获并还原tcp数据流之前，将mk\_hash\_index函数添加如下输出信息，重新安装Libnids（安装过程参考 [Libnids在Ubuntu下的安装][Libnids_Ubuntu] ）：

static int
    mk_hash_index(struct tuple4 addr)
    {
      struct sockaddr_in saddr, daddr;
      saddr.sin_addr.s_addr = addr.saddr;
      daddr.sin_addr.s_addr = addr.daddr;
      char ip[20];
      printf("ip, port: %s %d, %s %d\n", inet_ntoa(saddr.sin_addr), addr.source,
               inet_ntop(AF_INET, &daddr.sin_addr,ip,sizeof(ip)), addr.dest);
      int hash=mkhash(addr.saddr, addr.source, addr.daddr, addr.dest);
      printf("hash: %d, tcp_stream_table_size#: %d\n\n", hash, tcp_stream_table_size);
      return hash % tcp_stream_table_size;
    }

此时捕获并还原tcp流，可以得到如下的部分截图信息：由图可以看出，哈希表长度为1040，以及每次hash后的数值：  
![Center][]

# 哈希表的查找 #

struct tcp_stream *
    find_stream(struct tcphdr * this_tcphdr, struct ip * this_iphdr,
    	    int *from_client)
    {
      struct tuple4 this_addr, reversed;
      struct tcp_stream *a_tcp;
    
      this_addr.source = ntohs(this_tcphdr->th_sport);
      this_addr.dest = ntohs(this_tcphdr->th_dport);
      this_addr.saddr = this_iphdr->ip_src.s_addr;
      this_addr.daddr = this_iphdr->ip_dst.s_addr;
      a_tcp = nids_find_tcp_stream(&this_addr);
      if (a_tcp) {
        *from_client = 1;
        return a_tcp;
      }
      reversed.source = ntohs(this_tcphdr->th_dport);
      reversed.dest = ntohs(this_tcphdr->th_sport);
      reversed.saddr = this_iphdr->ip_dst.s_addr;
      reversed.daddr = this_iphdr->ip_src.s_addr;
      a_tcp = nids_find_tcp_stream(&reversed);
      if (a_tcp) {
        *from_client = 0;
        return a_tcp;
      }
      return 0;
    }

struct tcp_stream *
    nids_find_tcp_stream(struct tuple4 *addr)
    {
      int hash_index;
      struct tcp_stream *a_tcp;
    
      hash_index = mk_hash_index(*addr);
      for (a_tcp = tcp_stream_table[hash_index];
           a_tcp && memcmp(&a_tcp->addr, addr, sizeof (struct tuple4));
           a_tcp = a_tcp->next_node);
      return a_tcp ? a_tcp : 0;
    }

# 哈希表的插入 #

如果一个数据报是正常的数据报，但是在哈希表中没有找到该数据报对应的数据流（这是三次握手的第一个数据报，标志着一个新的tcp连接的开始），那么就使用该函数添加该数据报到哈希表中。**哈希表处理冲突的方法是使用双向链表**，如果新来的tcp流发生冲突，**将这个新tcp流插入到双向链表的表头**。

static void
    add_new_tcp(struct tcphdr * this_tcphdr, struct ip * this_iphdr)
    {
      struct tcp_stream *tolink;
      struct tcp_stream *a_tcp;
      int hash_index;
      struct tuple4 addr;
      
      addr.source = ntohs(this_tcphdr->th_sport);
      addr.dest = ntohs(this_tcphdr->th_dport);
      addr.saddr = this_iphdr->ip_src.s_addr;
      addr.daddr = this_iphdr->ip_dst.s_addr;
      hash_index = mk_hash_index(addr);
      
      //如果该tcp流中数据报数量超过了阈值，需要先释放空间
      if (tcp_num > max_stream) {
        struct lurker_node *i;
        int orig_client_state=tcp_oldest->client.state;
        tcp_oldest->nids_state = NIDS_TIMED_OUT;
        for (i = tcp_oldest->listeners; i; i = i->next)
          (i->item) (tcp_oldest, &i->data);
        nids_free_tcp_stream(tcp_oldest);
        if (orig_client_state!=TCP_SYN_SENT)
          nids_params.syslog(NIDS_WARN_TCP, NIDS_WARN_TCP_TOOMUCH, ugly_iphdr, this_tcphdr);
      }
      a_tcp = free_streams;
      if (!a_tcp) {
        fprintf(stderr, "gdb me ...\n");
        pause();
      }
      free_streams = a_tcp->next_free;
      
      tcp_num++;  //tcp流数量加1
      //更新tcp流的相关信息
      tolink = tcp_stream_table[hash_index];
      memset(a_tcp, 0, sizeof(struct tcp_stream));
      a_tcp->hash_index = hash_index;
      a_tcp->addr = addr;
      a_tcp->client.state = TCP_SYN_SENT;
      a_tcp->client.seq = ntohl(this_tcphdr->th_seq) + 1;
      a_tcp->client.first_data_seq = a_tcp->client.seq;
      a_tcp->client.window = ntohs(this_tcphdr->th_win);
      a_tcp->client.ts_on = get_ts(this_tcphdr, &a_tcp->client.curr_ts);
      a_tcp->client.wscale_on = get_wscale(this_tcphdr, &a_tcp->client.wscale);
      a_tcp->server.state = TCP_CLOSE;
      a_tcp->next_node = tolink;
      a_tcp->prev_node = 0;
      if (tolink)
        tolink->prev_node = a_tcp;
      tcp_stream_table[hash_index] = a_tcp;
      a_tcp->next_time = tcp_latest; 
      a_tcp->prev_time = 0;
      if (!tcp_oldest)
        tcp_oldest = a_tcp;
      if (tcp_latest)
        tcp_latest->prev_time = a_tcp;
      tcp_latest = a_tcp;  //将最新插入哈希表的流更新为当前流
    }

# 删除tcp流时对hash表的处理 #

//删除tcp数据流并释放空间
    void
    nids_free_tcp_stream(struct tcp_stream * a_tcp)
    {
      //在tcp_stream的结构中记录了该tcp流的hash index，这里要使用该值
      int hash_index = a_tcp->hash_index;
      struct lurker_node *i, *j;
    
      del_tcp_closing_timeout(a_tcp);
      //分别删除两个方向上的half_stream
      purge_queue(&a_tcp->server);
      purge_queue(&a_tcp->client);
       
      //从hash表中删除该tcp流并释放空间
      if (a_tcp->next_node)
        a_tcp->next_node->prev_node = a_tcp->prev_node;
      if (a_tcp->prev_node)
        a_tcp->prev_node->next_node = a_tcp->next_node;
      else
        tcp_stream_table[hash_index] = a_tcp->next_node;
      if (a_tcp->client.data)
        free(a_tcp->client.data);
      if (a_tcp->server.data)
        free(a_tcp->server.data);
      if (a_tcp->next_time)
        a_tcp->next_time->prev_time = a_tcp->prev_time;
      if (a_tcp->prev_time)
        a_tcp->prev_time->next_time = a_tcp->next_time;
      if (a_tcp == tcp_oldest)
        tcp_oldest = a_tcp->prev_time;
      if (a_tcp == tcp_latest)
        tcp_latest = a_tcp->next_time;
      
      i = a_tcp->listeners;
      
      while (i) {
        j = i->next;
        free(i);
        i = j;
      }
      a_tcp->next_free = free_streams;
      free_streams = a_tcp;
      tcp_num--; //删除了tcp流后，当前的tcp流数量减1
    }

[Libnids]: http://blog.csdn.net/u013074465/article/details/45061605
[Libnids_Ubuntu]: http://blog.csdn.net/u013074465/article/details/45055823
[Center]: /images/20220805/e9505ccba0d8474f8db6bd87d42aa77c.png