RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

Eléments pour un système
de protection extensible

Jean Claude
J.Ferrié, C.Kaiser
D.Lanciaux, B.Martin
Bernard

Rapport de Recherche n° 80

Septembre 1974
# ELEMENTS POUR UN SYSTEME DE PROTECTION EXTENSIBLE

J. Ferrié

C. Kaiser

D. Lanciaux

B. Martin

## ABSTRACT.

The purpose of this research is to develop and analyze addressing and protection structures which will help to run more secure program and to limit the propagation of errors. The generalized notions of object, type of object and type extension are defined and a mechanism is presented which rely on descriptors and which implements those notions into the addressing scheme.

This mechanism allows the definition at execution time of new levels of protection and provides a tool for controlling the cooperation of mutually suspicious subsystems.

An English presentation of this research has been published in the proceedings of the workshop on protection in Operating systems held at IRIA, August 1974.

## RESUME.

Cette étude a pour but de dégager une structure d'adressage et de protection qui permette d'exécuter des programmes avec davantage de sécurité et de limiter la propagation des erreurs. Les notions d'objet, de type d'objet et d'extension de type sont précisées ; un mécanisme qui repose sur l'utilisation des descripteurs permet de mettre en place ces concepts au niveau de l'adressage.

Ce mécanisme permet de définir à l'exécution de nouveaux niveaux de protection et d'assurer le contrôle de sous systèmes mutuellement méfiants.
# Plan

## 1. INTRODUCTION

* Position du problème

* Fonctions assurées par la protection

* Représentation de l'état de protection d'un système

* Problème de méfiance mutuelle

* But de la présente étude

## 2. NOTION DE DESCRIPTEUR

* Ensembles d'objets

* Caractérisation d'un objet

* Protection des descripteurs

## 3. CONSTRUCTION D'OBJETS

### 3.1. GENERALITES

* Notion de type d'objet

* Caractérisation d'un type d'objet

* Représentation des objets

### 3.2. LES OBJETS DE TYPE PRIMITIF

* Le type Segment

* Le type D-liste

### 3.3. LES OBJETS DE TYPE CONSTRUIT

* Généralités

* Représentation d'un objet de type construit

* Construction d'objets composés

* Niveau d'interprétation d'une représentation

### 3.4. COPIE DES DESCRIPTEURS

### 3.5. TRANSFORMATION DU TYPE D'UN OBJET

* Présentation du problème

* Le type Transition

* Manipulation d'une transition

* Création d'une transition

## 4. LES DOMAINES

### 4.1. CARACTERISATION D'UN DOMAINE

* Notion d'environnement

* Accès aux opérations

* Réalisation des opérations programmées -

### 4.2. L'OBJET DE TYPE DOMAINE

### 4.3. APPEL ET RETOUR DE DOMAINE
### 4.4. TRANSMISSION D'OBJETS ENTRE DOMAINES

* *Principes*

* *Contrôle par l'appelant*

* *Contrôle par l'appelé*

## 5. DESTRUCTION DES OBJETS ET DES TYPES

### 5.1. DESTRUCTION D'UN OBJET

* *Définitions*

* *Destruction d'un objet primitif*

* *Destruction d'un objet de type construit*

### 5.2. DESTRUCTION D'UN TYPE

* *Problèmes posés par la destruction d'un type*

* *Définitions*

* *Destruction d'un type*

## 6. LE NOYAU DE PROTECTION

### 6.1. FONCTIONS DU NOYAU

### 6.2. APPEL ET RETOUR

### 6.3. MECANISMES MIS EN JEU

## 7. EXEMPLES

### 7.1. REALISATION DE PRIMITIVES DE SYNCHRONISATION

### 7.2. LES "BIBLIOGRAPHIES"

# ANNEXE

# REFERENCES
# 1. INTRODUCTION

## Position du problème

La *protection* est le terme générique désignant l'action des mécanismes câblés et programmés qui ont pour rôle de contrôler l'accès aux entités présentes dans un système. Leur but n'est pas d'empêcher la production des erreurs, mais seulement d'empêcher leur incidence sur les entités protégées [Crocus]. Dans cette étude, nous laissons de côté les problèmes posés par la sécurité d'utilisation du système, qui déterminent le degré de confiance qu'on peut lui accorder et qui reposent en fait sur la façon d'utiliser ces mécanismes et sur leur fiabilité.

Les entités du système, capables de produire ou de propager des erreurs, et dont on yeut contrôler les actions, sont appelées les *agents* ; par exemple, un processus est un agent. Les entités dont on souhaite contrôler l'utilisation sont appelées les *objets*. En première approximation, la nature d'un objet est définie dès qu'ont été précisées les opérations qui permettent de le manipuler. Les mécanismes de protection visent justement à empêcher sa manipulation par d'autres opérations que celles qui ont été prévues au moment de sa définition.

**Remarque.** Tout élément qui n'a pas été défini par des opérations spécifiques est ignoré du mécanisme de protection et ne sera jamais désigné par le terme d'objet. Notre étude porte sur les entités en mémoire qui sont contrôlées par le mécanisme de protection, à l'exclusion des autres.

## Fonctions assurées par la protection

La protection a pris toute son importance avec le partage des objets d'un système entre plusieurs agents. Nous nous plaçons dans le cas où on demande au système de permettre :

- la création, la destruction, la manipulation et la conservation d'objets,

- le partage d'objets entre certains agents.

Pour cela les mécanismes de protection doivent contrôler pour chaque agent et à tout instant :

- d'une part, les objets qui lui sont accessibles,

- d'autre part, les opérations permises sur ces objets.

En conséquence, les objectifs généraux qui doivent être pris en compte pour la définition de ces mécanismes sont les suivants :

- interdire tout accès entre des entités indépendantes,

- assurer la protection en fonction de la nature de l'opération qui est tentée sur l'objet,
- permettre une protection variable suivant le processus et même suivant le contexte (la situation) de ce processus,

- autoriser la variation du nombre d'agents et d'objets.

## Représentation de l'état de protection d'un système

L'ensemble des opérations qu'un agent peut effectuer sur un objet, appelé *pouvoir* de l'agent sur l'objet, définit la relation entre cet agent et cet objet. L'ensemble de toutes les relations entre agents et objets, définit, à tout instant, l'état de protection du système.

Cet état peut être représenté par une matrice (figure 1) [Lampson].

<figure><img src="image_1.png" /><figcaption>Figure 1. Exemple de matrice d'état de protection</figcaption></figure>

Par exemple, dans la figure 1, les différents objets manipulables sont des segments, des processus et des sémaphores. Les différentes opérations qui permettent de manipuler ces objets sont respectivement : lire, écrire, exécuter pour les objets segments, bloquer, détruire et activer pour les processus et P et V pour les sémaphores. Ainsi l'agent $P_1$ possède un sémaphore privé $s_1$ ; il peut lire et écrire le segment $S_1$ alors que $P_2$ peut l'exécuter. $P_1$ peut également se bloquer et se détruire alors que $P_2$ n'a aucune action possible sur $P_1$ ;

On notera, à ce propos, que l'entité processus est à la fois agent et objet. Dans l'exemple, les pouvoirs d'un processus sur les objets restent constants pour toutes les procédures (tous les programmes) exécutées par ce processus. Pour les faire varier selon, par exemple, que le processus exécute ou non une procédure du moniteur, nous introduisons un degré de protection plus fin et nous associons à un processus plusieurs contextes d'exécution possibles.
De cette façon l'agent qui accède aux objets est défini par un couple (processus, contexte). Deux agents diffèrent au moins par l'un des éléments du couple.

Les problèmes que l'on va rencontrer dans notre étude concernent :

- d'une part, la représentation en mémoire de cet ensemble de relations traduites par la matrice d'état et leur utilisation pour contrôler les actions des agents sur les objets,

- d'autre part, la modification de l'état de protection du système, qui interyient lorsqu'un processus change de contexte ou lorsqu'il y a création et destruction d'objets.

### Problème de méfiance mutuelle

Nous illustrerons cette classe de problème sur l'exemple suivant :
Considérons le cas d'un processus $p_1$ qui possède un objet D (c'est par exemple une banque de données). $p_1$ accepte de partager D avec un autre processus $p_2$ mais il souhaite que les actions de $p_2$ soient contrôlées. A cet effet, il fournit une procédure de contrôle P dotée des pouvoirs suffisants pour effectuer les références à D.

<figure><img src="image_2.png" /><figcaption>Figure 2. Exemple d'un problème de méfiance</figcaption></figure>

La méfiance de $p_1$ se traduit par les exigences suivantes :

- interdire l'accès à D, autrement que par la procédure P,

- n'autoriser l'utilisation de P, qu'à partir d'un (ou plusieurs) point d'entrée bien déterminé définissant les fonctions de P,

- contrôler les arguments fournis à P.
Les exigences requises par le processus p₂ s'expriment comme suit :
les objets qui lui sont propres doivent demeurer à l'abri des erreurs
éventuelles ou des malveillances de P, même lorsque p₂ exécute cette
procédure.

Ces problèmes de méfiance mutuelle, fréquents dans les systèmes
d'exploitation, ne sont pas toujours résolus de façon satisfaisante. En
particulier dans le système MULTICS, la relation d'ordre induite par les
anneaux de protection, ne permet de traduire la méfiance que dans un sens.

But de la présente étude

Nous pouvons maintenant préciser la nature de notre étude.

a. Nous nous plaçons dans le contexte de systèmes d'exploitation qui comportent un nombre variable d'objets partagés par un nombre variable d'agents et dans lesquels les agents sont méfiants les uns envers les autres.

b. Nous étudions les mécanismes de protection élémentaires qui permettent de bâtir des sous-systèmes sans pour autant les ordonner totalement. Pour cela nous imposons les contraintes :

- d'unicité : ces mécanismes doivent s'appliquer, à tous les objets du système quelle que soit leur nature,

