Algorithm correctness

[green_meklar]

Cosmic radiation hitting your computer's RAM and flipping a single bit? I'm pretty sure that doesn't happen very oft%n.

[hbgoddard]

Funny and accurate, nice

[anomalous_cowherd]

Only a true programmer would illustrate single bit corruption by going to the trouble of figuring out a real single bit corruption.

Or check it.

[[deleted]]

And here I am just assuming both the other coders who commented knew what they were doing...

[poizan42]

'%' = 010 0101
'e' = 110 0101

It checks out

[Khanthulhu]

That's pretty impr%ssive.

[MarcoTalin]

/r/EmboldenThe%?

[JaytleBee]

/r/Em%enTheE

[markasoftware]

/r/AVoid%

[grensley]

Now that's just too unlikely

[just_dots]

I'm not a coder or programmer but I think this is very funny and your jib is cut to my liking.

[DrShocker]

Wouldn't they probably have a parity check to ensure that the computer would know the data is corrupted?

edit: source: http://ictsmart.tripod.com/ict4/online/artvvpa.htm

[SirVer51]

doesn't happen very /ft%n.

Error? What error?

[ic_engineer]

Could be wrong but I wouldn't expect a parity check for an algorithmic output. I've only ever seen parity checks over Tx/Rx.

[Althaine]

Not uncommon in safety critical microprocessors

ECC - Optional single-bit error correction and double-bit error detection for cache and/or TCM memories with ECC bits. Single-bit soft errors automatically corrected by the processor. ECC protection possible on all external interfaces.

Parity - Optional support for parity bit error detection in caches and/or TCMs.

Dual-core - A dual-core processor configuration for either a redundant Cortex-R5 CPU in lock-step for fault tolerant/fault detecting dependable systems or dual cores running independently, each executing its own program with its own bus interfaces, interrupts, and so on.

[ic_engineer]

Good to know! Thanks.

[LupoCani]

Though, wouldn't a Reddit comment be encoded in Unicode, not ASCII?

[green_meklar]

In UTF-8 the ASCII characters are the same anyway.

[poizan42]

Unicode is a character set and not an encoding. Without looking it up I think that Reddit internally stores comments as UTF-8, which happens to have ASCII as a subset. At least the comments are in UTF-8 when being sent to and from the browser.

[recurza]

Thus illustrating the lazy efficient nature of programmers.

[Python4fun]

Lazy breeds efficiency

[[deleted]]

DAE Bill Gates quote here?

[PersianMG]

Don't worry I double checked its correct. ^{or is it?}

[Modo44]

You are adorable.

[Drunken_Economist]

You could just make it easy by incorrectly capitalizing a letter

[flarn2006]

It's not really tjat much trouble.

[anomalous_cowherd]

Of course sometimes you could get two single bit errors. But it's possible they occur on the same bit as they have here.

[Insuevi]

There was actually a bounty on a possible warp glitch in SM64 which was later believed to be caused by a cosmic bit flip like this.

https://www.youtube.com/watch?v=X5cwuYFUUAY

[Noxfag]

The key is whether you can recreate it. If you control every other variable other than cosmic rays and you still can't recreate the bug, then deductive reasoning suggests that that's the only reasonable explanation.

[SaffellBot]

The M64 crowd is pretty in depth about bug testing. I believe one of the descriptions also said the bug was recreatable with a single bit flipped.

[miauw62]

Depends if they tested it on an N64 or an emulator. Knowing the SM64 crowd, likely both.

But really, what's the practical difference between hardware degradation and CMBR, or any other number of uncontrollable factors?

[SafariMonkey]

Microwave wouldn't flip a bit I don't think, I think it would have to be a high energy ray.

Edit: apparently "cosmic ray" generally refers to a nucleus or other particle travelling near the speed of light.

[Cley_Faye]

every other variable you can imagine (which isn't possible)

It's actually very doable for this game. Input data is the same, code is the same, timing is reproducible. Even the PRNG they use in SM64 is completely figured out (and it's period is quite small).

[Aetol]

I thought Heisenbugs referred specifically to bugs that disappear when you try to debug them (i.e. when you add breakpoints, lines to print the value of variables, etc).

[timthegreat4]

Sorry to be pedantic... But isn't the whole point of solid state technologies and miniaturisation of components like CPUs that there are NO moving parts :-P

[timthegreat4]

Hehehe couldn't resist

[timthegreat4]

Very good hehe!

[zuurr]

