Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-07-12T12:30:10Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO (2015-08-17) - RAFAEL BRANDAO LOBO.pdf: 1015468 bytes, checksum: d543b6f16adc4ce4d3aa4d59c8d546ff (MD5) / Made available in DSpace on 2016-07-12T12:30:10Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO (2015-08-17) - RAFAEL BRANDAO LOBO.pdf: 1015468 bytes, checksum: d543b6f16adc4ce4d3aa4d59c8d546ff (MD5) Previous issue date: 2015-07-17 / CAPEs / Deadlocks are a common type of concurrency bug. When a deadlock occurs, it is difficult to clearly determine whether there is an actual deadlock or if the application is slow or hanging due to a different reason. It is also difficult to establish the cause of the deadlock. In general, developers deal with deadlocks by using analysis tools, introducing application-specific deadlock detection mechanisms, or simply by using techniques to avoid the occurrence of deadlocks by construction. In this paper we propose a different approach. We believe that if deadlocks manifest at runtime, as exceptions, programmers will be able to identify these deadlocks in an accurate and timely manner. We leverage two insights to make this practical: (i) most deadlocks occurring in real systems involve only two threads acquiring two locks (TTTL deadlocks); and (ii) it’s possible to detect TTTL deadlocks efficiently enough for most practical systems. We conducted a study on bug reports and found that more than 90% of identified deadlocks were indeed TTTL.We extended Java’s ReentrantLock class to detect TTTL deadlocks and measured the performance overhead of this approach with a conservative benchmark. For applications whose execution time is not dominated by locking, the overhead is estimated as below 6%. Empirical usability evaluation in two experiments showed that students finished tasks 16.87% to 30.7% faster on the average using our approach with the lock being the most significant factor behind it, and, in one of the experiments they were able to identify the defects more accurately with a signficant 81.25% increase in the number of correct answers when deadlock exceptions where present. / Deadlocks são um tipo comum de bug de concorrência. Quando um deadlock acontece, é difícil determinar claramente se houve um deadlock de verdade ou se a aplicação está lenta ou travada por qualquer outro motivo. Também é difícil estabelecer a causa do deadlock. Em geral, desenvolvedores lidam com deadlocks de várias maneiras: utilizando ferramentas analíticas; utilizando mecanismos especificos da aplicação para detectar deadlocks; ou simplesmente usando técnicas para evitar a ocorrência de deadlocks no momento da construção do código. Neste trabalho, propomos uma abordagem diferente. Acreditamos que se deadlocks se manifestarem durante a execução na forma de exceções, programadores serão capazes de identificar esses deadlocks de forma mais precisa e mais rápida. Levamos em consideração alguns aspectos para tornar esta abordagem prática: (i) a maioria dos deadlocks que ocorrem em sistemas reais envolvem apenas duas threads adquirindo dois locks ou two-thread, two-lock (TTTL) deadlock; e (ii) é possível detectar TTTL deadlocks de forma suficientemente eficiente para uso prático na maioria dos sistemas. Conduzimos um estudo com bugs reportados em sistemas de software de larga escala e descobrimos que mais de 90% dos bugs identificados como deadlocks eram de fato TTTL. Extendemos a classe ReentrantLock de Java para detectar TTTL deadlocks e medimos seu overhead na performance com um benchmark bastante conservador onde medimos o overhead das operações de trava quando deadlocks não são possíveis. Para aplicações cujo tempo de execução não é dominado por travas, o impacto médio no tempo de execução é na ordem de 6%. Realizamos uma avaliação empírica para testar usabilidade através de dois experimentos. Nesta avaliação, mostramos que, em média, estudantes terminam tarefas de 16.87% a 30.7% mais rapidamente usando nossa abordagem, sendo o tipo de abordagem o fator de maior significância e, em um dos experimentos, estudantes foram capazes de identificar mais corretamente a causa dos bugs, mostrando que o número de respostas corretas aumentou significativamente em 81.25% quando as exceções propostas estavam presentes.

This work aims at improving an existing soft microprocessor core optimized for Xilinx Virtex®-4 FPGA. Instruction and data caches will be designed and implemented. Interrupt support will be added as well, preparing the microprocessor core to host operating systems. Thorough verification of the added modules is also emphasized in this work. Maintaining core clock frequency at its maximum has been the main concern through all the design and implementation steps.

