Buranello-Cafeo XML Access Control Using Static Analysis1 Analisi Verifica Programmi 2004/05 Alberto...

Buranello-Cafeo XML Access Control Using Static Analysis

1

XML Access Control Using Static Analysis

Analisi Verifica Programmi 2004/05

Alberto Buranello 802691Fabio Cafeo 801733

Buranello-Cafeo XML Access Control Using Static Analysis 2

Introduzione

XML è un linguaggio che negli ultimi anni ha suscitato interesse negli ambienti di ricerca del W3C

L’obiettivo più interessante è quello di utilizzare un documento XML come un vero e proprio database. Si rende quindi necessaria una adeguata politica di controllo degli accessi Esistono già dei linguaggi come XPath e XQuery il

cui scopo è quello di interrogare correttamente file XML


Controllo degli accessi I documenti XML devono essere efficienti ed espressivi:

Facili per scrivere politiche di controllo degli accessi Garantiscono o negano l’accesso ad un elemento o ad un

attributo Entrambi questi requisiti appartengono ai database relazionali

I documenti XML hanno la possibilità di gestire un numero infinito di path, quindi non esiste upper bound sull’altezza dell’albero degli elementi del documento

Questo requisito è supportato da XPath Se gli elementi o attributi nei documenti XML sono caricati a

run-time provocano un grosso problema nella gestione dei permessi d’accesso. Infatti, si corre il rischio di avere prestazioni inaccettabili

L’analisi statica esamina questa politica a tempo di compilazione, cioè:

Quando una query è creata piuttosto che quando è eseguita Nel caso il database venga aggiornato frequentemente sarà

comunque necessaria la verifica a run-time


Analisi Statica Si compone di due fasi:

1. Creiamo degli automi, da cui si possono ricostruire i paths agli elementi o attributi, seguendo quest’ordine: Query automata: automa creato dalle queries Access control automata: si genera un automa che

rappresenta le politiche di controllo degli accessi Schema automata: un terzo automa viene generato

dagli schemi 2. Si confrontano questi automi applicando le seguenti

regole in ordine: se l’intersezione tra query automata e schema

automata è inclusa nell’ access control automata, gli accessi attraverso le queries sono always-granted

se l’intersezione tra i tre automi è vuota, gli accessi attraverso le queries sono always-denied

Altrimenti sono statically indeterminate


Documenti XML Sono formati da elementi,

attributi e nodi testuali. L’insieme di queste entità forma un albero

Il contenuto di ciascun elemento è una sequenza di elementi o nodi testuali.

Un elemento possiede un insieme di attributi, che hanno un nome e un valore

ΣE ≡ Insieme dei tag nome ΣA ≡ Insieme dei tag attributo @ Sarà preposto ai simboli che si

riferiscono a ΣA

Esempio documento XML


Schema Uno schema è una descrizione di documenti XML

consentiti Esistono schema languages che permettono la scrittura

degli schemi DTD, W3C XML Schema, RELAX NG

Uno schema è una quintupla G=(N, ΣE, ΣA,S,P) N = insieme finito di non terminali S = è un sottoinsieme di ΣE x N P = è un insieme di produzioni X→r A, X N, r è

un’espressione regolare su ΣE x N, A ΣA L’insieme delle regole di produzioni specifica le

strutture degli elementi consentiti. Lo schema può essere ricorsivo all’infinito se non si

impone alcun upper bound sull’altezza del documento


Esempio di schema

Si separano i non terminali (N) dai nomi elemento (ΣE), poichè si permette agli elementi con nome uguale, di avere differenti percorsi subordinati

W3C XML Schema e RELAX NG richiedono questa separazione


XPath XPath da una espressione regolare permette di

interrogare un documento Ad esempio, //foo[@bar = “abc”]

Si trovano gli elementi foo in cui l’attributo bar è uguale alla stringa data

Dove [@bar=“abc”] è predicato (condizione aggiuntiva). Utilizza gli axes per rappresentare le dipendenze

strutturali tra i nodi. XPath fornisce molti tipi di axes, ne considereremo solo tre: Descendant-or-self // Child / Attribute @

Permette alle condizioni su un elemento di avere ulteriori restrizioni


XQuery XQuery è un altro linguaggio, per l’XML, per interrogare un database

e usa l’XPath per individuare gli elementi o attributi L’XQuery ha dei comandi che associano uno o più variabili con

espressioni di XPath. La valutazione delle espressioni XPath crea delle ennuple

Si possono imporre condizioni aggiuntive alle ennuple. Le ennuple che non soddisfano le condizioni vengono scartate; le rimanenti vengono valutate e si ritorna un valore od una sequenza di valori

