A system and a method automatically generate video-based tests to distinguish human users from computer software agents. The system comprises a CAPTCHA generation engine, a CAPTCHA serving engine, a video clips database, and a video tests database. The CAPTCHA generation engine selects a video clip from the video clips database, and segments the video clip into multiple video segments. For each video segment, the CAPTCHA generation engine associates a plurality of related queries with the video segment, generates a video test based on the association, and stores in the video tests database. A CAPTCHA serving engine selects a video test for a user, maintaining a user trial counter for each user taking the video test. Based on the user trial counter information and the response to the selected video test, the CAPTCHA serving engine determines whether the user is a human user.