Testování stavového automatu

Cílem úlohy je vyzkoušet si otestování stavového automatu uvnitř (téměř) reálné aplikace.

Vaše semestrální práce se bude zabývat jedním z následujících automatů ve webové aplikaci (viz níže):

1. Články redakčního systému (stavy: draft, submitted, waiting, published, rejected)
2. Bug v bug trackeru (stavy: new, assigned, resolved, reopened, closed), bugzilla
3. Objednávka v e-shopu (stavy: new, preparing, partial, prepared, dispatched, delivered, canceled)
4. Zboží v e-shopu (stavy: preorder, available, out_of_stock, on_the_way, not_available)
5. Uživatel (stavy: new, confirmed, code_sent, verified, banned)
6. Online aukce (stavy: draft, waiting, bidding, canceled, successful, failed)
7. Objednávka taxi (stavy: new, accepted, waiting, on_route, completed, canceled)
8. VPS (stavy: initiating, offline, starting, stopping, online)
9. Proces pod správou supervisord (stavy: stopped, stopping, starting, running, backoff, fatal, exited)

Poznámky:

• Stavový diagram na odkazované stránce lze získat v podobě kódu pro Graphviz nebo v PDF změnou “png” za “dot” či “pdf” na konci URL obrázku.
• Počáteční stav reprezentovaný černým puntíkem a koncový reprezentovaný černým puntíkem v kroužku jsou jeden a tentýž stav ve kterém entita neexistuje, z pohledu automatu je to obyčejný počáteční stav. Z pohledu programátora šipky vedoucí z tohoto stavu jsou volání kontruktoru a ty vedoucí do něj jsou volání destruktoru (je to mírně nepřesné přirovnání, pro pochopení pointy stačí).

Navrhněte testovací sadu pro konečný automat z aplikace (viz výše; u aplikace za výstupní symboly považujte název přechodu plus název cílového stavu přechodu) a z umělých automatů (dle čísla vaší skupiny; zadání, ZIP s CSV a diagramy, řešení úloh 40 až 50).

Testy musí zajistit, že případné skryté stavy ve vzdálenosti jednoho kroku budou odhaleny (k=1). Samozřejmě, navrhněte i příslušnou charakterizační množinu. Nedosažitelné části automatu identifikujte jako chybu. Jestliže přechod z nějakého stavu není pro danou událost určen, zůstává automat ve stejném stavu a na výstup pošle předdefinovaný výstupní symbol (default output).

Zpráva řešení bude obsahovat:

1. Kopii zadání úlohy
2. 2x Graf konečného automatu.
3. 2x Tabulku testů pokrytí stavů (+ algoritmus).
4. 2x Tabulku testů pokrytí hran (+ algoritmus).
5. 2x Výpočet charakterizační množiny W (+ algoritmus).
6. 2x Tabulku testů pokrývající skryté stavy do jednoho kroku (+ algoritmus).
7. Případné poznámky zdůvodnění nestandardních kroků.

Řešení úlohy bude provedeno pomocí vámi napsaného algoritmu (v libovolném programovacím jazyce). Smíte používat libovolné knihovny pro obsluhu vstupu, výstupu i reprezentace grafu, samotný algoritmus však musí být napsán vámi. Relevantní část zdrojového kódu vašeho programu vložíte do zprávy (jako přílohu na konec; doporučuji relevantní zdrojový kód vyčlenit do samostatného souboru a ten vložit celý), ve zprávě se pak na přílohu a odpovídající funkci/metodu odkážete.

Váš program spustíte na dva vstupy (zpráva tedy bude mít dvě velmi podobné části). Prvním je umělý automat (viz 1. odstavec), druhým je automat získaný z aplikace pro vaši semestrální úlohu.

Doporučujeme zprávu generovat vaším programem. Proto můžete odevzdávat zprávu i v HTML. Nebo můžete použít libovolný jiný formát, například LuaTeX či Markdown, a exportovat výsledek do PDF (viz Pandoc).

1. Z aplikace získejte definici stavového automatu (jednu entitu dle vašeho téma) a importujte ji do Uppallu.
2. Vymodelujte v Uppallu další entity, například uživatele, tak aby byly použity alespoň dvoje hodiny.
3. Simulujte chování systému a dokažte nějaké zajímavé vlastnosti.

