Submitted by Isaac Francisco de Souza Dias (isaac.souzadias@ufpe.br) on 2016-01-19T17:42:17Z
No. of bitstreams: 2
license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5)
dissertation.pdf: 864300 bytes, checksum: 624346f890c947cf26d691a5fc74d707 (MD5) / Made available in DSpace on 2016-01-19T17:42:17Z (GMT). No. of bitstreams: 2
license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5)
dissertation.pdf: 864300 bytes, checksum: 624346f890c947cf26d691a5fc74d707 (MD5)
Previous issue date: 2015-04-24 / FACEPE / Probabilistic software analysis aims at quantifying how likely a target event is to occur,
given a probabilistic characterization of the behavior of a program or of its execution environment.
Examples of target events may include an uncaught exception, the invocation of a certain method,
or the access to confidential information. The technique collects constraints on the inputs that
lead to the target events and analyzes them to quantify how likely it is for an input to satisfy the
constraints. Current techniques either handle only linear constraints or only support continuous
distributions using a “discretization” of the input domain, leading to imprecise and costly results.
This work proposes an iterative distribution-aware sampling approach to support probabilistic
symbolic execution for arbitrarily complex mathematical constraints and continuous
input distributions. We follow a compositional approach, where the symbolic constraints are
decomposed into sub-problems whose solution can be solved independently. At each iteration
the convergence rate of the computation is increased by automatically refocusing the analysis
on estimating the sub-problems that mostly affect the accuracy of the results, as guided by
three different ranking strategies. Experiments on publicly available benchmarks show that the
proposed technique improves on previous approaches in terms of scalability and accuracy of the
results. / Análise Probabilística de Software (PSA) visa a quantificar a probabilidade de que um
evento de interesse seja alcançado durante a execução de um programa, dada uma caracterização
probabilística do comportamento do programa ou do seu ambiente de execução. O evento
de interesse pode ser, por exemplo, uma exceção não capturada, a invocação de um método
específico, ou o acesso à informação confidencial. A técnica coleta restrições sobre as entradas
que levam para os eventos de interesse e as analisa para quantificar o quão provável que uma
entrada satisfaça essas restrições. Técnicas atuais ou suportam apenas restrições lineares, ou
suportam distribuições contínuas utilizando uma "discretização" do domínio de entrada, levando
a resultados imprecisos e caros.
Este trabalho apresenta uma abordagem iterativa, composicional e sensível às distribuições
para suportar o uso de PSA em restrições com operações matemáticas arbitrariamente
complexas e distribuições contínuas de entrada. Nossa abordagem composicional permite que as
restrições sejam decompostas em subproblemas que podem ser resolvidos independentemente.
Em cada iteração a análise é reorientada automaticamente para a estimação dos subproblemas que
mais afetam a precisão dos resultados, assim aumentando a taxa de convergência da computação.
Esta reorientação é guiada por três diferentes estratégias de ranqueamento. Experimentos em
programas publicamente disponíveis mostram que a técnica proposta é melhor do que abordagens
existentes em termos de escalabilidade e precisão.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufpe.br:123456789/14932 |
| Date | 24 April 2015 |
| Creators | BORGES, Mateus Araújo |
| Contributors | http://lattes.cnpq.br/3762670242328435, D'AMORIM, Marcelo Bezerra |
| Publisher | Universidade Federal de Pernambuco, Programa de Pos Graduacao em Ciencia da Computacao, UFPE, Brasil |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFPE, instname:Universidade Federal de Pernambuco, instacron:UFPE |
| Rights | Attribution-NonCommercial-NoDerivs 3.0 Brazil, http://creativecommons.org/licenses/by-nc-nd/3.0/br/, info:eu-repo/semantics/openAccess |
Page generated in 0.002 seconds