Skip to content

Instantly share code, notes, and snippets.

@greymd
Last active February 20, 2023 08:12
Show Gist options
  • Save greymd/455a13bb6f757c5ccd00bfb155d525e2 to your computer and use it in GitHub Desktop.
Save greymd/455a13bb6f757c5ccd00bfb155d525e2 to your computer and use it in GitHub Desktop.
yamayaさんの難読化シェル芸(フィボナッチ数列) 解説

yamayaさんの難読化シェル芸(フィボナッチ数列) 解説

経緯

(1) ある日、yamaya さんという怖い方がこのツイートを投稿する。

yamaya_src

(2) シェル芸bot上で実行されたこのシェル芸は、結果として下記のようにフィボナッチ数列を出す。

1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903 https://t.co/8Rj5NtWE4W

— シェル芸bot (@minyoruminyon) April 6, 2019

(3) 結果を見たシェル芸界隈が戦慄する。

(4) ものすごく雑に内容の解読を試みる。← ココ

解説

※ 2019/09/03追記: 本文中で不明だった点について更新しました。

ちょっと可読化

! : "`/???/???/???${#?}???<<<_.`";_____=${_::-~$?}
____='__+=___,___=__-___,__<_[$($_____<<<$___>&$[-~${##}])]||____'
((__=-~$?,____))|&$_____

スクリプト自体はワンライナーではなく3行のシェルスクリプトとなっている。 純粋に記号のみ(数字すらない)で書かれており、変数もすべて記号になっている。 説明を簡単にするために、シェル変数を下記のように読み替える。

  • __ => a
  • ___ => b
  • ____ => fibs
  • _____ => cmd

するとこうなる

! : "`/???/???/???${#?}???<<<_.`";cmd=${_::-~$?}
fibs='a+=b,b=a-b,a<_[$($cmd<<<$b>&$[-~${##}])]||fibs'
((a=-~$?,fibs))|&$cmd

