Safety Problems in Access Control with Temporal Constraints - Computer Network Security - page 174

5 Some Mathematical Results

Consider a timed protection system Π .If Π is a timed protection system ob-
tained from Π by modifying all or part of its timed constraints “ since at least
duration d ” then, obviously, Π and Π leak the same rights, possibly at different
points in time. Hence, HRU ( Π ) denoting the HRU protection system obtained
from Π by removing all its timed constraints “ since at least duration d ”, the
following lemma should not come as a great surprise.

Lemma 1. Let ∆ be a protection state. The following conditions are equivalent:

- there exists a positive real number d such that Π is d-unsafe for r with respect
to ∆,
- HRU ( Π ) is unsafe for r with respect to ∆.

Let C timed be a class of timed protection systems. The most basic problem on

timed protection systems in

C timed is the following decision problem:

Problem: UNIVERSAL TIMED SAFETY( C timed ),

Input: aright r , a timed protection system Π ∈C timed , and a protection state

∆ =( S, O, A ),
Output: determine if there exists a positive real number d such that Π is d -
unsafe for r with respect to ∆ .

Like all decision problems, UNIVERSAL TIMED SAFETY( C timed )musthave

a countable set of instances. As a result, hereafer, we will always assume that
for all positive real numbers d , if a timed protection system Π ∈C timed contains

the timed constraint “ since at least duration d ”then d is rational.

Theorem 2. 1. UNIVERSAL TIMED SAFETY ( C timed ( ∞ , 1)) is decidable,

+
timed (1 ,

2. UNIVERSAL TIMED SAFETY ( C ∞ )) is decidable,

+
timed (2 ,

3. UNIVERSAL TIMED SAFETY ( C ∞ )) is undecidable.

Proof. The corresponding results for SAFETY with respect to HRU protection
systems have been proved by [7,8]. Lemma 1 now finishes the proof.

Let r be a right, Π ∈C timed be a timed protection system, and ∆ be a protection

state. Suppose that the set of all waiting periods of Π for r with respect to ∆
is nonempty. Hence, it has a greatest lower bound d glb . What is the crucial
observation we need to make about d glb ? Simply this: in view of the fact that
the timed constraints in Π are rational, d glb must be rational. This suggests the
following optimization problem:

Problem: MIN TIMED SAFETY( C timed ),
Input: aright r , a timed protection system Π

∈C timed , and a protection state

∆ =( S, O, A ),
Output: if the set of all waiting periods of Π for r with respect to ∆ is nonempty
then find its greatest lower bound.