Download pptx - Protocol Engineering: Beschreibung und Entwicklung von Kommunikationsprotokollen

Protocol Engineering: Beschreibung und Entwicklung von

Kommunikationsprotokollen

Fakultät Informatik, Institut für Software- und Multimediatechnik, Lehrstuhl Softwaretechnologie

Dresden, 1. Juli 2011

Falk Hartmann

Wissenschaftlicher Vortrag im Rahmen des Promotionsverfahrens

Protocol Engineering: Beschreibung und Entwicklung von Kommunikationsprotokollen

Agenda

Folie 2


Agenda

Folie 3


Kommunikationsprotokoll (1)

Basically, a protocol is an agreement between the communicating parties on how communication is to proceed.

[Tanenbaum und Wetherall, 2010]

A well-defined set of messages […] each of which carries a defined meaning (semantics), together with the rules governing when a particular message can be sent.

[Larmouth, 2000]

Ein Kommunikationsprotokoll ist eine Verhaltenskonvention, die die zeitliche Abfolge der Interaktionen zwischen den diensterbringenden Instanzen vorschreibt und die Formate (Syntax und Semantik) der auszutauschenden Nachrichten definiert.

[König, 2003]

Folie 4


Kommunikationsprotokoll (2)

Ein Kommunikationsprotokoll beschreibt die Abläufe bei der Kommunikation zwischen zwei (oder mehr) Kommunikationspartnern und die Syntax und Semantik der zwischen den Kommunikationspartnern ausgetauschten Botschaften.

Typische Merkmale- Zeitabhängiges Verhalten

Timeouts- Nichtdeterminismus

Gleichzeitigkeit mehrerer Ereignisse (Botschaften, Timeouts...)Mehrere Folgereaktionen auf ein Ereignis

Folie 5


Eigenschaften von Kommunikationsprotokollen

Anzahl der Kommunikationspartner- 2 (Unicast/Anycast)- >2 (Multicast/Broadcast)

Synchronität- Synchron (Request/Reponse)- Asynchron

Verbindungsorientierung- Verbindungslos (Brief) - Verbindungsorientiert (Telefonat)

Übertragungsrichtung- Simplex (eine Richtung)- Halbduplex (zu jedem Zeitpunkt nur eine Richtung)- Duplex (gleichzeitig in beide Richtungen)

Folie 6


Anwendungsgebiete

Folie 7


Schichtenarchitekturen

Folie 8


Verhältnisse zwischen den Schichten

Folie 9


Dienstprimitive

Benennung nach ISO/OSI-Notation[<Schicht>]<Name> <Typ>([<Parameter>{,<Parameter>}])

Typenrequest – Anfordern eines Dienstes an Dienstzugangspunkt Aindication – Anzeige am Partner-Dienstzugangspunkt Bresponse – Antwort am Partner-Dienstzugangspunkt Bconfirm – Bestätigung der Diensterbringung an Dienstzugangspunkt A

BeispieleTCONNECT request(remoteHost, remotePort, localHost, localPort)

Vereinfachungen TCONNECTrequ(...) – übliche VerkürzungCONNECTrequ(...) – wenn Schicht eindeutig

Folie 10


Entwicklungsphasen

TODO

Folie 11

nach [König, 2003]


Agenda

Folie 12


Botschaftsbeschreibung

Allgemein- Beschreibung der in den Botschaften enthaltenen Daten

- Abstrakte Syntax- Beschreibung der zu übertragenden Botschaften

- Transfersyntax (≙ konkrete Syntax)- Beschreibung der Abbildungen

- Abstrakte Syntax → Transfersyntax: Kodierung (Encoding, Serialisierung, Marshalling)

- Transfersyntax → Abstrakte Syntax: Dekodierung (Decoding, Deserialisierung, Unmarshalling, Parsen)

Herangehensweisen- Grammatiken- Deklarative Ansätze (ASN.1, Protocol Buffers)- Algebraische Ansätze (ACT ONE)

Folie 13


Botschaftstypen

Typ der Botschaften- Text

