Radiation-hardened quine | Hacker News Reader

Radiation-hardened quine

github.com

231 pointsepsylon71 comments

I was curious how well this quine would withstand having more than one character removed, so I performed a test. I did 1000 iterations removing 2 characters each time, then 1000 more removing 3 characters each time, and so on.

Here are the results up to 23 removals: http://i.imgur.com/PwWN7Z7.png

Nice, Love it when people actually perform experiments! :D In how many cases was the wrong output still functional?

Neat! Was each test of n random 1-character removals, or 1 removal of an n-character run?

The first one.

Nice!

This reminds me of a work I did as an undergrad which landed in a paper called "Can a Program Reverse-Engineer Itself?". The idea is to take any program/function and make it a quine so you can retrieve its original code even if it has been obfuscated. You can find the paper here: http://pablo.rauzy.name/research.html#imacc11.

I can't read this code at all, but, does this code basically contain the same code twice, so if something from the first half is removed the second half saves it?

I didnt look at the code and am not knowledgeable in this kind of coding but unless I am wrong, if the program simply would contain the same code twice each of these 2 codes would have to contain the same code twice ad infinitum.

If we follow your reasoning than quine itself is not possible.

Yes, Line 15: /#{eval eval if eval==instance_eval}}/.i rescue##/

They are checking the two instances and rescuing the corrupted one. But how exactly it works is beyond me.

Also, in line 17, I think it's running whichever of the two codes is longer (since the longer one is the one that didn't have a byte deleted)

    eval eval"[eval||=9,instance_eval||=9].max_by{|s|s.size}#"##"

See the max_by ... size part

Yes, and I was thoroughly disappointed by this result. So - new challenge: a radiation hardened quine in less than two times the characters of the equivalent non-radiation hardened version.

Fascinating exercise. "Deleting one character" seems a phenomenally unlikely outcome of radiation, though.

A harder task might be "Randomly delete, add or mutate a single character".

We had a few similar tasks on CGSE, e.g.

• http://codegolf.stackexchange.com/q/4486/15

• http://codegolf.stackexchange.com/q/18087/15

Addition and deletion anywhere but the end seems overwhelmingly unlikely.

Depends on how the code is stored in memory ... with ropes addition or deletion anywhere could happen.

True! But:

1) it's still less likely - most of the data is almost certainly characters of content, not sizes;

2) it's unlikely to be robust against flipped bits in pointers in the rope structures (even if implemented as indexes);

and 3) there is no reason to expect it to be limited to one byte (if an addition or deletion happens, "more than one byte" is far more likely than "one byte").

Granted it's not "deleting" a character but here, if you haven't seen it: https://blogs.oracle.com/ksplice/entry/attack_of_the_cosmic_...

That seems to be a flipped bit, by far the most likely kind of problem due to radiation.

Corrupting one bit is likely but if the rest of your system is not radiation hardened it isn't very helpful.

Yes, my objection wasn't that this failed to be a practical complete solution to radiation, but that there wasn't really a tie to radiation at all.

I agree, flipping random bit is more likely. I.E. mutating random character into some other random character (does not have to be printable one). This also has a pretty strong assumption that Ruby itself is not corrupted.

Wouldn't radiation flip a bit, rather than remove a character?

Here's the google translate link to his blog post about it.

My favorite part: "Ruby I terrible."

http://translate.google.com/translate?sl=auto&tl=en&js=n&pre...

Japanese is Subject-Object-Verb order, so it was probably "My Ruby (is) terrible". But I don't know Japanese so I can't tell you for sure.

Chinese would also drop the verb in this case, so I'm assuming they might do that in Japanese as well.

Ruby is the subject in that sentence, not sure why gtranslate injects an "I". I'd translate it as "Ruby is scary, isn't it?"

Could also be 'surprising'. With the context of the sentence before it is basically, "I thought this would be hard to write. Ruby is surprising."

Also, the author is a contributor to ruby on github, so I doubt he is negative towards the language.

http://jisho.org/words?jap=%E6%81%90%E3%82%8D%E3%81%97%E3%81...

Yes it's one of those "funny" words in Japanese that is highly context sensitive, so you're probably right.

Yeah.. 恐ろしい is kind of a "Wondrous and terrifying" blend

Chinese and Japanese grammar have very little relation to each other - about as much as Chinese and English. (The alphabets are, of course, very similar, as the Japanese adopted Chinese characters.)

The Japanese use Chinese characters. The Japanese also have alphabets. (At least two.) But Chinese characters aren't exactly an alphabet and the Japanese don't use Chinese characters directly as an alphabet, though many characters are based on Chinese ones.

