Shodan has been acknowledged as one of the most popular search engines available today, designed to crawl the Internet and to index discovered services. This paper expands the features exposed by Shodan with advanced vulnerability assessment capabilities embedded into a novel tool called Shodan-based vulnerability assessment tool (ShoVAT). ShoVAT takes the output of traditional Shodan queries and performs an in-depth analysis of service-specific data, that is, service banners. It embodies specially crafted algorithms which rely on novel in-memory data structures to automatically reconstruct Common Platform Enumeration names and to proficiently extract vulnerabilities from National Vulnerability Database. Compared with the state of the art, ShoVAT brings several novel and significant contributions because it encompasses automated vulnerability identification techniques, it can return highly accurate results with customized and even purposefully modified service banners, and it supports historical service vulnerability analysis without the need to deploy additional monitoring infrastructures. The experiments performed on 1501 services in 12 different institutions across different sectors revealed high accuracy of results and a total of 3922 known vulnerabilities. Copyright (c) 2015John Wiley & Sons, Ltd.