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