7 ms·

JavaScript-Is-Weird as a compressor

111 points by mgarciaisaia 3y ago

deleted 3y ago
[deleted]
SquareWheel 3y ago
It's not a huge surprise that gzip as a general compression algorithm didn't compress this down any further. I do wonder about a format that was specifically trained on these specific characters though, and the patterns that tend to emerge from the weird compiler. Maybe the chunks at a certain scale would be predictable and thus compressible. Of course at that point you're probably more interested in a common binary format, and should start thinking about wasm instead.
- hughw 3y ago
  The information content of the weird program is the same as that of the original cleartext, so I wouldn't expect zipping a transpiled program to compress better than compressing the original.
  - Ono-Sendai 3y ago
    Information content isn't really a well-defined concept for finite-length strings.
  - Brian_K_White 3y ago
    Another comment pointed out that there is more information or entropy in the weird version if you don't happen to be a js interpreter. The compression algorithm knows that 165427-165427 is really 165427-same, but does not know that it's really 0 and the same as all the other things that resolve to 0. There must be a lot of similar things like that in this particular case that relies on knowledge of the rules of js. I guess it's tempting to think next about adding ai to a compressor so that it could know the actual rules of js and refactor it, but I just think of the tragedy that is jbig that does OCR as part of the compression, except, gets it wrong, and the original data is lost forever without a trace. And it's built right in to some scanners and happens before the compressed output even leaves the device. The user never sees anything else. There is no better reference uncompressed version anywhere if the user did not know about the problem and override some default settings.
dclowd9901 3y ago
It might be that GZIP isn’t actually a good format with which to try to compress this data. I would think a compression algorithm that expects a rather large 8 byte character space wouldn’t be very suitable for a 4-bit space
- jrockway 3y ago
  I got a little nerd sniped by this. I wrote a program that takes an input (/usr/share/dict/words on Debian 12, specifically), and compresses it with gzip and Zstandard, and also expands its binary representation (by replacing each 1 bit with A and each 0 bit with B) and compresses that. The result is: gzip expgz zstd expzstd original 263120 421278 252449 389004 985084 So unlike in the article, expansion + compression is at least better than the original. The ratios are (smaller # better; the opposite of how most compression algorithms advertise their performance, but what the original article used): 0.27, 0.42, 0.25, 0.39. gzip and Zstandard aren't a lot different in either case. Whatever patterns that the Javascript weirdifier uses is less obvious to compression algorithms in general than just bitwise substitution. Here's the program if you want to look for bugs: https://go.dev/play/p/wwNXVzO2TO- https://go.dev/play/p/wwNXVzO2TO-
telegpt 3y ago
[dead]
ShamelessC 3y ago
> So, yeah - this isn't a good idea. If the Weird transpiler only changes the encoding of each character with a really weird equivalent, it makes a lot of sense that it doesn't compress better than the source one - the ideal scenario would be to compress the same. If your results disagree with your premise in unsurprising and obvious ways - please start your article with that so I can stop reading it.
garba_dlm 3y ago
and Golang is a clever way to build up an AI
- garba_dlm 3y ago
  ahaha, downvoted out of sight but I'm pretty sure I read this sentiment in some other comment in this site
crazygringo 3y ago
I'm actually surprised at how insanely terrible the "compression" is. Looking at the table at the end, I'm not surprised at all that the "weird" obfuscated code is ~2000x the size of the original source. But I am surprised that that the gzipped weird code is still ~25x the size of the original source, as opposed to ~0.25x for gzipping the original source. After all, the amount information in the weird code should still ultimately be approximately the same as the original source code, right? Or maybe double or something like that. I'm very surprised it's twenty-five times as much. The only reason I can guess is that the "weird" process results in information structures that are represented in an extremely hierarchical way, and gzip is built for stream compression, and is unable to find/represent/compress hierarchical structures? And if that's the case, it makes me wonder if there are any compression algorithms which are able to handle that better? That might not be based on "dictionary words/sequences" as much, but rather attempting to find "nestable/repeatable syntax patterns"?
- thristian 3y ago
  Compression is all about detecting patterns in the data, usually with some kind of sliding window of past data, used to predict future data. For gzip in particular, this sliding window has a fixed size of 32KB. If the "weird" version is ~2000× the size of the original source, gzip would need a sliding window of ~2000× the size (about 64MB) to obtain equivalent compression.
  - wizzard0 3y ago
    Also, an encoder like these can inject any amount of entropy (eg replace "0" with "100500999-100500999") which gzip can reduce to "100500999-same" but without knowledge of JS semantics has no chance to reduce to either "0" nor the nearby "172913211-172913211")
  - josephg 3y ago
    > For gzip in particular, this sliding window has a fixed size of 32KB. I'm surprised people keep reaching for gzip for this sort of comparison. LZ4 / zstd compress better at the same compression speed, and zstd and brotli compresses much better. Brotli is also supported in all modern browsers. There's basically no reason to use gzip in new software. (With the exception of compressing for the web - at least until zstd makes it into browsers.)
