Swap from Aho-Corasick to an experimental/home-grown algorithm that uses a probabilistic

approach for handling Internet domain names.

For switching back to Aho-Corasick it is necessary to edit
ndpi-typedefs.h and uncomment the line
// #define USE_LEGACY_AHO_CORASICK

[1] With Aho-Corasick
$ ./example/ndpiReader -G ./lists/ -i tests/pcap/ookla.pcap | grep Memory
nDPI Memory statistics:
nDPI Memory (once):      37.34 KB
Flow Memory (per flow):  960 B
Actual Memory:           33.09 MB
Peak Memory:             33.09 MB

[2] With the new algorithm
$ ./example/ndpiReader -G ./lists/ -i tests/pcap/ookla.pcap | grep Memory
nDPI Memory statistics:
nDPI Memory (once):      37.31 KB
Flow Memory (per flow):  960 B
Actual Memory:           7.42 MB
Peak Memory:             7.42 MB

In essence from ~33 MB to ~7 MB

This new algorithm will enable larger lists to be loaded (e.g. top 1M domans
https://s3-us-west-1.amazonaws.com/umbrella-static/index.html)

In ./lists there are file names that are named as <category>_<string>.list
With -G ndpiReader can load all of them at startup

5 files changed, 199 insertions, 20 deletions

diff --git a/src/include/ndpi_api.h b/src/include/ndpi_api.h
index 941578f47..7f4208ad0 100644
--- a/src/include/ndpi_api.h
+++ b/src/include/ndpi_api.h
@@ -808,6 +808,30 @@ extern "C" {
   int ndpi_load_categories_file(struct ndpi_detection_module_struct *ndpi_str, const char* path, void *user_data);
 
   /**
+   * Loads a file (separated by <cr>) of domain names associated with the specified category
+   *
+   * @par     ndpi_mod    = the detection module
+   * @par     path        = the path of the file
+   * @par     category_id = Id of the category to which domains will be associated
+   * @return  0 if the file is loaded correctly;
+   *          -1 else
+   */
+  int ndpi_load_category_file(struct ndpi_detection_module_struct *ndpi_str,
+			      char* path, ndpi_protocol_category_t category_id);
+  
+  /**
+   * Load files (whose name is <categoryid>_<label>.<extension>) stored
+   * in a directory and bind each domain to the specified category.
+   *
+   * @par     ndpi_mod    = the detection module
+   * @par     path        = the path of the file
+   * @return  0 if the file is loaded correctly;
+   *          -1 else
+   */
+  int ndpi_load_categories_dir(struct ndpi_detection_module_struct *ndpi_str,
+			       char* path);
+
+  /**
    * Read a file and load the list of risky domains
    *
    * @par     ndpi_mod = the detection module
diff --git a/src/include/ndpi_protocol_ids.h b/src/include/ndpi_protocol_ids.h
index dda9b7acd..d3db7726d 100644
--- a/src/include/ndpi_protocol_ids.h
+++ b/src/include/ndpi_protocol_ids.h
@@ -367,7 +367,7 @@ typedef enum {
   NDPI_PROTOCOL_HOTS                  = 336, /* Heroes of the Storm */
   NDPI_PROTOCOL_FACEBOOK_REEL_STORY   = 337,
   NDPI_PROTOCOL_SRTP                  = 338,
-  NDPI_PROTOCOL_GAMBLING              = 339,
+  NDPI_PROTOCOL_FREE                  = 339, /* Formerly used by gambling now a category. It can be reused in the future */
   NDPI_PROTOCOL_EPICGAMES             = 340,
   NDPI_PROTOCOL_GEFORCENOW            = 341,
   NDPI_PROTOCOL_NVIDIA                = 342,
diff --git a/src/include/ndpi_typedefs.h b/src/include/ndpi_typedefs.h
index 523ba4aec..75df402ef 100644
--- a/src/include/ndpi_typedefs.h
+++ b/src/include/ndpi_typedefs.h
@@ -31,7 +31,7 @@
 /* Used by both nDPI core and patricia code under third-party */
 #include "ndpi_patricia_typedefs.h"
 
-#define USE_LEGACY_AHO_CORASICK
+// #define USE_LEGACY_AHO_CORASICK
 
 #ifndef NDPI_CFFI_PREPROCESSING
 #ifndef u_char
@@ -1101,6 +1101,9 @@ typedef enum {
     Crypto Currency e.g Bitcoin, Litecoin, Etherum ..et.
   */
   NDPI_PROTOCOL_CATEGORY_CRYPTO_CURRENCY = 106,
+
+  /* Gambling websites */
+  NDPI_PROTOCOL_CATEGORY_GAMBLING = 107,
   
   /*
     IMPORTANT
diff --git a/src/lib/ndpi_domain_classify.c b/src/lib/ndpi_domain_classify.c
index d94d692fa..8b66c940e 100644
--- a/src/lib/ndpi_domain_classify.c
+++ b/src/lib/ndpi_domain_classify.c
@@ -48,7 +48,8 @@ typedef struct {
   ndpi_domain_classify_t *class[MAX_NUM_NDPI_DOMAIN_CLASSIFICATIONS];
 } ndpi_domain_classifications_t;
 
-//#define DEBUG
+// #define DEBUG_ADD
+// #define DEBUG_CONTAINS
 
 /* ********************************************************** */
 
@@ -133,7 +134,14 @@ static bool ndpi_domain_search_add(ndpi_domain_search *search, char *domain) {
 
   if(domain == NULL)              return(false);
   if((len = strlen(domain)) == 0) return(false);
-  if(domain[len-1] == '.') domain[len-1] = '0';
+
+  len--;
+  while((len > 0)
+	&& ((domain[len] == '.')
+	    || (domain[len] == '\n')
+	    || (domain[len] == '\r'))
+	)
+    domain[len--] = '\0';
 
   if(domain[0] == '.') ++domain;
 
@@ -178,7 +186,9 @@ static bool ndpi_domain_search_contains(ndpi_domain_search *search, char *domain
   u_int32_t bitmap_id = 0;
   bool quit = false;
 
-  elem = strrchr(domain, '.');
+  if((elem = strrchr(domain, '.')) == NULL)
+    return(false); /* This does not look like a domain */
+  
   while(elem) {
     u_int32_t h;
 
@@ -263,8 +273,12 @@ bool ndpi_domain_classify_add(ndpi_domain_classify *_s,
 			      char *domain) {
   u_int32_t i;
   ndpi_domain_classifications_t *s = (ndpi_domain_classifications_t*)_s;
-  char buf[256];
+  char buf[256], *dot = strrchr(domain, '.');
 
+  if(!dot) return(false);
+  if((!strcmp(dot, ".arpa")) || (!strcmp(dot, ".local")))
+    return(false);
+  
   for(i=0; i<MAX_NUM_NDPI_DOMAIN_CLASSIFICATIONS; i++) {
     if(s->class[i] != NULL) {
       if(s->class[i]->class_id == class_id) {
@@ -277,7 +291,7 @@ bool ndpi_domain_classify_add(ndpi_domain_classify *_s,
 	return(false);
 
       s->class[i]->class_id = class_id;
-      s->class[i]->domains     =  ndpi_domain_search_alloc();
+      s->class[i]->domains  =  ndpi_domain_search_alloc();
       break;
     }
   }
@@ -287,7 +301,7 @@ bool ndpi_domain_classify_add(ndpi_domain_classify *_s,
 
   snprintf(buf, sizeof(buf), "%s", domain);
 
-#ifdef DEBUG
+#ifdef DEBUG_ADD
   printf("[add] %s @ %u\n", domain, class_id);
 #endif
 
@@ -356,18 +370,48 @@ u_int32_t ndpi_domain_classify_add_domains(ndpi_domain_classify *_s,
 
 /* ********************************************************** */
 
+static bool is_valid_domain_char(u_char c) {
+  if(((c >= 'A')&& (c <= 'Z'))
+     || ((c >= 'a')&& (c <= 'z'))
+     || ((c >= '0')&& (c <= '9'))
+     || (c == '_')
+     || (c == '-')
+     || (c == '.'))
+    return(true);
+  else
+    return(false);
+}
+
+/* ********************************************************** */
+
 u_int16_t ndpi_domain_classify_contains(ndpi_domain_classify *_s,
 					char *domain) {
   u_int32_t i, len;
   ndpi_domain_classifications_t *s = (ndpi_domain_classifications_t*)_s;
+  char *dot;
 
-  if(!domain)                     return(0);
-  if((len = strlen(domain)) == 0) return(0);
+  if(!domain)                                             return(0);
+  if((len = strlen(domain)) == 0)                         return(0);
+  if((dot = strrchr(domain, '.')) == NULL)                return(0);
+  if((!strcmp(dot, ".arpa")) || (!strcmp(dot, ".local"))) return(0);
 
   /* This is a number or a numeric IP or similar */
-  if(isdigit(domain[len-1]) && isdigit(domain[0]))
+  if(isdigit(domain[len-1]) && isdigit(domain[0])) {
+#ifdef DEBUG_CONTAINS
+    printf("[contains] %s INVALID\n", domain);
+#endif
+
     return(0);
+  }
+  
+  if(!is_valid_domain_char(domain[0])) {
+#ifdef DEBUG_CONTAINS
+    printf("[contains] %s INVALID\n", domain);
+#endif
 
+    return(0);
+  }
+  
   for(i=0; i<MAX_NUM_NDPI_DOMAIN_CLASSIFICATIONS; i++) {
     if(s->class[i] != NULL) {
       char buf[256];
@@ -375,16 +419,16 @@ u_int16_t ndpi_domain_classify_contains(ndpi_domain_classify *_s,
       snprintf(buf, sizeof(buf), "%s", domain);
       
       if(ndpi_domain_search_contains(s->class[i]->domains, buf)) {
-#ifdef DEBUG
-	printf("[search] %s = %d\n", domain, s->class[i]->class_id);
+#ifdef DEBUG_CONTAINS
+	printf("[contains] %s = %d\n", domain, s->class[i]->class_id);
 #endif
 	return(s->class[i]->class_id);
       }
     }
   }
 
-#ifdef DEBUG
-  printf("[search] %s NOT FOUND\n", domain);
+#ifdef DEBUG_CONTAINS
+  printf("[contains] %s NOT FOUND\n", domain);
 #endif
 
   return(0);
diff --git a/src/lib/ndpi_main.c b/src/lib/ndpi_main.c
index 0df5e61f7..d1c4e3746 100644
--- a/src/lib/ndpi_main.c
+++ b/src/lib/ndpi_main.c
@@ -24,6 +24,7 @@
 #include <stdlib.h>
 #include <errno.h>
 #include <sys/types.h>
+#include <dirent.h>
 
 #define NDPI_CURRENT_PROTO NDPI_PROTOCOL_UNKNOWN
 
@@ -2122,10 +2123,6 @@ static void ndpi_init_protocol_defaults(struct ndpi_detection_module_struct *ndp
 			  "BITCOIN", NDPI_PROTOCOL_CATEGORY_CRYPTO_CURRENCY,
 			  ndpi_build_default_ports(ports_a, 8333, 0, 0, 0, 0) /* TCP */,
 			  ndpi_build_default_ports(ports_b, 0, 0, 0, 0, 0) /* UDP */);
-  ndpi_set_proto_defaults(ndpi_str, 0 /* encrypted */, 1 /* app proto */, NDPI_PROTOCOL_ACCEPTABLE, NDPI_PROTOCOL_GAMBLING,
-			  "Gambling", NDPI_PROTOCOL_CATEGORY_WEB,
-			  ndpi_build_default_ports(ports_a, 0, 0, 0, 0, 0) /* TCP */,
-			  ndpi_build_default_ports(ports_b, 0, 0, 0, 0, 0) /* UDP */);
   ndpi_set_proto_defaults(ndpi_str, 0 /* encrypted */, 1 /* app proto */, NDPI_PROTOCOL_ACCEPTABLE, NDPI_PROTOCOL_PROTONVPN,
 			  "ProtonVPN", NDPI_PROTOCOL_CATEGORY_VPN,
 			  ndpi_build_default_ports(ports_a, 0, 0, 0, 0, 0) /* TCP */,
@@ -2147,6 +2144,10 @@ static void ndpi_init_protocol_defaults(struct ndpi_detection_module_struct *ndp
 			  ndpi_build_default_ports(ports_a, 0, 0, 0, 0, 0) /* TCP */,
 			  ndpi_build_default_ports(ports_b, 0, 0, 0, 0, 0) /* UDP */);
 
+  ndpi_set_proto_defaults(ndpi_str, 0 /* encrypted */, 1 /* app proto */, NDPI_PROTOCOL_ACCEPTABLE, NDPI_PROTOCOL_FREE,
+			  "Free", NDPI_PROTOCOL_CATEGORY_WEB,
+			  ndpi_build_default_ports(ports_a, 0, 0, 0, 0, 0) /* TCP */,
+			  ndpi_build_default_ports(ports_b, 0, 0, 0, 0, 0) /* UDP */);
 
 #ifdef CUSTOM_NDPI_PROTOCOLS
 #include "../../../nDPI-custom/custom_ndpi_main.c"
@@ -2783,6 +2784,7 @@ static const char *categories[] = {
   "Allowed_Site",
   "Antimalware",
   "Crypto_Currency",
+  "Gambling"
 };
 
 #if !defined(NDPI_CFFI_PREPROCESSING) && defined(__linux__)
@@ -4144,13 +4146,119 @@ int ndpi_load_categories_file(struct ndpi_detection_module_struct *ndpi_str,
   }
 
   fclose(fd);
-  ndpi_enable_loaded_categories(ndpi_str);
+
+  /*
+    Not necessay to call ndpi_enable_loaded_categories() as
+    ndpi_set_protocol_detection_bitmask2() will do that
+  */
+  /* ndpi_enable_loaded_categories(ndpi_str); */
 
   return(num);
 }
 
 /* ******************************************************************** */
 
+/*
+  Loads a file (separated by <cr>) of domain names associated with the
+  specified category
+*/
+int ndpi_load_category_file(struct ndpi_detection_module_struct *ndpi_str,
+			    char *path, ndpi_protocol_category_t category_id) {
+  char buffer[256], *line;
+  FILE *fd;
+  u_int num_loaded = 0;
+ 
+  if(!ndpi_str || !path || !ndpi_str->protocols_ptree)
+    return(-1);
+
+#ifdef NDPI_ENABLE_DEBUG_MESSAGES
+  printf("Loading %s [proto %d]\n", path, category_id);
+#endif
+  
+  fd = fopen(path, "r");
+
+  if(fd == NULL) {
+    NDPI_LOG_ERR(ndpi_str, "Unable to open file %s [%s]\n", path, strerror(errno));
+    return(-1);
+  }
+
+  while(1) {
+    int len;
+    
+    line = fgets(buffer, sizeof(buffer), fd);
+
+    if(line == NULL)
+      break;
+
+    len = strlen(line);
+
+    if((len <= 1) || (line[0] == '#'))
+      continue;
+
+    if(ndpi_load_category(ndpi_str, line, category_id, NULL) > 0)
+      num_loaded++;    
+  }
+
+  fclose(fd);
+  return(num_loaded);
+}
+ 
+/* ******************************************************************** */
+
+/*
+  Load files (whose name is <categoryid>_<label>.<extension>) stored
+  in a directory and bind each domain to the specified category.
+
+  It can be used to load all files store in the lists/ directory
+
+  It returns the number of loaded files or -1 in case of failure
+*/
+int ndpi_load_categories_dir(struct ndpi_detection_module_struct *ndpi_str,
+			     char *dir_path) {
+  DIR *dirp = opendir(dir_path);
+  struct dirent *dp;
+  int rc = 0;
+  
+  if (dirp == NULL)
+    return(-1);
+  
+  while((dp = readdir(dirp)) != NULL) {
+    char *underscore, *extn;
+    
+    if(dp->d_name[0] == '.') continue;
+    extn = strrchr(dp->d_name, '.');
+
+    if((extn == NULL) || strcmp(extn, ".list"))
+      continue;
+    
+    /* Check if the format is <proto it>_<string>.<extension> */
+    if((underscore = strchr(dp->d_name, '_')) != NULL) {
+      ndpi_protocol_category_t proto_id;
+      
+      underscore[0] = '\0';
+      proto_id = (ndpi_protocol_category_t)atoi(dp->d_name);
+
+      if((proto_id > 0) && (proto_id < NDPI_LAST_IMPLEMENTED_PROTOCOL)) {
+	/* Valid file */
+	char path[256];
+
+	underscore[0] = '_';
+	snprintf(path, sizeof(path), "%s/%s", dir_path, dp->d_name);
+
+	ndpi_load_category_file(ndpi_str, path, proto_id);
+	rc++;
+      }	
+    }
+  }
+  
+  (void)closedir(dirp);
+
+  return(rc);
+}
+
+
+/* ******************************************************************** */
+
 static int ndpi_load_risky_domain(struct ndpi_detection_module_struct *ndpi_str,
 				  char* domain_name) {
   if(ndpi_str->risky_domain_automa.ac_automa == NULL) {