Kinds of fuzz testing

At the risk of belaboring the obvious, I'd like to draw a distinction between two different, complementary, kinds of fuzzing: external and internal.

1. External fuzzing explores the input space trying to ensure code coverage. This is what AFL and friends do. At a high level, these tools try to identify interesting input that drives execution over new paths. External fuzzing is obviously useful for any non-trivial application.
2. Internal fuzzing (schedule fuzzing) explores the execution space to ensure correctness under various schedule interleavings. Internal fuzzing is appropriate when the system under test has inherent non-determinism, i.e. when a system might behave differently on the same input. These variations in behavior might be due to race conditions or algorithmic randomness.

To my mind the two techniques are entirely complementary. Identifying interesting inputs is a job for external fuzzing. Ensuring relatively complete code coverage for a given input is a job for internal fuzzing.

Node.fz

Summary

Node.fz is an internal fuzzing (schedule fuzzing) tool. It exaggerates the most prominent form of non-determinism in Node.js: asynchrony, i.e. the order in which pending events are handled by the event loop and the worker pool. Doing this only requires changes in libuv.

Some care needs to be taken to ensure that the alternative schedules are legal from the Node and libuv specifications, both explicit and implicit. For example, IIRC Node doesn't actually guarantee timer ordering, but a lot of Node core and application code depend on this behavior anyway.

Current implementation

I developed it on libuv v1.7.4 (Node 0.12.7 up to 4.X) and it would need to be ported for newer versions of node. The code works for Linux, though it was a bit of a rush job.

Extra stuff

Node.fz does not explore the re-ordering of independent promise chains. This would be an interesting addition, although it would require extending modifications into the Node.js (and possibly V8?) codebase.

Additional reading

1. The Node.fz paper is available here. Section 3 is a bug study; Node.js experts should be able to skip ahead to sections 4 and 5 for the details on Node.fz.
2. Kaushik Sen at UC Berkeley has done a lot of work on measuring the effectiveness of systematic or randomized (fuzzy) schedule exploration. Other prominent researchers in this space are Shaz Qadeer and Madan Musuvathi of Microsoft.

from security-wg.

@joshbw Fuzz testing would be great. The http_parser would probably be highest value, easiest to build a driver for. It has a programmatic C API, https://github.com/nodejs/node/tree/master/deps/http_parser, and can also be reached implicitly by writing a simple node HTTP server.

from security-wg.

@joshgav do you want to have that on the agenda on next meeting on Thursday? (#52 )

from security-wg.

@joshbw @jlamendo spent a bunch of the http_parser fuzzing it using AFL. Might be good to know what perspective / tactics he took so that we might try something different.

from security-wg.

Thanks - I was away on vacation for a bit, but getting moving on this now. I'll ping @jlamendo

from security-wg.

@joshbw Sorry about the long delay in getting back to you - I don't check github notifications as often as I should. I primarily used AFL's persistent mode. It's similar to llvm-fuzz in that it does multiple input parses without requiring the application to completely exit and restart. I did around 20M iterations, didn't see a single crash ( even a non-security impacting one! ). I also reviewed it manually. After that, my gut says that further fuzzing there is unlikely to be fruitful. One thing to note - I fuzzed http_parser with a standalone harness, and didn't hit anything involving the way http_parser is integrated into node itself.

The things I'd like to fuzz but haven't really had the time to setup are primarily c-ares/DNS and internationalization.

from security-wg.

Has there been any update on that topic?

from security-wg.

Possibly relevant/useful prior art?: https://github.com/VTLeeLab/NodeFz

Although take note of SBULeeLab/NodeFz#1

/cc @davisjam

from security-wg.

@joshbw should this stay open? are you still planning on implementing MS fuzzing as a service?

from security-wg.

Actually, I will just close this for now, but if anyone wants to contribute any fuzzing, please do so. And ping me if I misunderstand and this issue needs to be reopened.

from security-wg.

Appears to be superceeded by #435

from security-wg.