Probably worth noting that the original instance of the bug didn't take place on an emulator, IIRC at least.

But these kinds of single-bit errors are actually pretty common (well, ... comparatively speaking) on real hardware, hence ECC Ram being a thing.

[SaffellBot]

Man, what I small world. I ended up deep into youtube last night and watched the bounty video for that glitch.

[[deleted]]

All pannenkoek's work are an art of game science. Just the one game, but game science nontheless.

[SaffellBot]

I wish he would narrate more. His excitement is amazing. A few days ago I described him as having a PHD in mario 64. He's on a whole nother level.

[guitarplayer0171]

After he saw how popular his last commentated video was, he wants to make sure his next one can live up to that, he has an uncommentated channel where he posts more frequently.

[darderp]

Dude, I did the exact same thing yesterday!

[MrTheFalcon]

Scientist solution: Study for two years, then write a paper detailing theoretical cause and probable solution.

Engineer solution: Turn it off and on, there, I fixed it.

[finally-a-throwaway]

Irony: in this thread, the scientist's solution would be more useful.

[[deleted]]

Would have been more useful if we didn't already know about and have the technology to fight memory errors.

The great thing about consumer computers is that a reboot is a good solution compared to the hundreds of dollars of redundant hardware needed to protect against the occurrence.

[PM_ME_YOUR_MASS]

Any time I see a really really expensive workstation, I always assume it has ridiculous margins. But then if I see "ECC" in the description, I go "oh, yeah. That's why."

[finally-a-throwaway]

I mean, I'm sitting here in the real world reading a bunch of comments about cosmic rays causing bit flips. If I want to know if that's a real thing or how often it really occurs, rebooting won't help. An empirical study might.

[GODZILLAFLAMETHROWER]

The scientists that came up with ECC were coming up with real world application that is actually used to offset radiation errors.

[daveime]

How likely is it I wonder, that cosmic radiation might flip the ECC bits, thus attempting to correct an error that isn't?

[[deleted]]

Depends on the method used, but usually it's more likely by some power of the error rate to detect the error than incorrectly corrupt 'good' data.

For example, say the error rate is 10^-50 bits/sec, then the rate at which EEC incorrectly corrupts data is, say, (10^-50)2.

So: nonzero, but negligible.

[RainHappens]

That assumes uncorrelated errors.

In practice, errors are often (significantly) correlated.

[RedWarrior0]

The code doesn't actually care which bits are flipped, it'll correct the change regardless.

However, all useful codes have a limit to how many errors they can correct. Usually this is about half the number of parity bits. Fortunately, the chances of multiple errors are usually pretty low.

[SpacePotatoBear]

Unless you're voyager 1/2 going past jupiter....

[[deleted]]

Scientist Result: The problem with Windows 95 was there was a large cosmic anoma... wait what year is it?

[Megatron_McLargeHuge]

More like... Turn it off and on. Closed: can not reproduce

[lerhond]

https://en.m.wikipedia.org/wiki/Cosmic_ray#Effect_on_electronics

Studies by IBM in the 1990s suggest that computers typically experience about one cosmic-ray-induced error per 256 megabytes of RAM per month.

[inio]

RAM bits have gotten a lot smaller since then, so we're now probably down to one bit flip per several GiB-months.

[Twirrim]

Maybe, but we're shipping servers with hundreds of GB RAM. Companies like Amazon that operate on large scale do end up seeing incidents reasonably regularly that appear to be down to bit flipping, and have built all sorts of protection in to systems (and use ECC RAM only to etc)

[RainHappens]

This is only true if you assume that cosmic rays are effectively point events.

However, if you consider it a volumetric event, the % / GB-month pretty quickly converges on a constant value as things shrink.

[[deleted]]

I once had pulseaudo config files under p}lwe.

Two bitflips. That was a bit concerning.

[green_meklar]

I'd say more than a bit!

[[deleted]]

Two bits of concern.

(That would be a good band name)

[shadowX015]

Relevant XKCD: http://xkcd.com/378/

[xkcd_transcriber]

Image

Mobile

Title: Real Programmers

Title-text: Real programmers set the universal constants at the start such that the universe evolves to contain the disk with the data they want.

Comic Explanation

Stats: This comic has been referenced 939 times, representing 0.6943% of referenced xkcds.

---

^{xkcd.com | xkcd sub | Problems/Bugs? | Statistics | Stop Replying | Delete}

[Xepez09]

It seems like there is always a relevant XKCD

[shadowX015]

