Adversarial examples undermine the reliability of neural networks. To defend against attacks, multiple approaches have been proposed. However, many of them introduce high training overhead or high inference overhead, some significantly decrease the network’s accuracy or insufficiently increase the network’s robustness, and others do not scale to deep networks. To mitigate all these shortcomings, we propose a new form of defense: optimal program synthesis of short \emph{repair programs}, integrated into a trained network. A repair program modifies a few neurons by using a few other neurons. The challenge is to identify the most successful combination of neurons to enhance the network’s robustness while maintaining high accuracy. We introduce DefEnSyn, a stochastic synthesizer of repair programs. To cope with the exponential number of neuron combinations, DefEnSyn learns the effective combinations by synthesizing repair programs of increasing length. We evaluate DefEnSyn on classifiers for ImageNet and CIFAR-10 and show it enhances the robustness of networks to $L_\infty$-, $L_2$-, and $L_0$- black-box adversarial example attacks and to backdoor attacks. DefEnSyn’s repair programs enhance the networks’ robustness on average by $+40%$ and up to $+71%$. DefEnSyn decreases the network’s accuracy by only $\approx -1%$. We demonstrate that DefEnSyn outperforms existing state-of-the-art defenses based on adversarial training, randomization, and repair, in both robustness and accuracy.