صفحه محصول - پروپوزال پیش بینی خطای نرم افزار با داده کاوی

پروپوزال پیش بینی خطای نرم افزار با داده کاوی (docx) 1 صفحه

دسته بندی : تحقیق

نوع فایل : Word (.docx) ( قابل ویرایش و آماده پرینت )

تعداد صفحات: 1 صفحه

قسمتی از متن Word (.docx) :

دانشکده آموزش‌های الکترونیکی. پایان‌نامه کارشناسی ارشد در رشته مهندسی فناوری اطلاعات (تجارت الکترونیک) استفاده از داده کاوی در پیش‌بینی خطای نرم‌افزار بر اساس متریک‌های کد و وابستگی به کوشش: جواد کامیابی استاد راهنما: دکتر اشکان سامی دی 1390 به نام خدا اظهار نامه اینجانب جواد کامیابی دانشجوی رشته مهندسی فناوری اطلاعات گرایش تجارت الکترونیک دانشکده آموزش‌های الکترونیکی اظهار می‌نمایم که این پایان‌نامه حاصل پژوهش خودم بوده و در جاهایی که از منابع دیگران استفاده کرده‌ام، نشانی و مشخصات کامل آن را نوشته‌ام. همچنین اظهار می‌کنم که تحقیق و موضوع پایان‌نامه‌ام تکراری نیست و تعهد می‌نمایم که بدون مجوز دانشگاه دستاوردهای آن را منتشر ننموده و یا در اختیار غیر قرار ندهم. کلیه حقوق این اثر مطابق با آیین‌نامه مالکیت فکری و معنوی متعلق به دانشگاه شیراز است. نام و نام‌خانوادگی تاریخ و امضا تقدیم به روح پاک شهدای هشت سال دفاع مقدس، آنان که جز به موجب فداکاریشان نیست که اکنون در آرامش نشسته‌ایم و می‌اندیشیم و می‌نویسیم و آزادانه نقد و گاهی هم تخریب می‌کنیم ریزترین‌های دین و میهنمان را حال آن که ممکن بود روزی برسد که برای فکر کردن و نوشتن هم باید از غربی‌ها و شرقی‌ها کسب اجازت کنیم. حال که با لطف و عنایت خداوند متعال رساله حاضر به پایان رسیده است بر خود لازم میدانم که از استاد ارجمند آقای دکتر اشکان سامی به خاطر زحمات فراوان ایشان در راه به ثمر رساندن این تحقیق تشکر و قدردانی نمایم. همچنین از آقایان دکتر امید بوشهریان و دکتر شهریار لطفی به خاطر راهنمایی‌های ارزشمندشان در تدوین این پایان نامه تشکر می‌کنم. در نهایت از تمامی افرادی که من را در راه تحصیل علم یاری نمودند، به خصوص پدر و مادر عزیزم به خاطر زحمات فراوانشان در تمامی عرصه‌های زندگیم تشکر و قدردانی می‌نمایم؛ و برای همه این عزیزان از خداوند متعال درخواست توفیق دارم. و من الله توفیق جواد کامیابی 20 آذر 1390 چکیده: تشخیص خطای نرم افزار با استفاده از درخت وابستگی بر اساس گراف وابستگی نرم افزار به کوشش جواد کامیابی تضمین کیفیت نرم‌افزار همیشه دارای محدودیت‌های زمان و هزینه بوده است. به منظور رسیدن به کیفیت بالا و کاهش محدودیت‌ها، مدیران همواره سعی کرده‌اند تا بخش‌های مستعد خطا را در نرم‌افزار پیش‌بینی نمایند و منابع مذکور را به صورت موثری به این بخش‌ها اختصاص دهند. پیش از این، محققین روش‌های خودکاری را برای کمک به مدیران در این امر مهم معرفی و از آن‌ها استفاده کرده‌اند. روش‌های خودکار مذکور با استفاده از اندازه گیری معیارهای مختلف نرم‌افزار و یافتن ارتباط میان این معیارها و خطاهای نرم‌افزاری، همواره سعی در افزایش سرعت و دقت در پیش‌بینی خطا داشته‌اند. به نوعی می‌توان این معیارها را در چهار دسته که عبارتند از معیارهای پیچیدگی، داده‌های تاریخی، معیارهای طراحی و معیارهای وابستگی، قرار داد. اگرچه معیارهای استفاده شده، تا حدودی موثر هستند اما هنوز هیچکدام موفق به پیش‌بینی تمامی خطاهای موجود نشده‌اند. در این رساله، ما با توسعه دادن مفهوم وابستگی در نرم‌افزار، به معرفی مفهوم جدیدی به نام درخت وابستگی می‌پردازیم. این مفهوم به ما کمک می‌کند تا با در نظر گرفتن تمامی وابستگی‌های مستقیم و غیر مستقیم در بین اجزای نرم‌افزار، معیارهای جدیدی را استخراج نماییم که این معیارها می‌توانند عملاً نتایج مطلوب‌تری را نسبت به معیارهای پیشین، در پیش‌بینی خطا ارائه دهند. TOC \o "1-3" \h \z \u فهرست مطالبعنوان صفحه TOC \o "1-3" \h \z \u 1-مقدمه: PAGEREF _Toc311824329 \h 132- پیشینه پژوهشی: PAGEREF _Toc311824330 \h 162-1-معیارهای نرم‌افزار PAGEREF _Toc311824331 \h 162-2-معیارهای وابستگی: PAGEREF _Toc311824332 \h 172-3-معیارهای تاریخی: PAGEREF _Toc311824333 \h 182-4-بررسی فعالیت‌های گذشته PAGEREF _Toc311824334 \h 192-4-1- بررسی فعالیت‌ها در زمینه معیارهای کد : PAGEREF _Toc311824335 \h 192-4-2- بررسی فعالیت‌ها در زمینه معیارهای تاریخی: PAGEREF _Toc311824336 \h 222-4-3- بررسی فعالیت‌ها در زمینه معیارهای وابستگی: PAGEREF _Toc311824337 \h 253-درخت وابستگی: PAGEREF _Toc311824338 \h 304-فرضیات: PAGEREF _Toc311824339 \h 405-جمع آوری داده: PAGEREF _Toc311824340 \h 415-تحلیل و مقایسه: PAGEREF _Toc311824341 \h 556-نتیجه گیری: PAGEREF _Toc311824342 \h 917-مراجع: PAGEREF _Toc311824343 \h 92 فهرست تصاویر عنوان صفحه TOC \h \z \c "شکل " شکل 1: نمونه‌ای از وابستگی‌های میان کلاس‌ها PAGEREF _Toc311824571 \h 29 شکل 2: نمونه‌ای از وابستگی‌های پیچیده در میان کلاس‌ها PAGEREF _Toc311824572 \h 30 شکل 3: تصویری از نمای کلی برنامه Class Dependency Analyzer PAGEREF _Toc311824573 \h 37 شکل 4: نمونه‌ای از کلاس دیاگرام نمایش داده شده در برنامه Class Dependency Analyzer PAGEREF _Toc311824574 \h 37 شکل 5: نمایش تمامی کلاس‌های وابسته به یک کلاس خاص در برنامه Class Dependency Analyzer PAGEREF _Toc311824575 \h 38 شکل 6: نمونه‌ای از یک گراف جهت دار PAGEREF _Toc311824576 \h 39 شکل 7: ماتریس وابستگی مربوط به گراف جهت دار در شکل شماره 6 PAGEREF _Toc311824577 \h 39 شکل 8: درخت وابستگی تشکیل شده از روی ماتریس وابستگی شکل 7 PAGEREF _Toc311824578 \h 42 شکل 9: متغیر تصادفی، انحراف معیار σ حول محور μ PAGEREF _Toc311824579 \h 53 فهرست نمودارها عنوان صفحه TOC \h \z \c "نمودار " نمودار 1: ارتباط بین جفتگری و انسجام PAGEREF _Toc311824749 \h 28 نمودار 2: بررسی رفتار معیار دقت در هنگام افزایش وابستگی درجه 1 PAGEREF _Toc311824750 \h 46 نمودار 3: بررسی رفتار معیار دقت در هنگام افزایش وابستگی درجه 2 PAGEREF _Toc311824751 \h 46 نمودار 4: بررسی رفتار معیار دقت در هنگام افزایش وابستگی درجه 3 PAGEREF _Toc311824752 \h 47 نمودار 5: مقایسه نتیجه «دقت» در دسته بندی سه نسخه اکلیپس PAGEREF _Toc311824753 \h 54 نمودار 6: مقایسه نتیجه «فراخوانی» در دسته بندی سه نسخه اکلیپس PAGEREF _Toc311824754 \h 55 نمودار 7: مقایسه نتیجه «صحت» در دسته بندی سه نسخه اکلیپس PAGEREF _Toc311824755 \h 56 نمودار 8: مقایسه نتیجه «معیار F» در دسته بندی سه نسخه اکلیپس PAGEREF _Toc311824756 \h 56 نمودار 9: مقایسه نتیجه «منحنی مشخصه عملکرد» در دسته بندی سه نسخه اکلیپس PAGEREF _Toc311824757 \h 57 نمودار 10: مقایسه نتیجه «کاپا» در دسته بندی سه نسخه اکلیپس PAGEREF _Toc311824758 \h 57 نمودار 11: مقایسه نتیجه «انحراف معیار» در دسته بندی سه نسخه اکلیپس PAGEREF _Toc311824759 \h 58 نمودار 12: مقایسه نتیجه «دقت» در دسته بندی آپاچی بر روی متریک‌های کد و درخت وابستگی PAGEREF _Toc311824760 \h 59 نمودار 13: مقایسه نتیجه «فراخوانی» در دسته بندی آپاچی بر روی متریک‌های کد و درخت وابستگی PAGEREF _Toc311824761 \h 60 نمودار 14: مقایسه نتیجه «صحت» در دسته بندی آپاچی بر روی متریک‌های کد و درخت وابستگی PAGEREF _Toc311824762 \h 60 نمودار 15: مقایسه نتیجه «معیار F» در دسته بندی آپاچی بر روی متریک‌های کد و درخت وابستگی PAGEREF _Toc311824763 \h 61 نمودار 16: مقایسه نتیجه «منحنی مشخصه عملکرد» در دسته بندی آپاچی بر روی متریک‌های کد و درخت وابستگی PAGEREF _Toc311824764 \h 61 نمودار 17: مقایسه نتیجه «کاپا» در دسته بندی آپاچی بر روی متریک‌های کد و درخت وابستگی PAGEREF _Toc311824765 \h 62 نمودار 18: مقایسه نتیجه «انحراف معیار» در دسته بندی آپاچی بر روی متریک‌های کد و درخت وابستگی PAGEREF _Toc311824766 \h 62 نمودار 19: قیاس نتیجه «دقت» در دسته‌بندی بر روی کل داده‌ها PAGEREF _Toc311824767 \h 64 نمودار 20: قیاس نتیجه «فراخوانی» در دسته‌بندی بر روی کل داده‌ها PAGEREF _Toc311824768 \h 65 نمودار 21: قیاس نتیجه «صحت» در دسته‌بندی بر روی کل داده‌ها PAGEREF _Toc311824769 \h 66 نمودار 22: قیاس نتیجه «معیار F» در دسته‌بندی بر روی کل داده‌ها PAGEREF _Toc311824770 \h 66 نمودار 23: قیاس نتیجه «منحنی مشخصه عملکرد» در دسته‌بندی بر روی کل داده‌ها PAGEREF _Toc311824771 \h 67 نمودار 24: قیاس نتیجه «کاپا» در دسته‌بندی بر روی کل داده‌ها PAGEREF _Toc311824772 \h 67 نمودار 25: قیاس نتیجه «انحراف معیار» در دسته‌بندی بر روی کل داده‌ها PAGEREF _Toc311824773 \h 68 1-مقدمه: یکی چالش بر انگیزترین موضوعات مطرح در تضمین کیفیت، در شرکت‌های سازنده نرم افزار، موضوع رفع خطاهای نرم افزار است. خطاهای نرم افزاری می‌توانند در زمان پیش و یا پس از انتشار نرم افزار تشخیص داده شوند. اما منابعی که می‌توان برای تشخیص و تصحیح خطاها در نظر گرفت محدود است (Kamyabi et al.). خطاها را می‌توان به دو دسته کلی تقسیم کرد. خطاهای نحوی و خطاهای مفهومی. با توجه به‌این که ابزارهای خودکار بسیار قدرتمندی برای تشخیص خطاهای نحوی وجود دارند، احتمال‌این که خطایی ازاین دست تا زمان انتشار تشخیص داده نشود، بسیار کم است. خطاهای مفهومی به آن دسته از خطاها اشاره دارد که در اثر مشکلاتی جدای از اشتباهات نحوی و خطاهای انسانی ملموس اتفاق می‌افتند و معمولاً در اثر عدم هماهنگی در بخش‌های مختلف کد و گاهی به صورت بسیار ناملموس به وجود می‌آیند که در اینجا به سادگی نمی‌توان با بررسی کد، این‌گونه خطاها را تشخیص داد. بنا بر این در مورد خطاهای مفهومی داستان فرق می‌کند چرا که عوامل بسیار زیادی می‌توانند در بروزاین‌گونه از خطاها دخیل باشند. CITATION Zim081 \l 1033 (Zimmermann & Nagappan, 2008) بنا براین همواره سعی شده است که با اندازه گیری معیارهای مختلف و استفاده از آن‌ها در روش‌های پیش‌بینی خودکار خطا، سرعت و دقت را در امر تست نرم افزار افزایش دهند. طی تحقیقاتی که تا کنون صورت گرفته، متداول‌ترین معیارهای استفاده شده در پیش‌بینی اتوماتیک خطا، معیارهای پیچیدگی است. CITATION Zim081 \l 1033 (Zimmermann & Nagappan, 2008) اما جدیدترین روشی که مطرح شده است، مسأله مربوط به وابستگی‌های بین کلاس‌ها و همچنین بین ماژول‌ها می‌باشد. انواع وابستگی‌ها می‌توانند بین دو کلاس و یا دو ماژول مطرح شوند که تحقیقات نشان داده است که این وابستگی‌ها ارتباط بسیار زیادی با وجود خطاهای مفهومی دارند. برای اجرای روشمند و علمی روند یافتن روابط و الگوهای مناسب برای پیش بینی خطا بر اساس معیارهای قابل اندازه گیری، از مفهومی به نام داده‌کاوی استفاده خواهیم کرد که در تشریح و بیان مسأله به آن خواهیم پرداخت. دراین پایان نامه، سعی می‌کنیم که به بررسی چنین وابستگی‌هایی بپردازیم و بر اساس روابط موجود بین وابستگی و وجود خطا در نرم افزار، وجود خطا در کد را پیش بینی نماییم. در ادامه این رساله در بخش دوم به بررسی تحقیقات قبلی انجام شده در این زمینه می‌پردازیم، در بخش سوم به بیان انگیزش و نحوه به وجود آمدن ایده کار شده در این رساله می‌پردازیم، در بخش چهارم فرضیات مورد بررسی را مطرح می‌کنیم، در بخش پنجم داده‌ها و ابزارهای جمع آوری شده برای انجام عملی آزمایشات را معرفی می‌کنیم، در بخش ششم به بیان شیوه و نوع آزمایشات و بیان نتایج آنالیزها و نتایج می‌پردازیم و در بخش هفتم و پایانی این رساله سعی در نتیجه‌گیری از آزمایشات انجام شده خواهیم داشت. 3-درخت وابستگی: همان‌طور که گفته شد جدیدترین روشی که در پیش‌بینی خطای نرم‌افزار مطرح شده است، مسأله مربوط به وابستگی‌های بین کلاس‌ها و همچنین بین ماژول‌ها می‌باشد. انواع وابستگی‌ها می‌توانند بین دو کلاس و یا دو ماژول مطرح شوند که تحقیقات نشان داده است که این وابستگی‌ها ارتباط بسیار زیادی با وجود خطاهای مفهومی دارند. مسأله‌ای که در این رساله تحقیق مطرح شده است، استفاده از یک تکنیک جدید بر پایه وابستگی‌های بخش‌های مختلف نرم افزار در سطح کد است. در گذشته استفاده از گراف‌های کنترل جریان متداول بوده که این گراف جریان داده‌ها را در هنگام اجرای برنامه مورد نظر قرار داده است و از این امر در مباحث مهندسی نرم افزار استفاده شده است اما، من در این طرح پیشنهادی از وابستگی کدها استفاده کرده‌ام که بر خلاف گراف کنترل جریان، وابستگی‌ها را در زمانی بررسی می‌کند که برنامه اجرا نشده است. این وابستگی‌ها می‌توانند شامل مواردی مانند وراثت، صدا زدن زیر رویه‌ها و ماژول‌ها و هرگونه وابستگی دیگری در کد باشند که این مسأله تنها محدود به برنامه نویسی شیء گرا نشده و می‌تواند برنامه‌های ساخت یافته را نیز پوشش بدهد چرا که در آنجا نیز ما شاهد وابستگی بین ماژول‌های برنامه، توابع و رویه‌ها هستیم. برای بررسی این وابستگی‌ها و روابط آن با خطاها از مفهومی به نام داده کاوی استفاده می‌کنیم. حال سوال‌ این است که داده کاوی چیست؟ با پیشرفت سریع تکنولوژی و ورود فناوری اطلاعات بسیاری از حوزه‌ها، نیاز به داده‌ها، افزایش روز افزونی داشت. بعد از مدت کوتاهی پایگاه‌های داده بسیار عظیم با حجم بسیار گسترده‌ای از داده‌ها در سازمان‌ها، ادارات و مراکز مختلف به وجود آمدند. حال جامعه علمی می‌توانند از چنین حجم گسترده‌ای از داده‌ها استفاده کرده و با پردازش، تحلیل و بررسی این داده‌های ذخیره شده، به روابط و اطلاعاتی دست پیدا بکنند که به هر نحوی برای سازمان و بخش مربوطه مفید واقع شود (Hand et al., 2001). ممکن است در میان حجم زیادی از داده‌ها، با روش‌های مختلف بتوان روابط خاصی پیدا کرد که از جنبه‌های مختلف برای بخش مربوطه دارای اهمیت باشد. ممکن است این اهمیت دارای جنبه اقتصادی و یا افزایش کارایی سیستم باشد. داده کاوی، علمی است که روش‌ها و الگوریتم‌های متنوعی را در اختیار ما قرار می‌دهد تا بتوانیم از این حجم داده‌ها، با کشف الگوها و روابط، به اطلاعات ارزشمندی دست پیدا بکنیم. به عبارتی «علم استخراج اطلاعات ارزشمند، از مجموعه داده‌ها و پایگاه‌های داده بزرگ» به عنوان داده کاوی شناخته می‌شود. (Hand et al., 2001). لری کنستانتین در سال 1974 مفهوم وابستگی را معرفی کرد و این مفهوم به صورت گسترده‌ای در تحقیقات و کتاب‌ها و منابع مختلف، به صورت یک اصل در مهندسی نرم‌افزار مورد استفاده قرار گرفت. اما مفهوم وابستگی معرفی شده توسط کنستانتین از واژه Coupling یعنی جفتگری گرفته شده است. جفتگری همیشه به همراه مفهوم دیگری به کار برده شده است. این مفهوم، پیوستگی می‌باشد. قالبا جفتگری کم نشانه طراحی خوب نرم‌افزار است در حالی که پیوستگی کم نشان دهنده یک طراحی ضعیف می‌باشد. تأثیر این دو مفهوم بر یکدیگر به صورت عکس است و به گونه‌ای که در نمودار زیر مشاهده می‌نمایید، با افزایش جفتگری، پیوستگی کاهش پیدا می‌کند. CITATION Con29 \l 1033 (Constantine, 1996) نمودار SEQ نمودار_ \* ARABIC 1: ارتباط بین جفتگری و انسجام. در واقع جفتگری معنای معمول‌تر خود یعنی وابستگی را به طور کامل دارا است. هرچه وابستگی در نرم‌افزار افزایش پیدا کند، کیفیت طراحی، به دلیل کاهش انسجام آن کاهش پیدا می‌کند. حال ممکن است این سوال مطرح شود که کدام دلیل منطقی وجود دارد که باعث وجود چنین رابطه‌ای بین وابستگی و انسجام می‌شود؟ شاید منطقی ترین پاسخی که بتوان برای این سوال پیدا کرد موضوع چرخش کد باشد. چرخش کد مفهومیست که با تغییر بخش‌هایی از کد نرم‌افزار به یکی از دلایل زیر اشاره دارد: تغییر در اثر تغییر در نسخه‌های مختلف. تغییر به قصد رفع خطا. بدون نیاز به تمرکز بر دلیل تغییر، می‌توان این امر منطقی را قبول کرد که اگر بخش‌هایی از برنامه، به هر دلیلی دچار تغییر بشوند، ممکن است هماهنگی این بخش‌ها با بخش‌های دیگر برنامه از بین برود. Class AClass BClass C شکل SEQ شکل_ \* ARABIC 1: نمونه‌ای از وابستگی‌های میان کلاس‌ها. برای مثال اگر در تصویر بالا کلاس A را در نظر بگیریم، ممکن است کلاس‌های دیگری مانند B و یا C به آن وابسته باشند. اگر تغییری در کلاس A اتفاق بیفتد، ممکن است روند تغییرات صورت گرفته به گونه‌ای باشد که یکی از کلاس‌های وابسته آن نتوانند مثل قبل با کلاس A ارتباط برقرار کنند و در نتیجه دچار بروز خطاهایی در بخش‌هایی از برنامه بشویم. از آنجایی که چنین خطاهایی اصولاً خطاهای نحوی را شامل نمی‌شوند، ممکن است یافتن آن‌ها قدری مشکل‌تر باشد. حال سوالی که مطرح می‌شود این است که آیا روند پخش شوندگی خطا می‌تواند به همین طریق تا وابستگی‌های گذرا نیز ادامه پیدا کند یا خیر؟ برای توضیح بیشتر این امر، ابتدا وابستگی گذرا را توضیح خواهیم داد. فرض کنیم که تصویر قبل بخشی از یک گراف وابستگی بزرگ‌تر مانند گراف زیر باشد. Class AClass BClass CClass DClass FClass EClass GClass H شکل SEQ شکل_ \* ARABIC 2: نمونه‌ای از وابستگی‌های پیچیده در میان کلاس‌ها. در این صورت کلاس‌های E، F و D از طریق B دارای وابستگی‌های گذرا یا در اصطلاح Transitive نسبت به کلاس A هستند. به همین ترتیب وابستگی‌های گذرای دیگری را نیز می‌توان یافت برای مثال می‌توان به وابستگی گذرای G از طریق C به A اشاره نمود. در وابستگی‌های گذرا بیش از یک گره میانجی نیز می‌توانند مشارکت داشته باشند به گونه‌ای که برای مثال کلاس H از طریق مسیر F-B نسبت به کلاس A دارای وابستگی گذرا می‌باشد. بنا به مثال‌های نشان داده شده، یک وابستگی گذرا، نوعی از وابستگی است که در آن گره مبدأ از طریق یک یا چند گره میانی به گره مقصد وابسته باشد. حال که مقصود از وابستگی گذرا روشن شد، می‌توانیم به صورت روشن‌تری سوال مطرح شده را بیان کنیم. آیا خطای موجود در یک گره، می‌تواند در نتیجه مسائلی مانند چرخش کد به وابسته‌های گذرای یک کلاس سرایت کند یا خیر؟ اگر دیدمان را از دیاگرام وابستگی نرم‌افزار به سمت یک گراف جهت دار سوق دهیم، می‌توانیم مسائلی را در مورد گراف جهت دار پیدا کنیم که پرورش دهنده ایده‌های مربوط به وابستگی هستند. اولین مسأله‌ای که بعد از طرح موضوع مربوط به وابستگی‌های گذرا به ذهن خطور می‌کند، الگوریتم‌های پیدا کننده کوتاه ترین مسیر بین دو گره مشخص در گراف هستند. معروف‌ترین این الگوریتم‌ها، الگوریتم وارشال است. الگوریتم وارشال همه مسیرهای ممکن در یک گراف، بین هر جفت از رأس‌ها را مقایسه می‌کند. این الگوریتم قادر است این کار را تنها با V2 مقایسه انجام دهد. این ملاحظه قابل توجهی می‌باشد که در یک گراف V2 یال وجود داشته باشد و هر ترکیبی از یال‌ها چک شده باشد. یک گراف G با راس‌های Vi که i از 1 تا N می‌باشد را در نظر بگیرید. علاوه بر این یک تابع به نام ShortestPath(i,j,k) را در نظر بگیرید که کوتاه‌ترین مسیر ممکن از i تا j را با استفاده از راس‌های 1 تا k که به عنوان راس‌های میانی در امتداد مسیر می‌باشند را بر می‌گرداند. هم اکنون این تابع داده شده است. هدف ما پیدا کردن کوتاه‌ترین مسیر از هر i تا هر j تنها با استفاده از راس‌های 1 تا k+1 می‌باشد. دو کاندیدا برای این مسیر وجود دارد : کوتاه‌ترین مسیری که فقط از راس‌های موجود در مجموعه‌ی (k,........,1) استفاده می‌کند. تعدادی مسیر که از i تا k+1 و سپس از k+1 تا j می‌روند وجود دارد که این مسیر بهتر می‌باشد. 11239597790(1). ما می‌دانیم که بهترین مسیر از i تا j که فقط از راس‌های بین 1 تا k+1 استفاده می‌کند توسط ShortestPath(i,j,k) تعریف شده است و واضح است که اگر یک مسیر بهتر از i تا k+1 و از k+1 تا j وجود داشته باشد بنابراین طول مسیر بین i,j از الحاق کوتاه‌ترین مسیر از i تا k+1 و کوتاه‌ترین مسیر از k+1 تا j بدست می‌آید. بنابراین تابع ShortestPath(i,j,k) را در فرمول بازگشتی زیر ارائه می‌دهیم: بنا به تعریف انجام شده، به نظر می‌رسد که الگوریتم وارشال می‌تواند در حل مسأله‌ای مانند یافتن بستار تعدی و وابستگی‌های گذرای گراف وابستگی نرم افزار قابلیت استفاده داشته باشد. مسأله دیگری که خودنمایی می‌کند، حجم وابستگی‌ها در میان گروهی از گره‌های یک گراف است. در یک گراف جهت‌دار با n گره، میزان وابستگی‌ها می‌تواند در دامنه‌ای از صفر تا n(n-1) قرار بگیرد. مشخصاً در گرافی که هیچ گونه وابستگی در آن وجود ندارد، ما تنها تعدادی گره مستقل خواهیم داشت. اما گرافی که در آن تمامی گره‌های آن به هم وابستگی دارند، در اصطلاح گراف کامل نامیده می‌شود. به یک گراف و یا زیر گراف کامل، در اصلاح کلیک گفته می‌شود. کلیک مبحثی است که مسائل بسیار زیاد و معروفی با عنوان مسائل کلیک در مورد آن مطرح شده‌اند. بعضی از این مسائل عبارتند از: یافتن کلیک‌ها با اندازه ثابت در یک گراف. یافتن تمامی کلیک‌های ماکزیمال در یک گراف. یافتن تمامی کلیک‌های ماکزیموم در یک گراف. ... مسأله جذاب و جالب دیگری که در مورد گراف‌ها خودنمایی می‌کند این است که مسأله کلیک، می‌تواند کمک کننده این باشد که قسمت‌هایی از گراف وابستگی نرم‌افزار را که بیشترین چگالی وابستگی ممکن در آن موجود است را پیدا کنیم و ارتباط آن را با خطا نشان دهیم. کارپ در سال 1947 اثبات کرد که در کل مسائل مربوط به کلیک جزء مسائل ان پی-کامل هستند. به این معنی که هیچ الگوریتم قابل اجرا در زمان چند جمله‌ای برای این مسائل وجود ندارد. این مشکل در جایی خود را بیشتر نشان می‌دهد که گراف وابستگی یک نرم‌افزار معمولی ممکن است شامل چندین هزار گره باشد بنابراین به نظر می‌رسد که مسائل مربوط به کلیک، برخلاف جذابیت بسیاری که در زمینه وابستگی نرم‌افزار از خود نشان می‌دهند، به صورت عملی قابل استفاده نیستند. CITATION Kar75 \l 1033 (Karp, 1975) سوال دومی که مطرح می‌شود این است که آیا می‌توان از خصوصیات مسائل مربوط به کلیک در پیدا کردن نقاط مستعد خطای برنامه استفاده نمود یا خیر؟ این سوال از آنجا مطرح می‌شود که وقتی بتوان گروهی از گره‌های یک گراف را پیدا کرد که تشکیل یک کلیک را می‌دهند، در واقع بیشترین وابستگی‌های ممکن بین این گروه از گره‌ها اتفاق افتاده است. سوال این است که آیا این تراکم گره‌ها می‌تواند نشانه‌ای بر مستعد خطا بودن آن بخش از نرم‌افزار باشد یا خیر؟ 4-فرضیات: حال سوال این است که هدف از طرح مبحث مورد نظر چیست؟ به عبارتی به چه نتیجه‌ای می‌خواهیم برسیم؟ در پاسخ به این موضوع می‌توان اهدافی را برای ادامه کار مشخص کرد و این اهداف را در اینجا به صورت سوال‌ها و فرضیاتی مطرح می‌کنیم: الف: آیا درخت وابستگی هیچ‌گونه ارتباطی با خطا دار بودن بخش‌های متناظر در برنامه دارد؟ ب: در صورت بودن ارتباط آیا درخت وابستگی می‌تواند به صورت معیاری برای پیش‌بینی خطا، به صورت عملی مورد استفاده قرار بگیرد؟ ج: عملکرد درخت وابستگی در قیاس با دیگر مشخصه‌های استفاده شده در پیش‌بینی خطا به چه صورتی است؟ آیا عملاً می‌توان بیان کرد که درخت وابستگی، خصوصیتی قابل مقایسه با دیگر مشخصه‌ها و متریک‌های مورد استفاده در پیش‌بینی خطا دارد یا خیر؟ 7-مراجع: BIBLIOGRAPHY Akyama, F. (1971). An Example of Software System Debugging. International Conference on Digital Forensics (pp. 353-359). Vancouver, Canada: Chapman & Hall.Basili, V., Briand, L., & Melo, W. (1996). A validation of object-oriented design metrics as quality indicators. IEEE Transaction on Software Engineering , 22 (10) , (pp.751-761).Bener, A., Tosun, A., Turhan, B., & Menzies, T. (2010). Practical Considerations in Deploying Statistical Methods for Defect Prediction: A Case Study within the Turkish Telecommunications Industry. Information and Software Technology , vol.52, (p.1242-1257).Bevan, J., & Whitehead, E. J. (2003). Identification of Software Instabilities. Working Conference on Reverse Engineering, (pp. 134-145). Victoria, B.C., Canada.Binkley, A. B., & Schach, S. R. (1998). Validation of the coupling dependency metric as a predictor of failures and maintenance measures. In in International Conference on Software Engineering, (pp.452-455). Kyoto.Chidamber, S., & Kemerer, C. (1994). A metrics suite for object oriented design. IEEE Transaction on Software Engineering , 20 (6) , (pp.476-493).Clarke, A., & Pogdurski, L. (1990). A Formal Model of Program Dependences and its Implications for Software Testing, Debugging, and Maintenance. IEEE Transactions on Software Engineering , 16, (pp.965-979).Constantine, L. (1996). Usage-centered software engineering: new models, methods, and metrics. International Conference on Software Engineering: Education and Practice, (pp. 2-9). Hamilton, New Zealand.Fenton, N. E., & Lawrence, P. S. (1998). Software Metrics: A Rigorous and Practical Approach. Boston: PWS Publishing Co.Ferdinand, A. (1974). A Theory of System Complexity. Int’l J. General Systems , vol. 1, (pp. 19-33).Graves, T. L., Karr, A. F., Marron, J. S., & Siy, H. (2000). Predicting fault incidence using software change history. IEEE Transactions on Software Engineering , vol. 26, (pp. 653-661).Hand, D. J., Mannila, H., & Smyth, P. (2001). Principles of Data Mining. MIT-Press.Henry, S., & Kafura, D. (1981). Software Structure Metrics based on Information Folow. IEEE Transactions on Software Engineering , 7 (5) , (pp. 510-518).Hideaki, H., & Osamu, M. (2010). An Integrated Approach to Detect Fault-Prone Modules Using Complexity and Text Feature Metrics. the international conference on Advances in computer science and information technology, (pp. 457–468). Berlin Heidelberg.Hudepohl, J. P., Aud, S. J., Khoshgoftaar, T. M., Allen, E. B., & Mayrand, J. (1996). Emerald: Software Metrics and Models on the Desktop. IEEE Software , vol. 13, No. 5,(pp. 56-60).Jiang, Y., Cuki, B., Menzies, T., & Bartlow, N. (2008). Comparing design and code metrics for software quality prediction. The 4th international workshop on Predictor models in software engineering (pp. 11-18). Leipzig, Germany: ACM New York, NY, USA.Kafura, D., & Henry, S. (1981). Software Structure Metrics based on Information Flow. IEEE Transactions on Software Engineering , vol.7, (pp. 510-518).Kamyabi, J., Maleki, F. & S., A., (2012). Software defect prediction using transitive dependencies on software dependency graph. International Conference of Computer Science and its Applications. vol. 114, No. 1, (pp. 241-249). Jeju, South Korea: Springer Netherlands.Karp, R. M. (1975). Richard M. Karp. The Journal of Symbolic Logic , vol 40, No. 4, (pp. 618-619).Khoshgoftaar, T., Allen, E., Goel, N., Nandi, A., & McMullan, J. (1996). Detection of software modules with high debug code churn in a very large legacy system. Seventh International Symposium on Software Reliability Engineering, (pp. 364-371). White Plains, NY , USA .McCabe, T. J. (1976). A complexity measure. the 2nd international conference on Software, (p.p. 407).Menzies, T., Greenwald, J., & Frank, A. (2007). Data Mining Static Code Attributes to Learn Defect Predictors. IEEE Transactions on Software Engineering , vol 33, No. 1, (pp. 2-13).Menzies, T., Milton, Z., Turhan, B., Cukic, B., Jiang, Y., & Bener, A. (2010). Defect prediction from static code features: current results, limitations, new approaches. Emperical Software Engineering , Vol 17, No 4.Nagappan, N., & Ball, T. (2005). Use of relative code churn measures to predict system defect density. 27th International Conference on Software Engineering, (pp. 284-292). St. Louis, Missouri, USA.Nagappan, N., & Ball, T. (2007). Using Software Dependencies and Churn Metrics to Predict Field Failures: An Empirical Case Study. International Symposium on Empirical Software Engineering and Measurement, (pp. 364-373).Nagappan, N., Ball, T., & Murphy, B. (2006). Using Historical In-Process and Product Metrics for Early Estimation of Software Failures. 17th International Symposium on Software Reliability Engineering, (pp. 62-74). downtown Raleigh, North Carolina.Nagappan, N., Ball, T., & Zeller, A. (2006). Mining Metrics to Predict Component Failures. International Conference on Software Engineering, (pp. pp.452-461). Shanghai, China.Ohlsson, N., & Alberg, H. (1996). Predicting fault-prone software modules in telephone switches. IEEE Transaction on Software Engineering , 22 (12) , 886-894.Ostand, T. J., Weyuker, E. J., & Bell, R. M. (2004). Where the Bugs Are. The 2004 ACM SIGSOFT international symposium on Software testing and analysis, (pp. 86-96). Newport Beach, CA, USA.Ostrand, T., Weyuker, E., & Bell, R. (2005). Predicting the location and number of faults in large software systems. IEEE Transactions on Software Engineering , 31 (4) , 340-355.Pinzger, M., Gall, H., & Fischer, M. (2005). Towards an Inte-grated View on Architecture and its Evolution. Electronic Notes in Theoretical Computer Science, (pp. 183-196).Podgurski, A., & Clarke, L. (1990). A Formal Model of Program Dependences and Its Implications for Software Testing, Debugging, and Maintenance. IEEE Transactions on Software Engineering , 16 (9) , 965-979.Pressman, R. S. (1982). Software Engineering - A Practitioner's Approach. McGraw Hill.Sami, a & Fakhrahmad, m. (2010). Design-level metrics estimation based on code metrics. the ACM Symposium on Applied Computing. New York, NY, USA 2010.Schröter, A., Zimmermann, T., & Zeller, A. (2006). Predicting component failures at design time. International symposium on Empirical software engineering (pp. 18-27). Colorado: ACM New York, NY, USA.Schröter, A., Zimmermann, T., & Zeller, A. (2006). Predicting component failures at design time. ACM/IEEE International symposium on empirical software engineering (pp. 18-27). New York, NY, USA: ACM Press.Selby, R., & Porter, A. (1989). Software metric classification trees help guide the maintenance of large-scale systems. Software Maintenance, (pp. 116 - 123). Miami, FL , USA.Tosun, A., Turhan, B., & Bener, A. (2009). Validation of network measures as indicators of defective modules in software systems. the 5th International Conference on Predictor Models in Software Engineering. Zhao, M., Wohlin, C., Ohlsson, N., & and Xie, M. (1998). A Comparison between Software Design and Code metrics for the Prediction of Software Fault Content,. Information and Software Technology. , 40 (14) , 801-809.Zimmermann, T., & Nagappan, N. (2008). Predicting defects using network analysis on dependency graphs. The 2008 International Conference on Software Engineering, (pp. 531-540). Leipzig, Germany.Zimmermann, T., Weißgerber, P., Diehl, S., & Zeller, A. (2005). Mining Version Histories to Guide Software Changes. IEEE Transactions in Software Engineering , 31 (6) , 429-445. Abstract SOFTWARE DEFECT PREDICTION USING DATAMINING BASED ON SOFTWARE DEPENDENCIES AND CODE METRICS By Javad Kamyabi In software production process, quality assurance resources are limited by time and cost. In order to achieve high quality, managers need to detect the defect prone parts of code and allocate the resources to them. So far, researchers have used some automated methods for defect prediction. These methods use software metrics to predict the defects. These metrics are complexity metrics, design metrics, dependency related metrics and historical data for software defect prediction. Although these methods are somewhat efficient, no one helps to predict all the defects. In this thesis we have extended the definition of dependency and as the result the concept of dependency tree is defined. Dependency tree covers all of the direct and indirect dependencies existed for each component. It helps us to extract some new metrics for defect prediction. Novelty of my work is that these metrics cover all direct and indirect dependencies and they provide better results in defect prediction in comparison with the previous metrics. Shiraz University Department of E-learning M.S.THESIS In Information Technology (e-commerce). SOFTWARE DEFECT PREDICTION USING DATAMINING BASED ON SOFTWARE DEPENDENCIES AND CODE METRICS By Javad Kamyabi Supervised by Dr. Ashkan Sami December 2011