4 ms·

The problem is that the search space grows (exponentially?) as you increase the fuzzer’s limit. So there’s a cost, and likely diminishing returns, to raising th

The problem is that the search space grows (exponentially?) as you increase the fuzzer’s limit. So there’s a cost, and likely diminishing returns, to raising that limit.

jandrese 5y ago
Are they checking every possible overflow up to the max? Like no overflow at 7377 bytes, lets try 7378... While I can see targeting near natural boundaries (1025 bytes for example), you should be able to skip over most of the search space and verify that it doesn't blow up on enormous values like 16777216 bytes.
- lucb1e 5y ago
  It's not that simple though. Single-variable integer overflows can be checked like that, but when the critical byte in a buffer might be at positions 1 through {bufferlength}, you have to do a shotgun approach and see if anything sticks, and at some point the number of possible combinations grows too big even for that. I'm not an expert on fuzzing myself, but generally I do see the point of having a limit here. Why, then, that limit was not chosen to be the max size for each of the length-checked inputs, I don't know. That does seem a bit more obvious, but also I just read this article so I can't prove that I wouldn't have made the same mistake.
UncleMeat 5y ago
Coverage-guided fuzzing dramatically mitigates the exponential nature of the search space. It used to be that searching for magic bits was impossible with fuzzing but now it is nearly trivial.
moring 5y ago
Is it possible to feed a fuzzer with information from static analysis to limit the search space? Such as, if you have a check like "someParameter > 0" in the code, have the fuzzer generate a positive, negative, and zero value for someParameter, but not thousands of them -- at least not based on this check alone -- because they will all behave the same.
- baby 5y ago
  There's whitebox fuzzing that's starting to become a thing, when your fuzzer gets stuck you give the non-giving corpus to an SMT solver and it'll try to see if there exists an input that could uncover a new path. I'm really excited about these but haven't really followed the advances.

The problem is that the search space grows (exponentially?) as you increase the fuzzer’s limit. So there’s a cost, and likely diminishing returns, to raising that limit.

jandrese 5y ago

Are they checking every possible overflow up to the max? Like no overflow at 7377 bytes, lets try 7378... While I can see targeting near natural boundaries (1025 bytes for example), you should be able to skip over most of the search space and verify that it doesn't blow up on enormous values like 16777216 bytes.

lucb1e 5y ago
It's not that simple though. Single-variable integer overflows can be checked like that, but when the critical byte in a buffer might be at positions 1 through {bufferlength}, you have to do a shotgun approach and see if anything sticks, and at some point the number of possible combinations grows too big even for that. I'm not an expert on fuzzing myself, but generally I do see the point of having a limit here. Why, then, that limit was not chosen to be the max size for each of the length-checked inputs, I don't know. That does seem a bit more obvious, but also I just read this article so I can't prove that I wouldn't have made the same mistake.

UncleMeat 5y ago

Coverage-guided fuzzing dramatically mitigates the exponential nature of the search space. It used to be that searching for magic bits was impossible with fuzzing but now it is nearly trivial.

moring 5y ago

Is it possible to feed a fuzzer with information from static analysis to limit the search space? Such as, if you have a check like "someParameter > 0" in the code, have the fuzzer generate a positive, negative, and zero value for someParameter, but not thousands of them -- at least not based on this check alone -- because they will all behave the same.

baby 5y ago
There's whitebox fuzzing that's starting to become a thing, when your fuzzer gets stuck you give the non-giving corpus to an SMT solver and it'll try to see if there exists an input that could uncover a new path. I'm really excited about these but haven't really followed the advances.