Jak możemy być pewni, że niższe komponenty programowania komputerowego, takie jak kompilatory, asemblery, instrukcje maszynowe itp. Są bezbłędne?

57

Ponieważ coraz bardziej polegamy na komputerach, w tym na bardzo ważnych zadaniach codziennego życia, zastanawiałem się tylko, w jaki sposób testowane są te istotne elementy.

Z technicznego punktu widzenia, w jaki sposób testowane są kompilatory i asemblery? (Przypuszczam, że dotyczy to problemu zatrzymania !!)

Sudip Bhandari
źródło
36
Możesz rozpocząć badania od „Hack Kena Thompsona” Zobacz Refleksje na temat Trusting Trust
Bryan Oakley
7
Oto przykład kompilatora, dla którego istnieje dowód poprawności: compcert.inria.fr/doc/index.html
Giorgio
8
Większość kompilatorów / linkerów / asemblerów jest testowana najgłębiej, używając ich bardzo często w wielu różnych okolicznościach. Aby znaleźć błędy, nie ma nic ponad miliony użytkowników korzystających z kompilatora.
Bart van Ingen Schenau
3
i dodaj również system operacyjny do listy.
Erik Eidt,

Odpowiedzi:

104

Nie możesz być pewien, ale zakładasz, że tak, dopóki nie odkryjesz, że nie są. Przez lata pojawiło się wiele błędów w kompilatorach i sprzęcie.

Sposób, w jaki są one testowane, na przykład kompilator, polega na tym, że są one bardzo wąsko i sztywno zdefiniowane, starannie napisane, a następnie przetestowane za pomocą ogromnego zestawu testów w celu zweryfikowania poprawności. Dodaj do tego szeroką bazę użytkowników kompilatora, a więcej błędów zostanie wykrytych i zgłoszonych. Dla porównania, aplikacja do planowania spotkań u dentysty ma znacznie mniej użytkowników, a jeszcze mniej jest w stanie wykryć wady.

SQLite składa się z około 73 tys. Linii kodu, a pakiet testowy składa się z około 91378 tys. Linii kodu, ponad 1250 razy więcej niż sam SQLite. Oczekuję, że kompilatory i inne podstawowe narzędzia mają podobne proporcje. Procesory są dziś projektowane głównie z oprogramowaniem, przy użyciu języków opisu sprzętu, takich jak Verilog lub VHDL, a na nich działają również testy oprogramowania, a także specjalne styki we / wy do przeprowadzania autotestów w miejscu produkcji.

Ostatecznie jest to gra prawdopodobieństwa, a powtarzane i szeroko zakrojone testy pozwalają obniżyć prawdopodobieństwo wystąpienia defektów do akceptowalnie niskiego poziomu, tak samo jak w przypadku innego projektu oprogramowania.

Jaka jest nazwa?
źródło
7
Często zastanawiałem się nad tym samym pytaniem co OP, ale w odniesieniu do DBMS. Dałeś świetny przykład, który odpowiedział na nie w kontekście SQLite. Dziękuję Ci!
Brandon
7
+1, ale jakoś wątpię, że „kompilatory i inne podstawowe narzędzia mają podobne proporcje”.
Mehrdad
5
Zauważ, że (1) SQLite ma w rzeczywistości dwa zestawy testowe, z nietrywialną redundancją między nimi a (2) mimo to nadal występują błędy w SQLite.
Matthieu M.,
7
Odniosłem wrażenie, że SQLite jest jednym z najbardziej „szeroko testowanych” programów (pod względem linii kodu testowego / linii kodu operacyjnego) dostępnych do ogólnego użytku, a nawet bardziej niż wielu kompilatorów. Co więcej, w pełni funkcjonalny kompilator jest ogromnym oprogramowaniem i nie wyobrażam sobie, aby miał tysiąc razy więcej kodu testowego. (GCC ma podobno do 14,5 miliona linii. Wydaje się mało prawdopodobne, że albo właściwa kolekcja kompilatora ma tylko 14k LOC, lub że ma 14-miliardową testową bazę kodu siedzącą z boku! :-P)
David Z
2
@DavidZ: Jest to z pewnością jedyny projekt, jaki znam, na przykład na temat stosowania obszernych testów OOM (używają do testowania wtryskiwacza błędów i odtwarzają je raz po raz, a następnie zawodzą przy pierwszym, a następnie drugim przydziale ... aż do całego testu jest wykonywany).
Matthieu M.,
46

