گراف فراخوانی
گراف فراخوانی (که به عنوان مولتی گراف فراخوانی[۱] نیز شناخته میشود) یک گراف کنترل جریان است، که روابط فراخوانی بین زیر برنامهها را در یک برنامه کامپیوتری نشان میدهد. هر راس یک دستور العمل را نشان میدهد و هر یال (f, g) نشان میدهد که دستورالعمل f روند g را فراخوانی میکند. در نتیجه، یک چرخه در گراف فراخوانی رویه بازگشتی را نشان میدهد.
مفاهیم پایهای[ویرایش]
گرافهای فراخوانی میتوانند پویا یا ایستا باشند.[۲] یک گراف فراخوانی پویا یک ثبت از اجرای برنامه است، به عنوان مثال به عنوان خروجی توسط یک پروفایلر؛ بنابراین، یک گراف فراخوانی پویا میتواند دقیق باشد، اما فقط یک بار اجرای برنامه را توصیف میکند. یک گراف فراخوانی ایستا یک گراف فراخوانی است که طراحی شدهاست تا همهٔ اجراهای ممکن برنامه را نمایش دهد. داشتن گراف فراخوانی استاتیک کاملاً دقیق یک مسئله حل نشدنی است، بنابراین الگوریتمهای گراف فراخوانی استاتیک معمولاً با تقریب بیش از حد به دست آمدهاند؛ یعنی هر رابطه فراخوانی که رخ میدهد در گراف نشان داده میشود، و احتمالاً برخی از روابط فراخوانی که هرگز در اجرای واقعی برنامه رخ نمیدهند نیز در گراف نمایش داده میشوند.
گرافهای فراخوانی را میتوان طوری تعریف کرد که بتوانند درجات مختلفی از دقت را نمایش دهند. یک گراف فراخوانی دقیق تر، رفتار برنامه واقعی را با دقت بیشتری تقریب میکند، به قیمت اینکه زمان بیشتری برای محاسبه کردن و حافظه بیشتری برای ذخیرهسازی نیاز داریم. دقیقترین گراف فراخوانی کاملاً به متن حساس است، به این معنی که گراف برای هر دستور العمل، شامل یک راس جداگانه برای هر پشته فراخوانی است که میتوان با آن دستور العمل را فعال کرد. یک گراف فراخوانی کاملاً حساس به متن، درخت فراخوانی محتوا نامیده میشود. این را میتوان به راحتی به صورت پویا محاسبه کرد، اگرچه ممکن است مقدار زیادی از حافظه را اشغال کند. فراخوانی درختهای محتوا معمولاً به صورت ایستا محاسبه نمیشود، زیرا ممکن است برای یک برنامه بزرگ خیلی زمان بر باشد. گراف فراخوانی این که کمترین دقت را دارد گراف فراخوانی غیر حساس به متن است، به این معنی که برای هر رویه فقط یک راس وجود دارد.
با زبانهایی که دارای ارسال پویا هستند، مانند جاوا و C++، محاسبه یک گراف فراخوانی ایستا دقیقاً به نتایج تجزیه و تحلیل مستعار نیاز دارد.[۳] و برعکس، محاسبه نام مستعار دقیق به یک گراف فراخوانی نیاز دارد. بسیاری از سیستمهای تجزیه و تحلیل استاتیک، رگرسیون نامتناهی ظاهری را با محاسبه آن دو بهطور همزمان حل میکنند.
موارد استفاده[ویرایش]
گرافهای تجزبه را میتوان به روشهای مختلفی استفاده کرد. یکی از کاربردهای ساده گرافهای فراخوانی، یافتن دستورالعملهایی است که هرگز فراخوانی نمیشوند. گرافهای فراخوانی میتوانند به عنوان سندی برای درک برنامهها توسط انسان عمل کنند.[۴] آنها همچنین میتوانند به عنوان پایه ای برای تجزیه و تحلیلهای بیشتر، مانند تجزیه و تحلیلی که جریان مقادیر بین رویهها را دنبال میکند، یا پیشبینی تأثیر تغییر، عمل کنند.[۵] همچنین از گرافهای فراخوانی میتوان برای تشخیص ناهنجاریهای اجرای برنامه یا حملات تزریق کد استفاده کرد.
نرمافزار[ویرایش]
نرمافزارهای آزاد مولد گراف فراخوانی[ویرایش]
گراف فراخوانی زمان اجرا (بیشتر ابزارهای فهرست شده پروفایلرهایی با عملکرد گراف فراخوانی هستند)[ویرایش]
- gprof: در BSD یا بخشی از ابزار باینری گنو گنجانده شدهاست.
- callgrind: بخشی از والگریند(valgrind)
- KCachegrind: ابزاری قدرتمند برای تولید و تجزیه و تحلیل گرافهای فراخوانی بر اساس دادههایی که توسط callgrind تولید شدهاند.
- Mac OS X Activity Monitor: مانیتور فرایند رابط کاربر گرافیکی اپل دارای یک تولید کنندهٔ گراف فراخوانی درون خود است که میتواند فرایندهارا به صورت نمونه تولید کند و یک گراف فراخوانی برگرداند. این عملکرد فقط در Mac OS X Leopard موجود است.
- OpenPAT: شامل ابزار کنترل جریان است که بهطور خودکار یک تصویر گراف فراخوانی Graphviz را از اندازهگیریهای زمان اجرای برنامه ایجاد میکند.
- pprof، ابزار منبع باز برای تجسم و تجزیه و تحلیل دادههای پروفایل است، تا در ارتباط با gperftools استفاده شود.
- CodeAnalyst از AMD (منتشر شده تحت GPL)
- makeppgraph یک مولد گراف وابستگی (در سطح ماژول) برای ساختههای عملی شده با makepp است.
- Intel(R) Single Event API (آزاد و منبع باز)
استاتیک برای دریافت گراف فراخوانی بدون اجرای برنامه[ویرایش]
C++/C
- Sourcetrail یک گراف فراخوانی ایستا ایجاد میکند که میتواند به صورت پویا توسط کاربر کاوش شود. از پایتون و جاوا نیز پشتیبانی میکند
- doxygen: از Graphviz برای تولید نمودارهای تماس/ارث بری استاتیک استفاده میکند
- cflow GNU :cflow قادر است گراف فراخوانی مستقیم و معکوس یک برنامه C را تولید کند
- egypt: یک اسکریپت پرل کوچک که از gcc و Graphviz برای تولید گراف فراخوانی ایستا یک برنامه C استفاده میکند.
- Analizo: معیارهای کد منبع را محاسبه میکند، نمودارهای وابستگی تولید میکند.
- CCTree: افزونه Native Vim که میتواند نمودارهای تماس ثابت را با خواندن پایگاه داده cscope نمایش دهد. برای برنامههای C کار میکند.
- codeviz: یک مولد گراف فراخوانی ایستا (برنامه اجرا نمیشود). به عنوان یک پچ برای gcc پیادهسازی شدهاست. برای برنامههای C و C++ کار میکند.
- calltree.sh: توابع پوسته Bash که cscope, graphviz، و نمونهای از ابزارهای رندر نقطهای را به هم میچسبانند تا روابط "caller" و "callee" را در بالا، پایین و/یا بین توابع C که مشخص کردهاید نشان دهند.
- tceetree: مانند calltree.sh, Cscope و Graphviz را به هم متصل میکند، اما یک اسکریپت اجرایی به جای bash است.
- Go
- برو-کالویس: یک مولد گراف فراخوانی تعاملی برای برنامههای Go است که خروجی آن را میتوان با Graphviz ترسیم کرد.
- چند زبانه
- callGraph: مولد گراف فراخوانی منبع باز برای awk, bash, basic, dart, fortran, go, lua, javascript, julia, kotlin, matlab, perl, pascal, php, python, R, raku, ruby, rust, scala, swift, tcl, and typescript.
- .NET
- NDepend :یک ابزار تحلیل ایستا برای کد NET. است این ابزار از تعداد زیادی معیار کد پشتیبانی میکند و امکان تجسم وابستگیها را با استفاده از گرافهای جهت دار و ماتریس وابستگی فراهم میکند.
- PHP, Perl و Python
- توسعه دهنده::NYTProf: یک تحلیلگر عملکرد پرل و مولد نمودار فراخوانی است.
- phpCallGraph: یک مولد گراف فراخوانی برای برنامههای PHP که از Graphviz استفاده میکند. به زبان PHP نوشته شدهاست و حداقل به PHP 5.2 نیاز دارد.
- pycallgraph: یک مولد گراف فراخوانی برای برنامههای پایتون است که از Graphviz استفاده میکند.
- پیان: یک مولد گراف فراخوانی ایستا برای برنامههای پایتون که از Graphviz استفاده میکند.
- gprof2dot: یک مولد گراف فراخوانی که به زبان پایتون نوشته شدهاست که دادههای پروفایل برای بسیاری از زبانها/زمانهای اجرا را به یک Graphviz callgraph تبدیل میکند.
- code2flow: یک مولد گراف فراخوانی برای برنامههای پایتون و جاوا اسکریپت که از Graphviz استفاده میکند
- rcviz: ماژول پایتون برای رندر کردن گرافهای تماس تولید شده در زمان اجرا با Graphviz. هر راس نشان دهنده فراخوانی یک تابع با پارامترهای ارسال شده به آن و مقداری که بازگشته است.
- XQuery
- نمودارهای فراخوانی XQuery از ویکیبوک XQuery: یک مولد گراف فراخوانی برای یک ماژول تابع XQuery که از Graphviz استفاده میکند
مولد گراف فراخوانی اختصاصی[ویرایش]
- بستر آزمایش LDRA
- موتورهای تجزیه و تحلیل استاتیک و پویا برای هر دو نرمافزار میزبان و هم جاسازی شده، با تعداد بی شماری از گزارشها از جمله گراف فراخوانی.
- تحلیلگر پروژه
- تحلیلگر کد ایستا و مولد گراف فراخوانی برای کدهای ویژوال بیسیک
- کارشناس بصری
- تحلیلگر کد ایستا و مولد گراف فراخوانی برای Oracle PL/SQL، SQLServer Transact-SQL، C# و کد PowerBuilder
- آنالایزر عملکرد اینتل VTune
- نمایه ساز ابزار دقیق برای نمایش گراف فراخوانی و آمار اجرای برنامه
- مجموعه ابزار مهندسی مجدد نرمافزار DMS
- ابزار تجزیه و تحلیل برنامه قابل تنظیم با استخراج گراف فراخوانی سراسری استاتیک کل برنامه برای C، جاوا و COBOL
سایر ابزارهای مرتبط[ویرایش]
- <a href="https://en.wikipedia.org/wiki/Graphviz" rel="mw:ExtLink" title="Graphviz" class="cx-link" data-linkid="146">Graphviz</a>
- یک نمایش متنی از هر گراف (از جمله گراف فراخوانی) را به تصویر تبدیل میکند.
- <a href="https://en.wikipedia.org/wiki/Tsort" rel="mw:ExtLink" title="Tsort" class="cx-link" data-linkid="149">tsort</a>
- ابزار خط فرمان که مرتبسازی توپولوژیکی را انجام میدهد.
منابع[ویرایش]
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.