idnits 2.17.1 draft-bortzmeyer-language-state-machines-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 15. -- Found old boilerplate from RFC 3978, Section 5.5 on line 575. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 586. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 593. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 599. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (November 11, 2006) is 6374 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Obsolete normative reference: RFC 4234 (ref. '2') (Obsoleted by RFC 5234) -- Obsolete informational reference (is this intentional?): RFC 793 (ref. '3') (Obsoleted by RFC 9293) -- Obsolete informational reference (is this intentional?): RFC 3730 (ref. '6') (Obsoleted by RFC 4930) -- Obsolete informational reference (is this intentional?): RFC 4006 (ref. '7') (Obsoleted by RFC 8506) Summary: 4 errors (**), 0 flaws (~~), 1 warning (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group S. Bortzmeyer 3 Internet-Draft AFNIC 4 Intended status: Standards Track November 11, 2006 5 Expires: May 15, 2007 7 Cosmogol: a language to describe finite state machines 8 draft-bortzmeyer-language-state-machines-01 10 Status of this Memo 12 By submitting this Internet-Draft, each author represents that any 13 applicable patent or other IPR claims of which he or she is aware 14 have been or will be disclosed, and any of which he or she becomes 15 aware will be disclosed, in accordance with Section 6 of BCP 79. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as Internet- 20 Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt. 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 This Internet-Draft will expire on May 15, 2007. 35 Copyright Notice 37 Copyright (C) The Internet Society (2006). 39 Abstract 41 Several RFCs contain a state machine to describe a protocol. There 42 is no standard way of describing such a machine, the most common way 43 being an ASCII-art diagram. This document specifies an other 44 solution: a domain-specific language for finite state machines. It 45 allows state machine descriptions to be automatically checked and may 46 be translated into other formats. Its purpose is to provide a stable 47 reference for RFCs which use this mini-language. 49 Table of Contents 51 1. Requirements notation . . . . . . . . . . . . . . . . . . . . 3 52 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 53 3. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 54 4. Grammar . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 55 5. Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . 8 56 6. Internationalisation considerations . . . . . . . . . . . . . 10 57 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 58 8. Security Considerations . . . . . . . . . . . . . . . . . . . 12 59 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 60 9.1. Normative References . . . . . . . . . . . . . . . . . . . 13 61 9.2. Informative References . . . . . . . . . . . . . . . . . . 13 62 Appendix A. Examples . . . . . . . . . . . . . . . . . . . . . . 14 63 Appendix B. First implementation . . . . . . . . . . . . . . . . 17 64 Appendix C. Related work . . . . . . . . . . . . . . . . . . . . 18 65 Appendix D. Changes . . . . . . . . . . . . . . . . . . . . . . . 19 66 D.1. Changes from -00 . . . . . . . . . . . . . . . . . . . . . 19 67 Appendix E. Acknowledgements . . . . . . . . . . . . . . . . . . 20 68 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 21 69 Intellectual Property and Copyright Statements . . . . . . . . . . 22 71 1. Requirements notation 73 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 74 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 75 document are to be interpreted as described in [1]. 77 2. Introduction 79 One can find finite state machines, for instance, in RFC 793 [3] or 80 RFC 4340 [8]. The Guide for Internet Standards Writers [5], in 2.12 81 "Notational conventions" and 3.3 "State machines description", lists 82 several ways to describe them but does not recommend one. Unlike 83 grammars, which are always specified with ABNF [2], state machines 84 have no standard description language. RFCs typically use figures, 85 list of transitions or tables. 87 Figures (wether in ASCII-art, in Unicode-art, in SVG, in GIF or 88 whatever) are: 90 o impossible to analyze automatically (for instance to check if they 91 are deterministic), 93 o not readable if the state machine is large. 95 Another issue, and one which created a lot of discussions, is the 96 "need" to allow something more than US-ASCII (and some people require 97 even more than raw text) in the RFCs. A common "use case" is this 98 need to specify state machines through drawings. That it is not the 99 only way and not even the best way and the choice here is to use an 100 ASCII-based languages, thus requiring no change in the format of the 101 RFC. 103 Informal natural language text is not perfect either, because it 104 impossible to analyze automatically (for instance to check if they 105 are complete). 107 Tables are also a possible solution (if the machine is finite). They 108 are fine for automatic processing but very bad for presentation to 109 humans, specially if they are large. Most people find them too low- 110 level. 112 To conclude, let us note that RFC 4006 [7] uses a list of tuples, 113 each tuple being a transition. Although the (informal) syntax it 114 uses is not parsable by a program, the idea behind it is close from 115 the Cosmogol language. 117 3. Terminology 119 TODO: because of the state of this document, some choices are not 120 final. Every time you see the word ALTERNATIVE in uppercase, it 121 means several possible choices are listed. 123 The terminology of state machines is not perfectly standard. We use 124 here the words: 126 o state, 128 o message, the condition of a transition, 130 o action, performed after the transition. 132 The Cosmogol language contains declarations, assignments and 133 transitions. A declaration announces that a name will be used for 134 either a message, a state or an action. An assignment binds a value 135 to a variable. 137 A transition is described by the name of the message, the names of 138 the current and next state and an optional action. They are the 139 heart of the Cosmogol language: in Cosmogol, a state machine is a 140 list of transitions. 142 A processor is a program that processes Cosmogol files. It can be 143 validating or not. Any processor MUST check the syntax of the file. 144 A validating processor MUST perform the checks described in 145 Section 5. 147 In addition to the checks, a processor MAY perform other tasks such 148 as translating to another format, for instance Graphviz [9]. 150 TODO: some way to modularize state machines? For instance, X509 151 checking is described by several SM. 153 4. Grammar 155 Here is the grammar of Cosmogol, using ABNF [2] 157 state-machine = 1*(statement / (*comment-wsp)) 159 statement = (declaration / transition / assignment) 160 *comment-wsp ";" *comment-wsp 162 colon = *comment-wsp ":" *comment-wsp 163 comma = *comment-wsp "," *comment-wsp 164 equal = *comment-wsp "=" *comment-wsp 165 arrow = *comment-wsp "->" *comment-wsp 167 declaration = names colon value 168 ; ALTERNATIVE: indicate the possible values in the grammar: 169 ; declaration = names colon type 170 ; type = "state" / "message" / "action" 172 assignment = name equal value 174 names = name *(comma name) 176 name = quoted-name / regular-identifier 178 quoted-name = DQUOTE 1*(identifier-chars) DQUOTE 180 ; TODO: this grammar allows identifiers like foo----bar 181 ; (several dashes). Do we really want it? 182 regular-identifier = 183 ALPHA / 184 (ALPHA *(ALPHA / DIGIT / "-") (ALPHA / DIGIT)) 186 transition = current-states colon 187 messages arrow next-state 188 [colon action] 190 ; ALTERNATIVE : some people prefer to put the message first: 191 ;transition = message colon 192 ; current-state arrow next-state 193 ; [colon action] 195 ; ALTERNATIVE: some people prefer to see the current-state and 196 ; the message grouped together: 197 ;transition = left-paren current-state comma message right-paren 198 ; arrow next-state 199 ; [colon action] 200 ; ALTERNATIVE: allow some grouping, for instance: 201 ; Signal1: 202 ; IDLE -> BUSY: 203 ; connectSubscriber; 204 ; CONNECTING -> DISCONNECTING: 205 ; disconnectSubscriber 206 ; # Henk-Jan van Tuyl 208 ; ALTERNATIVE: allow more than one action, comma-separated 209 ; Marc Petit-Huguenin 211 current-states = name *(comma name) 212 messages = name *(comma name) 213 next-state = name 214 action = name 216 value = regular-identifier / quoted-name 218 identifier-chars = ALPHA / DIGIT / 219 "-" / "_" / "'" / "," / ";" / SP 220 ; All letters and digits and 221 ; some (a bit arbitrary) chars 223 comment = "#" *(WSP / VCHAR) CRLF 225 comment-nl = comment / CRLF 227 comment-wsp = *(WSP / comment-nl) 229 5. Semantics 231 A validating processor MUST perform all these checks. 233 Every message, state and action MUST be declared. The possible 234 values for the right side of a declaration are: 236 o MESSAGE 238 o STATE 240 o ACTION 242 The order between statements (transitions, declarations and 243 assignments) has no meaning. For instance, the declaration of a 244 message can takes place after its use in a transition. 246 All names are case-sensitive. ALTERNATIVE: make them case- 247 insensitive, which is possible since everything is in US-ASCII. 249 TODO: should we document naming *conventions*, such as "States in 250 uppercase, messages in capitalized"? 252 Assignments are only possible to pre-defined variables. No 253 assignment is mandatory. The variables are: 255 o Title (used for some displays) 257 o Initial (to indicate the initial state; if this variable is 258 assigned, every state MUST be reachable - may be indirectly - from 259 the initial state) 261 o Final (to indicate the final state; if this variable is assigned, 262 this final state MUST be reachable - may be indirectly - from 263 every state) 265 When there are several current states indicated, they must be 266 interpreted as a set. For every member of the set, the message yield 267 to the next state. Same thing when there are several messages. This 268 allows some grouping of similar transitions. So, the following state 269 machine: 271 Waiting, End: timeout, user-cancel, atomic-war -> Start; 273 is to be interpreted as completely equivalent to: 275 Waiting: timeout -> Start; 276 End: timeout -> Start; 277 Waiting: user-cancel -> Start; 278 End: user-cancel -> Start; 279 Waiting: atomic-war -> Start; 280 End: atomic-war -> Start; 282 The state machine MUST be deterministic, that is for every couple 283 (current state, message), there must be only one output (next state 284 and optional action). 286 Besides the "Initial" variable mentioned above Paragraph 2, a 287 processor may provide a mean to the user to declare (may be on the 288 command line) a state as the start of the machine and the processor 289 may check that every other state is reachable from this state, as if 290 it were declared as "Initial". Same thing for the "Final" state. 292 A processor may provide a flag to require that the state machine is 293 complete, that is every transition must be explicitely listed. 295 6. Internationalisation considerations 297 The character set of the language is US-ASCII only, for conformance 298 with [4], section 2.1. This reflects the fact that RFC must be 299 written in english (TODO: something which does not seem to be 300 documented anywhere). 302 7. IANA Considerations 304 None 306 8. Security Considerations 308 Implementors of state machines are warned to pay attention to the 309 default case, the one for which there is no explicitely listed 310 transition. 312 ALTERNATIVE: force every transition to be declared. This is believed 313 to be too demanding for large SM. 315 9. References 317 9.1. Normative References 319 [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement 320 Levels", BCP 14, RFC 2119, March 1997. 322 [2] Crocker, D., Ed. and P. Overell, "Augmented BNF for Syntax 323 Specifications: ABNF", RFC 4234, October 2005. 325 9.2. Informative References 327 [3] Postel, J., "Transmission Control Protocol", STD 7, RFC 793, 328 September 1981. 330 [4] Bradner, S., "The Internet Standards Process -- Revision 3", 331 BCP 9, RFC 2026, October 1996. 333 [5] Scott, G., "Guide for Internet Standards Writers", BCP 22, 334 RFC 2360, June 1998. 336 [6] Hollenbeck, S., "Extensible Provisioning Protocol (EPP)", 337 RFC 3730, March 2004. 339 [7] Hakala, H., Mattila, L., Koskinen, J-P., Stura, M., and J. 340 Loughney, "Diameter Credit-Control Application", RFC 4006, 341 August 2005. 343 [8] Kohler, E., Handley, M., and S. Floyd, "Datagram Congestion 344 Control Protocol (DCCP)", RFC 4340, March 2006. 346 [9] AT&T Research, "Graphviz, Graph Visualization Software", 347 December 2004, . 349 [10] Rapp, C., "The State Machine Compiler", January 2000, 350 . 352 [11] Thurston, A., "Ragel State Machine Compiler", August 2006, 353 . 355 [12] "FSMLang", September 2006, . 357 [13] Tels, "Graph::Easy", March 2006, 358 . 360 URIs 362 [14] 364 Appendix A. Examples 366 The TCP state machine, from RFC 793 [3]. 368 # The TCP state machine. RFC 793 3.2 "Terminology" 370 Title = "Transmission Control Protocol"; 372 SYN-RCVD, SYN-SENT, FIN-WAIT-1, FIN-WAIT-2, ESTAB, 373 CLOSING, TIME-WAIT, CLOSED, CLOSE-WAIT, 374 LISTEN, LAST-ACK : STATE; 376 CLOSE, passive-OPEN, active-OPEN , 377 rcv-SYN, rcv-ACK-of-FIN, rcv-ACK-of-SYN, rcv-SYN-ACK, 378 rcv-FIN, SEND, Timeout : MESSAGE; 380 LISTEN : CLOSE -> CLOSED : Delete-TCB ; 381 # ALTERNATIVE syntax: 382 # CLOSE: LISTEN -> CLOSED : Delete-TCB ; 383 # ALTERNATIVE syntax: 384 # (LISTEN, CLOSE) -> CLOSED : Delete-TCB ; 386 CLOSED : passive-OPEN -> LISTEN : Create-TCB; 388 LISTEN : rcv-SYN -> SYN-RCVD; 390 SYN-RCVD : CLOSE -> FIN-WAIT-1; 392 FIN-WAIT-1: rcv-ACK-of-FIN -> FIN-WAIT-2; 394 FIN-WAIT-1: rcv-FIN -> CLOSING; 396 FIN-WAIT-2 : rcv-FIN -> TIME-WAIT; 398 CLOSING : rcv-ACK-of-FIN -> TIME-WAIT; 400 CLOSED : active-OPEN -> SYN-SENT; 402 LISTEN : SEND -> SYN-SENT; 404 SYN-SENT : rcv-SYN -> SYN-RCVD; 406 SYN-RCVD : rcv-ACK-of-SYN -> ESTAB; 408 SYN-SENT : rcv-SYN-ACK-> ESTAB; 410 ESTAB : CLOSE -> FIN-WAIT-1; 411 ESTAB : rcv-FIN -> CLOSE-WAIT; 413 CLOSE-WAIT : CLOSE -> LAST-ACK; 415 TIME-WAIT : Timeout -> CLOSED; 417 LAST-ACK : rcv-ACK-of-FIN -> CLOSED; 419 The EPP state machine, from RFC 3730 [6]. 421 # Extensible Provisioning Protocol (EPP) 423 "Waiting for client", "Prepare greeting", "End session", 424 "Waiting for client authentication", "Processing login", 425 "Prepare fail response", "Prepare response", 426 "Waiting for command", "Processing command": STATE; 428 "Connected or hello", "Close connection or idle", 429 "Send greeting", "login received", "Send response", 430 Timeout, "Auth fail", 431 "Auth OK", "Command received", 432 "Command processed", "Send X5xx response", 433 "Send 2501 response": MESSAGE; 435 Initial = "Waiting for client"; 437 "Waiting for client": "Connected or hello" -> "Prepare greeting"; 439 "End session" : "Close connection or idle" -> 440 "Waiting for client"; 442 "Prepare greeting": "Send greeting"-> 443 "Waiting for client authentication"; 445 "Waiting for client authentication":Timeout : -> "End session"; 447 "Waiting for client authentication" : "login received"-> 448 "Processing login"; 450 "Processing login": "Auth fail" -> "Prepare fail response"; 452 "Prepare fail response":"Send response" -> 453 "Waiting for client authentication"; 455 "Processing login": "Auth OK" -> "Waiting for command"; 457 "Waiting for command": Timeout -> "End session"; 458 "Prepare response" : "Send response" -> "Waiting for command"; 460 "Processing command" : "Command processed" -> 461 "Prepare response"; 463 "Waiting for command" : "Command received" -> 464 "Processing command"; 466 "Prepare response" : "Send X5xx response" -> "End session"; 468 "Prepare fail response" : "Send 2501 response"-> 469 "End session"; 471 The DCCP state machine, from RFC 4340 [8]. 473 # RFC 4340, 8.4. "DCCP State Diagram" 475 CLOSED, LISTEN, REQUEST, RESPOND, OPEN, PARTOPEN, CLOSING, TIMEWAIT, 476 CLOSEREQ : STATE; 478 Passive-open, Active-open, Receive-ack, Receive-reset, 479 Server-active-close, Active-close, Receive-packet, 480 Receive-response, 481 Receive-request, Timer-expires, Receive-close : MESSAGE; 483 CLOSED : Passive-open ->LISTEN; 485 LISTEN : Receive-request ->RESPOND; 487 RESPOND: Receive-ack ->OPEN; 489 CLOSING : Receive-reset ->TIMEWAIT; 491 OPEN : Server-active-close->CLOSEREQ; 493 CLOSEREQ : Receive-close ->CLOSED; 495 OPEN : Active-close ->CLOSING; 497 REQUEST : Receive-response->PARTOPEN; 499 PARTOPEN : Receive-packet ->OPEN; 501 CLOSED : Active-open->REQUEST; 503 TIMEWAIT : Timer-expires -> CLOSED; 505 OPEN: Receive-close ->CLOSED; 507 Appendix B. First implementation 509 The first implementation of the Cosmogol language can be found at 510 . It is a processor which is able to check 511 state machines specified in Cosmogol and to translate them into 512 Graphviz. 514 Appendix C. Related work 516 All of them are interesting back-ends for a Cosmogol processor: 518 o Graphviz [9] is a widely-used language to describe graphs. It has 519 been used for state machines such as TCP [14]. But it is more 520 presentation-oriented, you cannot restrict it to just the 521 description. Consequently, there are currently no tools to check, 522 for instance the determinism. 524 o The Perl module Graph::Easy [13] shares most of the aims of 525 Graphviz. It is also oriented towards presentation. 527 o SMC [10], Ragel [11] and FSMlang [12] are more oriented towards 528 code-generation. 530 Appendix D. Changes 532 D.1. Changes from -00 534 o The syntax of a transition is different: the current-state is now 535 the first item, and not the message. There was a clear consensus 536 among the reviewers on this change. 538 o Several messages are now allowed in a transition, to indicate a 539 set of messages. Same thing for the current state. 541 o Several bug fixes in the grammar. 543 Appendix E. Acknowledgements 545 Significant contributions have been made by Pierre Beyssac, Emmanuel 546 Chantreau, Frank Ellermann, Kim Minh Kaplan, Thomas Quinot, Bertrand 547 Petit, Phil Regnauld, Mohsen Souissi and Olivier Ricou. 549 Author's Address 551 Stephane Bortzmeyer 552 AFNIC 553 Immeuble International 554 Saint-Quentin-en-Yvelines 78181 555 France 557 Phone: +33 1 39 30 83 46 558 Email: bortzmeyer+ietf@nic.fr 559 URI: http://www.afnic.fr/ 561 Full Copyright Statement 563 Copyright (C) The Internet Society (2006). 565 This document is subject to the rights, licenses and restrictions 566 contained in BCP 78, and except as set forth therein, the authors 567 retain all their rights. 569 This document and the information contained herein are provided on an 570 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 571 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 572 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 573 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 574 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 575 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 577 Intellectual Property 579 The IETF takes no position regarding the validity or scope of any 580 Intellectual Property Rights or other rights that might be claimed to 581 pertain to the implementation or use of the technology described in 582 this document or the extent to which any license under such rights 583 might or might not be available; nor does it represent that it has 584 made any independent effort to identify any such rights. Information 585 on the procedures with respect to rights in RFC documents can be 586 found in BCP 78 and BCP 79. 588 Copies of IPR disclosures made to the IETF Secretariat and any 589 assurances of licenses to be made available, or the result of an 590 attempt made to obtain a general license or permission for the use of 591 such proprietary rights by implementers or users of this 592 specification can be obtained from the IETF on-line IPR repository at 593 http://www.ietf.org/ipr. 595 The IETF invites any interested party to bring to its attention any 596 copyrights, patents or patent applications, or other proprietary 597 rights that may cover technology that may be required to implement 598 this standard. Please address the information to the IETF at 599 ietf-ipr@ietf.org. 601 Acknowledgment 603 Funding for the RFC Editor function is provided by the IETF 604 Administrative Support Activity (IASA).