Jakub Kaszycki

Zadania z biblioteczką considered beneficial

Ten artykuł jest swoistą ripostą, reakcją na artykuł mojego kolegi, szkalujący zadania z biblioteczkami. Oryginalny artykuł jest niezwykle głęboki i merytoryczny oraz będę się do niego odwoływał, więc gorąco polecam przeczytać go w pierwszej kolejności.

Powszechnie wiadomo, że Olimpiada Informatyczna nie może polegać tylko na algorytmach, bo byłby to wtedy konkurs matematyczny. Przejmując niektóre swoje aspekty np. od LOGII, niekoniecznie nieświadomie wzbogaciła umiejętności uczestników na parę różnych sposobów. Są to oczywistości takie jak rzeczywiście niewielkie limity czasowe, akcentujące potrzebę niezwłocznej odpowiedzi ze strony programu i zwiększające ilość obsłużonych żądań na minutę, ale są też rzeczy, których zalet niektórzy mogą w ogóle nie zauważyć - mam na myśli zadania z biblioteczkami.

Umieszczanie na każdych warsztatach i na każdym obozie informatycznym zadań z biblioteczkami jest po prostu logiczne - mają przecież przygotowywać do Olimpiady i (a przynajmniej niektóre) naśladować Olimpiadę, więc jasne jest, że wprowadza się dodatkowe elementy upodabniające.

Łatwo odrzucić je od razu, bojkotować je i zignorować wszelkie zalety mając nadzieję na jak najrzadsze ich występowanie. Myślenie takie jest przejawem paranoi, a nie zdroworozsądkowego podejścia - naszym obowiązkiem wobec przyszłych koderów w kabinach lub open space’ach jest je propagować.

Zrozumieć

Sam koncept biblioteczek wydaje się skomplikowany, przekombinowany i głupi; możemy odnieść wrażenie, że przez to niektóre problemy wymagające rozwiązań online które normalnie nigdy nie dostałyby się na konkurs pojawią się bez żadnego ostrzeżenia. Niech by to! Kolejne dyskretne poszerzenie i tak zbyt dużego zakresu merytorycznego konkursu!

Jednak:

Czytanie dokumentacji

Jak wiedzą wszyscy pasjonaci Kangura czy Alfika, prawidłowe wypełnienie karty odpowiedzi jest częścią konkursu. Tak samo jak typowy Janusz kursuje w trójkącie telewizor-lodówka-łóżko, tak rasowy programista kursuje w trójkącie edytor-dokumentacja-Stack Overflow. Jednak jedną rzeczą jest wymuszenie na wyjściu czytelności/estetyki w celu zaprezentowania go użytkownikowi, a innym jest formatowanie znaków białych dla sprawdzarki. Zadania z biblioteczką rozwiązują ten problem - nie trzeba martwić się o format wyjścia, bo jest to seria deterministycznych wywołań deterministycznych funkcji deterministycznej biblioteczki, które same dbają o konieczne znaki białe. Sam miałem inny pomysł - zadania mogłyby wypisywać JSON’y, ale w sumie dotąd chyba nigdy z nikim się nim nie podzieliłem.

W ten sposób 30-70% treści każdego zadania z biblioteczką to precyzyjne, czysto techniczne wyjaśnienia związane z nieteorytycznym aspektem programowania.

Narzucanie konwencji

Mądre słowa dla każdego antysystemowca, kto nie chce mieć narzucanych konwencji (grafika Boldomatic, cytat z filmu Doctor Strange (2016))
Mądre słowa dla każdego antysystemowca, kto nie chce mieć narzucanych konwencji (grafika Boldomatic, cytat z filmu Doctor Strange (2016))

W zadaniach muszą być podane dokładne interfejsy komunikacji z rozwiązaniem. Dzięki temu osiąga się wiele rzeczy:

Bezpieczeństwo

Możemy chyba się zgodzić, że bezpieczeństwo bardzo łatwo wdrożyć w języku C++. Podstawowa obserwacja jest taka, że ewentualna korupcja stosu lub naruszenie ochrony pamięci zatrzymuje jedynie obecny proces. Oznacza to, że aby uchronić się przed tego typu atakami, wystarczy umieścić rozwiązanie razem z biblioteczką w osobnym procesie. Bardzo proste użycie dlopen() uniemożliwia przykrycie jakichkolwiek symboli (funkcji, zmiennych) w biblioteczce. Dalej, wrzucenie tego fragmentu z dlopen() do osobnego procesu zablokuje dostęp do pamięci sprawdzarki.

