All right. Hello everybody. My name is Nicola Henle. I work at AMD on the GPU side of the company where we develop the AMD GPU target in LLVM, which is upstream, and we use to compile compute kernels and graphics shaders directly into binary that runs on the GPU. But this talk is not about that. This talk is about TableGen, which is the domain-specific language that is used in part to build LLVM itself. Now, my own personal history with TableGen is probably fairly standard initially. I mean, I started working on the back end and you just have to use it at some point. I copied and pasted stuff. And then last year there was something that I worked on in our back end that really ran into the limitations of the TableGen front end. It ran into weird errors, crashes, and so on. So I dug in more deeply and in part this talk is my attempt to spread some of the knowledge that I gained while looking deeply into TableGen, fixing some of these problems that I encountered. So the agenda is a brief overview of what is TableGen, where it is used very roughly, and then really look at what are the features of the TableGen language. What can you do with it? Maybe you'll learn about some interesting patterns that you can use in your own TableGen sources. And depending on how time permits, at the end I want to take a bit of a more deep dive into one of the more advanced uses of TableGen language features in our back end. The nature of this talk is such that you may have questions that it makes sense to ask right then and there, so don't hesitate to do that when it makes sense. Alright, so what is TableGen? So TableGen is a tool, LVM-TableGen, into which you can feed TableGen source, like the example that you see on the left hand side, and it spits you out some automatically generated C++ code that you then include in your handwritten C++ code. It is used for all sorts of things in back ends, so for example machine instruction descriptions, register descriptions, scheduling properties of the microarchitectures of the machines that you're targeting, it automatically generates bytecode for instruction selection, assembly parsers and emitters, disassemblers, etc. And it all does this based on these kind of sources that you see here in this example, it's just the definition of four machine instructions that we have in our back ends, where a bitwise and an or in 32 and 64 bits. So I said it's one tool, LVM-TableGen, that's a bit of a lie. I know actually of two TableGen tools, one in LVM and one in Clang. They use the same front end, which is just a library that is reusable part of LVM, and they have different back ends for different purposes. So in general the flow of what TableGen does is it reads your TableGen sources, the front end parses it, does some evaluation on it and produces a big list of record definitions, which I'll show you later. And then the back ends, they don't care about the original source anymore, they just look at this set of records, they maybe filter them to look at only the records that they are interested in, which depends on the back end, to interpret what is in those records and then use that to generate the purpose specific auto-generated C++. You specify the back end that you want to use on the TableGen command line, and if you don't specify any, then it'll just dump all the record definitions. That's extremely verbose, but it's also extremely helpful sometimes if you want to kind of debug some gnarly problem that you have with your TableGen source. So if there is one lesson, only one lesson to take away from this talk, it should actually be this, that if you're running into problems with TableGen, don't be afraid to just dump all the records and use, you know, regex searches in what you get to figure out in detail what's going on. But usually you don't invoke TableGen yourself, you let CMake do it, it's all integrated. Usually you don't have to worry about it too much, there's some snippet of how it is integrated as an example. The one lesson that you should take away from this is that there is this setting LLVM optimized TableGen which you should absolutely use in debug builds because even if you do a debug build of LLVM, usually you don't want to debug build of TableGen, right? So optimize that, it helps your build times. Okay, so records. So what are records? Well they're basically just key value dictionaries usually with a name. So on the right hand side you see at the top this little snippet that I showed two slides earlier and this little snippet actually gets expanded into this big record definition and this is actually only just a small excerpt of it. And the way that this expansion happens is TableGen has a notion of classes which are basically templates for records. So at the top you see this s and b32 colon sob232. Sob232 is a class, TableGen class which is defined in our backends TableGen sources which then in itself derives from other classes and once all the transitive inheritance is done you get this big record. You have at the top this is something that the record dumping prints out in these double slash comments, a list of all the classes that were transitively inherited. So most of these are target specific but in particular there is this class called instruction. So instruction is a target independent class which all the backends that are interested in machine instructions use to filter out the record definitions. So they look at all the record definitions that somehow directly or indirectly inherit from instruction and then they work with those. And yeah like I said usually records are named so in this case we have a name that actually appears as a column in C++ to refer to that machine instruction. Not all of them have to be named like if you have standalone instruction selection patterns they don't need a name although just giving them a name can be helpful for debugging issues. Yeah so TableGen is not just a tool it's also this domain specific language and it has a kind of a core language which is used to write down record definitions and then a larger set of features around it that allow you to generate kind of regular sets of records fairly easily. Like you saw before in the example we have this scalar and and scalar or and obviously these instructions are going to be very similar so we have tools to generate these big rack records that are mostly the same in an easy way. So this is kind of a sketch of the kind of TableGen source files that live in LLVM and how they include each other so the main bulk is typically in just targets back end definitions. You usually have one top level file that includes everything else because you can have textual inclusion but not really include guards and also yeah there were some additions fairly recently but that's the way things work. You include all the various files in your back end that define instructions scheduling and etc and you include the target independent stuff. And the other big chunk is the intrinsic definitions and there are some random other things as well. Alright so much for the very brief overview. Now I want to go into just TableGen language features and there is a list of them that I want to cover. Okay so very brief look at the types of system. It's fairly standard although I mean a bit quirky. You have bits and integer types. The integers are 64 bit only. You have bit sequences. You can cast between them. You can slice bit sequences. There is a string type. There is also a code type which is a bit strange but you know there is this notation with the square and curly brackets to have like a convenient way to have C++ fragments in your TableGen source which then gets pasted into some auto-generated larger function. Really you don't need one type for that but whatever. There is a list type which is just a homogenous list. TableGen does some type inference but the TableGen front end is basically one single pass through the source so there is no type inferencing pass or anything. So there are some cases where you need to help out and put the type in these angle brackets as the second example shows. You don't need that often but sometimes you need it. You can index into lists but only with literal constants at the moment and then there are some other unset DAG and class record types that I will explain in the next few slides. Okay so unset values is an interesting thing because of course usually all the key values like the values in your records should be defined but sometimes they're not and there is actually one at the top right you see an example of how these variables or values can end up unset. Both of them are unset in the same way one explicitly with the question mark the other implicitly but there is one nice application having to do with instruction encoding for having unset values on purpose so what you see on the left hand side is just a short extract of the table-gen source of our back end which defines one encoding type. It's a 32-bit instruction since the NG32 it has this inst variable which is a placeholder for the 32 bits of the instruction and then there is an encoding called vinterp which defines the fields of the encoding. You see that the bits are 1 to 26 they're assigned to a constant value that's what defines this encoding class and then other bits out of these 32 are parceled out to variables that are there defined at the top like the vdesk which is just undefined or the op which is the opcode which is actually passed in as a kind of a template argument to this vinterp class and on the right hand side you see one of the machine instructions or the record corresponding to it that uses this encoding and you see that now this inst field with its 32 bits has been expanded so there should be eight entries in each row there and you see that for example in blue the two bits that correspond to the opcode have been filled in to 0,0 but a lot of the other bits actually still refer to these fields like vdesk, vsource, etc which are just unset bit sequences and the whole machinery for instruction encoding and disassembly is built based on these relations so the relations of which fields defining registers, etc are where is read out of this and it's also tied to you see there the DAG out operand list for example it mentions the name vdesk which is attached to the variable name vdesk to tie the representation of operands in your machine instruction to the encoding then there is the DAG type so it's called DAG like directed as acyclic graph because it's used in instruction selection but I think the best way to think about it is really that it's a kind of s expression where you have an operator and then a list of arguments except that each of the arguments can optionally also be assigned a name it's a convenient way of having heterogeneous nested structures and like I said most it's used for instruction selection patterns so there is an example down here also from our back end the first row in there describes a pattern that is looked for in the selection DAG and the row below is the machine instruction that should be generated for that pattern and so in the top row you see the inner thing is a bitwise XOR that is used once XOR is something that is named source zero with a constant this is then interpreted as a 16-bit float and converted to a 32-bit float and it so happens if you XOR that value to a 16-bit float well it flips the sign bit so many instructions have the ability to aside from whatever else they're doing to flip the sign bit and so we just replace it by this conversion instruction with the modifier that says negate the source even though the name is DAG it really more represents a tree than a DAG even though the name is DAG it really more represents a tree than a DAG that's why I said the name is a bit misleading I mean you can't really express a DAG in the source language with this syntax and then of course there's classes as I already said classes are basically templates for records they have inheritance although I actually don't have an example of that here on the slide but this syntax is basically the same as C++ for the inheritance and so on the right hand side right in the example above you see some source that's not taken from anything real that's just a random example and at the bottom you have what it's expanded to okay so there are two records that are explicitly defined right my record derives from both of these classes that are defined and I think the main thing to point out here is an interesting feature which is in the other record which has this B angle brackets 3 which is actually an anonymous instantiation of the class so you see here this anonymous zero record which is generated automatically which is quite a useful feature and the other thing that's interesting to notice that every class has an implicit template argument called name which is replaced by the name of the record that is being instantiated alright so when you know about classes and records it's very tempting to try to define all the variables in your records as functions of template arguments class template arguments this works but it tends to lead to a design of your table gen classes where they have lots and lots of template arguments and it becomes a bit of a mess for these things it's better to use let statements so let statements are a way to override values that are defined in the classes that you inherit from for example and one very interesting thing about this is that actually expressions are evaluated late so if you have here the class A again on the left is an example source it has a template P a template argument P is assigned to a variable X and then X is assigned to Y this assignment doesn't happen immediately it's delayed as late as possible which means that below when you instantiate A2 for example and then say let X equals 17 in the fully evaluated instantiation on the right hand side you see that both X and Y get this value 17 rather than having the value 2 that would be implied by the template parameter that you passed in it's important to remember that the let statement is not the one that you know from I don't know rust or functional languages it doesn't define a new variable it just allows you to override an existing one so classes I said are basically templates for records multi classes are templates for sets of records okay so maybe best to look at an example there on the bottom left this is part of a definition of intrinsics we have a def M so M is used to instantiate multi classes which is given a name which is kind of a base name for intrinsics it instantiates this multi class that is defined above and this multi class defines three records with names you know underscore X underscore Y underscore Z which are concatenated with the base name and each of those then inherits from you know some class helper class that we defined which in turn derives from a target independent intrinsic class which means that we're defining intrinsics here so we're defining three records and at once like classes multi classes have this implicit name argument so by default the names that are instantiated are just like the base name that comes from the def N def M concatenated from the name that the record has inside the multi class but you can play around with this like the example on the right hand side shows if you look at this the REC 3 the REC 3 is actually prefixed to the base name so the rule is that if you explicitly mention the name template argument then that overrides the default concatenation that can be useful in some ISAs where you have like instruction families where some of the instructions are prefixed with something there's some interesting corner cases so interestingly multi classes also support inheritance from other multi classes which is really basically the same as just putting a def M of the base multi class as I've shown there while preparing the slides I noticed that that's not entirely true and maybe that should be changed but yeah if you have a def M so the def M instantiates a multi class right but it can also actually inherit from classes which can be useful for tagging the records that you're instantiating with something like instruction things and stuff like that but it cannot have a body so if you want to override anything that that is any variable that is defined in the records that you instantiate you need to use global let's statements okay so multi class is one way of generating many regular records there is another way of doing that which is for each and for each is yeah it's a for each loop like you loop over a list or a range of integers so there is nothing too special about it in case I haven't mentioned it here in the example at the top you know that the hash is a concatenation operator string concatenation just good to know and there is also this exclamation mark add which is a built-in function to add integers you know this is just part of the encoding of the register in the isa one interesting thing about for each is that you can abuse it as an if statement so this is an example from our back end as well so we have a family of instructions that we call just vop one instructions and they have multiple incarnations right they have the basic e32 vop one there is an extended 64 bit encoding there's something that has a feature called sdwa for all of them but then for some of them there is also an incarnation that uses a feature called dpp and now if you have a class of instructions that is regular in that way except for this one thing you have multiple options for realizing that in table-gen right one way would be to just have different multi-classes right multi-class for vop one with and multi-class for vop one without the problem is with this kind of approach that you can easily get a combinatorial explosion of multi-classes so what we do here instead is this if statement basically so we have this notion of a vop profile that is passed as a template argument to the multi-class and it has a bit that tells us whether the instruction should have this dpp or not and then there is an interesting pattern here which is basically using table-gen classes as functions right this pool-to-list class it takes this bit value as an argument and then it has a variable called ret which is the return value of the function that we're defining and you know if the bit is zero then it we return an empty list which means that the for each will not do nothing or we return a one element list and the for each will do something so that's a pattern that we use quite extensively and it's quite useful yeah for each versus multi-class both of them serve kind of similar purposes I would say that multi-class is more idiomatic for table-gen and it's often easier to reuse but for each there are some programmability advantages so both have their place and use them as it makes sense another kind of niche feature is the dev set which as the example on the top right shows you allows you to capture all the records that are defined inside the outer curly braces into a list that you can then later reference and use in a for each for example to iterate over them we use this in AMD GPU to define for these intrinsics that are up there a generic table so generic table is generic searchable tables is one backend that is a fairly versatile way of exporting data out of table-gen without writing your own custom backend what's happening here is that we just define a generic table and you really should think of it as like a database table which is called resource intrinsics the fields are listed there the rows of the table come from records that are derived from the given filter class and table-gen the searchable tables backend will give you a function which you pass in a key of your choice and it will search the table and produce the corresponding struct if it exists and you can actually also define multiple keys over generic tables which is nice for mapping from between two things back and forth in both directions so here we use the for each based on lists that we previously captured to define the rows of this table and now again you might ask so Devset is really a niche feature and even though I added in myself I have to say that it's not very idiomatic for table-gen in most cases you'll probably want to instead use like multi-classes or possibly heterogeneous multi-classes where you define maybe some machine instructions and then some other class maybe for those tables at the same time but in this particular case something interesting happens because the intrinsics are defined in target independent table-gen sources which are included by all back-ends by all targets and they have to be defined there because it's a global enum that is the same for all targets it's not target specific but the table like if we were to define the table in the same place then every target would get this table which is really specific to our back-end that doesn't make sense so instead we do the separation using the Devset feature we already saw one built-in function this exclamation mark add there are a whole bunch of others the most interesting ones are probably the casts so you are able to cast between strings and records actually which means that if you cast a record to a string it gives you the name if you cast a string to a record then it looks for a record of that name and gives it back to you if it has been defined previously in the source file and then so there is for each which is basically a map function is what it would be called in like Haskell or something and there is a left-fold which is also nice to have alright so this is what we went over we went over most of the stuff now I said we could maybe do a deep dive into some more advanced application of table-gen if we have the time we don't have that much time anymore so I wonder which part might be best so we have this very complex family of intrinsics for image operations in our back-end right there is a lot of orthogonality here where part of these image instructions is the dimensionality of the image right if it's 1d to the array 2d and then the arguments of the intrinsic depends on that dimensionality of course it's either only an s coordinate or it's an s and a t and a slice in the array or it's just an s and t etc you may have this dot d which stands for partial derivatives in which case you have all these green you know ds over dh dt over dh which are partial derivatives of coordinates with respect to screen coordinates and this really large number of intrinsics we want to define some way and we do all of this in table-gen so you get code like this which at the bottom left you see it defines the notion of a 2d array dimensionality of an image it gives it a name 2d array and says okay there are two coordinates that are relevant for derivatives namely s and t and one coordinate which isn't and then in this class that we define above we define a variable gradient args which is the list of gradient arguments for intrinsics that need them which are defined basically using function calls right we first iterate over the given coordinate names and use string concatenations to define these names ds dh etc and then we pass that to that class which has really a role of a function which is defined above make argument list and it produces what is there on the right in the box so why do we want so what is that that we have on the right and why do we want it well when we define intrinsics we have to define the types of the arguments of the intrinsics right and there are we can give a type explicitly such as 32 bit float but we actually want to be able to pass not just 32 bit floats but also half precision floats so we need an any float type for the ds dh argument and then the arguments that come after that should be constrained by the IR verifier to be of the same type so that's what the LLVM match type is for and what this make argument list function does is precisely generate an array of this form by taking you know the first name combining it with the base type and then doing a mapping which maps all the names to this AMD GPU arg pair of match type and argument name and any questions about this this is a lot to those are things that we use it we don't use them for much internally they're convenient for debugging and I have plans for other things that we can do with them other questions about this I will upload the slides of course so you can look at it later we do more stuff like this so for example if you have two of these arrays of arguments you need to and all of them use LLVM match types you need to adjust the index that the match type refers to that's what that stuff is about especially that stuff on that slide but we don't really have the time to look at it in detail alright so I just want to close with some final thoughts maybe a brief look at what we covered you know a brief overview of TableGen quick run through of pretty much all the features of the frontend language except the built-in functions not in detail and a brief example of what you can use some things to keep in mind you know multi-class versus for each calling TableGen directly if you have problems to dump all the records these are kind of things that I think you should take home some possible things to improve in TableGen in the future I'm not going to work on them because well priorities just aren't like that but there are still some cleanups that could be done in the type system right to smooth some of these corner cases it will be convenient to have the hash operator not just work for strings but also for lists and DAGs that would be convenient the thing with multi-class inheritance that I mentioned and then you know back ends I mean it used to be like last year when I started diving deep into TableGen my problem was that I always ran into crashes and errors in the frontend this at least for me this doesn't happen anymore if it happens for you talk to me but now the problem is that the main problem is that I do something with selection DAG you know the eye cells patterns and I just get weird error messages that are super difficult to understand at least for me and I think there are some things there that are also in the feature set that could maybe be more orthogonal but yeah that's that would be something probably another big project and not for this talk so with that thank you very much you mentioned dumping like invoking TableGen itself given a td file you can just invoke TableGen on it to dump like pre-process kind of just record definitions and then is there a way to go from the map to then dump the C++ that gets emitted okay so the question is can you I said you can run TableGen itself to so you can dump the records can you then go from there to the generate include files so the generate includes so of course you can go to the generated include files directly by just invoking the back end directly but if you want to like edit the stuff that's in between that's currently not possible because so you could just cut out the record definitions and feed them back into TableGen as input I think there are two problems that you'd run into one problem is that I don't think the output of the dump is you have to define a variable before you refer to it and I don't think the dumping makes sure to preserve that order I think it just dumps alphabetically that's one thing the other thing is that the back ends filter the records out based on the classes that they inherit and the way that the records are dumped currently you get the information of the inheritance in a comment and not as actual inheritance in the TableGen language so I think those would be the two major hurdles to enable that thank you so much for the back end yeah so obviously you can generate other stuff than C++ from a back end and in fact somebody not so long ago added a back end that dumps the records in JSON format so you know you could then use some other tool but yeah you could dump other things then generate other things than C++ if you wanted to then in C++ you can do whatever you also explained how to use classes to actually implement something like function calls would be better to just have function calls syntax rather than a more obfuscated way so right the question was I showed how you can kind of abuse classes as functions and wouldn't it be better to have a dedicated syntax for that I thought about this myself back when I did all this work I didn't find a solution to it that I was completely convinced of but it's certainly something to think about maybe keep it as classes but allow invoking it with the exclamation mark syntax to make it at least a little bit more approachable I'm maybe wondering every so often I just have to have a brief look at table-gen files and it always takes me a very long time to run for understanding what this actually means just wondering if that's one of the very small tweaks that helps 5% to write if you just read the stuff it might help the understandability but to have a dedicated defined function syntax it's a thought that I was also thinking about this but it would have to be because this pattern isn't used that often today so it would have to be something that's very intuitive but also fit well with the other stuff in table-gen so do you think there might be a scope for it because I know there is a table-gen manual but it's pretty much a reference manual do you think this is going to contribute some of this to table-gen? Yeah, so the question is is there a scope to add better documentation or tutorial to LLVM? I wish I had the time I started a series of blog posts on my blog where the idea was that maybe that could one day lead to something like that but then I just like it's a problem of time Is table-gen Turing complete yet? Not intentionally, I don't know so there are some places like with these function calls and everything where the question naturally arises but at least last year whenever I was at a point where I thought well maybe it would be nice to have arbitrary recursion or something in there which is a way of not adding it so I don't think it is but maybe you will prove me wrong so you can, there is a very limited scope for self-references when you define a record you can define a variable which you assign a cast from the name of the record and then the record will contain a reference to itself that is the only way that was, stuff like that was actually being used in existing table-gen when I started looking this deep yeah I mean go ahead next post then you present table-gen is Turing complete yeah I don't think so but I would not be super surprised if it were other questions because I was lazy and at the time that I first thought about it there was like one place where I wanted to use it by now I think there are a few more places where it is used so maybe maybe, oh sorry the question was I showed how to abuse for each as an if statement and the question was maybe there should be an actual if statement in the table-gen front-end language for textual conditional parsing I don't think that would, no that's very far away from the kind of thing that I showed


