Call graph

Call graph

A call graph (also known as a call multigraph) is a directed graph that represents calling relationships between subroutines in a computer program. Specifically, each node represents a procedure and each edge "(f,g)" indicates that procedure "f" calls procedure "g". Thus, a cycle in the graph indicates recursive procedure calls.

Call graphs are a basic program analysis result that can be used for human understanding of programs, or as a basis for further analyses, such as an analysis that tracks the flow of values between procedures. One simple application of call graphs is finding procedures that are never called.

Call graphs can be dynamic or static. A dynamic call graph is a record of an execution of the program, e.g., as output by a profiler. Thus, a dynamic call graph can be exact, but only describes one run of the program. A static call graph is a call graph intended to represent every possible run of the program. The exact static call graph is undecidable, so static call graph algorithms are generally overapproximations. That is, every call relationship that occur is represented in the graph, and possibly also some call relationships that would never occur in actual runs of the program.

Call graphs can be defined to represent varying degrees of precision. A more precise call graph more precisely approximates the behavior of the real program, at the cost of taking longer to compute and more memory to store. The most precise call graph is fully context-sensitive, which means that for each procedure, the graph contains a separate node for each call stack that procedure can be activated with. A fully context-sensitive call graph can be computed dynamically easily, although it may take up a large amount of memory. Fully context-sensitive call graphs are usually not computed statically, because it would take too long for a large program. The least precise call graph is context-insensitive, which means that there is only one node for each procedure.

With languages that feature dynamic dispatch, such as Java and C++, computing a static call graph precisely requires alias analysis results. Conversely, computing precise aliasing requires a call graph. Many static analysis systems solve the apparent infinite regress by computing both simultaneously.

This term is frequently used in the compiler and binary translation community. By tracking a call graph, it may be possible to detect anomalies of program execution or code injection attacksFact|date=February 2007.

oftware

Free software call-graph generators

; [http://kcachegrind.sourceforge.net/cgi-bin/show.cgi KCachegrind] : powerful tool to generate and analyze call graphs based on data generated by Valgrind's callgrind tool.; [http://www.csn.ul.ie/~mel/projects/codeviz/ codeviz] : a static call graph generator (the program is "not" run). Implemented as a patch to gcc; works for C and C++ programs.; [http://www.gson.org/egypt/ egypt] : a small Perl script that uses gcc and Graphviz to generate the static call graph of a C program.; gprof : part of the GNU Binary Utilities; [http://pycallgraph.slowchop.com/ pycallgraph] : a call graph generator for Python programs that uses Graphviz.; [http://www.stack.nl/~dimitri/doxygen/ doxygen] : Uses graphviz to generate static call/inheritance diagrams

Proprietary call-graph generators

; [http://www.aisee.com/aicall/ aiCall] : Free evaluation version

Other, related tools

; Graphviz : Turns a text representation of any graph (including a call graph) into a picture. Must be used together with gprof, which in accordance to the Unix philosophy doesn't handle graphics by itself.

ample Graph

A sample Call Graph generate from GProf analyzing itself (while analyzing itself):

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]

References

*Ryder, B.G., "Constructing the Call Graph of a Program," Software Engineering, IEEE Transactions on , vol.SE-5, no.3pp. 216- 226, May 1979 [http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=35910&arnumber=1702621&count=17&index=5]
*Grove, D., DeFouw, G., Dean, J., and Chambers, C. 1997. Call graph construction in object-oriented languages. SIGPLAN Not. 32, 10 (Oct. 1997), 108-124. [http://doi.acm.org/10.1145/263700.264352]
*Callahan, D.; Carle, A.; Hall, M.W.; Kennedy, K., "Constructing the procedure call multigraph," Software Engineering, IEEE Transactions on , vol.16, no.4pp.483-487, Apr 1990 [http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=1950&arnumber=54302&count=13&index=12]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • call graph — noun A directed graph that represents relationships between called and calling subroutines in a computer program, used in code analysis …   Wiktionary

  • Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

  • Graph factorization — Not to be confused with Factor graph. 1 factorization of Desargues graph: each color class is a 1 factor …   Wikipedia

  • Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia

  • Median graph — The median of three vertices in a median graph In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest… …   Wikipedia

  • Minor (graph theory) — In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. The theory of graph minors began with Wagner s theorem that a graph… …   Wikipedia

  • Claw-free graph — A claw In graph theory, an area of mathematics, a claw free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and …   Wikipedia

  • Hadwiger conjecture (graph theory) — In graph theory, the Hadwiger conjecture (or Hadwiger s conjecture) states that, if an undirected graph G requires k or more colors in any vertex coloring, then one can find k disjoint connected subgraphs of G such that each subgraph is connected …   Wikipedia

  • Signed graph — In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign.Formally, a signed graph Sigma; is a pair ( G , sigma;) that consists of a graph G = ( V , E ) and a sign mapping or… …   Wikipedia

  • Directed acyclic graph — An example of a directed acyclic graph In mathematics and computer science, a directed acyclic graph (DAG i …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”