호출 그래프

Call graph
Python에서 간단한 컴퓨터 프로그램을 위해 생성된 호출 그래프입니다.

콜 그래프(콜[1][2] 멀티그래프라고도 함)는 컨트롤 플로우그래프로 [3]컴퓨터 프로그램 내의 서브루틴 간의 콜 관계를 나타냅니다.각 노드는 프로시저를 나타내고, 각 에지(f, g)는 프로시저 f가 프로시저 g를 호출하는 것을 나타낸다.따라서 그래프의 사이클은 재귀 프로시저 호출을 나타냅니다.

기본 개념

콜 그래프는 다이내믹 또는 [4]스태틱입니다.동적 콜 그래프는 프로그램 실행 기록입니다(프로파일러 출력 등).따라서 동적 콜 그래프는 정확할 수 있지만 프로그램의 실행은 1회뿐입니다.정적 콜 그래프는 프로그램의 가능한 모든 실행을 나타내는 콜그래프입니다.정확한 정적 콜그래프는 판단할 수 없는 문제이기 때문에 정적 콜그래프 알고리즘은 일반적으로 과잉 근사치입니다.즉, 발생하는 모든 콜 관계는 그래프에 나타나며, 프로그램의 실제 실행에서는 발생하지 않는 콜 관계도 있을 수 있습니다.

콜 그래프는 다양한 정밀도를 나타내도록 정의할 수 있습니다.보다 정밀한 콜그래프는 실제 프로그램의 동작을 보다 정확하게 추정하지만 계산에는 시간이 더 오래 걸리고 저장 메모리도 더 많이 소요됩니다.가장 정확한 콜 그래프는 완전히 컨텍스트에 의존합니다.즉, 각 프로시저에 대해 이 그래프는 프로시저를 활성화할 수 있는 콜스택마다 다른 노드를 포함합니다.완전 컨텍스트 의존 콜그래프는 콜 컨텍스트트리라고 불립니다이것은 메모리를 많이 사용하더라도 동적으로 쉽게 계산할 수 있습니다.대규모 프로그램에는 시간이 너무 오래 걸리기 때문에 일반적으로 콜 컨텍스트트리는 정적으로 계산되지 않습니다.가장 정밀도가 낮은 콜그래프는 문맥에 의존하지 않습니다.즉, 각 프로시저에 노드가1개밖에 존재하지 않습니다.

Java 나 C++ 등 동적 디스패치를 특징으로 하는 언어를 사용하는 경우 정적 콜그래프를 계산하려면 에일리어스 분석 [5]결과가 정확하게 필요합니다.반대로 정확한 에일리어싱을 계산하려면 콜그래프가 필요합니다.많은 정적 분석 시스템은 두 가지를 동시에 계산함으로써 명백한 무한 회귀를 해결합니다.

사용법

콜 그래프는 다양한 방법으로 사용할 수 있습니다.콜 그래프의 간단한 응용 프로그램 중 하나는 호출되지 않은 프로시저를 찾는 것입니다.콜 그래프는 인간이 [6]프로그램을 이해하기 위한 문서 역할을 할 수 있습니다.또한 절차 간 값의 흐름을 추적하는 분석이나 변경 영향 [7]예측과 같은 추가 분석의 기초가 될 수 있다.콜 그래프를 사용하여 프로그램 실행 또는 코드 주입 [8]공격의 이상을 검출할 수도 있습니다.

소프트웨어

무료 소프트웨어 콜 그래프 생성기

런타임 콜그래프(리스트에 있는 툴의 대부분은 콜그래프 기능을 가진 프로파일러)

  • gprof : BSD 또는 GNU 바이너리 유틸리티에 포함되어 있습니다.
  • callgrind : Valgrind의 일부
  • KCachegrind : 콜그라인드에 의해 생성된 데이터를 기반으로 콜그래프를 생성 및 분석하는 강력한 도구
  • Mac OS X Activity Monitor : Apple GUI 프로세스모니터 Activity Monitor에는 프로세스를 샘플링하여 콜그래프를 반환할 수 있는 콜그래프 생성기가 내장되어 있습니다.Mac OS X Leopard에서만 사용할 수 있는 기능입니다.
  • OpenPAT : 포함control_flow실행 시 측정에서 Graphviz 콜그래프 그림을 자동으로 생성하는 도구입니다.
  • 프로파일 데이터의 시각화 및 분석을 위한 오픈 소스 도구인 ppprof를 gperftools와 함께 사용합니다.
  • AMD의 Code Analyst (GPL로 출시)
  • makeppgraph는 makepp로 실행되는 빌드에 대한 종속성 그래프 생성기(모듈 레벨)입니다.
  • 인텔(R) 싱글 이벤트 API (무료, 오픈 소스)