- Beschreibung durch Grammatik- Kodierung manuell oder durch generierten Code- Dekodierung durch generierten Code (Parser-Generator)

- XML- Beschreibung durch XML Schema- Kodierung/Dekodierung durch generierten Code (Binding-Technologien

wie JAXB/JAXWS) oder XML-APIs wie DOM, SAX oder StAX- Binär

- Beschreibung durch ASN.1 oder Protocol Buffers- Kodierung/Dekodierung manuell oder durch generierten Code

Folie 14


ASN.1 (Allgemein)

Allgemeines- Abstract Syntax Notation 1- ASN.1 definiert abstrakte Syntax, also in Botschaften zu transportierende

Daten unabhängig von ihrer konkreten Darstellung- Analogie zu IDLs- Encoding Rules

- definieren Übersetzung in Transfersyntax- existieren für binäre, textuelle und XML-basierte Transfersyntax

- Nachbildung nicht mit ASN.1 definierter Botschaften nur bedingt möglich- Keine Unterstützung für Berechnung abhängiger Teile der Botschaften

Geschichte- Grundlage: Beschreibungssyntax X.409 der CCITT (1984)- Standardisierung als ISO 8824/8825 (1987)

Folie 15


ASN.1 (Syntax)

Grundlegende Sprachmittel- Typ- und Wertedefinitionen- Parametrisierte Typen- Datentyperweiterbarkeit- Makros

Elementare Typen- BOOLEAN, INTEGER, OCTET STRING, BIT STRING, IA5String

Operatoren auf Typen- Wertebereichsbegrenzungen- SEQUENCE/SEQUENCE OF- SET/SET OF- CHOICE - ENUMERATED - Default-Werte und Optionalität möglich

Tags- Unterscheidung der Fälle z.B. bei CHOICE

Folie 16


Beispiel: TCP Segment

Folie 17


ASN.1 (Beispiel)

Folie 18


ASN.1 – Basic Encoding Rules

Allgemein- Grundlegenste Kodierung- Metainformationen werden nahezu komplett übernommen- TLV : Type, Length, Value- Sehr gute Eignung als Transfersyntax- Encoding erzeugt in der Regel relativ große PDUs → Packed Encoding Rules

BeispielTCP Packet von Port 56237 zu Zielport 4444

Folie 19

Type: 02 = Integer, Length: 02 = 2 Byte, Value: 0x115c = 4444


ASN.1 – Packed Encoding Rules

Allgemein- Adressierung der Kritikpunkte an den Basic Encoding Rules- Metainformationen werden als dem Dekodierer bekannt vorausgesetzt- Abkehr von TLV

BeispielTCP Packet von Port 56237 zu Zielport 4444

Folie 20

Value: 0x115c = 4444


Protocol Buffers (Allgemein)

Allgemeines- Definition der Transfersyntax- Typsystem definiert Typen aus Sicht der Transfersyntax- Werkzeugunterstützung

- Definition von Abbildungen auf Typsysteme der Zielsprachen (C++, Java, Python)

- Entworfen für die Codegenerierung- Platzsparende Kodierung

- durch Kodierung mit variabler Länge („varint“)- Nicht geeignet zur Nachbildung von mit anderen Mitteln definierten

Botschaften- Keine Beschreibungsmöglichkeiten für abhängige Teile der Botschaft

Geschichte- Erstveröffentlichung (Version 2.0) durch Google (2008)- Aktuelle Version 2.4.1

Folie 21


Protocol Buffers (Syntax)

Grundlegende Sprachmittel- Botschaftsdefinitionen- Einbettung von Botschaften- Default-Werte und Optionalität/Wiederholung möglich- Erweiterbarkeit

Elementare Typen- Integer verschiedener Wertebereiche mit Kodierung variabler bzw. fester

Länge- Strings (UTF-8/ASCII)- Boolean- Float/Double- Byte-Felder

Tags- Analog zu ASN.1

Folie 22


Agenda

Folie 23


Kommunikationsablauf

Visualisierung- Message Sequence Charts- Zustandsübergangsdiagramme- Strukturdiagramme

