3 ms·

http://lcamtuf.blogspot.ru/2015/04/finding-bugs-in-sqlite-easy-way.html http://lcamtuf.blogspot.ru/2015/04/finding-bugs-in-sqlite-ea... Fuzzing found real acti

by thesz 10y ago

http://lcamtuf.blogspot.ru/2015/04/finding-bugs-in-sqlite-easy-way.html http://lcamtuf.blogspot.ru/2015/04/finding-bugs-in-sqlite-ea... Fuzzing found real actionable bugs in SQLite. As I consider fuzzing a variant of static checking (it executes a subset of symbolic evaluation space), I consider the result above as a resounding success of static methods. Also please look at the date when the phrase was added: https://web.archive.org/web/20090205181900/http://sqlite.org/testing.html https://web.archive.org/web/20090205181900/http://sqlite.org... - it's 2009, the very first version of the page! And they didn't change it a bit since. Basically you base your damnation on an outdated information.

emeraldd 10y ago
How does fuzzing fit into static analysis? By my understanding, Static Analysis is defined as examining the code without executing it and fuzzing would inherently require executing the code ...
- thesz 10y ago
  Executing code with single input value is a subset of (symbolic) execution of the same code with all values. You cannot "examine the code" without executing it, partially or in full, with some input or intermediate values or (symbolically) with all of them. I am sure I sound contrary to "common definitions" - so be it. I also think that dynamic typing is a subset of static typing, more or less for the same reason.
  - emeraldd 10y ago
    > You cannot "examine the code" without executing it, partially or in full, with some input or intermediate values or (symbolically) with all of them. It is entirely possible to break a stream of text down into symbols and examine the relationship of those symbols without evaluating (i.e. executing) them. It is not really necessary or possible to know their meaning/definition at all, only their "shape" or the "part of speech" that they represent. In the simplest form, static analyzers are a set of heuristic pattern matchers that a stream of text is sent through. It might get fancy and build an AST first, but that still does not constitute execution or evaluation in the technical sense.
pdq 10y ago
Fuzzing is black-box dynamic testing. Static testing explicitly means you are not executing the program, whereas fuzzing requires generating stimulus, feeding it into the program at runtime, and seeing if it crashes/hangs. https://en.wikipedia.org/wiki/Fuzz_testing https://en.wikipedia.org/wiki/Fuzz_testing https://en.wikipedia.org/wiki/Static_program_analysis https://en.wikipedia.org/wiki/Static_program_analysis
- thesz 10y ago
  http://pat.keldysh.ru/~roman/doc/2009-Klyuchnikov_Romanenko--Proving_the_Equivalence_of_Higher-Order_Terms_by_Means_of_Supercompilation.pdf http://pat.keldysh.ru/~roman/doc/2009-Klyuchnikov_Romanenko-... You can prove that sqlite_exec("create table a ...insert into a ...select * from a where ...") is equal to, say list ["gaga", "gugu"], given supercompiler that is powerful enough. The paper above proves properties up to termination of programs, so it will prove (Haskell) sum [1..] == sum (map (+1) [0..]) as equal (up to computation of the lists). Would you consider this an example of static analysis? If answer is "yes", bear in mind that supercompilation includes evaluation of the programs - basically, supercompiler executes them, looking for states it already seen. I also would like to hear reasons why if answer is "no".
  - pdq 10y ago
    Yes, that is static analysis. But that is vastly different from standard fuzzing. It's pretty simple: if you execute the program code, whether directly on a processor or in an virtual processor/emulator, it's dynamic analysis. Otherwise it's a variant of static analysis. https://en.wikipedia.org/wiki/Dynamic_program_analysis https://en.wikipedia.org/wiki/Dynamic_program_analysis
    - thesz 10y ago
      Supercompilation evaluates code on a virtual machine, building a trace and looking for a "stop" criteria.

by thesz 10y ago

emeraldd 10y ago

How does fuzzing fit into static analysis? By my understanding, Static Analysis is defined as examining the code without executing it and fuzzing would inherently require executing the code ...

thesz 10y ago
Executing code with single input value is a subset of (symbolic) execution of the same code with all values. You cannot "examine the code" without executing it, partially or in full, with some input or intermediate values or (symbolically) with all of them. I am sure I sound contrary to "common definitions" - so be it. I also think that dynamic typing is a subset of static typing, more or less for the same reason.
- emeraldd 10y ago
  > You cannot "examine the code" without executing it, partially or in full, with some input or intermediate values or (symbolically) with all of them. It is entirely possible to break a stream of text down into symbols and examine the relationship of those symbols without evaluating (i.e. executing) them. It is not really necessary or possible to know their meaning/definition at all, only their "shape" or the "part of speech" that they represent. In the simplest form, static analyzers are a set of heuristic pattern matchers that a stream of text is sent through. It might get fancy and build an AST first, but that still does not constitute execution or evaluation in the technical sense.

pdq 10y ago

Fuzzing is black-box dynamic testing. Static testing explicitly means you are not executing the program, whereas fuzzing requires generating stimulus, feeding it into the program at runtime, and seeing if it crashes/hangs. https://en.wikipedia.org/wiki/Fuzz_testing https://en.wikipedia.org/wiki/Fuzz_testing https://en.wikipedia.org/wiki/Static_program_analysis https://en.wikipedia.org/wiki/Static_program_analysis

thesz 10y ago
http://pat.keldysh.ru/~roman/doc/2009-Klyuchnikov_Romanenko--Proving_the_Equivalence_of_Higher-Order_Terms_by_Means_of_Supercompilation.pdf http://pat.keldysh.ru/~roman/doc/2009-Klyuchnikov_Romanenko-... You can prove that sqlite_exec("create table a ...insert into a ...select * from a where ...") is equal to, say list ["gaga", "gugu"], given supercompiler that is powerful enough. The paper above proves properties up to termination of programs, so it will prove (Haskell) sum [1..] == sum (map (+1) [0..]) as equal (up to computation of the lists). Would you consider this an example of static analysis? If answer is "yes", bear in mind that supercompilation includes evaluation of the programs - basically, supercompiler executes them, looking for states it already seen. I also would like to hear reasons why if answer is "no".
- pdq 10y ago
  Yes, that is static analysis. But that is vastly different from standard fuzzing. It's pretty simple: if you execute the program code, whether directly on a processor or in an virtual processor/emulator, it's dynamic analysis. Otherwise it's a variant of static analysis. https://en.wikipedia.org/wiki/Dynamic_program_analysis https://en.wikipedia.org/wiki/Dynamic_program_analysis
  - thesz 10y ago
    Supercompilation evaluates code on a virtual machine, building a trace and looking for a "stop" criteria.