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