Formale Beschreibungstechniken- Endliche Zustandsautomaten (FSM)- Prozessalgebren- Temporale Logiken

Werkzeuge- LOTOS- SDL

Folie 24


Message Sequence Charts (Allgemein)

Geschichte- Vorschlag durch [Grabowski und Rudolph, 1992]- basierend auf OSI-Zeitablaufdiagramme und ISDN Information Flow Diagrams- MSC´92: Normierung durch ITU-T in der Empfehlung Z.120- MSC´96: Denotationelle Semantik basierend auf Prozessalgebren- MSC´2000: Datentypen, entfernte Methodenaufrufe, Objektorientierung- UML Sequenzdiagramme nehmen Anleihen bei MSCs

Allgemeines- Graphische (MSC/GR) und textuelle Variante (MSC/PR)

Folie 25


Message Sequence Charts (Beispiel)

Folie 26


Zustandsübergangsdiagramm (Allgemein)

Geschichte- Statechart Notation [Harel, 1987]- Verwendung zur Abbildung von Protokollabläufen verbreitet [Stevens, 1993]- Normierung als State Diagram innerhalb der UML 1.x

Allgemein- Typischerweise Interpretation als endliche Zustandsautomaten

Folie 27


Zustandsübergangsdiagramm (Beispiel)

Folie 28

nach [Stevens, 1993]


Strukturdiagramm

Allgemein- Visualisierung der statischen Verhältnisse mehrerer Kommunikationspartner- Breite Anwendung im Bereich der Prozessalgebren- Vermutliche erste Verwendung in [Hoare, 1985]

Folie 29


Endliche Zustandsautomaten (Allgemein)

DefinitionEin endlicher Zustandsautomat ist ein Verhaltensmodell basierend auf einer endlichen Menge von Zuständen, einer Menge von Übergängen zwischen den Zuständen und Ein- und Ausgaben, welche mit den Übergängen bzw. Zuständen verknüpft sind.

Geschichte- Basierend auf Arbeiten an den Bell Labs [Mealy, 1955], [Moore, 1956]

Allgemeines- Moore-Automat: Eingaben sind mit den Übergängen assoziiert, Ausgaben mit

den Zuständen- Mealy-Automat: Ein- und Ausgaben sind mit den Übergängen assoziiert- Timed Automata

- Erweiterung um Zeitbegriff („Uhren“)- Übergänge können Uhren setzen bzw. vom Wert der Uhren abhängen

Folie 30


Endliche Zustandsautomaten (Beispiel)

Visualisierung - mittels Zustandsübergangsdiagramm (Innensicht)- mittels Strukturdiagramm (Außensicht)

Folie 31


Prozessalgebren (Allgemein)

DefinitionProzessalgebren sind eine formale Beschreibungstechnik für komplexe Computersysteme, insbesondere für Systeme, welche kommunizierende, nebenläufige Komponenten enthalten. (nach [Bergstra et al., 2001])

Geschichte- Communicating Sequential Processes (CSP) [Hoare, 1978]- Calculus of Communicating Systems (CCS) [Milner, 1980]- Finite State Processes (FSP) [Magee und Kramer, 2006]

Allgemeines- Betrachtung von Prozessen und Aktionen- Abbildung auf Protocol Engineering

- Kommunikationspartner ≙ Prozess- Dienstprimitivaufrufe und Botschaftsversand-/empfang ≙ Aktion

Folie 32


Prozessalgebren (Allgemein)

Semantik- FSP definiert über Labelled Transition Systems [Magee und Kramer, 2006]- Prozessalgebren erlauben die Verifikation wichtiger Eigenschaften

- Safety- „Nichts Negatives wird passieren.“- In jedem Zustand des Gesamtmodells kann keine Aktion auftreten,

für die es keinen Folgezustand gibt.- Progress

- „Etwas Positives wird irgendwann passieren.“- In jedem Zustand des Gesamtmodells wird eine der zulässigen

Aktionen eventuell auftreten.- Gegenteil zur Starvation

Folie 33


