Een Minsky-machine in ncurses terminfo

De parameteruitbreiding van ncurses terminfo kan Minsky-machines met twee tellers simuleren. Hiermee is het mogelijk om een "parasitair" Fibonacci-programma in je terminal te draaien, dat wordt aangestuurd door /usr/bin/top.

1. Inleiding

In 2019 merkte Gwen Weinholt (weinholt.se) op dat Terminfo een stackmachine bevat met parameters, rekenkunde en logica, if-then-else, output en persistente variabelen. Gwen stelde vast dat terminfo dicht bij een Turing-machine ligt, maar dat het lussen (loops) mist. Dit zou kunnen worden opgelost door de iteratie buiten de taal zelf te plaatsen.

Recentelijk heeft Martin Tournoij het Go-pakket termfo geïmplementeerd en opgemerkt dat "terminfo-bestanden Turing-compleet zijn".

Dit artikel bouwt voort op deze observaties en maakt het argument van universaliteit expliciet via een reductie van Minsky-machines met twee tellers.

2. Terminfo is een kleine programmeertaal

Vroege fysieke terminals gebruikten verschillende escape-sequenties om de cursor te verplaatsen, tekens te verwijderen, dikgedrukt te schrijven of kleuren te gebruiken, enzovoort. Terminal-applicaties moeten weten welke escape-sequenties een terminal begrijpt. De omgevingsvariabele $TERM geeft het terminaltype aan, en de terminfo-database beschrijft de mogelijkheden (capabilities). De database is in feite een set van gecompileerde sleutels en waarden, meestal opgeslagen in /usr/share/terminfo.

