सूचक विश्लेषण: Difference between revisions

From Vigyanwiki
(Created page with "कंप्यूटर विज्ञान में, पॉइंटर विश्लेषण, या पॉइंट-टू-एनालिसिस, एक स...")
 
No edit summary
Line 1: Line 1:
[[कंप्यूटर विज्ञान]] में, पॉइंटर विश्लेषण, या पॉइंट-टू-एनालिसिस, एक [[स्थिर कोड विश्लेषण]] तकनीक है जो यह निर्धारित करती है कि कौन से [[सूचक (कंप्यूटर प्रोग्रामिंग)]] या ढेर संदर्भ, किस चर या भंडारण स्थानों को इंगित कर सकते हैं। यह अक्सर अधिक जटिल विश्लेषणों जैसे पलायन [[विश्लेषण का]] एक घटक होता है। एक निकट संबंधी तकनीक [[आकार विश्लेषण (सॉफ्टवेयर)]] है।
[[कंप्यूटर विज्ञान]] में, सूचक विश्लेषण, या पॉइंट-टू-एनालिसिस, एक [[स्थिर कोड विश्लेषण]] तकनीक है जो यह निर्धारित करती है कि कौन से [[सूचक (कंप्यूटर प्रोग्रामिंग)]] या ढेर संदर्भ, किस चर या भंडारण स्थानों को इंगित कर सकते हैं। यह अधिकांशतः अधिक जटिल विश्लेषणों जैसे पलायन [[विश्लेषण का]] एक घटक होता है। एक निकट संबंधी तकनीक [[आकार विश्लेषण (सॉफ्टवेयर)|बनावट विश्लेषण (सॉफ्टवेयर)]] है।


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


== उदाहरण ==
== उदाहरण ==
निम्नलिखित उदाहरण कार्यक्रम के लिए, अंक-टू-विश्लेषण यह गणना करेगा कि अंक-टू-सेट <code>p</code> है {<code>x</code>, <code>y</code>}.
निम्नलिखित उदाहरण प्रोग्राम के लिए, अंक-टू-विश्लेषण यह गणना करेगा कि अंक-टू-सेट <code>p</code> है {<code>x</code>, <code>y</code>}.<syntaxhighlight lang="c">
 
int x;
<वाक्यविन्यास प्रकाश लैंग = सी>
int y;
इंट एक्स;
int* p = unknown() ? &x : &y;
इंट वाई;
</syntaxhighlight>
int * पी = अज्ञात ()? & एक्स : और वाई;
</वाक्यविन्यास हाइलाइट>


== परिचय ==
== परिचय ==


