/*
|
* 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 <cmath>
|
#include <random>
|
|
#include <inttypes.h>
|
#include <stdio.h>
|
#include <stdlib.h>
|
#include <string.h>
|
#include <unistd.h>
|
|
#include <sys/time.h>
|
|
namespace {
|
|
/*
|
* Operators.
|
*/
|
|
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[] = { "==", "!=", ">", ">=", "<", "<=" };
|
|
/*
|
* Exceptions.
|
*/
|
static const char* kExceptionTypes[] = {
|
"IllegalStateException",
|
"NullPointerException",
|
"IllegalArgumentException",
|
"ArrayIndexOutOfBoundsException"
|
};
|
|
/*
|
* Version of JFuzz. Increase this each time changes are made to the program
|
* to preserve the property that a given version of JFuzz yields the same
|
* fuzzed program for a deterministic random seed.
|
*/
|
const char* VERSION = "1.5";
|
|
/*
|
* Maximum number of array dimensions, together with corresponding maximum size
|
* within each dimension (to keep memory/runtime requirements roughly the same).
|
*/
|
static const uint32_t kMaxDim = 10;
|
static const uint32_t kMaxDimSize[kMaxDim + 1] = { 0, 1000, 32, 10, 6, 4, 3, 3, 2, 2, 2 };
|
|
/*
|
* Utility function to return the number of elements in an array.
|
*/
|
template <typename T, uint32_t N>
|
constexpr uint32_t countof(T const (&)[N]) {
|
return N;
|
}
|
|
/**
|
* A class that generates a random 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.
|
*/
|
class JFuzz {
|
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)
|
: 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),
|
fuzz_try_nest_(try_nest),
|
return_type_(randomType()),
|
array_type_(randomType()),
|
array_dim_(random1(kMaxDim)),
|
array_size_(random1(kMaxDimSize[array_dim_])),
|
indentation_(0),
|
expr_depth_(0),
|
stmt_length_(0),
|
if_nest_(0),
|
loop_nest_(0),
|
switch_nest_(0),
|
do_nest_(0),
|
try_nest_(0),
|
boolean_local_(0),
|
int_local_(0),
|
long_local_(0),
|
float_local_(0),
|
double_local_(0),
|
in_inner_(false) { }
|
|
~JFuzz() { }
|
|
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;
|
}
|
}
|
|
// Emits a random strong selected from an array of operator strings.
|
template <std::uint32_t N>
|
inline void emitOneOf(const char* const (&ops)[N]) {
|
fputs(ops[random0(N)], out_);
|
}
|
|
//
|
// Expressions.
|
//
|
|
// Emit an unary operator (same type in-out).
|
void emitUnaryOp(Type tp) {
|
if (tp == kBoolean) {
|
fputc('!', out_);
|
} else if (isInteger(tp)) {
|
emitOneOf(kIntUnaryOps);
|
} else { // isFP(tp)
|
emitOneOf(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)
|
emitOneOf(kIncDecOps);
|
}
|
}
|
|
// Emit a binary operator (same type in-out).
|
void emitBinaryOp(Type tp) {
|
if (tp == kBoolean) {
|
emitOneOf(kBoolBinOps);
|
} else if (isInteger(tp)) {
|
emitOneOf(kIntBinOps);
|
} else { // isFP(tp)
|
emitOneOf(kFpBinOps);
|
}
|
}
|
|
// Emit an assignment operator (same type in-out).
|
void emitAssignmentOp(Type tp) {
|
if (tp == kBoolean) {
|
emitOneOf(kBoolAssignOps);
|
} else if (isInteger(tp)) {
|
emitOneOf(kIntAssignOps);
|
} else { // isFP(tp)
|
emitOneOf(kFpAssignOps);
|
}
|
}
|
|
// Emit a relational operator (one type in, boolean out).
|
void emitRelationalOp(Type tp) {
|
if (tp == kBoolean) {
|
emitOneOf(kBoolRelOps);
|
} else { // isInteger(tp) || isFP(tp)
|
emitOneOf(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(4)) {
|
case 1: fputs("(float)", out_); return kInt;
|
case 2: fputs("(float)", out_); return kLong;
|
case 3: fputs("(float)", out_); return kDouble;
|
// Narrowing-widening.
|
case 4: fputs("(float)(int)(float)", out_); return kFloat;
|
}
|
} else if (tp == kDouble) {
|
switch (random1(5)) {
|
case 1: fputs("(double)", out_); return kInt;
|
case 2: fputs("(double)", out_); return kLong;
|
case 3: fputs("(double)", out_); return kFloat;
|
// Narrowing-widening.
|
case 4: fputs("(double)(int)(double)", out_); return kDouble;
|
case 5: fputs("(double)(float)(double)", out_); return kDouble;
|
}
|
}
|
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(6)) {
|
case 1: fputs("Float.isNaN", out_); return kFloat;
|
case 2: fputs("Float.isFinite", out_); return kFloat;
|
case 3: fputs("Float.isInfinite", out_); return kFloat;
|
case 4: fputs("Double.isNaN", out_); return kDouble;
|
case 5: fputs("Double.isFinite", out_); return kDouble;
|
case 6: fputs("Double.isInfinite", out_); return kDouble;
|
}
|
} else if (isInteger(tp)) {
|
const char* prefix = tp == kLong ? "Long" : "Integer";
|
switch (random1(13)) {
|
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.incrementExact", out_); break;
|
case 10: fputs("Math.decrementExact", out_); break;
|
case 11: fputs("Math.negateExact", out_); break;
|
case 12: fputs("Math.abs", out_); break;
|
case 13: fputs("Math.round", out_);
|
return tp == kLong ? kDouble : kFloat;
|
}
|
} else { // isFP(tp)
|
switch (random1(6)) {
|
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;
|
case 6: if (tp == kDouble) {
|
fputs("Double.longBitsToDouble", out_);
|
return kLong;
|
} else {
|
fputs("Float.intBitsToFloat", out_);
|
return kInt;
|
}
|
}
|
}
|
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(11)) {
|
case 1: fprintf(out_, "%s.compare", prefix); break;
|
case 2: fprintf(out_, "%s.sum", prefix); break;
|
case 3: fprintf(out_, "%s.min", prefix); break;
|
case 4: fprintf(out_, "%s.max", prefix); break;
|
case 5: fputs("Math.min", out_); break;
|
case 6: fputs("Math.max", out_); break;
|
case 7: fputs("Math.floorDiv", out_); break;
|
case 8: fputs("Math.floorMod", out_); break;
|
case 9: fputs("Math.addExact", out_); break;
|
case 10: fputs("Math.subtractExact", out_); break;
|
case 11: fputs("Math.multiplyExact", out_); break;
|
}
|
} else { // isFP(tp)
|
const char* prefix = tp == kDouble ? "Double" : "Float";
|
switch (random1(5)) {
|
case 1: fprintf(out_, "%s.sum", prefix); break;
|
case 2: fprintf(out_, "%s.min", prefix); break;
|
case 3: fprintf(out_, "%s.max", prefix); break;
|
case 4: fputs("Math.min", out_); break;
|
case 5: 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 a method call (out type given).
|
void emitMethodCall(Type tp) {
|
if (tp != kBoolean && !in_inner_) {
|
// Accept all numerical types (implicit conversion) and when not
|
// declaring inner classes (to avoid infinite recursion).
|
switch (random1(8)) {
|
case 1: fputs("mA.a()", out_); break;
|
case 2: fputs("mB.a()", out_); break;
|
case 3: fputs("mB.x()", out_); break;
|
case 4: fputs("mBX.x()", out_); break;
|
case 5: fputs("mC.s()", out_); break;
|
case 6: fputs("mC.c()", out_); break;
|
case 7: fputs("mC.x()", out_); break;
|
case 8: fputs("mCX.x()", out_); break;
|
}
|
} else {
|
// Fall back to intrinsic.
|
emitIntrinsic(tp);
|
}
|
}
|
|
// 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) {
|
if (tp == kBoolean) {
|
fprintf(out_, "this instanceof %s", in_inner_ ? "X" : "Test");
|
} else if (isInteger(tp)) {
|
const char* prefix = tp == kLong ? "Long" : "Integer";
|
switch (random1(2)) {
|
case 1: fprintf(out_, "%s.MIN_VALUE", prefix); break;
|
case 2: fprintf(out_, "%s.MAX_VALUE", prefix); break;
|
}
|
} else { // isFP(tp)
|
const char* prefix = tp == kDouble ? "Double" : "Float";
|
switch (random1(6)) {
|
case 1: fprintf(out_, "%s.MIN_NORMAL", prefix); break;
|
case 2: fprintf(out_, "%s.MIN_VALUE", prefix); break;
|
case 3: fprintf(out_, "%s.MAX_VALUE", prefix); break;
|
case 4: fprintf(out_, "%s.POSITIVE_INFINITY", prefix); break;
|
case 5: fprintf(out_, "%s.NEGATIVE_INFINITY", prefix); break;
|
case 6: fprintf(out_, "%s.NaN", prefix); 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", random()); break;
|
case kLong: fprintf(out_, "%dL", random()); break;
|
case kFloat: fprintf(out_, "%d.0f", random()); break;
|
case kDouble: fprintf(out_, "%d.0", random()); 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 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;
|
[[fallthrough]];
|
case 2:
|
if (emitLocalVariable(tp))
|
return;
|
[[fallthrough]];
|
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);
|
fputc(' ', out_);
|
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:
|
// Method call: mA.a()
|
emitMethodCall(tp);
|
break;
|
case 8:
|
// Emit unboxing boxed value: (int) Integer(x)
|
emitUnbox(tp);
|
break;
|
case 9:
|
// 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 one dimension of an array initializer, where parameter dim >= 1
|
// denotes the number of remaining dimensions that should be emitted.
|
void emitArrayInitDim(int dim) {
|
if (dim == 1) {
|
// Last dimension: set of values.
|
fputs("{ ", out_);
|
for (uint32_t i = 0; i < array_size_; i++) {
|
emitExpression(array_type_);
|
fputs(", ", out_);
|
}
|
fputs("}", out_);
|
|
} else {
|
// Outer dimensions: set of sets.
|
fputs("{\n", out_);
|
indentation_ += 2;
|
emitIndentation();
|
|
for (uint32_t i = 0; i < array_size_; i++) {
|
emitArrayInitDim(dim - 1);
|
if (i != array_size_ - 1) {
|
fputs(",\n", out_);
|
emitIndentation();
|
}
|
}
|
|
fputs(",\n", out_);
|
indentation_ -= 2;
|
emitIndentation();
|
fputs("}", out_);
|
}
|
}
|
|
// Emit an array initializer of the following form.
|
// {
|
// type[]..[] tmp = { .. };
|
// mArray = tmp;
|
// }
|
bool emitArrayInit() {
|
// Avoid elaborate array initializers.
|
uint64_t p = pow(array_size_, array_dim_);
|
if (p > 20) {
|
return emitAssignment(); // fall back
|
}
|
|
fputs("{\n", out_);
|
|
indentation_ += 2;
|
emitIndentation();
|
emitType(array_type_);
|
for (uint32_t i = 0; i < array_dim_; i++) {
|
fputs("[]", out_);
|
}
|
fputs(" tmp = ", out_);
|
emitArrayInitDim(array_dim_);
|
fputs(";\n", out_);
|
|
emitIndentation();
|
fputs("mArray = tmp;\n", out_);
|
|
indentation_ -= 2;
|
emitIndentation();
|
fputs("}\n", out_);
|
return true;
|
}
|
|
// 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
|
}
|
|
bool isWhile = random1(2) == 1;
|
fputs("{\n", out_);
|
indentation_ += 2;
|
emitIndentation();
|
fprintf(out_, "int i%u = %d;\n", 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;
|
}
|
|
bool emitTry() {
|
fputs("try {\n", out_);
|
indentation_ += 2;
|
bool mayFollow = emitStatementList();
|
indentation_ -= 2;
|
emitIndentation();
|
fputc('}', out_);
|
return mayFollow;
|
}
|
|
bool emitCatch() {
|
uint32_t count = random1(countof(kExceptionTypes));
|
bool mayFollow = false;
|
for (uint32_t i = 0; i < count; ++i) {
|
fprintf(out_, " catch (%s ex%u_%u) {\n", kExceptionTypes[i], try_nest_, i);
|
indentation_ += 2;
|
mayFollow |= emitStatementList();
|
indentation_ -= 2;
|
emitIndentation();
|
fputc('}', out_);
|
}
|
return mayFollow;
|
}
|
|
bool emitFinally() {
|
fputs(" finally {\n", out_);
|
indentation_ += 2;
|
bool mayFollow = emitStatementList();
|
indentation_ -= 2;
|
emitIndentation();
|
fputc('}', out_);
|
return mayFollow;
|
}
|
|
// Emit a try-catch-finally block.
|
bool emitTryCatchFinally() {
|
// Apply a hard limit on the number of catch blocks. This is for
|
// javac which fails if blocks within try-catch-finally are too
|
// large (much less than you'd expect).
|
if (try_nest_ > fuzz_try_nest_) {
|
return emitAssignment(); // fall back
|
}
|
|
++try_nest_; // Entering try-catch-finally
|
|
bool mayFollow = emitTry();
|
switch (random0(3)) {
|
case 0: // try..catch
|
mayFollow |= emitCatch();
|
break;
|
case 1: // try..finally
|
mayFollow &= emitFinally();
|
break;
|
case 2: // try..catch..finally
|
// When determining whether code may follow, we observe that a
|
// finally block always follows after try and catch
|
// block. Code may only follow if the finally block permits
|
// and either the try or catch block allows code to follow.
|
mayFollow = (mayFollow | emitCatch()) & emitFinally();
|
break;
|
}
|
fputc('\n', out_);
|
|
--try_nest_; // Leaving try-catch-finally
|
return mayFollow;
|
}
|
|
// 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_);
|
emitArrayIndex(); // restrict its range
|
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 %u: {\n", random0(array_size_));
|
} 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;
|
}
|
|
bool emitNopCall() {
|
fputs("nop();\n", out_);
|
return true;
|
}
|
|
// 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 emitArrayInit(); break;
|
case 6: return emitForLoop(); break;
|
case 7: return emitDoLoop(); break;
|
case 8: return emitIfStmt(); break;
|
case 9: return emitSwitch(); break;
|
case 10: return emitTryCatchFinally(); break;
|
case 11: return emitNopCall(); 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 interface and class declarations.
|
void emitClassDecls() {
|
in_inner_ = true;
|
fputs(" private interface X {\n", out_);
|
fputs(" int x();\n", out_);
|
fputs(" }\n\n", out_);
|
fputs(" private class A {\n", out_);
|
fputs(" public int a() {\n", out_);
|
fputs(" return ", out_);
|
emitExpression(kInt);
|
fputs(";\n }\n", out_);
|
fputs(" }\n\n", out_);
|
fputs(" private class B extends A implements X {\n", out_);
|
fputs(" public int a() {\n", out_);
|
fputs(" return super.a() + ", out_);
|
emitExpression(kInt);
|
fputs(";\n }\n", out_);
|
fputs(" public int x() {\n", out_);
|
fputs(" return ", out_);
|
emitExpression(kInt);
|
fputs(";\n }\n", out_);
|
fputs(" }\n\n", out_);
|
fputs(" private static class C implements X {\n", out_);
|
fputs(" public static int s() {\n", out_);
|
fputs(" return ", out_);
|
emitLiteral(kInt);
|
fputs(";\n }\n", out_);
|
fputs(" public int c() {\n", out_);
|
fputs(" return ", out_);
|
emitLiteral(kInt);
|
fputs(";\n }\n", out_);
|
fputs(" public int x() {\n", out_);
|
fputs(" return ", out_);
|
emitLiteral(kInt);
|
fputs(";\n }\n", out_);
|
fputs(" }\n\n", out_);
|
in_inner_ = false;
|
}
|
|
// Emit field declarations.
|
void emitFieldDecls() {
|
fputs(" private A mA = new B();\n", out_);
|
fputs(" private B mB = new B();\n", out_);
|
fputs(" private X mBX = new B();\n", out_);
|
fputs(" private C mC = new C();\n", out_);
|
fputs(" private X mCX = new C();\n\n", out_);
|
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 a static void method.
|
void emitStaticNopMethod() {
|
fputs(" public static void nop() {}\n\n", out_);
|
}
|
|
// Emit program header. Emit command line options in the comments.
|
void emitHeader() {
|
fputs("\n/**\n * AOSP JFuzz Tester.\n", out_);
|
fputs(" * Automatically generated program.\n", out_);
|
fprintf(out_,
|
" * jfuzz -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;
|
emitClassDecls();
|
emitFieldDecls();
|
emitArrayDecl();
|
emitTestConstructor();
|
emitTestMethod();
|
emitStaticNopMethod();
|
emitMainMethod();
|
indentation_ -= 2;
|
fputs("}\n\n", out_);
|
}
|
|
//
|
// Random integers.
|
//
|
|
// Return random integer.
|
int32_t random() {
|
return fuzz_random_engine_();
|
}
|
|
// 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_;
|
const uint32_t fuzz_try_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 try_nest_;
|
uint32_t boolean_local_;
|
uint32_t int_local_;
|
uint32_t long_local_;
|
uint32_t float_local_;
|
uint32_t double_local_;
|
bool in_inner_;
|
};
|
|
} // anonymous namespace
|
|
int32_t main(int32_t argc, char** argv) {
|
// Time-based seed.
|
struct timeval tp;
|
gettimeofday(&tp, nullptr);
|
|
// Defaults.
|
uint32_t seed = (tp.tv_sec * 1000000 + tp.tv_usec);
|
uint32_t expr_depth = 1;
|
uint32_t stmt_length = 8;
|
uint32_t if_nest = 2;
|
uint32_t loop_nest = 3;
|
uint32_t try_nest = 2;
|
|
// Parse options.
|
while (1) {
|
int32_t option = getopt(argc, argv, "s:d:l:i:n:vh");
|
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 't':
|
try_nest = strtoul(optarg, nullptr, 0);
|
break;
|
case 'v':
|
fprintf(stderr, "jfuzz version %s\n", VERSION);
|
return 0;
|
case 'h':
|
default:
|
fprintf(stderr,
|
"usage: %s [-s seed] "
|
"[-d expr-depth] [-l stmt-length] "
|
"[-i if-nest] [-n loop-nest] [-t try-nest] [-v] [-h]\n",
|
argv[0]);
|
return 1;
|
}
|
}
|
|
// Seed global random generator.
|
srand(seed);
|
|
// Generate fuzzed program.
|
JFuzz fuzz(stdout, seed, expr_depth, stmt_length, if_nest, loop_nest, try_nest);
|
fuzz.emitProgram();
|
return 0;
|
}
|
