Workflow systems are popular in daily business processing. Since vulnerability cannot be totally removed from a workflow management system, successful attacks always happen and may inject malicious tasks or incorrect data into the workflow system. Referring to the incorrect data will further corrupt more data objects in the system, which comprises the integrity level of the system. This problem cannot be efficiently solved by existing defense mechanisms, such as access control, intrusion detection, and checkpoints. In this paper, we propose a practical solution for on-line attack recovery of workflows. The recovery system discovers all damages caused by the malicious tasks that the intrusion detection system reports and automatically repairs the damages based on data and control dependencies among workflow tasks. We analyze the behaviors of our attack recovery system based on the Continuous Time Markov Chain model. The analytical results demonstrate that our system is practical when the parameters of the system are reasonably designed.