تولید داده آزمون مبتنی بر جستجوی مقید جهت پوشش مسیرهای اولیه در آزمون ساختاری

محورهای موضوعی : پردازش چند رسانه ای، سیستمهای ارتباطی، سیستمهای هوشمند

ابراهیم فضلی ¹ , مجتبی اعجمی ²

1 - استادیار، دانشکده مهندسی برق و کامپیوتر، واحد زنجان، دانشگاه آزاد اسلامی، زنجان، ایران.
2 - استادیار، دانشکده مهندسی برق و کامپیوتر، واحد زنجان، دانشگاه آزاد اسلامی، زنجان، ایران.

تاریخ دریافت : 1401/09/15 تاریخ پذیرش : 1402/03/30 تاریخ انتشار : 1402/01/01

کلید واژه: مسیر اولیه, آزمون ساختاری, جستجوی مقید, داده آزمون,

چکیده مقاله :

این مقاله به مسئله تولید داده آزمون جهت پوشش مسیرهای آزمون پوشش دهنده مسیرهای اولیه می‌‌پردازد. روش ارائه شده جهت حل معادله مسیر ترکیبی از روش مبتنی بر جستجو و مبتنی بر قید می‌‌باشد. در بخش مبتنی بر قید از حل کننده ای بنام choco جهت حل قیدهای مبتنی بر تساوی استفاده شده است. در بخش مبتنی بر جستجو یک روش فرا‌‌ ابتکاری مبتنی بر الگوریتم بهینه سازی گرگ خاکستری[1] استفاده شده است. این روش صرفا با مقداردهی دو پارامتر، عمل جستجوی مقادیر را آغاز می‌کند. این روش قابلیت ارتقا به فضای چند بعدی بدون نیاز به پارامترهای اضافی را دارد. استفاده از برنامه نویسی مقید با استفاده از حل کننده می‌‌تواند یکی از نقاط ضعف اساسی روشهای مبتنی بر جستجو که حل شرط‌های تساوی می‌‌باشد را برطرف کند. نقطه قوت دیگر الگوریتم جستجو به روش گرگ خاکستری، استفاده از عامل‌های جستجوی مختلف و راه‌حل‌های چندگانه می‌‌باشد که از به دام افتادن فرآیند جستجو در بهینه‌های محلی جلوگیری می‌‌کند. نتایج اجرای روش پیشنهادی بر روی دسته ای محدود از برنامه‌های محک حاکی از بهبود سرعت و همچنین درصد موفقیت بالا در تولید داده آزمون نسبت به دیگر الگوریتم‌های جستجوی فرا ابتکاری مانند الگوریتم ژنتیک، می‌‌باشد.

چکیده انگلیسی:

This paper presents a novel scalable Constraint Search Based method forTest Data Generation, called CSBTDG, used in structural testing. CSBTDG outperforms existing methods for test data generation in several orders of magnitude, both in time and constraint efficiency. Search-based software testing is a powerful automated method to generate test inputs for software under test. Its goal is to reach a branch or a statement in a program. One major limitation of this approach is an insufficiently informed fitness function to start and guide search toward a test target within nested predicates (constraints). Another important limitation of this approach about equality constraints. To address these problems we propose a new search method based on integrating constraint programming using choco constraint solver and the Gray Wolf heuristic search algorithm. Preliminary experiments promise efficiency and effectiveness for the new constraint search based test data generation approach using multiple fitness functions.Test data generation is done by solving constraints related to test paths extracted from the program under test [3][2]. In general, the constraint solving problem of the test paths is a sub problem of a wider set of problems called constraint satisfaction problem (CSP) [4]. Formally, a constraint satisfaction problem is defined as a triple (X, D, C). X represents a set of variables, D is a set of range of values for variables and C is a set of constraints. Constraint satisfaction is the process of finding solutions for a set of constraints that satisfy the conditions imposed on the variables. Evaluation of variables is a function of a subset of variables to a specific set of values in the corresponding domains. The proposed solution is called consistent evaluation if none of the constraints are violated. An evaluation is a complete evaluation if it includes all variables. If the assessment is consistent and complete, it is a solution. It is said that such evaluation is a solution to the constraint satisfaction problem. Therefore, a solution is a set of values for the variables that satisfy all the constraints, that is, a point in the feasible region. The main innovation of this article is to present a cooperation model to exchange information between the solver and the searcher. In this model of data generation, the test solver is an initial setup to assign values to some variables to start searching for the meta-heuristic algorithm.

منابع و مأخذ:

• [1] Fazli and M. Afsharchi, "A Time and Space-Efficient Compositional Method for Prime and Test Paths Generation," in IEEE Access, vol. 7, pp. 134399-134410, 2019, doi: 10.1109/ACCESS.2019.2941429.


• [2] M. S. Bueno and M. Jino. Automatic test data generation for program paths using genetic algorithms. International Journal of Software Engineering and Knowledge Engineering, 12(06):691–

709, 2002.

• [3] Jussien, N., Rochart, G., & Lorca, X. (2008). Choco: an open source java constraint programming library. In CPAIOR'08 Workshop on Open-Source Software for Integer and Contraint Programming (OSSICP'08) (pp. 1-10).


• [4] Dwarakanath and A. Jankiti. Minimum number of test paths forprime path and other structural coverage criteria. In IFIP International Conference on Testing Software and Systems, pages 63–79. Springer, 2014.


• [5] C. Ntafos and S. L. Hakimi. On path cover problems in digraphs
  and applications to program testing. IEEE Transactions on Software
  Engineering, (5):520–529, 1979.


• [6] A. Nejmeh. Npath: a measure of execution path complexity and its applications. Communications of the ACM, 31(2):188–200, 1988.