BSides Iowa 2018: "LANGSEC: Defending against iOS text bombs"

okay I'm Chad a baker from here in Des Moines I have a consultancy fly dog Solutions LLC and today I'm gonna be talking about lang SEC language-based security and how a lot of the vulnerabilities that have popped up recently for a long time have all been based in programmer failure to follow basic formal language patterns in their programming and so hopefully we can write software that's correct from the start so that we won't find any bugs in it later so the the language security thesis is that if we use formal language to write provably correct code there's not going to be any books and for the longest time well since the 70s in C we've been very

undisciplined about how we write our code in thinking of the different complexity models that we're introducing as we go along to try to make sure that we're very disciplined and at each decision we make try to always default to the least complex model we can use which makes our code a lot more testable and a lot more safe so here's a vulnerability that came out maybe like a week or couple weeks ago it was the Windows Defender bug which was a bug in Windows ball durability scanner that it parsed a RAR file and it had a memory leak in it with root privileges stuff like this should not happen if we were writing formal parsers and you think

about all the different parsers that you use I mean we have HTTP your parson the command line if you're used in sequel you have a sequel parser if you're passing JSON packets around with a web client got a parser for that you have a parser for all your different data files like JSON or PNG and you also have a parser and a lot of your operating system calls anytime where you're passing in a string to that operating system calls in your C library there's a parser under the hood of that and so there's been a lot of different parser related bugs lately this this Windows Defender bug that came out a couple weeks ago this iOS Unicode parse

bomb where they didn't write a proper parser for Unicode so you could pass like emoji that would like crash your your iOS device shellshock there was a bug in the bash parser image tragic there was a bug in everybody's like a PNG or JPEG parser for image magic and then sequel injection we deal with that all the time and if we think about it that's really a parser bug because we're allowing unperson put to go to a place where it's not supposed to go and we catch that upfront if we actually parsed it properly so here's kind of a brief history over the last century of how this is unfolded a little bit after the

turn is a little bit after 1900 there was a International math conference and Hilbert proposed the problem hey can we solve like all problems mathematically and with computers before we actually had computers and then Church and Turing came along a couple years later and they're like no there's things out there that are uncomputable even if we had a infinitely powerful computer we still couldn't solve them and then in the 50s and 60s Chomsky came along and he's like hey everything is you know uncomputable in the worst case but for most of like human language and what we do as humans there are many simplified use cases of the languages we use and and we can kind

of construct a hierarchy of it takes more and more power and then Valaya in around 1975 proved that context-free grammar parsing is just matrix matrix multiply so you know if you have a fast Strawson sparse matrix matrix multiply that's exactly the same complexity as grammar parsing so it's actually the same problem so here's kind of a Chomsky type hierarchy of the different complexities that we normally run into at the top we have a static immutable variables I mean you declare it once it never changes and it's really easy to reason about cuz it's constant you have a finite state machines which are nice because you only need a finite state to reason about them and they're also cool because you can

evaluate them in parallel you can actually shop everyone else is coming in

you can chop them up and evaluate chunks in parallel and then combine them and so you can use cool algorithms like yeah like Map Reduce if you wanted to and evaluate the massive strings in parallel and there's context-free complexity which is I have a finite state machine and I also need a stack to store what state I'm in and that's that's kind of bounded reasoning as long as I have the context of where I'm at on the stack and when I'm parsing these things I have to make sure that this stack only grows to a certain size or else it's gonna overflow my memory so I still have to be careful with that and then there's the full case of like

all different programs which I can simulate with just a finite state machine in two stacks and if I if you give me a finite state machine in two stacks no matter how they are you have a sometimes they call like a weird machine and you can compute anything with it so for those we try to whitelist it to a patterns of that we know our are going to halt on us and use finite resource bounds so for static immutable things we just have to be very smart about using our programming language wisely so if we have like a constant constructs use that like there's the Const identifier in C++ that you can use to simplify things to the compiler if

