模型驱动的软件工程是一种以模型为核心的软件开发方法, 模型和模型转换是其核心成分.模型是对系统的一种抽象描述, 而模型转换则是将一种模型变换成另一种模型的特殊程序, 它推动了整个开发过程并实现了开发的自动化.

现有的工作大多都将研究重点放在了转换语言和算法上, 如讨论如何实现模型重构^{[1, 2]}、实现代码生成^{[3, 4]}和模型同步^{[5, 6]}等.这些研究增强了模型转换的处理能力, 使之能够实现许多复杂的操作.

当把模型转换技术运用到工业生产中时, 可伸缩性成为左右其成败的关键因素之一.在被开发 (或维护) 的系统比较复杂的情况下, 被转换的模型可能具有较大规模.如果转换程序不能快速地处理“大模型”, 那么这个开发 (或维护) 过程就可能失败.此外, 在大数据时代, 高效地处理“大模型”的能力也变得越来越重要.

例如, 在基于运行时模型的软件管理技术中, 模型同步 (即双向模型转换) 常常被用于实现系统状态和抽象管理视图之间的连接^[7].当系统状态发生改变时, 通过正向转换将其映射到管理视图上; 系统管理员在管理视图上进行系统调整, 并利用逆向转换将系统变化传播到运行时系统上.在这一过程中, 模型同步的执行效率至关重要.如果同步操作不能及时将系统状态转换成管理视图, 那么管理员则可能无法观测到系统最新的运行情况, 从而无法对系统进行正确调整.同理, 如果同步操作不能将管理视图上的变化及时传播到运行时系统上, 系统状态可能在转换过程中发生改变, 从而导致系统调整的错误和失败.

因此, 在应用模型转换之前, 应该对其性能进行系统化的测试.一方面, 可以明确转换程序的执行效率和极限, 从而确定其应用范围; 另一方面, 还可以进一步确定其中的性能瓶颈, 从而可以对其进行优化改进.为了进行性能测试, 一个关键问题在于如何有效地生成较大规模的输入数据, 即模型.模型生成需满足下面4个基本需求.

●  语法正确性:自动生成的模型需要符合语法约束;

●  高效性:生成模型的过程必须是高效的;

●  随机性:模型必须被随机生成, 以便衡量转换程序的平均执行时间;

●  可配置性:模型生成的过程必须是可配置的, 比如, 应允许用户限制模型元素的数量等等.

目前主要存在两种类型的自动化模型生成方法——基于求解器的方法和基于算法的方法.在基于求解器的方法中, 元模型和生成需求被编码成某种约束表达式, 如Object Constraint Language (OCL)^[8]表达式.之后, 这些约束表达式会被代入到一个约束求解器中进行求解.如果约束可解, 求解器会返回一个符合条件的模型.基于求解器的模型生成方法能够处理复杂的约束条件, 但其效率十分低下, 无法快速生成较大规模的模型, 因此不能很好地支持性能测试.基于算法的模型生成方法通常会使用某种算法生成模型, 这类方法能够随机、快速地生成模型.但大部分算法往往忽略了生成过程的可配置性以及一些基本语法约束, 这就导致它们生成的模型可能包含语法错误.

本文提出一种针对模型转换性能测试的模型生成算法, 该方法具有随机性和可配置性, 能够在合理的时间内生成正确的模型.在该方法中, 所有的模型元素及关系都将被随机生成.为了生成正确的模型, 该方法考虑了元模型中定义的全部语法约束和一部分语义约束.该方法还允许用户自定义约束来指导生成过程, 以便具有更好的可配置性.最后, 通过一组实验证明该方法能够正确、高效地生成较大规模的模型数据.本文的初步想法已经发表在COMPSAC 2014上^[9], 本文完善了方法描述, 并对方法进行了更多的实验评估.

本文方法的主要目标是生成规模较大、语法正确的模型, 但并不直接处理用OCL描述的语义约束.这样做有以下3个原因:(1) 不同于白盒测试, 用于性能测试的输入模型对于OCL语义约束的要求较低; (2) 在生成过程中处理OCL约束会极大地影响模型生成效率; (3) 对于某些转换程序而言, 如模型一致性修复程序, 不符合OCL约束的模型反而是有效的输入.本文方法可以看作模型生成的基线方法, 并可以结合其他技术构造满足复杂约束的模型:从理论上看, 只要能够快速地生成足够数量的随机模型, 一定可以从中选出符合OCL约束的结果; 从实践上看, 可以利用模型修复技术^[10]对随机生成的模型进行后处理, 使其符合OCL约束.

本文第1节介绍该算法支持的约束条件.第2节讨论该算法的技术细节.第3节对本文方法进行实验评估.第4节讨论相关的工作.最后是结论和未来工作.

1 模型生成的约束

在本文中, 模型生成是一个根据语法约束 (即元模型) 和用户选项 (配置参数) 生成模型的过程.语法约束和用户选项都可以看作是生成约束.然而, 与基于求解器的方法不同, 本方法并不会直接求解这些约束, 而是利用这些约束来指导模型的生成过程.首先讨论本文方法所支持的约束.

1.1 元模型与模型

不失一般性, 元模型M可以被形式化地定义为

$\mathbb{M} = \left( {T, H, A, R, C, assoc, mult, \prec } \right), $

其中,

●  T是一个由类 (class) 构成的集合, 其中, 每一个元素代表一个类型;

●  H是一个抽象类的集合, 且H⊂T;

●  A是一个由属性构成的集合, 其中, 每一个属于A的属性a可以被定义为一个标签函数a:t_c→d, a是属性的标识符, t_c∈T表示拥有该属性的类型, 而d表示一个基本数据类型;

●  R是由引用组成的集合, 其中, 每一个引用 (reference) 都代表两种类型的元素之间的一种关联;

●  C表示聚合引用, 且C⊆R;

●  assoc是一个函数, 其定义是assoc:R→T².它将每个关联r∈R映射到一个类型的有序对〈src, tar〉上, 指明了引用r的源和目标.如果assoc(r)=〈src, tar〉, 我们定义符号r.source≡src, r.target≡tar;

●  mult也是一个函数, 其定义是$mult:R \to N_0^2 \times N_0^2$.该函数用于刻画引用的多重性, 其中, N₀是指所有的非负整数, 包括+∞.对于每一个引用r∈R, 如果 (〈ls, us〉, 〈lt, ut〉)=mult(r), 则ls和us确定了源端多重性的下限和上限, 而lt和ut则确定了目标端多重性的下限和上限;

●  最后, ≺表示类型之间的继承关系, 它是一个定义在集合T上的偏序关系.如果c₁≺c₂, 则表示c₁是c₂的一个子类.此外, 本文还定义⊓_c≡{t|t≼c}, ⊔_c≡{c|c≼t}.

