Welcome to JavaFuzz as our latest A[a]rt tools team member!
Rationale:
JavaFuzz is tool for generating random Java programs with
the objective of fuzz testing the ART infrastructure. Each
randomly generated Java program can be run under various
modes of execution, such as using the interpreter, using
the optimizing compiler, using an external reference
implementation, or using various target architectures.
Any difference between the outputs (a divergence) may
indicate a bug in one of the execution modes.
Test: tbd
Bug=30610121
Change-Id: I92dcac35f5229996936d01a0ba7f5acf6dc7b433
diff --git a/tools/javafuzz/javafuzz.cc b/tools/javafuzz/javafuzz.cc
new file mode 100644
index 0000000..4e6e978
--- /dev/null
+++ b/tools/javafuzz/javafuzz.cc
@@ -0,0 +1,1072 @@
+/*
+ * Copyright 2016, The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <random>
+
+#include <inttypes.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <unistd.h>
+#include <time.h>
+
+namespace {
+
+/*
+ * Java operators.
+ */
+
+#define EMIT(x) fputs((x)[random0(sizeof(x)/sizeof(const char*))], out_);
+
+static constexpr const char* kIncDecOps[] = { "++", "--" };
+static constexpr const char* kIntUnaryOps[] = { "+", "-", "~" };
+static constexpr const char* kFpUnaryOps[] = { "+", "-" };
+
+static constexpr const char* kBoolBinOps[] = { "&&", "||", "&", "|", "^" }; // few less common
+static constexpr const char* kIntBinOps[] = { "+", "-", "*", "/", "%",
+ ">>", ">>>", "<<", "&", "|", "^" };
+static constexpr const char* kFpBinOps[] = { "+", "-", "*", "/" };
+
+static constexpr const char* kBoolAssignOps[] = { "=", "&=" , "|=", "^=" }; // few less common
+static constexpr const char* kIntAssignOps[] = { "=", "+=", "-=", "*=", "/=", "%=",
+ ">>=", ">>>=", "<<=", "&=", "|=", "^=" };
+static constexpr const char* kFpAssignOps[] = { "=", "+=", "-=", "*=", "/=" };
+
+static constexpr const char* kBoolRelOps[] = { "==", "!=" };
+static constexpr const char* kRelOps[] = { "==", "!=", ">", ">=", "<", "<=" };
+
+/*
+ * Version of JavaFuzz. Increase this each time changes are made to the program
+ * to preserve the property that a given version of JavaFuzz yields the same
+ * fuzzed Java program for a deterministic random seed.
+ */
+const char* VERSION = "1.0";
+
+/**
+ * A class that generates a random Java program that compiles correctly. The program
+ * is generated using rules that generate various programming constructs. Each rule
+ * has a fixed probability to "fire". Running a generated program yields deterministic
+ * output, making it suited to test various modes of execution (e.g an interpreter vs.
+ * an compiler or two different run times) for divergences.
+ *
+ * TODO: Due to the original scope of this project, the generated Java program is heavy
+ * on loops, arrays, and basic operations; fuzzing other aspects of Java programs,
+ * like elaborate typing, class hierarchies, and interfaces is still TBD.
+ */
+class JavaFuzz {
+ public:
+ JavaFuzz(FILE* out,
+ uint32_t seed,
+ uint32_t expr_depth,
+ uint32_t stmt_length,
+ uint32_t if_nest,
+ uint32_t loop_nest)
+ : out_(out),
+ fuzz_random_engine_(seed),
+ fuzz_seed_(seed),
+ fuzz_expr_depth_(expr_depth),
+ fuzz_stmt_length_(stmt_length),
+ fuzz_if_nest_(if_nest),
+ fuzz_loop_nest_(loop_nest),
+ return_type_(randomType()),
+ array_type_(randomType()),
+ array_dim_(random1(3)),
+ array_size_(random1(10)),
+ indentation_(0),
+ expr_depth_(0),
+ stmt_length_(0),
+ if_nest_(0),
+ loop_nest_(0),
+ switch_nest_(0),
+ do_nest_(0),
+ boolean_local_(0),
+ int_local_(0),
+ long_local_(0),
+ float_local_(0),
+ double_local_(0) { }
+
+ ~JavaFuzz() { }
+
+ void emitProgram() {
+ emitHeader();
+ emitTestClassWithMain();
+ }
+
+ private:
+ //
+ // Types.
+ //
+
+ // Current type of each expression during generation.
+ enum Type {
+ kBoolean,
+ kInt,
+ kLong,
+ kFloat,
+ kDouble
+ };
+
+ // Test for an integral type.
+ static bool isInteger(Type tp) {
+ return tp == kInt || tp == kLong;
+ }
+
+ // Test for a floating-point type.
+ static bool isFP(Type tp) {
+ return tp == kFloat || tp == kDouble;
+ }
+
+ // Emit type.
+ void emitType(Type tp) const {
+ switch (tp) {
+ case kBoolean: fputs("boolean", out_); break;
+ case kInt: fputs("int", out_); break;
+ case kLong: fputs("long", out_); break;
+ case kFloat: fputs("float", out_); break;
+ case kDouble: fputs("double", out_); break;
+ }
+ }
+
+ // Emit type class.
+ void emitTypeClass(Type tp) const {
+ switch (tp) {
+ case kBoolean: fputs("Boolean", out_); break;
+ case kInt: fputs("Integer", out_); break;
+ case kLong: fputs("Long", out_); break;
+ case kFloat: fputs("Float", out_); break;
+ case kDouble: fputs("Double", out_); break;
+ }
+ }
+
+ // Return a random type.
+ Type randomType() {
+ switch (random1(5)) {
+ case 1: return kBoolean;
+ case 2: return kInt;
+ case 3: return kLong;
+ case 4: return kFloat;
+ default: return kDouble;
+ }
+ }
+
+ //
+ // Expressions.
+ //
+
+ // Emit an unary operator (same type in-out).
+ void emitUnaryOp(Type tp) {
+ if (tp == kBoolean) {
+ fputs("!", out_);
+ } else if (isInteger(tp)) {
+ EMIT(kIntUnaryOps);
+ } else { // isFP(tp)
+ EMIT(kFpUnaryOps);
+ }
+ }
+
+ // Emit a pre/post-increment/decrement operator (same type in-out).
+ void emitIncDecOp(Type tp) {
+ if (tp == kBoolean) {
+ // Not applicable, just leave "as is".
+ } else { // isInteger(tp) || isFP(tp)
+ EMIT(kIncDecOps);
+ }
+ }
+
+ // Emit a binary operator (same type in-out).
+ void emitBinaryOp(Type tp) {
+ if (tp == kBoolean) {
+ EMIT(kBoolBinOps);
+ } else if (isInteger(tp)) {
+ EMIT(kIntBinOps);
+ } else { // isFP(tp)
+ EMIT(kFpBinOps);
+ }
+ }
+
+ // Emit an assignment operator (same type in-out).
+ void emitAssignmentOp(Type tp) {
+ if (tp == kBoolean) {
+ EMIT(kBoolAssignOps);
+ } else if (isInteger(tp)) {
+ EMIT(kIntAssignOps);
+ } else { // isFP(tp)
+ EMIT(kFpAssignOps);
+ }
+ }
+
+ // Emit a relational operator (one type in, boolean out).
+ void emitRelationalOp(Type tp) {
+ if (tp == kBoolean) {
+ EMIT(kBoolRelOps);
+ } else { // isInteger(tp) || isFP(tp)
+ EMIT(kRelOps);
+ }
+ }
+
+ // Emit a type conversion operator sequence (out type given, new suitable in type picked).
+ Type emitTypeConversionOp(Type tp) {
+ if (tp == kInt) {
+ switch (random1(5)) {
+ case 1: fputs("(int)", out_); return kLong;
+ case 2: fputs("(int)", out_); return kFloat;
+ case 3: fputs("(int)", out_); return kDouble;
+ // Narrowing-widening.
+ case 4: fputs("(int)(byte)(int)", out_); return kInt;
+ case 5: fputs("(int)(short)(int)", out_); return kInt;
+ }
+ } else if (tp == kLong) {
+ switch (random1(6)) {
+ case 1: /* implicit */ return kInt;
+ case 2: fputs("(long)", out_); return kFloat;
+ case 3: fputs("(long)", out_); return kDouble;
+ // Narrowing-widening.
+ case 4: fputs("(long)(byte)(long)", out_); return kLong;
+ case 5: fputs("(long)(short)(long)", out_); return kLong;
+ case 6: fputs("(long)(int)(long)", out_); return kLong;
+ }
+ } else if (tp == kFloat) {
+ switch (random1(3)) {
+ case 1: fputs("(float)", out_); return kInt;
+ case 2: fputs("(float)", out_); return kLong;
+ case 3: fputs("(float)", out_); return kDouble;
+ }
+ } else if (tp == kDouble) {
+ switch (random1(3)) {
+ case 1: fputs("(double)", out_); return kInt;
+ case 2: fputs("(double)", out_); return kLong;
+ case 3: fputs("(double)", out_); return kFloat;
+ }
+ }
+ return tp; // nothing suitable, just keep type
+ }
+
+ // Emit a type conversion (out type given, new suitable in type picked).
+ void emitTypeConversion(Type tp) {
+ if (tp == kBoolean) {
+ Type tp = randomType();
+ emitExpression(tp);
+ fputc(' ', out_);
+ emitRelationalOp(tp);
+ fputc(' ', out_);
+ emitExpression(tp);
+ } else {
+ tp = emitTypeConversionOp(tp);
+ fputc(' ', out_);
+ emitExpression(tp);
+ }
+ }
+
+ // Emit an unary intrinsic (out type given, new suitable in type picked).
+ Type emitIntrinsic1(Type tp) {
+ if (tp == kBoolean) {
+ switch (random1(4)) {
+ case 1: fputs("Float.isNaN", out_); return kFloat;
+ case 2: fputs("Float.isInfinite", out_); return kFloat;
+ case 3: fputs("Double.isNaN", out_); return kDouble;
+ case 4: fputs("Double.isInfinite", out_); return kDouble;
+ }
+ } else if (isInteger(tp)) {
+ const char* prefix = tp == kLong ? "Long" : "Integer";
+ switch (random1(9)) {
+ case 1: fprintf(out_, "%s.highestOneBit", prefix); break;
+ case 2: fprintf(out_, "%s.lowestOneBit", prefix); break;
+ case 3: fprintf(out_, "%s.numberOfLeadingZeros", prefix); break;
+ case 4: fprintf(out_, "%s.numberOfTrailingZeros", prefix); break;
+ case 5: fprintf(out_, "%s.bitCount", prefix); break;
+ case 6: fprintf(out_, "%s.signum", prefix); break;
+ case 7: fprintf(out_, "%s.reverse", prefix); break;
+ case 8: fprintf(out_, "%s.reverseBytes", prefix); break;
+ case 9: fputs("Math.abs", out_); break;
+ }
+ } else { // isFP(tp)
+ switch (random1(5)) {
+ case 1: fputs("Math.abs", out_); break;
+ case 2: fputs("Math.ulp", out_); break;
+ case 3: fputs("Math.signum", out_); break;
+ case 4: fputs("Math.nextUp", out_); break;
+ case 5: fputs("Math.nextDown", out_); break;
+ }
+ }
+ return tp; // same type in-out
+ }
+
+ // Emit a binary intrinsic (out type given, new suitable in type picked).
+ Type emitIntrinsic2(Type tp) {
+ if (tp == kBoolean) {
+ switch (random1(3)) {
+ case 1: fputs("Boolean.logicalAnd", out_); break;
+ case 2: fputs("Boolean.logicalOr", out_); break;
+ case 3: fputs("Boolean.logicalXor", out_); break;
+ }
+ } else if (isInteger(tp)) {
+ const char* prefix = tp == kLong ? "Long" : "Integer";
+ switch (random1(3)) {
+ case 1: fprintf(out_, "%s.compare", prefix); break;
+ case 2: fputs("Math.min", out_); break;
+ case 3: fputs("Math.max", out_); break;
+ }
+ } else { // isFP(tp)
+ switch (random1(2)) {
+ case 1: fputs("Math.min", out_); break;
+ case 2: fputs("Math.max", out_); break;
+ }
+ }
+ return tp; // same type in-out
+ }
+
+ // Emit an intrinsic (out type given, new suitable in type picked).
+ void emitIntrinsic(Type tp) {
+ if (random1(2) == 1) {
+ tp = emitIntrinsic1(tp);
+ fputc('(', out_);
+ emitExpression(tp);
+ fputc(')', out_);
+ } else {
+ tp = emitIntrinsic2(tp);
+ fputc('(', out_);
+ emitExpression(tp);
+ fputs(", ", out_);
+ emitExpression(tp);
+ fputc(')', out_);
+ }
+ }
+
+ // Emit unboxing boxed object.
+ void emitUnbox(Type tp) {
+ fputc('(', out_);
+ emitType(tp);
+ fputs(") new ", out_);
+ emitTypeClass(tp);
+ fputc('(', out_);
+ emitExpression(tp);
+ fputc(')', out_);
+ }
+
+ // Emit miscellaneous constructs.
+ void emitMisc(Type tp) {
+ switch (tp) {
+ case kBoolean: fputs("this instanceof Test", out_); break;
+ case kInt: fputs("mArray.length", out_); break;
+ case kLong: fputs("Long.MAX_VALUE", out_); break;
+ case kFloat: fputs("Float.MAX_VALUE", out_); break;
+ case kDouble: fputs("Double.MAX_VALUE", out_); break;
+ }
+ }
+
+ // Adjust local of given type and return adjusted value.
+ uint32_t adjustLocal(Type tp, int32_t a) {
+ switch (tp) {
+ case kBoolean: boolean_local_ += a; return boolean_local_;
+ case kInt: int_local_ += a; return int_local_;
+ case kLong: long_local_ += a; return long_local_;
+ case kFloat: float_local_ += a; return float_local_;
+ default: double_local_ += a; return double_local_;
+ }
+ }
+
+ // Emit an expression that is a strict upper bound for an array index.
+ void emitUpperBound() {
+ if (random1(8) == 1) {
+ fputs("mArray.length", out_);
+ } else if (random1(8) == 1) {
+ fprintf(out_, "%u", random1(array_size_)); // random in range
+ } else {
+ fprintf(out_, "%u", array_size_);
+ }
+ }
+
+ // Emit an array index, usually within proper range.
+ void emitArrayIndex() {
+ if (loop_nest_ > 0 && random1(2) == 1) {
+ fprintf(out_, "i%u", random0(loop_nest_));
+ } else if (random1(8) == 1) {
+ fputs("mArray.length - 1", out_);
+ } else {
+ fprintf(out_, "%u", random0(array_size_)); // random in range
+ }
+ // Introduce potential off by one errors with low probability.
+ if (random1(100) == 1) {
+ if (random1(2) == 1) {
+ fputs(" - 1", out_);
+ } else {
+ fputs(" + 1", out_);
+ }
+ }
+ }
+
+ // Emit a literal.
+ void emitLiteral(Type tp) {
+ switch (tp) {
+ case kBoolean: fputs(random1(2) == 1 ? "true" : "false", out_); break;
+ case kInt: fprintf(out_, "%d", random0(100)); break;
+ case kLong: fprintf(out_, "%dL", random0(100)); break;
+ case kFloat: fprintf(out_, "%d.0f", random0(100)); break;
+ case kDouble: fprintf(out_, "%d.0", random0(100)); break;
+ }
+ }
+
+ // Emit array variable, if available.
+ bool emitArrayVariable(Type tp) {
+ if (tp == array_type_) {
+ fputs("mArray", out_);
+ for (uint32_t i = 0; i < array_dim_; i++) {
+ fputc('[', out_);
+ emitArrayIndex();
+ fputc(']', out_);
+ }
+ return true;
+ }
+ return false;
+ }
+
+ // Emit a loop variable, if available.
+ bool emitLoopVariable(Type tp) {
+ if (tp == kInt) {
+ if (loop_nest_ > 0) {
+ fprintf(out_, "i%u", random0(loop_nest_));
+ return true;
+ }
+ }
+ return false;
+ }
+
+ // Emit a local variable, if available.
+ bool emitLocalVariable(Type tp) {
+ uint32_t locals = adjustLocal(tp, 0);
+ if (locals > 0) {
+ uint32_t local = random0(locals);
+ switch (tp) {
+ case kBoolean: fprintf(out_, "lZ%u", local); break;
+ case kInt: fprintf(out_, "lI%u", local); break;
+ case kLong: fprintf(out_, "lJ%u", local); break;
+ case kFloat: fprintf(out_, "lF%u", local); break;
+ case kDouble: fprintf(out_, "lD%u", local); break;
+ }
+ return true;
+ }
+ return false;
+ }
+
+ // Emit a field variable.
+ void emitFieldVariable(Type tp) {
+ switch (tp) {
+ case kBoolean:fputs("mZ", out_); break;
+ case kInt: fputs("mI", out_); break;
+ case kLong: fputs("mJ", out_); break;
+ case kFloat: fputs("mF", out_); break;
+ case kDouble: fputs("mD", out_); break;
+ }
+ }
+
+ // Emit a variable.
+ void emitVariable(Type tp) {
+ switch (random1(4)) {
+ case 1:
+ if (emitArrayVariable(tp))
+ return;
+ // FALL-THROUGH
+ case 2:
+ if (emitLocalVariable(tp))
+ return;
+ // FALL-THROUGH
+ case 3:
+ if (emitLoopVariable(tp))
+ return;
+ // FALL-THROUGH
+ default:
+ emitFieldVariable(tp);
+ break;
+ }
+ }
+
+ // Emit an expression.
+ void emitExpression(Type tp) {
+ // Continuing expression becomes less likely as the depth grows.
+ if (random1(expr_depth_ + 1) > fuzz_expr_depth_) {
+ if (random1(2) == 1) {
+ emitLiteral(tp);
+ } else {
+ emitVariable(tp);
+ }
+ return;
+ }
+
+ expr_depth_++;
+
+ fputc('(', out_);
+ switch (random1(12)) { // favor binary operations
+ case 1:
+ // Unary operator: ~x
+ emitUnaryOp(tp);
+ emitExpression(tp);
+ break;
+ case 2:
+ // Pre-increment: ++x
+ emitIncDecOp(tp);
+ emitVariable(tp);
+ break;
+ case 3:
+ // Post-increment: x++
+ emitVariable(tp);
+ emitIncDecOp(tp);
+ break;
+ case 4:
+ // Ternary operator: b ? x : y
+ emitExpression(kBoolean);
+ fputs(" ? ", out_);
+ emitExpression(tp);
+ fputs(" : ", out_);
+ emitExpression(tp);
+ break;
+ case 5:
+ // Type conversion: (float) x
+ emitTypeConversion(tp);
+ break;
+ case 6:
+ // Intrinsic: foo(x)
+ emitIntrinsic(tp);
+ break;
+ case 7:
+ // Emit unboxing boxed value: (int) Integer(x)
+ emitUnbox(tp);
+ break;
+ case 8:
+ // Miscellaneous constructs: a.length
+ emitMisc(tp);
+ break;
+ default:
+ // Binary operator: x + y
+ emitExpression(tp);
+ fputc(' ', out_);
+ emitBinaryOp(tp);
+ fputc(' ', out_);
+ emitExpression(tp);
+ break;
+ }
+ fputc(')', out_);
+
+ --expr_depth_;
+ }
+
+ //
+ // Statements.
+ //
+
+ // Emit current indentation.
+ void emitIndentation() const {
+ for (uint32_t i = 0; i < indentation_; i++) {
+ fputc(' ', out_);
+ }
+ }
+
+ // Emit a return statement.
+ bool emitReturn(bool mustEmit) {
+ // Only emit when we must, or with low probability inside ifs/loops,
+ // but outside do-while to avoid confusing the may follow status.
+ if (mustEmit || ((if_nest_ + loop_nest_) > 0 && do_nest_ == 0 && random1(10) == 1)) {
+ fputs("return ", out_);
+ emitExpression(return_type_);
+ fputs(";\n", out_);
+ return false;
+ }
+ // Fall back to assignment.
+ return emitAssignment();
+ }
+
+ // Emit a continue statement.
+ bool emitContinue() {
+ // Only emit with low probability inside loops.
+ if (loop_nest_ > 0 && random1(10) == 1) {
+ fputs("continue;\n", out_);
+ return false;
+ }
+ // Fall back to assignment.
+ return emitAssignment();
+ }
+
+ // Emit a break statement.
+ bool emitBreak() {
+ // Only emit with low probability inside loops, but outside switches
+ // to avoid confusing the may follow status.
+ if (loop_nest_ > 0 && switch_nest_ == 0 && random1(10) == 1) {
+ fputs("break;\n", out_);
+ return false;
+ }
+ // Fall back to assignment.
+ return emitAssignment();
+ }
+
+ // Emit a new scope with a local variable declaration statement.
+ bool emitScope() {
+ Type tp = randomType();
+ fputs("{\n", out_);
+ indentation_ += 2;
+ emitIndentation();
+ emitType(tp);
+ switch (tp) {
+ case kBoolean: fprintf(out_, " lZ%u = ", boolean_local_); break;
+ case kInt: fprintf(out_, " lI%u = ", int_local_); break;
+ case kLong: fprintf(out_, " lJ%u = ", long_local_); break;
+ case kFloat: fprintf(out_, " lF%u = ", float_local_); break;
+ case kDouble: fprintf(out_, " lD%u = ", double_local_); break;
+ }
+ emitExpression(tp);
+ fputs(";\n", out_);
+
+ adjustLocal(tp, 1); // local now visible
+
+ bool mayFollow = emitStatementList();
+
+ adjustLocal(tp, -1); // local no longer visible
+
+ indentation_ -= 2;
+ emitIndentation();
+ fputs("}\n", out_);
+ return mayFollow;
+ }
+
+ // Emit a for loop.
+ bool emitForLoop() {
+ // Continuing loop nest becomes less likely as the depth grows.
+ if (random1(loop_nest_ + 1) > fuzz_loop_nest_) {
+ return emitAssignment(); // fall back
+ }
+
+ bool goesUp = random1(2) == 1;
+ fprintf(out_, "for (int i%u = ", loop_nest_);
+ if (goesUp) {
+ fprintf(out_, "0; i%u < ", loop_nest_);
+ emitUpperBound();
+ fprintf(out_, "; i%u++) {\n", loop_nest_);
+ } else {
+ emitUpperBound();
+ fprintf(out_, " - 1; i%d >= 0", loop_nest_);
+ fprintf(out_, "; i%d--) {\n", loop_nest_);
+ }
+
+ ++loop_nest_; // now in loop
+
+ indentation_ += 2;
+ emitStatementList();
+
+ --loop_nest_; // no longer in loop
+
+ indentation_ -= 2;
+ emitIndentation();
+ fprintf(out_, "}\n");
+ return true; // loop-body does not block flow
+ }
+
+ // Emit while or do-while loop.
+ bool emitDoLoop() {
+ // Continuing loop nest becomes less likely as the depth grows.
+ if (random1(loop_nest_ + 1) > fuzz_loop_nest_) {
+ return emitAssignment(); // fall back
+ }
+
+ // TODO: remove this
+ // The jack bug b/28862040 prevents generating while/do-while loops because otherwise
+ // we get dozens of reports on the same issue per nightly/ run.
+ if (true) {
+ return emitAssignment();
+ }
+
+ bool isWhile = random1(2) == 1;
+ fputs("{\n", out_);
+ indentation_ += 2;
+ emitIndentation();
+ fprintf(out_, "int i%u = %d;", loop_nest_, isWhile ? -1 : 0);
+ emitIndentation();
+ if (isWhile) {
+ fprintf(out_, "while (++i%u < ", loop_nest_);
+ emitUpperBound();
+ fputs(") {\n", out_);
+ } else {
+ fputs("do {\n", out_);
+ do_nest_++;
+ }
+
+ ++loop_nest_; // now in loop
+
+ indentation_ += 2;
+ emitStatementList();
+
+ --loop_nest_; // no longer in loop
+
+ indentation_ -= 2;
+ emitIndentation();
+ if (isWhile) {
+ fputs("}\n", out_);
+ } else {
+ fprintf(out_, "} while (++i%u < ", loop_nest_);
+ emitUpperBound();
+ fputs(");\n", out_);
+ --do_nest_;
+ }
+ indentation_ -= 2;
+ emitIndentation();
+ fputs("}\n", out_);
+ return true; // loop-body does not block flow
+ }
+
+ // Emit an if statement.
+ bool emitIfStmt() {
+ // Continuing if nest becomes less likely as the depth grows.
+ if (random1(if_nest_ + 1) > fuzz_if_nest_) {
+ return emitAssignment(); // fall back
+ }
+
+ fputs("if (", out_);
+ emitExpression(kBoolean);
+ fputs(") {\n", out_);
+
+ ++if_nest_; // now in if
+
+ indentation_ += 2;
+ bool mayFollowTrue = emitStatementList();
+ indentation_ -= 2;
+ emitIndentation();
+ fprintf(out_, "} else {\n");
+ indentation_ += 2;
+ bool mayFollowFalse = emitStatementList();
+
+ --if_nest_; // no longer in if
+
+ indentation_ -= 2;
+ emitIndentation();
+ fprintf(out_, "}\n");
+ return mayFollowTrue || mayFollowFalse;
+ }
+
+ // Emit a switch statement.
+ bool emitSwitch() {
+ // Continuing if nest becomes less likely as the depth grows.
+ if (random1(if_nest_ + 1) > fuzz_if_nest_) {
+ return emitAssignment(); // fall back
+ }
+
+ bool mayFollow = false;
+ fputs("switch (", out_);
+ emitExpression(kInt);
+ fputs(") {\n", out_);
+
+ ++if_nest_;
+ ++switch_nest_; // now in switch
+
+ indentation_ += 2;
+ for (uint32_t i = 0; i < 2; i++) {
+ emitIndentation();
+ if (i == 0) {
+ fprintf(out_, "case %d: {\n", random0(100));
+ } else {
+ fprintf(out_, "default: {\n");
+ }
+ indentation_ += 2;
+ if (emitStatementList()) {
+ // Must end with break.
+ emitIndentation();
+ fputs("break;\n", out_);
+ mayFollow = true;
+ }
+ indentation_ -= 2;
+ emitIndentation();
+ fputs("}\n", out_);
+ }
+
+ --if_nest_;
+ --switch_nest_; // no longer in switch
+
+ indentation_ -= 2;
+ emitIndentation();
+ fprintf(out_, "}\n");
+ return mayFollow;
+ }
+
+ // Emit an assignment statement.
+ bool emitAssignment() {
+ Type tp = randomType();
+ emitVariable(tp);
+ fputc(' ', out_);
+ emitAssignmentOp(tp);
+ fputc(' ', out_);
+ emitExpression(tp);
+ fputs(";\n", out_);
+ return true;
+ }
+
+ // Emit a single statement. Returns true if statements may follow.
+ bool emitStatement() {
+ switch (random1(16)) { // favor assignments
+ case 1: return emitReturn(false); break;
+ case 2: return emitContinue(); break;
+ case 3: return emitBreak(); break;
+ case 4: return emitScope(); break;
+ case 5: return emitForLoop(); break;
+ case 6: return emitDoLoop(); break;
+ case 7: return emitIfStmt(); break;
+ case 8: return emitSwitch(); break;
+ default: return emitAssignment(); break;
+ }
+ }
+
+ // Emit a statement list. Returns true if statements may follow.
+ bool emitStatementList() {
+ while (stmt_length_ < 1000) { // avoid run-away
+ stmt_length_++;
+ emitIndentation();
+ if (!emitStatement()) {
+ return false; // rest would be dead code
+ }
+ // Continuing this list becomes less likely as the total statement list grows.
+ if (random1(stmt_length_) > fuzz_stmt_length_) {
+ break;
+ }
+ }
+ return true;
+ }
+
+ // Emit field declarations.
+ void emitFieldDecls() {
+ fputs(" private boolean mZ = false;\n", out_);
+ fputs(" private int mI = 0;\n", out_);
+ fputs(" private long mJ = 0;\n", out_);
+ fputs(" private float mF = 0;\n", out_);
+ fputs(" private double mD = 0;\n\n", out_);
+ }
+
+ // Emit array declaration.
+ void emitArrayDecl() {
+ fputs(" private ", out_);
+ emitType(array_type_);
+ for (uint32_t i = 0; i < array_dim_; i++) {
+ fputs("[]", out_);
+ }
+ fputs(" mArray = new ", out_);
+ emitType(array_type_);
+ for (uint32_t i = 0; i < array_dim_; i++) {
+ fprintf(out_, "[%d]", array_size_);
+ }
+ fputs(";\n\n", out_);
+ }
+
+ // Emit test constructor.
+ void emitTestConstructor() {
+ fputs(" private Test() {\n", out_);
+ indentation_ += 2;
+ emitIndentation();
+ emitType(array_type_);
+ fputs(" a = ", out_);
+ emitLiteral(array_type_);
+ fputs(";\n", out_);
+ for (uint32_t i = 0; i < array_dim_; i++) {
+ emitIndentation();
+ fprintf(out_, "for (int i%u = 0; i%u < %u; i%u++) {\n", i, i, array_size_, i);
+ indentation_ += 2;
+ }
+ emitIndentation();
+ fputs("mArray", out_);
+ for (uint32_t i = 0; i < array_dim_; i++) {
+ fprintf(out_, "[i%u]", i);
+ }
+ fputs(" = a;\n", out_);
+ emitIndentation();
+ if (array_type_ == kBoolean) {
+ fputs("a = !a;\n", out_);
+ } else {
+ fputs("a++;\n", out_);
+ }
+ for (uint32_t i = 0; i < array_dim_; i++) {
+ indentation_ -= 2;
+ emitIndentation();
+ fputs("}\n", out_);
+ }
+ indentation_ -= 2;
+ fputs(" }\n\n", out_);
+ }
+
+ // Emit test method.
+ void emitTestMethod() {
+ fputs(" private ", out_);
+ emitType(return_type_);
+ fputs(" testMethod() {\n", out_);
+ indentation_ += 2;
+ if (emitStatementList()) {
+ // Must end with return.
+ emitIndentation();
+ emitReturn(true);
+ }
+ indentation_ -= 2;
+ fputs(" }\n\n", out_);
+ }
+
+ // Emit main method driver.
+ void emitMainMethod() {
+ fputs(" public static void main(String[] args) {\n", out_);
+ indentation_ += 2;
+ fputs(" Test t = new Test();\n ", out_);
+ emitType(return_type_);
+ fputs(" r = ", out_);
+ emitLiteral(return_type_);
+ fputs(";\n", out_);
+ fputs(" try {\n", out_);
+ fputs(" r = t.testMethod();\n", out_);
+ fputs(" } catch (Exception e) {\n", out_);
+ fputs(" // Arithmetic, null pointer, index out of bounds, etc.\n", out_);
+ fputs(" System.out.println(\"An exception was caught.\");\n", out_);
+ fputs(" }\n", out_);
+ fputs(" System.out.println(\"r = \" + r);\n", out_);
+ fputs(" System.out.println(\"mZ = \" + t.mZ);\n", out_);
+ fputs(" System.out.println(\"mI = \" + t.mI);\n", out_);
+ fputs(" System.out.println(\"mJ = \" + t.mJ);\n", out_);
+ fputs(" System.out.println(\"mF = \" + t.mF);\n", out_);
+ fputs(" System.out.println(\"mD = \" + t.mD);\n", out_);
+ fputs(" System.out.println(\"mArray = \" + ", out_);
+ if (array_dim_ == 1) {
+ fputs("Arrays.toString(t.mArray)", out_);
+ } else {
+ fputs("Arrays.deepToString(t.mArray)", out_);
+ }
+ fputs(");\n", out_);
+ indentation_ -= 2;
+ fputs(" }\n", out_);
+ }
+
+ // Emit program header. Emit command line options in the comments.
+ void emitHeader() {
+ fputs("\n/**\n * AOSP Java Fuzz Tester.\n", out_);
+ fputs(" * Automatically generated Java program.\n", out_);
+ fprintf(out_,
+ " * javafuzz -s %u -d %u -l %u -i %u -n %u (version %s)\n */\n\n",
+ fuzz_seed_,
+ fuzz_expr_depth_,
+ fuzz_stmt_length_,
+ fuzz_if_nest_,
+ fuzz_loop_nest_,
+ VERSION);
+ fputs("import java.util.Arrays;\n\n", out_);
+ }
+
+ // Emit single test class with main driver.
+ void emitTestClassWithMain() {
+ fputs("public class Test {\n\n", out_);
+ indentation_ += 2;
+ emitFieldDecls();
+ emitArrayDecl();
+ emitTestConstructor();
+ emitTestMethod();
+ emitMainMethod();
+ indentation_ -= 2;
+ fputs("}\n\n", out_);
+ }
+
+ //
+ // Random integers.
+ //
+
+ // Return random integer in range [0,max).
+ uint32_t random0(uint32_t max) {
+ std::uniform_int_distribution<uint32_t> gen(0, max - 1);
+ return gen(fuzz_random_engine_);
+ }
+
+ // Return random integer in range [1,max].
+ uint32_t random1(uint32_t max) {
+ std::uniform_int_distribution<uint32_t> gen(1, max);
+ return gen(fuzz_random_engine_);
+ }
+
+ // Fuzzing parameters.
+ FILE* out_;
+ std::mt19937 fuzz_random_engine_;
+ const uint32_t fuzz_seed_;
+ const uint32_t fuzz_expr_depth_;
+ const uint32_t fuzz_stmt_length_;
+ const uint32_t fuzz_if_nest_;
+ const uint32_t fuzz_loop_nest_;
+
+ // Return and array setup.
+ const Type return_type_;
+ const Type array_type_;
+ const uint32_t array_dim_;
+ const uint32_t array_size_;
+
+ // Current context.
+ uint32_t indentation_;
+ uint32_t expr_depth_;
+ uint32_t stmt_length_;
+ uint32_t if_nest_;
+ uint32_t loop_nest_;
+ uint32_t switch_nest_;
+ uint32_t do_nest_;
+ uint32_t boolean_local_;
+ uint32_t int_local_;
+ uint32_t long_local_;
+ uint32_t float_local_;
+ uint32_t double_local_;
+};
+
+} // anonymous namespace
+
+int32_t main(int32_t argc, char** argv) {
+ // Defaults.
+ uint32_t seed = time(NULL);
+ uint32_t expr_depth = 1;
+ uint32_t stmt_length = 4;
+ uint32_t if_nest = 2;
+ uint32_t loop_nest = 3;
+
+ // Parse options.
+ while (1) {
+ int32_t option = getopt(argc, argv, "s:d:l:i:n:h");
+ if (option < 0) {
+ break; // done
+ }
+ switch (option) {
+ case 's':
+ seed = strtoul(optarg, nullptr, 0); // deterministic seed
+ break;
+ case 'd':
+ expr_depth = strtoul(optarg, nullptr, 0);
+ break;
+ case 'l':
+ stmt_length = strtoul(optarg, nullptr, 0);
+ break;
+ case 'i':
+ if_nest = strtoul(optarg, nullptr, 0);
+ break;
+ case 'n':
+ loop_nest = strtoul(optarg, nullptr, 0);
+ break;
+ case 'h':
+ default:
+ fprintf(stderr,
+ "usage: %s [-s seed] "
+ "[-d expr-depth] [-l stmt-length] "
+ "[-i if-nest] [-n loop-nest] [-h]\n",
+ argv[0]);
+ return 1;
+ }
+ }
+
+ // Seed global random generator.
+ srand(seed);
+
+ // Generate fuzzed Java program.
+ JavaFuzz fuzz(stdout, seed, expr_depth, stmt_length, if_nest, loop_nest);
+ fuzz.emitProgram();
+ return 0;
+}