  Semantic segmentation is a fundamental visual task that finds extensive
deployment in applications with security-sensitive considerations. Nonetheless,
recent work illustrates the adversarial vulnerability of semantic segmentation
models to white-box attacks. However, its adversarial robustness against
black-box attacks has not been fully explored. In this paper, we present the
first exploration of black-box decision-based attacks on semantic segmentation.
First, we analyze the challenges that semantic segmentation brings to
decision-based attacks through the case study. Then, to address these
challenges, we first propose a decision-based attack on semantic segmentation,
called Discrete Linear Attack (DLA). Based on random search and proxy index, we
utilize the discrete linear noises for perturbation exploration and calibration
to achieve efficient attack efficiency. We conduct adversarial robustness
evaluation on 5 models from Cityscapes and ADE20K under 8 attacks. DLA shows
its formidable power on Cityscapes by dramatically reducing PSPNet's mIoU from
an impressive 77.83% to a mere 2.14% with just 50 queries.
