Extended probabilistic symbolic execution

Simple item page
dc.contributor.advisorVisser, Willemen_ZA
dc.contributor.authorUwimbabazi, Alineen_ZA
dc.contributor.otherStellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.en_ZA
dc.date.accessioned2013-11-28T10:20:18Zen_ZA
dc.date.accessioned2013-12-13T17:11:10Z
dc.date.available2013-11-28T10:20:18Zen_ZA
dc.date.available2013-12-13T17:11:10Z
dc.date.issued2013-12en_ZA
dc.descriptionThesis (MSc)--Stellenbosch University, 2013.en_ZA
dc.description.abstractENGLISH 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.en_ZA
dc.description.abstractAFRIKAANSE 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.af_ZA
dc.format.extent70 p. : ill.
dc.identifier.urihttp://hdl.handle.net/10019.1/85804
dc.language.isoen_ZA
dc.publisherStellenbosch : Stellenbosch Universityen_ZA
dc.rights.holderStellenbosch Universityrn_ZA
dc.subjectDissertations -- Mathematical sciencesen_ZA
dc.subjectTheses -- Mathematical sciencesen_ZA
dc.subjectDissertations -- Computer scienceen_ZA
dc.subjectTheses -- Computer scienceen_ZA
dc.subjectComputer softwareen_ZA
dc.subjectSymbolic executionen_ZA
dc.subjectComputer programmingen_ZA
dc.subjectProbabilitiesen_ZA
dc.titleExtended probabilistic symbolic executionen_ZA
dc.typeThesis
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
uwimbabazi_extended_2013.pdf
Size:
1.91 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.98 KB
Format:
Plain Text
Description:
Download
Collections
Masters Degrees (Mathematical Sciences)