Register | Sign In


Understanding through Discussion


EvC Forum active members: 65 (9162 total)
6 online now:
Newest Member: popoi
Post Volume: Total: 915,815 Year: 3,072/9,624 Month: 917/1,588 Week: 100/223 Day: 11/17 Hour: 0/0


Thread  Details

Email This Thread
Newer Topic | Older Topic
  
Author Topic:   The Minkowski's challenge
nwr
Member
Posts: 6408
From: Geneva, Illinois
Joined: 08-08-2005
Member Rating: 5.1


Message 16 of 120 (352360)
09-26-2006 11:10 AM
Reply to: Message 1 by Albert Godwin
09-25-2006 11:37 AM


Faulty premise
Albert Godwin writes:
If you have a PC virus that mutates, can you force it to evolve an encrypted virus?
And if you can't, will you please stop saying that the whole of those creatures did evolve?
The tacit premise on which you base this seems entirely wrong. You want simulated evolution to achieve a very specific purpose, namely encryption. The idea that evolution is driven to achieve a particular purpose is a teleological assumption.
Evolutionists have rejected such teleological assumptions from the beginning. This type of criticism of evolution is badly misconceived.

This message is a reply to:
 Message 1 by Albert Godwin, posted 09-25-2006 11:37 AM Albert Godwin has not replied

  
Percy
Member
Posts: 22391
From: New Hampshire
Joined: 12-23-2000
Member Rating: 5.2


Message 17 of 120 (352364)
09-26-2006 11:26 AM
Reply to: Message 13 by Barbarian
09-26-2006 10:48 AM


Barbarian writes:
(1) is the task to evolve a mechanism which helps eluding a selector looking at patterns of N bytes? What is N? (I could tell right away if I saw the QBASIC code.) Am I right in calling this a stealth mechanism and not an encryption one?
I don't think Albert is using the proper term when he says "encryption", but he's basing his argument on the Minkowski novel and can't be blamed for that. After rereading the Minkowski/Faust discussion I can see that when Minkowsi says encryption he really means camouflage. Your own term, "stealth", is also much closer to what I think was intended. Camouflage and stealth are much more accurate terms when you consider actual evolutionary examples such as rabbits evolving white fur to blend in with snow.
If all Albert is looking for is an example of a code creature species hiding from a predator or otherwise protecting itself from selection pressures by evolving camouflage, then this should be easy. This happens in ALife all the time. In fact, it's so incredibly common and mundane that I don't think you should even go through the effort of coding yet another one, though it would be a fun exercise and well worth engaging in from that standpoint.
--Percy

This message is a reply to:
 Message 13 by Barbarian, posted 09-26-2006 10:48 AM Barbarian has replied

Replies to this message:
 Message 18 by Modulous, posted 09-26-2006 1:27 PM Percy has not replied
 Message 19 by Barbarian, posted 09-27-2006 7:22 AM Percy has not replied

  
Modulous
Member
Posts: 7801
From: Manchester, UK
Joined: 05-01-2005


Message 18 of 120 (352404)
09-26-2006 1:27 PM
Reply to: Message 17 by Percy
09-26-2006 11:26 AM


If all Albert is looking for is an example of a code creature species hiding from a predator or otherwise protecting itself from selection pressures by evolving camouflage, then this should be easy. This happens in ALife all the time.
Was it in Tierra where they changed the parameters so that larger programs would get a proportionally larger amount of processor time dedicated to them, only to find that the 'organisms' mutated in a way to fool the size alogirithm into thinking they were larger than they were thus getting a disproportionally large amount of processor time?

This message is a reply to:
 Message 17 by Percy, posted 09-26-2006 11:26 AM Percy has not replied

  
Barbarian
Inactive Member


Message 19 of 120 (352583)
09-27-2006 7:22 AM
Reply to: Message 17 by Percy
09-26-2006 11:26 AM


