Największa tajemnica CROOK-a

Błędy w działaniu kompilatora C

Na przestrzeni ostatnich niemal trzech lat, które minęły od pierwszego uruchomienia CROOK-5 w emulatorze EM400, system operacyjny z Politechniki Gdańskiej stawiał wiele zagadek. Większość z nich wynikała z niedostatków w emulacji MERY-400. System czasami odmawiał współpracy, a jego narzędzia nie zawsze spełniały swoje funkcje. Sytuacja poprawiła się znacznie, gdy po kolejnych poprawkach emulator przeszedł wreszcie poprawnie testy procesora i arytmometru dostarczane przez producenta MERY-400. A kiedy udokumentowane zostały i zaimplementowane wszystkie przeróbki procesora, CROOK i narzędzia systemowe przestały sprawiać jakiekolwiek problemy.

Niestety nie można było tego samego powiedzieć o programach użytkowych. Niektóre z nich od czasu do czasu kończyły się błędami, inne niby działały, ale konsekwentnie odmawiały spełniania jakiejś wybranej funkcji. Spektrum problemów było szerokie, a częstotliwość i okoliczności ich występowania wydawały się być przypadkowe. Dotyczyły one jednak zawsze grupy tych samych binariów.

Szczególnie problematyczny okazał się kompilator C. Tylko jedna na kilka- kilkanaście kompilacji przebiegała poprawnie. Pozostałe kończyły się smutnym "error in program", tragicznym "WRONG INSTRUCTION", dziwnymi "ERR BRAK O^PERATORA" lub "ERR BR^AK ZMIENNEJ", czy wreszcie zupełnym zapętleniem się programu.

Powtarzalność problemów była w tym przypadku na tyle wysoka, że kompilator C stał się idealnym kandydatem do podjęcia próby rozwiązania tej ostatniej zagadki CROOK-a.

Winny CROOK?

Gdzie więc przyczyna?

Za każdym razem, kiedy pod kontrolą systemu CROOK w emulatorze dzieje się coś dziwnego, jedna hipoteza powraca jak mantra: czy z tą wersją systemu aby na pewno działały poprawnie wszystkie programy?

Obraz dysku z systemem uruchamianym w EM400 pochodzi z maszyny, która do końca swoich dni była sprawna i wykorzystywana przez autorów CROOK-a do jego rozwoju. Nowe funkcjonalności były dodawane, inne usprawniane. Czy na pewno zachowana była ciągła kompatybilność? Niepokój jest tym bardziej uzasadniony, że dziwną plagą dotknięte były głównie nowsze binaria. Budowane narzędziami, które nie istniały dla starszych wersji systemu, na przykład konsolidatorem LINK stworzonym w Instytucie Informatyki Uniwersytetu Warszawskiego.

Hipotezie winiącej CROOK-a przeczy jednak jeden, mocny fakt. W przypadku kompilatora C dziwne zachowania powtarzają się na wszystkich jądrach systemu uczestniczących w testach: 8/15, 8/14, 8/7 i 7/6. Trudno sobie wyobrazić, że na maszynie używanej regularnie przez kilku programistów, kompilator C był niesprawny na przestrzeni wielu miesięcy.

Winny EM400?

Mimo setek dni spędzonych na zgłębianiu szczegółów pracy procesora MERY-400 i implementowaniu ich w emulatorze, wciąż najbardziej prawdopodobną przyczyną pozostaje błąd w emulacji.

EM400 przygotowany jest na badanie takich sytuacji i pozwala z dużą dokładnością śledzić wszystko to, co dzieje się w emulowanym systemie. Może zapisywać do pliku log zawierający nie tylko każdy krok procesora, ale również wywołania systemowe, operacje I/O, obsługę przerwań, etc. Choć taki log ma nieraz kilkaset megabajtów i jego analiza bywa żmudna, to jest to niemal pewna droga do sukcesu.

Zacznijmy więc od takiego właśnie „podglądnięcia” działań kompilatora C. Już kilka minut analizy zapisów w logu pod kątem najbardziej prawdopodobnych anomalii prowadzi do następującego fragmentu:

