document

HTML5 & JavaScript side
twitter: @y_imaya

Zstandard と Zip ファイル

Zstandard 対応のアーカイバ欲しい問題

Zstandard はパフォーマンスに優れたすばらしいものですが、今のところ個別のファイルしか圧縮できません。(いわゆるアーカイブ機能がない) Zstandard に対応したアーカイバ欲しいなと思っていたけど特に何もせずにいたのですが、最近 @__gfx__ さんの下記ツイートを見て再び興味を持ちました。

これは例えば Zip ファイルの仕様に Zstandard が追加され、その仕様に対応したアーカイバが公開されれば問題は解決しますが、そもそも仕様に追加されるかすらわかりません。 しかし、実際に仕様に追加されるのを待つのではなく、Zipでは圧縮を行わずアーカイブ機能だけを利用して、その前段階で Zstandard で圧縮すれば大体欲しい感じになりそうだということに気が付きました。 

7−Zip と Zstandard

7−Zip に Zstandard 圧縮をサポートしてもらおうという提案があったみたいですがまだサポートされておらず、非公式の Zstandard 対応版ができたりしてました。 でもまあ、勝手に拡張されたアーカイブファイルとか怖いので、今回はよりシンプルな方法を取りました。

シェルスクリプト化

というわけで、シェルスクリプトを作ってみました。 なんか作ってるうちにあれも欲しいこれも欲しいとなっていき、ワンライナーだったのが最終的にはそこそこの大きさになってしまいました…。

使ってみたい方は https://github.com/imaya/zipstd からどうぞ!

性能

可逆圧縮におけるコーパスである Silesia compression corpus を使用して、簡単にですが性能を測ってみました。

Compression: Zstandard + Zip

$ gtime -v zipstd -3 -P 1 -o silesia-zstd-3.zip silesia
zipstd: start compression
zipstd: Maximum number of Processes: 1
zipstd: [Directory: silesia]
silesia/dickens      : 36.24%   (10192446 => 3693846 bytes, silesia/dickens.zst) 
silesia/mozilla      : 36.27%   (51220480 => 18576312 bytes, silesia/mozilla.zst) 
silesia/mr           : 35.71%   (9970564 => 3560660 bytes, silesia/mr.zst)     
silesia/nci          :  8.56%   (33553445 => 2870655 bytes, silesia/nci.zst)   
silesia/ooffice      : 51.14%   (6152192 => 3146461 bytes, silesia/ooffice.zst) 
silesia/osdb         : 34.86%   (10085684 => 3515524 bytes, silesia/osdb.zst)  
silesia/reymont      : 29.51%   (6627202 => 1955962 bytes, silesia/reymont.zst) 
silesia/samba        : 23.53%   (21606400 => 5084702 bytes, silesia/samba.zst) 
silesia/sao          : 76.62%   (7251944 => 5556254 bytes, silesia/sao.zst)    
silesia/webster      : 29.46%   (41458703 => 12215621 bytes, silesia/webster.zst) 
silesia/x-ray        : 72.77%   (8474240 => 6166670 bytes, silesia/x-ray.zst)  
silesia/xml          : 11.96%   (5345280 => 639077 bytes, silesia/xml.zst)     
  adding: silesia/dickens.zst (stored 0%)
  adding: silesia/mozilla.zst (stored 0%)
  adding: silesia/mr.zst (stored 0%)
  adding: silesia/nci.zst (stored 0%)
  adding: silesia/ooffice.zst (stored 0%)
  adding: silesia/osdb.zst (stored 0%)
  adding: silesia/reymont.zst (stored 0%)
  adding: silesia/samba.zst (stored 0%)
  adding: silesia/sao.zst (stored 0%)
  adding: silesia/webster.zst (stored 0%)
  adding: silesia/x-ray.zst (stored 0%)
  adding: silesia/xml.zst (stored 0%)

	Command being timed: "zipstd -3 -P 1 -o silesia-zstd-3.zip silesia"
	User time (seconds): 2.44
	System time (seconds): 0.70
	Percent of CPU this job got: 91%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:03.43
	Average shared text size (kbytes): 0
	Average unshared data size (kbytes): 0
	Average stack size (kbytes): 0
	Average total size (kbytes): 0
	Maximum resident set size (kbytes): 13221888
	Average resident set size (kbytes): 0
	Major (requiring I/O) page faults: 0
	Minor (reclaiming a frame) page faults: 20196
	Voluntary context switches: 285
	Involuntary context switches: 3579
	Swaps: 0
	File system inputs: 15
	File system outputs: 12
	Socket messages sent: 0
	Socket messages received: 0
	Signals delivered: 2
	Page size (bytes): 4096
	Exit status: 0

