数据收集优先级的贝叶斯网络算法降低了系统质量分析的成本

理论计算机科学电子笔记233（2009）29-42www.elsevier.com/locate/entcs用于系统质量分析的数据收集优先级PerNüarman1PontusJohnson2RobertLagerstroüm3UlrikFranke4Mathias Ekstedt5工业信息与控制系统皇家理工瑞典斯德哥尔摩摘要在评估软件质量时，收集分析所需数据的成本往往相当可观。本文提出了使用贝叶斯网络评估软件质量相结合的算法，如何优先收集哪些数据，以尽量减少评估的成本。 这个算法，诊断算法在贝叶斯网络工具'GeNie'中实现。本文中的服务互操作性的示例评估表明，使用该算法可以显着减少数据收集所花费的时间。关键词：系统质量分析，贝叶斯网络，数据收集策略1引言近年来，软件、系统和企业架构已成为工业界和学术界的既定学科。架构模型可以帮助不同涉众之间的沟通。架构模型还可以帮助理解它们所代表的复杂系统。理解的一个重要部分是能够从模型中推断新知识，即能够分析模型。例如，通过考虑一组企业服务及其关系上的架构模型，观察者可能会推断这些服务将无法互操作（可能是由于协议不匹配）。 模型 并没有明确指出服务不能互操作，而是通过使用一个集合1电子邮件：pern@ics.kth.se2电子邮件：pj101@ics.kth.se3电子邮件：robertl@ics.kth.se4电子邮件：ulrikf@ics.kth.se5电子邮件地址：mathiase@ics.kth.se1571-0661/© 2009 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2009.02.05930P. Närman等人/理论计算机科学电子笔记233（2009）29的推理规则（例如，协议必须匹配），有可能推断出这个新的信息。本文建立在架构分析领域内的先前研究的基础上，其中使用基于贝叶斯统计的形式主义来分析架构模型[9] [10]。这种方法允许分析各种系统属性，如互操作性，信息安全和软件系统的可用性。 在本文中，我们将使用企业服务互操作性分析作为运行示例。然而，大型系统的建模可能变得过于昂贵，因为模型变得非常大。因此，希望能够对不完整的模型进行分析，即对不包含对所考虑的属性进行完全可信的评估所需的所有信息的模型进行分析（在我们的示例中为互操作性）。相反，不仅需要获得分析结果，而且需要估计其不确定性或缺乏可信度。使用所提出的基于贝叶斯算法的方法，有可能获得的结果表明，该系统能够互操作的概率是，例如，80%。为了提高结果的可信度，需要对架构模型进行细化。架构模型的细化通常需要数据收集。有些人需要查找和研究文档和代码，也许还需要采访开发人员和其他利益相关者。 由于这种数据收集是昂贵的，首先收集最重要的数据或证据。 在本文中，我们提出了一种方法来确定各种证据的收集顺序。下一部分将提供本文所基于的体系结构分析方法的一些背景。第3节具体介绍了企业服务互操作性分析中的方法。在第四部分中，对示例系统进行建模。它表明，该模型迅速变得非常大，有必要的数据收集策略。在第5节中，提出了一种用于选择最优选的下一个证据的算法。由于算法需要关于证据收集成本的信息，第6节考虑了如何分配此类成本。在第7节中，展示了使用该算法的结果。第8节结束了论文。2抽象和具体模型抽象模型是包含实体和实体关系的企业架构元模型，并使用贝叶斯网络的属性和属性关系进行了扩充。实体是大多数元模型中的基本部分。 实体表示建模时感兴趣的对象，例如系统、服务、人员或流程。抽象模型中的实体类似于UML中的类[15]。实体关系连接两个实体，例如“服务描述描述服务”或“人员是流程的资源”。 实体关系也表明了实体之间的关系，例如一个人可以成为P. Närman等人/理论计算机科学电子笔记233（2009）2931Fig. 1. 抽象模型的UML描述。零个或多个进程。抽象模型的属性表示与实体相关的随机变量。UML也有与实体相关的属性，但抽象模型中的属性与UML中的属性不同。在抽象模型中，属性和属性关系表示贝叶斯网络的节点和关系，见下文。抽象模型的UML描述如图1所示。Johnson等人对实验模型和具体模型[11 ]第10段。2.1贝叶斯网络Friedman等人[5]描述了贝叶斯网络B =（G，P）作为联合概率分布的表示，其中G =（V，E）是由顶点V和边E组成的有向非循环图。 顶点表示随机变量X1，.， 也称为机会节点。在抽象模型的上下文中，每个机会节点对应于一个属性。 每个机会节点X i可以假设来自有限域V al（X i）的值X i。边表示节点之间的因果依赖关系，即，节点之间的因果关系网络B的第二个组成部分P描述了每个机会节点P（Xi）的条件概率分布，给定其在G中的父节点Pa（Xi）。可以写出域X1，.的联合概率分布，使用概率的链式法则，以乘积的形式。nP（X1，.， X n）=P（X i| Pa（Xi））。i=1为了指定联合分布，必须定义以乘积形式出现的相应条件第二个分量P描述了Xi的每个可能值Xi和Pa（Xi）的pa（Xi）的分布，其中pa（Xi）是Pa（Xi）的值的集合这些条件概率用矩阵表示，这里称为条件概率矩阵（CPM）。使用贝叶斯网络，可以回答这样的问题，例如给定Y=y2和Z=z1，变量X处于状态x1的概率是多少。32P. Närman等人/理论计算机科学电子笔记233（2009）29语言A语言B语言A语言B语言A语言B兼容1001不兼容0110表1等式关系的条件概率矩阵。在一般情况下，条件概率矩阵所描述的变量之间的关系可以是任意复杂的条件概率。本文中使用的示例模型只使用了几个相当简单的关系，即AND、加权抽样分布和等式。表1中给出了一个相等关系的CPM示例。更 关于贝叶斯网络的全面处理可以在 例如[14]，[16]，[17]，[18]，[2.2创建具体模型抽象模型告诉我们需要找到哪些信息来进行不同变量的分析。一旦收集到这些信息，它就会在模型中指定，从而创建抽象模型的实例化。 这些实例化被称为具体模型。抽象模型可以使用贝叶斯网络的众所周知的学习算法在案例研究中收集的证据上迭代改进[7]。 这个学习过程的结果决定了所有属性的先验值，以及最终抽象模型中的条件概率矩阵一旦建立了一个具体的模型，我们可以使用贝叶斯数学来计算模型的属性值3一种用于互操作性分析在本节中，我们将提出一个用于企业服务互操作性分析的抽象模型.这个抽象模型是Ullberg等人[21]提出的模型的简化版本。这个抽象模型包含七个实体，所有这些实体都被简单地描述，并带有相应的属性，参见图2。服务是独立的构建块，它们共同表示应用程序环境，就像软件系统的组件一样。然而，服务拥有许多组件所缺乏的品质，例如与其他服务的完全自主性。这允许服务负责自己的域。此外，服务的范围通常限于支持特定的业务功能或一组相关功能[3]企业中的每个服务都需要具有高质量，即每个服务都需要能够与其他服务进行互操作的基础。衡量服务质量的两个方面是服务的正确性和可用性.P. Närman等人/理论计算机科学电子笔记233（2009）2933服务具有服务描述。这些用于广告和描述服务能力、行为、质量及其接口[16]。 服务描述有四个属性：可理解性、完整性、正确性和在服务存储库中的存在性。这些属性都决定了所描述的服务的质量对于服务之间的通信，每个服务都有一个服务接口。服务接口包含服务通信所需的协议，并指定服务提供或调用哪些操作[4][17]。服务使用服务总线（通常称为企业服务总线（ESB））作为通信介质。服务总线是一种类似于中间件的解决方案，用于管理消息和事务传输[13]。服务编排描述是详细描述和控制服务编排以进行交互的规范[17]这些描述是用服务编 排 语 言 编 写 的 ， 其 中 业 务 流 程 执 行 语 言 （ Business Process ExecutionLanguage）被认为是行业标准。服务编排描述必须是服务兼容的，以便编排的服务具有高质量。服务在服务集群中互操作，例如，可以编排三个细粒度服务A1、A2和A3以提供更粗粒度的服务B。因此，集群出现在许多不同的抽象级别上，最粗粒度的企业服务由其他几个更细粒度的集群组成。图二.服务集群互操作抽象模型。所有的集群，独立于抽象级别，都可以从互操作性方面进行分析;即集群内的服务如何互操作。 服务集群互操作性是根据集群内每个服务的质量、服务协议兼容性、服务总线兼容性和服务编排语言兼容性来4混凝土模型使用服务集群互操作性的抽象模型，我们现在继续创建一个非常小的服务集群的示例具体模型，34P. Närman等人/理论计算机科学电子笔记233（2009）29只有两个服务。这个具体模型的目的是评估服务集群的可互操作性。4.1在对具体模型进行具体模型的创建开始于设置抽象模型中指示的多重性，然后命名具体模型中的实例化实体。在这里，我们有一个服务集群，其中有两个服务：每个服务都有一个服务描述和一个服务接口，它们相互通信。服务的集成由一个服务总线和一个服务编排描述来管理。具体模型的概述见图3。具体模型的每个对象都有许多属性;这些问题是互操作性评估需要回答的。我们有几种方法来收集每个属性的证据;因此，我们可以找到关于一个属性的几个证据。收集信息的可行方法是，例如，采访人员，执行手动测试，研究文档或这些方法的组合。在本例中，我们介绍了三个证据来源。Max是负责开发服务集群的顾问。系统所有者George负责实现服务的系统。最后，调查人员可以通过对具体模型中的各种属性执行手动检查来图3.第三章。一个由两个服务组成的服务集群的具体模型，并给出了一些示例属性。P. Närman等人/理论计算机科学电子笔记233（2009）2935Max服务描述完整性完成不完全完成0.90.1不完全0.10.9表2在条件概率矩阵中指定的证据的可信度。麦克斯回答正确的概率4.2证据的可信度由于某些来源比其他来源更适合提供某些信息，因此信息收集来源的选择非常重要。 公信力 可以量化并以条件概率矩阵表示。表2中给出了一个示例。确定证据可信度的一种方法是使用证据学[8]。这种理论可能会指出，除其他事项外，来源的能力简介与问题的领域匹配得越好，来源的信息越新 确定证据可信度的另一种方法是允许调查人员主观地具体说明。从专家那里获得定量估计是统计学中一个研究得很好的领域;例如[2]和[12]。在当前的例子中，我们使用一个简单的启发式方法来估计源答案的可信度，将他们的能力域与问题所需的能力域相匹配。乔治以前有服务经验。因此，调查人员根据服务实体的属性来估计乔治有95%的可能性是正确的由于George对服务基础设施实体（例如服务总线）的了解较少，因此他对这些实体的属性值的可信度估计为90%。对Max进行了能力概况和模型实体之间的类似匹配。调查人员其他值（例如服务总线的兼容性）。在这些情况下，预测略好于猜测，60%。各种证据的可信度见表3。假设源不支持偏差，表3中的概率可以以条件概率表的形式表示，例如：表2.4.3很多证据在这个简单的例子中，需要赋值的属性的数量已经相当可观了，确切地说是二十六个 对于每一个属性，都有可能收集到三条证据;在我们的例子中，这意味着可以收集到大约78条证据。随着新服务的增加，这一数字将迅速增长。每一个新的36P. Närman等人/理论计算机科学电子笔记233（2009）29表3三个来源能够正确回答问题的属性和概率集群服务将添加10个属性。 假设有十个证据来源，这意味着可以收集到一万多件证据。这反映了服务互操作性评估问题的复杂性有两个与大型混凝土模型和许多证据相关的实际问题。第一个问题是计算。大型混凝土模型的贝叶斯分析可能很难解决。一般来说，计算需求随着团的数量线性增长，并随着团的大小呈指数增长，其中团是一组属性，其中每个属性都连接到集合中的每个其他属性[19]。作为求解具体模型时的一种策略，可以通过引入中间属性来将最大团大小保持在可接受的大小。在本文中，我们专注于与大型混凝土模型和许多证据相关的第二个实际问题。这个问题是由于收集证据的费用。如果服务互操作性示例中的每一个证据都需要一分钟来收集，那么收集所有证据就需要一个人工月证据，假设一百个服务和十个证据来源。较好的选择通常是不收集所有证据，而是接受评估结果的一定程度的不确定性。在采用这一策略时，希望以最低的证据收集成本收集那些对评估结果影响最大的证据。下一节将介绍一种算法，用于确定接下来要收集的证据P. Närman等人/理论计算机科学电子笔记233（2009）2937∈T T →ΣΣ5贝叶斯网络为了解决证据优先级排序的问题，我们转向贝叶斯网络中的诊断理论。使用GeNIe[1]，这是一个由该大学决策系统实验室创建的用于构建决策模型的图形环境匹兹堡大学，然后我们继续演示上面开发的例子。 为简单起见，以下对贝叶斯网络中的诊断的描述基于Jagt诊断涉及两种类型的任务：（i）确定观察到的症状的原因（组合），以及（ii）通过收集额外的，最初未观察到的数据来增加诊断的可信度。由于信息很少是免费的，第二项任务必然涉及制定一项尽可能巧妙地收集信息的战略，即以最少的成本获得最大的诊断价值。我们现在着手使这一点更加精确。5.1信息价值假设诊断概率网络（DPN）被定义为贝叶斯网络，其中至少一个随机变量H是假设变量（在我们的情况下是服务集群互操作性），并且至少另一个随机变量T是测试变量（在我们的情况下，我们可能收集有关的信息的模型变量例如，George设H表示所有假设变量的集合，T表示所有检验变量的集合。此外，每个测试T有一个成本函数Cost（T）：R。如果测试是免费的，则相关的成本设置为零。此外，每个假设H都有一个相关的价值函数V（P（H））：[0，1]→R。给定一个DPN，我们有执行测试T∈T的期望值EV：EV（T）=V（P（H |t））·P（t）t∈T为了做出明智的决定，我们还需要考虑不执行测试T的预期结果。因此，我们引入预期收益EB：EB（T）= EV（T）− V（P（H））= V（P（H|·P（t）− V（P（H））t∈T然而，目前还没有与测试成本挂钩。这可通过测试强度TS进行EB（T）TS（H，T）=V（P（H））−K·Cost（T）其中，我们引入了系数K，反映了 测试的预期收益与成本。价值函数的定义仍然存在。 为了优化多个假设的检验选择， Jagt引入了一个基于假设之间的边际概率的函数38P. Närman等人/理论计算机科学电子笔记233（2009）29. n−f∈F−ΣΣ（而不是联合概率）称为边际强度1（MS1）MS1（P（F））（f0， 5）210， 52−nF·nF其中，F是用户希望追求的假设的所有所选目标状态的集合，nf是目标状态的总数。这个测试选择函数是凸的，最小值在1nf，最大值在0和1。 我们现在寻找的价值函数变成了所有目标状态的边际强度之和：V（P（F））=MS1（P（f））f∈F5.2诊断在GeNIe图4示出了GeNIe的测试排名用户界面。上面定义的值函数在GeNIe的多原因模块中实现，随时可用（并在“选项”按钮下设置）。可能的测试列在右边，根据基于熵的值函数给出的诊断值进行排名。 在列表上方设置的熵/成本比对应于上面定义的系数K见图4。使用GeNIe的诊断概率网络中的测试排名。由于没有设置该系数的标准方法，因此由用户指定适当的值。一旦执行了测试，则将其从可用测试列表中删除，并重新计算和更新测试的排名以反映新情况。6证据收集费用上一节中描述的诊断算法不仅考虑了从每个来源获得的信息的价值，还考虑了获得信息的成本。为了使用该算法来指导第4节中给出的示例的数据收集，因此有必要分配一个每个潜在的证据来源的成本。 这里分配的成本没有任何特定的单位，如“美元”。相反，它们仅仅是从各种来源获得数据所需的P. Närman等人/理论计算机科学电子笔记233（2009）2939决定使用顾问Max、系统所有者George和手动检查（由研究者执行）作为模型中所有属性的证据收集方法。由于咨询师Max目前正在服务开发项目中工作，并且大部分时间都可以回答问题，从Max获取信息的成本相当低，因此成本设置为0.5。然而，系统所有者乔治还参与了其他几个项目，经常出差。因此，采访乔治的成本被设定为1，是采访马克斯的两倍。 人工检查有时是一种简单快捷的方法 收集证据，例如，当涉及到确定属性的值时，如存储库中服务总线类型或服务描述的存在。然而，采用人工检查也可能非常耗时，例如在收集某些服务的可理解性或完整性等属性的证据时。这些类型的证据将需要调查人员真正了解服务及其环境，这可能是一个漫长的过程。因此，通过人工检查收集证据的成本是相当大的，在本例中，这些成本被设定为5。详见表4。表4成本表，指定每个可能证据的每个来源的成本。40P. Närman等人/理论计算机科学电子笔记233（2009）297收集数据并计算结果本章将通过一个小例子来证明诊断算法对于数据收集优先级排序的有用性。感兴趣的属性是两个服务我们掌握的证据来源是上面提到的;Max，George和各种属性的手动检查。在这个特定的例子中，服务和支持集成服务是以某种方式进行配置的，以使它们能够互操作，因此服务集群的互操作性实际上是“高”的。对应于上述成本系数K的熵/成本比被设置为0.0025。在没有收集关于具体模型中属性的任何数据的情况下，图3中具体模型的条件概率矩阵和先验概率表明服务集群互操作性为“高”，概率仅为21%。研究者认为90%的可信度水平对于研究者使用GeNIe的诊断算法来指导数据收集。使用此策略，达到目标90%可信度水平的总成本约为15，如下面的图5所示从图5中还可以明显看出，当研究人员不遵守在收集数据时，达到90%可信度的成本平均约为56（根据10个系列），几乎高出四倍，是一个相当大的增长。面对一个涉及几百个服务的真正的服务互操作性分析，这种增长转化为可能花费在数据收集上的几个人工月。图五. 从成本和结果可信度方面比较数据收集策略。P. Närman等人/理论计算机科学电子笔记233（2009）29418结论在介绍了一种基于贝叶斯网络的体系结构评估方法后，本文表明，诊断算法，在GeNIE工具中实现，可以用作支持时，希望尽量减少在调查复杂的软件质量，如服务互操作性收集数据所花费的时间。在GeNIe中实现的一个示例的特点是分析了非常小的服务集群的互操作性。在该示例中，证明了与不使用任何特定策略收集数据相比，使用诊断算法几乎降低了数据收集的成本。从这一点上，我们得出结论，诊断算法可以大大降低执行系统质量分析的成本。引用[1] 决策系统实验室，http://genie.sis.pitt.edu/about.html[2] 德鲁兹泽尔和L. van der Gaag，《构建概率网络：数字从何而来？》、IEEE Transactions on Knowledge and Data Engineering，12，IEEE，Los Angeles，USA，2000，289 -299[3] 厄尔·T[4] 厄尔·T“面向服务的体系结构：概念、技术和设计”，Prentice Hall，新泽西州，2005年[5] 弗里德曼，M.利尼亚尔岛Nachman和D PeNew Rochelle，NY，2000，600-620[6] 雅格特河M，论文，荷兰代尔夫特理工大学媒体、信息技术和系统系，宾夕法尼亚州匹兹堡匹兹堡大学信息科学2002[7] 詹森·F五、[8] 约翰松·E·和P. Johnson，Assessment of Enterprise Information Security - Estimating the Credibility ofthe Results ， Proceeding of the Symposium on Requirements Engineering for Information Security（SREIS）in the 13th International IEEE Requirements Engineering Conference，13Paris，法国，2005年[9] 约翰逊P.，R. Lagerstréom，P. 陈文生，张文生，等.企业信息化管理系统的研究与应用.北京：中国科学技术出版社，2001[10] 约翰逊P.，R. Lagerstrom，P. N？rman和M. 陈文，系统质量分析方法的研究，北京大学出版社，2007年[11] 约翰逊P.，Johansson E.，T. Sommestad和J.Ullberg，A Tool for Enterprise Architecture Analysis，Proceedings of the 11th IEEE International Enterprise Distributed Object Conference（EDOC），11IEEE Computer Society，Annapolis，October 2007，142-152[12] 基尼河和D.冯温特费尔特，从复杂技术问题的专家那里获得概率，IEEE工程管理学报，38，IEEE，1991，191-201[13] 马克·E M. Bell，[14] 那不勒斯河， 上鞍河，新泽西州，美国2003[15] 对象管理组织（OMG），版本2.1.1，2007，URL：http://www.omg.org/technology/documents/formal/uml.htm42P. Närman等人/理论计算机科学电子笔记233（2009）29[16] D. Georgakopoulos和Papazoglou M.面向服务的计算，ACM的通信46，ACM，2003，25-28[17] Papazoglou M.，面向服务的计算：概念、特征和方向，第四届Web信息系统工程国际会议论文集（WISE[18] 珀尔·J[19] 里什岛和R. Dechter，论因果独立性的影响，斯坦福交互和混合主动决策理论系统春季研讨会，斯坦福，1998[20] 沙赫特河，概率推理与非概率图，运筹学，36，运筹学与管理科学研究所，1988年，589-604[21] Ull bergJ.，R.Lagerstr？om和JohnsonP.，EnterpriseArchitecture：AServiceinteroperabilityAnalysisFramework ， Proceedings of the 4th International Interoperability for Enterprise Software andApplications Conference（I-ESA