Um sistema de software que apresente problemas em sua execução pode gerar conseqüências desde um simples incômodo ao usuário, até desastres como a perda de uma sonda da NASA em Marte. As atividades de teste visam identificar erros nos sistemas de software, prevenindo estas conseqüências indesejáveis. Porém, os testes podem envolver entre 30% e 40% do esforço de desenvolvimento do sistema, e em sistemas críticos, seu custo pode ser de 3 a 5 vezes maior do que o custo combinado das demais atividades. Para tentar reduzir estes custos podemos automatizar parte das atividades. No presente caso, pretende-se minimizar os casos de teste gerados manualmente, utilizando uma técnica denominada verificação de modelos. Esta técnica consiste em verificar propriedades definidas formalmente através de expressões matemáticas, utilizando uma ferramenta de verificação que simula a execução do código. Além disso, um sistema que utilize um tratamento de condições excepcionais eficiente, tem sua manutenibilidade, robustez e confiabilidade melhoradas. Por isso, definimos propriedades relacionadas ao tratamento de exceções, como ponto de entrada para a verificação de modelos. Apresentamos um ambiente de testes criado para permitir a verificação destas propriedades com o verificador Java PathFinder e a exibição das estatísticas de cobertura de testes de acordo com o critério selecionado. Este ambiente facilita a execução dos testes, pois apresenta uma interface gráfica com o usuário que permite a configuração e execução dos testes sem que seja necessária a escrita de código pelo testador. Apresentamos também o resultado do uso deste ambiente para o teste de vários programas exemplo, utilizando desde código concorrente até diferentes estratégias de tratamento de exceção e discutimos as características, cuidados no uso e limitações das ferramentas utilizadas. / A software system that shows some failure at runtime execution may bring consequences that range from a simple user annoyance to great disasters such as the lost NASA probe on Mars. The test activities aim to find errors in software systems, preventing these undesirable consequences. However, tests may take between 30% and 40% of total development time, and on critical systems, its cost can be from 3 to 5 times greater than the combined cost of the other activities. In an effort to reduce these costs, we may automate some of the activities. In this work we intend to minimize test case manual generation, using a technique called model checking. This technique involves the checking of properties defined through the use of mathematical formulas, using a tool, that simulates code execution. In addition, a system with an efficient exception handling mechanism, has its maintainability, robustness and reliability enhanced. So, in this work we define exception handling related properties, as an input for model checking. We present a test tool created to allow checking of these properties using the Java PathFinder model checker, and to list the test coverage statistics, according to the selected test criteria. This tool makes easy the test execution, since it presents a graphical user interface that allows configuration and running of tests with no need to write any lines of code. We also show the results of running several tests with the GUI, using some programs implemented with concurrent code and several exception handling techniques and discuss the main features, pitfalls and limitations of the underlying tools.

A área de gerenciamento de processos de negócio apresenta-se ativa e tem recebido atenção tanto da comunidade de pesquisa como da indústria. Uma das principais preocupações nessa área é a escolha da melhor abordagem para modelagem e implementação de processos de negócio. Atualmente, organizações possuem processos de negócio com complexas estruturas que são reavaliados e ajustados com frequência, exigindo flexibilidade das linguagens para modelagem de processos. Além disso, processos de negócio atuais também exigem ambientes para implementação capazes de garantir confiabilidade na execução de instâncias do processo modelado, especialmente em caso de falhas. Embora diversos modelos transacionais tenham sido propostos com o objetivo de garantir propriedades transacionais adaptadas ao contexto de processos de negócio, a implementação de processos transacionais ainda oferece um cenário com desafios teóricos e práticos. Neste trabalho apresentamos uma implementação da abordagem WED-flow para controle de processos transacionais. A WED-flow é uma abordagem que combina conceitos de modelos transacionais avançados, eventos e estados de dados com o objetivo principal de reduzir a complexidade no tratamento de exceções. A ferramenta de software desenvolvida é capaz de controlar a execução de instâncias de processos de negócio, permite a evolução incremental do modelo projetado e ainda disponibiliza a estrutura necessária para apoiar a implementação de mecanismos de recuperação para tratar interrupções em instâncias causadas por exceções. / Business processes management is an active area which have received increased attention from research and industry communities. A major concern is the selection of the best approach for modeling and implementing business processes. Nowadays, organizations have business processes with complex structures, which are reevaluated and adjusted frequently, requiring flexibility from modeling languages. In addition, current business processes also require implementation environments capable of ensuring execution reliability, especially in case of failures. Although several transactional models have been proposed in order to guarantee transactional properties adapted to the context of business processes, the implementation of transactional processes still offers a scenario with several theoretical and practical challenges. In this work, we present an implementation of WED-flow approach for controlling transactional processes. WED-flow is an approach which combines the concepts of advanced transactional models, events and data states for the purpose of reducing exception handling complexity. The developed software tool is able of controlling the execution of business processes instances, allows incremental evolution of the designed model and also provides the necessary structure to support recovery mechanisms implementation to handle instances interruptions caused by exceptions.

