Wykres połączeń

Wykres wywołań wygenerowany dla prostego programu komputerowego w Pythonie.

Wykres wywołań (znany również jako multigraf wywołań ) to wykres przepływu sterowania , który przedstawia relacje wywołań między podprogramami w programie komputerowym . Każdy węzeł reprezentuje procedurę, a każda krawędź (f, g) wskazuje, że procedura f wywołuje procedurę g . Zatem cykl na wykresie wskazuje na rekurencyjne wywołania procedur.

Podstawowe koncepcje

Wykresy połączeń mogą być dynamiczne lub statyczne. Dynamiczny wykres wywołań jest zapisem wykonania programu, na przykład jako wyjście z profilera. Zatem dynamiczny wykres wywołań może być dokładny, ale opisuje tylko jedno uruchomienie programu. Statyczny wykres wywołań to wykres wywołań, który ma reprezentować każde możliwe uruchomienie programu. Dokładny statyczny wykres wywołań jest problemem nierozstrzygalnym , więc algorytmy statycznego wykresu wywołań są generalnie zawyżone. Oznacza to, że każda występująca relacja wywołania jest reprezentowana na wykresie, a być może także niektóre relacje wywołania, które nigdy nie wystąpiłyby w rzeczywistych uruchomieniach programu.

Wykresy wywołań można zdefiniować tak, aby reprezentowały różne stopnie precyzji. Bardziej precyzyjny wykres wywołań dokładniej przybliża zachowanie rzeczywistego programu, kosztem dłuższych obliczeń i większej ilości pamięci do przechowywania. Najbardziej precyzyjny wykres wywołań jest w pełni kontekstowy , co oznacza, że ​​dla każdej procedury wykres zawiera osobny węzeł dla każdego stosu wywołań , za pomocą którego można aktywować procedurę. W pełni kontekstowy wykres wywołań nazywany jest drzewem kontekstu wywołania. Można to łatwo obliczyć dynamicznie, chociaż może to zająć dużą ilość pamięci. Drzewa kontekstu wywołania zwykle nie są obliczane statycznie, ponieważ w przypadku dużego programu zajęłoby to zbyt dużo czasu. Najmniej precyzyjny wykres wywołań jest niewrażliwy na kontekst , co oznacza, że ​​dla każdej procedury istnieje tylko jeden węzeł.

W przypadku języków obsługujących dynamiczną wysyłkę (np. Java lub C++ ), pierwszorzędnych funkcji (np. Python lub Racket ) lub wskaźników funkcji (np. C ), obliczenie statycznego wykresu wywołań wymaga precyzyjnych wyników analizy aliasów . I odwrotnie, obliczenie precyzyjnego aliasingu wymaga wykresu wywołań. Wiele systemów analizy statycznej rozwiązuje pozorny nieskończony regres, obliczając oba jednocześnie.

zwyczaje

Wykresy połączeń mogą być używane na różne sposoby. Jednym z prostych zastosowań wykresów wywołań jest znajdowanie procedur, które nigdy nie są wywoływane. Wykresy wywołań mogą służyć jako dokumentacja umożliwiająca ludziom zrozumienie programów . Wykresy wywołań mogą być również wykorzystywane do wykrywania anomalii w wykonywaniu programów lub ataków polegających na wstrzykiwaniu kodu.

Oprogramowanie

Darmowe generatory wykresów wywołań

Wykres połączeń w czasie wykonywania (większość wymienionych narzędzi to profilery z funkcją wykresu połączeń)

  • gprof : zawarty w BSD lub część GNU Binary Utilities
  • callgrind: część Valgrind
  • KCachegrind : potężne narzędzie do generowania i analizowania wykresów połączeń na podstawie danych generowanych przez callgrind
  • Monitor aktywności w systemie Mac OS X: monitor procesów z graficznym interfejsem użytkownika firmy Apple Monitor aktywności ma wbudowany generator wykresów połączeń, który może próbkować procesy i zwracać wykres połączeń. Ta funkcja jest dostępna tylko w systemie Mac OS X Leopard
  • OpenPAT: zawiera narzędzie control_flow , które automatycznie tworzy wykres wywoławczy Graphviz na podstawie pomiarów w czasie wykonywania .
  • pprof , narzędzie typu open source do wizualizacji i analizy danych profilu, do użytku w połączeniu z gperftools .
  • CodeAnalyst firmy AMD (wydany na licencji GPL)
  • makeppgraph to generator wykresów zależności (na poziomie modułu) dla kompilacji wykonywanych za pomocą makepp .
  • Intel(R) Single Event API (bezpłatny, open-source)

Statyczny do uzyskiwania wykresów połączeń bez uruchamiania aplikacji

C/C++
  • Sourcetrail tworzy statyczny wykres połączeń, który użytkownik może dynamicznie eksplorować. Obsługuje również Pythona i Javę
  • doxygen : Używa Graphviz do generowania statycznych diagramów połączeń/dziedziczenia
  • cflow : GNU cflow jest w stanie wygenerować bezpośredni i odwrócony wykres wywołań programu C
  • egypt : mały skrypt Perla , który używa gcc i Graphviz do generowania statycznego wykresu wywołań programu C.
  • Analizo : oblicza metryki kodu źródłowego, generuje wykresy zależności.
  • CCTree : Natywna wtyczka Vima , która może wyświetlać statyczne wykresy wywołań, czytając bazę danych cscope . Działa dla programów C.
  • codeviz : statyczny generator wykresów wywołań (program nie jest uruchamiany). Zaimplementowane jako łatka do gcc ; działa dla programów C i C++.
  • calltree.sh : Funkcje powłoki Bash, które łączą cscope, graphviz i próbkowanie narzędzi do renderowania kropek, aby wyświetlić relacje „rozmówca” i „wywoływany” powyżej, poniżej i/lub między określonymi funkcjami C.
  • tceetree : podobnie jak calltree.sh, łączy Cscope i Graphviz , ale jest raczej plikiem wykonywalnym niż skryptem bash.