quote:
If all Albert is looking for is an example of a code creature species hiding from a predator or otherwise protecting itself from selection pressures by evolving camouflage, then this should be easy. This happens in ALife all the time. In fact, it's so incredibly common and mundane that I don't think you should even go through the effort of coding yet another one, though it would be a fun exercise and well worth engaging in from that standpoint.
IMO the best - and still pretty weak - argument for doing it anyway is that even if we convinced Albert about the relevance of prior work in this area, the challenge would still have to be met directly in order to convince the more literal-minded segment of the population; stating that e.g. Tierra or Avida proves its doability could sound like cop-outs for many.
Basically, I planned to go through the proposed rule amendments one at a time and making it clear for Albert why am I proposing them. Such an exercise could lead to a lot of useful results. I know that under those amendments the task would be tedious but ultimately pretty simple, although getting it actually run to completion within a few hours could be challenging or even impossible.

This message is a reply to:
 Message 17 by Percy, posted 09-26-2006 11:26 AM Percy has not replied

  
Albert Godwin
Inactive Member


Message 20 of 120 (352753)
09-28-2006 6:03 AM
Reply to: Message 13 by Barbarian
09-26-2006 10:48 AM


quote:
(1) is the task to evolve a mechanism which helps eluding a selector looking at patterns of N bytes? What is N? (I could tell right away if I saw the QBASIC code.) Am I right in calling this a stealth mechanism and not an encryption one?
The Qbasic source is already present, please look back to the codes.
quote:
(2) do I get to change the selector too, to be more stochastic? Right now the selector goes and kills on sight all viruses (= programs containing a certain sequence of bytes). It should measure the difficulty of recognizing a virus and give them a chance of survival proportional to that difficulty.
Do whatever you'd like as long as it is in qbasic
quote:
(3) do I have to use Intel 8086 machine code in a PC BIOS + MS DOS environment, as the OP does? I could easily do that - all I have to do is break out the Norton Guides and feel young again -, but I think I could propose a simpler virtual machine code, which would allow me to do 4) below, do away with the fundamental DOSyness of the OP program and make us start from the same base, as both of us would be beginners for that kind of code.
(4) it may be that the evolution of a stealth mechanism becomes possible but not in human timeframes. If that is the case, would you accept a formal proof instead of a physical experiment? The proof would try to show that after a huge number of iterations the probability of having a working stealth code goes above 90%.
No, i am sorry. If you can evolve steath (which will not either happen, ny the way) that's not the challenge. the challenge is to evolve encryption. and do it in real programming, no virual simulations and no formal proofs. i want a practical responce.
by the way, if you have read the original Marcus Minkowski/Faust Amoyo discussion, the program indeed DID evolve. but that's just a minor evolution, not marcroevolution.
quote:
(5) is there anything to speed up the process of approval from the original author to publish the code again? I would want to keep the solution as close to the original one as possible.
I don't understand. the author, Fady Bahig has a storefront here:
Lulu Logo
he put his mail there, if you want to contact him, you can.
Hey? you didn't see the code? you will find it in the proposed new articles forum !
quote:
No, that is not fine at all. But I might of course reconsider if you told us what is your objection to making theoretical posts here.
I just said that because i didn't want to see stupid replies, just like the one Rick posted right after my last message.

This message is a reply to:
 Message 13 by Barbarian, posted 09-26-2006 10:48 AM Barbarian has replied

Replies to this message:
 Message 23 by RickJB, posted 09-28-2006 7:20 AM Albert Godwin has not replied
 Message 24 by Percy, posted 09-28-2006 9:40 AM Albert Godwin has not replied
 Message 28 by Barbarian, posted 09-29-2006 4:29 AM Albert Godwin has not replied
 Message 31 by Dr Jack, posted 09-29-2006 5:45 AM Albert Godwin has not replied
 Message 37 by Barbarian, posted 09-29-2006 9:49 AM Albert Godwin has not replied

  
Albert Godwin
Inactive Member


Message 21 of 120 (352755)
09-28-2006 6:05 AM


you can find the code and discussion here:
http://EvC Forum: The Minkowski's challenge -->EvC Forum: The Minkowski's challenge

Replies to this message:
 Message 22 by Barbarian, posted 09-28-2006 7:03 AM Albert Godwin has not replied

  
Barbarian
Inactive Member


Message 22 of 120 (352762)
09-28-2006 7:03 AM
Reply to: Message 21 by Albert Godwin
09-28-2006 6:05 AM