[pt] Mecanismos de tratamento de exceções são modelos comumente usados em linguagens de programação para a estruturação do fluxo de execução excepcional de módulos de software. Tais mecanismos possibilitam a detecção e a sinalização da ocorrência de exceções, permitindo que módulos de software tomem medidas corretivas que recuperem o sistema para um estado correto. Estudos recentes mostram que falhas recorrentes e problemas de desempenho em aplicações de software estão relacionados à má qualidade do código que implementa o tratamento de exceções. Os estudos preliminares realizados no contexto desta dissertação não apenas corroboram esses resultados, como também evidenciam uma série de outros fatos interessantes que ocorrem durante a evolução de sistemas de software. Em especial, percebeu-se que é bastante comum nas versões preliminares de um sistema a implementação de ações de tratamento de exceções ineficazes. Também se percebeu que pouco (ou nenhum) esforço é realizado em termos de melhorar o tratamento de exceções durante a evolução do sistema de software. Os trabalhos recentes que se propõem a auxiliar desenvolvedores de software a lidar com código de tratamento de exceções falham em auxiliá-los em uma tarefa primordial: implementar código de tratamento de exceções bem estruturado desde as primeiras versões de um sistema. Neste contexto, o presente trabalho propõe um sistema de recomendação capaz de prover exemplos de código tratando exceções de modo a auxiliar desenvolvedores a implementarem seu próprio código em suas aplicações. O sistema extrai informações estruturais do código sob desenvolvimento para buscar por exemplos em um repositório local a fim de recomendar exemplos de código com contexto parecido ao que o desenvolvedor está trabalhando. O sistema implementado neste trabalho recomenda exemplos de código implementados em Java. / [en] Exception handling mechanisms are models commonly used in programming languages to structure the exceptional execution flow of software modules. These mechanisms enable the detection and signaling of exception occurrences, allowing these modules to take corrective actions to recover a module to a correct state. Recent studies show that recurrent failures and performance issues in software applications are related to the poor structuring of exception handling code. The preliminary studies performed in the context of this dissertation not only confirm these results, but also show other interesting facts that occur during software evolution. In particular, it was realized that it is often very common to observe ineffective exception handling actions in the first releases of a system. It was also realized that little (or no) effort was allocated to improve the quality of these action during the software evolution. Recent studies that aim aiding software developers to deal with exception handling elements fail in assisting them in a crucial task: implementing well-structured exception handling code since the first release of a system. In this context, this dissertation proposes a recommender system able to provide code fragments implementing exception handling code. The proposed strategy aims to assist developers in implementing their own code in their applications. The system extracts structural information from the code under development to search for examples in a local repository in order to recommend code examples that share similar structural context with the code that the developer is working on. The system implemented in the context of this dissertation recommends code examples implemented in Java.

The main purpose of exception handling mechanisms is to improve software robustness by handling exceptions when they occur. However, empirical evidence indicates that improper implementation of exception handling code can be a source of faults in software systems. There is still limited empirical knowledge about the relationship between exception handling code and defects. In this dissertation, we present three case studies investigating defect densities of exception handling code. The results show that in every system under study, the defect density of exception handling code was significantly higher than the defect density of overall source code and normal code. The ability to predict the location of faults can assist in directing quality enhancement efforts to modules that are likely to have faults. This information can be used to guide test plans, narrow the test space, and improve software quality. We hypothesize that complicated exception handling structure is a predictive factor that is associated with defects. To the best of our knowledge, no study has addressed the relationship between the attributes of exception handling method call structures and defect occurrence, nor has prior work addressed fault prediction. We extract exception-based software metrics from the structural attributes of exception handling call graphs. To find out whether there are patterns of relationship between exception-based software metrics and fault-proneness, we propose a defect prediction model using exception handling call structures. We apply the J48 algorithm, which is the Java implementation of the C4.5 algorithm, to build exception defect prediction models. In two out of three systems under study, the results reveal that there are logical patterns of relationships between most class level exception metrics and fault-proneness. The accuracy of our prediction models is comparable to the results of defect prediction model studies in the literature. It was observed that our approach has somewhat worse predictive accuracy when a system has low average defects per class.

No description available.