you're using languages like C or C++ you can use enews I mean don't pass an integer that has you know 32 bits worth of values when you only need like 3 and so you can constrain your state space down to the minimum you need that's very important for finite state machines you can use regular expressions or a handy notation for string matching the one thing you have to worry about with finite are a regular expression so is make sure that you bound all your matches make sure that you're not matching on anything that's more than like lengths something that's what we run into trouble with regular expressions mostly a little tidbit Eric Schmidt at Google he was one of the

co-authors of lacks the Lex parser for context-free grammars of course you can use the the Bacchus nord BNF notation where you like have like you know state a goes to B or C or D and then they expand into you know this and at the bottom you have terminals there's different parser generators out there that a lot of people use like bison if you're doing C code or antler if you're in like the Java world and there's another way that you can use it that's probably should be used more it's called a parser Combinator where you kind of build up your language using various small functions and just compose them together it's like you have a function

that recognizes the letter a and you have a function I that like recognizes the letter B and then you have a function that says I want to recognize an A and then recognize a B and you'll chain those together and you can create essentially just your full context-free grammar out of these these combinators and when you're in the the turing-complete case that i don't really have any i don't know the complexity of what i'm dealing with about all you can do is count your resources like how long did this computation take make sure that it's that using more than a set amount of memory and just make sure that it never seeds those resource bounds because

that's all you can do if you're treating it as a black box is make sure that you kill it off if it runs too long or tries to use too much resource for parts or Combinator libraries I'd recommend either hammer if you're doing C and there's a new one they just wrote in rust called nom which is even faster hammer is nice because like with the iOS text bug you have a essentially a binary protocol cuz you can you it like like with emojis they use like different byte lengths so so hammer is really nice because it does like one bit at a time if you want to and so does nom and if you want to look at it really

good examples of some parsers in the wild go to the node.js project and look at their HTTP parser it's actually a really nicely constructed parser that it has it's a it's a big finite state machine with case statements and switches and you can kind of just follow okay this is this is how I parse that that URI up at the up at the top of the window also if you look into the clang source code you see more of that parser Combinator style where they're taking functions and composing them they don't actually use like a library like like a hammer or nom under the hood they're just have like their own but it's still nice and if you want to see something a

little bit more messy real world look at the the post-grad store SQLite parsers they're also on github another thing that does come up a lot is resource usage and when you're using resources time is very important especially if you have a network involved so do like Grace Hopper did when she's like like the general is like you know how do I how long was this communication gonna take to go to the satellite and so great Grace Hopper cut off a couple sections of about a nanometer sorry a nanosecond worth of wire and she's like well general it's gonna take this many nanoseconds and that that works the same on you know how many nanoseconds between

this and that server on the rack how many nanoseconds you know between you and this data center count your nanoseconds because usually that's the first thing that fails is people don't count nanoseconds and the way that they're trying to write this system and that you can't violate the speed of light so if your nanoseconds aren't going to fit you're already screwed so so some other orders of a vulnerable parser first look at the tests over the thing did they actually write any unit tests or integration tests so for it do they have control flow that looks very ad hoc if they're not using a like like a partial generator library I mean is there go twos everywhere is it more

of like a finite state machine that they're chaining them together I mean look at that if they're doing like this ad hoc stuff look for any regular expressions they have in there that have no bounds on them cuz they're gonna blow up if they're doing what's called shotgun parsing where you parse just a little piece of something and then you use it without verifying that the whole thing parses that that's where you're running to the the problem that that thing actually later on gets negated because it's it's an error State and so don't ever use partial parses also if it's C code I mean you can just grab to see if it has like a sterling in it or a

2i because both of those are very unsafe if you're doing Malick's make sure that whatever is allocating that thing is bounded somehow in the code to make sure that it doesn't blow up and also look at the the specification for the grammar that it is that they're trying to parse and if they never wrote it down that's a big red flag because you kind of have to have a formal specification of what it is you're parsing if you're gonna write correct code yes so some of the top parser bugs are using partial parsers so like I get about halfway done I'm like adds close enough but I don't wait until the full thing parses that that's always

