9. Dezember 2003Überprüfung der Sicherheit von Informationsflüssen in Programmen - Stefan Kurz,1 Hauptseminar Software-Sicherheit Thema Überprüfung der

9. Dezember 2003Überprüfung der Sicherheit von Informationsflüssen in Programmen - Stefan Kurz, 1

Hauptseminar

Software-Sicherheit

Thema

Überprüfung der Sicherheit vonInformationsflüssen in Programmen


Übersicht

Einführung– Sicherheitsklassen– Sicherer Informationsfluss– Expliziter und impliziter Informationsfluss

Überprüfung der Sicherheit von Informationsflüssen in Programmen– Typ-basierter Ansatz– Semantik-basierter Ansatz

• Einführung� Postdominanz und unmittelbare Postdominanz -Sicherheit

• Überprüfung der -Sicherheit mit Hilfe einer abstrakten Semantik

Zusammenfassung


Motivation

Szenario:– Programm kompiliert nach Java Bytecode (JVML), heruntergeladen über

das Internet und ausgeführt in einem Java-fähigen Browser– Benötigt zur Ausführung Zugriff auf vertrauliche Daten des Benutzers

Problem:– Sichtbarkeit der vertraulichen Daten des Benutzers z.B. über das Internet?

Überprüfung der Sicherheit der Informationsflüsse im Programm!


Einführung





Zusammenfassung


Sicherheitsklassen

Information kann man anhand von Sicherheitsstufen (z.B. low, high, usw.) klassifizieren. Bildung von Sicherheitsklassen

Objekte (z.B. Programmvariablen) können Information halten. Jedem Objekt wird eine Sicherheitsklasse zugeordnet.

– Statische Zuordnung:Die Sicherheitsklasse eines Objekts ist konstant.

– Dynamische Zuordnung:Die Sicherheitsklasse eines Objekts variiert mit der von dem Objekt gehaltenen Information.


Sicherer Informationsfluss

Die Menge SC der Sicherheitsklassen muss einen vollständigen Verband bilden. Partielle Ordnung auf der Menge SC der SicherheitsklassenBeispiel:

Sei SC = {L, M, H} die Menge der Sicherheitsklassen unclassified (L),confidential (M) und secret (H). L M H ist eine mögliche partielle Ordnung auf SC.

Sicherer Informationsfluss: Es darf keine Information von einem Objekt mit höherer Sicherheitsklasse zu einem Objekt mit niedrigerer Sicherheitsklasse fließen.Beispiel:

Sei (SC, ) wie oben.Seien x, y Programmvariablen mit Sicherheitsklassen M, L SC. Die Zuweisung x:=y ist sicher, da L M.


Expliziter und impliziter Informationsfluss

Expliziter Informationsfluss– Aufgrund von Zuweisungen– Beispiel: x:=y;

Impliziter Informationsfluss– Aufgrund von bedingten oder repetitiven Anweisungen– Beispiel: if z=0 then x:=0; else x:=1;







Zusammenfassung


Typen und Typsysteme

Ein Typ legt den Wertebereich einer Programmvariablen fest. Ein Typsystem besteht aus einer Typisierungsrelation, die jeder

Programmvariablen einen Typ zuordnet, und aus einer Menge von Typinferenzregeln der Form

mit H1,...,Hn und C in der Form

Bemerkung: Typsysteme werden gewöhnlich dazu verwendet, die Typkorrektheit von Programmen in einer streng typisierten Programmiersprache zu überprüfen.Im Folgenden wird gezeigt, wie man Typsysteme zur Überprüfung der Sicherheit von Informationsflüssen in Programmen einsetzen kann.

CHH n,...,1 Annahmen

Schlussfolgerung

:p: Typisierungsrelation: Programmanweisung: Typ

p


Typsysteme und sicherer Informationsfluss

Ein Typ entspricht einer Sicherheitsklasse aus SC. Unterscheidung zwischen Typen für Ausdrücke ( ), Typen für

Programmvariablen ( var) und Typen für Anweisungen ( cmd) Erweiterung der partiellen Ordnung auf SC zu einer Subtypbeziehung

