Two programs are checked for equivalence. Based on concrete states, a control path in each program is determined. A symbolic representation of the output is determined for each program and verified that for every input that would execute the programs on the determined control paths, the outputs are the same. Based on this operation, iterative processing may be performed to verify equivalence for all inputs of the program.