rdbx_driver.c 9.78 KB
Newer Older
Cullen Jennings's avatar
Cullen Jennings committed
1 2 3 4 5 6 7 8 9
/*
 * rdbx_driver.c
 *
 * driver for the rdbx implementation (replay database with extended range)
 *
 * David A. McGrew
 * Cisco Systems, Inc.
 */
/*
10
 *
Geir Istad's avatar
Geir Istad committed
11
 * Copyright (c) 2001-2017, Cisco Systems, Inc.
Cullen Jennings's avatar
Cullen Jennings committed
12
 * All rights reserved.
13
 *
Cullen Jennings's avatar
Cullen Jennings committed
14 15 16
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
17
 *
Cullen Jennings's avatar
Cullen Jennings committed
18 19
 *   Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
20
 *
Cullen Jennings's avatar
Cullen Jennings committed
21 22 23 24
 *   Redistributions in binary form must reproduce the above
 *   copyright notice, this list of conditions and the following
 *   disclaimer in the documentation and/or other materials provided
 *   with the distribution.
25
 *
Cullen Jennings's avatar
Cullen Jennings committed
26 27 28
 *   Neither the name of the Cisco Systems, Inc. nor the names of its
 *   contributors may be used to endorse or promote products derived
 *   from this software without specific prior written permission.
29
 *
Cullen Jennings's avatar
Cullen Jennings committed
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

45
#ifdef HAVE_CONFIG_H
46
#include <config.h>
47 48
#endif

49 50
#include <stdio.h>    /* for printf()          */
#include "getopt_s.h" /* for local getopt()    */
Cullen Jennings's avatar
Cullen Jennings committed
51 52 53 54

#include "rdbx.h"

#ifdef ROC_TEST
55
#error "srtp_rdbx_t won't work with ROC_TEST - bitmask same size as seq_median"
Cullen Jennings's avatar
Cullen Jennings committed
56 57 58 59
#endif

#include "ut_sim.h"

60
srtp_err_status_t test_replay_dbx(int num_trials, unsigned long ws);
Cullen Jennings's avatar
Cullen Jennings committed
61

62
double rdbx_check_adds_per_second(int num_trials, unsigned long ws);
Cullen Jennings's avatar
Cullen Jennings committed
63

64 65 66 67
void usage(char *prog_name)
{
    printf("usage: %s [ -t | -v ]\n", prog_name);
    exit(255);
Cullen Jennings's avatar
Cullen Jennings committed
68 69
}

70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
int main(int argc, char *argv[])
{
    double rate;
    srtp_err_status_t status;
    int q;
    unsigned do_timing_test = 0;
    unsigned do_validation = 0;

    /* process input arguments */
    while (1) {
        q = getopt_s(argc, argv, "tv");
        if (q == -1)
            break;
        switch (q) {
        case 't':
            do_timing_test = 1;
            break;
        case 'v':
            do_validation = 1;
            break;
        default:
            usage(argv[0]);
        }
93 94
    }

95 96 97
    printf("rdbx (replay database w/ extended range) test driver\n"
           "David A. McGrew\n"
           "Cisco Systems, Inc.\n");
98

99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
    if (!do_validation && !do_timing_test)
        usage(argv[0]);

    if (do_validation) {
        printf("testing srtp_rdbx_t (ws=128)...\n");

        status = test_replay_dbx(1 << 12, 128);
        if (status) {
            printf("failed\n");
            exit(1);
        }
        printf("passed\n");

        printf("testing srtp_rdbx_t (ws=1024)...\n");

        status = test_replay_dbx(1 << 12, 1024);
        if (status) {
            printf("failed\n");
            exit(1);
        }
        printf("passed\n");
Cullen Jennings's avatar
Cullen Jennings committed
120 121
    }

122 123 124 125 126 127 128 129
    if (do_timing_test) {
        rate = rdbx_check_adds_per_second(1 << 18, 128);
        printf("rdbx_check/replay_adds per second (ws=128): %e\n", rate);
        rate = rdbx_check_adds_per_second(1 << 18, 1024);
        printf("rdbx_check/replay_adds per second (ws=1024): %e\n", rate);
    }

    return 0;
Cullen Jennings's avatar
Cullen Jennings committed
130 131
}

