Testování konečného automatu

Konečný automat

Konečný automat (finite state machine) je model výpočtu, který se skládá z konečného množství stavů a přechodů mezi nimi. Automat přechází mezi stavy na základě symbolů čtených ze vstupu, případně při přechodu nějakým způsobem reaguje. Kromě údaje o aktuálním stavu neobsahuje automat žádnou další paměť.

Pomocí konečného automatu můžeme namodelovat chování hardware a aplikací (zejména pak uživatelského rozhraní řízeného pomocí menu).

Testování

Uvažme automat na obrázku se vstupními symboly $Input = \\{e71, e94\\}$ . Nejprve zkonstruujeme množinu pokrytí stavů , která obsahuje všechny posloupnosti vstupů takové, že se s jejich pomocí z počátečního stavu do libovolného uzlu ( $\\varepsilon$ je prázdný vstup).

$L = \\{\\varepsilon,\\; e::71,\\; e71::e71,\\; e71::e94\\}$

Druhou množinou, kterou zkonstruujeme, je množina pokrytí přechodů . Tuto sestavíme jako $T = L \\cdot Input$ , kde $\\cdot$ je operace zřetězení. Množina proto pokrývá veškeré přechody (vstupy), které mohou v aplikaci (automatu) nastat. Může proto detekovat chyby způsobené špatným přechodem (tzn. reagujícím na špatný vstup), případně stavy, které nejsou do modelu zaneseny.

$T = \\{{\\small \\varepsilon,\\; e71,\\;e94,\\;e71::e71,\\;e71::e94,\\;e71::e71::e71,\\;e71::e71::e94,\\;e71::e94::e71,\\; e71::e94::e94}\\}$

Skryté stavy

Posledním a nejhůře odhalitelným typem chyby jsou skryté stavy. Skryté stavy se navenek prezentují jako stavy, které máme v modelu, ale vnitřně v nich existuje určitý rozdíl, který se projeví až po nějaké době (až po mnoha přechodech na tento skrytý stav) – například přetečením celočíselné proměnné, která by byla v případě korektního stavu vždy resetována.

Skryté stavy je velmi obtížné odhalit, protože k chybě může skutečně dojít například až po přetečení proměnné typu integer (typicky hodnoty 2 147 483 647) a do té doby se stav může chovat zcela korektně. Kdybychom měli automat testovat až do této hloubky, tak by byl test neproveditelný.

Z tohoto důvodu se testuje do omezené hloubky pomocí charakterizační množiny , která značí vstupy, pomocí nichž jsme schopni odlišit libovolné dva stavy.

$Z = Input^{k} \\cdot W \\cup Input^{k-1} \\cdot W \\cup \\cdots \\cup Input^{1} \\cdot W \\cup W$

V našem případě budeme uvažovat, že všechny stavy rozeznáme okamžitým pohledem na aplikaci, tj. $W = \\{\\varepsilon\\}$ a budeme hledat pouze následující skryté stavy. Z toho plyne, že množinu

získáme jako $Z = Input \\cdot W \\cup W = \\{e71,\\; e94,\\; \\varepsilon\\}$ .

Konečná sada testů

Konečnou sadu testů, která prověří všechny stavy, přechody a přechody do neznáma získáme jako $T \\cdot Z$ .

Pro automat z příkladu proto vygenerujeme následující sadu testů:

${\\small T \\cdot Z = \\{ \\varepsilon,\\; e71,\\; e94,\\; e71::e71,\\; e71::e71::e71,\\; e71::e71::e71::e71,\\; e71::e71::e71::e94,\\; }$ ${ \\small e71::e71::e94,\\; e71::e71::e94::e71,\\; e71::e71::e94::e94,\\; e71::e94, \\; e71::e94::e71, }$ ${ \\small e71::e94::e71::e71,\\; e71::e94::e71::e94,\\; e71::e94::e94, \\; e71::e94::e94::e71, }$ ${ \\small e71::e94::e94::e94, \\; e94::e71, \\; e94::e94 \\} }$

Literatura

MAŘÍK, Radek. Testování a verifikace softwaru, Testovan konecnych automatu - slides k přednášce.
HOLCOMBE, Mike; IPATE, Florentin. Correct Systems : Building a business process solution [online]. A volume in the Applied Computing Series. [s.l.] : Springer-Verlag, 1998 [cit. 2010-12-29]. Dostupné z WWW: <http://www.dcs.shef.ac.uk/~wmlh/bookwebversion.html>. ISBN 3-540-76246-9.

Testování

Skryté stavy

Konečná sada testů

Literatura

Doporučujeme