सॉफ्टवेयर के लिए मॉडल जाँच
मॉडल जाँच स्वचालित रूप से सत्यापित करती है कि क्या किसी सिस्टम का मॉडल उसके पहुंच योग्य अवस्थाओं का संपूर्ण अन्वेषण करके एक अस्थायी-तर्क विनिर्देश को संतुष्ट करता है।
Definition
मॉडल जाँच एक स्वचालित सत्यापन तकनीक है जो, किसी सिस्टम के परिमित-अवस्था मॉडल और एक अस्थायी-तर्क विनिर्देश को देखते हुए, संपूर्ण रूप से जाँच करती है कि क्या विनिर्देश सही है और यदि नहीं, तो एक काउंटरउदाहरण ट्रेस उत्पन्न करती है।
Scope
यह विषय अस्थायी-तर्क गुणों (सुरक्षा और जीवंतता) के विरुद्ध परिमित-अवस्था और समवर्ती प्रणालियों के स्वचालित सत्यापन, अवस्था-विस्फोट समस्या और इससे निपटने की तकनीकों (बाइनरी डिसीजन डायग्राम के साथ प्रतीकात्मक प्रतिनिधित्व, आंशिक-क्रम न्यूनीकरण, अमूर्तन), SAT/SMT के साथ बाउंडेड मॉडल जाँच, और सॉफ्टवेयर के लिए काउंटरउदाहरण-निर्देशित अमूर्तन शोधन को शामिल करता है।
Core questions
- सभी पहुंच योग्य अवस्थाओं का अन्वेषण करके किसी गुण को कैसे सत्यापित किया जा सकता है?
- अवस्था-विस्फोट समस्या क्या है और इसे कैसे कम किया जाता है?
- प्रतीकात्मक और बाउंडेड विधियाँ मॉडल जाँच को कैसे बढ़ाती हैं?
- अनंत-अवस्था सॉफ्टवेयर प्रणालियों को परिमित मॉडल में कैसे अमूर्त किया जाता है?
Key theories
- अस्थायी-तर्क मॉडल जाँच
- क्लार्क, एमर्सन और सिस्टला, और स्वतंत्र रूप से क्विल और सिफाकिस ने अस्थायी-तर्क विनिर्देशों के विरुद्ध परिमित-अवस्था समवर्ती प्रणालियों की स्वचालित रूप से जाँच करने के लिए एल्गोरिदम प्रस्तुत किए।
- प्रतीकात्मक मॉडल जाँच
- बर्च और उनके सहयोगियों ने बाइनरी डिसीजन डायग्राम के साथ अवस्थाओं के सेट को प्रतीकात्मक रूप से दर्शाया, जिससे खगोलीय रूप से कई अवस्थाओं वाली प्रणालियों का सत्यापन संभव हो गया और सरल अवस्था विस्फोट पर काबू पाया गया।
Clinical relevance
मॉडल जाँच का उपयोग हार्डवेयर डिज़ाइन, संचार प्रोटोकॉल, और समवर्ती तथा सुरक्षा-महत्वपूर्ण सॉफ्टवेयर को सत्यापित करने के लिए किया जाता है, जहाँ यह सूक्ष्म बग्स का पता लगाता है जिन्हें परीक्षण से नहीं पकड़ा जा सकता और ऐसे काउंटरउदाहरण प्रदान करता है जो दोषों को इंगित करते हैं। इसका स्वचालन इसे इंटरैक्टिव प्रमेय सिद्ध करने से अलग करता है।
History
प्रोग्रामों के लिए अस्थायी तर्क के पन्यूली के परिचय पर आधारित, क्लार्क और एमर्सन और, स्वतंत्र रूप से, क्विल और सिफाकिस ने लगभग 1981-82 में मॉडल जाँच विकसित की, इस कार्य को बाद में ट्यूरिंग अवार्ड से सम्मानित किया गया। बाइनरी डिसीजन डायग्राम (1990 के दशक) के साथ प्रतीकात्मक मॉडल जाँच और SAT-आधारित बाउंडेड मॉडल जाँच ने इसकी पहुँच को बहुत बढ़ा दिया, और अमूर्तन-शोधन विधियों ने इसे सॉफ्टवेयर तक पहुँचाया।
Debates
- अवस्था विस्फोट का मुकाबला करना
- केंद्रीय चुनौती यह है कि सिस्टम के आकार के साथ अवस्थाओं की संख्या तेजी से बढ़ती है; शोधकर्ता सत्यापन को व्यवहार्य बनाए रखने के लिए प्रतीकात्मक प्रतिनिधित्व, अमूर्तन, आंशिक-क्रम न्यूनीकरण और बाउंडेड जाँच के सर्वोत्तम मिश्रण पर बहस करते हैं।
Key figures
- Edmund Clarke
- E. Allen Emerson
- Joseph Sifakis
- Kenneth McMillan
- Amir Pnueli
Related topics
Seminal works
- clarke1986
- queille1982
- burch1992
Frequently asked questions
- मॉडल जाँच प्रमेय सिद्ध करने से कैसे भिन्न है?
- मॉडल जाँच पूरी तरह से स्वचालित है और परिमित या अमूर्त मॉडल के लिए सिस्टम के अवस्था स्थान का संपूर्ण अन्वेषण करती है, जबकि प्रमेय सिद्ध करना तार्किक कटौती (अक्सर इंटरैक्टिव रूप से) का उपयोग करता है और अनंत-अवस्था प्रणालियों को संभाल सकता है लेकिन इसके लिए अधिक मानवीय मार्गदर्शन की आवश्यकता होती है।
- अवस्था-विस्फोट समस्या क्या है?
- यह पहुंच योग्य अवस्थाओं की संख्या में घातीय वृद्धि है क्योंकि एक सिस्टम में घटक या चर बढ़ते हैं, जो सरल मॉडल जाँच को सीमित करता है और प्रतीकात्मक, बाउंडेड और अमूर्तन-आधारित तकनीकों को प्रेरित करता है।