It is well-known that standard neural networks, even with a high\nclassification accuracy, are vulnerable to small $\\ell_\\infty$-norm bounded\nadversarial perturbations. Although many attempts have been made, most previous\nworks either can only provide empirical verification of the defense to a\nparticular attack method, or can only develop a certified guarantee of the\nmodel robustness in limited scenarios. In this paper, we seek for a new\napproach to develop a theoretically principled neural network that inherently\nresists $\\ell_\\infty$ perturbations. In particular, we design a novel neuron\nthat uses $\\ell_\\infty$-distance as its basic operation (which we call\n$\\ell_\\infty$-dist neuron), and show that any neural network constructed with\n$\\ell_\\infty$-dist neurons (called $\\ell_{\\infty}$-dist net) is naturally a\n1-Lipschitz function with respect to $\\ell_\\infty$-norm. This directly provides\na rigorous guarantee of the certified robustness based on the margin of\nprediction outputs. We then prove that such networks have enough expressive\npower to approximate any 1-Lipschitz function with robust generalization\nguarantee. We further provide a holistic training strategy that can greatly\nalleviate optimization difficulties. Experimental results show that using\n$\\ell_{\\infty}$-dist nets as basic building blocks, we consistently achieve\nstate-of-the-art performance on commonly used datasets: 93.09% certified\naccuracy on MNIST ($\\epsilon=0.3$), 35.42% on CIFAR-10 ($\\epsilon=8/255$) and\n16.31% on TinyImageNet ($\\epsilon=1/255$).\n