Due to the excessive use of cloud-based machine learning (ML) services, the smart cyber-physical systems (CPS) are increasingly becoming vulnerable to black-box attacks on their ML modules. Traditionally, the black-box attacks are either transfer attacks requiring model stealing, or score/decision-based gradient estimation attacks requiring a large number of queries. In practical scenarios, especially for cloud-based ML services and timing-constrained CPS use-cases, every query incurs a huge cost, thereby rendering state-of-the-art decision-based attacks ineffective in such settings. Towards this, we propose a novel methodology for automatically generating an extremely fast and imperceptible decision-based attack called FaDec. It follows two main steps: (1) fast estimation of the classification boundary by combining the half-interval search-based algorithm with gradient sign estimation to reduce the number of queries; and (2) adversarial noise optimization to ensure the imperceptibility. For illustration, we evaluate FaDec on the image recognition and traffic sign detection using multiple state-of-the-art DNNs trained on CIFAR-10 and the German Traffic Sign Recognition Benchmarks (GTSRB) datasets. The experimental analysis shows that the proposed FaDec attack is 16x faster compared to the state-of-the-art decision-based attacks, and generates an attack image with better imperceptibility for a much lesser number of iterations, thereby making our attack more powerful in practical scenarios. We open-sourced the complete code and results of our methodology at https://github.com/fklodhi/FaDec.