a problem I don't define the resource balance that my parts are supposed to use like like my parser should only use so much memory and so much so many CPU cycles or else it's going to say error I can't do this make sure that it does that yeah if you're doing this wonky control flow the unrar bug for the the Microsoft Defender problem was a type mismatch between signed and unsigned integers so anytime you're taking out a parse result and throwing it into a variable make sure you're type checking whatever that is that you're throwing it into to make sure that it fits and also just this bad language and protocol design from the start especially with

Network protocols where we don't really think through the whole thing as we write it and there's just a actual defect in the design not necessarily our code so in terms of like quality assurance when we're parsing that there's there's usually two stages one is our compile time test stuff that we can teach our programming language to do and our libraries we can use to make sure that we're doing it right upfront and then their runtime test once you're a lot slower that we just have to run this thing and make sure that it's doing what we think it's doing so in our language we can start out and try to reduce the amount of state that our

parsing task uses so in JavaScript there's constants in rust and C++ there's ways to declare constant variables that aren't going to change on us and rust also has something called a borrow checker for when you're you're allocating memory that'll it'll it'll check the semantics of that so as long as you're using it within the the context of what Russ says is safe you know that you aren't using memory that's already been freed or something another thing you can do is use code coverage for your unit tests this is a big win so you can do this in in clang there's the rust options to do this LLVM actually has a coverage report that you can actually see how much LLVM

covers on itself there's Istanbul if you're into the JavaScript land so what this does is it kind of turns your code itself into almost a finite state machine where you can see okay my tests never hit this branch why is that and try to see if if I could hit all of the different states so at least I I know that I've tested most of the states of my code and of course this isn't gonna work if you have code that's really recursive that's kind of calling itself but as long as your code has nice nice branch tree flows it's gonna give you a really good test coverage another trick we can use our sat SMT solvers so sad' stands for a

satisfiability modulo theories so you have a Sat solver that solves just a boolean circuit like give me a satisfying assignment of true and false that that makes this circuit evaluate to true and modulo theories means I add in an extra library that knows more than just sat like it might be able to reason about integers or it might be able to reason about bit vectors which is that very useful so the idea kind of behind this is is Howard Currie correspondence that programs are actually the same thing as mathematical proofs they're just use a different language to describe them so we can use all the machinery from math to reason about programs and all the other way we can

use all the the things we know about programs to reason about math and so the idea is to take your code and compile it into a math proof and see if I can prove it and either I can prove it or I get a counter example which is a bug in my code and so the simplest example is you take an if statement you know if X is less than 5 I need to solve an equation that X is less than 5 so a lot on your branching logic usually goes into this SMT solver and what you'll do is you'll have the concrete and the symbolic and then and you use both of them and it's called can

colic testing so the idea is that you take you take your code you have an SMT solver create equations for all those branching conditions and then you you start with some concrete value you trace through your code with code coverage see where it ends up and then you'd be like okay well I didn't get to this thing how do I get to this thing here and I mean I mean I'm your branch conditions and you just internally do this over and over again and I'll talk about later one of the the most advanced solvers is coming out in a conference next month another trick you can do is to always know what your memory failure modes are on a piece

of code so one thing that Neil Mitchell says that to do for a lot of his code is he will take his his virtual machine that he's written his coat on and he'll keep on reducing the stack size until something breaks and they don't go look at the stack trace and so knowing where where your code breaks on all your resource boundaries is really critical especially if it's not your code and then then you can in your in your CI system you can whitelist traces of these stack traces that are acceptable like yeah I needed enough memory for that that's a good that's that's that's correct and also helps you reduce the space of your programs another thing

that you need to do is know where IO is where are you getting that information from the outside that's not static that you're bringing with you in the code and so what you want to do in general is build Islands a very pure code that it's just you know logic you know I put in a number I get back the same result every time and and try to grow those in the big islands and and then know where the boundaries are where they had taken IO from the outside which for most of us is an operating system call and one of the things you can do is called Tate or flow analysis where you use either like the LLVM data flow

sanitizer there's the checker framework for Java if you have Android code and the idea is that I have this variable X I want to know everything that ever assigns into this variable X from my i/o from the outside world like did this come in from like the network did this come in from a file that I read and so what you do is you do what's called Tate analysis that you figure out you know I have an i/o that comes in it reads to some string buffer where does that string buffer get populated everywhere else in my code and this is very important for like security like you don't want to be writing private information to your log files