Since we're being technical, Japanese does not have any alphabet as such; an alphabet has, by definition, a 1 to 1 correspondence between a single character and a sound. Japanese uses syllabaries ('kana' in Japanese), where almost all characters represent more than 1 sound. Hiragana is typically used to write Japanese words and grammatical particles, while katakana is typically used to write foreign words and for special emphasis, roughly analogous to how boldface type is used in English. Both of these kana are derived from Chinese characters, greatly simplified, though the relationship is somewhat distant.

Japanese also uses a third writing system called kanji, also not an alphabet, whose name literally means "Han [Chinese] characters" in Japanese. Kanji are logographs, where one character represents one entire word or concept rather than sounds.

Most kanji are identical or very similar to modern Chinese characters and are readily intelligible to a Chinese reader, at least in a general sense, though some have diverged a bit.

Grammar is another matter entirely. Japanese is a language isolate, a language that is not related to any other known language. (Someone will reply that it's distantly related to Korean, but this is a fringe theory in linguistics that is not widely accepted.) Chinese and Japanese are not grammatically related at all, and any similarity between their syntaxes is coincidental.

> an alphabet has, by definition, a 1 to 1 correspondence between a single character and a sound.

Do any languages have an alphabet according to this definition?

Korean?

IIRC Hangul has some weird pronunciation quirks depending on where some letters are in a syllable.

At the least, Korean has voiced-versus-non-voiced-depending-on-word-position changes, and IIRC there are other similar rules (about changing pronunciation in certain contexts) as well.

Cyrillic-using languages generally do.

The 'o' in Russian is pronounced 'a' half of the time (non-scientific estimate). :(

Finnish almost does. There are minor exceptions, though.

>a 1 to 1 correspondence between a single character and a sound.

While you're correct that the Japanese writing system is not an alphabet, I feel like your definition here is so vague it almost contradicts your point. After all, each kana character has a much closer correspondence with a particular "sound" than many actual alphabets.

So to clarify, the characters of an alphabet (notionally) correspond to particular phonemes.

> Japanese is a language isolate, a language that is not related to any other known language. Someone will reply that it's distantly related to Korean, but this is a fringe theory in linguistics that is not widely accepted

When using some strict definition of "related" (e.g. "neither language is a strict descendent of the other"), that may be true, but anybody that's studied both languages has probably noticed that there's an eery similarity between the two, even if it's merely the result of many centuries of cross-pollenization....

My own experience is not so great, I've only studied Korean a bit, but I did study it in Japanese (which I know fairly well), and the similarity made it a lot easier, because so many things corresponded 1-to-1... However Korean friends that are fluent in Japanese constantly rave about how easy it was for them to learn, not just because of the huge amount of shared Chinese-derivative vocabulary (many words are completely identical, with formulaic changes in pronunciation), but because the whole structure of grammar, sentence/conversation-planning, idioms, etc, is so similar that a huge proportion of their Korean instincts pretty much just work as-is in Japanese.

Continuing on,

Spoken Japanese and Chinese have little to no relation, except for Chinese words imported into Japanese.

Hiragana, however, is derived from Chinese characters thousands of years ago. The Chinese characters were used in Japanese writing to write words phonetically.

See http://en.wikipedia.org/wiki/File:Hiragana_origin.svg

The whole paragraph can be translated like this:

"I didn't really think I'd be able to write this [program], but somehow I was able too. Ruby is scary, isn't it? I wonder if you could write this in another language?"

Exercise for the reader, make a quine that still works even if any one character is mutated (by 1 bit or 8?), rather than deleted.

That definitely wouldn't work with this strategy (two copies), because you wouldn't be able to tell which copy was the mutated one. Error-correcting codes to the rescue. :)

couldn't one make 3 copies and take the two that are equal as non-modified?

So like above said, error correction for at most one error.

2 copy + one hash could do the same job?

Hard mode: flip bits in the interpreter's process memory as it's running.

Extreme mode: Run this code on an abacus.

Olympic mode: while drunk.

Or in the program counter or ALU, etc.

Depends on how you define "works." The program continues to output the original source code after the deletion, and ceases to be a quine. Still a very cool trick though :)

But reverting to the original source gives the program a stability property that will maintain functionality through multiple generations. Outputting the modified source would cause the program to accrue errors over time, meaning eventually entropy would win.

Good point :)

Interesting! Does anyone know of a language or operating system that uses Reed–Solomon error correction on every file?

https://en.wikipedia.org/wiki/Reed–Solomon_error_correction