需要指出的是, 上述的定义是对OCL规范中对象模型定义的简化.不难验证, 该定义兼容图语法的类型图和Ecore (即meta object facility (MOF) 规范^[11]的工业实现).

一个符合元模型$\mathbb{M}$语法约束的模型M可以被定义为

$M = \left( {N, E, typ{e_N}, typ{e_E}} \right), $

其中, N是模型元素集合; E表示关系集合; type_N是一个函数type_N:N→T, 它将模型元素映射到对应的类型上; type_E也是一个函数type_E:E→R, 它将关系映射到引用上.

假设M=(N, E, type_N, type_E), 则本文定义:

●  对于每个元素e和类型t, e∈_tM⇔e∈N∧type_N(e)=t;

●  对于一个元素e和一个集合G, e∈_GM⇔e∈N∧type_N(e)∈G;

●  对于每个元素e∈_tM和属性a:t_c→d, 符号a(e) 返回属性a对于e的取值;

●  对于任意两个元素a和b以及一个引用r, 〈a, b〉∈_rM⇔〈a, b〉∈E∧type_E(〈a, b〉)=r.并且, 我们称〈a, b〉是一个“r-关系”.

●  对于任意两个元素a和b以及一个引用集合G, 〈a, b〉∈_GM⇔〈a, b〉∈E∧type_E(〈a, b〉)∈G.

此外, 在本文中,

$r\left( x \right) \equiv \left\{ {\left\langle {x, z} \right\rangle \left| {\left\langle {x, z} \right\rangle { \in _r}M} \right.} \right\}, {r^{-1}}\left( y \right) \equiv \left\{ {\left\langle {z, y} \right\rangle { \in _r}M} \right\}.$

1.2 语法约束

最基本的约束就是从元模型中推导出的语法约束.生成的模型必须满足所有的语法约束.对于一个模型M, 它所对应的元模型$\mathbb{M}$规定了以下3种类型的语法约束.

●  元素语法约束:对于任意在模型M中的元素e, 它的类型必须是定义在$\mathbb{M}$上的一个非抽象类;

●  属性语法约束:对于任意元素$e{ \in _{{ \sqcap _t}}}M$和它的属性a(即a:t_c→d), a(e) 的类型必须是d;

●  关系语法约束:对于任意在模型M中的关系〈a, b〉, 它的类型必须是元模型中的一个关联, 假设为r.此外, 还必须满足多重性条件, 即:对任意$a{ \in _{{ \sqcap _{r.source}}}}M$和$b{ \in _{{ \sqcap _{r.target}}}}M, $lt≤|r(a)|≤ut ∧ ls≤|r^-1(b)|≤us, 其中,

$\left( {\left\langle {ls, us} \right\rangle, \left\langle {lt, ut} \right\rangle } \right) = mult\left( r \right).$

1.3 引用上的语义约束

除了语法约束之外, 生成的模型还必须满足一些语义约束.语义约束多种多样, 涉及到模型所刻画的具体领域.本文只关注定义在引用上的4种基本的语义约束, 这4种基本的语义约束定义如下.

●  自反性:该约束决定了r-关系的源端和目标端是否可以是同一个模型元素 (在不考虑类型约束的情况下).更准确地说, 如果r是非自反的, 那么∀a(〈a, a〉∉_rM).在默认情况下, 所有引用都是自反的;

●  有序性:该约束决定了引用r是否是一个偏序.当r是有序的, 则对于任意〈e_n, e₀〉∉_rM, 一定不存在e₁, e₂, …, e_n-1, 使得$\mathop \wedge \limits_{0 \leqslant i < n} \langle {e_i}, {e_{i + 1}}\rangle { \in _r}M.$默认情况下, 引用都是无序的;

●  必要性:该约束决定了一个元素是否必须参与到一个r-关系中.它有两种具体的类型:源端必要性和目标端必要性.如果r是目标端必要的, 则∀a(|r(a)| > 0);如果r是源端必要的, 则∀b(|r^-1(b)| > 0).在默认情况下, 引用既不是源端必要的, 也不是目标端必要的;

●  唯一性:该约束决定了一个元素是否可以参与到多个r-关系中.它也具有两种具体的类型:源端唯一性和目标端唯一性.如果r是目标端唯一的, 则∀a(|r(a)|≤0);如果r是源端唯一的, 则∀b(|r^-1(b)|≤1).默认情况下, 引用既不是源端唯一的, 也不是目标端唯一的.

上面4种约束可以扩展到引用集合G上.

●  自反性:如果G是自反的 (或非自反的), 其中的每个引用都是自反的 (或非自反的);

●  有序性:如果G是有序的, 则对于任意〈e_n, e₀〉∉_GM, 一定不存在e₁, e₂, …, e_n-1, 使得$\mathop \wedge \limits_{0 \leqslant i < n} \langle {e_i}, {e_{i + 1}}\rangle { \in _G}M.$对任意两个元素e₀和e_n, ${{e}_{0}}{{<}_{G}}~{{e}_{n}}~\Leftrightarrow ~\exists {{e}_{1}}, {{e}_{2}}, ..., {{e}_{n-1}}(\underset{0\le i<n}{\mathop{\wedge }}\, \langle {{e}_{i}}, {{e}_{i+1}}\rangle {{\in }_{G}}M);$

●  必要性:若G是目标端必要的, 则有$\forall a\left( \sum\limits_{r\in G}{|r(a)|}>0 \right);$若G是源端必要的, 则有$\forall b\left( \sum\limits_{r\in G}{|{{r}^{-1}}(b)|}>0 \right);$

●  唯一性:若G是目标端唯一的, 则有$\forall a\left( \sum\limits_{r\in G}{|r(a)|}\le 1 \right);$若G是源端唯一的, 则有$\forall b\left( \sum\limits_{r\in G}{|{{r}^{-1}}(b)|}\le 1 \right).$

例如:表示继承的引用必须是非自反的和有序的; 所有的聚合引用所构成的集合是非自反、有序且源端唯一的; 通常, 聚合引用集合也必须是源端必要的, 这是因为每个元素 (根元素除外) 都必须有一个容器.

1.4 范围约束

如前所述, 本文提出的生成算法具有一定的可配置性.其可配置性体现在本文方法允许定义一些私有的范围约束来限制生成的模型, 范围约束包括元素范围约束、关系范围约束和值范围约束.

对于在元模型中定义的一个类型, 它的元素范围约束 (ERC) 规定了在最终生成的模型中可以存在多少个该类型的元素, 每一个类型只能拥有一个ERC.同时, 我们还可以定义全局元素范围约束 (GERC) 用来限制模型中元素的总数量.ERC/GERC都是一个整数类型的界 (bound), 界的定义将在下面介绍.

