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 char 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_unordered(rdbx_t *rdbx, uint32_t idx) { 201 err_status_t rstat; 202 203 rstat = rdbx_check(rdbx, idx); 204 if ((rstat != err_status_ok) && (rstat != err_status_replay_old)) { 205 printf("replay_check_unordered failed at index %u\n", idx); 206 return err_status_algo_fail; 207 } 208 return err_status_ok; 209 } 210 211 err_status_t 212 test_replay_dbx(int num_trials, unsigned long ws) { 213 rdbx_t rdbx; 214 uint32_t idx, ircvd; 215 ut_connection utc; 216 err_status_t status; 217 int num_fp_trials; 218 219 status = rdbx_init(&rdbx, ws); 220 if (status) { 221 printf("replay_init failed with error code %d\n", status); 222 exit(1); 223 } 224 225 /* 226 * test sequential insertion 227 */ 228 printf("\ttesting sequential insertion..."); 229 for (idx=0; idx < (uint32_t)num_trials; idx++) { 230 status = rdbx_check_add(&rdbx, idx); 231 if (status) 232 return status; 233 } 234 printf("passed\n"); 235 236 /* 237 * test for false positives by checking all of the index 238 * values which we've just added 239 * 240 * note that we limit the number of trials here, since allowing the 241 * rollover counter to roll over would defeat this test 242 */ 243 num_fp_trials = num_trials % 0x10000; 244 if (num_fp_trials == 0) { 245 printf("warning: no false positive tests performed\n"); 246 } 247 printf("\ttesting for false positives..."); 248 for (idx=0; idx < (uint32_t)num_fp_trials; idx++) { 249 status = rdbx_check_expect_failure(&rdbx, idx); 250 if (status) 251 return status; 252 } 253 printf("passed\n"); 254 255 /* re-initialize */ 256 rdbx_uninit(&rdbx); 257 258 if (rdbx_init(&rdbx, ws) != err_status_ok) { 259 printf("replay_init failed\n"); 260 return err_status_init_fail; 261 } 262 263 /* 264 * test non-sequential insertion 265 * 266 * this test covers only fase negatives, since the values returned 267 * by ut_next_index(...) are distinct 268 */ 269 ut_init(&utc); 270 271 printf("\ttesting non-sequential insertion..."); 272 for (idx=0; idx < (uint32_t)num_trials; idx++) { 273 ircvd = ut_next_index(&utc); 274 status = rdbx_check_unordered(&rdbx, ircvd); 275 if (status) 276 return status; 277 } 278 printf("passed\n"); 279 280 /* 281 * test a replay condition close to zero. 282 */ 283 rdbx_uninit(&rdbx); 284 285 if (rdbx_init(&rdbx, ws) != err_status_ok) { 286 printf("replay_init failed\n"); 287 return err_status_init_fail; 288 } 289 290 printf("\ttesting replay close to zero..."); 291 status = rdbx_check_add(&rdbx, 1); 292 if (status) 293 return status; 294 status = rdbx_check_expect_failure(&rdbx, 64500); 295 if (status) 296 return status; 297 status = rdbx_check_add(&rdbx, 2); 298 if (status) 299 return status; 300 printf("passed\n"); 301 302 rdbx_uninit(&rdbx); 303 304 return err_status_ok; 305 } 306 307 308 309 #include <time.h> /* for clock() */ 310 #include <stdlib.h> /* for random() */ 311 312 double 313 rdbx_check_adds_per_second(int num_trials, unsigned long ws) { 314 uint32_t i; 315 int delta; 316 rdbx_t rdbx; 317 xtd_seq_num_t est; 318 clock_t timer; 319 int failures; /* count number of failures */ 320 321 if (rdbx_init(&rdbx, ws) != err_status_ok) { 322 printf("replay_init failed\n"); 323 exit(1); 324 } 325 326 failures = 0; 327 timer = clock(); 328 for(i=0; i < (uint32_t)num_trials; i++) { 329 330 delta = index_guess(&rdbx.index, &est, i); 331 332 if (rdbx_check(&rdbx, delta) != err_status_ok) 333 ++failures; 334 else 335 if (rdbx_add_index(&rdbx, delta) != err_status_ok) 336 ++failures; 337 } 338 timer = clock() - timer; 339 340 printf("number of failures: %d \n", failures); 341 342 rdbx_uninit(&rdbx); 343 344 return (double) CLOCKS_PER_SEC * num_trials / timer; 345 } 346
