Motivated by the increasing importance of knowing which operating systems are running in a given network, we evaluated operating system discovery (OSD) tools. The results indicated a serious lack of accuracy in current OSD tools. This thesis proposes a new OSD approach which addresses the limitations of existing approaches and leads to a more flexible, less intrusive, and much more accurate tool. Moreover, unlike existing OSD tools which are completely ad hoc, our approach is formal and follows the principles of diagnosis problem solving. This formalization allows us to characterize the complexity of OSD, to use well-tested algorithms, and to benefit from numerous extensions. To fully address the needs of OSD, we generalize the theory of diagnosis with a query-based extension. This extension leads to a spectrum of test selection algorithms to solve each query.