类似于ERC, 对于元模型中的每一个引用, 我们可以为其定义一个关系范围约束 (RRC).RRC限制了模型中某种类型关系的数量, RRC也是一个整数类型的界.

此外, 对于每一个属性, 我们还可以定义一个值范围约束 (VRC), 值范围约束用来限制该属性可能的取值.每个VRC都是某种基本数据类型 (属性的类型) 的界.

某种数据类型d的界B_d可以被定义为

${{B}_{d}}\subseteq {{V}_{d}}\times P$

(1)

其中, V_d是类型d所有的可能取值; P是一个概率集合, P中的每一个元素都是一个从0到1的实数.一个合法的界必须满足以下两点:

$\sum\limits_{(v, p)\in {{B}_{d}}}{p}=1且\forall {{b}_{1}}, {{b}_{2}}\in {{B}_{d}}({{b}_{1}}\ne {{b}_{2}}\to {{v}_{1}}\ne {{v}_{2}}), $

其中, b₁=(v₁, p₁), b₂=(v₂, p₂).每个属于B_d的〈v, p〉的含义是“从{v|〈v, p〉∈B_d}中选择v的概率为p".

范围约束可以用来控制生成模型中各种类型的元素和关系的出现数量以及不同属性值的出现频率, 从一个侧面保证生成模型的多样性和各种元模型要素的覆盖率.例如, 要让模型中包含30%的A元素和40%的B元素, 则可设定A, B元素的ERC分别为0.3S和0.4S, 其中, S为模型中元素数量总和.如果希望A元素中某个布尔类型的属性a取值分布为“70%为true, 30%为false”, 则可设置a的VRC为{〈true, 0.7〉, 〈false, 0.3〉}.

2 生成算法 2.1 方法概览

本文的方法可以表示为图 1所示的流程, 其中包含4个主要步骤.

第1个阶段是配置生成参数.在这个过程中, 需要建立一个配置模型, 其中包含语义约束和用户自定义约束.用户自定义约束包括范围约束和额外约束.配置模型和元模型将被用于指导模型的生成;

第2个阶段是元素和属性的生成.基于语法和范围约束, 本方法可以创建模型元素并设置该模型元素的属性值;

第3个阶段是生成所有的关系, 它包含3个子步骤:(1) 实例化聚合引用 (这些引用构成的集合是有序的、非自反的、源端必要且源端唯一的); (2) 根据配置模型定义的语义约束和范围约束, 实例化被配置模型约束的引用; (3) 实例化普通类型的引用.尽管我们把关系生成过程分解为3个子步骤, 但它们都使用了同样的算法实现, 通过输入不同的参数来控制不同类型的关系生成;

最后一个阶段是验证阶段.所有的用户定义的额外约束都会在这个阶段被检查, 因为我们在模型生成过程并没有求解这些约束.如果生成的模型满足了这些约束, 本方法将返回该模型; 否则将返回一个空模型, 并报告错误.

2.2 配置生成过程

本节将讨论如何利用配置模型来配置模型生成过程.我们首先利用MOF来定义配置模型语法, 如图 2所示.

类ConfigurationModel表示一个配置, 它指向一个Class, 表示了生成的模型中可以作为根元素的类型.它的属性uniqueRoot表示生成模型是否有唯一的根元素.一个配置模型ConfigurationModel可以包含4种类型的约束:ElementRangeConstraint, RelationshipConstraint, GlobalRangeConstraint和ExtraConstraint.

一个ElementRangeConstraint对应一个ERC.关系class表示该约束所限制的类型.需要注意的是:该约束限制了用指定类型创建的元素数量, 而不包括用其子类创建的元素数量.每个ElementRangeConstraint还可能包含一组AttributeRangeConstraint, 一个AttributeRangeConstraint表示一个VRC.关系attribute指明了被约束的属性.类RelationshipConstraint则被用于限制关系的生成过程, 它结合了语义约束和关系范围约束.需要说明的是:聚合关系不能使用RelationshipConstraint进行显式约束, 因为本文算法会自动处理聚合引用.

一个GlobalRangeConstraint可以用来规定范围的默认值, 包括模型元素的总数 (total size)、默认的元素范围 (default element range)、默认的关系范围 (default relationship range) 以及默认的值范围 (default value range).模型元素的总数 (total size) 刻画了生成的模型中元素的总个数.默认的元素范围 (default element range) 刻画了任意类型的实例数量.如果不存在针对某类型的ElementRangeConstraint, 这个默认值将被使用.默认的关系范围和默认的值范围与此类似.

ExtraConstraint表示任何在本文中没有被讨论的约束, 它们必须被写成OCL表达式的形式.出于生成效率的考虑, 本文的方法不能求解这些约束, 只是用它们验证生成的模型.

ElementRangeConstraint, AttributeRangeConstraint, RelationshipConstraint, GlobalRangeConstraint都是Bound的子类, Bound表示一个界, 它可以表示成文字形式, 其语法必须符合下面的定义.

bound::=bList

item::=bItem|pbItem

pbItem::=bItem ‘:’probability

bItem::=bList|bRange|literal

bList::=‘{’bList‘, ’item‘}’

        |‘{’item‘}’

bRange::=‘[’literal‘..’literal‘]’

literal表示常量

probability表示一个从0到1的实数

其中, bList表示可能取值的列表, bRange表示一个有上界和下界定义的范围.bItem表示一个没有明确定义概率的项, 可以是一个具体值、一个列表或一个范围, 其概率可以由其他项推导出来.

用这种形式定义的界可以很容易地被转换成公式 (1) 所定义的逻辑形式.例如, {3, 5:0.2, [7..9]:0.3}可以被转换成{〈3, 0.5〉, 〈5, 0.2〉, 〈7, 0.1〉, 〈8, 0.1〉, 〈9, 0.1〉}.

2.3 生成元素和属性

第2阶段是生成模型中的元素和属性值.简单地说, 对于元模型$\mathbb{M}$中的每个非抽象类t, 创建s_t个元素; 其中, s_t表示t元素的数量.基本的元素和属性生成算法可以写成算法1的形式.

算法1. Generate elements and attribute values.

1:    for all t∈T-H do //t为元模型中的非抽象类

2:       s_t←需要生成的t-元素数量

3:       for i=1 to s_t do

4:         e←创建一个t-元素

5:        将e加入到模型中

6:         for all a:t→t_d∈A do

7:           v←根据a的范围约束中规定的取值范围和概率所生成的值

8:           a(e)←v

9:         end for

10:       end for

11:    end for

