कार्यक्रमों का स्वचालित परीक्षण

परिचय

लंबे समय से यह माना जाता था कि सॉफ्टवेयर दोषों का पता लगाने के लिए कार्यक्रमों का गतिशील विश्लेषण बहुत भारी था, और परिणाम प्रयास और संसाधनों को सही नहीं ठहराते हैं। हालांकि, आधुनिक सॉफ्टवेयर उद्योग के विकास में दो महत्वपूर्ण रुझान हमें इस समस्या पर नए सिरे से विचार करने की अनुमति देते हैं। एक तरफ, सॉफ्टवेयर की मात्रा और जटिलता में निरंतर वृद्धि के साथ, त्रुटियों और गुणवत्ता नियंत्रण का पता लगाने का कोई भी स्वचालित साधन उपयोगी और मांग में हो सकता है। दूसरी ओर, आधुनिक कंप्यूटिंग सिस्टम की उत्पादकता में निरंतर वृद्धि हमें जटिल कंप्यूटिंग समस्याओं को कुशलता से हल करने की अनुमति देती है। गतिशील विश्लेषण के क्षेत्र में हाल के शोध कार्य, जैसे एसएजीई , केएलई और एवलांच , प्रदर्शित करते हैं कि इस दृष्टिकोण की अंतर्निहित जटिलता के बावजूद, इसका उपयोग उचित है, कम से कम कुछ कार्यक्रमों के वर्ग के लिए।

गतिशील बनाम स्टेटिक विश्लेषण

गतिशील विश्लेषण के अधिक प्रभावी विकल्प के रूप में, स्थैतिक विश्लेषण को अक्सर माना जाता है। स्थैतिक विश्लेषण के मामले में, अध्ययन के तहत कार्यक्रम को लॉन्च किए बिना संभावित त्रुटियों की खोज की जाती है, उदाहरण के लिए, आवेदन के स्रोत कोड द्वारा। आमतौर पर, इस मामले में एक सार प्रोग्राम मॉडल का निर्माण किया जाता है, जो वास्तव में, विश्लेषण का उद्देश्य है।
इस मामले में, स्थैतिक विश्लेषण की निम्नलिखित विशिष्ट विशेषताओं पर जोर दिया जाना चाहिए:

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

स्थैतिक विश्लेषण के विपरीत, गतिशील विश्लेषण किया जाता है जबकि कार्यक्रम चल रहा है। इस मामले में:

• प्रोग्राम को चलाने के लिए, कुछ इनपुट की आवश्यकता होती है।
• डायनामिक विश्लेषण केवल विशिष्ट इनपुट डेटा द्वारा परिभाषित पथ पर दोषों का पता लगाता है; कार्यक्रम के अन्य भागों में स्थित दोषों का पता नहीं लगाया जाएगा।
• अधिकांश कार्यान्वयन में, झूठी सकारात्मकता की उपस्थिति को बाहर रखा गया है, क्योंकि कार्यक्रम में उस समय एक त्रुटि का पता लगाया जाता है; इस प्रकार, पता चला त्रुटि प्रोग्राम मॉडल के विश्लेषण के आधार पर की गई भविष्यवाणी नहीं है, बल्कि इसकी घटना के तथ्य का एक बयान है।

आवेदन

स्वचालित परीक्षण मुख्य रूप से उन कार्यक्रमों के लिए किया जाता है जिनके लिए किसी भी इनपुट डेटा के साथ संचालन और सुरक्षा सर्वोच्च प्राथमिकताएं हैं: वेब सर्वर, एसएसएच क्लाइंट / सर्वर, सैंडबॉक्सिंग, नेटवर्क प्रोटोकॉल।

फ़ज परीक्षण (फ़ज़िंग)

फ़ज़िंग एक परीक्षण तकनीक है जिसमें किसी प्रोग्राम के इनपुट को अमान्य, अनपेक्षित, या यादृच्छिक डेटा सबमिट किया जाता है।

