Probabilistic Output Analyses for Deterministic Programs: Reusing Existing Non-probabilistic Analyses

Maja Hanne Kirkeby

doi:10.4204/EPTCS.312.4

Probabilistic Output Analyses for Deterministic Programs: Reusing Existing Non-probabilistic Analyses

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Abstract

We consider reusing established non-probabilistic output analyses (either forward or backwards) thatyield over-approximations of a program’s pre-image or image relation, e.g., interval analyses. Weassume a probability measure over the program input and present two techniques (one for forward andone for backward analyses) that both derive upper and lower probability bounds for the output events.We demonstrate the most involved technique, namely the forward technique, for two examples andcompare their results to a cutting-edge probabilistic output analysis.

Originalsprog	Engelsk
Titel	Proceedings 16th Workshop on Quantitative Aspects of Programming Languages and Systems Prague, Czech Republic, 7th April 2019
Redaktører	Alessandro Aldini, Herbert Wiklicky
Antal sider	15
Vol/bind	312
Forlag	Open Publishing Association
Publikationsdato	20 jan. 2020
Sider	43-57
DOI	https://doi.org/10.4204/EPTCS.312.4
Status	Udgivet - 20 jan. 2020
Begivenhed	16th Workshop on Quantitative Aspects of Programming Languages and Systems - Prague, Tjekkiet Varighed: 7 apr. 2019 → 7 apr. 2019 Konferencens nummer: 16 https://conf.researchr.org/track/etaps-2019/qapl-2019-papers

Workshop

Workshop	16th Workshop on Quantitative Aspects of Programming Languages and Systems
Nummer	16
Land/Område	Tjekkiet
By	Prague
Periode	07/04/2019 → 07/04/2019
Andet	Quantitative aspects of computation refer to the use of physical quantities (time, bandwidth, etc.) as well as mathematical quantities (for example, probabilities) for the characterisation of the behaviour and for determining the properties of systems. Such quantities play a central role in defining both the model of systems (architecture, language design, semantics) and the methodologies and tools for the analysis and verification of system properties. The aim of the QAPL workshop series is to discuss the explicit use of time and probability and general quantities either directly in the model or as a tool for the analysis or synthesis of systems. The 16th edition of QAPL will also focus on discussing the developments, challenges and results in this area covered by our workshop in its nearly 20-year history.
Internetadresse	https://conf.researchr.org/track/etaps-2019/qapl-2019-papers

Navn	Electronic Proceedings in Theoretical Computer Science
Nummer	312
ISSN	2075-2180

Link til dokument

10.4204/EPTCS.312.4Licens: Ikke-specificeret

Andre filer og links

Proceeding

Citer dette

Kirkeby, M. H. (2020). Probabilistic Output Analyses for Deterministic Programs: Reusing Existing Non-probabilistic Analyses. I A. Aldini, & H. Wiklicky (red.), Proceedings 16th Workshop on Quantitative Aspects of Programming Languages and Systems Prague, Czech Republic, 7th April 2019 (Bind 312, s. 43-57). Open Publishing Association. https://doi.org/10.4204/EPTCS.312.4

Kirkeby, Maja Hanne. / Probabilistic Output Analyses for Deterministic Programs : Reusing Existing Non-probabilistic Analyses. Proceedings 16th Workshop on Quantitative Aspects of Programming Languages and Systems Prague, Czech Republic, 7th April 2019. red. / Alessandro Aldini ; Herbert Wiklicky . Bind 312 Open Publishing Association, 2020. s. 43-57 (Electronic Proceedings in Theoretical Computer Science; Nr. 312).