Compression: Zip (Deflate)

$ gtime -v zip -r -o silesia-zip-deflate.zip silesia
  adding: silesia/ (stored 0%)
  adding: silesia/dickens (deflated 62%)
  adding: silesia/mozilla (deflated 63%)
  adding: silesia/mr (deflated 63%)
  adding: silesia/nci (deflated 90%)
  adding: silesia/ooffice (deflated 50%)
  adding: silesia/osdb (deflated 63%)
  adding: silesia/reymont (deflated 72%)
  adding: silesia/samba (deflated 75%)
  adding: silesia/sao (deflated 26%)
  adding: silesia/webster (deflated 71%)
  adding: silesia/x-ray (deflated 29%)
  adding: silesia/xml (deflated 87%)
	Command being timed: "zip -r -o silesia-zip-deflate.zip silesia"
	User time (seconds): 10.94
	System time (seconds): 0.14
	Percent of CPU this job got: 99%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:11.17
	Average shared text size (kbytes): 0
	Average unshared data size (kbytes): 0
	Average stack size (kbytes): 0
	Average total size (kbytes): 0
	Maximum resident set size (kbytes): 4292608
	Average resident set size (kbytes): 0
	Major (requiring I/O) page faults: 1
	Minor (reclaiming a frame) page faults: 366
	Voluntary context switches: 52
	Involuntary context switches: 2871
	Swaps: 0
	File system inputs: 4
	File system outputs: 6
	Socket messages sent: 0
	Socket messages received: 0
	Signals delivered: 0
	Page size (bytes): 4096
	Exit status: 0

Size

$ ls -al
-rw-r--r--    1 imaya  staff  68229691  3 20  2003 silesia-zip-deflate.zip
-rw-r--r--    1 imaya  staff  66983710  7 22 22:38 silesia-zstd-3.zip

Decompression: Zstandard + Zip

$ gtime -v unzipstd -P 1 -o decompress-zipstd silesia-zstd-3.zip
unzipstd: start decompression
unzipstd: Maximum number of Processes: 1
[File: silesia-zstd-3.zip]
Archive:  silesia-zstd-3.zip
 extracting: decompress-zipstd/silesia/dickens.zst  
 extracting: decompress-zipstd/silesia/mozilla.zst  
 extracting: decompress-zipstd/silesia/mr.zst  
 extracting: decompress-zipstd/silesia/nci.zst  
 extracting: decompress-zipstd/silesia/ooffice.zst  
 extracting: decompress-zipstd/silesia/osdb.zst  
 extracting: decompress-zipstd/silesia/reymont.zst  
 extracting: decompress-zipstd/silesia/samba.zst  
 extracting: decompress-zipstd/silesia/sao.zst  
 extracting: decompress-zipstd/silesia/webster.zst  
 extracting: decompress-zipstd/silesia/x-ray.zst  
 extracting: decompress-zipstd/silesia/xml.zst  
