ѧ
JOURN AL OF SOFTWARE
1999ꡡ1010ڡVol.10No.101999



T3BDDĶ̬ģͼ
  ա 
ժҪ Java Beansһ׼.ĶJBDL(Java Beans description language),Լ淶.Ϊ˼Java BeansԼʵ֮һ,¸һֻJBDLʽֵģ͵ĳ󻯶̬ģͼ鷽.صT3BDD3-terminal binary decision diagramķŻ̬ģͼ鷽.
ؼʡ,Java Beans,ʽ淶,Ż,ģͼ,жͼ.
ͼšTP311
T3BDD Based Dynamic Model Checking
NI Bin FENG Yu-lin HUANG Tao
(Laboratory of Computer Science Institute of Software The Chinese Academy of Sciences Beijing 100080)
Abstract Java Beans is a standard for software components. For checking the consistency of the Java Beans semantic constraints with its implementation, a formal Java Beans description language (JBDL) and a dynamic model checking method are proposed in this paper. The authors contribute an efficient symbolic model checking approach using T3BDD. The approach is based on three valued semantics for JBDL formulas and a kind of abstract model which is dynamically established and evolved during Beans execution.
Key words Component, Java Beans, formal specification, symbolic, model checking, binary decision diagram (BDD).
ͶڳΪ֧ģ͵һͼ.ɸõĻԪͺ.Ĺ淶ͨһı׼,ṩ֧ϵͳṹAPI.,Щ׼Ŀǰ÷ʽķ̻.֧úͷֲʽĹؼ.Ϊ˿,ϣʽؽ֤.ںܶ,֤ǱҪ.,Ҫжεķƺʵ.徫ȷϸʽ,ʹοԱ岻ϵ.֤ڱ֤ȷ.֤ҲڿѡϹԼϵͳҪݺȷԼֶ.
ѡJava Beans׼Ϊо,һڶһʱ߼Ĺ淶ԡJBDL(Java Beans description language)̻BeanԼ.Ϊ˼BeanJBDL淶ʵ֮һ,һֻڳͷŻĶ̬ģͼ鷽.ڶ̬,ģǶ̬,żĽ,ģͻڲݻ.,ĸʱʽڶ̬ݱģµֵ,ԼT3BDD(3-terminal binary decision diagram)Чؽģͼķ.
ģͼ֤ϵͳΪԼһַʽ.ģ״̬Ŀ͵.ĿǰģͼҪǴӼϾܵر״̬ը.һЩԵļ.
(1) ʹЧ㷨״̬ռ.ԵĹCMUE.M.ClarkeR.E.Bryant,TEXASE.A.EmersonʹBDDֺͶԳԵȷ߼֤[13];P.GodefroidƫԺ״̬޹ص鲢ϵͳ[4].
(2) ģͼ(compositional model checking).ԵĹPnueliļ-֤;Winskelm ֤;GrafSteffenԼȫռ֤ķ.
(3) ģͼ(symbolic model checking).ԵĹUPPSALAWang Yi K.G.Larson˶ʵʱϵͳеȷ֤;DenmarkH.R.Anderson,SusscxM.Henessy,IBMD.Kozen,EdinbergeC.StirlingйѧԺоֻ˶CCSĲϵͳеȷ֤.
(4) óģͼ.ԵĹ:CMUD.E.Long˶ÿг󻮷,ACTL*ʽʽ֤;Wolper޹صϵͳģͼ;Kurshan״̬ͼĹ;BurchBensalem˻trace۵Ĺ.
෽,ǹĲͬ:(1) Ҫģʱ̬,ͬʱ,ģڲϵݻ,ʹʱʽֵ;(2) ǲһĳ󷽷,ַʹóԶ,ҲڳռϽвνʵĳ;(3) BDD,T3BDDʾģͺ͹ʽ,ģͼ.
ȼҪJBDL淶,Ȼģͺͳģ͵ʽԼT3BDDģͼ㷨,ʵоĽ.
1JBDL淶
Լ̻Beanľ̬ṹͶ̬ΪӦ,4Լ.̬Լ̻Bean״̬ռ.ΪԼ̻BeanĸӦǰ.Լ̻Beanڴ֮,¼ڹ,״̬ΪӦʱ.ЭԼ̻ɵͲBeanЭɸ߲BeanĲʱӦʱ.JBDLķʽ:
< JBDL Specification> =Spec <Bean Name> Inheritance<Bean Name>< Static Constraints>;
<Behavior Constraints> ; <Life Cycle Constraints> ;
<Cooperation Constraints> ;
End Spec
<Static Constraints =Static Constraints: < Static Formulas 
<Behavior Constraints =Behavior Constraints: (<Behavior Name:
Pre Conditions <Static Formulas Post Conditions < Static 
Formulas)*
<Life Cycle Constraints =Life Cycle Constraints: < Temporal Formulas
<Cooperation Constraints =Cooperation Constrains: (<Behavior Name>: < Temporal 
Formulas)*
JBDLǻڶһνʷ֧ʱ߼.߼Ե֧,ԱJava Beansĸֶ.ǻ߼Ե,ԱͳһءϵرBean״̬Ͳʱϵ.JBDL淶ϸڿԲο[57].
2ģ 
Ҫж̬,ҪBeanйҪʱ򼤷¼,ȴ.¼ļBeanյ¼,ݴBeanĵǰ״̬ݻģ,ݸģһԼ,ȻѼظBean.δֲһ,Bean;,һ,ʾԱиԤ.ƪ,ֱӸģͺͳģ͵ʽ,ּ֧¼ƺͳ󷽷ϸڿԲο[59].
1. ģ¶ԪM={S,R,I}:
(1) SBean״̬ļ,״̬sSҽsǴBeanڼдĳ¼ʱ״̬.
(2) RSSϳΪ״̬תһԪϵ,(s,t)Rҽȷtļ¼ڼзȷsļ¼֮,֮û¼.
(3) IR,s IҽsǴBeanڼдڳʼ״̬¼ʱ״̬.
ڼģǲݻ,һ,ĳЩʱʽֵJBDLȻΪ,żļ,ڽһݻļģ,ǵֵΪ.,Ǽ⵽һʱԼ,ǲ֪ʱ㻹ò.,Ҫ:(1) ʽĿǰ,żģ͵ݻ,ʽڽ;(2) ʽڴڿʼļģϲ.ǰѵ1¹ʽֵΪȷ(unknown).,ʱʽڼģµ3ȡֵ.JBDLʱʽֵ嶨.
2. ڼģMռC,M,s0 |= f,ΪʽfڼģMµ״̬s0,M,s0| f,ΪʽfڼģMµ״̬s0,M,s0 |?f,ΪʽfڼģMµ״̬s0ȷ.ϵ|= , |ٺ|= ?ݹ鶨:
(1) M,s0 |= p ҽpǾ̬ʽ,p״̬s0,
M,s0 |p ҽpǾ̬ʽ,p״̬s0;
(2) M,s0 |= f1  f2 ҽM,s0 |= f1M,s0 |= f2,
M,s0 |f1  f2 ҽM,s0 | f1M,s0 | f2,
M,s0 |= ?f1  f2 ;
(3) M,s0 |= f1  f2 ҽM,s0 |= f1M,s0 |= f2,
M,s0 |f1  f2 ҽM,s0 | f1M,s0 | f2,
M,s0 |= ?f1  f2 ;
(4) M,s0 |= AX(f1) ҽ(s0,t)R״̬t,M,t |= f1,
M,s0 | AX(f1) ҽ(s0,t)? Rĳ״̬t,M,t | f1,
M,s0 |= ?AX(f1) ;
(5) M,s0 |= EX(f1) ҽ(s0,t)Rĳ״̬t,M,t |= f1,
M,s0 |= ?EX(f1) ;
(6) M,s0 |= A[f1Uf2] ҽ·(s0,s1,), i(i 0)[M,si |= f2 j(i> j
 0)[M,sj |= f1]],