Go
  • go-callvis : interaktywny generator wykresów połączeń dla programów Go, których dane wyjściowe można narysować za pomocą Graphviz
Wielojęzyczny
  • callGraph : generator wykresów wywołań typu open source dla awk, bash, basic, dart, fortran, go, lua, javascript, julia, kotlin, matlab, perl, pascal, php, python, R, raku, ruby, rust, scala, Swift, tcl i maszynopis.
.NET
  • NDepend : to narzędzie do analizy statycznej kodu .NET. To narzędzie obsługuje dużą liczbę metryk kodu, pozwala na wizualizację zależności za pomocą grafów skierowanych i macierzy zależności.
PHP, Perl i Python
  • Devel::NYTPraf : analizator wydajności Perla i generator wykresów połączeń
  • phpCallGraph : generator wykresów wywołań dla programów PHP korzystających z Graphviz . Jest napisany w PHP i wymaga co najmniej PHP 5.2.
  • pycallgraph : generator wykresów wywołań dla programów w Pythonie, który używa Graphviz .
  • pyan : statyczny generator wykresów wywołań dla programów w Pythonie, który używa Graphviz .
  • gprof2dot : Generator wykresów wywołań napisany w Pythonie, który konwertuje dane profilowania dla wielu języków/środowisk wykonawczych na wykres wywołań Graphviz .
  • code2flow : Generator wykresów wywołań dla programów w Pythonie i JavaScript, który używa Graphviz
  • rcviz : moduł Pythona do renderowania wykresów wywołań generowanych w czasie wykonywania za pomocą Graphviz . Każdy węzeł reprezentuje wywołanie funkcji z przekazanymi parametrami i wartością zwracaną.
XQuery

Własne generatory wykresów wywołań

LDRA Testbed
Silniki analizy statycznej i dynamicznej zarówno dla oprogramowania hosta, jak i oprogramowania wbudowanego, z mnóstwem raportów, w tym wykresów wywołań.
Project Analyzer
Statyczny analizator kodu i generator wykresów wywołań dla kodu Visual Basic
Visual Expert
Statyczny analizator kodu i generator wykresów wywołań dla Oracle PL/SQL , SQLServer Kod Transact-SQL , C# i PowerBuilder
Intel VTune Performance Analyzer
Narzędzie do profilowania oprzyrządowania do wyświetlania wykresów wywołań i statystyk wykonania
DMS Software Reengineering Toolkit
Konfigurowalne narzędzie do analizy programów ze statyczną globalną ekstrakcją grafów wywołań dla całego programu dla C, Java i COBOL

Inne, powiązane narzędzia

Graphviz
Zamienia tekstową reprezentację dowolnego wykresu (w tym wykresu połączeń) na obraz.
tsort
Narzędzie wiersza poleceń, które wykonuje sortowanie topologiczne.

Przykładowy wykres

Przykładowy wykres wywołań wygenerowany z analizy gprof : 

indeks o nazwie nazwa |indeks o nazwie nazwa 72384/72384 sym_id_parse [54] | 1508/1508 cg_dfn [15] [3] 72384 mecz [3] |[13] 1508 pre_visit [13] ---------------------- |--- ------------------- 4/9052 cg_tally [32] | 1508/1508 cg_assemble [38] 3016/9052 hist_print [49] |[14] 1508 propagate_time [14] 6032/9052 propagate_flags [52] |------------------- --- [4] 9052 sym_lookup [4] | 2 cg_dfn [15] ------------------------------------- | 1507/1507 cg_assemble [38] 5766/5766 core_create_function_syms [41]|[15] 1507+2 cg_dfn [15] [5] 5766 core_sym_class [5] | 1509/1509 is_numbered [9] ------------------------------------- | 1508/1508 is_busy [11] 24/1537 parse_spec [19] | 1508/1508 pre_visit [13] 1513/1537 core_create_function_syms [41]| 1508/1508 post_visit [12] [6] 1537 sym_init [6] | 2 cg_dfn [15] ---------------------- |---------------------- 1511/1511 core_create_function_syms [41]| 1505/1505 hist_print [49] [7] 1511 get_src_info [7] |[16] 1505 print_line [16] ---------------------- | 2/9 print_name_only [25] 2/1510 arc_add [31] |------------------------------------- 1508/1510 cg_assemble [38] | 1430/1430 core_create_function_syms [41] [8] 1510 arc_lookup [8] |[17] 1430 source_file_lookup_path [17] ---------------------- |--- ------------------- 1509/1509 cg_dfn [15] | 24/24 sym_id_parse [54] [9] 1509 is_numbered [9] |[18] 24 parse_id [18] ---------------------- | 24/24 parse_spec [19] 1508/1508 propagate_flags [52] |------------------------------------- [10] 1508 dziedziczenie_flag [10] | 24/24 parse_id [18] ------------------------------------- |[19] 24 parse_spec [19] 1508/1508 cg_dfn [15] | 24/1537 sym_init [6] [11] 1508 is_busy [11] |------------------------------------ ------------ ---------- | 24/24 main [1210] 1508/1508 cg_dfn [15] |[20] 24 sym_id_add [20] [12] 1508 post_visit [12] |

Zobacz też

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Call_graph&oldid=1135934310 ”