Introduction

  Though the emergence of full-scale electronic commerce on the World-Wide-Web is proceeding slowly, the web has been quickly and aggressively realized as an effective advertising medium. Indeed, advertising itself has become an important commodity on the web. The latest evidence of this fact is the growth of click-through payments, in which the webmaster of one web site B pays the webmaster of another site A for every referral that B's pages receive from A's. In other words, if a web user, when viewing one of A's pages, clicks on a link in that page to one of B's pages (in this sense, the user has ``clicked through'' A to reach B), then A is entitled to payment from B. B runs a click-through payment program to motivate others to prominently display links to site B and thus to increase the traffic that B receives.

Due to the structure of the HTTP protocol, click-through payment schemes as implemented on the web today hold many opportunities for fraud. The referrer A is given no way to verify that it is paid for every referral its pages give B. This allows B to undetectably ``forget'' some referrals that it receives from A, a practice called hit shaving. Moreover, even if A were able to detect that its referrals were shaved by B, it has no evidence to present to a third party to argue this fact. The attention paid to hit shaving in discussions of web advertising (e.g., [Kle98]), often in advertisements for the click-through programs themselves, suggests that hit shaving is a recognized and prominent problem in the click-through industry today. Moreover, the stakes suggest that fraud is likely: some click-through programs advertise surprisingly large payments (e.g., up to $6 per click-through) and prizes based on click-throughs (e.g., one web site advertised a click-through contest in which first prize was a 1998 Corvette).

The purpose of this paper is to bring the problem of hit shaving to the attention of the technical community and to explore remedies to the problem. We first focus on solutions that can be immediately useful on the web today: we offer web constructions (i.e., ways to construct web pages and CGI scripts) that enable a webmaster to monitor how often users click through her pages to others, and to which pages they click. Moreover, these techniques require no cooperation or awareness by the sites to which the referrals are made, making them very effective. Though only heuristic in nature and not foolproof, these techniques can immediately offer webmasters greater ability to detect hit shaving by click-through payment programs. We then explore more ambitious approaches that, with the cooperation of click-through program providers, enables webmasters to monitor more precisely the number of click-throughs for which they should be paid, and to even obtain nonrepudiable evidence of these click-throughs from the target site. Even though this second set of approaches requires cooperation by the webmasters of the click-through payment programs, these webmasters need not be trusted, in the sense that their failure to cooperate is quickly detectable. All of the techniques that we propose are largely invisible to the web user, in that the user experiences nothing out of the ordinary as a consequence of these techniques. Moreover, these techniques work with off-the-shelf browsers today.