Bemerkung: Die Subtypbeziehung ist kontravariant bzgl. der Typen für Anweisungen, d.h. falls ´ gilt, dann ist ´ cmd cmd.

Beispiel:Sei wie oben L M. Dann ist M cmd L cmd.

Man beachte dabei, dass eine Anweisung c genau dann den Typ cmd hat, wenn für

jede Zuweisung x:=y in c gilt: Die Sicherheitsklasse von x ist mindestens .Bemerkung: Typcoercion ist ebenfalls möglich.


Typsysteme und sicherer Informationsfluss...

Typkonsistenz (Type Soundness): Programmvariablen mit höherer Sicherheitsklasse dürfen keine Programmvariablen mitniedrigerer Sicherheitsklasse beeinflussen (non-interference).– Simple Security (für Ausdrücke): In einem Ausdruck vom Typ darf von

keiner Programmvariablen mit höherer Sicherheitsklasse als gelesen werden (no read up).

– Confinement (für Anweisungen): In einer Anweisung vom Typ cmd darf auf keine Programmvariable mit niedrigerer Sicherheitsklasse als geschrieben werden (no write down).


Beispiel

Gegeben sei folgender Programmabschnitt

(1) if z=0 then x:=0; else x:=1;

(2) x:=y;

mit (x) = M var, (y) = L var, (z) = H var.

SC = {L, M, H}mit L M H

cmdee

evare

:´

:´,:

:

Zu (2):– Typcoercion: Konvertierung des Typs von y von L nach M– Anwendung folgender Typinferenzregel für Zuweisungen mit = M:

Typinferenzregeln für sicheren Informationsflussgarantieren sicheren expliziten und implizitenInformationsfluss in Programmen.




(2) x:=y;

mit (x) = M var, (y) = L var, (z) = H var. Zu (1):

– Anwendung der Typinferenzregel für Zuweisungen

ergibt: x:=0 : M cmd und x:=1 : M cmd

Beispiel...


cmdee

evare

:´

:´,:

:


Beispiel...



(2) x:=y;

mit (x) = M var, (y) = L var, (z) = H var. Zu (1)...

– Betrachte die Typinferenzregel für bedingte Anweisungen:

– Gesucht: SC, sodass obige Typinferenzregel angewendet werden kanncmdcce

cmdccmdc

e

:´

:´,:

,:

elsethenif


x:=0 : M cmd

x:=1 : M cmd

()



(2) x:=y;



– Gesucht: SC, sodass obige Typinferenzregel angewendet werden kann• Typcoercion: , da z vom Typ H ist



(2) x:=y;



– Gesucht: SC, sodass obige Typinferenzregel angewendet werden kann• Typcoercion: , da z vom Typ H ist• Kontravarianz der Subtypbeziehung bzgl. der Typen für Anweisungen: , da aus

M H H cmd M cmd folgt, aber () gilt







Zusammenfassung


Einführung

Ziel: Statische Überprüfung der Sicherheit von Informationsflüssen in einem Programm (notiert in Java Bytecode (JVML), siehe unten) mit Hilfe abstrakter Interpretation einer operationalen Semantik

Vorgehensweise:– Definition einer konkreten operationalen Semantik, in der Werte und

Sicherheitsklassen von Variablen betrachtet werden(d.h. der Wert einer (konkreten) Variablen setzt sich zusammen aus einer Sicherheitsklasseund dem tatsächlichen Wert) Dynamische Überprüfung der Sicherheit von Informationsflüssen in einem Programm ( konkrete Ausführung(en) des Programms)

– Definition einer abstrakten operationalen Semantik, in der nur noch Sicherheitsklassen von Variablen betrachtet werden Statische Überprüfung der Sicherheit von Informationsflüssen in einem Programm ( abstrakte Ausführung des Programms)


Befehlssatz

Beispiel:

op hole zwei Operanden vom Stack, führe die Operation aus und schreibe das Ergebnis zurück auf den Stack

