DAE2FSM: Automatic generation of accurate discrete-time logical abstractions for continuous-time circuit dynamics

We abstract the I/O functionality of continuous-time dynamical systems (e.g., SPICE netlists with combinational and sequential logic) as Finite State Machines (FSMs). This enables efficient simulation of large designs implemented with less-than-perfect devices and components, and also opens the door to formal verification of transistor-level designs against higher-level specifications. In particular, our automatically generated FSMs faithfully capture the behaviour of latches, flip-flops, and circuits constructed from them. Among other technical advances, we generalize an existing (binary-only) FSM-learning approach to arbitrary I/O alphabets, which empowers it to learn high-fidelity abstractions of multi-level-discretized, multi-input/multi-output systems. Our approach, when applied to correctly functioning latches and flip-flops, is able to learn compact, multi-input FSM abstractions whose predictions closely match SPICE simulations. In addition, we have also applied our technique to produce multi-level-discretized FSM representations of digital systems that nevertheless exhibit "analogish" traits, such as an over-clocked, error-prone D-flip-flop. For such circuits, the automatically learned FSM abstraction includes additional states that characterise "failure modes" of the circuit for specific input sequences (these failure modes are also confirmed by SPICE simulations). Finally, we demonstrate that our technique is also applicable to larger and more complex multi-input, multi-output systems; for example, we are able to automatically derive an accurate FSM abstraction of a 280-transistor (BSIM4), 0-to-5 increment/decrement counter.