Drogi Do Jakości Testowanie Mutacyjne

Dariusz Cieślak

Dariusz Cieślak, absolwent informatyki na Politechnice Warszawskiej. Zainteresowania zawodowe obejmują programowanie obiektowe i techniki zapewnienia jakości w projektach informatycznych.

Koszty jakości

Znacznym składnikiem czasu tworzenia projektu (i oczywiście jego kosztu) jest wyszukiwanie błędów aplikacji. Zwykle faza ta występuje pod koniec procesu wytwórczego tuż przed oddaniem klientowi systemu (wcześniej jak zwykle "braknie czasu" na gruntowne przetestowanie). W ten sposób klient staje się testerem wyłapującym błędy programistów co drastycznie pogarsza jego opinię o profesjonaliźmie naszej firmy. Tracimy nie tylko czas na wyszukanie błędów ale także wizerunek naszej firmy w oczach klienta. Co więc robić, żeby zmniejszyć koszty związane z niską jakością systemów ? Oczywiście najprościej jest nie popełniać błędów.

Łatwo powiedzieć, trudniej zrobić. Musimy przedsięwziąć specjalne środki żeby z wyszukiwania defektów w wytworzonym produkcie ("tradycyjne" testowanie) przejść do zapobiegania defektom (testowanie wbudowane w proces wytwórczy). Skupiamy wysiłki na jak najwcześniejszym wyłapaniu błędów.

Naprawiać produkt czy proces ?

Po drugiej wojnie światowej w USA w przemyśle motoryzacyjnym stosowano technikę korygowania defektów dopiero po zejściu samochodu z linii produkcyjnej. Przez takie podejście dużo usterek pozostawało nie wykrytych co przyczyniało się do niskiej jakości i zniechęcenie właścicieli aut. Głosy nawołujące do zmiany polityki produkcji pochodzące od Wiliama Edwardsa Deminga, zostały w USA zignorowane. Podatnym gruntem dla idei jakości Deminga stała się dopiero Japonia, gdzie wdrożono techniki zapobiegania defektom podczas produkcji. Produkty japońskie stały się z czasem na rynku amerykańskim symbolem jakości co znalazło swoje odzwierciedlenie w strukturze sprzedaży - zwiększył się udział koncernów japońskich. To była dość kosztowna lekcja dla amerykańskiego przemysłu.

Proste zastosowanie filozofii Deminga składa się z następujących kroków podejmowanych dla każdego zgłoszonego defektu:

1. Zidentyfikowanie błędu
2. Odnalezienie przyczyny powstania błędu
3. Zlokalizowanie punktu w procesie produkcyjnym, który spowodował błąd
4. Korekta procesu tak, by zapewnić, że błąd nie wydarzy się ponownie
5. Ciągłe monitorowanie procesu

Generalną zasadą jest, że korygujemy proces a dopiero potem produkt. A jak to ma się do oprogramowania ? Produkcja oprogramowania jest aktualnie w tej samej fazie co amerykański przemysł samochodowy w latach pięćdziesiątych. Testowaniu podlega dopiero napisany program. Błędy usuwane są jeden po drugim bez usuwania przyczyny ich powstania. Jakość systemów jest taka a nie inna - wielu użytkowników uznaje już błędy w oprogramowaniu za normę.

Niezwykle ważne staje się przejście z myślenia produktami (błędy w oprogramowaniu) na myślenie procesami (błędy w procesie który dopuścił błąd w oprogramowaniu). Właśnie próba zmian w procesie wytwórczym jest podstawowym orężem walki o jakość.

Bardzo ciekawe podejście proponuje metodyka Extreme Programming (o której już była mowa na łamach Software). Znana głównie z kontrowersyjnego programowania w parach, zawiera wiele innych ciekawych rozwiązań. W XP Testowanie Oprogramowania staje się integralną częścią tworzenia systemu. Używając procedury Deminga można napisać:

1. błąd = błąd aplikacji
2. przyczyna = brak wystarczającego testowania
3. punkt w procesie = pisanie kodu
4. korekta = projektowanie testów równolegle z pisaniem kodu (Test Driven Design)
5. monitorowanie = ?

Jak widzimy brakuje nam jeszcze wykonania ostatniego kroku (monitorowanie nowego procesu). W artykule zaproponujemy narzędzie do badania jakości testów względem kodu jakim są techniki mutacyjne.