स्थैतिक विश्लेषण के एक रूप के रूप में, पूरी तरह से सटीक सूचक विश्लेषण को [[अनिर्णीत समस्या]] के रूप में दिखाया जा सकता है।<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
स्थैतिक विश्लेषण के एक रूप के रूप में, पूरे प्रकार से त्रुटिहीन सूचक विश्लेषण को [[अनिर्णीत समस्या]] के रूप में दिखाया जा सकता है।<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 22: Line 20:
|doi = 10.1007/3-540-36579-6_10| doi-access=free
|doi = 10.1007/3-540-36579-6_10| doi-access=free
}}</ref><ref>{{harv|Hind}}</ref>
}}</ref><ref>{{harv|Hind}}</ref>
* क्षेत्र संवेदनशीलता (संरचना संवेदनशीलता के रूप में भी जाना जाता है): एक विश्लेषण या तो एक [[रिकॉर्ड (कंप्यूटर विज्ञान)]] या [[वस्तु (कंप्यूटर विज्ञान)]] के प्रत्येक क्षेत्र को अलग से देख सकता है, या उन्हें मर्ज कर सकता है।
* क्षेत्र संवेदनशीलता (संरचना संवेदनशीलता के रूप में भी जाना जाता है): एक विश्लेषण या तो एक [[रिकॉर्ड (कंप्यूटर विज्ञान)]] या [[वस्तु (कंप्यूटर विज्ञान)|ऑब्जेक्ट (कंप्यूटर विज्ञान)]] के प्रत्येक क्षेत्र को भिन्न प्रकार से देख सकता है, या उन्हें मर्ज कर सकता है।
* ऐरे सेंसिटिविटी: एक एरे-सेंसिटिव पॉइंटर एनालिसिस प्रत्येक इंडेक्स को अलग-अलग एरे में मॉडल करता है। अन्य विकल्पों में केवल पहली प्रविष्टि को अलग से और बाकी को एक साथ मॉडलिंग करना, या सभी सरणी प्रविष्टियों को मर्ज करना शामिल है।
* ऐरे संवेदनशीलता: एक एरे-संवेदनशीलता सूचक विश्लेषण प्रत्येक इंडेक्स को भिन्न-भिन्न एरे में मॉडल करता है। अन्य विकल्पों में सिर्फ पहली प्रविष्टि को भिन्न प्रकार से और बाकी को एक साथ मॉडलिंग करना, या सभी सरणी प्रविष्टियों को मर्ज करना सम्मलित है।
* संदर्भ संवेदनशीलता: सूचक विश्लेषण प्रत्येक कार्यक्रम बिंदु पर जाने वाले नियंत्रण प्रवाह के सारांश के साथ सूचना के बिंदुओं को अर्हता प्राप्त कर सकता है।
* संदर्भ संवेदनशीलता: सूचक विश्लेषण प्रत्येक प्रोग्राम बिंदु पर जाने वाले नियंत्रण प्रवाह के सारांश के साथ सूचना के बिंदुओं को अर्हता प्राप्त कर सकता है।
* फ्लो सेंसिटिविटी: एक विश्लेषण पॉइंट टू फैक्ट्स पर इंट्राप्रोसेरल कंट्रोल फ्लो के प्रभाव को मॉडल कर सकता है।
* फ्लो संवेदनशीलता: एक विश्लेषण पॉइंट टू फैक्ट्स पर इंट्राप्रोसेरल कंट्रोल फ्लो के प्रभाव को मॉडल कर सकता है।
* हीप मॉडलिंग: रन-टाइम आबंटन को इसके द्वारा अमूर्त किया जा सकता है:
* हीप मॉडलिंग: रन-टाइम आवंटन को इसके द्वारा अमूर्त किया जा सकता है:
** उनकी आवंटन साइटें (बयान या निर्देश जो आवंटन करता है, उदाहरण के लिए, एक कॉल <code>malloc</code> या एक वस्तु निर्माता),
** उनकी आवंटन साइटें (बयान या निर्देश जो आवंटन करता है, उदाहरण के लिए, एक कॉल <code>मैलोक</code> या एक ऑब्जेक्ट निर्माता),
** आकार विश्लेषण (सॉफ्टवेयर) पर आधारित एक अधिक जटिल मॉडल,
** बनावट विश्लेषण (सॉफ्टवेयर) पर आधारित एक अधिक जटिल मॉडल,
** आवंटन का प्रकार, या
** आवंटन का प्रकार, या
** एक एकल आवंटन (इसे हीप-असंवेदनशीलता कहा जाता है)।
** एक एकल आवंटन (इसे हीप-असंवेदनशीलता कहा जाता है)।
* हीप क्लोनिंग: हीप- और संदर्भ-संवेदी विश्लेषण प्रत्येक आवंटन साइट को नियंत्रण प्रवाह के सारांश द्वारा निर्देश या कथन को पूरा करने वाले कथन के लिए अग्रणी बना सकते हैं।
* हीप क्लोनिंग: हीप- और संदर्भ-संवेदी विश्लेषण प्रत्येक आवंटन साइट को नियंत्रण प्रवाह के सारांश द्वारा निर्देश या कथन को पूरा करने वाले कथन के लिए अग्रणी बना सकते हैं।
* उपसमुच्चय बाधाएँ या समानता बाधाएँ: जब तथ्यों के बिंदुओं का प्रचार किया जाता है, तो विभिन्न प्रोग्राम स्टेटमेंट एक चर के बिंदुओं से सेटों पर विभिन्न बाधाओं को प्रेरित कर सकते हैं। समानता की कमी (जैसे स्टीन्सगार्ड के एल्गोरिथ्म में उपयोग की जाने वाली) को एक [[संघ-खोज डेटा संरचना]] के साथ ट्रैक किया जा सकता है, जिससे एक सबसेट-बाधा आधारित विश्लेषण (जैसे, एंडरसन के एल्गोरिथ्म) की सटीकता की कीमत पर उच्च प्रदर्शन हो सकता है।
* उपसमुच्चय बाधाएँ या समानता बाधाएँ: जब तथ्यों के बिंदुओं का प्रचार किया जाता है, तो विभिन्न प्रोग्राम कथन एक चर के बिंदुओं से सेटों पर विभिन्न बाधाओं को प्रेरित कर सकते हैं। समानता की कमी (जैसे स्टीन्सगार्ड के कलन विधि में उपयोग की जाने वाली) को एक [[संघ-खोज डेटा संरचना]] के साथ चिह्न किया जा सकता है, जिससे एक उपसमुच्य-बाधा आधारित विश्लेषण (जैसे, एंडरसन के कलन विधि) की त्रुटिहीनता की कीमत पर उच्च प्रदर्शन हो सकता है।


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


