Secure multiparty sessions with topics

(1)

Introduction Safe sessions Types with topics Results Conclusion

Secure multiparty sessions with topics

Ilaria Castellani, Mariangiola Dezani-Ciancaglini, Ugo de’Liguoro

INRIA Sophia Antipolis, University of Turin

PLACES - Eindhoven, April 2016

1/20

(2)

Motivation and goal

control flow based security analysis relies onsecurity levelsand level drop detection to discover information leaks

in case of multiparty communication this leads to unreasonable restrictions

previous work where multiparty sessions have been endowed with security levels and type systems enforcing leak-free communication, suffers from similar restrictions

here we add a further dimension, calledtopics, to relax these restrictions, and show that this can be ensured via a type system

2/20

(3)

Motivation and goal

2/20

(4)

Motivation and goal

2/20

(5)

Motivation and goal

2/20

(6)

Motivation and goal

2/20

(7)

Secure information flow

Let (L, v) be the lattice of security levels:

` v `⁰⇔ ` is less confidential than `⁰

⊥ = public, > = secret. Aleakis an information flow

· · · v^`· · · u^`⁰· · · where ` 6v `⁰ and

v^`is sent from a participantpto a participantqandqis either the sender or the receiver of u^`⁰

3/20

(8)

Secure information flow

⊥ = public, > = secret.

Aleakis an information flow

· · · v^`· · · u^`⁰· · · where ` 6v `⁰ and

3/20

(9)

Secure information flow

⊥ = public, > = secret.

Aleakis an information flow

· · · v^`· · · u^`⁰· · · where ` 6v `⁰ and

3/20

(10)

Motivating example

Alice as PC member:

receives the opinion of Bob on paper 1 sends her judgment on paper 2 to Charlie

the level of Bob opinion is not smaller than the level of Alice judgment standard information flow security

7

information flow security with topics

3

4/20

(11)

Motivating example

Alice as PC member:

receives the opinion of Bob on paper 1

sends her judgment on paper 2 to Charlie

7

3

4/20

(12)

Motivating example

Alice as PC member:

7

3

4/20

(13)

Motivating example

Alice as PC member:

the level of Bob opinion is not smaller than the level of Alice judgment

standard information flow security

7

3

4/20

(14)

Motivating example

Alice as PC member:

7

3

4/20

(15)

Motivating example

Alice as PC member:

7

3

4/20

(16)

Motivating example

Alice as PC member:

7

3

4/20

(17)

Motivating example

Alice as PC member:

7

3

4/20

(18)

Safety with topics

A leak is an information flow

· · · v^`· · · u^`⁰· · · where ` 6v `⁰

Addingtopicsa leak is

· · · v^`,ϕ· · · u^`⁰^,ψ· · · where ` 6v `⁰ and ϕ, ψ are correlated

5/20

(19)

Access control and leak freedom w.r.t. topics

Access control (AC):for each participant p and topic ϕ:

participant p is able to receive v^`,ϕ if ` v ρ(p, ϕ) (reading level)

Leak freedom (LF):a session is leak free if for each participant p whenever p receives v^`,ϕ, she just sends values u^`⁰^,ψ s.t.

` v `⁰ or ϕj ψ where ϕb ψ if ϕ and ψ are independent topics.

6/20

(20)

Access control and leak freedom w.r.t. topics

6/20

(21)

Access control and leak freedom w.r.t. topics

6/20

(22)

A multiparty session calculus

Expressions:

e ::= x || v^`,ϕ || op(e1, . . . , en) Processes:

P ::= q!λ(e).P || p?λ(x ).Q || P ⊕ P || P + P || µX .P || X || 0

Multiparty sessions:

M ::= p1/ P1 | . . . | pn/ Pn

Operational semantics:

P ^q!λ(v

`,ϕ)

−−−−−→ P⁰ Q ^p?λ(v

`,ϕ)

−−−−−−→ Q⁰ p / P | q / Q ^p(λ,v

`,ϕ)q

−−−−−−→ p / P⁰ | q / Q⁰

7/20

(23)

Safe sessions

Definition

A multiparty session M is safe if it satisfies:

Access control (AC):