Sorry, missing the code was entirely my mistake, when I returned to the original proposed OP I thought the code got snipped b/c there was some discussion as per the appropriateness of posting long excerpts or something like that. Please consider those requests moot.

This message is a reply to:
 Message 21 by Albert Godwin, posted 09-28-2006 6:05 AM Albert Godwin has not replied

  
RickJB
Member (Idle past 4990 days)
Posts: 917
From: London, UK
Joined: 04-14-2006


Message 23 of 120 (352764)
09-28-2006 7:20 AM
Reply to: Message 20 by Albert Godwin
09-28-2006 6:03 AM


I just said that because i didn't want to see stupid replies, just like the one Rick posted right after my last message.
Well excuse me for breathing, Lord Godwin!
It seems perfectly reasonable for anyone to want to question the theoretical basis of your challenge.
Edited by RickJB, : No reason given.

This message is a reply to:
 Message 20 by Albert Godwin, posted 09-28-2006 6:03 AM Albert Godwin has not replied

  
Percy
Member
Posts: 22391
From: New Hampshire
Joined: 12-23-2000
Member Rating: 5.2


Message 24 of 120 (352795)
09-28-2006 9:40 AM
Reply to: Message 20 by Albert Godwin
09-28-2006 6:03 AM


Albert Godwin writes:
No, i am sorry. If you can evolve steath (which will not either happen, ny the way) that's not the challenge. the challenge is to evolve encryption. and do it in real programming, no virual simulations and no formal proofs. i want a practical responce.
I'm not sure why Barbarian didn't bring this up, but in reading the Minkowski/Faust discussion it seemed apparent that by encryption they actually meant camouflage. As Minkowski discovered when he ran his program, it achieved camouflage by slightly altering its code. As Minkowski himself says about the evolution of encryption, "that's not obligatory." Yes, encryption would also achieve the goal of hiding from the selector program, but so do very minor changes to the code sequence.
This is because the selection pressure is for hiding from the selector, not for encryption. As Minkowski makes clear in the discussion, simple mutations achieve the goal of hiding from the selector, and after that there is no selection pressure for further hiding. More complex approaches to hiding, such as actual encryption of the program code, cannot evolve if the code creature has already achieved hiding.
Minkowski said that he couldn't imagine any selection pressure that would evolve encryption, and neither can I, which isn't to say it isn't possible. But you've mistaken the way evolution works, as has been pointed out by others in this thread. Evolution does not lay out a specific goal like flagellum or gills. It lays out a general goal of "Produce more offspring and more viable offspring than everyone else." As genetic algorithms make clear (genetic algorithms is a subject that would be worth your while investigating), evolutionary solutions are often novel, surprising and unexpected. The Mikowski software provides selection pressure for camouflage, but you're requiring a specific solution of encryption, which isn't the way evolution works.
You can try to fine tune the selection pressures to produce encryption (fine tuning selection pressures is a primary topic in genetic algorithms), but what you would really need in that case is for both code creature and selector program to evolve at the same time. The reason the code creature won't evolve encryption is because fooling the selector is so easy that encryption isn't necessary. But if the selector could also evolve to be smarter then the code creature would be forced to develop more sophisticated camouflage techniques, possibly even encryption.
Keep in mind that the selector's task is much easier than the code creature's. All the selector has to do is recognize byte sequences, it doesn't have to know any encryption/decryption algorithms. If, for example, the byte sequence "BFB801BE0001B9B800E86500" from the code creature becomes after encryption "AEA7F0ADFFF0A8A7FFD754FF", recognizing one is as easy as recognizing the other for the selector. All the selector has to do is chance across the proper sequence of bytes through the mutation/reproduction process, it doesn't have to know anything about encryption.
--Percy
Edited by Percy, : Grammar.

This message is a reply to:
 Message 20 by Albert Godwin, posted 09-28-2006 6:03 AM Albert Godwin has not replied

Replies to this message:
 Message 25 by Barbarian, posted 09-28-2006 10:36 AM Percy has replied

  
Barbarian
Inactive Member


Message 25 of 120 (352805)
09-28-2006 10:36 AM
Reply to: Message 24 by Percy
09-28-2006 9:40 AM