सूचक विश्लेषण एल्गोरिदम का उपयोग एकत्रित कच्चे सूचक उपयोगों (एक सूचक को दूसरे के लिए असाइनमेंट या एक सूचक को दूसरे को इंगित करने के लिए असाइन करना) को एक उपयोगी ग्राफ में परिवर्तित करने के लिए किया जाता है जो प्रत्येक सूचक को इंगित कर सकता है।<ref>{{cite conference
सूचक विश्लेषण कलन विधि का उपयोग एकत्रित कच्चे सूचक उपयोगों (एक सूचक को दूसरे के लिए असाइनमेंट या एक सूचक को दूसरे को इंगित करने के लिए असाइन करना) को एक उपयोगी ग्राफ में परिवर्तित करने के लिए किया जाता है जो प्रत्येक सूचक को इंगित कर सकता है।<ref>{{cite conference
| url          =https://www.zyrianov.org/papers/ICPC19.pdf
| url          =https://www.zyrianov.org/papers/ICPC19.pdf
| title        =srcPtr: A Framework for Implementing Static Pointer Analysis Approaches
| title        =srcPtr: A Framework for Implementing Static Pointer Analysis Approaches
Line 49: Line 47:
| publisher    =IEEE
| publisher    =IEEE
}}
}}
</ref> स्टेन्सगार्ड के एल्गोरिथ्म और एंडरसन के एल्गोरिथ्म सूचक विश्लेषण के लिए सामान्य संदर्भ-असंवेदनशील, प्रवाह-असंवेदनशील एल्गोरिदम हैं। वे अक्सर कंपाइलर्स में उपयोग किए जाते हैं, और [[एलएलवीएम]] कोडबेस में कार्यान्वयन होते हैं।
</ref> स्टेन्सगार्ड के कलन विधि और एंडरसन के कलन विधि सूचक विश्लेषण के लिए सामान्य संदर्भ-असंवेदनशील, प्रवाह-असंवेदनशील कलन विधि हैं। वे अधिकांशतः कंपाइलर्स में उपयोग किए जाते हैं, और [[एलएलवीएम]] कोडबेस में कार्यान्वयन होते हैं।


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


