1 /* 2 * rdbx_driver.c 3 * 4 * driver for the rdbx implementation (replay database with extended range) 5 * 6 * David A. McGrew 7 * Cisco Systems, Inc. 8 */ 9 10 /* 11 * 12 * Copyright (c) 2001-2006, Cisco Systems, Inc. 13 * All rights reserved. 14 * 15 * Redistribution and use in source and binary forms, with or without 16 * modification, are permitted provided that the following conditions 17 * are met: 18 * 19 * Redistributions of source code must retain the above copyright 20 * notice, this list of conditions and the following disclaimer. 21 * 22 * Redistributions in binary form must reproduce the above 23 * copyright notice, this list of conditions and the following 24 * disclaimer in the documentation and/or other materials provided 25 * with the distribution. 26 * 27 * Neither the name of the Cisco Systems, Inc. nor the names of its 28 * contributors may be used to endorse or promote products derived 29 * from this software without specific prior written permission. 30 * 31 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 32 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 33 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 34 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 35 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 36 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 37 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 38 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 39 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 40 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 41 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 42 * OF THE POSSIBILITY OF SUCH DAMAGE. 43 * 44 */ 45 46 #include <stdio.h> /* for printf() */ 47 #include "getopt_s.h" /* for local getopt() */ 48 49 #include "rdbx.h" 50 51 #ifdef ROC_TEST 52 #error "rdbx_t won't work with ROC_TEST - bitmask same size as seq_median" 53 #endif 54 55 #include "ut_sim.h" 56 57 err_status_t 58 test_replay_dbx(int num_trials, unsigned long ws); 59 60 double 61 rdbx_check_adds_per_second(int num_trials, unsigned long ws); 62 63 void 64 usage(char *prog_name) { 65 printf("usage: %s [ -t | -v ]\n", prog_name); 66 exit(255); 67 } 68 69 int 70 main (int argc, char *argv[]) { 71 double rate; 72 err_status_t status; 73 int q; 74 unsigned do_timing_test = 0; 75 unsigned do_validation = 0; 76 77 /* process input arguments */ 78 while (1) { 79 q = getopt_s(argc, argv, "tv"); 80 if (q == -1) 81 break; 82 switch (q) { 83 case 't': 84 do_timing_test = 1; 85 break; 86 case 'v': 87 do_validation = 1; 88 break; 89 default: 90 usage(argv[0]); 91 } 92 } 93 94 printf("rdbx (replay database w/ extended range) test driver\n" 95 "David A. McGrew\n" 96 "Cisco Systems, Inc.\n"); 97 98 if (!do_validation && !do_timing_test) 99 usage(argv[0]); 100 101 if (do_validation) { 102 printf("testing rdbx_t (ws=128)...\n"); 103 104 status = test_replay_dbx(1 << 12, 128); 105 if (status) { 106 printf("failed\n"); 107 exit(1); 108 } 109 printf("passed\n"); 110 111 printf("testing rdbx_t (ws=1024)...\n"); 112 113 status = test_replay_dbx(1 << 12, 1024); 114 if (status) { 115 printf("failed\n"); 116 exit(1); 117 } 118 printf("passed\n"); 119 } 120 121 if (do_timing_test) { 122 rate = rdbx_check_adds_per_second(1 << 18, 128); 123 printf("rdbx_check/replay_adds per second (ws=128): %e\n", rate); 124 rate = rdbx_check_adds_per_second(1 << 18, 1024); 125 printf("rdbx_check/replay_adds per second (ws=1024): %e\n", rate); 126 } 127 128 return 0; 129 } 130 131 void 132 print_rdbx(rdbx_t *rdbx) { 133 char buf[2048]; 134 printf("rdbx: {%llu, %s}\n", 135 (unsigned long long)(rdbx->index), 136 bitvector_bit_string(&rdbx->bitmask, buf, sizeof(buf)) 137 ); 138 } 139 140 141 /* 142 * rdbx_check_add(rdbx, idx) checks a known-to-be-good idx against 143 * rdbx, then adds it. if a failure is detected (i.e., the check 144 * indicates that the value is already in rdbx) then 145 * err_status_algo_fail is returned. 146 * 147 */ 148 149 err_status_t 150 rdbx_check_add(rdbx_t *rdbx, uint32_t idx) { 151 int delta; 152 xtd_seq_num_t est; 153 154 delta = index_guess(&rdbx->index, &est, idx); 155 156 if (rdbx_check(rdbx, delta) != err_status_ok) { 157 printf("replay_check failed at index %u\n", idx); 158 return err_status_algo_fail; 159 } 160 161 /* 162 * in practice, we'd authenticate the packet containing idx, using 163 * the estimated value est, at this point 164 */ 165 166 if (rdbx_add_index(rdbx, delta) != err_status_ok) { 167 printf("rdbx_add_index failed at index %u\n", idx); 168 return err_status_algo_fail; 169 } 170 171 return err_status_ok; 172 } 173 174 /* 175 * rdbx_check_expect_failure(rdbx_t *rdbx, uint32_t idx) 176 * 177 * checks that a sequence number idx is in the replay database 178 * and thus will be rejected 179 */ 180 181 err_status_t 182 rdbx_check_expect_failure(rdbx_t *rdbx, uint32_t idx) { 183 int delta; 184 xtd_seq_num_t est; 185 err_status_t status; 186 187 delta = index_guess(&rdbx->index, &est, idx); 188 189 status = rdbx_check(rdbx, delta); 190 if (status == err_status_ok) { 191 printf("delta: %d ", delta); 192 printf("replay_check failed at index %u (false positive)\n", idx); 193 return err_status_algo_fail; 194 } 195 196 return err_status_ok; 197 } 198 199 err_status_t 200 rdbx_check_add_unordered(rdbx_t *rdbx, uint32_t idx) { 201 int delta; 202 xtd_seq_num_t est; 203 err_status_t rstat; 204 205 delta = index_guess(&rdbx->index, &est, idx); 206 207 rstat = rdbx_check(rdbx, delta); 208 if ((rstat != err_status_ok) && (rstat != err_status_replay_old)) { 209 printf("replay_check_add_unordered failed at index %u\n", idx); 210 return err_status_algo_fail; 211 } 212 if (rstat == err_status_replay_old) { 213 return err_status_ok; 214 } 215 if (rdbx_add_index(rdbx, delta) != err_status_ok) { 216 printf("rdbx_add_index failed at index %u\n", idx); 217 return err_status_algo_fail; 218 } 219 220 return err_status_ok; 221 } 222 223 err_status_t 224 test_replay_dbx(int num_trials, unsigned long ws) { 225 rdbx_t rdbx; 226 uint32_t idx, ircvd; 227 ut_connection utc; 228 err_status_t status; 229 int num_fp_trials; 230 231 status = rdbx_init(&rdbx, ws); 232 if (status) { 233 printf("replay_init failed with error code %d\n", status); 234 exit(1); 235 } 236 237 /* 238 * test sequential insertion 239 */ 240 printf("\ttesting sequential insertion..."); 241 for (idx=0; idx < num_trials; idx++) { 242 status = rdbx_check_add(&rdbx, idx); 243 if (status) 244 return status; 245 } 246 printf("passed\n"); 247 248 /* 249 * test for false positives by checking all of the index 250 * values which we've just added 251 * 252 * note that we limit the number of trials here, since allowing the 253 * rollover counter to roll over would defeat this test 254 */ 255 num_fp_trials = num_trials % 0x10000; 256 if (num_fp_trials == 0) { 257 printf("warning: no false positive tests performed\n"); 258 } 259 printf("\ttesting for false positives..."); 260 for (idx=0; idx < num_fp_trials; idx++) { 261 status = rdbx_check_expect_failure(&rdbx, idx); 262 if (status) 263 return status; 264 } 265 printf("passed\n"); 266 267 /* re-initialize */ 268 rdbx_dealloc(&rdbx); 269 270 if (rdbx_init(&rdbx, ws) != err_status_ok) { 271 printf("replay_init failed\n"); 272 return err_status_init_fail; 273 } 274 275 /* 276 * test non-sequential insertion 277 * 278 * this test covers only fase negatives, since the values returned 279 * by ut_next_index(...) are distinct 280 */ 281 ut_init(&utc); 282 283 printf("\ttesting non-sequential insertion..."); 284 for (idx=0; idx < num_trials; idx++) { 285 ircvd = ut_next_index(&utc); 286 status = rdbx_check_add_unordered(&rdbx, ircvd); 287 if (status) 288 return status; 289 status = rdbx_check_expect_failure(&rdbx, ircvd); 290 if (status) 291 return status; 292 } 293 printf("passed\n"); 294 295 /* re-initialize */ 296 rdbx_dealloc(&rdbx); 297 298 if (rdbx_init(&rdbx, ws) != err_status_ok) { 299 printf("replay_init failed\n"); 300 return err_status_init_fail; 301 } 302 303 /* 304 * test insertion with large gaps. 305 * check for false positives for each insertion. 306 */ 307 printf("\ttesting insertion with large gaps..."); 308 for (idx=0, ircvd=0; idx < num_trials; idx++, ircvd += (1 << (rand() % 12))) { 309 status = rdbx_check_add(&rdbx, ircvd); 310 if (status) 311 return status; 312 status = rdbx_check_expect_failure(&rdbx, ircvd); 313 if (status) 314 return status; 315 } 316 printf("passed\n"); 317 318 rdbx_dealloc(&rdbx); 319 320 return err_status_ok; 321 } 322 323 324 325 #include <time.h> /* for clock() */ 326 #include <stdlib.h> /* for random() */ 327 328 double 329 rdbx_check_adds_per_second(int num_trials, unsigned long ws) { 330 uint32_t i; 331 int delta; 332 rdbx_t rdbx; 333 xtd_seq_num_t est; 334 clock_t timer; 335 int failures; /* count number of failures */ 336 337 if (rdbx_init(&rdbx, ws) != err_status_ok) { 338 printf("replay_init failed\n"); 339 exit(1); 340 } 341 342 failures = 0; 343 timer = clock(); 344 for(i=0; i < num_trials; i++) { 345 346 delta = index_guess(&rdbx.index, &est, i); 347 348 if (rdbx_check(&rdbx, delta) != err_status_ok) 349 ++failures; 350 else 351 if (rdbx_add_index(&rdbx, delta) != err_status_ok) 352 ++failures; 353 } 354 timer = clock() - timer; 355 356 printf("number of failures: %d \n", failures); 357 358 rdbx_dealloc(&rdbx); 359 360 return (double) CLOCKS_PER_SEC * num_trials / timer; 361 } 362 363