quote:
I'm not sure why Barbarian didn't bring this up, but in reading the Minkowski/Faust discussion it seemed apparent that by encryption they actually meant camouflage. As Minkowski discovered when he ran his program, it achieved camouflage by slightly altering its code. As Minkowski himself says about the evolution of encryption, "that's not obligatory." Yes, encryption would also achieve the goal of hiding from the selector program, but so do very minor changes to the code sequence.
I tried to clarify that in the proposed amendment #1 above, but my English let me down and I could not promptly remember the word 'camouflage', so I proposed 'stealth' instead; nonetheless, 'camouflage' is a much better choice.

This message is a reply to:
 Message 24 by Percy, posted 09-28-2006 9:40 AM Percy has replied

Replies to this message:
 Message 26 by Percy, posted 09-28-2006 10:43 AM Barbarian has replied

  
Percy
Member
Posts: 22391
From: New Hampshire
Joined: 12-23-2000
Member Rating: 5.2


Message 26 of 120 (352806)
09-28-2006 10:43 AM
Reply to: Message 25 by Barbarian
09-28-2006 10:36 AM


Barbarian writes:
I tried to clarify that in the proposed amendment #1 above, but my English let me down and I could not promptly remember the word 'camouflage', so I proposed 'stealth' instead; nonetheless, 'camouflage' is a much better choice.
Oh, yes, I realize that. But in his Message 20 to you Albert said he wasn't interested in stealth but encryption:
Albert writes:
No, i am sorry. If you can evolve steath (which will not either happen, ny the way) that's not the challenge. the challenge is to evolve encryption. and do it in real programming, no virual simulations and no formal proofs. i want a practical responce.
It didn't seem like you addressed this in your Message 22.
--Percy

This message is a reply to:
 Message 25 by Barbarian, posted 09-28-2006 10:36 AM Barbarian has replied

Replies to this message:
 Message 27 by Barbarian, posted 09-29-2006 4:04 AM Percy has not replied

  
Barbarian
Inactive Member


Message 27 of 120 (353034)
09-29-2006 4:04 AM
Reply to: Message 26 by Percy
09-28-2006 10:43 AM


Ah, ok, I misunderstood your post then. The reason was that I wanted first to think a bit about my next couple of moves here, and some pretty promising variants did in fact involve going along with this different notion of encryption. More soon.

This message is a reply to:
 Message 26 by Percy, posted 09-28-2006 10:43 AM Percy has not replied

  
Barbarian
Inactive Member


Message 28 of 120 (353038)
09-29-2006 4:29 AM
Reply to: Message 20 by Albert Godwin
09-28-2006 6:03 AM


