Czy zasięg ścieżki gwarantuje znalezienie wszystkich błędów?

64

Jeśli testowana jest każda ścieżka przez program, czy gwarantuje to znalezienie wszystkich błędów?

Jeśli nie, dlaczego nie? Jak można przejść przez każdą możliwą kombinację przebiegu programu i nie znaleźć problemu, jeśli taki istnieje?

Waham się z sugestią, że można znaleźć „wszystkie błędy”, ale może dlatego, że pokrycie ścieżki nie jest praktyczne (ponieważ jest kombinatoryczne), więc nigdy nie jest doświadczane?

Uwaga: ten artykuł zawiera krótkie podsumowanie rodzajów pokrycia, gdy o nich myślę.


źródło
33
Jest to równoważne z problemem zatrzymania .
31
Co, jeśli kod, który powinien tam być, prawda?
RemcoGerlich
6
@Snowman: Nie, nie jest. Nie można rozwiązać problemu zatrzymania dla wszystkich programów, ale dla wielu konkretnych programów można go rozwiązać. W przypadku tych programów wszystkie ścieżki kodu można wyliczyć w skończonym (choć prawdopodobnie długim) czasie.
Jørgen Fogh
3
@ JørgenFogh Ale kiedy próbujesz znaleźć błędy w jakimkolwiek programie, czy nie jest a priori nieznane, czy program się zatrzymuje, czy nie? Czy nie jest to pytanie dotyczące ogólnej metody „znajdowania wszystkich błędów w dowolnym programie za pomocą zasięgu ścieżki”? W takim przypadku, czy nie jest to podobne do „stwierdzenia, czy jakiś program się zatrzymuje”?
Andres F.
1
@AndresF. nie wiadomo tylko, czy program się zatrzyma, jeśli podzbiór języka, w którym jest napisany, jest zdolny do wyrażania programu bez zatrzymywania. Jeśli twój program jest napisany w C bez użycia niezwiązanych pętli / rekurencji / setjmp itp., Lub w Coq lub w ESSL, to musi się zatrzymać i wszystkie ścieżki można prześledzić. (Kompletność Turinga jest poważnie przereklamowana)
Leushenko

Odpowiedzi:

128

Jeśli testowana jest każda ścieżka przez program, czy gwarantuje to znalezienie wszystkich błędów?

Nie

Jeśli nie, dlaczego nie? Jak można przejść przez każdą możliwą kombinację przebiegu programu i nie znaleźć problemu, jeśli taki istnieje?

Ponieważ nawet jeśli przetestujesz wszystkie możliwe ścieżki , nadal nie przetestowałeś ich ze wszystkimi możliwymi wartościami lub wszystkimi możliwymi kombinacjami wartości . Na przykład (pseudokod):

def Add(x as Int32, y as Int32) as Int32:
   return x + y

Test.Assert(Add(2, 2) == 4) //100% test coverage
Add(MAXINT, 5) //Throws an exception, despite 100% test coverage

Minęły już dwie dekady, odkąd wskazano, że testy programu mogą w przekonujący sposób wykazać obecność błędów, ale nigdy nie mogą wykazać ich braku. Po zacytowaniu tej dobrze nagłośnionej uwagi inżynier oprogramowania wraca do porządku dnia i kontynuuje udoskonalanie swoich strategii testowych, podobnie jak dotychczasowy alchemik, który nadal udoskonalał swoje chryzokosmiczne oczyszczenia.

- EW Dijkstra (Podkreślenie dodane. Napisane w 1988 roku. To już znacznie więcej niż 2 dekady.)

