Summary: This paper considers the problem of modality conflicts in security policies for Service-Oriented Architecture (SOA) environments. We describe the importance of this problem and present an algorithm for discovering modality conflicts with low overhead. Often being of large scale and compound structure, SOA systems can definitely benefit from that efficiency boost. Another advantage of the proposal over previously developed algorithms is its formal proof of correctness, also presented in this paper.