Wyjaśnienie abstrakcyjnej interpretacji: od teorii krat do wnioskowania i Astrée

Rozważ dwa programy, które przechodzą każdy napisany przez Ciebie test. Jeden jest poprawny. W drugim występuje błąd dzielenia przez zero, który pojawia się tylko wtedy, gdy określona kombinacja danych wejściowych pojawia się jednocześnie – kombinacja, której Twoje testy nigdy nie generują. Tradycyjne testy nie potrafią wskazać, który jest który. Abstrakcyjna interpretacja potrafi.

Abstrakcyjna interpretacja to matematyczna struktura, która umożliwia narzędziom analizy statycznej wnioskowanie o wszystkich możliwych zachowaniach programu bez jego uruchamiania. To technika stojąca za narzędziem Infer Facebooka, które znajduje błędy wskaźnika zerowego na dużą skalę, za analizatorem Astrée formalnie weryfikującym oprogramowanie sterujące lotem Airbusa oraz za każdym analizatorem statycznym, który deklaruje poprawność – gwarancją, że jeśli program przejdzie analizę, to faktycznie jest wolny od klasy sprawdzanych błędów. Zrozumienie, jak to działa, wyjaśnia, dlaczego niektóre narzędzia wykrywają błędy, a inne je pomijają, i dlaczego te gwarancje wiążą się z określonymi kompromisami.

Czym jest interpretacja abstrakcyjna?

Interpretacja abstrakcyjna to teoria aproksymacji programów, opracowana w 1977 roku przez Patricka Cousota i Radhię Cousot. Główna idea: zamiast obliczać dokładny zbiór wszystkich możliwych stanów programu, który na ogół jest nierozstrzygalny, należy obliczyć bezpieczne nadmierne przybliżenie, wykorzystując uproszczoną dziedzinę matematyczną, którą można łatwo analizować.

Słowo „abstrakcyjny” nie oznacza tu niejasności ani konceptualizmu. Odnosi się do konkretnej operacji matematycznej: przekształcenia zbioru konkretnych wartości w prostszą reprezentację, która zachowuje interesujące Cię właściwości, a jednocześnie eliminuje zbędne szczegóły. Konkretna wartość całkowita, taka jak 42 staje się, w abstrakcji analizy znaków, po prostu „dodatni”. Abstrakcja traci informację (nie znasz już dokładnej wartości), ale zyskuje łatwość obliczeń (znak dowolnej liczby całkowitej może mieć jedną z trzech możliwości: dodatni, ujemny lub zero).

To, co czyni to użytecznym w analizie programów, to gwarancja, jaką się z tym wiąże: jeśli analiza nie wykryje błędu w domenie abstrakcyjnej, błąd nie wystąpi w żadnym konkretnym wykonaniu. Jeśli wykryje potencjalny błąd, błąd ten może, ale nie musi, wystąpić w praktyce, ale żaden rzeczywisty błąd nie może pozostać ukryty. To jest właśnie solidność.

Interpretacja abstrakcyjna kontra analiza AST kontra analiza dynamiczna

Te terminy są często mylone. W wynikach wyszukiwania dla tego artykułu pojawia się fraza „analiza kodu AST”, która jednak opisuje różne rzeczy.

Drzewo składni abstrakcyjnej (AST) to struktura danych reprezentująca strukturę gramatyczną kodu źródłowego. Każdy kompilator i linter tworzy takie drzewo. Stanowi ono podstawę parsowania, narzędzi refaktoryzujących i analizy statycznej opartej na wzorcach. Analiza oparta na AST znajduje wzorce: kod pasujący do reguły (funkcja ze zbyt wieloma parametrami, ciąg SQL utworzony przez konkatenację) jest oznaczany flagą. Nie analizuje wartości ani zachowania w czasie wykonywania.

Abstrakcyjna interpretacja analizuje zachowanie programu w czasie wykonywania bez jego uruchamiania. Wykorzystuje ona kod AST jako dane wejściowe, ale wykracza daleko poza nie: modeluje przepływ wartości przez program, zakresy, jakie mogą przyjmować zmienne, sprawdza, czy wskaźnik może być nullem w określonym miejscu wywołania, czy pętla się kończy. Analiza AST to dopasowywanie wzorców. Abstrakcyjna interpretacja to rozumowanie behawioralne.