koito17 3y ago
Just for fun, I decided to pass the output.js file through Google Closure Compiler's advanced optimizations. It does a surprisingly good job at reconstructing part of the strings. % npx google-closure-compiler -O ADVANCED --js output.js (()=>{})["co"+(1/0+[])[4]+"structor"]("co"+(1/0+[])[4]+... Not pasting the full thing. But it reduces the output.js file from ~118 KiB to ~9.92 KiB, which is pretty good! There is technically not much stopping the compiler from inferring that 1/0 === Infinity, recognizing (1/0+[])[4] is free of side-effects, and eventually concluding its safe to substitute the whole expression with "n". Google Closure already has optimizations for string concatenation, so if it were able to perform an optimization pass with Infinity, then it would also be able to emit the string "constructor" instead of "co"+(1/0+[])[4]+"structor"
- woneton 3y ago
  $ wc -c output.js 117708 output.js $ uglify-js output.js -c unsafe | node Hello world! $ uglify-js output.js -c unsafe | wc -c 2740 $ uglify-js output.js -c unsafe | cut -c 1-60 (()=>{}).constructor("conso"+"".constructor["from"+(()=>{}). $ uglify-js output.js -c unsafe | gzip | wc -c 192
- pjc50 3y ago
  Interesting. I wonder if an even more effective approach to unobfuscation would be an "anti-jit" compiler; since what we're interested in is the actual execution flow, can we leverage all the browser's optimization engine to pull that out for us? Do the various JIT engines use an intermediate representation (IR) and what does it look like?
  - circuit10 3y ago
    V8 starts with interpreting bytecode (Ignition), then hot code gets tiered up to a non-optimising JIT without an IR (Sparkplug), and even hotter code goes an optimising one with an IR (TurboFan) That way it can start executing quickly and not waste time on compiling/optimising things that only get run a few times
- Alifatisk 3y ago
wizzard0 3y ago
1) The title is a clickbait, but 2) Thanks for leading with an example of a negative result! That's what any researcher faces every day, unlike what gets published, after all
- _the_inflator 3y ago
  I won’t quote Edison here, but I totally agree.
mgarciaisaia 3y ago
Author here! I've just enabled Issues & PRs in the repo if you want to chime in there.
urbandw311er 3y ago
My view of the author changed somewhat when I reached the section where he had to ask ChatGPT how to read command line parameters.
- RedShift1 3y ago
  Or the command line is too complex and/or poorly documented and chatGPT was quicker at solving it?
- vorticalbox 3y ago
  I read that as satire given the current state of the LLMs like chatGPT
- themoonisachees 3y ago
  But also, this is the area where an LLM shines; tasks that you technically could solve yourself but are so boilerplate that you should spend you brain power elsewhere. Then again here it looks like not much brainpower got put into this project at all (and that's OK, sometimes it be like that )
- The_Colonel 3y ago
  I don't remember it either, because I rarely write command line utilities. Asking ChatGPT is just like looking up documentation, just faster ...
  - fturst 3y ago
    Disagree. I can be more or less certain that documentation authors or write-ups have knowledge about the topic im researching to a reasonable degree, because 1) they need accurate and efficient code that makes sense to establish a relationship with the reader and compete with other solutions 2) humans are bad at explaining things they dont know about opposed to executing or managing unknowns ChatGPT? None of these. Its a giant probability calculator that wants my prompts and its own answers to foster itself. This also nurtures its inaccuracies and makes it easier to confidently lie. I hardly find any reasonable use for ChatGPT other than quick completion suggestions for at a maximum of 2-3 lines, because thats what its designed for.
klabb3 3y ago
Maybe OT, but does anyone know if there is runtime analysis of JS and/or wasm? Obfuscation is a serious threat to the open web, and things like fingerprinting can be incredibly invasive. Web browsers typically only support static “prettifying” (ie auto indent). I’ve seen websites probe for chrome extensions, canvas and all kinds of APIs. Deobfuscators are often not enough to restore legibility. (I assume disassemblers are similar, but I’ve never tried.) I would love to have a trace/intercept/breakpoints of any external APIs called in order to restore a sense of control over what code websites run. Ideally, integrated in the browser. With WASM gaining popularity, this will become (much) more important, imo.
molf 3y ago
Using `xz -9 -e` results in pretty reasonable compression, in comparison: 19648 dommy-2.0.js 28092 dommy-2.0.weird.js.xz 115023 lodash-4.17.15.js 138808 lodash-4.17.15.weird.js.xz 7114 modernizr-custom.js 11148 modernizr-custom.weird.js.xz
klyrs 3y ago
This is way more fun than the "base64->gzip" algorithm that so many of us have tried upon learning about compression...