प्रवाह-असंवेदनशील सूचक विश्लेषण के कई दृष्टिकोणों को अमूर्त व्याख्या के रूपों के रूप में समझा जा सकता है, जहां हीप आवंटन को उनके आवंटन स्थल (यानी, एक कार्यक्रम स्थान) द्वारा सारित किया जाता है।<ref>{{Cite journal|last1=Smaragdakis|first1=Yannis|last2=Bravenboer|first2=Martin|last3=Lhoták|first3=Ondrej|date=2011-01-26|title=Pick your contexts well: understanding object-sensitivity|url=https://doi.org/10.1145/1926385.1926390|journal=Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages|series=POPL '11|location=Austin, Texas, USA|publisher=Association for Computing Machinery|pages=17–30|doi=10.1145/1926385.1926390|isbn=978-1-4503-0490-0|s2cid=6451826}}</ref>
प्रवाह-असंवेदनशील सूचक विश्लेषण के कई दृष्टिकोणों को अमूर्त व्याख्या के रूपों के रूप में समझा जा सकता है, जहां हीप आवंटन को उनके आवंटन स्थल (अर्थात, एक प्रोग्राम स्थान) द्वारा सारित किया जाता है।<ref>{{Cite journal|last1=Smaragdakis|first1=Yannis|last2=Bravenboer|first2=Martin|last3=Lhoták|first3=Ondrej|date=2011-01-26|title=Pick your contexts well: understanding object-sensitivity|url=https://doi.org/10.1145/1926385.1926390|journal=Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages|series=POPL '11|location=Austin, Texas, USA|publisher=Association for Computing Machinery|pages=17–30|doi=10.1145/1926385.1926390|isbn=978-1-4503-0490-0|s2cid=6451826}}</ref>


[[File:Pointer Analysis - Abstracting Memory Addresses by Their Allocation Site.svg|alt=A diagram showing how pointer analysis abstracts runtime memory|thumb|फ्लो-असंवेदनशील सूचक विश्लेषण अक्सर उनके आवंटन साइट द्वारा संभावित रनटाइम आवंटन का सार करता है। रनटाइम पर, यह प्रोग्राम तीन अलग-अलग ढेर आवंटन बनाता है। एक प्रवाह-असंवेदनशील सूचक विश्लेषण इन्हें एकल अमूर्त स्मृति स्थान के रूप में मानेगा, जिससे परिशुद्धता का नुकसान होगा।]]कई प्रवाह-असंवेदनशील एल्गोरिदम को [[Datalog]] में निर्दिष्ट किया गया है, जिसमें जावा के लिए सूट विश्लेषण ढांचे में शामिल हैं।<ref>{{Cite journal|last1=Antoniadis|first1=Tony|last2=Triantafyllou|first2=Konstantinos|last3=Smaragdakis|first3=Yannis|date=2017-06-18|title=Porting doop to Soufflé: a tale of inter-engine portability for Datalog-based analyses|url=https://doi.org/10.1145/3088515.3088522|journal=Proceedings of the 6th ACM SIGPLAN International Workshop on State of the Art in Program Analysis|series=SOAP 2017|location=Barcelona, Spain|publisher=Association for Computing Machinery|pages=25–30|doi=10.1145/3088515.3088522|isbn=978-1-4503-5072-3|s2cid=3074689}}</ref>
[[File:Pointer Analysis - Abstracting Memory Addresses by Their Allocation Site.svg|alt=A diagram showing how pointer analysis abstracts runtime memory|thumb|फ्लो-असंवेदनशील सूचक विश्लेषण अधिकांशतः उनके आवंटन साइट द्वारा संभावित रनटाइम आवंटन का सार करता है। रनटाइम पर, यह प्रोग्राम तीन भिन्न-भिन्न ढेर आवंटन बनाता है। एक प्रवाह-असंवेदनशील सूचक विश्लेषण इन्हें एकल अमूर्त स्मृति स्थान के रूप में मानेगा, जिससे परिशुद्धता का नुकसान होगा।]]कई प्रवाह-असंवेदनशील कलन विधि को [[Datalog|डेटा लॉग]] में निर्दिष्ट किया गया है, जिसमें जावा के लिए सूट विश्लेषण ढांचे में सम्मलित हैं।<ref>{{Cite journal|last1=Antoniadis|first1=Tony|last2=Triantafyllou|first2=Konstantinos|last3=Smaragdakis|first3=Yannis|date=2017-06-18|title=Porting doop to Soufflé: a tale of inter-engine portability for Datalog-based analyses|url=https://doi.org/10.1145/3088515.3088522|journal=Proceedings of the 6th ACM SIGPLAN International Workshop on State of the Art in Program Analysis|series=SOAP 2017|location=Barcelona, Spain|publisher=Association for Computing Machinery|pages=25–30|doi=10.1145/3088515.3088522|isbn=978-1-4503-5072-3|s2cid=3074689}}</ref>
संदर्भ-संवेदनशील, प्रवाह-असंवेदनशील एल्गोरिदम उच्च परिशुद्धता प्राप्त करते हैं, आम तौर पर कुछ प्रदर्शन की कीमत पर, प्रत्येक प्रक्रिया का कई बार विश्लेषण करके, संदर्भ के अनुसार एक बार।<ref>{{harv|Smaragdakis|Balatsouras|p=29}}</ref> अधिकांश विश्लेषण संदर्भ-स्ट्रिंग दृष्टिकोण का उपयोग करते हैं, जहां संदर्भों में प्रविष्टियों की एक सूची होती है (संदर्भ प्रविष्टि के सामान्य विकल्पों में कॉल साइट्स, आवंटन साइट्स और प्रकार शामिल हैं)।<ref>{{Cite journal|last1=Thiessen|first1=Rei|last2=Lhoták|first2=Ondřej|date=2017-06-14|title=Context transformations for pointer analysis|url=https://doi.org/10.1145/3140587.3062359|journal=ACM SIGPLAN Notices|volume=52|issue=6|pages=263–277|doi=10.1145/3140587.3062359|issn=0362-1340}}</ref> समाप्ति (और अधिक सामान्यतः, स्केलेबिलिटी) सुनिश्चित करने के लिए, ऐसे विश्लेषण आम तौर पर एक के-सीमित दृष्टिकोण का उपयोग करते हैं, जहां संदर्भ में एक निश्चित अधिकतम आकार होता है, और कम से कम हाल ही में जोड़े गए तत्वों को आवश्यकतानुसार हटा दिया जाता है।<ref>{{harv|Li|Tan|Møller|Smaragdakis|pp=1:4}}</ref> संदर्भ-संवेदनशील, प्रवाह-असंवेदनशील विश्लेषण के तीन सामान्य प्रकार हैं:<ref>{{harv|Smaragdakis|Balatsouras}}</ref>
संदर्भ-संवेदनशील, प्रवाह-असंवेदनशील कलन विधि उच्च परिशुद्धता प्राप्त करते हैं, सामान्यतः कुछ प्रदर्शन की कीमत पर, प्रत्येक प्रक्रिया का कई बार विश्लेषण करके, संदर्भ के अनुसार एक बार।<ref>{{harv|Smaragdakis|Balatsouras|p=29}}</ref> अधिकांश विश्लेषण संदर्भ-स्ट्रिंग दृष्टिकोण का उपयोग करते हैं, जहां संदर्भों में प्रविष्टियों की एक सूची होती है (संदर्भ प्रविष्टि के सामान्य विकल्पों में कॉल साइट्स, आवंटन साइट्स और प्रकार सम्मलित हैं)।<ref>{{Cite journal|last1=Thiessen|first1=Rei|last2=Lhoták|first2=Ondřej|date=2017-06-14|title=Context transformations for pointer analysis|url=https://doi.org/10.1145/3140587.3062359|journal=ACM SIGPLAN Notices|volume=52|issue=6|pages=263–277|doi=10.1145/3140587.3062359|issn=0362-1340}}</ref> समाप्ति (और अधिक सामान्यतः, स्केलेबिलिटी) सुनिश्चित करने के लिए, ऐसे विश्लेषण सामान्यतः एक के-सीमित दृष्टिकोण का उपयोग करते हैं, जहां संदर्भ में एक निश्चित अधिकतम बनावट होता है, और कम से कम हाल ही में जोड़े गए तत्वों को आवश्यकतानुसार हटा दिया जाता है।<ref>{{harv|Li|Tan|Møller|Smaragdakis|pp=1:4}}</ref> संदर्भ-संवेदनशील, प्रवाह-असंवेदनशील विश्लेषण के तीन सामान्य प्रकार हैं:<ref>{{harv|Smaragdakis|Balatsouras}}</ref>
* कॉल-साइट संवेदनशीलता
* कॉल-साइट संवेदनशीलता
* वस्तु संवेदनशीलता
* ऑब्जेक्ट संवेदनशीलता
* संवेदनशीलता टाइप करें
* संवेदनशीलता टाइप करें


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


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


निम्नलिखित कार्यक्रम दर्शाता है कि कैसे कॉल-साइट संवेदनशीलता प्रवाह-असंवेदनशील, संदर्भ-असंवेदनशील विश्लेषण की तुलना में उच्च सटीकता प्राप्त कर सकती है।
निम्नलिखित प्रोग्राम दर्शाता है कि कैसे कॉल-साइट संवेदनशीलता प्रवाह-असंवेदनशील, संदर्भ-असंवेदनशील विश्लेषण की तुलना में उच्च त्रुटिहीनता प्राप्त कर सकती है।<syntaxhighlight lang="c">
<वाक्यविन्यास प्रकाश लैंग = सी>
int *id(int* x) {
इंट * आईडी (इंट * एक्स) {
   return x;
   वापसी एक्स;
}
}
मुख्य प्रवेश बिंदु() {
int main() {
   इंट वाई;
   int y;
   इंट जेड;
   int z;
   int *y2 = आईडी (और वाई); // कॉल-साइट 1
   int *y2 = id(&y); // call-site 1
   int *z2 = आईडी (&z); // कॉल-साइट 2
   int *z2 = id(&z); // call-site 2
   वापसी 0;
   return 0;
}
}
</वाक्यविन्यास हाइलाइट>
</syntaxhighlight>इस प्रोग्राम के लिए, एक संदर्भ-असंवेदनशील विश्लेषण (स्पष्ट रूप से लेकिन अस्पष्ट रूप से) यह निष्कर्ष निकालेगा कि x या तो y या z के आवंटन को इंगित कर सकता है, इसलिए y2 और z2 उपनाम हो सकते हैं, और दोनों या तो आवंटन को इंगित कर सकते हैं। एक कॉलसाइट-संवेदी विश्लेषण आईडी का दो बार विश्लेषण करेगा, एक बार कॉल-साइट 1 के लिए और एक बार कॉल-साइट 2 के लिए, और एक्स के लिए पॉइंट-टू फैक्ट्स कॉल-साइट द्वारा योग्य होंगे, विश्लेषण को यह समझने में सक्षम बनाता है कि जब मुख्य रिटर्न , y2 सिर्फ आवंटन होल्डिंग y को इंगित कर सकता है और z2 सिर्फ आवंटन होल्डिंग z को इंगित कर सकता है।
इस कार्यक्रम के लिए, एक संदर्भ-असंवेदनशील विश्लेषण (ध्वनिपूर्ण लेकिन अस्पष्ट रूप से) यह निष्कर्ष निकालेगा {{var|x}} या तो आवंटन होल्डिंग को इंगित कर सकता है {{var|y}} या वह {{var|z}}, इसलिए {{var|y2}} और {{var|z2}} may उर्फ, और दोनों या तो आवंटन की ओर इशारा कर सकते हैं। एक कॉलसाइट-संवेदनशील विश्लेषण विश्लेषण करेगा {{var|id}} दो बार, एक बार कॉल-साइट 1 के लिए और एक बार कॉल-साइट 2 के लिए, और पॉइंट-टू फैक्ट्स के लिए {{var|x}} कॉल-साइट द्वारा योग्य होगा, विश्लेषण को सक्षम करने के लिए कि कब {{var|main}} लौटता है, {{var|y2}} केवल आवंटन होल्डिंग को इंगित कर सकता है {{var|y}} और {{var|z2}} केवल आवंटन होल्डिंग को इंगित कर सकता है {{var|z}}.
 
=== वस्तु संवेदनशीलता ===
 
ऑब्जेक्ट सेंसिटिव एनालिसिस में, प्रत्येक वेरिएबल के पॉइंट-टू सेट को मेथड कॉल के रिसीवर ऑब्जेक्ट के एब्स्ट्रैक्ट हीप एलोकेशन द्वारा क्वालिफाई किया जाता है। कॉल-साइट संवेदनशीलता के विपरीत, वस्तु-संवेदनशीलता गैर-वाक्यविन्यास या गैर-स्थानीय है: संदर्भ प्रविष्टियां पॉइंट-टू-विश्लेषण के दौरान ही प्राप्त की जाती हैं।<ref>{{harv|Smaragdakis|Balatsouras|p=37}}</ref>


=== ऑब्जेक्ट संवेदनशीलता ===


ऑब्जेक्ट संवेदनशीलता विश्लेषण में, प्रत्येक वेरिएबल के पॉइंट-टू सेट को मेथड कॉल के रिसीवर ऑब्जेक्ट के एब्स्चिह्न्ट हीप आवंटन द्वारा क्वालिफाई किया जाता है। कॉल-साइट संवेदनशीलता के विपरीत, ऑब्जेक्ट-संवेदनशीलता गैर-वाक्यविन्यास या गैर-स्थानीय है: संदर्भ प्रविष्टियां पॉइंट-टू-विश्लेषण के समय ही प्राप्त की जाती हैं।<ref>{{harv|Smaragdakis|Balatsouras|p=37}}</ref>
=== टाइप संवेदनशीलता ===
=== टाइप संवेदनशीलता ===


टाइप सेंसिटिविटी ऑब्जेक्ट सेंसिटिविटी का एक प्रकार है जहां रिसीवर ऑब्जेक्ट की आवंटन साइट को उस वर्ग/प्रकार से बदल दिया जाता है जिसमें रिसीवर ऑब्जेक्ट की आवंटन साइट वाली विधि होती है।<ref>{{harv|Smaragdakis|Balatsouras|p=39}}</ref> इसका परिणाम वस्तु-संवेदनशील विश्लेषण में उपयोग किए जाने वाले संदर्भों की तुलना में बहुत कम संदर्भों में होता है, जिसका आमतौर पर बेहतर प्रदर्शन होता है।
टाइप संवेदनशीलता ऑब्जेक्ट संवेदनशीलता का एक प्रकार है जहां रिसीवर ऑब्जेक्ट की आवंटन साइट को उस वर्ग/प्रकार से बदल दिया जाता है जिसमें रिसीवर ऑब्जेक्ट की आवंटन साइट वाली विधि होती है।<ref>{{harv|Smaragdakis|Balatsouras|p=39}}</ref> इसका परिणाम ऑब्जेक्ट-संवेदनशील विश्लेषण में उपयोग किए जाने वाले संदर्भों की तुलना में बहुत कम संदर्भों में होता है, जिसका सामान्यतः उत्तम प्रदर्शन होता है।


==संदर्भ==
==संदर्भ==

Revision as of 10:01, 28 February 2023

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

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

उदाहरण

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

int x;
int y;
int* p = unknown() ? &x : &y;

परिचय

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

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

संदर्भ-असंवेदनशील, प्रवाह-असंवेदनशील कलन विधि

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

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

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

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

कई प्रवाह-असंवेदनशील कलन विधि को डेटा लॉग में निर्दिष्ट किया गया है, जिसमें जावा के लिए सूट विश्लेषण ढांचे में सम्मलित हैं।[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] इसका परिणाम ऑब्जेक्ट-संवेदनशील विश्लेषण में उपयोग किए जाने वाले संदर्भों की तुलना में बहुत कम संदर्भों में होता है, जिसका सामान्यतः उत्तम प्रदर्शन होता है।

संदर्भ

  1. ↑ 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.
  2. ↑ 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.
  3. ↑ (Hind)
  4. ↑ 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.
  5. ↑ 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.
  6. ↑ 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.
  7. ↑ (Smaragdakis & Balatsouras, p. 29)
  8. ↑ 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.
  9. ↑ (Li et al., pp. 1:4)
  10. ↑ (Smaragdakis & Balatsouras)
  11. ↑ (Smaragdakis & Balatsouras, p. 37)
  12. ↑ (Smaragdakis & Balatsouras, p. 39)


ग्रन्थसूची


Retrieved from ‘https://www.vigyanwiki.in/index.php?title=सूचक_विश्लेषण&oldid=111441’