- d'extensibilité : les mêmes mécanismes doivent pouvoir être utilisés pour construire des sous-systèmes protégés, le système d'exploitation en est alors un cas particulier.

c. La protection peut jouer à différents niveaux : compilation, édition de lien et exécution. Dans notre étude nous considérons la protection à l'exécution et nous la faisons porter sur les accès aux objets. Nous serons ainsi amenés à définir une structure d'adressage adaptée pour la protection, sans pour autant introduire le choix d'une machine particulière.

2. NOTION DE DESCRIPTEUR

Ensembles d'objets

Un système comporte un grand nombre d'objets qu'il faut pouvoir regrouper et isoler afin de les utiliser plus sûrement. Les critères de regroupement des objets en ensembles sont divers ; on peut vouloir réunir tous les objets :

- qui sont manipulables par les mêmes opérations,

- qu'un agent a la possibilité d'atteindre, à un instant donné,

- qui ont même durée de vie,

- et qui, d'une manière générale, ont une même propriété (degré de protection, réentrance, partage,...).

Ainsi la protection doit permettre non seulement d'isoler des ensembles
d'objets mais aussi de contrôler le passage d'objets d'un ensemble à un
autre. On notera, à ce propos, que plusieurs objets peuvent simultanément
appartenir à plusieurs ensembles.

## Caractérisation d'un objet

Un objet est caractérisé par trois éléments : un nom unique, une représentation et une liste d'opérations.

Le *nom unique* est l'indicatif qui définit l'objet sans ambiguïté dans le système. Cet indicatif ne peut pas être l'adresse physique de la représentation de l'objet car cette adresse change lorsque l'objet est déplacé en mémoire pour des raisons d'allocation d'espace. Ce ne peut être une adresse virtuelle que si tous les objets du système sont représentés dans la mémoire virtuelle. Les divers indicatifs qui sont utilisés par les agents pour sélectionner cet objet dans les différents ensembles où il apparaît, sont appelés les *noms locaux* de l'objet, par opposition au nom unique.

La *représentation* d'un objet met en jeu une suite d'emplacements et la suite de bits qu'ils contiennent ; cette dernière suite est interprétée par les opérations définies sur l'objet.

La *liste des opérations* définit les manipulations possibles sur l'objet. Seules, ces opérations peuvent entraîner une modification de la représentation de l'objet.

Dans le cas où l'objet est partagé entre plusieurs agents, chacun d'eux n'est pas systématiquement autorisé à manipuler l'objet avec toutes les opérations définies sur celui-ci, mais seulement avec un sous-ensemble d'entre elles. Pour autoriser ce genre de partage, nous introduisons la notion de *descripteur* ("capability") [Dennis].

Un descripteur est une référence à l'objet, qui contient :

- le nom unique de l'objet,

- et des *droits* qui traduisent les opérations permises sur l'objet, sous contrôle de ce descripteur.

Dans cette optique, tout accès à l'objet ne peut se faire que par l'intermédiaire d'un descripteur, la sélection par un agent d'un objet parmi d'autres, se fait alors en utilisant le *nom local* du descripteur qui repère cet objet. Ceci implique que toute modification d'un descripteur soit strictement contrôlée (en particulier un agent ne doit pas pouvoir y inscrire lui-même un nom unique d'objet ou des droits).
La nécessité de passer par un descripteur pour accéder à un objet présente plusieurs avantages :

1. il facilite la constitution et la protection d'ensembles d'objets, car un agent ne peut désigner que les objets dont les descripteurs lui sont accessibles (par un nom local),

2. il permet de traduire le partage d'un objet avec des droits différents, entre plusieurs agents,

3. il introduit une séparation explicite entre la sélection d'un objet (par la sélection d'un descripteur) et les opérations sur l'objet lui-même,

4. il permet de satisfaire, comme on le verra plus loin, l'extensibilité du mécanisme de protection.

En conséquence, un objet, de nom unique NU, existe dans le système tant qu'il existe le couple d'éléments suivants :

- un (ou plusieurs) descripteur contenant le même nom unique NU,

- et une représentation que le système sait retrouver avec l'indicatif NU.

Corollairement une représentation dont l'indicatif NU n'apparaît dans aucun descripteur, n'a pas de sens et les emplacements correspondants de la mémoire doivent être récupérés par le système.

**Remarque.** La valeur d'un objet peut être indéterminée ou vide ; cela n'a aucune influence sur le nombre de descripteurs qui repèrent cet objet.

## Protection des descripteurs

Nous ayons vu que les descripteurs ne devaient pas être modifiés, sans contrôle. Leur protection peut être obtenue de deux façons :

- soit chaque emplacement de mémoire est précédé d'un préfixe qui indique si son contenu est un descripteur ou non ; c'est la méthode appliquée dans la Burroughs B6700.

- soit les descripteurs sont regroupés dans des zones particulières de mémoire, protégées en bloc et appelées D-liste. C'est la méthode utilisée dans la Plessey P250 [England].

Pour l'instant, nous avons retenu arbitrairement la seconde méthode qui présente l'avantage de ne pas lier les longueurs de mot et de descripteur.

La protection élémentaire est obtenue par des mécanismes câblés.

On appelle noyau, la partie du système qui réalise les mécanismes d'extensibilité de cette protection ; le noyau est la partie la plus protégée du système. D'après ce que nous avons vu, ses principales fonctions sont :
- la gestion des noms uniques des objets,

- la construction des descripteurs.

# 3. CONSTRUCTION D'OBJETS

## 3.1. GENERALITES

### Notion de type d'objet

Parmi les objets d'un système, tous ne présentent pas des caractéristiques différentes. Plusieurs objets peuvent être définis et manipulés par la même liste d'opérations : ils appartiennent alors à une même classe d'équivalence caractérisée par la liste des opérations possibles sur ces objets ; nous dirons qu'ils sont du même type. La notion de type permet alors de réaliser une partition de l'ensemble des objets [Boulenger], [Gray], [Morris], [Wulf].

On distingue les types primitifs et les types construits. Un *type* primitif est un type dont on suppose l'existence a priori et qui est reconnu par le câblé. Les objets appartenant à un type primitif sont appelés des objets primitifs. A partir de types primitifs, il est possible d'élaborer, par programme, d'autres types d'objets ; on parle alors de *types construits*.

### Caractérisation d'un type

Un type d'objet est caractérisé par trois éléments : une marque de type, une règle de construction, une liste d'opérations.

La *marque de type* est un indicatif quï définit sans ambiguïté le type dans le système. Elle est commune à tous les objets appartenant à ce type.

La *règle de construction* définit la construction d'un objet du type à partir d'un objet d'un type déjà défini. Tous les objets d'un type donné sont construits suivant la même règle de construction qui est utilisée par l'algorithme de création d'un nouvel objet du type, ainsi que par les opérations de manipulation de ces objets. Elle fait intervenir, en particulier, le type des objets qui entrent dans la composition du nouveau type.

