5 ms·

This was the day that Mike learned the difference between theory and practice: In theory, there is no difference between theory and practice; but in practice, t

This was the day that Mike learned the difference between theory and practice: In theory, there is no difference between theory and practice; but in practice, there is. When I read the challenge, and saw that arbitrary Unix programs were allowed, my first idea for a compressor was to scan the OS software for snippets of data that match the source data. Of course, that was 10 years ago. Today, in the Cloud world, I'd just write a decompressor that connects to my system over the network and retrieves the source data.

recursive 14y ago
You can be pretty sure that you wouldn't find the target in the OS software. For a well constructed output file, that has about the same likelihood as a randomly generated cryptographic hash collision. As for your cloud solution, that could be defeated by running the decompressor offline.
- mcherm 14y ago
  you wouldn't find the entire target but you would find file in the operating system that had subsets of the target file.
  - meanguy 14y ago
    Sigh. Claude Shannon is rolling in his grave.
    - shimon 14y ago
      Why is this an invalid approach? If you have an agreed-upon OS installation, you've got at least several hundred megabytes of binary data from which you can extract sequences for a lookup dictionary. To compress, you locate largest substrings of the input that also appear somewhere in the OS data. For example, you might find that bytes 1000-2000 of the input data are the same as bytes 4528-5528 of /bin/ls. Then you just need a program that can extract this byte range from /bin/ls and fill it in at the appropriate place. Of course, it isn't a given that you will be able to find a sufficiently large overlapping substring in the OS binary data. And it may not be allowed to assume an agreed-upon OS installation, although it was OK to assume that gunzip was available. And finally, doing this sort of largest-overlapping-substring search could be very very slow. The real key here is that the challenge is about compressing one specific random file. It's clearly impossible to write a compressor that can represent ANY sequence of N bytes in fewer than N bytes including the decompressor. But this challenge is constrained to reconstructing a single input file, not handling arbitrary inputs. If the input files are random, and you keep asking for them, there's a tiny chance you'll get one with enough repetition that even gzip could compress it. If you can key against a large set of reference data, your odds improve significantly. So, I don't know if this is a practical approach given the restrictions of the contest, the cost of entering, and the expected payoff, but I would say that if it is plausible to use a large body of OS files for lookup, this could be a winnable challenge.
      - romaniv 14y ago
        Of course, it isn't a given that you will be able to find a sufficiently large overlapping substring in the OS binary data. It seems that it's a given that you will not find that substring. The larger it is, the less likely you will find it and the less likely it will repeat in the uncompressed file. http://news.ycombinator.com/item?id=4617983 http://news.ycombinator.com/item?id=4617983
        shimon 14y ago
        Unlikely but not impossible. Note that the substring does NOT need to repeat in the uncompressed file; it just needs to be possible to say "copy bytes X through Y of /bin/ls here" in fewer than Y-X bytes. I'd love to know what the odds really are, but it seems like you have some good options for improving them (e.g. ask for a really huge input file).
        recursive 14y ago
        > it just needs to be possible to say "copy bytes X through Y of /bin/ls here" in fewer than Y-X bytes It is very unlikely that the length of the sequence will be smaller than the space required to store X. Your plan is similar to saying "The input could contain long repeated segments containing only zeroes. Compress those using scheme Z. The longer the file, the more likely this is to occur.". Information theory allows us to prove that this cannot always work. In fact it is very unlikely to work for a specific randomly generated target file.
        jwecker 14y ago
        So by saying 'cannot _always_ work,' and 'very unlikely to work,' you are implicitly conceding the point- that it is possible. The question then becomes, given the size of the OS environment space (and the quality of the randomness in the originals), could one in 50 attempts actually succeed in shaving off a byte? I sincerely doubt that Mike, despite his superior knowledge of information theory, actually took the time to figure out just how good or bad the odds were. He assumed that it was fundamentally impossible, when it is in fact not impossible, just unlikely (to some unknown [to me] degree).
  - georgemcbay 14y ago
    Yes, you would find some matches with an exhaustive search, but they'd be pretty small and now you have to encode the path to get those bytes back in a form that is smaller than the byte run that matches. And good luck with that.
im3w1l 14y ago
>When I read the challenge, and saw that arbitrary Unix programs were allowed, my first idea for a compressor was to scan the OS software for snippets of data that match the source data. No this would not work. It is very simple to see this. There are more files with size n, than with there are with lower sizes. A decompressor should therefor be a surjective function from a smaller set to a larger which is impossible. This applies no matter how you construct you (de)compressor. You can have it access word lists, files on harddrive, etc. There will be at least one file it wont be able to compress and then decompress.
- lurker14 14y ago
  I was slightly vague in my oroginal post. I didn't mean "match completely the soruce data", I meant "match a part of the source data", as a standard rsync/Exchange-style block-deduplicator would do. Per the challenge, it need not work on every file, only the one the challenger chose to provide. If the challenger is not suspecting this attack, he won't know to make sure to pick one of the many source files that are resistant to the attack. Of course the compression is impossible in general, if the task is sufficiently rigorously described, which it wasn't in this case.
  - im3w1l 14y ago
    A randomly generated file will in a crushing majority of cases not be compressible in this way.