decompress-zipstd/silesia/dickens.zst: 10192446 bytes                          
decompress-zipstd/silesia/mozilla.zst: 51220480 bytes                          
decompress-zipstd/silesia/mr.zst: 9970564 bytes                                
decompress-zipstd/silesia/nci.zst: 33553445 bytes                              
decompress-zipstd/silesia/ooffice.zst: 6152192 bytes                           
decompress-zipstd/silesia/osdb.zst: 10085684 bytes                             
decompress-zipstd/silesia/reymont.zst: 6627202 bytes                           
decompress-zipstd/silesia/samba.zst: 21606400 bytes                            
decompress-zipstd/silesia/sao.zst: 7251944 bytes                               
decompress-zipstd/silesia/webster.zst: 41458703 bytes                          
decompress-zipstd/silesia/x-ray.zst: 8474240 bytes                             
decompress-zipstd/silesia/xml.zst: 5345280 bytes                               

	Command being timed: "unzipstd -P 1 -o decompress-zipstd silesia-zstd-3.zip"
	User time (seconds): 1.01
	System time (seconds): 0.38
	Percent of CPU this job got: 88%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:01.58
	Average shared text size (kbytes): 0
	Average unshared data size (kbytes): 0
	Average stack size (kbytes): 0
	Average total size (kbytes): 0
	Maximum resident set size (kbytes): 9043968
	Average resident set size (kbytes): 0
	Major (requiring I/O) page faults: 39
	Minor (reclaiming a frame) page faults: 8318
	Voluntary context switches: 152
	Involuntary context switches: 2222
	Swaps: 0
	File system inputs: 38
	File system outputs: 20
	Socket messages sent: 0
	Socket messages received: 0
	Signals delivered: 1
	Page size (bytes): 4096
	Exit status: 0

Decompression: Zip (Deflate)

$ gtime -v unzip silesia-zip-deflate.zip -d decompress-zip
Archive:  silesia-zip-deflate.zip
   creating: decompress-zip/silesia/
  inflating: decompress-zip/silesia/dickens  
  inflating: decompress-zip/silesia/mozilla  
  inflating: decompress-zip/silesia/mr  
  inflating: decompress-zip/silesia/nci  
  inflating: decompress-zip/silesia/ooffice  
  inflating: decompress-zip/silesia/osdb  
  inflating: decompress-zip/silesia/reymont  
  inflating: decompress-zip/silesia/samba  
  inflating: decompress-zip/silesia/sao  
  inflating: decompress-zip/silesia/webster  
  inflating: decompress-zip/silesia/x-ray  
  inflating: decompress-zip/silesia/xml  
	Command being timed: "unzip silesia-zip-deflate.zip -d decompress-zip"
	User time (seconds): 1.63
	System time (seconds): 0.14
	Percent of CPU this job got: 94%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:01.88
	Average shared text size (kbytes): 0
	Average unshared data size (kbytes): 0
	Average stack size (kbytes): 0
	Average total size (kbytes): 0
	Maximum resident set size (kbytes): 3358720
	Average resident set size (kbytes): 0
	Major (requiring I/O) page faults: 0
	Minor (reclaiming a frame) page faults: 309
	Voluntary context switches: 96
	Involuntary context switches: 975
	Swaps: 0
	File system inputs: 33
	File system outputs: 9
	Socket messages sent: 0
	Socket messages received: 0
	Signals delivered: 0
	Page size (bytes): 4096
	Exit status: 0

性能まとめ

圧縮は速いしデフォルト設定のzipより小さくなる。 伸長はどちらもはやいけど若干zipより速くなる。

asm.js を手書きする

はじめに

人間は誰しもパフォーマンスを求め、最終的には asm.js か WebAssembly を手書きするようになるので、人権を手に入れるためにいつでも asm.js を書ける環境をつくります。 WebAssembly はさすがに手書き厳しそうでした。

というのは冗談で、zlib.js の一部の処理を asm.js で高速化できないかと考え、ひとまず Adler-32 と CRC-32 を asm.js で書き直してみた際にいろいろ苦労したので忘れないようにこの記事を書いています。

なお、今回 asm.js で書いたコードは以下の通り gist で公開しています。 zlib.js での採用はまだ検証が必要なので未定ですが、採用するにしてももう少しきちんとした書き方になるでしょう。

asm.js 手書き環境の整備

JavaScript shell

