SE513828C2 - Brandväggsapparat och metod för att kontrollera nätverksdatapakettrafik mellan interna och externa nätverk - Google Patents

Description

15 20 25 30 513 828 2 ket. Avsändare och destinationsadress, avsändar- och des- tinationsportar, protokollfält, flaggor och alternativ un- dersöks också och jämförs med en lista av brandväggsregler.

Beroende av vilken regel som matchar paketet kan brandväggen besluta om att inte vidarebefordra paketet, exempelvis om en blockeringsregel matchas.

Förutom obehörig access finns det andra hot som upp- kommer när en organisation år ansluten till internet.

Grunden är att man inte kan lita på data mottagen från okända avsändare. Avsökning efter virus och trojanska häs- tar i e-mail och på webbsidor är tjänster som utförs av några tidigare kända brandväggar.

Efter hand som nätverksbandbredden ökar blir dessutom prestanda hos brandväggarana en viktig uppgift.

Brandväggar kan arbeta på många olika nivåer och tillhandahåller olika sorters funktionalitet för att avsöka data som passerar dem. Den grundläggande funktionaliteten hos alla brandväggar är emellertid att utföra filtrering baserad på innehållet i nåtverks- (IP=Internet Protocol) och transport- (UDP, TCP=Transmission Control Protocol och ICMP=Internat Control Message Protocol) nivåhuvuden. Utan sådan IP-filtrering är all annan funktionlitet, såsom datasökning, oanvändbar, dvs användare av det interna nätverket kan likaväl konfigurera sina nät- verkstillämpningar att inte gå igenom scannern för att koppla upp till fjärrservrar och sålunda koppla förbi all säkerhetsfunktionalitet.

Företak eller organisationer är anslutna till inter- net av olika anledningar, exempelvis för att publicera in- formation om ett företag, dess produkter och tjänster på webben för tillgång till information tillgänglig på inter- net och korrespondera via e-mail.

Företaget har ofta intern information, som användare av internet inte skall kunna få tillgång till, såsom in- ternetinformationsservrar, filservrar etc. Den mest vanliga 10 15 20 25 30 35 513 828 3 konfigurationen medger uppkoppling från internet till en uppsättning servrar (webb, e-mail och andra publika servrar), men att neka till andra värdar (exempelvis in- tranetservrar). För att åstadkomma detta upprättas en "de- (DMZ). Uppkopplingar till datorer i DMZ kan göras från internet såväl som från intranet, men till- militariserad zon" gång till intranet från internet är begränsad. I tidigare kända nätverk är ett internt nätverk, såsom ett intranet, anslutet till den demilitariserade zonen via en brandvägg och DMZ är kopplad till internet via en router. Följakt- ligen kan nätverkstrafik passera fritt mellan internet och DMZ, som är fullständigt oskyddad från användare på inter- net. En anledning till detta är att tidigare kända brand- väggar också saknar möjligheten att ansluta fler än två nätverk - ett internt och ett externt nätverk.

Andra brandväggar har tre nätverksgränssnitt. Här kan begränsningar göras med avseende på trafik mellan internet och DMZ såväl som intranet. Några begränsningar görs för trafiken till och från värdarna i DMZ, exempelvis över webbservern endast access till HTTP- (Hypertext Transfer Protocol) porten. Internetanvändare skall inte kunna ansluta sig till någon annan service. Användare på internet kan emellertid vilja få tillgång till webbservern på fler sätt än internetanvändarna för administrativa ändamål, sålunda skall mer access beviljas mellan dessa två nätverk.

Liknande regler behövs för e-mailservern; SMTP- (Simple Mail Transfer Protocol) anslutningar skall tillåtas från internet, men att läsa mail skall endast vara möjligt för vissa tillåtna värdar på intranet och möjligen också från någon värd på internet.

I en brandväggsmiljö är antalet maskiner i DMZ exem- pelvis 30. Reglerna för maskinerna i DMZ kan vara olika för varje maskin, men antalet regler per maskin är tämligen lågt, exempelvis 10-15. Fler regler kan tillämpas på trafik från intranet till DMZ, men dessa är sannolikt mera 10 15 20 25 30 513 828 4 generella. Ett tämligen litet antal regler är sålunda gil- tiga för alla maskiner i DMZ.

Regler avseende trafik mellan internet och intranet är dessutom i de flesta fall få, om några alls. Den mesta trafiken skall blockeras. Trafik initierad från intranet kan emellertid tillåtas.

Då antalet användare av internet växer kommer de publika servrarna att besökas mera frekvent, vilket orsakar mera trafik. Trafiken till och från intranet ökar då intranetanvändarna tar del i den ökade mängden information som är tillgänglig på internet. Följaktligen ökar band- breddskraven. Detta ställer större krav på prestanda hos de använda brandväggarna.

Huvuduppgiften för en brandvägg är paketfiltrering, dvs givet ett IP-paket och en uppsättning regler, vilken regel skall då tillämpas på detta paket? Om flera regler matchar samma paket krävs att en policy definieras för att specificera vilken regel som skall tas. Det finns två ti- digare kända lösningar till detta problem. En lösning är att ta den regel som matchar flest antal fält hos paketet, och om två regler matchar samma antal fält, men olika så- dana, krävs att en ordning specificeras mellan dem. Detta används i paketklassificeringsalgoritmen av Borg och Flo- din, Born, N. Flodin, Malin, paketklassificering, juni 1997; borg, N., Masters Lic., Luleå Tekniska Högskola, februari 1998. En A Packet Classifier for IP Networks, annan lösning är att definiera en ordning mellan reglerna och använda den ordningen för att definiera vilka regler som skall tas. En fördel med den andra lösningen är att den ger bättre flexibilitet vid definiering av filterregler, och NetBSD-brandväggskoden använder denna metod.

En filterregel innefattar en uppsättning kriterier som skall uppfyllas och en funktion som skall utföras när de är uppfyllda. Kriterierna är baserade pà IP-avsändar- och destinationsadresser (32-bitars prefix), IP-protokoll- W 15 20 25 30 35 513 828 5 fält (8-bitars heltal), huruvida eller inte paketet har IP- alternativ satta och vad dessa alternativ är (heltal), UDP/TCP-avsändar- och destinationsportnummer (2 16-bitars heltalsområden), TCP-startflaggor (3 bitar), ICMP-startfält och kodfält (2 8-bitars heltal), vilket gränssnitt paketet lästes från (8 + 8 bitar) och vilket gränssnitt paketet skall skickas vidare till (8 + 8 bitar).

De flesta av dagens brandväggar inriktar sig inte speciellt på regelmatchningsproblemet. Det är vanligt att ha en länkad lista (eller en vektor) med regler, som jämför paketet med var och en av dessa ända tills en matchning hittas. Detta är emellertid inte effektivt. Ett annat sätt att angripa är hashing av reglerna. Om metoden att lösa tvetydigheter bland reglerna, dvs två regler matchar samma paket, löser dessutom de flesta implementationer problemet genom att definiera den första eller sista matchningsregeln så som den som skall följas.

