A FINITE-STATE MACHINE APPROACH FOR MODELING AND ANALYZING RESTFUL SYSTEMS
Keywords:
representational state transfer, World Wide Web, software architectural styles, formal model, nite-state machines, hypermediaAbstract
Representational State Transfer (REST), as an architectural style for distributed hyper- media systems, enables scalable operation of the World Wide Web and is the foundation for its future evolution. However, although described over 10 years ago, no formal model for representing RESTful systems exists that is comprehensive in following REST prin- ciples, intuitive to Web engineers and researchers alike, and oers practical development guidelines. The lack of such formal models has hindered understanding of both the REST architectural style and the Web architecture, consequently limiting Web engineering ad- vancement. In this paper we present a generic model of RESTful systems based on a nite-state machine formalism. We show that the model enables intuitive formalization of REST design principles, including uniform interface, stateless client-server operation, and code-on-demand execution. Furthermore, we describe the model's mapping to a system-level view of operation and apply the model to an example Web application and several real-word Web applications. Finally, we explore the practical challenges and benets of using the model in the eld of Web engineering, ranging from better understanding of REST to designing frameworks for RESTful system development.
Downloads
References
I. Jacobs and N. Walsh (2004), Architecture of the World Wide Web, Volume One, W3C Recom-
mendation, WWW consortium (2004) http://www.w3.org/TR/webarch/.
R.T. Fielding and R.N. Taylor (2002), Principled design of the modern Web architecture, ACM
Transactions on Internet Technology, Vol.2, No.2, pp. 115-150.
L. Dusseault and J. Snell (2010), PATCH Method for HTTP, Proposed standard, Internet Engi-
neering Task Force (IETF) http://tools.ietf.org/html/rfc5789.
F. Rosenberg, F. Curbera, M.J. Duftler and R. Khalaf (2008), Composing RESTful Services and
Collaborative Work
ows: A Lightweight Approach, IEEE Internet computing, Vol.12, No.5, pp.
-31.
R. Alarcon and E. Wilde (2010), Linking Data from RESTful Services, 3rd InternationalWorkshop
on Linked Data on the Web, Raleigh, North Carolina, USA.
V. Trifa, D. Guinard, P. Bolliger and S. Wieland (2010), Design of a Web-based Distributed
Location-Aware Infrastructure for Mobile Devices, 1st IEEE International Workshop on the Web
of Things, Mannheim, Germany, pp. 714-719.
B. Fitzpatrick, B. Slatkin and M. Atkins (2010), PubSubHubbub protocol, http://pubsubhubbub.
googlecode.com/svn/trunk/pubsubhubbub-core-0.3.html.
R.T. Fielding, J. Gettys, J.C. Mogul, H.F. Nielsen, L. Masinter, P.J. Leach and T. Berners-
Lee (eds.) (1999), RFC 2616: Hypertext Transfer Protocol { HTTP/1.1, IETF draft standard,
http://www.ietf.org/rfc/rfc2616.txt.
I. Hickson (ed.) (2011), HTML5 - A vocabulary and associated APIs for HTML and XHTML,
W3C Editor's draft, http://dev.w3.org/html5/spec/.
L. Dusseault (ed.) (2007), HTTP Extensions for Web Distributed Authoring and Versioning (Web-
DAV), IETF proposed standard, http://tools.ietf.org/html/rfc4918.
J. Gregorio and B. de hOra (eds.) (2007), The Atom Publishing Protocol, IETF proposed standard,
http://www.ietf.org/rfc/rfc5023.txt
M. Belshe and R. Peon (eds.) (2011), SPDY Protocol, http://mbelshe.github.com/
SPDY-Specification/draft-mbelshe-spdy-00.xml.
Z. Shelby, B. Frank and D. Sturek (eds.) (2010), Constrained Application Protocol (CoAP), IETF
draft http://tools.ietf.org/html/draft-shelby-core-coap-01.
R. Sayre (2005), Atom: The standard in syndication, IEEE Internet Computing, Vol.9, No.4, pp.
-78.
D. Crockford (ed.) (2006), The application/json Media Type for JavaScript Object Notation
(JSON), IETF draft, http://tools.ietf.org/html/rfc4627.
J.A. Larson (2003), VoiceXML and the W3C Speech Interface Framework, IEEE Multimedia,
Vol.10, No.4, pp. 91-93.
D. Beckett (2004), RDF/XML Syntax Speci cation, W3C Recommendation, http://www.w3.org/
TR/rdf-syntax-grammar/
C. Pautasso and E. Wilde (2010), RESTful web services: principles, patterns, emerging tech-
nologies, 19th international conference on World wide web (WWW '10), Raleigh, NC, USA, pp.
-1360.
R.T. Fielding (2002), waka: A replacement for HTTP, ApacheCon 2002, http://gbiv.com/
protocols/waka/200211_fielding_apachecon.ppt
N. Koch (2000), Software Engineering for Adaptive Hypermedia Systems: Reference Model, Mod-
eling Techniques and Development Process, Ph.D. dissertation, Ludwig-Maximilians-University of
Munich, Germany.
http://tech.groups.yahoo.com/group/rest-discuss/message/17571
F. Fernandez and J. Navon (2010), Towards a Practical Model to Facilitate Reasoning about REST
Extensions and Reuse, 1st International Workshop on RESTful Design, Raleigh, North Carolina,
pp. 31-38.
R.T. Fielding (2010), ACTION-434: Some notes on organizing discussion on WebApps architec-
ture, W3C TAG mailing list, http://lists.w3.org/Archives/Public/www-tag/2010Oct/0100.
html.
http://www.w3.org/2001/tag/doc/IdentifyingApplicationState-20110930.html
J. Kemp (2010), AWWW and the Web interaction model, W3C TAG mailing list, http://lists.
w3.org/Archives/Public/www-tag/2010Jun/0034.
J. Rees (2010), ACTION-434: Some notes on organizing discussion on WebApps architecture,
W3C TAG mailing list, http://lists.w3.org/Archives/Public/www-tag/2010Oct/0061.html.
J. Ousterhout and E. Stratmann (2010), Managing state for Ajax-driven web components, 2010
USENIX conference on Web application development, Berkeley, CA, USA, pp. 7-7.
A. Bohannon and B.C. Pierce (2010), Featherweight Firefox: formalizing the core of a web browser,
USENIX conference on Web application development, Berkeley, CA, USA, pp. 11-11.
ISSUE-60: Web Application State Management, W3C TAG Issues list, http://www.w3.org/2001/
tag/group/track/issues/60.
S. Vinoski (2008), RESTful Web Services Development Checklist, IEEE Internet Computing,
Vol.12, No.6, pp. 96-95, (2008)
C. Pautasso (2009), RESTful Web service composition with BPEL for REST, Data & Knowledge
Engineering, Vol.68, No.9, pp. 851-866.
J. Gregorio (2007), Do we need WADL?, http://bitworking.org/news/193/Do-we-need-WADL
J.E. Hopcroft and J.D. Ullman (1979), Introduction to Automata Theory, Languages, and Com-
putation, Addison-Wesley Publishing, Reading Massachusetts.
T. Berners-Lee and N. Mendelsohn (2006), The Rule of Least Power, W3C TAG Finding, http:
//www.w3.org/2001/tag/doc/leastPower.html.
I. Zuzak, I. Budiselic, G. Delac (2011), Formal Modeling of RESTful Systems Using Finite-State
Machines, 11th International Conference on Web Engineering, Paphos, Cyprus, pp. 346-360.
R.N. Taylor, N. Medvidovic and E.M. Dashofy (2009), Software Architecture: Foundations, Theory,
and Practice, Wiley Publishing.
N.R. Mehta (2004), Composing style-based software architectures from architectural primitives,
Ph.D. dissertation, University of Southern California, California, USA.
A.G. Hernandez and M.N. Moreno Garcia (2010), A Formal De nition of RESTful Semantic Web
Services, 1st International Workshop on RESTful Design, Raleigh, North Carolina, pp. 39-45.
G. Decker, A. Luders, H. Overdick, K. Schlichting and M. Weske (2009), RESTful Petri Net
Execution, Web Services and Formal Methods, Springer-Verlag Berlin, Heidelberg, pp. 73-87.
L. Li and W. Chou (2011), Design and Describe REST API without Violating REST: A Petri Net
Based Approach, International Conference on Web Services, Washington, DC, USA, pp. 508-515.
R. Alarcon, E. Wilde, J. Bellido (2010), Hypermedia-driven RESTful Service Composition, 6th
Workshop on Engineering Service-Oriented Applications, San Francisco, California.
M.C. Ferreira de Oliveira, M.A. Santos Turine and P.C. Masiero (2001), A statechart based model
for hypermedia applications, ACM Transactions on Information Systems, Vol.19, No.1, pp. 28-52.
I. Porres and I. Rauf (2011), Modeling Behavioral RESTful Web Service Interfaces in UML, 26th
Annual ACM Symposium on Applied Computing Track on Service Oriented Architectures and
Programming, TaiChung, Taiwan, pp. 1598-1605.
M. Laitkorpi, P. Selonen and T. Systa (2009), Towards a Model-Driven Process for Designing
ReSTful Web Services, International Conference on Web Services, Los Angeles, CA, USA, pp.
{180.
S. Perez, F. Durao, S. Melia, P. Dolog and O. Diaz (2010), RESTful, Resource-Oriented Archi-
tectures: A Model-Driven Approach, 1st International Symposium on Web Intelligent Systems &
Services, Hong Kong, China, pp. 282-294.
S. Schreier (2011), Modeling RESTful applications, Second International Workshop on RESTful
Design, Hyderabad, India, pp. 15-21.
S. Charlton (2010), Building a RESTful Hypermedia Agent, Part 1., http://www.stucharlton.
com/blog/archives/2010/03/building-a-restful-hypermedia.
M.H. Alal , J.R. Cordy and T.R. Dean (2009), Modeling methods for web application veri cation
and testing: state of the art., Software Testing, Veri cation & Reliability archive, Vol.19, No.4,
pp. 265-296, John Wiley and Sons Ltd. Chichester, UK.
J. Dargham and S. Al-Nasrawi (2006), FSM Behavioral Modeling Approach for Hypermedia Web
Applications: FBM-HWA Approach, Advanced International Conference on Telecommunications
and International Conference on Internet and Web Applications and Services, Guadeloupe, French
Caribbean, pp. 199-199.
P.D. Stotts, R. Furuta and C.R. Cabarrus (1998), Hyperdocuments as Automata: Veri cation of
Trace-Based Properties by Model Checking, ACM Transactions on Information Systems, Vol.16,
No.1, pp. 1-30.
X. Zhao, E. Liu and G.J. Clapworthy (2011), A Two-Stage RESTful Web Service Composition
Method Based on Linear Logic, 9th European Conference on Web Services, Lugano, Switzerland.
B. Kamara, G. von Bochmann, M. Dincturk, G.V. Jourdan, I. Onut (2011), A Strategy for E-
cient Crawling of Rich Internet Applications, 11th International Conference on Web Engineering,
Paphos, Cyprus, pp. 74-89.
Twitter API documentation, https://dev.twitter.com/docs
T. Berners-Lee, R. Fielding, L. Masinter (2005), Uniform Resource Identi er (URI): Generic
Syntax,IETF standard, http://tools.ietf.org/html/rfc3986
Internet Assigned Numbers Authority - Registered Media Types, http://www.iana.org/
assignments/media-types/index.html.
J. Gregorio, R. Fielding, M. Hadley, M. Nottingham and D. Orchard (eds.) (2011), URI Template,
IETF draft, http://tools.ietf.org/html/draft-gregorio-uritemplate.
M. Chatti, M. Jarke, Z. Wang and M. Specht (2009), SMashup Personal Learning Environments,
nd Workshop on Mash-Up Personal Learning Environments (MUPPLE'09), Nice, France, pp.
-14.
GitHub API documentation, http://developer.github.com/v3/.
M. Trybulec (2009), Labelled State Transition Systems, Formalized mathematics, Vol.17, No.2, pp.
-171.
E. Castellani (2003), Symmetry and equivalence, Symmetries in Physics Philosophical Re
ections,
Cambridge University Press, pp. 425-436.
J. Webber, S. Parastatidis and I. Robinson (2010), REST in Practice: Hypermedia and Systems
Architecture, O'Reilly Media.
I. Robinson (2011), RESTful domain application protocols, REST: From research to practice,
Springer, pp. 61-92.
R. France and B. Rumpe (2007), Model-driven development of complex software: A research
roadmap, Future of Software Engineering, IEEE Computer Society, pp. 37-54.
M. Han and C. Hofmeister (2006), Modeling and veri cation of adaptive navigation in web appli-
cations, 6th international conference on Web engineering (ICWE '06), Palo Alto, California, USA,
pp. 329-336.
E. Di Sciascio, F.M. Donini, M. Mongiello and G. Piscitelli (2002) AnWeb: a system for automatic
support to web application veri cation, 14th international conference on Software engineering and
knowledge engineering, Ischia, Italy, pp. 609-616.
F.M. Donini, M. Mongiello, M. Ruta and R. Totaro (2006), A Model Checking-based Method for
Verifying Web Application Design, Electronic Notes in Theoretical Computer Science, Vol.151,
No.2, pp. 19-32.
R. Fielding (2008), REST APIs must be hypertext-driven, http://roy.gbiv.com/untangled/
/rest-apis-must-be-hypertext-driven.
M. Broy (2011), Can Practitioners Neglect Theory and Theoreticians Neglect Practice?, IEEE
Computer, Vol.44, No.10, pp. 19-24.
S. Parastatidis, J. Webber, G. Silveira and I.S. Robinson (2010), The role of hypermedia in dis-
tributed system development, 1st International Workshop on RESTful Design, Raleigh, North
Carolina, pp. 16-22.
The RESTAgent library, http://restagent.codeplex.com/
B. Lerner, B. Burg, H. Venter and W. Schulte (2011), C3: An Experimental, Extensible, Recon-
gurable Platform for HTML-based Applications, 2nd USENIX Conference on Web Application
Development.
