A reinforcement learning approach for control flow error detection in automated software testing

Abstract

Test girdileri üretmek için otomatik yazılım test yöntemleri kaçınılmaz hale geldi. Test araçları bir hata bulmak için olaylar üretir ve yazılım üzerinde bu olayların gerçekleşmesini sağlarlar. Ne yazık ki, test edilen uygulama çalışmaz hale geldiğinde, elde edilen olay dizisi bu hata ile ilgisi olmayan bir çok öğe de barındırır. Hata ile ilgisiz olan bu olaylar hata ayıklamayı zorlaştırmaktadır. Biz de bu çalışmada özellikle çökme senaryolarını bulmak ve onarılmasına yardım etmek için, ajanıın hedefinin çökmelere giden en kısa giriş dizilerini bulmak olduğu takviye öğrenme (RL) yaklaşımı sunuyoruz. Bu sayede yazılım geliştiricileri kilitlenmeye giden en kısa yol olan ajanın eylemlerini analiz ederek hataya neden olan akışı kolayca tespit edip müdahale edeceklerdir. Önce hataya sebep olan bir girdi dizisine Recursive Delta Debugging (RDD) uygulayarak bu dizideki hatayla ilgili olmayan girdileri ayıklayıp, daha sonra RL ile daha kısa yolları keşfetmek için öğrenmeyi başlatıyoruz. Kilitlenme hatalarının yakalanmasına ajanın hedefi hataya giden en kısa yolu bulmak şeklinde belirleyerek ve ödüller vererek bir RL problemi olarak yaklaşıyoruz. Bu probleme hem modelden bağımsız politika üzerinde hem de model tabanlı planlama yapabilen RL yöntemlerini uyguluyoruz. Ayrıca, küçük bir varyansta öğrenmeyi durdurarak ve ilgisiz eylemleri yinelemeli olarak kaldıran bir algoritma ile en kısa çarpışma sırasına ulaşarak yakınsamayla boğuşmaktan kaçınarak zaman karmaşıklığını azaltan Algılanmış Hedef Katalizörünü (DGC, Detected Goal Catalyst) içeren yeni bir RL yaklaşımı sunuyoruz. Deneyler, DGC'nin en kısa yolu bulmada hem SARSA hem de Öncelikli Süpürme algoritmalarının öğrenme performansını önemli ölçüde geliştirdiğini göstermektedir.

Automatic software testing methods have become inevitable in producing test inputs. Test tools generate events and execute these events on SUT to find a bug. Unfortunately, when a crash occurs, an event sequence which includes many irrelevant events to the failure is obtained. These irrelevant events make debugging process more difficult. To locate and repair bugs with an emphasis on the crash scenarios, we present in this work a reinforcement learning (RL) approach for finding the shortest input sequence(s) leading to system crash or block where these represent the goal state of the RL problem. We shoot for simplifying the bug scenario as much as possible so that developers would analyze agent’s actions causing crashes or freeze. In this study, we developed Crash Detection Module (CDM) which consists of three main flows. We first simplify the crash scenario given using Recursive Delta Debugging (RDD), then we apply RL algorithms to explore for the shorter crashing sequence. We approach the exploration of crash scenarios as a RL problem where the agent first attains the goal state of crash/ blocking by executing inputs, then shortens the input sequence with the help of the rewarding mechanism. We apply both model-free on-policy and model-based planning-capable RL agents to our problem. Furthermore, we present a novel RL approach, involving Detected Goal Catalyst (DGC), which decreases the time complexity by avoiding grappling with convergence via stopping learning at a small variance and attaining the shortest crash sequence with an algorithm that recursively removes unrelated actions. Experiments show that DGC significantly improves the learning performance of both SARSA and Prioritized Sweeping algorithms on finding the shortest path.