애플리케이션을 실행하지 않고 콜그래프를 취득하기 위한 스태틱

C/C++
  • Sourcetrail은 사용자가 동적으로 탐색할 수 있는 정적 콜그래프를 만듭니다.Python 및 Java 지원
  • doxygen : Graphviz를 사용하여 정적 콜/상속도를 생성합니다.
  • cflow : GNU cflow는 C 프로그램의 직접 콜그래프와 반전 콜그래프를 생성할 수 있습니다.
  • 이집트 : gcc 및 Graphviz를 사용하여 C 프로그램의 스태틱콜 그래프를 생성하는 소규모 Perl 스크립트
  • Analizo: 소스 코드 메트릭을 계산하고 종속성 그래프를 생성합니다.
  • CCTree : cscope 데이터베이스를 읽어 스태틱콜 그래프를 표시할 수 있는 네이티브 Vim 플러그인C 프로그램에 대응합니다.
  • codeviz : 스태틱콜 그래프 생성기(프로그램은 실행되지 않습니다).gcc에 대한 패치로 구현되어 C 및 C++ 프로그램에서 작동합니다.
  • 콜 트리sh : cscope, graphviz 및 닷렌더링 툴의 샘플링을 결합하는 Bash 쉘 함수.지정된 C 함수 위, 아래 및/또는 그 사이의 "발신자" 및 "발신자" 관계를 표시합니다.
  • tceetree :calltree.sh과 마찬가지로 Cscope와 Graphviz를 연결하지만 bash 스크립트가 아닌 실행 파일입니다.
가세요
  • go-callvis : Graphviz로 출력을 그릴 수 있는 Go 프로그램용 인터랙티브콜 그래프 생성기
다국어
  • callGraph : awk, bash, basic, dart, fortran, go, lua, javascript, julia, kotlin, matlab, pascal, phthon, R, raku, ruby, rust, scala, swift, tcl, tcl 및 tcript용 오픈소스 호출그래프 생성기.
.그물
  • NDepend :의 정적 분석 도구입니다.NET 코드이 도구는 다수의 코드 메트릭을 지원하며 방향 그래프와 종속성 매트릭스를 사용하여 종속성을 시각화할 수 있습니다.
PHP, Perl 및 Python
  • 개발::NYTProf:Perl 퍼포먼스아나라이저 및 콜차트 생성기
  • phpCallGraph : Graphviz를 사용하는 PHP 프로그램의 호출 그래프 생성기.PHP로 작성되어 있으며 적어도 PHP 5.2가 필요합니다.
  • pycallgraph : Graphviz를 사용하는 Python 프로그램의 콜그래프 생성기.
  • pyan : Graphviz를 사용하는 Python 프로그램의 정적 호출 그래프 생성기.
  • gprof2dot : 여러 언어/런타임 프로파일링 데이터를 Graphviz 콜그래프로 변환하는 Python으로 작성된 콜그래프 생성기.
  • code2flow : Graphviz를 사용하는 Python 및 Javascript 프로그램용 호출 그래프 생성기
  • rcviz : Graphviz를 사용하여 런타임 생성 콜그래프를 렌더링하기 위한 Python 모듈.각 노드는 전달된 파라미터와 반환값을 가진 함수의 호출을 나타냅니다.
XQuery

독자적인 콜 그래프 생성기

LDRA 테스트베드
호스트 및 임베디드 소프트웨어 양쪽의 스태틱 및 다이내믹 분석 엔진.콜 그래프를 포함한 수많은 보고서를 제공합니다.
프로젝트 분석기
Visual Basic 코드의 정적 코드 분석기 및 콜 그래프 생성기
비주얼 엑스퍼트
Oracle PL/SQL, SQL Server Transact-SQL, C# 및 PowerBuilder 코드의 정적 코드 분석기 및 콜 그래프 생성기
인텔 VTune 퍼포먼스아나라이저
호출 그래프 및 실행 통계를 표시하기 위한 프로파일러 계측
DMS 소프트웨어 리엔지니어링 툴킷
C, Java 및 COBOL용 정적 전체 프로그램 콜 그래프 추출을 통한 맞춤 가능한 프로그램 분석 도구