pop hole den obersten Wert v vom Stackpush k schreibe die Konstante k auf den Stackload x schreibe den Wert der Programmvariablen x auf den Stackstore x hole den obersten Wert v vom Stack und speichere ihn in der Programmvariablen x (x := v)if j hole den obersten Wert v vom Stack und, falls v 0, springe zur Adresse jgoto j springe zur Adresse jjsr j bei Adresse i: springe zur Adresse j und schreibe die Rücksprungadresse i + 1 auf den Stackret x springe zu der Adresse, die in der Programmvariablen x gespeichert isthalt stoppe

1 load z2 if 53 push 04 goto 65 push 16 store x7 load y8 store x9 halt

if z=0then x:=0;else x:=1;x:=y;


Kontrollflussgraph

Beispiel:


zugehöriger Kontrollflussgraph

1

2

3

4

6

7

8

9

5


Postdominanz und unmittelbare Postdominanz

Seien i und j Knoten in einem Kontrollflussgraphen.Knoten j postdominiert Knoten i, j pd i, falls j i und j ist auf jedem Pfad ausgehend von i nach halt.Knoten j postdominiert Knoten i unmittelbar, j ipd i, falls j pd i und esgibt keinen Knoten r mit j pd r pd i. Häufig verwendet man auch die Notation j = ipd(i). Man beachte: Für jeden Knoten i , für den ipd(i) nicht existiert, setzt man ipd(i) = .

Beispiel: Gegeben sei obiger Kontrollflussgraph.

Dann ist z.B.ipd(2) = 6.

1

2

3

4

6

7

5

1

2

3

4

6

7

5


-Sicherheit

Sei (SC, ) ein endlicher Verband von Sicherheitsklassen, SC und die Menge der Programmvariablen mit einer Sicherheitsklasse .

Dann garantiert -Sicherheit, dass Änderungen an Werten von Variablen aus nicht die Werte von Variablen aus beeinflussen.Bemerkung: -Sicherheit garantiert zudem, dass geheime Informationen nicht

durch den Zugriff auf den Stack oder durch die Beobachtung der Beendigung eines Programms sichtbar werden.

Beispiel:Sei x M und z H mit M, H SC und M H.Bemerkung: bezeichnet die Menge der Programmvariablen mit Sicherheitsklasse .

Der Programmabschnitt if z=0 then x:=0; else x:=1; istnicht M-sicher.

x: 0z: 0

m1: x: 0z: 0

m1: x: 0

z: 0m2: x: 0

z:m2: x: 0

z: 1m2: x: 1

z: 1m2

:x: 1z: 1

m2:x: 0

z: 0m1

: Man betrachte dazu folgende Speicherbelegungen m1, m2 mit m1(x) = m2(x):


-Sicherheit und konkrete Semantik

Werten von Variablen wird eine Sicherheitsklasse zugeordnet.– Sicherheitsklasse von Werten während der Ausführung eines Programms:

Kleinste obere Grenze der Sicherheitsklassen aller expliziten undimpliziten Informationsflüsse, von denen die Werte der Variablen abhängen

Befehle werden in einer Sicherheitsumgebung ausgeführt.– Die Sicherheitsumgebung entspricht stets der kleinsten oberen Grenze

der Sicherheitsklassen aller offenen impliziten Informationsflüsse. Die konkrete (operationale) Semantik wird durch eine Menge von

Inferenzregeln definiert und kann als Transitionssystem beschrieben werden, in dem ein Zustand wie folgt angegeben wird:

I= i, M, S,

Mit Hilfe der konkreten Semantik kann die -Sicherheit einer bestimmten Ausführung eines Programms überprüft werden.

SC: Sicherheitsumgebung,i: Inhalt des Befehlszählers,M: Speicherbelegung,S: Stack für Operanden,: ipd-Stack zur Protokollierung impliziter Informationsflüsse


InferenzregelEs muss gelten:Die Speicherbelegung ist in einem -konsistenten Zustand,d.h. die Variablen mit einer Sicherheitsklasse halten einen Wert mit Sicherheitsklasse .


Inferenzregel

Beispiel

Gegeben: SC = {L, M, H} mit L M H, y L, x M, z H.Gesucht: Ist folgender Programmabschnitt M-sicher?

z:x:y:

SpeicherbelegungM

Sicherheits-umgebung:

if z=0 then x:=0; else x:=1;x:=y;

