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.

{ zpětná vazba }

Tweet		Delicious
Sdílet

Hodnocení (1): 4

Přečtěte si také

Latinské čtverce

Ortogonální pole

Diskuse

Článek zatím nemá žádné komentáře.