recursive 14y ago

You can be pretty sure that you wouldn't find the target in the OS software. For a well constructed output file, that has about the same likelihood as a randomly generated cryptographic hash collision. As for your cloud solution, that could be defeated by running the decompressor offline.

mcherm 14y ago
you wouldn't find the entire target but you would find file in the operating system that had subsets of the target file.
- meanguy 14y ago
  Sigh. Claude Shannon is rolling in his grave.
  - shimon 14y ago
    Why is this an invalid approach? If you have an agreed-upon OS installation, you've got at least several hundred megabytes of binary data from which you can extract sequences for a lookup dictionary. To compress, you locate largest substrings of the input that also appear somewhere in the OS data. For example, you might find that bytes 1000-2000 of the input data are the same as bytes 4528-5528 of /bin/ls. Then you just need a program that can extract this byte range from /bin/ls and fill it in at the appropriate place. Of course, it isn't a given that you will be able to find a sufficiently large overlapping substring in the OS binary data. And it may not be allowed to assume an agreed-upon OS installation, although it was OK to assume that gunzip was available. And finally, doing this sort of largest-overlapping-substring search could be very very slow. The real key here is that the challenge is about compressing one specific random file. It's clearly impossible to write a compressor that can represent ANY sequence of N bytes in fewer than N bytes including the decompressor. But this challenge is constrained to reconstructing a single input file, not handling arbitrary inputs. If the input files are random, and you keep asking for them, there's a tiny chance you'll get one with enough repetition that even gzip could compress it. If you can key against a large set of reference data, your odds improve significantly. So, I don't know if this is a practical approach given the restrictions of the contest, the cost of entering, and the expected payoff, but I would say that if it is plausible to use a large body of OS files for lookup, this could be a winnable challenge.
    - romaniv 14y ago
      Of course, it isn't a given that you will be able to find a sufficiently large overlapping substring in the OS binary data. It seems that it's a given that you will not find that substring. The larger it is, the less likely you will find it and the less likely it will repeat in the uncompressed file. http://news.ycombinator.com/item?id=4617983 http://news.ycombinator.com/item?id=4617983
      - shimon 14y ago
        Unlikely but not impossible. Note that the substring does NOT need to repeat in the uncompressed file; it just needs to be possible to say "copy bytes X through Y of /bin/ls here" in fewer than Y-X bytes. I'd love to know what the odds really are, but it seems like you have some good options for improving them (e.g. ask for a really huge input file).
        recursive 14y ago
        > it just needs to be possible to say "copy bytes X through Y of /bin/ls here" in fewer than Y-X bytes It is very unlikely that the length of the sequence will be smaller than the space required to store X. Your plan is similar to saying "The input could contain long repeated segments containing only zeroes. Compress those using scheme Z. The longer the file, the more likely this is to occur.". Information theory allows us to prove that this cannot always work. In fact it is very unlikely to work for a specific randomly generated target file.
        jwecker 14y ago
        So by saying 'cannot _always_ work,' and 'very unlikely to work,' you are implicitly conceding the point- that it is possible. The question then becomes, given the size of the OS environment space (and the quality of the randomness in the originals), could one in 50 attempts actually succeed in shaving off a byte? I sincerely doubt that Mike, despite his superior knowledge of information theory, actually took the time to figure out just how good or bad the odds were. He assumed that it was fundamentally impossible, when it is in fact not impossible, just unlikely (to some unknown [to me] degree).
- georgemcbay 14y ago
  Yes, you would find some matches with an exhaustive search, but they'd be pretty small and now you have to encode the path to get those bytes back in a form that is smaller than the byte run that matches. And good luck with that.

im3w1l 14y ago

>When I read the challenge, and saw that arbitrary Unix programs were allowed, my first idea for a compressor was to scan the OS software for snippets of data that match the source data. No this would not work. It is very simple to see this. There are more files with size n, than with there are with lower sizes. A decompressor should therefor be a surjective function from a smaller set to a larger which is impossible. This applies no matter how you construct you (de)compressor. You can have it access word lists, files on harddrive, etc. There will be at least one file it wont be able to compress and then decompress.

lurker14 14y ago
I was slightly vague in my oroginal post. I didn't mean "match completely the soruce data", I meant "match a part of the source data", as a standard rsync/Exchange-style block-deduplicator would do. Per the challenge, it need not work on every file, only the one the challenger chose to provide. If the challenger is not suspecting this attack, he won't know to make sure to pick one of the many source files that are resistant to the attack. Of course the compression is impossible in general, if the task is sufficiently rigorously described, which it wasn't in this case.
- im3w1l 14y ago
  A randomly generated file will in a crushing majority of cases not be compressible in this way.