Or to top that, imagine a computer where the entire memory space, perhaps shared with persistent flash memory, was encoded in this manner, so that even the filesystem was protected against bit flips.

When I was doing Mac repair a few years back, the majority of the PowerMac G5s that came through the doors died premature deaths for two reasons: the ram was in a bad spot which caused the board to bend and crack on insertion, and the ram was non-ECC so it was notoriously difficult to isolate a bad ram chip. It was the most unreliable Mac I ever diagnosed, by perhaps an order of magnitude.

Contrast that with the Mac Pro, which used ECC and was so much more reliable that I don't remember seeing a single Mac Pro fail in the 3 years I was there.

Imagine how stable a Reed–Solomon computer would be..

ZFS (the file system) goes to some fairly extreme lengths to validate data. It effectively doesn't trust anything past the south bridge.

> Does anyone know of a language or operating system that uses Reed–Solomon error correction on every file?

A while back, after losing some personal photographs to bit rot, I became curious about this and did some experimentation with RS. The biggest drawback I found was that even with a relatively fast processor it is slow compared to typical disk read/write speeds. I concluded that the ZFS approach of RAID + checksums would be preferable.

In the early 1970's I implemented the driver for, and programs using, a digital videotape drive (IIRC, it incorporated an Ampex 2 inch reel-to-reel recorder, and used the sound track for positioning information). It used hardware Reed-Solomon error correction (IIRC, it was capable of correcting up to 11-bit errors). It stored a massive (for the time) database of scanned drawings for a number of aircraft maintenance manuals.

In safety-related system you usually don't try to correct bit flips (at least in my niche), but you've got lots and lots of mechanisms ensuring that bit flips are discovered. Even more, hardware faults like stuck-at bits and so on need to be discovered, as well.

The downside is that all those checks are slow.

For more info on this search for "defensive programming", "Immunity-aware programming" and "preventitive programming". Several hardware companies have manuals/rules for programming in harsh environments.

Even if you're not into hardware it's worth a look, lots of cool tips.

  $ git clone the_quine
  $ cd the_quine
  $ ruby the_quine
  The program 'ruby' can be found in the following packages:
   * ruby1.8
   * ruby1.9.1
  # shit I don't have ruby
  $ sudo apt-get install ruby1.9.1
  # 200 bytes/s, terrible
  # ... what's going on? Ah finally.
  $ touch output
  $ ruby rbquine.rb > output
  $ diff rbquine.rb output
  # nowt

This would be much easier to understand if GitHub had proper ruby syntax highlighting. Just yesterday I was testing this, it appears they use very simplistic algorithm for parsing Ruby string interpolation - probably just regexes, which cannot handle nesting.

https://gist.github.com/tomprimozic/9113077

Ironically, Linguist+Pygments, the detection and highlighting engine, is a Ruby tool.

Pygments is a Python tool, accessed through RubyPython* (for which I should really make sure it still works with Ruby 2.1 and maybe start trying to figure out how to make it work with Py3.)

We have a few crashes that I can't figure out (but am putting in the test suite).

* https://bitbucket.org/raineszm/rubypython/src

same author wrote a 50 language quine: https://github.com/mame/quine-relay

I recommend reading specs for low power digital radio protocols like WSPR for ideas around basic error correction. Just something I did recently and was fun.

I looked at his git profile, I recognised the name: Yusuke Endoh - multiple IOCCC winner. Here is one of my favourites:

http://www.ioccc.org/2012/endoh1/hint.html

i wonder how far this can be taken... e.g. flipping or setting a random string of bits that would be physically contiguous in hardware as if a real neutron came smashing into the memory... if doing it during run can be achieved etc.

how about a real native app with instructions? i'd never expect something as high level and wooly as ruby in systems that will be exposed to radiation. that's just asking for failure imo... how robust is the interpreter for instance?

A friend of mine writes firmware for embedded devices like automatic door controls. Besides having very well designed and redundant hardware (multiple PSUs etc.) the software does a lot of things to keep itself running robustly. For example, the microcontroller regularly tests its own memory for bad blocks and compensates accordingly - similiar to what flash memory controllers do.

So yeah, even if you don't go into space or inside a nuclear reactor software can be written to tolerate a lot of harware failures.

thats interesting to know... i think you misunderstand me though. neutrons rain down on your hardware right now from deep space with significant energies... nuclear reactors aside.

this is the primary reason afaik for things like ecc and encasing your hardware in boro-silicate glass...

If you had asked me I might've said this was impossible.

Reply on news.ycombinator.com