W kategoriach laika:

  1. Nie możesz.
  2. Kompilatory i interpretatory są testowane jednostkowo jak każde inne (profesjonalne) oprogramowanie.
  3. Pomyślny test nie oznacza, że ​​program nie zawiera błędów, oznacza jedynie, że nie wykryto żadnych błędów.
  4. Szeroka baza użytkowników korzystających z kompilatora przez długi czas jest dobrym wskaźnikiem tego, że ma bardzo niewiele błędów, ponieważ użytkownicy zwykle testują przypadki, o których projektanci nie pomyśleli.
  5. Dobrym wskaźnikiem jest również bycie otwartym oprogramowaniem. „Biorąc pod uwagę wystarczającą liczbę gałek ocznych, wszystkie błędy są płytkie ... Biorąc pod uwagę wystarczająco dużą bazę beta-testerów i współautorów, prawie każdy problem zostanie szybko scharakteryzowany, a poprawka będzie dla kogoś oczywista”. . Kompilator z zamkniętym kodem źródłowym może mieć błędy, które pojawiają się w bardzo określonych momentach lub generują mniej niż optymalny kod maszynowy, a firma stojąca za nim może po prostu nie ujawnić ich istnienia i nadać mu bardzo niski priorytet na mapie drogowej produktu.

Konkluzja:

Powiedziałbym, że idź na OOP ( O ld, O pen i P opular). Właśnie wymyśliłem ten akronim.

Tulains Córdova
źródło
19
+1 Za wymyślenie kolejnego TLA (trzyliterowego akronimu) - świat nie ma ich jeszcze dość.
s1lv3r
34
Ponadto OOP nie miał jeszcze znaczenia w programowaniu komputerowym. Więc KTT (od Ciebie do Ciebie)!
Pierre Arlaud,
15
Komentarz Pierre'a to żart @Dannnno.
yannis
19
Alternatywnie, może to P opular, O LD i O pen. ;) Tak właściwie to uszeregowałem je według ważności.
jpmc26,
23
@ jpmc26 Wybrałbym praktyczne, stare, otwarte i popularne. Co do akronimu ...
StupidOne
24

Żółwie są na dole.

Nic nie jest pewne. Nie masz innego wyboru, jak oprzeć się na ocenach zaufania.

Możesz myśleć o tym jak o stosie: matematyka> fizyka> sprzęt> oprogramowanie układowe> system operacyjny> asembler / kompilator / itp.

Na każdym poziomie masz testy, które możesz wykonać, aby poprawić swoje oceny zaufania. Niektóre z tych testów mają jakość formalnych dowodów, niektóre oparte są na obserwacji, większość jest kombinacją obu.

Najtrudniejszą częścią jest rozwikłanie rekurencji w niektórych z tych testów, ponieważ używamy programów do przeprowadzania prób i analiz obserwacyjnych, w których zbyt trudno jest to zrobić ręcznie.

Ostatecznie jednak odpowiedź brzmi: próbujesz wszystkiego, co możesz wymyślić. Analiza statyczna, fuzzowanie, symulacja, uruchamianie z celowo wybranymi wejściami ekstremalnymi lub losowymi, uruchamianie / mapowanie każdej ścieżki kontroli, formalne dowody itp. Zasadniczo Twoim celem w testowaniu powinno zawsze być robienie wszystkiego, co możliwe, aby udowodnić, że Twój produkt (np. Teoria / chip / program) nie działa zgodnie z przeznaczeniem. Jeśli podejmiesz prawdziwy wysiłek i nadal nie uda ci się, możesz poprawić swój poziom pewności co do poprawności produktu.

Testowanie jest co najwyżej procesem półdecyzji, co oznacza, że ​​biorąc pod uwagę błąd, w końcu go znajdziesz, ale nigdy nie możesz być pewien, że wszystkie je znalazłeś. Nawet w przypadku formalnie zweryfikowanego oprogramowania nadal polegasz na fizyce, narzędziach używanych do formalnych dowodów oraz że udowodniono, że to, co udowodniłeś, jest konieczne i wystarczające, aby Twój program zrobił to, co jest (często subiektywnie) „zamierzone”. Nie wspominając już o wszystkich innych używanych komponentach, które nie mają formalnych dowodów.

voutasaurus
źródło
17