算法1的基本流程并不复杂, 但困难的是为每个类t确定对应的s_t.如果s_t没有被正确赋值, 那么就可能无法生成合法模型.这是因为元模型和配置模型在生成的模型上强加了如下约束.

●  首先, 令${{S}_{t}}=\sum\limits_{o\in {{\sqcap }_{t}}}{{{s}_{o}}}$;

●  其次, 对于每一个类, 其实例数量由所有可能容器元素数量的取值决定.先定义引用之间的等价关系~, 即r1~r2⇔⊓_r1.target∩⊓_r2.target≠∅∨∃r3(r1~r3∧r3~r2).利用这一等价关系, 我们可以将聚合引用集合C划分成若干等价类C₁, ..., C_n.那么对每个等价类C_i, 都需要满足下面的约束条件:

$\sum\limits_{r\in {{C}_{i}}}{(l{{t}_{r}}\times {{S}_{r.source}})}\le \sum\limits_{c\in C{{C}_{i}}}{{{s}_{c}}}\le \sum\limits_{r\in {{C}_{i}}}{(u{{t}_{r}}\times {{S}_{r.source}})}, $

其中, 对引用任意r假设有 (〈ls_r, us_r , 〈lt_r, ut_r〉)=mult(r), 且CC_i={c|r∈C_i∧c∈⊓_r.target};

●  第三, 任意两个类s和t, S_s和S_t同时还被非聚合引用r的多重性所约束, 其中, 〈s, t〉=assoc(r) 且 (〈ls, us〉, 〈lt, ut〉)=mult(r), 则有ut×S_s≥ls×S_t∧us×S_t≥S_s;

●  第四, 对于每一个类t和S_t的取值必须属于range_t, 其中, range_t表示由ElementRangeConstraint或default element range所确定的界;

●  最后, 如果定义了total size约束, 则所有S_t的和必须符合该约束.

在获得这些约束后, 我们可以利用一个约束求解器去求解这些范围约束, 并获得一个随机解, 以此来确定每一个类t所对应的s_t的取值.

2.4 生成关系

第3个阶段是生成模型M的关系, 这个过程可以表述为算法2.这种算法包含3个子过程:生成聚合关系 (第1行)、生成受约束关系 (第2行~第4行)、生成普通关系 (第5行).所有这3个子过程都基于配置模型中定义的语义和范围约束.

算法2. Entry of relationship generation.

1:    生成聚合关系

2:    for all RelationshipConstraint c do

3:      生成受c约束的关系 (即, 类型属于c.references的关系)

4:    end for

5:    产生其他关系

首先, 我们讨论聚合关系的生成.如之前所述, 所有的聚合关系都是非自反的、有序的、源端唯一的、源端必要的 (除了根元素).所以, 对于所有的聚合引用, 我们都可以在算法3中进行处理.parents是所有可能的容器元素集合, children是所有子元素集合.注意, 这两个集合可能相交.第4行收集所有可能的根元素 (即possibleRoots).第5行~第7行计算根元素的数量 (即numberOfRoot), 这一步是基于uniqueRoot的值进行计算的.第8行~第11行从possibleRoots中随机选择numberOfRoot个元素作为根元素, 并将其从children集合中移除, 因为根元素不需要容器.实际的生成过程是通过调用GenerateRelationships (第13行) 实现的, 其中, 根据聚合关系的语义设置了参数.算法GenerateRelationships稍后再进行讨论.

算法3. Generate containment relationships.

1:    N←模型M的元素集合

2:    parents←N

3:    RC←配置模型中指定的根元素类型

4:    possibleRoots←{e|e∈N∧∃t(t∈RC∧type_E(e)≼t)}

5:    if config.uniqueRoot=true then numberOfRoot←1

6:    else numberOfRoot←1到|possibleRoots|中的随机整数

7:    end if

8:    roots←从possibleRoots中随机选择的numberOfRoot个元素

9:    children←N-roots

10:    size←|children|

11:    GenerateRelationships(C, parents, children, true, true, false, false, false, true, size)

接下来生成被RelationshipConstraint所约束的引用.由于RelationshipConstraint刻画了一组引用集合的语义和范围约束, 简单地从中抽取相应的信息并将其作为GenerateRelationships的实际参数.这个过程如算法4所示.对于给定的一个RelationshipConstraint, 收集可能的源和目标元素 (第3行和第4行), 随机生成需要生成的关系数量 (第5行).与算法3类似, 调用GenerateRelationships使用提取的参数生成关系 (第6行).

算法4. GenerateConstrainedRelationships(rc).

Input: rc是一个RelationshipConstraint;

1:    N←模型M的元素集合

2:    S←rc.references

3:    src←{e|e∈N∧∃r(r∈S∧type_E(e) ≼r.source)}

4:    tar←{e|e∈N∧∃r(r∈S∧type_E(e) ≼r.target)}

5:    size←根据rc中规定的关系范围约束随机选择的整数

6:    GenerateReferences(S, src, tar, rc.sourceUnique, rc.sourceNecessary, rc.targetUnique, rc.targetNecessary, rc.reflexive, rc.ordered, size)

在第3个子阶段, 根据默认的语义生成剩余的关系, 如算法5所示.

算法5. Generate reminder relationships.

1:    N←模型M的元素集合

2:    for all未生成的引用r do

3:       src← {e|e∈N∧type_E(e) ≼r.source}

4:       tar← {e|e∈N∧type_E(e) ≼r.target}

5:       size← 根据全局关系范围约束所选择的整数值 (如果约束存在), 或随机整数 (如果约束不存在)

6:       GeneratedReferences(S, src, tar, false, false, false, false, true, false, size)

7:    end for

如前所述, 核心的生成逻辑是由GenerateRelationships实现的.算法GenerateRelationships的基本思想可以表述为:(1) 随机选择一个引用r; (2) 从集合N中随机选择一个源端元素e_s和一个目标端元素e_t; (3) 建立一个r-关系〈e_s, e_t〉, 并插入到模型M中.然而在这个基本过程中, 我们必须处理如下两个问题:(1) 如何根据定义在r上的各种约束条件正确选择e_s和e_t?(2) 如果无法选择到合适的e_s和e_t, 如何进行处理?

在继续之前, 我们首先定义两个辅助函数IsForbidden和IsCandidate.IsForbidden用于检查两个元素e_s和e_t, 是否可以建立一个r-关系而不违反自反性和有序性约束 (见算法6).IsCandidate用于检查元素是否可以成为r-关系的源端或目标端而不会违反多重性的上界以及必要性和唯一性约束.

算法6. IsForbidden(S, e_s, e_t, reflexive, ordered).

Input:引用集合S, 两个模型元素e_s和e_t, 自反性和有序性约束reflexive及ordered;