whenever σ · p(λ, v^`,ϕ)q is a trace of M, then ` v ρ(q, ϕ);

Leak freedom (LF):

whenever σ · p(λ, v^`,ϕ)q · σ⁰· q(λ⁰, u^`⁰^,ψ)r is a relay trace of M, then either ` v `⁰ or ϕb ψ.

where σ · p(λ, v^`,ϕ)q · σ⁰· q(λ⁰, u^`⁰^,ψ)r is a relay trace from p to r mediated by q.

8/20

(24)

Examples

A trace of a safe session (that was not such in past systems)

Bob (evaluation,”reject”^`¹^{, paper 1}) Alice Alice (evaluation,”accept”^`²^{, paper 2}) Charlie

`1is not smaller than `2

paper 1 and paper 2 are independent

9/20

(25)

Examples

Bob (evaluation,”reject”^`¹^{, paper 1}) Alice

Alice (evaluation,”accept”^`²^{, paper 2}) Charlie

9/20

(26)

Examples

9/20

(27)

Examples

9/20

(28)

Examples

9/20

(29)

Types

Sorts:

S ::= nat || int || bool || string Global types:

G ::= p → q : {λi(S_i^`ⁱ^,ϕⁱ).G_i}_{i ∈I} || µt.G || t || end Session types:

T ::=_

i ∈I

q!λ_i(S_i^`ⁱ^,ϕⁱ).T_i || ^

i ∈I

p?λ_i(S_i^`ⁱ^,ϕⁱ).T_i || µt.T || t || end

10/20

(30)

Level, topic agreement with a type

h`, ϕiagreeswith T , h`, ϕi ≺ T , if according to T only values of level

`⁰w ` are sent on topics related with ϕ

h`, ϕi ≺ T is co-inductively defined by h`, ϕi ≺ end

if h`, ϕi ≺ Ti for all i ∈ I then h`, ϕi ≺^

i ∈I

p?λi(S_i^`ⁱ^,ϕⁱ).Ti

if h`, ϕi ≺ T_i and either ` v `⁰_i or ϕb ψi for all i ∈ I then h`, ϕi ≺_

i ∈I

q!λi(S^`⁰ⁱ^,ψⁱ).Ti

11/20

(31)

Level, topic agreement with a type

h`, ϕiagreeswith T , h`, ϕi ≺ T , if according to T only values of level

`⁰w ` are sent on topics related with ϕ h`, ϕi ≺ T is co-inductively defined by

h`, ϕi ≺ end

if h`, ϕi ≺ T_i for all i ∈ I then h`, ϕi ≺^

i ∈I

p?λi(S_i^`ⁱ^,ϕⁱ).Ti

if h`, ϕi ≺ T_i and either ` v `⁰_i or ϕb ψi for all i ∈ I then h`, ϕi ≺_

i ∈I

q!λi(S^`⁰ⁱ^,ψⁱ).Ti

11/20

(32)

Safe session types

Type T issafeif

1 all input continuations are safe and agreed by the respective participant, topic pairs,

2 all output continuations are safe and outputs are sent to participants with the proper reading level

Coinductively end is safe

if h`i, ϕii ≺ Ti and Ti is safe for all i ∈ I then

^

i ∈I

p?λi(S_i^`ⁱ^,ϕⁱ).T_i is safe if `iv ρ(q, ϕi) and Ti is safe for all i ∈ I then

_

i ∈I

q!λ_i(S_i^`ⁱ^,ϕⁱ).T_i

12/20

(33)

Safe session types

Type T issafeif

1 all input continuations are safe and agreed by the respective participant, topic pairs,

2 all output continuations are safe and outputs are sent to participants with the proper reading level

Coinductively end is safe

if h`i, ϕii ≺ Ti and Ti is safe for all i ∈ I then

^

i ∈I

p?λi(S_i^`ⁱ^,ϕⁱ).T_i is safe if `iv ρ(q, ϕi) and Ti is safe for all i ∈ I then

_

i ∈I

q!λ_i(S_i^`ⁱ^,ϕⁱ).T_i

12/20

(34)

Session type system

Type rules:

Γ ` e : S^`,ϕ Γ ` P I T Γ ` q!λ(e).P I q!λ(S^`,ϕ).T

Γ, x : S^`,ϕ` Q I T Γ ` p?λ(x ).Q I p?λ(S^`,ϕ).T Γ ` P1I T¹ Γ ` P2I T²

Γ ` P1⊕ P2I T¹∨ T2

Γ ` P1I T¹ Γ ` P2I T² Γ ` P1+ P2I T¹∧ T2

Γ ` P I T is asafe typing if all types in the derivation are safe.

Example: if ρ(p, ϕ) = > and ϕb ψ we can derive

` p?λ(x).r!λ⁰(false^⊥,ψ).0 I p?λ(bool^>,ϕ).r!λ⁰(bool^⊥,ψ).end

13/20

(35)

Session type system

Type rules:

Γ ` e : S^`,ϕ Γ ` P I T Γ ` q!λ(e).P I q!λ(S^`,ϕ).T

Γ, x : S^`,ϕ` Q I T Γ ` p?λ(x ).Q I p?λ(S^`,ϕ).T Γ ` P1I T¹ Γ ` P2I T²

Γ ` P1⊕ P2I T¹∨ T2

Γ ` P1I T¹ Γ ` P2I T² Γ ` P1+ P2I T¹∧ T2

Γ ` P I T is asafe typing if all types in the derivation are safe.

Example: if ρ(p, ϕ) = > and ϕb ψ we can derive

` p?λ(x).r!λ⁰(false^⊥,ψ).0 I p?λ(bool^>,ϕ).r!λ⁰(bool^⊥,ψ).end

13/20

(36)

Subtyping

Subtyping of safe types, T ≤ T⁰, is co-inductively defined by end ≤ end

if T_i≤ T_i⁰ for all i ∈ I ⊇ J then

^

i ∈I

p?λi(S_i^`ⁱ^,ϕⁱ).Ti 6^

j ∈J

p?λj(S_j^`^j^,ϕ^j).T_j⁰

if T_i≤ T_i⁰ for all i ∈ I ⊆ J then _

i ∈I

p!λi(S_i^`ⁱ^,ϕⁱ).Ti 6_

j ∈J

p!λj(S_j^`^j^,ϕ^j).T_j⁰

14/20

(37)

Global type system

Let’s take from [Honda-Yoshida-Carbone 2008]:

pt{G } is the set of participants of G

G p is the projection into the session type for p

` Pi I Tⁱ Ti≤ G pi pt{G } ⊆ {p1, . . . , pn} ∀i ∈ {1, . . . , n}

p1/ P1| . . . | pn/ PnI G

15/20

(38)

Typing example

Alice / Bob?evaluation(x ). Charlie!evaluation(”accept”^`¹^{,paper 2}).0 Bob?evaluation(String^`¹^{,paper 1}).Charlie!evaluation(String^`²^{,paper 2}).end

16/20

(39)

Session and global type reduction

Reduction of session types:

T ∨ T⁰=⇒ T p!λ(S^`,ϕ).T =⇒ T ^

i ∈I

p?λi(S_i^`ⁱ^,ϕⁱ).Ti =⇒ Ti

Reduction of global types:

G =⇒ G \ p−→ q^λ

where G \ p−→ q is the global type obtained from G by executing the^λ communication p−→ q^λ

17/20

(40)

Subject reduction

Theorem

If p / P | M−→ p / P^κ ⁰ | M⁰, and p / P | M I G and ` P I T , then:

1 p / P⁰ | M⁰ I G⁰ for some G⁰ such that G =⇒^∗G⁰;

2 ` P⁰ I T⁰ for some T⁰ such that T =⇒^∗T⁰.

Proved by establishing that:

if q!λ(S^`,ϕ).T ≤ G p, then T ≤ (G \ p−→ q) p;^λ if p?λ(S^`,ϕ).T ∧ T⁰≤ G q, then T ≤ (G \ p−→ q) q;^λ G r = (G \ p−→ q) r for r 6= p, r 6= q.^λ

18/20

(41)

Soundness theorem

Theorem

If M is typeable by a derivation containing only safe types then M is safe.

Proof essentially based on subject reduction theorem.

19/20

(42)

Conclusion and further work

Advantages of the proposed approach:

A sequence of messages directed to the same participant is always allowed

Thanks to the introduction of topics, the standard leak-freedom requirement can be relaxed also on relay sequences, by forbidding only downward flows between messages on related topics. Further directions:

consider multiple sessions

enrich the present calculus by allowing levels and topics to depend on exchanged values, following [Louren¸co-Caires 2015]

20/20

(43)

Conclusion and further work

Thanks to the introduction of topics, the standard leak-freedom requirement can be relaxed also on relay sequences, by forbidding only downward flows between messages on related topics.

Further directions:

20/20

(44)

Conclusion and further work

Thanks to the introduction of topics, the standard leak-freedom requirement can be relaxed also on relay sequences, by forbidding only downward flows between messages on related topics.

Further directions:

20/20