Mason Wheeler
źródło
7
@digitgopher: Podejrzewam, ale jeśli program nie ma danych wejściowych, co to za użyteczna rzecz?
Mason Wheeler
34
Istnieje również możliwość pominięcia testów integracyjnych, błędów w testach, błędów w zależnościach, błędów w systemie kompilacji / wdrażania lub błędów w oryginalnej specyfikacji / wymaganiach. Nigdy nie możesz zagwarantować znalezienia wszystkich błędów.
Ixrec
11
@Ixrec: SQLite robi jednak dość dzielny wysiłek! Ale spójrz, jaki to ogromny wysiłek! To nie byłoby dobrze skalowane do dużych baz kodowych.
Mason Wheeler
13
Nie tylko nie przetestowałbyś wszystkich możliwych wartości lub ich kombinacji, ale nie przetestowałeś wszystkich względnych czasów, z których niektóre mogą narazić warunki wyścigu lub nawet spowodować, że Twój test wejdzie w impas, co sprawi, że nic nie zgłosisz . To nawet nie byłby błąd!
Nie będę istniał Idonotexist
14
Przypominam sobie (wsparte takimi pismami ), że Dijkstra uważał, że w dobrych praktykach programistycznych dowód, że program jest poprawny (we wszystkich warunkach), powinien przede wszystkim stanowić integralną część jego rozwoju. Z tego punktu widzenia testowanie jest jak alchemia. Zamiast hiperboli uważam, że była to bardzo silna opinia wyrażona bardzo silnym językiem.
David K
71

Oprócz odpowiedzi Masona istnieje jeszcze jeden problem: zasięg nie mówi, jaki kod został przetestowany, ale mówi, który kod został wykonany .

Wyobraź sobie, że masz testsuite ze 100% pokryciem trasy. Teraz usuń wszystkie asercje i ponownie uruchom testsuite. Voilà, testsuite wciąż ma 100% pokrycia trasy, ale absolutnie nic nie testuje.

Jörg W Mittag
źródło
2
Może upewnić się, że nie ma wyjątku podczas wywoływania testowanego kodu (z parametrami w teście). To nieco więcej niż nic.
Paŭlo Ebermann
7
@ PaŭloEbermann Zgoda, nieco więcej niż nic. Jest to jednak znacznie mniej niż „znalezienie wszystkich błędów”;)
Andres F.
1
@ PaŭloEbermann: Wyjątki to ścieżka do kodu. Jeśli kod może zostać wygenerowany, ale przy pewnych danych testowych nie zostanie wygenerowany, test nie osiągnie 100% pokrycia ścieżki. Nie jest to specyficzne dla wyjątków jako mechanizmu obsługi błędów. Visual Basic na ON ERROR GOTOto również droga, jak jest na C if(errno).
MSalters
1
@MSalters Mówię o kodzie, który (według specyfikacji) nie powinien zgłaszać żadnych wyjątków, niezależnie od danych wejściowych. Jeśli coś wyrzuci, byłby to błąd. Oczywiście, jeśli masz kod, który ma wyrzucać wyjątek, należy go przetestować. (I oczywiście, jak powiedział Jörg, samo sprawdzenie, czy kod nie generuje wyjątku, zwykle nie wystarcza, aby upewnić się, że działa poprawnie, nawet w przypadku kodu nie rzucającego.) A niektóre wyjątki mogą zostać zgłoszone przez - widoczna ścieżka do kodu, jak w przypadku zerowania wskaźnika zerowego lub dzielenia przez zero. Czy narzędzie do pokrywania ścieżek je łapie?
Paŭlo Ebermann
2
Ta odpowiedź przybija. Chciałbym pójść o krok dalej i powiedzieć, że z tego powodu pokrycie ścieżki nigdy nie gwarantuje znalezienia choćby jednego błędu. Istnieją dane, które mogą zagwarantować co najmniej, że zostaną wykryte zmiany, jednak - badanie mutacji w rzeczywistości może zagwarantować, że (niektóre) modyfikacje kodu będzie zostać wykryte.
eis
34

Oto prostszy przykład na zakończenie. Rozważ następujący algorytm sortowania (w Javie):

int[] sort(int[] x) { return new int[] { x[0] }; }

Teraz przetestujmy:

sort(new int[] { 0xCAFEBABE });

Teraz rozważmy, że (A) to konkretne wywołanie sortzwraca poprawny wynik, (B) wszystkie ścieżki kodu zostały objęte tym testem.

Ale oczywiście program nie sortuje.

Wynika z tego, że pokrycie wszystkich ścieżek kodu nie jest wystarczające, aby zagwarantować, że program nie zawiera błędów.

Atsby
źródło
12