इस दृष्टिकोण का मुख्य विचार बेतरतीब ढंग से "म्यूटेट" करना है, अर्थात्। मनमाना स्थानों में अपेक्षित इनपुट डेटा बदलें। सभी फ़ज़र्स लगभग उसी तरह से काम करते हैं, जो आपको विशिष्ट बाइट्स या बाइट्स के अनुक्रम के साथ इनपुट डेटा को म्यूट करने पर कुछ प्रतिबंध लगाने की अनुमति देता है। एक उदाहरण के रूप में, हम उल्लेख कर सकते हैं: zzuf (linux) , minifuzz (Windows), filefuzz (Windows)। प्रोटोकॉल फ़ज़र्स: PROTOS (WAP, HTTP- उत्तर, LDAP, SNMP, SIP) (जावा) , SPIKE (linux) । फजर फ्रेमवर्क: सुल्ली (जटिल डेटा संरचना बनाने के लिए एक रूपरेखा) ।
फ़ज़ टेस्टिंग ऑटोमैटिक टेस्टिंग, ब्रूट फ़ोर्स मेथड का अग्रदूत है। इस दृष्टिकोण के फायदों में से केवल इसकी सादगी है। स्पष्ट दोष यह है कि फ़्यूज़र को प्रोग्राम की आंतरिक संरचना के बारे में कुछ भी पता नहीं है और अंततः, कोड को पूरी तरह से कवर करने के लिए, यह खगोलीय संख्या विकल्पों के माध्यम से छांटने के लिए मजबूर है (जैसा कि आप अनुमान लगा सकते हैं, पूर्ण गणना इनपुट डेटा ओ (सी ^ एन) के आकार से काफी तेजी से होता है) सी> 1)।

नई पीढ़ी के लेखक (समीक्षा)

तार्किक, लेकिन स्वत: परीक्षण के विचार की इतनी सरल निरंतरता दृष्टिकोण और कार्यक्रमों का उद्भव नहीं था जो आपको अध्ययन के तहत कार्यक्रम की बारीकियों को ध्यान में रखते हुए, उत्परिवर्तित इनपुट डेटा पर प्रतिबंध लगाने की अनुमति देते हैं।

ट्रैकिंग एक कार्यक्रम में टैग किए गए डेटा

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

कोड इंस्ट्रूमेंटेशन

अध्ययन के तहत कार्यक्रम का कोड विश्लेषण के लिए सुविधाजनक रूप में कम हो गया है। उदाहरण के लिए, आंतरिक वैलग्राइंड (हिमस्खलन) प्रतिनिधित्व का उपयोग किया जाता है, या llvm bytecode कार्यक्रम (KLEE), जो पार्स करना आसान है, का विश्लेषण किया जाता है।

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

बूलियन बाधाओं का समाधान

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

पर्यावरण मॉडलिंग

सिस्टम कॉल को इंटरसेप्ट करने के अलावा, बूलियन फ़ार्मुलों के "सॉल्वर" के लिए स्वचालित रूप से स्थिति उत्पन्न करने के लिए, एनालाइज़र को कार्य को औपचारिक बनाने की आवश्यकता होती है। इनपुट फ़ाइल, रजिस्टरों का एक सेट और कार्यक्रम का पता स्थान (मेमोरी) बूलियन "गोताखोर" के सरणियों का उपयोग करके दर्शाया गया है।

एक कार्यक्रम में रास्तों की खोज

"सॉल्वर" से एक प्रतिक्रिया प्राप्त करने के बाद, उपकरण जांच के तहत सशर्त संक्रमण को पलटने के लिए इनपुट डेटा पर एक शर्त प्राप्त करता है या पता चलता है कि यह हमेशा सही या गलत है। हालत के प्रत्येक संस्करण कार्यक्रम में एक नया स्वतंत्र पथ बनाता है, और कार्यक्रम को स्वतंत्र रूप से पूरा करने के लिए प्रत्येक पथ और शर्तों पर विचार करना पड़ता है, अर्थात। प्रत्येक शाखा अनुदेश पर पथ " कांटा ", इनपुट के आधार पर। नए इनपुट डेटा अध्ययन के तहत कार्यक्रम के पहले बंद किए गए आधार ब्लॉक को खोल सकते हैं, और इसी तरह। संपूर्ण परीक्षण के लिए, कार्यक्रम में सभी संभावित रास्तों की पूरी गणना आवश्यक है। पथों की संख्या की वृद्धि दर के बाद से, हालांकि जानवर बल विधि (~ O (2 ^ n), जहां n इनपुट डेटा के आधार पर सशर्त संक्रमणों की संख्या है) की तुलना में काफी कम है, यह अभी भी महत्वपूर्ण बना हुआ है। कुछ रास्तों के विश्लेषण को प्राथमिकता देने के लिए, विश्लेषक विभिन्न उत्तराधिकारियों का उपयोग करने के लिए मजबूर हैं। विशेष रूप से, वे उस पथ की पसंद के बीच अंतर करते हैं जो सबसे बड़ी संख्या में खुला (नए) बेस ब्लॉक (एवाल्चे, केएलई) और यादृच्छिक पथ (केएलईई) की पसंद को कवर करता है।

