| 1 | // SPDX-License-Identifier: GPL-3.0-or-later |
| 2 | |
| 3 | #include "ml_kmeans.h" |
| 4 | #include "libnetdata/libnetdata.h" |
| 5 | #include <dlib/clustering.h> |
| 6 | |
| 7 | // gcc with libstdc++ may require this, |
| 8 | // but with libc++ it does not work correctly. |
| 9 | #if !defined(_LIBCPP_VERSION) |
| 10 | #include <cmath> |
| 11 | using std::isinf; |
| 12 | using std::isnan; |
| 13 | #endif |
| 14 | |
| 15 | namespace { |
| 16 | |
| 17 | // Guard against out-of-range timestamps when time_t is narrower than int64_t |
| 18 | // (e.g. 32-bit builds). if constexpr ensures the upper-bound check is elided |
| 19 | // at compile time on 64-bit platforms, avoiding constant-expression warnings. |
| 20 | static inline bool ml_int64_fits_nonnegative_time_t(int64_t value) |
| 21 | { |
| 22 | if (value < 0) |
| 23 | return false; |
| 24 | if constexpr (sizeof(time_t) < sizeof(int64_t)) { |
| 25 | // coverity[CONSTANT_EXPRESSION_RESULT] - on 64-bit, Coverity still analyzes |
| 26 | // this dead branch; the check is genuinely reachable only on 32-bit builds |
| 27 | // where time_t is narrower than int64_t. |
| 28 | if (value > (int64_t) std::numeric_limits<time_t>::max()) |
| 29 | return false; |
| 30 | } |
| 31 | return true; |
| 32 | } |
| 33 | |
| 34 | } |
| 35 | |
| 36 | void |
| 37 | ml_kmeans_init(ml_kmeans_t *kmeans) |
| 38 | { |
| 39 | kmeans->cluster_centers.reserve(2); |
| 40 | kmeans->cluster_centers.clear(); |
| 41 | kmeans->min_dist = std::numeric_limits<calculated_number_t>::max(); |
| 42 | kmeans->max_dist = std::numeric_limits<calculated_number_t>::min(); |
| 43 | } |
| 44 | |
| 45 | void |
| 46 | ml_kmeans_train(ml_kmeans_t *kmeans, const std::vector<DSample> &preprocessed_features, unsigned max_iters, time_t after, time_t before) |
| 47 | { |
| 48 | kmeans->after = after; |
| 49 | kmeans->before = before; |
| 50 | |
| 51 | kmeans->min_dist = std::numeric_limits<calculated_number_t>::max(); |
| 52 | kmeans->max_dist = std::numeric_limits<calculated_number_t>::min(); |
| 53 | |
| 54 | kmeans->cluster_centers.clear(); |
| 55 | |
| 56 | if (preprocessed_features.size() < 2) { |
| 57 | netdata_log_error("ml_kmeans_train: not enough features to train kmeans (size=%zu)", |
| 58 | preprocessed_features.size()); |
| 59 | return; |
| 60 | } |
| 61 | |
| 62 | // Reserve capacity for cluster centers BEFORE calling dlib functions to prevent |
| 63 | // reallocation during lazy evaluation. dlib uses expression templates that hold |
| 64 | // references to vector elements, and reallocation would invalidate those references, |
| 65 | // causing heap-use-after-free when multiple threads train models concurrently. |
| 66 | kmeans->cluster_centers.reserve(2); |
| 67 | |
| 68 | dlib::pick_initial_centers(2, kmeans->cluster_centers, preprocessed_features); |
| 69 | dlib::find_clusters_using_kmeans(preprocessed_features, kmeans->cluster_centers, max_iters); |
| 70 | |
| 71 | for (const auto &preprocessed_feature : preprocessed_features) { |
| 72 | calculated_number_t mean_dist = 0.0; |
| 73 | |
| 74 | for (const auto &cluster_center : kmeans->cluster_centers) { |
| 75 | mean_dist += dlib::length(cluster_center - preprocessed_feature); |
| 76 | } |
| 77 | |
| 78 | mean_dist /= kmeans->cluster_centers.size(); |
| 79 | |
| 80 | if (mean_dist < kmeans->min_dist) |
| 81 | kmeans->min_dist = mean_dist; |
| 82 | |
| 83 | if (mean_dist > kmeans->max_dist) |
| 84 | kmeans->max_dist = mean_dist; |
| 85 | } |
| 86 | } |
| 87 | |
| 88 | calculated_number_t |
| 89 | ml_kmeans_anomaly_score(const ml_kmeans_inlined_t *inlined_km, const DSample &DS) |
| 90 | { |
| 91 | calculated_number_t mean_dist = 0.0; |
| 92 | for (const auto &CC: inlined_km->cluster_centers) |
| 93 | mean_dist += dlib::length(CC - DS); |
| 94 | |
| 95 | mean_dist /= inlined_km->cluster_centers.size(); |
| 96 | |
| 97 | if (inlined_km->max_dist == inlined_km->min_dist) |
| 98 | return 0.0; |
| 99 | |
| 100 | calculated_number_t anomaly_score = 100.0 * std::abs((mean_dist - inlined_km->min_dist) / (inlined_km->max_dist - inlined_km->min_dist)); |
| 101 | return (anomaly_score > 100.0) ? 100.0 : anomaly_score; |
| 102 | } |
| 103 | |
| 104 | static void ml_buffer_json_member_add_double(BUFFER *wb, const char *key, calculated_number_t cn) { |
| 105 | if (!isnan(cn) && !isinf(cn)) { |
| 106 | buffer_json_member_add_double(wb, key, cn); |
| 107 | return; |
| 108 | } |
| 109 | |
| 110 | const char *classification = nullptr; |
| 111 | if (isnan(cn)) { |
| 112 | classification = "nan"; |
| 113 | } else if (isinf(cn)) { |
| 114 | if (cn > 0) { |
| 115 | classification = "+inf"; |
| 116 | } else { |
| 117 | classification = "-inf"; |
| 118 | } |
| 119 | } |
| 120 | |
| 121 | buffer_json_member_add_string(wb, key, classification); |
| 122 | } |
| 123 | |
| 124 | static void ml_buffer_json_add_array_item_double(BUFFER *wb, calculated_number_t cn) { |
| 125 | if (!isnan(cn) && !isinf(cn)) { |
| 126 | buffer_json_add_array_item_double(wb, cn); |
| 127 | return; |
| 128 | } |
| 129 | |
| 130 | const char *classification = nullptr; |
| 131 | if (isnan(cn)) { |
| 132 | classification = "nan"; |
| 133 | } else if (isinf(cn)) { |
| 134 | if (cn > 0) { |
| 135 | classification = "+inf"; |
| 136 | } else if (cn < 0) { |
| 137 | classification = "-inf"; |
| 138 | } |
| 139 | } |
| 140 | |
| 141 | buffer_json_add_array_item_string(wb, classification); |
| 142 | } |
| 143 | |
| 144 | bool ml_json_parse_double(struct json_object *jo, calculated_number_t *cn) { |
| 145 | switch(json_object_get_type(jo)) { |
| 146 | case json_type_string: { |
| 147 | const char *s = json_object_get_string(jo); |
| 148 | if (strcmp(s, "nan") == 0) { |
| 149 | *cn = NAN; |
| 150 | return true; |
| 151 | } |
| 152 | else if (strcmp(s, "+inf") == 0) { |
| 153 | *cn = INFINITY; |
| 154 | return true; |
| 155 | } |
| 156 | else if (strcmp(s, "-inf") == 0) { |
| 157 | *cn = -INFINITY; |
| 158 | return true; |
| 159 | } |
| 160 | |
| 161 | return false; |
| 162 | } |
| 163 | case json_type_double: { |
| 164 | *cn = json_object_get_double(jo); |
| 165 | return true; |
| 166 | } |
| 167 | case json_type_int: { |
| 168 | *cn = json_object_get_int64(jo); |
| 169 | return true; |
| 170 | } |
| 171 | default: |
| 172 | return false; |
| 173 | } |
| 174 | } |
| 175 | |
| 176 | void |
| 177 | ml_kmeans_serialize(const ml_kmeans_inlined_t *inlined_km, BUFFER *wb) |
| 178 | { |
| 179 | buffer_json_member_add_uint64(wb, "after", inlined_km->after); |
| 180 | buffer_json_member_add_uint64(wb, "before", inlined_km->before); |
| 181 | |
| 182 | ml_buffer_json_member_add_double(wb, "min_dist", inlined_km->min_dist); |
| 183 | ml_buffer_json_member_add_double(wb, "max_dist", inlined_km->max_dist); |
| 184 | |
| 185 | buffer_json_member_add_array(wb, "cluster_centers"); |
| 186 | for (const auto &cc: inlined_km->cluster_centers) { |
| 187 | buffer_json_add_array_item_array(wb); |
| 188 | |
| 189 | for (const auto &d: cc) { |
| 190 | ml_buffer_json_add_array_item_double(wb, d); |
| 191 | } |
| 192 | |
| 193 | buffer_json_array_close(wb); |
| 194 | } |
| 195 | buffer_json_array_close(wb); |
| 196 | } |
| 197 | |
| 198 | bool ml_kmeans_deserialize(ml_kmeans_inlined_t *inlined_km, struct json_object *root) |
| 199 | { |
| 200 | struct json_object *value; |
| 201 | |
| 202 | if (!json_object_object_get_ex(root, "after", &value)) { |
| 203 | netdata_log_error("Failed to deserialize kmeans: missing key 'after'"); |
| 204 | return false; |
| 205 | } |
| 206 | if (!json_object_is_type(value, json_type_int)) { |
| 207 | netdata_log_error("Failed to deserialize kmeans: failed to parse int for 'after'"); |
| 208 | return false; |
| 209 | } |
| 210 | int64_t raw_after = json_object_get_int64(value); |
| 211 | // Timestamps must be non-negative Unix epoch seconds and fit in time_t. |
| 212 | if (!ml_int64_fits_nonnegative_time_t(raw_after)) { |
| 213 | netdata_log_error("Failed to deserialize kmeans: out-of-range value for 'after': %" PRId64, raw_after); |
| 214 | return false; |
| 215 | } |
| 216 | inlined_km->after = (time_t) raw_after; |
| 217 | |
| 218 | if (!json_object_object_get_ex(root, "before", &value)) { |
| 219 | netdata_log_error("Failed to deserialize kmeans: missing key 'before'"); |
| 220 | return false; |
| 221 | } |
| 222 | if (!json_object_is_type(value, json_type_int)) { |
| 223 | netdata_log_error("Failed to deserialize kmeans: failed to parse int for 'before'"); |
| 224 | return false; |
| 225 | } |
| 226 | int64_t raw_before = json_object_get_int64(value); |
| 227 | // Same contract as 'after': non-negative and fits in time_t. |
| 228 | if (!ml_int64_fits_nonnegative_time_t(raw_before)) { |
| 229 | netdata_log_error("Failed to deserialize kmeans: out-of-range value for 'before': %" PRId64, raw_before); |
| 230 | return false; |
| 231 | } |
| 232 | inlined_km->before = (time_t) raw_before; |
| 233 | |
| 234 | if (!json_object_object_get_ex(root, "min_dist", &value)) { |
| 235 | netdata_log_error("Failed to deserialize kmeans: missing key 'min_dist'"); |
| 236 | return false; |
| 237 | } |
| 238 | if (!ml_json_parse_double(value, &inlined_km->min_dist)) { |
| 239 | netdata_log_error("Failed to deserialize kmeans: failed to parse double for 'min_dist'"); |
| 240 | return false; |
| 241 | } |
| 242 | |
| 243 | if (!json_object_object_get_ex(root, "max_dist", &value)) { |
| 244 | netdata_log_error("Failed to deserialize kmeans: missing key 'max_dist'"); |
| 245 | return false; |
| 246 | } |
| 247 | if (!ml_json_parse_double(value, &inlined_km->max_dist)) { |
| 248 | netdata_log_error("Failed to deserialize kmeans: failed to parse double for 'max_dist'"); |
| 249 | return false; |
| 250 | } |
| 251 | |
| 252 | struct json_object *cc_root; |
| 253 | if (!json_object_object_get_ex(root, "cluster_centers", &cc_root)) { |
| 254 | netdata_log_error("Failed to deserialize kmeans: missing key 'cluster_centers'"); |
| 255 | return false; |
| 256 | } |
| 257 | if (!json_object_is_type(cc_root, json_type_array)) { |
| 258 | netdata_log_error("Failed to deserialize kmeans: failed to parse array for 'cluster_centers'"); |
| 259 | return false; |
| 260 | } |
| 261 | |
| 262 | size_t num_centers = json_object_array_length(cc_root); |
| 263 | if (num_centers != 2) { |
| 264 | netdata_log_error("Failed to deserialize kmeans: expected cluster centers array of size 2"); |
| 265 | return false; |
| 266 | } |
| 267 | |
| 268 | for (size_t i = 0; i < num_centers; i++) { |
| 269 | struct json_object *cc_obj = json_object_array_get_idx(cc_root, i); |
| 270 | if (!cc_obj || !json_object_is_type(cc_obj, json_type_array)) { |
| 271 | netdata_log_error("Failed to deserialize kmeans: expected cluster center array"); |
| 272 | return false; |
| 273 | } |
| 274 | |
| 275 | size_t size = json_object_array_length(cc_obj); |
| 276 | if (size != 6) { |
| 277 | netdata_log_error("Failed to deserialize kmeans: expected cluster center array of size 6"); |
| 278 | return false; |
| 279 | } |
| 280 | |
| 281 | inlined_km->cluster_centers[i].set_size(size); |
| 282 | for (size_t j = 0; j < size; j++) { |
| 283 | struct json_object *value = json_object_array_get_idx(cc_obj, j); |
| 284 | calculated_number_t cn; |
| 285 | |
| 286 | if (!ml_json_parse_double(value, &cn)) { |
| 287 | netdata_log_error("Failed to deserialize kmeans: failed to parse double %zu for cluster center %zu", j, i); |
| 288 | return false; |
| 289 | } |
| 290 | |
| 291 | inlined_km->cluster_centers[i](j) = cn; |
| 292 | } |
| 293 | } |
| 294 | |
| 295 | return true; |
| 296 | } |