src/test/test.c

   1 /* Copyright (c) 2001-2004, Roger Dingledine.
   2  * Copyright (c) 2007-2021, The Tor Project, Inc. */
   3 /* See LICENSE for licensing information */
   4
   5 /**
   6  * \file test.c
   7  * \brief Unit tests for many pieces of the lower level Tor modules.
   8  **/
   9
  10 #include "orconfig.h"
  11 #include "lib/crypt_ops/crypto_dh.h"
  12 #include "lib/crypt_ops/crypto_rand.h"
  13 #include "app/config/or_state_st.h"
  14 #include "test/rng_test_helpers.h"
  15
  16 #include <stdio.h>
  17 #ifdef HAVE_FCNTL_H
  18 #include <fcntl.h>
  19 #endif
  20
  21 #ifdef _WIN32
  22 /* For mkdir() */
  23 #include <direct.h>
  24 #else
  25 #include <dirent.h>
  26 #endif /* defined(_WIN32) */
  27
  28 #include <math.h>
  29
  30 /* These macros pull in declarations for some functions and structures that
  31  * are typically file-private. */
  32 #define ROUTER_PRIVATE
  33 #define CIRCUITSTATS_PRIVATE
  34 #define CIRCUITLIST_PRIVATE
  35 #define MAINLOOP_PRIVATE
  36 #define STATEFILE_PRIVATE
  37
  38 #include "core/or/or.h"
  39 #include "lib/err/backtrace.h"
  40 #include "lib/buf/buffers.h"
  41 #include "core/or/circuitlist.h"
  42 #include "core/or/circuitstats.h"
  43 #include "lib/compress/compress.h"
  44 #include "app/config/config.h"
  45 #include "core/or/connection_edge.h"
  46 #include "core/or/extendinfo.h"
  47 #include "test/test.h"
  48 #include "core/mainloop/mainloop.h"
  49 #include "lib/memarea/memarea.h"
  50 #include "core/or/onion.h"
  51 #include "core/crypto/onion_ntor.h"
  52 #include "core/crypto/onion_fast.h"
  53 #include "core/crypto/onion_tap.h"
  54 #include "core/or/policies.h"
  55 #include "lib/sandbox/sandbox.h"
  56 #include "app/config/statefile.h"
  57 #include "lib/crypt_ops/crypto_curve25519.h"
  58 #include "feature/nodelist/networkstatus.h"
  59
  60 #include "core/or/extend_info_st.h"
  61 #include "core/or/or_circuit_st.h"
  62 #include "feature/relay/onion_queue.h"
  63
  64 /** Run unit tests for the onion handshake code. */
  65 static void
  66 test_onion_handshake(void *arg)
  67 {
  68   /* client-side */
  69   crypto_dh_t *c_dh = NULL;
  70   char c_buf[TAP_ONIONSKIN_CHALLENGE_LEN];
  71   char c_keys[40];
  72   /* server-side */
  73   char s_buf[TAP_ONIONSKIN_REPLY_LEN];
  74   char s_keys[40];
  75   int i;
  76   /* shared */
  77   crypto_pk_t *pk = NULL, *pk2 = NULL;
  78
  79   (void)arg;
  80   pk = pk_generate(0);
  81   pk2 = pk_generate(1);
  82
  83   /* client handshake 1. */
  84   memset(c_buf, 0, TAP_ONIONSKIN_CHALLENGE_LEN);
  85   tt_assert(! onion_skin_TAP_create(pk, &c_dh, c_buf));
  86
  87   for (i = 1; i <= 3; ++i) {
  88     crypto_pk_t *k1, *k2;
  89     if (i==1) {
  90       /* server handshake: only one key known. */
  91       k1 = pk;  k2 = NULL;
  92     } else if (i==2) {
  93       /* server handshake: try the right key first. */
  94       k1 = pk;  k2 = pk2;
  95     } else {
  96       /* server handshake: try the right key second. */
  97       k1 = pk2; k2 = pk;
  98     }
  99
 100     memset(s_buf, 0, TAP_ONIONSKIN_REPLY_LEN);
 101     memset(s_keys, 0, 40);
 102     tt_assert(! onion_skin_TAP_server_handshake(c_buf, k1, k2,
 103                                                   s_buf, s_keys, 40));
 104
 105     /* client handshake 2 */
 106     memset(c_keys, 0, 40);
 107     tt_assert(! onion_skin_TAP_client_handshake(c_dh, s_buf, c_keys,
 108                                                 40, NULL));
 109
 110     tt_mem_op(c_keys,OP_EQ, s_keys, 40);
 111     memset(s_buf, 0, 40);
 112     tt_mem_op(c_keys,OP_NE, s_buf, 40);
 113   }
 114  done:
 115   crypto_dh_free(c_dh);
 116   crypto_pk_free(pk);
 117   crypto_pk_free(pk2);
 118 }
 119
 120 static void
 121 test_bad_onion_handshake(void *arg)
 122 {
 123   char junk_buf[TAP_ONIONSKIN_CHALLENGE_LEN];
 124   char junk_buf2[TAP_ONIONSKIN_CHALLENGE_LEN];
 125   /* client-side */
 126   crypto_dh_t *c_dh = NULL;
 127   char c_buf[TAP_ONIONSKIN_CHALLENGE_LEN];
 128   char c_keys[40];
 129   /* server-side */
 130   char s_buf[TAP_ONIONSKIN_REPLY_LEN];
 131   char s_keys[40];
 132   /* shared */
 133   crypto_pk_t *pk = NULL, *pk2 = NULL;
 134
 135   (void)arg;
 136
 137   pk = pk_generate(0);
 138   pk2 = pk_generate(1);
 139
 140   /* Server: Case 1: the encrypted data is degenerate. */
 141   memset(junk_buf, 0, sizeof(junk_buf));
 142   crypto_pk_obsolete_public_hybrid_encrypt(pk,
 143                                junk_buf2, TAP_ONIONSKIN_CHALLENGE_LEN,
 144                                junk_buf, DH1024_KEY_LEN,
 145                                PK_PKCS1_OAEP_PADDING, 1);
 146   tt_int_op(-1, OP_EQ,
 147             onion_skin_TAP_server_handshake(junk_buf2, pk, NULL,
 148                                             s_buf, s_keys, 40));
 149
 150   /* Server: Case 2: the encrypted data is not long enough. */
 151   memset(junk_buf, 0, sizeof(junk_buf));
 152   memset(junk_buf2, 0, sizeof(junk_buf2));
 153   crypto_pk_public_encrypt(pk, junk_buf2, sizeof(junk_buf2),
 154                                junk_buf, 48, PK_PKCS1_OAEP_PADDING);
 155   tt_int_op(-1, OP_EQ,
 156             onion_skin_TAP_server_handshake(junk_buf2, pk, NULL,
 157                                             s_buf, s_keys, 40));
 158
 159   /* client handshake 1: do it straight. */
 160   memset(c_buf, 0, TAP_ONIONSKIN_CHALLENGE_LEN);
 161   tt_assert(! onion_skin_TAP_create(pk, &c_dh, c_buf));
 162
 163   /* Server: Case 3: we just don't have the right key. */
 164   tt_int_op(-1, OP_EQ,
 165             onion_skin_TAP_server_handshake(c_buf, pk2, NULL,
 166                                             s_buf, s_keys, 40));
 167
 168   /* Server: Case 4: The RSA-encrypted portion is corrupt. */
 169   c_buf[64] ^= 33;
 170   tt_int_op(-1, OP_EQ,
 171             onion_skin_TAP_server_handshake(c_buf, pk, NULL,
 172                                             s_buf, s_keys, 40));
 173   c_buf[64] ^= 33;
 174
 175   /* (Let the server proceed) */
 176   tt_int_op(0, OP_EQ,
 177             onion_skin_TAP_server_handshake(c_buf, pk, NULL,
 178                                             s_buf, s_keys, 40));
 179
 180   /* Client: Case 1: The server sent back junk. */
 181   const char *msg = NULL;
 182   s_buf[64] ^= 33;
 183   tt_int_op(-1, OP_EQ,
 184             onion_skin_TAP_client_handshake(c_dh, s_buf, c_keys, 40, &msg));
 185   s_buf[64] ^= 33;
 186   tt_str_op(msg, OP_EQ, "Digest DOES NOT MATCH on onion handshake. "
 187             "Bug or attack.");
 188
 189   /* Let the client finish; make sure it can. */
 190   msg = NULL;
 191   tt_int_op(0, OP_EQ,
 192             onion_skin_TAP_client_handshake(c_dh, s_buf, c_keys, 40, &msg));
 193   tt_mem_op(s_keys,OP_EQ, c_keys, 40);
 194   tt_ptr_op(msg, OP_EQ, NULL);
 195
 196   /* Client: Case 2: The server sent back a degenerate DH. */
 197   memset(s_buf, 0, sizeof(s_buf));
 198   tt_int_op(-1, OP_EQ,
 199             onion_skin_TAP_client_handshake(c_dh, s_buf, c_keys, 40, &msg));
 200   tt_str_op(msg, OP_EQ, "DH computation failed.");
 201
 202  done:
 203   crypto_dh_free(c_dh);
 204   crypto_pk_free(pk);
 205   crypto_pk_free(pk2);
 206 }
 207
 208 static void
 209 test_ntor_handshake(void *arg)
 210 {
 211   /* client-side */
 212   ntor_handshake_state_t *c_state = NULL;
 213   uint8_t c_buf[NTOR_ONIONSKIN_LEN];
 214   uint8_t c_keys[400];
 215
 216   /* server-side */
 217   di_digest256_map_t *s_keymap=NULL;
 218   curve25519_keypair_t s_keypair;
 219   uint8_t s_buf[NTOR_REPLY_LEN];
 220   uint8_t s_keys[400];
 221
 222   /* shared */
 223   const curve25519_public_key_t *server_pubkey;
 224   uint8_t node_id[20] = "abcdefghijklmnopqrst";
 225
 226   (void) arg;
 227
 228   /* Make the server some keys */
 229   curve25519_secret_key_generate(&s_keypair.seckey, 0);
 230   curve25519_public_key_generate(&s_keypair.pubkey, &s_keypair.seckey);
 231   dimap_add_entry(&s_keymap, s_keypair.pubkey.public_key, &s_keypair);
 232   server_pubkey = &s_keypair.pubkey;
 233
 234   /* client handshake 1. */
 235   memset(c_buf, 0, NTOR_ONIONSKIN_LEN);
 236   tt_int_op(0, OP_EQ, onion_skin_ntor_create(node_id, server_pubkey,
 237                                           &c_state, c_buf));
 238
 239   /* server handshake */
 240   memset(s_buf, 0, NTOR_REPLY_LEN);
 241   memset(s_keys, 0, 40);
 242   tt_int_op(0, OP_EQ, onion_skin_ntor_server_handshake(c_buf, s_keymap, NULL,
 243                                                     node_id,
 244                                                     s_buf, s_keys, 400));
 245
 246   /* client handshake 2 */
 247   memset(c_keys, 0, 40);
 248   tt_int_op(0, OP_EQ, onion_skin_ntor_client_handshake(c_state, s_buf,
 249                                                        c_keys, 400, NULL));
 250
 251   tt_mem_op(c_keys,OP_EQ, s_keys, 400);
 252   memset(s_buf, 0, 40);
 253   tt_mem_op(c_keys,OP_NE, s_buf, 40);
 254
 255   /* Now try with a bogus server response. Zero input should trigger
 256    * All The Problems. */
 257   memset(c_keys, 0, 400);
 258   memset(s_buf, 0, NTOR_REPLY_LEN);
 259   const char *msg = NULL;
 260   tt_int_op(-1, OP_EQ, onion_skin_ntor_client_handshake(c_state, s_buf,
 261                                                         c_keys, 400, &msg));
 262   tt_str_op(msg, OP_EQ, "Zero output from curve25519 handshake");
 263
 264  done:
 265   ntor_handshake_state_free(c_state);
 266   dimap_free(s_keymap, NULL);
 267 }
 268
 269 static void
 270 test_fast_handshake(void *arg)
 271 {
 272   /* tests for the obsolete "CREATE_FAST" handshake. */
 273   (void) arg;
 274   fast_handshake_state_t *state = NULL;
 275   uint8_t client_handshake[CREATE_FAST_LEN];
 276   uint8_t server_handshake[CREATED_FAST_LEN];
 277   uint8_t s_keys[100], c_keys[100];
 278
 279   /* First, test an entire handshake. */
 280   memset(client_handshake, 0, sizeof(client_handshake));
 281   tt_int_op(0, OP_EQ, fast_onionskin_create(&state, client_handshake));
 282   tt_assert(! fast_mem_is_zero((char*)client_handshake,
 283                               sizeof(client_handshake)));
 284
 285   tt_int_op(0, OP_EQ,
 286             fast_server_handshake(client_handshake, server_handshake,
 287                                   s_keys, 100));
 288   const char *msg = NULL;
 289   tt_int_op(0, OP_EQ,
 290             fast_client_handshake(state, server_handshake, c_keys, 100, &msg));
 291   tt_ptr_op(msg, OP_EQ, NULL);
 292   tt_mem_op(s_keys, OP_EQ, c_keys, 100);
 293
 294   /* Now test a failing handshake. */
 295   server_handshake[0] ^= 3;
 296   tt_int_op(-1, OP_EQ,
 297             fast_client_handshake(state, server_handshake, c_keys, 100, &msg));
 298   tt_str_op(msg, OP_EQ, "Digest DOES NOT MATCH on fast handshake. "
 299             "Bug or attack.");
 300
 301  done:
 302   fast_handshake_state_free(state);
 303 }
 304
 305 /** Run unit tests for the onion queues. */
 306 static void
 307 test_onion_queues(void *arg)
 308 {
 309   uint8_t buf1[TAP_ONIONSKIN_CHALLENGE_LEN] = {0};
 310   uint8_t buf2[NTOR_ONIONSKIN_LEN] = {0};
 311
 312   or_circuit_t *circ1 = or_circuit_new(0, NULL);
 313   or_circuit_t *circ2 = or_circuit_new(0, NULL);
 314
 315   create_cell_t *onionskin = NULL, *create2_ptr;
 316   create_cell_t *create1 = tor_malloc_zero(sizeof(create_cell_t));
 317   create_cell_t *create2 = tor_malloc_zero(sizeof(create_cell_t));
 318   (void)arg;
 319   create2_ptr = create2; /* remember, but do not free */
 320
 321   create_cell_init(create1, CELL_CREATE, ONION_HANDSHAKE_TYPE_TAP,
 322                    TAP_ONIONSKIN_CHALLENGE_LEN, buf1);
 323   create_cell_init(create2, CELL_CREATE, ONION_HANDSHAKE_TYPE_NTOR,
 324                    NTOR_ONIONSKIN_LEN, buf2);
 325
 326   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP));
 327   tt_int_op(0,OP_EQ, onion_pending_add(circ1, create1));
 328   create1 = NULL;
 329   tt_int_op(1,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP));
 330
 331   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR));
 332   tt_int_op(0,OP_EQ, onion_pending_add(circ2, create2));
 333   create2 = NULL;
 334   tt_int_op(1,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR));
 335
 336   tt_ptr_op(circ2,OP_EQ, onion_next_task(&onionskin));
 337   tt_int_op(1,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP));
 338   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR));
 339   tt_ptr_op(onionskin, OP_EQ, create2_ptr);
 340
 341   clear_pending_onions();
 342   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP));
 343   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR));
 344
 345  done:
 346   circuit_free_(TO_CIRCUIT(circ1));
 347   circuit_free_(TO_CIRCUIT(circ2));
 348   tor_free(create1);
 349   tor_free(create2);
 350   tor_free(onionskin);
 351 }
 352
 353 /**
 354  * Test onion queue priority, separation, and resulting
 355  * ordering.
 356  *
 357  * create and add a mix of TAP, NTOR2, and NTORv3. Ensure
 358  * they all end up in the right queue. In particular, ntorv2
 359  * and ntorv3 should share a queue, but TAP should be separate,
 360  * and lower prioritt.
 361  *
 362  * We test this by way of adding TAP first, and then an interleaving
 363  * order of ntor2 and ntor3, and check that the ntor2 and ntor3 are
 364  * still interleaved, but TAP comes last. */
 365 static void
 366 test_onion_queue_order(void *arg)
 367 {
 368   uint8_t buf_tap[TAP_ONIONSKIN_CHALLENGE_LEN] = {0};
 369   uint8_t buf_ntor[NTOR_ONIONSKIN_LEN] = {0};
 370   uint8_t buf_ntor3[CELL_PAYLOAD_SIZE] = {0};
 371
 372   or_circuit_t *circ_tap = or_circuit_new(0, NULL);
 373   or_circuit_t *circ_ntor = or_circuit_new(0, NULL);
 374   or_circuit_t *circ_ntor3 = or_circuit_new(0, NULL);
 375
 376   create_cell_t *onionskin = NULL;
 377   create_cell_t *create_tap1 = tor_malloc_zero(sizeof(create_cell_t));
 378   create_cell_t *create_ntor1 = tor_malloc_zero(sizeof(create_cell_t));
 379   create_cell_t *create_ntor2 = tor_malloc_zero(sizeof(create_cell_t));
 380   create_cell_t *create_v3ntor1 = tor_malloc_zero(sizeof(create_cell_t));
 381   create_cell_t *create_v3ntor2 = tor_malloc_zero(sizeof(create_cell_t));
 382   (void)arg;
 383
 384   create_cell_init(create_tap1, CELL_CREATE, ONION_HANDSHAKE_TYPE_TAP,
 385                    TAP_ONIONSKIN_CHALLENGE_LEN, buf_tap);
 386   create_cell_init(create_ntor1, CELL_CREATE, ONION_HANDSHAKE_TYPE_NTOR,
 387                    NTOR_ONIONSKIN_LEN, buf_ntor);
 388   create_cell_init(create_ntor2, CELL_CREATE, ONION_HANDSHAKE_TYPE_NTOR,
 389                    NTOR_ONIONSKIN_LEN, buf_ntor);
 390   create_cell_init(create_v3ntor1, CELL_CREATE2, ONION_HANDSHAKE_TYPE_NTOR_V3,
 391                    NTOR_ONIONSKIN_LEN, buf_ntor3);
 392   create_cell_init(create_v3ntor2, CELL_CREATE2, ONION_HANDSHAKE_TYPE_NTOR_V3,
 393                    NTOR_ONIONSKIN_LEN, buf_ntor3);
 394
 395   /* sanity check queue init */
 396   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP));
 397   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR));
 398   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR_V3));
 399
 400   /* Add tap first so we can ensure it comes out last */
 401   tt_int_op(0,OP_EQ, onion_pending_add(circ_tap, create_tap1));
 402   tt_int_op(1,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP));
 403   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR));
 404   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR_V3));
 405
 406   /* Now add interleaving ntor2 and ntor3, to ensure they share
 407    * the same queue and come out in this order */
 408   tt_int_op(0,OP_EQ, onion_pending_add(circ_ntor, create_ntor1));
 409   tt_int_op(1,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP));
 410   tt_int_op(1,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR));
 411   tt_int_op(1,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR_V3));
 412
 413   tt_int_op(0,OP_EQ, onion_pending_add(circ_ntor3, create_v3ntor1));
 414   tt_int_op(1,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP));
 415   tt_int_op(2,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR));
 416   tt_int_op(2,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR_V3));
 417
 418   tt_int_op(0,OP_EQ, onion_pending_add(circ_ntor, create_ntor2));
 419   tt_int_op(1,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP));
 420   tt_int_op(3,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR));
 421   tt_int_op(3,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR_V3));
 422
 423   tt_int_op(0,OP_EQ, onion_pending_add(circ_ntor3, create_v3ntor2));
 424   tt_int_op(1,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP));
 425   tt_int_op(4,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR));
 426   tt_int_op(4,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR_V3));
 427
 428   /* Now remove 5 tasks, ensuring order and queue sizes */
 429   tt_ptr_op(circ_ntor, OP_EQ, onion_next_task(&onionskin));
 430   tt_int_op(1,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP));
 431   tt_int_op(3,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR));
 432   tt_int_op(3,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR_V3));
 433   tt_ptr_op(onionskin, OP_EQ, create_ntor1);
 434
 435   tt_ptr_op(circ_ntor3, OP_EQ, onion_next_task(&onionskin));
 436   tt_int_op(1,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP));
 437   tt_int_op(2,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR));
 438   tt_int_op(2,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR_V3));
 439   tt_ptr_op(onionskin, OP_EQ, create_v3ntor1);
 440
 441   tt_ptr_op(circ_ntor, OP_EQ, onion_next_task(&onionskin));
 442   tt_int_op(1,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP));
 443   tt_int_op(1,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR));
 444   tt_int_op(1,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR_V3));
 445   tt_ptr_op(onionskin, OP_EQ, create_ntor2);
 446
 447   tt_ptr_op(circ_ntor3, OP_EQ, onion_next_task(&onionskin));
 448   tt_int_op(1,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP));
 449   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR));
 450   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR_V3));
 451   tt_ptr_op(onionskin, OP_EQ, create_v3ntor2);
 452
 453   tt_ptr_op(circ_tap, OP_EQ, onion_next_task(&onionskin));
 454   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP));
 455   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR));
 456   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR_V3));
 457   tt_ptr_op(onionskin, OP_EQ, create_tap1);
 458
 459   clear_pending_onions();
 460   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_TAP));
 461   tt_int_op(0,OP_EQ, onion_num_pending(ONION_HANDSHAKE_TYPE_NTOR));
 462
 463  done:
 464   circuit_free_(TO_CIRCUIT(circ_tap));
 465   circuit_free_(TO_CIRCUIT(circ_ntor));
 466   circuit_free_(TO_CIRCUIT(circ_ntor3));
 467   tor_free(create_tap1);
 468   tor_free(create_ntor1);
 469   tor_free(create_ntor2);
 470   tor_free(create_v3ntor1);
 471   tor_free(create_v3ntor2);
 472 }
 473
 474 static int32_t cbtnummodes = 10;
 475
 476 static int32_t
 477 mock_xm_networkstatus_get_param(
 478     const networkstatus_t *ns, const char *param_name, int32_t default_val,
 479     int32_t min_val, int32_t max_val)
 480 {
 481   (void)ns;
 482   (void)default_val;
 483   (void)min_val;
 484   (void)max_val;
 485   // only support cbtnummodes right now
 486   tor_assert(strcmp(param_name, "cbtnummodes")==0);
 487   return cbtnummodes;
 488 }
 489
 490 static void
 491 test_circuit_timeout_xm_alpha(void *arg)
 492 {
 493   circuit_build_times_t cbt;
 494   build_time_t Xm;
 495   int alpha_ret;
 496   circuit_build_times_init(&cbt);
 497   (void)arg;
 498
 499   /* Plan:
 500    * 1. Create array of build times with 10 modes.
 501    * 2. Make sure Xm calc is sane for 1,3,5,10,15,20 modes.
 502    * 3. Make sure alpha calc is sane for 1,3,5,10,15,20 modes.
 503    */
 504
 505   /* 110 build times, 9 modes, 8 mode ties, 10 abandoned */
 506   build_time_t circuit_build_times[] = {
 507     100, 20, 1000, 500, 200, 5000, 30, 600, 200, 300, CBT_BUILD_ABANDONED,
 508     101, 21, 1001, 501, 201, 5001, 31, 601, 201, 301, CBT_BUILD_ABANDONED,
 509     102, 22, 1002, 502, 202, 5002, 32, 602, 202, 302, CBT_BUILD_ABANDONED,
 510     103, 23, 1003, 503, 203, 5003, 33, 603, 203, 303, CBT_BUILD_ABANDONED,
 511     104, 24, 1004, 504, 204, 5004, 34, 604, 204, 304, CBT_BUILD_ABANDONED,
 512     105, 25, 1005, 505, 205, 5005, 35, 605, 205, 305, CBT_BUILD_ABANDONED,
 513     106, 26, 1006, 506, 206, 5006, 36, 606, 206, 306, CBT_BUILD_ABANDONED,
 514     107, 27, 1007, 507, 207, 5007, 37, 607, 207, 307, CBT_BUILD_ABANDONED,
 515     108, 28, 1008, 508, 208, 5008, 38, 608, 208, 308, CBT_BUILD_ABANDONED,
 516     109, 29, 1009, 509, 209, 5009, 39, 609, 209, 309, CBT_BUILD_ABANDONED
 517   };
 518
 519   memcpy(cbt.circuit_build_times, circuit_build_times,
 520          sizeof(circuit_build_times));
 521   cbt.total_build_times = 110;
 522
 523   MOCK(networkstatus_get_param, mock_xm_networkstatus_get_param);
 524
 525 #define CBT_ALPHA_PRECISION 0.00001
 526   cbtnummodes = 1;
 527   Xm = circuit_build_times_get_xm(&cbt);
 528   alpha_ret = circuit_build_times_update_alpha(&cbt);
 529   tt_int_op(alpha_ret, OP_EQ, 1);
 530   tt_int_op(Xm, OP_EQ, 205);
 531   tt_assert(fabs(cbt.alpha - 1.394401) < CBT_ALPHA_PRECISION);
 532
 533   cbtnummodes = 3;
 534   Xm = circuit_build_times_get_xm(&cbt);
 535   alpha_ret = circuit_build_times_update_alpha(&cbt);
 536   tt_int_op(alpha_ret, OP_EQ, 1);
 537   tt_int_op(Xm, OP_EQ, 117);
 538   tt_assert(fabs(cbt.alpha - 0.902313) < CBT_ALPHA_PRECISION);
 539
 540   cbtnummodes = 5;
 541   Xm = circuit_build_times_get_xm(&cbt);
 542   alpha_ret = circuit_build_times_update_alpha(&cbt);
 543   tt_int_op(alpha_ret, OP_EQ, 1);
 544   tt_int_op(Xm, OP_EQ, 146);
 545   tt_assert(fabs(cbt.alpha - 1.049032) < CBT_ALPHA_PRECISION);
 546
 547   cbtnummodes = 10;
 548   Xm = circuit_build_times_get_xm(&cbt);
 549   alpha_ret = circuit_build_times_update_alpha(&cbt);
 550   tt_int_op(alpha_ret, OP_EQ, 1);
 551   tt_int_op(Xm, OP_EQ, 800);
 552   tt_assert(fabs(cbt.alpha - 4.851754) < CBT_ALPHA_PRECISION);
 553
 554   cbtnummodes = 15;
 555   Xm = circuit_build_times_get_xm(&cbt);
 556   alpha_ret = circuit_build_times_update_alpha(&cbt);
 557   tt_int_op(alpha_ret, OP_EQ, 1);
 558   tt_int_op(Xm, OP_EQ, 800);
 559   tt_assert(fabs(cbt.alpha - 4.851754) < CBT_ALPHA_PRECISION);
 560
 561   cbtnummodes = 20;
 562   Xm = circuit_build_times_get_xm(&cbt);
 563   alpha_ret = circuit_build_times_update_alpha(&cbt);
 564   tt_int_op(alpha_ret, OP_EQ, 1);
 565   tt_int_op(Xm, OP_EQ, 800);
 566   tt_assert(fabs(cbt.alpha - 4.851754) < CBT_ALPHA_PRECISION);
 567
 568  done:
 569 #undef CBT_ALPHA_PRECISION
 570   UNMOCK(networkstatus_get_param);
 571   circuit_build_times_free_timeouts(&cbt);
 572 }
 573
 574 static void
 575 test_circuit_timeout(void *arg)
 576 {
 577   /* Plan:
 578    *  1. Generate 1000 samples
 579    *  2. Estimate parameters
 580    *  3. If difference, repeat
 581    *  4. Save state
 582    *  5. load state
 583    *  6. Estimate parameters
 584    *  7. compare differences
 585    */
 586   circuit_build_times_t initial;
 587   circuit_build_times_t estimate;
 588   circuit_build_times_t final;
 589   double timeout1, timeout2;
 590   or_state_t *state=NULL;
 591   int i, runs;
 592   (void)arg;
 593
 594   initialize_periodic_events();
 595
 596   circuit_build_times_init(&initial);
 597   circuit_build_times_init(&estimate);
 598   circuit_build_times_init(&final);
 599
 600   state = or_state_new();
 601
 602   // Use a deterministic RNG here, or else we'll get nondeterministic
 603   // coverage in some of the circuitstats functions.
 604   testing_enable_deterministic_rng();
 605
 606   circuitbuild_running_unit_tests();
 607 #define timeout0 (build_time_t)(30*1000.0)
 608   initial.Xm = 3000;
 609   circuit_build_times_initial_alpha(&initial,
 610                                     CBT_DEFAULT_QUANTILE_CUTOFF/100.0,
 611                                     timeout0);
 612   do {
 613     for (i=0; i < CBT_DEFAULT_MIN_CIRCUITS_TO_OBSERVE; i++) {
 614       build_time_t sample = circuit_build_times_generate_sample(&initial,0,1);
 615
 616       circuit_build_times_add_time(&estimate, sample);
 617     }
 618     circuit_build_times_update_alpha(&estimate);
 619     timeout1 = circuit_build_times_calculate_timeout(&estimate,
 620                                   CBT_DEFAULT_QUANTILE_CUTOFF/100.0);
 621     circuit_build_times_set_timeout(&estimate);
 622     log_notice(LD_CIRC, "Timeout1 is %f, Xm is %d", timeout1, estimate.Xm);
 623            /* 2% error */
 624   } while (fabs(circuit_build_times_cdf(&initial, timeout0) -
 625                 circuit_build_times_cdf(&initial, timeout1)) > 0.02);
 626
 627   tt_int_op(estimate.total_build_times, OP_LE, CBT_NCIRCUITS_TO_OBSERVE);
 628
 629   circuit_build_times_update_state(&estimate, state);
 630   circuit_build_times_free_timeouts(&final);
 631   tt_int_op(circuit_build_times_parse_state(&final, state), OP_EQ, 0);
 632
 633   circuit_build_times_update_alpha(&final);
 634   timeout2 = circuit_build_times_calculate_timeout(&final,
 635                                  CBT_DEFAULT_QUANTILE_CUTOFF/100.0);
 636
 637   circuit_build_times_set_timeout(&final);
 638   log_notice(LD_CIRC, "Timeout2 is %f, Xm is %d", timeout2, final.Xm);
 639
 640   /* 5% here because some accuracy is lost due to histogram conversion */
 641   tt_assert(fabs(circuit_build_times_cdf(&initial, timeout0) -
 642                    circuit_build_times_cdf(&initial, timeout2)) < 0.05);
 643
 644   for (runs = 0; runs < 50; runs++) {
 645     int build_times_idx = 0;
 646     int total_build_times = 0;
 647
 648     final.close_ms = final.timeout_ms = CBT_DEFAULT_TIMEOUT_INITIAL_VALUE;
 649     estimate.close_ms = estimate.timeout_ms
 650                       = CBT_DEFAULT_TIMEOUT_INITIAL_VALUE;
 651
 652     for (i = 0; i < CBT_DEFAULT_RECENT_CIRCUITS*2; i++) {
 653       circuit_build_times_network_circ_success(&estimate);
 654       circuit_build_times_add_time(&estimate,
 655             circuit_build_times_generate_sample(&estimate, 0,
 656                 CBT_DEFAULT_QUANTILE_CUTOFF/100.0));
 657
 658       circuit_build_times_network_circ_success(&estimate);
 659       circuit_build_times_add_time(&final,
 660             circuit_build_times_generate_sample(&final, 0,
 661                 CBT_DEFAULT_QUANTILE_CUTOFF/100.0));
 662     }
 663
 664     tt_assert(!circuit_build_times_network_check_changed(&estimate));
 665     tt_assert(!circuit_build_times_network_check_changed(&final));
 666
 667     /* Reset liveness to be non-live */
 668     final.liveness.network_last_live = 0;
 669     estimate.liveness.network_last_live = 0;
 670
 671     build_times_idx = estimate.build_times_idx;
 672     total_build_times = estimate.total_build_times;
 673
 674     tt_assert(circuit_build_times_network_check_live(&estimate));
 675     tt_assert(circuit_build_times_network_check_live(&final));
 676
 677     circuit_build_times_count_close(&estimate, 0,
 678             (time_t)(approx_time()-estimate.close_ms/1000.0-1));
 679     circuit_build_times_count_close(&final, 0,
 680             (time_t)(approx_time()-final.close_ms/1000.0-1));
 681
 682     tt_assert(!circuit_build_times_network_check_live(&estimate));
 683     tt_assert(!circuit_build_times_network_check_live(&final));
 684
 685     log_info(LD_CIRC, "idx: %d %d, tot: %d %d",
 686              build_times_idx, estimate.build_times_idx,
 687              total_build_times, estimate.total_build_times);
 688
 689     /* Check rollback index. Should match top of loop. */
 690     tt_assert(build_times_idx == estimate.build_times_idx);
 691     // This can fail if estimate.total_build_times == 1000, because
 692     // in that case, rewind actually causes us to lose timeouts
 693     if (total_build_times != CBT_NCIRCUITS_TO_OBSERVE)
 694       tt_assert(total_build_times == estimate.total_build_times);
 695
 696     /* Now simulate that the network has become live and we need
 697      * a change */
 698     circuit_build_times_network_is_live(&estimate);
 699     circuit_build_times_network_is_live(&final);
 700
 701     for (i = 0; i < CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT; i++) {
 702       circuit_build_times_count_timeout(&estimate, 1);
 703
 704       if (i < CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT-1) {
 705         circuit_build_times_count_timeout(&final, 1);
 706       }
 707     }
 708
 709     tt_int_op(estimate.liveness.after_firsthop_idx, OP_EQ, 0);
 710     tt_assert(final.liveness.after_firsthop_idx ==
 711                 CBT_DEFAULT_MAX_RECENT_TIMEOUT_COUNT-1);
 712
 713     tt_assert(circuit_build_times_network_check_live(&estimate));
 714     tt_assert(circuit_build_times_network_check_live(&final));
 715
 716     circuit_build_times_count_timeout(&final, 1);
 717
 718     /* Ensure return value for degenerate cases are clamped correctly */
 719     initial.alpha = INT32_MAX;
 720     tt_assert(circuit_build_times_calculate_timeout(&initial, .99999999) <=
 721               INT32_MAX);
 722     initial.alpha = 0;
 723     tt_assert(circuit_build_times_calculate_timeout(&initial, .5) <=
 724               INT32_MAX);
 725   }
 726
 727  done:
 728   circuit_build_times_free_timeouts(&initial);
 729   circuit_build_times_free_timeouts(&estimate);
 730   circuit_build_times_free_timeouts(&final);
 731   or_state_free(state);
 732   teardown_periodic_events();
 733
 734   testing_disable_deterministic_rng();
 735 }
 736
 737 #define ENT(name)                                                       \
 738   { #name, test_ ## name , 0, NULL, NULL }
 739 #define FORK(name)                                                      \
 740   { #name, test_ ## name , TT_FORK, NULL, NULL }
 741
 742 static struct testcase_t test_array[] = {
 743   ENT(onion_handshake),
 744   { "bad_onion_handshake", test_bad_onion_handshake, 0, NULL, NULL },
 745   ENT(onion_queues),
 746   ENT(onion_queue_order),
 747   { "ntor_handshake", test_ntor_handshake, 0, NULL, NULL },
 748   { "fast_handshake", test_fast_handshake, 0, NULL, NULL },
 749   FORK(circuit_timeout),
 750   FORK(circuit_timeout_xm_alpha),
 751
 752   END_OF_TESTCASES
 753 };
 754
 755 struct testgroup_t testgroups[] = {
 756   { "", test_array },
 757   { "accounting/", accounting_tests },
 758   { "addr/", addr_tests },
 759   { "address/", address_tests },
 760   { "address_set/", address_set_tests },
 761   { "bridges/", bridges_tests },
 762   { "buffer/", buffer_tests },
 763   { "bwmgt/", bwmgt_tests },
 764   { "cellfmt/", cell_format_tests },
 765   { "cellqueue/", cell_queue_tests },
 766   { "channel/", channel_tests },
 767   { "channelpadding/", channelpadding_tests },
 768   { "channeltls/", channeltls_tests },
 769   { "checkdir/", checkdir_tests },
 770   { "circuitbuild/", circuitbuild_tests },
 771   { "circuitpadding/", circuitpadding_tests },
 772   { "circuitlist/", circuitlist_tests },
 773   { "circuitmux/", circuitmux_tests },
 774   { "circuitmux_ewma/", circuitmux_ewma_tests },
 775   { "circuitstats/", circuitstats_tests },
 776   { "circuituse/", circuituse_tests },
 777   { "compat/libevent/", compat_libevent_tests },
 778   { "config/", config_tests },
 779   { "config/mgr/", confmgr_tests },
 780   { "config/parse/", confparse_tests },
 781   { "connection/", connection_tests },
 782   { "conscache/", conscache_tests },
 783   { "consdiff/", consdiff_tests },
 784   { "consdiffmgr/", consdiffmgr_tests },
 785   { "container/", container_tests },
 786   { "container/namemap/", namemap_tests },
 787   { "control/", controller_tests },
 788   { "control/btrack/", btrack_tests },
 789   { "control/event/", controller_event_tests },
 790   { "crypto/", crypto_tests },
 791   { "crypto/ope/", crypto_ope_tests },
 792 #ifdef ENABLE_OPENSSL
 793   { "crypto/openssl/", crypto_openssl_tests },
 794 #endif
 795   { "crypto/pem/", pem_tests },
 796   { "crypto/rng/", crypto_rng_tests },
 797   { "dir/", dir_tests },
 798   { "dir/auth/ports/", dirauth_port_tests },
 799   { "dir/auth/process_descs/", process_descs_tests },
 800   { "dir/md/", microdesc_tests },
 801   { "dirauth/dirvote/", dirvote_tests},
 802   { "dir/voting/flags/", voting_flags_tests },
 803   { "dir/voting/schedule/", voting_schedule_tests },
 804   { "dir_handle_get/", dir_handle_get_tests },
 805   { "dispatch/", dispatch_tests, },
 806   { "dns/", dns_tests },
 807   { "dos/", dos_tests },
 808   { "entryconn/", entryconn_tests },
 809   { "entrynodes/", entrynodes_tests },
 810   { "extorport/", extorport_tests },
 811   { "geoip/", geoip_tests },
 812   { "guardfraction/", guardfraction_tests },
 813   { "hs_cache/", hs_cache },
 814   { "hs_cell/", hs_cell_tests },
 815   { "hs_client/", hs_client_tests },
 816   { "hs_common/", hs_common_tests },
 817   { "hs_config/", hs_config_tests },
 818   { "hs_control/", hs_control_tests },
 819   { "hs_descriptor/", hs_descriptor },
 820   { "hs_dos/", hs_dos_tests },
 821   { "hs_intropoint/", hs_intropoint_tests },
 822   { "hs_metrics/", hs_metrics_tests },
 823   { "hs_ntor/", hs_ntor_tests },
 824   { "hs_ob/", hs_ob_tests },
 825   { "hs_service/", hs_service_tests },
 826   { "keypin/", keypin_tests },
 827   { "link-handshake/", link_handshake_tests },
 828   { "mainloop/", mainloop_tests },
 829   { "metrics/", metrics_tests },
 830   { "netinfo/", netinfo_tests },
 831   { "nodelist/", nodelist_tests },
 832   { "oom/", oom_tests },
 833   { "onion-handshake/ntor-v3/", ntor_v3_tests },
 834   { "oos/", oos_tests },
 835   { "options/", options_tests },
 836   { "options/act/", options_act_tests },
 837   { "parsecommon/", parsecommon_tests },
 838   { "periodic-event/" , periodic_event_tests },
 839   { "policy/" , policy_tests },
 840   { "prob_distr/", prob_distr_tests },
 841   { "procmon/", procmon_tests },
 842   { "process/", process_tests },
 843   { "proto/haproxy/", proto_haproxy_tests },
 844   { "proto/http/", proto_http_tests },
 845   { "proto/misc/", proto_misc_tests },
 846   { "protover/", protover_tests },
 847   { "pt/", pt_tests },
 848   { "pubsub/build/", pubsub_build_tests },
 849   { "pubsub/msg/", pubsub_msg_tests },
 850   { "relay/" , relay_tests },
 851   { "relaycell/", relaycell_tests },
 852   { "relaycrypt/", relaycrypt_tests },
 853   { "replaycache/", replaycache_tests },
 854   { "router/", router_tests },
 855   { "routerkeys/", routerkeys_tests },
 856   { "routerlist/", routerlist_tests },
 857   { "routerset/" , routerset_tests },
 858 #ifdef USE_LIBSECCOMP
 859   { "sandbox/" , sandbox_tests },
 860 #endif
 861   { "scheduler/", scheduler_tests },
 862   { "sendme/", sendme_tests },
 863   { "shared-random/", sr_tests },
 864   { "socks/", socks_tests },
 865   { "statefile/", statefile_tests },
 866   { "stats/", stats_tests },
 867   { "status/" , status_tests },
 868   { "storagedir/", storagedir_tests },
 869   { "token_bucket/", token_bucket_tests },
 870   { "tortls/", tortls_tests },
 871 #ifndef ENABLE_NSS
 872   { "tortls/openssl/", tortls_openssl_tests },
 873 #endif
 874   { "tortls/x509/", x509_tests },
 875   { "util/", util_tests },
 876   { "util/format/", util_format_tests },
 877   { "util/handle/", handle_tests },
 878   { "util/logging/", logging_tests },
 879   { "util/process/", util_process_tests },
 880   { "util/thread/", thread_tests },
 881   END_OF_GROUPS
 882 };