for example and some of this you can do a compile time with with types by making special types for things that are like secret or you don't want passed around just a contorted C++ example and another idea that that's been popping around a lot lately is observability when you make a change to your code even if it's an infrastructure piece you want to make sure that there's some way that you can observe the change to it and so usually you want to have two source code repositories one for your actual code and then after your code is checked in it then runs through your CI system and then your CI system for each check in

writes out all the tests test results both like your unit tests and also your benchmarks which are essentially a resource tests like how much how much resources did this piece of code use and you really need that that a that second repository so you can kind of go back and and do analysis you know where did I introduce that bug because because if you don't have that that repository of all your test results it's really hard to to kind of bisect and get back to that another thing you can do is take your grammar or whatever it is your language and dejected simplify it break it so that it can only be used in certain ways

so for like sequel I can just completely eliminate all kinds of sequel injections if I take the sequel parser and I make it so that anything that has like a drop or update statement in it it is automatically rejects and I put this at my database so even if I throw in something that somehow gotten injected it can't do any harm other than read for in your code you could ban floating point statements for certain sections that you know you just don't me the complexity of floating point you can in your CI system make sure that you're never calling certain functions or as I'm going to show you later you can actually eliminate whole functions from

your system so they can't be called because they don't exist and even down your your operating system so in LLVM there's a couple cool parameters where I can take these parameters and throw them through and everywhere that these functions are unused and the compiler can tell those that are not used it just eliminates them from your binary when it does the linking it makes us a special section for your functions and it makes a special section for your data and then when it goes into link it it could be like well you're using this thing this thing in this thing but you aren't using you these other functions here so I'm just gonna throw them out so that way

you've just taken your whole attack service and limited it to just the code that you're using for this project which is pretty powerful because like you know that some attacker tries to use library X function Z function Z doesn't exist because you're not using it and plus it saves space because in there in our serverless yeah you know so back in 92 the MPI standard for like the big department but energy supercomputers doing tens of thousands of nodes 2014 database lambda same idea you have a big static binary that you'd like a zip file that you pass through you to all the different nodes and they just execute it and the only contract is that your

operating system has to be stable but you can deject all the libraries that you bring in with you to make sure that you're only using like a dejected version of a sequel parser because you know that this this function only does reads and if it writes the database you can even deject your own system calls you can link in custom G Lib C so you can write essentially a wrapper around all those i/o operating system calls so instead of calling the normal calls that are usually linked in on your system it calls a custom set that you pass through it so like you try to call function X it does extra checking to make sure that

you know this exists and the way I want it or like I just can't do it it's a no op so this is another way to kind of trick your binary into being much more safe than it normally would be using the full G Lib C which is very unsafe yeah and in terms of memory bugs you essentially have to you have those are on this your stack which are mostly handled by the compiler and those are on the heap that are mostly handled by the user and the problem is C in C++ is that we have a lot of heat bugs because we're humans we make errors and that's where a language like rust comes in where you

have a borrow checker that you have to kind of like it's like a library I have to check stuff in and check stuff out and it keeps track of where all those those allocations are on the heap even across threads another thing you can do is run LLVM Zaisan so it's the LOV m address sanitizer and they did this on Gen 2 and I would strongly recommend if you have a system where you're deploying like an entire distribution like embedded vehicles run a syn on everything like Gen 2 did on a debug build and you will find just keep allocation glitches galore and everything that you're bringing in it's very powerful and this is the this is

the the parser that sorry the fuzzer the that's coming out I think in May it's called angora it's kind of a so there's American fuzzy lop and this is supposed to be like better than American fuzzy lot because there's like longer hair and it gets a much better coverage and the way that it does it is it uses byte level tape tracking so it doesn't just know like the line of code you hit it knows the actual bytes that that input manipulated so like I don't know that I just I just hid variable X I knew I know I hit variable X and I and I know I hit like the first or second byte on

