Improving the power grid's security against cyber-physical attacks has been a major challenge for the power grid operators since the cyber attack on the Ukrainian grid in Dec. 2016. In order to partly address this challenge, we study the problem of power grid state estimation following such an attack. We assume that an adversary attacks an area by disconnecting some lines within the attacked area and blocking the measurements coming from inside the attacked area from reaching the control center in order to mask the failed lines. The objective is to use the phase angle measurements before and partial measurements after the attack to detect the failed lines. Despite recent efforts, there is no method that is both efficient and robust for estimating the state of the grid after such an attack in practical noisy settings. In this work, we provide such a method using Bayesian regression. Bayessian regression allows us to determine the probability that each line is failed, instead of a 0-1 hard decision on the status of the lines. These probabilities reflect the uncertainty in the detection, depending on the noise level. We show that these probabilities can further be used to limit the search space and significantly improve the running time of the existing brute force search methods for failed lines detection.