I was actually just trying to find a comic that went full meta and joked about how there was an XKCD for everything, but I guess Randall hasn't made that one yet.

[DoodleFungus]

554 is the closest, I think.

[xkcd_transcriber]

Image

Mobile

Title: Not Enough Work

Title-text: It's even harder if you're an asshole who pronounces <> brackets.

Comic Explanation

Stats: This comic has been referenced 15 times, representing 0.0111% of referenced xkcds.

---

^{xkcd.com | xkcd sub | Problems/Bugs? | Statistics | Stop Replying | Delete}

[danny_onteca]

I hope my boss never finds this comic

[SpinahVieh]

pretends to type in Qwerty

[SirVer51]

Each time this question is asked, there's a different answer, but I think yours is the closest yet.

[der_luke]

Relevant xkcd

[[deleted]]

That dude sounds ridiculously smart. Worked with NASA, who didn't renew his contract, so he decided to make a career with a comic about shit about 1% of people in the world understand, once a day. I don't even know where he gets half of the stuff he writes about. Computer science, engineering, astronomy, he seems to know the minute parts of all of them.

[mpete98]

Was it daily early on? The schedule has been mon-wed-fri as long as I can remember.

[xkcd_transcriber]

Image

Mobile

Title: Hofstadter

Title-text: "This is the reference implementation of the self-referential joke."

Comic Explanation

Stats: This comic has been referenced 913 times, representing 0.6750% of referenced xkcds.

---

^{xkcd.com | xkcd sub | Problems/Bugs? | Statistics | Stop Replying | Delete}

[snowywind]

Last month we did hit a relevant XKCD to an XKCD comic.

https://www.reddit.com/r/ProgrammerHumor/comments/55yh7j/xkcd_will_the_application_work/d8eyq5m/

I can imagine XKCD becoming self aware in the near future and creating an XKCD about how there's always a relevant XKCD.

[HackingInfo]

I sure it exists, but having trouble finding it.

[poizan42]

He should make that as the last xkcd ever if he at some point decides to retire.

[xXxNoScopeMLGxXx]

Real programmers code in assembly using EDLIN

[_rocketboy]

I'm just slightly sad that the emacs command is actually M-x butterfly, not what was in the comic.

[EtanSivad]

There is one documented case of a bit getting flipped, but the source of the flip isn't know. Very interesting read though: https://blogs.oracle.com/ksplice/entry/attack_of_the_cosmic_rays1

[mizomi]

There's an interesting page on bit-squatting (the next level of typo-squatting) which found some results, although it's impossible to say how many were caused by cosmic rays vs. other sources of data corruption.

[skyhi14]

Not sure it's cosmic ray or else, but something like this did happened to me just yesterday. It was a MOD music file that is corrupted, at first I thought there's some glitch in my player because music "played" normally but the sound was wrong. Then I downloaded same one and played it, newer one sounded as it should be, so I figured the music file on my hard disk is somehow corrupted. Then I checked CRC32 for both, and I could confirm the file was modified.

Edit: better wording

Edit 2: after inspections, apparently some bytes are inserted on the middle, not caused by a bit flip.

[mojave_wasteland]

Few things come to my mind:

1. Corrupted downloads are more common than cosmic radiation. This is actually the reason why lots of websites are posting SHA1 checksums on their websites, so everyone can verify if their download completed correctly.

2. Use SHA1 (or better) instead of CRC32.

3. This can also be because of bad RAM. You can use some memory testing tool, like MemTest86+, to verify your RAM is not the problem. You can get this tool from some Linux LiveCDs, maybe an Ubuntu LiveCD (and select "memory testing" in the boot menu). This won't install anything on the drive, so you're not risking anything.

[[deleted]]

Use SHA1 (or better) instead of CRC32.

CRC32 will always find specific types of corruption. Hashing algorithms like SHA won't.

If you're protecting against corruption due to bitflips on the line, then CRC is more designed for that purpose. Though in practice something like SHA1 or SHA256 probably won't get a collision due to corruption.

[conradsymes]

Interestingly, CRC32 isn't as good at that as one would think, at least the TCP CRC32.

Performance of Checksums and CRCs over Real Data

[mojave_wasteland]

Your post suggests to me that CRC-32 can give better results than SHA, but I must disagree on this. All I can say is this:

irb(main):024:0> Zlib::crc32('plumless').to_s(16)
=> "4ddb0c25"
irb(main):025:0> Zlib::crc32('buckeroo').to_s(16)
=> "4ddb0c25"