La *liste d'opérations* regroupe toutes les opérations qu'il est possible d'effectuer sur les objets du type. Elles ont été spécifiées, une fois pour toutes, au moment de la définition du type, et sont telles qu'elles acceptent en arguments un (ou plusieurs) objet(s) du type. Pour que la protection soit effectivement réalisée, il faut contrôler que l'objet fourni en argument à ces opérations, est bien de type attendu. Enfin ces opérations connaissent la construction d'un objet du type et disposent des opérations (ou d'une partie seulement) permettant de manipuler les objets du type constituant.
**Remarque.** L'algorithme de création d'un objet de type donné doit avoir été spécifié au moment de la définition du type. A la différence des opérations de manipulation, l'opération de création ne reçoit pas en arguments des objets de ce type mais au contraire les délivre comme résultat. Bien qu'elle ne fasse pas partie des opérations de manipulation, elle est implantée et contrôlée selon le même schéma.

## Représentation des objets

L'extensibilité recherchée pour notre système de protection consiste à utiliser les types primitifs pour construire, de proche en proche, d'autres types d'objets pour lesquels les opérations de manipulation sont définies par programme. Avant de présenter le mécanisme permettant de réaliser dynamiquement des types construits, nous analysons les caractéristiques des objets.

Pour marquer l'appartenance d'un objet à un type, tout descripteur d'objet contient désormais : une marque de type, un nom unique et des droits.

Les droits représentent les opérations définies sur ce type. A chaque opération est associé un droit dans le descripteur ; lorsque l'opération est permise le droit est présent. Dans le cas d'une opération à plusieurs arguments du même type, plusieurs droits peuvent être nécessaires.

## 3.2. LES OBJETS DE TYPE PRIMITIF

Les types d'objets dont nous supposons l'existence a priori sont : le type Segment, le type D-liste, le type Transition, et le type Domaine. La création d'objets de types primitifs sera étudiée ultérieurement (voir 6.1.). Nous présentons ici les types Segment et D-liste.

### Le type Segment

Tout objet de type Segment est appelé segment. Un segment est représenté par une suite de L emplacements (mots) en mémoire. Les opérations possibles sur un segment sont :

- les opérations classiques (lecture, écriture et exécution) d'accès à un mot du segment dans la limite $[0,L]$,

- et les opérations de modification de la taille L du segment, et de destruction du segment.

A chacune de ces opérations, est associé un droit dans le descripteur du segment.
<figure><img src="image_3.png" /><figcaption>Figure 3. Descripteur d'un segment</figcaption></figure>

Certaines opérations, lecture, écriture, exécution, sont directement interprétées par le câblé et le descripteur qui leur sert d'opérande est nécessairement un descripteur de segment. En outre, chaque processus peut les utiliser quel que soit son contexte d'exécution. Les autres sont programmées dans le noyau et leur utilisation est contrôlée. Dans ce cas, un descripteur de segment doit être fourni comme argument de l'opération réalisant la fonction attendue.

## Le type D-liste

Tout objet de type D-liste est appelé D-liste. Une D-liste est représentée en mémoire par une suite de L emplacements qui contiennent ou qui sont appelés à contenir des descripteurs. Ceci a deux conséquences, sur le plan de la protection :

- d'une part, une D-liste ne doit pas contenir autre chose que des descripteurs,

- d'autre part, tout emplacement d'une D-liste qui, à un instant donné, n'est plus significatif, doit être rendu inutilisable.

La première contrainte qui est à la base du mécanisme de protection, impose de séparer nettement les opérations sur les segments et les opérations sur les D-listes. En particulier, il ne faut transférer dans une D-liste que des éléments qui se trouvent déjà dans une autre D-liste, et qui, à ce titre, jouent déjà le rôle de descripteurs.

La deuxième contrainte impose de prévoir un descripteur vide. Pour cela, il suffit d'introduire un type supplémentaire d'objet, le type nul (noté $\emptyset$). Dans ces conditions, toute utilisation d'un descripteur de type nul lors de l'accès à un objet, correspond forcément à une erreur et pour cette raison doit être interceptée par le mécanisme de protection.
Les opérations possibles sur une D-liste sont :

- les opérations de lecture et d'écriture d'un descripteur dans la D-liste,

- les opérations de modification de la taille L de la D-liste, et de destruction de la D-liste.

Les premières sont directement interprétées par le câblé et sont disponibles au processus quel que soit son contexte d'exécution, les autres sont programmées dans le noyau et leur emploi est contrôlé.

<figure><img src="image_4.png" /><figcaption>Figure 4. Descripteur d'une D-liste</figcaption></figure>

**Remarque.** On pourrait aussi introduire une opération de copie d'un descripteur d'une D-liste a dans une autre D-liste b ; cette opération à plusieurs arguments, met en jeu deux descripteurs de D-liste. Son utilisation n'est possible que si les droits de lecture pour a et d'écriture pour b sont présents dans les descripteurs.

## 3.3. LES OBJETS DE TYPE CONSTRUIT

### Généralités

Un type construit est un type dont chaque objet est obtenu à partir d'un objet existant, appartenant à un type déjà défini (primitif ou non). Les opérations qu'il est possible d'effectuer sur les objets du type construit $T^j$ sont propres à la classe d'équivalence définie par ce type et nécessairement réalisées par programme. Le descripteur d'un objet de type construit
$T^j$ contient la marque du type $T^j$, le nom unique de l'objet et des droits.
**Remarque.** Le descripteur d'un objet de type construit $T^j$ ne peut pas être utilisé par les opérations définies sur les segments ou les D-listes.

La seule façon d'accéder à l'objet consiste à interpréter son descripteur à l'aide des opérations programmées $op_j^j, \dots, op_n^j$ définies sur le type $T^j$. Le droit d'appeler ces opérations et la façon de réaliser l'appel seront étudiés au chapitre 4.

## Représentation d'un objet de type construit

La représentation d'un objet $o$ de type construit $T^j$ est la représentation de l'objet $o'$ de type $T^i$ ($i \prec j$) * à partir duquel il est réalisé.

Il en résulte que le nom unique de l'objet $o$ est identique au nom unique de l'objet $o'$. La représentation est toutefois interprétée différemment selon qu'il s'agit des opérations définies sur le type $T^j$ ou des opérations définies sur le type $T^i$.

**Remarque.** Une même représentation est utilisée pour des objets de types différents ; c'est la raison pour laquelle la marque de type n'est pas associée à la représentation mais au contraire figure dans les descripteurs.

<figure><img src="image_5.png" /><figcaption>**Figure 5.** Représentation d'un objet de type construit $T$.</figcaption></figure>

<footnote>* la notation $i \prec j$ traduit l'ordre chronologique de construction de type.</footnote>
La figure 5 représente un objet de type construit T, obtenu à partir d'un objet de type Segment.

### Exemple.

Le processus en exécution dans un environnement matérialisé par la D-liste a (voir figure 5), peut manipuler le segment de nom local $D_i$, au moyen des opérations câblées lecture (l) et écriture (e). Lorsqu'il s'exécute dans l'environnement matérialisé par la D-liste b, il peut manipuler l'objet de type T et de nom local $D_j$, au moyen des opérations programmées $op_1, ..., op_n$. Les deux objets de noms locaux respectifs $D_i$ et $D_j$ possèdent la même représentation qui est interprétée de façon différente suivant l'opération mise en jeu (opérations définies sur les segments ou sur le type T).

### Construction d'objets composés

La construction d'objets qui vient d'être présentée lie un type $T^j$ à un type $T^i$, unique, déjà créé. Elle permet la définition d'un nouvel objet $o^j$ à partir d'un objet $o^i$ déjà existant et d'un seul ; elle ne permet pas la définition d'un objet $o^j \in T^i$, composé à partir d'un ensemble d'objets déjà construits $o^{i1} \in T^{i1}, o^{i2} \in T^{i2}, ..., o^{in} \in T^{in}$.

Pour obtenir cette composition, il faut faire intervenir l'élément de regroupement que représente la D-liste et construire le type $T^j$ à partir de celle-ci. Les descripteurs des objets $o^{i1}, o^{i2}, o^{i3}$ sont regroupés dans une D-liste qui constitue, dès lors, un objet intermédiaire unique. C'est cet objet qui est utilisé pour construire un objet du nouveau type $T^j$. Les opérations définissant le type $T^j$ sont contrôlées par les droits d'un descripteur de type $T^j$ ; le regroupement des composants et l'accès à ceux-ci en tant qu'éléments d'une D-liste, suivent les règles définies par les opérations sur les D-listes.

Cette utilisation des D-listes pour composer des objets conduit à la classification suivante des types et des objets construits : un type est **construit complexe** si les objets de ce type sont construits à partir de D-listes, sinon il est **construit simple**.
<figure><img src="image_6.png" /><figcaption>a) Objet de type construit simple</figcaption></figure>

<figure><img src="image_7.png" /></figure>

**Nota** : La D-liste intermédiaire ne pourrait contenir qu'un seul élément ou aucun.

**Figure 6.** Exemples d'objets de types construits simple et complexe.

**Remarque.** L'emploi des D-listes peut entrainer des circuits dans les références aux objets et dans ce cas, un programme peut être amené à boucler. Ces circuits pourraient être évités, au niveau de la construction des objets :
- d'abord, en imposant que tout objet d'un type $T^j$ ne soit obtenu que par regroupements d'objets d'un type déjà existant, au moment de la création de $T^j$,

- ensuite, en ne créant qu'un seul type à la fois.

En effet, dans ce cas, les types pourraient être rangés selon l'ordre
chronologique et tous les objets être classés selon cette relation d'ordre.

Cette solution imposerait que :

- la construction simple d'un objet $o^j \in T^j$, à partir d'un objet $o^i \in T^i$ ne soit possible que si $i < j$.

- la composition d'un objet $o^j \in T^j$, à partir d'une D-liste contenant des objets $o^i_1 \in T^i_1, \dots, o^i_n \in T^i_n$ ne soit possible que si $i_1 < j, \dots, i_n < j$.

## Niveau d'interprétation d'une représentation

Nous avons présenté la construction d'un objet d'un nouveau type à partir d'un objet d'un type déjà défini. On peut répéter cette construction, de proche en proche, si à chaque étape i, on a défini les opérations $op_i^1, \dots, op_i^j, \dots, op_i^r$ de manipulation et l'opération de création des objets du type $T^i$. Alors une même représentation en mémoire peut se trouver repérée par des descripteurs de types différents et manipulée par des opérations différentes suivant l'environnement d'exécution du processus. Ceci peut être utilement exploité pour construire d'une manière structurée des sous-systèmes protégés.

<figure><img src="image_8.png" /><figcaption>**Figure 7.** Niveaux d'interprétation d'une représentation</figcaption></figure>
Exemple.

La figure 7 traduit les différents environnements possibles d'un
processus. Au niveau 0 matérialisé par la D-liste 0, le processus a accès au
segment de nom local s ; c'est à ce niveau que seront définies, en terme
d'opérations sur le segment, les opérations notées op de manipulation des
objets de type T. Au niveau 1, matérialisé par la D-liste 1, le processus
peut manipuler l'objet o de type T, construit à partir du segment s ; les
opérations qu'il peut appliquer sur cet objet o sont les opérations op
définies au niveau 6.

Le même raisonnement permet de progresser jusqu'au niveau j. Ceci
suppose que les opérations notées $op^j$ :

- d'une part, acceptent en arguments des objets de type $T^j$,

- d'autre part, sont définies au niveau (j-1) en termes d'opérations de ce niveau, et habilitées à transformer le type $T^j$ des objets passés en arguments en type $T^{j-1}$.

3.4. COPIE DES DESCRIPTEURS

La copie des descripteurs d'une D-liste dans une autre, est
nécessaire pour plusieurs raisons :

- pour définir un objet composé en regroupant des descripteurs dans
une même D-liste,

- pour réaliser le passage d'arguments, à l'appel d'une opération
programmée,

- pour traduire des accès différents à un même objet, selon le contexte
d'exécution, etc...

La copie des descripteurs est réalisée au moyen des opérations
(lecture, écriture) définies sur les D-listes. Elle se fait en conservant les
droits, ou au contraire en les restreignant, autrement dit, en limitant les
opérations autorisées sur l'objet à un sous-ensemble des opérations possibles.
De cette façon, on garantit un minimum de protection puisqu'aucun agent ne
peut alors acquérir plus de droits qu'on ne lui en passe.

Tout agent dispose implicitement des opérations de manipulation des
descripteurs d'une D-liste. La protection joue toutefois sur la D-liste mais
non sur les descripteurs qui y sont contenus ; ainsi tout agent qui a accès
en lecture à une D-liste peut y lire n'importe lequel des descripteurs qui
y figurent et l'écrire dans une autre D-liste, pour laquelle il a le droit
d'écrire.
### 3.5. TRANSFORMATION DU TYPE D'UN OBJET

#### Présentation du problème

