Random-walk fuzzer for the Dart VM.

runtime/tests/vm/dart/random_walk_fuzzer.dart

+// Copyright (c) 2015, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+// Random-walk fuzzer for the Dart VM.
+//
+// Start with all the classes and libraries and various interesting values.
+// Repeatedly choose one as a receiver, construct a message it is likely to
+// understand, send the message, and add the result.
+//
+// Intentionally not run on the build bots because through dart:io it could
+// trash their setups.
+
+library fuzzer;
+
+import 'dart:io';
+import 'dart:math';
+import 'dart:mirrors';
+import 'dart:typed_data';
+
+var blacklist = [
+  'dart.io.exit',
+  'dart.io.exitCode',
+  'dart.io.sleep',
+  'dart.io.Process.killPid',
+];
+
+final bool trace = false;
+
+void main(List<String> args) {
+  int seed;
+  if (args.length == 1) {
+    seed = int.parse(args[0]);
+  } else {
+    // Dart's built-in random number generator doesn't provide access to the
+    // seed when it is choosen by the implementation. We need to be able to
+    // report this seed to make runs of the fuzzer reproducible, so we create
+    // the seed ourselves.
+
+    // When running on many machines in parallel, the current time alone
+    // is a poor choice of seed.
+    seed = 0;
+    try {
+      var f = new File("/dev/urandom").openSync();
+      seed = (seed << 8) | f.readByteSync();
+      seed = (seed << 8) | f.readByteSync();
+      seed = (seed << 8) | f.readByteSync();
+      seed = (seed << 8) | f.readByteSync();
+      f.close();
+    } catch(e) {
+      print("Failed to read from /dev/urandom: $e");
+    }
+
+    seed ^= new DateTime.now().millisecondsSinceEpoch;
+    seed &= 0xFFFFFFFF;
+  }
+  random = new Random(seed);
+
+  // Information needed to reproduce this run.
+  print("Dart VM fuzzer");
+  print("Executable: ${Platform.executable}");
+  print("Arguments: ${Platform.executableArguments}");
+  print("Version: ${Platform.version}");
+  print("Seed: ${seed}");
+  print("------------------------------------------");
+
+  setupInterestingValues();
+  setupClasses();
+
+  // Bound the number of steps in our random walk so that if any issue is found
+  // it can be reproduced without having to wait too long.
+  for (int i = 0; i < 100000; i++) {
+    fuzz(randomElementOf(candidateReceivers));
+    if (maybe(0.01)) garbageCollect();
+  }
+}
+
+Random random;
+
+bool maybe(probability) => random.nextDouble() < probability;
+
+randomElementOf(list) {
+  return list.length == 0 ? null : list[random.nextInt(list.length)];
+}
+
+class Candidate<T> {
+  Candidate origin;
+  String message;
+  T mirror;
+  trace() {
+    if (origin == null) {
+      print("");
+    } else {
+      origin.trace();
+      print(" $message");
+    }
+    print(mirror);
+  }
+}
+
+List<Candidate<ObjectMirror>> candidateReceivers =
+    new List<Candidate<ObjectMirror>>();
+List<Candidate<InstanceMirror>> candidateArguments =
+    new List<Candidate<InstanceMirror>>();
+
+void addInstance(var instance) {
+  addInstanceMirror(reflect(instance));
+}
+
+void addInstanceMirror(InstanceMirror mirror,
+                       [Candidate origin, String message]) {
+  var c = new Candidate<InstanceMirror>();
+  c.mirror = mirror;
+  c.origin = origin;
+  c.message = message;
+
+  candidateReceivers.add(c);
+  candidateArguments.add(c);
+}
+
+void addObjectMirror(ObjectMirror mirror) {
+  var c = new Candidate<ObjectMirror>();
+  c.mirror = mirror;
+  c.origin = null;
+  c.message = null;
+
+  candidateReceivers.add(c);
+}
+
+void setupInterestingValues() {
+  addInstance(null);
+  addInstance(true);
+  addInstance(false);
+
+  addInstance([]);
+  addInstance(const []);
+  addInstance({});
+  addInstance(const {});
+
+  addInstance(() => null);
+
+  addInstance(-1);
+  addInstance(0);
+  addInstance(1);
+  addInstance(2);
+
+  addInstance(1 << 31);
+  addInstance(1 << 31 + 1);
+  addInstance(1 << 31 - 1);
+
+  addInstance(1 << 32);
+  addInstance(1 << 32 + 1);
+  addInstance(1 << 32 - 1);
+
+  addInstance(1 << 63);
+  addInstance(1 << 63 + 1);
+  addInstance(1 << 63 - 1);
+
+  addInstance(1 << 64);
+  addInstance(1 << 64 + 1);
+  addInstance(1 << 64 - 1);
+
+  addInstance(-1.0);
+  addInstance(0.0);
+  addInstance(1.0);
+  addInstance(2.0);
+  addInstance(double.NAN);
+  addInstance(double.INFINITY);
+  addInstance(double.NEGATIVE_INFINITY);
+  addInstance(double.MIN_POSITIVE);
+  addInstance(double.MAX_FINITE);
+
+  addInstance("foo");  // ASCII string
+  addInstance("blåbærgrød");  // Latin1 string
+  addInstance("Îñţérñåţîöñåļîžåţîờñ");  // Unicode string
+  addInstance("𝄞");  // Surrogate pairs
+  addInstance("𝄞"[0]);  // Surrogate pairs
+  addInstance("𝄞"[1]);  // Surrogate pairs
+  addInstance("\u{0}");  // Non-printing charater
+  addInstance("\u{1}");  // Non-printing charater
+  addInstance("f\u{0}oo");  // Internal NUL
+  addInstance("blåbæ\u{0}rgrød");  // Internal NUL
+  addInstance("Îñţérñåţîö\u{0}ñåļîžåţîờñ");  // Internal NUL
+  addInstance("\u{0}𝄞");  // Internal NUL
+
+  for (int len = 0; len < 8; len++) {
+    addInstance(fillInt(new Int8List(len)));
+    addInstance(fillInt(new Int16List(len)));
+    addInstance(fillInt(new Int32List(len)));
+    addInstance(fillInt(new Int64List(len)));
+    addInstance(fillInt(new Uint8List(len)));
+    addInstance(fillInt(new Uint16List(len)));
+    addInstance(fillInt(new Uint32List(len)));
+    addInstance(fillInt(new Uint64List(len)));
+    addInstance(fillFloat(new Float32List(len)));
+    addInstance(fillFloat(new Float64List(len)));
+  }
+
+  randomInstance(ignore) {
+    return randomElementOf(candidateArguments).mirror.reflectee;
+  }
+  for (int len = 0; len < 8; len++) {
+    addInstance(new List.generate(len, randomInstance));
+  }
+}
+
+void fillInt(TypedData d) {
+  for (var i = 0; i < d.length; i++) {
+    d[i] = random.nextInt(0xFFFFFFFF);
+  }
+}
+
+void fillFloat(TypedData d) {
+  for (var i = 0; i < d.length; i++) {
+    d[i] = random.nextDouble();
+  }
+}
+
+void setupClasses() {
+  currentMirrorSystem().libraries.values.forEach((lib) {
+    if (lib.simpleName == #fuzzer) return;  // Don't recurse.
+    addObjectMirror(lib);
+    lib.declarations.values.forEach((decl) {
+      if (decl is ClassMirror) {
+        addObjectMirror(decl);
+      }
+    });
+  });
+}
+
+MethodMirror randomMethodOf(receiver) {
+  if (receiver is ClassMirror) {
+    return randomElementOf(receiver.declarations.values.where(
+        (d) => d is MethodMirror && d.isStatic).toList());
+  } else if (receiver is LibraryMirror) {
+    return randomElementOf(receiver.declarations.values.where(
+        (d) => d is MethodMirror).toList());
+  } else if (receiver is InstanceMirror) {
+    var methods = [];
+    var cls = receiver.type;
+    while (cls != reflectClass(Object)) {
+      cls.declarations.values.forEach((d) {
+        if (d is MethodMirror && !d.isStatic) methods.add(d);
+      });
+      cls = cls.superclass;
+    }
+    return randomElementOf(methods);
+  }
+  throw new Error("UNREACHABLE");
+}
+
+String prettyMessageName(receiver, method) {
+  var r = "?", m = "?";
+  if (receiver is InstanceMirror) {
+    r = MirrorSystem.getName(receiver.type.simpleName);
+  } else if (receiver is ClassMirror) {
+    r = MirrorSystem.getName(receiver.simpleName);
+    r = "$r class";
+  } else if (receiver is LibraryMirror) {
+    r = MirrorSystem.getName(receiver.simpleName);
+    r = "$r lib";
+  }
+  m = MirrorSystem.getName(method.simpleName);
+  return "$r>>#$m";
+}
+
+void fuzz(Candidate c) {
+  ObjectMirror receiver = c.mirror;
+  MethodMirror method = randomMethodOf(receiver);
+  if (method == null) return;
+  if (blacklist.contains(MirrorSystem.getName(method.qualifiedName))) return;
+
+  List positional = randomPositionalArgumentsFor(method);
+  Map named = randomNamedArgumentsFor(method);
+  InstanceMirror result;
+
+  String message = prettyMessageName(receiver, method);
+  if (trace) {
+    c.trace();
+    print(message);
+  }
+
+  if (method.isConstructor) {
+    try {
+      result = receiver.newInstance(method.simpleName, positional, named);
+    } catch(e) {}
+  } else if (method.isRegularMethod) {
+    try {
+      result = receiver.invoke(method.simpleName, positional, named);
+    } catch(e) {}
+  } else if (method.isGetter) {
+    try {
+      result = receiver.getField(method.simpleName);
+    } catch(e) {}
+  } else if (method.isSetter) {
+    try {
+      result = receiver.setField(method.simpleName, positional[0]);
+    } catch(e) {}
+  }
+
+  if (result != null) {
+    addInstanceMirror(result, c, message);
+  }
+}
+
+InstanceMirror randomArgumentWithBias(TypeMirror bias) {
+  if (maybe(0.75)) {
+    for (var candidate in candidateArguments) {
+      if (candidate.mirror.type.isAssignableTo(bias)) {
+        return candidate.mirror;
+      }
+    }
+  }
+  return randomElementOf(candidateArguments).mirror;
+}
+
+List randomPositionalArgumentsFor(MethodMirror method) {
+  var result = [];
+  for (int i = 0; i < method.parameters.length; i++) {
+    ParameterMirror p = method.parameters[i];
+    if (!p.isNamed && (!p.isOptional || maybe(0.5))) {
+      result.add(randomArgumentWithBias(p.type));
+    }
+  }
+  return result;
+}
+
+Map randomNamedArgumentsFor(MethodMirror method) {
+  var result = {};
+  for (int i = 0; i < method.parameters.length; i++) {
+    ParameterMirror p = method.parameters[i];
+    if (p.isNamed && maybe(0.5)) {
+      result[p.simpleName] = randomArgumentWithBias(p.type);
+    }
+  }
+
+  return result;
+}
+
+void garbageCollect() {
+  // Chain a bunch of moderately sized arrays, then let go of them. Using a
+  // moderate size avoids our allocations going directly to a large object 
+  // page in old space.
+  var n;
+  for (int i = 0; i < 2048; i++) {
+    var m = new List(512);
+    m[0] = n;
+    n = m;
+  }
+}