Een typisch macOS Terminal-profiel declareert TERM=xterm-256color. Het uitvoeren van infocmp xterm-256color laat onder andere de volgende mogelijkheid zien: cup=\E[%i%p1%d;%p2%dH. cup is de sleutel die wordt gebruikt voor cursor-adressering. Curses levert argumenten voor rij en kolom die beginnen bij nul, en %i verhoogt de eerste twee parameters, omdat de escape-sequentie van de terminal coördinaten gebruikt die beginnen bij één.

De taal wordt kort gepresenteerd in ncurses/tinfo/lib_tparm.c. De relevante onderdelen voor dit artikel zijn:

InstructieBetekenis
%{n}push integer constante $n$
%gXpush register $X$
%PXpop naar register $X$
%=pop twee, push resultaat van gelijkheid (equal)
%+pop twee, push som (sum)
%-pop twee, push aftrekking (subtraction)
%dpop en print
%p1 %p2push de rij- en kolomargumenten die aan cup zijn doorgegeven (geteld vanaf 0)
%?c %t a %e b %;if $c$ dan $a$, anders $b$
%? c1 %t a1 %e c2 %t a2 %e b %;if $c1$ dan $a1$, else if $c2$ dan $a2$, anders $b$

De taal maakt gebruik van 26 hoofdletters en 26 kleine letters als registers (A-Z en a-z). De hoofdletterregisters zijn bedoeld om persistent te blijven over verschillende uitbreidingen binnen één proces.

Het interessante is dat we onze eigen terminal-conventies kunnen gebruiken en kunnen definiëren wat er gebeurt wanneer curses bijvoorbeeld de cursor verplaatst. In het volgende voorbeeld compileren we een terminal genaamd test, met een cup-regel die "hello" print op rij 5, kolom 30, voordat de cursor naar de gevraagde positie wordt verplaatst.

test.txt:

test,cup=\E[5;30H hello \E[%i%p1%d;%p2%dH,

Compileer en run met:

tic test.txt; TERM=test; tput cup 0 0

Let op: standaard installeert tic gebruikersvermeldingen in ~/.terminfo/. Om ze in de huidige directory te compileren en op te zoeken, gebruik dan export TERMINFO="$PWD".

We hebben dus een kleine taal met rekenkunde, persistente status en conditionele control flow. Zoals in sectie 1 vermeld, ontbreekt een interne lus. Alleen herhaalde uitbreiding van capabilities kan dienen als klok.

3. Een Minsky-tellermachine in terminfo

Stel dat $A$ en $B$ de twee registers zijn en $Z$ de programmateller (program counter).

Een willekeurige instructie $i$: INC A -> j kan worden gecompileerd als: Als $Z == i$: $A = A+1, Z = j$

In terminfo: %gZ%{i}%=%t %gA%{1}%+%PA %{j}%PZ (vereenvoudigd).

Hetzelfde geldt voor $j$: JZDEC A -> k, l, wat wordt: Als $Z == j$: Als $A == 0$: $Z = k$ Anders: $A = A-1, Z = l$

We kunnen een enkele if/else-if keten op $Z$ maken, met één vertakking per instructie. Elke uitbreiding voert één stap van de machine uit, en herhaalde uitbreidingen zorgen voor de klok.

Dit implementeert direct de instructieset van een Minsky-machine met twee tellers. Met geïdealiseerde, onbegrensde tellers en capability-grootte is deze constructie computationeel universeel.

In de praktijk begrenzen concrete ncurses-implementaties zowel de registerwaarden als de grootte van de terminfo-vermelding, waardoor elke werkelijke instantie een finite-state machine is.

4. Optellen

Hier is een kleine telmachine die eenvoudig te inspecteren en te begrijpen is. De machine berekent $4 + 9 = 13$. Elke uitbreiding print de huidige status naar stdout, en het programma verzendt niet de uiteindelijke escape-sequentie voor cursorverplaatsing.

Minsky-programma: 0: $A=4, B=9, Z=1$ (initialisatie) 1: JZDEC B, 3, 2 (als $B$ leeg is, stop) 2: INC A, 1 (verplaats één eenheid van $B$ naar $A$) 3: HALT (stop)

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
%;
# print the trace after executing this expansion
Z=%gZ%d A=%gA%d B=%gB%d\n,

Compileer en run door de regels 20 keer uit te breiden (het aantal uitbreidingen dat de machine nodig heeft voordat hij stopt):

tic add.txt
TERM=add; yes 'cup 0 0' | head -n 20 | tput -S

Laatste regel van de output: Z=3 A=13 B=0

5. Fibonacci

Net als bij de telmachine kunnen we een Fibonacci-machine bouwen met 3 registers:

  • $A = F(N-1)$
  • $B = F(N)$
  • $N = \text{huidige Fibonacci-index, ook gebruikt als initialisatievlag}$

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,

Deze regels betekenen:

  • Als $(N == 0)$, dan $A = 0, B = 1, N = 1$.
  • Anders: stack $B' = A + B$, $A' = \text{oude } B$, $N = N + 1$.
  • Print de trace-regel.

Compileer en run met:

tic fib.txt
TERM=fib; yes 'cup 0 0' | head -n 10 | tput -S

Bij head -n 10 is de laatste regel: A=34 B=55 N=10 F(10)=55

6. Fibonacci, geklokt door /usr/bin/top

De vorige machine wordt aangestuurd door yes, dat herhaaldelijk dezelfde regel uitzendt. Een interessante variant is om een ander programma als klok te gebruiken dat het scherm met regelmatige intervallen opnieuw tekent.

Bijvoorbeeld: /usr/bin/top tekent elke seconde zijn klok in de header opnieuw. In mijn configuratie veroorzaakt dit een cup(0,78) aanroep wanneer het secondenveld wordt bijgewerkt. Deze specifieke cursorverplaatsing kan worden gebruikt als klok. De exacte coördinaat hangt af van de layout van top en de grootte van de terminal.

fib_top.txt:

fib_top,cup=
# advanced one step when top addresses the seconds digit at (0,78)
%?%p1%{0}%=%p2%{78}%=%A%t\
%?%gN%{0}%=%t\
%{0}%PA%{1}%PB%{1}%PN\
%e\
%gA%gB%+%gB%PA%PB%gN%{1}%+%PN\
%;\
%;
# show the current result in the window title
\E]0;F(%gN%d)=%gB%d\007
# emit the cursor move top requested
\E[%p1%{1}%+%d;%p2%{1}%+%dH,

Compileer en run met:

tic fib_top.txt
TERM=fib_top; /usr/bin/top

Dit resulteert in een parasitair Fibonacci-programma in je terminal, aangestuurd door /usr/bin/top, waarbij de output in de titel van het venster verschijnt.

7. Beveiligingsimplicaties

Is dit een bug? Er hoeft niets "gebroken" te worden in het Fibonacci-voorbeeld. Rekenkunde, conditionele logica, persistente variabelen, parameteruitbreiding en cursor-adressering werken allemaal zoals bedoeld. Het onverwachte gedrag ontstaat uit de compositie van deze functies, wat het eerder een "hack" dan een bug maakt.

Het interessante beveiligingsaspect is de vertrouwensgrens: een door de gebruiker gecontroleerd terminfo-programma wordt herhaaldelijk geïnterpreteerd door ncurses binnen een ander proces. Maar zelfs wanneer het wordt uitgevoerd door een setuid-root programma zoals top, is het Fibonacci-programma geen exploit voor privilege-escalatie. Terminfo-parameteruitbreiding kan geen bestanden openen, geen commando's uitvoeren of syscalls doen.

Op zichzelf produceert het voorbeeld alleen terminal-output. Alleen een kwetsbaarheid in de terminfo-parser of de parameter-evaluator in die bevoorrechte context zou een impact op de privileges kunnen hebben.

8. Conclusie

Dit artikel demonstreert dat:

  • terminfo niet alleen passieve terminal-metadata is, maar een kleine, stateful programmeertaal;
  • we een Minsky-machine met twee tellers kunnen implementeren middels herhaalde ncurses terminfo-uitbreiding;
  • de constructie computationeel universeel is, uitgaande van geïdealiseerde onbegrensde tellers en een onbegrensd aantal uitbreidingsstappen;
  • de regels kunnen worden uitgebreid binnen een host-proces, waardoor het effectief als een parasiet fungeert.