En tidigare känd brandvägg, PIX-brandväggen av Cisco Systems, är en kopplingsorienterad säkerhetsanordning som skyddar ett internt nätverk från ett externt nätverk. PIX- brandväggen är en mycket dyr anordning och den har en övre gräns av omkring 16 OQO samtidiga förbindelser. Huvuddelen av PIX-brandväggen är ett skyddsschema baserat på den adaptiva säkerhetsalgoritmen (ASA The Adaptive Security Algorithm), som tillhandahåller en fastställd kopplings- orienterad säkerhet. ASA spårar avsändar- och destina- tionsadressen, TCP-sekvensnummer, portnummer och ytterlig- are TCP-flaggor hos varje paket. Denna information lagras i en tabell och alla ingående och utgående paket jämförs mot ingångar i tabellen. Information hos varje etablerad uppkoppling måste sålunda lagras under förbindelsens livs- tid och antalet möjliga förbindelser definieras sålunda av den tillgängliga minneskapaciteten. En fullständigt laddad Cisco-PIX-brandvägg kan hantera omkring 90 Mbit/s. Ciscos_ PIX-brandvägg stödjer emellertid också portadressöversätt- 20 25 30 35 513 828 ning (PAT=Port Address Translation), varvid fler än 64 000 interna värdar kan servas av en enkel extern adress.

Ett tidigare känt paketfilter kallat ipf (IP-filter) är inkluderat i standardversionen av net BSD 1.3.

Regeluppsättningarna i ipf delas upp på gränssnitten, på vilka de är giltiga. Dessutom kontrolleras reglerna två gånger, först när paketet kommer in i värddatorn och sedan när det lämnar värddatorn. Regler som endast är giltiga för inkommande paket adderas inte till listan som kontrolleras vid utgångsporten och vice versa. Datastrukturen är huvudsakligen en optimerad länkad lista.

Exokernel, Engler, D., Kaashoek, M.F., Exokernel: An Operating System Architecture..., Proceedings of the 15” ACM Symposium on Operating System Principles, December 1995, använder ett annat angreppssätt för att O'Tool Jr, J., hantera paketdemultiplexering kallat DPF, Angler, D., Kaashoek, M.F., DPF: Fast, Flexible Message Demultip- lexing..., Engler, D., Kaashoek, M.F., Computer Communica- tions Review, Vo. 26, No. 4, Oktober 1996. Reglerna skrivs i ett speciellt programmeringsspråk och kompileras däref- ter. Kompilatorn vet om alla specificerade regler, varvid den genererade koden kan optimeras för de förväntade tra- fikmönstren.

Uppfinningen Det är ett ändamål med föreliggande uppfinning att tillhandahålla en förbättrad brandväggsapparat och en metod för att kontrollera nätverkstrafiken mellan interna och externa nätverk, som tillhandahåller en effektiv adressuppslagnings- och regelmatchningsprocess för att åstadkomma en effektiv och snabb IP-paketsfiltrering och ett obegränsat antal möjliga förbindelser genom brand- väggen.

Detta àstadkoms med brandväggsapparaten och metoden enligt uppfinningen, varvid uppsättningen regler som behö- 10 15 20 25 30 513 828 ver sökas igenom linjärt är reducerad genom segmentering av regeluppsättningen. Brandväggen enligt uppfinningen in- nefattar organ för 2-dimensionell adressuppslagning, som utför en tvåstegsuppslagning, först av avsändar- och des- tinationsadresser hos paketet i en uppsättning adresspre- fix. Varje prefix är associerat med en delmängd av regler av en total uppsättning regler. En linjär sökning utförs i den resulterande delmängden av regler för att hitta den regel som är tillämplig på det aktuella paketet.

Ett annat ändamål med uppfinningen är att tillhanda- hålla en fragmentmaskin, vilken fragmenterar paket, som är för stora för att hanteras så som de är.

Ytterligare ett ändamål med uppfinningen är att tillhandahålla nätverksadressöversättningsorgan, som över- sätter interna avsåndaradresser till externa avsändar- adresser för ett paket som överförs från ett internt nät- verk till ett externt nätverk, eller externa avsändar- adresser till interna avsåndaradresser för ett paket som överförs från det externa nätverket till det interna nät- verket.

Ytterligare ett ändamål med uppfinningen är att tillhandahålla hålslagningsorgan, som utför ett temporärt undantag från en extern till intern blockeringsregel för en förbindelse initierad från det interna nätverket, varvid en återkopplad kanal för paket överförda från det externa nätverket till det interna nätverket etableras genom brandväggen.

Ett ytterligare ändamål med uppfinningen är att tillhandahålla en brandvägg, som kan hantera åtminstone 1 000 unika regler. Fördelen med brandväggen och metoden enligt föreliggande uppfinning är det obegränsade antalet möjliga samtidiga förbindelser, den snabba IP-filtreringen och det stora antalet möjliga regler som stöds. 10 15 20 25 30 513 828 8 Ytterligare ett ändamål med brandväggen enligt upp- finningen är att tillhandahålla en brandvägg innefattande en rOuter .

Kort beskrivning av ritningarna För att förklara uppfinningen mera i detalj och för- delarna och kännetecknen med uppfinningen, kommer före- dragna utföringsformer att beskrivas i detalj nedan, med hänvisning till de bifogade ritningarna, pà vilka FIG 1 visar en vanlig nätverkstopologi, innefattande brandväggen enligt uppfinningen, FIG 2 är ett blockdiagram av brandväggen enligt upp- finningen, FIG 3 är en illustrativ vy av en del av en 2-dimen- sionell tät chunk, FIG 4 är en illustrativ vy av datastrukturen enligt uppfinningen, FIG 5 är en illustrativ vy av en klass (0,0) platta, FIG 6 är en illustrativ vy av en klass (1,1) platta, FIG 7 är en illustrativ vy av en klass (1,2) platta, FIG 8 är en illustrativ vy av en klass (2,1) platta, FIG 9 är en illustrativ vy av en klass (1,3+) platta, FIG 10 är en illustrativ vy av en klass (3+,1) platta, FIG 11 är en illustrativ vy av en klass (2+,2+) platta, FIG 12 visar ett exempel på en lyckad sökning för en speciell frågenyckel i ett Patricia-träd innefattande sex nycklar, och FIG 13 visar Patricia-trädet, sättning av frågenycklar från den lyckade sökningen enligt som en följd av en in- FIG 12.

N U 20 25 30 513 828 9 Detaljerad beskrivning av uppfinningen Ett exempel på en modern nättopologi från ett före- tags eller en organisations synvinkel visas i FIG 1. Ett internt nätverk 1, såsom ett intranet innefattar flera nätverksnoder 2 såsom persondatorer, arbetsstationer, fil- servrar etc, som är kopplade till en brandvägg 3. Företag eller organisationer kopplade till ett externt nätverk 4 (internet) avsett att publicera företagsrelaterad informa- tion, såsom produkter och tjänster, på webben, får tillgång till information publicerad av andra företag eller organisationer på internet och korrespondera via e-mail.

Företaget kan emellertid ha intern information, som använ- dare på internet inte har tillåtelse att få tillgång till, exempelvis information tillgänglig via intranetinforma- tionsservrar, filservrar etc. För att tillåta internet- användare att få tillgång till information tillåts de koppla upp sig mot en begränsad uppsättning servrar, exem- pelvis webb, e-mail etc och förhindra dem att nå informa- tion på andra värddatorer, såsom intranetservrar. De publika servrarna är tillgängliga i en “demilitariserad (DMZ) 5, gen 3 är dessutom kopplad till internet via en router 6 och zon" som är kopplad till brandväggen 3. Brandväg- förbindelser till noder i DMZ 5 kan sålunda göras från det externa nätverket eller internet 4 såväl som från intranet l, men åtkomst till intranet 1 från internet 4 är begränsad.

I den följande beskrivningen tillhandahålls ett flertal specifika detaljer för att ge en mera grundläggande beskrivning av föreliggande uppfinning. Det skall vara uppenbart för fackmannen inom området att föreliggande uppfinning kan realiseras utan dessa specifika detaljer.

