break-loader.c revision d839b3d0b42f40f874392f88197e596e9b7d3387 
1/* -*- mode: C; c-file-style: "gnu" -*- */
2/* dbus-break-loader.c  Program to find byte streams that break the message loader
3 *
4 * Copyright (C) 2003  Red Hat Inc.
5 *
6 * Licensed under the Academic Free License version 2.0
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
21 *
22 */
23
24#include <dbus/dbus.h>
25#include <sys/stat.h>
26#include <sys/types.h>
27#include <fcntl.h>
28#include <stdio.h>
29#include <stdlib.h>
30#include <unistd.h>
31#include <errno.h>
32#include <sys/wait.h>
33#include <string.h>
34
35#define DBUS_COMPILATION
36#include <dbus/dbus-string.h>
37#include <dbus/dbus-internals.h>
38#include <dbus/dbus-test.h>
39#include <dbus/dbus-marshal.h>
40#undef DBUS_COMPILATION
41
42static DBusString failure_dir;
43static int total_attempts;
44static int failures_this_iteration;
45
46static int
47random_int_in_range (int start,
48                     int end)
49{
50  /* such elegant math */
51  double gap;
52  double v_double;
53  int v;
54
55  if (start == end)
56    return start;
57
58  _dbus_assert (end > start);
59
60  gap = end - start - 1; /* -1 to not include "end" */
61  v_double = ((double)start) + (((double)rand ())/RAND_MAX) * gap;
62  if (v_double < 0.0)
63    v = (v_double - 0.5);
64  else
65    v = (v_double + 0.5);
66
67  if (v < start)
68    {
69      fprintf (stderr, "random_int_in_range() generated %d for range [%d,%d)\n",
70               v, start, end);
71      v = start;
72    }
73  else if (v >= end)
74    {
75      fprintf (stderr, "random_int_in_range() generated %d for range [%d,%d)\n",
76               v, start, end);
77      v = end - 1;
78    }
79
80  /* printf ("  %d of [%d,%d)\n", v, start, end); */
81
82  return v;
83}
84
85static dbus_bool_t
86try_mutated_data (const DBusString *data)
87{
88  int pid;
89
90  total_attempts += 1;
91  /* printf ("  attempt %d\n", total_attempts); */
92
93  pid = fork ();
94
95  if (pid < 0)
96    {
97      fprintf (stderr, "fork() failed: %s\n",
98               strerror (errno));
99      exit (1);
100      return FALSE;
101    }
102
103  if (pid == 0)
104    {
105      /* Child, try loading the data */
106      if (!dbus_internal_do_not_use_try_message_data (data, _DBUS_MESSAGE_UNKNOWN))
107        exit (1);
108      else
109        exit (0);
110    }
111  else
112    {
113      /* Parent, wait for child */
114      int status;
115      DBusString filename;
116      dbus_bool_t failed;
117
118      if (waitpid (pid, &status, 0) < 0)
119        {
120          fprintf (stderr, "waitpid() failed: %s\n", strerror (errno));
121          exit (1);
122          return FALSE;
123        }
124
125      failed = FALSE;
126
127      if (!_dbus_string_init (&filename) ||
128          !_dbus_string_copy (&failure_dir, 0,
129                              &filename, 0) ||
130          !_dbus_string_append_byte (&filename, '/'))
131        {
132          fprintf (stderr, "out of memory\n");
133          exit (1);
134        }
135
136      _dbus_string_append_int (&filename, total_attempts);
137
138      if (WIFEXITED (status))
139        {
140          if (WEXITSTATUS (status) != 0)
141            {
142              _dbus_string_append (&filename, "-exited-");
143              _dbus_string_append_int (&filename, WEXITSTATUS (status));
144              failed = TRUE;
145            }
146        }
147      else if (WIFSIGNALED (status))
148        {
149          _dbus_string_append (&filename, "signaled-");
150          _dbus_string_append_int (&filename, WTERMSIG (status));
151          failed = TRUE;
152        }
153
154      if (failed)
155        {
156          DBusError error;
157
158          _dbus_string_append (&filename, ".message-raw");
159
160          printf ("Child failed, writing %s\n", _dbus_string_get_const_data (&filename));
161
162          dbus_error_init (&error);
163          if (!_dbus_string_save_to_file (data, &filename, &error))
164            {
165              fprintf (stderr, "Failed to save failed message data: %s\n",
166                       error.message);
167              dbus_error_free (&error);
168              exit (1); /* so we can see the seed that was printed out */
169            }
170
171          failures_this_iteration += 1;
172
173	  _dbus_string_free (&filename);
174
175          return FALSE;
176        }
177      else
178	{
179	  _dbus_string_free (&filename);
180	  return TRUE;
181	}
182    }
183
184  _dbus_assert_not_reached ("should not be reached");
185  return TRUE;
186}
187
188static void
189randomly_shorten_or_lengthen (const DBusString *orig_data,
190                              DBusString       *mutated)
191{
192  int delta;
193
194  if (orig_data != mutated)
195    {
196      _dbus_string_set_length (mutated, 0);
197
198      if (!_dbus_string_copy (orig_data, 0, mutated, 0))
199        _dbus_assert_not_reached ("out of mem");
200    }
201
202  if (_dbus_string_get_length (mutated) == 0)
203    delta = random_int_in_range (0, 10);
204  else
205    delta = random_int_in_range (- _dbus_string_get_length (mutated),
206                                 _dbus_string_get_length (mutated) * 3);
207
208  if (delta < 0)
209    _dbus_string_shorten (mutated, - delta);
210  else if (delta > 0)
211    {
212      int i = 0;
213
214      i = _dbus_string_get_length (mutated);
215      if (!_dbus_string_lengthen (mutated, delta))
216        _dbus_assert_not_reached ("couldn't lengthen string");
217
218      while (i < _dbus_string_get_length (mutated))
219        {
220          _dbus_string_set_byte (mutated,
221                                 i,
222                                 random_int_in_range (0, 256));
223          ++i;
224        }
225    }
226}
227
228static void
229randomly_change_one_byte (const DBusString *orig_data,
230                          DBusString       *mutated)
231{
232  int i;
233
234  if (orig_data != mutated)
235    {
236      _dbus_string_set_length (mutated, 0);
237
238      if (!_dbus_string_copy (orig_data, 0, mutated, 0))
239        _dbus_assert_not_reached ("out of mem");
240    }
241
242  if (_dbus_string_get_length (mutated) == 0)
243    return;
244
245  i = random_int_in_range (0, _dbus_string_get_length (mutated));
246
247  _dbus_string_set_byte (mutated, i,
248                         random_int_in_range (0, 256));
249}
250
251static void
252randomly_remove_one_byte (const DBusString *orig_data,
253                          DBusString       *mutated)
254{
255  int i;
256
257  if (orig_data != mutated)
258    {
259      _dbus_string_set_length (mutated, 0);
260
261      if (!_dbus_string_copy (orig_data, 0, mutated, 0))
262        _dbus_assert_not_reached ("out of mem");
263    }
264
265  if (_dbus_string_get_length (mutated) == 0)
266    return;
267
268  i = random_int_in_range (0, _dbus_string_get_length (mutated));
269
270  _dbus_string_delete (mutated, i, 1);
271}
272
273
274static void
275randomly_add_one_byte (const DBusString *orig_data,
276                       DBusString       *mutated)
277{
278  int i;
279
280  if (orig_data != mutated)
281    {
282      _dbus_string_set_length (mutated, 0);
283
284      if (!_dbus_string_copy (orig_data, 0, mutated, 0))
285        _dbus_assert_not_reached ("out of mem");
286    }
287
288  i = random_int_in_range (0, _dbus_string_get_length (mutated));
289
290  _dbus_string_insert_bytes (mutated, i, 1,
291			     random_int_in_range (0, 256));
292}
293
294static void
295randomly_modify_length (const DBusString *orig_data,
296                        DBusString       *mutated)
297{
298  int i;
299  int byte_order;
300  const char *d;
301  dbus_uint32_t orig;
302  int delta;
303
304  if (orig_data != mutated)
305    {
306      _dbus_string_set_length (mutated, 0);
307
308      if (!_dbus_string_copy (orig_data, 0, mutated, 0))
309        _dbus_assert_not_reached ("out of mem");
310    }
311
312  if (_dbus_string_get_length (mutated) < 12)
313    return;
314
315  d = _dbus_string_get_const_data (mutated);
316
317  if (!(*d == DBUS_LITTLE_ENDIAN ||
318        *d == DBUS_BIG_ENDIAN))
319    return;
320
321  byte_order = *d;
322
323  i = random_int_in_range (4, _dbus_string_get_length (mutated) - 8);
324  i = _DBUS_ALIGN_VALUE (i, 4);
325
326  orig = _dbus_demarshal_uint32 (mutated, byte_order, i, NULL);
327
328  delta = random_int_in_range (-10, 10);
329
330  _dbus_marshal_set_uint32 (mutated, byte_order, i,
331                            (unsigned) (orig + delta));
332}
333
334static void
335randomly_set_extreme_ints (const DBusString *orig_data,
336                           DBusString       *mutated)
337{
338  int i;
339  int byte_order;
340  const char *d;
341  dbus_uint32_t orig;
342  static int which = 0;
343  unsigned int extreme_ints[] = {
344    _DBUS_INT_MAX,
345    _DBUS_UINT_MAX,
346    _DBUS_INT_MAX - 1,
347    _DBUS_UINT_MAX - 1,
348    _DBUS_INT_MAX - 2,
349    _DBUS_UINT_MAX - 2,
350    _DBUS_INT_MAX - 17,
351    _DBUS_UINT_MAX - 17,
352    _DBUS_INT_MAX / 2,
353    _DBUS_INT_MAX / 3,
354    _DBUS_UINT_MAX / 2,
355    _DBUS_UINT_MAX / 3,
356    0, 1, 2, 3,
357    (unsigned int) -1,
358    (unsigned int) -2,
359    (unsigned int) -3
360  };
361
362  if (orig_data != mutated)
363    {
364      _dbus_string_set_length (mutated, 0);
365
366      if (!_dbus_string_copy (orig_data, 0, mutated, 0))
367        _dbus_assert_not_reached ("out of mem");
368    }
369
370  if (_dbus_string_get_length (mutated) < 12)
371    return;
372
373  d = _dbus_string_get_const_data (mutated);
374
375  if (!(*d == DBUS_LITTLE_ENDIAN ||
376        *d == DBUS_BIG_ENDIAN))
377    return;
378
379  byte_order = *d;
380
381  i = random_int_in_range (4, _dbus_string_get_length (mutated) - 8);
382  i = _DBUS_ALIGN_VALUE (i, 4);
383
384  orig = _dbus_demarshal_uint32 (mutated, byte_order, i, NULL);
385
386  which = random_int_in_range (0, _DBUS_N_ELEMENTS (extreme_ints));
387
388  _dbus_assert (which >= 0);
389  _dbus_assert (which < _DBUS_N_ELEMENTS (extreme_ints));
390
391  _dbus_marshal_set_uint32 (mutated, byte_order, i,
392                            extreme_ints[which]);
393}
394
395static int
396random_type (void)
397{
398  const char types[] = {
399    DBUS_TYPE_INVALID,
400    DBUS_TYPE_NIL,
401    DBUS_TYPE_BYTE,
402    DBUS_TYPE_BOOLEAN,
403    DBUS_TYPE_INT32,
404    DBUS_TYPE_UINT32,
405    DBUS_TYPE_INT64,
406    DBUS_TYPE_UINT64,
407    DBUS_TYPE_DOUBLE,
408    DBUS_TYPE_STRING,
409    DBUS_TYPE_CUSTOM,
410    DBUS_TYPE_ARRAY,
411    DBUS_TYPE_DICT,
412    DBUS_TYPE_OBJECT_PATH
413  };
414
415  _dbus_assert (_DBUS_N_ELEMENTS (types) == DBUS_NUMBER_OF_TYPES + 1);
416
417  return types[ random_int_in_range (0, _DBUS_N_ELEMENTS (types)) ];
418}
419
420static void
421randomly_change_one_type (const DBusString *orig_data,
422                          DBusString       *mutated)
423{
424  int i;
425  int len;
426
427  if (orig_data != mutated)
428    {
429      _dbus_string_set_length (mutated, 0);
430
431      if (!_dbus_string_copy (orig_data, 0, mutated, 0))
432        _dbus_assert_not_reached ("out of mem");
433    }
434
435  if (_dbus_string_get_length (mutated) == 0)
436    return;
437
438  len = _dbus_string_get_length (mutated);
439  i = random_int_in_range (0, len);
440
441  /* Look for a type starting at a random location,
442   * and replace with a different type
443   */
444  while (i < len)
445    {
446      int b;
447      b = _dbus_string_get_byte (mutated, i);
448      if (_dbus_type_is_valid (b))
449        {
450          _dbus_string_set_byte (mutated, i, random_type ());
451          return;
452        }
453      ++i;
454    }
455}
456
457static int times_we_did_each_thing[7] = { 0, };
458
459static void
460randomly_do_n_things (const DBusString *orig_data,
461                      DBusString       *mutated,
462                      int               n)
463{
464  int i;
465  void (* functions[]) (const DBusString *orig_data,
466                        DBusString       *mutated) =
467    {
468      randomly_shorten_or_lengthen,
469      randomly_change_one_byte,
470      randomly_add_one_byte,
471      randomly_remove_one_byte,
472      randomly_modify_length,
473      randomly_set_extreme_ints,
474      randomly_change_one_type
475    };
476
477  _dbus_string_set_length (mutated, 0);
478
479  if (!_dbus_string_copy (orig_data, 0, mutated, 0))
480    _dbus_assert_not_reached ("out of mem");
481
482  i = 0;
483  while (i < n)
484    {
485      int which;
486
487      which = random_int_in_range (0, _DBUS_N_ELEMENTS (functions));
488
489      (* functions[which]) (mutated, mutated);
490      times_we_did_each_thing[which] += 1;
491
492      ++i;
493    }
494}
495
496static dbus_bool_t
497find_breaks_based_on (const DBusString   *filename,
498                      dbus_bool_t         is_raw,
499                      DBusMessageValidity expected_validity,
500                      void               *data)
501{
502  DBusString orig_data;
503  DBusString mutated;
504  const char *filename_c;
505  dbus_bool_t retval;
506  int i;
507
508  filename_c = _dbus_string_get_const_data (filename);
509
510  retval = FALSE;
511
512  if (!_dbus_string_init (&orig_data))
513    _dbus_assert_not_reached ("could not allocate string\n");
514
515  if (!_dbus_string_init (&mutated))
516    _dbus_assert_not_reached ("could not allocate string\n");
517
518  if (!dbus_internal_do_not_use_load_message_file (filename, is_raw,
519                                                   &orig_data))
520    {
521      fprintf (stderr, "could not load file %s\n", filename_c);
522      goto failed;
523    }
524
525  printf ("        changing one random byte 100 times\n");
526  i = 0;
527  while (i < 100)
528    {
529      randomly_change_one_byte (&orig_data, &mutated);
530      try_mutated_data (&mutated);
531
532      ++i;
533    }
534
535  printf ("        changing length 50 times\n");
536  i = 0;
537  while (i < 50)
538    {
539      randomly_modify_length (&orig_data, &mutated);
540      try_mutated_data (&mutated);
541
542      ++i;
543    }
544
545  printf ("        removing one byte 50 times\n");
546  i = 0;
547  while (i < 50)
548    {
549      randomly_remove_one_byte (&orig_data, &mutated);
550      try_mutated_data (&mutated);
551
552      ++i;
553    }
554
555  printf ("        adding one byte 50 times\n");
556  i = 0;
557  while (i < 50)
558    {
559      randomly_add_one_byte (&orig_data, &mutated);
560      try_mutated_data (&mutated);
561
562      ++i;
563    }
564
565  printf ("        changing ints to boundary values 50 times\n");
566  i = 0;
567  while (i < 50)
568    {
569      randomly_set_extreme_ints (&orig_data, &mutated);
570      try_mutated_data (&mutated);
571
572      ++i;
573    }
574
575  printf ("        changing typecodes 50 times\n");
576  i = 0;
577  while (i < 50)
578    {
579      randomly_change_one_type (&orig_data, &mutated);
580      try_mutated_data (&mutated);
581
582      ++i;
583    }
584
585  printf ("        changing message length 15 times\n");
586  i = 0;
587  while (i < 15)
588    {
589      randomly_shorten_or_lengthen (&orig_data, &mutated);
590      try_mutated_data (&mutated);
591
592      ++i;
593    }
594
595  printf ("        randomly making 2 of above modifications 42 times\n");
596  i = 0;
597  while (i < 42)
598    {
599      randomly_do_n_things (&orig_data, &mutated, 2);
600      try_mutated_data (&mutated);
601
602      ++i;
603    }
604
605  printf ("        randomly making 3 of above modifications 42 times\n");
606  i = 0;
607  while (i < 42)
608    {
609      randomly_do_n_things (&orig_data, &mutated, 3);
610      try_mutated_data (&mutated);
611
612      ++i;
613    }
614
615  printf ("        randomly making 4 of above modifications 42 times\n");
616  i = 0;
617  while (i < 42)
618    {
619      randomly_do_n_things (&orig_data, &mutated, 4);
620      try_mutated_data (&mutated);
621
622      ++i;
623    }
624
625  retval = TRUE;
626
627 failed:
628
629  _dbus_string_free (&orig_data);
630  _dbus_string_free (&mutated);
631
632  /* FALSE means end the whole process */
633  return retval;
634}
635
636static unsigned int
637get_random_seed (void)
638{
639  DBusString bytes;
640  unsigned int seed;
641  int fd;
642  const char *s;
643
644  seed = 0;
645
646  if (!_dbus_string_init (&bytes))
647    exit (1);
648
649  fd = open ("/dev/urandom", O_RDONLY);
650  if (fd < 0)
651    goto use_fallback;
652
653  if (_dbus_read (fd, &bytes, 4) != 4)
654    goto use_fallback;
655
656  close (fd);
657
658  s = _dbus_string_get_const_data (&bytes);
659
660  seed = * (unsigned int*) s;
661  goto out;
662
663 use_fallback:
664  {
665    long tv_usec;
666
667    fprintf (stderr, "could not open/read /dev/urandom, using current time for seed\n");
668
669    _dbus_get_current_time (NULL, &tv_usec);
670
671    seed = tv_usec;
672  }
673
674 out:
675  _dbus_string_free (&bytes);
676
677  return seed;
678}
679
680int
681main (int    argc,
682      char **argv)
683{
684  const char *test_data_dir;
685  const char *failure_dir_c;
686  int total_failures_found;
687
688  if (argc > 1)
689    test_data_dir = argv[1];
690  else
691    {
692      fprintf (stderr, "Must specify a top_srcdir/test/data directory\n");
693      return 1;
694    }
695
696  total_failures_found = 0;
697  total_attempts = 0;
698
699  if (!_dbus_string_init (&failure_dir))
700    return 1;
701
702  /* so you can leave it overnight safely */
703#define MAX_FAILURES 1000
704
705  while (total_failures_found < MAX_FAILURES)
706    {
707      unsigned int seed;
708
709      failures_this_iteration = 0;
710
711      seed = get_random_seed ();
712
713      _dbus_string_set_length (&failure_dir, 0);
714
715      if (!_dbus_string_append (&failure_dir, "failures-"))
716        return 1;
717
718      if (!_dbus_string_append_uint (&failure_dir, seed))
719        return 1;
720
721      failure_dir_c = _dbus_string_get_const_data (&failure_dir);
722
723      if (mkdir (failure_dir_c, 0700) < 0)
724        {
725          if (errno != EEXIST)
726            fprintf (stderr, "didn't mkdir %s: %s\n",
727                     failure_dir_c, strerror (errno));
728        }
729
730      printf ("next seed = %u \ttotal failures %d of %d attempts\n",
731              seed, total_failures_found, total_attempts);
732
733      srand (seed);
734
735      if (!dbus_internal_do_not_use_foreach_message_file (test_data_dir,
736                                                          find_breaks_based_on,
737                                                          NULL))
738        {
739          fprintf (stderr, "fatal error iterating over message files\n");
740          rmdir (failure_dir_c);
741          return 1;
742        }
743
744      printf ("  did %d random mutations: %d %d %d %d %d %d %d\n",
745              _DBUS_N_ELEMENTS (times_we_did_each_thing),
746              times_we_did_each_thing[0],
747              times_we_did_each_thing[1],
748              times_we_did_each_thing[2],
749              times_we_did_each_thing[3],
750              times_we_did_each_thing[4],
751              times_we_did_each_thing[5],
752              times_we_did_each_thing[6]);
753
754      printf ("Found %d failures with seed %u stored in %s\n",
755              failures_this_iteration, seed, failure_dir_c);
756
757      total_failures_found += failures_this_iteration;
758
759      rmdir (failure_dir_c); /* does nothing if non-empty */
760    }
761
762  return 0;
763}
764