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
main(void)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
print_rdb(rdb_t * rdb)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
rdb_check_add(rdb_t * rdb,uint32_t idx)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
rdb_check_expect_failure(rdb_t * rdb,uint32_t idx)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
rdb_check_add_unordered(rdb_t * rdb,uint32_t idx)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
test_rdb_db()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
rdb_check_adds_per_second(void)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