Zadání - 1. varianta: Vytvořte generátor testů pro Selenium. Vstupem je aplikace pro semestrální úlohu (přesněji stavový automat z ní získaný). Výstupem je vygenerovaný test, který po spuštění v Seleniu aplikaci prokliká a projde tak pokud možno všechny stavy i hrany automatu. Důraz je kladen hlavně na integraci Selenia, vazby mezi odkazy a přechody automatu.

Zadání - 2. varianta: Vytvořte generátor testů, podobný 1. variantě zadání, avšak bez interakce se Seleniem. Testy budou přímo vyvolávat přechody automatu, tak aby pokryl stavy i přechody. Důraz je kladen na generování testovacích dat (vhodné hodnoty parametrů přechodů, výchozí stav databáze, obnovení databáze pro další běh, atd.) a sestavení vhodných posloupností přechodů (pokrytí grafu). Splnění úlohy může spočívat například v návrhu vhodného DSL (realizovaný nejlépe v JSON) pro reprezentaci generovaných testů a vytvoření interpretu, který testy provede. Komplikací je zde nedeterminističnost automatu, kdy testující program neví, do jakého z možných stavů nedeterministický přechod povede. Testující program tedy musí reagovat na skutečné chování automatu.

Zadání - n. varianta: Jak jinak by se takovéto automaty daly testovat? Jaké nástroje k tomu existují? Jak je lze použít?

Poznámky ke všem variantám:

• Cílem úlohy je prozkoumat situaci a vyzkoušet možná řešení. Neúspěšné postupy jsou také užitečné a ve zprávě je uveďte.
• Algoritmy můžete zkoušet na automatech pro semestrální práci nebo na libovolných vámi připravených automatech.
• Zpráva by měla být dostatečně podrobným návodem, aby bylo možné váš postup reprodukovat, doladit, rozšířit a použít k testování reálné aplikace. V případě neúspěšných pokusů by mělo být jasné, proč je takový postup nevhodný a s čím byly problémy.
• Výsledný generátor nemusí být dokonalý produkt nasaditelný v produkčním prostředí. Stačí prototyp ukazující realizovatelnost zvoleného postupu. Čitelný a okomentovaný kód je důležitější než množství funkcí.
• Za splnění úlohy je považováno i to, když naleznete jen neúspěšné postupy nebo zjistíte, že to nijak rozumně nejde. Podstatné je taková zjištění popsat a zdůvodnit. (Věříme, že by tato bonusová úloha měla nějak jít řešit, ale nezkoušeli jsme to.)
• Namísto Selenia je možné použít i libovolný jiný open-source nástroj, pokud si myslíte, že by byl k tomuto účelu vhodnější.

Jako základ pro export automatu z aplikace můžete použít následující PHP skript:

<?php
list($context, $core_cfg) = require './core/init.php';  // inicializace frameworku
$machine = $context->smalldb->getMachine('article');    // získání instance automatu
$states = $machine->describeAllMachineStates();         // popis stavů automatu
$actions = $machine->describeAllMachineActions();       // popis přechodů automatu
var_dump($states);
var_dump($actions);

Poznámka: Implementace automatu rozlišuje mezi “akcí” a “přechodem”. Akce je skupina stejnojmených přechodů v automatu, která může sdílet část konfigurace. Samotné přechody automatu jsou pod klíčem “transitions” v konfiguraci akce, kde klíčem je výchozí stav a v “targets” jsou možné cílové stavy přechodu. “Akci” lze tedy chápat jako vstupní symbol. Podrobnější popis naleznete v plugin/smalldb/class/StateMachine/AbstractMachine.php.

• Aplikace: http://cascade-examples.frozen-doe.net/
• Zdrojové kódy: http://cascade-examples.frozen-doe.net/src.zip

Dokumentaci i demo frameworku, na kterém je aplikace postavena, najdete na cascade.frozen-doe.net a smalldb.org (aplikace stojí na postarší verzi knihoven, to podstatné se však nijak výrazně neměnilo; pro bonusovou úlohu doporučuji použít aktuální verzi).