L

z: (1, H)x: (0, M)y: (0, L)

,),(,,1|,,,|

_),()(][

SkMiSMi

innotikxMxic

loadload



)),((),,(),,,(,|,),0(,,|_][

iipdSupgradeiMupgradejSkMiinnotijic

SM

iftrueif

(1, H) (6, L) H



Befehlszähler:

125



,),(,,1|,,,|_][

SkMiSMiinnotikic

pushpush

6

(1, H)



,],/),[(,1|,),(,,|_][

SxkMiSkMiinnotixic

storestore

´,,,|,,,|

´),(

SMiSMi

pi

ipd

,],/),[(,1|,),(,,|

_][SxkMiSkMi

innotixic

storestore

Lipd-Stack

7

(1, H)



,),(,,1|,,,|

_),()(][

SkMiSMi

innotikxMxic

loadload

8

(0, L)



,],/),[(,1|,),(,,|_][

SxkMiSkMiinnotixic

storestore

9

Operanden-StackS



Damit obiger Programmabschnitt M-sicher ist, muss nun gelten:• Die Speicherbelegung ist M-geschützt, d.h. für alle v M gilt: Der Speicherinhalt von v hat eine Sicherheitsklasse M.• Der Operanden-Stack ist M-geschützt, d.h. alle Elemente im Operanden-Stack haben eine Sicherheitsklasse M.• Die Sicherheitsumgebung entspricht einer Sicherheitsklasse M.

!(0, L)

(1, H)


-Sicherheit und abstrakte Semantik

Keine statische Überprüfung der -Sicherheit eines Programms mit Hilfe der konkreten Semantik möglich, da damit nur der Informationsflusseiner bestimmten Ausführung des Programms untersucht werden kann!Problem: Das konkrete Transitionssystem ist unendlich.

Statt Betrachtung von Werten und Sicherheitsklassen von Variablennur noch Betrachtung der Sicherheitsklassen!

Definition einer abstrakten (operationalen) Semantik Grundlage:

Konkrete Semantik Abstraktion:

Von konkreten Werten wird dadurch abstrahiert, dass ihre Sicherheitsklassebeibehalten und ihr Wert nicht mehr berücksichtigt wird.

Man beachte: Das abstrakte Transitionssystem ist endlich.


Zusammenfassung

Typ-basierterAnsatz

Semantik-basierterAnsatz

Grundlage Typsystem (operationale) Semantik

Vorgehensweise statisch(zur Kompilierzeit)

dynamisch/statisch(zur Laufzeit,konkrete/abstrakte Ausführung)

Anzahl der Programme,die als sicher erkanntwerden

-(Fehlalarme möglich)

+(fluss-sensitiv)

Effizienz + -


Kritik

Typ-basierter Ansatz:effizient, aber Fehlalarme möglich

Semantik-basierter Ansatz:genauer (Stichwort „konservative Approximation“), aber höherer Rechenaufwand

Sogenannte „physikalische Seitenkanäle“ können von beiden Ansätzen nicht aufgedeckt werden! Darunter versteht man das Ausspionieren geheimer Informationen durch die Beobachtung des Programmverhaltens (z.B. Programmlaufzeit) u.ä.


Literatur

[1] R. Barbuti, C. Bernardeschi, N. de Francesco,Checking Security of Java Bytecode by Abstract Interpretation,ACM Symposium on Applied Computing (SAC), 2002

[2] D. Volpano, G. Smith, C. Irvine,A Sound Type System for Secure Flow Analysis,Journal of Computer Security, 1996

[3] D. E. Denning,A Lattice Model of Secure Information Flow,Communications of the ACM, 1976und ACM Symposium on Operating Systems Principles, 1975


Vielen Dank für die Aufmerksamkeit!


Ergänzungen


Vollständiger Verband der Sicherheitsklassen

Sei SC = {A, B, ...} eine Menge von Sicherheitsklassen. Sei SC SC eine Relation (Informationsfluss). Sei ein assoziativer und kommutativer binärer Verknüpfungsoperator auf

SC.

Man kann zeigen, dass SC, , einen vollständigen Verband bildet.Es gilt dann:

SC, bildet eine partielle Ordnung.– SC ist endlich.– SC hat eine untere Grenze L, sodass L A für alle A SC.– A B ist die kleinste obere Grenze von A, B SC.


Formale Systeme

Inferenzregeln:

Syntaktische Herleitbarkeit: H C, falls C durch Anwendung von Inferenzregeln aus H herleitbar ist.

Semantische Gültigkeit: Sei FS ein formales System, d.h. eine Menge von Axiomen ( C) und Inferenzregeln.

FS I= C C gilt in FS Konsistenz (Soundness): C I= C (jede syntaktisch herleitbare

Aussage ist auch semantisch gültig) Vollständigkeit (Completeness): I= C C (jede semantisch gültige

Aussage ist auch syntaktisch herleitbar)

CHH n,...,1 Annahmen

Schlussfolgerung


Transitionssysteme

Ein Transitionssystem T ist ein Tripel (S, , s0), wobei S eine Menge von Zuständen bezeichnet, s0 S ist der Anfangszustand und S S ist die Übergangsrelation. Es gibt genau dann einen Übergang von s nach s´, wenn (s, s´) . Man schreibt dann s s´. * bezeichnet die reflexive und transitive Hülle von . s S ist genau dann ein Endzustand des Transitionssystems (Schreibweise: s ), wenn kein s´ existiert mit s s´.


Kontrollflussgraph

Gegeben sei ein Programm c bestehend aus n Anweisungen.Der Kontrollflussgraph des Programms c ist der gerichtete Graph (V, E), wobei V = {1, ..., n + 1} die Menge der Knoten ist und E V V genau dann eine Kante (i, j) enthält, wenn die Anweisung bei Adresse j unmittelbar nach der Anweisung bei Adresse i ausgeführt werden kann; zudem ist eine Kante (i, n+1) für jede Adresse i enthalten, für die gilt: c[i] = halt.


-Sicherheit

Sei P = c, ein Programm und SC.Man sagt, P ist -sicher, falls für jede Zuweisung von Werten an Variablen aus gilt: Seien m1 und m2 zwei beliebige Speicherbelegungen mitD(m1) = D(m2) = Var(c) und für alle x gilt: m1(x) = m2(x). Dann muss gelten: 1, m1, i, m1´, s impliziert es existiert m2´ mit 1, m2, i, m2´, s und für alle x gilt: m1´(x) = m2´(x).

Beispiel zur Verletzung der -Sicherheit durch Beobachtung der Beendigung eines Programms:

1 load y2 if 13 halt


-Geschütztheit

Sei P = c, ein Programm und SC.– Eine konkrete Speicherbelegung M mit D(M) = Var(c) ist genau dann

-geschützt bzgl. P, wenn gilt: für alle x ist M(x) V .– Ein konkreter Operanden-Stack S ist genau dann -geschützt bzgl. P,

wenn gilt: S (V )*.

Dabei bezeichnet V alle Werte mit Sicherheitsklasse . V = (Ve SC).


-Sicherheit und konkrete Semantik

Man kann beweisen: Sei P = c, ein Programm und SC.

Falls jede terminierende Ausführung von P, die in einer -konsistenten Speicherbelegung startet und in einem Zustand I= i, M, S, endet, sodass dann gilt: M und S sind -geschützt bzgl. P und es ist ,dann ist P -sicher.


upgradeM, upgradeS

Sei W = {x | c[j] = store x und j liegt auf einem Pfad des Kontrollfluss-graphen, der bei i startet und bei ipd(i) endet, ipd(i) ausgenommen}.Für alle x W mit M(x) = (k, ): upgradeM(M, i, )(x) = (k, )

upgradeS(S, ): Setzt die Sicherheitsklasse jedes Wertes v in S auf die kleinste obere Grenze von und der Sicherheitsklasse von v.

Beispiel zur Notwendigkeit von upgradeS:1 push 12 push 03 load y4 if 65 pop6 store x7 halt

Documents

9. Dezember 2003Überprüfung der Sicherheit von Informationsflüssen in Programmen - Stefan Kurz,1 Hauptseminar Software-Sicherheit Thema Überprüfung der