Made available in DSpace on 2014-06-12T15:51:19Z (GMT). No. of bitstreams: 1 license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Message Sequence Charts (MSC) é uma linguagem gráfica, usada na academia e na indústria, cujo objetivo é descrever o comportamento de componentes de sistemas e seus ambientes. A sintaxe e a semântica de um diagrama MSC padrão são definidos pelo International Telecommunication Union. A motivação para esse trabalho foi originada a partir de esforços para modelar cenários de aplicações de aparelhos móveis com o objetivo de automatizar a geração de testes, no contexto de uma colaboração entre Centro de Informática da Universidade Federal de Pernambuco (CIn- UFPE) e a Motorola, no contexto do projeto Brasil Test Center (BTC). Ao modelar algumas destas aplicações que envolvem múltipla sincronização utilizando como linguagem de modelagem, MSC padrão, constatou-se que os diagramas são de difícil entendimento ou com um comportamento diferente do desejado. É proposta neste trabalho uma extensão de MSC com o objetivo de permitir a descrição de mensagens síncronas, que permitem descrever eventos instantâneos (abstraindo-se a duração do tempo real para que a conexão seja estabelecida) e podendo envolver várias instâncias de MSC. Essa extensão é conservativa, no sentido que o comportamento das construções existentes não é afetado pela mesma; além disso, em um mesmo diagrama é possível conter mensagens síncronas e mensagens assíncronas. Foi desenvolvido um algoritmo de transformação, que a partir de um diagrama escrito na notação MSC estendido, gera um diagrama correspondente na notação de MSC padrão. Este algoritmo tem por objetivo permitir a transitividade entre as notações e demonstrar suas equivalências. Este algoritmo de transformação implementa mensagens síncronas como uma seqüência de mensagens assíncronas seguindo um algoritmo particular de handshake. A segunda contribuição desse trabalho é a definição de uma semântica para a notação padrão e estendida de MSC. Essa definição é dada em termos da álgebra de processos CSP (Communicating Sequential Processes). O formalismo introduzido na notação de Message Sequence Charts com CSP permite mostrar a equivalência entre um diagrama na notação de MSC estendido e seu correspondente descrito em MSC padrão, gerado a partir do algoritmo de transformação. Além disso, modelar MSC como um processo descrito na notação CSP permite uma análise sobre seus diagramas, usando um rico conjunto de leis algébricas de CSP, bem como o uso de ferramentas, como FDR2 e o Probe. Finalmente, para validar a estratégia proposta, desenvolveu-se um exemplo que ilustra a utilização da notação estendida de MSC, notação síncrona; a conversão desta notação para a notação padrão e a equivalência entre o MSC estendido e o padrão. Mostramos, ainda, o uso da ferramenta Power Tool Kit(PTK) para geração de casos de teste a partir de diagramas MSC

Capturing a requirement is a great challenge in the initial stages of the software development, be it a system requirement or a customer requirement to the software engineers. Understanding the requirement and predicting or differentiating what may happen and what must happen is difficult especially in the complex real time systems. Live sequence charts are extensions of the message sequence charts which can specify the live ness of the requirements. And the play engine tool is used to specify, validate, and analyze the scenarios of the requirements. This thesis is to evaluate live sequence charts using the play engine tool and to see if the built-in model checkers can detect inconsistencies in the LSC’s. / The requirements capturing and analysis has always been the initial criteria and main problem during the software design and development for the software engineers. It’s been very common to use natural language for capturing the requirements in the industries because of its ease of use. The graphical languages were used to represent the requirements, its behavior and the scenarios graphically or visually, for example UML. UML Sequence diagrams are used in the real time software development to capture the requirements which specifies the scenarios of the system behavior and also the interactions between the objects graphically. Message sequence charts are also a graphical language for representing the scenarios and also the behavior of the system especially in the telecommunication domain. But these two are only useful in specifying the one aspect of the behavior and not much helpful in specifying the liveness of the requirement. Liveness can be defined as something good will happen [34] or something must happen. For this reason live sequence charts were developed which can specify the liveness of the requirement. Live sequence charts are capable of specifying the scenarios what may happen and what must happen. This thesis is to evaluate the live sequence charts using the play engine tool running on the windows machine and also to study the built in model checkers for formal verification. The thesis starts with the various types of graphical representation of requirements in Software Engineering, followed by the Research Methodology, next a bit more explanation of Live Sequence Charts, Evaluation, Result, Conclusions and Lessons Learned from the thesis. / Permanent Address: C/O: K.VIJAYA H.NO. 3-1-39/12/3/2 TEACHER'S COLONY ARMOOR-503224 ANDHRAPRADESH INDIA.