To jest „niebezpieczne” pytanie dla nowych programistów, ponieważ zaczną obwiniać swoje narzędzia zamiast kodu (już tam byli, zrobili to, widziałem, że zbyt wielu to robi). Chociaż występują błędy w kompilatorach, środowiskach uruchomieniowych, systemie operacyjnym itp., Programiści powinni być realistyczni i pamiętać, że dopóki nie pojawią się dowody i testy jednostkowe wykazujące inaczej, błąd znajduje się w kodzie .

Przez ponad 25 lat programowania głównie w C, C ++ i Javie znalazłem:

  • dwa błędy z powodu błędu kompilatora (gcc i SunOS C)
  • około raz na rok lub dwa błąd związany z problemem Java JVM (zwykle związany ze zużyciem pamięci / odśmiecaniem)
  • około raz na miesiąc lub dwa błąd w bibliotece, który często jest naprawiany przez użycie najnowszej wersji lub powrót do poprzedniej wersji biblioteki

Wszystkie pozostałe błędy są bezpośrednio związane z błędem lub, częściej, z brakiem zrozumienia, jak działa biblioteka. Czasami coś, co wydaje się błędem, jest spowodowane niekompatybilnością, na przykład, jak zmieniła się struktura klasy Java, która zepsuła niektóre biblioteki AOP.

Ed Griebel
źródło
Jestem ciekawy - w jakich latach dla jakich języków? W czasach EGCS, zanim C ++ był odpowiednio ustandaryzowany, błędy kompilatora nie były tak trudne do znalezienia ...
Charles Duffy
3
Im bardziej niejasny jest kompilator, procesor lub język, tym łatwiej jest znaleźć błąd w kompilatorach (przed kimś innym), więc znalezienie 2 w GCC C jest fajne :)
Surt
1
Tak się składa, że ​​zmarnowałem około miesiąca, zakładając, że miałem problem ze skryptami gdb lub zrozumiałem, co badam. W końcu zacząłem podejrzewać, uprościłem mój testowy przypadek i znalazłem błąd w bibliotece (libkvm), który uniemożliwił debugerowi jądra dostęp do niektórych adresów ze zrzutu pamięci. Tj. YMMV - i jestem najszczęśliwszy, gdy znajduję nowy błąd w kodzie powyżej mnie, szczególnie coś, czego używam zamiast programować.
Arlie Stephens
Oczywiście nie był to błąd kompilatora ani nawet jedna z częściej używanych bibliotek. I prawdę mówiąc, nie znajduję błędów u tych, którzy mają jakąkolwiek częstotliwość.
Arlie Stephens
@ArlieStephens Jest taka lekcja: uproszczenie przypadku testowego jest czymś, co powinieneś zrobić wcześnie, gdy nie możesz znaleźć problemu. Niezależnie od tego, czy problem jest twój, czy innego kodu, pomoże ci to zawęzić. Często, jeśli problem dotyczy innego kodu, spowoduje to „dowody i testy jednostkowe wykazujące”.
jpmc26
8

Myślę, że interesującą kwestią jest to, że zdecydowana większość licencji na oprogramowanie komercyjne (a nawet oprogramowanie typu open source) wyraźnie określa, że ​​nie można ufać oprogramowaniu.

OPROGRAMOWANIE JEST DOSTARCZANE „W STANIE, W JAKIM JEST”, BEZ ŻADNEJ GWARANCJI, WYRAŹNEJ LUB DOROZUMIANEJ, W TYM, ALE NIE OGRANICZONE DO GWARANCJI PRZYDATNOŚCI HANDLOWEJ, PRZYDATNOŚCI DO OKREŚLONEGO CELU I NARUSZENIA.

Z umowy licencyjnej Microsoft Word

. Z wyjątkiem Ograniczonej gwarancji oraz w maksymalnym zakresie dozwolonym przez obowiązujące prawo, Microsoft i jej dostawcy świadczą Oprogramowanie i usługi wsparcia (jeśli istnieją) TAK JAK JEST I ZE WSZYSTKIMI WADAMI, i niniejszym zrzekają się wszelkich innych gwarancji i warunków, wyraźnych, dorozumianych lub ustawowe, w tym między innymi dorozumiane gwarancje, obowiązki lub warunki przydatności handlowej, przydatności do określonego celu, niezawodności lub dostępności, dokładności lub kompletności odpowiedzi, wyników, wysiłku pracowników, brak wirusów i brak zaniedbania, wszystko w odniesieniu do Oprogramowania oraz świadczenie lub brak wsparcia lub innych usług, informacji, oprogramowania i powiązanych treści za pośrednictwem Oprogramowania lub w inny sposób wynikające z korzystania z Oprogramowania .

