Wykres połączeń - Call graph
Wykres połączenia (znany również jako multigraf połączeń ) stanowi wykres kontrolny przepływu , co oznacza wywołanie relacji między podprogramów w programie komputerowym . Każdy węzeł reprezentuje procedurę, a każda krawędź (f, g) wskazuje, że procedura f wywołuje procedurę g . Tak więc cykl na wykresie wskazuje na rekurencyjne wywołania procedur.
Podstawowe koncepcje
Wykresy połączeń mogą być dynamiczne lub statyczne. Dynamiczny wykres wywołań to zapis wykonania programu, na przykład jako dane wyjściowe przez profilera. Tak więc dynamiczny wykres wywołań może być dokładny, ale opisuje tylko jedno uruchomienie programu. Statyczny wykres wywołań to wykres wywołań przeznaczony do reprezentowania każdego możliwego uruchomienia programu. Dokładny statyczny wykres połączeń jest nierozstrzygalnym problemem , więc algorytmy statycznego wykresu połączeń są na ogół przeszacowaniami. Oznacza to, że każda relacja wywołania, która występuje, 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 połączeń można zdefiniować tak, aby reprezentowały różne stopnie dokładności. Bardziej precyzyjny wykres wywołań dokładniej przybliża zachowanie rzeczywistego programu, kosztem dłuższego czasu obliczeń i większej ilości pamięci do przechowywania. Najbardziej precyzyjny graf wywołań jest w pełni wrażliwy na kontekst , co oznacza, że dla każdej procedury graf zawiera oddzielny węzeł dla każdego stosu wywołań , za pomocą którego można aktywować procedurę. W pełni kontekstowy wykres wywołań jest nazywany drzewem kontekstowym wywołań . Można to łatwo obliczyć dynamicznie, chociaż może to zająć dużo pamięci. Wywoływanie drzew kontekstowych zwykle nie jest 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, które obsługują dynamiczną wysyłkę , takich jak Java i C++ , obliczenie statycznego wykresu wywołań wymaga dokładnie wyników analizy aliasów . I odwrotnie, obliczanie precyzyjnego aliasowania wymaga wykresu połączeń. Wiele systemów analizy statycznej rozwiązuje pozorny nieskończony regres, obliczając oba jednocześnie.
Zastosowania
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 połączeń mogą służyć jako dokumentacja umożliwiająca ludziom zrozumienie programów . Mogą również służyć jako podstawa do dalszych analiz, takich jak analiza śledząca przepływ wartości między procedurami lub przewidywanie wpływu zmian . Wykresy wywołań mogą być również wykorzystywane do wykrywania anomalii w wykonywaniu programu lub ataków polegających na wstrzykiwaniu kodu.
Oprogramowanie
Darmowe generatory wykresów połączeń
Wykres połączeń w czasie wykonywania (większość wymienionych narzędzi to profilery z funkcją wykresu połączeń)
- gprof : zawarty w BSD lub jako 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 systemu Mac OS X: Monitor procesów Apple GUI 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
control_flownarzędzie, które automatycznie tworzy wykres wywoławczy Graphviz z 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 od AMD (wydany na licencji GPL)
- makeppgraph to generator grafó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 może być dynamicznie eksplorowany przez użytkownika. Obsługuje również Python i Java
- doxygen : używa Graphviz do generowania statycznych diagramów wywołań/dziedziczenia
- cflow : GNU cflow jest w stanie wygenerować bezpośredni i odwrócony wykres wywołań programu w języku C
- egipt : mały skrypt Perla, który używa gcc i Graphviz do generowania statycznego wykresu wywołań programu w 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 połączeń, czytając bazę danych cscope . Działa dla programów w C.
- codeviz : generator statycznego wykresu wywołań (program nie jest uruchamiany). Zaimplementowany jako łatka do gcc ; działa dla programów C i C++.
- calltree.sh : funkcje powłoki Bash, które łączą ze sobą cscope, graphviz i próbkę narzędzi do renderowania kropek, aby wyświetlić relacje „rozmówcy” i „wywołany” powyżej, poniżej i/lub między określonymi funkcjami C.
- tceetree : podobnie jak calltree.sh łączy Cscope i Graphviz , ale jest to plik wykonywalny, a nie skrypt basha.
- Udać się
- go-callvis : interaktywny generator wykresów połączeń dla programów Go, którego dane wyjściowe można narysować za pomocą Graphviz
- Wielojęzyczny
- callGraph : generator wykresów połączeń 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.
- .INTERNET
- NDepend : jest narzędziem do statycznej analizy kodu .NET. Narzędzie to 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::NYTProf : analizator wydajności Perla i generator wykresów połączeń
- phpCallGraph : generator wykresów wywołań dla programów PHP, który używa Graphviz . Jest napisany w PHP i wymaga co najmniej PHP 5.2.
- pycallgraph : generator wykresów wywołań dla programów Pythona, który używa Graphviz .
- pyan : generator statycznego wykresu wywołań dla programów Pythona, który używa Graphviz .
- gprof2dot : Generator wykresów połączeń napisany w Pythonie, który konwertuje dane profilowania dla wielu języków/środowisk wykonawczych na wykres połączeń Graphviz .
- code2flow : Generator wykresów wywołań dla programów Python 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 do niej parametrami i wartością zwracaną.
- XZapytanie
- Wykresy wywołań XQuery z XQuery Wikibook : Generator wykresów wywołań dla modułu funkcyjnego XQuery, który używa Graphviz
Autorskie generatory wykresów połączeń
- Stanowisko testowe LDRA
- Silniki analizy statycznej i dynamicznej zarówno dla oprogramowania hosta, jak i oprogramowania wbudowanego, z mnóstwem raportów, w tym wykresami połączeń.
- Analizator projektów
- Analizator kodu statycznego i generator wykresów wywołań dla kodu Visual Basic
- Ekspert wizualny
- Analizator kodu statycznego i generator wykresów wywołań dla Oracle PL/SQL , SQLServer Transact-SQL , C# i kodu PowerBuilder
- Analizator wydajności Intel VTune
- Profiler oprzyrządowania do wyświetlania wykresu połączeń i statystyk wykonania
- Zestaw narzędzi do przeprojektowania oprogramowania DMS
- Konfigurowalne narzędzie do analizy programów ze statyczną ekstrakcją globalnego wykresu połączeń dla całego programu dla C, Java i COBOL
- Graphviz
- Zamienia tekstową reprezentację dowolnego wykresu (w tym wykresu połączeń) na obraz.
- Tsort
- Narzędzie wiersza polecenia, które wykonuje sortowanie topologiczne.
Przykładowy wykres
Przykładowy wykres wywołań wygenerowany na podstawie analizy samego programu gprof :
index called name |index called name
72384/72384 sym_id_parse [54] | 1508/1508 cg_dfn [15]
[3] 72384 match [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 inherit_flags [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] |