Message Sequence Charts are a visual representation of the system specification which shows how all the participating processes are interacting with each other. Message Sequence Graphs provide modularity by easily allowing combination of more than one Message Sequence Charts to show more complicated system behavior. Requirements modeled as Message Sequence Graphs give a global view of the system as interaction across all the participating processes can be viewed. Thus systems modeled as Message Sequence Graphs are like sequential composition of parallel process. This makes it very attractive during the requirements gathering and review phases as it needs inter-working between different stakeholders with varied domain knowledge and expertise – requirements engineers, system designers, end customers, test professionals etc. In this thesis we give a detailed construction of a finite-state transition system for a com-connected Message Sequence Graph. Though this result is fairly well-known in the literature there has been no precise description of such a transition system. Several analysis and verification problems concerning MSG specifications can be solved using this transition system. The transition system can be used to construct correct tools for problems like model-checking and detecting implied scenarios in MSG specifications. There are several contributions of this thesis. Firstly, we have provided a detailed construction of a transition system exactly implementing the message sequence graph. We have provided the detailed correctness arguments for this construction. Secondly, this construction works for general Message Sequence Graphs and not limited to com-connected graphs alone, although, we show that a finite model can be ensured only if the original graph is com-connected. Also, we show that the construction works for both synchronous and asynchronous messaging systems. Thirdly, we show how to find implied scenarios using the transition model we have generated. We also discuss some of the flaws in the existing approaches. Fourthly we provide a proof of undecidability argument for non com-connected MSG with synchronous messaging.

Les MSG (pour « Message Sequence Graphs ») sont un formalisme bien connu et souvent utilisé pour décrire des ensembles de scénarios de manière visuelle dans le domaine des protocoles de communication. Nous nous intéressons dans la première partie de la thèse à la détection de la divergence, la vérification de la coopération globale ainsi que la vérification de propriétés d’accessibilité et de couverture. Notre première contribution consiste à utiliser des solveurs SAT afin de résoudre ces problèmes efficacement. Afin de munir le formalisme des MSG de compteurs, de timers et d’autres aspects, nous introduisons le modèle des PNS (pour « réseaux de Petri avec états ») et une sémantique de processus non-branchants. Ce modèle est non seulement plus expressif que les MSG, mais il permet également des spécifications plus concises. Nous nous intéressons à trois problèmes de vérification classiques sur l’ensemble des marquages accessibles par les préfixes des processus : le caractère borné, la couverture et l’accessibilité. Afin de considérer des systèmes paramétrés, nous introduisons également la notion de borne semi-structurelle. Cela consiste à fixer le marquage initial d’un sous-ensemble approprié de places, puis à vérifier que le système est borné, quelles que soient les valeurs des paramètres. Nous montrons comment un dépliage conduit à un problème plus simple à vérifier. Une caractéristique particulièrement attrayante des MSG et des PNS réside dans leur représentation graphique similaire à un automate. Il est donc intéressant de décrire les bugs de manière visuelle. Nous montrons comment calculer en temps polynomial une représentation simple et concise d’un bug. / Message Sequence Charts (MSCs) are a popular model often used for the docu- mentation of telecommunication protocols. In the first part of the thesis, we focus on detecting process divergence, checking global-cooperation and checking reachability properties. Our first contribution is to use SAT solvers to solve these problems effectively. In order to study MSC specifications with counters, timers and other features, we introduce the model of Petri nets with states together with a non-branching non-sequential process seman- tics. We obtain a framework that is more expressive and more concise than MSGs. We consider then three classical verification problems for the set of markings reached by prefixes of processes : boundedness, covering and reachability. We consider also the notion of semi-structural property in order to study parametrized sys- tems. In this way, only part of the places are provided with an initial marking. Unfolding such a system leads to a simpler problem in the form of a linear programme. A particularly attractive feature of MSG and PNS lies in their graphical representation similar to an automaton. So, it is interesting to describe the bugs visually. We show how to compute in polynomial time a simple and concise representation of a bug.

