1 /*
2  * stats.c
3  *
4  * statistical tests
5  *
6  * David A. McGrew
7  * Cisco Systems, Inc.
8  */
9 
10 /*
11  *
12  * Copyright (c) 2001-2017, 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 #ifdef HAVE_CONFIG_H
47 #include <config.h>
48 #endif
49 
50 #include "stat.h"
51 
52 srtp_debug_module_t srtp_mod_stat = {
53     0,                  /* debugging is off by default */
54     (char *)"stat test" /* printable module name       */
55 };
56 
57 /*
58  * each test assumes that 20,000 bits (2500 octets) of data is
59  * provided as input
60  */
61 
62 #define STAT_TEST_DATA_LEN 2500
63 
stat_test_monobit(uint8_t * data)64 srtp_err_status_t stat_test_monobit(uint8_t *data)
65 {
66     uint8_t *data_end = data + STAT_TEST_DATA_LEN;
67     uint16_t ones_count;
68 
69     ones_count = 0;
70     while (data < data_end) {
71         ones_count += octet_get_weight(*data);
72         data++;
73     }
74 
75     debug_print(srtp_mod_stat, "bit count: %d", ones_count);
76 
77     if ((ones_count < 9725) || (ones_count > 10275))
78         return srtp_err_status_algo_fail;
79 
80     return srtp_err_status_ok;
81 }
82 
stat_test_poker(uint8_t * data)83 srtp_err_status_t stat_test_poker(uint8_t *data)
84 {
85     int i;
86     uint8_t *data_end = data + STAT_TEST_DATA_LEN;
87     double poker;
88     uint16_t f[16] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
89 
90     while (data < data_end) {
91         f[*data & 0x0f]++; /* increment freq. count for low nibble  */
92         f[(*data) >> 4]++; /* increment freq. count for high nibble */
93         data++;
94     }
95 
96     poker = 0.0;
97     for (i = 0; i < 16; i++)
98         poker += (double)f[i] * f[i];
99 
100     poker *= (16.0 / 5000.0);
101     poker -= 5000.0;
102 
103     debug_print(srtp_mod_stat, "poker test: %f\n", poker);
104 
105     if ((poker < 2.16) || (poker > 46.17))
106         return srtp_err_status_algo_fail;
107 
108     return srtp_err_status_ok;
109 }
110 
111 /*
112  * runs[i] holds the number of runs of size (i-1)
113  */
114 
stat_test_runs(uint8_t * data)115 srtp_err_status_t stat_test_runs(uint8_t *data)
116 {
117     uint8_t *data_end = data + STAT_TEST_DATA_LEN;
118     uint16_t runs[6] = { 0, 0, 0, 0, 0, 0 };
119     uint16_t gaps[6] = { 0, 0, 0, 0, 0, 0 };
120     uint16_t lo_value[6] = { 2315, 1114, 527, 240, 103, 103 };
121     uint16_t hi_value[6] = { 2685, 1386, 723, 384, 209, 209 };
122     int state = 0;
123     uint16_t mask;
124     int i;
125 
126     /*
127      * the state variable holds the number of bits in the
128      * current run (or gap, if negative)
129      */
130 
131     while (data < data_end) {
132         /* loop over the bits of this byte */
133         for (mask = 1; mask < 256; mask <<= 1) {
134             if (*data & mask) {
135                 /* next bit is a one  */
136                 if (state > 0) {
137                     /* prefix is a run, so increment the run-count  */
138                     state++;
139 
140                     /* check for long runs */
141                     if (state > 25) {
142                         debug_print(srtp_mod_stat, ">25 runs: %d", state);
143                         return srtp_err_status_algo_fail;
144                     }
145 
146                 } else if (state < 0) {
147                     /* prefix is a gap  */
148                     if (state < -25) {
149                         debug_print(srtp_mod_stat, ">25 gaps: %d", state);
150                         return srtp_err_status_algo_fail; /* long-runs test
151                                                              failed   */
152                     }
153                     if (state < -6) {
154                         state = -6; /* group together gaps > 5 */
155                     }
156                     gaps[-1 - state]++; /* increment gap count      */
157                     state = 1;          /* set state at one set bit */
158                 } else {
159                     /* state is zero; this happens only at initialization */
160                     state = 1;
161                 }
162             } else {
163                 /* next bit is a zero  */
164                 if (state > 0) {
165                     /* prefix is a run */
166                     if (state > 25) {
167                         debug_print(srtp_mod_stat, ">25 runs (2): %d", state);
168                         return srtp_err_status_algo_fail; /* long-runs test
169                                                              failed   */
170                     }
171                     if (state > 6) {
172                         state = 6; /* group together runs > 5 */
173                     }
174                     runs[state - 1]++; /* increment run count       */
175                     state = -1;        /* set state at one zero bit */
176                 } else if (state < 0) {
177                     /* prefix is a gap, so increment gap-count (decrement state)
178                      */
179                     state--;
180 
181                     /* check for long gaps */
182                     if (state < -25) {
183                         debug_print(srtp_mod_stat, ">25 gaps (2): %d", state);
184                         return srtp_err_status_algo_fail;
185                     }
186 
187                 } else {
188                     /* state is zero; this happens only at initialization */
189                     state = -1;
190                 }
191             }
192         }
193 
194         /* move along to next octet */
195         data++;
196     }
197 
198     if (srtp_mod_stat.on) {
199         debug_print(srtp_mod_stat, "runs test", NULL);
200         for (i = 0; i < 6; i++)
201             debug_print(srtp_mod_stat, "  runs[]: %d", runs[i]);
202         for (i = 0; i < 6; i++)
203             debug_print(srtp_mod_stat, "  gaps[]: %d", gaps[i]);
204     }
205 
206     /* check run and gap counts against the fixed limits */
207     for (i = 0; i < 6; i++)
208         if ((runs[i] < lo_value[i]) || (runs[i] > hi_value[i]) ||
209             (gaps[i] < lo_value[i]) || (gaps[i] > hi_value[i]))
210             return srtp_err_status_algo_fail;
211 
212     return srtp_err_status_ok;
213 }
214