कॉल ग्राफ: Difference between revisions
No edit summary |
No edit summary |
||
| Line 7: | Line 7: | ||
सटीकता की अलग-अलग डिग्री का प्रतिनिधित्व करने के लिए कॉल ग्राफ़ को परिभाषित किया जा सकता है। अधिक सटीक कॉल ग्राफ़ अधिक सटीक रूप से वास्तविक प्रोग्राम के व्यवहार का अनुमान लगाता है, गणना करने में अधिक समय लेने और स्टोर करने के लिए अधिक मेमोरी की योग्यता पर। सबसे सटीक कॉल ग्राफ़ पूरी तरह से संदर्भ-संवेदनशील है, जिसका अर्थ है कि प्रत्येक प्रक्रिया के लिए, ग्राफ़ में प्रत्येक [[कॉल स्टैक]] के लिए एक अलग नोड होता है जिसके साथ प्रक्रिया को सक्रिय किया जा सकता है। एक पूरी तरह से संदर्भ-संवेदनशील कॉल ग्राफ़ को कॉलिंग संदर्भ ट्री कहा जाता है। इसकी गतिशील रूप से सुगमता से गणना की जा सकती है, चूंकि इसमें बड़ी मात्रा में मेमोरी लग सकती है। [[कॉलिंग कॉन्टेक्स्ट ट्री]] की सामान्यतः स्टेटिक रूप से गणना नहीं की जाती है, चूंकि एक बड़े प्रोग्राम के लिए इसमें बहुत अधिक समय लगेगा। कम से कम सटीक कॉल ग्राफ़ संदर्भ-असंवेदनशील है, जिसका अर्थ है कि प्रत्येक प्रक्रिया के लिए एकमात्र नोड है। | सटीकता की अलग-अलग डिग्री का प्रतिनिधित्व करने के लिए कॉल ग्राफ़ को परिभाषित किया जा सकता है। अधिक सटीक कॉल ग्राफ़ अधिक सटीक रूप से वास्तविक प्रोग्राम के व्यवहार का अनुमान लगाता है, गणना करने में अधिक समय लेने और स्टोर करने के लिए अधिक मेमोरी की योग्यता पर। सबसे सटीक कॉल ग्राफ़ पूरी तरह से संदर्भ-संवेदनशील है, जिसका अर्थ है कि प्रत्येक प्रक्रिया के लिए, ग्राफ़ में प्रत्येक [[कॉल स्टैक]] के लिए एक अलग नोड होता है जिसके साथ प्रक्रिया को सक्रिय किया जा सकता है। एक पूरी तरह से संदर्भ-संवेदनशील कॉल ग्राफ़ को कॉलिंग संदर्भ ट्री कहा जाता है। इसकी गतिशील रूप से सुगमता से गणना की जा सकती है, चूंकि इसमें बड़ी मात्रा में मेमोरी लग सकती है। [[कॉलिंग कॉन्टेक्स्ट ट्री]] की सामान्यतः स्टेटिक रूप से गणना नहीं की जाती है, चूंकि एक बड़े प्रोग्राम के लिए इसमें बहुत अधिक समय लगेगा। कम से कम सटीक कॉल ग्राफ़ संदर्भ-असंवेदनशील है, जिसका अर्थ है कि प्रत्येक प्रक्रिया के लिए एकमात्र नोड है। | ||
उन भाषाओं के साथ जिनमें [[गतिशील प्रेषण]] ( | उन भाषाओं के साथ जिनमें [[गतिशील प्रेषण]] (अर्थात [[Index.php?title=जावा|जावा]] या C ++) है,<ref name=":0">{{cite journal |last1=Grove |first1=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> प्रथम श्रेणी के कार्य (अर्थात [[Index.php?title=पायथन|पायथन]] या [[Index.php?title=रैकेट|रैकेट]]), या [[फंक्शन पॉइंटर]] (अर्थात [[Index.php?title=सी|सी]]), की सुविधा देने वाली भाषाओं के साथ, एक स्थिर कॉल ग्राफ़ की गणना करने के लिए सटीक रूप से उपनाम विश्लेषण परिणामों की आवश्यकता होती है। इसके विपरीत, सटीक उपघटन की गणना करने के लिए कॉल ग्राफ़ की आवश्यकता होती है। कई स्थैतिक विश्लेषण प्रणालियाँ एक साथ दोनों की गणना करके स्पष्ट अनंत प्रतिगमन को हल करती हैं। | ||
== उपयोग == | == उपयोग == | ||
कॉल ग्राफ़ का उपयोग विभिन्न | कॉल ग्राफ़ का उपयोग विभिन्न पद्यतियों से किया जा सकता है। कॉल ग्राफ़ का एक सरल अनुप्रयोग उन प्रक्रियाओं को ढूंढ रहा है जिन्हें कभी नहीं बुलाया जाता है। कॉल ग्राफ़ मनुष्यों के लिए प्रोग्राम की समझ के लिए प्रलेखन के रूप में कार्य कर सकते हैं।<ref>{{cite journal |last1=Eisenbarth |first1=T. |last2=Koschke |first2=R. |last3=Simon |first3=D. |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|year=2001 |isbn=0-7695-1189-9 }}</ref> प्रोग्राम निष्पादन या अंतः क्षेपण आक्षेपों की विसंगतियों का पता लगाने के लिए कॉल ग्राफ़ का भी उपयोग किया जा सकता है।<ref>{{cite book |last1=Gao |first1=Debin |title=Proceedings of the 11th ACM conference on Computer and communications security - CCS '04 |last2=Reiter |first2=Michael K. |last3=Song |first3=Dawn |chapter=Gray-box extraction of execution graphs for anomaly detection |date=25 October 2004 |pages=318–329 |doi=10.1145/1030083.1030126|publisher=ACM|isbn=1581139616 }}</ref> | ||
Revision as of 20:31, 27 February 2023
कॉल ग्राफ़ (जिसे कॉल मल्टीग्राफ़ के रूप में भी जाना जाता है[1][2]) एक नियंत्रण-प्रवाह ग्राफ है,[3] जो एक कंप्यूटर प्रोग्राम में सबरूटीन्स के बीच कॉलिंग संबंधों का प्रतिनिधित्व करता है। प्रत्येक नोड एक प्रक्रिया का प्रतिनिधित्व करता है और प्रत्येक किनारे (एफ, जी) इंगित करता है कि प्रक्रिया एफ कॉल प्रक्रिया जी। इस प्रकार, ग्राफ में एक चक्र (ग्राफ सिद्धांत) पुनरावर्ती प्रक्रिया कॉल को इंगित करता है।
बुनियादी अवधारणाएँ
कॉल ग्राफ़ गतिशील या स्थिर हो सकते हैं।[4] डायनेमिक कॉल ग्राफ़ प्रोग्राम के निष्पादन का एक रिकॉर्ड है, उदाहरण के लिए एक प्रोफाइलर द्वारा आउटपुट के रूप में। इस प्रकार, एक डायनेमिक कॉल ग्राफ़ सटीक हो सकता है, परंतु एकमात्र प्रोग्राम के एक रन का वर्णन करता है। एक स्थिर कॉल ग्राफ़ जिसका उद्देश्य प्रोग्राम के हर संभव रन का प्रतिनिधित्व करना है। सटीक स्थैतिक कॉल ग्राफ़ एक अनिर्णीत समस्या है, इसलिए स्थैतिक कॉल ग्राफ़ एल्गोरिदम सामान्यतः अतिरेक हैं। अर्थात्, होने वाले प्रत्येक कॉल संबंध को ग्राफ़ में दर्शाया जाता है, और संभवतः कुछ कॉल संबंध भी होते हैं जो प्रोग्राम के वास्तविक रन में कभी नहीं होंगे।
सटीकता की अलग-अलग डिग्री का प्रतिनिधित्व करने के लिए कॉल ग्राफ़ को परिभाषित किया जा सकता है। अधिक सटीक कॉल ग्राफ़ अधिक सटीक रूप से वास्तविक प्रोग्राम के व्यवहार का अनुमान लगाता है, गणना करने में अधिक समय लेने और स्टोर करने के लिए अधिक मेमोरी की योग्यता पर। सबसे सटीक कॉल ग्राफ़ पूरी तरह से संदर्भ-संवेदनशील है, जिसका अर्थ है कि प्रत्येक प्रक्रिया के लिए, ग्राफ़ में प्रत्येक कॉल स्टैक के लिए एक अलग नोड होता है जिसके साथ प्रक्रिया को सक्रिय किया जा सकता है। एक पूरी तरह से संदर्भ-संवेदनशील कॉल ग्राफ़ को कॉलिंग संदर्भ ट्री कहा जाता है। इसकी गतिशील रूप से सुगमता से गणना की जा सकती है, चूंकि इसमें बड़ी मात्रा में मेमोरी लग सकती है। कॉलिंग कॉन्टेक्स्ट ट्री की सामान्यतः स्टेटिक रूप से गणना नहीं की जाती है, चूंकि एक बड़े प्रोग्राम के लिए इसमें बहुत अधिक समय लगेगा। कम से कम सटीक कॉल ग्राफ़ संदर्भ-असंवेदनशील है, जिसका अर्थ है कि प्रत्येक प्रक्रिया के लिए एकमात्र नोड है।
उन भाषाओं के साथ जिनमें गतिशील प्रेषण (अर्थात जावा या C ++) है,[5] प्रथम श्रेणी के कार्य (अर्थात पायथन या रैकेट), या फंक्शन पॉइंटर (अर्थात सी), की सुविधा देने वाली भाषाओं के साथ, एक स्थिर कॉल ग्राफ़ की गणना करने के लिए सटीक रूप से उपनाम विश्लेषण परिणामों की आवश्यकता होती है। इसके विपरीत, सटीक उपघटन की गणना करने के लिए कॉल ग्राफ़ की आवश्यकता होती है। कई स्थैतिक विश्लेषण प्रणालियाँ एक साथ दोनों की गणना करके स्पष्ट अनंत प्रतिगमन को हल करती हैं।
उपयोग
कॉल ग्राफ़ का उपयोग विभिन्न पद्यतियों से किया जा सकता है। कॉल ग्राफ़ का एक सरल अनुप्रयोग उन प्रक्रियाओं को ढूंढ रहा है जिन्हें कभी नहीं बुलाया जाता है। कॉल ग्राफ़ मनुष्यों के लिए प्रोग्राम की समझ के लिए प्रलेखन के रूप में कार्य कर सकते हैं।[6] प्रोग्राम निष्पादन या अंतः क्षेपण आक्षेपों की विसंगतियों का पता लगाने के लिए कॉल ग्राफ़ का भी उपयोग किया जा सकता है।[7]
सॉफ्टवेयर
मुफ्त सॉफ्टवेयर कॉल ग्राफ़ जेनरेटर
रन-टाइम कॉल ग्राफ़ (सूचीबद्ध अधिकांश उपकरण कॉल ग्राफ़ कार्यक्षमता वाले प्रोफाइलर हैं)
- gprof : बीएसडी या जीएनयू बाइनरी यूटिलिटीज के हिस्से में शामिल
- कॉलग्रिंड : चुनाव द्वार का हिस्सा
- KCachegrind : कॉलग्रिंड द्वारा उत्पन्न डेटा के आधार पर कॉल ग्राफ़ बनाने और उनका विश्लेषण करने के लिए शक्तिशाली उपकरण
- मैक ओएस एक्स एक्टिविटी मॉनिटर: ऐप्पल जीयूआई प्रोसेस मॉनिटर एक्टिविटी मॉनिटर में एक अंतर्निहित कॉल ग्राफ़ जनरेटर है जो प्रक्रियाओं का नमूना ले सकता है और कॉल ग्राफ़ वापस कर सकता है। यह फ़ंक्शन केवल Mac OS X Leopard में उपलब्ध है
- ओपनपैट : इसमें शामिल है
control_flowउपकरण जो रनटाइम मापन से स्वचालित रूप से ग्राफ विज़ुअलाइज़ेशन कॉल-ग्राफ़ चित्र बनाता है। - pprof, प्रोफ़ाइल डेटा के विज़ुअलाइज़ेशन और विश्लेषण के लिए ओपन सोर्स टूल, //gperftools.googlecode.com/git/doc/cpuprofile.html gperftools।
- एएमडी से कोड विश्लेषक (जीपीएल के तहत जारी)
- makeppgraph मेक (सॉफ़्टवेयर)#आधुनिक संस्करणों के साथ किए गए बिल्ड के लिए एक निर्भरता ग्राफ़ जेनरेटर (मॉड्यूल स्तर पर) है।
- Intel(R) सिंगल इवेंट एपीआई (मुफ्त, ओपन-सोर्स)
एप्लिकेशन चलाए बिना कॉल ग्राफ़ प्राप्त करने के लिए स्थिर
- सी/सी ++
- सोर्सट्रेल एक स्थिर कॉल ग्राफ बनाता है, जिसे उपयोगकर्ता द्वारा गतिशील रूप से खोजा जा सकता है। पायथन और जावा का भी समर्थन करता है
- doxygen : स्टैटिक कॉल/इनहेरिटेंस डायग्राम जेनरेट करने के लिए ग्राफविज का उपयोग करता है
- GNU cflow : GNU cflow एक C प्रोग्राम का डायरेक्ट और इनवर्टेड कॉल ग्राफ़ उत्पन्न करने में सक्षम है
- egypt : एक छोटी सी पर्ल स्क्रिप्ट जो सी प्रोग्राम के स्टेटिक कॉल ग्राफ को उत्पन्न करने के लिए जीसीसी और ग्रप्ह्वइज़ का उपयोग करती है।
- एनालिज़ो: स्रोत कोड मेट्रिक्स की गणना करता है, निर्भरता ग्राफ उत्पन्न करता है।
- CCTree : नेटिव विम (पाठ संपादक) प्लगइन जो cscope डेटाबेस को पढ़कर स्टेटिक कॉल ग्राफ़ प्रदर्शित कर सकता है। सी कार्यक्रमों के लिए काम करता है।
- codeviz : एक स्थिर कॉल ग्राफ जनरेटर (कार्यक्रम नहीं चलाया जाता है)। जीएनयू कंपाइलर संग्रह के पैच के रूप में लागू किया गया; सी और सी ++ प्रोग्राम के लिए काम करता है।
- calltree.sh : बैश शेल फंक्शंस जो सीस्कोप, ग्राफविज़ और डॉट-रेंडरिंग टूल्स के नमूने को एक साथ जोड़ते हैं ऊपर, नीचे, और/या आपके द्वारा निर्दिष्ट सी कार्यों के बीच कॉलर और कैली संबंधों को प्रदर्शित करने के लिए।
- tceetree : calltree.sh की तरह, यह Cscope और Graphviz को जोड़ता है, लेकिन यह बैश स्क्रिप्ट के बजाय निष्पादन योग्य है।
- जाना
- go-callvis : गो प्रोग्राम के लिए एक इंटरैक्टिव कॉल ग्राफ़ जनरेटर जिसका आउटपुट ग्राफ़विज़ के साथ खींचा जा सकता है
बहु भाषा
- callGraph : ऑक, बैश, बेसिक, डार्ट, फोरट्रान, गो, लुआ, जावास्क्रिप्ट, जूलिया, कोटलिन, मैटलैब, पर्ल, पास्कल, पीएचपी के लिए ओपन-सोर्स कॉल ग्राफ जेनरेटर , अजगर, आर, राकू, रूबी, रस्ट, स्काला, स्विफ्ट, टीसीएल और टाइपस्क्रिप्ट।
- ।जाल
- NDepend : .NET कोड के लिए एक स्थिर विश्लेषण टूल है। यह उपकरण बड़ी संख्या में कोड मेट्रिक्स का समर्थन करता है, निर्देशित ग्राफ़ और निर्भरता मैट्रिक्स का उपयोग करके निर्भरता के विज़ुअलाइज़ेशन की अनुमति देता है।
PHP, पर्ल और पायथन
- Devel::NYTProf : एक पर्ल प्रदर्शन विश्लेषक और कॉल चार्ट जनरेटर
- phpCallGraph : PHP प्रोग्राम के लिए एक कॉल ग्राफ़ जनरेटर जो ग्राफ़विज़ का उपयोग करता है। यह PHP में लिखा गया है और इसके लिए कम से कम PHP 5.2 की आवश्यकता है।
- pycallgraph : पायथन प्रोग्राम के लिए एक कॉल ग्राफ़ जनरेटर जो ग्राफ़विज़ का उपयोग करता है।
- pyan : ग्राफ़विज़ का उपयोग करने वाले पायथन प्रोग्राम के लिए एक स्थिर कॉल ग्राफ़ जनरेटर।
- gprof2dot : पायथन में लिखा गया एक कॉल ग्राफ़ जनरेटर जो कई भाषाओं/रनटाइम्स के लिए प्रोफाइलिंग डेटा को ग्राफ़विज़ कॉलग्राफ़ में परिवर्तित करता है।
- code2flow: पायथन और जावास्क्रिप्ट प्रोग्राम के लिए एक कॉल ग्राफ़ जनरेटर जो ग्राफ़विज़ का उपयोग करता है
- rcviz : ग्राफ़विज़ के साथ रनटाइम-जेनरेट किए गए कॉल ग्राफ़ को प्रस्तुत करने के लिए पायथन मॉड्यूल। प्रत्येक नोड एक फ़ंक्शन के आह्वान का प्रतिनिधित्व करता है जिसमें इसे पास किए गए पैरामीटर और वापसी मान होता है।
- XQuery
- XQuery Wikibook से XQuery कॉल ग्राफ़: XQuery फ़ंक्शन मॉड्यूल के लिए एक कॉल ग्राफ़ जनरेटर जो ग्राफ़विज़ का उपयोग करता है
मालिकाना कॉल ग्राफ जनरेटर
- एलडीआरए टेस्टबेड
- कॉल ग्राफ़ सहित असंख्य रिपोर्ट के साथ होस्ट और एम्बेडेड सॉफ़्टवेयर दोनों के लिए स्थिर और गतिशील विश्लेषण इंजन।
- परियोजना विश्लेषक
- विजुअल बेसिक कोड के लिए स्टेटिक कोड एनालाइजर और कॉल ग्राफ जनरेटर
- दृश्य विशेषज्ञ
- Oracle डेटाबेस PL/SQL, Microsoft SQL Server Transact-SQL, C Sharp (प्रोग्रामिंग लैंग्वेज)|C# और PowerBuilder कोड के लिए स्थैतिक कार्यक्रम विश्लेषण और कॉल ग्राफ़ जनरेटर
- VTune
- कॉल ग्राफ़ और निष्पादन आँकड़े दिखाने के लिए इंस्ट्रूमेंटिंग प्रोफाइलर
- डीएमएस सॉफ्टवेयर रीइंजीनियरिंग टूलकिट
- सी, जावा और कोबोल के लिए स्थिर पूरे कार्यक्रम वैश्विक कॉल ग्राफ निष्कर्षण के साथ अनुकूलन कार्यक्रम विश्लेषण उपकरण
अन्य, संबंधित उपकरण
- ग्राफ़विज़
- किसी भी ग्राफ़ (कॉल ग्राफ़ सहित) के पाठ प्रतिनिधित्व को चित्र में बदल देता है।
- tsort
- कमांड-लाइन यूटिलिटी जो एक टोपोलॉजिकल सॉर्ट करती है।
नमूना ग्राफ
स्वयं का विश्लेषण करने वाले gprof से उत्पन्न एक नमूना कॉल ग्राफ़: <पूर्व> इंडेक्स कॉल्ड नेम | इंडेक्स कॉल्ड नेम
72384/72384 sym_id_parse [54] | 1508/1508 सीजी_डीएफएन [15]
[3] 72384 मैच [3] |[13] 1508 प्री_विजिट [13]
|-------------------------------------
4/9052 सीजी_टैली [32] | 1508/1508 cg_इकट्ठा करना [38]
3016/9052 इतिहास_प्रिंट [49] | [14] 1508 प्रचार_समय [14]
6032/9052 प्रचार_झंडे [52] |----------------------
[4] 9052 सिम्_लुकअप [4] | 2 सीजी_डीएफएन [15]
| 1507/1507 cg_इकट्ठा करना [38]
5766/5766 core_create_function_syms [41]|[15] 1507+2 cg_dfn [15]
[5] 5766 कोर_सिम_क्लास [5] | 1509/1509_क्रमांकित है [9]
| 1508/1508 व्यस्त है [11]
24/1537 पार्स_स्पेक [19] | 1508/1508 यात्रा से पहले [13]
1513/1537 core_create_function_syms [41] | 1508/1508 यात्रा के बाद [12]
[6] 1537 सिम्_इनिट [6] | 2 सीजी_डीएफएन [15]
|-------------------------------------
1511/1511 core_create_function_syms [41] | 1505/1505 इतिहास_प्रिंट [49]
[7] 1511 get_src_info [7] |[16] 1505 प्रिंट_लाइन [16]
| 2/9 प्रिंट_नाम_ओनली [25]
2/1510 आर्क_एड [31] |----------------------
1508/1510 cg_assembly [38] | 1430/1430 core_create_function_syms [41]
[8] 1510 आर्क_लुकअप [8] |[17] 1430 स्रोत_फाइल_लुकअप_पथ [17]
|-------------------------------------
1509/1509 सीजी_डीएफएन [15] | 24/24 sym_id_parse [54]
[9] 1509 संख्याबद्ध है [9] |[18] 24 पार्स_आईडी [18]
| 24/24 पार्स_स्पेक [19]
1508/1508 प्रचार_झंडे [52] |----------------------
[10] 1508 इनहेरिट_फ्लैग्स [10] | 24/24 पार्स_आईडी [18]
|[19] 24 पार्स_स्पेक [19]
1508/1508 सीजी_डीएफएन [15] | 24/1537 सिम्_इनिट [6]
[11] 1508 व्यस्त है [11] |-------------------------------------
| 24/24 मुख्य [1210]
1508/1508 cg_dfn [15] |[20] 24 sym_id_add [20]
[12] 1508 पोस्ट_विजिट [12] | </पूर्व>
यह भी देखें
संदर्भ
- ↑ 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.
- ↑ Uday Khedker; Amitabha Sanyal; Bageshri Sathe (2009). Data Flow Analysis: Theory and Practice. CRC Press. p. 234. ISBN 978-0-8493-3251-7.
- ↑ Pankaj Jalote (1997). An Integrated Approach to Software Engineering. Springer Science & Business Media. p. 372. ISBN 978-0-387-94899-7.
- ↑ 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.
- ↑ 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.