M,s0 |A[f1Uf2] ҽĳ·(s0,s1,), i(i 0)[M,si|(f2 f1) 
j(i>j0)[M,sj |f2]],
M,s0 |= ?A[f1Uf2] ;
(7) M,s0 |= E[f1Uf2] ҽĳ·(s0,s1,),i(i0)[M,si|=f2 j(i>j0)
M,sj |= f1]],
M,s0 | E[f1Uf2] ҽM,s0 |(f2  f1),
M,s0 |= ?E[f1Uf2] ;
(8) M,s0 |= AG(f) ҽ·(s0,s1,),i(i0)[M,si |= f],
M,s0 | AG(f) ҽĳ·(s0,s1,,t),M,t | f,
M,s0 |= ?AG(f) ;
(9) M,s0 |= EG(f) ҽ·(s0,s1,), i(i 0)[M,si |= f],
M,s0 | EG(f) ҽM,s0 |f,
M,s0 |= ?EG(f) ;
(10) M,s0 |= AF(f) ҽ·(s0,s1,),i(i 0)[M,si |= f],
M,s0 |= ?AF(f) ;
(11) M,s0 |= EF(f) ҽ·(s0,s1,),i(i0)[M,si |= f],
M,s0 |= ?EF(f) .
3ģͼ鷽
ͨģͼBeanʱ.,ѡһֳģ͵Чıʾ,ַԼģͼʱҪ״̬ռ,һ߼ЧʺͿԼ״̬ռģ.Ȼ,ǸĳģϽģͼ㷨.
3.1Żʾ
Żʾ÷ʾ״̬״̬ת,ֱʾʽƺʵ״̬ռЧ㷨.жͼBDD(binary decision diagram)[2]ǽӦýΪ㷺һַŻʾ.׼BDDʾģ.JBDLʱʽڼеֵ,BDDֻܱʾֽ,޷ֱBDDʾJBDLʱʽ.Ϊ,ǶBDD,ʹBDDսᶥһ,ΪսᶥBDD,T3BDD.
3. f:booleanm{true,false,unknown}һmάӳ䵽{true,false,unknown}ĺ.fѲռ仮Ϊ3{Strue,Sfalse,Sunknown},ʹStrue={< x1,x2,,xn,>|f(x1,x2,,xn)=true}, Sfalse={< x1,x2,,xn> |f(x1,x2,,xn)=false},Sunknown={< x1,x2,,xn> |f(x1,x2,,xn)=unknown}.ftrue,ffalse,funknownֱǼStrue,SfalseSunknown,fıʾʽftrue.true+ffalse.false+funknown.unknownfķʽ.͵ʽ3սᶥtrue,false,unknownBDDʾ.ǰBDDΪսᶥBDD,T3BDD.
4. ͼͬT3BDDΪԼT3BDD.
1. κκf:Booleanm{true,false,unknown}Ψһ(̬ͬ)ԼT3BDD֮Ӧ,ҸT3BDDǶٵT3BDD.
ݶ1,JBDLʱʽT3BDDfʾ,㹫ʽ״̬Strue,㹫ʽ״̬Sfalse,ȷ״̬Sunknown.ģҲT3BDDʾ.״̬һBeanԼо̬ӹʽĲֵȷ.ÿ״̬ӦһĲֵ.,ĸΪn,ÿ״̬ԿһnԪ.ǾͿnԪϵʾ״̬ļϺͳʼ״̬ļ,nԪϵòʽʾ,ҲͿT3BDDʾ.ͬʱ,ñBeanԼо̬ӹʽĲVһż(Vfrom,Vto),ڳ״̬תбʾʼ״̬͵״̬ĲֱӦżеVfromVto,VfromVtoΪT3BDDӦĲʽı,ó״̬תʼ״̬͵״̬ӦĲΪԪعһϵ.ʽӦT3BDDͱʾ״̬תļ.
3.2ģͼ㷨
ǸT3BDDʾĳģ,T3BDDʾJBDLʱʽģͼ㷨.
ģͼĹ,ҪǸݳģͺ͹ʽʽݹ鹹T3BDD.T3BDDS(s)ʾ״̬SӦT3BDD,sǱʾ״̬Ĳ.T3BDDR(s,t)ʾ״̬ת϶ӦT3BDD,sΪVfrom,tΪVto.T3BDDI(s)ʾʼ״̬IӦT3BBD,sǱʾ״̬Ĳ.T3BDDf(s)ʾʽfӦT3BDD,sΪT3BDDеĲ.˵ΰJBDLʱʽʽݹع칫ʽT3BDD.Ϊ˱﷽,ĹʽһֲҪJBDLʱʽ,ЩʽעΪʽ.
(1) ʽpǾ̬ӹʽ
ݳķ,pģӦĲ֮Ӧ.ģpӦĲΪvi,visķ,T3BDDp(s)ǽΪviķսᶥT3BDD.
(2) ʽf(ʽ)
T3BDDf (s)еսᶥtrueΪfalse,falseΪtrue,unknown,õT3BDDf(s).
(3) ʽu2f(f)(ʽ)
T3BDDf(s)еսᶥunknownΪfalse,õT3BDDu2f (f)(s).
(4) ʽf 2u(f)(ʽ)
T3BDDf (s)еսᶥfalseΪunknown,õT3BDDf 2u (f)(s).
(5) ʽf1*f2,*ΪŻߡ 
T3BDDf1 * f2(s)=T3BDDf1(s)*T3BDDf2(s)Ч㷨BDD㷨һ,䲻֮ͬڡź͡ 3ֵ{true,false,unknown}ļ㷽:

truefalseunknowntruefalseunknown
truetruetruetruetruetruefalseunknown
falsetruefalseunknownfalsefalsefalsefalse
unknowntrueunknownunknownunknownunknownfalseunknown

 
(6) ʽf(s)|vi=b,s=< v1,v2,,vn>,btruefalse(ʽ)
ʽʾviƵb.Ƶ㷨BDDƵ㷨,:
(a) T3BDDĶ,viĶӦ(bΪtrue,viΪtrueӦ;bΪfalse,viΪfalseӦ)ö.
(b) ԼT3BDD.
(7) ʽtf(s,t)(ʽ)
< v1,v2,,vn>ΪtӦĲ,tf(s,t)= v1 v2vn f(s,t), vi f
(s,t)=f(s,t)|vi=true f(s,t)|vi=false.
(8) ʽEX(f)
㹫ʽf 2u(t(f(t) R(s,t)))ӦT3BDD.
(9) ʽAX(f)
㹫ʽ (t( f(t) R(s,t)))ӦT3BDD.
(10) ʽm Q(g(Q)),g(Q)=f(s) t(Q(t) R(s,t))(ʽ).
g(Q)true,g(Q)false,g(Q)unknownֱT3BDDg(Q)(s)ȷļStrue(g(Q)),Sfalse(g(Q))Sunknown(g(Q)),Qgеĳֲ ,gtruegfalse2|S|2|S|İյĵ,ݲ,gtruegfalse󲻶С.T3BDDm Q(g(Q))(s)ȷļStrueʾgtrueȷС,Sfalseʾgfalseȷ󲻶,Sunknownʾ״̬.
[1],ͨf(s) t(f(t) T(s,t)))m Q(g(Q))ֱӼm Q(g(Q))ЧҪ,T(s,t)=P(R(s,t) w(P(s,w) P(w,t))).h(P)=R(s,t) w(P(s,w) P(w,t)),m P(h(P))õķ.P0=false T3BDD,ȻPi+1=g(Pi),ֱPi+1Piͬ.
(11) ʽn Q(g(Q)),g(Q)=f(s) t(Q(t) R(s,t))(ʽ)
g(Q)true,g(Q)false,g(Q)unknownֱT3BDDg(Q)(s)ȷļStrue(g(Q)),Sfalse(g(Q))Sunknown(g(Q)),Qgеĳֲ ,gtruegfalse2|S|2|S|İյĵ,ݲ,gtruegfalse󲻶С.T3BDDn Q(g(Q))(s)ȷļStrueʾgtrueȷ󲻶,SfalseʾgfalseȷС,Sunknownʾ״̬.
[1],ǼvQ(g(Q))=Q(g(Q)) ( t(T(t,t) T(s,t))),T(s,t)=m P(R(s,t) w(P(s,w) P(w,t))).
(12) ʽE(f1Uf2)
㹫ʽ(f1f2) f 2u(m Q(f2(s)t(Q(t) (f1(s) R(s,t))))).
(13) ʽEG(f)
㹫ʽf f 2u(vQ(( tR(s,t) f (s)) t(Q(t) (f (s) R(s,t))))).
(14) ʽA(f1Uf2)
㹫ʽ (u2f (F1)) f 2u( F2) f 2u( F3) f 2u( F4).F1=Q(( f1(s)  f2(s))t(Q(t) ( f2(s) R(s, t)))),F2=Q(( (u2f(f1(s)))  (u2f(f2(s))))   t(Q(t) ( f2(s) R(s,t)))),F3=Q((   tR(s,t) f2(s))  t(Q(t) ( f2(s) R(s,t))))),F4=  t(T(t,t)  T(s,t)),T(s,t)=m P((R(s,t) f1(s))  w(P(s,w) P(w,t))).
(15) ʽEF(f)
㹫ʽf 2u(m Q((f(s) ( t(Q(t) R(s,t)))))).
(16) ʽAG(f)
㹫ʽ Q(( f(s) (t(Q(t) R(s,t))))).
(17) ʽAF(f)
㹫ʽf 2u( (Q(( tR(s,t)  f (s))  t(Q(t)( f (s) R(s,t)))))) (t(T(t,t) T(s,t)))),T(s,t)= P((R(s,t)  f(s))  w(P(s,w) P(w,t))).
JBDLʱʽӦT3BDD֮,ͨÿʽfs( I(s) f(s))ü,sf(s)=v1v2vn(f(s)),< v1,v2,,vn>ΪsӦĲ,vi(f(s))=(f(s)|vi=true f(s)|vi=false), f(s)|vi =bǰfalseеıfalseƵfalseõT3BDD.T3BDD" s(I(s) f(s))Ϊtrue,ʾfгʼ״̬;Ϊfalse,ʾfĳʼ״̬;Ϊunknown,ʾfĳʼ״̬ȷ.
㷨Ŀռ临ӶʹBDDͬ,˳.㷨ʱ临ӶȰʽʽ,|T3BDDf|ΪT3BDDfĶ,|t|Ϊtĳ,|d|Ϊģ״̬תͼֱ,|d|Ϊ2|t|.