Några välkända egenskaper är inte beskrivna i detalj för att inte göra uppfinningen oklar.

W U 20 25 30 513 828 lO En utföringsform av brandväggen och de olika modu- lerna i den snabba vägen och hur de filtrerade paketen flyter genom enligt uppfinningen visas i FIG 2.

I ett enkelt fall tas paket emot från ett nätverk 1, 4 eller 5 via en brandväggsingångsanslutning 7 och an- bringas på utgången hos det 2-dimensionella adressupp- slagsorganet eller ett 2d-SFT-block 8. En mellanliggande förbindelse 9 förbinder 2d-SFT- och regelmatchningsorganet eller block 10, varvid paketet antingen passerar (ner) el- ler blockeras b5. För att kunna fungera ordentligt har brandväggen enligt föreliggande uppfinning emellertid ett antal ytterligare moduler.

I denna utföringsform utförs ett uppslag av avsän- daradress och destinationsadress i 2d-SFT-blocket 8, vilket resulterar i en regel eller i själva verket en kort lista med regler. Regellistan finns kvar i regelmatchningsblocket 10 ända tills listan söks igenom och en matchande regel hittas.

Dessutom genereras information om paketet kan behöva bearbetas av andra moduler eller inte genom 2d-SFT-uppsla- get. Några av dessa beslut tas under regelmatchningen, vilket innebär att regelmatchningen i realiteten börjar 2d-SFT- innan det når blocket, så som illustreras i FIG 2. blocket 8 beskrivs i detalj nedan.

När ett paket är för stort för att skickas över en länk, fragmenteras det i en fragmenteringsapparat eller - maskin ll. Detta innebär att allt som följer IP-startfältet delas upp i delar (fragment) och varje fragment förses med sitt eget IP-startfält. Fragmentflaggan och fragmentoff- seten sätts i varje fragment för att indikera om det är det sista fragmentet eller inte och för att registrera var data hos fragmentet passar in i original- (ofragmenterat) paketet. Dessa fält kontrolleras för att bestämma om pake- tet skall matas till ingången il - kopplad till anslut- ningen 7 - hos fragmentmaskinen ll eller inte.

W Ü 20 25 30 35 513 828 ll När ett paket är fragmenterat innehåller endast det första fragmentet, fragmentstartfältet, transportstartfâl- tet (TCP~, UDP- eller ICMP-startfältet). Detta innebär att de följande fragmenten inte kan matchas mot en regel som exempelvis innefattar portar.

Fragmentmaskinen ll samlar fragment från varje frag- menterat paket ända tills fragmentstartfältet tas emot (fragment kommer nödvändigtvis inte fram i ordning). De- larna av informationen som endast presenteras i fragment- startfältet lagras sedan i den med det fragmenterade pake- tet associerade ingången, och de insamlade fragmenten matas till utgången ol, kopplad till anslutningen 7, med fragmentstartfältet först. Varje fragment som överförs från fragmentmaskinen matas med fragmentstartfältsinformationen, så att den kan bearbetas av filtret precis som att det var ett ej fragmenterat paket.

När alla fragment hos ett fragmenterat paket har ta- gits emot i fragmentmaskinen ll tas ingången eller fältet för paketet bort.

Vid några punkter kan fragmentmaskinen också besluta om att blockera fragment. Detta inträffar när fragmenterade paket anländer (möjligen såsom en följd av en attack), om antalet insamlade fragment överstiger en viss nivå eller helt enkelt såsom en följd av skräpminnessamling (gamla ingångar tas bort för att göra plats för nya).

Nätverksadressöversättning (NAT=Network Address Translation) används vanligtvis när ett företag har ett nätverk med många interna IP-adresser och endast ett fåtal externa (riktiga) IP-adresser. Några delar av IP-adress- rymden är reserverade för interna adresser, såsom l0.*.*.*, l92.l68.*.* Och l72.16.*.*. användas i interna/privata nätverk. De måste emellertid Dessa adresser kan fritt inte vara synliga på det externa. Brandväggen sätts därför upp för att översätta interna avsändaradresser till externa avsändaradresser då paket går från det interna till ett 10 15 20 25 30 513 828 12 externt nätverk. För paket som går i den andra riktningen översätts den externa destinationsadressen till en intern adress då paketen går igenom brandväggen. För att avbilda många interna adresser på ett fåtal externa adresser används även portar.

Exempelvis sätts brandväggen upp för att avbilda in- terna adresser från 10.l.0.0 till lO.l.255.255 (2“ adres- ser) till externa adresser l94.22.l87.0 till l94.22.l87.255 (28 adresser) genom att använda portar 20 000 till 20 255 (28 portar).

När en förbindelse initieras från l0.l.l.l port 4 000 till l30.240.64.46 port 6 000, tas en adress a och en port p, så att (a,p) inte kolliderar med någon annan NAT- förbindelse, från adress- och portområdet. Hos varje utgående, internt till externt (I2X), paket från den för- bindelsen byts avsändaradressen 10.1.l.l och port 4 000 mot a respektive p. För varje inkommande, externt till internt (X2I), paket byts destinationsadressen a och port p mot 10 1.1.1 respektive 4 000.

På detta viset kan de 256 externa adresserna till- sammans med de 256 portarna representera 65 536 adresser hos det interna nätverket.

Som en följd från 2d-SFT-uppslaget åstadkoms också information om ett paket är föremål för en extern till in- tern adressöversättning, och paketet matas till ingången i2 hos ett X2I-NAT-block 12, som utför den externa till interna adressöversättningen. Därför tas administrationen för att utföra X2I-NAT-uppslaget bort från alla paket som inte kräver översättning. För paket där X2I-NAT-uppslaget utförs skickas paketen till ett långsamvägsorgan 13 via sin långsamvägsutgång s2 i felfallet, eftersom uppdateringar av NAT-datastrukturen hanteras däri. När ett lyckat X2I-NAT- uppslag utförs ändras adress och portar och en re- gelmatchning för det nya avsändar-destinationsparet återfås 10 20 25 30 513 828 13 innan paketet skickas till nästa filtreringssteg via sin utgång o2.

Såsom ett resultat från 2d-SFT-uppslaget eller från X2I-NAT-uppslaget är det också klart om paketet är föremål för intern till extern (I2X) adressöversättning. Detta ut- förs huvudsakligen på samma sätt som X2I-NAT, men utförs som det sista filtreringssteget. Ett paket som är föremål för intern till extern (I2X) adressöversättning mottaget från utgångsanslutningen 15 hos regelmatchningsblocket 10 överförs till ingången i5 hos ett I2X-NAT-block 14, vilket utför den interna till externa adressöversättningen. För paket där I2X-NAT-uppslaget är utfört skickas paketen till långsamvägsorganet 13 via sin långsamvägsutgång s5 i fel- fallet, eftersom uppdateringar av NAT-datastrukturen tas hand om däri. När ett lyckat I2X-NAT-uppslag utförs ändras adress och portar och paketet överförs till det lämpliga nätverket via sin utgång o2 och utgångsanslutningen 15.

Anledningen till att ha X2I-NAT som det första steget efter 2d-SFT-uppslaget och I2X-NAT som det sista steget är att filtreringsreglerna ges med hänvisning till interna adresser, som är fasta, och inte NAT-adresser, vilka tilldelas dynamiskt.

Den mesta trafiken som går från ett externa nätverk till ett internt nätverk 1 blockeras vanligtvis för att skydda det interna nätverket. Värddatorer i det interna nätverket tillåts emellertid vanligtvis att komma åt värd- datorer i det externa nätverket 4. För att ta emot någon âtergående trafik från det externa, mäste ett temporärt undantag från den externa till interna blockeringsregeln göras för förbindelser initierade från det interna nätver- ket. Detta benämns hälslagning (HP=Hole Punching), dvs ett hål för att skicka tillbaka paket slås genom brandväggen.

