5 ms·

> I wonder if you could make something like Afl-fuzz but point it at your test cases, until it brute-forces some code that makes all your tests pass :) Isn't t

by creshal 12y ago

> I wonder if you could make something like Afl-fuzz but point it at your test cases, until it brute-forces some code that makes all your tests pass :) Isn't that how genetic algorithms are supposed to work?

malka 12y ago
afl fuzz seems to act in some way as a genetic algorithm where the fitness depends of the triggering of new internal states in the target.
deleted 12y ago
[deleted]
- qbrass 12y ago
  Genetic algorithms are more general than that. They don't have to generate code. Using GAs to specifically generate code is genetic programming. https://en.wikipedia.org/wiki/Genetic_programming https://en.wikipedia.org/wiki/Genetic_programming
  - logicallee 12y ago
    But isn't the point of afl-fuzz that it knows deeply about the executable its targeting (watches its state)? So it would be like inspecting the test cases deeply as you fuzz, as opposed to treating them as a black box to hill-climb...
rainforest 12y ago
That's how genetic programming could work; with a suitable test suite you should be able to evolve an implementation. See FINCH for some early work on GP for Java [1]. [1] : http://finch.cs.bgu.ac.il/pubs/gptp.pdf http://finch.cs.bgu.ac.il/pubs/gptp.pdf
Xeoncross 12y ago
This might be computationally feasible in this lifetime for a simple app of sorts, but we are dealing with potentially an insane number of combinations that would have to be tried. We still have trouble calculating all possible 20 character passwords.
- logicallee 12y ago
  You have considerably less trouble checking all 20-character passwords if you get to introspect on the program doing the checking though! (To see what character lets it advance to the following loop or otherwise changes its state; this is similar to a timing attack.) Without doing that, btw, I think you understate the difficulty of "calculating all possible 20 character passwords." It's not just that we 'still have trouble' doing it. If you just take lowercase a-z (and hell, even exclude Q,A,Z,M, and Y so that it's the same on all major keyboard layouts) you still get 20^20=100,000,000,000,000,000,000,000,000 combinations i.e. 10^26. Which at 1000 gigatries per second leaves you with 10^14 seconds, i.e. 3 years. Hey, it's not so bad :) If you add in upper and lowercase, 0-9, and these 32 characters, https://kb.wisc.edu/page.php?id=4073 https://kb.wisc.edu/page.php?id=4073 you get 94^20 = 2e+39 possibilities. That compares favorably with the number of grams in the whole solar system (something like 1.99E+33), including, obviously, the whole Earth, the sun, all the planets, etc. It's the number of grams in 1,000,000 of our solar systems. So don't expect us to start calculating all possible 20 character passwords anytime soon :)

by creshal 12y ago

malka 12y ago

afl fuzz seems to act in some way as a genetic algorithm where the fitness depends of the triggering of new internal states in the target.

deleted 12y ago

[deleted]

qbrass 12y ago
Genetic algorithms are more general than that. They don't have to generate code. Using GAs to specifically generate code is genetic programming. https://en.wikipedia.org/wiki/Genetic_programming https://en.wikipedia.org/wiki/Genetic_programming
- logicallee 12y ago
  But isn't the point of afl-fuzz that it knows deeply about the executable its targeting (watches its state)? So it would be like inspecting the test cases deeply as you fuzz, as opposed to treating them as a black box to hill-climb...

rainforest 12y ago

That's how genetic programming could work; with a suitable test suite you should be able to evolve an implementation. See FINCH for some early work on GP for Java [1]. [1] : http://finch.cs.bgu.ac.il/pubs/gptp.pdf http://finch.cs.bgu.ac.il/pubs/gptp.pdf

Xeoncross 12y ago

This might be computationally feasible in this lifetime for a simple app of sorts, but we are dealing with potentially an insane number of combinations that would have to be tried. We still have trouble calculating all possible 20 character passwords.

logicallee 12y ago
You have considerably less trouble checking all 20-character passwords if you get to introspect on the program doing the checking though! (To see what character lets it advance to the following loop or otherwise changes its state; this is similar to a timing attack.) Without doing that, btw, I think you understate the difficulty of "calculating all possible 20 character passwords." It's not just that we 'still have trouble' doing it. If you just take lowercase a-z (and hell, even exclude Q,A,Z,M, and Y so that it's the same on all major keyboard layouts) you still get 20^20=100,000,000,000,000,000,000,000,000 combinations i.e. 10^26. Which at 1000 gigatries per second leaves you with 10^14 seconds, i.e. 3 years. Hey, it's not so bad :) If you add in upper and lowercase, 0-9, and these 32 characters, https://kb.wisc.edu/page.php?id=4073 https://kb.wisc.edu/page.php?id=4073 you get 94^20 = 2e+39 possibilities. That compares favorably with the number of grams in the whole solar system (something like 1.99E+33), including, obviously, the whole Earth, the sun, all the planets, etc. It's the number of grams in 1,000,000 of our solar systems. So don't expect us to start calculating all possible 20 character passwords anytime soon :)