Python z kolei jest żółtodziobem konkursów programistycznych. Uważa się, że jeżeli w Pythonie nie można wywołać korupcji stosu (właściwie to można, trzeba tylko się znać), to już jest stuprocentowo bezpieczny. Jednak, powtarzam, interpreter Pythona nie ma wbudowanej konteneryzacji, bo to nie jest celem interpretera języka programowania. Jeżeli chcemy skonteneryzować program Pythona, możemy zrobić podproces w kontenerze i otworzyć do niego IPC/kolejkę/FIFO/cokolwiek. Wtedy żaden moduł ast czy globals() nie pomogą - biblioteczka będzie zawierała jedynie wywołania plików czy socketów. Sama sprawdzarka będzie całkowicie zabezpieczona.

Jeżeli jakiś kontest stosuje model security by obscurity, który ja bym raczej nazwał shitty and obscenity, to jest sam sobie winien. Od tego istnieją takie rzeczy jak WikiLeaks czy (bardziej do kodu) (Paste|Ghost|…)bin, żeby takie „kwiatki” wyciekały na światło dzienne. W tej kwestii absolutnie muszę zgodzić się z Jonaszem, nie jest to jednak wada zadań z biblioteczką, lecz leniwych i niedbałych twórców takich biblioteczek.

Tak, owszem, dlatego właśnie tych biblioteczek się nie publikuje. Gdyby w regulaminach olimpiad były ścisłe przepisy dotyczące transparencji, uwzględniające ujawnienie 100% testów i kodów sprawdzarek po konkursie, to nawet w kwestiach niealgorytmicznych zamiast wątpliwych heurystyk stosowano by najnowsze zdobycze i standardy bezpieczeństwa systemów.

Przedstawione zgłoszenie „pewnego uczestnika” tylko dowodzi tezy przedstawionej przeze mnie trzy akapity wyżej - biblioteczka powinna być prostą otoczką IPC a nie kompletną sprawdzarką. Nazywa się to izolacją i nie jest to wcale taki młody koncept (np. Apache od dłuższego czasu do obsłużenia żądań spawnuje podprocesy z opuszczonymi uprawnieniami i niezerowym UID/GID). Jest to również demonstracja zbyt luźnego systemu typów Pythona lub braku asercji w sprawdzarce, ale to temat na inny artykuł.

Także zaglądanie do kodu jest już wyżej przeze mnie wymienioną wątpliwą heurystyką - jest to wysoce zależne od niestabilnego ludzkiego czynnika, nieskalowalne i niepewne.

Uważam jednak, że można by wprowadzić „konkurs poboczny” - polegający na szukaniu dziur w systemie. Gdyby był odpowiednio nagradzany (chociażby ironicznie, wyjazdami na konferencje bezpieczeństwa systemów wraz ze zwolnieniem z zajęć szkolnych), to jestem pewien, że w ciągu parę lat systemy OI stałyby się fortem Knox konkursów informatycznych.

Alternatywa na siłę

Więc, mając nadzieję, że czytelnicy nie dali się przekonać mojemu koledze, wytknę teraz parę oczywistych wad alternatywy.

Opisana własność nie nazywa się asynchronizmem, bowiem asynchronizm I/O to zupełnie inny temat, co więcej jest on zazwyczaj opcjonalny i wyłącznie pozytywny. Nazwałbym to dosłownie „niezachowaniem kolejności komunikacji” lub „naruszeniem protokołu komunikacji”. Jest to związane z tym, że warstwa wejścia wyjścia plików (odpowiednik warstwy sieciowej i/lub warstwy transportowej w modelu OSI) jest poniżej warstwy sesji (najlepiej przybliżającej przedstawiony problem), a zgodnie z tym modelem warstwa niższa nie musi się przejmować zawiłościami warstwy wyższej. Więc jest to oczekiwane zachowanie.

Przedstawiony żart z komisji jest prawdziwy w połowie. O ile druga część (o bezpieczeństwie) jest faktycznym błędem organizatorów, „męczenie się z dodatkowymi nagłówkami i ich kompilacją” i „narzucenie im mojego stylu nazywania funkcji” jest standardem w każdym projekcie informatycznym, nieważne czy wolnym, czy własnościowym.

Skoordynowane wejście/wyjście (błędnie nazwane przez Jonasza „synchronicznym”) jest jednym z rozwiązań. Jeżeli by przedstawić w formie diagramu komunikację sprawdzarki z programem, szybko zauważymy, że odpowiada to przedstawionemu przez mnie wcześniej modelowi IPC. Jednak dużo szybsze od tekstowego IPC jest binarne IPC, więc dobra biblioteczka miałaby mniejszy narzut czasowy niż konwencjonalne rozwiązanie. Wszystko przez bezpieczny, znany i przyjazny strumień binarny który, podobnie jak tekstowy, jest możliwy do zhackowania.

Okazuje się, że biblioteczki to system używany praktycznie wszędzie poza kontestami, dlaczego więc mamy uczyć uczestników rzeczy niepraktycznych?