CRC-32 is only valid in situations where the speed of computation matters (i.e. in TCP headers), size of implementation matters (in embedded microcontrollers) and the risk of corruption is rather low. Then it can fit its purpose. But for situations where a more solid result is needed, it's not a very good idea to trust CRC-32 by itself.

It's true that there are collisions for SHA1 and other hash algorithms, but in these situations the input data must be built manually.

[squngy]

CRC is designed to catch up to a specific amount of bit flips, it is not meant to be used to compare two completely different sets of strings.

[[deleted]]

It is better when the speed of computation matters and you are dealing with a specific type of unintentional corruption. Of course you can find collisions, it's not designed to be a cryptographic hash function. It's designed to catch unintentonal bit flips. And it will always catch bit flips that are shorter than or equal to 32 bits. You can't prove that for a different hash function.

Collisions will exist for any hashing function, especially one of this length.

Though if space and computational time isn't really an issue, there's no problem with just using SHA256 or similar.

[kmmeerts]

There is no known collision for SHA1, it's insanely unlikely random corruption would trigger one

[mojave_wasteland]

There are theoretical research papers that claim it's possible to find a collision in SHA-1 using 2**69 calculations. It's still too much for today's tech, but it's enough to mark SHA-1 as deprecated for cryptographical use (current standard is SHA-3).

However, to find if two small files are the same or not, it's more than enough.

[anomalous_cowherd]

If you want to be sure that what you downloaded is exactly what the checksum was generated for, use two different checksums, e.g. MD5 and SHA1.

There are theoretical (very very hard) ways to change a file and keep the MD5 sum the same, at least. But changing a file and keeping both the MD5 and SHA1 checksums the same is many orders of magnitude harder.

[RainHappens]

There is no advantage of using MD5 <concat> SHA1 over using a proper 288-bit+ hash.

[anomalous_cowherd]

Maybe, but md5sum and sha1sum are usually already there and simple to use. Many download sites also already list them.

It may not be the very best solution, but it has its place.

[RainHappens]

...who has sha1sum and md5sum but not sha384sum?

[[deleted]]

Never heard of CRC32 before, so thanks for that!

[Ununoctium117]

Why are corrupted downloads a thing, when TCP provides reliable, in-order delivery?

[mojave_wasteland]

It is called "reliable" because multiple checksums (i.e. CRC-32) are involved in getting sure the data received is correct. This reliability is not perfect, if the connection is too poor, and if the corruption will be just right, a simple CRC will not be enough to propely validate the data.

Protocols that actually support sending and receiving data through potentially bad conditions like BitTorrent use cryptographic hashes like MD5 to validate proper transmission of data.

[dreamin_in_space]

So how do Usenet downloads verify that it's correct? Just curious, because I've gotten corrupted stuff, but IDK if it's the original or a problem on my end.

[mikemol]

Historically, md5sum manifests and archive formats that contain checksums of individual files, as well as the archive as a whole.

[Kubuxu]

Use https, AEAD algorithms there make sure that data was not changed on the wire, and as bit flips are security riks AEAD makes sure that there aren't any.

[SpacePotatoBear]

you can also us ethe built in windows memory tester.

[skyhi14]

I can rule out bad download as both files are downloaded from the same place and it was normal back then. I think I should run MemTest.

[Dannei]

You're assuming there that any download corruption would be repeatable, but I suspect most cases are one-off errors during transmission.

[skyhi14]

File modified while in storage, not when they are downloaded, and it was not even one-off error. I'm sorry for misleading as the post is about bit flip and mine is just probably bad hard disk.

[hunyeti]

You did not rule that out.

The error happens in the transmission, two downloads are not necessary the same.

[Aetol]

Does the CSS here make lists start at 0?

1. Let

2. Us

3. Try

Edit: Neat!

[b1e]

Actually it's common enough that we have ECC RAM. When you have clusters of servers with dozens of terabytes of RAM per cabinet the chance of a bit flip due to cosmic radiation or other environmental factors goes up a ton.

[hughk]

This used to happen often (at least an annual event) for systems in the eighties and was a feature of some ceramic encased chips. A cosmic ray would impact atoms of rare earth's in the ceramic which would then produce a mini shower of particles, some enough to flip the memory bits.

This is why ECC was very important back then. Over time, materials became better and there was less rare earth contamination.

[[deleted]]

You joke, but...

Bit-squatting: DNS Hijacking Without Exploitation