All right. DEF CON 13 is proud to present Marshall Betto with the Protocol Informatics Project.
Saturday morning at DEF CON. God damn, why am I working Saturday morning at DEF CON?
All right. Marshall, take it away.
All right, so this project is called the Protocol Informatics Project.
It's basically a play on words from bioinformatics, which is kind of my main inspiration for this project.
Yeah, it's not that loud. Should I talk closer? Okay, there we go. Thanks.
So, my name is Marshall Betto. I'm a research scientist at McAfee.
However, this is pretty much all independent research. My company's never even seen this stuff.
So, I think that's why it's worthy, as opposed to something that's out there trying to make money or something like that.
Let's start.
Well, the purpose of this project is to basically automate network protocol analysis.
So, I just added this slide the other night just to kind of say, this is what this thing does.
You input a PCAP file, and output is going to be a packet format.
So, this is my little XML markup of this particular protocol format, which is just kind of something that's made up,
which is basically a two-byte link field followed by an ASCII string or something like that.
My application, what it does is it goes through, does a series of comparisons and checks,
and uses sequence alignment algorithms to understand the general structure of the format.
So, if you were to analyze this markup, basically what it's doing is it's describing this protocol,
saying that it operates on UDP 435364, something I just pretty much made up.
It's a block-based protocol, so you open up a block, you insert the link to that particular block,
which is going to be a short, big in the end, followed by a variable type,
which is going to be a plain text string.
Right now, the default value for that is going to be hello.
And then I close it all out.
So, the general idea is, you take a protocol you've never seen before in your life,
you're trying to reverse engineer a World of Warcraft, for all I know.
You input the PCAP file, and out comes the structure.
So, that's the general idea behind it.
So, the objective of protocol analysis is, first, to understand exactly the format of every single packet.
I mean, that's a pretty simple concept in general, but it does get more complicated as you have to understand
the actual state and the actual handshake and things of that sort.
So, there's really no good way of doing this at this current time.
I mean, it's pretty much a manual process.
People sit down with E3O or something like that and break out a piece of paper
and just start writing down offsets and trying to use their human intuition
to be able to understand what this particular field does and where it's located in the packet.
So, this information is generally important to understand proprietary protocols,
which are actually kind of becoming a little bit more rare, in my opinion.
Of all the security products that I've been looking at and things like that,
everybody seems to be using SOAP over SSL nowadays.
So, maybe this stuff isn't as applicable in those situations.
But, if you're going back and looking at legacy protocols, like some SCADA networks and things like that,
this stuff is going to be a lot more useful because there's really not that much documentation
for that sort of stuff.
So, it's also important for extending the functionality of software.
If you guys want to write an open source client for a particular service,
this project can help out in that regard.
And lastly, and my favorite, is finding vulnerabilities in unknown or badly documented protocols
using fuzzing.
So, what I basically do is I feed it my PCAP file, it analyzes the structure,
pops out the XML markup, then I feed that into my fuzzer and it starts going to work.
So, what protocol informatics does, which is just the name of my program basically,
it heuristically identifies the fields in data format.
So, it's never going to be perfect, but it's as close to automated as you're ever going to get.
So, nowadays the problems with protocol analysis in general is it's a manual process.
Like I was mentioning earlier, you just pretty much do it by hand using ethereal
and fields are identified largely using human intuition.
So, I guess I was talking to Spoon about this a little earlier
and he was basically explaining to me that, well, all these protocols are written by humans
so you can basically use your human intuition to be able to understand how they were thinking
and things like that.
However, computers have never really been able to mimic human behavior that well.
I mean, if you're looking at pattern recognition and things like that,
people are moving over neural networks and other hidden markup models and other things of that sort
in order to try to mimic that intuition in a computer program.
I guess the main challenges with protocol analysis these days is
kind of just understanding general structure when it comes to different types of protocols.
For example, a protocol that's all binary, usually quite hard to analyze
because there's really no points of reference for us.
When you're going through it, you're just kind of looking at the bytes
and trying to find patterns and things like that.
Typically, it doesn't seem like that's going to be pretty much a tedious, painstaking process.
So, this is really an attempt to automate that.
I think the crux of protocol analysis in general is variable length fields,
long strings in the middle of packets and stuff like that.
You don't necessarily know, if it's not plain text data, where it starts and where it ends
and what each byte represents and things of that sort.
Typically, this is all going to be differential analysis.
You're just going to be going through, doing comparison, comparison, comparison,
trying to kind of build a profile as you go along.
Fortunately, however, biologists already fixed this problem back in the 1970s
when they were trying to analyze genetic structure, DNA, amino acids, and all that sort of stuff.
This is all pretty much... I'm not taking credit for any of these algorithms I'm presenting today.
All I'm basically doing is reapplying it to our realm,
which is computer security, computer science, and things like that.
So, bioinformatics. What is bioinformatics?
It's basically information theory applied to biology.
So, it's a lot of probability, Shannon entropy, all sorts of things like that.
And it's mainly used to identify genes in the genetic structure of organisms.
So, Human Genome Project, the majority of the algorithms that are used are mainly sequence alignment algorithms.
What they're going out there and trying to find is where the beginning of these genes start and where they end,
what the function of these genes are, and what the structure of these genes are,
how they fold, and all sorts of things like that.
So, the workflow for how biologists do this, they have these large databases just full of genetic data.
The human genome's in there, they have mice and every other species that they've sequenced.
And they put this all in a database and then they can start running queries on it.
So, saying, like, I know that this gene exists in, you know, human.
It will go through and it can understand common ancestors and things like that,
based on mutation rates and all sorts of stuff like that.
So, if you want to put it in simple computational terms,
it basically is just processing a large amount of structured but complex data.
It's just too much for the human eye to just recognize.
So, you have to put it in a database, you have to run these algorithms on it and things like that,
if you really want to understand the structure.
So, yeah, the objective is to identify genes, determine structure, and the function.
Easier said than done, naturally, but there's a lot of analogies to protocol analysis in this case.
So, one application of bioinformatics is allowing biologists to map phenotypes to genotypes.
Being able to say, blue eyes maps of this particular gene,
attached earlobes maps of this particular gene, and things like that.
Protocol analysis and bioinformatics have a lot of things in common.
They're both operating in large sequences of data.
And my favorite is just the analogy of biology's phenotype-to-genotype mapping
is equivalent to protocol analysis' mapping of offsets to field locations.
We're basically just trying to understand the function of a particular field in a byte stream.
We don't know where it exists, but it's between this offset and this offset.
Fortunately for us, what actually makes this easier is, when it comes to genes and things like that,
it's not all... it doesn't have a defined start and a defined end.
You can have... I think eye color, for instance, isn't just like one single gene.
It's spread out throughout the genome.
So, you have to do a bit more complicated analysis to understand,
here's a block where it starts, then it skips this many symbols, and then it restarts over here.
So, fortunately for us, it's really not like that.
We have fields. Here's your start offset, here's your end offset.
So, what I did was I created an application that was meant to understand the structured, complex data found in our protocols.
So, the core algorithms that are used in bioinformatics in general are mainly sequence alignment algorithms.
There's two of the most classic algorithms, the Niederman-Wunsch algorithm and the Smith-Waterman.
I'll get into each particular detail as we go on, but basically,
the Niederman-Wunsch algorithm is a global sequence alignment algorithm.
It takes into account every single symbol in the genetic sequence and tries to align it to a different sequence.
It's just a pairwise alignment.
Smith-Waterman, on the other hand, is a local sequence alignment algorithm.
It's going to find the most common substring within the two sequences that are most similar.
There's ways to improve sequence alignment, and that's basically by using similarity matrices.
I'll get into that a little later.
All these algorithms are operations on matrices.
There's a lot you can do with different weighting and things like that,
and assigning scores, and how the matrix is traversed is all dependent on the scores in the cells.
There's actually a lot of really neat things that they figured out that they can do using this.
Then what we get into is phylogenetic tree building.
This is kind of cool, because this is how biologists are able to build a tree of life,
not based on fossil record, but instead based on genetic information.
How similar are these two sequences, and being able to go all the way up through the evolutionary tree
to find common ancestors and things like that.
I go over the two tree building algorithms, Upkema and the neighbor joining tree,
which I'm sure many people have heard of that.
And lastly, I get into multiple sequence alignment,
and that's where there's a lot of challenges involved with aligning more than one sequence,
just due to computational problems.
I go over the progressive and tree-based multiple sequence alignment algorithms.
And this is a lot of information, so if I am going too fast, just put your hands up or something like that.
The fundamental purpose of sequence alignment is really simple.
It's take two sequences, regardless of their length,
and insert gaps into either sequence to make them the same length.
So, right here I have an example of a DNA alignment.
There's four base amino acids in DNA.
There's thymine, guanine, cytosine, and adenine.
This is kind of just a really simple example of inserting gaps into the first sequence
to align it to the second sequence.
So, as you can see, there's three gaps that were actually inserted into the first sequence,
which would represent a deletion, evolutionary-wise.
The Niedermann-Wunsch algorithm, which I mentioned earlier,
is a dynamic programming algorithm, meaning that it operates on matrices.
I think it was the first sequence alignment algorithm ever written.
I think it was 1973 when it first came out.
Basically, it performs a global alignment on a pair of sequences,
and what that means is that every symbol in the sequence that goes into the algorithm
comes out of the algorithm.
Gaps are inserted.
There's no substring searching or anything like that.
It's going to try to insert gaps anywhere it can
to make the sequences line up to each other as best as possible
to maximize the alignment, maximize the score of the alignment.
And it's mainly used for analyzing closely related structures,
and the reason for that is if you were trying to analyze the human genome and the mouse genome
and using a global sequence alignment algorithm,
there's going to be so many gaps that are inserted that it's not even going to be relevant at that point.
It's mainly used for maybe comparing two different types of humans' DNA
to understand a brown-eyed person versus a blue-eyed person
versus an attached earlobes person versus a dangling.
Dynamic programming is a common concept in computer science.
It's not coding, per se.
It's just a terminology that's used to solve problems by using matrices.
So the idea is to break the problem up into subproblems.
So you have a matrix.
You perform a computation on each cell in the matrix,
and as the algorithm progresses,
it uses information that was previously gained in the other cells
to progress until the end of the process.
So the results of the previous computations are saved and used by the remaining subproblems.
And Niedermann-Wunsch is a dynamic programming algorithm,
as is most of the sequence alignment algorithms out there.
So how Niedermann-Wunsch works, it's actually a pretty simple little operation that it does.
The first sequence is placed in the topmost row,
and the second sequence is placed in the leftmost column.
And basically there's this little equation right here
that basically is used to assess each cell in the matrix,
starting at position 1, 1.
There's three steps for these sequence alignment algorithms.
The first step is to assign a similarity score.
So basically what you do is,
you go through and you score every single similarity
between the character in sequence 1 and the character in sequence 2.
The second step is you assess all possible pathways through the matrix,
left, up, and diagonal from the particular cell that you're in,
assigning the current cell with the value of the maximum scoring pathway
using this particular equation,
which I have a matrix on the next slide that will make it a bit easier to understand.
The third step is constructing a pathway from the highest scoring cell
back to the beginning of the matrix.
And what this represents is the insertion of gaps in each sequence.
And lastly...
Okay, actually, let me get back to the equation.
What you're going to do is, when you're in cell IJ,
you're going to look at your diagonal cell,
which is I-1, J-1, plus S-IJ,
which S-IJ is going to be the similarity score
between the offset I and offset J in each sequence.
It's also going to look at the left...
It's going to look at the left cell from the current position,
and it's going to add a gap penalty
because if you're going left or if you're going up,
you're actually inserting a gap into the sequence.
And that's not necessarily a good thing
because it kind of makes it a bit irrelevant if there's too many gaps.
So there's something called the gap penalty
that will basically dock the alignment score at the end.
So you'll be able to understand what the relative...
You'll be able to really understand how important this alignment is
and what it really represents.
If it has a really low score,
then you know that it's probably really not that significant.
So this is the visualization of the concept.
I use HTTP just because everybody understands it.
It's a text-based protocol. It's really simple.
You actually probably wouldn't ever have to use this program
to do text-based protocols just because they're so easy.
But for example's sake,
I use it just because it's small enough
to fit into a PowerPoint presentation.
So the first sequence is placed in the topmost row,
which is git slash index.html HTTP 1.0.
And the second sequence is git slash HTTP 1.0.
So as mentioned earlier,
you just kind of iterate through the matrix
and you perform the scoring based on the similarity between each character.
So right here, the Gs match,
so you score with one and so on.
So you go out and you build up the matrix.
One thing to be mentioned, though, is
Needleman-Wunsch, kind of like the default
runtime environment for it,
is to have a match score of 1,
a gap penalty of 0,
and a mismatch score of 0.
So in some cases,
you can actually make this a bit more complex
by having different scoring mechanisms.
G might have a stronger alignment,
so you have a higher score in that case,
and things like that.
And when I talk about similarity matrices a little later on,
you'll kind of understand what I'm talking about.
It's probably a little too early for that.
So what you do is
you start in cell 1-1,
and you look at your left cell,
your diagonal cell,
and your upper cell.
And you apply this little equation right here,
which is going to take the maximum value
of the diagonal,
or the left,
or the upper.
For the diagonal cell,
you actually add the score of that position.
So in this case,
it's going to look at diagonal
and add 1,
because the G's match.
There's no match here, there's no match here,
so the maximum is going to be the diagonal plus 1.
So it's going to leave it a 1.
And the way that these matrices are traversed,
they're traversed left to right,
and then they move downward.
The next step, move over one position.
This time, it's going to look left,
it's going to look diagonal,
it's going to look up.
It's going to take the maximum.
In this case, before, the cell was 0,
so this S-I-J in this case is going to be 0.
It realizes that the leftmost cell in this case
is going to be the maximum,
so it places that particular value in this cell.
It's a really simple operation, actually.
It just goes cell by cell and it builds up.
This is kind of like the completed matrix.
I do this all in hex down here
just to make it all line up and look pretty on the screen.
Basically, this is kind of how it looks
after you perform all the scoring of the matrix.
The next step at this point
is to actually traverse back to the beginning of the matrix
and understand what your alignment is going to be.
In this case, typically,
the maximum cell is always going to be your bottom right.
What we do is we start in the bottom right cell in this case
because it had the highest value.
We look at the neighboring cells
and we choose the cell with the maximum value
and traverse there.
We start here at E
and we notice that our neighbors are all Ds.
Basically, that means that we can go anywhere
because they're all equal.
We can go left, we can go up, we can go diagonal.
I personally like to just go diagonal
just because it just makes the most sense.
Basically, it signifies that there's not going to be any gap
that's inserted into any of the sequences,
which may mean that there's actual match there.
This is kind of the evolution at this current point.
Starting down here, we look, we go diagonal because it's D.
At this point in D, we look around.
All of our neighbors are C.
We want to go diagonal again by default.
My mouse is disappearing.
The same deal here.
All B, so we go diagonal.
All the neighbors are A.
Go back to A.
Neighbors are 9, etc., etc.
All until we reach this point up here at this 5.
And we look at our neighboring cells again
and we realize that there's a 5 to our left,
a 4 to our diagonal, and a 4 to our up.
We want to have the maximized alignment
so we're going to take the path
that will result in the maximum score.
So at this point, we're going to start going left.
This is the completed traverse
all the way back to the beginning of the matrix.
So at this point...
Goddamn.
So at this point, we're looking around.
We notice that 5 to our left is the maximum,
so we're going to go there.
Same thing.
We're surrounded by two 4s and a 5 on the left,
so we go left, etc., etc.,
all the way until we hit back here.
And all of them are equal again,
so we decide that we're going to go diagonal.
And then it goes all the way back to the root.
So what this means at this point
is there are going to be gaps
inserted into one of these sequences.
So what did this do?
We computed a path through the matrix,
and now we can apply the rules of Needham and Woons
to obtain the two aligned sequences.
Basically, here's the rule.
Any time that you traverse left on the matrix,
a gap is inserted into a sequence.
So when you go left,
it's going to insert a gap into sequence 1
at that particular offset.
If you ever go up,
you're going to insert a gap at that offset
in the first sequence.
So, here's the results of that particular alignment.
On the bottom down here,
kind of a lame example with HTTP, I know,
but it illustrates the point.
There's gaps that are inserted right here
under index.html
because that particular sequence
did not have that file in there,
and everything else matches up.
So what this allows us to do, really,
is to understand the beginning and ending
of the boundaries in the packet.
So, if you wanted to analyze this really simple example,
you can say that, okay,
these two sequences had git slash in common.
We can consider that a keyword.
Index.html was a file name.
It's a variable length field.
You can put any file in there that you want.
And it was subject to deletion in the second sequence.
So what we can assume at this point
is that that is a variable length field
because it was subject to deletion,
followed by the keyword HTTP 1.0.
So, if you wanted to actually describe this protocol
in a fuzzer, you could say,
okay, we're going to send a git space slash
and we're going to send a whole bunch
of random data in between,
followed by HTTP 1.0.
Pretty simple.
This leads us into explaining
the local sequence alignment algorithm,
which is used kind of for a different purpose.
So, this is called Smith-Waterman.
I think it was written in 1979, I think.
I might be wrong about that.
It's basically a derivative of Needleman-Wunsch.
It just has some different rules, basically.
What the point that it's trying to do
is find the maximum local alignment
between the two sequences,
which is going to be a subsequence between the two.
It's going to find the subset in each sequence
that makes the most sense.
And that may be subject to gaps
and it might not necessarily.
So, this is especially useful
in determining similarity between distance sequences
because you could look at a chimpanzee genome
and a human genome
and use local sequence alignment algorithms
and you'll actually get a lot more data out of it
because the alignments will actually mean a lot more in the end.
So, local alignment has a strong scoring mechanism,
whereas global is weak
because of the number of gaps
that may be inserted into the global alignment.
So, local alignment algorithms are used a lot
to kind of search the database
to understand which species are the most similar to others
and things like that.
So, how Smith-Waterman works,
it's a derivative of Needleman-Wunsch.
The only difference is
you kind of start it with some different initial values.
Also, this is kind of like a default run.
You can also use similarity matrices and things like that
to modify how this works.
But by default, it has a match score of 2.
So, if G and G match, we assign that a 2.
It has a gap penalty of negative 2.
Any time that we move up or any time that we move left,
we're going to subtract negative 2 from the alignment score.
The lower the alignment score, the less significant it is.
Any mismatch, so G and E don't match,
it's going to have a mismatch score of negative 1.
The difference is, when you're in the matrix,
you start in the cell that has the highest score,
and you're going to start traversing back.
The difference is, when the score hits 0 in the matrix,
you're going to return immediately.
And at that point, those particular offsets in the matrix
are the ones that are saved and used
as a representative local alignment sequence.
I actually didn't do a matrix and stuff like that.
It was kind of short notice and things like that.
But basically, if you want to align these two sequences,
same thing as before,
the score's going to end up being 18,
and it's going to find the substring space, HTTP slash 1.0,
as being the most common local alignment
in those particular sequences.
So that's going to be the most similar difference between the two.
Smith-Waterman is actually used a lot
to determine the distance between two sequences.
So if you want to find the distance between sequence 1 and sequence 2,
you're going to take the Smith-Waterman score of sequence 1
running against itself,
minus the Smith-Waterman score of sequence 1
aligned with sequence 2.
So in this case, it's 48 minus 18, which is 30.
So the distance is going to be 30.
Just pretty simple.
Basically, here's how it's used.
In my program, it's not necessarily used
to determine the protocol fields.
I use it just as a classifier
to allow me to build
kind of like a relationship matrix
and understand which packets
in the tcpdump file
are the most similar to each other.
Because if you're looking at a complex protocol
like isocamp or smb
or something like that,
they have multiple different message types.
This is actually going to be really helpful
because it's going to allow us to cluster
the different types of messages
within that particular protocol.
It's used to calculate the relative distance
between sequences for clustering purposes
and tree building, which we'll get into later.
In bioinformatics,
Smith-Waterman is used for multiple sequence alignment
because DNA has no start and end
whereas a packet does.
That's also another big advantage that we have.
We know where the packet starts, we know where the packet ends.
We also have fields that start here and end there.
There's no fields that are going to span
over multiple blocks
and jump in over each other
and stuff like that,
like it does in DNA.
To improve these alignment algorithms,
we use what's called a similarity matrix.
Basically, we replace our scoring mechanism.
Before, I was showing you
that a match score would equal 1
in Niedermann-Wunsch, a match score in
Smith-Waterman would equal 2, and things like that.
Similarity matrices, on the other hand,
are tables
based on the probability
that this sequence is allowed
to mutate into another sequence.
In evolution, it is possible
for different amino acids
to mutate
into others, but not
other ones.
It basically allows
biologists to say,
adenine can mutate into thymine
but not cytosine, and things like that.
By the way, I'm not a biologist, I don't actually know
if that is true, but it's just an example.
Similarity matrices
are pretty different, I guess, because
it's kind of
based on preference.
There's similarity matrices out there that are
used only when
comparing really distant sequences,
and there's similarity matrices that are used when comparing
really close sequences.
The applications
to protocol analysis is really good, though, because
we have data types. We have
plaintext data, we have binary data,
and things like that.
We can assume that binary data
is acceptable for binary data to mutate
into other binary data, and plaintext data
to mutate into other plaintext data.
Especially if you're using a
protocol that usually uses English words,
you can actually have a
similarity matrix that accepts
I before E
and other kind of common
linguistic rules like that.
So,
the protocol informatics similarity matrices,
our alphabet is 256
bytes long, so we have a
256 by 256 matrix,
and each mutation,
each cell contains
mutation probabilities between every character, so
we might say that it's acceptable for
A to mutate into E, but not into
hex FF and things like that.
So,
this is actually kind of some
outdated stuff. There's actually a lot easier ways of doing this.
So,
what this allows us to do is
obtain a bit more optimized alignments.
This way, if we use these
similarity matrices that are specially tailored
for different types of network protocols,
if you have one that's mixed,
has plaintext in it and binary data in it,
you could use a particular similarity matrix in there.
And basically what this does is it allows
when gaps are inserted into the sequences,
the alignment is still
going to hold true where
plaintext data is only mutating into other
plaintext data, binary data is only mutating into
other binary data. You're not going to have any mismatches in between.
So, I guess
the kind of role of similarity matrices though
is that they're
going to really have to be tweaked.
And you could have
probabilistic models, you can do some
Markov chains and stuff like that to
initially build your stuff, but it's also kind of subjective.
I can say
that I know that
a plaintext
character is commonly followed
by a null, so it's able
to mutate into a null character and stuff like that.
That's very acceptable.
So, bioinformatics
scientists spend years perfecting their version of similarity
matrices. I don't know how many revisions
there are of Blozeman and the PAM matrices,
but there's quite a lot, and they're each
used for kind of different purposes.
I kind of actually had
a problem
trying to represent this stuff and kind of
allow others to
understand kind of what I'm talking about.
And this isn't actually that great, but
this is just a kind of stupid example.
This superscript B just stands for binary.
So let's just assume it's like 0x01,
0x02, 0x03, etc.
So if you wanted to align these protocols,
alignment without proper scoring
might actually
insert gaps into incorrect
places and
assume that
F might be able to mutate
into 0x01 and 0x04
and stuff like that, which isn't necessarily
a correct alignment.
If you use a similarity matrix
with decent data
that keeps track of
mutations between different types of data types,
you'll start getting better
alignments where all the ASCII
data is aligned to each other, all the binary data is
aligned to each other, and things like that.
So it's basically just a tool to help us
signify
our alignments a bit better.
So
I kind of explained so far
how to do a pairwise sequence alignment, which
isn't that useful. Just have a
look at two HTTP requests and say,
okay, here's the variable link field.
This is where you put file names.
It's really not that big of a deal.
But it's really not that
pairwise sequence alignment isn't really that useful.
You really have to start getting the multiple sequence
alignment if you really want to
get significant results.
Multiple sequence alignment is basically the
act of aligning more than two sequences.
It uses
Niedermann-Munch as the alignment algorithm and uses
Smith-Waterman as a scoring algorithm.
The problem with this is there's computation
issues.
So Niedermann-Munch, as I
showed before, it operates
on a n by n, or
excuse me, n by m matrix where n is
the length of sequence one and m is the length of
sequence two. If you want
to start aligning three sequences, you can
start building hypercubes and things like that and traversing
through hypercubes.
The problem is the operation is
n to the nth power where n is the length of sequences
and n is the number of sequences.
This isn't really going to be feasible
for us. So I have my little
illustration of my hypercube being traversed.
It can be done,
but I've been trying to align
sequences that are up to 1500 bytes
in length and it takes
a really, really, really long time.
What we use is a heuristic
sequence alignment algorithm.
I'm basically sacrificing accuracy for time.
The objective is to align
every sequence to each other in a reasonable
amount of time, but the results are never, ever going to be
perfect.
The way that this is done
is by building these polygenetic trees.
Polygenetic trees are basically
what you guys would think
of a tree of life. You start with
common ancestors and you kind of move
down and you can start understanding the
similarities between certain species and things
like that. It's the same thing with packets.
We know that in SMB
all the SMB authentication packets are going to be
more similar than a data transfer packet
and things like that.
Typically, these are just binary trees
which makes it quite simple, actually.
It does have an interesting parallel in protocol
analysis because protocols mimic
evolution by changing their fields.
The kind of goofy thing
that I have here is what came first,
git slash index.html or git slash?
Obviously, git slash is going to be the
common ancestor.
Here's my little
rip-off of a tree of life of lizards.
As you can see,
on the right-hand side,
these guys look a lot more similar
in structure than to this
C. tigris guy over here with the
long tail. So, basically, similar
situation, apply it to packets.
So, to create
polygenetic trees, there's an algorithm called Upcoma
which is the unweighted paired group method using
arithmetic averages. It's pretty simple,
actually. This little
equation right here just signifies
how the distance between two clusters is taken.
Basically,
the dpq
function is going to determine
the distance between each
sequence in cluster i and
cluster j. And it's basically just
taking the mean of that and returning that back as
the distance of i and j.
In this case, the dpq
is going to be the Smith-Waterman score and the d
ij is the distance between two clusters
i and j. So, this is just
the operation that's used each step of the
way when building the tree.
So, to build
the tree, each sequence is put
into its individual cluster cell, one packet
per cluster, basically. Use the Upcoma
algorithm to iterate through every single cluster
doing comparisons between every single
sequence. You take the two with
the smallest distance between each other.
You create a new cluster k by uniting
those two sequences.
You define a new node k with child
nodes i and j to build the tree.
You add the cluster k
to the universal set and you remove
the clusters i and j. So, basically
at the very end, you should only have one cluster.
And you should have a tree build
at that point.
Here is a phylogenetic tree
of the SMB protocol. This is just
doing null sessions and stuff like that.
As you can see, there's
actually a pretty large disparity between
the differences between
different types of packets.
The edge length signifies
the distance.
So, it's kind of
more than a pretty picture.
I'm sorry I can't actually
I don't have any cool interface where I can zoom in and tell you
exactly what those packets were and stuff like that at this current
time, but from the analysis that I did
each one of these clusters up here
represented one of the SMB
message types in the protocol.
So, this is actually going to help us
say we want to analyze
the SMB authentication
packet. Okay, it's
this cluster over here, for instance.
So, we start at this root node, and then we're going to
start doing our progressive alignment over here.
So,
the tree is your guide. Basically,
what this tree is going to be used for is to align
the sequences to each other.
As I was talking about the heuristic
alignment earlier,
what we're basically going to have to do is what's
called progressive sequence alignment, and what that means
is we're going to align two sequences to
each other, and then
we're going to
pick one of the
alignments and use that as a representative
sequence for those two sequences.
Then we're going to align another sequence
to that representative sequence. And as
gaps are inserted, they are
moved down towards
the root, excuse me,
down towards the leaf nodes
on the graph. So,
the problem with this is
if gaps are inserted into the tree
in errant places, that will be propagated
all the way down to the leaf nodes, which can result
in insignificant alignment.
It probably should be a more
tree building
should probably be a bit more
of a manual process where
while you're doing the analysis, you kind of look at it
and you say, this does look acceptable
to me, I'm going to accept this alignment to be
the representative sequence, so
gaps aren't inserted into errant places
basically.
Opposed to the exponential hypercube
traversal, Upcoma performs
in comparisons where n is equal to
the depth of the tree minus the root.
That's very feasible for us.
We can actually align sequences in our lifetime
which is very helpful, I think.
So, multiple sequence
alignment. Basically, the rule
as I was explaining earlier about progressive alignment
is once a gap, always a gap.
Basically, what you're going to do is
you're going to align two sequences
to each other, place a representative
sequence in the root node of that
and
and
as you align sequences
to those representative sequences, those
gaps are going to translate themselves
all the way down to the leaf node.
Basically, the rule for
doing the tree traversal, you start in the root
and if the root is null
you start going left and then you go right.
If the left is not null and the right is not null
which signifies that there are sequences on those
two leaf nodes, you align those two sequences
you choose a sequence with the least
number of gaps inserted and that's kind of just
I got the best results
out of that. I don't really know if that's kosher
in the bioinformatics world or anything like that, but
from my experience, that resulted
in decent alignment.
In this case
we aligned sequence one to sequence two
sequence one is chosen to be the representative
because there were not as many gaps inserted
so it kind of lowers the margin of error
of error and gaps propagating all the way down
through all the alignment. So, what we're going to do is
we're going to place sequence
one in the root node
of these two leaf nodes
and we're going to keep track of the edits
in the edge. So, the edits in this case would be
I don't have
the list of the offsets right in front of my face
but
there's going to be edits that are inserted into sequence two
to insert those gaps.
Pretty tree,
not really.
So, you start in the
root node, the parent node right up here
like I was saying earlier
if the root is null, you go left then right
the root is null in this case, there's no value
being stored there, so we're going to go left.
Same thing here, we're going to go
our child nodes
are not null, so what we're going to do is we're going to
align sequence one and we're going to align sequence two.
We're going to choose a representative sequence
which is going to be one, we call it one prime at this point
we keep track of the edits in the edge.
So, the edits
between sequence one
and two are stored in the left
edge and the edits for sequence
two are stored in the right edge.
We just traverse our way
back up to the root
start moving right now
we align
the representative sequence which is one prime
with three, store those
edits in the edge, and now what we need to do
is we actually need to
propagate those gaps that are inserted via
the edits all the way down
to the leaf node.
If we want to
align all the sequences to each other, we basically
add up all the edits
so sequence one aligned
which is over here, we're going to
add the edits of one prime three
to one two
to add the edits
the edits in this case are going to be the gaps
by the way. If we're going to
propagate
those gaps down the tree to sequence
two, we're going to take one prime three
add it to
the edits of two one
and lastly
for sequence
three, all we need to do is add the edits of
three and the edits of sequence
three and one prime in this case.
As
explained.
So, another
kind of hokey example of three
sequences being aligned this time
a bit more
verbose
usage of HTTP I guess
so basically in
this case right down here, this is what's
called our consensus sequence
what we basically do is we start in
offset zero and we go down and we say
these are all a bunch of G's so we're going to put a G down here
etc etc
once we start getting over here we start noticing that
there's gaps inserted so
that might possibly mean that
that is a variable link field so in this case
I'm just representing that by the question
mark down there and
all is the same
you have a space here, this all
matches up just fine, followed by host
followed by more unknowns
dot three
three spaces for .com, .net
etc, followed by the
user agent block
followed by the browser type
followed by accept text X amount
so, when we're
analyzing this consensus sequence, basically what we can
say is okay, here's the structure
of this particular format
we have a get space slash, followed by a variable
link string, followed by HTTP 1.0
I'm not counting new lines or
anything like that at this time, followed by
host, followed by another variable link
sequence, followed by a dot, followed by another
variable link sequence, followed by user agent
variable link sequence, accept
text X amount. So
what we could do at this
point is feed this little
structure into our fuzzer and
just let it start going
this is a completely automated process
I didn't really have to do anything in this case
unfortunately I don't have
any good mixed protocol where it's
half binary, half plain text
for me to show you right now
but
I'll put up some examples on the website and kind of like
walk you through using the tool and stuff like that
that might be actually useful
one thing
that I want to say about this though is
if you'll notice
with these consensus sequences, I'm just
assuming that this is
going to be variable length and
this is not going to mean anything. So basically
what's happening here is I'm losing information
there's a C here and two gaps
there's got to be a better way to
represent these consensus sequences
there's something called sequence logos
and basically what it is
it's kind of just like a stacked histogram
of each offset
so let me find a good example
so right here after the host
you have two W's followed by a
gap. Basically when you stack that
histogram up, usually
it's a W but sometimes it
contains a gap and things like that
so in that case
you don't really lose information and you're actually
able to use a little more of your human intuition
to be able to understand
the alignment a bit better than just
ruling it out
just because there are gaps or because there are mismatches
and things like that
so basically
here's how we're going to analyze
the consensus sequence in
this case. We could do
statistical analysis on each column
by building histograms so we build
our consensus sequence
like I showed you on the previous page
and we look at the mutation rates
and the offset comparison between
each offset. So basically
what we can do is
we can say
this has a
mutation rate of
let me try to find a good example
what we can do is
if you look at this block right here of all these question marks
almost every single one of these
has a similar mutation rate
they have a rate of change that is pretty
constant. So if we
wanted to analyze this like a binary protocol
it's a lot more difficult to
look at just on the screen
we pretty much base our
understanding where the fields begin
and fields end based on the mutation rate
so for instance
what we can do is
look at the rates of mutation
for each offset and
using that we can kind of understand
what the particular field might be
used for.
One thing I wanted to mention though is beware
of junk data. In the last example if there were any
posts in there it would
result in kind of a bad alignment
and it would actually be a little
more difficult to understand
what the general structure was.
What I was talking about earlier
with the clustering algorithms, if you cluster
things correctly and you choose
the root nodes
in each cluster
you'll be able to get decent alignments
out of it instead of trying to align
really distant sequences where lots of gaps
are going to be inserted.
Classification is your friend
the better that you cluster
the packets, the better your sequence
alignment is going to end up being.
This was kind of an experimental
phase about a year ago
when I was working on this but I kind of
already implemented this in code so it's really not that experimental
anymore. I just haven't really had a chance to work on the slides.
At first
what I was basically doing was I was
separating the dynamic data, data that
was changing versus the static data. So in the case
of HTTP I was able to understand
just the different blocks and stuff like that
and understanding the variable length fields
just because it was dynamic data it was changing.
To understand integer
fields this actually worked out pretty good.
You can build
just like an engram frequency table
for 1, 2, and 4 byte window sizes
and you just kind of slide yourself
over the consensus sequence at that point
and you can use
some logic in your program to
try to discern what
the particular function is of that
field. So for example
if two consecutive bytes that are integers
mutate at the same rate
the chances are that they are part of the same field and maybe
they are checksum or something like that. They are changing every
single packet.
The second example
if in two consecutive bytes the least significant
byte increments faster than the greater significant
byte it might be a 16-bit sequence identifier
field or something of that sort.
So
this is all also implemented stuff fortunately.
But what I was going
to basically do is build a protocol profile based on
each consensus and allowing each sequence individually
to break down the structure. So
for example I would
take a
SMB login
authentication packet consensus sequence
I would take a SMB data transfer
packet and then I would align
those two consensus sequences
to understand the general structure
of the packet
format in general. They are still going to be pretty
deviant but you will be able to understand
the specific blocks in between.
Like on block based protocols like ISACAMP
and SMB and things like that
that is actually going to be quite helpful
I would think.
The biggest challenge for me this far
is being able to present the data
in a readable format where the user can actually
understand the results.
So
I have all this stuff kind of implemented
like on a command line tool
which kind of made it difficult so I'm just kind of using
ANSI color and stuff like that to
kind of print all this stuff out.
And the last
thing I wanted to say about this particular tool
is it will never be fully automated
if accuracy is in mind but
if you are doing protocol fuzzing
you don't really have to be accurate necessarily
so it's kind of okay to have
it's kind of okay I guess to have
that kind of entropy
in each sequence.
Let me get this.
Sorry.
So basically what this can be used for is
understanding unknown protocols, some kind of
like
worm for all we know communicates with
its brothers and sisters all over the internet
using some binary format that we've never seen before.
This also allows us
to fuzz network protocols more efficiently because
we don't necessarily have to write protocol specs for them.
If it's a common
protocol I'd probably say just go
read the RFC or something like that and
just look at the ethereal
samples because there's so many of them.
But if you're looking at some black box
protocol you've never ever seen before in your life
this is going to be a tool that would probably
definitely be useful.
Also,
one thing
I kind of forgot to mention but
this can also be used for file formats.
There's really no difference between
a packet format and a file format so if you wanted
to understand some proprietary file
format, same situation.
The only thing that you need to do is just have a lot
of samples that are different.
And also if any of you guys have any ideas
about how this stuff can be used I'm interested in
hearing it.
My conclusion
is this stuff will never be automated
100% like I was describing
the tree building earlier. It's good
if you wanted to
be involved
in each step of the process so you
know which representative sequence is used and which
gaps are inserted because as gaps propagate
down to the
root nodes there can be errant gaps
that make the alignment quite useless
and things like that.
Basically right now I have a Python
proof of concept for this. I have some
C++ code that I'm working on.
It's actually going to be pretty good. I should have it
probably finished in about a month or two.
The Python code right now, I use Pyrex
I don't know if you guys have ever heard that, to do
all the hard, computationally
expensive algorithms like the Neiman
Woons matrix operations and stuff like that.
I don't know if you guys have ever seen this
tool. It's called Orange. It's pretty cool.
It's basically like a widget based
visual programming interface that kind of allows you
to play with different
data mining
algorithms. So you can kind of link together everything.
In this case, what you'd be able
to do with
protocol informatics is be able to say
okay, I want to use this particular
classification
algorithm for clustering. I want to use
this particular sequence alignment algorithm.
I want to use this particular tree building algorithm.
Because there's actually
four different types of tree building algorithms.
There's the upcomma, there's neighbor joining, there's
multiple parsimony, things like that.
There's a multitude of
opportunity to implement all sorts of
things and kind of just figure out what works.
I guess the whole moral
of the story with what I'm trying to say
is
I know it's kind of difficult for people
in this industry to kind of look outside
their science that they're working on
and kind of understand that people might
have already kind of solved everything
back in the day. So this is just kind of a good
example. This stuff was figured out in the
70s and it's 2005
now and we found a use for it.
I'm taking questions
now. Feel free to walk
up to get a microphone up here or something
like that.
Thanks for coming.
Questions?
I can't hear you.
Do you want to come up
here and try to use a mic?
I don't know.
Here you go.
Yeah,
I'm working on almost exactly the same thing
with mutating web things, but I
just walked in on the end of your lecture and
I was talking to this guy who's also
doing tree algorithms, but he's doing
it with granularity
based on the levels of complexity
of the search.
Have you looked at any of that stuff
for your sorting and tree
methods?
Yeah, that's basically a maximum
parsimony tree building. That's where
every
step of the tree, you're going to look at
the complexity
of what it would take for these sequences to mutate
to reach this particular result.
And usually,
evolution chooses the path of
least resistance. So, in maximum
parsimony trees, you have
two different choices. You're going to choose the choice that's the most
simple.
Anyone else?
Okay. Well,
this was a lot of information. I'm sorry if I
didn't have any other ways to represent it
in a kind of clear and concise
manner, but
this is the website for this project
and I encourage you all to
visit the site and download the tool and
just give me feedback if you got it.
So, thanks.
Just want to make an announcement
that Meet the Fed will be at...