Random-walk fuzzer for the Dart VM.

fuzzer.dart

Index: fuzzer.dart
diff --git a/fuzzer.dart b/fuzzer.dart
new file mode 100644
index 0000000000000000000000000000000000000000..1b436dabdaf16408bfe1451500d322a2cd19cf74
--- /dev/null
+++ b/fuzzer.dart
@@ -0,0 +1,200 @@
+library fuzzer;
+
+import 'dart:io';
+import 'dart:math';
+import 'dart:mirrors';
+
+void main([List<String> args]) {
+  int seed;
+  if (args.length == 1) {
+    seed = int.parse(args[0]);
+  } else {
+    seed = new DateTime.now().millisecondsSinceEpoch & ((1<<31)-1);

[groebert, 2015/01/16 09:55:16]

If we execute on multiple machines at the same time, milliseconds will not be a
good source for the seed. Maybe also mix in /dev/urandom?

[rmacnak, 2015/02/05 00:38:28]

Added

+  }
+  random = new Random(seed);
+
+  print("Dart VM fuzzer");
+  print("Executable: ${Platform.executable}");
+  print("Arguments: ${Platform.executableArguments}");
+  print("Version: ${Platform.version}");
+  print("Seed: ${seed}");
+
+  setupInterestingValues();
+  setupClasses();
+
+  while(true) {

[groebert, 2015/01/16 09:55:16]

Better use a pre-defined maximum number of iterations, for example 5M. That way,
you can restart the VM several times with new seeds but won't have to wait too
long to reproduce a bug with a given seed.

[rmacnak, 2015/02/05 00:38:28]

Bounded

+    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)];
+}
+
+List<ObjectMirror> candidateReceivers = new List<ObjectMirror>();
+List<InstanceMirror> candidateArguments = new List<InstanceMirror>();
+
+void addInstance(var i) {
+  var mirror = reflect(i);
+  candidateReceivers.add(mirror);
+  candidateArguments.add(mirror);
+}
+
+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
+
+  // TODO: Lists and maps of these values.

[rmacnak, 2015/02/05 00:38:28]

Implemented.

+  // TODO: TypedData.
+}
+
+void setupClasses() {
+  currentMirrorSystem().libraries.values.forEach((lib) {
+    candidateReceivers.add(lib);
+    lib.declarations.values.forEach((decl) {
+      if (decl is ClassMirror) {
+        candidateReceivers.add(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");
+}
+
+void fuzz(ObjectMirror receiver) {
+  MethodMirror method = randomMethodOf(receiver);
+  if (method == null) return;
+  List positional = randomPositionalArgumentsFor(method);
+  Map named = randomNamedArgumentsFor(method);
+  InstanceMirror result;
+
+  print("$receiver >> ${method.simpleName}");
+
+  if (method.isConstructor) {

[groebert, 2015/01/16 09:55:16]

Maybe also add a blacklist of known-bad classes/methods so they're skipped
during fuzzing. This could also check that we're not fuzzing anything from the
package fuzzer.

[rmacnak, 2015/02/05 00:38:28]

Excluded the fuzzer itself and a few functions from dart:io.

+    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) {
+    addInstance(result);
+  }
+}
+
+
+InstanceMirror randomArgumentWithBias(TypeMirror bias) {
+  if (maybe(0.75)) {
+    for (var candidate in candidateArguments) {
+      if (candidate.type.isAssignableTo(bias)) {
+        return candidate;
+      }
+    }
+  }
+  return randomElementOf(candidateArguments);
+}
+
+List randomPositionalArgumentsFor(MethodMirror method) {
+  var arity = method.parameters.length;
+  var args = new List(arity);
+  for (int i = 0; i < arity; i++) {
+    args[i] = randomArgumentWithBias(method.parameters[i].type);
+  }
+  return args;
+}
+
+Map randomNamedArgumentsFor(MethodMirror method) {
+  // TODO: Implement.

[rmacnak, 2015/02/05 00:38:28]

Implemented.

+  return null;
+}
+
+void garbageCollect() {
+  // TODO: Chain a bunch of moderately sized arrays, then let go of them.

[rmacnak, 2015/02/05 00:38:28]

Implemented.

+}