Counterexample ranking using mined invariants

Abstract

Unit testing and verification constitute an important step in the validation life cycle of large and complex multi-component designs. Many unit validation methods often suffer from the problem of false negatives, when they analyze a component in isolation and look for errors. It often turns out that some of the reported unit failures are infeasible, i.e. the valuations of the component input parameters that trigger the failure scenarios, though feasible on the unit in isolation, cannot occur in practice considering the integrated design, in which the unit-under-test is instantiated. In this work, we consider this problem in the context of a multi-component design code, with a set of unit level failures reported on a specific unit. We present here an automated two-stage failure scenario classification and prioritization strategy that can filter out false negatives and cluster them accordingly. The use of classical AI and program analysis techniques in conjunction with formal verification helps in developing new frameworks for reasoning and deduction, which appear promising for a wide variety of problems. Experiments show that our clustering and prioritization scheme works quite well in practice.

Short bio

Ansuman Banerjee is currently serving as an Assistant Professor at the Advanced Computing and Microelectronics Unit, Indian Statistical Institute Kolkata. His research interests include design automation for embedded systems, hardware-software verification, VLSI CAD, and automata theory. Ansuman received his Ph.D. from IIT Kharagpur. Prior to joining ISI, he served as a post-doctoral researcher in the Computer Science department at National University of Singapore, and worked for Interra Systems India Pvt. Ltd., where he worked as part of the synthesis and verification team.