test/break-loader.c

   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.1
   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-basic.h>
  40 #undef DBUS_COMPILATION
  41
  42 static DBusString failure_dir;
  43 static int total_attempts;
  44 static int failures_this_iteration;
  45
  46 static int
  47 random_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
  85 static dbus_bool_t
  86 try_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
 188 static void
 189 randomly_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
 228 static void
 229 randomly_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
 251 static void
 252 randomly_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
 274 static void
 275 randomly_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
 294 static void
 295 randomly_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
 334 static void
 335 randomly_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
 395 static int
 396 random_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
 420 static void
 421 randomly_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
 457 static int times_we_did_each_thing[7] = { 0, };
 458
 459 static void
 460 randomly_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
 496 static dbus_bool_t
 497 find_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
 636 static unsigned int
 637 get_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
 680 int
 681 main (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 }