Zasadniczo to zdanie w licencji w prawie każdym oprogramowaniu, z którego korzystasz, mówi ci konkretnie, że nie możesz ufać oprogramowaniu, nie mówiąc już o używanym kompilatorze.

Oprogramowanie jest jak teoria naukowa, uważa się, że działa tak, jak określono, dopóki nie zadziała.

Toby Allen
źródło
+1 za wskazanie, że same licencje stwierdzają, że żadne oprogramowanie nie jest idealne.
Tulains Córdova
3
Z przyjemnością odnotowałem odstępstwo od tej praktyki w ViaVoice dla komputerów Mac. Zamiast zwyczajowego „jeśli to nie działa, szkoda”, w rzeczywistości powiedzieli coś w rodzaju „Oprogramowanie ma gwarancję działania zgodnie z opisem”.
WGroleau,
1
Prostym tłumaczeniem tego fragmentu wyrażenia gwarancyjnego jest: „To może być oprogramowanie lub sh * t. Może działać. Może nie. Nawet jeśli działa, może nie rób, co chcesz. A tak na marginesie, moglibyśmy skradzić to komuś innemu. Szkoda. Mamy twoje pieniądze i wykorzystaliśmy je na zatrudnienie wielu prawników. GRA! -nyah-nyah-nyaaah-naah! ”. :-)
Bob Jarvis,
2
@ BobJarvis: Moim ulubionym oświadczeniem gwarancyjnym, stosowanym w niektórych programach typu open source (takich jak nmap IIRC), jest „Jeśli się zepsuje, zachowasz oba elementy”.
Peter Cordes
To stwierdzenie jest wszechobecne w oprogramowaniu open source i wielu darmowych programach zamkniętych. Nie pojawia się w większości komercyjnych licencji na płatne oprogramowanie.
jwg
2

Jako autor kompilatorów języka matematycznego * z mojego doświadczenia mogę powiedzieć, że teoretycznie nie możesz. A niektóre błędy dają po prostu błędne wyniki, takie jak (z mojej listy wstydów) obliczanie 6/3*2od prawej 6/(3*2)i wyprowadzanie 1 bez awarii lub bezsensownych błędów kompilacji.

Ale wiele kompilatorów IMHO nie ma tylu błędów, co inne oprogramowanie, ponieważ:

  • Pisanie testów jednostkowych jest łatwe. Każda instrukcja jest jednostką i możesz pisać testy tak proste jak:test_unit("2+(-2)*(-2+1)*3+1",9);
  • Program jest kombinacją instrukcji i dla każdego programu, aby uzyskać poprawny wynik, każda pojedyncza instrukcja musi dawać poprawny wynik (głównie). Tak więc jest bardzo mało prawdopodobne, aby mieć jakieś błędy, podczas gdy program daje poprawny wynik.
  • Wraz ze wzrostem wielkości i liczby napisanych programów dramatycznie wzrasta prawdopodobieństwo wyłapania błędów.

W przypadku asemblerów, instrukcji maszynowych itp. Powyższe mają również zastosowanie; z drugiej strony weryfikacja i walidacja w zakresie projektowania i produkcji układów mają znacznie bardziej rygorystyczne procesy, ponieważ jest to ogromny biznes: elektroniczna automatyzacja projektowania .

Przed przejściem do produkcji każdy procesor powinien zostać poddany rygorystycznym testom, ponieważ każdy błąd kosztuje prawie kilka milionów dolarów: w produkcji chipów występują ogromne jednorazowe koszty produkcji. Dlatego firmy wydają dużo pieniędzy i piszą dużo kodu symulacyjnego do swojego projektu przed rozpoczęciem produkcji, chociaż nie daje to 100% gwarancji - na przykład: błąd Pentium FDIV.

Krótko mówiąc, jest bardzo mało prawdopodobne, aby miały poważne błędy w kompilatorach, kodach maszynowych itp.

Mój skromny język matematyki *