asm.js は Mozilla が言い始めただけあって Firefox で実行するのが一番良いのですが、毎回 Firefox で実行するのは正直手間です。 そこで、ここでは Web ブラウザを使わずにコマンドラインだけで asm.js として正しいかチェックを行う環境を JavaScript shell を使って構築していきます。 JavaScript shell とは Mozilla の JavaScript エンジン SpiderMonkey のコマンドラインツールです。

概要:https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Introduction_to_the_JavaScript_shell

ダウンロードと準備

下記のURLから、最新版の jsshell をダウンロードしましょう。

https://archive.mozilla.org/pub/firefox/nightly/latest-mozilla-central/

あとは展開してパスを通し、

$ js -w -c hoge.js

のように js ファイルを指定して実行すると、asm.js のチェック(というか、実際にコンパイルを試みる)を行います。 なお、 -w オプションは warning を表示するオプションで、asm.js まわりのメッセージは warning として出力されるため必要となり、 -c オプションはコンパイルのみ行い、実行はしないというオプションです。asm.jsとしてただしいコードかどうかはコンパイルできるかどうかで判別できるので、実行する必要はありません。

watch

各々の好きなタスクランナーで asm.js のコードが変更されたら JavaScript shell でチェックを行うようにすると便利です。

一例として npm scripts で chokidar-cli を使って行う場合の手順を書いておきます。

ディレクトリ構成

src 以下に *.asm.js というファイル名で asm.js のコードを置き、vendor/jsshell に JavaScript shell を配置しています。

.
├── package.json
├── src
│   ├── adler32.asm.js
│   └── crc32.asm.js
└── vendor
    └── jsshell
        ├── js
        ├── libmozglue.dylib
        └── libnss3.dylib

chokidar-cli のインストール
$ npm i -D chokidar-cli
npm scripts の登録

package.json 内の scripts に以下のように watch を追加します。

  "scripts": {
    "watch": "chokidar src/**/*.asm.js -c \"vendor/jsshell/js -w -c {path}\""
  },
監視の開始
$ npm run watch

これで src/ 以下に *.asm.js となるファイルを作ったり更新したりすると、JavaScript shell によるチェックが行われるようになりました。

ひとまず、 asm.js を手書きで開発していく環境が整ったと言っても良いでしょう。

asm.js で詰まったポイント

仕様を軽く読んだだけでは覚えきれず、詰まったポイントが幾つかあったので詰まった現象と対処法を書いておきます。 型関係のエラーは大体言われてすぐ気がつくので省略します。

32bit整数同士の掛け算が * 演算子で行えない

具体的には

TypeError: asm.js type error: one arg to int multiply must be a small (-2 ^ 20, 2 ^ 20) int literal

というエラーの場合、asm.js の仕様 に書いてあるように Math.imul を使いましょう。

Uint8Array, Int8Array 以外のヒープのビューにアクセスするときにエラーが出る

具体的には

TypeError: asm.js type error: index expression isn't shifted; must be an Int8/Uint8 access

というエラーです。

asm.js の仕様 によると index が数値ではなく expression の時は右シフトしなくてはならないので、 array[index << 2 >> 2] のようにしましょう。 (この仕様は正直通常のJSで遅くなるのでツライ)

大きなヒープで何度も計算すると素のJSよりも遅くなる

asm.js では function の引数などに配列を使うことはできません。 では、どうするかというと最初に Heap (ArrayBuffer) を asm.js コードに渡してやり、その中で Uint8Array などでビューを作ってやり、自分でメモリの構造を決め、asm.js 内の各 function では index と length を使ってここからここまでは何々の配列として扱う、みたいなことをします。

CRC-32 の計算では事前計算テーブルとデータという2つの配列を扱わなくてはならないため、この2つの配列を結合するあたらしい ArrayBuffer を作り、それを heap として asm.js のコードを呼んでいました。 このときのヒープの構造は 0-1023 バイトまでは事前計算テーブル(32bit*256個)、1024 バイト以降は CRC-32 に渡すデータとして扱う、という形にしました。

なお、この際

var table = new stdlib.Uint32Array(heap, 0, 256);
var data = new stdlib.Uint8Array(heap, 1024);

