1 /* 2 * replay_driver.c 3 * 4 * A driver for the replay_database implementation 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> 47 48 #include "rdb.h" 49 #include "ut_sim.h" 50 51 /* 52 * num_trials defines the number of trials that are used in the 53 * validation functions below 54 */ 55 56 unsigned num_trials = 1 << 16; 57 58 err_status_t 59 test_rdb_db(void); 60 61 double 62 rdb_check_adds_per_second(void); 63 64 int 65 main (void) { 66 err_status_t err; 67 68 printf("testing anti-replay database (rdb_t)...\n"); 69 err = test_rdb_db(); 70 if (err) { 71 printf("failed\n"); 72 exit(1); 73 } 74 printf("done\n"); 75 76 printf("rdb_check/rdb_adds per second: %e\n", 77 rdb_check_adds_per_second()); 78 79 return 0; 80 } 81 82 83 void 84 print_rdb(rdb_t *rdb) { 85 printf("rdb: {%u, %s}\n", rdb->window_start, v128_bit_string(&rdb->bitmask)); 86 } 87 88 err_status_t 89 rdb_check_add(rdb_t *rdb, uint32_t idx) { 90 91 if (rdb_check(rdb, idx) != err_status_ok) { 92 printf("rdb_check failed at index %u\n", idx); 93 return err_status_fail; 94 } 95 if (rdb_add_index(rdb, idx) != err_status_ok) { 96 printf("rdb_add_index failed at index %u\n", idx); 97 return err_status_fail; 98 } 99 100 return err_status_ok; 101 } 102 103 err_status_t 104 rdb_check_expect_failure(rdb_t *rdb, uint32_t idx) { 105 err_status_t err; 106 107 err = rdb_check(rdb, idx); 108 if ((err != err_status_replay_old) && (err != err_status_replay_fail)) { 109 printf("rdb_check failed at index %u (false positive)\n", idx); 110 return err_status_fail; 111 } 112 113 return err_status_ok; 114 } 115 116 err_status_t 117 rdb_check_add_unordered(rdb_t *rdb, uint32_t idx) { 118 err_status_t rstat; 119 120 /* printf("index: %u\n", idx); */ 121 rstat = rdb_check(rdb, idx); 122 if ((rstat != err_status_ok) && (rstat != err_status_replay_old)) { 123 printf("rdb_check_add_unordered failed at index %u\n", idx); 124 return rstat; 125 } 126 if (rstat == err_status_replay_old) { 127 return err_status_ok; 128 } 129 if (rdb_add_index(rdb, idx) != err_status_ok) { 130 printf("rdb_add_index failed at index %u\n", idx); 131 return err_status_fail; 132 } 133 134 return err_status_ok; 135 } 136 137 err_status_t 138 test_rdb_db() { 139 rdb_t rdb; 140 uint32_t idx, ircvd; 141 ut_connection utc; 142 err_status_t err; 143 144 if (rdb_init(&rdb) != err_status_ok) { 145 printf("rdb_init failed\n"); 146 return err_status_init_fail; 147 } 148 149 /* test sequential insertion */ 150 for (idx=0; idx < num_trials; idx++) { 151 err = rdb_check_add(&rdb, idx); 152 if (err) 153 return err; 154 } 155 156 /* test for false positives */ 157 for (idx=0; idx < num_trials; idx++) { 158 err = rdb_check_expect_failure(&rdb, idx); 159 if (err) 160 return err; 161 } 162 163 /* re-initialize */ 164 if (rdb_init(&rdb) != err_status_ok) { 165 printf("rdb_init failed\n"); 166 return err_status_fail; 167 } 168 169 /* test non-sequential insertion */ 170 ut_init(&utc); 171 172 for (idx=0; idx < num_trials; idx++) { 173 ircvd = ut_next_index(&utc); 174 err = rdb_check_add_unordered(&rdb, ircvd); 175 if (err) 176 return err; 177 err = rdb_check_expect_failure(&rdb, ircvd); 178 if (err) 179 return err; 180 } 181 182 /* re-initialize */ 183 if (rdb_init(&rdb) != err_status_ok) { 184 printf("rdb_init failed\n"); 185 return err_status_fail; 186 } 187 188 /* test insertion with large gaps */ 189 for (idx=0, ircvd=0; idx < num_trials; idx++, ircvd += (1 << (rand() % 10))) { 190 err = rdb_check_add(&rdb, ircvd); 191 if (err) 192 return err; 193 err = rdb_check_expect_failure(&rdb, ircvd); 194 if (err) 195 return err; 196 } 197 198 /* re-initialize */ 199 if (rdb_init(&rdb) != err_status_ok) { 200 printf("rdb_init failed\n"); 201 return err_status_fail; 202 } 203 204 /* test loss of first 513 packets */ 205 for (idx=0; idx < num_trials; idx++) { 206 err = rdb_check_add(&rdb, idx + 513); 207 if (err) 208 return err; 209 } 210 211 /* test for false positives */ 212 for (idx=0; idx < num_trials + 513; idx++) { 213 err = rdb_check_expect_failure(&rdb, idx); 214 if (err) 215 return err; 216 } 217 218 219 return err_status_ok; 220 } 221 222 #include <time.h> /* for clock() */ 223 #include <stdlib.h> /* for random() */ 224 225 #define REPLAY_NUM_TRIALS 10000000 226 227 double 228 rdb_check_adds_per_second(void) { 229 uint32_t i; 230 rdb_t rdb; 231 clock_t timer; 232 int failures; /* count number of failures */ 233 234 if (rdb_init(&rdb) != err_status_ok) { 235 printf("rdb_init failed\n"); 236 exit(1); 237 } 238 239 timer = clock(); 240 for(i=0; i < REPLAY_NUM_TRIALS; i+=3) { 241 if (rdb_check(&rdb, i+2) != err_status_ok) 242 ++failures; 243 if (rdb_add_index(&rdb, i+2) != err_status_ok) 244 ++failures; 245 if (rdb_check(&rdb, i+1) != err_status_ok) 246 ++failures; 247 if (rdb_add_index(&rdb, i+1) != err_status_ok) 248 ++failures; 249 if (rdb_check(&rdb, i) != err_status_ok) 250 ++failures; 251 if (rdb_add_index(&rdb, i) != err_status_ok) 252 ++failures; 253 } 254 timer = clock() - timer; 255 256 return (double) CLOCKS_PER_SEC * REPLAY_NUM_TRIALS / timer; 257 } 258