132 133 134 135 136 137
void print_rdbx(srtp_rdbx_t *rdbx)
{
    char buf[2048];
    printf("rdbx: {%llu, %s}\n", (unsigned long long)(rdbx->index),
           bitvector_bit_string(&rdbx->bitmask, buf, sizeof(buf)));
}
Cullen Jennings's avatar
Cullen Jennings committed
138 139 140 141 142

/*
 * rdbx_check_add(rdbx, idx) checks a known-to-be-good idx against
 * rdbx, then adds it.  if a failure is detected (i.e., the check
 * indicates that the value is already in rdbx) then
143
 * srtp_err_status_algo_fail is returned.
Cullen Jennings's avatar
Cullen Jennings committed
144 145 146
 *
 */

147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169
srtp_err_status_t rdbx_check_add(srtp_rdbx_t *rdbx, uint32_t idx)
{
    int delta;
    srtp_xtd_seq_num_t est;

    delta = srtp_index_guess(&rdbx->index, &est, idx);

    if (srtp_rdbx_check(rdbx, delta) != srtp_err_status_ok) {
        printf("replay_check failed at index %u\n", idx);
        return srtp_err_status_algo_fail;
    }

    /*
     * in practice, we'd authenticate the packet containing idx, using
     * the estimated value est, at this point
     */

    if (srtp_rdbx_add_index(rdbx, delta) != srtp_err_status_ok) {
        printf("rdbx_add_index failed at index %u\n", idx);
        return srtp_err_status_algo_fail;
    }

    return srtp_err_status_ok;
Cullen Jennings's avatar
Cullen Jennings committed
170 171 172
}

/*
173
 * rdbx_check_expect_failure(srtp_rdbx_t *rdbx, uint32_t idx)
174
 *
Cullen Jennings's avatar
Cullen Jennings committed
175 176 177 178
 * checks that a sequence number idx is in the replay database
 * and thus will be rejected
 */

179 180 181 182 183
srtp_err_status_t rdbx_check_expect_failure(srtp_rdbx_t *rdbx, uint32_t idx)
{
    int delta;
    srtp_xtd_seq_num_t est;
    srtp_err_status_t status;
Cullen Jennings's avatar
Cullen Jennings committed
184

185
    delta = srtp_index_guess(&rdbx->index, &est, idx);
Cullen Jennings's avatar
Cullen Jennings committed
186

187 188 189 190 191 192
    status = srtp_rdbx_check(rdbx, delta);
    if (status == srtp_err_status_ok) {
        printf("delta: %d ", delta);
        printf("replay_check failed at index %u (false positive)\n", idx);
        return srtp_err_status_algo_fail;
    }
Cullen Jennings's avatar
Cullen Jennings committed
193

194
    return srtp_err_status_ok;
Cullen Jennings's avatar
Cullen Jennings committed
195 196
}

197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217
srtp_err_status_t rdbx_check_add_unordered(srtp_rdbx_t *rdbx, uint32_t idx)
{
    int delta;
    srtp_xtd_seq_num_t est;
    srtp_err_status_t rstat;

    delta = srtp_index_guess(&rdbx->index, &est, idx);

    rstat = srtp_rdbx_check(rdbx, delta);
    if ((rstat != srtp_err_status_ok) &&
        (rstat != srtp_err_status_replay_old)) {
        printf("replay_check_add_unordered failed at index %u\n", idx);
        return srtp_err_status_algo_fail;
    }
    if (rstat == srtp_err_status_replay_old) {
        return srtp_err_status_ok;
    }
    if (srtp_rdbx_add_index(rdbx, delta) != srtp_err_status_ok) {
        printf("rdbx_add_index failed at index %u\n", idx);
        return srtp_err_status_algo_fail;
    }
Cullen Jennings's avatar
Cullen Jennings committed
218

219
    return srtp_err_status_ok;
Cullen Jennings's avatar
Cullen Jennings committed
220 221
}

