5 ms·

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 in

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?

DSingularity 8y ago
Think 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 ago
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.
- 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 ago
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.
trishume 8y ago
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.
- gamozolabs 8y ago
  Bingo
  - TickleSteve 8y ago
    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.
    - dragontamer 8y ago
      > compiler gives you that information It seems like he's fuzzing machine code. So he doesn't have the original source code.
pcwalton 8y ago
Same way GPUs handle divergence. You mask off inapplicable lanes until control flow reconverges. That's why AVX-512 is essential: it contains mask registers that make this approach practical.
gamozolabs 8y ago
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).
- TickleSteve 8y ago
  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?
  - derefr 8y ago
    Crypto code, maybe?

DSingularity 8y ago

Think 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 ago

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.

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 ago

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.

trishume 8y ago

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.

gamozolabs 8y ago
Bingo
- TickleSteve 8y ago
  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.
  - dragontamer 8y ago
    > compiler gives you that information It seems like he's fuzzing machine code. So he doesn't have the original source code.

pcwalton 8y ago

Same way GPUs handle divergence. You mask off inapplicable lanes until control flow reconverges. That's why AVX-512 is essential: it contains mask registers that make this approach practical.

gamozolabs 8y ago

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

TickleSteve 8y ago
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?
- derefr 8y ago
  Crypto code, maybe?