[00:02.400 --> 00:11.200]  All right. DEF CON 13 is proud to present Marshall Betto with the Protocol Informatics Project.
[00:13.400 --> 00:18.100]  Saturday morning at DEF CON. God damn, why am I working Saturday morning at DEF CON?
[00:18.160 --> 00:20.480]  All right. Marshall, take it away.
[00:26.520 --> 00:29.760]  All right, so this project is called the Protocol Informatics Project.
[00:29.760 --> 00:34.860]  It's basically a play on words from bioinformatics, which is kind of my main inspiration for this project.
[00:37.200 --> 00:41.700]  Yeah, it's not that loud. Should I talk closer? Okay, there we go. Thanks.
[00:42.420 --> 00:46.700]  So, my name is Marshall Betto. I'm a research scientist at McAfee.
[00:46.700 --> 00:51.220]  However, this is pretty much all independent research. My company's never even seen this stuff.
[00:51.420 --> 00:57.140]  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.
[00:58.600 --> 00:59.920]  Let's start.
[01:00.460 --> 01:04.600]  Well, the purpose of this project is to basically automate network protocol analysis.
[01:04.600 --> 01:09.700]  So, I just added this slide the other night just to kind of say, this is what this thing does.
[01:09.700 --> 01:13.920]  You input a PCAP file, and output is going to be a packet format.
[01:13.920 --> 01:21.080]  So, this is my little XML markup of this particular protocol format, which is just kind of something that's made up,
[01:21.080 --> 01:26.840]  which is basically a two-byte link field followed by an ASCII string or something like that.
[01:28.660 --> 01:32.800]  My application, what it does is it goes through, does a series of comparisons and checks,
[01:32.800 --> 01:38.200]  and uses sequence alignment algorithms to understand the general structure of the format.
[01:38.200 --> 01:45.120]  So, if you were to analyze this markup, basically what it's doing is it's describing this protocol,
[01:45.120 --> 01:50.100]  saying that it operates on UDP 435364, something I just pretty much made up.
[01:50.640 --> 01:56.980]  It's a block-based protocol, so you open up a block, you insert the link to that particular block,
[01:56.980 --> 02:02.240]  which is going to be a short, big in the end, followed by a variable type,
[02:02.240 --> 02:04.260]  which is going to be a plain text string.
[02:04.260 --> 02:06.680]  Right now, the default value for that is going to be hello.
[02:07.040 --> 02:08.240]  And then I close it all out.
[02:08.240 --> 02:12.920]  So, the general idea is, you take a protocol you've never seen before in your life,
[02:12.920 --> 02:16.300]  you're trying to reverse engineer a World of Warcraft, for all I know.
[02:16.480 --> 02:20.360]  You input the PCAP file, and out comes the structure.
[02:20.360 --> 02:22.020]  So, that's the general idea behind it.
[02:23.180 --> 02:30.200]  So, the objective of protocol analysis is, first, to understand exactly the format of every single packet.
[02:30.200 --> 02:36.820]  I mean, that's a pretty simple concept in general, but it does get more complicated as you have to understand
[02:36.820 --> 02:40.540]  the actual state and the actual handshake and things of that sort.
[02:40.540 --> 02:45.060]  So, there's really no good way of doing this at this current time.
[02:45.060 --> 02:46.700]  I mean, it's pretty much a manual process.
[02:46.700 --> 02:49.860]  People sit down with E3O or something like that and break out a piece of paper
[02:49.860 --> 02:53.180]  and just start writing down offsets and trying to use their human intuition
[02:53.180 --> 02:59.320]  to be able to understand what this particular field does and where it's located in the packet.
[03:00.000 --> 03:04.080]  So, this information is generally important to understand proprietary protocols,
[03:04.080 --> 03:07.520]  which are actually kind of becoming a little bit more rare, in my opinion.
[03:07.520 --> 03:10.160]  Of all the security products that I've been looking at and things like that,
[03:10.160 --> 03:12.600]  everybody seems to be using SOAP over SSL nowadays.
[03:12.720 --> 03:17.240]  So, maybe this stuff isn't as applicable in those situations.
[03:17.240 --> 03:22.200]  But, if you're going back and looking at legacy protocols, like some SCADA networks and things like that,
[03:22.200 --> 03:26.180]  this stuff is going to be a lot more useful because there's really not that much documentation
[03:26.180 --> 03:27.440]  for that sort of stuff.
[03:27.440 --> 03:31.260]  So, it's also important for extending the functionality of software.
[03:31.260 --> 03:37.500]  If you guys want to write an open source client for a particular service,
[03:37.500 --> 03:41.040]  this project can help out in that regard.
[03:41.400 --> 03:46.060]  And lastly, and my favorite, is finding vulnerabilities in unknown or badly documented protocols
[03:46.060 --> 03:46.980]  using fuzzing.
[03:46.980 --> 03:52.200]  So, what I basically do is I feed it my PCAP file, it analyzes the structure,
[03:52.200 --> 03:57.400]  pops out the XML markup, then I feed that into my fuzzer and it starts going to work.
[03:58.160 --> 04:01.860]  So, what protocol informatics does, which is just the name of my program basically,
[04:01.860 --> 04:04.260]  it heuristically identifies the fields in data format.
[04:04.260 --> 04:09.640]  So, it's never going to be perfect, but it's as close to automated as you're ever going to get.
[04:11.180 --> 04:16.800]  So, nowadays the problems with protocol analysis in general is it's a manual process.
[04:17.840 --> 04:21.840]  Like I was mentioning earlier, you just pretty much do it by hand using ethereal
[04:21.840 --> 04:25.200]  and fields are identified largely using human intuition.
[04:25.200 --> 04:29.080]  So, I guess I was talking to Spoon about this a little earlier
[04:29.080 --> 04:33.100]  and he was basically explaining to me that, well, all these protocols are written by humans
[04:33.100 --> 04:37.780]  so you can basically use your human intuition to be able to understand how they were thinking
[04:37.780 --> 04:39.020]  and things like that.
[04:39.020 --> 04:43.720]  However, computers have never really been able to mimic human behavior that well.
[04:43.720 --> 04:46.360]  I mean, if you're looking at pattern recognition and things like that,
[04:46.360 --> 04:52.020]  people are moving over neural networks and other hidden markup models and other things of that sort
[04:52.020 --> 04:58.200]  in order to try to mimic that intuition in a computer program.
[04:59.880 --> 05:03.960]  I guess the main challenges with protocol analysis these days is
[05:03.960 --> 05:09.040]  kind of just understanding general structure when it comes to different types of protocols.
[05:09.400 --> 05:14.800]  For example, a protocol that's all binary, usually quite hard to analyze
[05:14.800 --> 05:18.000]  because there's really no points of reference for us.
[05:18.000 --> 05:20.320]  When you're going through it, you're just kind of looking at the bytes
[05:20.320 --> 05:22.740]  and trying to find patterns and things like that.
[05:23.260 --> 05:29.520]  Typically, it doesn't seem like that's going to be pretty much a tedious, painstaking process.
[05:30.080 --> 05:32.280]  So, this is really an attempt to automate that.
[05:33.960 --> 05:38.640]  I think the crux of protocol analysis in general is variable length fields,
[05:39.820 --> 05:42.340]  long strings in the middle of packets and stuff like that.
[05:42.340 --> 05:47.280]  You don't necessarily know, if it's not plain text data, where it starts and where it ends
[05:47.280 --> 05:49.980]  and what each byte represents and things of that sort.
[05:52.700 --> 05:55.220]  Typically, this is all going to be differential analysis.
[05:55.220 --> 05:58.480]  You're just going to be going through, doing comparison, comparison, comparison,
[05:58.480 --> 06:01.420]  trying to kind of build a profile as you go along.
[06:02.440 --> 06:06.400]  Fortunately, however, biologists already fixed this problem back in the 1970s
[06:06.400 --> 06:11.220]  when they were trying to analyze genetic structure, DNA, amino acids, and all that sort of stuff.
[06:11.260 --> 06:15.620]  This is all pretty much... I'm not taking credit for any of these algorithms I'm presenting today.
[06:15.720 --> 06:19.160]  All I'm basically doing is reapplying it to our realm,
[06:19.160 --> 06:21.960]  which is computer security, computer science, and things like that.
[06:23.020 --> 06:25.460]  So, bioinformatics. What is bioinformatics?
[06:25.860 --> 06:28.600]  It's basically information theory applied to biology.
[06:28.600 --> 06:33.840]  So, it's a lot of probability, Shannon entropy, all sorts of things like that.
[06:33.840 --> 06:41.080]  And it's mainly used to identify genes in the genetic structure of organisms.
[06:41.080 --> 06:47.440]  So, Human Genome Project, the majority of the algorithms that are used are mainly sequence alignment algorithms.
[06:47.440 --> 06:52.220]  What they're going out there and trying to find is where the beginning of these genes start and where they end,
[06:52.220 --> 06:55.440]  what the function of these genes are, and what the structure of these genes are,
[06:55.440 --> 06:57.400]  how they fold, and all sorts of things like that.
[06:57.400 --> 07:06.500]  So, the workflow for how biologists do this, they have these large databases just full of genetic data.
[07:07.080 --> 07:13.060]  The human genome's in there, they have mice and every other species that they've sequenced.
[07:13.320 --> 07:16.320]  And they put this all in a database and then they can start running queries on it.
[07:16.320 --> 07:21.320]  So, saying, like, I know that this gene exists in, you know, human.
[07:21.520 --> 07:26.360]  It will go through and it can understand common ancestors and things like that,
[07:26.360 --> 07:29.640]  based on mutation rates and all sorts of stuff like that.
[07:29.640 --> 07:33.760]  So, if you want to put it in simple computational terms,
[07:33.760 --> 07:37.160]  it basically is just processing a large amount of structured but complex data.
[07:37.160 --> 07:40.060]  It's just too much for the human eye to just recognize.
[07:40.060 --> 07:43.160]  So, you have to put it in a database, you have to run these algorithms on it and things like that,
[07:43.160 --> 07:45.460]  if you really want to understand the structure.
[07:48.100 --> 07:52.100]  So, yeah, the objective is to identify genes, determine structure, and the function.
[07:53.280 --> 07:58.640]  Easier said than done, naturally, but there's a lot of analogies to protocol analysis in this case.
[07:58.640 --> 08:05.220]  So, one application of bioinformatics is allowing biologists to map phenotypes to genotypes.
[08:05.220 --> 08:09.180]  Being able to say, blue eyes maps of this particular gene,
[08:09.180 --> 08:12.320]  attached earlobes maps of this particular gene, and things like that.
[08:16.560 --> 08:19.860]  Protocol analysis and bioinformatics have a lot of things in common.
[08:19.860 --> 08:22.120]  They're both operating in large sequences of data.
[08:22.360 --> 08:28.160]  And my favorite is just the analogy of biology's phenotype-to-genotype mapping
[08:28.160 --> 08:31.660]  is equivalent to protocol analysis' mapping of offsets to field locations.
[08:31.660 --> 08:37.860]  We're basically just trying to understand the function of a particular field in a byte stream.
[08:37.860 --> 08:41.520]  We don't know where it exists, but it's between this offset and this offset.
[08:41.520 --> 08:48.920]  Fortunately for us, what actually makes this easier is, when it comes to genes and things like that,
[08:48.920 --> 08:53.500]  it's not all... it doesn't have a defined start and a defined end.
[08:53.720 --> 08:58.080]  You can have... I think eye color, for instance, isn't just like one single gene.
[08:58.080 --> 09:00.120]  It's spread out throughout the genome.
[09:00.120 --> 09:05.100]  So, you have to do a bit more complicated analysis to understand,
[09:05.100 --> 09:09.740]  here's a block where it starts, then it skips this many symbols, and then it restarts over here.
[09:09.740 --> 09:11.860]  So, fortunately for us, it's really not like that.
[09:11.860 --> 09:15.800]  We have fields. Here's your start offset, here's your end offset.
[09:16.660 --> 09:23.860]  So, what I did was I created an application that was meant to understand the structured, complex data found in our protocols.
[09:25.660 --> 09:30.920]  So, the core algorithms that are used in bioinformatics in general are mainly sequence alignment algorithms.
[09:30.920 --> 09:37.100]  There's two of the most classic algorithms, the Niederman-Wunsch algorithm and the Smith-Waterman.
[09:37.320 --> 09:41.020]  I'll get into each particular detail as we go on, but basically,
[09:41.020 --> 09:44.080]  the Niederman-Wunsch algorithm is a global sequence alignment algorithm.
[09:44.080 --> 09:52.780]  It takes into account every single symbol in the genetic sequence and tries to align it to a different sequence.
[09:52.780 --> 09:54.540]  It's just a pairwise alignment.
[09:54.780 --> 09:58.340]  Smith-Waterman, on the other hand, is a local sequence alignment algorithm.
[09:58.340 --> 10:04.320]  It's going to find the most common substring within the two sequences that are most similar.
[10:06.500 --> 10:10.840]  There's ways to improve sequence alignment, and that's basically by using similarity matrices.
[10:10.840 --> 10:12.120]  I'll get into that a little later.
[10:12.420 --> 10:17.180]  All these algorithms are operations on matrices.
[10:18.260 --> 10:21.660]  There's a lot you can do with different weighting and things like that,
[10:21.660 --> 10:29.300]  and assigning scores, and how the matrix is traversed is all dependent on the scores in the cells.
[10:29.360 --> 10:34.040]  There's actually a lot of really neat things that they figured out that they can do using this.
[10:35.360 --> 10:37.660]  Then what we get into is phylogenetic tree building.
[10:37.660 --> 10:44.020]  This is kind of cool, because this is how biologists are able to build a tree of life,
[10:44.020 --> 10:48.580]  not based on fossil record, but instead based on genetic information.
[10:48.580 --> 10:53.220]  How similar are these two sequences, and being able to go all the way up through the evolutionary tree
[10:53.220 --> 10:55.560]  to find common ancestors and things like that.
[10:56.060 --> 11:00.940]  I go over the two tree building algorithms, Upkema and the neighbor joining tree,
[11:00.940 --> 11:04.080]  which I'm sure many people have heard of that.
[11:04.080 --> 11:06.520]  And lastly, I get into multiple sequence alignment,
[11:06.520 --> 11:11.120]  and that's where there's a lot of challenges involved with aligning more than one sequence,
[11:11.120 --> 11:13.200]  just due to computational problems.
[11:13.300 --> 11:16.940]  I go over the progressive and tree-based multiple sequence alignment algorithms.
[11:25.630 --> 11:31.010]  And this is a lot of information, so if I am going too fast, just put your hands up or something like that.
[11:32.870 --> 11:36.590]  The fundamental purpose of sequence alignment is really simple.
[11:36.590 --> 11:39.310]  It's take two sequences, regardless of their length,
[11:39.310 --> 11:42.450]  and insert gaps into either sequence to make them the same length.
[11:43.370 --> 11:45.730]  So, right here I have an example of a DNA alignment.
[11:46.270 --> 11:48.070]  There's four base amino acids in DNA.
[11:48.070 --> 11:50.450]  There's thymine, guanine, cytosine, and adenine.
[11:51.030 --> 11:55.650]  This is kind of just a really simple example of inserting gaps into the first sequence
[11:55.650 --> 11:57.530]  to align it to the second sequence.
[11:57.530 --> 12:06.350]  So, as you can see, there's three gaps that were actually inserted into the first sequence,
[12:06.350 --> 12:11.350]  which would represent a deletion, evolutionary-wise.
[12:12.030 --> 12:14.970]  The Niedermann-Wunsch algorithm, which I mentioned earlier,
[12:14.970 --> 12:18.890]  is a dynamic programming algorithm, meaning that it operates on matrices.
[12:21.070 --> 12:27.010]  I think it was the first sequence alignment algorithm ever written.
[12:27.010 --> 12:30.270]  I think it was 1973 when it first came out.
[12:31.210 --> 12:34.210]  Basically, it performs a global alignment on a pair of sequences,
[12:34.210 --> 12:39.270]  and what that means is that every symbol in the sequence that goes into the algorithm
[12:39.790 --> 12:41.330]  comes out of the algorithm.
[12:41.330 --> 12:42.290]  Gaps are inserted.
[12:42.290 --> 12:44.130]  There's no substring searching or anything like that.
[12:44.130 --> 12:47.470]  It's going to try to insert gaps anywhere it can
[12:47.470 --> 12:50.390]  to make the sequences line up to each other as best as possible
[12:50.390 --> 12:54.430]  to maximize the alignment, maximize the score of the alignment.
[12:55.110 --> 12:57.810]  And it's mainly used for analyzing closely related structures,
[12:57.810 --> 13:01.790]  and the reason for that is if you were trying to analyze the human genome and the mouse genome
[13:01.790 --> 13:05.490]  and using a global sequence alignment algorithm,
[13:05.490 --> 13:10.030]  there's going to be so many gaps that are inserted that it's not even going to be relevant at that point.
[13:10.570 --> 13:15.570]  It's mainly used for maybe comparing two different types of humans' DNA
[13:15.570 --> 13:18.010]  to understand a brown-eyed person versus a blue-eyed person
[13:18.010 --> 13:21.410]  versus an attached earlobes person versus a dangling.
[13:23.790 --> 13:27.570]  Dynamic programming is a common concept in computer science.
[13:27.570 --> 13:29.850]  It's not coding, per se.
[13:29.850 --> 13:35.670]  It's just a terminology that's used to solve problems by using matrices.
[13:35.670 --> 13:38.170]  So the idea is to break the problem up into subproblems.
[13:38.170 --> 13:40.290]  So you have a matrix.
[13:40.290 --> 13:44.810]  You perform a computation on each cell in the matrix,
[13:44.810 --> 13:47.910]  and as the algorithm progresses,
[13:47.910 --> 13:50.710]  it uses information that was previously gained in the other cells
[13:50.710 --> 13:54.590]  to progress until the end of the process.
[13:54.590 --> 14:00.850]  So the results of the previous computations are saved and used by the remaining subproblems.
[14:00.850 --> 14:02.630]  And Niedermann-Wunsch is a dynamic programming algorithm,
[14:02.630 --> 14:05.610]  as is most of the sequence alignment algorithms out there.
[14:16.230 --> 14:21.290]  So how Niedermann-Wunsch works, it's actually a pretty simple little operation that it does.
[14:21.770 --> 14:24.490]  The first sequence is placed in the topmost row,
[14:24.490 --> 14:27.190]  and the second sequence is placed in the leftmost column.
[14:27.950 --> 14:30.250]  And basically there's this little equation right here
[14:30.250 --> 14:35.430]  that basically is used to assess each cell in the matrix,
[14:35.430 --> 14:37.230]  starting at position 1, 1.
[14:38.230 --> 14:41.850]  There's three steps for these sequence alignment algorithms.
[14:41.850 --> 14:43.790]  The first step is to assign a similarity score.
[14:43.790 --> 14:45.370]  So basically what you do is,
[14:45.370 --> 14:48.430]  you go through and you score every single similarity
[14:48.430 --> 14:52.410]  between the character in sequence 1 and the character in sequence 2.
[14:53.130 --> 14:57.590]  The second step is you assess all possible pathways through the matrix,
[14:57.590 --> 15:00.790]  left, up, and diagonal from the particular cell that you're in,
[15:00.790 --> 15:04.050]  assigning the current cell with the value of the maximum scoring pathway
[15:04.050 --> 15:05.810]  using this particular equation,
[15:05.810 --> 15:10.270]  which I have a matrix on the next slide that will make it a bit easier to understand.
[15:10.450 --> 15:14.110]  The third step is constructing a pathway from the highest scoring cell
[15:14.110 --> 15:16.490]  back to the beginning of the matrix.
[15:16.850 --> 15:21.710]  And what this represents is the insertion of gaps in each sequence.
[15:23.510 --> 15:24.550]  And lastly...
[15:24.550 --> 15:26.770]  Okay, actually, let me get back to the equation.
[15:28.030 --> 15:31.010]  What you're going to do is, when you're in cell IJ,
[15:31.010 --> 15:33.010]  you're going to look at your diagonal cell,
[15:33.010 --> 15:36.150]  which is I-1, J-1, plus S-IJ,
[15:36.150 --> 15:38.370]  which S-IJ is going to be the similarity score
[15:40.290 --> 15:43.770]  between the offset I and offset J in each sequence.
[15:44.550 --> 15:46.810]  It's also going to look at the left...
[15:47.790 --> 15:52.050]  It's going to look at the left cell from the current position,
[15:52.050 --> 15:54.010]  and it's going to add a gap penalty
[15:54.010 --> 15:56.530]  because if you're going left or if you're going up,
[15:56.530 --> 15:58.750]  you're actually inserting a gap into the sequence.
[15:58.750 --> 16:00.090]  And that's not necessarily a good thing
[16:00.090 --> 16:03.230]  because it kind of makes it a bit irrelevant if there's too many gaps.
[16:03.230 --> 16:04.890]  So there's something called the gap penalty
[16:04.890 --> 16:10.890]  that will basically dock the alignment score at the end.
[16:10.890 --> 16:14.010]  So you'll be able to understand what the relative...
[16:16.690 --> 16:19.850]  You'll be able to really understand how important this alignment is
[16:19.850 --> 16:20.890]  and what it really represents.
[16:20.890 --> 16:22.050]  If it has a really low score,
[16:22.050 --> 16:24.370]  then you know that it's probably really not that significant.
[16:26.590 --> 16:29.270]  So this is the visualization of the concept.
[16:29.270 --> 16:32.170]  I use HTTP just because everybody understands it.
[16:32.170 --> 16:34.670]  It's a text-based protocol. It's really simple.
[16:34.670 --> 16:37.010]  You actually probably wouldn't ever have to use this program
[16:37.010 --> 16:40.710]  to do text-based protocols just because they're so easy.
[16:40.930 --> 16:44.190]  But for example's sake,
[16:44.190 --> 16:46.950]  I use it just because it's small enough
[16:46.950 --> 16:48.690]  to fit into a PowerPoint presentation.
[16:48.690 --> 16:54.570]  So the first sequence is placed in the topmost row,
[16:54.570 --> 16:57.510]  which is git slash index.html HTTP 1.0.
[16:57.510 --> 17:00.970]  And the second sequence is git slash HTTP 1.0.
[17:01.350 --> 17:03.210]  So as mentioned earlier,
[17:03.210 --> 17:04.890]  you just kind of iterate through the matrix
[17:04.890 --> 17:11.350]  and you perform the scoring based on the similarity between each character.
[17:11.350 --> 17:14.330]  So right here, the Gs match,
[17:14.330 --> 17:17.790]  so you score with one and so on.
[17:17.790 --> 17:20.390]  So you go out and you build up the matrix.
[17:20.410 --> 17:21.590]  One thing to be mentioned, though, is
[17:21.590 --> 17:24.910]  Needleman-Wunsch, kind of like the default
[17:24.910 --> 17:26.330]  runtime environment for it,
[17:26.330 --> 17:30.090]  is to have a match score of 1,
[17:30.930 --> 17:32.690]  a gap penalty of 0,
[17:32.690 --> 17:35.770]  and a mismatch score of 0.
[17:35.770 --> 17:37.930]  So in some cases,
[17:37.930 --> 17:40.410]  you can actually make this a bit more complex
[17:40.410 --> 17:45.530]  by having different scoring mechanisms.
[17:45.530 --> 17:47.010]  G might have a stronger alignment,
[17:47.010 --> 17:48.750]  so you have a higher score in that case,
[17:48.750 --> 17:49.550]  and things like that.
[17:49.550 --> 17:52.530]  And when I talk about similarity matrices a little later on,
[17:52.530 --> 17:54.750]  you'll kind of understand what I'm talking about.
[17:54.750 --> 17:57.270]  It's probably a little too early for that.
[17:59.130 --> 18:00.410]  So what you do is
[18:00.410 --> 18:04.450]  you start in cell 1-1,
[18:04.450 --> 18:06.410]  and you look at your left cell,
[18:06.410 --> 18:07.310]  your diagonal cell,
[18:07.310 --> 18:08.490]  and your upper cell.
[18:08.830 --> 18:10.670]  And you apply this little equation right here,
[18:10.670 --> 18:12.330]  which is going to take the maximum value
[18:12.330 --> 18:14.250]  of the diagonal,
[18:14.250 --> 18:15.730]  or the left,
[18:15.730 --> 18:17.190]  or the upper.
[18:18.590 --> 18:19.750]  For the diagonal cell,
[18:19.750 --> 18:23.430]  you actually add the score of that position.
[18:23.430 --> 18:25.330]  So in this case,
[18:25.870 --> 18:26.730]  it's going to look at diagonal
[18:27.250 --> 18:28.570]  and add 1,
[18:28.570 --> 18:30.570]  because the G's match.
[18:31.210 --> 18:33.010]  There's no match here, there's no match here,
[18:33.010 --> 18:35.330]  so the maximum is going to be the diagonal plus 1.
[18:35.330 --> 18:37.690]  So it's going to leave it a 1.
[18:38.090 --> 18:40.030]  And the way that these matrices are traversed,
[18:40.030 --> 18:41.410]  they're traversed left to right,
[18:41.410 --> 18:43.130]  and then they move downward.
[18:44.590 --> 18:47.610]  The next step, move over one position.
[18:48.250 --> 18:50.050]  This time, it's going to look left,
[18:50.050 --> 18:50.810]  it's going to look diagonal,
[18:50.810 --> 18:51.870]  it's going to look up.
[18:52.450 --> 18:53.810]  It's going to take the maximum.
[18:55.230 --> 18:57.330]  In this case, before, the cell was 0,
[18:57.330 --> 19:00.330]  so this S-I-J in this case is going to be 0.
[19:03.070 --> 19:05.850]  It realizes that the leftmost cell in this case
[19:05.850 --> 19:07.050]  is going to be the maximum,
[19:07.050 --> 19:12.330]  so it places that particular value in this cell.
[19:13.130 --> 19:14.810]  It's a really simple operation, actually.
[19:14.810 --> 19:17.930]  It just goes cell by cell and it builds up.
[19:18.210 --> 19:19.850]  This is kind of like the completed matrix.
[19:20.030 --> 19:21.750]  I do this all in hex down here
[19:21.750 --> 19:24.110]  just to make it all line up and look pretty on the screen.
[19:25.090 --> 19:26.630]  Basically, this is kind of how it looks
[19:26.630 --> 19:30.650]  after you perform all the scoring of the matrix.
[19:30.650 --> 19:31.670]  The next step at this point
[19:31.670 --> 19:35.210]  is to actually traverse back to the beginning of the matrix
[19:35.210 --> 19:38.410]  and understand what your alignment is going to be.
[19:39.370 --> 19:42.630]  In this case, typically,
[19:42.630 --> 19:46.030]  the maximum cell is always going to be your bottom right.
[19:47.090 --> 19:49.810]  What we do is we start in the bottom right cell in this case
[19:49.810 --> 19:51.370]  because it had the highest value.
[19:52.370 --> 19:53.670]  We look at the neighboring cells
[19:53.670 --> 19:55.270]  and we choose the cell with the maximum value
[19:55.270 --> 19:56.610]  and traverse there.
[19:57.630 --> 19:58.990]  We start here at E
[19:59.490 --> 20:01.970]  and we notice that our neighbors are all Ds.
[20:01.970 --> 20:03.610]  Basically, that means that we can go anywhere
[20:03.610 --> 20:04.730]  because they're all equal.
[20:04.730 --> 20:06.710]  We can go left, we can go up, we can go diagonal.
[20:07.190 --> 20:09.470]  I personally like to just go diagonal
[20:09.470 --> 20:11.530]  just because it just makes the most sense.
[20:11.530 --> 20:14.570]  Basically, it signifies that there's not going to be any gap
[20:14.570 --> 20:17.090]  that's inserted into any of the sequences,
[20:17.720 --> 20:20.550]  which may mean that there's actual match there.
[20:23.870 --> 20:28.930]  This is kind of the evolution at this current point.
[20:29.470 --> 20:34.170]  Starting down here, we look, we go diagonal because it's D.
[20:34.170 --> 20:35.790]  At this point in D, we look around.
[20:35.790 --> 20:36.870]  All of our neighbors are C.
[20:36.870 --> 20:38.890]  We want to go diagonal again by default.
[20:39.550 --> 20:40.650]  My mouse is disappearing.
[20:40.870 --> 20:42.330]  The same deal here.
[20:42.330 --> 20:44.290]  All B, so we go diagonal.
[20:44.290 --> 20:45.150]  All the neighbors are A.
[20:45.150 --> 20:46.150]  Go back to A.
[20:46.170 --> 20:47.850]  Neighbors are 9, etc., etc.
[20:47.970 --> 20:51.610]  All until we reach this point up here at this 5.
[20:51.810 --> 20:53.590]  And we look at our neighboring cells again
[20:53.590 --> 20:55.450]  and we realize that there's a 5 to our left,
[20:55.510 --> 20:57.510]  a 4 to our diagonal, and a 4 to our up.
[20:57.510 --> 20:59.390]  We want to have the maximized alignment
[20:59.390 --> 21:01.330]  so we're going to take the path
[21:01.330 --> 21:03.830]  that will result in the maximum score.
[21:04.330 --> 21:06.370]  So at this point, we're going to start going left.
[21:08.170 --> 21:09.550]  This is the completed traverse
[21:09.550 --> 21:11.530]  all the way back to the beginning of the matrix.
[21:11.650 --> 21:12.790]  So at this point...
[21:13.550 --> 21:14.270]  Goddamn.
[21:14.810 --> 21:17.090]  So at this point, we're looking around.
[21:17.090 --> 21:19.150]  We notice that 5 to our left is the maximum,
[21:19.150 --> 21:19.850]  so we're going to go there.
[21:19.850 --> 21:20.530]  Same thing.
[21:20.710 --> 21:23.190]  We're surrounded by two 4s and a 5 on the left,
[21:23.190 --> 21:25.530]  so we go left, etc., etc.,
[21:25.530 --> 21:27.730]  all the way until we hit back here.
[21:29.470 --> 21:31.030]  And all of them are equal again,
[21:31.030 --> 21:32.710]  so we decide that we're going to go diagonal.
[21:32.750 --> 21:35.270]  And then it goes all the way back to the root.
[21:36.430 --> 21:38.250]  So what this means at this point
[21:38.250 --> 21:40.190]  is there are going to be gaps
[21:40.190 --> 21:41.830]  inserted into one of these sequences.
[21:43.150 --> 21:44.670]  So what did this do?
[21:44.750 --> 21:46.610]  We computed a path through the matrix,
[21:46.610 --> 21:48.390]  and now we can apply the rules of Needham and Woons
[21:48.390 --> 21:50.250]  to obtain the two aligned sequences.
[21:50.630 --> 21:51.910]  Basically, here's the rule.
[21:52.270 --> 21:55.070]  Any time that you traverse left on the matrix,
[21:55.470 --> 21:56.750]  a gap is inserted into a sequence.
[21:56.750 --> 21:57.570]  So when you go left,
[21:57.570 --> 22:00.010]  it's going to insert a gap into sequence 1
[22:00.010 --> 22:01.390]  at that particular offset.
[22:01.390 --> 22:02.950]  If you ever go up,
[22:02.950 --> 22:04.290]  you're going to insert a gap at that offset
[22:04.290 --> 22:05.670]  in the first sequence.
[22:05.690 --> 22:08.410]  So, here's the results of that particular alignment.
[22:10.310 --> 22:12.030]  On the bottom down here,
[22:12.030 --> 22:14.110]  kind of a lame example with HTTP, I know,
[22:14.110 --> 22:15.990]  but it illustrates the point.
[22:16.930 --> 22:19.470]  There's gaps that are inserted right here
[22:19.470 --> 22:20.490]  under index.html
[22:20.490 --> 22:21.790]  because that particular sequence
[22:21.790 --> 22:24.410]  did not have that file in there,
[22:24.410 --> 22:26.610]  and everything else matches up.
[22:27.130 --> 22:28.970]  So what this allows us to do, really,
[22:28.970 --> 22:31.510]  is to understand the beginning and ending
[22:31.510 --> 22:33.610]  of the boundaries in the packet.
[22:36.030 --> 22:39.190]  So, if you wanted to analyze this really simple example,
[22:39.190 --> 22:40.850]  you can say that, okay,
[22:40.850 --> 22:44.030]  these two sequences had git slash in common.
[22:44.310 --> 22:46.030]  We can consider that a keyword.
[22:46.650 --> 22:48.850]  Index.html was a file name.
[22:48.910 --> 22:50.690]  It's a variable length field.
[22:50.870 --> 22:52.810]  You can put any file in there that you want.
[22:53.470 --> 22:56.310]  And it was subject to deletion in the second sequence.
[22:56.310 --> 22:57.870]  So what we can assume at this point
[22:57.870 --> 23:00.010]  is that that is a variable length field
[23:00.010 --> 23:02.090]  because it was subject to deletion,
[23:02.090 --> 23:04.750]  followed by the keyword HTTP 1.0.
[23:06.550 --> 23:09.950]  So, if you wanted to actually describe this protocol
[23:09.950 --> 23:11.010]  in a fuzzer, you could say,
[23:11.010 --> 23:12.950]  okay, we're going to send a git space slash
[23:12.950 --> 23:14.970]  and we're going to send a whole bunch
[23:14.970 --> 23:16.210]  of random data in between,
[23:16.210 --> 23:17.690]  followed by HTTP 1.0.
[23:17.690 --> 23:18.590]  Pretty simple.
[23:20.850 --> 23:22.870]  This leads us into explaining
[23:22.870 --> 23:24.990]  the local sequence alignment algorithm,
[23:24.990 --> 23:26.750]  which is used kind of for a different purpose.
[23:26.750 --> 23:29.890]  So, this is called Smith-Waterman.
[23:29.890 --> 23:32.730]  I think it was written in 1979, I think.
[23:32.730 --> 23:34.010]  I might be wrong about that.
[23:34.010 --> 23:36.050]  It's basically a derivative of Needleman-Wunsch.
[23:36.050 --> 23:38.750]  It just has some different rules, basically.
[23:40.530 --> 23:42.970]  What the point that it's trying to do
[23:42.970 --> 23:44.710]  is find the maximum local alignment
[23:44.710 --> 23:45.910]  between the two sequences,
[23:45.910 --> 23:48.710]  which is going to be a subsequence between the two.
[23:49.390 --> 23:54.310]  It's going to find the subset in each sequence
[23:54.310 --> 23:57.630]  that makes the most sense.
[23:57.950 --> 23:59.670]  And that may be subject to gaps
[23:59.670 --> 24:01.290]  and it might not necessarily.
[24:01.830 --> 24:03.390]  So, this is especially useful
[24:03.390 --> 24:05.630]  in determining similarity between distance sequences
[24:05.630 --> 24:08.670]  because you could look at a chimpanzee genome
[24:08.670 --> 24:09.950]  and a human genome
[24:09.950 --> 24:11.550]  and use local sequence alignment algorithms
[24:11.550 --> 24:14.330]  and you'll actually get a lot more data out of it
[24:14.330 --> 24:18.390]  because the alignments will actually mean a lot more in the end.
[24:18.530 --> 24:21.470]  So, local alignment has a strong scoring mechanism,
[24:21.470 --> 24:22.370]  whereas global is weak
[24:22.370 --> 24:24.050]  because of the number of gaps
[24:24.050 --> 24:26.930]  that may be inserted into the global alignment.
[24:27.670 --> 24:30.230]  So, local alignment algorithms are used a lot
[24:30.230 --> 24:33.610]  to kind of search the database
[24:33.610 --> 24:37.490]  to understand which species are the most similar to others
[24:37.490 --> 24:38.730]  and things like that.
[24:42.440 --> 24:44.340]  So, how Smith-Waterman works,
[24:44.340 --> 24:46.200]  it's a derivative of Needleman-Wunsch.
[24:46.200 --> 24:47.220]  The only difference is
[24:47.220 --> 24:50.360]  you kind of start it with some different initial values.
[24:52.200 --> 24:54.380]  Also, this is kind of like a default run.
[24:54.380 --> 24:57.560]  You can also use similarity matrices and things like that
[24:57.560 --> 24:59.140]  to modify how this works.
[24:59.140 --> 25:03.120]  But by default, it has a match score of 2.
[25:03.360 --> 25:06.520]  So, if G and G match, we assign that a 2.
[25:06.520 --> 25:08.040]  It has a gap penalty of negative 2.
[25:08.040 --> 25:10.480]  Any time that we move up or any time that we move left,
[25:10.480 --> 25:14.060]  we're going to subtract negative 2 from the alignment score.
[25:14.960 --> 25:18.220]  The lower the alignment score, the less significant it is.
[25:18.420 --> 25:21.100]  Any mismatch, so G and E don't match,
[25:21.100 --> 25:23.560]  it's going to have a mismatch score of negative 1.
[25:24.440 --> 25:28.140]  The difference is, when you're in the matrix,
[25:28.140 --> 25:32.540]  you start in the cell that has the highest score,
[25:32.540 --> 25:34.480]  and you're going to start traversing back.
[25:34.480 --> 25:37.680]  The difference is, when the score hits 0 in the matrix,
[25:37.680 --> 25:39.340]  you're going to return immediately.
[25:39.500 --> 25:42.540]  And at that point, those particular offsets in the matrix
[25:42.540 --> 25:44.640]  are the ones that are saved and used
[25:44.640 --> 25:46.580]  as a representative local alignment sequence.
[25:58.100 --> 26:02.020]  I actually didn't do a matrix and stuff like that.
[26:02.020 --> 26:04.400]  It was kind of short notice and things like that.
[26:04.400 --> 26:07.260]  But basically, if you want to align these two sequences,
[26:07.260 --> 26:09.040]  same thing as before,
[26:09.040 --> 26:11.260]  the score's going to end up being 18,
[26:11.260 --> 26:15.680]  and it's going to find the substring space, HTTP slash 1.0,
[26:15.680 --> 26:18.560]  as being the most common local alignment
[26:18.560 --> 26:20.380]  in those particular sequences.
[26:20.380 --> 26:24.520]  So that's going to be the most similar difference between the two.
[26:26.360 --> 26:28.080]  Smith-Waterman is actually used a lot
[26:28.080 --> 26:30.260]  to determine the distance between two sequences.
[26:30.260 --> 26:34.080]  So if you want to find the distance between sequence 1 and sequence 2,
[26:34.080 --> 26:37.020]  you're going to take the Smith-Waterman score of sequence 1
[26:37.020 --> 26:38.480]  running against itself,
[26:38.480 --> 26:40.640]  minus the Smith-Waterman score of sequence 1
[26:40.640 --> 26:42.360]  aligned with sequence 2.
[26:42.360 --> 26:45.200]  So in this case, it's 48 minus 18, which is 30.
[26:45.200 --> 26:47.100]  So the distance is going to be 30.
[26:47.100 --> 26:49.340]  Just pretty simple.
[26:50.780 --> 26:52.580]  Basically, here's how it's used.
[26:52.580 --> 26:55.360]  In my program, it's not necessarily used
[26:55.360 --> 26:56.720]  to determine the protocol fields.
[26:56.720 --> 26:59.200]  I use it just as a classifier
[26:59.200 --> 27:01.080]  to allow me to build
[27:01.080 --> 27:03.320]  kind of like a relationship matrix
[27:03.320 --> 27:05.520]  and understand which packets
[27:05.520 --> 27:06.700]  in the tcpdump file
[27:06.700 --> 27:08.380]  are the most similar to each other.
[27:08.380 --> 27:11.620]  Because if you're looking at a complex protocol
[27:11.620 --> 27:13.300]  like isocamp or smb
[27:13.300 --> 27:14.040]  or something like that,
[27:14.040 --> 27:16.340]  they have multiple different message types.
[27:16.640 --> 27:17.980]  This is actually going to be really helpful
[27:17.980 --> 27:19.440]  because it's going to allow us to cluster
[27:20.020 --> 27:22.280]  the different types of messages
[27:22.280 --> 27:23.920]  within that particular protocol.
[27:25.560 --> 27:27.240]  It's used to calculate the relative distance
[27:27.240 --> 27:28.700]  between sequences for clustering purposes
[27:28.700 --> 27:30.460]  and tree building, which we'll get into later.
[27:30.460 --> 27:33.320]  In bioinformatics,
[27:33.320 --> 27:35.060]  Smith-Waterman is used for multiple sequence alignment
[27:35.060 --> 27:37.040]  because DNA has no start and end
[27:37.040 --> 27:38.600]  whereas a packet does.
[27:38.600 --> 27:40.740]  That's also another big advantage that we have.
[27:40.740 --> 27:42.980]  We know where the packet starts, we know where the packet ends.
[27:42.980 --> 27:45.020]  We also have fields that start here and end there.
[27:45.020 --> 27:48.540]  There's no fields that are going to span
[27:48.540 --> 27:50.440]  over multiple blocks
[27:50.440 --> 27:51.660]  and jump in over each other
[27:51.660 --> 27:52.360]  and stuff like that,
[27:52.360 --> 27:54.280]  like it does in DNA.
[27:57.380 --> 27:59.740]  To improve these alignment algorithms,
[27:59.740 --> 28:01.800]  we use what's called a similarity matrix.
[28:01.840 --> 28:05.220]  Basically, we replace our scoring mechanism.
[28:05.920 --> 28:07.100]  Before, I was showing you
[28:07.100 --> 28:08.940]  that a match score would equal 1
[28:08.940 --> 28:10.700]  in Niedermann-Wunsch, a match score in
[28:10.700 --> 28:13.520]  Smith-Waterman would equal 2, and things like that.
[28:13.620 --> 28:15.180]  Similarity matrices, on the other hand,
[28:15.180 --> 28:16.740]  are tables
[28:17.400 --> 28:18.740]  based on the probability
[28:19.360 --> 28:20.840]  that this sequence is allowed
[28:20.840 --> 28:22.860]  to mutate into another sequence.
[28:23.200 --> 28:25.100]  In evolution, it is possible
[28:25.100 --> 28:27.820]  for different amino acids
[28:27.820 --> 28:28.760]  to mutate
[28:28.760 --> 28:30.840]  into others, but not
[28:30.840 --> 28:31.620]  other ones.
[28:31.720 --> 28:34.700]  It basically allows
[28:35.240 --> 28:37.040]  biologists to say,
[28:37.040 --> 28:38.680]  adenine can mutate into thymine
[28:38.680 --> 28:40.260]  but not cytosine, and things like that.
[28:40.260 --> 28:42.600]  By the way, I'm not a biologist, I don't actually know
[28:42.600 --> 28:44.680]  if that is true, but it's just an example.
[28:46.080 --> 28:46.800]  Similarity matrices
[28:48.280 --> 28:56.340]  are pretty different, I guess, because
[28:57.500 --> 28:58.440]  it's kind of
[28:58.440 --> 28:59.800]  based on preference.
[29:00.440 --> 29:02.400]  There's similarity matrices out there that are
[29:02.400 --> 29:04.080]  used only when
[29:04.620 --> 29:06.440]  comparing really distant sequences,
[29:06.440 --> 29:08.200]  and there's similarity matrices that are used when comparing
[29:08.200 --> 29:10.520]  really close sequences.
[29:11.620 --> 29:12.540]  The applications
[29:12.540 --> 29:14.420]  to protocol analysis is really good, though, because
[29:14.420 --> 29:16.400]  we have data types. We have
[29:16.400 --> 29:18.360]  plaintext data, we have binary data,
[29:18.360 --> 29:19.800]  and things like that.
[29:20.240 --> 29:22.080]  We can assume that binary data
[29:22.080 --> 29:24.200]  is acceptable for binary data to mutate
[29:24.200 --> 29:26.120]  into other binary data, and plaintext data
[29:26.120 --> 29:28.040]  to mutate into other plaintext data.
[29:28.040 --> 29:30.480]  Especially if you're using a
[29:30.480 --> 29:32.460]  protocol that usually uses English words,
[29:32.460 --> 29:34.360]  you can actually have a
[29:34.360 --> 29:36.280]  similarity matrix that accepts
[29:37.220 --> 29:38.400]  I before E
[29:38.400 --> 29:40.660]  and other kind of common
[29:40.660 --> 29:44.460]  linguistic rules like that.
[29:44.460 --> 29:46.180]  So,
[29:46.180 --> 29:48.520]  the protocol informatics similarity matrices,
[29:48.520 --> 29:50.200]  our alphabet is 256
[29:50.920 --> 29:52.020]  bytes long, so we have a
[29:52.020 --> 29:53.880]  256 by 256 matrix,
[29:53.880 --> 29:56.040]  and each mutation,
[29:56.040 --> 29:57.660]  each cell contains
[29:57.660 --> 29:59.720]  mutation probabilities between every character, so
[29:59.720 --> 30:01.620]  we might say that it's acceptable for
[30:01.620 --> 30:03.680]  A to mutate into E, but not into
[30:03.680 --> 30:06.500]  hex FF and things like that.
[30:07.040 --> 30:07.620]  So,
[30:08.560 --> 30:09.800]  this is actually kind of some
[30:09.800 --> 30:12.500]  outdated stuff. There's actually a lot easier ways of doing this.
[30:12.520 --> 30:13.440]  So,
[30:13.440 --> 30:15.040]  what this allows us to do is
[30:15.040 --> 30:18.000]  obtain a bit more optimized alignments.
[30:18.160 --> 30:19.700]  This way, if we use these
[30:19.700 --> 30:21.520]  similarity matrices that are specially tailored
[30:21.520 --> 30:23.620]  for different types of network protocols,
[30:23.620 --> 30:25.480]  if you have one that's mixed,
[30:25.480 --> 30:27.440]  has plaintext in it and binary data in it,
[30:27.440 --> 30:29.900]  you could use a particular similarity matrix in there.
[30:30.000 --> 30:31.700]  And basically what this does is it allows
[30:31.700 --> 30:33.700]  when gaps are inserted into the sequences,
[30:34.520 --> 30:35.680]  the alignment is still
[30:35.680 --> 30:36.860]  going to hold true where
[30:37.860 --> 30:39.600]  plaintext data is only mutating into other
[30:39.600 --> 30:41.520]  plaintext data, binary data is only mutating into
[30:41.520 --> 30:44.320]  other binary data. You're not going to have any mismatches in between.
[30:44.320 --> 30:45.620]  So, I guess
[30:45.620 --> 30:47.680]  the kind of role of similarity matrices though
[30:47.680 --> 30:49.180]  is that they're
[30:49.680 --> 30:51.800]  going to really have to be tweaked.
[30:52.000 --> 30:53.160]  And you could have
[30:54.380 --> 30:55.700]  probabilistic models, you can do some
[30:55.700 --> 30:57.420]  Markov chains and stuff like that to
[30:57.420 --> 31:00.380]  initially build your stuff, but it's also kind of subjective.
[31:01.100 --> 31:01.960]  I can say
[31:01.960 --> 31:03.620]  that I know that
[31:07.400 --> 31:07.880]  a plaintext
[31:07.880 --> 31:09.600]  character is commonly followed
[31:09.600 --> 31:11.680]  by a null, so it's able
[31:11.680 --> 31:13.940]  to mutate into a null character and stuff like that.
[31:14.000 --> 31:15.560]  That's very acceptable.
[31:15.560 --> 31:17.880]  So, bioinformatics
[31:17.880 --> 31:19.800]  scientists spend years perfecting their version of similarity
[31:19.800 --> 31:21.780]  matrices. I don't know how many revisions
[31:21.780 --> 31:23.560]  there are of Blozeman and the PAM matrices,
[31:24.080 --> 31:25.700]  but there's quite a lot, and they're each
[31:25.700 --> 31:27.340]  used for kind of different purposes.
[31:34.780 --> 31:35.620]  I kind of actually had
[31:36.440 --> 31:36.880]  a problem
[31:37.620 --> 31:39.540]  trying to represent this stuff and kind of
[31:40.640 --> 31:41.700]  allow others to
[31:41.700 --> 31:43.600]  understand kind of what I'm talking about.
[31:43.860 --> 31:45.780]  And this isn't actually that great, but
[31:45.780 --> 31:47.780]  this is just a kind of stupid example.
[31:47.780 --> 31:49.540]  This superscript B just stands for binary.
[31:49.540 --> 31:51.440]  So let's just assume it's like 0x01,
[31:51.440 --> 31:53.920]  0x02, 0x03, etc.
[31:53.920 --> 31:56.300]  So if you wanted to align these protocols,
[31:56.300 --> 31:57.600]  alignment without proper scoring
[31:57.600 --> 31:58.740]  might actually
[31:59.720 --> 32:01.420]  insert gaps into incorrect
[32:01.420 --> 32:03.540]  places and
[32:03.540 --> 32:05.180]  assume that
[32:05.180 --> 32:07.560]  F might be able to mutate
[32:07.560 --> 32:09.820]  into 0x01 and 0x04
[32:09.820 --> 32:11.280]  and stuff like that, which isn't necessarily
[32:11.620 --> 32:12.880]  a correct alignment.
[32:13.620 --> 32:15.440]  If you use a similarity matrix
[32:15.440 --> 32:17.400]  with decent data
[32:17.400 --> 32:19.380]  that keeps track of
[32:19.380 --> 32:22.160]  mutations between different types of data types,
[32:22.160 --> 32:23.440]  you'll start getting better
[32:23.440 --> 32:25.360]  alignments where all the ASCII
[32:25.360 --> 32:27.340]  data is aligned to each other, all the binary data is
[32:27.340 --> 32:28.780]  aligned to each other, and things like that.
[32:28.780 --> 32:31.300]  So it's basically just a tool to help us
[32:32.180 --> 32:32.600]  signify
[32:33.500 --> 32:35.160]  our alignments a bit better.
[32:36.980 --> 32:37.400]  So
[32:38.240 --> 32:39.580]  I kind of explained so far
[32:39.580 --> 32:41.320]  how to do a pairwise sequence alignment, which
[32:41.320 --> 32:43.860]  isn't that useful. Just have a
[32:43.860 --> 32:45.380]  look at two HTTP requests and say,
[32:45.380 --> 32:47.660]  okay, here's the variable link field.
[32:47.660 --> 32:49.340]  This is where you put file names.
[32:49.340 --> 32:50.740]  It's really not that big of a deal.
[32:52.460 --> 32:53.460]  But it's really not that
[32:53.460 --> 32:55.560]  pairwise sequence alignment isn't really that useful.
[32:55.560 --> 32:57.480]  You really have to start getting the multiple sequence
[32:57.480 --> 32:59.180]  alignment if you really want to
[32:59.180 --> 33:01.240]  get significant results.
[33:04.960 --> 33:06.900]  Multiple sequence alignment is basically the
[33:06.900 --> 33:09.040]  act of aligning more than two sequences.
[33:10.240 --> 33:10.660]  It uses
[33:10.660 --> 33:12.660]  Niedermann-Munch as the alignment algorithm and uses
[33:12.660 --> 33:14.700]  Smith-Waterman as a scoring algorithm.
[33:14.700 --> 33:16.760]  The problem with this is there's computation
[33:16.760 --> 33:17.640]  issues.
[33:21.920 --> 33:23.300]  So Niedermann-Munch, as I
[33:23.300 --> 33:25.220]  showed before, it operates
[33:25.220 --> 33:27.220]  on a n by n, or
[33:27.220 --> 33:29.160]  excuse me, n by m matrix where n is
[33:29.160 --> 33:31.160]  the length of sequence one and m is the length of
[33:31.160 --> 33:33.320]  sequence two. If you want
[33:33.320 --> 33:35.180]  to start aligning three sequences, you can
[33:35.180 --> 33:37.380]  start building hypercubes and things like that and traversing
[33:37.380 --> 33:38.540]  through hypercubes.
[33:38.660 --> 33:40.800]  The problem is the operation is
[33:40.800 --> 33:43.080]  n to the nth power where n is the length of sequences
[33:43.080 --> 33:44.660]  and n is the number of sequences.
[33:44.660 --> 33:46.640]  This isn't really going to be feasible
[33:46.640 --> 33:48.540]  for us. So I have my little
[33:48.540 --> 33:50.900]  illustration of my hypercube being traversed.
[33:50.900 --> 33:52.780]  It can be done,
[33:52.780 --> 33:54.700]  but I've been trying to align
[33:54.700 --> 33:56.740]  sequences that are up to 1500 bytes
[33:56.740 --> 33:58.520]  in length and it takes
[33:58.840 --> 34:00.660]  a really, really, really long time.
[34:04.740 --> 34:06.540]  What we use is a heuristic
[34:06.540 --> 34:08.060]  sequence alignment algorithm.
[34:08.620 --> 34:11.440]  I'm basically sacrificing accuracy for time.
[34:11.660 --> 34:12.600]  The objective is to align
[34:12.600 --> 34:14.580]  every sequence to each other in a reasonable
[34:14.580 --> 34:16.640]  amount of time, but the results are never, ever going to be
[34:16.640 --> 34:17.380]  perfect.
[34:19.440 --> 34:20.760]  The way that this is done
[34:20.760 --> 34:22.760]  is by building these polygenetic trees.
[34:23.440 --> 34:24.820]  Polygenetic trees are basically
[34:25.660 --> 34:26.620]  what you guys would think
[34:26.620 --> 34:28.360]  of a tree of life. You start with
[34:29.040 --> 34:30.680]  common ancestors and you kind of move
[34:30.680 --> 34:32.660]  down and you can start understanding the
[34:32.660 --> 34:34.640]  similarities between certain species and things
[34:34.640 --> 34:36.400]  like that. It's the same thing with packets.
[34:36.880 --> 34:38.340]  We know that in SMB
[34:38.340 --> 34:40.600]  all the SMB authentication packets are going to be
[34:40.600 --> 34:42.880]  more similar than a data transfer packet
[34:42.880 --> 34:43.760]  and things like that.
[34:44.060 --> 34:45.820]  Typically, these are just binary trees
[34:46.540 --> 34:48.960]  which makes it quite simple, actually.
[34:50.140 --> 34:52.600]  It does have an interesting parallel in protocol
[34:52.600 --> 34:54.640]  analysis because protocols mimic
[34:54.640 --> 34:56.560]  evolution by changing their fields.
[34:56.960 --> 34:58.600]  The kind of goofy thing
[34:58.600 --> 34:59.920]  that I have here is what came first,
[34:59.920 --> 35:02.440]  git slash index.html or git slash?
[35:02.440 --> 35:04.360]  Obviously, git slash is going to be the
[35:04.360 --> 35:05.920]  common ancestor.
[35:09.050 --> 35:10.050]  Here's my little
[35:10.050 --> 35:12.810]  rip-off of a tree of life of lizards.
[35:12.910 --> 35:13.790]  As you can see,
[35:13.790 --> 35:15.710]  on the right-hand side,
[35:15.710 --> 35:17.970]  these guys look a lot more similar
[35:17.970 --> 35:19.930]  in structure than to this
[35:19.930 --> 35:22.010]  C. tigris guy over here with the
[35:22.010 --> 35:23.990]  long tail. So, basically, similar
[35:23.990 --> 35:26.070]  situation, apply it to packets.
[35:38.290 --> 35:40.010]  So, to create
[35:40.010 --> 35:42.230]  polygenetic trees, there's an algorithm called Upcoma
[35:42.230 --> 35:44.330]  which is the unweighted paired group method using
[35:44.330 --> 35:46.530]  arithmetic averages. It's pretty simple,
[35:46.530 --> 35:48.290]  actually. This little
[35:48.290 --> 35:50.130]  equation right here just signifies
[35:50.130 --> 35:52.890]  how the distance between two clusters is taken.
[35:53.250 --> 35:54.050]  Basically,
[35:54.050 --> 35:55.750]  the dpq
[35:56.290 --> 35:58.170]  function is going to determine
[35:58.170 --> 35:59.990]  the distance between each
[36:00.650 --> 36:02.270]  sequence in cluster i and
[36:02.270 --> 36:04.170]  cluster j. And it's basically just
[36:04.170 --> 36:05.970]  taking the mean of that and returning that back as
[36:05.970 --> 36:07.470]  the distance of i and j.
[36:08.250 --> 36:10.370]  In this case, the dpq
[36:10.370 --> 36:12.490]  is going to be the Smith-Waterman score and the d
[36:12.910 --> 36:14.550]  ij is the distance between two clusters
[36:14.550 --> 36:16.270]  i and j. So, this is just
[36:16.270 --> 36:18.290]  the operation that's used each step of the
[36:18.290 --> 36:19.970]  way when building the tree.
[36:21.050 --> 36:22.330]  So, to build
[36:22.330 --> 36:24.110]  the tree, each sequence is put
[36:24.110 --> 36:26.250]  into its individual cluster cell, one packet
[36:26.250 --> 36:28.430]  per cluster, basically. Use the Upcoma
[36:28.430 --> 36:30.130]  algorithm to iterate through every single cluster
[36:30.130 --> 36:31.910]  doing comparisons between every single
[36:31.910 --> 36:34.150]  sequence. You take the two with
[36:34.150 --> 36:36.350]  the smallest distance between each other.
[36:36.370 --> 36:38.250]  You create a new cluster k by uniting
[36:38.250 --> 36:40.010]  those two sequences.
[36:40.810 --> 36:42.310]  You define a new node k with child
[36:42.310 --> 36:44.370]  nodes i and j to build the tree.
[36:44.370 --> 36:46.410]  You add the cluster k
[36:46.410 --> 36:47.790]  to the universal set and you remove
[36:48.290 --> 36:50.290]  the clusters i and j. So, basically
[36:50.290 --> 36:52.570]  at the very end, you should only have one cluster.
[36:53.370 --> 36:54.390]  And you should have a tree build
[36:54.390 --> 36:55.350]  at that point.
[36:56.610 --> 36:58.410]  Here is a phylogenetic tree
[36:58.410 --> 37:00.310]  of the SMB protocol. This is just
[37:00.310 --> 37:02.830]  doing null sessions and stuff like that.
[37:02.850 --> 37:04.450]  As you can see, there's
[37:04.450 --> 37:06.490]  actually a pretty large disparity between
[37:06.490 --> 37:08.090]  the differences between
[37:08.550 --> 37:10.130]  different types of packets.
[37:10.630 --> 37:12.350]  The edge length signifies
[37:12.910 --> 37:13.990]  the distance.
[37:14.630 --> 37:16.570]  So, it's kind of
[37:16.570 --> 37:17.750]  more than a pretty picture.
[37:18.590 --> 37:19.690]  I'm sorry I can't actually
[37:19.690 --> 37:22.370]  I don't have any cool interface where I can zoom in and tell you
[37:22.370 --> 37:24.430]  exactly what those packets were and stuff like that at this current
[37:24.430 --> 37:26.610]  time, but from the analysis that I did
[37:26.610 --> 37:28.310]  each one of these clusters up here
[37:28.930 --> 37:30.270]  represented one of the SMB
[37:30.890 --> 37:32.490]  message types in the protocol.
[37:32.530 --> 37:34.350]  So, this is actually going to help us
[37:35.390 --> 37:36.510]  say we want to analyze
[37:36.510 --> 37:38.130]  the SMB authentication
[37:38.570 --> 37:40.190]  packet. Okay, it's
[37:40.190 --> 37:42.290]  this cluster over here, for instance.
[37:42.290 --> 37:44.170]  So, we start at this root node, and then we're going to
[37:44.170 --> 37:46.810]  start doing our progressive alignment over here.
[37:46.950 --> 37:48.270]  So,
[37:50.690 --> 37:52.650]  the tree is your guide. Basically,
[37:52.650 --> 37:54.610]  what this tree is going to be used for is to align
[37:54.610 --> 37:56.470]  the sequences to each other.
[37:57.250 --> 37:58.550]  As I was talking about the heuristic
[37:58.550 --> 38:00.730]  alignment earlier,
[38:00.730 --> 38:02.650]  what we're basically going to have to do is what's
[38:02.650 --> 38:04.710]  called progressive sequence alignment, and what that means
[38:04.710 --> 38:06.550]  is we're going to align two sequences to
[38:06.550 --> 38:08.530]  each other, and then
[38:08.530 --> 38:09.750]  we're going to
[38:10.750 --> 38:11.990]  pick one of the
[38:11.990 --> 38:13.770]  alignments and use that as a representative
[38:13.770 --> 38:16.010]  sequence for those two sequences.
[38:16.350 --> 38:17.910]  Then we're going to align another sequence
[38:17.910 --> 38:19.930]  to that representative sequence. And as
[38:19.930 --> 38:21.750]  gaps are inserted, they are
[38:22.690 --> 38:23.930]  moved down towards
[38:23.930 --> 38:25.990]  the root, excuse me,
[38:25.990 --> 38:27.810]  down towards the leaf nodes
[38:27.810 --> 38:29.630]  on the graph. So,
[38:29.630 --> 38:31.130]  the problem with this is
[38:33.890 --> 38:35.970]  if gaps are inserted into the tree
[38:35.970 --> 38:37.910]  in errant places, that will be propagated
[38:37.910 --> 38:40.050]  all the way down to the leaf nodes, which can result
[38:40.050 --> 38:41.310]  in insignificant alignment.
[38:42.130 --> 38:43.830]  It probably should be a more
[38:44.490 --> 38:45.250]  tree building
[38:45.770 --> 38:47.310]  should probably be a bit more
[38:47.770 --> 38:49.370]  of a manual process where
[38:50.010 --> 38:52.070]  while you're doing the analysis, you kind of look at it
[38:52.070 --> 38:53.810]  and you say, this does look acceptable
[38:53.810 --> 38:55.910]  to me, I'm going to accept this alignment to be
[38:55.910 --> 38:57.910]  the representative sequence, so
[38:57.910 --> 38:59.950]  gaps aren't inserted into errant places
[38:59.950 --> 39:00.850]  basically.
[39:02.590 --> 39:04.130]  Opposed to the exponential hypercube
[39:04.130 --> 39:05.650]  traversal, Upcoma performs
[39:05.650 --> 39:07.610]  in comparisons where n is equal to
[39:07.610 --> 39:09.370]  the depth of the tree minus the root.
[39:09.850 --> 39:11.590]  That's very feasible for us.
[39:11.590 --> 39:13.550]  We can actually align sequences in our lifetime
[39:13.550 --> 39:15.050]  which is very helpful, I think.
[39:16.470 --> 39:17.790]  So, multiple sequence
[39:17.790 --> 39:19.490]  alignment. Basically, the rule
[39:19.490 --> 39:21.530]  as I was explaining earlier about progressive alignment
[39:21.530 --> 39:23.330]  is once a gap, always a gap.
[39:24.230 --> 39:25.810]  Basically, what you're going to do is
[39:25.810 --> 39:27.570]  you're going to align two sequences
[39:27.570 --> 39:29.510]  to each other, place a representative
[39:29.510 --> 39:31.410]  sequence in the root node of that
[39:31.410 --> 39:32.270]  and
[39:32.270 --> 39:32.390]  and
[39:34.290 --> 39:36.130]  as you align sequences
[39:36.130 --> 39:38.130]  to those representative sequences, those
[39:38.130 --> 39:40.330]  gaps are going to translate themselves
[39:40.330 --> 39:41.830]  all the way down to the leaf node.
[39:42.430 --> 39:44.150]  Basically, the rule for
[39:44.150 --> 39:46.410]  doing the tree traversal, you start in the root
[39:46.410 --> 39:47.910]  and if the root is null
[39:47.910 --> 39:50.150]  you start going left and then you go right.
[39:50.610 --> 39:52.310]  If the left is not null and the right is not null
[39:52.310 --> 39:54.310]  which signifies that there are sequences on those
[39:54.310 --> 39:56.050]  two leaf nodes, you align those two sequences
[39:56.530 --> 39:58.250]  you choose a sequence with the least
[39:58.250 --> 40:00.050]  number of gaps inserted and that's kind of just
[40:01.090 --> 40:02.230]  I got the best results
[40:02.230 --> 40:04.050]  out of that. I don't really know if that's kosher
[40:04.050 --> 40:06.010]  in the bioinformatics world or anything like that, but
[40:06.010 --> 40:08.050]  from my experience, that resulted
[40:08.050 --> 40:09.690]  in decent alignment.
[40:10.750 --> 40:11.970]  In this case
[40:11.970 --> 40:13.770]  we aligned sequence one to sequence two
[40:13.770 --> 40:15.850]  sequence one is chosen to be the representative
[40:15.850 --> 40:18.010]  because there were not as many gaps inserted
[40:18.010 --> 40:19.470]  so it kind of lowers the margin of error
[40:19.470 --> 40:21.490]  of error and gaps propagating all the way down
[40:21.490 --> 40:24.050]  through all the alignment. So, what we're going to do is
[40:24.050 --> 40:26.070]  we're going to place sequence
[40:26.070 --> 40:28.310]  one in the root node
[40:28.310 --> 40:29.730]  of these two leaf nodes
[40:29.730 --> 40:31.570]  and we're going to keep track of the edits
[40:31.570 --> 40:34.470]  in the edge. So, the edits in this case would be
[40:35.410 --> 40:36.410]  I don't have
[40:36.410 --> 40:38.610]  the list of the offsets right in front of my face
[40:38.610 --> 40:38.850]  but
[40:40.070 --> 40:42.330]  there's going to be edits that are inserted into sequence two
[40:42.330 --> 40:44.410]  to insert those gaps.
[40:53.700 --> 40:54.620]  Pretty tree,
[40:54.620 --> 40:55.380]  not really.
[40:55.820 --> 40:57.560]  So, you start in the
[40:58.480 --> 41:00.200]  root node, the parent node right up here
[41:01.320 --> 41:02.300]  like I was saying earlier
[41:02.300 --> 41:04.160]  if the root is null, you go left then right
[41:04.160 --> 41:06.420]  the root is null in this case, there's no value
[41:06.420 --> 41:08.380]  being stored there, so we're going to go left.
[41:09.000 --> 41:10.400]  Same thing here, we're going to go
[41:11.280 --> 41:12.320]  our child nodes
[41:12.320 --> 41:14.100]  are not null, so what we're going to do is we're going to
[41:14.100 --> 41:16.300]  align sequence one and we're going to align sequence two.
[41:18.020 --> 41:19.860]  We're going to choose a representative sequence
[41:19.860 --> 41:22.180]  which is going to be one, we call it one prime at this point
[41:22.180 --> 41:24.360]  we keep track of the edits in the edge.
[41:24.720 --> 41:26.360]  So, the edits
[41:27.420 --> 41:28.320]  between sequence one
[41:28.320 --> 41:29.980]  and two are stored in the left
[41:29.980 --> 41:32.280]  edge and the edits for sequence
[41:32.280 --> 41:34.060]  two are stored in the right edge.
[41:35.360 --> 41:36.420]  We just traverse our way
[41:36.420 --> 41:37.220]  back up to the root
[41:38.460 --> 41:39.660]  start moving right now
[41:41.360 --> 41:42.240]  we align
[41:42.240 --> 41:44.640]  the representative sequence which is one prime
[41:44.640 --> 41:46.380]  with three, store those
[41:46.380 --> 41:48.340]  edits in the edge, and now what we need to do
[41:48.340 --> 41:49.520]  is we actually need to
[41:50.100 --> 41:52.400]  propagate those gaps that are inserted via
[41:52.400 --> 41:54.440]  the edits all the way down
[41:54.440 --> 41:55.860]  to the leaf node.
[41:57.220 --> 41:58.420]  If we want to
[41:58.420 --> 42:00.500]  align all the sequences to each other, we basically
[42:01.240 --> 42:02.820]  add up all the edits
[42:02.820 --> 42:04.240]  so sequence one aligned
[42:04.240 --> 42:05.860]  which is over here, we're going to
[42:06.400 --> 42:08.220]  add the edits of one prime three
[42:08.220 --> 42:10.140]  to one two
[42:10.140 --> 42:12.420]  to add the edits
[42:12.420 --> 42:14.480]  the edits in this case are going to be the gaps
[42:14.480 --> 42:15.900]  by the way. If we're going to
[42:17.140 --> 42:17.660]  propagate
[42:18.320 --> 42:20.640]  those gaps down the tree to sequence
[42:20.640 --> 42:22.500]  two, we're going to take one prime three
[42:22.500 --> 42:23.760]  add it to
[42:24.480 --> 42:26.520]  the edits of two one
[42:26.520 --> 42:27.560]  and lastly
[42:28.780 --> 42:29.820]  for sequence
[42:29.820 --> 42:31.500]  three, all we need to do is add the edits of
[42:31.500 --> 42:33.820]  three and the edits of sequence
[42:33.820 --> 42:35.860]  three and one prime in this case.
[42:37.420 --> 42:37.940]  As
[42:37.940 --> 42:38.840]  explained.
[42:40.220 --> 42:41.840]  So, another
[42:41.840 --> 42:43.740]  kind of hokey example of three
[42:43.740 --> 42:45.100]  sequences being aligned this time
[42:46.700 --> 42:47.180]  a bit more
[42:48.600 --> 42:49.120]  verbose
[42:49.120 --> 42:51.140]  usage of HTTP I guess
[42:52.220 --> 42:53.760]  so basically in
[42:53.760 --> 42:55.860]  this case right down here, this is what's
[42:55.860 --> 42:57.140]  called our consensus sequence
[42:57.880 --> 43:00.000]  what we basically do is we start in
[43:00.000 --> 43:01.600]  offset zero and we go down and we say
[43:01.600 --> 43:04.200]  these are all a bunch of G's so we're going to put a G down here
[43:04.200 --> 43:04.860]  etc etc
[43:05.680 --> 43:07.840]  once we start getting over here we start noticing that
[43:07.840 --> 43:09.540]  there's gaps inserted so
[43:09.540 --> 43:11.800]  that might possibly mean that
[43:11.800 --> 43:13.980]  that is a variable link field so in this case
[43:13.980 --> 43:15.780]  I'm just representing that by the question
[43:15.780 --> 43:17.600]  mark down there and
[43:17.600 --> 43:19.520]  all is the same
[43:19.520 --> 43:21.880]  you have a space here, this all
[43:21.880 --> 43:24.000]  matches up just fine, followed by host
[43:24.000 --> 43:25.820]  followed by more unknowns
[43:25.820 --> 43:27.400]  dot three
[43:27.860 --> 43:29.680]  three spaces for .com, .net
[43:29.680 --> 43:31.940]  etc, followed by the
[43:31.940 --> 43:33.120]  user agent block
[43:33.940 --> 43:35.800]  followed by the browser type
[43:35.800 --> 43:37.840]  followed by accept text X amount
[43:37.840 --> 43:39.880]  so, when we're
[43:39.880 --> 43:42.040]  analyzing this consensus sequence, basically what we can
[43:42.040 --> 43:43.880]  say is okay, here's the structure
[43:43.880 --> 43:45.480]  of this particular format
[43:45.960 --> 43:47.960]  we have a get space slash, followed by a variable
[43:47.960 --> 43:50.460]  link string, followed by HTTP 1.0
[43:50.460 --> 43:52.000]  I'm not counting new lines or
[43:52.000 --> 43:53.880]  anything like that at this time, followed by
[43:53.880 --> 43:55.840]  host, followed by another variable link
[43:55.840 --> 43:57.980]  sequence, followed by a dot, followed by another
[43:57.980 --> 43:59.920]  variable link sequence, followed by user agent
[43:59.920 --> 44:01.720]  variable link sequence, accept
[44:01.720 --> 44:03.340]  text X amount. So
[44:03.880 --> 44:05.960]  what we could do at this
[44:05.960 --> 44:07.340]  point is feed this little
[44:08.600 --> 44:09.900]  structure into our fuzzer and
[44:09.900 --> 44:11.780]  just let it start going
[44:11.780 --> 44:13.580]  this is a completely automated process
[44:13.580 --> 44:15.900]  I didn't really have to do anything in this case
[44:16.700 --> 44:17.840]  unfortunately I don't have
[44:17.840 --> 44:19.820]  any good mixed protocol where it's
[44:19.820 --> 44:21.580]  half binary, half plain text
[44:22.720 --> 44:24.100]  for me to show you right now
[44:24.100 --> 44:24.720]  but
[44:25.680 --> 44:27.780]  I'll put up some examples on the website and kind of like
[44:27.780 --> 44:29.640]  walk you through using the tool and stuff like that
[44:29.640 --> 44:31.340]  that might be actually useful
[44:33.360 --> 44:34.120]  one thing
[44:34.120 --> 44:35.900]  that I want to say about this though is
[44:36.620 --> 44:37.480]  if you'll notice
[44:38.260 --> 44:39.840]  with these consensus sequences, I'm just
[44:39.840 --> 44:41.840]  assuming that this is
[44:41.840 --> 44:43.160]  going to be variable length and
[44:43.670 --> 44:45.500]  this is not going to mean anything. So basically
[44:45.500 --> 44:47.420]  what's happening here is I'm losing information
[44:47.420 --> 44:49.580]  there's a C here and two gaps
[44:49.580 --> 44:51.520]  there's got to be a better way to
[44:51.520 --> 44:53.160]  represent these consensus sequences
[44:53.160 --> 44:55.540]  there's something called sequence logos
[44:55.540 --> 44:57.300]  and basically what it is
[44:57.300 --> 44:59.020]  it's kind of just like a stacked histogram
[44:59.020 --> 45:01.080]  of each offset
[45:01.080 --> 45:03.600]  so let me find a good example
[45:03.600 --> 45:05.700]  so right here after the host
[45:05.700 --> 45:07.800]  you have two W's followed by a
[45:07.800 --> 45:09.780]  gap. Basically when you stack that
[45:09.780 --> 45:11.620]  histogram up, usually
[45:11.720 --> 45:14.720]  it's a W but sometimes it
[45:14.720 --> 45:15.440]  contains a gap and things like that
[45:15.440 --> 45:17.340]  so in that case
[45:17.340 --> 45:19.480]  you don't really lose information and you're actually
[45:19.480 --> 45:21.600]  able to use a little more of your human intuition
[45:21.600 --> 45:22.780]  to be able to understand
[45:23.440 --> 45:25.140]  the alignment a bit better than just
[45:26.520 --> 45:27.320]  ruling it out
[45:27.320 --> 45:29.340]  just because there are gaps or because there are mismatches
[45:29.340 --> 45:30.040]  and things like that
[45:30.040 --> 45:36.620]  so basically
[45:36.620 --> 45:38.960]  here's how we're going to analyze
[45:38.960 --> 45:40.880]  the consensus sequence in
[45:40.880 --> 45:42.700]  this case. We could do
[45:42.700 --> 45:44.940]  statistical analysis on each column
[45:44.940 --> 45:46.900]  by building histograms so we build
[45:46.900 --> 45:47.900]  our consensus sequence
[45:48.380 --> 45:49.880]  like I showed you on the previous page
[45:49.880 --> 45:51.980]  and we look at the mutation rates
[45:51.980 --> 45:54.300]  and the offset comparison between
[45:54.700 --> 45:56.600]  each offset. So basically
[45:56.600 --> 45:57.460]  what we can do is
[45:58.180 --> 45:59.100]  we can say
[46:00.640 --> 46:02.900]  this has a
[46:04.180 --> 46:04.960]  mutation rate of
[46:05.440 --> 46:06.940]  let me try to find a good example
[46:19.020 --> 46:20.160]  what we can do is
[46:20.160 --> 46:22.380]  if you look at this block right here of all these question marks
[46:23.700 --> 46:25.480]  almost every single one of these
[46:25.480 --> 46:26.820]  has a similar mutation rate
[46:26.820 --> 46:29.140]  they have a rate of change that is pretty
[46:29.140 --> 46:31.080]  constant. So if we
[46:31.080 --> 46:33.220]  wanted to analyze this like a binary protocol
[46:33.220 --> 46:35.180]  it's a lot more difficult to
[46:35.180 --> 46:36.840]  look at just on the screen
[46:36.840 --> 46:38.580]  we pretty much base our
[46:39.140 --> 46:41.020]  understanding where the fields begin
[46:41.020 --> 46:43.060]  and fields end based on the mutation rate
[46:43.060 --> 46:45.240]  so for instance
[46:45.820 --> 46:47.080]  what we can do is
[46:47.080 --> 46:49.360]  look at the rates of mutation
[46:49.360 --> 46:50.880]  for each offset and
[46:50.880 --> 46:52.980]  using that we can kind of understand
[46:52.980 --> 46:54.900]  what the particular field might be
[46:54.900 --> 46:55.900]  used for.
[46:56.820 --> 46:58.840]  One thing I wanted to mention though is beware
[46:58.840 --> 47:00.900]  of junk data. In the last example if there were any
[47:00.900 --> 47:02.680]  posts in there it would
[47:02.680 --> 47:04.280]  result in kind of a bad alignment
[47:04.880 --> 47:06.760]  and it would actually be a little
[47:06.760 --> 47:08.580]  more difficult to understand
[47:08.580 --> 47:10.240]  what the general structure was.
[47:10.980 --> 47:12.300]  What I was talking about earlier
[47:12.300 --> 47:14.800]  with the clustering algorithms, if you cluster
[47:14.800 --> 47:16.780]  things correctly and you choose
[47:18.040 --> 47:19.440]  the root nodes
[47:19.440 --> 47:20.300]  in each cluster
[47:23.020 --> 47:25.700]  you'll be able to get decent alignments
[47:25.700 --> 47:27.080]  out of it instead of trying to align
[47:27.080 --> 47:29.320]  really distant sequences where lots of gaps
[47:29.320 --> 47:30.500]  are going to be inserted.
[47:33.520 --> 47:34.680]  Classification is your friend
[47:35.160 --> 47:37.300]  the better that you cluster
[47:37.300 --> 47:39.420]  the packets, the better your sequence
[47:39.420 --> 47:40.980]  alignment is going to end up being.
[47:44.320 --> 47:45.680]  This was kind of an experimental
[47:45.680 --> 47:47.140]  phase about a year ago
[47:47.140 --> 47:48.920]  when I was working on this but I kind of
[47:48.920 --> 47:51.120]  already implemented this in code so it's really not that experimental
[47:51.120 --> 47:53.820]  anymore. I just haven't really had a chance to work on the slides.
[47:54.760 --> 47:55.420]  At first
[47:55.420 --> 47:57.140]  what I was basically doing was I was
[47:57.140 --> 47:59.120]  separating the dynamic data, data that
[47:59.120 --> 48:01.200]  was changing versus the static data. So in the case
[48:01.200 --> 48:03.200]  of HTTP I was able to understand
[48:03.200 --> 48:04.800]  just the different blocks and stuff like that
[48:04.800 --> 48:06.740]  and understanding the variable length fields
[48:06.740 --> 48:09.300]  just because it was dynamic data it was changing.
[48:09.980 --> 48:11.040]  To understand integer
[48:11.040 --> 48:13.800]  fields this actually worked out pretty good.
[48:14.200 --> 48:14.840]  You can build
[48:14.840 --> 48:16.600]  just like an engram frequency table
[48:16.600 --> 48:18.300]  for 1, 2, and 4 byte window sizes
[48:18.820 --> 48:20.220]  and you just kind of slide yourself
[48:20.720 --> 48:22.880]  over the consensus sequence at that point
[48:23.740 --> 48:25.000]  and you can use
[48:25.000 --> 48:26.740]  some logic in your program to
[48:26.740 --> 48:28.620]  try to discern what
[48:29.120 --> 48:30.760]  the particular function is of that
[48:30.760 --> 48:32.160]  field. So for example
[48:32.160 --> 48:34.940]  if two consecutive bytes that are integers
[48:35.440 --> 48:36.620]  mutate at the same rate
[48:36.620 --> 48:38.660]  the chances are that they are part of the same field and maybe
[48:38.660 --> 48:40.740]  they are checksum or something like that. They are changing every
[48:40.740 --> 48:41.760]  single packet.
[48:42.300 --> 48:43.460]  The second example
[48:43.460 --> 48:45.780]  if in two consecutive bytes the least significant
[48:45.780 --> 48:47.860]  byte increments faster than the greater significant
[48:47.860 --> 48:49.820]  byte it might be a 16-bit sequence identifier
[48:49.820 --> 48:51.480]  field or something of that sort.
[49:02.100 --> 49:02.220]  So
[49:04.600 --> 49:07.540]  this is all also implemented stuff fortunately.
[49:07.980 --> 49:08.860]  But what I was going
[49:08.860 --> 49:10.800]  to basically do is build a protocol profile based on
[49:10.800 --> 49:12.900]  each consensus and allowing each sequence individually
[49:12.900 --> 49:14.800]  to break down the structure. So
[49:14.800 --> 49:16.240]  for example I would
[49:17.320 --> 49:18.360]  take a
[49:18.360 --> 49:19.660]  SMB login
[49:20.240 --> 49:22.400]  authentication packet consensus sequence
[49:22.400 --> 49:24.500]  I would take a SMB data transfer
[49:24.500 --> 49:26.520]  packet and then I would align
[49:26.520 --> 49:28.500]  those two consensus sequences
[49:28.500 --> 49:30.500]  to understand the general structure
[49:30.500 --> 49:32.280]  of the packet
[49:32.280 --> 49:34.460]  format in general. They are still going to be pretty
[49:34.460 --> 49:36.460]  deviant but you will be able to understand
[49:36.460 --> 49:38.580]  the specific blocks in between.
[49:38.580 --> 49:40.180]  Like on block based protocols like ISACAMP
[49:40.180 --> 49:41.460]  and SMB and things like that
[49:42.280 --> 49:43.920]  that is actually going to be quite helpful
[49:43.920 --> 49:45.680]  I would think.
[49:46.300 --> 49:47.980]  The biggest challenge for me this far
[49:47.980 --> 49:49.500]  is being able to present the data
[49:49.500 --> 49:51.860]  in a readable format where the user can actually
[49:52.520 --> 49:54.060]  understand the results.
[49:54.620 --> 49:54.900]  So
[49:55.660 --> 49:57.260]  I have all this stuff kind of implemented
[49:57.880 --> 49:59.580]  like on a command line tool
[49:59.580 --> 50:01.640]  which kind of made it difficult so I'm just kind of using
[50:01.640 --> 50:03.720]  ANSI color and stuff like that to
[50:03.720 --> 50:05.660]  kind of print all this stuff out.
[50:06.900 --> 50:07.840]  And the last
[50:07.840 --> 50:09.700]  thing I wanted to say about this particular tool
[50:09.700 --> 50:11.740]  is it will never be fully automated
[50:11.740 --> 50:13.280]  if accuracy is in mind but
[50:13.280 --> 50:14.940]  if you are doing protocol fuzzing
[50:14.940 --> 50:16.600]  you don't really have to be accurate necessarily
[50:16.600 --> 50:17.960]  so it's kind of okay to have
[50:18.960 --> 50:20.620]  it's kind of okay I guess to have
[50:21.860 --> 50:23.280]  that kind of entropy
[50:23.280 --> 50:25.760]  in each sequence.
[50:28.960 --> 50:30.320]  Let me get this.
[50:36.920 --> 50:37.720]  Sorry.
[50:37.960 --> 50:39.940]  So basically what this can be used for is
[50:39.940 --> 50:42.300]  understanding unknown protocols, some kind of
[50:42.300 --> 50:42.460]  like
[50:43.760 --> 50:45.880]  worm for all we know communicates with
[50:45.880 --> 50:48.020]  its brothers and sisters all over the internet
[50:48.020 --> 50:50.800]  using some binary format that we've never seen before.
[50:51.100 --> 50:52.100]  This also allows us
[50:52.100 --> 50:54.040]  to fuzz network protocols more efficiently because
[50:54.040 --> 50:56.700]  we don't necessarily have to write protocol specs for them.
[50:57.000 --> 50:57.960]  If it's a common
[50:57.960 --> 51:00.140]  protocol I'd probably say just go
[51:00.140 --> 51:02.220]  read the RFC or something like that and
[51:02.220 --> 51:03.680]  just look at the ethereal
[51:03.680 --> 51:06.340]  samples because there's so many of them.
[51:06.340 --> 51:08.060]  But if you're looking at some black box
[51:08.060 --> 51:09.940]  protocol you've never ever seen before in your life
[51:09.940 --> 51:12.180]  this is going to be a tool that would probably
[51:12.180 --> 51:13.520]  definitely be useful.
[51:16.520 --> 51:17.180]  Also,
[51:17.180 --> 51:17.660]  one thing
[51:17.660 --> 51:19.400]  I kind of forgot to mention but
[51:19.400 --> 51:21.580]  this can also be used for file formats.
[51:21.860 --> 51:23.500]  There's really no difference between
[51:23.640 --> 51:25.460]  a packet format and a file format so if you wanted
[51:25.460 --> 51:27.480]  to understand some proprietary file
[51:27.480 --> 51:30.020]  format, same situation.
[51:30.020 --> 51:31.560]  The only thing that you need to do is just have a lot
[51:31.560 --> 51:33.420]  of samples that are different.
[51:35.760 --> 51:37.540]  And also if any of you guys have any ideas
[51:37.540 --> 51:39.480]  about how this stuff can be used I'm interested in
[51:39.480 --> 51:40.220]  hearing it.
[51:41.440 --> 51:42.340]  My conclusion
[51:42.340 --> 51:44.320]  is this stuff will never be automated
[51:44.320 --> 51:46.080]  100% like I was describing
[51:46.080 --> 51:48.140]  the tree building earlier. It's good
[51:48.140 --> 51:49.720]  if you wanted to
[51:51.960 --> 51:52.780]  be involved
[51:52.780 --> 51:54.280]  in each step of the process so you
[51:54.280 --> 51:56.280]  know which representative sequence is used and which
[51:56.280 --> 51:58.380]  gaps are inserted because as gaps propagate
[51:58.380 --> 52:00.320]  down to the
[52:00.320 --> 52:02.180]  root nodes there can be errant gaps
[52:02.180 --> 52:04.100]  that make the alignment quite useless
[52:04.100 --> 52:05.340]  and things like that.
[52:06.520 --> 52:08.480]  Basically right now I have a Python
[52:08.480 --> 52:10.580]  proof of concept for this. I have some
[52:10.580 --> 52:12.320]  C++ code that I'm working on.
[52:12.500 --> 52:14.360]  It's actually going to be pretty good. I should have it
[52:14.360 --> 52:16.300]  probably finished in about a month or two.
[52:16.620 --> 52:18.740]  The Python code right now, I use Pyrex
[52:18.740 --> 52:20.240]  I don't know if you guys have ever heard that, to do
[52:20.240 --> 52:22.520]  all the hard, computationally
[52:22.520 --> 52:24.220]  expensive algorithms like the Neiman
[52:24.220 --> 52:26.480]  Woons matrix operations and stuff like that.
[52:27.120 --> 52:28.580]  I don't know if you guys have ever seen this
[52:28.580 --> 52:30.440]  tool. It's called Orange. It's pretty cool.
[52:30.780 --> 52:32.120]  It's basically like a widget based
[52:32.120 --> 52:34.400]  visual programming interface that kind of allows you
[52:34.400 --> 52:35.320]  to play with different
[52:36.300 --> 52:37.000]  data mining
[52:37.000 --> 52:39.760]  algorithms. So you can kind of link together everything.
[52:39.800 --> 52:41.380]  In this case, what you'd be able
[52:41.380 --> 52:42.260]  to do with
[52:43.540 --> 52:45.060]  protocol informatics is be able to say
[52:45.060 --> 52:47.680]  okay, I want to use this particular
[52:49.120 --> 52:49.560]  classification
[52:49.560 --> 52:51.160]  algorithm for clustering. I want to use
[52:51.160 --> 52:53.740]  this particular sequence alignment algorithm.
[52:53.740 --> 52:55.740]  I want to use this particular tree building algorithm.
[52:55.740 --> 52:56.440]  Because there's actually
[52:57.220 --> 52:59.240]  four different types of tree building algorithms.
[52:59.240 --> 53:01.100]  There's the upcomma, there's neighbor joining, there's
[53:01.100 --> 53:03.320]  multiple parsimony, things like that.
[53:03.320 --> 53:04.760]  There's a multitude of
[53:05.220 --> 53:07.280]  opportunity to implement all sorts of
[53:07.280 --> 53:09.360]  things and kind of just figure out what works.
[53:09.600 --> 53:11.400]  I guess the whole moral
[53:11.400 --> 53:13.180]  of the story with what I'm trying to say
[53:13.180 --> 53:13.560]  is
[53:15.080 --> 53:17.340]  I know it's kind of difficult for people
[53:17.340 --> 53:19.340]  in this industry to kind of look outside
[53:19.340 --> 53:21.280]  their science that they're working on
[53:21.280 --> 53:23.380]  and kind of understand that people might
[53:23.380 --> 53:25.060]  have already kind of solved everything
[53:25.060 --> 53:27.320]  back in the day. So this is just kind of a good
[53:27.320 --> 53:29.280]  example. This stuff was figured out in the
[53:29.280 --> 53:31.340]  70s and it's 2005
[53:31.340 --> 53:33.460]  now and we found a use for it.
[53:36.460 --> 53:37.380]  I'm taking questions
[53:37.380 --> 53:39.460]  now. Feel free to walk
[53:39.460 --> 53:41.400]  up to get a microphone up here or something
[53:41.400 --> 53:42.280]  like that.
[53:43.260 --> 53:44.400]  Thanks for coming.
[53:53.700 --> 53:54.500]  Questions?
[53:57.540 --> 53:58.640]  I can't hear you.
[53:59.000 --> 54:00.860]  Do you want to come up
[54:00.860 --> 54:02.520]  here and try to use a mic?
[54:19.470 --> 54:20.390]  I don't know.
[54:22.330 --> 54:23.350]  Here you go.
[54:26.180 --> 54:26.760]  Yeah,
[54:26.760 --> 54:28.660]  I'm working on almost exactly the same thing
[54:28.660 --> 54:30.660]  with mutating web things, but I
[54:30.660 --> 54:32.320]  just walked in on the end of your lecture and
[54:32.320 --> 54:34.600]  I was talking to this guy who's also
[54:34.600 --> 54:36.740]  doing tree algorithms, but he's doing
[54:36.740 --> 54:37.940]  it with granularity
[54:38.460 --> 54:41.000]  based on the levels of complexity
[54:41.000 --> 54:42.320]  of the search.
[54:42.780 --> 54:44.900]  Have you looked at any of that stuff
[54:44.900 --> 54:46.680]  for your sorting and tree
[54:46.680 --> 54:47.640]  methods?
[54:49.000 --> 54:50.300]  Yeah, that's basically a maximum
[54:50.300 --> 54:52.020]  parsimony tree building. That's where
[54:52.660 --> 54:53.220]  every
[54:54.020 --> 54:56.240]  step of the tree, you're going to look at
[54:57.100 --> 54:58.040]  the complexity
[54:58.040 --> 55:00.260]  of what it would take for these sequences to mutate
[55:00.260 --> 55:02.800]  to reach this particular result.
[55:02.800 --> 55:03.920]  And usually,
[55:03.920 --> 55:06.080]  evolution chooses the path of
[55:06.080 --> 55:07.980]  least resistance. So, in maximum
[55:07.980 --> 55:09.760]  parsimony trees, you have
[55:09.760 --> 55:12.020]  two different choices. You're going to choose the choice that's the most
[55:12.020 --> 55:12.860]  simple.
[55:15.900 --> 55:17.200]  Anyone else?
[55:22.400 --> 55:24.440]  Okay. Well,
[55:24.440 --> 55:26.500]  this was a lot of information. I'm sorry if I
[55:26.500 --> 55:28.320]  didn't have any other ways to represent it
[55:28.320 --> 55:30.300]  in a kind of clear and concise
[55:30.300 --> 55:31.240]  manner, but
[55:32.340 --> 55:34.460]  this is the website for this project
[55:34.460 --> 55:36.480]  and I encourage you all to
[55:36.480 --> 55:38.040]  visit the site and download the tool and
[55:38.040 --> 55:40.560]  just give me feedback if you got it.
[55:40.560 --> 55:41.520]  So, thanks.
[55:46.250 --> 55:47.570]  Just want to make an announcement
[55:47.570 --> 55:49.150]  that Meet the Fed will be at...