Entropy and Software Systems: Towards an Information-Theoretic Foundation of Software Testing

摘要

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 behav-iorial 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.