Extended Abstract: Viability of Decision Trees for Learning Models of Systems

Abstract:
Abstract models of embedded systems are useful for various tasks, ranging from diagnosis, over testing to monitoring at run-time. However, deriving a model for an unknown system is difficult. We consider systems that can be modeled as finite state transducers. Existing approaches for learning provably precise models are costly. On the other hand, generic learners like decision trees can identify specific properties of systems and have successfully been applied, e.g., for anomaly detection and test case identification. We consider Decision Tree Learning (DTL) to derive a model of a system from given observations with bounded history. We prove theoretical limitations and explain why, nonetheless, usage in realistic applications is successful. Experimental results demonstrate in which cases the approach is successful and effective.