Příklad použití klasifikačního stromu ve spolehlivosti software – metoda plovoucích mezí Jan A. Strouhal
Abstrakt: Příspěvek se zabývá příkladem konstrukce klasifikačního stromu pro použití ve spolehlivosti software. V první části je popsána základní konstrukce, která počítá s expertním počtem i hodnotami hranic metrik, v další části je popsán příklad vylepšení této základní konstrukce vyhledáním optimálních hranic metrik pomocí programu.
Klasifikační stromy Vezmeme-li části programu (moduly), které máme již otestované, můžeme z jejich vlastností (metrik) zkonstruovat klasifikační strom, kterým pak můžeme klasifikovat netestované části programu, u kterých chceme zjistit, zda je máme či nemusíme testovat. Tento zkonstruovaný strom nám může pomoci zkrátit dobu testování nebo dokonce zvýšit spolehlivost, protože se při testování zaměříme více na části, které jsou skutečně potřeba otestovat a odladit. Postup byl řešen na konferenci ROBUST 2006. Funkce výběru metrik:
F ( pi ; ni ) = −
pi pi ni ni log 2 log 2 − , pi + ni pi + ni pi + ni pi + ni
kde p je počet pozitivních modulů (+ třída), a n je počet negativních modulů v i-tém uzlu. Čím je F menší, tím větší je homogenita v uzlu. Metriku, pro níž je E (C , A) =
v
∑ [w * F ( p , n )] , i
i =1
použijeme jako kořen.
i
i
kde wi =
pi + ni C
Popis vstupních údajů Dále popsané vstupní údaje jsou z vyvýjeného programu CSC Atlas pro správu domů, kde jednotlivé moduly jsou ucelenými částmi tohoto programu tj. objednávky, faktury, domy, jednotky, nájemci, evidence plateb, atd. Data o těchto modulech byla sbírána v průběhu roku 2005, nově klasifikované moduly taktéž. Základní konstrukce – pevné meze Vstupní údaje U závislé proměnné (metrika: počet chyb) budeme předpokládat, že při počtu chyb větším než 120 je modul náchylný k chybám a tudíž jej budeme řadit do + třídy Modul C D G Metrika A B E F H I J K 125 130 80 Počet chyb 30 20 105 140 12 32 25 14 + + + Třída Nezávislé proměnné (metriky: funkce, propojení dat, počet revizí) Metrika Funkce Propojení dat Počet revizí
A R 90 0
B R 20 7
C F 200 6
D R 150 4
E P 110 3
Modul F G F P 50 0 10 11
H P 170 2
I P 82 5
J P 190 9
K R 70 2
Kódování Vezmeme nezávislé proměnné (metriky: funkce, propojení dat, počet revizí) a pomocí kódování rozdělíme do tří skupin α , β , γ γ Metrika α β Funkce
α =Práce se
soubory (F)
Propojení dat α = 0 ≤ x ≤ 79 Počet revizí α =0≤ x≤3
β =Uživatelské
rozhraní (R)
β = 80 ≤ x ≤ 149 β =4≤ x≤8
γ =Řízení
procesu (P)
γ = x ≥ 150 γ = x≥9
můžeme pak psát Modul A B
Metrika Funkce
β Propojení dat β Počet revizí α
β α β
Třída
-
-
C
D
β +
α γ
E
F
G
H
I
J
K
β
γ β α
+
-
-
+
-
-
-
-
β γ
α α γ
γ α γ
γ γ α
γ β β
γ γ γ
β α α
Příklad výpočtu pro základní kořen – uvažována Metrika „Funkce“ Pomocí metriky „Funkce“ rozdělíme (tučně zvýrazněny pozitivní α - C,F; β - A,B,D,K; γ - E,G,H,I,J třídy): P n Celkem váha F(p,n) Váha*F(p,n) Větev 1 1 1 11 0,182 0,000 0,000 Větev 2 1 3 11 0,364 0,811 0,295 Větev 3 1 4 11 0,455 0,722 0,328 Součet 0,623
Počet revizí
.α (≤3)
.γ (≥9)
β (4÷8)
A, E, H, K (M,R)
Funkce B, C, D, I (N,P,Q,S,T) .α (F)
– .α (≤79) B (N)
Propojení dat
.γ (R)
G
J
+
–
.γ (≥150) C, D (Q)
β (80÷149)
.β (P)
F (O)
I (P,S,T)
–
–
+
–
Obr. 1: Výsledný strom (kurzívou v závorce vyznačeny nově klasifikované moduly)
Nově klasifikované moduly Pro nová data získaná dalším testováním na dalších modulech získáváme po průchodu stromem jejich výsledné třídy. Průchod je vidět ve stromu z kurzívou označených modulech. Nezávislé proměnné (metriky: funkce, propojení dat, počet revizí) Metrika Funkce Propojení dat Počet revizí Třída
Modul M R 195 2 -
N R 75 4 -
O F 0 11 -
P R 130 8 -
Q P 172 7 +
R F 51 0 -
S P 24 5 -
T P 132 5 -
Závěr: Pro modul Q je vysoká pravděpodobnost více než 120 chyb. Nová metoda – metoda plovoucích mezí Při vytváření klasifikačního stromu předem dané (expertní) hranice metrik nemusí být vždy optimální a mohou způsobovat vytvoření stromu se slepými koncovými listy nebo s koncovými listy, které jsou stále nehomogenní přestože jsou již vyčerpány všechny metriky. Pokud však budeme procházet všechny možné meze (také i počet mezí) můžeme dostat menší hodnoty E() a tím i lepší dělení jednotlivých větví stromu. Tuto metodu nazveme metoda plovoucích mezí. Protože by bylo náročné procházet ručně všechny možné meze a zjišťovat vhodnou metriku a meze vytvořili jsme pomocný program, který propočítává minimum E() přes všechny metriky. Program generuje tyto meze v polovinách mezi všemi naměřenými hodnotami pro danou metriku. Výsledkem (výstupem) programu je vyhledání optimální metriky pro kořen (přes minimum E()). Následně je pak možné vybrat pouze moduly jdoucí určitou větví a znovu určit optimální metriku pro další kořen. Vstupní údaje Pro konstrukci stromu pomocí nové metody jsme opět použili údaje z programu CSC Atlas.
.α (≤3)
Počet revizí
.β (>3)
B, C, D, I, F, G, J
A, E, H, K
–
.γ (≥86)
Propojení dat
.α (≤10)
C, D, J
G .β <10÷86> B, F, I
–
Funkce
.α (P)
.β (F)
.γ (R)
J
C
D
–
+
+
Obr. 3: Aplikace klasifikačního stromu na nových modulech pro novou metodu Nezávislé proměnné (metriky: funkce, propojení dat, počet revizí) Modul O P Metrika M N Q R S T + + Třída -
+
Závěr: Pro moduly O a P je vysoká pravděpodobnost více než 120 chyb. Tento výsledek byl potvrzen empiricky a lze tedy konstatovat, že nová metoda se v tomto případě ukázala být lepším odhadem modulů náchylných k chybám. Literatura [1] Strouhal J. A.: Klasifikační stromy ve spolehlivosti software. Sborník příspěvků konference ROBUST 2006, JČMF Praha, ISBN 80-7015-073-4, str. 461-468 [2] Hahn A., Radkova L., Achiemere G., Klement V., Strouhal J.: Evaluation of Our Therapeutic Approach to the Patients Suffering from Chronic Tinnitus. Acta Oto-Laryngologica, zasláno k publikaci [3] Dohnal G.: Markovské modely spolehlivosti software. Sborník příspěvků konference ROBUST 2006, JČMF Praha, ISBN 80-7015-073-4, str. 453-461 Adresa autora: Ing. Jan Adam Strouhal, České vysoké učení technické v Praze, Fakulta strojní, Ústav technické matematiky, Karlovo nám. 13, 121 35 Praha 2 e-mail:
[email protected] Tato práce byla vytvořena v rámci projektu MŠMT 1M06047 - CQR
