Verification of distributed and multi-agent systems using data analytics and message contents independence approach

使用数据分析和消息内容独立方法验证分布式和多代理系统

• 批准号: RGPIN-2016-04067
• 负责人: Far, Behrouz
• 金额: $ 1.6万
• 依托单位: University of Calgary
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=614818
• 关键词: Verification; distributed; multi; agent; systems

Distributed software systems (DSS) are a class of software systems in which functionality and/or control are distributed. In DSS the way components interact is usually described by scenarios, e.g. sequence diagrams. Maintaining consistency among the scenarios in multiple design iteration is a complex and expensive task. Lack of centralized control and multiplicity of scenarios imply that there may be unintended/unexpected behavior during execution, commonly known as “emergent behavior” (EB) and “implied scenario” (IS). They may lead to costly and/or irreversible damage to the users, environment, and the business. Our goal in this research is to manage (i.e. model, analyze, detect and resolve) EB and IS by identifying design flaws that may lead to them. We focus on addressing the problems using novel social network analysis and data mining approach. The main focus is on detecting the “shared states” and “shared interactions”, which are the main culprits of EB and IS in a DSS, respectively. However, detecting shared states and/or interactions is not an easy task in terms of computational resources and complexity of the algorithms. We view a component’s behavior as a language equivalent to its state transition diagram. Similarly, interaction among components - as constrained by the design scenarios - are modeled by a graph similar to what is common in social networks. Clustering technique are applied to the strings of the language and the graph to identify common sequences of states and interactions. Largest frequent subset of shared states in string mining and higher changes of pairwise members in graph mining are suspects of causing EB and IS. Unique points in this research besides being computationally manageable are: (1) Modeling both interactions of components and their internal states together that saves the components’ states and preserves the interaction information among the components; (2) Using interaction information to detect potential problems; (3) Ability to investigate whether new path can exist between components based on identified interactions; (4) Ability to suggest solutions based on exact cause of the detected problem; (5) Ability to investigate interactions of the same-type components/agents. This research has a solid theoretical basis and a fully implemented system. Through both simulated and detailed case studies applied to various domain problems we will show the efficiency and effectiveness of the approach. This research provides a cost effective solution to model-based verification of DSS which appeals to a large audience, namely medium/large companies. It has great potential for lightweight software development processes, especially appealing to Agile developers. Although formal models and Agile methodologies are generally considered immiscible, our research shows that “just enough” documentation is “good enough” to produce useful results.

分布式软件系统（DSS）是一类功能和/或控制是分布式的软件系统。在DSS中，组件交互的方式通常由场景描述，例如序列图。在多个设计迭代中保持场景之间的一致性是一项复杂而昂贵的任务。缺乏集中控制和场景的多样性意味着在执行过程中可能会出现非预期/意外的行为，通常称为“紧急行为”（EB）和“隐含场景”（IS）。它们可能会对用户、环境和业务造成代价高昂和/或不可逆转的损害。 我们在这项研究中的目标是通过识别可能导致EB和IS的设计缺陷来管理（即建模，分析，检测和解决）EB和IS。我们专注于使用新的社会网络分析和数据挖掘方法来解决这些问题。主要的重点是检测“共享状态”和“共享交互”，这是在一个DSS的EB和IS的罪魁祸首，分别。然而，检测共享状态和/或交互在计算资源和算法的复杂性方面不是一件容易的任务。我们将组件的行为看作是一种等价于其状态转换图的语言。类似地，组件之间的交互（受设计场景的约束）由类似于社交网络中常见的图形建模。聚类技术应用于语言和图的字符串，以识别状态和交互的公共序列。字符串挖掘中共享状态的最大频繁子集和图挖掘中成对成员的较高变化被怀疑是导致EB和IS的原因。 本研究的独特之处在于：（1）将组件的交互及其内部状态一起建模，保存了组件的状态并保留了组件之间的交互信息;（2）利用交互信息来检测潜在的问题;（3）能够根据识别出的交互来研究组件之间是否存在新的路径;（4）能够根据检测到的问题的确切原因提出解决方案;（5）能够调查同类组件/代理的相互作用。 本研究具有坚实的理论基础和完备的实施体系。通过模拟和详细的案例研究应用于各种领域的问题，我们将显示该方法的效率和有效性。 这项研究提供了一个具有成本效益的解决方案，以基于模型的验证的DSS，吸引了大量的观众，即中型/大型公司。它对轻量级软件开发过程有很大的潜力，特别是对敏捷开发人员有吸引力。虽然正式模型和敏捷方法通常被认为是不兼容的，但我们的研究表明，“刚好足够”的文档是“足够好”的，可以产生有用的结果。