it and you could buy a new bit level if you wanted to another thing that it does is type inference and so it can tell kind of in the context of using things you know is this an unsigned or signed integer it also does something called gradient descent which they use a lot in in AI where you have a bite you know that's you know 32 bits and a 32 bits but anyway you have some value in memory and it does a gradient descent where it kind of tries to do what I just blame gradient descent you kind of you can have a slope of where you're getting better and better answers and it tries

to tell where that is and keep following that that's slope in high dimensions and then it actually gets pretty pretty good results because a lot of our a lot of the conditions that we have in programs are like like X is greater than 5 type of things they're linear and also it does a context-sensitive branch count so it knows that I called function acts from the context of something up here and it calls it it takes those pieces of code coverage and it counts them separately based on the context in which it was called so it does a little bit more recursion I guess you know more state about about where things were called another thing that's it's been

used a lot in the automotive industry is parametrized tests like quick check so what you do is you take a dejected grammar of whatever your problem is and you attempt to shorten failures when you find them and one example is a canned bus for every or it's not car your network that's what I've used tend to call it my head so the idea is that you have messages that are being passed onto the network from different devices that come in and the CPU analyzes them to say hey I'm braking or something and the idea is that no matter which permutation these messages come in I want it to be in the same state if up to some

asynchronous condition and and so the idea is to have the CPU process like different permutations of these messages that come in and make sure that it always has the same result and so what you'll do is you usually write what's called a generator that generates phrases in this dejected grammar you have which in this case would be can bus messages and then after you've found one you also have something that's a shortener that takes that that that's snippet that you found and tries to somehow shorten it like do I have to call every single one of these can i you know eliminate this one in this one and it's basically it has a tree that

created this dejected grammar and you try to prune the tree in different ways to see if you can come up with a very human readable example which is very useful in brain complex systems so I guess I'm takeaways from this if you haven't learned rust at least learn how to do like a simple hello world in it just just write like a very small parser that like recognizes something very simple you know you really don't need that much to do safe code learn a couple of these parser libraries for whatever they are whether if it's antler if you're in Java land or a or hammer or Nam if you're in the C C++ world make

sure that you always run code coverage for your unit test that that's that's pretty important because you're getting that that content you're getting that con Kollek testing for free without the SMT solver because you as the human are putting in the inputs and also make sure you specify all resource bounds everywhere no matter what I always know your failure modes always know at what point this thing runs outta memory always know that I can only put integers up to a certain size into this datatype otherwise I have an air condition everything has to be bounded and for things that you don't have bounded at least put it in a black box with counters around it and walled off from

the operating system so it only can view certain calls and treat it like a black box yeah they need questions about any of these particular levers I tried not to put too much code in the presentation

like is anybody using much language space security stuff and they're as they're writing their applications today or yeah that's a problem and even for like your QA people that are doing like webdriver tests you can write yeah you can help them write webdriver tests to try to get grammars out of you know you know I want this field to have certain something I mean you could use a lot of these these fuzzing based techniques in webdriver if you wanted to I could especially look like the quickcheck stuff that's that's very useful for because because nobody wants to sit around and play with things by hand all day long and in web fields yeah we're still using 1970s C techniques it

shouldn't be a problem in 2017 I think it's more of just one that we don't always think about a lot of the code we write is parsing a grammar but we just usually don't think about it in that context because it doesn't seem like a grammar to us I mean we usually have some business modeling case that we associate with it but we don't actually think of it as that we're actually taking a context-free grammar of input and then doing something on it but we don't usually think about it I mean we take the compiler class and undergrad and we learn about finite state automata and context-free grammars and what you can and can't do with them but it never

gets taught in the engineering side which doesn't make sense and there are some things you can do on the IO - what one thing is just figure out the tape of your operating system calls it's the cheapest thing you can do you can do that in LLVM like if this thing is making an operating system call here's all the things that are tainted by it and so that you know what the taint is otherwise you have to use something like Haskell that you have like actual IO and the data type where were you as a programmer pass that around to every variable and say oh by the way this thing has IO it can come

from the outside world