Programowanie sterowane testami

W praktyce testy rozrastają się do sporych rozmiarów i ich wykonanie zajmuje dużo czasu. Można grupować testy i w trakcie programowania wykonywać tylko wybrane grupy (taki zestaw testów w terminologii bibliotek z rodziny xUnit nazywa się Test Suite). Autor stosuje dość skuteczną praktykę wykonywania testów począwszy od ostatnio zmienianych modułów. Zwykle tam kryją się błędy które musimy wykryć.

Jednym z rozwiązań problemu jakości jest systematyczne testowanie systemu. W Extreme Programming sekwencje testujące powstają w trakcie projektowania przed napisaniem kodu w miniaturowych cyklach: projekt - test - implementacja (ang: Test Driven Development, w skrócie TDD).

Dzięki takiemu podejściu uzyskujemy testowalną architekturę systemu i wymagania zapisane w sposób wykonywalny (poprzez testy). Sprawdzenie, czy implementacja spełnia testy jest w pełni automatyczne i niezawodne (błyskawicznie wykryjemy niespełniony warunek testowy).

Bardzo łatwo jednak jest napisać wiele testów i nie uzyskać poprawy jakości systemu. Powtarzanie assert(1) to przykład złego testu bo nie mówi nic o implementacji. Powstaje więc pytanie: jaki sposób zapewnimy że testy są dobrze napisane (będziemy monitorować proces pisania testów) ?

Jak testować testy ?

Po pierwsze możemy wspomagać się narzędziami do analizy pokryć. W najprostszym przypadku sprawdzamy jaki procent linii kodu został wykonany przez testy. Mamy nadzieję, że wysokie pokrycie kodu przez testy jest wystarczającym wskaźnikiem jakości testów. Jednak testy nie sprawdzające wyników a dające wysokie pokrycie linii kodu dają zafałszowany obraz jakości całego systemu. Sama analiza pokryć nie jest więc wystarczającym wskaźnikiem jakości testów.

Również XP sięgnęło po techniki inspekcji. Programowanie w parach jest szczególną formą ciągłej inspekcji prowadzonej podczas pisania kodu. Piszący i recenzujący zamieniają się co jakiś czas. Oprócz wyłapywania błędów programowanie w parach jest również formą szkolenia nowych programistów.

Innych krokiem, jaki możemy podjąć są inspekcje (lub przeglądy) dokonywane na danych testowych. Pierwsze inspekcje zostały przeprowadzone na szeroką skalę w latach siedemdziesiątych przez Michaela Fagana pracującego dla IBM. Polegają na przeglądzie kodu przez inną osobę niż autor i próbie wychwycenia widocznych błędów lub niezgodności z założeniami projektu. Inspekcje mają też swoje wady: angażują cenny czas specjalistów, ponadto jakość inspekcji nie jest natychmiast widoczna (widać ją dopiero po ilości błędów pochodzących z analizowanego fragmentu systemu).

Idealnie by było znaleźć automatyczne kryterium mówiące nam kiedy testy są niewystarczające i wskazujące, który fragment kodu nie był dostatecznie przetestowany. A może zwalczać błędy innymi błędami?

Testowanie mutacyjne

Rysunek 1. Algorytm testowania mutacyjnego

Rodzina metod testowania opartych na błędach w programie (znana także pod nazwą wstrzykiwanie błędów - ang. fault injection) zakłada, że program napisany przez programistę jest bliski programowi idealnemu (nie zawierającemu błędów). Różnią się fragmentami, w których programista popełnia błędy. Zakładamy, że różnica pomiędzy programem napisanym a idealnym jest niewielka (mamy do czynienia z kompetentnym programistą).

Drugie założenie, które jest podwaliną działania metod opartych na błędach mówi, że jeśli testy wykryją wszystkie błędy proste w programie (np. zastosowanie w jednym miejscu złego operatora) to wykryją też większość złożonych błędów (składających się z wielu błędów prostych) popełnionych przez programistę. Jest to tzw. efekt sprzężenia.