Rozważ absfunkcję, która zwraca wartość bezwzględną liczby. Oto test (Python, wyobraź sobie jakiś szkielet testowy):

def test_abs_of_neg_number_returns_positive():
    assert abs(-3) == 3

Ta implementacja jest poprawna, ale zapewnia jedynie 60% pokrycia kodu:

def abs(x):
    if x < 0:
        return -x
    else:
        return x

Ta implementacja jest niepoprawna, ale zapewnia 100% pokrycia kodu:

def abs(x):
    return -x
RemcoGerlich
źródło
2
Oto kolejna implementacja, która pomyślnie przechodzi test (proszę wybaczyć Pythonowi, który nie łamie linii): def abs(x): if x == -3: return 3 else: return 0Możliwe, że pominiesz tę else: return 0część i uzyskasz 100% pokrycia, ale funkcja byłaby zasadniczo bezużyteczna, nawet jeśli przejdzie test jednostkowy.
CVn
7

Kolejny dodatek do odpowiedzi Masona , zachowanie programu może zależeć od środowiska wykonawczego.

Poniższy kod zawiera opcję Use-After-Free:

int main(void)
{
    int* a = malloc(sizeof(a));
    int* b = a;
    *a = 0;
    free(a);
    *b = 12; /* UAF */
    return 0;
}

Ten kod jest niezdefiniowanym zachowaniem, w zależności od konfiguracji (wydania | debugowania), systemu operacyjnego i kompilatora, przyniesie różne zachowania. Zasięg ścieżki nie tylko nie gwarantuje, że znajdziesz UAF, ale Twój zestaw testów zazwyczaj nie obejmuje różnych możliwych zachowań UAF, które zależą od konfiguracji.

Z drugiej strony, nawet jeśli pokrycie ścieżki gwarantowałoby znalezienie wszystkich błędów, jest mało prawdopodobne, że można to osiągnąć w praktyce w dowolnym programie. Rozważ następujące:

int main(int a, int b)
{
    if (a != b) {
        if (cryptohash(a) == cryptohash(b)) {
            return ERROR;
        }
    }
    return 0;
} 

Jeśli Twój pakiet testowy może wygenerować wszystkie ścieżki do tego, gratulacje, jesteś kryptografem.

dureuill
źródło
Łatwe dla wystarczająco małych liczb całkowitych :)
CodesInChaos
Nie wiedząc o niczym cryptohash, trudno jest powiedzieć, czym jest „wystarczająco mały”. Może ukończenie superkalkulatora zajmuje dwa dni. Ale tak, intmoże okazać się trochę short.
dureuill
Przy 32-bitowych liczbach całkowitych i typowych skrótach kryptograficznych (SHA2, SHA3 itp.) Obliczenia powinny być dość tanie. Kilka sekund.
CodesInChaos
7

Z pozostałych odpowiedzi jasno wynika, że ​​100% pokrycia kodu w testach nie oznacza 100% poprawności kodu, ani nawet że wszystkie błędy, które można znaleźć podczas testowania, zostaną znalezione (nie wspominając o błędach, których żaden test nie może wyłapać).

Innym sposobem odpowiedzi na to pytanie jest praktyka:

W prawdziwym świecie, a nawet na własnym komputerze, jest wiele programów, które są opracowywane przy użyciu zestawu testów, które zapewniają 100% pokrycia, a które nadal zawierają błędy, w tym błędy, które można by lepiej zidentyfikować.

W związku z tym powstaje pytanie:

Jaki jest sens narzędzi pokrycia kodu?

Narzędzia pokrycia kodu pomagają zidentyfikować obszary, których testowanie zostało zaniedbane. To może być w porządku (kod jest wyraźnie poprawny nawet bez testowania), może być niemożliwe do rozwiązania (z jakiegoś powodu nie można trafić na ścieżkę), lub może być lokalizacją wielkiego śmierdzącego błędu albo teraz, albo po przyszłych modyfikacjach.

