23875

راهكاري جديد براي توليد خودكار داده هاي آزمون با استفاده از اجراي نمادين پويا

كارشناسي ارشد

مهندسي تكنولوژي نرم افزار - كامپيوتر

1395

13/8/1398

دكتر سعيد پارسا

مهندسي كامپيوتر

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

1400/03/18

a novel approach for automatic test data generation using concolic execution

11/3/2020 12:00:00 AM

Unit test is one of the major software tests for the validation of software components. One of the new approaches to automatically generate test data is to use Dynamic Symbolic Execution. In this method, the program under test is executed both realistically and symbolically. At each stage, by selecting a branch of the program execution tree, suitable test data is obtained to cover a new path of the program. This method faces various challenges, one of which is the issue of path explosion. Node selection is the first step in any iteration of dynamic symbolic execution. Improper node selection will cause the path to explode. This thesis provides a solution for selecting the appropriate node. The proposed solution tries to fairly select the branches of the program under test. In this method, firstly the nodes of the program execution tree are divided into classes based on the offset code, and when the node is selected, one of the classes is selected fairly. Then one of the nodes in the selected class is selected. This selection is done with the priority of selecting nodes with a shallower depth. The proposed solution has been tested by the ant colony method for a number of benchmark programs. The results show that the proposed solution in most cases offers a lower number of program implementations and in less time it covers more branches of the program. While this solution is economical to save time and cost on software testing, using ant colony can cover more paths of test data. One of the most important steps in the software development lifecycle is software testing. Software testing is performed with the aim of ensuring the correctness of the developed software and its compliance with the described requirements. Automatic production of test data is one of the important steps of software testing, the purpose of which is to generate inputs to evaluate software behavior. The three most important approaches in the automatic production of white box test data are random methods, symbolic execution, and search-based methods. Each of these methods has its drawbacks. In random methods, test data is generated inaccurately, so that it does not cover many program paths. To solve this problem, a large amount of data is generated, which is a time-consuming and very costly process. The main drawbacks of the symbolic method are the existence of libraries and ready-made functions in the program code that prevent the production of appropriate algebraic expressions for constraint solvers. In addition, solvents lose their ability to solve algebraic expressions and spend further time solving algebraic expressions and generating data if there is too much complexity and recursive calls in the program code. The main problem with search-based methods is that due to the use of fitness functions, random nature, and trying to converge to an optimal answer, they may be in the local minimum and stay away from the optimal answer. In this research, To solve the mentioned problems, a new and innovative approach in the field of automatic production of test data is presented. This approach tries to produce appropriate test data by relying on a fuzzy inference system and machine learning. The purpose of this approach is to cover the maximum base paths, which is a stronger test adequacy criterion than the node and edge coverage criterion. In order to evaluate the proposed solution, various experiments have been performed on different programs. The results show that the proposed approach is able to produce test data more efficiently than previous approaches.

آزمون نرم‌افزار، آزمون واحد، اجراي نمادين، اجراي نمادين پويا، انفجار مسير، روش كلوني مورچگان، سيستم فازي، يادگيري ماشين، مسير پايه , آزمون واحد

Software test, unit test, symbolic execution, dynamic symbolic execution, path explosion, ant colony method, fuzzy system, machine learning, basic path