2

I have a list of IP addresses, stored like this:

char IP_addresses_list[] = {
    "157.55.130", /* 157.55.130.0/24 */
    "157.56.52",  /* 157.56.52.0/24 */
    "157.12.53",  /* 157.12.53.0/24 */
    ...
};

I get the IP address from the sniffed packet (casting it to struct iphdr *iph = (struct iphdr *)(packet + sizeof(struct ether_header)); I convert it in a character string using inet_ntop; finally, I compare the IP address from the packet with the ones in the list with the following code:

/* 
* input: IP address to search in the list
* output: 1 if IP address is found in the list, 0 otherwise
*/
int find_IP_addr(char *server) {
    int ret = 0;
    int i, string_size1, string_size2;
    char *copied_server, *copied_const_char;
    char *save_ptr1, *save_ptr2;
    char dot[2] = ".";
    /* Here I store the IP address from the packet */
    char first_IPaddr_pkt[4], second_IPaddr_pkt[4], third_IPaddr_pkt[4];
    /* Here I store the IP address from the list */
    char first_IPaddr_list[4], second_IPaddr_list[4], third_IPaddr_list[4];

    string_size1 = strlen(server)+1;
    copied_server = (char *)malloc(string_size1 * sizeof(char));
    strcpy(copied_server, server);

    /* I store and compare the first three bits of the IP address */
    strcpy(first_IPaddr_pkt, strtok_r(copied_server, dot, &save_ptr1));
    strcpy(second_IPaddr_pkt, strtok_r(NULL, dot, &save_ptr1));
    strcpy(third_IPaddr_pkt, strtok_r(NULL, dot, &save_ptr1));  
    printf("tokenized %s, %s and %s\n", first_IPaddr_pkt, second_IPaddr_pkt, third_IPaddr_pkt);

    /* Now I scan the list */
    for (i=0; i<LIST_LENGTH; i++) {
        /* I copy an address from the list */
        string_size2 = strlen(IP_addresses_list[i])+1; // +1 for null character
        copied_const_char = (char *)malloc(string_size2 * sizeof(char));
        strcpy(copied_const_char, IP_addresses_list[i]);
        /* Let's split the address from the list */
        strcpy(first_IPaddr_list, strtok_r(copied_const_char, dot, &save_ptr2));
        strcpy(second_IPaddr_list, strtok_r(NULL, dot, &save_ptr2));
        strcpy(third_IPaddr_list, strtok_r(NULL, dot, &save_ptr2)); 
        printf("tokenized %s, %s and %s\n", first_IPaddr_list, second_IPaddr_list, third_IPaddr_list);
        /* I compare the first byte of the address from the packet I got and 
        the first byte of the address from the list:
        if they are different, there's no reason to continue comparing 
        the other bytes of the addresses */
        if (strcmp(first_IPaddr_pkt, first_IPaddr_list) != 0) {
            continue;
        }
        else  {
            if (strcmp(second_IPaddr_pkt, second_IPaddr_list) != 0) {
                continue;
        }
        else {
            if (strcmp(third_IPaddr_pkt, third_IPaddr_list) != 0) {
                continue;
            }
            else
                /* All the bytes are the same! */
                ret = 1;
            }
        }
        free(copied_const_char);
    }
    free(copied_server);
    return ret;
}

I'd like to make this more fast, without using strtok, strcmp, malloc or free. In /usr/include/netinet/ip.h I see that addresses are

u_int32_t saddr;
u_int32_t daddr;

is it possible to compare without even using inet_ntop first, maybe just comparing the two addresses while they still are u_int32_t?

EDIT: here's a solution example for whoever will read this question.

#include <stdio.h>
#include <sys/types.h>

int main() {

    // In the list I have: 104.40.0.0./13
    int cidr = 13;
    u_int32_t ipaddr_from_pkt = 1747488105;     // pkt coming from 104.40.141.105
    u_int32_t ipaddr_from_list = 1747451904;    // 104.40.0.0
    int mask = (-1) << (32 - cidr);

    if ((ipaddr_from_pkt & mask) == ipaddr_from_list)
        printf("IP address belongs to the given range!!!\n");
    else printf ("failure\n");

    return 0;
}

Thanks to iharob too for the bsearch hint.

elmazzun
  • 1,066
  • 2
  • 18
  • 44
  • none of these are valid IPv4 addresses, so I'd first convert them to something that looks like one and then just use the standard networking libraries – Marcus Müller Oct 09 '15 at 15:25
  • 2
    That's a lot of code for just ip address comparison!. Yes don't use `malloc()`/`free()` and there is no reasonable reason to need `strtok()`. – Iharob Al Asimi Oct 09 '15 at 15:27
  • "is it possible to compare without even using `inet_ntop` first, maybe just comparing the two addresses while they still are `u_int32_t`?" Why **wouldn't** comparing to 32-bit unsigned `int` values be valid? – Andrew Henle Oct 09 '15 at 15:28
  • When are new programmers going to care about *readability*, you made me think your code was wrong and hence give a wrong answer. `strlen(server)+1` I didn't see the `+1` because it's too close to the other characters thus looking like a single object. – Iharob Al Asimi Oct 09 '15 at 15:31

4 Answers4

3

I would avoid converting the binary data to strings. If you keep them binary then it's quite easy to compare:

match = (ip & listed_mask) == listed_ip;

"/24" is a mask. Means inly 24 highest bits are relevant. You convert it to binary mask as follows:

listed_mask = (-1) << (32 - 24);
PineForestRanch
  • 473
  • 2
  • 11
  • I'm not good with masks and logical operators: could you explain your code please? – elmazzun Oct 09 '15 at 15:55
  • 1
    /24 is a mask. You use it to compute "listed_mask" - see above. Then you use the mask to mask out the irrelevant 8 bits of the ip with the & operation. This replaces rhe irrelevant bits with zeroes. You compre the result to the listed_ip from your list (which is already masked) and if it's equal you've found the match. – PineForestRanch Oct 09 '15 at 16:01
1

The performance issues have nothing to do with strcmp(), malloc() is unnecessary though.

If you are only using IPv4 addresses you only need 16 characters to store it so you can remove malloc() and declare the temporary storage as an array.

But there is an important improvement if there are going to be many ip addresses in the list.

First you need to sort the list of IP addresses, and then use bsearch() to search for the right IP. This way the code will run in O(log(2n)) time which is a lot faster than O(N), specially for large N

Iharob Al Asimi
  • 52,653
  • 6
  • 59
  • 97
0

My approach here would be:

  1. simply use a strncat with ".0" to build valid IPv4 addresses.
  2. use getaddrinfo with constant values for socket type etc to build a addrinfo struct
  3. compare the relevant fields of the addrinfo.

Basically, the example from man getaddrinfo does all this.

Marcus Müller
  • 34,677
  • 4
  • 53
  • 94
  • I wrote "157.55.130" because I meant to say "157.55.130.0/24": I don't want to write the whole range of addresses from 157.55.130.0 to 157.55.130.255. If I get a packet coming from 157.55.130.45, I compare just the first three bytes of the address (157.55.130), and this string is in the list. – elmazzun Oct 09 '15 at 15:45
  • 1
    you don't have to follow my advice, but letting a standard library functionality do your job with well-formed addresses is definitely what I'd prefer above your long hand-comparison solution. I consider using the *tools that were designed for the job* smart, in this case *using a standard library function designed to understand strings representing IP addresses* is much smarter than writing your own, potentially bug-ridden version. Assuming you don't have to parse millions of addresses per second, the overhead will be absolutely negligible on any machine I can think of. – Marcus Müller Oct 09 '15 at 15:55
-1

The fastest way would be to store addresses in a dictionary, see this link

Community
  • 1
  • 1
S van Balen
  • 288
  • 2
  • 11