On Bots

I came across a 20 year old project called On Bots. I decided to use some of the concepts to create a new Scraper Junkyard.

The folks behind this project seem to have created 2,147,483,647 numbered web pages, each with links to a “left” and “right” web page. The left and right links were such that the numbers formed a binary search tree, which is clever. The leftmost, bottom web page had a numerical value of 1, the rightmost, bottom web page had a value of 2,147,483,647, and the root web page’s value was 1,073,741,824. They hint at having a link to parent nodes, but I’m not 100% certain they did. The HTML for each web page has “the value of each node is written out in American English (short scale)” to “make the content of each page more interesting for the search engines”. Each page also has a comment entry form. Apparently people or bots filled out those forms periodically.

I gather that the numerical value assigned to each node appeared as part of the HTML file name, and hence in URLs. The experimenters used the numerical values and binary tree relationships to observe how various circa 2005 search engines (Google, Yahoo! and MSN) reacted to having such a glorious abundance of content.

I decided to do something of the same, to trap bots (not necessarily Google, Bing or something else) in a dark forest of garbage web pages.

I did not want to do the work of writing a large number of web pages with links that put them in a binary search tree arrangement, so I thought of writing a simple PHP program that could take its own node number from the URL it’s invoked with. With that number it could calculate parent and left and right child URLs, where their numerical values are encoded in those URLs. I could not figure out how to go from a number to the numbers of left and right binary search tree nodes, or back to a BST parent node.

15-node binary search tree image, with numerical values labeling nodes

Since all the even-numbered nodes are leaf nodes, there’s probably a way to calculate that Node Numbered N has a parent node with some number, and left and right child nodes with other numbers, but I couldn’t figure it out.

Since I wanted a full binary tree, I used the array-as-binary-tree trick You can use array indexes to figure out parent and child indexes of nodes, which are entries in the array. If an element is at index n in the array, its child elements are at indexes 2n+1 and 2n+2. Its parent node is at index (n-1)/2, which is rounded down to the next lowest integer value. In my case no array need appear, as I’m only using the indexes to compose URLs. A single PHP program does all the work.

Here’s a binary tree constructed from an array with sorted integer values from 0 to 15.

15-node sorted array binary tree image, with numerical values labeling nodes

Looking at the node valued 12, (n-1)/2 = (12-1)/2 = 11/1 = 5.5, which rounds down to 5. The node labeled 5 is indeed the parent of the node labeled 12. The node labeled 2 has a left child with value 2n+1 = 2*2+1 = 5, and a right child with value 2n+2 = 2*2+2 = 6. It all works out, I can write a program that can calculate parent, left and right child links once it knows its own node number. The nodes are numbered in breadth-first order, too.

I decided to write the “file name” part of the URL path as node_$NUMBER.html. With that convention, an Apache mod_rewrite configuration like this will send all requests for “junkyard” URLs to the single PHP program.

RewriteRule ^.*/node_..*.html$ /node.php [L]

Don’t bother clicking this link.