Search services are the main interface through which people discover information on the Internet. A fundamental calllenge in testing search services is the lack of oracles. The sheer volume of data on the Internet prohibits testers from verifying the results. Furthermore, it is difficult to objectively assess the ranking quality because different assessors can have very different opinions on the relevance of a Web page to a query. This paper presents a novel method for automatically testing search services without the need of a human oracle. Experimental findings have revealed that some commonly used search engines, including Google, yahoo! and Live Search, are not as reliable as most users would expect in the sense that they can fail to find pages that exist in their own repositories, and can rank pages in a way that is logically inconsistent. Suggestions are made for search services providers to improve their service quality.