Hi there, I'd like to tell you about tools for
disambiguating RFCs. This is work led
by our grad student Jane Yen, along with Ramesh
Govindan and myself Bharath Raghavan at UFC.
In nearly every talk I give I somehow keep coming
back to September 1981. This is when
the foundational protocols of the internet that
are still in use today were defined and
they were written in English and manifested in
the world in Clark's phrase "through
rough consensus and running code." So what I want
to ask is what makes protocols special?
Since then we have grappled with something
fundamental about network protocols. They
are specified in English, implemented in code
through interpretation of that English prose,
coded typically in a relatively low level
language, but have a fundamental intent to
interoperate with other implementations. Those
other implementations went through the same
process, interpretation by a person who scrutinized
that English text or not, and wrote an
implementation
that reflected their best guess as to the intent
of the spec author. And yet these implementations
were written separate in time and space from one
another and from the specification, something
that rarely takes place in other domains of
software development. And from that we want
to achieve all the different properties. We've
struggled for a long time to achieve all of
them. Properties such as security and interoperability,
flexibility, scalability, correctness, and
extensibility. And while this is sometimes due to
the design and specification process,
it's often because of implementations with issues
being discovered incrementally over
time. And those implementations get improved, the
specifications get improved, and then
around we go again. But it's not clear that this
is fundamental. And so what we might
do is consider different options that we have in
protocol specification and implementation.
How easy are they to specify and how easy are
they to implement? And not just implement
badly but with all of the properties that we seek.
The place we began in our work is
the place that we've been some time, that the
specification is written in English and
a person somewhere, a human must read the spec,
interpret it correctly, and then implement
it correctly. Many have rightly observed that
this opens the door to many possible mistakes.
So the natural option is to formalize the
specification process. Many languages and
tools for formal specification of software
generally and protocol specifically have been
developed. And these formal specs enable a degree
of certainty about what the spec author
meant. But they're a pain to write and to read,
even for specialists. And so they've
been considered really only worth it for the most
safety critical applications. And then
one can consider, well, if we have this formal
specification, we can produce an automated
implementation. A crisp enough formal
specification should be easy to convert to code.
So if you're
going to go to the trouble to write a formal spec,
you might as well automate the code
generation. But formal specs have seen little
adoption, and we're still writing protocol
specifications in English. So our work, the first
piece of which is appearing in SIGCOMM
this year, takes a small step toward filling in
the missing quadrant, taking RFCs, identifying
ambiguities in the spec text, and then after the
author fixes those, attempting to auto
generate code straight from English. Our approach
is built upon a set of concepts and techniques
in natural language processing known as combinatorial
categorical grammar, which is a way to do
what's known as semantic parsing, how to decompose
a sentence into sensible units. Now we're
not natural language processing experts. We're
networking people. So really what we wanted
to do is take these techniques that have been
developed in NLP and apply them to this context.
We use this grammar based approach rather than a
more popular deep neural net based
approach because we wish to retain the structure
of the text so that we can figure out whether
multiple interpretations of a sentence are valid
and how those should be fixed, if at
all. So what kind of text are we talking about?
Well, we want to be able to process excellent
chunks of text like this. Or this. So we built a
tool called Sage that attempts to identify
ambiguity in RFC text, taking advantage of their
structured nature and flag sentences
that are ambiguous. Then for limited RFC features
that we support, we take this disambiguated
text and convert it directly into protocol code.
This is a very early stage tool. It's
not ready for wider use. So really part of our
motivation in presenting it to you all
is to learn from the community and identify what
are next steps of where we want to extend
it to support. So in addition to parsing prose, RFCs
have many types of structured text. Sage
currently supports interpretation of packet
headers and pseudocode, some aspects of state
and session management, but does not support
state machines or algorithm specifications.
The latter are absolutely needed to support more
advanced protocols. And so I come back
to where I began, which is what makes protocols
special? They're essential to everything we
do today and have to work in contexts far outside
their original intention. However,
because as a community there exists standardized
practices for the development of RFCs, what
I'd like to pose for discussion is how the
process for standardizing RFCs might integrate
semi-automated tools, like say a future version
of Sage, to improve specifications and to
to produce baseline implementations.
Thank you.