This paper studies fault tolerance in switching reconfigurable nano-crossbar arrays. Both permanent and transient faults are taken into account by independently assigning stuck-open and stuck-closed fault probabilities into crosspoints. In the presence of permanent faults, a fast and accurate heuristic algorithm is proposed that uses the techniques of index sorting, backtracking, and row matching. The algorithm's effectiveness is demonstrated on standard benchmark circuits in terms of run-time, success rate, and accuracy. In the presence of transient faults, tolerance analysis is performed by formally and recursively determining tolerable fault positions. In this way, we are able to specify fault tolerance performances of nano-crossbars without relying on randomly generated faults that is relatively costly regarding that the number of fault distributions in a crossbar grows exponentially with the crossbar size.