CPU 2 | USR  2:0xf1e9 CC0    |     AWT r7, -1           T = -1
CPU 2 | USR  2:0xf1ea CC0    |     AW r7, [r2]          N = 0x53c0 = 21440
CPU 2 | USR  2:0xf1eb CC0    |     .word 0x0022        
CPU 2 | USR  2:0xf1eb CC0    |     (ineffective: illegal instruction) opcode: 000 000 0 000 100 010 (0x0022)

Mówi on, że w trakcie wykonywania procesu w przestrzeni użytkownika, procesor trafił na nielegalną instrukcję o kodzie 0x22. Dziwne, bo deasemblacja zbioru z programem pokazuje, że powinna w tym miejscu być zupełnie legalna instrukcja:

0xf1e9:             AWT   r7, -1
0xf1ea:             AW    r7, [r2]
0xf1eb:             TW    r6, word_5944

Podejrzenie o błąd w emulatorze nabiera sensu. Możliwe wyjaśnienia takiej sytuacji dzielą się zasadniczo na dwie grupy:

1. Emulator dokonuje niepoprawnego odczytu pamięci, mimo że w komórce znajduje się poprawna wartość (przyczyną może być na przykład niespójny stan pamięci między wątkami, czy błąd w emulacji adresowania).
2. Wartość 0x22 została do komórki faktycznie zapisana (np. z powodu błędu w adresowaniu, czy błędu po stronie urządzenia I/O, piszącego do pamięci), a odczyt jest poprawny.

Większość potencjalnych błędów z pierwszej grupy została szybko wyeliminowana testami, w które nie ma się co tutaj zagłębiać. Pozostaje w zasadzie tylko druga, znacznie bardziej prawdopodobna możliwość: coś nadpisuje zawartość nieszczęsnej komórki 0xf1eb w segmencie pamięci kompilatora. Po dodaniu śledzenia zapisów pod ten adres okazuje się jednak, że oprócz wstępnego ładowania obrazu procesu, poszukiwany zapis nie jest w ogóle wykonywany! Przy kolejnych uruchomieniach kompilatora komórka 0xf1eb zawiera poprawny rozkaz, a kompilator jak nie działał, tak nie działa.

Spróbujmy w takim razie zebrać większą próbkę wystąpień pierwotnie zauważonego problemu. Krok wstecz i kolejne logi z różnych wywołań CC0 pokazują, że nielegalne instrukcje owszem, wciąż pojawiają się w kodzie kompilatora, ale pod różnymi, losowo wyglądającymi (sic!) adresami. W dodatku niemal zawsze mają ten sam kod: 0x22.

Dobrze, postawmy więc pytanie nieco inaczej: Co (skąd pochodząca instrukcja) zapisuje wartość 0x22 gdzieś (gdziekolwiek) w przestrzeni adresowej procesu użytkownika? Tym razem uzyskanie odpowiedzi wymaga nieco więcej zachodu, ale ostatecznie odnajduje się ona w tym samym logu emulacji w postaci zapisu:

CPU 2 |  OS  2:0x137a CC0    |     PW r6, r1            N = 0xf1eb = -3605

Ta jedna, niewinnie wyglądająca linia, jest niczym obuch celnie wymierzony w czerep autora niniejszego tekstu. Znaczy bowiem, że pamięć procesu niszczona jest instrukcją pochodzącą wprost z jądra systemu CROOK-5.

Jednak CROOK

Ile dobrej woli by nie włożyć w interpretację tego faktu, to nadpisywanie rozkazów w obszarze procesu użytkownika nie należy do standardowych zadań systemu operacyjnego. Z czym więc mamy do czynienia? Zwykły błąd? Brutalny żart? Zmyślny sabotaż? Przebiegłe zabezpieczenie przed nieautoryzowanym uruchamianiem? A może ktoś celowo zadbał o to, żeby w niepowołanych rękach system działał nie do końca poprawnie? Sensacyjne hipotezy można by mnożyć, ale powstrzymajmy póki co fantazję i spróbujmy rzeczowej analizy.

