सूचक विश्लेषण

कंप्यूटर विज्ञान में, पॉइंटर विश्लेषण, या पॉइंट-टू-एनालिसिस, एक स्थिर कोड विश्लेषण तकनीक है जो यह निर्धारित करती है कि कौन से सूचक (कंप्यूटर प्रोग्रामिंग) या ढेर संदर्भ, किस चर या भंडारण स्थानों को इंगित कर सकते हैं। यह अक्सर अधिक जटिल विश्लेषणों जैसे पलायन विश्लेषण का एक घटक होता है। एक निकट संबंधी तकनीक आकार विश्लेषण (सॉफ्टवेयर) है।

(यह शब्द का सबसे आम बोलचाल का उपयोग है। एक द्वितीयक उपयोग में 'पॉइंटर एनालिसिस 'पॉइंट-टू-एनालिसिस दोनों के लिए सामूहिक नाम है, जिसे ऊपर के रूप में परिभाषित किया गया है, और उपनाम विश्लेषण। पॉइंट्स-टू और अलियास विश्लेषण निकटता से संबंधित हैं लेकिन हमेशा समतुल्य समस्याएं नहीं हैं।)

उदाहरण

निम्नलिखित उदाहरण कार्यक्रम के लिए, अंक-टू-विश्लेषण यह गणना करेगा कि अंक-टू-सेट p है {x, y}.

<वाक्यविन्यास प्रकाश लैंग = सी> इंट एक्स; इंट वाई; int * पी = अज्ञात ()? & एक्स : और वाई; </वाक्यविन्यास हाइलाइट>

परिचय

स्थैतिक विश्लेषण के एक रूप के रूप में, पूरी तरह से सटीक सूचक विश्लेषण को अनिर्णीत समस्या के रूप में दिखाया जा सकता है। अधिकांश दृष्टिकोण ध्वनि हैं, लेकिन व्यापक रूप से प्रदर्शन और सटीकता में हैं। कई डिजाइन निर्णय विश्लेषण की सटीकता और प्रदर्शन दोनों को प्रभावित करते हैं; अक्सर (लेकिन हमेशा नहीं) कम सटीकता से उच्च प्रदर्शन प्राप्त होता है। इन विकल्पों में शामिल हैं:

• क्षेत्र संवेदनशीलता (संरचना संवेदनशीलता के रूप में भी जाना जाता है): एक विश्लेषण या तो एक रिकॉर्ड (कंप्यूटर विज्ञान) या वस्तु (कंप्यूटर विज्ञान) के प्रत्येक क्षेत्र को अलग से देख सकता है, या उन्हें मर्ज कर सकता है।
• ऐरे सेंसिटिविटी: एक एरे-सेंसिटिव पॉइंटर एनालिसिस प्रत्येक इंडेक्स को अलग-अलग एरे में मॉडल करता है। अन्य विकल्पों में केवल पहली प्रविष्टि को अलग से और बाकी को एक साथ मॉडलिंग करना, या सभी सरणी प्रविष्टियों को मर्ज करना शामिल है।
• संदर्भ संवेदनशीलता: सूचक विश्लेषण प्रत्येक कार्यक्रम बिंदु पर जाने वाले नियंत्रण प्रवाह के सारांश के साथ सूचना के बिंदुओं को अर्हता प्राप्त कर सकता है।
• फ्लो सेंसिटिविटी: एक विश्लेषण पॉइंट टू फैक्ट्स पर इंट्राप्रोसेरल कंट्रोल फ्लो के प्रभाव को मॉडल कर सकता है।
• हीप मॉडलिंग: रन-टाइम आबंटन को इसके द्वारा अमूर्त किया जा सकता है:
  • उनकी आवंटन साइटें (बयान या निर्देश जो आवंटन करता है, उदाहरण के लिए, एक कॉल malloc या एक वस्तु निर्माता),
  • आकार विश्लेषण (सॉफ्टवेयर) पर आधारित एक अधिक जटिल मॉडल,
  • आवंटन का प्रकार, या
  • एक एकल आवंटन (इसे हीप-असंवेदनशीलता कहा जाता है)।
