Utilize este identificador para referenciar este registo: http://hdl.handle.net/10451/15867
Título: Cooperative testing of multitihreaded Java applications
Autor: Simões, Miguel Ângelo Marques
Orientador: Martins, Francisco Cipriano da Cunha, 1972-
Marques, Eduardo Resende Brandão
Palavras-chave: Testes de software
Semântica cooperativa
Threads
Java
Teses de mestrado - 2014
Data de Defesa: 2014
Resumo: Para desenvolver programas concorrentes, o modelo de programação prevalente é o uso de threads. Uma thread define uma linha de execução sequencial num programa, em que partilha o espaço de memória com todas as outras threads que estão a executar o programa ao mesmo tempo. Além de memória partilhada, as threads de um programa também interagem mediante primitivas de concorrência como locks ou barreiras. O uso de threads é suportado por alguma das linguagens de programação mais conhecidas e utilizadas, como por exemplo, o Java ou C. Em programas multithreaded, erros de programação são fáceis de cometer, com o uso de memória partilhada e primitivas de interacção. Por exemplo, a partilha de memória entre as threads pode levar a condições de corrida sobre os dados (data races), e inerente inconsistência de valores para os mesmos. Outro problema típico é a ocorrência de impasses (deadlocks) no uso de primitivas de concorrência, como locks, que não permitem que uma ou mais threads progridem na sua execução. Quando um bug se manifesta, um programador normalmente tenta determinar manualmente a sua origem, através de t´técnicas de debugging, e/ou executa o conjunto de testes associados ao programa, observando em quais testes são reportados erros. Frequentemente, estas duas abordagens falham para programas multithreaded. A razão para estas dificuldades é que numa execução¸ com múltiplas threads as mudanças de contexto acontecem de forma não-determinista, o que torna impossível observar e controlar de forma precisa o fluxo de execução¸ e escalonamento de threads associado. Ao mesmo tempo, os bugs tipicamente apenas se manifestam num sub-conjunto de todos os escalonamentos possíveis, e com frequência apenas em escalonamentos bastante específicos e difíceis de reproduzir. Um teste de software pode ser repetido imensas vezes, sem expor um bug. Se e quando este é detectado, pode ser extremamente difícil identificar e replicar o fluxo de execução¸ ocorrido. Até padrões de bugs relativamente simples são difíceis de detectar e replicar com precisão (por exemplo, ver [9]). Esta tese trata do problema geral de testar programas concorrentes escritos em Java [16], de modo a que bugs possam ser descobertos e replicados de forma determinista. A nossa abordagem passa pela execução¸ de testes de software com semântica cooperativa [23, 24]. A observação fundamental subjacente ao uso de semântica cooperativa é que as mudanças de contexto relevantes entre threads acontecem apenas nos pontos de potencial interferência entre estas, tais como o acesso a dados partilhados ou o uso das primitivas para concorrência, chamados yield points cooperativos. Uma execução¸ é considerada cooperativa se o código entre dois yield points consecutivos da mesma thread executa de forma sequencial como uma transação, sem qualquer interferência de outras threads. A semântica cooperativa pode ser explorada para testes de software deterministas, em que a reproducibilidade de execução é garantida, e a cobertura sistemática do espaço de estados de escalonamento possa ser efectuada. A ideia base é executar as threads com semântica cooperativa, por forma a que a execução repetida de um teste possa explorar o espaço de estados de forma controlada e customizada, e até eventualmente exaustiva. Esta técnica é usada em algumas ferramentas [3, 7, 17] para programas concorrentes escritos em C/C++. Nesta tese nós apresentamos o desenho, implementação e avaliação de uma ferramenta de testes cooperativa para programas concorrentes escritos em Java. A ferramenta desenvolvida chama-se Cooperari e está disponível em https://bitbucket.org/edrdo/Cooperari . Tanto quanto pudemos determinar pela avaliação do estado da arte, trata-se da primeira ferramenta de testes cooperativos para programas em Java. As contribuições desta tese são as seguintes:• A ferramenta instrumenta o bytecode Java da aplicação, por forma a interceptar yield points na execução, e a tornar a execução cooperativa. Os yield points suportados concernem operações sobre monitores Java (operações de locking e primitivas de notificação), operações do ciclo de vida de uma thread definidos na API java.lang.Thread, e ainda acessos (de leitura e escrita) a campos de objectos ou posições de vectores. A instrumentação dos yield points é definida recorrendo à linguagem AspectJ [14]. • Para a execução cooperativa definimos um ambiente de execução, que compreende um escalonador (scheduler) cooperativo e uma implementação cooperativa de monitores Java e operações do ciclo de vida de uma thread. O escalonador cooperativo condiciona o escalonador nativo da máquina virtual Java (que se mantém activo), por forma a se obter uma semântica cooperativa na execução. Aquando da intercepcão de um yield point, o escalonador cooperativo toma controlo da execução, e deterministicamente seleciona a próxima thread que irá executar.• Desenvolvimento de duas políticas de cobertura. A escolha feita num passo de escalonamento é determinado pela política de cobertura do espaço de estados de escalonamentos. A primeira delas simplesmente escolhe a próxima thread a executar de forma pseudo-aleatória, sem manter estado entre várias execuções de um programa/teste; para execução determinista, o gerador de números aleatórios é inicializado com uma semente fixa. A outra política mantém um histórico de decisões de escalonamento anteriores, por forma a evitar decisões repetidas de escalonamento para o mesmo estado do programa.• Implementação de mecanismos de monitorização em tempo de execução para a deteção de data races e alguns tipos de deadlock. É assinalado um erro quando na monitorização do acesso aos dados ´e verificado que para a mesma variável ou posição do vector está a ser acedido por duas threads, em que uma delas está a escrever e a outra está a escrever ou ler. Nós detectamos deadlocks verificando se existe ciclos nas dependências dos locks ou se alguma thread está bloqueada eternamente pois está à espera de uma notificação. • A ferramenta está integrada com o JUnit [20], o popular ambiente de testes para programas Java. Os programadores de testes podem usar a ferramenta JUnit da forma usual, recorrendo apenas a anotações adicionais às classes de teste. Na nossa ferramenta adicionamos novas anotações no JUnit, como por exemplo a definição da pasta que se deve instrumentar, o critério de avaliação para os testes e ainda uma que define que a execução irá ser cooperativa (execução por nós desenvolvida). Após a execução de um teste, a nossa ferramenta detecta se ocorreu um erro, se sim termina a execução, se não irá executar mais testes até cobrir a política ou então ter atingido o número máximo de execuções. • A ferramenta foi avaliada com exemplos de programas multithreaded retirados dos repositórios ConTest e SIR, referenciados na literatura. No caso geral, a ferramenta consegue detectar e replicar deterministicamente os bugs dos programas em causa, em contraste a testes com execução preemptiva que na vasta maioria dos casos não o consegue fazer.
Software bugs are easy to introduce in multithreaded programs, resulting in wellknown errors, such as data races in the use of shared memory among threads, or deadlocks when using multithread primitives like locks. These bugs are hard to detect, replicate, and trace precisely, and are typically manifested only for a subset of all possible thread interleavings, many times even for a very particular thread interleaving. At the same time, given the non-determinism and irreproducibility of scheduling decisions at runtime, it is generally hard to control and observe thread interleaving and explore the associated state-space appropriately, when programming/executing software tests for a multithreaded program. This thesis presents Cooperari, a tool for deterministic testing of multithreaded Java programs, based on the use of cooperative semantics. In a cooperative execution, threads voluntarily suspend at interference points (e.g., lock acquisition, shared data access), called yield points, and the code between two consecutive yield points of the same thread always executes serially as a transaction. A cooperative scheduler takes over control at yield points and deterministically selects the next thread to run. A program test runs multiple times, until it either fails or the state-space of thread interleavings is deemed as covered by a configurable policy that is responsible for the scheduling decisions. Beyond failed assertions in software tests, some types of deadlock and data races are also detected by Cooperari at runtime. The tool integrates with the popular JUnit framework for Java software tests, and was evaluated using standard benchmark programs. Cooperari can find, characterize, and deterministically reproduce bugs that are not detected under unconstrained preemptive semantics.
Descrição: Tese de mestrado, Engenharia Informática (Engenharia de Software), Universidade de Lisboa, Faculdade de Ciências, 2014
URI: http://hdl.handle.net/10451/15867
Designação: Mestrado em Engenharia Informática (Engenharia de Software)
Aparece nas colecções:FC-DI - Master Thesis (dissertation)

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
ulfc112244_tm_Miguel_Simões.PDF480,96 kBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.