Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2018. / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES). / Sistemas concorrentes enfrentam uma ameaça à sua confiabilidade em comportamentos emergentes, os quais não são incluídos na especificação, mas podem acontecer durante o tempo de execução. Quando sistemas concorrentes são modelados a base de cenários, é possível detectar estes comportamentos emergentes como cenários implícitos que, analogamente, são cenários inesperados que podem acontecer devido à natureza concorrente do sistema. Até agora, o processo de lidar com cenários implícitos pode exigir tempo e esforço significativos do usuário, pois eles são detectados e tratados um a um. Nesta dissertação, uma nova metodologia é proposta para lidar com vários cenários implícitos de cada vez, encontrando comportamentos comuns entre eles. Além disso, propomos uma nova maneira de agrupar estes comportamentos em famílias utilizando uma técnica de agrupamento usando o algoritmo de Smith-Waterman como uma medida de similaridade. Desta forma, permitimos a remoção de vários cenários implícitos com uma única correção, diminuindo o tempo e o esforço necessários para alcançar maior confiabilidade do sistema. Um total de 1798 cenários implícitos foram coletados em sete estudos de caso, dos quais 14 famílias de comportamentos comuns foram definidas. Consequentemente, apenas 14 restrições foram necessárias para resolver todos os cenários implícitos coletados coletados, aplicando nossa abordagem. Estes resultados suportam a validade e eficácia da nossa metodologia. / Concurrent systems face a threat to their reliability in emergent behaviors, which are not included in the specification but can happen during runtime. When concurrent systems are modeled in a scenario-based manner, it is possible to detect emergent behaviors as implied scenarios (ISs) which, analogously, are unexpected scenarios that can happen due to the concurrent nature of the system. Until now, the process of dealing with ISs can demand significant time and effort from the user, as they are detected and dealt with in a one by one basis. In this paper, a new methodology is proposed to deal with various ISs at a time, by finding Common Behaviors (CBs) among them. Additionally, we propose a novel way to group CBs into families utilizing a clustering technique using the Smith- Waterman algorithm as a similarity measure. Thus allowing the removal of multiple ISs with a single fix, decreasing the time and effort required to achieve higher system reliability. A total of 1798 ISs were collected across seven case studies, from which 14 families of CBs were defined. Consequently, only 14 constraints were needed to resolve all collected ISs, applying our approach. These results support the validity and effectiveness of our methodology.

