Analiza kształtu (analiza programu)

W analizie programu analiza kształtu jest techniką statycznej analizy kodu , która odkrywa i weryfikuje właściwości połączonych , dynamicznie alokowanych struktur danych w (zwykle imperatywnych ) programach komputerowych. Zwykle jest używany w czasie kompilacji, aby znaleźć błędy oprogramowania lub zweryfikować właściwości poprawności programów na wysokim poziomie. W Java można go użyć do zapewnienia, że ​​metoda sortowania poprawnie posortuje listę. W przypadku programów C może szukać miejsc, w których blok pamięci nie jest prawidłowo zwalniany.

Aplikacje

Analiza kształtu została zastosowana do różnych problemów:

• Bezpieczeństwo pamięci: znajdowanie wycieków pamięci , dereferencje zwisających wskaźników i odkrywanie przypadków, w których blok pamięci jest zwalniany więcej niż raz.
• Znajdowanie błędów poza zakresem tablicy
• Sprawdzanie właściwości stanu typu (na przykład upewnianie się, że plik jest open() przed read () )
• Zapewnienie, że metoda odwracania połączonej listy nie wprowadza cykli do listy
• Sprawdzanie, czy metoda sortowania zwraca wynik w posortowanej kolejności

Przykład

Analiza kształtu jest formą analizy wskaźnikowej , chociaż jest bardziej precyzyjna niż typowa analiza wskaźnikowa. Analiza wskaźnika próbuje określić zestaw obiektów, na które może wskazywać wskaźnik (nazywany zbiorem punktów do wskaźnika). Niestety, te analizy są z konieczności przybliżone (ponieważ doskonale precyzyjna analiza statyczna mogłaby rozwiązać problem zatrzymania ). Analiza kształtu może określić mniejsze (bardziej precyzyjne) zestawy punktów do.