Pod pewnymi względami sprawdzanie pisowni jest porównywalne: Coś może „przejść” sprawdzanie pisowni i zostać błędnie napisane w taki sposób, aby pasowało do słowa w słowniku. Lub może „zawieść”, ponieważ poprawnych słów nie ma w słowniku. Lub może przejść i być kompletnym nonsensem. Sprawdzanie pisowni to narzędzie, które pomaga zidentyfikować miejsca, które mogły zostać pominięte podczas korekty, ale podobnie jak nie może zagwarantować pełnego i prawidłowego odczytu, tak więc pokrycie kodu nie może zagwarantować pełnego i poprawnego testowania.

I oczywiście niewłaściwy sposób użycia sprawdzania pisowni jest znany z każdej sugestii, jaką sugeruje owca morska, więc sytuacja kaczki staje się gorsza niż wtedy, gdy zostawiamy pożyczkę.

Z pokryciem kodu może być kuszące, zwłaszcza jeśli masz prawie idealne 98%, wypełnianie skrzynek, tak aby pozostałe ścieżki zostały trafione.

Jest to odpowiednik wyrównywania za pomocą sprawdzania pisowni, że wszystkie słowa to pogoda lub węzeł to wszystkie odpowiednie słowa. Rezultatem jest bałaganiarski bałagan.

Jeśli jednak zastanowisz się, jakie testy naprawdę nieobjęte ścieżki naprawdę potrzebują, narzędzie do pokrywania kodu wykona swoje zadanie; nie obiecując ci poprawności, ale wskazując niektóre prace, które należało wykonać.

Jon Hanna
źródło
+1 Podoba mi się ta odpowiedź, ponieważ jest konstruktywna i wspomina o niektórych korzyściach z zasięgu.
Andres F.
4

Zasięg ścieżki nie pozwala stwierdzić, czy wszystkie wymagane funkcje zostały zaimplementowane. Pozostawienie funkcji jest błędem, ale pokrycie ścieżki jej nie wykryje.

Pete Becker
źródło
1
Myślę, że to zależy od definicji błędu. Nie sądzę, że brakujące funkcje lub funkcje powinny być traktowane jako błędy.
eis
@eis - nie widzisz problemu z produktem, którego dokumentacja mówi, że robi X, a tak naprawdę nie? To dość wąska definicja „błędu”. Kiedy zarządzałem kontrolą jakości linii produktów C ++ firmy Borland, nie byliśmy aż tak hojni.
Pete Becker
Nie widzę dlaczego dokumentacja powie to robi X czy że nigdy nie został zrealizowany
eis
@eis - jeśli oryginalny projekt wymagał funkcji X, dokumentacja mogłaby w końcu opisywać funkcję X. Jeśli nikt jej nie zaimplementował, jest to błąd, a pokrycie ścieżki (lub jakikolwiek inny test czarnej skrzynki) go nie znajdzie.
Pete Becker
Ups, zasięg ścieżki to testowanie białej skrzynki , a nie czarnej skrzynki . Testowanie białych skrzynek nie wykrywa brakujących funkcji.
Pete Becker
4

Częścią problemu jest to, że 100% pokrycia gwarantuje tylko, że kod będzie działał poprawnie po jednym wykonaniu . Niektóre błędy, takie jak wycieki pamięci, mogą nie być widoczne lub powodować problemy po jednym wykonaniu, ale z czasem będą powodować problemy dla aplikacji.

Załóżmy na przykład, że masz aplikację, która łączy się z bazą danych. Być może w jednej z metod programista zapomina o zamknięciu połączenia z bazą danych po zakończeniu zapytania. Można uruchomić kilka testów tej metody i nie wykryć żadnych błędów w jej działaniu, ale serwer bazy danych może napotkać scenariusz, w którym nie ma dostępnych połączeń, ponieważ ta konkretna metoda nie zamknęła połączenia, gdy zostało wykonane, a otwarte połączenia muszą teraz limit czasu.

