Can you fit 500M of rules into a firewall? - Boris Lytochkin - EuroBSDcon 2024

ladies and gentlemen quick Round of Applause for our next speaker Boris will be telling us about optimizing what large firewall rule sets y I'll be in the first row to first row row to troll you about it thank you Christoph uh at least two reasons why it is the best thing to to have an after party at the end of day one well the first reason is obvious it's always cruel to have an after party and the second one is not that obvious uh I'm not standing between you guys and the after party so I have some some time and give you a good need explanation about apfw techniques so uh how many people in the room are familiar with IP IPFW rule set just raise your hands okay IPFW lookup tables okay and uh table ARG from lookup tables oh yeah that's cool so I've submitted my work in April uh and it's September now so uh We've we've added 70 million of rules on top of that uh no breakage we are running okay uh so I had to change title a bit uh this is about one million times bigger rule Set uh than I wrote about 20 years ago when I was a student of physics department of Moscow State University back then uh I started really hard to improve my uh well improve my R set composition techniques so boom and I'm uh Yandex fellow I'm working as a network foran at Yandex I manage a small team of network Engineers that are responsible for every single Network in our campus and our warehouses uh we control the the management Network for our data centers and we do provide remote access to our corporate Network as well so uh let's take a look on the simplified diagram or our Network we have around uh 400 routers that are responsible for routing and filtering uh network uh access from users uh to the services of uh inside our corporate Network and the internet no matter if they are connected through the VPN or Wireless or through wire all of these servers are running FreeBSD that is why actually I'm standing here and uh this talk is a story about the firewall we are running on these servers a story of dynamic firewall so what are the properties of this firewall why we build it and how we build it the first thing uh it limits the whole traffic from the users uh to every single network uh either in corporate Network or the Internet it's combined uh with the old services that are uh needed for the users including DCP server uh array out advertisement for IPv6 we have a cach node for our internal streaming etc etc etc another very important property is that sometimes we run these routers and firewalls on very low power and almost silent servers so we need to keep our uh CPU footprint CPU requirements and green power something yeah uh at we very low levels and uh the main reason why we call this firewall Dynamic is that when a user connects to the network uh the firewall is configured for uh processing the user's traffic within 3 seconds let's take a look on the access rules how we do it uh what is inside and how we deal with it an access rule for dynamic firewall uh uses the user uh user notation from The Source because initially we don't not have any idea what are the user IP addresses the destination is usual it's a network prefix or domain name for the service either on the corporate Network or over in the net in the net let's talk about some challenges these thing arise we still want to use per user grity this is kind of new thing uh to the techniques that is common for the Enterprise firewalls so we do support per user or per group rules uh of any kind of any amount of that we do support uh the rule sets that are different uh if a user is connected through the VPN or through the wireless network within the offices we have some sensitive services that we know do not want to expose to the VPN we do run iv6 so we have a lot of AP addresses uh that are given out to users and they change frequently and one last but not least any user can roam to any office or switch to VPN network and it is totally okay to have it everywhere it want here or she wants so this is kind of another uh challenge to be solved we need to cut some Corners the first Corner we're going to cut uh we do support uh uh UDP and TCP only there's a way to support uh other protocols but so far we haven't seen any demand for that so TCP and UDP are enough you know most of the user most of the rules we have in our uh rule set are made for large groups especially large groups like all staff members and we can we will see how we deal with this to uh to save some RAM and CP usage and another thing that we don't not want uh all users to be loaded into firewall rule set we can load them on demand and when the user is disconnected unload the rules from the kernel let's take a look on the groups we have we have at the high level of the rules We compare we combine users uh like staff all the Departments uh or we can combine users uh based on their projects basically we have couple of couple more uh ways to group the group uh users into this kind of three view structure and all of these groups are are pretty much okay uh to be used in the rule set here's the sample rule we have in our database the rule uh tells us that the user number one the user one has access to the dev server using SSH HTTP and https and the percent Mark denotes that this just a user this is a group you group rule it allows all the soft members to the DNS cache and another rule uh is all about uh giving access for all the Developers to some Network for uh their project in green you see how the processor that is uh in charge of converting these rules into apfw uh unlocks on unpacks these rules given that simple explanation here's our numbers we have about uh 50,000 of rules running in our kernel we have 65 uh th000 users and it's growing both rules and users and if you combine the uh individual user accounts and the IP address destinations you will get that number that was on the on the title so 570 million of uh entries firewall entries in the rule set the first thing to think to fix Is How We Do conversion between user account that is in the rules and the IP address because firewall is all about IP addresses and network traffic not not that users to do that uh we can use a thing that is called Mark it was integrated into uh freeb the kernel couple of years ago and this is basically uh the very similar to F FW Mark uh you can take a in Linux kernel but we had added some tweaks for that so this is a 32bit number unsigned you can uh it is saved in an Boo and bo tag for each packet you can set it using IPFW uh set Mark action you can make a check with a mark action mark up code you can do a look up in lookup tables for that and the most valuable thing for me is every uh every time you use Mark you can mask out some bits so you can play with the uh Mark as a bit field value another thing we need to uh to be uh to use for the our f is lookup tables lookup tables can have different keys for ex we will be using address key and uh number key in this talk there are different algorithms uh that are supporting different type of keys and we use uh different value types so we when you uh do a lookup table then you can fetch a value from that and that will be uh that value will be used in table Arc this is basically what I asked about table Arc in the in the beginning so let's try uh to take these two parts together and configure our firewall converting this sample rule to the to the way we can uh we can load it into to the kernel first thing we need to do we need to create a table uh and that table would like would have would help us to convert a IP address into Mark in this example we somehow we know that user one uses IP address ending one with zero one ones and user four is using another one IP address so we load it into the table now now we have a table uh comprising two records and what we can do uh we can use set Mark when looking up a source IP address in the uh packet processing and then we are going to check it using the markup code so far so good because this is the real IPFW rule that you can install into the kernel it will work the problem is that you need a special tool or a special side car to track all user IP addresses and push these uh these mappings into into the kernel for this we've built a message queue uh the publisher for the for the messages are radio server and there are only two different types of messages message uh type number one it's a new map so user IP address and the way it is is connected to the network and the second message is flashing IP address the when the user is disconnected so uh we are able to convert all these rules into the row IP OFW format but we have some issues there so we have 50,000 rules uh we have like 120 million of ores when we are comparing marks and this is not going to have to be loaded into the kernel it's too big it's too slow and I don't like it besides that IPFW is rather slow when you're uh talking about adding or removing rules and well there are only 65,000 of drule numbers and we have like 50 50,000 rules already and we want uh some spare uh spare numbers for our static firewall or some to grow it so let's take a look on another differential it's in review state so if you have any ideas or comments just go to the uh fabricator and leave your opinion I think we'll be merging it uh in a uh in a week or so and that differential allows us to use 32bit R numbers yeah it should be enough at least for a couple of years but still uh evaluating these r sequentially one by one it's not an option for us because it's too it's way too slow to cope with this what we can do we can create a per user rule set or per user rule number push all the rul all the rules that applicable for the user into its rule set and that will gives us uh a drop in rul set count to around 13 uh 13,000 let's take take a look how we do it we've seen the first step uh on the previous slides we do a look up of the source IP address of the user and we Mark uh traffic with the mark assigned for each user as well then uh we need a another table that is U that is converting Mark of the user user into uh the rule number that that hosts all the users rule rules let's take a look on this so we have two user now two rules and we are going to convert them into apfw format the rule set for user one is pretty much simple we skip Source IP address here we Den note an any here because we've checked Source address when we were looking up uh Mark for the user forward rule set is AIT a bit more uh bigger here so two two rules and an example and now we need a glue to uh forward or to to drive the traffic uh check routine to these rule sets for that we create a numberto number table uh for the key we use Mark for the value we use skip to table skip to Value so the rule rule number of the user rule set so far so good Okay so we've converted 50,000 rules to 13,000 rules but it's not enough right it's way too long to check let's optimize it even further so this is a sample rule set of user we stripped out the source IP address because we've checked it and now we're going to uh put this rule set into another table we use uh prefix as a key and protocol and the port sequence as a Val as a value you cannot put uh protocol in ports uh to the table as is so we have a we have to have another uh another step involving these checks so we have the original procedure with the 13k of rules let's add some more steps instead of just assigning a user uh rule number we are going to add per user table and look up the prefix in this table and when we find find the match there we are going to check ports and protocols there let's take a look on this on this example so this is a small Ru rule set comprising two two fire two five firewall rules and we can load it into the radx tree the normal structure for prefixes but if we do it the way uh we used to do there's a problem if we make a look up in the table we are going to uh find a more specific prefix in the table in the radic and to make it right to filter the the traffic properly we need to pull all the protocols and ports down to the leaves of the tree so we take a uh TCP 22 port and push it down uh one level then we do the same thing for the next levels etc etc etc so at the bottom of the tree all the leaves have all the protocols and ports from the uh their parents this way we can do filtering uh with a single uh table lookup let's take a look how we do it first thing we need going to strip out the prefixes and we are going to rewrite protocol and port check without without any IP addresses we number them so we make an index for that and this allow us to create a user table let's take a look for that so this is a set of rules that check for protocol ports and this is the per user table as it should be written so we have prefix in the key and uh rule number to check protocol ports as a value and now we need a glue glue is simple take a destination IP address make a look up in the table and do skip to that allows us to convert the whole rule set to another structure we have not our 500 million of rules but we have 570 million of uh table entries in the firew rule set and we don't have that amount of rules in the rule set itself it's not that good but still it's it's a way to go that that was the one of the first implementations we were running in production it was like I think eight years ago so that was done and what we're going to do we're going to take a look how we can push the total amount of table entries down to do that we can we can remember that most of the rules are done for the big groups of users mostly the whole company uh and if you have a like 65,000 uh employees then these five rules will get us more than three 300,000 table entries and that is actually a thing uh to be optimized if we're talking about small group well it's still 25,000 entries and that's not an option for us to fix that what we're going to do we're going to convert the big groups the big uh the big groups that are referenced in the rule set into pseudo users well just just change the asra just add with a PR sign and now we have converted uh all all stuff PT all group into a user and DPT devs is also a user as well we left the project one group as a group so it will be expanded to the per user rule sets but okay we've done that we do not have any kind of way to reference the new sudo users we've created to the real users rule set to do that we need some Loops in the AP W um logic you canot write a for Loop there so we're going to use uh strictly written uh with the finite amount of Cycles so we we're going to spell it out uh rule set that allows us to check another user if we do not find found a match in the per user table or we you didn't find a match in the protocoling ports so we can go from the per user table or uh layer four decision block back to the user selection let's take a look how we do that first thing we we need to create a rule set for users including pseudo users this is a sample rule set for the pseudo user called dpto all this is a set of PR set of rules that is are that we need for configur the check checking protocols and ports here take a look on the last rules rule action for the real user and the pseudo users we use different thing we we use Deni for the real users and return next rule for the P sudo user let's let's do the rul set the first thing we need we are going to do we create a table Yeah table is uh is used to convert Mark to uh to real number for each real user okay now we create another table another table tells that user with this Mark uh should be checked again DPT all or other sudo user that is is uh when the user is a member of this group basically what we can do we can do as much uh tables as we want so we can add more pseudo users to uh real user rule set let's compile this all together we create a rule set that uh checks for the per user rules uh per user table we create a set of tables that are uh responsible for converting Mark to the rule set numbers to skip or to call and we need a special uh thing we call uh table Walker that is responsible for looking up Mark and choosing where to jump into the rule set that is the way basically how we converted all these entries down to 25 million of uh uh table entries in our all set and this is the VM start from real production server uh there are about 48,000 uh users loaded into the kernel and our Ru set takes about 2 GB of RAM uh there are yeah there are 17 million of TP entries there this technique has some limitations though uh one is obvious uh every time you want to add a pseudo user to uh user rule set you you are going to add an additional table R up and it will cost you some CPU power so you don't want to convert very small groups you want to convert only large groups to super uh to pseudo users here's some tips for you if you want to build this uh this kind of rule sets uh first thing to think about is to check one packet uh header item once so if you take a source IP address check it once assign a mark and use Mark afterwards as we know rul sets inserts and deletions uh as slow keep the rule sets as small as possible well we do have like one 100,000 of rules we consider it not that small firewall rule set but still keeping the firewall Ru set small with help of help of tables and you know what Mark rules use it any questions uh is your ipw hooked both on input and output or unhooked at One Direction uh this rule set is set on input input input so clear oh how long does it take to um uh uh rebuild this in memory from a cold boot um these days we use uh loading users on demand so the whole procedure from zero to uh IPFW is a capable of uh filtering the connected users is about 10 or 15 seconds how do you expire users out of the table is that also how do you expire users out of the table yep is that done by with radius as well or uh it can it could be done by radius uh you can track the user traffic and uh know that there is no traffic from user it can reload it unload it is it is radius used for 802.1x yep okay anyone else when you answered the question on the loading time uh you aren't doing this using IPFW from SLB IPFW right yeah uh what we do actually we push the T push the rules using this BFW but all the tables are loaded through the yoka tail are you using IPv6 exclusively uh not exclusively but we treat any network with IPv6 broken as broken um so you said you're only doing uh UDP and TCP how do you handle icmp because just dropping icmp can create some problems with IPv6 okay uh this is very simple we allow most of icmp without any Dynamic rules so this is kind of it was it is branching uh prior jumping into the dynamic firewall all right am I missing anyone going once going twice thank you very much for this presentation e for