Bezpośrednie sąsiedztwo kodu odpowiedzialnego za zapis wygląda następująco:

                  BLOK:
    0x136b:                 RJ   r4, GENAN
    0x136d:                 PW   r1, [BLPASC+r5]
    0x136f:                 LW   r1, [BAR+r5]
    0x1371:                 BB   r1, 1\9
    0x1373:                 UJS  TPRI+3
(4) 0x1374:                 RJ   r4, GENAN
    0x1376:                 LWT  r4, 062
    0x1377:                 NR   r4, r1
    0x1378:                 CWT  r4, 042
    0x1379:                 BLC  ?E
(3) 0x137a:                 PW   r6, r1
    0x137b:                 UJS  TPRI+3
(1)               TPRI:
    0x137c:                 LW   r3, [BLPASC+r5]
(2) 0x137e:                 IRB  r3, BLOK
          ...

Wszystko zaczyna się w procedurze obsługi wywołania systemowego wczytaj rekord (1), realizującego czytanie ze strumienia. Dlaczego akurat tam? Diabli wiedzą, ale póki co nie zaprzątajmy sobie tym głowy. Ważne, że następuje w niej warunkowy skok do procedury BLOK (2), która w przedostatniej instrukcji (3) dokonuje warunkowo felernego zapisu. Zapis ten, prócz tego, że sam w sobie jest dziwny, jest też podejrzany z punktu widzenia ścieżki wykonywania kodu:

1. Zawartość rejestru r6, który przechowuje zapisywaną wartość, nie jest ustawiana przez system operacyjny. Jest w nim to, co akurat zostawił tam proces użytkownika przed wywołaniem systemowym. Według dokumentacji wywołanie to nie używa rejestru r6 do przekazywania argumentów, więc dlaczego system operacyjny miałby z rejestru r6 w ten sposób korzystać?
2. Zawartość rejestru r1, który przechowuje docelowy adres zapisu, ustawiana jest w procedurze GENAN (4), która na pierwszy rzut oka wygląda ze wszech miar jak generator liczb pseudolosowych.

Błąd?

Dobrze zatem. Skoro mamy jedną linię asemblera, z którą związane są aż trzy wyjątkowo dziwne obserwacje, to załóżmy przez chwilę, że faktycznie mamy do czynienia z błędem. Spróbujmy uruchomić CROOK-a z małą poprawką: Zablokujmy podejrzany zapis przez proste zastąpienie instrukcji pod adresem 0x137a instrukcją NOP. Rezultat? W tak „naprawionym” CROOK-u zarówno kompilator, jak i inne nie działające wcześniej programy funkcjonują poprawnie.

Za każdym razem.

Bez najmniejszych efektów ubocznych.

Ale zanim ktoś zdąży zakrzyknąć: „Czyli ewidentny błąd w CROOK-u!”, to napiszę o kolejnej obserwacji: Procedura BLOK występuje we wszystkich zachowanych wersjach jądra systemu, w postaci nie zmienionej ani o jotę. Wygląda na to, że nie jest to jakaś przypadkowa linia, która wkradła się z jedną, nieudaną edycją, a zamierzone, utrzymywane z wersji na wersję zachowanie systemu.

Nie błąd, czyli co?

Sprawa zaczyna się robić coraz ciekawsza, co przy okazji nie ułatwia utrzymywania wyobraźni w ryzach. Ach, te chwytliwe nagłówki: „System operacyjny z Politechniki Gdańskiej odmawia wykonywania binariów z Uniwersytetu Warszawskiego!”, „Wielka zemsta autorów CROOK-a!”.

Żarty na bok, rzetelna analiza na front. Skoro bezpośrednie sąsiedztwo źródła problemu nie wyjaśnia wiele, to poszukajmy krok dalej, w samej procedurze GENAN.

