fuzz: add 2 new fuzzers for KD-trees and Ball-trees (#2670)

5 files changed, 193 insertions, 1 deletions

diff --git a/.gitignore b/.gitignore
index baa2a26dc..be30cdd0e 100644
--- a/.gitignore
+++ b/.gitignore
@@ -80,6 +80,8 @@
 /fuzz/fuzz_ds_ahocorasick
 /fuzz/fuzz_ds_bitmap64_fuse
 /fuzz/fuzz_ds_domain_classify
+/fuzz/fuzz_ds_kdtree
+/fuzz/fuzz_ds_btree
 /fuzz/fuzz_libinjection
 /fuzz/fuzz_binaryfusefilter
 /fuzz/fuzz_tls_certificate
diff --git a/fuzz/Makefile.am b/fuzz/Makefile.am
index c22102892..86b3f9234 100644
--- a/fuzz/Makefile.am
+++ b/fuzz/Makefile.am
@@ -2,7 +2,7 @@ bin_PROGRAMS = fuzz_process_packet fuzz_ndpi_reader fuzz_ndpi_reader_alloc_fail
 #Alghoritms
 bin_PROGRAMS += fuzz_alg_bins fuzz_alg_hll fuzz_alg_hw_rsi_outliers_da fuzz_alg_jitter fuzz_alg_ses_des fuzz_alg_crc32_md5 fuzz_alg_bytestream fuzz_alg_shoco fuzz_alg_memmem fuzz_alg_strnstr fuzz_alg_quick_encryption
 #Data structures
-bin_PROGRAMS += fuzz_ds_patricia fuzz_ds_ahocorasick fuzz_ds_libcache fuzz_ds_tree fuzz_ds_ptree fuzz_ds_hash fuzz_ds_cmsketch fuzz_ds_bitmap64_fuse fuzz_ds_domain_classify
+bin_PROGRAMS += fuzz_ds_patricia fuzz_ds_ahocorasick fuzz_ds_libcache fuzz_ds_tree fuzz_ds_ptree fuzz_ds_hash fuzz_ds_cmsketch fuzz_ds_bitmap64_fuse fuzz_ds_domain_classify fuzz_ds_kdtree fuzz_ds_btree
 #Third party
 bin_PROGRAMS += fuzz_libinjection fuzz_binaryfusefilter
 #Internal crypto
@@ -414,6 +414,36 @@ fuzz_ds_domain_classify_LINK=$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) \
     $(LIBTOOLFLAGS) --mode=link $(CXX) @NDPI_CFLAGS@ $(AM_CXXFLAGS) $(CXXFLAGS) \
     $(fuzz_ds_domain_classify_LDFLAGS) @NDPI_LDFLAGS@ $(LDFLAGS) -o $@
 
+fuzz_ds_kdtree_SOURCES = fuzz_ds_kdtree.cpp fuzz_common_code.c
+fuzz_ds_kdtree_CXXFLAGS = @NDPI_CFLAGS@ $(CXXFLAGS) -DNDPI_LIB_COMPILATION
+fuzz_ds_kdtree_CFLAGS = @NDPI_CFLAGS@ $(CXXFLAGS) -DNDPI_LIB_COMPILATION
+fuzz_ds_kdtree_LDADD = ../src/lib/libndpi.a $(ADDITIONAL_LIBS)
+fuzz_ds_kdtree_LDFLAGS = $(LIBS)
+if HAS_FUZZLDFLAGS
+fuzz_ds_kdtree_CXXFLAGS += $(LIB_FUZZING_ENGINE)
+fuzz_ds_kdtree_CFLAGS += $(LIB_FUZZING_ENGINE)
+fuzz_ds_kdtree_LDFLAGS += $(LIB_FUZZING_ENGINE)
+endif
+# force usage of CXX for linker
+fuzz_ds_kdtree_LINK=$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) \
+    $(LIBTOOLFLAGS) --mode=link $(CXX) @NDPI_CFLAGS@ $(AM_CXXFLAGS) $(CXXFLAGS) \
+    $(fuzz_ds_kdtree_LDFLAGS) @NDPI_LDFLAGS@ $(LDFLAGS) -o $@
+
+fuzz_ds_btree_SOURCES = fuzz_ds_btree.cpp fuzz_common_code.c
+fuzz_ds_btree_CXXFLAGS = @NDPI_CFLAGS@ $(CXXFLAGS) -DNDPI_LIB_COMPILATION
+fuzz_ds_btree_CFLAGS = @NDPI_CFLAGS@ $(CXXFLAGS) -DNDPI_LIB_COMPILATION
+fuzz_ds_btree_LDADD = ../src/lib/libndpi.a $(ADDITIONAL_LIBS)
+fuzz_ds_btree_LDFLAGS = $(LIBS)
+if HAS_FUZZLDFLAGS
+fuzz_ds_btree_CXXFLAGS += $(LIB_FUZZING_ENGINE)
+fuzz_ds_btree_CFLAGS += $(LIB_FUZZING_ENGINE)
+fuzz_ds_btree_LDFLAGS += $(LIB_FUZZING_ENGINE)
+endif
+# force usage of CXX for linker
+fuzz_ds_btree_LINK=$(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) \
+    $(LIBTOOLFLAGS) --mode=link $(CXX) @NDPI_CFLAGS@ $(AM_CXXFLAGS) $(CXXFLAGS) \
+    $(fuzz_ds_btree_LDFLAGS) @NDPI_LDFLAGS@ $(LDFLAGS) -o $@
+
 fuzz_libinjection_SOURCES = fuzz_libinjection.c
 fuzz_libinjection_CFLAGS = @NDPI_CFLAGS@ $(CXXFLAGS)
 fuzz_libinjection_LDADD = ../src/lib/libndpi.a $(ADDITIONAL_LIBS)
