Quantitative Security Analysis for Multi-threaded Programs

Minh Tri Ngo, Marieke Huisman

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
35 Downloads (Pure)

Abstract

Quantitative theories of information flow give us an approach to relax the absolute confidentiality properties that are difficult to satisfy for many practical programs. The classical information-theoretic approaches for sequential programs, where the program is modeled as a communication channel with only input and output, and the measure of leakage is based on the notions of initial uncertainty and remaining uncertainty after observing the final outcomes, are not suitable to multi-threaded programs. Besides, the information-theoretic approaches have been also shown to conflict with each other when comparing programs. Reasoning about the exposed information flow of multi-threaded programs is more complicated, since the outcomes of such programs depend on the scheduler policy, and the leakages in intermediate states also contribute to the overall leakage of the program. This paper proposes a novel model of quantitative analysis for multi-threaded programs that also takes into account the effect of observables in intermediate states along the trace. We define a notion of the leakage of a program trace. Given the fact that the execution of a multi-threaded program is typically described by a set of traces, the leakage of a program under a specific scheduler is computed as the expected value of the leakages of all possible traces. Examples are given to compare our approach with the existing approaches.
Original languageEnglish
Title of host publicationProceedings 11th International Workshop on Quantitative Aspects of Programming Languages and Systems
EditorsLuca Bortolussi, Herbert Wiklicky
Place of PublicationAustralia
PublisherOpen Publishing Association
Pages34-48
Number of pages15
DOIs
Publication statusPublished - 11 Jun 2013
Event11th International Workshop on Quantitative Aspects of Programming Languages and Systems, QAPL 2013 - Rome, Italy
Duration: 23 Mar 201324 Mar 2013
Conference number: 11
http://eptcs.web.cse.unsw.edu.au/content.cgi?QAPL2013

Publication series

NameElectronic Proceedings in Theoretical Computer Science
PublisherOpen Publishing Association
Volume117
ISSN (Electronic)2075-2180

Workshop

Workshop11th International Workshop on Quantitative Aspects of Programming Languages and Systems, QAPL 2013
Abbreviated titleQAPL 2013
CountryItaly
CityRome
Period23/03/1324/03/13
Internet address

Fingerprint

Chemical analysis
Uncertainty

Keywords

  • EWI-23290
  • IR-86228
  • METIS-297619
  • Security
  • Quantative Analysis
  • Multi-threaded programs

Cite this

Ngo, M. T., & Huisman, M. (2013). Quantitative Security Analysis for Multi-threaded Programs. In L. Bortolussi, & H. Wiklicky (Eds.), Proceedings 11th International Workshop on Quantitative Aspects of Programming Languages and Systems (pp. 34-48). (Electronic Proceedings in Theoretical Computer Science; Vol. 117). Australia: Open Publishing Association. https://doi.org/10.4204/EPTCS.117.3
Ngo, Minh Tri ; Huisman, Marieke. / Quantitative Security Analysis for Multi-threaded Programs. Proceedings 11th International Workshop on Quantitative Aspects of Programming Languages and Systems. editor / Luca Bortolussi ; Herbert Wiklicky. Australia : Open Publishing Association, 2013. pp. 34-48 (Electronic Proceedings in Theoretical Computer Science).
@inproceedings{181710d81ddb48649a73419f5a8a4fc3,
title = "Quantitative Security Analysis for Multi-threaded Programs",
abstract = "Quantitative theories of information flow give us an approach to relax the absolute confidentiality properties that are difficult to satisfy for many practical programs. The classical information-theoretic approaches for sequential programs, where the program is modeled as a communication channel with only input and output, and the measure of leakage is based on the notions of initial uncertainty and remaining uncertainty after observing the final outcomes, are not suitable to multi-threaded programs. Besides, the information-theoretic approaches have been also shown to conflict with each other when comparing programs. Reasoning about the exposed information flow of multi-threaded programs is more complicated, since the outcomes of such programs depend on the scheduler policy, and the leakages in intermediate states also contribute to the overall leakage of the program. This paper proposes a novel model of quantitative analysis for multi-threaded programs that also takes into account the effect of observables in intermediate states along the trace. We define a notion of the leakage of a program trace. Given the fact that the execution of a multi-threaded program is typically described by a set of traces, the leakage of a program under a specific scheduler is computed as the expected value of the leakages of all possible traces. Examples are given to compare our approach with the existing approaches.",
keywords = "EWI-23290, IR-86228, METIS-297619, Security, Quantative Analysis, Multi-threaded programs",
author = "Ngo, {Minh Tri} and Marieke Huisman",
year = "2013",
month = "6",
day = "11",
doi = "10.4204/EPTCS.117.3",
language = "English",
series = "Electronic Proceedings in Theoretical Computer Science",
publisher = "Open Publishing Association",
pages = "34--48",
editor = "Luca Bortolussi and Herbert Wiklicky",
booktitle = "Proceedings 11th International Workshop on Quantitative Aspects of Programming Languages and Systems",
address = "Australia",

}

