C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Reasoning about Secure Interoperation
using Soft Constraints
Stefano Bistarelli
Simon Foley, Barry O’Sullivan
Dipartimento di Scienze,
Università di Pescara, Italy;
Department of Computer Science
University College Cork
Ireland
IIT, CNR, Pisa, Italy
Speaker: Stefano Bistarelli
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Thanks to my co-authors….
Barry O’Sullivan



University College Cork,
Ireland
Cork Constraint
Computation Centre
Constraints
Simon Foley


University College Cork,
Ireland
Security, Policy, Formal
Methods
C
Motivations
Admin
System
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Sales
System
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Basic Security Modeling
Security
Policy
Subject



Do
Operation
Security
Mechanism
Object
Subject: processes, … Objects: memory, files, …
Security policy defines rules that govern access to
objects by subjects.
Security mechanism ensures security policy is upheld.
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Secure Composition of Systems
Alice allowed
access Bob’s files
Admin
System
Clare allowed
access Alice’s files
connection
Sales
System
Systems are individually secure.
Is it safe to allow file sharing between Personnel and
Sales systems?




Clare not authorized to access Bob’s files, but,
Clare may access Bob’s files via Sales system.
Need to reconfigure connections to close this circuitous
access route [COLOPS2003,SAC2004,IAAI2004].
Need to reconfigure system access configurations!
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Secure Interoperation
Computation Foundations [Gong&Qian, 1994]


Analyzing the security of interoperating and
individually secure systems can be done in
polynomial time.
Given a non-secure network configuration, then
re-configuring the connections in an optimal way
(to minimize the impact on interoperability) is NP.
C
Talk Outline:
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
describe how constraints provide a natural approach to modelling and solving the
secure interoperation problem
Basic Security Modelling


Secure Composition of
systems
Secure Interoperation
What are Soft
Constraints?

Semiring Framework
Using constraints for




Access Configuration
Access Reconfiguration
Access Interoperation
Dealing with Transitivity
Future Work
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Crisp toward soft constraints
C={pairwise-different}
x1 {yellow}
x2 {red,blue}
P={ V, D,C, PC, con, def, a}
x3 {blue,yellow}
x4 {red,blue,yellow}
x1
x2
x3
x4
combination
projection
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Crisp toward soft constraints
5$
C={pairwise-different}
x1 {yellow}
x2 {red,blue}

3$
C-semiring <A,+,´,0,1>:
Weighted
<+,min,+,+,0>
2$
x3 {blue,yellow}
<[0,1],max,,0,1>
Probabilistic
<[0,1],max,min,0,1>
x4 {red,blue,yellow}
<{false,true},,,false,true>
15$
x1
x2
x3
x4
Combination (+)
13$
15$
13$
Projection (min)
Fuzzy
Classical
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
The Semiring Framework
A c-semiring is a tuple <A,+,×,0,1> such that:
 A is the set of all consistency values and 0, 1A.


0 is the lowest consistency value and 1 is the
highest consistency value;
+, the additive operator, is a closed, commutative,
associative and idempotent operation such that 1
is its absorbing element and 0 is its unit element;
×, the multiplicative operator, is a closed and
associative operation such that 0 is its absorbing
element, 1 is its unit element and × distributes
over +.
Stefano Bistarelli, Ugo Montanari, and Francesca Rossi,
Semiring-based Constraint Solving and Optimization
Journal of the ACM, 44(2):201–236, Mar 1997.
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Semiring-based Constraints
Given a semiring <A,+,×, 0, 1> , an ordered set of variables V
over a finite domain D, a constraint is a function which maps an
assignment  of the variables in the support of c, supp(c) to an
element of A.
Notation c represents the constraint function c evaluated
under instantiation , returning a semiring value.
Given two constraints c1 and c2, their combination is defined as
(c1c2) = c1×c2 .
The operation C represents the combination of a set of
constraints C.
a· b iff a+b=b
c1 v c2 iff 8  c1 · c2
Stefano Bistarelli, Ugo Montanari and Francesca Rossi,
Soft Concurrent Constraint Programming,
Proceedings of ESOP-2002, LNCS, April 2002.
C
Talk Outline:
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
describe how constraints provide a natural approach to modelling and solving the
secure interoperation problem
Basic Security Modelling