diff --git a/fuzz/fuzz_ds_btree.cpp b/fuzz/fuzz_ds_btree.cpp
new file mode 100644
index 000000000..4f244ffac
--- /dev/null
+++ b/fuzz/fuzz_ds_btree.cpp
@@ -0,0 +1,65 @@
+#include "ndpi_api.h"
+#include "fuzz_common_code.h"
+
+#include <stdint.h>
+#include <stdio.h>
+#include <assert.h>
+#include "fuzzer/FuzzedDataProvider.h"
+
+extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
+  FuzzedDataProvider fuzzed_data(data, size);
+  u_int16_t i, j, num_iteration, num_rows, num_columns, num_q_rows, num_q_columns, num_results;
+  ndpi_btree *b;
+  double **inputs, **q;
+
+  /* Just to have some data */
+  if (fuzzed_data.remaining_bytes() < 1024)
+    return -1;
+
+#if 0 /* TODO: ball.c code is not ready to handle memory allocation errors :( */
+  /* To allow memory allocation failures */
+  fuzz_set_alloc_callbacks_and_seed(size);
+#endif
+
+  num_rows = fuzzed_data.ConsumeIntegralInRange(1, 16);
+  num_columns = fuzzed_data.ConsumeIntegralInRange(1, 16);
+
+  inputs = (double **)ndpi_malloc(sizeof(double *) * num_rows);
+  for (i = 0; i < num_rows; i++) {
+    inputs[i] = (double *)ndpi_malloc(sizeof(double) * num_columns);
+    for (j = 0; j < num_columns; j++)
+      inputs[i][j] = fuzzed_data.ConsumeFloatingPoint<double>();
+  }
+
+  num_q_rows = fuzzed_data.ConsumeIntegralInRange(1, 16);
+  num_q_columns = fuzzed_data.ConsumeIntegralInRange(1, 16);
+
+  q = (double **)ndpi_malloc(sizeof(double *) * num_q_rows);
+  for (i = 0; i < num_q_rows; i++) {
+    q[i] = (double *)ndpi_malloc(sizeof(double) * num_q_columns);
+    for (j = 0; j < num_q_columns; j++)
+      q[i][j] = fuzzed_data.ConsumeFloatingPoint<double>();
+  }
+
+  num_results = fuzzed_data.ConsumeIntegralInRange((int)num_q_rows, 16);
+
+  b = ndpi_btree_init(inputs, num_rows, num_columns);
+
+  num_iteration = fuzzed_data.ConsumeIntegral<u_int8_t>();
+  for (i = 0; i < num_iteration; i++) {
+    ndpi_knn result;
+
+    result = ndpi_btree_query(b, q, num_q_rows, num_q_columns, num_results);
+    ndpi_free_knn(result);
+  }
+
+  for (i = 0; i < num_rows; i++)
+    ndpi_free(inputs[i]);
+  ndpi_free(inputs);
+  for (i = 0; i < num_q_rows; i++)
+    ndpi_free(q[i]);
+  ndpi_free(q);
+  ndpi_free_btree(b);
+
+  return 0;
+}
diff --git a/fuzz/fuzz_ds_kdtree.cpp b/fuzz/fuzz_ds_kdtree.cpp
new file mode 100644
index 000000000..e8366d02e
--- /dev/null
+++ b/fuzz/fuzz_ds_kdtree.cpp
@@ -0,0 +1,89 @@
+#include "ndpi_api.h"
+#include "fuzz_common_code.h"
+
+#include <stdint.h>
+#include <stdio.h>
+#include <assert.h>
+#include "fuzzer/FuzzedDataProvider.h"
+
+extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
+  FuzzedDataProvider fuzzed_data(data, size);
+  u_int16_t i, j, rc, num_iteration, is_added = 0, num_dimensions;
+  ndpi_kd_tree *k = NULL;
+  double *values, *values_added;
+
+  /* Just to have some data */
+  if (fuzzed_data.remaining_bytes() < 1024)
+    return -1;
+
+  /* To allow memory allocation failures */
+  fuzz_set_alloc_callbacks_and_seed(size);
+
+  num_dimensions = fuzzed_data.ConsumeIntegralInRange(1, 8);
+
+  values = (double *)ndpi_malloc(sizeof(double) * num_dimensions);
+  values_added = (double *)ndpi_malloc(sizeof(double) * num_dimensions);
+  if (!values || !values_added) {
+    ndpi_free(values);
+    ndpi_free(values_added);
+    return 0;
+  }
+
+  k = ndpi_kd_create(num_dimensions);
+
+  num_iteration = fuzzed_data.ConsumeIntegral<u_int8_t>();
+  for (i = 0; i < num_iteration; i++) {
+
+    for (j = 0; j < num_dimensions; j++)
+      values[j] = fuzzed_data.ConsumeFloatingPoint<double>();
+
+    rc = ndpi_kd_insert(k, values, NULL);
+
+    /* Keep one random entry really added */
+    if (rc == 0 && fuzzed_data.ConsumeBool()) {
+      for (j = 0; j < num_dimensions; j++)
+        values_added[j] = values[j];
+      is_added = 1;
+    }
+  }
+
+  /* "Random" search */
+  num_iteration = fuzzed_data.ConsumeIntegral<u_int8_t>();
+  for (i = 0; i < num_iteration; i++) {
+    ndpi_kd_tree_result *res = NULL;
+    double *user_data;
+
+    for (j = 0; j < num_dimensions; j++)
+      values[j] = fuzzed_data.ConsumeFloatingPoint<double>();
+
+    res = ndpi_kd_nearest(k, values);
+    if (res) {
+      ndpi_kd_num_results(res);
+      ndpi_kd_result_get_item(res, &user_data);
+      if(is_added) {
+        ndpi_kd_distance(values, values_added, num_dimensions);
+      }
+      ndpi_kd_result_free(res);
+    }
+
+  }
+  /* Search of an added entry */
+  if (is_added) {
+    ndpi_kd_tree_result *res = NULL;
+    double *user_data;
+
+    res = ndpi_kd_nearest(k, values_added);
+    if (res) {
+      ndpi_kd_num_results(res);
+      ndpi_kd_result_get_item(res, &user_data);
+      ndpi_kd_result_free(res);
+    }
+  }
+
+  ndpi_free(values);
+  ndpi_free(values_added);
+  ndpi_kd_clear(k);
+  ndpi_kd_free(k);
+
+  return 0;
+}
diff --git a/src/lib/third_party/src/kdtree.c b/src/lib/third_party/src/kdtree.c
index a3a2823c8..4628f7f9e 100644
--- a/src/lib/third_party/src/kdtree.c
+++ b/src/lib/third_party/src/kdtree.c
@@ -160,6 +160,9 @@ static void clear_rec(struct kdnode *node, void (*destr)(void*))
 
 void kd_clear(struct kdtree *tree)
 {
+  if (!tree)
+    return;
+
   clear_rec(tree->root, tree->destr);
   tree->root = 0;
 
@@ -206,6 +209,9 @@ static int insert_rec(struct kdnode **nptr, const double *pos, void *data, int d
 
 int kd_insert(struct kdtree *tree, const double *pos, void *data)
 {
+  if (!tree)
+    return -1;
+
   if (insert_rec(&tree->root, pos, data, 0, tree->dim)) {
     return -1;
   }