For the deafblind around the world, Protactile Sign Language is the only medium for interpersonal communication. The problem is, it requires physical contact with someone who can interpret. But what they badly need is a two-way communication tool that frees them from these invisible shackles. Introducing good vibes, words through vibrations. Smartphones are all around us, and they vibrate. Vibrations provide the much needed tactile feedback to the deafblind as they can feel what they can't see or hear. So we infused the smartphone with a 180-year-old language, Morse. Made up of just dots and dashes, Morse is a binary language that can be perfectly translated into two distinct tactile inputs. Short tap and long press. And two distinct tactile outputs, short and long vibrations. Combinations of these inputs make words which, when transmitted as vibrations, can be felt and decoded by the deafblind. For the first time in human history, the deafblind have a two-way communication tool. The app is working on the cheapest phones, a 4,000-rupee phone. Vibration, I feel it is very good. This particular technology will also add to their privacy. The way people accepted it and using it, it's awesome, incredible. The Good Vibes project is sending a message of hope to our deafblind friends and their messaging back.


Once conquering the basics of Copic markers, it's time to dive in and learn how to use different marker application techniques to advance your art skills. In this class, students will learn 42 techniques taught in a systematic way so the ideas build upon each other. The finished product is a piece of hex art suitable for framing and displaying in the studio. Students will practice a variety of ways to blend with textures, techniques using the colorless blender, and a variety of ways to create natural elements, sky and sea, minerals and plants. The 42 videos, three and a half hours in total, are broken into six themed lessons which will enhance a deeper understanding of marker strokes, color layering, and light and shadow. The prerequisite that's recommended is the Copic Jumpstart class. Markers used in that class will be adequate for the hex art class even if they're not the same colors as the instructor uses. The knowledge learned in the Jumpstart class will also assist in making adaptations during the hex art class. Sign up for class today and get immediate access to the lessons and start making art right away. Visit art-classes.com for more information.


