Adaptive Model Checking

• Published in: Logic journal of the IGPL 2006-10, Vol.14 (5), p.729-744
• Main Authors: Groce, Alex, Peled, Doron, Yannakakis, Mihalis
• Format: Article
• Language: English
• ISSN: 1367-0751; 1368-9894
• DOI: 10.1093/jigpal/jzl007

We consider the case where inconsistencies are present between a system and its corresponding model, used for automatic verification. Such inconsistencies can be the result of modeling errors or recent modifications of the system. Despite such discrepancies, we can still attempt to perform automatic verification. In fact, as we show, we can sometimes exploit the verification results to assist in automatically learning the required updates to the model. In a related previous work, we have suggested the idea of black box checking, where verification starts without any model, and the model is obtained while repeated verification attempts are performed. Under the current assumptions, an existing inaccurate (but not completely obsolete) model is used to expedite the updates. We use techniques from black box testing and machine learning. We present an implementation of the proposed methodology called AMC (for Adaptive Model Checking). We discuss some experimental results, comparing various tactics of updating a model while trying to perform model checking.