Comandi più importanti : FOR, LET, WHERE e RETURN

crea una lista sulle coppie patologia-commento per il cancro-gastrico


Sintassi della politica dei controlli degli accessi

La politica dei controlli degli accessi è un insieme di regole per verificare gli accessi

Ciascuna regola consiste : object (nodo target) viene usata un’espressione XPath subject (utente o processo user) è specificato da un

UserID. Ha un prefisso che indica il tipo di soggetto: + accesso garantito — accesso negato

action indica l’azione da intraprendere: read, update, delete e create Si approfondirà solo l’action read, poiché attualmente

l’XQuery non supporta altre azioni permission (garantito o negato) che significa il subject ha

il permesso di compiere l’action sull’object Si utilizza la seguente sintassi per la nostra politica di

controllo degli accessi:


Esempio Definiamo qui tre regole per il controllo degli accessi:

Ogni regola è caratterizzata da un ruolo (Role) del soggetto richiedente

Ad esempio, la seconda regola può essere letta così: Intern può leggere gli elementi /record

Documento XML

Regole


Uso di XPath per il controllo degli accessi

XPath fornisce un numero sufficiente di modi per riferirsi alle unità più piccole di una struttura di un documento (elemento, attributo, nodo testo, nodo elemento)

Permette una scrittura di politica flessibile Ad esempio, garantisce l’accesso ad un elemento, ma lo nega agli

attributi dell’elemento stesso Spesso accade che l’accesso ad un certo nodo è determinato da

un valore nel documento target Ad esempio, per un record medico, un paziente può leggere il

proprio record, ma non quello di un altro pazienteRole: Patient

+R,/record[@patientId = $userid3]/diagnosis)

Una politica dei controlli degli accessi fornisce un modo per rappresentare una restrizione necessaria sul record

Si usa il termine value-based access control per riferirsi ad una politica in cui vengono usati predicati per le restrizioni aggiuntive


Semantica della politica dei controlli degli accessi (1)

Requisiti: Brevità: specifica la regola generale piuttosto che le

regole su ogni singolo nodo Privilegi più piccoli: garantisce il minimo privilegio al

soggetto richiedente Correttezza: fornisce il permesso o la negazione ad

ogni richiesta d’accesso Consistenza della negazione ai discendenti: quando

un elemento è negato bisogna negare gli elementi e attributi subordinati

In altre parole quando è permesso l’accesso ad un nodo deve essere permesso l’accesso a tutti gli elementi predecessori


Semantica della politica dei controlli degli accessi (2)

Definizione dei requisiti:1. Una regola propaga i permessi ai discendenti della struttura del

documento XML con +R o –R. Viceversa se la regola è con +r o –r vale solo sul nodo specificato

2. Una regola che nega il permesso al nodo prevale su qualsiasi altra che ne permette l’accesso

3. Se non è applicata alcuna regola al nodo, per default si applica la negazione del permesso a quel nodo (“-”)

Algoritmo per la generazione dei permessi d’accesso:1. L’algoritmo raccoglie ogni regola di permesso con +r e segna con il

simbolo “+” il nodo target riferito all’espressione dell’XPath. Se il nodo è di tipo elemento l’algoritmo segna “+” su tutti i nodi figli (nodi testo e commento) eccetto per gli elementi e attributi. Segna con “+” tutti i nodi discendenti se l’azione è R

2. L’algoritmo raccoglie le regole di negazione e segna con “–” il nodo target allo stesso modo. Quindi il simbolo “-” sovrascrive gli eventuali segni “+”

3. L’algoritmo segna con “-” tutti i nodi che non sono marcati Queste operazioni sono eseguite per ogni soggetto ed azione

indipendentemente Questo algoritmo non soddisfa sempre il requisito di “Consistenza della

negazione ai discendenti”. Ad esempio, se una regola con +R è specificata su un certo nodo, su un nodo predecessore è specificato –R, la negazione degli accessi revoca il permesso di accesso della politica di scrittura


Esempi <record>

<diagnosis><pathology type="Gastric

Cancer">Well differentiated adeno carcinoma

</pathology><comment>This seems

correct</comment></diagnosis>

</record>

Role: Intern+R, /record-R, //comment

La prima regola segna con “+” l’intero albero

La seconda regola marca gli elementi comment e i nodi testo subordinati con “-”, sovrascrivendo i “+” scritti precedentemente

Gli elementi comment sono determinati come “accesso negato”

• Una regola che utilizza +R o –R può essere riscritta con l’uso di +r o –r

• (Sbj, +R, /a) è semanticamente equivalente a:

(Sbj, +r, /a) (Sbj, +r, /a//*) (Sbj, +r, /a//@*)

• L’uso di +R o –R permette la scrittura di una politica in maniera più concisa


Controllo degli accessi a run-time

In un documento XML, se esistono nodi con accesso negato l’analizzatore di query si comporta come se non esistessero nel documento

Scenario: Quando è richiesto l’accesso ad un nodo e ai suoi

discendenti, il controllore dopo aver recuperato le politiche di accesso, decide se permettere o meno l’accesso a ciascun nodo

Una semplice implementazione di questo scenario può portare a scarse performance perché si ripetono le valutazioni per ciascun nodo


Analisi Statica

Passo 1: creazione dello schema automata dagli schemi

Passo 2: creazione di access control automata dalle politiche di controllo degli accessi

Passo 3: creazione di query automata dalle query XQuery

Passo 4: confronto fra gli schemi ottenuti nei passi precedenti


Automi non-deterministici a stati finiti

Un automa M è definito con una quintupla (Ω, Q, Qinit , Qfin, δ) Ω è l’alfabeto Q è un insieme finito di stati Qinit è sottoinsieme di Q (stati iniziali) Qfin è sottoinsieme di Q (stati finali) δ è una funzione di transizione da Q x Ω a Q

L(M) è l’insieme delle stringhe accettate da M Gli automi si utilizzano per catturare le

espressioni XPath.


Espressioni XPath Inizialmente si crea una espressione regolare rimpiazzando

“/” e “//” rispettivamente con “∙” e “∙Ω*∙” dove “∙” denota la concatenazione di due insiemi regolari Poi, a partire dall’espressione regolare si crea l’automa

L’automa così costruito accetta un path sse combacia con l’espressione XPath

Se un’espressione XPath “r” contiene predicati, non si può catturarne le semantiche con gli automi. Perciò si costruisce la sovrastima (over-estimation automata) e la sottostima (under-estimation automata) M[r]

Per costruire la sovrastima si assume che i predicati siano sempre soddisfatti, in altre parole, i predicati di r vengono tutti usati per costruire l’automa che accetterà anche cammini parziali

Per costruire la sottostima si assume che i predicati non siano mai soddisfatti, in altre parole, M[r] è sempre l’insieme vuoto

][rM


Passo 1: Creazione dello schema automata

Si considerano solo i paths permessi Definizione dello schema:

),,,,,(

),,,,(

fininifininiAEG

AE

qNqqqNM

PSNG

Dove MG è l’automa dello schema G, δ è una funzione di transizione, tale che

AE

ini

ae

rxax

xeqxxxerxxx

,

|

]'[,|']'[|'

con

