We study the time complexity of McKay's algorithm to compute canonical forms and automorphism groups or graplu. The algorithm is based on a type of backtrack search, and it performs pruning by discovered automorphisms and by hashing partial information of vertex labelings. In practice, the algorithm is implemented in the nauty package. We obtain colorings of Fürer's graphs that allow the algorithm to compute their canonical forms in polynomial time. We then prove an exponential lower bound or the algorithm for connected 3-regular graphs of color-class size 4 using Fürer's construction. We conducted experiments with nauty for these graphs. Our experimental results also indicate the same exponential lower bound.