Made available in DSpace on 2014-06-12T16:01:13Z (GMT). No. of bitstreams: 2 arquivo7234_1.pdf: 3108647 bytes, checksum: 005c566b9ea912b4246e213ae0704e2f (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2005 / O desenvolvimento crescente de sistemas concorrentes e de tempo real vem provocando uma evolução nos conceitos e paradigmas da Engenharia de Software. Recentemente, entre outras abordagens, destacamos o surgimento de UML-RT, visando adaptar e estender as estruturas já consagradas de UML para os conceitos de concorrência e tempo real. Complementarmente, já existem modelos teóricos de concorrência e tempo real bem consolidados, como álgebra de processos, que contam com estratégias e ferramentas de validação, verificação e transformação de modelos. Por outro lado, processos de software bem definidos, que integrem estratégias formais de análise com orientações menos formais (mas sistemáticas) de desenvolvimento, são, ainda, negligenciados. O Rational Unified Process (RUP), um dos processos de desenvolvimento de software mais extensivamente usado e aceito, introduziu vários conceitos e orientações que objetivam sistematizar o desenvolvimento com UML-RT; no entanto, vários aspectos importantes e críticos de aplicações concorrentes, como a transformação de uma classe de análise (passiva) em uma classe ativa (cápsula ou processo), com um fluxo de execução independente, são tratados de forma superficial e informal; outros exemplos são a decomposição de cápsulas e a análise de uma aplicação com relação a propriedades clássicas de concorrência (como ausência de deadlock) ou específicas do negócio. As orientações fornecidas pelo RUP parecem sugerir que é simples garantir estes resultados, quando, na verdade, requerem grande atenção e conhecimento do desenvolvedor. O foco deste trabalho é a adaptação e extensão de uma das disciplinas mais afetadas do RUP, Análise e Projeto, a fim de integrar de forma mais detalhada e rigorosa os conceitos e implicações do desenvolvimento de aplicação concorrentes ao processo, incluindo a aplicação de leis de transformação de modelos, sugeridas em estratégias formais de desenvolvimento. A grosso modo, o objetivo pode ser resumido à adaptação do RUP ao paradigma de desenvolvimento baseado em modelos (MDE, Model Driven software Engineering). Apesar do foco em Análise e Projeto, outras disciplinas e fases são também revisadas. A proposta é validada através de sua aplicação a um estudo de caso sobre o projeto de um Sistema Automático de Produção SAP (Automatic Manufacturing System AMS), inicialmente explorado em [18]

This work presents a method to perform formal and dynamic verification of concurrent software. The objective is to provide a method capable of identifying problems in programs whose execution is based on multiple threads, and analyze behavioral properties. The method is able to detect problems in concurrent software, as well as check conformity of the concurrent software with desirable behavior, based on information collected dynamically, i.e. at runtime. The information collected consists of the software execution flow as well as data about the way communicate the software components during this run. The data collected reflect the software's execution, which ensures greater confidence to the information collected. This information is analyzed to identify deadlocks and race conditions in a process called Dynamic Analysis. In addition, this information is also used to automatically generate a model that describes the behavior of a software, which is used for verification of behavioral properties. This process is called Formal Verification. The automatic model generation eliminates the need for manual construction of the model, which requires much effort and knowledge of formal methods, this can increase costs and development time software. However, the dynamic analysis is known to only perform coverage of the current behavior of competing software systems. Current behavior is one that occurs only during an execution of concurrent software systems, without considering all other possible behaviors from the non-determinism. Due to the non-determinism, concurrent software can produce different results for the same input to each execution of software. Therefore reproduce the behavior that leads to competitive software failure is a complex task. This paper proposes a method to perform formal verification and dynamic concurrent software capable of capturing the non-deterministic behavior of these systems and provide reduced development costs by eliminating the need for manual construction of concurrent software system models. The method is validated by a case study consists of three test software systems. / Fundação de Amparo a Pesquisa do Estado de Alagoas / Neste trabalho é apresentado um método para verificação formal e dinâmica de software concorrentes. O objetivo é oferecer um método capaz de identificar problemas inerentes a programas cuja execução baseia-se em múltiplas threads, além de analisar propriedades comportamentais descritas com base nos preceitos da lógica temporal. Propõe-se um método capaz de detectar problemas e verificar formalmente a adequação da execução de sistemas de software concorrentes com relação ao comportamento desejável a tais sistemas, baseando-se em informações coletadas dinamicamente, ou seja, em tempo de execução. As informações coletadas correspondem às sequências de execução de sistemas de software, bem como dados sobre a maneira como se comunicam seus componentes durante sua execução. Os dados colhidos refletem a execução do sistema de software propriamente dito, o que garante maior confiança às informações coletadas. Tais informações são analisadas de modo a identificar impasses e condições de corrida em um processo denominado Análise Dinâmica. Ademais, estas informações também são utilizadas para geração automática de um modelo que descreve o comportamento do sistema de software, o qual é utilizado para verificação de propriedades comportamentais. A este processo de verificação dá-se o nome de Verificação Formal. A geração automática do modelo elimina a necessidade de construção manual do mesmo, que requer muito esforço e conhecimento acerca de métodos formais, isso pode aumentar custos e tempo de desenvolvimento do sistema de software. Entretanto, a análise dinâmica é conhecida por apenas realizar cobertura sobre o comportamento atual de sistemas de software concorrentes, sem considerar a análise de todas as outras possíveis sequências de execuções devido ao não determinismo. Em razão do comportamento não determinístico, sistemas de software concorrentes são capazes de produzir resultados diferentes para a mesma entrada a cada nova execução. Deste modo, reproduzir o comportamento que leva sistemas de software concorrente à falha é uma tarefa complexa. O presente trabalho propõe um método para realizar verificação formal e dinâmica de sistemas de software concorrente capaz de capturar o comportamento não determinístico desses sistemas, além de proporcionar a redução de custos de desenvolvimento através da eliminação da necessidade de construção manual de modelos de sistemas de software concorrente. O método é validado através de um estudo de caso composto por testes em três sistemas de software.

Depurar sistemas distribuídos continua uma tarefa difícil, mesmo após 30 anos de pesquisa intensa. Embora essa situação possa ser parcialmente atribuída à complexidade das execuções concorrentes, o rápido passo de desenvolvimento das plataformas e tecnologias para computação distribuída também carrega a sua parcela de culpa, por encurtar a vida de muitas ferramentas potencialmente úteis. Neste trabalho, apresentamos uma análise dos principais problemas, técnicas e ferramentas ligados à depuração de sistemas concorrentes e discutidos na literatura. Baseados nessa análise, desenvolvemos e apresentamos uma nova técnica, simples e portátil, que pode ser aplicada a sistemas distribuídos que utilizam chamadas síncronas e bloqueantes. Essa técnica, concebida para sobreviver à heterogeneidade, é validada por meio da implementação de um arcabouço escrito para plataforma Eclipse e instanciado para sistemas de objetos distribuídos baseados em Java/CORBA. / After over thirty years of intense research, debugging distributed systems is still regarded as a difficult task. While this situation could be partially blamed on the fact that concurrent executions are complex, the fast pace of evolution witnessed with distributed computing technologies have also played its by shortening the lifespan of many potentially useful debugging tools. This work presents an analysis of the main issues, techniques and tools in the field of parallel, distributed, and concurrent debugging in general. Based on this analysis, we develop and present a simple and portable technique targeted at synchronous-call-based distributed systems. This technique, designed for portability, is validated through the implementation of an Eclipse-based framework that is instantiated for Java/CORBA distributed object systems.

Depurar sistemas distribuídos continua uma tarefa difícil, mesmo após 30 anos de pesquisa intensa. Embora essa situação possa ser parcialmente atribuída à complexidade das execuções concorrentes, o rápido passo de desenvolvimento das plataformas e tecnologias para computação distribuída também carrega a sua parcela de culpa, por encurtar a vida de muitas ferramentas potencialmente úteis. Neste trabalho, apresentamos uma análise dos principais problemas, técnicas e ferramentas ligados à depuração de sistemas concorrentes e discutidos na literatura. Baseados nessa análise, desenvolvemos e apresentamos uma nova técnica, simples e portátil, que pode ser aplicada a sistemas distribuídos que utilizam chamadas síncronas e bloqueantes. Essa técnica, concebida para sobreviver à heterogeneidade, é validada por meio da implementação de um arcabouço escrito para plataforma Eclipse e instanciado para sistemas de objetos distribuídos baseados em Java/CORBA. / After over thirty years of intense research, debugging distributed systems is still regarded as a difficult task. While this situation could be partially blamed on the fact that concurrent executions are complex, the fast pace of evolution witnessed with distributed computing technologies have also played its by shortening the lifespan of many potentially useful debugging tools. This work presents an analysis of the main issues, techniques and tools in the field of parallel, distributed, and concurrent debugging in general. Based on this analysis, we develop and present a simple and portable technique targeted at synchronous-call-based distributed systems. This technique, designed for portability, is validated through the implementation of an Eclipse-based framework that is instantiated for Java/CORBA distributed object systems.

[pt] Atualmente, podemos observar uma clara tendência na direção de sistemas cada vez maiores e mais complexos quanto às suas partes e formas de interconexão. Num cenário como este, torna-se imperativa a preocupação com a modelagem da estrutura, organização geral e formas de interação presentes nesses sistemas, assim como com as garantias de que certos requisitos críticos sejam atendidos. O contexto de nosso trabalho engloba disciplinas de Engenharia de Software, como Arquitetura de Software e Técnicas de Modelagem, e disciplinas mais formais como Verificação de Modelos, Lógicas Modais e Álgebras de Processos. Nosso trabalho tem inspirações nestas disciplinas mas apresenta, de fato, um cunho metodológico, localizando-se nas fronteiras da ES com Métodos Formais, onde buscamos investigar e estabelecer uma forma sistemática para utilização efetiva de métodos formais logo nas etapas iniciais do desenvo lvimento. Mais especificamente, mostramos como é possível, a partir de modelos baseados em abstrações arquiteturais, obter-se sistematicamente um modelo formal sobre o qual possamos realizar certos tipos de análise comportamental. Nossa proposta inclui um sistema notacional básico para expressar modelos arquiteturais, junto com sua semântica formal, e um protótipo construído para dar suporte a tarefas de especificação e análise formal orientadas por abstrações arquiteturais. Com isto, pretendemos abordar alguns dos aspectos essenciais de uma metodologia de desenvolvimento que integre ferramentas e técnicas formais na etapa de modelagem arquitetural. / [en] There is a trend nowadays towards bigger and more complex systems concerning their parts and interconnectivity. In such scenario, modeling structure, overall organization and interaction have become a main concern, as well as fulfillment of mission critical requirements. The scope of our work encompasses Software Engineering related subjects such as Software Architecture, Modeling Techniques and more formal disciplines like Model Checking, Modal Logics and Process Algebra. Although inspired by such techniques, there is, indeed a methodological orientation in our work, traversing the boundaries of Software Engineering with Formal Methods, through which we seek to investigate and establish a systematic way for the effective utilization of formal methods in the first steps of software development. Still, more specifically, we show how it is possible, starting from models based on architectural abstractions, to systematically produce a formal model upon which we can execute certain forms of behavior analysis. Our proposal includes a basic notational system to express architectural models along with their formal semantics and a prototype built to support specification and formal analysis tasks oriented by architectural abstractions. With this, we intend to stress some essential aspects of a development methodology which aims to integrate tools and formal techniques to software modeling.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-09-20T18:52:30Z No. of bitstreams: 1 PAULO EDUARDO E SILVA BARBOSA - TESE PPGCC 2011..pdf: 8460190 bytes, checksum: 711c8b40aaed80c81ec520880038d9b8 (MD5) / Made available in DSpace on 2018-09-20T18:52:30Z (GMT). No. of bitstreams: 1 PAULO EDUARDO E SILVA BARBOSA - TESE PPGCC 2011..pdf: 8460190 bytes, checksum: 711c8b40aaed80c81ec520880038d9b8 (MD5) Previous issue date: 2011-09-08 / MDA é uma tendência de desenvolvimento de software que visa alterar o foco e os esforços dos modelos de desenvolvimento atuais. O método de implementação deixa de ser apenas a produção e código, e passa a também envolver modelos, metamodelos e transformações. Atualmente, essa abordagem tem sido diversificada com a inclusão de novos paradigmas que vão bem além do uso exclusivo dos padrões da OMG, como proposto originalmente. Contudo, a arquitetura MDA ainda sofre com a falta de formalização de alguns de seus artefatos e processos, levando a vários tipos de questionamentos. Um exemplo pertinente de questionamento se dá sobre o alto grau de ambigüidade dos modelos e transformações, originando problemas de baixa confiabilidade. Uma das conseqüências disso é o fato de que atualmente não existe uma maneira de garantir que transformações MDA sejam preservadoras de semântica, e nem que seus modelos envolvidos nas transformações sejam formais o suficiente para se permitir o uso de técnicas deverificação de equivalência, gerando críticas sobre a eficácia dessa abordagem. Esta tese de doutorado propõe lidar com esse problema, incorporando abordagens consolidadas de métodos formais na arquitetura MDA, tendo como contexto específico o desenvolvimento de software para sistemas embarcados com características de concorrência. Propomos extensões para parte da arquitetura MDA para que se possa construir modelos semânticos que representem aspectos estáticos e dinâmicos, ambos essenciais na semântica dos modelos envolvidos nas transformações e nos mecanismos de verificação de equivalência desses modelos. Com isso,obtemos a verificação de equivalência em transformações envolvendo modelos de sistemas concorrentes. Como avaliação do trabalho, provas de conceito, estudos de caso e avaliação experimental seguindo a abordagem GQM, envolvendo parcerias na academia e na indústria através de sistemas reais, foram implementados e avaliados. Verificamos equivalência entre modelos ao nível de transformações PIM-para-PIM, PSM-para-PSM e PIMpara-PSM como modelos de sistemas concorrentes descritos em redes de Petri e algumas de suas extensões. / MDA is a software development trend that aims to shift the focus and efforts of the current development methodologies. The implementation method changes from only code production to the usage of models, metamodels and transformations. Currently, this approach has been diversified with the inclusion of new paradigms that go beyond the only use of the MDA standards, as originally proposed. However, the MDA architecture still suffers from the lack of formalization of its artifacts and processes, leading to several sorts of questions. An important example of question is about the high ambiguity levels of models and transformations, originating problems of low reliability. One of the main consequences of this problem is the fact that still there is no way to ensure that MDA transformations are semantics preserving and neither the involved models are formal enough to allow the use of equivalence verification techniques, criticizing the effectiveness of this approach. This thesis proposes to deal with this problem by incorporating well consolidated formal methods techniques in the MDA architecture, having as specific context the software development for embedded systems with concurrent features. We propose extensions to part of the MDA architecture in order to construct semantic models to represent static and dynamic aspects, both essentials in the semantics of the involved models in the transformations and in the verification mechanisms of these models. With this, we achieve the verification of equivalence in transformations with models of concurrent systems. Asevaluationofthework,conceptualproofs, case studies and an experimental evaluation following the GQM approach, involving partners in the academy and industry, were implmented and evaluated. We verify models equivalence at the level of PIM-to-PIM, PSM-to-PSM and PIM-to-PSM transformations with models of concurrent systems described and inPetri nets and some of its extensions.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-22T19:52:23Z No. of bitstreams: 1 ANA EMÍLIA VICTOR BARBOSA - DISSERTAÇÃO PPGCC 2007..pdf: 1669761 bytes, checksum: f47054507fe9200c8d1d56d2848ae276 (MD5) / Made available in DSpace on 2018-08-22T19:52:23Z (GMT). No. of bitstreams: 1 ANA EMÍLIA VICTOR BARBOSA - DISSERTAÇÃO PPGCC 2007..pdf: 1669761 bytes, checksum: f47054507fe9200c8d1d56d2848ae276 (MD5) Previous issue date: 2007-04-20 / Capes / Neste trabalho propomos uma técnica que visa detectar violações de propriedades comportamentais automaticamente durante a execução de sistema de software concorrentes. A técnica foi inspirada na metodologia de desenvolvimento Design by Contract (DbC). DbC permite que os desenvolvedores adicionem aos programas asserções para que sejam verificadas em tempo de execução. O uso de asserções para expressar propriedades de programas concorrentes (multithreaded)eparalelos, entretanto,não ésuficiente. Nesses sistemas,muitas das propriedades comportamentais de interesse, como vivacidade e segurança, não podem ser expressas apenas com asserções. Essas propriedades requerem o uso de operadores temporais. Neste trabalho, utilizamos Lógica Linear Temporal (Linear Time Logic - LTL) para expressar o comportamento desejado. Para dar suporte a checagem do comportamento dos programas em tempo de execução, propomos uma técnica baseada em Programação Orientada a Aspectos, que permite que o programa seja continuamente monitorado (o comportamento é checado através do uso de autômatos que permite a deteção de comportamentos inesperados). Associada a cada propriedade comportamental existe um conjunto de pontos de interesse do código-fonte que devem obedece-la. Esses pontos são então monitorados durante a execução do sistema através do uso de aspectos. Entre outros benefícios, a técnica permite que o sistema de software alvo seja instrumentado de maneira não intrusiva, sem alterar o código-fonte — particulamente, nenhum código do software alvo deve ser modificado para execução da monitoração. Para validar este trabalho, desenvolvemos como prova de conceitos um protótipo que implementa a técnica e permite a monitoração de programas Java multi-threaded, chamado DesignMonitor. Essa ferramenta é apresentada e discutida através de um estudo de caso para demonstrar a aplicação da técnica / In this work we propose and develop a technique that allows to detect the violation of behavior properties of concurrent systems. The technique was inspired by the Design by Contract (DbC) programming methodology, which proposes the use of assertions and their evaluation at runtime to check programs behavior. The use of simple assertions to express properties of concurrent and parallel programs, however, is not sufficient. Many of the relevant properties of those systems,s uch as liveness and security, can not be expressed with simple assertions. Thesepropertiesrequiretheuseof temporal operators. In our work, we used Linear Time Logic (LTL) to specify the expected behavior. To support the runtime checking of the program against the expected behavior, we propose a technique, based on Aspect-Oriented Programming, that allows the program to be continuously monitored (behavior is checked against automata that allows the detection of unexpected behaviors). Each property is mapped to a set of points of interest in the target program. Those points are then monitored during the system execution through aspects. Among other benefits, the technique allows the instrumentation of the target software to be performed automatically and in a non-intrusive way — in particular, no code must be changed toturn monitoring on or off. To validate the work, we developed a proof of concept prototype tool that implements the technique and allows the monitoring of multi-threaded Java programs, called DesignMonitor. The tool was used in case study that has allowed the evaluation and the discussion of practical issues related with the technique.