5 ms·

"no one knows how it works" - That caught my attention, having seen computer evolved ASTs. Probably no one knows because no one has put effort to reverse engine

"no one knows how it works" - That caught my attention, having seen computer evolved ASTs. Probably no one knows because no one has put effort to reverse engineer the internals - most of which would be unnecessary complexity that is very likely with neural nets. Many years back, I had once experimented with PyEvolve to develop a custom trading strategy which was kind-of code with a custom instruction set. The output of a strategy was a string (program AST) that was uglier than most obfuscation outputs with many unnecessary statements. For example "a=1;b=2;c=a+b;d=c/3;if(d==1).." - expand that to many more variables. The program evolved strategies that made small profit and therefore the output was worth analysing. But decompiling that output used to take me hours - and few of those were tweaks of well documented strategies. Others I never understood because it was too much effort for a relatively small profit (and other trading parameters).

dflock 10y ago
Could you not automate that too? Have another stage of evolution where you just randomly delete statements from the 'code' and the fitness function is that the performance doesn't get worse. This should eventually reduce the 'code' to it's minimal state, removing any unnecessary parts.
- fbonetti 10y ago
  Deleting random lines of code? That's like the bogosort of machine learning.
  - timtadh 10y ago
    It is actually called Delta Debugging and was pioneered by Andreas Zeller (https://www.st.cs.uni-saarland.de/dd/ https://www.st.cs.uni-saarland.de/dd/). His first paper on it ("Yesterday, my program worked. Today, it does not. Why?") used essentially the technique above to isolate the failure inducing change. Surprisingly, techniques like this work very well and doing better is sometimes very difficult especially for large programs. For instance, in theory, using "Concolic Execution" which combines symbolic execution, constraint solving, and concrete execution one can do better. However, such systems have their own limitations with respect to program complexity. See also the tremendous effectiveness of AFL (American Fuzzy Lop) http://lcamtuf.coredump.cx/afl/ http://lcamtuf.coredump.cx/afl/ . AFL uses a straight forward technique to mutate code. It doesn't use any fancy program analysis and has been able to find lots of bugs in real programs.
    - tripzilch 10y ago
      I was going to mention AFL as well, but for a different reason (unless I misunderstood your post). Disclaimer: I've never used AFL myself but I've read articles about it with great interest (especially the crazyweird experiment when it created valid JPG images out of thin air, that was brilliant). So during fuzzing, it finds lots "interesting" program-inputs (that cause crashes, bugs and weird behaviour). But it also has a different mode, where it tries to minimize these program-inputs to the essential parts that cause the behaviour. Since the bugs found are generated from (semi) randomly mutated inputs, the "interesting" inputs often also contain extraneous data that just happens to be there, but isn't relevant to the particular "interesting" behaviour found. From what I understand, it uses this minimization mode after fuzzing, between sets of fuzzing runs (for good seed inputs to start with) and perhaps also during fuzzing (not sure). I read about it, but I forgot how it works exactly. It's probably explained on lcamtuf's site or AFL docs. I'm assuming it uses a similar method as proposed by dflock above, iterating deleting random stuff as long as the "interesting" behaviour remains. I also wouldn't be surprised if non-AFL style fuzzer toolsets have similar test-input minimization tools. They also generate random inputs usually, just not AFL's clever pruning technique of keeping track of previously-seen program states to guide the random search to prefer novel states. Which I believe is the most revolutionary idea that makes AFL perform so uniquely well.
- _wmd 10y ago
  There already is automation for exactly this, it's the optimization step of any compiler. Sounds like OP's lacked an optimizer
  - johncolanduoni 10y ago
    That's not too helpful (especially with python due to interpretation) because what you want to see is the output of the optimizer in the source language with only optimizations that make things clearer (as opposed to more opaque like many optimizations) applied.
user5994461 10y ago
I can relate, I remember once a few years ago while I was analysing a program. I spent hours reverse engineering one of the custom cryptographic function, it looked like nothing I ever saw... then I realized it was Base64 :D

dflock 10y ago

Could you not automate that too? Have another stage of evolution where you just randomly delete statements from the 'code' and the fitness function is that the performance doesn't get worse. This should eventually reduce the 'code' to it's minimal state, removing any unnecessary parts.

fbonetti 10y ago
Deleting random lines of code? That's like the bogosort of machine learning.
- timtadh 10y ago
  It is actually called Delta Debugging and was pioneered by Andreas Zeller (https://www.st.cs.uni-saarland.de/dd/ https://www.st.cs.uni-saarland.de/dd/). His first paper on it ("Yesterday, my program worked. Today, it does not. Why?") used essentially the technique above to isolate the failure inducing change. Surprisingly, techniques like this work very well and doing better is sometimes very difficult especially for large programs. For instance, in theory, using "Concolic Execution" which combines symbolic execution, constraint solving, and concrete execution one can do better. However, such systems have their own limitations with respect to program complexity. See also the tremendous effectiveness of AFL (American Fuzzy Lop) http://lcamtuf.coredump.cx/afl/ http://lcamtuf.coredump.cx/afl/ . AFL uses a straight forward technique to mutate code. It doesn't use any fancy program analysis and has been able to find lots of bugs in real programs.
  - tripzilch 10y ago
    I was going to mention AFL as well, but for a different reason (unless I misunderstood your post). Disclaimer: I've never used AFL myself but I've read articles about it with great interest (especially the crazyweird experiment when it created valid JPG images out of thin air, that was brilliant). So during fuzzing, it finds lots "interesting" program-inputs (that cause crashes, bugs and weird behaviour). But it also has a different mode, where it tries to minimize these program-inputs to the essential parts that cause the behaviour. Since the bugs found are generated from (semi) randomly mutated inputs, the "interesting" inputs often also contain extraneous data that just happens to be there, but isn't relevant to the particular "interesting" behaviour found. From what I understand, it uses this minimization mode after fuzzing, between sets of fuzzing runs (for good seed inputs to start with) and perhaps also during fuzzing (not sure). I read about it, but I forgot how it works exactly. It's probably explained on lcamtuf's site or AFL docs. I'm assuming it uses a similar method as proposed by dflock above, iterating deleting random stuff as long as the "interesting" behaviour remains. I also wouldn't be surprised if non-AFL style fuzzer toolsets have similar test-input minimization tools. They also generate random inputs usually, just not AFL's clever pruning technique of keeping track of previously-seen program states to guide the random search to prefer novel states. Which I believe is the most revolutionary idea that makes AFL perform so uniquely well.
_wmd 10y ago
There already is automation for exactly this, it's the optimization step of any compiler. Sounds like OP's lacked an optimizer
- johncolanduoni 10y ago
  That's not too helpful (especially with python due to interpretation) because what you want to see is the output of the optimizer in the source language with only optimizations that make things clearer (as opposed to more opaque like many optimizations) applied.

user5994461 10y ago

I can relate, I remember once a few years ago while I was analysing a program. I spent hours reverse engineering one of the custom cryptographic function, it looked like nothing I ever saw... then I realized it was Base64 :D