Relevant odors signaling food, mates, or predators can be masked by unpredictable mixtures of less relevant background odors. Here, we developed a mouse behavioral paradigm to test the role played by the novelty of the background odors. During the task, mice identified target odors in previously learned background odors and were challenged by catch trials with novel background odors, a task similar to visual CAPTCHA. Female wild-type (WT) mice could accurately identify known targets in novel background odors. WT mice performance was higher than linear classifiers and the nearest neighbor classifier trained using olfactory bulb glomerular activation patterns. Performance was more consistent with an odor deconvolution method. We also used our task to investigate the performance of female Cntnap2 mice, which show some autism-like behaviors. Cntnap2 mice had glomerular activation patterns similar to WT mice and matched WT mice target detection for known background odors. However, Cntnap2 mice performance fell almost to chance levels in the presence of novel backgrounds. Our findings suggest that mice use a robust algorithm for detecting odors in novel environments and this computation is impaired in Cntnap2 mice.