1 /* 2 * Copyright 2016, The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include <cmath> 18 #include <random> 19 20 #include <inttypes.h> 21 #include <stdio.h> 22 #include <stdlib.h> 23 #include <string.h> 24 #include <unistd.h> 25 26 #include <sys/time.h> 27 28 namespace { 29 30 /* 31 * Operators. 32 */ 33 34 static constexpr const char* kIncDecOps[] = { "++", "--" }; 35 static constexpr const char* kIntUnaryOps[] = { "+", "-", "~" }; 36 static constexpr const char* kFpUnaryOps[] = { "+", "-" }; 37 38 static constexpr const char* kBoolBinOps[] = { "&&", "||", "&", "|", "^" }; // few less common 39 static constexpr const char* kIntBinOps[] = { "+", "-", "*", "/", "%", 40 ">>", ">>>", "<<", "&", "|", "^" }; 41 static constexpr const char* kFpBinOps[] = { "+", "-", "*", "/" }; 42 43 static constexpr const char* kBoolAssignOps[] = { "=", "&=" , "|=", "^=" }; // few less common 44 static constexpr const char* kIntAssignOps[] = { "=", "+=", "-=", "*=", "/=", "%=", 45 ">>=", ">>>=", "<<=", "&=", "|=", "^=" }; 46 static constexpr const char* kFpAssignOps[] = { "=", "+=", "-=", "*=", "/=" }; 47 48 static constexpr const char* kBoolRelOps[] = { "==", "!=" }; 49 static constexpr const char* kRelOps[] = { "==", "!=", ">", ">=", "<", "<=" }; 50 51 /* 52 * Exceptions. 53 */ 54 static const char* kExceptionTypes[] = { 55 "IllegalStateException", 56 "NullPointerException", 57 "IllegalArgumentException", 58 "ArrayIndexOutOfBoundsException" 59 }; 60 61 /* 62 * Version of JFuzz. Increase this each time changes are made to the program 63 * to preserve the property that a given version of JFuzz yields the same 64 * fuzzed program for a deterministic random seed. 65 */ 66 const char* VERSION = "1.5"; 67 68 /* 69 * Maximum number of array dimensions, together with corresponding maximum size 70 * within each dimension (to keep memory/runtime requirements roughly the same). 71 */ 72 static const uint32_t kMaxDim = 10; 73 static const uint32_t kMaxDimSize[kMaxDim + 1] = { 0, 1000, 32, 10, 6, 4, 3, 3, 2, 2, 2 }; 74 75 /* 76 * Utility function to return the number of elements in an array. 77 */ 78 template <typename T, uint32_t N> 79 constexpr uint32_t countof(T const (&)[N]) { 80 return N; 81 } 82 83 /** 84 * A class that generates a random program that compiles correctly. The program 85 * is generated using rules that generate various programming constructs. Each rule 86 * has a fixed probability to "fire". Running a generated program yields deterministic 87 * output, making it suited to test various modes of execution (e.g an interpreter vs. 88 * an compiler or two different run times) for divergences. 89 */ 90 class JFuzz { 91 public: 92 JFuzz(FILE* out, 93 uint32_t seed, 94 uint32_t expr_depth, 95 uint32_t stmt_length, 96 uint32_t if_nest, 97 uint32_t loop_nest, 98 uint32_t try_nest) 99 : out_(out), 100 fuzz_random_engine_(seed), 101 fuzz_seed_(seed), 102 fuzz_expr_depth_(expr_depth), 103 fuzz_stmt_length_(stmt_length), 104 fuzz_if_nest_(if_nest), 105 fuzz_loop_nest_(loop_nest), 106 fuzz_try_nest_(try_nest), 107 return_type_(randomType()), 108 array_type_(randomType()), 109 array_dim_(random1(kMaxDim)), 110 array_size_(random1(kMaxDimSize[array_dim_])), 111 indentation_(0), 112 expr_depth_(0), 113 stmt_length_(0), 114 if_nest_(0), 115 loop_nest_(0), 116 switch_nest_(0), 117 do_nest_(0), 118 try_nest_(0), 119 boolean_local_(0), 120 int_local_(0), 121 long_local_(0), 122 float_local_(0), 123 double_local_(0), 124 in_inner_(false) { } 125 126 ~JFuzz() { } 127 128 void emitProgram() { 129 emitHeader(); 130 emitTestClassWithMain(); 131 } 132 133 private: 134 // 135 // Types. 136 // 137 138 // Current type of each expression during generation. 139 enum Type { 140 kBoolean, 141 kInt, 142 kLong, 143 kFloat, 144 kDouble 145 }; 146 147 // Test for an integral type. 148 static bool isInteger(Type tp) { 149 return tp == kInt || tp == kLong; 150 } 151 152 // Test for a floating-point type. 153 static bool isFP(Type tp) { 154 return tp == kFloat || tp == kDouble; 155 } 156 157 // Emit type. 158 void emitType(Type tp) const { 159 switch (tp) { 160 case kBoolean: fputs("boolean", out_); break; 161 case kInt: fputs("int", out_); break; 162 case kLong: fputs("long", out_); break; 163 case kFloat: fputs("float", out_); break; 164 case kDouble: fputs("double", out_); break; 165 } 166 } 167 168 // Emit type class. 169 void emitTypeClass(Type tp) const { 170 switch (tp) { 171 case kBoolean: fputs("Boolean", out_); break; 172 case kInt: fputs("Integer", out_); break; 173 case kLong: fputs("Long", out_); break; 174 case kFloat: fputs("Float", out_); break; 175 case kDouble: fputs("Double", out_); break; 176 } 177 } 178 179 // Return a random type. 180 Type randomType() { 181 switch (random1(5)) { 182 case 1: return kBoolean; 183 case 2: return kInt; 184 case 3: return kLong; 185 case 4: return kFloat; 186 default: return kDouble; 187 } 188 } 189 190 // Emits a random strong selected from an array of operator strings. 191 template <std::uint32_t N> 192 inline void emitOneOf(const char* const (&ops)[N]) { 193 fputs(ops[random0(N)], out_); 194 } 195 196 // 197 // Expressions. 198 // 199 200 // Emit an unary operator (same type in-out). 201 void emitUnaryOp(Type tp) { 202 if (tp == kBoolean) { 203 fputc('!', out_); 204 } else if (isInteger(tp)) { 205 emitOneOf(kIntUnaryOps); 206 } else { // isFP(tp) 207 emitOneOf(kFpUnaryOps); 208 } 209 } 210 211 // Emit a pre/post-increment/decrement operator (same type in-out). 212 void emitIncDecOp(Type tp) { 213 if (tp == kBoolean) { 214 // Not applicable, just leave "as is". 215 } else { // isInteger(tp) || isFP(tp) 216 emitOneOf(kIncDecOps); 217 } 218 } 219 220 // Emit a binary operator (same type in-out). 221 void emitBinaryOp(Type tp) { 222 if (tp == kBoolean) { 223 emitOneOf(kBoolBinOps); 224 } else if (isInteger(tp)) { 225 emitOneOf(kIntBinOps); 226 } else { // isFP(tp) 227 emitOneOf(kFpBinOps); 228 } 229 } 230 231 // Emit an assignment operator (same type in-out). 232 void emitAssignmentOp(Type tp) { 233 if (tp == kBoolean) { 234 emitOneOf(kBoolAssignOps); 235 } else if (isInteger(tp)) { 236 emitOneOf(kIntAssignOps); 237 } else { // isFP(tp) 238 emitOneOf(kFpAssignOps); 239 } 240 } 241 242 // Emit a relational operator (one type in, boolean out). 243 void emitRelationalOp(Type tp) { 244 if (tp == kBoolean) { 245 emitOneOf(kBoolRelOps); 246 } else { // isInteger(tp) || isFP(tp) 247 emitOneOf(kRelOps); 248 } 249 } 250 251 // Emit a type conversion operator sequence (out type given, new suitable in type picked). 252 Type emitTypeConversionOp(Type tp) { 253 if (tp == kInt) { 254 switch (random1(5)) { 255 case 1: fputs("(int)", out_); return kLong; 256 case 2: fputs("(int)", out_); return kFloat; 257 case 3: fputs("(int)", out_); return kDouble; 258 // Narrowing-widening. 259 case 4: fputs("(int)(byte)(int)", out_); return kInt; 260 case 5: fputs("(int)(short)(int)", out_); return kInt; 261 } 262 } else if (tp == kLong) { 263 switch (random1(6)) { 264 case 1: /* implicit */ return kInt; 265 case 2: fputs("(long)", out_); return kFloat; 266 case 3: fputs("(long)", out_); return kDouble; 267 // Narrowing-widening. 268 case 4: fputs("(long)(byte)(long)", out_); return kLong; 269 case 5: fputs("(long)(short)(long)", out_); return kLong; 270 case 6: fputs("(long)(int)(long)", out_); return kLong; 271 } 272 } else if (tp == kFloat) { 273 switch (random1(4)) { 274 case 1: fputs("(float)", out_); return kInt; 275 case 2: fputs("(float)", out_); return kLong; 276 case 3: fputs("(float)", out_); return kDouble; 277 // Narrowing-widening. 278 case 4: fputs("(float)(int)(float)", out_); return kFloat; 279 } 280 } else if (tp == kDouble) { 281 switch (random1(5)) { 282 case 1: fputs("(double)", out_); return kInt; 283 case 2: fputs("(double)", out_); return kLong; 284 case 3: fputs("(double)", out_); return kFloat; 285 // Narrowing-widening. 286 case 4: fputs("(double)(int)(double)", out_); return kDouble; 287 case 5: fputs("(double)(float)(double)", out_); return kDouble; 288 } 289 } 290 return tp; // nothing suitable, just keep type 291 } 292 293 // Emit a type conversion (out type given, new suitable in type picked). 294 void emitTypeConversion(Type tp) { 295 if (tp == kBoolean) { 296 Type tp = randomType(); 297 emitExpression(tp); 298 fputc(' ', out_); 299 emitRelationalOp(tp); 300 fputc(' ', out_); 301 emitExpression(tp); 302 } else { 303 tp = emitTypeConversionOp(tp); 304 fputc(' ', out_); 305 emitExpression(tp); 306 } 307 } 308 309 // Emit an unary intrinsic (out type given, new suitable in type picked). 310 Type emitIntrinsic1(Type tp) { 311 if (tp == kBoolean) { 312 switch (random1(6)) { 313 case 1: fputs("Float.isNaN", out_); return kFloat; 314 case 2: fputs("Float.isFinite", out_); return kFloat; 315 case 3: fputs("Float.isInfinite", out_); return kFloat; 316 case 4: fputs("Double.isNaN", out_); return kDouble; 317 case 5: fputs("Double.isFinite", out_); return kDouble; 318 case 6: fputs("Double.isInfinite", out_); return kDouble; 319 } 320 } else if (isInteger(tp)) { 321 const char* prefix = tp == kLong ? "Long" : "Integer"; 322 switch (random1(13)) { 323 case 1: fprintf(out_, "%s.highestOneBit", prefix); break; 324 case 2: fprintf(out_, "%s.lowestOneBit", prefix); break; 325 case 3: fprintf(out_, "%s.numberOfLeadingZeros", prefix); break; 326 case 4: fprintf(out_, "%s.numberOfTrailingZeros", prefix); break; 327 case 5: fprintf(out_, "%s.bitCount", prefix); break; 328 case 6: fprintf(out_, "%s.signum", prefix); break; 329 case 7: fprintf(out_, "%s.reverse", prefix); break; 330 case 8: fprintf(out_, "%s.reverseBytes", prefix); break; 331 case 9: fputs("Math.incrementExact", out_); break; 332 case 10: fputs("Math.decrementExact", out_); break; 333 case 11: fputs("Math.negateExact", out_); break; 334 case 12: fputs("Math.abs", out_); break; 335 case 13: fputs("Math.round", out_); 336 return tp == kLong ? kDouble : kFloat; 337 } 338 } else { // isFP(tp) 339 switch (random1(6)) { 340 case 1: fputs("Math.abs", out_); break; 341 case 2: fputs("Math.ulp", out_); break; 342 case 3: fputs("Math.signum", out_); break; 343 case 4: fputs("Math.nextUp", out_); break; 344 case 5: fputs("Math.nextDown", out_); break; 345 case 6: if (tp == kDouble) { 346 fputs("Double.longBitsToDouble", out_); 347 return kLong; 348 } else { 349 fputs("Float.intBitsToFloat", out_); 350 return kInt; 351 } 352 } 353 } 354 return tp; // same type in-out 355 } 356 357 // Emit a binary intrinsic (out type given, new suitable in type picked). 358 Type emitIntrinsic2(Type tp) { 359 if (tp == kBoolean) { 360 switch (random1(3)) { 361 case 1: fputs("Boolean.logicalAnd", out_); break; 362 case 2: fputs("Boolean.logicalOr", out_); break; 363 case 3: fputs("Boolean.logicalXor", out_); break; 364 } 365 } else if (isInteger(tp)) { 366 const char* prefix = tp == kLong ? "Long" : "Integer"; 367 switch (random1(11)) { 368 case 1: fprintf(out_, "%s.compare", prefix); break; 369 case 2: fprintf(out_, "%s.sum", prefix); break; 370 case 3: fprintf(out_, "%s.min", prefix); break; 371 case 4: fprintf(out_, "%s.max", prefix); break; 372 case 5: fputs("Math.min", out_); break; 373 case 6: fputs("Math.max", out_); break; 374 case 7: fputs("Math.floorDiv", out_); break; 375 case 8: fputs("Math.floorMod", out_); break; 376 case 9: fputs("Math.addExact", out_); break; 377 case 10: fputs("Math.subtractExact", out_); break; 378 case 11: fputs("Math.multiplyExact", out_); break; 379 } 380 } else { // isFP(tp) 381 const char* prefix = tp == kDouble ? "Double" : "Float"; 382 switch (random1(5)) { 383 case 1: fprintf(out_, "%s.sum", prefix); break; 384 case 2: fprintf(out_, "%s.min", prefix); break; 385 case 3: fprintf(out_, "%s.max", prefix); break; 386 case 4: fputs("Math.min", out_); break; 387 case 5: fputs("Math.max", out_); break; 388 } 389 } 390 return tp; // same type in-out 391 } 392 393 // Emit an intrinsic (out type given, new suitable in type picked). 394 void emitIntrinsic(Type tp) { 395 if (random1(2) == 1) { 396 tp = emitIntrinsic1(tp); 397 fputc('(', out_); 398 emitExpression(tp); 399 fputc(')', out_); 400 } else { 401 tp = emitIntrinsic2(tp); 402 fputc('(', out_); 403 emitExpression(tp); 404 fputs(", ", out_); 405 emitExpression(tp); 406 fputc(')', out_); 407 } 408 } 409 410 // Emit a method call (out type given). 411 void emitMethodCall(Type tp) { 412 if (tp != kBoolean && !in_inner_) { 413 // Accept all numerical types (implicit conversion) and when not 414 // declaring inner classes (to avoid infinite recursion). 415 switch (random1(8)) { 416 case 1: fputs("mA.a()", out_); break; 417 case 2: fputs("mB.a()", out_); break; 418 case 3: fputs("mB.x()", out_); break; 419 case 4: fputs("mBX.x()", out_); break; 420 case 5: fputs("mC.s()", out_); break; 421 case 6: fputs("mC.c()", out_); break; 422 case 7: fputs("mC.x()", out_); break; 423 case 8: fputs("mCX.x()", out_); break; 424 } 425 } else { 426 // Fall back to intrinsic. 427 emitIntrinsic(tp); 428 } 429 } 430 431 // Emit unboxing boxed object. 432 void emitUnbox(Type tp) { 433 fputc('(', out_); 434 emitType(tp); 435 fputs(") new ", out_); 436 emitTypeClass(tp); 437 fputc('(', out_); 438 emitExpression(tp); 439 fputc(')', out_); 440 } 441 442 // Emit miscellaneous constructs. 443 void emitMisc(Type tp) { 444 if (tp == kBoolean) { 445 fprintf(out_, "this instanceof %s", in_inner_ ? "X" : "Test"); 446 } else if (isInteger(tp)) { 447 const char* prefix = tp == kLong ? "Long" : "Integer"; 448 switch (random1(2)) { 449 case 1: fprintf(out_, "%s.MIN_VALUE", prefix); break; 450 case 2: fprintf(out_, "%s.MAX_VALUE", prefix); break; 451 } 452 } else { // isFP(tp) 453 const char* prefix = tp == kDouble ? "Double" : "Float"; 454 switch (random1(6)) { 455 case 1: fprintf(out_, "%s.MIN_NORMAL", prefix); break; 456 case 2: fprintf(out_, "%s.MIN_VALUE", prefix); break; 457 case 3: fprintf(out_, "%s.MAX_VALUE", prefix); break; 458 case 4: fprintf(out_, "%s.POSITIVE_INFINITY", prefix); break; 459 case 5: fprintf(out_, "%s.NEGATIVE_INFINITY", prefix); break; 460 case 6: fprintf(out_, "%s.NaN", prefix); break; 461 } 462 } 463 } 464 465 // Adjust local of given type and return adjusted value. 466 uint32_t adjustLocal(Type tp, int32_t a) { 467 switch (tp) { 468 case kBoolean: boolean_local_ += a; return boolean_local_; 469 case kInt: int_local_ += a; return int_local_; 470 case kLong: long_local_ += a; return long_local_; 471 case kFloat: float_local_ += a; return float_local_; 472 default: double_local_ += a; return double_local_; 473 } 474 } 475 476 // Emit an expression that is a strict upper bound for an array index. 477 void emitUpperBound() { 478 if (random1(8) == 1) { 479 fputs("mArray.length", out_); 480 } else if (random1(8) == 1) { 481 fprintf(out_, "%u", random1(array_size_)); // random in range 482 } else { 483 fprintf(out_, "%u", array_size_); 484 } 485 } 486 487 // Emit an array index, usually within proper range. 488 void emitArrayIndex() { 489 if (loop_nest_ > 0 && random1(2) == 1) { 490 fprintf(out_, "i%u", random0(loop_nest_)); 491 } else if (random1(8) == 1) { 492 fputs("mArray.length - 1", out_); 493 } else { 494 fprintf(out_, "%u", random0(array_size_)); // random in range 495 } 496 // Introduce potential off by one errors with low probability. 497 if (random1(100) == 1) { 498 if (random1(2) == 1) { 499 fputs(" - 1", out_); 500 } else { 501 fputs(" + 1", out_); 502 } 503 } 504 } 505 506 // Emit a literal. 507 void emitLiteral(Type tp) { 508 switch (tp) { 509 case kBoolean: fputs(random1(2) == 1 ? "true" : "false", out_); break; 510 case kInt: fprintf(out_, "%d", random()); break; 511 case kLong: fprintf(out_, "%dL", random()); break; 512 case kFloat: fprintf(out_, "%d.0f", random()); break; 513 case kDouble: fprintf(out_, "%d.0", random()); break; 514 } 515 } 516 517 // Emit array variable, if available. 518 bool emitArrayVariable(Type tp) { 519 if (tp == array_type_) { 520 fputs("mArray", out_); 521 for (uint32_t i = 0; i < array_dim_; i++) { 522 fputc('[', out_); 523 emitArrayIndex(); 524 fputc(']', out_); 525 } 526 return true; 527 } 528 return false; 529 } 530 531 // Emit a local variable, if available. 532 bool emitLocalVariable(Type tp) { 533 uint32_t locals = adjustLocal(tp, 0); 534 if (locals > 0) { 535 uint32_t local = random0(locals); 536 switch (tp) { 537 case kBoolean: fprintf(out_, "lZ%u", local); break; 538 case kInt: fprintf(out_, "lI%u", local); break; 539 case kLong: fprintf(out_, "lJ%u", local); break; 540 case kFloat: fprintf(out_, "lF%u", local); break; 541 case kDouble: fprintf(out_, "lD%u", local); break; 542 } 543 return true; 544 } 545 return false; 546 } 547 548 // Emit a field variable. 549 void emitFieldVariable(Type tp) { 550 switch (tp) { 551 case kBoolean:fputs("mZ", out_); break; 552 case kInt: fputs("mI", out_); break; 553 case kLong: fputs("mJ", out_); break; 554 case kFloat: fputs("mF", out_); break; 555 case kDouble: fputs("mD", out_); break; 556 } 557 } 558 559 // Emit a variable. 560 void emitVariable(Type tp) { 561 switch (random1(4)) { 562 case 1: 563 if (emitArrayVariable(tp)) 564 return; 565 // FALL-THROUGH 566 case 2: 567 if (emitLocalVariable(tp)) 568 return; 569 // FALL-THROUGH 570 default: 571 emitFieldVariable(tp); 572 break; 573 } 574 } 575 576 // Emit an expression. 577 void emitExpression(Type tp) { 578 // Continuing expression becomes less likely as the depth grows. 579 if (random1(expr_depth_ + 1) > fuzz_expr_depth_) { 580 if (random1(2) == 1) { 581 emitLiteral(tp); 582 } else { 583 emitVariable(tp); 584 } 585 return; 586 } 587 588 expr_depth_++; 589 590 fputc('(', out_); 591 switch (random1(12)) { // favor binary operations 592 case 1: 593 // Unary operator: ~ x 594 emitUnaryOp(tp); 595 fputc(' ', out_); 596 emitExpression(tp); 597 break; 598 case 2: 599 // Pre-increment: ++x 600 emitIncDecOp(tp); 601 emitVariable(tp); 602 break; 603 case 3: 604 // Post-increment: x++ 605 emitVariable(tp); 606 emitIncDecOp(tp); 607 break; 608 case 4: 609 // Ternary operator: b ? x : y 610 emitExpression(kBoolean); 611 fputs(" ? ", out_); 612 emitExpression(tp); 613 fputs(" : ", out_); 614 emitExpression(tp); 615 break; 616 case 5: 617 // Type conversion: (float) x 618 emitTypeConversion(tp); 619 break; 620 case 6: 621 // Intrinsic: foo(x) 622 emitIntrinsic(tp); 623 break; 624 case 7: 625 // Method call: mA.a() 626 emitMethodCall(tp); 627 break; 628 case 8: 629 // Emit unboxing boxed value: (int) Integer(x) 630 emitUnbox(tp); 631 break; 632 case 9: 633 // Miscellaneous constructs: a.length 634 emitMisc(tp); 635 break; 636 default: 637 // Binary operator: x + y 638 emitExpression(tp); 639 fputc(' ', out_); 640 emitBinaryOp(tp); 641 fputc(' ', out_); 642 emitExpression(tp); 643 break; 644 } 645 fputc(')', out_); 646 647 --expr_depth_; 648 } 649 650 // 651 // Statements. 652 // 653 654 // Emit current indentation. 655 void emitIndentation() const { 656 for (uint32_t i = 0; i < indentation_; i++) { 657 fputc(' ', out_); 658 } 659 } 660 661 // Emit a return statement. 662 bool emitReturn(bool mustEmit) { 663 // Only emit when we must, or with low probability inside ifs/loops, 664 // but outside do-while to avoid confusing the may follow status. 665 if (mustEmit || ((if_nest_ + loop_nest_) > 0 && do_nest_ == 0 && random1(10) == 1)) { 666 fputs("return ", out_); 667 emitExpression(return_type_); 668 fputs(";\n", out_); 669 return false; 670 } 671 // Fall back to assignment. 672 return emitAssignment(); 673 } 674 675 // Emit a continue statement. 676 bool emitContinue() { 677 // Only emit with low probability inside loops. 678 if (loop_nest_ > 0 && random1(10) == 1) { 679 fputs("continue;\n", out_); 680 return false; 681 } 682 // Fall back to assignment. 683 return emitAssignment(); 684 } 685 686 // Emit a break statement. 687 bool emitBreak() { 688 // Only emit with low probability inside loops, but outside switches 689 // to avoid confusing the may follow status. 690 if (loop_nest_ > 0 && switch_nest_ == 0 && random1(10) == 1) { 691 fputs("break;\n", out_); 692 return false; 693 } 694 // Fall back to assignment. 695 return emitAssignment(); 696 } 697 698 // Emit a new scope with a local variable declaration statement. 699 bool emitScope() { 700 Type tp = randomType(); 701 fputs("{\n", out_); 702 indentation_ += 2; 703 emitIndentation(); 704 emitType(tp); 705 switch (tp) { 706 case kBoolean: fprintf(out_, " lZ%u = ", boolean_local_); break; 707 case kInt: fprintf(out_, " lI%u = ", int_local_); break; 708 case kLong: fprintf(out_, " lJ%u = ", long_local_); break; 709 case kFloat: fprintf(out_, " lF%u = ", float_local_); break; 710 case kDouble: fprintf(out_, " lD%u = ", double_local_); break; 711 } 712 emitExpression(tp); 713 fputs(";\n", out_); 714 715 adjustLocal(tp, 1); // local now visible 716 717 bool mayFollow = emitStatementList(); 718 719 adjustLocal(tp, -1); // local no longer visible 720 721 indentation_ -= 2; 722 emitIndentation(); 723 fputs("}\n", out_); 724 return mayFollow; 725 } 726 727 // Emit one dimension of an array initializer, where parameter dim >= 1 728 // denotes the number of remaining dimensions that should be emitted. 729 void emitArrayInitDim(int dim) { 730 if (dim == 1) { 731 // Last dimension: set of values. 732 fputs("{ ", out_); 733 for (uint32_t i = 0; i < array_size_; i++) { 734 emitExpression(array_type_); 735 fputs(", ", out_); 736 } 737 fputs("}", out_); 738 739 } else { 740 // Outer dimensions: set of sets. 741 fputs("{\n", out_); 742 indentation_ += 2; 743 emitIndentation(); 744 745 for (uint32_t i = 0; i < array_size_; i++) { 746 emitArrayInitDim(dim - 1); 747 if (i != array_size_ - 1) { 748 fputs(",\n", out_); 749 emitIndentation(); 750 } 751 } 752 753 fputs(",\n", out_); 754 indentation_ -= 2; 755 emitIndentation(); 756 fputs("}", out_); 757 } 758 } 759 760 // Emit an array initializer of the following form. 761 // { 762 // type[]..[] tmp = { .. }; 763 // mArray = tmp; 764 // } 765 bool emitArrayInit() { 766 // Avoid elaborate array initializers. 767 uint64_t p = pow(array_size_, array_dim_); 768 if (p > 20) { 769 return emitAssignment(); // fall back 770 } 771 772 fputs("{\n", out_); 773 774 indentation_ += 2; 775 emitIndentation(); 776 emitType(array_type_); 777 for (uint32_t i = 0; i < array_dim_; i++) { 778 fputs("[]", out_); 779 } 780 fputs(" tmp = ", out_); 781 emitArrayInitDim(array_dim_); 782 fputs(";\n", out_); 783 784 emitIndentation(); 785 fputs("mArray = tmp;\n", out_); 786 787 indentation_ -= 2; 788 emitIndentation(); 789 fputs("}\n", out_); 790 return true; 791 } 792 793 // Emit a for loop. 794 bool emitForLoop() { 795 // Continuing loop nest becomes less likely as the depth grows. 796 if (random1(loop_nest_ + 1) > fuzz_loop_nest_) { 797 return emitAssignment(); // fall back 798 } 799 800 bool goesUp = random1(2) == 1; 801 fprintf(out_, "for (int i%u = ", loop_nest_); 802 if (goesUp) { 803 fprintf(out_, "0; i%u < ", loop_nest_); 804 emitUpperBound(); 805 fprintf(out_, "; i%u++) {\n", loop_nest_); 806 } else { 807 emitUpperBound(); 808 fprintf(out_, " - 1; i%d >= 0", loop_nest_); 809 fprintf(out_, "; i%d--) {\n", loop_nest_); 810 } 811 812 ++loop_nest_; // now in loop 813 814 indentation_ += 2; 815 emitStatementList(); 816 817 --loop_nest_; // no longer in loop 818 819 indentation_ -= 2; 820 emitIndentation(); 821 fprintf(out_, "}\n"); 822 return true; // loop-body does not block flow 823 } 824 825 // Emit while or do-while loop. 826 bool emitDoLoop() { 827 // Continuing loop nest becomes less likely as the depth grows. 828 if (random1(loop_nest_ + 1) > fuzz_loop_nest_) { 829 return emitAssignment(); // fall back 830 } 831 832 bool isWhile = random1(2) == 1; 833 fputs("{\n", out_); 834 indentation_ += 2; 835 emitIndentation(); 836 fprintf(out_, "int i%u = %d;\n", loop_nest_, isWhile ? -1 : 0); 837 emitIndentation(); 838 if (isWhile) { 839 fprintf(out_, "while (++i%u < ", loop_nest_); 840 emitUpperBound(); 841 fputs(") {\n", out_); 842 } else { 843 fputs("do {\n", out_); 844 do_nest_++; 845 } 846 847 ++loop_nest_; // now in loop 848 849 indentation_ += 2; 850 emitStatementList(); 851 852 --loop_nest_; // no longer in loop 853 854 indentation_ -= 2; 855 emitIndentation(); 856 if (isWhile) { 857 fputs("}\n", out_); 858 } else { 859 fprintf(out_, "} while (++i%u < ", loop_nest_); 860 emitUpperBound(); 861 fputs(");\n", out_); 862 --do_nest_; 863 } 864 indentation_ -= 2; 865 emitIndentation(); 866 fputs("}\n", out_); 867 return true; // loop-body does not block flow 868 } 869 870 // Emit an if statement. 871 bool emitIfStmt() { 872 // Continuing if nest becomes less likely as the depth grows. 873 if (random1(if_nest_ + 1) > fuzz_if_nest_) { 874 return emitAssignment(); // fall back 875 } 876 877 fputs("if (", out_); 878 emitExpression(kBoolean); 879 fputs(") {\n", out_); 880 881 ++if_nest_; // now in if 882 883 indentation_ += 2; 884 bool mayFollowTrue = emitStatementList(); 885 indentation_ -= 2; 886 emitIndentation(); 887 fprintf(out_, "} else {\n"); 888 indentation_ += 2; 889 bool mayFollowFalse = emitStatementList(); 890 891 --if_nest_; // no longer in if 892 893 indentation_ -= 2; 894 emitIndentation(); 895 fprintf(out_, "}\n"); 896 return mayFollowTrue || mayFollowFalse; 897 } 898 899 bool emitTry() { 900 fputs("try {\n", out_); 901 indentation_ += 2; 902 bool mayFollow = emitStatementList(); 903 indentation_ -= 2; 904 emitIndentation(); 905 fputc('}', out_); 906 return mayFollow; 907 } 908 909 bool emitCatch() { 910 uint32_t count = random1(countof(kExceptionTypes)); 911 bool mayFollow = false; 912 for (uint32_t i = 0; i < count; ++i) { 913 fprintf(out_, " catch (%s ex%u_%u) {\n", kExceptionTypes[i], try_nest_, i); 914 indentation_ += 2; 915 mayFollow |= emitStatementList(); 916 indentation_ -= 2; 917 emitIndentation(); 918 fputc('}', out_); 919 } 920 return mayFollow; 921 } 922 923 bool emitFinally() { 924 fputs(" finally {\n", out_); 925 indentation_ += 2; 926 bool mayFollow = emitStatementList(); 927 indentation_ -= 2; 928 emitIndentation(); 929 fputc('}', out_); 930 return mayFollow; 931 } 932 933 // Emit a try-catch-finally block. 934 bool emitTryCatchFinally() { 935 // Apply a hard limit on the number of catch blocks. This is for 936 // javac which fails if blocks within try-catch-finally are too 937 // large (much less than you'd expect). 938 if (try_nest_ > fuzz_try_nest_) { 939 return emitAssignment(); // fall back 940 } 941 942 ++try_nest_; // Entering try-catch-finally 943 944 bool mayFollow = emitTry(); 945 switch (random0(3)) { 946 case 0: // try..catch 947 mayFollow |= emitCatch(); 948 break; 949 case 1: // try..finally 950 mayFollow &= emitFinally(); 951 break; 952 case 2: // try..catch..finally 953 // When determining whether code may follow, we observe that a 954 // finally block always follows after try and catch 955 // block. Code may only follow if the finally block permits 956 // and either the try or catch block allows code to follow. 957 mayFollow = (mayFollow | emitCatch()) & emitFinally(); 958 break; 959 } 960 fputc('\n', out_); 961 962 --try_nest_; // Leaving try-catch-finally 963 return mayFollow; 964 } 965 966 // Emit a switch statement. 967 bool emitSwitch() { 968 // Continuing if nest becomes less likely as the depth grows. 969 if (random1(if_nest_ + 1) > fuzz_if_nest_) { 970 return emitAssignment(); // fall back 971 } 972 973 bool mayFollow = false; 974 fputs("switch (", out_); 975 emitArrayIndex(); // restrict its range 976 fputs(") {\n", out_); 977 978 ++if_nest_; 979 ++switch_nest_; // now in switch 980 981 indentation_ += 2; 982 for (uint32_t i = 0; i < 2; i++) { 983 emitIndentation(); 984 if (i == 0) { 985 fprintf(out_, "case %u: {\n", random0(array_size_)); 986 } else { 987 fprintf(out_, "default: {\n"); 988 } 989 indentation_ += 2; 990 if (emitStatementList()) { 991 // Must end with break. 992 emitIndentation(); 993 fputs("break;\n", out_); 994 mayFollow = true; 995 } 996 indentation_ -= 2; 997 emitIndentation(); 998 fputs("}\n", out_); 999 } 1000 1001 --if_nest_; 1002 --switch_nest_; // no longer in switch 1003 1004 indentation_ -= 2; 1005 emitIndentation(); 1006 fprintf(out_, "}\n"); 1007 return mayFollow; 1008 } 1009 1010 bool emitNopCall() { 1011 fputs("nop();\n", out_); 1012 return true; 1013 } 1014 1015 // Emit an assignment statement. 1016 bool emitAssignment() { 1017 Type tp = randomType(); 1018 emitVariable(tp); 1019 fputc(' ', out_); 1020 emitAssignmentOp(tp); 1021 fputc(' ', out_); 1022 emitExpression(tp); 1023 fputs(";\n", out_); 1024 return true; 1025 } 1026 1027 // Emit a single statement. Returns true if statements may follow. 1028 bool emitStatement() { 1029 switch (random1(16)) { // favor assignments 1030 case 1: return emitReturn(false); break; 1031 case 2: return emitContinue(); break; 1032 case 3: return emitBreak(); break; 1033 case 4: return emitScope(); break; 1034 case 5: return emitArrayInit(); break; 1035 case 6: return emitForLoop(); break; 1036 case 7: return emitDoLoop(); break; 1037 case 8: return emitIfStmt(); break; 1038 case 9: return emitSwitch(); break; 1039 case 10: return emitTryCatchFinally(); break; 1040 case 11: return emitNopCall(); break; 1041 default: return emitAssignment(); break; 1042 } 1043 } 1044 1045 // Emit a statement list. Returns true if statements may follow. 1046 bool emitStatementList() { 1047 while (stmt_length_ < 1000) { // avoid run-away 1048 stmt_length_++; 1049 emitIndentation(); 1050 if (!emitStatement()) { 1051 return false; // rest would be dead code 1052 } 1053 // Continuing this list becomes less likely as the total statement list grows. 1054 if (random1(stmt_length_) > fuzz_stmt_length_) { 1055 break; 1056 } 1057 } 1058 return true; 1059 } 1060 1061 // Emit interface and class declarations. 1062 void emitClassDecls() { 1063 in_inner_ = true; 1064 fputs(" private interface X {\n", out_); 1065 fputs(" int x();\n", out_); 1066 fputs(" }\n\n", out_); 1067 fputs(" private class A {\n", out_); 1068 fputs(" public int a() {\n", out_); 1069 fputs(" return ", out_); 1070 emitExpression(kInt); 1071 fputs(";\n }\n", out_); 1072 fputs(" }\n\n", out_); 1073 fputs(" private class B extends A implements X {\n", out_); 1074 fputs(" public int a() {\n", out_); 1075 fputs(" return super.a() + ", out_); 1076 emitExpression(kInt); 1077 fputs(";\n }\n", out_); 1078 fputs(" public int x() {\n", out_); 1079 fputs(" return ", out_); 1080 emitExpression(kInt); 1081 fputs(";\n }\n", out_); 1082 fputs(" }\n\n", out_); 1083 fputs(" private static class C implements X {\n", out_); 1084 fputs(" public static int s() {\n", out_); 1085 fputs(" return ", out_); 1086 emitLiteral(kInt); 1087 fputs(";\n }\n", out_); 1088 fputs(" public int c() {\n", out_); 1089 fputs(" return ", out_); 1090 emitLiteral(kInt); 1091 fputs(";\n }\n", out_); 1092 fputs(" public int x() {\n", out_); 1093 fputs(" return ", out_); 1094 emitLiteral(kInt); 1095 fputs(";\n }\n", out_); 1096 fputs(" }\n\n", out_); 1097 in_inner_ = false; 1098 } 1099 1100 // Emit field declarations. 1101 void emitFieldDecls() { 1102 fputs(" private A mA = new B();\n", out_); 1103 fputs(" private B mB = new B();\n", out_); 1104 fputs(" private X mBX = new B();\n", out_); 1105 fputs(" private C mC = new C();\n", out_); 1106 fputs(" private X mCX = new C();\n\n", out_); 1107 fputs(" private boolean mZ = false;\n", out_); 1108 fputs(" private int mI = 0;\n", out_); 1109 fputs(" private long mJ = 0;\n", out_); 1110 fputs(" private float mF = 0;\n", out_); 1111 fputs(" private double mD = 0;\n\n", out_); 1112 } 1113 1114 // Emit array declaration. 1115 void emitArrayDecl() { 1116 fputs(" private ", out_); 1117 emitType(array_type_); 1118 for (uint32_t i = 0; i < array_dim_; i++) { 1119 fputs("[]", out_); 1120 } 1121 fputs(" mArray = new ", out_); 1122 emitType(array_type_); 1123 for (uint32_t i = 0; i < array_dim_; i++) { 1124 fprintf(out_, "[%d]", array_size_); 1125 } 1126 fputs(";\n\n", out_); 1127 } 1128 1129 // Emit test constructor. 1130 void emitTestConstructor() { 1131 fputs(" private Test() {\n", out_); 1132 indentation_ += 2; 1133 emitIndentation(); 1134 emitType(array_type_); 1135 fputs(" a = ", out_); 1136 emitLiteral(array_type_); 1137 fputs(";\n", out_); 1138 for (uint32_t i = 0; i < array_dim_; i++) { 1139 emitIndentation(); 1140 fprintf(out_, "for (int i%u = 0; i%u < %u; i%u++) {\n", i, i, array_size_, i); 1141 indentation_ += 2; 1142 } 1143 emitIndentation(); 1144 fputs("mArray", out_); 1145 for (uint32_t i = 0; i < array_dim_; i++) { 1146 fprintf(out_, "[i%u]", i); 1147 } 1148 fputs(" = a;\n", out_); 1149 emitIndentation(); 1150 if (array_type_ == kBoolean) { 1151 fputs("a = !a;\n", out_); 1152 } else { 1153 fputs("a++;\n", out_); 1154 } 1155 for (uint32_t i = 0; i < array_dim_; i++) { 1156 indentation_ -= 2; 1157 emitIndentation(); 1158 fputs("}\n", out_); 1159 } 1160 indentation_ -= 2; 1161 fputs(" }\n\n", out_); 1162 } 1163 1164 // Emit test method. 1165 void emitTestMethod() { 1166 fputs(" private ", out_); 1167 emitType(return_type_); 1168 fputs(" testMethod() {\n", out_); 1169 indentation_ += 2; 1170 if (emitStatementList()) { 1171 // Must end with return. 1172 emitIndentation(); 1173 emitReturn(true); 1174 } 1175 indentation_ -= 2; 1176 fputs(" }\n\n", out_); 1177 } 1178 1179 // Emit main method driver. 1180 void emitMainMethod() { 1181 fputs(" public static void main(String[] args) {\n", out_); 1182 indentation_ += 2; 1183 fputs(" Test t = new Test();\n ", out_); 1184 emitType(return_type_); 1185 fputs(" r = ", out_); 1186 emitLiteral(return_type_); 1187 fputs(";\n", out_); 1188 fputs(" try {\n", out_); 1189 fputs(" r = t.testMethod();\n", out_); 1190 fputs(" } catch (Exception e) {\n", out_); 1191 fputs(" // Arithmetic, null pointer, index out of bounds, etc.\n", out_); 1192 fputs(" System.out.println(\"An exception was caught.\");\n", out_); 1193 fputs(" }\n", out_); 1194 fputs(" System.out.println(\"r = \" + r);\n", out_); 1195 fputs(" System.out.println(\"mZ = \" + t.mZ);\n", out_); 1196 fputs(" System.out.println(\"mI = \" + t.mI);\n", out_); 1197 fputs(" System.out.println(\"mJ = \" + t.mJ);\n", out_); 1198 fputs(" System.out.println(\"mF = \" + t.mF);\n", out_); 1199 fputs(" System.out.println(\"mD = \" + t.mD);\n", out_); 1200 fputs(" System.out.println(\"mArray = \" + ", out_); 1201 if (array_dim_ == 1) { 1202 fputs("Arrays.toString(t.mArray)", out_); 1203 } else { 1204 fputs("Arrays.deepToString(t.mArray)", out_); 1205 } 1206 fputs(");\n", out_); 1207 indentation_ -= 2; 1208 fputs(" }\n", out_); 1209 } 1210 1211 // Emit a static void method. 1212 void emitStaticNopMethod() { 1213 fputs(" public static void nop() {}\n\n", out_); 1214 } 1215 1216 // Emit program header. Emit command line options in the comments. 1217 void emitHeader() { 1218 fputs("\n/**\n * AOSP JFuzz Tester.\n", out_); 1219 fputs(" * Automatically generated program.\n", out_); 1220 fprintf(out_, 1221 " * jfuzz -s %u -d %u -l %u -i %u -n %u (version %s)\n */\n\n", 1222 fuzz_seed_, 1223 fuzz_expr_depth_, 1224 fuzz_stmt_length_, 1225 fuzz_if_nest_, 1226 fuzz_loop_nest_, 1227 VERSION); 1228 fputs("import java.util.Arrays;\n\n", out_); 1229 } 1230 1231 // Emit single test class with main driver. 1232 void emitTestClassWithMain() { 1233 fputs("public class Test {\n\n", out_); 1234 indentation_ += 2; 1235 emitClassDecls(); 1236 emitFieldDecls(); 1237 emitArrayDecl(); 1238 emitTestConstructor(); 1239 emitTestMethod(); 1240 emitStaticNopMethod(); 1241 emitMainMethod(); 1242 indentation_ -= 2; 1243 fputs("}\n\n", out_); 1244 } 1245 1246 // 1247 // Random integers. 1248 // 1249 1250 // Return random integer. 1251 int32_t random() { 1252 return fuzz_random_engine_(); 1253 } 1254 1255 // Return random integer in range [0,max). 1256 uint32_t random0(uint32_t max) { 1257 std::uniform_int_distribution<uint32_t> gen(0, max - 1); 1258 return gen(fuzz_random_engine_); 1259 } 1260 1261 // Return random integer in range [1,max]. 1262 uint32_t random1(uint32_t max) { 1263 std::uniform_int_distribution<uint32_t> gen(1, max); 1264 return gen(fuzz_random_engine_); 1265 } 1266 1267 // Fuzzing parameters. 1268 FILE* out_; 1269 std::mt19937 fuzz_random_engine_; 1270 const uint32_t fuzz_seed_; 1271 const uint32_t fuzz_expr_depth_; 1272 const uint32_t fuzz_stmt_length_; 1273 const uint32_t fuzz_if_nest_; 1274 const uint32_t fuzz_loop_nest_; 1275 const uint32_t fuzz_try_nest_; 1276 1277 // Return and array setup. 1278 const Type return_type_; 1279 const Type array_type_; 1280 const uint32_t array_dim_; 1281 const uint32_t array_size_; 1282 1283 // Current context. 1284 uint32_t indentation_; 1285 uint32_t expr_depth_; 1286 uint32_t stmt_length_; 1287 uint32_t if_nest_; 1288 uint32_t loop_nest_; 1289 uint32_t switch_nest_; 1290 uint32_t do_nest_; 1291 uint32_t try_nest_; 1292 uint32_t boolean_local_; 1293 uint32_t int_local_; 1294 uint32_t long_local_; 1295 uint32_t float_local_; 1296 uint32_t double_local_; 1297 bool in_inner_; 1298 }; 1299 1300 } // anonymous namespace 1301 1302 int32_t main(int32_t argc, char** argv) { 1303 // Time-based seed. 1304 struct timeval tp; 1305 gettimeofday(&tp, NULL); 1306 1307 // Defaults. 1308 uint32_t seed = (tp.tv_sec * 1000000 + tp.tv_usec); 1309 uint32_t expr_depth = 1; 1310 uint32_t stmt_length = 8; 1311 uint32_t if_nest = 2; 1312 uint32_t loop_nest = 3; 1313 uint32_t try_nest = 2; 1314 1315 // Parse options. 1316 while (1) { 1317 int32_t option = getopt(argc, argv, "s:d:l:i:n:vh"); 1318 if (option < 0) { 1319 break; // done 1320 } 1321 switch (option) { 1322 case 's': 1323 seed = strtoul(optarg, nullptr, 0); // deterministic seed 1324 break; 1325 case 'd': 1326 expr_depth = strtoul(optarg, nullptr, 0); 1327 break; 1328 case 'l': 1329 stmt_length = strtoul(optarg, nullptr, 0); 1330 break; 1331 case 'i': 1332 if_nest = strtoul(optarg, nullptr, 0); 1333 break; 1334 case 'n': 1335 loop_nest = strtoul(optarg, nullptr, 0); 1336 break; 1337 case 't': 1338 try_nest = strtoul(optarg, nullptr, 0); 1339 break; 1340 case 'v': 1341 fprintf(stderr, "jfuzz version %s\n", VERSION); 1342 return 0; 1343 case 'h': 1344 default: 1345 fprintf(stderr, 1346 "usage: %s [-s seed] " 1347 "[-d expr-depth] [-l stmt-length] " 1348 "[-i if-nest] [-n loop-nest] [-t try-nest] [-v] [-h]\n", 1349 argv[0]); 1350 return 1; 1351 } 1352 } 1353 1354 // Seed global random generator. 1355 srand(seed); 1356 1357 // Generate fuzzed program. 1358 JFuzz fuzz(stdout, seed, expr_depth, stmt_length, if_nest, loop_nest, try_nest); 1359 fuzz.emitProgram(); 1360 return 0; 1361 } 1362
