Scientific knowledge map · Paper #8
Filtering Sources of Unwanted Traffic Based on Blacklists
2008 · Information Theory and Applications Workshop (ITA)
- Theory
- Applied
- algorithm
Research question
What does the paper try to establish?
How can a router compress a large, possibly changing IP blacklist into a small set of source-prefix filters while controlling collateral damage and the fraction of malicious addresses left unblocked?
Central answer
What is the proposed answer?
Model filters as address intervals and exploit their one-dimensional order. FILTER-ALL-STATIC greedily merges the cheapest adjacent bad-address ranges; FILTER-SOME-STATIC also weighs the cost of leaving a bad address unfiltered. The paper proves both greedy constructions optimal, extends them incrementally to changing blacklists, and simulates how address clustering and density affect filter efficiency.
Evidence profile
Six dimensions, kept separate
The chart summarizes documented evidence and process. It is not a correctness probability, confidence score, or ranking, and no composite score is calculated.
LowMediumHighN/A = not assessed
A smaller value means less documented support for that dimension, not that the paper is false or unimportant.
- Epistemic evidence High
-
The paper formally defines objectives, supplies algorithms and optimality arguments, analyzes complexity, and evaluates clustering effects; operational blacklist accuracy and deployment remain outside scope.
Blacklist, filter, weight, and objective definitions FILTER-ALL-STATIC algorithm and optimality FILTER-SOME-STATIC algorithm and optimality Clustering and density simulations - Auditability High
-
A fixed author-hosted full text is checked in with page count and hash, making algorithms, proofs, assumptions, and simulations inspectable.
Author-copy provenance FILTER-ALL-STATIC algorithm and optimality FILTER-SOME-STATIC algorithm and optimality Clustering and density simulations - Production provenance Medium
-
Named authorship, author-copy provenance, and official metadata are documented; author roles, revision history, and simulation lineage are not.
Author-copy provenance Official publication metadata - External scrutiny Medium
-
The work has a workshop publication record and explicit proofs, but no public reviews, mechanized verification, or independent reproduction was located.
Official publication metadata - Reception Low
-
No citations were verifiably located in the constrained dated search. Under the author's 0-8 rule this is low, but it is not a claim that the paper has no citations.
Citation search attempted - Contribution significance High
-
The work turns blacklist compression into a precise optimization family with efficient exact algorithms, dynamic updates, and an explicit false-positive/false-negative control.
Problem, assumptions, and contributions FILTER-ALL-STATIC algorithm and optimality FILTER-SOME-STATIC algorithm and optimality Dynamic blacklist updates
Assessment: Ai draft author review pending · 2026-07-11 · rubric 0.2. These dimensions describe documented support and process, not truth, correctness, or a universal ranking. No composite score is calculated.
Top-down and bottom-up view
Hierarchical knowledge map
Collapse a branch for a top-level reading, or follow its source links and child nodes to audit the evidence and boundaries underneath it.
Filtering Sources of Unwanted Traffic Based on Blacklists
A family of provably optimal algorithms for compiling static and changing source-IP blacklists into a bounded number of interval filters.
Problem, assumptions, and contributions Official publication metadata-
question Research question
research questionHow should limited ACL entries aggregate blacklist addresses while balancing missed malicious sources against blocked legitimate addresses?
Problem, assumptions, and contributions -
contribution Central answer
proved and simulatedExploit the total order of IP addresses: greedy adjacent-range operations produce optimal static filter sets and efficient incremental variants reuse that structure as a blacklist changes.
FILTER-ALL-STATIC algorithm and optimality FILTER-SOME-STATIC algorithm and optimality Dynamic blacklist updates -
model Weighted interval-filter model
formalizedEach filter blocks a contiguous address range. Address weights can encode legitimate-traffic cost, confidence in maliciousness, or operator policy, under a maximum filter count.
Blacklist, filter, weight, and objective definitions -
algorithm FILTER-ALL-STATIC
proved optimalStarting with one filter per bad address, the greedy algorithm merges the N-F least-cost adjacent ranges. Theorem 3.1 proves optimality; sorting yields O(N log N) time.
FILTER-ALL-STATIC algorithm and optimality -
algorithm FILTER-SOME-STATIC
proved optimalAt each step the algorithm compares removing a bad-address filter with merging adjacent filters, using signed address weights to trade false negatives against collateral damage. Theorem 3.2 proves optimality.
FILTER-SOME-STATIC algorithm and optimality -
algorithm Dynamic blacklist variants
incrementally specifiedFILTER-ALL-DYNAMIC updates the sorted merge-cost list after an address arrives or departs; a corresponding filter-some method is outlined to exploit temporal correlation rather than recomputing from scratch.
Dynamic blacklist updates -
evidence group Clustering and density evaluation simulation
Multifractal and synthetic blacklist distributions vary clustering, blacklist density, filter budget, and weights to measure blocked bad addresses and collateral damage.
Clustering and density simulations-
result Clustering makes aggregation effective
simulation supportedThe reported benefits are strongest when malicious addresses cluster in the IP space; sparse or weakly clustered blacklists require more filters or greater collateral damage.
Clustering and density simulations
-
-
limitation group Operational boundaries
materialBlacklist construction and accuracy are assumed, weights are policy inputs, spoofing and evasion are not modeled, and evaluation uses distribution models rather than a deployed filtering system or released longitudinal blacklist.
Problem, assumptions, and contributions Blacklist, filter, weight, and objective definitions Clustering and density simulations Summary and future work -
artifact Artifacts
paper available no codeA fixed author copy is available locally; implementation, simulation code, generated blacklists, and result data were not located.
Clustering and density simulations Author-copy provenance -
scrutiny Scrutiny
peer reviewedThe work appeared at ITA 2008 with explicit optimality arguments and a public author copy; review reports or independent reproduction were not located.
FILTER-ALL-STATIC algorithm and optimality FILTER-SOME-STATIC algorithm and optimality Official publication metadata
Audit trail
Source index
Locators state the depth of the current audit. PDF page numbers, where present, are one-based file pages; metadata-, summary-, and abstract-bounded records explicitly identify their limitations.
- Problem, assumptions, and contributions Abstract and Section I, PDF pages 1-2
- Blacklist, filter, weight, and objective definitions Section II, PDF pages 2-3
- FILTER-ALL-STATIC algorithm and optimality Section III-A, Algorithms 1-2 and Theorem 3.1, PDF pages 3-5
- FILTER-SOME-STATIC algorithm and optimality Section III-B, Algorithm 3 and Theorem 3.2, PDF pages 5-7
- Dynamic blacklist updates Sections III-C and III-D, PDF pages 7-8
- Clustering and density simulations Section IV, PDF pages 8-10
- Summary and future work Section V, PDF page 10
- Author-copy provenance Public author-hosted PDF
- Official publication metadata DOI 10.1109/ITA.2008.4601049
- Citation search attempted Exact-title search, 2026-07-11; no verified count retrieved