I went through phases where it seemed like the spirit was going to really teach me this lesson. So I worked at hospice, which as far as determining the old patients, all was around me. And that was very, very powerful. And what happened during that experience was I would go in and I had to go through like four or five, six weeks of training to be a hospice volunteer. And I was already into this stuff, so I thought, the spirit is having me do this. This is an assignment. And I would go in there and I would go through the hallways and they would all be in their rooms and everything. And I would just let myself be guided, often times to take food and water and so on and so forth. And the funniest thing happened was when I would go into these rooms where there'd be a terminally ill, diagnosed terminally ill patients dying under the last stages of the tube, like really far along, I would go in there and I would be in all the glory, all the glory of God's love. And these people were then reflections of where my mind was. If they were in a coma, sometimes they would come out, right from me on the spot. Even if their family was there and they'd been in the comas for weeks, they would turn and come right out of the coma. And they would start talking to me, sometimes alone or even in the company of their families. And they would do a little expression session with me, what they were still guilty about.  And all those words would come out of my mouth were versions of, you are innocent, you did a great job. Mission accomplished. Thank you. You are loved. Boom, boom, it would just come out from the spirit of just, you are innocent. It was just telling them that all the things that they were concerned, many of those were just holding onto the body out of guilt. It was like the mind was making the decision to cling to the body, to hold on, even though it was on the very end. And they were, most all of them were asking me for just permission to know their own innocence. And I did it. I mean, I launched. I gave them the innocent mission. And the funny thing was, I had a very high checkout rate. Instead of raising the dead, I have had one of those too, so it did go the other way. But in this case, I would come back the next day and they would say, so-and-so checked out. And then the ones I would visit would end their life very quickly because they felt the innocence. And the only reason they were hanging on was because they felt they were guilty. They said, that's nonsense. You did a great job and mission accomplished and all that stuff. I do find sometimes with these terminal ill cases, they are quite interesting how they play out because it's always about innocence. The lesson is innocence. And the belief that we've done something wrong seems to manifest in terms of sickness and death in this world. But the teaching is far beyond that. It's teaching that we have an eternal life that we're just unaware of. All we have to do is forgive all of our illusions that the ego was part of that big trick and that we can wake up from this dream of sickness and death and separation to eternal life. And it just makes so much intuitive sense. Every time I've heard people speak about this, I've always said, yeah, I know something in my heart knows this is the truth. And if it's the last thing that I do, I'm going to discover that truth.  I'm going to publish it to all the world. So that's why we talk about this with gathering shatakras all around the world.  And most of our talks, while they can get a bit philosophical at times seemingly or metaphysical, they're really all about practical application. And I've been really, I've been hushed in humility by seeing this journey about how the Spirit is just showing me our divinity, that we really are divine beings. And that these little flesh suits that we wear aren't really the whole story. They're not the whole story at all.