Secure Composition of
systems
Secure Interoperation
What are Soft
Constraints?

Semiring Framework
Using constraints for




Access Configuration
Access Reconfiguration
Access Interoperation
Dealing with Transitivity
Future Work
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Access Configuration
A collection of constraints between
entities (subjects, objects) specifying
access permissions

Represented as a semiring
 S=<PERM,+,£,?,>>
 Srw=<2{r,w},[,Å,;,{r,w}>

Sbool=<{F,T},Ç,Æ,F,T>
a
{w}
b
CS,O(a,b)={w}
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Access Configuration
A collection of constraints between
entities (subjects, objects) specifying
access permissions

Represented as a semiring
 S=<PERM,+,£,?,>>
 Srw=<2{r,w},[,Å,;,{r,w}>

Sbool=<{F,T},Ç,Æ,F,T>
a
F
b
CS,O(a,b)=F
a
T
b
CS,O(a,b)=T
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Access Configuration: Example
Sbool=<{F,T},Ç,Æ,F,T>



CS,O(b,a)=F
CS,O(c,b)=F
CS,O(x,y)=T
a
c
b
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Access Configuration: Example
Sbool=<{F,T},Ç,Æ,F,T>



CS,O(b,a)=F
CS,O(c,b)=F
CS,O(x,y)=T
a
c
b
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Access Configuration: Example
Sbool=<{F,T},Ç,Æ,F,T>



CS,O(b,a)=F
CS,O(c,b)=F
CS,O(x,y)=T
a
c
b
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Access Configuration: Example
Sbool=<{F,T},Ç,Æ,F,T>



CS,O(b,a)=F
CS,O(c,b)=F
CS,O(x,y)=T
a
c
b
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Access Configuration: Example
Sbool=<{F,T},Ç,Æ,F,T>



CS,O(b,a)=F
CS,O(c,b)=F
CS,O(x,y)=T
a
c
b
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Access Reconfiguration
Existing configuration CS may
be safely re-configured to CS’
when CS’v CS
C>
v
CS
Secure reconfigurations
CS’
C?
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Access Reconfiguration: Example
a
b
a
c
a
rw
c
rw
b
rw
r
c
b
a
r
w
c
rw
b
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Access Interoperation
CS1
a
c
CS3
b
a
c
Has to be a secure reconfiguration of both the
sistems S1 and S3
d
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Access Interoperation
CS1
a
c
CS3
b
a
c
d
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Access Interoperation
CS1 CS3
CS1
a
a
CS3
a
a
b
b
c
c
c
c
a
c
b
d
d
a
c
d
C
Access Transitivity
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
CS1
a
c
CS3
b
a
c
d
C
Access Transitivity
c
- Pisa
Iit
Istituto per l’Informatica e la Telematica
CS1 CS3
CS1
a
Consiglio Nazionale delle Ricerche
b
CS3
a
c
d
C
Access Transitivity
- Pisa
Iit
Istituto per l’Informatica e la Telematica
CS1 CS3
CS1
a
Consiglio Nazionale delle Ricerche
CS3
a
b
a
b
c
c
c
a
c
b
d
a
c
d
d
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Access Transitivity vs non-transitivity
CS1
a
CS3
CS1 CS3
a
a
b
b
c
c
c
CS1
a
c
b
a
c
b
d
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Where to from here?
Real world implementation:

Currently seeking funding to
work with a company based
in New Hampshire, USA.
C
Conclusion
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
We described how constraints provide a
natural approach to modelling and solving the
secure interoperation problem
Access Configuration
Access Reconfiguration
Access Interoperation

Transitivity entities
All naturally represented with constraint
operations
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
C
Consiglio Nazionale delle Ricerche
- Pisa
Iit
Istituto per l’Informatica e la Telematica
Questions?
Thank you for your
attention
You have been listening
to:



“Reasoning about Secure
Interoperation using Soft
Constraints”
Stefano Bistarelli, Simon
Foley and Barry
O’Sullivan
Proceedings of
FAST2004, pag. 183-196