Fixed false positive in suspicous user agent

Optimized stddev calculation

4 files changed, 25 insertions, 13 deletions

diff --git a/src/include/ndpi_typedefs.h b/src/include/ndpi_typedefs.h
index 359ff6d84..153651cec 100644
--- a/src/include/ndpi_typedefs.h
+++ b/src/include/ndpi_typedefs.h
@@ -1505,11 +1505,10 @@ typedef struct {
 struct ndpi_analyze_struct {
   u_int32_t *values;
   u_int32_t min_val, max_val, sum_total, num_data_entries, next_value_insert_index;
-  u_int16_t num_values_array_len /* lenght of the values array */;
+  u_int16_t num_values_array_len /* length of the values array */;
 
   struct {
-    /* https://www.johndcook.com/blog/standard_deviation/ */
-    float mu, q;
+    u_int64_t sum_square_total;
   } stddev;
 };
 
diff --git a/src/lib/ndpi_analyze.c b/src/lib/ndpi_analyze.c
index 26f2ae041..7b53e20ea 100644
--- a/src/lib/ndpi_analyze.c
+++ b/src/lib/ndpi_analyze.c
@@ -87,8 +87,6 @@ void ndpi_reset_data_analysis(struct ndpi_analyze_struct *d) {
   Add a new point to analyze
  */
 void ndpi_data_add_value(struct ndpi_analyze_struct *s, const u_int32_t value) {
-  float tmp_mu;
-
   if(s->sum_total == 0)
     s->min_val = s->max_val = value;
   else {
@@ -105,10 +103,14 @@ void ndpi_data_add_value(struct ndpi_analyze_struct *s, const u_int32_t value) {
       s->next_value_insert_index = 0;
   }
 
-  /* Update stddev */
-  tmp_mu = s->stddev.mu;
-  s->stddev.mu = ((s->stddev.mu * (s->num_data_entries - 1)) + value) / s->num_data_entries;
-  s->stddev.q = s->stddev.q + (value - tmp_mu)*(value - s->stddev.mu);
+  /*
+    Optimized stddev calculation
+    
+    https://www.khanacademy.org/math/probability/data-distributions-a1/summarizing-spread-distributions/a/calculating-standard-deviation-step-by-step
+    https://math.stackexchange.com/questions/683297/how-to-calculate-standard-deviation-without-detailed-historical-data
+    http://mathcentral.uregina.ca/QQ/database/QQ.09.02/carlos1.html
+  */
+  s->stddev.sum_square_total += value * value;
 }
 
 /* ********************************************************************************* */
@@ -138,7 +140,7 @@ u_int32_t ndpi_data_max(struct ndpi_analyze_struct *s) { return(s->max_val); }
 
 /* Compute the variance on all values */
 float ndpi_data_variance(struct ndpi_analyze_struct *s) {
-  return(s->num_data_entries ? (s->stddev.q / s->num_data_entries) : 0);
+  return(s->num_data_entries ? ((float)s->stddev.sum_square_total - (float)((s->sum_total * s->sum_total) / (float)(s->num_data_entries))) / (float)s->num_data_entries : 0);
 }
 
 /* ********************************************************************************* */
diff --git a/src/lib/ndpi_main.c b/src/lib/ndpi_main.c
index 5ee124ac7..de95726ef 100644
--- a/src/lib/ndpi_main.c
+++ b/src/lib/ndpi_main.c
@@ -55,7 +55,7 @@ extern u_int32_t get_stun_lru_key(struct ndpi_flow_struct *flow, u_int8_t rev);
 
 static int _ndpi_debug_callbacks = 0;
 
-/* #define DGA_DEBUG 1   */
+/* #define DGA_DEBUG 1 */
 /* #define MATCH_DEBUG 1 */
 
 /* ****************************************** */
@@ -6644,7 +6644,12 @@ int ndpi_check_dga_name(struct ndpi_detection_module_struct *ndpi_str,
     char tmp[128], *word, *tok_tmp;
 
     len = snprintf(tmp, sizeof(tmp)-1, "%s", name);
-    if(len < 0) return(0);
+    if(len < 0) {
+#ifdef DGA_DEBUG
+      printf("[DGA] Too short");
+#endif
+      return(0);
+    }
 
     for(i=0, j=0; (i<len) && (j<(sizeof(tmp)-1)); i++) {
 	tmp[j] = tolower(name[i]);
@@ -6709,6 +6714,9 @@ int ndpi_check_dga_name(struct ndpi_detection_module_struct *ndpi_str,
        || (max_domain_element_len >= 19 /* word too long. Example bbcbedxhgjmdobdprmen.com */)
        ) {
       if(flow) NDPI_SET_BIT(flow->risk, NDPI_SUSPICIOUS_DGA_DOMAIN);
+#ifdef DGA_DEBUG
+      printf("[DGA] Found!");
+#endif
       return(1);
     }
 
@@ -6801,5 +6809,9 @@ int ndpi_check_dga_name(struct ndpi_detection_module_struct *ndpi_str,
 #endif
   }
 
+#ifdef DGA_DEBUG
+  printf("[DGA] Result: %u", rc);
+#endif
+
   return(rc);
 }
diff --git a/src/lib/protocols/http.c b/src/lib/protocols/http.c
index 941c9b431..4ae455ee1 100644
--- a/src/lib/protocols/http.c
+++ b/src/lib/protocols/http.c
@@ -269,7 +269,6 @@ static void ndpi_check_user_agent(struct ndpi_detection_module_struct *ndpi_stru
   if((strlen(ua) < 4)
      || (!strncmp(ua, "test", 4))
      || (!strncmp(ua, "<?", 2))
-     || strchr(ua, ';')
      || strchr(ua, '{')
      || strchr(ua, '}')
      || ndpi_check_dga_name(ndpi_struct, NULL, ua)