Network Working Group S. Bortzmeyer
Internet-Draft AFNIC
Intended status: Standards Track September 11, 2006
Expires: March 15, 2007
Cosmogol: a language to describe finite state machines
draft-bortzmeyer-language-state-machines-00
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on March 15, 2007.
Copyright Notice
Copyright (C) The Internet Society (2006).
Bortzmeyer Expires March 15, 2007 [Page 1]
Internet-Draft Cosmogol September 2006
Abstract
Several RFC contain a state machines to describe a protocol. There
is no standard way of describing such a machine, the most common way
being an ASCII-art diagram. This document specifies an other
solution: a domain-specific language for finite state machines. It
allows state machine descriptions to be automatically checked and
translated to other formats. Its purpose is to provide a stable
reference for RFC which use this mini-language.
Table of Contents
1. Requirements notation . . . . . . . . . . . . . . . . . . . . 3
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5
4. Grammar . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
5. Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6. Internationalisation considerations . . . . . . . . . . . . . 9
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10
8. Security Considerations . . . . . . . . . . . . . . . . . . . 11
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12
9.1. Normative References . . . . . . . . . . . . . . . . . . . 12
9.2. Informative References . . . . . . . . . . . . . . . . . . 12
Appendix A. Examples . . . . . . . . . . . . . . . . . . . . . . 13
Appendix B. First implementation . . . . . . . . . . . . . . . . 17
Appendix C. Related work . . . . . . . . . . . . . . . . . . . . 18
Appendix D. Acknowledgements . . . . . . . . . . . . . . . . . . 19
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 20
Intellectual Property and Copyright Statements . . . . . . . . . . 21
Bortzmeyer Expires March 15, 2007 [Page 2]
Internet-Draft Cosmogol September 2006
1. Requirements notation
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [1].
Bortzmeyer Expires March 15, 2007 [Page 3]
Internet-Draft Cosmogol September 2006
2. Introduction
One can find finite state machines, for instance, in RFC 793 [3] or
RFC 4340 [7]. The Guide for Internet Standards Writers [4], in 2.12
"Notational conventions" and 3.3 "State machines description", lists
several ways to describe them but does not recommend one. Unlike
grammars, which are always specified with ABNF [2], state machines
have no standard description language. RFC typically use figures or
tables.
Figures (wether in ASCII-art, in Unicode-art, in SVG, in GIF or
whatever) are:
o impossible to analyze automatically (for instance to check if they
are deterministic),
o not readable if the state machine is large.
Another issue, and one which created a lot of discussions, is the
"need" to allow something more than US-ASCII (and some people require
even more than raw text) in the RFCs. A common "use case" is this
need to specify state machines through drawings. That it is not the
only way and not even the best way and the choice here is to use an
ASCII-based languages, thus requiring no change in the format of the
RFC.
Informal natural language text is not perfect either, because it
impossible to analyze automatically (for instance to check if they
are complete).
Tables are also a possible solution (if the machine is finite). They
are fine for automatic processing but very bad for presentation to
humans, specially if they are large. Most people find them too low-
level.
To conclude, let us note that RFC 4006 [6] uses a list of tuples,
each tuple being a transition. Although the (informal) syntax it
uses is not parsable by a program, the idea behind it is close from
the Cosmogol language.
Bortzmeyer Expires March 15, 2007 [Page 4]
Internet-Draft Cosmogol September 2006
3. Terminology
TODO: because of the state of this document, some choices are not
final. Every time you see the word ALTERNATIVE in uppercase, it
means several possible choices are listed.
The terminology of state machines is not perfectly standard. We use
here the words:
o state,
o message, the condition of a transition,
o action, performed after the transition.
The Cosmogol language contains declarations, assignments and
transitions. A declaration announces that a name will be used for
either a message, a state or an action. An assignment binds a value
to a variable.
A transition is described by the name of the message, the names of
the current and next state and an optional action.
A processor is a program that processes Cosmogol files. It can be
validating or not. Any processor MUST check the syntax of the file.
A validating processor MUST perform the checks described in
Section 5.
In addition to the checks, a processor MAY perform other tasks such
as translating to another format, for instance Graphviz [8].
TODO: some way to modularize state machines? For instance, X509
checking is described by several SM.
Bortzmeyer Expires March 15, 2007 [Page 5]
Internet-Draft Cosmogol September 2006
4. Grammar
Here is the grammar of Cosmogol, using ABNF [2]
state-machine = 1*(statement / (*comment-wsp))
statement = (declaration / transition / assignment)
*comment-wsp ";" *comment-wsp
colon = *comment-wsp ":" *comment-wsp
comma = *comment-wsp "," *comment-wsp
equal = *comment-wsp "=" *comment-wsp
arrow = *comment-wsp "->" *comment-wsp
declaration = names colon value
assignment = name equal value
names = name *(comma name)
name = quoted-name / regular-identifier
regular-identifier = ALPHA / (ALPHA *(ALPHA / DIGIT / "-") ALPHA)
transition = message colon
current-state arrow next-state
[colon action]
; ALTERNATIVE : some people prefer to put the current-state first:
;transition = current-state colon
; message arrow next-state
; [colon action]
; ALTERNATIVE: some people prefer to see the current-state and
; the message grouped together:
;transition = left-paren current-state comma message right-paren
; arrow next-state
; [colon action]
message = name
current-state = name
next-state = name
action = name
value = regular-identifier
Bortzmeyer Expires March 15, 2007 [Page 6]
Internet-Draft Cosmogol September 2006
identifier-chars = %x41-5A / %x61-7A / DIGIT /
"-" / "_" / "'" / "," / ";" / SP
; All letters and digits and some chars
quoted-name = DQUOTE 1*(identifier-chars) DQUOTE
comment = "#" *(WSP / VCHAR) CRLF
comment-nl = comment / CRLF
comment-wsp = *(WSP / comment-nl)
Bortzmeyer Expires March 15, 2007 [Page 7]
Internet-Draft Cosmogol September 2006
5. Semantics
A validating processor MUST perform all these checks.
Every message, state and action MUST be declared. The possible
values for the right side of a declaration are:
o MESSAGE
o STATE
o ACTION
All names are case-sensitive. ALTERNATIVE: make them case-
insensitive, which is possible since everything is in US-ASCII.
TODO: should we document naming *conventions*, such as "States in
uppercase, messages in capitalized"?
Assignments are only possible to pre-defined variables. No
assignment is mandatory. They are:
o Title (used for some displays)
o Initial (to indicate the initial state; if this variable is
assigned, every state MUST be reachable - may be indirectly - from
the initial state)
The state machine MUST be deterministic, that is for every couple
(message, current state), there must be only one output (next state
and optional action).
Besides the "Initial" variable mentioned above, a processor MAY
provide a mean to the user to declare (may be on the command line) a
state as the start of the machine and the processor MAY check that
every other state is reachable from this state, as if it were
declared as "Initial".
Bortzmeyer Expires March 15, 2007 [Page 8]
Internet-Draft Cosmogol September 2006
6. Internationalisation considerations
The character set of the language is US-ASCII only. This reflects
the fact that RFC must be written in english (TODO: reference for
that?).
Bortzmeyer Expires March 15, 2007 [Page 9]
Internet-Draft Cosmogol September 2006
7. IANA Considerations
None
Bortzmeyer Expires March 15, 2007 [Page 10]
Internet-Draft Cosmogol September 2006
8. Security Considerations
Implementors of state machines are warned to pay attention to the
default case, the one for which there is no explicitely listed
transition.
ALTERNATIVE: force every transition to be declared. This is believed
to be too demanding for large SM.
Bortzmeyer Expires March 15, 2007 [Page 11]
Internet-Draft Cosmogol September 2006
9. References
9.1. Normative References
[1] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997.
[2] Crocker, D., Ed. and P. Overell, "Augmented BNF for Syntax
Specifications: ABNF", RFC 4234, October 2005.
9.2. Informative References
[3] Postel, J., "Transmission Control Protocol", STD 7, RFC 793,
September 1981.
[4] Scott, G., "Guide for Internet Standards Writers", BCP 22,
RFC 2360, June 1998.
[5] Hollenbeck, S., "Extensible Provisioning Protocol (EPP)",
RFC 3730, March 2004.
[6] Hakala, H., Mattila, L., Koskinen, J-P., Stura, M., and J.
Loughney, "Diameter Credit-Control Application", RFC 4006,
August 2005.
[7] Kohler, E., Handley, M., and S. Floyd, "Datagram Congestion
Control Protocol (DCCP)", RFC 4340, March 2006.
[8] AT&T Research, "Graphviz, Graph Visualization Software",
December 2004, .
[9] Rapp, C., "The State Machine Compiler", January 2000,
.
[10] Thurston, A., "Ragel State Machine Compiler", August 2006,
.
[11] "FSMLang", September 2006, .
Bortzmeyer Expires March 15, 2007 [Page 12]
Internet-Draft Cosmogol September 2006
URIs
[12]
Bortzmeyer Expires March 15, 2007 [Page 13]
Internet-Draft Cosmogol September 2006
Appendix A. Examples
The TCP state machine, from RFC 793 [3].
# The TCP state machine. RFC 793 3.2 "Terminology"
SYN-RCVD, SYN-SENT, FIN-WAIT-1, FIN-WAIT-2, SENT, ESTAB,
CLOSING, TIME-WAIT, CLOSED, CLOSE-WAIT,
LISTEN, LAST-ACK : STATE;
CLOSE, passive-OPEN, active-OPEN ,
rcv-SYN, rcv-ACK-of-FIN, rcv-ACK-of-SYN,
rcv-FIN, SEND, Timeout : MESSAGE;
CLOSE: LISTEN -> CLOSED : Delete-TCB ;
# ALTERNATIVE syntax:
# LISTEN : CLOSE > CLOSED : Delete-TCB ;
# ALTERNATIVE syntax:
# (LISTEN, CLOSE) -> CLOSED : Delete-TCB ;
passive-OPEN : CLOSED -> LISTEN : Create-TCB;
rcv-SYN: LISTEN -> SYN-RCVD;
CLOSE: SYN-RCVD -> FIN-WAIT-1;
rcv-ACK-of-FIN: FIN-WAIT-1 -> FIN-WAIT-2;
rcv-FIN : FIN-WAIT-2 -> TIME-WAIT;
active-OPEN: CLOSED -> SYN-SENT;
SEND: LISTEN -> SYN-SENT;
rcv-SYN: SYN-SENT -> SYN-RCVD;
rcv-ACK-of-SYN: SYN-RCVD -> ESTAB;
rcv-SYN: SYN-SENT -> ESTAB;
CLOSE: ESTAB -> FIN-WAIT-1;
rcv-FIN: ESTAB -> CLOSE-WAIT;
CLOSE: CLOSE-WAIT -> LAST-ACK;
Timeout: TIME-WAIT -> CLOSED;
Bortzmeyer Expires March 15, 2007 [Page 14]
Internet-Draft Cosmogol September 2006
rcv-ACK-of-FIN: LAST-ACK -> CLOSED;
The EPP state machine, from RFC 3730 [5].
Bortzmeyer Expires March 15, 2007 [Page 15]
Internet-Draft Cosmogol September 2006
# Extensible Provisioning Protocol (EPP)
"Waiting for client", "Prepare greeting", "End session",
"Waiting for client authentication", "Processing login",
"Prepare fail response", "Prepare response",
"Waiting for command", "Processing command": STATE;
"Connected or hello", "Close connection or idle",
"Send greeting", "login received", "Send response",
Timeout, "Auth fail",
"Auth OK", "Command received",
"Command processed", "Send X5xx response",
"Send 2501 response": MESSAGE;
"Connected or hello" : "Waiting for client" -> "Prepare greeting";
"Close connection or idle": "End session" ->
"Waiting for client";
"Send greeting": "Prepare greeting" ->
"Waiting for client authentication";
Timeout : "Waiting for client authentication" -> "End session";
"login received": "Waiting for client authentication" ->
"Processing login";
"Auth fail" : "Processing login" -> "Prepare fail response";
"Send response" : "Prepare fail response" ->
"Waiting for client authentication";
"Auth OK": "Processing login" -> "Waiting for command";
Timeout: "Waiting for command" -> "End session";
"Send response" : "Prepare response" -> "Waiting for command";
"Command processed" : "Processing command" ->
"Prepare response";
"Command received" : "Waiting for command" ->
"Processing command";
"Send X5xx response": "Prepare response" -> "End session";
"Send 2501 response": "Prepare fail response" ->
"End session";
Bortzmeyer Expires March 15, 2007 [Page 16]
Internet-Draft Cosmogol September 2006
The DCCP state machine, from RFC 4340 [7].
# RFC 4340, 8.4. "DCCP State Diagram"
CLOSED, LISTEN, REQUEST, RESPOND, OPEN, PARTOPEN, CLOSING, TIMEWAIT,
CLOSEREQ : STATE;
Passive-open, Active-open, Receive-ack, Receive-reset,
Server-active-close, Active-close, Receive-packet,
Receive-response,
Receive-request, Timer-expires, Receive-close : MESSAGE;
Passive-open: CLOSED ->LISTEN;
Receive-request: LISTEN ->RESPOND;
Receive-ack:RESPOND ->OPEN;
Receive-reset : CLOSING ->TIMEWAIT;
Server-active-close: OPEN ->CLOSEREQ;
Receive-close: CLOSEREQ ->CLOSED;
Active-close: OPEN ->CLOSING;
Receive-response: REQUEST ->PARTOPEN;
Receive-packet: PARTOPEN ->OPEN;
Active-open: CLOSED ->REQUEST;
Timer-expires: TIMEWAIT -> CLOSED;
Receive-close: OPEN ->CLOSED;
Bortzmeyer Expires March 15, 2007 [Page 17]
Internet-Draft Cosmogol September 2006
Appendix B. First implementation
The first implementation of the Cosmogol language can be found at
.
Bortzmeyer Expires March 15, 2007 [Page 18]
Internet-Draft Cosmogol September 2006
Appendix C. Related work
All of them are interesting back-ends for a Cosmogol processor:
Graphviz [8] is a widely-used language to describe graphs. It has
been used for state machines such as TCP [12]. But it is more
presentation-oriented, you cannot restrict it to just the
description. Consequently, there are currently no tools to check,
for instance the determinism.
SMC [9], Ragel [10] and FSMlang [11] are more oriented towards
code-generation.
Bortzmeyer Expires March 15, 2007 [Page 19]
Internet-Draft Cosmogol September 2006
Appendix D. Acknowledgements
Significant contributions were or will be made by Bertrand Petit,
Phil Regnauld, Olivier Ricou, Pierre Beyssac and Thomas Quinot.
Bortzmeyer Expires March 15, 2007 [Page 20]
Internet-Draft Cosmogol September 2006
Author's Address
Stephane Bortzmeyer
AFNIC
Immeuble International
Saint-Quentin-en-Yvelines 78181
France
Phone: +33 1 39 30 83 46
Email: bortzmeyer+ietf@nic.fr
URI: http://www.afnic.fr/
Bortzmeyer Expires March 15, 2007 [Page 21]
Internet-Draft Cosmogol September 2006
Full Copyright Statement
Copyright (C) The Internet Society (2006).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Acknowledgment
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
Bortzmeyer Expires March 15, 2007 [Page 22]