1 /*
2 * Copyright 2023-2024 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License 2.0 (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 */
9
10 #include <openssl/bio.h>
11 #include "quictestlib.h"
12 #include "../testutil.h"
13
14 #define MSG_DATA_LEN_MAX 1472
15 #define SAMPLING_WINDOW_PERIOD 10 /* in milliseconds */
16 #define MAX_PKTS_PER_WINDOW 1024
17
18 struct pkt_info_st {
19 size_t size;
20 OSSL_TIME timestamp;
21 };
22
23 struct bw_limiter_st {
24 struct pkt_info_st pinfos[MAX_PKTS_PER_WINDOW]; /* ring buffer */
25 size_t start, num; /* ring buffer start and number of items */
26 size_t size_sum; /* sum of packet sizes in window */
27 size_t bw; /* bandwidth in bytes/ms */
28 };
29
30 struct noisy_dgram_st {
31 uint64_t this_dgram;
32 BIO_MSG msg;
33 uint64_t reinject_dgram;
34 int backoff;
35 int noise_rate; /* 1 in noise_rate packets will get noise */
36 struct bw_limiter_st recv_limit, send_limit;
37 OSSL_TIME (*now_cb)(void *arg);
38 void *now_cb_arg;
39 };
40
noisy_dgram_ctrl(BIO * bio,int cmd,long num,void * ptr)41 static long noisy_dgram_ctrl(BIO *bio, int cmd, long num, void *ptr)
42 {
43 long ret;
44 BIO *next = BIO_next(bio);
45
46 if (next == NULL)
47 return 0;
48
49 switch (cmd) {
50 case BIO_CTRL_DUP:
51 ret = 0L;
52 break;
53 case BIO_CTRL_NOISE_BACK_OFF: {
54 struct noisy_dgram_st *data;
55
56 data = BIO_get_data(bio);
57 if (!TEST_ptr(data))
58 return 0;
59 data->backoff = 1;
60 ret = 1;
61 break;
62 }
63 case BIO_CTRL_NOISE_RATE: {
64 struct noisy_dgram_st *data;
65
66 data = BIO_get_data(bio);
67 if (!TEST_ptr(data))
68 return 0;
69 data->noise_rate = (int)num;
70 ret = 1;
71 break;
72 }
73 case BIO_CTRL_NOISE_RECV_BANDWIDTH: {
74 struct noisy_dgram_st *data;
75
76 data = BIO_get_data(bio);
77 if (!TEST_ptr(data))
78 return 0;
79 data->recv_limit.bw = (size_t)num;
80 ret = 1;
81 break;
82 }
83 case BIO_CTRL_NOISE_SEND_BANDWIDTH: {
84 struct noisy_dgram_st *data;
85
86 data = BIO_get_data(bio);
87 if (!TEST_ptr(data))
88 return 0;
89 data->send_limit.bw = (size_t)num;
90 ret = 1;
91 break;
92 }
93 case BIO_CTRL_NOISE_SET_NOW_CB: {
94 struct noisy_dgram_st *data;
95 struct bio_noise_now_cb_st *now_cb = ptr;
96
97 data = BIO_get_data(bio);
98 if (!TEST_ptr(data))
99 return 0;
100 data->now_cb = now_cb->now_cb;
101 data->now_cb_arg = now_cb->now_cb_arg;
102 ret = 1;
103 break;
104 }
105 default:
106 ret = BIO_ctrl(next, cmd, num, ptr);
107 break;
108 }
109 return ret;
110 }
111
bandwidth_limit(struct bw_limiter_st * limit,OSSL_TIME now,BIO_MSG * msg,size_t num_msg)112 static size_t bandwidth_limit(struct bw_limiter_st *limit, OSSL_TIME now,
113 BIO_MSG *msg, size_t num_msg)
114 {
115 size_t i;
116 OSSL_TIME sampling_start
117 = ossl_time_subtract(now, ossl_ms2time(SAMPLING_WINDOW_PERIOD));
118
119 if (limit->bw == 0) /* 0 -> no limit */
120 return num_msg;
121
122 if (num_msg > MAX_PKTS_PER_WINDOW)
123 num_msg = MAX_PKTS_PER_WINDOW;
124
125 /* trim the start of the ring buffer */
126 for (i = 0; i < limit->num; i++) {
127 size_t idx = (limit->start + i) % MAX_PKTS_PER_WINDOW;
128
129 if (ossl_time_compare(limit->pinfos[idx].timestamp, sampling_start) >= 0)
130 break;
131 limit->size_sum -= limit->pinfos[idx].size;
132 }
133 limit->start = (limit->start + i) % MAX_PKTS_PER_WINDOW;
134 limit->num -= i;
135
136 for (i = 0; i < num_msg; ++i) {
137 size_t end;
138 size_t pktsize = msg[i].data_len;
139
140 if ((limit->size_sum + pktsize) / SAMPLING_WINDOW_PERIOD > limit->bw) {
141 /*
142 * Throw out all the packets once reaching the limit,
143 * although some following packets could still fit.
144 * This is accurate enough.
145 */
146 #ifdef OSSL_NOISY_DGRAM_DEBUG
147 printf("**BW limit applied: now: %llu orig packets %u new packets %u\n",
148 (unsigned long long)ossl_time2ms(now),
149 (unsigned int)num_msg, (unsigned int) i);
150 #endif
151 num_msg = i;
152 break;
153 }
154
155 if (limit->num >= MAX_PKTS_PER_WINDOW) {
156 limit->size_sum -= limit->pinfos[limit->start].size;
157 limit->start = (limit->start + 1) % MAX_PKTS_PER_WINDOW;
158 } else {
159 ++limit->num;
160 }
161 end = (limit->start + limit->num) % MAX_PKTS_PER_WINDOW;
162 limit->pinfos[end].size = pktsize;
163 limit->pinfos[end].timestamp = now;
164 limit->size_sum += pktsize;
165 }
166 return num_msg;
167 }
168
noisy_dgram_sendmmsg(BIO * bio,BIO_MSG * msg,size_t stride,size_t num_msg,uint64_t flags,size_t * msgs_processed)169 static int noisy_dgram_sendmmsg(BIO *bio, BIO_MSG *msg, size_t stride,
170 size_t num_msg, uint64_t flags,
171 size_t *msgs_processed)
172 {
173 BIO *next = BIO_next(bio);
174 struct noisy_dgram_st *data;
175 OSSL_TIME now;
176
177 if (next == NULL)
178 return 0;
179
180 data = BIO_get_data(bio);
181 if (!TEST_ptr(data))
182 return 0;
183
184 now = data->now_cb != NULL ? data->now_cb(data->now_cb_arg)
185 : ossl_time_now();
186
187 /* bandwidth limit can be applied on both sides */
188 num_msg = bandwidth_limit(&data->send_limit, now, msg, num_msg);
189 if (num_msg == 0) {
190 *msgs_processed = 0;
191 ERR_raise(ERR_LIB_BIO, BIO_R_NON_FATAL);
192 return 0;
193 }
194
195 /*
196 * We only introduce noise when receiving messages. We just pass this on
197 * to the underlying BIO.
198 */
199 return BIO_sendmmsg(next, msg, stride, num_msg, flags, msgs_processed);
200 }
201
202 /* Default noise_rate value. With a value of 5 that is 20% packets. */
203 #define NOISE_RATE 5
204
205 /*
206 * We have 3 different types of noise: drop, duplicate and delay
207 * Each of these have equal probability.
208 */
209 #define NOISE_TYPE_DROP 0
210 #define NOISE_TYPE_DUPLICATE 1
211 #define NOISE_TYPE_DELAY 2
212 #define NOISE_TYPE_BITFLIPS 3
213 #define NUM_NOISE_TYPES 4
214
215 /*
216 * When a duplicate occurs we reinject the new datagram after up to
217 * MAX_DGRAM_REINJECT datagrams have been sent. A reinject of 1 means that the
218 * duplicate follows immediately after the original datagram. A reinject of 4
219 * means that original datagram plus 3 other datagrams are sent before the
220 * reinjected datagram is inserted.
221 * This also controls when a delay (not a duplicate) occurs. In that case
222 * we add 1 to the number because there is no point in skipping the current
223 * datagram only to immediately reinject it in the next datagram.
224 */
225 #define MAX_DGRAM_REINJECT 4
226
get_noise(int noise_rate,int long_header,uint64_t * reinject,int * should_drop,uint16_t * flip,size_t * flip_offset)227 static void get_noise(int noise_rate, int long_header, uint64_t *reinject,
228 int *should_drop, uint16_t *flip, size_t *flip_offset)
229 {
230 uint32_t type;
231
232 *flip = 0;
233
234 if (test_random() % noise_rate != 0) {
235 *reinject = 0;
236 *should_drop = 0;
237 return;
238 }
239
240 type = test_random() % NUM_NOISE_TYPES;
241
242 /*
243 * Of noisy datagrams, 25% drop, 25% duplicate, 25% delay, 25% flip bits
244 * A duplicated datagram keeps the current datagram and reinjects a new
245 * identical one after up to MAX_DGRAM_DELAY datagrams have been sent.
246 * A delayed datagram is implemented as both a reinject and a drop, i.e. an
247 * identical datagram is reinjected after the given number of datagrams have
248 * been sent and the current datagram is dropped.
249 */
250 *should_drop = (type == NOISE_TYPE_DROP || type == NOISE_TYPE_DELAY);
251
252 /*
253 * Where a duplicate occurs we reinject the copy of the datagram up to
254 * MAX_DGRAM_DELAY datagrams later
255 */
256 *reinject = (type == NOISE_TYPE_DUPLICATE || type == NOISE_TYPE_DELAY)
257 ? (uint64_t)((test_random() % MAX_DGRAM_REINJECT) + 1)
258 : 0;
259
260 /*
261 * No point in reinjecting after 1 datagram if the current datagram is also
262 * dropped (i.e. this is a delay not a duplicate), so we reinject after an
263 * extra datagram in that case
264 */
265 *reinject += type == NOISE_TYPE_DELAY;
266
267 /* flip some bits in the header */
268 if (type == NOISE_TYPE_BITFLIPS) {
269 /* we flip at most 8 bits of the 16 bit value at once */
270 *flip = (test_random() % 255 + 1) << (test_random() % 8);
271 /*
272 * 25/50 bytes of guesstimated header size (it depends on CID length)
273 * It does not matter much if it is overestimated.
274 */
275 *flip_offset = test_random() % (25 * (1 + long_header));
276 }
277 }
278
flip_bits(unsigned char * msg,size_t msg_len,uint16_t flip,size_t flip_offset)279 static void flip_bits(unsigned char *msg, size_t msg_len, uint16_t flip,
280 size_t flip_offset)
281 {
282 if (flip == 0)
283 return;
284
285 /* None of these border conditions should happen but check them anyway */
286 if (msg_len < 2)
287 return;
288 if (msg_len < flip_offset + 2)
289 flip_offset = msg_len - 2;
290
291 #ifdef OSSL_NOISY_DGRAM_DEBUG
292 printf("**Flipping bits in a datagram at offset %u\n",
293 (unsigned int)flip_offset);
294 BIO_dump_fp(stdout, msg, msg_len);
295 printf("\n");
296 #endif
297
298 msg[flip_offset] ^= flip >> 8;
299 msg[flip_offset + 1] ^= flip & 0xff;
300 }
301
noisy_dgram_recvmmsg(BIO * bio,BIO_MSG * msg,size_t stride,size_t num_msg,uint64_t flags,size_t * msgs_processed)302 static int noisy_dgram_recvmmsg(BIO *bio, BIO_MSG *msg, size_t stride,
303 size_t num_msg, uint64_t flags,
304 size_t *msgs_processed)
305 {
306 BIO *next = BIO_next(bio);
307 size_t i, j, data_len = 0, msg_cnt = 0;
308 BIO_MSG *thismsg;
309 struct noisy_dgram_st *data;
310 OSSL_TIME now;
311
312 if (!TEST_ptr(next))
313 return 0;
314
315 data = BIO_get_data(bio);
316 if (!TEST_ptr(data))
317 return 0;
318
319 /*
320 * For simplicity we assume that all elements in the msg array have the
321 * same data_len. They are not required to by the API, but it would be quite
322 * strange for that not to be the case - and our code that calls
323 * BIO_recvmmsg does do this (which is all that is important for this test
324 * code). We test the invariant here.
325 */
326 for (i = 0; i < num_msg; i++) {
327 if (i == 0) {
328 data_len = msg[i].data_len;
329 if (!TEST_size_t_le(data_len, MSG_DATA_LEN_MAX))
330 return 0;
331 } else if (!TEST_size_t_eq(msg[i].data_len, data_len)) {
332 return 0;
333 }
334 }
335
336 if (!BIO_recvmmsg(next, msg, stride, num_msg, flags, msgs_processed))
337 return 0;
338
339 #ifdef OSSL_NOISY_DGRAM_DEBUG
340 printf("Pre-filter datagram list:\n");
341 for (i = 0; i < *msgs_processed; i++) {
342 printf("Pre-filter Datagram:\n");
343 BIO_dump_fp(stdout, msg[i].data, msg[i].data_len);
344 printf("\n");
345 }
346 printf("End of pre-filter datagram list\nApplying noise filters:\n");
347 #endif
348
349 now = data->now_cb != NULL ? data->now_cb(data->now_cb_arg)
350 : ossl_time_now();
351
352 msg_cnt = *msgs_processed;
353 msg_cnt = bandwidth_limit(&data->recv_limit, now, msg, msg_cnt);
354 if (msg_cnt == 0)
355 goto end;
356
357 if (data->noise_rate == 0)
358 goto end;
359
360 /* Introduce noise */
361 for (i = 0, thismsg = msg;
362 i < msg_cnt;
363 i++, thismsg++, data->this_dgram++) {
364 uint64_t reinject;
365 int should_drop;
366 uint16_t flip;
367 size_t flip_offset;
368
369 /* If we have a message to reinject then insert it now */
370 if (data->reinject_dgram > 0
371 && data->reinject_dgram == data->this_dgram) {
372 if (msg_cnt < num_msg) {
373 /* Make space for the injected message */
374 for (j = msg_cnt; j > i; j--) {
375 if (!bio_msg_copy(&msg[j], &msg[j - 1]))
376 return 0;
377 }
378 if (!bio_msg_copy(thismsg, &data->msg))
379 return 0;
380 msg_cnt++;
381 data->reinject_dgram = 0;
382 #ifdef OSSL_NOISY_DGRAM_DEBUG
383 printf("**Injecting a datagram\n");
384 BIO_dump_fp(stdout, thismsg->data, thismsg->data_len);
385 printf("\n");
386 #endif
387 continue;
388 } /* else we have no space for the injection, so just drop it */
389 data->reinject_dgram = 0;
390 }
391
392 get_noise(data->noise_rate,
393 /* long header */ (((uint8_t *)thismsg->data)[0] & 0x80) != 0,
394 &reinject, &should_drop, &flip, &flip_offset);
395 if (data->backoff) {
396 /*
397 * We might be asked to back off on introducing too much noise if
398 * there is a danger that the connection will fail. In that case
399 * we always ensure that the next datagram does not get dropped so
400 * that the connection always survives. After that we can resume
401 * with normal noise
402 */
403 #ifdef OSSL_NOISY_DGRAM_DEBUG
404 printf("**Back off applied\n");
405 #endif
406 should_drop = 0;
407 flip = 0;
408 data->backoff = 0;
409 }
410
411 flip_bits(thismsg->data, thismsg->data_len, flip, flip_offset);
412
413 /*
414 * We ignore reinjection if a message is already waiting to be
415 * reinjected
416 */
417 if (reinject > 0 && data->reinject_dgram == 0) {
418 /*
419 * Both duplicated and delayed datagrams get reintroduced after the
420 * delay period. Datagrams that are delayed only (not duplicated)
421 * will also have the current copy of the datagram dropped (i.e
422 * should_drop below will be true).
423 */
424 if (!bio_msg_copy(&data->msg, thismsg))
425 return 0;
426
427 data->reinject_dgram = data->this_dgram + reinject;
428
429 #ifdef OSSL_NOISY_DGRAM_DEBUG
430 printf("**Scheduling a reinject after %u messages%s\n",
431 (unsigned int)reinject, should_drop ? "" : "(duplicating)");
432 BIO_dump_fp(stdout, thismsg->data, thismsg->data_len);
433 printf("\n");
434 #endif
435 }
436
437 if (should_drop) {
438 #ifdef OSSL_NOISY_DGRAM_DEBUG
439 printf("**Dropping a datagram\n");
440 BIO_dump_fp(stdout, thismsg->data, thismsg->data_len);
441 printf("\n");
442 #endif
443 for (j = i + 1; j < msg_cnt; j++) {
444 if (!bio_msg_copy(&msg[j - 1], &msg[j]))
445 return 0;
446 }
447 msg_cnt--;
448 }
449 }
450
451 #ifdef OSSL_NOISY_DGRAM_DEBUG
452 printf("End of noise filters\nPost-filter datagram list:\n");
453 for (i = 0; i < msg_cnt; i++) {
454 printf("Post-filter Datagram:\n");
455 BIO_dump_fp(stdout, msg[i].data, msg[i].data_len);
456 printf("\n");
457 }
458 printf("End of post-filter datagram list\n");
459 #endif
460
461 end:
462 *msgs_processed = msg_cnt;
463
464 if (msg_cnt == 0) {
465 ERR_raise(ERR_LIB_BIO, BIO_R_NON_FATAL);
466 return 0;
467 }
468
469 return 1;
470 }
471
data_free(struct noisy_dgram_st * data)472 static void data_free(struct noisy_dgram_st *data)
473 {
474 if (data == NULL)
475 return;
476
477 OPENSSL_free(data->msg.data);
478 BIO_ADDR_free(data->msg.peer);
479 BIO_ADDR_free(data->msg.local);
480 OPENSSL_free(data);
481 }
482
noisy_dgram_new(BIO * bio)483 static int noisy_dgram_new(BIO *bio)
484 {
485 struct noisy_dgram_st *data = OPENSSL_zalloc(sizeof(*data));
486
487 if (!TEST_ptr(data))
488 return 0;
489
490 data->noise_rate = NOISE_RATE;
491 data->msg.data = OPENSSL_malloc(MSG_DATA_LEN_MAX);
492 data->msg.peer = BIO_ADDR_new();
493 data->msg.local = BIO_ADDR_new();
494 if (data->msg.data == NULL
495 || data->msg.peer == NULL
496 || data->msg.local == NULL) {
497 data_free(data);
498 return 0;
499 }
500
501 BIO_set_data(bio, data);
502 BIO_set_init(bio, 1);
503
504 return 1;
505 }
506
noisy_dgram_free(BIO * bio)507 static int noisy_dgram_free(BIO *bio)
508 {
509 data_free(BIO_get_data(bio));
510 BIO_set_data(bio, NULL);
511 BIO_set_init(bio, 0);
512
513 return 1;
514 }
515
516 /* Choose a sufficiently large type likely to be unused for this custom BIO */
517 #define BIO_TYPE_NOISY_DGRAM_FILTER (0x80 | BIO_TYPE_FILTER)
518
519 static BIO_METHOD *method_noisy_dgram = NULL;
520
521 /* Note: Not thread safe! */
bio_f_noisy_dgram_filter(void)522 const BIO_METHOD *bio_f_noisy_dgram_filter(void)
523 {
524 if (method_noisy_dgram == NULL) {
525 method_noisy_dgram = BIO_meth_new(BIO_TYPE_NOISY_DGRAM_FILTER,
526 "Noisy datagram filter");
527 if (method_noisy_dgram == NULL
528 || !BIO_meth_set_ctrl(method_noisy_dgram, noisy_dgram_ctrl)
529 || !BIO_meth_set_sendmmsg(method_noisy_dgram, noisy_dgram_sendmmsg)
530 || !BIO_meth_set_recvmmsg(method_noisy_dgram, noisy_dgram_recvmmsg)
531 || !BIO_meth_set_create(method_noisy_dgram, noisy_dgram_new)
532 || !BIO_meth_set_destroy(method_noisy_dgram, noisy_dgram_free))
533 return NULL;
534 }
535 return method_noisy_dgram;
536 }
537
bio_f_noisy_dgram_filter_free(void)538 void bio_f_noisy_dgram_filter_free(void)
539 {
540 BIO_meth_free(method_noisy_dgram);
541 }
542
