De reținut
- O relație metamorfică (MR) descrie cum ar trebui să se schimbe rezultatul când datele de intrare se schimbă într-un mod cunoscut. De exemplu, adăugarea unui filtru la o căutare poate doar micșora rezultatele.
- Testarea metamorfică rulează o dată de intrare sursă, o transformă într-o dată de intrare derivată și verifică dacă cele două rezultate respectă relația. Nu e nevoie de o valoare așteptată.
- E deosebit de valoroasă acolo unde răspunsurile exacte nu pot fi cunoscute: software științific, compilatoare, căutare și ordonare, simulări, modele ML. Arta stă în găsirea unor relații puternice, pe care defectele reale le-ar încălca.
De unde pornim
Ai văzut problema oracolului: pentru multe programe nu poți spune care e rezultatul corect. Testarea metamorfică e unul dintre cele mai practice răspunsuri. A fost introdusă de T.Y. Chen, S.C. Cheung și S.M. Yiu într-un raport tehnic din 1998 și a devenit de atunci o tehnică importantă, atât în cercetare, cât și în industrie.
Ideea, într-un exemplu
Nu poți verifica ușor că sin(1.234) întoarce exact valoarea corectă. Dar știi că sin(x) = sin(π − x). Așa că:
- Testul sursă: calculezi
a = sin(1.234). - Testul derivat: calculezi
b = sin(π − 1.234). - Verifici relația:
a ≈ b, în limita toleranței de virgulă mobilă.
Dacă relația e încălcată, cel puțin unul dintre rezultate e greșit, deși n-ai știut niciodată valoarea corectă a vreunuia.
Relații în practică
| Sistem | Relație metamorfică |
|---|---|
| Motor de căutare | Adăugarea unui termen ȘI în plus întoarce o submulțime a rezultatelor inițiale |
| Filtru de e-commerce | Rezultatele pentru „preț < 100” le conțin pe toate cele pentru „preț < 50” |
| Sortare / ordonare | Amestecarea ordinii datelor de intrare nu schimbă rezultatul sortat |
| Drumul cel mai scurt | Cel mai scurt traseu A→B nu e mai lung decât A→C plus C→B |
| Statistică | Înmulțirea tuturor valorilor cu k înmulțește media cu k; adunarea unei constante nu schimbă varianța |
| Clasificator de imagini | O mică schimbare de luminozitate n-ar trebui să schimbe eticheta prezisă |
| Compilator | Eliminarea codului care nu se execută niciodată pentru o anumită dată de intrare nu schimbă rezultatul programului pentru acea dată de intrare |
| Simulare | Dublarea pasului de timp, în limite stabile, dă aproximativ aceeași stare finală |
Relațiile pot fi egalități (același rezultat), incluziuni (submulțime sau supramulțime), inegalități (nu mai mare decât) sau aproximative (în limita unei toleranțe).
Cum găsești relații bune
Relațiile metamorfice bune sunt:
- Ancorate în domeniu: vin din matematică, fizică, reguli de business sau așteptările utilizatorilor, nu din implementare.
- Puternice: un defect tipic le încalcă. „Rezultatul nu e null” e o relație, dar una slabă.
- Diverse: mai multe relații diferite exersează părți diferite ale logicii.
O metodă utilă: enumeră transformările datelor de intrare la care sistemul ar trebui să fie insensibil (reordonare, scalare, adăugiri irelevante, rescrieri echivalente) sau sensibil într-un mod previzibil (filtre mai stricte, date mai mari). Fiecare sugerează o relație.
Automatizarea
Testarea metamorfică se combină natural cu datele de intrare generate:
@given(st.lists(strategie_produse(), min_size=1))
def test_filtrul_mai_strict_intoarce_o_submultime(produse):
magazin = incarca(produse)
larg = set(cauta(magazin, pret_maxim=100))
ingust = set(cauta(magazin, pret_maxim=50))
assert ingust <= larg # relație metamorfică: submulțime
Fiecare dată de intrare sursă generată produce automat una derivată, așa că poți rula mii de verificări fără nicio valoare așteptată scrisă manual.
Testarea unui compilator e problema oracolului în forma ei cea mai grea: pentru un program aleator, care e codul mașină „corect”?
Vu Le, Mehrdad Afshari și Zhendong Su au introdus Equivalence Modulo Inputs (EMI). Rulezi un program cu o anumită dată de intrare și înregistrezi ce cod nu se execută niciodată. Apoi creezi variante ștergând o parte din acel cod mort. Pentru acea dată de intrare, fiecare variantă trebuie să dea același rezultat ca originalul. Dacă o variantă compilată dă un rezultat diferit, compilatorul greșește.
În articolul lor de la PLDI 2014, au raportat 147 de bug-uri confirmate, unice în GCC și LLVM, găsite în unsprezece luni, cele mai multe fiind compilări greșite, cel mai greu de observat tip de bug de compilator. Multe au fost reparate de dezvoltatorii compilatoarelor.
Lecția: o singură relație metamorfică puternică, aplicată automat pe multe programe, a găsit bug-uri în două dintre cele mai intens testate programe din lume.
Limitări
- Relațiile sunt oracole parțiale. Un program poate respecta toate relațiile alese și totuși să fie greșit, de exemplu dacă greșește constant într-un fel pe care relațiile nu-l constrâng.
- Unele relații au nevoie de toleranțe, mai ales în virgulă mobilă și în ML. Prea strânse produc alarme false; prea largi ascund bug-uri.
- Depanarea e indirectă. O încălcare spune că una dintre cele două rulări e greșită, nu care.
Atenuezi aceste limite combinând relații, folosind mai multe teste derivate pentru fiecare sursă și împerechind testele metamorfice cu alte oracole.
Așa da
Să deduci relațiile din cunoașterea domeniului, împreună cu experții: „În modelul nostru de risc, creșterea expunerii nu poate niciodată să scadă cerința de capital.”
Așa nu
Să te bazezi pe o singură relație slabă, de exemplu „rezultatul are aceeași lungime”. Va trece pentru majoritatea bug-urilor reale și va da o încredere falsă.
Verifică-te
Testezi un API de căutare de produse care ordonează rezultatele după relevanță. Propune două relații metamorfice.
Arată răspunsul
De exemplu: (1) adăugarea unui filtru (categorie, preț maxim) întoarce o submulțime a rezultatelor nefiltrate; (2) schimbarea literelor mari și mici din căutare sau adăugarea unor spații în plus întoarce aceleași rezultate, în aceeași ordine. Altele: adăugarea unui produs care nu se potrivește cu căutarea nu schimbă rezultatele; cererea paginii 2, cu 10 rezultate pe pagină, e egală cu elementele 11–20 dintr-o singură pagină de 20.
