Afl-fuzz: making up grammar with a dictionary in hand
lcamtuf.blogspot.com
lcamtuf.blogspot.com
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 :) You can throw the syntax of all the modules it should be using at it.
While it might not be make as much sense as if you come up with code yourself, arguably everything humanity has done has been a result of evolutionary fuzzing and test cases.
Isn't that how genetic algorithms are supposed to work?
We still have trouble calculating all possible 20 character passwords.
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 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 :)
Deleted comment
Using GAs to specifically generate code is genetic programming.
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...
It's interesting? It should be no surprise that technology often gets its highest and most inspirational motivation from the dreams of the totality of human literature. For, it is a fact, Artists dream, Engineers build. And all roles are equally capable of authoring things.
It should be less of a surprise, and more of a cause for call to arms, that we are in fact building skynet, and have been for decades now.
Just wait and see. This is how things roll.
Getting trivial solutions is really easy and doesn't "connect" much to the "space" of good algorithms. That's the primary reason for the development of neural networks: with continuous differentiable elements you can do a nicer "hill climbing" toward small representations through back-propagation. With hard-value logic you'd be more stumbling in the dark until you get lucky, but that's O(exp(N)) on the program size.
(Now you have two problems)
AIUI prolog kind of works like that. You give it what it can use and what it needs to produce, and it'll fill in the implementation.
(In practice it's slow as hell and figuring out how to tell it the information in the "right" way so that it can "figure out" the proper implementation is a black art.)
"PS. If you wish to submit raw code to be incorporated into the project, please be aware that the copyright on AFL is formally claimed by Google..."
I'm assuming that this would make forks unlikely or impossible?
-edit- In addition, the bottom of the README which you quoted just mentions the need to sign a CLA if you want your code pushed upstream. See the FSF page about why they require copyright assignment [2] for their projects for some background.
[1] http://lcamtuf.coredump.cx/afl/README.txt [2] https://www.gnu.org/licenses/why-assign.html
(An interesting alternative route would be to rewrite the binary in-place, using something like PEBIL.)