Jakie są najlepsze praktyki testowania programów z zachowaniem stochastycznym?

14

Podczas prac badawczo-rozwojowych często piszę programy, których zachowanie jest w pewnym stopniu losowe. Na przykład, kiedy pracuję w programowaniu genetycznym, często piszę programy, które generują i wykonują dowolny losowy kod źródłowy.

Problem z testowaniem takiego kodu polega na tym, że błędy są często przerywane i mogą być bardzo trudne do odtworzenia. Wykracza to poza zwykłe ustawienie losowego ziarna na tę samą wartość i rozpoczęcie wykonywania od nowa.

Na przykład kod może odczytać wiadomość z bufora pierścienia jądra, a następnie wykonać warunkowe skoki na zawartość wiadomości. Oczywiście stan bufora pierścieniowego zmieni się, gdy później spróbujemy odtworzyć problem.

Chociaż takie zachowanie jest cechą , może wyzwalać inny kod w nieoczekiwany sposób, a zatem często ujawnia błędy, których nie znajdują testy jednostkowe (lub testery ludzkie).

Czy istnieją sprawdzone metody testowania tego rodzaju systemów? Jeśli tak, niektóre odniesienia byłyby bardzo pomocne. Jeśli nie, wszelkie inne sugestie są mile widziane!

John Doucette
źródło
5
Nie możesz też wyśmiewać bufora pierścieniowego jądra? I inne losowe aspekty twojego kodu?
Jonathan Merlet
1
@JathanathanMerlet Potencjalnie problem polega na tym, że po wdrożeniu kod będzie miał dostęp do rzeczywistego bufora pierścieniowego (w rzeczywistości do prawdziwego systemu operacyjnego). Jeśli więc przetestuję tylko wersję próbną, odkładam odkrycie tych błędów na później.
John Doucette
Wydaje mi się, że problem nie jest związany z losowym zachowaniem programu (ponieważ może to być kontrolowane przez losowe ziarno), ale z konkretnymi stanami tego „bufora pierścieniowego jądra”. Więc twoje pytanie brzmi „jak przetestować program, który zależy od stanu zewnętrznego”, prawda?
AakashM,
@AakashM, tak, to lepszy sposób na wyrażenie tego. Mówiąc ściślej, program ze stanem zewnętrznym, który stochastycznie uzyskuje dostęp lub zmienia stan zewnętrzny.
John Doucette,

Odpowiedzi:

7

Przydaje się dodawanie haków, jak sugerowano, w celu odtworzenia dokładnych stanów. Instrumentuj również system, aby mógł zrzucić swoje „nasiona” (w twoim przypadku, w tym nasiona PRNG, a także bufor pierścieniowy jądra i wszelkie inne źródła niedeterministycznego wkładu).

Następnie uruchom testy zarówno z prawdziwym losowym wprowadzaniem danych, jak i w stylu regresji ze wszystkimi wcześniej odkrytymi interesującymi przypadkami.

W szczególnym przypadku twojego dostępu do jądra, w każdym przypadku polecam zrobić próbę. Użyj makiety, aby wymusić klasy równoważności, które rzadziej pojawią się w praktyce, w duchu „pusty” i „pełny” dla kontenerów lub „0, 1, 2 ^ n, 2 ^ n + 1, wiele” dla policzalne rzeczy. Następnie możesz przetestować próbę i rzeczywistość, wiedząc, że poradziłeś sobie i przetestowałeś przypadki, o których wcześniej myślałeś.

Zasadniczo to, co sugeruję, stanowi połączenie deterministycznych i niedeterministycznych danych wejściowych, przy czym te deterministyczne są mieszanką tych, o których możesz pomyśleć i tych, które Cię zaskoczyły.

Stephan A. Terre
źródło
6

Jedną rozsądną rzeczą jest zaszczepienie generatora liczb losowych stałą wartością dla testów, aby uzyskać deterministyczne zachowanie.

Dima
źródło
1
to; lub całkowicie wykpić prng
jk.
1
Dzieki za sugestie! Robię to już dla testów jednostkowych, ale nie mogę ręcznie przetestować wszystkich możliwych programów.
John Doucette
2
ale to oznacza, że ​​nie można sprawdzić, czy losowość działa poprawnie.
Louis Rhys,
2

Myślę, że testy statystyczne to jedyny sposób. Podobnie jak liczby losowe są „testowane” pod kątem losowości za pomocą testów statystycznych, więc muszą istnieć algorytmy wykorzystujące losowe zachowanie.

Po prostu uruchom algorytm wiele razy z tym samym lub innym wejściem i porównaj go ze sobą. Problem z tym podejściem polega na ogromnym wydłużeniu czasu obliczeniowego wymaganego do zakończenia testów.

Euforyk
źródło
Niekoniecznie, ponieważ możesz wybrać niewielki zestaw „obejmujących” danych wejściowych i uruchamiać na nich wiele razy - liczba danych wejściowych wymaganych do ustalenia niezawodności może być mniejsza. Ten zestaw „obejmujący” powinien zawierać każdą gałąź kodu, inicjować wszystkie obiekty itp.
Daniel Moskovich,
2

Nie jestem specjalistą w tej dziedzinie, ale istnieje literatura naukowa związana z testowaniem programów stochastycznych.

Jeśli nie możesz łatwo stworzyć klas testowych, możesz użyć testu statystycznego, jak powiedział #Euphoric. Borning i in. porównaj podejście tradycyjne i statystyczne. Uogólnieniem testów statystycznych zaproponowanym przez @Euphoric może być ten omówiony przez Whittakera. Zasugerował, aby stworzyć stochastyczny model pożądanego (stochastycznego, w twoim przypadku) zachowania, a następnie wygenerować konkretne przypadki testowe z tego modelu (patrz jego dedykowany artykuł ).

mgoeminne
źródło
Dzięki! Wygląda bardzo pomocnie. Dla osób spoza instytucji akademickich wersję dokumentu z nadrukiem można pobrać z autorskiego repozytorium kodu Google tutaj: team4model.googlecode.com/svn/trunk/resources/paper/…
John Doucette