Założenie to opiera się na badaniach w których porównuje się wykrywalność przez testy mutacji pierwszego rzędu (ang. 1-order), które polegają na pojedynczej zmianie w kodzie, z wykrywalnością mutacji wyższego rzędu (ang. n-order), kiedy za jednym razem wstrzykujemy kilka błędów. Okazało się, że testy zabijające mutanty pierwszego rzędu są dość skuteczne w wykrywaniu mutantów wyższych rzędów. Oto fragment z artykułu Jeffersona Offutta z Clemson University który zajmuje się badaniami nad technikami bazującymi na błędach ("Investigation of the Software Testing Coupling Effect"):

"W przypadku gdy używamy testowania mutacyjnego możemy się skupić na mutantach pierwszego rzędu i zignorować mutanty wyższego rzędu. (...) Ważnym praktycznym wnioskiem płynącym z tych wyników jest fakt, że kiedy testujemy oprogramowanie na podstawie małej ilości prostych błędów możemy oczekiwać wykrycia dużo bardziej złożonych błędów."

Przyjmując dwie powyższe hipotezy możemy opracować metodę badania jakości testów. Chcemy, by testy wykryły potencjalne błędy popełnione przez programistę - sprawdźmy więc jak przygotowane testy radzą sobie z błędami prostymi. Jeśli wszystkie sztucznie wstrzyknięte proste błędy w programie zostaną wykryte przez testy, to możemy uznać, że testy są wystarczająco dobre.

Zmodyfikowany program zwany jest "mutantem". W sytuacji kiedy przygotowane testy nie zauważą mutanta mamy do czynienia z "żywym mutantem". Na podstawie informacji o wstrzykniętym błędzie możemy rozszerzać testy aż do momentu zabicia wszystkich mutantów (rysunek 1).

Zwróćmy uwagę na pierwszy krok algorytmu. Należy sprawdzić, czy niezmutowany program jest akceptowany przez testy. Jeśli wystąpiła by taka sytuacja, to Testowanie Mutacyjne będzie bezsensowne. Dlaczego ? Mutanty zostaną zabite przez dowolny test i możemy ten stan błędnie zinterpretować jako wystarczająco dobry poziom testów.

Graf stanów osiągalnych Każdy program komputerowy można zamodelować jako zbiór stanów (np. dla obiektu "drzwi" mogą to być stany: "otwarte", "zamknięte", "zablokowane"). Na skutek czynników zewnętrznych lub upływającego czasu stan systemu może ulec zmianie. Ale nie wszystkie przejścia pomiędzy stanami są możliwe (np. ze stanu "otwarte" do "zablokowane"). Na podstawie informacji o możliwych przejściach można utworzyć graf stanów osiągalnych systemu. Ścieżka w takim grafie to jeden wybrany scenariusz działania systemu.

Można też spojrzeć na Testowanie Mutacyjne inaczej: Implementacja oraz testy stanowią dwa różne obrazy działającego programu. Implementacja stanowi szczegółowy obraz ściśle definiujący zachowanie programu. Testy natomiast są obrazem fragmentarycznym opisującym pewien podzbiór ścieżek w grafie stanów osiągalnych programu. Błędy w implementacji zwykle popełniane są nieświadomie. Jeśli popełnimy błąd w implementacji, to dobrze napisane testy powinny ten błąd wychwycić. Przy odpowiednim poziomie jakości testów wprowadzenie błędów do implementacji staje się wręcz trudne!

A jak sprawdzić czy testy są napisane wystarczająco dobrze? Wprowadzamy świadomie do programu błędy (tworzymy mutanty) i sprawdzamy, czy zostaną one wykryte przez testy. Poziomem działania narzędzia mutacyjnego można sterować na dwa sposoby:

• Dla zdefiniowane i stałego zbioru mutacji osiągać poprzez testowanie odpowiednio wysoki stosunek mutantów martwych do wszystkich mutantów (np. 0.9).
• Zmieniając ilość rodzajów mutacji (np. zamiana operatora "+" na "-", dodatnie negacji do warunku logicznego itp.) dążyć do zabicia wszystkich mutantów poprzez rozbudowę testów.

Oczywiście powyższe podejścia można łączyć. Każde wykrycie błędu, który nie został przechwycony na etapie automatycznych testów może być sygnałem do rozbudowy zbioru rodzajów mutacji. Elastyczne podejście pozwala nam na inkrementalne wdrażanie testowania mutacyjnego - począwszy od najprostszych mutacji lub zaczynając od wybranych najważniejszych modułów systemu.