Większość linterów (ESLint, Checkstyle, Pylint) opiera się głównie na AST. Większość formalnych narzędzi do weryfikacji (Infer, Astrée, Polyspace) wykorzystuje interpretację abstrakcyjną. Analiza dynamiczna (uruchomienie programu i obserwacja rzeczywistego zachowania) znajduje tylko błędy wywołane przez określone dane wejściowe. Interpretacja abstrakcyjna znajduje błędy we wszystkich możliwych danych wejściowych bez konieczności uruchamiania programu.

Matematyczne zasady analizy statycznej

Zapytanie „jakie są matematyczne zasady stojące za narzędziami do analizy statycznej” pojawia się bezpośrednio w wynikach wyszukiwania. Oto prosta odpowiedź.

Interpretacja abstrakcyjna opiera się na trzech strukturach matematycznych:

Kraty. Krata to częściowo uporządkowany zbiór, w którym każda para elementów ma najmniejszą granicę górną (złącze) i największą granicę dolną (spotkanie). W analizie statycznej krata reprezentuje domenę abstrakcyjną, zbiór możliwych wartości abstrakcyjnych, uporządkowanych według ilości niesionych przez nie informacji. W analizie znaków krata wygląda następująco:

        ⊤ (unknown -- could be anything)
       / \
   pos   neg
       \ /
        0
        |
        ⊥ (unreachable -- no possible value)

Przemieszczanie się w górę siatki oznacza utratę precyzji (mniej wiedzy). Przemieszczanie się w dół oznacza jej zyskanie (więcej wiedzy). Górny element ⊤ oznacza „nie wiemy nic przydatnego”. Dolny element ⊥ oznacza „ten stan jest nieosiągalny”.

Połączenia Galois. Połączenia Galois to formalna relacja między domeną konkretną (rzeczywistymi wartościami programu) a domeną abstrakcyjną (uproszczoną reprezentacją). Składają się one z dwóch funkcji: funkcji abstrakcji α, która odwzorowuje wartości konkretne na ich abstrakcyjną reprezentację, oraz funkcji konkretyzacji γ, która odwzorowuje wartości abstrakcyjne z powrotem na zbiór wartości konkretnych, które reprezentują.

Właściwość krytyczna: dziedzina abstrakcyjna musi być bezpiecznym przybliżeniem. γ(α(S)) ⊇ S Dla każdego konkretnego zbioru S. Abstrakcja może zawierać więcej wartości niż faktycznie występuje, co prowadzi do fałszywych wyników, ale nigdy nie może wykluczać wartości, które faktycznie występują. Wykluczenie rzeczywistych wartości oznaczałoby pominięcie rzeczywistych błędów.

Iteracja stałoprzecinkowa. W przypadku programów z pętlami analiza musi być iterowana, aż do osiągnięcia stanu stabilnego. Dla pętli takiej jak:

c

int x = 0;
while (condition) {
    x = x + 1;
}

