5

Fuzzing, per a current Wikipedia definition is defined the following way:

Fuzzing or fuzz testing is an automated software testing technique that involves providing invalid, unexpected, or random data as inputs to a computer program. The program is then monitored for exceptions such as crashes, failing built-in code assertions, or potential memory leaks. Typically, fuzzers are used to test programs that take structured inputs.

https://en.wikipedia.org/wiki/Fuzzing

Symbolic execution, by contrast, is defined the following way, also pulling from Wikipedia:

In computer science, symbolic execution (also symbolic evaluation) is a means of analyzing a program to determine what inputs cause each part of a program to execute. An interpreter follows the program, assuming symbolic values for inputs rather than obtaining actual inputs as normal execution of the program would, a case of abstract interpretation.

https://en.wikipedia.org/wiki/Symbolic_execution

What I am trying to understand is the functional difference between these two methods. I see the line that says symbolic execution determines "what inputs cause each part of a program to execute," so you might differentiate each method by the "goal" a security researcher has in mind. Papers I have read recently differentiate symbolic execution from fuzzing by saying the former has significantly more overhead / runs more slowly.

From my perspective, symbolic execution utilizes a form of "targeted fuzzing" that specifically hits certain symbolic values. I've also heard it said that symbolic execution is just "more sophisticated fuzzing."

Can someone clarify what the real difference is between the two and why or when we should prefer one method over the other?

yaloner
  • 250
  • 1
  • 6
Bradley Evans
  • 275
  • 2
  • 6
  • Honestly, symbolic execution is, at the moment, a pie in the sky. It has a huge number of advantages, but is just too difficult to properly implement in such a way that you get high coverage. It's all very academic, and today, fuzzers are far more efficient than any implementation using symbolic execution (even though, in theory, symbolic execution is superior). Note also that symbolic execution may miss bugs in the language itself. – forest Nov 02 '18 at 01:22

2 Answers2

5

Can someone clarify what the real difference is between the two and why or when we should prefer one method over the other?

(Dynamic) symbolic execution is sometimes called whitebox fuzzing, see, e.g., SAGE. Fuzzing can be grouped into categories:

  • Blackbox fuzzing: doesn't require any information about the system under test (SUT). There are two strategies to generate input: generate from a grammar/model, or mutate from existing ones.
  • Whitebox fuzzing: require all the information about the SUT, including APIs, environment etc. It needs to know which instruction is executed, so that it can replace the semantics of the instruction with the symbolic semantics.
  • Greybox fuzzing: require to know a little information about the SUT, i.e. basic block transition. Currently it is the most successful, see, e.g., this trophy case.

Can someone clarify what the real difference is between the two and why or when we should prefer one method over the other?

Let consider a program with an input x, having the following condition: if (x > 5 && x < 10) abort();
Suppose x is an integer, i.e. its domain is 232. The probability to randomly generate an input x that triggers the error is 4/232. This probability is a bit higher in clever greybox fuzzing, but in general they suck for this kind of condition.

On the other hand, whitebox fuzzing executes the program with a symbol x = X, and use a constraint solver, e.g. Z3, to solve the constraint. Z3 can solve X > 5 ∧ X < 10 in mili or nano second.

However, there is no free lunch, this power comes with an expensive price.

  • A recent paper shows that for just one path, i.e. no constraint solving, an execution in KLEE is 3000 times slower than native execution, while angr is 300,000 times slower. Since it is very slow, it is unrealistic to achieve 100% coverage.
  • Constraint solver is only good for linear arithmetic. There is no efficient solver for the theory of string, floating point arithmetic etc
  • It is unrealistic to know all information about APIs, environment etc.

The current state-of-the-art is hybrid fuzzing, combining both greybox and whitebox. The idea is to use greybox fuzzer as global search to quickly sample the state space. When it gets stuck, then use the heavyweight whitebox as local search. This is the technique used by all the team in the Cyber Grand Challenge. The hybrid fuzzer QSym , running on a modest machine, discovered some CVE that Google couldn't find with greybox fuzzers running on the cloud.

forest
  • 64,616
  • 20
  • 206
  • 257
sean
  • 166
  • 1
  • 1
  • 4
  • Huh, I didn't know that SAGE used symbolic execution! I wonder how it compares with AFL... – forest Nov 02 '18 at 06:44
  • Also, you mention that greybox fuzzing is currently the most effective, but then you say that hybrid fuzzing is state-of-the-art. That seems like a contradiction. Perhaps I am misunderstanding. – forest Nov 02 '18 at 06:54
  • @forest: by successful, I meant the number of bugs that it found (publicly). SAGE is not available, so only the MS guys know what it can do. Which one is better will highly depend on the benchmarks, I just give an example that greybox (including AFL), will not work while whitebox (including SAGE) will work very well. However, this is an NP-hard problem, so there is no algorithm that can win in all instances. – sean Nov 02 '18 at 07:02
  • I'm sure SAGE is not _particularly_ difficult to get access to. I guess there is not enough information to say. – forest Nov 02 '18 at 07:03
  • @forest: I met Patrice Godefroid, the main developer of SAGE, at FSE 2016 in Seattle. SAGE is publicly available and it is running in the cloud as project Springfield, but you need to pay a couple of thousands dollars for one run. – sean Nov 02 '18 at 07:08
  • Do you mean that the binary (or source) is available, or that a service which runs SAGE is available? The former would certainly make it easier to obtain, even if it's not impossible regardless. – forest Nov 02 '18 at 07:10
  • @forest: it is available as a cloud service, neither binary nor source are available. You submit the program with sample test cases, it will test the program for you. See here: https://www.microsoft.com/en-us/security-risk-detection/ – sean Nov 02 '18 at 07:11
3

Can someone clarify what the real difference is between the two and why or when we should prefer one method over the other?

Much like a baseball bat, the difference is in the goal of the person holding it - Barry Bonds is going to use it differently than a street criminal.

Both Fuzzing and Symbolic Execution are feeding inputs into a program in order to learn something. In that sense, they're the same exact thing. You can use many of the same tools to do either.

When someone calls it Fuzzing, they're concentrating on a wide variety of synthetic inputs, with the goal of finding inputs that will break things in a way that can be abused. There is a greater focus on "invalid" inputs, because seeing valid inputs handled validly is uninteresting to the person who is Fuzzing.

When someone calls it Symbolic Execution, they're likely to have a smaller, more consistent set of synthetic inputs. Many of them will be "valid" inputs, and they will be verifying the program acts as expected. Some of them will be "invalid" inputs, and they will be verifying that the program handled them without failing.

Fuzzing is used to find ways that programs will break (either to take advantage of, or to fix).

Symbolic Execution is used to ensure the correctness of a program - to measure how it handles the same inputs and to see that performance/stability get better, not worse, over time.

gowenfawr
  • 71,975
  • 17
  • 161
  • 198