Derek W.
źródło
Zgodził się, że to część problemu, ale prawdziwy problem jest bardziej fundamentalny. Nawet z teoretycznym komputerem z nieskończoną pamięcią i bez współbieżności, 100% pokrycia testowego nie oznacza braku błędów. Trywialne przykłady tego obfitują w odpowiedzi tutaj, ale tutaj jest inna: jeśli mój program jest times_two(x) = x + 2, zostanie to w pełni objęte pakietem testowym assert(times_two(2) == 4), ale nadal jest to oczywiście błędny kod! Nie ma potrzeby wycieków pamięci :)
Andres F.
2
To świetna uwaga i zdaję sobie sprawę, że jest to większy / bardziej fundamentalny gwóźdź do trumny możliwości aplikacji wolnych od błędów, ale jak mówisz, został już tutaj dodany i chciałem dodać coś, co nie było całkiem pokryte istniejące odpowiedzi. Słyszałem o aplikacjach, które uległy awarii, ponieważ połączenia z bazą danych nie zostały zwolnione z powrotem do puli połączeń, gdy nie były już potrzebne - Wyciek pamięci jest tylko kanonicznym przykładem niewłaściwego zarządzania zasobami. Chodzi mi o to, aby dodać, że właściwego zarządzania zasobami w ogóle nie można całkowicie przetestować.
Derek W
Słuszna uwaga. Zgoda.
Andres F.
3

Jeśli testowana jest każda ścieżka przez program, czy gwarantuje to znalezienie wszystkich błędów?

Jak już powiedziano, odpowiedź brzmi NIE.

Jeśli nie, dlaczego nie?

Poza tym, co się mówi, na różnych poziomach pojawiają się błędy, których nie można przetestować za pomocą testów jednostkowych. Wystarczy wspomnieć o kilku:

  • błędy wykryte podczas testów integracyjnych (testy jednostkowe nie powinny przecież wykorzystywać rzeczywistych zasobów)
  • błędy w wymaganiach
  • błędy w projektowaniu i architekturze
BЈовић
źródło
2

Co to znaczy dla każdej ścieżki do przetestowania?

Inne odpowiedzi są świetne, ale chcę tylko dodać, że sam warunek „każda ścieżka przez program jest testowany” jest niejasny.

Rozważ tę metodę:

def add(num1, num2)
  foo = "bar"  # useless statement
  $global += 1 # side effect
  num1 + num2  # actual work
end

Jeśli napiszesz test, który potwierdza add(1, 2) == 3, narzędzie do pokrycia kodu powie ci, że każda linia jest wykonywana. Ale tak naprawdę nie twierdziłeś nic o globalnym skutku ubocznym lub bezużytecznym zadaniu. Te wiersze zostały wykonane, ale tak naprawdę nie zostały przetestowane.

Testowanie mutacji pomogłoby znaleźć takie problemy. Narzędzie do testowania mutacji ma listę z góry określonych sposobów „mutowania” kodu i sprawdzania, czy testy nadal przebiegają pomyślnie. Na przykład:

  • Jedna mutacja może zmienić +=się -=. Ta mutacja nie spowodowałaby niepowodzenia testu, więc udowodniłaby, że test nie potwierdza niczego znaczącego na temat globalnego efektu ubocznego.
  • Inna mutacja może usunąć pierwszą linię. Ta mutacja nie spowodowałaby niepowodzenia testu, więc udowodniłaby, że twój test nie potwierdza niczego istotnego w zadaniu.
  • Jeszcze inna mutacja może usunąć trzecią linię. Spowodowałoby to niepowodzenie testu, co w tym przypadku pokazuje, że Twój test potwierdza coś o tej linii.

W skrócie, testy mutacji są sposobem na przetestowanie testów . Ale tak jak nigdy nie przetestujesz rzeczywistej funkcji przy każdym możliwym zestawie danych wejściowych, nigdy nie uruchomisz każdej możliwej mutacji, więc znowu jest to ograniczone.

Każdy test, który możemy wykonać, jest heurystyczny w kierunku programów wolnych od błędów. Nic nie jest doskonałe.

Nathan Long
źródło
0