Der Elektrik/Elektronik- und der IT-Anteil steigt derzeit in den aktuellen Premium -Fahrzeugen stetig an. Durch den Verbau von immer mehr (hochvernetzten) Steuergeräten im Fahrzeug wird versucht, dem Wunsch der Kunden nach mehr Funktionalität, Sicherheit, etc. gerecht zu werden. Aufgrund der Komplexität und der großen Entwicklungssprünge sind jedoch die neuen Steuergeräte meistens nicht mehr kompatibel mit den Vorgänger-Steuergeräten. Hier ist ein großes Einsparpotenzial vorhanden und dies ist auch der Ansatzpunkt des Forschungsthemas ”CompA“ (Compatibility Analysis of Electronic Control Units), das in diesem Dokument beschrieben wird. Im Rahmen dieses Forschungsthemas wird eine Methode definiert, mit der zwei Steuergeräte auf Rückwärtskompatibilität untersucht werden können. Der Ansatz baut auf drei Schwerpunkten auf: • Definition eines Spezifikationsansatzes zur hinreichenden Beschreibung von Steuergeräten auf Basis eines XML-Schemas. Es werden hierbei sowohl die statischen als auch die dynamischen Eigenschaften abgebildet. Dieser neuartige Spezifikationsansatz bildet die Basis für den nächsten Schwerpunkt. • Definition einer Methode zur Analyse von Rückwärtskompatibilität von Steuergeräten auf Basis eines XML-Schemas. Die Rückwärtskompatibilität zweier Steuergeräte bzw. Systeme wird auf Basis der zugehörigen XML-Dokumente analysiert. Kern der Vergleichsmethode ist hierbei ein effizientes Mapping der XML-Dokumente und ein Experten-Regelwerk. • Definition einer Methode zur Kompatibilitätsanalyse von Message Sequence Charts (MSC). MSCs werden eingesetzt, um dynamisches Verhalten an der Schnittstelle von Steuergeräten zu beschreiben. In diesem Dokument wird ein Ansatz definiert, mit dem MSCs zueinander auf Rückwärtskompatibilität geprüft werden können. Der Vergleich erfolgt auf Basis deterministischer Automaten. Des Weiteren wird im vorliegenden Dokument ein Konzept für eine graphische Benutzeroberfläche (GUI) vorgestellt, die zur Spezifikation von Steuergeräten geeignet ist und sich adaptiv unterschiedlichen Schemata anpasst. Alle vorgestellten Konzepte wurden in einem Software-Tool implementiert und die Gültigkeit an mehreren Beispielen validiert.

Der Elektrik/Elektronik- und der IT-Anteil steigt derzeit in den aktuellen Premium -Fahrzeugen stetig an. Durch den Verbau von immer mehr (hochvernetzten) Steuergeräten im Fahrzeug wird versucht, dem Wunsch der Kunden nach mehr Funktionalität, Sicherheit, etc. gerecht zu werden. Aufgrund der Komplexität und der großen Entwicklungssprünge sind jedoch die neuen Steuergeräte meistens nicht mehr kompatibel mit den Vorgänger-Steuergeräten. Hier ist ein großes Einsparpotenzial vorhanden und dies ist auch der Ansatzpunkt des Forschungsthemas ”CompA“ (Compatibility Analysis of Electronic Control Units), das in diesem Dokument beschrieben wird. Im Rahmen dieses Forschungsthemas wird eine Methode definiert, mit der zwei Steuergeräte auf Rückwärtskompatibilität untersucht werden können. Der Ansatz baut auf drei Schwerpunkten auf: • Definition eines Spezifikationsansatzes zur hinreichenden Beschreibung von Steuergeräten auf Basis eines XML-Schemas. Es werden hierbei sowohl die statischen als auch die dynamischen Eigenschaften abgebildet. Dieser neuartige Spezifikationsansatz bildet die Basis für den nächsten Schwerpunkt. • Definition einer Methode zur Analyse von Rückwärtskompatibilität von Steuergeräten auf Basis eines XML-Schemas. Die Rückwärtskompatibilität zweier Steuergeräte bzw. Systeme wird auf Basis der zugehörigen XML-Dokumente analysiert. Kern der Vergleichsmethode ist hierbei ein effizientes Mapping der XML-Dokumente und ein Experten-Regelwerk. • Definition einer Methode zur Kompatibilitätsanalyse von Message Sequence Charts (MSC). MSCs werden eingesetzt, um dynamisches Verhalten an der Schnittstelle von Steuergeräten zu beschreiben. In diesem Dokument wird ein Ansatz definiert, mit dem MSCs zueinander auf Rückwärtskompatibilität geprüft werden können. Der Vergleich erfolgt auf Basis deterministischer Automaten. Des Weiteren wird im vorliegenden Dokument ein Konzept für eine graphische Benutzeroberfläche (GUI) vorgestellt, die zur Spezifikation von Steuergeräten geeignet ist und sich adaptiv unterschiedlichen Schemata anpasst. Alle vorgestellten Konzepte wurden in einem Software-Tool implementiert und die Gültigkeit an mehreren Beispielen validiert.