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
usage(char * prog_name)64 usage(char *prog_name) {
65 printf("usage: %s [ -t | -v ]\n", prog_name);
66 exit(255);
67 }
68
69 int
main(int argc,char * argv[])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
print_rdbx(rdbx_t * rdbx)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
rdbx_check_add(rdbx_t * rdbx,uint32_t idx)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
rdbx_check_expect_failure(rdbx_t * rdbx,uint32_t idx)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
rdbx_check_unordered(rdbx_t * rdbx,uint32_t idx)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
test_replay_dbx(int num_trials,unsigned long ws)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
rdbx_check_adds_per_second(int num_trials,unsigned long ws)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