We present a software tool and a framework for security protocol change management. While we focus on trust negotiation protocols in this paper, many of the ideas are generally applicable to other types of protocols. Trust negotiation is a flexible approach to access control that is well suited to dynamic environments typical of service-oriented applications. However, managing the evolution of trust negotiation protocols is a difficult problem that has not been sufficiently addressed, especially in situations where there are ongoing negotiations. By using our framework, the consequences of changing the protocol that applies to ongoing trust negotiations can be automatically determined. We have also implemented a database-backed GUI tool to manage the change process as an extension of an existing system, and we have performed experiments to test the efficiency of our management software. Our experimental results show that the techniques proposed can scale to applications with tens of thousands of simultaneous users even on commodity PCs.