Not-a-Bot: Improving Service Availability in the Face of Botnet Attacks

R. Gummadi, H. Balakrishnan, P. Maniatis, S. Ratnasamy, “Not-a-Bot: Improving Service Availability in the Face of Botnet Attacks,” NSDI’09, (April 2009). [PDF]


In recent years, botnets have become the major originators of email spams, DDoS attacks, and click-frauds on advertisement-based web sites. This paper argues that separating human-generated traffic from botnet-generated activities can improve reliability of various web-based services against botnet attacks. But identifying human-generated traffic in the absence of strong unique identities can be challenging. In this paper, the authors propose NAB (Not-A-Bot), a system to approximately identify and certify human-generated activity in a non-intrusive way.

NAB Architecture

NAB consists of an attester, a small trusted software, that runs locally at a host (isolated from the untrusted OS) and generates attestations corresponding to a request from an application, as well as an external verifier that validates these attestations in a distributed site. There are four main requirements that drive the NAB architecture (attester and verifier) design:

  1. Attestations must be generated in response to human requests automatically.
  2. Attestations must not be transferable from the client on which they are generated to attest traffic originating from another client.
  3. NAB must benefit users that deploy it without hurting those that do not.
  4. NAB must preserve the existing privacy and anonymity semantics of applications

Requirements 1 and 2 are implemented/met in the attester and requirements 3 and 4 are ensured in the verifier.


The attester runs on a trusted computing base (TCB), which is implemented by taking advantage of the Trusted Platform Module (TPM) available is most modern systems. The authors use TPM to create a trusted path between physical input devices and the human activity attester.

The attester’s sole purpose is to create attestations – when asked for by an application – for legitimate human activity. The authors used a simple t-δ attester, where a attestation is created if there is any input activity in last δ time units. Even though there is a possibility of forging/harvesting user activity in this simpler approach, the authors argue that the botnet will be limited by human activity frequency, which will decrease the number of attacks.

NAB generates responder-specific, content-specific, and if appropriate, challenger-specific attestations and employs existing cryptographic methods to secure them. It also ensures that attestations cannot be double-spent and cannot be misused by botnets (for a very limited time window botnets can forge attestations)


Verifier is co-located with the server processing requests. When invoked, the verifier is passed both the attestation and the request. Based on these information (plus the crypto-thing that are in the paper), the verifier checks the validity of the attestation. The authors also discussed different application-specific spam, DDoS, and click-fraud verification policies.

Evaluation Results

Major results from the evaluation are:

  • TCB size can be really small (500 SLOC)
  • Attester CPU cost is 107 instructions/attestations
  • For simple application changes less than 250 SLOC changes is enough to enable them of NAB
  • In the worst case, NAB can suppress 92% spam, 89% non-human possibly DDoS activity, and 87% automated clicks without false positives
  • The verifier can withstand 100,000 bot DDoS and can handle more than 1000 requests/second


The authors have a done good job in discussing several alternatives in multiple cases instead of sticking to their chosen one, which provides insights into botnet behavior and explains why some solutions might not work. There solution still has some loopholes, but possibly will work to some extent. The requirement of changing all the applications could be a turn off. However, the fact that NAB does not discriminate against unattested traffic makes that problem go away and allows incremental deployment.

One problem that I can think of right now regarding this approach is that the applications are not in the TCB and the requests for attestations do not seem to be going through a trusted channel. What are the fallback options if a malicious entity corrupts/removes attestations just after they leave the trusted base of the attester? Also, the verifiers do not seem to be in a TCB. What if it is compromised?

Leave a Reply

Your email address will not be published. Required fields are marked *