A topic not discussed in the paper is denial of service attacks by exploiting the hash codes. For TinyLFU this occurs when an attacker is able to place an entry as the main cache's victim. Then the attacker artificially raises the victim's frequency by exploiting hash collisions so that all new arrivals are rejected. This would lead to a very poor hit rate and exhaust the underlying resource.
Initially, I tried to protect against this by using a random smear in the sketch. However that doesn't protect against entries with the same hash code. The proper solution was to instead add a random admittance if the candidate is "warm". This adds enough jitter to break the attack vector without impacting the hit rate.
See the relevant function and the test case.
P.S. This is neat :)
A topic not discussed in the paper is denial of service attacks by exploiting the hash codes. For TinyLFU this occurs when an attacker is able to place an entry as the main cache's victim. Then the attacker artificially raises the victim's frequency by exploiting hash collisions so that all new arrivals are rejected. This would lead to a very poor hit rate and exhaust the underlying resource.
Initially, I tried to protect against this by using a random smear in the sketch. However that doesn't protect against entries with the same hash code. The proper solution was to instead add a random admittance if the candidate is "warm". This adds enough jitter to break the attack vector without impacting the hit rate.
See the relevant function and the test case.
P.S. This is neat :)