Mateon1(Mateusz Naściszewski)

Karma: 53

Mateon1 26 Sep 2022 20:55 UTC

1 point

in reply to: Rafael Harth’s comment on: LW Petrov Day 2022 (Monday, 9/26)

The button shows up for me despite low karma. I have looked through the client-side code, and found this snippet:

const currentKarmaThreshold = getPetrovDayKarmaThreshold()
const disableLaunchButton = !userCanLaunchPetrovMissile(currentUser) 

const beforePressMessage = <p>press button to initiate missile launch procedure</p>
const afterPressMessage = disableLaunchButton ? <p>You are not authorized to initiate a missile strike at this time. Try again later.</p> : <p>enter launch code to initiate missile strike</p>

This probably means Mawrak is encountering some sort of Javascript error, since the code indicates the button should only reject the launch attempt after you press it, not before.

Mateon1 27 Jul 2022 2:03 UTC
3 points
0
in reply to: anonymousaisafety’s comment on: Eavesdropping on Aliens: A Data Decoding Challenge
I actually did not read the linked thread until now, I came across this post from the front page and thought this was a potentially interesting challenge.

Regarding “in the concept of the fiction”, I think this piece of data is way too human to be convincing. The noise is effectively a ‘gotcha, sprinkle in /dev/random into the data’.

Why sample with 24 bits of precision if the source image only has 8 bits of precision, and it shows. Then why only add <11 bits of noise, and uniform noise at that? It could work well if you had a 16-bit lossless source image, or even an approximation of one, but the way this image is constructed is way too artificial. (And why not gaussian noise? Or any other kind of more natural noise? Uniform noise pretty much never happens in practice.) One can also entirely separate the noise from the source data you used because 8 + 11 < 24.

JPEG-caused block artifacts were visible while I was analyzing the planes of the image, that’s why I thought the bayer filter was possibly 4x4 pixels in size. I believe you likely downsampled the image from a jpeg at approximately 2000x1200 resolution, which does affect analysis and breaks the fiction that this is raw sensor data from an alien civilization.

With these kinds of flaws I do believe cracking the PRNG is within limits since the data is already really flawed.

(1) is possibly true. At least it’s true in this case, although in practice understanding the structure of the data doesn’t actually help very much vs some of the best general purpose compressors from the PAQ family.

It doesn’t help that lossless image compression algorithms kinda suck. I can often get better results by using zpaq on a NetPBM file than using a special purpose algorithm like png or even lossless webp (although the latter is usually at least somewhat competitive with the zpaq results).

(2) I’d say my decompressor would contain useful info about the structure of the data, or at least the file format itself, however...

...it would not contain any useful representation of the pictured piece of bismuth. The lossless compression requirement hurts a lot. Reverse rendering techniques for various representations do exist, but they are either lossy, or larger than the source data.

Constructing and raytracing a NeRF / SDF / voxel grid / whatever might possibly be competitive if you had dozens (or maybe hundreds) of shots of the same bismuth piece at different angles, but it really doesn’t pay for a single image, especially at this quality, especially with all the jpeg artifacts that leaked through, and so on.

I feel like this is a bit of a wasted opportunity, you could have chosen a lot of different modalities of data, even something like a stream of data from the IMU sensor in your phone as you walk around the house. You would not need to add any artificial noise, it would already be there in the source data. Modeling that could actually be interesting (if the sample rate on the IMU was high enough for a physics-based model to help).

I also think that viewing the data ‘wrongly’ and figuring out something about it despite that is a feature, not a bug.

Updates on best results so far:

General purpose compression on the original file, using cmix:
```
\time ./cmix -c /ztmp/mystery_file_difficult.bin /ztmp/mystery_file_difficult.cmix
Detected block types: DEFAULT: 100.0%
2100086 bytes -> 760584 bytes in 5668.77 s.
cross entropy: 2.897
5566.69user 105.07system 1:39:57elapsed 94%CPU (0avgtext+0avgdata 18968788maxresident)k
30749016inputs+5592outputs (3812631major+12008307minor)pagefaults 0swaps
```
Results with knowledge about the contents of the file: https://gist.github.com/mateon1/f4e2b8e3fad338405fa793fb155ebf29 (spoilers).

Summary:

The best general-purpose method after massaging the structure of the data manages 713248 bytes.

The best purpose specific method manages to compress the data, minus headers, to 712439 bytes.

Mateon1 26 Jul 2022 10:08 UTC
13 points
0
in reply to: Mateon1’s comment on: Eavesdropping on Aliens: A Data Decoding Challenge
Morning progress so far:

I figured out how the values (and the noise) are generated.

The source image is an 8-bits per pixel color image, the source pixel value is chosen from one of the color channels using a bayer filter, with a blue filter at 0, 0.

The final value is given by: clamp(0, 2**24-1, (source_value * 65793 + uniform(0, 1676))), where uniform(x, y) is a uniformly chosen random value between x and y inclusive.

Without cracking the noise source, the best we can do to encode the noise itself is 465255 bytes.

...because 347475 pixels in the image have non-255 values, and log2(1677^347475) = 3722036.5 bits.

The best I could do to encode the bulk of the data is 276554 bytes, again with the general purpose zpaq compressor.

Aside on attempted alternative compression methods for the bulk of the data:

Image compression did quite poorly here, I thought adam7 interlacing would help compression due to the bayer filter pattern, but png did not perform well. With zopflipng + pngcrush the best I could achieve was 329939 bytes.

This gives an approximate lower bound of 741809 bytes without either modeling the actual data better, or cracking the noise source. This does not include the data needed to describe the decompressor and glue all the data together into the original bitstream.

Mateon1 26 Jul 2022 0:07 UTC
11 points
0
in reply to: Mateon1’s comment on: Eavesdropping on Aliens: A Data Decoding Challenge

I have further discovered that in the bulk of the data, the awkward seventh bit is not in fact part of the values in the image, it is a parity bit. My analysis was confused by counting septets from the beginning of the file, which unfortunately seems incorrect.

Analyzing bi-gram statistics on the septets helped figure out that what I previously believed to be the ‘highest’ bit is in fact the lowest bit of the previous value, and that value always makes the parity of the septet even.

I was trying to ignore the header for now after failing to find values corresponding to the image width and height, but it looks like it’s biting me in the ass right now.

Analyzing the file more carefully:

The first 78 bits are the ‘prelude’, presumably added by the transmission system itself to estabilish a clock for the signal.

All following bits are divided into septets, with each septet’s lowest (last) bit being a parity check.

But: the first 37 septets have inverted (odd) parity (It’s possible it’s metadata for the transmitting system itself).

The next 50 septets constitute some kind of header (with even parity).

The remaining septets are image data (with even parity), four septets per pixel, most significant first. This means the image has 24-bit depth.

There’s a rogue zero bit at the end of the transmission to make things a multiple of 8 bits. Note that the intern’s code does not explain the last zero bit. The code would not output extra data at the end, it would truncate the file if anything, so the zero bit must have been part of the transmission.

Curiously, by removing the data mentioned in the spoiler and packing everything into nice big-endian values, zpaq compresses the file worse than it does the original file. Just the main section of the file compresses to 850650 bytes.

Mateon1 24 Jul 2022 22:32 UTC
10 points
0
in reply to: Mateon1’s comment on: Eavesdropping on Aliens: A Data Decoding Challenge
I sat down before going to bed and believe I have made some more progress.

I experimented with what I called the sign bit in the earlier post, and I’m certain I got it wrong. By ignoring the sign bit, I can reconstruct a much higher fidelity image. I can also do a non-obvious operation of rotating the bit to least significant place after inverting. I can’t visually distinguish the two approaches, though.

I wrote a naive debayering filter and got this image out: https://i.imgur.com/e5ydBTb.png (bit rotated version, 16-bit color RGB. Red channel on even rows/columns is exact, blue channel on odd rows/columns is exact, green channel is exact elsewhere.)

You can reverse image search that image to find that it’s a standard stock photo of bismuth, example larger but slightly cropped version: http://blog-imgs-98.fc2.com/s/c/i/scienceminestrone/Bismuth.jpg

Finding the original image would definitely help, even if it wouldn’t fit the spirit of this challenge.

I haven’t yet tried going in the reverse direction and seeing how much space this saves—doing this properly is tricky. I’m not aware of any good, ready-to-use libraries that provide things like context modeling and arithmetic coding, so writing a custom compressor is a lot of work.

In fact, I believe it may be worth trying to break the author’s noise source on the sensor. Most programming languages use a fairly breakable PRNG, either a xorshift variant or an LCG. But this may be a dead end if cryptographic randomness was used. Again, this wouldn’t fit the spirit of this challenge, but it would minimize description length if it worked.

Mateon1 24 Jul 2022 18:01 UTC
21 points
0
on: Eavesdropping on Aliens: A Data Decoding Challenge
I believe I had a good start analyzing the file, although I’m currently slightly stuck on the exact details of the encoding.

Spoilers ahead for people who want to try things entirely by themselves.

My initial findings were that the raw file easily compresses from 2100086 bytes to 846149 bytes with zpaq -m5, probably hard to beat its context modeling with other compressors or even manual implementations.

I wrote a Python script to reverse the intern’s transformation and analyzed the bits, looks like the file is largely organized into septets of data. I dumped those septets in all the ways that made sense (inverted bits, inverted order of bits) into a file. None of them compressed better than the source.

I opened those files with GIMP as raw data files, and noticed that at 4000x600 8-bit grayscale with a small offset for the header it looks like some sort of 2D data, but it’s extremely noisy. There are lots of very flat areas in the file, though, which is why it seems to compress so well. Likely a threshold of some sort on the sensor data.

By only taking every fourth septet I could form four 1000x600 grayscale images. One of them seems to have actual structure (I presume it’s the most significant septet), the rest are dominated by noise.

It’s recognizable as a picture of a piece of crystalized bismuth. (https://i.imgur.com/rP5sq56.png) :::

There also seems to be some sort of pattern in the picture pixels similar to the raw data behind a Bayer filter in a camera. It might be a 2x2 or a 4x4 filter, I can’t quite tell. It could also just be some sort of block artifacts from the picture source (which wouldn’t be present in raw sensor data from aliens, but the author needs to source this image somehow).

The binary encoding seems to involve a sign bit in each septet if I’m interpreting things correctly, but I’m not sure how to combine septets into a sensible value yet.

I’m currently stuck at this point and won’t have time to work on it more this evening, but seems like good progress for one and a half hour.