Prozessalgebren (Syntax)

Prozessbeschreibung

Folie 34

P, Q : Prozessex, y : Aktionena, a’ : Namen für Aktionen

Präfix x → P

Ein Prozess, der mit der Aktion x beginnt und sich dann wie P verhält.

Alternative x → P|y → Q

Ein Prozess, der entweder mit der Aktion x beginnt und sich dann wie P verhält oder mit der Aktion y beginnt und sich dann wie Q verhält.

Parallele KompositionP||Q

Die nebenläufige Abarbeitung der Prozesse P und Q. Die Prozesse synchronisieren sich auf gleichnamigen Aktionen.

Prozessbenennunga:P

Der Prozess, der aus P hervorgeht, wenn den Namen aller Aktionen ein a vorangestellt wird.

AktionsumbenennungP/{a1’/a1,...,an’/an}

Der Prozess, der aus P hervorgeht, wenn in allen Aktionen, deren Name mit ai beginnt, der Namensbeginn durch ai’ ersetzt wird (für 0≤i≤n).


Prozessalgebren (Beispiel)

Folie 35



Folie 36



Folie 37



Prüfung von Safety und Progress-Eigenschaft- Naive Implementierung des TCP-Zustandsübergangsdiagramms

Folie 38

Problem 1:Aktionen, die nur sendend auftreten!

Problem 2:Namensgleichheit zwischen ACK für SYN und FIN.

Problem 3:Kanalmodellierung für simultanes Schließen nötig!


Temporale Logiken (Allgemein)

DefinitionTemporale Logiken sind Erweiterungen der Aussagenlogik durch Operatoren, die die Formulierung von Aussagen mit Bezugnahme auf die Zeit gestatten.

Geschichte- Grundlage durch Arthur Prior [Prior, 1957] - Temporal Logic of Actions [Lamport, 1993]- Fluent Linear Temporal Logic [Magee und Kramer, 2006]

Allgemeines- Linear vs. Branching Time- Zeitliche Ordnung von Ereignissen vs. absolute Zeit- Anwendung in der Protokollmodellierung zur Spezifikation und Prüfung von

Liveness-Eigenschaften - Zeitliche Operatoren

- □ always/immer- ◊ eventually/irgendwann

Folie 39


Temporale Logiken (Allgemein/Beispiel)

Folie 40

Fluent- Ableitung eines Zustands aus einem Ablaufs von Aktionen- Initiierende und beendende Aktionen

Assertion- Sicherstellung einer temporallogischen Formel über Fluents- Automatische Prüfung z.B. in LTSA [Giannakopoulou und Magee, 2003]

Beispiel- Sicherstellung der Liveness-Eigenschaft „Die Kommunikationspartner

erreichen immer wieder einen erfolgreichen Verbindungsaufbau.“


LOTOS

Allgemeines- Language Of Temporal Ordering Specification- Grundkonzepte:

- Prozessalgebren, insbesondere CCS [Milner,1980]- Erweiterung um Unterbrechungen

- Algebraische Botschaftsbeschreibung mittels ACT ONE- Einsatz für Verifikation, Leistungsvorhersage und Test

z.B. im GSM-Bereich [Iglesias et al., 2001] - Hoher Formalisierungsgrad verhindert breite praktische Anwendung

Implementierungen- Topo (Toolset for Product Realisation with Lotos) [Mañas et al.,1993]

Geschichte- Standardisierung als ISO 8807 (1990)- Erweiterung um Grafische Variante GLOTOS als ISO 8807/AM1

Folie 41


SDL

Allgemeines- Specification and Description Language- Grundkonzepte

- Zustandsautomaten für Prozesse (Agenten)- Semantik basierend auf CSP [Hoare, 1978]- Botschaftsmodellierung typischerweise basierend auf ASN.1

- Standardisierung als ITU-T Z.100- Graphische (SDL/GR) und textuelle Variante (SDL/PR)- Integration von MSC- Starker Einsatz im Telekommunikationsbereich (z.B. ISDN-Dienstedefinition)

