Effective verification of confidentiality for multi-threaded programs

    Research output: Contribution to journalArticleAcademicpeer-review

    6 Citations (Scopus)
    69 Downloads (Pure)

    Abstract

    This paper studies how confidentiality properties of multi-threaded programs can be verified efficiently by a combination of newly developed and existing model checking algorithms. In particular, we study the verification of scheduler-specific observational determinism (SSOD), a property that characterizes secure information flow for multi-threaded programs under a given scheduler. Scheduler-specificness allows us to reason about refinement attacks, an important and tricky class of attacks that are notorious in practice. SSOD imposes two conditions: (SSOD-1)~all individual public variables have to evolve deterministically, expressed by requiring stuttering equivalence between the traces of each individual public variable, and (SSOD-2)~the relative order of updates of public variables is coincidental, i.e., there always exists a matching trace. We verify the first condition by reducing it to the question whether all traces of each public variable are stuttering equivalent. To verify the second condition, we show how the condition can be translated, via a series of steps, into a standard strong bisimulation problem. Our verification techniques can be easily adapted to verify other formalizations of similar information flow properties. We also exploit counter example generation techniques to synthesize attacks for insecure programs that fail either SSOD-1 or SSOD-2, i.e., showing how confidentiality of programs can be broken.
    Original languageUndefined
    Pages (from-to)269-300
    Number of pages31
    JournalJournal of computer security
    Volume22
    Issue number2
    DOIs
    Publication statusPublished - 2014

    Keywords

    • EWI-24237
    • IR-88981
    • METIS-303986

    Cite this

    @article{333af6bee6f748979b2ee0d4ee3e73a7,
    title = "Effective verification of confidentiality for multi-threaded programs",
    abstract = "This paper studies how confidentiality properties of multi-threaded programs can be verified efficiently by a combination of newly developed and existing model checking algorithms. In particular, we study the verification of scheduler-specific observational determinism (SSOD), a property that characterizes secure information flow for multi-threaded programs under a given scheduler. Scheduler-specificness allows us to reason about refinement attacks, an important and tricky class of attacks that are notorious in practice. SSOD imposes two conditions: (SSOD-1)~all individual public variables have to evolve deterministically, expressed by requiring stuttering equivalence between the traces of each individual public variable, and (SSOD-2)~the relative order of updates of public variables is coincidental, i.e., there always exists a matching trace. We verify the first condition by reducing it to the question whether all traces of each public variable are stuttering equivalent. To verify the second condition, we show how the condition can be translated, via a series of steps, into a standard strong bisimulation problem. Our verification techniques can be easily adapted to verify other formalizations of similar information flow properties. We also exploit counter example generation techniques to synthesize attacks for insecure programs that fail either SSOD-1 or SSOD-2, i.e., showing how confidentiality of programs can be broken.",
    keywords = "EWI-24237, IR-88981, METIS-303986",
    author = "Ngo, {Minh Tri} and Stoelinga, {Mari{\"e}lle Ida Antoinette} and Marieke Huisman",
    note = "http://dx.doi.org/10.3233/JCS-130492 eemcs-eprint-24237",
    year = "2014",
    doi = "10.3233/JCS-130492",
    language = "Undefined",
    volume = "22",
    pages = "269--300",
    journal = "Journal of computer security",
    issn = "0926-227X",
    publisher = "IOS Press",
    number = "2",

    }

    Effective verification of confidentiality for multi-threaded programs. / Ngo, Minh Tri; Stoelinga, Mariëlle Ida Antoinette; Huisman, Marieke.

    In: Journal of computer security, Vol. 22, No. 2, 2014, p. 269-300.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Effective verification of confidentiality for multi-threaded programs

    AU - Ngo, Minh Tri

    AU - Stoelinga, Mariëlle Ida Antoinette

    AU - Huisman, Marieke

    N1 - http://dx.doi.org/10.3233/JCS-130492 eemcs-eprint-24237

    PY - 2014

    Y1 - 2014

    N2 - This paper studies how confidentiality properties of multi-threaded programs can be verified efficiently by a combination of newly developed and existing model checking algorithms. In particular, we study the verification of scheduler-specific observational determinism (SSOD), a property that characterizes secure information flow for multi-threaded programs under a given scheduler. Scheduler-specificness allows us to reason about refinement attacks, an important and tricky class of attacks that are notorious in practice. SSOD imposes two conditions: (SSOD-1)~all individual public variables have to evolve deterministically, expressed by requiring stuttering equivalence between the traces of each individual public variable, and (SSOD-2)~the relative order of updates of public variables is coincidental, i.e., there always exists a matching trace. We verify the first condition by reducing it to the question whether all traces of each public variable are stuttering equivalent. To verify the second condition, we show how the condition can be translated, via a series of steps, into a standard strong bisimulation problem. Our verification techniques can be easily adapted to verify other formalizations of similar information flow properties. We also exploit counter example generation techniques to synthesize attacks for insecure programs that fail either SSOD-1 or SSOD-2, i.e., showing how confidentiality of programs can be broken.

    AB - This paper studies how confidentiality properties of multi-threaded programs can be verified efficiently by a combination of newly developed and existing model checking algorithms. In particular, we study the verification of scheduler-specific observational determinism (SSOD), a property that characterizes secure information flow for multi-threaded programs under a given scheduler. Scheduler-specificness allows us to reason about refinement attacks, an important and tricky class of attacks that are notorious in practice. SSOD imposes two conditions: (SSOD-1)~all individual public variables have to evolve deterministically, expressed by requiring stuttering equivalence between the traces of each individual public variable, and (SSOD-2)~the relative order of updates of public variables is coincidental, i.e., there always exists a matching trace. We verify the first condition by reducing it to the question whether all traces of each public variable are stuttering equivalent. To verify the second condition, we show how the condition can be translated, via a series of steps, into a standard strong bisimulation problem. Our verification techniques can be easily adapted to verify other formalizations of similar information flow properties. We also exploit counter example generation techniques to synthesize attacks for insecure programs that fail either SSOD-1 or SSOD-2, i.e., showing how confidentiality of programs can be broken.

    KW - EWI-24237

    KW - IR-88981

    KW - METIS-303986

    U2 - 10.3233/JCS-130492

    DO - 10.3233/JCS-130492

    M3 - Article

    VL - 22

    SP - 269

    EP - 300

    JO - Journal of computer security

    JF - Journal of computer security

    SN - 0926-227X

    IS - 2

    ER -