Nous avons vu que la définition d'un nouveau type construit $T^j$, à partir d'un type $T^i$ existant, s'accompagne de la définition de la règle de construction et des opérations $op_i^j, ..., op_n^j$.

Ces opérations doivent, en utilisant la règle de construction, transformer les objets de type $T^j$, reçus en arguments, en objets de type $T^i$ pour lesquels elles disposent des opérations $op_i^j, ..., op_m^i$ ; il ne doit pas être possible aux opérations associées au type $T^j$ de transformer $T^j$, en un autre type $T^k$ ($k \neq i$) qui n'entre pas dans la construction du type $T^j$.

De même l'opération de création d'un objet du type $T^j$ doit connaître la règle de construction de celui-ci ; à partir d'objets de type $T^i$, elle fournit des objets de type $T^j$ et uniquement des objets de ce type.

En conséquence, la transformation des objets de type $T^j$ en objets de type $T^i$ (et inversement) doit être contrôlée [Morris].

#### Le type Transition

Le droit à transformer le type d'un objet est considéré, lui aussi, comme un objet. Cet objet appartient au type Transition (type primitif) et son utilisation est contrôlée par un descripteur.

Un objet de type Transition est appelé une transition. Une transition définit simultanément :

- le type de l'objet sur lequel doit porter la transformation et les droits minimaux qui doivent être associés à cet objet, pour que la transformation soit possible,

- le type et les droits du nouvel objet, obtenus après transformation.

Les opérations possibles sur une transition sont : composer, décomposer, contrôler et détruire-type. Etant donné la transition $(T^i, d^i) \stackrel{\sim}{\leftrightarrow} (T^j, d^j)$ l'opération *composer* définit la transformation $T^i \rightarrow T^j$ : elle permet d'obtenir, à partir d'un objet de type $T^i$, un nouvel objet de type $T^j$ et de droits $d^j$ ; dans ce cas, les droits $d^i$ définissent les droits minimaux requis sur l'objet de type $T^i$.

Au contraire, l'opération *décomposer* définit la transformation $T^i \leftrightarrow T^j$ : elle permet d'obtenir, à partir d'un objet de type $T^j$, l'objet constituant de type $T^i$ et de droits $d^i$. Dans ce cas, ce sont les droits $d^j$ qui définissent les droits minimaux requis de l'objet de type $T^j$ pour que cette opération soit possible.
L'opération _contrôler_ sera évoquée à propos du contrôle des arguments (voir 4.5), _détruire-type_ sera décrite dans le chapitre 5.2, traitant de la destruction de type.

**Remarque.** Toutes ces opérations sont directement interprétées par le câblé et sont utilisables par le processus quel que soit son contexte d'exécution.

Comme les objets de type Transition ne sont pas partagés et que leur représentation est suffisamment courte, celle-ci est directement rangée dans le descripteur à la place du nom unique qui n'a plus de raison d'être. Le descripteur d'un objet de type Transition [Lindsay] est défini de la façon suivante :

- la marque du type Transition,

- des droits: ils définissent un sous-ensemble des opérations possibles sur cette transition, à l'exclusion de _contrôler_ qui est toujours autorisée,

- la représentation de l'objet : elle définit la transformation de type $(T^i, d^i) \rightsquigarrow (T^j, d^j)$.

<figure><img src="image_9.png" /><figcaption>**Figure 8.** Descripteur d'un objet de transition</figcaption></figure>

Nous dirons qu'un type $T^i$ est en amont d'un type $T^j$ lorsqu'il existe une transition permettant de composer des objets de type $T^j$ à partir d'objets de type $T^i$. Cette transition est alors dite _transition amont_ pour le type $T^j$ et _transition aval_ pour le type $T^i$. On parlera également de droits amont et aval.
## Remarques.

1. Le descripteur d'une transition peut être copié d'une D-liste dans une autre ; cette copie peut éventuellement s'accompagner d'une restriction des droits.

2. Dans tous les cas, la partie représentation de la transition reste invariante à l'exception toutefois des droits associés au type aval qui eux sont modifiables. La justification en sera donnée plus loin.

## Manipulation d'une transition

La transformation de type $T^i \to T^j$ est mise en jeu par diverses opérations, à savoir :

- les opérations $op_j^i, ..., op_n^j$ de manipulation des objets du type $T^j$,

- et l'opération de création d'objets de type $T^j$.

Les premières acceptent en arguments, des objets de type $T^j$ et les décomposent en utilisant l'opération décomposer et la transition $(T^i, d^i) \to (T^j, d^j)$ dans laquelle $T^j$ est en aval de $T^i$. Toutes ces opérations $op_j^i, ..., op_n^j$ ne nécessitent pas toutefois les mêmes droits $d^j$, sur les arguments ; pour cette raison, chaque opération $op_k^j$ met en jeu une transition particulière qui ne diffère alors des autres que par les droits $d_k^j$.

L'opération de création d'un objet de type $T^j$, opère par composition d'objets de type $T^i$, en utilisant l'opération composer et la transition $(T^i, d^i) \to (T^j, d^j)$ dans laquelle $T^j$ est en aval de $T^i$. A la création d'un objet de type $T^j$, tous les droits sur cet objet sont présents ; ils correspondent à toutes les opérations $op_j^i, ..., op_n^j$ définies sur le type $T^j$. **Remarque.** La modification du droit aval $d^j$ d'une transition n'a pas d'importance. Ce droit n'a pas besoin d'être protégé : en effet, il est utilisé seulement par les opérations de manipulation des objets du type $T^j$, qui sont données. Par contre, il est impératif que le droit amont $d^i$ ne puisse être modifié pour éviter, à l'occasion d'une décomposition, de manipuler des objets de type $T^i$ avec des opérations $op_j^i, ..., op_m^i$ qui n'auraient pas été autorisées sur ces objets. Ce point sera étudié plus en détail en 4.5.

## 3.6. CREATION D'UNE TRANSITION

La création d'un nouveau type d'objet $T^j$ impose de définir la marque de type, la règle de construction ainsi que les opérations de manipulation et de création, d'un objet du type. Puisque ces opérations ne peuvent être définies qu'une fois fixée la règle de construction, la création d'un type $T^j$ se fera donc en 2 étapes :

- création d'une transition,
- définition des opérations de manipulation et de création d'un objet du type.

La création d'une transition est réalisée par le noyau, à l'appel de l'opération allouer-marque. Cette opération alloue une marque de type originale et délivre comme résultat un objet de transition ($T^i, d^i$) $\stackrel{\rightarrow}{\rightleftharpoons}$ ($T^j, \*$). Elle doit donc recevoir en argument les informations nécessaires à l'élaboration de cet objet, à savoir :

- la marque du type amont $T^i$,

- les droits $d^i$ qui sont requis sur les objets de ce type, par les opérations du nouveau type.

Ceci nécessite de la part de l'agent créateur du type $T^j$, la connaissance du type $T^i$; elle est matérialisée par la possession dans son environnement d'une transition amont pour le type $T^i$. C'est cet objet qui est passé en argument à l'opération allouer-marque.

### Remarques.

1. Les droits aval qui figurent dans la transition délivrée par allouer-marque sont maximaux. Toute transition ($T^i \stackrel{\rightarrow}{\rightleftharpoons} T^j$) nécessaire à la description des opérations du type $T^j$ sera obtenue par copie (avec éventuellement restriction des droits aval $d^j$) de la transition originale.

2. L'opération allouer-marque délivre, à chaque appel, une marque de type nouvelle. On est donc assuré, de cette façon que la construction de type se fait toujours à partir d'un type existant. Ceci entraine qu'il ne peut y avoir de cycle dans la définition de type.

## 4. LES DOMAINES

### 4.1. CARACTERISATION D'UN DOMAINE

#### Notion d'environnement

La notion de *domaine* est introduite pour traduire la variation du pouvoir d'un processus sur les objets du système. Un domaine regroupe les objets nécessaires à la réalisation d'un traitement et spécifie les droits d'accès à ceux-ci.

Un domaine constitue une enceinte de protection où, seuls les objets décrits dans ce domaine, sont accessibles au processus qui s'y exécute et ceci avec les droits mentionnés. On limite de la sorte la propagation des erreurs et on facilite leur détection. L'exécution d'un processus devient alors une suite d'appels de domaines.
Pour que cette enceinte reste étanche, un contrôle doit être opéré quand un processus change de domaine. En particulier, un processus n'a pas le droit d'entrer dans un domaine en appelant une procédure quelconque décrite dans ce domaine. Seules quelques procédures du domaine peuvent être appelées de l'extérieur, ce sont les points d'entrée du domaine.

Un domaine est un objet qui se caractérise par :

Une liste de points d'entrée. Chacun d'eux correspond, en principe, à un objet exécutable de type Segment.

Une D-liste décrivant l'ensemble des objets accessibles dans le domaine. Nous appelons cet objet D-liste d'environnement du domaine ou environnement. Tout objet n'est accessible qu'à l'intérieur d'un environnement et avec les droits spécifiques du domaine auquel appartient cet environnement. Le nom local d'un objet repère le descripteur de l'objet dans l'environnement du domaine.

Pour que la protection des objets d'un type construit soit effective, la transformation de leur type ne devrait être permise que dans l'environnement des opérations du type. L'application directe de la notion de domaine permet d'assurer cette protection :

en regroupant à l'intérieur d'un même domaine les opérations qui spécifient le nouveau type,

en associant chacune de ces opérations à un point d'entrée du domaine afin d'en contrôler l'accès. Par extension, on appelle opération tout traitement résultant de l'appel d'un point d'entrée d'un domaine.

### Accès aux opérations

Le contrôle de l'accès aux opérations se fait selon leur nature, câblées ou programmées :

- Les opérations câblées sont permises dans tout domaine. Rappelons toutefois que l'opération ne peut s'effectuer que si le descripteur de l'objet primitif qui lui sert d'opérande contient le droit d'exécuter cette opération.