P in q a) ,(

S r in occorrenzaun' è P, in e) ,(fin


Esempio

Schema automata

Paths permessi


Passo 2: Creazione di access control automata

La politica di controllo degli accessi consiste in una serie di regole

In questo passo, per ogni soggetto richiedente, vengono creati una coppia di automi: over-estimation access control under-estimation access control

Questa coppia cattura tutti quei paths (ad elementi od attributi) che sono rappresentati nella politica di controllo degli accessi

Inizialmente si sostituiscono +R, –R con +r, –r su tutti i nodi. Così le regole sono meno sintetiche e si ottengono tutti i possibili paths agli elementi r1, ..., rm indicano i permessi di accesso r’1, ..., r’m indicano le negazioni di accesso


Passo 2: Creazione di access control automata (2)

Se r1, ..., rm e r’1, ..., r’m non contengono predicati (possibili condizioni) Il principio adottato è che “l’accesso negato ha la

precedenza” Dato Γ schema, MΓ accetta i path di r ma non quelli negati da

r’

Esempio nel caso del Role Intern visto in precedenza

Altrimenti creiamo una sovrastima e una sottostima di MΓ


Passo 3: Creazione di query automata

Da un’espressione XQuery, si estraggono le espressioni XPath

Si distingue tra il comando RETURN e i comandi FOR,LET e WHERE

Il primo ritorna i sottoalberi che includono gli elementi ed attributi subordinati

I secondi esaminano gli elementi o attributi ma non i loro elementi subordinati

Si crea il query automata Mr per ciascuna espressione r estratta dall’XPath

Se r è presente in una clausola FOR-LET-WHERE di XQuery, definiamo per preservare da errori l’analisi statica

Se r ricorre in una clausola RETURN, Mr è un automa che accetta path sse qualche sotto-path si combina con r

Di conseguenza

][rMM r


Esempio (Passo 3)<record>

<diagnosis><pathology type="Gastric Cancer">

Well differentiated adeno carcinoma

</pathology><comment>This seems

correct</comment></diagnosis><chemotherapy>

<prescription>5-FU 500mg</prescription>

<comment>Is this sufficient?</comment></chemotherapy><comment>How was the operation?</comment>

</record

Dato r come/record//comment che è l’ultima espressione XPath che ricorre nella clausola return

Allora Mr accetta :/record/comment/record/comment/@type/record/comment/record/record/comment/diagnosis,……………

<TreatmentAnalysis>for $r in document("medical_record")/recordwhere $r/diagnosis/pathology/@type= "Gastric Cancer"return $r/diagnosis/pathology, $r//comment

</TreatmentAnalysis>

XQuery


Passo 4: Confronto fra automi Se non contiene predicati, l’espressione r è sempre garantita

se tutti i path sono accettati da Mr e MG , formalmente:

Se gli schemi non sono disponibili, si assume MG permetta tutti i paths e si controlla che

L’espressione r è sempre negata se nessun path è accettato da tutti gli automi, formalmente:

Quando gli schemi non sono disponibili, si controlla se:

Il path r è staticamente indeterminato se non è sempre garantito nè sempre negato


Passo 4 con i predicati

Quando ci sono i predicati si usano sottostime e sovrastime

Usiamo una sottostima MΓ se una query è sempre garantita o meno

Allo stesso modo si usa una sovrastima per determinare se un path è sempre negato

M


Ottimizzazione di query Se un’espressione XPath r è sempre negata da un’altra

espressione XQuery, è possibile rimpiazzare r con una lista vuota. Questa riscrittura rende non necessario un run-time checking nella politica di controllo degli accessi

<TreatmentAnalysis>for $r in document("medical_record")/recordwhere $r/diagnosis/pathology/@type= "Gastric Cancer"return$r/diagnosis/pathology, $r//comment</TreatmentAnalysis>

<TreatmentAnalysis>for $r in document("medical_record")/recordwhere $r/diagnosis/pathology/@type="Gastric Cancer"return$r/diagnosis/pathology</TreatmentAnalysis>

• L’analisi statica per il ruolo Doctor ci dice che l’accesso è sempre garantito dall’espressione XPath, rendendo quindi non necessario il run-time checking

• Per il ruolo Intern, l’analisi statica ci avverte che l’ultima espressione XPath è sempre negata

QUERY

ottimizzazione


Esempio su un caso reale (1) Mostriamo ora di quanto

l’analisi statica migliori le prestazioni, utilizzando un esempio proposto dall’XMark project

Lo scenario è quello di una casa d’aste, in cui sono disponibili 20 query di esempio

È disponibile anche una DTD in cui vi sono 77 tipi elemento

Si scrive una politica d’accesso riferita a 9 ruoli

Ciascun role ha associato da 1 a 15 regole di controllo degli accessi

Role name

Significato

1 M Amministratore

2 MM Gestore degli utenti

3 IM Gestore dei beni

4 S Venditore

5 B Compratore

6 V Visitatore

7 UBCompratore con accesso negato

alle voci esterne

8 USVenditore con accesso negato

alle voci esterne

9 UVVisitatore con accesso negato

alle voci esterne

Tabella dei ruoli


Esempio su un caso reale (2)Definizione di una semplice politica degli accessi

Ad esempio, al ruolo del venditore è possibile leggere il documento root (/). Questo permesso è garantito dalla prima riga (+R) e si propaga ai discendenti.

Il compratore può leggere il contenuto della sua cartella creditcard e profile, ma non quelle di altri utenti.

Da notare che la politica è value-based, cioè i predicati XPath appaiono nelle regole.


Esempio su un caso reale (3) Costruiamo una tabella in cui, per ogni coppia query/role, si

segna se l’analisi statica rende superfluo il controllo a run-time

Eseguiamo questo esperimento su due casi:

Con DTD

Senza DTD


Legenda “G” indica che tutte le espressioni dell’XPath sono sempre permesse

La query non contiene alcuna espressione XPath che richiede un controllo degli accessi a run-time

“D” indica che almeno una delle espressioni XPath è negata La query contiene l’espressione XPath che fallirà sempre il controllo degli

accessi a run-time. In questo caso si riscriverà tale espressione come lista nulla, rendendo non necessario il controllo degli accessi a run-time

“-” indica che l’espressione XPath è staticamente indeterminata Non è possibile predire il risultato del controllo a run-time della query e

verrà, quindi, eseguito

Le due tabelle mostrano, rispettivamente: il 65% e il 40% delle coppie query/role non richiedono un controllo

dell’accesso a run-time Il 25% e il 10% di queste coppie possono essere ottimizzate dalla riscrittura

delle queries Possiamo concludere che quando non è disponibile un documento DTD,

l’analisi statica può risultare significativa per l’ottimizzazione di queries

Esempio su un caso reale (4)

33

Esempio su un caso reale (5): accesso ai nodi

No access:, la query iniziale accede a questi nodi, ma la sua riscrittura no; questi nodi sono esentati dall’accesso

Access without runtime access check: si evita il controllo degli accessi a run-time su questi nodi, i nodi vanno comunque letti

Access with runtime access check: su questi nodi è richiesto il controllo degli accessi a run-time sia sulla query originale che su quella riscritta

Il grafico mostra, per ciascun ruolo, il numero di nodi per le tre categorie

Si osserva che il costo della valutazione delle query per M, MM, IM e V è ridotto in maniera significativa, poiché i nodi del terzo gruppo sono pochi

Nel caso specifico di M si nota che non era richiesto nessun controllo degli accessi a runtime perché l’amministratore ha l’accesso a tutti i nodi


Scalabilità dell’analisi statica Nel seguente test di scalabilità, si misurerà il tempo di esecuzione

dell’analisi, su DTDs reali e con politiche casuali con insiemi grandi di regole

Fasi: Inizializzazione: dove si computa nello schema automaton MG , poi si

computa l’access control automaton MΓ per ogni ruolo della politica Analisi: si analizza staticamente l’espressione XPath per ogni query, cioè

si vuole determinare se l’accesso è sempre permesso o negato Documenti DTDs usati:

xmlspecv21.dtd (157 tipi elemento) da W3C XML Working Group HL7.dtd (621 tipi elemento) da Health Level Seven docbookx.dtd (393 tipi elemento) da OASIS DocBook technical committee

Si utilizzeranno politiche di controllo degli accessi di grandezze variabili (da 1 a 500 regole per ruolo)

Per ogni DTD, sono generate casualmente 10 politiche di controllo con l’uso di elementi attributi e elementi nome definite nella DTD stessa

Per ogni DTD, si analizza staticamente una query con 12 espressioni XPath


Test

È stato eseguito su una macchina con processore Pentium 4 2.4 GHz, con 512 MB RAM, con sistema operativo basato su Linux

Esempio di politica generata casualmente


Risultati test (1)

• La figura mostra il tempo di esecuzione per la fase di inizializzazione

• Ogni punto indica il tempo richiesto per eseguire l’access control automaton per ogni ruolo nella politica generata casualmente

• Il run-time non tiene conto del tempo per computare lo schema automata (MG)

• xmlspecv21.dtd (214), HL7.dtd (623), docbookx.dtd (501)


Risultati test (2) Questa figura mostra il tempo di esecuzione per la fase di analisi Ogni punto indica il tempo medio richiesto per l’analisi di ogni

espressione XPath della Query In entrambe le fasi, le prestazioni sono di gran lunga migliori nel caso di

HL7.dtd piuttosto che negli altri casi. Questo perché gli altri due documenti contengono molte definizioni ricorsive e perciò risultano molto più complesse rispetto al primo


Conclusioni Lo scopo di questo lavoro, è quello di alleggerire il

controllo della politica degli accessi nei documenti XML, distribuendone il peso fra l’analisi statica e i controlli a run-time

L’idea chiave è l’uso degli automi per rappresentare e confrontare: queries, politiche di controllo degli accessi e schemi

Dal prototipo precedente si nota che: L’analisi statica rende spesso superfluo il controllo a run-

time e fornisce significative ottimizzazioni Il nostro prototipo è ben bilanciato quando gli schemi, le

queries e le politiche di accesso sono molto grandi Si è sempre preso in considerazione un XQuery

semplificato, ma nei casi reali, l’XPath permette un arbitrario annidamento di espressioni FLWR ed anche query ricorsive Non è stato gestito nel nostro progetto la ricorsività delle

queries che è stata completamente lasciata al controllo run-time


Bibliografia Murata, Tozawa, Kudo, “XML Access Control

Using Static Analysis” http://monetdb.cwi.nl/xml/ Health Level Seven, http://www.h17.org OASIS DocBook technical committee,

http://www.oasis-open.org/committees/docbook

W3C XML Working Group, http://www.w3.org

Buranello-Cafeo XML Access Control Using Static Analysis1 Analisi Verifica Programmi 2004/05 Alberto...

Documents

Transcript of Buranello-Cafeo XML Access Control Using Static Analysis1 Analisi Verifica Programmi 2004/05 Alberto...