“ eat ”
<$End> “Lions” “ eat ” < P reyL ist> <$End> “Lions” “ eat ”
Figure 2.7: A sample expansion of a string in L { G m cej ungie). replaced by the RHS of the production, which has the effect of swapping th e comma for an “and” . Note th a t the production will only m atch at the end ®f the string. The phrase structure gram m ar provides us w ith two facilities: the ability to define replacement rules; and the ability to provide a set of alternative paths to use during generation. It may not be immediately clear how a phrase structure gram m ar can be used to describe a network protocol. However, as we will discover, we can make phrase structure grammars more useful by limiting their syntax.
2 .2 .3
P o w er T h r o u g h S im p lific a tio n
Formal grammars, as expressed with a phrase structure grammar, are extremely pow erful. According to [26], it can be proven th a t there is no (known) stronger m ethod for generating sets. Having said th at, the complete phrase structure gram m ar th a t we discussed is computationally unwieldy: in its full form, a phrase structure gramm ar is too complex to transform into a parser. We would like to simplify the phrase structure gram m ar to the point where we can run a transform on it and build a parser. W hen a lim itation is placed on the phrase structure grammar, th a t reduces the set of languages it can be used to describe, we say th a t we have lessened the expressiveness of the grammar. We wish to limit the complexity of the phrase structure gram m ar to the point where it is possible to
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
2.2. G ram m ars
26
transform it into a parser, while keeping it sufficiently expressive th a t we can still describe network protocols. In the academic cannon, there are standard lim itations th a t can be placed on a phrase structure grammar, to allow for the easy creation of parsers. The limitations are organised into what is known as the Chomsky Hierarchy[26], which orders formal grammars from “most expressive” to “least expressive” . Each limitation is assigned a number, and, in most cases, a name.
T yp e-0 Type-0 gram m ars are the fully featured phrase structure gramm ar th a t we have al ready discussed. There are no limitations on the number of symbols th a t may appear in either the left or right hand sides of the production.
Type-1: C o n te x t S en sitiv e G ram m ars Grammars are context sensitive if every production contains only one non-term inal on the LHS th a t is changed by the RHS. In other words, each rule modified one non term inal in the LHS, all other symbols in the LHS are considered context. The RHS provides the same values for each symbol of the context, and a new value for the for the modified symbol.
c l c2 T arget c3 = c l c2 Some New V alues c3
Figure 2.8: A Type-1 grammar. Rules < c l > , < c 2 > , and < c 3 > are context. Rule < T a rg e t> is changed.
Figure 2.8 provides an example of a context sensitive grammar. The special non terminal is < T a rg e t> , and the context is < c l> , < c 2 > , and < c3 > . Each of < c l> ,
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
2.2. G ram m ars
27
< c 2 > , and < c 3 > remain effectively unchanged by the rule, while < T a rg e t> is re placed by a set of new values.
Type-2: C o n te x t Free G ram m ars Context free grammars (or CFGs) have a single symbol on the LHS of a production, and an unlimited number of symbols on the RHS. This means th a t any non-term inal th a t is expanded in a context free gramm ar is completely independent of th e sur rounding symbols. Even with th e limitation of a unary LHS, context free grammars are still very expressive. They can describe gramm ars with nested elements, and offer recursion to arbitrary depths. They are often used to describe programming languages and network protocols. Because of their limitations, type-2 grammars may be parsed in linear time by finite autom ata equipped with a stack.
T ype-3: R egu lar G ram m ars Regular grammars are an even more highly constrained language. Like CFGs, regu larly grammars may only have a single non-terminal on their LHS. However, unlike any of the preceding types, their RHS is limited to containing a sequence of terminals, followed by a non-terminal. This structural limitation prevents regular grammars from generating any nested or balanced structure. W ith such a limitation, a simple finite autom ata is sufficient to represent a regular grammar.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
2.2. G ram m ars
2 .2 .4
28
T h e D ra w b a ck o f F o rm a l G ram m ars
As powerful as formal grammars are, they suffer a single drawback th a t makes them unattractive for defining protocol grammars: they require explicit enumeration of parameters. We term a parameter of a protocol to be some value th a t changes while two hosts are communicating. W hen the param eter changes, it changes how the recipient of some communication parses th a t data. Practically, protocol parameters are used to control when th e parser detects the end of a symbol. There are a number of idioms for the length of a symbol can be determined:8 1. The length of the symbol can be explicitly stated in the protocol specification. 2. The end of the symbol may be delimited by some term inal stated in the protocol specification. 3. The length of the symbol is encoded in some preceding nonterminal. We refer to the preceding symbol as the param eter. We refer to the variable-length symbol as having dynamic length. 4. The end of the symbol may be denoted by some string defined by a preceding symbol. We refer to the preceding symbol as the param eter, and the symbol whose value changes as having dynamic text. The first two idioms are perfectly compatible with formal grammars, as they can easily be stated with any grammar more complex than a regular grammar. Figure 2.9 and Figure 2.10 show each idiom. In a context free grammar, dynamic length and dynamic tex t can only be stated by exhaustively enumerating every possible param eter. If we define a length in a 8This list has been highly adapted from that supplied by Lambright in [38], which was more closely associated with datagram oriented protocols.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without perm ission.
29
2.2. G ram m ars L i s t = Thing Thing T hing Thing Thing Thing = "A" I "B" I "C"
Figure 2.9: An example of explicit length definition in a formal context free grammar. Note th at this gramm ar will m atch exactly five instances of the letters “A” , “B” , or “C”. L i s t = Thing "AXAX" Thing = "A" I "X" I T hing
Figure 2.10: An example of explicit symbol delimiter in a formal context free gram mar. Note th a t this gram m ar will m atch exactly any number of “A” and “X” , so long as the end is delimited by “AXAX” . context free grammar, we m ust list each possible length, as shown in Figure 2.11. The grammar defines < L is t> in a manner th a t allows us to correctly parse all instances of the language, but it is not scalable. Consider a scenario where we have a list th a t may contain a few thousand values. We would have to include every possible length in the grammar. The “Content-Length” held in HTTP [17] is a practical example of this type of param eter.
L is t = "0" I "1" L I "2" L L | "3" L L L L = "A" | "B" I "C"
Figure 2.11: An example of explicit length definition, for a list of variable length in a formal context free gramm ar. The same is true for dynam ic text. The dynamic text idiom involves three a definition, a variable length for the term inator.
held,and a term inator. The dehnition
symbols:
sets the text
The term inator delimits the end of the variable length held.
Figure 2.12 shows a gram m ar with the given delimiter. Even in this example, if we allow the delimiter to be any English letter, we will have 26 branches. If we also allow the delimiter to be a string of multiple letters, the size of the gram m ar will increase
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
30
2.2. G ram m ars
exponentially. The boundary delimiter of MIME [21] is a practical example of this type of parameter.
L i s t = "X" L "X" | "Y" L "Y" | "Z" L = "A" I "B" | "C" I L |
L "Z"
Figure 2.12: An example of th e dynamic tex t idiom. In each branch of the alternation in < L i s t > , the first term inal is the definition, the nonterminal is the variable length field, and the second term inal is the term inator. In order to refer to both dynam ic length and dynamic text together, we use the term dynamic elements. W hen using a formal gram m ar to define a protocol, param eters make life difficult, b u t protocol designers have good reason for using dynamic elements. If a sending node wishes to send a block of data, of a known size, it can use dynamic length to tell th e receiver how much d a ta it is about to receive. If the sending node does not know the size of d a ta it is about to send (because it is being compressed on the
fly,
for example) dynamic text allows the sender to specify a term inator th a t the receiver can use to delimit the end of th e d ata block. If we are to use a formal gram m ar to describe network protocols, we must support dynam ic elements.
2 .2 .5
E x is tin g G ra m m a r s D e sc r ib in g N e tw o r k P r o to c o ls
Before defining our own gram m ar to define network protocols, it is w orth exploring previous work on this problem. The author found six different gramm ars for protocol specification, which are described below. Half of the specifications are designed to describe datagram oriented protocols, while th e other half are used to describe stream oriented protocols.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
2.2. G ram m ars
31
After we describe each gram m ar, we compare the gramm ars to each other.
P ro to c o l F ilte r S p ecificatio n s W hen monitoring network data, it is often desirous to create a filter to detect different classes of datagram . Creating a filter is a two step process: first, a textual predicate containing assertions about fields in a datagram must be written; and second, the predicate must be compiled, transform ing the predicate into a series of instructions, telling a recogniser values th a t m ust be present in a datagram for the predicate to pass. To simplify the compilation of predicates, datagram protocols are defined in a lan guage similar to a context free gramm ar. During compilation, the predicate compiler can resolve the location of a field by consulting the context free grammar. Chandra and M cCann[10, 40] propose Packet Types, a specification language for datagram filters. Programmers using Packet Types specify datagram structure by using rules. Packet Type rules perform a role similar to those of the phrase structure grammar, but are structured as a series of name-value pairs making the specification look like a series of C structures. In order to handle dynamic elements, each symbol in a Packet Type gram m ar has a series of verifiable attributes, including v alu e, and numelems.
The v a lu e
attrib u te provides the ability to te st a terminal against a value seen in the protocol text, numelems provides the ability to validate th e number of times a symbol repeats. Each rule has a where clause th a t contain verifiable predicates th a t can test the values of any symbol. Lambright and Debray[38] create a similar language for packet filters, called A PF. Like Packet Types, A PF embeds constraints into a set of rules. Although the aim of A PF is to provide a mechanism for generating packet filters (similar to BPF[56, 41]),
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
2.2. G ram m ars
32
the grammar appears to be sufficiently expressive to specify protocol text. The prim ary distinction between Packet Types and APF is th a t Packet Types provides a section for constraints and assignments a t the end of each production. A PF embeds each statem ent into the te x t of the production itself. Like Packet Types, A PF does not provide alternations in its grammar. Not all filter specifications recognise the need to describe dynamic entities. Jayaram and Cytron [33] assert th a t “it is simple to express such varying length fields in gramm ar form.” Their paper only describes grammars for protocols with dynamic entities up to 16 repetitions in length.
P ro to c o l S p ecification s Anderson and Landweber[5] create a methodology to express the semantics of stream s of datagram s. Their methodology, “Real-Time Asynchronous Gram m ars” (RTAG) provides a language with the same name. RTAG is similar to a context free gramm ar, whose term inals are events in a network d ata stream, instead of blocks of data. Events are detected by hand-written code which parses incoming datagrams, extracts useful data, and creates d ata structures suitable for consumption by the RTAG processor. Like A PF, the RTAG gramm ar provides a mechanism to embed blocks of code directly into gramm ar productions. Each block can modify attributes of other pro ductions, run conditional blocks, and execute external functions. Note th a t RTAG is designed to specify the behaviour of an entire protocol, it does not specify the syntax of individual datagram s. M cGuire’s Austin Protocol Compiler[43, 42] is the most ambitious datagram spec ification language surveyed. Not only does it attem pt to define the on-the-wire for m at of datagram protocols, it also specifies how the protocol should behave; using a language called “Timed A bstract Protocol” or TAP. TAP provides a limited pro
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
2.2. G ram m ars
33
gramming language th a t can be translated into C by the Austin Protocol Compiler. The purpose of TAP and the Austin Protocol Compiler is to create verifiable protocol definitions th a t can be converted directly into reference implementations. Borisov et al[8] of Microsoft Research create a full specification for protocols aimed specifically at intrusion detection systems. Their closed source specification frame work, called Generic Application-level Protocol Analyser or GAPA, utilises a language called Generic Application-level Protocol Analyser Language (or G APAL). GAPAL provides a layered description of protocols, including a context free gram m ar for de scribing protocol text, a state transition graph to handle protocol state, and a set of handlers containing arbitrary code. According to [8], GAPAL is expressive enough to build an entire protocol stack, including IP, TCP, as well as stream oriented applica tion protocols on top of TCP. GAPA can monitor H TTP traffic at rates of 60mbps. The authors of th a t paper suggest th a t GAPAL is an efficient way to develop protocol monitors. Outside of the academic realm, there are three other language specifications w orth noting: Augmented BNF (ABNF), A bstract Syntax N otation One (ASN.l), and the eXensible Mark-up Language (XML). Although these languages are not aimed ex plicitly at stream oriented protocols, they are often used in the definition of stream oriented protocols. Augmented Backus-Naur Form is used in many Request For Comments documents to define stream oriented network protocols.9 ABNF is almost identical to the phrase structure gram m ar discussed above, w ith a few minor syntactic changes.
Unlike
A SN .l and XML, there are no known support libraries for parsing text given an unmodified ABNF definition. 9RFC s are the standards definitions of the Internet Engineering Task Force (IETF). Most popular non-proprietary protocols in use on the Internet today are specified in RFCs.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
2.2. G ram m ars
34
Abstract Syntax Notation One[32], provides three mechanisms. The first allows a programmer to define a schema for data.
The schema is a set of one or more
arbitrarily complex d a ta types th a t are to be made available to a program. The second mechanism allows th e programmer to m anipulate objects of th e requested type in the program. The final mechanism allows the programmer to transm it or receive those d ata types, with A SN .l automatically handling serialisation and deserialisation. The extensible M arkup Language[13] is similar to A SN.l. It provides a mech anism for specifying a schema th a t defines a serialised representation of data. The programmer is responsible for writing d ata out in a manner th a t adheres to the schema.
Parsers exist th a t read d ata adhering to an XML specification, make it
available to a program through callbacks, or queryable in-memory representations.
A n a ly sis o f E x istin g D efin itions Of th e six approaches, note th a t none are targeted at the problem we have selected. We wish to create a machine-readable protocol specification language th a t supports dynamic elements, th a t can be used to create stream-oriented network monitors. Packet Types and A PF support dynamic elements, but are designed for dealing with datagram -oriented protocols. All of the definitions we have discussed are based on context free grammars. The exact nature of the definition varies, b u t the form remains the same: a sin gle root structure, consisting of sequences and alternations of either terminals or non-terminals, defined recursively by other structures.
Each definition is context
free. We can consider the differences between each approach in term s of datagram /stream orientation, availability of libraries, complexity of the extension to phrase structure grammar.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
2.2. G ram m ars
35
M ost of the solutions considered are datagram oriented, meaning th a t they are explicitly intended to operate on datagrams. Although the general concepts th a t are applicable to a datagram oriented approach m ap easily onto stream s (and vice versa) there are likely to be dram atic differences in implementation techniques.
Packet
Types, A PF, and T A P /A P C are explicitly datagram oriented. While ABNF, ASN.l, and XML are agnostic in their orientation, they are comparatively verbose languages, meaning th a t they do not necessarily lend themselves well to th e compact nature of datagram s. Note th a t RTAG parses events instead of datagram s or streams, making it slightly different th a n the other approaches. T he greatest axis of difference between the approaches is the use of assignments and embedded code. A t one extreme, we have ABNF, ASN.l, and XML, th a t are simply gram m ar definitions, in the spirit of the phrase structure grammar. At the other extreme is the A ustin Protocol Compiler, which embeds executable code defin ing behaviour into th e protocol specification. Between the two are Packet Types, RTAG, and APF, which allow assignments th a t modify how the parse progresses. The greatest difference between the approaches is practical.
Only half of the
languages we have discussed have publicly available libraries to parse an input given a gram m ar. Those languages are APC, ASN .l, and XML.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
C hapter 3 T he N etw ork P ro to co l G ram m ar In C hapter 2, we saw gram m ars used to describe protocols, and an evaluation of network monitoring tools. The tools th a t we saw were, almost exclusively, datagram oriented. In this chapter we present the Network Protocol Grammar, a new language for succinctly describing stream oriented application protocols in a machine-readable manner. In Chapter 4 we use this language to build a network m onitoring library called qcap.1 Before embarking on an explanation of the NPG, we explain why th e NPG is nec essary, and derive requirements for the language. W ith the requirements explained, we outline th e language, identifying its novel features. Finally, we justify the design decisions th a t we made.
3.1
M o tiv a tin g th e N P G
We wish to know who is using the network, for w hat purpose, and how. “W ho” could follow any axis of identity, from specific humans, to accounts, to hosts. Our definition of “purpose” is similarly open ended, we are interested in the reason why any event *qcap is available at h t t p : //q c a p .s o u r c e f o r g e .n e t .
36
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.2. P ro b lem A nalysis
37
occurs, either due to protocol specification, user behaviour, or processes running on a host. “How” encompasses th e tex t th a t is sent over th e network, and the nature of the host interactions th at caused it to be sent. The tools discussed in Section 2.1.2 provide some degree of network awareness, but in a limited manner. The network debugging and visualisation tools are datagram oriented, providing little information about the content of streams. The forensic tools provide access to stream content, but in an ad hoc manner: they only provide access to a subset of the fields in the stream, and they do not provide a program m atic interface. In order to build network awareness tools, we need access to all levels of the network stack. Limiting our view to an individual layer blinds us to the big picture of overall network activity. We need to be able to observe all aspects of network communications, in context. The problem we find ourselves facing is th a t there are no tools th a t provide con sistent access to every field of application-level protocols. In building such a tool (see Chapter 4), we discovered th a t defining each protocol in code was time consuming, error prone, and unpleasant. We decided th a t there m ust be a better m ethod to delve into stream content.
3.2
P ro b lem A n alysis
We wish to build a stream parser th a t is able to rend a stream down from a long sequence of bytes to a series of discrete fields, each tagged with their significance in the protocol. We wish to be able to define parsers in a m anner th a t is concise, easy to read, easy to write, and minimises errors. The resulting parsers will be used by qcap for m onitoring stream oriented protocols.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.2. P rob lem A n a ly sis
38
It is possible to create a parser in at least three ways. T he most basic approach, taken by W ireShark, is to implement a parser for each protocol in a general purpose programming language2. Alternatively, we could partially define a protocol as code, and annotate th a t code with textual parsing rules,3 in the same manner as th e parser generator bison[23]. Or, we can take the idea of parsing rules one step further, and use a context free grammar to define the entire grammar, along the lines of Packet Types[10]. If textual parsing rules are part of the language, a parser generator must be used to transform the rules into a parser.
3 .2 .1
F in d in g F ie ld s in P r o to c o ls
A stream can be thought of as an ordered sequence of fields, following some kind of specification (i.e. a protocol). In order to understand the stream , we must be able to locate and understand the meaning of each field. Finding meaningful text in a protocol is easy, regardless of approach.
If the
protocol is defined in code, the programmer only needs to identify when areas of meaningful tex t begin and end, and allow library to inform the application. W ith a partial or full context-free grammar, the rule names of th e gram m ar can be used to specify each field, and the parser generator can provide the appropriate notification to the library.
3 .2 .2
F a st E x e c u tio n
Network d a ta can be very high volume. We want our parsers to be efficient enough to handle large volumes of d ata with as low a cost as possible. 2For the sake of brevity, we will refer to any procedural or object-oriented programming language as a general purpose programming language. Any program, or fragment of a program, w ritten in a general purpose programming language shall be referred to as code. 3Textual parsing rules refer to productions defined in a context free grammar, or some other specification language such as BNF or ABNF.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without perm ission.
3.2. P roblem A n alysis
39
Any of the approaches can produce a fast parser. It is possible to write fast code, just as it is possible for the parser generator to create fast code. However, it may be difficult for a programmer to consistently produce fast code for every parser they implement. A properly tuned parser generator could produce fast execution for every parser it generates. It makes sense to allow the parser generator to handle speed concerns, as it only needs to be optimised once. If the parser generator is to handle speed critical sections, then those sections must be implemented using grammar rules.
3 .2 .3
C o rrect P a rser s
A “correct” parser behaves in the m anner the programmer expects. Any parser w ritten by a human is likely to have bugs, and may behave unexpect edly. The more code a person writes, th e more likely th a t the codebase will contain errors[47]. Machine generated code, however, is likely to be more correct. Because it is automatically generated, the parser will be less prone to book-keeping errors th a t a programmer may fall prey to. The declarative nature of context free grammars allows an explicit explanation of the structure of the protocol, rather th a n the implicit specification found in code; making deviations from specification easier to detect. Another advantage of parser generators is th a t their compile-time syntax checking allows for the detection of certain classes of error. This allows th e programmer to detect some errors a t compile time, instead of explicitly having to generate test cases to show internal consistency. Hand-written code is a stark contrast, requiring th a t every possible code p ath be tested for some level of assurance th a t th e code does not contain (severe) bugs.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.3. D escrip tio n o f th e N P G
3 .2 .4
40
P a r se r s M u s t B e E a sy t o W r ite
There are hundreds of stream ing protocols in existence. We wish to simplify the task of writing parsers for each protocol. “Simple” is a question of preference. Some programmers may find a special pur pose protocol specification language attractive, because it allows them to ignore the complexities imposed by general purpose languages. Others may find the use of a protocol specification language limiting, because it cannot perform tasks th a t would be straight-forward in a general purpose language. Regardless of preference, writing stream parsers by hand is complex and error prone, as discussed in Section 2.1.3. A context free gram m ar to describe a protocol should be much more compact than general purpose code describing the same protocol. Ideally, the gram m ar should be derivable directly from the protocol specification document (assuming th a t the specification defines the protocol in a well-known gram m ar), possibly reducing the task of parser specification to a cut and paste.
3.3
D escrip tio n o f th e N P G
Given the requirements in the previous Section, the author decided th a t a declar ative grammar was the best approach to defining application protocols for network monitoring tools. As such, he has created the Network Protocol G ram m ar. In this section, we describe the syntax of the NPG. An im plem entation of a parser generator for languages specified in NPG will be discussed in C hapter 4. We have chosen to base the Network Protocol G ram m ar on ABNF[14], primarily for backward com patibility w ith existing protocol definitions. Since ABNF is already used in many protocol specifications, we can specify parsers for those protocols simply by copying the ABNF definition out of the specification, and into a hie. As we saw in
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.3. D escrip tio n o f th e N P G
41
Section 2.2.5, there are a num ber of languages th a t can elegantly describe dynamic elements. NPG borrows syntax from the Packet Types[10] specification language. Packet Types contains a structure th a t expresses relationships between elements in th e input text; which we can easily repurpose. To facilitate grammar definition, we also add a few syntactic structures th a t simplify a specification author’s life. Section 3.3.1 describes th e ABNF basis of th e NPG. Section 3.3.2 describes the additions to ABNF th a t have been derived from Packet Types, and the additional syntactic structures th a t ease th e lot of N PG users. We justify these decisions in Section 3.4.
3 .3 .1
R e v ie w o f A B N F
R u le s The basic element of the ABNF grammar is a rule, which is identical to the rules of phrase structure grammar. In ABNF, a production is specified with a rule name, followed by an equals sign, followed by a set of elements:
nam e = elem enti ... elem entn
Elements are anything th at can appear on th e right hand side of a rule. They consist of term inal values and nonterminals.
C o n sta n ts Constants are term inal values. Terminals are sequences of characters, specified as a case insensitive string (in quotes, as most programmers would expect), or as numeric constants. Numeric constants can be specified as a series of alternatives or ranges. A constant
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.3. D escrip tio n o f th e N P G
42
is specified with the prefix °/0b, °/0d, 0/0h, or %o. Each prefix specifies a different base for th e following number, either binary, decimal, hexadecimal, or octal. The values following can either be: • a single number in the base specified, e.g. %bl010, %dlO, °/oh0a, 70o l2 , all of which match an ASCII newline. • a set of values, each specified by a number, separated by dots, e.g. %d50.5 1 .5 3 .5 5 , %h32.3 3 .3 5 .3 7 , %o62.6 3 .6 5 .6 7 , which m atch any of the ASCII characters 2, 3, -5, and 7. • a range of values, whose upper bound and lower bound are separated by a
,
e.g. %d97-122, °/„h61-7a, °/0o l4 1-172, which m atch any ASCII character between “a” and “z” . Constants m atch when the input text contains a character with the given value. Numeric constants m atch against characters w ith the same number, while strings m atch against an ordered set of characters in th e input (regardless of case). Figure 3.1 provides an example of rules and constants in ABNF.
r u l e l = "abc" r u le 2 = °/od65 %h61-63 %ol30.132 Figure 3.1: An example of ABNF. The example contains two rules. The first, < r u l e l > matches the text “a&c” , “a&C” , “aBc” , “aB C ” , “A6c” , “A6C” , “A B c", or “A B C ” . The second rule, < r u le 2 > matches “A a X ” , “A b X ”, “A c X ” , uA a Z ” , “A b Z ”, or “A cZ ” .
R u le R eferen ces The elements in th e right hand side of a rule can refer to other rules. Unsurprisingly, a rule is referenced through the use of its name. Figure 3.2 contains an example of a
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.3. D escrip tio n o f th e N P G
43
rule reference.
r u l e l = " (" ru le 2 ")" °/.d33 ru le 2 = "abc" Figure 3.2: A rule reference in ABNF. The reference is the second element of the production < r u l e l > . Assuming th a t < r u l e l > is the starting rule, the gram m ar will match “(abc)!”, “(abC)!”, “(aB c)!”, “(aBC)!”, “(Abc)!”, “(AbC)!”, “(A B c)!”, or “(A B C )!”.
Sequences A sequence is a series of symbols in th e right hand side of a rule th a t must m atch consecutively for the rule to match. Like the phrase structure grammar, ABNF uses white space as the sequence operator, meaning th a t a list of symbols separated by spaces defines a sequence. Figures 3.1 and 3.2 contain sequences. In order for the sequence to m atch, every symbol in it must m atch against the input, in order. To explicitly create a sequence (to control alternation or repetition, for example), any number of symbols may be w rapped in round brackets.
A ltern a tio n Alternatives provide a set of possible values th a t an input may contain. In order to for the alternative to match, any one of th e possible values must match. Each possibility is separated by a “/ ” . Alternation has lower precedence than sequences, meaning th a t individual alternatives can contain multiple elements, as seen in Figure 3.3. We can use recursion and alternation to define gramm ars with balanced sta rt and stop features, as seen in Figure 3.4.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.3. D escrip tio n o f th e N P G
44
r u l e l = "a" "b" "c" / "xyz" / r u le 2 r u le 2 = "123" Figure 3.3: A rule reference in ABNF. Assuming th a t < r u l e l > is the starting rule, the grammar will match any case perm utation of: “abc”, “xyz”, or “123”.
b ra c k e ts = argum ents / "(" b r a c k e ts ")" argum ents = " a rg , " argum ents / " la s tA rg " Figure 3.4: A recursive grammar. Assuming the gram m ar starts with < b r a c k e ts > , we will match a balanced number of brackets around an argument list consisting of one or more instances of the text a rg , and finishing w ith a la stA rg . Examples include: “(lastArg)”, “(((arg, arg, lastArg)))”, or “((arg, lastArg))”. R ep etitio n O perators Every structure of ABNF we have seen so far is a mapping from the phrase structure grammar described in Section 2.2.2. ABNF possesses two operators th a t we have not seen: the repetition operator, and the optional sequence operator.4 These operators do not increase the expressiveness of the language, but they do make ABNF gramm ars easier to to read. The repetition operator indicates th a t the associated element should repeat a specific number of times. It is a prefix operator denoted by a star (*). The operator takes two operands: a prefix minimum, and a postfix maximum. All counts dealing with the operator are inclusive. To specify th a t a character r should occur between three and five times, the following block of NPG could be used: 3*5" r" , which would match “rrr”, “r r r r ” , or “rrrrr”. Note th a t the more verbose, and less readable syntax "rrr" / "rrrr" / "rrrrr" could also have been used. 4These operators are the intellectual offspring of the Kleene star[22\ operator. Operators styled on Kleene star exist in many languages.
Reproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.3 . D escrip tion o f th e N P G
45
Either operand may be omitted. If the minimum is discarded, it is an implicit zero. If the maximum is omitted, it is an implicit infinity. If both minimum and maximum are om itted, the entity may occur zero or more times. ABNF also provides an optional sequence operator. Like the repetition operator, the optional sequence operator changes how often an element can occur, in this case, between zero and one times. The optional sequence operator is [], w ith the element list between the square brackets.
The optional sequence operator is functionally
identical to 0* 1 (). In order to m atch zero or one occurrences of the string “kittens” , we could use either [ " k itt e n s " ] or *1 " k itte n s " .
3 .3 .2
T h e N e tw o r k P r o to c o l G ra m m a r
Our goal with this thesis is to provide a tool for monitoring the application layer of network interactions. We wish to extend network monitoring out of the network and physical layers, and into the application layer. To analyse the application layer, we need a succinct way of describing application protocols th a t contain dynamic elements. The Network Protocol Grammar is a context free gram m ar to do just th at. We derive m ost of the N PG ’s structures from ABNF. We use A B N F’s rules, con stan t definitions, sequences, alternatives, and repetition operators w ithout change. We support dynamic elements by borrowing Packet Types’ where clause, and expres sions. The Packet Types where clause is used to express relationships and constraints, limiting the datagram s th a t a Packet Types grammar will recognise. Packet Types is designed in this m anner because it is used for datagram recognition. W hen writing a Packet Types gramm ar, the goal is be able to detect syntactically correct instances of protocols. Our goal is different: we wish to parse stream s containing dynamic elements.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.3. D escrip tio n o f th e N P G
46
L ogical M od el o f th e N P G The N PG provides a model for grammars. A gram m ar consists of a series of rules. Each rule has two attributes, its minimum cardinality, and its maximum cardinality. If a rule is a terminal, it has an additional attrib u te: the text it matches. This model is identical to th a t of ABNF. N PG differs from ABNF by making attributes mutable. For terminals, all three attrib u tes are mutable. For nonterminals, only th e minimum and maximum cardi nality is mutable. In turn, zero or more nonterminals are annotated with assignment operations th at can modify attributes. W hen an annotated nonterm inal matches the input, it changes one or more of the attributes of the rules. The modification made to the attribute(s) is a function of the tex t th a t the nonterminal matched.
In tro d u cin g th e s e t C lause To express the relationship between nonterminals and the attrib u tes they change, we introduce the s e t clause to the NPG. Any rule can be annotated with a s e t clause. The s e t clause contains zero or more statem ents th a t define which rules’ attrib u te is changed, the nonterm inal the change depends on, and the function th a t determines the change.
S y n ta x o f th e s e t C lause The s e t clause exists a t the end of a standard NPG rule. It begins with the string s e t, and contains th e list of statem ents between braces.5 Each statem ent consists of a left hand side and a right hand side. 5In order to promote consistency, we also allow the elem ents of the rule to be wrapped in braces, but that is a purely cosm etic change.
Reproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.3. D escrip tio n o f th e N P G
47
The left hand side identifies the rule and attrib u te th a t is modified by the state ment. The rule is identified by its name. A ttributes are identified by the constant strings te x t, re p e titio n _ m in , or rep etitio n _ m ax . A hash (#) is used to join the rule name and the attrib u te string. The t e x t attrib u te is used to modify the tex t of rules th a t contain a terminal. It may not be used with rules th a t contain nonterminals. The r e p e t i t ion_min and r e p e t i t i o n max attrib u tes change the cardinality of rules. The change is global across all uses of the the rule, r e p e t i t ion_min is used to change the minimum number of times th a t a rule may match, while r e p e t i t ion_max is used to change the maximum number of times th a t a rule may match. In situ ations where grammar authors may wish to change bo th attributes simultaneously, they may use the pseudoattribute r e p e t i t i o n , causing both r e p e t i t ion_min and r e p e t i t ion_max to be modified at the same time.
t e x t = le n g th v alu e set { v a lu e # re p e titio n _ m in = i n t ( l e n g t h ) ; v a lu e # re p e titio n _ m a x = i n t ( l e n g t h ) ;
} le n g th = l*%d48-57 v a lu e = %d97-122 Figure 3.5: G ram m ar Gset provides a sample use of the s e t clause. The grammar, rooted at < t e x t > will m atch any input text th a t has some number n, followed by n lower case ASCII characters. For example, it will m atch “4four” , “2 a V , “20intem ationalization'” , or “0” . Meanwhile, the right hand side references one or more nonterminals used in the rule. The nonterminals may have functions applied to them, or they may remain bare. Figure 3.5 shows a gram m ar Gset th a t uses a s e t clause. Rules referenced in the right hand side of a s e t statem ent must occur exactly
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.3. D escrip tio n o f th e N P G
48
once in the associated rule.
Sem antics o f th e s e t C lause Gset from Figure 3.5 creates two annotations in the logical NPG model. B oth anno tations are attached to the < le n g th > rule reference in < t e x t > . The targ et of the annotations are the repetition attrib u tes of the < v a lu e > rule. When Gset is matching an input string i, there are four events of interest th a t occur: • The < le n g th > rule is accepted, meaning th a t it has matched one or more ASCII characters representing integers. • The string th a t < le n g th > matched is fed to the function i n t ( ) , which pro duces an output out com patible with the r e p e t i t ion_min and r e p e t i t ion_max attributes of < v a lu e > . • The r e p e t i t iom m in and re p e titio n _ m a x attributes of < v a lu e > are updated to reflect out. • A character starting < v a lu e > is received. Because th e cardinality of < v a lu e > has been set to out, < v a lu e > will not m atch until exactly out characters have been received.
Scoping th e s e t C lause Nonterminals referenced in th e right hand side of the s e t clause are scoped to the rule in question.
This allows nonterminals to be used in multiple rules, without
unpredictable effects.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.3. D escrip tio n o f th e N P G
49
Consider the gram m ar Gmuiti showing in Figure 3.6. In the example, Gmuiu the gramm ar matches some number, followed by zero or more space separated numbers, and then a string. The length of th e string is specified by the first number.
m u lti = le n m u ltiL en value set { v a lu e # re p e titio n _ m in = i n t ( l e n ) ; v alu e# re p e titio n _ m a x = i n t ( l e n ) ;
} m ultiL en = *(" " le n ) le n = l*°/„d48-57 v a lu e = °/0d97-122 Figure 3.6: G ram m ar The grammar matches “20intem ationalization”, “20 1 2 3intem ationalization” , “0 10 10 10”, u0 10 10 10”, or u2 50 la b ”. Gmuiu uses < l e n > to describe all of the numbers in the input text, but th e only instance th a t sets < v a lu e > ’s attributes is the one in < m u lti> . The same scope lim it does not apply to the attrib u te target. W hen a ru le/attrib u te pair is specified on th e left hand side of a statement, every tim e the rule is used, it will m atch in a modified form.
S yn ta x C han ges During our experience using the Network Protocol G rammar, we discovered a number of usability issues w ith the ABNF-derived portions of the gramm ar. Notably, casesensitive text is hard to define, and there is no mechanism for supplying a starting rule for the gram m ar. We make two additions to NPG to handle these problems. ABNF forces users to define case sensitive text using character ranges. So, to define the case sensitive string “k itten” , we must specify the ASCII character code for each byte individually, yielding: °/„dl07 %dl05 %d!16 % dll6 °/odl01 ’/0dllO . Such
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.4. D esig n D ecisio n s
50
constructs are difficult to read. We add a new string type: a case sensitive terminal, which consists of the string, surrounded by double quotes. To differentiate a case sensitive string from a case insensitive string, we append the character c onto the last quotation mark. T he string “k itten ” , using our case sensitive term inal is a much more readable " k itte n " c . Note th a t this change does not effect N PG ’s ability to read standard ABNF. Although the ABNF standard indicates the structure of a gramm ar, it does not supply a m ethod to indicate which is the root of the grammar. NPG sets the first rule in the grammar to be the topm ost rule.
3.4
D esig n D ecisio n s
The NPG did not spring from its creator’s head fully formed. Instead, it was built iteratively.
At various points the author considered different paths. This section
describes possible paths, and why th e chosen path was selected.
3 .4 .1
D iv o r c in g B e h a v io u r a n d G ram m ar
Some parser generators, such as bison[23] and yacc[34] force gramm ar authors to annotate the rules in their grammars w ith code th a t specifies activities th a t should occur when the given input is received. O ther gramm ar description languages, such as XML, eschew th a t approach, forcing programmers to subscribe to rules in the programming code th a t uses the grammar. The NPG is intended to be used as a general specification language, th a t is not bound to individual applications, or programming languages. Including code in a grammar definition would limit N PG ’s portability.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.4. D esign D ecision s
3 .4 .2
51
C h o o sin g t h e B a se G ra m m a r
Since we did not want to create the NPG from scratch, we considered existing protocol definition languages as a starting point. Our intent was to extend an existing context free grammar. We considered three possible grammars to use as a base. The first, ABNF, is a standard context free grammar, meaning th a t it suffered the failings described in Section 2.2.4. The other two grammars are packet filter description languages th a t already contain syntactic structures addressing the problems raised in Section 2.2.4. ABNF is a popular context free grammar, used to define protocols in many RFCs. It is close to the “textbook” context free gramm ars th a t most programmers encounter in school, meaning th a t most programmers can read and understand ABNF with little or no effort. Our second candidate was Packet Types, described in Section 2.2.5. Unlike ABNF, we were unable to find references to the language outside of academia. It is also based on a context free grammar, but th a t gram m ar associates a type w ith each symbol used in a production; producing grammars th a t bear a resemblence to C-style structs. Packet Types is notable because it provides syntax to handle dynamic elements, meaning th a t if the NPG uses it as a base grammar, we would be able to use the dynamic element handling portion verbatim. However, Packet Types is a filter spec ification language, its prim ary goal is winnowing packets. Its alternation syntax is limited: it does not allow inline alternatives in a rule, instead, it introduces a special class of rule th a t may m atch any one of a set of alternatives. Our third candidate was APF. APF provides a bison-like syntax. Although A PF is also a filter specification language, it is much closer to a standard phrase structure grammar. Its lack of alternation syntax could easily be remedied. APF does not appear to be used outside of Lambright’s original paper, meaning th a t any protocol
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.4. D esig n D ecisio n s
52
definition in an A PF-based language would have to be ported from ABNF. W hen deciding which gram m ar to use as a template, ABNF’s popularity won the day.
Many protocols are defined in ABNF, meaning th a t very little work should
have to be done to produce N PG definitions. For protocols th a t don’t require N PG ’s advanced features, the specification can be used without modification. Protocols th a t require N PG ’s more complex field term inators would only require m inor additions.
3 .4 .3
C h o o sin g a S y n ta x for D e sc r ib in g D y n a m ic E le m e n ts
Protocol recognition literature provides two examples of ways to handle dynamic text: the Packet Types where clause, or the embedded expressions used in A PF. In order to get a rough idea of the appearance of these two idioms, we compare how they represent an IP datagram . The APF representation is shown in Figure 3.7, and the Packet Types representation is shown in Figure 3.8. The examples are adapted from Lam bright’s APF p ap er[38], and the Packet Types papers[10, 40]. A P F ’s expressions are less structured, able to appear anywhere in th e produc tion. Packet Types has a more formal approach, forcing the assignment of dynamic attributes into a clause added to the production. Of the two approaches, the author prefers Packet Types, as it enforces more structure. W ithin structures, A PF references productions by index. In Figure 3.7, the < i h l > production is referenced w ith a $2 and the < t o t a l l e n g t h > production is indexed w ith $4. Packet Types uses th e much more hum an readable approach of referring to symbols by name. The author chose to use th e Packet Types the approach to dynamic elements, as it is more readable and structured.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.4. D esig n D ecisio n s IP_PDU
:
53
v e r s io n i h l { o p tL e n = p to in t( $ 2 ) * 4 - 20;} to s t o t a l l e n g t h { p a y lo a d L e n = p to in t( $ 4 ) - p to in t($ 2 )* 4 ;} id m o refrag s d o n tfra g unused o f f s e t t t l p ro to checksum src dst o p tio n s payload
v e rs io n ih l to s to ta lle n g th id m orefrag s d o n tfra g unused o ffse t ttl p ro to checksum
b it* 4 ; b it* 4 ; b y te ; byte*2 byte*2 b it ; b it ; b it ; b it* 1 3 b y te ; b y te ; b yte*2
s rc d st
b y te *4 ; b y te *4 ;
o p tio n s
b y te * o p tL e n ;
p ay lo ad
b y te * p a y lo a d L e n ;
; ;
;
;
Figure 3.7: A specification an IP packet using A PF. Text highlighted in bold denotes syntactic structures specifying dynamic length. The $2 and $4 in the expressions are references to symbols in the
3 .4 .4
D e s ig n in g th e N P G L o g ica l M o d e l
The N PG logical model, described in Section 3.3.2, was derived from the Packet Types gram m ar. The entities in the logical model m ap directly to entities in the grammar. Because the model exhibits th e behaviour we wish N PG to express, possesses no
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.4. D esign D ecision s
54
nybble := b i t [4 ]; sh ort := b i t [1 6 ]; lon g := b i t [3 2 ]; IP_PDU := { nybble nybble b yte sh ort
v e r sio n ; i h l; to s; t o t a lle n g t h ;
sh o rt b it b it b it b it
id ; m o refra g s; don tfrag; unused; o f f s e t [13];
b yte b yte sh o rt
ttl; p r o to ; checksum ;
lon g
sr c ;
lon g
d e st;
ip _ o p tio n o p tio n s [] ; payload payload [] ; } w h ere {
o p tio n s# n u m b y te s = ihl^ tvalue * 4 - 20; p a y lo a d ^ n u m b y tes = totallen g th ^ tv a lu e - ih l# v a lu e * 4;
} Figure 3.8: The specification of an IP packet using Packet Types. Text highlighted in bold denote syntactic structures providing dynamic length. discernible drawbacks, and no alternatives made themselves clear, we did not examine any other approaches.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.4. D esign D ecision s
55
valu e The natural number formed by concatenating all th e bits of the field in network order. num bits The to tal number of bits occupied by the field, numbytes The to tal number of bytes occupied by the field, numelems The number of elements in an array-type field. a l t For an alternative-type field, a collection of booleans indicating which alternative was chosen. Figure 3.9: Packet Types attributes, originally presented in [40].
3 .4 .5
C h o o sin g R u le A ttr ib u t e s
Packet Types provides five attributes for rules, shown in Figure 3.9. We chose to ignore those attributes for a number of reasons.
P acket T y p es A ttrib u tes The numbits, and numbytes, fields are not appropriate for the NPG, as the NPG is byte oriented. Similarly, numelems has no direct application to the Network Protocol Grammar because our language has no concept of arrays. Instead, we provide the same functionality with the re p e titio n _ m in and re p etitio n _ m ax attributes. These fields are more general, able to describe ranges of valid repetitions, instead of a specific number of repetitions.6 The v alu e attrib u te is sensible when querying a rule for the text it matches, as Packet Types does in its assertions. B ut th e NPG exists in a different space: we wish to assign a value to a rule, instead of verifying it. Furthermore, we can only assign to terminals. We wish to make the relationship between assignment and the type of rule clear, so we use the name te x t. To the author, t e x t implies th e only type of 6Such ranges could be useful for cryptographic protocols that require a minimum and maximum key length, but whose key length may be variable due to compression, or other vagaries.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.4. D esign D ecisio n s
56
symbol th at possesses a text value: terminals. The a l t attrib u te in Packet Types is used to determine which branch of an alter nation matched. Packet Types contains syntactic structures to layer protocols on top of one another. Those structures use the a l t attrib u te to set the type of a d atagram ’s payload.7 NPG does not currently provide features for protocols to be layered on top of one another, and therefore does not use this feature.
S elected A ttrib u tes The author chose N P G ’s attributes based on their mapping to concepts within context free grammars. Cardinality attributes are derived directly from ABNF’s repetition operators, which allow for the specification of upper and lower bounds for cardinality. Similarly, the t e x t attribute was chosen to rewrite a single terminal.
S ca le of G ram m ar M odification A more general mechanism for exposing the gram m ar to modification could modify a gramm ar arbitrarily at parse time, adding or removing entire alternations and sequences, or adding new rules. We did not follow this route of redefinition because we wanted to limit the scope of modification from what is possible, to w hat is useful and achievable. In the protocols we have surveyed so far, th e selected attributes are sufficient to allow parsing.
3 .4 .6
C h o o sin g S c o p in g R u le s
The Packet Types papers do not specify scoping rules. Instead, the author has created the two scoping rules. We address each scoping rule separately 7If other roles are intended for this feature, the author was unable to find them in [10, 40],
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.4. D esig n D ecisio n s
57
S cop in g A ttrib u te A ssig n m en ts From th e s e t Clause Recall th a t nonterminals in the right hand side of s e t statem ent must occur in the associated rule. If th e nonterminal occurs in any other rule, it is ignored for the purposes of the attrib u te assignment. We can say th a t the expressions in th e s e t clause have local scope. An alternative to locally scoping attrib u te assignment is global scoping. A global scope would cause any reference of the given nonterminal to modify an attrib u te in a s e t clause. The author feels th a t global scoping is unintuitive and error prone for attrib u te assignments. Consider Figure 3.10.
m essage = { " S e n tin e l: " AlphaNum NL *lH eaders NL P ayload NL End } set { E nd#text = string(A lphaN u m );
} AlphaNum = l*(% d65-90 / 0/„d97-122 / 0/.d48-57 / Headers =
"From: " AlphaNum AlphaNum NL / "To: " AlphaNum "0" AlphaNum NL / "X-" AlphaNum ": " AlphaNum NL
P ayload = AlphaNum / " " / NL NL = 7„dl0 End = "ignore"
Figure 3.10: G ram m ar Gscope. G scope misbehaves when a ttrib u te assignment is globally scoped. GScope will do two very different things when run under local or global scope. Un
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.4. D esig n D ecisio n s
58
der local scope, it will use the first
S cop in g th e U se o f M od ified R u les W hen a rule is modified with the t e x t attribute, every instance of th a t rule through out the gram m ar will m atch the new value. The modified rule has global scope. Local scope would only allow the modified rule to appear in the rule where it was modified, all other uses of the rule would m atch the original definition in th e grammar. Global scope is superior for rule use because th e attribute assignment may be buried in p art of the gram m ar th a t cannot appear in the same production as the reference to the modified rule. Consider a scenario where one of many headers, which may appear in any order, sets the length of a field following the headers.
Under
local scoping, both the header and the field would have to appear in the same rule. Under global scoping, the header and the field can occur in different rules, improving m odularity of the grammar.
3 .4 .7
L a y erin g G ra m m a r s
One of the features of Packet Types th a t we chose not to implement was protocol layering.
Packet Types allows grammar specifications to be built on top of each
other. So, for example, the specification for a T C P datagram can be layered onto the
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.4. D esign D ecision s
59
payload portion of an IP datagram . This practice occurs at the application layer as well, some application layer protocols are built on other application layer protocols. For example, the Internet Printing Protocol[29] can use H TTP to tran sp o rt infor mation. W hen IP P runs over HTTP, it sets some fields in the H T T P protocol in a specific manner, and transfers d ata in the H TTP payload. We chose not to provide gram m atical hooks for protocol layering for due to com plexity. The line between the transport layer protocol and the higher level protocol may be fuzzy: d ata may be carried outside of what one considers the payload-bearing portion of th e protocol. Instead, we opt to leave th a t problem to be addressed in somebody else’s thesis.
3 .4 .8
T h e C a se S e n s itiv e T erm in a l
The case sensitive terminal, although not necessary, makes grammars much easier to read. When defining the case sensitive terminal, the author decided th a t the string had to be shown verbatim in the grammar. The only decision left was to decide on the delimiters to use for the string. We chose not to use special characters, such as backticks ( ‘) or apostrophes ( ‘) as delimiters, as ABNF already uses many punctuation characters. We feel th a t us ing yet another punctuation character would limit th e scope of future modifications. Instead, we chose to use the existing double quote (") delimiter, w ith a suffixed argu ment “c” . This follows the Perl idiom of appending modifiers to regular expressions. For example, the Perl regular expression /s e a r c h / can be made case insensitive by appending an i to the term inating slash: / s e a r c h / i . This approach is extensible, allowing us to add other arguments in future. It maintains consistency with ABNF. It does not consume any more delimiters.8 The sThe author was disappointed to discover that square brackets are used by A BN F to delimit
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
3.4. D esign D ecisio n s
60
approach should also be familiar to anyone who has w ritten more than a few lines of Perl.
3 .4 .9
S e le c tin g a S ta r tin g R u le
We chose to use the first rule of an NPG gramm ar as the starting rule because it should be the first rule visible when opening the gram m ar file. We easily could have given the rule a special name, added a special delimiter to the rule, or chosen some other distinguished position. Although a special name would be an acceptable, it is not necessarily easy for gram m ar authors to deal with. If the special name is somehow related to the file name (similar to Java’s class naming approach), then th e gramm ar author is forced to modify the gram m ar whenever the gram m ar’s filename changes. If the special name is constant across all grammars (similar to C ’s m ain() function), then we make life difficult for anyone who wishes to combine grammars, as there is guaranteed to be a t least one rule naming conflict. We chose not to use a special delimiter for the s ta rt rule because th a t would add complexity to the grammar of the NPG. Instead, we would rather modify the semantics of th e language. The only other distinguished position the author considered was the last rule in the grammar. We chose to avoid th e bottom because it would require th e user to scroll to the end of the file to find it.
optional regions. Perl, and other regular expression languages use square brackets to delimit ranges of legal characters verbatim.
Reproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
C hapter 4 T he qcap Library Chapter 3 presented a gram m ar for specifying network protocols in a machine-readable manner. This chapter builds on th a t work, presenting a tool for network analysis called qcap. qcap is a network m onitoring library th a t provides applications w ith access to each level of th e T C P /IP protocol stack, as well as stream ing application protocols running on TCP. Stream parsers are generated from NPG specifications of protocols. In this chapter, we describe qcap, starting from basic requirements, and work ing our way into a description of th e library, as well as design and im plem entation concerns. We will begin with an explanation why qcap is necessary.
4.1
M o tiv a tin g qcap
A quick survey of existing libraries (netdude[36], pcap[56], and CoralReef[9]) shows network analysis libraries concentrate solely on datagram oriented protocols. Newer libraries (netdude and CoralReef) provide hooks for protocol-specific datagram anal-
61
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4.2. R eq uirem ents for qcap
62
ysis, but provide no stream-level functionality.1 The lack of stream reconstruction libraries means th a t any researcher who wishes to explore application stream s must build their analysis tools from th e IP layer to the application layer.
Their tools m ust defragment IP streams, reconstruct T C P
sessions, and parse the application stream in question. T C P /IP reconstruction is not trivial, and differs depending on the endpoints in question[54], adding a further layer of complexity. qcap is designed to be a foundation for tools th a t need access to some level of the network stack. It emulates the network, transport, and application portions of a network stack, and provides access to all parts of the reconstruction process.
4.2
R eq u irem en ts for qcap
W hen designing the Network Protocol Grammar, we wanted to be able to describe protocols in a way th a t is concise, minimises errors, and easy to use. For qcap we map those requirements in the context of software design. qcap m ust b e fast. Fast network reconstruction means th a t large volumes of net work data can be rebuilt quickly. The exact definition of “large” and “quickly” will depend, of course. The author wishes qcap top be able to reconstruct a gigabyte in one to two minutes on commodity hardware. qcap m ust exp ose h ig h lev el data. The purpose of the qcap library is to reveal information contained in high-level protocols to applications. qcap m ust b e easy to u se. We want qcap to be used by other researchers. In order 1libnids[59] is a partial exception: it reconstructs byte-oriented data streams from T C P /IP data grams. In doing so, however, it discards the relationship between the higher level TC P payload, and the datagrams that carried it, making it less useful for network analysis.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4.3. D escrip tio n o f th e qcap Library
63
for th a t to happen, the library must be easy for programmers to use. Defining “easy to use” is difficult, so we shall simply state th a t we want to qcap API to be simple, comprising of a small number of functions, whose purpose is clear. qcap m ust reco n stru ct all netw ork traffic. As we stated above, a valuable re construction tool would rebuild data from every level of the network stack, starting at the IP layer, and working up to the application layer. qcap’s reco n stru ctio n p ro cess m ust b e tran sp aren t. W hen a datagram is re ceived by a host, it will not necessarily be passed out of the kernel. It may be discarded for a number of reasons. If th e datagram is discarded, we wish qcap to inform the application th a t a discard event occurred, and why. Our analysis of the qcap problem domain provided many fewer options than our analysis of the NPG domain. In addition to the aforementioned requirements, we wished to get a system up and running as quickly as possible. As such, we avoided exotic approaches to the problem of creating a full network stack, and used a simple layered approach. The layers correspond to th e layers of the network stack. We delay further discussion of design issues until after we have described the qcap API.
4.3
D escrip tio n o f th e qcap Library
The qcap life cycle is simple, falling into four steps: creation, configuration, execution, and cleanup. During creation, the application creates a qcap instance, and specifies a source for datagram s to be read from. Configuration follows, allowing th e application to subscribe to specific network events, and specify pcap filters for winnowing data grams. During execution, the application passes control to qcap allowing qcap to
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4.3. D escrip tio n o f th e qcap L ibrary
64
trigger callbacks installed during the configuration phase. Once the datagram source has been exhausted, or the application requests th a t execution stop, the application tells qcap to clean up after itself.
4 .3 .1
C a llb a ck s in qcap
qcap provides four callbacks for network events, each providing a slightly different view on the payload of network transactions. Each callback is parameterized, allowing it to m atch a subset of events. The application can deregister callbacks at any time.
D atagram -O rien ted C allbacks Datagram -oriented callbacks are triggered for network events involving individual datagram s, such as initial receipt, discard, or acceptance by a higher level protocol. The application can choose to be notified of datagram s as they pass through specific portions of the network stack. D uring IP defragmentation, many datagram s can be merged into one larger d ata gram. In this situation, a pseudopacket is created, carrying the total d a ta of the fragments, as well as references to the constituent packets.
The pseudopacket is
treated as a normal datagram for th e remainder of the reconstruction process.
S eg m en t-O rien ted C allbacks A segment is a unit of d ata sent across a TC P connection, equivalent to th e payload of a single TC P datagram [51],
Segment-oriented callbacks operate at the stream
level. They are triggered when a segment is accepted or discarded. The application may choose to ignore some classes of segment, such as empty segments resulting from em pty T C P acknowledgement datagrams.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4.4. Im p lem en ta tio n N o tes
65
Stream C reation C allbacks To minimise the costs of marshalling datagram payload into segments, qcap includes a stream creation callback. The callback is triggered whenever a stream is erected (from one side of a conversation), and allows the application to decide if it wishes to receive segment callbacks for the d a ta in th a t stream.
A p p lication -O rien ted C allbacks Application oriented callbacks are triggered whenever specific portions of T C P stream s are detected by the application parser generated from an NPG definition. The appli cation parameterises each application-oriented callback with th e type of stream qcap should listen on, and the specific held it wishes to receive notifications about (with names derived from rules in the N PG specification).
4.4
Im p lem en ta tio n N o te s
qcap is built in a manner th a t hides the complexity of the network stack from the application. However, part of qcap’s internals will determine how it behaves for tests in Chapter 5, so we will provide an overview of th e system.
4 .4 .1
H a n d lin g I P a n d T C P R e c o n s tr u c tio n
qcap uses th e open source lib n id s[5 9 ] library to perform IP defragm entation, and TC P stream reconstruction. According to the l i b n i d s website, it “emulates the IP stack of a 2.0.x linux kernel.” A number of li b n id s internal d a ta structures had to be modified to carry datagram inform ation from the physical layer to the application layer of the simulation.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4.4. Im p lem en tation N o te s
4 .4 .2
66
P a r se r
A bulk of the original work in qcap is found in the application layer parser generator. The parser generator is responsible for producing parsers from protocol specifications w ritten in NPG. qcap transform s grammars into nondeterministic finite autom ata. Each autom ata consists of a set of states, connected by transitions. Every transition corresponds w ith a legal input symbol. Two states in the autom ata are distinguished: one as the start state, and one as the accept state. For every protocol there need only be one autom ata. Many parsers can read simultaneously from one autom ata. A utom ata in qcap have a number of additional features designed specifically for handling dynamic elements. First, each transition has an unordered set of vetoes th a t execute after the parser has matched a symbol on the transition. As their nam e suggests, vetoes prevent the parser from matching the transition, effectively “turning off” transitions. Second, each transition maintains an ordered set of actions. Each action acts as an instruction th a t is executed when the transition is matched and followed. Actions may have arbitrary behaviour, b u t are usually used to perform book-keeping activities, such as managing the the parser’s stack. Vetoes are tested before actions execute. Parsers are responsible for receiving input, determining if the input conforms to the grammar defined by their associated autom ata, and parsing the input into parts, as defined by th e grammar. Each parser has a state pointer, th a t records its position in the autom ata. Parsers have zero or more registers th a t store param eters for dynamic elements; and zero or more buffers for recording input to be processed into param eters (and eventual storage in a register). In order to properly m aintain the location in an automata, parsers also have two stacks: a rule stack, which records the gram m ar rules th at th e parser has entered but not yet left; and a counter stack which is used
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
67
4.4. Im p lem en tation N o tes
enter
state 1
state2
state3
Figure 4.1: Graphical notation used to describe an autom ata N otation used to describe autom ata. Assuming the autom ata is in statel, an input of “a” , while z is less than five, will cause the autom ata to progress to state2 across enter. The only valid escape from state2 is to stated, on an input of “b” . W hen the autom ata crosses exit, the value x will be set to 5, and z will be incremented. when making decisions about cardinality. Initially, the state pointer is set to th e s ta rt state. W hen a character of input is received, the parser examines the transitions leaving the current state. If there are no transitions th a t m atch the input character, th e parse fails and the input is rejected. If there is one transition th a t matches the input (th at the vetoes do not prevent), then the parser updates its state pointer to point to the destination of th a t transition, and waits for the next input. If there is more th a n one transition th a t matches the input character, the parser has reached an ambiguous subgraph of the grammar - th a t case will be examined in Section 4.5.4. If, after the parser has followed a transition, it finds itself in the accept state, the parser reports th a t it has fully parsed the stream and terminates. Some transitions are special. They represent recursive rule references in the cor responding NPG definition. When the parser crosses a transition th a t corresponds to entering rule dst from rule src, it pushes d st onto a rule stack (which already has src at the top). When it comes time to exit th e rule reference, the parser checks its rule stack to ensure th a t dst is on th e top of th e stack. If dst is present, the parser pops it off, and checks th a t src is on th e stack before returning to src if dst is not present, the parser tests the other outgoing transitions. In this manner, qcap ensures th a t parsers leaving rule references exit to th e correct rule.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4.4. Im p lem en ta tio n N o tes
68
The generated parsers are able to perform as ordinary pushdown parsers and manage dynamic elements by using a combination of actions and vetoes. T he format we will use to render autom ata in this document is shown in Figure 4.1. Note th a t the increment operations indicated in the Figure are performed by actions. Similarly, th e tests are performed by vetoes. States in an autom ata are represented by circles. Transitions are represented by directed arrows. The character associated with a transition is rendered above th e transition in a monospace font. If a transition has one or more vetoes associated w ith it, those are shown as boolean statem ents in italics over the transition. If a transition has actions associated w ith it, those are shown as assignments over the transition. We use C-style short hands to represent increment and decrement operations. W hen we need to label transitions, they are tagged with a san s serif font.
4 .4 .3
H a n d lin g D y n a m ic E le m e n ts
Dynamic elements are preceded by parameters. The param eter modifies the parser in some way, changing how the dynamic element will be parsed. All of the syntac tic structures th a t act as param eters are defined explicitly in th e right-hand-side of assignments in s e t clause of the NPG. After the gramm ar has been compiled into an autom ata, the life cycle of a pa ram eter/elem ent pair is broken into four parts: 1. d etect the param eter th a t specifies an syntactic feature, 2. read the param eter from the input stream, 3. convert the param eter into a form meaningful to the parser, 4. u p d ate the parser to reflect the parameter.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4.4. Im p lem en ta tio n N o te s
69
Each step is performed with a combination of actions and vetoes, stored at strate gic locations in the autom ata. Each param eter is explicitly linked to a rule reference in the grammar, which means th a t d etectio n is the simple m atter of annotating the transitions leading into th e rule reference, and out of the rule reference. The entry transition tells the parser to sta rt record subsequent input into buffer b. The exit transition tells the parser to stop recording into b, and to read the param eter out of the buffer. The con version step causes the parser to execute the NPG expression on the right-handside of the assignment. The parser then u p d a tes itself by storing the result in a register associated with th e left hand side of the assignment. The exact nature of th e register depends on the type of dynamic element in ques tion. If the element is a dynamic cardinality, then the register is pair of integers, one representing the lower bound, and the other representing the upper bound. If the element is dynamic text, then the register is a variable length string. Every dynamic element has a different register, allowing an arbitrary number of param eters to modify the parse.
4 .4 .4
P a r sin g D y n a m ic C a r d in a litie s
After a param eter has been stored into a register, it is ready for use by th e parser. The upper and lower limits of cardinalities are stored into integer registers and consulted by vetoes and actions when the parser deals with dynamic cardinalities. The actions m aintain a counter stack by performing push, pop, and increment operations. Vetoes use th e topm ost value on the counter stack, and the value of registers to decide which transitions should be active. Parsing dynamic cardinalities has two components: parsing minimum cardinalities and parsing maximum cardinalities, qcap’s behaviour for each is analogous, so we
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
70
4.4. Im p lem en ta tio n N o te s
prev
rStart
rEnd
next
Figure 4.2: An au to m ata th a t does not handle dynamic cardinality An autom ata th a t we will add dynamic cardinality to. r S ta r t and r E n d denote the first and last node we wish to repeat. will start by discussing how qcap handles maximum cardinalities. Before we consider a maximum cardinality, we examine the original autom ata, shown in Figure 4.2. The autom ata consists of the region we wish to repeat, delimited by rS ta r t and r E n d , and th e states before and after th e region: prev and next, respectively. r S ta r t and rE n d could be one node or many. In this example, rS ta r t and rE n d represent start and end of a rule r.
H an d ling M axim u m C ard in ality We want to assign an upper limit of u for repetitions of r, meaning th a t r can occur at most u times. B ut we do not know the value of u when we generate the autom ata, so we must consider every possible value of u th a t will change the structure of the autom ata. There are two cases of interest. If u is zero, then rS ta r t and rE n d will be skipped entirely. We add a transition named skip leading from prev to next, and give it the same symbol used to exit rE nd, in this case b. We add a veto to skip, to ensure th a t th e value of u is zero. In order to ensure th a t enter does not inadvertently match, we add a veto to enter stating th a t u must be greater than zero. If u is some value greater th an one, then it will be necessary to cycle back from rE n d to r S ta r t. In order to be able to count the num ber of repetitions, we create a counter cu, and initialise it in enter. To cause r to repeat, we add a transition named repeat to the grammar, and give it th e same symbol as the enter transition:
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4.4. Im p lem en ta tio n N o tes
71 b 0= = u
skip
u>0;cu=0 enter
prev
exit
rStart
rEnd
next
Figure 4.3: An autom ata modified to handle a maximum dynamic cardinality The structure of an autom ata th a t handles dynamic maximum cardinality. in this case, a. To prevent repeat from causing the region to match more often th an it should, we add a veto limiting cu to be less th an u. After these changes, we arrive at th e autom ata shown in Figure 4.3. An example parse of a maximum-respecting auto m ata is shown in Figure 4.5.
H andling M in im u m C ardinality Now th a t we have an autom ata th a t can handle maximum cardinality, we consider minimum cardinality. We want to set a lower bound I for our rule r to repeat. If r matches less th a n I times, we will not allow the parser to leave the portion of the autom ata th a t maps to r. After r has m atched I or more times, we will perm it the parser to leave th e region mapping to r. The only way out of the region is through the transition exit. We prevent the parser from following exit at inappropriate times by adding a veto th a t checks if the repetition counter cu is greater th a n or equal to I. Figure 4.4 shows an autom ata modified to handle an upper and lower bound for a region. Figure 4.5 shows an example of dynamic cardinality in a simple autom ata. Figure 4.6 shows the same parse, b u t with an invalid input string.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4.4. Im p lem en ta tio n N o tes
72 b 0==M
skip
u>0;cu=0
cu > = l & cu<=u
enter
exit
prev
rEnd
rStart
next
Figure 4.4: An auto m ata modified to handle a minimum and maximum dynamic cardinality The structure of an autom ata th a t handles both dynamic minimum and maximum cardinality. b
0=u skip
u>0;cu=0 enter
R egister u= 2 cu 0
region
next
In p u t
Current S ta te
a
prev
E vents P foiiows enter, increments cu. Sets current state to region.
I 11 h-> 10
prev
exit
a
region
P foiiows repeat, increments c„. Sets current state to region.
u= 2 cu 2
b
region
P follows exit. next.
Sets current state to
Figure 4.5: Example of parsing a dynamic cardinality. Register u is the upper bound on the cardinality for th e only region. Register cu is the counter used by the dynamic element. The input string is “aa&” , and the autom ata being parsed is shown above. M aintaining th e C oun ter Stack Each counter resides on the counter stack. Counters are pushed onto th e counter stack when the parser enters a dynamic region. Once in th e region, all vetoes and
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4.4. Im plem en tation N o te s
73 0=u skip
u>0;cu=0
cu>=l & cu<=u
enter
exit
prev R e g iste r u = '6 I= 3 cu 0 u = 3 1= 3 Cu 1 u —3 I= 3 cu — 2
region
next
In p u t
C u r r e n t S ta te
E v e n ts
a
prev
P follows enter. Assigns 0 to cu. Sets current state to region.
a
region
P follows repeat. Increments cu. Sets current state to region.
b
region
P cannot find an exit from region. repeat will not m atch because the input b does not m atch a. exit will not match because cu is less than I. P rejects the input.
Figure 4.6: Example of the parser rejecting an invalid input string on a dynamic cardinality. The configuration of the parser is similar to th a t of Figure 4.5, b u t it has a lower bound of three repetitions in the region,. The input string is “aa&” . actions operate on the topm ost counter value. When the parser leaves the region, it pops the counter off the top of the counter stack. So far, we have left the stack maintenance actions out of our autom ata for space reasons. Figure 4.7 displays the push and pop operations. All reads from the counter cu should be considered peek operations onto the top of the counter stack.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
74
4 .4 . Im p lem en tation N o te s
b 0==u skip
prev
u>0;cu=0 PUSHCTR(cu)
cu>=l & cu<=u POPCTR(cu)
enter
exit
rStart
rEnd
next
Figure 4.7: An autom ata modified to handle a dynamic cardinality, and m aintain the counter stack The complete structure of an autom ata th a t handles dynamic cardinality, and counter stack maintenance.
4 .4 .5
D y n a m ic a lly C h a n g in g T e x t
Handling dynamic text is easier than handling dynamic cardinality. Every parser P is given two modes: a “normal” mode for parsing input using the autom ata, and a “register” mode for parsing input using the contents of a special text register. W hen in normal mode, P behaves exactly as we have discussed. W hen in register mode, P parses from a string stored in a special register. Register mode exists entirely outside of th e autom ata. It causes th e parser to stop in the middle of a transition, and attem pt to read the dynamic text. As subsequent inputs are read, the dynamic text is checked, bypassing the autom ata. If the text matches, then the parser returns to the transition it stopped in, and follows the remainder of the transition to the next state.
The parser stops in the middle of
the transition because there may be actions th a t need to be executed between the acceptance of the text in the register, and the parser’s entry into the subsequent state. Similar to dynamic cardinalities, we have to make modifications to the autom ata. We must consider two cases when handing dynamic text: th a t the te x t is empty, or th a t it contains more than one character. If the text is empty, we provide a transition
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4.5. D esig n D ecisio n s
75 a len(t)=0 skip DYN ENTER
dynamic
prev
exit
nextl
next2
Figure 4.8: An auto m ata th a t parses dynamic text An autom ata th a t parses dynamic text. The asterisk (*) on the d ynam ic transition indicates th a t transition will m atch any input, deferring the decision to the DYN_ENTER action. named skip th a t allows us to avoid the dynamic text, which may only be followed if the tex t length is zero. We also consider the case where the text contains one or more characters. In th a t case, we an notate a transition named d ynam ic with th e special DYN_ENTER action, and connect it to the next state as if it were a normal transition. The DYN_ENTER action switches P from normal mode into register mode. In register mode, P m aintains a pointer to th e register containing the dynamic tex t, and a counter for its progress through th e text. It also tracks the transition th a t contains the DYN_ENTER annotation. W hen th e counter reaches the end of the text, th e parser drops out of register mode, sets its current state to be the destination of the DYN_ENTER transition, and continues executing. Figure 4.9 illustrates a successful parse.
4.5
D esig n D ecisio n s
The overall architecture of qcap is simple. It is designed as a layered network stack. In designing and building the library, an emphasis was put on creating a useful ap plication level parser, rather th a n concentrating on design of lower level layers.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4.5. D esign D ecision s
76 a len(t)=0 skip DYN ENTER
dynamic prev
exit
nextl
R egister
Input
C urrent S ta te
t = “x y " post = 0
X
prev
t = “xy" post = 1
y
d ynam ic
t = “xy" post = 0
a
n ext
next2
E ven ts P follows dynam ic. DYN_ENTER halts execution, and switches to register mode. P increments post, and tests to see if post = len{t). P tests t\postj = y. Since it does, P stays in register mode. P increments post , and tests to see if post = len(t). Since it does P drops back to normal mode, sets post = 0, and sets th e current state to n e x tl. P follows d ynam ic. Increments cu. Sets current state to next2.
Figure 4.9: Example of a parser P accepting “xya”. The text in the dynamic text register t is “xyv .
4 .5 .1
D isc a r d in g t h e T o k en izer
Some parsers have preprocessors th a t consume input called tokenizers, th a t join sym bols in the input text into tokens. A token is an element of the input th a t is known to have special meaning, such as keywords in a programming language. Tokens can be annotated with the input text, to give further meaning to the parser. For example, a simple programming language may tu rn the input “if a then V into a sequence of four tokens: IF , V A R (a), T H E N , and V A R (b). The IF and T H E N tokens denote keywords. The V A R token is param eterized with th e nam e of the variable th a t it corresponds to.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4.5. D esign D ecisio n s
77
Tokens are typically used to simplify the life of a hum an writing a parser. Tools such as flex[24] are used to tokenize input before the tokens are passed on to the parser, which m ay be specified using a language like bison[23]. If the parser P for some language L uses a tokenizer, then P consumes a slightly different alphabet from L. qcap is not a hum an parser writer. The qcap parser generator can generate an autom ata from a grammar easily. The autom ata does not require input text to be preparsed and simplified. In fact, such a “simplification” would make the creation of a parser much more difficult, as the N PG specification for a protocol would have to be preparsed to generate tokens.
4 .5 .2
C h o o s in g C allb ack s for D a t a R e tu r n
Developers th a t use the qcap API will immediately notice th a t d a ta is only m ade available to th e application via callbacks. This approach was attractive for a number of reasons: • It allows qcap to perform its own cleanup after th e application has processed an event. • It allows qcap to keep state on th e stack between events. Pointers to stack d a ta can even be handed to the application. This minimises the work necessary to copy d a ta into heap d ata structures (saving time and programming effort), and allows for some simplifications in memory management. • qcap produces four different kinds of events. It is unclear how different event types could be returned through a single function, w ithout overloading a retu rn type.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4 .5 . D esign D ecisio n s
78
• The connection between subscriptions and the resulting events is very explicit. Of course, there is a cost associated w ith using this style of subscription interface. It requires the application to be structured in a nonintuitive manner th a t may force th e use of threading for interactive applications. However, given th a t a request for new data from qcap may block for a long period of time, interactive applications would have to be m ultithreaded anyway. An alternative approach would see the application repeatedly requesting the next event, until the event stream is exhausted. There are three drawbacks to this ap proach: the application must deallocate the returned structures, four different types of d a ta must be returned through the same interface, and it forces qcap to use th e heap to store state between calls (instead of using the stack). In the author’s mind, the latter two costs outweigh the benefit of allowing the application to request events.
4 .5 .3
C h o o sin g a N e tw o r k S ta c k
The basis of the qcap IP and T C P network stack is a modified version of l i b n i d s [59]. We chose to use li b n id s because large portions of its code base are lifted from the Linux 2.0.36 kernel2, leading us to believe th a t lib n id s should be relatively fast and correct. During integration, however, we discovered th a t the li b n id s architecture does not make small change easy. Two alternatives also presented themselves: implementing the network stack by hand, or using another network stack. Writing the network stack by hand was not an attractive proposition, as the Internet protocol stack is complex. We did not wish to spend development tim e working on a problem th a t had already been solved. 2See the file CREDITS in the li b n i d s distribution.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4.5. D esig n D ecisio n s
79
We could have used another protocol stack instead of li b n id s . In retrospect, this may have been a b etter approach, as modifying lib n id s proved to be more time consuming than originally intended. The other stack th a t the author considered was the x-kernel[49], which is a network stack sim ulator from the University of Arizona. Before implementation, th e author feared th a t the xkernel may not be fast enough to handle large volumes of data. After implementation, the author was willing to review his hypothesis. If we were to reimplement the network stack, we would not use lib n id s . Instead, we would likely use th e x-kernel, or implement the stack ourselves.
4 .5 .4
C h o o sin g a P arser A r c h ite c tu r e
There are at least three classes of parser th a t we may employ. The classic parsers, the ones th a t get the most play in books on parsing[4, 19, 26], are LL and LR parsers. Both classes of parser share the same foundation: they are based on deterministic finite autom ata, they read every character in an input stream exactly once, and they usually have some am ount of look ahead, qcap uses an entirely different class of parser: a generalized parser. We chose not to use an LL or LR parser because of the way they handle ambiguity. An ambiguity in a gram m ar occurs when the parser receives an input, and there are two or more valid interpretations of the grammar. LL and LR parsers deal with ambiguity by using lookahead. W ith lookahead, parsers may delay a decision for a fixed amount of input.
in -a -h o u s e = " k itten " / "kitchen"
Figure 4.10: A trivial example of an ambiguous gram m ar in NPG.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4.5. D esig n D ecision s
80
A trivial example of an ambiguous grammar is shown in Figure 4.10. The first three characters of the rule < in -a -h o u s e > could belong to either half of the alter nation. A parser is unable to ascertain which p ath of the alternation to take until the fourth character (either a t or a c) resolves the ambiguity. A standard LL or LR parser would require a lookahead of three characters to determine which path should be followed. Lookahead is decided when the parser is being built, and is compiled statically into the executable. However, qcap deals with grammars th a t change at runtime. Figure 4.11 shows a gram m ar whose lookahead can only be ascertained a t run time.
m essage = b lo b -te m p la te "!" (b lob / l*70d65-90 "!") set { b lo b # te x t = b lo b -te m p la te ;
} b lo b -te m p la te = l*% d65-90; b lob =
Figure 4.11: An example of an infinitely ambiguous grammar using NPG. Unlike LL and LR parsers, generalized parsers run over autom ata th a t are much less optimised. A generalized parser has an autom ata and a set of subparsers. Outside of ambiguous sections, there is one subparser per parser. When a generalized parser hits an ambiguous section of the grammar, it spawns a subparser for each possible path. Each of the subparsers receive every character of input and progress down their own path. Whenever a subparser rejects an input, it is discarded. If the parser only has one subparser, and it rejects, then the input is rejected. If any of the subparsers accept, then the input is accepted. We selected a generalized parsing algorithm because of its flexibility. It can be slower th a n other types of parsers and it performs more comparisons than are neces
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
4.5. D esig n D ecisio n s sary with other techniques, b u t it handles dynamic elements properly.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
81
C hapter 5 E valuation To show th a t the N PG and qcap operate as expected, we dem onstrate three attributes of NPG and qcap: (1) th a t the gram m ar and implementation create “correct” parsers, (2) th a t the implementation is at least as expressive and efficient as existing tools, and (3) th a t the parser and gram m ar are easy to use. This chapter provides results of our tests of NPG and qcap. The language is, in the opinion of the author, very easy to use. The library proved to create correct parsers. However, even though qcap is able to parse inputs properly, it is unusably slow. The remainder of this chapter summerizes our experiences with NPG and qcap, and compares a definition of an H T T P parser in NPG to three definitions of an H TTP parser in general purpose code.
5.1
C orrectn ess o f P arser and Im p lem en ta tio n
Our parsing approach is able to correctly parse protocols. We ran a parser generated from the NPG specification of H T T P requests over 3,598 requests th a t we gathered from the network connection a t our lab. The parser correctly accepted valid requests,
82
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
5.1. C orrectn ess o f P arser and Im p lem en ta tio n
83
while rejecting invalid requests. The H TTP requests were from five hour-long samples taken daily a t 14:00, starting on June 12, 2006. The samples were captured on the outside interface of th e CCSL gateway. Many of the requests were from the outside, aimed a t a Webserver from the M ath Departm ent whose traffic we are party to; while others were from com puters within our lab, sent to the outside world. Since the volume of requests was so high, we were unable to validate th a t all requests th a t were accepted were proper HTTP. Instead, we took a random sampling of 50 requests, and inspected them ourselves. The author was satisfied th a t each file sampled was proper HTTP. Our assertion th a t the parser is correct is further supported by the requests th a t parser rejected, which shall be discussed below. The parser rejected 53 streams, informing the author of th e character th a t caused the rejection. In each case, the rejection was for a valid reason. The most common cause for rejection was an illegal character inserted into the
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without perm ission.
84
5.2. U sab ility
5.2
U sa b ility
Even though the qcap library is incomplete, we are able to evaluate and discuss the usability of the NPG and the qcap API. We argue th a t the Network Protocol G ram m ar is a promising m ethod for parsing protocols for three reasons: • Declarative definitions of protocols are easy to write, understand, and debug. In our experience th e NPG definition was easier to manipulate than im perative definitions. • The hierarchical nature of the N PG allows a programmar to ignore portions of the gramm ar th a t are outside his or her scope of interest. The relationship between rules is immediately apparent, given th a t NPG only supports rule reference operators and the s e t clause. • The code generated from the definition has the potential to be as efficient, and much less error prone than imperative definitions. • A declarative definition of a protocol can be transformed to fulfil many tasks. Imperative definitions are more specialised, they are much more difficult to transform. Even though the NPG is very usable, th e implementation of th e parser in qcap proved to be somewhat disappointing, due to speed problems.
We discuss those
problems in detail in the next section.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
5.3. Speed o f Im p lem en ta tio n
5.3
85
S p eed o f Im p lem en ta tio n
Although the parsing algorithm produces correct results, it runs a t rates far slower th a n desired. Ideally, the qcap parser would be able to process tens of megabytes per second on commodity hardware. T h at is not the case. The qcap parser currently processes d ata slightly faster th an 5.3 kilobytes per second. In order to evaluate the speed of the qcap parser, we ran the H T T P parser against a 249,060 byte series of H T T P requests, and tested the amount of tim e spent on the processor with the tim e command. Averaged from 10 runs, qcap took 46.594 seconds to load the H TTP definition, parse 249K, and exit; leading us to believe th a t qcap can parse H TTP requests at a rate of roughly 5345 bytes per second. Through profiling and algorithmic analysis, we have found multiple causes for slow processing. They include delayed com putation, our nonstandard im plem entation of a generalised parser, and interpretation. In th e rest of this section, we detail the issues we discovered, as well as addressing possible solutions.
5 .3 .1
S lo w d o w n D u e t o G e n e r a lise d P a rsin g
Finite autom ata may be transformed from one form to another w ithout changing im portant properties. The process of generating an autom ata th a t can be used with an LL or LALR parser from a nondeterministic finite autom ata is an example of such a transformation. The advantage of working with a generalised parser is th a t it can use an unmodified nondeterministic finite autom ata w ithout modification. The drawback of using a generalised parser is th a t the underlying NFA is unoptimised, meaning th a t unnecessary com putation may be done during a parse. An example of this is the creation of new parsers on static ambiguous sections. S tatic ambiguous sections are areas of ambiguity th a t are expressed in the non
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
5.3. S p eed o f Im p lem en ta tio n
86
dynam ic portions of a grammar. Such ambiguous sections may be detected before input is received, and the NFA m ay be transformed to delay a parsing decision until after th e ambiguous section is passed. However, by using a generalised parser we delay th e detection of ambiguity until input is being processed, thereby slowing down the parse. If we consider the slowdown due to generalised parsing on a per-token basis, the slowdown can be expressed as 0 ( p * t * c), where p is the number of active parsers, t is th e number of transitions leaving the current state, and c is the cost of traversing a transition. Since there is a high degree of variability in the values of p, t, and c, we only consider their worst case values: the largest number of parsers th a t can be active due to a static ambiguity; th e largest number of transitions leaving any state; and th e largest number of actions and vetoes present on any transition. We can improve the speed of th e parse by detecting static ambiguities before the parse begins and deferring th e emission of parse information until the input resolves the ambiguity. In doing so, we are converting the nondeterministic au to m ata into a deterministic autom ata. The result would remove the p multiplier from the cost of executing each character: 0 ( t * c). The cost of th e parse time speed improvement is an extra compilation step after th e grammar has been loaded, b u t because we can serialise the gram m ar after it has been compiled, and store it in its compiled state, we do not consider this to be an overt burden. Aho et al provide the subset construction algorithm for detecting ambiguities in [4], th a t is sufficient to perform these tasks. Note th a t such a change means the parser needs to be able to be able to delay actions until enough input has been received to resolve the ambiguity.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
87
5.3. S p eed o f Im p lem en ta tio n
b 0==u skip
prev
u>0;cu=0
cu>=l & cu<=u
enter
exit
rStart
rEnd
next
Figure 5.1: An autom ata modified to handle a minimum and maximum dynamic cardinality The structure of an autom ata th a t handles both dynamic minimum and maximum cardinality.
5 .3 .2
N o n sta n d a r d I m p le m e n ta tio n o f G e n e r a lise d P a r s in g
The current parser generator builds nondeterministic finite autom ata in a m anner th a t is more complex than necessary. Whenever there is a symbol th a t repeats, the last repetition is unrolled and annotated with an end-symbol action. This means th a t every pass through the repetition causes a new parser to be generated unnecessarily. Logically, the parser acts in a m anner consistent w ith the autom ata shown in Fig ure 5.1, b u t the internal representation is shown in Figure 5.2. The extra transition, named unrolled is necessary because it carries an end-symbol action. This approach was taken because actions immediately modify the state of the parser they run upon. We did not wish to allow actions to be delayed, because th a t would increase the complexity of the parser implementation. This representation causes an ex tra parser to be generated every time th e repeti tion occurs, as one parser heads back on repeat while th e other follows unrolled. The next token causes one of the two parsers to be discarded. Generating and deleting a parser are unnecessary operations th a t occur every tim e a symbol repeats; adding a constant cost factor to every pass through a repeating portion of the finite autom ata.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
5.3. Speed o f Im p lem en ta tio n
88
b
0==u skip
cu
cu>=l & cu<=u
enter
prev
unrolled
rStart
exit
rEnd
next
Figure 5.2: The internal representation of repeating symbols Internally, qcap unrolls the last repetition of a region w ith a cardinality greater th an one, resulting in the transition, unrolled being added to th e finite autom ata. We can improve efficiency be removing the unrolled transition, and moving the end-symbol action onto the exit transition.
5 .3 .3
In te r p r e ta tio n
The existing parser generator builds a nondeterministic finite autom ata annotated with vetoes and actions. At parse time, th e parser traverses the finite autom ata. The author feels th a t such an approach is inherently slower th a n generating executable code that can be compiled and then run. Executable code would not necessarily store the finite autom ata explicitly, but would likely store th e autom ata implicitly in its structure. Running generated code should be faster than interpreting a finite autom ata, as the interpreter must loop over d ata contained in th e autom ata (requiring both looping instructions and tests to see if th e d a ta in question has been exhausted). The author assumes th a t replacing the interpreter with a compiler would result in a speed improvement. The exact speedup is unclear, however. In the next Section we compare the NPG definition of a protocol to multiple imperative definitions of the same protocols. Our comparison takes the form of a
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
5.4. C ase S tu d y
89
case study.
5 .4
C ase S tu d y
In order to provide perspective in the comparison of the N PG to other methods for writing protocol parsers and analysers, we compare the definition of an NPG parser to the definition of parsers in general purpose code. We target the client side2 of H T T P [17] as our protocol of choice, because there many parsers are available for comparison. We compare t h t tp d , Wireshark, and Apache to a parser defined in NPG. All three of th e non-NPG parsers define H TTP implicitly in general purpose code, making our comparison artificial, as there are few commonalities between the declarative NPG definition and the parsers in question. We focus our comparison on the nature of the parsers, both qualitatively (in terms of th eir general structure, and coding idioms used), and quantitatively (in term s of lines). For each example, we will direct our attention to one representative part of the parser, to give th e reader a feel for the code in question.
5 .4 .1
R e v ie w o f H T T P
The server side of H TTP conversations consist of a series of requests. Each request has three parts: a request line, headers, and a body; as shown in Figure 5.3. The request line has a
Reproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
90
5.4. C ase S tu d y R equest
= r e q u e s t - lin e *header CRLF [body]
r e q u e s t - li n e method v e r s io n
= method SP u r l SP v e r s io n CRLF = "P0ST"c / "GET"c / "HEAD"c = "HTTP/"c 1+DIGIT 1*DIGIT
header
= ALPHA * (ALPHANUM / "-") * (ALPHANUM / WS / PUNCTUATION) CRLF
body
Figure 5.3: A fragment of NPG describing an H T T P request. Note th a t the produc tion
5 .4 .2
Im p le m e n ta tio n s o f H T T P P a rser s
This section compares an H TTP parser defined in the network protocol gram m ar to three other parsers. In each case, we will com pare the segment of code used to parse the H T T P
5 .4 .3
A n H T T P P a rser in N P G
The H T T P specification uses a nonstandard version of ABNF, meaning th a t creating the ABNF version of the protocol was more complex than expected. The changes are
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
91
5.4. C ase S tu d y fairly simple: HTTP changes the ABNF alternation operator from “/ ” to
allowing
linear white space to occur between any elements in a sequence, and the addition of a list operator th a t implicitly allows commas in sequences. Most annoyingly, the RFC does not gather all of the ABNF together in one place, meaning th a t a human must dig through the document, copying tiny snippets of specification into one file. Porting the changes from the H TTP RFC to canonical ABNF was trivial drudge work, taking roughly four hours. Adding the NPG construct (to handle the C ontent-T ype header) took a few minutes. The most complex portion of the task was testing, which took an additional five hours. The resulting definition was 501 lines. To get an idea of the nature of the changes necessary to port the H TTP specifi cation to NPG, we consider Section 5.1 of the RFC, which defines the first line of an H TTP request. See Figure 5.4 for the text from th e RFC. In order to port this snippet of ABNF to NPG, we fix the syntactic errors, modify the gram m ar to meet the constraints supplied in th e text, and then write the result to a file. The errors are trivial to fix, we simply substitute the ABNF alternation operator (/) for the nonstandard pipe (|) th a t was used in the text. The prose places an additional constraint on th e grammar: th e
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
92
5.4. C ase S tu d y 5 .1 R eq u est-L in e The R eq u est-L in e b e g in s w ith a method to k e n , fo llo w e d by th e Request-URI and th e p r o to c o l v e r s io n , and ending w ith CRLF. The elem en ts are sep a r a te d by SP c h a r a c te r s . No CR or LF i s a llow ed ex cep t in th e f i n a l CRLF sequence.
R eq u est-L in e = Method SP Request-URI SP HTTP-Version CRLF 5 . 1 . 1 Method The Method tok en in d ic a t e s th e method t o be perform ed on th e r e so u r c e i d e n t i f i e d by th e Request-U R I. The method i s c a s e - s e n s i t i v e .
S e c tio n OPTIONS" S e c tio n GET" HEAD" S e c tio n S e c tio n POST" S e c tio n PUT" S e c tio n DELETE" S e c tio n TRACE" S e c tio n CONNECT" _ exten sion -m eth od ex ten sio n -m eth o d = token
Method
9 .2 9 .3 9 .4 9 .5 9 .6 9 .7 9 .8 9 .9
Figure 5.4: Snippet of RFC 2616[17] describing the first line of an H TTP request. Underlined portions of prose indicate constraints th a t modify the ABNF definition. Underlined portions of ABNF indicate syntactically invalid portions of the definition.
not go into detail to explain it.
We include it to show th a t there is no hidden
complexity to the NPG parser. The programmer does not pay for protocol simplicity by having to navigate a complex API.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without perm ission.
93
5.4. Case S tu d y ; S5. 1 - R eq u est-L in e R eq u est-L in e = Method SP Request-URI SP HTTP-Version CRLF ; S 5 . 1 . 1 - Method Method
= / / / / / / /
"OPTIONS"c "GET"c "HEAD"c "P0ST"c "PUT"c "DELETE"c "TRACE"c "C0NNECT"c
Figure 5.5: Snippet of the NPG gram m ar for HTTP, as m apped from Figure 5.4. Underlined portions denote text changed from the ABNF definition in the RFC.
qcap_t * qp; qcap_npg_handler_add( qp, " h ttp " , "Method", m ethod_callb ack , NULL);
/ * The c a llb a c k t o be t r ig g e r e d whenever an HTTP
Figure 5.6: Code to load and run an NPG specification. The function qcap_npg_handler_add() adds a callback to the given qcap session. The NPG file contains m eta-inform ation informing qcap which side of a stream the callback should be attached to, as well as the standard p ort numbers in use.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
94
5.4. C ase S tu d y
5 .4 .4
t h t t p d ’s H T T P P a r se r
th t t p d 3 is a small Webserver. According to its web page, it is a “simple, small, portable, fast, and secure H TTP server.” We choose to compare t h t t p d ’s parser against NPG because it conveniently locates all of its parsing code in one place (unlike many other servers). The t h t t p d parser is roughly 500 lines of C code. It uses the POSIX stan d ard s tr p b r k O , s tr s p n O , and strcm pO functions to recognise known strings. For th e most part, it acts as a backtracking parser, repeatedly comparing input to expected values until it finds one th a t matches.
When text fields of a specific form at are
expected, they are pulled apart, byte by byte. The t h t t p d parser is longer (in lines of C) than the NPG specification for th e server side of HTTP. Furthermore, t h t t p d parses a subset of th e H T T P protocol. A fragment of t h t t p d ’s code for parsing the H TTP
It is not overly
complex, although it is much more verbose th an the NPG definition. According to th e t h t t p d release notes4, there were only a handful of changes to the request parsing code, either in term s of bug fixes or new features added. However, 3h t t p :// w w w .a c m e .com/software/thttpd 4h t t p : / / w w w . a c m e .com/software/thttpd/\#releasenotes
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
95
5.4. C ase S tu d y /* Get th e end of th e method * / char * m ethod_str = b u f g e t s ( he ) ; char * u r l = str p b rk ( m ethod_str, " \0 12\015" ); i f ( u r l == (char*) 0 ) { re tu r n -1 ;
} *url++ = ’ \ 0 ’ ; /* Repeat f o r URI and HTTP v e r s io n * / P arse the r e s t o f the r e q u e s t
line
...
/ * Determine which method th e c l i e n t has se n t * / i f ( strcasecm p ( m eth o d _ str, h ttp d _ m eth o d _ str( METHOD_GET ) ) == 0 ) hc->method = METHOD_GET; e l s e i f ( strcasecm pC m ethod_str, h ttp d _ m eth o d _ str( METHOD_HEAD ) ) == 0 ) hc->method = METHOD_HEAD; e ls e i f ( strcasecm pC m ethod_str, h ttp d _ m eth o d _ str( METH0D_P0ST ) ) == 0 ) hc->method = METHOD_POST; The f o l l o w i n g m e t h o d s w e r e ad de d t o g i v e t h t t p d t h e same c a p a b i l i t i e s as t h e NPG grammar
e l s e i f ( strcasecm pC m ethod_str, hc->method = METHOD^OPTIONS; e l s e i f ( strcasecm pC m ethod_str, hc->method = METHOD_PUT; e l s e i f ( strcasecm pC m ethod_str, hc->method = METHOD_DELETE; e l s e i f ( strcasecm pC m ethod_str, hc->method = METHOD_TRACE; e l s e i f ( strcasecm pC m ethod_str, hc->method = METH0D_C0NNECT; e ls e { r e tu rn -1 ;
httpd_m ethod_str( METHOD.OPTIONS ) ) == 0 ) httpd_m ethod_str( METHOD_PUT ) ) == 0 ) httpd_m ethod_str( METHOD_DELETE ) ) == 0 ) httpd_m ethod_str( METHOD_TRACE ) ) == 0 ) httpd_m ethod_str( METH0D_C0NNECT ) ) == 0 )
} Figure 5.7: Code from th ttp d (v ersio n 2.25b) for parsing the m ethod of an H T T P request. Error handling code has been removed. The function h ttp d _ m eth o d _ str() does a lookup for the string representation of the requested method. Only the first three methods are present in the original code. The remainder were added to provide parity with the NPG specification. a number of buffer overflows have been detected in t h t t p d ’s parsing code.5 5http://www. securityf ocus.com/archive/17342584
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
5.4. Case S tu d y
5 .4 .5
96
W ir e sh a r k ’s H T T P P a rser
W ireshark6 is a datagram oriented protocol analyser. It has an H T T P parser, capable of reading H TTP request lines and headers from individual datagram s and sequences of datagrams. The H T T P parser is tightly coupled with th e code for reporting the parse results. W ireshark’s H TTP parser is roughly 1027 lines long (including extensive com ments and some reporting of parse results). It handles grammars outside of the server side HTTP specification, such as protocols th a t masquerade as HTTP, and client side responses. It is the au th o r’s estimation th a t the extra code for dealing w ith those other grammars numbers no more than 200 to 250 lines. Similar to th t tp d , the parser backtracks, testing a set of known possibilities on the input until one matches. The portion of the W ireshark H TTP parser responsible for parsing the H TTP m ethod is shown in Figure 5.8. Wireshark uses a similar approach to th t tp d , but instead of trying every legal H T T P method sequentially, it gets th e length of the method, and only compares th e received methods to expected methods of the same length. The approach should be faster than t h t t p d ’s linear search, as it involves fewer string comparisons. Although it would be slower than the optimal speed provided by a non-backtracking parser (as could be generated from the NPG definition). The author found W ireshark’s code harder to understand than th t t p d , due to the blurring of the line between the parser, and the reporting structure. It is unclear which calculations are necessary to parse incoming datagram s, and which calculations are necessary for providing output. W ireshark’s H TTP parser was noted as containing minor vulnerabilities7; parsers h t t p : / / s e c l i s t s . o r g /lis t s /v u ln - d e v /1 9 9 9 /N o v /0 0 1 7 . html 6T he HTTP parser described here is contained in the Ethereal Subversion repository. The version of the parser is 17769, and can be found at h t t p : //a n o n s v n .e t h e r e a l.c o m /v ie w c v s /v ie w c v s .p y / tr u n k /e p a n /d is se c to r s/p a c k e t-h ttp .c ? r e v = 1 7 7 6 9 \& v ie w = a u to . 7h t t p : / / e v e . m i t r e . o r g /c g i-b in /c v e n a m e . cgi?name=CVE-2005-2361
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
97
5.4. C ase S tu d y i n t l i n e l e n = tvb_f in d _ lin e _ e n d (tv b , o f f s e t , tvb _en su re_len gth _rem ain in g(tvb , o f f s e t ) , & n e x t_ o ffse t, FALSE); /* OK, does i t lo o k l i k e an HTTP r e q u e st or resp on se? is_ r e q u e st_ o r_ r e p ly = is_ h ttp _ r e q u e st_ o r _ r e p ly ( (c o n st gchar * ) l i n e , & http_type, & r e q r e sp _ d isse c to r ); i f (is_ r e q u e st_ o r _ r e p ly ) g o to i s J i t t p ;
*/
s t a t i c in t isJ h ttp _ r e q u e st_ o r _ r e p ly (c o n st gchar * d a ta , h ttp _typ e_t * ty p e, R eqR espD issector * r e q r e s p _ d is s e c to r )
{ / * Look f o r th e space fo llo w in g th e Method.
*/
The o r i g i n a l c o d e c o n t a i n e d a l o o p s e a r c h i n g f o r a s p a c e
c o n st guchar * p tr = s tr p b r k (d a ta , " "); i f (p tr == NULL) r e tu r n 0; i n t le n = p tr - data; sw itc h ( le n ) { ca se 3: i f ( strn cm p (d ata, "GET", le n ) == 0 I I strn cm p (d ata, "PUT", le n ) == 0) { *type = HTTP-REQUEST;
} break; c a se 4: i f ( strn cm p (d ata, "HEAD", le n ) == 0 I I stm c m p (d a ta , "POST", le n ) == 0) { *type = HTTPJtEQUEST;
} break;
Figure 5.8: P art of the W ireshark H TTP parser. Error handling code has been removed, as has code unrelated to parsing. There are more methods supported in the original code, but non-HTTP related methods were removed.
h t t p :/ / e v e . m it r e . o r g /c g i-b in /c v e n a m e . cgi?name=CVE-2004-1141
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without perm ission.
5.4. C ase S tu d y
98
for other protocols have contained more serious vulnerabilities[15].
5 .4 .6
A p a c h e ’s H T T P P a r s e r
Apache is a popular open source Webserver. According to NetCraft, it was used to host 61.25% of all websites on the Internet in July, 2006.8 It is highly optimised and designed for easy extensibility through plugins. As such, its H T T P parsing code is a mix of deferral and optimised reading. Whereas Wireshark mixes a great deal of reporting code with its parser, Apache mixes a large number of memory allocation decisions and defensive coding practices with its parser. The H T T P request parser operates in two passes. The first pass reads the request line and headers into in-memory structures. At the end of the first pass, the m ethod, URL, and protocol are known, and th e headers are stored in a general purpose header table. In th e second pass, the headers are parsed as necessary. Because th e second pass is incremental and spread throughout the codebase, we cannot make an accurate estimate of its size. The first parse, however, takes roughly 521 lines. We continue our comparison of parsers by examining the
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
99
5.4. C ase S tu d y
a neophyte, as input reading and parsing are split between two files in different p arts of the source tree, and much of the reading uses Apache-specific d ata structures.
Acquire the r e q u e s t lin e
rv = a p _ r g e tlin e (& (r -> th e _ r e q u e st) , (a p r _ siz e _ t) (r -> s e r v e r -> lim it_ r e q _ lin e + 2 ) , & len, r , 0 , b b ) ; i f (rv != APR_SUCCESS) r e tu r n 0; Find the s t a r t
o f t h e met hod
r->m ethod = ap _getw ord _w h ite(r-> p ool, r -> t h e _ r e q u e s t) ; r->methodjnumber = ap_method_number_of (r->m ethod) ; P a r s e th e method
i n t le n = s tr le n (m e th o d ); sw itc h ( le n ) { ca se 3: s w itc h (m ethod[0 ]) { c a se ’P' : r etu rn (m eth od [l] == ’U’ k k m ethod[2] == ’T’ ? M_PUT : UNKN0WN_METH0D); c a se ’GJ: retu rn (m ethod[1] == JE’ && m ethod[2] == JT’ ? M_GET : UNKN0WN.METH0D); d e fa u lt: re tu r n UNKNOWN.METHOD;
} ca se 4: sw itc h (m ethod[0 ]) { ca se ’H’ : retu rn (m ethod[1] == ’E' && m ethod[2] == ’A’ k k m ethod[3] == ’D’ ? M_GET : UNKN0WNJ1ETH0D); c a se ’P ’ : r e tu rn (m ethod[1] == ’O’ k k m ethod[2] == ’S ’ k k m ethod[3] == ? M.POST : UNKN0WNJ1ETH0D);
Figure 5.9: The Apache 2.2.2 H T T P request m ethod parser. Error handling has been removed, and code has been shifted from various files into a single listing, and comments have been added.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
5.4. Case S tu d y
100
Apache’s H T T P parser has been the source of a number of vulnerabilities10. In terestingly, the vulnerabilities found by th e author seem to deal almost entirely w ith memory exhaustion. This may be a result of Apache’s two pass parser: since the first pass is very simple, only responsible for reading untrusted d a ta into memory, it does not appear as prone to assault as a full hand-coded parser.
5 .4 .7
C o m p a r iso n o f A p p r o a c h e s
The three parsers listed are very similar. They accept lines of text, and then attem p t to break the line into smaller chunks. The parsers differ slightly in their approach to dealing with th e smaller chunks: t h t t p d and W ireshark repeatedly test input against expected values, while Apache looks for individual characters th a t would uniquely identify the input. In each case, th e parser was longer th a n the complete ABNF specification for H TTP, while only parsing a subset of th e entire protocol. The only exception to this rule is NPG, which is the same size as th e original ABNF specification. N P G ’s succinct, declarative style provides a num ber of advantages over general purpose code: it is easier to m aintain, generated parsers can be efficient and secure, and specifications allow for reuse. In order to properly prove th a t NPG really has the following attributes, we would need to undertake a study comparing a num ber of parsers w ritten in different lan guages, to one w ritten in NPG. Ideally, such a study would involve a number of different teams of programmers, building software th a t would be used in some real istic environment. However, such a test is beyond the scope of this thesis. Instead 10URL: h t t p : / / l i s t s . g ro k . o r g . u k /p ip e r m a il/f u ll- d is c lo s u r e /2 0 0 4 -N o v e m b e r /028248. htm l h t t p : / / e v e .m it r e . o r g /c g i-b in /c v e n a m e . cgi?name=CVE-2004-0786 h t t p :/ / l i s t s . g r o k . o r g .u k /p ip e r m a il/fu ll- d is c lo s u r e /2 0 0 4 -J im e /0 2 3 1 3 3 .h tm l
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
5.4. C ase Study
101
of basing our argument on empirical testing, we m ust base it on reasoning about the nature of N PG ’s declarative style.
N P G Is Easier to M ain tain N PG is easier to m aintain th an general purpose code because it forces the programmer to explicitly state the parsing rules for a protocol. The NPG keeps rules separate from the code th a t uses the result of the parse, as well as the code th a t performs the parse.
In contrast, general purpose code forces programmers to mix parsing
rules with bookkeeping code necessary for a proper parse such as updating a state machine, buffer maintenance, incrementing counters, or managing repeated passes over th e input. The qcap implementation of NPG not only makes parsing code easier to maintain, b ut it provides an explicit interface between th e protocol parser and the application. By forcing the programmer to use callbacks to extract information from the parser, the boundary between the two domains is well defined. NPG enforces strong encap sulation, splitting the parser from the rest of th e code base. The size of NPG specifications makes the gram m ar superior to general purpose code. Because the NPG specification is small compared to hand-w ritten parsers, it should be easier for programmers to explore, understand, and modify.
G en erated parsers can b e efficient and secu re Parsers built from an N PG definition can be b o th secure and efficient, assuming th a t the parser generator is well designed. The N PG parser generator provides developers w ith these attributes a t minimal cost. G enerated parsers should be at least as secure as hand w ritten parsers because the author of the parser generator is able to design th e parser generator to avoid known
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
5.4. C ase S tu d y
102
vulnerabilities. As vulnerabilities in generated parsers are discovered, the author is able to improve the generator to prevent those as well. All parsers generated from th a t point on, should avoid th a t vulnerability. In contrast, hand w ritten parsers must be tested for vulnerabilities individually and must be improved individually. Similarly, generated parsers can be efficient. The author of the parser generator is able to optimise the generated code for speed as well as security. As other developers use the parser generator and submit patches or suggestions for optimisations, the parser implementation can be improved. In both cases, using a parser generator allows a developer to use th e work of others to build a parser th at is secure and efficient. Compared to the process of building a parser from scratch, profiling it, running security audits, and making improvements, there is much less work involved.
A n N P G sp ecification is fertile ground for reuse The N P G ’s declarative style is easy for programs to transform into other represen tations, making the definition fertile ground for further development. For example, we could use an NPG definition to create parsers in many different languages, or we could use the definition to automatically build test suites for servers. For other possible uses, see Section 6.2. It is difficult to transform parsers specified in general purpose code, as the parser must be disentangled from the rest of the code base, and the flow of control must be followed. The best hope for reusing the code in a general purpose parser is to tear it out and wrap it in an A PI so th a t other programmers may use it as a parser for their projects.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
5.5. E x p erien ce C reating G ram m ars
5.5
103
E x p erien ce C reatin g G ram m ars
Over the course of this project, the author has created NPG specifications for a number of existing protocols, including H TTP and SMTP. The experience of building the grammars leads the author to a number of conclusions.
5 .5 .1
R F C -d e fin e d G ra m m a rs A r e S e ld o m P ro p er A B N F
Each of the ABNF-specified protocols examined contained syntax errors. Usually, the problems were small errors, such as using illegal characters in rule names, or typos in rule references (often dealing w ith the case of the first letter in the rule name). Occasionally, as is the case w ith HTTP, the authors add new syntactic constructs to ABNF and modify existing ABNF constructs. Their changes are easy to port to correct ABNF, b u t the process is time consuming. The headaches involved in this process should not be overestimated, however. In the case of b o th H TTP and SMTP, the time taken to create a specification from an existing ABNF-like grammar was only a few hours. Testing took only a handful of hours. Compared to building a parser from scratch, the tim e taken is negligible.
5 .5 .2
R F C -d e fin e d G ra m m a rs M a y B e In c o m p le te
Just because a protocol is defined with a context free grammar, we cannot assume th a t the protocol is fully defined in grammar. The original protocol authors may have om itted “fiddly” portions of the formal definition, opting to define those in text instead. One example of this behaviour is found in the SM TP grammar. The SMTP does not provide a definition of the text following the DATA verb[52]. Neither of th e specifications th a t we ported provided a top level rule in the formal grammar.
In other words, the RFCs did not include an overall formal definition
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
5.5. E x p erien ce C reating G ram m ars
104
of a protocol session; instead, they specified individual interactions. As a result, the author had to determ ine the proper ordering of interactions and string them together. Such omissions complicate the process of gram m ar porting, b u t are not especially arduous.
5 .5 .3
A B N F Is In c o m p le te
The ABNF specification omits at least two semantics th a t are all but necessary for parser generation. First, ABNF does not define a m ethod for indicating which rule is the root of the grammar. If a gram m ar contains two or more rules, a parser generator is left guessing as to which rule should be the topm ost rule in the parser generator. Second, ABNF does not specify an end of stream token, meaning th a t there is no way to indicate when a stream is supposed to end. For some protocols (such as SM TP), where there are strings th a t indicate an end of stream in the protocol itself, this did not pose a serious problem. For other protocols such as H TTP11, th e end of the stream is a syntactically significant event. For th a t reason, we extended NPG to include a stream term ination term inal.
5 .5 .4
N P G R eq u ir e s B e t t e r P a r s in g D ir e c tio n
Both PacketTypes and GAPAL allow protocol specifications to contain assignments th a t direct parsing. In each case, th e language allows protocol authors to insert a structure th a t changes the rule associated with a rule name. In other words, when some rule < c u r r e n t> matches, it is able to change the rule associated w ith th e rule nam e < f u tu r e > . We call such direction dynamically directed parsing. 11Specifically H T TP sessions that do not include a length field for the response body.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without perm ission.
5.5. E xp erien ce C rea tin g G ram m ars
105
For example consider a protocol defined by Gset, shown in Figure 5.10. It uses a rule named < c o n tr o l> to set th e type of payload expected in < d a ta > . If the < c o n t r o l> is b in a ry , we wish to allow any bytes in < d a ta > ; b u t if < c o n tr o l> is t e x t , we wish to allow only ASCII upper-case characters.
a = l* c o n tr o l d a ta c o n tr o l = ("Type:" (" tex t" / "binary") / "Length:" l*70d48-57) %dl0 d ata = *7.d0-255
Figure 5.10: G ram m ar G set• Although not shown in this gram m ar, we wish to use the Type branch of th e < c o n t r o l> alternation to set the type of characters th a t are valid in < d a ta > . The standard m anner of defining such a parse is seen in the gram m ar GsetCFG, shown in Figure 5.11. As we can see, th e < c o n t r o l> rule of Gset m ust be reproduced in its entirety, in order to properly parse the input. So long as the list of Types we wish to support is small, then th e repetition is not onerous. If we wish to expand our types to include b in ary, hex, o c t a l , Unicode, and eb cd ic; the gram m ar will become annoyingly verbose.
a = t y p e l / ty p e2 t y p e l = l* ((" T y p e:
binary" / "Length:" l * ’/ .d48-57) 7,dl0) *7.d0-255
t y p e l = l* ((" T y p e :
te x t" / "Length:" l*%d48-57) 7,dl0) *%d65-90
Figure 5.11: parsing.
An explicit enumeration of types to emulate dynamically directed
Like dynamic cardinality and dynamic text, this is a problem of enumeration and verbosity. It is possible to use a context free gramm ar to represent this structure,
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
106
5.6. Sum m ary o f E valu ation
but it becomes onerous when there are too many possibilities to enumerate, or when there are too many productions th a t m ust be repeated for each enumeration. We call this problem dynamically directed parsing. We can extend NPG to
handle dynamically directed parsing
sion to the s e t clause. So
far, wehave supported two types of
w ith a trivial exten assignment:integer
assignment for setting cardinality, and string assignment for modifying terminals. We add another type of assignment, rule assignment, to modify the symbols associated w ith a rule name. To handle rule assignment, we allow a rule name to appear on the LHS of an expression. The RHS is allowed to contain the name of any other rule. When a rule < a > has < b > assigned to it, < a > will accept an input if and only if < b > will accept it. This allows us to rewrite G set as GsetNPG, shown in Figure 5.12.
a = l* c o n tr o l d ata c o n tr o l = ("Type:" (cT ext / cB inary) / "Length:" l*°/0d 48 -5 7 ) °/0dlO cT ext = { " te x t" } cBinary = {"binary"}
s e t { d a ta = dataT ext; } s e t { d a ta = dataB inary; }
d a ta = dataT ext = d65-90 dataB inary = dO-255
Figure 5.12: We can avoid explicitly enum erating values in dynamically directed parsing by using rule assignment.
5.6
Sum m ary o f E valuation
A complete evaluation of NPG and qcap requires empirical comparisons of qcap ’s generated parsers to hand-w ritten parsers; or, failing th a t, an evaluation of q cap ’s
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
5.6. Sum m ary o f E valu ation
107
correctness. Although the author cannot furnish the first, he does provide the second; showing th a t qcap is able to parse correctly, if slowly. We show th a t N PG ’s declarative nature makes it easy to use. A specification defined in NPG is shorter th a n an equivalent definition in general purpose code. Parser generators built for N PG can be optimised for speed and security, potentially lessening the am ount of effort th a t must be expended by the programmer. Specifying a protocol with NPG creates reusable final result, as the definition is not tied to a programming language or purpose; it can be transformed and used in ways not intended by the protocol designer.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
C hapter 6 D iscu ssion We have created a novel language, NPG, for specifying network protocols, th a t han dles common idioms in network programming. O ur gramm ar provides for th e concise expression of dynamic regions, which cannot practically be expressed using context free grammars. The language is a mixture of ABNF, one of the standard languages for specifying streaming network protocols, and the Packet Types packet filtering language. We have shown th a t the NPG can be used to specify a grammar th a t can be used to create a parser for network data. We have done this by building a parser generator into th e qcap network analysis library. The qcap library provides other novel functionality. It exposes all levels of the network stack to applications, cross referencing physical layer events to the transport and application layers, qcap is the only library th a t provides programm atic access to the higher layers of the network stack. In doing so, we have achieved our initial goal, which was to create a gram m ar for parsing stream oriented network protocols.
108
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
6.1. Im p lica tio n s o f R esu lts
6.1
109
Im p lica tio n s o f R esu lts
The qcap library is currently very slow, but the speed results for GAPA, provided by Borisov et al [8], indicate th a t the use of grammars to specify protocols for monitors is feasible. It is w orth noting th a t the GAPA framework interprets the gramm ar during the parse, ju st as qcap does. It seems likely th at the GAPA parser could be sped up further if th e gramm ar definition was compiled directly into machine code. Such speed gains could make the parser applicable to other applications.
6.2
O th er A p p lica tio n s o f th e N P G
The ability to write a gramm ar th a t can completely define a network protocol provides many opportunities, some of which are more apparent than others. We will discuss these opportunities in order of effort: the easiest to achieve will be described first.
6 .2 .1
V a lid a tio n o f E x is tin g P r o to c o l Im p le m e n ta tio n s
At the most basic level, NPG allows us to recognise a stream of network data, deter mining if a server should be able to parse it. Such recognition only needs to be done during debugging, but may be useful in scenarios where both a client and server are being developed in parallel. Stream validation may also be useful in production environments. Consider a scenario where outgoing SMTP connections are allowed out of a network, but H T T P connections are not. A savvy user may set up an H T T P proxy operating on th e standard SM TP port outside the network, and use th a t to perform any activity they desire.
To detect such a scenario, we need to be able to examine a stream and
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
6.2. O ther A p p lica tio n s o f th e N P G
110
recognise if it is of a specific protocol.
6 .2 .2
T e stin g P r o to c o l S y n ta x
Currently, protocols are defined in prose spiced up with BNF-like syntax to make the definition less ambiguous. A good example are RFCs discussed in previous chapters. Because the RFC is not machine-readable, it is not possible to directly test the def inition. The definition may be syntactically incorrect (as was the case with many of the protocols converted to NPG), or it may not express w hat the authors intended. W ithout machine readable protocol specifications, the closest thing to a true test is the reference im plem entation of a protocol. The reference implementation provides a “canonical” im plem entation th a t developers may use to te st other implementations of the protocol. However, the reference im plem entation will likely contain bugs, meaning th a t it may fail to properly parse the protocol as specified. W ith the NPG, it is possible to create a specification th a t can be converted directly into a parser. W ith th a t parser, it is possible to test th e protocol syntax directly.
6 .2 .3
T riv ia l P r o to c o l A n a ly s e r s
In most situations, the software at each end of a network stream has to be tightly coupled with th e protocol it is running. However, protocol analysers do not need such tight coupling, as they simply need to analyse and classify passing traffic (possibly recording some subset of the traffic for analysis). A network protocol gramm ar allows protocol analysers to be easily extended after deployment, by adding a new gram m ar definition for any new protocols th a t may appear.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
111
6.2. Other A p p lica tio n s o f th e N P G
6 .2 .4
C a n o n ic a lisa tio n o f I m p le m e n ta tio n
W hen creating a new implementation of a network server or client, developers must convert the human-readable specification into a machine-readable executable. Tools, such as flex[24] or bison[23] exist, b u t require th a t the programm er translate a protocol definition from a technical document into executable code. T h at process is boring, error-prone, and labour intensive.
Even if th e programmer creates an
implementation th a t works for some set of te st cases, there is no guarantee th a t the implementation is correct relative to the protocol standard, and there is no guarantee th a t the test cases provide sufficient coverage to ensure th a t all possible conversations will be parsed correctly. Automatically building protocol parsers is an extremely attractive proposition: it speeds up the development cycle, allowing programmers to generate optimised parsing code; gives developers the opportunity to prevent well-known parsing bugs; and en sures th a t the final parser is correct relative to the protocol definition. Intriguingly, it also gives us the opportunity to write th e protocol definition once and generate implementations for many programming languages. If the NPG is to be used to this purpose, trivial extensions could be added th a t would provide other opportunities. Protocols often require common tasks to be per formed, such as password validation, compression, or encryption. The NPG could be modified to allow decoding functions to be set in the grammar. In such a scenario, encryption could be added to a protocol by adding an encoding clause to a rule, and specifying the type of encoding to use, and the fields th a t contain credentials. W hen the specification is compiled into a parser, a library of callbacks would be searched for the appropriate decoding function.
The decoding function
would be automatically incorporated into th e parser, simplifying development. Generated parsers could be used in new applications as the entire parsing frame
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
6.3. L im itation s
112
work, providing d ata to application code through call-backs or some other mechanism, as proposed by Glenn Wurster[60]. They may also find a role as preprocessors for legacy applications. If a legacy application has a known security vulnerability or is otherwise unable to process certain types of input, a proxy can be built between th e source of the input and the application itself. The proxy would be responsible for modifying the input (and possibly the output) to minimise the impact of the fault, w ithout modifying the application itself. In such a scenario, a generated parser could provide a secure, standards-com pliant front-end for the proxy. Such an approach is similar to Microsoft’s Shield[58] defence. James Deverick is currently involved in using a network-based proxy to this end[16].
6.3
L im itation s
The NPG is a concise rendering for certain classes of context free grammars. As such, the language is extremely expressive. From a protocol design standpoint, however, there are still areas to improve.
6 .3 .1
E x p r e ssin g E n c o d in g s
The text of protocols is often transformed in some way, either to confound listeners, or to limit bandwidth consumption. In both cases, the net result is the same: NPG cannot describe the structure of the transformed text. A simple example can be found in the base 64 encoding of H T T P authentica tion tokens[20]. W hen a client sends a username and password to a server with the A u th e n tic a te header, and specifies the B asic encoding type, it passes a base 64 encoding of a user name and password to the server, separated by a colon. In its current incarnation, the NPG would be able to locate the encoded text, b u t would
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
113
6.3. L im itation s not be able to parse the user name field and password field.
6 .3 .2
S y n c h r o n isin g C lien t an d S e r v er
Every T C P connection has two sides.
Currently, the NPG does not provide any
mechanism for sharing d ata between the parser reading each side of the connection. However, it is conceivable th a t a protocol may require information sent from one participant to modify th e syntax of the protocol coming from the other participant. For example, if a client requests x bytes of d a ta from a server, the server may oblige and provide exactly x bytes. If the server doesn’t explicitly state x in its outgoing stream , a parser reading th a t stream has no way of telling the size of x , unless it was informed of x by the parser reading the other direction. So far, we have not encountered a protocol th a t is so thrifty with its transmissions th a t it does not have recipients repeat param eters back to senders. However, we would not be surprised if such a protocol existed.
6 .3 .3
S e le c tin g R u le s B a se d o n P r e v io u s M a tc h e s
NPG is based on Packet Types, a datagram filtering language. Packet Types provides a syntactic construct allowing a grammar to specify th a t “if some rule < i n i t i a l > matched in the past, m atch some future input against < f o llo w in g > .” This is useful for datagram parsing because fields th a t occur early in the datagram often specify the form at of the payload, which follows another large volume of fields. Again, we have not directly encountered a protocol th a t requires this functionality; however it may prove to be useful for other protocols in future.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
6.4. Further W ork
6.4
114
F urther W ork
Although we have a fully functional, open source implementation of an NPG parser generator, there are many possibilities for further work.
6 .4 .1
R o a d m a p for Im p r o v in g qcap
The qcap library is functional b u t in need of improvements. The following list is a roadmap for improvements th a t should be made to th e library. R ep lace th e generalised parser w ith an LL(fc) parser. The existing parser is functional, but it is unnecessarily slow. The goal of the project remains the construction of a fast parser for network traffic. Until the parser runs at ac ceptable speeds, qcap will not be ready for widespread use. We select an LL(k) parser1 for two reasons. F irst, it is easy to implement an LL parser and the transform ation function (subset construction, as described in [4]) is well understood. Second, an LR parser may require th a t the entire stream be read before returning a parse result [8]. Reimplementation is a two-step process. Initially, the subset construction tran s formation must be implemented to tu rn the N PG nondeterministic finite au tom ata into a deterministic finite autom ata. The finite autom ata is usable by an LL(fc) parser. Since an LL(fc) deterministic finite autom ata is also usable w ith the existing generalised parser, it can be tested with the existing parser. After the transform ation has been debugged, the LL interpreter can be implemented. M od ify th e N P G to su p p ort dyn am ically d irected parsing. Although dynam ically directed parsing is not strictly necessary to parse protocols it is convenient, 1Where
k is chosen upon examining the grammar.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
6.4. Further W ork
115
as it allows a protocol designer to store a parse decision at token k and defer its use until token k + n. It is the au th o r’s belief th a t the NPG would benefit from the addition of dynamically directed parsing. C on n ect th e qcap N P G p arser gen erator to th e qcap netw ork a n alysis stack. Parsers built from NPG gram m ars only run on input text, they do not yet run on d ata parsed from network streams. In order for qcap to be a useful network analysis library, NPG parsers must be able to read network data. Im prove th e qcap A P I. The qcap API is functional, but is not as easy to use as it could be. Small usability fixes are desirable.
6 .4 .2
N P G E n a b led N e tw o r k M o n ito r in g T o o ls
qcap has been designed as a library for developing network monitoring tools. Because qcap uses the NPG to define parsers, such tools would be very easy to extend to handle new streaming protocols, qcap also provides a full view of the network stack, meaning th a t users of such a tool would be able to see the effects of the behaviour of high level application protocols on low level transport and network layer protocols.
6 .4 .3
U s in g N P G In A p p lic a tio n s
Even though the Network Protocol G ram m ar is targeted at network monitoring tools, it could be useful to application developers. Existing parser generators do not use language specifications directly to create parsers, they rely upon a programmer to p ort the specification to an interm ediate language before creating the parser. Because N PG is a superset of the existing specification language ABNF, application developers using NPG as an input to a parser generator would not need to port the language; they could use the specification directly.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
6.4. Further W ork
116
Before NPG can be used to generate application code, a new parser generator must be w ritten th a t would enable th e creation of a parser in static code. However, a subtle optim isation could be added: the callbacks th a t the application is interested in are known at compile time, instead of run time (as is the case w ith qcap). Knowing which portions of th e gram m ar m atter a t compile time allows th e parser generator to avoid checks for callbacks at the sta rt and completion of regions.
6 .4 .4
U s in g N P G to S e n d D a ta
So far, our discussion of the NPG has centred on using th e language to recognise and parse incoming stream s of data. It could also be used to generate outgoing stream s of d ata from applications, similar to th e process followed by ASN.1[32]. Since N PG only defines an on-the-wire format, w ithout defining the d ata structures used to generate the protocol text, th e value of such an approach is questionable. It would require an extra language (or additions to th e NPG) th a t would map between d ata contained in the application and th e one-the-wire specification.
R ed efin in g G ram m ars as O b fu scation Treating a protocol gram m ar as a first class object provides an interesting opportu nity. It allows us to autom atically transform the gramm ar into other forms [48]. If we assume th a t there is an ASN. 1-style encoding and decoding layer shielding the application from changes in the protocol text, then we can modify the encoding in arbitrary ways w ithout having to modify the application at all. Such m anipulation could be used for obfuscation at run time. If the parties in a communication session can agree on a transform ation in a m anner th a t is opaque to an eavesdropping party, a simple m anipulation could be used to protect th e session from autom ated analysis by outside parties.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
6.4. Further W ork
6 .4 .5
117
Im p le m e n tin g G ra m m a r s T h a t M o d ify O th e r G ra m m ars
Many application protocols in the Internet suite have been modified since their initial specification. For example RFC 1870[35] extends SMTP to allow th e client to specify the size of an email before it is sent to the server.
The extension modifies two
SM TP productions minimally: one on th e client side and one on th e server side. T he modifications are sufficient to make RFC 1870 streams break SM TP parsers. Ideally, N PG would provide a mechanism to allow minimal changes such as these to be added w ithout modifying the original grammar. One approach to handling such a change would see a special N PG construct to allow one grammar to be declared as a modifier to another. In other words, if we have a grammar Gbase, some other grammar G ext can declare itself an modifier to Gbase. The modifier would change some subset of Gbase s rules. If we take th e SMTP client grammar as an example, we can say th a t G s m t p is the base gram m ar, and GWciszo modifies it. Ideally, modifiers would be implemented in a m anner th a t would allow multiple modifiers to change a single grammar.
6 .4 .6
B it O rie n te d P a rser s
Parsers are machines th a t consume symbols and change their internal state depending on th a t symbol. Previously in this document, we have implicitly assumed th a t the symbols our parsers consume are bytes. T h at need not be the case. The NPG provides bit-oriented literals, meaning th a t a protocol may contain fields smaller than a byte. In order for a parser to consume such fields, it would need to shrink its symbol size to handle n bits, where n is the length of the smallest b it
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
6.5. D angers o f th e N etw o rk P ro to co l G ram m ar
118
oriented field. Assumedly, there would be a runtim e cost to mask off the appropriate number of bits from the input, and then feed them into the parser. qcap has a fixed symbol size of eight bits, meaning th a t any protocol using binary literals must ensure th a t the literals contain exactly eight bits. It could be extended to smaller symbols, b u t the value of such an extension is questionable: the author is not aware of any stream oriented protocols th a t do not respect byte boundaries.
6.5
D angers o f th e N etw ork P r o to c o l G ram m ar
Just as NPG offers a number of promising technical opportunities, it presents moral risks, qcap’s express purpose is exploring network traffic, providing access to the full text of unencrypted T C P streams. T h at tool is available as an open source library, free to anyone with unencumbered access to th e Internet.
6 .5 .1
L egal C o n c e r n s S u rr o u n d in g t h e N e tw o r k P r o to c o l G ra m m ar
Although network traffic monitoring may be illegal in some areas, we do not address any legal concerns surrounding this technology. It is the deployer’s responsibility to ensure th a t their tools are in compliance with local laws, qcap is being developed and deployed in an academic environment w ith the goal of improving understanding of network traffic.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
6.5. D angers o f th e N etw o rk P ro to c o l G ram m ar
6 .5 .2
119
M oral C o n ce rn s S u r r o u n d in g t h e N e tw o r k P r o t o c o l G ra m m ar
The inherent risk of qcap is th a t it will be used to violate the privacy of people using the Internet. So long as privacy violations lead to nothing more serious th a n salacious gossip and embarrassment for the unwary, the author is happy to see his work used in this way.2 However, violation of privacy can have much more serious consequences. Consider a scenario where a repressive government is monitoring Internet traffic to prevent challenges to its authority: in such a situation, a breach of privacy may result in a jail term or death3. If the ideas presented in this thesis are used by a repressive government as a tool of repression or persecution, the author will have com m itted an immoral act. The author’s response to this risk is pragmatic, qcap is an improvement on the existing approach to building network parsers. It simply promises to make parser development easier. Programmers can already build fast, efficient parsers. The NPG speeds up development, and produces parsers w ith fewer bugs. The author feels it is unlikely th a t existing network-sniffing tools are so shoddy th a t any organisation with a large installed base will discard their existing network sniffer in favour of qcap in the short term. In the long term , organisations may start to use the N PG as a basis for their own sniffers. It seems much more likely th a t qcap would be adopted by small businesses in open societies. Businesses could use qcap to m onitor traffic flowing on their LANs and WANs for misuse. The categories of misuse are broad and arbitrary, b u t may include file sharing and instant messaging. The immediate effect would be th e limiting of protocols running on “inappropriate” networks. 2Of course, if the author falls prey to sniffing, his opinion on this matter is likely to change. 3h t t p ://web. a m n e s t y .org/library/index/engasal70012004
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
6.5. D a n g ers o f th e N etw ork P r o to c o l G ram m ar
120
At this point, however, the author suspects th a t the second order effects of qcap will become apparent. The developers of illicit applications will wish to continue to use their applications. We can expect those developers to make their protocols harder to detect; either by tunnelling them over existing protocols, encrypting them, obfuscating them, or repurposing existing protocols. Regardless of the route followed, the net result will be protocols th a t are less vulnerable to full text analysis. The author would like to believe th a t these developers will start a general push th a t will result in more protocols being secured. More secure protocols may, in turn, result in stronger privacy online. This is, however, solely speculation. Although the NPG and qcap may provide incremental improvements in network sniffers and monitors, it should also provide improvements in network security and, most im portantly, our understanding of networks.
As described above, th e NPG
can be used to build parsers for existing network protocols. Those parsers should have fewer bugs, and fewer exploitable security holes th an parsers designed by hand; meaning th a t servers implemented w ith NPG should be more secure. From an academic standpoint, th e most valuable contribution of qcap is its ability to fully parse large volumes of application data. This allows researchers to dig deeply into network data, and easily discover exactly w hat given network streams are doing. Given th a t researchers do not currently have a “tu rn key” approach for full stream analysis, th e author feels th a t the academic value of qcap and the NPG outstrips any marginal improvements in network sniffing technology.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
G lossary ABNF
accept
alp h ab et APF
A S N .l
d yn am ic len g th
dynam ic te x t
d yn am ically d irected parsing
Augmented BNF, a language for representing context free grammars, often used in RFCs, 33 If a gram m ar accepts an input, then the gram m ar recognises an input, meaning th a t the gram m ar can generate the input, 20 A set of tokens legal in a language, 19 A language for specifying the format of d a ta grams, proposed by Lambright and Debray in [38], 31 A bstract Syntax N otation One. A framework for exchanging d ata between hosts on a net work. Provides d ata formatting and m ar shalling functionality, 33 An idiom in protocol design. Indicates th a t th e protocol specifies the length of some field in a preceding field, 28 An idiom in protocol design. Indicates th a t th e protocol specifies a term inator for some field in a preceding field, 28 An idiom in protocol design. Indicates th a t th e protocol may use input a t token k to m od ify th e set of gram m ar rules available at token k + n, 104
filter
A tool used in network monitoring to filter out classes of datagram th a t are not of interest, 31
GAPA
An engine for parsing network protocols, 33
121
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
G lossary
122
HTTP
Hyper-Text Transfer Protocol. Designed to transfer files required for rendering web pages, b u t now used to transfer information of many types. Runs on top of TC P, 14
NPG
Network Protocol G ram m ar, a context free language devised by the author to describe stream ing network protocols, 7
op tion al seq u en ce op erator
A repetition operator th a t indicates th a t a symbol may repeat zero or one times, 45
Packet T y p es
A language for specifying the format of data grams, proposed by C handra and M cCann in [10, 40], 31 An action th a t can be performed on a gram m ar and an input string. Decomposes the in put string into constituent parts, as defined in th e gramm ar, 20
p arse
recognise
reject
rep etitio n o p era to r
R FC
stream orien ted
strin g
An action th a t can be performed on a gram m ar and an input string. Tests to see if some string is a member of a language, providing a boolean response, 20 If a gram m ar rejects an input, then the gram m ar does not recognise the input, meaning th a t th e gramm ar cannot generate th e input, 20 An operator th a t may appear in ABNF or N PG allowing some number of repetitions of a symbol, 44 Request For Comment document. Specifica tions for protocols published by the Internet Engineering Task Force, 33 An attrib u te of a network protocol. Stream oriented protocols exchange d ata as a reliable, well ordered sequence of bytes, sent from one host to others, 13 A sequence of tokens from an alphabet, th a t may appear in a language, 19
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
G lossary TAP
TCP
XML
123
Timed A bstract Protocol. A language for de scribing behaviour of datagram -oriented pro tocols, 32 Transmission Control Protocol. Protocol run ning on to p of IP th a t allows hosts to exchange d ata in as a reliable stream of bytes, instead of an unreliable stream of packets, 13 extensible M arkup Language. A popular d ata format language, 34
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
B ibliography [1] Netwitness homepage, 2005. h ttp ://w w w .n e tw itn e ss.c o m Accessed: May 3, 2005. [2] snort homepage, 2005. h ttp ://w w w .s n o r t.o r g / Accessed: May 10, 2006. [3] W ireshark homepage, 2005.
h ttp ://w w w .w ir e sh c L r k .o r g
Accessed: July 31,
2006. [4] A. V. Aho, R. Sethi, and J. D. Ullman. Compilers - Principles, Techniques, and Tools. Addison-Wesley, Reading, MA, USA, 1986. [5] D. P. Anderson and L. H. Landweber. A grammar-based methodology for pro tocol specification and implementation. In SIG C O M M ’85: Proceedings o f the ninth symposium on Data communications, pages 63-70, New York, NY, USA, 1985. ACM Press. [6] R. Ball, G. A. Fink, and C. North. Home-centric visualization of network traffic for security adm inistration. In VizSE C /D M SEC ’04■ Proceedings of the 2004 A CM workshop on Visualization and data m ining fo r computer security, pages 55-64, New York, NY, USA, 2004. ACM Press. [7] R. A. Becker, S. G. Eick, and A. R. Wilks. Visualizing network data. IE E E Transactions on Visualization and Computer Graphics, l(l):1 6 -2 8 , 1995. 124
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
125
B IB L IO G R A P H Y
[8] N. Borisov, D. J. Brumley, and H. J. Wang. Generic Application-Level P ro tocol Analyzer and its Language.
URL: h t t p : //r e s e a r c h .m ic r o s o f t .c o m /
r e se a r c h /s h ie ld /p a p e r s /g a p a F e b l0 2 0 0 6 . p d f.
[9] CAIDA.
Coralreef homepage, h ttp ://w w w .c a id a .o r g /to o ls /m e a su r e m e n t/
c o r a lr e e f / Accessed: June 26, 2006.
[10] S. C handra and P. J. McCann. Packet types. In Workshop Record o f W CSSS ’99: The 2nd A C M SIG P L A N Workshop on Compiler Support fo r Systems Software, pages 94-102, Atlanta, Georgia, May 1999. [11] Clearsight. Clearsight analyzer homepage, 2005. h t t p : //w w w .c le a r s ig h t n e t . c o m /p r o d u c ts-a n a ly z e r. j s p Accessed: May 4, 2005.
[12] Colasoft. Colasoft capsa, 2005. h t tp ://w w w .c o la s o ft.c o m /p r o d u c ts /c a p s a . php Accessed: May 3, 2005.
[13] W. W. W. Consortium, extensible M arkup Language (XML) Homepage, h t t p : / / www.w3.org/XML Accessed: May 3, 2006.
[14] D. Crocker and P. Overell. Augmented BNF for Syntax Specifications: ABNF. RFC 4234 (Draft Standard), Oct. 2005. [15] Debian Project. Debian Security Advisory 1049-1. h ttp ://w w w .d e b ia n .o rg / s e c u rity /2 0 0 6 /d s a -1 0 4 9 Accessed: June 7, 2006. Details Ethereal’s vulnerabil ity to CVE-2006-1932, CVE-2006-1933, CVEL2006-1934, CVE-2006-1935, CVE2006-1936, CVE-2006-1937, CVE-2006-1938, CVE-2006-1939, CVE-2006-1940. [16] J. Deverick. Personal communications, 2005. Discussion between th e author and James Deverick at the Large Installation System A dm inistration conference, held in San Diego.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
126
B IB L IO G R A P H Y
[17] R. Fielding, J. Gettys, J. Mogul, H. Frystyk, L. Masinter, P. Leach, and T. Berners-Lee. Hypertext Transfer Protocol - H T T P /1.1. RFC 2616 (Draft Standard), June 1999. U pdated by RFC 2817. [18] G. A. Fink, P. Muessig, and C. North. Visual correlation of host processes and network traffic. In VizSEC, page 2, 2005. [19] C. N. Fischer and J. Richard J. LeBlanc. Crafting a compiler with C. BenjaminCummings Publishing Co., Inc., Redwood City, CA, USA, 1991. [20] J. Franks, P. Hallam-Baker, J. Hostetler, S. Lawrence, P. Leach, A. Luotonen, and L. Stewart. H TTP Authentication: Basic and Digest Access Authentication. RFC 2617 (D raft Standard), June 1999. [21] N. Freed and N. Borenstein. M ultipurpose Internet Mail Extensions (MIME) P art Two: M edia Types. RFC 2046 (Draft Standard), Nov. 1996. U pdated by RFCs 2646, 3798. [22] D. P. Friedman, C. T. Haynes, and M. Wand. Essentials o f programming lan guages (2nd ed.). Massachusetts Institute of Technology, Cambridge, MA, USA, 2001 .
[23] GNU Project. Bison homepage, h ttp ://w w w .g n u .o rg /s o ftw a re /b is o n / Ac cessed: January 30, 2006. [24] GNU Project.
Flex homepage,
h ttp ://w w w .g n u .o r g /s o f tw a r e /f le x / Ac
cessed: January 30, 2006. [25] B. Gregg. Chaosreader homepage, 2004. h ttp ://u s e r s .tp g .c o m .a u /b d g c v b / c h a o s re a d e r.h tm l Accessed: May 3, 2005.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
127
B IB L IO G R A P H Y
[26] D. Grune and C. J. Jacobs.
Parsing Techniques - A Practical Guide.
Ellis
Horwood, Chichester, England, 1990. [27] U. C. Guard. Team coordination training student guide. h ttp ://w w w .c g a u x . i n f o / g _ o c x / t r a i n i n g / t c t Accessed: May 4, 2005. [28] P. Herman, tc p sta t homepage, h t t p : / / w w w .f r e n c h f r i e s .n e t / p a u l / t c p s t a t / Accessed: May 1, 2005. [29] R. Herriot, S. Butler, P. Moore, R. Turner, and J. Wenn. Internet Printing Protocol/1.1: Encoding and Transport. RFC 2910 (Proposed Standard), Sept. 2000. U pdated by RFCs 3380, 3381, 3382, 3510, 3995. [30] E. Hughes and A. Somayaji. Towards network awareness. In Large Installation System Adm inistration Conference (L IS A ’05), Dec 2005. [31] N. Instruments. Observer homepage, 2005. h ttp ://w w w .n e tw o rk in stru m e n ts . c o m /p ro d u c ts/o b se rv e r.h tm l Accessed: May 4, 2005. [32] ITU -T a n d lS O /IE C . Asn.l homepage, h t t p : / / a s n l . e l i b e l . t m . f r / Accessed: May 3, 2006. [33] M. Jayaram and R. Cytron.
Efficient demultiplexing of network packets by
autom atic parsing. In Workshop Record of W CSSS ’96: The Inaugural Workshop on Compiler Support fo r Systems Software, Tuscon, Arizona, February 1996. ACM SIGPLAN. [34] S. Johnson.
Yacc:
Yet another compiler-compiler.
h t t p :/ / d i n o s a u r .
c o m p ile r t o o ls .n e t/ Accessed: February 13, 2006. [35] J. Klensin, N. Freed, and K. Moore. SMTP Service Extension for Message Size Declaration. R FC 1870 (Standard), Nov. 1995.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
B IB L IO G R A P H Y [36] C. Kreibich.
128
N etdude homepage,
h t t p : / / n e t d u d e .s o u r c e f o r g e .n e t / Ac
cessed: June 26, 2006. [37] K. Lakkaraju, W. Yurcik, and A. J. Lee. NVisionIP: netflow visualizations of system state for security situational awareness. In V izSE C /D M SE C ’04: Proceed ings o f the 2004 A CM workshop on Visualization and data m ining fo r computer security, pages 65-72, New York, NY, USA, 2004. ACM Press. [38] H. D. Lambright and S. K. Debray. Apf: A modular language for fast packet classification. URL: http://w w w .cs.arizona.edu/people/debray/papers/filter.ps. [39] C. P. Lee, J. Trost, N. Gibbs, R. Beyah, and
J.
A. Copeland. Visual firewall:
Real-time network security monitor. In VizSEC, page 16, 2005. [40] P. J. McCann and S. Chandra. Packet types: abstract specification of network protocol messages. In SIG COM M ’00: Proceedings o f the conference on Applica tions, Technologies, Architectures, and Protocols fo r Computer Communication, pages 321-333, New York, NY, USA, 2000. ACM Press. [41] S. McCanne and V. Jacobson. The BSD packet filter: A new architecture for userlevel packet capture. In Proceedings o f the 1993 W inter U SEN IX Conference, pages 259-270, 1993. [42] T. McGuire.
A ustin protocol compiler homepage.
h ttp ://a p c o m p ile r.
s o u r c e f o r g e .n e t/ Accessed: May 1, 2006. [43] T. McGuire. A ustin Protocol Compiler Homepage. PhD thesis, University of Texas a t Austin, 2004. [44] J. McPherson, K.-L. Ma, P. Krystosk, T. Bartoletti, and M. Christensen. Portvis: a tool for port-based detection of security events. In VizSE C /D M SE C ’04-' Pro
R e p r o d u c e d with perm ission of the copyright owner. Further reproduction prohibited without permission.
129
B IB L IO G R A P H Y
ceedings o f the 2004 A CM workshop on Visualization and data m ining fo r com puter security, pages 73-81, New York, NY, USA, 2004. ACM Press. [45] A. Oline and D. Reiners. Exploring three-dimensional visualization for intrusion detection. In VizSEC, page 14, 2005. [46] S. Ostermann. tcptrace homepage, h ttp ://w w w .tc p tr a c e .o r g Accessed: May 3, 2005. [47] T. J. O strand and E. J. Weyuker. The distribution of faults in a large industrial software system. In IS S T A ’02: Proceedings o f the 2002 A C M SIG SO F T inter national symposium on Software testing and analysis, pages 55-64, New York, NY, USA, 2002. ACM Press. [48] G. Palidwor. Personal communications, 2006. Discussion between the author and G areth Palidwor, regarding the possibilities for grammars th a t are first class objects. [49] L. Peterson, x-kernel homepage, 2006. h ttp ://w w w .c s .a r iz o n a .e d u /x k e r n e l/ Accessed: June 28, 2006. [50] J. Postel. Internet Protocol. RFC 791 (Standard), Sept. 1981. U pdated by RFC 1349. [51] J. Postel.
Transmission Control Protocol. RFC 793 (Standard), Sept. 1981.
U pdated by RFC 3168. [52] J. Postel.
Simple Mail Transfer Protocol.
RFC 821 (Standard), Aug. 1982.
Obsoleted by RFC 2821. [53] J. Postel and J. Reynolds. File Transfer Protocol. RFC 959 (Standard), Oct. 1985. U pdated by RFCs 2228, 2640, 2773.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
130
B IB L IO G R A P H Y
[54] T. H. Ptacek and T. N. Newsham. vice:
Insertion, evasion, and denial of ser
Eluding network intrusion detection.
h ttp ://w w w .a c ir i.o r g /v e r n /
Ptacek-N ew sham -E vasion-98.ps Accessed: June 26, 2006. [55] C. Shannon and D. Moore. The spread of th e w itty worm. h ttp ://w w w .c a id a . o r g / a n a l y s i s / s e c u r i t y / w i t t y / Accessed: June 7, 2006. [56] tcpdum p workers. Tcpdum p public repository, h ttp ://w w w .tcp d u m p .o rg Ac cessed: May 12, 2006. [57] D. Waitzman. Standard for the transmission of IP datagram s on avian carriers. RFC 1149 (Experimental), Apr. 1990. U pdated by RFC 2549. [58] H. J. Wang, C. Guo, D. R. Simon, and A. Zugenmaier. Shield: vulnerabilitydriven network filters for preventing known vulnerability exploits. In SIG COM M ’04: Proceedings of the 2004 conference on Applications, technologies, architec tures, and protocols fo r computer communications, pages 193-204, New York, NY, USA, 2004. ACM Press. [59] R. Wojtczuk.
libnids homepage, 2005. h t t p : / / l i b n i d s . s o u r c e f o r g e . n e t /
Accessed: May 5, 2005. [60] G. Wurster. Personal communications, 2005. Glenn W urster gave an in-house talk in the lab on using parsers for input processing on servers. [61] X. Yin, W. Yurcik, M. Treaster, Y. Li, and K. Lakkaraju. Visflowconnect: netflow visualizations of link relationships for security situational awareness.
In
VizSEC /D M SEC ’04-' Proceedings of the 2004 A C M workshop on Visualization and data mining fo r computer security, pages 26-34, New York, NY, USA, 2004. ACM Press.
R eproduced with perm ission of the copyright owner. Further reproduction prohibited without permission.
When life gives you a hundred reasons to cry, show life that you have a thousand reasons to smile
© Copyright 2015 - 2024 PDFFOX.COM - All rights reserved.