- Les opérations programmées ne sont permises dans un domaine que si celui-ci possède dans son environnement, les descripteurs des domaines où elles sont définies.

### Réalisation des opérations programmées

La manipulation, par un domaine D, d'objets du type construit T, est possible de deux façons :

- Si le domaine D ne peut pas décomposer les objets du type T, dans ce cas il doit pouvoir appeler un domaine D' capable de recevoir en paramètres des objets de type T.
- Si le domaine D peut décomposer les objets de type T en objets de type T', ou bien T' est primitif et D dispose des opérations permettant de manipuler directement des objets de ce type, ou bien T' n'est pas primitif et on se ramène au cas de manipulations par D d'objets de type T' (au lieu du type T).

La transmission d'objets d'un domaine à un autre nous conduit à distinguer deux classes d'opérations. Une opération est dite **forte** pour un type T donné d'objets si le domaine dans lequel elle existe, peut décomposer les objets de ce type T, reçus en paramètres. Par opposition, nous dirons qu'une opération d'un domaine est **faible** pour un type T donné, si un objet de ce type reçu en paramètre n'est pas décomposé dans le domaine mais si au contraire, il est fait appel à un autre domaine pour cela.

**Remarque 1.** Une opération qui reçoit en paramètres, plusieurs objets de types différents peut être, à la fois, forte pour certains types et faible pour d'autres.

2. A une opération **forte**, il correspond au minimum un droit dans le descripteur des objets qu'elle décompose.

## 4.2 L'OBJET DE TYPE DOMAINE

Tous les domaines appartiennent à un même type ; le type Domaine. Le type Domaine est primitif construit complexe ; il est reconnu par le câblé et chaque objet de ce type est obtenu par composition d'une D-liste.

Celle-ci contient :

- le descripteur de la D-liste d'environnement du domaine,

- autant de descripteurs de segments exécutables qu'il existe de points d'entrée dans le domaine.

Cette composition est réalisée par l'opération **créer-domaine** incluse dans le noyau. La figure 9 schématise la composition d'un domaine, le descripteur de cet objet est défini par :

- la marque domaine,

- une liste de droits, représentant la liste des opérations permises sur cet objet,

- le nom unique de la représentation commune à la D-liste décrite précédemment.

Les opérations possibles sur un domaine sont câblées (appel et retour) ou réalisées dans le noyau (détruire). Le retour permet le rappel du domaine appelant au point suivant l'appel, il est toujours permis, les droits apparaissant dans le descripteur d'un domaine ne concernent donc que les opérations d'appel et de destruction.
Pour traduire le fait qu'un domaine peut avoir plusieurs points d'entrée et pour contrôler leur appel, nous associons à chacun d'eux, un droit dans le descripteur : on appelle ce droit, **guichet**.

La possession du guichet associé à une opération sous entend alors
le droit d'appeler le domaine qui la contient.

<u>Exemple.</u>

Dans la figure 9, le processus est autorisé à exécuter les opérations op₁ et op₃ définies dans le domaine de nom local d, car il en possède les guichets.

<figure><img src="image_10.png" /><figcaption>**Figure 9.** Exemple d'un domaine à trois points d'entrée</figcaption></figure>
### 4.3 APPEL ET RETOUR DE DOMAINE

L'appel d'une opération s'écrit : **appel** (d,g,p) où d est le nom local chez l'appelant du domaine appelé et g le nom d'un point d'entrée c'est-à-dire également le nom que possède l'opération dans la D-liste obtenue par décomposition du domaine appelé. p est utilisé pour transmettre les paramètres effectifs au domaine appelé.

Pour que l'appel d'un domaine devienne effectif, les conditions suivantes doivent être respectées :

- le processus doit posséder dans son contexte un descripteur du domaine appelé,

- l'opération demandée doit être autorisée au processus qui doit donc en posséder le guichet,

- le point d'entrée demandé doit correspondre à un segment exécutable.

A chaque appel d'un nouveau domaine, le contexte est sauvegardé dans une pile associée au processus afin de préparer le retour. L'environnement du domaine appelé est utilisé comme un modèle pour établir le nouveau contexte du processus et le descripteur du segment exécutable correspondant au point d'entrée définit la nouvelle valeur du compteur ordinal.

### 4.4. TRANSMISSION D'OBJETS ENTRE DOMAINES

#### Principes

La transmission d'objet entre domaines se fait en passant un descripteur de l'objet. L'argument doit être accessible à la fois au domaine appelant et au domaine appelé. Ceci est obtenu en effectuant, lors de l'appel, la recopie du descripteur de l'objet à un emplacement fixé du nouveau contexte. Au retour le lien vers l'objet est rompu par effacement de cet emplacement.

Si plusieurs objets doivent être transmis, leurs descripteurs sont regroupés par l'appelant dans une D-liste ; on se ramène ainsi à la transmission d'un seul objet. Lorsqu'au retour des objets doivent être transmis à l'appelant, la même D-liste est utilisée. La figure 10 schématise ce mécanisme.
<figure><img src="image_11.png" /><figcaption>Figure 10. Transmission d'objets entre domaines</figcaption></figure>
La transmission d'objets entre domaines pose des problèmes différents selon que l'on considère le point de vue du domaine appelant ou du domaine appelé :

a. vu du domaine appelant : le mécanisme de protection doit assurer que les objets qu'il transmet ne peuvent pas être manipulés à l'aide d'opérations qu'il n'a pas autorisées sur ces objets. Lors du retour, le problème se pose de façon symétrique.

b. vu du domaine appelé : le mécanisme de protection doit permettre au domaine appelé de s'assurer que l'objet reçu est conforme à l'objet attendu. Lors du retour, ce point de vue devient celui du domaine appelant.

### Contrôle par l'appelant

Ce contrôle est assuré par le fait que c'est le descripteur de l'objet qui est passé. Il est possible de recopier un descripteur en restreignant les droits sur l'objet ; ce mécanisme peut être utilisé par un domaine pour protéger les objets qu'il transmet. Le mécanisme de protection assure alors que tout domaine recevant un objet ne pourra pas le manipuler avec d'autres opérations que celles qui sont validées par les droits figurant dans le descripteur de cet objet. Cependant le problème se pose différemment lorsque l'objet est reçu par un domaine regroupant des opérations fortes pour le type de cet objet. Puisque ces opérations décomposent les objets de ce type qu'elles reçoivent, il s'agit d'assurer qu'elles ne peuvent pas à l'aide des opérations composer et décomposer, acquérir des droits qu'elles ne devraient pas posséder. En fait, le problème ne se pose que lorsque la création d'objets d'un type T' a lieu à partir d'objets de type T déjà existants et reçus en paramètres lors de l'appel. En effet, si le domaine appelé crée lui-même les objets de type T, il possède déjà sur ceux-ci les droits maximaux.

**Exemple.**

Soit trois domaines $D_1, D_2, D_3$ (voir figure 11) : dans $D_1$ est décrit l'objet o de type T avec les droits $d_1$ ; dans $D_2$ est décrit le même objet passé de $D_1$ à $D_2$ avec les droits $d_2 \subseteq d_1$ ; $D_3$ regroupe les opérations définies sur les objets de type T' créés à partir d'objets de type T. Si $D_2$ veut obtenir un objet o' de type T', il doit en demander la création à $D_3$ qui possède la transition $(T \rightleftarrows T')$ permettant de construire des objets de type T' à partir d'objets de type T ou de décomposer des objets de type T' en objets de type T. Nous devons nous assurer que le domaine $D_3$ ne pourra pas acquérir sur l'objet o qui lui est transmis par $D_2$ des droits supérieurs
ni à $d_1$ ni à $d_2$. De par le fonctionnement des opérations composer et décomposer, cette protection est toujours effective.

<figure><img src="image_12.png" /><figcaption>Figure 11. Contrôle par l'appelant</figcaption></figure>

### preuve :

Soient $t$ et $t'$ respectivement les transitions utilisées pour réaliser les opérations de composition et de décomposition dans le domaine $D_3$. Soient $d_T$ et $d'_T$ les droits amont associés au type $T$ et $d'_T$, les droits aval associés au type $T'$ dans $t$ et $t'$ respectivement. Nous savons que : $d_T = d'_T$ et que : $d'_T \subseteq d'_T$, d'après ce qui a été vu en 3.4.

Si l'objet $o$ a pu servir à construire un objet $o'$ de type $T'$, c'est nécessairement que $d_2 \supseteq d'_T$ d'après l'algorithme de cette opération. En conséquence l'objet $o'$ ne pourra être décomposé en l'objet $o$ qu'avec les droits $d'_T = d'_T \subseteq d_2 \subseteq d_1$.
Contrôle par l'appelé

Ce contrôle a pour but de permettre à l'appelé de vérifier que les objets reçus sont du type attendu et que les droits sur ces objets sont conformes aux droits requis. Le contrôle des droits vise deux objectifs différents selon que l'opération qui l'effectue est une opération faible ou forte pour le type de l'objet reçu.

- cas d'une opération faible. Le rôle de ce contrôle est de permettre à l'opération appelée de vérifier que les droits transmis par l'appelant sont suffisants pour réaliser le traitement demandé.

- cas d'une opération forte définie sur les objets de ce type. Considérons l'opération op définie sur les objets de type T. Supposons qu'un domaine possédant des objets de ce type veuille appeler cette opération. On peut contrôler que le domaine qui réalise l'appel de l'opération op possède un guichet vers cette opération ; cependant, il faut également vérifier que cette opération est autorisée à l'appelant sur l'objet transmis lors de l'appel.

Ce contrôle des paramètres peut être assuré systématiquement par l'instruction d'appel ou au gré du domaine appelé avant l'utilisation de l'objet.

Le première méthode [Wulf] consiste à associer à chaque point d'entrée une liste contenant un modèle (type, droits) de chacun des paramètres attendus et à assurer, lors de l'appel, la comparaison terme à terme de cette liste et de la liste des paramètres effectifs. Ceci ne suffit pas toujours à contrôler totalement les objets transmis et n'est en général pas satisfaisant. En effet :