Hålet existerar endast under förbindelsens livslängd och påverkar endast paket från förbindelsen. w U 20 25 30 513 828 l4 Hålslagning håller också reda på TCP-sekvensnummer för att skydda hålslagsförbindelserna från att "kapas". Det är därför nödvändigt att både utföra HP-uppslag för (I2X) paket, utförda av ett I2X-HP-block 16, och ingående (X2I) paket, utförda av ett X2I-HP-block 17.

Såsom ett resultat från 2d-SFT-uppslaget eller från utgående X2I-NAT-uppslaget vet vi om paketet är föremål för intern (I2X) (X2I) ning. Detta innebär att vi kan undvika administrationen till extern eller extern till intern hålslag- från att utföra HP-uppslagning för paket, som inte kan vara föremål för hålslagning. Ett utgående paket som är föremål för hålslagning matas till ingången I3 hos I2X-HP-blocket 16, samt protokollet låses upp för att hitta ett existerande varvid avsändar- och destinationsadresser och -portar tillstånd. Om inget sådant tillstånd existerar skickas paketet till långsamvägsorganet 13 via sin lång- samvägsutgång s3, varvid HP-datastrukturen uppdateras och ett tillstånd skapas. Om ett matchningstillstånd hittas uppdateras det innan paketet skickas till nästa filtre- ringssteg via en annan utgång o3.

X2I-HP utförs på samma sätt. Ett utgående paket som är föremål för hålslagning matas till en ingång i4 hos X2I- HP-blocket 17, varvid avsändar- och destinationsadresser och -portar samt protokoll låses upp för att hitta ett existerande tillstånd. Om inget sådant tillstånd existerar har ett försök att sända paketet via ett existerande hål i en blockerande regel gjorts och paketet blockeras vid sin utgång b4. Om matchningstillståndet hittas uppdateras det innan paketet sänds till nästa filtreringssteg via en annan utgång 04.

Genom att återigen hänvisa till 2dSFT-blocket 8 i beroende av innehållet i datafälten hos ett data- paket, som överförs mellan nätverken, en regel tillämplig på datapaketet från en fullständig uppsättning av regler, varvid paketet blockeras eller skickas vidare genom brand- väljs, 10 15 20 25 30 515 828 15 väggen. För att reducera uppsättningen regler, som skall sökas igenom linjärt, segmenteras regeluppsättningen. En- ligt uppfinningen utförs detta medelst ett 2-dimensionellt uppslag av avsändar- och destinationsadresserna hos paketet i en uppsättning adressprefix, varvid varje prefix har en deluppsättning med regler från den fullständiga upp- sättningen av regler, för att hitta ett med avsändar- och destinationsadresserna associerat prefix. Baserat på inne- hållet i datafälten utförs sedan en regelmatchning av re- gelmatchningsorganet 10 för att finna den på datapaketet tillämpliga regeln.

Vid utförandet av det 2-dimensionella uppslaget av adressen ses varje regel som om den täcker en rektangulär yta av ett tvådimensionellt plan, varvid offseten och storleken hos rektangeln bestäms av adressprefixen och prefixlängderna. Uppslaget betraktas sålunda vara samma problem som att finna rektangeln som omger en punkt i ett plan. För att förenkla uppslaget görs en begränsning för att säkerställa att varje punkt i planet täcks av en och endast en rektangel, vilket leder till en enklara upp- slagsprocedur.

Efter att det 2-dimensionella adressuppslaget är ut- fört fortsätter uppslaget med en resulterande uppsättning av regler associerade med det funna aktuella prefixet.

Adressfälten används emellertid inte i den slutgiltiga re- gelmatchningen. Om regeln sälunda inte är giltig för adresserna hos det aktuella paketet är den inte i listan med regler som följer av adressuppslaget.

Eftersom varje regel representeras av en rektangel, vilken täcker en del av den totala adressrymden och flera regler kan tillämpas på samma adresser, kan rektanglarna överlappa. För att få metoden enligt uppfinningen att fun- gera på ett riktigt sätt tillåts emellertid inte överlap- pande rektanglar. För att uppfylla kriteriet för icke- överlappning måste följaktligen följande steg utföras: W 20 25 30 513 828 16 1. För varje regel skapa rektangeln i adressrymden. 2. Skapa en uppsättning, som innefattar endast den nyligen skapade rektangeln. Denna uppsättning skall kallas jämförelseuppsättningen. 3. För varje rektangel som redan finns i planet; jämför den med varje rektangel i jämförelseuppsättningen. 4. Om de överlappar, skär ut de icke-överlappande delarna. Regellistan med överlappande delar tilldelas re- geln från den vid slutet tillagda nya rektangeln. 5. För alla delar - om delen av en del av rektangeln som redan fanns i planet - återlämna den till planet. Om inte så lägg till den till uppsättningen av rektanglar för jämförelse. 6. Om jämförelseuppsättningen inte är tom återgå till steg 3. Rektanglar som redan finns i planet och redan har jämförts kan utelämnas. 7. I detta tillstånd är jämförelsemängden tom. Om några rektanglar överlappade den nya delas de upp i mindre delar om så behövs, med de gemensamma delarna med regel- listor innehållande den nya regeln.

I en annan metod för att uppfylla kriteriet för icke- överlappning finns det inte bara en uppsättning rektanglar i planet. Istället innehåller varje rektangel avskilt från sitt koordinat- och regellistindex, en uppsättning rektanglar eller underrektanglar. Var och en av un- derrektanglarna har en ytterligare uppsättning av under- rektanglar. Ibland är det emellertid nödvändigt att refe- rera till samma underrektangel och att gå igenom en riktad acyklisk graf (DAG=Directed Acyclic Graph) för rektangel- djupet.

Det finns alltid en rotrektangel, som täcker hela planet. Denna representerar startdata att följa om all an- nan jämförelse felar. Regelfunktionen är antingen blockerat eller tillåtet att passera beroende på konfigurationen. 10 15 20 25 30 513 828 17 En rektangel kallad rot är rotrektangeln, till vilken en rektangel ny skall läggas till.

Om rot- och nyrektanglarna har samma storlek läggs reglerna i den nya rektangeln till regellistan associerad med rotrektangeln.

Iterera över alla underrektanglar till rotrektangeln.

Om den nya rektangeln fullständigt kan täckas av någon av dessa, gör ett rekursivt anrop med underrektangeln såsom rot istället och återgår sedan.

Iterera ännu en gång över alla underrektanglar i rotrektangeln.

Om en underrektangel fullständigt kan inrymmas i den nya rektangeln flyttas den från rotrektangeln till den nya rektangeln. Regellistan för underrektangeln och alla rek- tanglar under den behöver modifieras för att regeln för den nya rektangeln också.

Om underrektangeln skär den nya rektangeln skapas en ny rektangel innefattande den gemensamma delen för båda.

Regellistan för den skärande rektangeln är en kombination av de ursprungliga. Den nya rektangeln läggs sedan till båda de ursprungliga underrektanglarna och den nya rek- tangeln.

När alla rektanglar har lagts till DAG kan grafen gås igenom och listan med prefixdefinierade rektanglar, som behövs för den tvådimensionella uppslagsbyggkoden, kan produceras. Snittrektangeln kommer att vara en riktig pre- fixdefinierad rektangel, men resten av den omgivande rek- tangeln efter att underrektanglarna har skurits bort kan inte ordentligt definieras av prefix.