のようにビューでわかりやすくすればいいのでは、と思ってやってみたところ asm.js では許されていませんでした。(コンストラクタの引数は heap のみの一つだけ、と言われます) TypedArray#subarray などのメソッドも使えないので素直に先頭からの index でアクセスしましょう。

こうして、配列の CRC-32 ハッシュ値を求めようとする際に、毎回テーブル+データのヒープを作ってasm.jsに渡す素直な実装が出来たわけですが、当然 ArrayBuffer の作成と(計算が行われた後は使わなくなるため)破棄が行われ、何度も実行していると GC が大量に発生することになり、asm.js 化する前より性能が落ちたりします。

function crc32_asm(data) {
  var table = new Uint32Array([
    // CRC-32 の事前計算テーブル
    ...
  ]);

  function asm(stdlib, foreign, heap) {
    "use asm";

    var heapUint32 = new stdlib.Uint32Array(heap);
    var heapUint8  = new stdlib.Uint8Array(heap);

    function calc(pos, length) {
      // CRC-32 の計算をして返す
    }


    return {
      calc: calc
    }
  }

  // 事前計算テーブルとCRC-32を求めたい配列の結合
  var tableUint8Array = new Uint8Array(table.buffer);
  var dataLength = tableUint8Array.length + data.length;
  var heapSize = 1 << 8;
  while (dataLength  > heapSize) {
    heapSize <<= 1;
  }
  var heap = new ArrayBuffer(heapSize);
  var heapUint8Array = new Uint8Array(heap);

  heapUint8Array.set(tableUint8Array);
  heapUint8Array.set(data, tableUint8Array.length);

  // asm.js にヒープを渡し、返ってきた calc 関数に引数を渡しそのまま実行 
  return asm(self, {}, heap).calc(0, data.length) >>> 0;
}

Web ブラウザの開発ツールでプロファイルを取ったところ、GC が支配的になっていることに気づいたので、ArrayBuffer の作成を最低限に抑えるようにしました。

具体的には、asm.js コード全体を呼び出すのは現在のヒープサイズでは足りない際に、ArrayBuffer を倍の長さで作り直した時だけで、それ以外は以前のヒープに TypedArray#set でデータを上書きし、 asm.js コードの実行によって得られた function によってハッシュ値を計算するようにしました。

function crc32_asm() {
  var table = new Uint32Array([
    // CRC-32 の事前計算テーブル
    ...
 ]);

  function asm(stdlib, foreign, heap) {
    "use asm";

    var heapUint32 = new stdlib.Uint32Array(heap);
    var heapUint8  = new stdlib.Uint8Array(heap);

    function calc(pos, length) {
      // CRC-32 の計算をして返す
      ...
    }

    return {
      calc: calc
    }
  }

  function calcBufferSize(data) {
    return 1024 + data.length;
  }

  var tableUint8Array = new Uint8Array(table.buffer);
  var heapSize = 1 << 16;
  var heap;
  var heapUint8Array;
  var asmFunctions;

  function init() {
    update(new Uint8Array(0));
  }

  // バッファの拡張と事前計算テーブルをセットして asm.js を実行し直す
  function update(data) {
    var requireBufferSize = calcBufferSize(data);

    while (requireBufferSize > heapSize) {
      heapSize <<= 1;
    }

    heap = new ArrayBuffer(heapSize);
    heapUint8Array = new Uint8Array(heap);

    heapUint8Array.set(tableUint8Array);
    asmFunctions = asm(self, {}, heap);
  }

  function calc(data) {
    // 現在のヒープサイズで足りないときだけ、asm.js を実行し直す
    if (calcBufferSize(data) > heapSize) {
      update(data);
    }

    // データを heap にセットする
    heapUint8Array.set(data, 1024);

    return asmFunctions.calc(0, data.length) >>> 0;
  }

  init();

  return {
    calc: calc
  };
}

複数の配列を扱いたいという場合はわりとよくあると思うので、このバッファの使い回しは asm.js では基本となると思います。

