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
56unsigned num_trials = 1 << 16;
57
58err_status_t
59test_rdb_db(void);
60
61double
62rdb_check_adds_per_second(void);
63
64int
65main (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
83void
84print_rdb(rdb_t *rdb) {
85  printf("rdb: {%u, %s}\n", rdb->window_start, v128_bit_string(&rdb->bitmask));
86}
87
88err_status_t
89rdb_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
103err_status_t
104rdb_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
116err_status_t
117rdb_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
137err_status_t
138test_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
227double
228rdb_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