گراف فراخوانی: تفاوت میان نسخهها
برچسب ویرایش و اصلاح جزئی |
ایجاد شده بهواسطهٔ ترجمهٔ صفحهٔ «Call graph» |
||
خط ۱: | خط ۱: | ||
[[پرونده:A_Call_Graph_generated_by_pycallgraph.png|بندانگشتی| یک |
[[پرونده:A_Call_Graph_generated_by_pycallgraph.png|بندانگشتی| یک گراف فراخوانی که برای یک برنامه کامپیوتری ساده در زبان برنامه نویسی پایتون ایجاد شده است.]] |
||
'''"این مقاله در حال ترجمه از ویکی انگلیسی است لطفا حذف نشود."''' |
'''"این مقاله در حال ترجمه از ویکی انگلیسی است لطفا حذف نشود."''' |
||
{{ویرایش}} |
|||
'''گراف فراخوانی''' (که به عنوان '''مولتی گراف فراخوانی''' <ref>{{Cite journal|last=Callahan|first=D.|last2=Carle|first2=A.|last3=Hall|first3=M.W.|last4=Kennedy|first4=K.|date=April 1990|title=Constructing the procedure call multigraph|journal=IEEE Transactions on Software Engineering|volume=16|issue=4|pages=483–487|doi=10.1109/32.54302}}</ref> نیز شناخته میشود.) یک [[گراف روند کنترلی|گراف کنترل جریان است]] ، که روابط فراخوانی بین [[رویه (علوم رایانه)|زیر برنامه ها را]] در یک [[برنامه رایانهای|برنامه کامپیوتری نشان می دهد]] . هر گره یک دستور العمل را نشان می دهد و هر یال ''(f, g)'' نشان می دهد که دستورالعمل ''f'' ''روند g را'' فراخوانی می کند. در نتیجه، یک [[دور (نظریه گراف)|چرخه]] در |
'''گراف فراخوانی''' (که به عنوان '''مولتی گراف فراخوانی''' <ref>{{Cite journal|last=Callahan|first=D.|last2=Carle|first2=A.|last3=Hall|first3=M.W.|last4=Kennedy|first4=K.|date=April 1990|title=Constructing the procedure call multigraph|journal=IEEE Transactions on Software Engineering|volume=16|issue=4|pages=483–487|doi=10.1109/32.54302}}</ref> نیز شناخته میشود.) یک [[گراف روند کنترلی|گراف کنترل جریان است]] ، که روابط فراخوانی بین [[رویه (علوم رایانه)|زیر برنامه ها را]] در یک [[برنامه رایانهای|برنامه کامپیوتری نشان می دهد]] . هر گره یک دستور العمل را نشان می دهد و هر یال ''(f, g)'' نشان می دهد که دستورالعمل ''f'' ''روند g را'' فراخوانی می کند. در نتیجه، یک [[دور (نظریه گراف)|چرخه]] در گراف فراخوانی رویه بازگشتی را نشان می دهد. |
||
== مفاهیم پایه ای == |
== مفاهیم پایه ای == |
||
گراف های فراخوانی می توانند پویا یا ایستا باشند. <ref>{{Cite journal|last=Ryder|first=B.G.|date=May 1979|title=Constructing the Call Graph of a Program|journal=IEEE Transactions on Software Engineering|volume=SE-5|issue=3|pages=216–226|doi=10.1109/tse.1979.234183}}</ref> یک گراف فراخوانی پویا یک ثبت از اجرای برنامه است، به عنوان مثال به عنوان خروجی توسط یک پروفایلر. بنابراین، یک گراف فراخوانی پویا می تواند دقیق باشد، اما فقط یک بار اجرای برنامه را توصیف می کند. یک گراف فراخوانی ایستا یک گراف فراخوانی است که طراحی شده است تا همه ی اجراهای ممکن برنامه را نمایش دهد. داشتن گراف فراخوانی استاتیک کاملا دقیق یک [[مسئله تصمیمناپذیر|مساله حل نشدنی است]]، بنابراین الگوریتمهای گراف فراخوانی استاتیک معمولاً با تقریب بیش از حد به دست آمده اند. یعنی هر رابطه فراخوانی که رخ میدهد در گراف نشان داده میشود، و احتمالاً برخی از روابط فراخوانی که هرگز در اجرای واقعی برنامه رخ نمیدهند نیز در گراف نمایش داده میشوند. |
|||
⚫ | گرافهای فراخوانی را می توان طوری تعریف کرد که بتوانند درجات مختلفی از دقت را نمایش دهند. یک گراف فراخوانی دقیق تر، رفتار برنامه واقعی را با دقت بیشتری تقریب می کند، به قیمت اینکه زمان بیشتری برای محاسبه کردن و حافظه بیشتری برای ذخیره سازی نیاز داریم. دقیقترین گراف فراخوانی کاملاً به ''متن حساس است'' ، به این معنی که گراف برای هر دستور العمل، شامل یک گره جداگانه برای هر [[پشته تماس|پشته فراخوانی است]] که میتوان با آن دستور العمل را فعال کرد. یک گراف تماس کاملاً حساس به متن، درخت فراخوانی محتوا نامیده می شود. این را می توان به راحتی به صورت پویا محاسبه کرد، اگرچه ممکن است مقدار زیادی از حافظه را اشغال کند. فراخوانی درختهای محتوا معمولاً به صورت ایستا محاسبه نمیشود، زیرا ممکن است برای یک برنامه بزرگ خیلی زمان بر باشد. گراف فراخوانی این که کمترین دقت را دارد گراف فراخوانی غیر ''حساس به متن است'' ، به این معنی که برای هر رویه فقط یک گره وجود دارد. |
||
با زبان هایی که دارای ارسال پویا هستند ، مانند [[جاوا]] و [[C++]] ، محاسبه یک گراف فراخوانی ایستا دقیقاً به نتایج [[تحلیل مستعار|تجزیه و تحلیل مستعار نیاز دارد.]] <ref>{{Cite journal|last=Grove|first=David|last2=DeFouw|first2=Greg|last3=Dean|first3=Jeffrey|last4=Chambers|first4=Craig|last5=Grove|first5=David|last6=DeFouw|first6=Greg|last7=Dean|first7=Jeffrey|last8=Chambers|first8=Craig|date=9 October 1997|title=Call graph construction in object-oriented languages|journal=ACM SIGPLAN Notices|publisher=ACM|volume=32|issue=10|pages=108, 108–124, 124|doi=10.1145/263700.264352}}</ref> و برعکس، محاسبه نام مستعار دقیق به یک گراف فراخوانی نیاز دارد. بسیاری از سیستم های تجزیه و تحلیل استاتیک، رگرسیون نامتناهی ظاهری را با محاسبه آن دو به طور همزمان حل می کنند. |
|||
== موارد استفاده == |
|||
گراف های تجزبه را می توان به روش های مختلفی استفاده کرد. یکی از کاربردهای ساده گراف های فراخوانی، یافتن دستورالعمل هایی است که هرگز فراخوانی نمی شوند. گراف های فراخوانی می توانند به عنوان سندی برای درک برنامه ها توسط انسان عمل کنند. <ref>{{Cite journal|last=Eisenbarth|first=T.|last2=Koschke|first2=R.|last3=Simon|first3=D.|year=2001|title=Aiding program comprehension by static and dynamic feature analysis|journal=Proceedings IEEE International Conference on Software Maintenance. ICSM 2001|pages=602–611|doi=10.1109/icsm.2001.972777|isbn=0-7695-1189-9}}</ref> آنها همچنین می توانند به عنوان پایه ای برای تجزیه و تحلیل های بیشتر، مانند تجزیه و تحلیلی که جریان مقادیر بین رویه ها را دنبال می کند، یا پیش بینی تأثیر تغییر ، عمل کنند. <ref>{{Cite journal|last=Musco|first=Vincenzo|last2=Monperrus|first2=Martin|last3=Preux|first3=Philippe|date=26 July 2016|title=A large-scale study of call graph-based impact prediction using mutation testing|url=https://hal.archives-ouvertes.fr/hal-01346046/document|journal=Software Quality Journal|volume=25|issue=3|pages=921–950|arxiv=1812.06286|doi=10.1007/s11219-016-9332-8}}</ref> همچنین از گراف های فراخوانی می توان برای تشخیص ناهنجاری های اجرای برنامه یا حملات تزریق کد استفاده کرد. |
|||
== نرم افزار == |
|||
⚫ | |||
=== [[نرمافزار آزاد|نرم افزارهای رایگان]] مولد گراف فراخوانی === |
|||
==== گراف فراخوانی زمان اجرا (بیشتر ابزارهای فهرست شده پروفایلرهایی با عملکرد گراف فراخوانی هستند) ==== |
|||
== منابع == |
|||
{{پانویس|چپچین= بله}} |
|||
* gprof : در BSD یا بخشی از ابزار [[ابزار مدیریت برنامههای باینری گنو|باینری گنو]] گنجانده شده است. |
|||
* callgrind : بخشی از والگریند(valgrind) |
|||
* [https://kcachegrind.github.io/html/Home.html KCachegrind] : ابزاری قدرتمند برای تولید و تجزیه و تحلیل گراف های فراخوانی بر اساس داده هایی که توسط callgrind تولید شده اند. |
|||
* Mac OS X Activity Monitor: مانیتور فرایند رابط کاربر گرافیکی اپل دارای یک تولید کننده ی گراف فراخوانی درون خود است که می تواند فرایندهارا به صورت نمونه تولید کند و یک گراف فراخوانی برگرداند. این عملکرد فقط در [[مکاواس|Mac OS X]] Leopard موجود است. |
|||
* OpenPAT : شامل ابزار کنترل جریان است که به طور خودکار یک تصویر گراف فراخوانی Graphviz را از اندازه گیری های زمان اجرای برنامه ایجاد میکند. |
|||
* [https://github.com/google/pprof pprof] ، ابزار منبع باز برای تجسم و تجزیه و تحلیل داده های پروفایل است، تا در ارتباط با [https://web.archive.org/web/20150904193554/http://gperftools.googlecode.com/git/doc/cpuprofile.html gperftools] استفاده شود . |
|||
* CodeAnalyst از [[ایامدی|AMD]] (منتشر شده تحت GPL) |
|||
* [http://makepp.sourceforge.net/gallery/ makeppgraph] یک مولد گراف وابستگی (در سطح ماژول) برای ساخته های عملی شده با [[ساخت (نرمافزار)|makepp]] است . |
|||
* [https://github.com/01org/IntelSEAPI/wiki Intel(R) Single Event API] (رایگان، منبع باز) |
|||
[[رده:آنالیز ایستای برنامه]] |
[[رده:آنالیز ایستای برنامه]] |
||
[[رده:مولدهای مستندسازی]] |
[[رده:مولدهای مستندسازی]] |
نسخهٔ ۷ دسامبر ۲۰۲۱، ساعت ۲۰:۲۹
"این مقاله در حال ترجمه از ویکی انگلیسی است لطفا حذف نشود."
گراف فراخوانی (که به عنوان مولتی گراف فراخوانی [۱] نیز شناخته میشود.) یک گراف کنترل جریان است ، که روابط فراخوانی بین زیر برنامه ها را در یک برنامه کامپیوتری نشان می دهد . هر گره یک دستور العمل را نشان می دهد و هر یال (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 (رایگان، منبع باز)
- ↑ 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.