For security concerns, a security traversal service can route data flows through a sequences of security devices (middleboxes). In this paper, we identify the problem of delay guarantee in security traversal and propose a scheme to dynamically change the security traversal path. To provide deterministic delay guarantee with minimum virtual machine (VM) and transmission cost, we model this security traversal path determination as a constrained shortest path problem (CSP) and propose an optimal security traversal with middlebox addition (OSTMA) mechanism. Besides, we implement the proposed OSTMA mechanism in an OpenFlow network by designing a centralized security traversal controller to dynamically monitor the network condition information and reconfigure the security traversal path. Our experimental results show that the proposed dynamic security traversal scheme can still achieve delay requirements for network topology changes and burst traffic.