diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-08-17 17:33:40 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-08-17 17:33:40 +0000 |
commit | 2d58b31cd35b301814fd63be1e3cdc03b80a4fba (patch) | |
tree | 1fab434bb5ac7440c990be2fcb8bdf592de37210 /src/regex | |
parent | 14c98ff17a8b1e4db1e6445f6116b7be5b4b8934 (diff) | |
download | gnunet-2d58b31cd35b301814fd63be1e3cdc03b80a4fba.tar.gz gnunet-2d58b31cd35b301814fd63be1e3cdc03b80a4fba.zip |
Fixed eval test case and stack smashing protection
Diffstat (limited to 'src/regex')
-rw-r--r-- | src/regex/regex.c | 5 | ||||
-rw-r--r-- | src/regex/test_regex_eval_api.c | 100 |
2 files changed, 69 insertions, 36 deletions
diff --git a/src/regex/regex.c b/src/regex/regex.c index 694386e9a..79d94ea03 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -630,7 +630,8 @@ GNUNET_REGEX_automaton_traverse (const struct GNUNET_REGEX_Automaton *a, | |||
630 | if (NULL == a || 0 == a->state_count) | 630 | if (NULL == a || 0 == a->state_count) |
631 | return; | 631 | return; |
632 | 632 | ||
633 | for (count = 0, s = a->states_head; NULL != s; s = s->next, count++) | 633 | for (count = 0, s = a->states_head; NULL != s && count < a->state_count; |
634 | s = s->next, count++) | ||
634 | { | 635 | { |
635 | s->traversal_id = count; | 636 | s->traversal_id = count; |
636 | marks[s->traversal_id] = GNUNET_NO; | 637 | marks[s->traversal_id] = GNUNET_NO; |
@@ -750,7 +751,7 @@ GNUNET_REGEX_add_multi_strides_to_dfa (struct GNUNET_REGEX_Context *regex_ctx, | |||
750 | struct GNUNET_REGEX_Automaton *dfa, | 751 | struct GNUNET_REGEX_Automaton *dfa, |
751 | const unsigned int stride_len) | 752 | const unsigned int stride_len) |
752 | { | 753 | { |
753 | struct GNUNET_REGEX_Strided_Context ctx = { stride_len, NULL, NULL}; | 754 | struct GNUNET_REGEX_Strided_Context ctx = { stride_len, NULL, NULL }; |
754 | struct GNUNET_REGEX_Transition *t; | 755 | struct GNUNET_REGEX_Transition *t; |
755 | struct GNUNET_REGEX_Transition *t_next; | 756 | struct GNUNET_REGEX_Transition *t_next; |
756 | 757 | ||
diff --git a/src/regex/test_regex_eval_api.c b/src/regex/test_regex_eval_api.c index 37fd38c0d..2de7d40b2 100644 --- a/src/regex/test_regex_eval_api.c +++ b/src/regex/test_regex_eval_api.c | |||
@@ -46,7 +46,8 @@ struct Regex_String_Pair | |||
46 | /** | 46 | /** |
47 | * Random regex test. Generate a random regex as well as 'str_count' strings to | 47 | * Random regex test. Generate a random regex as well as 'str_count' strings to |
48 | * match it against. Will match using GNUNET_REGEX implementation and compare | 48 | * match it against. Will match using GNUNET_REGEX implementation and compare |
49 | * the result to glibc regex result. 'rx_length' has to be smaller then 'max_str_len'. | 49 | * the result to glibc regex result. 'rx_length' has to be smaller then |
50 | * 'max_str_len'. | ||
50 | * | 51 | * |
51 | * @param rx_length length of the regular expression. | 52 | * @param rx_length length of the regular expression. |
52 | * @param max_str_len maximum length of the random strings. | 53 | * @param max_str_len maximum length of the random strings. |
@@ -64,34 +65,33 @@ test_random (unsigned int rx_length, unsigned int max_str_len, | |||
64 | int eval; | 65 | int eval; |
65 | int eval_check; | 66 | int eval_check; |
66 | int eval_canonical; | 67 | int eval_canonical; |
68 | int eval_canonical_check; | ||
67 | struct GNUNET_REGEX_Automaton *dfa; | 69 | struct GNUNET_REGEX_Automaton *dfa; |
68 | regex_t rx; | 70 | regex_t rx; |
69 | regmatch_t matchptr[1]; | 71 | regmatch_t matchptr[1]; |
70 | char error[200]; | 72 | char error[200]; |
71 | int result; | 73 | int result; |
72 | size_t str_len; | ||
73 | char *canonical_regex; | 74 | char *canonical_regex; |
74 | 75 | ||
75 | // At least one string is needed for matching | 76 | /* At least one string is needed for matching */ |
76 | GNUNET_assert (str_count > 0); | 77 | GNUNET_assert (str_count > 0); |
77 | // The string should be at least as long as the regex itself | 78 | /* The string should be at least as long as the regex itself */ |
78 | GNUNET_assert (max_str_len >= rx_length); | 79 | GNUNET_assert (max_str_len >= rx_length); |
79 | 80 | ||
80 | // Generate random regex and a string that matches the regex | 81 | /* Generate random regex and a string that matches the regex */ |
81 | matching_str = GNUNET_malloc (rx_length + 1); | 82 | matching_str = GNUNET_malloc (rx_length + 1); |
82 | rand_rx = GNUNET_REGEX_generate_random_regex (rx_length, matching_str); | 83 | rand_rx = GNUNET_REGEX_generate_random_regex (rx_length, matching_str); |
83 | 84 | ||
84 | // Now match | 85 | /* Now match */ |
85 | result = 0; | 86 | result = 0; |
86 | for (i = 0; i < str_count; i++) | 87 | for (i = 0; i < str_count; i++) |
87 | { | 88 | { |
88 | if (0 < i) | 89 | if (0 < i) |
89 | { | 90 | { |
90 | matching_str = GNUNET_REGEX_generate_random_string (max_str_len); | 91 | matching_str = GNUNET_REGEX_generate_random_string (max_str_len); |
91 | str_len = strlen (matching_str); | ||
92 | } | 92 | } |
93 | 93 | ||
94 | // Match string using DFA | 94 | /* Match string using DFA */ |
95 | dfa = GNUNET_REGEX_construct_dfa (rand_rx, strlen (rand_rx)); | 95 | dfa = GNUNET_REGEX_construct_dfa (rand_rx, strlen (rand_rx)); |
96 | if (NULL == dfa) | 96 | if (NULL == dfa) |
97 | { | 97 | { |
@@ -100,26 +100,39 @@ test_random (unsigned int rx_length, unsigned int max_str_len, | |||
100 | } | 100 | } |
101 | 101 | ||
102 | eval = GNUNET_REGEX_eval (dfa, matching_str); | 102 | eval = GNUNET_REGEX_eval (dfa, matching_str); |
103 | /* save the canonical regex for later comparison */ | ||
103 | canonical_regex = GNUNET_strdup (GNUNET_REGEX_get_canonical_regex (dfa)); | 104 | canonical_regex = GNUNET_strdup (GNUNET_REGEX_get_canonical_regex (dfa)); |
104 | GNUNET_REGEX_automaton_destroy (dfa); | 105 | GNUNET_REGEX_automaton_destroy (dfa); |
105 | 106 | ||
106 | // Match string using glibc regex | 107 | /* Match string using glibc regex */ |
107 | if (0 != regcomp (&rx, rand_rx, REG_EXTENDED)) | 108 | if (0 != regcomp (&rx, rand_rx, REG_EXTENDED)) |
108 | { | 109 | { |
109 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 110 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, |
110 | "Could not compile regex using regcomp\n"); | 111 | "Could not compile regex using regcomp: %s\n", rand_rx); |
111 | return -1; | 112 | return -1; |
112 | } | 113 | } |
113 | 114 | ||
114 | eval_check = regexec (&rx, matching_str, 1, matchptr, 0); | 115 | eval_check = regexec (&rx, matching_str, 1, matchptr, 0); |
115 | regfree (&rx); | 116 | regfree (&rx); |
116 | 117 | ||
117 | // We only want to match the whole string, because that's what our DFA does, too. | 118 | /* We only want to match the whole string, because that's what our DFA does, |
119 | * too. */ | ||
118 | if (eval_check == 0 && | 120 | if (eval_check == 0 && |
119 | (matchptr[0].rm_so != 0 || matchptr[0].rm_eo != strlen (matching_str))) | 121 | (matchptr[0].rm_so != 0 || matchptr[0].rm_eo != strlen (matching_str))) |
120 | eval_check = 1; | 122 | eval_check = 1; |
121 | 123 | ||
122 | // Match canonical regex | 124 | /* Match canonical regex */ |
125 | dfa = | ||
126 | GNUNET_REGEX_construct_dfa (canonical_regex, strlen (canonical_regex)); | ||
127 | if (NULL == dfa) | ||
128 | { | ||
129 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Constructing DFA failed\n"); | ||
130 | return -1; | ||
131 | } | ||
132 | |||
133 | eval_canonical = GNUNET_REGEX_eval (dfa, matching_str); | ||
134 | GNUNET_REGEX_automaton_destroy (dfa); | ||
135 | |||
123 | if (0 != regcomp (&rx, canonical_regex, REG_EXTENDED)) | 136 | if (0 != regcomp (&rx, canonical_regex, REG_EXTENDED)) |
124 | { | 137 | { |
125 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 138 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, |
@@ -128,17 +141,24 @@ test_random (unsigned int rx_length, unsigned int max_str_len, | |||
128 | return -1; | 141 | return -1; |
129 | } | 142 | } |
130 | 143 | ||
131 | eval_canonical = regexec (&rx, matching_str, 1, matchptr, 0); | 144 | eval_canonical_check = regexec (&rx, matching_str, 1, matchptr, 0); |
132 | regfree (&rx); | 145 | regfree (&rx); |
133 | GNUNET_free (canonical_regex); | ||
134 | 146 | ||
135 | // compare result | 147 | /* We only want to match the whole string, because that's what our DFA does, |
136 | if (eval_check != eval) | 148 | * too. */ |
149 | if (eval_canonical_check == 0 && | ||
150 | (matchptr[0].rm_so != 0 || matchptr[0].rm_eo != strlen (matching_str))) | ||
151 | eval_canonical_check = 1; | ||
152 | |||
153 | /* compare results */ | ||
154 | if (eval_check != eval || eval_canonical != eval_canonical_check) | ||
137 | { | 155 | { |
138 | regerror (eval_check, &rx, error, sizeof error); | 156 | regerror (eval_check, &rx, error, sizeof error); |
139 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 157 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Unexpected result:\nregex: %s\ncanonical_regex: %s\n\ |
140 | "Unexpected result:\nregex: %s\nstring: %s\ngnunet regex: %i\nglibc regex: %i\nglibc error: %s\n\n", | 158 | string: %s\ngnunet regex: %i\nglibc regex: %i\n\ |
141 | rand_rx, matching_str, eval, eval_check, error); | 159 | canonical regex: %i\ncanonical regex glibc: %i\n\ |
160 | glibc error: %s\n\n", rand_rx, canonical_regex, matching_str, | ||
161 | eval, eval_check, eval_canonical, eval_canonical_check, error); | ||
142 | result += 1; | 162 | result += 1; |
143 | } | 163 | } |
144 | 164 | ||
@@ -146,6 +166,7 @@ test_random (unsigned int rx_length, unsigned int max_str_len, | |||
146 | } | 166 | } |
147 | 167 | ||
148 | GNUNET_free (rand_rx); | 168 | GNUNET_free (rand_rx); |
169 | GNUNET_free (canonical_regex); | ||
149 | 170 | ||
150 | return result; | 171 | return result; |
151 | } | 172 | } |
@@ -157,7 +178,8 @@ test_random (unsigned int rx_length, unsigned int max_str_len, | |||
157 | * | 178 | * |
158 | * @param a automaton. | 179 | * @param a automaton. |
159 | * @param rx compiled glibc regex. | 180 | * @param rx compiled glibc regex. |
160 | * @param rxstr regular expression and strings with expected results to match against. | 181 | * @param rxstr regular expression and strings with expected results to |
182 | * match against. | ||
161 | * | 183 | * |
162 | * @return 0 on successfull, non 0 otherwise | 184 | * @return 0 on successfull, non 0 otherwise |
163 | */ | 185 | */ |
@@ -185,7 +207,8 @@ test_automaton (struct GNUNET_REGEX_Automaton *a, regex_t * rx, | |||
185 | eval = GNUNET_REGEX_eval (a, rxstr->strings[i]); | 207 | eval = GNUNET_REGEX_eval (a, rxstr->strings[i]); |
186 | eval_check = regexec (rx, rxstr->strings[i], 1, matchptr, 0); | 208 | eval_check = regexec (rx, rxstr->strings[i], 1, matchptr, 0); |
187 | 209 | ||
188 | // We only want to match the whole string, because that's what our DFA does, too. | 210 | /* We only want to match the whole string, because that's what our DFA does, |
211 | * too. */ | ||
189 | if (eval_check == 0 && | 212 | if (eval_check == 0 && |
190 | (matchptr[0].rm_so != 0 || | 213 | (matchptr[0].rm_so != 0 || |
191 | matchptr[0].rm_eo != strlen (rxstr->strings[i]))) | 214 | matchptr[0].rm_eo != strlen (rxstr->strings[i]))) |
@@ -198,11 +221,13 @@ test_automaton (struct GNUNET_REGEX_Automaton *a, regex_t * rx, | |||
198 | result = 1; | 221 | result = 1; |
199 | regerror (eval_check, rx, error, sizeof error); | 222 | regerror (eval_check, rx, error, sizeof error); |
200 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 223 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, |
201 | "Unexpected result:\nregex: %s\ncanonical_regex: %s\nstring: %s\nexpected result: %i\n" | 224 | "Unexpected result:\nregex: %s\ncanonical_regex: %s\n" |
202 | "gnunet regex: %i\nglibc regex: %i\nglibc error: %s\nrm_so: %i\nrm_eo: %i\n\n", | 225 | "string: %s\nexpected result: %i\n" |
203 | rxstr->regex, GNUNET_REGEX_get_canonical_regex (a), | 226 | "gnunet regex: %i\nglibc regex: %i\nglibc error: %s\n" |
204 | rxstr->strings[i], rxstr->expected_results[i], eval, | 227 | "rm_so: %i\nrm_eo: %i\n\n", rxstr->regex, |
205 | eval_check, error, matchptr[0].rm_so, matchptr[0].rm_eo); | 228 | GNUNET_REGEX_get_canonical_regex (a), rxstr->strings[i], |
229 | rxstr->expected_results[i], eval, eval_check, error, | ||
230 | matchptr[0].rm_so, matchptr[0].rm_eo); | ||
206 | } | 231 | } |
207 | } | 232 | } |
208 | return result; | 233 | return result; |
@@ -227,16 +252,18 @@ main (int argc, char *argv[]) | |||
227 | int check_rand; | 252 | int check_rand; |
228 | char *check_proof; | 253 | char *check_proof; |
229 | 254 | ||
230 | struct Regex_String_Pair rxstr[16] = { | 255 | struct Regex_String_Pair rxstr[17] = { |
231 | {"ab?(abcd)?", 5, | 256 | {"ab?(abcd)?", 5, |
232 | {"ababcd", "abab", "aabcd", "a", "abb"}, | 257 | {"ababcd", "abab", "aabcd", "a", "abb"}, |
233 | {match, nomatch, match, match, nomatch}}, | 258 | {match, nomatch, match, match, nomatch}}, |
234 | {"ab(c|d)+c*(a(b|c)d)+", 5, | 259 | {"ab(c|d)+c*(a(b|c)d)+", 5, |
235 | {"abcdcdcdcdddddabd", "abcd", "abcddddddccccccccccccccccccccccccabdacdabd", | 260 | {"abcdcdcdcdddddabd", "abcd", |
261 | "abcddddddccccccccccccccccccccccccabdacdabd", | ||
236 | "abccccca", "abcdcdcdccdabdabd"}, | 262 | "abccccca", "abcdcdcdccdabdabd"}, |
237 | {match, nomatch, match, nomatch, match}}, | 263 | {match, nomatch, match, nomatch, match}}, |
238 | {"ab+c*(a(bx|c)d)+", 5, | 264 | {"ab+c*(a(bx|c)d)+", 5, |
239 | {"abcdcdcdcdddddabd", "abcd", "abcddddddccccccccccccccccccccccccabdacdabd", | 265 | {"abcdcdcdcdddddabd", "abcd", |
266 | "abcddddddccccccccccccccccccccccccabdacdabd", | ||
240 | "abccccca", "abcdcdcdccdabdabd"}, | 267 | "abccccca", "abcdcdcdccdabdabd"}, |
241 | {nomatch, nomatch, nomatch, nomatch, nomatch}}, | 268 | {nomatch, nomatch, nomatch, nomatch, nomatch}}, |
242 | {"a+X*y+c|p|R|Z*K*y*R+w|Y*6+n+h*k*w+V*F|W*B*e*", 1, | 269 | {"a+X*y+c|p|R|Z*K*y*R+w|Y*6+n+h*k*w+V*F|W*B*e*", 1, |
@@ -255,7 +282,8 @@ main (int argc, char *argv[]) | |||
255 | {"", "bla", "blabla", "bl", "la", "b", "l", "a"}, | 282 | {"", "bla", "blabla", "bl", "la", "b", "l", "a"}, |
256 | {match, match, match, nomatch, nomatch, nomatch, nomatch, nomatch}}, | 283 | {match, match, match, nomatch, nomatch, nomatch, nomatch, nomatch}}, |
257 | {"ab(c|d)+c*(a(b|c)+d)+(bla)(bla)*", 8, | 284 | {"ab(c|d)+c*(a(b|c)+d)+(bla)(bla)*", 8, |
258 | {"ab", "abcabdbla", "abdcccccccccccabcbccdblablabla", "bl", "la", "b", "l", | 285 | {"ab", "abcabdbla", "abdcccccccccccabcbccdblablabla", "bl", "la", "b", |
286 | "l", | ||
259 | "a"}, | 287 | "a"}, |
260 | {nomatch, match, match, nomatch, nomatch, nomatch, nomatch, nomatch}}, | 288 | {nomatch, match, match, nomatch, nomatch, nomatch, nomatch, nomatch}}, |
261 | {"a|aa*a", 6, | 289 | {"a|aa*a", 6, |
@@ -278,6 +306,9 @@ main (int argc, char *argv[]) | |||
278 | {nomatch, match, match}}, | 306 | {nomatch, match, match}}, |
279 | {"ab(c|d)+c*(a(b|c)d)+", 1, | 307 | {"ab(c|d)+c*(a(b|c)d)+", 1, |
280 | {"abacd"}, | 308 | {"abacd"}, |
309 | {nomatch}}, | ||
310 | {"d|5kl", 1, | ||
311 | {"d5kl"}, | ||
281 | {nomatch}} | 312 | {nomatch}} |
282 | }; | 313 | }; |
283 | 314 | ||
@@ -285,7 +316,7 @@ main (int argc, char *argv[]) | |||
285 | check_dfa = 0; | 316 | check_dfa = 0; |
286 | check_rand = 0; | 317 | check_rand = 0; |
287 | 318 | ||
288 | for (i = 0; i < 16; i++) | 319 | for (i = 0; i < 17; i++) |
289 | { | 320 | { |
290 | if (0 != regcomp (&rx, rxstr[i].regex, REG_EXTENDED)) | 321 | if (0 != regcomp (&rx, rxstr[i].regex, REG_EXTENDED)) |
291 | { | 322 | { |
@@ -294,12 +325,12 @@ main (int argc, char *argv[]) | |||
294 | return 1; | 325 | return 1; |
295 | } | 326 | } |
296 | 327 | ||
297 | // NFA test | 328 | /* NFA test */ |
298 | a = GNUNET_REGEX_construct_nfa (rxstr[i].regex, strlen (rxstr[i].regex)); | 329 | a = GNUNET_REGEX_construct_nfa (rxstr[i].regex, strlen (rxstr[i].regex)); |
299 | check_nfa += test_automaton (a, &rx, &rxstr[i]); | 330 | check_nfa += test_automaton (a, &rx, &rxstr[i]); |
300 | GNUNET_REGEX_automaton_destroy (a); | 331 | GNUNET_REGEX_automaton_destroy (a); |
301 | 332 | ||
302 | // DFA test | 333 | /* DFA test */ |
303 | a = GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex)); | 334 | a = GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex)); |
304 | check_dfa += test_automaton (a, &rx, &rxstr[i]); | 335 | check_dfa += test_automaton (a, &rx, &rxstr[i]); |
305 | check_proof = GNUNET_strdup (GNUNET_REGEX_get_canonical_regex (a)); | 336 | check_proof = GNUNET_strdup (GNUNET_REGEX_get_canonical_regex (a)); |
@@ -315,9 +346,10 @@ main (int argc, char *argv[]) | |||
315 | regfree (&rx); | 346 | regfree (&rx); |
316 | } | 347 | } |
317 | 348 | ||
349 | /* Random tests */ | ||
318 | srand (time (NULL)); | 350 | srand (time (NULL)); |
319 | for (i = 0; i < 50; i++) | 351 | for (i = 0; i < 50; i++) |
320 | check_rand += test_random (100, 120, 20); | 352 | check_rand += test_random (50, 60, 30); |
321 | 353 | ||
322 | return check_nfa + check_dfa + check_rand; | 354 | return check_nfa + check_dfa + check_rand; |
323 | } | 355 | } |