Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Extended probabilistic symbolic execution
Thesis (MSc)--Stellenbosch University, 2013.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2013
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613819482669056 |
|---|---|
| access_status_str | Open Access |
| author | Uwimbabazi, Aline |
| author2 | Visser, Willem |
| author_browse | Uwimbabazi, Aline Visser, Willem |
| author_facet | Visser, Willem Uwimbabazi, Aline |
| author_sort | Uwimbabazi, Aline |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (MSc)--Stellenbosch University, 2013. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/85804 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:42:12.448Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2013 |
| publishDateRange | 2013 |
| publishDateSort | 2013 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/85804 Extended probabilistic symbolic execution Uwimbabazi, Aline Visser, Willem Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Dissertations -- Mathematical sciences Theses -- Mathematical sciences Dissertations -- Computer science Theses -- Computer science Computer software Symbolic execution Computer programming Probabilities Thesis (MSc)--Stellenbosch University, 2013. ENGLISH ABSTRACT: Probabilistic symbolic execution is a new approach that extends the normal symbolic execution with probability calculations. This approach combines symbolic execution and model counting to estimate the number of input values that would satisfy a given path condition, and thus is able to calculate the execution probability of a path. The focus has been on programs that manipulate primitive types such as linear integer arithmetic in object-oriented programming languages such as Java. In this thesis, we extend probabilistic symbolic execution to handle data structures, thus allowing support for reference types. Two techniques are proposed to calculate the probability of an execution when the programs have structures as inputs: an approximate approach that assumes probabilities for certain choices stay fixed during the execution and an accurate technique based on counting valid structures. We evaluate these approaches on an example of a Binary Search Tree and compare it to the classic approach which only take symbolic values as input. AFRIKAANSE OPSOMMING: Probabilistiese simboliese uitvoering is ’n nuwe benadering wat die normale simboliese uitvoering uitbrei deur waarksynlikheidsberekeninge by te voeg. Hierdie benadering kombineer simboliese uitvoering en modeltellings om die aantal invoerwaardes wat ’n gegewe padvoorwaarde sal bevredig, te beraam en is dus in staat om die uitvoeringswaarskynlikheid van ’n pad te bereken. Tot dus vêr was die fokus op programme wat primitiewe datatipes manipuleer, byvoorbeeld lineêre heelgetalrekenkunde in objek-geörienteerde tale soos Java. In hierdie tesis brei ons probabilistiese simboliese uitvoering uit om datastrukture, en dus verwysingstipes, te dek. Twee tegnieke word voorgestel om die uitvoeringswaarskynlikheid van ’n program met datastrukture as invoer te bereken. Eerstens is daar die benaderingstegniek wat aanneem dat waarskynlikhede vir sekere keuses onveranderd sal bly tydens die uitvoering van die program. Tweedens is daar die akkurate tegniek wat gebaseer is op die telling van geldige datastrukture. Ons evalueer hierdie benaderings op ’n voorbeeld van ’n binêre soekboom en vergelyk dit met die klassieke tegniek wat slegs simboliese waardes as invoer neem. 2013-11-28T10:20:18Z 2013-12-13T17:11:10Z 2013-11-28T10:20:18Z 2013-12-13T17:11:10Z 2013-12 Thesis http://hdl.handle.net/10019.1/85804 en_ZA Stellenbosch University 70 p. : ill. application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Dissertations -- Mathematical sciences Theses -- Mathematical sciences Dissertations -- Computer science Theses -- Computer science Computer software Symbolic execution Computer programming Probabilities Uwimbabazi, Aline Extended probabilistic symbolic execution |
| title | Extended probabilistic symbolic execution |
| title_full | Extended probabilistic symbolic execution |
| title_fullStr | Extended probabilistic symbolic execution |
| title_full_unstemmed | Extended probabilistic symbolic execution |
| title_short | Extended probabilistic symbolic execution |
| title_sort | extended probabilistic symbolic execution |
| topic | Dissertations -- Mathematical sciences Theses -- Mathematical sciences Dissertations -- Computer science Theses -- Computer science Computer software Symbolic execution Computer programming Probabilities |
| url | http://hdl.handle.net/10019.1/85804 |
| work_keys_str_mv | AT uwimbabazialine extendedprobabilisticsymbolicexecution |