Hi, Albert -
I am coming closer to get what the OP is trying to say: it seems to claim that the evolution of mutually dependent traits is impossible if the presence of only some but not all of them is detrimental to the organism, because there is no right order in which they could evolve, and that this makes all "macroevolution" impossible as well? Encryption is not meant to evade virus protection but to exemplify a set of traits - encryption cability, decryption capability and being encrypted - which can only appear together or the program is bust? I'll assume this is what you say, but please correct me if I misunderstood it.
This is a slightly different ballgame then. You want the program to hide part of its code by some sort of scrambling, byte-by-byte - there should be a routine that does the scrambling before saving, one that does the unscrambling and then passes control to the resulting code, and this unscrambled resulting code must do something, it must be executed. In addition, all this must be achieved step-by-step.
Now, depending on the exact definitions, this could be anywhere between trivial and impossible. Some stuff to consider: what is an acceptable scrambling? Adding 1 to each byte? XOR-ing it to a randomly chosen segment of the ROM BASIC code byte by byte and storing the start address of the chosen segment? Full-blown DES encryption? I propose that a deterministic, one-to-one replacement of every byte value, regardless of its position, should suffice as encryption/scrambling (e.g. adding 1 for scrambling and subtracting 1 for unscrambling should be sufficient).
What is the function and size of the code which needs to be hidden this way? Can it be a single NOP? Must it contain all the file-writing code? And: must it be executable over the whole evolution pathway? I propose that the code segment in question must be executed in the final result (but not in all previous generations) and that it have a minimal length of 12 bytes (so there is no restriction as to the actual function it performs - we only need to execute it to prove that the unscrambling did happen).
I would propose two more amendments to the rules for this challenge.
(7) a sequence of selectors may be used. I.e. we use one selector to evolve some trait, then when that is done we use another selector until the trait evolves into something else, and so on. Note that this is what happens in nature all the time: environments change. Real environment changes regardless if certain traits have already appeared, but we need to link the two because we want a certain result, we are reverse-engineering a teleological mechanism here.
(8) we should remove the error generating mechanism from the code. Most of biological evolution happens over mechanisms which seem to try very hard to produce exact copies, so mutations are essentially errors of that mechanism. I propose that mutations happen after file writing, during the copying to the new directory or whatever corresponds to that step. It should not be possible for a program to evolve the capability of not mutating at all. (In a virtual machine, replacements of bytes would also happen as random mishaps during store operations, not under the control of the code.)
Incidentally, if I posted a solution, would you be able to verify it? You said you were no assembly expert. Virtual machine?
quote:
No, i am sorry. If you can evolve steath (which will not either happen, ny the way) that's not the challenge. the challenge is to evolve encryption. and do it in real programming, no virual simulations and no formal proofs. i want a practical responce.
There is a lot of manual work involved in getting the next generation. Run the selector, create different directories, move survivors to them one by one, rename them to Gen.com, run them etc. If you are extra lucky, you can do ten generations hourly, and even that with a relatively small population. I am willing to put up with the - btw. incorrect - assumption implicitly present in the challenge that any replicator over any substrate can evolve into anything at all, but I draw the line at adding the clause "over arbitrarily small number of generations". That is simply not a realistic restriction. It could take 100.000s of generations to evolve something useful, and that would only prove that it is impossible to do it manually; living things had enough time to do that and much more.
A virtual simulation would have all the advantages we need here. It could manage the whole cycle - generate-select-verify - in a much shorter time. We could do away with dangerous things like one-byte interrupt calls which could easily damage the filesystem on your disk, or do damage to older harddisks or monitors. The particular machine code is complicated, and while that complexity is not a principial showstopper in any of the theoretical questions we try to tackle here, it could still make the effort practically unrealistic. Note that this does not mean that processes of similar character are unrealistic in nature, with more time and resources at its hands. If I understand your challenge correctly this time, I will insist on either the use of a virtual machine, or on a detailed explanation from your part about why do you think a virtual machine is a bad idea, because I don't really get it.
I am also worried about your dismissal of 'theory'. For instance, in 'theory', the probability of having the mutation shown in the OP in one step is approximately 0.00000003, as calculated from a few assumptions (the code size is appr. 170 bytes and the random generator is a uniform generator of one-byte values, so the probability in question = P(one mutation at the exact spot) * P(the mutation is an insertion) * P(the inserted byte is 52H=PUSH DX) = (255^169)/(256^172) = 0.00000003...). Does this fall into your 'theory' category? If it does, why is it not acceptable as a replacement to actually generating tens of millions of files and verifying each one of them? I did not plan to use as proof anything more complicated than this kind of calculation.
quote:
by the way, if you have read the original Marcus Minkowski/Faust Amoyo discussion, the program indeed DID evolve. but that's just a minor evolution, not marcroevolution.
I saw it, but I never said the program could not evolve at all. I said there are severe limitations to what it could evolve to, considering the inherent size limitation and the very restrictive selector.
quote:
I just said that because i didn't want to see stupid replies, just like the one Rick posted right after my last message.
I do not see at all what was stupid in that reply, and I wish you explained it in more detail. In addition, you addressed the restriction to either me or to an abstract 'you', not just to Rick. When I suggested that you should explain your demand, I sort of expected that you would point out whatever seems to be 'theoretical' in my previous posts. You should consider that we most likely do not share your idea about what is and what is not inacceptably theoretical (although I suspect it is more like 'conjectural' you are hinting at here), so for the sake of communication, you should walk the extra mile and explain it to us.

This message is a reply to:
 Message 20 by Albert Godwin, posted 09-28-2006 6:03 AM Albert Godwin has not replied

Replies to this message:
 Message 30 by Percy, posted 09-29-2006 5:37 AM Barbarian has not replied

  
