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>
countof(T const (&)[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:
JFuzz(FILE * out,uint32_t seed,uint32_t expr_depth,uint32_t stmt_length,uint32_t if_nest,uint32_t loop_nest,uint32_t try_nest)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
~JFuzz()126 ~JFuzz() { }
127
emitProgram()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.
isInteger(Type tp)148 static bool isInteger(Type tp) {
149 return tp == kInt || tp == kLong;
150 }
151
152 // Test for a floating-point type.
isFP(Type tp)153 static bool isFP(Type tp) {
154 return tp == kFloat || tp == kDouble;
155 }
156
157 // Emit type.
emitType(Type tp) const158 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.
emitTypeClass(Type tp) const169 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.
randomType()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>
emitOneOf(const char * const (& ops)[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).
emitUnaryOp(Type tp)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).
emitIncDecOp(Type tp)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).
emitBinaryOp(Type tp)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).
emitAssignmentOp(Type tp)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).
emitRelationalOp(Type tp)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).
emitTypeConversionOp(Type tp)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).
emitTypeConversion(Type tp)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).
emitIntrinsic1(Type tp)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).
emitIntrinsic2(Type tp)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).
emitIntrinsic(Type tp)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).
emitMethodCall(Type tp)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.
emitUnbox(Type tp)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.
emitMisc(Type tp)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.
adjustLocal(Type tp,int32_t a)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.
emitUpperBound()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.
emitArrayIndex()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.
emitLiteral(Type tp)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.
emitArrayVariable(Type tp)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.
emitLocalVariable(Type tp)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.
emitFieldVariable(Type tp)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.
emitVariable(Type tp)560 void emitVariable(Type tp) {
561 switch (random1(4)) {
562 case 1:
563 if (emitArrayVariable(tp))
564 return;
565 [[fallthrough]];
566 case 2:
567 if (emitLocalVariable(tp))
568 return;
569 [[fallthrough]];
570 default:
571 emitFieldVariable(tp);
572 break;
573 }
574 }
575
576 // Emit an expression.
emitExpression(Type tp)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.
emitIndentation() const655 void emitIndentation() const {
656 for (uint32_t i = 0; i < indentation_; i++) {
657 fputc(' ', out_);
658 }
659 }
660
661 // Emit a return statement.
emitReturn(bool mustEmit)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.
emitContinue()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.
emitBreak()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.
emitScope()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.
emitArrayInitDim(int dim)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 // }
emitArrayInit()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.
emitForLoop()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.
emitDoLoop()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.
emitIfStmt()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
emitTry()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
emitCatch()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
emitFinally()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.
emitTryCatchFinally()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.
emitSwitch()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
emitNopCall()1010 bool emitNopCall() {
1011 fputs("nop();\n", out_);
1012 return true;
1013 }
1014
1015 // Emit an assignment statement.
emitAssignment()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.
emitStatement()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.
emitStatementList()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.
emitClassDecls()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.
emitFieldDecls()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.
emitArrayDecl()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.
emitTestConstructor()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.
emitTestMethod()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.
emitMainMethod()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.
emitStaticNopMethod()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.
emitHeader()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.
emitTestClassWithMain()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.
random()1251 int32_t random() {
1252 return fuzz_random_engine_();
1253 }
1254
1255 // Return random integer in range [0,max).
random0(uint32_t 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].
random1(uint32_t 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
main(int32_t argc,char ** argv)1302 int32_t main(int32_t argc, char** argv) {
1303 // Time-based seed.
1304 struct timeval tp;
1305 gettimeofday(&tp, nullptr);
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