It would be cool to see an evaluation of this against baseline. Software is a giant warehouse filled with soggy pinatas. Swing any kind of bat in there and you'll get some candy.
I'll try to do a blog on this specific aspect. It can be hard to apples to apples with other fuzzers and toolings but I can give it a try.
This tooling is specifically designed for "hard" targets, while "hard" is subjective, think targets with fewer than 2 CVEs a year. Where getting even a null deref is hard.
I have used this on some soft targets and it's just as if you ran AFL against it, candy everywhere. The upside is that this tool usually "finishes" in an hour (no more coverage, no more crashes). Making it a bit easier to develop mutators/generators as you can run them to completion faster and have a more effective development cycle.
I may be getting this wrong... but how can this possibly work?
Correct me if I'm wrong, but he's trying to emulate 16 systems in parallel by vectorizing the instructions.
Ok, but this assumes that all paths are identical. Once you start fuzzing by varying their input, the paths will all vary at which point you're down to 16 non-identical paths again.
The whole point of fuzzing is to expose the different paths and this would fail horribly for that, surely?
trishume hits the nail on the head here. The mutation strategy is well aware of how this system works.
Each core gets a completely unique fuzz case, where each lane of the vector gets a small mutation. In _many_ cases this mutation doesn't even affect flow (eg, the mutated parts are skipped over or never parsed due to errors). Meaning all 16 run to completion. What's really important here is that when the small modification you made to an individual lane does actually cause it to diverge, you now know where and when that part of the input is used in the program. This information is huge and can be used to tweak weights and other parameters of mutators/generators, making them learn which fields to use when and how often.
With some better logic (covered in a later blog) I'll talk more about handling fully divergent cases by having graph analysis to find post dominators in functions and run VMs until they can sync up. Rather than the current model of "sync if you can", this will be a smart forward-looking sync that will ensure that by the end of every function all VMs will be running again (even if that means I have to insert artifical post dominator nodes to graphs).
What kind of application are you running such that you don't get large path differences based on the input?
All fuzzing I have done (with AFL and the like) the paths vary wildly and will end up in completely different parts of the stack.
Surely the advantage you're gaining by parallelising is completely wiped out when you lose sync (which to me must be most of the time).
I just can't see how you can possibly keep sync between parallel runs in anything but the most trivial application-under-test.
To me, it seems that this will necessarily degrade to a single path being active. Have you done any analysis on how many paths are active simultaneously over a non-trivial run?
I bet his mutation strategy works in tandem with the SIMD strategy. Probably the input for each SIMD lane differs by only one byte or something so that they are maximally coherent.
So what you're really doing is (in parallel) finding the decoherence points... These branching/decision points are much more easily found by instrumenting the code as in AFL.
No need to parallelise at all, the compiler gives you that information.
What you have seems like a neat trick, but not an efficient way of actually fuzzing.
I wondered about that too, but the author points out that the VMs can re-converge: if you have one that does 5 times round a loop and another that does 10, they end up resynchronised.
Any kind of software with a message or input processing loop will naturally re-converge at the top of the loop. It's quite neat.
...but during that one iteration of the loop, the paths will diverge wildly.
In a typical message handling loop, the big-switch will immediately jump off to separate message-handling code, immediately wiping out the possibility of parallelisation.
The point isn't just to execute 16 VMs at the same time. The point is to quickly identify when different executions diverge so you know which inputs lead to different paths.
Technically right now if they have AVX instructions my lifter screams at me and tells me to not be lazy and implement those instructions ;)
However if I were to lift AVX instructions I would lift them to their scalar counterparts in my IL (eg. by emitting 16 32-bit operations). Lets say there are 16 `vpaddd`s in a row, thus creating a 16x16 matrix, when I lift it I'd lift these adds to 128 individual adds, and then generate 128 `vpaddd`s. While I'm doing 16x more the `vpaddd`s I'm also running 16x more VMs than the application originally had, thus it cancels out, and the net effect is that I'm still running `vpaddd`s as fast as the CPU can execute them. Technically in this case my stuff might even be faster as it's going to be 128 adds instead of 16, which means the CPU is running based on instruction throughput longer and decoding the same instruction and keeping latencies down.
However it's possible that this transposition of the matrix might increase dependencies between instructions or something of the sorts which might slow down performance.
That being said, AVX is pretty much only used for memory loads and stores in string operations in most programs anyways, so it doesn't matter much.
You could also set the processor capability bits in the VM to pretend the processor is an older one, which will generally cause the application to fallback to a compatible piece of code. It's pretty rare in non-maths-heavy code.
I do this as much as possible. I even go out of my way to compile things if I have access to source with a weaker version of x86, or even cross compile it for something like MIPS.
This is done however not due to a theoretical limitation of the tooling, but rather a practical one in that I haven't written SSE lifters and decoders yet. If I were to write these it would work just fine.
The real problem is when different VMs branch differently. You essentially have to run both sides of a branch in serial with masked lanes. The author mentions this and states that the method works only because the VMs are very deterministic. I don't understand how he deals with indirect jumps.
You mean the possibility that the branch target is different on the different VMs? He can fork the vectorization if the targets diverge. I’m not sure what he does though.
When you are fuzzing the ultimate goal is to explore as much as you can of the entire search space. Forks cant hurt performance. They are just another potential execution path to be vectorized.
I don't know what this is except that it's something about optimization or bug finding or both and that it's wonderfully weird. How often do you see someone use up 96 gigs of RAM and rewrite instructions to AVX512, use a virtual MMU?
Same. I have no idea what I just read. It's probably one of those things that only make sense if you already understand them. cough math topics on Wikipedia cough
"Fuzzing" is the technique for finding bugs by varying the inputs of a program and looking at how this affects code paths. A simpler place to start would be http://lcamtuf.coredump.cx/afl/
Okay, I get the idea with kmasks for branching. But what about loops, where one VM would still have to continue the loop and the others would have to leave it?
