Post on 01-May-2015
transcript
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
Buranello-Cafeo XML Access Control Using Static Analysis 3
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
Buranello-Cafeo XML Access Control Using Static Analysis 4
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
Buranello-Cafeo XML Access Control Using Static Analysis 5
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
Buranello-Cafeo XML Access Control Using Static Analysis 6
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
Buranello-Cafeo XML Access Control Using Static Analysis 7
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
Buranello-Cafeo XML Access Control Using Static Analysis 8
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
Buranello-Cafeo XML Access Control Using Static Analysis 9
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
Buranello-Cafeo XML Access Control Using Static Analysis 10
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:
Buranello-Cafeo XML Access Control Using Static Analysis 11
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
Buranello-Cafeo XML Access Control Using Static Analysis 12
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
Buranello-Cafeo XML Access Control Using Static Analysis 13
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
Buranello-Cafeo XML Access Control Using Static Analysis 14
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
Buranello-Cafeo XML Access Control Using Static Analysis 15
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
Buranello-Cafeo XML Access Control Using Static Analysis 16
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
Buranello-Cafeo XML Access Control Using Static Analysis 17
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
Buranello-Cafeo XML Access Control Using Static Analysis 18
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.
Buranello-Cafeo XML Access Control Using Static Analysis 19
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
Buranello-Cafeo XML Access Control Using Static Analysis 20
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
Buranello-Cafeo XML Access Control Using Static Analysis 21
Esempio
Schema automata
Paths permessi
Buranello-Cafeo XML Access Control Using Static Analysis 22
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
Buranello-Cafeo XML Access Control Using Static Analysis 23
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Γ
Buranello-Cafeo XML Access Control Using Static Analysis 24
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
Buranello-Cafeo XML Access Control Using Static Analysis 25
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
Buranello-Cafeo XML Access Control Using Static Analysis 26
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
Buranello-Cafeo XML Access Control Using Static Analysis 27
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
Buranello-Cafeo XML Access Control Using Static Analysis 28
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
Buranello-Cafeo XML Access Control Using Static Analysis 29
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
Buranello-Cafeo XML Access Control Using Static Analysis 30
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.
Buranello-Cafeo XML Access Control Using Static Analysis 31
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
Buranello-Cafeo XML Access Control Using Static Analysis 32
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
Buranello-Cafeo XML Access Control Using Static Analysis 34
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
Buranello-Cafeo XML Access Control Using Static Analysis 35
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
Buranello-Cafeo XML Access Control Using Static Analysis 36
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)
Buranello-Cafeo XML Access Control Using Static Analysis 37
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
Buranello-Cafeo XML Access Control Using Static Analysis 38
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
Buranello-Cafeo XML Access Control Using Static Analysis 39
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