Gorkem
źródło
Intel testuje piekło swoich procesorów, uruchamiając sekwencje losowych instrukcji i porównując je z modelem oprogramowania, między innymi: tweakers.net/reviews/740/4/… . Z tego powodu często publikowane są naprawdę niejasne erraty dla niektórych naprawdę nieprawdopodobnych kombinacji instrukcji w nietypowym trybie.
Peter Cordes
0

Bez skazy? Oni nie są. Niedawno zainstalowałem kilka „aktualizacji” i minęły miesiące (i kilka przeprogramowanych sekcji kodu) później, zanim moja strona ASP.NET znów działała poprawnie, z powodu niewyjaśnionych zmian w działaniu różnych podstawowych rzeczy.

Są one jednak testowane, a następnie wykorzystywane przez wiele bardzo inteligentnych, zorientowanych na szczegóły osób, które zwykle zauważają, zgłaszają i naprawiają większość rzeczy. Stack Exchange to świetny przykład (i ulepszenie), w jaki sposób wszyscy ludzie używający tych narzędzi pomagają testować i analizować, jak działają te niezwykle złożone i niskiego poziomu narzędzia, przynajmniej w zakresie praktycznego zastosowania.

Ale bezbłędnie, nie. Chociaż można również zobaczyć, jak ludzie na Stack Exchange zyskują imponujący wgląd w szczegóły wydajności i zgodność z normami oraz dziwactwa, zawsze występują wady i niedoskonałości, szczególnie gdy różni ludzie mają różne opinie na temat tego, co to wada.

Dronz
źródło
-1

Aby pokazać, że systemy bazowe są bezbłędne

a) Potrzeba udowodnienia, że ​​są bezbłędne

  1. Dowód matematyczny
  2. Realistycznie możliwe tylko w przypadku trywialnych programów

b) Wykonaj wyczerpujący test

  1. Możliwe tylko dla trywialnych programów i niektórych prostych programów
  2. Gdy tylko element pomiaru czasu przejdzie do testu, nie jest możliwe wykonanie wyczerpującego testu, ponieważ czas można podzielić na czas nieokreślony.
  3. Poza trywialnymi programami, możliwe opcje eksplodują wykładniczo.

W testowaniu oprogramowania wyczerpujący test jest wykorzystywany tylko do testowania jednostkowego niektórych prostych funkcji.

Przykład: Chcesz przetestować 8-znakowe wejście utf-8 w jakimś polu, dokonujesz wyboru, aby wyciąć wejście 8-krotną maksymalną długością 6 utf-8 w bajtach, co daje 8 * 6 = 48 bajtów skończone możliwości.

Można teraz pomyśleć, że wystarczy przetestować tylko 1112 064 poprawnych punktów kodowych każdego z 8 znaków, tj. 1112,064 ^ 8 (powiedzmy 10 ^ 48) testów (co jest już mało prawdopodobne), ale tak naprawdę trzeba przetestować każdą wartość każdego z 48 bajtów lub 256 ^ 48, która wynosi około 10 ^ 120, co jest takiej samej złożoności jak szachy w porównaniu do całkowitej liczby atomów we wszechświecie około 10 ^ 80.

Zamiast tego możesz używać, w kolejności rosnącej wysiłku, a każdy test powinien obejmować wszystkie poprzednie:

a) przetestuj dobrą i złą próbkę.

b) pokrycie kodu, tj. spróbuj przetestować każdy wiersz kodu, który jest względnie prosty dla większości kodów. Teraz możesz się zastanawiać, jaki jest ostatni 1% kodu, którego nie możesz przetestować ... błędy, martwy kod, wyjątki sprzętowe itp.

c) zasięg ścieżki, testowane są wszystkie wyniki wszystkich gałęzi we wszystkich kombinacjach. Teraz już wiesz, dlaczego dział testowy nienawidzi cię, gdy twoje funkcje zawierają więcej niż 10 warunków. Zastanawiasz się także, dlaczego ostatnich 1% nie można przetestować ... niektóre oddziały są zależne od poprzednich.

d) test danych, przetestuj liczbę próbek z wartością graniczną, typowymi problematycznymi wartościami i liczbami magicznymi, zero, -1, 1, min +/- 1, max +/- 1, 42, wartości rnd. Jeśli to nie da ci zasięgu, wiesz, że nie złapałeś wszystkich wartości w swojej analizie.

Jeśli już to zrobisz, powinieneś być gotowy do egzaminu podstawowego ISTQB.

Surt
źródło