  In an interdomain network, autonomous systems (ASes) often establish peering
agreements, so that one AS (agreement consumer) can influence the routing
policies of the other AS (agreement provider). Peering agreements are
implemented in the BGP configuration of the agreement provider. It is crucial
to verify their implementation because one error can lead to disastrous
consequences. However, the fundamental challenge for peering agreement
verification is how to preserve the privacy of both ASes involved in the
agreement. To this end, this paper presents IVeri, the first privacy-preserving
interdomain agreement verification system. IVeri models the interdomain
agreement verification problem as a SAT formula, and develops a novel,
efficient, privacy-serving SAT solver, which uses oblivious shuffling and
garbled circuits as the key building blocks to let the agreement consumer and
provider collaboratively verify the implementation of interdomain peering
agreements without exposing their private information. A prototype of IVeri is
implemented and evaluated extensively. Results show that IVeri achieves
accurate, privacy-preserving interdomain agreement verification with reasonable
overhead.
