Most of the IdentityHub involves workflow-styled processes... create a
key, publish it in LDAP, set it up in a DANE, wait a while, set it up
in a server, wait a while, remove a predecessor from DANE, and many
more such actions. To coordinate such process is difficult, let alone
allow dynamic enhancements in individual identity hosting contexts.
Perpetuum presents an answer.
This is the third article in an article series On Display in which we report on the output from projects that fall under the InternetWide Umbrella of projects.
What is it?
Perpetuum, coordinates processes and generates code for them to relieve programs from the complexity of looking around for state and locks.
The processes involved are drawn as so-called Petri Nets. This is well-known mathemetical formalism, invented by Carl Petri when he was 14 years old. It is a language that expresses progressing control by passing tokens between places by transitions that "fire". When firing, a transition can start or end concurrent branches in a process, where ending concurrency comes down to the same idea as synchronising the original branches.
These diagrams can be drawn and simulated with existing graphical tools, and saved in a standardised XML format, named PNML. This is where Perpetuum sets off.
Perpetuum generates code to coordinate attempts at firing (events from the environment) and when they do, tries to cause changes by invoking a transition in underlying code. In a sense, the environment is being filtered and the application code is driven under the strict control of the Petri Net.
Design Criteria
What we wanted to achieve is to isolate the most complex part of these workflow-styled operations. Introducing a user is simple enough when all that needs to be done is add a username and a password in one database table, but in the IdentityHub it will do much more; keys must be generated for X.509 and PGP, installed in LDAP, possibly claimed in DNS and signed under DNSSEC, and various components of the infrastructure must be notified or called into action. Most processes in the IdentityHub follow a similarly complex plot; adding a member to a group involves instructing the Remote PKCS #11 component about a layer that needs to be added for that user, to give an example where the IdentityHub is more functional, but also more complex than an everage database table behind a PHP application.
The complexity of processes hits an application hard when it is distributed throughout the code. Specifically, when a bit of code needs to check if certain parts of a process have completed, and if not it needs to somehow wait for them to complete, be careful not to end up in race conditions when other threads are just finishing this work, and so on. In contrast with this, all the code dealing with concurrency and synchronisation is now captured in the Petri Net, and the application logic consists of elementary transitions that do simple, individual things. When a transition needs to make a DNS lookup, it need not know about success and failure branches, but is provided with a transition to trigger in each of these situations, as a way of feeding back to the Petri Net. (For now, this sort of data is still provided by a bit of code that is not generated. We are looking into ways of automating even that.)
Hanging over the Petri Nets is a management module. This module is manually coded, and creates new instances of a Petri Net when a new task arrives, and keeps feeding it with events to consider. It will take note of failures and may tear down Petri Nets that are finished. In future versions, it may also accommodate some form of persistency, probably by freezing Petri Net instances and storing their state in a database. This would allow for long-term processes to sit silent while awaiting a timeout, such as a renewal for a 90-day certificate.
So we have split the complexities of workflow management into three kinds of component:
- management of instances
- concurrency control, generated from Petri Nets
- application logic, processing individual short actions
Behind all this is the goal of letting the Petri Nets be the driving force for flexibility. If you are administering a network with a somewhat different topology than an application assumes, you should have the freedom to add or remove parts of the Petri Net. It is the centralisation of these aspects and their automatic generation of code that makes this doable.
Finally, having graphical tools has already given us the very big benefit of simulation runs; without having written a single line of code, we could draw a Petri Net and go through several concrete runs to test the ideas. For complex processes such as those of network protocols, this adds value in terms of understanding and debugging a process early. Having to do this after coding, and then having the code spread all over an application, is orders of magnitude more difficult.
First Releases and Field Testing
We have had a working code generator for C for a while now, and believe it is working. Since C is wide open to various program structures, we have stopped this process at the point where we believed that it would integrate well with event libraries. We have since then realised that a richer semantics (and/or programming culture) for these concepts is helpful to provide better functionality, but in C that would have been restrictive and so we chose to let others wrap more refined models around our general one. What we have done for the C model is make it highly compact, in service of embedded applications. One can easily imagine Petri Nets to respond to buttons being pressed, but only at the right times, and then whatever hardware responses to be triggered in the application logic.
Perpetuum 1.0 also generates code for Erlang, along with intensive test code to ensure that it works as it ought to. Erlang has a very strong concurrency culture of habits in the form of the OTP library, and we have striven to integrate with those habits, thus delivering a higher level of service than we felt comfortabel with in C.
The Petri Net implementation used for Erlang is utterly efficient, because it uses a single integer to store the entire state of the Petri Net. It relies on Erlang's support of arbitrarily large integers and will rescale its representation when a Petri Net run needs more tokens in a place than available at that time.
We are testing this version with our own application for Kerberos Realm Crossover which involves a client process talking to a server process, both heavily leaning on DNS and DNSSEC, as well as some public key crypto, for security. Note how the individual transitions call for actions in the application logic that are all relatively simple and, most importantly, isolated from each other but for variable transport; things like sending a DNS query, or things like processing a signature as valid or invalid. This isolation and simplicity has been our purpose all along.
Based on this, we are learning a few lessons that will influence the next release. Things like asynchronous signalling without any feedback, which is not a desirable model; instead, we will be sending feedback to the management process that initiated the Petri Net. We are also learning that some events are triggered by the controller and others by a callback to the application logic. For now, the management process passes a "success" and "failure" event to the application logic, so that it may act on the response by triggering one of these without knowledge of the diagram. Ideally, we would have that encoded in the Petri Net or an accompanying table, so even the management process need not be aware of this ongoing work, or at least it might have a way of inferring this data from the automatically generated code.
Future Dreams
In some future version, we hope to have one or more ways of composing Petri Nets, so it will be possible to describe partial views on a problem; this might be useful for pluggable components, but also to specify client and server separately and see their interaction in a composed system.
A technical facility that we have designed but not yet implemented, is dealing with inhibitor arcs with multiplicity. This takes a slightly different path than our current bitfield vector model.
On top of that, we have several more computational wishes, some of which are:
- persistency and process hibernation
- ways to automate relations between transitions
We do not need that for our current work, which is a field test with KXOVER.
Getting Started
Although 1.0 is stable, it is not going to be an easy ride. Please be prepared to use your developer skills if you want to try it, and please realise that we too are now running our first field test. Having said that, we would love to get your input in this stage. Others might want to await the next release, which will also be announced on this blog.
If you feel like diving in, please head for these documents first:
- Project README
- Quickstart to play around
- Tools, or just follow our advise and install GreatSPN
- USING it for Designs
- Proper INSTALL
- Testing for an impression of what the code can do, and the test code to inspect how it might be done (in Erlang).
This is definitely going to take you some getting used to. If you are not accustomed to Erlang, you probably want to limit yourself to the C generated code, and integrate with your customary event loop. We hope that the documentation is up to that, but are open to your feedback and/or pull requests that may help people getting started with what will be a new approach for most programmers.
We are also quite keen on developments in formal model checking. Rick and Adriaan both have a background in it, but neither have this aspect high on their agenda at the moment. Do send us your ideas though, we are most curious!
Wild Ideas for Applications
The application area for Perpetuum is huge. One application might be an open source program driver for a washing machine. Very few tweaks are made in this mundane application, but a few interesting ones could be imagined; solar panels might be used for hot fill, for the soapy wash run but not for the initial rinse; signals might be sent to our preference of alarming device when washing has finished; and we might even respond to room temperature to send a reminder at the most energy-efficient time for running your laundry.
We are also playing with the idea of modelling a protocol implementation for TLS with Petri Nets. This might be a nice test for our ideas of Composition of Petri Nets. Composition would allow partial protocols drawn in individual diagrams, and them being composed on such linking aspects as matching transition names. This might allow for the individual specification of involvement with various stages of the protocol. When a CipherSuite cannot function in a given setting, it would simply remove the token that held it alive.
Petri Nets have the (at least theoretic) potential of model checking. Some checks are possible in general, some require a special class of Petri Nets, and some will run as long as the time is taken for a brute force over all possible markings.
Image credit: Bluecmd at WikiMedia Commons
Go Top