Konstrukcja przykładowego mutatora

Aby uniknąć skomplikowanej analizy składniowej użyjemy języka AWK wraz z jego wyrażeniami regularnymi. Jest to prosty język skryptowy z rodowodem unixowym o dość eleganckiej i czytelnej składni. Do naszych zastosowań w zupełności wystarczy. Językiem docelowym będzie Python (język ten ma bardzo dobrze skonstruowany mechanizm wyjątków z którego skorzystamy).

Najbardziej oczywistą implementacją jest wygenerowanie serii programów (w każdym z nich jest wprowadzony jeden błąd w stosunku do oryginału). Następnie uruchamiamy po kolei każdy z wygenerowanych programów szukając takiego, w którym testy nie wykryją wprowadzonej mutacji.

My zastosujemy sprytniejsze podejście: wygenerujemy jeden program (zwany metamutantem), który w kolejnych uruchomieniach (w pętli) będzie przybierał różne postacie. Dzięki temu unikniemy narzutu na kompilację/ładowanie poszczególnych mutantów.

W pierwszej kolejności trzeba wybrać miejsca w kodzie programu, które nadają się do wstrzyknięcia mutantów (listing 1). Jest to uzależnione od składni docelowego języka programowania. Zastosowanie wyrażeń regularnych i cech języka AWK pozwala wygodnie opisać wprowadzanie mutantów.

Listing 1. Wybieranie wierszy w kodzie do mutacji
function dodaj_linie(numer_wiersza) {
   if(linie)
      linie = linie ", "
   linie = linie numer_wiersza
}

/if / {
   sub(/if /, "if _mutant(" FNR ", ")
   zamknacNawias = 1
   dodaj_linie(FNR)
}
/return / {
   sub(/return /, "return _mutant(" FNR ", ")
   zamknacNawias = 1
   dodaj_linie(FNR)
}
zamknacNawias && /:$/ {
   sub(/:$/, "):")
   zamknacNawias = 0
}
zamknacNawias && !/,$/ && !/\\$/{
   sub(/$/, ")")
   zamknacNawias = 0
}

Funkcja dodaj linie() (listing 1) tworzy listę numerów wierszy, gdzie został dodany kod metamutanta. Funkcja  mutant() przyjmuje jako argumenty: numer linii w którym występuje mutant i oryginalną wartość, która będzie podlegać mutacji. Mutant uaktywnia się kiedy numer wiersza przechowywany w zmiennej  mutant_line pasuje do numeru przypisanego mutantowi. Kiedy nie pasuje, to funkcja  mutant() zwraca wartość oryginalną. W ten sposób zmienna  mutant_line aktywuje po kolei wszystkie mutanty.

Trywialny przykład

Listing 2. Funkcja sumująca dodatnie elementy listy
def suma_dodatnich(lista):

   suma = 0
   for x in lista:
      if x > 0:
         suma = suma + x
   return suma

def test():

   assert suma_dodatnich([]) == 0
   assert suma_dodatnich([1, 2, 3]) == 6

Dla rozgrzewki sprawdźmy jak nasz pupil poradzi sobie z dość prostym programikiem (Listing 2). Funkcja suma dodatnich sumuje dodatnie liczby na liście przekazanej jako argument. Do przykładu dołączony jest test. Daje on 100% pokrycia linii kodu programu, ale nie sprawdza przypadku, kiedy w liście przekazanej jako argument znajdzie się element ujemny.

Zobaczmy, jak w tym momencie zadziała analizator mutacyjny:

   suma_dodatnich.py:6: 1 mutant caught

Wskazana linia to "if x > 0:". Mutant powstały poprzez zmianę tej linii na "if 1:" nie został wykryty poprzez testy. Oznacza to, że testy nie są pełne według kryterium zastosowanych mutacji. W tym prostym przypadku braki w testach widać na pierwszy rzut oka -- w bardziej złożonym module mogą być one łatwo przeoczone (i wtedy najpełniej ujawniają się zalety testowania mutacyjnego).

Zobaczmy, co się stanie jeśli jeden z programistów spełni wymaganie pokrycia linii kodu i nawet poda dobre dane wejściowe ale nie sprawdzi wyników. Takie testy są niebezpieczne, bo dają fałszywe poczucie działania kodu (jest pokrycie linii kodu 100 %) podczas gdy dowiadujemy się tylko, że kod nie wygenerował wyjątku. Taki test jest pokazany na listingu 3.