222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316
srtp_err_status_t test_replay_dbx(int num_trials, unsigned long ws)
{
    srtp_rdbx_t rdbx;
    uint32_t idx, ircvd;
    ut_connection utc;
    srtp_err_status_t status;
    int num_fp_trials;

    status = srtp_rdbx_init(&rdbx, ws);
    if (status) {
        printf("replay_init failed with error code %d\n", status);
        exit(1);
    }

    /*
     *  test sequential insertion
     */
    printf("\ttesting sequential insertion...");
    for (idx = 0; (int)idx < num_trials; idx++) {
        status = rdbx_check_add(&rdbx, idx);
        if (status)
            return status;
    }
    printf("passed\n");

    /*
     *  test for false positives by checking all of the index
     *  values which we've just added
     *
     * note that we limit the number of trials here, since allowing the
     * rollover counter to roll over would defeat this test
     */
    num_fp_trials = num_trials % 0x10000;
    if (num_fp_trials == 0) {
        printf("warning: no false positive tests performed\n");
    }
    printf("\ttesting for false positives...");
    for (idx = 0; (int)idx < num_fp_trials; idx++) {
        status = rdbx_check_expect_failure(&rdbx, idx);
        if (status)
            return status;
    }
    printf("passed\n");

    /* re-initialize */
    srtp_rdbx_dealloc(&rdbx);

    if (srtp_rdbx_init(&rdbx, ws) != srtp_err_status_ok) {
        printf("replay_init failed\n");
        return srtp_err_status_init_fail;
    }

    /*
     * test non-sequential insertion
     *
     * this test covers only fase negatives, since the values returned
     * by ut_next_index(...) are distinct
     */
    ut_init(&utc);

    printf("\ttesting non-sequential insertion...");
    for (idx = 0; (int)idx < num_trials; idx++) {
        ircvd = ut_next_index(&utc);
        status = rdbx_check_add_unordered(&rdbx, ircvd);
        if (status)
            return status;
        status = rdbx_check_expect_failure(&rdbx, ircvd);
        if (status)
            return status;
    }
    printf("passed\n");

    /* re-initialize */
    srtp_rdbx_dealloc(&rdbx);

    if (srtp_rdbx_init(&rdbx, ws) != srtp_err_status_ok) {
        printf("replay_init failed\n");
        return srtp_err_status_init_fail;
    }

    /*
     * test insertion with large gaps.
     * check for false positives for each insertion.
     */
    printf("\ttesting insertion with large gaps...");
    for (idx = 0, ircvd = 0; (int)idx < num_trials;
         idx++, ircvd += (1 << (rand() % 12))) {
        status = rdbx_check_add(&rdbx, ircvd);
        if (status)
            return status;
        status = rdbx_check_expect_failure(&rdbx, ircvd);
        if (status)
            return status;
    }
    printf("passed\n");
Cullen Jennings's avatar
Cullen Jennings committed
317

318
    srtp_rdbx_dealloc(&rdbx);
Cullen Jennings's avatar
Cullen Jennings committed
319

320
    return srtp_err_status_ok;
Cullen Jennings's avatar
Cullen Jennings committed
321 322
}

323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357
#include <time.h>   /* for clock()  */
#include <stdlib.h> /* for random() */

double rdbx_check_adds_per_second(int num_trials, unsigned long ws)
{
    uint32_t i;
    int delta;
    srtp_rdbx_t rdbx;
    srtp_xtd_seq_num_t est;
    clock_t timer;
    int failures; /* count number of failures */

    if (srtp_rdbx_init(&rdbx, ws) != srtp_err_status_ok) {
        printf("replay_init failed\n");
        exit(1);
    }

    failures = 0;
    timer = clock();
    for (i = 0; (int)i < num_trials; i++) {
        delta = srtp_index_guess(&rdbx.index, &est, i);

        if (srtp_rdbx_check(&rdbx, delta) != srtp_err_status_ok)
            ++failures;
        else if (srtp_rdbx_add_index(&rdbx, delta) != srtp_err_status_ok)
            ++failures;
    }
    timer = clock() - timer;

    printf("number of failures: %d \n", failures);

    srtp_rdbx_dealloc(&rdbx);

    return (double)CLOCKS_PER_SEC * num_trials / timer;
}