Rozważ następujący prosty program C++.

 
    0     
        

 
    0     Pozycja  *  pozycje  [  10  ];  for  (  int  i  =  ;  i  <  10  ;  ++  i  )  {  pozycje  [  i  ]  =  nowa  pozycja  (...);  // wiersz [1]  }  element_procesu  (  elementy  );  // wiersz [2]  for  (  int  i  =  ;  i  <  10  ;  ++  i  
      
 )  {  usuń  elementy  [  i  ];  // linia [3]  } 

Ten program tworzy tablicę obiektów, przetwarza je w dowolny sposób, a następnie usuwa. Zakładając, że process_items jest wolna od błędów, jest jasne, że program jest bezpieczny: nigdy nie odwołuje się do zwolnionej pamięci i usuwa wszystkie skonstruowane przez siebie obiekty.

Niestety, większość analiz wskaźnikowych ma trudności z precyzyjną analizą tego programu. Aby określić punkty do zbiorów, analiza wskaźników musi być w stanie nazwać obiekty programu. Ogólnie rzecz biorąc, programy mogą przydzielać nieograniczoną liczbę obiektów; ale aby zakończyć, analiza wskaźnikowa może używać tylko skończonego zestawu nazw. Typowym przybliżeniem jest nadanie wszystkim obiektom alokowanym w danej linii programu tej samej nazwy. W powyższym przykładzie wszystkie obiekty zbudowane w wierszu [1] miałyby taką samą nazwę. Dlatego po usunięciu instrukcja jest analizowana po raz pierwszy, analiza stwierdza, że ​​usuwany jest jeden z obiektów o nazwie [1]. Za drugim razem, gdy instrukcja jest analizowana (ponieważ jest w pętli), analiza ostrzega o możliwym błędzie: ponieważ nie jest w stanie rozróżnić obiektów w tablicy, może się zdarzyć, że drugie usunięcie usuwa ten sam obiekt co pierwszy usuń . To ostrzeżenie jest fałszywe, a celem analizy kształtu jest unikanie takich ostrzeżeń.

Podsumowanie i materializacja

Analiza kształtu rozwiązuje problemy analizy wskaźnikowej dzięki zastosowaniu bardziej elastycznego systemu nazewnictwa obiektów. Zamiast nadawać obiektowi tę samą nazwę w całym programie, obiekty mogą zmieniać nazwy w zależności od działań programu. Czasami kilka odrębnych obiektów o różnych nazwach może zostać podsumowanych lub połączonych, tak aby miały tę samą nazwę. Następnie, gdy podsumowany obiekt ma być użyty przez program, może zostać zmaterializowany — oznacza to, że podsumowany obiekt jest podzielony na dwa obiekty o różnych nazwach, z których jeden reprezentuje pojedynczy obiekt, a drugi pozostałe obiekty podsumowania. Podstawowa heurystyka analizy kształtu polega na tym, że obiekty używane przez program są reprezentowane za pomocą unikalnych zmaterializowanych obiektów, podczas gdy obiekty nieużywane są sumowane.

Tablica obiektów w powyższym przykładzie jest podsumowana na różne sposoby w wierszach [1], [2] i [3]. W linii [1] tablica została zbudowana tylko częściowo. Elementy tablicy 0..i-1 zawierają skonstruowane obiekty. Element tablicy i ma zostać skonstruowany, a następujące elementy są niezainicjowane. Analiza kształtu może przybliżyć tę sytuację za pomocą podsumowania dla pierwszego zestawu elementów, zmaterializowanej lokalizacji pamięci dla elementu i oraz podsumowania dla pozostałych niezainicjowanych lokalizacji, w następujący sposób:

0 .. i-1	I	i+1 .. 9
wskaźnik do skonstruowanego obiektu (podsumowanie)	niezainicjowane	niezainicjowane (podsumowanie)

Po zakończeniu pętli, w linii [2], nie ma potrzeby utrzymywania czegokolwiek w stanie materializacji. Analiza kształtu określa w tym momencie, że wszystkie elementy tablicy zostały zainicjowane:

0 .. 9

wskaźnik do skonstruowanego obiektu (podsumowanie)

Jednak w linii [3] element tablicy i jest ponownie używany. Dlatego analiza dzieli tablicę na trzy segmenty, jak w wierszu [1]. Tym razem jednak pierwszy segment przed i został usunięty, a pozostałe elementy są nadal ważne (zakładając, że instrukcja delete nie została jeszcze wykonana).

0 .. i-1	I	i+1 .. 9
za darmo (podsumowanie)	wskaźnik do skonstruowanego obiektu	wskaźnik do skonstruowanego obiektu (podsumowanie)

Zauważ, że w tym przypadku analiza rozpoznaje, że wskaźnik w indeksie i nie został jeszcze usunięty. Dlatego nie ostrzega przed podwójnym usunięciem.

Zobacz też

• Analiza aliasów
• Analiza ucieczki

Bibliografia

•    Neila D. Jonesa; Stevena S. Muchnicka (1982). „Elastyczne podejście do międzyproceduralnej analizy przepływu danych i programów z rekurencyjnymi strukturami danych”. POPL '82 Obrady 9. Sympozjum ACM SIGPLAN-SIGACT na temat zasad języków programowania . ACM: 66–74. doi : 10.1145/582153.582161 . ISBN 0897910656 . S2CID 13266723 .

• Mooly Sagiv ; Thomas Przedstawiciele ; Reinhard Wilhelm (maj 2002).    „Parametryczna analiza kształtu za pomocą logiki 3-wartościowej” (PDF) . Transakcje ACM dotyczące języków i systemów programowania . ACM. 24 (3): 217–298. CiteSeerX 10.1.1.147.2132 . doi : 10.1145/292540.292552 . S2CID 101653 .

• Wilhelm, Reinhard; Sagiv, Mooly; Przedstawiciele, Thomas (2007). „Rozdział 12: Analiza kształtu i zastosowania”. W Srikant, YN; Shankar, Priti (red.). Podręcznik projektowania kompilatora: optymalizacje i generowanie kodu maszynowego, wydanie drugie   . Prasa CRC. s. 12–1–12–44. ISBN 978-1-4200-4382-2 .