Output:当创建关系〈e_s, e_t〉后, 自反性和有序性约束reflexive及ordered是否会被违反.

1:    ifreflexive=false and e_s=e_t then return true //检查自反性

2:    else if ordered=true and e_t < _Se_s and then return true //检查有序性

3:    else return false end if

算法IsCandidate有两个版本, 即IsSrcCandidate和IsTarCandidate.算法7展示了IsSrcCandidate, 它用来判断元素e是否可以用作r-关系的源端.如果e满足了多重性的下界并且还有其他不满足下界的元素e_t存在, 则e不能作为r-关系的源端 (第3行、第5行、第6行).这是因为算法赋予不满足下界的元素更高的优先级用来创建新关系, 这是为了保证所有的元素都能满足下界.算法IsTarCandidate与之类似, 只是它使用$\sum\limits_{r\in S}{|{{r}^{-1}}(o)|}$, r^-1(o), ls_r和us_r代替了$\sum\limits_{r\in S}{|r(o)|}$, r(o), lt_r和ut_r进行判断.

算法7. IsSrcCandidate(S, r, e, unique, necessary).

Input:引用集合S, 引用r, 被检查的元素e, 必要性和唯一性约束necessary及unique;

Output:元素e是否可以作为一个r-relationship的源点.

1:    (〈ls_r, us_r〉, 〈lt_r, ut_r )← mult(r)

2:    U←{所有候选元素} //每个候选元素都不违反上界和语义约束, 并且都是有效的

3:    ${{C}_{L}}\leftarrow \left\{ o|o\in U\wedge \left( \left( unique\to \sum\limits_{r\in S}{|r(o)|}=0 \right)\wedge \left( (r(o)<l{{t}_{r}})\vee \left( necessary\wedge \sum\limits_{r\in S}{|r(o)|}=0 \right) \right) \right) \right\}$

4:    ${{C}_{U}}\leftarrow \left\{ o|o\in U\wedge \neg unique\wedge l{{t}_{r}}\le \sum\limits_{r\in S}{|r(o)|}\le u{{t}_{r}}\wedge \neg \left( necessary\wedge \sum\limits_{r\in S}{|r(o)|}=0 \right) \right\}$

5:    if C_L≠∅ then return C_L中是否包含e

6:    else if C_U≠∅ then return C_U中是否包含e

7:    else return false end if

现在讨论GenerateRelationships的细节, 它可以描述为算法8.

算法8. GenerateReferences(S, src, tar, srcUnique, srcNecessary, tarUnique, tarNecessary, reflexive, ordered, size).

Input:引用集合S, 源端元素集合src, 目标端元素集合tar, 语义约束srcUnique, srcNecessary, tarUnique, tarNecessary, reflexive, ordered, 待生成的关系数量size;

1:    G←S

2:    R←模型M的关系集合

3:    repeat

4:       if G=∅ then abort end if

5:       r←从G随机选择的引用, 且满足

