Fuzzing

[joshbw]

Microsoft has a "fuzzing as a service" (https://www.microsoft.com/en-us/security-risk-detection/). I've chased down resources to offer it for free to open source projects, similar to Google's efforts. As Google and MS use different fuzzing mutators there is utility in using both (internally we have found that eventually you exhaust the findings from one fuzzing algorithm, but that switching algorithms will uncover new findings; conceivably someone could invent a fuzzing algorithm that does superset the output of many existing algorithms, but nobody has fully done that yet)

Fuzzing provides the most utility when applied to unmanaged (i.e. c/c++) parsers, though can find potential DoS and fault scenarios in managed parsers as well. As I'm not anywhere as familiar with all of the pieces of the Node.js code base as I would like, can folks point me to parts of the codebase that would be good targets for fuzzing, and I'll get it set up.

We (MS) are still working on streamlining the process on our side, but we hope to get things configured such that we automatically pick up new commits to the codebase and run until we hit some threshold (given that we hope to do this for a ton of open source parsers, that threshold will probably be around 1m iterations without a fault per fuzzing algorithm, on the most recent commit; 1m iterations without a fault isn't a guaranty that the 1,000,001th iteration won't find a fault, but it does suggest that there are diminishing returns for additional passes where CPU cycles could be better spent hitting other code. )

[vdeturckheim]

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

[sam-github]

@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.

[evilpacket]

@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.

[joshbw]

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

[jlamendo]

@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.

[vdeturckheim]

Has there been any update on that topic?

[Trott]

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

Although take note of SBULeeLab/NodeFz#1

/cc @davisjam

[davisjam]

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.

[sam-github]

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

[sam-github]

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.

[sam-github]

Appears to be superceeded by #435