The Crypto-CS-SETI challenge:
An Un-programming Challenge

A challenge to all bright minds in the IT and CS world: Can you disassemble a program for an unknown computer, given only the compiled ROM image?

I hereby announce a challenge, beginning immediately, to gather as much information as possible about the program file linked below.

Imagine finding a crashed flying saucer.

This time it is no hoax and there are no black helicopters involved.

And there is no doubt that it is not of our planet because there is absolutely no way Akhnaten could have bought a used carbon-carbon heat-shield on eBay—and, in particular, one that cannot be carbon-14 dated as it has no carbon-14 atoms.

By deciphering the hieroglyphs, we learn that there was a royal cover up (which is why we haven't heard about it until now) and that the alien technology was based on self-replicating biological principles, which, unfortunately, replicated nowhere nearly as fast as the locusts and cockroaches could eat them.

As more and more of the secret royal journal is translated, things start to make sense: Where Akhnaten got his strange ideas, why he was so terrible at genetics, but not, alas, the Philip Glass Opera.

But apart from the heat-shield, the only actual physical evidence is some broken test-tubes and a small glittering object, which archaeologist quickly declare—"Probably had ceremonial or religious significance,"—which is simply their way of saying "no idea..."

On subsequent examination, the object is found to be a small triangular corner, sawed from a piece of printed circuit board and then used as jewelry or as a talisman—proving the archaeologists both wrong and right.

An X-ray examination reveals that one part of the object contains what is clearly some kind of mask-programmed ROM storage.

We read out the bit-pattern...and then what?

What, if anything, can we deduce about the rest of the alien world from only a program? We don't know what it does, and we have no information about the computer for which it was written [1]?

It could have been an alien's favorite game cartridge for his Erodommoc-46 home computer, or it might be a piece of supercomputer which unlocked the tasty secret of DNA-computing. Or maybe it was the mobile phone with which they digitally signed their marriage certificate several hundred thousand years ago.

Of course, none of the above is true, except possibly for the bit about the opera, but the question is worthy of study in its own right. It's not only a purely academic question, but a very real problem for curators of computer history collections, where artifacts don't always come with enough metadata to allow proper identification. The task is akin to breaking a cryptographic code, only instead of searching for highly confidential messages such as "Hvid armes hovedkvarter har ikke mere jordbærsyltetøj, kan I sende en stafet over åen med et par glas?" we are looking for "while (something()) {something_else(); };". And instead of having been encrypted, it has merely been compiled and that should make the task much easier—nobody has actively tried to hide anything. Quite the contrary, like all terrestrial programmers, they probably went out of their way to make sure the computer would understand their program in precisely one way.

But we cannot make too many assumptions about the code.

It might have been developed in a highly structured manner with formal methods and proven correct because it was part of something important, or it could have been optimized by a genetic-algorithm compiler and be the most terrible spaghetti code and only marginally less tangled than animal DNA code.

Can we actually disassemble a program for an unknown computer? The best way to find out is to try, so here is my challenge to all bright minds in the IT and CS world:

With the publication of this article I release a 16384 byte program file [2].

The challenge is to deduce as much as possible about the program, about the device and about what it does. The program is from a computer very few people have ever come into contact with and for which no copies of the documentation are thought to exist anymore. And Google is absolutely clueless about it, so it is a pretty good stand-in for an alien EPROM.

The only help you get is this:

It is an unmodified real-world program that somebody once wrote to do something beneficial. The computer still works and I have studied it sufficiently with a logic analyzer to be able to judge any submitted results from the challenge.

There is no prize for winning in this challenge, because I have absolutely no idea where to put the goal-posts. The real prize will be learning something about programs, as archeological or crypto-zoological artifacts and I strongly urge publication of this learning.

I also urge anyone who might be able to identify this ROM-image—either from having programmed this computer, or who for some reason recognizes this code—to please contact me privately, rather than publicly spoil the challenge for the rest.

And with that, good luck!

References

[1] A somewhat similar situation was discussed in http://en.wikipedia.org/wiki/History_Lesson_%28short_story%29

[2] The binary file for the challenge is available here:
http://phk.freebsd.dk/UCO/

POUL-HENNING KAMP (phk@FreeBSD.org) is one of the primary developers of the FreeBSD operating system, which he has worked on from the very beginning. He is widely unknown for his MD5-based password scrambler, which protects the passwords on Cisco routers, Juniper routers, and Linux and BSD systems. Some people have noticed that he wrote a memory allocator, a device file system, and a disk encryption method that is actually usable. Kamp lives in Denmark with his wife, his son, his daughter, about a dozen FreeBSD computers, and one of the world's most precise NTP (Network Time Protocol) clocks. He makes a living as an independent contractor doing all sorts of stuff with computers and networks.

Comments

  • Poul-Henning Kamp | Fri, 13 Jan 2012 16:27:57 UTC 

    Just a few clarifying comments:

1. No, I will neither give you any (further) hints, at least not yet.

2. This is not "20 questions", I will not respond to pure guesswork.

Poul-Henning

  • Poul-Henning Kamp | Sat, 14 Jan 2012 11:31:33 UTC 

    I have been asked about the organization of the physical memory.

It is an oversight on my part that this was not mentioned, since it obviously is something we would find out while investigating the hardware:

The data bus has 8 bits, the address bus 14 bits.

  • Poul-Henning Kamp | Sun, 15 Jan 2012 20:51:58 UTC 

    I have received a question by email, which I chosen to answer:

Q:
If I had access to the hardware I would know how many chips was
connected to the address bus, and if the chips connected to it was
similar or different.

A:
And you wouldn't be any wiser than you are with the information I have
already released about the image.

  • Poul-Henning Kamp | Wed, 18 Jan 2012 07:36:02 UTC 

    This morning I had an email from a group which correctly have identified the CPU and its application through what must be extremely clever google-sleuting.

That's really impressive, but not what this challenge is about.

The challenge is about how much we can deduce from a program when we know nothing about the computer.

For all I care, this group, which seems very talented, have disqualified themselves.

Please stay within the rules.

  • Poul-Henning Kamp | Wed, 18 Jan 2012 10:13:29 UTC 

    Further update:

I have received evidence of the above mentioned groups effort, and they are nothing short of impressive.

I will acknowledge their identity by recognizing: d04232031b7fd99403b00f3ded26f31e0a316d8c

However, the same evidence also clearly shows that they broke the rules of the contest by trying to, and successfully identifying the device in question, at which point their effort no longer is a "cold read" of an alien ROM.

This is a very unfortunate situation, but under the rules of this contest, it is a disqualifying action.

I hope that despite this disappointment, they will not release illegal clues, which spoil the competition for all other participants, and I do encourage them to document what they found and how they found it, up to the point where they disqualified themselves.

Poul-Henning

  • Julian Sauer | Wed, 18 Jan 2012 12:39:04 UTC 

    I am a bit concerned; in the challenge description you wrote "Google is absolutely clueless about it", yet in the comments you announced that a group used google to identify the CPU. Personally I am using google a lot to find information about different 8-bit CPU architectures to get ideas about the different ways such a CPU can work. As far as I can see such a knowledge is essential to solve this challenge. Now, knowing that information about this CPU is on google (and apparently in a way it can be found starting with only the information given here, who knows maybe I already read about it without knowing?) how am I supposed to avoid identifying it by accident while researching 8-bit CPU architectures, which includes looking at different existing CPUs. Given this the challenge with the current set of rules seems to be a bit pointless for anyone who doesn't already have an extensive knowlede of 8-bit CPUs. I'd like to see a bit of clarification on what is allowed and what not, until then I'll stop working on this to avoid risking dequalification.

  • d12eb697 | Wed, 18 Jan 2012 13:02:32 UTC 

    I am part of the above mentioned group.

Positively identifying it by accident is impossible unless you already know enough about the architecture to, well, be able to recognize a positive identification. However, accidentally coming across references to it is very much possible. We did have an almost complete disassembly (a few things flipped here and there, a couple missing instructions, but most everything else was there), as obtained purely through guesswork and reasoning about the binary. At that point, of course, we were also researching existing 8-bit CPUs. We weren't searching specifically for this CPU - we accidentally came across a block diagram for it while searching for another, much better known CPU, because both happened to be used together in the same product and were mentioned on the same page.

It's worth noting that we learned essentially nothing from said block diagram - we already knew of all the main components, as evidenced by the disassembly. It was simply confirmation of our existing findings, and as far as I can tell, there's basically no additional information available on the net (though we did identify the specific device that this ROM was ripped from, but I think Poul-Henning knows how that happened and it certainly isn't our fault). If he thinks this disqualifies us, so be it.

Personally, I was expecting something a lot more obscure than what it turned out to be. It's by no means documented or well-known, but it's also not even remotely "not Googleable". The device is up dozens of times on eBay right now.

  • lubki | Wed, 18 Jan 2012 14:05:17 UTC 

    This is very disappointing, of course everyone is looking through google since the start to find out more about this. Google and research was not denied in the challenge.
I am also disappointed that the author of this challenge did not implement the processor himself and that there are actual products on ebay with it in!! Aliens on ebay?? Very lazy. I think the comment above by d12eb697 is enough for all of us. 
I have *no* idea what this is and I have been staring at this for days now.

  • Poul-Henning Kamp | Wed, 18 Jan 2012 14:08:14 UTC 

    As I said, this is an unfortunate situation.

Despite my best due diligence, that particular block diagram had not shown up during the research I did for this piece, and it quite does throw a spanner in the works as far as the competition goes.

I certainly won't dispute the claim that this group had an "almost complete disassembly," although I have not seen any proof of that, only a couple of snippets of their disassembly which does have some minor issues.

If they had only sent me the solution before starting their Google Sleuting, they would have been clear and amazing winners.

Fortunately, this is a challenge for and between gentlemen, so lets be gentlemen:

If the group writes up an article about how they did this feat, explaining which rules of deduction led them to which conclusions, what properties of executable code they thought about, which patterns were they looking for and so on ...

...then I will do my damnest to get the editor of ACM Queue to publish their article.

This will probably take at least a couple of weeks, and in the meantime the rest of you can keep wracking your brains on the contest.

Is that fair and workable solution ?

Poul-Henning

  • rstos | Wed, 18 Jan 2012 14:25:10 UTC 

    I'm halting work on this and I urge others to do so also.
It seems there is a clear winner and the rules have changed when the quiz is underway.
You made a mistake where you said google does not know anything about this chip and you penalize these people because they were honest and showed you a block diagram when they had already RCEd it?

  • Poul-Henning Kamp | Wed, 18 Jan 2012 14:37:58 UTC 

    I did my best to find information about this processor and I did not find the page they did.  It may not even have existed at the point in time where I wrote the article since Queue had a quite long lead-time on this piece.  (Despite rumours to the contrary, I have not memorized all of Google, so I really did not know this page existed.)

The contest quite clearly asks what we can tell from only the ROM image, and therefore using any other information about the device should be obviously off limits.  If you think that is "changing the rules while underway" then you clearly don't understand the rules of a contest between gentlemen.

If you want to stop, feel free to, but other people might still want to scale this mental mountain, even though they'll find footprints at the top.

(Think if it as a 128x128 soduko if that helps :-)

  • Kimse | Wed, 18 Jan 2012 19:14:46 UTC 

    First of all, nice competition, I do not my self have the skills to participate in this competition (tho I did identify some what I think is jump commands, at the beginning)

But will the correct answer be revealed later?

  • Poul-Henning Kamp | Wed, 18 Jan 2012 19:37:33 UTC 

    In a sense I would prefer not to see complete solutions published, but instead see methods and tools published.

  • rstos | Thu, 19 Jan 2012 06:55:52 UTC 

    What is the status now? Is there winner to this quiz?

  • Poul-Henning Kamp | Thu, 19 Jan 2012 08:06:01 UTC 

    Well, being as it is that I had no idea where to put the goal-posts, it's pretty hard to declare somebody a clear winner isn't it ?

I have not received any indication that rivals the claims of the above mentioned group, so up until the point where they broke the rules of the challenge, they were probably the prospective winners.

  • Julian Sauer | Thu, 19 Jan 2012 12:27:08 UTC 

    Instead of clarification on the rules there is only more confusion:

d12eb697 claims the group found the CPU by accident while searching for another CPU
Poul-Henning Kamp responds with "If they had only sent me the solution before starting their Google Sleuting, [...]". If there is no reason to question d12eb697 claims, this is a silly statement; there is no way the group could foresee this. I assume the group contacted Poul-Henning Kamp as soon as they found the information (why should they contact him with only an almost complete solution otherwise?), which is the best action they could have taken, opposed to keeping this secret to gain an advantage.

Poul-Henning Kamp also claims "The contest quite clearly asks what we can tell from only the ROM image, and therefore using any other information about the device should be obviously off limits." after writing "It is an oversight on my part that this was not mentioned, since it obviously is something we would find out while investigating the hardware". While not related to information being on google, this shows that the rules are all but clear.

Adding to this, that the device in question seems to be some consumer device or at least something "up dozens of times on eBay right now", I can only conclude that this challenge was neither carefully planned nor carefully run. It looked like an interesting challenge but with all this, continuing seems pointless.

  • rstos | Thu, 19 Jan 2012 13:13:26 UTC 

    Julian: I have already deleted my work directory and most of my students have done so also.

This has moved from an interesting challenge for them to learn about unknown processors on to a lesson on how NOT to run such a challenge.

  • Poul-Henning Kamp | Thu, 19 Jan 2012 15:57:09 UTC 

    There is a reason this was called  "a challenge" which is not the same as "a competition".

If you care to read the article, it should be quite evident for you, that the challenge was about broadening our understanding of code and computers, adding to our sum of human knowledge.

It should also be quite obvious that there is no way I can prevent anybody from cheating or breaking the rules of the challenge, in fact, I was quite worried that somebody would come out and say "Hey I wrote that, its ..." and ruin the challenge.  That is why the challenge is set up as a "gentlemans challenge".

If you don't care to participate, don't participate, it's entirely voluntary.

If you don't want to abide by the rules of this challenge, at least be a gentleman, and don't ruin it for others.

The group in question broke the rules, it is evident from the material they sent me, that they already quite early tried to identify the device using searches on the web.  If you want to ace the challenge and identify the device, you do it by analyzing the program, and from the program *alone* find out what the computer does.

This particular ROM image is pretty unique in the world, in the sense that we have no CPU documentation for the computer that runs it.  Probing our knowledge and understanding of code using a CPU which people had heard about or read about, would invalidate the premise "based on only the ROM image".

Ideally, I could have designed a computer and written a program just for such a challenge, but it would not have made the challenge life-like and realistic the way this one is:  hardware and software written for educational purposes are never realistic.  This ROM image is not realistic, it is *real*.

I still think it is a damn good challenge, and I am very amazed at the skill, speed and deductions of the group who solved it in 5 days.

I am grateful for the information they shared with me, and I am even more grateful that they have not spoiled the challenge for everybody else, in that respect, they have been true gentlemen.

As for winners, I think anybody who manages to solve some part of this challenge will feel like a winner to themselves, it is not in any way an easy challenge.

But the true winners, in the sense that there can be any, is whoever publishes their methods observations and tools, and thus adds to our understanding of computers and code.

Poul-Henning

  • shawn_e | Thu, 19 Jan 2012 16:33:24 UTC 

    "cluster" comes to mind and I'm not talking about a large array of alien CPUs working together.

  • Segher | Thu, 19 Jan 2012 18:07:16 UTC 

    Hi everyone.  I am the miscreant who stumbled upon that
infernal block diagram (which btw is in the public domain
and available on many websites).

We reversed (most of) the instruction set and internal
architecture of the CPU, and some of its peripherals.
It became clear that this machine was of earthly origin,
but nothing else was apparent, not even an approximate
age, or what part of the world it is from.

Since I'm quite into computer-related archaeology, and
interested in way too many things, I soon found myself
on yet another yak-shaving expedition, as always seems
to happen.  Then suddenly, O Fortuna!, I was looking at
a block diagram that matched everything we knew about
our alien CPU in detail.  That gave us a name for this
CPU but nothing much else.

Us being human beings, we threw that name into google,
not expecting much (we were told we wouldn't find anything,
after all!)

Unfortunately that ends up identifying the device this
CPU is from.

Then we contacted phk.

We did not "cheat" in any way.  The challenge is to find
out what we could from the binary alone; that is what we
did.  When we could no longer adhere to the rules, through
no fault of our own, we were open about that.  Poul sent
us the schematics of the device, so there is no way we
can honestly reverse any more of it; and I do not find
looking further into the code driving it to be very 
interesting, given what its function is, so that's the
end of that as well.

But.  This was quite a nice challenge for us, and it's
really a weird historical computing artefact.  I do
encourage everyone else to keep looking at it and discover,
well, whatever there is to discover, and hopefully your
journey will not be stopped short by a train wreck like
ours was!


Segher

  • Poul-Henning Kamp | Thu, 19 Jan 2012 23:30:36 UTC 

    Thank you for being graceful about this.

If you ever come near Denmark, call me, and I'll show you a LOT of old computing artifacts in datamuseum.dk

Poul-Henning

  • XAD | Sat, 28 Jan 2012 08:59:37 UTC 

    I don't fell able to participate to this challenge, but I would like to mention, that there is a fundamental flaw in it: Decoding a human-produced code is far away from decoding an alien-produced code. It should be expected, that the "Hardware" and the "Software" could be based on entirely different principles: other materials, non-binary processors and logic, chaotic organization,.... As a challenge, I would have suggested to decode the DNA Processing Logic (not the DNA-Content, which is now quite well known). Even this would be much easyer, than decoding an alien-based code, since we have a good understanding of its reactions to external inputs.

  • Poul-Henning Kamp | Sun, 05 Feb 2012 21:51:28 UTC 

    Well, until we see some actual aliens, I'll refrain from speculating too how they build their computers.

I don't think it is a bad assumption that they might have binary computers, the principle has a lot going for it, so much in fact that it has out-competet all other types on this planet by a large margin.

  • Poul-Henning Kamp | Sat, 05 May 2012 19:20:04 UTC 

    This just to add a pointer to a very interesting blog post from the crew who reverse engineered the unknown CPUs instruction set in a matter of days:

http://fail0verflow.com/blog/2012/unprogramming-intro.html

  • rcf | Thu, 19 Jul 2012 10:32:24 UTC 

    Are there plans to release any solutions to this challenge? 

The failOverview team suggested they would be showing their methods but haven't posted anything on this since their introduction to the challenge in March.

  • hepp | Sat, 27 Oct 2012 14:00:23 UTC 

    I really hope there will be a approach and tools 
blog at some time. I really want a fly-on-the wall
look at how you get from this blob to something
useful.
Leave this field empty

Post a Comment:

(Required)
(Required)
(Required - 4,000 character limit - HTML syntax is not allowed and will be removed)