Using Memory Bound Functions To Prevent Spam
In 1992, IBM research scientists Cynthia Dwork and Moni Naor published a paper titled Pricing via Processing or Combating Junk Mail, suggesting a possibility of using CPU bound functions to deter abusers from sending spam. The scheme was based on the idea that computer users are much more likely to abuse a resource if the cost of abusing the resource is negligible: the underlying reason spam has become so rampant is that sending an e-mail has minuscule cost for spammers.
Dwork and Naor proposed that spamming might be reduced by injecting an additional cost in the form of an expensive CPU computation: CPU bound functions would consume CPU resources at the sender's machine for each message, thus preventing huge amounts of spam from being sent in a short period. The basic scheme that protects against abuses is as follows:
Let S be sender, R be recipient, and M be an e-mail. If R has agreed beforehand to receive e-mail from S, then M is transmitted in the usual way. Otherwise, S computes some function G(M) and sends (M, G(M)) to R. R checks if what it receives from S is of the form (M, G(M)). If yes, R accepts M. Otherwise, R rejects M. The figure on the right depicts cases in which there were no prior agreements:
The function G is selected such that the verification by R is relatively fast (taking a millisecond) and such that the computation by S is somewhat slow (involving at least several seconds). Therefore, S will be discouraged from sending M to multiple recipients with no prior agreements: the cost in terms of both time and computing resources of computing G repeatedly will become very prohibitive for a spammer who intends to send many millions of e-mails.
The major problem of using the above scheme is that fast CPUs compute much faster than slow CPUs. Further, higher-end computer systems also have sophisticated pipelines and other advantageous features that facilitate computations. As a result, a spammer with a state-of-the-art system will hardly be affected by such deterrence while a typical user with a mediocre system will be adversely affected. If a computation takes a few seconds on a new PC, it may take a minute on an old PC, and several minutes on a PDA, which might be a nuisance for users of old PCs, but probably unacceptable for users of PDAs. The disparity in client CPU speed constitutes one of the prominent roadblocks to widespread adoption of any scheme based on a CPU bound function. Therefore, researchers are concerned with finding functions that most computer systems will evaluate at about the same speed, so that high-end systems might evaluate these functions somewhat faster than low-end systems (2-10 times faster, but not 10-100 faster) as CPU disparities might imply. These ratios are “egalitarian” enough for the intended applications: the functions are effective in discouraging abuses and do not add a prohibitive delay on legitimate interactions, across a wide range of systems.
The new egalitarian approach is to rely on memory bound functions. As stated before, a memory bound function is a function whose computation time is dominated by the time spent accessing memory. A memory bound function accesses locations in a large region of memory in an unpredictable way, in such a way that using caches are not effective. In recent years, the speed of CPU has grown drastically, but there has been comparatively small progress in developing faster main memory. Since the ratios of memory latencies of machines built in the last five years is typically no greater than two, and almost always less than four, the memory bound function will be egalitarian to most systems for the foreseeable future.
Read more about this topic: Memory Bound Function
Famous quotes containing the words memory, bound, functions and/or prevent:
“Men like my father cannot die. They are with me still real in memory as they were in flesh. Loving and beloved forever. How green was my valley then.”
—Philip Dunne (19081992)
“When you think of the huge uninterrupted success of a book like Don Quixote, youre bound to realize that if humankind have not yet finished being revenged, by sheer laughter, for being let down in their greatest hope, it is because that hope was cherished so long and lay so deep!”
—Georges Bernanos (18881948)
“In todays world parents find themselves at the mercy of a society which imposes pressures and priorities that allow neither time nor place for meaningful activities and relations between children and adults, which downgrade the role of parents and the functions of parenthood, and which prevent the parent from doing things he wants to do as a guide, friend, and companion to his children.”
—Urie Bronfenbrenner (b. 1917)
“Only the freedom of mind can prevent the state from becoming totalitarian and from issuing totalitarian demands.”
—Friedrich Dürrenmatt (19211990)