Listing 3. 'Oszukany' test - brak sprawdzenia wyników
def test():

   suma_dodatnich([])
   suma_dodatnich([1, 2, 3])
   suma_dodatnich([1, -2, 3])
   suma_dodatnich([-1, -2, -3])
   assert 1

   suma_dodatnich.py:6: 0 mutant caught
   suma_dodatnich.py:6: 1 mutant caught
   suma_dodatnich.py:8: 0 mutant caught
   suma_dodatnich.py:8: 1 mutant caught

Powyżej widzimy odpowiedź testera mutacyjnego. Zostały wychwycone cztery żywe mutanty. Widać tu wyraźną przewagę testowania mutacyjnego nad analizą pokryć: nie da się w prosty sposób "oszukać" mutatora uruchamiając po prostu poszczególne ścieżki w kodzie. Trzeba świadomie dodać testy na odpowiednim poziomie szczegółowości.

"Agresywnością" (dokładnością sprawdzania) mutatora możemy sterować poprzez ilość rodzajów mutacji. Jeśli chcemy, by specyfikacja była pełniejsza - dodajemy więcej rodzajów mutacji. Gdy nie chcemy specyfikować zbyt szczegółowo zmniejszamy zbiór rodzajów mutacji.

Na listingu 4 pokazano minimalny test, który zabija wszystkie mutanty w programie.

Listing 4. Minimalny poprawny test
def test():

   assert suma_dodatnich([-2, 3]) == 3

Mutanty zawieszające system

Zmutowany program zwykle spowoduje rzucenie wyjątku (np. próbując indeksować element tablicy spoza zakresu) lub błąd w testach (zły wynik funkcji). Może się zdarzyć jednak sytuacja kiedy mutant zawiesi program. Funkcja pokazana na listingu 5 zlicza ilość pustych wierszy w otwartym pliku przekazanym jako argument. W funkcji testującej posługujemy się klasą String IO, która na podstawie ciągów znaków "udaje" otwarty plik. Dzięki temu rozwiązaniu nie musimy tworzyć (i martwić się o usunięcie) plików tymczasowych.

Listing 5. Mutant wieszający program
def ilosc_pustych_linii(plik):

   licznik = 0

   while 1:

      linia = plik.readline()

      if not linia:
         break

      if linia == "\n":
         licznik = licznik + 1
   
   return licznik

def test():

   import StringIO

   s = StringIO.StringIO("a\nbc\n\nd")
   assert ilosc_pustych_linii(s) == 1,\
      "zła ilość pustych linii"

   s = StringIO.StringIO("\n\n\nd")
   assert ilosc_pustych_linii(s) == 3,\
      "zła ilość pustych linii"

Program ulegnie zawieszeniu w wyniku wprowadzenia mutacji do fragmentu:

   if not linia:
      break

Po mutacji fragment będzie wyglądał następująco:

   if 0:
      break

Mutant spowoduje, że warunek zakończenia pętli nigdy nie będzie sprawdzony i system utknie w pętli. Jak się przed tym ustrzec ? Możemy poradzić sobie na dwa sposoby:

Po pierwsze wyszukiwać zapętlenia programu zakładając maksymalną ilość wykonań pętli. Jeśli linia z mutantem wykonuje się zbyt wiele razy rzucamy wyjątek. Sposób implementacji pokazano na listingu 6. Założono tu, że pętla nie będzie się wykonywać więcej niż sto razy.

Listing 6. Zabezpieczenie przed zapętleniem (AWK)
END {
   print "def _mutant(line, orginalValue):"
   print "\tglobal _mutant_line"
   print "\tglobal _mutant_value"
   print "\tglobal _mutant_count"
   print "\t_mutant_count = _mutant_count + 1"
   print "\tif _mutant_count > 100:"
   print "\t\traise 'ZapetlenieError'"
   print "\tif line == _mutant_line:"
   print "\t\treturn _mutant_value"
   print "\treturn orginalValue"
   print ""
   print "global _mutant_line"
   print "_mutant_line = -1"
   print "global _mutant_value"
   print "_mutant_value = -1"
   print "global _mutant_count"
   print "_mutant_count = 0"
   for(test in testy) {
      print test "()"
   }
   print "for _mutant_line in [" linie "]:"
   print "\tfor _mutant_value in [ 0, 1 ]:"
   print "\t\t_mutant_count = 0"
   print "\t\ttry:"
   for(test in testy) {
      print "\t\t\t" test "()"
   }
   print "\t\texcept:"
   print "\t\t\t# OK, catched mutant"
   print "\t\t\tpass"
   print "\t\telse:"
   print "\t\t\tprint '" fileName ":%d:' % _mutant_line, _mutant_value, 'mutant caught'"
   print ""
}

