<blockquote style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;" class="gmail_quote">The main downside is that I don't know why it is that finding bugs<br>should depend linearly on anything. is it really true that if run A
<br>explores 10 more blocks than run B then run A has a .10 better chance of<br>finding a bug in the program?</blockquote><div><br>I think the above is the crux of the problem. Despite lots of intuition on where the bugs are or how to find them, there hasn't been much analysis (to my knowledge) of modeling bug prediction. Clearly a lot of bugs occur where unchecked data is transferred into fixed sized buffers, but from a system perspective I've not seen anything quantifiable that suggests where bugs will be. For your weights a,b,c (or even the linear equation) you're right that we don't have metrics on what the best fit looks like.
<br><br>I think it would be interesting for an academic or two to put a lot of "small enough" programs through a lot of fuzzers. Fuzz almost all/most of the possible paths and then analyze the common traits to answer basic questions as to how diversity, coverage, and interesting functions relate to finding bugs. (to any professors out there: I haven't finished my masters yet and would love to find an interesting program). The cool research out there (Molnar, Aitel, DeMott, etc) seems to focus a lot on the feedback systems to find more bugs, but as of yet, I've seen no reason as to why any fitness function is well suited to the problem.
<br><br><br></div><br><br><div><span class="gmail_quote">On 10/16/07, <b class="gmail_sendername">David Molnar</b> <<a href="mailto:dmolnar@eecs.berkeley.edu">dmolnar@eecs.berkeley.edu</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
On Mon, 2007-10-15 at 21:38 -0700, J.M. Seitz wrote:<br><br>> So, let's try this:<br>><br>> spankage = code coverage + (path diversity weight * 2) + (num<br>> interesting funcs hit * 5)<br>><br>> This stems from many talks with Jared, Pedram, and Charlie. I also
<br>> proposed that a proximity value to dangerous functions be thrown in, but<br>> let's not get too far ahead of ourselves.<br><br>Cool, this is interesting. I wonder if you could also flip it around and<br>try to estimate the values of those coefficients instead of picking "2"
<br>and "5". I don't think those are bad values, just it'd be interesting if<br>there is a way to derive them somehow from data about which fuzzing runs<br>have been successful so far.<br><br>One way this could work is as follows: suppose we have a set of fuzzing
<br>runs R_1, R_2,...,R_n, and suppose for each run we know whether the run<br>found a bug or not. Let's define Y_i to be 1 if the run R_i found at<br>least one bug and Y_i to be 0 otherwise. Then we could set up a linear
<br>model:<br><br>Y_i = a + b*coverage_i + c*path diversity_i + d*num int.funcs_i +error_i<br><br>This just says we think whether a bug is found on run i depends linearly<br>on coverage, path diversity, and number of interesting functions, plus
<br>an "intercept term" a and an error term. In your equation above for<br>"spankage", we have a = 0, b = 1, c = 2, d =5.<br><br>The error represents among other things the effect of all the other<br>variables we did not measure. Like, there's no variable in this equation
<br>for "did the developers do a lot of threat modeling," so if that has a<br>lot of impact on whether a specific run finds a bug, then we will see<br>that as "error" in estimating how important coverage, path diversity,
<br>and #interesting functions is to finding a bug. The error can also<br>account for things like randomization in the fuzzer, difficulty in<br>measuring path diversity, and so on.<br><br>The main point is that if we assume this model holds we can then
<br>estimate values for a,b,c, and d from the data using any of several<br>methods. For example, if we believe the errors are independent of the<br>other variables, and if we believe the errors have a mean value of 0,<br>
then we can use ordinary least squares regression. We can then look at<br>the resulting estimates for a,b,c, and d to give us some idea of whether<br>coverage, path diversity, and number of interesting functions in fact<br>
have an impact on finding bugs. Finally, we could feed the resulting<br>estimates back into your Fuzzing Proxy Coverage Spanker-abob.<br><br>The main downside is that I don't know why it is that finding bugs<br>should depend linearly on anything. is it really true that if run A
<br>explores 10 more blocks than run B then run A has a .10 better chance of<br>finding a bug in the program? Mainly this came to mind because I'm just<br>learning about linear regressions now and have to read dozens of papers
<br>where people run, like, regressions of computer use vs. wages and<br>compare them to regressions of pencil use vs. wages to see whether<br>computers or pencils better predict high wages. Still, it seems like we<br>should be able to leverage the data generated on which fuzzer runs
<br>produce bugs and which do not.<br><br>-David Molnar<br><br></blockquote></div><br><br clear="all"><br>-- <br>Matthew Wollenweber<br><a href="mailto:mwollenweber@gmail.com">mwollenweber@gmail.com</a> | <a href="mailto:mjw@cyberwart.com">
mjw@cyberwart.com</a><br><a href="http://www.cyberwart.com">www.cyberwart.com</a>