о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999ꡡ3611ڡVol.36No.111999



ݴƲеĹעģͼӦ㷨
ӨТ
ժҪע(FI)һЧĲԺݴ (FTM)ķ, ɱձӦݴϵͳ̵ĸ׶. FIȷĺ͸ 㷺ӦڶFIԭһ. ϸFIӦöFTMڲ ֳ, ڴ˻ԪFIģ, ԸԪԽ . ͬʱ, ΪFIģ͵ľӦù, иFI㷨(FI-IEA), ˸㷨ʵеĹؼ.
ؼʣݴ,ע,,
ͼţTP302.8
A FAULT INJECTION MODEL AND ITS APPLICATION
ALGORITHM FOR TESTING AND EVALUATION OF FTM
SUN Jun-Zhao, WANG Jian-Ying, and YANG Xiao-Zong
(Department of Computer Science and Engineering, Harbin Institute of Technology, Harbin 150001)
AbstractFault injection(FI) is a powerful method for the test ing and evaluation of fault-tolerance mechanisms(FTMs), which may widely be used during all phases of the development of fault tolerant computer systems. The technique of FI cannot be applied correctly and widely unless it is based on a consistent understanding of FI philosophy. FTM is the application object of FI and its characteristics as seen in testing and evaluation processes are discussed in detail. And then an FI model is described as a 6-tuple. The attributes of each factor are deeply analyzed. As the actual application process of the FI model, an FI independent experiment algorithm(FI-IEA) is presented at the same time, and some key problems on how to implement the algorithm are discussed.
Key wordsfault-tolerance mechanism(FTM), fault injection, testing, evaluation
1
ݴϵͳеһҪζõݴ(FTM)вԺ.ע(FI)ǲFTMЧ1.ͨΪϲϵͳ,FIϵͳϺʧЧĹ.öϵͳעϺӦϢļͷ,ʵֲԺFTMĿ,.ʽ֤ģͺͻڲȷ,FIΪһֻĲ,Ӧ÷Χ㡢ȷȸߡʱ仨ٵŵ,ڶ๤ߺоԱ.
ĿǰFIокܶɹ,LʵõĹҲͶʹ.Ȼ,FIʽͳһģͷоȱ,о棺
(1)FIʵַĸĽʹ£24,ڲͬעϵķܾȷģʵӰ졢鿪߽ȷԡʵõFIߵȷо
(2)ĳЩĿרƵFI57,оĿṩضĿϵͳĳЩȤָ.
оľԵЩоFI򵥵ĶϵͳӦ.ڲڶFIһµ,һȷȲ,һԽƹΪ㷺Ŀϵͳ.
Ŀǰý϶ϵFIģоף8ΪFIģ,FIΪԪF,A,R,M,ģ͸Ԫİj
(1)󼶱,ӦFIĿϵͳģ,ģ͡ģͺģ3֣
(2)ӦĿ,Ŀ:ȷϺƸ.ǰֱ֤̺߰FTMĹų͹Ԥ;߰ṩĽƵϢԼάĹֵ.
ģ¼ڲ㣺
(1)ȱٶģ͵ʽ,ֽͨܣ
(2)FIĹӦ,FIԵо㣻
(3)ֻ˹FIľ̬Ԫ,δеĶ̬̣
(4)ԹϺ͹(ϵͳΪA)ڴԺ͹򻯣
(5)ûȷģеľӦ÷.
оFIͳһʽģͼӦ㷨.ϸFIFTMڲбĻ,ԪFIģ,ԸԪϸµķ˸ģھӦе㷨,㷨ʵеļؼ.
2ԲFTMļ
ݴ㼼áࡱ˼ιӰ,߼ϵͳɿԵҪֶ.ϵͳвõFTM?㼼йϴҪ.ϵͳ󼶱Ĳͬ,ΪɲιɵĶ༶νṹ,ɵ߿ɳΪӲϵͳӦ3.ÿһоܷ.ϵͳõÿһFTMΪλڸòνṹĳһ,ֹüвĳЩһ,ټ⵽ùϵķ,ϸ߲δйϢ,Աڽϸ߼ϴ.FTMʵֵĹϴܰ⡢Ρԡ顢ָع.뼼Ӷʱ(watchdog)ȽϡݡءлƵǵ͵FTM.
2.1ܼFTMģ
ӹܼϳ,FTMģͿɱʾΪ״̬(STATE)(OUTPUT)Ķ壺
STATE(FW,S)=S',OUTPUT(FW,S)=A,дΪFTM(FW,S)=(A,S').
,FTMɴϼF빤ؼWĵѿ˻;SΪϵͳԭ״̬,S'Ϊϴϵͳĸ״̬AΪFTMFWȡĹϴ֮.ܼFTMģ͵Ķ½жFIģ͵Ķ.
2.2FTMĲ
FTMĲָ֤ƺʵֵȷ,FTMԤڹܲһµƹ,ΪһϺ;ṩйعϵϢ.FTMרڴϵ,ʹFIΪFTMԵҪֶ.
FTM,ҪָйϴתΪЧʷĶ,ҲԶһЩ/Ŀ.ԺFTM,ЧԲƵԭ¼棺
(1)׶βƵĹϼ,ʹƵFTMпδԤڴĻԤһµĹͣ
(2)FTM/ʵֹĹ,ڲԹδֻȷų
(3)ԵĶFTMΪһʱֵ,繦ܷĳͻȣ
(4)ΪݴƶӵļͻָȲͨݴ,ܵӰĿܣ
FTM۽Ϊɿģ͵Ƚģе,侫ȷȶģӰܴ.FIҪӦüͨFTMΪģṩЩ.
2.3ĿFTMʽ
ݴϵͳ̵Ĳͬ׶пγֲͬʽĲĿģύ,
(1)ģģ,ϵͳ̵γ,ͨĳ׼(VHDL)ϵͳΪ/ṹ.󼶱Ĳͬ,γϸ³̶Ȳͬģģ.Ӳܿؼ߼żĴ-ͼģ鼶оƬܽż߼.ɰ΢ָָϵͳӦ.Ϊģʱ俪,ûģ(hybrid simulation)ģʽģ(mix-mode simulation)ͷֲģ(hierarchical simulation)Ƚģ⼼
(2)ģ,ϵͳԭ,γڿ̺,Ŀϵͳʵʵ.ʽĲͬ,ɷΪӲԭ͡ԭͺX-(Ӳ+)ԭ3.ӲԭݴIC,ԭN-汾ݴЭ.ģҲģģƵڲͬ󼶱Ͻп.
ĿFTMʽֱӾúFIģ.
2.4
ҪԴӲͬȶϵͳFTMв,Ҫ3֣
(1)ԪFTM(U-FTM):ĳϵͳеĹܶFTM,ĳֹϴܵеһ֣
(2)FTM(I-FTM):ϵͳеĳһӹϴܵFTMܳƣ
(3)ϵͳFTM(S-FTM):ʵϵͳݴĿϵͳFTMЧܺ.
FIеĲԳӦU-FTMI-FTMĿ,ҪӦS-FTM.
3FTMеFIģ
FTM,FIӦڶӲĲԹ,ӲѡԵĹϷ(fault simulation)дģ(seeding model)Ĵ߲Է(program mutation).۵ڲFTMFIģҿɷƹ㵽ЩӦ.


