/usr/bin/top 内の寄生的なフィボナッチ計算

ニコラス・セリオ 計算 > ncurses terminfo内のミンキーマシン🎰 ncurses terminfoのパラメータ展開は、2カウンタのミンキーマシンをシミュレートできます。ホストされた寄生フィボナッチプログラムをターミナルに、/usr/bin/topでクロックします。 2026年10月2日 1.はじめに 2019年に、Gwen Weinholt (weinholt.se) は、Terminfoにパラメータ、算術と論理、if-then-else、出力、永続変数を持つスタックマシンが搭載されていることに気づきました。Gwenは、terminfoはチューリングマシンに近いがループが欠けていると指摘し、これはイテレーションを言語の外にプッシュすることで回避できると述べました。最近、Martin TournoijはGoのtermfoパッケージを実装し、「terminfoファイルはチューリング完全である」と述べました。この記事はこれらの観察に基づいており、2カウンタのミンキーマシンからの還元により、普遍性の主張を明確にします。 2. Terminfoは小さなプログラミング言語です 初期の物理ターミナルは、カーソル移動、文字削除、太字や色での書き込みなどのためにさまざまなエスケープシーケンスを使用していました。ターミナルアプリケーションは、ターミナルがどのエスケープシーケンスを理解するかを知る必要があります。$TERM環境変数はターミナルタイプを指定し、terminfoデータベースはその機能を記述します。データベースは実際にはコンパイルされたキーと値のセットであり、通常は/usr/share/terminfoに格納されています。典型的なmacOSターミナルプロファイルはTERM=xterm-256colorを宣言します。infocmp xterm-256colorを実行すると、他の機能の中でも特に次のようなものが見られます。 cup=\E[%i%p1%d;%p2%dH。 cupはカーソルアドレス指定に使用されるキーです。Cursesは0ベースの行と列の引数を供給し、%iは最初の2つのパラメータをインクリメントします。なぜなら、ターミナルエスケープシーケンスは1ベースの座標を使用するからです。 言語はncurses/tinfo/lib_tparm.cで簡単に紹介されています。この記事に関連する部分： 命令 意味 %{n} 整数定数nをプッシュする %gX レジスタXをプッシュする %PX レジスタXにポップする %= %+ %- 2つポップし、等しい/合計/減算をプッシュする %d ポップして印刷する %p1 %p2 cupに渡された行と列の引数（0からカウント）をプッシュする %?c %t a %e b %; cが真ならa、偽ならb 言語は26個の大文字と26個の小文字のレジスタ（A-Zおよびa-z）を使用します。大文字のレジスタは、単一プロセス内のさまざまな展開で持続することを意図したものです。 興味深いのは、独自のターミナル規約を使用し、たとえばcursesがカーソルを移動したときに何が起こるかを定義できることです。次の例では、testという名前のターミナルをコンパイルし、cupルールがカーソルを要求された位置に移動する前に、行5、列30にhelloと表示するように設定します。 test.txt: test,cup=\E[5;30H hello \E[%i%p1%d;%p2%dH, コンパイルして実行するには： tic test.txt; TERM=test; tput cup 0 0 注意：デフォルトでは、ticはユーザーエントリを通常~/.terminfo/の下にインストールします。代わりに現在のディレクトリでコンパイルして検索するには、export TERMINFO="$PWD"を使用します。 したがって、算術演算、永続的な状態、条件付き制御フローを備えた小さな言語があります。セクション1で述べたように、内部ループが欠けています。繰り返しの機能展開のみがクロックを提供できます。 3. Terminfo内のミンキーカウンタマシン AとBを2つのレジスタ、Zをプログラムカウンタとします。任意の命令i: INC A -> jは次のようにコンパイルできます。 if Z == i: A = A+1 Z = j またはterminfoで： %gA%{1}%+%PA%{j}%PZ。 同様に、j: JZDEC A -> k, lは次のようにコンパイルされます。 if Z == j: if A == 0: Z = k else: A = A-1 Z = l Zに対する単一のif / else-ifチェーンを持つことができ、命令ごとに1つのブランチがあります。各展開は1つのマシンステップを実行し、繰り返しの展開がクロックを提供します。これは2カウンタのミンキーマシンの命令セットを直接実装します。理想的な無限カウンタと機能サイズを仮定すると、この構築は計算上普遍的です。実際には、具体的なncurses実装はレジスタ値とterminfoエントリサイズの Сboth をバインドするため、実際のインスタンスはすべて有限状態です。 4. 加算 ここでは、検査と理解が容易な小さな加算機を示します。このマシンは4 + 9 = 13を計算します。各展開は現在の状態を標準出力に印刷し、プログラムは最終的なカーソル移動エスケープを発行しません。 ミンキープログラム： 0: A=4, B=9, Z=1 # 初期化 1: JZDEC B,3,2 # Bが空なら停止 2: INC A,1 # BからAへ1単位移動 3: HALT # 停止 add.txt: add,cup= # if (Z == 0) { A = 4; B = 9; Z = 1 } %?%gZ%{0}%=%t %{4}%PA %{9}%PB %{1}%PZ # else if (Z == 1) { if (B == 0) { Z = 3 } else { B = B-1; Z = 2 } } %e%gZ%{1}%=%t %?%gB%{0}%=%t %{3}%PZ %e %gB%{1}%-%PB %{2}%PZ %; # else if (Z == 2) { A = A + 1; Z = 1 } %e%gZ%{2}%=%t %gA%{1}%+%PA %{1}%PZ # else if (Z == 3) { HALTED } %e%gZ%{3}%=%t %; # この展開を実行した後にトレースを印刷する Z=%gZ%d A=%gA%d B=%gB%d\n, コンパイルして実行するには、マシンが停止する前に必要な展開回数（20回）でルールを拡張します。 tic add.txt TERM=add; yes 'cup 0 0' | head -n 20 | tput -S 最後の出力行： Z=3 A=13 B=0 5. フィボナッチ 加算機と同様に、3つのレジスタを使用してフィボナッチマシンを構築できます。 A = F(N-1) B = F(N) N = 現在のフィボナッチインデックス、初期化フラグとしても使用 fib.txt: fib,cup= %?%gN%{0}%=%t%{0}%PA%{1}%PB%{1}%PN %e%gA%gB%+%gB%PA%PB%gN%{1}%+%PN%; A=%gA%d B=%gB%d N=%gN%d F(%gN%d)=%gB%d\r\n, これらの行は次のことを意味します。 if (N == 0) { A = 0; B = 1; N = 1; } else { stack: B' = A + B, A' = old B; N = N + 1; } トレース行を印刷する コンパイルして実行するには： tic fib.txt TERM=fib; yes 'cup 0 0' | head -n 10 | tput -S head -n 10を使用すると、最後の行は次のようになります。 A=34 B=55 N=10 F(10)=55 6. フィボナッチ、/usr/bin/topでクロックされる 前のマシンは、同じ行を繰り返し発行するyesでクロックされます。興味深いバリアントは、別のプログラムがクロックを提供し、定期的に画面を再描画することです。たとえば、/usr/bin/topは毎秒ヘッダークロックを再描画します。私のセットアップでは、秒フィールドが再描画されるときにcup(0,78)呼び出しが発生します。このカーソル移動自体がクロック（クロックをクロックするクロック…）として使用できます。正確な座標は、topのレイアウトとターミナルのサイズによって異なります。 fib_top.txt: fib_top,cup= # topが秒フィールドを(0,78)でアドレスするときに1ステップ進める %?%p1%{0}%=%p2%{78}%=%A%t\n %?%gN%{0}%=%t\n %{0}%PA%{1}%PB%{1}%PN\n %e\n %{0}%gA%gB%+%gB%PA%PB%gN%{1}%+%PN\n %;\n%; # 現在の結果をウィンドウタイトルに表示する \E]0;F(%gN%d)=%gB%d\007 # topが要求したカーソル移動を発行する \E[%p1%{1}%+%d;%p2%{1}%+%dH, コンパイルして実行するには： tic fib_top.txt TERM=fib_top; /usr/bin/top /usr/bin/topによってクロックされる、ターミナル内の寄生フィボナッチプログラム。 ウィンドウタイトルに出力。 7. セキュリティ上の考慮事項 これはバグか？ フィボナッチの例では壊れる必要のあるものはありません。算術演算、条件分岐、永続変数、パラメータ展開、カーソルアドレス指定はすべて意図したとおりに動作します。予期しない動作はそれらの組み合わせから生じるため、バグではなくハックです。興味深いセキュリティプロパティは信頼の境界です。ユーザー制御のterminfoプログラムは、別のプロセス内でncursesによって繰り返し解釈されます。しかし、topのようなsetuid-rootプログラムによって評価されたとしても、フィボナッチプログラムは特権昇格の脆弱性ではありません。Terminfoパラメータ展開は、ファイルを開いたり、コマンドを実行したり、システムコールを発行したりすることはできません。それ自体では、この例はターミナル出力のみを生成します。特権コンテキストでのterminfoパーサーまたはパラメータ評価プログラムの脆弱性のみが、特権的な影響を与える可能性があります。 8. 結論 この記事は次を示しています。 terminfoは受動的なターミナルメタデータだけでなく、状態を持つ小さなプログラミング言語です。 繰り返しのncurses terminfo展開を使用して2カウンタのミンキーマシンを実装できます。 この構築は、理想的な無限カウンタと無限の展開ステップ数を仮定すると、計算上普遍的です。 ルールはホストプロセス内で展開でき、効果的に寄生虫として機能します。