기타 관련 도구

그래피즈
임의의 그래프(콜 그래프 포함)의 텍스트 표현을 그림으로 변환합니다.
쇼트
토폴로지 정렬을 수행하는 명령줄 유틸리티.

샘플 그래프

gprof 자체 분석에서 생성된 콜그래프 예를 다음에 나타냅니다.

name 72384/72384 sym_id_dfn [54] 1508/1508 cg_dfn [15] [3] 72384 일치 [13] 1508 pre_defn [13] ----------------------------------------------------------------------------------------------------------------------------------------------------------------------4/9052 cg_cg[32] 1508/1508 cg_assembly [38] 3016/9052 hist_print [49] [14] 1508 전파_time [14] 6032/9052 전파_cg [52] ---------------------------------[ 4] 9052 sym_cg_df [ 4]n [15] ----------------------- 1507/1507 cg_assembly [38] 5766/5766 core_create_function_syms [41][15] [15] 1507+2 cg_dfn [5] core_class [5] 1509/1509는 [9] --------------------------------------------------------------------------------------------------------------1508/1508 is_context [11] 24/1537 parse_spec [19] 1508/1508 pre_syms [13] 1513/1537 core_create_function_syms [41] 1508/1508 post_syms [12] [6] 1537 sym [6]2 cg_dfn [15]----------------------------------- 1511 core_create_function_syms [41] 1505 hist_print [49][7] 1511 get_src_info [7] [16] 1505 print _ line [ 16] ----------------------------------------------------- 2/9 print _ name _ name _ name _ name _ only [ 25 / 151010arc_add [31] --------------------------- 1508/1510 cg_assembly [38] 1430 core_create_function_syms [41][8] 1510 arc_syms [8] [17] 1430 source_file_path [17] ---------------------------------------------------------------------------------------------------------------------- 1509/1509 cg_dfn [ 15 ]24/24 sym_id_pec [ 54 ][ 9 ][ 18 ]24 parse_id [ 18 ] -------------------------------------------------------------------------- [ 10 ] 1508 inherit _ parse _ id [ 10 ]24/24 parse _ id [ 18 ] --------------------------- [ 19 ]24 parse _ spec [ 19 ]1508 cg _ dfn [ 15 ]24 symi [ 6 ][ 11 ][ 11 ]-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

「 」를 참조해 주세요.

레퍼런스

  1. ^ Callahan, D.; Carle, A.; Hall, M.W.; Kennedy, K. (April 1990). "Constructing the procedure call multigraph". IEEE Transactions on Software Engineering. 16 (4): 483–487. doi:10.1109/32.54302.
  2. ^ Uday Khedker; Amitabha Sanyal; Bageshri Sathe (2009). Data Flow Analysis: Theory and Practice. CRC Press. p. 234. ISBN 978-0-8493-3251-7.
  3. ^ Pankaj Jalote (1997). An Integrated Approach to Software Engineering. Springer Science & Business Media. p. 372. ISBN 978-0-387-94899-7.
  4. ^ Ryder, B.G. (May 1979). "Constructing the Call Graph of a Program". IEEE Transactions on Software Engineering. SE-5 (3): 216–226. doi:10.1109/tse.1979.234183.
  5. ^ Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig; Grove, David; DeFouw, Greg; Dean, Jeffrey; Chambers, Craig (9 October 1997). "Call graph construction in object-oriented languages". ACM SIGPLAN Notices. ACM. 32 (10): 108, 108–124, 124. doi:10.1145/263700.264352.
  6. ^ Eisenbarth, T.; Koschke, R.; Simon, D. (2001). "Aiding program comprehension by static and dynamic feature analysis". Proceedings IEEE International Conference on Software Maintenance. ICSM 2001: 602–611. doi:10.1109/icsm.2001.972777. ISBN 0-7695-1189-9.
  7. ^ Musco, Vincenzo; Monperrus, Martin; Preux, Philippe (26 July 2016). "A large-scale study of call graph-based impact prediction using mutation testing". Software Quality Journal. 25 (3): 921–950. arXiv:1812.06286. doi:10.1007/s11219-016-9332-8.
  8. ^ Gao, Debin; Reiter, Michael K.; Song, Dawn (25 October 2004). "Gray-box extraction of execution graphs for anomaly detection". Proceedings of the 11th ACM conference on Computer and communications security - CCS '04. ACM. pp. 318–329. doi:10.1145/1030083.1030126. ISBN 1581139616.