- Lorsque l'objet transmis doit être décomposé au cours du traitement, un nouveau contrôle est assuré par l'opération de décomposition.

- Si l'objet est de type D-liste, le contrôle de cet objet à l'appel est insuffisant. Il doit être complété par le contrôle du type et des droits de chacun de ses composants.

- Enfin, le contrôle des paramètres est un choix qui peut être laissé au domaine qui les reçoit. En tout état de cause, l'intégrité des objets est assurée par le mécanisme de protection puisque l'accès ne peut se faire qu'à l'aide du descripteur fourni par l'appelant.

Seule la méthode qui consiste en un contrôle des objets au gré du domaine qui les reçoit permet d'assurer la totalité des vérifications nécessaires. Cependant, comme il est effectué librement par le domaine qui reçoit les objets, on n'assure pas ainsi que ce contrôle aura lieu. Ceci n'est effectif que lorsque l'objet reçu doit être décomposé car le contrôle
est alors réalisé systématiquement par l'opération décomposer. Notons que
dans ce dernier cas, le modèle nécessaire au contrôle de l'objet est une
transition. Lorsqu'il ne s'agit que de contrôler un objet qui ne doit pas
être décomposé, il ne semble pas nécessaire qu'il en soit de même, le
modèle fourni peut être une simple donnée (mot d'un segment ou contenu d'un
registre de donnée). En fait, la lecture du contenu d'un descripteur
n'existant pas, il n'est jamais possible de connaître la marque d'un type.
Seule la possession par un domaine d'objets d'un type donné T ou d'une
transition dans laquelle apparaît le type T lui assure la connaissance de
ce type. On assure donc le contrôle des paramètres à l'aide d'une transition
car seuls ces objets contiennent les informations nécessaires à ce contrôle.
Il se fera à l'aide de l'opération contrôler (t,p) où t est le nom local
d'une transition et p celui de l'objet à contrôler. Cette opération utilise
les champs "type aval" et "droit aval" de la transition et est toujours
autorisée à un agent quels que soient les droits possédés sur cet objet. On
rappelle que son utilisation n'est pas nécessaire lorsque l'objet à
contrôler doit en plus être décomposé.

# 5. DESTRUCTION DES OBJETS ET DES TYPES

## 5.1. DESTRUCTION D'UN OBJET

*Définitions*

On dit qu'un objet est détruit lorsqu'aucun agent ne peut plus
accéder à sa représentation, c'est-à-dire lorsqu'il n'existe plus de
représentation pour cet objet ou de descripteur permettant d'atteindre
cette représentation. **Quand ces deux conditions sont réalisées simultanément**
la destruction est **complète**, sinon elle est **partielle**.

Un agent peut demander la destruction d'un objet quand le droit
correspondant apparaît dans l'un des descripteurs de l'objet qui figurent
dans son environnement. On dit alors que l'agent est maître de cet objet.

Plusieurs agents peuvent être maîtres du même objet. Inversement,
un objet peut être sans maître si le droit de le détruire n'apparait dans
aucun descripteur ou si cette opération n'existe pas pour les objets de
ce type.

La destruction d'un objet intervient à la demande explicite d'un
agent, maître de cet objet ou implicitement quand tous les descripteurs
ont été détruits.
## Destruction d'un objet primitif

La destruction complète d'un objet nécessite la recherche et la destruction de tous ses descripteurs. Comme aucune trace n'est gardée de leur propagation (par un chaînage inverse, par exemple), cette recherche serait une opération parfois complexe. Aussi procède-t-on en deux étapes lorsque la destruction est demandée par un agent. La représentation de l'objet est d'abord rendue inaccessible par un indicateur de destruction, mais la recherche des descripteurs n'est pas effectuée : la destruction n'est que partielle. Un compte, entretenu en permanence, est associé à la représentation de l'objet ; il indique le nombre de descripteurs qui la repèrent. L'objet n'est détruit complètement que lorsque ce compte redevient nul.

En ce qui concerne l'allocation des ressources, le support de la représentation peut être réutilisé dès que l'indicateur de destruction est présent. Par contre le nom unique ne peut l'être que lorsque le compte est nul.

Cette méthode impose de comptabiliser toute création, copie ou destruction de descripteur. Aussi la destruction d'une D-liste entraine des modifications de comptes par suite de la destruction des descripteurs qu'elle contient.

## Destruction d'un objet de type construit

La destruction d'un objet construit ne peut relever du noyau car son algorithme dépend de l'algorithme de création de l'objet. La destruction des objets d'un type construit doit être définie en même temps que les autres opérations de ce type.

Si la destruction d'un objet de type construit conduit à la destruction de sa représentation (indicateur de destruction présent), tous les objets qui partagent cette représentation sont également détruits. De ce point de vue, un système bien formé est construit de telle sorte qu'on évite de détruire un objet avant de détruire tout objet construit à partir de celui-ci. Ceci implique que l'on s'interdise la coexistence de descripteurs d'objets de types différents et de nom unique commun (donc de même représentation) dans d'autres environnements que ceux où ces objets sont composés ou décomposés.

## 5.2. DESTRUCTION D'UN TYPE

### Problèmes posés par la destruction d'un type

La destruction d'un type consiste à interdire définitivement toute opération sur les objets de ce type : ces objets, de même que les procédures de définition des opérations de ce type peuvent donc être détruits
puisqu'ils sont inutilisables.

Nous ne considérons pas ici les types primitifs. On rappelle que les opérations définies sur le type T font intervenir les primitives composer et décomposer et des transitions amont pour le type T. Ces opérations cessent d'être possibles lorsque les transitions amont pour le type T ont été détruites.

Dès qu'un type T a été détruit, les opérations définies sur les types construits à partir de T cessent d'être exécutables car elles utilisent les opérations du type T ; ces types doivent donc, à leur tour être détruits.

Il en est ainsi lorsque toutes les transitions aval pour le type T ont été détruites. Ainsi, la destruction d'un type T entraine de proche en proche la destruction des types qui sont en aval de T, de sorte qu'il n'est plus possible d'obtenir par décompositions successives un objet de type T.

**Remarques**

1. Un type primitif ne peut être détruit car sa destruction impliquerait celle de tous les types construits.

2. Un système sera bien formé s'il est construit de sorte qu'il ne soit pas possible de détruire les types qui sont à la base de sa construction autrement que lors de la destruction de ce système.

3. Lors des contrôles d'arguments, des transitions sont utilisées ; elles doivent être détruites également.

## Définitions

Nous dirons qu'un type est *complètement détruit* si sa marque n'apparaît plus dans aucun descripteur. C'est-à-dire si :

a. aucun objet de ce type ne peut plus être obtenu par composition ou décomposition d'un objet d'un autre type,

b. les opérations fortes pour ce type ne sont plus définies,

c. tous les objets du type sont complètement détruits.

En d'autres termes, la destruction d'un type est complète quand les transitions (amont et aval) pour ce type ainsi que ses objets sont complètement détruits.

La destruction d'un type est réalisée par une opération du noyau. Le droit de détruire un type est fourni lors de l'allocation de la marque de type, il apparaît dans un objet de transition amont pour ce type.

## Destruction d'un type

La destruction d'un type nécessite la recherche et la destruction de tous les objets qui contiennent sa marque. De même que pour la destruction des objets nous procédons en deux étapes. Lorsque la destruction d'un type
construit est demandée par un agent, l'utilisation de sa marque est d'abord interdite par un indicateur de destruction. Chaque fois qu'une transition doit être utilisée, les indicateurs de destruction des types mis en jeu sont consultés ; si l'un des indicateurs est présent, l'utilisation de la transition est refusée. Un compte est entretenu en permanence pour chaque type construit ; il indique le nombre de descriptrieurs qui contiennent sa marque. La destruction d'un type n'est complète que lorsque ce compte devient nul.

# 6. LE NOYAU DE PROTECTION

## 6.1. QUELQUES FONCTIONS DU NOYAU

Le noyau constitue la partie centrale du mécanisme de protection. C'est lui qui gère les noms uniques des objets, et les marques de type. Il en résulte que :

- toute création et destruction d'objet primitif de type Segment, D-liste, Domaine, est assurée par le noyau,

- toute création et destruction d'un type construit est également assurée par le noyau.

Il est implanté dans un (ou plusieurs) domaine particulier, plus privilégié que les autres dans la mesure où :

1. Il forme des objets de type D-liste à partir d'objets de type Segment ; à cet effet, il possède dans son environnement une transition qui lui permet de composer (ou de décomposer) des D-listes à partir de (ou en) segments.

2. Il forme des objets de type Domaine, à partir de D-listes qui lui sont passées en arguments ; pour cela, il possède une transition (D-liste) $\succcurlyeq$ (Domaine).

En plus de ces fonctions de création et de destruction d'objets primitifs, il réalise les opérations définies sur les types Segment et D-liste, et qui n'existent pas dans le câblé, telles que : modifier-taille d'un segment ou d'une D-liste.

A la création d'un segment ou d'une D-liste, il délivre, comme résultat au domaine appelant, un descripteur ayant les attributs de l'objet créé, et tous les droits d'accès correspondants.

La création d'un nouveau type $T^j$ se fait toujours à partir d'un type $T^i$ déjà créé (c'est-à-dire $i < j$). A l'appel de l'opération allouer-marque le noyau fournit alors, comme résultat au domaine appelant, une transition $(T^i, d^i) \succcurlyeq (T^j, d^j)$.
## 6.2. APPEL DU NOYAU

Pour simplifier la présentation, nous supposons ici que le noyau est implanté dans un seul domaine. Les multiples points d'entrée de ce domaine correspondent aux différentes fonctions assurées par le noyau (création et destruction d'objets primitifs, création et destruction de types).

L'appel du noyau, par un domaine quelconque, à une entrée donnée est possible, si le descripteur de type Domaine qui conduit au noyau figure dans le contexte du processus, avec le guichet correspondant à l'entrée souhaitée.

