  The wide deployment of deep neural networks, though achieving great success
in many domains, has severe safety and reliability concerns. Existing
adversarial attack generation and automatic verification techniques cannot
formally verify whether a network is globally robust, i.e., the absence or not
of adversarial examples in the input space. To address this problem, we develop
a global robustness verification framework with three components: 1) a novel
rule-based ``back-propagation'' finding which input region is responsible for
the class assignment by logic reasoning; 2) a new network architecture Sliding
Door Network (SDN) enabling feasible rule-based ``back-propagation''; 3) a
region-based global robustness verification (RGRV) approach. Moreover, we
demonstrate the effectiveness of our approach on both synthetic and real
datasets.