• हीप क्लोनिंग: हीप- और संदर्भ-संवेदी विश्लेषण प्रत्येक आवंटन साइट को नियंत्रण प्रवाह के सारांश द्वारा निर्देश या कथन को पूरा करने वाले कथन के लिए अग्रणी बना सकते हैं।
• उपसमुच्चय बाधाएँ या समानता बाधाएँ: जब तथ्यों के बिंदुओं का प्रचार किया जाता है, तो विभिन्न प्रोग्राम स्टेटमेंट एक चर के बिंदुओं से सेटों पर विभिन्न बाधाओं को प्रेरित कर सकते हैं। समानता की कमी (जैसे स्टीन्सगार्ड के एल्गोरिथ्म में उपयोग की जाने वाली) को एक संघ-खोज डेटा संरचना के साथ ट्रैक किया जा सकता है, जिससे एक सबसेट-बाधा आधारित विश्लेषण (जैसे, एंडरसन के एल्गोरिथ्म) की सटीकता की कीमत पर उच्च प्रदर्शन हो सकता है।

संदर्भ-असंवेदनशील, प्रवाह-असंवेदनशील एल्गोरिदम

सूचक विश्लेषण एल्गोरिदम का उपयोग एकत्रित कच्चे सूचक उपयोगों (एक सूचक को दूसरे के लिए असाइनमेंट या एक सूचक को दूसरे को इंगित करने के लिए असाइन करना) को एक उपयोगी ग्राफ में परिवर्तित करने के लिए किया जाता है जो प्रत्येक सूचक को इंगित कर सकता है। स्टेन्सगार्ड के एल्गोरिथ्म और एंडरसन के एल्गोरिथ्म सूचक विश्लेषण के लिए सामान्य संदर्भ-असंवेदनशील, प्रवाह-असंवेदनशील एल्गोरिदम हैं। वे अक्सर कंपाइलर्स में उपयोग किए जाते हैं, और एलएलवीएम कोडबेस में कार्यान्वयन होते हैं।

प्रवाह-असंवेदनशील दृष्टिकोण

प्रवाह-असंवेदनशील सूचक विश्लेषण के कई दृष्टिकोणों को अमूर्त व्याख्या के रूपों के रूप में समझा जा सकता है, जहां हीप आवंटन को उनके आवंटन स्थल (यानी, एक कार्यक्रम स्थान) द्वारा सारित किया जाता है।

फ्लो-असंवेदनशील सूचक विश्लेषण अक्सर उनके आवंटन साइट द्वारा संभावित रनटाइम आवंटन का सार करता है। रनटाइम पर, यह प्रोग्राम तीन अलग-अलग ढेर आवंटन बनाता है। एक प्रवाह-असंवेदनशील सूचक विश्लेषण इन्हें एकल अमूर्त स्मृति स्थान के रूप में मानेगा, जिससे परिशुद्धता का नुकसान होगा।

कई प्रवाह-असंवेदनशील एल्गोरिदम को Datalog में निर्दिष्ट किया गया है, जिसमें जावा के लिए सूट विश्लेषण ढांचे में शामिल हैं।

संदर्भ-संवेदनशील, प्रवाह-असंवेदनशील एल्गोरिदम उच्च परिशुद्धता प्राप्त करते हैं, आम तौर पर कुछ प्रदर्शन की कीमत पर, प्रत्येक प्रक्रिया का कई बार विश्लेषण करके, संदर्भ के अनुसार एक बार। अधिकांश विश्लेषण संदर्भ-स्ट्रिंग दृष्टिकोण का उपयोग करते हैं, जहां संदर्भों में प्रविष्टियों की एक सूची होती है (संदर्भ प्रविष्टि के सामान्य विकल्पों में कॉल साइट्स, आवंटन साइट्स और प्रकार शामिल हैं)। समाप्ति (और अधिक सामान्यतः, स्केलेबिलिटी) सुनिश्चित करने के लिए, ऐसे विश्लेषण आम तौर पर एक के-सीमित दृष्टिकोण का उपयोग करते हैं, जहां संदर्भ में एक निश्चित अधिकतम आकार होता है, और कम से कम हाल ही में जोड़े गए तत्वों को आवश्यकतानुसार हटा दिया जाता है। संदर्भ-संवेदनशील, प्रवाह-असंवेदनशील विश्लेषण के तीन सामान्य प्रकार हैं:

• कॉल-साइट संवेदनशीलता
• वस्तु संवेदनशीलता
• संवेदनशीलता टाइप करें

कॉल-साइट संवेदनशीलता

कॉल-साइट संवेदनशीलता में, प्रत्येक वेरिएबल के पॉइंट-टू सेट (अमूर्त ढेर आवंटन का सेट प्रत्येक वेरिएबल को इंगित कर सकता है) कार्यक्रम में कॉलसाइट्स की एक सूची से युक्त एक संदर्भ द्वारा आगे योग्य है। ये संदर्भ कार्यक्रम के नियंत्रण-प्रवाह को अमूर्त करते हैं।

