GCD: Garbled, Corrected, Demonstrandum -- Fixing and Proving Go's Extended GCD Implementation
यह शोध पत्र Go के एक्सटेंडेड GCD कार्यान्वयन में दो महत्वपूर्ण विचलनों की पहचान और सुधार करता है जो RSA कुंजी निर्माण से समझौता करते हैं, और तत्पश्चात Gobra और Lean सत्यापन उपकरणों का उपयोग करके सुधारा गया कोड की शुद्धता और समाप्ति को सिद्ध करता है, साथ ही यह भी प्रदर्शित करता है कि AI एजेंट औपचारिक प्रमाणों को परिष्कृत करने में कैसे सहायता कर सकते हैं।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कल्पना कीजिए कि आप एक उच्च-सुरक्षा डिजिटल तिजोरी (जैसे कि ऑनलाइन बैंकिंग या सुरक्षित मैसेजिंग के लिए उपयोग की जाने वाली तिजोरियाँ) बना रहे हैं। इस तिजोरी को लॉक और अनलॉक करने के लिए, आपको एक बहुत ही विशिष्ट, जटिल गणितीय कुंजी (key) की आवश्यकता होगी। कंप्यूटर विज्ञान की दुनिया में, यह कुंजी एक्स्टेंडेड ग्रेटेस्ट कॉमन डिवीज़र (GCD) एल्गोरिदम नामक एक रेसिपी का उपयोग करके बनाई जाती है।
यह शोध पत्र इस बारे में है कि शोधकर्ताओं की एक टीम ने गो (Go) प्रोग्रामिंग भाषा के "रसोईघर" (kitchen) में जाकर यह जाँचने के लिए कि क्या इस कुंजी के लिए रेसिपी का सही ढंग से पालन किया जा रहा है। उन्होंने पाया कि रेसिपी में थोड़ा बदलाव किया गया था, और उन्होंने इसे ठीक किया और साथ ही गणितीय रूप से यह भी सिद्ध किया कि नया संस्करण पूरी तरह से काम करता है।
यहाँ उनकी खोज की कहानी है, जिसे सरल भागों में विभाजित किया गया है:
1. "कॉपी-पेस्ट" की गलती
गो (Go) डेवलपर्स अपने सॉफ़्टवेयर को सख्त सरकारी सुरक्षा मानकों को पूरा करने के लिए अपडेट करना चाहते थे। ऐसा करने के लिए, उन्होंने एक भरोसेमंद, प्रसिद्ध स्रोत बोरिंगएसएसएल (BoringSSL) (गूगल द्वारा उपयोग की जाने वाली एक सुरक्षित लाइब्रेरी) से एक रेसिपी ली और उसे गो (Go) में "पोर्ट" (अनुवादित) किया।
इसे ऐसे समझें जैसे किसी प्रसिद्ध शेफ ने आपको केक की एक गुप्त रेसिपी दी। आप उस रेसिपी को पढ़ने में आसान बनाने के लिए उसे अपने हाथ की लिखावट में फिर से लिखते हैं। शोध पत्र का दावा है कि इसे फिर से लिखते समय, गो डेवलपर्स ने अनजाने में दो महत्वपूर्ण चरणों को बदल दिया।
- समस्या: मूल रेसिपी में एक सख्त नियम था: "यदि आप इन दो संख्याओं को जोड़ते हैं, और परिणाम बहुत बड़ा है, तो आपको एक ही समय में दोनों संख्याओं से एक विशिष्ट राशि घटानी होगी।" यह केक को ढहने से बचाने के लिए किया जाता है।
- बग (Bug): गो (Go) वर्शन ने प्रत्येक संख्या के लिए अलग-अलग "बहुत बड़ा" होने की जाँच की। यह आटे और चीनी को स्वतंत्र रूप से जाँचने जैसा था। इसने उस गणितीय संतुलन (invariants) को तोड़ दिया जो यह गारंटी देता है कि कुंजी सही है।
- आश्चर्य: तीन अलग-अलग मानव विशेषज्ञों ने कोड की समीक्षा की और इस गलती को पकड़ नहीं पाए। यह इतना सूक्ष्म था कि यह उनके जाल से बच निकला।
2. "बहुत बड़ा" सामग्री (Ingredient)
दूसरा मुद्दा अनुमति दी गई सामग्रियों के आकार के बारे में था।
- नियम: मूल रेसिपी कहती थी, "पहली सामग्री हमेशा दूसरी से छोटी होनी चाहिए।"
- बदलाव: गो (Go) वर्शन ने पहली सामग्री को दूसरी से बड़ा होने की अनुमति दे दी।
- समाधान: शोधकर्ताओं को इस एक के लिए कोड बदलने की आवश्यकता नहीं थी। इसके बजाय, उन्हें "प्रूफ" (गणितीय गारंटी) को अपडेट करना था ताकि यह दिखाया जा सके कि बड़ी सामग्रियों के साथ भी रेसिपी काम करती है।
3. जादुई जासूस (Gobra)
यह सिद्ध करने के लिए कि उन्होंने बग्स को ठीक कर दिया है, शोधकर्ताओं ने गोबरा (Gobra) नामक टूल का उपयोग किया।
- उपमा: एक अत्यंत सख्त, अति-सतर्क रोबोट इंस्पेक्टर की कल्पना करें। आप इसे कोड और नियमों (specifications) की एक सूची देते हैं। रोबोट केवल कोड चलाता नहीं है; यह कोड के चलने के हर संभव तरीके का अनुकरण (simulate) करता है, यह सुनिश्चित करने के लिए कि यह कभी भी नियमों को नहीं तोड़ता है।
- परिणाम: रोबोट ने पुष्टि की कि एक बार "सिंक्रोनाइज़ेशन बग" को ठीक करने के बाद, कोड 100% सही था। वास्तव में, क्योंकि फिक्स ने अनावश्यक चरणों को हटा दिया था, नया कोड बग वाले वर्शन की तुलना में 24% तेज़ चला।
4. एआई असिस्टेंट (AI Assistant)
शोधकर्ताओं ने सारा भारी काम अकेले नहीं किया। उन्होंने एक एआई एजेंट (एक स्मार्ट कंप्यूटर प्रोग्राम) की मदद ली।
- यह कैसे काम करता था: एआई एक अथक प्रशिक्षु (apprentice) की तरह काम करता था। जब रोबोट इंस्पेक्टर (Gobra) कहता, "यह हिस्सा समझ में नहीं आ रहा है," तो एआई नियमों या कोड में बदलाव का सुझाव देता।
- सावधानी: एआई ने शुरू में यह मान लिया था कि कोड एकदम सही है और उसने गणित को फिट करने की कोशिश की। मानव शोधकर्ताओं को एआई को बताना पड़ा, "नहीं, कोड वास्तव में गलत है; अंतर को खोजो।" एक बार जब एआई यह समझ गया, तो वह अविश्वसनीय रूप से सहायक हो गया, सुझाव देने और गणितीय प्रमाण लिखने में मदद करने लगा।
5. निष्कर्ष (Takeaway)
शोध पत्र तीन मुख्य सबक प्रस्तुत करता है:
- विशेषज्ञ भी सूक्ष्म गलतियाँ करते हैं: तीन मानव समीक्षकों ने एक महत्वपूर्ण बग को मिस कर दिया जिसे एक फॉर्मल प्रूफ टूल ने ढूंढ निकाला।
- फॉर्मल वेरिफिकेशन शक्तिशाली है: गोबरा (Gobra) जैसे टूल का उपयोग करना एक गणितीय गारंटी होने जैसा है कि आपका कोड काम करता है, बजाय इसके कि आप केवल इस उम्मीद में रहें कि यह कुछ परीक्षणों को पास करने के कारण काम कर रहा है।
- एआई एक बेहतरीन साथी है: एआई मनुष्यों को ये जटिल प्रमाण लिखने में मदद कर सकता है, लेकिन मनुष्यों को एआई को कोड को स्वीकार करने के बजाय उस पर सवाल उठाने के लिए निर्देशित करने की आवश्यकता होती है।
संक्षेप में: शोधकर्ताओं ने गो (Go) के स्टैंडर्ड लाइब्रेरी में एक महत्वपूर्ण सुरक्षा एल्गोरिदम में छिपी खामी को पाया, उसे ठीक किया, गणितीय रूप से सिद्ध किया कि समाधान काम करता है, और यह भी दिखाया कि सुधार ने वास्तव में सॉफ़्टवेयर को तेज़ बना दिया। उन्होंने यह सब मानव अंतर्दृष्टि, स्वचालित प्रूफ टूल्स और एआई सहायता के संयोजन का उपयोग करके किया।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।