reviews for this type of stuff in my in my CI system one of the ways was I mean you can just do like simple compiled checks to see if they're using unsafe calls I know there's a couple Santa static analysis tools out there they do it every day to get that ad sorry anyway yeah I mean you can take all of those calls that you know or unsafe parsers that are like like ASCII to integer and C and and make sure that they are only used in contexts that you know that you're always passing in something that's not going to break that dumb parser because because it's not like a like it that the way that ask you to

integer fails is undefined so yeah taking all of those make debug bills with a SAN and debug builds with a dejected G Lib C it's okay to link in your own G Lib C that has all kinds of stuff that's not not there or that's much safer than the actual G Lib C it's not gonna be as performant but it's gonna be a lot safer make sure you run all of those those taint analysis if you can make sure that you have code coverage that's like the easiest win it is this half code coverage on your unit tests [Music] yeah and use like buzzers and stuff every now and then just to just just the

act of getting the fuzzer around the code gets it into a state where other people can write other tests to it because because if you can't even set it up for a simple fuzzer it's hard for like one organization in town they have all their COBOL code locked up in this non git repository for all their mainframe stuff and nobody can get any modern tooling at it and it makes absolutely no sense so I mean you have to have your source code and your build systems there in a way where you've taken out all of the those credentials and stuff and move them out of the code so it doesn't matter who touches it and

so that you can get other teams putting those those modern tools around it like especially for stuff like like COBOL code or sequel also for Network stuff Tyler treat from workiva before he left he wrote a library called Comcast like the cable company and you can use that and it will inject both failure and latency in your network connections which is really nice so you can test your network code on the same box with simulated network degradation 'z and stuff without having to like actually deploy it on a full cluster which is nice if you don't have like one node available to you so I mean I can just like pop it out like I abuse AWS code

build for all kinds of stuff because it's essentially a fat lambda function that you can just call and demand and it has a bunch of different environments so I usually like to store all my my static stuff an s3 bucket it'll just you know read it all in apply any you know quick you know packages it needs to the Linux critical Colonel like oh I need this I need that just takes like two seconds since it's all hosted on Amazon and this kind of just run my my stuff usually like a fat code build instance for 90% of my stuff just just on one box but yeah make your make your CI system and that nice for external tooling on the

code and also have that that second like after you run your CI test make sure you actually take a meaningful subset of those tests it's not like you know hundreds of megabytes and commit those as a version also and so you can do bisection because because that's very very useful when you're trying to figure out okay which feature did I add that added this this unstability to my system or something or which feature did I add that I still haven't had tests around and I'll know exactly which which library came in and did that or which configuration changed came in and did that iiiii visibility

[Music] there's like team organization structure it usually helps to and for whatever reason you got these people from Lake I know the consultants like you must have a QA person you must have a person that's a developer you must have a person that's a business analyst you really don't need that but you really should probably have whoever writes the code has someone else on the team do the QA card for it it's like you know they do it they're done with the development and then some other developer who didn't touch that code you know at least assign them to do the code review and more than just code of you actually you know writing some more tests around it just

to the poke at it cuz you really have to poke at the code you can't just human read it that's helpful and also there's a lot of things you can do in the build system to but turn all your boarding flags on when you're compiling stuff there's there's a couple static analysis tools out there they are a little bit more robust than that but not many of them are very expressive because they make you like the Hewlett Packard will try is trying to sell you one you have to configure all these XML files for snippets of code that you don't like I'm trying to think if there's one called Puma I believe for c-sharp code that

uses the Rozlyn framework for their compiler that's written by a local guy in town and what he's doing is he's actually taking unsafe unsafe code patterns and just uh making a library of those and so every time you compile it's like oh you used this operating system call in the context of this which is usually unsafe and it would flag a warning and it does it very much at the language level where it is essentially writing a parser that's dejected the whole languages of c-sharp into all of c-sharp is okay except for this this this this and he's making more and more complex dejection z' of things that that result in warning so yeah you can definitely do

it at the language level if you have like like Rosslyn or the LV I'm toolchain if you're in in like seal and and there's also for Java there's the checker framework you can do a lot with the checker framework actually but you have to look at linking it as an extra jar in your compiler [Applause]