$\forall e\left( lt\le \left| r\left( e \right) \right|\wedge l{{s}_{r}}\le \left| {{r}^{-1}}\left( e \right) \right| \right)\to \neg \exists {r}'\exists e\left( \left| {r}'\left( e \right) \right| < l{{t}_{{{r}'}}}\vee \left| {{{{r}'}}^{-1}}\left( e \right) \right| < l{{t}_{{{s}'}}} \right)$

6:       e_s, e_t←从src和tar中随机选择的两个元素, 且满足:IsSrcCandidate(r, e_s, tarUnique, tarNecessary)∧IsTarCandidate(r,e_t,srcUnique,srcNecessary)∧¬IsForbidden(S,e_s,e_t,reflexive,ordered )

7:       if这样的e_s和e_t存在then R←R∪ {〈e_s, e_t〉}

8:       else if只有e_s存在then

9:        寻找四元组〈r’, x, y, z〉, 且满足:(1) 〈x, y〉∈_r’M; (2) 删除关系〈x, y〉后, 〈x, z〉和〈e_s, y〉都是合法的r’-关系和r-关系, 即, IsForbidden(S, x, z, reflexive, ordered) 和IsForbidden(S, e_s, y, reflexive, ordered) 都是false且z的多重性上界依然满足

10:         if如果四元组存在then R←R-{〈x, y〉}∪ {〈x, z〉, 〈e_s, y〉}

11:         else将e_s标记为r的无效源端候选元素

12:         end if

13:       else if只有e_t存在then

14:        寻找四元组〈r’, x, y, z〉, 且满足:(1) 〈x, y〉∈_r’M; (2) 删除关系〈x, y〉后, 〈z, y〉和〈x, e_t〉都是合法的r’-关系和r-关系

15:         if如果四元组存在then R←R-{〈x, y〉}∪ {〈z, y〉, 〈x, e_t〉}

16:         else将e_t标记为r的无效目标端候选元素

17:         end if

18:       else G←G-{r}

19:       end if

20:    until src和tar中的所有元素都满足多重性下界and (所有元素都达到多重性上界or已经产生了size个关系)

算法会不断生成新的关系, 直到终止条件满足.在生成一个新关系时, 它首先尝试选择两个模型元素来建立一个合法的r-关系 (第6行、第7行).在这个过程中, 它会调用算法6和算法7来选择恰当的元素.这种选择策略能够保证多重性下限的约束被满足.例如, 图 3(a)展示了一个包含两个类A和B以及一个从A到B的聚合关系r的元模型.该元模型要求每个A元素至少关联一个B元素.如图 3(b)所示, 这是一个包含两个A和两个B的中间结果.模型中已经存在了一个r-关系〈e₁, e₃〉, 现在我们尝试去创建第2个关系.按照算法第6行, 只有e₂和e₄能够被选择成为新关系的源和目标.否则, 如果选择e₁和e₄来创建关系, 将得到一个错误的结果, 因为没有其他的B元素可以与e₂关联, 其多重性约束就会被破坏.

如果只能找到源端元素e_s(即, 此时不存在任何e_t能够满足第6行的条件), 则算法会尝试“修补”模型.修补模型是通过删除一个已经存在的关系并加入两个新关系来实现的, 整个过程不会违反任何多重性、范围约束和语义约束 (第9行、第10行).如果模型无法通过修补过程来增加新的关系, 则将e_s标记为r的无效源端 (第11行), 以后再创建r-关系时, e_s不会再被选择.如果只能找到目标端元素e_t, 处理方式与之类似 (第14行~第17行).修复过程是希望通过调整现有模型中的一个关系来向模型增加新的关系.例如, 如图 4(a)所示的元模型, 其中定义了3个类和2个聚合关系.元模型要求A元素必须关联一个B元素和一个C元素.图 4(b)展示了一个中间结果, 其中包含3个元素和1个r-关系〈e₁, e₃〉.现在我们尝试添加一个r’-关系.然而, 由于类型的限制, e₂不能参与到这样一个关系中 (用虚线表示).那么根据修复逻辑, 我们可以删除〈e₁, e₃〉, 然后向模型中添加新的r-关系〈e₁, e₂〉和一个新的r’-关系〈e₁, e₃〉, 最终结果如图 4(c)所示.

如果不能为r找到任何源端和目标端, 就将r从集合G中删除 (第18行).

这个算法的终止条件是下面两个条件之一:(1) G是空集; (2) 在所有元素都达到多重性下界的情况下, 所有元素都达到了多重性的上界 (不能再生成任何关系了) 或者已经生成了size个关系.该算法一定会终止, 因为在每一个循环中, 我们至少创建了一个新关系, 删除了一个候选元素, 或者删除了一个候选引用.因此, 终止条件一定会被满足.

2.5 约束验证

最后一个步骤是对生成的模型进行约束验证, 此阶段会对所有的语法、语义和用户定义的约束进行检查.如果生成的模型违反了任何约束, 生成的模型将会被拒绝, 并且报告给用户一个错误的信息.由于我们的方法能够保证语法和语义约束不被破坏 (我们会在后续进行讨论), 最后可能被破坏的约束就是用户定义的约束了, 特别是复杂的额外约束.但是由于我们的方法主要用于实现黑盒测试和性能测试, 这种情况并不多见.所以, 绝大多数情况下, 我们的方法都能生成一个有效的输出.

2.6 讨论

1) 复杂性

该算法的复杂度是多项式的.假设基于元模型M=(T, H, A, R, C, assoc, mult, ≺) 生成一个模型M=(N, E, type_N, type_E).容易得出:生成元素和属性 (算法1) 的复杂度是O(|N|×|A|), 生成关系的复杂度是O(|E|+|N|×|R|)×(O(|E|)× O(|N|³)).这是因为:(1) 算法8的循环体最多被执行的次数是O(|E|+|N|×|R|); (2) 算法6的复杂度是O(|N|²); (3) 选择两个候选元素 (算法8的第6行) 的复杂度是O(|N|×|N|²); (4) 寻找〈r’, x, y, z〉(算法8的第10行和第17行) 的复杂度是O(|E|×|N|×|N|²)=O(|E|)×O(|N|³).在实现中, 采用了缓存机制来减小时间开销.

2) 正确性

当不存在冲突的时候, 我们的方法能够生成一个符合语法约束、语义约束和范围约束的模型.严格地证明这一点是很复杂的, 我们只能定性地讨论一下.

●  首先, 我们的方法基于元模型生成元素、属性和关系, 因此, 生成的模型满足语法约束 (多重性约束在后面进行讨论);

●  其次, 当生成关系时, 我们的方法依然把语义约束考虑在内.在算法8的第6行, 被选择的用于生成新关系的元素必须满足4种语义约束.并不难证明, 修补过程 (算法8中第8行~第12行及第13行~第17行) 也不会违反任何语义约束.这是因为在追加一个新的关系之前, 我们调用了IsForbidden和IsCandidate函数检查语义约束;

●  最后, 算法1和算法8只有当所有的范围约束都满足时才会终止.

本文的方法能够保证生成所需数量的元素, 但并不保证一定会创建用户要求数量的关系.如果用户规定的数量过小或者过大, 或者其他约束之间存在冲突时, 算法所生成的关系数量都可能不符合用户的要求.在后续工作中, 我们将研究如何消解生成过程中发现的约束冲突.

值得注意的是, 在执行修补的过程中将不会违反任何范围约束.假设我们发现了〈r’, x, y, z〉, 如果y的度 (即|r’^-1(y)|) 在〈x, y〉被移除后违反了它的下界, y在后面就需要与其他的x’关联.这等同于在没有任何删减的情况下直接关联e_s和y.

3) 随机性和元模型覆盖率

本文提出的算法是随机算法, 因为其中所有选择操作都是随机的, 比如在创建关系时, 选择何种类型的关系进行创建、在哪两个元素之间进行创建都是随机决定的, 因此算法所生成的模型也是随机的.这最大限度地减小了利用相同配置所生成的多个模型之间的相似性, 保证了数据的多样性.

此外, 由于支持范围约束, 本文方法还能保证不同类型的元素和关系以及不同属性值的出现数量和频率.

●  一方面, 可以利用元素范围约束和关系范围约束规定每种类型的元素和关系出现的上下界.算法能够根据这个上下界, 在模型中生成特定数量的元素和关系 (在没有冲突的情况下);

●  另一方面, 利用值范围约束可以规定某个属性的不同取值的出现频率.

这都可以保证元模型中关键要素的覆盖率.

4) OCL约束

本文算法生成的模型能够符合元模型所规定的语法约束和一部分基本语义约束, 但对于复杂的语义约束不能直接处理.如前所述, 这样做的原因有3个:(1) 不同于白盒测试, 性能测试中对于OCL约束的使用相对较少, 输入数据的规模更加重要; (2) 在生成模型时考虑OCL约束将极大地影响生成效率, 不利于构造大模型;

(3) 对于某些模型转换, 违反OCL约束的模型可能才是有效的输入.正因如此, 虽然忽略了OCL约束, 但本文方法依然能够在一定程度上满足模型转换性能测试的需要.

实际上, 本文方法可以用作生成大规模输入模型的基础方法——在此基础上进行扩展, 可以构造出符合复杂OCL约束的模型.理论上, 只要用本文方法构造出足够数量的随机模型, 再利用OCL约束进行筛选, 则可以从中选择出满足条件的模型.实践中, 可以设计出相应的约束修复程序, 在生成的模型中寻找并修复不符合约束的地方, 从而将随机模型修正为符合OCL约束的输入模型.这些扩展技术将是本文下一步的工作.

3 评估

本节首先用一个例子展示如何利用本文的方法生成模型, 并对模型转换的性能进行测试.之后, 通过一个实验评估本文方法的随机性, 并利用两个实验检验本文方法的效率.

为了检验本文方法的效率, 我们进行了两个实验.在第1个实验中, 我们比较了EMFtoCSP^[12], Alloy^[13]和本文方法的执行效率.EMFtoCSP和Alloy都是目前最好的模型约束求解器, 有很多研究工作都是基于它们来实现测试输入生成^{[14, 15]}.在第2个实验中, 我们检验了本文方法生成大模型时的效率.两个实验的执行环境都是:一台配有Intel i7 4770 CPU, 16GB DDR3内存, Windows 7的电脑.本文并没有与其他基于算法的方法进行比较, 这些方法的局限性已在文献[16]中被充分地讨论过, 本文也会在第4节展开, 进一步加以讨论.