Cóż ... tak, właściwie, jeśli każda ścieżka „przez” program jest testowana. Ale to oznacza, że ​​każda możliwa ścieżka przez całą przestrzeń wszystkich możliwych stanów, jakie może mieć program, łącznie ze wszystkimi zmiennymi. Nawet w przypadku bardzo prostego statycznie skompilowanego programu - powiedzmy, starego crunchera liczb Fortran - nie jest to wykonalne, chociaż może to być przynajmniej możliwe: jeśli masz tylko dwie zmienne całkowite, masz do czynienia ze wszystkimi możliwymi sposobami łączenia punktów na dwuwymiarowa siatka; w rzeczywistości przypomina bardzo Traveling Salesman. Dla n takich zmiennych mamy do czynienia z przestrzenią n- wymiarową, więc dla każdego prawdziwego programu zadanie jest całkowicie niewykonalne.

Gorzej: poważnie mówiąc, masz nie tylko stałą liczbę prymitywnych zmiennych, ale tworzysz zmienne w locie w wywołaniach funkcji lub masz zmienne o zmiennej wielkości ... lub cokolwiek podobnego, jak to możliwe, w języku kompletnym Turinga. To sprawia, że ​​przestrzeń stanu jest nieskończenie wymiarowa, niszcząc wszelkie nadzieje na pełne pokrycie, nawet biorąc pod uwagę absurdalnie potężny sprzęt testowy.


To powiedziawszy ... w rzeczywistości rzeczy nie są tak ponure. To jest możliwe, aby udowodnić całych programów za prawidłowe, ale będziesz musiał zrezygnować z kilku pomysłów.

Po pierwsze: wysoce wskazane jest przejście na deklaratywny język. Języki imperatywne, z jakiegoś powodu, zawsze były zdecydowanie najbardziej popularne, ale sposób ich mieszać ze sobą algorytmów z interakcji w świecie rzeczywistym sprawia, że niezwykle trudno nawet powiedzieć, co masz na myśli przez „poprawne”.

Znacznie łatwiej w czysto funkcjonalnych językach programowania: mają one wyraźne rozróżnienie między naprawdę interesującymi właściwościami funkcji matematycznych a rozmytymi interakcjami w świecie rzeczywistym, o których tak naprawdę nie można nic powiedzieć. W przypadku funkcji bardzo łatwo jest określić „prawidłowe zachowanie”: jeśli dla wszystkich możliwych danych wejściowych (z typów argumentów) pojawi się odpowiedni pożądany wynik, wówczas funkcja zachowuje się poprawnie.

Mówicie, że wciąż jest to trudne ... w końcu przestrzeń wszystkich możliwych argumentów jest na ogół również nieskończona. To prawda - choć w przypadku jednej funkcji nawet naiwne testowanie zasięgu prowadzi o wiele dalej, niż można się spodziewać w programie imperatywnym! Istnieje jednak niesamowicie potężne narzędzie, które zmienia grę: uniwersalna kwantyfikacja / polimorfizm parametryczny . Zasadniczo pozwala to na pisanie funkcji na bardzo ogólnych rodzajach danych, z gwarancją, że jeśli działa na prostym przykładzie danych, będzie działał dla każdego możliwego wejścia.

Przynajmniej teoretycznie. Nie jest łatwo znaleźć odpowiednie typy, które są tak ogólne, że możesz to całkowicie udowodnić - zwykle potrzebujesz języka o typie zależnym , a te są raczej trudne w użyciu. Ale pisanie w funkcjonalnym stylu z samym polimorfizmem parametrycznym już wspaniale podnosi „poziom bezpieczeństwa” - niekoniecznie znajdziesz wszystkie błędy, ale będziesz musiał je całkiem dobrze ukryć, aby kompilator ich nie wykrył!

po lewej stronie
źródło
Nie zgadzam się z twoim pierwszym zdaniem. Przejście przez każdy stan programu samo w sobie nie wykrywa żadnych błędów. Nawet jeśli sprawdzasz awarie i wyraźne błędy, nadal nie sprawdziłeś w żaden sposób faktycznej funkcjonalności, więc pokryłeś tylko niewielką część przestrzeni błędów.
Mateusz
@MatthewRead: jeśli zastosujesz to konsekwentnie, wówczas „przestrzeń błędów” będzie odpowiednią podprzestrzenią przestrzeni wszystkich stanów. Oczywiście jest to hipotetyczne, ponieważ nawet „prawidłowe” stany stanowią zdecydowanie zbyt dużą przestrzeń, aby umożliwić wyczerpujące testy.
lewo około