Damn, I love backtrack. I really do. Where's our queue? Alrighty, so we've got a pretty intense 50 minutes. We'll be going through the development life cycle of an exploit. The exploit is in an NNM open view system. Are you familiar with that? Like that big machine that owns the whole network sort of thing. So if there's one box in the whole network that you want to own, it's probably that one. The whole exploit development cycle was quite interesting and a bit painful. And that's basically what I wanted to share, the pain, you know, sort of not have to deal with it all by myself. So basically what we'll be doing today is we'll be going from bug to zero day. We'll just retrace all the steps that we took in order to own NNM from fuzzing until the whole, you know, developing through Oli and getting our shellcode in there and we'll see that we had to face all these nasty, nasty difficulties which took a sleep and lack of sleep and lots of trouble with the wives sort of thing. I love you. Okay, so I think we'll just drop straight into the demo. I think we might be a little tight on time. This is basically our open view NNM system which we were encountering. We were actually fighting with this in a pentest. And what we decided to do at some stage when we noticed that there weren't any plausible attack vectors is to start, you know, prodding the zero day angle seeing if we could find something, some low hanging fruit that would eventually give us or compromise the system. So a quick port scan revealed that there's all sorts of funky services running on NNM from, you know, SNMP services to HTTP services and everything. So we went for the lowest hanging fruit and we started bashing away at the HTTP service and oddly enough in less than 60 seconds the thing blew up. So I'd like to show you the whole process, the development of the spike file that we used which was ridiculously simple and while I'm in the intros I'd like to say no thanks to HP which didn't even bother returning a mail after two calls and three mails telling them that they've got an unauthenticated overflow which could lead to system compromise and they never even bothered returning a mail. This exploit was actually published six months ago and it never even received the CVE so I've been having fun pawning HP machines while everyone's been ignoring this so, you know, hopefully this will sort of raise some attention to the topic and people will actually patch their machines or at least disable the service because this is actually quite popular. Alrighty, so the service that we'll be debugging today or observing is the OVAS service. This is their main web server and what we did is we started using a very simple sort of template. Is the mic on? Can you hear me at the back? Too far. Alrighty, so basically we took a very, very overly simplistic spike template which we started throwing out the application and I'd like to show you the results. Obviously the wonderful thing about this is that we're all doing this on the back track so the whole process was self-contained into one sort of debugging session. So if you look at the spike file then you'll see that we're a pretty basic sort of template here. We're fuzzing just like a few headers, the host header. We're not even going to be doing the actual get request. I've sort of dumped it down a bit so the fuzzing won't take too long during the demo. Hopefully we'll be finding that our overflow is in the host header field so let's just give that a quick run and see what happens to our NNM machine. So we'll use the audit SPK file, HTTP SPK file and just by running this, what am I missing? Port. Just by running this we can actually see that HP NNM is reacting its opening threads for each session being battered away and in exactly 20 seconds the thing broke. So we were very happy because we thought that this is going to be a stroll in the park. We'll develop this exploit, get a root shell, get home back in time for dinner. Little did we know. Little did we know. So looking at this crash we started poking around and very soon we realized that this was a structured exception handler crash. I can actually replicate this with a standalone Python script. It took us a couple of tries playing around with the buffer lengths just to see that everything was as anticipated. So looking at the proof of concept or standalone skeleton exploit as I call them, basically what we've got here is a get request with a very, very long and ugly host header and this is where our crash comes out and apart from that everything is pretty much as usual. There's nothing fancy or interesting about this get request apart from again this host header which is taking around 4,000 bytes of buffer. So we slammed this against our NNM machine. Yeah we probably should have the debugger there and we'll take the OVAS process and let it live. And hitting the open view service with our script, this is actually a bit freaky because it takes it a few seconds to crash. What we'll see is that we own all these wonderful registers. We own a bit of the stack and possibly the best part of this whole thing is that we own the structured exception handler. Now usually what we'd want to do in a situation like this is allow the exception to occur. So I'll just simulate that by pressing shift F9. And here we have EIP which is all ours. So we're all happy and giddy about this and yes we're going to own this thing in 30 seconds because all we need to do now as you usually do in structured exception handler overwrites is you need to find a nice place that contains a pop-pop ret instruction and that will basically bring us right here. So the rest of our buffer which is usually where we'd shove our shell code in would be right here. Now notice that we're pointed to 4 bytes before our value that overwrites EIP. And usually what you do in a standard structured exception handler exploit is use these four bytes to jump over this address so we don't actually execute these bytes. And then here you'd be putting your bind or reverse shell. If we look at this a bit further we'll see that we've got around 400 or 500 bytes for shell code which is usually enough. I mean you could probably get away with a reverse shell of 350, 400 bytes unless you need to start encoding it. So the first thing we did all happy and joyous is look for a pop-up ret command to get us back to our buffer. And this is where things started to get really, really ugly. We found an address in one of the HP DLLs which obviously isn't compiled with safe SEH or GS or anything that's just out there. So looking for the first address I think I might still have it here in Oli. Yes. So we found this address which indeed contains a pop-pop ret command. Now just take note of these values here because this is going to play an interesting part in the next few minutes. So essentially what we'd like to do is go to our proof of concept exploit and change these 42 bytes into our address that will lead us to our pop-up ret. So we did this and we just took that wonderful address, shoved it here and it's padding just at the right place. I skipped a few steps of finding the right place in the buffer, etc. That's not what we want to deal with today. We're going to look at the harder aspects of developing this exploit. So we send this and let's see what happens. Okay now apparently the actual overflow is in the HP mechanism of filtering URLs and logging them which is actually quite common. So once again we've got our structured exception handler which catches the error but something is wrong here. Take a look at this. I'll show you what the original value should have been and what it ended up as. So the original value should have been 5a02ef74 and what we got here, well I see a 02 and I see a 74 but something else, something has gone wrong here. So we tried this a few times thinking that we did something wrong but essentially at the end what we realized is when we looked at the actual placement of our buffer on the exception handler we saw something funky here. So if you can see it over there at the back but it looks like something expanded. Do you see that 5a right here? That 5a should have been the first thing to overwrite our address and we can see our 5a here. Let me just show you the original address. We can see our 5a. We can see our 02 and it looks like our EF has been mangled because 74 is here so EF is basically transformed to what is it, AFC something. And that is when we understood that we're screwed because what's going on here is some sort of translation or expansion of bytes which are not alphanumeric. So suddenly we had this alphanumeric cloud over our head and we realized that we'll need to do some encoding on our shellcode. Now Metasploit actually contains a couple of really, really good alphanumeric encoders so we thought that, okay so this isn't such a big deal, we'll just simply encode it with Metasploit and everything will be done with. So the next step was to find a nice alphanumeric return address that wouldn't be mangled after sent or after accepted by NNM. So we dug in a bit deeper and this is what we found. All right so this is the address again somewhere in NNM, one of the DLLs, lots of them to look for and we'll once again slam our NNM server and wait patiently for the crash. This actually freaked me out yesterday because I was sending the buffer and waiting for a couple of minutes until the crash occurred.  So once again we've got our structured exception handler, this address is good, this address does not get mangled in any way and this will directly lead us to a pop-pop-ret instruction set. So I'll allow the exception to occur, I'll press Shift F9, I'm taken to a pop-pop-ret. Now notice what happens here on our stack. We pop one, we pop one and then we would return back to our buffer so if we follow this and dump, these are the exact bytes that we're jumping to and these are the exact bytes that constitute our return address. So we take the jump and usually what we do here is we take a short jump over the return address and put our shellcode here. Now a short jump would be an EB something, EB10 for example and that would just very very conveniently take us there. But then we realize that EB is not in our allowed instruction set, in fact we're only allowed a very limited instruction set, a limited range of bytes that we can use. I think I've got it somewhere here just to give you a bit of reference. So you can see that this thing isn't pure alpha numeric, I mean you've got some of these bytes here but it is a very limited instruction set and we can't just do, we can't even have our short jump, we can't even use EB. So this is where things got really really hairy and we had to think sort of very very hard on how to do this. So after bashing our heads a bit we realize that we might try to use a conditional jump, something like a jump zero, jump not zero, we just need to make sure that our zero flags are set and that jump would always be taken, otherwise these instructions will actually kill our exploit. So in the end what we ended up doing here is giving a conditional jump and we have to make sure that each and every time that this exploit is sent that condition will always happen, otherwise we screw our exploit. So we've got our zero flag here, the jump not zero is taken and that should take us across our return address and into the safe zone of our buffer. So we'll take that jump and here we are. And from here onwards we're free to write around 400 bytes of shell code. So the first thing we do is go to the metasploit framework, generate some alphanumeric shell code and something looks wrong because you'll notice that the actual encoder, doesn't matter which one you use, either the alpha two or the pex alpha num will actually contain some characters which are not alphanumeric. And this is a problem because looking at this you say, well, okay, it doesn't matter that this is the decoder, it still contains a byte which will screw up our shell code, we cannot have this. And then the very, very sad realization that metasploit will no longer help us and we need to do something custom. And that is when things really, really got ugly.  Luckily for me, I saw this article about Venetian shell code and I got this interesting idea there that came up to me and I said, maybe we can use that technique in order to write our own alphanumeric shell code here. Now the other problem that we have is that we only have around 400 bytes of space. Now if we want to have a reverse shell or a bind shell, that's around, I don't know, 250, 300 bytes and if we want to encode that, you're at least doubling that. So there's no way that our original space for our shell code could cover all of that. And then we think, okay, so maybe we need a smaller payload, something like an egg hunter that could look for a second larger payload in memory and we'd have to figure out a way of getting the second payload into memory and then the first payload, the egg hunter, would actually search safely through the address space and find our final payload and give us a bind or a reverse shell, whatever it is. Yes, it did get hairy because now what that means is that we need to encode, manually encode 32 bytes of egg hunter code. The egg hunter that we used was one of Matt Miller's creations, amazing stuff, really, really, 32 bytes of magic if you ask me. So let's just take some reference, take a while to look at the egg hunter shell code itself. The egg or that signature that the egg hunter will be looking for is Woot, W-00-T, all in capitals and you can actually see the egg right here inside the assembly code. If anyone's interested in seeing the actual code then come to me later, I'll show you the article by Matt Miller and give you some code examples. But essentially these are the bytes that we'll need to write and encode manually. So the technique that was mentioned in the Venetian shell code article basically said that the easiest way to get past the alphanumeric situation is to actually carve our own shell code in memory in real time and very elegantly place it onto the stack in a place where we anticipate that execution will reach. This sounds much more complex than it actually is. I think it's much easier to see this in action. So what I'll be doing now is I'll be writing the shell code in Oli and explaining each line what it does. 25 minutes left. So that's the first part of the shell code and it's actually not too complex. Notice that the shell code is composed of really, really basic instructions and all the characters, all the op codes are allowed. So basically we're limited to things like add, sub, push, pop and a few others but that's pretty much it and that is the instruction set that we have to start carving our shell code in memory. We'll be using EAX for several calculations so the first part of the shell code basically says whatever you have in EAX, zero it out. So EAX is zero already but let me just shove some values here so you can actually see the process happening and we'll step that and step that. So EAX is now zero and I know that all my calculations are beginning from a clean slate. The next thing I do is I want to locate my position in the stack because if I will be carving out shell code on the stack I need to know where it's carved and I need to carve it in a place where execution will reach after my first state shell code. So looking at the actual memory dump we would probably want to write our 32 bytes of egg hunter around here. So in order to do that we need to find our current location in the stack and we can do this by using a really cool trick by pushing ESP, the stack pointer to the top of our stack and then popping it to EAX so now EAX actually holds the value of ESP and we can start doing calculations on EAX. The next three lines basically align the stack to exactly the place that we want to write our shell code. This is actually an interesting calculation because if we do, if we take this, that and the other command then EAX should now be pointing to exactly this area. So our stack is aligned to the place that we want to write our shell code. Now that we've got that in place we actually write the egg hunter shell code once again using the sub and add commands. So just take a look at the rest of the shell code and see what that looks like. All right, so these were the first instructions that we gave. Did our desktop just die? These were the first instructions that we gave and now once again we zero out EAX in order to start writing and carving our shell code in memory and just again, just to make sure that you've seen that notice these last four bytes of our egg hunter. These will be the first four bytes that we write in memory. So E7FFE775. We'll do some calculations. We'll work on EAX, subtract these two values and look at the value that we have in EAX right now. Let me just get it to the right place. Do you see that? That's my 75, that's my E7, that's my FF and that's my E7. So I've got that value on the stack now and what I'm about to do it is I'm going to push it to the exact place where I had it aligned to before. So we'll push that and you should see the last four bytes of the egg hunter written to the stack. Oh, that ran a bit too fast. Okay, I've already written two lines. Let's do that again just so you can see it happening in real time. Feel the love. All right, we'll crash it once again. We'll take the jump, we'll pop, pop, ret it, we'll gently jump over our return address and we'll paste the beginning of our shell code. Great. So once again, we zero out EAX, we find the location of where we are on the stack, we align our stack to where we want to carve our shell code and now we start writing the shell code. All right, so again, the first two lines zero out EAX, these are the last four bytes of our shell code, of our egg hunter shell code, we push these onto the stack and there you have them and then we continue and then we zero out EAX once again and we write the next four bytes and we push them onto the stack and again, zero out EAX and we keep on doing this with all the 32 bytes of our egg hunter and slowly our egg hunter materializes just at the end of our buffer. Once again, zero out EAX, do the calculations for the next route, push it onto the stack and so on. Now, where exactly are we pushing this stuff because once this loop finishes and I've pushed all my 32 bytes onto the stack, well, it was aligned in such a way that as I continue the code execution, I will actually meet my egg hunter and from here on, basically what happens is that the egg hunter kicks in and starts looking for the final payload which is a bind or reverse shell. So let's do that, let's take all these modifications, let's put them in a script, run it and see how the exploit works and also look at the egg hunter in action because this is probably one of the nicest pieces of assembly that you could ever use in an exploit like this. We also had another problem, which I didn't mention. Where do we put this large payload, this large, I don't know, 600, 700 byte payload of a bind or reverse shell? So mucking around with the NNM service, we actually saw that if we append an unlimited amount of data at the end of our HTTP request, that wouldn't actually be affected by the OV filter and we wouldn't be getting any bad characters and nothing would be mangled. So this is an ideal place to put even 1,500 bytes of shell code. So that is where our second state shell code will reach and don't forget, as always with an egg hunter we always need to have that signature, that egg that the egg hunter will know to identify and act upon once it sees it. So let me run this final working exploit and show you how we actually got to execute code on NNM. How are we doing with time? Alrighty. So we hit NNM once again, same sort of idea, the structured exception handler. Yeah, it has to kick in. We've got our wonderful, friendly return address. We take the jump, we pop, pop, ret. We do the funky jump over the return address. Ugg, I wanted to do something with that. Hold on, sorry. Once again crashing it, structured exception handler kicks in. We take the jump, take the pop, pop, ret. Jump over our return address and right here I'd like to make a tiny change just so any future changes are actually seen in Olly better. We'll get this red highlight than just normal highlighting. So let's start walking through and see what happens. Once again, EAX gets zeroed out. We push our stack location into EAX. We do some calculations on it. We align our stack to where we want to write our egg hunter payload. And then we start writing the egg hunter. So ESP starts decoding our egg hunter shell code and we end up meeting it. Now, our egg hunter will look for instances of root, capital W, zero, zero, capital T. And once it finds two of these in a row, it will assume that our shell code is right after that. So what we'll do is let's put a couple of break points in these instructions. This is basically the command that looks for the first instance of root. If that is found, then we look for another instance of root and if that is found, we jump to the location that comes immediately after that, i.e. our shell code. So let's give that a run and we hit our first break points. It's currently looking at this memory address, looking for these bytes, W, zero, zero, T, or the other way around. Not here, go back, search again. Not here, go back, search again. And you can actually see EDX is the main counter used to search through memory. This could take a really, really long time because we might be looking through four gigs of RAM, which is a lot. So let's skip this break point and ask the egg hunter to stop and show us what's going on after the first root has been identified. So we'll let that run. This could take some time. Nice seeing you all. You want to entertain them, Chris? No. Pup goes that way. Pup goes that way. Olly actually does add a lot of overhead to these type of things. You'll notice that when we run this without Olly, it shouldn't take more than 10 seconds, but those are probably the most beautiful 10 seconds that computer has ever seen because basically it's pointing itself. So we've hit our second break point. Let's just take a look at what EDI holds and look at that, it's holding our first root. See, follow this memory space. Look at that, that's our second root. That was our first root and this is your standard bind shell code if I remember correctly. So let's see what happens now. The jump to continue running the egg hunter is not taken and the next instruction that we're going to hit is jump EDI. Now, what do we have in EDI once again? We have a nice unadulterated bind shell. So let's take the jump and this bind shell, just in case, was encoded using the alphanumeric Metasploit encoder. Even though we didn't really have to, we just thought it might be safer. If everything is sort of alphanumeric-ish, then what the hell, why don't we have the shell code that way as well? So basically what we see now is the bind shell decoding and this is actually very pretty to watch. If you look from here onwards, you'll actually see the bind shell decode in real time. So we'll press, we'll single step and just look at that CLD in below and you see that that's like raw bind shell decoded. And this happens really, really quickly. So let's allow our bind shell to completely decode. I'll put a break point at the beginning and in theory, we have nothing listening on port 4444 right now. If we now let this bind shell run, we've got a shell. So just to have like, you know, the meat and everything will do that and that's actually interesting. We won't go into that right now. What I'd like to show you though is what I'd like to show you is the actual exploit running in real time so you can get an estimate of how long the egg hunter does search through endless amounts of memory space and obviously also look at the process shooting up to 100%, which again is probably, you know, the nicest part of this whole thing is that the machine is literally hacking itself and the last one is, you said, well, I've got a buffer somewhere. It's got a bind shell. Look for it and when you find it, execute it and make me some coffee while you're at it sort of thing. All righty, so what do we want? How do you get to the task manager thing? Backtrack! Ah yes, that's the one. It's okay. All right, so what's this little box right here? As the machine gets hacked. All righty. So we'll send our final payload. Look at that. Oh come on, you can do it. I think I can, I think I can. It's probably taking some time to crash. There you go, egg hunter working. The machine is in pain screaming. We'll probably be done a bit earlier. And you know exactly when to look for the shell, right? The machine is so slow, it's actually delaying the output of net stat. It's like, just give me a second, I'll have it there, just a sec. Isn't that beautiful? All right, so the shell code, the egg hunter looks like it's calmed down, which would probably indicate that we've got our shell.  I had the whole offset of the shell code wrong and Chris takes me to drink. Thank you, Chris. Thank you. He planned an off-sec party last night. Yeah, I saw it to God, brother. All right, guys, thank you very, very much for coming. Thanks for this support.