また、私見ですがこのバッファの使い回しをすすめていくと、Webアプリケーション全体をプロセスとみなし、このバッファがプロセス内のデータセグメントとスタックセグメントのようになるのではないかと思います。 どういうことかというと、Webアプリケーション内全体で一度に大きな ArrayBuffer を確保し、asm.js で使用する変数や配列などをこの ArrayBuffer の中で割り当てていくメモリ管理コードを持つようになるということです。 このとき、長く使いそうなものは上から、一時的なものは下から積み上げていく、つまりプロセスにおけるデータセグメント内のヒープ領域とスタックセグメントのような形が考えられます。 そして、ヒープ領域の拡張時に断片化の解消などを含むメモリ管理の仕組みを再実装していくことになるのではないかと思います。

実際、Emscripten における runtime.js がそのような仕組みになっています。これは Emscripten が他言語で書かれたアプリケーションを動かすのを目的としているので、既存のプロセスのメモリ管理に相当する実装があるのは当然かも知れません。

つまり、人の手による温かみのある asm.js とは最終的にはほぼ Emscripten と同じようなコードになり、 asm.js の手書きとは人間 Emscripten になることであり、人権が失われ機械として生きていくということです。

zlib.js 0.3.0 リリース

致命的なバグの修正

HLIT と HDIST のデコードに関するバグ修正

Inflate において、リテラルと長さ符号(HLIT)と距離符号(HDIST)の展開において不具合があったため、Inflate に失敗あるいは正しくないデータになってしまうことがありました。 これはどういうことかと言うと、HLIT と HDIST は連続して格納されていますが、その中で同じ符号が連続する場合は繰り返しを行う処理があります。 0.2.0 までの実装では、HLIT と HDIST をそれぞれ別の配列として扱っていたため、 HLIT と HDIST をまたぐような繰り返し符号が出現していた際、誤ったデータが展開されてしまっていました。

0.3.0 では HLIT と HDIST の展開を連続する配列として展開し、その後のハフマン符号テーブルを構築する際に HLIT と HDIST を分離して行うようにしています。

仕様でいうと RFC1951 の 3.2.7 にある以下の部分を誤って実装していたということです。

The code length repeat codes can cross from HLIT + 257 to the
HDIST + 1 code lengths.  In other words, all code lengths form
a single sequence of HLIT + HDIST + 258 values.

不正な Deflate データによる無限ループの修正

0.2.0 までは細工された Deflate データを伸長しようとすると、無限ループに陥る場合がありました。 ハフマン符号を使ってリテラル・長さ符号と距離符号を取得する際、ハフマン符号のコード長が不正になっており、無限に読み込もうとして無限ループに陥ってました。

0.3.0 ではコード長をチェックして明らかに不正な場合、例外を投げるように修正しました。

その他のバグ修正

PKZIP 作成時、余計な領域が後ろに残っているバグの修正

0.2.0 までは PKZIP の作成を行うと、後ろに余計な領域が残っており、厳密なアーカイバで展開しようとすると「データのペイロード後にデータが存在します」という警告が出ていました。 これは "End of central directory record" のサイズ計算が誤っていて、余分にバッファを確保してしまうせいです。

https://pkware.cachefly.net/webdocs/casestudies/APPNOTE.TXT の 4.3.16 にある通り、22 が正しいサイズです。

このバグと修正方法についてはzlib.js 0.2.0のzip.js/zip.min.jsのバグの修正[ZIPファイルの破損]によって報告されていました。 @TakeshiOkamoto さん、ありがとうございました。

ビルド・テスト環境の変更

Ant によるビルドと BusterJS によるテストから、 Grunt によるビルドと Karma + mocha + power-assert によるテストに変更しました。 Grunt にする作業自体はだいぶ前に行っていたのですが、すでに時代遅れになっている気もするのでさらに変更するかもしれません…。

難読化されたJavaScriptコードを読む

はじめに

何らかの事情で JavaScript のコードを読み、その挙動について調査しなくてはいけないということはよくあると思います。
そんなとき、難読化やMinifyなどによって複雑怪奇に見えるコードに遭遇したという経験をもつひとも多いのではないでしょうか。

