UML顺序图的自动验证

UML顺序图的自动验证 !"# 顺序图的自动验证 王璐珍 董 威 陈火旺 (国防科技大学计算机学院，长沙 G&""H#) :I5?-366J7K<-1:L907M$.0? 摘 要 ’() 顺序图反映了系统中并发对象之间的消息交互及顺序，在软件建模中占有重要地位。该文对 ’() 顺序图 模型的自动验证方法进行了研究，在把 顺序图转换为 语言后，使用模型检验器 来验证系统设计模型 >,0?6 @>AB ()/-’ 是否满足某些关键性质需求。为了加强该方法的适用性，采用可扩展的标记语言 文件格式定义顺序图模型的外部 = () 表示形式，该表示方法遵从 的 标准，从而使验证过程适用于不同的 建模环境。NO =A ((()’ 关键词 顺序图 模型检验 @>AB )=)’(( 文章编号 &5P##&5(#)%5P5G 文献标识码 Q 中图分类号 R>#&&$S ""!!""!"""" $%&’()&*+ ,-.*/*+)&*’0 ’/ !"# 1-2%-0+- 3*)4.)(5 3’04 6-* 6)04 #%78-0 98-0 :%’;)04 (@.7006 0D T0?CM4/, @.3/1./，B-4301-6 ;/D/19/ R/.71060:U，T7-1:97- G&""H#) 13E934U 0D /,’ $<5&.)+&: ) 9/VM/1./ 23-:,-?9 ,/D6/.4 47/ 314/,-.4301 -12 9/VM/1./ 0D ?/99-:/9 -?01: .01.M,,/14 0WX/.49 31 47/ ’( ，9U94/?-12 7062 47/ 3?C0,4-14 C0934301 31 90D4<-,/ ?02/631:$R739 C-C/, 31E/943:-4/9 47/ <-U9 0D -M40?-43.-66U E/,3DU31: ，() 9/VM/1./ 23-:,-?9 ?02/69$QD4/, 4,-19D0,?31: () 9/VM/1./ 23-:,-?9 40 >,0?/6- C,0:,-?947/ ?/4702 M9/9 @>AB ’’ ?02/6 .7/.Y/, 40 E/,3DU 3D 2/9 3:1/2 ?02/69 9-439DU 47/ Y/U ,/VM3,/?/149 0D 9U94/?$R0 3?C,0E/ 47/ -CC63.-W3634U 0D 47/ ，()?/4702/=4/193W/ 6 (-,YMC )-1:M-:/ =()D0,?-4 39 M9 /2 40 2/D31/ 47/ /F4/,1-6 /FC,/99301 0D 9/VM/1./ 23-:,-?9$R739 ，/FC,/99301 D0660<9 =(A 0D N(O47M9 40 ?-Y/ 47/ E/,3D3.-4301 C,0./99 -CC6U 40 23DD/,/14 ’() ?02/631: /1E3,01?/149$ :，，，，=->;’.?5’()@/VM/1./ 23-:,-?9(02/6 T7/.Y31:@>AB=() 进行验证。将验证结合到软件设计过程中，可以帮助设计人员 & 引言尽早发现错误，提高模型的可信度，减少由于设计错误带来的 当前，计算机应用已经深入到各个领域。一些安全攸关领 巨大损失。 域对系统的质量 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 非常高，一旦出错，将造成重大损失。为保 证系统设计的正确性，对系统模型进行形式化验证十分必要。 是一种描述能力强大且表达直观的可视化 建 模 语 言 ，为 () ’ 顺序图 !()’*&+软件开发人员提供了从系统需求 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 、设计到实现的有力支持。 顺序图经常用于描述并发系统的设计需求，提供系 ) ’(中的顺序图经常用于早期形式化系统的需求，表示 () ’统的正常执行场景和异常执行场景。它描述对象之间的动态交 系统典型的执行场景。设计并发的软件系统非常困难，因此一 互关系，着重体现对象之间消息传递的时间顺序，用于描述或 些缺陷经常被忽略，比如竞态条件()和时间冲突, 01234301 -./.实现用例中包含的执行场景。它只显示参与的对象，而不刻画 *+*#+!、非局部选择()等。这些设计错误中有许多 101560.-6 .703./对象间的关系或对象的属性。顺序图采用两维坐标:垂直轴表 都可以使用模型检验技术被检测出。模型检验是一种确保设计 示时间，水平轴表示不同的对象。顺序图中的对象用矩形框表 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 正确性的形式化自动验证技术，其实质是通过建立系统的 示，并标有对象名称和所属的类的名称。垂直虚线是对象的生 有穷状态模型，对这个模型的状态空间进行搜索，确定系统是 命线，表示在某一段时间内对象是存在的。对象间的消息传递 否满足期望的属性。模型检验在工业应用和协议分析中取得了 通过在对象的生命线之间画可视化消息来表示，消息的箭头指 巨大成功。 明了消息所属的类型。每一条消息至少标一个消息名。以“乘客 现在有许多 建模开发环境，比如:和 () 8-4301-6 809/ ’乘坐电梯”执行场景的顺序图为例，如图 所示:& ，但是这些工具提供的环境只包括建模及代码 (-:3.;,-< ()’乘 客 ()要 乘 坐 电 梯 ()时 ，首 先 由 电 梯 控 制 器 C99163D4-/:/,自动生成，还没有对模型进行形式化验证的功能。为了能在使 ()向电梯发送打开门命令，然后乘客进入电 63D4.014,065200,0C/1用 进行系统设计的过程中把验证工作结合进来，该文根 ) ’(梯 ， 电 梯 控 制 器 向 电 梯 发 送 关 闭 门 命 令 5C-99/1:/,/14/,5 据 和建模环境提供的软件模型信息，提出一种基于 ) =) ’((，电梯运行。电梯到达指定楼层后向电梯控制器 200,.609/5?0E/的 顺序图模型的自动验证方法。该方法把顺序图转化为 () ’发 送 到 达 消 息， 电 梯 控 制 器 向 电 梯 发 送 打 开 门 命 令5-,,3E-65 用建模语言 描述的模型，然后使用模型检验器 >,0?/6- @>AB ，乘客离开电梯。200,0C/15C-99/1:/,/F34 基金项目:国家自然科学基金项目(编号:Z%%H#"S&)资助 作者简介:王璐珍，硕士研究生，研究方向为形式化验证。董威，博士，研究方向为软件可靠性、软件测试。陈火旺，中国工程院院士，教授，研究方向 为软件工程、人工智能等。 行验证。从顺序图转化为 0AD7 程序以及用 -0NM 进行验证 的过程都是自动化的。 图 & “乘客乘坐电梯”顺序图 图 验证 顺序图的过程 ! ()’ 为了用于 () 顺序图模型的验证，文献*+,中对消息序列 ’#$& 模型检验器 -0NM 图的形式化描述，定义 顺序图 为一个六元组 ，，) - -0 ’(./(模型检验器 ()是贝尔实验 -0NM-;<=>? 0AD7 NFB?A=A?B?A，，，，其中:1-234 *9,():对象的有穷集合;，它支持分布式系统(如数据通信 &0 室开发的一种通用验证系统 ():消息的有穷集合。按照消息发 生 的 顺 序 为 消 息 排 !(协议、分布式操作系统、数据库系统等)的设计和验证，主要证 序，是一个有序集;中的进程都被认为是异步的，同步 -0NM 明进程交互的正确性。()消息类型函数 :，，把每一条消息映射为同步 #15678(! 要 显 式 声 明 。 中 需 要 验 证 的 性 质 用 线 性 时 态 逻 辑0NM -需表示同步，表示异步;6 7 消息或异步消息，(，)公式表示。该工具已经成功应用在 );F?A 3?<=DA7> )DG;@)3)()发送标记函数 :，每一条消息有一个发送者;+-(0 ! 许多通讯协议的验证中。()接收标记函数 :，每一条消息有一个接收者;920 (!在 中 ， 被 验 证 系 统 的 模 型 使 用 语 言 描 述 。0NM 0AD?>7 -< 数 示 ()动作类型函:，，，表3 56;<=>?@A?7B?C?6BADE8 :((!的语法类似 ，它允许并发进程的动态创建，是有穷状 0AD7 S中每一条消息的动作类型，其中调用、返回和发送动作都归为 )， @T7FF>?态系统建模的规范语言;消息的传递使用消息通道(类型。6;<=>? 程序由进程、消息通 0AD7 可以定义为同步通信或异步通信。例如，图 中描绘的顺序图可以通过元组，，，，，& 01-2 /(道和变量这三种对象组成。进程指明系统行为，通道和全局变 表 示 :，，;，3 4 0 5=766?FG?A>;H@BDFBAD>>;H8B CDDAD=?F& ../( ，，，，，=766?FG?A?FB?ACDDA@D>6?#D?+7AA;7>9CDDAD=?F 量定义这些进程运行的环境。!;H@BDFBAD> .-.2#$ 分析 ) 顺序图的 R) 文件 !’((();()等等。CDDAD=?F&>;HB3CDDAD=?F&6;=>? ..<为了让 模型能通过 迅速传播，达到充 U NFB?AF?B L)(’(一个简单的 顺序图仅仅描述一个场景，可以通过连 ()’分的软件设计共享，更进一步将 与 结合，这就是所 () R() ’*,:接、分支、循环等操作把顺序图组合在一起来描述多个场景。定 谓的 标准。(，元数据 RN RNR ?B7C7B7 NFB?A@T7FG?R ))(((((N3义组合型顺序图 是一个五元组 ，，，，，其中:L L./MIIOP4 交换)是一种允许在领先的开发工具之间完全共享模型的交换 M:图中结点的有穷集合;格式，它用来在不同的 建模工具之间或基于 (() (UO(?B7 ’N，是起始结点;IM " UVW?@B O7@;>;BE，元对象设施)的元数据仓库之间交换数据。该文3，是终止结点;IM "就采用基于 标准的 格式定义顺序图的外部表示形 RN R) ((标记函数 :把 中每一个结点映射为一个顺序图;OM 文件可以作为保存内部数据结构的统一格式，这样就 R() 式。，表示图中边的集合。PMQM #把对系统模型原始描述的分析过程与设计工具隔离开来，设计 从起始结点开始到终止结点结束的路径代表了由该组合 工具只需要负责生成 格式的模型文件。由于 的自解 R() R() 型顺序图模型描述的系统的有穷执行。目前只考虑了把简单顺 释性，可以很方便地读取和保存结构化的数据。序图通过连接操作得到的组合型顺序图转换为 程序。 0AD7 首先分析顺序图的 文件，找到与消息相关的各项信 *+,R ()。同步连接表示顺序图 的 (& 连接分为同步连接和异步连接息，包括消息名、消息发送者、消息接收者、消息类型、消息序号 所有事件都在顺序图 的事件之前发生，异步连接表示逐个 (! 等，然后建立前面定义的顺序图六元组。得到顺序图六元组以 对象地连接两个顺序图。这里采用异步连接的解释。 后，按照下面的算法生成顺序图的文本描述: 简单顺序图的文本格式如表 所示。& 顺序输入系统某条执行路径上所有简单顺序图的 文 R() 件，把转换得到的简单顺序图文本文件连接在一起得到组合型 顺序图的文本文件。组合型顺序图的文本文件中还可以包含对 条件、对象动作和并发执行事件的描述。如表 所示。! #$# 顺序图到 0AD7 程序的转换 组合 型 顺 序 图 与 之 间 的 元 素 映 射 关 系 可 以 简 单0AD7 # 顺序图的自动验证 ’() 该文提出使用 验证 顺序图的过程如图 所示。 -0NM ’() ! 首先由系统设计人员使用 顺序图为系统建模，精确’() 描述系统行为;然后使用转换规则将顺序图的 文件转化 R )( 为 程序;启动 进行验证，确定系统是否拥有期望 0AD7 -0NM 的属性。如果产生一个否定的结果，则同时会产生一个反例，方 件，其中 C/6B3&&-90(3 是 C/6B41C3 语句中定义的进程的名字， (); &//01234567386943&&03’()*+,-.-’(;:<6/(=)>;=?)&’(;=@@) 是 该 进 程 的 标 识 号 ，是 程 序 中 变 量 的 名 字 ， C=7 H0/=0GD3-90(3 是程序中的标记，需要引用的语句前面加上标记。 D0G3D-903 (A 01344(3&&03，B3&&03，=); *+,-//-2;/-;..:(:’(可以使用 检测系统是否会出现死锁，是否有竞态条件，以 MXL5 41C3B3&&03$41C3; )/-;’(及事件发生的顺序是否满足要求等。 =(<41C3&=CD3EE41C373&4/61) ))()) 4F39 G3;=9 ]实例分析41C3)&397; 从文献中给出的一个电梯实例出发，用顺序图反映对象 S^TB’/-/3B6/7)41C3@B’/-(3&&0;3$90(3; 397; 的动态协作过程如图 所示。] 3D&3 B//3B6/741C3@B/3&&03$/3B3=H3/; ’-)’-(;+-//01-77(B/-3&&0;3$&3973/，B/-/3B6/7); *,..:’(:’41C3)B/-3&&0;3$41C3; ’(=(<41C3 I)B/3043)4F39 G3;=9 =< 1C 34&=CD3 4F39 41C3/3B3=H3; ))()B/-/3B6/7 ) 41C3 @ B /-3&&0;3$903; ’’((0177(B3&&03$3B3=H3，B3B67); *+,-//-/-;///-//..:’(:’397; J 图 # 生成顺序图文本文件的算法 简单顺序图的文本格式表 > : 顺序图中所有对象依次排列&7-G671?KE=9&4-73< &7-G671 =9&4-73<:L5MN.58O =9&4-90(3;对象的定义 =9&4-G671 O5PL5MN.58O; =9&4-G671:?KE3H394 =9&4-G671 对象中所有事件依次排列 : 事件类型3H3943&&0;3-&397E3&&0;3-/3B3=H3EB697=46=9E(( B/3043-=9&4E43/(=9-=9&4E B6/3;=69E0B46=9E66DC 3&&03903:LPO5NLQLORELPO5NLQLORSC0/0D=&4T 消息的名字(;-((- :; 发送事件(3&&0;3-&397MO5P (3&&0;3-90(33&&0;3-/3B3=H3:RO8OLUO 3&&0;3-903; ((( 接收事件 :; 创建一个对象B/3043-=9&48RO.NO =9&490(3 :; 撤销一个对象43/(=9-=9&4POMNRVW (3&&0;3-90(3 表 组合型顺序图部分文本格式 ! B697=46=9:8V5PLNLV5 B697-903;(条件 0B46=9:.8NLV5 0B46=9-90(3;对象的局部动作 :; 并发执行的事件B63=69VRRON =9&4G671 OPVRRON/;858*5-5858*5 表 # 组合型顺序图与 X/63D0 语句的对应关系 ( 顺序图语言注释语句 X/6(3D0 MO5P 3&&03903 B3&&03903I3&&03903 消息的发送事件(;(-(;((;( RO8OLUO (3&&0;390(3 B-(3&&0;390(3Y(3&&0;390(3 单个的消息接收事件RO8OLUO (3&&0;390(3>; 76 ::B-3&&0;3903>Y3&&0;3903> ((((ROOLUO 3&&03903 8;!(( ::B-(3&&0;390(3!Y(3&&0;390(3! 连续的消息接收事件 $$$$$ $$$$$$ $ 67 图 ] 电梯系统中部分顺序图 () 创建一个对象 8RO.NO =9&490(3 /’9 =9&490(3 : 397B3&&03903Y3&&03903-(;((;(POMNRVW 3&&0;3903 撤销一个对象(( () 8697=46=9 X 0&&3/4X条件顺序输入图 中顺序图 =<40D、D644B0D D和 V4F3VC 的文 ] ,85/.对象的动作 B4=69 ZOZX ZOZX .))本文件，转换得到电梯系统的 程序如图 所示。X/6(3D0 _ 并发执行的事件MO5P (3&&0;390(3>EE 76 电梯门必须在乘客进入电梯之前打开，即在进程 中，消 D=<4 ::B-3&&0;3903>I3&&0;3903> (((( RO8OLUO 3&&03903 (;(!息 的 接 收 事 件 必 须 在 消 息 的 接 收 事 件 之 前 766/6C39> 3943/! ::B-(3&&0;390(3!Y(3&&0;390(3! 发生。使用 公式验证这一性质时，首先通过 语句把 ,N, ‘73<=93 67 需 要 引 用 的 事 件 定 义 为 公 式 中 的 命 题 符 号 :N 73<=93 ,,‘ 与 ，然 7666C39 D=<4 S#T7666C 73<=93 C0&&3943 D=<4 S#TC0&&39//‘/\\*+ 顺序图转化为 X/63D0 程序以后，调用 MXL5 模型 把 ,(后输入对应的 公式:()，启动 ,N, ST766/6C39aK?KC0&&3943/MXL5 检 验 器 对 模 型 进 行 验 证 。 使 用 的 预 定 义 格 式 X/63D0 (进行验证，验证结果如图 所示。b 来 引 用 进 程 中 变 量 的 值 ，使 C/6[ B3&&903SC=7TH$0/=0GD3903 -(-( 用 预 定 义 格 式 来 引 用 进 程 中 C6B3&&903 SC=7TD0G3D903 /-(-(\ 的 事 -,?:* ^_+9L,<.++D，-;I*!，.669I.+#，>;;6;:*/R，*/,*6&，>;;6<+;5*E，L;;+6‘ 结果指明该 1W1 公式不成立，同时给出了反例路径。 6*YF，-;I*’，.669I.+%，>;;6;:*/D"，:.55*/2*6*K9,DD a; <=./ ;;6;:*/R^L.+5*，[b*/,*6&^L.+5*，[b>;;6<+;5*E^L.+5*， [b-;I*’^L.+5*; 出了基于自动机理论对消息序列图进行模型检验的一些算法。 ;)，并给出对应的转 552 n+ 6=7*.*;3.:]列图转化为消息流图(::6Re>6RPg>6:b>6R,68 ;;;:*/;;;:*/;;;:[;;;:*/^*换规则，得到反映图中消息可视化顺序的 程序。该文 ::6<+5*Ee>6<+5*EPgb>6<+5*E^,68* ;;;;;;[;;;把 顺序图转换为模型检验器 的输入语言，将验证结 JBN q71 \::6R,68 b,6&,68b>6<+5E [;;;:*/^^*hh [*/*^^*hh[;;;*^^年 月)!""! D! 的方法。(收稿日期:,68*hhb*^^,68*)Pg6*M [-;I’[.;>; ;;6;:*/D"e>;;6;:*/D"; >+92 1282， T[*7./.**/;:T7T7q/*7;*/./.*-]]] J*<9L9<.,9;PI*659; D$R@JA=$,,:c c 333$;2$;62 c 8+ c ， ""DP"% ://:--! !$m Q+86 ，] 0 H ;+-U.// ，O B*+*>$Q/ ./.+?U*6 L;6 -*55.2* 5*Y8*/<* <=6,5@0AJ$L,6 C<,5 > W+5，D%%E;DF():FGFF .;3.*;/*:./;;!"图 & 电梯系统的部分 B6;-*+. 程序 #$H *PQ>++= ，J 1*8*$J?,<,9< >*,*<,9 L 6<*55 >9*62*<* (/[../.;/;:;I/692L6 $$ 6>8<,9 , +>9 ,=* 6 <+9 85, 5,8,,6P<+5> 3.//i;:;*;/;[*I./*I*.[**;*--.> ;P+;<.+ <=;9<* 9 *55.2* 5*Y8*<* <=.6,5@CA$N:B6;< ;L WQCQJ， ////-//**6 <+95 2**6,*> L6 1W1 L68+* 6* 5,8,,*6P<+5*>g j/I.-/.;-;-..;D%%F :./i.<<*:,./<* *:,= ERg R$m Q+86， MM95$>+ <= k///-: &$] 0 H;+-U.//$W=* -;>*+ <=**6 m*>8<,9;/ n8++ 5,,5< 56<= L6 .*:.**.;iX29**692，D%%F;#(&):F%G%& ///!!! /*I*6P<+.9- l E$Q T*69*3 , ,=* NP1 *,>, N,*6<=2* J*<9L9<,9@JA $/II;s7s77..././:.;/55*6,9 9+,95 9L 39,=9 5<* L <+9g .;/I;.;/l j/;:;.-=,,:c c <29$2$62 c *35 c 6%% c K9b*69*3$=,+$ :;-;/:-;II-.<<*:,./<* 95.[+*>g F$7 (*+.<=*3，m 4 J=?.-.58/>.6$7JCl:n6;- m*Y896*-*/, ,; B6;,;P 9+>9 *>5,,*5 P >95+*> ? **6P<+9g /I./.j.[[/I.-,?:*> J?5,*-5@CA$/ :NW=* D#,= X86;79<6; C;/L*6*/<* ;/ m*.+PW9-* J,.,*PI*<,;6 ’R [?,*o>*:,= 6*.<=*> ERo*66;65iD J?5,*-5，W*<=/9<.+ q/9I*659,? ;L O*+,L，O*+,L，W=* \*,=*6+./>5 E 5,.,*5o5,;6*>F I959,*>g !j!$J 1*8*，B 1.>M9$N+**,92 .> *69L?92 7JC J*<9L9<.,9;5 ’( /-:-///)/:/Di5,,*5o,<=*> .-.q592 B6;*+. c sJ9@CA$N:0PC 6*2;96*， H;+U.，O B*+*> /-://]]-//!’ ,6./59,9;/5j^I959,*>l-.,<=*>g *>5$ B6<**>925 L ,=* ONQCJ 6M5= JBN%E，,=* > ;/;7k;;:\!/.,;9< 5,*5 ! -:N,*6,9+ 6M5= ,=* JBN *69L9<,9 J?5,*$ONQCJ //.;/.k;;:;/ \).;/-7=5= g .;/i"*;I*jJ*69*5 );+8-* #!， Q-*69<./ 7.,=*-.,9<.+ J;<9*,?，B6;I9>*/<*，m$N，$.K 59U* pD 5,.,*5g j-!’D%%F D$R%# *6? 852* ?,*g --;.j7[ 图 E 1 W1 公式的证明结果 DD$09/289 H8./2，09./*6 C=*/，J;/2Y9.; C=*/$Q 59-:+* +/9*.6 ,9-* .:P (上接 &’ 页) $ *+,， 0 12*3*2，0 4 1*5,6$8+,96<*556 5<=*>8+92 39,= ’()-./(./.7:;;/:6;K9-.,9;/ .+2;69,=- L;6 -8+,9:6;<*55;6 Z;[ 5<=*>8+/92 ;/ L;86 :6;P ,= <;89<.,9; >*+.?5@0AB$.6.++*+ C;8,，D%%";DE:DF#GD --//-:’!<*55;65@CA$/ N:DDQ//8.+ N/,*6/.,9;/.+ J?-:;598- ;/ Q+2;69,=- ./> %$0 H;;2*I** ，J >* *+>* ， *+,.$C;+*K9,? ;L 5<=*>8+92 /I./ )()-/-:/C;-:8,.,9;/(NJQQCS""，W.9[*9)，1*<,86* ;,*5 9/ C;-:8,*6 J<9*/<*， \-8+,9:6;<*55;6 ,.5M5 39,= :6*5:*<9L9*> :6;<*55;6 .++;<.,9;/5@CA$/N:O95P D%E%，J692*6，:EGFD :/!"""" <6*,* Q+*9> ,=*,9<5 &&，D%%R:&%GF D$09*6 C=*，09289 H82$J*9P6+ J<=*>8+925:N6**, ::7.-.!!!!.///./-;-./-:;I-/;/\,= D $ B O*++ST+ J*6U ，V W8U $ XLL9<9* *LL*<,9**55 L "-;，7 :./.././I/;*5S Q+269,= @ C A $ N :D Q8+ N,*6,9+ J?598 ];-./;-/!//.//.;/.-:;-;/ Q+269,= > C8,,9(NJQQCSD，*3 U*+>)，1*<,86* ,*5 9;-./;-:.;/"../;/ \\6+ 5<=*>8+*5 ,=6** >*>9<,*> 6<*5565@CA$N:O95<6*,* 7,=*P /;-.;/ .:;;/. C8,*6 J<9*<*，#，J692*6，D:RGE ;-:/!!!:/!"""’,9<5，D%%F;DER:EFGF% -.