Ngo, MT & Huisman, M 2013, Quantitative Security Analysis for Multi-threaded Programs. in L Bortolussi & H Wiklicky (eds), Proceedings 11th International Workshop on Quantitative Aspects of Programming Languages and Systems. Electronic Proceedings in Theoretical Computer Science, vol. 117, Open Publishing Association, Australia, pp. 34-48, 11th International Workshop on Quantitative Aspects of Programming Languages and Systems, QAPL 2013, Rome, Italy, 23/03/13. https://doi.org/10.4204/EPTCS.117.3

Quantitative Security Analysis for Multi-threaded Programs. / Ngo, Minh Tri; Huisman, Marieke.

Proceedings 11th International Workshop on Quantitative Aspects of Programming Languages and Systems. ed. / Luca Bortolussi; Herbert Wiklicky. Australia : Open Publishing Association, 2013. p. 34-48 (Electronic Proceedings in Theoretical Computer Science; Vol. 117).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Quantitative Security Analysis for Multi-threaded Programs

AU - Ngo, Minh Tri

AU - Huisman, Marieke

PY - 2013/6/11

Y1 - 2013/6/11

N2 - Quantitative theories of information flow give us an approach to relax the absolute confidentiality properties that are difficult to satisfy for many practical programs. The classical information-theoretic approaches for sequential programs, where the program is modeled as a communication channel with only input and output, and the measure of leakage is based on the notions of initial uncertainty and remaining uncertainty after observing the final outcomes, are not suitable to multi-threaded programs. Besides, the information-theoretic approaches have been also shown to conflict with each other when comparing programs. Reasoning about the exposed information flow of multi-threaded programs is more complicated, since the outcomes of such programs depend on the scheduler policy, and the leakages in intermediate states also contribute to the overall leakage of the program. This paper proposes a novel model of quantitative analysis for multi-threaded programs that also takes into account the effect of observables in intermediate states along the trace. We define a notion of the leakage of a program trace. Given the fact that the execution of a multi-threaded program is typically described by a set of traces, the leakage of a program under a specific scheduler is computed as the expected value of the leakages of all possible traces. Examples are given to compare our approach with the existing approaches.

AB - Quantitative theories of information flow give us an approach to relax the absolute confidentiality properties that are difficult to satisfy for many practical programs. The classical information-theoretic approaches for sequential programs, where the program is modeled as a communication channel with only input and output, and the measure of leakage is based on the notions of initial uncertainty and remaining uncertainty after observing the final outcomes, are not suitable to multi-threaded programs. Besides, the information-theoretic approaches have been also shown to conflict with each other when comparing programs. Reasoning about the exposed information flow of multi-threaded programs is more complicated, since the outcomes of such programs depend on the scheduler policy, and the leakages in intermediate states also contribute to the overall leakage of the program. This paper proposes a novel model of quantitative analysis for multi-threaded programs that also takes into account the effect of observables in intermediate states along the trace. We define a notion of the leakage of a program trace. Given the fact that the execution of a multi-threaded program is typically described by a set of traces, the leakage of a program under a specific scheduler is computed as the expected value of the leakages of all possible traces. Examples are given to compare our approach with the existing approaches.

KW - EWI-23290

KW - IR-86228

KW - METIS-297619

KW - Security

KW - Quantative Analysis

KW - Multi-threaded programs

U2 - 10.4204/EPTCS.117.3

DO - 10.4204/EPTCS.117.3

M3 - Conference contribution

T3 - Electronic Proceedings in Theoretical Computer Science

SP - 34

EP - 48

BT - Proceedings 11th International Workshop on Quantitative Aspects of Programming Languages and Systems

A2 - Bortolussi, Luca

A2 - Wiklicky, Herbert

PB - Open Publishing Association

CY - Australia

ER -

Ngo MT, Huisman M. Quantitative Security Analysis for Multi-threaded Programs. In Bortolussi L, Wiklicky H, editors, Proceedings 11th International Workshop on Quantitative Aspects of Programming Languages and Systems. Australia: Open Publishing Association. 2013. p. 34-48. (Electronic Proceedings in Theoretical Computer Science). https://doi.org/10.4204/EPTCS.117.3