<p>Programs have multiple exits in the presence of certain control structures, e.g., exception handling and coroutines. These control structures offer flexible manipulations of control flow. However, their formalizations are overall specialized, which hinders reasoning about combinations of these control structures.</p> <p>In this thesis, we propose a unifying theory of multi-exit programs. We mechanically formalize the semantics of multi-exit programs as indexed predicate transformers, a generalization of predicate transformers by taking the tuple of postconditions on all exits as the parameter. We explore their algebraic properties and verification rules, then define a normal form for monotonic and for conjunctive indexed predicate transformers. We also propose a new notion of fail-safe correctness to model the category of programs that always maintain certain safe conditions when they fail, and a new notion of fail-safe refinement to express partiality in software development.</p> <p>For the indexed predicate transformer formalization, we illustrate its applications in three models of multi-exit control structures: the termination model of exception handling, the retry model of exception handling, and a coroutine model. Additionally, for the fail-safe correctness notion and the fail-safe refinement notion, we illustrate their applications in the termination model. Six design patterns in the termination model and one in the retry model are studied. All the verification rules and design patterns in the thesis have been formally checked by a verification tool.</p> / Doctor of Philosophy (PhD)

Atualmente, diversas empresas e organizações estão cada vez mais empreendendo esforços para transformar rapidamente as suas potenciais ideias em produtos e serviços. Esses esforços também têm estimulado a evolução dos sistemas de informação que passaram a ser apoiados por modelos de alto nível de abstração para descrever a lógica do processo. Neste contexto, destaca-se o sucesso dos Sistemas de Informação cientes de Processos (PAIS, do inglês Process-Aware Information Systems) para o gerenciamento de processos de negócios e automação de processos científicos de larga escala (e-Science). Grande parte do sucesso dos PAIS é devido à capacidade de prover funcionalidades genéricas para modelagem, execução e monitoramento dos processos. Essas características são bem-sucedidas quando os modelos de processos têm um caminho bem-comportado no sentido de atingir os seus objetivos. No entanto, situações anômalas que desviam a execução desse caminho bem-comportado ainda representam um significativo desafio para os PAIS. Por causa dos vários tipos de falhas que desviam a execução do comportamento esperado, prover uma execução robusta e confiável é uma tarefa complexa para os atuais PAIS, uma vez que nem todas as situações de falha podem ser eficientemente descritas dentro da estrutura do fluxo tradicional. Como consequência, o tratamento de tais situações geralmente envolve intervenções manuais nos sistemas por operadores humanos, o que resulta em custos adicionais e significativos para as empresas. Neste trabalho é introduzido um método de composição para recuperação ciente de custos e benefícios que é capaz de encontrar e seguir caminhos alternativos que reduzam os prejuízos financeiros do tratamento de exceções. Do ponto de vista prático, esse método provê o tratamento de exceção automatizado e otimizado ao calcular os custos e benefícios de cada caminho de recuperação e escolher o caminho com a melhor relação custo-benefício disponível. Mais especificamente, o método de recuperação proposto estende a abordagem WED-flow (Workflow, Event processing and Data-flow) para permitir a composição ciente de custos e benefícios de passos de recuperação transacionais backward e forward. Por fim, os experimentos mostram que esse método de recuperação pode ser adequadamente incorporado para manipular exceções em uma ampla variedade de processos. / Nowadays, many corporations and organizations are increasingly making efforts to transform quickly and effectively their potential ideas into products and services. These efforts have also stimulated the evolution of information systems that are now supported by higher-level abstract models to describe the process logic. In this context, several sophisticated Process-Aware Information Systems (PAIS) have successfully been proposed for managing business processes and automating large-scale scientific (e-Science) processes. Much of this success is due to their ability to provide generic functionality for modeling, execution and monitoring processes. These functionalities work well when process models have a well-behaved path towards achieving their objectives. However, anomalous situations that fall outside of the well-behaved execution path still pose a significant challenge to PAIS. Because of the many types of failures that may deviate execution away from expected behaviors, provision of robust and reliable execution is a complex task for current PAIS, since not all failure situations can be efficiently modeled within the traditional flow structure. As a consequence, the treatment for such situations usually involves interventions in systems by human operators, which result in significant additional cost for businesses. In this work, we introduce a cost/benefit-aware recovery composition method that is able to find and follow alternative paths to reduce the financial side effects of exception handling. From a practical point of view, this method provides the automated and optimized exception handling, by calculating the cost and benefits of each recovery path, and choosing the recovery path with the best cost/benefits available. More specifically, our recovery method extends the WED-flow (Workflow, Event processing and Data-flow) approach for enabling cost/benefit-aware composition of forward and/or backward transactional recovery steps. Finally, the experiments point out that this recovery method can be suitably incorporated into exception handling within a wide variety of processes.

