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/Android.mk b/tools/javafuzz/Android.mk
new file mode 100644
index 0000000..63db57a
--- /dev/null
+++ b/tools/javafuzz/Android.mk
@@ -0,0 +1,25 @@
+# Copyright (C) 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.
+
+# Java fuzzer tool.
+
+LOCAL_PATH:= $(call my-dir)
+
+include $(CLEAR_VARS)
+LOCAL_CPP_EXTENSION := cc
+LOCAL_SRC_FILES := javafuzz.cc
+LOCAL_CFLAGS += -O0 -g -Wall
+LOCAL_MODULE_HOST_OS := darwin linux windows
+LOCAL_MODULE := javafuzz
+include $(BUILD_HOST_EXECUTABLE)
diff --git a/tools/javafuzz/README.md b/tools/javafuzz/README.md
new file mode 100644
index 0000000..ca8532a
--- /dev/null
+++ b/tools/javafuzz/README.md
@@ -0,0 +1,63 @@
+JavaFuzz
+========
+
+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.
+
+JavaFuzz can be combined with dexfuzz to get multilayered fuzz testing.
+
+How to run JavaFuzz
+===================
+
+ javafuzz [-s seed] [-d expr-depth] [-l stmt-length]
+ [-i if-nest] [-n loop-nest]
+
+where
+
+ -s : defines a deterministic random seed
+ (randomized using time by default)
+ -d : defines a fuzzing depth for expressions
+ (higher values yield deeper expressions)
+ -l : defines a fuzzing length for statement lists
+ (higher values yield longer statement sequences)
+ -i : defines a fuzzing nest for if/switch statements
+ (higher values yield deeper nested conditionals)
+ -n : defines a fuzzing nest for for/while/do-while loops
+ (higher values yield deeper nested loops)
+
+The current version of JavaFuzz sends all output to stdout, and uses
+a fixed testing class named Test. So a typical test run looks as follows.
+
+ javafuzz > Test.java
+ jack -cp ${JACK_CLASSPATH} --output-dex . Test.java
+ art -classpath classes.dex Test
+
+Background
+==========
+
+Although test suites are extremely useful to validate the correctness of a
+system and to ensure that no regressions occur, any test suite is necessarily
+finite in size and scope. Tests typically focus on validating particular
+features by means of code sequences most programmers would expect. Regression
+tests often use slightly less idiomatic code sequences, since they reflect
+problems that were not anticipated originally, but occurred “in the field”.
+Still, any test suite leaves the developer wondering whether undetected bugs
+and flaws still linger in the system.
+
+Over the years, fuzz testing has gained popularity as a testing technique for
+discovering such lingering bugs, including bugs that can bring down a system in
+an unexpected way. Fuzzing refers to feeding a large amount of random data as
+input to a system in an attempt to find bugs or make it crash. Mutation-based
+fuzz testing is a special form of fuzzing that applies small random changes to
+existing inputs in order to detect shortcomings in a system. Profile-guided or
+coverage-guided fuzzing adds a direction to the way these random changes are
+applied. Multilayer approaches generate random inputs that are subsequently
+mutated at various stages of execution.
+
+The randomness of fuzz testing implies that the size and scope of testing is no
+longer bounded. Every new run can potentially discover bugs and crashes that were
+hereto undetected.
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;
+}