När datastrukturen används för att filtrera uppslag enligt vad som beskrivits ovan görs uppslaget i två steg.

Först utförs ett 2-dimensionellt adressuppslag, som leder till ett heltal. Detta heltal är ett index till en vektor med regler, varvid varje regel specificerar vilka fält som 10 15 20 25 30 513 828 l8 skall jämföras och vilken funktion som skall utföras om en matchning hittades.

Varje regel har ett nästafält, som indikerar med vilken regel man skall fortsätta i det fall man inte hittar någon matchning. Traverseringen av regellistan fortsätter tills en matchning hittas, och när ordentliga åtgärder vidtas för att blockera eller skicka vidare paketet.

Det 2-dimensionella prefixproblemet löses enligt följande.

Adressutrymmet eller universum U är en 2-dimensionell rymd innefattande heltalspar (s,d), som satisfierar: O S s < 232, S d < 232.

En undermängd R av U satisfierar: (s,d) e R om soí s < sl, doš d< dl, varvid (s0,d°),( s1,d1)e U kallas en rek- tangel. Vidare definierar punktparet [(so,d°),( s1,dQ] unikt R.

En rektangel definierad av [(s0,d0),( s1,d1)], där sl- so = 51-2” * ks = 2” Qch dl-do = dl-zid * kd= 2” för något icke negative heltal is,id,ks, och kd kallas ett prefix.

Givet en punkt (s,d) = {P1,P2,...,Pn}, så att P en delmängd av U, varvid det 2- dimensionella prefixmatchningsproblemet är problemet att (s,d) Avsändardestinationsdelen av brandväggsfiltrerings- e U och en uppsättning prefix P beräkna i så att e Pr problemet representeras såsom ett 2~dimensionellt prefix- matchningsproblem, där mängden P uppnås genom att konver- tera vägvalstabellen och filtreringsreglerna till en par- tition av prefix. Eftersom varje paket som skall filtreras kräver en prefixmatchning blir det nödvändigt att hitta en representation för P, så att prefixmatchningen kan beräknas effektivt.

Ett antal prefix, som partitionerar ett mindre 32 x 32 bitars universum visas i FIG 3. Svarta kvadrater 18 re- presenterar satta bitar (representanter) och vita kvadrater 10 15 20 25 30 35 513 828 19 19 representerar icke satta bitar. Notera: punkt (0,0) är placerad i det övre vänstra hörnet i FIG 3.

För varje prefix P = [(sWcL),(s1,dQ] e P väljs punk- ten (s0,d°) såsom en representant för P. Låt dessutom p = {p1, p2,. .,p,,} = {(s1,d1),(s2,d,),...,(s,,,d,,)} beteckna uppsättningen representanter för prefixen i P. (sd,dJ så att sd 2 s och da 2 d, (s,d), Givet en punkt e U, är för varje (s,d) e U, (sd,dd) en dominerande punkt över eller alternativt, (s,d) domineras av (sd,dQ .

Givet ett punktpar (s1,d1),(s2,d2) e U ges avståndet mellan de två punkterna under normen Lw av: Nu givet en punkt p=(s,d) är problemet att hitta det matchande prefixet i P ekvivalent med problemet att hitta den närmast dominerande punkten p i p under normen Lw, dvs den dominerande punkten av på e p av p, som minimerar Læ- avståndet mellan pi och p. Det är sålunda tillräckligt att representera endast de dominerande punkterna istället för själva prefixen.

Enligt vad som visas i FIG 4 är mängden p begrepps- mässigt representerad såsom en 232x 2” punkters bitmatris, där bit p är en mängd om p e p. För att reducera den er- forderliga rymden för representationen, representerar vi i realiteten p såsom ett fyra nivåers 2“8-träd. Varje nivå är (återigen) begreppsmässigt representerad såsom en 28x 28 (s,d) dominerande punkt i underträdet under. Det vill säga på (s,d) frånvaron av en dominerande punkt i rektangeln [<22“*s,22“*d), (22“**(s+1), 2*^** Den aktuella representationen av en nivå är en 2-di- bitars bitmatris, där bit är satt om det finns en nivå 1 (toppnivän) representerar bit närvaron eller mensionell tät chunk eller bara en 2d-chunk. Hur och när en nivå kan representeras en l-dimensionell tät chunk dis- 10 15 20 25 30 35 513 828 20 kuteras senare. En 2d-chunk utgörs av 32 x 32 plattor, där varje platta representerar 8 x 8 bitar. Eftersom punkterna, som definierar en platta, är dominerande punkter av prefix, är inte alla 2“ olika plattor möjliga. Vi inför en begränsning på plattorna, så att endast 677 olika sorter är möjliga.

Om det finns en punkt i en platta T (en punkt i någon av underuniversumen representerade av en av bitarna i plattan) med sin närmaste dominerande punkt i en annan platta Td, så har alla punkter i T deras närmast domine- rande punkter i Td. Definitionen av en dominerande punkt utvidgas till en dominerande platta. Den dominerande plat- tan Td kallas en dominerande platta för T, eller alterna- tivt plattan T domineras av plattan Td.

För att uppfylla kravet hos den tidigare definitionen behölls följande lemma.

Om P = [(s0,d0),( s1,dQ] är ett prefix, som satisfie- rar sl-s0>l, är då [(s°,d°),( s°+2i,dQ] och [(s0+2i,dQ ,( s1,dQ], varvid s¿1%=2i för något icke negativt heltal i, också prefix. Lemmat för den andra dimensionen är symme- trisk.

Genom lemmat ovan kan ett prefix delas i två delar när så krävs. Givet en uppsättning prefix Pdnæd represen- tanter i plattan Td kan vi sålunda upprepat dela upp dem ända tills alla prefix har sina ändpunkter i samma platta, i båda dimensionerna, för att uppfylla ovan nämnda krav.

Detta kallas plattdelning och är en avgörande del av kon- struktionen av täta 2d-chunkar.

De olika sorternas plattor delas in i sju klasser visade i FIG 5-11. För varje klass visas en platta såsom en vit matris (asterisker representerar bitar som kan vara antingen O eller 1). För varje bit som är satt ( ej *) och plattklass finns det också linjer, som indikerar de garan- terade gränserna för undermängderna dominerade av den biten (punkten). Notera att en satt bit i en platta typiskt kan 10 15 20 25 30 35 513 828 21 dominera punkter i andra plattor till höger och/eller under. Vi ger också antalet olika sorters plattor i klassen och skiljer mellan naturliga eller begränsade plattklasser.

Slutligen beskriver vi hur plattorna representeras/kodas i den täta 2d-chunken.

En klass (0, 0) platta visas i FIG 5. Ingen bit är satt: naturlig, 1 sort, och alltid dominerad av en platta Td från klass (1, 1), (1, 2), (2, 1), (1, 3+) (3+, 1). Att hitta en dominerande punkt för en punkt i bit (sb,d%) hitta den dominerande punkten för den motsvarande punkten i eller i en klass (O, 0) platta är exakt detsamma som att bit (sb,db) hos sin dominerande platta Td. En klass (O, O) platta kan sålunda, och skall, alltid kodas exakt på samma sätt som sin dominerande platta Tw En klass (1, 1) naturlig, platta visas i FIG 6. En bit är satt: 1 sort och dominerar möjligtvis (0, O) plattor till höger och/eller under. Eftersom alla punkter inom denna platta har samma närmaste dominerande punkt, kodar vi helt enkelt en referens till den punkten i själva plattan.

En klass (1, 2) platta visas i FIG 7. Två bitar i den första raden (D~dimension) är satta: naturlig, 1 sort och dominerar möjligen klass (0, 0) plattor under. Kan inte (O, O) plattor till höger.

Det finns två närmast dominerande punkter för punk- dominera klass terna i denna platta, en för punkterna i den vänstra halvan och en för punkterna i den högra halvan. Vi kan kolla referenserna till båda dessa dominerande punkterna såsom en vektor med längden 2 och kan sedan använda den vänstra/högra halvan av frågepunkten som index.

En klass (2, första kolumnen 1) platta visas i FIG 8. Två bitar i den (S-dimension) är satta: naturlig, 1 sort och dominerar möjligen klass (0, 0) plattor till höger. Kan inte dominera klass (0,0) plattor under. Det finns två närmast dominerande punkter för punkterna i denna platta, en för punkterna i den övre halvan och en för punkterna i 10 15 20 25 30 35 513 828 22 den undre halvan. Referenser till båda dessa dominerande punkterna kodas kodas som en vektor med längden 2 och kan sedan använda den övre/undre halvan av frågepunkten som index.

En klass (1, flera bitar i den första raden är satta: naturlig, 3+) platta visas i FIG 9. Tre eller 24 olika Kan och dominerar möjligtvis klass (0, O) plattor under. inte dominera klass (O, O) plattor till höger. Det kan finnas många dominerande punkter för punkterna i denna klass av plattor. Det är nödvändigt att koda denna sortens platta eftersom det finns 24 olika sorters plattor. För varje satt bit i den första raden kodas en pekare till den dominerande punkten under (om det endast finns en) eller till chunken på nästa nivå (om det finns flera dominerande punkter. Slutligen kodas en referens till den första peka- ren (en baspekare). På detta viset kan den dominerande punkten (eller en referens till chunken på nästa nivå) av en frågepunkt (s,d) helt enkelt inspektera i vilken kolumn d är och tillsammans med chunksorten utföra finnas genom att ett tabelluppslag för att få fram en pekaroffset x, och slutligen pekaren X pekare bort från baspekaren. Notera att (D-) dimensionell eftersom alla representanter i plattan ligger varje chunk på nästa nivå endast behöver vara 1- på samma S-koordinat.

En klass (3+, 1) platta visas i FIG 10. Tre eller flera bitar i den första kolumnen är satta: naturlig, 24 sorter och dominerar möjligtvis klass (O, 0) plattor till höger. Kan inte dominera klass (0, O) plattor under. Det kan finnas många dominerande punkter för punkterna i denna klass av plattor. Det är nödvändigt att koda plattans sort eftersom det finns 24 olika sorter. För varje satt bit i den första kolumnen kodas dessutom en pekare till den do- minerande punkten under (om det endast finns en) eller till chunken på nästa nivå (om det finns flera dominerande punkter). Slutligen kodas en referens till den första pe- 10 15 20 25 30 513 828 23 karen (en baspekare). På detta viset kan den dominerande punkten (eller en referens till chunken på nästa nivå) hos en frågepunkt (s,d) finnas genom att helt enkelt inspektera i vilken rad s är och tillsammans med vilken sort av chunk utföra ett tabelluppslag för att få fram en pekareoffset x, och slutligen få fram pekaren X pekare bort från baspekaren. Notera att varje chunk på nästa nivå endast behöver vara 1- (S-) dimensionell eftersom alla represen- tanter i plattan ligger på samma D-koordinat.

En klass (2+, flera bitar är satta i både den första raden och den första 2+) platta visas i FIG ll. Två eller kolumnen: begränsad, 625 sorter, kan inte dominera andra plattor och kan inte domineras av andra plattor. Det finns typisk många dominerande punkter i denna klass av plattor. och (3+, 1) plattor. En begränsning införs emellertid för att reducera Kodningen utförs exakt som för klass (1, 3+) antalet olika sorter innan den verkliga kodningen utförs.

Den första uppgiften är att införa en begränsning liknande plattbegränsningen enligt definition 8 för varje bit. Ett par bitvektorer med längden 8, Sv och Dv, beräknas sedan, varvid Si = 1, om det finns en bit satt i den ite kolumnen, och O annars Di = 1, om det finns en bit satt i den ite kolumnen och O, annars En ny platta skapas slutligen genom att beräkna pro- dukten av Sv och DVT genom att använda matrismultiplika- tion, och kodas.

Så som i klass (1, 3+) och (3+, 1) dimensionella undernivàer också tillhandahållas i detta plattorna kan 1- fallet. Det kontrolleras om alla representanter i en bit, innefattande fler än en representant, är i samma rad i U, 10 15 20 25 30 513 828 24 vilket innebär att S-dimensionen kollapsar, eller i samma kolumn i U, vilket innebär att D-dimensionen kollapsar.

En ytterligare beskrivning av datastrukturen använd i brandväggen för att representera NAT- och HP-ingångar.

I båda dessa fall används paret av IP-adresser saddr och daddr, portparet sport och dport och protokollet proto av det bearbetade paketet som nyckel vid uppslaget. Det första steget i uppslaget är att beräkna ett hash-värde.

Detta åstadkoms genom att använda väldigt enkla och snabba instruktioner, såsom bitskift bitvis logiska operatorer.

Genom att använda hash-värdet som index fås sedan en 16- bitars pekare från en stor vektor (hash-tabell).

Pekaren är antingen 0, vilket innebär att uppslaget gick fel (tomt) träd, vilket är en mycket effektiv datastruktur för att eller refererar till roten i ett Patricia- representera små uppsättningar av nycklar. Om pekaren re- fererar till ett Patricia-träd byggs en nyckel genom att daddr, dport och proto. Nyckeln används sedan när Patricia-trädet söks ige- konkatinera bitmönstren för saddr, sport, nom enligt vad som beskrivs i nästa stycke.

Ett Patricia-träd är ett binärt träd, frågenycklar som bitvektorer och använder ett bitindex i som behandlar varje intern nod för att styra hoppen. Sökningen åstadkoms genom att traversera trädet från roten till ett löv. När en intern nod med bitindex i besöks inspekteras bit i för frâgenyckeln för att bestämma om sökningen skall fortsätta i det vänstra (om biten är 0) eller det högra (om biten är 1) underträdet. Traverseringen stoppas när den när ett löv.

För att bestämma om frâgenyckeln finns i tabellen eller inte jämförs frâgenyckeln med den i lövet lagrade nyckeln.

Om de två nycklarna är lika har sökningen lyckats.

FIG 12 illustrerar ett exempel pä en misslyckad sök- ning för frâgenyckeln 001111 i ett Patricia-träd innefat- tande sex nycklar. Bitarna nr 0, 2 och 3 inspekteras under traverseringen, som slutar i lövet nyckeln 011101. Dä frà- 10 15 20 25 30 513 828 25 gan och lövnycklarna jämförs detekteras en felmatchning i bit nr 1.

Med hänvisning till bitindexen lagrade i den interna noden är Patricia-trädet hopordnat (heap ordered), dvs nå~ gon intern nod, förutom roten, har ett bitindex större än bitindexet hos sin förälder. Härav följer att alla lagrade nycklar i ett underträd med roten i en nod med bitindex i är identiska upp till och innefattande, bit i-1.

Införelse åstadkoms genom att först utföra en lyckad sökning och att lagra index i för den första felaktiga matchningsbiten i jämförelsen med fråge- och lövnyckeln.

Två nya noder skapas sedan, en ny intern nod med index i och en lövnod för varje frågenyckel. Beroende av om den ite biten hos frågenyckeln är 0 eller 1 lagras lövet såsom det vänstra respektive det högra underträdet för den interna noden. Genom att använda det andra underträdsfältet som länkfält sätts den interna noden sedan in direkt ovanför noden med minsta bitindex större än i i vägen traverserad från roten till lövet.

FIG 13 visar Patricia-trädet som följer från insätt- ningen av frågenyckeln från den lyckade sökningen i det tidigare exemplet i FIG 12. En ny intern nod med bitindex 1 skapas och sätts in mellan noderna med bitindex 0 och 2 i vägen traverserad från roten.

Patricia-haching använd för hålslagning fungerar exakt enligt vad som beskrivits ovan - ett enkelt hash-ta- belluppslag följt av ett Patricia-tråduppslag. Nästan all- tid nås ett löv direkt, vilket innebär att det inte är nödvändigt att bygga en bitvektor från parametrarna - dessa jämförs direkt för att överensstämma med fält i strukturen innefattande/representerande Patricia-lövet.

En uppslagsfunktion hp_lookup(iaddr, xaddr, iport, xport, proto) tillhandahålls, som används för både I2X-HP och X2I-HP. Enda skillnaden mellan dessa är ordningen, ip vilken parametrarna ges. För I2X-HP är funktionsanropet W U 20 25 35 513 828 26 hp_lookup(saddr, daddr, sport, dport, proto) och för X2I-HP är anropet hp¿lookup(daddr, saddr, dport, sport, proto).

Uppslagsfunktionen skicka tillbaka en referens till en struktur innefattande Patricia-lövnyckeln, dvs iaddr, xaddr, iport, xport och proto samt ett antal andra fält, vilka representerar tillståndet hos förbindelsen, exempel- vis för TCP-sekvensnummer.

Patricia~hashingen för NAT är något mer komplicerad än för HP. Anledningen är att tre olika adresser och por- tar, iaddr, naddr, xaddr, iport, nport, xport är involve- rade i motsats till HP där endast två adresser och portar är involverade. Detta innebär att skillnaden mellan I2X och X2I blir lite mera krångligt än bara att växla adresser och portar i uppslaget.

Problemet löses genom att låta den minst signifikanta biten av hash-värdet reflektera om uppslaget är I2X eller X2I (det är väsentligen det samma som att använda två hash- tabeller). för en NAT-förbindelse är densamma för I2X och X2I och den Strukturen innefattande Patricia-lövnycklarna innefattar alla tre adresser och portar.

Det finns två uppslagsfunktioner, nat_i2x_lookup(saddr, daddr, sport, dport, proto) och nat_x2i_lookup(saddr, daddr, sport, dport, proto). Båda funktionerna använder argumenten att räkna ett hash-värde där den minst signifikanta biten är satt i enlighet därmed.

Om den resulterande pekaren refererar till en Patricia-nod (intern nod) konkatineras adresserna, portarna och proto- kollet för att skapa den nödvändiga bitvektorn för traver- seringen av Patricia-trädet. När lövstrukturen uppnås jäm- förs adresserna, portarna och protokollet med de motsva- rande fälten i lövet.

När ett paket är föremål för IZX-NAT: saddr (hos paketet) jämförs med iaddr (hos lövstruk- turen) W Ü 20 25 30 35 515 828 27 daddr jämförs med xaddr sport jämförs med iport dport jämförs med xport proto jämförs med proto Om alla dessa matchar har uppslaget lyckats och av- sändaradressen och porten saddr och sport hos paketet byts ut mot naddr respektive nport (hos lövstrukturen), innan paketet skickas vidare.

När ett paket är föremål för X2I-NAT: saddr (hos paketet) jämförs med xaddr (hos lövstruk- turen) daddr sport jämförs med naddr jämförs med xport dport jämförs med nport proto jämförs med proto Om alla dessa matchar har uppslaget lyckats och des- tinationsadressen och -porten, daddr och dport hos paketet byts ut mot iaddr respektive iport (hos lövstrukturen), innan paketet skickas till nästa bearbetningssteg.

Uppdateringar av HP~ och NAT-datastrukturerna utförs av EFFNIX kärna (tidigare NetBSD), cessor 1) men det mesta av uppslagen utförs av vidarebe- fordringskärnan, som kör på BSPn (pro- som arbetar på Apn (processor 2). Det finns endast ett exempel av HP-datastrukturen och ett exempel av NAT-datastrukturen. Dessa ligger i delat minne och koms åt av de två processorerna samtidigt. Detta re- sulterar i ett mycket intressant synkroniseringsproblem - en skriver och en läser. Synkroniseringen löses genom att låta uppdateringsrutiner invalidera lövstrukturerna och noderna innan något ändras (skrivning). Uppslagsrutinerna kontrollerar att refererade löv och noder är giltiga före och efter de har refererats samt också att de inte har 10 15 513 828 28 blivit ändrade under åtkomsten. Om en kapplöpning inträffar och detekteras (alla farliga kapplöpningsförhållanden detektera) och behandlas där (antingen utförs ett lyckat uppslag följt fallerar uppslaget och paketet skickas till BSPn av en bearbetning eller uppdateras datastrukturen).

Det är uppenbart att föreliggande uppfinning till- handahåller en brandväggsapparat och en metod för att kon- trollera nätverksdatapakettrafiken mellan interna och ex- terna nätverk som fullständigt uppfyller ändamàlen och fördelarna framlagda ovan. Även om uppfinningen har beskrivits i anslutning till en specifik utföringsform är denna uppfinning möjlig i flera utföringsformer underförstått att den aktuella be- skrivningen skall betraktas såsom en exemplifiering av principerna med uppfinningen och är inte avsedd att be- gränsa uppfinningen till den illustrerade specifika utfö- ringsformen.

Claims (17)

10 Ü 20 25 30 35 515 828 29 NYA KRAV PATENTKRAV

1. Brandvägg (3) för styrning av nätverksdatapaket- trafik mellan interna och externa nätverk (l, 5, 4), inne- fattande filtreringsorgan för att, beroende av innehållet i datafält i ett mellan nätverken överfört datapaket, välja en på datapaketet tillämplig regel från en fullständig upp- sättning regler för att blockera paketet eller vidare- befordra paketet genom brandväggen (3), kännetecknad av 2- dimensionella adressuppslagsorgan (8) för utförande av ett 2-dimensionellt uppslag av avsändar- och destinations- adresser för paketet i en uppsättning av adressprefix, var- vid varje prefix har en deluppsättning med regler från den för att hitta ett prefix associerat med avsändar- och destinationsadresserna, (10) på innehållet i datafälten - för att hitta den på paketet fullständiga uppsättningen av regler, och regelmatchningsorgan för regelmatchning - baserat tillämpliga regeln. kännetecknad av att (8), organ för att hitta det med avsändar- och destinations-

2. Brandvägg enligt krav l, det 2-dimensionella adressuppslagsorganet innefattar adresserna associerade prefixet genom att bestämma den när- mast dominerande punkten p i p under normen Lw, dvs den do- minerande punkten av pi e p av p, som minimerar Lw-avstän- det mellan pi och p.

3. Brandvägg enligt krav 2, kânnetecknad av att avsändar- och destinationsadresserna representeras av en representerad av heltalspar (s,d), 232, s d < 232, mängden prefix P = punkt e U, varvid U är en 2-dimensionell adressrymd som satisfierar: 0 S s < {P1,P2,.. varje prefix Pi är en logisk rektangel i adressrymden .,RJ är en delmängd av U, U definierad av [(s0,d0),( sl,d,)], varvid sl-so = sl-22 * ks W Ü 20 25 30 513 828 30 = Zisoch di-do = dl-22.* kd= 2% för något icke negative hel- tal is,id,1 rektangeln R är en delmängd av U, som satisfierar: (S,d> U och punktparet [(s,,,d,,) , ( sl,dl)] e R om søš s < sl, doš d< dl, varvid (so,do),( s1,d1)e definierar R unikt.

4. Brandvägg enligt krav 3, kännetecknad av att för varje prefix P = [(sWcL),(sl,dQ} e P är punkten (so,dQ -,pn} = {(S,,dQ,(s2fl%),...,(snflL)} är uppsättningen representanter en representant för P och p = {pU p2,.. för prefixen i P, varvid givet en punkt (sd,dd) G U så do- mineras för varje (s,d) e U (s,d) av (sd,dfi) där sd 2 s och ddzd.

5. Brandvägg enligt något av föregående krav, kännetecknad (ll) mentinsamlingsorgan för insamling av paketfragment från ett av en fragmentmaskin innefattande frag- fragmenterat paket ända tills ett fragmenthuvud för paketet tas emot, fragmenthuvudlagringsorgan för lagring av den i paketets fragmenthuvudfält aktuella informationen i en ingång, fragmentvidarebefordringsorgan för vidarebefordran av paketfragment försedda med fragmenthuvudfältsinformation med början med fragmenthuvudet, varvid varje fragment behandlas av filtreringsorganet såsom ett vanligt ej fragmenterat paket.

6. Brandvägg enligt något av föregående krav, kännetecknad av nätverksadressöversättningsorgan (12, 14), för översättning, beroende av informationen i prefixet, av interna avsändaradresser till externa avsändaradresser för ett paket skickat ut genom brandväggen (3) eller externa avsändaradresser till interna avsändaradresser för ett pa- ket skickat in genom brandväggen (3). 10 U 20 25 30 Lu UI 513 828 31 känneteck- 14), översättning, beroende av informationen i prefixet, av in-

7. Brandvägg enligt något av kraven l-5, nad av nätverksadressöversättningsorgan (12, för terna avsändaradresser till externa avsändaradresser för till det eller externa avsändaradresser till ett paket skickat från det interna nätverket (1) externa nätverket (4) interna avsändaradresser för ett paket skickat från det ex- terna nätverket (4) till det interna nätverket (1).

8. Brandvägg enligt något av föregående krav, kännetecknad av hålslagningsorgan (16, 17) för bestämning, baserat på informationen i prefixet, om paketet är föremål för ett temporärt undantag från en extern-till-intern blockeringsregel för en förbindelse initierad från det in- terna nätverket och etablering av en äterkopplad kanal ge- nom brandväggen för paket överförda från det externa nät- verket (4) sens varaktighet. till det interna nätverket (1) under förbindel-

9. Metod att styra nätverksdatapakettrafik mellan interna (1, 5) och externa nätverk (4) genom en brandvägg (3), innefattande stegen att beroende av innehållet i datafälten hos ett data- paket, som överförs mellan nätverken, välja en på datapake- tet tillämplig regel från en fullständig uppsättning reg- ler, tillämpa regeln på paketet, och beroende av regeln blockera eller vidarebefordra pa- ketet genom brandväggen (3), kännetecknad stegen att: av att filtreringen dessutom innefattar utföra ett 2-dimensionellt uppslag av avsändar- och destinationsadresser för paketet för att hitta ett med av- sändar- och destinationsadresserna associerat prefix, via sin representation i en uppsättning adressprefix, varvid W Ü 20 25 30 513 828 32 varje prefix har en deluppsättning med regler av den full- ständiga uppsättningen regler, och baserat på innehållet i datafälten hos paketet utföra en regelmatchning mot deluppsättningen av regler för att hitta den på datapaketet tillämpliga regeln. före

10. Metod enligt krav 9, kännetecknad steget att välja en på datapaketet tillämplig regel, dess- av att, utom innefatta de ytterligare stegen att: samla paketfragment från ett fragmenterat paket ända tills ett fragmenthuvud för paketet tas emot, i en ingång lagra information från ett fragment- huvudfält hos paketet, vidarebefordra paketfragmenten försedda med fragment- och huvudinformation med början med fragmenthuvudfältet, varvid varje fragment behandlas av filtreringsorganet såsom ett vanligt ej fragmenterat paket.

11. Metod enligt krav 9 eller 10, kännetecknad av att, före steget att utföra en regelmatchning, dessutom in- nefatta steget att: beroende av informationen i prefixet översätta den externa avsändaradressen till en intern avsändaradress för ett paket, som skall skickas in genom brandväggen (3).

12. Metod enligt något av de föregående kraven 9-11, kännetecknad av att, före steget att utföra en regel- matchning, dessutom innefatta steget att: beroende av informationen i prefixet, översätta den externa avsändaradressen till en intern avsändaradress för ett paket, som skall skickas från det externa nätverket (4) till det interna nätverket (1, 5).

13. Metod enligt något av de föregående kraven 9-12, kännetecknad av det ytterligare steget att: 10 U 20 25 30 513 828 33 beroende av informationen i prefixet översätta den interna avsändaradressen till en extern avsändaradress för ett paket, som skall skickas ut genom brandväggen (3).

14. Metod enligt något av kraven 9-13, kännetecknad av det ytterligare steget att: beroende av informationen i prefixet översätta den interna avsändaradressen till en extern avsändaradress för ett paket, till det externa nätverket (1). som skall skickas från det interna nätverket (4)

15. Metod enligt något av de föregående kraven 9-14 kânnetecknad av att, före steget att utföra en regel- matchning, dessutom innefatta stegen att: baserat på informationen i prefixet, bestämma om pa- ketet är föremål för ett temporärt undantag från en intern blockeringsregel för en förbindelse initierad från det in- (1), om så är fallet, etablera en återkopplad kanal för till det in- (3), med en varaktig- terna nätverket och paket överförda från det externa nätverket (4) terna nätverket (1) genom brandväggen het motsvarande förbindelsens livstid.

16. Metod enligt något av kraven 9-15, kännetecknad av att steget att utföra ett 2-dimensionellt uppslag av av- sändar- och destinationsadresser för paketet innefattar steget att: hitta den närmast dominerande punkten p i p under normen Lw, dvs den dominerande punkten av pi e p av p, som minimerar Lw-avståndet mellan pi och p.

17. Metod enligt något av kraven 9-15, kännetecknad av att avsändar- och destinationsadresserna representeras av en punkt (s,d) )e U, varvid U är en 2-dimensionell 5 10 15 513 828 34 adressrymd representerad av heltalspar (s,d) , som satisfie- rar: O S s < 232, S d < 232, mängden prefix P = {P1,P2, . . .,P,,} är en delmängd av U, varje prefix Pi är en logisk rektangel i adressrymden U definierad av [(s0,d0),( s1,d1)], varvid sl-so = sl-Zís * ks = 22 och dl-do = d1-2id * kd = 2% för något icke negative hel- tal is,id,k och kd, rektangeln R är en delmängd av U, sl som satisfierar: (s,d) U och punktparet [(s°,d°) , ( s1,d1)] definierar R unikt, e R om soS s < sl, doS d< dl, varvid (so,do),( s1,d1)e för varje prefix P = [(s,,,d°) , (sl,dl)] e P är punkten {p1I P2/ ° ' ° rpm” = , (sn,dn)} är uppsättningen representanter (smdd) där sd 2 s och (swdo) en representant för P och p = {(sl,d1), (swdz), . . . för prefixen i P, varvid givet en punkt (s,d) e U (s,d) e U så do- mineras för varje av (swdd) ddzd.