Percy
Member
Posts: 22391
From: New Hampshire
Joined: 12-23-2000
Member Rating: 5.2


Message 29 of 120 (353042)
09-29-2006 5:14 AM


Albert's participation in his own thread is a bit thin. It's been mentioned that Albert has started similar threads at other boards, and I imagine that's where his time is going. Google turned up one of these threads. This is from PhysOrg Forums' The Minkowski Challenge, A practical challenge to evolution:
Albert writes:
So long just more theoritizations
Look boys, There is a programmer guy called barbarian who will take the challenge
EvC Forum: Information
follow up and you will see that he will fail.
It seems he's as brief in discussion at other boards as he is here. He seems to think that the primitive and naive Minkowski evolution program (by the standards of the state of the art 20 years ago, let alone by the standards of today) represents a challenge to evolutionists, when the real challenge is how to bring Albert's understanding up to a level where meaningful discussion can take place.
Albert doesn't appear familiar with programming, artificial life or genetic programming. He's been encouraged to investigate the latter two but shows no apparent interest, and he hasn't engaged any of the replies questioning whether his challenge can say anything meaningful about evolution. It is tactically wise for the unarmed man to avoid the battlefield, but this approach only postpones the inevitable outcome, though Albert is unlikely to comprehend the result if he continues to resist learning about the area he's discussing.
Barbarian indicates he has a couple ideas of how to approach the problem of encouraging the evolution of encryption. Tuning the selection pressures is a common issue in genetic algorithm development, which unlike actual evolution tends to have very specific goals. The key is to fine tune the "environment" so that it provides selection pressures that push evolution in the necessary direction. It remains to be seen whether evolution of encryption is analogous to horses evolving wheels or rocket power, in other words, not a realistic goal.
I encourage Barbarian in his efforts while at the same time entertaining serious doubts about the advisability of this approach. If Barbarian is unsuccessful then evolutionists will properly conclude that the evolution of encryption is either too difficult a problem or simply isn't amenable to evolution, since we already know that evolution has been demonstrated many times in many ways, but Albert will conclude that it demonstrates the impossibility of significant evolution. And if Barbarian is successful then Albert will dispute the results, though at least discussion with him might become possible in this circumstance.
I'm fascinated by the research areas of artificial life and genetic algorithms. Given sufficient time I would be developing my own ALife system, but alas, this board's messages still need integration into the database and my day job is sparing me few cycles these days. But I do have time to discuss these topics. The great value of discussion is that everyone has the opportunity to learn something, so here's hoping that Albert begins discussing the subject soon.
--Percy

  
Percy
Member
Posts: 22391
From: New Hampshire
Joined: 12-23-2000
Member Rating: 5.2


Message 30 of 120 (353046)
09-29-2006 5:37 AM
Reply to: Message 28 by Barbarian
09-29-2006 4:29 AM


Hi Barbarian,
I hadn't yet seen this, your most recent message, when I posted my previous message. You've done a great job breaking down the problem and identifying the key issues.
The most important issue derives from the primitive approach taken my Minkowski. I had forgotten that the actual running and pruning of the offspring programs was manual. This definitely needs to be automated in order for any meaningful evolution to take place. It shouldn't run under DOS but Windows or Linux so that all illegal accesses and instructions can be trapped, and so that your mutation algorithm doesn't have to concern itself with the potential for generating destructive code.
You're actually giving yourself the very ambitious goal of developing an ALife system, which could be extremely time-consuming. Perhaps you have resources or existing code at your disposal that would shorten the development time, in which case I encourage you to go for it. But if this would be a significant effort for you why not instead translate Minkowski's code into an existing ALife framework like Avida? The Minkowski program would be one ALife creature, the selector (or selectors) would be another and the equivalent of a predator.
Anyway, best of luck. I wish I had sufficient available time to extend an offer to help.
--Percy

This message is a reply to:
 Message 28 by Barbarian, posted 09-29-2006 4:29 AM Barbarian has not replied

  
Newer Topic | Older Topic
Jump to:


Copyright 2001-2023 by EvC Forum, All Rights Reserved

™ Version 4.2
Innovative software from Qwixotic © 2024