W pierwszej iteracji, x is {0}. Po jednym ciele pętli, x może być {0, 1}. Po dwóch, {0, 1, 2}Ten zestaw ciągle rośnie, nigdy nie stabilizuje się sam. Rozwiązaniem jest poszerzanie: operator wymuszający zbieżność poprzez przejście do szerszego przybliżenia (zwykle [0, +∞) (do analizy interwałowej). Następnie analiza wykorzystuje zwężenie aby odzyskać trochę precyzji.

Tego typu obliczenia stałoprzecinkowe zapewniają kompletność abstrakcyjnej interpretacji we wszystkich ścieżkach wykonywania, włączając w to pętle, i sprawiają, że są one bardziej kosztowne obliczeniowo niż proste dopasowywanie wzorców.

Domeny abstrakcyjne: wybór tego, co przybliżać

Domena abstrakcyjna określa, co analiza może, a czego nie może znaleźć. Różne domeny odpowiadają na różne pytania dotyczące zachowania programu.

Domena abstrakcyjna	Co śledzi	Przykładowe zastosowanie	Czego mu brakuje
Analiza znaków	Czy wartości są dodatnie, ujemne czy zerowe	Wykrywanie dzielenia przez zero	Dokładne wartości, warunki przepełnienia
Analiza interwałowa	Górne i dolne granice wartości liczbowych	Przepełnienie bufora, bezpieczeństwo dostępu do tablicy	Zależności między zmiennymi
Domena ośmiokątna	Liniowe zależności między parami zmiennych	Bardziej precyzyjne wykrywanie przepełnienia	Relacje nieliniowe
Analiza wskaźników	Czy wskaźniki mogą być puste lub aliasować się nawzajem	Dereferencja zerowa, użycie po zwolnieniu	Czas życia obiektu, kształt sterty
Analiza skażenia	Czy wartości pochodzą z niepewnych źródeł	Wstrzyknięcie SQL, wykrywanie XSS	Niejawne przepływy przez kontrolę
Domena wielościenna	Dowolne liniowe ograniczenia arytmetyczne	Weryfikacja ograniczeń pętli	Koszty wydajności rosną wykładniczo

Kompromis między domenami zawsze polega na wyborze precyzji i wydajności. Domena interwałowa jest szybka i wychwytuje większość błędów numerycznych. Domena wielościenna jest znacznie bardziej precyzyjna, ale charakteryzuje się wykładniczą złożonością liczby zmiennych. Praktyczne narzędzia do analizy statycznej wybierają domeny, które równoważą kompromis dla ich docelowego zastosowania. Systemy wbudowane o krytycznym znaczeniu dla bezpieczeństwa mogą pozwolić sobie na wolniejszą, bardziej precyzyjną analizę; zintegrowane z CI/CD lintery muszą kończyć działanie w ciągu kilku sekund.

Jak trzy prawdziwe narzędzia wykorzystują abstrakcyjną interpretację

Zamiast opisywać teorię w izolacji, konkretne narzędzia jasno pokazują jej zastosowanie.

Facebook Infer wykorzystuje formę abstrakcyjnej interpretacji zwaną bi-abdukcją do analizy języków Java, C, C++ i Objective-C pod kątem dereferencji wskaźników zerowych, wycieków zasobów i sytuacji wyścigu. Bi-abdukcja automatycznie wykrywa warunki wstępne i końcowe dla funkcji, umożliwiając analizę międzyproceduralną bez konieczności ręcznej specyfikacji. Infer działa w ramach CI w Facebooku, Spotify, Mozilli i dziesiątkach innych dużych organizacji, ponieważ skaluje się do wielomilionowych baz kodu, zachowując jednocześnie niezawodność w zakresie sprawdzanych klas błędów.

Astrée wykorzystuje abstrakcyjną interpretację z numerycznymi domenami abstrakcyjnymi, aby udowodnić brak błędów w czasie wykonywania w programach C. Został on wykorzystany przez Airbusa do formalnej weryfikacji głównego oprogramowania sterowania lotem A380, co dowodzi braku błędów w czasie wykonywania w całym systemie sterowania – gwarancji, której nie mógł zapewnić żaden program testujący. Astrée nie znajduje żadnych wyników fałszywie negatywnych dla sprawdzanych klas błędów, choć może generować wyniki fałszywie pozytywne, które wymagają ręcznej weryfikacji.

Polyspace (MathWorks) stosuje abstrakcyjną interpretację kodu C i C++ w aplikacjach krytycznych dla bezpieczeństwa. Klasyfikuje każdą operację jako „zieloną” (brak błędu, którego można dowieść), „czerwoną” (zdecydowanie błąd) lub „pomarańczową” (potencjalny błąd wymagający weryfikacji). Klasyfikacja „zielona” stanowi formalny dowód: brak wykonania danej operacji nie może spowodować błędu w czasie wykonywania.

Trójkąt solidności-precyzji-wydajności

Narzędzia do interpretacji abstrakcyjnej poruszają się w fundamentalnym trójkącie konkurujących ze sobą właściwości. Żadne narzędzie nie jest w stanie zmaksymalizować wszystkich trzech jednocześnie.

Solidność oznacza brak fałszywych wyników negatywnych: każdy prawdziwy błąd w analizowanej klasie zostaje wykryty. Solidne narzędzia dają gwarancje; narzędzia, które nie są solidne, mogą nie wykryć błędów.

Precyzja oznacza mniej fałszywych wyników: wyniki odpowiadają rzeczywistym problemom, a nie teoretycznym, które nie mogą wystąpić. Wysoka precyzja wymaga bardziej dopracowanych dziedzin abstrakcyjnych i analizy międzyproceduralnej.

Wydajność oznacza, że ​​analiza kończy się w użytecznym czasie. Bardziej precyzyjna analiza jest droższa. Udowodnienie braku błędów w czasie wykonania w bazie kodu liczącej milion wierszy zajmuje godziny; skanowanie linterem zajmuje sekundy.

Różne zastosowania wymagają różnych punktów w tym trójkącie:

• Linting IDE i CI/CD:najpierw wydajność, potem precyzja, opcjonalnie solidność
• Skanowanie bezpieczeństwa:precyzja przede wszystkim (zmniejszenie zmęczenia alertami programisty), solidność ważna dla klas o wysokim stopniu ważności
• Certyfikacja krytyczna dla bezpieczeństwa:najpierw solidność (nie można pominąć prawdziwych błędów), wydajność na drugim miejscu, fałszywe pozytywy są dopuszczalne w procesie ręcznego przeglądu

Interpretacja abstrakcyjna w rozwoju systemów wbudowanych i krytycznych dla bezpieczeństwa

Zapytanie „korzyści z analizy statycznej w rozwoju systemów wbudowanych” wskazuje na jeden z najważniejszych obszarów zastosowań interpretacji abstrakcyjnej. Systemy wbudowane, jednostki sterujące w pojazdach, oprogramowanie sprzętowe urządzeń medycznych, oprogramowanie do sterowania lotami kosmicznymi – wszystkie te obszary mają ograniczenia, które sprawiają, że interpretacja abstrakcyjna jest szczególnie cenna:

Brak wiązki testowej dla wszystkich stanów. Sterownik silnika samochodu reaguje na tysiące kombinacji czujników w czasie rzeczywistym. Skonstruowanie testów dla każdej kombinacji jest niemożliwe. Abstrakcyjna interpretacja obejmuje wszystkie stany jednocześnie.

Wymagania certyfikacyjne. Normy DO-178C (przemysł lotniczy i kosmiczny), ISO 26262 (przemysł motoryzacyjny) i IEC 62443 (kontrola przemysłowa) wymagają wykazania, że ​​oprogramowanie działa poprawnie w każdych warunkach. Formalna weryfikacja z wykorzystaniem interpretacji abstrakcyjnej może spełnić ten wymóg w sposób, w jaki nie potrafią tego zrobić raporty z zakresu pokrycia testów.

Ograniczenia zasobów. Oprogramowanie wbudowane często nie ma alokatora pamięci, obsługi wyjątków ani mechanizmu awaryjnego. Błąd w czasie wykonywania, dereferencja wskaźnika null, przekroczenie zakresu tablicy to poważna awaria systemu. Kosztem przeoczenia tych błędów nie jest zgłoszenie awarii i poprawka. To incydent bezpieczeństwa.

Analizatory Astrée i Polyspace powstały specjalnie w tym celu. Ich konstrukcja charakteryzuje się wysokim wskaźnikiem fałszywie dodatnich wyników i powolną analizą, w zamian za gwarancję, że żaden wynik fałszywie ujemny nie zostanie przepuszczony.

Fałszywie pozytywne wyniki i narastający problem

Najczęstszym zarzutem wobec abstrakcyjnych narzędzi interpretacyjnych są fałszywe alarmy, czyli ostrzeżenia o potencjalnych błędach, które w rzeczywistości nie mogą wystąpić w praktyce. Zrozumienie, dlaczego fałszywe alarmy są nieodłączną cechą, a nie wadą jakości, ułatwia radzenie sobie z nimi.

Wyniki fałszywie dodatnie mają dwa źródła:

Nadmierne przybliżenie w domenie abstrakcyjnej. Jeśli domena interwałowa śledzi x ∈ [0, 100], nie potrafi odróżnić przypadków, w których x w praktyce zawsze jest mniejsze niż 50. Podział przez x może zostać oznaczony jako potencjalnie dzielący przez zero, nawet jeśli logika programu to gwarantuje x > 0. Bardziej precyzyjna domena (śledząca dokładną wartość lub ograniczenie łączące x do innej zmiennej) wyeliminowałoby wyniki fałszywie dodatnie, ale wiązałoby się z większymi kosztami obliczeniowymi.

Poszerzanie. Operator konwergencji, który umożliwia analizę pętli, nieuchronnie traci informacje. Po poszerzeniu x od [0, 5] do [0, +∞), analizator już nie wie, że x pozostaje ograniczony. Jeśli kod sprawdza assert(x < 1000) po pętli tego twierdzenia nie da się już udowodnić, nawet jeśli w praktyce x zawsze utrzymuje się znacznie poniżej 1000.

Praktyczne strategie zarządzania wynikami fałszywie dodatnimi: skonfiguruj analizę tak, aby używała bardziej precyzyjnych domen dla modułów krytycznych (akceptując wolniejszą analizę), eliminuj potwierdzone wyniki fałszywie dodatnie za pomocą ukierunkowanych adnotacji i traktuj pomarańczowe/nieznane wyniki narzędzia jako priorytetową kolejkę przeglądów, a nie potwierdzone błędy.

W jaki sposób SMART TS XL Stosuje analizę statyczną w skali przedsiębiorstwa

SMART TS XL działa w przestrzeni, w której abstrakcyjna teoria interpretacji spotyka się z rzeczywistością przedsiębiorstwa: bazy kodów obejmujące wiele języków, dekady rozwoju i granice organizacyjne, które sprawiają, że formalna weryfikacja dla każdego programu jest niepraktyczna.

Zamiast stosować jedną abstrakcyjną domenę do wszystkich programów, SMART TS XL'S statyczna analiza kodu łączy techniki analizy strukturalnej odpowiednie dla każdego języka w środowisku, COBOL, JCL, Java, Python, RPG, PL/I, SQL i nowoczesnych stosów, generując jednocześnie metryki jakości, dane zależności i ustalenia dotyczące bezpieczeństwa dla całego portfolio.

Funkcja mapowania zależności aplikacji stosuje analizę teorii grafów do grafu wywołań międzyjęzykowych, identyfikując, w jaki sposób programy, zbiory danych i strumienie zadań łączą się ze sobą ponad granicami językowymi – jest to rodzaj analizy całego systemu, której nie są w stanie wykonać narzędzia jednojęzyczne. Jest to rozumowanie strukturalne na poziomie systemu: nie dowodzenie właściwości poszczególnych programów, lecz dowodzenie właściwości ich połączeń.

Funkcja analizy wpływu stosuje analizę osiągalności na grafie zależności: biorąc pod uwagę proponowaną zmianę w jednym węźle, oblicza zbiór wszystkich węzłów osiągalnych z tego węzła. Jest to pytanie analizy statycznej „co zostanie zmienione?”, na które odpowiedź opiera się na strukturze kodu, a nie na obserwacji w czasie wykonywania lub szacunkach człowieka.

Dla zespołów prowadzących modernizacja dziedziczna programy SMART TS XLAnaliza strukturalna firmy niweluje lukę między formalnymi narzędziami interpretacji abstrakcyjnej (które są specyficzne dla danego języka i wymagają specjalistycznej wiedzy w celu konfiguracji) a praktyczną potrzebą zrozumienia, co tak naprawdę robią duże, nieudokumentowane, wielojęzyczne systemy starszej generacji, co jest warunkiem wstępnym dla każdego programu modernizacji, który nie chce odkrywać swoich najdroższych niespodzianek w trakcie realizacji.

Najczęściej zadawane pytania

Jaka jest różnica między interpretacją abstrakcyjną a sprawdzaniem modeli? Obie są formalnymi metodami weryfikacji programów. Interpretacja abstrakcyjna przeszacowuje zbiór możliwych stanów (poprawna, ale potencjalnie nieprecyzyjna). Sprawdzanie modeli wyczerpująco eksploruje przestrzeń stanów (kompletną, ale wykonalną tylko dla skończonych, ograniczonych systemów). Interpretacja abstrakcyjna skaluje się do dużych programów. Sprawdzanie modeli skaluje się do złożonych właściwości w mniejszych modelach. Są one komplementarne, a nie konkurencyjne.

Czy abstrakcyjna interpretacja dotyczy tylko oprogramowania krytycznego dla bezpieczeństwa? Nie, choć tam przynosi najwyraźniejszą wartość. Wnioskowanie działa w standardowych procesach CI/CD w dużych firmach technologicznych, wykrywając dereferencje wskaźników zerowych i wycieki zasobów w codziennym kodzie Java i C. Stopień zastosowanej rygorystyczności to kwestia wyboru: pełna solidność z formalnymi gwarancjami z jednej strony, lekka analiza heurystyczna z drugiej, a większość praktycznych narzędzi znajduje się gdzieś pomiędzy.

Czy abstrakcyjna interpretacja może analizować COBOL? Abstrakcyjna interpretacja jest teorią niezależną od języka. Zastosowanie jej w COBOL-u wymaga implementacji abstrakcyjnych funkcji przejścia dla operacji COBOL-a, arytmetyki pól PIC, klauzul REDEFINES, nazw warunków poziomu 88 itd. Uniwersalne narzędzia do abstrakcyjnej interpretacji (Infer, Astrée) nie obsługują COBOL-a. Platformy analizy strukturalnej dla przedsiębiorstw, które natywnie rozumieją COBOL, stosują powiązane techniki analizy statycznej w celu wykrywania problemów jakościowych, martwego kodu i problemów architektonicznych w bazach kodu COBOL.