ERA

Download the full-sized PDF of Hardness of Firewall AnalysisDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3H12V84G

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

Hardness of Firewall Analysis Open Access

Descriptions

Author or creator
Elmallah, Ehab
Gouda, Mohamed
Additional contributors
Subject/Keyword
equivalence
completeness
verification
logical analysis
redundancy
packet classifiers
NP-hard
Communication Networks
3_SAT
firewalls
Type of item
Computing Science Technical Report
Computing science technical report ID
TR13-08
Language
English
Place
Time
Description
We identify 13 problems whose solutions can significantly enhance our ability to design and analyze firewalls and other packet classifiers. These problems include the firewall equivalence problem, the firewall redundancy problem, the firewall verification problem, and the firewall completeness problem. The main result of this paper is to prove that every one of these problems is NP-hard. Our proof of this result is interesting in the following way. Only one of the 13 problems, the so called slice probing problem, is shown to be NP-hard by a reduction from the well-known 3-SAT problem. Then, the remaining 12 problems are shown to be NP-hard by reductions from the slice probing problem. The negative results of this paper suggest that firewalls designers may need to rely on SAT solvers to solve instances of these 13 problems or may be content with probabilistic solutions of these problems.
Date created
2013
DOI
doi:10.7939/R3H12V84G
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-24T23:11:13.828+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 163577
Last modified: 2015:10:12 17:31:19-06:00
Filename: TR13-08.pdf
Original checksum: 074a7e629a967c0a7ec92c43d85dc03d
Well formed: false
Valid: false
Status message: Unexpected error in findFonts java.lang.ClassCastException: edu.harvard.hul.ois.jhove.module.pdf.PdfSimpleObject cannot be cast to edu.harvard.hul.ois.jhove.module.pdf.PdfDictionary offset=2542
Page count: 9
Activity of users you follow
User Activity Date