@inproceedings{c4642c2d8b194789be728a596fd49031,

title = "Probabilistic Output Analyses for Deterministic Programs: Reusing Existing Non-probabilistic Analyses",

abstract = "We consider reusing established non-probabilistic output analyses (either forward or backwards) thatyield over-approximations of a program{\textquoteright}s pre-image or image relation, e.g., interval analyses. Weassume a probability measure over the program input and present two techniques (one for forward andone for backward analyses) that both derive upper and lower probability bounds for the output events.We demonstrate the most involved technique, namely the forward technique, for two examples andcompare their results to a cutting-edge probabilistic output analysis.",

author = "Kirkeby, {Maja Hanne}",

year = "2020",

month = jan,

day = "20",

doi = "10.4204/EPTCS.312.4",

language = "English",

volume = "312",

series = "Electronic Proceedings in Theoretical Computer Science",

publisher = "Open Publishing Association",

number = "312",

pages = "43--57",

editor = "Alessandro Aldini and {Wiklicky }, Herbert",

booktitle = "Proceedings 16th Workshop on Quantitative Aspects of Programming Languages and Systems Prague, Czech Republic, 7th April 2019",

note = "16th Workshop on Quantitative Aspects of Programming Languages and Systems, QAPL 2019 ; Conference date: 07-04-2019 Through 07-04-2019",

url = "https://conf.researchr.org/track/etaps-2019/qapl-2019-papers",

}

Kirkeby, MH 2020, Probabilistic Output Analyses for Deterministic Programs: Reusing Existing Non-probabilistic Analyses. i A Aldini & H Wiklicky (red), Proceedings 16th Workshop on Quantitative Aspects of Programming Languages and Systems Prague, Czech Republic, 7th April 2019. bind 312, Open Publishing Association, Electronic Proceedings in Theoretical Computer Science, nr. 312, s. 43-57, 16th Workshop on Quantitative Aspects of Programming Languages and Systems, Prague, Tjekkiet, 07/04/2019. https://doi.org/10.4204/EPTCS.312.4

Probabilistic Output Analyses for Deterministic Programs: Reusing Existing Non-probabilistic Analyses. / Kirkeby, Maja Hanne.
Proceedings 16th Workshop on Quantitative Aspects of Programming Languages and Systems Prague, Czech Republic, 7th April 2019. red. / Alessandro Aldini; Herbert Wiklicky . Bind 312 Open Publishing Association, 2020. s. 43-57 (Electronic Proceedings in Theoretical Computer Science; Nr. 312).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Probabilistic Output Analyses for Deterministic Programs

T2 - 16th Workshop on Quantitative Aspects of Programming Languages and Systems

AU - Kirkeby, Maja Hanne

N1 - Conference code: 16

PY - 2020/1/20

Y1 - 2020/1/20

N2 - We consider reusing established non-probabilistic output analyses (either forward or backwards) thatyield over-approximations of a program’s pre-image or image relation, e.g., interval analyses. Weassume a probability measure over the program input and present two techniques (one for forward andone for backward analyses) that both derive upper and lower probability bounds for the output events.We demonstrate the most involved technique, namely the forward technique, for two examples andcompare their results to a cutting-edge probabilistic output analysis.

AB - We consider reusing established non-probabilistic output analyses (either forward or backwards) thatyield over-approximations of a program’s pre-image or image relation, e.g., interval analyses. Weassume a probability measure over the program input and present two techniques (one for forward andone for backward analyses) that both derive upper and lower probability bounds for the output events.We demonstrate the most involved technique, namely the forward technique, for two examples andcompare their results to a cutting-edge probabilistic output analysis.

UR - https://arxiv.org/html/2001.06163#EPTCS312.0

U2 - 10.4204/EPTCS.312.4

DO - 10.4204/EPTCS.312.4

M3 - Article in proceedings

VL - 312

T3 - Electronic Proceedings in Theoretical Computer Science

SP - 43

EP - 57

BT - Proceedings 16th Workshop on Quantitative Aspects of Programming Languages and Systems Prague, Czech Republic, 7th April 2019

A2 - Aldini, Alessandro

A2 - Wiklicky , Herbert

PB - Open Publishing Association

Y2 - 7 April 2019 through 7 April 2019

ER -

Kirkeby MH. Probabilistic Output Analyses for Deterministic Programs: Reusing Existing Non-probabilistic Analyses. I Aldini A, Wiklicky H, red., Proceedings 16th Workshop on Quantitative Aspects of Programming Languages and Systems Prague, Czech Republic, 7th April 2019. Bind 312. Open Publishing Association. 2020. s. 43-57. (Electronic Proceedings in Theoretical Computer Science; Nr. 312). doi: 10.4204/EPTCS.312.4