ͼ1FIԪģ
ڲFTMFIһԪ飺
FI=F,W,R,M,Cond,Proc,
,FWRMֱΪϼؼؼ,ǹFIľ̬Ԫ;ϵͳĳ(f,w)FWĳԪrRĶӦϵʾΪ(f,w)Condr,ȻCondFWR;ProcΪCondĳһmMĴ,ΪProc:Condm.CondProcǹFIĶ̬Ԫ.Ԫϵͼ1ʾ.¶FIԪֱ.
(1)ϼF
FڻȡĳmMFIӦõĹϼ.FEXΪFI迼ǵĹϼ,FEIΪõFIܹעй֮,F=FEXFEI.FEXȷȡĿΪԻ۵Ĳͬ.FTMĲ,FEXĿFTM˵Ĺ֮.FTMʱ,FEXΪɲָĳϼϵͳֳпܷĹϼ.Ĺģ͵ıʾɣ
ٹԣF=(LM,VM,TM),LM,VM,TMֱΪλáֵʱ3ֹԵģ;
ڹϷֲf=(lm,vm,tm)F,fڹȫFķP(f|F),fĸӦģеķֲɣP(LM=lmVM=vmTM=tm).Լ໥,P(f|F)=P(LM=lm)P(VM=vm)P(TM=tm)ǵԼ,P(f|F)ĳʵʽ,Ϊ˳ȡڿɻõĹϷֲݼע빤߹.
(2)ؼW
wW,wʾϷʱϵͳ״̬Ϊ.ϵעҪϵͳصĳּͬ.ֵȷϵͳ״̬Ϊע봥,Դ˾עʱ(T(Inject)).ҲʹFTM,Ϊ֤ƸĽЧFIпԵҪʵ.ϵͳΪľȷϵͳ͹ϵĳ󼶱.ͨX-ԿɼΪϵͳеĳ,ӲĿFTMΪΪӲź,ĿFTMΪΪ.
ͶӰܴ.FTMĲ,ѡʹעĹϱΪĿw;FTMʱ,wΪϵͳֳźŵķ棬ͨûϵĵͳʵʱϵͳеĻģ.Ϸ,ĳFIӦõĹģʽʾɷΪ:΢۷,ע봥wTInjectWTInject,ʾעʱ̵ϵͳ״̬,WTInjectΪпע봥֮;ں۷,ϵͳеĸwRUNWRUN,ʾעмϵͳΪ,WRUNΪпܸ֮.
FͬҪȫеķֲ,ʾΪ
P(w|W)=P(WTInject=wTInject|WRUNwRUNPWRUNwRUN.
FW֮ʱ,ֱ۵ķwTInjectȡwRUNڼʱ̣FW,ע봥wT(Inject)FĹϷʱ.
(3)ؼR
rR,rǽĳһѡ(f,w)ʩĿϵͳFTMʱ,⵽ķӦΪϢ.ڱʾעЧĿϵͳ״̬γϵͳĻ¼E={e1,e2,,eN},ӶϵͳӦΪɶΪ
ٻ¼eEΪ;
aiajΪ,aiajaiajaiΪ,Сģţֱʾ߾һ
޴ԭõľΪ.
ĿFTMͲĿ, ߿ԶΪA={a1,a2,,aM}, öԻ¼ļRа3Ϣ
ΪжYa:(FW){0,1},ʹ(f,w)(FW),Ya(f,w)=0,a/1,aδ
Ϊʱ̺Ta:(FW)0,),ʹ(f,w)(FW),Ta(f,w)=aʱ̣aδʱ,Ta(f,w)=.˴עʱΪʱ,T(Inject)=0
Ϣ.һڸжĳЩΪǷ,ڻ¼Ǿɼ,硰ǷΪ¼;һ,ϵͳڹϷµķӦΪɽº.
(4)M
ǲFTMFIĿ꼯.FIڲFTMʱ,MǶĿFTM˵ȷԵж(pass/fail)./ʵֹʱ,ͨϣܸRеġϢȷĽƻķ.FIFTMʱ,ҪĶǸ(coverage),ΪFWĿFTMϴΪa(⡢롢ָ)ķʱ̺T(a)ۻֲ
Ca(t|FW)=P(Tat|FW).
Ca(t|FW)ڸܶȺLa(t|FW),La(t|FW)ΪΪaӳ(latency).ɼ,ӳһԵȼ۵Ķ.ͨиĵǸʵ򻯲
ʣ