La passation d'arguments entre le noyau et les domaines appelants est régie par le mécanisme général d'appel et de retour de domaine. Le contrôle des arguments fournis au noyau, obéit également au schéma général. **Remarque.** La protection du noyau est assurée si aucun autre domaine ne possède :

- de transition (D-liste) $\rightarrow$ (Domaine) avec le droit de décomposer,

- de transition, (Segment)$\rightarrow$(D-liste) avec le droit de composer.

Nous reportons à une étude ultérieure, l'initialisation du noyau proprement dit.

## 6.3. MECANISMES MIS EN JEU

La gestion des noms uniques et des marques de types est assurée par le noyau, au moyen de deux tables : la table des noms uniques et la table des marques.

Le nom unique qui figure dans un descripteur d'objet est utilisé comme entrée dans la table des noms uniques. Chaque entrée de cette table constitue en fait la partie fixe commune aux différents descripteurs repérant la même représentation ; elle est appelée _qualification_ de la représentation et contient entre autres :

- l'adresse physique (en mémoire centrale ou sur disque) de la représentation de l'objet,

- la longueur L (en nombre de mots) de cette représentation,

- l'indicateur de destruction de la représentation,

- le compte de descripteurs repérant cette représentation.

La marque de type qui figure dans le descripteur de l'objet est utilisée comme entrée dans la table des marques. Chaque entrée contient :

- l'indicateur de destruction de type,

- le compte des descripteurs d'objets (y compris les transitions) qui contiennent cette marque de type.
On rappelle que les comptes de descripteurs qui contiennent un même nom unique ou une même marque de type, sont mis à jour (incrémentés ou décrémentés) par les opérations câblées de copie de descripteurs.

# 7. EXEMPLES

## 7.1. REALISATION DE PRIMITIVES DE SYNCHRONISATION

Pour illustrer les mécanismes précédents, nous allons décrire la réalisation d'un jeu de primitives de synchronisation P, V, créer, détruire, agissant sur des sémaphores. On s'impose comme contraintes de les réaliser en deux niveaux, l'un pour gérer les files d'attente, l'autre pour préciser les conditions de synchronisation.

Nous négligeons les problèmes posés par l'indivisibilité des primitives P, V, etc... et nous étudions seulement la représentation, le contrôle et le bon emploi de l'information.

Nous supposons que les objets de type Processus ont déjà été introduits dans le système. Nous définissons les domaines :

- $D_1$ de gestion des files d'attente,

- $D_2$ qui réalise la synchronisation proprement dite,

- $D_j(j > 2)$ qui représentent les domaines utilisateurs, à partir desquels il doit être possible d'appeler, à la fois, les domaines $D_1$ et $D_2$.

Remarque. On aurait, tout aussi bien pu adopter un autre découpage en domaines, par exemple, en spécifiant que $D_1$ est le domaine de gestion des ensembles de processus ; le but de ce nouveau découpage aurait été de permettre l'introduction d'autres jeux de primitives de synchronisation, comme les primitives traitant des événements, sur le même ensemble de processus.

### a. Le domaine de gestion de files

C'est dans ce domaine que sont définis les objets de type File. Un objet de type File est un objet construit complexe, composé :

- des objets qui se trouvent dans la file,

- d'un objet segment, dans lequel est décrite la structure de la file ;

Les opérations que nous définissons sur les objets de type File sont :
enlever (file, élément)
insérer (élément, file)
détruire (file).

où élément représente un descripteur d'objet,
et file le descripteur de la file désignée.
Les objets de type File sont fournis en appelant l'opération
créer-file qui retourne comme résultat au domaine appelant D<sub>j</sub> (j ≥ 2),
un descripteur de type File.

La politique de gestion des files est implicitement connue des
opérations enlever et insérer. En outre ces opérations vérifient que
l'objet reçu en argument est bien un objet de type File.

Le domaine D<sub>j</sub> de gestion de files possède 4 points d'entrée qui correspondent aux procédures : enlever(file), insérer(file), détruire(file), créer-file.

b. Le domaine de synchronisation

C'est dans ce domaine D₂ que sont définis les objets de type Sémaphore.

Un objet de type Sémaphore est un objet construit, composé :

- d'un objet de type File, qui représente la file d'attente des processus bloqués derrrière le sémaphore,

- d'un objet de type Segment, dans lequel se trouve rangée la valeur du sémaphore.

Les opérations qui sont définies sur les objets de type sémaphore sont :

P(sem)

V(sem)

détruire(sem), où sem représente un descripteur de sémaphore.

Les objets de type Sémaphore sont fournis en résultat d'une opération
créer-sémaphore, appelée à partir du domaine D<sub>j</sub> (j > 2).

Les opérations P et V contrôlent que l'objet reçu en argument est
bien un objet de type Sémaphore.

Le domaine D<sub>2</sub> de synchronisation possède 4 points d'entrées qui correspondent aux procédures réalisant les opérations : P(semp), V(sem), détruire(sem), créer-sémaphore.

Nous supposons, que ce domaine connait le processus qui exécute
l'une des opérations P, V ou détruire.

A partir d'un objet de type Sémaphore reçu en argument à l'appel
d'une opération P ou V le domaine D<sub>2</sub> peut connaître la file d'attente
correspondante. La gestion de la file d'attente se fait par appel du
domaine D<sub>1</sub>.

Le domaine D₂ connait en outre la file des processus prêts, qui ne sont en attente d'aucun sémaphore.
### c. Les domaines utilisateurs