この記事はそんなコードにぶつかった際に、どうすれば良いのかを自分なりにまとめてみました。

また、jjencode 作者のはせがわようすけさんのJavaScript難読化読経というスライドを見て、
作者がネタバレしてるんだからこの辺の知見について書いても大丈夫だろうという気持ちで書き始めたことも一応記しておきます。

ツールによって難読化されたコードの読み方

まずはコードリーディング出来る状態にするため、よく見る2つのツールによる難読化のデコード方法について書いておきます。

Javascript Obfuscator

Javascript Obfuscatoreval(function(p,a,c,k,e,d){... から始まる特徴的なコードにエンコードするツールです。
このエンコードされた JavaScript コードは、先頭の evalconsole.log にするだけでデコードすることが可能です。
パッと見でのコードリーディングを防ぎたいというくらいの効果しかありません。

jjencode, aaencode, etc.

コードを読もうとしたとき、記号プログラミングの手法によって読みにくくなっていることがあります。
そうした場合は、開発ツールのコンソールを使ってデコードするところから始めます。
難読化ツールとしては jjencode が有名です。
これらの難読化ツールは基本的に number.constructor.constructor を使うことで Function を引き出し、Function(実行したいスクリプト本体文字列) とすることで任意のコードを実行しています。
booleanstring を使っても同様のことが出来るので、Number がハズレだったら StringBoolean を試すとよいでしょう)

蛇足かもしれませんが説明しておきますと、number.constructorNumber であり、Number.constructorFunction となります。

(0).constructor
=> Number() { [native code] }

(0).constructor.constructor
=> Function() { [native code] }

つまり、下記のように Number.constructorconsole.log にしてやることで、実行しようとしているコードを確認することができます。

Number.constructor = console.log.bind(console);

また、コードが何らかの悪意を持っている可能性がある場合は、下記のように debugger 文を使って実行を中断しましょう。(あるいは、例外を投げて失敗させても良いでしょう)

Number.constructor = function() {
    console.log(arguments);
    debugger;
};

記号プログラミングによる難読化手法は、より詳細な説明をはせがわようすけさんが資料を公開しているのでそちらを参照してください。

このように、jjencode などのエンコーダによる難読化は簡単にデコードできるため、解読を防ぐ用途での効果は期待しない方がよいでしょう。
実際、jjencodeには下記のように注意書きがされています。

Be aware

Using jjencode for actual attack isn't good idea.
- Decode easily. jjencode is not utilitarian obfuscation, just an encoder.
- Too characteristic. Detected easily.
- Browser depended. The code can't run on some kind of browsers.

Minify/Compile/Transpile されたコードの読み方

ここから、本来のコードリーディングの作業に入っていきます。
Minify/Compile/Transpile(以下、まとめてMinifyと表記します) されたコードをどのように追っていくかという話題です。
当然、SourceMap は提供されてないことを前提とします。

Pretty Print ツールによるソースコードの整形

まずは、ごちゃごちゃしているコードを Pretty Print (読みやすい形に変換)します。
Google Chrome などの開発者ツールについている Pretty Print でも良いのですが、後々のために Pretty Print した別のファイルにしておきます。

例えば、下記のようなコードを

function hello(a){alert("Hello, "+a)}hello("New user");

このようにきれいに整形してくれます。(例は Closure Compiler のオンラインサービス版の初期コード)

function hello(a) {
    alert('Hello, ' + a);
}
hello('New user');

Pritty Print する方法はいくつかありますが、自分は esprimaescodegen による Pretty Print スクリプトを愛用しています。

IDEによるリファクタリング

Pretty Print してしまえばあとは頑張ってコードを読んでいくだけなのですが、そのまま読んでいくのは人類には厳しいのでIDEのサポートを受けながらコードを読みやすい形に修正しながら読み進めていきます。
なぜIDEを使用するかというといくつかの理由がありますが、lintを使うなど他の環境でも同様のことができるなら問題ありません。
自分は WebStorm や Visual Studio を使っています。

unused variable の除去

未使用の変数は見つけ次第どんどん削除していきましょう。

dead code の除去

未使用の変数と同様に、到達しないコードもIDEが教えてくれるので削除していきます。

変数名/function名のリネーム

Minifyされたコードは変数やfunction名が a とか b といった短い名前に変更されています。
しかも、別のスコープでまた a とか b となっていくので、どれがどれだかややこしくなっています。
これをIDEのリファクタリング機能のリネームを活用することで分かりやすい名前にしていきます。
(どういう名前にするかは、コードをよく読んで推測するしかない)
単なる置換よりも、スコープなどを適切に判断してくれるIDEのリファクタリング機能の方が便利です。

変数の使いまわしの分離

Closure Compiler ではファイルサイズ優先の Minify を行うため、元々は別の変数だったものを同じ変数を再度利用することがあります。
(オプションで変更することは可能だが、オプションの変更を行うには自分でビルドしなおすか外部ツールを使用するしかありません)
そういった変数を見つけ出して、それぞれ別の変数に分離します。
簡単にですが見分けたい場合を書いておくと、数値をいれてる変数に文字列を入れるなど、別のものを同じ変数に入れていたら注意して読んだ方が良いでしょう。

6to5 に末尾呼び出し最適化が入ったと思ったら一瞬でなくなった

一昨日の記事を書いた後、末尾呼び出し最適化の実装にバグがあって速攻で消されたようです。

  • v3.5.0: 末尾呼び出し最適化の実装が入る
  • v3.5.1: 他のTailオブジェクトと混同して判定されてしまうため、Tail.prototype._isTailDescriptor というのを付けて対処
  • v3.5.2: _tailCall をつかった末尾呼び出し最適化がコメントアウト
  • v3.5.3: v3.5.0 以前の末尾再帰最適化の実装に戻す

少し見たところ、以下のようなケースでうまく動かないようです。

function foo() {
  return "foo";
}

function fooWrapper() {
  return foo();
}

function test() {
  var str = fooWrapper();
  if (str !== "foo") {
    throw new Error();
  }
}

function testWrapper() {
  return test();
}

testWrapper();

なぜこのケースでうまく動かないのか見ていきます。
このコードを 6to5(v3.5.1) で変換したものがこちらです。

"use strict";

var _tailCall = (function() {
    function Tail(func, args, context) {
        this.func = func;
        this.args = args;
        this.context = context;
    }
    Tail.prototype._isTailDescriptor = true;
    var isRunning = false;
    return function(func, args, context) {
        var result = new Tail(func, args, context);
        if (!isRunning) {
            isRunning = true;
            do {
                result = result.func.apply(result.context, result.args);
            } while (result instanceof Tail || result && result._isTailDescriptor);
            isRunning = false;
        }
        return result;
    };
})();

function foo() {
    return "foo";
}

function fooWrapper() {
    return _tailCall(foo);
}

function test() {
    var str = fooWrapper();
    if (str !== "foo") {
        throw new Error();
    }
}

function testWrapper() {
    return _tailCall(test);
}

testWrapper();

呼び出し順序は以下の順序です。

testWrapper
  _tailCall(test)
    test
      fooWrapper
        _tailCall(foo)

ここで問題となるのが _tailCall(foo) です。
これはもともと return foo(); なので "foo" が返るはずです。
しかし、この呼び出し順序では最初の _tailCall(test) が呼ばれた時に isRunnningtrue になるため、 _tailCall(foo) は Tail オブジェクトを返します。
var str = fooWrapper();str の値が Tail オブジェクトになってしまうため、変換前の結果と異なってしまいます。

今回のように他の末尾呼び出ししている function の戻り値を変数に代入するようなケースでもうまく動くような修正が入らなければ、再び末尾呼び出し最適化を有効にするのは難しそうな気配を感じます。
(現在はもともと入ってた末尾再帰最適化での高速化を行っているようです)
そのほかにもパフォーマンスの問題もあるので大変そうですが、はやく再び有効になると良いなあと思います。

記事検索
最新コメント
最新トラックバック
カテゴリ別アーカイブ
タグクラウド
QRコード
QRコード
  • ライブドアブログ