Linmin Yang, Zhe Dang, Thomas R. Fischer, Min Sik Kim and Li Tan. In Proceedings of the ACM Sigsoft FSE/SDP workshop on Future of software engineering research (FSE-FoSER'10). ACM press. Santa Fe, New Mexico. November, 2010.
We integrate information theory into software testing. In particular, we use entropy in information theory to measure the amount of uncertainty in a software system before it is fully tested, and we show how the amount decreases when we test the system. Moreover, we introduce behaviorial complexity as a novel complexity metric for labeled graphs (which can be interpreted as control flow graphs, design specifications, etc.), which is also based on information theory. We seek practical approaches in testing real systems using the above theories, and we apply our novel approaches in testing model-based embedded systems and network intrusion detection systems. Our information-theoretic approach is syntax-independent, which is a desired property in software testing.