Automated functional testing of web search engines in the absence of an oracle

A software product is functionally correct if it behaves according to the functional specification. Compared with other quality aspects of Web search engines such as performance and capacity, functional correctness is more fundamental but its verification suffers from the oracle problem: It is often difficult or impossible to decide whether outcomes of test case executions are correct. For example, how can testers decide whether the results returned by a Web search engine are actually correct and complete? In this paper, we present an approach to help alleviate the oracle problem in testing search engines. The testing process is fully automatic, including test case generation, execution, output collection, and verification. A tool has been developed to implement the approach and detected failures in popular search engines including Google, Yahoo!, and Microsoft's Live Search. The failures are illustrated using screenshots, and more experimental results are analyzed