ʽӶȹʽӶ
̬ʽO(1)fO(1)
u2f(f )O(1)f 2u(f )O(1)
f(s)|vi=bO(|T3BDDf|*log(|T3BDDf|))f1*f2O(|T3BDDf1|*|T3BDDf2|)
AF(f )O(|T3BDDf|2*|t|*log(|d|)))EX(f )O(|T3BDDf|2*|t|))
E(f1Uf2)O(|T3BDDf|2*|t|*log(|d|)))AX(f )O(|T3BDDf|2*|t|))
EG(f )O(|T3BDDf|2*|t|*log(|d|)))A(f1Uf2)O(|T3BDDf|2*|t|*log(|d|)))
EF(f )O(|T3BDDf|2*|t|*log(|d|)))AG(f )O(|T3BDDf|2*|t|*log(|d|)))
tf(s,t)O(|T3BDDf|2*|t|))
Q(f(s) t(Q(t)R(s,t)))O(|T3BDDf|2*|t|*log(|d|)))
Q(f(s) t(Q(t)R(s,t)))O(|T3BDDf|2*|t| *log(|d|)))

 
Beanÿ״̬ռÿռ϶,ͬʱڶ̬״̬Ŀ,ֱڼģϽģͼ׵¿ռľ.Ϊ,һֳģͱʾ,ܼټģ͵״̬Ŀ,ܱ֤ܵ״̬Ŀн.ͬʱ,ǻֳ֤󷽷JBDLʱʽı.ʵ,ڳģϽе.ƪ,T3BDDģͼ鷽.ڳ󷽷[5,6,8].
4ʵо
JBDL淶Ͷ̬ģͼ鷽,ƺʵ˼֧ſܺ͹ߡMChecker.MChecker,ǶJavaSoftṩķֲʵƱۼͶʵˣ߽о.ʵ۽ȫһ,˶̬ʱͿռ϶Ч,㷨ʵʱոӶҪԶС.ڹϵͳԼʵоϸڿɲμ[5,6,9].
5 
͸߿ɸԵҪʽ֤.ѡJava Beans׼Ϊо,һڶһʱ߼Ĺ淶 JBDL̻BeanԼ.Ϊ˼淶ʵֵһ,һֻڳͷŻĶ̬ģͼ鷽.ĸ˶̬ģͼ鷽,JBDLʽֵģ͵ĳ,T3BDDڳģϽзŻģͼķ.ʵ,÷ʱͿռ϶Ч.
עͣоõȻѧ͹863߿ƼĿ
߼飺߱1969ʿҪоΪۺͼģͼ飻
գ1942ʿоԱʿʦҪоΪֲ
㼼ƶ㼼̡
Σ1965ʿоԱҪоΪֲ̣
ѧż㼼Ի
ߵλ:йѧԺоѧоʵ  100080
E-mail: tao@ox.jos.ac.cn
ο
1.Burch J R, Clarke E M, McMillan K L et al. Symbolic model checking: 1020 states 
and beyond. Information and Computation, 1992,98(2):142170
2.Bryant R E. Graph-based algorithms for Boolean function manipulation. IEEE 
Transactions on Computers, 1986,C-35(8),677691
3.Clarke E M, Grumberg O, Long D E. Model checking and abstraction. In: SIGACT & 
SIGPALN ed. Proceedings of the 19th Annual ACM Symposium on Principles of 
Programming Languages. New York: ACM Press, 1992. 343354
4.Godefroid P. Model checking for programming languages using VeriSoft. In: SIGACT
& SIGPALN ed. Proceedings of the 24th ACM Symposium on Principles of Programming
Languages. New York: ACM Press, 1997. 174186
5.߱.Լ̬ģͼⷽͼо[ʿѧλ].йѧԺо
,1998
(Ni Bin. An approach to dynamic model checking for component semantic 
constraints [Ph.D. Thesis]. Institute of Software, The Chinese Academy of 
Sciences, 1998)
6.Ni Bin, Feng Yu-lin. Specifying and checking for semantic constraints on Java 
Beans. In: Keijro Araki, Feng Yu-lin eds. Proceedings of the International 
Symposium on Future Software Technology97. Tokyo: SEA, 1997. 7984
7.Ni Bin, Feng Yu-lin. Exploiting abstraction to check semantic constraints for 
Java Beans. In: Jose Cuena ed. IT&KNOWS Proceedings of the  IFIP World 
Computer Congress. Kluwer Academic Publishers Group, 1998. 187200
8.Ni Bin, Zhou Ze-hua. Mchecker an automatically dynamic checking tool for Java 
Beans semantic constraints. In: Chen Jian, Li Ming-shu et al eds. Proceedings of
the 27th Technology of Object Oriented Languages and Systems. Beijing, 1998. 
164172
ոڣ1998-07-07޸:1998-10-19
