Abstract-A brandvägg är ett paketfilter som placeras vid ingången till ett privat nätverk. Det kontrollerar huvudfälten för varje inkommande paket i det privata nätverket och beslutar, baserat på de angivna reglerna i brandväggen, om att acceptera paketet och tillåta det att fortsätta, eller att kassera paketet. En egenskap hos en brandvägg är en uppsättning paket som brandväggen är skyldig att acceptera eller kassera. Associeras med varje brandvägg är en mycket stor uppsättning egenskaper som brandväggen behöver för att tillfredsställa. Utrymmet och tids komplexiteten hos den mest kända deterministiska algoritmen, för att verifiera att en given brandvägg uppfyller en viss egenskap, är O(n d ), där n är antalet regler i den givna brandväggen och d är antalet fält som kontrolleras av brandväggen. Vanligtvis är n runt 2000 och d är 5. I detta dokument föreslår vi den första deterministiska brandväggsverifieringsalgoritmen vars rymdkomplexitet är O(nd), linjär i både n och d. Denna algoritm består av tre komponenter: ett projektionspass, ett divisionspass och en sondalgoritm. Vi tillämpade vår verifieringsalgoritm till över två miljoner brandvägg-fastighet par, varierande n från 100 till 10000 och fastställande d på 5. Från detta experiment, Vi observerade att algoritmen kräver (900 + 0.5n) Kilobytes av lagring och i storleksordningen 10 sekunder exekveringstid.
I REF ger vi en elegant algoritm för brandväggsverifiering vars utrymme komplexitet är O(nd), och vars tid komplexitet är ordning O(n d ).
Projection and Division: Linear-Space Verification of Firewalls
{'venue': '2010 IEEE 30th International Conference on Distributed Computing Systems', 'journal': '2010 IEEE 30th International Conference on Distributed Computing Systems', 'mag_field_of_study': ['Computer Science']}