Complexity Theory of Randomised Testing
यह शोध पत्र जनरेटरों को ट्यूरिंग ट्रांसड्यूसर के रूप में मॉडल करके रैंडमाइज्ड टेस्टिंग के लिए पहले जटिलता-सैद्धांतिक आधार स्थापित करता है ताकि कुशल और स्थान-सीमित इनपुट जनरेशन की सीमाओं को स्पष्ट किया जा सके, जो जनरेशन और डिसीजन कॉम्प्लेक्सिटी के बीच मौलिक अंतरों को प्रकट करता है और यह सिद्ध करता है कि कुशल जनरेशन के लिए विशिष्ट सर्टिफिकेट स्कीम्स की आवश्यकता होती है और इसे सामान्य लॉजिकल प्रेडिकेट्स से कंपोजिशनली व्युत्पन्न नहीं किया जा सकता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कल्पना कीजिए कि आप एक वीडियो गेम डेवलपर हैं जो एक नए, विशाल संसार का परीक्षण करने की कोशिश कर रहे हैं। आप यह सुनिश्चित करना चाहते हैं कि आपका गेम क्रैश न हो, इसलिए आपको एक ऐसे रोबोट की आवश्यकता है जो लाखों रैंडम लेवल, पात्र और वस्तुएं उगल सके ताकि यह देखा जा सके कि कहीं कुछ टूट तो नहीं रहा। इस रोबोट को एक जेनरेटर (generator) कहा जाता है। वर्षों से, डेवलपर्स इन रोबोटों को हाथ से बनाते रहे हैं, उन्हें तब तक ट्यून करते रहे हैं जब तक कि वे ठीक से काम न करने लगें। लेकिन वास्तव में कोई नहीं जानता था कि इन रोबोटों की सैद्धांतिक सीमाएँ (theoretical limits) क्या हैं। क्या वे कोई भी संभव लेवल बना सकते हैं? क्या वे इसे इतना तेज़ कर सकते हैं कि यह उपयोगी हो?
इंपीरियल कॉलेज लंदन और काइहोंग के शोधकर्ताओं की एक टीम ने इन रोबोटों को सूक्ष्मदर्शी से देखने का निर्णय लिया—कॉम्प्लेक्सिटी थ्योरी (Complexity Theory) का उपयोग करके, जो यह अध्ययन करती है कि समस्याओं को हल करना कितना कठिन है। उन्होंने केवल कोड को नहीं देखा; उन्होंने इन रोबोटों को "ट्यूरिंग मशीनों" (अंतिम सैद्धांतिक कंप्यूटर) के रूप में मॉडल किया जो डेटा के रैंडम बिट्स को खाते हैं और गेम लेवल उगलते हैं। यहाँ उन्होंने क्या खोजा।
"क्या बनाया जा सकता है" की सूची
सबसे पहले, उन्होंने पूछा: एक जेनरेटर द्वारा बनाई जा सकने वाली चीजों की परम सीमा क्या है?
उन्होंने पाया कि यदि आप एक जेनरेटर को असीमित समय और मेमोरी देते हैं, तो वह बिल्कुल उन्हीं चीजों का समूह बना सकता है जिसे एक मानक कंप्यूटर पहचान (recognize) सकता है। गणित की दुनिया में, इसे रिकर्सिवली एन्यूमेरेबल (Recursively Enumerable - RE) भाषाएं कहा जाता है।
- अच्छी खबर: यदि इनपुट का एक सेट (जैसे "सभी वैध C प्रोग्राम") जिसे एक कंप्यूटर पहचान सकता है, तो एक जेनरेटर सैद्धांतिक रूप से उन्हें उत्पन्न कर सकता है।
- बुरी खबर: यदि इनपुट का एक सेट बहुत अजीब है जिसे कंप्यूटर द्वारा पहचाना नहीं जा सकता (जैसे "सभी प्रोग्राम जो कभी रुकेंगे नहीं"), तो कोई भी जेनरेटर उन्हें कभी भी उत्पन्न नहीं कर पाएगा। यह आपके कोड में बग नहीं है; यह ब्रह्मांड का एक मौलिक नियम है। आप एक ऐसा रोबोट नहीं बना सकते जो हर संभव अनंत लूप (infinite loop) को उगल सके, क्योंकि गणित कहता है कि उन सभी को सूचीबद्ध करना असंभव है।
"स्पीड बंप" (गति की बाधा) की समस्या
अगला सवाल था: क्या होगा अगर हमें जेनरेटर को तेज़ होने की आवश्यकता हो? वास्तविक दुनिया में, आप एक मिलियन साल तक इंतज़ार नहीं कर सकते। आपको सेकंडों में परिणाम चाहिए।
शोधकर्ताओं ने एक आश्चर्यजनक मोड़ की खोज की: किसी चीज़ को वैध होने के लिए जांचना और किसी चीज़ को वैध बनाना एक ही बात नहीं है।
- SAT सॉल्वर का उदाहरण: कल्पना कीजिए कि आपके पास एक पहेली है जहाँ आपको लाइट जलाने के लिए स्विचों का एक विशिष्ट संयोजन खोजना है। यह जांचना कि क्या कोई संयोजन काम करता है, कठिन है (यह "NP-complete" है)। लेकिन शोधकर्ताओं ने दिखाया कि आप इन काम करने वाले संयोजनों को बनाने के लिए एक तेज़ रोबोट बना सकते हैं। यह "विटनेस (witness) को रोपित करके" काम करता है: रोबोट पहले गुप्त रूप से एक जीतने वाला संयोजन चुनता है, फिर उसके इर्द-गिर्द पहेली बनाता है।
- हैश कोलिजन (Hash Collision) का जाल: हालाँकि, उन्होंने यह भी सिद्ध किया कि कुछ समस्याओं के लिए, भले ही उत्तर की जांच करना आसान हो, उत्तर बनाना तेज़ रूप से करना असंभव हो सकता है। उन्होंने "हैश कोलिजन" (दो अलग-अलग इनपुट ढूंढना जो एक ही डिजिटल फिंगरप्रिंट उत्पन्न करते हैं) को देखा। यह जांचना कि क्या दो फिंगरप्रिंट मेल खाते हैं, बहुत तेज़ है। लेकिन मेल खाने वाला जोड़ा ढूंढना? यदि आप ऐसा करने के लिए एक तेज़ रोबोट बना सकते, तो आप लगभग सभी आधुनिक एन्क्रिप्शन की सुरक्षा को तोड़ देते।
- निष्कर्ष: जब तक क्रिप्टोग्राफी की दुनिया टूटी नहीं है, ऐसी समस्याएँ हैं जहाँ जांचना आसान है, लेकिन बनाना कठिन है। आप केवल एक तेज़ जेनरेटर की इच्छा नहीं कर सकते; कभी-कभी, गणित ही इसकी अनुमति नहीं देता।
"मेमोरी" की बाधा (फज़िंग और फीडबैक)
कई आधुनिक परीक्षण उपकरण, जैसे कि "फज़र्स (fuzzers)", केवल रैंडम डेटा नहीं उगलते; वे याद रखते हैं कि उन्होंने पहले क्या आज़माया था। यदि कोई टेस्ट प्रोग्राम को क्रैश कर देता है, तो फज़र उसे याद रखता है और उसे फिर से क्रैश करने के लिए इनपुट को बदलने की कोशिश करता है। यह एक जासूस की तरह है जो हर सुराग से सीखता है।
शोधकर्ताओं ने इसे सीमित मेमोरी (space) वाले जेनरेटर के रूप में मॉडल किया। उन्होंने पाया कि इस "मेमोरी" और फीडबैक लूप के साथ भी, जेनरेटर अभी भी सीमित है।
- सीमा: यदि जेनरेटर के पास पॉलीनोमियल (polynomial) मात्रा में मेमोरी है (जो लगभग सभी व्यावहारिक उपकरणों को कवर करता है), तो वह केवल ऐसी चीजें उत्पन्न कर सकता है जो PSPACE नामक वर्ग से संबंधित हैं।
- वास्तविकता की जाँच: इसका मतलब है कि भले ही सबसे स्मार्ट, सबसे अधिक मेमोरी वाले फज़िंग टूल्स हों, वे "EXPTIME-complete" (वे समस्याएँ जिन्हें हल करने में घातीय समय लगता है) समस्याओं के लिए इनपुट उत्पन्न नहीं कर सकते। यदि कोई समस्या इतनी जटिल है कि उसे PSPACE मशीन द्वारा हल नहीं किया जा सकता, तो फीडबैक या मेमोरी का कोई भी स्तर जेनरेटर को टेस्ट केस बनाने में मदद नहीं करेगा।
"कंपोजेबिलिटी" (संयोजन क्षमता) का मिथक
अंत में, उन्होंने सॉफ्टवेयर इंजीनियरों के एक सपने पर प्रहार किया: क्या हम जेनरेटर्स का एक "लेगो सेट (Lego set)" बना सकते हैं?
कल्पना कीजिए कि आपके पास एक उपकरण है जहाँ आप कहते हैं, "मुझे A और B के लिए एक जेनरेटर चाहिए," या "मुझे NOT A के लिए एक जेनरल चाहिए," और वह उपकरण स्वचालित रूप से उन्हें एक नए, तेज़ जेनरेटर में जोड़ देता है।
पेपर इस सपने को मानक धारणाओं के तहत एक कड़ा "नहीं" देता है।
- नियम: आप जेनरेटर्स को "AND" (संयोजन) या "NOT" (निषेध) का उपयोग करके स्वचालित रूप से जोड़ नहीं सकते और यह गारंटी नहीं दे सकते कि वे अभी भी तेज़ रहेंगे।
- क्यों? यदि आप ऐसा कर सकते, तो आप उन समस्याओं को हल कर सकते जिन्हें वर्तमान में तेजी से हल करना असंभव माना जाता है।
- अपवाद: आप बहुत सरल, प्रतिबंधित प्रकार के लॉजिक (जैसे "लीनियर डैलोग (linear Datalog)" या "NL" समस्याएं) के लिए ऐसा कर सकते हैं, लेकिन जैसे ही आप जटिल "ANDs" या "NOTs" जोड़ते हैं, जादू टूट जाता है। यदि आप जटिल नियमों को जोड़ना चाहते हैं, तो आपको या तो गति की गारंटी छोड़नी होगी या यह स्वीकार करना होगा कि आपका जेनरेटर बस तब तक "कोशिश और विफल" (rejection sampling) होगा जब तक कि वह भाग्यशाली न हो जाए।
बड़ी तस्वीर
पेपर निष्कर्ष निकालता है कि डेटा उत्पन्न करना, डेटा वैध है या नहीं यह तय करने की तुलना में एक अलग और अक्सर कठिन चुनौती है।
- क्या सिद्ध हुआ: उन्होंने सिद्ध किया कि सभी उत्पन्न करने योग्य चीजों का सेट वही है जो रिकर्सिवली एन्यूरेबल चीजें हैं। उन्होंने सिद्ध किया कि कुछ कठिन समस्याओं (जैसे SAT) के लिए तेज़ जेनरेटर मौजूद हैं, लेकिन अन्य (जैसे हैश कोलिजन, यह मानते हुए कि क्रिप्टो सुरक्षित है) के लिए नहीं। उन्होंने सिद्ध किया कि फीडबैक-संचालित उपकरण PSPACE द्वारा सीमित हैं।
- क्या खारिज किया गया: उन्होंने एक सार्वभौमिक, तेज़, कंपोजिशनल लाइब्रेरी बनाने की संभावना को खारिज कर दिया जो किसी भी तार्किक संयोजन के नियमों को संभाल सके। उन्होंने इस विचार को खारिज कर दिया कि "जांचना आसान" हमेशा "बनाना आसान" होता है।
संक्षेप में, यदि आप एक परीक्षण रोबोट बना रहे हैं, तो आप केवल यह उम्मीद नहीं कर सकते कि वह तेज़ और स्मार्ट होगा। गणित ने एक रेखा खींच दी है: कुछ चीजें बनाना असंभव है, कुछ को तेज़ी से बनाना असंभव है, और कुछ को आप गति को तोड़े बिना आपस में मिला नहीं सकते। लेकिन अब, हम अंततः जानते हैं कि वे रेखाएँ कहाँ हैं।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।