3.1 应用举例

在之前发表的会议论文^[9]中, 展示了一个用本文方法对ATL转换JavaSource2Table进行性能测试的例子.

本文从ATL转换数据库 (http://www.eclipse.org/atl/atlTransformations/) 选择了另一个开源转换程序MySQL2KM3, 用本文方法对其进行性能测试.MySQL2KM3能够将基于MySQL的关系数据库模型转换成KM3模型.MySQL元模型如图 5所示.

为了产生输入模型, 首先根据第2.2节定义的配置元模型建立模型生成的配置模型, 定义每种类型的元素和关系的生成数量以及每种属性的取值范围.为了避免产生过多的主键, 将Column元素isPrimaryKey属性的取值设定为10%的概率为true, 90%的概率为false.又通过对MySQL2KM3的源码分析发现:Column元素的type属性如果取值是tinyint, int, float, double, varchar, enum, 则可以触发相应的转换规则; 反之, 则不能触发转换规则.为了保证对应规则都被触发, 同时模拟无效输入, 在配置模型中规定, type属性只能从上述字面值和blob (代表无效输入) 中随机选取.同时, EnumColumn代表枚举类型, 其type属性显然必须取值为enum.因此在配置模型中, 规定EnumColumn的type属性必须取值为enum, 即, 覆盖了上一条针对type属性的范围约束.最后, 由于转换中没有一条规则处理IntegerColumn, 因此将其数量设置为0.

根据配置模型, 生成了10组输入模型, 每组输入模型包含5个模型.第1组模型包含500个模型元素, 之后, 每组模型中元素数量等比例地增加, 直到第10组模型包括5 000个模型元素.整个生成过程在10分钟内完成.依次将这50个模型作为转换MySQL2KM3的输入, 执行转换获得执行时间, 并针对每组输入求平均值, 最终获得的结果见表 1.可以看出, 本文方法能够很好地支持对模型转换进行性能测试.

我们在进行性能测试的过程中还发现, MySQL2KM3并不是一个全函数.针对某些满足特定条件的Table元素无法进行转换, 从而导致执行过程中产生警告信息 (但并不影响执行时间和结果).这是因为, 在MySQL2KM3中存在3条规则用于转换Table元素, 每条规则规定了一种前置条件.当Table元素不满足这3个前置条件但又被要求进行转换时, ATL引擎就会发出警告, 因为没有规则能够处理这样的Table元素.设计良好的转换程序应该能够避免这种警告的产生, 例如, 在要求转换Table元素之前先判断是否能够进行转换:如果不能转换, 则应该使用默认值 (如null); 反之, 则调用转换规则并使用转换结果.这说明, 本文方法还能被应用于黑盒测试的场景, 并发现转换程序中存在的缺陷.如何利用本文方法支持对模型转换的正确性进行黑盒测试, 也是本文未来的工作之一.

3.2 实验1:随机性

本文方法是一种随机方法, 同样的配置下能够产生一组具有多样性的模型, 从而可以用于计算转换程序的平均执行时间.为了评估本文方法产生模型的随机性, 利用第3.1节中产生的50个模型计算它们之间的相似性.将每一组的5个模型进行两两比较, 并获得每组模型的平均相似度.相似度的计算公式如下:

$\frac{匹配的元素数}{全部的元素数}$

本文利用模型比较工具EMF Compare (https://www.eclipse.org/emf/compare/) 计算两个模型中的匹配元素.为了避免任何主观偏向, 本文采用默认配置进行模型比较, 最后统计匹配元素数量并计算相似度.对于每组模型的平均相似度见表 2.

从表 2中可以看出:针对MySQL元模型, 本文方法产生的每组模型的平均相似度可以控制在26%以下.即:按照EMF Compare进行计算, 任意两个同组模型之间至多有26%的元素是相似的.通过检查这些相似元素可以发现, 主要是Column元素和EnumColumn元素之间存在较多的匹配元素.由于EMF Compare判断两个元素是否相似的默认策略是计算元素属性之间的编辑距离, 而Column/EnumColumn元素包含较多的属性且存在多个布尔类型属性, 这就导致两个Column元素之间存在较大的相似机率.模型元素数量越多, 匹配的Column元素也就越多, 因此相似度在不断增加.根据函数拟合的结果, 当模型元素达到10⁶时, 模型相似度达到50%(即, 大约为Column元素所占比例).需要指出的是:这种类型的相似元素是不可避免的, 但对于计算转换程序的平均执行开销并无负面影响.

3.3 实验2:执行效率比较

首先, 我们从ATL转换数据库中任选了两个元模型JavaSource和PetriNet用于测试.其中, JavaSource是一个简单Java源文件元模型, PetriNet则是一个Petri网元模型.

然后, 被测试的3种方法都要被要求根据JavaSource元模型和相同的参数生成同样大小的模型.生成过程没有设置额外的约束条件.我们用每种方法生成10个模型, 第1个模型有150个模型元素, 第2个模型具有300个元素等 (按此规律线性增长).每个模型生成5次, 以便获取平均执行时间.实验结果见表 3.

表 3中的每个单元都展示了一种方法 (行) 在生成一个模型 (列) 时所用的平均时间 (单位:s).在实验中, 我们的方法能够在0.06s~0.26s之间返回结果; Alloy则能在0.12s~45.04s之间生成结果; 而对于EMFtoCSP, 它在生成第1个模型时使用了72.79s, 之后都没有在有效时间内 (20min) 生成输出.我们的方法和Alloy方法的性能曲线如图 6所示.

为了进一步比较Alloy方法和本文的方法, 我们又利用PetriNet元模型进行了2次实验.同样, 我们利用这两种方法生成10个模型, 每个模型生成5次以便获得平均值.其中, 第1个模型具有600个元素, 第2个模型具有1 200个元素等.实现结果见表 4.其中, 我们的方法可以在0.06s~1.76s之间返回结果; Alloy方法在生成第1个模型时用时226.87s, 在生成第2个模型时已经无法返回结果了.

这个实验能够证明本文方法比其他两种方法的效率更高.此外, 在实验中我们还注意到:本文的方法能够随机生成模型, 而Alloy和EMFtoCSP则不能.这也就是说:在相同的配置下, 本文的方法每次生成的模型都能和之前生成的不同; 而对于Alloy和EMFtoCSP, 如果我们不改变约束条件, 它们总会生成同一个模型.这是因为, 它们所使用的约束求解器会按照确定的方法遍历状态空间 (随机搜索的效率会更低).

3.4 实验3:可伸缩性

在第3个实验中, 我们利用本文的方法分别为5个元模型生成一组模型 (不包括其他约束).对于每一个元模型, 我们会生成5个模型, 其文件大小从1MB到5MB发生变化.对于每一个模型, 我们都生成5次以便获取平均执行时间 (单位:s).这5个元模型分别是JavaSource, extlibrary, BibTex, PetriNet和TextualPathExp.其中, extLibrary是EMF工具中的标准案例项目Extended Library Model Example中使用的元模型, JavaSource和PetriNet与实验1中使用的元模型相同, 它们与BibTex, TextualPathExp一起都来自ATL转换数据库.

对于每一个模型, 为了控制模型的大小, 其元素和关系数量都是固定值.对于每个元模型下相应的5个模型, 元素范围约束和关系范围约束的变化比例是一致的.例如, 假设生成第1个模型M₁时, 我们使用了两个范围约束ra₁和rb₁.在生成第2个模型M₂时, 如果k·ra₁=ra₂, 那么rb₂=k·rb₁.实验3的结果见表 5.

对于JavaSource模型, 消耗的时间在3.94s~98.05s之间.对于extlibrary模型, 消耗的时间在1.94s~39.86s之间.对于BibTex模型, 消耗的时间在5.74s~214.44s之间.对于PetriNet模型, 消耗的时间在6.56s~119.4s之间.对于TextualPathExp模型, 消耗的时间在71.56s~2800.35s之间.

实验2的性能曲线如图 7所示.在图 7中, 我们还列出了每条曲线拟合的函数.对于JavaSource模型, 其性能曲线服从函数y=5.789x^2.2792; 对于extlibrary模型, 性能曲线服从函数y=3.7502x^2.0197; 对于BibTex模型, 性能曲线服从函数y=1.9556x^1.9096; 对于PetriNet模型, 性能曲线服从函数y=5.9807x^1.8124; 对于TextualPathExp模型, 性能曲线服从函数y=68.936x^2.297.

从这个实验中, 我们可以得到下面3个结论.

1) 当模型的大小呈线性增长时, 消耗的时间服从幂函数y=k×x^p;

2) 指数p的变化范围在1.8124~2.297之间, 其平均近似值为2.06.对于不同元模型, 指数变化不大;