Les domaines utilisateurs $D_j (j > 2)$ ne connaissent que des objets de type Sémaphore. Il en ignorent la composition, en termes d'objets constituants. Ils ne peuvent les manipuler qu'en faisant appel au domaine de synchronisation $D_2$, (par l'un des guichets P, V, ou détruire).

Les domaines utilisateurs, peuvent utiliser par ailleurs le domaine de gestion des files $D_1$, pour gérer leurs propres objets.

Dans le schéma proposé, la fiabilité du domaine $D_2$ repose bien sûr sur celle du domaine $D_1$. L'utilisation par les domaines utilisateurs $D_j$ du domaine $D_1$ est possible sans pour autant compromettre le bon fonctionnement du domaine $D_2$ qui utilise, lui aussi, le domaine $D_1$.

<figure><img src="image_13.png" /><figcaption>Figure 12. Graphe des interactions possibles entre domaines</figcaption></figure>
<figure><img src="image_14.png" /><figcaption>Figure 13. Type des objets manipulés par les différents domaines</figcaption></figure>
## 7.2. "LES BIBLIOGRAPHIES"

Cet exemple est emprunté à [Wulf]. Il montre comment un sous-système protégé peut être bâti par un utilisateur à partir des mécanismes fournis par le système.

Nous considérons le cas d'un chercheur qui entretient une bibliographie annotée qu'il a formée comme un ensemble de fichiers associés chacun à une publication.

Pour gérer sa bibliographie, le chercheur a été conduit à mettre au point un ensemble de programmes qui permettent :

* l'impression de tout ou d'une partie de la bibliographie,

* sa mise à jour ; elle consiste à insérer une publication nouvelle ou au contraire à en supprimer une. Pour partager avec ses collègues la bibliographie qu'il a construite et l'ensemble des programmes qu'il a implantés, ce chercheur est confronté aux problèmes suivants :

1. personne d'autre que lui-même ne doit pouvoir effacer la bibliographie qu'il a établie,

2. il désire qu'il ne soit pas possible à ses collègues de copier ou modifier les programmes qu'il a mis au point,

3. il a annoté certaines publications et ne souhaite pas que celles-ci soient accessibles par tous,

4. il souhaite que sa bibliographie ne soit manipulée qu'à l'aide des programmes qu'il a écrits,

5. enfin, il est aisément imaginable que ses collègues souhaitent tout comme lui que les points 1 - 3 - 4 soient respectés à l'égard des bibliographies qu'ils créent à leur tour.

De ces remarques, il découle que :

1. les bibliographies sont des objets qui doivent être protégés et leur accès ne doit être possible qu'à l'aide des procédures mises au point par notre chercheur. Celles-ci constituent les seules opérations sur les bibliographies.

2. les procédures de manipulation des bibliographies doivent elles-mêmes être protégées : elles ne doivent être accessibles aux autres utilisateurs qu'au gré de leur créateur ; de plus ceux-ci ne doivent y avoir accès que pour les exécuter.

L'implantation d'un tel système à l'aide des mécanismes que nous avons décrits permet de respecter ces contraintes ; elle conduit à distinguer trois domaines (fig. 14) :
Domaine D<sub>j</sub> (j>2) des utilisateurs

<figure><img src="image_15.png" /><figcaption>Figure 14. Description des domaines mis en jeu dans l'exemple de la "bibliographie"</figcaption></figure>
1 - le domaine de gestion des fichiers ($D_1$)

2 - le domaine de gestion des bibliographies ($D_2$)

3 - les domaines des utilisateurs ($D_j : j > 2$).

## Le domaine de gestion des fichiers

Un fichier est défini comme un objet construit simple obtenu par composition d'un segment et sur lequel sont possibles les opérations suivantes :

* créer fichier : CF

* détruire fichier : DF

* ouvrir fichier : OF

* fermer fichier : FF

* lire article : LA

* écrire article : EA

Ces opérations sont regroupées dans le domaine $D_1$ et ne sont accessibles qu'aux utilisateurs qui en possèdent les guichets. Chacune d'elles met en jeu une transition à l'aide de laquelle elle assure le contrôle des objets qu'elle reçoit et les décompose en segments.

## Le domaine des bibliographies ($D_2$)

Afin de permettre à tout créateur d'une bibliographie de la protéger de l'action des autres utilisateurs, il importe de créer un nouveau type, le type Bibliographie défini par les opérations possibles sur les objets de ce type :

* création : CB

* destruction : DB

* mise à jour : MJB

* impression : IB

* impression sans annotations : ISAP.

Une bibliographie est un objet composé, décrit à l'aide d'une D-liste des fichiers qui sont supports des publications dont elle est le répertoire. Les opérations possibles sur ces objets reçoivent des objets de type Bibliographie qu'elles transforment en D-liste afin d'avoir accès aux composants à l'aide des opérations définies sur les fichiers.

L'accès aux fichiers d'une bibliographie n'est possible que dans les domaines qui possèdent la transition adéquate. Si le créateur du type Bibliographie ne transmet pas les transitions qu'il a obtenues du noyau, l'accès aux bibliographies n'est possible aux autres utilisateurs qu'à l'aide des opérations qu'il a mises à leur disposition.

Par ailleurs l'intégrité de ces opérations est assurée si
celles-ci sont regroupées dans un domaine ($D_2$), car elles ne sont alors accessibles qu'à travers un guichet qui garantit qu'elles ne peuvent être qu'exécutées.

### Les domaines des utilisateurs ($D_j, j > 2$)

Pour qu'un utilisateur puisse accéder à une bibliographie, quatre conditions doivent être réunies, il doit :

* connaître l'objet, ce qui se traduit par la possession par cet utilisateur d'un descripteur de l'objet,

* connaître le domaine $D_2$,

* avoir le guichet de l'opération qu'il demande,

* avoir le droit d'exécuter cette opération sur la bibliographie.

Chaque utilisateur de ce système peut donc ainsi assurer une protection sélective des bibliographies qu'il crée. De même que le créateur du type Bibliographie peut assurer un partage sélectif des opérations qu'il a mises au point, en ne fournissant qu'un nombre limité de guichets aux autres utilisateurs.

### Remerciements.

Nous tenons à remercier J. Boulenger pour les nombreuses discussions que nous avons eues avec lui, au commencement de cette étude.
# ANNEXE

Nous décrivons en pseudo Algol 68 les algorithmes des opérations définies sur le type transition (opérations de transition), des opérations définies sur le type domaine (appel et retour) et des opérations sur les D-listes. Dans ces algorithmes nous considérons qu'une D-liste est un tableau de structures :

```
mode D-liste = [1:] struct (int type, [1:k] bool droit,
                          union (int, struct (
                            int type amont, [1:k] bool droit amont, int type aval, [1:k] bool
                            droit aval)) ref) ; co k est supposé connu co
```

[1:k] D-liste env ; co env est la D-liste d'environnement du domaine courant co

## 1 - opérations de transition

a - procédures utilisées dans la description des opérations de transition :

- erreur (i) : co c'est l'appel de la procédure de traitement des erreurs de type i co

- tester type (i,j) : co cette opération permet de vérifier que l'objet de nom i porte la marque j co

```
if (type of env (i) = j) then erreur (type j) fi ;
```

- tester droits (i,j) : co cette procédure vérifie que les droits j sont inclus dans les droits associés à l'objet i co

```
if (j c droit of env (i)) then erreur (droits requis) fi
```

- tester transition (i) : co cette procédure permet de tester les indicateurs de destruction des types aval et amont de la transition de nom i co

```
begin if (type amont of ref of env (i) = détruit) then
    erreur (type amont détruit) fi ;
```

```
if (type aval of ref of env (i) = détruit) then
    erreur (type aval détruit) fi
```

end

b - opérations de transition :

- composer (e, t, n) : co e est le nom local de l'objet à composer, t celui de la transition à utiliser, n est le nom de l'emplacement dans lequel doit être rangé le descripteur de l'objet composé co
```
begin int m, [1 : k] bool d;
tester-type (t, transition) ;
tester-transition (t) ;
m := type amont of ref of env (t) ;
tester-type (e, m) ;
d := droit amont of ref of env (t) ;
tester-droits (e, d) ;
env (n) := (m, d, ref of env (e))
```

end

- décomposer (u, t, e) : co n est le nom local de l'objet à décomposer et t celui de la transition à utiliser. e est le nom de l'emplacement où doit être rangé le descripteur obtenu par décomposition co

```
begin int m, [1 : n] bool d;
tester-type (t, transition) ;
tester-transition (t) ;
m := type aval of ref of env (t) ;
tester-type (n, m) ;
d := droit aval of ref of env (t) ;
tester-droits (r, d) ;
env (e) := (m, d, ref of env (n))
```

end

- contrôler (t, p) : co t est le nom de la transition utilisée, p est celui de l'objet à contrôler co

```
begin int m, [1 : n] bool d;
tester-type (t, transition) ;
tester-transition (t) ;
m := type aval of ref of env (t) ;
tester-type (p, m) ;
d := droit aval of ref of env (t) ;
tester-droits (p, d)
```

end
## 2 - opérations d'appel et de retour de domaine

a - procédures utilisées dans la description des opérations appel et retour :

- tester objet (i) : vérifie que l'objet de nom i n'est pas détruit ;

- capter (d₁, i d₂) : range dans l'emplacement de nom d₂ le descripteur i de la D-liste de nom d₁ ;

- ranger (d₁, d₂, i) : range le descripteur d₁ dans l'emplacement i de la D-liste de nom d₂ ;

- sauver : range le contexte courant dans la pile ;

- former (d₁, d₂, i) : établit le contexte formé du descripteur d₁ de l'environnement, du descripteur d₂ d'un segment exécutable et du déplacement i dans ce segment ;

- rappeler : rétablit le contexte qui est rangé en tête de pile et modifie le pointeur de tête en conséquence ;

b - Appel et retour de domaine :

- appel (d, g, p) :

```
begin struct (int champ 1, [1 : k] bool champ 2, int champ 3) e, s ;
    co e et s sont des registres de travail. d est le nom local du
domaine appelé et p celui du paramètre à transmettre. g est le
nom du guichet invoqué dans le domaine appelé co
tester-type (d, domaine) ;
tester-objet (d) ;
if (droit (g) of env (d)) then erreur (droits) fi ;
capter (d, g, s) ;
tester-type (s, segment) ;
if (champ 2 of s = exécutable) then erreur (droit) fi ;
sauver ;
capter (d, i, e) ;
former (e, s, o) ;
ranger (p, e, i) ;
co il s'agit de la transmission des paramètres co
end
```
- retour

```
begin struct (int champ 1, [1 : k] bool champ 2, int champ 3) e, f ;
    co e désigne le registre pointeur d'environnement, f est un
    registre de travail co
f := (o, o, o) ;
ranger (f, e, i) ;
co ou romp ainsi le lien des paramètres dans l'environnement
courant co
rappeler
end
```

### 3 - Opérations sur les D-listes

- lire-descripteur ($d_1$, $i$, $d_2$) : **co** cette opération range dans l'emplacement de nom $d_2$ le descripteur de nom $i$ de la D-liste repérée par $d_1$. Pour que l'opération soit effective la lecture de la D-liste de nom $d_1$ doit être permise **co**

```
begin tester-type ($d_1$, D-liste) ;
tester-droits ($d_1$, lire) ;
capter ($d_1$, $i$, $d_2$)
end
```

- écrire-descripteur ($d_1$, $d_2$, $i$) : **co** cette opération range le descripteur de nom $d_1$ dans l'emplacement $i$ de la D-liste de nom $d_2$. Elle n'est effective que si la D-liste de nom $d_2$ peut être écrite **co**

```
begin tester-type ($d_2$, D-liste) ;
tester-droits ($d_2$, Ecrire) ;
ranger ($d_1$, $d_2$, $i$) ;
end
```

- copier ($d_1$, $d_2$, $i_1$, $i_2$, $r$) : **co** cette opération est toujours permise, elle réalise la copie du descripteur de nom $d_1$ dans l'emplacement $d_2$ de la D-liste d'environnement. $i_1$ et $i_2$ sont des indicateurs booléens d'utilisation des masques contenus dans le registre de donnée. La présence de $i_2$ suppose que $d_1$ contienne une transition et concerne le champ droit aval de ce descripteur. **co**

```
begin type of env ($d_2$) := type of env ($d_1$) ;
    for j to k do
        droit (j) of env ($d_2$) := droit (j) of env ($d_1$)^(i_1|r(j)|1) ;
        ref of env ($d_2$) := ref of env ($d_1$) ;
        if (type of env ($d_1$) = transition) then for j to k do
            droit aval (j) of ref of env($d_2$) := droit aval of ref of env ($d_1$) ^ (i_2|r(j + k)|1) fi
```
[Boulenger]
J. Boulenger, M. Kronental
Aspects de la notion de type
Rapport Laboria, (1974).

[Crocus]
Groupe de travail "Crocus"
Systèmes d'exploitation des ordinateurs - Principes
de conception - (chapitre 5)
Editions Dunod, coll. Université - à paraître (octobre 1974).

[Dennis]
J.B. Dennis, E. Van Horn
Programming semantics for multiprogrammed computations
Comm. ACM 9,3 (march 1966) p. 143-155.

[England]
D.M. England
Capability concept mechanism and structure in system 250
proc. international workshop on protection in operating
systems.
IRIA (August 1974), p. 63-82.

[Gray]
J. Gray, B. Lampson, B. Lindsay, H. Sturgis
The control structure of an operating system
IBM Research RC 3949 (july 1972).

[Lampson]
B.W. Lampson
Protection
Proc. Fifth Annual Princeton Conference on Information
Sciences and Systems
Princeton University (march 1971), p. 437-443.

[Lindsay]
B. Lindsay
Suggestions for an extensible capability based-machine
architecture
International workshop on computer architecture,
Grenoble (juin 1973).

[Morris]
J.H. Morris
Protection in programming languages
Comm. ACM 16,1 (january 1973), p. 15-21.
[Wulf]
W. Wulf, E. Cohen, W. Corwin, A. Jones, R. Levin, C. Pierson, F. Pollack
Hydra : the kernel of a multiprocessor operating system
Comm. ACM 17,6 (june 1974), p. 337-344.