6 ms·
Vectorized Emulation: fuzzing at 2 trillion instructions per second
- jacobush 8y agoI 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?
- Double_a_92 8y agoSame. 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
- pjc50 8y ago"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/ http://lcamtuf.coredump.cx/afl/
- aaaaaaaaaab 8y ago>The goal is to take standard applications and JIT them to their AVX-512 equivalent such that we can fuzz 16 VMs at a time per thread. What happens if the executable already contains AVX512 (or other SIMD) instructions? Though I guess you can rewrite them into their scalar equivalent first, and convert that into AVX512.
- pjc50 8y agoYou 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.
- gamozolabs 8y agoI 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.
- vnorilo 8y agoThe 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.
- DSingularity 8y agoYou 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.
- vnorilo 8y agoSure, but how does that not utterly destroy performance as the fork would probably lead to multiple sub-forks down the line.. or lane? :)
- DSingularity 8y agoWhen 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.
- OskarS 8y agoHe writes that he's using a special type of IL for this technique, presumably he forbids indirect jumps in it.
- gamozolabs 8y agoTechnically 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.
- vectorEQ 8y agoThis is really interesting. i'm looking forward to more blogs on the last few topics / chapters!
- mckirk 8y agoOkay, 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?
- sanxiyn 8y agoYou loop until all masks are zero.
- TickleSteve 8y ago....and different branches? i.e based in the outcome of that loop??
- munin 8y agoIt 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.
- karmajunkie 8y agoThis might possibly be the best analogy for this industry I've ever come across.
- jacobush 8y agoSoggy candy mixed with pulped paper and sawdust.
- gamozolabs 8y agoI'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.
- TickleSteve 8y agoI 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?
- DSingularity 8y agoThink VM like the java VM not VM like the AWS VM =) Here he is simply trying to fuzz faster by executing vectorized code instead.
- pjc50 8y agoI 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.
- TickleSteve 8y ago...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.
- buckminster 8y agoThe 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.
- trishume 8y agoI 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.
- rbanffy 8y ago> if you cheap out on RAM and buy used Phis you could probably get the same setup for $1k USD. I'd love to lay my hands on a cheap 72x5 Phi based workstations... But since Intel only sells those by the tray, I guess I'll have to wait until someone decommission a large supercomputer.
- rbanffy 8y agoI love to see the creative misuse of technology. We need more of that.
- lachlan-sneff 8y agoThis is insane. and awesome.
- mpartel 8y agoThis is supremely cool! The masking stuff reminds me of how branching works (or at least used to work) on GPUs, so I wonder, could all this be made to work on a GPU too?
- brian_herman__ 8y agoCool can this be in the next version of http://lcamtuf.coredump.cx/afl/ http://lcamtuf.coredump.cx/afl/?