Możemy także blokować wybiórczo generowanie mutantów w programie w miejscach, gdzie prowadzą one do zapętlenia. W kodzie docelowym zapisujemy w komentarzach dyrektywy sterujące pracą mutatora (tu: MUTATOR:START i MUTATOR:STOP) które pozwolą pominąć niechciane mutanty. Implementację pokazano na listingu 7.

Listing 7. Wyłączanie fragmentów kodu z mutowania (AWK)
/MUTATOR:STOP/ {
   mutatorStop = 1
}
/MUTATOR:START/ {
   mutatorStop = 0
}
mutatorStop {
   print
   next
}

Powyższa sztuczka ma jeszcze jedno ciekawe zastosowanie. Przy złożonych modułach uruchamianie kilkadziesiąt razy (tyle ile zostało wygenerowanych mutantów) wszystkich testów może być czasochłonne. Posługując się dyrektywami MUTATOR:START i MUTATOR:STOP możemy sprawdzać pokrycie implementacji przez testy "po kawałku" pomijając już fragmenty, gdzie nie pozostał ani jeden żywy mutant. Przyspiesza to znacznie Testowanie Mutacyjne.

Wpływ testowania na architekturę

W sieci http://citeseer.ist.psu.edu - obszerna biblioteka literatury naukowej i technicznej on-line

Podejście TDD wymusza pilnowanie testowalności architektury. Moduły muszą mieć jak najmniejsze zależności od innych modułów aby można je było testować w izolacji. Jeśli coś jest skomplikowane do inicjalizacji (wymaga wiele kodu), to jest bardzo prawdopodobne, że zautomatyzowany test nigdy nie zostanie napisany. Programowanie sterowane testami więc dba o sprzężenia w projekcie. Działa to też w drugą stronę: jeśli pisanie testów idzie "ciężko" to możemy podejrzewać, że moduł został źle zaprojektowany.

Rozważmy następujący przypadek: w module wprowadzono 100 mutantów. Ilość testów jednostkowych wynosi 10. Zakładając, że średnio dla każdego mutanta należy sprawdzić 5 testów aby trafić na wykrywający, ilość wykonanych testów wyniesie 500. Widzimy więc, że Testowanie Mutacyjne dużych modułów jest czasochłonne. W pesymistycznym przypadku wszystkie testy modułu trzeba wykonywać dla każdego z wprowadzonych mutantów. Testowanie mutacyjne zmusza więc nas pośrednio do pilnowania maksymalnej wielkości modułów.

Inny przypadek: moduł A korzysta z funkcjonalności modułu B. Testy są napisane tylko dla modułu B. Pomimo, że funkcjonalność A będzie przetestowana poprzez testy pisane dla B (to już są testy integracyjne), to analiza mutacyjna samego modułu A wykaże, że wszystkie mutanty są żywe! Dzieje się tak, ponieważ testowaliśmy funkcjonalność jednej warstwy w warstwie wyższej. Dla modułu A zabrakło testów jednostkowych.

Można by rzec, że Testowanie Mutacyjne to "papierek lakmusowy" nie tylko dla jakości testów, ale także dla poprawności architektury systemu.

Zamiast podsumowania

Autor rozwija system do zarządzania firmą w architekturze klient - serwer o wielkości 35 tysięcy linii kodu (152 moduły, około 500 sekwencji testowych) w stylu inkrementalnym (system cały czas pracuje na rzeczywistych danych). Taki tryb pracy wymusił konieczność pilnowania jakości na każdym kroku (potencjalne błędy utrudnią lub uniemożliwią pracę wielu osobom). Testowanie mutacyjne zostało wybrane jako efektywne narzędzie wspomagające i w tym projekcie sprawdza się znakomicie.