हिमस्खलन

हिमस्खलन गतिशील विश्लेषण के माध्यम से एक सॉफ्टवेयर दोष का पता लगाने वाला उपकरण है। एवलांच, वाल्ग्रिंड द्वारा प्रदान किए गए कार्यक्रम के गतिशील इंस्ट्रूमेंटेशन क्षमताओं का उपयोग करता है और कार्यक्रम निष्पादन पथ का विश्लेषण करता है। इस विश्लेषण का परिणाम या तो इनपुट डेटा का एक सेट है, जिस पर प्रोग्राम में कोई त्रुटि होती है, या नए परीक्षण डेटा का एक सेट जो आपको पहले निष्पादित नहीं किए जाने की अनुमति देता है और तदनुसार, अभी तक सत्यापित किए गए प्रोग्राम टुकड़े नहीं हैं। इस प्रकार, परीक्षण डेटा का एक सेट होने पर, हिमस्खलन पुनरावृत्त गतिशील विश्लेषण को कार्यान्वित करता है, जिसमें कार्यक्रम को विभिन्न स्वचालित रूप से उत्पन्न परीक्षण डेटा पर बार-बार निष्पादित किया जाता है, प्रत्येक नए लॉन्च में इस तरह के परीक्षणों के साथ प्रोग्राम कोड की कवरेज बढ़ जाती है।

काम की सामान्य योजना

हिमस्खलन उपकरण में 4 मुख्य घटक होते हैं: दो Valgrind एक्सटेंशन मॉड्यूल (प्लगइन्स) - Tracegrind और Covgrind , एक STP बाधा सत्यापन उपकरण और एक नियंत्रण मॉड्यूल।

Tracegrind गतिशील रूप से विश्लेषण किए गए कार्यक्रम में टैग किए गए डेटा के प्रवाह की निगरानी करता है और इसके असफल भागों को दरकिनार करने और खतरनाक कार्यों को ट्रिगर करने के लिए स्थितियां एकत्र करता है। इन स्थितियों को नियंत्रण मॉड्यूल द्वारा एसटीपी को उनकी व्यवहार्यता की जांच करने के लिए प्रेषित किया जाता है। यदि कोई भी स्थिति संभव है, तो एसटीपी शर्तों में शामिल सभी चर के उन मूल्यों को निर्धारित करता है (इनपुट फ़ाइल के बाइट सहित) जो स्थिति को सच बनाते हैं।

• यदि खतरनाक ऑपरेशन के संचालन के लिए शर्तें संतुष्ट हैं, तो प्रोग्राम को नियंत्रण मॉड्यूल द्वारा फिर से लॉन्च किया गया है (इस बार बिना किसी इंस्ट्रूमेंटेशन के) त्रुटि इनपुट की पुष्टि के लिए इसी इनपुट फ़ाइल के साथ।
• कार्यक्रम के असफल भागों को दरकिनार करने के लिए संभव स्थितियां नए प्रोग्राम लॉन्च के लिए संभावित इनपुट फ़ाइलों के सेट को निर्धारित करती हैं। इस प्रकार, प्रत्येक कार्यक्रम के शुरू होने के बाद, एसटीपी उपकरण स्वचालित रूप से बाद में विश्लेषण शुरू होने के लिए बहुत सारी इनपुट फाइलें उत्पन्न करता है।
• अगला, कार्य सबसे "दिलचस्प" इनपुट डेटा के इस सेट से चुनने का उदय होता है, अर्थात्। सबसे पहले, इनपुट डेटा जिस पर त्रुटि होने की सबसे अधिक संभावना है, उस पर कार्रवाई की जानी चाहिए। इस समस्या को हल करने के लिए, एक हेयुरिस्टिक मेट्रिक का उपयोग किया जाता है - कार्यक्रम में पहले से पास किए गए बेस ब्लॉक्स की संख्या (बेस ब्लॉक को यहां इस अर्थ में समझा जाता है, जैसा कि वैलग्राइंड ढांचे द्वारा परिभाषित किया गया है)। ह्यूरिस्टिक मूल्य को मापने के लिए, कोग्रिंड घटक का उपयोग किया जाता है, जिसके कार्य में संभावित रनटाइम त्रुटियों को ठीक करना भी शामिल है। कोवरग्रिंड ट्रेसग्रिंड की तुलना में बहुत हल्का मॉड्यूल है, इसलिए पहले से प्राप्त इनपुट फ़ाइलों के लिए अपेक्षाकृत मूल्य को मापना अपेक्षाकृत जल्दी संभव है और इसके उच्चतम मूल्य के साथ इनपुट फ़ाइल का चयन करें।