111 points by mgarciaisaia 3y ago

deleted 3y ago

[deleted]

It's not a huge surprise that gzip as a general compression algorithm didn't compress this down any further. I do wonder about a format that was specifically trained on these specific characters though, and the patterns that tend to emerge from the weird compiler. Maybe the chunks at a certain scale would be predictable and thus compressible. Of course at that point you're probably more interested in a common binary format, and should start thinking about wasm instead.

hughw 3y ago
The information content of the weird program is the same as that of the original cleartext, so I wouldn't expect zipping a transpiled program to compress better than compressing the original.
- Ono-Sendai 3y ago
  Information content isn't really a well-defined concept for finite-length strings.
- Brian_K_White 3y ago
  Another comment pointed out that there is more information or entropy in the weird version if you don't happen to be a js interpreter. The compression algorithm knows that 165427-165427 is really 165427-same, but does not know that it's really 0 and the same as all the other things that resolve to 0. There must be a lot of similar things like that in this particular case that relies on knowledge of the rules of js. I guess it's tempting to think next about adding ai to a compressor so that it could know the actual rules of js and refactor it, but I just think of the tragedy that is jbig that does OCR as part of the compression, except, gets it wrong, and the original data is lost forever without a trace. And it's built right in to some scanners and happens before the compressed output even leaves the device. The user never sees anything else. There is no better reference uncompressed version anywhere if the user did not know about the problem and override some default settings.

dclowd9901 3y ago

It might be that GZIP isn’t actually a good format with which to try to compress this data. I would think a compression algorithm that expects a rather large 8 byte character space wouldn’t be very suitable for a 4-bit space

jrockway 3y ago
I got a little nerd sniped by this. I wrote a program that takes an input (/usr/share/dict/words on Debian 12, specifically), and compresses it with gzip and Zstandard, and also expands its binary representation (by replacing each 1 bit with A and each 0 bit with B) and compresses that. The result is: gzip expgz zstd expzstd original 263120 421278 252449 389004 985084 So unlike in the article, expansion + compression is at least better than the original. The ratios are (smaller # better; the opposite of how most compression algorithms advertise their performance, but what the original article used): 0.27, 0.42, 0.25, 0.39. gzip and Zstandard aren't a lot different in either case. Whatever patterns that the Javascript weirdifier uses is less obvious to compression algorithms in general than just bitwise substitution. Here's the program if you want to look for bugs: https://go.dev/play/p/wwNXVzO2TO- https://go.dev/play/p/wwNXVzO2TO-

telegpt 3y ago

[dead]

ShamelessC 3y ago

> So, yeah - this isn't a good idea. If the Weird transpiler only changes the encoding of each character with a really weird equivalent, it makes a lot of sense that it doesn't compress better than the source one - the ideal scenario would be to compress the same. If your results disagree with your premise in unsurprising and obvious ways - please start your article with that so I can stop reading it.

garba_dlm 3y ago

and Golang is a clever way to build up an AI

garba_dlm 3y ago
ahaha, downvoted out of sight but I'm pretty sure I read this sentiment in some other comment in this site

crazygringo 3y ago

I'm actually surprised at how insanely terrible the "compression" is. Looking at the table at the end, I'm not surprised at all that the "weird" obfuscated code is ~2000x the size of the original source. But I am surprised that that the gzipped weird code is still ~25x the size of the original source, as opposed to ~0.25x for gzipping the original source. After all, the amount information in the weird code should still ultimately be approximately the same as the original source code, right? Or maybe double or something like that. I'm very surprised it's twenty-five times as much. The only reason I can guess is that the "weird" process results in information structures that are represented in an extremely hierarchical way, and gzip is built for stream compression, and is unable to find/represent/compress hierarchical structures? And if that's the case, it makes me wonder if there are any compression algorithms which are able to handle that better? That might not be based on "dictionary words/sequences" as much, but rather attempting to find "nestable/repeatable syntax patterns"?

thristian 3y ago
Compression is all about detecting patterns in the data, usually with some kind of sliding window of past data, used to predict future data. For gzip in particular, this sliding window has a fixed size of 32KB. If the "weird" version is ~2000× the size of the original source, gzip would need a sliding window of ~2000× the size (about 64MB) to obtain equivalent compression.
- wizzard0 3y ago
  Also, an encoder like these can inject any amount of entropy (eg replace "0" with "100500999-100500999") which gzip can reduce to "100500999-same" but without knowledge of JS semantics has no chance to reduce to either "0" nor the nearby "172913211-172913211")
- josephg 3y ago
  > For gzip in particular, this sliding window has a fixed size of 32KB. I'm surprised people keep reaching for gzip for this sort of comparison. LZ4 / zstd compress better at the same compression speed, and zstd and brotli compresses much better. Brotli is also supported in all modern browsers. There's basically no reason to use gzip in new software. (With the exception of compressing for the web - at least until zstd makes it into browsers.)

