Testování konečného automatu
Konečný automat
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ů L, 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ů T. Tuto sestavíme jako T = L \\cdot Input, kde \\cdot je operace zřetězení. Množina T 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 k pomocí charakterizační množiny W, 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 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.







Doporučujeme

Internet pro vaši firmu na míru