1. Czy jest ona używana gdzieś indziej? Nie. Mamy więc w CROOK-u generator liczb pseudolosowych, używany wyłącznie do wybrania adresu, pod który system dokonuje niszczącego zapisu.
2. Jakie inne punkty zaczepienia daje ciało procedury? Raczej mizerne:
   • mamy tam zmienną LAST opisana w komentarzu jako „GENERATOR”, co jedynie umacnia hipotezę z generatorem pseudolosowym,
   • są wywoływane dwie inne procedury, wyglądające na pomocnicze: GENOB i GENAD, prowadzące donikąd.

Tyle. Żadnych dalszych punktów zaczepienia. Spójrzmy więc na kod w bezpośrednim otoczeniu generatora, może się poszczęści. Dwieście linii niczym nie wyróżniającego się asemblera wyżej trafia się takie coś:

C1=17152.    [   A1+C1]
C2=17152.    [A1:A2+C2.]
C3=17152.    [   M +C3.]
C4=17152.    [A2:A3+C4.]
C5=17152.    [   A1+C5.]
C6=17152.    [A3:A2+C6.]
CN=17152.    [GEN(NR+CN,(A3-A2)mod077)  CR5  NR+CN  PASC ]
C7=17152.    [   S +C7.] [ /S/=/S/+A2-A1 ]

Osiem stałych, opatrzonych dziwnym, wyjątkowo bogatym jak na CROOK-a komentarzem. Fragment zdecydowanie odstaje od reszty, ale uwagę przykuwa coś innego: powtarzająca się liczba 17152.

Odpowiedź na Wielkie Pytanie o Życie, Wszechświat i całą resztę

Deep Thought się jednak pomylił. CROOK mówi, że nie 42, tylko 17152.

Zobrazowany dysk MERY-400 z Politechniki Gdańskiej to około 20MB danych. Zawartość, lub przynajmniej znaczenie większości plików jest zrozumiałe. Ale niektóre z nich pozostawiają w pamięci ślad: „W zasadzie wiadomo co to jest, ale jakoś to dziwnie wygląda”. Takie ślady okazują się czasami być przydatne wiele miesięcy później, dopełniając brakujący fragment innej układanki. Tak też było w tym przypadku.

Liczba 17152 już gdzieś, kiedyś się pojawiła. W jakimś nie do końca zrozumiałym kontekście, przy okazji prac nad czymś zupełnie innym. Poszukajmy zatem: „grep -r 17152 *” odnajduje makro służące do budowania jakiegoś programu użytkowego. Do tego programu linkowany jest obiekt budowany assemblerem GASS z następującego źródła:

          .UNIT        SECRET
SYSID      =           %B                 ; NUMER ZEGARA
          .USE         CODE
$         .XVAR        1
SECRET_M  .RES         2
          .USE         DATA
          .IMP         .croota,mkmain
          .EXP         IC0,SECRET_M,main
C          =           17152
          .DATA        A1+C
A1        .DATA        A2+C,SECRET_M+C
S         .DATA        0
A2        .DATA        A3+C,A1+C
A3        .DATA        A2+C,SYSID+C,S+C

          .RES         2
IC0        STRA        $(4)
           SET     R4, #$
           CALL    R5, .croota
main       CALL    R5, mkmain
          .END         IC0

Zbieżność nazw symboli i stałych pomiędzy programem użytkowym a jądrem systemu, operacje arytmetyczne odpowiadające tym w komentarzach źródła systemu – to nie może być przypadek. Lokalizacja w pobliżu symbolu main również nie jest przypadkowa. Do tego podejrzany generator liczb pseudolosowych i dziwnie zachowujące się programy. Fragmenty układanki zaczynają pasować do siebie idealnie. I choć dookoła dużo jeszcze pustych przestrzeni, których wypełnienie wymagać będzie sporo pracy, to można bez cienia wątpliwości stwierdzić:

W połowie lat '80, kiedy nie nazwany jeszcze nawet DRM zaczynał dopiero nieśmiało raczkować, stworzony w Instytucie Okrętowym Politechniki Gdańskiej, działający na MERZE-400 CROOK-5 dysponował wbudowanymi w system operacyjny mechanizmami pozwalającymi twórcom oprogramowania chronić je przed nieautoryzowanym uruchamianiem. Mechanizmami nie wspomnianymi w żadnej dokumentacji.