호출 그래프
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
호출 그래프는 프로그램 내 함수 간의 호출 관계를 시각적으로 나타낸 것이다. 동적 호출 그래프는 프로그램 실행 중의 호출 관계를 기록하며, 정적 호출 그래프는 프로그램의 모든 가능한 실행 경로를 나타내도록 설계되었다. 정적 호출 그래프는 정확하게 계산하기 어려워 과대 근사하는 경우가 많다. 호출 그래프는 정밀도에 따라 컨텍스트 감지 및 컨텍스트 비감지 방식으로 구분되며, 동적 디스패치, 일급 함수, 함수 포인터 등을 사용하는 언어에서는 별칭 분석이 필요하다. 호출 그래프는 호출되지 않는 함수를 찾고, 프로그램 이해를 돕고, 최적화 및 디버깅, 보안 분석 등에 활용된다. 다양한 오픈 소스 및 상용 소프트웨어가 호출 그래프를 생성하는 데 사용된다.
더 읽어볼만한 페이지
- 정적 프로그램 분석 - 호어 논리
호어 논리는 프로그램의 실행 전후 조건을 명시하고 코드 조각이 조건을 어떻게 변화시키는지 추론하는 규칙을 제공하여 프로그램의 정확성을 형식적으로 검증하는 논리 시스템이다. - 정적 프로그램 분석 - Perl::Critic
Perl::Critic은 Perl 코드의 품질, 스타일, 오류를 검사하여 더 나은 코드를 작성하도록 돕는 정적 분석 도구이다. - 그래프 자료 구조 - 노드 (컴퓨터 과학)
노드는 컴퓨터 과학에서 트리 구조를 이루는 구성 요소로, 자료 구조 내 정보를 표현하며, 값, 조건, 다른 자료 구조를 포함하고 부모 노드에 의해 표현되며, 웹 페이지 구조를 표현하는 데 사용된다. - 그래프 자료 구조 - 그래프 (자료 구조)
그래프는 정점과 간선으로 구성되어 정점 간의 관계를 표현하는 비선형 자료 구조로, 방향, 무방향, 가중치 그래프 등 다양한 형태로 존재하며, 인접 리스트, 인접 행렬 등으로 표현되고, DFS, BFS, 다익스트라, 플로이드-워셜 알고리즘 등을 통해 탐색 및 문제 해결에 활용된다.
| 호출 그래프 |
|---|
2. 기본 개념
호출 그래프는 동적 호출 그래프와 정적 호출 그래프로 나눌 수 있다.[4] 동적 호출 그래프는 프로그램 실행을 기록한 것으로, 프로파일러의 출력을 통해 얻을 수 있다. 동적 호출 그래프는 정확하지만, 프로그램의 한 번의 실행만을 설명한다. 정적 호출 그래프는 프로그램의 모든 가능한 실행을 나타내도록 설계된 호출 그래프이다. 정확한 정적 호출 그래프는 결정 불가능 문제이므로, 정적 호출 그래프 알고리즘은 일반적으로 과대 근사한다. 즉, 발생하는 모든 호출 관계가 그래프에 표시되며, 실제 실행에서는 절대 발생하지 않는 일부 호출 관계도 표시될 수 있다.
호출 그래프는 다양한 정밀도를 가질 수 있다. 더 정밀한 호출 그래프는 계산에 더 오래 걸리고 저장에 더 많은 메모리가 필요하지만, 실제 프로그램의 동작을 더 정확하게 근사한다.
동적 디스패치를 사용하는 언어의 경우, 정적 호출 그래프를 정확하게 계산하려면 별칭 분석 결과가 필요하다. 반대로, 정확한 별칭을 계산하려면 호출 그래프가 필요하다.
2. 1. 동적 호출 그래프
동적 호출 그래프는 프로그램의 특정 실행을 기록한 것으로, 예를 들어 프로파일러의 출력을 통해 얻을 수 있다.[4] 동적 호출 그래프는 실제로 실행된 호출 관계만 포함하므로 정확하지만, 해당 실행에 대한 정보만 제공한다는 한계가 있다.2. 2. 정적 호출 그래프
정적 호출 그래프는 프로그램의 모든 가능한 실행을 나타내도록 설계된다.[4] 정확한 정적 호출 그래프는 결정 불가능 문제이므로, 정적 호출 그래프 알고리즘은 일반적으로 과대 근사한다. 즉, 발생하는 모든 호출 관계가 그래프에 표시되며, 프로그램의 실제 실행에서는 절대 발생하지 않는 일부 호출 관계도 표시될 수 있다.호출 그래프는 다양한 정밀도를 나타내도록 정의될 수 있다. 보다 정밀한 호출 그래프는 계산에 더 오래 걸리고 저장에 더 많은 메모리가 소요되는 대가로, 실제 프로그램의 동작을 더 정확하게 근사한다. 가장 정밀한 호출 그래프는 완전한 ''컨텍스트 감지''를 가지며, 이는 각 프로시저에 대해 해당 프로시저가 활성화될 수 있는 각 호출 스택에 대한 별도의 노드가 그래프에 포함된다는 것을 의미한다. 완전한 컨텍스트 감지 호출 그래프는 호출 컨텍스트 트리라고 한다. 이는 동적으로 쉽게 계산할 수 있지만, 많은 양의 메모리를 차지할 수 있다. 호출 컨텍스트 트리는 일반적으로 정적으로 계산되지 않는데, 이는 대규모 프로그램의 경우 시간이 너무 오래 걸리기 때문이다. 가장 덜 정밀한 호출 그래프는 ''컨텍스트 비감지''이며, 이는 각 프로시저에 대해 하나의 노드만 있다는 것을 의미한다.
동적 디스패치 (예: 자바 또는 C++),[5] 일급 함수 (예: 파이썬 또는 래킷), 또는 함수 포인터 (예: C)를 특징으로 하는 언어의 경우, 정적 호출 그래프를 정확하게 계산하려면 별칭 분석 결과가 필요하다. 반대로, 정확한 별칭을 계산하려면 호출 그래프가 필요하다. 많은 정적 분석 시스템은 두 가지를 동시에 계산하여 명백한 무한 퇴행을 해결한다.
2. 3. 정밀도
호출 그래프는 다양한 정밀도로 정의될 수 있다. 정밀도가 높은 호출 그래프는 실제 프로그램의 동작을 더 정확하게 근사하지만, 계산하는 데 시간이 더 오래 걸리고 저장 공간도 더 많이 필요하다. 가장 정밀한 호출 그래프는 완전한 ''컨텍스트 감지''를 가지는데, 이는 각 프로시저에 대해 해당 프로시저가 활성화될 수 있는 각 호출 스택마다 별도의 노드가 그래프에 포함된다는 것을 의미한다. 완전한 컨텍스트 감지 호출 그래프는 호출 컨텍스트 트리라고 부른다. 이는 동적으로 쉽게 계산할 수 있지만, 메모리를 많이 차지할 수 있다. 호출 컨텍스트 트리는 대규모 프로그램의 경우 시간이 너무 오래 걸리기 때문에 일반적으로 정적으로 계산하지 않는다. 가장 덜 정밀한 호출 그래프는 ''컨텍스트 비감지''이며, 이는 각 프로시저마다 하나의 노드만 있다는 것을 의미한다.[4]2. 4. 동적 디스패치와 별칭 분석
동적 디스패치 (예: 자바 또는 C++)[5], 일급 함수 (예: 파이썬 또는 래킷), 또는 함수 포인터 (예: C)를 사용하는 언어의 경우, 정적 호출 그래프를 정확하게 계산하려면 별칭 분석 결과가 필요하다. 반대로, 정확한 별칭을 계산하려면 호출 그래프가 필요하다. 많은 정적 분석 시스템은 이 두 가지를 동시에 계산하여 명백한 무한 퇴행을 해결한다.3. 활용
호출 그래프는 호출되지 않은 프로시저를 찾거나, 프로그램 실행 또는 코드 주입 공격의 이상 징후를 탐지하는 등 다양한 방식으로 사용될 수 있다.[14][7]
3. 1. 프로그램 이해
호출 그래프는 다양한 방식으로 사용될 수 있다. 간단한 응용 중 하나는 호출되지 않은 프로시저를 찾는 것이다. 호출 그래프는 사람이 프로그램을 이해하는 데 도움이 되는 문서 역할을 할 수 있다.[13][6] 호출 그래프는 프로그램 실행이나 코드 주입 공격의 이상 징후를 탐지하는 데에도 사용할 수 있다.[14][7]3. 2. 최적화
호출 그래프는 호출되지 않는 함수(dead code)를 찾거나, 자주 호출되는 함수를 파악하여 최적화에 활용할 수 있다. 호출 그래프는 사람이 프로그램을 이해하는 데 도움을 주는 문서 역할도 할 수 있다.[13]3. 3. 디버깅
호출 그래프는 프로그램 실행 중 발생하는 오류의 원인을 추적하고, 스택 오버플로우와 같은 문제를 해결하는 데 도움을 줄 수 있다.3. 4. 보안 분석
호출 그래프는 코드 주입 공격과 같은 보안 취약점을 탐지하고 분석하는 데 활용될 수 있다.[14] 프로그램 실행의 이상 징후를 탐지하여 악성코드 분석 등에도 활용할 수 있다.[7]4. 소프트웨어
호출 그래프를 생성하는 다양한 도구들이 있으며, 자유 소프트웨어, 상용 소프트웨어, 기타 관련 도구 등으로 분류할 수 있다.
4. 1. 자유 소프트웨어
다음은 자유 소프트웨어(오픈 소스) 호출 그래프 생성 도구들이다.- codeviz: GCC에 대한 패치로 구현되었으며, C 및 C++를 지원하는 정적 호출 그래프 생성 프로그램이다(대상 프로그램은 실행하지 않음).[8]
- egypt: GCC와 Graphviz를 사용하여 C 프로그램의 정적 호출 그래프를 생성하는 짧은 Perl 스크립트이다.[8]
- gprof: GNU Binutils의 일부이다.
- pycallgraph: Graphviz를 사용하여 Python 프로그램의 호출 그래프를 생성한다.[9]
- [http://www.stack.nl/~dimitri/doxygen/ doxygen]: Graphviz를 사용하여 정적인 호출, 상속 다이어그램을 생성한다.
4. 1. 1. 런타임 호출 그래프 생성 도구 (프로파일러)
- gprof: BSD에 포함되거나 GNU 바이너리 유틸리티의 일부이다.[1]
- Callgrind: Valgrind의 일부이다.[1]
- [https://kcachegrind.github.io/html/Home.html KCachegrind]: Callgrind에서 생성된 데이터를 기반으로 호출 그래프를 생성하고 분석하는 강력한 도구이다.[1]
- Mac OS X Activity Monitor: 애플의 GUI 프로세스 모니터인 Activity Monitor에는 프로세스를 샘플링하고 호출 그래프를 반환할 수 있는 내장 호출 그래프 생성기가 있다. 이 기능은 Mac OS X 레오파드에서만 사용할 수 있다.[1]
- OpenPAT: 런타임 측정을 통해 자동으로 Graphviz 호출 그래프 그림을 생성하는
control_flow도구를 포함한다.[1] - [https://github.com/google/pprof pprof]: gperftools와 함께 사용할 프로파일 데이터의 시각화 및 분석을 위한 오픈 소스 도구이다.[1]
- Intel(R) Single Event API: 무료, 오픈 소스 도구이다.[1]
4. 1. 2. 정적 호출 그래프 생성 도구
다음은 프로그램을 실행하지 않고 정적 분석을 통해 호출 그래프를 생성하는 도구들이다.| 언어 | 도구 | 설명 |
|---|---|---|
| C/C++ | Sourcetrail | 정적 호출 그래프를 생성하고 사용자가 동적으로 탐색할 수 있도록 지원하며, Python과 Java도 지원한다. |
| C/C++ | doxygen | Graphviz를 사용하여 정적 호출/상속 다이어그램을 생성한다. |
| C | [https://github.com/chaudron/cally Cally] | GCC의 레지스터 전송 언어(RTL) 파일을 사용하여 C 프로젝트의 호출 그래프를 구축한다. |
| C | cflow | C 프로그램의 직접 및 반전 호출 그래프를 생성한다. |
| C | [http://www.gson.org/egypt/ egypt] | gcc와 Graphviz를 사용하여 C 프로그램의 정적 호출 그래프를 생성하는 Perl 스크립트이다. |
| C/C++ | [http://www.analizo.org/ Analizo] | 소스 코드 메트릭을 계산하고 종속성 그래프를 생성한다. |
| C | [https://www.vim.org/scripts/script.php?script_id=2368 CCTree] | cscope 데이터베이스를 읽어 정적 호출 그래프를 표시하는 Vim 플러그인이다. |
| C/C++ | [https://github.com/petersenna/codeviz codeviz] | 정적 호출 그래프 생성기 (gcc 패치로 구현)이다. |
| C | [http://toolchainguru.blogspot.com/2011/03/c-calltrees-in-bash-revisited.html calltree.sh] | cscope, graphviz, dot 렌더링 도구를 연결하는 Bash 쉘 함수이다. |
| C | [https://sourceforge.net/projects/tceetree/ tceetree] | Cscope와 Graphviz를 연결하는 실행 파일 (Bash 스크립트가 아님)이다. |
| Go | [https://github.com/ofabry/go-callvis go-callvis] | Graphviz로 그릴 수 있는 출력을 가진 Go 프로그램용 대화형 호출 그래프 생성기이다. |
| 다중 언어 | [https://github.com/koknat/callGraph callGraph] | awk, bash, basic, dart, fortran, go, lua, javascript, julia, kotlin, matlab, perl, pascal, php, python, R, raku, ruby, rust, scala, swift, tcl, typescript를 위한 오픈 소스 호출 그래프 생성기이다. |
| .NET | NDepend | .NET 코드용 정적 분석 도구. 종속성 그래프 및 행렬 시각화 기능을 제공한다. |
| PHP, Perl, Python | [https://metacpan.org/module/Devel::NYTProf Devel::NYTProf] | Perl 성능 분석기 및 호출 차트 생성기이다. |
| PHP | [http://phpcallgraph.sourceforge.net/ phpCallGraph] | Graphviz를 사용하는 PHP 프로그램용 호출 그래프 생성기이다. |
| Python | [http://pycallgraph.slowchop.com/ pycallgraph] | Graphviz를 사용하는 Python 프로그램용 호출 그래프 생성기이다. |
| Python | [https://github.com/davidfraser/pyan pyan] | Graphviz를 사용하는 Python 프로그램용 정적 호출 그래프 생성기이다. |
| Python | [https://github.com/jrfonseca/gprof2dot gprof2dot] | 여러 언어/런타임의 프로파일링 데이터를 Graphviz 호출 그래프로 변환한다. |
| Python, Javascript | [https://github.com/scottrogowski/code2flow code2flow] | Graphviz를 사용하는 Python 및 Javascript 프로그램용 호출 그래프 생성기이다. |
| Python | [https://github.com/carlsborg/rcviz rcviz] | 런타임에 생성된 호출 그래프를 Graphviz로 렌더링하는 Python 모듈이다. |
| XQuery | [https://en.wikibooks.org/wiki/XQuery/Call_Graphs XQuery Call Graphs from the XQuery Wikibook] | Graphviz를 사용하는 XQuery 함수 모듈용 호출 그래프 생성기이다. |
4. 2. 상용 소프트웨어
http://www.aisee.com/aicall/ aiCall는 무료 평가판이 제공된다.4. 3. 기타 관련 도구
- '''Graphviz''': 텍스트로 표현된 그래프(호출 그래프 포함)를 그림으로 변환한다. GProf와 함께 사용할 필요가 있다. 유닉스 철학에 기반하여 gprof 단독으로는 그림을 그리지 않는다.[1]
- '''tsort''': 위상 정렬을 수행하는 명령줄 유틸리티이다.[2]
참조
[1]
논문
Constructing the procedure call multigraph
1990-04
[2]
서적
Data Flow Analysis: Theory and Practice
CRC Press
[3]
서적
An Integrated Approach to Software Engineering
https://archive.org/[...]
Springer Science & Business Media
[4]
논문
Constructing the Call Graph of a Program
1979-05
[5]
논문
Call graph construction in object-oriented languages
ACM
1997-10-09
[6]
서적
Proceedings IEEE International Conference on Software Maintenance. ICSM 2001
[7]
서적
Proceedings of the 11th ACM conference on Computer and communications security - CCS '04
https://figshare.com[...]
ACM
2004-10-25
[8]
웹사이트
egypt
https://www.gson.org[...]
[9]
웹사이트
Python Call Graph — Python Call Graph 1.0.1 documentation
https://pycallgraph.[...]
[10]
논문
Constructing the procedure call multigraph
1990-04
[11]
서적
Data Flow Analysis: Theory and Practice
CRC Press
[12]
서적
An Integrated Approach to Software Engineering
https://archive.org/[...]
Springer Science & Business Media
[13]
서적
Proceedings IEEE International Conference on Software Maintenance. ICSM 2001
[14]
서적
Proceedings of the 11th ACM conference on Computer and communications security - CCS '04
https://figshare.com[...]
ACM
2004-10-25
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com