つぎに、特殊な変数を読み替える。 ${#?}${##} は「ここでは」それぞれ1と等価だと考えて良い。 これについて深掘りをすると横道にそれる内容となるので、興味がある人は本文後半を参照。

結果以下のようになる。これを実行してもちゃんとフィボナッチ数列は出力される。

! : "`/???/???/???1???<<<_.`";cmd=${_::-~$?}
fibs='a+=b,b=a-b,a<_[$($cmd<<<$b>&$[-~1])]||fibs'
((a=-~$?,fibs))|&$cmd

いかがだろうか。 ちょっと読めてきたのではないだろうか (そんなわけ無いと思う)。

1行目

では、一行ずつ読み解く まず一行目に着目する。

! : "`/???/???/???1???<<<_.`";cmd=${_::-~$?}

一番最初に目を引く /???/???/???1??? はbashのパス名展開。 ?は任意の一文字にマッチする。 これはシェル芸botの環境(と、多くのLinux環境)ではsha1sumコマンドとして展開される。

$ echo /???/???/???1???
/usr/bin/sha1sum

つまり、これと等価となる。

! : "`/usr/bin/sha1sum<<<_.`";cmd=${_::-~$?}

コマンド置換の中でsha1sumコマンドを実行している。 <<<文字列でその文字列を標準入力として与えられるので、_.という文字列をsha1sumコマンドに入力していることを意味する。

$ /usr/bin/sha1sum<<<_.
bcfb6c607e4bdf81340239b7bff7eaa91ca4379f  -

さらにその結果を:コマンドという、何もしないコマンドに与えて実行している。 なお、文頭の!の理由については後述。つまり、これと等価となる。

! : "bcfb6c607e4bdf81340239b7bff7eaa91ca4379f  -";cmd=${_::-~$?}

次に、cmd=${_::-~$?} の個所について。 これは ${var:position:length} というbashの変数展開の文法を$_という変数に適用した結果を、変数cmdに格納するというスクリプト。

$_ はbashでは「前回実行したコマンドの最後の引数」が入る。 コロン;で区切られた一つ前のコマンドの引数であるbcfb6c607e4bdf81340239b7bff7eaa91ca4379f -が格納される。

${var:position:length} の変数展開の箇所は ${_::-~$?} となっている。 varが対応する個所は_でよいとして、positionに対応する個所が空白である。 これは文法上許され、空白の場合、最後のlengthのみで動作が決定する。 lengthの数字の値だけ、文頭からその文字数分文字を切り出してくれる。

$ hoge=ABCD
$ echo ${hoge::2}
AB

lengthの個所には-~$?という記載がある。 ここで、文頭に記載されていた!が効果を発揮する。 !を記述することで、前回実行したコロン:コマンドの終了ステータスの真偽が逆転する。 通常は0なのが、1となる。 そのため、前回のコマンドの終了ステータスを取得する$?1が格納される。 また、先程の変数展開のpositionおよびlengthの個所にはbashの算術式が使える。 これは一般的にはあまり知られていないが一応 Documented (マニュアル上言及があるもの) である。 ※1

そのため-~$? のうち-はマイナス、~はチルダ展開ではなくビット反転を表す。 $?は1なので、この表現は2の補数を考慮すると2と等価となる。

$ echo $(( -~1 ))
2

ここまでで、1行目はこれと等価であることがわかった。

: "bcfb6c607e4bdf81340239b7bff7eaa91ca4379f  -";cmd=${_::2}

変数cmd (元ネタでは_____) の中身にはbcという文字列が入ることがわかった。

$ : "bcfb6c607e4bdf81340239b7bff7eaa91ca4379f  -";cmd=${_::2}
$ echo $cmd
bc

2行目

fibs='a+=b,b=a-b,a<_[$($cmd<<<$b>&$[-~1])]||fibs'

この2行目でやっていることは至極単純である。 fibsという変数にa+=b,b=a-b,a<_[$($cmd<<<$b>&$[-~1])]||fibsという文字列を代入している。 以上といえば以上だが、もう少し簡単に噛み砕く。 この変数の内容は、後に算術式上で実行される。 そのため、算術式の文法に沿って記述されている。 なのでabの変数には$がつかない。

算術式ではカンマ,で区切ることによって、式を逐次実行できる。 bashのセミコロン;で作るリストとイメージは近い。 改行とスペースで見やすくする。

a += b,
b = a - b,
a < _[$($cmd<<<$b>&$[-~1])] || fibs

変数abの足し引きをして、bの内容を出力することで、フィボナッチ数列を出している。 問題なのがa<_[... で始まる行。 これは「a_[...]という配列の一要素を比較し、a < _[...]、ではない場合 fibsを評価」

という意味になる。 なお、このときの_$_とは関係ないので、変数名は何でも良い。 とりあえずcとおく。

a < c[...] || fibs

次に問題なのがcの要素番号が入るべき個所である。 これは算術式の文法ではなく、ただのコマンド置換 $(...) である。 算術式中ではコマンド置換の利用ができるので、ここまでは不思議なことではない。 ただし、変数名には$をつける必要がある。

$($cmd<<<$b>&$[-~1])

先述の通り、$cmdにはbcが入る。 $bには出力するべきフィボナッチ数列。 そして>&はリダイレクトであり、そのリダイレクトの対象となるファイルディスクリプタの番号に $[-~1]という記載がある。 $[...] は非推奨であるがこれもbashの算術式であり、$(( ... )) と等価。 -~12と等価なので$[-~1]2である。 つまりコマンド置換の個所はこう読み替えられる。

$( bc <<< $b >&2 )

このコマンド置換の中身では、bcコマンドに数値を渡して、標準エラー出力に出す、ということをしている。 bcは入力された数値をそのまま出力するのでこれは動く。 ということで、2行目全体はこのように読み替えることができる。

fibs='a += b,b = a-b,a < c[$(bc <<< $b >&2 )] || fibs'

なぜ a < c[...] と比較しているかについてはスクリプトの終了条件に関わる。 詳しくは後述する。

3行目

((a=-~$?,fibs))|&$cmd

-~$? は終了ステータスのビット反転の符号を反転させたもの。 前回のコマンドはただの変数への文字列の代入なので、$?0となる。 下記のように-~01なので、aには1が入る。

$ echo $(( -~0 ))
1

またcmdbcなので、下記のように読み替えられる。

((a=1,fibs)) |& bc

なお、|& は標準出力/エラー出力両者をパイプで渡す記述。

a1を代入したあと、fibsという変数を記載している。 このように算術式に変数を記載すると、その変数の内容が再評価される。

つまり2行目にあったfibsの中身である

a += b,b = a-b,a < c[$(bc <<< $b >&2 )] || fibs

が算術式として実行されることを意味する。 aの初期値は1、算術式では未定義の変数は0扱いなのでbの初期値は0となるが、すぐに1となる。 そして、c[...]の個所を評価する段階でコマンド置換$(...)の中身が実行され、エラー出力として変数bの内容がbcコマンド経由で出力される。 なお、コマンド置換自体は標準出力の内容をエラー出力に流されているため、何も結果として返さない。 そのため、c[...]の中身は存在しないため、こんな状態となるように一見見える。

a < c[]

しかし、下記に示すようにこれは本来文法エラーである。

$ (( a < c[] ))
bash: c[]: 誤った配列の添字
bash: c[]: 誤った配列の添字

$ (( a < c[$(bc <<< 1234 >&2)] ))
1234
bash: c[]: 誤った配列の添字
bash: c[]: 誤った配列の添字

しかしこの例の場合は動いてしまう。 直接算術式に記述するとコマンド置換が評価されてしまい、文法エラーとなるが、 一旦変数に代入して再評価することで、このエラーを避けることができる。

この事象は、シェルのコマンド置換と算術式の評価順序が関連している。 そのまま実行すると、コマンド置換の個所が先に評価され、空文字(というより文法上存在しないものと等価)となってしまうため、c[]が評価されてしまい、シンタックスエラーとなる。 しかし、一旦変数に代入して評価することで、カレントシェルの評価の影響を避け、純粋にBashの算術式として評価させることができる。

その証拠に、コマンド置換をエスケープして記述することで、このエラーを避けることができる。これは、カレントシェルの評価の影響を避ける事ができるためと考えらえられる。

$ (( c[\$(echo test >&2)] ))
test

また、算術式中で標準出力を全く伴わないコマンド置換は0と等価となる。 未定義のシェル変数についてならまだしも、コマンド置換のこんな挙動については当然のごとく Undocumanted (資料上説明がないもの)であるが、下記のようにして検証ができる。

$ hoge='a[0]=100,a[1]=200,a[$(true)]'
$ echo $((hoge))
100

そもそも算術式中、特に配列の添字の中でコマンド置換が使える挙動自体がUndocumented である

$ hoge='a < c[$(bc <<< 1234 >&2)]'; (( hoge ))
1234

少々本題からそれたが、つまりシンタックスエラーを避けるために2行目で一旦変数に代入したと考えられる。 本題に戻る。

ここで、2行目の全体像を再掲する

fibs='a += b,b = a-b,a < c[$(bc <<< $b >&2 )] || fibs'

c[$(...)] の個所は文法エラーを避けるよう評価することでc[0]として扱われることがわかった。 次の問題は、これは比較演算子上どう扱われるか?ということだ。

このような重箱の隅をつついた挙動は当然のごとく Undocumented である。 しかし、一応、算術式上でnullや未定義のシェル変数は0と等価であることがDocumentedである。 未定義の配列の1要素であるc[0]が、未定義のシェル変数と等価の挙動をするかどうかについてはわからないが、シェルの文法を考えれば等価な挙動をすると考えるのが自然であろう。 この仮説が正しければ、シェルの文法上c[0]0と等価となる※2

そして、現にこれは、0として扱われる。

$ hoge='0 == c[$(bc <<< 1234 >&2)]'
$ echo $((hoge))
1234
1

$ hoge='1 == c[$(bc <<< 1234 >&2)]'
$ echo $((hoge))
1234
0

そのため a < c[...] という個所は、aが1以上であれば偽であり、|| で繋がれた後続のfibsが実行される。fibsはさらにまた内容が評価され、フィボナッチ数列の計算と出力の処理が実行される。 つまりこれは再帰呼び出しをしているということになる。

通常aは1以上なので、終了条件がおとずれないように見えるかもしれない。 しかしaはいずれオーバーフローを起こすので(64bit環境であれば9223372036854775807が最大)、いずれ負の数となる。

$ (( a=9223372036854775807 )); echo $a
9223372036854775807
$ (( a=9223372036854775808 )); echo $a
-9223372036854775808

そのため、この式は真となり、ちゃんと止まる。 下記はオリジナルを実行した例。

$ ((__=-~$?,____))|&$_____
1
1
(中略)
4660046610375530309
7540113804746346429

可読化した3行目を振り返る。

((a=1,fibs)) |& bc

最後に、標準出力/エラー出力共々、bcコマンドに渡している。 bcコマンドはそのまま数値を標準出力に表示してくれる。 標準出力はシェル芸botのツイート対象となるため、フィボナッチ数列のツイートが表示された、という流れになる。 実はbcコマンドは全く計算ロジックに入ってこない。 単なるecho代わりに使われているというオチであった。

付録: ${##}${#?} などについて

これらの変数はbashの文法上、正常に解釈できる。

bashでは配列の要素数を数える際に${#var} (varは変数名)という記法を使う。 こんな感じ。

$ arr=(A B C)
$ echo ${#arr[@]}
3

また、文字列を入れると文字数をカウントしてくれる

$ hoge=12345
$ echo ${#hoge}
5

文法上は ${#?}$? の文字数を、${##}$# の文字数をカウントする。 そのため、文字列として1文字以上を入れると1以外になり得る。

$ (exit 255)
$ echo ${#?}
3

ご存知の通り $? は終了ステータスであり、$# は引数の数として利用されている。 そのため、多くの場合は1と等価ではあるが、例外もあることがわかる。

なお、bashのソースコード上は${#-}${##}${#?}${#@}の4つについて評価をするマクロが存在するlink

${#@}は引数の数をカウントする際に使える。よくシェルスクリプトを書く人には$#の方が馴染みがあるかもしれない。 ${#-}はそのシェルで渡されたオプションの個数をカウントする際に使える。

注釈

※1: [2019/09/02追記] 3.5.3 Shell Parameter Expansion より "length and offset are arithmetic expressions (see Shell Arithmetic)." thanks @qwertanus

※2: [2019/09/03追記] @qwertanus さんからの指摘があり修正しました。

※3: 6.5 Shell Arithmetic "A shell variable that is null or unset evaluates to 0 when referenced by name without using the parameter expansion syntax."

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment