4 ms·

Yes, you could do it with deltas instead. The tradeoffs are that it won't be as fast and will cost you a LOT more in bandwidth. (and cost your users more bandwi

Yes, you could do it with deltas instead. The tradeoffs are that it won't be as fast and will cost you a LOT more in bandwidth. (and cost your users more bandwidth as well. They might be on a very slow/limited data plan) Maybe you don't care about bandwidth and would prefer to avoid the complexity and maintenance overhead of adding a bloom filter. As with anything, there are tradeoffs and your requirements can change over time. Maybe the ad networks or malware creators start using new domains every 10 minutes to counter your blocking system so now you have to store more data and disseminate it more frequently. As engineers, it's our job to weigh the tradeoffs between different solutions given the resources and constraints of the situation. For the situation I've outlined above, I'd at least strongly consider a bloom filter but it's certainly not the only way to do it.

marginalia_nu 5y ago
> As engineers, it's our job to weigh the tradeoffs between different solutions given the resources and constraints of the situation. For the situation I've outlined above, I'd at least strongly consider a bloom filter but it's certainly not the only way to do it. We should also not gloss over that with a bloom filter can't rule out false positives, and it's really not feasible to figure out which they are. Due to the nature of hashing, you won't be able to easily come up with a list of false positives. Finding just one hash collision in a wide hash is computationally stupidly hard. > As with anything, there are tradeoffs and your requirements can change over time. Maybe the ad networks or malware creators start using new domains every 10 minutes to counter your blocking system so now you have to store more data and disseminate it more frequently. Domains cost quite a lot of money so that is still pretty unrealistic. Sure you can have CN wildcards, but you can also do wildcard matching. Actually this whole scenario is unrealistic, since you can just serve ads off a random URL. The way you would create a decent ad filter is to look for characteristics in the script itself (a bit like an antivirus program), not base it off the URL.
- teraflop 5y ago
  > We should also not gloss over that with a bloom filter can't rule out false positives, and it's really not feasible to figure out which they are. Nothing says a bloom filter has to be the only data structure you use. It's a performance optimization; even if 1% of the time you have to consult a more expensive data structure to confirm your result, it can still save you a lot of computation in the long run. > Finding just one hash collision in a wide hash is computationally stupidly hard. But bloom filters don't use wide hashes; the domain of the hash function is the number of bits in the filter. > Domains cost quite a lot of money so that is still pretty unrealistic. In the case of malware, the cost of buying domains isn't that relevant, because you can compromise existing domains using automated attacks.

marginalia_nu 5y ago

> As engineers, it's our job to weigh the tradeoffs between different solutions given the resources and constraints of the situation. For the situation I've outlined above, I'd at least strongly consider a bloom filter but it's certainly not the only way to do it. We should also not gloss over that with a bloom filter can't rule out false positives, and it's really not feasible to figure out which they are. Due to the nature of hashing, you won't be able to easily come up with a list of false positives. Finding just one hash collision in a wide hash is computationally stupidly hard. > As with anything, there are tradeoffs and your requirements can change over time. Maybe the ad networks or malware creators start using new domains every 10 minutes to counter your blocking system so now you have to store more data and disseminate it more frequently. Domains cost quite a lot of money so that is still pretty unrealistic. Sure you can have CN wildcards, but you can also do wildcard matching. Actually this whole scenario is unrealistic, since you can just serve ads off a random URL. The way you would create a decent ad filter is to look for characteristics in the script itself (a bit like an antivirus program), not base it off the URL.

teraflop 5y ago
> We should also not gloss over that with a bloom filter can't rule out false positives, and it's really not feasible to figure out which they are. Nothing says a bloom filter has to be the only data structure you use. It's a performance optimization; even if 1% of the time you have to consult a more expensive data structure to confirm your result, it can still save you a lot of computation in the long run. > Finding just one hash collision in a wide hash is computationally stupidly hard. But bloom filters don't use wide hashes; the domain of the hash function is the number of bits in the filter. > Domains cost quite a lot of money so that is still pretty unrealistic. In the case of malware, the cost of buying domains isn't that relevant, because you can compromise existing domains using automated attacks.