and so this is gpu-accelerated security
so first off standards go mine hey I'm
Andrew
that's my website you're interested to
have some notable projects and a before
so before we begin felt it's worth
getting up a disclaimer my knowledge is
absolutely not absolute and they're very
likely things I've missed and my
research primarily focused on intrusion
detection systems or its focusing on
intrusion detection systems I've just
recognized similarities and other areas
that could be applied to and there's a
lot of things that I would like to
explore by simply do not have time for
and it's 53 days left
sorry to all the fourth-year syndrome
and and if I'm to explain doubt in
perlier general questions please just
weave in to the end cuz I've got way too
many slights to cover for the time flaw
and another thing is it took me hours to
fully comprehend some of the topics I'm
going to go through so I'm gonna try and
explain them the best I can but don't
want it if at the end you're included
confused so the other thing is I can
remember being a first-tier and
completely glazing over some talks
because there was just key terms or
acronyms not used and or that I didn't
know so uh there are some of the things
I might say feathers talk and if you
don't know what they are have a quick
look and most certainly is the head fat
algorithm and I'm gonna say Colonel I
don't mean Linux kernel I mean a
function execute on GPU so I want to
start this off with a preface lots of
applications try and implement a GPU
support or there's initially a we will
do GPU as you can see the special in
case of Surakarta
is that things won't always go to plan
and there's often at least from the open
source projects I've been able to come
across they've been issue with regards
to continuing support for GPU I'm on a
night with open source a lot of things
just here's a paper on this awesome
concept and pay well and are the core
there's no source code or anything even
terrific
that provided to back up the claims are
making so however before we continue
their notes GPUs aren't necessarily a
complete replacement for all of these
tasks a lot of things you're better off
having balance at blend of CPU and GPU
and and for my particular examples and
intrusion detection system does a lot
more than just signature matching that's
just the area focuses on because of that
time on the base of it so first off my
methodology in the direction started off
with when should I actually be using the
GPU and effectively you need to do a
computation on a huge number of items
computation doesn't rely on the
computation of other items so it's
fairly independent and is fairly simple
put a star in there and basically as
long as you've not got too many
branching operations we find difficult
lots of branching operations the
processing of a GPUs the cores are
fairly stupid and so not as fast as see
if you definitely I'm going to skip this
bottom half because it's basically the
inverse of the top part but quite a lot
to get through and so to summarize what
the GPU before performing simple
operations on a huge volume of data and
what's Picabia does in the GPU the data
must be copied to the GPU and we want to
get your results back off the GPU age
pocket or back half again and that
introducing overhead so my methodology
for how to go about approaching this to
speed things up was to maximize minimize
and then just generally optimize and
again now I apply these principles
somewhat to them like file carving and
intrusion detection systems so first off
a maximizing so when you copy data to
the GPU there is there's overhead and as
if you were compared to if you were just
to execute that same function on CPU so
the more the more often you have to copy
data the more often you're going to
encounter that overhead stuff and that
by maximizing the
you copy at once you minimize the number
of copies that you have to make so you
encountered that overhead laughs and so
my solution to this was buffer copies
and effectively as long as you don't
need as long as the day isn't
time-sensitive and basically hold the
back of it and then try and send over as
much at once and with time sensitive
data and you would just have a timeout
and but you would actually have that
with all data because you wouldn't just
be like I'm gonna wait until I get
another packet so I can finish off this
buffer and you could just be waiting
indefinitely that depends and so have I
implemented this I have a mock-up
intrusion detection system nowhere near
advanced as like snort or sir cat or
anything you get it's more just to prove
the things I've 130 so I basically every
time I capture packets I'm loading them
into a buffer and I'm copying that
buffer over and once it reaches a
sufficient size or a certain time I feed
it and reach so second part this sort to
parts list they're kind of similar I am
this is minimizing so similarly as to
maximizing when the copies introduce
overhead the more data that needs to be
copied the longer it takes or I should
be maybe save more bytes it takes to
represent that data the longer it takes
I'm so if you can represent the same
information in less bytes it's usually
going to be faster um so my solution for
that one was what I've called bit
indexing there's probably another term
for it it's a simple enough idea there's
probably been done before I just could
not find anything on it so I've just
come to that and the other one is
basically minimizing the members and so
if you're cut copying over objects and
you've got lots of unnecessary members
you're you're just wasting time and if
you don't use those except for debugging
do not put them in the final person okay
so these are some more like just general
summary of optimizations so
there's texture memory shared memory and
global memory they were on that first
flight of your some terms might cover it
in case you didn't catch that the extra
memory is effectively a cache for
texture data and 64 kilobytes it's
fairly small if you can fit your data in
that you've got complete control over
that cache I'm I'm sorry that can lead
to some massive performance improvements
in your application especially in the
area of string searching where you might
have thousands of patterns to search
there and shared memory is kind of
similar except it is the level 1 cache
off the GPU and effectively you fence
off a section of it you say hey that 32
kilobytes that's mine you don't care to
take that I get stick tailor and then
this global which is just like the GPU
equivalent of RAM and still fairly fast
but not as fast as l2 methods and
buffering kudamon copies cover that I'm
minimizing maximizing data one that's
often missed out at least from the
research that I've done is using
multiple GPUs if they're available
certainly in the CUDA standard is really
really easy to make use of multiple GPUs
lots of applications just fail to do
that and they sync all the things and
asynchronous tasks have existed for
quite a while now had the support
columns trade goods and it's often not
used use your threads so although you'll
be doing a lot on the GPU it doesn't
mean you can just go off single third
task I will literally run everything on
one thread I've seen that in a lot of
applications as well and if you can work
out how I've not been able to so far a
single large kernels it seemed like a
really great idea the idea is
effectively that you launch the function
once and you just keep copying data to
it instead of relaunching function with
new data
so you're minimizing that little kernel
launch overhead and there's another one
as well that I only just remembered like
two minutes before this talk which is
memory padding so if you've got the
space to allow it
you should pad your data so it basically
lines in memory trunks so when you fetch
that
and you're not having to get another
chunk with her and then get another
trunk you cannot try and make it so it's
just one request rather than three or
more and so applying what I know so I
felt there's better to start off with
quick representation of what Apple
Korsak is because although it's fairly
common in multi string managing it's not
one I'd encountered before before
starting this so I figured there might
be other people and encountered it not
really going to talk through this too
much because I think the visualization
speaks for itself bugs get to it so we
start off with our patterns and we
affect we build a tree out of them I'm
just basically to click through this
kind of see what it's doing
I'll just know that at this point I gave
up because I was doing this on my laptop
with a touchpad and it was just in the
arch to build this diagram except once
and then when you're searching for a
pattern just works like that and so
that's how you would represent it the
CPU with nodes and pointers and all
those lovely luxuries and on the GPU
you've not really got the luxury of all
that and particularly my case all that
it's a single dimensional array and I've
got to represent that sometime and so
enter the head-fuck algorithm and it's
based on Apple Korsak it's just an
extension that effectively compresses
some things and so same principles root
node n nodes and patterns are stored
alphabetically and the key part here
which you will help in the next slide is
the notes are made up of an integer
offset which is the location of the
first child both handles and and an
8-month array of 32 bit bitmaps and that
those bitmaps collectively represent all
of the ASCII letters and we'll see why
that matters again on the next slide and
there's a population count
fun and which allows you to basically
take the number of children find the
location of a child and also check
whether it exists and or whether
exist in a given order so this is what
that looks like
I've tried again to explain this as best
as I can but it's this this one took me
quite a long time to get right and so
for the example of pattern a CD or AC
DVD and you would start off with your
written or 0 and you look for the
population count up to a is the first
one in that so the population count up
to a is zero and then you add the offset
which is the location of the first child
and that takes you down to node 1 and
you basically can repeat this process
and I've got the calculations down the
sights because I felt that the address
themselves will justify or explain well
not entirely what was going on but you
can effectively repeat that same process
to work your way down through the tree
and it's worth noting that this
implementation of it is the
implementation where you're only looking
for the index of that pattern not
specifically what pattern is if you want
to know what the pattern was instead of
having one final note you would have a
final node for each branch of the tree I
am which I'm instead of it just being
there was a match that final note would
basically represent what the pattern was
mmm so previous slide you might notice
that there's d EF and there's also
another d EF right at the bottom those
nodes can actually be merged merging is
a bit more complicated than it looks
looks fairly simple and that's example
but it's pretty awful that I've got 200
line function that's not pretty at all
and the key points though is virtual
nodes share the same children merging is
done in reverse order to maintain the
alphabetical requirements and the
alphabetical requirement is so that the
population count method that will work
fine finding the children and this one
here is that indexing again there's
probably another name for it it's just
I've not encountered it before and it
effectively allows you to
represents a single index in one bit
rather than in one bite and so I've
tried to give it a decent example and
this string a string of data along the
top so random data hello world
exclamation mark and wouldn't be broken
up like this it's just broken up so that
you can visualize better what's going on
and there's a little bit of bitwise
magic going on in there it's effectively
saying which which for a would this be
located in and so for that first one the
arrays you know and and then it's saying
which bit should I set according to the
index and that one there is effectively
just shifting the bit across by the
index relative to that ring so the real
index is seven but the way that we
interpret it would be like seven on this
side and hopefully that's an OK
explanation but again it's this one to
me a lot playing about let's get right
and so the one thing this is if you use
a byte to represent this bit index you
also get 8 bits in a byte this went for
a short you get 16 and went for an
integer or any other authority that
types 32 bits and the nice thing about
that though is you can actually check to
see if you've got any matches in any of
those 32 bits when you get your results
back by just comparing it to 0 so if
it's 0 you didn't get any matches
because none of those bits are set that
if any little bits are set that is
hopefully 0 and so implementation
experimentation etc and digital
forensics file carving immensely data
intensive and when you're searching for
file headers a basically a chunk of data
will be copied to the GPU you would
search that and then a result array
typically of the same size would be
copied back so if you're copying 2 gigs
of data to the GPU for searching you
would be copying two gigs back and
that'll take a bit time
so for Matt that's assuming as well
that's assuming as well but it's a
single bite a data structure that you're
using to represent results if you're
wanting to get the index for example of
the results and you were using an
integer to do that then that would be
the same size to represent that and by
comparison if you were just getting the
index you can use a single byte or a
single integer depending on what you're
doing and and that would be good for in
the case of the byte eight locations
okay so in that example there if you're
offloading identification to CPU and
using bit indexing instead of a two
gigabyte result or a about 0.25 Gekas
all right and alternatively you could
use that in addition for fast access and
I thought I'd pick up a bit cord but
it's pretty disgusting so again don't
worry if you don't get em but it's the
point this called down the bottom is
effectively doing the same as the one
above or has the same outcome just that
the one above can be significantly
faster and so around some benchmarks
last night because I didn't wanna come
here with like this is faster honest
just trust me and so this is Titan in
microseconds I deal with text one tiny
little bit idea and I was just like
bashing together some benchmarks to test
with so that's only one mega theater
that was testing it against a bar
I've got comparisons of the indexing
versus boolean indexing a for every
single locations match and one in 20
locations is about one in 50 and you can
see for yourself the time differences
the only one that didn't perform as well
in is when all locations were match and
that would just be the extra overhead
because of the multiplicity M so future
work for that particular section working
out with there's no other name for it
again it probably is a testing on much
larger data again that was only one
megabyte I was testing with I would
this up 200 some eggs and possibly even
gigabytes and determine if it's faster
to separate the indexing and
identification
that's something I've not yet tested I
walk into that I'm testing more and
fewer bytes for the storage methods of
that particular method I was using was a
integer so it was testing 32 locations
at once and it'd be interesting to test
a 64-bit data structure of see if it
sped up or if that would cause
additional slowdowns because they like
more results to check through um and
then I think it'd be faster than running
to searches because the assuming you
were able to copy over more data that's
the GP on that initial search because
the space saved with the result rate and
by again I need to test that
so clearly theory at the moment and so
bit about specifically what I'm doing
the my dissertation is focused on
network intrusion detection system
optimization and I want to make
something more so general because as I
said if this problem applies to a lot of
things and so I'm actually developing a
head fact library so it's an
implementation of the algorithms that
I've just discussed and sort of general
purposes its use I'm just gonna say it's
really prototype and there's probably
things in it that get done better but I
like to think that the concepts are
there that can be built upon and
head-fuck algorithm it's not mine and is
described in that paper there so if
you're interested in the algorithm
itself check that out the only that I've
added to it is the bit indexing and the
other optimization methods and so I also
have to show some benchmark data from
the strength searching algorithm that I
was using and this is extremely old
extremely unoptimized this was my
feasibility demo last year and I've not
done anything on that one since and
because I've been working I the ideas
but all my final results will happen
website once we've done and as well as
all the research that most of this talk
is based on is already on the
and so some important things to know if
it's prey fast but it's not as fast as
it could be because there's no texture
memory in use there's no branch
minimization this is like this was bad
and lots and lots and lots of excessive
copying needless members in each node
I'd so many debug member cells like that
I just need results and but again I just
want to show that I'm not just speaking
entirely theory and I have actually done
some things and point if not the time
there includes the memory copy time
whereas a lot results just glaze over
that entirely and go
yeah the processing times fast we've got
27 gigabytes per second we're going to
completely ignore the fact that we
needed to copy all idea to the GPU to
actually do it and so I think it's
better to represent the results in a
realistic fashion like that's it with
the memory copy time and so this is my
final design for now and I've got the
bit indexing for the return type packet
identification offloaded to CPU
separately again I need to test furthest
actually faster I've got my buffer
system and for copying the packets to
the GPU I'm using a head pack algorithm
to build my tree for failure States
which is copied to texture memory which
is then compared and that's pretty much
it at the moment I am but there could be
more added and any questions programmers
who designed things like there are
institutions this is the tank it says
they're not really going to want to use
that they're going to want to use an
equal sign in the color of the plant and
had much of that hitting from from
German programmers so and if I that way
yeah so I go back through that the
contrast and that's really bad and if
I'd known it was gonna be slow the bear
are that bad I would have done it with
light theme and I've effectively go down
to this is the source that you want this
is what you want to search against go
and it's fully I've made it so that the
the default implementation for one
result found it's not implemented you
have to override that damn so if I'm
trying to make it so it'd be easy enough
for anyone just to pick up and go okay
on result phones we won't do this and
again I'm a student not developer so I'm
kind of just guessing as to what I
should do rather than knowing exactly
what I should do
I'm so I'm trying to build an interface
that's easy to use but again it's just
guesswork for me at the moment
[Music]
so really what I would if I had the time
I would have really liked have
integrated this and snort or Sorocaba
and the circuit CUDA code was just too
broken for me to touch em and I found
the phone smart really hard to read
I'm just because of the sheer scale of
it I think if I was if I was doing this
as a thesis absolutely I would have no
problem implementing it I just think I'm
but we're being an honest project is
didn't have the time to do such a wide
scope is actually even things on that
I've had to just go I originally had DP
DK
let me tap on PF ring as like all those
collection methods call it and but they
just simply was not time to implement
all of those and so that is the
collection effort for that is just love
pcap and yeah okay