प्रतिबंध

• एक चिह्नित इनपुट फ़ाइल या सॉकेट
• त्रुटि विश्लेषण शून्य संकेतक को शून्य से विभाजित करने और विभाजित करने के लिए सीमित है।

परिणाम

हिमस्खलन के बगफंडिंग प्रदर्शन को बड़ी संख्या में खुले स्रोत परियोजनाओं पर परीक्षण किया गया है।

• qtdump (libquicktime-1.1.3)। तीन दोष नल सूचक की डेरेफेरिंग के साथ जुड़े हुए हैं, एक अनंत लूप की उपस्थिति के साथ, दूसरे मामले में एक गलत पते (विभाजन त्रुटि) के लिए एक अपील है। कुछ दोष डेवलपर द्वारा तय किए जाते हैं।
• flvdumper ( gnash -0.8.6)। एक दोष की तत्काल घटना आवेदन द्वारा उपयोग किए जाने वाले बूस्ट लाइब्रेरी में एक अपवाद के कारण होती है (बूस्ट लाइब्रेरी के आंतरिक बिंदुओं में से एक शून्य हो जाता है)। चूंकि एप्लिकेशन स्वयं अपवाद नहीं हुआ है जो कि हुआ है, प्रोग्राम SIGABRT सिग्नल के साथ समाप्त होता है। दोष डेवलपर द्वारा तय किया गया है।
• cjpeg (libjpeg7)। एप्लिकेशन फ़ाइल से शून्य मान पढ़ता है और, उचित सत्यापन के बिना, इसे एक भाजक के रूप में उपयोग करता है, जो फ्लोटिंग-पॉइंट अपवाद और SIGFPE सिग्नल के साथ प्रोग्राम की समाप्ति की ओर जाता है। दोष डेवलपर द्वारा तय किया गया है।
• swfdump ( स्वफ़टल्स-0.9.0 )। दोनों दोषों की घटना नल सूचक के डेरेफेरिंग के साथ जुड़ी हुई है।

क्ली

केएलई एवलांच से कुछ अलग है जिसमें यह संदिग्ध स्थानों की तलाश नहीं करता है, लेकिन जितना संभव हो उतना कोड को कवर करने की कोशिश करता है और कार्यक्रम में रास्तों का विस्तृत विश्लेषण करता है। सामान्य तौर पर, केएलईई स्कीम एवलांच के समान है, लेकिन समस्या को हल करने के लिए अन्य बुनियादी उपकरणों का उपयोग करता है, जो इसकी सीमाओं को लागू करता है और इसके फायदे देता है।

• Avalanche द्वारा उपयोग किए गए Valgrind के इंस्ट्रूमेंटेशन के बजाय, KLEE, llvm bytecode में प्रोग्राम करता है। तदनुसार, यह आपको किसी भी प्रोग्रामिंग भाषा में प्रोग्राम का विश्लेषण करने की अनुमति देता है जिसके लिए एक llvm बैकएंड है।
• बूलियन बाधाओं की समस्या को हल करने के लिए, KLEE भी STP का उपयोग करता है।
• KLEE भी लगभग 50 सिस्टम कॉल को स्वीकार करता है, जिससे कई आभासी प्रक्रियाएं एक दूसरे के साथ हस्तक्षेप किए बिना समानांतर में चलने की अनुमति देती हैं।
• एसटीपी के लिए अनुरोधों का अनुकूलन और कैशिंग।

