सूचक विश्लेषण: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[कंप्यूटर विज्ञान]] में, सूचक विश्लेषण, या बिंदु विश्लेषण, एक [[स्थिर कोड विश्लेषण]] तकनीक है जो यह निर्धारित करती है कि कौन से [[सूचक (कंप्यूटर प्रोग्रामिंग)]], या हीप संदर्भ, किस चर या भंडारण स्थानों को इंगित कर सकते हैं। यह | [[कंप्यूटर विज्ञान]] में, सूचक विश्लेषण, या बिंदु विश्लेषण, एक [[स्थिर कोड विश्लेषण]] तकनीक है जो यह निर्धारित करती है कि कौन से [[सूचक (कंप्यूटर प्रोग्रामिंग)]], या हीप संदर्भ, किस चर या भंडारण स्थानों को इंगित कर सकते हैं। यह अधिकांशतः अधिक जटिल विश्लेषणों जैसे पलायन [[विश्लेषण]] का एक घटक होता है। एक निकट संबंधी तकनीक [[आकृति]] [[आकार विश्लेषण (सॉफ्टवेयर)|विश्लेषण (सॉफ्टवेयर)]] है। | ||
(यह शब्द का सबसे | (यह शब्द का सबसे सामान्य बोलचाल का उपयोग है, एक द्वितीयक उपयोग में सूचक विश्लेषण दोनों बिंदु विश्लेषण के लिए सामूहिक नाम और उपनाम विश्लेषण है, जैसा कि ऊपर परिभाषित किया गया है, बिंदु और अलियास विश्लेषण बारीकी से संबंधित हैं लेकिन इसमें निरंतर समान समस्याएं नहीं होती हैं। | ||
== उदाहरण == | == उदाहरण == | ||
| Line 12: | Line 12: | ||
== परिचय == | == परिचय == | ||
स्थैतिक विश्लेषण के रूप में, पूर्ण रूप से | स्थैतिक विश्लेषण के रूप में, पूर्ण रूप से त्रुटिहीन सूचक विश्लेषण को [[अनिर्णीत समस्या]] के रूप में दिखाया जा सकता है।<ref>{{Cite journal|last=Reps|first=Thomas|date=2000-01-01|title=Undecidability of context-sensitive data-dependence analysis|url=https://doi.org/10.1145/345099.345137|journal=ACM Transactions on Programming Languages and Systems|volume=22|issue=1|pages=162–186|doi=10.1145/345099.345137|s2cid=2956433|issn=0164-0925}}</ref> अधिकांश दृष्टिकोण में ध्वनि हैं, लेकिन व्यापक रूप से प्रदर्शन और त्रुटिहीनता की सीमा में हैं, कई डिजाइन निर्णय विश्लेषण की त्रुटिहीनता और प्रदर्शन दोनों को प्रभावित करते हैं; अधिकांशतः (लेकिन निरंतर नहीं) कम त्रुटिहीनता से उच्च प्रदर्शन प्राप्त होता है, और यह इन विकल्पों में सम्मलित हैं:<ref>{{cite conference | ||
| title=Dimensions of Precision in Reference Analysis of Object-Oriented Programming Languages | | title=Dimensions of Precision in Reference Analysis of Object-Oriented Programming Languages | ||
| author=Barbara G. Ryder | | author=Barbara G. Ryder | ||
| Line 21: | Line 21: | ||
}}</ref><ref>{{harv|Hind}}</ref> | }}</ref><ref>{{harv|Hind}}</ref> | ||
* क्षेत्र संवेदनशीलता (संरचना संवेदनशीलता के रूप में भी जाना जाता है): एक विश्लेषण या तो एक [[रिकॉर्ड (कंप्यूटर विज्ञान)]] या [[वस्तु (कंप्यूटर विज्ञान)|ऑब्जेक्ट (कंप्यूटर विज्ञान)]] के प्रत्येक क्षेत्र को भिन्न प्रकार से देख सकता है, या उन्हें मिला सकता है। | * क्षेत्र संवेदनशीलता (संरचना संवेदनशीलता के रूप में भी जाना जाता है): एक विश्लेषण या तो एक [[रिकॉर्ड (कंप्यूटर विज्ञान)]] या [[वस्तु (कंप्यूटर विज्ञान)|ऑब्जेक्ट (कंप्यूटर विज्ञान)]] के प्रत्येक क्षेत्र को भिन्न प्रकार से देख सकता है, या उन्हें मिला सकता है। | ||
* सरणी संवेदनशीलता: एक सरणी-संवेदनशीलता सूचक विश्लेषण प्रत्येक अनुक्रमणिका को भिन्न-भिन्न सरणी में | * सरणी संवेदनशीलता: एक सरणी-संवेदनशीलता सूचक विश्लेषण प्रत्येक अनुक्रमणिका को भिन्न-भिन्न सरणी में प्रतिरूप करता है। अन्य विकल्पों में सिर्फ पहली प्रविष्टि को भिन्न प्रकार से और बाकी को एक साथ मॉडलिंग करना, या सभी सरणी प्रविष्टियों को मिलाना सम्मलित होता है। | ||
*संदर्भ संवेदनशीलता या बहुभिन्नरूपी: सूचक विश्लेषण प्रत्येक प्रोग्राम बिंदु पर जाने वाले नियंत्रण प्रवाह के सारांश के साथ सूचना के | *संदर्भ संवेदनशीलता या बहुभिन्नरूपी: सूचक विश्लेषण प्रत्येक प्रोग्राम बिंदु पर जाने वाले नियंत्रण प्रवाह के सारांश के साथ सूचना के बिंदुओ को अर्हता प्राप्त करा सकता है। | ||
* प्रवाह संवेदनशीलता: एक विश्लेषण तथ्यों से | * प्रवाह संवेदनशीलता: एक विश्लेषण तथ्यों से बिंदुओ पर अंतराप्रक्रियात्मक नियंत्रण प्रवाह के प्रभाव को प्रतिरूप बना सकता है। | ||
* हीप मॉडलिंग: रन-टाइम आवंटन को इसके द्वारा अमूर्त किया जा सकता है: | * हीप मॉडलिंग: रन-टाइम आवंटन को इसके द्वारा अमूर्त किया जा सकता है: | ||
** उनकी आवंटन साइटें (विवरण या निर्देश जो आवंटन करता है, उदाहरण के लिए, मॉलोक या ऑब्जेक्ट कन्स्ट्रक्टर को कॉल), | ** उनकी आवंटन साइटें (विवरण या निर्देश जो आवंटन करता है, उदाहरण के लिए, मॉलोक या ऑब्जेक्ट कन्स्ट्रक्टर को कॉल), | ||
** आकृति विश्लेषण पर आधारित एक अधिक जटिल | ** आकृति विश्लेषण पर आधारित एक अधिक जटिल प्रतिरूप, | ||
** आवंटन का प्रकार, या | ** आवंटन का प्रकार, या | ||
** एक एकल आवंटन (इसे हीप-असंवेदनशीलता कहा जाता है)। | ** एक एकल आवंटन (इसे हीप-असंवेदनशीलता कहा जाता है)। | ||
* हीप क्लोनिंग: हीप | * हीप क्लोनिंग: हीप और संदर्भ संवेदनशील विश्लेषण प्रत्येक आवंटन साइट को नियंत्रण प्रवाह के सारांश द्वारा आवंटन को निष्पादित करने वाले निर्देश या कथन की ओर अग्रसर कर सकते हैं। | ||
* उपसमुच्चय बाधाएँ या समानता बाधाएँ: जब तथ्यों के बिंदुओं का प्रचार किया जाता है, तो विभिन्न प्रोग्राम विवरण एक चर के बिंदुओं से | * उपसमुच्चय बाधाएँ या समानता बाधाएँ: जब तथ्यों के बिंदुओं का प्रचार किया जाता है, तो विभिन्न प्रोग्राम विवरण एक चर के बिंदुओं से समुच्चयों पर विभिन्न बाधाओं को प्रेरित कर सकते हैं, समानता की कमी (जैसे स्टीन्सगार्ड के कलन विधि में उपयोग की जाने वाली) को एक [[संघ-खोज डेटा संरचना]] के साथ ट्रैक किया जा सकता है, जिससे एक उपसमुच्चय-बाधा आधारित विश्लेषण (जैसे, एंडरसन के कलन विधि) की शुद्धता की कीमत पर उच्च प्रदर्शन हो सकता है। | ||
== संदर्भ-असंवेदनशील, प्रवाह-असंवेदनशील कलन विधि == | == संदर्भ-असंवेदनशील, प्रवाह-असंवेदनशील कलन विधि == | ||
| Line 49: | Line 49: | ||
</ref> | </ref> | ||
स्टेन्सगार्ड के कलन विधि और एंडरसन के कलन विधि सूचक विश्लेषण के लिए सामान्य संदर्भ-असंवेदनशील, प्रवाह-असंवेदनशील कलन विधि हैं, वे | स्टेन्सगार्ड के कलन विधि और एंडरसन के कलन विधि सूचक विश्लेषण के लिए सामान्य संदर्भ-असंवेदनशील, प्रवाह-असंवेदनशील कलन विधि हैं, वे अधिकांशतः कंपाइलर्स में उपयोग किए जाते हैं, और [[एलएलवीएम]] कोडबेस में कार्यान्वयन होते हैं। | ||
== प्रवाह-असंवेदनशील दृष्टिकोण == | == प्रवाह-असंवेदनशील दृष्टिकोण == | ||
Revision as of 20:41, 1 March 2023
कंप्यूटर विज्ञान में, सूचक विश्लेषण, या बिंदु विश्लेषण, एक स्थिर कोड विश्लेषण तकनीक है जो यह निर्धारित करती है कि कौन से सूचक (कंप्यूटर प्रोग्रामिंग), या हीप संदर्भ, किस चर या भंडारण स्थानों को इंगित कर सकते हैं। यह अधिकांशतः अधिक जटिल विश्लेषणों जैसे पलायन विश्लेषण का एक घटक होता है। एक निकट संबंधी तकनीक आकृति विश्लेषण (सॉफ्टवेयर) है।
(यह शब्द का सबसे सामान्य बोलचाल का उपयोग है, एक द्वितीयक उपयोग में सूचक विश्लेषण दोनों बिंदु विश्लेषण के लिए सामूहिक नाम और उपनाम विश्लेषण है, जैसा कि ऊपर परिभाषित किया गया है, बिंदु और अलियास विश्लेषण बारीकी से संबंधित हैं लेकिन इसमें निरंतर समान समस्याएं नहीं होती हैं।
उदाहरण
निम्नलिखित प्रोग्राम के उदाहरण के लिए, बिंदु विश्लेषण यह गणना करता है की p का निर्धारित बिंदु {x, y} है।
int x;
int y;
int* p = unknown() ? &x : &y;
परिचय
स्थैतिक विश्लेषण के रूप में, पूर्ण रूप से त्रुटिहीन सूचक विश्लेषण को अनिर्णीत समस्या के रूप में दिखाया जा सकता है।[1] अधिकांश दृष्टिकोण में ध्वनि हैं, लेकिन व्यापक रूप से प्रदर्शन और त्रुटिहीनता की सीमा में हैं, कई डिजाइन निर्णय विश्लेषण की त्रुटिहीनता और प्रदर्शन दोनों को प्रभावित करते हैं; अधिकांशतः (लेकिन निरंतर नहीं) कम त्रुटिहीनता से उच्च प्रदर्शन प्राप्त होता है, और यह इन विकल्पों में सम्मलित हैं:[2][3]
- क्षेत्र संवेदनशीलता (संरचना संवेदनशीलता के रूप में भी जाना जाता है): एक विश्लेषण या तो एक रिकॉर्ड (कंप्यूटर विज्ञान) या ऑब्जेक्ट (कंप्यूटर विज्ञान) के प्रत्येक क्षेत्र को भिन्न प्रकार से देख सकता है, या उन्हें मिला सकता है।
- सरणी संवेदनशीलता: एक सरणी-संवेदनशीलता सूचक विश्लेषण प्रत्येक अनुक्रमणिका को भिन्न-भिन्न सरणी में प्रतिरूप करता है। अन्य विकल्पों में सिर्फ पहली प्रविष्टि को भिन्न प्रकार से और बाकी को एक साथ मॉडलिंग करना, या सभी सरणी प्रविष्टियों को मिलाना सम्मलित होता है।
- संदर्भ संवेदनशीलता या बहुभिन्नरूपी: सूचक विश्लेषण प्रत्येक प्रोग्राम बिंदु पर जाने वाले नियंत्रण प्रवाह के सारांश के साथ सूचना के बिंदुओ को अर्हता प्राप्त करा सकता है।
- प्रवाह संवेदनशीलता: एक विश्लेषण तथ्यों से बिंदुओ पर अंतराप्रक्रियात्मक नियंत्रण प्रवाह के प्रभाव को प्रतिरूप बना सकता है।
- हीप मॉडलिंग: रन-टाइम आवंटन को इसके द्वारा अमूर्त किया जा सकता है:
- उनकी आवंटन साइटें (विवरण या निर्देश जो आवंटन करता है, उदाहरण के लिए, मॉलोक या ऑब्जेक्ट कन्स्ट्रक्टर को कॉल),
- आकृति विश्लेषण पर आधारित एक अधिक जटिल प्रतिरूप,
- आवंटन का प्रकार, या
- एक एकल आवंटन (इसे हीप-असंवेदनशीलता कहा जाता है)।
- हीप क्लोनिंग: हीप और संदर्भ संवेदनशील विश्लेषण प्रत्येक आवंटन साइट को नियंत्रण प्रवाह के सारांश द्वारा आवंटन को निष्पादित करने वाले निर्देश या कथन की ओर अग्रसर कर सकते हैं।
- उपसमुच्चय बाधाएँ या समानता बाधाएँ: जब तथ्यों के बिंदुओं का प्रचार किया जाता है, तो विभिन्न प्रोग्राम विवरण एक चर के बिंदुओं से समुच्चयों पर विभिन्न बाधाओं को प्रेरित कर सकते हैं, समानता की कमी (जैसे स्टीन्सगार्ड के कलन विधि में उपयोग की जाने वाली) को एक संघ-खोज डेटा संरचना के साथ ट्रैक किया जा सकता है, जिससे एक उपसमुच्चय-बाधा आधारित विश्लेषण (जैसे, एंडरसन के कलन विधि) की शुद्धता की कीमत पर उच्च प्रदर्शन हो सकता है।
संदर्भ-असंवेदनशील, प्रवाह-असंवेदनशील कलन विधि
सूचक विश्लेषण कलन विधि का उपयोग एकत्रित कच्चे सूचक उपयोगों (एक सूचक को दूसरे के लिए असाइनमेंट या एक सूचक को दूसरे को इंगित करने के लिए असाइन करना) को एक उपयोगी ग्राफ में परिवर्तित करने के लिए किया जाता है जो प्रत्येक सूचक को इंगित कर सकता है।[4]
स्टेन्सगार्ड के कलन विधि और एंडरसन के कलन विधि सूचक विश्लेषण के लिए सामान्य संदर्भ-असंवेदनशील, प्रवाह-असंवेदनशील कलन विधि हैं, वे अधिकांशतः कंपाइलर्स में उपयोग किए जाते हैं, और एलएलवीएम कोडबेस में कार्यान्वयन होते हैं।
प्रवाह-असंवेदनशील दृष्टिकोण
प्रवाह-असंवेदनशील सूचक विश्लेषण के कई दृष्टिकोणों को अमूर्त व्याख्या के रूपों के रूप में समझा जा सकता है, जहां हीप आवंटन को उनके आवंटन स्थल (यानी, एक प्रोग्राम स्थान) द्वारा सारित किया जाता है।[5]
कई प्रवाह-असंवेदनशील कलन विधि को डेटा लॉग में निर्दिष्ट किया गया है, जिसमें जावा के लिए सूट विश्लेषण ढांचे में सम्मलित हैं।[6]
संदर्भ-संवेदनशील, प्रवाह-असंवेदनशील कलन विधि उच्च परिशुद्धता प्राप्त करते हैं, सामान्यतः कुछ प्रदर्शन की कीमत पर, प्रत्येक प्रक्रिया का कई बार विश्लेषण करके, संदर्भ के अनुसार एक बार।[7] अधिकांश विश्लेषण संदर्भ-स्ट्रिंग दृष्टिकोण का उपयोग करते हैं, जहां संदर्भों में प्रविष्टियों की एक सूची होती है (संदर्भ प्रविष्टि के सामान्य विकल्पों में कॉल साइट्स, आवंटन साइट्स और प्रकार सम्मलित हैं)।[8] समाप्ति (और अधिक सामान्यतः, स्केलेबिलिटी) सुनिश्चित करने के लिए, ऐसे विश्लेषण सामान्यतः एक के-सीमित दृष्टिकोण का उपयोग करते हैं, जहां संदर्भ में एक निश्चित अधिकतम बनावट होता है, और कम से कम हाल ही में जोड़े गए तत्वों को आवश्यकतानुसार हटा दिया जाता है।[9] संदर्भ-संवेदनशील, प्रवाह-असंवेदनशील विश्लेषण के तीन सामान्य प्रकार हैं:[10]
- कॉल-साइट संवेदनशीलता
- ऑब्जेक्ट संवेदनशीलता
- संवेदनशीलता टाइप करें
कॉल-साइट संवेदनशीलता
कॉल-साइट संवेदनशीलता में, प्रत्येक वेरिएबल के बिंदु-टू सेट (अमूर्त ढेर आवंटन का सेट प्रत्येक वेरिएबल को इंगित कर सकता है) प्रोग्राम में कॉलसाइट्स की एक सूची से युक्त एक संदर्भ द्वारा आगे योग्य है। ये संदर्भ प्रोग्राम के नियंत्रण-प्रवाह को अमूर्त करते हैं।
निम्नलिखित प्रोग्राम दर्शाता है कि कैसे कॉल-साइट संवेदनशीलता प्रवाह-असंवेदनशील, संदर्भ-असंवेदनशील विश्लेषण की तुलना में उच्च त्रुटिहीनता प्राप्त कर सकती है।
int *id(int* x) {
return x;
}
int main() {
int y;
int z;
int *y2 = id(&y); // call-site 1
int *z2 = id(&z); // call-site 2
return 0;
}
इस प्रोग्राम के लिए, एक संदर्भ-असंवेदनशील विश्लेषण (स्पष्ट रूप से लेकिन अस्पष्ट रूप से) यह निष्कर्ष निकालेगा कि x या तो y या z के आवंटन को इंगित कर सकता है, इसलिए y2 और z2 उपनाम हो सकते हैं, और दोनों या तो आवंटन को इंगित कर सकते हैं। एक कॉलसाइट-संवेदी विश्लेषण आईडी का दो बार विश्लेषण करेगा, एक बार कॉल-साइट 1 के लिए और एक बार कॉल-साइट 2 के लिए, और एक्स के लिए बिंदु-टू फैक्ट्स कॉल-साइट द्वारा योग्य होंगे, विश्लेषण को यह समझने में सक्षम बनाता है कि जब मुख्य रिटर्न , y2 सिर्फ आवंटन होल्डिंग y को इंगित कर सकता है और z2 सिर्फ आवंटन होल्डिंग z को इंगित कर सकता है।
ऑब्जेक्ट संवेदनशीलता
ऑब्जेक्ट संवेदनशीलता विश्लेषण में, प्रत्येक वेरिएबल के बिंदु-टू सेट को मेथड कॉल के रिसीवर ऑब्जेक्ट के एब्स्चिह्न्ट हीप आवंटन द्वारा क्वालिफाई किया जाता है। कॉल-साइट संवेदनशीलता के विपरीत, ऑब्जेक्ट-संवेदनशीलता गैर-वाक्यविन्यास या गैर-स्थानीय है: संदर्भ प्रविष्टियां बिंदु-टू-विश्लेषण के समय ही प्राप्त की जाती हैं।[11]
टाइप संवेदनशीलता
टाइप संवेदनशीलता ऑब्जेक्ट संवेदनशीलता का एक प्रकार है जहां रिसीवर ऑब्जेक्ट की आवंटन साइट को उस वर्ग/प्रकार से बदल दिया जाता है जिसमें रिसीवर ऑब्जेक्ट की आवंटन साइट वाली विधि होती है।[12] इसका परिणाम ऑब्जेक्ट-संवेदनशील विश्लेषण में उपयोग किए जाने वाले संदर्भों की तुलना में बहुत कम संदर्भों में होता है, जिसका सामान्यतः उत्तम प्रदर्शन होता है।
संदर्भ
- ↑ Reps, Thomas (2000-01-01). "Undecidability of context-sensitive data-dependence analysis". ACM Transactions on Programming Languages and Systems. 22 (1): 162–186. doi:10.1145/345099.345137. ISSN 0164-0925. S2CID 2956433.
- ↑ Barbara G. Ryder (2003). "Dimensions of Precision in Reference Analysis of Object-Oriented Programming Languages". Compiler Construction, 12th International Conference, CC 2003 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2003 Warsaw, Poland, April 7–11, 2003 Proceedings. pp. 126–137. doi:10.1007/3-540-36579-6_10.
- ↑ (Hind)
- ↑ 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; Bravenboer, Martin; Lhoták, Ondrej (2011-01-26). "Pick your contexts well: understanding object-sensitivity". Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL '11. Austin, Texas, USA: Association for Computing Machinery: 17–30. doi:10.1145/1926385.1926390. ISBN 978-1-4503-0490-0. S2CID 6451826.
- ↑ Antoniadis, Tony; Triantafyllou, Konstantinos; Smaragdakis, Yannis (2017-06-18). "Porting doop to Soufflé: a tale of inter-engine portability for Datalog-based analyses". Proceedings of the 6th ACM SIGPLAN International Workshop on State of the Art in Program Analysis. SOAP 2017. Barcelona, Spain: Association for Computing Machinery: 25–30. doi:10.1145/3088515.3088522. ISBN 978-1-4503-5072-3. S2CID 3074689.
- ↑ (Smaragdakis & Balatsouras, p. 29)
- ↑ Thiessen, Rei; Lhoták, Ondřej (2017-06-14). "Context transformations for pointer analysis". ACM SIGPLAN Notices. 52 (6): 263–277. doi:10.1145/3140587.3062359. ISSN 0362-1340.
- ↑ (Li et al., pp. 1:4)
- ↑ (Smaragdakis & Balatsouras)
- ↑ (Smaragdakis & Balatsouras, p. 37)
- ↑ (Smaragdakis & Balatsouras, p. 39)
ग्रन्थसूची
- 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).