Implementierungen- Cinderella SDL (grafisches Modellierungstool)- Tau SDL Suite (jetzt IBM, Teil der Rational-Produktlinie)

Geschichte- SDL ´76: Erste Version- SDL ´88: Klare Grammatik und Semantik- Aktuelle Version SDL 2000

Folie 42


Agenda

Folie 43


Fazit

Aktueller Stand- Mächtige formale Beschreibungsmittel- Verbreitung auf spezielle Bereiche beschränkt

- ASN.1 und SDL relativ verbreitet in der Telekommunikation- Hoher Einarbeitungsaufwand

- Interpretation der Verifikationsergebnisse erfordert Erfahrung

Trends- Protokollmodellierung/Codegenerierung- Verifikation von Sicherheitsprotokollen- Verifikation der Protokollimplementierung

Folie 44


Protokollmodellierung/Codegenerierung

Botschaftschreibung- Eher evolutionäre Entwicklungen- ASN.1

- Verbesserter Tool-Support z.B. ASN1Compiler (Objective Systems)- Neue Einsatzbereiche, z.B. Medical Device Encoding Rules (ISO/IEEE

11073) zum Vitaldatenaustausch im medizinischen Gerätebau [Schrenker und Cooper, 2001]

- Protocol Buffers

Folie 45



Protokollabläufe- Domänenspezifische Sprachen für Spezialfälle

The Austin Protocol Compiler [McGuire und Gouda, 2005]- TAP - Timed Abstract Protocol Notation - Sprache zur Beschreibung asynchroner Protokolle- Vorgehen

- Beschreibung des Protokolls in TAP- Verifikation der Protokollbeschreibung- Umsetzung in implementierungsfreundliches Protokollmodell - Generierung von Protokoll-Stubs in C

- Garantiert Übertragung der verifizierten Eigenschaften der Spezifikation in die Implementierung

Folie 46



spi2java [Busenius und Ivanova,2008] , [Pironti und Sisto, 2007], [Pozza et al., 2004]

- Basierend auf Spi-Kalkül (-Kalkül mit kryptografischen Operationen)- Generiert Java-Code- Garantiert Übereinstimmung des Codes mit der im Spi-Kalkül formulierten

Spezifikation

Annäherung UML/SDL [Bochmann et al., 2010]- Bereits existierende Gemeinsamkeiten: MSC, State Charts- Entwicklung eines UML-Profiles für SDL (neue Version 2009)- Kauf von Telelogic zu IBM (Tau SDL Suite)

Folie 47


Verifikation von Sicherheitsprotokollen

Grundidee- Verifikation von Sicherheitsprotokollen (z.B. zum Schlüsselaustausch, zur

Authentifizierung)- Modellierung der Kommunikationspartner und eventueller Eindringlinge durch

Prozessalgebren, z.B. CSP [Ryan und Schneider, 2000]- Abbildung der gewünschten Protokolleigenschaften in temporallogische

Formeln- Geheimhaltung, Anonymität, Unleugbarkeit

CAPSL- CAPSL – Common Authentification Protocol Specification Language [Millen,

1997]- CASPER-Compiler: Generierung von Spezifikationen für Model Checker, z.B.

FDR (Formal Systems)- Codegenerierung für Java

SPIN- Vorgehensweise zur Modellierung in PROMELA [Yongjian und Rui, 2004]

Folie 48


Verifikation der Protokollimplementierung

Verifikation der Protokollimplementierung [Jurjens, 2009]- First-order Logic-Ansatz- Übersetzung der (Java-)Implementierung in Prädikatenlogik mittels

Kontrollfluss-Analyse- Übergabe an ATP mittels Austauschformat- „Gegenentwurf“ zu spi2java, Verifikation ausgehend vom Code

[Bokor et al., 2007]- Ausgangspunkt: Synchrones rundenbasiertes Diagnose-Protokoll (DD),

entwickelt für ein framebasiertes Time-Triggered-System- Ziel: Berechnung eines konsistenten Global-Health-Vector- Portierung auf Time-Triggered-Architecture - Modellierung und Analyse der Konsistenzbedingung mittels SAL- Fehlverhalten auf Time-Triggered-Architecture- Lösung: Read- und Send-Alignment zur Resynchronisation der

