Anropsdiagram

En samtalsgraf genererad för ett enkelt datorprogram i Python.

En samtalsgraf (även känd som en samtalsmultigraf ) är en kontrollflödesgraf , som representerar anropsförhållanden mellan subrutiner i ett datorprogram . Varje nod representerar en procedur och varje kant (f, g) indikerar att procedur f anropar procedur g . Således indikerar en cykel i grafen rekursiva proceduranrop.

Grundläggande koncept

Samtalsdiagram kan vara dynamiska eller statiska. En dynamisk anropsgraf är en registrering av en exekvering av programmet, till exempel som utmatning av en profilerare. Således kan en dynamisk anropsgraf vara exakt, men beskriver bara en körning av programmet. En statisk samtalsgraf är en samtalsgraf avsedd att representera alla möjliga körningar av programmet. Den exakta statiska samtalsgrafen är ett oavgörligt problem , så statiska samtalsdiagramalgoritmer är i allmänhet överapproximationer. Det vill säga att varje samtalsrelation som uppstår representeras i grafen, och möjligen även vissa samtalsrelationer som aldrig skulle uppstå i faktiska körningar av programmet.

Anropsdiagram kan definieras för att representera olika grader av precision. En mer exakt samtalsgraf approximerar mer exakt beteendet hos det verkliga programmet, till priset av att det tar längre tid att beräkna och mer minne att lagra. Den mest exakta samtalsgrafen är helt kontextkänslig , vilket innebär att för varje procedur innehåller grafen en separat nod för varje samtalsstack som proceduren kan aktiveras med. En helt kontextkänslig samtalsgraf kallas ett anropskontextträd. Detta kan enkelt beräknas dynamiskt, även om det kan ta upp en stor mängd minne. Anropskontextträd beräknas vanligtvis inte statiskt, eftersom det skulle ta för lång tid för ett stort program. Den minst exakta samtalsgrafen är kontextokänslig , vilket innebär att det bara finns en nod för varje procedur.

Med språk som har dynamisk sändning (t.ex. Java eller C++ ), förstklassiga funktioner (t.ex. Python eller Racket ) eller funktionspekare (t.ex. C ), kräver beräkning av en statisk anropsgraf exakt aliasanalysresultat . Omvänt kräver beräkning av exakt aliasing en samtalsgraf. Många statiska analyssystem löser den skenbara oändliga regressen genom att beräkna båda samtidigt.

Användningsområden

Samtalsdiagram kan användas på olika sätt. En enkel tillämpning av samtalsdiagram är att hitta procedurer som aldrig anropas. Anropsdiagram kan fungera som dokumentation för människor att förstå program . Anropsdiagram kan också användas för att upptäcka anomalier i programexekvering eller kodinjektionsattacker.

programvara

Gratis programvara för generatorer för samtalsgrafer

Körtidsanropsdiagram (de flesta av de listade verktygen är profilerare med samtalsdiagramfunktioner)

gprof : ingår i BSD eller en del av GNU Binary Utilities
callgrind : en del av Valgrind
KCachegrind : kraftfullt verktyg för att generera och analysera samtalsdiagram baserat på data som genereras av callgrind
Mac OS X Activity Monitor: Apple GUI-processmonitor Activity Monitor har en inbyggd anropsgrafgenerator som kan ta prov på processer och returnera en anropsgraf. Denna funktion är endast tillgänglig i Mac OS X Leopard
OpenPAT : inkluderar verktyget control_flow som automatiskt skapar en Graphviz call-graph-bild från körtidsmätningar.
pprof , öppen källkodsverktyg för visualisering och analys av profildata, att användas tillsammans med gperftools .
CodeAnalyst från AMD (släppt under GPL)
makeppgraph är en beroendegrafgenerator (på modulnivå) för builds utförda med makepp .
Intel(R) Single Event API (gratis, öppen källkod)

Statisk för att få samtalsdiagram utan att köra applikation

C/C++

Sourcetrail skapar en statisk samtalsgraf, som kan utforskas dynamiskt av användaren. Stöder även Python och Java
doxygen : Använder Graphviz för att generera statiska anrops-/arvsdiagram
cflow : GNU cflow kan generera den direkta och inverterade anropsgrafen för ett C-program
egypt : ett litet Perl -skript som använder gcc och Graphviz för att generera den statiska anropsgrafen för ett C-program.
Analizo : beräknar källkodsmått, genererar beroendegrafer.
CCTree : Native Vim -plugin som kan visa statiska samtalsdiagram genom att läsa en cscope -databas. Fungerar för C-program.
codeviz : en statisk anropsgrafgenerator (programmet körs inte ). Implementerad som en patch till gcc ; fungerar för C- och C++-program.
calltree.sh : Bash-skalfunktioner som limmar ihop cscope, graphviz och ett urval av punktrenderingsverktyg för att visa "anropare" och "callee"-relationer ovanför, under och/eller mellan C-funktionerna du anger.
tceetree : som calltree.sh kopplar det ihop Cscope och Graphviz , men det är en körbar snarare än ett bash-skript.

Go

go-callvis : en interaktiv anropsgrafgenerator för Go-program vars utdata kan ritas med Graphviz

Multi-language

callGraph : öppen källkodsgenerator för anropsdiagram för awk, bash, basic, dart, fortran, go, lua, javascript, julia, kotlin, matlab, perl, pascal, php, python, R, raku, ruby, rust, scala, swift, tcl och typscript.

.NET

NDepend :är ett statiskt analysverktyg för .NET-kod. Det här verktyget stöder ett stort antal kodmått, möjliggör visualisering av beroenden med hjälp av riktade grafer och beroendematris.

PHP, Perl och Python

Devel::NYTProf : en Perl prestandaanalysator och samtalsdiagramgenerator
phpCallGraph : en anropsgrafgenerator för PHP-program som använder Graphviz . Det är skrivet i PHP och kräver minst PHP 5.2.
pycallgraph : en anropsgrafgenerator för Python-program som använder Graphviz .
pyan : en statisk anropsgrafgenerator för Python-program som använder Graphviz .
gprof2dot : En anropsgrafgenerator skriven i Python som konverterar profileringsdata för många språk/körtider till en Graphviz -anropsgraf.
code2flow : En anropsgrafgenerator för Python- och Javascript-program som använder Graphviz
rcviz : Python-modul för att rendera runtime-genererade anropsdiagram med Graphviz . Varje nod representerar ett anrop av en funktion med parametrarna som skickas till den och returvärdet.

XQuery

XQuery Call Graphs från XQuery Wikibook : En anropsdiagramgenerator för en XQuery-funktionsmodul som använder Graphviz

Proprietära samtalsgrafgeneratorer

LDRA Testbed: Statiska och dynamiska analysmotorer för både värd och inbäddad programvara, med en myriad av rapporter inklusive anropsdiagram.
Project Analyzer: Statisk kodanalysator och anropsgrafgenerator för Visual Basic-kod
Visual Expert: Statisk kodanalysator och anropsgrafgenerator för Oracle PL/SQL , SQLServer Transact-SQL , C# och PowerBuilder - kod
Intel VTune Performance Analyzer: Instrumentprofiler för att visa anropsdiagram och exekveringsstatistik
DMS Software Reengineering Toolkit: Anpassningsbart programanalysverktyg med statisk helprograms global anropsgrafextraktion för C, Java och COBOL

Andra, relaterade verktyg

Graphviz: Förvandlar en textrepresentation av valfri graf (inklusive en samtalsgraf) till en bild.
tsort: Kommandoradsverktyg som utför en topologisk sortering.

Exempelgraf

Ett exempel på samtalsdiagram genererat från gprof som analyserar sig själv:

index kallas namn |index kallas namn 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 är_numrerad [9] ---------------------------- | 1508/1508 är_upptagen [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 är_numrerad [9] |[18] 24 parse_id [18] ---------------------------- | 24/24 parse_spec [19] 1508/1508 propagate_flags [52] |---------------------------- [10] 1508 ärv_flaggor [10] | 24/24 parse_id [18] ---------------------------- |[19] 24 parse_spec [19] 1508/1508 cg_dfn [15] | 24/1537 sym_init [6] [11] 1508 är_upptagen [11] |-------------------------------------- ---------- | 24/24 main [1210] 1508/1508 cg_dfn [15] |[20] 24 sym_id_add [20] [12] 1508 post_visit [12] |

Se även