A adoção em larga escala de redes de computadores e gerenciadores de banco de dados contribuiu para o surgimento de sistemas de informação complexos. Atualmente, estes sistemas tornaram-se elementos essenciais na vida das pessoas, dando suporte a processos de negócio e serviços corporativos indispensáveis à sociedade, como automação bancária e telefonia. A utilização de componentes na estruturação destes sistemas promove maior qualidade e flexibilidade ao produto e agiliza o processo de desenvolvimento. Entretanto, para que estes benefícios sejam totalmente observados, é fundamental que os provedores de componentes de prateleira projetem especificações precisas, completas e consistentes. Geralmente, as especificações omitem ou negligenciam o comportamento dos componentes nas situações de falha. Desta forma, a utilização de componentes não confiáveis, cujos comportamentos não podem ser inteiramente previstos, compromete seriamente o projeto de sistemas tolerantes a falhas. Uma estratégia para a especificação de componentes tolerantes a falhas é informar a ocorrência de erros através de exceções e realizar a recuperação dos mesmos por rotinas de tratamento correspondentes. A especificação deve separar claramente o comportamento normal do excepcional, destinado à recuperação do erro. Entretanto, em sistemas concorrentes e distribuídos, a especificação apenas deste tratamento local não é suficiente. Uma exceção pode ser lançada em decorrência de erros sistêmicos (i.e. problemas de rede) que afetam todo o sistema. Assim, determinadas exceções devem ser tratadas em nível arquitetural, envolvendo os demais componentes no tratamento. O modelo conceitual de ações Atômicas Coordenadas (ações CA - Coordinated Atomic actions), bastante aplicado na estruturação de sistemas tolerantes a falhas, define um mecanismo geral para a coordenação do tratamento excepcional dos componentes, que cooperam na execução das atividades e competem por recursos compartilhados. Portanto, o modelo de ações CA oferece uma solução potencialmente viável para a especificação do tratamento de exceções em nível arquitetural. Este trabalho propõe um framework para a especificação do tratamento de exceções em nível arquitetural, baseando-se no modelo de aninhamento de ações CA e utilizando a linguagem orientada a eventos CSP (Communicating Sequential Processes). Sua principal característica é prover um protocolo padronizado para a coordenação do tratamento de exceções, que envolve a cooperação dos componentes do sistema. Além disso, é apresentada uma estratégia para a verificação formal dos sistemas na ferramenta FDR (Failure Divergence Refinement), com base no modelo de refinamento por rastros. / The widespread scale adoption of computer networks and database management systems has contributed to the arising of complex information systems. Nowadays, these systems have become essential aspects in the everyday life, supporting business processes and indispensable enterprise services to society such as banking automation and telephony. The usage of components in structuring of these systems promotes higher quality and flexibility to the product and accelerates the software development process. However, in order to fully observe the benefits it is essential that the suppliers of these COTS (commercial off-the-shelf) design precise, complete and consistent specifications. Generally, the specifications omit or neglect the behavior of these components in exceptional situations. Therefore, the usage of untrustworthy components whose behavior cannot be entirely foreseen seriously compromise the design of fault-tolerant systems. One of the strategies used for the specification of fault-tolerant components is to inform the occurrence of errors through exceptions and make its recovering by the correspondent exception handling routines. The specification should separate clearly the normal behavior from the exceptional one, specially designed for error recovery. However, in concurrent and distributed systems, specification of local exception handling is not enough. An exception could be raised as a result of systemic errors (i.e. network errors) which affect the entire system, thus specific types of exceptions should be treated at an architectural level involving all the other components in this handling activity. The conceptual model of Coordinated Atomic (CA) actions, often applied in the structuring of fault-tolerant systems, defines a general mechanism for coordination of exception handling with components that cooperate while executing activities and compete for shared resources. Therefore, the model of CA actions offers a perfectly viable solution for the specification of exception handling at an architectural level. This work proposes a framework for the specification of exception handling at an architectural level, based on the nesting model of CA actions and using the event-oriented language CSP (Communicating Sequential Processes). Its main characteristic is to provide a standardized protocol for coordination of exception handling that involves the cooperation of system components. Moreover, it is presented a formal strategy for system verification using the FDR (Failure Divergence Refinement) tool, based on the traces refinement model.