3) 对于不同的元模型, 系数k剧烈变化, 这就意味着, 系数k受元模型复杂性影响较大.

理论上讲, 本文方法的性能也会受到要生成的模型复杂性的影响.在今后的工作中, 将研究本文方法性能和元模型的复杂性以及模型之间的关系.

4 相关工作

目前存在一些关于模型生成 (或元模型实例生成) 的研究工作, 可以分为3种技术路线:基于求解的方法、基于算法的方法和基于图形语法的方法.前两种方法在本文开始部分已经提到.本节将比较已有的研究工作.

基于求解器方法的基本思想如下:(1) 将元模型和约束转换成一组不变式, 这些不变式可以被模型检查器、约束求解器或者SAT/SMT求解器所接受; (2) 使用上述求解器求解不变式, 并获得一个解; (3) 把得到的解转换成模型.

Alloy^[13]是一个成熟的针对关系模型证明器.Anastasakis等人讨论了如何把一个UML类图转换成Alloy语言^[17], 他们提出一些转换规则, 能够把UML类图和部分OCL约束映射到Alloy中.Sen等人提出了一个基于Alloy的工具^[14], 该工具能够生成可以测试模型转换的输入模型.McQuillan等人提出一种用于度量面向对象系统的元模型^[18].用户可以使用该元模型定义一些度量指标 (即一个度量模型), 之后这些度量指标可以被转换成Alloy语言, 并检测度量指标的有效性 (如果有效, Alloy可以找到一个符合该度量模型的实例).

Apt^[19]等人提出了一种模型约束求解器——ECLⁱPS^s.Cabot等人^[20]提出了一种将OCL约束下的UML模型转换成ECLⁱPS^s的方法.他们的方法都基于EMFtoCSP^[12], 并用于生成模型转换的测试输入^[15].

Soeken等人^{[21, 22]}也提出一种使用SAT求解器验证OCL约束下的UML模型的方法, 他们使用bit-vector (位向量) 来编码元模型和约束.

不难看出, 基于求解器的方法比本文的方法更加灵活, 因为它们可以处理更多的约束条件.它们适用于模型验证和白盒测试.然而在第3节中我们已经通过实验证明:与本文的方法相比, 基于求解器的方法不能高效地生成较大规模的模型.这使得它们无法很好地支持模型转换的性能测试.

除此之外, 还有很多基于算法的方法.

Mougenot等人^[23]提出了一种基于Boltzmann算法^[24]的大模型生成器.首先, 他们将元模型转换成树的规约, 其中, 类是节点, 聚合引用是边.该方法还支持聚合引用的多重性约束.之后, 他们调用Boltzmann方法生成一个符合规范的有效树.该方法执行效率很高, 但却没有讨论如何生成非聚合关系.此外, 该方法也没有考虑语义约束.因此, 他们的方法可能生成一个无效的模型, 例如一个包含循环继承的类图.

Brottier等人^[25]提出了一种用于测试模型转换的模型生成算法.该算法能够依照一定的覆盖准则和组合策略, 将一组给定模型片段复合成完整的模型.但他们没有讨论如何生成初始的模型片段.相比于该工作, 本文的方法更具有可配置性, 考虑到了更多的约束条件, 从而确保了生成模型的正确性.

Ehrig等人介绍了一种基于图语法的模型生成方法^[26].该方法将元模型和约束编码成一组图转换规则, 并通过执行这些规则生成一个模型.然而, 在图转换中最常进行的操作是图模式匹配, 这是一个NP完全问题, 也是图转换的性能瓶颈.因此, 这种基于图语法的模型生成方法也不可能高效地生成大规模的模型.

5 总结与展望

本文主要工作包括:(1) 提出了一种随机、高效、正确、可配置的模型生成算法, 在合理的时间内能够生成符合语法、语义和范围约束的模型; (2) 进行了两个实验, 验证了本方法的高效性.

在未来的工作中, 我们计划从以下两个方面改进本文的方法:(1) 尝试处理更多种类的约束 (尤其是语义约束); (2) 探索并行模型生成算法, 以便更好地利用多核计算机.此外, 我们还会进行更加系统的实验评估, 以便分析本文方法的性能与元模型的复杂度以及将要生成的模型之间的精确关系.

此外, 在本文方法的基础上, 我们还将研究如何基于随机模型生成技术构造更加复杂但高效的模型生成方法, 以便支持复杂的OCL约束.同时, 还将探索如何利用本文方法实现对模型转换的随机测试.