×
نام و نام خانوادگی
بازخوانی ...
اطلاعات کتابشناختی
عنوان اصلی: ارايه رويكردي نوين براي مساله دسترس پذيري و كاربرد آن در آزمون مبتني بر گراف
پدیدآورندگان : محمد وليزاده (پديدآور)
محمد حسام تدين (پديدآور)
عليرضا باقري (پديدآور)
نوع : متن
جنس : کتاب راهنما
چاپ
صاحب محتوا :

موسسه تحقیقات ارتباطات و فناوری اطلاعات

توصیفگر : مساله علامت گذاري
مسله برش كميته منطقي
تقريب ناپذيري
پوشش راس
مسيريابي
تضمين دسترسي
پيچيدگي محاسباتي
آزمون نرم افزار
وضعیت نشر : تهران : پژوهشگاه ارتباطات و فناوري اطلاعات ، 1398
مشخصات فیزیکی : 89 ص.: مصور
یادداشت :
برای رسیدن به پوشش بالا در آزمون مبتنی بر گراف، چالش‌های مهمی همچون مساله دسترس‌پذیری وجود دارد. راهکارهای موجود عمدتا از روش مسیریابی برای تولید موارد آزمون و پوشش عناصر گراف استفاده می‌کنند. روش مسیریابی چالش دسترس‌پذیری را به نحو مطلوبی برطرف نمی‌سازد چراکه درگیر مسائلی همچون کثرت و واگرایی مسیر و نیز محدودیت‌های پیچیده مسیر می‌گردد. در این پیشنهاد راهکار نوینی به نام شیوه علامت‌گذاری ارائه می‌گردد که چالش‌های اصلی درگیر در تولید موارد آزمون مبتنی بر گراف یک برنامه را به نحو بهتری برطرف می‌سازد. راهکار علامت‌گذاری برخلاف راهکار رایج مسیریابی که از یک دنباله یال استفاده می‌کند، از یک مجموعه‌ از یال‌های گراف برای تضمین دسترسی به راس هدف استفاده می‌نماید. هدف مساله علامت‌گذاری، علامت‌گذاری بهینه برخی یال‌های گراف است به‌طوری‌که هر مسیر آغاز شونده از راس مبدا به راس مقصد برسد. در این رساله، از طریق کاهش مساله مجموعه ضربه‌زننده به مساله علامت‌گذاری، نشان می‌دهیم که مساله علامت‌گذاری در یک گراف جهت‌دار یک مساله NP-کامل است، حتی اگر آن گراف، یک گراف غیرمدور بدون‌وزن دودویی باشد. همچنین نشان می‌دهیم که مساله علامت‌گذاری در یک گراف غیرمدور بدون‌وزن دودویی با n راس نمی‌تواند با دقت α log n تقریب زده شود، به‌طوری‌که α یک عدد ثابت است. در ادامه، کران پایینی برای جواب بهینه مساله علامت‌گذاری در یک گراف غیرمدور بدون وزن دودویی داده می‌شود. یک الگوریتم اکتشافی با مرتبه O(n3) برای حل مساله علامت‌گذاری در یک گراف وزن‌دار غیرمدور با n راس ارائه شده و دقت آن از طریق محک‌زنی برروی گراف‌های متعدد نشان داده می‌شود. طبق تحقیقات به عمل آمده برروی هزاران گراف برنامه‌، هزینه دسترسی در راهکار علامت‌گذاری حدود 3.5 برابر کمتر از هزینه دسترسی در راهکار مسیریابی است. طی چند دهه اخیر، راهکارهای متعددی برای حل مسایل مربوط به دسترس‌ناپذیری همچون مساله برش کمینه ارائه گردیده است. در این رساله نشان می‌دهیم که چگونه می‌توان مساله دسترس‌پذیری را به مساله دسترس‌ناپذیری تبدیل نموده و متعاقبا از الگوریتم‌های موجود در زمینه مساله دسترس‌ناپذیری، برای حل مساله دسترس‌پذیری استفاده کرد. در این راستا، مساله جدیدی به‌نام برش کمینه منطقی را مطرح می‌نماییم. هدف مساله برش کمینه منطقی، قطع دسترس‌پذیری راس مقصد از راس مبدا از طریق حذف برخی یال‌های گراف است به‌طوری‌که مجموع وزن یال‌های حذف شده کمینه بوده و تمام یال‌های خروجی هیچ راسی از گراف یکجا حذف نشود. در این تحقیق نشان می‌دهیم که مساله برش کمینه منطقی یک مساله NP-کامل و تقریب‌ناپذیر است. همچنین، نحوه تبدیل مساله علامت‌گذاری به مساله برش کمینه منطقی را تشریح می‌نماییم. نهایتا کاربرد مساله علامت‌گذاری در استخراج موارد آزمون کارکردی و امنیت یک برنامه ارائه می‌گردد.
In order to reach a high coverage in graph-based testing method, there are important challenges such as reachability problem. The current approaches mainly use path-finding solution to generate test cases and to increase graph coverage. The path-finding solution does not resolve the reachability challenge well enough as it involves issues such as path explosion, path divergence, and complex constraints. We propose a new solution named Marking approach, which resolves the challenges of graph-based test case generation appropriately. The marking solution uses a set of edges to assure reaching the target vertex whereas the common path-finding solution uses a sequence of edges to reach the target. The goal of marking problem is minimal marking of some edges of the underlying digraph such that any path starting at the source vertex finally reaches the target vertex. By reducing the hitting set problem to the marking problem, we show that the marking problem is NP-Complete, even if the underlying digraph is an unweighted binary DAG. Moreover, we show that the marking problem in an unweighted binary DAG with n vertices cannot be approximated with α log n where α is a constant. We also provide a lower bound for the optimal solution of the marking problem. A heuristic algorithm with the complexity O(n3) is provided for solving the marking problem in a weighted DAG with n vertices. The precision of the algorithm is demonstrated by benchmarking on various digraphs. Based on the benchmarks performed on thousands of program flow graphs, the reachability cost of marking solutuion is about 3.5 times less than that of the path-finding solution. During the last decades, various solutions were proposed to solve unreachability problems such as the min-cut problem. We show that how reachability and unreachability problems can be reduced to each other. In this regard, we introduce a new problem named logical min-cut and show how to convert the marking problem to the logical min-cut problem. The logical min-cut problem states how a target vertex can be made unreachable from a source vertex by removal of some edges of a digraph where the sum of weights of the removed edges is minimal and all outgoing edges of any vertex of the digraph cannot be removed together. This research shows that the logical min-cut problem is NP-Complete and cannot be approximated with α log n in a DAG with n vertices. Finally, applications of the marking problem are presented in functional and security test case generation of a computer program.
شناسه : oai:vlib.itrc.ac.ir/13970
تاریخ ایجاد رکورد : 1399/3/13
تاریخ تغییر رکورد : 1399/3/13
قیمت شيء دیجیتال : فاقد شيء دیجیتالی


* محتوای این صفحه توسط کارشناسان این درگاه ویرایش نشده است. لطفا در صورت مشاهده ایراد در محتوا از این طریق اطلاع رسانی کنید.

دیدگاه شما

تست
ورود به درگاه کنسرسیوم
Loding



رمز عبور خود را فراموش کرده ام.
چنانچه تا کنون عضو سایت نشده اید ثبت نام کنید.
درباره کنسرسیوم
ما مجموعه‌ای از كتابخانه‌ها و سازمان‌های دارای منابع اطلاعاتی (کتاب، نشریه، نسخه‌های خطی، عکس، صدا، فیلم و... ) هستیم که با هدف تامین نیازهای پژوهشگران و شهروندان ایرانی برای دسترسی هر چه سریع‌تر به محتوای مورد نظر خود، کنسرسیوم محتوای ملی را تشکیل داده‌ایم. برای رسیدن به این هدف، قصد داریم با بسترسازی مناسب و جلب مشارکت دیگر تولید کنندگان محتوا به گرد آوری، تبدیل، سازماندهی و حفاظت اطلاعات به شکل رقومی و در سطح ملی، بپردازیم.