निम्नलिखित कार्यक्रम दर्शाता है कि कैसे कॉल-साइट संवेदनशीलता प्रवाह-असंवेदनशील, संदर्भ-असंवेदनशील विश्लेषण की तुलना में उच्च सटीकता प्राप्त कर सकती है। <वाक्यविन्यास प्रकाश लैंग = सी> इंट * आईडी (इंट * एक्स) {

 वापसी एक्स;

} मुख्य प्रवेश बिंदु() {

 इंट वाई;
 इंट जेड;
 int *y2 = आईडी (और वाई); // कॉल-साइट 1
 int *z2 = आईडी (&z); // कॉल-साइट 2
 वापसी 0;

} </वाक्यविन्यास हाइलाइट> इस कार्यक्रम के लिए, एक संदर्भ-असंवेदनशील विश्लेषण (ध्वनिपूर्ण लेकिन अस्पष्ट रूप से) यह निष्कर्ष निकालेगा x या तो आवंटन होल्डिंग को इंगित कर सकता है y या वह z, इसलिए y2 और z2 may उर्फ, और दोनों या तो आवंटन की ओर इशारा कर सकते हैं। एक कॉलसाइट-संवेदनशील विश्लेषण विश्लेषण करेगा id दो बार, एक बार कॉल-साइट 1 के लिए और एक बार कॉल-साइट 2 के लिए, और पॉइंट-टू फैक्ट्स के लिए x कॉल-साइट द्वारा योग्य होगा, विश्लेषण को सक्षम करने के लिए कि कब main लौटता है, y2 केवल आवंटन होल्डिंग को इंगित कर सकता है y और z2 केवल आवंटन होल्डिंग को इंगित कर सकता है z.

वस्तु संवेदनशीलता

ऑब्जेक्ट सेंसिटिव एनालिसिस में, प्रत्येक वेरिएबल के पॉइंट-टू सेट को मेथड कॉल के रिसीवर ऑब्जेक्ट के एब्स्ट्रैक्ट हीप एलोकेशन द्वारा क्वालिफाई किया जाता है। कॉल-साइट संवेदनशीलता के विपरीत, वस्तु-संवेदनशीलता गैर-वाक्यविन्यास या गैर-स्थानीय है: संदर्भ प्रविष्टियां पॉइंट-टू-विश्लेषण के दौरान ही प्राप्त की जाती हैं।

टाइप संवेदनशीलता

टाइप सेंसिटिविटी ऑब्जेक्ट सेंसिटिविटी का एक प्रकार है जहां रिसीवर ऑब्जेक्ट की आवंटन साइट को उस वर्ग/प्रकार से बदल दिया जाता है जिसमें रिसीवर ऑब्जेक्ट की आवंटन साइट वाली विधि होती है। इसका परिणाम वस्तु-संवेदनशील विश्लेषण में उपयोग किए जाने वाले संदर्भों की तुलना में बहुत कम संदर्भों में होता है, जिसका आमतौर पर बेहतर प्रदर्शन होता है।

ग्रन्थसूची

• Zyrianov, Vlas; Newman, Christian D.; Guarnera, Drew T.; Collard, Michael L.; Maletic, Jonathan I. (2019). "srcPtr: A Framework for Implementing Static Pointer Analysis Approaches" (PDF). ICPC '19: Proceedings of the 27th IEEE International Conference on Program Comprehension. Montreal, Canada: IEEE.
• Smaragdakis, Yannis; Balatsouras, George (2015). "Pointer Analysis" (PDF). Foundations and Trends in Programming Languages. 2 (1): 1–69. doi:10.1561/2500000014. Retrieved May 30, 2019.
• Li, Yue; Tan/, Tian; Møller, Anders; Smaragdakis, Yannis (2020-05-18). "A Principled Approach to Selective Context Sensitivity for Pointer Analysis". ACM Transactions on Programming Languages and Systems. 42 (2): 10:1–10:40. doi:10.1145/3381915. ISSN 0164-0925. S2CID 214812357.
• Michael Hind (2001). "Pointer analysis: haven't we solved this problem yet?" (PDF). PASTE '01: Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering. ACM. pp. 54–61. ISBN 1-58113-413-4.
• Steensgaard, Bjarne (1996). "Points-to analysis in almost linear time" (PDF). POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. New York, NY, USA: ACM. pp. 32–41. doi:10.1145/237721.237727. ISBN 0-89791-769-3.
• Andersen, Lars Ole (1994). Program Analysis and Specialization for the C Programming Language (PDF) (PhD thesis).