verfügbaren Information

Folie 49


Vielen Dank für Ihre Aufmerksamkeit!

Folie 50


Agenda

Folie 51


Standardisierungsorganisationen

CCITT Comité Consultatif International Téléphonique et Télégraphique (jetzt ITU-T)

ISO International Organization for Standardization

ITU International Telecommunication Union

ITU-T ITU, Telecommunication Standardization Sector

OMG Object Management Group

Folie 52


Abkürzungen (1)

Folie 53

ACT ONE Algebraic specification techniques for Correct design of Trusty software systems

ASN.1 Abstract Syntax Notation

BER Basic Encoding Rules

CCS Calculus of Communicating Systems

CSP Communicating Sequential Processes

FSM Finite State Machine

FSP Finite State Processes

IP Internet Protocol

HTTP HyperText Transfer Protocol

LOTOS Language Of Temporal Ordering Specification

LTS Labelled Transition System


Abkürzungen (2)

Folie 54

MT-SICS Mettler Toledo Standard Interface Command Set

OBD-2 On-Board-Diagnose

OSI Open Systems Interconnection

PER Packed Encoding Rules

SAL Symbolic Analysis Laboratory

SOAP Simple Object Access Protocol

SDL Specification and Description Language

TCP Transmission Control Protocol

TTCN Testing and Test Control Notation

UML Unified Modeling Language

WAP Wireless Application Protocol

XML Extensible Markup Language


Konferenzen

FORTE - International Conference on Formal Techniques for Networked and Distributed Systems

ICNP – International Conference on Network Protocols

TestCom - International Conference on Testing Communicating Systems

TTCN-3 User Conferences

WRiPE (ab 2011) - International Workshop on Rigorous Protocol Engineering

Folie 55


Literatur (1)

Folie 56


Literatur (2)

Folie 57


Literatur (3)

Folie 58


Literatur (4)

Folie 59


Literatur (5)

Folie 60


Beispiel: HTTP und seine Grundlagen

Folie 61


ACT ONE (Allgemein)

Allgemein- Algebraic specification techniques for Correct design of Trusty software

systems (version 1)- Botschaften als abstrakte Datentypen, welche algebraisch beschrieben

werden- Sorten (natürliche Zahlen)- Operatoren (Addition)- Gleichungen (Kommutativität der Addition)

- Keine Abbildung in konkrete Syntax definiert- Steuerung von Codegeneratoren über Annotationen möglich [Schröder, 2003]

Geschichte- Basierend auf [Ehrig und Mahr, 1985]- Standardisiert als Anhang zur Spezifikation ISO 8807 (LOTOS)

Folie 62


ACT ONE (Beispiel)

Folie 63


Zeitablaufdiagramm (Allgemein)

Geschichte- OSI Time Sequence Diagramm (vor 1990)

Allgemein- Typischerweise Darstellung des zeitlichen Ablaufs der Aufrufs der

Dienstprimitive- Beispielhafte Darstellung- Keine formale Grundlage- Weiterentwicklung und Standardisierung als Message Sequence Charts

Folie 64


Zeitablaufdiagramm (Beispiel)

Folie 65

nach [König, 2003]


Zustandsübergangsdiagramm (Beispiel)

Folie 66

nach [Stevens, 1993]

Ausschnitt zeigt Übergänge aus der Sicht des Initiators, welcher die Verbindung auch aktiv schließt.


MDML

Allgemein- Definition der abstrakten Syntax- Zuordnung der Kodierung/Dekodierung zu den einzelnen Elementen der

abstrakten Syntax- Beschreibung abhängiger Teile der Botschaft möglich

(Prüfsummen, Längen)

Geschichte- Textuelle, XML-basierte Syntax (2008)- Graphische Syntax [Schmidt 2010]

Folie 67


Endliche Zustandsautomaten (Beispiel)

Folie 68


spi2java

Folie 69