ƽӳڣ

оĿĲͬ,ϴԡֵ䡢ԡFTMıȽŻϡʧЧģʽȵ.
(5)ӦϵCond
ʾ(f,w)r֮ĿFTMµӳϵ.ƻȡһmMĹΪһΡ顱(IE),IEлȡFWRռеһ(f,w,r)ĹΪIEһΡС(run).Ȼ,ÿһIEʼʱ,Cond=?IEÿһRun,Cond=Cond(f,w,r).
(6)Proc
ÿһIECondȡmM㷨.FTMĲ,ProcΪ򵥵Ϊȷж.ڶFTMЧʱ,ƼCondаݽз,ơȻơƵ.ĿΪȡĳķֲʱ,æ2ȼ.
4FI㷨(FI-IEA)
FIIE㷨(FI-IEA).ĳFTMϵһIEڻȡmM,ĿFTMʽ,ϽۿȷΪFI-IEA㷨ĹȫFȫWΪ֮A.㷨£
Cond=?C=C0m=Acc=Nulli=0
while(End_Expr_Cond(C,Acc)<>True)do
i=i+1
(f,w)=Input_Case_Sele(F,W,Cond,m)
Run(wRUN)
Call Inject(f,wTInject)
r=Readout()
Cond=Cond(f,w,r)
m=Proc(Cond)
C=C+Cal_Cost(i)
Acc=Cal_Acc(i,Cond,m)
end
㷨иԪء͹ھβͬ,нInject̺ReadoutΪ߹̣ͼ2ʾ.۸㷨ʵеļؼ.


