Highly Space Efficient Blacklisting.

Many recent mobile devices have CPU units comparable to desktop computers while the storage capacity they offer is significantly reduced, often by a factor of one hundred. This restriction is crucial for most current blacklisting solutions which have good performance but suffer from large memory consumption. In order to improve the situation, we propose a novel blacklisting solution operating on compressed lists. For compression, we adapt the tabular Quine-McCluskey algorithm based on the concept of reduced masks. This guarantees that the compressed blacklist is never larger than the original one. For l entries in the blacklist and k prime implicants with the highest degree n our optimized top-down reduction algorithm requires at most k + l + 2(n) memory instead of kl. Evaluations prove that the space efficient network address blacklisting on compressed data can save up to 74,43% memory space.