केएलई एक प्रतीकात्मक आभासी मशीन है जहां प्रतीकात्मक प्रक्रियाओं को समानांतर में (शब्दावली केएलईई: राज्यों के ढांचे में) निष्पादित किया जाता है, जहां प्रत्येक प्रक्रिया अध्ययन के तहत कार्यक्रम में से एक पथ है। कार्यक्रम में प्रत्येक शाखा पर ऐसी प्रक्रियाओं (सिस्टम के माध्यम से नहीं) के कांटों का प्रभावी कार्यान्वयन हमें एक साथ बड़ी संख्या में पथों का विश्लेषण करने की अनुमति देता है।
यात्रा करने वाले प्रत्येक अनूठे पथ के लिए, KLEE उस पथ पर जाने के लिए आवश्यक इनपुट डेटा के सेट को बचाता है।
KLEE क्षमताएं आपको कम लागत के साथ किन्हीं भी दो कार्यों की समतुल्यता की जांच करने की अनुमति देती हैं (एक व्यापक एपीआई प्रदान की जाती है) ( एक कार्यशील प्रोटोटाइप के खिलाफ समान कार्यक्षमता की जाँच करना, निर्दिष्ट इनपुट डेटा की पूरी श्रृंखला में)।
निम्न उदाहरण इस कार्यक्षमता को दिखाता है:

अहस्ताक्षरित mod_opt ( अहस्ताक्षरित x, अहस्ताक्षरित y ) {
अगर ( y ( // y ) == y ) // दो की शक्ति?
वापसी x & ( y x 1 ) ;
अन्यथा
वापसी x % y ;
}
अहस्ताक्षरित आधुनिक ( अहस्ताक्षरित x, अहस्ताक्षरित y ) {
वापसी x % y ;
}
इंट मेन ( ) {
अहस्ताक्षरित x, y ;
प्रतीकात्मक बनाना ( और x, आकारोफ़ ( x ) ) ;
प्रतीकात्मक बनाना ( और y, आकार-आकार ( y ) ) ;
मुखर ( mod ( x, y ) == mod_opt ( x, y ) ) ;
वापसी 0 ;
}

इस उदाहरण में KLEE को चलाकर, आप इनपुट मानों की संपूर्ण श्रेणी में दो कार्यों की समता को सत्यापित कर सकते हैं (y! = 0)। दावे में शर्त पूरी न होने की समस्या को हल करने के लिए, KLEE, सभी संभावित रास्तों की गणना के आधार पर, इस निष्कर्ष पर पहुंचता है कि दो कार्य मानों की पूरी श्रृंखला पर बराबर हैं।

परिणाम

वास्तविक परीक्षा परिणाम प्राप्त करने के लिए, लेखकों ने कोरुटिल्स 6.11 में कार्यक्रमों के पूरे सेट का विश्लेषण किया। कोड कवरेज का औसत प्रतिशत 94% था। कुल में, प्रोग्राम ने इनपुट डेटा के 3321 सेट उत्पन्न किए, जिससे कोड के संपूर्ण निर्दिष्ट प्रतिशत को कवर किया जा सके। साथ ही, 10 अद्वितीय त्रुटियां पाई गईं, जिन्हें पैकेज के डेवलपर्स द्वारा कार्यक्रमों में वास्तविक दोष के रूप में मान्यता दी गई थी, जो एक बहुत अच्छी उपलब्धि है, क्योंकि इस कार्यक्रम के सेट को 20 से अधिक वर्षों के लिए विकसित किया गया है और अधिकांश त्रुटियों को समाप्त कर दिया गया है।

प्रतिबंध

• बहु-थ्रेडेड अनुप्रयोगों, प्रतीकात्मक फ्लोटिंग-पॉइंट डेटा (एसटीपी प्रतिबंध), कोडांतरक आवेषण के लिए कोई समर्थन नहीं।
• परीक्षित अनुप्रयोग को llvm-बाइट कोड (साथ ही इसके पुस्तकालयों!) में संकलित किया जाना चाहिए।
• प्रभावी विश्लेषण के लिए, आपको कोड को संपादित करने की आवश्यकता है।

प्रारंभिक निष्कर्ष

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

निष्कर्ष

यह लेख के विषय को जारी रखने की योजना बनाई गई है (हिमस्खलन और केएलई के साथ कुछ अनुभव के परिणाम, साथ ही केएलई और एवलांच की तुलना, एस 2 ई की समीक्षा (https://s2e.epfl.ch) (चयन प्रतीकात्मक निष्पादन)) हैबर के पाठकों से सकारात्मक प्रतिक्रिया के अधीन है।

लेख में निम्नलिखित कार्यों के टुकड़े शामिल हैं: हिमस्खलन_कार्टिकल , केएलईई , फ़ज़ परीक्षण का उपयोग ।