ͼ2FI
(1)ѡ
Input_Case_Sele(F,W,Cond,m).书γɵiRunе(f,w)ע.FTMĲ,ͨùܲԷ,ɴĿFTMĹ˵Ԥڴ(F,W)еÿһеĲԪ(f,w).ิӵFTMӲ֧ʵֵ.ΪһĲԳ,FTMĽṹģ,ԴģԹ,ÿһӦõ(f,w).
FIFTMʱ,ѡԸĿĲͬ,Ҫַ
ȷѡ:ڱȽϲͬFTMִͬϴܵЧʸߵ.ʱ,wRUNѡȡ׼Գ(benchmark),ԤָռFWTInjectеÿһԪ(f,wTInject)ע飻
ѡ:ĳضFTMЧ.漰ĳֳȫռFWнг,õĳʳֲ(stratified sampling)༶(multi-stagesampling).
Աʷ(Cond,m)ΪǳڡʽѡԵĿ.Եʷȷ֦δִ·Ĵ?;в޷Żسʱ,轫עԪ(f,w)ȫ(F,W)ų.
(2)ֹ
End_Expr_Cond(C,Acc).䷵ֵΪTrueʱʾIEֹ,õmΪĹ.ֹʾΪñC;ȷȱAcc֮Թϵ,ʽΪCMAX(C)ݡţAccMIN(Acc).MAX(C)Ϊ,MIN(Acc)Ϊɽܵ;ȷ.
ü㺯Cost_Cal(i).iĺ.ܷC0Ϊʼ÷,NΪIE,CiΪiRunķ.,ʱΨһ迼ǵķ,ÿRunʱ,ӶÿֱRuni򻯱ʾC=i.
ȷȼ㺯:Acc_Cal(i,Cond,m).ȡںȷȵĲͬ׼.FTMĲ,ĳָǳ̶Ϊ׼,繦ܲضĸ,ṹе/ж//·/ģ鸲ʵ.FTMʱ,ȷȵļõĳͲƼй,ı׼йƲı׼䷶ΧֲȶԵ.
(3)ע
Inject(f,wTInject).вõע뷽ĿFTMʽϵͳ/ϵĳ󼶱й,ͼ3ʾ.һֹע빤,ʵע빦,迼ǵʵַ׳̶,Ŀϵͳ(ǷŸмų̶),ǷƻĿϵͳĿ,ʱֱĸߵ,չԺͨԵȵ.


ͼ3ע뷽
غReadout().вõע뷽ʹ¼Ͳͬ,ƲͬĶز.޹й̼ıȽϡִ·Ӳźš桢˹۲.
ע뼰صĶ̬ͼ4ʾ.


ͼ4עϢع
5Ӧʵ
FTT-1͹ע9ǻڱFIģ?ʵֵĹܽżע빤.ģӲоƬܽϵı,עλú͹ģͿѡص.ùӦڴܹ˾709ܹ˾Ժ501ܹ˾771ȲƵĶͺݴ,ڸgԺĿзҪ.Ŀǰ,ĽHFI-3ѾƳɹ,ԭйܻעСɿءĿַע뷽ʽȸΪȽĹ,ڱһЩؼʹ.
FIģֲģеĲ,ΪFIоһʽۿ.Ըģ͵ľӦ㷨Ĳ,ṩ˽FIӦڲFTMľеһַ.
ʵ֤,ĽFIģܹ׼ȷFIĻԭ,Ӧ㷨ձ,ΪʵõFIϵͳṩһ;,ָFI֮Чķ.
*õȻѧ(Ŀ69873013).
߼飺,,19721,ʿо,оΪģͺϵͳԲ.
Ө,,19694,ʿо,оΪϵͳɿۺͼ.
Т,,19391,,ʿʦ,оΪϵͳݴ㼼.
ߵλҵѧѧ빤ϵ150001
ο
1Clark J A, Pradhan D K. Fault injection: A method for validat ing computer-system dependability. IEEE Computer, 1995, 28(6): 4755
2Kanawati G A, Kanawati N A, Abraham J A. FERRARI: A flexible software -based fault and error injection system. IEEE Trans on Computers, 1995, 44(2): 248260
3Goswami K K, Iyer R K, Young L. D?PEND: A simulation-based environmen t for system level dependability analysis. IEEE Trans on Computers, 1997, 46(1): 6074
4Carreira J, Madeira H, Silva J G. Xception: A technique for the experi mental evaluation of dependability in modern computers. IEEE Trans on Software E ngineering, 1998, 24(2): 125136
5Vardanega T, David P et al. On the devlopment of fault-toleranton-board control software and its evaluation by fault injection. In: Proc 25th IEEE Int'l Sympon Fault Tolerant Computing(FTCS-25). Pasadena, California, 1995. 510515
6Amendola A M, Impagliazzo L, Marmo P et al. Experimental evaluatio n of computer-based railway control systems. In: Proc 27th IEEE Int'l Symp on Fault Tolerant Computing(FTCS-27), Seattle, 1997. 380384
7Stott D T, Ries G, Hsueh M C et al. Dependability analysis of a high-speed network using software-implemented fault injection and simulated fault injection. IEEE Trans on Computers, 1998, 47(1): 108119
8Arlat J et al. Fault injection for dependability validation: A methodology and some applications. IEEE Trans ?n Software Engineering, 1990, 16(2): 166181
9Wang J Y, Sun J Z, Li Y C et al. The implementation of FTT-1: A hardware-based fault injector. In: Proc Computer-Aided Design, Test, and Evaluation for Dependability. Beijing, 1996. 170174
ԭյڣ1998-10-27޸ĸյڣ1999-07-27.