koito17 3y ago

Just for fun, I decided to pass the output.js file through Google Closure Compiler's advanced optimizations. It does a surprisingly good job at reconstructing part of the strings. % npx google-closure-compiler -O ADVANCED --js output.js (()=>{})["co"+(1/0+[])[4]+"structor"]("co"+(1/0+[])[4]+... Not pasting the full thing. But it reduces the output.js file from ~118 KiB to ~9.92 KiB, which is pretty good! There is technically not much stopping the compiler from inferring that 1/0 === Infinity, recognizing (1/0+[])[4] is free of side-effects, and eventually concluding its safe to substitute the whole expression with "n". Google Closure already has optimizations for string concatenation, so if it were able to perform an optimization pass with Infinity, then it would also be able to emit the string "constructor" instead of "co"+(1/0+[])[4]+"structor"

woneton 3y ago
$ wc -c output.js 117708 output.js $ uglify-js output.js -c unsafe | node Hello world! $ uglify-js output.js -c unsafe | wc -c 2740 $ uglify-js output.js -c unsafe | cut -c 1-60 (()=>{}).constructor("conso"+"".constructor["from"+(()=>{}). $ uglify-js output.js -c unsafe | gzip | wc -c 192
pjc50 3y ago
Interesting. I wonder if an even more effective approach to unobfuscation would be an "anti-jit" compiler; since what we're interested in is the actual execution flow, can we leverage all the browser's optimization engine to pull that out for us? Do the various JIT engines use an intermediate representation (IR) and what does it look like?
- circuit10 3y ago
  V8 starts with interpreting bytecode (Ignition), then hot code gets tiered up to a non-optimising JIT without an IR (Sparkplug), and even hotter code goes an optimising one with an IR (TurboFan) That way it can start executing quickly and not waste time on compiling/optimising things that only get run a few times
Alifatisk 3y ago

wizzard0 3y ago

1) The title is a clickbait, but 2) Thanks for leading with an example of a negative result! That's what any researcher faces every day, unlike what gets published, after all

_the_inflator 3y ago
I won’t quote Edison here, but I totally agree.

mgarciaisaia 3y ago

Author here! I've just enabled Issues & PRs in the repo if you want to chime in there.

urbandw311er 3y ago

My view of the author changed somewhat when I reached the section where he had to ask ChatGPT how to read command line parameters.

RedShift1 3y ago
Or the command line is too complex and/or poorly documented and chatGPT was quicker at solving it?
vorticalbox 3y ago
I read that as satire given the current state of the LLMs like chatGPT
themoonisachees 3y ago
But also, this is the area where an LLM shines; tasks that you technically could solve yourself but are so boilerplate that you should spend you brain power elsewhere. Then again here it looks like not much brainpower got put into this project at all (and that's OK, sometimes it be like that )
The_Colonel 3y ago
I don't remember it either, because I rarely write command line utilities. Asking ChatGPT is just like looking up documentation, just faster ...
- fturst 3y ago
  Disagree. I can be more or less certain that documentation authors or write-ups have knowledge about the topic im researching to a reasonable degree, because 1) they need accurate and efficient code that makes sense to establish a relationship with the reader and compete with other solutions 2) humans are bad at explaining things they dont know about opposed to executing or managing unknowns ChatGPT? None of these. Its a giant probability calculator that wants my prompts and its own answers to foster itself. This also nurtures its inaccuracies and makes it easier to confidently lie. I hardly find any reasonable use for ChatGPT other than quick completion suggestions for at a maximum of 2-3 lines, because thats what its designed for.

klabb3 3y ago

Maybe OT, but does anyone know if there is runtime analysis of JS and/or wasm? Obfuscation is a serious threat to the open web, and things like fingerprinting can be incredibly invasive. Web browsers typically only support static “prettifying” (ie auto indent). I’ve seen websites probe for chrome extensions, canvas and all kinds of APIs. Deobfuscators are often not enough to restore legibility. (I assume disassemblers are similar, but I’ve never tried.) I would love to have a trace/intercept/breakpoints of any external APIs called in order to restore a sense of control over what code websites run. Ideally, integrated in the browser. With WASM gaining popularity, this will become (much) more important, imo.

molf 3y ago

Using `xz -9 -e` results in pretty reasonable compression, in comparison: 19648 dommy-2.0.js 28092 dommy-2.0.weird.js.xz 115023 lodash-4.17.15.js 138808 lodash-4.17.15.weird.js.xz 7114 modernizr-custom.js 11148 modernizr-custom.weird.js.xz

klyrs 3y ago

This is way more fun than the "base64->gzip" algorithm that so many of us have tried upon learning about compression...