Countering the Path Explosion Problem in the Symbolic Execution of Hardware Designs
यह शोध पत्र पीसवाइज कंपोजिशन (piecewise composition) को प्रस्तुत करता है, जो हार्डवेयर डिजाइनों के लिए एक नवीन सिम्बोलिक एक्जीक्यूशन तकनीक है जो पथ अन्वेषण (path exploration) को SMT सॉल्वर पर ऑफलोड करने के लिए मॉड्यूलर संरचना का लाभ उठाती है, जिससे नेटलिस्ट ट्रांसलेशन के बिना सीधे RTL Verilog का विश्लेषण करते हुए रनटाइम में 97% की कमी और अन्वेषित पथों में एक परिमाण (order-of-magnitude) की कमी प्राप्त होती है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कल्पना कीजिए कि आप एक जासूस हैं जो एक विशाल, भविष्यवादी शहर के भीतर एक रहस्य को सुलझाने की कोशिश कर रहे हैं। यह शहर एक कंप्यूटर चिप है, सिलिकॉन का एक छोटा सा टुकड़ा जो आपके फोन से लेकर पृथ्वी की कक्षा में घूम रहे उपग्रहों तक सब कुछ नियंत्रित करता है। यह सुनिश्चित करने के लिए कि शहर सुरक्षित है, आपको हर एक सड़क, गली और छिपे हुए दरवाजे की जांच करनी होगी ताकि कोई भी बुरे लोग अंदर न घुस सकें या नियमों को तोड़ न सके। विज्ञान का यह क्षेत्र 'हार्डवेयर वेरिफिकेशन' (hardware verification) कहलाता है, जो डिजिटल रूप से एक सुरक्षा निरीक्षक के समान है जो यह सुनिश्चित करता है कि किसी भी पुल पर वाहन चलाने से पहले वह ढहे नहीं।
जासूसों द्वारा इस काम के लिए इस्तेमाल किया जाने वाला मुख्य उपकरण "सिम्बॉलिक एक्जीक्यूशन" (symbolic execution) कहलाता है। विशिष्ट चाबियों के एक खास सेट के साथ एक समय में एक सड़क पर चलने के बजाय, सिम्बॉलिक एक्जीक्यूशन एक जादुई मानचित्र होने जैसा है जो आपको एक ही समय में हर संभव सड़क पर चलने की अनुमति देता है। आप विशिष्ट संख्याओं को "भूतों" (ghosts) से बदल देते हैं जो किसी भी संख्या का प्रतिनिधित्व करते हैं, और देखते हैं कि शहर हर काल्पनिक संभावना के प्रति कैसी प्रतिक्रिया देता है। समस्या क्या है? जैसे-जैसे शहर बड़ा और अधिक जटिल होता जाता है, सड़कों की संख्या इतनी तेजी से बढ़ती है कि उन सभी की जांच करना असंभव हो जाता है। इसे "पाथ एक्सप्लोजन प्रॉब्लम" (path explosion problem) के रूप में जाना जाता है। यह एक फायरहोस (firehose) से पानी पीने की तरह है; पानी (या इस मामले में, जांचने योग्य पथों की संख्या) इतनी तेजी से बाहर आता है कि लीक खोजने से पहले ही आप अभिभूत हो जाते हैं। यदि हम हर पथ की जांच नहीं कर सकते हैं, तो हम एक छिपे हुए ट्रैपडोर (trapdoor) को मिस कर सकते हैं जिसका उपयोग हैकर्स गुप्त जानकारी चुराने या सिस्टम को क्रैश करने के लिए कर सकते हैं।
यहीं पर शोध पत्र "काउंटरिंग द पाथ एक्सप्लोजन प्रॉब्लम इन द सिम्बॉलिक एक्जीक्यूशन ऑफ हार्डवेयर डिजाइन्स" (Countering the Path Explosion Problem in the Symbolic Execution of Hardware Designs) काम आता है। लेखक, काकी रयान और सिंथिया स्टर्टन, एक चतुर नई रणनीति पेश करते हैं जिसे "पीसवाइज कंपोजिशन" (piecewise composition) कहा जाता है। पूरे शहर में एक साथ चलने के बजाय, उन्होंने महसूस किया कि शहर मोहल्लों (या "ब्लॉक्स") में बना हुआ है। आप प्रत्येक मोहल्ले को अलग से एक्सप्लोर कर सकते हैं, उस एकल मोहल्ले के भीतर सभी संभावित मार्गों का मानचित्र बना सकते हैं, और फिर एक सुपर-स्मार्ट कैलकुलेटर (जिसे SMT सॉल्वर कहा जाता है) का उपयोग करके यह पता लगा सकते हैं कि वे अलग-अलग मानचित्र आपस में कैसे जुड़ते हैं।
इसे एक विशाल जिग्सॉ पहेली (jigsaw puzzle) को सुलझाने जैसा समझें। पुराना तरीका यह था कि हर एक टुकड़े को एक-एक करके रखने की कोशिश की जाती थी, इस उम्मीद में कि अंततः तस्वीर उभर आएगी। यदि पहेली के दस लाख टुकड़े हैं, तो आप हमेशा के लिए वहीं रह जाएंगे। नया "पीसवाइज कंपोजिशन" तरीका पहले छोटे, प्रबंधनीय ढेर बनाने जैसा है। आप "आकाश" वाले ढेर को हल करते हैं, फिर "सागर" वाले ढेर को, और फिर "पेड़" वाले ढेर को। एक बार जब आपके पास इन छोटे ढेरों के समाधान होते हैं, तो आप यह देखने के लिए एक त्वरित जांच का उपयोग करते हैं कि वे कैसे जुड़ते हैं। शोध पत्र दिखाता है कि यह दृष्टिकोण केवल थोड़ा ही मदद नहीं करता है; यह काम को नाटकीय रूप से कम कर देता है। जटिल CPUs और सिस्टम-ऑन-चिप्स सहित पांच अलग-अलग ओपन-सोर्स डिजाइनों पर अपने परीक्षणों में, इस पद्धति ने इंजन द्वारा एक्सप्लोर किए जाने वाले पथों की संख्या को लगभग 92% से 99% तक कम कर दिया।
परिणाम चौंकाने वाले थे। नया इंजन पुराने तरीकों की तुलना में 97% तेज़ चला। इसने उन डिजाइनों में सुरक्षा संबंधी बग्स और नियम उल्लंघन को सफलतापूर्वक खोज निकाला जिन्हें पहले पूरी तरह से जांचना बहुत कठिन था। उदाहरण के लिए, एक विशिष्ट प्रोसेसर कोर OR1200 का परीक्षण करते समय, इंजन ने 30 में से 27 ज्ञात बग्स खोज निकाले, जबकि पिछले उपकरणों ने कम खोजे थे। लेखक इस बात पर जोर देते हैं कि यह केवल एक सैद्धांतिक विचार नहीं है; उन्होंने एक कामकाजी उपकरण बनाया है जो वास्तविक कोड (Verilog) को पढ़ता है जिसका उपयोग चिप बनाने के लिए किया जाता है और एक "काउंटर-एग्जांपल" (counter-example) उत्पन्न करता है—निर्देशों का एक विशिष्ट सेट जो साबित करता है कि बग मौजूद है।
हालाँकि, शोध पत्र इस बात पर ध्यान देने में सावधानी बरतता है कि यह सब कुछ तुरंत हल करने वाली कोई जादुई छड़ी नहीं है। यह विधि इस बात पर निर्भर करती है कि हार्डवेयर को एक मॉड्यूलर तरीके से डिजाइन किया गया हो, जिसमें स्पष्ट ब्लॉक हों जो भ्रमित करने वाले तरीकों से आपस में न उलझें। यदि किसी डिजाइन में कुछ अव्यवस्थित कनेक्शन (जैसे "राइट-राइट" डिपेंडेंसी जहाँ दो भाग एक ही समय में एक ही मेमोरी में लिखने की कोशिश करते हैं) हैं, तो टूल अनुमान लगाने के बजाय रुक जाएगा और त्रुटि रिपोर्ट करेगा। लेकिन अधिकांश अच्छी तरह से संरचित हार्डवेयर डिजाइनों के लिए, यह नया दृष्टिकोण संभावनाओं के फायरहोस को नियंत्रित करने का एक तरीका प्रदान करता है, जिससे यह सुनिश्चित करना बहुत आसान हो जाता है कि हमारे डिजिटल शहर सुरक्षित, सुदृढ़ और भविष्य के लिए तैयार हैं।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।